tree-fucker

1Conventions

The key words MUST, MUST NOT, REQUIRED, SHALL, SHALL NOT, SHOULD, SHOULD NOT, RECOMMENDED, NOT RECOMMENDED, MAY, and OPTIONAL in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals.

Rust declarations in this document describe API shape and semantics. They are not a commitment to exact syntax where language limitations require a mechanically different representation.

2Terminology

Root

The filesystem path whose descendants form a tree.

Entry

A file, directory, symbolic link, or other filesystem object known to the tree.

Loaded directory

A directory whose immediate children are represented in the snapshot and whose policy state requires continued observation. Excluded and explicitly unloaded directories are not loaded.

Loading directory

A directory selected for loading whose complete current listing has not yet been accepted. Its immediate children are not represented.

Listing

A successful read of a directory's immediate children from the filesystem. A metadata read of the directory itself is not a listing.

Snapshot

An immutable, versioned representation of all known entries and directory load states.

Update

A transition from one snapshot version to another, accompanied by the changes that produced it.

Watcher

A platform or polling facility that reports possible filesystem changes. A watcher event is a hint that some paths should be read.

Reconciliation

Listing a directory and comparing the result with the current snapshot, independently of watcher events.

Baseline cursor

A persistent position in a stable ordering of loaded directories. Advancing the cursor gives every loaded directory finite access to reconciliation work.

Reconciliation round

A finite baseline traversal over an obligation set captured when the round begins. Each obligation receives exactly one designated round attempt. A round ends after every obligation reaches an Accepted, Unsatisfied, or Removed terminal state. It is successful when every remaining obligation is Accepted; otherwise it is degraded.

Obligation set

The EntryId and load generation of every directory that is loaded when a reconciliation round begins. A directory loaded later joins the next round. A directory removed, unloaded, or excluded before its attempt is removed from the current obligation set.

Accepted listing

A complete listing result that was normalized, validated against every applicable publication guard, and applied to the current snapshot. A valid empty diff is accepted. A failed, cancelled, stale, or discarded result is not accepted.

Designated round attempt

The one filesystem job assigned to satisfy a round obligation. A job originally dispatched for another reason can be designated when it is accepted before the baseline cursor reaches it or while it is in active state when the cursor arrives. Jobs and events accepted after the obligation becomes terminal do not reopen that obligation.

Causal barrier

A value from the coordinator-wide monotonically increasing sequence assigned when a command is accepted or a reconciliation round starts. Filesystem jobs receive dispatch generations from the same sequence. A job is post-barrier only when its dispatch generation is greater than the barrier.

Publication domain

The state one job may publish for its target: the target's binding and path, kind, configured metadata, load state, and the immediate-child projection a listing of that target reconciles. Each domain is versioned by a target-state generation. A directory's immediate-child name-to-EntryId mapping is versioned separately by its child-binding generation.

Root incarnation

One continuous period during which the configured root is available as the same observed directory. Each confirmed reappearance starts a new incarnation.

Priority directory

A loaded directory requested by a consumer for lower-latency reconciliation. Priority changes scheduling, not correctness.

Quiescent tree

A tree whose relevant filesystem state is no longer changing.

3Goals

tree-fucker has the following goals:

1. Maintain eventual agreement between loaded directory contents and the underlying filesystem without trusting watcher completeness.
2. Publish immutable snapshots and ordered, diffable updates.
3. Bound reconciliation work so large trees do not cause periodic full-tree pauses.
4. Keep watcher latency independent from reconciliation correctness.
5. Remain correct with coarse, future-dated, non-monotonic, or otherwise unreliable filesystem modification times. POSIX permits callers to set supported timestamps explicitly [POSIX-UTIMENS].
6. Support native recursive watchers, native non-recursive watchers, polling watchers, and operation without a watcher.
7. Make filesystem races, event loss, queue pressure, and I/O failure observable and testable.
8. Avoid dependence on a particular async runtime.

4Non-Goals

tree-fucker does not provide:

1. A transactional view of a filesystem that is changing while it is read. POSIX leaves the visibility of entries added or removed during directory iteration unspecified [POSIX-READDIR], and Rust exposes that platform iterator directly [RUST-READ-DIR].
2. Instantaneous convergence. Reconciliation is bounded and eventual.
3. File-content synchronization. The tree tracks paths, kinds, load state, and configured metadata. Consumers read and write contents.
4. Distributed replication, conflict resolution, or remote transport.
5. Filesystem journaling or recovery across process restarts.
6. A guarantee that every platform watcher reports every change. Linux, macOS, and Windows all document event-loss or rescan cases [INOTIFY] [FSEVENTS] [RDCW].
7. Stable identity across arbitrary delete-and-create or rename sequences. Identity preservation is best effort unless the filesystem supplies an unambiguous stable identifier.

5Consistency Contract

5.1Directory Guarantee

Every reconciliation round MUST reach a terminal outcome after each designated round attempt reaches a terminal outcome. Work admitted for other reasons does not extend the round. There is no wall-clock bound: filesystem calls can be arbitrarily slow or can fail to return, in which case progress requires adapter cancellation or termination.

In a successful round, every remaining obligation MUST have one accepted listing dispatched after that round's causal barrier. A stale, discarded, or uncommitted result does not satisfy an obligation.

A degraded round records its unsatisfied obligations, schedules them for retry, publishes degraded health, and ends. The next round starts normally so one persistently failing directory cannot prevent healthy directories from receiving continued baseline coverage.

A watcher event, directory modification time, inode, file identifier, cached child count, or previous listing result MUST NOT be used to avoid this required listing.

A publication-valid accepted listing dispatched after the round barrier for another reason MUST satisfy a still-Pending obligation when it targets the same EntryId and load generation and carries the active round's reconciliation generation. The implementation MUST track this by reconciliation and dispatch generation, not by filesystem time.

5.2Eventual Convergence

If all of the following remain true:

1. the relevant filesystem subtree becomes quiescent;
2. filesystem operations eventually succeed;
3. the coordinator and workers continue to make progress;
4. the applicable paths remain loaded;
5. the represented tree remains within configured entry limits; and
6. no fatal tree error occurs,

then the snapshot MUST eventually agree with successful filesystem listings for those paths.

Newly discovered directories can require additional listings. The convergence bound is therefore expressed in completed work, not wall time.

5.3Watcher Independence

Suppressing any finite or infinite subset of watcher events MUST NOT invalidate the directory guarantee.

A working watcher SHOULD cause affected paths to converge before the baseline cursor reaches them. Without one, a state that remains present after the tree becomes quiescent is detected by the first accepted listing dispatched afterward for its containing directory. No wall-clock bound is implied.

5.4Metadata

Modification time, creation time, size, permissions, inode, file ID, and similar values are metadata. They MAY be stored, diffed, and published.

Metadata MUST NOT be treated as proof of directory contents. In particular, equality of modification times MUST NOT suppress a required directory listing.

Timestamp equality is known to classify changed state as unchanged when multiple observations fall within one filesystem clock period [RACY-GIT]. This demonstrates why timestamp equality alone cannot serve as a general unchanged-state proof.

5.5Failure Qualification

