Chapter 16: Pattern-Match Compilation

New files

src/match_compile.rs

src/usefulness.rs

src/env.rs

Changed files

src/core.rs

src/core_lint.rs

src/eval.rs

src/io_lower.rs

src/lib.rs

src/main.rs

Motivation

Our interpreter tries patterns from top to bottom, which makes their meaning easy to follow. A native compiler needs to turn that process into instructions that inspect tags, load fields, and branch. We could translate each pattern separately, but we’d often inspect the same value again and again.

Instead, we’ll look at the patterns together. Put them in a matrix, choose a useful test, and divide the remaining work according to its result. This gives us a decision tree. Join points let different paths share the code they reach, including the next clause when a guard fails.

We can also ask whether any inputs slip through the patterns, or whether an earlier clause has already caught everything a later clause could match. It’s a pleasing connection. Understanding the shapes of values helps us both run patterns and explain mistakes in them.

The Language, Now

There is no new source syntax. Earlier programs keep the same results, including guards that fail after their patterns match:

f (Just x) | x < 0 = 0
f (Just x) = x
f Nothing = 99

main = print (f (Just 42))

The first clause recognizes Just 42, but its guard fails. Execution must try the second clause and return 42. It must not report pattern failure or skip to the Nothing clause. Local where bindings remain in scope for the guards and right-hand side of their own equation.

The checker can now show us holes in a match. W0001 includes example inputs that aren’t covered, and W0002 points out a clause that earlier clauses have made unreachable. These are warnings, so the program can still run. Encountering an uncovered input at runtime still reports fun: pattern match failure at FILE:LINE:COL.

Theory

Think of a match as a matrix whose rows are clauses and whose columns are scrutinees. Specializing a column for constructor C keeps rows that can match C, removes that constructor, and inserts its fields as new columns. A default matrix retains rows whose selected pattern can match any other value. This is the decision-tree approach described by Maranget (Maranget 2008).

Fun chooses the first column containing a refutable pattern in the first row. That simple heuristic is deterministic and easy to trace. It is not a claim to minimize the number of tests for every matrix. Wildcards, variables, and as-patterns do not inspect a value. Their bindings are recorded for the eventual clause body. Constructor patterns expose fields only after their tag has matched.

Finite datatypes have known constructor families. Integer and character literals need a default path because a finite set of tested literals cannot exhaust their value domain. String patterns become equality tests. Double patterns also use primitive equality, preserving the language’s floating comparison behavior, including equality of positive and negative zero.

Usefulness asks whether a candidate pattern vector admits a value not matched by preceding covering rows (Maranget 2007). A useless source row is redundant. A useful all-wildcard candidate supplies a missing-case witness. Guards complicate coverage because a matching pattern may still fall through. The implementation treats a guarded row as covering only when one guard is literally True. It does not attempt to prove arbitrary Boolean expressions.

One Question, Two Checks

There’s a neat way to turn both warnings into the same question. Does this pattern match anything the earlier patterns missed? Maranget calls such a pattern useful. We’ll write U(P, q) for this question, with earlier rows P and candidate pattern vector q. A witness is an actual shape that slips past P and matches q (Maranget 2007).

For reachability, P contains the covering rows before the current clause and q is that clause’s pattern vector. For exhaustiveness, P contains all covering rows and q is an all-wildcard vector. The first query asks whether a clause adds any cases. The second asks whether anything is still missing. It’s the rows together that determine coverage. A clause can be unreachable even when no single earlier clause covers it completely.

Consider a function with two arguments, Maybe Bool and Bool:

choose Nothing     _     = 0
choose (Just True) _     = 1
choose (Just _)    False = 2

Ignore the right-hand sides and retain the argument columns:

Row	First Argument	Second Argument
1	`Nothing`	`_`
2	`Just True`	`_`
3	`Just _`	`False`

Ask whether (_, _) is useful. The first column contains both constructors of Maybe, so examine each constructor family member. Specializing for Nothing discards rows 2 and 3 and leaves a wildcard for the second argument. That branch is covered. Specializing for Just discards row 1 and replaces the first column with the constructor’s single field:

Row	Value Inside `Just`	Second Argument
2	`True`	`_`
3	`_`	`False`

The True branch is covered by row 2. In the False branch, only row 3 remains, and it covers a second argument of False. The uncovered second argument is True. Rebuilding the constructor around the field gives the witness (Just False, True) for the original argument vector. Adding choose (Just False) True = 3 completes this match. Any subsequent clause is unreachable, even though no original clause alone covered every input.

