Walker

Active contributors: sharkdp, tmccombs, tavianator

Purpose

The walker is fd's hot path. It enumerates filesystem entries from one or more root paths, applies the configured filters, batches surviving results, and either streams them to stdout or hands them to the command-execution subsystem. It also owns the Ctrl-C handler and the buffer-then-stream policy that keeps short searches sorted and long searches responsive.

Directory layout

src/
├── walk.rs        # WorkerState, ReceiverBuffer, Batch/BatchSender,
│                  # build_walker, build_overrides, spawn_senders, scan
└── dir_entry.rs   # DirEntry wrapper used throughout

The walker delegates the actual recursion to ignore::WalkParallel from the ignore crate.

Key abstractions

Type	File	Description
WorkerState	src/walk.rs	Holds patterns, Config, and the two Arc<AtomicBool> flags. The methods on it (scan, build_walker, spawn_senders, receive) are the entire walker.
Batch	src/walk.rs	Arc<Mutex<Option<Vec<WorkerResult>>>>. Multiple senders append into the same Vec between channel sends.
BatchSender	src/walk.rs	Per-thread wrapper around the Sender and current Batch. Decides when to flush.
WorkerResult	src/walk.rs	Entry(DirEntry) or Error(ignore::Error).
ReceiverBuffer	src/walk.rs	The state machine that buffers up to 1000 results or 100 ms, sorts, then streams.
ReceiverMode	src/walk.rs	Two states: Buffering and Streaming.
DirEntry	src/dir_entry.rs	Either a Normal(ignore::DirEntry) or BrokenSymlink(PathBuf). Lazy metadata + style.

Constants of note:

• MAX_BUFFER_LENGTH = 1000 — switch to streaming after this many buffered entries.
• DEFAULT_MAX_BUFFER_TIME = 100ms — also switches to streaming after this much wall time.
• Channel capacity = 2 * config.threads, set in WorkerState::scan.
• Batch limit = 0x100 (256), or 1 when running per-result --exec with multiple threads (so that Batches spread across exec workers).

How it works

sequenceDiagram
    participant Main as walk::scan
    participant Walker as ignore::WalkParallel
    participant Sender as Sender thread (per cpu)
    participant Channel as crossbeam-channel<br/>(bounded 2*threads)
    participant Receiver as ReceiverBuffer

    Main->>Main: build WalkParallel via build_walker()<br/>install ctrlc handler
    Main->>Walker: walker.run(|| sender_closure)
    par For each thread
        Walker->>Sender: traversed entry
        Sender->>Sender: skip root (depth==0),<br/>skip if quit_flag set,<br/>apply filter chain,<br/>style if printing
        Sender->>Channel: BatchSender.send(WorkerResult)
    end
    Receiver->>Channel: recv_deadline(deadline) /<br/>recv() in streaming mode
    Channel-->>Receiver: Batch
    Receiver->>Receiver: if Buffering and<br/>len > MAX_BUFFER_LENGTH<br/>→ stream(): sort, switch to Streaming
    Receiver->>Receiver: if Streaming → print directly
    Receiver-->>Main: ExitCode after disconnect / max_results / SIGINT

Setup

WorkerState::scan does five things:

1. Calls build_walker(paths) to produce the ignore::WalkParallel.
2. If colored output is on, registers a ctrlc handler. First Ctrl-C sets quit_flag; the second one calls ExitCode::KilledBySigint.exit() immediately.
3. Creates a bounded crossbeam-channel with capacity 2 * threads.
4. Inside thread::scope, spawns the receiver and runs spawn_senders on the calling thread.
5. After the senders finish and the receiver joins, returns KilledBySigint if the interrupt flag was set, or the exit code from the receiver.

build_walker

WorkerState::build_walker constructs an ignore::WalkBuilder configured to:

• hidden(config.ignore_hidden),
• respect .ignore, parent-directory ignores, and VCS ignores per the user's flags,
• require git for VCS handling unless --no-require-git was passed,
• add_custom_ignore_filename(".fdignore") when fdignore is enabled,
• read the global ignore file from ${etcetera::config_dir()}/fd/ignore if present,
• add any --ignore-file paths,
• register --exclude patterns via OverrideBuilder,
• follow_links(config.follow_links) and same_file_system(config.one_file_system),
• honour --max-depth,
• run with config.threads threads.