A reconciliation round containing an unsatisfied obligation is degraded. The implementation MUST report the failed paths and retain retry work. It MUST NOT claim that the round was successful.

6Architecture

The system consists of six logical components:

Coordinator

Owns mutable synchronization state. It receives commands, watcher hints, timer notifications, and completed filesystem jobs. It is the only component allowed to publish a new snapshot.

Snapshot store

Holds the current immutable snapshot and its monotonically increasing version.

Watcher adapter

Converts backend-specific events into normalized hints. It can be absent or degraded without disabling reconciliation.

Reconciliation scheduler

Maintains round obligations, cursors, retry work, request barriers, and admission budgets for every directory-listing reason.

Filesystem workers

Perform bounded metadata and directory-listing jobs. Workers do not mutate snapshots.

Update stream

Publishes committed snapshot transitions, lifecycle state, and recoverable errors to consumers.

Mutable state MUST have one logical writer. Filesystem reads MAY run concurrently, but their results MUST be validated and serialized by the coordinator before publication.

All snapshot-producing filesystem jobs MUST pass through one admission scheduler. The scheduler has baseline, control, refresh, watcher, priority, and retry classes. Initial scan, load, policy invalidation, and root recovery use the control class. Overflow creates future baseline obligations rather than a separate class.

At the beginning of each dispatch cycle, the scheduler computes class reservations from jobs that are ready at that instant. A class with fewer ready jobs than its reservation releases the unused slots for that cycle. Only released slots can be borrowed. Jobs arriving after admission begins wait for the next cycle.

Jobs with multiple reasons are attributed in this order:

1. baseline, when designated for a round obligation;
2. control;
3. refresh;
4. watcher;
5. retry; and
6. priority.

Attribution controls admission accounting only. Every attached command barrier and scheduling reason remains on the coalesced job.

7Data Model

7.1Entry

An entry contains at least:

• EntryId
• normalized relative path
• entry kind
• directory load state, where applicable
• configured metadata
• optional filesystem identity

EntryId values are scoped to one tree instance and MUST NOT be reused during that instance's lifetime.

Implementations MAY retain an EntryId across a rename when identity is unambiguous. Consumers MUST tolerate a rename represented as removal plus addition with a new EntryId.

A filesystem adapter can advertise stable rename identity. Only then MAY an update contain an atomic rename change that preserves EntryId. Without that capability, rename is represented as removal and addition.

7.2Directory Load State

A directory is in exactly one of these states:

Unloaded

The directory entry is known, but its children are not represented and it does not participate in reconciliation.

Loading

The directory is selected or explicitly requested for loading, but no complete listing has been accepted for its current load generation. Its immediate children are not represented. It receives control and retry work but does not participate in reconciliation.

Loaded

Its immediate children are represented and it participates in every reconciliation round.

Excluded

The directory entry remains represented, but policy excludes its descendants. It does not participate in reconciliation.

The first accepted listing for a Loading directory MUST atomically install its immediate children and transition it to Loaded. A retryable failure defined in Section 13.1 leaves it Loading. Other outcomes follow Section 13. Removal, unload, or exclusion MUST invalidate its work and remove it or transition it to Unloaded or Excluded.

A directory MUST be in exactly one load state. Loading and Unloaded directories MUST NOT have represented immediate children.

7.3Snapshot

A snapshot is immutable after publication. It provides lookup by path and EntryId, ordered traversal, child traversal, and its version.

Applying a listing MUST produce either one complete new snapshot or no snapshot. Consumers MUST NOT observe partially applied directory changes.

7.4Update

A delta update contains:

• previous snapshot version
• new snapshot version
• new snapshot handle
• ordered path changes
• health state
• recoverable errors assigned to this publication event

Path changes distinguish addition, removal, atomic rename, metadata change, kind change, and load-state change. A Rename carries EntryId, old path, and new path. A directory Rename atomically rebases every represented descendant, and every moved binding advances its entry generation.

Rename MUST be emitted only when accepted listings of every affected parent establish the move and the adapter supplies unambiguous stable identity. A watcher hint alone MUST NOT emit Rename. Otherwise the move is a removal followed by an addition.

Path changes describe the net difference between the named previous and new snapshots and form one indivisible transaction. Their canonical order is:

1. removals, deepest path first;
2. renames, interpreted as one simultaneous phase;
3. kind changes;
4. load-state changes;
5. additions, shallowest path first; and
6. metadata changes.

Removals use previous-snapshot path order. Renames use old path and then new path. Kind, load-state, addition, and metadata changes use new-snapshot path order. EntryId is the final tie-breaker. Consumers MUST NOT expose intermediate transaction states.

Update order MUST match snapshot version order. Health state consists of orthogonal initial-scan, root-availability, watcher-health, reconciliation-health, and shutdown fields. An implementation MUST NOT collapse these independent conditions into one mutually exclusive state.

Root availability is Available with a root-incarnation generation, or Unavailable with the last incarnation generation. Initial-scan state is Running, Degraded with failed paths, Complete, or Unavailable. Running, Degraded, and Complete identify the root incarnation to which they apply. A degraded initial scan MAY become Complete after background retries accept every required initial listing.

A reset update contains a complete snapshot and health state. It MAY replace queued Delta and Health events for a slow consumer. Applying either all delivered deltas, or a Reset followed by every subsequently delivered Delta, MUST produce the snapshot version named by the last applied event.

A Reset supersedes a Delta only when the Delta's new version is at most the Reset version. It supersedes a Health event only when the Health event's current snapshot version is at most the Reset version and the Reset preserves the newest health and every undelivered error or an explicit truncated-error count. It MUST NOT supersede Terminal or an event for a later snapshot version.

8Path and Scan Policy

Policy determines whether an entry is excluded, unloaded, or loaded. Policy can depend on path, kind, depth, revisioned parent context, and consumer-owned state.

The policy interface MUST be able to derive child context from parent context and directory entries. Every evaluation carries a policy revision. A stateless path predicate MAY implement policies that do not require traversal context.

The logical policy operations are:

revision() -> PolicyRevision
root_context(root_metadata) -> PolicyContext
classify(parent_context, path, metadata) -> ScanDecision
child_context(parent_context, directory_listing) -> PolicyContext

ScanDecision is Excluded or Eligible with an initially_loaded flag. PolicyContext is an opaque, revisioned value owned by the policy implementation. A changed child context increments the affected policy-context generation.

Excluded takes precedence over every explicit load request. For an Eligible directory, load and unload install a path-scoped override of initially_loaded. The override persists across policy revisions while the path remains Eligible and refers to the same EntryId. It is removed when the entry is removed or becomes Excluded. A newly Eligible entry starts from initially_loaded.

A policy change increments the policy revision and MUST identify the roots whose decisions may have changed. Those roots are invalidated and reevaluated. Listings dispatched under an older relevant revision MUST NOT commit after invalidation.

Invalidation MUST immediately install a revision fence over each named root and every represented descendant. Results captured before the fence MUST NOT commit within that scope. The coordinator MUST then reevaluate the represented subtree in parent-before-child order. When inherited context changes, it MUST increment the affected context generation and recursively enqueue represented descendants. Rejecting old jobs alone is not reevaluation.

