Traverse recursive WARP graphs with cycle-safe bounded receipts #820

1. Background Context

Source: git-warp #820. Audited against main 94b40dac64034cd8caab9bb05efe14a0c22bd735. Template: feature; work type: type:feature.

Current scope and disposition: Traverse typed references with child-local indexed selection; queue, cursor and cancellation guarantees belong here, not in a docs-only roadmap.

Reported context (historical names and counts require the current disposition above):
Plan: https://github.com/git-stunts/git-warp/blob/plan/streaming-recursive-materialization/docs/plans/streaming-indexed-recursive-warp.md
Design PR: #813

2. Problem Description

Traverse typed references with child-local indexed selection; queue, cursor and cancellation guarantees belong here, not in a docs-only roadmap.

Historical source report; the current disposition above supersedes obsolete claims:
Extend indexed traversal across graph-valued attachments without call-stack recursion, global ordinal assumptions, eager child materialization, or infinite expansion.

• Use an explicit async work queue with backpressure and cancellation.
• Apply each child graph local Roaring selection and address roots.
• Track visited identity by graph identity, retained root, and coordinate.
• Distinguish first expansion, shared reference, direct/indirect cycle, unresolved locator, redaction, and budget exhaustion.
• Support depth, graph, node, edge, result, byte, time, and concurrency budgets.
• Preserve occurrence paths while avoiding repeated basis expansion.
• Emit continuation cursors and transitive receipts.

2b. Proposed Solution

Traverse typed references with child-local indexed selection; queue, cursor and cancellation guarantees belong here, not in a docs-only roadmap.

Historical approach to reconcile:
Current architecture rules take precedence: parsing/encoding stays at adapters, domain concepts are runtime-backed, no trust casts are introduced, and tests run in Docker.
Extend indexed traversal across graph-valued attachments without call-stack recursion, global ordinal assumptions, eager child materialization, or infinite expansion.

• Use an explicit async work queue with backpressure and cancellation.
• Apply each child graph local Roaring selection and address roots.
• Track visited identity by graph identity, retained root, and coordinate.
• Distinguish first expansion, shared reference, direct/indirect cycle, unresolved locator, redaction, and budget exhaustion.
• Support depth, graph, node, edge, result, byte, time, and concurrency budgets.
• Preserve occurrence paths while avoiding repeated basis expansion.
• Emit continuation cursors and transitive receipts.

2c. Alternatives considered and rejected

No additional alternatives are recorded as decided. Reject duplicate ownership, private-import escape hatches and a broken intermediate mainline; retain original alternatives below when present.

2d. Acceptance Criteria

• Direct and indirect cycles terminate deterministically.
• Shared child graphs are expanded once while all reference paths remain observable.
• Slow consumers do not cause unbounded queue growth.
• Every opened child basis and live-locator resolution appears in the receipt.
• Limit exhaustion reports incomplete posture and a usable cursor.
• No traversal path constructs a complete parent or child graph.

2e. Test Plan

Golden: Attach, replace, clear and stream node/edge content through supported package imports.

Edges: Missing owners/handles, size boundaries, history and concurrent updates.

Known failure modes: Staging failure, missing capability, truncation and cancellation publish no partial result.

Fuzz and stress: Generated large payloads, slow consumers and recursive cycles where in scope, under a Docker heap cap.

All tests and benchmarks execute in COPY-based Docker containers without host repository or Git-directory mounts. This planning audit does not claim those checks were run.

3. Prerequisites

Completion prerequisites; preparatory work may start earlier.

• #816: Each child must use its own indexed selection and bounded address roots; full child materialization is forbidden.
• #819: Recursive traversal consumes validated pinned/live references and records each resolved child basis.
• #903: Recursive traversal must honor the distinction between finite owned structural attachments and possibly cyclic external/live references. It consumes Define recursive attachment ownership and descendant-preserving mutation semantics #903 ownership semantics directly as well as Add typed recursive WARP graph attachment references #819 reference encoding; this is already transitively ordered through Add typed recursive WARP graph attachment references #819. Review basis: contract-inference.

4. Scope

In: Traverse typed references with child-local indexed selection; queue, cursor and cancellation guarantees belong here, not in a docs-only roadmap.

Out: unrelated domain work and any expansion beyond the issue’s stated observable outcome.

Safe intermediate state: the PR builds and passes relevant checks after its listed prerequisites; existing supported behavior remains usable. Any preparatory step must be independently mergeable.

Domain review, 2026-10-01 — accepted ownership / scope correction:

Consume #903 ownership laws as well as #819 reference encoding. Apply finite-owned structure and potentially cyclic external-reference rules correctly; do not infer ownership from traversal reachability.

5. Why now

Maintainer ordering: memory correctness first, supported attachments next, then land eligible PRs. Preserve this card’s existing priority unless a separately recorded scope decision changes it.

6. Risks

Main risk: implementing the historical description instead of the current runtime contract. Preserve compatibility, causal/ownership invariants and bounded behavior relevant to attachments.

7. Definition of Done

The issue-specific acceptance checks pass, relevant validation evidence is attached, and the issue links the coherent PR and resulting mainline integration commit. No open item is hidden in a later repair PR.

8. Stakeholders

James Ross: maintainer, assignee and acceptance owner. Public API consumers rely on reachable node/edge attachment operations and honest ownership.

9. Related Issues

• Blocks completion of #822: Migration explicitly verifies recursive traversal in scratch and repeats that verification after promotion. Reference encoding alone cannot establish cycle termination, shared-child handling or bounded traversal.
• Blocks completion of #823: The final proof explicitly includes shared children, cycles, live locators and slow recursive consumers.

Historical paths, counts, release names and shell examples in source material are evidence to reconcile, not authority to restore retired documentation or run host tests.