match-lang
_{^{PATTERN MATCH CHECKING}}

match-lang checks pattern matches. Give it the arms of a match and the type being matched, and it reports the values no arm handles, each with a concrete pattern such as Some(false) or 10..=19, the arms no value can reach, and the alternatives of an or-pattern that are redundant.

It knows nothing about any particular language. A language plugs in by implementing one trait, Model, which says for each of its types which constructors build its values (a sum's variants, a struct's single constructor, an integer type's bounds, a slice's element type) and what each constructor's fields are. Sums, products, booleans, bounded and unbounded integers, characters, opaque literals such as strings, arrays, slices, or-patterns, and guards are all handled, so one implementation serves every language in the -lang family that has a match.

---

MSRV is 1.85+ (Rust 2024 edition). no_std-compatible (needs only alloc), #![forbid(unsafe_code)], no dependencies.

Status: 0.2.0, pre-1.0. Exhaustiveness and usefulness checking are complete; decision-tree compilation arrives in 0.5.0. The API may change before 1.0, which follows once a real consumer has used it end to end. See dev/ROADMAP.md and CHANGELOG.md.

---

The model

• A Model is the language's side: signature(ty) returns the Signature of a type, and fields(ty, variant) the field types of one of its constructors. Optional hooks say which types are empty (!, empty enums) and name variants for printing.
• A Pat is a pattern, built bottom-up: Pat::variant(1, [Pat::bool(true)]), Pat::range(0, 9), Pat::or([..]), Pat::slice_rest([..], [..]). An Arm is a pattern, with or without a guard.
• check takes a model, the scrutinee's type, and the arms, and returns a Report: missing cases as Witness patterns, unreachable arm indices, and Redundant or-alternatives. A Checker does the same with configurable limits and reuses its buffers across checks.
• An Error means the check could not finish: a pattern that does not fit its type, a match too complex for the step budget, or a model that contradicts itself.

What it guarantees, and how each guarantee is checked:

Guarantee	How it is held
A match is reported exhaustive exactly when every value is matched by an unguarded arm.	Property tests compare the checker with a brute-force reference that enumerates every value of random types (integers, characters, strings, and slices through exact representatives) and runs first-match semantics directly.
Every witness describes at least one value, and every value it describes really is unmatched.	The same reference checks every value each witness matches.
An arm is reported unreachable exactly when no value reaches it; an or-alternative is reported redundant exactly when no value reaches it.	The reference expands every or-pattern and decides usefulness from the definition, guards included.
Empty types are understood: Err(_) is not required for a Result<T, !>, and is unreachable.	Integration and property tests with empty types, variants, products, and slice elements.
Deep and wide matches are safe: no recursion, no quadratic copying.	Tests with 100,000-deep patterns and witnesses, and 100,000-field tuples, whose step counts stay linear.
Every check ends in bounded time and memory.	All work is charged to a step budget; matrices that need exponential work (random 3-SAT encodings, or-pattern explosions) return Error::StepLimit. A model that answers at random never causes a panic.

---

Installation

[dependencies]
match-lang = "0.2"

Without the standard library:

[dependencies]
match-lang = { version = "0.2", default-features = false }

---

Quick start

A model for bool and Option<T>, and a match with a gap and a dead arm:

use match_lang::{check, Arm, Model, Pat, Signature};

#[derive(Clone)]
enum Ty {
    Bool,
    Option(Box<Ty>),
}

struct Lang;

impl Model for Lang {
    type Ty = Ty;

    fn signature(&self, ty: &Ty) -> Signature<Ty> {
        match ty {
            Ty::Bool => Signature::Bool,
            Ty::Option(_) => Signature::Sum { count: 2 }, // None, Some
        }
    }

    fn fields(&self, ty: &Ty, variant: u32, out: &mut Vec<Ty>) {
        if let (Ty::Option(inner), 1) = (ty, variant) {
            out.push((**inner).clone());
        }
    }

    fn variant_name(&self, _: &Ty, variant: u32) -> Option<&str> {
        Some(if variant == 0 { "None" } else { "Some" })
    }
}

// match x { Some(true) => .., None => .., Some(true) => .. }
let arms = [
    Arm::new(Pat::variant(1, [Pat::bool(true)])),
    Arm::new(Pat::variant(0, [])),
    Arm::new(Pat::variant(1, [Pat::bool(true)])),
];
let report = check(&Lang, &Ty::Option(Box::new(Ty::Bool)), &arms)?;

assert!(!report.is_exhaustive());
assert_eq!(report.missing()[0].display(&Lang).to_string(), "Some(false)");
assert_eq!(report.unreachable(), &[2]);
# Ok::<(), match_lang::Error>(())

Integers and ranges

Integer types are covered range by range, up to their exact bounds:

use match_lang::{check, Arm, Model, Pat, Signature};

struct Bytes;

impl Model for Bytes {
    type Ty = ();
    fn signature(&self, _: &()) -> Signature<()> {
        Signature::Int { min: 0, max: 255 }
    }
    fn fields(&self, _: &(), _: u32, _: &mut Vec<()>) {}
}

let arms = [Arm::new(Pat::range(0, 9)), Arm::new(Pat::int(11)), Arm::new(Pat::range(13, 255))];
let missing: Vec<String> =
    check(&Bytes, &(), &arms)?.missing().iter().map(|w| w.to_string()).collect();
assert_eq!(missing, ["10", "12"]);
# Ok::<(), match_lang::Error>(())

Guards and or-patterns

A guard may fail, so a guarded arm never covers anything; redundant alternatives are reported by their position in the arm's pattern:

use match_lang::{check, Arm, Model, Pat, Redundant, Signature};

struct Flag;