Specialization and the Default Matrix

usefulness.rs implements the search on the first column. The selected pattern and constructor family determine the next problem:

Constructor candidate. For C(p1, ..., pk), keep rows headed by C or a wildcard. Replace C by its fields. Expand a wildcard to k wildcards. Drop rows headed by other constructors, and make the same expansion in the query.
Wildcard candidate, complete family. If every constructor of the column’s datatype appears, specialize for each. Any useful branch supplies a witness.
Wildcard candidate, incomplete family. Search the default matrix: retain only wildcard-headed rows and drop their first column. A useful suffix can be prefixed by a missing constructor. Literal domains are handled through this path, choosing a literal absent from the tested heads.

The zero-column case distinguishes an empty matrix from an empty row. With no rows, nothing covers the remaining empty vector, so it is useful. With an empty row, an earlier clause already matches everything left, so it is not useful. These small base cases let the search handle nested constructors without enumerating all values of a recursive datatype.

On return, the algorithm rebuilds each stripped constructor around the witness fields. Fun’s useful therefore returns an optional pattern vector, rather than just a Boolean. The warning driver can print a concrete missing shape, add that shape to its temporary coverage matrix, and search again for up to three examples.

Guards and the Limits of Coverage

A guarded clause can be unreachable because earlier clauses already cover its patterns. It can’t usually establish coverage itself, since its guard might fail. Fun checks the row against earlier coverage, then adds it only if it is unguarded or has a syntactically literal True guard. It does not solve arbitrary guard expressions. Consequently a reported gap can reflect this conservative policy, and a useful pattern does not prove that its guard will ever succeed.

The analysis uses typed constructor families and treats variables as wildcards. As-pattern names do not change coverage. It does not prove that recursive field types are inhabited. Compilation and checking remain separate. The decision tree must preserve clause order and guard fallthrough regardless of these warnings.

A join point names a continuation local to an expression. Its parameters carry the values needed by the shared body, and every jump is a fully applied tail transfer. Unlike an ordinary function, a join cannot escape or be passed as a value. This distinction anticipates the later use of joins in ANF (Maurer et al. 2017).

Implementation

The compiler’s internal row separates the remaining patterns from the eventual right-hand side. values records the values bound along the current decision path. target and params identify the shared clause body.

