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

> Explore FFF's multi-pattern OR search: discover how it compiles patterns into an Aho-Corasick automaton and uses a bigram pre-filter for one SIMD-accelerated pass, minimizing I/O and OR-ing bitsets for fast results.

- Repository: [Dmitriy Kovalenko/fff](https://github.com/dmtrKovalenko/fff)
- Tags: deep-dive
- Published: 2026-06-02

---

**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`](https://github.com/dmtrKovalenko/fff/blob/main/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.

```rust
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`](https://github.com/dmtrKovalenko/fff/blob/main/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.

```rust
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`](https://github.com/dmtrKovalenko/fff/blob/main/crates/fff-c/src/lib.rs), specifically via the `fff_multi_grep` function. The Lua bridge in [`lua/fff/rust/init.lua`](https://github.com/dmtrKovalenko/fff/blob/main/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
-- 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:

```rust
// 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`](https://github.com/dmtrKovalenko/fff/blob/main/crates/fff-core/src/file_picker.rs) (public API) and [`crates/fff-core/src/grep.rs`](https://github.com/dmtrKovalenko/fff/blob/main/crates/fff-core/src/grep.rs) (core algorithm), with FFI bindings in [`crates/fff-c/src/lib.rs`](https://github.com/dmtrKovalenko/fff/blob/main/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.