Type Designimplementation

Pattern Matching

Matching is the elimination form for a sum type: it inspects the tag and binds the payload in one construct. Destructuring, guards, nested patterns and bindings are the surface; the decision tree the compiler builds from it is a separate subject.

The question

What does match give me that a chain of if statements and field accesses does not?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute

What the program is here

A match expression over a scrutinee whose static type is (usually) a closed sum, plus an ordered list of arms. Each arm holds a pattern — a tree of constructors, literals, bindings and wildcards — an optional guard, and a body. The checker types every pattern against the scrutinee type, collects the bindings each one introduces, and checks the arms against each other for reachability. Compilation of this list into a decision tree is a separate phase and belongs to [[pattern-matching-compilation]].

What this phase may assume or do

A pattern is well-typed only if its constructor belongs to the scrutinee's type and its sub-patterns type against the corresponding payload fields. A name may be bound in an or-pattern only if every alternative binds it at the same type and the same binding mode. Arms are tried in source order, so a later arm is reachable only if some value escapes every earlier one — and a guard, because the checker cannot evaluate it, never counts toward covering a case even when it obviously does.

Key points

Matching is the elimination form for a sum: it tests the tag and binds the payload in a single construct so the two cannot drift apart.
Patterns are trees of constructors, literals, bindings and wildcards, and they nest arbitrarily — five conditions in one expression rather than five nested ifs.
A binding is in scope only in its arm, and only where the tag that justifies it has already been established.
Guards express what patterns cannot, and never count toward exhaustiveness, because the checker cannot evaluate them.
Or-patterns require every alternative to bind the same names at the same types.
Arms are tried in source order; which underlying tests run first is the compiler's choice, so a side-effecting guard is not something to rely on.
Matching without a closed variant set is destructuring syntax; matching over a closed set is a proof the compiler can check.

Matching is the elimination form

For every way of building a value there is a corresponding way of taking one apart. Products are built with a constructor and taken apart by field access. Sums are built with a variant constructor and taken apart by matching — and matching is not one of several options, it is the operation that corresponds to the way the value was built. That is why languages with good sum types invariably have a match construct: without it the sum type is inert.

The alternative construction — test the tag with an if, then reach into the payload — separates the test from the extraction. Those two steps can drift: the test can say Circle and the extraction reach for w. A match keeps them in one place, so the binding is only in scope where the tag has already been checked, and there is no expressible way to get it wrong.

That single property does most of the work. Everything else in this lesson — guards, nesting, or-patterns, bindings — is convenience layered on top of "the test and the extraction happen together, and the compiler checks they agree".

The same logic, tested-then-extracted versus matched

1// Test and extraction separated: two places to keep in sync.
2if shape.is_circle() {
3    let r = shape.as_circle_unchecked().r;   // nothing checks this agrees with the test
4    area = PI * r * r;
5}
6 
7// Match: the binding exists only where the tag has been established.
8let area = match shape {
9    Shape::Circle { r } => PI * r * r,
10    Shape::Rect { w, h } => w * h,
11    Shape::Empty => 0.0,
12};

In the second form r does not exist outside its arm, and no arm can name a field the tag does not imply. The compiler is not being asked to trust anything.

Patterns are trees, and they nest

A pattern is not a tag name — it is a tree, mirroring the structure of the value. Some(Ok(Point { x: 0, y })) matches a value only if the outer Option is Some, the inner Result is Ok, the payload is a Point, its x field equals zero, and it binds the y field. That is five separate conditions expressed in one expression, and the alternative is five nested if statements plus four intermediate bindings whose names nobody agrees on.

Nesting is where matching stops being a nicer switch and becomes a different thing. A protocol handler that must distinguish "authenticated request for a resource the user owns" from "authenticated request for one they do not" from "unauthenticated" is naturally three nested tags, and the nested pattern says exactly that in three lines with no intermediate state.

Bindings can appear at any depth, and most languages provide an at-pattern (name @ subpattern in Rust, name as pattern in OCaml) to bind the whole while also destructuring it. Or-patterns (A | B => ...) let several shapes share an arm, subject to the rule in the legality condition: every alternative must bind the same names at the same types, or the body would not know what it has.

The pattern Some(Ok(Point { x: 0, y })) as the checker sees it

AST — only what later phases match on

Constructor Some“Some(...)”— Tests the Option tag. Fails immediately on None.

└── Constructor Ok“Ok(...)”— Tests the Result tag inside the Some payload.

└── Struct Point“Point { x: 0, y }”

├── Literal 0 (field x)“x: 0”— A test, not a binding. Compares by equality.

└── Binding y (field y)“y”— A binding, not a test. Always succeeds and introduces `y` into the arm body.