#![allow(unused)]
fn main() {
use crate::{
    core::{self, Alt, AltCon, Expr, Id, Pat, RowBody, Type},
    names,
    session::{Session, Stop},
    source::Span,
};
use std::collections::BTreeMap;
struct Compiler<'a> {
    sess: &'a mut Session,
    constructors: Vec<core::ConDecl>,
    truths: std::collections::BTreeSet<u32>,
}
impl Compiler<'_> {
    fn fresh(&mut self, ty: Type) -> Id {
        Id {
            name: self.sess.fresh_id("$case"),
            ty,
        }
    }
    fn fields(&self, con: &crate::data::ConId, ty: &Type) -> Vec<Type> {
        let c = &self.constructors[con.index as usize];
        let args = match ty {
            Type::Con(_, args) => args.as_slice(),
            Type::Bool => &[],
            _ => unreachable!("typed data scrutinee"),
        };
        c.fields
            .iter()
            .map(|t| crate::elaborate::instantiate(t, &c.parameters, args))
            .collect()
    }
    fn boolean(
        &mut self,
        test: Expr,
        yes: Expr,
        no: Expr,
        result: &Type,
    ) -> Expr {
        let truth = self
            .constructors
            .iter()
            .find(|c| c.id.name == "True")
            .unwrap()
            .id
            .clone();
        Expr::Case(
            Box::new(test),
            self.fresh(Type::Bool),
            result.clone(),
            vec![
                Alt {
                    con: AltCon::Con(truth),
                    binders: vec![],
                    rhs: yes,
                },
                Alt {
                    con: AltCon::Default,
                    binders: vec![],
                    rhs: no,
                },
            ],
        )
    }
    fn group(&mut self, g: core::BindGroup) -> core::BindGroup {
        core::BindGroup {
            recursive: g.recursive,
            binds: g
                .binds
                .into_iter()
                .map(|mut b| {
                    b.rhs = Box::new(self.expr(*b.rhs));
                    b
                })
                .collect(),
        }
    }
    fn expr(&mut self, e: Expr) -> Expr {
        match e {
            Expr::Match(m) => self.compile(m),
            Expr::Lam(i, b) => Expr::Lam(i, Box::new(self.expr(*b))),
            Expr::TyLam(v, b) => Expr::TyLam(v, Box::new(self.expr(*b))),
            Expr::TyApp(b, t) => Expr::TyApp(Box::new(self.expr(*b)), t),
            e @ Expr::App(..) => {
                let mut work = vec![Some(e)];
                let mut output = Vec::new();
                while let Some(job) = work.pop() {
                    match job {
                        Some(Expr::App(a, b)) => {
                            work.push(None);
                            work.push(Some(*b));
                            work.push(Some(*a));
                        }
                        Some(e) => output.push(self.expr(e)),
                        None => {
                            let b = output.pop().unwrap();
                            let a = output.pop().unwrap();
                            output
                                .push(Expr::App(Box::new(a), Box::new(b)));
                        }
                    }
                }
                output.pop().unwrap()
            }
            Expr::Let(g, b) => {
                Expr::Let(self.group(g), Box::new(self.expr(*b)))
            }
            Expr::Con(c, ts, args) => Expr::Con(
                c,
                ts,
                args.into_iter().map(|e| self.expr(e)).collect(),
            ),
            Expr::Prim(p, ts, args, s) => Expr::Prim(
                p,
                ts,
                args.into_iter().map(|e| self.expr(e)).collect(),
                s,
            ),
            other => other,
        }
    }
    fn compile(&mut self, m: core::Match) -> Expr {
        crate::usefulness::warn(
            self.sess,
            &m,
            &self.constructors,
            &self.truths,
        );
        let mut rows = vec![];
        let mut bodies = vec![];
        for r in m.rows {
            let mut params = vec![];
            for p in &r.pats {
                binders(p, &mut params)
            }
            let target = self.sess.fresh_id("$rhs");
            rows.push(Row {
                pats: r.pats,
                values: BTreeMap::new(),
                target: target.clone(),
                params: params.clone(),
            });
            bodies.push((target, params, r.locals, r.body));
        }
        let mut definitions = vec![];
        for (index, (target, params, locals, body)) in
            bodies.into_iter().enumerate().rev()
        {
            let fail = self.sess.fresh_id("$fail");
            let mut body = match body {
                RowBody::Plain(e) => self.expr(*e),
                RowBody::Guarded(gs) => {
                    let residual = self.tree(
                        m.scruts.clone(),
                        rows[index + 1..].to_vec(),
                        &m.result,
                        m.span,
                    );
                    definitions.push((fail.clone(), vec![], residual));
                    let mut fallback =
                        Expr::Jump(fail.clone(), vec![], m.result.clone());
                    for (g, e) in gs.into_iter().rev() {
                        let g = self.expr(g);
                        let e = self.expr(e);
                        fallback = self.boolean(g, e, fallback, &m.result)
                    }
                    fallback
                }
            };
            for g in locals.into_iter().rev() {
                body = Expr::Let(self.group(g), Box::new(body))
            }
            definitions.push((target, params, body));
        }
        let mut body = self.tree(m.scruts, rows, &m.result, m.span);
        for (id, params, rhs) in definitions.into_iter().rev() {
            body = Expr::Join(id, params, Box::new(rhs), Box::new(body))
        }
        body
    }
    fn tree(
        &mut self,
        scruts: Vec<Id>,
        mut rows: Vec<Row>,
        result: &Type,
        span: Span,
    ) -> Expr {
        if rows.is_empty() {
            return Expr::PatternFail(span, result.clone());
        }
        // Bind variables/as-patterns without copying their unique Core binders.
        for row in &mut rows {
            for (p, s) in row.pats.iter_mut().zip(&scruts) {
                loop {
                    match p.clone() {
                        Pat::Var(id) => {
                            row.values.insert(id.unique(), s.clone());
                            *p = Pat::Wild;
                            break;
                        }
                        Pat::As(id, inner) => {
                            row.values.insert(id.unique(), s.clone());
                            *p = *inner
                        }
                        _ => break,
                    }
                }
            }
        }
        let Some(column) =
            rows[0].pats.iter().position(|p| !matches!(p, Pat::Wild))
        else {
            let row = &rows[0];
            return Expr::Jump(
                row.target.clone(),
                row.params
                    .iter()
                    .map(|p| Expr::Var(row.values[&p.unique()].clone()))
                    .collect(),
                result.clone(),
            );
        };
        let scrut = scruts[column].clone();
        let mut heads = vec![];
        for row in &rows {
            let head = match &row.pats[column] {
                Pat::Con(c, _) => AltCon::Con(c.clone()),
                Pat::Lit(l) => AltCon::Lit(l.clone()),
                _ => continue,
            };
            if !heads.contains(&head) {
                heads.push(head)
            }
        }
        let mut alts = vec![];
        for head in heads {
            let fields = match &head {
                AltCon::Con(c) => self.fields(c, &scrut.ty),
                _ => vec![],
            };
            let params = fields
                .into_iter()
                .map(|t| self.fresh(t))
                .collect::<Vec<_>>();
            let mut specialized = vec![];
            for mut row in rows.clone() {
                let p = row.pats.remove(column);
                let fields = match (&head, p) {
                    (_, Pat::Wild) => vec![Pat::Wild; params.len()],
                    (AltCon::Con(c), Pat::Con(d, ps)) if *c == d => ps,
                    (AltCon::Lit(a), Pat::Lit(b)) if *a == b => vec![],
                    _ => continue,
                };
                row.pats.splice(column..column, fields);
                specialized.push(row)
            }
            let mut columns = scruts.clone();
            columns.splice(column..=column, params.clone());
            let rhs = self.tree(columns, specialized, result, span);
            alts.push(Alt {
                con: head,
                binders: params,
                rhs,
            });
        }
        let mut defaults = vec![];
        for mut row in rows {
            if matches!(row.pats[column], Pat::Wild) {
                row.pats.remove(column);
                defaults.push(row)
            }
        }
        let mut columns = scruts;
        columns.remove(column);
        let fallback = self.tree(columns, defaults, result, span);
        if matches!(scrut.ty, Type::String | Type::Double) {
            let mut body = fallback;
            for alt in alts.into_iter().rev() {
                let AltCon::Lit(l) = alt.con else {
                    unreachable!()
                };
                let primitive = if matches!(scrut.ty, Type::String) {
                    crate::primitives::Prim::StrEq
                } else {
                    crate::primitives::Prim::DblEq
                };
                let test = Expr::Prim(
                    crate::ast::Op::Runtime(primitive),
                    vec![],
                    vec![Expr::Var(scrut.clone()), Expr::Lit(l)],
                    span,
                );
                body = self.boolean(test, alt.rhs, body, result);
            }
            body
        } else {
            alts.push(Alt {
                con: AltCon::Default,
                binders: vec![],
                rhs: fallback,
            });
            Expr::Case(
                Box::new(Expr::Var(scrut.clone())),
                self.fresh(scrut.ty),
                result.clone(),
                alts,
            )
        }
    }
}
fn binders(p: &Pat, out: &mut Vec<Id>) {
    match p {
        Pat::Var(i) => out.push(i.clone()),
        Pat::As(i, p) => {
            out.push(i.clone());
            binders(p, out)
        }
        Pat::Con(_, ps) => {
            for p in ps {
                binders(p, out)
            }
        }
        _ => {}
    }
}
/// Compile every nested match; generated binders come from the shared unique supply.
pub fn compile(
    sess: &mut Session,
    mut program: core::Program,
) -> Result<core::Program, Stop> {
    let mut compiler = Compiler {
        sess,
        constructors: program.constructors.clone(),
        truths: program.groups.iter().flat_map(|g| &g.binds)
            .filter(|b| matches!(&*b.rhs, Expr::Con(c, _, _) if c.name == "True"))
            .map(|b| b.name.unique()).collect(),
    };
    program.groups = program
        .groups
        .into_iter()
        .map(|g| compiler.group(g))
        .collect();
    compiler.sess.finish(program)
}
#[derive(Clone)]
struct Row {
    pats: Vec<Pat>,
    values: BTreeMap<u32, Id>,
    target: names::Id,
    params: Vec<Id>,
}
}