Unloaded and Excluded directories themselves are reevaluated, but policy invalidation MUST NOT invent unrepresented descendants. A transition that requires loading enters Loading; its listing uses the control class and normal admission bounds. Policy traversal does not satisfy a baseline obligation unless it produces an otherwise eligible accepted listing.

Any accepted read that changes a policy input, including path, depth, kind, configured metadata, or derived parent context, MUST invoke the same fencing and reevaluation procedure even without an explicit policy invalidation command. The directly changed entry MUST be reclassified in the committing transaction. Every affected represented descendant is then reevaluated parent before child under the installed fence.

Excluded, Unloaded, and Loading directories do not participate in baseline reconciliation. A directory entering Loaded after a round begins joins the next round. Unloading it removes its current obligation and pending work.

9Public Interface

The logical public interface is:

pub struct Tree { .. }
pub struct TreeHandle { .. }
pub struct Snapshot { .. }
pub struct Update { .. }
pub struct Config { .. }

impl Tree {
    pub async fn open(
        filesystem: Arc<dyn FileSystem>,
        root: PathBuf,
        policy: Arc<dyn ScanPolicy>,
        config: Config,
    ) -> Result<(TreeHandle, UpdateStream)>;
}

impl TreeHandle {
    pub fn snapshot(&self) -> Snapshot;
    pub async fn initial_scan_complete(&self) -> Result<()>;
    pub async fn refresh(&self, paths: Vec<RelativePath>)
        -> Result<()>;
    pub async fn load(&self, path: RelativePath) -> Result<()>;
    pub async fn unload(&self, path: RelativePath) -> Result<()>;
    pub async fn invalidate_policy(
        &self,
        roots: Vec<RelativePath>,
    ) -> Result<()>;
    pub async fn set_priority(
        &self,
        paths: impl IntoIterator<Item = RelativePath>,
    ) -> Result<()>;
    pub async fn shutdown(&self) -> Result<()>;
}

A command is accepted only after the coordinator assigns it a causal barrier. If command capacity is exhausted, the command fails before acceptance. Dropping a caller-side future does not cancel an accepted command.

Commands and job dispatches allocate values from the sequence defined in Section 2. A read satisfies barrier B only when its dispatch generation is greater than B. A pre-barrier job MAY commit when every publication guard remains valid, but it MUST NOT satisfy the command. Coalescing MUST retain a required post-barrier successor read.

A causal barrier orders only actions observed by the coordinator. It does not make filesystem operations linearizable and does not wait for unrelated earlier jobs.

initial_scan_complete succeeds when initial traversal is exhausted and every initial obligation is Accepted or Removed. It fails with the set of degraded paths when traversal is exhausted and every obligation is terminal but at least one is Unsatisfied. Background retries continue after this failure and can move initial-scan health from Degraded through Running to Complete. The call binds to the root incarnation active when invoked. Root loss fails its waiters with RootUnavailable; callers invoke it again for a recovered incarnation.

refresh succeeds after each target has an accepted read dispatched no earlier than its barrier. An already in-flight read dispatched before the barrier does not satisfy the command. A not-found result is an accepted refresh result when it commits the corresponding removal or a post-barrier parent listing proves that an unrepresented target is absent.

load transitions an Unloaded target to Loading and succeeds after the named directory enters Loaded state through an accepted post-barrier listing. A target already Loading or Loaded still requires an accepted post-barrier listing. Descendants selected for loading by policy continue as ordinary scan work unless the API explicitly requests recursive completion.

unload succeeds after represented descendants are removed, pending work is cancelled, and in-flight results are invalidated. It does not require filesystem I/O.

invalidate_policy succeeds after affected entries are reevaluated and all resulting load, unload, and exclusion transitions are committed. Every directory newly selected for loading creates a policy-listing obligation before completion.

Required policy-listing obligations are keyed by EntryId and load generation and have Pending, Accepted, Removed, or Unsatisfied states. Removal, unload, exclusion, or kind change resolves an obligation as Removed. The command succeeds when reevaluation is complete and every obligation is Accepted or Removed. A terminal required-read failure makes its obligation Unsatisfied and fails the command under the error rules below. A stale or discarded result leaves it Pending and queues a successor.

set_priority succeeds after the coordinator replaces the priority set. It does not wait for a listing or create a snapshot version.

A command that requires no state change completes through an explicit acknowledgement; it need not create a snapshot version.

shutdown stops command acceptance, invalidates in-flight work, requests backend cancellation, publishes terminal health, and closes the update stream. It does not wait for blocked filesystem calls. Calls made after shutdown begins fail with a shutdown error.

For refresh, load, and invalidate_policy, a required read that reaches Transient, PermissionDenied, Unsupported, or Fatal failure completes the command with that error; background recovery follows Section 13. A stale result is rescheduled and does not complete the command. There is no wall-clock completion bound while the target keeps changing.

Concurrent removal has these command effects:

refresh

succeeds when the removal is committed;

load

fails with NotFound;

unload

succeeds as a no-op; and

invalidate_policy

succeeds for the removed portion after committing all remaining affected transitions.

Other terminal conditions have these command effects:

configured entry limit exceeded

the command fails with LimitExceeded;

root NotFound or non-directory

root lifecycle rules in Section 13.2 override this table;

load of an Excluded directory

the command fails with PolicyDenied;

load of a non-directory

the command fails with NotDirectory;

pending load whose target becomes Excluded

the command fails with PolicyDenied;

pending unload whose target ceases to be a loaded directory

the command succeeds because its requested terminal state holds;

kind change during refresh

the command succeeds after the new kind and metadata commit; and

fatal tree termination

every unfinished command fails with TreeTerminated.

Shutdown completes every other accepted but unfinished command with a shutdown error.

Snapshot reads MUST be non-blocking with respect to filesystem I/O.

UpdateStream yields Result<UpdateEvent, StreamError>, where UpdateEvent is Delta, Reset, Health, or Terminal. Delta carries one snapshot transition. Reset carries the latest complete snapshot, current health, and all recoverable errors not previously delivered, or an explicit truncated-error count. Health carries the current snapshot version, current health, and recoverable errors not attached to a Delta or Reset. A recoverable error that changes neither snapshot nor health MUST produce a Health event; its health value MAY equal the previous event's value. Terminal carries final health and is the last item before orderly stream closure.

The update stream is bounded. When a consumer falls behind, the implementation MUST replace undelivered deltas with a Reset event or disconnect that consumer with an explicit Lagged error. It MUST NOT grow memory without bound or silently omit state. Fatal tree termination publishes Terminal before closure unless the consumer was already disconnected for lag.

Undelivered Health events MAY be coalesced only when the replacement Health or Reset preserves every undelivered error or carries an explicit count of truncated errors.

The core is runtime-neutral. Runtime integration is supplied by an adapter that provides task spawning, timers, cancellation, and a monotonic clock. The state machine and scheduler MUST run under a deterministic adapter in tests.

9.1Command Target Resolution

Command paths are normalized before acceptance. Target resolution has the following semantics:

refresh

