diff options
Diffstat (limited to 'compiler/rustc_pattern_analysis')
| -rw-r--r-- | compiler/rustc_pattern_analysis/Cargo.toml | 1 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/constructor.rs | 11 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/lib.rs | 67 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/lints.rs | 32 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/rustc.rs | 37 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/usefulness.rs | 54 |
6 files changed, 100 insertions, 102 deletions
diff --git a/compiler/rustc_pattern_analysis/Cargo.toml b/compiler/rustc_pattern_analysis/Cargo.toml index 7cc585bea3a..1d0e1cb7e6a 100644 --- a/compiler/rustc_pattern_analysis/Cargo.toml +++ b/compiler/rustc_pattern_analysis/Cargo.toml @@ -6,6 +6,7 @@ edition = "2021" [dependencies] # tidy-alphabetical-start derivative = "2.2.0" +rustc-hash = "1.1.0" rustc_apfloat = "0.2.0" rustc_arena = { path = "../rustc_arena", optional = true } rustc_data_structures = { path = "../rustc_data_structures", optional = true } diff --git a/compiler/rustc_pattern_analysis/src/constructor.rs b/compiler/rustc_pattern_analysis/src/constructor.rs index af553840898..eba71a23435 100644 --- a/compiler/rustc_pattern_analysis/src/constructor.rs +++ b/compiler/rustc_pattern_analysis/src/constructor.rs @@ -155,13 +155,13 @@ use std::iter::once; use smallvec::SmallVec; use rustc_apfloat::ieee::{DoubleS, IeeeFloat, SingleS}; -use rustc_index::bit_set::{BitSet, GrowableBitSet}; -use rustc_index::IndexVec; +use rustc_index::bit_set::GrowableBitSet; use self::Constructor::*; use self::MaybeInfiniteInt::*; use self::SliceKind::*; +use crate::index; use crate::usefulness::PlaceCtxt; use crate::TypeCx; @@ -804,7 +804,10 @@ pub enum ConstructorSet<Cx: TypeCx> { Struct { empty: bool }, /// This type has the following list of constructors. If `variants` is empty and /// `non_exhaustive` is false, don't use this; use `NoConstructors` instead. - Variants { variants: IndexVec<Cx::VariantIdx, VariantVisibility>, non_exhaustive: bool }, + Variants { + variants: index::IdxContainer<Cx::VariantIdx, VariantVisibility>, + non_exhaustive: bool, + }, /// The type is `&T`. Ref, /// The type is a union. @@ -906,7 +909,7 @@ impl<Cx: TypeCx> ConstructorSet<Cx> { } } ConstructorSet::Variants { variants, non_exhaustive } => { - let mut seen_set: BitSet<_> = BitSet::new_empty(variants.len()); + let mut seen_set = index::IdxSet::new_empty(variants.len()); for idx in seen.iter().map(|c| c.as_variant().unwrap()) { seen_set.insert(idx); } diff --git a/compiler/rustc_pattern_analysis/src/lib.rs b/compiler/rustc_pattern_analysis/src/lib.rs index ed10a515508..21fa8e68d82 100644 --- a/compiler/rustc_pattern_analysis/src/lib.rs +++ b/compiler/rustc_pattern_analysis/src/lib.rs @@ -21,17 +21,53 @@ rustc_fluent_macro::fluent_messages! { "../messages.ftl" } use std::fmt; -use rustc_index::Idx; +#[cfg(feature = "rustc")] +pub mod index { + // Faster version when the indices of variants are `0..variants.len()`. + pub use rustc_index::bit_set::BitSet as IdxSet; + pub use rustc_index::Idx; + pub use rustc_index::IndexVec as IdxContainer; +} +#[cfg(not(feature = "rustc"))] +pub mod index { + // Slower version when the indices of variants are something else. + pub trait Idx: Copy + PartialEq + Eq + std::hash::Hash {} + impl<T: Copy + PartialEq + Eq + std::hash::Hash> Idx for T {} + + #[derive(Debug)] + pub struct IdxContainer<K, V>(pub rustc_hash::FxHashMap<K, V>); + impl<K: Idx, V> IdxContainer<K, V> { + pub fn len(&self) -> usize { + self.0.len() + } + pub fn iter_enumerated(&self) -> impl Iterator<Item = (K, &V)> { + self.0.iter().map(|(k, v)| (*k, v)) + } + } + + #[derive(Debug)] + pub struct IdxSet<T>(pub rustc_hash::FxHashSet<T>); + impl<T: Idx> IdxSet<T> { + pub fn new_empty(_len: usize) -> Self { + Self(Default::default()) + } + pub fn contains(&self, elem: T) -> bool { + self.0.contains(&elem) + } + pub fn insert(&mut self, elem: T) { + self.0.insert(elem); + } + } +} + #[cfg(feature = "rustc")] use rustc_middle::ty::Ty; #[cfg(feature = "rustc")] use rustc_span::ErrorGuaranteed; -use crate::constructor::{Constructor, ConstructorSet}; +use crate::constructor::{Constructor, ConstructorSet, IntRange}; #[cfg(feature = "rustc")] -use crate::lints::{ - lint_nonexhaustive_missing_variants, lint_overlapping_range_endpoints, PatternColumn, -}; +use crate::lints::{lint_nonexhaustive_missing_variants, PatternColumn}; use crate::pat::DeconstructedPat; #[cfg(feature = "rustc")] use crate::rustc::RustcMatchCheckCtxt; @@ -50,7 +86,7 @@ pub trait TypeCx: Sized + fmt::Debug { /// Errors that can abort analysis. type Error: fmt::Debug; /// The index of an enum variant. - type VariantIdx: Clone + Idx; + type VariantIdx: Clone + index::Idx + fmt::Debug; /// A string literal type StrLit: Clone + PartialEq + fmt::Debug; /// Extra data to store in a match arm. @@ -77,6 +113,17 @@ pub trait TypeCx: Sized + fmt::Debug { /// Raise a bug. fn bug(&self, fmt: fmt::Arguments<'_>) -> !; + + /// Lint that the range `pat` overlapped with all the ranges in `overlaps_with`, where the range + /// they overlapped over is `overlaps_on`. We only detect singleton overlaps. + /// The default implementation does nothing. + fn lint_overlapping_range_endpoints( + &self, + _pat: &DeconstructedPat<'_, Self>, + _overlaps_on: IntRange, + _overlaps_with: &[&DeconstructedPat<'_, Self>], + ) { + } } /// Context that provides information global to a match. @@ -111,16 +158,10 @@ pub fn analyze_match<'p, 'tcx>( let report = compute_match_usefulness(cx, arms, scrut_ty, scrut_validity)?; - let pat_column = PatternColumn::new(arms); - - // Lint ranges that overlap on their endpoints, which is likely a mistake. - if !report.overlapping_range_endpoints.is_empty() { - lint_overlapping_range_endpoints(cx, &report.overlapping_range_endpoints); - } - // Run the non_exhaustive_omitted_patterns lint. Only run on refutable patterns to avoid hitting // `if let`s. Only run if the match is exhaustive otherwise the error is redundant. if tycx.refutable && report.non_exhaustiveness_witnesses.is_empty() { + let pat_column = PatternColumn::new(arms); lint_nonexhaustive_missing_variants(cx, arms, &pat_column, scrut_ty)?; } diff --git a/compiler/rustc_pattern_analysis/src/lints.rs b/compiler/rustc_pattern_analysis/src/lints.rs index cf3dddfafeb..d9dbd8250ef 100644 --- a/compiler/rustc_pattern_analysis/src/lints.rs +++ b/compiler/rustc_pattern_analysis/src/lints.rs @@ -1,14 +1,11 @@ -use rustc_session::lint; use rustc_session::lint::builtin::NON_EXHAUSTIVE_OMITTED_PATTERNS; use rustc_span::ErrorGuaranteed; -use crate::errors::{ - self, NonExhaustiveOmittedPattern, NonExhaustiveOmittedPatternLintOnArm, Uncovered, -}; +use crate::errors::{NonExhaustiveOmittedPattern, NonExhaustiveOmittedPatternLintOnArm, Uncovered}; use crate::pat::PatOrWild; use crate::rustc::{ - self, Constructor, DeconstructedPat, MatchArm, MatchCtxt, PlaceCtxt, RevealedTy, - RustcMatchCheckCtxt, SplitConstructorSet, WitnessPat, + Constructor, DeconstructedPat, MatchArm, MatchCtxt, PlaceCtxt, RevealedTy, RustcMatchCheckCtxt, + SplitConstructorSet, WitnessPat, }; /// A column of patterns in the matrix, where a column is the intuitive notion of "subpatterns that @@ -196,26 +193,3 @@ pub(crate) fn lint_nonexhaustive_missing_variants<'a, 'p, 'tcx>( } Ok(()) } - -pub(crate) fn lint_overlapping_range_endpoints<'a, 'p, 'tcx>( - cx: MatchCtxt<'a, 'p, 'tcx>, - overlapping_range_endpoints: &[rustc::OverlappingRanges<'p, 'tcx>], -) { - let rcx = cx.tycx; - for overlap in overlapping_range_endpoints { - let overlap_as_pat = rcx.hoist_pat_range(&overlap.overlaps_on, overlap.pat.ty()); - let overlaps: Vec<_> = overlap - .overlaps_with - .iter() - .map(|pat| pat.data().unwrap().span) - .map(|span| errors::Overlap { range: overlap_as_pat.clone(), span }) - .collect(); - let pat_span = overlap.pat.data().unwrap().span; - rcx.tcx.emit_spanned_lint( - lint::builtin::OVERLAPPING_RANGE_ENDPOINTS, - rcx.match_lint_level, - pat_span, - errors::OverlappingRangeEndpoints { overlap: overlaps, range: pat_span }, - ); - } -} diff --git a/compiler/rustc_pattern_analysis/src/rustc.rs b/compiler/rustc_pattern_analysis/src/rustc.rs index e82d6666b1a..87e70d68c1b 100644 --- a/compiler/rustc_pattern_analysis/src/rustc.rs +++ b/compiler/rustc_pattern_analysis/src/rustc.rs @@ -1,3 +1,4 @@ +use smallvec::SmallVec; use std::fmt; use std::iter::once; @@ -5,24 +6,21 @@ use rustc_arena::{DroplessArena, TypedArena}; use rustc_data_structures::captures::Captures; use rustc_hir::def_id::DefId; use rustc_hir::HirId; -use rustc_index::Idx; -use rustc_index::IndexVec; +use rustc_index::{Idx, IndexVec}; use rustc_middle::middle::stability::EvalResult; use rustc_middle::mir::interpret::Scalar; use rustc_middle::mir::{self, Const}; use rustc_middle::thir::{FieldPat, Pat, PatKind, PatRange, PatRangeBoundary}; use rustc_middle::ty::layout::IntegerExt; -use rustc_middle::ty::TypeVisitableExt; -use rustc_middle::ty::{self, OpaqueTypeKey, Ty, TyCtxt, VariantDef}; -use rustc_span::ErrorGuaranteed; -use rustc_span::{Span, DUMMY_SP}; +use rustc_middle::ty::{self, OpaqueTypeKey, Ty, TyCtxt, TypeVisitableExt, VariantDef}; +use rustc_session::lint; +use rustc_span::{ErrorGuaranteed, Span, DUMMY_SP}; use rustc_target::abi::{FieldIdx, Integer, VariantIdx, FIRST_VARIANT}; -use smallvec::SmallVec; use crate::constructor::{ IntRange, MaybeInfiniteInt, OpaqueId, RangeEnd, Slice, SliceKind, VariantVisibility, }; -use crate::TypeCx; +use crate::{errors, TypeCx}; use crate::constructor::Constructor::*; @@ -34,8 +32,6 @@ pub type DeconstructedPat<'p, 'tcx> = crate::pat::DeconstructedPat<'p, RustcMatchCheckCtxt<'p, 'tcx>>; pub type MatchArm<'p, 'tcx> = crate::MatchArm<'p, RustcMatchCheckCtxt<'p, 'tcx>>; pub type MatchCtxt<'a, 'p, 'tcx> = crate::MatchCtxt<'a, RustcMatchCheckCtxt<'p, 'tcx>>; -pub type OverlappingRanges<'p, 'tcx> = - crate::usefulness::OverlappingRanges<'p, RustcMatchCheckCtxt<'p, 'tcx>>; pub(crate) type PlaceCtxt<'a, 'p, 'tcx> = crate::usefulness::PlaceCtxt<'a, RustcMatchCheckCtxt<'p, 'tcx>>; pub(crate) type SplitConstructorSet<'p, 'tcx> = @@ -991,6 +987,27 @@ impl<'p, 'tcx> TypeCx for RustcMatchCheckCtxt<'p, 'tcx> { fn bug(&self, fmt: fmt::Arguments<'_>) -> ! { span_bug!(self.scrut_span, "{}", fmt) } + + fn lint_overlapping_range_endpoints( + &self, + pat: &crate::pat::DeconstructedPat<'_, Self>, + overlaps_on: IntRange, + overlaps_with: &[&crate::pat::DeconstructedPat<'_, Self>], + ) { + let overlap_as_pat = self.hoist_pat_range(&overlaps_on, pat.ty()); + let overlaps: Vec<_> = overlaps_with + .iter() + .map(|pat| pat.data().unwrap().span) + .map(|span| errors::Overlap { range: overlap_as_pat.clone(), span }) + .collect(); + let pat_span = pat.data().unwrap().span; + self.tcx.emit_spanned_lint( + lint::builtin::OVERLAPPING_RANGE_ENDPOINTS, + self.match_lint_level, + pat_span, + errors::OverlappingRangeEndpoints { overlap: overlaps, range: pat_span }, + ); + } } /// Recursively expand this pattern into its subpatterns. Only useful for or-patterns. diff --git a/compiler/rustc_pattern_analysis/src/usefulness.rs b/compiler/rustc_pattern_analysis/src/usefulness.rs index d8c63e0571d..dac354a1c52 100644 --- a/compiler/rustc_pattern_analysis/src/usefulness.rs +++ b/compiler/rustc_pattern_analysis/src/usefulness.rs @@ -1324,10 +1324,10 @@ 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: MatchCtxt<'_, Cx>, overlap_range: IntRange, matrix: &Matrix<'p, Cx>, specialized_matrix: &Matrix<'p, Cx>, - overlapping_range_endpoints: &mut Vec<OverlappingRanges<'p, Cx>>, ) { let overlap = overlap_range.lo; // Ranges that look like `lo..=overlap`. @@ -1357,11 +1357,7 @@ fn collect_overlapping_range_endpoints<'p, Cx: TypeCx>( .map(|&(_, pat)| pat) .collect(); if !overlaps_with.is_empty() { - overlapping_range_endpoints.push(OverlappingRanges { - pat, - overlaps_on: overlap_range, - overlaps_with, - }); + mcx.tycx.lint_overlapping_range_endpoints(pat, overlap_range, &overlaps_with); } } suffixes.push((child_row_id, pat)) @@ -1377,11 +1373,7 @@ fn collect_overlapping_range_endpoints<'p, Cx: TypeCx>( .map(|&(_, pat)| pat) .collect(); if !overlaps_with.is_empty() { - overlapping_range_endpoints.push(OverlappingRanges { - pat, - overlaps_on: overlap_range, - overlaps_with, - }); + mcx.tycx.lint_overlapping_range_endpoints(pat, overlap_range, &overlaps_with); } } prefixes.push((child_row_id, pat)) @@ -1407,7 +1399,6 @@ fn collect_overlapping_range_endpoints<'p, Cx: TypeCx>( fn compute_exhaustiveness_and_usefulness<'a, 'p, Cx: TypeCx>( mcx: MatchCtxt<'a, Cx>, matrix: &mut Matrix<'p, Cx>, - overlapping_range_endpoints: &mut Vec<OverlappingRanges<'p, Cx>>, is_top_level: bool, ) -> Result<WitnessMatrix<Cx>, Cx::Error> { debug_assert!(matrix.rows().all(|r| r.len() == matrix.column_count())); @@ -1490,12 +1481,7 @@ fn compute_exhaustiveness_and_usefulness<'a, 'p, Cx: TypeCx>( let ctor_is_relevant = matches!(ctor, Constructor::Missing) || missing_ctors.is_empty(); let mut spec_matrix = matrix.specialize_constructor(pcx, &ctor, ctor_is_relevant); let mut witnesses = ensure_sufficient_stack(|| { - compute_exhaustiveness_and_usefulness( - mcx, - &mut spec_matrix, - overlapping_range_endpoints, - false, - ) + compute_exhaustiveness_and_usefulness(mcx, &mut spec_matrix, false) })?; // Transform witnesses for `spec_matrix` into witnesses for `matrix`. @@ -1524,12 +1510,7 @@ 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( - overlap_range, - matrix, - &spec_matrix, - overlapping_range_endpoints, - ); + collect_overlapping_range_endpoints(mcx, overlap_range, matrix, &spec_matrix); } } } @@ -1556,15 +1537,6 @@ pub enum Usefulness<'p, Cx: TypeCx> { Redundant, } -/// Indicates that the range `pat` overlapped with all the ranges in `overlaps_with`, where the -/// range they overlapped over is `overlaps_on`. We only detect singleton overlaps. -#[derive(Clone, Debug)] -pub struct OverlappingRanges<'p, Cx: TypeCx> { - pub pat: &'p DeconstructedPat<'p, Cx>, - pub overlaps_on: IntRange, - pub overlaps_with: Vec<&'p DeconstructedPat<'p, Cx>>, -} - /// The output of checking a match for exhaustiveness and arm usefulness. pub struct UsefulnessReport<'p, Cx: TypeCx> { /// For each arm of the input, whether that arm is useful after the arms above it. @@ -1572,7 +1544,6 @@ pub struct UsefulnessReport<'p, Cx: TypeCx> { /// 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>>, - pub overlapping_range_endpoints: Vec<OverlappingRanges<'p, Cx>>, } /// Computes whether a match is exhaustive and which of its arms are useful. @@ -1583,14 +1554,9 @@ pub fn compute_match_usefulness<'p, Cx: TypeCx>( scrut_ty: Cx::Ty, scrut_validity: ValidityConstraint, ) -> Result<UsefulnessReport<'p, Cx>, Cx::Error> { - let mut overlapping_range_endpoints = Vec::new(); let mut matrix = Matrix::new(arms, scrut_ty, scrut_validity); - let non_exhaustiveness_witnesses = compute_exhaustiveness_and_usefulness( - cx, - &mut matrix, - &mut overlapping_range_endpoints, - true, - )?; + let non_exhaustiveness_witnesses = + compute_exhaustiveness_and_usefulness(cx, &mut matrix, true)?; let non_exhaustiveness_witnesses: Vec<_> = non_exhaustiveness_witnesses.single_column(); let arm_usefulness: Vec<_> = arms @@ -1608,9 +1574,5 @@ pub fn compute_match_usefulness<'p, Cx: TypeCx>( }) .collect(); - Ok(UsefulnessReport { - arm_usefulness, - non_exhaustiveness_witnesses, - overlapping_range_endpoints, - }) + Ok(UsefulnessReport { arm_usefulness, non_exhaustiveness_witnesses }) } |