Before building tests, Compiler::compile assigns each clause a parameterized right-hand-side join. It also compiles the residual matrix following that clause into a failure join. Guards run in order. If all fail, a jump enters that residual matrix. Several leaves can therefore reach one clause body without copying it, and several failed guards can use one fallback.

A constructor branch must bind fields at the scrutinee’s actual type arguments. The helper looks up the declaration and substitutes its parameters:

#![allow(unused)]
fn main() {
fn fields(&self, con: &crate::data::ConId, ty: &Type) -> Vec<Type> {
    let c = &self.constructors[con.index as usize];
    let args = match ty {
        Type::Con(_, args) => args.as_slice(),
        Type::Bool => &[],
        _ => unreachable!("typed data scrutinee"),
    };
    c.fields
        .iter()
        .map(|t| crate::elaborate::instantiate(t, &c.parameters, args))
        .collect()
}
}

For example, specializing Just at Maybe Int binds an Int, not the declaration’s uninstantiated type variable. The same rule matters for a record projection: its single-constructor match now becomes a tag branch and ordinary field binders. Core lint independently checks these instantiated types.

Compiler::tree handles the matrix recursively. An empty matrix becomes PatternFail. A first row with no refutable patterns jumps to its clause join, passing the values accumulated for its binders. Otherwise the selected column produces a flat Case, or equality tests for string and Double literals, with specialized subtrees and a default subtree.