A represented Loaded or Loading directory receives a listing. A represented Unloaded or Excluded directory receives only a metadata read. Refresh MUST NOT by itself request loading or traverse descendants. Removal, kind change, and policy or load-state consequences required by accepted metadata MUST still commit. A represented non-directory receives a metadata read.

• An unrepresented target is resolved from its deepest represented
• Loaded or Loading ancestor by post-barrier parent listings, one path
• component at a time. A listing that proves a component absent is an
• accepted refresh result even when no snapshot version changes. The
• walk MUST stop rather than cross an Unloaded, Excluded, or
• non-directory component, returning NotLoaded, PolicyDenied, or
• NotDirectory respectively.

load

The exact target MUST already be represented as a directory. Unloaded transitions to Loading. Loading and Loaded retain their state while a post-barrier listing is scheduled. Excluded fails with PolicyDenied, a non-directory fails with NotDirectory, and an unrepresented target fails with NotFound. The command MUST NOT probe ancestors or bypass policy.

unload

Loaded or Loading transitions to Unloaded, cancels pending work, and removes represented descendants. Unloaded or Excluded succeeds as a no-op. An unrepresented target also succeeds as a no-op but MUST NOT install an override. A represented non-directory fails with NotDirectory.

invalidate_policy

Every represented target root, including one that is Unloaded or Excluded, is reevaluated under Section 8. An unrepresented root affects no current entry and succeeds as a no-op; later discoveries use the new policy revision.

set_priority

Normalized paths are stored regardless of current representation. Only matching Loaded directories enter the priority cursor. Other paths remain dormant and cause no filesystem I/O.

While the root is unavailable, refresh of the root invokes the recovery procedure in Section 13.2 and every other root-dependent command fails with RootUnavailable. set_priority, snapshot, and shutdown retain their stated behavior. These root rules override no-op and concurrent-removal behavior elsewhere in this section.

9.2Configuration Defaults

A conforming implementation provides these defaults:

• batch size 64
• maximum in-flight jobs 8
• pending command capacity 1024
• paths per command limit 65536
• priority-set path limit 65536
• update-stream capacity 256
• coalesced watcher-path limit 65536
• entries per directory limit 1000000
• represented entry limit 10000000
• transient degrade threshold 3 consecutive failures
• retry maximum delay 5 minutes
• watch registration failure ReconcileOnly
• root reappearance monitoring enabled

All numeric limits and listed modes are configurable. Reducing a limit below current use fails without changing active state. Reaching an entry limit aborts the listing, leaves the previous snapshot intact, marks the path degraded, and prevents that listing from satisfying a round or command.

A command exceeding its path limit MUST fail before acceptance. A set_priority call exceeding the priority-set path limit MUST fail without replacing the existing priority set.

open MUST reject InvalidConfig before creating tree state unless all of these conditions hold:

• batch_size is at least 2
• maximum_in_flight is greater than zero
• target_duty_cycle is finite and greater than zero and at most 1
• minimum_period is greater than zero and at most maximum_period
• retry_maximum_delay is at least minimum_period
• any configured fixed interval is greater than zero
• every expedited class weight is greater than zero
• baseline_share is finite, at least zero, and less than 1

Root reappearance polling and retries use exponential backoff from the minimum reconciliation period to the configured maximum delay.

10Filesystem Abstraction

The filesystem interface supplies, at minimum:

• root and path canonicalization
• entry metadata
• directory listing
• watcher registration and removal
• normalized watcher event streams
• filesystem case-sensitivity behavior

The abstraction SHOULD separate directory listing from metadata reads so tests and implementations can observe which operation establishes correctness.

Configuration defines which metadata participates in snapshot convergence. A baseline listing MUST refresh every configured metadata field for the directory itself and the names, kinds, and configured metadata of each immediate child. The adapter MAY return these values with read_dir or through batched metadata reads. File contents are never part of a listing.

Test implementations MUST be able to:

• configure recursive and non-recursive watch behavior
• drop selected watcher events
• emit overflow or rescan notifications
• pause and resume event delivery
• mutate directory contents without changing mtime
• return future-dated or decreasing mtimes
• fail individual metadata or listing operations
• control watch-registration timing

11Synchronization Algorithm

11.1Initial Scan

The initial scan starts at the root and applies scan policy while traversing descendants.

When a watcher is configured, its registration attempt MUST complete before the corresponding listing is dispatched. This applies to each Loading directory for a per-directory backend and to the root before its first listing for a recursive backend. The initial root registration attempt MUST complete before open publishes its handle.

Successful registration uses this ordering to close the listing-before-watch gap:

• establish watch
• list directory
• apply listing

Apple prescribes starting monitoring successfully before constructing a directory hierarchy snapshot, and recommends relisting directories changed during the scan rather than comparing event and filesystem timestamps [FSEVENTS]. Linux documents the equivalent gap when recursively adding inotify watches [INOTIFY].

A change before the listing appears in the listing. A change after the listing should appear as a watcher hint and, even if it does not, is found by reconciliation.

watch_registration_failure_mode is either ReconcileOnly or RequireWatcher and defaults to ReconcileOnly. On registration success, registration precedes listing. On failure, ReconcileOnly MUST publish degraded watcher health and schedule the listing without a watch under normal admission rules. RequireWatcher MUST NOT dispatch the corresponding listing.

A RequireWatcher failure before handle publication fails open. Later, a required listing blocked by RequireWatcher reaches a WatcherRegistrationFailed terminal outcome. It fails every refresh, load, or invalidate_policy command waiting on that listing, records the path as a failed initial-scan outcome when applicable, leaves the directory Loading, and retries registration under the common retry and admission rules. Loss of an established watcher follows Section 13.4.

Initial-scan obligations are keyed by EntryId and load generation and have Pending, Accepted, Removed, or Unsatisfied states. Only traversal work carrying the initial-scan reason creates these obligations. An accepted first listing resolves one as Accepted. Any retryable terminal failure of a Pending obligation resolves it as Unsatisfied. The first such transition records the foreground outcome; later transitions retain the initial-scan recovery reason. A stale or discarded result leaves it Pending and MUST be rescheduled. Removal, unload, exclusion, or kind change resolves it as Removed.

The foreground initial scan ends when traversal is exhausted and every initial obligation is terminal. Accepted and Removed are non-failing. If any obligation is Unsatisfied, initial-scan health becomes Degraded and waiters fail with those paths; otherwise it becomes Complete.

Background retries for an Unsatisfied path retain an initial-scan recovery reason. Admission returns that obligation to Pending. The reason propagates to every child directory selected by the accepted listing, creating new Pending obligations. During recovery, health is Degraded while any obligation is Unsatisfied, Running while traversal or a Pending obligation remains and none is Unsatisfied, and Complete only after traversal is exhausted with every obligation Accepted or Removed. A waiter already completed or failed MUST remain settled.

11.2Watcher Hints

Watcher events are normalized to affected paths and parent directories. Create, remove, and rename hints schedule parent listings. Metadata or content hints schedule the minimum reads needed to update configured metadata.

Backends can coalesce events, report only a containing path, or split a rename into multiple records [INOTIFY] [FSEVENTS]. Normalization MUST therefore preserve uncertainty rather than inventing precision.

