Compiling Pattern Matching

Read a match literally and you get: try arm one; if it does not fit, try arm two; and so on. Compile it literally and you get a chain of tests in which the same discriminant is loaded and compared over and over. For a five-arm match on an enum, the last arm costs five loads and five comparisons, and the shape is linear in the number of arms.

That is not what any production compiler generates, and the reason is that testing a tag is *pure*. Nothing is observable about having compared a discriminant against a value, so the compiler is free to test it once and branch on the result — a jump table, or a balanced comparison tree, or a bit test, depending on density. What was linear becomes one test.

Nested patterns are where it gets interesting. Some(Ok(x)) versus Some(Err(e)) versus None looks like three independent tests of the whole value; a decision tree tests the outer Option tag once, and only inside the Some branch tests the inner Result tag. Each discriminant is examined exactly once on any path from root to leaf, which is the property the whole algorithm exists to establish.

The standard algorithm — Maranget's, which is what most modern implementations use in some form — treats the arms as a matrix. Each row is an arm; each column is a position within the scrutinee. Compilation is recursive: pick a column, split the matrix into one sub-matrix per constructor that appears in it, recurse on each, and emit a test that branches between them.

Two rules make it terminate and stay correct. A row whose pattern in the chosen column is a wildcard belongs in *every* sub-matrix, because a wildcard accepts every constructor. And when a constructor is selected, the row expands: Some(p) in that column is replaced by p in a new column for the payload. The matrix therefore changes shape as the tree is built, which is why the algorithm is written over matrices rather than over the source arms.

Which column to pick first is the whole art. Picking left to right is correct and often bad. The standard heuristics prefer a column with no wildcards — because a wildcard row must be duplicated into every branch, and duplication is how the tree explodes — and among those, the column with the fewest distinct constructors, or the one whose test is cheapest. Different compilers use different heuristic stacks and get measurably different code from the same source.

This is also where the second implementation strategy appears. A *backtracking automaton* keeps the source order literally and re-tests on failure: smaller code, potentially repeated tests. A decision tree tests each column once and can duplicate rows: faster code, potentially much larger. Neither dominates, and some compilers switch between them based on the size of the result.

The tree below is what the three arms compile to. Read it as a program: each internal node is one test on one sub-value, each edge is an outcome of that test, and each leaf is an arm body. Every path from root to leaf tests value.tag exactly once and tests value.payload.tag at most once.

Notice that the tree has no notion of arm order. Order is baked in during construction — when two rows could both accept a value, the earlier one wins and the later one is simply absent from that leaf — so the generated code contains no evidence of the source ordering at all. That is why the semantic rule ("first matching arm") and the implementation ("test each discriminant once") are not in tension: the ordering is resolved at compile time.

And notice what the leaves cost: nothing. Once a leaf is reached, the arm body runs with its bindings already computed as projections of the scrutinee — x is value.payload.payload, known statically at that leaf. No search, no re-test, no dispatch.

A guard is the one thing that cannot be moved. It is arbitrary code with arbitrary effects, so it may only run once every earlier arm has been ruled out, and if it evaluates false, matching must continue exactly as if the arm had not matched. In tree terms a guarded leaf is not a leaf: it is a test whose false edge must rejoin the search at the right place, which usually means duplicating the remaining decision tree or falling back to a shared failure block. This is why a match whose arms are all guards compiles to something very close to the if-chain it resembles — the compiler has no freedom left.

Or-patterns and wildcards are the other source of growth. A row with a wildcard in the chosen column belongs in every sub-matrix, so it is duplicated once per constructor; do that at several levels and the tree size can grow exponentially in the depth of the patterns. Real implementations bound this: they share identical subtrees (the tree becomes a DAG), they fall back to a backtracking automaton past a size threshold, and their column heuristics exist largely to avoid the duplication in the first place.

The practical consequence is that match compilation has a *size* failure mode as well as a speed one, and the two pull against each other. A compiler that always built the ideal decision tree would occasionally emit enormous functions; one that always backtracked would emit small, slow code. Which you get for a given match is a heuristic outcome, which is why it is worth looking at the generated code for a match that sits in a hot loop rather than assuming.

The surface half of matching — what patterns can express, what a guard is, why guards do not count toward coverage — is [[pattern-matching]], and the proof that no case is missing is [[exhaustiveness-checking]]. Both are frontend concerns and both are about what the checker can conclude.

This lesson is the point where that ordered list of arms stops being a specification and becomes code, and it belongs with closures and coroutines because it is the same kind of move: a construct the source treats as primitive is rewritten into tests and branches the back end already knows. The interesting content is entirely in what the rewrite is free to change (test order, sharing, representation) and what it must not (arm order, guard order, evaluation of guards).

It also shares an algorithm with its neighbour, which is the tidiest fact in this part of the domain. The usefulness analysis that decides whether an arm is reachable, and the exhaustiveness check that decides whether a case is missing, are the same matrix computation run for a different purpose. One compiler component, three outputs: a warning about an unreachable arm, an error naming an uncovered value, and a decision tree.