Skip to content

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

Description

@flyingrobots

Plan: https://github.com/git-stunts/git-warp/blob/plan/streaming-recursive-materialization/docs/plans/streaming-indexed-recursive-warp.md
Design PR: #813

Outcome

Extend indexed traversal across graph-valued attachments without call-stack recursion, global ordinal assumptions, eager child materialization, or infinite expansion.

Required work

  • 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.

Acceptance

  • 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.

Metadata

Metadata

Assignees

No one assigned

    Labels

    area:queryPrimary work area: query.priority:nextNext in line after active work.status:availableOpen and available for prioritization; not blocked or actively in progress.type:featureNew capability or product behavior.

    Type

    No type

    Projects

    No projects

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions