match_lang/lib.rs
1//! # match-lang
2//!
3//! Exhaustiveness and usefulness checking for pattern matching, generic over
4//! a language's types.
5//!
6//! Give it the arms of a match and the type being matched, and it tells you
7//! which values no arm handles (with a concrete pattern for each), which arms
8//! can never be reached, and which alternatives of an or-pattern are
9//! redundant. A language plugs in by implementing [`Model`]: for each of its
10//! types, a [`Signature`] saying which constructors build its values, and the
11//! field types of each constructor. The crate knows nothing else about the
12//! language, so every language in the family shares one implementation.
13//!
14//! ## Quick start
15//!
16//! ```
17//! use match_lang::{check, Arm, Model, Pat, Signature};
18//!
19//! // The language: `bool` and `Option<T>`.
20//! #[derive(Clone)]
21//! enum Ty {
22//! Bool,
23//! Option(Box<Ty>),
24//! }
25//!
26//! struct Lang;
27//!
28//! impl Model for Lang {
29//! type Ty = Ty;
30//!
31//! fn signature(&self, ty: &Ty) -> Signature<Ty> {
32//! match ty {
33//! Ty::Bool => Signature::Bool,
34//! Ty::Option(_) => Signature::Sum { count: 2 }, // None, Some
35//! }
36//! }
37//!
38//! fn fields(&self, ty: &Ty, variant: u32, out: &mut Vec<Ty>) {
39//! if let (Ty::Option(inner), 1) = (ty, variant) {
40//! out.push((**inner).clone());
41//! }
42//! }
43//!
44//! fn variant_name(&self, _: &Ty, variant: u32) -> Option<&str> {
45//! Some(if variant == 0 { "None" } else { "Some" })
46//! }
47//! }
48//!
49//! // match x: Option<bool> { Some(true) => .., None => .., Some(true) => .. }
50//! let arms = [
51//! Arm::new(Pat::variant(1, [Pat::bool(true)])),
52//! Arm::new(Pat::variant(0, [])),
53//! Arm::new(Pat::variant(1, [Pat::bool(true)])),
54//! ];
55//! let report = check(&Lang, &Ty::Option(Box::new(Ty::Bool)), &arms)?;
56//!
57//! assert!(!report.is_exhaustive());
58//! assert_eq!(report.missing()[0].display(&Lang).to_string(), "Some(false)");
59//! assert_eq!(report.unreachable(), &[2]);
60//! # Ok::<(), match_lang::Error>(())
61//! ```
62//!
63//! ## What it handles
64//!
65//! - **Sums, products, booleans**, with fields to any depth. Sum variants
66//! whose fields include an empty type (see [`Model::is_empty`]) have no
67//! values: they are never required, and arms matching only them are
68//! unreachable.
69//! - **Integers and characters**, with literals and inclusive ranges over the
70//! type's exact bounds, so `0..=127 | 128..=255` covers a `u8`. Unbounded
71//! integers ([`Signature::BigInt`]) and opaque literals such as strings
72//! ([`Signature::Opaque`]) always need a wildcard.
73//! - **Arrays and slices**: fixed-length patterns `[a, b]` and rest patterns
74//! `[a, .., z]`, over fixed-length arrays and variable-length slices.
75//! - **Or-patterns**, nested anywhere; each redundant alternative is
76//! reported on its own.
77//! - **Guards**: a guarded arm may fail, so it never covers a value for
78//! exhaustiveness and never makes a later arm unreachable.
79//!
80//! ## How it works
81//!
82//! This is the usefulness algorithm of Luc Maranget's *Warnings for pattern
83//! matching* (JFP 2007), in the form modern compilers use: one pass computes
84//! the usefulness of every row of the pattern matrix, columns are split into
85//! the constructors their patterns mention plus one constructor standing for
86//! all the missing ones (integer and character ranges are cut into disjoint
87//! segments; slice lengths are grouped into a finite set), and witnesses are
88//! built on the way back. It runs on an explicit stack, not recursion, and
89//! rows share their tails, so deep or wide matches cost no call stack and no
90//! quadratic copying. Deciding exhaustiveness is NP-hard in general; every
91//! unit of work counts against a step limit, and a match too complex to
92//! check is an [`Error::StepLimit`], never a hang.
93//!
94//! ## Tiers
95//!
96//! - [`check`]: one call with default limits.
97//! - [`Checker`]: the same, with configurable limits and buffers reused
98//! across checks.
99//!
100//! ## Features
101//!
102//! - `std` (default): nothing beyond `alloc` is used; without it the crate
103//! is `no_std`.
104//!
105//! The crate is `#![forbid(unsafe_code)]` and has no dependencies.
106
107#![cfg_attr(not(feature = "std"), no_std)]
108#![cfg_attr(docsrs, feature(doc_cfg))]
109#![forbid(unsafe_code)]
110#![deny(
111 warnings,
112 missing_docs,
113 unsafe_op_in_unsafe_fn,
114 unused_must_use,
115 unused_results,
116 clippy::unwrap_used,
117 clippy::expect_used,
118 clippy::panic,
119 clippy::todo,
120 clippy::unimplemented,
121 clippy::unreachable,
122 clippy::dbg_macro,
123 clippy::print_stdout,
124 clippy::print_stderr,
125 clippy::undocumented_unsafe_blocks
126)]
127
128extern crate alloc;
129
130mod checker;
131mod engine;
132mod error;
133mod model;
134mod pat;
135mod report;
136mod witness;
137
138pub use checker::{Checker, DEFAULT_STEP_LIMIT, DEFAULT_WITNESS_LIMIT};
139pub use error::{Error, Reason};
140pub use model::{Model, Signature};
141pub use pat::{Arm, Pat};
142pub use report::{Redundant, Report};
143pub use witness::{Ctor, Witness, WitnessDisplay, WitnessFields, WitnessRef};
144
145/// Checks `arms`, in order, against values of type `ty`: the one-call entry
146/// point, with the default limits. For many matches, or other limits, use a
147/// [`Checker`].
148///
149/// # Errors
150///
151/// - [`Error::InvalidPattern`] if a pattern does not fit the type it is
152/// matched against (checked before any analysis).
153/// - [`Error::StepLimit`] if the analysis needs more than
154/// [`DEFAULT_STEP_LIMIT`] steps.
155/// - [`Error::Model`] if the model answers inconsistently.
156/// - [`Error::TooLarge`] past `u32::MAX - 1` pattern nodes or matrix entries.
157///
158/// # Examples
159///
160/// ```
161/// use match_lang::{check, Arm, Model, Pat, Signature};
162///
163/// struct Bytes;
164///
165/// impl Model for Bytes {
166/// type Ty = ();
167/// fn signature(&self, _: &()) -> Signature<()> {
168/// Signature::Int { min: 0, max: 255 }
169/// }
170/// fn fields(&self, _: &(), _: u32, _: &mut Vec<()>) {}
171/// }
172///
173/// let arms = [
174/// Arm::new(Pat::range(0, 127)),
175/// Arm::new(Pat::range(128, 255)),
176/// Arm::new(Pat::int(7)),
177/// ];
178/// let report = check(&Bytes, &(), &arms)?;
179/// assert!(report.is_exhaustive());
180/// assert_eq!(report.unreachable(), &[2]);
181/// # Ok::<(), match_lang::Error>(())
182/// ```
183pub fn check<M: Model>(model: &M, ty: &M::Ty, arms: &[Arm]) -> Result<Report<M::Ty>, Error> {
184 Checker::new().check(model, ty, arms)
185}
186
187/// Compiles and runs the `rust` code blocks in `README.md` and `docs/API.md` as
188/// part of `cargo test`, so the published examples cannot drift from the API.
189///
190/// Present only while collecting doctests (`#[cfg(doctest)]`); it is not part of
191/// the public surface and does not appear in the built library or its docs.
192#[cfg(doctest)]
193#[doc = include_str!("../README.md")]
194#[doc = include_str!("../docs/API.md")]
195pub struct MarkdownDocTests;