Skip to content

Tags: pg83/ay

Tags

1

Toggle 1's commit message
T-14: fix dfsID non-source branch to lead its own closure; WalkClosur…

…e output → dedicated bump arena

dfsID's non-source branch emitted the queried node mid-list instead of first:
closureOf returns the SCC-SHARED closure (strongconnect maps every cycle member
to one slice via subgraphCache[u]=ref for all members), so closureOf(v)[0] is
the SCC representative, not v. For a root inside an include cycle (e.g.
scheme.h <-> scimpl.h) the walk root therefore did not lead its own closure —
the [1:] consumers (walkClosureWithSourceRel, WalkSource) then stripped a real
header instead of the root. The old WalkClosure masked this by force-writing
block[0]=root and skipping dups. Fix: the non-source branch emits the queried
node first, so a walk root always leads its closure; the [1:] convention holds
without any prepend/skip. Non-source children reorder is washed out by the
normalizer's sorted-input canonicalization, so the graph stays byte-exact.

WalkClosure now builds its (retained) output directly into a dedicated
walkOutArena: orderIDPool and the order->out copy are removed. The arena is
SEPARATE from closureArena because the DFS populates the closure cache via
closureArena as it walks — sharing one bump cursor would interleave cache and
output allocations. Per-call hint 8192 (measured sg5 max output 4014, ~2x).

sg5 stays byte-exact (all 5 gating cases OK). Perf ~neutral: wall/alloc flat,
RSS ~+20MB from 1.5x arena overshoot on the now-arena-retained outputs;
WalkClosure's per-call make is eliminated.

Co-Authored-By: Claude Opus 4.8 (1M context) <noreply@anthropic.com>