Additional search paths (paths[1..]) are added with builder.add(path); the first path is the builder's primary root.

spawn_senders filter chain

Inside the closure passed to WalkParallel::run, every entry passes through this chain:

1. Quit check. If quit_flag is set, return WalkState::Quit.
2. ignore_contain. If the entry is a directory and contains any of the configured marker files, skip the whole subtree (WalkState::Skip).
3. Skip the root. e.depth() == 0 → WalkState::Continue without emitting.
4. Broken-symlink rescue. If ignore reports Io(NotFound) for a path that symlink_metadata says is a symlink, wrap it as DirEntry::broken_symlink(path) instead of dropping it.
5. Other walk errors. Either dropped silently or forwarded as WorkerResult::Error depending on flow.
6. min_depth. Below the threshold → WalkState::Continue without emitting.
7. Pattern match. All conjuncted regexes (the main pattern + every --and) must match. The match input is the basename, or the full absolute path when --full-path is set (search_str_for_entry).
8. extensions RegexSet. Match against the basename.
9. FileTypes::should_ignore. Reject anything outside the requested types, plus the executables_only and empty_only gates.
10. Owner constraint (Unix only). Rejected if metadata cannot be read.
11. Size constraints. Skip non-files. For files, every SizeFilter must accept the metadata length.
12. Time constraints. Every TimeFilter must accept the modified time.
13. Style precomputation. If we are printing (no command set) and have LsColors, compute and cache the entry's Style here so the receiver does not have to.
14. Send. BatchSender::send(WorkerResult::Entry(entry)). If the channel is closed → WalkState::Quit.
15. Prune. With --prune, return WalkState::Skip so a matching directory is not descended into.

ReceiverBuffer

The receiver runs in Buffering mode initially:

• Calls rx.recv_deadline(deadline) so it stops blocking when the buffer-time deadline is hit.
• Each Entry goes into a local buffer. If buffer.len() > MAX_BUFFER_LENGTH, it switches to Streaming mode by sorting and flushing the buffer.
• Each Error is forwarded to stderr if --show-errors.
• After max_results entries → stop().
• In Streaming mode, every entry is written directly via output::print_entry. After draining a batch, it flushes if the channel is empty so users see progress.
• On a RecvTimeoutError::Timeout, switches to streaming.
• On Disconnected, calls stop() to print any remaining buffered entries.

Quiet mode and exit codes

When Config::quiet is true, the very first Entry returns Err(ExitCode::HasResults(true)), short-circuiting the walk. After the receiver is done, stop() returns HasResults(num_results > 0). ExitCode::HasResults(true) becomes process exit code 0; false becomes 1. This is how fd -q works as a "does it exist" predicate.

--exec integration

When Config::command is set, WorkerState::receive does not run the ReceiverBuffer. Instead:

• In batch mode, it calls exec::batch(rx.into_iter().flatten(), cmd, config).
• In one-by-one mode, it spawns config.threads worker threads inside a thread::scope, each running exec::job(rx.into_iter().flatten(), cmd, config). The ExitCodes are merged.

See command-execution for the consumer side.

Concurrency safety

• quit_flag and interrupt_flag are Arc<AtomicBool> shared between the senders, the receiver, and the Ctrl-C handler.
• The Batch mutex is short-lived: each send only holds it long enough to push a single entry. The IntoIterator impl on Batch take()s the inner Vec at the receiver, which is fine because by then no senders are touching it.
• The bounded channel provides backpressure: senders block when they get ahead of the receiver, which keeps memory usage proportional to the receiver's processing speed.

Entry points for modification

• To change the buffer policy, edit MAX_BUFFER_LENGTH and DEFAULT_MAX_BUFFER_TIME, or change the logic in ReceiverBuffer::recv/poll.
• To add a new walker-time filter, drop another check into the closure inside WorkerState::spawn_senders. Keep the cheapest checks first; expensive ones (size, time, owner) require metadata() and should stay later in the chain.
• To change how broken symlinks are reported, edit the Err(ignore::Error::WithPath { ... }) arm in spawn_senders.
• To support a new walk option, prefer extending ignore::WalkBuilder configuration in build_walker over rolling a custom mechanism.

Related pages

• Filters — the per-entry checks invoked here.
• Ignore rules — what WalkBuilder is configured with.
• Command execution — the alternate consumer of WorkerResult.
• Output — what ReceiverBuffer::print ultimately calls.