The warning pass uses the original nested patterns, before that representation is lost. Its specialization helper is the matrix operation traced above:

#![allow(unused)]
fn main() {
use crate::{
    core::{ConDecl, Lit, Match, Pat, RowBody, Type},
    diagnostics::{Diagnostic, ErrorCode, Severity},
    session::Session,
};
fn peel(p: &Pat) -> &Pat {
    if let Pat::As(_, p) = p { peel(p) } else { p }
}
fn wild(p: &Pat) -> bool {
    matches!(peel(p), Pat::Wild | Pat::Var(_))
}
fn same(a: &Pat, b: &Pat) -> bool {
    match (peel(a), peel(b)) {
        (Pat::Con(a, _), Pat::Con(b, _)) => a == b,
        (Pat::Lit(Lit::Double(a)), Pat::Lit(Lit::Double(b))) => {
            f64::from_bits(*a) == f64::from_bits(*b)
        }
        (Pat::Lit(a), Pat::Lit(b)) => a == b,
        _ => false,
    }
}
fn fields(head: &Pat, ty: &Type, cons: &[ConDecl]) -> Vec<Type> {
    match peel(head) {
        Pat::Con(id, _) => {
            let c = &cons[id.index as usize];
            let args = match ty {
                Type::Con(_, args) => args.as_slice(),
                _ => &[],
            };
            c.fields
                .iter()
                .map(|t| {
                    crate::elaborate::instantiate(t, &c.parameters, args)
                })
                .collect()
        }
        _ => vec![],
    }
}
fn family(ty: &Type, cons: &[ConDecl]) -> Vec<Pat> {
    cons.iter()
        .filter(|c| match (&c.result, ty) {
            (Type::Bool, Type::Bool) => true,
            (Type::Con(a, _), Type::Con(b, _)) => a == b,
            _ => false,
        })
        .map(|c| Pat::Con(c.id.clone(), vec![Pat::Wild; c.fields.len()]))
        .collect()
}
/// Return a witness matched by the query but not by any covering row.
pub fn useful(
    matrix: &[Vec<Pat>],
    query: &[Pat],
    types: &[Type],
    cons: &[ConDecl],
) -> Option<Vec<Pat>> {
    if query.is_empty() {
        return matrix.is_empty().then(Vec::new);
    }
    let q = peel(&query[0]);
    if !wild(q) {
        let mut ts = fields(q, &types[0], cons);
        let n = ts.len();
        ts.extend_from_slice(&types[1..]);
        let mut qs = match q {
            Pat::Con(_, ps) => ps.clone(),
            _ => vec![],
        };
        qs.extend_from_slice(&query[1..]);
        let mut witness =
            useful(&specialize(matrix, q, n), &qs, &ts, cons)?;
        let children = witness.drain(..n).collect();
        let p = match q {
            Pat::Con(c, _) => Pat::Con(c.clone(), children),
            _ => q.clone(),
        };
        witness.insert(0, p);
        return Some(witness);
    }
    let heads = matrix
        .iter()
        .filter(|r| !wild(&r[0]))
        .map(|r| peel(&r[0]).clone())
        .collect::<Vec<_>>();
    let all = family(&types[0], cons);
    if !all.is_empty()
        && all.iter().all(|h| heads.iter().any(|p| same(h, p)))
    {
        for head in all {
            let mut ts = fields(&head, &types[0], cons);
            let n = ts.len();
            ts.extend_from_slice(&types[1..]);
            let mut qs = vec![Pat::Wild; n];
            qs.extend_from_slice(&query[1..]);
            if let Some(mut w) =
                useful(&specialize(matrix, &head, n), &qs, &ts, cons)
            {
                let children = w.drain(..n).collect();
                let Pat::Con(c, _) = head else { unreachable!() };
                w.insert(0, Pat::Con(c, children));
                return Some(w);
            }
        }
        None
    } else {
        let defaults = matrix
            .iter()
            .filter(|r| wild(&r[0]))
            .map(|r| r[1..].to_vec())
            .collect::<Vec<_>>();
        let mut witness =
            useful(&defaults, &query[1..], &types[1..], cons)?;
        let missing = all
            .into_iter()
            .find(|h| !heads.iter().any(|p| same(h, p)))
            .unwrap_or_else(|| {
                for n in 0..=heads.len() {
                    let p = match types[0] {
                        Type::Int => Pat::Lit(Lit::Int(n as i64)),
                        Type::Char => Pat::Lit(Lit::Char(
                            char::from_u32(97 + n as u32).unwrap_or('\0'),
                        )),
                        Type::String => {
                            Pat::Lit(Lit::String("x".repeat(n)))
                        }
                        Type::Double => {
                            Pat::Lit(Lit::Double((n as f64).to_bits()))
                        }
                        _ => return Pat::Wild,
                    };
                    if !heads.iter().any(|h| same(&p, h)) {
                        return p;
                    }
                }
                unreachable!()
            });
        witness.insert(0, missing);
        Some(witness)
    }
}
fn covers(
    body: &RowBody,
    truths: &std::collections::BTreeSet<u32>,
) -> bool {
    match body {
        RowBody::Plain(_) => true,
        RowBody::Guarded(gs) => gs.iter().any(|(g, _)| match g {
            crate::core::Expr::Con(c, _, _) => c.name == "True",
            crate::core::Expr::Global(id) => truths.contains(&id.unique()),
            _ => false,
        }),
    }
}
/// Warnings do not alter the decision tree; unmatched execution still fails at runtime.
pub fn warn(
    sess: &mut Session,
    m: &Match,
    cons: &[ConDecl],
    truths: &std::collections::BTreeSet<u32>,
) {
    let types = m.scruts.iter().map(|i| i.ty.clone()).collect::<Vec<_>>();
    let mut matrix = vec![];
    for (index, row) in m.rows.iter().enumerate() {
        if useful(&matrix, &row.pats, &types, cons).is_none()
            && !(index > 0 && m.rows[index - 1].span == row.span)
        {
            let mut d = Diagnostic::error(
                ErrorCode::Redundant,
                "clause can never match",
                row.span,
            );
            d.severity = Severity::Warning;
            sess.emit(d);
        }
        if covers(&row.body, truths) {
            matrix.push(row.pats.clone())
        }
    }
    let mut missing = vec![];
    for _ in 0..3 {
        let Some(p) =
            useful(&matrix, &vec![Pat::Wild; types.len()], &types, cons)
        else {
            break;
        };
        missing.push(
            p.iter()
                .map(ToString::to_string)
                .collect::<Vec<_>>()
                .join(" "),
        );
        matrix.push(p)
    }
    if !missing.is_empty() {
        let mut d = Diagnostic::error(
            ErrorCode::NonExhaustive,
            "non-exhaustive pattern match",
            m.span,
        );
        d.severity = Severity::Warning;
        d.notes.push(format!("missing: {}", missing.join("; ")));
        sess.emit(d)
    }
}
fn specialize(
    matrix: &[Vec<Pat>],
    head: &Pat,
    arity: usize,
) -> Vec<Vec<Pat>> {
    matrix
        .iter()
        .filter_map(|row| {
            let mut fields = if wild(&row[0]) {
                vec![Pat::Wild; arity]
            } else if same(&row[0], head) {
                match peel(&row[0]) {
                    Pat::Con(_, ps) => ps.clone(),
                    _ => vec![],
                }
            } else {
                return None;
            };
            fields.extend_from_slice(&row[1..]);
            Some(fields)
        })
        .collect()
}
}

