V4004 match_too_large
A match compiles to a decision tree of more than 1,048,576 nodes (tests and leaves, counting the rows its or-patterns expand into), so the compiler stops building it (design §17.193).
An error from the pattern phase. sakura explain V4004 prints this explanation offline.
A match compiles to a decision tree of more than 1,048,576 nodes (tests and leaves, counting
the rows its or-patterns expand into), so the compiler stops building it (design §17.193). The
count is a function of the source alone. The number of arms is not limited: a flat match of
thousands of literals or constructors stays far under the budget. The tree grows with the
product of the alternatives when several columns are each matched by or-patterns, and when rows
with wildcards are copied into every branch of the columns tested before them; a match in a
guard counts toward the enclosing one, once for each branch the guard's row reaches. Test one column
at a time, or move the rows with wildcards first. Core lowering counts the tree, so sakura build,
run and test report it and sakura check does not. Below, L stands for 1 | 2 | … | 20, so the
wrong match has a row for each of 20^5 combinations.
Wrong:
match (a, b, c, d, e) { (L, L, L, L, L) => true, _ => false }Fixed:
fn small(x: Int) -> Bool { match x { L => true, _ => false } }
small(a) && small(b) && small(c) && small(d) && small(e)Wrong program
compiler/tests/ui/V4004_match_too_large.sak, which the compiler's ui suite runs through sakura build:
// Every combination of the five or-patterns is a row, 20^5 of them, and the wildcard rows
// around them are copied into the branches: past the budget.
fn inside(a: Int, b: Int, c: Int, d: Int, e: Int) -> Bool {
match (a, b, c, d, e) {
(0, _, _, _, _) => false,
(1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20, 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20, 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20, 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20, 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20) =>
true,
(_, 0, _, _, _) => false,
_ => false,
}
}
pub fn main() -> Unit ! {Console} { Console.print("{inside(1, 2, 3, 4, 5)}") }sakura build reports V4004.
Fixed program
compiler/tests/ui/V4004_match_too_large.fixed.sak, which sakura build accepts with no diagnostics:
fn small(x: Int) -> Bool {
match x {
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 =>
true,
_ => false,
}
}
fn inside(a: Int, b: Int, c: Int, d: Int, e: Int) -> Bool {
small(a) && small(b) && small(c) && small(d) && small(e)
}
pub fn main() -> Unit ! {Console} { Console.print("{inside(1, 2, 3, 4, 5)}") }V4003 or_pattern_bindings
All alternatives of an or-pattern must bind the same names with the same types (design §3.2).
V5001 impure_contract
Predicates in where, requires, ensures and property bodies must be pure, terminating and deterministic: no loops, no recursion, and calls only to @total functions in the contract subset (design §7.1).