Auto merge of #140106 - dianne:deref-pat-usefulness, r=Nadrieril

allow deref patterns to participate in exhaustiveness analysis

Per [this proposal](https://hackmd.io/4qDDMcvyQ-GDB089IPcHGg#Exhaustiveness), this PR allows deref patterns to participate in exhaustiveness analysis. Currently all deref patterns enforce `DerefPure` bounds on their scrutinees, so this assumes all patterns it's analyzing are well-behaved. This also doesn't support [mixed exhaustiveness](https://hackmd.io/4qDDMcvyQ-GDB089IPcHGg#Mixed-exhaustiveness), and instead emits an error if deref patterns are used together with normal constructors. I think mixed exhaustiveness would be nice to have (especially if we eventually want to support arbitrary `Deref` impls[^1]), but it'd require more work to get reasonable diagnostics[^2].

Tracking issue for deref patterns: #87121

r? `@Nadrieril`

[^1]: Regardless of whether we support limited exhaustiveness checking for untrusted `Deref` or always require other arms to be exhaustive, I think it'd be useful to allow mixed matching for user-defined smart pointers. And it'd be strange if it worked there but not for `Cow`.

[^2]: I think listing out witnesses of non-exhaustiveness can be confusing when they're not necessarily disjoint, and when you only need to cover some of them, so we'd probably want special formatting and/or explanatory subdiagnostics. And if it's implemented similarly to unions, we'd probably also want some way of merging witnesses; the way witnesses for unions can appear duplicated is pretty unfortunate. I'm not sure yet how the diagnostics should look, especially for deeply nested patterns.

4 files changed, 103 insertions, 8 deletions

diff --git a/compiler/rustc_pattern_analysis/src/constructor.rs b/compiler/rustc_pattern_analysis/src/constructor.rs
index 4ce868f014f..f7a4931c111 100644
--- a/compiler/rustc_pattern_analysis/src/constructor.rs
+++ b/compiler/rustc_pattern_analysis/src/constructor.rs
@@ -696,6 +696,10 @@ pub enum Constructor<Cx: PatCx> {
     F128Range(IeeeFloat<QuadS>, IeeeFloat<QuadS>, RangeEnd),
     /// String literals. Strings are not quite the same as `&[u8]` so we treat them separately.
     Str(Cx::StrLit),
+    /// Deref patterns (enabled by the `deref_patterns` feature) provide a way of matching on a
+    /// smart pointer ADT through its pointee. They don't directly correspond to ADT constructors,
+    /// and currently are not supported alongside them. Carries the type of the pointee.
+    DerefPattern(Cx::Ty),
     /// Constants that must not be matched structurally. They are treated as black boxes for the
     /// purposes of exhaustiveness: we must not inspect them, and they don't count towards making a
     /// match exhaustive.
@@ -740,6 +744,7 @@ impl<Cx: PatCx> Clone for Constructor<Cx> {
             Constructor::F64Range(lo, hi, end) => Constructor::F64Range(*lo, *hi, *end),
             Constructor::F128Range(lo, hi, end) => Constructor::F128Range(*lo, *hi, *end),
             Constructor::Str(value) => Constructor::Str(value.clone()),
+            Constructor::DerefPattern(ty) => Constructor::DerefPattern(ty.clone()),
             Constructor::Opaque(inner) => Constructor::Opaque(inner.clone()),
             Constructor::Or => Constructor::Or,
             Constructor::Never => Constructor::Never,
@@ -856,6 +861,10 @@ impl<Cx: PatCx> Constructor<Cx> {
             }
             (Slice(self_slice), Slice(other_slice)) => self_slice.is_covered_by(*other_slice),
 
+            // Deref patterns only interact with other deref patterns. Prior to usefulness analysis,
+            // we ensure they don't appear alongside any other non-wild non-opaque constructors.
+            (DerefPattern(_), DerefPattern(_)) => true,
+
             // Opaque constructors don't interact with anything unless they come from the
             // syntactically identical pattern.
             (Opaque(self_id), Opaque(other_id)) => self_id == other_id,
@@ -932,6 +941,7 @@ impl<Cx: PatCx> Constructor<Cx> {
             F64Range(lo, hi, end) => write!(f, "{lo}{end}{hi}")?,
             F128Range(lo, hi, end) => write!(f, "{lo}{end}{hi}")?,
             Str(value) => write!(f, "{value:?}")?,
+            DerefPattern(_) => write!(f, "deref!({:?})", fields.next().unwrap())?,
             Opaque(..) => write!(f, "<constant pattern>")?,
             Or => {
                 for pat in fields {
@@ -1039,8 +1049,17 @@ impl<Cx: PatCx> ConstructorSet<Cx> {
         let mut missing = Vec::new();
         // Constructors in `ctors`, except wildcards and opaques.
         let mut seen = Vec::new();
+        // If we see a deref pattern, it must be the only non-wildcard non-opaque constructor; we
+        // ensure this prior to analysis.
+        let mut deref_pat_present = false;
         for ctor in ctors.cloned() {
             match ctor {
+                DerefPattern(..) => {
+                    if !deref_pat_present {
+                        deref_pat_present = true;
+                        present.push(ctor);
+                    }
+                }
                 Opaque(..) => present.push(ctor),
                 Wildcard => {} // discard wildcards
                 _ => seen.push(ctor),
@@ -1048,6 +1067,9 @@ impl<Cx: PatCx> ConstructorSet<Cx> {
         }
 
         match self {
+            _ if deref_pat_present => {
+                // Deref patterns are the only constructor; nothing is missing.
+            }
             ConstructorSet::Struct { empty } => {
                 if !seen.is_empty() {
                     present.push(Struct);
diff --git a/compiler/rustc_pattern_analysis/src/errors.rs b/compiler/rustc_pattern_analysis/src/errors.rs
index e60930d6cd2..156ba973767 100644
--- a/compiler/rustc_pattern_analysis/src/errors.rs
+++ b/compiler/rustc_pattern_analysis/src/errors.rs
@@ -1,5 +1,5 @@
 use rustc_errors::{Diag, EmissionGuarantee, Subdiagnostic};
-use rustc_macros::{LintDiagnostic, Subdiagnostic};
+use rustc_macros::{Diagnostic, LintDiagnostic, Subdiagnostic};
 use rustc_middle::ty::Ty;
 use rustc_span::Span;
 
@@ -133,3 +133,15 @@ pub(crate) struct NonExhaustiveOmittedPatternLintOnArm {
     pub lint_level: &'static str,
     pub lint_name: &'static str,
 }
+
+#[derive(Diagnostic)]
+#[diag(pattern_analysis_mixed_deref_pattern_constructors)]
+pub(crate) struct MixedDerefPatternConstructors<'tcx> {
+    #[primary_span]
+    pub spans: Vec<Span>,
+    pub smart_pointer_ty: Ty<'tcx>,
+    #[label(pattern_analysis_deref_pattern_label)]
+    pub deref_pattern_label: Span,
+    #[label(pattern_analysis_normal_constructor_label)]
+    pub normal_constructor_label: Span,
+}
diff --git a/compiler/rustc_pattern_analysis/src/rustc.rs b/compiler/rustc_pattern_analysis/src/rustc.rs
index 7c12f69f14c..a89d01dcbbe 100644
--- a/compiler/rustc_pattern_analysis/src/rustc.rs
+++ b/compiler/rustc_pattern_analysis/src/rustc.rs
@@ -269,6 +269,7 @@ impl<'p, 'tcx: 'p> RustcPatCtxt<'p, 'tcx> {
                 }
                 _ => bug!("bad slice pattern {:?} {:?}", ctor, ty),
             },
+            DerefPattern(pointee_ty) => reveal_and_alloc(cx, once(pointee_ty.inner())),
             Bool(..) | IntRange(..) | F16Range(..) | F32Range(..) | F64Range(..)
             | F128Range(..) | Str(..) | Opaque(..) | Never | NonExhaustive | Hidden | Missing
             | PrivateUninhabited | Wildcard => &[],
@@ -296,7 +297,7 @@ impl<'p, 'tcx: 'p> RustcPatCtxt<'p, 'tcx> {
                 }
                 _ => bug!("Unexpected type for constructor `{ctor:?}`: {ty:?}"),
             },
-            Ref => 1,
+            Ref | DerefPattern(_) => 1,
             Slice(slice) => slice.arity(),
             Bool(..) | IntRange(..) | F16Range(..) | F32Range(..) | F64Range(..)
             | F128Range(..) | Str(..) | Opaque(..) | Never | NonExhaustive | Hidden | Missing
@@ -493,11 +494,15 @@ impl<'p, 'tcx: 'p> RustcPatCtxt<'p, 'tcx> {
                     ),
                 };
             }
-            PatKind::DerefPattern { .. } => {
-                // FIXME(deref_patterns): At least detect that `box _` is irrefutable.
-                fields = vec![];
-                arity = 0;
-                ctor = Opaque(OpaqueId::new());
+            PatKind::DerefPattern { subpattern, .. } => {
+                // NB(deref_patterns): This assumes the deref pattern is matching on a trusted
+                // `DerefPure` type. If the `Deref` impl isn't trusted, exhaustiveness must take
+                // into account that multiple calls to deref may return different results. Hence
+                // multiple deref! patterns cannot be exhaustive together unless each is exhaustive
+                // by itself.
+                fields = vec![self.lower_pat(subpattern).at_index(0)];
+                arity = 1;
+                ctor = DerefPattern(cx.reveal_opaque_ty(subpattern.ty));
             }
             PatKind::Leaf { subpatterns } | PatKind::Variant { subpatterns, .. } => {
                 match ty.kind() {
@@ -874,6 +879,7 @@ impl<'p, 'tcx: 'p> RustcPatCtxt<'p, 'tcx> {
                 print::write_ref_like(&mut s, pat.ty().inner(), &print(&pat.fields[0])).unwrap();
                 s
             }
+            DerefPattern(_) => format!("deref!({})", print(&pat.fields[0])),
             Slice(slice) => {
                 let (prefix_len, has_dot_dot) = match slice.kind {
                     SliceKind::FixedLen(len) => (len, false),
@@ -1100,6 +1106,14 @@ pub fn analyze_match<'p, 'tcx>(
     scrut_ty: Ty<'tcx>,
 ) -> Result<UsefulnessReport<'p, 'tcx>, ErrorGuaranteed> {
     let scrut_ty = tycx.reveal_opaque_ty(scrut_ty);
+
+    // The analysis doesn't support deref patterns mixed with normal constructors; error if present.
+    // FIXME(deref_patterns): This only needs to run when a deref pattern was found during lowering.
+    if tycx.tcx.features().deref_patterns() {
+        let pat_column = PatternColumn::new(arms);
+        detect_mixed_deref_pat_ctors(tycx, &pat_column)?;
+    }
+
     let scrut_validity = PlaceValidity::from_bool(tycx.known_valid_scrutinee);
     let report = compute_match_usefulness(
         tycx,
@@ -1119,6 +1133,51 @@ pub fn analyze_match<'p, 'tcx>(
     Ok(report)
 }
 
+// FIXME(deref_patterns): Currently it's the responsibility of the frontend (rustc or rust-analyzer)
+// to ensure that deref patterns don't appear in the same column as normal constructors. Deref
+// patterns aren't currently implemented in rust-analyzer, but should they be, the columnwise check
+// here could be made generic and shared between frontends.
+fn detect_mixed_deref_pat_ctors<'p, 'tcx>(
+    cx: &RustcPatCtxt<'p, 'tcx>,
+    column: &PatternColumn<'p, RustcPatCtxt<'p, 'tcx>>,
+) -> Result<(), ErrorGuaranteed> {
+    let Some(&ty) = column.head_ty() else {
+        return Ok(());
+    };
+
+    // Check for a mix of deref patterns and normal constructors.
+    let mut normal_ctor_span = None;
+    let mut deref_pat_span = None;
+    for pat in column.iter() {
+        match pat.ctor() {
+            // The analysis can handle mixing deref patterns with wildcards and opaque patterns.
+            Wildcard | Opaque(_) => {}
+            DerefPattern(_) => deref_pat_span = Some(pat.data().span),
+            // Nothing else can be compared to deref patterns in `Constructor::is_covered_by`.
+            _ => normal_ctor_span = Some(pat.data().span),
+        }
+    }
+    if let Some(normal_constructor_label) = normal_ctor_span
+        && let Some(deref_pattern_label) = deref_pat_span
+    {
+        return Err(cx.tcx.dcx().emit_err(errors::MixedDerefPatternConstructors {
+            spans: vec![deref_pattern_label, normal_constructor_label],
+            smart_pointer_ty: ty.inner(),
+            deref_pattern_label,
+            normal_constructor_label,
+        }));
+    }
+
+    // Specialize and recurse into the patterns' fields.
+    let set = column.analyze_ctors(cx, &ty)?;
+    for ctor in set.present {
+        for specialized_column in column.specialize(cx, &ty, &ctor).iter() {
+            detect_mixed_deref_pat_ctors(cx, specialized_column)?;
+        }
+    }
+    Ok(())
+}
+
 struct RecursiveOpaque {
     def_id: DefId,
 }
diff --git a/compiler/rustc_pattern_analysis/src/usefulness.rs b/compiler/rustc_pattern_analysis/src/usefulness.rs
index 11ebbea07fa..53638f2a57d 100644
--- a/compiler/rustc_pattern_analysis/src/usefulness.rs
+++ b/compiler/rustc_pattern_analysis/src/usefulness.rs
@@ -702,6 +702,7 @@
 //!   - `ui/consts/const_in_pattern`
 //!   - `ui/rfc-2008-non-exhaustive`
 //!   - `ui/half-open-range-patterns`
+//!   - `ui/pattern/deref-patterns`
 //!   - probably many others
 //!
 //! I (Nadrieril) prefer to put new tests in `ui/pattern/usefulness` unless there's a specific
@@ -866,7 +867,8 @@ impl PlaceValidity {
     /// inside `&` and union fields where validity is reset to `MaybeInvalid`.
     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) {
+        if matches!(ctor, Constructor::Ref | Constructor::DerefPattern(_) | Constructor::UnionField)
+        {
             // Validity of `x: &T` does not imply validity of `*x: T`.
             MaybeInvalid
         } else {