Multiple pending hints for the same directory MUST be coalesced.

Each represented metadata or listing target has a monotonically increasing change epoch. Accepting a watcher hint increments every affected target's epoch. A job captures its target's epoch at dispatch. If a newer epoch exists when the job completes, its result is stale: it MUST NOT satisfy a command or round obligation, and the target MUST be queued again when a read remains required. A stale result MUST NOT commit.

An accepted refresh, or a load that requires a read, is an explicit invalidation. After resolving each actual read target and before dispatch, the coordinator MUST increment that target's change epoch. Policy invalidation uses policy generations instead. Overflow and watcher restart use reconciliation coverage generations.

11.3Reconciliation Scheduling

The scheduler admits at most batch_size new snapshot-producing filesystem jobs per dispatch cycle. Watcher hints can request an immediate cycle; the timer requests one when periodic baseline work is due. batch_size MUST be at least 2, defaults to 64, and is configurable.

A dispatch cycle freezes at most batch_size ready jobs after applying class reservations. Those jobs form a closed batch. Workers execute the batch subject to the maximum in-flight limit. The coordinator MAY keep accepting and coalescing inputs, but MUST NOT admit another snapshot-producing job until every batch member is Accepted, failed, stale or discarded, or cancelled. Newly ready work joins the next cycle.

Admission into a closed batch is the dispatch point for causal barriers and generation capture, even when a job waits for a worker. An admitted waiting job is queued, not in flight. Before filesystem I/O starts, a batch member whose publication guard is stale MUST be cancelled without performing I/O.

Every listing reason enters one of the weighted fair classes defined in Section 6. The scheduler divides capacity between:

baseline work, which advances the round cursor; and
expedited work from control, refresh, watcher, retry, and priority
sources.

When baseline and expedited work are both ready, the baseline reservation is:

clamp(floor(batch_size * baseline_share), 1, batch_size - 1)

The default baseline share is one half. When only one group is ready, it can use every admission slot. No expedited source may bypass admission or occupy baseline-reserved admission slots.

Capacity released during admission as specified in Section 6 MAY be borrowed. Weighted rotation among expedited classes MUST give every continuously pending class finite service.

The default expedited class weights are:

• control 4
• refresh 4
• watcher 2
• retry 1
• priority 2

Priority directories use an independent rotating cursor. A priority set larger than its share MUST receive fair service across dispatch cycles.

A directory listed successfully for control, watcher, explicit refresh, retry, or priority work during the current round can satisfy its baseline obligation. The baseline cursor still advances past it and records that the directory was covered in that round.

11.4Filesystem Jobs

A job is active from closed-batch admission through its terminal state, including time queued for a worker. The scheduler MUST NOT keep more than one snapshot-producing job active for an EntryId. Directory listings, file metadata reads, and directory metadata reads all obey this rule. Requests for the same entry are coalesced into the active job or queued behind it.

Every job for a represented entry captures:

• relative path
• EntryId
• root-incarnation generation
• entry generation
• load generation
• policy revision
• policy-context generation
• target-state generation
• containing-directory child-binding generation
• change epoch
• dispatch generation
• reconciliation generation
• scheduling reason

Generations change as follows:

root-incarnation generation

changes whenever a missing root is confirmed to have reappeared;

entry generation

changes when the path-to-EntryId binding or entry kind changes, including for every binding moved by a directory rename;

load generation

changes on every transition among Loading, Loaded, Unloaded, and Excluded;

policy revision

changes when the consumer invalidates policy;

policy-context generation

changes when derived context affecting the entry changes;

target-state generation

belongs to an entry and versions its publication domain: its binding and path, kind, configured metadata, load state, and the immediate-child projection a listing of it reconciles. It MUST advance atomically whenever any of these change, including when a committed update changes the path, kind, configured metadata, or load state of an immediate child;

child-binding generation

belongs to a directory and versions its immediate-child name-to-EntryId mapping. It MUST advance on addition, removal, replacement, or rename of an immediate child. A change only to an existing child's metadata, kind, load state, or descendants MUST NOT advance it;

change epoch

changes for every accepted watcher hint or explicit invalidation;

dispatch generation

is allocated from the coordinator sequence at admission and stored as the latest dispatch generation for its actual read target; and

reconciliation generation

is allocated whenever a round begins. Overflow or watcher restart allocates a newer minimum generation for subsequent coverage without changing an active round's generation.

Root-incarnation, entry, and dispatch generations are publication guards for every job. Load generation also guards directory jobs. Policy revision and policy-context generation guard a job whenever its result can classify an entry or derive policy context. Change epoch guards the actual metadata or listing target. A dispatch generation becomes stale only when a later job for that target is dispatched or the target is invalidated; unrelated coordinator sequence values do not stale it. A later dispatch for a sibling never stales a job.

Every represented-entry job MUST capture its target's target-state generation. A non-root job MUST also capture its containing directory's child-binding generation. A result spanning multiple publication domains MUST guard every such domain. An atomic rename MUST guard both affected parents and advance the target-state generation of every moved binding. Validation, snapshot application, and generation advancement MUST be atomic. An accepted result MUST be applied against the coordinator's current snapshot; it MUST NOT replace that snapshot with a dispatch-time snapshot.

A sibling's commit therefore does not stale a job. A change to sibling B advances B's target-state generation and the parent's target-state generation, neither of which a job for sibling A captures. A parent listing in flight is staled instead, which prevents an older parent read from overwriting a newer child publication. A commit that adds, removes, replaces, or renames an immediate child advances the parent's child-binding generation and stales every in-flight job for that directory's children.

A completed result with any stale applicable publication guard MUST be discarded in full. The current path is queued again when its state still requires the read.

Publication guards apply to non-Fatal outcomes. Once a Fatal completion is correlated with an admitted job, it MUST be handled before publication-guard validation. It MUST publish terminal health and terminate the tree even when the job's publication guards are stale. No snapshot payload from that result may commit.

Reconciliation generation is a coverage tag, not a publication guard. A mismatch MUST NOT by itself prevent an otherwise current result from committing. It prevents that result from satisfying a round, overflow, or watcher-restart coverage requirement for a newer generation.

This validation prevents a slow read from resurrecting or regressing an entry that was changed, replaced, unloaded, excluded, or reevaluated while I/O was in progress.

A root-recovery probe has no EntryId. It captures the last root-incarnation generation, the expected Unavailable state, and a dispatch generation. Its result MUST be discarded unless all three still match when it completes.

11.5Applying a Listing

A successful listing is normalized and compared with the current immediate children in the snapshot.

A metadata read is accepted only after the same generation validation. Its configured fields are applied atomically to the current entry. An accepted read can produce an empty diff.

The resulting transaction can:

• add newly observed entries
• remove absent entries and represented descendants
• preserve stable identity through an atomic rename
• change entry kind or metadata
• transition a Loading directory to Loaded
• schedule child directories selected for loading
• cancel jobs for removed or unloaded directories

The transaction is committed atomically as one new snapshot version. An empty structural diff can still publish metadata or health changes.

