util: equation() renders an unbounded derivation in full, quadratically — #574's deferred depth cap

[Yaraslaut]

Split out of #574, which fixed the crash but deliberately left this. #574's own fix list had a fourth item — "Consider a depth cap: past N nodes, collapse to a named leaf holding the value. An explanation 200,000 steps deep is not an explanation." — and PR #581 did not do it, because it changes equation()'s documented output contract rather than fixing a defect. Filing it so closing #574 does not lose it, together with the cost measurement #574 did not have.

Verification status: reproduced

Revision: fix-574-quantity-provenance-locale @ 3a1effd0 (PR #581), i.e. after the iterative-traversal fix. Nothing below is a crash any more; this is purely about what the output costs and what it is worth.

equation() builds its formula by repeated concatenation in EquationRenderer::combine, so rendering a chain of n derivation nodes copies O(n²) bytes, twice (once symbolic, once substituted). Measured on clang 22.1.8, running total = total + one n times and then calling equation():

n	wall, -O1 + ASan+UBSan	first output line
40,000	11.2 s	200,001 chars
70,000	32.3 s	350,001 chars
100,000	82.8 s	500,001 chars

$ ./prov_san 100000
equation() lines=4 first=500001 chars
destroyed cleanly
 100000  16.87s user 65.47s system 99% cpu 1:22.81 total

The shape of that first line is 0 + c1 + c1 + c1 + ... repeated 100,000 times, with a three-line where c1 = 1 legend under it. It is returned as a std::vector<std::string> of "print-ready lines", so a caller that prints it emits a single half-megabyte line.

Why it matters

Two separate things, and they may want different answers:

1. It is not an explanation. docs/spec/util/quantity_type.md describes equation() as "the worked formula as print-ready lines" — something a domain user reads to see why a number is what it is. Half a megabyte of + c1 is not that. util/render: two reproduced value-type defects that ship by default — Quantity provenance chains and unvalidated locale group-separator stripping #574's suggestion was to collapse past some depth to a named leaf holding the value.
2. It is quadratic, and the depth can come from wire input. The same "loop bound from a ledger replay or a batch of rows" argument util/render: two reproduced value-type defects that ship by default — Quantity provenance chains and unvalidated locale group-separator stripping #574 made about the retained chain applies to anything that calls equation() on the result. Since Fix two shipped value-type defects: provenance chains that overflow the stack, and locale group separators that are stripped instead of validated #581 the walk no longer overflows the stack, so a deep chain now reaches this instead of crashing — which is the right trade, but it means the cost is reachable where the crash used to be.

A depth cap fixes both. Reserving the output would fix only the second (the string still has to be built).

What would change the verdict

• Close as "works as intended" if a derivation that deep is considered out of contract for equation() — but then the contract should say so, and say what happens instead, because today nothing bounds it.
• Close as a non-issue if no caller ever renders a derivation past a few dozen nodes in practice. That is plausible for hand-written domain code and not plausible for a loop whose bound is data, which is the case util/render: two reproduced value-type defects that ship by default — Quantity provenance chains and unvalidated locale group-separator stripping #574 was about.

Not verified

• Whether reserving in combine (instead of capping) brings the cost down enough to matter — the quadratic copying is inherent to building one string per level, so probably not, but it was not measured.
• What a good cap would be. "200,000 steps is not an explanation" is clear; "50 is" is not obviously true.

[Yaraslaut]

New evidence: this is no longer just a cost complaint, it actively fails CI on master's own tip.

master's clang-tsan CI leg times out on exactly the 70,000-node case this issue measured, independent of any PR — confirmed on master's own CI run at 3e8f59f2 (the commit that merged #581), not just on a PR branch:

1076/1739 Test #1076: equation() walks a 70000-node provenance chain without
overflowing the stack ...... ***Timeout 120.07 sec
99% tests passed, 1 tests failed out of 1076

Run: https://github.com/LASTRADA-Software/morph/actions/runs/35431457068/job/105872791321

This issue's own table measured 70,000 nodes at 32.3s under ASan+UBSan alone; TSan's heavier per-access instrumentation pushed the same case past ctest's 120s TIMEOUT. Also reproduced independently on two unrelated draft PRs' CI (#585, #586) via the pull_request merge-ref, which is how it was first noticed — neither PR's own changes touch this code.

Practical consequence: master's clang-tsan leg is red right now, and any PR based on current master will show the same failure through no fault of its own, until either this issue's fix (a depth cap) lands or the test/timeout is adjusted as a stopgap. Worth deciding which happens first, since PRs are going to keep tripping over this in the meantime.

🤖 Generated with Claude Code

[Yaraslaut]

Triage

Verdict: triage: valid, area: util.

Premise check

Re-verified against docs/spec/util/quantity_type.md's own text (lines ~447-451): "Depth is unbounded, so every walk of the DAG is iterative." That sentence is about crash-safety (the iterative rewrite exists so a deep chain doesn't overflow the stack) — it says nothing about the cost of rendering that walk into strings, and nowhere bounds equation()'s output size. So this issue's premise — unbounded depth is a deliberate, specified correctness property, but the quadratic string-building cost of rendering it is unaddressed by that spec — holds up on a fresh read, not just on the original measurement.

New evidence since filing: a caller already reaches this depth in practice

The issue's own "what would change the verdict" section names two closing conditions:

• "no caller ever renders a derivation past a few dozen nodes in practice" — now falsified. tests/test_quantity.cpp:736's stack-safety regression test (added by the same Fix two shipped value-type defects: provenance chains that overflow the stack, and locale group separators that are stripped instead of validated #581 this issue was split from) calls equation() on exactly the 70,000-node case this issue's table measured, and that call now times out master's own CI under TSan (32.3s under ASan+UBSan per this issue's table; TSan's heavier per-access instrumentation pushes it past ctest's 120s TIMEOUT). See tests: equation()'s 70000-node stack-safety regression test exceeds ctest's 120s TIMEOUT under TSan, failing master's CI #589, filed separately since it's a different fix site (the test's TIMEOUT property, not equation() itself) and considerably more urgent — master's clang-tsan leg is red right now.
• "a derivation that deep is considered out of contract" — nothing in the spec says so; see above.

That doesn't by itself prove a depth cap is the right fix (vs. reserving, vs. a different renderer), but it does mean this is reachable in the framework's own test suite, not just a theoretical wire-input scenario — which was the weakest part of the original filing.

Architecture fit

A depth cap on rendered output doesn't conflict with invariant "every walk is iterative" (docs/spec/util/quantity_type.md) — that invariant is about not recursing over the DAG, not about how much of the walk gets turned into Rendered strings. Capping output past some depth is compatible with the existing iterative stack machine (EquationRenderer::render); it would just stop appending past the cap rather than changing how the walk is driven. No invariant blocks the direction #574 originally suggested.

What's still open, per the issue's own "not verified" section

Whether reserving (vs. capping) helps, and what a good cap value is, remain undecided — this triage doesn't resolve those, it just confirms the problem is real and the direction is architecturally sound. Leaving those as implementation-time decisions.

🤖 Generated with Claude Code