Crate match_lang 

match-lang

Exhaustiveness and usefulness checking for pattern matching, generic over a language’s types.

Give it the arms of a match and the type being matched, and it tells you which values no arm handles (with a concrete pattern for each), which arms can never be reached, and which alternatives of an or-pattern are redundant. A language plugs in by implementing Model: for each of its types, a Signature saying which constructors build its values, and the field types of each constructor. The crate knows nothing else about the language, so every language in the family shares one implementation.

Quick start

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

// The language: `bool` and `Option<T>`.
#[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: Option<bool> { 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]);

What it handles

• Sums, products, booleans, with fields to any depth. Sum variants whose fields include an empty type (see Model::is_empty) have no values: they are never required, and arms matching only them are unreachable.
• Integers and characters, with literals and inclusive ranges over the type’s exact bounds, so 0..=127 | 128..=255 covers a u8. Unbounded integers (Signature::BigInt) and opaque literals such as strings (Signature::Opaque) always need a wildcard.
• Arrays and slices: fixed-length patterns [a, b] and rest patterns [a, .., z], over fixed-length arrays and variable-length slices.
• Or-patterns, nested anywhere; each redundant alternative is reported on its own.
• Guards: a guarded arm may fail, so it never covers a value for exhaustiveness and never makes a later arm unreachable.

How it works

This is the usefulness algorithm of Luc Maranget’s Warnings for pattern matching (JFP 2007), in the form modern compilers use: one pass computes the usefulness of every row of the pattern matrix, columns are split into the constructors their patterns mention plus one constructor standing for all the missing ones (integer and character ranges are cut into disjoint segments; slice lengths are grouped into a finite set), and witnesses are built on the way back. It runs on an explicit stack, not recursion, and rows share their tails, so deep or wide matches cost no call stack and no quadratic copying. Deciding exhaustiveness is NP-hard in general; every unit of work counts against a step limit, and a match too complex to check is an Error::StepLimit, never a hang.

Tiers

• check: one call with default limits.
• Checker: the same, with configurable limits and buffers reused across checks.

Features

• std (default): nothing beyond alloc is used; without it the crate is no_std.

The crate is #![forbid(unsafe_code)] and has no dependencies.

Structs

Arm

One arm of a match: a pattern, and whether the arm has a guard.

Checker

Checks matches for exhaustiveness and usefulness, reusing its buffers from one check to the next.

Pat

A pattern: the left-hand side of one match arm, or a part of one.

Redundant

A redundant or-pattern alternative: in arm arm, the alternative whose root is node node of the arm’s pattern, by preorder index.

Report

What checking a match found: missing cases, unreachable arms, and redundant or-pattern alternatives.

Witness

A pattern describing values that no arm matches: proof that a match is not exhaustive.

WitnessDisplay

A witness printed with the model’s variant names. Returned by Witness::display and WitnessRef::display.

WitnessFields

The fields of a WitnessRef, in order. Returned by WitnessRef::fields.

WitnessRef

A node of a Witness: its constructor, its type, and its fields.

Enums

Ctor

The constructor at one node of a Witness.

Error

Why a check could not produce a Report.

Reason

What is wrong with a pattern, in Error::InvalidPattern.

Signature

The constructors that build the values of one type.

Constants

DEFAULT_STEP_LIMIT

The default step limit: about 16.7 million units of work. Real matches, even with tens of thousands of arms, use a small fraction of it; a pathological one stops in well under a second.

DEFAULT_WITNESS_LIMIT

The default witness limit.

Traits

Model

A language’s constructor model.

Functions

check

Checks arms, in order, against values of type ty: the one-call entry point, with the default limits. For many matches, or other limits, use a Checker.