RewriteRules.Common iterated on -x * 1/2 never reaches a fixed point, with or without the
normalisation between passes. Found by a new test that puts #746 tier 2's "termination checked by
tooling rather than asserted by authors" into the build rather than into a workspace harness.
The cycle
Printed forms are not enough to see it — two of the three trees print the same string — so this is
the shape:
0: -x * 1 / 2 Divf(Mulf(Mulf(-1, x), 1), 2)
1: -1/2 * x Mulf(-1/2, x)
2: -x / 2 Mulf(-1, Divf(x, 2))
3: -x / 2 Divf(Mulf(-1, x), 2)
4: -1/2 * x Mulf(-1/2, x) <- step 1 again
So the cycle proper is
Mulf(-1/2, x) -> Mulf(-1, Divf(x, 2)) -> Divf(Mulf(-1, x), 2) -> Mulf(-1/2, x)
three distinct trees printing as two distinct strings. Each step is Common.ApplyOnce(...) followed
by .InnerSimplified, which is how Simplificator runs the set.
ApplyOnce is deterministic — -x / 2 parsed fresh always rewrites to -1/2 * x. The apparent
non-determinism in a printed trace is only the two trees at steps 2 and 3 sharing a string.
What it does and does not break
Simplify does not hang: it bounds its own iteration, and "-x * 1/2".Simplify() is
-1/2 * x in about 40 ms. So this is not a user-visible defect today.
It matters because tier 2 makes rule sets first-class data that a caller may apply on its own, and
Common is not a terminating rewrite system on its own. Two rules disagree about which of
c * x and (c * x) / d is the destination, and nothing records that the orientation is a choice.
Why it was not found before
work/rulecheck has measured termination for a while and reports Power and NumericNeat as
settling only in composition. Its corpus has no unary shape applied to a compound expression, so
-x * 1/2 is not in it. The corpus was the limit, not the check.
Not fixed here
Choosing an orientation changes the output shape of a set that runs on nearly every simplification,
and CanonicalOrderExact and the normalisation already interact in ways that have been surprising
before. That is a deliberate decision rather than a patch, so this is filed rather than fixed.
The new test names Common in a list of known non-terminating sets and asserts the list in both
directions, so a set that starts cycling fails and a set that stops cycling has to leave the list.
RewriteRules.Commoniterated on-x * 1/2never reaches a fixed point, with or without thenormalisation between passes. Found by a new test that puts #746 tier 2's "termination checked by
tooling rather than asserted by authors" into the build rather than into a workspace harness.
The cycle
Printed forms are not enough to see it — two of the three trees print the same string — so this is
the shape:
So the cycle proper is
three distinct trees printing as two distinct strings. Each step is
Common.ApplyOnce(...)followedby
.InnerSimplified, which is howSimplificatorruns the set.ApplyOnceis deterministic —-x / 2parsed fresh always rewrites to-1/2 * x. The apparentnon-determinism in a printed trace is only the two trees at steps 2 and 3 sharing a string.
What it does and does not break
Simplifydoes not hang: it bounds its own iteration, and"-x * 1/2".Simplify()is-1/2 * xin about 40 ms. So this is not a user-visible defect today.It matters because tier 2 makes rule sets first-class data that a caller may apply on its own, and
Commonis not a terminating rewrite system on its own. Two rules disagree about which ofc * xand(c * x) / dis the destination, and nothing records that the orientation is a choice.Why it was not found before
work/rulecheckhas measured termination for a while and reportsPowerandNumericNeatassettling only in composition. Its corpus has no unary shape applied to a compound expression, so
-x * 1/2is not in it. The corpus was the limit, not the check.Not fixed here
Choosing an orientation changes the output shape of a set that runs on nearly every simplification,
and
CanonicalOrderExactand the normalisation already interact in ways that have been surprisingbefore. That is a deliberate decision rather than a patch, so this is filed rather than fixed.
The new test names
Commonin a list of known non-terminating sets and asserts the list in bothdirections, so a set that starts cycling fails and a set that stops cycling has to leave the list.