Fuzzy File Search

Feature Definition

When a developer wants to open a file, they rarely type the full path. They type prom and expect to find src/session/prompt.ts. They type base_cod and expect aider/coders/base_coder.py. Fuzzy file search is the mechanism that turns partial, approximate input into ranked file path matches.

For an AI coding agent, fuzzy file search serves two distinct roles:

1. TUI file picker: An interactive UI element where the human user types a partial filename and sees ranked matches update in real time. This is the Ctrl+P / Cmd+P experience from VS Code, reimplemented in a terminal.
2. File discovery tool: A non-interactive function the LLM can call to find files by approximate name. The model knows it needs “the database migration file” but doesn’t know the exact path — fuzzy search bridges that gap.

The hard parts are:

• Speed: The file picker must feel instant. Walking a 100k-file repository and scoring every path against the query must complete in under 50ms for each keystroke. This demands parallel file walking, incremental matching, and careful memory layout.
• Ranking quality: foobar should match src/foo/bar.rs and FooBar.java and foo_bar_test.py, but the ranking should prefer exact substring matches over scattered character matches. Case sensitivity should be context-dependent (smart case: case-insensitive unless the query contains uppercase).
• Ignore handling: The file walker must respect .gitignore, .ignore, and hardcoded exclusions (node_modules/, .git/, target/) without re-implementing those rules from scratch.
• Incremental updates: As the user types additional characters, the search should narrow incrementally rather than restart from scratch. This is the difference between a matcher that appends to its previous state and one that recomputes everything.

For adjacent non-fuzzy discovery/search primitives, see List, Glob, and Grep. For the ripgrep backend and ignore semantics that feed several of those flows, see Ripgrep Integration.

---

Aider Implementation

Reference: references/aider/aider/ | Commit: b9050e1d5faf8096eae7a46a9ecc05a86231384b

No Fuzzy Search

Aider does not implement fuzzy file search. There is no interactive file picker in its TUI (which is a simple readline-based prompt, not a full terminal UI). There is no fuzzy matching tool exposed to the LLM.

File discovery in Aider happens through two mechanisms:

1. Exact glob matching (commands.py:799-898):

The /add command accepts glob patterns that are resolved via Python’s pathlib.Path.glob():

raw_matched_files = list(Path(self.coder.root).glob(pattern))

This is exact glob matching — *.py matches all Python files, **/test_*.py matches test files — but there’s no fuzzy ranking. The pattern prom won’t match prompt.ts.

2. Identifier-to-filename matching (base_coder.py:684-699):

When the user’s message contains a word that matches a filename stem (basename without extension), Aider adds that file to the repo map’s boosted set:

def get_ident_filename_matches(self, idents):
    all_fnames = defaultdict(set)
    for rel_fname in self.get_all_relative_files():
        base = Path(rel_fname).stem.lower()
        if len(base) >= 5:
            all_fnames[base].add(rel_fname)
    return all_fnames

This matches prompt to prompt.ts but requires the stem to be at least 5 characters and only matches exact stems — no fuzzy scoring. It’s a heuristic for repo map personalization, not a search feature.

Design Implication

Aider’s lack of fuzzy search is consistent with its architecture: the user tells the LLM which files to work with (via /add), and the repo map fills in context automatically. The model never needs to “find” files because the human curates the file set. This works for workflows where the user knows the codebase, but it breaks down when the user says “fix the bug in the login handler” and expects the agent to find the relevant files autonomously.

---

Codex Implementation

Reference: references/codex/codex-rs/file-search/src/lib.rs | Commit: 4ab44e2c5cc54ed47e47a6729dfd8aa5a3dc2476

file-search Crate

Codex has a dedicated file-search crate that implements fuzzy file finding using nucleo, the fuzzy matcher from the Helix text editor. This is the most sophisticated fuzzy search implementation across the three reference codebases.

Architecture: Two-Thread Model

The crate uses two cooperating worker threads:

Walker thread (lines 382-454): Uses the ignore crate’s WalkBuilder for parallel, gitignore-aware directory traversal. Walks the filesystem and feeds discovered file paths into nucleo’s injector channel.