Read it asEvery leaf is either a test or a binding, and the checker types each one against the payload type at that position. Note that the tree has no notion of order or efficiency — deciding which test to perform first is the compiler's job, and doing it well is exactly the subject of [[pattern-matching-compilation]].

Guards, and the thing guards cannot do

specThat guards do not contribute to exhaustiveness is a rule of the language, not a limitation of a particular compiler: Rust, OCaml, Haskell and Scala all specify it the same way, because any other choice would require deciding arbitrary boolean expressions. What differs is the diagnostic — Rust names an uncovered range, OCaml and Haskell print a witness value, and Scala reports a warning rather than an error unless the scrutinee is sealed.

A guard is an arbitrary boolean expression attached to an arm: Some(n) if n > 100 => .... It runs after the pattern has matched and the bindings are in scope, and if it is false the match continues to the next arm. Guards are what let matching express conditions the pattern language cannot — comparisons, calls, anything.

The important consequence is stated in the legality condition and gets people every time: a guard never contributes to exhaustiveness. Writing Some(n) if n >= 0 and Some(n) if n < 0 covers every integer, obviously, and the compiler will still demand a third arm. It is not being pedantic — it cannot evaluate arbitrary expressions, so it has exactly two options, and assuming the guards are complete would make the check unsound.

The corollary is that a guard can also make an arm you believed unreachable reachable, and vice versa, which is why reachability warnings interact with guards in ways that surprise people. If you need the coverage to be checked, encode the distinction in the pattern — match on a range pattern rather than a guarded comparison where the language supports it.

The second thing guards cannot do is control evaluation order in a way you can rely on. Arms are tried in source order in every mainstream implementation, but which *tests* within a set of arms run first is up to the decision-tree builder, and a guard is a side-effecting expression sitting in the middle of that. A guard with a side effect is a bug waiting for a compiler upgrade.

Guards cover values but not the exhaustiveness check

1match n {
2    x if x >= 0 => "non-negative",
3    x if x <  0 => "negative",
4    // error[E0004]: non-exhaustive patterns: `i32::MIN..=i32::MAX` not covered
5}
6 
7// Encode it in the pattern instead, and the check succeeds:
8match n {
9    0.. => "non-negative",
10    _   => "negative",
11}

The two guards are exhaustive to any reader and to no checker. The rewrite moves the distinction from an expression the compiler cannot evaluate into a pattern it can.

The same idea in languages that added it late

Pattern matching is now spreading into languages that were designed without it, and the retrofits are instructive because each had to choose which half to keep. Python 3.10 added structural pattern matching with match/case, including class patterns and mapping patterns — but Python has no closed sum types, so there is nothing to be exhaustive over and the construct is a destructuring dispatch rather than a proof. C# added type patterns, property patterns and switch expressions, and gets exhaustiveness only for the cases where the compiler can see a closed hierarchy. Java added pattern matching for switch alongside sealed classes, and it is the sealing that makes the check possible.

That correlation is the lesson. Matching without a closed set is a syntax improvement; matching over a closed set is a proof obligation the compiler can discharge. If you are evaluating a language's pattern matching, the question to ask is not what the patterns can express but whether anything makes the variant set closed — because that is what determines whether [[exhaustiveness-checking]] is available, and that is the feature that actually changes how code ages.

JavaScript has destructuring assignment, which is the binding half without the testing half, and a pattern matching proposal that has not landed. TypeScript therefore reaches the effect through a switch on a discriminant field, which works because the checker special-cases exactly that shape — see [[union-types]].

What each language's matching actually buysimplementation

Language	Patterns available	Closed variant set?	Exhaustiveness
Rustspec	Constructors, literals, ranges, or-patterns, bindings, guards, slices	Yes — `enum` is closed	Enforced as an error
OCaml / Haskellimplementation	Constructors, literals, nested, or-patterns, guards	Yes — declared constructors	Warning by default, error under a flag
Scala 3implementation	Constructors, types, extractors, guards	Only for `sealed`/`enum`	Warning for sealed hierarchies
Java 21+implementation	Type patterns, record patterns, guards	Only for `sealed`	Error for sealed hierarchies in a switch
C#implementation	Type, property, positional, relational patterns	Rarely — hierarchies are open	Compiler warns where it can prove it
Python 3.10+spec	Class, mapping, sequence, value patterns, guards	No	None — a fallthrough is silent
TypeScriptimplementation	No match construct; `switch` on a literal discriminant	Yes, for a declared discriminated union	By the `never` idiom, opt-in per site

How it works

The steps, in the order the compiler takes them.

