diff options
Diffstat (limited to 'compiler/rustc_pattern_analysis/src')
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/constructor.rs | 162 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/errors.rs | 8 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/lib.rs | 112 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/lints.rs | 104 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/pat.rs | 169 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/rustc.rs (renamed from compiler/rustc_pattern_analysis/src/cx.rs) | 295 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/usefulness.rs | 495 |
7 files changed, 859 insertions, 486 deletions
diff --git a/compiler/rustc_pattern_analysis/src/constructor.rs b/compiler/rustc_pattern_analysis/src/constructor.rs index 6486ad8b483..b688051ca9c 100644 --- a/compiler/rustc_pattern_analysis/src/constructor.rs +++ b/compiler/rustc_pattern_analysis/src/constructor.rs @@ -40,7 +40,7 @@ //! - 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 [`crate::cx::MatchCheckCtxt::ctors_for_ty`] determines the +//! We compute this in two steps: first [`TypeCx::ctors_for_ty`] determines the //! set of all possible constructors for the type. Then [`ConstructorSet::split`] looks at the //! column of constructors and splits the set into groups accordingly. The precise invariants of //! [`ConstructorSet::split`] is described in [`SplitConstructorSet`]. @@ -136,7 +136,7 @@ //! the algorithm can't distinguish them from a nonempty constructor. The only known case where this //! could happen is the `[..]` pattern on `[!; N]` with `N > 0` so we must take care to not emit it. //! -//! This is all handled by [`crate::cx::MatchCheckCtxt::ctors_for_ty`] and +//! This is all handled by [`TypeCx::ctors_for_ty`] and //! [`ConstructorSet::split`]. The invariants of [`SplitConstructorSet`] are also of interest. //! //! @@ -155,17 +155,15 @@ use std::iter::once; use smallvec::SmallVec; use rustc_apfloat::ieee::{DoubleS, IeeeFloat, SingleS}; -use rustc_data_structures::fx::FxHashSet; -use rustc_hir::RangeEnd; +use rustc_index::bit_set::{BitSet, GrowableBitSet}; use rustc_index::IndexVec; -use rustc_middle::mir::Const; -use rustc_target::abi::VariantIdx; use self::Constructor::*; use self::MaybeInfiniteInt::*; use self::SliceKind::*; -use crate::usefulness::PatCtxt; +use crate::usefulness::PlaceCtxt; +use crate::TypeCx; /// Whether we have seen a constructor in the column or not. #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)] @@ -174,6 +172,21 @@ enum Presence { Seen, } +#[derive(Debug, Copy, Clone, PartialEq, Eq)] +pub enum RangeEnd { + Included, + Excluded, +} + +impl fmt::Display for RangeEnd { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.write_str(match self { + RangeEnd::Included => "..=", + RangeEnd::Excluded => "..", + }) + } +} + /// A possibly infinite integer. Values are encoded such that the ordering on `u128` matches the /// natural order on the original type. For example, `-128i8` is encoded as `0` and `127i8` as /// `255`. See `signed_bias` for details. @@ -221,7 +234,7 @@ impl MaybeInfiniteInt { match self { Finite(n) => match n.checked_sub(1) { Some(m) => Finite(m), - None => bug!(), + None => panic!("Called `MaybeInfiniteInt::minus_one` on 0"), }, JustAfterMax => Finite(u128::MAX), x => x, @@ -234,7 +247,7 @@ impl MaybeInfiniteInt { Some(m) => Finite(m), None => JustAfterMax, }, - JustAfterMax => bug!(), + JustAfterMax => panic!("Called `MaybeInfiniteInt::plus_one` on u128::MAX+1"), x => x, } } @@ -253,7 +266,7 @@ pub struct IntRange { impl IntRange { /// Best effort; will not know that e.g. `255u8..` is a singleton. - pub(crate) fn is_singleton(&self) -> bool { + pub fn is_singleton(&self) -> bool { // Since `lo` and `hi` can't be the same `Infinity` and `plus_one` never changes from finite // to infinite, this correctly only detects ranges that contain exacly one `Finite(x)`. self.lo.plus_one() == self.hi @@ -271,7 +284,7 @@ impl IntRange { } if lo >= hi { // This should have been caught earlier by E0030. - bug!("malformed range pattern: {lo:?}..{hi:?}"); + panic!("malformed range pattern: {lo:?}..{hi:?}"); } IntRange { lo, hi } } @@ -432,7 +445,7 @@ impl Slice { let kind = match (array_len, kind) { // If the middle `..` has length 0, we effectively have a fixed-length pattern. (Some(len), VarLen(prefix, suffix)) if prefix + suffix == len => FixedLen(len), - (Some(len), VarLen(prefix, suffix)) if prefix + suffix > len => bug!( + (Some(len), VarLen(prefix, suffix)) if prefix + suffix > len => panic!( "Slice pattern of length {} longer than its array length {len}", prefix + suffix ), @@ -532,7 +545,7 @@ impl Slice { // therefore `Presence::Seen` in the column. let mut min_var_len = usize::MAX; // Tracks the fixed-length slices we've seen, to mark them as `Presence::Seen`. - let mut seen_fixed_lens = FxHashSet::default(); + let mut seen_fixed_lens = GrowableBitSet::new_empty(); match &mut max_slice { VarLen(max_prefix_len, max_suffix_len) => { // A length larger than any fixed-length slice encountered. @@ -600,7 +613,7 @@ impl Slice { smaller_lengths.map(FixedLen).chain(once(max_slice)).map(move |kind| { let arity = kind.arity(); - let seen = if min_var_len <= arity || seen_fixed_lens.contains(&arity) { + let seen = if min_var_len <= arity || seen_fixed_lens.contains(arity) { Presence::Seen } else { Presence::Unseen @@ -629,13 +642,19 @@ impl OpaqueId { /// `specialize_constructor` returns the list of fields corresponding to a pattern, given a /// constructor. `Constructor::apply` reconstructs the pattern from a pair of `Constructor` and /// `Fields`. -#[derive(Clone, Debug, PartialEq)] -pub enum Constructor<'tcx> { - /// The constructor for patterns that have a single constructor, like tuples, struct patterns, - /// and references. Fixed-length arrays are treated separately with `Slice`. - Single, +#[derive(derivative::Derivative)] +#[derivative(Debug(bound = ""), Clone(bound = ""), PartialEq(bound = ""))] +pub enum Constructor<Cx: TypeCx> { + /// Tuples and structs. + Struct, /// Enum variants. - Variant(VariantIdx), + Variant(Cx::VariantIdx), + /// References + Ref, + /// Array and slice patterns. + Slice(Slice), + /// Union field accesses. + UnionField, /// Booleans Bool(bool), /// Ranges of integer literal values (`2`, `2..=5` or `2..5`). @@ -644,9 +663,7 @@ pub enum Constructor<'tcx> { F32Range(IeeeFloat<SingleS>, IeeeFloat<SingleS>, RangeEnd), F64Range(IeeeFloat<DoubleS>, IeeeFloat<DoubleS>, RangeEnd), /// String literals. Strings are not quite the same as `&[u8]` so we treat them separately. - Str(Const<'tcx>), - /// Array and slice patterns. - Slice(Slice), + Str(Cx::StrLit), /// 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. @@ -669,12 +686,12 @@ pub enum Constructor<'tcx> { Missing, } -impl<'tcx> Constructor<'tcx> { +impl<Cx: TypeCx> Constructor<Cx> { pub(crate) fn is_non_exhaustive(&self) -> bool { matches!(self, NonExhaustive) } - pub(crate) fn as_variant(&self) -> Option<VariantIdx> { + pub(crate) fn as_variant(&self) -> Option<Cx::VariantIdx> { match self { Variant(i) => Some(*i), _ => None, @@ -701,8 +718,8 @@ impl<'tcx> Constructor<'tcx> { /// The number of fields for this constructor. This must be kept in sync with /// `Fields::wildcards`. - pub(crate) fn arity(&self, pcx: &PatCtxt<'_, '_, 'tcx>) -> usize { - pcx.cx.ctor_arity(self, pcx.ty) + pub(crate) fn arity(&self, pcx: &PlaceCtxt<'_, '_, Cx>) -> usize { + pcx.ctor_arity(self) } /// Returns whether `self` is covered by `other`, i.e. whether `self` is a subset of `other`. @@ -710,20 +727,20 @@ impl<'tcx> Constructor<'tcx> { /// this checks for inclusion. // We inline because this has a single call site in `Matrix::specialize_constructor`. #[inline] - pub(crate) fn is_covered_by<'p>(&self, pcx: &PatCtxt<'_, 'p, 'tcx>, other: &Self) -> bool { + pub(crate) fn is_covered_by<'p>(&self, pcx: &PlaceCtxt<'_, 'p, Cx>, other: &Self) -> bool { match (self, other) { - (Wildcard, _) => { - span_bug!( - pcx.cx.scrut_span, - "Constructor splitting should not have returned `Wildcard`" - ) - } + (Wildcard, _) => pcx + .mcx + .tycx + .bug(format_args!("Constructor splitting should not have returned `Wildcard`")), // Wildcards cover anything (_, Wildcard) => true, // Only a wildcard pattern can match these special constructors. (Missing { .. } | NonExhaustive | Hidden, _) => false, - (Single, Single) => true, + (Struct, Struct) => true, + (Ref, Ref) => true, + (UnionField, UnionField) => true, (Variant(self_id), Variant(other_id)) => self_id == other_id, (Bool(self_b), Bool(other_b)) => self_b == other_b, @@ -756,12 +773,9 @@ impl<'tcx> Constructor<'tcx> { (Opaque(self_id), Opaque(other_id)) => self_id == other_id, (Opaque(..), _) | (_, Opaque(..)) => false, - _ => span_bug!( - pcx.cx.scrut_span, - "trying to compare incompatible constructors {:?} and {:?}", - self, - other - ), + _ => pcx.mcx.tycx.bug(format_args!( + "trying to compare incompatible constructors {self:?} and {other:?}" + )), } } } @@ -785,13 +799,16 @@ pub enum VariantVisibility { /// In terms of division of responsibility, [`ConstructorSet::split`] handles all of the /// `exhaustive_patterns` feature. #[derive(Debug)] -pub enum ConstructorSet { - /// The type has a single constructor, e.g. `&T` or a struct. `empty` tracks whether the - /// constructor is empty. - Single { empty: bool }, +pub enum ConstructorSet<Cx: TypeCx> { + /// The type is a tuple or struct. `empty` tracks whether the type is empty. + Struct { empty: bool }, /// This type has the following list of constructors. If `variants` is empty and /// `non_exhaustive` is false, don't use this; use `NoConstructors` instead. - Variants { variants: IndexVec<VariantIdx, VariantVisibility>, non_exhaustive: bool }, + Variants { variants: IndexVec<Cx::VariantIdx, VariantVisibility>, non_exhaustive: bool }, + /// The type is `&T`. + Ref, + /// The type is a union. + Union, /// Booleans. Bool, /// The type is spanned by integer values. The range or ranges give the set of allowed values. @@ -830,25 +847,25 @@ pub enum ConstructorSet { /// 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(crate) struct SplitConstructorSet<'tcx> { - pub(crate) present: SmallVec<[Constructor<'tcx>; 1]>, - pub(crate) missing: Vec<Constructor<'tcx>>, - pub(crate) missing_empty: Vec<Constructor<'tcx>>, +pub(crate) struct SplitConstructorSet<Cx: TypeCx> { + pub(crate) present: SmallVec<[Constructor<Cx>; 1]>, + pub(crate) missing: Vec<Constructor<Cx>>, + pub(crate) missing_empty: Vec<Constructor<Cx>>, } -impl ConstructorSet { +impl<Cx: TypeCx> ConstructorSet<Cx> { /// 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(crate) fn split<'a, 'tcx>( + pub(crate) fn split<'a>( &self, - pcx: &PatCtxt<'_, '_, 'tcx>, - ctors: impl Iterator<Item = &'a Constructor<'tcx>> + Clone, - ) -> SplitConstructorSet<'tcx> + pcx: &PlaceCtxt<'_, '_, Cx>, + ctors: impl Iterator<Item = &'a Constructor<Cx>> + Clone, + ) -> SplitConstructorSet<Cx> where - 'tcx: 'a, + Cx: 'a, { let mut present: SmallVec<[_; 1]> = SmallVec::new(); // Empty constructors found missing. @@ -866,22 +883,39 @@ impl ConstructorSet { } match self { - ConstructorSet::Single { empty } => { + ConstructorSet::Struct { empty } => { if !seen.is_empty() { - present.push(Single); + present.push(Struct); } else if *empty { - missing_empty.push(Single); + missing_empty.push(Struct); + } else { + missing.push(Struct); + } + } + ConstructorSet::Ref => { + if !seen.is_empty() { + present.push(Ref); } else { - missing.push(Single); + missing.push(Ref); + } + } + ConstructorSet::Union => { + if !seen.is_empty() { + present.push(UnionField); + } else { + missing.push(UnionField); } } ConstructorSet::Variants { variants, non_exhaustive } => { - let seen_set: FxHashSet<_> = seen.iter().map(|c| c.as_variant().unwrap()).collect(); + let mut seen_set: BitSet<_> = BitSet::new_empty(variants.len()); + for idx in seen.iter().map(|c| c.as_variant().unwrap()) { + seen_set.insert(idx); + } let mut skipped_a_hidden_variant = false; for (idx, visibility) in variants.iter_enumerated() { let ctor = Variant(idx); - if seen_set.contains(&idx) { + if seen_set.contains(idx) { present.push(ctor); } else { // We only put visible variants directly into `missing`. @@ -975,8 +1009,8 @@ impl ConstructorSet { // We have now grouped all the constructors into 3 buckets: present, missing, missing_empty. // In the absence of the `exhaustive_patterns` feature however, we don't count nested empty // types as empty. Only non-nested `!` or `enum Foo {}` are considered empty. - if !pcx.cx.tcx.features().exhaustive_patterns - && !(pcx.is_top_level && matches!(self, Self::NoConstructors)) + if !pcx.mcx.tycx.is_exhaustive_patterns_feature_on() + && !(pcx.is_scrutinee && matches!(self, Self::NoConstructors)) { // Treat all missing constructors as nonempty. // This clears `missing_empty`. diff --git a/compiler/rustc_pattern_analysis/src/errors.rs b/compiler/rustc_pattern_analysis/src/errors.rs index 0efa8a0ec08..88770b0c43b 100644 --- a/compiler/rustc_pattern_analysis/src/errors.rs +++ b/compiler/rustc_pattern_analysis/src/errors.rs @@ -1,11 +1,11 @@ -use crate::{cx::MatchCheckCtxt, pat::WitnessPat}; - use rustc_errors::{AddToDiagnostic, Diagnostic, SubdiagnosticMessage}; use rustc_macros::{LintDiagnostic, Subdiagnostic}; use rustc_middle::thir::Pat; use rustc_middle::ty::Ty; use rustc_span::Span; +use crate::rustc::{RustcMatchCheckCtxt, WitnessPat}; + #[derive(Subdiagnostic)] #[label(pattern_analysis_uncovered)] pub struct Uncovered<'tcx> { @@ -21,8 +21,8 @@ pub struct Uncovered<'tcx> { impl<'tcx> Uncovered<'tcx> { pub fn new<'p>( span: Span, - cx: &MatchCheckCtxt<'p, 'tcx>, - witnesses: Vec<WitnessPat<'tcx>>, + cx: &RustcMatchCheckCtxt<'p, 'tcx>, + witnesses: Vec<WitnessPat<'p, 'tcx>>, ) -> Self { let witness_1 = cx.hoist_witness_pat(witnesses.get(0).unwrap()); Self { diff --git a/compiler/rustc_pattern_analysis/src/lib.rs b/compiler/rustc_pattern_analysis/src/lib.rs index 07730aa49d3..a1c9b157666 100644 --- a/compiler/rustc_pattern_analysis/src/lib.rs +++ b/compiler/rustc_pattern_analysis/src/lib.rs @@ -1,54 +1,132 @@ //! Analysis of patterns, notably match exhaustiveness checking. pub mod constructor; -pub mod cx; +#[cfg(feature = "rustc")] pub mod errors; +#[cfg(feature = "rustc")] pub(crate) mod lints; pub mod pat; +#[cfg(feature = "rustc")] +pub mod rustc; pub mod usefulness; #[macro_use] extern crate tracing; +#[cfg(feature = "rustc")] #[macro_use] extern crate rustc_middle; +#[cfg(feature = "rustc")] rustc_fluent_macro::fluent_messages! { "../messages.ftl" } -use lints::PatternColumn; -use rustc_hir::HirId; +use std::fmt; + +use rustc_index::Idx; +#[cfg(feature = "rustc")] use rustc_middle::ty::Ty; -use usefulness::{compute_match_usefulness, UsefulnessReport}; -use crate::cx::MatchCheckCtxt; -use crate::lints::{lint_nonexhaustive_missing_variants, lint_overlapping_range_endpoints}; +use crate::constructor::{Constructor, ConstructorSet}; +#[cfg(feature = "rustc")] +use crate::lints::{ + lint_nonexhaustive_missing_variants, lint_overlapping_range_endpoints, PatternColumn, +}; use crate::pat::DeconstructedPat; +#[cfg(feature = "rustc")] +use crate::rustc::RustcMatchCheckCtxt; +#[cfg(feature = "rustc")] +use crate::usefulness::{compute_match_usefulness, ValidityConstraint}; + +// It's not possible to only enable the `typed_arena` dependency when the `rustc` feature is off, so +// we use another feature instead. The crate won't compile if one of these isn't enabled. +#[cfg(feature = "rustc")] +pub(crate) use rustc_arena::TypedArena; +#[cfg(feature = "stable")] +pub(crate) use typed_arena::Arena as TypedArena; + +pub trait Captures<'a> {} +impl<'a, T: ?Sized> Captures<'a> for T {} + +/// Context that provides type information about constructors. +/// +/// Most of the crate is parameterized on a type that implements this trait. +pub trait TypeCx: Sized + fmt::Debug { + /// The type of a pattern. + type Ty: Copy + Clone + fmt::Debug; // FIXME: remove Copy + /// The index of an enum variant. + type VariantIdx: Clone + Idx; + /// A string literal + type StrLit: Clone + PartialEq + fmt::Debug; + /// Extra data to store in a match arm. + type ArmData: Copy + Clone + fmt::Debug; + /// Extra data to store in a pattern. + type PatData: Clone; + + /// FIXME(Nadrieril): `Cx` should only give us revealed types. + fn reveal_opaque_ty(&self, ty: Self::Ty) -> Self::Ty; + fn is_exhaustive_patterns_feature_on(&self) -> bool; + + /// The number of fields for this constructor. + fn ctor_arity(&self, ctor: &Constructor<Self>, ty: Self::Ty) -> usize; + + /// The types of the fields for this constructor. The result must have a length of + /// `ctor_arity()`. + fn ctor_sub_tys(&self, ctor: &Constructor<Self>, ty: Self::Ty) -> &[Self::Ty]; + + /// The set of all the constructors for `ty`. + /// + /// This must follow the invariants of `ConstructorSet` + fn ctors_for_ty(&self, ty: Self::Ty) -> ConstructorSet<Self>; + + /// Best-effort `Debug` implementation. + fn debug_pat(f: &mut fmt::Formatter<'_>, pat: &DeconstructedPat<'_, Self>) -> fmt::Result; + + /// Raise a bug. + fn bug(&self, fmt: fmt::Arguments<'_>) -> !; +} + +/// Context that provides information global to a match. +#[derive(derivative::Derivative)] +#[derivative(Clone(bound = ""), Copy(bound = ""))] +pub struct MatchCtxt<'a, 'p, Cx: TypeCx> { + /// The context for type information. + pub tycx: &'a Cx, + /// An arena to store the wildcards we produce during analysis. + pub wildcard_arena: &'a TypedArena<DeconstructedPat<'p, Cx>>, +} /// The arm of a match expression. -#[derive(Clone, Copy, Debug)] -pub struct MatchArm<'p, 'tcx> { - /// The pattern must have been lowered through `check_match::MatchVisitor::lower_pattern`. - pub pat: &'p DeconstructedPat<'p, 'tcx>, - pub hir_id: HirId, +#[derive(Debug)] +#[derive(derivative::Derivative)] +#[derivative(Clone(bound = ""), Copy(bound = ""))] +pub struct MatchArm<'p, Cx: TypeCx> { + pub pat: &'p DeconstructedPat<'p, Cx>, pub has_guard: bool, + pub arm_data: Cx::ArmData, } /// The entrypoint for this crate. Computes whether a match is exhaustive and which of its arms are /// useful, and runs some lints. +#[cfg(feature = "rustc")] pub fn analyze_match<'p, 'tcx>( - cx: &MatchCheckCtxt<'p, 'tcx>, - arms: &[MatchArm<'p, 'tcx>], + tycx: &RustcMatchCheckCtxt<'p, 'tcx>, + arms: &[rustc::MatchArm<'p, 'tcx>], scrut_ty: Ty<'tcx>, -) -> UsefulnessReport<'p, 'tcx> { - let pat_column = PatternColumn::new(arms); +) -> rustc::UsefulnessReport<'p, 'tcx> { + // Arena to store the extra wildcards we construct during analysis. + let wildcard_arena = tycx.pattern_arena; + let scrut_validity = ValidityConstraint::from_bool(tycx.known_valid_scrutinee); + let cx = MatchCtxt { tycx, wildcard_arena }; - let report = compute_match_usefulness(cx, arms, scrut_ty); + let report = compute_match_usefulness(cx, arms, scrut_ty, scrut_validity); + + let pat_column = PatternColumn::new(arms); // 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 && report.non_exhaustiveness_witnesses.is_empty() { + if tycx.refutable && report.non_exhaustiveness_witnesses.is_empty() { lint_nonexhaustive_missing_variants(cx, arms, &pat_column, scrut_ty) } diff --git a/compiler/rustc_pattern_analysis/src/lints.rs b/compiler/rustc_pattern_analysis/src/lints.rs index 8ab559c9e7a..bba1f406056 100644 --- a/compiler/rustc_pattern_analysis/src/lints.rs +++ b/compiler/rustc_pattern_analysis/src/lints.rs @@ -6,15 +6,16 @@ use rustc_session::lint; use rustc_session::lint::builtin::NON_EXHAUSTIVE_OMITTED_PATTERNS; use rustc_span::Span; -use crate::constructor::{Constructor, IntRange, MaybeInfiniteInt, SplitConstructorSet}; -use crate::cx::MatchCheckCtxt; +use crate::constructor::{IntRange, MaybeInfiniteInt}; use crate::errors::{ NonExhaustiveOmittedPattern, NonExhaustiveOmittedPatternLintOnArm, Overlap, OverlappingRangeEndpoints, Uncovered, }; -use crate::pat::{DeconstructedPat, WitnessPat}; -use crate::usefulness::PatCtxt; -use crate::MatchArm; +use crate::rustc::{ + Constructor, DeconstructedPat, MatchArm, MatchCtxt, PlaceCtxt, RustcMatchCheckCtxt, + SplitConstructorSet, WitnessPat, +}; +use crate::TypeCx; /// A column of patterns in the matrix, where a column is the intuitive notion of "subpatterns that /// inspect the same subvalue/place". @@ -27,11 +28,11 @@ use crate::MatchArm; /// /// This is not used in the main algorithm; only in lints. #[derive(Debug)] -pub(crate) struct PatternColumn<'p, 'tcx> { - patterns: Vec<&'p DeconstructedPat<'p, 'tcx>>, +pub(crate) struct PatternColumn<'a, 'p, 'tcx> { + patterns: Vec<&'a DeconstructedPat<'p, 'tcx>>, } -impl<'p, 'tcx> PatternColumn<'p, 'tcx> { +impl<'a, 'p, 'tcx> PatternColumn<'a, 'p, 'tcx> { pub(crate) fn new(arms: &[MatchArm<'p, 'tcx>]) -> Self { let mut patterns = Vec::with_capacity(arms.len()); for arm in arms { @@ -47,32 +48,23 @@ impl<'p, 'tcx> PatternColumn<'p, 'tcx> { fn is_empty(&self) -> bool { self.patterns.is_empty() } - fn head_ty(&self) -> Option<Ty<'tcx>> { + fn head_ty(&self, cx: MatchCtxt<'a, 'p, 'tcx>) -> Option<Ty<'tcx>> { if self.patterns.len() == 0 { return None; } - // 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, ..)); - let first_ty = self.patterns[0].ty(); - if is_opaque(first_ty) { - for pat in &self.patterns { - let ty = pat.ty(); - if !is_opaque(ty) { - return Some(ty); - } - } - } - Some(first_ty) + + let ty = self.patterns[0].ty(); + // FIXME(Nadrieril): `Cx` should only give us revealed types. + Some(cx.tycx.reveal_opaque_ty(ty)) } /// Do constructor splitting on the constructors of the column. - fn analyze_ctors(&self, pcx: &PatCtxt<'_, 'p, 'tcx>) -> SplitConstructorSet<'tcx> { + fn analyze_ctors(&self, pcx: &PlaceCtxt<'_, 'p, 'tcx>) -> SplitConstructorSet<'p, 'tcx> { let column_ctors = self.patterns.iter().map(|p| p.ctor()); - pcx.cx.ctors_for_ty(pcx.ty).split(pcx, column_ctors) + pcx.ctors_for_ty().split(pcx, column_ctors) } - fn iter<'a>(&'a self) -> impl Iterator<Item = &'p DeconstructedPat<'p, 'tcx>> + Captures<'a> { + fn iter<'b>(&'b self) -> impl Iterator<Item = &'a DeconstructedPat<'p, 'tcx>> + Captures<'b> { self.patterns.iter().copied() } @@ -81,7 +73,11 @@ impl<'p, 'tcx> PatternColumn<'p, 'tcx> { /// 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> { + fn specialize( + &self, + pcx: &PlaceCtxt<'a, 'p, 'tcx>, + ctor: &Constructor<'p, 'tcx>, + ) -> Vec<PatternColumn<'a, 'p, 'tcx>> { let arity = ctor.arity(pcx); if arity == 0 { return Vec::new(); @@ -117,14 +113,14 @@ impl<'p, 'tcx> PatternColumn<'p, 'tcx> { /// Traverse the patterns to collect any variants of a non_exhaustive enum that fail to be mentioned /// in a given column. #[instrument(level = "debug", skip(cx), ret)] -fn collect_nonexhaustive_missing_variants<'p, 'tcx>( - cx: &MatchCheckCtxt<'p, 'tcx>, - column: &PatternColumn<'p, 'tcx>, -) -> Vec<WitnessPat<'tcx>> { - let Some(ty) = column.head_ty() else { +fn collect_nonexhaustive_missing_variants<'a, 'p, 'tcx>( + cx: MatchCtxt<'a, 'p, 'tcx>, + column: &PatternColumn<'a, 'p, 'tcx>, +) -> Vec<WitnessPat<'p, 'tcx>> { + let Some(ty) = column.head_ty(cx) else { return Vec::new(); }; - let pcx = &PatCtxt::new_dummy(cx, ty); + let pcx = &PlaceCtxt::new_dummy(cx, ty); let set = column.analyze_ctors(pcx); if set.present.is_empty() { @@ -135,7 +131,7 @@ fn collect_nonexhaustive_missing_variants<'p, 'tcx>( } let mut witnesses = Vec::new(); - if cx.is_foreign_non_exhaustive_enum(ty) { + if cx.tycx.is_foreign_non_exhaustive_enum(ty) { witnesses.extend( set.missing .into_iter() @@ -164,14 +160,15 @@ fn collect_nonexhaustive_missing_variants<'p, 'tcx>( witnesses } -pub(crate) fn lint_nonexhaustive_missing_variants<'p, 'tcx>( - cx: &MatchCheckCtxt<'p, 'tcx>, +pub(crate) fn lint_nonexhaustive_missing_variants<'a, 'p, 'tcx>( + cx: MatchCtxt<'a, 'p, 'tcx>, arms: &[MatchArm<'p, 'tcx>], - pat_column: &PatternColumn<'p, 'tcx>, + pat_column: &PatternColumn<'a, 'p, 'tcx>, scrut_ty: Ty<'tcx>, ) { + let rcx: &RustcMatchCheckCtxt<'_, '_> = cx.tycx; if !matches!( - cx.tcx.lint_level_at_node(NON_EXHAUSTIVE_OMITTED_PATTERNS, cx.match_lint_level).0, + rcx.tcx.lint_level_at_node(NON_EXHAUSTIVE_OMITTED_PATTERNS, rcx.match_lint_level).0, rustc_session::lint::Level::Allow ) { let witnesses = collect_nonexhaustive_missing_variants(cx, pat_column); @@ -180,13 +177,13 @@ pub(crate) fn lint_nonexhaustive_missing_variants<'p, 'tcx>( // is not exhaustive enough. // // NB: The partner lint for structs lives in `compiler/rustc_hir_analysis/src/check/pat.rs`. - cx.tcx.emit_spanned_lint( + rcx.tcx.emit_spanned_lint( NON_EXHAUSTIVE_OMITTED_PATTERNS, - cx.match_lint_level, - cx.scrut_span, + rcx.match_lint_level, + rcx.scrut_span, NonExhaustiveOmittedPattern { scrut_ty, - uncovered: Uncovered::new(cx.scrut_span, cx, witnesses), + uncovered: Uncovered::new(rcx.scrut_span, rcx, witnesses), }, ); } @@ -196,17 +193,17 @@ pub(crate) fn lint_nonexhaustive_missing_variants<'p, 'tcx>( // usage of the lint. for arm in arms { let (lint_level, lint_level_source) = - cx.tcx.lint_level_at_node(NON_EXHAUSTIVE_OMITTED_PATTERNS, arm.hir_id); + rcx.tcx.lint_level_at_node(NON_EXHAUSTIVE_OMITTED_PATTERNS, arm.arm_data); if !matches!(lint_level, rustc_session::lint::Level::Allow) { let decorator = NonExhaustiveOmittedPatternLintOnArm { lint_span: lint_level_source.span(), - suggest_lint_on_match: cx.whole_match_span.map(|span| span.shrink_to_lo()), + suggest_lint_on_match: rcx.whole_match_span.map(|span| span.shrink_to_lo()), lint_level: lint_level.as_str(), lint_name: "non_exhaustive_omitted_patterns", }; use rustc_errors::DecorateLint; - let mut err = cx.tcx.sess.struct_span_warn(arm.pat.span(), ""); + let mut err = rcx.tcx.dcx().struct_span_warn(*arm.pat.data().unwrap(), ""); err.set_primary_message(decorator.msg()); decorator.decorate_lint(&mut err); err.emit(); @@ -217,28 +214,29 @@ pub(crate) fn lint_nonexhaustive_missing_variants<'p, 'tcx>( /// Traverse the patterns to warn the user about ranges that overlap on their endpoints. #[instrument(level = "debug", skip(cx))] -pub(crate) fn lint_overlapping_range_endpoints<'p, 'tcx>( - cx: &MatchCheckCtxt<'p, 'tcx>, - column: &PatternColumn<'p, 'tcx>, +pub(crate) fn lint_overlapping_range_endpoints<'a, 'p, 'tcx>( + cx: MatchCtxt<'a, 'p, 'tcx>, + column: &PatternColumn<'a, 'p, 'tcx>, ) { - let Some(ty) = column.head_ty() else { + let Some(ty) = column.head_ty(cx) else { return; }; - let pcx = &PatCtxt::new_dummy(cx, ty); + let pcx = &PlaceCtxt::new_dummy(cx, ty); + let rcx: &RustcMatchCheckCtxt<'_, '_> = cx.tycx; let set = column.analyze_ctors(pcx); if matches!(ty.kind(), ty::Char | ty::Int(_) | ty::Uint(_)) { let emit_lint = |overlap: &IntRange, this_span: Span, overlapped_spans: &[Span]| { - let overlap_as_pat = cx.hoist_pat_range(overlap, ty); + let overlap_as_pat = rcx.hoist_pat_range(overlap, ty); let overlaps: Vec<_> = overlapped_spans .iter() .copied() .map(|span| Overlap { range: overlap_as_pat.clone(), span }) .collect(); - cx.tcx.emit_spanned_lint( + rcx.tcx.emit_spanned_lint( lint::builtin::OVERLAPPING_RANGE_ENDPOINTS, - cx.match_lint_level, + rcx.match_lint_level, this_span, OverlappingRangeEndpoints { overlap: overlaps, range: this_span }, ); @@ -255,8 +253,8 @@ pub(crate) fn lint_overlapping_range_endpoints<'p, 'tcx>( let mut suffixes: SmallVec<[_; 1]> = Default::default(); // Iterate on patterns that contained `overlap`. for pat in column.iter() { - let this_span = pat.span(); let Constructor::IntRange(this_range) = pat.ctor() else { continue }; + let this_span = *pat.data().unwrap(); if this_range.is_singleton() { // Don't lint when one of the ranges is a singleton. continue; diff --git a/compiler/rustc_pattern_analysis/src/pat.rs b/compiler/rustc_pattern_analysis/src/pat.rs index 404651124ad..9efd3e864da 100644 --- a/compiler/rustc_pattern_analysis/src/pat.rs +++ b/compiler/rustc_pattern_analysis/src/pat.rs @@ -5,16 +5,11 @@ use std::fmt; use smallvec::{smallvec, SmallVec}; -use rustc_data_structures::captures::Captures; -use rustc_middle::ty::{self, Ty}; -use rustc_span::{Span, DUMMY_SP}; +use crate::constructor::{Constructor, Slice, SliceKind}; +use crate::usefulness::PlaceCtxt; +use crate::{Captures, TypeCx}; use self::Constructor::*; -use self::SliceKind::*; - -use crate::constructor::{Constructor, SliceKind}; -use crate::cx::MatchCheckCtxt; -use crate::usefulness::PatCtxt; /// Values and patterns can be represented as a constructor applied to some fields. This represents /// a pattern in this form. @@ -27,34 +22,36 @@ use crate::usefulness::PatCtxt; /// This happens if a private or `non_exhaustive` field is uninhabited, because the code mustn't /// observe that it is uninhabited. In that case that field is not included in `fields`. Care must /// be taken when converting to/from `thir::Pat`. -pub struct DeconstructedPat<'p, 'tcx> { - ctor: Constructor<'tcx>, - fields: &'p [DeconstructedPat<'p, 'tcx>], - ty: Ty<'tcx>, - span: Span, +pub struct DeconstructedPat<'p, Cx: TypeCx> { + ctor: Constructor<Cx>, + fields: &'p [DeconstructedPat<'p, Cx>], + ty: Cx::Ty, + /// Extra data to store in a pattern. `None` if the pattern is a wildcard that does not + /// correspond to a user-supplied pattern. + data: Option<Cx::PatData>, /// Whether removing this arm would change the behavior of the match expression. useful: Cell<bool>, } -impl<'p, 'tcx> DeconstructedPat<'p, 'tcx> { - pub fn wildcard(ty: Ty<'tcx>, span: Span) -> Self { - Self::new(Wildcard, &[], ty, span) +impl<'p, Cx: TypeCx> DeconstructedPat<'p, Cx> { + pub fn wildcard(ty: Cx::Ty) -> Self { + DeconstructedPat { ctor: Wildcard, fields: &[], ty, data: None, useful: Cell::new(false) } } pub fn new( - ctor: Constructor<'tcx>, - fields: &'p [DeconstructedPat<'p, 'tcx>], - ty: Ty<'tcx>, - span: Span, + ctor: Constructor<Cx>, + fields: &'p [DeconstructedPat<'p, Cx>], + ty: Cx::Ty, + data: Cx::PatData, ) -> Self { - DeconstructedPat { ctor, fields, ty, span, useful: Cell::new(false) } + DeconstructedPat { ctor, fields, ty, data: Some(data), useful: Cell::new(false) } } pub(crate) fn is_or_pat(&self) -> bool { matches!(self.ctor, Or) } /// Expand this (possibly-nested) or-pattern into its alternatives. - pub(crate) fn flatten_or_pat(&'p self) -> SmallVec<[&'p Self; 1]> { + pub(crate) fn flatten_or_pat(&self) -> SmallVec<[&Self; 1]> { if self.is_or_pat() { self.iter_fields().flat_map(|p| p.flatten_or_pat()).collect() } else { @@ -62,66 +59,66 @@ impl<'p, 'tcx> DeconstructedPat<'p, 'tcx> { } } - pub fn ctor(&self) -> &Constructor<'tcx> { + pub fn ctor(&self) -> &Constructor<Cx> { &self.ctor } - pub fn ty(&self) -> Ty<'tcx> { + pub fn ty(&self) -> Cx::Ty { self.ty } - pub fn span(&self) -> Span { - self.span + /// Returns the extra data stored in a pattern. Returns `None` if the pattern is a wildcard that + /// does not correspond to a user-supplied pattern. + pub fn data(&self) -> Option<&Cx::PatData> { + self.data.as_ref() } pub fn iter_fields<'a>( &'a self, - ) -> impl Iterator<Item = &'p DeconstructedPat<'p, 'tcx>> + Captures<'a> { + ) -> impl Iterator<Item = &'p DeconstructedPat<'p, Cx>> + Captures<'a> { self.fields.iter() } /// Specialize this pattern with a constructor. /// `other_ctor` can be different from `self.ctor`, but must be covered by it. pub(crate) fn specialize<'a>( - &'a self, - pcx: &PatCtxt<'_, 'p, 'tcx>, - other_ctor: &Constructor<'tcx>, - ) -> SmallVec<[&'p DeconstructedPat<'p, 'tcx>; 2]> { + &self, + pcx: &PlaceCtxt<'a, 'p, Cx>, + other_ctor: &Constructor<Cx>, + ) -> SmallVec<[&'a DeconstructedPat<'p, Cx>; 2]> { + let wildcard_sub_tys = || { + let tys = pcx.ctor_sub_tys(other_ctor); + tys.iter() + .map(|ty| DeconstructedPat::wildcard(*ty)) + .map(|pat| pcx.mcx.wildcard_arena.alloc(pat) as &_) + .collect() + }; match (&self.ctor, other_ctor) { - (Wildcard, _) => { - // We return a wildcard for each field of `other_ctor`. - pcx.cx.ctor_wildcard_fields(other_ctor, pcx.ty).iter().collect() - } - (Slice(self_slice), Slice(other_slice)) - if self_slice.arity() != other_slice.arity() => - { - // The only tricky case: two slices of different arity. Since `self_slice` covers - // `other_slice`, `self_slice` must be `VarLen`, i.e. of the form - // `[prefix, .., suffix]`. Moreover `other_slice` is guaranteed to have a larger - // arity. So we fill the middle part with enough wildcards to reach the length of - // the new, larger slice. - match self_slice.kind { - FixedLen(_) => bug!("{:?} doesn't cover {:?}", self_slice, other_slice), - VarLen(prefix, suffix) => { - let (ty::Slice(inner_ty) | ty::Array(inner_ty, _)) = *self.ty.kind() else { - bug!("bad slice pattern {:?} {:?}", self.ctor, self.ty); - }; - let prefix = &self.fields[..prefix]; - let suffix = &self.fields[self_slice.arity() - suffix..]; - let wildcard: &_ = pcx - .cx - .pattern_arena - .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() - } + // Return a wildcard for each field of `other_ctor`. + (Wildcard, _) => wildcard_sub_tys(), + // The only non-trivial case: two slices of different arity. `other_slice` is + // guaranteed to have a larger arity, so we fill the middle part with enough + // wildcards to reach the length of the new, larger slice. + ( + &Slice(self_slice @ Slice { kind: SliceKind::VarLen(prefix, suffix), .. }), + &Slice(other_slice), + ) if self_slice.arity() != other_slice.arity() => { + // Start with a slice of wildcards of the appropriate length. + let mut fields: SmallVec<[_; 2]> = wildcard_sub_tys(); + // Fill in the fields from both ends. + let new_arity = fields.len(); + for i in 0..prefix { + fields[i] = &self.fields[i]; + } + for i in 0..suffix { + fields[new_arity - 1 - i] = &self.fields[self.fields.len() - 1 - i]; } + fields } _ => self.fields.iter().collect(), } } - /// We keep track for each pattern if it was ever useful during the analysis. This is used - /// with `redundant_spans` to report redundant subpatterns arising from or patterns. + /// We keep track for each pattern if it was ever useful during the analysis. This is used with + /// `redundant_subpatterns` to report redundant subpatterns arising from or patterns. pub(crate) fn set_useful(&self) { self.useful.set(true) } @@ -139,19 +136,19 @@ impl<'p, 'tcx> DeconstructedPat<'p, 'tcx> { } } - /// Report the spans of subpatterns that were not useful, if any. - pub(crate) fn redundant_spans(&self) -> Vec<Span> { - let mut spans = Vec::new(); - self.collect_redundant_spans(&mut spans); - spans + /// Report the subpatterns that were not useful, if any. + pub(crate) fn redundant_subpatterns(&self) -> Vec<&Self> { + let mut subpats = Vec::new(); + self.collect_redundant_subpatterns(&mut subpats); + subpats } - fn collect_redundant_spans(&self, spans: &mut Vec<Span>) { + fn collect_redundant_subpatterns<'a>(&'a self, subpats: &mut Vec<&'a Self>) { // We don't look at subpatterns if we already reported the whole pattern as redundant. if !self.is_useful() { - spans.push(self.span); + subpats.push(self); } else { for p in self.iter_fields() { - p.collect_redundant_spans(spans); + p.collect_redundant_subpatterns(subpats); } } } @@ -159,47 +156,47 @@ impl<'p, 'tcx> DeconstructedPat<'p, 'tcx> { /// This is mostly copied from the `Pat` impl. This is best effort and not good enough for a /// `Display` impl. -impl<'p, 'tcx> fmt::Debug for DeconstructedPat<'p, 'tcx> { +impl<'p, Cx: TypeCx> fmt::Debug for DeconstructedPat<'p, Cx> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - MatchCheckCtxt::debug_pat(f, self) + Cx::debug_pat(f, self) } } /// Same idea as `DeconstructedPat`, except this is a fictitious pattern built up for diagnostics /// purposes. As such they don't use interning and can be cloned. -#[derive(Debug, Clone)] -pub struct WitnessPat<'tcx> { - ctor: Constructor<'tcx>, - pub(crate) fields: Vec<WitnessPat<'tcx>>, - ty: Ty<'tcx>, +#[derive(derivative::Derivative)] +#[derivative(Debug(bound = ""), Clone(bound = ""))] +pub struct WitnessPat<Cx: TypeCx> { + ctor: Constructor<Cx>, + pub(crate) fields: Vec<WitnessPat<Cx>>, + ty: Cx::Ty, } -impl<'tcx> WitnessPat<'tcx> { - pub(crate) fn new(ctor: Constructor<'tcx>, fields: Vec<Self>, ty: Ty<'tcx>) -> Self { +impl<Cx: TypeCx> WitnessPat<Cx> { + pub(crate) fn new(ctor: Constructor<Cx>, fields: Vec<Self>, ty: Cx::Ty) -> Self { Self { ctor, fields, ty } } - pub(crate) fn wildcard(ty: Ty<'tcx>) -> Self { + pub(crate) fn wildcard(ty: Cx::Ty) -> Self { Self::new(Wildcard, Vec::new(), ty) } /// Construct a pattern that matches everything that starts with this constructor. /// For example, if `ctor` is a `Constructor::Variant` for `Option::Some`, we get the pattern /// `Some(_)`. - pub(crate) fn wild_from_ctor(pcx: &PatCtxt<'_, '_, 'tcx>, ctor: Constructor<'tcx>) -> Self { - let field_tys = - pcx.cx.ctor_wildcard_fields(&ctor, pcx.ty).iter().map(|deco_pat| deco_pat.ty()); - let fields = field_tys.map(|ty| Self::wildcard(ty)).collect(); + pub(crate) fn wild_from_ctor(pcx: &PlaceCtxt<'_, '_, Cx>, ctor: Constructor<Cx>) -> Self { + let field_tys = pcx.ctor_sub_tys(&ctor); + let fields = field_tys.iter().map(|ty| Self::wildcard(*ty)).collect(); Self::new(ctor, fields, pcx.ty) } - pub fn ctor(&self) -> &Constructor<'tcx> { + pub fn ctor(&self) -> &Constructor<Cx> { &self.ctor } - pub fn ty(&self) -> Ty<'tcx> { + pub fn ty(&self) -> Cx::Ty { self.ty } - pub fn iter_fields<'a>(&'a self) -> impl Iterator<Item = &'a WitnessPat<'tcx>> { + pub fn iter_fields<'a>(&'a self) -> impl Iterator<Item = &'a WitnessPat<Cx>> { self.fields.iter() } } diff --git a/compiler/rustc_pattern_analysis/src/cx.rs b/compiler/rustc_pattern_analysis/src/rustc.rs index 8a4f39a1f4a..a5a47724f3f 100644 --- a/compiler/rustc_pattern_analysis/src/cx.rs +++ b/compiler/rustc_pattern_analysis/src/rustc.rs @@ -1,32 +1,50 @@ use std::fmt; use std::iter::once; -use rustc_arena::TypedArena; +use rustc_arena::{DroplessArena, TypedArena}; use rustc_data_structures::captures::Captures; use rustc_hir::def_id::DefId; -use rustc_hir::{HirId, RangeEnd}; +use rustc_hir::HirId; use rustc_index::Idx; use rustc_index::IndexVec; use rustc_middle::middle::stability::EvalResult; -use rustc_middle::mir; use rustc_middle::mir::interpret::Scalar; +use rustc_middle::mir::{self, Const}; use rustc_middle::thir::{FieldPat, Pat, PatKind, PatRange, PatRangeBoundary}; use rustc_middle::ty::layout::IntegerExt; -use rustc_middle::ty::{self, Ty, TyCtxt, VariantDef}; +use rustc_middle::ty::{self, OpaqueTypeKey, Ty, TyCtxt, VariantDef}; use rustc_span::{Span, DUMMY_SP}; use rustc_target::abi::{FieldIdx, Integer, VariantIdx, FIRST_VARIANT}; use smallvec::SmallVec; use crate::constructor::{ - Constructor, ConstructorSet, IntRange, MaybeInfiniteInt, OpaqueId, Slice, SliceKind, - VariantVisibility, + IntRange, MaybeInfiniteInt, OpaqueId, RangeEnd, Slice, SliceKind, VariantVisibility, }; -use crate::pat::{DeconstructedPat, WitnessPat}; +use crate::TypeCx; -use Constructor::*; +use crate::constructor::Constructor::*; -pub struct MatchCheckCtxt<'p, 'tcx> { +// Re-export rustc-specific versions of all these types. +pub type Constructor<'p, 'tcx> = crate::constructor::Constructor<RustcMatchCheckCtxt<'p, 'tcx>>; +pub type ConstructorSet<'p, 'tcx> = + crate::constructor::ConstructorSet<RustcMatchCheckCtxt<'p, 'tcx>>; +pub type DeconstructedPat<'p, 'tcx> = + crate::pat::DeconstructedPat<'p, RustcMatchCheckCtxt<'p, 'tcx>>; +pub type MatchArm<'p, 'tcx> = crate::MatchArm<'p, RustcMatchCheckCtxt<'p, 'tcx>>; +pub type MatchCtxt<'a, 'p, 'tcx> = crate::MatchCtxt<'a, 'p, RustcMatchCheckCtxt<'p, 'tcx>>; +pub(crate) type PlaceCtxt<'a, 'p, 'tcx> = + crate::usefulness::PlaceCtxt<'a, 'p, RustcMatchCheckCtxt<'p, 'tcx>>; +pub(crate) type SplitConstructorSet<'p, 'tcx> = + crate::constructor::SplitConstructorSet<RustcMatchCheckCtxt<'p, 'tcx>>; +pub type Usefulness<'p, 'tcx> = crate::usefulness::Usefulness<'p, RustcMatchCheckCtxt<'p, 'tcx>>; +pub type UsefulnessReport<'p, 'tcx> = + crate::usefulness::UsefulnessReport<'p, RustcMatchCheckCtxt<'p, 'tcx>>; +pub type WitnessPat<'p, 'tcx> = crate::pat::WitnessPat<RustcMatchCheckCtxt<'p, 'tcx>>; + +#[derive(Clone)] +pub struct RustcMatchCheckCtxt<'p, 'tcx> { pub tcx: TyCtxt<'tcx>, + pub typeck_results: &'tcx ty::TypeckResults<'tcx>, /// The module in which the match occurs. This is necessary for /// checking inhabited-ness of types because whether a type is (visibly) /// inhabited can depend on whether it was defined in the current module or @@ -35,6 +53,7 @@ pub struct MatchCheckCtxt<'p, 'tcx> { pub module: DefId, pub param_env: ty::ParamEnv<'tcx>, pub pattern_arena: &'p TypedArena<DeconstructedPat<'p, 'tcx>>, + pub dropless_arena: &'p DroplessArena, /// Lint level at the match. pub match_lint_level: HirId, /// The span of the whole match, if applicable. @@ -48,9 +67,23 @@ pub struct MatchCheckCtxt<'p, 'tcx> { pub known_valid_scrutinee: bool, } -impl<'p, 'tcx> MatchCheckCtxt<'p, 'tcx> { - pub(super) fn is_uninhabited(&self, ty: Ty<'tcx>) -> bool { - !ty.is_inhabited_from(self.tcx, self.module, self.param_env) +impl<'p, 'tcx> fmt::Debug for RustcMatchCheckCtxt<'p, 'tcx> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_struct("RustcMatchCheckCtxt").finish() + } +} + +impl<'p, 'tcx> RustcMatchCheckCtxt<'p, 'tcx> { + fn reveal_opaque(&self, key: OpaqueTypeKey<'tcx>) -> Option<Ty<'tcx>> { + self.typeck_results.concrete_opaque_types.get(&key).map(|x| x.ty) + } + pub fn is_uninhabited(&self, ty: Ty<'tcx>) -> bool { + !ty.inhabited_predicate(self.tcx).apply_revealing_opaque( + self.tcx, + self.param_env, + self.module, + &|key| self.reveal_opaque(key), + ) } /// Returns whether the given type is an enum from another crate declared `#[non_exhaustive]`. @@ -63,12 +96,33 @@ impl<'p, 'tcx> MatchCheckCtxt<'p, 'tcx> { } } - pub(crate) fn alloc_wildcard_slice( - &self, - tys: impl IntoIterator<Item = Ty<'tcx>>, - ) -> &'p [DeconstructedPat<'p, 'tcx>] { - self.pattern_arena - .alloc_from_iter(tys.into_iter().map(|ty| DeconstructedPat::wildcard(ty, DUMMY_SP))) + /// Whether the range denotes the fictitious values before `isize::MIN` or after + /// `usize::MAX`/`isize::MAX` (see doc of [`IntRange::split`] for why these exist). + pub fn is_range_beyond_boundaries(&self, range: &IntRange, ty: Ty<'tcx>) -> bool { + ty.is_ptr_sized_integral() && { + // The two invalid ranges are `NegInfinity..isize::MIN` (represented as + // `NegInfinity..0`), and `{u,i}size::MAX+1..PosInfinity`. `hoist_pat_range_bdy` + // converts `MAX+1` to `PosInfinity`, and we couldn't have `PosInfinity` in `range.lo` + // otherwise. + let lo = self.hoist_pat_range_bdy(range.lo, ty); + matches!(lo, PatRangeBoundary::PosInfinity) + || matches!(range.hi, MaybeInfiniteInt::Finite(0)) + } + } + + /// Type inference occasionally gives us opaque types in places where corresponding patterns + /// have more specific types. To avoid inconsistencies as well as detect opaque uninhabited + /// types, we use the corresponding concrete type if possible. + fn reveal_opaque_ty(&self, ty: Ty<'tcx>) -> Ty<'tcx> { + if let ty::Alias(ty::Opaque, alias_ty) = ty.kind() { + if let Some(local_def_id) = alias_ty.def_id.as_local() { + let key = ty::OpaqueTypeKey { def_id: local_def_id, args: alias_ty.args }; + if let Some(real_ty) = self.typeck_results.concrete_opaque_types.get(&key) { + return real_ty.ty; + } + } + } + ty } // In the cases of either a `#[non_exhaustive]` field list or a non-public field, we hide @@ -100,12 +154,12 @@ impl<'p, 'tcx> MatchCheckCtxt<'p, 'tcx> { } pub(crate) fn variant_index_for_adt( - ctor: &Constructor<'tcx>, + ctor: &Constructor<'p, 'tcx>, adt: ty::AdtDef<'tcx>, ) -> VariantIdx { match *ctor { Variant(idx) => idx, - Single => { + Struct | UnionField => { assert!(!adt.is_enum()); FIRST_VARIANT } @@ -113,37 +167,36 @@ impl<'p, 'tcx> MatchCheckCtxt<'p, 'tcx> { } } - /// Creates a new list of wildcard fields for a given constructor. The result must have a length - /// of `ctor.arity()`. + /// Returns the types of the fields for a given constructor. The result must have a length of + /// `ctor.arity()`. #[instrument(level = "trace", skip(self))] - pub(crate) fn ctor_wildcard_fields( - &self, - ctor: &Constructor<'tcx>, - ty: Ty<'tcx>, - ) -> &'p [DeconstructedPat<'p, 'tcx>] { + pub(crate) fn ctor_sub_tys(&self, ctor: &Constructor<'p, 'tcx>, ty: Ty<'tcx>) -> &[Ty<'tcx>] { let cx = self; match ctor { - Single | Variant(_) => match ty.kind() { - ty::Tuple(fs) => cx.alloc_wildcard_slice(fs.iter()), - ty::Ref(_, rty, _) => cx.alloc_wildcard_slice(once(*rty)), + Struct | Variant(_) | UnionField => match ty.kind() { + ty::Tuple(fs) => cx.dropless_arena.alloc_from_iter(fs.iter()), 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. - cx.alloc_wildcard_slice(once(args.type_at(0))) + cx.dropless_arena.alloc_from_iter(once(args.type_at(0))) } else { let variant = - &adt.variant(MatchCheckCtxt::variant_index_for_adt(&ctor, *adt)); + &adt.variant(RustcMatchCheckCtxt::variant_index_for_adt(&ctor, *adt)); let tys = cx.list_variant_nonhidden_fields(ty, variant).map(|(_, ty)| ty); - cx.alloc_wildcard_slice(tys) + cx.dropless_arena.alloc_from_iter(tys) } } - _ => bug!("Unexpected type for `Single` constructor: {:?}", ty), + _ => bug!("Unexpected type for constructor `{ctor:?}`: {ty:?}"), + }, + Ref => match ty.kind() { + ty::Ref(_, rty, _) => cx.dropless_arena.alloc_from_iter(once(*rty)), + _ => bug!("Unexpected type for `Ref` constructor: {ty:?}"), }, Slice(slice) => match *ty.kind() { ty::Slice(ty) | ty::Array(ty, _) => { let arity = slice.arity(); - cx.alloc_wildcard_slice((0..arity).map(|_| ty)) + cx.dropless_arena.alloc_from_iter((0..arity).map(|_| ty)) } _ => bug!("bad slice pattern {:?} {:?}", ctor, ty), }, @@ -163,13 +216,11 @@ impl<'p, 'tcx> MatchCheckCtxt<'p, 'tcx> { } } - /// The number of fields for this constructor. This must be kept in sync with - /// `Fields::wildcards`. - pub(crate) fn ctor_arity(&self, ctor: &Constructor<'tcx>, ty: Ty<'tcx>) -> usize { + /// The number of fields for this constructor. + pub(crate) fn ctor_arity(&self, ctor: &Constructor<'p, 'tcx>, ty: Ty<'tcx>) -> usize { match ctor { - Single | Variant(_) => match ty.kind() { + Struct | Variant(_) | UnionField => match ty.kind() { ty::Tuple(fs) => fs.len(), - ty::Ref(..) => 1, ty::Adt(adt, ..) => { if adt.is_box() { // The only legal patterns of type `Box` (outside `std`) are `_` and box @@ -177,12 +228,13 @@ impl<'p, 'tcx> MatchCheckCtxt<'p, 'tcx> { 1 } else { let variant = - &adt.variant(MatchCheckCtxt::variant_index_for_adt(&ctor, *adt)); + &adt.variant(RustcMatchCheckCtxt::variant_index_for_adt(&ctor, *adt)); self.list_variant_nonhidden_fields(ty, variant).count() } } - _ => bug!("Unexpected type for `Single` constructor: {:?}", ty), + _ => bug!("Unexpected type for constructor `{ctor:?}`: {ty:?}"), }, + Ref => 1, Slice(slice) => slice.arity(), Bool(..) | IntRange(..) @@ -202,7 +254,7 @@ impl<'p, 'tcx> MatchCheckCtxt<'p, 'tcx> { /// /// See [`crate::constructor`] for considerations of emptiness. #[instrument(level = "debug", skip(self), ret)] - pub fn ctors_for_ty(&self, ty: Ty<'tcx>) -> ConstructorSet { + pub fn ctors_for_ty(&self, ty: Ty<'tcx>) -> ConstructorSet<'p, 'tcx> { let cx = self; let make_uint_range = |start, end| { IntRange::from_range( @@ -275,7 +327,9 @@ impl<'p, 'tcx> MatchCheckCtxt<'p, 'tcx> { let is_inhabited = v .inhabited_predicate(cx.tcx, *def) .instantiate(cx.tcx, args) - .apply(cx.tcx, cx.param_env, cx.module); + .apply_revealing_opaque(cx.tcx, cx.param_env, cx.module, &|key| { + cx.reveal_opaque(key) + }); // Variants that depend on a disabled unstable feature. let is_unstable = matches!( cx.tcx.eval_stability(variant_def_id, None, DUMMY_SP, None), @@ -298,9 +352,9 @@ impl<'p, 'tcx> MatchCheckCtxt<'p, 'tcx> { ConstructorSet::Variants { variants, non_exhaustive: is_declared_nonexhaustive } } } - ty::Adt(..) | ty::Tuple(..) | ty::Ref(..) => { - ConstructorSet::Single { empty: cx.is_uninhabited(ty) } - } + ty::Adt(def, _) if def.is_union() => ConstructorSet::Union, + ty::Adt(..) | ty::Tuple(..) => ConstructorSet::Struct { empty: cx.is_uninhabited(ty) }, + ty::Ref(..) => ConstructorSet::Ref, ty::Never => ConstructorSet::NoConstructors, // This type is one for which we cannot list constructors, like `str` or `f64`. // FIXME(Nadrieril): which of these are actually allowed? @@ -359,15 +413,20 @@ impl<'p, 'tcx> MatchCheckCtxt<'p, 'tcx> { fields = &[]; } PatKind::Deref { subpattern } => { - ctor = Single; fields = singleton(self.lower_pat(subpattern)); + ctor = match pat.ty.kind() { + // This is a box pattern. + ty::Adt(adt, ..) if adt.is_box() => Struct, + ty::Ref(..) => Ref, + _ => bug!("pattern has unexpected type: pat: {:?}, ty: {:?}", pat, pat.ty), + }; } PatKind::Leaf { subpatterns } | PatKind::Variant { subpatterns, .. } => { match pat.ty.kind() { ty::Tuple(fs) => { - ctor = Single; + ctor = Struct; let mut wilds: SmallVec<[_; 2]> = - fs.iter().map(|ty| DeconstructedPat::wildcard(ty, pat.span)).collect(); + fs.iter().map(|ty| DeconstructedPat::wildcard(ty)).collect(); for pat in subpatterns { wilds[pat.field.index()] = self.lower_pat(&pat.pattern); } @@ -380,7 +439,7 @@ impl<'p, 'tcx> MatchCheckCtxt<'p, 'tcx> { // _)` or a box pattern. As a hack to avoid an ICE with the former, we // ignore other fields than the first one. This will trigger an error later // anyway. - // See https://github.com/rust-lang/rust/issues/82772 , + // See https://github.com/rust-lang/rust/issues/82772, // explanation: https://github.com/rust-lang/rust/pull/82789#issuecomment-796921977 // The problem is that we can't know from the type whether we'll match // normally or through box-patterns. We'll have to figure out a proper @@ -390,19 +449,20 @@ impl<'p, 'tcx> MatchCheckCtxt<'p, 'tcx> { let pat = if let Some(pat) = pattern { self.lower_pat(&pat.pattern) } else { - DeconstructedPat::wildcard(args.type_at(0), pat.span) + DeconstructedPat::wildcard(args.type_at(0)) }; - ctor = Single; + ctor = Struct; fields = singleton(pat); } ty::Adt(adt, _) => { ctor = match pat.kind { - PatKind::Leaf { .. } => Single, + PatKind::Leaf { .. } if adt.is_union() => UnionField, + PatKind::Leaf { .. } => Struct, PatKind::Variant { variant_index, .. } => Variant(variant_index), _ => bug!(), }; let variant = - &adt.variant(MatchCheckCtxt::variant_index_for_adt(&ctor, *adt)); + &adt.variant(RustcMatchCheckCtxt::variant_index_for_adt(&ctor, *adt)); // For each field in the variant, we store the relevant index into `self.fields` if any. let mut field_id_to_id: Vec<Option<usize>> = (0..variant.fields.len()).map(|_| None).collect(); @@ -414,7 +474,7 @@ impl<'p, 'tcx> MatchCheckCtxt<'p, 'tcx> { ty }); let mut wilds: SmallVec<[_; 2]> = - tys.map(|ty| DeconstructedPat::wildcard(ty, pat.span)).collect(); + tys.map(|ty| DeconstructedPat::wildcard(ty)).collect(); for pat in subpatterns { if let Some(i) = field_id_to_id[pat.field.index()] { wilds[i] = self.lower_pat(&pat.pattern); @@ -477,11 +537,11 @@ impl<'p, 'tcx> MatchCheckCtxt<'p, 'tcx> { // with other `Deref` patterns. This could have been done in `const_to_pat`, // but that causes issues with the rest of the matching code. // So here, the constructor for a `"foo"` pattern is `&` (represented by - // `Single`), and has one field. That field has constructor `Str(value)` and no - // fields. + // `Ref`), and has one field. That field has constructor `Str(value)` and no + // subfields. // Note: `t` is `str`, not `&str`. let subpattern = DeconstructedPat::new(Str(*value), &[], *t, pat.span); - ctor = Single; + ctor = Ref; fields = singleton(subpattern) } // All constants that can be structurally matched have already been expanded @@ -495,12 +555,16 @@ impl<'p, 'tcx> MatchCheckCtxt<'p, 'tcx> { } PatKind::Range(patrange) => { let PatRange { lo, hi, end, .. } = patrange.as_ref(); + let end = match end { + rustc_hir::RangeEnd::Included => RangeEnd::Included, + rustc_hir::RangeEnd::Excluded => RangeEnd::Excluded, + }; let ty = pat.ty; ctor = match ty.kind() { ty::Char | ty::Int(_) | ty::Uint(_) => { let lo = cx.lower_pat_range_bdy(*lo, ty); let hi = cx.lower_pat_range_bdy(*hi, ty); - IntRange(IntRange::from_range(lo, hi, *end)) + IntRange(IntRange::from_range(lo, hi, end)) } ty::Float(fty) => { use rustc_apfloat::Float; @@ -511,13 +575,13 @@ impl<'p, 'tcx> MatchCheckCtxt<'p, 'tcx> { use rustc_apfloat::ieee::Single; let lo = lo.map(Single::from_bits).unwrap_or(-Single::INFINITY); let hi = hi.map(Single::from_bits).unwrap_or(Single::INFINITY); - F32Range(lo, hi, *end) + F32Range(lo, hi, end) } ty::FloatTy::F64 => { use rustc_apfloat::ieee::Double; let lo = lo.map(Double::from_bits).unwrap_or(-Double::INFINITY); let hi = hi.map(Double::from_bits).unwrap_or(Double::INFINITY); - F64Range(lo, hi, *end) + F64Range(lo, hi, end) } } } @@ -597,20 +661,6 @@ impl<'p, 'tcx> MatchCheckCtxt<'p, 'tcx> { } } - /// Whether the range denotes the fictitious values before `isize::MIN` or after - /// `usize::MAX`/`isize::MAX` (see doc of [`IntRange::split`] for why these exist). - pub fn is_range_beyond_boundaries(&self, range: &IntRange, ty: Ty<'tcx>) -> bool { - ty.is_ptr_sized_integral() && { - // The two invalid ranges are `NegInfinity..isize::MIN` (represented as - // `NegInfinity..0`), and `{u,i}size::MAX+1..PosInfinity`. `hoist_pat_range_bdy` - // converts `MAX+1` to `PosInfinity`, and we couldn't have `PosInfinity` in `range.lo` - // otherwise. - let lo = self.hoist_pat_range_bdy(range.lo, ty); - matches!(lo, PatRangeBoundary::PosInfinity) - || matches!(range.hi, MaybeInfiniteInt::Finite(0)) - } - } - /// Convert back to a `thir::Pat` for diagnostic purposes. pub(crate) fn hoist_pat_range(&self, range: &IntRange, ty: Ty<'tcx>) -> Pat<'tcx> { use MaybeInfiniteInt::*; @@ -623,7 +673,7 @@ impl<'p, 'tcx> MatchCheckCtxt<'p, 'tcx> { PatKind::Constant { value } } else { // We convert to an inclusive range for diagnostics. - let mut end = RangeEnd::Included; + let mut end = rustc_hir::RangeEnd::Included; let mut lo = cx.hoist_pat_range_bdy(range.lo, ty); if matches!(lo, PatRangeBoundary::PosInfinity) { // The only reason to get `PosInfinity` here is the special case where @@ -637,7 +687,7 @@ impl<'p, 'tcx> MatchCheckCtxt<'p, 'tcx> { } let hi = if matches!(range.hi, Finite(0)) { // The range encodes `..ty::MIN`, so we can't convert it to an inclusive range. - end = RangeEnd::Excluded; + end = rustc_hir::RangeEnd::Excluded; range.hi } else { range.hi.minus_one() @@ -650,14 +700,14 @@ impl<'p, 'tcx> MatchCheckCtxt<'p, 'tcx> { } /// Convert back to a `thir::Pat` for diagnostic purposes. This panics for patterns that don't /// appear in diagnostics, like float ranges. - pub fn hoist_witness_pat(&self, pat: &WitnessPat<'tcx>) -> Pat<'tcx> { + pub fn hoist_witness_pat(&self, pat: &WitnessPat<'p, 'tcx>) -> Pat<'tcx> { let cx = self; let is_wildcard = |pat: &Pat<'_>| matches!(pat.kind, PatKind::Wild); let mut subpatterns = pat.iter_fields().map(|p| Box::new(cx.hoist_witness_pat(p))); let kind = match pat.ctor() { Bool(b) => PatKind::Constant { value: mir::Const::from_bool(cx.tcx, *b) }, IntRange(range) => return self.hoist_pat_range(range, pat.ty()), - Single | Variant(_) => match pat.ty().kind() { + Struct | Variant(_) | UnionField => match pat.ty().kind() { ty::Tuple(..) => PatKind::Leaf { subpatterns: subpatterns .enumerate() @@ -672,7 +722,7 @@ impl<'p, 'tcx> MatchCheckCtxt<'p, 'tcx> { } ty::Adt(adt_def, args) => { let variant_index = - MatchCheckCtxt::variant_index_for_adt(&pat.ctor(), *adt_def); + RustcMatchCheckCtxt::variant_index_for_adt(&pat.ctor(), *adt_def); let variant = &adt_def.variant(variant_index); let subpatterns = cx .list_variant_nonhidden_fields(pat.ty(), variant) @@ -686,13 +736,13 @@ impl<'p, 'tcx> MatchCheckCtxt<'p, 'tcx> { PatKind::Leaf { subpatterns } } } - // Note: given the expansion of `&str` patterns done in `expand_pattern`, we should - // be careful to reconstruct the correct constant pattern here. However a string - // literal pattern will never be reported as a non-exhaustiveness witness, so we - // ignore this issue. - ty::Ref(..) => PatKind::Deref { subpattern: subpatterns.next().unwrap() }, _ => bug!("unexpected ctor for type {:?} {:?}", pat.ctor(), pat.ty()), }, + // Note: given the expansion of `&str` patterns done in `expand_pattern`, we should + // be careful to reconstruct the correct constant pattern here. However a string + // literal pattern will never be reported as a non-exhaustiveness witness, so we + // ignore this issue. + Ref => PatKind::Deref { subpattern: subpatterns.next().unwrap() }, Slice(slice) => { match slice.kind { SliceKind::FixedLen(_) => PatKind::Slice { @@ -744,7 +794,7 @@ impl<'p, 'tcx> MatchCheckCtxt<'p, 'tcx> { /// Best-effort `Debug` implementation. pub(crate) fn debug_pat( f: &mut fmt::Formatter<'_>, - pat: &DeconstructedPat<'p, 'tcx>, + pat: &crate::pat::DeconstructedPat<'_, Self>, ) -> fmt::Result { let mut first = true; let mut start_or_continue = |s| { @@ -758,7 +808,7 @@ impl<'p, 'tcx> MatchCheckCtxt<'p, 'tcx> { let mut start_or_comma = || start_or_continue(", "); match pat.ctor() { - Single | Variant(_) => match pat.ty().kind() { + Struct | Variant(_) | UnionField => match pat.ty().kind() { ty::Adt(def, _) if def.is_box() => { // Without `box_patterns`, the only legal pattern of type `Box` is `_` (outside // of `std`). So this branch is only reachable when the feature is enabled and @@ -767,13 +817,14 @@ impl<'p, 'tcx> MatchCheckCtxt<'p, 'tcx> { write!(f, "box {subpattern:?}") } ty::Adt(..) | ty::Tuple(..) => { - let variant = match pat.ty().kind() { - ty::Adt(adt, _) => Some( - adt.variant(MatchCheckCtxt::variant_index_for_adt(pat.ctor(), *adt)), - ), - ty::Tuple(_) => None, - _ => unreachable!(), - }; + let variant = + match pat.ty().kind() { + ty::Adt(adt, _) => Some(adt.variant( + RustcMatchCheckCtxt::variant_index_for_adt(pat.ctor(), *adt), + )), + ty::Tuple(_) => None, + _ => unreachable!(), + }; if let Some(variant) = variant { write!(f, "{}", variant.name)?; @@ -789,15 +840,15 @@ impl<'p, 'tcx> MatchCheckCtxt<'p, 'tcx> { } write!(f, ")") } - // Note: given the expansion of `&str` patterns done in `expand_pattern`, we should - // be careful to detect strings here. However a string literal pattern will never - // be reported as a non-exhaustiveness witness, so we can ignore this issue. - ty::Ref(_, _, mutbl) => { - let subpattern = pat.iter_fields().next().unwrap(); - write!(f, "&{}{:?}", mutbl.prefix_str(), subpattern) - } _ => write!(f, "_"), }, + // Note: given the expansion of `&str` patterns done in `expand_pattern`, we should + // be careful to detect strings here. However a string literal pattern will never + // be reported as a non-exhaustiveness witness, so we can ignore this issue. + Ref => { + let subpattern = pat.iter_fields().next().unwrap(); + write!(f, "&{:?}", subpattern) + } Slice(slice) => { let mut subpatterns = pat.iter_fields(); write!(f, "[")?; @@ -838,6 +889,46 @@ impl<'p, 'tcx> MatchCheckCtxt<'p, 'tcx> { } } +impl<'p, 'tcx> TypeCx for RustcMatchCheckCtxt<'p, 'tcx> { + type Ty = Ty<'tcx>; + type VariantIdx = VariantIdx; + type StrLit = Const<'tcx>; + type ArmData = HirId; + type PatData = Span; + + fn is_exhaustive_patterns_feature_on(&self) -> bool { + self.tcx.features().exhaustive_patterns + } + + fn reveal_opaque_ty(&self, ty: Ty<'tcx>) -> Ty<'tcx> { + self.reveal_opaque_ty(ty) + } + + fn ctor_arity(&self, ctor: &crate::constructor::Constructor<Self>, ty: Self::Ty) -> usize { + self.ctor_arity(ctor, ty) + } + fn ctor_sub_tys( + &self, + ctor: &crate::constructor::Constructor<Self>, + ty: Self::Ty, + ) -> &[Self::Ty] { + self.ctor_sub_tys(ctor, ty) + } + fn ctors_for_ty(&self, ty: Self::Ty) -> crate::constructor::ConstructorSet<Self> { + self.ctors_for_ty(ty) + } + + fn debug_pat( + f: &mut fmt::Formatter<'_>, + pat: &crate::pat::DeconstructedPat<'_, Self>, + ) -> fmt::Result { + Self::debug_pat(f, pat) + } + fn bug(&self, fmt: fmt::Arguments<'_>) -> ! { + span_bug!(self.scrut_span, "{}", fmt) + } +} + /// Recursively expand this pattern into its subpatterns. Only useful for or-patterns. fn expand_or_pat<'p, 'tcx>(pat: &'p Pat<'tcx>) -> Vec<&'p Pat<'tcx>> { fn expand<'p, 'tcx>(pat: &'p Pat<'tcx>, vec: &mut Vec<&'p Pat<'tcx>>) { diff --git a/compiler/rustc_pattern_analysis/src/usefulness.rs b/compiler/rustc_pattern_analysis/src/usefulness.rs index f268a551547..b51b1a1f722 100644 --- a/compiler/rustc_pattern_analysis/src/usefulness.rs +++ b/compiler/rustc_pattern_analysis/src/usefulness.rs @@ -242,7 +242,7 @@ //! Therefore `usefulness(tp_1, tp_2, tq)` returns the single witness-tuple `[Variant2(Some(true), 0)]`. //! //! -//! Computing the set of constructors for a type is done in [`MatchCheckCtxt::ctors_for_ty`]. See +//! Computing the set of constructors for a type is done in [`TypeCx::ctors_for_ty`]. See //! the following sections for more accurate versions of the algorithm and corresponding links. //! //! @@ -300,6 +300,166 @@ //! //! //! +//! # `Missing` and relevancy +//! +//! ## Relevant values +//! +//! Take the following example: +//! +//! ```compile_fail,E0004 +//! # let foo = (true, true); +//! match foo { +//! (true, _) => 1, +//! (_, true) => 2, +//! }; +//! ``` +//! +//! Consider the value `(true, true)`: +//! - Row 2 does not distinguish `(true, true)` and `(false, true)`; +//! - `false` does not show up in the first column of the match, so without knowing anything else we +//! can deduce that `(false, true)` matches the same or fewer rows than `(true, true)`. +//! +//! Using those two facts together, we deduce that `(true, true)` will not give us more usefulness +//! information about row 2 than `(false, true)` would. We say that "`(true, true)` is made +//! irrelevant for row 2 by `(false, true)`". We will use this idea to prune the search tree. +//! +//! +//! ## Computing relevancy +//! +//! We now generalize from the above example to approximate relevancy in a simple way. Note that we +//! will only compute an approximation: we can sometimes determine when a case is irrelevant, but +//! computing this precisely is at least as hard as computing usefulness. +//! +//! Our computation of relevancy relies on the `Missing` constructor. As explained in +//! [`crate::constructor`], `Missing` represents the constructors not present in a given column. For +//! example in the following: +//! +//! ```compile_fail,E0004 +//! enum Direction { North, South, East, West } +//! # let wind = (Direction::North, 0u8); +//! match wind { +//! (Direction::North, _) => 1, +//! (_, 50..) => 2, +//! }; +//! ``` +//! +//! Here `South`, `East` and `West` are missing in the first column, and `0..50` is missing in the +//! second. Both of these sets are represented by `Constructor::Missing` in their corresponding +//! column. +//! +//! We then compute relevancy as follows: during the course of the algorithm, for a row `r`: +//! - if `r` has a wildcard in the first column; +//! - and some constructors are missing in that column; +//! - then any `c != Missing` is considered irrelevant for row `r`. +//! +//! By this we mean that continuing the algorithm by specializing with `c` is guaranteed not to +//! contribute more information about the usefulness of row `r` than what we would get by +//! specializing with `Missing`. The argument is the same as in the previous subsection. +//! +//! Once we've specialized by a constructor `c` that is irrelevant for row `r`, we're guaranteed to +//! only explore values irrelevant for `r`. If we then ever reach a point where we're only exploring +//! values that are irrelevant to all of the rows (including the virtual wildcard row used for +//! exhaustiveness), we skip that case entirely. +//! +//! +//! ## Example +//! +//! Let's go through a variation on the first example: +//! +//! ```compile_fail,E0004 +//! # let foo = (true, true, true); +//! match foo { +//! (true, _, true) => 1, +//! (_, true, _) => 2, +//! }; +//! ``` +//! +//! ```text +//! ┐ Patterns: +//! │ 1. `[(true, _, true)]` +//! │ 2. `[(_, true, _)]` +//! │ 3. `[_]` // virtual extra wildcard row +//! │ +//! │ Specialize with `(,,)`: +//! ├─┐ Patterns: +//! │ │ 1. `[true, _, true]` +//! │ │ 2. `[_, true, _]` +//! │ │ 3. `[_, _, _]` +//! │ │ +//! │ │ There are missing constructors in the first column (namely `false`), hence +//! │ │ `true` is irrelevant for rows 2 and 3. +//! │ │ +//! │ │ Specialize with `true`: +//! │ ├─┐ Patterns: +//! │ │ │ 1. `[_, true]` +//! │ │ │ 2. `[true, _]` // now exploring irrelevant cases +//! │ │ │ 3. `[_, _]` // now exploring irrelevant cases +//! │ │ │ +//! │ │ │ There are missing constructors in the first column (namely `false`), hence +//! │ │ │ `true` is irrelevant for rows 1 and 3. +//! │ │ │ +//! │ │ │ Specialize with `true`: +//! │ │ ├─┐ Patterns: +//! │ │ │ │ 1. `[true]` // now exploring irrelevant cases +//! │ │ │ │ 2. `[_]` // now exploring irrelevant cases +//! │ │ │ │ 3. `[_]` // now exploring irrelevant cases +//! │ │ │ │ +//! │ │ │ │ The current case is irrelevant for all rows: we backtrack immediately. +//! │ │ ├─┘ +//! │ │ │ +//! │ │ │ Specialize with `false`: +//! │ │ ├─┐ Patterns: +//! │ │ │ │ 1. `[true]` +//! │ │ │ │ 3. `[_]` // now exploring irrelevant cases +//! │ │ │ │ +//! │ │ │ │ Specialize with `true`: +//! │ │ │ ├─┐ Patterns: +//! │ │ │ │ │ 1. `[]` +//! │ │ │ │ │ 3. `[]` // now exploring irrelevant cases +//! │ │ │ │ │ +//! │ │ │ │ │ Row 1 is therefore useful. +//! │ │ │ ├─┘ +//! <etc...> +//! ``` +//! +//! Relevancy allowed us to skip the case `(true, true, _)` entirely. In some cases this pruning can +//! give drastic speedups. The case this was built for is the following (#118437): +//! +//! ```ignore(illustrative) +//! match foo { +//! (true, _, _, _, ..) => 1, +//! (_, true, _, _, ..) => 2, +//! (_, _, true, _, ..) => 3, +//! (_, _, _, true, ..) => 4, +//! ... +//! } +//! ``` +//! +//! Without considering relevancy, we would explore all 2^n combinations of the `true` and `Missing` +//! constructors. Relevancy tells us that e.g. `(true, true, false, false, false, ...)` is +//! irrelevant for all the rows. This allows us to skip all cases with more than one `true` +//! constructor, changing the runtime from exponential to linear. +//! +//! +//! ## Relevancy and exhaustiveness +//! +//! For exhaustiveness, we do something slightly different w.r.t relevancy: we do not report +//! witnesses of non-exhaustiveness that are irrelevant for the virtual wildcard row. For example, +//! in: +//! +//! ```ignore(illustrative) +//! match foo { +//! (true, true) => {} +//! } +//! ``` +//! +//! we only report `(false, _)` as missing. This was a deliberate choice made early in the +//! development of rust, for diagnostic and performance purposes. As showed in the previous section, +//! ignoring irrelevant cases preserves usefulness, so this choice still correctly computes whether +//! a match is exhaustive. +//! +//! +//! //! # Or-patterns //! //! What we have described so far works well if there are no or-patterns. To handle them, if the @@ -555,37 +715,46 @@ use smallvec::{smallvec, SmallVec}; use std::fmt; -use rustc_data_structures::{captures::Captures, stack::ensure_sufficient_stack}; -use rustc_middle::ty::{self, Ty}; -use rustc_span::{Span, DUMMY_SP}; - use crate::constructor::{Constructor, ConstructorSet}; -use crate::cx::MatchCheckCtxt; use crate::pat::{DeconstructedPat, WitnessPat}; -use crate::MatchArm; +use crate::{Captures, MatchArm, MatchCtxt, TypeCx, TypedArena}; use self::ValidityConstraint::*; -#[derive(Copy, Clone)] -pub(crate) struct PatCtxt<'a, 'p, 'tcx> { - pub(crate) cx: &'a MatchCheckCtxt<'p, 'tcx>, - /// Type of the current column under investigation. - pub(crate) ty: Ty<'tcx>, - /// Whether the current pattern is the whole pattern as found in a match arm, or if it's a - /// subpattern. - pub(crate) is_top_level: bool, +#[cfg(feature = "rustc")] +use rustc_data_structures::stack::ensure_sufficient_stack; +#[cfg(not(feature = "rustc"))] +pub fn ensure_sufficient_stack<R>(f: impl FnOnce() -> R) -> R { + f() } -impl<'a, 'p, 'tcx> PatCtxt<'a, 'p, 'tcx> { - /// A `PatCtxt` when code other than `is_useful` needs one. - pub(crate) fn new_dummy(cx: &'a MatchCheckCtxt<'p, 'tcx>, ty: Ty<'tcx>) -> Self { - PatCtxt { cx, ty, is_top_level: false } - } +/// Context that provides information local to a place under investigation. +#[derive(derivative::Derivative)] +#[derivative(Debug(bound = ""), Clone(bound = ""), Copy(bound = ""))] +pub(crate) struct PlaceCtxt<'a, 'p, Cx: TypeCx> { + #[derivative(Debug = "ignore")] + pub(crate) mcx: MatchCtxt<'a, 'p, Cx>, + /// Type of the place under investigation. + pub(crate) ty: Cx::Ty, + /// Whether the place is the original scrutinee place, as opposed to a subplace of it. + pub(crate) is_scrutinee: bool, } -impl<'a, 'p, 'tcx> fmt::Debug for PatCtxt<'a, 'p, 'tcx> { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - f.debug_struct("PatCtxt").field("ty", &self.ty).finish() +impl<'a, 'p, Cx: TypeCx> PlaceCtxt<'a, 'p, Cx> { + /// A `PlaceCtxt` when code other than `is_useful` needs one. + #[cfg_attr(not(feature = "rustc"), allow(dead_code))] + pub(crate) fn new_dummy(mcx: MatchCtxt<'a, 'p, Cx>, ty: Cx::Ty) -> Self { + PlaceCtxt { mcx, ty, is_scrutinee: false } + } + + pub(crate) fn ctor_arity(&self, ctor: &Constructor<Cx>) -> usize { + self.mcx.tycx.ctor_arity(ctor, self.ty) + } + pub(crate) fn ctor_sub_tys(&self, ctor: &Constructor<Cx>) -> &[Cx::Ty] { + self.mcx.tycx.ctor_sub_tys(ctor, self.ty) + } + pub(crate) fn ctors_for_ty(&self) -> ConstructorSet<Cx> { + self.mcx.tycx.ctors_for_ty(self.ty) } } @@ -595,7 +764,7 @@ impl<'a, 'p, 'tcx> fmt::Debug for PatCtxt<'a, 'p, 'tcx> { /// - in the matrix, track whether a given place (aka column) is known to contain a valid value or /// not. #[derive(Debug, Copy, Clone, PartialEq, Eq)] -enum ValidityConstraint { +pub enum ValidityConstraint { ValidOnly, MaybeInvalid, /// Option for backwards compatibility: the place is not known to be valid but we allow omitting @@ -604,7 +773,7 @@ enum ValidityConstraint { } impl ValidityConstraint { - fn from_bool(is_valid_only: bool) -> Self { + pub fn from_bool(is_valid_only: bool) -> Self { if is_valid_only { ValidOnly } else { MaybeInvalid } } @@ -629,12 +798,9 @@ impl ValidityConstraint { /// /// Pending further opsem decisions, the current behavior is: validity is preserved, except /// inside `&` and union fields where validity is reset to `MaybeInvalid`. - fn specialize<'tcx>(self, pcx: &PatCtxt<'_, '_, 'tcx>, ctor: &Constructor<'tcx>) -> Self { + fn specialize<Cx: TypeCx>(self, ctor: &Constructor<Cx>) -> Self { // We preserve validity except when we go inside a reference or a union field. - if matches!(ctor, Constructor::Single) - && (matches!(pcx.ty.kind(), ty::Ref(..)) - || matches!(pcx.ty.kind(), ty::Adt(def, ..) if def.is_union())) - { + if matches!(ctor, Constructor::Ref | Constructor::UnionField) { // Validity of `x: &T` does not imply validity of `*x: T`. MaybeInvalid } else { @@ -654,15 +820,24 @@ impl fmt::Display for ValidityConstraint { } /// Represents a pattern-tuple under investigation. -#[derive(Clone)] -struct PatStack<'p, 'tcx> { +// The three lifetimes are: +// - 'a allocated by us +// - 'p coming from the input +// - Cx global compilation context +#[derive(derivative::Derivative)] +#[derivative(Clone(bound = ""))] +struct PatStack<'a, 'p, Cx: TypeCx> { // Rows of len 1 are very common, which is why `SmallVec[_; 2]` works well. - pats: SmallVec<[&'p DeconstructedPat<'p, 'tcx>; 2]>, + pats: SmallVec<[&'a DeconstructedPat<'p, Cx>; 2]>, + /// Sometimes we know that as far as this row is concerned, the current case is already handled + /// by a different, more general, case. When the case is irrelevant for all rows this allows us + /// to skip a case entirely. This is purely an optimization. See at the top for details. + relevant: bool, } -impl<'p, 'tcx> PatStack<'p, 'tcx> { - fn from_pattern(pat: &'p DeconstructedPat<'p, 'tcx>) -> Self { - PatStack { pats: smallvec![pat] } +impl<'a, 'p, Cx: TypeCx> PatStack<'a, 'p, Cx> { + fn from_pattern(pat: &'a DeconstructedPat<'p, Cx>) -> Self { + PatStack { pats: smallvec![pat], relevant: true } } fn is_empty(&self) -> bool { @@ -673,17 +848,17 @@ impl<'p, 'tcx> PatStack<'p, 'tcx> { self.pats.len() } - fn head(&self) -> &'p DeconstructedPat<'p, 'tcx> { + fn head(&self) -> &'a DeconstructedPat<'p, Cx> { self.pats[0] } - fn iter(&self) -> impl Iterator<Item = &DeconstructedPat<'p, 'tcx>> { + fn iter<'b>(&'b self) -> impl Iterator<Item = &'a DeconstructedPat<'p, Cx>> + Captures<'b> { self.pats.iter().copied() } // 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> { + fn expand_or_pat<'b>(&'b self) -> impl Iterator<Item = PatStack<'a, 'p, Cx>> + Captures<'b> { self.head().flatten_or_pat().into_iter().map(move |pat| { let mut new = self.clone(); new.pats[0] = pat; @@ -695,18 +870,23 @@ impl<'p, 'tcx> PatStack<'p, 'tcx> { /// Only call if `ctor.is_covered_by(self.head().ctor())` is true. fn pop_head_constructor( &self, - pcx: &PatCtxt<'_, 'p, 'tcx>, - ctor: &Constructor<'tcx>, - ) -> PatStack<'p, 'tcx> { + pcx: &PlaceCtxt<'a, 'p, Cx>, + ctor: &Constructor<Cx>, + ctor_is_relevant: bool, + ) -> PatStack<'a, 'p, Cx> { // We pop the head pattern and push the new fields extracted from the arguments of // `self.head()`. let mut new_pats = self.head().specialize(pcx, ctor); new_pats.extend_from_slice(&self.pats[1..]); - PatStack { pats: new_pats } + // `ctor` is relevant for this row if it is the actual constructor of this row, or if the + // row has a wildcard and `ctor` is relevant for wildcards. + let ctor_is_relevant = + !matches!(self.head().ctor(), Constructor::Wildcard) || ctor_is_relevant; + PatStack { pats: new_pats, relevant: self.relevant && ctor_is_relevant } } } -impl<'p, 'tcx> fmt::Debug for PatStack<'p, 'tcx> { +impl<'a, 'p, Cx: TypeCx> fmt::Debug for PatStack<'a, 'p, Cx> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { // We pretty-print similarly to the `Debug` impl of `Matrix`. write!(f, "+")?; @@ -719,9 +899,9 @@ impl<'p, 'tcx> fmt::Debug for PatStack<'p, 'tcx> { /// A row of the matrix. #[derive(Clone)] -struct MatrixRow<'p, 'tcx> { +struct MatrixRow<'a, 'p, Cx: TypeCx> { // The patterns in the row. - pats: PatStack<'p, 'tcx>, + pats: PatStack<'a, 'p, Cx>, /// 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 @@ -734,7 +914,7 @@ struct MatrixRow<'p, 'tcx> { useful: bool, } -impl<'p, 'tcx> MatrixRow<'p, 'tcx> { +impl<'a, 'p, Cx: TypeCx> MatrixRow<'a, 'p, Cx> { fn is_empty(&self) -> bool { self.pats.is_empty() } @@ -743,17 +923,17 @@ impl<'p, 'tcx> MatrixRow<'p, 'tcx> { self.pats.len() } - fn head(&self) -> &'p DeconstructedPat<'p, 'tcx> { + fn head(&self) -> &'a DeconstructedPat<'p, Cx> { self.pats.head() } - fn iter(&self) -> impl Iterator<Item = &DeconstructedPat<'p, 'tcx>> { + fn iter<'b>(&'b self) -> impl Iterator<Item = &'a DeconstructedPat<'p, Cx>> + Captures<'b> { 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> { + fn expand_or_pat<'b>(&'b self) -> impl Iterator<Item = MatrixRow<'a, 'p, Cx>> + Captures<'b> { self.pats.expand_or_pat().map(|patstack| MatrixRow { pats: patstack, parent_row: self.parent_row, @@ -766,12 +946,13 @@ impl<'p, 'tcx> MatrixRow<'p, 'tcx> { /// Only call if `ctor.is_covered_by(self.head().ctor())` is true. fn pop_head_constructor( &self, - pcx: &PatCtxt<'_, 'p, 'tcx>, - ctor: &Constructor<'tcx>, + pcx: &PlaceCtxt<'a, 'p, Cx>, + ctor: &Constructor<Cx>, + ctor_is_relevant: bool, parent_row: usize, - ) -> MatrixRow<'p, 'tcx> { + ) -> MatrixRow<'a, 'p, Cx> { MatrixRow { - pats: self.pats.pop_head_constructor(pcx, ctor), + pats: self.pats.pop_head_constructor(pcx, ctor, ctor_is_relevant), parent_row, is_under_guard: self.is_under_guard, useful: false, @@ -779,7 +960,7 @@ impl<'p, 'tcx> MatrixRow<'p, 'tcx> { } } -impl<'p, 'tcx> fmt::Debug for MatrixRow<'p, 'tcx> { +impl<'a, 'p, Cx: TypeCx> fmt::Debug for MatrixRow<'a, 'p, Cx> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { self.pats.fmt(f) } @@ -796,22 +977,22 @@ impl<'p, 'tcx> fmt::Debug for MatrixRow<'p, 'tcx> { /// 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> { +struct Matrix<'a, 'p, Cx: TypeCx> { /// Vector of rows. The rows must form a rectangular 2D array. Moreover, all the patterns of /// each column must have the same type. Each column corresponds to a place within the /// scrutinee. - rows: Vec<MatrixRow<'p, 'tcx>>, + rows: Vec<MatrixRow<'a, 'p, Cx>>, /// 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>, + wildcard_row: PatStack<'a, 'p, Cx>, /// Track for each column/place whether it contains a known valid value. place_validity: SmallVec<[ValidityConstraint; 2]>, } -impl<'p, 'tcx> Matrix<'p, 'tcx> { +impl<'a, 'p, Cx: TypeCx> Matrix<'a, 'p, Cx> { /// Pushes a new row to the matrix. If the row starts with an or-pattern, this recursively /// expands it. Internal method, prefer [`Matrix::new`]. - fn expand_and_push(&mut self, row: MatrixRow<'p, 'tcx>) { + fn expand_and_push(&mut self, row: MatrixRow<'a, 'p, Cx>) { if !row.is_empty() && row.head().is_or_pat() { // Expand nested or-patterns. for new_row in row.expand_or_pat() { @@ -823,16 +1004,13 @@ impl<'p, 'tcx> Matrix<'p, 'tcx> { } /// Build a new matrix from an iterator of `MatchArm`s. - fn new<'a>( - cx: &MatchCheckCtxt<'p, 'tcx>, - arms: &[MatchArm<'p, 'tcx>], - scrut_ty: Ty<'tcx>, + fn new( + wildcard_arena: &'a TypedArena<DeconstructedPat<'p, Cx>>, + arms: &'a [MatchArm<'p, Cx>], + scrut_ty: Cx::Ty, scrut_validity: ValidityConstraint, - ) -> Self - where - 'p: 'a, - { - let wild_pattern = cx.pattern_arena.alloc(DeconstructedPat::wildcard(scrut_ty, DUMMY_SP)); + ) -> Self { + let wild_pattern = wildcard_arena.alloc(DeconstructedPat::wildcard(scrut_ty)); let wildcard_row = PatStack::from_pattern(wild_pattern); let mut matrix = Matrix { rows: Vec::with_capacity(arms.len()), @@ -851,58 +1029,48 @@ impl<'p, 'tcx> Matrix<'p, 'tcx> { matrix } - fn head_ty(&self) -> Option<Ty<'tcx>> { + fn head_ty(&self, mcx: MatchCtxt<'a, 'p, Cx>) -> Option<Cx::Ty> { 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) + let ty = self.wildcard_row.head().ty(); + // FIXME(Nadrieril): `Cx` should only give us revealed types. + Some(mcx.tycx.reveal_opaque_ty(ty)) } fn column_count(&self) -> usize { self.wildcard_row.len() } - fn rows<'a>( - &'a self, - ) -> impl Iterator<Item = &'a MatrixRow<'p, 'tcx>> + Clone + DoubleEndedIterator + ExactSizeIterator + fn rows<'b>( + &'b self, + ) -> impl Iterator<Item = &'b MatrixRow<'a, 'p, Cx>> + Clone + DoubleEndedIterator + ExactSizeIterator { self.rows.iter() } - fn rows_mut<'a>( - &'a mut self, - ) -> impl Iterator<Item = &'a mut MatrixRow<'p, 'tcx>> + DoubleEndedIterator + ExactSizeIterator + fn rows_mut<'b>( + &'b mut self, + ) -> impl Iterator<Item = &'b mut MatrixRow<'a, 'p, Cx>> + 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> { + fn heads<'b>( + &'b self, + ) -> impl Iterator<Item = &'b DeconstructedPat<'p, Cx>> + Clone + Captures<'a> { self.rows().map(|r| r.head()) } /// 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 wildcard_row = self.wildcard_row.pop_head_constructor(pcx, ctor); - let new_validity = self.place_validity[0].specialize(pcx, ctor); + pcx: &PlaceCtxt<'a, 'p, Cx>, + ctor: &Constructor<Cx>, + ctor_is_relevant: bool, + ) -> Matrix<'a, 'p, Cx> { + let wildcard_row = self.wildcard_row.pop_head_constructor(pcx, ctor, ctor_is_relevant); + let new_validity = self.place_validity[0].specialize(ctor); let new_place_validity = std::iter::repeat(new_validity) .take(ctor.arity(pcx)) .chain(self.place_validity[1..].iter().copied()) @@ -911,7 +1079,7 @@ impl<'p, 'tcx> Matrix<'p, 'tcx> { Matrix { rows: Vec::new(), wildcard_row, place_validity: new_place_validity }; 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, i); + let new_row = row.pop_head_constructor(pcx, ctor, ctor_is_relevant, i); matrix.expand_and_push(new_row); } } @@ -929,7 +1097,7 @@ impl<'p, 'tcx> Matrix<'p, 'tcx> { /// + _ + [_, _, tail @ ..] + /// | ✓ | ? | // column validity /// ``` -impl<'p, 'tcx> fmt::Debug for Matrix<'p, 'tcx> { +impl<'a, 'p, Cx: TypeCx> fmt::Debug for Matrix<'a, 'p, Cx> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { write!(f, "\n")?; @@ -1019,18 +1187,19 @@ impl<'p, 'tcx> fmt::Debug for Matrix<'p, 'tcx> { /// 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)] -struct WitnessStack<'tcx>(Vec<WitnessPat<'tcx>>); +#[derive(derivative::Derivative)] +#[derivative(Debug(bound = ""), Clone(bound = ""))] +struct WitnessStack<Cx: TypeCx>(Vec<WitnessPat<Cx>>); -impl<'tcx> WitnessStack<'tcx> { +impl<Cx: TypeCx> WitnessStack<Cx> { /// Asserts that the witness contains a single pattern, and returns it. - fn single_pattern(self) -> WitnessPat<'tcx> { + fn single_pattern(self) -> WitnessPat<Cx> { assert_eq!(self.0.len(), 1); self.0.into_iter().next().unwrap() } /// Reverses specialization by the `Missing` constructor by pushing a whole new pattern. - fn push_pattern(&mut self, pat: WitnessPat<'tcx>) { + fn push_pattern(&mut self, pat: WitnessPat<Cx>) { self.0.push(pat); } @@ -1048,7 +1217,7 @@ impl<'tcx> WitnessStack<'tcx> { /// pats: [(false, "foo"), _, true] /// result: [Enum::Variant { a: (false, "foo"), b: _ }, true] /// ``` - fn apply_constructor(&mut self, pcx: &PatCtxt<'_, '_, 'tcx>, ctor: &Constructor<'tcx>) { + fn apply_constructor(&mut self, pcx: &PlaceCtxt<'_, '_, Cx>, ctor: &Constructor<Cx>) { let len = self.0.len(); let arity = ctor.arity(pcx); let fields = self.0.drain((len - arity)..).rev().collect(); @@ -1066,10 +1235,11 @@ impl<'tcx> WitnessStack<'tcx> { /// /// 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)] -struct WitnessMatrix<'tcx>(Vec<WitnessStack<'tcx>>); +#[derive(derivative::Derivative)] +#[derivative(Debug(bound = ""), Clone(bound = ""))] +struct WitnessMatrix<Cx: TypeCx>(Vec<WitnessStack<Cx>>); -impl<'tcx> WitnessMatrix<'tcx> { +impl<Cx: TypeCx> WitnessMatrix<Cx> { /// New matrix with no witnesses. fn empty() -> Self { WitnessMatrix(vec![]) @@ -1084,12 +1254,12 @@ impl<'tcx> WitnessMatrix<'tcx> { self.0.is_empty() } /// Asserts that there is a single column and returns the patterns in it. - fn single_column(self) -> Vec<WitnessPat<'tcx>> { + fn single_column(self) -> Vec<WitnessPat<Cx>> { 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>) { + fn push_pattern(&mut self, pat: WitnessPat<Cx>) { for witness in self.0.iter_mut() { witness.push_pattern(pat.clone()) } @@ -1098,9 +1268,9 @@ impl<'tcx> WitnessMatrix<'tcx> { /// 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>, + pcx: &PlaceCtxt<'_, '_, Cx>, + missing_ctors: &[Constructor<Cx>], + ctor: &Constructor<Cx>, report_individual_missing_ctors: bool, ) { if self.is_empty() { @@ -1109,7 +1279,10 @@ impl<'tcx> WitnessMatrix<'tcx> { 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 { + if missing_ctors.is_empty() { + // Nothing to report. + *self = Self::empty(); + } else if !report_individual_missing_ctors { // Report `_` as missing. let pat = WitnessPat::wild_from_ctor(pcx, Constructor::Wildcard); self.push_pattern(pat); @@ -1160,15 +1333,22 @@ impl<'tcx> WitnessMatrix<'tcx> { /// - unspecialization, where we lift the results from the previous step into results for this step /// (using `apply_constructor` and by updating `row.useful` 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_usefulness<'p, 'tcx>( - cx: &MatchCheckCtxt<'p, 'tcx>, - matrix: &mut Matrix<'p, 'tcx>, +#[instrument(level = "debug", skip(mcx, is_top_level), ret)] +fn compute_exhaustiveness_and_usefulness<'a, 'p, Cx: TypeCx>( + mcx: MatchCtxt<'a, 'p, Cx>, + matrix: &mut Matrix<'a, 'p, Cx>, is_top_level: bool, -) -> WitnessMatrix<'tcx> { +) -> WitnessMatrix<Cx> { debug_assert!(matrix.rows().all(|r| r.len() == matrix.column_count())); - let Some(ty) = matrix.head_ty() else { + if !matrix.wildcard_row.relevant && matrix.rows().all(|r| !r.pats.relevant) { + // Here we know that nothing will contribute further to exhaustiveness or usefulness. This + // is purely an optimization: skipping this check doesn't affect correctness. See the top of + // the file for details. + return WitnessMatrix::empty(); + } + + let Some(ty) = matrix.head_ty(mcx) else { // The base case: there are no columns in the matrix. We are morally pattern-matching on (). // A row is useful iff it has no (unguarded) rows above it. for row in matrix.rows_mut() { @@ -1180,12 +1360,18 @@ fn compute_exhaustiveness_and_usefulness<'p, 'tcx>( return WitnessMatrix::empty(); } } - // No (unguarded) rows, so the match is not exhaustive. We return a new witness. - return WitnessMatrix::unit_witness(); + // No (unguarded) rows, so the match is not exhaustive. We return a new witness unless + // irrelevant. + return if matrix.wildcard_row.relevant { + WitnessMatrix::unit_witness() + } else { + // We choose to not report anything here; see at the top for details. + WitnessMatrix::empty() + }; }; debug!("ty: {ty:?}"); - let pcx = &PatCtxt { cx, ty, is_top_level }; + let pcx = &PlaceCtxt { mcx, ty, is_scrutinee: is_top_level }; // Whether the place/column we are inspecting is known to contain valid data. let place_validity = matrix.place_validity[0]; @@ -1194,7 +1380,7 @@ fn compute_exhaustiveness_and_usefulness<'p, 'tcx>( // Analyze the constructors present in this column. let ctors = matrix.heads().map(|p| p.ctor()); - let ctors_for_ty = &cx.ctors_for_ty(ty); + let ctors_for_ty = pcx.ctors_for_ty(); let is_integers = matches!(ctors_for_ty, ConstructorSet::Integers { .. }); // For diagnostics. let split_set = ctors_for_ty.split(pcx, ctors); let all_missing = split_set.present.is_empty(); @@ -1224,32 +1410,21 @@ fn compute_exhaustiveness_and_usefulness<'p, 'tcx>( 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); + debug!("specialize({:?})", ctor); + // `ctor` is *irrelevant* if there's another constructor in `split_ctors` that matches + // strictly fewer rows. In that case we can sometimes skip it. See the top of the file for + // details. + let ctor_is_relevant = matches!(ctor, Constructor::Missing) || missing_ctors.is_empty(); + let mut spec_matrix = matrix.specialize_constructor(pcx, &ctor, ctor_is_relevant); let mut witnesses = ensure_sufficient_stack(|| { - compute_exhaustiveness_and_usefulness(cx, &mut spec_matrix, false) + compute_exhaustiveness_and_usefulness(mcx, &mut spec_matrix, false) }); - let counts_for_exhaustiveness = match ctor { - Constructor::Missing => !missing_ctors.is_empty(), - // If there are missing constructors we'll report those instead. Since `Missing` matches - // only the wildcard rows, it matches fewer rows than this constructor, and is therefore - // guaranteed to result in the same or more witnesses. So skipping this does not - // jeopardize correctness. - _ => missing_ctors.is_empty(), - }; - if counts_for_exhaustiveness { - // Transform witnesses for `spec_matrix` into witnesses for `matrix`. - witnesses.apply_constructor( - pcx, - &missing_ctors, - &ctor, - report_individual_missing_ctors, - ); - // Accumulate the found witnesses. - ret.extend(witnesses); - } + // Transform witnesses for `spec_matrix` into witnesses for `matrix`. + witnesses.apply_constructor(pcx, &missing_ctors, &ctor, report_individual_missing_ctors); + // Accumulate the found witnesses. + ret.extend(witnesses); // A parent row is useful if any of its children is. for child_row in spec_matrix.rows() { @@ -1270,34 +1445,34 @@ fn compute_exhaustiveness_and_usefulness<'p, 'tcx>( /// Indicates whether or not a given arm is useful. #[derive(Clone, Debug)] -pub enum Usefulness { +pub enum Usefulness<'p, Cx: TypeCx> { /// The arm is useful. This additionally carries a set of or-pattern branches that have been /// found to be redundant despite the overall arm being useful. Used only in the presence of /// or-patterns, otherwise it stays empty. - Useful(Vec<Span>), + Useful(Vec<&'p DeconstructedPat<'p, Cx>>), /// The arm is redundant and can be removed without changing the behavior of the match /// expression. Redundant, } /// The output of checking a match for exhaustiveness and arm usefulness. -pub struct UsefulnessReport<'p, 'tcx> { +pub struct UsefulnessReport<'p, Cx: TypeCx> { /// For each arm of the input, whether that arm is useful after the arms above it. - pub arm_usefulness: Vec<(MatchArm<'p, 'tcx>, Usefulness)>, + pub arm_usefulness: Vec<(MatchArm<'p, Cx>, Usefulness<'p, Cx>)>, /// If the match is exhaustive, this is empty. If not, this contains witnesses for the lack of /// exhaustiveness. - pub non_exhaustiveness_witnesses: Vec<WitnessPat<'tcx>>, + pub non_exhaustiveness_witnesses: Vec<WitnessPat<Cx>>, } /// Computes whether a match is exhaustive and which of its arms are useful. #[instrument(skip(cx, arms), level = "debug")] -pub(crate) fn compute_match_usefulness<'p, 'tcx>( - cx: &MatchCheckCtxt<'p, 'tcx>, - arms: &[MatchArm<'p, 'tcx>], - scrut_ty: Ty<'tcx>, -) -> UsefulnessReport<'p, 'tcx> { - let scrut_validity = ValidityConstraint::from_bool(cx.known_valid_scrutinee); - let mut matrix = Matrix::new(cx, arms, scrut_ty, scrut_validity); +pub fn compute_match_usefulness<'p, Cx: TypeCx>( + cx: MatchCtxt<'_, 'p, Cx>, + arms: &[MatchArm<'p, Cx>], + scrut_ty: Cx::Ty, + scrut_validity: ValidityConstraint, +) -> UsefulnessReport<'p, Cx> { + let mut matrix = Matrix::new(cx.wildcard_arena, arms, scrut_ty, scrut_validity); let non_exhaustiveness_witnesses = compute_exhaustiveness_and_usefulness(cx, &mut matrix, true); let non_exhaustiveness_witnesses: Vec<_> = non_exhaustiveness_witnesses.single_column(); @@ -1308,7 +1483,7 @@ pub(crate) fn compute_match_usefulness<'p, 'tcx>( debug!(?arm); // We warn when a pattern is not useful. let usefulness = if arm.pat.is_useful() { - Usefulness::Useful(arm.pat.redundant_spans()) + Usefulness::Useful(arm.pat.redundant_subpatterns()) } else { Usefulness::Redundant }; |