impl Model for Flag {
    type Ty = ();
    fn signature(&self, _: &()) -> Signature<()> {
        Signature::Bool
    }
    fn fields(&self, _: &(), _: u32, _: &mut Vec<()>) {}
}

let arms = [
    Arm::guarded(Pat::wild()),                             // _ if cond
    Arm::new(Pat::or([Pat::bool(true), Pat::bool(true)])), // true | true
];
let report = check(&Flag, &(), &arms)?;
assert_eq!(report.missing()[0].to_string(), "false");
// Node 0 is the or-pattern; nodes 1 and 2 its alternatives.
assert_eq!(report.redundant(), &[Redundant { arm: 1, node: 2 }]);
# Ok::<(), match_lang::Error>(())

---

Examples

Runnable programs in examples/:

Example	What it shows
option	The one-call path on Option<bool>: missing cases and an unreachable arm. cargo run --example option
language	A small language's checker with named enums and structs, integers, interned strings, slices, guards, and or-patterns; a reused Checker; compiler-style messages that map report positions back to the language's own pattern tree.

---

Performance

A check is one pass over the pattern matrix. Rows are persistent stacks that share their tails, so specializing a row pushes only the head constructor's fields; every arena is a stack truncated when its level finishes and reused by the next check. Columns are split into only the constructors their patterns mention, integer ranges into disjoint segments in one sorted sweep, and slice lengths into intervals. A row whose wildcard head can teach nothing under a constructor explored only for usefulness is not explored there, which is what keeps matrices such as one-test-per-row from going exponential.

Measured with the benchmarks in benches/, Windows x86_64, Rust stable, release profile, one reused Checker:

Benchmark	What it measures	Windows
enum_100k_variants	100,000 arms, one per variant of a 100,000-variant enum.	~7.9 ms
int_literals_100k	100,000 integer literals and a wildcard over i64.	~10.9 ms
int_ranges_100k_exhaustive	100,000 adjacent ranges covering all of i64.	~9.4 ms
truth_table_16	All 65,536 rows of a 16-column boolean truth table.	~77 ms
wide_1000x1000	1,000 rows by 1,000 columns, each row testing one column.	~55 ms
nested_options_1000	None, Some(None), ... 1,000 levels deep (500,000 pattern nodes).	~49 ms
or_alternatives_100k	1,000 arms of 100 alternatives each.	~11.4 ms
slices_1000_lengths	Fixed-length slice patterns of every length to 1,000, then [..].	~68 ms
small_matches/reused_checker_10k	10,000 three-arm matches through one Checker (~0.41 µs each).	~4.1 ms
small_matches/fresh_check_10k	The same through check, allocating each time (~1.3 µs each).	~13.2 ms

These are library-only numbers: building the Pat trees is not included. Linux and macOS figures come from the CI matrix and are not recorded here.

cargo bench --bench bench

Numbers vary by CPU; use the trend across runs, not a single absolute.

---

Design notes

• Maranget's algorithm, as compilers run it. Usefulness of every row is computed in one pass; a column is split into the constructors its patterns mention plus one "missing" constructor for the rest; witnesses are built on the way back. Witnesses come from the missing constructors wherever there are any, so they are a sample chosen to be informative, not a list of every missing value.
• Exhaustiveness is NP-hard, so there is a budget. Every unit of work counts against a step limit (about 16.7 million by default, configurable). A match that needs more is an Error::StepLimit, never a hang; the benchmark matches above use at most about 8.5 million steps, and Report::steps shows what a real match uses.
• No recursion anywhere input reaches. The specialization recursion runs on an explicit stack of frames; flattening, validation, Drop, Clone, and Display of patterns and witnesses are iterative.
• Patterns are checked against their types first. A pattern that does not fit (an integer pattern on an enum, a variant that does not exist, a range outside a type's bounds) is an Error::InvalidPattern naming the arm and node, before any analysis.
• Exact in the presence of empty types. A variant with an empty field has no values: it is never required and arms matching only it are unreachable. A slice of an empty type has only [].
• No first-party dependencies. The crate depends on nothing; a language's types reach it only through Model, so hir-lang implements the trait rather than the other way round.

---

Testing

The suite runs on Windows, Linux, and macOS through the CI matrix, on stable and the 1.85 MSRV:

cargo test                       # unit + integration + property + doctests
cargo test --no-default-features # no_std + alloc
cargo clippy --all-targets --all-features -- -D warnings
cargo bench --bench bench

tests/properties.rs holds the checker to a brute-force reference over random types up to three levels deep (sums with empty variants, products, booleans, bounded and unbounded integers, characters across the surrogate gap, opaque literals, arrays, slices) and random matches with nested or-patterns and guards: exhaustiveness, every witness, every unreachable arm, and every redundant alternative must agree. A one-off run of 200,000 cases per property found no disagreement, and each of more than a dozen deliberate bugs planted in the engine was caught. tests/adversarial.rs covers deep and wide matches, exponential matrices, and a model that answers at random. Every rust example in this README and in docs/API.md is compiled and run as a doctest.

---

Cross-platform support

• Linux (x86_64, aarch64)
• macOS (x86_64, Apple Silicon)
• Windows (x86_64)

The crate uses no operating-system facilities and no platform-specific code.

---

Contributing

See REPS.md for the engineering standards every change is held to, dev/DIRECTIVES.md for the definition of done, and dev/ROADMAP.md for what comes next. Before a PR: cargo fmt --all, cargo clippy --all-targets --all-features -- -D warnings, and cargo test --all-features must be clean.

License

Licensed under either of

• Apache License, Version 2.0 — LICENSE-APACHE
• MIT License — LICENSE-MIT

at your option.

^{COPYRIGHT © 2026 James Gober.}