Pruning Irrelevant Pattern Columns: How rustc's Match Checker Went From Exponential to Linear

// compiler/rustc_pattern_analysis/src/usefulness.rs:8-11, 110-135

//! The algorithm implemented here is inspired from the one described in [this
//! paper](http://moscova.inria.fr/~maranget/papers/warn/index.html). We have however changed it in
//! various ways to accommodate the variety of patterns that Rust supports. We thus explain our
//! version here, without being as precise.
...
//! # Specialization
//!
//! The examples in the previous section motivate the operation at the heart of the algorithm:
//! "specialization". It captures this idea of "removing one layer of constructor".
//!
//! `specialize(c, p)` takes a value-only constructor `c` and a pattern `p`, and returns a
//! pattern-tuple or nothing. It works as follows:
//!
//! - Specializing for the wrong constructor returns nothing
//!
//!   - `specialize(None, Some(p0)) := <nothing>`
//!   - `specialize([,,,], [p0]) := <nothing>`
//!
//! - Specializing for the correct constructor returns a tuple of the fields
//!
//!   - `specialize(Variant1, Variant1(p0, p1, p2)) := (p0, p1, p2)`
//!   - `specialize(Foo{ bar, baz, quz }, Foo { bar: p0, baz: p1, .. }) := (p0, p1, _)`
//!   - `specialize([,,,], [p0, .., p1]) := (p0, _, _, p1)`

// compiler/rustc_pattern_analysis/src/usefulness.rs:302-361

//! Relevancy allowed us to skip the case `(true, true, _)` entirely. In some cases this pruning can
//! give drastic speedups. The case this was built for is the following (#118437):
//!
//! ```ignore(illustrative)
//! match foo {
//!     (true, _, _, _, ..) => 1,
//!     (_, true, _, _, ..) => 2,
//!     (_, _, true, _, ..) => 3,
//!     (_, _, _, true, ..) => 4,
//!     ...
//! }
//! ```
//!
//! Without considering relevancy, we would explore all 2^n combinations of the `true` and `Missing`
//! constructors. Relevancy tells us that e.g. `(true, true, false, false, false, ...)` is
//! irrelevant for all the rows. This allows us to skip all cases with more than one `true`
//! constructor, changing the runtime from exponential to linear.

// compiler/rustc_pattern_analysis/src/usefulness.rs:1018-1025

struct PatStack<'p, Cx: PatCx> {
    // Rows of len 1 are very common, which is why `SmallVec[_; 2]` works well.
    pats: SmallVec<[PatOrWild<'p, Cx>; 2]>,
    /// Sometimes we know that as far as this row is concerned, the current case is already handled
    /// by a different, more general, case. When the case is irrelevant for all rows this allows us
    /// to skip a case entirely. This is purely an optimization. See at the top for details.
    relevant: bool,
}

// compiler/rustc_pattern_analysis/src/usefulness.rs:1081-1085

// `ctor` is relevant for this row if it is the actual constructor of this row, or if the
// row has a wildcard and `ctor` is relevant for wildcards.
let ctor_is_relevant =
    !matches!(self.head().ctor(), Constructor::Wildcard) || ctor_is_relevant;
Ok(PatStack { pats: new_pats, relevant: self.relevant && ctor_is_relevant })

// compiler/rustc_pattern_analysis/src/usefulness.rs:1704-1709

if !matrix.wildcard_row_is_relevant && matrix.rows().all(|r| !r.pats.relevant) {
    // Here we know that nothing will contribute further to exhaustiveness or usefulness. This
    // is purely an optimization: skipping this check doesn't affect correctness. See the top of the
    // file for details.
    return Ok(WitnessMatrix::empty());
}

// compiler/rustc_pattern_analysis/src/usefulness.rs:1739-1748

for ctor in split_ctors {
    // Dig into rows that match `ctor`.
    debug!("specialize({:?})", ctor);
    // `ctor` is *irrelevant* if there's another constructor in `split_ctors` that matches
    // strictly fewer rows. In that case we can sometimes skip it. See the top of the file for
    // details.
    let ctor_is_relevant = matches!(ctor, Constructor::Missing)
        || missing_ctors.is_empty()
        || mcx.tycx.exhaustive_witnesses();

// compiler/rustc_pattern_analysis/src/constructor.rs:1011-1037

/// Describes the result of analyzing the constructors in a column of a match.
///
/// `present` is morally the set of constructors present in the column, and `missing` is the set of
/// constructors that exist in the type but are not present in the column.
///
/// More formally, if we discard wildcards from the column, this respects the following constraints:
/// 1. the union of `present`, `missing` and `missing_empty` covers all the constructors of the type
/// 2. each constructor in `present` is covered by something in the column
/// 3. no constructor in `missing` or `missing_empty` is covered by anything in the column
/// 4. each constructor in the column is equal to the union of one or more constructors in `present`
/// 5. `missing` does not contain empty constructors (see discussion about emptiness at the top of
///    the file);
/// 6. `missing_empty` contains only empty constructors
/// 7. constructors in `present`, `missing` and `missing_empty` are split for the column; in other
///    words, they are either fully included in or fully disjoint from each constructor in the
///    column. In yet other words, there are no non-trivial intersections like between `0..10` and
///    `5..15`.

// compiler/rustc_pattern_analysis/src/constructor.rs:36-49

//! Constructor splitting looks at the constructors in the first column of the matrix and constructs
//! such a sensible set of constructors. Formally, we want to find a smallest disjoint set of
//! constructors:
//! - Whose union covers the whole type, and
//! - That have no non-trivial intersection with any of the constructors in the column (i.e. they're
//!     each either disjoint with or covered by any given column constructor).
//!
//! We compute this in two steps: first [`PatCx::ctors_for_ty`] determines the
//! set of all possible constructors for the type. Then [`ConstructorSet::split`] looks at the
//! column of constructors and splits the set into groups accordingly. The precise invariants of
//! [`ConstructorSet::split`] is described in [`SplitConstructorSet`].

// compiler/rustc_pattern_analysis/src/usefulness.rs:1548-1579

fn apply_constructor(
    &mut self,
    pcx: &PlaceCtxt<'_, Cx>,
    missing_ctors: &[Constructor<Cx>],
    ctor: &Constructor<Cx>,
) {
    ...
    if matches!(ctor, Constructor::Missing) {
        // We got the special `Missing` constructor that stands for the constructors not present
        // in the match. For each missing constructor `c`, we add a `c(_, _, _)` witness
        // appropriately filled with wildcards.
        let mut ret = Self::empty();
        for ctor in missing_ctors {
            let pat = pcx.wild_from_ctor(ctor.clone());
            // Clone `self` and add `c(_, _, _)` to each of its witnesses.
            let mut wit_matrix = self.clone();
            wit_matrix.push_pattern(pat);
            ret.extend(wit_matrix);
        }
        *self = ret;
    } else {
        // Any other constructor we unspecialize as expected.
        for witness in std::mem::take(&mut self.0) {
            self.0.extend(witness.apply_constructor(pcx, ctor));
        }
    }
}

// compiler/rustc_pattern_analysis/src/usefulness.rs:1317-1334

fn unspecialize(&mut self, specialized: Self) {
    for child_row in specialized.rows() {
        let parent_row_id = child_row.parent_row;
        let parent_row = &mut self.rows[parent_row_id];
        // A parent row is useful if any of its children is.
        parent_row.useful |= child_row.useful;
        ...