diff options
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/lints.rs | 48 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/pat.rs | 104 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/usefulness.rs | 37 |
3 files changed, 119 insertions, 70 deletions
diff --git a/compiler/rustc_pattern_analysis/src/lints.rs b/compiler/rustc_pattern_analysis/src/lints.rs index f1237ecf83c..3af09a0b174 100644 --- a/compiler/rustc_pattern_analysis/src/lints.rs +++ b/compiler/rustc_pattern_analysis/src/lints.rs @@ -11,6 +11,7 @@ use crate::errors::{ NonExhaustiveOmittedPattern, NonExhaustiveOmittedPatternLintOnArm, Overlap, OverlappingRangeEndpoints, Uncovered, }; +use crate::pat::PatOrWild; use crate::rustc::{ Constructor, DeconstructedPat, MatchArm, MatchCtxt, PlaceCtxt, RevealedTy, RustcMatchCheckCtxt, SplitConstructorSet, WitnessPat, @@ -23,9 +24,9 @@ use crate::rustc::{ /// 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. `specialize` takes care to expand them. +/// This must not contain an or-pattern. `expand_and_push` takes care to expand them. /// -/// This is not used in the main algorithm; only in lints. +/// 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>>, @@ -33,20 +34,26 @@ pub(crate) struct PatternColumn<'p, 'tcx> { impl<'p, 'tcx> PatternColumn<'p, 'tcx> { pub(crate) fn new(arms: &[MatchArm<'p, 'tcx>]) -> Self { - let mut patterns = Vec::with_capacity(arms.len()); + let patterns = Vec::with_capacity(arms.len()); + let mut column = PatternColumn { patterns }; for arm in arms { - if arm.pat.is_or_pat() { - patterns.extend(arm.pat.flatten_or_pat()) - } else { - patterns.push(arm.pat) - } + column.expand_and_push(PatOrWild::Pat(arm.pat)); } - Self { patterns } + column } - - fn is_empty(&self) -> bool { - self.patterns.is_empty() + /// 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()) } @@ -83,23 +90,12 @@ impl<'p, 'tcx> PatternColumn<'p, 'tcx> { (0..arity).map(|_| Self { patterns: Vec::new() }).collect(); let relevant_patterns = self.patterns.iter().filter(|pat| ctor.is_covered_by(pcx, pat.ctor())); - let ctor_sub_tys = pcx.ctor_sub_tys(ctor); for pat in relevant_patterns { - let specialized = pat.specialize(pcx, ctor, ctor_sub_tys); - for (subpat, column) in specialized.iter().zip(&mut specialized_columns) { - if subpat.is_or_pat() { - column.patterns.extend(subpat.flatten_or_pat()) - } else { - column.patterns.push(subpat) - } + let specialized = pat.specialize(ctor, arity); + for (subpat, column) in specialized.into_iter().zip(&mut specialized_columns) { + column.expand_and_push(subpat); } } - - assert!( - !specialized_columns[0].is_empty(), - "ctor {ctor:?} was listed as present but isn't; - there is an inconsistency between `Constructor::is_covered_by` and `ConstructorSet::split`" - ); specialized_columns } } diff --git a/compiler/rustc_pattern_analysis/src/pat.rs b/compiler/rustc_pattern_analysis/src/pat.rs index 4438d20a357..2f5dc241cb7 100644 --- a/compiler/rustc_pattern_analysis/src/pat.rs +++ b/compiler/rustc_pattern_analysis/src/pat.rs @@ -50,14 +50,6 @@ impl<'p, Cx: TypeCx> DeconstructedPat<'p, Cx> { pub(crate) fn is_or_pat(&self) -> bool { matches!(self.ctor, Or) } - /// Expand this (possibly-nested) or-pattern into its alternatives. - pub(crate) fn flatten_or_pat(&self) -> SmallVec<[&Self; 1]> { - if self.is_or_pat() { - self.iter_fields().flat_map(|p| p.flatten_or_pat()).collect() - } else { - smallvec![self] - } - } pub fn ctor(&self) -> &Constructor<Cx> { &self.ctor @@ -79,17 +71,10 @@ impl<'p, Cx: TypeCx> DeconstructedPat<'p, Cx> { /// `other_ctor` can be different from `self.ctor`, but must be covered by it. pub(crate) fn specialize( &self, - pcx: &PlaceCtxt<'_, 'p, Cx>, other_ctor: &Constructor<Cx>, - ctor_sub_tys: &[Cx::Ty], - ) -> SmallVec<[&'p DeconstructedPat<'p, Cx>; 2]> { - let wildcard_sub_tys = || { - ctor_sub_tys - .iter() - .map(|ty| DeconstructedPat::wildcard(*ty)) - .map(|pat| pcx.mcx.wildcard_arena.alloc(pat) as &_) - .collect() - }; + ctor_arity: usize, + ) -> SmallVec<[PatOrWild<'p, 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`. (Wildcard, _) => wildcard_sub_tys(), @@ -105,14 +90,15 @@ impl<'p, Cx: TypeCx> DeconstructedPat<'p, Cx> { // Fill in the fields from both ends. let new_arity = fields.len(); for i in 0..prefix { - fields[i] = &self.fields[i]; + fields[i] = PatOrWild::Pat(&self.fields[i]); } for i in 0..suffix { - fields[new_arity - 1 - i] = &self.fields[self.fields.len() - 1 - i]; + fields[new_arity - 1 - i] = + PatOrWild::Pat(&self.fields[self.fields.len() - 1 - i]); } fields } - _ => self.fields.iter().collect(), + _ => self.fields.iter().map(PatOrWild::Pat).collect(), } } @@ -153,14 +139,86 @@ impl<'p, Cx: TypeCx> DeconstructedPat<'p, Cx> { } } -/// This is mostly copied from the `Pat` impl. This is best effort and not good enough for a -/// `Display` impl. +/// This is best effort and not good enough for a `Display` impl. impl<'p, Cx: TypeCx> fmt::Debug for DeconstructedPat<'p, Cx> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { Cx::debug_pat(f, self) } } +/// Represents either a pattern obtained from user input or a wildcard constructed during the +/// 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>), +} + +impl<'p, Cx: TypeCx> PatOrWild<'p, Cx> { + pub(crate) fn as_pat(&self) -> Option<&'p DeconstructedPat<'p, Cx>> { + match self { + PatOrWild::Wild => None, + PatOrWild::Pat(pat) => Some(pat), + } + } + pub(crate) fn ctor(self) -> &'p Constructor<Cx> { + match self { + PatOrWild::Wild => &Wildcard, + PatOrWild::Pat(pat) => pat.ctor(), + } + } + + pub(crate) fn is_or_pat(&self) -> bool { + match self { + PatOrWild::Wild => false, + PatOrWild::Pat(pat) => pat.is_or_pat(), + } + } + + /// Expand this (possibly-nested) or-pattern into its alternatives. + pub(crate) fn flatten_or_pat(self) -> SmallVec<[Self; 1]> { + match self { + PatOrWild::Pat(pat) if pat.is_or_pat() => { + pat.iter_fields().flat_map(|p| PatOrWild::Pat(p).flatten_or_pat()).collect() + } + _ => smallvec![self], + } + } + + /// 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, + other_ctor: &Constructor<Cx>, + ctor_arity: usize, + ) -> SmallVec<[PatOrWild<'p, Cx>; 2]> { + match self { + PatOrWild::Wild => (0..ctor_arity).map(|_| PatOrWild::Wild).collect(), + PatOrWild::Pat(pat) => pat.specialize(other_ctor, ctor_arity), + } + } + + pub(crate) fn set_useful(&self) { + if let PatOrWild::Pat(pat) = self { + pat.set_useful() + } + } +} + +impl<'p, Cx: TypeCx> fmt::Debug for PatOrWild<'p, Cx> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + match self { + PatOrWild::Wild => write!(f, "_"), + PatOrWild::Pat(pat) => pat.fmt(f), + } + } +} + /// 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)] diff --git a/compiler/rustc_pattern_analysis/src/usefulness.rs b/compiler/rustc_pattern_analysis/src/usefulness.rs index 16bf709881b..ca6d8be2930 100644 --- a/compiler/rustc_pattern_analysis/src/usefulness.rs +++ b/compiler/rustc_pattern_analysis/src/usefulness.rs @@ -716,7 +716,7 @@ use smallvec::{smallvec, SmallVec}; use std::fmt; use crate::constructor::{Constructor, ConstructorSet}; -use crate::pat::{DeconstructedPat, WitnessPat}; +use crate::pat::{DeconstructedPat, PatOrWild, WitnessPat}; use crate::{Captures, MatchArm, MatchCtxt, TypeCx}; use self::ValidityConstraint::*; @@ -827,7 +827,7 @@ impl fmt::Display for ValidityConstraint { #[derivative(Clone(bound = ""))] struct PatStack<'p, Cx: TypeCx> { // Rows of len 1 are very common, which is why `SmallVec[_; 2]` works well. - pats: SmallVec<[&'p DeconstructedPat<'p, Cx>; 2]>, + pats: SmallVec<[PatOrWild<'p, Cx>; 2]>, /// Sometimes we know that as far as this row is concerned, the current case is already handled /// by a different, more general, case. When the case is irrelevant for all rows this allows us /// to skip a case entirely. This is purely an optimization. See at the top for details. @@ -836,7 +836,7 @@ struct PatStack<'p, Cx: TypeCx> { impl<'p, Cx: TypeCx> PatStack<'p, Cx> { fn from_pattern(pat: &'p DeconstructedPat<'p, Cx>) -> Self { - PatStack { pats: smallvec![pat], relevant: true } + PatStack { pats: smallvec![PatOrWild::Pat(pat)], relevant: true } } fn is_empty(&self) -> bool { @@ -847,14 +847,11 @@ impl<'p, Cx: TypeCx> PatStack<'p, Cx> { self.pats.len() } - fn head_opt(&self) -> Option<&'p DeconstructedPat<'p, Cx>> { - self.pats.first().copied() - } - fn head(&self) -> &'p DeconstructedPat<'p, Cx> { - self.head_opt().unwrap() + fn head(&self) -> PatOrWild<'p, Cx> { + self.pats[0] } - fn iter(&self) -> impl Iterator<Item = &'p DeconstructedPat<'p, Cx>> + Captures<'_> { + fn iter(&self) -> impl Iterator<Item = PatOrWild<'p, Cx>> + Captures<'_> { self.pats.iter().copied() } @@ -872,14 +869,13 @@ impl<'p, Cx: TypeCx> PatStack<'p, Cx> { /// Only call if `ctor.is_covered_by(self.head().ctor())` is true. fn pop_head_constructor( &self, - pcx: &PlaceCtxt<'_, 'p, Cx>, ctor: &Constructor<Cx>, - ctor_sub_tys: &[Cx::Ty], + ctor_arity: usize, ctor_is_relevant: bool, ) -> PatStack<'p, Cx> { // We pop the head pattern and push the new fields extracted from the arguments of // `self.head()`. - let mut new_pats = self.head().specialize(pcx, ctor, ctor_sub_tys); + let mut new_pats = self.head().specialize(ctor, ctor_arity); new_pats.extend_from_slice(&self.pats[1..]); // `ctor` is relevant for this row if it is the actual constructor of this row, or if the // row has a wildcard and `ctor` is relevant for wildcards. @@ -926,11 +922,11 @@ impl<'p, Cx: TypeCx> MatrixRow<'p, Cx> { self.pats.len() } - fn head(&self) -> &'p DeconstructedPat<'p, Cx> { + fn head(&self) -> PatOrWild<'p, Cx> { self.pats.head() } - fn iter(&self) -> impl Iterator<Item = &'p DeconstructedPat<'p, Cx>> + Captures<'_> { + fn iter(&self) -> impl Iterator<Item = PatOrWild<'p, Cx>> + Captures<'_> { self.pats.iter() } @@ -949,14 +945,13 @@ impl<'p, Cx: TypeCx> MatrixRow<'p, Cx> { /// Only call if `ctor.is_covered_by(self.head().ctor())` is true. fn pop_head_constructor( &self, - pcx: &PlaceCtxt<'_, 'p, Cx>, ctor: &Constructor<Cx>, - ctor_sub_tys: &[Cx::Ty], + ctor_arity: usize, ctor_is_relevant: bool, parent_row: usize, ) -> MatrixRow<'p, Cx> { MatrixRow { - pats: self.pats.pop_head_constructor(pcx, ctor, ctor_sub_tys, ctor_is_relevant), + pats: self.pats.pop_head_constructor(ctor, ctor_arity, ctor_is_relevant), parent_row, is_under_guard: self.is_under_guard, useful: false, @@ -1054,7 +1049,7 @@ impl<'p, Cx: TypeCx> Matrix<'p, Cx> { } /// Iterate over the first pattern of each row. - fn heads(&self) -> impl Iterator<Item = &'p DeconstructedPat<'p, Cx>> + Clone + Captures<'_> { + fn heads(&self) -> impl Iterator<Item = PatOrWild<'p, Cx>> + Clone + Captures<'_> { self.rows().map(|r| r.head()) } @@ -1066,11 +1061,12 @@ impl<'p, Cx: TypeCx> Matrix<'p, 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(ctor.arity(pcx)) + .take(arity) .chain(self.place_validity[1..].iter().copied()) .collect(); let mut matrix = Matrix { @@ -1081,8 +1077,7 @@ impl<'p, Cx: TypeCx> Matrix<'p, Cx> { }; for (i, row) in self.rows().enumerate() { if ctor.is_covered_by(pcx, row.head().ctor()) { - let new_row = - row.pop_head_constructor(pcx, ctor, ctor_sub_tys, ctor_is_relevant, i); + let new_row = row.pop_head_constructor(ctor, arity, ctor_is_relevant, i); matrix.expand_and_push(new_row); } } |