How FFF Multi-Pattern OR Search Works: A Deep Dive into the Rust Implementation

FFF's multi-pattern OR search compiles all literal patterns into a single Aho-Corasick automaton and applies a bigram pre-filter to scan files in one SIMD-accelerated pass, returning matches for any pattern while OR-ing bigram bitsets to minimize file I/O.

The dmtrKovalenko/fff repository implements a high-performance file picker with advanced grep capabilities. Its multi-pattern OR search—commonly used for searching multiple literal strings simultaneously—combines finite automata theory with intelligent indexing to deliver sub-millisecond results across thousands of files. This architecture enables Neovim users to search for multiple terms like "init" or "setup" in a single query without the overhead of multiple passes.

Entry Point: FilePicker::multi_grep

The public API for OR searches resides in FilePicker::multi_grep within the core crate. Located in crates/fff-core/src/file_picker.rs at lines 1178-1185, this method collects the current search context and delegates to the low-level engine.

pub fn multi_grep(
    &self,
    patterns: &[&str],
    constraints: &[fff_query_parser::Constraint<'_>],
    options: &GrepSearchOptions,
) -> GrepResult<'_> { … }

This function aggregates the bigram overlay, arena pointers, and abort signal before forwarding execution to multi_grep_search in the grep module. It maintains the same return type (GrepResult) as single-pattern searches, ensuring API consistency across the codebase.

Core Algorithm: multi_grep_search

The actual implementation lives in crates/fff-core/src/grep.rs at lines 44-71 within the multi_grep_search function. This routine orchestrates three distinct phases: automaton construction, bigram pre-filtering, and single-pass scanning.

pub(crate) fn multi_grep_search<'a>(
    files: &'a [FileItem],
    patterns: &[&str],
    constraints: &[Constraint<'_>],
    options: &GrepSearchOptions,
    …
) -> GrepResult<'a> {
    // 1️⃣ Build a *single* Aho‑Corasick automaton from all patterns.
    // 2️⃣ Apply a **bigram OR pre‑filter** so a file is kept if it matches
    //    the bigram set of *any* pattern.
    // 3️⃣ Scan each candidate file once with the automaton; every match
    //    reports which pattern triggered it, giving true OR semantics.
}

Aho-Corasick Automaton Construction

All literal patterns compile into one deterministic finite automaton using aho_corasick::AhoCorasick. This data structure enables SIMD-accelerated scanning of a file's bytes in a single linear pass. Unlike running separate regex engines for each pattern, the automaton simultaneously tracks all pattern states, emitting match events with the specific pattern index that triggered the hit.

Bigram Pre-Filter with OR Logic

When a bigram index exists, the engine extracts bigram signatures from each pattern and queries the index for candidate files. Crucially, the resulting bitsets are OR-ed together using the |= operator—meaning a file is retained for full scanning if it contains the bigrams of any pattern in the set. This bigram OR pre-filter dramatically reduces the candidate set before the more expensive Aho-Corasick pass begins.

Smart Case Handling

The search respects the smart_case option in GrepSearchOptions. When enabled, the search becomes case-insensitive only if all supplied patterns are lowercase; otherwise, it maintains case-sensitivity. This logic executes before automaton construction to ensure the Aho-Corasick matcher uses the correct byte patterns.

Constraints and Retry Logic

File-path constraints apply first to filter the candidate list. If these constraints eliminate all files—suggesting the user included path tokens in the search text—the engine automatically removes path-related tokens and retries the search. This fallback ensures users receive results even when mixing path and content queries.

FFI and Lua Integration

The Rust core exposes multi-pattern functionality through a C-FFI layer in crates/fff-c/src/lib.rs, specifically via the fff_multi_grep function. The Lua bridge in lua/fff/rust/init.lua loads this compiled shared library, allowing Neovim plugins to invoke the OR search through picker:multi_grep(patterns, constraints, opts).

Usage Examples

Searching from Lua (Neovim)

Use the high-level Lua API to search for multiple patterns with smart case sensitivity:

-- Lua (inside Neovim)
local picker = require('fff').picker()

-- Search for either "init" or "setup" (case‑insensitive smart case)
local patterns = { "init", "setup" }
local constraints = {}               -- optional path / file‑type constraints
local opts = { smart_case = true }   -- same options as single grep

local result = picker:multi_grep(patterns, constraints, opts)

-- Iterate over matches
for _, file in ipairs(result.files) do
  print(string.format("%s:%d: %s", file.path, file.line, file.text))
end

Direct Rust API Usage

For Rust developers integrating fff-core directly:

// Direct Rust usage (unit‑test style)
let picker = Picker::new(...);
let patterns = ["ActorAuth", "actor_auth"];
let constraints = [];
let opts = GrepSearchOptions::default();

let grep_res = picker.multi_grep(&patterns, &constraints, &opts);
assert!(!grep_res.matches.is_empty());

Summary

• FFF multi-pattern OR search uses a single Aho-Corasick automaton to match multiple literal patterns in one SIMD-accelerated file scan.
• The bigram OR pre-filter ORs pattern bitsets (|=) to include files matching any pattern's bigram signature, minimizing expensive I/O.
• Smart case detection automatically switches to case-insensitive mode when all patterns are lowercase.
• The architecture spans crates/fff-core/src/file_picker.rs (public API) and crates/fff-core/src/grep.rs (core algorithm), with FFI bindings in crates/fff-c/src/lib.rs for Lua integration.
• Each Match result includes the pattern index, allowing callers to identify which specific term triggered the hit.

Frequently Asked Questions

How does FFF handle case sensitivity in multi-pattern searches?

FFF applies smart case logic by inspecting the patterns before building the automaton. If options.smart_case is true and every pattern contains only lowercase characters, the search executes case-insensitively; otherwise, it maintains exact case matching. This occurs in multi_grep_search before constructing the Aho-Corasick matcher.

What makes FFF's multi-pattern search faster than running multiple separate grep commands?

The implementation uses a single Aho-Corasick automaton to track all patterns simultaneously during one linear scan of the file bytes, leveraging SIMD instructions for throughput. Additionally, the bigram pre-filter ORs the pattern signatures to eliminate non-candidate files before scanning begins, whereas multiple grep commands would require redundant file reads and separate state machines.

Can I mix path constraints with multi-pattern content searches?

Yes. The constraints parameter in FilePicker::multi_grep accepts path and file-type filters that execute before the content search. If these constraints filter out all results, the engine automatically strips path-related tokens and retries, assuming the user accidentally included filename fragments in the pattern list.

Does the multi-pattern search return which specific pattern matched each result?

Yes. The GrepResult returned by multi_grep_search contains Match structures that include the pattern index corresponding to the specific term that triggered the match. This allows the UI to highlight which of the OR patterns was found at each location.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}