let walker = WalkBuilder::new(root)
    .follow_links(true)
    .build_parallel();

walker.run(|| {
    Box::new(move |entry| {
        // Feed path into nucleo injector
        injector.push(path, |cols| {
            cols[0] = path_string.into();
        });
        WalkState::Continue
    })
});

Matcher thread (lines 456-571): Consumes the walker output, applies the fuzzy query, and emits ranked results via a SessionReporter callback.

nucleo.pattern.reparse(
    0,
    &query,
    CaseMatching::Smart,       // auto case sensitivity
    Normalization::Smart,      // unicode normalization
    append,                    // incremental: append to previous query
);

The append flag is the key to incremental matching. When the user types an additional character, nucleo can narrow the previous result set rather than re-scoring every path from scratch.

Nucleo Configuration

let nucleo = Nucleo::new(
    Config::DEFAULT.match_paths(),  // path-aware scoring
    notify,                         // completion callback
    Some(threads.get()),           // worker threads (default 2)
    1,                              // column count (single path string)
);

Config::DEFAULT.match_paths() enables path-aware scoring, which means nucleo treats / as a word boundary. This makes p/t match packages/tools with a higher score than apart/contest, because the / boundaries align with the query structure.

Public API

One-shot search (lines 141-200):

pub fn run(
    pattern_text: &str,
    roots: Vec<PathBuf>,
    options: FileSearchOptions,
    cancel_flag: Option<Arc<AtomicBool>>,
) -> anyhow::Result<FileSearchResults>

Creates a session, runs the search to completion, and returns all results. Used when the model calls a file-search tool.

Session-based search (lines 200-290):

pub fn create_session(
    search_directories: Vec<PathBuf>,
    options: FileSearchOptions,
    reporter: Arc<dyn SessionReporter>,
    cancel_flag: Option<Arc<AtomicBool>>,
) -> anyhow::Result<FileSearchSession>

Creates a long-lived search session that supports incremental query updates. Used for the TUI’s interactive file picker.

pub trait SessionReporter: Send + Sync + 'static {
    fn on_update(&self, snapshot: &FileSearchSnapshot);
    fn on_complete(&self);
}

The reporter receives progressive updates as new matches are found and scored, enabling real-time display in the TUI.

FileSearchOptions

pub struct FileSearchOptions {
    pub limit: NonZero<usize>,         // max results (default 20)
    pub exclude: Vec<String>,          // exclusion patterns
    pub threads: NonZero<usize>,       // worker threads (default 2)
    pub compute_indices: bool,         // include matched char indices
    pub respect_gitignore: bool,       // honor .gitignore (default true)
}

The compute_indices option enables character-level match highlighting — when enabled, each FileMatch includes a Vec<u32> of the indices in the path string that matched the query. This is used by the TUI to bold or color the matched characters.

Result Structure

pub struct FileMatch {
    pub score: u32,              // nucleo match score (higher = better)
    pub path: PathBuf,           // relative path from search root
    pub root: PathBuf,           // search root directory
    pub indices: Option<Vec<u32>>, // matched character positions
}

Scoring and Tie-Breaking

Results are sorted by score descending, with ties broken alphabetically by path (lines 303-316):

pub fn cmp_by_score_desc_then_path_asc<T, FScore, FPath>(
    score_of: FScore,
    path_of: FPath,
) -> impl FnMut(&T, &T) -> std::cmp::Ordering

CLI

The file-search crate includes a standalone CLI (cli.rs) for testing:

file-search [OPTIONS] [PATTERN]
  --json              JSON output
  --limit <N>         Max results (default 64)
  --cwd <PATH>        Search root
  --compute-indices   Include match indices
  --exclude <GLOB>    Exclusion patterns
  --threads <N>       Worker threads (default 2)

Thread Count Choice

The default of 2 threads is deliberate (not matching CPU count). The authors found that fuzzy file search is I/O-bound, not CPU-bound — the filesystem walking is the bottleneck, and throwing more threads at it yields diminishing returns after 2. This is documented implicitly by the default choice and tested empirically.

---

OpenCode Implementation

