diff options
Diffstat (limited to 'compiler/rustc_pattern_analysis/src')
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/constructor.rs | 34 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/lib.rs | 94 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/lints.rs | 165 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/pat.rs | 106 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/rustc.rs | 56 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/usefulness.rs | 269 |
6 files changed, 419 insertions, 305 deletions
diff --git a/compiler/rustc_pattern_analysis/src/constructor.rs b/compiler/rustc_pattern_analysis/src/constructor.rs index 15ff4ceb5b3..eba71a23435 100644 --- a/compiler/rustc_pattern_analysis/src/constructor.rs +++ b/compiler/rustc_pattern_analysis/src/constructor.rs @@ -155,13 +155,13 @@ use std::iter::once; use smallvec::SmallVec; use rustc_apfloat::ieee::{DoubleS, IeeeFloat, SingleS}; -use rustc_index::bit_set::{BitSet, GrowableBitSet}; -use rustc_index::IndexVec; +use rustc_index::bit_set::GrowableBitSet; use self::Constructor::*; use self::MaybeInfiniteInt::*; use self::SliceKind::*; +use crate::index; use crate::usefulness::PlaceCtxt; use crate::TypeCx; @@ -718,7 +718,7 @@ 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 { + pub(crate) fn arity(&self, pcx: &PlaceCtxt<'_, Cx>) -> usize { pcx.ctor_arity(self) } @@ -727,7 +727,7 @@ 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<'p>(&self, pcx: &PlaceCtxt<'_, 'p, Cx>, other: &Self) -> bool { + pub(crate) fn is_covered_by(&self, pcx: &PlaceCtxt<'_, Cx>, other: &Self) -> bool { match (self, other) { (Wildcard, _) => pcx .mcx @@ -804,7 +804,10 @@ pub enum ConstructorSet<Cx: TypeCx> { Struct { empty: bool }, /// This type has the following list of constructors. If `variants` is empty and /// `non_exhaustive` is false, don't use this; use `NoConstructors` instead. - Variants { variants: IndexVec<Cx::VariantIdx, VariantVisibility>, non_exhaustive: bool }, + Variants { + variants: index::IdxContainer<Cx::VariantIdx, VariantVisibility>, + non_exhaustive: bool, + }, /// The type is `&T`. Ref, /// The type is a union. @@ -858,12 +861,14 @@ impl<Cx: TypeCx> ConstructorSet<Cx> { /// any) are missing; 2/ split constructors to handle non-trivial intersections e.g. on ranges /// or slices. This can get subtle; see [`SplitConstructorSet`] for details of this operation /// and its invariants. - #[instrument(level = "debug", skip(self, pcx, ctors), ret)] + #[instrument(level = "debug", skip(self, ctors), ret)] pub(crate) fn split<'a>( &self, - pcx: &PlaceCtxt<'a, '_, Cx>, ctors: impl Iterator<Item = &'a Constructor<Cx>> + Clone, - ) -> SplitConstructorSet<Cx> { + ) -> SplitConstructorSet<Cx> + where + Cx: 'a, + { let mut present: SmallVec<[_; 1]> = SmallVec::new(); // Empty constructors found missing. let mut missing_empty = Vec::new(); @@ -904,7 +909,7 @@ impl<Cx: TypeCx> ConstructorSet<Cx> { } } ConstructorSet::Variants { variants, non_exhaustive } => { - let mut seen_set: BitSet<_> = BitSet::new_empty(variants.len()); + let mut seen_set = index::IdxSet::new_empty(variants.len()); for idx in seen.iter().map(|c| c.as_variant().unwrap()) { seen_set.insert(idx); } @@ -1003,17 +1008,6 @@ impl<Cx: TypeCx> ConstructorSet<Cx> { } } - // We have now grouped all the constructors into 3 buckets: present, missing, missing_empty. - // In the absence of the `exhaustive_patterns` feature however, we don't count nested empty - // types as empty. Only non-nested `!` or `enum Foo {}` are considered empty. - if !pcx.mcx.tycx.is_exhaustive_patterns_feature_on() - && !(pcx.is_scrutinee && matches!(self, Self::NoConstructors)) - { - // Treat all missing constructors as nonempty. - // This clears `missing_empty`. - missing.append(&mut missing_empty); - } - SplitConstructorSet { present, missing, missing_empty } } } diff --git a/compiler/rustc_pattern_analysis/src/lib.rs b/compiler/rustc_pattern_analysis/src/lib.rs index 8ea8dd61ab4..21fa8e68d82 100644 --- a/compiler/rustc_pattern_analysis/src/lib.rs +++ b/compiler/rustc_pattern_analysis/src/lib.rs @@ -21,28 +21,59 @@ rustc_fluent_macro::fluent_messages! { "../messages.ftl" } use std::fmt; -use rustc_index::Idx; +#[cfg(feature = "rustc")] +pub mod index { + // Faster version when the indices of variants are `0..variants.len()`. + pub use rustc_index::bit_set::BitSet as IdxSet; + pub use rustc_index::Idx; + pub use rustc_index::IndexVec as IdxContainer; +} +#[cfg(not(feature = "rustc"))] +pub mod index { + // Slower version when the indices of variants are something else. + pub trait Idx: Copy + PartialEq + Eq + std::hash::Hash {} + impl<T: Copy + PartialEq + Eq + std::hash::Hash> Idx for T {} + + #[derive(Debug)] + pub struct IdxContainer<K, V>(pub rustc_hash::FxHashMap<K, V>); + impl<K: Idx, V> IdxContainer<K, V> { + pub fn len(&self) -> usize { + self.0.len() + } + pub fn iter_enumerated(&self) -> impl Iterator<Item = (K, &V)> { + self.0.iter().map(|(k, v)| (*k, v)) + } + } + + #[derive(Debug)] + pub struct IdxSet<T>(pub rustc_hash::FxHashSet<T>); + impl<T: Idx> IdxSet<T> { + pub fn new_empty(_len: usize) -> Self { + Self(Default::default()) + } + pub fn contains(&self, elem: T) -> bool { + self.0.contains(&elem) + } + pub fn insert(&mut self, elem: T) { + self.0.insert(elem); + } + } +} + #[cfg(feature = "rustc")] use rustc_middle::ty::Ty; +#[cfg(feature = "rustc")] +use rustc_span::ErrorGuaranteed; -use crate::constructor::{Constructor, ConstructorSet}; +use crate::constructor::{Constructor, ConstructorSet, IntRange}; #[cfg(feature = "rustc")] -use crate::lints::{ - lint_nonexhaustive_missing_variants, lint_overlapping_range_endpoints, PatternColumn, -}; +use crate::lints::{lint_nonexhaustive_missing_variants, PatternColumn}; use crate::pat::DeconstructedPat; #[cfg(feature = "rustc")] use crate::rustc::RustcMatchCheckCtxt; #[cfg(feature = "rustc")] use crate::usefulness::{compute_match_usefulness, ValidityConstraint}; -// It's not possible to only enable the `typed_arena` dependency when the `rustc` feature is off, so -// we use another feature instead. The crate won't compile if one of these isn't enabled. -#[cfg(feature = "rustc")] -pub(crate) use rustc_arena::TypedArena; -#[cfg(feature = "stable")] -pub(crate) use typed_arena::Arena as TypedArena; - pub trait Captures<'a> {} impl<'a, T: ?Sized> Captures<'a> for T {} @@ -52,8 +83,10 @@ impl<'a, T: ?Sized> Captures<'a> for T {} pub trait TypeCx: Sized + fmt::Debug { /// The type of a pattern. type Ty: Copy + Clone + fmt::Debug; // FIXME: remove Copy + /// Errors that can abort analysis. + type Error: fmt::Debug; /// The index of an enum variant. - type VariantIdx: Clone + Idx; + type VariantIdx: Clone + index::Idx + fmt::Debug; /// A string literal type StrLit: Clone + PartialEq + fmt::Debug; /// Extra data to store in a match arm. @@ -73,23 +106,32 @@ pub trait TypeCx: Sized + fmt::Debug { /// The set of all the constructors for `ty`. /// /// This must follow the invariants of `ConstructorSet` - fn ctors_for_ty(&self, ty: Self::Ty) -> ConstructorSet<Self>; + 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; /// Raise a bug. fn bug(&self, fmt: fmt::Arguments<'_>) -> !; + + /// 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>, + _overlaps_on: IntRange, + _overlaps_with: &[&DeconstructedPat<'_, Self>], + ) { + } } /// Context that provides information global to a match. #[derive(derivative::Derivative)] #[derivative(Clone(bound = ""), Copy(bound = ""))] -pub struct MatchCtxt<'a, 'p, Cx: TypeCx> { +pub struct MatchCtxt<'a, Cx: TypeCx> { /// The context for type information. pub tycx: &'a Cx, - /// An arena to store the wildcards we produce during analysis. - pub wildcard_arena: &'p TypedArena<DeconstructedPat<'p, Cx>>, } /// The arm of a match expression. @@ -109,25 +151,19 @@ pub fn analyze_match<'p, 'tcx>( tycx: &RustcMatchCheckCtxt<'p, 'tcx>, arms: &[rustc::MatchArm<'p, 'tcx>], scrut_ty: Ty<'tcx>, -) -> rustc::UsefulnessReport<'p, 'tcx> { - // Arena to store the extra wildcards we construct during analysis. - let wildcard_arena = tycx.pattern_arena; +) -> 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, wildcard_arena }; - - let report = compute_match_usefulness(cx, arms, scrut_ty, scrut_validity); - - let pat_column = PatternColumn::new(arms); + let cx = MatchCtxt { tycx }; - // Lint on ranges that overlap on their endpoints, which is likely a mistake. - lint_overlapping_range_endpoints(cx, &pat_column); + let report = compute_match_usefulness(cx, 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() { - lint_nonexhaustive_missing_variants(cx, arms, &pat_column, scrut_ty) + let pat_column = PatternColumn::new(arms); + lint_nonexhaustive_missing_variants(cx, arms, &pat_column, scrut_ty)?; } - report + Ok(report) } diff --git a/compiler/rustc_pattern_analysis/src/lints.rs b/compiler/rustc_pattern_analysis/src/lints.rs index f1237ecf83c..d9dbd8250ef 100644 --- a/compiler/rustc_pattern_analysis/src/lints.rs +++ b/compiler/rustc_pattern_analysis/src/lints.rs @@ -1,16 +1,8 @@ -use smallvec::SmallVec; - -use rustc_data_structures::captures::Captures; -use rustc_middle::ty; -use rustc_session::lint; use rustc_session::lint::builtin::NON_EXHAUSTIVE_OMITTED_PATTERNS; -use rustc_span::Span; +use rustc_span::ErrorGuaranteed; -use crate::constructor::{IntRange, MaybeInfiniteInt}; -use crate::errors::{ - NonExhaustiveOmittedPattern, NonExhaustiveOmittedPatternLintOnArm, Overlap, - OverlappingRangeEndpoints, Uncovered, -}; +use crate::errors::{NonExhaustiveOmittedPattern, NonExhaustiveOmittedPatternLintOnArm, Uncovered}; +use crate::pat::PatOrWild; use crate::rustc::{ Constructor, DeconstructedPat, MatchArm, MatchCtxt, PlaceCtxt, RevealedTy, RustcMatchCheckCtxt, SplitConstructorSet, WitnessPat, @@ -23,9 +15,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,32 +25,38 @@ 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()) } /// Do constructor splitting on the constructors of the column. - fn analyze_ctors(&self, pcx: &PlaceCtxt<'_, 'p, 'tcx>) -> SplitConstructorSet<'p, 'tcx> { + fn analyze_ctors( + &self, + pcx: &PlaceCtxt<'_, 'p, 'tcx>, + ) -> Result<SplitConstructorSet<'p, 'tcx>, ErrorGuaranteed> { let column_ctors = self.patterns.iter().map(|p| p.ctor()); - pcx.ctors_for_ty().split(pcx, column_ctors) - } - - fn iter(&self) -> impl Iterator<Item = &'p DeconstructedPat<'p, 'tcx>> + Captures<'_> { - self.patterns.iter().copied() + 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 @@ -83,23 +81,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 } } @@ -110,18 +97,18 @@ impl<'p, 'tcx> PatternColumn<'p, 'tcx> { fn collect_nonexhaustive_missing_variants<'a, 'p, 'tcx>( cx: MatchCtxt<'a, 'p, 'tcx>, column: &PatternColumn<'p, 'tcx>, -) -> Vec<WitnessPat<'p, 'tcx>> { +) -> Result<Vec<WitnessPat<'p, 'tcx>>, ErrorGuaranteed> { let Some(ty) = column.head_ty() else { - return Vec::new(); + return Ok(Vec::new()); }; let pcx = &PlaceCtxt::new_dummy(cx, ty); - let set = column.analyze_ctors(pcx); + let set = column.analyze_ctors(pcx)?; 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), // so for consistency we refuse to handle the top-level case, where we could handle it. - return vec![]; + return Ok(Vec::new()); } let mut witnesses = Vec::new(); @@ -141,7 +128,7 @@ fn collect_nonexhaustive_missing_variants<'a, 'p, 'tcx>( let wild_pat = WitnessPat::wild_from_ctor(pcx, ctor); 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); + let wits_for_col_i = collect_nonexhaustive_missing_variants(cx, col_i)?; // For each witness, we build a new pattern in the shape of `ctor(_, _, wit, _, _)`, // adding enough wildcards to match `arity`. for wit in wits_for_col_i { @@ -151,7 +138,7 @@ fn collect_nonexhaustive_missing_variants<'a, 'p, 'tcx>( } } } - witnesses + Ok(witnesses) } pub(crate) fn lint_nonexhaustive_missing_variants<'a, 'p, 'tcx>( @@ -159,13 +146,13 @@ pub(crate) fn lint_nonexhaustive_missing_variants<'a, 'p, 'tcx>( arms: &[MatchArm<'p, 'tcx>], pat_column: &PatternColumn<'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(cx, pat_column)?; if !witnesses.is_empty() { // Report that a match of a `non_exhaustive` enum marked with `non_exhaustive_omitted_patterns` // is not exhaustive enough. @@ -204,79 +191,5 @@ pub(crate) fn lint_nonexhaustive_missing_variants<'a, 'p, 'tcx>( } } } -} - -/// Traverse the patterns to warn the user about ranges that overlap on their endpoints. -#[instrument(level = "debug", skip(cx))] -pub(crate) fn lint_overlapping_range_endpoints<'a, 'p, 'tcx>( - cx: MatchCtxt<'a, 'p, 'tcx>, - column: &PatternColumn<'p, 'tcx>, -) { - let Some(ty) = column.head_ty() else { - return; - }; - let pcx = &PlaceCtxt::new_dummy(cx, ty); - let rcx: &RustcMatchCheckCtxt<'_, '_> = cx.tycx; - - let set = column.analyze_ctors(pcx); - - if matches!(ty.kind(), ty::Char | ty::Int(_) | ty::Uint(_)) { - let emit_lint = |overlap: &IntRange, this_span: Span, overlapped_spans: &[Span]| { - let overlap_as_pat = rcx.hoist_pat_range(overlap, ty); - let overlaps: Vec<_> = overlapped_spans - .iter() - .copied() - .map(|span| Overlap { range: overlap_as_pat.clone(), span }) - .collect(); - rcx.tcx.emit_spanned_lint( - lint::builtin::OVERLAPPING_RANGE_ENDPOINTS, - rcx.match_lint_level, - this_span, - OverlappingRangeEndpoints { overlap: overlaps, range: this_span }, - ); - }; - - // If two ranges overlapped, the split set will contain their intersection as a singleton. - let split_int_ranges = set.present.iter().filter_map(|c| c.as_int_range()); - for overlap_range in split_int_ranges.clone() { - if overlap_range.is_singleton() { - let overlap: MaybeInfiniteInt = overlap_range.lo; - // Ranges that look like `lo..=overlap`. - let mut prefixes: SmallVec<[_; 1]> = Default::default(); - // Ranges that look like `overlap..=hi`. - let mut suffixes: SmallVec<[_; 1]> = Default::default(); - // Iterate on patterns that contained `overlap`. - for pat in column.iter() { - let Constructor::IntRange(this_range) = pat.ctor() else { continue }; - let this_span = pat.data().unwrap().span; - if this_range.is_singleton() { - // Don't lint when one of the ranges is a singleton. - continue; - } - if this_range.lo == overlap { - // `this_range` looks like `overlap..=this_range.hi`; it overlaps with any - // ranges that look like `lo..=overlap`. - if !prefixes.is_empty() { - emit_lint(overlap_range, this_span, &prefixes); - } - suffixes.push(this_span) - } else if this_range.hi == overlap.plus_one() { - // `this_range` looks like `this_range.lo..=overlap`; it overlaps with any - // ranges that look like `overlap..=hi`. - if !suffixes.is_empty() { - emit_lint(overlap_range, this_span, &suffixes); - } - prefixes.push(this_span) - } - } - } - } - } else { - // Recurse into the fields. - for ctor in set.present { - for col in column.specialize(pcx, &ctor) { - lint_overlapping_range_endpoints(cx, &col); - } - } - } + Ok(()) } diff --git a/compiler/rustc_pattern_analysis/src/pat.rs b/compiler/rustc_pattern_analysis/src/pat.rs index 4438d20a357..75fe59edf88 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)] @@ -182,7 +240,7 @@ 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 { + 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) diff --git a/compiler/rustc_pattern_analysis/src/rustc.rs b/compiler/rustc_pattern_analysis/src/rustc.rs index b6f67b7c56f..87e70d68c1b 100644 --- a/compiler/rustc_pattern_analysis/src/rustc.rs +++ b/compiler/rustc_pattern_analysis/src/rustc.rs @@ -1,3 +1,4 @@ +use smallvec::SmallVec; use std::fmt; use std::iter::once; @@ -5,22 +6,21 @@ use rustc_arena::{DroplessArena, TypedArena}; use rustc_data_structures::captures::Captures; use rustc_hir::def_id::DefId; use rustc_hir::HirId; -use rustc_index::Idx; -use rustc_index::IndexVec; +use rustc_index::{Idx, IndexVec}; use rustc_middle::middle::stability::EvalResult; use rustc_middle::mir::interpret::Scalar; use rustc_middle::mir::{self, Const}; use rustc_middle::thir::{FieldPat, Pat, PatKind, PatRange, PatRangeBoundary}; use rustc_middle::ty::layout::IntegerExt; -use rustc_middle::ty::{self, OpaqueTypeKey, Ty, TyCtxt, VariantDef}; -use rustc_span::{Span, DUMMY_SP}; +use rustc_middle::ty::{self, OpaqueTypeKey, Ty, TyCtxt, TypeVisitableExt, VariantDef}; +use rustc_session::lint; +use rustc_span::{ErrorGuaranteed, Span, DUMMY_SP}; use rustc_target::abi::{FieldIdx, Integer, VariantIdx, FIRST_VARIANT}; -use smallvec::SmallVec; use crate::constructor::{ IntRange, MaybeInfiniteInt, OpaqueId, RangeEnd, Slice, SliceKind, VariantVisibility, }; -use crate::TypeCx; +use crate::{errors, TypeCx}; use crate::constructor::Constructor::*; @@ -31,9 +31,9 @@ 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, '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, 'p, RustcMatchCheckCtxt<'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>>; @@ -76,7 +76,9 @@ 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. pub match_lint_level: HirId, @@ -302,7 +304,10 @@ impl<'p, 'tcx> RustcMatchCheckCtxt<'p, 'tcx> { /// /// See [`crate::constructor`] for considerations of emptiness. #[instrument(level = "debug", skip(self), ret)] - pub fn ctors_for_ty(&self, ty: RevealedTy<'tcx>) -> ConstructorSet<'p, 'tcx> { + pub fn ctors_for_ty( + &self, + ty: RevealedTy<'tcx>, + ) -> Result<ConstructorSet<'p, 'tcx>, ErrorGuaranteed> { let cx = self; let make_uint_range = |start, end| { IntRange::from_range( @@ -311,9 +316,11 @@ impl<'p, 'tcx> RustcMatchCheckCtxt<'p, 'tcx> { RangeEnd::Included, ) }; + // Abort on type error. + ty.error_reported()?; // This determines the set of all possible constructors for the type `ty`. For numbers, // arrays and slices we use ranges and variable-length slices when appropriate. - match ty.kind() { + Ok(match ty.kind() { ty::Bool => ConstructorSet::Bool, ty::Char => { // The valid Unicode Scalar Value ranges. @@ -423,7 +430,7 @@ impl<'p, 'tcx> RustcMatchCheckCtxt<'p, 'tcx> { ty::CoroutineWitness(_, _) | ty::Bound(_, _) | ty::Placeholder(_) | ty::Infer(_) => { bug!("Encountered unexpected type in `ConstructorSet::for_ty`: {ty:?}") } - } + }) } pub(crate) fn lower_pat_range_bdy( @@ -944,6 +951,7 @@ impl<'p, 'tcx> RustcMatchCheckCtxt<'p, 'tcx> { impl<'p, 'tcx> TypeCx for RustcMatchCheckCtxt<'p, 'tcx> { type Ty = RevealedTy<'tcx>; + type Error = ErrorGuaranteed; type VariantIdx = VariantIdx; type StrLit = Const<'tcx>; type ArmData = HirId; @@ -963,7 +971,10 @@ impl<'p, 'tcx> TypeCx for RustcMatchCheckCtxt<'p, 'tcx> { ) -> &[Self::Ty] { self.ctor_sub_tys(ctor, ty) } - fn ctors_for_ty(&self, ty: Self::Ty) -> crate::constructor::ConstructorSet<Self> { + fn ctors_for_ty( + &self, + ty: Self::Ty, + ) -> Result<crate::constructor::ConstructorSet<Self>, Self::Error> { self.ctors_for_ty(ty) } @@ -976,6 +987,27 @@ impl<'p, 'tcx> TypeCx for RustcMatchCheckCtxt<'p, 'tcx> { fn bug(&self, fmt: fmt::Arguments<'_>) -> ! { span_bug!(self.scrut_span, "{}", fmt) } + + fn lint_overlapping_range_endpoints( + &self, + pat: &crate::pat::DeconstructedPat<'_, Self>, + overlaps_on: IntRange, + overlaps_with: &[&crate::pat::DeconstructedPat<'_, Self>], + ) { + 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( + lint::builtin::OVERLAPPING_RANGE_ENDPOINTS, + self.match_lint_level, + pat_span, + errors::OverlappingRangeEndpoints { overlap: overlaps, range: pat_span }, + ); + } } /// Recursively expand this pattern into its subpatterns. Only useful for or-patterns. diff --git a/compiler/rustc_pattern_analysis/src/usefulness.rs b/compiler/rustc_pattern_analysis/src/usefulness.rs index 16bf709881b..dac354a1c52 100644 --- a/compiler/rustc_pattern_analysis/src/usefulness.rs +++ b/compiler/rustc_pattern_analysis/src/usefulness.rs @@ -712,11 +712,12 @@ //! I (Nadrieril) prefer to put new tests in `ui/pattern/usefulness` unless there's a specific //! reason not to, for example if they crucially depend on a particular feature like `or_patterns`. +use rustc_index::bit_set::BitSet; use smallvec::{smallvec, SmallVec}; use std::fmt; -use crate::constructor::{Constructor, ConstructorSet}; -use crate::pat::{DeconstructedPat, WitnessPat}; +use crate::constructor::{Constructor, ConstructorSet, IntRange}; +use crate::pat::{DeconstructedPat, PatOrWild, WitnessPat}; use crate::{Captures, MatchArm, MatchCtxt, TypeCx}; use self::ValidityConstraint::*; @@ -731,20 +732,18 @@ pub fn ensure_sufficient_stack<R>(f: impl FnOnce() -> R) -> R { /// Context that provides information local to a place under investigation. #[derive(derivative::Derivative)] #[derivative(Debug(bound = ""), Clone(bound = ""), Copy(bound = ""))] -pub(crate) struct PlaceCtxt<'a, 'p, Cx: TypeCx> { +pub(crate) struct PlaceCtxt<'a, Cx: TypeCx> { #[derivative(Debug = "ignore")] - pub(crate) mcx: MatchCtxt<'a, 'p, Cx>, + pub(crate) mcx: MatchCtxt<'a, Cx>, /// Type of the place under investigation. pub(crate) ty: Cx::Ty, - /// Whether the place is the original scrutinee place, as opposed to a subplace of it. - pub(crate) is_scrutinee: bool, } -impl<'a, 'p, Cx: TypeCx> PlaceCtxt<'a, 'p, 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, 'p, Cx>, ty: Cx::Ty) -> Self { - PlaceCtxt { mcx, ty, is_scrutinee: false } + pub(crate) fn new_dummy(mcx: MatchCtxt<'a, Cx>, ty: Cx::Ty) -> Self { + PlaceCtxt { mcx, ty } } pub(crate) fn ctor_arity(&self, ctor: &Constructor<Cx>) -> usize { @@ -753,7 +752,7 @@ impl<'a, 'p, Cx: TypeCx> PlaceCtxt<'a, 'p, Cx> { pub(crate) fn ctor_sub_tys(&self, ctor: &Constructor<Cx>) -> &[Cx::Ty] { self.mcx.tycx.ctor_sub_tys(ctor, self.ty) } - pub(crate) fn ctors_for_ty(&self) -> ConstructorSet<Cx> { + pub(crate) fn ctors_for_ty(&self) -> Result<ConstructorSet<Cx>, Cx::Error> { self.mcx.tycx.ctors_for_ty(self.ty) } } @@ -767,9 +766,6 @@ impl<'a, 'p, Cx: TypeCx> PlaceCtxt<'a, 'p, Cx> { pub enum ValidityConstraint { ValidOnly, MaybeInvalid, - /// Option for backwards compatibility: the place is not known to be valid but we allow omitting - /// `useful && !reachable` arms anyway. - MaybeInvalidButAllowOmittingArms, } impl ValidityConstraint { @@ -777,20 +773,9 @@ impl ValidityConstraint { if is_valid_only { ValidOnly } else { MaybeInvalid } } - fn allow_omitting_side_effecting_arms(self) -> Self { - match self { - MaybeInvalid | MaybeInvalidButAllowOmittingArms => MaybeInvalidButAllowOmittingArms, - // There are no side-effecting empty arms here, nothing to do. - ValidOnly => ValidOnly, - } - } - fn is_known_valid(self) -> bool { matches!(self, ValidOnly) } - fn allows_omitting_empty_arms(self) -> bool { - matches!(self, ValidOnly | MaybeInvalidButAllowOmittingArms) - } /// If the place has validity given by `self` and we read that the value at the place has /// constructor `ctor`, this computes what we can assume about the validity of the constructor @@ -813,7 +798,7 @@ impl fmt::Display for ValidityConstraint { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { let s = match self { ValidOnly => "✓", - MaybeInvalid | MaybeInvalidButAllowOmittingArms => "?", + MaybeInvalid => "?", }; write!(f, "{s}") } @@ -827,7 +812,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 +821,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 +832,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 +854,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. @@ -915,6 +896,11 @@ struct MatrixRow<'p, Cx: TypeCx> { /// [`compute_exhaustiveness_and_usefulness`] if the arm is found to be useful. /// This is reset to `false` when specializing. useful: bool, + /// Tracks which rows above this one have an intersection with this one, i.e. such that there is + /// a value that matches both rows. + /// Note: Because of relevancy we may miss some intersections. The intersections we do find are + /// correct. + intersects: BitSet<usize>, } impl<'p, Cx: TypeCx> MatrixRow<'p, Cx> { @@ -926,11 +912,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() } @@ -942,6 +928,7 @@ impl<'p, Cx: TypeCx> MatrixRow<'p, Cx> { parent_row: self.parent_row, is_under_guard: self.is_under_guard, useful: false, + intersects: BitSet::new_empty(0), // Initialized in `Matrix::expand_and_push`. }) } @@ -949,17 +936,17 @@ 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, + intersects: BitSet::new_empty(0), // Initialized in `Matrix::expand_and_push`. } } } @@ -998,13 +985,15 @@ struct Matrix<'p, Cx: TypeCx> { impl<'p, Cx: TypeCx> Matrix<'p, Cx> { /// Pushes a new row to the matrix. If the row starts with an or-pattern, this recursively /// expands it. Internal method, prefer [`Matrix::new`]. - fn expand_and_push(&mut self, row: MatrixRow<'p, Cx>) { + fn expand_and_push(&mut self, mut row: MatrixRow<'p, Cx>) { if !row.is_empty() && row.head().is_or_pat() { // Expand nested or-patterns. - for new_row in row.expand_or_pat() { + for mut new_row in row.expand_or_pat() { + new_row.intersects = BitSet::new_empty(self.rows.len()); self.rows.push(new_row); } } else { + row.intersects = BitSet::new_empty(self.rows.len()); self.rows.push(row); } } @@ -1024,9 +1013,10 @@ impl<'p, Cx: TypeCx> Matrix<'p, Cx> { for (row_id, arm) in arms.iter().enumerate() { let v = MatrixRow { pats: PatStack::from_pattern(arm.pat), - parent_row: row_id, // dummy, we won't read it + parent_row: row_id, // dummy, we don't read it is_under_guard: arm.has_guard, useful: false, + intersects: BitSet::new_empty(0), // Initialized in `Matrix::expand_and_push`. }; matrix.expand_and_push(v); } @@ -1054,23 +1044,24 @@ 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()) } /// This computes `specialize(ctor, self)`. See top of the file for explanations. fn specialize_constructor( &self, - pcx: &PlaceCtxt<'_, '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(ctor.arity(pcx)) + .take(arity) .chain(self.place_validity[1..].iter().copied()) .collect(); let mut matrix = Matrix { @@ -1081,8 +1072,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); } } @@ -1220,7 +1210,7 @@ impl<Cx: TypeCx> WitnessStack<Cx> { /// pats: [(false, "foo"), _, true] /// result: [Enum::Variant { a: (false, "foo"), b: _ }, true] /// ``` - fn apply_constructor(&mut self, pcx: &PlaceCtxt<'_, '_, Cx>, ctor: &Constructor<Cx>) { + fn apply_constructor(&mut self, pcx: &PlaceCtxt<'_, Cx>, ctor: &Constructor<Cx>) { let len = self.0.len(); let arity = ctor.arity(pcx); let fields = self.0.drain((len - arity)..).rev().collect(); @@ -1271,7 +1261,7 @@ impl<Cx: TypeCx> WitnessMatrix<Cx> { /// Reverses specialization by `ctor`. See the section on `unspecialize` at the top of the file. fn apply_constructor( &mut self, - pcx: &PlaceCtxt<'_, '_, Cx>, + pcx: &PlaceCtxt<'_, Cx>, missing_ctors: &[Constructor<Cx>], ctor: &Constructor<Cx>, report_individual_missing_ctors: bool, @@ -1322,6 +1312,75 @@ impl<Cx: TypeCx> WitnessMatrix<Cx> { } } +/// Collect ranges that overlap like `lo..=overlap`/`overlap..=hi`. Must be called during +/// exhaustiveness checking, if we find a singleton range after constructor splitting. This reuses +/// row intersection information to only detect ranges that truly overlap. +/// +/// If two ranges overlapped, the split set will contain their intersection as a singleton. +/// Specialization will then select rows that match the overlap, and exhaustiveness will compute +/// which rows have an intersection that includes the overlap. That gives us all the info we need to +/// compute overlapping ranges without false positives. +/// +/// 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>, + overlap_range: IntRange, + matrix: &Matrix<'p, Cx>, + specialized_matrix: &Matrix<'p, Cx>, +) { + let overlap = overlap_range.lo; + // Ranges that look like `lo..=overlap`. + let mut prefixes: SmallVec<[_; 1]> = Default::default(); + // Ranges that look like `overlap..=hi`. + let mut suffixes: SmallVec<[_; 1]> = Default::default(); + // Iterate on patterns that contained `overlap`. We iterate on `specialized_matrix` which + // contains only rows that matched the current `ctor` as well as accurate intersection + // information. It doesn't contain the column that contains the range; that can be found in + // `matrix`. + for (child_row_id, child_row) in specialized_matrix.rows().enumerate() { + let PatOrWild::Pat(pat) = matrix.rows[child_row.parent_row].head() else { continue }; + let Constructor::IntRange(this_range) = pat.ctor() else { continue }; + // Don't lint when one of the ranges is a singleton. + if this_range.is_singleton() { + continue; + } + if this_range.lo == overlap { + // `this_range` looks like `overlap..=this_range.hi`; it overlaps with any + // ranges that look like `lo..=overlap`. + if !prefixes.is_empty() { + let overlaps_with: Vec<_> = prefixes + .iter() + .filter(|&&(other_child_row_id, _)| { + child_row.intersects.contains(other_child_row_id) + }) + .map(|&(_, pat)| pat) + .collect(); + if !overlaps_with.is_empty() { + mcx.tycx.lint_overlapping_range_endpoints(pat, overlap_range, &overlaps_with); + } + } + suffixes.push((child_row_id, pat)) + } else if this_range.hi == overlap.plus_one() { + // `this_range` looks like `this_range.lo..=overlap`; it overlaps with any + // ranges that look like `overlap..=hi`. + if !suffixes.is_empty() { + let overlaps_with: Vec<_> = suffixes + .iter() + .filter(|&&(other_child_row_id, _)| { + child_row.intersects.contains(other_child_row_id) + }) + .map(|&(_, pat)| pat) + .collect(); + if !overlaps_with.is_empty() { + mcx.tycx.lint_overlapping_range_endpoints(pat, overlap_range, &overlaps_with); + } + } + prefixes.push((child_row_id, pat)) + } + } +} + /// The core of the algorithm. /// /// This recursively computes witnesses of the non-exhaustiveness of `matrix` (if any). Also tracks @@ -1338,77 +1397,78 @@ impl<Cx: TypeCx> WitnessMatrix<Cx> { /// 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, 'p, Cx>, + mcx: MatchCtxt<'a, Cx>, matrix: &mut Matrix<'p, Cx>, is_top_level: bool, -) -> WitnessMatrix<Cx> { +) -> Result<WitnessMatrix<Cx>, Cx::Error> { debug_assert!(matrix.rows().all(|r| r.len() == matrix.column_count())); if !matrix.wildcard_row_is_relevant && matrix.rows().all(|r| !r.pats.relevant) { // Here we know that nothing will contribute further to exhaustiveness or usefulness. This // is purely an optimization: skipping this check doesn't affect correctness. See the top of // the file for details. - return WitnessMatrix::empty(); + return Ok(WitnessMatrix::empty()); } let Some(ty) = matrix.head_ty() else { // The base case: there are no columns in the matrix. We are morally pattern-matching on (). // A row is useful iff it has no (unguarded) rows above it. - for row in matrix.rows_mut() { - // All rows are useful until they're not. - row.useful = true; - // When there's an unguarded row, the match is exhaustive and any subsequent row is not - // useful. - if !row.is_under_guard { - return WitnessMatrix::empty(); - } + let mut useful = true; // Whether the next row is useful. + for (i, row) in matrix.rows_mut().enumerate() { + row.useful = useful; + row.intersects.insert_range(0..i); + // The next rows stays useful if this one is under a guard. + useful &= row.is_under_guard; } - // No (unguarded) rows, so the match is not exhaustive. We return a new witness unless - // irrelevant. - return if matrix.wildcard_row_is_relevant { - WitnessMatrix::unit_witness() + return if useful && matrix.wildcard_row_is_relevant { + // The wildcard row is useful; the match is non-exhaustive. + Ok(WitnessMatrix::unit_witness()) } else { - // We choose to not report anything here; see at the top for details. - WitnessMatrix::empty() + // Either the match is exhaustive, or we choose not to report anything because of + // relevancy. See at the top for details. + Ok(WitnessMatrix::empty()) }; }; debug!("ty: {ty:?}"); - let pcx = &PlaceCtxt { mcx, ty, is_scrutinee: is_top_level }; + let pcx = &PlaceCtxt { mcx, 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]; - // For backwards compability we allow omitting some empty arms that we ideally shouldn't. - let place_validity = place_validity.allow_omitting_side_effecting_arms(); + // 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; // Analyze the constructors present in this column. let ctors = matrix.heads().map(|p| p.ctor()); - let ctors_for_ty = pcx.ctors_for_ty(); - let is_integers = matches!(ctors_for_ty, ConstructorSet::Integers { .. }); // For diagnostics. - let split_set = ctors_for_ty.split(pcx, ctors); + let mut split_set = ctors_for_ty.split(ctors); let all_missing = split_set.present.is_empty(); - // Build the set of constructors we will specialize with. It must cover the whole type. + // We need to iterate over a full set of constructors, so we add `Missing` to represent the + // missing ones. This is explained under "Constructor Splitting" at the top of this file. let mut split_ctors = split_set.present; - if !split_set.missing.is_empty() { - // We need to iterate over a full set of constructors, so we add `Missing` to represent the - // missing ones. This is explained under "Constructor Splitting" at the top of this file. - split_ctors.push(Constructor::Missing); - } else if !split_set.missing_empty.is_empty() && !place_validity.is_known_valid() { - // The missing empty constructors are reachable if the place can contain invalid data. + if !(split_set.missing.is_empty() + && (split_set.missing_empty.is_empty() || empty_arms_are_unreachable)) + { 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; // Which constructors are considered missing. We ensure that `!missing_ctors.is_empty() => - // split_ctors.contains(Missing)`. The converse usually holds except in the - // `MaybeInvalidButAllowOmittingArms` backwards-compatibility case. + // split_ctors.contains(Missing)`. The converse usually holds except when + // `!place_validity.is_known_valid()`. let mut missing_ctors = split_set.missing; - if !place_validity.allows_omitting_empty_arms() { - missing_ctors.extend(split_set.missing_empty); + if !can_omit_empty_arms { + missing_ctors.append(&mut split_set.missing_empty); } let mut ret = WitnessMatrix::empty(); @@ -1422,17 +1482,36 @@ fn compute_exhaustiveness_and_usefulness<'a, 'p, Cx: TypeCx>( 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) - }); + })?; // Transform witnesses for `spec_matrix` into witnesses for `matrix`. witnesses.apply_constructor(pcx, &missing_ctors, &ctor, report_individual_missing_ctors); // Accumulate the found witnesses. ret.extend(witnesses); - // A parent row is useful if any of its children is. for child_row in spec_matrix.rows() { - let parent_row = &mut matrix.rows[child_row.parent_row]; - parent_row.useful = parent_row.useful || child_row.useful; + let parent_row_id = child_row.parent_row; + let parent_row = &mut matrix.rows[parent_row_id]; + // A parent row is useful if any of its children is. + parent_row.useful |= child_row.useful; + for child_intersection in child_row.intersects.iter() { + // Convert the intersecting ids into ids for the parent matrix. + let parent_intersection = spec_matrix.rows[child_intersection].parent_row; + // Note: self-intersection can happen with or-patterns. + if parent_intersection != parent_row_id { + parent_row.intersects.insert(parent_intersection); + } + } + } + + // Detect ranges that overlap on their endpoints. + if let Constructor::IntRange(overlap_range) = ctor { + if overlap_range.is_singleton() + && spec_matrix.rows.len() >= 2 + && spec_matrix.rows.iter().any(|row| !row.intersects.is_empty()) + { + collect_overlapping_range_endpoints(mcx, overlap_range, matrix, &spec_matrix); + } } } @@ -1443,7 +1522,7 @@ fn compute_exhaustiveness_and_usefulness<'a, 'p, Cx: TypeCx>( } } - ret + Ok(ret) } /// Indicates whether or not a given arm is useful. @@ -1470,13 +1549,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")] pub fn compute_match_usefulness<'p, Cx: TypeCx>( - cx: MatchCtxt<'_, 'p, Cx>, + cx: MatchCtxt<'_, Cx>, arms: &[MatchArm<'p, Cx>], scrut_ty: Cx::Ty, scrut_validity: ValidityConstraint, -) -> UsefulnessReport<'p, Cx> { +) -> Result<UsefulnessReport<'p, Cx>, Cx::Error> { 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, true)?; let non_exhaustiveness_witnesses: Vec<_> = non_exhaustiveness_witnesses.single_column(); let arm_usefulness: Vec<_> = arms @@ -1493,5 +1573,6 @@ pub fn compute_match_usefulness<'p, Cx: TypeCx>( (arm, usefulness) }) .collect(); - UsefulnessReport { arm_usefulness, non_exhaustiveness_witnesses } + + Ok(UsefulnessReport { arm_usefulness, non_exhaustiveness_witnesses }) } |