useful carries the candidate vector and column types alongside the matrix. Its driver repeatedly asks for useful witnesses and records diagnostics:

#![allow(unused)]
fn main() {
use crate::{
    core::{ConDecl, Lit, Match, Pat, RowBody, Type},
    diagnostics::{Diagnostic, ErrorCode, Severity},
    session::Session,
};
fn peel(p: &Pat) -> &Pat {
    if let Pat::As(_, p) = p { peel(p) } else { p }
}
fn wild(p: &Pat) -> bool {
    matches!(peel(p), Pat::Wild | Pat::Var(_))
}
fn same(a: &Pat, b: &Pat) -> bool {
    match (peel(a), peel(b)) {
        (Pat::Con(a, _), Pat::Con(b, _)) => a == b,
        (Pat::Lit(Lit::Double(a)), Pat::Lit(Lit::Double(b))) => {
            f64::from_bits(*a) == f64::from_bits(*b)
        }
        (Pat::Lit(a), Pat::Lit(b)) => a == b,
        _ => false,
    }
}
fn specialize(
    matrix: &[Vec<Pat>],
    head: &Pat,
    arity: usize,
) -> Vec<Vec<Pat>> {
    matrix
        .iter()
        .filter_map(|row| {
            let mut fields = if wild(&row[0]) {
                vec![Pat::Wild; arity]
            } else if same(&row[0], head) {
                match peel(&row[0]) {
                    Pat::Con(_, ps) => ps.clone(),
                    _ => vec![],
                }
            } else {
                return None;
            };
            fields.extend_from_slice(&row[1..]);
            Some(fields)
        })
        .collect()
}
fn fields(head: &Pat, ty: &Type, cons: &[ConDecl]) -> Vec<Type> {
    match peel(head) {
        Pat::Con(id, _) => {
            let c = &cons[id.index as usize];
            let args = match ty {
                Type::Con(_, args) => args.as_slice(),
                _ => &[],
            };
            c.fields
                .iter()
                .map(|t| {
                    crate::elaborate::instantiate(t, &c.parameters, args)
                })
                .collect()
        }
        _ => vec![],
    }
}
fn family(ty: &Type, cons: &[ConDecl]) -> Vec<Pat> {
    cons.iter()
        .filter(|c| match (&c.result, ty) {
            (Type::Bool, Type::Bool) => true,
            (Type::Con(a, _), Type::Con(b, _)) => a == b,
            _ => false,
        })
        .map(|c| Pat::Con(c.id.clone(), vec![Pat::Wild; c.fields.len()]))
        .collect()
}
/// Return a witness matched by the query but not by any covering row.
pub fn useful(
    matrix: &[Vec<Pat>],
    query: &[Pat],
    types: &[Type],
    cons: &[ConDecl],
) -> Option<Vec<Pat>> {
    if query.is_empty() {
        return matrix.is_empty().then(Vec::new);
    }
    let q = peel(&query[0]);
    if !wild(q) {
        let mut ts = fields(q, &types[0], cons);
        let n = ts.len();
        ts.extend_from_slice(&types[1..]);
        let mut qs = match q {
            Pat::Con(_, ps) => ps.clone(),
            _ => vec![],
        };
        qs.extend_from_slice(&query[1..]);
        let mut witness =
            useful(&specialize(matrix, q, n), &qs, &ts, cons)?;
        let children = witness.drain(..n).collect();
        let p = match q {
            Pat::Con(c, _) => Pat::Con(c.clone(), children),
            _ => q.clone(),
        };
        witness.insert(0, p);
        return Some(witness);
    }
    let heads = matrix
        .iter()
        .filter(|r| !wild(&r[0]))
        .map(|r| peel(&r[0]).clone())
        .collect::<Vec<_>>();
    let all = family(&types[0], cons);
    if !all.is_empty()
        && all.iter().all(|h| heads.iter().any(|p| same(h, p)))
    {
        for head in all {
            let mut ts = fields(&head, &types[0], cons);
            let n = ts.len();
            ts.extend_from_slice(&types[1..]);
            let mut qs = vec![Pat::Wild; n];
            qs.extend_from_slice(&query[1..]);
            if let Some(mut w) =
                useful(&specialize(matrix, &head, n), &qs, &ts, cons)
            {
                let children = w.drain(..n).collect();
                let Pat::Con(c, _) = head else { unreachable!() };
                w.insert(0, Pat::Con(c, children));
                return Some(w);
            }
        }
        None
    } else {
        let defaults = matrix
            .iter()
            .filter(|r| wild(&r[0]))
            .map(|r| r[1..].to_vec())
            .collect::<Vec<_>>();
        let mut witness =
            useful(&defaults, &query[1..], &types[1..], cons)?;
        let missing = all
            .into_iter()
            .find(|h| !heads.iter().any(|p| same(h, p)))
            .unwrap_or_else(|| {
                for n in 0..=heads.len() {
                    let p = match types[0] {
                        Type::Int => Pat::Lit(Lit::Int(n as i64)),
                        Type::Char => Pat::Lit(Lit::Char(
                            char::from_u32(97 + n as u32).unwrap_or('\0'),
                        )),
                        Type::String => {
                            Pat::Lit(Lit::String("x".repeat(n)))
                        }
                        Type::Double => {
                            Pat::Lit(Lit::Double((n as f64).to_bits()))
                        }
                        _ => return Pat::Wild,
                    };
                    if !heads.iter().any(|h| same(&p, h)) {
                        return p;
                    }
                }
                unreachable!()
            });
        witness.insert(0, missing);
        Some(witness)
    }
}
fn covers(
    body: &RowBody,
    truths: &std::collections::BTreeSet<u32>,
) -> bool {
    match body {
        RowBody::Plain(_) => true,
        RowBody::Guarded(gs) => gs.iter().any(|(g, _)| match g {
            crate::core::Expr::Con(c, _, _) => c.name == "True",
            crate::core::Expr::Global(id) => truths.contains(&id.unique()),
            _ => false,
        }),
    }
}
/// Warnings do not alter the decision tree; unmatched execution still fails at runtime.
pub fn warn(
    sess: &mut Session,
    m: &Match,
    cons: &[ConDecl],
    truths: &std::collections::BTreeSet<u32>,
) {
    let types = m.scruts.iter().map(|i| i.ty.clone()).collect::<Vec<_>>();
    let mut matrix = vec![];
    for (index, row) in m.rows.iter().enumerate() {
        if useful(&matrix, &row.pats, &types, cons).is_none()
            && !(index > 0 && m.rows[index - 1].span == row.span)
        {
            let mut d = Diagnostic::error(
                ErrorCode::Redundant,
                "clause can never match",
                row.span,
            );
            d.severity = Severity::Warning;
            sess.emit(d);
        }
        if covers(&row.body, truths) {
            matrix.push(row.pats.clone())
        }
    }
    let mut missing = vec![];
    for _ in 0..3 {
        let Some(p) =
            useful(&matrix, &vec![Pat::Wild; types.len()], &types, cons)
        else {
            break;
        };
        missing.push(
            p.iter()
                .map(ToString::to_string)
                .collect::<Vec<_>>()
                .join(" "),
        );
        matrix.push(p)
    }
    if !missing.is_empty() {
        let mut d = Diagnostic::error(
            ErrorCode::NonExhaustive,
            "non-exhaustive pattern match",
            m.span,
        );
        d.severity = Severity::Warning;
        d.notes.push(format!("missing: {}", missing.join("; ")));
        sess.emit(d)
    }
}
}

