feat(ir): accumulate match history, prune literal retests - #263
Merged
Conversation
The new Golden.CasePruning.Test module produces, with the current pipeline, the three redundant shapes issue #184 targets: a literal retest whose outcome is already decided on both paths (literalRetest, the Data.String.CodePoints.codePointAt shape), a constructor-tag retest surviving because the single-slot history forgot the first of two accumulated negatives (ctorRetest), and its literal twin (literalNegatives). The eval oracle is hand-verified; the structural goldens pin the dead retests so the pruning commit that follows shows their removal as a diff.
Generalize the case decision-tree compiler's MatchHistory from a single most-recent constructor slot per scrutinee (Map Exp (CtorName, Bool)) to accumulated knowledge of every emitted test (Map Exp (Map Pattern Bool)), and route the literal patterns — integer, float, string, char, boolean, array length — through the same consult-then-remember step (testFocus) that constructor tags used. A test already decided on the current path is pruned instead of re-emitted: one known to have passed proceeds straight to the next match; one known to have failed — recorded negatively, or excluded by a mutually exclusive sibling that passed (a different tag of the same type, a different literal of the same kind, a different array length) — falls through to the next clause. Accumulation fixes the lossy single slot: after two tags fail on one scrutinee, a retest of the first is now recognized as dead. A ProductType tag test is a tautology, so it stops recording anything; no test can consult the record. Mutual exclusion of distinct literals is sound at the Lua level: PureScript Int literals are 32-bit (exact in Lua 5.1 doubles), and the printer's show-roundtrip float text keeps distinct Doubles distinct. Accepted golden diffs: Data.String.CodePoints.codePointAt loses the nested 0 == v retest with its dead then-branch (the issue's repro), Golden.PatternMatching.Test2 loses a dead Zero retest after two accumulated negatives, Golden.CaseStatements shifts only generated name counters, and the Golden.CasePruning.Test trees collapse to their minimal forms. The two-binder unit test expectation loses the branch now excluded by a positive sibling test. No eval oracle changed.
Contributor
There was a problem hiding this comment.
Pull request overview
This PR improves the PureScript CoreFn → IR case decision-tree compiler by extending match-history pruning from constructor-tag tests to all emitted tests (constructor tags, literal equalities, and array-length checks), and by accumulating multiple outcomes per scrutinee so negative knowledge is not overwritten.
Changes:
- Generalize
MatchHistoryto store per-scrutinee outcomes for multiple pattern tests, enabling pruning of repeated or mutually-exclusive tests. - Route literal and array-length patterns through the same consult/remember pruning path used for constructor-tag tests.
- Add/refresh golden coverage (including a new focused
Golden.CasePruning.Test) and update expected IR-spec output to reflect the new pruning behavior.
Reviewed changes
Copilot reviewed 15 out of 15 changed files in this pull request and generated no comments.
Show a summary per file
| File | Description |
|---|---|
| lib/Language/PureScript/Backend/IR.hs | Extends match-history pruning to literals/array length; accumulates outcomes and prunes known tests. |
| test/Language/PureScript/Backend/IR/Spec.hs | Updates expected IR for multi-binder case compilation where a now-redundant literal retest is pruned. |
| test/ps/src/Golden/CasePruning/Test.purs | Adds a targeted PureScript repro module covering literal retests and accumulated negative constructor knowledge. |
| test/ps/output/Golden.CasePruning.Test/corefn.json | Adds CoreFn artifact for the new golden module. |
| test/ps/output/Golden.CasePruning.Test/golden.ir | Adds IR golden output demonstrating pruning behavior for the new module. |
| test/ps/output/Golden.CasePruning.Test/golden.lua | Adds Lua golden output showing pruned decision trees for the new module. |
| test/ps/output/Golden.CasePruning.Test/eval/golden.txt | Adds eval oracle for the new golden module (expected stdout). |
| test/ps/output/Golden.CasePruning.Test/eval/.gitignore | Ignores runtime-produced eval actual.txt for the new golden module. |
| test/ps/output/Golden.StringCodePoints.Test/golden.ir | Updates golden IR to remove redundant literal retests and adjust generated bindings accordingly. |
| test/ps/output/Golden.StringCodePoints.Test/golden.lua | Updates golden Lua for codePointAt to remove redundant nested 0 == v retest and dead branch. |
| test/ps/output/Golden.PatternMatching.Test2/golden.ir | Updates golden IR where accumulated negative tag knowledge prunes a now-dead constructor retest. |
| test/ps/output/Golden.PatternMatching.Test2/golden.lua | Updates golden Lua to remove the pruned Zero retest branch. |
| test/ps/output/Golden.CaseStatements.Test/golden.ir | Updates golden IR where only generated-name indices shift (structurally equivalent output). |
| test/ps/output/Golden.CaseStatements.Test/golden.lua | Updates golden Lua where only generated-name indices shift (structurally equivalent output). |
| changelog.d/20260713_134500_unisay_case_history_pruning.md | Adds changelog entry describing the expanded pruning behavior and its effect on redundant retests. |
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.
Closes #184.
The case decision-tree compiler already pruned redundant constructor-tag tests through
MatchHistory, but every literal pattern (integer, float, string, char, boolean, array length) emitted itseqtest unconditionally, and the history held a single most-recent slot per scrutinee, so negative knowledge was lost for sum types with three or more constructors. The repro from the issue isData.String.CodePoints.codePointAt, whose compiled golden re-tested0 == vin both branches of a test that had already decided it.This PR generalizes
MatchHistoryfromMap Exp (CtorName, Bool)toMap Exp (Map Pattern Bool)and routes all literal patterns through the same consult-then-remember step (testFocus) that constructor tags used. A test whose outcome the history already decides is pruned instead of re-emitted: a known-positive proceeds straight to the next match, and a known-negative (recorded directly, or implied by a mutually exclusive sibling that passed: a different tag of the same type, a different literal of the same kind, a different array length) falls through to the next clause. Since aProductTypetag test is a tautology and nothing can consult its record, it stops recording anything.Mutual exclusion of distinct literals is sound at the Lua level: PureScript
Intliterals are 32-bit and therefore exact in Lua 5.1 doubles, and the printer's show-roundtrip float text keeps distinctDoubles distinct.The first commit pins the pre-pruning decision trees in a new
Golden.CasePruning.Testmodule (thecodePointAtshape, a constructor-tag retest that survives only because the single slot forgot the first of two negatives, and its literal twin), so the second commit shows the pruning as a golden diff. Accepted diffs elsewhere:Data.String.CodePoints.codePointAtloses the nested0 == vretest with its dead then-branch,Golden.PatternMatching.Test2loses a deadZeroretest after two accumulated negatives, andGolden.CaseStatementsshifts only generated name counters. No eval oracle changed. The full suite passes, and the randomized specs also ran green on several seeds.