diff options
Diffstat (limited to 'compiler')
3 files changed, 1013 insertions, 764 deletions
diff --git a/compiler/rustc_mir_build/src/thir/pattern/check_match.rs b/compiler/rustc_mir_build/src/thir/pattern/check_match.rs index 4cc3bbfcf43..e402468f038 100644 --- a/compiler/rustc_mir_build/src/thir/pattern/check_match.rs +++ b/compiler/rustc_mir_build/src/thir/pattern/check_match.rs @@ -279,8 +279,10 @@ impl<'thir, 'p, 'tcx> MatchVisitor<'thir, 'p, 'tcx> { } else { // Check the pattern for some things unrelated to exhaustiveness. let refutable = if cx.refutable { Refutable } else { Irrefutable }; - pat.walk_always(|pat| check_borrow_conflicts_in_at_patterns(self, pat)); - pat.walk_always(|pat| check_for_bindings_named_same_as_variants(self, pat, refutable)); + pat.walk_always(|pat| { + check_borrow_conflicts_in_at_patterns(self, pat); + check_for_bindings_named_same_as_variants(self, pat, refutable); + }); Ok(cx.pattern_arena.alloc(DeconstructedPat::from_pat(cx, pat))) } } @@ -289,6 +291,7 @@ impl<'thir, 'p, 'tcx> MatchVisitor<'thir, 'p, 'tcx> { &self, refutability: RefutableFlag, match_span: Option<Span>, + scrut_span: Span, ) -> MatchCheckCtxt<'p, 'tcx> { let refutable = match refutability { Irrefutable => false, @@ -299,7 +302,9 @@ impl<'thir, 'p, 'tcx> MatchVisitor<'thir, 'p, 'tcx> { param_env: self.param_env, module: self.tcx.parent_module(self.lint_level).to_def_id(), pattern_arena: self.pattern_arena, + match_lint_level: self.lint_level, match_span, + scrut_span, refutable, } } @@ -330,7 +335,8 @@ impl<'thir, 'p, 'tcx> MatchVisitor<'thir, 'p, 'tcx> { source: hir::MatchSource, expr_span: Span, ) { - let cx = self.new_cx(Refutable, Some(expr_span)); + let scrut = &self.thir[scrut]; + let cx = self.new_cx(Refutable, Some(expr_span), scrut.span); let mut tarms = Vec::with_capacity(arms.len()); for &arm in arms { @@ -346,9 +352,8 @@ impl<'thir, 'p, 'tcx> MatchVisitor<'thir, 'p, 'tcx> { } } - let scrut = &self.thir[scrut]; let scrut_ty = scrut.ty; - let report = compute_match_usefulness(&cx, &tarms, self.lint_level, scrut_ty, scrut.span); + let report = compute_match_usefulness(&cx, &tarms, scrut_ty); match source { // Don't report arm reachability of desugared `match $iter.into_iter() { iter => .. }` @@ -453,10 +458,10 @@ impl<'thir, 'p, 'tcx> MatchVisitor<'thir, 'p, 'tcx> { pat: &Pat<'tcx>, refutability: RefutableFlag, ) -> Result<(MatchCheckCtxt<'p, 'tcx>, UsefulnessReport<'p, 'tcx>), ErrorGuaranteed> { - let cx = self.new_cx(refutability, None); + let cx = self.new_cx(refutability, None, pat.span); let pat = self.lower_pattern(&cx, pat)?; let arms = [MatchArm { pat, hir_id: self.lint_level, has_guard: false }]; - let report = compute_match_usefulness(&cx, &arms, self.lint_level, pat.ty(), pat.span()); + let report = compute_match_usefulness(&cx, &arms, pat.ty()); Ok((cx, report)) } diff --git a/compiler/rustc_mir_build/src/thir/pattern/deconstruct_pat.rs b/compiler/rustc_mir_build/src/thir/pattern/deconstruct_pat.rs index 479f6c0a3ca..8ddc6c924e2 100644 --- a/compiler/rustc_mir_build/src/thir/pattern/deconstruct_pat.rs +++ b/compiler/rustc_mir_build/src/thir/pattern/deconstruct_pat.rs @@ -1,46 +1,88 @@ -//! [`super::usefulness`] explains most of what is happening in this file. As explained there, -//! values and patterns are made from constructors applied to fields. This file defines a -//! `Constructor` enum, a `Fields` struct, and various operations to manipulate them and convert -//! them from/to patterns. +//! As explained in [`super::usefulness`], values and patterns are made from constructors applied to +//! fields. This file defines a `Constructor` enum, a `Fields` struct, and various operations to +//! manipulate them and convert them from/to patterns. //! -//! There's one idea that is not detailed in [`super::usefulness`] because the details are not -//! needed there: _constructor splitting_. +//! There are two important bits of core logic in this file: constructor inclusion and constructor +//! splitting. Constructor inclusion, i.e. whether a constructor is included in/covered by another, +//! is straightforward and defined in [`Constructor::is_covered_by`]. //! -//! # Constructor splitting +//! Constructor splitting is mentioned in [`super::usefulness`] but not detailed. We describe it +//! precisely here. //! -//! The idea is as follows: given a constructor `c` and a matrix, we want to specialize in turn -//! with all the value constructors that are covered by `c`, and compute usefulness for each. -//! Instead of listing all those constructors (which is intractable), we group those value -//! constructors together as much as possible. Example: //! +//! # Constructor grouping and splitting +//! +//! As explained in the corresponding section in [`super::usefulness`], to make usefulness tractable +//! we need to group together constructors that have the same effect when they are used to +//! specialize the matrix. +//! +//! Example: //! ```compile_fail,E0004 //! match (0, false) { -//! (0 ..=100, true) => {} // `p_1` -//! (50..=150, false) => {} // `p_2` -//! (0 ..=200, _) => {} // `q` +//! (0 ..=100, true) => {} +//! (50..=150, false) => {} +//! (0 ..=200, _) => {} //! } //! ``` //! -//! The naive approach would try all numbers in the range `0..=200`. But we can be a lot more -//! clever: `0` and `1` for example will match the exact same rows, and return equivalent -//! witnesses. In fact all of `0..50` would. We can thus restrict our exploration to 4 -//! constructors: `0..50`, `50..=100`, `101..=150` and `151..=200`. That is enough and infinitely -//! more tractable. +//! In this example we can restrict specialization to 5 cases: `0..50`, `50..=100`, `101..=150`, +//! `151..=200` and `200..`. +//! +//! In [`super::usefulness`], we had said that `specialize` only takes value-only constructors. We +//! now relax this restriction: we allow `specialize` to take constructors like `0..50` as long as +//! we're careful to only do that with constructors that make sense. For example, `specialize(0..50, +//! (0..=100, true))` is sensible, but `specialize(50..=200, (0..=100, true))` is not. +//! +//! 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 [`ConstructorSet::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`]. +//! +//! Constructor splitting has two interesting special cases: integer range splitting (see +//! [`IntRange::split`]) and slice splitting (see [`Slice::split`]). +//! +//! +//! # The `Missing` constructor +//! +//! We detail a special case of constructor splitting that is a bit subtle. Take the following: +//! +//! ``` +//! enum Direction { North, South, East, West } +//! # let wind = (Direction::North, 0u8); +//! match wind { +//! (Direction::North, 50..) => {} +//! (_, _) => {} +//! } +//! ``` +//! +//! Here we expect constructor splitting to output two cases: `North`, and "everything else". This +//! "everything else" is represented by [`Constructor::Missing`]. Unlike other constructors, it's a +//! bit contextual: to know the exact list of constructors it represents we have to look at the +//! column. In practice however we don't need to, because by construction it only matches rows that +//! have wildcards. This is how this constructor is special: the only constructor that covers it is +//! `Wildcard`. +//! +//! The only place where we care about which constructors `Missing` represents is in diagnostics +//! (see `super::usefulness::WitnessMatrix::apply_constructor`). //! -//! We capture this idea in a function `split(p_1 ... p_n, c)` which returns a list of constructors -//! `c'` covered by `c`. Given such a `c'`, we require that all value ctors `c''` covered by `c'` -//! return an equivalent set of witnesses after specializing and computing usefulness. -//! In the example above, witnesses for specializing by `c''` covered by `0..50` will only differ -//! in their first element. +//! We choose whether to specialize with `Missing` in +//! `super::usefulness::compute_exhaustiveness_and_reachability`. //! -//! We usually also ask that the `c'` together cover all of the original `c`. However we allow -//! skipping some constructors as long as it doesn't change whether the resulting list of witnesses -//! is empty of not. We use this in the wildcard `_` case. //! -//! Splitting is implemented in the [`Constructor::split`] function. We don't do splitting for -//! or-patterns; instead we just try the alternatives one-by-one. For details on splitting -//! wildcards, see [`Constructor::split`]; for integer ranges, see -//! [`IntRange::split`]; for slices, see [`Slice::split`]. +//! +//! ## Opaque patterns +//! +//! Some patterns, such as constants that are not allowed to be matched structurally, cannot be +//! inspected, which we handle with `Constructor::Opaque`. Since we know nothing of these patterns, +//! we assume they never cover each other. In order to respect the invariants of +//! [`SplitConstructorSet`], we give each `Opaque` constructor a unique id so we can recognize it. use std::cell::Cell; use std::cmp::{self, max, min, Ordering}; @@ -617,6 +659,18 @@ impl Slice { } } +/// A globally unique id to distinguish `Opaque` patterns. +#[derive(Clone, Debug, PartialEq, Eq)] +pub(super) struct OpaqueId(u32); + +impl OpaqueId { + fn new() -> Self { + use std::sync::atomic::{AtomicU32, Ordering}; + static OPAQUE_ID: AtomicU32 = AtomicU32::new(0); + OpaqueId(OPAQUE_ID.fetch_add(1, Ordering::SeqCst)) + } +} + /// A value can be decomposed into a constructor applied to some fields. This struct represents /// the constructor. See also `Fields`. /// @@ -626,8 +680,8 @@ impl Slice { /// `Fields`. #[derive(Clone, Debug, PartialEq)] pub(super) enum Constructor<'tcx> { - /// The constructor for patterns that have a single constructor, like tuples, struct patterns - /// and fixed-length arrays. + /// The constructor for patterns that have a single constructor, like tuples, struct patterns, + /// and references. Fixed-length arrays are treated separately with `Slice`. Single, /// Enum variants. Variant(VariantIdx), @@ -642,10 +696,12 @@ pub(super) enum Constructor<'tcx> { Str(mir::Const<'tcx>), /// Array and slice patterns. Slice(Slice), - /// Constants that must not be matched structurally. They are treated as black - /// boxes for the purposes of exhaustiveness: we must not inspect them, and they - /// don't count towards making a match exhaustive. - Opaque, + /// Constants that must not be matched structurally. They are treated as black boxes for the + /// purposes of exhaustiveness: we must not inspect them, and they don't count towards making a + /// match exhaustive. + /// Carries an id that must be unique within a match. We need this to ensure the invariants of + /// [`SplitConstructorSet`]. + Opaque(OpaqueId), /// Or-pattern. Or, /// Wildcard pattern. @@ -657,12 +713,15 @@ pub(super) enum Constructor<'tcx> { /// We use this for variants behind an unstable gate as well as /// `#[doc(hidden)]` ones. Hidden, - /// Fake extra constructor for constructors that are not seen in the matrix, as explained in the - /// code for [`Constructor::split`]. + /// Fake extra constructor for constructors that are not seen in the matrix, as explained at the + /// top of the file. Missing, } impl<'tcx> Constructor<'tcx> { + pub(super) fn is_wildcard(&self) -> bool { + matches!(self, Wildcard) + } pub(super) fn is_non_exhaustive(&self) -> bool { matches!(self, NonExhaustive) } @@ -728,7 +787,7 @@ impl<'tcx> Constructor<'tcx> { | F32Range(..) | F64Range(..) | Str(..) - | Opaque + | Opaque(..) | NonExhaustive | Hidden | Missing { .. } @@ -737,109 +796,23 @@ impl<'tcx> Constructor<'tcx> { } } - /// Some constructors (namely `Wildcard`, `IntRange` and `Slice`) actually stand for a set of - /// actual constructors (like variants, integers or fixed-sized slices). When specializing for - /// these constructors, we want to be specialising for the actual underlying constructors. - /// Naively, we would simply return the list of constructors they correspond to. We instead are - /// more clever: if there are constructors that we know will behave the same w.r.t. the current - /// matrix, we keep them grouped. For example, all slices of a sufficiently large length will - /// either be all useful or all non-useful with a given matrix. - /// - /// See the branches for details on how the splitting is done. - /// - /// This function may discard some irrelevant constructors if this preserves behavior. Eg. for - /// the `_` case, we ignore the constructors already present in the column, unless all of them - /// are. - pub(super) fn split<'a>( - &self, - pcx: &PatCtxt<'_, '_, 'tcx>, - ctors: impl Iterator<Item = &'a Constructor<'tcx>> + Clone, - ) -> SmallVec<[Self; 1]> - where - 'tcx: 'a, - { - match self { - Wildcard => { - let split_set = ConstructorSet::for_ty(pcx.cx, pcx.ty).split(pcx, ctors); - if !split_set.missing.is_empty() { - // We are splitting a wildcard in order to compute its usefulness. Some constructors are - // not present in the column. The first thing we note is that specializing with any of - // the missing constructors would select exactly the rows with wildcards. Moreover, they - // would all return equivalent results. We can therefore group them all into a - // fictitious `Missing` constructor. - // - // As an important optimization, this function will skip all the present constructors. - // This is correct because specializing with any of the present constructors would - // select a strict superset of the wildcard rows, and thus would only find witnesses - // already found with the `Missing` constructor. - // This does mean that diagnostics are incomplete: in - // ``` - // match x { - // Some(true) => {} - // } - // ``` - // we report `None` as missing but not `Some(false)`. - // - // When all the constructors are missing we can equivalently return the `Wildcard` - // constructor on its own. The difference between `Wildcard` and `Missing` will then - // only be in diagnostics. - - // If some constructors are missing, we typically want to report those constructors, - // e.g.: - // ``` - // enum Direction { N, S, E, W } - // let Direction::N = ...; - // ``` - // we can report 3 witnesses: `S`, `E`, and `W`. - // - // However, if the user didn't actually specify a constructor - // in this arm, e.g., in - // ``` - // let x: (Direction, Direction, bool) = ...; - // let (_, _, false) = x; - // ``` - // we don't want to show all 16 possible witnesses `(<direction-1>, <direction-2>, - // true)` - we are satisfied with `(_, _, true)`. So if all constructors are missing we - // prefer to report just a wildcard `_`. - // - // The exception is: if we are at the top-level, for example in an empty match, we - // usually prefer to report the full list of constructors. - let all_missing = split_set.present.is_empty(); - let report_when_all_missing = - pcx.is_top_level && !IntRange::is_integral(pcx.ty); - let ctor = - if all_missing && !report_when_all_missing { Wildcard } else { Missing }; - smallvec![ctor] - } else { - split_set.present - } - } - // Fast-track if the range is trivial. - IntRange(this_range) if !this_range.is_singleton() => { - let column_ranges = ctors.filter_map(|ctor| ctor.as_int_range()).cloned(); - this_range.split(column_ranges).map(|(_, range)| IntRange(range)).collect() - } - Slice(this_slice @ Slice { kind: VarLen(..), .. }) => { - let column_slices = ctors.filter_map(|c| c.as_slice()); - this_slice.split(column_slices).map(|(_, slice)| Slice(slice)).collect() - } - // Any other constructor can be used unchanged. - _ => smallvec![self.clone()], - } - } - /// Returns whether `self` is covered by `other`, i.e. whether `self` is a subset of `other`. /// For the simple cases, this is simply checking for equality. For the "grouped" constructors, /// this checks for inclusion. // We inline because this has a single call site in `Matrix::specialize_constructor`. #[inline] pub(super) fn is_covered_by<'p>(&self, pcx: &PatCtxt<'_, 'p, 'tcx>, other: &Self) -> bool { - // This must be kept in sync with `is_covered_by_any`. match (self, other) { + (Wildcard, _) => { + span_bug!( + pcx.cx.scrut_span, + "Constructor splitting should not have returned `Wildcard`" + ) + } // Wildcards cover anything (_, Wildcard) => true, // Only a wildcard pattern can match these special constructors. - (Wildcard | Missing { .. } | NonExhaustive | Hidden, _) => false, + (Missing { .. } | NonExhaustive | Hidden, _) => false, (Single, Single) => true, (Variant(self_id), Variant(other_id)) => self_id == other_id, @@ -869,11 +842,13 @@ impl<'tcx> Constructor<'tcx> { } (Slice(self_slice), Slice(other_slice)) => self_slice.is_covered_by(*other_slice), - // We are trying to inspect an opaque constant. Thus we skip the row. - (Opaque, _) | (_, Opaque) => false, + // Opaque constructors don't interact with anything unless they come from the + // syntactically identical pattern. + (Opaque(self_id), Opaque(other_id)) => self_id == other_id, + (Opaque(..), _) | (_, Opaque(..)) => false, _ => span_bug!( - pcx.span, + pcx.cx.scrut_span, "trying to compare incompatible constructors {:?} and {:?}", self, other @@ -917,16 +892,20 @@ pub(super) enum ConstructorSet { /// `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, they respect the following constraints: -/// - the union of `present` and `missing` covers the whole type -/// - `present` and `missing` are disjoint -/// - neither contains wildcards -/// - each constructor in `present` is covered by some non-wildcard constructor in the column -/// - together, the constructors in `present` cover all the non-wildcard constructor in the column -/// - non-wildcards in the column do no cover anything in `missing` -/// - constructors in `present` and `missing` are split for the column; in other words, they are -/// either fully included in or disjoint from each constructor in the column. This avoids -/// non-trivial intersections like between `0..10` and `5..15`. +/// More formally, if we discard wildcards from the column, this respects the following constraints: +/// 1. the union of `present` and `missing` covers the whole type +/// 2. each constructor in `present` is covered by something in the column +/// 3. no constructor in `missing` 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. constructors in `present` and `missing` are split for the column; in other words, they are +/// either fully included in or fully disjoint from each constructor in the column. In other +/// words, there are no non-trivial intersections like between `0..10` and `5..15`. +/// +/// We must be particularly careful with weird constructors like `Opaque`: they're not formally part +/// of the `ConstructorSet` for the type, yet if we forgot to include them in `present` we would be +/// ignoring any row with `Opaque`s in the algorithm. Hence the importance of point 4. #[derive(Debug)] pub(super) struct SplitConstructorSet<'tcx> { pub(super) present: SmallVec<[Constructor<'tcx>; 1]>, @@ -934,6 +913,7 @@ pub(super) struct SplitConstructorSet<'tcx> { } impl ConstructorSet { + /// Creates a set that represents all the constructors of `ty`. #[instrument(level = "debug", skip(cx), ret)] pub(super) fn for_ty<'p, 'tcx>(cx: &MatchCheckCtxt<'p, 'tcx>, ty: Ty<'tcx>) -> Self { let make_range = |start, end| { @@ -1069,9 +1049,10 @@ impl ConstructorSet { } } - /// This is the core logical operation of exhaustiveness checking. This analyzes a column a - /// constructors to 1/ determine which constructors of the type (if any) are missing; 2/ split - /// constructors to handle non-trivial intersections e.g. on ranges or slices. + /// This analyzes a column of constructors to 1/ determine which constructors of the type (if + /// any) are missing; 2/ split constructors to handle non-trivial intersections e.g. on ranges + /// or slices. This can get subtle; see [`SplitConstructorSet`] for details of this operation + /// and its invariants. #[instrument(level = "debug", skip(self, pcx, ctors), ret)] pub(super) fn split<'a, 'tcx>( &self, @@ -1083,18 +1064,26 @@ impl ConstructorSet { { let mut present: SmallVec<[_; 1]> = SmallVec::new(); let mut missing = Vec::new(); - // Constructors in `ctors`, except wildcards. - let mut seen = ctors.filter(|c| !(matches!(c, Opaque | Wildcard))); + // Constructors in `ctors`, except wildcards and opaques. + let mut seen = Vec::new(); + for ctor in ctors.cloned() { + if let Constructor::Opaque(..) = ctor { + present.push(ctor); + } else if !ctor.is_wildcard() { + seen.push(ctor); + } + } + match self { ConstructorSet::Single => { - if seen.next().is_none() { + if seen.is_empty() { missing.push(Single); } else { present.push(Single); } } ConstructorSet::Variants { visible_variants, hidden_variants, non_exhaustive } => { - let seen_set: FxHashSet<_> = seen.map(|c| c.as_variant().unwrap()).collect(); + let seen_set: FxHashSet<_> = seen.iter().map(|c| c.as_variant().unwrap()).collect(); let mut skipped_a_hidden_variant = false; for variant in visible_variants { @@ -1125,7 +1114,7 @@ impl ConstructorSet { ConstructorSet::Bool => { let mut seen_false = false; let mut seen_true = false; - for b in seen.map(|ctor| ctor.as_bool().unwrap()) { + for b in seen.iter().map(|ctor| ctor.as_bool().unwrap()) { if b { seen_true = true; } else { @@ -1145,7 +1134,7 @@ impl ConstructorSet { } ConstructorSet::Integers { range_1, range_2 } => { let seen_ranges: Vec<_> = - seen.map(|ctor| ctor.as_int_range().unwrap().clone()).collect(); + seen.iter().map(|ctor| ctor.as_int_range().unwrap().clone()).collect(); for (seen, splitted_range) in range_1.split(seen_ranges.iter().cloned()) { match seen { Presence::Unseen => missing.push(IntRange(splitted_range)), @@ -1162,7 +1151,7 @@ impl ConstructorSet { } } &ConstructorSet::Slice(array_len) => { - let seen_slices = seen.map(|c| c.as_slice().unwrap()); + let seen_slices = seen.iter().map(|c| c.as_slice().unwrap()); let base_slice = Slice::new(array_len, VarLen(0, 0)); for (seen, splitted_slice) in base_slice.split(seen_slices) { let ctor = Slice(splitted_slice); @@ -1178,7 +1167,7 @@ impl ConstructorSet { // unreachable if length != 0. // We still gather the seen constructors in `present`, but the only slice that can // go in `missing` is `[]`. - let seen_slices = seen.map(|c| c.as_slice().unwrap()); + let seen_slices = seen.iter().map(|c| c.as_slice().unwrap()); let base_slice = Slice::new(None, VarLen(0, 0)); for (seen, splitted_slice) in base_slice.split(seen_slices) { let ctor = Slice(splitted_slice); @@ -1194,7 +1183,7 @@ impl ConstructorSet { ConstructorSet::Unlistable => { // Since we can't list constructors, we take the ones in the column. This might list // some constructors several times but there's not much we can do. - present.extend(seen.cloned()); + present.extend(seen); missing.push(NonExhaustive); } // If `exhaustive_patterns` is disabled and our scrutinee is an empty type, we cannot @@ -1210,19 +1199,6 @@ impl ConstructorSet { SplitConstructorSet { present, missing } } - - /// Compute the set of constructors missing from this column. - /// This is only used for reporting to the user. - pub(super) fn compute_missing<'a, 'tcx>( - &self, - pcx: &PatCtxt<'_, '_, 'tcx>, - ctors: impl Iterator<Item = &'a Constructor<'tcx>> + Clone, - ) -> Vec<Constructor<'tcx>> - where - 'tcx: 'a, - { - self.split(pcx, ctors).missing - } } /// A value can be decomposed into a constructor applied to some fields. This struct represents @@ -1273,9 +1249,8 @@ impl<'p, 'tcx> Fields<'p, 'tcx> { fn wildcards_from_tys( cx: &MatchCheckCtxt<'p, 'tcx>, tys: impl IntoIterator<Item = Ty<'tcx>>, - span: Span, ) -> Self { - Fields::from_iter(cx, tys.into_iter().map(|ty| DeconstructedPat::wildcard(ty, span))) + Fields::from_iter(cx, tys.into_iter().map(|ty| DeconstructedPat::wildcard(ty, DUMMY_SP))) } // In the cases of either a `#[non_exhaustive]` field list or a non-public field, we hide @@ -1311,18 +1286,18 @@ impl<'p, 'tcx> Fields<'p, 'tcx> { pub(super) fn wildcards(pcx: &PatCtxt<'_, 'p, 'tcx>, constructor: &Constructor<'tcx>) -> Self { let ret = match constructor { Single | Variant(_) => match pcx.ty.kind() { - ty::Tuple(fs) => Fields::wildcards_from_tys(pcx.cx, fs.iter(), pcx.span), - ty::Ref(_, rty, _) => Fields::wildcards_from_tys(pcx.cx, once(*rty), pcx.span), + ty::Tuple(fs) => Fields::wildcards_from_tys(pcx.cx, fs.iter()), + ty::Ref(_, rty, _) => Fields::wildcards_from_tys(pcx.cx, once(*rty)), ty::Adt(adt, args) => { if adt.is_box() { // The only legal patterns of type `Box` (outside `std`) are `_` and box // patterns. If we're here we can assume this is a box pattern. - Fields::wildcards_from_tys(pcx.cx, once(args.type_at(0)), pcx.span) + Fields::wildcards_from_tys(pcx.cx, once(args.type_at(0))) } else { let variant = &adt.variant(constructor.variant_index_for_adt(*adt)); let tys = Fields::list_variant_nonhidden_fields(pcx.cx, pcx.ty, variant) .map(|(_, ty)| ty); - Fields::wildcards_from_tys(pcx.cx, tys, pcx.span) + Fields::wildcards_from_tys(pcx.cx, tys) } } _ => bug!("Unexpected type for `Single` constructor: {:?}", pcx), @@ -1330,7 +1305,7 @@ impl<'p, 'tcx> Fields<'p, 'tcx> { Slice(slice) => match *pcx.ty.kind() { ty::Slice(ty) | ty::Array(ty, _) => { let arity = slice.arity(); - Fields::wildcards_from_tys(pcx.cx, (0..arity).map(|_| ty), pcx.span) + Fields::wildcards_from_tys(pcx.cx, (0..arity).map(|_| ty)) } _ => bug!("bad slice pattern {:?} {:?}", constructor, pcx), }, @@ -1339,7 +1314,7 @@ impl<'p, 'tcx> Fields<'p, 'tcx> { | F32Range(..) | F64Range(..) | Str(..) - | Opaque + | Opaque(..) | NonExhaustive | Hidden | Missing { .. } @@ -1388,6 +1363,8 @@ impl<'p, 'tcx> DeconstructedPat<'p, 'tcx> { DeconstructedPat { ctor, fields, ty, span, reachable: Cell::new(false) } } + /// Note: the input patterns must have been lowered through + /// `super::check_match::MatchVisitor::lower_pattern`. pub(crate) fn from_pat(cx: &MatchCheckCtxt<'p, 'tcx>, pat: &Pat<'tcx>) -> Self { let mkpat = |pat| DeconstructedPat::from_pat(cx, pat); let ctor; @@ -1470,14 +1447,14 @@ impl<'p, 'tcx> DeconstructedPat<'p, 'tcx> { ty::Bool => { ctor = match value.try_eval_bool(cx.tcx, cx.param_env) { Some(b) => Bool(b), - None => Opaque, + None => Opaque(OpaqueId::new()), }; fields = Fields::empty(); } ty::Char | ty::Int(_) | ty::Uint(_) => { ctor = match value.try_eval_bits(cx.tcx, cx.param_env) { Some(bits) => IntRange(IntRange::from_bits(cx.tcx, pat.ty, bits)), - None => Opaque, + None => Opaque(OpaqueId::new()), }; fields = Fields::empty(); } @@ -1488,7 +1465,7 @@ impl<'p, 'tcx> DeconstructedPat<'p, 'tcx> { let value = rustc_apfloat::ieee::Single::from_bits(bits); F32Range(value, value, RangeEnd::Included) } - None => Opaque, + None => Opaque(OpaqueId::new()), }; fields = Fields::empty(); } @@ -1499,7 +1476,7 @@ impl<'p, 'tcx> DeconstructedPat<'p, 'tcx> { let value = rustc_apfloat::ieee::Double::from_bits(bits); F64Range(value, value, RangeEnd::Included) } - None => Opaque, + None => Opaque(OpaqueId::new()), }; fields = Fields::empty(); } @@ -1520,7 +1497,7 @@ impl<'p, 'tcx> DeconstructedPat<'p, 'tcx> { // into the corresponding `Pat`s by `const_to_pat`. Constants that remain are // opaque. _ => { - ctor = Opaque; + ctor = Opaque(OpaqueId::new()); fields = Fields::empty(); } } @@ -1581,7 +1558,7 @@ impl<'p, 'tcx> DeconstructedPat<'p, 'tcx> { fields = Fields::from_iter(cx, pats.into_iter().map(mkpat)); } PatKind::Error(_) => { - ctor = Opaque; + ctor = Opaque(OpaqueId::new()); fields = Fields::empty(); } } @@ -1591,6 +1568,7 @@ impl<'p, 'tcx> DeconstructedPat<'p, 'tcx> { pub(super) fn is_or_pat(&self) -> bool { matches!(self.ctor, Or) } + /// Expand this (possibly-nested) or-pattern into its alternatives. pub(super) fn flatten_or_pat(&'p self) -> SmallVec<[&'p Self; 1]> { if self.is_or_pat() { self.iter_fields().flat_map(|p| p.flatten_or_pat()).collect() @@ -1646,7 +1624,7 @@ impl<'p, 'tcx> DeconstructedPat<'p, 'tcx> { let wildcard: &_ = pcx .cx .pattern_arena - .alloc(DeconstructedPat::wildcard(inner_ty, pcx.span)); + .alloc(DeconstructedPat::wildcard(inner_ty, DUMMY_SP)); let extra_wildcards = other_slice.arity() - self_slice.arity(); let extra_wildcards = (0..extra_wildcards).map(|_| wildcard); prefix.iter().chain(extra_wildcards).chain(suffix).collect() @@ -1663,7 +1641,17 @@ impl<'p, 'tcx> DeconstructedPat<'p, 'tcx> { self.reachable.set(true) } pub(super) fn is_reachable(&self) -> bool { - self.reachable.get() + if self.reachable.get() { + true + } else if self.is_or_pat() && self.iter_fields().any(|f| f.is_reachable()) { + // We always expand or patterns in the matrix, so we will never see the actual + // or-pattern (the one with constructor `Or`) in the column. As such, it will not be + // marked as reachable itself, only its children will. We recover this information here. + self.set_reachable(); + true + } else { + false + } } /// Report the spans of subpatterns that were not reachable, if any. @@ -1672,7 +1660,6 @@ impl<'p, 'tcx> DeconstructedPat<'p, 'tcx> { self.collect_unreachable_spans(&mut spans); spans } - fn collect_unreachable_spans(&self, spans: &mut Vec<Span>) { // We don't look at subpatterns if we already reported the whole pattern as unreachable. if !self.is_reachable() { @@ -1768,7 +1755,7 @@ impl<'p, 'tcx> fmt::Debug for DeconstructedPat<'p, 'tcx> { F32Range(lo, hi, end) => write!(f, "{lo}{end}{hi}"), F64Range(lo, hi, end) => write!(f, "{lo}{end}{hi}"), Str(value) => write!(f, "{value}"), - Opaque => write!(f, "<constant pattern>"), + Opaque(..) => write!(f, "<constant pattern>"), Or => { for pat in self.iter_fields() { write!(f, "{}{:?}", start_or_continue(" | "), pat)?; @@ -1898,7 +1885,7 @@ impl<'tcx> WitnessPat<'tcx> { "trying to convert a `Missing` constructor into a `Pat`; this is probably a bug, `Missing` should have been processed in `apply_constructors`" ), - F32Range(..) | F64Range(..) | Opaque | Or => { + F32Range(..) | F64Range(..) | Opaque(..) | Or => { bug!("can't convert to pattern: {:?}", self) } }; diff --git a/compiler/rustc_mir_build/src/thir/pattern/usefulness.rs b/compiler/rustc_mir_build/src/thir/pattern/usefulness.rs index 461c44a169c..8f017833531 100644 --- a/compiler/rustc_mir_build/src/thir/pattern/usefulness.rs +++ b/compiler/rustc_mir_build/src/thir/pattern/usefulness.rs @@ -1,46 +1,55 @@ -//! Note: tests specific to this file can be found in: +//! # Match exhaustiveness and reachability algorithm //! -//! - `ui/pattern/usefulness` -//! - `ui/or-patterns` -//! - `ui/consts/const_in_pattern` -//! - `ui/rfc-2008-non-exhaustive` -//! - `ui/half-open-range-patterns` -//! - probably many others +//! This file contains the logic for exhaustiveness and reachability checking for pattern-matching. +//! Specifically, given a list of patterns in a match, we can tell whether: +//! (a) a given pattern is reachable (reachability) +//! (b) the patterns cover every possible value for the type (exhaustiveness) //! -//! I (Nadrieril) prefer to put new tests in `ui/pattern/usefulness` unless there's a specific -//! reason not to, for example if they depend on a particular feature like `or_patterns`. +//! 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. //! -//! ----- +//! Fun fact: computing exhaustiveness is NP-complete, because we can encode a SAT problem as an +//! exhaustiveness problem. See [here](https://niedzejkob.p4.team/rust-np) for the fun details. //! -//! This file includes the logic for exhaustiveness and reachability checking for pattern-matching. -//! Specifically, given a list of patterns for a type, we can tell whether: -//! (a) each pattern is reachable (reachability) -//! (b) the patterns cover every possible value for the type (exhaustiveness) //! -//! The algorithm implemented here is a modified version of the one described in [this -//! paper](http://moscova.inria.fr/~maranget/papers/warn/index.html). We have however generalized -//! it to accommodate the variety of patterns that Rust supports. We thus explain our version here, -//! without being as rigorous. +//! # Summary //! +//! The algorithm is given as input a list of patterns, one for each arm of a match, and computes +//! the following: +//! - a set of values that match none of the patterns (if any), +//! - for each subpattern (taking into account or-patterns), whether it would catch any value that +//! isn't caught by a pattern before it, i.e. whether it is reachable. //! -//! # Summary +//! To a first approximation, the algorithm works by exploring all possible values for the type +//! being matched on, and determining which arm(s) catch which value. To make this tractable we +//! cleverly group together values, as we'll see below. //! -//! The core of the algorithm is the notion of "usefulness". A pattern `q` is said to be *useful* -//! relative to another pattern `p` of the same type if there is a value that is matched by `q` and -//! not matched by `p`. This generalizes to many `p`s: `q` is useful w.r.t. a list of patterns -//! `p_1 .. p_n` if there is a value that is matched by `q` and by none of the `p_i`. We write -//! `usefulness(p_1 .. p_n, q)` for a function that returns a list of such values. The aim of this -//! file is to compute it efficiently. -//! -//! This is enough to compute reachability: a pattern in a `match` expression is reachable iff it -//! is useful w.r.t. the patterns above it: -//! ```rust -//! # fn foo(x: Option<i32>) { -//! match x { -//! Some(_) => {}, -//! None => {}, // reachable: `None` is matched by this but not the branch above -//! Some(0) => {}, // unreachable: all the values this matches are already matched by -//! // `Some(_)` above +//! The entrypoint of this file is the [`compute_match_usefulness`] function, which computes +//! reachability for each subpattern and exhaustiveness for the whole match. +//! +//! In this page we explain the necessary concepts to understand how the algorithm works. +//! +//! +//! # Usefulness +//! +//! The central concept of this file is the notion of "usefulness". Given some patterns `p_1 .. +//! p_n`, a pattern `q` is said to be *useful* if there is a value that is matched by `q` and by +//! none of the `p_i`. We write `usefulness(p_1 .. p_n, q)` for a function that returns a list of +//! such values. The aim of this file is to compute it efficiently. +//! +//! This is enough to compute reachability: a pattern in a `match` expression is reachable iff it is +//! useful w.r.t. the patterns above it: +//! ```compile_fail,E0004 +//! # #![feature(exclusive_range_pattern)] +//! # fn foo() { +//! match Some(0u32) { +//! Some(0..100) => {}, +//! Some(90..190) => {}, // reachable: `Some(150)` is matched by this but not the branch above +//! Some(50..150) => {}, // unreachable: all the values this matches are already matched by +//! // the branches above +//! None => {}, // reachable: `None` is matched by this but not the branches above //! } //! # } //! ``` @@ -49,48 +58,35 @@ //! pattern is _not_ useful w.r.t. the patterns in the match. The values returned by `usefulness` //! are used to tell the user which values are missing. //! ```compile_fail,E0004 -//! # fn foo(x: Option<i32>) { +//! # fn foo(x: Option<u32>) { //! match x { -//! Some(0) => {}, //! None => {}, +//! Some(0) => {}, //! // not exhaustive: `_` is useful because it matches `Some(1)` //! } //! # } //! ``` //! -//! The entrypoint of this file is the [`compute_match_usefulness`] function, which computes -//! reachability for each match branch and exhaustiveness for the whole match. -//! //! //! # Constructors and fields //! -//! Note: we will often abbreviate "constructor" as "ctor". -//! -//! The idea that powers everything that is done in this file is the following: a (matchable) -//! value is made from a constructor applied to a number of subvalues. Examples of constructors are -//! `Some`, `None`, `(,)` (the 2-tuple constructor), `Foo {..}` (the constructor for a struct -//! `Foo`), and `2` (the constructor for the number `2`). This is natural when we think of -//! pattern-matching, and this is the basis for what follows. -//! -//! Some of the ctors listed above might feel weird: `None` and `2` don't take any arguments. -//! That's ok: those are ctors that take a list of 0 arguments; they are the simplest case of -//! ctors. We treat `2` as a ctor because `u64` and other number types behave exactly like a huge -//! `enum`, with one variant for each number. This allows us to see any matchable value as made up -//! from a tree of ctors, each having a set number of children. For example: `Foo { bar: None, -//! baz: Ok(0) }` is made from 4 different ctors, namely `Foo{..}`, `None`, `Ok` and `0`. -//! -//! This idea can be extended to patterns: they are also made from constructors applied to fields. -//! A pattern for a given type is allowed to use all the ctors for values of that type (which we -//! call "value constructors"), but there are also pattern-only ctors. The most important one is -//! the wildcard (`_`), and the others are integer ranges (`0..=10`), variable-length slices (`[x, -//! ..]`), and or-patterns (`Ok(0) | Err(_)`). Examples of valid patterns are `42`, `Some(_)`, `Foo -//! { bar: Some(0) | None, baz: _ }`. Note that a binder in a pattern (e.g. `Some(x)`) matches the -//! same values as a wildcard (e.g. `Some(_)`), so we treat both as wildcards. -//! -//! From this deconstruction we can compute whether a given value matches a given pattern; we -//! simply look at ctors one at a time. Given a pattern `p` and a value `v`, we want to compute -//! `matches!(v, p)`. It's mostly straightforward: we compare the head ctors and when they match -//! we compare their fields recursively. A few representative examples: +//! In the value `Pair(Some(0), true)`, `Pair` is called the constructor of the value, and `Some(0)` +//! and `true` are its fields. Every matcheable value can be decomposed in this way. Examples of +//! constructors are: `Some`, `None`, `(,)` (the 2-tuple constructor), `Foo {..}` (the constructor +//! for a struct `Foo`), and `2` (the constructor for the number `2`). +//! +//! Each constructor takes a fixed number of fields; this is called its arity. `Pair` and `(,)` have +//! arity 2, `Some` has arity 1, `None` and `42` have arity 0. Each type has a known set of +//! constructors. Some types have many constructors (like `u64`) or even an infinitely many (like +//! `&str` and `&[T]`). +//! +//! Patterns are similar: `Pair(Some(_), _)` has constructor `Pair` and two fields. The difference +//! is that we get some extra pattern-only constructors, namely: the wildcard `_`, variable +//! bindings, integer ranges like `0..=10`, and variable-length slices like `[_, .., _]`. We treat +//! or-patterns separately, see the dedicated section below. +//! +//! Now to check if a value `v` matches a pattern `p`, we check if `v`'s constructor matches `p`'s +//! constructor, then recursively compare their fields if necessary. A few representative examples: //! //! - `matches!(v, _) := true` //! - `matches!((v0, v1), (p0, p1)) := matches!(v0, p0) && matches!(v1, p1)` @@ -100,213 +96,398 @@ //! - `matches!(v, 1..=100) := matches!(v, 1) || ... || matches!(v, 100)` //! - `matches!([v0], [p0, .., p1]) := false` (incompatible lengths) //! - `matches!([v0, v1, v2], [p0, .., p1]) := matches!(v0, p0) && matches!(v2, p1)` -//! - `matches!(v, p0 | p1) := matches!(v, p0) || matches!(v, p1)` //! -//! Constructors, fields and relevant operations are defined in the [`super::deconstruct_pat`] module. +//! Constructors, fields and relevant operations are defined in the [`super::deconstruct_pat`] +//! module. The question of whether a constructor is matched by another one is answered by +//! [`Constructor::is_covered_by`]. //! -//! Note: this constructors/fields distinction may not straightforwardly apply to every Rust type. -//! For example a value of type `Rc<u64>` can't be deconstructed that way, and `&str` has an -//! infinitude of constructors. There are also subtleties with visibility of fields and -//! uninhabitedness and various other things. The constructors idea can be extended to handle most -//! of these subtleties though; caveats are documented where relevant throughout the code. +//! Note 1: variable bindings (like the `x` in `Some(x)`) match anything, so we treat them as wildcards. +//! Note 2: this only applies to matcheable values. For example a value of type `Rc<u64>` can't be +//! deconstructed that way. //! -//! Whether constructors cover each other is computed by [`Constructor::is_covered_by`]. //! //! //! # Specialization //! -//! Recall that we wish to compute `usefulness(p_1 .. p_n, q)`: given a list of patterns `p_1 .. -//! p_n` and a pattern `q`, all of the same type, we want to find a list of values (called -//! "witnesses") that are matched by `q` and by none of the `p_i`. We obviously don't just -//! enumerate all possible values. From the discussion above we see that we can proceed -//! ctor-by-ctor: for each value ctor of the given type, we ask "is there a value that starts with -//! this constructor and matches `q` and none of the `p_i`?". As we saw above, there's a lot we can -//! say from knowing only the first constructor of our candidate value. +//! 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)` +//! +//! We get the following property: for any values `v_1, .., v_n` of appropriate types, we have: +//! ```text +//! matches!(c(v_1, .., v_n), p) +//! <=> specialize(c, p) returns something +//! && matches!((v_1, .., v_n), specialize(c, p)) +//! ``` +//! +//! We also extend specialization to pattern-tuples by applying it to the first pattern: +//! `specialize(c, (p_0, .., p_n)) := specialize(c, p_0) ++ (p_1, .., p_m)` +//! where `++` is concatenation of tuples. +//! +//! +//! The previous property extends to pattern-tuples: +//! ```text +//! matches!((c(v_1, .., v_n), w_1, .., w_m), (p_0, p_1, .., p_m)) +//! <=> specialize(c, p_0) does not error +//! && matches!((v_1, .., v_n, w_1, .., w_m), specialize(c, (p_0, p_1, .., p_m))) +//! ``` +//! +//! Whether specialization returns something or not is given by [`Constructor::is_covered_by`]. +//! Specialization of a pattern is computed in [`DeconstructedPat::specialize`]. Specialization for +//! a pattern-tuple is computed in [`PatStack::pop_head_constructor`]. Finally, specialization for a +//! set of pattern-tuples is computed in [`Matrix::specialize_constructor`]. +//! +//! +//! +//! # Undoing specialization +//! +//! To construct witnesses we will need an inverse of specialization. If `c` is a constructor of +//! arity `n`, we define `unspecialize` as: +//! `unspecialize(c, (p_1, .., p_n, q_1, .., q_m)) := (c(p_1, .., p_n), q_1, .., q_m)`. +//! +//! This is done for a single witness-tuple in [`WitnessStack::apply_constructor`], and for a set of +//! witness-tuples in [`WitnessMatrix::apply_constructor`]. +//! +//! +//! +//! # Computing usefulness +//! +//! We now present a naive version of the algorithm for computing usefulness. From now on we operate +//! on pattern-tuples. +//! +//! Let `pt_1, .., pt_n` and `qt` be length-m tuples of patterns for the same type `(T_1, .., T_m)`. +//! We compute `usefulness(tp_1, .., tp_n, tq)` as follows: +//! +//! - Base case: `m == 0`. +//! The pattern-tuples are all empty, i.e. they're all `()`. Thus `tq` is useful iff there are +//! no rows above it, i.e. if `n == 0`. In that case we return `()` as a witness-tuple of +//! usefulness of `tq`. +//! +//! - Inductive case: `m > 0`. +//! In this naive version, we list all the possible constructors for values of type `T1` (we +//! will be more clever in the next section). +//! +//! - For each such constructor `c` for which `specialize(c, tq)` is not nothing: +//! - We recursively compute `usefulness(specialize(c, tp_1) ... specialize(c, tp_n), specialize(c, tq))`, +//! where we discard any `specialize(c, p_i)` that returns nothing. +//! - For each witness-tuple `w` found, we apply `unspecialize(c, w)` to it. +//! +//! - We return the all the witnesses found, if any. +//! //! //! Let's take the following example: //! ```compile_fail,E0004 //! # enum Enum { Variant1(()), Variant2(Option<bool>, u32)} +//! # use Enum::*; //! # fn foo(x: Enum) { //! match x { -//! Enum::Variant1(_) => {} // `p1` -//! Enum::Variant2(None, 0) => {} // `p2` -//! Enum::Variant2(Some(_), 0) => {} // `q` +//! Variant1(_) => {} // `p1` +//! Variant2(None, 0) => {} // `p2` +//! Variant2(Some(_), 0) => {} // `q` //! } //! # } //! ``` //! -//! We can easily see that if our candidate value `v` starts with `Variant1` it will not match `q`. -//! If `v = Variant2(v0, v1)` however, whether or not it matches `p2` and `q` will depend on `v0` -//! and `v1`. In fact, such a `v` will be a witness of usefulness of `q` exactly when the tuple -//! `(v0, v1)` is a witness of usefulness of `q'` in the following reduced match: -//! -//! ```compile_fail,E0004 -//! # fn foo(x: (Option<bool>, u32)) { -//! match x { -//! (None, 0) => {} // `p2'` -//! (Some(_), 0) => {} // `q'` -//! } -//! # } +//! To compute the usefulness of `q`, we would proceed as follows: +//! ```text +//! Start: +//! `tp1 = [Variant1(_)]` +//! `tp2 = [Variant2(None, 0)]` +//! `tq = [Variant2(Some(true), 0)]` +//! +//! Constructors are `Variant1` and `Variant2`. Only `Variant2` can specialize `tq`. +//! Specialize with `Variant2`: +//! `tp2 = [None, 0]` +//! `tq = [Some(true), 0]` +//! +//! Constructors are `None` and `Some`. Only `Some` can specialize `tq`. +//! Specialize with `Some`: +//! `tq = [true, 0]` +//! +//! Constructors are `false` and `true`. Only `true` can specialize `tq`. +//! Specialize with `true`: +//! `tq = [0]` +//! +//! Constructors are `0`, `1`, .. up to infinity. Only `0` can specialize `tq`. +//! Specialize with `0`: +//! `tq = []` +//! +//! m == 0 and n == 0, so `tq` is useful with witness `[]`. +//! `witness = []` +//! +//! Unspecialize with `0`: +//! `witness = [0]` +//! Unspecialize with `true`: +//! `witness = [true, 0]` +//! Unspecialize with `Some`: +//! `witness = [Some(true), 0]` +//! Unspecialize with `Variant2`: +//! `witness = [Variant2(Some(true), 0)]` //! ``` //! -//! This motivates a new step in computing usefulness, that we call _specialization_. -//! Specialization consist of filtering a list of patterns for those that match a constructor, and -//! then looking into the constructor's fields. This enables usefulness to be computed recursively. -//! -//! Instead of acting on a single pattern in each row, we will consider a list of patterns for each -//! row, and we call such a list a _pattern-stack_. The idea is that we will specialize the -//! leftmost pattern, which amounts to popping the constructor and pushing its fields, which feels -//! like a stack. We note a pattern-stack simply with `[p_1 ... p_n]`. -//! Here's a sequence of specializations of a list of pattern-stacks, to illustrate what's -//! happening: -//! ```ignore (illustrative) -//! [Enum::Variant1(_)] -//! [Enum::Variant2(None, 0)] -//! [Enum::Variant2(Some(_), 0)] -//! //==>> specialize with `Variant2` -//! [None, 0] -//! [Some(_), 0] -//! //==>> specialize with `Some` -//! [_, 0] -//! //==>> specialize with `true` (say the type was `bool`) -//! [0] -//! //==>> specialize with `0` -//! [] -//! ``` +//! Therefore `usefulness(tp_1, tp_2, tq)` returns the single witness-tuple `[Variant2(Some(true), 0)]`. //! -//! The function `specialize(c, p)` takes a value constructor `c` and a pattern `p`, and returns 0 -//! or more pattern-stacks. If `c` does not match the head constructor of `p`, it returns nothing; -//! otherwise if returns the fields of the constructor. This only returns more than one -//! pattern-stack if `p` has a pattern-only constructor. //! -//! - Specializing for the wrong constructor returns nothing +//! Computing the set of constructors for a type is done in [`ConstructorSet::for_ty`]. See the +//! following sections for more accurate versions of the algorithm and corresponding links. //! -//! `specialize(None, Some(p0)) := []` //! -//! - Specializing for the correct constructor returns a single row with the fields //! -//! `specialize(Variant1, Variant1(p0, p1, p2)) := [[p0, p1, p2]]` +//! # Computing reachability and exhaustiveness in one go //! -//! `specialize(Foo{..}, Foo { bar: p0, baz: p1 }) := [[p0, p1]]` +//! The algorithm we have described so far computes usefulness of each pattern in turn to check if +//! it is reachable, and ends by checking if `_` is useful to determine exhaustiveness of the whole +//! match. In practice, instead of doing "for each pattern { for each constructor { ... } }", we do +//! "for each constructor { for each pattern { ... } }". This allows us to compute everything in one +//! go. //! -//! - For or-patterns, we specialize each branch and concatenate the results +//! [`Matrix`] stores the set of pattern-tuples under consideration. We track reachability of each +//! row mutably in the matrix as we go along. We ignore witnesses of usefulness of the match rows. +//! We gather witnesses of the usefulness of `_` in [`WitnessMatrix`]. The algorithm that computes +//! all this is in [`compute_exhaustiveness_and_reachability`]. //! -//! `specialize(c, p0 | p1) := specialize(c, p0) ++ specialize(c, p1)` +//! See the full example at the bottom of this documentation. //! -//! - We treat the other pattern constructors as if they were a large or-pattern of all the -//! possibilities: //! -//! `specialize(c, _) := specialize(c, Variant1(_) | Variant2(_, _) | ...)` //! -//! `specialize(c, 1..=100) := specialize(c, 1 | ... | 100)` +//! # Making usefulness tractable: constructor splitting //! -//! `specialize(c, [p0, .., p1]) := specialize(c, [p0, p1] | [p0, _, p1] | [p0, _, _, p1] | ...)` +//! We're missing one last detail: which constructors do we list? Naively listing all value +//! constructors cannot work for types like `u64` or `&str`, so we need to be more clever. The final +//! clever idea for this algorithm is that we can group together constructors that behave the same. //! -//! - If `c` is a pattern-only constructor, `specialize` is defined on a case-by-case basis. See -//! the discussion about constructor splitting in [`super::deconstruct_pat`]. +//! Examples: +//! ```compile_fail,E0004 +//! match (0, false) { +//! (0 ..=100, true) => {} +//! (50..=150, false) => {} +//! (0 ..=200, _) => {} +//! } +//! ``` //! +//! In this example, trying any of `0`, `1`, .., `49` will give the same specialized matrix, and +//! thus the same reachability/exhaustiveness results. We can thus accelerate the algorithm by +//! trying them all at once. Here in fact, the only cases we need to consider are: `0..50`, +//! `50..=100`, `101..=150`,`151..=200` and `201..`. //! -//! We then extend this function to work with pattern-stacks as input, by acting on the first -//! column and keeping the other columns untouched. +//! ``` +//! enum Direction { North, South, East, West } +//! # let wind = (Direction::North, 0u8); +//! match wind { +//! (Direction::North, 50..) => {} +//! (_, _) => {} +//! } +//! ``` //! -//! Specialization for the whole matrix is done in [`Matrix::specialize_constructor`]. Note that -//! or-patterns in the first column are expanded before being stored in the matrix. Specialization -//! for a single patstack is done from a combination of [`Constructor::is_covered_by`] and -//! [`PatStack::pop_head_constructor`]. The internals of how it's done mostly live in the -//! [`super::deconstruct_pat::Fields`] struct. +//! In this example, trying any of `South`, `East`, `West` will give the same specialized matrix. By +//! the same reasoning, we only need to try two cases: `North`, and "everything else". //! +//! We call _constructor splitting_ the operation that computes such a minimal set of cases to try. +//! This is done in [`ConstructorSet::split`] and explained in [`super::deconstruct_pat`]. //! -//! # Computing usefulness //! -//! We now have all we need to compute usefulness. The inputs to usefulness are a list of -//! pattern-stacks `p_1 ... p_n` (one per row), and a new pattern_stack `q`. The paper and this -//! file calls the list of patstacks a _matrix_. They must all have the same number of columns and -//! the patterns in a given column must all have the same type. `usefulness` returns a (possibly -//! empty) list of witnesses of usefulness. These witnesses will also be pattern-stacks. -//! -//! - base case: `n_columns == 0`. -//! Since a pattern-stack functions like a tuple of patterns, an empty one functions like the -//! unit type. Thus `q` is useful iff there are no rows above it, i.e. if `n == 0`. -//! -//! - inductive case: `n_columns > 0`. -//! We need a way to list the constructors we want to try. We will be more clever in the next -//! section but for now assume we list all value constructors for the type of the first column. -//! -//! - for each such ctor `c`: -//! -//! - for each `q'` returned by `specialize(c, q)`: -//! -//! - we compute `usefulness(specialize(c, p_1) ... specialize(c, p_n), q')` -//! -//! - for each witness found, we revert specialization by pushing the constructor `c` on top. -//! -//! - We return the concatenation of all the witnesses found, if any. -//! -//! Example: -//! ```ignore (illustrative) -//! [Some(true)] // p_1 -//! [None] // p_2 -//! [Some(_)] // q -//! //==>> try `None`: `specialize(None, q)` returns nothing -//! //==>> try `Some`: `specialize(Some, q)` returns a single row -//! [true] // p_1' -//! [_] // q' -//! //==>> try `true`: `specialize(true, q')` returns a single row -//! [] // p_1'' -//! [] // q'' -//! //==>> base case; `n != 0` so `q''` is not useful. -//! //==>> go back up a step -//! [true] // p_1' -//! [_] // q' -//! //==>> try `false`: `specialize(false, q')` returns a single row -//! [] // q'' -//! //==>> base case; `n == 0` so `q''` is useful. We return the single witness `[]` -//! witnesses: -//! [] -//! //==>> undo the specialization with `false` -//! witnesses: -//! [false] -//! //==>> undo the specialization with `Some` -//! witnesses: -//! [Some(false)] -//! //==>> we have tried all the constructors. The output is the single witness `[Some(false)]`. -//! ``` +//! # Or-patterns //! -//! This computation is done in [`is_useful`]. In practice we don't care about the list of -//! witnesses when computing reachability; we only need to know whether any exist. We do keep the -//! witnesses when computing exhaustiveness to report them to the user. +//! What we have described so far works well if there are no or-patterns. To handle them, if the +//! first pattern of a row in the matrix is an or-pattern, we expand it by duplicating the rest of +//! the row as necessary. This is handled automatically in [`Matrix`]. //! +//! This makes reachability tracking subtle, because we also want to compute whether an alternative +//! of an or-pattern is unreachable, e.g. in `Some(_) | Some(0)`. We track reachability of each +//! subpattern by interior mutability in [`DeconstructedPat`] with `set_reachable`/`is_reachable`. //! -//! # Making usefulness tractable: constructor splitting +//! It's unfortunate that we have to use interior mutability, but believe me (Nadrieril), I have +//! tried [other](https://github.com/rust-lang/rust/pull/80104) +//! [solutions](https://github.com/rust-lang/rust/pull/80632) and nothing is remotely as simple. //! -//! We're missing one last detail: which constructors do we list? Naively listing all value -//! constructors cannot work for types like `u64` or `&str`, so we need to be more clever. The -//! first obvious insight is that we only want to list constructors that are covered by the head -//! constructor of `q`. If it's a value constructor, we only try that one. If it's a pattern-only -//! constructor, we use the final clever idea for this algorithm: _constructor splitting_, where we -//! group together constructors that behave the same. //! -//! The details are not necessary to understand this file, so we explain them in -//! [`super::deconstruct_pat`]. Splitting is done by the [`Constructor::split`] function. //! -//! # Constants in patterns +//! # Constants and opaques //! //! There are two kinds of constants in patterns: //! //! * literals (`1`, `true`, `"foo"`) //! * named or inline consts (`FOO`, `const { 5 + 6 }`) //! -//! The latter are converted into other patterns with literals at the leaves. For example +//! The latter are converted into the corresponding patterns by a previous phase. For example //! `const_to_pat(const { [1, 2, 3] })` becomes an `Array(vec![Const(1), Const(2), Const(3)])` //! pattern. This gets problematic when comparing the constant via `==` would behave differently -//! from matching on the constant converted to a pattern. Situations like that can occur, when -//! the user implements `PartialEq` manually, and thus could make `==` behave arbitrarily different. -//! In order to honor the `==` implementation, constants of types that implement `PartialEq` manually -//! stay as a full constant and become an `Opaque` pattern. These `Opaque` patterns do not participate -//! in exhaustiveness, specialization or overlap checking. - -use self::ArmType::*; -use self::Usefulness::*; +//! from matching on the constant converted to a pattern. The situation around this is currently +//! unclear and the lang team is working on clarifying what we want to do there. In any case, there +//! are constants we will not turn into patterns. We capture these with `Constructor::Opaque`. These +//! `Opaque` patterns do not participate in exhaustiveness, specialization or overlap checking. +//! +//! +//! +//! # Full example +//! +//! We illustrate a full run of the algorithm on the following match. +//! +//! ```compile_fail,E0004 +//! # struct Pair(Option<u32>, bool); +//! # fn foo(x: Pair) -> u32 { +//! match x { +//! Pair(Some(0), _) => 1, +//! Pair(_, false) => 2, +//! Pair(Some(0), false) => 3, +//! } +//! # } +//! ``` +//! +//! We keep track of the original row for illustration purposes, this is not what the algorithm +//! actually does (it tracks reachability as a boolean on each row). +//! +//! ```text +//! ┐ Patterns: +//! │ 1. `[Pair(Some(0), _)]` +//! │ 2. `[Pair(_, false)]` +//! │ 3. `[Pair(Some(0), false)]` +//! │ +//! │ Specialize with `Pair`: +//! ├─┐ Patterns: +//! │ │ 1. `[Some(0), _]` +//! │ │ 2. `[_, false]` +//! │ │ 3. `[Some(0), false]` +//! │ │ +//! │ │ Specialize with `Some`: +//! │ ├─┐ Patterns: +//! │ │ │ 1. `[0, _]` +//! │ │ │ 2. `[_, false]` +//! │ │ │ 3. `[0, false]` +//! │ │ │ +//! │ │ │ Specialize with `0`: +//! │ │ ├─┐ Patterns: +//! │ │ │ │ 1. `[_]` +//! │ │ │ │ 3. `[false]` +//! │ │ │ │ +//! │ │ │ │ Specialize with `true`: +//! │ │ │ ├─┐ Patterns: +//! │ │ │ │ │ 1. `[]` +//! │ │ │ │ │ +//! │ │ │ │ │ We note arm 1 is reachable (by `Pair(Some(0), true)`). +//! │ │ │ ├─┘ +//! │ │ │ │ +//! │ │ │ │ Specialize with `false`: +//! │ │ │ ├─┐ Patterns: +//! │ │ │ │ │ 1. `[]` +//! │ │ │ │ │ 3. `[]` +//! │ │ │ │ │ +//! │ │ │ │ │ We note arm 1 is reachable (by `Pair(Some(0), false)`). +//! │ │ │ ├─┘ +//! │ │ ├─┘ +//! │ │ │ +//! │ │ │ Specialize with `1..`: +//! │ │ ├─┐ Patterns: +//! │ │ │ │ 2. `[false]` +//! │ │ │ │ +//! │ │ │ │ Specialize with `true`: +//! │ │ │ ├─┐ Patterns: +//! │ │ │ │ │ // no rows left +//! │ │ │ │ │ +//! │ │ │ │ │ We have found an unmatched value (`Pair(Some(1..), true)`)! This gives us a witness. +//! │ │ │ │ │ New witnesses: +//! │ │ │ │ │ `[]` +//! │ │ │ ├─┘ +//! │ │ │ │ Unspecialize new witnesses with `true`: +//! │ │ │ │ `[true]` +//! │ │ │ │ +//! │ │ │ │ Specialize with `false`: +//! │ │ │ ├─┐ Patterns: +//! │ │ │ │ │ 2. `[]` +//! │ │ │ │ │ +//! │ │ │ │ │ We note arm 2 is reachable (by `Pair(Some(1..), false)`). +//! │ │ │ ├─┘ +//! │ │ │ │ +//! │ │ │ │ Total witnesses for `1..`: +//! │ │ │ │ `[true]` +//! │ │ ├─┘ +//! │ │ │ Unspecialize new witnesses with `1..`: +//! │ │ │ `[1.., true]` +//! │ │ │ +//! │ │ │ Total witnesses for `Some`: +//! │ │ │ `[1.., true]` +//! │ ├─┘ +//! │ │ Unspecialize new witnesses with `Some`: +//! │ │ `[Some(1..), true]` +//! │ │ +//! │ │ Specialize with `None`: +//! │ ├─┐ Patterns: +//! │ │ │ 2. `[false]` +//! │ │ │ +//! │ │ │ Specialize with `true`: +//! │ │ ├─┐ Patterns: +//! │ │ │ │ // no rows left +//! │ │ │ │ +//! │ │ │ │ We have found an unmatched value (`Pair(None, true)`)! This gives us a witness. +//! │ │ │ │ New witnesses: +//! │ │ │ │ `[]` +//! │ │ ├─┘ +//! │ │ │ Unspecialize new witnesses with `true`: +//! │ │ │ `[true]` +//! │ │ │ +//! │ │ │ Specialize with `false`: +//! │ │ ├─┐ Patterns: +//! │ │ │ │ 2. `[]` +//! │ │ │ │ +//! │ │ │ │ We note arm 2 is reachable (by `Pair(None, false)`). +//! │ │ ├─┘ +//! │ │ │ +//! │ │ │ Total witnesses for `None`: +//! │ │ │ `[true]` +//! │ ├─┘ +//! │ │ Unspecialize new witnesses with `None`: +//! │ │ `[None, true]` +//! │ │ +//! │ │ Total witnesses for `Pair`: +//! │ │ `[Some(1..), true]` +//! │ │ `[None, true]` +//! ├─┘ +//! │ Unspecialize new witnesses with `Pair`: +//! │ `[Pair(Some(1..), true)]` +//! │ `[Pair(None, true)]` +//! │ +//! │ Final witnesses: +//! │ `[Pair(Some(1..), true)]` +//! │ `[Pair(None, true)]` +//! ┘ +//! ``` +//! +//! We conclude: +//! - Arm 3 is unreachable (it was never marked as reachable); +//! - The match is not exhaustive; +//! - Adding arms with `Pair(Some(1..), true)` and `Pair(None, true)` would make the match exhaustive. +//! +//! Note that when we're deep in the algorithm, we don't know what specialization steps got us here. +//! We can only figure out what our witnesses correspond to by unspecializing back up the stack. +//! +//! +//! # Tests +//! +//! Note: tests specific to this file can be found in: +//! +//! - `ui/pattern/usefulness` +//! - `ui/or-patterns` +//! - `ui/consts/const_in_pattern` +//! - `ui/rfc-2008-non-exhaustive` +//! - `ui/half-open-range-patterns` +//! - probably many others +//! +//! I (Nadrieril) prefer to put new tests in `ui/pattern/usefulness` unless there's a specific +//! reason not to, for example if they crucially depend on a particular feature like `or_patterns`. + use super::deconstruct_pat::{ Constructor, ConstructorSet, DeconstructedPat, IntRange, MaybeInfiniteInt, SplitConstructorSet, WitnessPat, @@ -340,8 +521,12 @@ pub(crate) struct MatchCheckCtxt<'p, 'tcx> { pub(crate) module: DefId, pub(crate) param_env: ty::ParamEnv<'tcx>, pub(crate) pattern_arena: &'p TypedArena<DeconstructedPat<'p, 'tcx>>, + /// Lint level at the match. + pub(crate) match_lint_level: HirId, /// The span of the whole match, if applicable. pub(crate) match_span: Option<Span>, + /// Span of the scrutinee. + pub(crate) scrut_span: Span, /// Only produce `NON_EXHAUSTIVE_OMITTED_PATTERNS` lint on refutable patterns. pub(crate) refutable: bool, } @@ -371,8 +556,6 @@ pub(super) struct PatCtxt<'a, 'p, 'tcx> { pub(super) cx: &'a MatchCheckCtxt<'p, 'tcx>, /// Type of the current column under investigation. pub(super) ty: Ty<'tcx>, - /// Span of the current pattern under investigation. - pub(super) span: Span, /// Whether the current pattern is the whole pattern as found in a match arm, or if it's a /// subpattern. pub(super) is_top_level: bool, @@ -384,20 +567,16 @@ impl<'a, 'p, 'tcx> fmt::Debug for PatCtxt<'a, 'p, 'tcx> { } } -/// A row of a matrix. Rows of len 1 are very common, which is why `SmallVec[_; 2]` -/// works well. +/// Represents a pattern-tuple under investigation. #[derive(Clone)] -pub(crate) struct PatStack<'p, 'tcx> { - pub(crate) pats: SmallVec<[&'p DeconstructedPat<'p, 'tcx>; 2]>, +struct PatStack<'p, 'tcx> { + // Rows of len 1 are very common, which is why `SmallVec[_; 2]` works well. + pats: SmallVec<[&'p DeconstructedPat<'p, 'tcx>; 2]>, } impl<'p, 'tcx> PatStack<'p, 'tcx> { fn from_pattern(pat: &'p DeconstructedPat<'p, 'tcx>) -> Self { - Self::from_vec(smallvec![pat]) - } - - fn from_vec(vec: SmallVec<[&'p DeconstructedPat<'p, 'tcx>; 2]>) -> Self { - PatStack { pats: vec } + PatStack { pats: smallvec![pat] } } fn is_empty(&self) -> bool { @@ -416,37 +595,18 @@ impl<'p, 'tcx> PatStack<'p, 'tcx> { self.pats.iter().copied() } - // Recursively expand the first pattern into its subpatterns. Only useful if the pattern is an - // or-pattern. Panics if `self` is empty. + // Recursively expand the first or-pattern into its subpatterns. Only useful if the pattern is + // an or-pattern. Panics if `self` is empty. fn expand_or_pat<'a>(&'a self) -> impl Iterator<Item = PatStack<'p, 'tcx>> + Captures<'a> { - self.head().iter_fields().map(move |pat| { - let mut new_patstack = PatStack::from_pattern(pat); - new_patstack.pats.extend_from_slice(&self.pats[1..]); - new_patstack + self.head().flatten_or_pat().into_iter().map(move |pat| { + let mut new_pats = smallvec![pat]; + new_pats.extend_from_slice(&self.pats[1..]); + PatStack { pats: new_pats } }) } - // Recursively expand all patterns into their subpatterns and push each `PatStack` to matrix. - fn expand_and_extend<'a>(&'a self, matrix: &mut Matrix<'p, 'tcx>) { - if !self.is_empty() && self.head().is_or_pat() { - for pat in self.head().iter_fields() { - let mut new_patstack = PatStack::from_pattern(pat); - new_patstack.pats.extend_from_slice(&self.pats[1..]); - if !new_patstack.is_empty() && new_patstack.head().is_or_pat() { - new_patstack.expand_and_extend(matrix); - } else if !new_patstack.is_empty() { - matrix.push(new_patstack); - } - } - } - } - - /// This computes `S(self.head().ctor(), self)`. See top of the file for explanations. - /// - /// Structure patterns with a partial wild pattern (Foo { a: 42, .. }) have their missing - /// fields filled with wild patterns. - /// - /// This is roughly the inverse of `Constructor::apply`. + /// This computes `specialize(ctor, self)`. See top of the file for explanations. + /// Only call if `ctor.is_covered_by(self.head().ctor())` is true. fn pop_head_constructor( &self, pcx: &PatCtxt<'_, 'p, 'tcx>, @@ -454,15 +614,15 @@ impl<'p, 'tcx> PatStack<'p, 'tcx> { ) -> PatStack<'p, 'tcx> { // We pop the head pattern and push the new fields extracted from the arguments of // `self.head()`. - let mut new_fields: SmallVec<[_; 2]> = self.head().specialize(pcx, ctor); - new_fields.extend_from_slice(&self.pats[1..]); - PatStack::from_vec(new_fields) + let mut new_pats = self.head().specialize(pcx, ctor); + new_pats.extend_from_slice(&self.pats[1..]); + PatStack { pats: new_pats } } } -/// Pretty-printing for matrix row. impl<'p, 'tcx> fmt::Debug for PatStack<'p, 'tcx> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + // We pretty-print similarly to the `Debug` impl of `Matrix`. write!(f, "+")?; for pat in self.iter() { write!(f, " {pat:?} +")?; @@ -471,45 +631,186 @@ impl<'p, 'tcx> fmt::Debug for PatStack<'p, 'tcx> { } } -/// A 2D matrix. +/// A row of the matrix. #[derive(Clone)] -pub(super) struct Matrix<'p, 'tcx> { - pub patterns: Vec<PatStack<'p, 'tcx>>, +struct MatrixRow<'p, 'tcx> { + // The patterns in the row. + pats: PatStack<'p, 'tcx>, + /// Whether the original arm had a guard. This is inherited when specializing. + is_under_guard: bool, + /// When we specialize, we remember which row of the original matrix produced a given row of the + /// specialized matrix. When we unspecialize, we use this to propagate reachability back up the + /// callstack. + parent_row: usize, + /// False when the matrix is just built. This is set to `true` by + /// [`compute_exhaustiveness_and_reachability`] if the arm is found to be reachable. + /// This is reset to `false` when specializing. + reachable: bool, } -impl<'p, 'tcx> Matrix<'p, 'tcx> { - fn empty() -> Self { - Matrix { patterns: vec![] } +impl<'p, 'tcx> MatrixRow<'p, 'tcx> { + fn is_empty(&self) -> bool { + self.pats.is_empty() } + fn len(&self) -> usize { + self.pats.len() + } + + fn head(&self) -> &'p DeconstructedPat<'p, 'tcx> { + self.pats.head() + } + + fn iter(&self) -> impl Iterator<Item = &DeconstructedPat<'p, 'tcx>> { + self.pats.iter() + } + + // Recursively expand the first or-pattern into its subpatterns. Only useful if the pattern is + // an or-pattern. Panics if `self` is empty. + fn expand_or_pat<'a>(&'a self) -> impl Iterator<Item = MatrixRow<'p, 'tcx>> + Captures<'a> { + self.pats.expand_or_pat().map(|patstack| MatrixRow { + pats: patstack, + parent_row: self.parent_row, + is_under_guard: self.is_under_guard, + reachable: false, + }) + } + + /// This computes `specialize(ctor, self)`. See top of the file for explanations. + /// Only call if `ctor.is_covered_by(self.head().ctor())` is true. + fn pop_head_constructor( + &self, + pcx: &PatCtxt<'_, 'p, 'tcx>, + ctor: &Constructor<'tcx>, + parent_row: usize, + ) -> MatrixRow<'p, 'tcx> { + MatrixRow { + pats: self.pats.pop_head_constructor(pcx, ctor), + parent_row, + is_under_guard: self.is_under_guard, + reachable: false, + } + } +} + +impl<'p, 'tcx> fmt::Debug for MatrixRow<'p, 'tcx> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + self.pats.fmt(f) + } +} + +/// A 2D matrix. Represents a list of pattern-tuples under investigation. +/// +/// Invariant: each row must have the same length, and each column must have the same type. +/// +/// Invariant: the first column must not contain or-patterns. This is handled by +/// [`Matrix::expand_and_push`]. +/// +/// In fact each column corresponds to a place inside the scrutinee of the match. E.g. after +/// specializing `(,)` and `Some` on a pattern of type `(Option<u32>, bool)`, the first column of +/// the matrix will correspond to `scrutinee.0.Some.0` and the second column to `scrutinee.1`. +#[derive(Clone)] +struct Matrix<'p, 'tcx> { + rows: Vec<MatrixRow<'p, 'tcx>>, + /// Stores an extra fictitious row full of wildcards. Mostly used to keep track of the type of + /// each column. This must obey the same invariants as the real rows. + wildcard_row: PatStack<'p, 'tcx>, +} + +impl<'p, 'tcx> Matrix<'p, 'tcx> { /// Pushes a new row to the matrix. If the row starts with an or-pattern, this recursively - /// expands it. - fn push(&mut self, row: PatStack<'p, 'tcx>) { + /// expands it. Internal method, prefer [`Matrix::new`]. + fn expand_and_push(&mut self, row: MatrixRow<'p, 'tcx>) { if !row.is_empty() && row.head().is_or_pat() { - row.expand_and_extend(self); + // Expand nested or-patterns. + for new_row in row.expand_or_pat() { + self.rows.push(new_row); + } } else { - self.patterns.push(row); + self.rows.push(row); + } + } + + /// Build a new matrix from an iterator of `MatchArm`s. + fn new<'a>( + cx: &MatchCheckCtxt<'p, 'tcx>, + iter: impl Iterator<Item = &'a MatchArm<'p, 'tcx>>, + scrut_ty: Ty<'tcx>, + ) -> Self + where + 'p: 'a, + { + let wild_pattern = cx.pattern_arena.alloc(DeconstructedPat::wildcard(scrut_ty, DUMMY_SP)); + let wildcard_row = PatStack::from_pattern(wild_pattern); + let mut matrix = Matrix { rows: vec![], wildcard_row }; + for (row_id, arm) in iter.enumerate() { + let v = MatrixRow { + pats: PatStack::from_pattern(arm.pat), + parent_row: row_id, // dummy, we won't read it + is_under_guard: arm.has_guard, + reachable: false, + }; + matrix.expand_and_push(v); + } + matrix + } + + fn head_ty(&self) -> Option<Ty<'tcx>> { + if self.column_count() == 0 { + return None; + } + + let mut ty = self.wildcard_row.head().ty(); + // If the type is opaque and it is revealed anywhere in the column, we take the revealed + // version. Otherwise we could encounter constructors for the revealed type and crash. + let is_opaque = |ty: Ty<'tcx>| matches!(ty.kind(), ty::Alias(ty::Opaque, ..)); + if is_opaque(ty) { + for pat in self.heads() { + let pat_ty = pat.ty(); + if !is_opaque(pat_ty) { + ty = pat_ty; + break; + } + } } + Some(ty) + } + fn column_count(&self) -> usize { + self.wildcard_row.len() } - /// Iterate over the first component of each row + fn rows<'a>( + &'a self, + ) -> impl Iterator<Item = &'a MatrixRow<'p, 'tcx>> + Clone + DoubleEndedIterator + ExactSizeIterator + { + self.rows.iter() + } + fn rows_mut<'a>( + &'a mut self, + ) -> impl Iterator<Item = &'a mut MatrixRow<'p, 'tcx>> + DoubleEndedIterator + ExactSizeIterator + { + self.rows.iter_mut() + } + + /// Iterate over the first pattern of each row. fn heads<'a>( &'a self, ) -> impl Iterator<Item = &'p DeconstructedPat<'p, 'tcx>> + Clone + Captures<'a> { - self.patterns.iter().map(|r| r.head()) + self.rows().map(|r| r.head()) } - /// This computes `S(constructor, self)`. See top of the file for explanations. + /// This computes `specialize(ctor, self)`. See top of the file for explanations. fn specialize_constructor( &self, pcx: &PatCtxt<'_, 'p, 'tcx>, ctor: &Constructor<'tcx>, ) -> Matrix<'p, 'tcx> { - let mut matrix = Matrix::empty(); - for row in &self.patterns { + let wildcard_row = self.wildcard_row.pop_head_constructor(pcx, ctor); + let mut matrix = Matrix { rows: vec![], wildcard_row }; + for (i, row) in self.rows().enumerate() { if ctor.is_covered_by(pcx, row.head().ctor()) { - let new_row = row.pop_head_constructor(pcx, ctor); - matrix.push(new_row); + let new_row = row.pop_head_constructor(pcx, ctor, i); + matrix.expand_and_push(new_row); } } matrix @@ -529,12 +830,12 @@ impl<'p, 'tcx> fmt::Debug for Matrix<'p, 'tcx> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { write!(f, "\n")?; - let Matrix { patterns: m, .. } = self; + let Matrix { rows, .. } = self; let pretty_printed_matrix: Vec<Vec<String>> = - m.iter().map(|row| row.iter().map(|pat| format!("{pat:?}")).collect()).collect(); + rows.iter().map(|row| row.iter().map(|pat| format!("{pat:?}")).collect()).collect(); - let column_count = m.iter().map(|row| row.len()).next().unwrap_or(0); - assert!(m.iter().all(|row| row.len() == column_count)); + let column_count = rows.iter().map(|row| row.len()).next().unwrap_or(0); + assert!(rows.iter().all(|row| row.len() == column_count)); let column_widths: Vec<usize> = (0..column_count) .map(|col| pretty_printed_matrix.iter().map(|row| row[col].len()).max().unwrap_or(0)) .collect(); @@ -552,129 +853,17 @@ impl<'p, 'tcx> fmt::Debug for Matrix<'p, 'tcx> { } } -/// This carries the results of computing usefulness, as described at the top of the file. When -/// checking usefulness of a match branch, we use the `NoWitnesses` variant, which also keeps track -/// of potential unreachable sub-patterns (in the presence of or-patterns). When checking -/// exhaustiveness of a whole match, we use the `WithWitnesses` variant, which carries a list of -/// witnesses of non-exhaustiveness when there are any. -/// Which variant to use is dictated by `ArmType`. -#[derive(Debug, Clone)] -enum Usefulness<'tcx> { - /// If we don't care about witnesses, simply remember if the pattern was useful. - NoWitnesses { useful: bool }, - /// Carries a list of witnesses of non-exhaustiveness. If empty, indicates that the whole - /// pattern is unreachable. - WithWitnesses(Vec<WitnessStack<'tcx>>), -} - -impl<'tcx> Usefulness<'tcx> { - fn new_useful(preference: ArmType) -> Self { - match preference { - // A single (empty) witness of reachability. - FakeExtraWildcard => WithWitnesses(vec![WitnessStack(vec![])]), - RealArm => NoWitnesses { useful: true }, - } - } - - fn new_not_useful(preference: ArmType) -> Self { - match preference { - FakeExtraWildcard => WithWitnesses(vec![]), - RealArm => NoWitnesses { useful: false }, - } - } - - fn is_useful(&self) -> bool { - match self { - Usefulness::NoWitnesses { useful } => *useful, - Usefulness::WithWitnesses(witnesses) => !witnesses.is_empty(), - } - } - - /// Combine usefulnesses from two branches. This is an associative operation. - fn extend(&mut self, other: Self) { - match (&mut *self, other) { - (WithWitnesses(_), WithWitnesses(o)) if o.is_empty() => {} - (WithWitnesses(s), WithWitnesses(o)) if s.is_empty() => *self = WithWitnesses(o), - (WithWitnesses(s), WithWitnesses(o)) => s.extend(o), - (NoWitnesses { useful: s_useful }, NoWitnesses { useful: o_useful }) => { - *s_useful = *s_useful || o_useful - } - _ => unreachable!(), - } - } - - /// After calculating usefulness after a specialization, call this to reconstruct a usefulness - /// that makes sense for the matrix pre-specialization. This new usefulness can then be merged - /// with the results of specializing with the other constructors. - fn apply_constructor( - self, - pcx: &PatCtxt<'_, '_, 'tcx>, - matrix: &Matrix<'_, 'tcx>, // used to compute missing ctors - ctor: &Constructor<'tcx>, - ) -> Self { - match self { - NoWitnesses { .. } => self, - WithWitnesses(ref witnesses) if witnesses.is_empty() => self, - WithWitnesses(witnesses) => { - let new_witnesses = if let Constructor::Missing { .. } = ctor { - let mut missing = ConstructorSet::for_ty(pcx.cx, pcx.ty) - .compute_missing(pcx, matrix.heads().map(DeconstructedPat::ctor)); - if missing.iter().any(|c| c.is_non_exhaustive()) { - // We only report `_` here; listing other constructors would be redundant. - missing = vec![Constructor::NonExhaustive]; - } - - // We got the special `Missing` constructor, so each of the missing constructors - // gives a new pattern that is not caught by the match. - // We construct for each missing constructor a version of this constructor with - // wildcards for fields, i.e. that matches everything that can be built with it. - // For example, if `ctor` is a `Constructor::Variant` for `Option::Some`, we get - // the pattern `Some(_)`. - let new_patterns: Vec<WitnessPat<'_>> = missing - .into_iter() - .map(|missing_ctor| WitnessPat::wild_from_ctor(pcx, missing_ctor.clone())) - .collect(); - - witnesses - .into_iter() - .flat_map(|witness| { - new_patterns.iter().map(move |pat| { - let mut stack = witness.clone(); - stack.0.push(pat.clone()); - stack - }) - }) - .collect() - } else { - witnesses - .into_iter() - .map(|witness| witness.apply_constructor(pcx, ctor)) - .collect() - }; - WithWitnesses(new_witnesses) - } - } - } -} - -#[derive(Copy, Clone, Debug)] -enum ArmType { - FakeExtraWildcard, - RealArm, -} - /// A witness-tuple of non-exhaustiveness for error reporting, represented as a list of patterns (in -/// reverse order of construction) with wildcards inside to represent elements that can take any -/// inhabitant of the type as a value. +/// reverse order of construction). /// /// This mirrors `PatStack`: they function similarly, except `PatStack` contains user patterns we /// are inspecting, and `WitnessStack` contains witnesses we are constructing. -/// FIXME(Nadrieril): use the same order of patterns for both +/// FIXME(Nadrieril): use the same order of patterns for both. /// -/// A `WitnessStack` should have the same types and length as the `PatStacks` we are inspecting -/// (except we store the patterns in reverse order). Because Rust `match` is always against a single -/// pattern, at the end the stack will have length 1. In the middle of the algorithm, it can contain -/// multiple patterns. +/// A `WitnessStack` should have the same types and length as the `PatStack`s we are inspecting +/// (except we store the patterns in reverse order). The same way `PatStack` starts with length 1, +/// at the end of the algorithm this will have length 1. In the middle of the algorithm, it can +/// contain multiple patterns. /// /// For example, if we are constructing a witness for the match against /// @@ -689,6 +878,7 @@ enum ArmType { /// ``` /// /// We'll perform the following steps (among others): +/// ```text /// - Start with a matrix representing the match /// `PatStack(vec![Pair(None, _)])` /// `PatStack(vec![Pair(_, false)])` @@ -711,8 +901,11 @@ enum ArmType { /// `WitnessStack(vec![true, Some(_)])` /// - Apply `Pair` /// `WitnessStack(vec![Pair(Some(_), true)])` +/// ``` /// /// The final `Pair(Some(_), true)` is then the resulting witness. +/// +/// See the top of the file for more detailed explanations and examples. #[derive(Debug, Clone)] pub(crate) struct WitnessStack<'tcx>(Vec<WitnessPat<'tcx>>); @@ -723,158 +916,235 @@ impl<'tcx> WitnessStack<'tcx> { self.0.into_iter().next().unwrap() } - /// Constructs a partial witness for a pattern given a list of - /// patterns expanded by the specialization step. - /// - /// When a pattern P is discovered to be useful, this function is used bottom-up - /// to reconstruct a complete witness, e.g., a pattern P' that covers a subset - /// of values, V, where each value in that set is not covered by any previously - /// used patterns and is covered by the pattern P'. Examples: + /// Reverses specialization by the `Missing` constructor by pushing a whole new pattern. + fn push_pattern(&mut self, pat: WitnessPat<'tcx>) { + self.0.push(pat); + } + + /// Reverses specialization. Given a witness obtained after specialization, this constructs a + /// new witness valid for before specialization. See the section on `unspecialize` at the top of + /// the file. /// - /// left_ty: tuple of 3 elements - /// pats: [10, 20, _] => (10, 20, _) + /// Examples: + /// ```text + /// ctor: tuple of 2 elements + /// pats: [false, "foo", _, true] + /// result: [(false, "foo"), _, true] /// - /// left_ty: struct X { a: (bool, &'static str), b: usize} - /// pats: [(false, "foo"), 42] => X { a: (false, "foo"), b: 42 } - fn apply_constructor(mut self, pcx: &PatCtxt<'_, '_, 'tcx>, ctor: &Constructor<'tcx>) -> Self { - let pat = { - let len = self.0.len(); - let arity = ctor.arity(pcx); - let fields = self.0.drain((len - arity)..).rev().collect(); - WitnessPat::new(ctor.clone(), fields, pcx.ty) - }; - + /// ctor: Enum::Variant { a: (bool, &'static str), b: usize} + /// pats: [(false, "foo"), _, true] + /// result: [Enum::Variant { a: (false, "foo"), b: _ }, true] + /// ``` + fn apply_constructor(&mut self, pcx: &PatCtxt<'_, '_, 'tcx>, ctor: &Constructor<'tcx>) { + let len = self.0.len(); + let arity = ctor.arity(pcx); + let fields = self.0.drain((len - arity)..).rev().collect(); + let pat = WitnessPat::new(ctor.clone(), fields, pcx.ty); self.0.push(pat); - - self } } -/// Algorithm from <http://moscova.inria.fr/~maranget/papers/warn/index.html>. -/// The algorithm from the paper has been modified to correctly handle empty -/// types. The changes are: -/// (0) We don't exit early if the pattern matrix has zero rows. We just -/// continue to recurse over columns. -/// (1) all_constructors will only return constructors that are statically -/// possible. E.g., it will only return `Ok` for `Result<T, !>`. +/// Represents a set of pattern-tuples that are witnesses of non-exhaustiveness for error +/// reporting. This has similar invariants as `Matrix` does. +/// +/// The `WitnessMatrix` returned by [`compute_exhaustiveness_and_reachability`] obeys the invariant +/// that the union of the input `Matrix` and the output `WitnessMatrix` together matches the type +/// exhaustively. /// -/// This finds whether a (row) vector `v` of patterns is 'useful' in relation -/// to a set of such vectors `m` - this is defined as there being a set of -/// inputs that will match `v` but not any of the sets in `m`. +/// Just as the `Matrix` starts with a single column, by the end of the algorithm, this has a single +/// column, which contains the patterns that are missing for the match to be exhaustive. +#[derive(Debug, Clone)] +pub struct WitnessMatrix<'tcx>(Vec<WitnessStack<'tcx>>); + +impl<'tcx> WitnessMatrix<'tcx> { + /// New matrix with no witnesses. + fn empty() -> Self { + WitnessMatrix(vec![]) + } + /// New matrix with one `()` witness, i.e. with no columns. + fn unit_witness() -> Self { + WitnessMatrix(vec![WitnessStack(vec![])]) + } + + /// Whether this has any witnesses. + fn is_empty(&self) -> bool { + self.0.is_empty() + } + /// Asserts that there is a single column and returns the patterns in it. + fn single_column(self) -> Vec<WitnessPat<'tcx>> { + self.0.into_iter().map(|w| w.single_pattern()).collect() + } + + /// Reverses specialization by the `Missing` constructor by pushing a whole new pattern. + fn push_pattern(&mut self, pat: WitnessPat<'tcx>) { + for witness in self.0.iter_mut() { + witness.push_pattern(pat.clone()) + } + } + + /// Reverses specialization by `ctor`. See the section on `unspecialize` at the top of the file. + fn apply_constructor( + &mut self, + pcx: &PatCtxt<'_, '_, 'tcx>, + missing_ctors: &[Constructor<'tcx>], + ctor: &Constructor<'tcx>, + report_individual_missing_ctors: bool, + ) { + if self.is_empty() { + return; + } + if matches!(ctor, Constructor::Missing) { + // We got the special `Missing` constructor that stands for the constructors not present + // in the match. + if !report_individual_missing_ctors { + // Report `_` as missing. + let pat = WitnessPat::wild_from_ctor(pcx, Constructor::Wildcard); + self.push_pattern(pat); + } else if missing_ctors.iter().any(|c| c.is_non_exhaustive()) { + // We need to report a `_` anyway, so listing other constructors would be redundant. + // `NonExhaustive` is displayed as `_` just like `Wildcard`, but it will be picked + // up by diagnostics to add a note about why `_` is required here. + let pat = WitnessPat::wild_from_ctor(pcx, Constructor::NonExhaustive); + self.push_pattern(pat); + } else { + // 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 = WitnessPat::wild_from_ctor(pcx, 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 self.0.iter_mut() { + witness.apply_constructor(pcx, ctor) + } + } + } + + /// Merges the witnesses of two matrices. Their column types must match. + fn extend(&mut self, other: Self) { + self.0.extend(other.0) + } +} + +/// The core of the algorithm. /// -/// All the patterns at each column of the `matrix ++ v` matrix must have the same type. +/// This recursively computes witnesses of the non-exhaustiveness of `matrix` (if any). Also tracks +/// usefulness of each row in the matrix (in `row.reachable`). We track reachability of each +/// subpattern using interior mutability in `DeconstructedPat`. /// -/// This is used both for reachability checking (if a pattern isn't useful in -/// relation to preceding patterns, it is not reachable) and exhaustiveness -/// checking (if a wildcard pattern is useful in relation to a matrix, the -/// matrix isn't exhaustive). +/// The input `Matrix` and the output `WitnessMatrix` together match the type exhaustively. /// -/// `is_under_guard` is used to inform if the pattern has a guard. If it -/// has one it must not be inserted into the matrix. This shouldn't be -/// relied on for soundness. -#[instrument(level = "debug", skip(cx, matrix, lint_root), ret)] -fn is_useful<'p, 'tcx>( +/// The key steps are: +/// - specialization, where we dig into the rows that have a specific constructor and call ourselves +/// recursively; +/// - unspecialization, where we lift the results from the previous step into results for this step +/// (using `apply_constructor` and by updating `row.reachable` for each parent row). +/// This is all explained at the top of the file. +#[instrument(level = "debug", skip(cx, is_top_level), ret)] +fn compute_exhaustiveness_and_reachability<'p, 'tcx>( cx: &MatchCheckCtxt<'p, 'tcx>, - matrix: &Matrix<'p, 'tcx>, - v: &PatStack<'p, 'tcx>, - witness_preference: ArmType, - lint_root: HirId, - is_under_guard: bool, + matrix: &mut Matrix<'p, 'tcx>, is_top_level: bool, -) -> Usefulness<'tcx> { - debug!(?matrix, ?v); - let Matrix { patterns: rows, .. } = matrix; - - // The base case. We are pattern-matching on () and the return value is - // based on whether our matrix has a row or not. - // NOTE: This could potentially be optimized by checking rows.is_empty() - // first and then, if v is non-empty, the return value is based on whether - // the type of the tuple we're checking is inhabited or not. - if v.is_empty() { - let ret = if rows.is_empty() { - Usefulness::new_useful(witness_preference) - } else { - Usefulness::new_not_useful(witness_preference) - }; - debug!(?ret); - return ret; - } - - debug_assert!(rows.iter().all(|r| r.len() == v.len())); - - // If the first pattern is an or-pattern, expand it. - let mut ret = Usefulness::new_not_useful(witness_preference); - if v.head().is_or_pat() { - debug!("expanding or-pattern"); - // We try each or-pattern branch in turn. - let mut matrix = matrix.clone(); - for v in v.expand_or_pat() { - debug!(?v); - let usefulness = ensure_sufficient_stack(|| { - is_useful(cx, &matrix, &v, witness_preference, lint_root, is_under_guard, false) - }); - debug!(?usefulness); - ret.extend(usefulness); - // If pattern has a guard don't add it to the matrix. - if !is_under_guard { - // We push the already-seen patterns into the matrix in order to detect redundant - // branches like `Some(_) | Some(0)`. - matrix.push(v); +) -> WitnessMatrix<'tcx> { + debug_assert!(matrix.rows().all(|r| r.len() == matrix.column_count())); + + let Some(ty) = matrix.head_ty() else { + // The base case: there are no columns in the matrix. We are morally pattern-matching on (). + // A row is reachable iff it has no (unguarded) rows above it. + for row in matrix.rows_mut() { + // All rows are reachable until we find one without a guard. + row.reachable = true; + if !row.is_under_guard { + // There's an unguarded row, so the match is exhaustive, and any subsequent row is + // unreachable. + return WitnessMatrix::empty(); } } - } else { - let mut ty = v.head().ty(); + // No (unguarded) rows, so the match is not exhaustive. We return a new witness. + return WitnessMatrix::unit_witness(); + }; - // Opaque types can't get destructured/split, but the patterns can - // actually hint at hidden types, so we use the patterns' types instead. - if let ty::Alias(ty::Opaque, ..) = ty.kind() { - if let Some(row) = rows.first() { - ty = row.head().ty(); - } + debug!("ty: {ty:?}"); + let pcx = &PatCtxt { cx, ty, is_top_level }; + + // Analyze the constructors present in this column. + let ctors = matrix.heads().map(|p| p.ctor()); + let split_set = ConstructorSet::for_ty(pcx.cx, pcx.ty).split(pcx, ctors); + + let all_missing = split_set.present.is_empty(); + let always_report_all = is_top_level && !IntRange::is_integral(pcx.ty); + // Whether we should report "Enum::A and Enum::C are missing" or "_ is missing". + let report_individual_missing_ctors = always_report_all || !all_missing; + + let mut split_ctors = split_set.present; + let mut only_report_missing = false; + if !split_set.missing.is_empty() { + // We need to iterate over a full set of constructors, so we add `Missing` to represent the + // missing ones. This is explained under "Constructor Splitting" at the top of this file. + split_ctors.push(Constructor::Missing); + // For diagnostic purposes we choose to only report the constructors that are missing. Since + // `Missing` matches only the wildcard rows, it matches fewer rows than any normal + // constructor and is therefore guaranteed to result in more witnesses. So skipping the + // other constructors does not jeopardize correctness. + only_report_missing = true; + } + + let mut ret = WitnessMatrix::empty(); + for ctor in split_ctors { + debug!("specialize({:?})", ctor); + // Dig into rows that match `ctor`. + let mut spec_matrix = matrix.specialize_constructor(pcx, &ctor); + let mut witnesses = ensure_sufficient_stack(|| { + compute_exhaustiveness_and_reachability(cx, &mut spec_matrix, false) + }); + + if !only_report_missing || matches!(ctor, Constructor::Missing) { + // Transform witnesses for `spec_matrix` into witnesses for `matrix`. + witnesses.apply_constructor( + pcx, + &split_set.missing, + &ctor, + report_individual_missing_ctors, + ); + // Accumulate the found witnesses. + ret.extend(witnesses); } - debug!("v.head: {:?}, v.span: {:?}", v.head(), v.head().span()); - let pcx = &PatCtxt { cx, ty, span: v.head().span(), is_top_level }; - - let v_ctor = v.head().ctor(); - debug!(?v_ctor); - // We split the head constructor of `v`. - let split_ctors = v_ctor.split(pcx, matrix.heads().map(DeconstructedPat::ctor)); - // For each constructor, we compute whether there's a value that starts with it that would - // witness the usefulness of `v`. - let start_matrix = &matrix; - for ctor in split_ctors { - debug!("specialize({:?})", ctor); - // We cache the result of `Fields::wildcards` because it is used a lot. - let spec_matrix = start_matrix.specialize_constructor(pcx, &ctor); - let v = v.pop_head_constructor(pcx, &ctor); - let usefulness = ensure_sufficient_stack(|| { - is_useful( - cx, - &spec_matrix, - &v, - witness_preference, - lint_root, - is_under_guard, - false, - ) - }); - let usefulness = usefulness.apply_constructor(pcx, start_matrix, &ctor); - ret.extend(usefulness); + + // A parent row is useful if any of its children is. + for child_row in spec_matrix.rows() { + let parent_row = &mut matrix.rows[child_row.parent_row]; + parent_row.reachable = parent_row.reachable || child_row.reachable; } } - if ret.is_useful() { - v.head().set_reachable(); + // Record that the subpattern is reachable. + for row in matrix.rows() { + if row.reachable { + row.head().set_reachable(); + } } ret } /// A column of patterns in the matrix, where a column is the intuitive notion of "subpatterns that -/// inspect the same subvalue". +/// inspect the same subvalue/place". /// This is used to traverse patterns column-by-column for lints. Despite similarities with -/// `is_useful`, this is a different traversal. Notably this is linear in the depth of patterns, -/// whereas `is_useful` is worst-case exponential (exhaustiveness is NP-complete). +/// [`compute_exhaustiveness_and_reachability`], this does a different traversal. Notably this is +/// linear in the depth of patterns, whereas `compute_exhaustiveness_and_reachability` is worst-case +/// exponential (exhaustiveness is NP-complete). The core difference is that we treat sub-columns +/// separately. +/// +/// This must not contain an or-pattern. `specialize` takes care to expand them. +/// +/// This is not used in the main algorithm; only in lints. #[derive(Debug)] struct PatternColumn<'p, 'tcx> { patterns: Vec<&'p DeconstructedPat<'p, 'tcx>>, @@ -907,17 +1177,19 @@ impl<'p, 'tcx> PatternColumn<'p, 'tcx> { Some(first_ty) } + /// Do constructor splitting on the constructors of the column. fn analyze_ctors(&self, pcx: &PatCtxt<'_, 'p, 'tcx>) -> SplitConstructorSet<'tcx> { let column_ctors = self.patterns.iter().map(|p| p.ctor()); ConstructorSet::for_ty(pcx.cx, pcx.ty).split(pcx, column_ctors) } + fn iter<'a>(&'a self) -> impl Iterator<Item = &'p DeconstructedPat<'p, 'tcx>> + Captures<'a> { self.patterns.iter().copied() } /// Does specialization: given a constructor, this takes the patterns from the column that match /// the constructor, and outputs their fields. - /// This returns one column per field of the constructor. The normally all have the same length + /// This returns one column per field of the constructor. They usually all have the same length /// (the number of patterns in `self` that matched `ctor`), except that we expand or-patterns /// which may change the lengths. fn specialize(&self, pcx: &PatCtxt<'_, 'p, 'tcx>, ctor: &Constructor<'tcx>) -> Vec<Self> { @@ -963,7 +1235,7 @@ fn collect_nonexhaustive_missing_variants<'p, 'tcx>( let Some(ty) = column.head_ty() else { return Vec::new(); }; - let pcx = &PatCtxt { cx, ty, span: DUMMY_SP, is_top_level: false }; + let pcx = &PatCtxt { cx, ty, is_top_level: false }; let set = column.analyze_ctors(pcx); if set.present.is_empty() { @@ -1004,16 +1276,15 @@ fn collect_nonexhaustive_missing_variants<'p, 'tcx>( } /// Traverse the patterns to warn the user about ranges that overlap on their endpoints. -#[instrument(level = "debug", skip(cx, lint_root))] +#[instrument(level = "debug", skip(cx))] fn lint_overlapping_range_endpoints<'p, 'tcx>( cx: &MatchCheckCtxt<'p, 'tcx>, column: &PatternColumn<'p, 'tcx>, - lint_root: HirId, ) { let Some(ty) = column.head_ty() else { return; }; - let pcx = &PatCtxt { cx, ty, span: DUMMY_SP, is_top_level: false }; + let pcx = &PatCtxt { cx, ty, is_top_level: false }; let set = column.analyze_ctors(pcx); @@ -1027,7 +1298,7 @@ fn lint_overlapping_range_endpoints<'p, 'tcx>( .collect(); cx.tcx.emit_spanned_lint( lint::builtin::OVERLAPPING_RANGE_ENDPOINTS, - lint_root, + cx.match_lint_level, this_span, OverlappingRangeEndpoints { overlap: overlaps, range: this_span }, ); @@ -1072,7 +1343,7 @@ fn lint_overlapping_range_endpoints<'p, 'tcx>( // Recurse into the fields. for ctor in set.present { for col in column.specialize(pcx, &ctor) { - lint_overlapping_range_endpoints(cx, &col, lint_root); + lint_overlapping_range_endpoints(cx, &col); } } } @@ -1107,30 +1378,24 @@ pub(crate) struct UsefulnessReport<'p, 'tcx> { pub(crate) non_exhaustiveness_witnesses: Vec<WitnessPat<'tcx>>, } -/// The entrypoint for the usefulness algorithm. Computes whether a match is exhaustive and which -/// of its arms are reachable. -/// -/// Note: the input patterns must have been lowered through -/// `check_match::MatchVisitor::lower_pattern`. +/// The entrypoint for this file. Computes whether a match is exhaustive and which of its arms are +/// reachable. #[instrument(skip(cx, arms), level = "debug")] pub(crate) fn compute_match_usefulness<'p, 'tcx>( cx: &MatchCheckCtxt<'p, 'tcx>, arms: &[MatchArm<'p, 'tcx>], - lint_root: HirId, scrut_ty: Ty<'tcx>, - scrut_span: Span, ) -> UsefulnessReport<'p, 'tcx> { - let mut matrix = Matrix::empty(); + let mut matrix = Matrix::new(cx, arms.iter(), scrut_ty); + let non_exhaustiveness_witnesses = + compute_exhaustiveness_and_reachability(cx, &mut matrix, true); + + let non_exhaustiveness_witnesses: Vec<_> = non_exhaustiveness_witnesses.single_column(); let arm_usefulness: Vec<_> = arms .iter() .copied() .map(|arm| { debug!(?arm); - let v = PatStack::from_pattern(arm.pat); - is_useful(cx, &matrix, &v, RealArm, arm.hir_id, arm.has_guard, true); - if !arm.has_guard { - matrix.push(v); - } let reachability = if arm.pat.is_reachable() { Reachability::Reachable(arm.pat.unreachable_spans()) } else { @@ -1139,28 +1404,20 @@ pub(crate) fn compute_match_usefulness<'p, 'tcx>( (arm, reachability) }) .collect(); + let report = UsefulnessReport { arm_usefulness, non_exhaustiveness_witnesses }; - let wild_pattern = cx.pattern_arena.alloc(DeconstructedPat::wildcard(scrut_ty, DUMMY_SP)); - let v = PatStack::from_pattern(wild_pattern); - let usefulness = is_useful(cx, &matrix, &v, FakeExtraWildcard, lint_root, false, true); - let non_exhaustiveness_witnesses: Vec<_> = match usefulness { - WithWitnesses(pats) => pats.into_iter().map(|w| w.single_pattern()).collect(), - NoWitnesses { .. } => bug!(), - }; - - let pat_column = arms.iter().flat_map(|arm| arm.pat.flatten_or_pat()).collect::<Vec<_>>(); - let pat_column = PatternColumn::new(pat_column); - lint_overlapping_range_endpoints(cx, &pat_column, lint_root); + let pat_column = PatternColumn::new(matrix.heads().collect()); + // Lint on ranges that overlap on their endpoints, which is likely a mistake. + lint_overlapping_range_endpoints(cx, &pat_column); // Run the non_exhaustive_omitted_patterns lint. Only run on refutable patterns to avoid hitting // `if let`s. Only run if the match is exhaustive otherwise the error is redundant. - if cx.refutable && non_exhaustiveness_witnesses.is_empty() { + if cx.refutable && report.non_exhaustiveness_witnesses.is_empty() { if !matches!( - cx.tcx.lint_level_at_node(NON_EXHAUSTIVE_OMITTED_PATTERNS, lint_root).0, + cx.tcx.lint_level_at_node(NON_EXHAUSTIVE_OMITTED_PATTERNS, cx.match_lint_level).0, rustc_session::lint::Level::Allow ) { let witnesses = collect_nonexhaustive_missing_variants(cx, &pat_column); - if !witnesses.is_empty() { // Report that a match of a `non_exhaustive` enum marked with `non_exhaustive_omitted_patterns` // is not exhaustive enough. @@ -1168,11 +1425,11 @@ pub(crate) fn compute_match_usefulness<'p, 'tcx>( // NB: The partner lint for structs lives in `compiler/rustc_hir_analysis/src/check/pat.rs`. cx.tcx.emit_spanned_lint( NON_EXHAUSTIVE_OMITTED_PATTERNS, - lint_root, - scrut_span, + cx.match_lint_level, + cx.scrut_span, NonExhaustiveOmittedPattern { scrut_ty, - uncovered: Uncovered::new(scrut_span, cx, witnesses), + uncovered: Uncovered::new(cx.scrut_span, cx, witnesses), }, ); } @@ -1201,5 +1458,5 @@ pub(crate) fn compute_match_usefulness<'p, 'tcx>( } } - UsefulnessReport { arm_usefulness, non_exhaustiveness_witnesses } + report } |