Skip to content

RewriteRules.Common does not terminate: a three-cycle on -x * 1/2 #1056

Description

@Rafael-SOWNet

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.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions