Problem
matchChosenByHeuristic (lib/Language/PureScript/Backend/IR.hs) picks which outstanding pattern test of a clause the decision tree emits next, scoring candidates with Maranget's pbaN composite (#311). It never consults MatchHistory — the per-path record of already-performed tests that mkClause applies after the pick to prune tests whose outcome is decided. On such a path a decided match is free to pick: a known-true match just continues the clause, a known-false one falls through to the next clause, neither emits anything. But the heuristic can tie-break to a fresh test instead, and the fresh test gets emitted even when the clause is already doomed by its decided sibling — producing a test whose success branch is immediately the no-match failure.
The pbaN unit test ("tests the column with fewer distinct patterns first", test/Language/PureScript/Backend/IR/Spec.hs) exhibits one. Matrix: 'a','p' -> 1 | 'b','p' -> 2 | 'c','p' -> 3 | 'd','p' -> 4 | 'a','q' -> 5. In the branch where 'p' == 'y' has already failed, the clause ('d','p') ties on all pbaN components (needed prefix 2 vs 2, distinct patterns 2 vs 2, sub-tests 0 vs 0) and leftmost picks the fresh 'd' == 'x' — although the clause's other match 'p' == 'y' is known false on this path, so the clause cannot succeed regardless. The asserted tree carries the resulting arm verbatim:
( ifThenElse
(literalChar 'd' `eq` literalChar 'x')
(exception "No patterns matched")
...A test whose success arm is the failure. With the decided match picked first, the clause is dismissed for free and that branch shrinks from 3 tests ('d'=='x', 'a'=='x', 'q'=='y') to 2.
Approach
Thread the current MatchHistory into the pick (it lives in mkClause, which already partially applies the heuristic over the remaining clauses): before pbaN scoring, take any outstanding match whose testOutcome under the history is TestKnownTrue or TestKnownFalse — emitting it costs nothing and it may discharge or dismiss the clause outright. Only undecided matches are scored with pbaN. Tree construction and the pruning in testFocus stay as they are; the pruning simply gets consulted one step earlier.
Prerequisites / Relations
Independent; refines the column choice merged in #311 without changing the composite itself. Orthogonal to #184 (extending MatchHistory with negative knowledge for literals): #184 makes the history richer, this makes the pick aware of it — they compose.
Verification / Measurement
The pbaN unit test's negative branch loses the if 'd'=='x' then exception arm (expected tree updated to the 7-test shape, red before the change). Eval goldens across the corpus stay unchanged (only tree shape may move); structural golden churn reviewed for shrinkage. Code-size and counter deltas through the bench harness (#172).
Problem
matchChosenByHeuristic(lib/Language/PureScript/Backend/IR.hs) picks which outstanding pattern test of a clause the decision tree emits next, scoring candidates with Maranget'spbaNcomposite (#311). It never consultsMatchHistory— the per-path record of already-performed tests thatmkClauseapplies after the pick to prune tests whose outcome is decided. On such a path a decided match is free to pick: a known-true match just continues the clause, a known-false one falls through to the next clause, neither emits anything. But the heuristic can tie-break to a fresh test instead, and the fresh test gets emitted even when the clause is already doomed by its decided sibling — producing a test whose success branch is immediately the no-match failure.The pbaN unit test ("tests the column with fewer distinct patterns first",
test/Language/PureScript/Backend/IR/Spec.hs) exhibits one. Matrix:'a','p' -> 1 | 'b','p' -> 2 | 'c','p' -> 3 | 'd','p' -> 4 | 'a','q' -> 5. In the branch where'p' == 'y'has already failed, the clause('d','p')ties on all pbaN components (needed prefix 2 vs 2, distinct patterns 2 vs 2, sub-tests 0 vs 0) and leftmost picks the fresh'd' == 'x'— although the clause's other match'p' == 'y'is known false on this path, so the clause cannot succeed regardless. The asserted tree carries the resulting arm verbatim:( ifThenElse (literalChar 'd' `eq` literalChar 'x') (exception "No patterns matched") ...A test whose success arm is the failure. With the decided match picked first, the clause is dismissed for free and that branch shrinks from 3 tests (
'd'=='x','a'=='x','q'=='y') to 2.Approach
Thread the current
MatchHistoryinto the pick (it lives inmkClause, which already partially applies the heuristic over the remaining clauses): before pbaN scoring, take any outstanding match whosetestOutcomeunder the history isTestKnownTrueorTestKnownFalse— emitting it costs nothing and it may discharge or dismiss the clause outright. Only undecided matches are scored with pbaN. Tree construction and the pruning intestFocusstay as they are; the pruning simply gets consulted one step earlier.Prerequisites / Relations
Independent; refines the column choice merged in #311 without changing the composite itself. Orthogonal to #184 (extending
MatchHistorywith negative knowledge for literals): #184 makes the history richer, this makes the pick aware of it — they compose.Verification / Measurement
The pbaN unit test's negative branch loses the
if 'd'=='x' then exceptionarm (expected tree updated to the 7-test shape, red before the change). Eval goldens across the corpus stay unchanged (only tree shape may move); structural golden churn reviewed for shrinkage. Code-size and counter deltas through the bench harness (#172).