Directory enumeration is not assumed to be atomic. POSIX explicitly leaves concurrent addition and removal visibility unspecified [POSIX-READDIR]. If the directory changes during enumeration, watcher hints or the next reconciliation round repair any mixed result after the directory becomes quiescent.

11.6Overflow and Backend Rescan Requests

When a watcher reports overflow, journal invalidation, or a rescan requirement, the implementation MUST stop treating preceding event order as complete.

IN_Q_OVERFLOW, FSEvents dropped-event flags, and a zero-byte or ERROR_NOTIFY_ENUM_DIR Windows result all require cache reconstruction or directory enumeration [INOTIFY] [FSEVENTS] [RDCW]. The notify crate exposes the same condition as Flag::Rescan [NOTIFY].

Overflow records a minimum reconciliation generation for a subsequent round for every loaded directory. It MUST NOT change the active round's generation, reset its baseline cursor, or discard its progress. Existing work MAY commit when publication-valid but cannot discharge the newer requirement. Repeated overflow notifications coalesce into the newest required generation.

Implementations MAY accelerate this work by assigning greater baseline weight, but MUST preserve configured admission and concurrency bounds.

11.7Explicit Refresh

refresh(paths) schedules immediate reads under the target-resolution rules in Section 9.1. It does not remove a baseline-round obligation unless an eligible accepted listing carries the active round generation.

Overlapping refresh requests MUST be coalesced. Every caller MUST still receive completion or failure for its request.

11.8Round Transitions

Round state changes according to the following rules:

Start

Freeze the current loaded EntryId and load-generation pairs as the obligation set. Allocate the round's causal barrier and reconciliation generation, then set every obligation to Pending. No later load, event, retry, or policy change adds an obligation to this round. Every post-barrier listing dispatched for a Pending obligation carries the active round generation regardless of its original scheduling reason.

Pre-cursor acceptance

If an accepted listing is post-barrier, carries the active round generation, and matches a Pending obligation's EntryId and load generation, atomically designate that completed job and set the obligation to Accepted. The cursor later skips that terminal obligation. A failed, stale, or cancelled job that was not designated leaves the obligation Pending.

Designation

When the baseline cursor reaches a Pending obligation, designate a matching post-barrier active job, whether queued or executing, or admit and designate one new round job. Set the obligation to Designated. A pre-barrier active job cannot be designated. In that case, coalescing MUST reserve a post-barrier successor; the cursor may advance, but the obligation remains Pending. The first such successor MUST be designated atomically when admitted, even after the cursor has advanced.

Accepted outcome

Set the designated obligation to Accepted.

Failed, stale, or cancelled outcome

Set the designated obligation to Unsatisfied and retain separate retry work when the directory remains Loaded. Later jobs do not alter this round's terminal outcome.

Load

A directory entering Loading is scheduled immediately as control work when possible. Only its transition to Loaded makes it eligible for the next round's obligation set.

Remove, unload, or exclude

Set the matching obligation to Removed and invalidate any designated job. A replacement at the same path is a new entry and joins the next round.

Overflow

Preserve current progress and record a required later generation as specified in Section 11.6.

Cursor wrap

Stop admitting new baseline obligations for the round. After all remaining obligations reach a terminal outcome, publish Successful health if all are Accepted; otherwise publish Degraded health with unsatisfied paths. Begin a new round without waiting for retry success.

Empty set

Complete the round successfully without filesystem work. Do not start another empty round until a periodic trigger or a directory enters Loaded state.

12Timing and Backpressure

Reconciliation uses a monotonic clock. Wall-clock time and filesystem timestamps MUST NOT control scheduler progress.

batch_duration is monotonic elapsed time from admission of a periodic cycle's closed batch until its last member reaches an Accepted, failed, stale or discarded, or cancelled terminal state. It includes worker queuing, asynchronous filesystem execution, validation, and publication. Work arriving later does not extend the batch.

Let target_period be the target time between the start of one periodic dispatch cycle and the earliest time the next one becomes ready. Let delay be the corresponding sleep after the current cycle completes. They are computed from the measured cycle duration and target duty cycle:

target_period = clamp(
    batch_duration / target_duty_cycle,
    minimum_period,
    maximum_period,
)

delay = max(0, target_period - batch_duration)

The defaults are:

• target_duty_cycle 1 percent
• minimum_period 1 second
• maximum_period 5 minutes

Implementations MAY choose a fixed interval through configuration.

target_period determines a due time, not the actual next start. A periodic cycle MAY start later while another closed batch is active. That delay does not alter its due time, and the ready timer remains subject to the finite-service requirement below.

Immediate command, watcher, or control work queued during a closed batch requests an immediate next cycle. delay governs only the next timer-requested periodic cycle. A batch with no jobs has duration zero and therefore uses the minimum period.

A timer that is ready MUST receive finite service even while watcher and command streams remain continuously ready. This can be achieved by an independent scheduler task, fair selection, or explicit timer priority.

Watcher event queues MUST be bounded or coalesced by path. Queue pressure MUST be observable. Dropping watcher hints under pressure is permitted because reconciliation preserves eventual correctness.

batch_size bounds the number of filesystem jobs, not the duration of an individual filesystem call. Implementations SHOULD support I/O cancellation or timeouts where the filesystem backend permits them.

13Error Handling

13.1Operation Failure

Filesystem adapters classify non-success outcomes as NotFound, NotDirectory, PermissionDenied, Transient, Unsupported, or Fatal. Fatal is reserved for failures that make continued operation of the tree unsafe, such as adapter corruption or loss of the backend. A path-scoped failure MUST be classified as NotFound, NotDirectory, PermissionDenied, Transient, or Unsupported.

Retryable work outcomes are Transient, PermissionDenied, Unsupported, WatcherRegistrationFailed, and the core-generated LimitExceeded. NotFound and NotDirectory are structural outcomes governed by Section 13.2. Fatal terminates the tree.

On Transient failure, the current snapshot is retained. The read target enters retry state with exponential backoff, jitter, and a configured maximum delay. Metadata retries continue while the target remains represented and the requirement is not superseded. Listing retries also require the directory to remain Loaded or Loading. Passing a configured attempt or duration threshold changes path health to degraded but does not discard retry work. An accepted recovery read resets that path's consecutive transient-failure count.

The transient threshold applies only to path-level degradation for a failure not yet used as a designated round outcome. It MUST NOT suppress a degraded reconciliation-round outcome. A designated Transient failure degrades that round on its first attempt. Reconciliation health remains degraded while either the latest completed round is degraded or another path-level degradation cause remains active. A later successful round clears only the round-derived cause.

PermissionDenied and Unsupported retain the current snapshot and publish degraded path health immediately. A Loaded directory retries once per baseline round or after a relevant watcher hint or explicit refresh. A represented metadata target or Loading directory that has no baseline opportunity retries with backoff through the retry class.

LimitExceeded retains the previous snapshot and current Loaded or Loading state, publishes degraded path health immediately, and makes the current command fail and any designated obligation Unsatisfied. It retains one coalesced listing retry. A Loaded target can retry through later baseline work; a Loading target retries with backoff. A relevant watcher hint, explicit refresh, or configured limit increase expedites that retry.

Each represented read target retains at most one coalesced retry record. The record carries its required phase: Metadata, Listing, or WatchRegistrationThenListing, plus attached reasons and barriers. A failed required watch registration uses the control class while the target remains Loading. Other retries use the retry class.

Metadata success clears only a Metadata requirement and its matching degradation cause. Listing success clears Listing and any metadata requirement covered by that listing. Watch-registration success advances WatchRegistrationThenListing to Listing; only the accepted listing clears it. Success MUST NOT clear an unrelated stronger requirement or degradation cause.

Fatal errors terminate the tree after publishing terminal health, regardless of the publication-guard state of the job that reported them (Section 11.4).

Retry work uses the common weighted scheduler. It MUST receive finite service and MUST NOT starve baseline, control, watcher, refresh, or priority work.

13.2Missing Paths and Kind Changes

A NotFound result for a non-root entry is applied as removal after validating all captured generations.

NotDirectory from a listing is not yet a terminal job outcome. The same admitted job MUST confirm it through current metadata supplied with the result or one guarded metadata operation before becoming terminal. This confirmation does not consume another admission slot. A retryable confirmation error fails the job and makes a designated obligation Unsatisfied. NotFound follows the root or non-root removal rules. Fatal terminates the tree. If confirmation observes a directory, the result is stale and the listing is rescheduled.

An unconfirmed NotDirectory from any non-root read, including a confirmation operation, MUST NOT commit a structural change. When current metadata does not identify the non-directory EntryId, the coordinator MUST reclassify the outcome as Transient and queue guarded resolution of the nearest represented ancestor under normal admission. Only confirmed current metadata invokes the non-root kind-change rules.

Initial root NotDirectory MUST fail open. After handle publication, a generation-valid root NotDirectory MUST directly make the root Unavailable without requiring EntryId-identifying metadata.

Confirmed NotDirectory for a represented non-root directory removes represented descendants, changes the entry kind, removes its directory load state, and invalidates its directory work atomically. A pending refresh succeeds after that commit, a pending load fails with NotDirectory, and matching round, initial-scan, and policy-listing obligations become Removed.

open MUST validate that the initial root exists and is a directory before returning. Initial NotFound or NotDirectory fails open.

Initial validation and confirmed reappearance MUST atomically allocate a fresh monotonically increasing root incarnation and fresh EntryIds, set root availability to Available, set initial-scan state to Running, and install the root as Loading. Root jobs, watcher registrations, watcher events, and initial-scan waiters bind to that incarnation.

A retryable failure of the first root listing leaves the root Loading. Confirmed NotFound or NotDirectory makes it Unavailable under the rules below. Fatal terminates the tree.

After handle publication, a validated root NotFound or change to a non-directory MUST atomically:

• mark root availability and initial-scan state Unavailable
• clear the complete snapshot
• remove every active round obligation
• cancel queued work and invalidate in-flight work and watchers
• fail root-dependent commands with RootUnavailable
• fail current initial-scan waiters with RootUnavailable
• publish the snapshot and health transition

PermissionDenied or Transient root failure retains the previous snapshot and follows Sections 13.1 and 13.3. While the root is unavailable, no baseline round starts.

Root reappearance monitoring is built in and enabled by configuration. When enabled, control-class probes use the common scheduler and retry backoff. When disabled, only refresh of the root starts a probe. Other refresh targets and all other root-dependent commands fail with RootUnavailable.

After initial validation or confirmed reappearance, the implementation applies the watch-registration procedure in Section 11.1 and schedules the first root listing. Acceptance transitions the root to Loaded and starts policy traversal. A retryable failure leaves it Loading and follows Sections 11.1 and 13.1; structural and Fatal outcomes follow the preceding root lifecycle rules. Old-incarnation events and job results MUST be discarded, and old EntryIds MUST NOT be resurrected. A refresh of the unavailable root succeeds only after an accepted post-barrier root listing for the recovered incarnation.

initial_scan_complete binds to the incarnation active when called. A caller whose wait fails because the root vanished invokes it again after recovery to observe the new incarnation.

13.3Permission Changes

Permission denial retains the last known representation and reports a degraded path. It does not imply that previous children were removed.

13.4Watcher Failure

Watcher failure is reported and reconciliation continues. The watcher MAY be restarted with backoff. Restarting it does not reset the snapshot and MUST allocate a newer minimum reconciliation generation for a subsequent round.

13.5Worker Failure

Panic, task cancellation, or channel loss in a filesystem worker MUST return its active jobs and read targets to schedulable state or terminate the tree with an explicit fatal error. Work MUST NOT disappear silently.

13.6Capacity Exhaustion

Baseline obligations are represented as scheduler state and MUST NOT be dropped because a queue is full. Watcher hints MAY be coalesced or dropped after incrementing an overflow counter. Commands that cannot be admitted fail before acceptance with a capacity error. Health changes are published even when no snapshot data changes.

14Paths, Links, and Filesystem Semantics

14.1Path Normalization

Snapshot paths are normalized relative paths. Backend-native paths are converted at the filesystem boundary. Paths that cannot be represented safely are rejected and reported.

Case comparison follows the configured filesystem semantics. Display casing is retained separately from comparison keys when required.

14.2Symbolic Links

Symbolic links are represented as entries and MUST NOT be traversed. Supporting traversal through symbolic links requires a separate specification with explicit containment and race semantics.

14.3Mount Boundaries

Crossing filesystem or mount boundaries is policy-controlled. Linux documents that mounting over a watched directory produces no event and suppresses events beneath the new mount point [INOTIFY]. The tree MUST NOT assume uniform watcher behavior beneath the entire root.

14.4Special Files

Sockets, devices, FIFOs, and unknown entry kinds can be represented as opaque entries. They are never treated as directories unless the filesystem abstraction classifies them as directories.

15Resource and Performance Model

Let:

N be the number of represented entries;
D be the number of loaded directories;
B be the configured batch size.

Snapshot storage is O(N). A baseline round attempts one listing for each member of its obligation set and can perform additional retries. A dispatch cycle admits at most B snapshot-producing filesystem jobs across all reasons.

Path and identity indexes SHOULD provide logarithmic or amortized constant-time lookup. Snapshot publication SHOULD structurally share unchanged data.

Very large individual directories can dominate a cycle despite the directory-count budget. Implementations MUST expose listing duration and child count. This specification defines no special large-directory isolation mode. A listing's duration has no wall-clock bound. Its accepted child count and publication remain subject to configured entry limits and all-or-nothing validation. An implementation extension MUST use common admission accounting and preserve complete, atomic listing publication.

Excluded and unloaded directories consume entry metadata only and do not incur periodic listings.

16Observability

The implementation exposes at least:

• current snapshot version
• initial scan state
• current reconciliation generation
• time and duration of the last successful round
• baseline and priority cursor progress
• loaded and represented entry counts
• queued and in-flight job counts
• watcher backend and health
• dropped or coalesced watcher hint counts
• listing latency and failure counts
• degraded paths

Consumers MUST receive the orthogonal health fields defined in Section 7.4. In particular, watcher degradation does not imply root unavailability, and reconciliation degradation does not terminate snapshot reads.

Logs SHOULD state the scheduling reason for a listing without logging file contents.

