Bound the top-down IR rewrite driver's re-application loop #351

Problem

pslua rewrites its intermediate representation (IR) through two drivers, both of which re-apply a rule at a node until it stops firing. One of them, rewriteExpBottomUpM, now carries an iteration budget (maxNestedRewrites, #348): without it, beta reduction livelocked on a term with no normal form. The other, rewriteExpTopDownM, still has the unbounded shape:

rewriteExpTopDownM ∷ Monad m ⇒ RewriteRuleM m ann → RawExp ann → m (RawExp ann)
rewriteExpTopDownM rule = visit
 where
  visit expression =
    rule expression >>= \case
      Just expression' → visit expression'
      Nothing → traverseOf subexpressions visit expression

visit recurses on the rule's own result with nothing to stop it. Its termination argument is a contract on the rules rather than a property of the driver, stated in the driver's own Haddock:

Termination is the rule's obligation: it must not fire on the root of its own result.

Two passes use this driver, both of them lowerings that consume a pattern from the outside in, which is why they cannot use the bottom-up driver (it would dismantle a chain from the inside out, since every tail of a magic-do chain is itself a chain head): magic-do, which turns Effect/ST bind chains into straight-line statements (Language.PureScript.Backend.IR.MagicDo), and deep-bind flattening, which lambda-lifts continuation chains and A-normalises application spines (Language.PureScript.Backend.IR.FlattenDeepBinds).

How it shows up

It does not, today — this is hardening, not a live bug. Neither pass substitutes an arbitrary subterm the way betaReduce does, so neither has a known input that makes it fire on its own result, and a sweep of the IR Optimizer group over hspec seeds 1..500 is clean.

What makes it worth closing anyway is the failure mode. A rule that ever breaks the obligation does not produce a wrong answer or a red test: the compiler stops emitting output and pins one core, exactly as #348 did, and the suite prints nothing at all rather than a failure. That is the hardest failure shape to attribute, and it is one refactor of either pass away.

Approach

Give the top-down driver the same treatment the bottom-up one received: thread a budget through visit, and return the term reached when it runs out. The bottom-up version is the shape to copy —

rewriteExpBottomUpM rule = runWriterT . reapply maxNestedRewrites
 where
  reapply budget = transformMOf subexpressions \e →
    lift (rule e) >>= \case
      Nothing → pure e
      Just e' → do
        tell Rewritten
        case budget of
          0 → pure e'
          _ → reapply (budget - 1) e'

— and the reasoning transfers unchanged: each rewrite preserves semantics and the IR invariants on its own, so a term abandoned mid-rewrite is as valid as a fully rewritten one, and stopping early costs optimization and nothing else.

Whether the two drivers should share one constant is the open question. maxNestedRewrites is 100 because the deepest converging chain measured across the whole test suite is 5 (1232 examples, 344 of them golden compilations of real PureScript, the ~300-deep constant chains included). The top-down driver's rules consume chains whose length is the program's, not a rewrite's, so their legitimate nesting may well scale with chain depth rather than sit at a small constant — in which case the two want separate constants, and the top-down one wants its own measurement.

Verification / Measurement

Instrument the driver to record the deepest nesting visit ever reaches, then run the full suite and the golden corpus, the same way the bottom-up bound was calibrated. The golden corpus is the population that matters here, since it is real compiled PureScript and includes the deep-chain stress modules the flattening pass exists for. Set the bound at a comfortable multiple of the measured peak.

The golden corpus must stay byte-identical: a bound above the legitimate peak cannot change any output, so any golden.ir or golden.lua movement means the bound is too low.

Prerequisites / Relations

Independent — #348 has landed, and this is the sibling driver it deliberately left alone (that change stayed scoped to the driver whose divergence was reproducible).

Acceptance criteria

• rewriteExpTopDownM terminates on every input, without relying on a rule-level obligation.
• The bound is justified by a recorded measurement of the deepest nesting real compilation reaches, not by a guess.
• The relationship to maxNestedRewrites is settled either way: one shared constant, or two with the top-down one's own measurement behind it.