Repository navigation
Architecture WS1: replace hand-rolled graph traversals with @statelyai/graph #3277
Description
Activity
Re-scoped after the #3275 merge: deliverable 1 (model.ts Tarjan copies + cycle DFS) and the depgraph traversals are done on main via @statelyai/graph. Still open per the issue body: the R73 BFS in provider-snapshot-presentation-policy.ts, the reverse reachability in daemon-platform-runtime-inventory.ts, the regex import extractor in scripts/mutation/ownership.ts, and the judgment call on the eager fixtures' specifier regex. Also picked up: parseImports static-scan parity is now tracked separately in #3293, and one unmerged correctness fix from the superseded refactor/ws1-graph-traversals branch (NUL-joined edge ids, f1a64ef) will be verified and absorbed by the implementing PR. Work dispatched; closing PR will link both issues.
I verified the #3275 addendum against the #3277 base (81f4666). The base already uses NUL in importEdgeId, and its importGraph distinct-file-pairs regression test uses the two pairs that stringify to the same " -> " ID. The superseded f1a64ef commit has equivalent behavior and coverage, so no separate fix commit needs to be absorbed.
The rebased #3316 base (
bf2246499a) already contains the correctness fix described inf1a64ef17:importEdgeIduses NUL,collapseEdgesshares that helper, andimportGraph gives every distinct file pair its own edge idreproduces the two->collision pairs.git log -S '\u0000' -- scripts/depgraph/import-graph.tsattributes this to main’sd32c36322(#3275). Therefore #3316 retains the existing fix/test rather than adding a duplicate commit. The superseded branch was inspected withgit showand was not modified or pushed.#3316 also now preserves the old cycle representatives on chorded SCCs: 1,024 synthetic cases and the complete 22-entry production cycle list match rebased main. Exact-head affected gates pass at
98b6e832c42edfa9a9a2c31efacf8bca0c3a1d82; detailed comparison evidence is on the PR.
Part of #3276.
Purpose
Delete the hand-rolled graph code the repo carries for gate computations and run every traversal through
@statelyai/graphon the shared construction path introduced in #3275. Off-the-shelf first: the library owns cycle/community algorithms; our code owns rule content.Blocked by: #3275 (PR #3275 — wait for merge or stack on
refactor/depgraph-statelyai-graph).Required behavior
Replace, keeping each gate's output identical on the current tree:
scripts/layering/model.ts— Tarjan's algorithm (two copies) plus the DFS that extracts a cycle path. Use the library's SCC/cycle facilities; keep our deterministic ordering and reporting shape so gate output does not churn.scripts/layering/provider-snapshot-presentation-policy.ts(R73) andscripts/layering/daemon-platform-runtime-inventory.ts(R76) — library traversal on the shared import-graph.scripts/mutation/ownership.ts— drop the regex import extractor and read the layering edge model (or the depgraph model from refactor(depgraph): run graph traversals on @statelyai/graph #3275) instead.src/__tests__/eager-import-closure.fixtures.ts— same treatment for its traversal/extractor if it duplicates one.Done when
grep -rnE "lowLink|queue\.(push|shift)" scripts/finds no import-graph traversal.pnpm check:toolingtier) produces identical output on the current tree versus merge-base.@statelyai/graphcomes in through refactor(depgraph): run graph traversals on @statelyai/graph #3275.Constraints
docs/agents/pull-requests.md(size budget, commit shape, validation).