17Testing Strategy

17.1Deterministic Integration Tests

A deterministic fake filesystem and executor cover:

• initial recursive scan
• watch-before-list ordering at the root and descendants
• recursive and non-recursive watcher backends
• both watch-registration failure modes
• silently dropped create, remove, modify, and rename events
• watcher overflow and restart
• unchanged, future-dated, and decreasing mtimes
• directory changes with unchanged mtime
• configured metadata changes with unchanged directory mtime
• Unloaded-to-Loading transitions and failed first listings
• pre-cursor acceptance and pre-barrier successor reads
• every command target-resolution outcome
• priority sets larger than one batch
• baseline progress under continuous priority and watcher work
• policy invalidation during scanning
• recursive policy-context invalidation
• removal, replacement, and unloading during an in-flight listing
• parent listings racing child metadata reads
• transient and persistent I/O errors
• first-attempt round degradation before the transient threshold
• initial missing or non-directory roots
• root removal, empty publication, and fresh-incarnation recovery
• case-only renames
• atomic rename and canonical path-change order
• symbolic links represented without traversal
• large and empty directories
• closed-batch completion under asynchronous job ordering
• recoverable errors without snapshot or health changes
• clean shutdown with work in flight

Time-based tests use an injected monotonic clock. They MUST NOT depend on wall-clock sleeps.

17.2Model-Based Tests

Random operation sequences are applied to both the implementation and a reference model that performs complete listings. After the fake filesystem becomes quiescent and a successful round completes, both snapshots MUST agree for all loaded paths.

17.3Property Tests

The following properties hold for every generated history:

• snapshot versions increase monotonically
• EntryId values are never reused
• updates transform their previous snapshot into their new snapshot
• path changes follow canonical transaction order
• no excluded entry has a represented descendant
• no unloaded directory has represented immediate children
• no Loading directory has represented immediate children
• baseline cursor progress is finite under sustained expedited work
• failed or stale jobs cannot resurrect removed entries
• at most one snapshot-producing job per EntryId is active
• no stale publication guard can commit
• a sibling's commit never stales an unrelated sibling's job
• an older parent listing never overwrites a newer committed child
• publication
• a Fatal completion terminates the tree even when its guards are stale
• a stale coverage tag can commit but cannot satisfy newer coverage
• every command read satisfying a barrier is post-barrier
• policy-context invalidation reevaluates represented descendants

17.4Fault Injection

Tests inject watcher loss, delayed and reordered job completion, channel closure, timeout, permission denial, malformed paths, and worker cancellation at every state transition.

17.5Benchmarks

Benchmarks report startup, one reconciliation round, update latency, snapshot publication, large directories, deep trees, high event rates, and high-latency filesystems against fixed public workload fixtures. This specification does not mandate hardware-dependent absolute latency values.

18Alternatives and Prior Art

18.1Watcher Events Only

Rejected. Native watcher APIs can overflow, omit events, fail on network filesystems, and expose registration gaps. They cannot provide eventual convergence by themselves [INOTIFY] [FSEVENTS] [RDCW].

18.2Polling Only

Viable for correctness but rejected as the default. It increases normal change latency or background I/O. Watcher hints provide cheap low-latency scheduling while reconciliation provides correctness. notify::PollWatcher and Parcel's brute-force snapshot backends demonstrate this trade-off [NOTIFY] [PARCEL-WATCHER].

18.3Modification-Time Gating

Rejected. Directory mtimes can be coarse, unchanged, future-dated, or explicitly set independently of contents [RACY-GIT] [POSIX-UTIMENS]. Some filesystems do not report correct change dates [NOTIFY]. Adding race windows and observation deadlines moves uncertainty into scheduler state without proving directory contents.

18.4Full-Tree Periodic Rescan

Rejected as the normal path. It creates work spikes proportional to the complete loaded tree. The cursor provides equivalent eventual coverage with bounded scheduling.

18.5Priority Directories Without Reserved Baseline Capacity

Rejected. A priority set as large as the batch can prevent the baseline cursor from moving forever, violating the directory guarantee.

18.6Mutable Shared Snapshot

Rejected. Readers could observe partial directory transitions and update ordering would be ambiguous. Immutable versioned snapshots make publication atomic and diffs reproducible.

18.7Existing Recovery Systems

Apple recommends monitoring before scanning, rebuilding a hierarchy snapshot from directory contents, and periodically sweeping when event history is advisory [FSEVENTS].

notify exposes native loss as Flag::Rescan and offers PollWatcher where native events are unavailable or unreliable [NOTIFY]. It emits events but does not define the application snapshot or its convergence contract.

Parcel exposes recursive subscriptions and historical snapshot queries over native or brute-force backends [PARCEL-WATCHER]. Watchman responds to event loss by recursively recrawling a watched root [WATCHMAN].

These systems establish rescan and polling as standard recovery techniques. This specification differs by making bounded, watcher-independent reconciliation part of the snapshot contract rather than an exceptional whole-tree recovery operation.

19Conformance

A conforming implementation:

1. satisfies the consistency contract in Section 5 without relying on watcher delivery or metadata equality;
2. implements the frozen obligation-set and round transitions in Section 11.8;
3. admits every listing reason through one fair, bounded scheduler;
4. validates every completed job against the publication guards in Section 11.4 and applies reconciliation generations only as coverage tags;
5. publishes immutable, version-ordered snapshots and bounded update streams;
6. reports degraded and terminal states without silently discarding required work; and
7. passes deterministic tests with all watcher events suppressed.

Snapshot serialization and process-restart identity are outside this specification. EntryId values and in-memory snapshots are scoped to one tree instance.

20Security Considerations

Filesystem paths, directory entries, policy results, and watcher events are untrusted inputs.

Implementations MUST:

1. reject relative paths that escape the configured root;
2. represent symbolic links without traversing them;
3. enforce configured limits for watcher paths, command paths, priority paths, pending commands, represented entries, entries per directory, retry state, dispatch batch size, and worker concurrency;
4. avoid recursive call-stack traversal for attacker-controlled depth;
5. preserve filenames that are not valid Unicode without lossy path identity;
6. reject stale job results after root-incarnation, entry, load, policy, target-state, child-binding, change, or dispatch generation changes;
7. avoid exposing file contents through updates or diagnostics; and
8. validate watcher hints against filesystem reads before committing structural snapshot changes.

A directory exceeding configured representation limits is degraded, not truncated. A truncated listing MUST NOT be committed because it could falsely remove entries beyond the limit. Retry count can be unbounded while a target remains eligible, but retry state is bounded to one coalesced record per represented read target plus one root-recovery record. A Loading target uses that one record for its current watch or listing phase. Retry admission obeys the scheduler limits.

This specification does not define a security boundary against a hostile process that can replace path components between filesystem operations. An adapter claiming that stronger property MUST use handle-relative operations or an equivalent platform mechanism. Linux openat2 with either RESOLVE_BENEATH or RESOLVE_IN_ROOT, optionally combined with RESOLVE_NO_SYMLINKS, illustrates such enforcement [OPENAT2].

21IANA Considerations

This document has no IANA actions.

22Normative References

23Informative References