ADR 0285 — Search bounds the work before reading

Serves I8, I10, I12, I13.

Decision

The workspace glob is one finite automaton for full-file matching and directory-prefix reachability. Its grammar is **, *, ?, literal punctuation and anchored UTF-16 matching. Directory prefixes that cannot lead to a match are excluded before host policy or opening; **/docs/** necessarily keeps arbitrary ancestors because a later descendant may be docs. There is no competing matcher and no recursive-regex backtracking in glob evaluation.

The existing descriptor-relative walker serves strict resource discovery and coding tools. Search consumes a file through a visitor before opening another, so total retained content is bounded by one file. Host authorization precedes every admitted path open; nofollow opens remain attached to pinned directory identities. The selected root capability is pinned before operation and path policies and retained across replacement of a configured alias or the root name itself. Excluded paths are outside the requested scope. Callback and cleanup failures propagate to error hooks; only failures at a filesystem operation become diagnostics naming that operation.

List, glob and search use the same coverage contract and finite directory-open, enumerated-entry, total-content-byte, file/depth/result, per-file-read, deadline and serialized-result budgets. Canonical spelling checks use that same budget and bounded enumeration; an incomplete check never claims a spelling is absent. List also caps raw entries at maxListEntries, before materialization; glob input is capped at 4,096 units. Linux enumerates through a descriptor path with a one-entry directory buffer; Darwin caps its native descriptor reader before materializing entries. Bounded entries are sorted after enumeration. No entry or match is read past its ceiling merely to establish that another exists: equality is conservatively partial. Content bytes consumed by failed decoding count against the same shared allowance; allocation and chunk reads stay within the remaining file and aggregate allowances.

The caller signal and deadline use the shared deadline/race primitives. CPU checkpoints detect expiry inside glob-state work and between bounded comparisons; asynchronous policy and I/O waits race cancellation. Directory readers check inside their enumeration loops before starting a new read and after the active read settles, so cancelling a wait also stops its producer. Late file/directory capabilities close when they arrive. An operating-system call already in flight may finish later; no user-space timer is described as interrupting the kernel.

Search regex keeps JavaScript RegExp syntax and semantics without flags. Each line is run by the native engine when its backtracking work stays within 2^24 steps: every start position walks each path through the alternatives once, and on a line of L units no repetition iterates more than L times beyond its required iterations — a body that can match empty still runs all of those, one that cannot never reaches more than L — so the unrolled pattern with repetition capped that way, paths × the longest path × L, bounds the line, measured once per power-of-two length. The engine may also enter, leave and save every group a step lies in — the enclosing groups and, inside a repeated body, every group of that body — so that bound is multiplied by the pattern’s number of groups plus one, which bounds both nesting depth and body width. An iteration that consumes nothing still costs a step, so nested repetition of an empty group is never a native line. Content matching yields to the event loop every 16 ms of CPU, so a caller’s abort arrives between lines of one file. An alternation of single units no two of which accept the same unit leaves one way forward per position and counts as one path, like the class it spells. The engine itself stops after 100,000,000 counted operations per call and then answers no match; one step of the model costs it about two, so 2^24 keeps a threefold margin and a native line never ends in a silent false. One uninterruptible native line therefore overshoots the deadline by a fraction of a second at most, and ordinary .* searches over code lines keep native speed. Every other line is run by a linear automaton rather than the backtracking engine: a deadline checked between lines cannot bound one uninterruptible backtracking match, and a denylist of constructs cannot make native matching linear.

Groups, alternation, classes, anchors, word boundaries and quantifiers compile into states; matching walks the line once through lazily cached deterministic transitions keyed by unit class, the cache is flushed past 4,096 states or 65,536 transitions; after two such flushes the state sets do not repeat (a counted gap after a frequent unit) and the matcher simulates the automaton directly, without interning. The deadline is checked inside that walk and during construction. Literals, single-unit escapes and bracket classes — escapes inside them included, \d/\w/\s read from the engine once — are exact unit ranges, each class checked against the engine at every range boundary and midpoint; under i literals and class members fold by ECMAScript Canonicalize, with every folded pair confirmed by the engine’s own case tables and a class negated after folding. One sort of the range endpoints splits the alphabet into segments, so thousands of such atoms cost their endpoints rather than atoms × units, and memberships past 4,194,304 refuse. Dot and class escapes outside a class are the same ranges ([^\n\r\u2028\u2029], [\s\S] under s, [\d] and so on). Only a class the engine check sends back stays a native one-character expression, evaluated once per distinct unit into a fixed bit set; more than 64 such classes refuse, so their work never exceeds 64 × 65,536 evaluations whatever family of syntax produces them. A unit class is a segment plus the native answers and the assertion kind. The restart of the unanchored search is one start closure per assertion context, kept outside the deterministic states, so a pattern that fans out to thousands of alternatives does not copy that fan-out into each state. Backreferences, lookaround, counted repetition above 1,000, automata above 16,384 states and constructions above 65,536 steps refuse before authorization or filesystem access.

coverage identifies scope, completeness, reasons and observed directory/entry/read-byte/time counters. Unreadable paths return only relative path, operation and safe code; host errors are not relabeled as symlinks. A complete empty result differs from zero reached files in a partial scan. The UTF-8 byte ceiling covers the complete JSON, including escaping, context and diagnostics; the minimum input-specific envelope is checked before I/O and all retained lists fit it. Diagnostic admission measures each retained item once; finalization checks the deadline even when there are no diagnostic items. Repeatedly serializing an entire shrinking list is not bounded work.

Verification

Mounted public coding-tool tests exercise pruning, each budget, cancellation, stalled host authorization, denied ancestors, real permission failures, UTF-8 rejection, output escaping and symlink substitution, for concrete roots and configured aliases and both policy callbacks. Discovery regressions include folded-name spelling checks, stalled policy cancellation and output bounds. Descriptor-backed read errors exercise the same walker separately. Differential tests compare the automaton with the established glob grammar and require viable ancestors of every matching path to remain reachable. Strict harness discovery still refuses symlinks and exhausted bounds.