diff options
Diffstat (limited to 'compiler/rustc_pattern_analysis/src')
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/constructor.rs | 96 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/lib.rs | 24 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/lints.rs | 120 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/pat.rs | 18 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/pat_column.rs | 90 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/rustc.rs | 10 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/usefulness.rs | 82 |
7 files changed, 173 insertions, 267 deletions
diff --git a/compiler/rustc_pattern_analysis/src/constructor.rs b/compiler/rustc_pattern_analysis/src/constructor.rs index 4996015f863..d6c194fb9dc 100644 --- a/compiler/rustc_pattern_analysis/src/constructor.rs +++ b/compiler/rustc_pattern_analysis/src/constructor.rs @@ -151,7 +151,6 @@ use std::cmp::{self, max, min, Ordering}; use std::fmt; use std::iter::once; -use std::mem; use smallvec::SmallVec; @@ -163,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. @@ -649,6 +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(Debug)] pub enum Constructor<Cx: TypeCx> { /// Tuples and structs. Struct, @@ -718,74 +717,6 @@ impl<Cx: TypeCx> Clone for Constructor<Cx> { } } -impl<Cx: TypeCx> fmt::Debug for Constructor<Cx> { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - match self { - Constructor::Struct => f.debug_tuple("Struct").finish(), - Constructor::Variant(idx) => f.debug_tuple("Variant").field(idx).finish(), - Constructor::Ref => f.debug_tuple("Ref").finish(), - Constructor::Slice(slice) => f.debug_tuple("Slice").field(slice).finish(), - Constructor::UnionField => f.debug_tuple("UnionField").finish(), - Constructor::Bool(b) => f.debug_tuple("Bool").field(b).finish(), - Constructor::IntRange(range) => f.debug_tuple("IntRange").field(range).finish(), - Constructor::F32Range(lo, hi, end) => { - f.debug_tuple("F32Range").field(lo).field(hi).field(end).finish() - } - Constructor::F64Range(lo, hi, end) => { - f.debug_tuple("F64Range").field(lo).field(hi).field(end).finish() - } - Constructor::Str(value) => f.debug_tuple("Str").field(value).finish(), - Constructor::Opaque(inner) => f.debug_tuple("Opaque").field(inner).finish(), - Constructor::Or => f.debug_tuple("Or").finish(), - Constructor::Wildcard => f.debug_tuple("Wildcard").finish(), - Constructor::NonExhaustive => f.debug_tuple("NonExhaustive").finish(), - Constructor::Hidden => f.debug_tuple("Hidden").finish(), - Constructor::Missing => f.debug_tuple("Missing").finish(), - } - } -} - -impl<Cx: TypeCx> PartialEq for Constructor<Cx> { - fn eq(&self, other: &Self) -> bool { - (mem::discriminant(self) == mem::discriminant(other)) - && match (self, other) { - (Constructor::Struct, Constructor::Struct) => true, - (Constructor::Variant(self_variant), Constructor::Variant(other_variant)) => { - self_variant == other_variant - } - (Constructor::Ref, Constructor::Ref) => true, - (Constructor::Slice(self_slice), Constructor::Slice(other_slice)) => { - self_slice == other_slice - } - (Constructor::UnionField, Constructor::UnionField) => true, - (Constructor::Bool(self_b), Constructor::Bool(other_b)) => self_b == other_b, - (Constructor::IntRange(self_range), Constructor::IntRange(other_range)) => { - self_range == other_range - } - ( - Constructor::F32Range(self_lo, self_hi, self_end), - Constructor::F32Range(other_lo, other_hi, other_end), - ) => self_lo == other_lo && self_hi == other_hi && self_end == other_end, - ( - Constructor::F64Range(self_lo, self_hi, self_end), - Constructor::F64Range(other_lo, other_hi, other_end), - ) => self_lo == other_lo && self_hi == other_hi && self_end == other_end, - (Constructor::Str(self_value), Constructor::Str(other_value)) => { - self_value == other_value - } - (Constructor::Opaque(self_inner), Constructor::Opaque(other_inner)) => { - self_inner == other_inner - } - (Constructor::Or, Constructor::Or) => true, - (Constructor::Wildcard, Constructor::Wildcard) => true, - (Constructor::NonExhaustive, Constructor::NonExhaustive) => true, - (Constructor::Hidden, Constructor::Hidden) => true, - (Constructor::Missing, Constructor::Missing) => true, - _ => unreachable!(), - } - } -} - impl<Cx: TypeCx> Constructor<Cx> { pub(crate) fn is_non_exhaustive(&self) -> bool { matches!(self, NonExhaustive) @@ -818,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`. @@ -827,12 +758,11 @@ 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 { + pub(crate) fn is_covered_by(&self, cx: &Cx, other: &Self) -> bool { match (self, other) { - (Wildcard, _) => pcx - .mcx - .tycx - .bug(format_args!("Constructor splitting should not have returned `Wildcard`")), + (Wildcard, _) => { + 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. @@ -873,7 +803,7 @@ impl<Cx: TypeCx> Constructor<Cx> { (Opaque(self_id), Opaque(other_id)) => self_id == other_id, (Opaque(..), _) | (_, Opaque(..)) => false, - _ => pcx.mcx.tycx.bug(format_args!( + _ => cx.bug(format_args!( "trying to compare incompatible constructors {self:?} and {other:?}" )), } @@ -950,10 +880,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> { @@ -962,7 +892,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/lib.rs b/compiler/rustc_pattern_analysis/src/lib.rs index a53d7a0d809..3d0eb117d17 100644 --- a/compiler/rustc_pattern_analysis/src/lib.rs +++ b/compiler/rustc_pattern_analysis/src/lib.rs @@ -6,6 +6,7 @@ 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 +68,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")] @@ -135,20 +137,6 @@ pub trait TypeCx: Sized + fmt::Debug { } } -/// Context that provides information global to a match. -pub struct MatchCtxt<'a, Cx: TypeCx> { - /// The context for type information. - pub tycx: &'a Cx, -} - -impl<'a, Cx: TypeCx> Clone for MatchCtxt<'a, Cx> { - fn clone(&self) -> Self { - Self { tycx: self.tycx } - } -} - -impl<'a, Cx: TypeCx> Copy for MatchCtxt<'a, Cx> {} - /// The arm of a match expression. #[derive(Debug)] pub struct MatchArm<'p, Cx: TypeCx> { @@ -175,15 +163,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 4bfe7dfb072..3f1497540d2 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>, + 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,18 +56,17 @@ 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. diff --git a/compiler/rustc_pattern_analysis/src/pat.rs b/compiler/rustc_pattern_analysis/src/pat.rs index d476766d466..d419ee46a8e 100644 --- a/compiler/rustc_pattern_analysis/src/pat.rs +++ b/compiler/rustc_pattern_analysis/src/pat.rs @@ -6,7 +6,6 @@ use std::fmt; use smallvec::{smallvec, SmallVec}; use crate::constructor::{Constructor, Slice, SliceKind}; -use crate::usefulness::PlaceCtxt; use crate::{Captures, TypeCx}; use self::Constructor::*; @@ -298,6 +297,7 @@ 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(Debug)] pub struct WitnessPat<Cx: TypeCx> { ctor: Constructor<Cx>, pub(crate) fields: Vec<WitnessPat<Cx>>, @@ -310,16 +310,6 @@ impl<Cx: TypeCx> Clone for WitnessPat<Cx> { } } -impl<Cx: TypeCx> fmt::Debug for WitnessPat<Cx> { - fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result { - fmt.debug_struct("WitnessPat") - .field("ctor", &self.ctor) - .field("fields", &self.fields) - .field("ty", &self.ty) - .finish() - } -} - impl<Cx: TypeCx> WitnessPat<Cx> { pub(crate) fn new(ctor: Constructor<Cx>, fields: Vec<Self>, ty: Cx::Ty) -> Self { Self { ctor, fields, ty } @@ -331,9 +321,9 @@ 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 fields = pcx.ctor_sub_tys(&ctor).map(|ty| Self::wildcard(ty)).collect(); - Self::new(ctor, fields, pcx.ty.clone()) + 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> { 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..3cacfc491b9 --- /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<'p, 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<'p, 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())); + 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 223d6cefc83..15de3346a97 100644 --- a/compiler/rustc_pattern_analysis/src/rustc.rs +++ b/compiler/rustc_pattern_analysis/src/rustc.rs @@ -30,11 +30,6 @@ pub type ConstructorSet<'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, 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>>; @@ -680,8 +675,9 @@ impl<'p, 'tcx> RustcMatchCheckCtxt<'p, 'tcx> { cx.pattern_arena.alloc_from_iter(pats.into_iter().map(|p| self.lower_pat(p))) } 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 = &[]; } diff --git a/compiler/rustc_pattern_analysis/src/usefulness.rs b/compiler/rustc_pattern_analysis/src/usefulness.rs index b15de1c0ca9..f729f0aa41b 100644 --- a/compiler/rustc_pattern_analysis/src/usefulness.rs +++ b/compiler/rustc_pattern_analysis/src/usefulness.rs @@ -719,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::*; @@ -730,21 +730,33 @@ 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. -pub(crate) struct PlaceCtxt<'a, Cx: TypeCx> { - pub(crate) mcx: MatchCtxt<'a, Cx>, +struct PlaceCtxt<'a, Cx: TypeCx> { + cx: &'a Cx, /// Type of the place under investigation. - pub(crate) ty: &'a Cx::Ty, + ty: &'a Cx::Ty, } +impl<'a, Cx: TypeCx> Copy for PlaceCtxt<'a, Cx> {} impl<'a, Cx: TypeCx> Clone for PlaceCtxt<'a, Cx> { fn clone(&self) -> Self { - Self { mcx: self.mcx, ty: self.ty } + Self { cx: self.cx, ty: self.ty } } } -impl<'a, Cx: TypeCx> Copy for PlaceCtxt<'a, Cx> {} - 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() @@ -752,23 +764,20 @@ impl<'a, Cx: TypeCx> fmt::Debug for PlaceCtxt<'a, Cx> { } 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: &'a Cx::Ty) -> Self { - PlaceCtxt { mcx, ty } - } - - pub(crate) fn ctor_arity(&self, ctor: &Constructor<Cx>) -> usize { - self.mcx.tycx.ctor_arity(ctor, self.ty) + fn ctor_arity(&self, ctor: &Constructor<Cx>) -> usize { + self.cx.ctor_arity(ctor, self.ty) } - pub(crate) fn ctor_sub_tys( + fn ctor_sub_tys( &'a self, ctor: &'a Constructor<Cx>, ) -> impl Iterator<Item = Cx::Ty> + ExactSizeIterator + Captures<'a> { - self.mcx.tycx.ctor_sub_tys(ctor, self.ty) + self.cx.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()) } } @@ -1089,7 +1098,7 @@ impl<'p, Cx: TypeCx> Matrix<'p, Cx> { 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); } @@ -1198,6 +1207,7 @@ 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(Debug)] struct WitnessStack<Cx: TypeCx>(Vec<WitnessPat<Cx>>); impl<Cx: TypeCx> Clone for WitnessStack<Cx> { @@ -1206,12 +1216,6 @@ impl<Cx: TypeCx> Clone for WitnessStack<Cx> { } } -impl<Cx: TypeCx> fmt::Debug for WitnessStack<Cx> { - fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result { - fmt.debug_tuple("WitnessStack").field(&self.0).finish() - } -} - impl<Cx: TypeCx> WitnessStack<Cx> { /// Asserts that the witness contains a single pattern, and returns it. fn single_pattern(self) -> WitnessPat<Cx> { @@ -1240,7 +1244,7 @@ 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.clone()); self.0.push(pat); @@ -1256,6 +1260,7 @@ 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(Debug)] struct WitnessMatrix<Cx: TypeCx>(Vec<WitnessStack<Cx>>); impl<Cx: TypeCx> Clone for WitnessMatrix<Cx> { @@ -1264,12 +1269,6 @@ impl<Cx: TypeCx> Clone for WitnessMatrix<Cx> { } } -impl<Cx: TypeCx> fmt::Debug for WitnessMatrix<Cx> { - fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result { - fmt.debug_tuple("WitnessMatrix").field(&self.0).finish() - } -} - impl<Cx: TypeCx> WitnessMatrix<Cx> { /// New matrix with no witnesses. fn empty() -> Self { @@ -1315,20 +1314,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); @@ -1362,7 +1361,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>, @@ -1435,7 +1434,7 @@ fn collect_overlapping_range_endpoints<'p, Cx: TypeCx>( /// This is all explained at the top of the file. #[instrument(level = "debug", skip(mcx, is_top_level), 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> { @@ -1469,7 +1468,7 @@ fn compute_exhaustiveness_and_usefulness<'a, 'p, Cx: TypeCx>( }; debug!("ty: {ty:?}"); - let pcx = &PlaceCtxt { mcx, ty: &ty }; + let pcx = &PlaceCtxt { cx: mcx.tycx, ty: &ty }; let ctors_for_ty = pcx.ctors_for_ty()?; // Whether the place/column we are inspecting is known to contain valid data. @@ -1592,13 +1591,14 @@ 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)?; |