The parser builds each arm's pattern as a tree; the checker walks it against the scrutinee type, resolving constructor names in the type's namespace rather than the value namespace.
For each pattern the checker collects the bindings it introduces with their types, and validates that or-pattern alternatives agree on the set, the types and the binding modes.
Arm bodies are checked in an environment extended with that arm's bindings; the match's own type is the join of the arm body types.
A usefulness analysis runs over the arms in order: an arm is reported unreachable if the values it accepts are all accepted by earlier arms, and the same analysis run against the full value set produces the exhaustiveness result — see [[exhaustiveness-checking]].
Guards are checked as ordinary boolean expressions in the arm's environment and are excluded from both analyses.
Lowering then turns the ordered arm list into a decision tree or a backtracking automaton, choosing which discriminant to test first — the subject of [[pattern-matching-compilation]], not of this lesson.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

A guarded pair of arms covers every value to any reader and the compiler still demands a wildcard; the engineer adds _ => unreachable!() and a later refactor makes it reachable, turning a compile-time check into a runtime panic.
A guard performs a side effect — increments a counter, logs, takes a lock — and the effect happens a different number of times after a compiler upgrade reorders the underlying tests, producing a metric that drifts with no code change.
An or-pattern alternative binds a name the other alternative does not; the error message names the binding rather than the alternative, and the engineer moves the binding rather than splitting the arm.
A deeply nested pattern silently stops matching after a field is renamed in an inner struct, because the arm still type-checks against a different constructor path and falls through to a later arm.
A Python match falls through every case with no error and the function returns None; the failure appears as a null-ish value several layers away, with nothing at the match site to indicate a case was missed.

When it helps

Any dispatch over a sum type, which is to say every parser, interpreter, protocol handler and state machine.
Destructuring nested data where the alternative is a chain of checks and intermediate bindings that must be kept consistent by hand.
Refactoring: when the shape of the data changes, every match arm that no longer type-checks is a site that genuinely needed attention.
Making the set of cases visible in one place, which is what makes a reviewer able to ask "what about X" and get an answer from the code.

When it hurts

Over an open hierarchy, where matching on concrete types re-implements virtual dispatch badly and breaks whenever a new subtype appears.
When arms grow large. A match with six arms of thirty lines each is a function that should have been six functions; the construct makes the sprawl comfortable.
When guards do the real work. A match whose arms are all wildcards with guards is an if/else chain with extra syntax and no coverage checking.
In a language where the construct exists without closed sums, where it can create the impression of a checked dispatch that is not checked at all.

What it costs

Every one of these is paid by something.

Combining the test and the binding buys the impossibility of a mismatched extraction and costs expressiveness at the edges: anything the pattern language cannot say has to move into a guard, which is then invisible to every analysis.
Source-ordered arms buy a simple, predictable reading and cost the compiler its freedom to reorder — a decision-tree builder must preserve the observable order of guards, which constrains the code it can generate.
Rich patterns (ranges, slices, or-patterns, at-bindings) buy concision and pay in implementation surface and diagnostic quality: the usefulness algorithm has to understand every pattern form, and the witness it prints for a missing case gets harder to render as the forms multiply.
Making matching the primary dispatch mechanism buys a place where all cases are visible and pays the expression-problem price: adding a case means editing every match, where a virtual method would have required editing nothing.

What else you could do

What a different compiler or language does instead, and when that is better.

Virtual dispatch — put a method on each variant and call it. Adding a variant then touches nothing else, at the cost of the operation being spread across the type hierarchy instead of visible in one place. Correct when variants are stable and operations grow.
The visitor pattern gives a match-like exhaustive dispatch in a language without matching, at the cost of substantial boilerplate and an indirection that obscures the control flow — see [[visitor-pattern]] for its role as the standard shape of a compiler pass.
A tag switch plus manual field access is what C and Go offer. It works and is fast; the tag and the extraction are simply not checked against each other, so the discipline is on the author.
Predicate dispatch and multimethods (Clojure, Julia, CLOS) generalise matching to dispatch on arbitrary predicates over several arguments, which is more expressive and gives up any hope of static exhaustiveness.

See it for yourself

The flag, dump or tool that shows you this directly.

rustc reports uncovered patterns as E0004 with a witness; cargo build output is the primary tool, and #[deny(unreachable_patterns)] turns the reachability warning into an error.
ghc -Wincomplete-patterns -Wincomplete-uni-patterns turns Haskell's exhaustiveness warnings on — they are not on by default, which surprises people.
ocamlc -w +8 enables the partial-match warning; the compiler prints a concrete value that would not be matched.
To see the generated decision tree rather than the source form: rustc --emit=mir shows the SwitchInt terminators the match became, and ghc -ddump-simpl shows the nested case expressions.
For Python, dis.dis on a function containing match shows the sequence of comparisons and jumps directly — and shows that nothing checks for a missing case.

