Flatten deeply-nested non-Effect/ST do-blocks#107
Merged
Conversation
A straight-line `do`/`>>=` chain desugars to a right-nested tree of continuation closures. Past ~200 nesting levels Lua's parser refuses to load the chunk (`chunk has too many syntax levels`, LUAI_MAXCCALLS) — a correctness failure unique to the Lua backend. magic-do (#46) already fixes Effect/ST; this handles every other monad. New IR pass `flattenDeepBinds` (runs right after `magicDo`, so only non-Effect/ST chains remain): it lambda-lifts long bind chains, splitting them into segments and turning each segment's continuation into a small named `$kont` helper whose free continuation variables are passed explicitly. This relocates closures and forwards their environment but never reorders, drops, or duplicates a bind/k call, so it is semantics-preserving for any monad. Running after `renameShadowedNames` makes every local unique, so helpers reuse the chain's own binder names as parameters and no De Bruijn shifting is needed. When a cut's live set would exceed Lua's 60-upvalue cap the pass bails and leaves the chain nested. Safety net `Language.PureScript.Backend.Lua.NestingCheck`: a post-codegen check (in `Backend.compileModules`) that rejects a chunk nesting beyond a conservative threshold with a clear `NestingTooDeep` error instead of emitting unloadable Lua. Catches whatever `flattenDeepBinds` bails on, plus not-yet-flattened deep constructs (ado/apply, case/concat/literal). Tests: golden fixtures Golden.LongMaybeBind (runnable, 300+ Maybe binds with transitive liveness; eval oracle `(Just 301)`) and Golden.LongMaybeBindModule (module mode); unit specs for both the pass (free-ref preservation, bounded nesting, idempotence) and the detector. Docs: docs/QUIRKS.md updated to describe the flattening and the remaining unfixed cases. Fixes #104
NestingCheck previously exercised only call arguments and the curried spine. Add metric + threshold coverage for the constructs the detector is the sole safety net for (FlattenDeepBinds does not flatten them): operator chains, if-ladders, nested table constructors, and field-access chains. FlattenDeepBinds previously tested only pristine bind chains. Add a chain interleaved with discard (unused-binder) steps — the shape a real do block produces once discardUnit.discard collapses to bind — asserting it still flattens while preserving the bind count and free-reference set.
flattenDeepBinds only flattened pure bind chains built on a literal Bind dictionary (Maybe, Either). It missed two shapes, so any do block that interleaves statement lines — most importantly a State block of get/put — failed to flatten and hit Lua's parser nesting cap (chunk has too many syntax levels): - A statement line is a discard, whose Discard Unit instance is discard = bind; the optimizer leaves the head as (dict.discard) dictInner, a literal-dict field projection wrapping a beta-redex. - A monad-transformer bind reduces to Control.Bind.bind <dict>, but Control.Bind.bind is itself a top-level binding after linking, so the old peelAlias-based check resolved through it (into \dict -> dict.bind) and never matched the name. Replace the recognition with a MagicDo-style normaliser (headReducesToBind) that resolves aliases, projects literal-dictionary fields, and beta-reduces, but checks the Control.Bind.bind / Control.Bind.discard names before resolving so they act as stops. The literal-dictionary dict.bind path (Maybe/Either) is unchanged. Add runnable golden tests for a long State (get/put) and Either chain, and replace the synthetic discard unit test with one using the real discard-alias shape. Maybe/Either goldens are byte-identical; the full suite stays green. This closes the #104 acceptance gap for State.
Strengthen the recognition's coverage and pin the load-bearing correctness invariant, after the State surprise showed recognition was undertested. Monad matrix (runnable goldens, all flatten and load under stock Lua 5.1): - LongReaderBind: Reader (single-layer transformer, all bind) - LongWriterBind: Writer (all tell -> discard, monoid threading) - LongExceptBind: Except (short-circuit monad) - LongStackBind: StateT Int (Except String) -- a two-layer transformer stack, whose bind dictionary is itself built from nested instances; this is the multi-layer head shape no prior test exercised. Property tests (Hedgehog, 200 examples each) over randomly generated bind/ discard chains of varying length: free references preserved, bind/discard step count preserved, idempotence, and -- for long chains -- flattening fires and nesting drops. These guard the invariant the pass rests on (recognition only governs which chains are restructured, never correctness), independent of any particular monad's dictionary shape.
There was a problem hiding this comment.
Pull request overview
This PR addresses Lua 5.1’s parser nesting limit by (1) flattening deeply nested non-Effect/ST do/>>= chains at the IR level via lambda-lifting and (2) adding a post-codegen nesting-depth safety check that fails compilation with a clear error instead of emitting unloadable Lua.
Changes:
- Add
IR.FlattenDeepBindspass to lambda-lift long bind/discard chains into bounded-depth$kontNhelper segments. - Add
Lua.NestingCheckto detect excessive syntactic nesting in generated chunks and throwNestingTooDeep. - Add new goldens and specs covering long bind chains across several monads plus unit tests for both the flattener and the nesting detector.
Reviewed changes
Copilot reviewed 43 out of 59 changed files in this pull request and generated 7 comments.
Show a summary per file
| File | Description |
|---|---|
| test/ps/spago.dhall | Adds PS deps needed by new golden modules (Either/Transformers/Tuples). |
| test/ps/output/Golden.LongWriterBind.Test/golden.lua | New golden Lua output for long Writer bind chain. |
| test/ps/output/Golden.LongWriterBind.Test/eval/golden.txt | Expected runtime output for Writer eval golden. |
| test/ps/output/Golden.LongWriterBind.Test/eval/.gitignore | Ignores eval actual output for Writer golden. |
| test/ps/output/Golden.LongStateBind.Test/eval/golden.txt | Expected runtime output for State eval golden. |
| test/ps/output/Golden.LongStateBind.Test/eval/.gitignore | Ignores eval actual output for State golden. |
| test/ps/output/Golden.LongStackBind.Test/eval/golden.txt | Expected runtime output for stacked StateT/Except eval golden. |
| test/ps/output/Golden.LongStackBind.Test/eval/.gitignore | Ignores eval actual output for stacked golden. |
| test/ps/output/Golden.LongReaderBind.Test/golden.lua | New golden Lua output for long Reader bind chain. |
| test/ps/output/Golden.LongReaderBind.Test/eval/golden.txt | Expected runtime output for Reader eval golden. |
| test/ps/output/Golden.LongReaderBind.Test/eval/.gitignore | Ignores eval actual output for Reader golden. |
| test/ps/output/Golden.LongMaybeBind.Test/eval/golden.txt | Expected runtime output for Maybe eval golden. |
| test/ps/output/Golden.LongMaybeBind.Test/eval/.gitignore | Ignores eval actual output for Maybe golden. |
| test/ps/output/Golden.LongExceptBind.Test/golden.lua | New golden Lua output for long Except bind chain. |
| test/ps/output/Golden.LongExceptBind.Test/eval/golden.txt | Expected runtime output for Except eval golden. |
| test/ps/output/Golden.LongExceptBind.Test/eval/.gitignore | Ignores eval actual output for Except golden. |
| test/ps/output/Golden.LongEitherBind.Test/eval/golden.txt | Expected runtime output for Either eval golden. |
| test/ps/output/Golden.LongEitherBind.Test/eval/.gitignore | Ignores eval actual output for Either golden. |
| test/ps/golden/Golden/LongWriterBind/Test.purs | New golden PS module exercising long Writer do block. |
| test/ps/golden/Golden/LongStateBind/Test.purs | New golden PS module exercising long State do block. |
| test/ps/golden/Golden/LongStackBind/Test.purs | New golden PS module exercising long StateT-over-Except do block. |
| test/ps/golden/Golden/LongReaderBind/Test.purs | New golden PS module exercising long Reader do block. |
| test/ps/golden/Golden/LongMaybeBindModule/Test.purs | New module-mode golden to exercise IR/Lua output for long Maybe chain. |
| test/ps/golden/Golden/LongMaybeBind/Test.purs | New runnable golden for long Maybe do block. |
| test/ps/golden/Golden/LongExceptBind/Test.purs | New runnable golden for long Except do block. |
| test/ps/golden/Golden/LongEitherBind/Test.purs | New runnable golden for long Either do block. |
| test/Main.hs | Wires new specs into the test runner. |
| test/Language/PureScript/Backend/Lua/NestingCheck/Spec.hs | Adds unit tests for chunk depth metric and thresholding behavior. |
| test/Language/PureScript/Backend/IR/FlattenDeepBinds/Spec.hs | Adds unit + property tests for free-ref preservation, depth bounding, idempotence. |
| pslua.cabal | Exposes new library modules and includes new test modules. |
| lib/Language/PureScript/Backend/Lua/NestingCheck.hs | Implements nesting-depth measurement and limit check for Lua chunks. |
| lib/Language/PureScript/Backend/Lua.hs | Adds NestingTooDeep to the Lua backend error type. |
| lib/Language/PureScript/Backend/IR/Optimizer.hs | Inserts flattenDeepBinds into the optimized IR pipeline after magicDo. |
| lib/Language/PureScript/Backend/IR/MagicDo.hs | Updates docs to reference FlattenDeepBinds for the general case. |
| lib/Language/PureScript/Backend/IR/FlattenDeepBinds.hs | New IR pass implementing segmented lambda-lifting of deep bind/discard chains. |
| lib/Language/PureScript/Backend.hs | Runs nesting check post-codegen and throws Lua.NestingTooDeep on overflow. |
| exe/Main.hs | Adds CLI error rendering for NestingTooDeep. |
| docs/QUIRKS.md | Updates docs for long do blocks, remaining unflattened shapes, and new failure mode. |
💡 Add Copilot custom instructions for smarter, more guided reviews. Learn how to get started.
- FlattenDeepBinds.hs — index all group members (not just Standalone) in topLevel & letLocals so RecursiveGroup-bound bind/discard aliases resolve (r3452746991, r3452747082); + RecursiveGroup tests - NestingCheck.hs — parenthesise `1 + (a `max` b)` in IfThenElse/BinOp/VarIndex for clarity (already correct: max binds tighter than +) (r3452747127, r3452747161, r3452747188); + deeper-on-right guard test - docs/QUIRKS.md — correct the live-set bail threshold to ~15, not ~50 (r3452747232) - exe/Main.hs — broaden NestingTooDeep message beyond do/>>= chains, link #108 (r3452747267)
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.
Fixes #104.
Problem
A straight-line
do/>>=chain desugars to a right-nested tree of continuation closures,bind m1 (\x1 -> bind m2 (\x2 -> … last)). Past roughly 200 nesting levels Lua's parser refuses to load the chunk at all (chunk has too many syntax levels,LUAI_MAXCCALLS). On the JS/ES backends deep nesting is only a performance cost; on Lua it is a correctness failure, because the file never loads.#46 fixed this for
Effect/STvia magic-do: their computations are thunks, so a chain lowers to a flat statement sequence. That cannot work for an arbitrary monad, wherebind m kis an opaque call whose control flow lives insidebind(Maybe short-circuits, lists callkzero or more times, State threads context). #104 is the general case.The fix:
flattenDeepBindsA new IR pass, wired into
optimizedUberModuleright aftermagicDo(so by the time it runs, everyEffect/STchain is already aLetthunk and only other monads remain). It lambda-lifts a long bind chain: the chain is split into fixed-size segments, and each segment's continuation becomes a small named$kontNhelper whose free continuation variables are passed as explicit parameters. The result is a flatletof helpers wrapping a shallow body, so nesting no longer grows with chain length.This relocates closures and forwards their environment, but it never reorders, drops, or duplicates a
bind/kcall, so it is semantics-preserving for any monad, strict Lua included: the helper calls pass only variables, and binding a helper does not run its body. Recognition precision therefore only decides which expressions get restructured, not correctness.Two properties make the De Bruijn bookkeeping disappear:
renameShadowedNames, so every local is uniquely named. A helper reuses the chain's own binder names as its parameters, so references stay at index 0 with no shifting.countFreeRefson the built helper bodies: because a helper's call site passes its live variables explicitly, those variables show up as free references one level up and propagate through the chain automatically.When a cut's live set would exceed Lua's 60-upvalue cap (
LUAI_MAXUPVALUES) the pass bails and leaves the chain nested rather than emit a function that also will not load. Packing the environment into a single table to cut that to one upvalue is a possible later upgrade.Safety net:
NestingCheckA post-codegen check in
Backend.compileModulesmeasures the chunk's maximum nesting depth and rejects it with a clearNestingTooDeeperror when it crosses a conservative threshold, instead of writing out Lua that no interpreter can load. The metric mirrors the recursive-descent parser: it counts function bodies, call arguments, and operators, but not the iterative spine of a curried call. This catches whateverflattenDeepBindsbails on, plus the deep-nesting shapes that are not flattened yet (see Scope below).Tests
Golden.LongMaybeBind: a runnable 300-stepMaybedoblock whose final result reads the first bound variable, forcing it through every lifted helper. The eval oracle is(Just 301). Without the fix the generated Lua fails to load; with it, stock Lua 5.1 runs it.Golden.LongMaybeBindModule: the same chain in module mode (nomain), which exercises the IR/Lua goldens.The generated
golden.lualoads and runs under stock Lua 5.1.5; max nesting is 43 against the ~200 cap. No existing golden changed.Scope
This handles
do/bindchains. Still not flattened, and now reported by the detector instead of silently breaking: applicative chains (ado/apply,bindFlipped), chains whose live set exceeds the upvalue budget, and deep nesting from non-bindconstructs (largecasetrees, long<>concatenations, wide literals). A general Lua-AST-level nesting breaker covering those is filed separately.