Repository navigation
pm-stack(aggregator): epic-graph rankedBlocked traversal is exponential on diamond blockedBy graphs — and contributingItems lists duplicates #6371
Description
pm-stack(aggregator): epic-graph rankedBlocked traversal is exponential on diamond blockedBy graphs — and contributingItems lists duplicates
Evidence
pm-stack/aggregator/src/epic-graph.ts:25-86 defines two recursive helpers,
transitiveOpenEpicDescendants and contributingDownstreamItems. They are
functionally identical (both return the set of open Epic items in the transitive
blockedBy ancestry of a ref), and both pass new Set(visited) — a fresh copy
of the visited set — to each recursive call (epic-graph.ts:45 and :76).
A visited set copied per branch only prunes cycles along the current path; it
never prunes a subgraph reached by a second path. On a diamond-shaped
blockedBy graph (two items in one layer both blocked by the same two items
in the next layer — the natural shape when parallel work shares blockers),
the number of root-to-leaf paths doubles per layer, and every path is walked
in full. epicGraph() (epic-graph.ts:350-353) then runs both helpers for
every blocker of every open member, over the whole pool (byRef is
the uncapped pool; the 120-node display cap at epic-graph.ts:237 does not
bound this traversal).
render.ts:6567 calls epicGraph() once per epic section on every project
page render (epicGraphSections → epicGraphOneHtml), so one diamond
anywhere in the pool's blockedBy graph, reachable from any member's blocker,
stalls the whole page render.
Verified this run on the laptop against origin/main @359996097f, probe
~/git/fleet/probe-epic-diamond (bun, real epicGraph from the tree; pool
items are otherwise minimal — one member blocked by both layer-0 nodes, each
layer's nodes blocked by both nodes of the next layer, last layer blocked by
one open Epic):
| diamond layers | pool nodes | epicGraph time |
|---|---|---|
| 4 | 11 | 1.3 ms |
| 8 | 19 | 0.9 ms |
| 12 | 27 | 5.8 ms |
| 16 | 35 | 84.7 ms |
| 20 | 43 | 1757.1 ms |
Growth is ~2× per added layer (12→16 layers: ~15×; 16→20: ~21×), so ~24
layers ≈ tens of seconds and ~28 layers ≈ many minutes — from a 43-node
pool, far below any pool-size limit. Control: a plain 40-node chain through
the same code takes 0.3 ms, so the cost is the diamond path multiplicity,
not pool size or depth alone.
Second, simpler defect in the same computation: rankedBlocked's
contributingItems is built by flat-mapping the per-blocker contributing
sets with no deduplication (epic-graph.ts:396, r.sortedBlockers.flatMap(b => b.contributingItems)),
while downstreamCount counts the blockers' sets distinctly per blocker.
In the probe above (member with two blockers that share the same downstream
epic), the output was:
{"ref":"developing-today/code#2","downstreamCount":1,
"contributingItems":["developing-today/code#9000","developing-today/code#9000"]}render.ts:6592-6594 renders that list verbatim, so the project page lists
the same "Contributing downstream epics" link twice.
Why it matters
- The aggregator is a live dashboard service; its project page render path
can be stalled for seconds-to-minutes by ordinary issue-graph data (two
shared blockers per layer is a normal shape for epic work), with no cap,
timeout, or memoization anywhere in the traversal. Nothing about the input
is exotic or attacker-crafted — it is the fleet's own native blockedBy
relations (impl(aggregator+collector) part 1 of 2: Project pool graph edges contract (split of #1122) #2399 contract). - The duplicate
contributingItemsentries are a visible correctness bug on
the same page, and the duplicated helper (two identical traversals per
blocker) doubles the exponential cost for no benefit.
Acceptance criteria
- The transitive blockedBy traversal visits each reachable pool item at
most once per query (shared visited set / memoization, not a per-branch
copy), so a 20-layer diamond pool of ~43 nodes scores in milliseconds,
comparable to the chain control — with a regression test (named oracle:
the same diamond fixture, asserting both the result set and a
node-visit bound or a generous wall-clock bound). - Only one traversal implementation remains (the duplicate helper is
removed or one calls the other), with identical results to today's
sets on the existing epic-graph tests. -
rankedBlocked[].contributingItemscontains each ref at most once
(distinct, in a deterministic order), pinned by a test with two
blockers sharing a downstream epic. - Existing epic-graph test suite passes unchanged in behaviour for
chains, cycles (a blockedBy cycle still terminates and returns the
correct set), and out-of-pool blockers.
Filed by new-issue-creator-code-b (Lane B), verified this run; probe and
timings above are reproducible from ~/git/fleet/probe-epic-diamond.
Activity
developing-today commentedon Nov 5, 2026
CODE-1889
dezren39 commentedon Nov 5, 2026
🤖 Agent note · filed
dezren39 commentedon Nov 5, 2026
🤖 Agent note · done (triage)
direct, worked by this lane03d1a21eaeec864cb3b6691faf83f4b4fcef9877(freshgh apiread ofpm-stack/aggregator/src/epic-graph.ts, 483 lines):transitiveOpenEpicDescendants(blockerRef, byRef, new Set(visited))— per-branch visited copy; line 77: identical pattern incontributingDownstreamItems. The two helpers (lines 26 and 57) are functionally identical and both run per blocker (lines 355 and 358), doubling the exponential traversal.contributingItems: r.sortedBlockers.flatMap(b => b.contributingItems)— no deduplication, matching the duplicate-output evidence in issue pm-stack(aggregator): epic-graph rankedBlocked traversal is exponential on diamond blockedBy graphs — and contributingItems lists duplicates #6371.repo-health:v1:fix:developing-today/code:issue:6371): shared-visited/memoized traversal, single traversal implementation, dedupedcontributingItems, diamond-fixture regression test (oracle: the issue pm-stack(aggregator): epic-graph rankedBlocked traversal is exponential on diamond blockedBy graphs — and contributingItems lists duplicates #6371 diamond fixture).101 remaining items
dezren39 commentedon Nov 6, 2026
Handed off to opencode claimant per execution-lane assignment (task 10756, issue #6371).
dezren39 commentedon Nov 6, 2026
🤖 Agent note · handed off
dezren39 commentedon Nov 6, 2026
agent-note:v1 · repo-worker-code (OpenChamber scheduled lane 335a5d1f) · picked up task 10756 · implementing shared-visited traversal + contributingItems dedupe in pm-stack/aggregator/src/epic-graph.ts. Next: PR.
dezren39 commentedon Nov 6, 2026
agent-note:v1 · repo-worker-code (OpenChamber scheduled lane 335a5d1f) · task 10756 done · PR opened: #6551 (shared-visited traversal, single helper, deduped contributingItems, diamond/shared-downstream/cycle regression tests). CI pending; the issue closes on merge.
dezren39 commentedon Nov 7, 2026
🤖 Agent note · bound