Plausible wrong readings

Stated the way a confident engineer states them.

"match is just a nicer switch." A switch compares a value against constants. A match tests a tree of constructors, binds payloads, and is checked for coverage — the last of which is the part that changes how code ages.
"My two guards cover everything, so the compiler should accept it." The compiler cannot evaluate your guards, and a checker that assumed guards were complete would be unsound. Move the distinction into the pattern if you want it checked.
"Arms are tried top to bottom, so I know exactly which comparisons run." You know the observable order of guards and arm bodies. Which tag tests the compiler performs, and in what order, is a code-generation decision.
"Python has pattern matching now, so it has the same guarantees." It has the patterns and not the closed variant set, so a missing case is silent. The guarantee came from the type system, not from the syntax.

Misconceptions

The claim, and what is actually true.

Pattern matching is slow because it tests every arm.

A compiler builds a decision tree that tests each discriminant once where it can. The naive left-to-right, arm-by-arm reading is the semantics, not the implementation.

Destructuring and pattern matching are the same feature.

Destructuring binds parts of a value whose shape is already known. Matching also tests which shape it is, and chooses a branch. JavaScript has the first and not the second.

A wildcard arm is a harmless default.

It is the mechanism by which a newly added variant becomes silently unhandled. It is sometimes correct and always worth a deliberate decision — see [[exhaustiveness-checking]].

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

A match looks at a value, works out which variant it is, pulls the pieces out, and runs the matching branch — all in one construct. The pieces are only in scope in the branch where the variant has been established, so you cannot accidentally read a field that is not there. Patterns nest, so several layers of that check happen in one expression.

practical

Three habits. Prefer a pattern to a guard whenever the language can express the distinction, because only the pattern is visible to the coverage check. Keep arms short — if an arm is more than a few lines, call a function named after the case, so the match stays a table of cases rather than a wall of logic. And never put a side effect in a guard: guards may be evaluated as part of a decision tree whose test order is the compiler's to choose, and the number of times yours runs is not something to build on.

advanced

The interesting design tension in matching is between expressiveness and analysability, and every feature sits somewhere on it. Constructor patterns are fully analysable — the usefulness algorithm understands them and produces witnesses. Range and literal patterns are analysable with more work, which is why languages add them late. Guards are not analysable at all, and view patterns or active patterns (F#, Scala extractors) are guards wearing a constructor's clothes: they look like patterns, they nest like patterns, and they are opaque to coverage checking because they run arbitrary code. Every time a language adds a more expressive pattern form, it has to decide whether the usefulness algorithm can still see through it, and the ones that cannot quietly convert a compile-time guarantee into a runtime hope.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

implementationBinding modes — whether Some(x) binds x by value, by reference or by mutable reference — are Rust's match-ergonomics rules, which changed in the 2021 and 2024 editions and are among the most edition-sensitive parts of the language. OCaml and Haskell have no such notion because they have no distinction to make. Do not carry an intuition about what a bare binding does across languages.

implementationThe claim that arms are tried in source order describes the observable semantics of Rust, OCaml, Haskell, Scala and Python. The generated code need not test them in that order and generally does not: [[pattern-matching-compilation]] may test any discriminant first as long as the observable behaviour, including the order of guard evaluation, is preserved.

specPython's structural pattern matching (PEP 634, 3.10+) performs no exhaustiveness check of any kind and falls through a match with no matching case silently, producing whatever the surrounding function returns. This is specified behaviour, not an implementation gap, and it is the single most important difference from matching in a language with sum types.

If you were asked this in an interview

Why does a match on two guarded arms that obviously cover every integer still fail the exhaustiveness check?
What does matching give you over an if chain plus field access, in terms of what the compiler can check?
Python 3.10 added match. What does it give you and what does it not, compared with match in Rust?

Connections

DSAbinary-tree dfs

API Designapi-state-machines error-model

Backendparse-dont-validate

Runtime gain3

Compile cost2

Debuggability4

Implementation4

Context dependence3

Runtime gain is moderate and comes from the compilation step rather than the surface: a decision tree over a dense tag can test each discriminant once, where a hand-written chain of predicate calls tests some of them repeatedly. Compile cost is low for the type checking and moderate for the usefulness analysis, which is worst-case exponential in pattern depth and is bounded in practice by heuristics. Implementation complexity is the high score: pattern forms multiply, and every one of them has to be understood by the type checker, the usefulness algorithm and the decision-tree builder alike.