diff options
Diffstat (limited to 'compiler/rustc_pattern_analysis/src')
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/constructor.rs | 8 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/errors.rs | 55 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/lib.rs | 44 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/lints.rs | 7 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/pat.rs | 33 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/rustc.rs | 286 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/rustc/print.rs | 160 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/usefulness.rs | 379 |
8 files changed, 619 insertions, 353 deletions
diff --git a/compiler/rustc_pattern_analysis/src/constructor.rs b/compiler/rustc_pattern_analysis/src/constructor.rs index fb103705475..e4edd7befb7 100644 --- a/compiler/rustc_pattern_analysis/src/constructor.rs +++ b/compiler/rustc_pattern_analysis/src/constructor.rs @@ -180,16 +180,14 @@ use std::cmp::{self, max, min, Ordering}; use std::fmt; use std::iter::once; -use smallvec::SmallVec; - use rustc_apfloat::ieee::{DoubleS, HalfS, IeeeFloat, QuadS, SingleS}; use rustc_index::bit_set::{BitSet, GrowableBitSet}; use rustc_index::IndexVec; +use smallvec::SmallVec; use self::Constructor::*; use self::MaybeInfiniteInt::*; use self::SliceKind::*; - use crate::PatCx; /// Whether we have seen a constructor in the column or not. @@ -290,7 +288,7 @@ impl IntRange { /// Best effort; will not know that e.g. `255u8..` is a singleton. 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)`. + // to infinite, this correctly only detects ranges that contain exactly one `Finite(x)`. self.lo.plus_one() == Some(self.hi) } @@ -904,7 +902,7 @@ impl<Cx: PatCx> Constructor<Cx> { // 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())?; + write!(f, "&{:?}", fields.next().unwrap())?; } Slice(slice) => { write!(f, "[")?; diff --git a/compiler/rustc_pattern_analysis/src/errors.rs b/compiler/rustc_pattern_analysis/src/errors.rs index 27f227e6d9c..1f7852e5190 100644 --- a/compiler/rustc_pattern_analysis/src/errors.rs +++ b/compiler/rustc_pattern_analysis/src/errors.rs @@ -1,6 +1,5 @@ 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; @@ -8,18 +7,18 @@ use crate::rustc::{RustcPatCtxt, WitnessPat}; #[derive(Subdiagnostic)] #[label(pattern_analysis_uncovered)] -pub struct Uncovered<'tcx> { +pub struct Uncovered { #[primary_span] span: Span, count: usize, - witness_1: Pat<'tcx>, - witness_2: Pat<'tcx>, - witness_3: Pat<'tcx>, + witness_1: String, // a printed pattern + witness_2: String, // a printed pattern + witness_3: String, // a printed pattern remainder: usize, } -impl<'tcx> Uncovered<'tcx> { - pub fn new<'p>( +impl Uncovered { + pub fn new<'p, 'tcx>( span: Span, cx: &RustcPatCtxt<'p, 'tcx>, witnesses: Vec<WitnessPat<'p, 'tcx>>, @@ -27,19 +26,13 @@ impl<'tcx> Uncovered<'tcx> { where 'tcx: 'p, { - let witness_1 = cx.hoist_witness_pat(witnesses.get(0).unwrap()); + let witness_1 = cx.print_witness_pat(witnesses.get(0).unwrap()); Self { span, count: witnesses.len(), // Substitute dummy values if witnesses is smaller than 3. These will never be read. - witness_2: witnesses - .get(1) - .map(|w| cx.hoist_witness_pat(w)) - .unwrap_or_else(|| witness_1.clone()), - witness_3: witnesses - .get(2) - .map(|w| cx.hoist_witness_pat(w)) - .unwrap_or_else(|| witness_1.clone()), + witness_2: witnesses.get(1).map(|w| cx.print_witness_pat(w)).unwrap_or_default(), + witness_3: witnesses.get(2).map(|w| cx.print_witness_pat(w)).unwrap_or_default(), witness_1, remainder: witnesses.len().saturating_sub(3), } @@ -49,19 +42,19 @@ impl<'tcx> Uncovered<'tcx> { #[derive(LintDiagnostic)] #[diag(pattern_analysis_overlapping_range_endpoints)] #[note] -pub struct OverlappingRangeEndpoints<'tcx> { +pub struct OverlappingRangeEndpoints { #[label] pub range: Span, #[subdiagnostic] - pub overlap: Vec<Overlap<'tcx>>, + pub overlap: Vec<Overlap>, } -pub struct Overlap<'tcx> { +pub struct Overlap { pub span: Span, - pub range: Pat<'tcx>, + pub range: String, // a printed pattern } -impl<'tcx> Subdiagnostic for Overlap<'tcx> { +impl Subdiagnostic for Overlap { fn add_to_diag_with<G: EmissionGuarantee, F: SubdiagMessageOp<G>>( self, diag: &mut Diag<'_, G>, @@ -78,38 +71,38 @@ impl<'tcx> Subdiagnostic for Overlap<'tcx> { #[derive(LintDiagnostic)] #[diag(pattern_analysis_excluside_range_missing_max)] -pub struct ExclusiveRangeMissingMax<'tcx> { +pub struct ExclusiveRangeMissingMax { #[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>, + pub max: String, // a printed pattern } #[derive(LintDiagnostic)] #[diag(pattern_analysis_excluside_range_missing_gap)] -pub struct ExclusiveRangeMissingGap<'tcx> { +pub struct ExclusiveRangeMissingGap { #[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>, + pub gap: String, // a printed pattern /// 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 gap_with: Vec<GappedRange>, } -pub struct GappedRange<'tcx> { +pub struct GappedRange { pub span: Span, - pub gap: Pat<'tcx>, - pub first_range: Pat<'tcx>, + pub gap: String, // a printed pattern + pub first_range: String, // a printed pattern } -impl<'tcx> Subdiagnostic for GappedRange<'tcx> { +impl Subdiagnostic for GappedRange { fn add_to_diag_with<G: EmissionGuarantee, F: SubdiagMessageOp<G>>( self, diag: &mut Diag<'_, G>, @@ -134,7 +127,7 @@ impl<'tcx> Subdiagnostic for GappedRange<'tcx> { pub(crate) struct NonExhaustiveOmittedPattern<'tcx> { pub scrut_ty: Ty<'tcx>, #[subdiagnostic] - pub uncovered: Uncovered<'tcx>, + pub uncovered: Uncovered, } #[derive(LintDiagnostic)] diff --git a/compiler/rustc_pattern_analysis/src/lib.rs b/compiler/rustc_pattern_analysis/src/lib.rs index c9590ad06b0..fec44d5af55 100644 --- a/compiler/rustc_pattern_analysis/src/lib.rs +++ b/compiler/rustc_pattern_analysis/src/lib.rs @@ -1,8 +1,12 @@ -//! Analysis of patterns, notably match exhaustiveness checking. +//! Analysis of patterns, notably match exhaustiveness checking. The main entrypoint for this crate +//! is [`usefulness::compute_match_usefulness`]. For rustc-specific types and entrypoints, see the +//! [`rustc`] module. // tidy-alphabetical-start #![allow(rustc::diagnostic_outside_of_impl)] #![allow(rustc::untranslatable_diagnostic)] +#![cfg_attr(feature = "rustc", feature(let_chains))] +#![warn(unreachable_pub)] // tidy-alphabetical-end pub mod constructor; @@ -21,18 +25,10 @@ rustc_fluent_macro::fluent_messages! { "../messages.ftl" } use std::fmt; -// Re-exports to avoid rustc_index version issues. -pub use rustc_index::Idx; -pub use rustc_index::IndexVec; - -#[cfg(feature = "rustc")] -use rustc_middle::ty::Ty; -#[cfg(feature = "rustc")] -use rustc_span::ErrorGuaranteed; +pub use rustc_index::{Idx, IndexVec}; // re-exported to avoid rustc_index version issues use crate::constructor::{Constructor, ConstructorSet, IntRange}; use crate::pat::DeconstructedPat; -use crate::pat_column::PatternColumn; pub trait Captures<'a> {} impl<'a, T: ?Sized> Captures<'a> for T {} @@ -60,7 +56,6 @@ pub trait PatCx: Sized + fmt::Debug { type PatData: Clone; fn is_exhaustive_patterns_feature_on(&self) -> bool; - fn is_min_exhaustive_patterns_feature_on(&self) -> bool; /// The number of fields for this constructor. fn ctor_arity(&self, ctor: &Constructor<Self>, ty: &Self::Ty) -> usize; @@ -130,30 +125,3 @@ impl<'p, Cx: PatCx> Clone 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: &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 = 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. - if tycx.refutable && report.non_exhaustiveness_witnesses.is_empty() { - let pat_column = PatternColumn::new(arms); - lint_nonexhaustive_missing_variants(tycx, arms, &pat_column, scrut_ty)?; - } - - Ok(report) -} diff --git a/compiler/rustc_pattern_analysis/src/lints.rs b/compiler/rustc_pattern_analysis/src/lints.rs index 892aacd7ac5..6bcef0ec879 100644 --- a/compiler/rustc_pattern_analysis/src/lints.rs +++ b/compiler/rustc_pattern_analysis/src/lints.rs @@ -1,11 +1,12 @@ +use rustc_session::lint::builtin::NON_EXHAUSTIVE_OMITTED_PATTERNS; +use rustc_span::ErrorGuaranteed; +use tracing::instrument; + use crate::constructor::Constructor; use crate::errors::{NonExhaustiveOmittedPattern, NonExhaustiveOmittedPatternLintOnArm, Uncovered}; use crate::pat_column::PatternColumn; use crate::rustc::{RevealedTy, RustcPatCtxt, WitnessPat}; use crate::MatchArm; -use rustc_session::lint::builtin::NON_EXHAUSTIVE_OMITTED_PATTERNS; -use rustc_span::ErrorGuaranteed; -use tracing::instrument; /// Traverse the patterns to collect any variants of a non_exhaustive enum that fail to be mentioned /// in a given column. diff --git a/compiler/rustc_pattern_analysis/src/pat.rs b/compiler/rustc_pattern_analysis/src/pat.rs index 5e75976621e..d91deab160c 100644 --- a/compiler/rustc_pattern_analysis/src/pat.rs +++ b/compiler/rustc_pattern_analysis/src/pat.rs @@ -5,13 +5,12 @@ use std::fmt; use smallvec::{smallvec, SmallVec}; +use self::Constructor::*; use crate::constructor::{Constructor, Slice, SliceKind}; use crate::{PatCx, PrivateUninhabitedField}; -use self::Constructor::*; - /// A globally unique id to distinguish patterns. -#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)] +#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)] pub(crate) struct PatId(u32); impl PatId { fn new() -> Self { @@ -147,6 +146,21 @@ impl<Cx: PatCx> fmt::Debug for DeconstructedPat<Cx> { } } +/// Delegate to `uid`. +impl<Cx: PatCx> PartialEq for DeconstructedPat<Cx> { + fn eq(&self, other: &Self) -> bool { + self.uid == other.uid + } +} +/// Delegate to `uid`. +impl<Cx: PatCx> Eq for DeconstructedPat<Cx> {} +/// Delegate to `uid`. +impl<Cx: PatCx> std::hash::Hash for DeconstructedPat<Cx> { + fn hash<H: std::hash::Hasher>(&self, state: &mut H) { + self.uid.hash(state); + } +} + /// Represents either a pattern obtained from user input or a wildcard constructed during the /// algorithm. Do not use `Wild` to represent a wildcard pattern comping from user input. /// @@ -190,7 +204,18 @@ impl<'p, Cx: PatCx> PatOrWild<'p, Cx> { } } - /// Expand this (possibly-nested) or-pattern into its alternatives. + /// Expand this or-pattern into its alternatives. This only expands one or-pattern; use + /// `flatten_or_pat` to recursively expand nested or-patterns. + pub(crate) fn expand_or_pat(self) -> SmallVec<[Self; 1]> { + match self { + PatOrWild::Pat(pat) if pat.is_or_pat() => { + pat.iter_fields().map(|ipat| PatOrWild::Pat(&ipat.pat)).collect() + } + _ => smallvec![self], + } + } + + /// Recursively 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 diff --git a/compiler/rustc_pattern_analysis/src/rustc.rs b/compiler/rustc_pattern_analysis/src/rustc.rs index d4dd4dd858c..d7885e05a2f 100644 --- a/compiler/rustc_pattern_analysis/src/rustc.rs +++ b/compiler/rustc_pattern_analysis/src/rustc.rs @@ -7,7 +7,7 @@ use rustc_hir::HirId; use rustc_index::{Idx, IndexVec}; use rustc_middle::middle::stability::EvalResult; use rustc_middle::mir::{self, Const}; -use rustc_middle::thir::{self, FieldPat, Pat, PatKind, PatRange, PatRangeBoundary}; +use rustc_middle::thir::{self, Pat, PatKind, PatRange, PatRangeBoundary}; use rustc_middle::ty::layout::IntegerExt; use rustc_middle::ty::{ self, FieldDef, OpaqueTypeKey, ScalarInt, Ty, TyCtxt, TypeVisitableExt, VariantDef, @@ -17,18 +17,25 @@ use rustc_session::lint; use rustc_span::{ErrorGuaranteed, Span, DUMMY_SP}; use rustc_target::abi::{FieldIdx, Integer, VariantIdx, FIRST_VARIANT}; +use crate::constructor::Constructor::*; use crate::constructor::{ IntRange, MaybeInfiniteInt, OpaqueId, RangeEnd, Slice, SliceKind, VariantVisibility, }; +use crate::lints::lint_nonexhaustive_missing_variants; +use crate::pat_column::PatternColumn; +use crate::rustc::print::EnumInfo; +use crate::usefulness::{compute_match_usefulness, PlaceValidity}; use crate::{errors, Captures, PatCx, PrivateUninhabitedField}; -use crate::constructor::Constructor::*; +mod print; // Re-export rustc-specific versions of all these types. 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 RedundancyExplanation<'p, 'tcx> = + crate::usefulness::RedundancyExplanation<'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, RustcPatCtxt<'p, 'tcx>>; @@ -40,9 +47,15 @@ pub type WitnessPat<'p, 'tcx> = crate::pat::WitnessPat<RustcPatCtxt<'p, 'tcx>>; /// /// Use `.inner()` or deref to get to the `Ty<'tcx>`. #[repr(transparent)] -#[derive(Clone, Copy)] +#[derive(Clone, Copy, PartialEq, Eq, Hash)] pub struct RevealedTy<'tcx>(Ty<'tcx>); +impl<'tcx> fmt::Display for RevealedTy<'tcx> { + fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result { + self.0.fmt(fmt) + } +} + impl<'tcx> fmt::Debug for RevealedTy<'tcx> { fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result { self.0.fmt(fmt) @@ -225,9 +238,7 @@ impl<'p, 'tcx: 'p> RustcPatCtxt<'p, 'tcx> { let tys = cx.variant_sub_tys(ty, variant).map(|(field, ty)| { let is_visible = adt.is_enum() || field.vis.is_accessible_from(cx.module, cx.tcx); - let is_uninhabited = (cx.tcx.features().exhaustive_patterns - || cx.tcx.features().min_exhaustive_patterns) - && cx.is_uninhabited(*ty); + let is_uninhabited = cx.is_uninhabited(*ty); let skip = is_uninhabited && (!is_visible || is_non_exhaustive); (ty, PrivateUninhabitedField(skip)) }); @@ -402,7 +413,7 @@ impl<'p, 'tcx: 'p> RustcPatCtxt<'p, 'tcx> { | ty::Foreign(_) | ty::RawPtr(_, _) | ty::FnDef(_, _) - | ty::FnPtr(_) + | ty::FnPtr(..) | ty::Pat(_, _) | ty::Dynamic(_, _, _) | ty::Closure(..) @@ -462,7 +473,12 @@ impl<'p, 'tcx: 'p> RustcPatCtxt<'p, 'tcx> { // This is a box pattern. ty::Adt(adt, ..) if adt.is_box() => Struct, ty::Ref(..) => Ref, - _ => bug!("pattern has unexpected type: pat: {:?}, ty: {:?}", pat, ty), + _ => span_bug!( + pat.span, + "pattern has unexpected type: pat: {:?}, ty: {:?}", + pat.kind, + ty.inner() + ), }; } PatKind::DerefPattern { .. } => { @@ -518,7 +534,12 @@ impl<'p, 'tcx: 'p> RustcPatCtxt<'p, 'tcx> { .map(|ipat| self.lower_pat(&ipat.pattern).at_index(ipat.field.index())) .collect(); } - _ => bug!("pattern has unexpected type: pat: {:?}, ty: {:?}", pat, ty), + _ => span_bug!( + pat.span, + "pattern has unexpected type: pat: {:?}, ty: {}", + pat.kind, + ty.inner() + ), } } PatKind::Constant { value } => { @@ -663,7 +684,7 @@ impl<'p, 'tcx: 'p> RustcPatCtxt<'p, 'tcx> { } } } - _ => bug!("invalid type for range pattern: {}", ty.inner()), + _ => span_bug!(pat.span, "invalid type for range pattern: {}", ty.inner()), }; fields = vec![]; arity = 0; @@ -674,7 +695,7 @@ impl<'p, 'tcx: 'p> RustcPatCtxt<'p, 'tcx> { Some(length.eval_target_usize(cx.tcx, cx.param_env) as usize) } ty::Slice(_) => None, - _ => span_bug!(pat.span, "bad ty {:?} for slice pattern", ty), + _ => span_bug!(pat.span, "bad ty {} for slice pattern", ty.inner()), }; let kind = if slice.is_some() { SliceKind::VarLen(prefix.len(), suffix.len()) @@ -723,7 +744,7 @@ impl<'p, 'tcx: 'p> RustcPatCtxt<'p, 'tcx> { /// Note: it is possible to get `isize/usize::MAX+1` here, as explained in the doc for /// [`IntRange::split`]. This cannot be represented as a `Const`, so we represent it with /// `PosInfinity`. - pub(crate) fn hoist_pat_range_bdy( + fn hoist_pat_range_bdy( &self, miint: MaybeInfiniteInt, ty: RevealedTy<'tcx>, @@ -753,16 +774,16 @@ impl<'p, 'tcx: 'p> RustcPatCtxt<'p, 'tcx> { } } - /// Convert back to a `thir::Pat` for diagnostic purposes. - pub(crate) fn hoist_pat_range(&self, range: &IntRange, ty: RevealedTy<'tcx>) -> Pat<'tcx> { + /// Prints an [`IntRange`] to a string for diagnostic purposes. + fn print_pat_range(&self, range: &IntRange, ty: RevealedTy<'tcx>) -> String { use MaybeInfiniteInt::*; let cx = self; - let kind = if matches!((range.lo, range.hi), (NegInfinity, PosInfinity)) { - PatKind::Wild + if matches!((range.lo, range.hi), (NegInfinity, PosInfinity)) { + "_".to_string() } else if range.is_singleton() { let lo = cx.hoist_pat_range_bdy(range.lo, ty); let value = lo.as_finite().unwrap(); - PatKind::Constant { value } + value.to_string() } else { // We convert to an inclusive range for diagnostics. let mut end = rustc_hir::RangeEnd::Included; @@ -785,90 +806,96 @@ impl<'p, 'tcx: 'p> RustcPatCtxt<'p, 'tcx> { range.hi }; let hi = cx.hoist_pat_range_bdy(hi, ty); - PatKind::Range(Box::new(PatRange { lo, hi, end, ty: ty.inner() })) - }; - - Pat { ty: ty.inner(), span: DUMMY_SP, kind } + PatRange { lo, hi, end, ty: ty.inner() }.to_string() + } } - /// Convert back to a `thir::Pat` for diagnostic purposes. This panics for patterns that don't - /// appear in diagnostics, like float ranges. - pub fn hoist_witness_pat(&self, pat: &WitnessPat<'p, 'tcx>) -> Pat<'tcx> { + + /// Prints a [`WitnessPat`] to an owned string, for diagnostic purposes. + /// + /// This panics for patterns that don't appear in diagnostics, like float ranges. + pub fn print_witness_pat(&self, pat: &WitnessPat<'p, 'tcx>) -> String { let cx = self; - let is_wildcard = |pat: &Pat<'_>| matches!(pat.kind, PatKind::Wild); - 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()), - Struct | Variant(_) | UnionField => match pat.ty().kind() { - ty::Tuple(..) => PatKind::Leaf { - subpatterns: subpatterns - .enumerate() - .map(|(i, pattern)| FieldPat { field: FieldIdx::new(i), pattern }) - .collect(), - }, - ty::Adt(adt_def, _) if adt_def.is_box() => { - // Without `box_patterns`, the only legal pattern of type `Box` is `_` (outside - // of `std`). So this branch is only reachable when the feature is enabled and - // the pattern is a box pattern. - PatKind::Deref { subpattern: subpatterns.next().unwrap() } - } - ty::Adt(adt_def, args) => { - 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 }) - .collect(); + let print = |p| cx.print_witness_pat(p); + match pat.ctor() { + Bool(b) => b.to_string(), + Str(s) => s.to_string(), + IntRange(range) => return self.print_pat_range(range, *pat.ty()), + Struct if pat.ty().is_box() => { + // Outside of the `alloc` crate, the only way to create a struct pattern + // of type `Box` is to use a `box` pattern via #[feature(box_patterns)]. + format!("box {}", print(&pat.fields[0])) + } + Struct | Variant(_) | UnionField => { + let enum_info = match *pat.ty().kind() { + ty::Adt(adt_def, _) if adt_def.is_enum() => EnumInfo::Enum { + adt_def, + variant_index: RustcPatCtxt::variant_index_for_adt(pat.ctor(), adt_def), + }, + ty::Adt(..) | ty::Tuple(..) => EnumInfo::NotEnum, + _ => bug!("unexpected ctor for type {:?} {:?}", pat.ctor(), *pat.ty()), + }; - if adt_def.is_enum() { - PatKind::Variant { adt_def: *adt_def, args, variant_index, subpatterns } - } else { - PatKind::Leaf { subpatterns } - } - } - _ => 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 - // literal pattern will never be reported as a non-exhaustiveness witness, so we - // ignore this issue. - Ref => PatKind::Deref { subpattern: subpatterns.next().unwrap() }, + let subpatterns = pat + .iter_fields() + .enumerate() + .map(|(i, pat)| print::FieldPat { + field: FieldIdx::new(i), + pattern: print(pat), + is_wildcard: would_print_as_wildcard(cx.tcx, pat), + }) + .collect::<Vec<_>>(); + + let mut s = String::new(); + print::write_struct_like( + &mut s, + self.tcx, + pat.ty().inner(), + &enum_info, + &subpatterns, + ) + .unwrap(); + s + } + Ref => { + let mut s = String::new(); + print::write_ref_like(&mut s, pat.ty().inner(), &print(&pat.fields[0])).unwrap(); + s + } Slice(slice) => { - match slice.kind { - SliceKind::FixedLen(_) => PatKind::Slice { - prefix: subpatterns.collect(), - slice: None, - suffix: Box::new([]), - }, - SliceKind::VarLen(prefix, _) => { - let mut subpatterns = subpatterns.peekable(); - let mut prefix: Vec<_> = subpatterns.by_ref().take(prefix).collect(); - if slice.array_len.is_some() { - // Improves diagnostics a bit: if the type is a known-size array, instead - // of reporting `[x, _, .., _, y]`, we prefer to report `[x, .., y]`. - // This is incorrect if the size is not known, since `[_, ..]` captures - // arrays of lengths `>= 1` whereas `[..]` captures any length. - while !prefix.is_empty() && is_wildcard(prefix.last().unwrap()) { - prefix.pop(); - } - while subpatterns.peek().is_some() - && is_wildcard(subpatterns.peek().unwrap()) - { - subpatterns.next(); - } - } - let suffix: Box<[_]> = subpatterns.collect(); - let wild = Pat::wildcard_from_ty(pat.ty().inner()); - PatKind::Slice { - prefix: prefix.into_boxed_slice(), - slice: Some(Box::new(wild)), - suffix, - } + let (prefix_len, has_dot_dot) = match slice.kind { + SliceKind::FixedLen(len) => (len, false), + SliceKind::VarLen(prefix_len, _) => (prefix_len, true), + }; + + let (mut prefix, mut suffix) = pat.fields.split_at(prefix_len); + + // If the pattern contains a `..`, but is applied to values of statically-known + // length (arrays), then we can slightly simplify diagnostics by merging any + // adjacent wildcard patterns into the `..`: `[x, _, .., _, y]` => `[x, .., y]`. + // (This simplification isn't allowed for slice values, because in that case + // `[x, .., y]` would match some slices that `[x, _, .., _, y]` would not.) + if has_dot_dot && slice.array_len.is_some() { + while let [rest @ .., last] = prefix + && would_print_as_wildcard(cx.tcx, last) + { + prefix = rest; + } + while let [first, rest @ ..] = suffix + && would_print_as_wildcard(cx.tcx, first) + { + suffix = rest; } } + + let prefix = prefix.iter().map(print).collect::<Vec<_>>(); + let suffix = suffix.iter().map(print).collect::<Vec<_>>(); + + let mut s = String::new(); + print::write_slice_like(&mut s, &prefix, has_dot_dot, &suffix).unwrap(); + s } - &Str(value) => PatKind::Constant { value }, - Never if self.tcx.features().never_patterns => PatKind::Never, - Never | Wildcard | NonExhaustive | Hidden | PrivateUninhabited => PatKind::Wild, + Never if self.tcx.features().never_patterns => "!".to_string(), + Never | Wildcard | NonExhaustive | Hidden | PrivateUninhabited => "_".to_string(), Missing { .. } => bug!( "trying to convert a `Missing` constructor into a `Pat`; this is probably a bug, `Missing` should have been processed in `apply_constructors`" @@ -876,9 +903,23 @@ impl<'p, 'tcx: 'p> RustcPatCtxt<'p, 'tcx> { F16Range(..) | F32Range(..) | F64Range(..) | F128Range(..) | Opaque(..) | Or => { bug!("can't convert to pattern: {:?}", pat) } - }; + } + } +} - Pat { ty: pat.ty().inner(), span: DUMMY_SP, kind } +/// Returns `true` if the given pattern would be printed as a wildcard (`_`). +fn would_print_as_wildcard(tcx: TyCtxt<'_>, p: &WitnessPat<'_, '_>) -> bool { + match p.ctor() { + Constructor::IntRange(IntRange { + lo: MaybeInfiniteInt::NegInfinity, + hi: MaybeInfiniteInt::PosInfinity, + }) + | Constructor::Wildcard + | Constructor::NonExhaustive + | Constructor::Hidden + | Constructor::PrivateUninhabited => true, + Constructor::Never if !tcx.features().never_patterns => true, + _ => false, } } @@ -893,9 +934,6 @@ impl<'p, 'tcx: 'p> PatCx for RustcPatCtxt<'p, 'tcx> { fn is_exhaustive_patterns_feature_on(&self) -> bool { self.tcx.features().exhaustive_patterns } - fn is_min_exhaustive_patterns_feature_on(&self) -> bool { - self.tcx.features().min_exhaustive_patterns - } fn ctor_arity(&self, ctor: &crate::constructor::Constructor<Self>, ty: &Self::Ty) -> usize { self.ctor_arity(ctor, *ty) @@ -941,11 +979,11 @@ impl<'p, 'tcx: 'p> PatCx for RustcPatCtxt<'p, 'tcx> { overlaps_on: IntRange, overlaps_with: &[&crate::pat::DeconstructedPat<Self>], ) { - let overlap_as_pat = self.hoist_pat_range(&overlaps_on, *pat.ty()); + let overlap_as_pat = self.print_pat_range(&overlaps_on, *pat.ty()); let overlaps: Vec<_> = overlaps_with .iter() .map(|pat| pat.data().span) - .map(|span| errors::Overlap { range: overlap_as_pat.clone(), span }) + .map(|span| errors::Overlap { range: overlap_as_pat.to_string(), span }) .collect(); let pat_span = pat.data().span; self.tcx.emit_node_span_lint( @@ -975,14 +1013,13 @@ impl<'p, 'tcx: 'p> PatCx for RustcPatCtxt<'p, 'tcx> { } // `pat` is an exclusive range like `lo..gap`. `gapped_with` contains ranges that start with // `gap+1`. - let suggested_range: thir::Pat<'_> = { + let suggested_range: String = { // 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 mut suggested_range = PatRange::clone(range); + suggested_range.end = rustc_hir::RangeEnd::Included; + suggested_range.to_string() }; - let gap_as_pat = self.hoist_pat_range(&gap, *pat.ty()); + let gap_as_pat = self.print_pat_range(&gap, *pat.ty()); if gapped_with.is_empty() { // If `gapped_with` is empty, `gap == T::MAX`. self.tcx.emit_node_span_lint( @@ -993,9 +1030,9 @@ impl<'p, 'tcx: 'p> PatCx for RustcPatCtxt<'p, 'tcx> { // Point at this range. first_range: thir_pat.span, // That's the gap that isn't covered. - max: gap_as_pat.clone(), + max: gap_as_pat.to_string(), // Suggest `lo..=max` instead. - suggestion: suggested_range.to_string(), + suggestion: suggested_range, }, ); } else { @@ -1007,17 +1044,17 @@ impl<'p, 'tcx: 'p> PatCx for RustcPatCtxt<'p, 'tcx> { // Point at this range. first_range: thir_pat.span, // That's the gap that isn't covered. - gap: gap_as_pat.clone(), + gap: gap_as_pat.to_string(), // Suggest `lo..=gap` instead. - suggestion: suggested_range.to_string(), + suggestion: suggested_range, // 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(), + gap: gap_as_pat.to_string(), + first_range: range.to_string(), }) .collect(), }, @@ -1042,3 +1079,26 @@ fn expand_or_pat<'p, 'tcx>(pat: &'p Pat<'tcx>) -> Vec<&'p Pat<'tcx>> { expand(pat, &mut pats); pats } + +/// The entrypoint for this crate. Computes whether a match is exhaustive and which of its arms are +/// useful, and runs some lints. +pub fn analyze_match<'p, 'tcx>( + tycx: &RustcPatCtxt<'p, 'tcx>, + arms: &[MatchArm<'p, 'tcx>], + scrut_ty: Ty<'tcx>, + pattern_complexity_limit: Option<usize>, +) -> Result<UsefulnessReport<'p, 'tcx>, ErrorGuaranteed> { + let scrut_ty = tycx.reveal_opaque_ty(scrut_ty); + 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. + if tycx.refutable && report.non_exhaustiveness_witnesses.is_empty() { + let pat_column = PatternColumn::new(arms); + lint_nonexhaustive_missing_variants(tycx, arms, &pat_column, scrut_ty)?; + } + + Ok(report) +} diff --git a/compiler/rustc_pattern_analysis/src/rustc/print.rs b/compiler/rustc_pattern_analysis/src/rustc/print.rs new file mode 100644 index 00000000000..17e389df17e --- /dev/null +++ b/compiler/rustc_pattern_analysis/src/rustc/print.rs @@ -0,0 +1,160 @@ +//! Pattern analysis sometimes wants to print patterns as part of a user-visible +//! diagnostic. +//! +//! Historically it did so by creating a synthetic [`thir::Pat`](rustc_middle::thir::Pat) +//! and printing that, but doing so was making it hard to modify the THIR pattern +//! representation for other purposes. +//! +//! So this module contains a forked copy of `thir::Pat` that is used _only_ +//! for diagnostics, and has been partly simplified to remove things that aren't +//! needed for printing. + +use std::fmt; + +use rustc_middle::bug; +use rustc_middle::ty::{self, AdtDef, Ty, TyCtxt}; +use rustc_span::sym; +use rustc_target::abi::{FieldIdx, VariantIdx}; + +#[derive(Clone, Debug)] +pub(crate) struct FieldPat { + pub(crate) field: FieldIdx, + pub(crate) pattern: String, + pub(crate) is_wildcard: bool, +} + +/// Returns a closure that will return `""` when called the first time, +/// and then return `", "` when called any subsequent times. +/// Useful for printing comma-separated lists. +fn start_or_comma() -> impl FnMut() -> &'static str { + let mut first = true; + move || { + if first { + first = false; + "" + } else { + ", " + } + } +} + +#[derive(Clone, Debug)] +pub(crate) enum EnumInfo<'tcx> { + Enum { adt_def: AdtDef<'tcx>, variant_index: VariantIdx }, + NotEnum, +} + +pub(crate) fn write_struct_like<'tcx>( + f: &mut impl fmt::Write, + tcx: TyCtxt<'_>, + ty: Ty<'tcx>, + enum_info: &EnumInfo<'tcx>, + subpatterns: &[FieldPat], +) -> fmt::Result { + let variant_and_name = match *enum_info { + EnumInfo::Enum { adt_def, variant_index } => { + let variant = adt_def.variant(variant_index); + let adt_did = adt_def.did(); + let name = if tcx.is_diagnostic_item(sym::Option, adt_did) + || tcx.is_diagnostic_item(sym::Result, adt_did) + { + variant.name.to_string() + } else { + format!("{}::{}", tcx.def_path_str(adt_def.did()), variant.name) + }; + Some((variant, name)) + } + EnumInfo::NotEnum => ty.ty_adt_def().and_then(|adt_def| { + Some((adt_def.non_enum_variant(), tcx.def_path_str(adt_def.did()))) + }), + }; + + let mut start_or_comma = start_or_comma(); + + if let Some((variant, name)) = &variant_and_name { + write!(f, "{name}")?; + + // Only for Adt we can have `S {...}`, + // which we handle separately here. + if variant.ctor.is_none() { + write!(f, " {{ ")?; + + let mut printed = 0; + for &FieldPat { field, ref pattern, is_wildcard } in subpatterns { + if is_wildcard { + continue; + } + let field_name = variant.fields[field].name; + write!(f, "{}{field_name}: {pattern}", start_or_comma())?; + printed += 1; + } + + let is_union = ty.ty_adt_def().is_some_and(|adt| adt.is_union()); + if printed < variant.fields.len() && (!is_union || printed == 0) { + write!(f, "{}..", start_or_comma())?; + } + + return write!(f, " }}"); + } + } + + let num_fields = variant_and_name.as_ref().map_or(subpatterns.len(), |(v, _)| v.fields.len()); + if num_fields != 0 || variant_and_name.is_none() { + write!(f, "(")?; + for i in 0..num_fields { + write!(f, "{}", start_or_comma())?; + + // Common case: the field is where we expect it. + if let Some(p) = subpatterns.get(i) { + if p.field.index() == i { + write!(f, "{}", p.pattern)?; + continue; + } + } + + // Otherwise, we have to go looking for it. + if let Some(p) = subpatterns.iter().find(|p| p.field.index() == i) { + write!(f, "{}", p.pattern)?; + } else { + write!(f, "_")?; + } + } + write!(f, ")")?; + } + + Ok(()) +} + +pub(crate) fn write_ref_like<'tcx>( + f: &mut impl fmt::Write, + ty: Ty<'tcx>, + subpattern: &str, +) -> fmt::Result { + match ty.kind() { + ty::Ref(_, _, mutbl) => { + write!(f, "&{}", mutbl.prefix_str())?; + } + _ => bug!("{ty} is a bad ref pattern type"), + } + write!(f, "{subpattern}") +} + +pub(crate) fn write_slice_like( + f: &mut impl fmt::Write, + prefix: &[String], + has_dot_dot: bool, + suffix: &[String], +) -> fmt::Result { + let mut start_or_comma = start_or_comma(); + write!(f, "[")?; + for p in prefix.iter() { + write!(f, "{}{}", start_or_comma(), p)?; + } + if has_dot_dot { + write!(f, "{}..", start_or_comma())?; + } + for p in suffix.iter() { + write!(f, "{}{}", start_or_comma(), p)?; + } + write!(f, "]") +} diff --git a/compiler/rustc_pattern_analysis/src/usefulness.rs b/compiler/rustc_pattern_analysis/src/usefulness.rs index 6e96a93473f..6535afcc398 100644 --- a/compiler/rustc_pattern_analysis/src/usefulness.rs +++ b/compiler/rustc_pattern_analysis/src/usefulness.rs @@ -462,8 +462,9 @@ //! # Or-patterns //! //! What we have described so far works well if there are no or-patterns. To handle them, if the -//! first pattern of a row in the matrix is an or-pattern, we expand it by duplicating the rest of -//! the row as necessary. This is handled automatically in [`Matrix`]. +//! first pattern of any row in the matrix is an or-pattern, we expand it by duplicating the rest of +//! the row as necessary. For code reuse, this is implemented as "specializing with the `Or` +//! constructor". //! //! This makes usefulness tracking subtle, because we also want to compute whether an alternative of //! an or-pattern is redundant, e.g. in `Some(_) | Some(0)`. We therefore track usefulness of each @@ -542,13 +543,11 @@ //! 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 -//! `EmptyEnum`. First, on stable rust, we require `_` patterns for empty types in all cases apart -//! from the toplevel exception. The `exhaustive_patterns` and `min_exaustive_patterns` allow -//! omitting patterns in the cases described above. There's a final detail: in the toplevel -//! exception or with the `exhaustive_patterns` feature, we ignore place validity when checking -//! whether a pattern is required for exhaustiveness. I (Nadrieril) hope to deprecate this behavior. +//! Having said all that, we don't fully follow what's been presented in this section. For +//! backwards-compatibility, we ignore place validity when checking whether a pattern is required +//! for exhaustiveness in two cases: when the `exhaustive_patterns` feature gate is on, or when the +//! match scrutinee itself has type `!` or `EmptyEnum`. I (Nadrieril) hope to deprecate this +//! exception. //! //! //! @@ -708,35 +707,99 @@ //! 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 self::PlaceValidity::*; -use crate::constructor::{Constructor, ConstructorSet, IntRange}; -use crate::pat::{DeconstructedPat, PatId, PatOrWild, WitnessPat}; -use crate::{Captures, MatchArm, PatCx, PrivateUninhabitedField}; -use rustc_hash::FxHashSet; -use rustc_index::bit_set::BitSet; -use smallvec::{smallvec, SmallVec}; use std::fmt; -use tracing::{debug, instrument}; #[cfg(feature = "rustc")] use rustc_data_structures::stack::ensure_sufficient_stack; +use rustc_hash::{FxHashMap, FxHashSet}; +use rustc_index::bit_set::BitSet; +use smallvec::{smallvec, SmallVec}; +use tracing::{debug, instrument}; + +use self::PlaceValidity::*; +use crate::constructor::{Constructor, ConstructorSet, IntRange}; +use crate::pat::{DeconstructedPat, PatId, PatOrWild, WitnessPat}; +use crate::{Captures, MatchArm, PatCx, PrivateUninhabitedField}; #[cfg(not(feature = "rustc"))] pub fn ensure_sufficient_stack<R>(f: impl FnOnce() -> R) -> R { f() } +/// A pattern is a "branch" if it is the immediate child of an or-pattern, or if it is the whole +/// pattern of a match arm. These are the patterns that can be meaningfully considered "redundant", +/// since e.g. `0` in `(0, 1)` cannot be redundant on its own. +/// +/// We track for each branch pattern whether it is useful, and if not why. +struct BranchPatUsefulness<'p, Cx: PatCx> { + /// Whether this pattern is useful. + useful: bool, + /// A set of patterns that: + /// - come before this one in the match; + /// - intersect this one; + /// - at the end of the algorithm, if `!self.useful`, their union covers this pattern. + covered_by: FxHashSet<&'p DeconstructedPat<Cx>>, +} + +impl<'p, Cx: PatCx> BranchPatUsefulness<'p, Cx> { + /// Update `self` with the usefulness information found in `row`. + fn update(&mut self, row: &MatrixRow<'p, Cx>, matrix: &Matrix<'p, Cx>) { + self.useful |= row.useful; + // This deserves an explanation: `intersects_at_least` does not contain all intersections + // because we skip irrelevant values (see the docs for `intersects_at_least` for an + // example). Yet we claim this suffices to build a covering set. + // + // Let `p` be our pattern. Assume it is found not useful. For a value `v`, if the value was + // relevant then we explored that value and found that there was another pattern `q` before + // `p` that matches it too. We therefore recorded an intersection with `q`. If `v` was + // irrelevant, we know there's another value `v2` that matches strictly fewer rows (while + // still matching our row) and is relevant. Since `p` is not useful, there must have been a + // `q` before `p` that matches `v2`, and we recorded that intersection. Since `v2` matches + // strictly fewer rows than `v`, `q` also matches `v`. In either case, we recorded in + // `intersects_at_least` a pattern that matches `v`. Hence using `intersects_at_least` is + // sufficient to build a covering set. + for row_id in row.intersects_at_least.iter() { + let row = &matrix.rows[row_id]; + if row.useful && !row.is_under_guard { + if let PatOrWild::Pat(intersecting) = row.head() { + self.covered_by.insert(intersecting); + } + } + } + } + + /// Check whether this pattern is redundant, and if so explain why. + fn is_redundant(&self) -> Option<RedundancyExplanation<'p, Cx>> { + if self.useful { + None + } else { + // We avoid instability by sorting by `uid`. The order of `uid`s only depends on the + // pattern structure. + #[cfg_attr(feature = "rustc", allow(rustc::potential_query_instability))] + let mut covered_by: Vec<_> = self.covered_by.iter().copied().collect(); + covered_by.sort_by_key(|pat| pat.uid); // sort to avoid instability + Some(RedundancyExplanation { covered_by }) + } + } +} + +impl<'p, Cx: PatCx> Default for BranchPatUsefulness<'p, Cx> { + fn default() -> Self { + Self { useful: Default::default(), covered_by: Default::default() } + } +} + /// Context that provides information for usefulness checking. -struct UsefulnessCtxt<'a, Cx: PatCx> { +struct UsefulnessCtxt<'a, 'p, 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>, + /// Track information about the usefulness of branch patterns (see definition of "branch + /// pattern" at [`BranchPatUsefulness`]). + branch_usefulness: FxHashMap<PatId, BranchPatUsefulness<'p, Cx>>, complexity_limit: Option<usize>, complexity_level: usize, } -impl<'a, Cx: PatCx> UsefulnessCtxt<'a, Cx> { +impl<'a, 'p, Cx: PatCx> UsefulnessCtxt<'a, 'p, Cx> { fn increase_complexity_level(&mut self, complexity_add: usize) -> Result<(), Cx::Error> { self.complexity_level += complexity_add; if self @@ -875,6 +938,11 @@ impl<Cx: PatCx> PlaceInfo<Cx> { return Ok((smallvec![Constructor::PrivateUninhabited], vec![])); } + if ctors.clone().any(|c| matches!(c, Constructor::Or)) { + // If any constructor is `Or`, we expand or-patterns. + return Ok((smallvec![Constructor::Or], vec![])); + } + let ctors_for_ty = cx.ctors_for_ty(&self.ty)?; debug!(?ctors_for_ty); @@ -883,13 +951,10 @@ impl<Cx: PatCx> PlaceInfo<Cx> { self.is_scrutinee && matches!(ctors_for_ty, ConstructorSet::NoConstructors); // Whether empty patterns are counted as useful or not. We only warn an empty arm unreachable if // it is guaranteed unreachable by the opsem (i.e. if the place is `known_valid`). - let empty_arms_are_unreachable = self.validity.is_known_valid() - && (is_toplevel_exception - || cx.is_exhaustive_patterns_feature_on() - || cx.is_min_exhaustive_patterns_feature_on()); + let empty_arms_are_unreachable = self.validity.is_known_valid(); // Whether empty patterns can be omitted for exhaustiveness. We ignore place validity in the // toplevel exception and `exhaustive_patterns` cases for backwards compatibility. - let can_omit_empty_arms = empty_arms_are_unreachable + let can_omit_empty_arms = self.validity.is_known_valid() || is_toplevel_exception || cx.is_exhaustive_patterns_feature_on(); @@ -968,10 +1033,6 @@ impl<'p, Cx: PatCx> PatStack<'p, Cx> { PatStack { pats: smallvec![PatOrWild::Pat(pat)], relevant: true } } - fn is_empty(&self) -> bool { - self.pats.is_empty() - } - fn len(&self) -> usize { self.pats.len() } @@ -984,10 +1045,10 @@ impl<'p, Cx: PatCx> PatStack<'p, Cx> { self.pats.iter().copied() } - // Recursively expand the first or-pattern into its subpatterns. Only useful if the pattern is - // an or-pattern. Panics if `self` is empty. + // Expand the first or-pattern into its subpatterns. Only useful if the pattern is an + // or-pattern. Panics if `self` is empty. fn expand_or_pat(&self) -> impl Iterator<Item = PatStack<'p, Cx>> + Captures<'_> { - self.head().flatten_or_pat().into_iter().map(move |pat| { + self.head().expand_or_pat().into_iter().map(move |pat| { let mut new = self.clone(); new.pats[0] = pat; new @@ -1049,16 +1110,38 @@ struct MatrixRow<'p, Cx: PatCx> { /// [`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>, + /// Tracks some rows above this one that have an intersection with this one, i.e. such that + /// there is a value that matches both rows. + /// Because of relevancy we may miss some intersections. The intersections we do find are + /// correct. In other words, this is an underapproximation of the real set of intersections. + /// + /// For example: + /// ```rust,ignore(illustrative) + /// match ... { + /// (true, _, _) => {} // `intersects_at_least = []` + /// (_, true, 0..=10) => {} // `intersects_at_least = []` + /// (_, true, 5..15) => {} // `intersects_at_least = [1]` + /// } + /// ``` + /// Here the `(true, true)` case is irrelevant. Since we skip it, we will not detect that row 0 + /// intersects rows 1 and 2. + intersects_at_least: BitSet<usize>, + /// Whether the head pattern is a branch (see definition of "branch pattern" at + /// [`BranchPatUsefulness`]) + head_is_branch: bool, } impl<'p, Cx: PatCx> MatrixRow<'p, Cx> { - fn is_empty(&self) -> bool { - self.pats.is_empty() + fn new(arm: &MatchArm<'p, Cx>, arm_id: usize) -> Self { + MatrixRow { + pats: PatStack::from_pattern(arm.pat), + parent_row: arm_id, + is_under_guard: arm.has_guard, + useful: false, + intersects_at_least: BitSet::new_empty(0), // Initialized in `Matrix::push`. + // This pattern is a branch because it comes from a match arm. + head_is_branch: true, + } } fn len(&self) -> usize { @@ -1073,15 +1156,19 @@ impl<'p, Cx: PatCx> MatrixRow<'p, Cx> { self.pats.iter() } - // Recursively expand the first or-pattern into its subpatterns. Only useful if the pattern is - // an or-pattern. Panics if `self` is empty. - fn expand_or_pat(&self) -> impl Iterator<Item = MatrixRow<'p, Cx>> + Captures<'_> { - self.pats.expand_or_pat().map(|patstack| MatrixRow { + // Expand the first or-pattern (if any) into its subpatterns. Panics if `self` is empty. + fn expand_or_pat( + &self, + parent_row: usize, + ) -> impl Iterator<Item = MatrixRow<'p, Cx>> + Captures<'_> { + let is_or_pat = self.pats.head().is_or_pat(); + self.pats.expand_or_pat().map(move |patstack| MatrixRow { pats: patstack, - parent_row: self.parent_row, + parent_row, is_under_guard: self.is_under_guard, useful: false, - intersects: BitSet::new_empty(0), // Initialized in `Matrix::expand_and_push`. + intersects_at_least: BitSet::new_empty(0), // Initialized in `Matrix::push`. + head_is_branch: is_or_pat, }) } @@ -1100,7 +1187,8 @@ impl<'p, Cx: PatCx> 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`. + intersects_at_least: BitSet::new_empty(0), // Initialized in `Matrix::push`. + head_is_branch: false, }) } } @@ -1116,7 +1204,7 @@ impl<'p, Cx: PatCx> fmt::Debug for MatrixRow<'p, Cx> { /// Invariant: each row must have the same length, and each column must have the same type. /// /// Invariant: the first column must not contain or-patterns. This is handled by -/// [`Matrix::expand_and_push`]. +/// [`Matrix::push`]. /// /// In fact each column corresponds to a place inside the scrutinee of the match. E.g. after /// specializing `(,)` and `Some` on a pattern of type `(Option<u32>, bool)`, the first column of @@ -1136,19 +1224,10 @@ struct Matrix<'p, Cx: PatCx> { } 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>) { - if !row.is_empty() && row.head().is_or_pat() { - // Expand nested or-patterns. - 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); - } + /// Pushes a new row to the matrix. Internal method, prefer [`Matrix::new`]. + fn push(&mut self, mut row: MatrixRow<'p, Cx>) { + row.intersects_at_least = BitSet::new_empty(self.rows.len()); + self.rows.push(row); } /// Build a new matrix from an iterator of `MatchArm`s. @@ -1165,14 +1244,7 @@ impl<'p, Cx: PatCx> Matrix<'p, Cx> { wildcard_row_is_relevant: true, }; for (arm_id, arm) in arms.iter().enumerate() { - let v = MatrixRow { - pats: PatStack::from_pattern(arm.pat), - parent_row: arm_id, - 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.push(MatrixRow::new(arm, arm_id)); } matrix } @@ -1209,22 +1281,38 @@ impl<'p, Cx: PatCx> Matrix<'p, Cx> { ctor: &Constructor<Cx>, ctor_is_relevant: bool, ) -> Result<Matrix<'p, Cx>, Cx::Error> { - let subfield_place_info = self.place_info[0].specialize(pcx.cx, ctor); - let arity = subfield_place_info.len(); - let specialized_place_info = - subfield_place_info.chain(self.place_info[1..].iter().cloned()).collect(); - let mut matrix = Matrix { - rows: Vec::new(), - place_info: specialized_place_info, - wildcard_row_is_relevant: self.wildcard_row_is_relevant && ctor_is_relevant, - }; - for (i, row) in self.rows().enumerate() { - if ctor.is_covered_by(pcx.cx, row.head().ctor())? { - let new_row = row.pop_head_constructor(pcx.cx, ctor, arity, ctor_is_relevant, i)?; - matrix.expand_and_push(new_row); + if matches!(ctor, Constructor::Or) { + // Specializing with `Or` means expanding rows with or-patterns. + let mut matrix = Matrix { + rows: Vec::new(), + place_info: self.place_info.clone(), + wildcard_row_is_relevant: self.wildcard_row_is_relevant, + }; + for (i, row) in self.rows().enumerate() { + for new_row in row.expand_or_pat(i) { + matrix.push(new_row); + } } + Ok(matrix) + } else { + let subfield_place_info = self.place_info[0].specialize(pcx.cx, ctor); + let arity = subfield_place_info.len(); + let specialized_place_info = + subfield_place_info.chain(self.place_info[1..].iter().cloned()).collect(); + let mut matrix = Matrix { + rows: Vec::new(), + place_info: specialized_place_info, + wildcard_row_is_relevant: self.wildcard_row_is_relevant && ctor_is_relevant, + }; + for (i, row) in self.rows().enumerate() { + if ctor.is_covered_by(pcx.cx, row.head().ctor())? { + let new_row = + row.pop_head_constructor(pcx.cx, ctor, arity, ctor_is_relevant, i)?; + matrix.push(new_row); + } + } + Ok(matrix) } - Ok(matrix) } /// Recover row usefulness and intersection information from a processed specialized matrix. @@ -1235,12 +1323,12 @@ impl<'p, Cx: PatCx> Matrix<'p, Cx> { let parent_row = &mut self.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() { + for child_intersection in child_row.intersects_at_least.iter() { // Convert the intersecting ids into ids for the parent matrix. let parent_intersection = specialized.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); + parent_row.intersects_at_least.insert(parent_intersection); } } } @@ -1465,7 +1553,9 @@ impl<Cx: PatCx> WitnessMatrix<Cx> { missing_ctors: &[Constructor<Cx>], ctor: &Constructor<Cx>, ) { - if self.is_empty() { + // The `Or` constructor indicates that we expanded or-patterns. This doesn't affect + // witnesses. + if self.is_empty() || matches!(ctor, Constructor::Or) { return; } if matches!(ctor, Constructor::Missing) { @@ -1535,7 +1625,7 @@ fn collect_overlapping_range_endpoints<'p, Cx: PatCx>( let overlaps_with: Vec<_> = prefixes .iter() .filter(|&&(other_child_row_id, _)| { - child_row.intersects.contains(other_child_row_id) + child_row.intersects_at_least.contains(other_child_row_id) }) .map(|&(_, pat)| pat) .collect(); @@ -1551,7 +1641,7 @@ fn collect_overlapping_range_endpoints<'p, Cx: PatCx>( let overlaps_with: Vec<_> = suffixes .iter() .filter(|&&(other_child_row_id, _)| { - child_row.intersects.contains(other_child_row_id) + child_row.intersects_at_least.contains(other_child_row_id) }) .map(|&(_, pat)| pat) .collect(); @@ -1594,8 +1684,8 @@ fn collect_non_contiguous_range_endpoints<'p, Cx: PatCx>( /// The core of the algorithm. /// /// This recursively computes witnesses of the non-exhaustiveness of `matrix` (if any). Also tracks -/// usefulness of each row in the matrix (in `row.useful`). We track usefulness of each subpattern -/// in `mcx.useful_subpatterns`. +/// usefulness of each row in the matrix (in `row.useful`). We track usefulness of subpatterns in +/// `mcx.branch_usefulness`. /// /// The input `Matrix` and the output `WitnessMatrix` together match the type exhaustively. /// @@ -1607,7 +1697,7 @@ fn collect_non_contiguous_range_endpoints<'p, Cx: PatCx>( /// This is all explained at the top of the file. #[instrument(level = "debug", skip(mcx), ret)] fn compute_exhaustiveness_and_usefulness<'a, 'p, Cx: PatCx>( - mcx: &mut UsefulnessCtxt<'a, Cx>, + mcx: &mut UsefulnessCtxt<'a, 'p, Cx>, matrix: &mut Matrix<'p, Cx>, ) -> Result<WitnessMatrix<Cx>, Cx::Error> { debug_assert!(matrix.rows().all(|r| r.len() == matrix.column_count())); @@ -1626,7 +1716,7 @@ fn compute_exhaustiveness_and_usefulness<'a, 'p, Cx: PatCx>( 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); + row.intersects_at_least.insert_range(0..i); // The next rows stays useful if this one is under a guard. useful &= row.is_under_guard; } @@ -1668,7 +1758,7 @@ fn compute_exhaustiveness_and_usefulness<'a, 'p, Cx: PatCx>( 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()) + && spec_matrix.rows.iter().any(|row| !row.intersects_at_least.is_empty()) { collect_overlapping_range_endpoints(mcx.tycx, overlap_range, matrix, &spec_matrix); } @@ -1688,14 +1778,11 @@ fn compute_exhaustiveness_and_usefulness<'a, 'p, Cx: PatCx>( } } - // Record usefulness in the patterns. + // Record usefulness of the branch patterns. for row in matrix.rows() { - if row.useful { + if row.head_is_branch { if let PatOrWild::Pat(pat) = row.head() { - let newly_useful = mcx.useful_subpatterns.insert(pat.uid); - if newly_useful { - debug!("newly useful: {pat:?}"); - } + mcx.branch_usefulness.entry(pat.uid).or_default().update(row, matrix); } } } @@ -1703,58 +1790,25 @@ fn compute_exhaustiveness_and_usefulness<'a, 'p, Cx: PatCx>( Ok(ret) } +/// Indicates why a given pattern is considered redundant. +#[derive(Clone, Debug)] +pub struct RedundancyExplanation<'p, Cx: PatCx> { + /// All the values matched by this pattern are already matched by the given set of patterns. + /// This list is not guaranteed to be minimal but the contained patterns are at least guaranteed + /// to intersect this pattern. + pub covered_by: Vec<&'p DeconstructedPat<Cx>>, +} + /// Indicates whether or not a given arm is useful. #[derive(Clone, Debug)] 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. - Useful(Vec<&'p DeconstructedPat<Cx>>), + Useful(Vec<(&'p DeconstructedPat<Cx>, RedundancyExplanation<'p, Cx>)>), /// The arm is redundant and can be removed without changing the behavior of the match /// expression. - Redundant, -} - -/// Report whether this pattern was found useful, and its subpatterns that were not useful if any. -fn collect_pattern_usefulness<'p, Cx: PatCx>( - useful_subpatterns: &FxHashSet<PatId>, - pat: &'p DeconstructedPat<Cx>, -) -> Usefulness<'p, Cx> { - 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.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 - // marked as useful itself, only its children will. We recover this information here. - true - } else { - false - } - } - - let mut redundant_subpats = Vec::new(); - pat.walk(&mut |p| { - if pat_is_useful(useful_subpatterns, p) { - // The pattern is useful, so we recurse to find redundant subpatterns. - true - } else { - // The pattern is redundant. - redundant_subpats.push(p); - false // stop recursing - } - }); - - if pat_is_useful(useful_subpatterns, pat) { - Usefulness::Useful(redundant_subpats) - } else { - Usefulness::Redundant - } + Redundant(RedundancyExplanation<'p, Cx>), } /// The output of checking a match for exhaustiveness and arm usefulness. @@ -1780,7 +1834,7 @@ pub fn compute_match_usefulness<'p, Cx: PatCx>( ) -> Result<UsefulnessReport<'p, Cx>, Cx::Error> { let mut cx = UsefulnessCtxt { tycx, - useful_subpatterns: FxHashSet::default(), + branch_usefulness: FxHashMap::default(), complexity_limit, complexity_level: 0, }; @@ -1793,25 +1847,32 @@ pub fn compute_match_usefulness<'p, Cx: PatCx>( .copied() .map(|arm| { debug!(?arm); - let usefulness = collect_pattern_usefulness(&cx.useful_subpatterns, arm.pat); + let usefulness = cx.branch_usefulness.get(&arm.pat.uid).unwrap(); + let usefulness = if let Some(explanation) = usefulness.is_redundant() { + Usefulness::Redundant(explanation) + } else { + let mut redundant_subpats = Vec::new(); + arm.pat.walk(&mut |subpat| { + if let Some(u) = cx.branch_usefulness.get(&subpat.uid) { + if let Some(explanation) = u.is_redundant() { + redundant_subpats.push((subpat, explanation)); + false // stop recursing + } else { + true // keep recursing + } + } else { + true // keep recursing + } + }); + Usefulness::Useful(redundant_subpats) + }; debug!(?usefulness); (arm, usefulness) }) .collect(); - 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); - } - } - } + let arm_intersections: Vec<_> = + matrix.rows().map(|row| row.intersects_at_least.clone()).collect(); Ok(UsefulnessReport { arm_usefulness, non_exhaustiveness_witnesses, arm_intersections }) } |