# V4004 match_too_large

URL: /docs/errors/V4004
Markdown: /docs/errors/V4004.md

> 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:

```sakura
match (a, b, c, d, e) { (L, L, L, L, L) => true, _ => false }
```

Fixed:

```sakura
fn small(x: Int) -> Bool { match x { L => true, _ => false } }
small(a) && small(b) && small(c) && small(d) && small(e)
```

## Wrong program [#wrong-program]

[`compiler/tests/ui/V4004_match_too_large.sak`](https://github.com/icantcodefyi/sakuralang/blob/main/compiler/tests/ui/V4004_match_too_large.sak), which the compiler's ui suite runs through `sakura build`:

```sakura
// 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 [#fixed-program]

[`compiler/tests/ui/V4004_match_too_large.fixed.sak`](https://github.com/icantcodefyi/sakuralang/blob/main/compiler/tests/ui/V4004_match_too_large.fixed.sak), which `sakura build` accepts with no diagnostics:

```sakura
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)}") }
```