# @effected/walker Path traversal: upward (`Walker.ascend` / `ascendWithin` / `ascendToMarker` / `firstMatch` / `findUpward` / `findUpwardAll` / `findRoot` / `findUpwardWith`, plus `*Sync` twins including `findUpwardSyncWith`) and downward (`descend`, the public glob-file walker), and path containment (`confineRelative` lexical, `confineReal` physical), plus `PosixPath` (cwd-free POSIX path arithmetic for pure code). Sixth migration; the first package extracted from an already-merged sibling rather than ported from a `*-effect` repo. **Design doc:** `@./okf/modules/walker.md` ## Tier: boundary **Boundary tier**: `effect` and `@effected/glob` are the only peers and there are no runtime dependencies, but walker does IO. `FileSystem` and `Path` arrive through the `R` channel from `effect` core, so the consumer's platform layer is the single place POSIX-vs-win32 semantics are chosen. Requiring core services costs no dependency. The `@effected/glob` peer is mostly type-and-property — `descend` imports `GlobPattern` as a type and calls `matches()`. The one value import is `compileAndExpand` (in `Expand.ts`), which calls `GlobPattern.compileResult` and references `GlobPatternError`; the peer was already declared, so the dependency graph is unchanged. Walker needs **no platform package, even in tests** — core's `Path.layer` plus a real in-memory volume from `@effected/memfs` (a devDependency). Do not add `@effect/platform-node`, and do not hand-roll a `FileSystem.layerNoop` tree: `__test__/fixtures.ts` seeds files and symlinks into the volume, and injects the unreadable and vanished directories as `readDirectory` faults — and an unresolvable link as a `realPath` fault — that decline for every other path. The volume owns the parent-directory arithmetic and the symlink semantics `descend` reads, so neither is re-derived in the fixture. The upward suites in `Walker.test.ts` do the same: `findUpward`'s fixtures seed a volume via `MemoryFileSystem.layerWith`, and the denied probe is an `exists` fault on a candidate that is genuinely present — so disarming the fault moves the answer. `Walker` is a static class with a private constructor, not an `as const` namespace object — an `as const` object's member types are inferred in the built `.d.ts` and lose their TSDoc entirely, while a class's `static readonly` declarations keep it. Call syntax is unaffected (`Walker.ascend(...)`). ## The one absorbing loop `firstMatch` is the whole algorithm. `findRoot` is a genuine one-line specialization of it (`firstMatch(dirs, isRoot)` — the candidate expansion is the identity). `findUpward` first flattens each directory's candidates in **directory-major** order, then reuses the same loop. Three properties are load-bearing. Each has a test, and each test has been watched failing against a deliberately broken implementation: - **Absorption is per candidate.** A failing probe means "this candidate did not match", never "abort the scan". One `EACCES` ancestor must not hide a valid root above it. The corollary: not-found and cannot-look are deliberately **indistinguishable** to the caller. Discovery is best-effort, and a `None` may mean a directory was unreadable rather than empty. - **Defects propagate.** `firstMatch` uses `Effect.catch`, which catches failures and not defects. **Never** change it to `Effect.catchCause`. - **`firstMatch` short-circuits.** The scan stops at the first match; later candidates are never probed. A marker predicate can be expensive — `isWorkspaceRoot` reads and parses a `package.json` — so this is not just an optimization. Every upward error channel is `never` — including `ascend`'s, whose two caller-error guards (`maxDepth`, `stopAt`) are **defects**, not failures. The one typed error in the package is `descend`'s `DescendError` — see below. ## `descend` — the downward glob-file walker `descend(pattern, options)` expands a compiled `@effected/glob` `GlobPattern` under `options.cwd`, returning matching FILE paths relative to `cwd`, POSIX separators, sorted. The walker is **semantics-free**: dotfile behavior and every other matching option are carried by the compiled pattern the caller hands in — never re-derived here. - **A path is answered in the spelling it matched under**: `./src/*.ts` answers `./src/a.ts`, as it always has. Consumers re-filter the answer with a spelling-sensitive `matches` (`@effected/github-actions`' `CacheKey` does), so never canonicalize output. Internally the walk IS canonical. `enumerationRoots` prefixes are canonical, and each root carries its alternatives' `spellings` in pattern order. The machine reads each canonical directory once and answers a file ONCE, in the first spelling it matches under: the earliest alternative's. `{src,./src}/*.ts` reads `src` once and answers `src/index.ts` alone, and `./` never makes `cwd` look like a boundary. Unreadable and depth-exceeded paths are spelled through the root's own earliest spelling (`./**` reports its base as `.`). - A literal pattern (no magic, no braces, not negated) fast-paths to one stat; missing is zero matches. The stat and the answer are the compiled row glob matches (`enumerationPrefix` of a one-row literal is the whole row), never the source: an escape is undone (`src/\x/f.js` stats `src/x/f.js`), and at level 1 and up glob has popped `
/..` (`f.js/x/..` answers `f.js`, as
minimatch and node-glob read it), and an answer that does not match as
spelled is none. A `.`, `..` or empty segment the row keeps (level 0) is
resolved physically by `resolvesPhysically`: it must follow an `lstat`
Directory, never a file, a missing name or a link, because `join`
normalizes it lexically where the kernel fails ENOTDIR or ENOENT (#1283).
Without `followSymlinks` no directory such a path passes through may be a
link (`link/e/..` reaches `link` through it, #1290); under it a link may be
passed through, and a `.` or empty segment after one names its target
(`link/./*.js` answers `link/./d.js`), while a `..` after one is still
refused, since the kernel resolves it from the target. A magic root's
spellings pass the same check: a spelling that does not resolve
(`f.js/../` at level 0) answers nothing. Braces are magic here (glob's `hasMagic` ignores them). A magic
pattern walks each of `enumerationRoots` — one per brace alternative, each
with its own prefix and depth, so `packages/{a,b}/src/*.ts` reads only those
two directories; a **negated**
pattern walks from `cwd` itself (its matches can land outside the inner
pattern's prefix); a missing base directory is an **empty result**, not an
error. A pattern that lexically climbs above `cwd` via `..` segments is
zero matches, refused before any filesystem access — the walk never reads
outside its documented root lexically, and physically only while
`followSymlinks` is off (under it a link targeting outside `cwd` IS
descended, as `@actions/glob` follows links out of the tree).
- Only files match. A symlink counts when it stat-resolves to a file (`stat`
follows links, as node's does); a symlinked **directory is never descended**
by default (cycle safety, detected by an `lstat` kind check) — the walk
base and each directory on the way to it included: a base reached through a
link is an empty result, and so is a literal pattern reached through one —
unless
`followSymlinks: true` opts in — then links are entered under
`@actions/glob`'s per-branch `traversalChain` guard: each `DescendFrame`
carries its branch's ancestor real paths, and a directory is a cycle only
when its real path is already an ancestor of the branch it sits on. The
guard is per-branch, never walk-global — two sibling links to one target
BOTH enumerate (a global visited set silently dropped the second, and a
test pins that it does not). Only the base and each link pay a
`FileSystem.realPath`; a plain directory's real path is its parent's plus
its name. A link whose `realPath` fails is never entered, and the failure
goes through `onUnreadable` like a failed `readDirectory` (NotFound stays
the silent benign race). Dangling = no match either way.
- Unreadable directory mid-walk: `onUnreadable: "fail"` (default) fails typed
as `DescendError` — the OPPOSITE of the upward per-probe absorption, because
a swallowed subtree in a downward enumeration is silently missing
membership. `"skip"` absorbs and continues. `"record"` absorbs and resolves
to a `DescendResult { matches, unreadable }` instead of a bare array, where
each `UnreadableDirectory` is `{ path, cause }` — the absorbed
`readDirectory` (or, for a link under `followSymlinks`, `realPath`)
`PlatformError` travels with the entry, so a caller that
must report WHY never re-reads the directory. The walk base records as
`path: ""`. A NotFound mid-walk is a benign vanished-directory race and
reads as empty in every mode — it is never recorded.
- Depth past `maxDepth` (default 256) is a typed `depthExceeded` failure,
never a truncation; an invalid `maxDepth` is a **defect**, exactly
`ascend`'s guard.
- The descent is a worklist dequeued by head index (never `Array.shift()`),
and a pattern that cannot match below one level (`crossesSegments` false and
not negated) reads a single level and never descends.
- **The pattern bounds its own reads** (`internal/patternBounds.ts`, applied in
the machine before the `maxDepth` check). Without a globstar no directory
deeper than the source's separator count can reach is queued. Under
`dot: false` no hidden directory is queued unless a segment names one.
Glob exposes no `dot`, so a differential `matches` probe proves it.
Neither bound holds, and nor does the literal fast path, for a pattern
glob reports `matchesByBasename`: `matchBase` is on and some brace
alternative compiles to ONE path portion, which matches by basename at any
depth (`*.js` and `x/../*.js` match `b/d/f/g.js`, #1261; `**` matches
`.a/f.js`; `c.js` matches `b/c.js`). glob reads it off the compiled rows,
the test matching itself applies, so walker never re-derives it from the
source: a multi-portion pattern (`src/[ab]/*.ts`, `src/{a,b}*/*.ts`) keeps
its depth bound and a tight `maxDepth` under `matchBase`, and a bare `**`
without `matchBase` prunes hidden directories like any other.
`__test__/PatternBoundsSweep.test.ts` compiles every pattern of up to
three segments over a fixed alphabet and every option that rewrites rows,
pins that nothing pruned matches inside a hidden directory, and walks
94,528 compilations (braces, classes, extglobs and escapes included, under
`matchBase`, `dot` and every level) with `descendSync` over a memfs tree
against a brute-force `matches` filter, plus every bounded one again under
the tightest `maxDepth` its separators allow: zero differences. The
literal fast-path classes (a literal running past a file through `.`/`..`,
an escaped literal) are compared too: the filter resolves every spelling
physically against the tree, as the fast path and a magic root's
spellings do (#1283, #1290).
Extend its alphabet, never patch one spelling at a time. They skip
READS only, never a match, so the answer is unchanged. They are why a bounded
pattern never trips `maxDepth` or an unreadable directory it has no reason
to enter. Never make either bound "tighter" by guessing: an unmodelled
syntax answers "no bound". `__test__/DescendBounds.test.ts` counts reads
through both drivers.
- `prune` suppresses **directories only** — a FILE named `.git` (a submodule
or worktree gitlink) stays matchable.
## One walk, two drivers
The downward walk is ONE generator, `src/internal/descendMachine.ts`, yielding
filesystem requests (`Stat`, `Lstat`, `RealPath`, `ReadDirectory`).
`descend` / `descendEntries` (`Descend.ts`) answer them through core's
`FileSystem`; `descendSync` / `descendEntriesSync` (`DescendSync.ts`) answer
them from a caller-supplied `WalkerSyncFileSystem` (a `node:fs`-shaped port:
`readDirectory`, `stat`, `lstat`, `realPath`; `code: "ENOENT"` is the benign
race). Every rule lives in the machine — **never put one in a driver**; a
driver only maps its platform's answers and failures. Path joining is a
caller function, not a request. The sync forms are on the root entry (pure);
`@effected/walker/node-sync` binds them to Node (`nodeWalkerSyncOps`), and
`__test__/entrypoints.test.ts` pins that `.` never reaches it. Sync
record-mode causes are `unknown` (`UnreadableDirectory