Generated do-pattern fallback rows share the originating span. The diagnostic pass suppresses redundant warnings for those synthetic adjacent rows, while retaining warnings for source clauses. Warning analysis does not choose the runtime branches. A mistake in a warning must not silently change evaluation.

Core lint now checks flat alternative shape, constructor field types, globally unique binders, and join argument types and arities. A jump must be in tail position relative to its join. Entering a non-tail subexpression clears the available outer joins. The subexpression may establish its own local joins. The Core interpreter keeps evaluation and return frames in an explicit vector. A source call changes the current expression and environment rather than calling Rust recursively. A jump unwinds frames to its lexical join and transfers control to that body. Closures borrow code through stable indices, so calling a function does not clone its syntax tree. Constructor and environment destruction also use a worklist, preventing a long list from overflowing the stack when released. Tests run non-tail recursion and list reclamation on a 256 KiB host stack.

Saved environments share an immutable balanced tree. Capturing a scope copies one Rc, while adding a binding copies only the search path. env.rs implements the update with a work vector. This keeps a growing scope from being copied in full whenever the interpreter saves a continuation. Recursive closures refer to a machine-owned group by index, so calls reuse the group without creating a reference-count cycle.

Running It

$ cd crates/ch16_match
$ cargo run -q -- run tests/programs/match/guard-fallback.fun --lint
42
$ cargo run -q -- dump --pass=types tests/programs/match/guard-fallback.fun
main : IO ()

For the transformation itself, dump the same file with --pass=core and then --pass=match. The former retains nested Match. The latter exposes flat Case, right-hand-side joins, and guard-failure jumps. The dumps include the Prelude, so the small no-Prelude cases in tests/matches.rs are useful for studying one decision tree at a time.

We check the translation by running matches both before and after compilation. Coverage needs its own check. For small Boolean patterns we can enumerate all possible inputs and compare that direct answer with the usefulness algorithm. This catches a different kind of mistake from a wrong runtime branch.

Exercises

Warm-up. Draw the decision tree for the example and mark the failing guard’s destination.
Intermediate. Add a wildcard clause before a constructor clause and predict the redundant-clause warning before running the checker.
Intermediate. Specialize a two-column matrix whose first row begins with a variable and whose second pattern is a constructor.
Advanced. Change the column heuristic in an experimental copy. Compare tree sizes while keeping the full before/after execution corpus unchanged.
Advanced. Construct malformed Core that jumps to an outer join from a non-tail expression, and explain the continuation that would be discarded.

Write You a Haskell