diff options
Diffstat (limited to 'compiler/rustc_pattern_analysis/src')
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/constructor.rs | 114 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/lib.rs | 9 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/pat.rs | 99 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/rustc.rs | 22 | ||||
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/usefulness.rs | 25 |
5 files changed, 177 insertions, 92 deletions
diff --git a/compiler/rustc_pattern_analysis/src/constructor.rs b/compiler/rustc_pattern_analysis/src/constructor.rs index bbb89576ef7..95c5556410d 100644 --- a/compiler/rustc_pattern_analysis/src/constructor.rs +++ b/compiler/rustc_pattern_analysis/src/constructor.rs @@ -678,15 +678,19 @@ pub enum Constructor<Cx: PatCx> { 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. @@ -708,6 +712,7 @@ impl<Cx: PatCx> 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, @@ -814,6 +819,81 @@ impl<Cx: PatCx> 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)] @@ -1040,10 +1120,32 @@ impl<Cx: PatCx> 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/lib.rs b/compiler/rustc_pattern_analysis/src/lib.rs index 5c57c990323..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> { @@ -120,7 +126,8 @@ pub trait PatCx: 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. diff --git a/compiler/rustc_pattern_analysis/src/pat.rs b/compiler/rustc_pattern_analysis/src/pat.rs index e3667d44bc9..5f388ee9f89 100644 --- a/compiler/rustc_pattern_analysis/src/pat.rs +++ b/compiler/rustc_pattern_analysis/src/pat.rs @@ -138,80 +138,11 @@ impl<Cx: PatCx> DeconstructedPat<Cx> { /// This is best effort and not good enough for a `Display` impl. 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(", "); - let mut fields: Vec<_> = (0..self.arity).map(|_| PatOrWild::Wild).collect(); for ipat in self.iter_fields() { fields[ipat.idx] = PatOrWild::Pat(&ipat.pat); } - - 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 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 => { - write!(f, "&{:?}", &fields[0]) - } - 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[..prefix_len] { - write!(f, "{}{:?}", start_or_comma(), p)?; - } - write!(f, "{}", start_or_comma())?; - write!(f, "..")?; - for p in &fields[prefix_len..] { - 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)?; - } - Ok(()) - } - Wildcard | Missing | NonExhaustive | Hidden | PrivateUninhabited => { - write!(f, "_ : {:?}", pat.ty()) - } - } + self.ctor().fmt_fields(f, self.ty(), fields.into_iter()) } } @@ -294,7 +225,6 @@ impl<'p, Cx: PatCx> 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: PatCx> { ctor: Constructor<Cx>, pub(crate) fields: Vec<WitnessPat<Cx>>, @@ -311,18 +241,24 @@ 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) } @@ -334,7 +270,22 @@ impl<Cx: PatCx> 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/rustc.rs b/compiler/rustc_pattern_analysis/src/rustc.rs index fd51fbedeef..b0f506c3651 100644 --- a/compiler/rustc_pattern_analysis/src/rustc.rs +++ b/compiler/rustc_pattern_analysis/src/rustc.rs @@ -247,7 +247,7 @@ impl<'p, 'tcx: 'p> RustcPatCtxt<'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") } @@ -275,7 +275,7 @@ impl<'p, 'tcx: 'p> RustcPatCtxt<'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"), } } @@ -398,7 +398,7 @@ impl<'p, 'tcx: 'p> RustcPatCtxt<'p, 'tcx> { ty::Float(_) | ty::Str | ty::Foreign(_) - | ty::RawPtr(_) + | ty::RawPtr(_, _) | ty::FnDef(_, _) | ty::FnPtr(_) | ty::Dynamic(_, _, _) @@ -462,6 +462,12 @@ impl<'p, 'tcx: 'p> RustcPatCtxt<'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) => { @@ -824,7 +830,8 @@ impl<'p, 'tcx: 'p> RustcPatCtxt<'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`" @@ -873,13 +880,14 @@ impl<'p, 'tcx: 'p> PatCx for RustcPatCtxt<'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)?; } } diff --git a/compiler/rustc_pattern_analysis/src/usefulness.rs b/compiler/rustc_pattern_analysis/src/usefulness.rs index 3760db8b688..cdc03eaeb37 100644 --- a/compiler/rustc_pattern_analysis/src/usefulness.rs +++ b/compiler/rustc_pattern_analysis/src/usefulness.rs @@ -1042,7 +1042,7 @@ struct MatrixRow<'p, Cx: PatCx> { 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. @@ -1163,10 +1163,10 @@ impl<'p, Cx: PatCx> 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`. @@ -1738,6 +1738,9 @@ pub struct UsefulnessReport<'p, Cx: PatCx> { /// 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. @@ -1769,5 +1772,19 @@ pub fn compute_match_usefulness<'p, Cx: PatCx>( }) .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 }) } |