Reference: references/opencode/packages/opencode/src/file/index.ts | Commit: 7ed449974864361bad2c1f1405769fd2c2fcdf42

fuzzysort-Based Search

OpenCode uses the fuzzysort JavaScript library for fuzzy file matching. Unlike Codex’s nucleo (which is a purpose-built terminal fuzzy matcher), fuzzysort is a general-purpose fuzzy search library optimized for in-memory string matching.

File Index Cache

OpenCode maintains a cached file index that’s populated asynchronously on startup (lines 270-347 of file/index.ts):

const state = Instance.state(async () => {
    type Entry = { files: string[]; dirs: string[] }
    let cache: Entry = { files: [], dirs: [] }
    // Background population via Ripgrep.files()
})

The index is seeded by spawning rg --files (via the ripgrep wrapper) and collecting paths, then refreshed on demand. state().files() re-runs the scan when no fetch is currently in progress, so results stay relatively fresh without a filesystem watcher. Directories are tracked separately from files.

Search Function

export async function search(input: {
    query: string
    limit?: number
    dirs?: boolean
    type?: "file" | "directory"
}): Promise<string[]>

The search function (lines 544-582) applies fuzzysort against the cached file list:

1. Load cached files/dirs
2. Compute searchLimit as limit * 20 only for directory mode when hidden entries are not preferred; otherwise use limit
3. Run fuzzysort.go(query, files, { limit: searchLimit })
4. In directory mode, sort visible paths first and hidden paths last unless the query indicates hidden preference
5. Truncate to requested limit

Hidden File Handling

OpenCode’s hidden file sorting is a notable detail (lines 560-575):

// Check if a path has hidden components
function isHidden(path: string) {
    return path.split("/").some(part => part.startsWith("."))
}

// If query looks like it targets hidden files, prefer them
const prefersHidden = query.startsWith(".") || query.includes("/.")

In directory-mode results, typing .env makes hidden paths bubble up, while typing config keeps visible paths first. This is a small but important UX detail implemented via post-processing after fuzzysort scoring.

Glob Tool (Non-Fuzzy)

For exact pattern matching, OpenCode exposes a glob tool (tool/glob.ts) that wraps Ripgrep.files():

export const GlobTool = Tool.define("glob", {
    parameters: z.object({
        pattern: z.string(),
        path: z.string().optional(),
    }),
    async execute(params, ctx) {
        // Uses Ripgrep.files() with glob patterns
        // Hard limit: 100 results
        // Sort by mtime descending
    }
})

