util: equation()'s label walk has no visited set, so a shared derivation costs one walk per path

[Yaraslaut]

Found while implementing #582's step limit, and filed separately because it is a
different defect with different evidence: #582 is about a derivation that is
long, this one is about a derivation that is shared, and the cost here is
exponential rather than quadratic.

EquationRenderer::assignLabels (include/morph/detail/quantity_equation.hpp)
is the one walk in equation() with no visited set. countRefs has seen;
render stops at a cK placeholder, a name, or an atom. assignLabels stops
at none of those — it labels a placeholder and then descends through it anyway:

if (!frame.expandThis && isPlaceholder(node) && !labelIndex.contains(node)) {
    labelIndex.emplace(node, placeholderOrder.size() + 1);
    placeholderOrder.push_back(node);
}
// Both the labelled and the unlabelled arm descend exactly when the
// node is not an atom, so the two cases share one exit.
if (isAtomNode(*node)) {
    continue;
}
pending.push_back(LabelFrame{.node = node->right.get(), .expandThis = false});
pending.push_back(LabelFrame{.node = node->left.get(), .expandThis = false});

So a node reachable by k displayed paths is walked k times, not once. The
derivation is a DAG, not a tree — the spec says so ("the derivation is a
shared DAG", docs/spec/util/quantity_type.md) — so the path count can be
exponential in the node count.

Verification status: reproduced

Revision: master be64026a. Reproduced with a standalone harness, clang 22.1.8,
-O1, no sanitizers. q = q + q repeated k times: k + 1 distinct nodes,
2^k root-to-leaf paths.

k=20 nodes=21 equation=0.006s lines=23 first=7 chars
k=22 nodes=23 equation=0.025s lines=25 first=7 chars
k=24 nodes=25 equation=0.099s lines=27 first=7 chars
k=26 nodes=27 equation=0.723s lines=29 first=7 chars
k=28 nodes=29 equation=2.653s lines=31 first=7 chars
k=30 nodes=31 equation=10.322s lines=33 first=7 chars

Four times the time for two more nodes — 2^k, cleanly. A 31-node derivation
takes 10.3 s to render. The output it produces is 33 lines, none longer than
about 50 characters:

  [0] c1 + c1
  [1]     = 536870912 + 536870912
  [2]     = 1073741824
  [3] where c1 = c2 + c2 = 268435456 + 268435456 = 536870912
  [4]       c2 = c3 + c3 = 134217728 + 134217728 = 268435456

That linear output next to exponential time is what localises the defect without
a profiler: every walk that emits text is bounded here, so the time is being
spent in the one walk that emits nothing. Confirmed by mutation — adding a
visited set to assignLabels alone (no other change, step limit explicitly
disabled so it cannot be what helps) takes k=30 to 0.000 s with byte-identical
output, and k=60 — 2^60 paths — also renders instantly:

k=30 nodes=31 equation=0.000s lines=33 first=7 chars    (step limit unlimited)
k=60 nodes=61 equation=0.000s lines=63 first=7 chars    (step limit unlimited)

Why the fix is safe

The walk exists to assign cK labels in first-appearance order. A second visit
to a node can only re-assign labels it already holds (the code guards that with
!labelIndex.contains(node)) and re-walk a subtree it already walked, so
skipping it changes nothing observable — which the byte-identical output above
is the evidence for.

Reachability

q + q is contrived; the realistic shape is the one the spec's own example
builds — a sub-value reused in several places, (x - y) / x — nested. Each
level of nesting doubles the walk. Whether a real application nests reuse deeply
enough to notice is not established here: this is reproduced as a cost
property of the code, not observed in a caller.

What would change the verdict

• Close when assignLabels carries a visited set and a nested-reuse
  derivation renders in time proportional to its node count.
• Re-open if any other equation() walk is found to lack one.

Not verified

• Whether the exponential is reachable through wire-driven input the way util/render: two reproduced value-type defects that ship by default — Quantity provenance chains and unvalidated locale group-separator stripping #574's
  depth was. q = q + q is a hand-written shape; nothing here shows a data-driven
  loop producing it.
• The attribution is by elimination and mutation, not by a profiler.

[Yaraslaut]

Triage: valid — and it is already fixed in flight, in PR #603

The premise holds, and its figures still describe master

include/morph/detail/quantity_equation.hpp is unchanged between be64026a (the revision this was measured on) and current master fbb90181:

$ git log --oneline be64026a..origin/master -- include/morph/detail/quantity_equation.hpp
(no output)

So the reported timings — k=20 0.006s, k=22 0.025s, k=24 0.099s, k=26 0.723s over 27 nodes — describe today's code, not a revision that has moved on. Roughly 4–7× per +2 in k, against a node count growing by 2, which is the exponential shape claimed. The mechanism is visible in the quoted code: assignLabels labels a placeholder and then descends through it regardless, while countRefs has seen and render stops at a placeholder. The spec's own words back the framing — docs/spec/util/quantity_type.md calls the derivation a shared DAG, and a per-path walk over a DAG is exponential in the path count.

But do not dispatch this — PR #603 already carries the fix

This is the important part of the triage. #603 (in flight, for #582) declares Fixes #582. Fixes #602. and touches assignLabels directly:

+  The labelling walk carries a **visited set**, like the reference count.
+    /// @brief Nodes `assignLabels` has already settled (label, elision, or …

So sending a lane at this issue would collide head-on with an open PR.

Two consequences, per the runner skill's Step 6:

1. These measurements go stale the moment util: bound what equation() renders, and make rendering it in full cheap (fixes #582) #603 merges. Anyone building against the numbers above after that point is building against a revision that no longer exists. That is recorded here rather than discovered later.
2. util: equation()'s label walk has no visited set, so a shared derivation costs one walk per path #602 should be closed by verifying util: bound what equation() renders, and make rendering it in full cheap (fixes #582) #603, not by separate work. The right check is to re-run this issue's own harness against util: bound what equation() renders, and make rendering it in full cheap (fixes #582) #603's branch and confirm the curve flattens — the issue supplies the harness, which is exactly what makes that cheap.

On filing it separately and fixing it here — I think this was right

AGENTS.md says "Do not fold an unrelated finding into the current change", and also "If it belongs to the change, it is not a separate finding." This sits on the line, and the lane took the defensible route: file with independent evidence, then fix in the same PR, and say so in the PR body.

I agree, for a reason worth recording: a step limit without a visited set would not be a coherent limit. #582's fix bounds how many steps assignLabels may spend; if a shared node consumes that budget once per path, the budget is spent on redundant walks and the limit does not bound the cost it was introduced to bound. The two changes are load-bearing for each other, so splitting them across PRs would have shipped a half-working limit.

Filing separately still bought the thing that matters — the evidence survives in an issue of its own, with its own reproduction, rather than living only inside a closed PR body. AGENTS.md's warning is that "closed issues stop being read"; a PR body is read even less.

Verification status

• Verified by me on fbb90181: that quantity_equation.hpp is untouched since the measured revision, that util: bound what equation() renders, and make rendering it in full cheap (fixes #582) #603 modifies assignLabels and adds a visited set, and that util: bound what equation() renders, and make rendering it in full cheap (fixes #582) #603 claims to fix this issue.
• Taken from the report, not re-run: the timing table and the harness. I did not build the harness or reproduce the exponential curve myself.
• Not verified: whether util: bound what equation() renders, and make rendering it in full cheap (fixes #582) #603's visited set is correct — that it settles each node once without changing which labels are emitted. That is a review question for util: bound what equation() renders, and make rendering it in full cheap (fixes #582) #603 and I have not assessed it here.

What would change the verdict

If #603 is rejected, re-scoped, or merges without the visited set, this becomes live again and needs its own lane. Re-open on that basis rather than assuming it went with #582.