diff options
Diffstat (limited to 'compiler/rustc_pattern_analysis/src')
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/constructor.rs | 84 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/errors.rs | 12 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/lib.rs | 60 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/lints.rs | 124 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/pat.rs | 140 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/pat_column.rs | 90 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/rustc.rs | 255 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/usefulness.rs | 236 |
8 files changed, 551 insertions, 450 deletions
diff --git a/compiler/rustc_pattern_analysis/src/constructor.rs b/compiler/rustc_pattern_analysis/src/constructor.rs index eba71a23435..24824682b74 100644 --- a/compiler/rustc_pattern_analysis/src/constructor.rs +++ b/compiler/rustc_pattern_analysis/src/constructor.rs @@ -162,7 +162,6 @@ use self::MaybeInfiniteInt::*; use self::SliceKind::*; use crate::index; -use crate::usefulness::PlaceCtxt; use crate::TypeCx; /// Whether we have seen a constructor in the column or not. @@ -391,12 +390,18 @@ impl IntRange { /// first. impl fmt::Debug for IntRange { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - if let Finite(lo) = self.lo { + if self.is_singleton() { + // Only finite ranges can be singletons. + let Finite(lo) = self.lo else { unreachable!() }; write!(f, "{lo}")?; - } - write!(f, "{}", RangeEnd::Excluded)?; - if let Finite(hi) = self.hi { - write!(f, "{hi}")?; + } else { + if let Finite(lo) = self.lo { + write!(f, "{lo}")?; + } + write!(f, "{}", RangeEnd::Excluded)?; + if let Finite(hi) = self.hi { + write!(f, "{hi}")?; + } } Ok(()) } @@ -642,8 +647,7 @@ 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(derivative::Derivative)] -#[derivative(Debug(bound = ""), Clone(bound = ""), PartialEq(bound = ""))] +#[derive(Debug)] pub enum Constructor<Cx: TypeCx> { /// Tuples and structs. Struct, @@ -686,6 +690,33 @@ pub enum Constructor<Cx: TypeCx> { Missing, } +impl<Cx: TypeCx> Clone for Constructor<Cx> { + fn clone(&self) -> Self { + match self { + Constructor::Struct => Constructor::Struct, + Constructor::Variant(idx) => Constructor::Variant(idx.clone()), + Constructor::Ref => Constructor::Ref, + Constructor::Slice(slice) => Constructor::Slice(slice.clone()), + Constructor::UnionField => Constructor::UnionField, + Constructor::Bool(b) => Constructor::Bool(b.clone()), + Constructor::IntRange(range) => Constructor::IntRange(range.clone()), + Constructor::F32Range(lo, hi, end) => { + Constructor::F32Range(lo.clone(), hi.clone(), end.clone()) + } + Constructor::F64Range(lo, hi, end) => { + Constructor::F64Range(lo.clone(), hi.clone(), end.clone()) + } + Constructor::Str(value) => Constructor::Str(value.clone()), + Constructor::Opaque(inner) => Constructor::Opaque(inner.clone()), + Constructor::Or => Constructor::Or, + Constructor::Wildcard => Constructor::Wildcard, + Constructor::NonExhaustive => Constructor::NonExhaustive, + Constructor::Hidden => Constructor::Hidden, + Constructor::Missing => Constructor::Missing, + } + } +} + impl<Cx: TypeCx> Constructor<Cx> { pub(crate) fn is_non_exhaustive(&self) -> bool { matches!(self, NonExhaustive) @@ -718,8 +749,8 @@ impl<Cx: TypeCx> Constructor<Cx> { /// The number of fields for this constructor. This must be kept in sync with /// `Fields::wildcards`. - pub(crate) fn arity(&self, pcx: &PlaceCtxt<'_, Cx>) -> usize { - pcx.ctor_arity(self) + pub(crate) fn arity(&self, cx: &Cx, ty: &Cx::Ty) -> usize { + cx.ctor_arity(self, ty) } /// Returns whether `self` is covered by `other`, i.e. whether `self` is a subset of `other`. @@ -727,12 +758,13 @@ impl<Cx: TypeCx> Constructor<Cx> { /// this checks for inclusion. // We inline because this has a single call site in `Matrix::specialize_constructor`. #[inline] - pub(crate) fn is_covered_by(&self, pcx: &PlaceCtxt<'_, Cx>, other: &Self) -> bool { - match (self, other) { - (Wildcard, _) => pcx - .mcx - .tycx - .bug(format_args!("Constructor splitting should not have returned `Wildcard`")), + pub(crate) fn is_covered_by(&self, cx: &Cx, other: &Self) -> Result<bool, Cx::Error> { + Ok(match (self, other) { + (Wildcard, _) => { + return Err(cx.bug(format_args!( + "Constructor splitting should not have returned `Wildcard`" + ))); + } // Wildcards cover anything (_, Wildcard) => true, // Only a wildcard pattern can match these special constructors. @@ -773,10 +805,12 @@ impl<Cx: TypeCx> Constructor<Cx> { (Opaque(self_id), Opaque(other_id)) => self_id == other_id, (Opaque(..), _) | (_, Opaque(..)) => false, - _ => pcx.mcx.tycx.bug(format_args!( - "trying to compare incompatible constructors {self:?} and {other:?}" - )), - } + _ => { + return Err(cx.bug(format_args!( + "trying to compare incompatible constructors {self:?} and {other:?}" + ))); + } + }) } } @@ -850,10 +884,10 @@ pub enum ConstructorSet<Cx: TypeCx> { /// 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<Cx: TypeCx> { - pub(crate) present: SmallVec<[Constructor<Cx>; 1]>, - pub(crate) missing: Vec<Constructor<Cx>>, - pub(crate) missing_empty: Vec<Constructor<Cx>>, +pub struct SplitConstructorSet<Cx: TypeCx> { + pub present: SmallVec<[Constructor<Cx>; 1]>, + pub missing: Vec<Constructor<Cx>>, + pub missing_empty: Vec<Constructor<Cx>>, } impl<Cx: TypeCx> ConstructorSet<Cx> { @@ -862,7 +896,7 @@ impl<Cx: TypeCx> ConstructorSet<Cx> { /// or slices. This can get subtle; see [`SplitConstructorSet`] for details of this operation /// and its invariants. #[instrument(level = "debug", skip(self, ctors), ret)] - pub(crate) fn split<'a>( + pub fn split<'a>( &self, ctors: impl Iterator<Item = &'a Constructor<Cx>> + Clone, ) -> SplitConstructorSet<Cx> diff --git a/compiler/rustc_pattern_analysis/src/errors.rs b/compiler/rustc_pattern_analysis/src/errors.rs index 88770b0c43b..2dffdc9846c 100644 --- a/compiler/rustc_pattern_analysis/src/errors.rs +++ b/compiler/rustc_pattern_analysis/src/errors.rs @@ -1,4 +1,4 @@ -use rustc_errors::{AddToDiagnostic, Diagnostic, SubdiagnosticMessage}; +use rustc_errors::{AddToDiagnostic, Diagnostic, SubdiagnosticMessageOp}; use rustc_macros::{LintDiagnostic, Subdiagnostic}; use rustc_middle::thir::Pat; use rustc_middle::ty::Ty; @@ -23,7 +23,10 @@ impl<'tcx> Uncovered<'tcx> { span: Span, cx: &RustcMatchCheckCtxt<'p, 'tcx>, witnesses: Vec<WitnessPat<'p, 'tcx>>, - ) -> Self { + ) -> Self + where + 'tcx: 'p, + { let witness_1 = cx.hoist_witness_pat(witnesses.get(0).unwrap()); Self { span, @@ -59,10 +62,7 @@ pub struct Overlap<'tcx> { } impl<'tcx> AddToDiagnostic for Overlap<'tcx> { - fn add_to_diagnostic_with<F>(self, diag: &mut Diagnostic, _: F) - where - F: Fn(&mut Diagnostic, SubdiagnosticMessage) -> SubdiagnosticMessage, - { + fn add_to_diagnostic_with<F: SubdiagnosticMessageOp>(self, diag: &mut Diagnostic, _: F) { let Overlap { span, range } = self; // FIXME(mejrs) unfortunately `#[derive(LintDiagnostic)]` diff --git a/compiler/rustc_pattern_analysis/src/lib.rs b/compiler/rustc_pattern_analysis/src/lib.rs index 21fa8e68d82..164dc36b679 100644 --- a/compiler/rustc_pattern_analysis/src/lib.rs +++ b/compiler/rustc_pattern_analysis/src/lib.rs @@ -1,11 +1,15 @@ //! Analysis of patterns, notably match exhaustiveness checking. +#![allow(rustc::untranslatable_diagnostic)] +#![allow(rustc::diagnostic_outside_of_impl)] + pub mod constructor; #[cfg(feature = "rustc")] pub mod errors; #[cfg(feature = "rustc")] pub(crate) mod lints; pub mod pat; +pub mod pat_column; #[cfg(feature = "rustc")] pub mod rustc; pub mod usefulness; @@ -67,8 +71,9 @@ use rustc_span::ErrorGuaranteed; use crate::constructor::{Constructor, ConstructorSet, IntRange}; #[cfg(feature = "rustc")] -use crate::lints::{lint_nonexhaustive_missing_variants, PatternColumn}; +use crate::lints::lint_nonexhaustive_missing_variants; use crate::pat::DeconstructedPat; +use crate::pat_column::PatternColumn; #[cfg(feature = "rustc")] use crate::rustc::RustcMatchCheckCtxt; #[cfg(feature = "rustc")] @@ -82,7 +87,7 @@ impl<'a, T: ?Sized> Captures<'a> for T {} /// 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 + type Ty: Clone + fmt::Debug; /// Errors that can abort analysis. type Error: fmt::Debug; /// The index of an enum variant. @@ -95,55 +100,62 @@ pub trait TypeCx: Sized + fmt::Debug { type PatData: Clone; fn is_exhaustive_patterns_feature_on(&self) -> bool; + fn is_min_exhaustive_patterns_feature_on(&self) -> bool; /// The number of fields for this constructor. - fn ctor_arity(&self, ctor: &Constructor<Self>, ty: Self::Ty) -> usize; + 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]; + fn ctor_sub_tys<'a>( + &'a self, + ctor: &'a Constructor<Self>, + ty: &'a Self::Ty, + ) -> impl Iterator<Item = Self::Ty> + ExactSizeIterator + Captures<'a>; /// The set of all the constructors for `ty`. /// /// This must follow the invariants of `ConstructorSet` - fn ctors_for_ty(&self, ty: Self::Ty) -> Result<ConstructorSet<Self>, Self::Error>; + fn ctors_for_ty(&self, ty: &Self::Ty) -> Result<ConstructorSet<Self>, Self::Error>; - /// Best-effort `Debug` implementation. - fn debug_pat(f: &mut fmt::Formatter<'_>, pat: &DeconstructedPat<'_, Self>) -> fmt::Result; + /// Write the name of the variant represented by `pat`. Used for the best-effort `Debug` impl of + /// `DeconstructedPat`. Only invoqued when `pat.ctor()` is `Struct | Variant(_) | UnionField`. + fn write_variant_name( + f: &mut fmt::Formatter<'_>, + pat: &crate::pat::DeconstructedPat<Self>, + ) -> fmt::Result; /// Raise a bug. - fn bug(&self, fmt: fmt::Arguments<'_>) -> !; + fn bug(&self, fmt: fmt::Arguments<'_>) -> Self::Error; /// Lint that the range `pat` overlapped with all the ranges in `overlaps_with`, where the range /// they overlapped over is `overlaps_on`. We only detect singleton overlaps. /// The default implementation does nothing. fn lint_overlapping_range_endpoints( &self, - _pat: &DeconstructedPat<'_, Self>, + _pat: &DeconstructedPat<Self>, _overlaps_on: IntRange, - _overlaps_with: &[&DeconstructedPat<'_, Self>], + _overlaps_with: &[&DeconstructedPat<Self>], ) { } } -/// Context that provides information global to a match. -#[derive(derivative::Derivative)] -#[derivative(Clone(bound = ""), Copy(bound = ""))] -pub struct MatchCtxt<'a, Cx: TypeCx> { - /// The context for type information. - pub tycx: &'a Cx, -} - /// The arm of a match expression. #[derive(Debug)] -#[derive(derivative::Derivative)] -#[derivative(Clone(bound = ""), Copy(bound = ""))] pub struct MatchArm<'p, Cx: TypeCx> { - pub pat: &'p DeconstructedPat<'p, Cx>, + pub pat: &'p DeconstructedPat<Cx>, pub has_guard: bool, pub arm_data: Cx::ArmData, } +impl<'p, Cx: TypeCx> Clone for MatchArm<'p, Cx> { + fn clone(&self) -> Self { + Self { pat: self.pat, has_guard: self.has_guard, arm_data: self.arm_data } + } +} + +impl<'p, Cx: TypeCx> Copy for MatchArm<'p, Cx> {} + /// 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")] @@ -154,15 +166,13 @@ pub fn analyze_match<'p, 'tcx>( ) -> Result<rustc::UsefulnessReport<'p, 'tcx>, ErrorGuaranteed> { let scrut_ty = tycx.reveal_opaque_ty(scrut_ty); let scrut_validity = ValidityConstraint::from_bool(tycx.known_valid_scrutinee); - let cx = MatchCtxt { tycx }; - - let report = compute_match_usefulness(cx, arms, scrut_ty, scrut_validity)?; + let report = compute_match_usefulness(tycx, arms, scrut_ty, scrut_validity)?; // 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 tycx.refutable && report.non_exhaustiveness_witnesses.is_empty() { let pat_column = PatternColumn::new(arms); - lint_nonexhaustive_missing_variants(cx, arms, &pat_column, scrut_ty)?; + lint_nonexhaustive_missing_variants(tycx, arms, &pat_column, scrut_ty)?; } Ok(report) diff --git a/compiler/rustc_pattern_analysis/src/lints.rs b/compiler/rustc_pattern_analysis/src/lints.rs index d9dbd8250ef..30e775733de 100644 --- a/compiler/rustc_pattern_analysis/src/lints.rs +++ b/compiler/rustc_pattern_analysis/src/lints.rs @@ -1,109 +1,24 @@ use rustc_session::lint::builtin::NON_EXHAUSTIVE_OMITTED_PATTERNS; use rustc_span::ErrorGuaranteed; +use crate::constructor::Constructor; use crate::errors::{NonExhaustiveOmittedPattern, NonExhaustiveOmittedPatternLintOnArm, Uncovered}; -use crate::pat::PatOrWild; -use crate::rustc::{ - Constructor, DeconstructedPat, MatchArm, MatchCtxt, PlaceCtxt, RevealedTy, RustcMatchCheckCtxt, - SplitConstructorSet, WitnessPat, -}; - -/// A column of patterns in the matrix, where a column is the intuitive notion of "subpatterns that -/// inspect the same subvalue/place". -/// This is used to traverse patterns column-by-column for lints. Despite similarities with the -/// algorithm in [`crate::usefulness`], this does a different traversal. Notably this is linear in -/// the depth of patterns, whereas `compute_exhaustiveness_and_usefulness` is worst-case exponential -/// (exhaustiveness is NP-complete). The core difference is that we treat sub-columns separately. -/// -/// This must not contain an or-pattern. `expand_and_push` takes care to expand them. -/// -/// This is not used in the usefulness algorithm; only in lints. -#[derive(Debug)] -pub(crate) struct PatternColumn<'p, 'tcx> { - patterns: Vec<&'p DeconstructedPat<'p, 'tcx>>, -} - -impl<'p, 'tcx> PatternColumn<'p, 'tcx> { - pub(crate) fn new(arms: &[MatchArm<'p, 'tcx>]) -> Self { - let patterns = Vec::with_capacity(arms.len()); - let mut column = PatternColumn { patterns }; - for arm in arms { - column.expand_and_push(PatOrWild::Pat(arm.pat)); - } - column - } - /// Pushes a pattern onto the column, expanding any or-patterns into its subpatterns. - /// Internal method, prefer [`PatternColumn::new`]. - fn expand_and_push(&mut self, pat: PatOrWild<'p, RustcMatchCheckCtxt<'p, 'tcx>>) { - // We flatten or-patterns and skip algorithm-generated wildcards. - if pat.is_or_pat() { - self.patterns.extend( - pat.flatten_or_pat().into_iter().filter_map(|pat_or_wild| pat_or_wild.as_pat()), - ) - } else if let Some(pat) = pat.as_pat() { - self.patterns.push(pat) - } - } - - fn head_ty(&self) -> Option<RevealedTy<'tcx>> { - self.patterns.first().map(|pat| pat.ty()) - } - - /// Do constructor splitting on the constructors of the column. - fn analyze_ctors( - &self, - pcx: &PlaceCtxt<'_, 'p, 'tcx>, - ) -> Result<SplitConstructorSet<'p, 'tcx>, ErrorGuaranteed> { - let column_ctors = self.patterns.iter().map(|p| p.ctor()); - let ctors_for_ty = &pcx.ctors_for_ty()?; - Ok(ctors_for_ty.split(column_ctors)) - } - - /// Does specialization: given a constructor, this takes the patterns from the column that match - /// the constructor, and outputs their fields. - /// This returns one column per field of the constructor. 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: &PlaceCtxt<'_, 'p, 'tcx>, - ctor: &Constructor<'p, 'tcx>, - ) -> Vec<PatternColumn<'p, 'tcx>> { - let arity = ctor.arity(pcx); - if arity == 0 { - return Vec::new(); - } - - // We specialize the column by `ctor`. This gives us `arity`-many columns of patterns. These - // columns may have different lengths in the presence of or-patterns (this is why we can't - // reuse `Matrix`). - let mut specialized_columns: Vec<_> = - (0..arity).map(|_| Self { patterns: Vec::new() }).collect(); - let relevant_patterns = - self.patterns.iter().filter(|pat| ctor.is_covered_by(pcx, pat.ctor())); - for pat in relevant_patterns { - let specialized = pat.specialize(ctor, arity); - for (subpat, column) in specialized.into_iter().zip(&mut specialized_columns) { - column.expand_and_push(subpat); - } - } - specialized_columns - } -} +use crate::pat_column::PatternColumn; +use crate::rustc::{RevealedTy, RustcMatchCheckCtxt, WitnessPat}; +use crate::MatchArm; /// 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<'a, 'p, 'tcx>( - cx: MatchCtxt<'a, 'p, 'tcx>, - column: &PatternColumn<'p, 'tcx>, +fn collect_nonexhaustive_missing_variants<'p, 'tcx>( + cx: &RustcMatchCheckCtxt<'p, 'tcx>, + column: &PatternColumn<'p, RustcMatchCheckCtxt<'p, 'tcx>>, ) -> Result<Vec<WitnessPat<'p, 'tcx>>, ErrorGuaranteed> { - let Some(ty) = column.head_ty() else { + let Some(&ty) = column.head_ty() else { return Ok(Vec::new()); }; - let pcx = &PlaceCtxt::new_dummy(cx, ty); - let set = column.analyze_ctors(pcx)?; + let set = column.analyze_ctors(cx, &ty)?; if set.present.is_empty() { // We can't consistently handle the case where no constructors are present (since this would // require digging deep through any type in case there's a non_exhaustive enum somewhere), @@ -112,20 +27,20 @@ fn collect_nonexhaustive_missing_variants<'a, 'p, 'tcx>( } let mut witnesses = Vec::new(); - if cx.tycx.is_foreign_non_exhaustive_enum(ty) { + if cx.is_foreign_non_exhaustive_enum(ty) { witnesses.extend( set.missing .into_iter() // This will list missing visible variants. .filter(|c| !matches!(c, Constructor::Hidden | Constructor::NonExhaustive)) - .map(|missing_ctor| WitnessPat::wild_from_ctor(pcx, missing_ctor)), + .map(|missing_ctor| WitnessPat::wild_from_ctor(cx, missing_ctor, ty)), ) } // Recurse into the fields. for ctor in set.present { - let specialized_columns = column.specialize(pcx, &ctor); - let wild_pat = WitnessPat::wild_from_ctor(pcx, ctor); + let specialized_columns = column.specialize(cx, &ty, &ctor); + let wild_pat = WitnessPat::wild_from_ctor(cx, ctor, ty); for (i, col_i) in specialized_columns.iter().enumerate() { // Compute witnesses for each column. let wits_for_col_i = collect_nonexhaustive_missing_variants(cx, col_i)?; @@ -141,24 +56,23 @@ fn collect_nonexhaustive_missing_variants<'a, 'p, 'tcx>( Ok(witnesses) } -pub(crate) fn lint_nonexhaustive_missing_variants<'a, 'p, 'tcx>( - cx: MatchCtxt<'a, 'p, 'tcx>, - arms: &[MatchArm<'p, 'tcx>], - pat_column: &PatternColumn<'p, 'tcx>, +pub(crate) fn lint_nonexhaustive_missing_variants<'p, 'tcx>( + rcx: &RustcMatchCheckCtxt<'p, 'tcx>, + arms: &[MatchArm<'p, RustcMatchCheckCtxt<'p, 'tcx>>], + pat_column: &PatternColumn<'p, RustcMatchCheckCtxt<'p, 'tcx>>, scrut_ty: RevealedTy<'tcx>, ) -> Result<(), ErrorGuaranteed> { - let rcx: &RustcMatchCheckCtxt<'_, '_> = cx.tycx; if !matches!( 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)?; + let witnesses = collect_nonexhaustive_missing_variants(rcx, pat_column)?; if !witnesses.is_empty() { // Report that a match of a `non_exhaustive` enum marked with `non_exhaustive_omitted_patterns` // is not exhaustive enough. // // NB: The partner lint for structs lives in `compiler/rustc_hir_analysis/src/check/pat.rs`. - rcx.tcx.emit_spanned_lint( + rcx.tcx.emit_node_span_lint( NON_EXHAUSTIVE_OMITTED_PATTERNS, rcx.match_lint_level, rcx.scrut_span, diff --git a/compiler/rustc_pattern_analysis/src/pat.rs b/compiler/rustc_pattern_analysis/src/pat.rs index 75fe59edf88..9bde23c7bf1 100644 --- a/compiler/rustc_pattern_analysis/src/pat.rs +++ b/compiler/rustc_pattern_analysis/src/pat.rs @@ -6,8 +6,7 @@ use std::fmt; use smallvec::{smallvec, SmallVec}; use crate::constructor::{Constructor, Slice, SliceKind}; -use crate::usefulness::PlaceCtxt; -use crate::{Captures, TypeCx}; +use crate::TypeCx; use self::Constructor::*; @@ -22,9 +21,9 @@ use self::Constructor::*; /// 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, Cx: TypeCx> { +pub struct DeconstructedPat<Cx: TypeCx> { ctor: Constructor<Cx>, - fields: &'p [DeconstructedPat<'p, Cx>], + fields: Vec<DeconstructedPat<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. @@ -33,14 +32,20 @@ pub struct DeconstructedPat<'p, Cx: TypeCx> { useful: Cell<bool>, } -impl<'p, Cx: TypeCx> DeconstructedPat<'p, Cx> { +impl<Cx: TypeCx> DeconstructedPat<Cx> { pub fn wildcard(ty: Cx::Ty) -> Self { - DeconstructedPat { ctor: Wildcard, fields: &[], ty, data: None, useful: Cell::new(false) } + DeconstructedPat { + ctor: Wildcard, + fields: Vec::new(), + ty, + data: None, + useful: Cell::new(false), + } } pub fn new( ctor: Constructor<Cx>, - fields: &'p [DeconstructedPat<'p, Cx>], + fields: Vec<DeconstructedPat<Cx>>, ty: Cx::Ty, data: Cx::PatData, ) -> Self { @@ -54,8 +59,8 @@ impl<'p, Cx: TypeCx> DeconstructedPat<'p, Cx> { pub fn ctor(&self) -> &Constructor<Cx> { &self.ctor } - pub fn ty(&self) -> Cx::Ty { - self.ty + pub fn ty(&self) -> &Cx::Ty { + &self.ty } /// 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. @@ -63,17 +68,17 @@ impl<'p, Cx: TypeCx> DeconstructedPat<'p, Cx> { self.data.as_ref() } - pub fn iter_fields(&self) -> impl Iterator<Item = &'p DeconstructedPat<'p, Cx>> + Captures<'_> { + pub fn iter_fields<'a>(&'a self) -> impl Iterator<Item = &'a DeconstructedPat<Cx>> { 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( - &self, + pub(crate) fn specialize<'a>( + &'a self, other_ctor: &Constructor<Cx>, ctor_arity: usize, - ) -> SmallVec<[PatOrWild<'p, Cx>; 2]> { + ) -> SmallVec<[PatOrWild<'a, Cx>; 2]> { let wildcard_sub_tys = || (0..ctor_arity).map(|_| PatOrWild::Wild).collect(); match (&self.ctor, other_ctor) { // Return a wildcard for each field of `other_ctor`. @@ -140,9 +145,77 @@ impl<'p, Cx: TypeCx> DeconstructedPat<'p, Cx> { } /// This is best effort and not good enough for a `Display` impl. -impl<'p, Cx: TypeCx> fmt::Debug for DeconstructedPat<'p, Cx> { +impl<Cx: TypeCx> fmt::Debug for DeconstructedPat<Cx> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - Cx::debug_pat(f, self) + let pat = self; + let mut first = true; + let mut start_or_continue = |s| { + if first { + first = false; + "" + } else { + s + } + }; + let mut start_or_comma = || start_or_continue(", "); + + match pat.ctor() { + Struct | Variant(_) | UnionField => { + Cx::write_variant_name(f, pat)?; + // Without `cx`, we can't know which field corresponds to which, so we can't + // get the names of the fields. Instead we just display everything as a tuple + // struct, which should be good enough. + write!(f, "(")?; + for p in pat.iter_fields() { + write!(f, "{}", start_or_comma())?; + write!(f, "{p:?}")?; + } + 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, "[")?; + match slice.kind { + SliceKind::FixedLen(_) => { + for p in subpatterns { + write!(f, "{}{:?}", start_or_comma(), p)?; + } + } + SliceKind::VarLen(prefix_len, _) => { + for p in subpatterns.by_ref().take(prefix_len) { + write!(f, "{}{:?}", start_or_comma(), p)?; + } + write!(f, "{}", start_or_comma())?; + write!(f, "..")?; + for p in subpatterns { + write!(f, "{}{:?}", start_or_comma(), p)?; + } + } + } + write!(f, "]") + } + Bool(b) => write!(f, "{b}"), + // Best-effort, will render signed ranges incorrectly + IntRange(range) => write!(f, "{range:?}"), + F32Range(lo, hi, end) => write!(f, "{lo}{end}{hi}"), + F64Range(lo, hi, end) => write!(f, "{lo}{end}{hi}"), + Str(value) => write!(f, "{value:?}"), + Opaque(..) => write!(f, "<constant pattern>"), + Or => { + for pat in pat.iter_fields() { + write!(f, "{}{:?}", start_or_continue(" | "), pat)?; + } + Ok(()) + } + Wildcard | Missing { .. } | NonExhaustive | Hidden => write!(f, "_ : {:?}", pat.ty()), + } } } @@ -150,17 +223,26 @@ impl<'p, Cx: TypeCx> fmt::Debug for DeconstructedPat<'p, Cx> { /// algorithm. Do not use `Wild` to represent a wildcard pattern comping from user input. /// /// This is morally `Option<&'p DeconstructedPat>` where `None` is interpreted as a wildcard. -#[derive(derivative::Derivative)] -#[derivative(Clone(bound = ""), Copy(bound = ""))] pub(crate) enum PatOrWild<'p, Cx: TypeCx> { /// A non-user-provided wildcard, created during specialization. Wild, /// A user-provided pattern. - Pat(&'p DeconstructedPat<'p, Cx>), + Pat(&'p DeconstructedPat<Cx>), } +impl<'p, Cx: TypeCx> Clone for PatOrWild<'p, Cx> { + fn clone(&self) -> Self { + match self { + PatOrWild::Wild => PatOrWild::Wild, + PatOrWild::Pat(pat) => PatOrWild::Pat(pat), + } + } +} + +impl<'p, Cx: TypeCx> Copy for PatOrWild<'p, Cx> {} + impl<'p, Cx: TypeCx> PatOrWild<'p, Cx> { - pub(crate) fn as_pat(&self) -> Option<&'p DeconstructedPat<'p, Cx>> { + pub(crate) fn as_pat(&self) -> Option<&'p DeconstructedPat<Cx>> { match self { PatOrWild::Wild => None, PatOrWild::Pat(pat) => Some(pat), @@ -221,14 +303,19 @@ impl<'p, Cx: TypeCx> fmt::Debug for PatOrWild<'p, Cx> { /// 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(derivative::Derivative)] -#[derivative(Debug(bound = ""), Clone(bound = ""))] +#[derive(Debug)] pub struct WitnessPat<Cx: TypeCx> { ctor: Constructor<Cx>, pub(crate) fields: Vec<WitnessPat<Cx>>, ty: Cx::Ty, } +impl<Cx: TypeCx> Clone for WitnessPat<Cx> { + fn clone(&self) -> Self { + Self { ctor: self.ctor.clone(), fields: self.fields.clone(), ty: self.ty.clone() } + } +} + impl<Cx: TypeCx> WitnessPat<Cx> { pub(crate) fn new(ctor: Constructor<Cx>, fields: Vec<Self>, ty: Cx::Ty) -> Self { Self { ctor, fields, ty } @@ -240,17 +327,16 @@ impl<Cx: TypeCx> WitnessPat<Cx> { /// 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: &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(crate) fn wild_from_ctor(cx: &Cx, ctor: Constructor<Cx>, ty: Cx::Ty) -> Self { + let fields = cx.ctor_sub_tys(&ctor, &ty).map(|ty| Self::wildcard(ty)).collect(); + Self::new(ctor, fields, ty) } pub fn ctor(&self) -> &Constructor<Cx> { &self.ctor } - pub fn ty(&self) -> Cx::Ty { - self.ty + pub fn ty(&self) -> &Cx::Ty { + &self.ty } pub fn iter_fields(&self) -> impl Iterator<Item = &WitnessPat<Cx>> { diff --git a/compiler/rustc_pattern_analysis/src/pat_column.rs b/compiler/rustc_pattern_analysis/src/pat_column.rs new file mode 100644 index 00000000000..ce14fdc364f --- /dev/null +++ b/compiler/rustc_pattern_analysis/src/pat_column.rs @@ -0,0 +1,90 @@ +use crate::constructor::{Constructor, SplitConstructorSet}; +use crate::pat::{DeconstructedPat, PatOrWild}; +use crate::{Captures, MatchArm, TypeCx}; + +/// A column of patterns in a match, where a column is the intuitive notion of "subpatterns that +/// inspect the same subvalue/place". +/// This is used to traverse patterns column-by-column for lints. Despite similarities with the +/// algorithm in [`crate::usefulness`], this does a different traversal. Notably this is linear in +/// the depth of patterns, whereas `compute_exhaustiveness_and_usefulness` is worst-case exponential +/// (exhaustiveness is NP-complete). The core difference is that we treat sub-columns separately. +/// +/// This is not used in the usefulness algorithm; only in lints. +#[derive(Debug)] +pub struct PatternColumn<'p, Cx: TypeCx> { + /// This must not contain an or-pattern. `expand_and_push` takes care to expand them. + patterns: Vec<&'p DeconstructedPat<Cx>>, +} + +impl<'p, Cx: TypeCx> PatternColumn<'p, Cx> { + pub fn new(arms: &[MatchArm<'p, Cx>]) -> Self { + let patterns = Vec::with_capacity(arms.len()); + let mut column = PatternColumn { patterns }; + for arm in arms { + column.expand_and_push(PatOrWild::Pat(arm.pat)); + } + column + } + /// Pushes a pattern onto the column, expanding any or-patterns into its subpatterns. + /// Internal method, prefer [`PatternColumn::new`]. + fn expand_and_push(&mut self, pat: PatOrWild<'p, Cx>) { + // We flatten or-patterns and skip algorithm-generated wildcards. + if pat.is_or_pat() { + self.patterns.extend( + pat.flatten_or_pat().into_iter().filter_map(|pat_or_wild| pat_or_wild.as_pat()), + ) + } else if let Some(pat) = pat.as_pat() { + self.patterns.push(pat) + } + } + + pub fn head_ty(&self) -> Option<&Cx::Ty> { + self.patterns.first().map(|pat| pat.ty()) + } + pub fn iter<'a>(&'a self) -> impl Iterator<Item = &'p DeconstructedPat<Cx>> + Captures<'a> { + self.patterns.iter().copied() + } + + /// Do constructor splitting on the constructors of the column. + pub fn analyze_ctors( + &self, + cx: &Cx, + ty: &Cx::Ty, + ) -> Result<SplitConstructorSet<Cx>, Cx::Error> { + let column_ctors = self.patterns.iter().map(|p| p.ctor()); + let ctors_for_ty = cx.ctors_for_ty(ty)?; + Ok(ctors_for_ty.split(column_ctors)) + } + + /// Does specialization: given a constructor, this takes the patterns from the column that match + /// the constructor, and outputs their fields. + /// This returns one column per field of the constructor. 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. + pub fn specialize( + &self, + cx: &Cx, + ty: &Cx::Ty, + ctor: &Constructor<Cx>, + ) -> Vec<PatternColumn<'p, Cx>> { + let arity = ctor.arity(cx, ty); + if arity == 0 { + return Vec::new(); + } + + // We specialize the column by `ctor`. This gives us `arity`-many columns of patterns. These + // columns may have different lengths in the presence of or-patterns (this is why we can't + // reuse `Matrix`). + let mut specialized_columns: Vec<_> = + (0..arity).map(|_| Self { patterns: Vec::new() }).collect(); + let relevant_patterns = + self.patterns.iter().filter(|pat| ctor.is_covered_by(cx, pat.ctor()).unwrap_or(false)); + for pat in relevant_patterns { + let specialized = pat.specialize(ctor, arity); + for (subpat, column) in specialized.into_iter().zip(&mut specialized_columns) { + column.expand_and_push(subpat); + } + } + specialized_columns + } +} diff --git a/compiler/rustc_pattern_analysis/src/rustc.rs b/compiler/rustc_pattern_analysis/src/rustc.rs index 87e70d68c1b..a8fe0cb6a1d 100644 --- a/compiler/rustc_pattern_analysis/src/rustc.rs +++ b/compiler/rustc_pattern_analysis/src/rustc.rs @@ -1,9 +1,7 @@ -use smallvec::SmallVec; use std::fmt; use std::iter::once; -use rustc_arena::{DroplessArena, TypedArena}; -use rustc_data_structures::captures::Captures; +use rustc_arena::DroplessArena; use rustc_hir::def_id::DefId; use rustc_hir::HirId; use rustc_index::{Idx, IndexVec}; @@ -20,7 +18,7 @@ use rustc_target::abi::{FieldIdx, Integer, VariantIdx, FIRST_VARIANT}; use crate::constructor::{ IntRange, MaybeInfiniteInt, OpaqueId, RangeEnd, Slice, SliceKind, VariantVisibility, }; -use crate::{errors, TypeCx}; +use crate::{errors, Captures, TypeCx}; use crate::constructor::Constructor::*; @@ -28,14 +26,8 @@ use crate::constructor::Constructor::*; 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 DeconstructedPat<'p, 'tcx> = crate::pat::DeconstructedPat<RustcMatchCheckCtxt<'p, 'tcx>>; pub type MatchArm<'p, 'tcx> = crate::MatchArm<'p, RustcMatchCheckCtxt<'p, 'tcx>>; -pub type MatchCtxt<'a, 'p, 'tcx> = crate::MatchCtxt<'a, RustcMatchCheckCtxt<'p, 'tcx>>; -pub(crate) type PlaceCtxt<'a, 'p, 'tcx> = - crate::usefulness::PlaceCtxt<'a, 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>>; @@ -47,11 +39,15 @@ pub type WitnessPat<'p, 'tcx> = crate::pat::WitnessPat<RustcMatchCheckCtxt<'p, ' /// /// Use `.inner()` or deref to get to the `Ty<'tcx>`. #[repr(transparent)] -#[derive(derivative::Derivative)] #[derive(Clone, Copy)] -#[derivative(Debug = "transparent")] pub struct RevealedTy<'tcx>(Ty<'tcx>); +impl<'tcx> fmt::Debug for RevealedTy<'tcx> { + fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result { + self.0.fmt(fmt) + } +} + impl<'tcx> std::ops::Deref for RevealedTy<'tcx> { type Target = Ty<'tcx>; fn deref(&self) -> &Self::Target { @@ -66,7 +62,7 @@ impl<'tcx> RevealedTy<'tcx> { } #[derive(Clone)] -pub struct RustcMatchCheckCtxt<'p, 'tcx> { +pub struct RustcMatchCheckCtxt<'p, 'tcx: 'p> { pub tcx: TyCtxt<'tcx>, pub typeck_results: &'tcx ty::TypeckResults<'tcx>, /// The module in which the match occurs. This is necessary for @@ -76,8 +72,6 @@ pub struct RustcMatchCheckCtxt<'p, 'tcx> { /// outside its module and should not be matchable with an empty match statement. pub module: DefId, pub param_env: ty::ParamEnv<'tcx>, - /// To allocate lowered patterns - pub pattern_arena: &'p TypedArena<DeconstructedPat<'p, 'tcx>>, /// To allocate the result of `self.ctor_sub_tys()` pub dropless_arena: &'p DroplessArena, /// Lint level at the match. @@ -93,13 +87,13 @@ pub struct RustcMatchCheckCtxt<'p, 'tcx> { pub known_valid_scrutinee: bool, } -impl<'p, 'tcx> fmt::Debug for RustcMatchCheckCtxt<'p, 'tcx> { +impl<'p, 'tcx: 'p> 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> { +impl<'p, 'tcx: 'p> RustcMatchCheckCtxt<'p, 'tcx> { /// 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. @@ -182,7 +176,9 @@ impl<'p, 'tcx> RustcMatchCheckCtxt<'p, 'tcx> { // `field.ty()` doesn't normalize after substituting. let ty = cx.tcx.normalize_erasing_regions(cx.param_env, ty); let is_visible = adt.is_enum() || field.vis.is_accessible_from(cx.module, cx.tcx); - let is_uninhabited = cx.tcx.features().exhaustive_patterns && cx.is_uninhabited(ty); + let is_uninhabited = (cx.tcx.features().exhaustive_patterns + || cx.tcx.features().min_exhaustive_patterns) + && cx.is_uninhabited(ty); if is_uninhabited && (!is_visible || is_non_exhaustive) { None @@ -210,11 +206,11 @@ impl<'p, 'tcx> RustcMatchCheckCtxt<'p, 'tcx> { /// 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_sub_tys( - &self, - ctor: &Constructor<'p, 'tcx>, + pub(crate) fn ctor_sub_tys<'a>( + &'a self, + ctor: &'a Constructor<'p, 'tcx>, ty: RevealedTy<'tcx>, - ) -> &[RevealedTy<'tcx>] { + ) -> impl Iterator<Item = RevealedTy<'tcx>> + ExactSizeIterator + Captures<'a> { fn reveal_and_alloc<'a, 'tcx>( cx: &'a RustcMatchCheckCtxt<'_, 'tcx>, iter: impl Iterator<Item = Ty<'tcx>>, @@ -222,7 +218,7 @@ impl<'p, 'tcx> RustcMatchCheckCtxt<'p, 'tcx> { cx.dropless_arena.alloc_from_iter(iter.map(|ty| cx.reveal_opaque_ty(ty))) } let cx = self; - match ctor { + let slice = match ctor { Struct | Variant(_) | UnionField => match ty.kind() { ty::Tuple(fs) => reveal_and_alloc(cx, fs.iter()), ty::Adt(adt, args) => { @@ -263,7 +259,8 @@ impl<'p, 'tcx> RustcMatchCheckCtxt<'p, 'tcx> { Or => { bug!("called `Fields::wildcards` on an `Or` ctor") } - } + }; + slice.iter().copied() } /// The number of fields for this constructor. @@ -422,7 +419,8 @@ impl<'p, 'tcx> RustcMatchCheckCtxt<'p, 'tcx> { | ty::FnDef(_, _) | ty::FnPtr(_) | ty::Dynamic(_, _, _) - | ty::Closure(_, _) + | ty::Closure(..) + | ty::CoroutineClosure(..) | ty::Coroutine(_, _) | ty::Alias(_, _) | ty::Param(_) @@ -457,21 +455,20 @@ impl<'p, 'tcx> RustcMatchCheckCtxt<'p, 'tcx> { /// Note: the input patterns must have been lowered through /// `rustc_mir_build::thir::pattern::check_match::MatchVisitor::lower_pattern`. pub fn lower_pat(&self, pat: &'p Pat<'tcx>) -> DeconstructedPat<'p, 'tcx> { - let singleton = |pat| std::slice::from_ref(self.pattern_arena.alloc(pat)); let cx = self; let ty = cx.reveal_opaque_ty(pat.ty); let ctor; - let fields: &[_]; + let mut fields: Vec<_>; match &pat.kind { PatKind::AscribeUserType { subpattern, .. } | PatKind::InlineConstant { subpattern, .. } => return self.lower_pat(subpattern), PatKind::Binding { subpattern: Some(subpat), .. } => return self.lower_pat(subpat), PatKind::Binding { subpattern: None, .. } | PatKind::Wild => { ctor = Wildcard; - fields = &[]; + fields = vec![]; } PatKind::Deref { subpattern } => { - fields = singleton(self.lower_pat(subpattern)); + fields = vec![self.lower_pat(subpattern)]; ctor = match ty.kind() { // This is a box pattern. ty::Adt(adt, ..) if adt.is_box() => Struct, @@ -483,15 +480,14 @@ impl<'p, 'tcx> RustcMatchCheckCtxt<'p, 'tcx> { match ty.kind() { ty::Tuple(fs) => { ctor = Struct; - let mut wilds: SmallVec<[_; 2]> = fs + fields = fs .iter() .map(|ty| cx.reveal_opaque_ty(ty)) .map(|ty| DeconstructedPat::wildcard(ty)) .collect(); for pat in subpatterns { - wilds[pat.field.index()] = self.lower_pat(&pat.pattern); + fields[pat.field.index()] = self.lower_pat(&pat.pattern); } - fields = cx.pattern_arena.alloc_from_iter(wilds); } ty::Adt(adt, args) if adt.is_box() => { // The only legal patterns of type `Box` (outside `std`) are `_` and box @@ -513,7 +509,7 @@ impl<'p, 'tcx> RustcMatchCheckCtxt<'p, 'tcx> { DeconstructedPat::wildcard(self.reveal_opaque_ty(args.type_at(0))) }; ctor = Struct; - fields = singleton(pat); + fields = vec![pat]; } ty::Adt(adt, _) => { ctor = match pat.kind { @@ -533,14 +529,12 @@ impl<'p, 'tcx> RustcMatchCheckCtxt<'p, 'tcx> { ty }, ); - let mut wilds: SmallVec<[_; 2]> = - tys.map(|ty| DeconstructedPat::wildcard(ty)).collect(); + fields = 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); + fields[i] = self.lower_pat(&pat.pattern); } } - fields = cx.pattern_arena.alloc_from_iter(wilds); } _ => bug!("pattern has unexpected type: pat: {:?}, ty: {:?}", pat, ty), } @@ -552,7 +546,7 @@ impl<'p, 'tcx> RustcMatchCheckCtxt<'p, 'tcx> { Some(b) => Bool(b), None => Opaque(OpaqueId::new()), }; - fields = &[]; + fields = vec![]; } ty::Char | ty::Int(_) | ty::Uint(_) => { ctor = match value.try_eval_bits(cx.tcx, cx.param_env) { @@ -568,7 +562,7 @@ impl<'p, 'tcx> RustcMatchCheckCtxt<'p, 'tcx> { } None => Opaque(OpaqueId::new()), }; - fields = &[]; + fields = vec![]; } ty::Float(ty::FloatTy::F32) => { ctor = match value.try_eval_bits(cx.tcx, cx.param_env) { @@ -579,7 +573,7 @@ impl<'p, 'tcx> RustcMatchCheckCtxt<'p, 'tcx> { } None => Opaque(OpaqueId::new()), }; - fields = &[]; + fields = vec![]; } ty::Float(ty::FloatTy::F64) => { ctor = match value.try_eval_bits(cx.tcx, cx.param_env) { @@ -590,7 +584,7 @@ impl<'p, 'tcx> RustcMatchCheckCtxt<'p, 'tcx> { } None => Opaque(OpaqueId::new()), }; - fields = &[]; + fields = vec![]; } ty::Ref(_, t, _) if t.is_str() => { // We want a `&str` constant to behave like a `Deref` pattern, to be compatible @@ -601,16 +595,16 @@ impl<'p, 'tcx> RustcMatchCheckCtxt<'p, 'tcx> { // subfields. // Note: `t` is `str`, not `&str`. let ty = self.reveal_opaque_ty(*t); - let subpattern = DeconstructedPat::new(Str(*value), &[], ty, pat); + let subpattern = DeconstructedPat::new(Str(*value), Vec::new(), ty, pat); ctor = Ref; - fields = singleton(subpattern) + fields = vec![subpattern] } // All constants that can be structurally matched have already been expanded // into the corresponding `Pat`s by `const_to_pat`. Constants that remain are // opaque. _ => { ctor = Opaque(OpaqueId::new()); - fields = &[]; + fields = vec![]; } } } @@ -647,7 +641,7 @@ impl<'p, 'tcx> RustcMatchCheckCtxt<'p, 'tcx> { } _ => bug!("invalid type for range pattern: {}", ty.inner()), }; - fields = &[]; + fields = vec![]; } PatKind::Array { prefix, slice, suffix } | PatKind::Slice { prefix, slice, suffix } => { let array_len = match ty.kind() { @@ -663,25 +657,23 @@ impl<'p, 'tcx> RustcMatchCheckCtxt<'p, 'tcx> { SliceKind::FixedLen(prefix.len() + suffix.len()) }; ctor = Slice(Slice::new(array_len, kind)); - fields = cx.pattern_arena.alloc_from_iter( - prefix.iter().chain(suffix.iter()).map(|p| self.lower_pat(&*p)), - ) + fields = prefix.iter().chain(suffix.iter()).map(|p| self.lower_pat(&*p)).collect(); } PatKind::Or { .. } => { ctor = Or; let pats = expand_or_pat(pat); - fields = - cx.pattern_arena.alloc_from_iter(pats.into_iter().map(|p| self.lower_pat(p))) + fields = pats.into_iter().map(|p| self.lower_pat(p)).collect(); } PatKind::Never => { - // FIXME(never_patterns): handle `!` in exhaustiveness. This is a sane default - // in the meantime. + // A never pattern matches all the values of its type (namely none). Moreover it + // must be compatible with other constructors, since we can use `!` on a type like + // `Result<!, !>` which has other constructors. Hence we lower it as a wildcard. ctor = Wildcard; - fields = &[]; + fields = vec![]; } PatKind::Error(_) => { ctor = Opaque(OpaqueId::new()); - fields = &[]; + fields = vec![]; } } DeconstructedPat::new(ctor, fields, ty, pat) @@ -766,7 +758,7 @@ impl<'p, 'tcx> RustcMatchCheckCtxt<'p, 'tcx> { 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()), + IntRange(range) => return self.hoist_pat_range(range, *pat.ty()), Struct | Variant(_) | UnionField => match pat.ty().kind() { ty::Tuple(..) => PatKind::Leaf { subpatterns: subpatterns @@ -785,7 +777,7 @@ impl<'p, 'tcx> RustcMatchCheckCtxt<'p, 'tcx> { 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) + .list_variant_nonhidden_fields(*pat.ty(), variant) .zip(subpatterns) .map(|((field, _ty), pattern)| FieldPat { field, pattern }) .collect(); @@ -796,7 +788,7 @@ impl<'p, 'tcx> RustcMatchCheckCtxt<'p, 'tcx> { PatKind::Leaf { subpatterns } } } - _ => bug!("unexpected ctor for type {:?} {:?}", pat.ctor(), pat.ty()), + _ => 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 @@ -850,106 +842,9 @@ impl<'p, 'tcx> RustcMatchCheckCtxt<'p, 'tcx> { Pat { ty: pat.ty().inner(), span: DUMMY_SP, kind } } - - /// Best-effort `Debug` implementation. - pub(crate) fn debug_pat( - f: &mut fmt::Formatter<'_>, - pat: &crate::pat::DeconstructedPat<'_, Self>, - ) -> fmt::Result { - let mut first = true; - let mut start_or_continue = |s| { - if first { - first = false; - "" - } else { - s - } - }; - let mut start_or_comma = || start_or_continue(", "); - - match pat.ctor() { - 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 - // the pattern is a box pattern. - let subpattern = pat.iter_fields().next().unwrap(); - write!(f, "box {subpattern:?}") - } - ty::Adt(..) | ty::Tuple(..) => { - 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)?; - } - - // Without `cx`, we can't know which field corresponds to which, so we can't - // get the names of the fields. Instead we just display everything as a tuple - // struct, which should be good enough. - write!(f, "(")?; - for p in pat.iter_fields() { - write!(f, "{}", start_or_comma())?; - write!(f, "{p:?}")?; - } - write!(f, ")") - } - _ => 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, "[")?; - match slice.kind { - SliceKind::FixedLen(_) => { - for p in subpatterns { - write!(f, "{}{:?}", start_or_comma(), p)?; - } - } - SliceKind::VarLen(prefix_len, _) => { - for p in subpatterns.by_ref().take(prefix_len) { - write!(f, "{}{:?}", start_or_comma(), p)?; - } - write!(f, "{}", start_or_comma())?; - write!(f, "..")?; - for p in subpatterns { - write!(f, "{}{:?}", start_or_comma(), p)?; - } - } - } - write!(f, "]") - } - Bool(b) => write!(f, "{b}"), - // Best-effort, will render signed ranges incorrectly - IntRange(range) => write!(f, "{range:?}"), - F32Range(lo, hi, end) => write!(f, "{lo}{end}{hi}"), - F64Range(lo, hi, end) => write!(f, "{lo}{end}{hi}"), - Str(value) => write!(f, "{value}"), - Opaque(..) => write!(f, "<constant pattern>"), - Or => { - for pat in pat.iter_fields() { - write!(f, "{}{:?}", start_or_continue(" | "), pat)?; - } - Ok(()) - } - Wildcard | Missing { .. } | NonExhaustive | Hidden => write!(f, "_ : {:?}", pat.ty()), - } - } } -impl<'p, 'tcx> TypeCx for RustcMatchCheckCtxt<'p, 'tcx> { +impl<'p, 'tcx: 'p> TypeCx for RustcMatchCheckCtxt<'p, 'tcx> { type Ty = RevealedTy<'tcx>; type Error = ErrorGuaranteed; type VariantIdx = VariantIdx; @@ -960,48 +855,60 @@ impl<'p, 'tcx> TypeCx for RustcMatchCheckCtxt<'p, 'tcx> { fn is_exhaustive_patterns_feature_on(&self) -> bool { self.tcx.features().exhaustive_patterns } + fn is_min_exhaustive_patterns_feature_on(&self) -> bool { + self.tcx.features().min_exhaustive_patterns + } - fn ctor_arity(&self, ctor: &crate::constructor::Constructor<Self>, ty: Self::Ty) -> usize { - self.ctor_arity(ctor, 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 ctor_sub_tys<'a>( + &'a self, + ctor: &'a crate::constructor::Constructor<Self>, + ty: &'a Self::Ty, + ) -> impl Iterator<Item = Self::Ty> + ExactSizeIterator + Captures<'a> { + self.ctor_sub_tys(ctor, *ty) } fn ctors_for_ty( &self, - ty: Self::Ty, + ty: &Self::Ty, ) -> Result<crate::constructor::ConstructorSet<Self>, Self::Error> { - self.ctors_for_ty(ty) + self.ctors_for_ty(*ty) } - fn debug_pat( + fn write_variant_name( f: &mut fmt::Formatter<'_>, - pat: &crate::pat::DeconstructedPat<'_, Self>, + pat: &crate::pat::DeconstructedPat<Self>, ) -> fmt::Result { - Self::debug_pat(f, pat) + if let ty::Adt(adt, _) = pat.ty().kind() { + if adt.is_box() { + write!(f, "Box")? + } else { + let variant = adt.variant(Self::variant_index_for_adt(pat.ctor(), *adt)); + write!(f, "{}", variant.name)?; + } + } + Ok(()) } - fn bug(&self, fmt: fmt::Arguments<'_>) -> ! { + + fn bug(&self, fmt: fmt::Arguments<'_>) -> Self::Error { span_bug!(self.scrut_span, "{}", fmt) } fn lint_overlapping_range_endpoints( &self, - pat: &crate::pat::DeconstructedPat<'_, Self>, + pat: &crate::pat::DeconstructedPat<Self>, overlaps_on: IntRange, - overlaps_with: &[&crate::pat::DeconstructedPat<'_, Self>], + overlaps_with: &[&crate::pat::DeconstructedPat<Self>], ) { - let overlap_as_pat = self.hoist_pat_range(&overlaps_on, pat.ty()); + let overlap_as_pat = self.hoist_pat_range(&overlaps_on, *pat.ty()); let overlaps: Vec<_> = overlaps_with .iter() .map(|pat| pat.data().unwrap().span) .map(|span| errors::Overlap { range: overlap_as_pat.clone(), span }) .collect(); let pat_span = pat.data().unwrap().span; - self.tcx.emit_spanned_lint( + self.tcx.emit_node_span_lint( lint::builtin::OVERLAPPING_RANGE_ENDPOINTS, self.match_lint_level, pat_span, diff --git a/compiler/rustc_pattern_analysis/src/usefulness.rs b/compiler/rustc_pattern_analysis/src/usefulness.rs index dac354a1c52..80a807b4f27 100644 --- a/compiler/rustc_pattern_analysis/src/usefulness.rs +++ b/compiler/rustc_pattern_analysis/src/usefulness.rs @@ -548,11 +548,12 @@ //! [`ValidityConstraint::specialize`]. //! //! Having said all that, in practice we don't fully follow what's been presented in this section. -//! Under `exhaustive_patterns`, we allow omitting empty arms even in `!known_valid` places, for -//! backwards-compatibility until we have a better alternative. Without `exhaustive_patterns`, we -//! mostly treat empty types as inhabited, except specifically a non-nested `!` or empty enum. In -//! this specific case we also allow the empty match regardless of place validity, for -//! backwards-compatibility. Hopefully we can eventually deprecate this. +//! Let's call "toplevel exception" the case where the match scrutinee itself has type `!` or +//! `EmptyEnum`. First, on stable rust, we require `_` patterns for empty types in all cases apart +//! from the toplevel exception. The `exhaustive_patterns` and `min_exaustive_patterns` allow +//! omitting patterns in the cases described above. There's a final detail: in the toplevel +//! exception or with the `exhaustive_patterns` feature, we ignore place validity when checking +//! whether a pattern is required for exhaustiveness. I (Nadrieril) hope to deprecate this behavior. //! //! //! @@ -718,7 +719,7 @@ use std::fmt; use crate::constructor::{Constructor, ConstructorSet, IntRange}; use crate::pat::{DeconstructedPat, PatOrWild, WitnessPat}; -use crate::{Captures, MatchArm, MatchCtxt, TypeCx}; +use crate::{Captures, MatchArm, TypeCx}; use self::ValidityConstraint::*; @@ -729,31 +730,48 @@ pub fn ensure_sufficient_stack<R>(f: impl FnOnce() -> R) -> R { f() } +/// Context that provides information for usefulness checking. +pub struct UsefulnessCtxt<'a, Cx: TypeCx> { + /// The context for type information. + pub tycx: &'a Cx, +} + +impl<'a, Cx: TypeCx> Copy for UsefulnessCtxt<'a, Cx> {} +impl<'a, Cx: TypeCx> Clone for UsefulnessCtxt<'a, Cx> { + fn clone(&self) -> Self { + Self { tycx: self.tycx } + } +} + /// 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, Cx: TypeCx> { - #[derivative(Debug = "ignore")] - pub(crate) mcx: MatchCtxt<'a, Cx>, +struct PlaceCtxt<'a, Cx: TypeCx> { + cx: &'a Cx, /// Type of the place under investigation. - pub(crate) ty: Cx::Ty, + ty: &'a Cx::Ty, } -impl<'a, Cx: TypeCx> PlaceCtxt<'a, 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, Cx>, ty: Cx::Ty) -> Self { - PlaceCtxt { mcx, ty } +impl<'a, Cx: TypeCx> Copy for PlaceCtxt<'a, Cx> {} +impl<'a, Cx: TypeCx> Clone for PlaceCtxt<'a, Cx> { + fn clone(&self) -> Self { + Self { cx: self.cx, ty: self.ty } + } +} + +impl<'a, Cx: TypeCx> fmt::Debug for PlaceCtxt<'a, Cx> { + fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result { + fmt.debug_struct("PlaceCtxt").field("ty", self.ty).finish() } +} - pub(crate) fn ctor_arity(&self, ctor: &Constructor<Cx>) -> usize { - self.mcx.tycx.ctor_arity(ctor, self.ty) +impl<'a, Cx: TypeCx> PlaceCtxt<'a, Cx> { + fn ctor_arity(&self, ctor: &Constructor<Cx>) -> usize { + self.cx.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) + fn ctors_for_ty(&self) -> Result<ConstructorSet<Cx>, Cx::Error> { + self.cx.ctors_for_ty(self.ty) } - pub(crate) fn ctors_for_ty(&self) -> Result<ConstructorSet<Cx>, Cx::Error> { - self.mcx.tycx.ctors_for_ty(self.ty) + fn wild_from_ctor(&self, ctor: Constructor<Cx>) -> WitnessPat<Cx> { + WitnessPat::wild_from_ctor(self.cx, ctor, self.ty.clone()) } } @@ -804,12 +822,42 @@ impl fmt::Display for ValidityConstraint { } } +/// Data about a place under investigation. +struct PlaceInfo<Cx: TypeCx> { + /// The type of the place. + ty: Cx::Ty, + /// Whether the place is known to contain valid data. + validity: ValidityConstraint, + /// Whether the place is the scrutinee itself or a subplace of it. + is_scrutinee: bool, +} + +impl<Cx: TypeCx> PlaceInfo<Cx> { + fn specialize<'a>( + &'a self, + cx: &'a Cx, + ctor: &'a Constructor<Cx>, + ) -> impl Iterator<Item = Self> + ExactSizeIterator + Captures<'a> { + let ctor_sub_tys = cx.ctor_sub_tys(ctor, &self.ty); + let ctor_sub_validity = self.validity.specialize(ctor); + ctor_sub_tys.map(move |ty| PlaceInfo { + ty, + validity: ctor_sub_validity, + is_scrutinee: false, + }) + } +} + +impl<Cx: TypeCx> Clone for PlaceInfo<Cx> { + fn clone(&self) -> Self { + Self { ty: self.ty.clone(), validity: self.validity, is_scrutinee: self.is_scrutinee } + } +} + /// Represents a pattern-tuple under investigation. // The three lifetimes are: // - 'p coming from the input // - Cx global compilation context -#[derive(derivative::Derivative)] -#[derivative(Clone(bound = ""))] struct PatStack<'p, Cx: TypeCx> { // Rows of len 1 are very common, which is why `SmallVec[_; 2]` works well. pats: SmallVec<[PatOrWild<'p, Cx>; 2]>, @@ -819,8 +867,14 @@ struct PatStack<'p, Cx: TypeCx> { relevant: bool, } +impl<'p, Cx: TypeCx> Clone for PatStack<'p, Cx> { + fn clone(&self) -> Self { + Self { pats: self.pats.clone(), relevant: self.relevant } + } +} + impl<'p, Cx: TypeCx> PatStack<'p, Cx> { - fn from_pattern(pat: &'p DeconstructedPat<'p, Cx>) -> Self { + fn from_pattern(pat: &'p DeconstructedPat<Cx>) -> Self { PatStack { pats: smallvec![PatOrWild::Pat(pat)], relevant: true } } @@ -973,10 +1027,9 @@ struct Matrix<'p, Cx: TypeCx> { /// each column must have the same type. Each column corresponds to a place within the /// scrutinee. rows: Vec<MatrixRow<'p, Cx>>, - /// Track the type of each column/place. - place_ty: SmallVec<[Cx::Ty; 2]>, - /// Track for each column/place whether it contains a known valid value. - place_validity: SmallVec<[ValidityConstraint; 2]>, + /// Track info about each place. Each place corresponds to a column in `rows`, and their types + /// must match. + place_info: SmallVec<[PlaceInfo<Cx>; 2]>, /// Track whether the virtual wildcard row used to compute exhaustiveness is relevant. See top /// of the file for details on relevancy. wildcard_row_is_relevant: bool, @@ -1004,10 +1057,10 @@ impl<'p, Cx: TypeCx> Matrix<'p, Cx> { scrut_ty: Cx::Ty, scrut_validity: ValidityConstraint, ) -> Self { + let place_info = PlaceInfo { ty: scrut_ty, validity: scrut_validity, is_scrutinee: true }; let mut matrix = Matrix { rows: Vec::with_capacity(arms.len()), - place_ty: smallvec![scrut_ty], - place_validity: smallvec![scrut_validity], + place_info: smallvec![place_info], wildcard_row_is_relevant: true, }; for (row_id, arm) in arms.iter().enumerate() { @@ -1023,11 +1076,11 @@ impl<'p, Cx: TypeCx> Matrix<'p, Cx> { matrix } - fn head_ty(&self) -> Option<Cx::Ty> { - self.place_ty.first().copied() + fn head_place(&self) -> Option<&PlaceInfo<Cx>> { + self.place_info.first() } fn column_count(&self) -> usize { - self.place_ty.len() + self.place_info.len() } fn rows( @@ -1054,29 +1107,23 @@ impl<'p, Cx: TypeCx> Matrix<'p, Cx> { pcx: &PlaceCtxt<'_, Cx>, ctor: &Constructor<Cx>, ctor_is_relevant: bool, - ) -> Matrix<'p, Cx> { - let ctor_sub_tys = pcx.ctor_sub_tys(ctor); - let arity = ctor_sub_tys.len(); - let specialized_place_ty = - ctor_sub_tys.iter().chain(self.place_ty[1..].iter()).copied().collect(); - let ctor_sub_validity = self.place_validity[0].specialize(ctor); - let specialized_place_validity = std::iter::repeat(ctor_sub_validity) - .take(arity) - .chain(self.place_validity[1..].iter().copied()) - .collect(); + ) -> Result<Matrix<'p, Cx>, Cx::Error> { + let subfield_place_info = self.place_info[0].specialize(pcx.cx, ctor); + let arity = subfield_place_info.len(); + let specialized_place_info = + subfield_place_info.chain(self.place_info[1..].iter().cloned()).collect(); let mut matrix = Matrix { rows: Vec::new(), - place_ty: specialized_place_ty, - place_validity: specialized_place_validity, + place_info: specialized_place_info, wildcard_row_is_relevant: self.wildcard_row_is_relevant && ctor_is_relevant, }; for (i, row) in self.rows().enumerate() { - if ctor.is_covered_by(pcx, row.head().ctor()) { + if ctor.is_covered_by(pcx.cx, row.head().ctor())? { let new_row = row.pop_head_constructor(ctor, arity, ctor_is_relevant, i); matrix.expand_and_push(new_row); } } - matrix + Ok(matrix) } } @@ -1100,11 +1147,11 @@ impl<'p, Cx: TypeCx> fmt::Debug for Matrix<'p, Cx> { .map(|row| row.iter().map(|pat| format!("{pat:?}")).collect()) .collect(); pretty_printed_matrix - .push(self.place_validity.iter().map(|validity| format!("{validity}")).collect()); + .push(self.place_info.iter().map(|place| format!("{}", place.validity)).collect()); let column_count = self.column_count(); assert!(self.rows.iter().all(|row| row.len() == column_count)); - assert!(self.place_validity.len() == column_count); + assert!(self.place_info.len() == column_count); let column_widths: Vec<usize> = (0..column_count) .map(|col| pretty_printed_matrix.iter().map(|row| row[col].len()).max().unwrap_or(0)) .collect(); @@ -1180,10 +1227,15 @@ impl<'p, Cx: TypeCx> fmt::Debug for Matrix<'p, Cx> { /// The final `Pair(Some(_), true)` is then the resulting witness. /// /// See the top of the file for more detailed explanations and examples. -#[derive(derivative::Derivative)] -#[derivative(Debug(bound = ""), Clone(bound = ""))] +#[derive(Debug)] struct WitnessStack<Cx: TypeCx>(Vec<WitnessPat<Cx>>); +impl<Cx: TypeCx> Clone for WitnessStack<Cx> { + fn clone(&self) -> Self { + Self(self.0.clone()) + } +} + impl<Cx: TypeCx> WitnessStack<Cx> { /// Asserts that the witness contains a single pattern, and returns it. fn single_pattern(self) -> WitnessPat<Cx> { @@ -1212,9 +1264,9 @@ impl<Cx: TypeCx> WitnessStack<Cx> { /// ``` fn apply_constructor(&mut self, pcx: &PlaceCtxt<'_, Cx>, ctor: &Constructor<Cx>) { let len = self.0.len(); - let arity = ctor.arity(pcx); + let arity = pcx.ctor_arity(ctor); let fields = self.0.drain((len - arity)..).rev().collect(); - let pat = WitnessPat::new(ctor.clone(), fields, pcx.ty); + let pat = WitnessPat::new(ctor.clone(), fields, pcx.ty.clone()); self.0.push(pat); } } @@ -1228,18 +1280,23 @@ impl<Cx: TypeCx> WitnessStack<Cx> { /// /// 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(derivative::Derivative)] -#[derivative(Debug(bound = ""), Clone(bound = ""))] +#[derive(Debug)] struct WitnessMatrix<Cx: TypeCx>(Vec<WitnessStack<Cx>>); +impl<Cx: TypeCx> Clone for WitnessMatrix<Cx> { + fn clone(&self) -> Self { + Self(self.0.clone()) + } +} + impl<Cx: TypeCx> WitnessMatrix<Cx> { /// New matrix with no witnesses. fn empty() -> Self { - WitnessMatrix(vec![]) + WitnessMatrix(Vec::new()) } /// New matrix with one `()` witness, i.e. with no columns. fn unit_witness() -> Self { - WitnessMatrix(vec![WitnessStack(vec![])]) + WitnessMatrix(vec![WitnessStack(Vec::new())]) } /// Whether this has any witnesses. @@ -1277,20 +1334,20 @@ impl<Cx: TypeCx> WitnessMatrix<Cx> { *self = Self::empty(); } else if !report_individual_missing_ctors { // Report `_` as missing. - let pat = WitnessPat::wild_from_ctor(pcx, Constructor::Wildcard); + let pat = pcx.wild_from_ctor(Constructor::Wildcard); self.push_pattern(pat); } else if missing_ctors.iter().any(|c| c.is_non_exhaustive()) { // We need to report a `_` anyway, so listing other constructors would be redundant. // `NonExhaustive` is displayed as `_` just like `Wildcard`, but it will be picked // up by diagnostics to add a note about why `_` is required here. - let pat = WitnessPat::wild_from_ctor(pcx, Constructor::NonExhaustive); + let pat = pcx.wild_from_ctor(Constructor::NonExhaustive); self.push_pattern(pat); } else { // For each missing constructor `c`, we add a `c(_, _, _)` witness appropriately // filled with wildcards. let mut ret = Self::empty(); for ctor in missing_ctors { - let pat = WitnessPat::wild_from_ctor(pcx, ctor.clone()); + let pat = pcx.wild_from_ctor(ctor.clone()); // Clone `self` and add `c(_, _, _)` to each of its witnesses. let mut wit_matrix = self.clone(); wit_matrix.push_pattern(pat); @@ -1324,7 +1381,7 @@ impl<Cx: TypeCx> WitnessMatrix<Cx> { /// We can however get false negatives because exhaustiveness does not explore all cases. See the /// section on relevancy at the top of the file. fn collect_overlapping_range_endpoints<'p, Cx: TypeCx>( - mcx: MatchCtxt<'_, Cx>, + mcx: UsefulnessCtxt<'_, Cx>, overlap_range: IntRange, matrix: &Matrix<'p, Cx>, specialized_matrix: &Matrix<'p, Cx>, @@ -1395,11 +1452,10 @@ fn collect_overlapping_range_endpoints<'p, Cx: TypeCx>( /// - 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(mcx, is_top_level), ret)] +#[instrument(level = "debug", skip(mcx), ret)] fn compute_exhaustiveness_and_usefulness<'a, 'p, Cx: TypeCx>( - mcx: MatchCtxt<'a, Cx>, + mcx: UsefulnessCtxt<'a, Cx>, matrix: &mut Matrix<'p, Cx>, - is_top_level: bool, ) -> Result<WitnessMatrix<Cx>, Cx::Error> { debug_assert!(matrix.rows().all(|r| r.len() == matrix.column_count())); @@ -1410,7 +1466,7 @@ fn compute_exhaustiveness_and_usefulness<'a, 'p, Cx: TypeCx>( return Ok(WitnessMatrix::empty()); } - let Some(ty) = matrix.head_ty() else { + let Some(place) = matrix.head_place() 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. let mut useful = true; // Whether the next row is useful. @@ -1430,19 +1486,25 @@ fn compute_exhaustiveness_and_usefulness<'a, 'p, Cx: TypeCx>( }; }; - debug!("ty: {ty:?}"); - let pcx = &PlaceCtxt { mcx, ty }; + let ty = &place.ty.clone(); // Clone it out so we can mutate `matrix` later. + let pcx = &PlaceCtxt { cx: mcx.tycx, ty }; + debug!("ty: {:?}", pcx.ty); let ctors_for_ty = pcx.ctors_for_ty()?; - // Whether the place/column we are inspecting is known to contain valid data. - let place_validity = matrix.place_validity[0]; // We treat match scrutinees of type `!` or `EmptyEnum` differently. let is_toplevel_exception = - is_top_level && matches!(ctors_for_ty, ConstructorSet::NoConstructors); - // Whether empty patterns can be omitted for exhaustiveness. - let can_omit_empty_arms = is_toplevel_exception || mcx.tycx.is_exhaustive_patterns_feature_on(); - // Whether empty patterns are counted as useful or not. - let empty_arms_are_unreachable = place_validity.is_known_valid() && can_omit_empty_arms; + place.is_scrutinee && matches!(ctors_for_ty, ConstructorSet::NoConstructors); + // Whether empty patterns are counted as useful or not. We only warn an empty arm unreachable if + // it is guaranteed unreachable by the opsem (i.e. if the place is `known_valid`). + let empty_arms_are_unreachable = place.validity.is_known_valid() + && (is_toplevel_exception + || mcx.tycx.is_exhaustive_patterns_feature_on() + || mcx.tycx.is_min_exhaustive_patterns_feature_on()); + // Whether empty patterns can be omitted for exhaustiveness. We ignore place validity in the + // toplevel exception and `exhaustive_patterns` cases for backwards compatibility. + let can_omit_empty_arms = empty_arms_are_unreachable + || is_toplevel_exception + || mcx.tycx.is_exhaustive_patterns_feature_on(); // Analyze the constructors present in this column. let ctors = matrix.heads().map(|p| p.ctor()); @@ -1458,11 +1520,9 @@ fn compute_exhaustiveness_and_usefulness<'a, 'p, Cx: TypeCx>( split_ctors.push(Constructor::Missing); } - // Decide what constructors to report. - let is_integers = matches!(ctors_for_ty, ConstructorSet::Integers { .. }); - let always_report_all = is_top_level && !is_integers; - // Whether we should report "Enum::A and Enum::C are missing" or "_ is missing". - let report_individual_missing_ctors = always_report_all || !all_missing; + // Whether we should report "Enum::A and Enum::C are missing" or "_ is missing". At the top + // level we prefer to list all constructors. + let report_individual_missing_ctors = place.is_scrutinee || !all_missing; // Which constructors are considered missing. We ensure that `!missing_ctors.is_empty() => // split_ctors.contains(Missing)`. The converse usually holds except when // `!place_validity.is_known_valid()`. @@ -1479,9 +1539,9 @@ fn compute_exhaustiveness_and_usefulness<'a, 'p, Cx: TypeCx>( // 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 spec_matrix = matrix.specialize_constructor(pcx, &ctor, ctor_is_relevant)?; let mut witnesses = ensure_sufficient_stack(|| { - compute_exhaustiveness_and_usefulness(mcx, &mut spec_matrix, false) + compute_exhaustiveness_and_usefulness(mcx, &mut spec_matrix) })?; // Transform witnesses for `spec_matrix` into witnesses for `matrix`. @@ -1531,7 +1591,7 @@ 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<&'p DeconstructedPat<'p, Cx>>), + Useful(Vec<&'p DeconstructedPat<Cx>>), /// The arm is redundant and can be removed without changing the behavior of the match /// expression. Redundant, @@ -1547,16 +1607,16 @@ pub struct UsefulnessReport<'p, Cx: TypeCx> { } /// Computes whether a match is exhaustive and which of its arms are useful. -#[instrument(skip(cx, arms), level = "debug")] +#[instrument(skip(tycx, arms), level = "debug")] pub fn compute_match_usefulness<'p, Cx: TypeCx>( - cx: MatchCtxt<'_, Cx>, + tycx: &Cx, arms: &[MatchArm<'p, Cx>], scrut_ty: Cx::Ty, scrut_validity: ValidityConstraint, ) -> Result<UsefulnessReport<'p, Cx>, Cx::Error> { + let cx = UsefulnessCtxt { tycx }; let mut matrix = Matrix::new(arms, scrut_ty, scrut_validity); - let non_exhaustiveness_witnesses = - compute_exhaustiveness_and_usefulness(cx, &mut matrix, true)?; + let non_exhaustiveness_witnesses = compute_exhaustiveness_and_usefulness(cx, &mut matrix)?; let non_exhaustiveness_witnesses: Vec<_> = non_exhaustiveness_witnesses.single_column(); let arm_usefulness: Vec<_> = arms |