This is not fuzzy — *.ts matches all TypeScript files, **/test/** matches test directories. It’s the file-discovery counterpart to the grep tool (content search).

List Tool

OpenCode’s list tool (tool/ls.ts) provides directory tree rendering with built-in ignore patterns:

const IGNORE_PATTERNS = [
    "node_modules/", "__pycache__/", ".git/", "dist/",
    "build/", "target/", "vendor/", ".idea/", ".vscode/",
    // ... 20+ patterns
]

The list tool builds a hierarchical tree view:

src/
  session/
    prompt.ts
    message-v2.ts
  tool/
    grep.ts
    glob.ts

Results capped at 100 files, with directories listed first, then files, sorted alphabetically.

Ignore Handling

File ignore logic lives in file/ignore.ts (lines 4-82):

const FOLDERS = new Set([
    "node_modules", "bower_components", ".pnpm-store", "vendor",
    "dist", "build", "out", ".next", "target", "bin", "obj",
    ".git", ".svn", ".hg", ".vscode", ".idea", ".turbo",
    // ...
])

The match() function checks each path component against this set and applies additional glob patterns:

export function match(
    filepath: string,
    opts?: { extra?: Bun.Glob[]; whitelist?: Bun.Glob[] }
): boolean

The whitelist mechanism allows overriding ignores — if a file matches a whitelist glob, it’s included even if it would normally be ignored.

---

Pitfalls & Hard Lessons

fuzzysort vs nucleo Performance

fuzzysort is designed for in-memory JavaScript use. It’s fast enough for ~50k files but degrades on larger repositories. nucleo is designed for terminal fuzzy finders (fzf, Helix) and handles 500k+ entries with incremental updates. For a Rust-based agent, nucleo is the clear choice — it’s already Rust, it supports incremental matching, and it handles path-aware scoring natively.

File Index Staleness

Codex’s one-shot API walks the filesystem per invocation, while its session API keeps a live search session for incremental updates. OpenCode keeps an in-memory cache but refreshes it by re-running ripgrep when searches request data and no fetch is active. Both approaches can still have short windows of staleness, and neither relies on a filesystem watcher.

Incremental Matching Fragility

Nucleo’s incremental matching (the append flag) assumes the new query is a strict extension of the previous one — e.g., pro → prom → promp. If the user deletes a character (promp → prom), the incremental optimization doesn’t apply and a full re-score is needed. The Codex implementation handles this correctly by checking whether the new query starts with the previous one, but the code path for non-incremental updates is significantly slower on large file sets.

Smart Case Complexity

Both nucleo and fuzzysort implement “smart case” — case-insensitive unless the query contains an uppercase character. This is usually what users want, but it can surprise when searching for acronyms. Typing DB to find database.rs won’t match because smart case treats it as case-sensitive. There’s no perfect solution; both tools accept this trade-off.

Walker Thread Lifetime

In Codex’s session-based search, the walker thread can outlive the search query if the filesystem is slow (e.g., network mounts). The cancel_flag: Arc<AtomicBool> parameter allows external cancellation, but the walker thread checks it between entries, not mid-readdir. On very slow filesystems, cancellation can be delayed by seconds.

---

OpenOxide Blueprint

Architecture

OpenOxide should implement fuzzy file search at two levels:

1. Library layer: A file_search module using nucleo + ignore, reusable across TUI and tool contexts
2. Tool layer: A find_files tool exposing fuzzy search to the LLM
3. TUI layer: An interactive file picker component using the library layer with incremental updates

Core Crate Dependencies

Crate	Purpose
nucleo	Fuzzy matching engine (from Helix editor)
ignore	.gitignore-aware filesystem walking

Library API

pub struct FileSearcher {
    nucleo: Nucleo<PathBuf>,
    walker_handle: JoinHandle<()>,
    cancel: Arc<AtomicBool>,
}

impl FileSearcher {
    /// Create a new searcher that walks the given roots
    pub fn new(roots: Vec<PathBuf>, options: SearchOptions) -> Self;

    /// Update the query (supports incremental narrowing)
    pub fn set_query(&mut self, query: &str);

    /// Get current top-N results
    pub fn results(&self, limit: usize) -> Vec<FileMatch>;

    /// Cancel the walker and clean up
    pub fn cancel(&self);
}

pub struct SearchOptions {
    pub max_results: usize,          // default 100
    pub threads: usize,              // default 2
    pub respect_gitignore: bool,     // default true
    pub compute_indices: bool,       // default false
    pub exclude: Vec<String>,        // additional exclusion globs
}

pub struct FileMatch {
    pub score: u32,
    pub path: PathBuf,
    pub indices: Option<Vec<u32>>,   // for TUI highlighting
}

Tool Parameters

#[derive(Deserialize)]
struct FindFilesParams {
    query: String,                   // fuzzy query (required)
    path: Option<String>,           // search root (optional, default CWD)
    limit: Option<usize>,          // max results (optional, default 20)
}

The tool should use one-shot search (not session-based) since LLM tool calls are non-interactive. The TUI file picker should use the session-based API for incremental updates.

Output Format

Found {n} files matching "{query}":

src/session/prompt.ts
src/session/prompt_test.ts
packages/opencode/src/session/prompt.ts

Plain file paths, one per line, sorted by match score. No line numbers (this is file search, not content search). Include match count in header.

Relationship to Glob and Grep

Three complementary search tools:

Tool	Input	Matches Against	Use Case
find_files	Fuzzy query	File paths	”Find the config file”
glob	Glob pattern	File paths	”List all *.rs files”
grep	Regex pattern	File contents	”Find where DatabasePool is used”

All three should share the same ignore crate configuration for consistent .gitignore handling.