Repository navigation
A rule set that never settles over a whole tree is caught too (#825) - #1168
Merged
Merged
Conversation
The cycle check added with this file rewrites at the root, which is what makes
its "a term came back" criterion mean something -- but it is also what it cannot
see past. A full pass can move its rewrite to a different node each time and
never repeat a term while still never settling.
`UntilStable` already answers that question. It reports hitting its bound as no
answer rather than as the last value reached, and its remarks say why: "an
unbounded rewrite loop is the failure mode this layer is supposed to make
visible, and handing back a value from the middle of one would hide exactly the
case worth seeing." This is a caller taking it up on that, over every registered
set and the same seeds.
It finds one, and it is not a cycle. NumericNeat grows `-x / (-y)` by four nodes
a pass for ever:
-1 * 1 * 1 * ... * x / (1 * y) * 1 * 1 * ... * (-1)
The rules that bring a negative factor out of a numerator and out of a
denominator each write the magnitude back in its place, and when the factor is
-1 the magnitude is 1, which goes back as a literal `1 *` rather than folding.
The two then undo each other around the factors that accumulate. That is the
shape of #1056 one file over, and #1056's fix was to decline c = -1 for the same
reason -- the sign is not a factor whose magnitude is worth writing out.
Simplify is not affected and answers `x / y`: the pipeline is bounded and picks
by size rather than running this set alone to a fixed point. So it is latent,
and it is filed as #1167 rather than fixed here, because declining at a
magnitude of 1 narrows two rules that are otherwise doing useful work and wants
measuring first.
Pinned as the one known pair rather than counted, so that a new one fails and so
does this one going away: a fix should delete the entry rather than leave a name
that no longer means anything.
Full suite 9555 passed, 0 failed.
Part of #825.
Co-Authored-By: Claude Opus 5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_012sonx8iAspMiwRwokT1Ura
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
The cycle check merged in #1165 rewrites at the root, which is what makes its "a term came back"
criterion mean something — and it is also what it cannot see past. A full pass can move its rewrite
to a different node each time and never repeat a term while still never settling.
UntilStablealready answers that question, and says so in its own remarks:This is a caller taking it up on that, over every registered set and the same seeds.
It finds one, and it is not a cycle
NumericNeathas no fixed point on-x / (-y). It grows by four nodes a pass, indefinitely:No term ever repeats, so the root check was right to pass — this needed the whole-tree form.
a-negative-factor-in-a-numerator-comes-outand its denominator twin each take a negative factor outand write the magnitude back in its place. When the factor is
-1the magnitude is1, and itgoes back as a literal
1 *rather than folding away; the two rules then undo each other around thefactors that accumulate.
That is #1056 one file over. #1056 was fixed by having the collecting rule decline
c = -1, witha comment giving the reason — "that is not a numeric factor to collect but the sign, which the
language spells as a product." The same reasoning applies here.
Latent, not live — checked rather than assumed
Simplifyis unaffected:"-x / (-y)".Simplify()answersx / yin 68 ms, because the pipelineis bounded and selects by size rather than running this set alone to a fixed point. Nothing a user
does today reaches it.
It still matters. A caller may reasonably use
Transformation.Rewriting(set).UntilStable(n)— thatis what the layer is for — and equality saturation runs sets against a budget, which a set with no
fixed point spends.
Not fixed here
Declining at a magnitude of
1is the obvious move and matches #1056's precedent, but it narrows tworules that are otherwise doing useful work. #1167
records what a fix would need to establish first: which expressions currently reach a better form
through the
1 *step, and whetherSimplify's answer moves for any of them.Pinned as the one known pair rather than counted, so a new one fails the test — and so does this
one disappearing. A fix should delete the entry rather than leave a name behind that no longer means
anything.
Verification
Full suite 9555 passed, 0 failed, 14 skipped.
Part of #825.