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 | 88 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/lints.rs | 99 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/pat.rs | 14 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/rustc.rs | 59 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/usefulness.rs | 224 |
6 files changed, 281 insertions, 237 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 b52643adcc9..4fd01b5e638 100644 --- a/compiler/rustc_pattern_analysis/src/lib.rs +++ b/compiler/rustc_pattern_analysis/src/lib.rs @@ -21,30 +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 {} @@ -53,11 +82,11 @@ impl<'a, T: ?Sized> Captures<'a> for T {} /// Most of the crate is parameterized on a type that implements this trait. pub trait TypeCx: Sized + fmt::Debug { /// The type of a pattern. - type Ty: Copy + Clone + fmt::Debug; // FIXME: remove Copy + type Ty: Clone + fmt::Debug; /// Errors that can abort analysis. type Error: fmt::Debug; /// The index of an enum variant. - 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. @@ -68,32 +97,41 @@ pub trait TypeCx: Sized + fmt::Debug { fn is_exhaustive_patterns_feature_on(&self) -> bool; /// The number of fields for this constructor. - fn ctor_arity(&self, ctor: &Constructor<Self>, ty: Self::Ty) -> usize; + fn ctor_arity(&self, ctor: &Constructor<Self>, ty: &Self::Ty) -> usize; /// The types of the fields for this constructor. The result must have a length of /// `ctor_arity()`. - fn ctor_sub_tys(&self, ctor: &Constructor<Self>, ty: Self::Ty) -> &[Self::Ty]; + fn ctor_sub_tys(&self, ctor: &Constructor<Self>, ty: &Self::Ty) -> &[Self::Ty]; /// The set of all the constructors for `ty`. /// /// This must follow the invariants of `ConstructorSet` - fn ctors_for_ty(&self, ty: Self::Ty) -> Result<ConstructorSet<Self>, Self::Error>; + fn ctors_for_ty(&self, ty: &Self::Ty) -> Result<ConstructorSet<Self>, Self::Error>; /// Best-effort `Debug` implementation. fn debug_pat(f: &mut fmt::Formatter<'_>, pat: &DeconstructedPat<'_, Self>) -> fmt::Result; /// 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. @@ -114,22 +152,16 @@ pub fn analyze_match<'p, 'tcx>( arms: &[rustc::MatchArm<'p, 'tcx>], scrut_ty: Ty<'tcx>, ) -> Result<rustc::UsefulnessReport<'p, 'tcx>, ErrorGuaranteed> { - // Arena to store the extra wildcards we construct during analysis. - let wildcard_arena = tycx.pattern_arena; 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 cx = MatchCtxt { tycx }; let report = compute_match_usefulness(cx, arms, scrut_ty, scrut_validity)?; - let pat_column = PatternColumn::new(arms); - - // Lint on ranges that overlap on their endpoints, which is likely a mistake. - lint_overlapping_range_endpoints(cx, &pat_column)?; - // Run the non_exhaustive_omitted_patterns lint. Only run on refutable patterns to avoid hitting // `if let`s. Only run if the match is exhaustive otherwise the error is redundant. if tycx.refutable && report.non_exhaustiveness_witnesses.is_empty() { + let pat_column = PatternColumn::new(arms); lint_nonexhaustive_missing_variants(cx, arms, &pat_column, scrut_ty)?; } diff --git a/compiler/rustc_pattern_analysis/src/lints.rs b/compiler/rustc_pattern_analysis/src/lints.rs index 52c9af85006..f9f065fbe8b 100644 --- a/compiler/rustc_pattern_analysis/src/lints.rs +++ b/compiler/rustc_pattern_analysis/src/lints.rs @@ -1,16 +1,7 @@ -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::{ErrorGuaranteed, 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, @@ -55,7 +46,7 @@ impl<'p, 'tcx> PatternColumn<'p, 'tcx> { } fn head_ty(&self) -> Option<RevealedTy<'tcx>> { - self.patterns.first().map(|pat| pat.ty()) + self.patterns.first().map(|pat| *pat.ty()) } /// Do constructor splitting on the constructors of the column. @@ -65,11 +56,7 @@ impl<'p, 'tcx> PatternColumn<'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(pcx, column_ctors)) - } - - fn iter(&self) -> impl Iterator<Item = &'p DeconstructedPat<'p, 'tcx>> + Captures<'_> { - self.patterns.iter().copied() + Ok(ctors_for_ty.split(column_ctors)) } /// Does specialization: given a constructor, this takes the patterns from the column that match @@ -114,7 +101,7 @@ fn collect_nonexhaustive_missing_variants<'a, 'p, 'tcx>( let Some(ty) = column.head_ty() else { return Ok(Vec::new()); }; - let pcx = &PlaceCtxt::new_dummy(cx, ty); + let pcx = &PlaceCtxt::new_dummy(cx, &ty); let set = column.analyze_ctors(pcx)?; if set.present.is_empty() { @@ -206,79 +193,3 @@ pub(crate) fn lint_nonexhaustive_missing_variants<'a, 'p, 'tcx>( } Ok(()) } - -/// 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>, -) -> Result<(), ErrorGuaranteed> { - let Some(ty) = column.head_ty() else { - return Ok(()); - }; - 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 2f5dc241cb7..8cd0ecb073c 100644 --- a/compiler/rustc_pattern_analysis/src/pat.rs +++ b/compiler/rustc_pattern_analysis/src/pat.rs @@ -54,8 +54,8 @@ impl<'p, Cx: TypeCx> DeconstructedPat<'p, Cx> { pub fn ctor(&self) -> &Constructor<Cx> { &self.ctor } - pub fn ty(&self) -> Cx::Ty { - self.ty + pub fn ty(&self) -> &Cx::Ty { + &self.ty } /// Returns the extra data stored in a pattern. Returns `None` if the pattern is a wildcard that /// does not correspond to a user-supplied pattern. @@ -240,17 +240,17 @@ 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) + let fields = field_tys.iter().cloned().map(|ty| Self::wildcard(ty)).collect(); + Self::new(ctor, fields, pcx.ty.clone()) } pub fn ctor(&self) -> &Constructor<Cx> { &self.ctor } - pub fn ty(&self) -> Cx::Ty { - self.ty + pub fn ty(&self) -> &Cx::Ty { + &self.ty } pub fn iter_fields(&self) -> impl Iterator<Item = &WitnessPat<Cx>> { diff --git a/compiler/rustc_pattern_analysis/src/rustc.rs b/compiler/rustc_pattern_analysis/src/rustc.rs index a8d1bece613..27b25802427 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,24 +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::TypeVisitableExt; -use rustc_middle::ty::{self, OpaqueTypeKey, Ty, TyCtxt, VariantDef}; -use rustc_span::ErrorGuaranteed; -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::*; @@ -33,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>>; @@ -78,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, @@ -766,7 +766,7 @@ impl<'p, 'tcx> RustcMatchCheckCtxt<'p, 'tcx> { let mut subpatterns = pat.iter_fields().map(|p| Box::new(cx.hoist_witness_pat(p))); let kind = match pat.ctor() { Bool(b) => PatKind::Constant { value: mir::Const::from_bool(cx.tcx, *b) }, - IntRange(range) => return self.hoist_pat_range(range, pat.ty()), + IntRange(range) => return self.hoist_pat_range(range, *pat.ty()), Struct | Variant(_) | UnionField => match pat.ty().kind() { ty::Tuple(..) => PatKind::Leaf { subpatterns: subpatterns @@ -785,7 +785,7 @@ impl<'p, 'tcx> RustcMatchCheckCtxt<'p, 'tcx> { RustcMatchCheckCtxt::variant_index_for_adt(&pat.ctor(), *adt_def); let variant = &adt_def.variant(variant_index); let subpatterns = cx - .list_variant_nonhidden_fields(pat.ty(), variant) + .list_variant_nonhidden_fields(*pat.ty(), variant) .zip(subpatterns) .map(|((field, _ty), pattern)| FieldPat { field, pattern }) .collect(); @@ -796,7 +796,7 @@ impl<'p, 'tcx> RustcMatchCheckCtxt<'p, 'tcx> { PatKind::Leaf { subpatterns } } } - _ => bug!("unexpected ctor for type {:?} {:?}", pat.ctor(), pat.ty()), + _ => bug!("unexpected ctor for type {:?} {:?}", pat.ctor(), *pat.ty()), }, // Note: given the expansion of `&str` patterns done in `expand_pattern`, we should // be careful to reconstruct the correct constant pattern here. However a string @@ -961,21 +961,21 @@ impl<'p, 'tcx> TypeCx for RustcMatchCheckCtxt<'p, 'tcx> { self.tcx.features().exhaustive_patterns } - fn ctor_arity(&self, ctor: &crate::constructor::Constructor<Self>, ty: Self::Ty) -> usize { - self.ctor_arity(ctor, ty) + fn ctor_arity(&self, ctor: &crate::constructor::Constructor<Self>, ty: &Self::Ty) -> usize { + self.ctor_arity(ctor, *ty) } fn ctor_sub_tys( &self, ctor: &crate::constructor::Constructor<Self>, - ty: Self::Ty, + ty: &Self::Ty, ) -> &[Self::Ty] { - self.ctor_sub_tys(ctor, ty) + self.ctor_sub_tys(ctor, *ty) } fn ctors_for_ty( &self, - ty: Self::Ty, + ty: &Self::Ty, ) -> Result<crate::constructor::ConstructorSet<Self>, Self::Error> { - self.ctors_for_ty(ty) + self.ctors_for_ty(*ty) } fn debug_pat( @@ -987,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 b4935d280e6..d7852a2b2cb 100644 --- a/compiler/rustc_pattern_analysis/src/usefulness.rs +++ b/compiler/rustc_pattern_analysis/src/usefulness.rs @@ -712,10 +712,11 @@ //! 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::constructor::{Constructor, ConstructorSet, IntRange}; use crate::pat::{DeconstructedPat, PatOrWild, WitnessPat}; use crate::{Captures, MatchArm, MatchCtxt, TypeCx}; @@ -731,20 +732,19 @@ 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, + #[derivative(Clone(clone_with = "Clone::clone"))] // See rust-derivative#90 + pub(crate) ty: &'a Cx::Ty, } -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: &'a Cx::Ty) -> Self { + PlaceCtxt { mcx, ty } } pub(crate) fn ctor_arity(&self, ctor: &Constructor<Cx>) -> usize { @@ -767,9 +767,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 +774,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 +799,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}") } @@ -911,6 +897,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> { @@ -938,6 +929,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`. }) } @@ -955,6 +947,7 @@ impl<'p, Cx: TypeCx> MatrixRow<'p, Cx> { parent_row, is_under_guard: self.is_under_guard, useful: false, + intersects: BitSet::new_empty(0), // Initialized in `Matrix::expand_and_push`. } } } @@ -993,13 +986,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); } } @@ -1019,17 +1014,18 @@ 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); } matrix } - fn head_ty(&self) -> Option<Cx::Ty> { - self.place_ty.first().copied() + fn head_ty(&self) -> Option<&Cx::Ty> { + self.place_ty.first() } fn column_count(&self) -> usize { self.place_ty.len() @@ -1056,14 +1052,14 @@ impl<'p, Cx: TypeCx> Matrix<'p, Cx> { /// 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(); + ctor_sub_tys.iter().chain(self.place_ty[1..].iter()).cloned().collect(); let ctor_sub_validity = self.place_validity[0].specialize(ctor); let specialized_place_validity = std::iter::repeat(ctor_sub_validity) .take(arity) @@ -1215,11 +1211,11 @@ 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(); - let pat = WitnessPat::new(ctor.clone(), fields, pcx.ty); + let pat = WitnessPat::new(ctor.clone(), fields, pcx.ty.clone()); self.0.push(pat); } } @@ -1266,7 +1262,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, @@ -1317,6 +1313,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 @@ -1333,7 +1398,7 @@ 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, ) -> Result<WitnessMatrix<Cx>, Cx::Error> { @@ -1346,64 +1411,65 @@ fn compute_exhaustiveness_and_usefulness<'a, 'p, Cx: TypeCx>( return Ok(WitnessMatrix::empty()); } - let Some(ty) = matrix.head_ty() else { + let Some(ty) = matrix.head_ty().cloned() 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 Ok(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 { + 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. + // 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: &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(); @@ -1424,10 +1490,29 @@ fn compute_exhaustiveness_and_usefulness<'a, 'p, Cx: TypeCx>( // 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); + } } } @@ -1465,7 +1550,7 @@ 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, @@ -1489,5 +1574,6 @@ pub fn compute_match_usefulness<'p, Cx: TypeCx>( (arm, usefulness) }) .collect(); + Ok(UsefulnessReport { arm_usefulness, non_exhaustiveness_witnesses }) } |