Build a Smaller ripgrep

The reconstruction should preserve the parallel search architecture, not copy ripgrep’s flags or output syntax.

Rebuild filtered traversal, worker-local search, work stealing, atomic output units, and coordinated shutdown.

1. Start with one concrete search

Accept a literal byte pattern and one root directory. Recursively visit files, read each through BufRead, and print matching lines. Keep this stage entirely single-threaded so filtering and errors are testable.

2. Separate traversal from eligibility

Introduce two decisions:

fn should_descend(entry: &DirEntry, rules: &Rules) -> bool;
fn should_search(entry: DirEntry) -> Option<Haystack>;

The first controls the directory tree. The second protects the searcher from directories, unsupported entries, and other application-level exclusions.

3. Make one reusable worker

Give SearchWorker its own read buffer and output Vec<u8>. Searching a file clears and reuses both. Return metadata separately from rendered bytes.

struct SearchWorker {
    needle: Vec<u8>,
    read_buf: Vec<u8>,
    output: Vec<u8>,
}

4. Add a fixed worker count

Begin with a bounded channel of file paths and N worker threads. This is not yet ripgrep’s fused traversal design, but it makes the concurrency boundary visible. Measure queue growth on a very wide directory.

5. Replace the central queue with local deques

Give every worker a LIFO deque of directory work and a list of peer stealers. Workers descend locally and steal only when idle. Carry the current ignore rules inside each directory work item.

Test an intentionally unbalanced tree: one root with a few files and one root with thousands. Confirm that workers steal from the busy root.

6. Stage then commit output

Search into the worker’s private buffer. Acquire the stdout lock only to write the completed buffer. Add a stress test that inserts yields between produced lines and confirms files never tear together.

7. Add distributed termination

An empty deque is not sufficient. Track active workers atomically and declare completion only when every worker is inactive while no deque contains work. Add a shared quit flag for broken pipes and “stop after first match.”

8. Extract generic contracts last

Once literal matching works, introduce a small matcher contract and an output sink. Keep traversal concrete unless a second traversal implementation creates a real abstraction pressure.

trait Matcher {
    type Error;
    fn find(&self, haystack: &[u8])
        -> Result<Option<Range<usize>>, Self::Error>;
}

Compare with production

The smaller version should now map onto these centers:

• WalkParallel and Stack for dynamic directory work;
• HaystackBuilder for application-level eligibility;
• SearchWorker for thread-local reusable state;
• Matcher, Searcher, and Sink for search composition;
• BufferWriter for visible output units; and
• atomics plus WalkState for completion and early shutdown.

Production ripgrep still supplies layered ignore precedence, Unicode-aware regex engines, mmap heuristics, encoding, multiline and context handling, binary detection, compressed files, several printers, platform behavior, and years of performance testing. Those are hardening around the same center—not the center itself.