diff options
Diffstat (limited to 'compiler/rustc_pattern_analysis/src')
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/constructor.rs | 174 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/errors.rs | 61 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/lib.rs | 49 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/lints.rs | 16 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/pat.rs | 229 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/pat_column.rs | 6 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/rustc.rs | 218 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/usefulness.rs | 224 |
8 files changed, 647 insertions, 330 deletions
diff --git a/compiler/rustc_pattern_analysis/src/constructor.rs b/compiler/rustc_pattern_analysis/src/constructor.rs index 767227619b0..95c5556410d 100644 --- a/compiler/rustc_pattern_analysis/src/constructor.rs +++ b/compiler/rustc_pattern_analysis/src/constructor.rs @@ -40,7 +40,7 @@ //! - That have no non-trivial intersection with any of the constructors in the column (i.e. they're //! each either disjoint with or covered by any given column constructor). //! -//! We compute this in two steps: first [`TypeCx::ctors_for_ty`] determines the +//! We compute this in two steps: first [`PatCx::ctors_for_ty`] determines the //! set of all possible constructors for the type. Then [`ConstructorSet::split`] looks at the //! column of constructors and splits the set into groups accordingly. The precise invariants of //! [`ConstructorSet::split`] is described in [`SplitConstructorSet`]. @@ -136,7 +136,7 @@ //! the algorithm can't distinguish them from a nonempty constructor. The only known case where this //! could happen is the `[..]` pattern on `[!; N]` with `N > 0` so we must take care to not emit it. //! -//! This is all handled by [`TypeCx::ctors_for_ty`] and +//! This is all handled by [`PatCx::ctors_for_ty`] and //! [`ConstructorSet::split`]. The invariants of [`SplitConstructorSet`] are also of interest. //! //! @@ -162,7 +162,7 @@ use self::MaybeInfiniteInt::*; use self::SliceKind::*; use crate::index; -use crate::TypeCx; +use crate::PatCx; /// Whether we have seen a constructor in the column or not. #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)] @@ -192,11 +192,9 @@ impl fmt::Display for RangeEnd { #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)] pub enum MaybeInfiniteInt { NegInfinity, - /// Encoded value. DO NOT CONSTRUCT BY HAND; use `new_finite`. + /// Encoded value. DO NOT CONSTRUCT BY HAND; use `new_finite_{int,uint}`. #[non_exhaustive] Finite(u128), - /// The integer after `u128::MAX`. We need it to represent `x..=u128::MAX` as an exclusive range. - JustAfterMax, PosInfinity, } @@ -229,25 +227,22 @@ impl MaybeInfiniteInt { } /// Note: this will not turn a finite value into an infinite one or vice-versa. - pub fn minus_one(self) -> Self { + pub fn minus_one(self) -> Option<Self> { match self { - Finite(n) => match n.checked_sub(1) { - Some(m) => Finite(m), - None => panic!("Called `MaybeInfiniteInt::minus_one` on 0"), - }, - JustAfterMax => Finite(u128::MAX), - x => x, + Finite(n) => n.checked_sub(1).map(Finite), + x => Some(x), } } - /// Note: this will not turn a finite value into an infinite one or vice-versa. - pub fn plus_one(self) -> Self { + /// Note: this will turn `u128::MAX` into `PosInfinity`. This means `plus_one` and `minus_one` + /// are not strictly inverses, but that poses no problem in our use of them. + /// this will not turn a finite value into an infinite one or vice-versa. + pub fn plus_one(self) -> Option<Self> { match self { Finite(n) => match n.checked_add(1) { - Some(m) => Finite(m), - None => JustAfterMax, + Some(m) => Some(Finite(m)), + None => Some(PosInfinity), }, - JustAfterMax => panic!("Called `MaybeInfiniteInt::plus_one` on u128::MAX+1"), - x => x, + x => Some(x), } } } @@ -268,18 +263,23 @@ impl IntRange { pub fn is_singleton(&self) -> bool { // Since `lo` and `hi` can't be the same `Infinity` and `plus_one` never changes from finite // to infinite, this correctly only detects ranges that contain exacly one `Finite(x)`. - self.lo.plus_one() == self.hi + self.lo.plus_one() == Some(self.hi) } + /// Construct a singleton range. + /// `x` must be a `Finite(_)` value. #[inline] pub fn from_singleton(x: MaybeInfiniteInt) -> IntRange { - IntRange { lo: x, hi: x.plus_one() } + // `unwrap()` is ok on a finite value + IntRange { lo: x, hi: x.plus_one().unwrap() } } + /// Construct a range with these boundaries. + /// `lo` must not be `PosInfinity`. `hi` must not be `NegInfinity`. #[inline] pub fn from_range(lo: MaybeInfiniteInt, mut hi: MaybeInfiniteInt, end: RangeEnd) -> IntRange { if end == RangeEnd::Included { - hi = hi.plus_one(); + hi = hi.plus_one().unwrap(); } if lo >= hi { // This should have been caught earlier by E0030. @@ -420,7 +420,7 @@ pub enum SliceKind { } impl SliceKind { - fn arity(self) -> usize { + pub fn arity(self) -> usize { match self { FixedLen(length) => length, VarLen(prefix, suffix) => prefix + suffix, @@ -459,7 +459,7 @@ impl Slice { Slice { array_len, kind } } - pub(crate) fn arity(self) -> usize { + pub fn arity(self) -> usize { self.kind.arity() } @@ -648,7 +648,7 @@ impl OpaqueId { /// constructor. `Constructor::apply` reconstructs the pattern from a pair of `Constructor` and /// `Fields`. #[derive(Debug)] -pub enum Constructor<Cx: TypeCx> { +pub enum Constructor<Cx: PatCx> { /// Tuples and structs. Struct, /// Enum variants. @@ -678,22 +678,26 @@ pub enum Constructor<Cx: TypeCx> { Or, /// Wildcard pattern. Wildcard, + /// Never pattern. Only used in `WitnessPat`. An actual never pattern should be lowered as + /// `Wildcard`. + Never, /// Fake extra constructor for enums that aren't allowed to be matched exhaustively. Also used - /// for those types for which we cannot list constructors explicitly, like `f64` and `str`. + /// for those types for which we cannot list constructors explicitly, like `f64` and `str`. Only + /// used in `WitnessPat`. NonExhaustive, - /// Fake extra constructor for variants that should not be mentioned in diagnostics. - /// We use this for variants behind an unstable gate as well as - /// `#[doc(hidden)]` ones. + /// Fake extra constructor for variants that should not be mentioned in diagnostics. We use this + /// for variants behind an unstable gate as well as `#[doc(hidden)]` ones. Only used in + /// `WitnessPat`. Hidden, /// Fake extra constructor for constructors that are not seen in the matrix, as explained at the - /// top of the file. + /// top of the file. Only used for specialization. Missing, /// Fake extra constructor that indicates and empty field that is private. When we encounter one /// we skip the column entirely so we don't observe its emptiness. Only used for specialization. PrivateUninhabited, } -impl<Cx: TypeCx> Clone for Constructor<Cx> { +impl<Cx: PatCx> Clone for Constructor<Cx> { fn clone(&self) -> Self { match self { Constructor::Struct => Constructor::Struct, @@ -708,6 +712,7 @@ impl<Cx: TypeCx> Clone for Constructor<Cx> { Constructor::Str(value) => Constructor::Str(value.clone()), Constructor::Opaque(inner) => Constructor::Opaque(inner.clone()), Constructor::Or => Constructor::Or, + Constructor::Never => Constructor::Never, Constructor::Wildcard => Constructor::Wildcard, Constructor::NonExhaustive => Constructor::NonExhaustive, Constructor::Hidden => Constructor::Hidden, @@ -717,7 +722,7 @@ impl<Cx: TypeCx> Clone for Constructor<Cx> { } } -impl<Cx: TypeCx> Constructor<Cx> { +impl<Cx: PatCx> Constructor<Cx> { pub(crate) fn is_non_exhaustive(&self) -> bool { matches!(self, NonExhaustive) } @@ -814,6 +819,81 @@ impl<Cx: TypeCx> Constructor<Cx> { } }) } + + pub(crate) fn fmt_fields( + &self, + f: &mut fmt::Formatter<'_>, + ty: &Cx::Ty, + mut fields: impl Iterator<Item = impl fmt::Debug>, + ) -> fmt::Result { + let mut first = true; + let mut start_or_continue = |s| { + if first { + first = false; + "" + } else { + s + } + }; + let mut start_or_comma = || start_or_continue(", "); + + match self { + Struct | Variant(_) | UnionField => { + Cx::write_variant_name(f, self, ty)?; + // Without `cx`, we can't know which field corresponds to which, so we can't + // get the names of the fields. Instead we just display everything as a tuple + // struct, which should be good enough. + write!(f, "(")?; + for p in fields { + write!(f, "{}{:?}", start_or_comma(), p)?; + } + write!(f, ")")?; + } + // Note: given the expansion of `&str` patterns done in `expand_pattern`, we should + // be careful to detect strings here. However a string literal pattern will never + // be reported as a non-exhaustiveness witness, so we can ignore this issue. + Ref => { + write!(f, "&{:?}", &fields.next().unwrap())?; + } + Slice(slice) => { + write!(f, "[")?; + match slice.kind { + SliceKind::FixedLen(_) => { + for p in fields { + write!(f, "{}{:?}", start_or_comma(), p)?; + } + } + SliceKind::VarLen(prefix_len, _) => { + for p in fields.by_ref().take(prefix_len) { + write!(f, "{}{:?}", start_or_comma(), p)?; + } + write!(f, "{}..", start_or_comma())?; + for p in fields { + write!(f, "{}{:?}", start_or_comma(), p)?; + } + } + } + write!(f, "]")?; + } + Bool(b) => write!(f, "{b}")?, + // Best-effort, will render signed ranges incorrectly + IntRange(range) => write!(f, "{range:?}")?, + F32Range(lo, hi, end) => write!(f, "{lo}{end}{hi}")?, + F64Range(lo, hi, end) => write!(f, "{lo}{end}{hi}")?, + Str(value) => write!(f, "{value:?}")?, + Opaque(..) => write!(f, "<constant pattern>")?, + Or => { + for pat in fields { + write!(f, "{}{:?}", start_or_continue(" | "), pat)?; + } + } + Never => write!(f, "!")?, + Wildcard | Missing | NonExhaustive | Hidden | PrivateUninhabited => { + write!(f, "_ : {:?}", ty)? + } + } + Ok(()) + } } #[derive(Debug, Clone, Copy)] @@ -835,7 +915,7 @@ pub enum VariantVisibility { /// In terms of division of responsibility, [`ConstructorSet::split`] handles all of the /// `exhaustive_patterns` feature. #[derive(Debug)] -pub enum ConstructorSet<Cx: TypeCx> { +pub enum ConstructorSet<Cx: PatCx> { /// The type is a tuple or struct. `empty` tracks whether the type is empty. Struct { empty: bool }, /// This type has the following list of constructors. If `variants` is empty and @@ -886,13 +966,13 @@ pub enum ConstructorSet<Cx: TypeCx> { /// of the `ConstructorSet` for the type, yet if we forgot to include them in `present` we would be /// ignoring any row with `Opaque`s in the algorithm. Hence the importance of point 4. #[derive(Debug)] -pub struct SplitConstructorSet<Cx: TypeCx> { +pub struct SplitConstructorSet<Cx: PatCx> { pub present: SmallVec<[Constructor<Cx>; 1]>, pub missing: Vec<Constructor<Cx>>, pub missing_empty: Vec<Constructor<Cx>>, } -impl<Cx: TypeCx> ConstructorSet<Cx> { +impl<Cx: PatCx> ConstructorSet<Cx> { /// This analyzes a column of constructors to 1/ determine which constructors of the type (if /// 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 @@ -1040,10 +1120,32 @@ impl<Cx: TypeCx> ConstructorSet<Cx> { // In a `MaybeInvalid` place even an empty pattern may be reachable. We therefore // add a dummy empty constructor here, which will be ignored if the place is // `ValidOnly`. - missing_empty.push(NonExhaustive); + missing_empty.push(Never); } } SplitConstructorSet { present, missing, missing_empty } } + + /// Whether this set only contains empty constructors. + pub(crate) fn all_empty(&self) -> bool { + match self { + ConstructorSet::Bool + | ConstructorSet::Integers { .. } + | ConstructorSet::Ref + | ConstructorSet::Union + | ConstructorSet::Unlistable => false, + ConstructorSet::NoConstructors => true, + ConstructorSet::Struct { empty } => *empty, + ConstructorSet::Variants { variants, non_exhaustive } => { + !*non_exhaustive + && variants + .iter() + .all(|visibility| matches!(visibility, VariantVisibility::Empty)) + } + ConstructorSet::Slice { array_len, subtype_is_empty } => { + *subtype_is_empty && matches!(array_len, Some(1..)) + } + } + } } diff --git a/compiler/rustc_pattern_analysis/src/errors.rs b/compiler/rustc_pattern_analysis/src/errors.rs index 2d592b35159..75b7b7c8f67 100644 --- a/compiler/rustc_pattern_analysis/src/errors.rs +++ b/compiler/rustc_pattern_analysis/src/errors.rs @@ -1,10 +1,10 @@ -use rustc_errors::{AddToDiagnostic, Diag, EmissionGuarantee, SubdiagnosticMessageOp}; +use rustc_errors::{Diag, EmissionGuarantee, SubdiagMessageOp, Subdiagnostic}; use rustc_macros::{LintDiagnostic, Subdiagnostic}; use rustc_middle::thir::Pat; use rustc_middle::ty::Ty; use rustc_span::Span; -use crate::rustc::{RustcMatchCheckCtxt, WitnessPat}; +use crate::rustc::{RustcPatCtxt, WitnessPat}; #[derive(Subdiagnostic)] #[label(pattern_analysis_uncovered)] @@ -21,7 +21,7 @@ pub struct Uncovered<'tcx> { impl<'tcx> Uncovered<'tcx> { pub fn new<'p>( span: Span, - cx: &RustcMatchCheckCtxt<'p, 'tcx>, + cx: &RustcPatCtxt<'p, 'tcx>, witnesses: Vec<WitnessPat<'p, 'tcx>>, ) -> Self where @@ -61,8 +61,8 @@ pub struct Overlap<'tcx> { pub range: Pat<'tcx>, } -impl<'tcx> AddToDiagnostic for Overlap<'tcx> { - fn add_to_diagnostic_with<G: EmissionGuarantee, F: SubdiagnosticMessageOp<G>>( +impl<'tcx> Subdiagnostic for Overlap<'tcx> { + fn add_to_diag_with<G: EmissionGuarantee, F: SubdiagMessageOp<G>>( self, diag: &mut Diag<'_, G>, _: F, @@ -77,6 +77,57 @@ impl<'tcx> AddToDiagnostic for Overlap<'tcx> { } #[derive(LintDiagnostic)] +#[diag(pattern_analysis_excluside_range_missing_max)] +pub struct ExclusiveRangeMissingMax<'tcx> { + #[label] + #[suggestion(code = "{suggestion}", applicability = "maybe-incorrect")] + /// This is an exclusive range that looks like `lo..max` (i.e. doesn't match `max`). + pub first_range: Span, + /// Suggest `lo..=max` instead. + pub suggestion: String, + pub max: Pat<'tcx>, +} + +#[derive(LintDiagnostic)] +#[diag(pattern_analysis_excluside_range_missing_gap)] +pub struct ExclusiveRangeMissingGap<'tcx> { + #[label] + #[suggestion(code = "{suggestion}", applicability = "maybe-incorrect")] + /// This is an exclusive range that looks like `lo..gap` (i.e. doesn't match `gap`). + pub first_range: Span, + pub gap: Pat<'tcx>, + /// Suggest `lo..=gap` instead. + pub suggestion: String, + #[subdiagnostic] + /// All these ranges skipped over `gap` which we think is probably a mistake. + pub gap_with: Vec<GappedRange<'tcx>>, +} + +pub struct GappedRange<'tcx> { + pub span: Span, + pub gap: Pat<'tcx>, + pub first_range: Pat<'tcx>, +} + +impl<'tcx> Subdiagnostic for GappedRange<'tcx> { + fn add_to_diag_with<G: EmissionGuarantee, F: SubdiagMessageOp<G>>( + self, + diag: &mut Diag<'_, G>, + _: F, + ) { + let GappedRange { span, gap, first_range } = self; + + // FIXME(mejrs) unfortunately `#[derive(LintDiagnostic)]` + // does not support `#[subdiagnostic(eager)]`... + let message = format!( + "this could appear to continue range `{first_range}`, but `{gap}` isn't matched by \ + either of them" + ); + diag.span_label(span, message); + } +} + +#[derive(LintDiagnostic)] #[diag(pattern_analysis_non_exhaustive_omitted_pattern)] #[help] #[note] diff --git a/compiler/rustc_pattern_analysis/src/lib.rs b/compiler/rustc_pattern_analysis/src/lib.rs index d4b38d260e7..1a1da5c55f6 100644 --- a/compiler/rustc_pattern_analysis/src/lib.rs +++ b/compiler/rustc_pattern_analysis/src/lib.rs @@ -49,6 +49,12 @@ pub mod index { } } + impl<V> FromIterator<V> for IdxContainer<usize, V> { + fn from_iter<T: IntoIterator<Item = V>>(iter: T) -> Self { + Self(iter.into_iter().enumerate().collect()) + } + } + #[derive(Debug)] pub struct IdxSet<T>(pub rustc_hash::FxHashSet<T>); impl<T: Idx> IdxSet<T> { @@ -70,14 +76,8 @@ use rustc_middle::ty::Ty; use rustc_span::ErrorGuaranteed; use crate::constructor::{Constructor, ConstructorSet, IntRange}; -#[cfg(feature = "rustc")] -use crate::lints::lint_nonexhaustive_missing_variants; use crate::pat::DeconstructedPat; use crate::pat_column::PatternColumn; -#[cfg(feature = "rustc")] -use crate::rustc::RustcMatchCheckCtxt; -#[cfg(feature = "rustc")] -use crate::usefulness::{compute_match_usefulness, ValidityConstraint}; pub trait Captures<'a> {} impl<'a, T: ?Sized> Captures<'a> for T {} @@ -90,7 +90,7 @@ pub struct PrivateUninhabitedField(pub bool); /// Context that provides type information about constructors. /// /// Most of the crate is parameterized on a type that implements this trait. -pub trait TypeCx: Sized + fmt::Debug { +pub trait PatCx: Sized + fmt::Debug { /// The type of a pattern. type Ty: Clone + fmt::Debug; /// Errors that can abort analysis. @@ -126,7 +126,8 @@ pub trait TypeCx: Sized + fmt::Debug { /// `DeconstructedPat`. Only invoqued when `pat.ctor()` is `Struct | Variant(_) | UnionField`. fn write_variant_name( f: &mut fmt::Formatter<'_>, - pat: &crate::pat::DeconstructedPat<Self>, + ctor: &crate::constructor::Constructor<Self>, + ty: &Self::Ty, ) -> fmt::Result; /// Raise a bug. @@ -142,35 +143,55 @@ pub trait TypeCx: Sized + fmt::Debug { _overlaps_with: &[&DeconstructedPat<Self>], ) { } + + /// The maximum pattern complexity limit was reached. + fn complexity_exceeded(&self) -> Result<(), Self::Error>; + + /// Lint that there is a gap `gap` between `pat` and all of `gapped_with` such that the gap is + /// not matched by another range. If `gapped_with` is empty, then `gap` is `T::MAX`. We only + /// detect singleton gaps. + /// The default implementation does nothing. + fn lint_non_contiguous_range_endpoints( + &self, + _pat: &DeconstructedPat<Self>, + _gap: IntRange, + _gapped_with: &[&DeconstructedPat<Self>], + ) { + } } /// The arm of a match expression. #[derive(Debug)] -pub struct MatchArm<'p, Cx: TypeCx> { +pub struct MatchArm<'p, Cx: PatCx> { pub pat: &'p DeconstructedPat<Cx>, pub has_guard: bool, pub arm_data: Cx::ArmData, } -impl<'p, Cx: TypeCx> Clone for MatchArm<'p, Cx> { +impl<'p, Cx: PatCx> Clone for MatchArm<'p, Cx> { fn clone(&self) -> Self { Self { pat: self.pat, has_guard: self.has_guard, arm_data: self.arm_data } } } -impl<'p, Cx: TypeCx> Copy for MatchArm<'p, Cx> {} +impl<'p, Cx: PatCx> Copy for MatchArm<'p, Cx> {} /// The entrypoint for this crate. Computes whether a match is exhaustive and which of its arms are /// useful, and runs some lints. #[cfg(feature = "rustc")] pub fn analyze_match<'p, 'tcx>( - tycx: &RustcMatchCheckCtxt<'p, 'tcx>, + tycx: &rustc::RustcPatCtxt<'p, 'tcx>, arms: &[rustc::MatchArm<'p, 'tcx>], scrut_ty: Ty<'tcx>, + pattern_complexity_limit: Option<usize>, ) -> Result<rustc::UsefulnessReport<'p, 'tcx>, ErrorGuaranteed> { + use lints::lint_nonexhaustive_missing_variants; + use usefulness::{compute_match_usefulness, PlaceValidity}; + let scrut_ty = tycx.reveal_opaque_ty(scrut_ty); - let scrut_validity = ValidityConstraint::from_bool(tycx.known_valid_scrutinee); - let report = compute_match_usefulness(tycx, arms, scrut_ty, scrut_validity)?; + let scrut_validity = PlaceValidity::from_bool(tycx.known_valid_scrutinee); + let report = + compute_match_usefulness(tycx, arms, scrut_ty, scrut_validity, pattern_complexity_limit)?; // 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. diff --git a/compiler/rustc_pattern_analysis/src/lints.rs b/compiler/rustc_pattern_analysis/src/lints.rs index 30e775733de..3ca5ebdb0dd 100644 --- a/compiler/rustc_pattern_analysis/src/lints.rs +++ b/compiler/rustc_pattern_analysis/src/lints.rs @@ -4,15 +4,15 @@ use rustc_span::ErrorGuaranteed; use crate::constructor::Constructor; use crate::errors::{NonExhaustiveOmittedPattern, NonExhaustiveOmittedPatternLintOnArm, Uncovered}; use crate::pat_column::PatternColumn; -use crate::rustc::{RevealedTy, RustcMatchCheckCtxt, WitnessPat}; +use crate::rustc::{RevealedTy, RustcPatCtxt, WitnessPat}; use crate::MatchArm; /// Traverse the patterns to collect any variants of a non_exhaustive enum that fail to be mentioned /// in a given column. #[instrument(level = "debug", skip(cx), ret)] fn collect_nonexhaustive_missing_variants<'p, 'tcx>( - cx: &RustcMatchCheckCtxt<'p, 'tcx>, - column: &PatternColumn<'p, RustcMatchCheckCtxt<'p, 'tcx>>, + cx: &RustcPatCtxt<'p, 'tcx>, + column: &PatternColumn<'p, RustcPatCtxt<'p, 'tcx>>, ) -> Result<Vec<WitnessPat<'p, 'tcx>>, ErrorGuaranteed> { let Some(&ty) = column.head_ty() else { return Ok(Vec::new()); @@ -57,9 +57,9 @@ fn collect_nonexhaustive_missing_variants<'p, 'tcx>( } pub(crate) fn lint_nonexhaustive_missing_variants<'p, 'tcx>( - rcx: &RustcMatchCheckCtxt<'p, 'tcx>, - arms: &[MatchArm<'p, RustcMatchCheckCtxt<'p, 'tcx>>], - pat_column: &PatternColumn<'p, RustcMatchCheckCtxt<'p, 'tcx>>, + rcx: &RustcPatCtxt<'p, 'tcx>, + arms: &[MatchArm<'p, RustcPatCtxt<'p, 'tcx>>], + pat_column: &PatternColumn<'p, RustcPatCtxt<'p, 'tcx>>, scrut_ty: RevealedTy<'tcx>, ) -> Result<(), ErrorGuaranteed> { if !matches!( @@ -97,8 +97,8 @@ pub(crate) fn lint_nonexhaustive_missing_variants<'p, 'tcx>( lint_name: "non_exhaustive_omitted_patterns", }; - use rustc_errors::DecorateLint; - let mut err = rcx.tcx.dcx().struct_span_warn(arm.pat.data().unwrap().span, ""); + use rustc_errors::LintDiagnostic; + let mut err = rcx.tcx.dcx().struct_span_warn(arm.pat.data().span, ""); err.primary_message(decorator.msg()); decorator.decorate_lint(&mut err); err.emit(); diff --git a/compiler/rustc_pattern_analysis/src/pat.rs b/compiler/rustc_pattern_analysis/src/pat.rs index decbfa5c0cf..5f388ee9f89 100644 --- a/compiler/rustc_pattern_analysis/src/pat.rs +++ b/compiler/rustc_pattern_analysis/src/pat.rs @@ -5,7 +5,7 @@ use std::fmt; use smallvec::{smallvec, SmallVec}; use crate::constructor::{Constructor, Slice, SliceKind}; -use crate::{PrivateUninhabitedField, TypeCx}; +use crate::{PatCx, PrivateUninhabitedField}; use self::Constructor::*; @@ -20,32 +20,42 @@ impl PatId { } } +/// A pattern with an index denoting which field it corresponds to. +pub struct IndexedPat<Cx: PatCx> { + pub idx: usize, + pub pat: DeconstructedPat<Cx>, +} + /// Values and patterns can be represented as a constructor applied to some fields. This represents /// a pattern in this form. A `DeconstructedPat` will almost always come from user input; the only /// exception are some `Wildcard`s introduced during pattern lowering. -pub struct DeconstructedPat<Cx: TypeCx> { +pub struct DeconstructedPat<Cx: PatCx> { ctor: Constructor<Cx>, - fields: Vec<DeconstructedPat<Cx>>, + fields: Vec<IndexedPat<Cx>>, + /// The number of fields in this pattern. E.g. if the pattern is `SomeStruct { field12: true, .. + /// }` this would be the total number of fields of the struct. + /// This is also the same as `self.ctor.arity(self.ty)`. + arity: usize, ty: Cx::Ty, - /// Extra data to store in a pattern. `None` if the pattern is a wildcard that does not - /// correspond to a user-supplied pattern. - data: Option<Cx::PatData>, + /// Extra data to store in a pattern. + data: Cx::PatData, /// Globally-unique id used to track usefulness at the level of subpatterns. pub(crate) uid: PatId, } -impl<Cx: TypeCx> DeconstructedPat<Cx> { - pub fn wildcard(ty: Cx::Ty) -> Self { - DeconstructedPat { ctor: Wildcard, fields: Vec::new(), ty, data: None, uid: PatId::new() } - } - +impl<Cx: PatCx> DeconstructedPat<Cx> { pub fn new( ctor: Constructor<Cx>, - fields: Vec<DeconstructedPat<Cx>>, + fields: Vec<IndexedPat<Cx>>, + arity: usize, ty: Cx::Ty, data: Cx::PatData, ) -> Self { - DeconstructedPat { ctor, fields, ty, data: Some(data), uid: PatId::new() } + DeconstructedPat { ctor, fields, arity, ty, data, uid: PatId::new() } + } + + pub fn at_index(self, idx: usize) -> IndexedPat<Cx> { + IndexedPat { idx, pat: self } } pub(crate) fn is_or_pat(&self) -> bool { @@ -58,13 +68,15 @@ impl<Cx: TypeCx> DeconstructedPat<Cx> { 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. - pub fn data(&self) -> Option<&Cx::PatData> { - self.data.as_ref() + /// Returns the extra data stored in a pattern. + pub fn data(&self) -> &Cx::PatData { + &self.data + } + pub fn arity(&self) -> usize { + self.arity } - pub fn iter_fields<'a>(&'a self) -> impl Iterator<Item = &'a DeconstructedPat<Cx>> { + pub fn iter_fields<'a>(&'a self) -> impl Iterator<Item = &'a IndexedPat<Cx>> { self.fields.iter() } @@ -73,36 +85,40 @@ impl<Cx: TypeCx> DeconstructedPat<Cx> { pub(crate) fn specialize<'a>( &'a self, other_ctor: &Constructor<Cx>, - ctor_arity: usize, + other_ctor_arity: usize, ) -> SmallVec<[PatOrWild<'a, Cx>; 2]> { - let wildcard_sub_tys = || (0..ctor_arity).map(|_| PatOrWild::Wild).collect(); - match (&self.ctor, other_ctor) { - // Return a wildcard for each field of `other_ctor`. - (Wildcard, _) => wildcard_sub_tys(), + if matches!(other_ctor, PrivateUninhabited) { // Skip this column. - (_, PrivateUninhabited) => smallvec![], - // The only non-trivial case: two slices of different arity. `other_slice` is - // guaranteed to have a larger arity, so we fill the middle part with enough - // wildcards to reach the length of the new, larger slice. - ( - &Slice(self_slice @ Slice { kind: SliceKind::VarLen(prefix, suffix), .. }), - &Slice(other_slice), - ) if self_slice.arity() != other_slice.arity() => { - // Start with a slice of wildcards of the appropriate length. - let mut fields: SmallVec<[_; 2]> = wildcard_sub_tys(); - // Fill in the fields from both ends. - let new_arity = fields.len(); - for i in 0..prefix { - fields[i] = PatOrWild::Pat(&self.fields[i]); + return smallvec![]; + } + + // Start with a slice of wildcards of the appropriate length. + let mut fields: SmallVec<[_; 2]> = (0..other_ctor_arity).map(|_| PatOrWild::Wild).collect(); + // Fill `fields` with our fields. The arities are known to be compatible. + match self.ctor { + // The only non-trivial case: two slices of different arity. `other_ctor` is guaranteed + // to have a larger arity, so we adjust the indices of the patterns in the suffix so + // that they are correctly positioned in the larger slice. + Slice(Slice { kind: SliceKind::VarLen(prefix, _), .. }) + if self.arity != other_ctor_arity => + { + for ipat in &self.fields { + let new_idx = if ipat.idx < prefix { + ipat.idx + } else { + // Adjust the indices in the suffix. + ipat.idx + other_ctor_arity - self.arity + }; + fields[new_idx] = PatOrWild::Pat(&ipat.pat); } - for i in 0..suffix { - fields[new_arity - 1 - i] = - PatOrWild::Pat(&self.fields[self.fields.len() - 1 - i]); + } + _ => { + for ipat in &self.fields { + fields[ipat.idx] = PatOrWild::Pat(&ipat.pat); } - fields } - _ => self.fields.iter().map(PatOrWild::Pat).collect(), } + fields } /// Walk top-down and call `it` in each place where a pattern occurs @@ -114,85 +130,19 @@ impl<Cx: TypeCx> DeconstructedPat<Cx> { } for p in self.iter_fields() { - p.walk(it) + p.pat.walk(it) } } } /// This is best effort and not good enough for a `Display` impl. -impl<Cx: TypeCx> fmt::Debug for DeconstructedPat<Cx> { +impl<Cx: PatCx> fmt::Debug for DeconstructedPat<Cx> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - let pat = self; - let mut first = true; - let mut start_or_continue = |s| { - if first { - first = false; - "" - } else { - s - } - }; - let mut start_or_comma = || start_or_continue(", "); - - match pat.ctor() { - Struct | Variant(_) | UnionField => { - Cx::write_variant_name(f, pat)?; - // Without `cx`, we can't know which field corresponds to which, so we can't - // get the names of the fields. Instead we just display everything as a tuple - // struct, which should be good enough. - write!(f, "(")?; - for p in pat.iter_fields() { - write!(f, "{}", start_or_comma())?; - write!(f, "{p:?}")?; - } - write!(f, ")") - } - // Note: given the expansion of `&str` patterns done in `expand_pattern`, we should - // be careful to detect strings here. However a string literal pattern will never - // be reported as a non-exhaustiveness witness, so we can ignore this issue. - Ref => { - let subpattern = pat.iter_fields().next().unwrap(); - write!(f, "&{:?}", subpattern) - } - Slice(slice) => { - let mut subpatterns = pat.iter_fields(); - write!(f, "[")?; - match slice.kind { - SliceKind::FixedLen(_) => { - for p in subpatterns { - write!(f, "{}{:?}", start_or_comma(), p)?; - } - } - SliceKind::VarLen(prefix_len, _) => { - for p in subpatterns.by_ref().take(prefix_len) { - write!(f, "{}{:?}", start_or_comma(), p)?; - } - write!(f, "{}", start_or_comma())?; - write!(f, "..")?; - for p in subpatterns { - write!(f, "{}{:?}", start_or_comma(), p)?; - } - } - } - write!(f, "]") - } - Bool(b) => write!(f, "{b}"), - // Best-effort, will render signed ranges incorrectly - IntRange(range) => write!(f, "{range:?}"), - F32Range(lo, hi, end) => write!(f, "{lo}{end}{hi}"), - F64Range(lo, hi, end) => write!(f, "{lo}{end}{hi}"), - Str(value) => write!(f, "{value:?}"), - Opaque(..) => write!(f, "<constant pattern>"), - Or => { - for pat in pat.iter_fields() { - write!(f, "{}{:?}", start_or_continue(" | "), pat)?; - } - Ok(()) - } - Wildcard | Missing | NonExhaustive | Hidden | PrivateUninhabited => { - write!(f, "_ : {:?}", pat.ty()) - } + let mut fields: Vec<_> = (0..self.arity).map(|_| PatOrWild::Wild).collect(); + for ipat in self.iter_fields() { + fields[ipat.idx] = PatOrWild::Pat(&ipat.pat); } + self.ctor().fmt_fields(f, self.ty(), fields.into_iter()) } } @@ -200,14 +150,14 @@ impl<Cx: TypeCx> fmt::Debug for DeconstructedPat<Cx> { /// algorithm. Do not use `Wild` to represent a wildcard pattern comping from user input. /// /// This is morally `Option<&'p DeconstructedPat>` where `None` is interpreted as a wildcard. -pub(crate) enum PatOrWild<'p, Cx: TypeCx> { +pub(crate) enum PatOrWild<'p, Cx: PatCx> { /// A non-user-provided wildcard, created during specialization. Wild, /// A user-provided pattern. Pat(&'p DeconstructedPat<Cx>), } -impl<'p, Cx: TypeCx> Clone for PatOrWild<'p, Cx> { +impl<'p, Cx: PatCx> Clone for PatOrWild<'p, Cx> { fn clone(&self) -> Self { match self { PatOrWild::Wild => PatOrWild::Wild, @@ -216,9 +166,9 @@ impl<'p, Cx: TypeCx> Clone for PatOrWild<'p, Cx> { } } -impl<'p, Cx: TypeCx> Copy for PatOrWild<'p, Cx> {} +impl<'p, Cx: PatCx> Copy for PatOrWild<'p, Cx> {} -impl<'p, Cx: TypeCx> PatOrWild<'p, Cx> { +impl<'p, Cx: PatCx> PatOrWild<'p, Cx> { pub(crate) fn as_pat(&self) -> Option<&'p DeconstructedPat<Cx>> { match self { PatOrWild::Wild => None, @@ -242,9 +192,10 @@ impl<'p, Cx: TypeCx> PatOrWild<'p, Cx> { /// 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() - } + PatOrWild::Pat(pat) if pat.is_or_pat() => pat + .iter_fields() + .flat_map(|ipat| PatOrWild::Pat(&ipat.pat).flatten_or_pat()) + .collect(), _ => smallvec![self], } } @@ -263,7 +214,7 @@ impl<'p, Cx: TypeCx> PatOrWild<'p, Cx> { } } -impl<'p, Cx: TypeCx> fmt::Debug for PatOrWild<'p, Cx> { +impl<'p, Cx: PatCx> fmt::Debug for PatOrWild<'p, Cx> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { match self { PatOrWild::Wild => write!(f, "_"), @@ -274,35 +225,40 @@ impl<'p, Cx: TypeCx> fmt::Debug for PatOrWild<'p, Cx> { /// Same idea as `DeconstructedPat`, except this is a fictitious pattern built up for diagnostics /// purposes. As such they don't use interning and can be cloned. -#[derive(Debug)] -pub struct WitnessPat<Cx: TypeCx> { +pub struct WitnessPat<Cx: PatCx> { ctor: Constructor<Cx>, pub(crate) fields: Vec<WitnessPat<Cx>>, ty: Cx::Ty, } -impl<Cx: TypeCx> Clone for WitnessPat<Cx> { +impl<Cx: PatCx> Clone for WitnessPat<Cx> { fn clone(&self) -> Self { Self { ctor: self.ctor.clone(), fields: self.fields.clone(), ty: self.ty.clone() } } } -impl<Cx: TypeCx> WitnessPat<Cx> { +impl<Cx: PatCx> WitnessPat<Cx> { pub(crate) fn new(ctor: Constructor<Cx>, fields: Vec<Self>, ty: Cx::Ty) -> Self { Self { ctor, fields, ty } } - pub(crate) fn wildcard(ty: Cx::Ty) -> Self { - Self::new(Wildcard, Vec::new(), ty) + /// Create a wildcard pattern for this type. If the type is empty, we create a `!` pattern. + pub(crate) fn wildcard(cx: &Cx, ty: Cx::Ty) -> Self { + let is_empty = cx.ctors_for_ty(&ty).is_ok_and(|ctors| ctors.all_empty()); + let ctor = if is_empty { Never } else { Wildcard }; + Self::new(ctor, Vec::new(), ty) } /// 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(cx: &Cx, ctor: Constructor<Cx>, ty: Cx::Ty) -> Self { + if matches!(ctor, Wildcard) { + return Self::wildcard(cx, ty); + } let fields = cx .ctor_sub_tys(&ctor, &ty) .filter(|(_, PrivateUninhabitedField(skip))| !skip) - .map(|(ty, _)| Self::wildcard(ty)) + .map(|(ty, _)| Self::wildcard(cx, ty)) .collect(); Self::new(ctor, fields, ty) } @@ -314,7 +270,22 @@ impl<Cx: TypeCx> WitnessPat<Cx> { &self.ty } + pub fn is_never_pattern(&self) -> bool { + match self.ctor() { + Never => true, + Or => self.fields.iter().all(|p| p.is_never_pattern()), + _ => self.fields.iter().any(|p| p.is_never_pattern()), + } + } + pub fn iter_fields(&self) -> impl Iterator<Item = &WitnessPat<Cx>> { self.fields.iter() } } + +/// This is best effort and not good enough for a `Display` impl. +impl<Cx: PatCx> fmt::Debug for WitnessPat<Cx> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + self.ctor().fmt_fields(f, self.ty(), self.fields.iter()) + } +} diff --git a/compiler/rustc_pattern_analysis/src/pat_column.rs b/compiler/rustc_pattern_analysis/src/pat_column.rs index ce14fdc364f..eb4e095c1c6 100644 --- a/compiler/rustc_pattern_analysis/src/pat_column.rs +++ b/compiler/rustc_pattern_analysis/src/pat_column.rs @@ -1,6 +1,6 @@ use crate::constructor::{Constructor, SplitConstructorSet}; use crate::pat::{DeconstructedPat, PatOrWild}; -use crate::{Captures, MatchArm, TypeCx}; +use crate::{Captures, MatchArm, PatCx}; /// A column of patterns in a match, where a column is the intuitive notion of "subpatterns that /// inspect the same subvalue/place". @@ -11,12 +11,12 @@ use crate::{Captures, MatchArm, TypeCx}; /// /// This is not used in the usefulness algorithm; only in lints. #[derive(Debug)] -pub struct PatternColumn<'p, Cx: TypeCx> { +pub struct PatternColumn<'p, Cx: PatCx> { /// This must not contain an or-pattern. `expand_and_push` takes care to expand them. patterns: Vec<&'p DeconstructedPat<Cx>>, } -impl<'p, Cx: TypeCx> PatternColumn<'p, Cx> { +impl<'p, Cx: PatCx> PatternColumn<'p, Cx> { pub fn new(arms: &[MatchArm<'p, Cx>]) -> Self { let patterns = Vec::with_capacity(arms.len()); let mut column = PatternColumn { patterns }; diff --git a/compiler/rustc_pattern_analysis/src/rustc.rs b/compiler/rustc_pattern_analysis/src/rustc.rs index f8839b0b590..b0f506c3651 100644 --- a/compiler/rustc_pattern_analysis/src/rustc.rs +++ b/compiler/rustc_pattern_analysis/src/rustc.rs @@ -8,7 +8,7 @@ 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::thir::{self, FieldPat, Pat, PatKind, PatRange, PatRangeBoundary}; use rustc_middle::ty::layout::IntegerExt; use rustc_middle::ty::{self, FieldDef, OpaqueTypeKey, Ty, TyCtxt, TypeVisitableExt, VariantDef}; use rustc_session::lint; @@ -18,20 +18,19 @@ use rustc_target::abi::{FieldIdx, Integer, VariantIdx, FIRST_VARIANT}; use crate::constructor::{ IntRange, MaybeInfiniteInt, OpaqueId, RangeEnd, Slice, SliceKind, VariantVisibility, }; -use crate::{errors, Captures, PrivateUninhabitedField, TypeCx}; +use crate::{errors, Captures, PatCx, PrivateUninhabitedField}; use crate::constructor::Constructor::*; // Re-export rustc-specific versions of all these types. -pub type Constructor<'p, 'tcx> = crate::constructor::Constructor<RustcMatchCheckCtxt<'p, 'tcx>>; -pub type ConstructorSet<'p, 'tcx> = - crate::constructor::ConstructorSet<RustcMatchCheckCtxt<'p, 'tcx>>; -pub type DeconstructedPat<'p, 'tcx> = crate::pat::DeconstructedPat<RustcMatchCheckCtxt<'p, 'tcx>>; -pub type MatchArm<'p, 'tcx> = crate::MatchArm<'p, RustcMatchCheckCtxt<'p, 'tcx>>; -pub type Usefulness<'p, 'tcx> = crate::usefulness::Usefulness<'p, RustcMatchCheckCtxt<'p, 'tcx>>; +pub type Constructor<'p, 'tcx> = crate::constructor::Constructor<RustcPatCtxt<'p, 'tcx>>; +pub type ConstructorSet<'p, 'tcx> = crate::constructor::ConstructorSet<RustcPatCtxt<'p, 'tcx>>; +pub type DeconstructedPat<'p, 'tcx> = crate::pat::DeconstructedPat<RustcPatCtxt<'p, 'tcx>>; +pub type MatchArm<'p, 'tcx> = crate::MatchArm<'p, RustcPatCtxt<'p, 'tcx>>; +pub type Usefulness<'p, 'tcx> = crate::usefulness::Usefulness<'p, RustcPatCtxt<'p, 'tcx>>; pub type UsefulnessReport<'p, 'tcx> = - crate::usefulness::UsefulnessReport<'p, RustcMatchCheckCtxt<'p, 'tcx>>; -pub type WitnessPat<'p, 'tcx> = crate::pat::WitnessPat<RustcMatchCheckCtxt<'p, 'tcx>>; + crate::usefulness::UsefulnessReport<'p, RustcPatCtxt<'p, 'tcx>>; +pub type WitnessPat<'p, 'tcx> = crate::pat::WitnessPat<RustcPatCtxt<'p, 'tcx>>; /// A type which has gone through `cx.reveal_opaque_ty`, i.e. if it was opaque it was replaced by /// the hidden type if allowed in the current body. This ensures we consistently inspect the hidden @@ -62,7 +61,7 @@ impl<'tcx> RevealedTy<'tcx> { } #[derive(Clone)] -pub struct RustcMatchCheckCtxt<'p, 'tcx: 'p> { +pub struct RustcPatCtxt<'p, 'tcx: 'p> { pub tcx: TyCtxt<'tcx>, pub typeck_results: &'tcx ty::TypeckResults<'tcx>, /// The module in which the match occurs. This is necessary for @@ -87,22 +86,19 @@ pub struct RustcMatchCheckCtxt<'p, 'tcx: 'p> { pub known_valid_scrutinee: bool, } -impl<'p, 'tcx: 'p> fmt::Debug for RustcMatchCheckCtxt<'p, 'tcx> { +impl<'p, 'tcx: 'p> fmt::Debug for RustcPatCtxt<'p, 'tcx> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - f.debug_struct("RustcMatchCheckCtxt").finish() + f.debug_struct("RustcPatCtxt").finish() } } -impl<'p, 'tcx: 'p> RustcMatchCheckCtxt<'p, 'tcx> { +impl<'p, 'tcx: 'p> RustcPatCtxt<'p, 'tcx> { /// Type inference occasionally gives us opaque types in places where corresponding patterns /// have more specific types. To avoid inconsistencies as well as detect opaque uninhabited /// types, we use the corresponding concrete type if possible. #[inline] pub fn reveal_opaque_ty(&self, ty: Ty<'tcx>) -> RevealedTy<'tcx> { - fn reveal_inner<'tcx>( - cx: &RustcMatchCheckCtxt<'_, 'tcx>, - ty: Ty<'tcx>, - ) -> RevealedTy<'tcx> { + fn reveal_inner<'tcx>(cx: &RustcPatCtxt<'_, 'tcx>, ty: Ty<'tcx>) -> RevealedTy<'tcx> { let ty::Alias(ty::Opaque, alias_ty) = *ty.kind() else { bug!() }; if let Some(local_def_id) = alias_ty.def_id.as_local() { let key = ty::OpaqueTypeKey { def_id: local_def_id, args: alias_ty.args }; @@ -199,7 +195,7 @@ impl<'p, 'tcx: 'p> RustcMatchCheckCtxt<'p, 'tcx> { + ExactSizeIterator + Captures<'a> { fn reveal_and_alloc<'a, 'tcx>( - cx: &'a RustcMatchCheckCtxt<'_, 'tcx>, + cx: &'a RustcPatCtxt<'_, 'tcx>, iter: impl Iterator<Item = Ty<'tcx>>, ) -> &'a [(RevealedTy<'tcx>, PrivateUninhabitedField)] { cx.dropless_arena.alloc_from_iter( @@ -218,7 +214,7 @@ impl<'p, 'tcx: 'p> RustcMatchCheckCtxt<'p, 'tcx> { reveal_and_alloc(cx, once(args.type_at(0))) } else { let variant = - &adt.variant(RustcMatchCheckCtxt::variant_index_for_adt(&ctor, *adt)); + &adt.variant(RustcPatCtxt::variant_index_for_adt(&ctor, *adt)); // In the cases of either a `#[non_exhaustive]` field list or a non-public // field, we skip uninhabited fields in order not to reveal the @@ -251,7 +247,7 @@ impl<'p, 'tcx: 'p> RustcMatchCheckCtxt<'p, 'tcx> { _ => bug!("bad slice pattern {:?} {:?}", ctor, ty), }, Bool(..) | IntRange(..) | F32Range(..) | F64Range(..) | Str(..) | Opaque(..) - | NonExhaustive | Hidden | Missing | PrivateUninhabited | Wildcard => &[], + | Never | NonExhaustive | Hidden | Missing | PrivateUninhabited | Wildcard => &[], Or => { bug!("called `Fields::wildcards` on an `Or` ctor") } @@ -270,7 +266,7 @@ impl<'p, 'tcx: 'p> RustcMatchCheckCtxt<'p, 'tcx> { // patterns. If we're here we can assume this is a box pattern. 1 } else { - let variant_idx = RustcMatchCheckCtxt::variant_index_for_adt(&ctor, *adt); + let variant_idx = RustcPatCtxt::variant_index_for_adt(&ctor, *adt); adt.variant(variant_idx).fields.len() } } @@ -279,7 +275,7 @@ impl<'p, 'tcx: 'p> RustcMatchCheckCtxt<'p, 'tcx> { Ref => 1, Slice(slice) => slice.arity(), Bool(..) | IntRange(..) | F32Range(..) | F64Range(..) | Str(..) | Opaque(..) - | NonExhaustive | Hidden | Missing | PrivateUninhabited | Wildcard => 0, + | Never | NonExhaustive | Hidden | Missing | PrivateUninhabited | Wildcard => 0, Or => bug!("The `Or` constructor doesn't have a fixed arity"), } } @@ -402,7 +398,7 @@ impl<'p, 'tcx: 'p> RustcMatchCheckCtxt<'p, 'tcx> { ty::Float(_) | ty::Str | ty::Foreign(_) - | ty::RawPtr(_) + | ty::RawPtr(_, _) | ty::FnDef(_, _) | ty::FnPtr(_) | ty::Dynamic(_, _, _) @@ -445,7 +441,8 @@ impl<'p, 'tcx: 'p> RustcMatchCheckCtxt<'p, 'tcx> { let cx = self; let ty = cx.reveal_opaque_ty(pat.ty); let ctor; - let mut fields: Vec<_>; + let arity; + let fields: Vec<_>; match &pat.kind { PatKind::AscribeUserType { subpattern, .. } | PatKind::InlineConstant { subpattern, .. } => return self.lower_pat(subpattern), @@ -453,9 +450,11 @@ impl<'p, 'tcx: 'p> RustcMatchCheckCtxt<'p, 'tcx> { PatKind::Binding { subpattern: None, .. } | PatKind::Wild => { ctor = Wildcard; fields = vec![]; + arity = 0; } PatKind::Deref { subpattern } => { - fields = vec![self.lower_pat(subpattern)]; + fields = vec![self.lower_pat(subpattern).at_index(0)]; + arity = 1; ctor = match ty.kind() { // This is a box pattern. ty::Adt(adt, ..) if adt.is_box() => Struct, @@ -463,20 +462,23 @@ impl<'p, 'tcx: 'p> RustcMatchCheckCtxt<'p, 'tcx> { _ => bug!("pattern has unexpected type: pat: {:?}, ty: {:?}", pat, ty), }; } + PatKind::DerefPattern { .. } => { + // FIXME(deref_patterns): At least detect that `box _` is irrefutable. + fields = vec![]; + arity = 0; + ctor = Opaque(OpaqueId::new()); + } PatKind::Leaf { subpatterns } | PatKind::Variant { subpatterns, .. } => { match ty.kind() { ty::Tuple(fs) => { ctor = Struct; - fields = fs + arity = fs.len(); + fields = subpatterns .iter() - .map(|ty| cx.reveal_opaque_ty(ty)) - .map(|ty| DeconstructedPat::wildcard(ty)) + .map(|ipat| self.lower_pat(&ipat.pattern).at_index(ipat.field.index())) .collect(); - for pat in subpatterns { - fields[pat.field.index()] = self.lower_pat(&pat.pattern); - } } - ty::Adt(adt, args) if adt.is_box() => { + ty::Adt(adt, _) if adt.is_box() => { // The only legal patterns of type `Box` (outside `std`) are `_` and box // patterns. If we're here we can assume this is a box pattern. // FIXME(Nadrieril): A `Box` can in theory be matched either with `Box(_, @@ -490,13 +492,13 @@ impl<'p, 'tcx: 'p> RustcMatchCheckCtxt<'p, 'tcx> { // solution when we introduce generalized deref patterns. Also need to // prevent mixing of those two options. let pattern = subpatterns.into_iter().find(|pat| pat.field.index() == 0); - let pat = if let Some(pat) = pattern { - self.lower_pat(&pat.pattern) + if let Some(pat) = pattern { + fields = vec![self.lower_pat(&pat.pattern).at_index(0)]; } else { - DeconstructedPat::wildcard(self.reveal_opaque_ty(args.type_at(0))) - }; + fields = vec![]; + } ctor = Struct; - fields = vec![pat]; + arity = 1; } ty::Adt(adt, _) => { ctor = match pat.kind { @@ -506,14 +508,12 @@ impl<'p, 'tcx: 'p> RustcMatchCheckCtxt<'p, 'tcx> { _ => bug!(), }; let variant = - &adt.variant(RustcMatchCheckCtxt::variant_index_for_adt(&ctor, *adt)); - fields = cx - .variant_sub_tys(ty, variant) - .map(|(_, ty)| DeconstructedPat::wildcard(ty)) + &adt.variant(RustcPatCtxt::variant_index_for_adt(&ctor, *adt)); + arity = variant.fields.len(); + fields = subpatterns + .iter() + .map(|ipat| self.lower_pat(&ipat.pattern).at_index(ipat.field.index())) .collect(); - for pat in subpatterns { - fields[pat.field.index()] = self.lower_pat(&pat.pattern); - } } _ => bug!("pattern has unexpected type: pat: {:?}, ty: {:?}", pat, ty), } @@ -526,6 +526,7 @@ impl<'p, 'tcx: 'p> RustcMatchCheckCtxt<'p, 'tcx> { None => Opaque(OpaqueId::new()), }; fields = vec![]; + arity = 0; } ty::Char | ty::Int(_) | ty::Uint(_) => { ctor = match value.try_eval_bits(cx.tcx, cx.param_env) { @@ -542,6 +543,7 @@ impl<'p, 'tcx: 'p> RustcMatchCheckCtxt<'p, 'tcx> { None => Opaque(OpaqueId::new()), }; fields = vec![]; + arity = 0; } ty::Float(ty::FloatTy::F32) => { ctor = match value.try_eval_bits(cx.tcx, cx.param_env) { @@ -553,6 +555,7 @@ impl<'p, 'tcx: 'p> RustcMatchCheckCtxt<'p, 'tcx> { None => Opaque(OpaqueId::new()), }; fields = vec![]; + arity = 0; } ty::Float(ty::FloatTy::F64) => { ctor = match value.try_eval_bits(cx.tcx, cx.param_env) { @@ -564,6 +567,7 @@ impl<'p, 'tcx: 'p> RustcMatchCheckCtxt<'p, 'tcx> { None => Opaque(OpaqueId::new()), }; fields = vec![]; + arity = 0; } ty::Ref(_, t, _) if t.is_str() => { // We want a `&str` constant to behave like a `Deref` pattern, to be compatible @@ -574,9 +578,10 @@ impl<'p, 'tcx: 'p> RustcMatchCheckCtxt<'p, 'tcx> { // subfields. // Note: `t` is `str`, not `&str`. let ty = self.reveal_opaque_ty(*t); - let subpattern = DeconstructedPat::new(Str(*value), Vec::new(), ty, pat); + let subpattern = DeconstructedPat::new(Str(*value), Vec::new(), 0, ty, pat); ctor = Ref; - fields = vec![subpattern] + fields = vec![subpattern.at_index(0)]; + arity = 1; } // All constants that can be structurally matched have already been expanded // into the corresponding `Pat`s by `const_to_pat`. Constants that remain are @@ -584,6 +589,7 @@ impl<'p, 'tcx: 'p> RustcMatchCheckCtxt<'p, 'tcx> { _ => { ctor = Opaque(OpaqueId::new()); fields = vec![]; + arity = 0; } } } @@ -623,6 +629,7 @@ impl<'p, 'tcx: 'p> RustcMatchCheckCtxt<'p, 'tcx> { _ => bug!("invalid type for range pattern: {}", ty.inner()), }; fields = vec![]; + arity = 0; } PatKind::Array { prefix, slice, suffix } | PatKind::Slice { prefix, slice, suffix } => { let array_len = match ty.kind() { @@ -638,12 +645,25 @@ impl<'p, 'tcx: 'p> RustcMatchCheckCtxt<'p, 'tcx> { SliceKind::FixedLen(prefix.len() + suffix.len()) }; ctor = Slice(Slice::new(array_len, kind)); - fields = prefix.iter().chain(suffix.iter()).map(|p| self.lower_pat(&*p)).collect(); + fields = prefix + .iter() + .chain(suffix.iter()) + .map(|p| self.lower_pat(&*p)) + .enumerate() + .map(|(i, p)| p.at_index(i)) + .collect(); + arity = kind.arity(); } PatKind::Or { .. } => { ctor = Or; let pats = expand_or_pat(pat); - fields = pats.into_iter().map(|p| self.lower_pat(p)).collect(); + fields = pats + .into_iter() + .map(|p| self.lower_pat(p)) + .enumerate() + .map(|(i, p)| p.at_index(i)) + .collect(); + arity = fields.len(); } PatKind::Never => { // A never pattern matches all the values of its type (namely none). Moreover it @@ -651,13 +671,15 @@ impl<'p, 'tcx: 'p> RustcMatchCheckCtxt<'p, 'tcx> { // `Result<!, !>` which has other constructors. Hence we lower it as a wildcard. ctor = Wildcard; fields = vec![]; + arity = 0; } PatKind::Error(_) => { ctor = Opaque(OpaqueId::new()); fields = vec![]; + arity = 0; } } - DeconstructedPat::new(ctor, fields, ty, pat) + DeconstructedPat::new(ctor, fields, arity, ty, pat) } /// Convert back to a `thir::PatRangeBoundary` for diagnostic purposes. @@ -690,7 +712,7 @@ impl<'p, 'tcx: 'p> RustcMatchCheckCtxt<'p, 'tcx> { None => PatRangeBoundary::PosInfinity, } } - JustAfterMax | PosInfinity => PatRangeBoundary::PosInfinity, + PosInfinity => PatRangeBoundary::PosInfinity, } } @@ -718,12 +740,12 @@ impl<'p, 'tcx: 'p> RustcMatchCheckCtxt<'p, 'tcx> { let value = mir::Const::from_ty_const(c, cx.tcx); lo = PatRangeBoundary::Finite(value); } - let hi = if matches!(range.hi, Finite(0)) { + let hi = if let Some(hi) = range.hi.minus_one() { + hi + } else { // The range encodes `..ty::MIN`, so we can't convert it to an inclusive range. end = rustc_hir::RangeEnd::Excluded; range.hi - } else { - range.hi.minus_one() }; let hi = cx.hoist_pat_range_bdy(hi, ty); PatKind::Range(Box::new(PatRange { lo, hi, end, ty: ty.inner() })) @@ -754,8 +776,7 @@ impl<'p, 'tcx: 'p> RustcMatchCheckCtxt<'p, 'tcx> { PatKind::Deref { subpattern: subpatterns.next().unwrap() } } ty::Adt(adt_def, args) => { - let variant_index = - RustcMatchCheckCtxt::variant_index_for_adt(&pat.ctor(), *adt_def); + let variant_index = RustcPatCtxt::variant_index_for_adt(&pat.ctor(), *adt_def); let subpatterns = subpatterns .enumerate() .map(|(i, pattern)| FieldPat { field: FieldIdx::new(i), pattern }) @@ -809,7 +830,8 @@ impl<'p, 'tcx: 'p> RustcMatchCheckCtxt<'p, 'tcx> { } } &Str(value) => PatKind::Constant { value }, - Wildcard | NonExhaustive | Hidden | PrivateUninhabited => PatKind::Wild, + Never if self.tcx.features().never_patterns => PatKind::Never, + Never | Wildcard | NonExhaustive | Hidden | PrivateUninhabited => PatKind::Wild, Missing { .. } => bug!( "trying to convert a `Missing` constructor into a `Pat`; this is probably a bug, `Missing` should have been processed in `apply_constructors`" @@ -823,7 +845,7 @@ impl<'p, 'tcx: 'p> RustcMatchCheckCtxt<'p, 'tcx> { } } -impl<'p, 'tcx: 'p> TypeCx for RustcMatchCheckCtxt<'p, 'tcx> { +impl<'p, 'tcx: 'p> PatCx for RustcPatCtxt<'p, 'tcx> { type Ty = RevealedTy<'tcx>; type Error = ErrorGuaranteed; type VariantIdx = VariantIdx; @@ -858,13 +880,14 @@ impl<'p, 'tcx: 'p> TypeCx for RustcMatchCheckCtxt<'p, 'tcx> { fn write_variant_name( f: &mut fmt::Formatter<'_>, - pat: &crate::pat::DeconstructedPat<Self>, + ctor: &crate::constructor::Constructor<Self>, + ty: &Self::Ty, ) -> fmt::Result { - if let ty::Adt(adt, _) = pat.ty().kind() { + if let ty::Adt(adt, _) = ty.kind() { if adt.is_box() { write!(f, "Box")? } else { - let variant = adt.variant(Self::variant_index_for_adt(pat.ctor(), *adt)); + let variant = adt.variant(Self::variant_index_for_adt(ctor, *adt)); write!(f, "{}", variant.name)?; } } @@ -884,10 +907,10 @@ impl<'p, 'tcx: 'p> TypeCx for RustcMatchCheckCtxt<'p, 'tcx> { 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(|pat| pat.data().span) .map(|span| errors::Overlap { range: overlap_as_pat.clone(), span }) .collect(); - let pat_span = pat.data().unwrap().span; + let pat_span = pat.data().span; self.tcx.emit_node_span_lint( lint::builtin::OVERLAPPING_RANGE_ENDPOINTS, self.match_lint_level, @@ -895,6 +918,75 @@ impl<'p, 'tcx: 'p> TypeCx for RustcMatchCheckCtxt<'p, 'tcx> { errors::OverlappingRangeEndpoints { overlap: overlaps, range: pat_span }, ); } + + fn complexity_exceeded(&self) -> Result<(), Self::Error> { + let span = self.whole_match_span.unwrap_or(self.scrut_span); + Err(self.tcx.dcx().span_err(span, "reached pattern complexity limit")) + } + + fn lint_non_contiguous_range_endpoints( + &self, + pat: &crate::pat::DeconstructedPat<Self>, + gap: IntRange, + gapped_with: &[&crate::pat::DeconstructedPat<Self>], + ) { + let &thir_pat = pat.data(); + let thir::PatKind::Range(range) = &thir_pat.kind else { return }; + // Only lint when the left range is an exclusive range. + if range.end != rustc_hir::RangeEnd::Excluded { + return; + } + // `pat` is an exclusive range like `lo..gap`. `gapped_with` contains ranges that start with + // `gap+1`. + let suggested_range: thir::Pat<'_> = { + // Suggest `lo..=gap` instead. + let mut suggested_range = thir_pat.clone(); + let thir::PatKind::Range(range) = &mut suggested_range.kind else { unreachable!() }; + range.end = rustc_hir::RangeEnd::Included; + suggested_range + }; + let gap_as_pat = self.hoist_pat_range(&gap, *pat.ty()); + if gapped_with.is_empty() { + // If `gapped_with` is empty, `gap == T::MAX`. + self.tcx.emit_node_span_lint( + lint::builtin::NON_CONTIGUOUS_RANGE_ENDPOINTS, + self.match_lint_level, + thir_pat.span, + errors::ExclusiveRangeMissingMax { + // Point at this range. + first_range: thir_pat.span, + // That's the gap that isn't covered. + max: gap_as_pat.clone(), + // Suggest `lo..=max` instead. + suggestion: suggested_range.to_string(), + }, + ); + } else { + self.tcx.emit_node_span_lint( + lint::builtin::NON_CONTIGUOUS_RANGE_ENDPOINTS, + self.match_lint_level, + thir_pat.span, + errors::ExclusiveRangeMissingGap { + // Point at this range. + first_range: thir_pat.span, + // That's the gap that isn't covered. + gap: gap_as_pat.clone(), + // Suggest `lo..=gap` instead. + suggestion: suggested_range.to_string(), + // All these ranges skipped over `gap` which we think is probably a + // mistake. + gap_with: gapped_with + .iter() + .map(|pat| errors::GappedRange { + span: pat.data().span, + gap: gap_as_pat.clone(), + first_range: thir_pat.clone(), + }) + .collect(), + }, + ); + } + } } /// 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 bbe02f94c0a..cdc03eaeb37 100644 --- a/compiler/rustc_pattern_analysis/src/usefulness.rs +++ b/compiler/rustc_pattern_analysis/src/usefulness.rs @@ -242,7 +242,7 @@ //! Therefore `usefulness(tp_1, tp_2, tq)` returns the single witness-tuple `[Variant2(Some(true), 0)]`. //! //! -//! Computing the set of constructors for a type is done in [`TypeCx::ctors_for_ty`]. See +//! Computing the set of constructors for a type is done in [`PatCx::ctors_for_ty`]. See //! the following sections for more accurate versions of the algorithm and corresponding links. //! //! @@ -540,8 +540,8 @@ //! We track in the algorithm whether a given place is known to contain valid data. This is done //! first by inspecting the scrutinee syntactically (which gives us `cx.known_valid_scrutinee`), and //! then by tracking validity of each column of the matrix (which correspond to places) as we -//! recurse into subpatterns. That second part is done through [`ValidityConstraint`], most notably -//! [`ValidityConstraint::specialize`]. +//! recurse into subpatterns. That second part is done through [`PlaceValidity`], most notably +//! [`PlaceValidity::specialize`]. //! //! Having said all that, in practice we don't fully follow what's been presented in this section. //! Let's call "toplevel exception" the case where the match scrutinee itself has type `!` or @@ -716,9 +716,9 @@ use std::fmt; use crate::constructor::{Constructor, ConstructorSet, IntRange}; use crate::pat::{DeconstructedPat, PatId, PatOrWild, WitnessPat}; -use crate::{Captures, MatchArm, PrivateUninhabitedField, TypeCx}; +use crate::{Captures, MatchArm, PatCx, PrivateUninhabitedField}; -use self::ValidityConstraint::*; +use self::PlaceValidity::*; #[cfg(feature = "rustc")] use rustc_data_structures::stack::ensure_sufficient_stack; @@ -728,35 +728,50 @@ pub fn ensure_sufficient_stack<R>(f: impl FnOnce() -> R) -> R { } /// Context that provides information for usefulness checking. -struct UsefulnessCtxt<'a, Cx: TypeCx> { +struct UsefulnessCtxt<'a, Cx: PatCx> { /// The context for type information. tycx: &'a Cx, /// Collect the patterns found useful during usefulness checking. This is used to lint /// unreachable (sub)patterns. useful_subpatterns: FxHashSet<PatId>, + complexity_limit: Option<usize>, + complexity_level: usize, +} + +impl<'a, Cx: PatCx> UsefulnessCtxt<'a, Cx> { + fn increase_complexity_level(&mut self, complexity_add: usize) -> Result<(), Cx::Error> { + self.complexity_level += complexity_add; + if self + .complexity_limit + .is_some_and(|complexity_limit| complexity_limit < self.complexity_level) + { + return self.tycx.complexity_exceeded(); + } + Ok(()) + } } /// Context that provides information local to a place under investigation. -struct PlaceCtxt<'a, Cx: TypeCx> { +struct PlaceCtxt<'a, Cx: PatCx> { cx: &'a Cx, /// Type of the place under investigation. ty: &'a Cx::Ty, } -impl<'a, Cx: TypeCx> Copy for PlaceCtxt<'a, Cx> {} -impl<'a, Cx: TypeCx> Clone for PlaceCtxt<'a, Cx> { +impl<'a, Cx: PatCx> Copy for PlaceCtxt<'a, Cx> {} +impl<'a, Cx: PatCx> Clone for PlaceCtxt<'a, Cx> { fn clone(&self) -> Self { Self { cx: self.cx, ty: self.ty } } } -impl<'a, Cx: TypeCx> fmt::Debug for PlaceCtxt<'a, Cx> { +impl<'a, Cx: PatCx> fmt::Debug for PlaceCtxt<'a, Cx> { fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result { fmt.debug_struct("PlaceCtxt").field("ty", self.ty).finish() } } -impl<'a, Cx: TypeCx> PlaceCtxt<'a, Cx> { +impl<'a, Cx: PatCx> PlaceCtxt<'a, Cx> { fn ctor_arity(&self, ctor: &Constructor<Cx>) -> usize { self.cx.ctor_arity(ctor, self.ty) } @@ -765,18 +780,14 @@ impl<'a, Cx: TypeCx> PlaceCtxt<'a, Cx> { } } -/// Serves two purposes: -/// - in a wildcard, tracks whether the wildcard matches only valid values (i.e. is a binding `_a`) -/// or also invalid values (i.e. is a true `_` pattern). -/// - in the matrix, track whether a given place (aka column) is known to contain a valid value or -/// not. +/// Track whether a given place (aka column) is known to contain a valid value or not. #[derive(Debug, Copy, Clone, PartialEq, Eq)] -pub enum ValidityConstraint { +pub enum PlaceValidity { ValidOnly, MaybeInvalid, } -impl ValidityConstraint { +impl PlaceValidity { pub fn from_bool(is_valid_only: bool) -> Self { if is_valid_only { ValidOnly } else { MaybeInvalid } } @@ -791,7 +802,7 @@ impl ValidityConstraint { /// /// Pending further opsem decisions, the current behavior is: validity is preserved, except /// inside `&` and union fields where validity is reset to `MaybeInvalid`. - fn specialize<Cx: TypeCx>(self, ctor: &Constructor<Cx>) -> Self { + fn specialize<Cx: PatCx>(self, ctor: &Constructor<Cx>) -> Self { // We preserve validity except when we go inside a reference or a union field. if matches!(ctor, Constructor::Ref | Constructor::UnionField) { // Validity of `x: &T` does not imply validity of `*x: T`. @@ -802,7 +813,7 @@ impl ValidityConstraint { } } -impl fmt::Display for ValidityConstraint { +impl fmt::Display for PlaceValidity { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { let s = match self { ValidOnly => "✓", @@ -814,19 +825,19 @@ impl fmt::Display for ValidityConstraint { /// Data about a place under investigation. Its methods contain a lot of the logic used to analyze /// the constructors in the matrix. -struct PlaceInfo<Cx: TypeCx> { +struct PlaceInfo<Cx: PatCx> { /// The type of the place. ty: Cx::Ty, /// Whether the place is a private uninhabited field. If so we skip this field during analysis /// so that we don't observe its emptiness. private_uninhabited: bool, /// Whether the place is known to contain valid data. - validity: ValidityConstraint, + validity: PlaceValidity, /// Whether the place is the scrutinee itself or a subplace of it. is_scrutinee: bool, } -impl<Cx: TypeCx> PlaceInfo<Cx> { +impl<Cx: PatCx> PlaceInfo<Cx> { /// Given a constructor for the current place, we return one `PlaceInfo` for each field of the /// constructor. fn specialize<'a>( @@ -921,7 +932,7 @@ impl<Cx: TypeCx> PlaceInfo<Cx> { } } -impl<Cx: TypeCx> Clone for PlaceInfo<Cx> { +impl<Cx: PatCx> Clone for PlaceInfo<Cx> { fn clone(&self) -> Self { Self { ty: self.ty.clone(), @@ -936,7 +947,7 @@ impl<Cx: TypeCx> Clone for PlaceInfo<Cx> { // The three lifetimes are: // - 'p coming from the input // - Cx global compilation context -struct PatStack<'p, Cx: TypeCx> { +struct PatStack<'p, Cx: PatCx> { // Rows of len 1 are very common, which is why `SmallVec[_; 2]` works well. pats: SmallVec<[PatOrWild<'p, Cx>; 2]>, /// Sometimes we know that as far as this row is concerned, the current case is already handled @@ -945,13 +956,13 @@ struct PatStack<'p, Cx: TypeCx> { relevant: bool, } -impl<'p, Cx: TypeCx> Clone for PatStack<'p, Cx> { +impl<'p, Cx: PatCx> Clone for PatStack<'p, Cx> { fn clone(&self) -> Self { Self { pats: self.pats.clone(), relevant: self.relevant } } } -impl<'p, Cx: TypeCx> PatStack<'p, Cx> { +impl<'p, Cx: PatCx> PatStack<'p, Cx> { fn from_pattern(pat: &'p DeconstructedPat<Cx>) -> Self { PatStack { pats: smallvec![PatOrWild::Pat(pat)], relevant: true } } @@ -986,23 +997,32 @@ impl<'p, Cx: TypeCx> PatStack<'p, Cx> { /// Only call if `ctor.is_covered_by(self.head().ctor())` is true. fn pop_head_constructor( &self, + cx: &Cx, ctor: &Constructor<Cx>, ctor_arity: usize, ctor_is_relevant: bool, - ) -> PatStack<'p, Cx> { + ) -> Result<PatStack<'p, Cx>, Cx::Error> { + let head_pat = self.head(); + if head_pat.as_pat().is_some_and(|pat| pat.arity() > ctor_arity) { + // Arity can be smaller in case of variable-length slices, but mustn't be larger. + return Err(cx.bug(format_args!( + "uncaught type error: pattern {:?} has inconsistent arity (expected arity <= {ctor_arity})", + head_pat.as_pat().unwrap() + ))); + } // We pop the head pattern and push the new fields extracted from the arguments of // `self.head()`. - let mut new_pats = self.head().specialize(ctor, ctor_arity); + let mut new_pats = head_pat.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. let ctor_is_relevant = !matches!(self.head().ctor(), Constructor::Wildcard) || ctor_is_relevant; - PatStack { pats: new_pats, relevant: self.relevant && ctor_is_relevant } + Ok(PatStack { pats: new_pats, relevant: self.relevant && ctor_is_relevant }) } } -impl<'p, Cx: TypeCx> fmt::Debug for PatStack<'p, Cx> { +impl<'p, Cx: PatCx> fmt::Debug for PatStack<'p, Cx> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { // We pretty-print similarly to the `Debug` impl of `Matrix`. write!(f, "+")?; @@ -1015,14 +1035,14 @@ impl<'p, Cx: TypeCx> fmt::Debug for PatStack<'p, Cx> { /// A row of the matrix. #[derive(Clone)] -struct MatrixRow<'p, Cx: TypeCx> { +struct MatrixRow<'p, Cx: PatCx> { // The patterns in the row. pats: PatStack<'p, Cx>, /// Whether the original arm had a guard. This is inherited when specializing. is_under_guard: bool, /// When we specialize, we remember which row of the original matrix produced a given row of the /// specialized matrix. When we unspecialize, we use this to propagate usefulness back up the - /// callstack. + /// callstack. On creation, this stores the index of the original match arm. parent_row: usize, /// False when the matrix is just built. This is set to `true` by /// [`compute_exhaustiveness_and_usefulness`] if the arm is found to be useful. @@ -1035,7 +1055,7 @@ struct MatrixRow<'p, Cx: TypeCx> { intersects: BitSet<usize>, } -impl<'p, Cx: TypeCx> MatrixRow<'p, Cx> { +impl<'p, Cx: PatCx> MatrixRow<'p, Cx> { fn is_empty(&self) -> bool { self.pats.is_empty() } @@ -1068,22 +1088,23 @@ impl<'p, Cx: TypeCx> MatrixRow<'p, Cx> { /// Only call if `ctor.is_covered_by(self.head().ctor())` is true. fn pop_head_constructor( &self, + cx: &Cx, ctor: &Constructor<Cx>, ctor_arity: usize, ctor_is_relevant: bool, parent_row: usize, - ) -> MatrixRow<'p, Cx> { - MatrixRow { - pats: self.pats.pop_head_constructor(ctor, ctor_arity, ctor_is_relevant), + ) -> Result<MatrixRow<'p, Cx>, Cx::Error> { + Ok(MatrixRow { + pats: self.pats.pop_head_constructor(cx, 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`. - } + }) } } -impl<'p, Cx: TypeCx> fmt::Debug for MatrixRow<'p, Cx> { +impl<'p, Cx: PatCx> fmt::Debug for MatrixRow<'p, Cx> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { self.pats.fmt(f) } @@ -1100,7 +1121,7 @@ impl<'p, Cx: TypeCx> fmt::Debug for MatrixRow<'p, Cx> { /// specializing `(,)` and `Some` on a pattern of type `(Option<u32>, bool)`, the first column of /// the matrix will correspond to `scrutinee.0.Some.0` and the second column to `scrutinee.1`. #[derive(Clone)] -struct Matrix<'p, Cx: TypeCx> { +struct Matrix<'p, Cx: PatCx> { /// Vector of rows. The rows must form a rectangular 2D array. Moreover, all the patterns of /// each column must have the same type. Each column corresponds to a place within the /// scrutinee. @@ -1113,7 +1134,7 @@ struct Matrix<'p, Cx: TypeCx> { wildcard_row_is_relevant: bool, } -impl<'p, Cx: TypeCx> Matrix<'p, Cx> { +impl<'p, Cx: PatCx> 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, mut row: MatrixRow<'p, Cx>) { @@ -1130,11 +1151,7 @@ impl<'p, Cx: TypeCx> Matrix<'p, Cx> { } /// Build a new matrix from an iterator of `MatchArm`s. - fn new( - arms: &[MatchArm<'p, Cx>], - scrut_ty: Cx::Ty, - scrut_validity: ValidityConstraint, - ) -> Self { + fn new(arms: &[MatchArm<'p, Cx>], scrut_ty: Cx::Ty, scrut_validity: PlaceValidity) -> Self { let place_info = PlaceInfo { ty: scrut_ty, private_uninhabited: false, @@ -1146,10 +1163,10 @@ impl<'p, Cx: TypeCx> Matrix<'p, Cx> { place_info: smallvec![place_info], wildcard_row_is_relevant: true, }; - for (row_id, arm) in arms.iter().enumerate() { + for (arm_id, arm) in arms.iter().enumerate() { let v = MatrixRow { pats: PatStack::from_pattern(arm.pat), - parent_row: row_id, // dummy, we don't read it + parent_row: arm_id, is_under_guard: arm.has_guard, useful: false, intersects: BitSet::new_empty(0), // Initialized in `Matrix::expand_and_push`. @@ -1202,7 +1219,7 @@ impl<'p, Cx: TypeCx> Matrix<'p, Cx> { }; for (i, row) in self.rows().enumerate() { if ctor.is_covered_by(pcx.cx, row.head().ctor())? { - let new_row = row.pop_head_constructor(ctor, arity, ctor_is_relevant, i); + let new_row = row.pop_head_constructor(pcx.cx, ctor, arity, ctor_is_relevant, i)?; matrix.expand_and_push(new_row); } } @@ -1239,7 +1256,7 @@ impl<'p, Cx: TypeCx> Matrix<'p, Cx> { /// + _ + [_, _, tail @ ..] + /// | ✓ | ? | // column validity /// ``` -impl<'p, Cx: TypeCx> fmt::Debug for Matrix<'p, Cx> { +impl<'p, Cx: PatCx> fmt::Debug for Matrix<'p, Cx> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { write!(f, "\n")?; @@ -1330,15 +1347,15 @@ impl<'p, Cx: TypeCx> fmt::Debug for Matrix<'p, Cx> { /// /// See the top of the file for more detailed explanations and examples. #[derive(Debug)] -struct WitnessStack<Cx: TypeCx>(Vec<WitnessPat<Cx>>); +struct WitnessStack<Cx: PatCx>(Vec<WitnessPat<Cx>>); -impl<Cx: TypeCx> Clone for WitnessStack<Cx> { +impl<Cx: PatCx> Clone for WitnessStack<Cx> { fn clone(&self) -> Self { Self(self.0.clone()) } } -impl<Cx: TypeCx> WitnessStack<Cx> { +impl<Cx: PatCx> WitnessStack<Cx> { /// Asserts that the witness contains a single pattern, and returns it. fn single_pattern(self) -> WitnessPat<Cx> { assert_eq!(self.0.len(), 1); @@ -1383,15 +1400,15 @@ impl<Cx: TypeCx> WitnessStack<Cx> { /// Just as the `Matrix` starts with a single column, by the end of the algorithm, this has a single /// column, which contains the patterns that are missing for the match to be exhaustive. #[derive(Debug)] -struct WitnessMatrix<Cx: TypeCx>(Vec<WitnessStack<Cx>>); +struct WitnessMatrix<Cx: PatCx>(Vec<WitnessStack<Cx>>); -impl<Cx: TypeCx> Clone for WitnessMatrix<Cx> { +impl<Cx: PatCx> Clone for WitnessMatrix<Cx> { fn clone(&self) -> Self { Self(self.0.clone()) } } -impl<Cx: TypeCx> WitnessMatrix<Cx> { +impl<Cx: PatCx> WitnessMatrix<Cx> { /// New matrix with no witnesses. fn empty() -> Self { WitnessMatrix(Vec::new()) @@ -1465,8 +1482,8 @@ impl<Cx: TypeCx> WitnessMatrix<Cx> { /// /// We can however get false negatives because exhaustiveness does not explore all cases. See the /// section on relevancy at the top of the file. -fn collect_overlapping_range_endpoints<'p, Cx: TypeCx>( - mcx: &mut UsefulnessCtxt<'_, Cx>, +fn collect_overlapping_range_endpoints<'p, Cx: PatCx>( + cx: &Cx, overlap_range: IntRange, matrix: &Matrix<'p, Cx>, specialized_matrix: &Matrix<'p, Cx>, @@ -1499,11 +1516,11 @@ fn collect_overlapping_range_endpoints<'p, Cx: TypeCx>( .map(|&(_, pat)| pat) .collect(); if !overlaps_with.is_empty() { - mcx.tycx.lint_overlapping_range_endpoints(pat, overlap_range, &overlaps_with); + cx.lint_overlapping_range_endpoints(pat, overlap_range, &overlaps_with); } } suffixes.push((child_row_id, pat)) - } else if this_range.hi == overlap.plus_one() { + } else if Some(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() { @@ -1515,7 +1532,7 @@ fn collect_overlapping_range_endpoints<'p, Cx: TypeCx>( .map(|&(_, pat)| pat) .collect(); if !overlaps_with.is_empty() { - mcx.tycx.lint_overlapping_range_endpoints(pat, overlap_range, &overlaps_with); + cx.lint_overlapping_range_endpoints(pat, overlap_range, &overlaps_with); } } prefixes.push((child_row_id, pat)) @@ -1523,6 +1540,33 @@ fn collect_overlapping_range_endpoints<'p, Cx: TypeCx>( } } +/// Collect ranges that have a singleton gap between them. +fn collect_non_contiguous_range_endpoints<'p, Cx: PatCx>( + cx: &Cx, + gap_range: &IntRange, + matrix: &Matrix<'p, Cx>, +) { + let gap = gap_range.lo; + // Ranges that look like `lo..gap`. + let mut onebefore: SmallVec<[_; 1]> = Default::default(); + // Ranges that start on `gap+1` or singletons `gap+1`. + let mut oneafter: SmallVec<[_; 1]> = Default::default(); + // Look through the column for ranges near the gap. + for pat in matrix.heads() { + let PatOrWild::Pat(pat) = pat else { continue }; + let Constructor::IntRange(this_range) = pat.ctor() else { continue }; + if gap == this_range.hi { + onebefore.push(pat) + } else if gap.plus_one() == Some(this_range.lo) { + oneafter.push(pat) + } + } + + for pat_before in onebefore { + cx.lint_non_contiguous_range_endpoints(pat_before, *gap_range, oneafter.as_slice()); + } +} + /// The core of the algorithm. /// /// This recursively computes witnesses of the non-exhaustiveness of `matrix` (if any). Also tracks @@ -1538,7 +1582,7 @@ fn collect_overlapping_range_endpoints<'p, Cx: TypeCx>( /// (using `apply_constructor` and by updating `row.useful` for each parent row). /// This is all explained at the top of the file. #[instrument(level = "debug", skip(mcx), ret)] -fn compute_exhaustiveness_and_usefulness<'a, 'p, Cx: TypeCx>( +fn compute_exhaustiveness_and_usefulness<'a, 'p, Cx: PatCx>( mcx: &mut UsefulnessCtxt<'a, Cx>, matrix: &mut Matrix<'p, Cx>, ) -> Result<WitnessMatrix<Cx>, Cx::Error> { @@ -1552,6 +1596,7 @@ fn compute_exhaustiveness_and_usefulness<'a, 'p, Cx: TypeCx>( } let Some(place) = matrix.head_place() else { + mcx.increase_complexity_level(matrix.rows().len())?; // The base case: there are no columns in the matrix. We are morally pattern-matching on (). // A row is useful iff it has no (unguarded) rows above it. let mut useful = true; // Whether the next row is useful. @@ -1602,13 +1647,24 @@ fn compute_exhaustiveness_and_usefulness<'a, 'p, Cx: TypeCx>( && 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); + collect_overlapping_range_endpoints(mcx.tycx, overlap_range, matrix, &spec_matrix); } } matrix.unspecialize(spec_matrix); } + // Detect singleton gaps between ranges. + if missing_ctors.iter().any(|c| matches!(c, Constructor::IntRange(..))) { + for missing in &missing_ctors { + if let Constructor::IntRange(gap) = missing { + if gap.is_singleton() { + collect_non_contiguous_range_endpoints(mcx.tycx, gap, matrix); + } + } + } + } + // Record usefulness in the patterns. for row in matrix.rows() { if row.useful { @@ -1623,7 +1679,7 @@ fn compute_exhaustiveness_and_usefulness<'a, 'p, Cx: TypeCx>( /// Indicates whether or not a given arm is useful. #[derive(Clone, Debug)] -pub enum Usefulness<'p, Cx: TypeCx> { +pub enum Usefulness<'p, Cx: PatCx> { /// The arm is useful. This additionally carries a set of or-pattern branches that have been /// found to be redundant despite the overall arm being useful. Used only in the presence of /// or-patterns, otherwise it stays empty. @@ -1634,17 +1690,18 @@ pub enum Usefulness<'p, Cx: TypeCx> { } /// Report whether this pattern was found useful, and its subpatterns that were not useful if any. -fn collect_pattern_usefulness<'p, Cx: TypeCx>( +fn collect_pattern_usefulness<'p, Cx: PatCx>( useful_subpatterns: &FxHashSet<PatId>, pat: &'p DeconstructedPat<Cx>, ) -> Usefulness<'p, Cx> { - fn pat_is_useful<'p, Cx: TypeCx>( + fn pat_is_useful<'p, Cx: PatCx>( useful_subpatterns: &FxHashSet<PatId>, pat: &'p DeconstructedPat<Cx>, ) -> bool { if useful_subpatterns.contains(&pat.uid) { true - } else if pat.is_or_pat() && pat.iter_fields().any(|f| pat_is_useful(useful_subpatterns, f)) + } else if pat.is_or_pat() + && pat.iter_fields().any(|f| pat_is_useful(useful_subpatterns, &f.pat)) { // We always expand or patterns in the matrix, so we will never see the actual // or-pattern (the one with constructor `Or`) in the column. As such, it will not be @@ -1675,23 +1732,32 @@ fn collect_pattern_usefulness<'p, Cx: TypeCx>( } /// The output of checking a match for exhaustiveness and arm usefulness. -pub struct UsefulnessReport<'p, Cx: TypeCx> { +pub struct UsefulnessReport<'p, Cx: PatCx> { /// For each arm of the input, whether that arm is useful after the arms above it. pub arm_usefulness: Vec<(MatchArm<'p, Cx>, Usefulness<'p, Cx>)>, /// If the match is exhaustive, this is empty. If not, this contains witnesses for the lack of /// exhaustiveness. pub non_exhaustiveness_witnesses: Vec<WitnessPat<Cx>>, + /// For each arm, a set of indices of arms above it that have non-empty intersection, i.e. there + /// is a value matched by both arms. This may miss real intersections. + pub arm_intersections: Vec<BitSet<usize>>, } /// Computes whether a match is exhaustive and which of its arms are useful. #[instrument(skip(tycx, arms), level = "debug")] -pub fn compute_match_usefulness<'p, Cx: TypeCx>( +pub fn compute_match_usefulness<'p, Cx: PatCx>( tycx: &Cx, arms: &[MatchArm<'p, Cx>], scrut_ty: Cx::Ty, - scrut_validity: ValidityConstraint, + scrut_validity: PlaceValidity, + complexity_limit: Option<usize>, ) -> Result<UsefulnessReport<'p, Cx>, Cx::Error> { - let mut cx = UsefulnessCtxt { tycx, useful_subpatterns: FxHashSet::default() }; + let mut cx = UsefulnessCtxt { + tycx, + useful_subpatterns: FxHashSet::default(), + complexity_limit, + complexity_level: 0, + }; let mut matrix = Matrix::new(arms, scrut_ty, scrut_validity); let non_exhaustiveness_witnesses = compute_exhaustiveness_and_usefulness(&mut cx, &mut matrix)?; @@ -1706,5 +1772,19 @@ pub fn compute_match_usefulness<'p, Cx: TypeCx>( }) .collect(); - Ok(UsefulnessReport { arm_usefulness, non_exhaustiveness_witnesses }) + let mut arm_intersections: Vec<_> = + arms.iter().enumerate().map(|(i, _)| BitSet::new_empty(i)).collect(); + for row in matrix.rows() { + let arm_id = row.parent_row; + for intersection in row.intersects.iter() { + // Convert the matrix row ids into arm ids (they can differ because we expand or-patterns). + let arm_intersection = matrix.rows[intersection].parent_row; + // Note: self-intersection can happen with or-patterns. + if arm_intersection != arm_id { + arm_intersections[arm_id].insert(arm_intersection); + } + } + } + + Ok(UsefulnessReport { arm_usefulness, non_exhaustiveness_witnesses, arm_intersections }) } |