Relationships
#2730 gatorwalk-factory: graph validation fails at default cycle limits; prune dominated count states
Opened by skunk-ape · 9/29/2026· Shipped 9/29/2026
Part of the gatorwalk-factory rebuild (gatorwalk-factory/ in swamp-extensions). Read gatorwalk-factory/DESIGN.md, "Graph validation", first. This closes gap 8 in lifecycles/swamp-extensions.md.
Problem
The graph analysis (_lib/graph.ts) runs two passes:
- The structural pass finds stuck work: dead ends, unreachable stages, and gates that never pass. It ignores cycle limits, and it finishes the swamp-extensions lifecycle in 119 states.
- The count pass (
exploreCounts) asks one narrower question: which transitions can only be taken after a person grants a cycle override? Its only finding is theneeds-cycle-overridewarning.
A count-pass state is the current stage plus the number of entries into every stage, so the state space is the product of every looping stage's limit. Since #2654, validate fails whenever either pass stops at its 100,000-state cap. The result is that a realistic lifecycle with loops fails validate at the default maxCycles of 5. swamp-extensions.yaml only passes because its limits were lowered to suit the analyser (2/3/3/2 on four stages), which the mapping itself says is not a process choice.
Measured on swamp-extensions.yaml on swamp-extensions main at fa830fbda:
| Cycle limits | Count-pass states | Time | Under the 100,000 cap? |
|---|---|---|---|
| As shipped (2/3/3/2) | 11,132 | 22 ms | yes |
| 3 everywhere | 23,574 | 29 ms | yes |
| 4 everywhere | 129,552 | 154 ms | no |
| Default 5 everywhere | 506,220 | 629 ms | no |
Speed is not the issue; the growth is. Each additional looping stage multiplies the state count by up to about six, so raising the cap only delays the failure. The GW-13 starter templates and the GW-15 launch templates will compose longer loops.
Fix: prune dominated count states
Two count states can be at the same stage with the same set of stages entered. That set is what the structural blockers read, so both states have produced the same artifacts and evidence. If one of them has fewer or equal entries into every stage, every transition open to the other is also open to it. An entry count below a limit never closes a transition, and a non-inverted max-cycles gate or a target's cycle limit only refuses when the count is too high. So the state with more entries can't discover an enabled transition the other can't, and it can be dropped.
For each (stage, entered set), keep only the count vectors that no other vector there is below or equal to on every stage. Explore those.
The exception is inverted max-cycles gates. invert: true means the gate passes only after enough entries, so more entries is better for it and the rule above breaks. For every stage that an inverted gate counts, compare counts for exact equality rather than dominance, and keep tracking them exactly as today. None of the bundled lifecycles use an inverted gate, but the format allows one, and it must be handled and tested.
This keeps the check exact: it reports the same needs-cycle-override findings as the full exploration. It is not an approximation.
Out of scope
- Changing what
validatedoes on truncation. #2654's rule, that a pass stopping at the cap failsvalidate, stays unless Seth decides otherwise. If pruning still leaves a realistic lifecycle over the cap, bring that back as a finding rather than relaxing the rule. - Raising or configuring the cap.
- The structural pass. It is not the problem.
Done when
exploreCountsprunes dominated states, with exact tracking for stages counted by invertedmax-cyclesgates. DESIGN.md's "What the analysis assumes" describes the rule and why it is exact.- Equivalence is tested: on the bundled lifecycles, on the testdata lifecycles and templates, and on generated small lifecycles (including inverted gates), the pruned pass gives the same findings as the unpruned exploration at a large cap. Keep the unpruned exploration available to tests as the reference.
- The lowered
maxCyclesvalues are removed fromswamp-extensions.yaml, and it validates at the default limits under the 100,000 cap. Report the count-pass state count before and after. The "Cycle limits" section ofswamp-extensions.mdis updated, and gap 8 is marked resolved, keeping its number.
Shipped
Click a lifecycle step above to view its details.
system commented 9/29/2026, 8:36:41 PM
Classified automatically when this issue was filed.
- Source: Extensions
If you feel this classification is incorrect, add a ripple to tell us so.
Sign in to post a ripple.