Auto merge of #3238 - rust-lang:rustup-2023-12-24, r=saethlin

Automatic Rustup

6 files changed, 290 insertions, 104 deletions

diff --git a/compiler/rustc_pattern_analysis/src/constructor.rs b/compiler/rustc_pattern_analysis/src/constructor.rs
index af0a7497a34..b688051ca9c 100644
--- a/compiler/rustc_pattern_analysis/src/constructor.rs
+++ b/compiler/rustc_pattern_analysis/src/constructor.rs
@@ -642,7 +642,8 @@ impl OpaqueId {
 /// `specialize_constructor` returns the list of fields corresponding to a pattern, given a
 /// constructor. `Constructor::apply` reconstructs the pattern from a pair of `Constructor` and
 /// `Fields`.
-#[derive(Clone, Debug, PartialEq)]
+#[derive(derivative::Derivative)]
+#[derivative(Debug(bound = ""), Clone(bound = ""), PartialEq(bound = ""))]
 pub enum Constructor<Cx: TypeCx> {
     /// Tuples and structs.
     Struct,
diff --git a/compiler/rustc_pattern_analysis/src/lib.rs b/compiler/rustc_pattern_analysis/src/lib.rs
index 785a60e9978..a1c9b157666 100644
--- a/compiler/rustc_pattern_analysis/src/lib.rs
+++ b/compiler/rustc_pattern_analysis/src/lib.rs
@@ -49,7 +49,7 @@ impl<'a, T: ?Sized> Captures<'a> for T {}
 /// Context that provides type information about constructors.
 ///
 /// Most of the crate is parameterized on a type that implements this trait.
-pub trait TypeCx: Sized + Clone + fmt::Debug {
+pub trait TypeCx: Sized + fmt::Debug {
     /// The type of a pattern.
     type Ty: Copy + Clone + fmt::Debug; // FIXME: remove Copy
     /// The index of an enum variant.
@@ -58,11 +58,11 @@ pub trait TypeCx: Sized + Clone + fmt::Debug {
     type StrLit: Clone + PartialEq + fmt::Debug;
     /// Extra data to store in a match arm.
     type ArmData: Copy + Clone + fmt::Debug;
-    /// Extra data to store in a pattern. `Default` needed when we create fictitious wildcard
-    /// patterns during analysis.
-    type PatData: Clone + Default;
+    /// Extra data to store in a pattern.
+    type PatData: Clone;
 
-    fn is_opaque_ty(ty: Self::Ty) -> bool;
+    /// FIXME(Nadrieril): `Cx` should only give us revealed types.
+    fn reveal_opaque_ty(&self, ty: Self::Ty) -> Self::Ty;
     fn is_exhaustive_patterns_feature_on(&self) -> bool;
 
     /// The number of fields for this constructor.
@@ -85,7 +85,8 @@ pub trait TypeCx: Sized + Clone + fmt::Debug {
 }
 
 /// Context that provides information global to a match.
-#[derive(Clone)]
+#[derive(derivative::Derivative)]
+#[derivative(Clone(bound = ""), Copy(bound = ""))]
 pub struct MatchCtxt<'a, 'p, Cx: TypeCx> {
     /// The context for type information.
     pub tycx: &'a Cx,
@@ -93,18 +94,16 @@ pub struct MatchCtxt<'a, 'p, Cx: TypeCx> {
     pub wildcard_arena: &'a TypedArena<DeconstructedPat<'p, Cx>>,
 }
 
-impl<'a, 'p, Cx: TypeCx> Copy for MatchCtxt<'a, 'p, Cx> {}
-
 /// The arm of a match expression.
-#[derive(Clone, Debug)]
+#[derive(Debug)]
+#[derive(derivative::Derivative)]
+#[derivative(Clone(bound = ""), Copy(bound = ""))]
 pub struct MatchArm<'p, Cx: TypeCx> {
     pub pat: &'p DeconstructedPat<'p, Cx>,
     pub has_guard: bool,
     pub arm_data: Cx::ArmData,
 }
 
-impl<'p, Cx: TypeCx> 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")]
diff --git a/compiler/rustc_pattern_analysis/src/lints.rs b/compiler/rustc_pattern_analysis/src/lints.rs
index 072ef4836a8..2be6e8e3db3 100644
--- a/compiler/rustc_pattern_analysis/src/lints.rs
+++ b/compiler/rustc_pattern_analysis/src/lints.rs
@@ -48,22 +48,14 @@ impl<'a, 'p, 'tcx> PatternColumn<'a, 'p, 'tcx> {
     fn is_empty(&self) -> bool {
         self.patterns.is_empty()
     }
-    fn head_ty(&self) -> Option<Ty<'tcx>> {
+    fn head_ty(&self, cx: MatchCtxt<'a, 'p, 'tcx>) -> Option<Ty<'tcx>> {
         if self.patterns.len() == 0 {
             return None;
         }
-        // If the type is opaque and it is revealed anywhere in the column, we take the revealed
-        // version. Otherwise we could encounter constructors for the revealed type and crash.
-        let first_ty = self.patterns[0].ty();
-        if RustcMatchCheckCtxt::is_opaque_ty(first_ty) {
-            for pat in &self.patterns {
-                let ty = pat.ty();
-                if !RustcMatchCheckCtxt::is_opaque_ty(ty) {
-                    return Some(ty);
-                }
-            }
-        }
-        Some(first_ty)
+
+        let ty = self.patterns[0].ty();
+        // FIXME(Nadrieril): `Cx` should only give us revealed types.
+        Some(cx.tycx.reveal_opaque_ty(ty))
     }
 
     /// Do constructor splitting on the constructors of the column.
@@ -125,7 +117,7 @@ fn collect_nonexhaustive_missing_variants<'a, 'p, 'tcx>(
     cx: MatchCtxt<'a, 'p, 'tcx>,
     column: &PatternColumn<'a, 'p, 'tcx>,
 ) -> Vec<WitnessPat<'p, 'tcx>> {
-    let Some(ty) = column.head_ty() else {
+    let Some(ty) = column.head_ty(cx) else {
         return Vec::new();
     };
     let pcx = &PlaceCtxt::new_dummy(cx, ty);
@@ -211,7 +203,7 @@ pub(crate) fn lint_nonexhaustive_missing_variants<'a, 'p, 'tcx>(
                 };
 
                 use rustc_errors::DecorateLint;
-                let mut err = rcx.tcx.sess.struct_span_warn(*arm.pat.data(), "");
+                let mut err = rcx.tcx.sess.struct_span_warn(*arm.pat.data().unwrap(), "");
                 err.set_primary_message(decorator.msg());
                 decorator.decorate_lint(&mut err);
                 err.emit();
@@ -226,7 +218,7 @@ pub(crate) fn lint_overlapping_range_endpoints<'a, 'p, 'tcx>(
     cx: MatchCtxt<'a, 'p, 'tcx>,
     column: &PatternColumn<'a, 'p, 'tcx>,
 ) {
-    let Some(ty) = column.head_ty() else {
+    let Some(ty) = column.head_ty(cx) else {
         return;
     };
     let pcx = &PlaceCtxt::new_dummy(cx, ty);
@@ -261,8 +253,8 @@ pub(crate) fn lint_overlapping_range_endpoints<'a, 'p, 'tcx>(
                 let mut suffixes: SmallVec<[_; 1]> = Default::default();
                 // Iterate on patterns that contained `overlap`.
                 for pat in column.iter() {
-                    let this_span = *pat.data();
                     let Constructor::IntRange(this_range) = pat.ctor() else { continue };
+                    let this_span = *pat.data().unwrap();
                     if this_range.is_singleton() {
                         // Don't lint when one of the ranges is a singleton.
                         continue;
diff --git a/compiler/rustc_pattern_analysis/src/pat.rs b/compiler/rustc_pattern_analysis/src/pat.rs
index 0cc8477b7cd..9efd3e864da 100644
--- a/compiler/rustc_pattern_analysis/src/pat.rs
+++ b/compiler/rustc_pattern_analysis/src/pat.rs
@@ -26,14 +26,16 @@ pub struct DeconstructedPat<'p, Cx: TypeCx> {
     ctor: Constructor<Cx>,
     fields: &'p [DeconstructedPat<'p, Cx>],
     ty: Cx::Ty,
-    data: Cx::PatData,
+    /// Extra data to store in a pattern. `None` if the pattern is a wildcard that does not
+    /// correspond to a user-supplied pattern.
+    data: Option<Cx::PatData>,
     /// Whether removing this arm would change the behavior of the match expression.
     useful: Cell<bool>,
 }
 
 impl<'p, Cx: TypeCx> DeconstructedPat<'p, Cx> {
-    pub fn wildcard(ty: Cx::Ty, data: Cx::PatData) -> Self {
-        Self::new(Wildcard, &[], ty, data)
+    pub fn wildcard(ty: Cx::Ty) -> Self {
+        DeconstructedPat { ctor: Wildcard, fields: &[], ty, data: None, useful: Cell::new(false) }
     }
 
     pub fn new(
@@ -42,7 +44,7 @@ impl<'p, Cx: TypeCx> DeconstructedPat<'p, Cx> {
         ty: Cx::Ty,
         data: Cx::PatData,
     ) -> Self {
-        DeconstructedPat { ctor, fields, ty, data, useful: Cell::new(false) }
+        DeconstructedPat { ctor, fields, ty, data: Some(data), useful: Cell::new(false) }
     }
 
     pub(crate) fn is_or_pat(&self) -> bool {
@@ -63,8 +65,10 @@ impl<'p, Cx: TypeCx> DeconstructedPat<'p, Cx> {
     pub fn ty(&self) -> Cx::Ty {
         self.ty
     }
-    pub fn data(&self) -> &Cx::PatData {
-        &self.data
+    /// Returns the extra data stored in a pattern. Returns `None` if the pattern is a wildcard that
+    /// does not correspond to a user-supplied pattern.
+    pub fn data(&self) -> Option<&Cx::PatData> {
+        self.data.as_ref()
     }
 
     pub fn iter_fields<'a>(
@@ -83,7 +87,7 @@ impl<'p, Cx: TypeCx> DeconstructedPat<'p, Cx> {
         let wildcard_sub_tys = || {
             let tys = pcx.ctor_sub_tys(other_ctor);
             tys.iter()
-                .map(|ty| DeconstructedPat::wildcard(*ty, Cx::PatData::default()))
+                .map(|ty| DeconstructedPat::wildcard(*ty))
                 .map(|pat| pcx.mcx.wildcard_arena.alloc(pat) as &_)
                 .collect()
         };
@@ -160,7 +164,8 @@ impl<'p, Cx: TypeCx> fmt::Debug for DeconstructedPat<'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, Clone)]
+#[derive(derivative::Derivative)]
+#[derivative(Debug(bound = ""), Clone(bound = ""))]
 pub struct WitnessPat<Cx: TypeCx> {
     ctor: Constructor<Cx>,
     pub(crate) fields: Vec<WitnessPat<Cx>>,
diff --git a/compiler/rustc_pattern_analysis/src/rustc.rs b/compiler/rustc_pattern_analysis/src/rustc.rs
index 65c90aa9f1d..a5a47724f3f 100644
--- a/compiler/rustc_pattern_analysis/src/rustc.rs
+++ b/compiler/rustc_pattern_analysis/src/rustc.rs
@@ -12,7 +12,7 @@ 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::{self, Ty, TyCtxt, VariantDef};
+use rustc_middle::ty::{self, OpaqueTypeKey, Ty, TyCtxt, VariantDef};
 use rustc_span::{Span, DUMMY_SP};
 use rustc_target::abi::{FieldIdx, Integer, VariantIdx, FIRST_VARIANT};
 use smallvec::SmallVec;
@@ -44,6 +44,7 @@ pub type WitnessPat<'p, 'tcx> = crate::pat::WitnessPat<RustcMatchCheckCtxt<'p, '
 #[derive(Clone)]
 pub struct RustcMatchCheckCtxt<'p, 'tcx> {
     pub tcx: TyCtxt<'tcx>,
+    pub typeck_results: &'tcx ty::TypeckResults<'tcx>,
     /// The module in which the match occurs. This is necessary for
     /// checking inhabited-ness of types because whether a type is (visibly)
     /// inhabited can depend on whether it was defined in the current module or
@@ -73,8 +74,16 @@ impl<'p, 'tcx> fmt::Debug for RustcMatchCheckCtxt<'p, 'tcx> {
 }
 
 impl<'p, 'tcx> RustcMatchCheckCtxt<'p, 'tcx> {
-    pub(crate) fn is_uninhabited(&self, ty: Ty<'tcx>) -> bool {
-        !ty.is_inhabited_from(self.tcx, self.module, self.param_env)
+    fn reveal_opaque(&self, key: OpaqueTypeKey<'tcx>) -> Option<Ty<'tcx>> {
+        self.typeck_results.concrete_opaque_types.get(&key).map(|x| x.ty)
+    }
+    pub fn is_uninhabited(&self, ty: Ty<'tcx>) -> bool {
+        !ty.inhabited_predicate(self.tcx).apply_revealing_opaque(
+            self.tcx,
+            self.param_env,
+            self.module,
+            &|key| self.reveal_opaque(key),
+        )
     }
 
     /// Returns whether the given type is an enum from another crate declared `#[non_exhaustive]`.
@@ -101,6 +110,21 @@ impl<'p, 'tcx> RustcMatchCheckCtxt<'p, 'tcx> {
         }
     }
 
+    /// Type inference occasionally gives us opaque types in places where corresponding patterns
+    /// have more specific types. To avoid inconsistencies as well as detect opaque uninhabited
+    /// types, we use the corresponding concrete type if possible.
+    fn reveal_opaque_ty(&self, ty: Ty<'tcx>) -> Ty<'tcx> {
+        if let ty::Alias(ty::Opaque, alias_ty) = ty.kind() {
+            if let Some(local_def_id) = alias_ty.def_id.as_local() {
+                let key = ty::OpaqueTypeKey { def_id: local_def_id, args: alias_ty.args };
+                if let Some(real_ty) = self.typeck_results.concrete_opaque_types.get(&key) {
+                    return real_ty.ty;
+                }
+            }
+        }
+        ty
+    }
+
     // In the cases of either a `#[non_exhaustive]` field list or a non-public field, we hide
     // uninhabited fields in order not to reveal the uninhabitedness of the whole variant.
     // This lists the fields we keep along with their types.
@@ -303,7 +327,9 @@ impl<'p, 'tcx> RustcMatchCheckCtxt<'p, 'tcx> {
                         let is_inhabited = v
                             .inhabited_predicate(cx.tcx, *def)
                             .instantiate(cx.tcx, args)
-                            .apply(cx.tcx, cx.param_env, cx.module);
+                            .apply_revealing_opaque(cx.tcx, cx.param_env, cx.module, &|key| {
+                                cx.reveal_opaque(key)
+                            });
                         // Variants that depend on a disabled unstable feature.
                         let is_unstable = matches!(
                             cx.tcx.eval_stability(variant_def_id, None, DUMMY_SP, None),
@@ -400,7 +426,7 @@ impl<'p, 'tcx> RustcMatchCheckCtxt<'p, 'tcx> {
                     ty::Tuple(fs) => {
                         ctor = Struct;
                         let mut wilds: SmallVec<[_; 2]> =
-                            fs.iter().map(|ty| DeconstructedPat::wildcard(ty, pat.span)).collect();
+                            fs.iter().map(|ty| DeconstructedPat::wildcard(ty)).collect();
                         for pat in subpatterns {
                             wilds[pat.field.index()] = self.lower_pat(&pat.pattern);
                         }
@@ -423,7 +449,7 @@ impl<'p, 'tcx> RustcMatchCheckCtxt<'p, 'tcx> {
                         let pat = if let Some(pat) = pattern {
                             self.lower_pat(&pat.pattern)
                         } else {
-                            DeconstructedPat::wildcard(args.type_at(0), pat.span)
+                            DeconstructedPat::wildcard(args.type_at(0))
                         };
                         ctor = Struct;
                         fields = singleton(pat);
@@ -448,7 +474,7 @@ impl<'p, 'tcx> RustcMatchCheckCtxt<'p, 'tcx> {
                                 ty
                             });
                         let mut wilds: SmallVec<[_; 2]> =
-                            tys.map(|ty| DeconstructedPat::wildcard(ty, pat.span)).collect();
+                            tys.map(|ty| DeconstructedPat::wildcard(ty)).collect();
                         for pat in subpatterns {
                             if let Some(i) = field_id_to_id[pat.field.index()] {
                                 wilds[i] = self.lower_pat(&pat.pattern);
@@ -873,8 +899,9 @@ impl<'p, 'tcx> TypeCx for RustcMatchCheckCtxt<'p, 'tcx> {
     fn is_exhaustive_patterns_feature_on(&self) -> bool {
         self.tcx.features().exhaustive_patterns
     }
-    fn is_opaque_ty(ty: Self::Ty) -> bool {
-        matches!(ty.kind(), ty::Alias(ty::Opaque, ..))
+
+    fn reveal_opaque_ty(&self, ty: Ty<'tcx>) -> Ty<'tcx> {
+        self.reveal_opaque_ty(ty)
     }
 
     fn ctor_arity(&self, ctor: &crate::constructor::Constructor<Self>, ty: Self::Ty) -> usize {
diff --git a/compiler/rustc_pattern_analysis/src/usefulness.rs b/compiler/rustc_pattern_analysis/src/usefulness.rs
index 6b1de807797..b51b1a1f722 100644
--- a/compiler/rustc_pattern_analysis/src/usefulness.rs
+++ b/compiler/rustc_pattern_analysis/src/usefulness.rs
@@ -300,6 +300,166 @@
 //!
 //!
 //!
+//! # `Missing` and relevancy
+//!
+//! ## Relevant values
+//!
+//! Take the following example:
+//!
+//! ```compile_fail,E0004
+//! # let foo = (true, true);
+//! match foo {
+//!     (true, _) => 1,
+//!     (_, true) => 2,
+//! };
+//! ```
+//!
+//! Consider the value `(true, true)`:
+//! - Row 2 does not distinguish `(true, true)` and `(false, true)`;
+//! - `false` does not show up in the first column of the match, so without knowing anything else we
+//!     can deduce that `(false, true)` matches the same or fewer rows than `(true, true)`.
+//!
+//! Using those two facts together, we deduce that `(true, true)` will not give us more usefulness
+//! information about row 2 than `(false, true)` would. We say that "`(true, true)` is made
+//! irrelevant for row 2 by `(false, true)`". We will use this idea to prune the search tree.
+//!
+//!
+//! ## Computing relevancy
+//!
+//! We now generalize from the above example to approximate relevancy in a simple way. Note that we
+//! will only compute an approximation: we can sometimes determine when a case is irrelevant, but
+//! computing this precisely is at least as hard as computing usefulness.
+//!
+//! Our computation of relevancy relies on the `Missing` constructor. As explained in
+//! [`crate::constructor`], `Missing` represents the constructors not present in a given column. For
+//! example in the following:
+//!
+//! ```compile_fail,E0004
+//! enum Direction { North, South, East, West }
+//! # let wind = (Direction::North, 0u8);
+//! match wind {
+//!     (Direction::North, _) => 1,
+//!     (_, 50..) => 2,
+//! };
+//! ```
+//!
+//! Here `South`, `East` and `West` are missing in the first column, and `0..50`  is missing in the
+//! second. Both of these sets are represented by `Constructor::Missing` in their corresponding
+//! column.
+//!
+//! We then compute relevancy as follows: during the course of the algorithm, for a row `r`:
+//! - if `r` has a wildcard in the first column;
+//! - and some constructors are missing in that column;
+//! - then any `c != Missing` is considered irrelevant for row `r`.
+//!
+//! By this we mean that continuing the algorithm by specializing with `c` is guaranteed not to
+//! contribute more information about the usefulness of row `r` than what we would get by
+//! specializing with `Missing`. The argument is the same as in the previous subsection.
+//!
+//! Once we've specialized by a constructor `c` that is irrelevant for row `r`, we're guaranteed to
+//! only explore values irrelevant for `r`. If we then ever reach a point where we're only exploring
+//! values that are irrelevant to all of the rows (including the virtual wildcard row used for
+//! exhaustiveness), we skip that case entirely.
+//!
+//!
+//! ## Example
+//!
+//! Let's go through a variation on the first example:
+//!
+//! ```compile_fail,E0004
+//! # let foo = (true, true, true);
+//! match foo {
+//!     (true, _, true) => 1,
+//!     (_, true, _) => 2,
+//! };
+//! ```
+//!
+//! ```text
+//!  ┐ Patterns:
+//!  │   1. `[(true, _, true)]`
+//!  │   2. `[(_, true, _)]`
+//!  │   3. `[_]` // virtual extra wildcard row
+//!  │
+//!  │ Specialize with `(,,)`:
+//!  ├─┐ Patterns:
+//!  │ │   1. `[true, _, true]`
+//!  │ │   2. `[_, true, _]`
+//!  │ │   3. `[_, _, _]`
+//!  │ │
+//!  │ │ There are missing constructors in the first column (namely `false`), hence
+//!  │ │ `true` is irrelevant for rows 2 and 3.
+//!  │ │
+//!  │ │ Specialize with `true`:
+//!  │ ├─┐ Patterns:
+//!  │ │ │   1. `[_, true]`
+//!  │ │ │   2. `[true, _]` // now exploring irrelevant cases
+//!  │ │ │   3. `[_, _]`    // now exploring irrelevant cases
+//!  │ │ │
+//!  │ │ │ There are missing constructors in the first column (namely `false`), hence
+//!  │ │ │ `true` is irrelevant for rows 1 and 3.
+//!  │ │ │
+//!  │ │ │ Specialize with `true`:
+//!  │ │ ├─┐ Patterns:
+//!  │ │ │ │   1. `[true]` // now exploring irrelevant cases
+//!  │ │ │ │   2. `[_]`    // now exploring irrelevant cases
+//!  │ │ │ │   3. `[_]`    // now exploring irrelevant cases
+//!  │ │ │ │
+//!  │ │ │ │ The current case is irrelevant for all rows: we backtrack immediately.
+//!  │ │ ├─┘
+//!  │ │ │
+//!  │ │ │ Specialize with `false`:
+//!  │ │ ├─┐ Patterns:
+//!  │ │ │ │   1. `[true]`
+//!  │ │ │ │   3. `[_]`    // now exploring irrelevant cases
+//!  │ │ │ │
+//!  │ │ │ │ Specialize with `true`:
+//!  │ │ │ ├─┐ Patterns:
+//!  │ │ │ │ │   1. `[]`
+//!  │ │ │ │ │   3. `[]`    // now exploring irrelevant cases
+//!  │ │ │ │ │
+//!  │ │ │ │ │ Row 1 is therefore useful.
+//!  │ │ │ ├─┘
+//! <etc...>
+//! ```
+//!
+//! Relevancy allowed us to skip the case `(true, true, _)` entirely. In some cases this pruning can
+//! give drastic speedups. The case this was built for is the following (#118437):
+//!
+//! ```ignore(illustrative)
+//! match foo {
+//!     (true, _, _, _, ..) => 1,
+//!     (_, true, _, _, ..) => 2,
+//!     (_, _, true, _, ..) => 3,
+//!     (_, _, _, true, ..) => 4,
+//!     ...
+//! }
+//! ```
+//!
+//! Without considering relevancy, we would explore all 2^n combinations of the `true` and `Missing`
+//! constructors. Relevancy tells us that e.g. `(true, true, false, false, false, ...)` is
+//! irrelevant for all the rows. This allows us to skip all cases with more than one `true`
+//! constructor, changing the runtime from exponential to linear.
+//!
+//!
+//! ## Relevancy and exhaustiveness
+//!
+//! For exhaustiveness, we do something slightly different w.r.t relevancy: we do not report
+//! witnesses of non-exhaustiveness that are irrelevant for the virtual wildcard row. For example,
+//! in:
+//!
+//! ```ignore(illustrative)
+//! match foo {
+//!     (true, true) => {}
+//! }
+//! ```
+//!
+//! we only report `(false, _)` as missing. This was a deliberate choice made early in the
+//! development of rust, for diagnostic and performance purposes. As showed in the previous section,
+//! ignoring irrelevant cases preserves usefulness, so this choice still correctly computes whether
+//! a match is exhaustive.
+//!
+//!
+//!
 //! # Or-patterns
 //!
 //! What we have described so far works well if there are no or-patterns. To handle them, if the
@@ -569,8 +729,10 @@ pub fn ensure_sufficient_stack<R>(f: impl FnOnce() -> R) -> R {
 }
 
 /// Context that provides information local to a place under investigation.
-#[derive(Clone)]
+#[derive(derivative::Derivative)]
+#[derivative(Debug(bound = ""), Clone(bound = ""), Copy(bound = ""))]
 pub(crate) struct PlaceCtxt<'a, 'p, Cx: TypeCx> {
+    #[derivative(Debug = "ignore")]
     pub(crate) mcx: MatchCtxt<'a, 'p, Cx>,
     /// Type of the place under investigation.
     pub(crate) ty: Cx::Ty,
@@ -596,14 +758,6 @@ impl<'a, 'p, Cx: TypeCx> PlaceCtxt<'a, 'p, Cx> {
     }
 }
 
-impl<'a, 'p, Cx: TypeCx> Copy for PlaceCtxt<'a, 'p, Cx> {}
-
-impl<'a, 'p, Cx: TypeCx> fmt::Debug for PlaceCtxt<'a, 'p, Cx> {
-    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        f.debug_struct("PlaceCtxt").field("ty", &self.ty).finish()
-    }
-}
-
 /// Serves two purposes:
 /// - in a wildcard, tracks whether the wildcard matches only valid values (i.e. is a binding `_a`)
 ///     or also invalid values (i.e. is a true `_` pattern).
@@ -670,15 +824,20 @@ impl fmt::Display for ValidityConstraint {
 // - 'a allocated by us
 // - 'p coming from the input
 // - Cx global compilation context
-#[derive(Clone)]
+#[derive(derivative::Derivative)]
+#[derivative(Clone(bound = ""))]
 struct PatStack<'a, 'p, Cx: TypeCx> {
     // Rows of len 1 are very common, which is why `SmallVec[_; 2]` works well.
     pats: SmallVec<[&'a DeconstructedPat<'p, Cx>; 2]>,
+    /// Sometimes we know that as far as this row is concerned, the current case is already handled
+    /// by a different, more general, case. When the case is irrelevant for all rows this allows us
+    /// to skip a case entirely. This is purely an optimization. See at the top for details.
+    relevant: bool,
 }
 
 impl<'a, 'p, Cx: TypeCx> PatStack<'a, 'p, Cx> {
     fn from_pattern(pat: &'a DeconstructedPat<'p, Cx>) -> Self {
-        PatStack { pats: smallvec![pat] }
+        PatStack { pats: smallvec![pat], relevant: true }
     }
 
     fn is_empty(&self) -> bool {
@@ -713,12 +872,17 @@ impl<'a, 'p, Cx: TypeCx> PatStack<'a, 'p, Cx> {
         &self,
         pcx: &PlaceCtxt<'a, 'p, Cx>,
         ctor: &Constructor<Cx>,
+        ctor_is_relevant: bool,
     ) -> PatStack<'a, 'p, Cx> {
         // We pop the head pattern and push the new fields extracted from the arguments of
         // `self.head()`.
         let mut new_pats = self.head().specialize(pcx, ctor);
         new_pats.extend_from_slice(&self.pats[1..]);
-        PatStack { pats: new_pats }
+        // `ctor` is relevant for this row if it is the actual constructor of this row, or if the
+        // row has a wildcard and `ctor` is relevant for wildcards.
+        let ctor_is_relevant =
+            !matches!(self.head().ctor(), Constructor::Wildcard) || ctor_is_relevant;
+        PatStack { pats: new_pats, relevant: self.relevant && ctor_is_relevant }
     }
 }
 
@@ -784,10 +948,11 @@ impl<'a, 'p, Cx: TypeCx> MatrixRow<'a, 'p, Cx> {
         &self,
         pcx: &PlaceCtxt<'a, 'p, Cx>,
         ctor: &Constructor<Cx>,
+        ctor_is_relevant: bool,
         parent_row: usize,
     ) -> MatrixRow<'a, 'p, Cx> {
         MatrixRow {
-            pats: self.pats.pop_head_constructor(pcx, ctor),
+            pats: self.pats.pop_head_constructor(pcx, ctor, ctor_is_relevant),
             parent_row,
             is_under_guard: self.is_under_guard,
             useful: false,
@@ -845,8 +1010,7 @@ impl<'a, 'p, Cx: TypeCx> Matrix<'a, 'p, Cx> {
         scrut_ty: Cx::Ty,
         scrut_validity: ValidityConstraint,
     ) -> Self {
-        let wild_pattern =
-            wildcard_arena.alloc(DeconstructedPat::wildcard(scrut_ty, Default::default()));
+        let wild_pattern = wildcard_arena.alloc(DeconstructedPat::wildcard(scrut_ty));
         let wildcard_row = PatStack::from_pattern(wild_pattern);
         let mut matrix = Matrix {
             rows: Vec::with_capacity(arms.len()),
@@ -865,24 +1029,14 @@ impl<'a, 'p, Cx: TypeCx> Matrix<'a, 'p, Cx> {
         matrix
     }
 
-    fn head_ty(&self) -> Option<Cx::Ty> {
+    fn head_ty(&self, mcx: MatchCtxt<'a, 'p, Cx>) -> Option<Cx::Ty> {
         if self.column_count() == 0 {
             return None;
         }
 
-        let mut ty = self.wildcard_row.head().ty();
-        // If the type is opaque and it is revealed anywhere in the column, we take the revealed
-        // version. Otherwise we could encounter constructors for the revealed type and crash.
-        if Cx::is_opaque_ty(ty) {
-            for pat in self.heads() {
-                let pat_ty = pat.ty();
-                if !Cx::is_opaque_ty(pat_ty) {
-                    ty = pat_ty;
-                    break;
-                }
-            }
-        }
-        Some(ty)
+        let ty = self.wildcard_row.head().ty();
+        // FIXME(Nadrieril): `Cx` should only give us revealed types.
+        Some(mcx.tycx.reveal_opaque_ty(ty))
     }
     fn column_count(&self) -> usize {
         self.wildcard_row.len()
@@ -913,8 +1067,9 @@ impl<'a, 'p, Cx: TypeCx> Matrix<'a, 'p, Cx> {
         &self,
         pcx: &PlaceCtxt<'a, 'p, Cx>,
         ctor: &Constructor<Cx>,
+        ctor_is_relevant: bool,
     ) -> Matrix<'a, 'p, Cx> {
-        let wildcard_row = self.wildcard_row.pop_head_constructor(pcx, ctor);
+        let wildcard_row = self.wildcard_row.pop_head_constructor(pcx, ctor, ctor_is_relevant);
         let new_validity = self.place_validity[0].specialize(ctor);
         let new_place_validity = std::iter::repeat(new_validity)
             .take(ctor.arity(pcx))
@@ -924,7 +1079,7 @@ impl<'a, 'p, Cx: TypeCx> Matrix<'a, 'p, Cx> {
             Matrix { rows: Vec::new(), wildcard_row, place_validity: new_place_validity };
         for (i, row) in self.rows().enumerate() {
             if ctor.is_covered_by(pcx, row.head().ctor()) {
-                let new_row = row.pop_head_constructor(pcx, ctor, i);
+                let new_row = row.pop_head_constructor(pcx, ctor, ctor_is_relevant, i);
                 matrix.expand_and_push(new_row);
             }
         }
@@ -1032,7 +1187,8 @@ impl<'a, 'p, Cx: TypeCx> fmt::Debug for Matrix<'a, 'p, Cx> {
 /// The final `Pair(Some(_), true)` is then the resulting witness.
 ///
 /// See the top of the file for more detailed explanations and examples.
-#[derive(Debug, Clone)]
+#[derive(derivative::Derivative)]
+#[derivative(Debug(bound = ""), Clone(bound = ""))]
 struct WitnessStack<Cx: TypeCx>(Vec<WitnessPat<Cx>>);
 
 impl<Cx: TypeCx> WitnessStack<Cx> {
@@ -1079,7 +1235,8 @@ impl<Cx: TypeCx> WitnessStack<Cx> {
 ///
 /// Just as the `Matrix` starts with a single column, by the end of the algorithm, this has a single
 /// column, which contains the patterns that are missing for the match to be exhaustive.
-#[derive(Debug, Clone)]
+#[derive(derivative::Derivative)]
+#[derivative(Debug(bound = ""), Clone(bound = ""))]
 struct WitnessMatrix<Cx: TypeCx>(Vec<WitnessStack<Cx>>);
 
 impl<Cx: TypeCx> WitnessMatrix<Cx> {
@@ -1122,7 +1279,10 @@ impl<Cx: TypeCx> WitnessMatrix<Cx> {
         if matches!(ctor, Constructor::Missing) {
             // We got the special `Missing` constructor that stands for the constructors not present
             // in the match.
-            if !report_individual_missing_ctors {
+            if missing_ctors.is_empty() {
+                // Nothing to report.
+                *self = Self::empty();
+            } else if !report_individual_missing_ctors {
                 // Report `_` as missing.
                 let pat = WitnessPat::wild_from_ctor(pcx, Constructor::Wildcard);
                 self.push_pattern(pat);
@@ -1181,7 +1341,14 @@ fn compute_exhaustiveness_and_usefulness<'a, 'p, Cx: TypeCx>(
 ) -> WitnessMatrix<Cx> {
     debug_assert!(matrix.rows().all(|r| r.len() == matrix.column_count()));
 
-    let Some(ty) = matrix.head_ty() else {
+    if !matrix.wildcard_row.relevant && matrix.rows().all(|r| !r.pats.relevant) {
+        // Here we know that nothing will contribute further to exhaustiveness or usefulness. This
+        // is purely an optimization: skipping this check doesn't affect correctness. See the top of
+        // the file for details.
+        return WitnessMatrix::empty();
+    }
+
+    let Some(ty) = matrix.head_ty(mcx) else {
         // The base case: there are no columns in the matrix. We are morally pattern-matching on ().
         // A row is useful iff it has no (unguarded) rows above it.
         for row in matrix.rows_mut() {
@@ -1193,8 +1360,14 @@ fn compute_exhaustiveness_and_usefulness<'a, 'p, Cx: TypeCx>(
                 return WitnessMatrix::empty();
             }
         }
-        // No (unguarded) rows, so the match is not exhaustive. We return a new witness.
-        return WitnessMatrix::unit_witness();
+        // No (unguarded) rows, so the match is not exhaustive. We return a new witness unless
+        // irrelevant.
+        return if matrix.wildcard_row.relevant {
+            WitnessMatrix::unit_witness()
+        } else {
+            // We choose to not report anything here; see at the top for details.
+            WitnessMatrix::empty()
+        };
     };
 
     debug!("ty: {ty:?}");
@@ -1237,32 +1410,21 @@ fn compute_exhaustiveness_and_usefulness<'a, 'p, Cx: TypeCx>(
 
     let mut ret = WitnessMatrix::empty();
     for ctor in split_ctors {
-        debug!("specialize({:?})", ctor);
         // Dig into rows that match `ctor`.
-        let mut spec_matrix = matrix.specialize_constructor(pcx, &ctor);
+        debug!("specialize({:?})", ctor);
+        // `ctor` is *irrelevant* if there's another constructor in `split_ctors` that matches
+        // strictly fewer rows. In that case we can sometimes skip it. See the top of the file for
+        // details.
+        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, false)
         });
 
-        let counts_for_exhaustiveness = match ctor {
-            Constructor::Missing => !missing_ctors.is_empty(),
-            // If there are missing constructors we'll report those instead. Since `Missing` matches
-            // only the wildcard rows, it matches fewer rows than this constructor, and is therefore
-            // guaranteed to result in the same or more witnesses. So skipping this does not
-            // jeopardize correctness.
-            _ => missing_ctors.is_empty(),
-        };
-        if counts_for_exhaustiveness {
-            // Transform witnesses for `spec_matrix` into witnesses for `matrix`.
-            witnesses.apply_constructor(
-                pcx,
-                &missing_ctors,
-                &ctor,
-                report_individual_missing_ctors,
-            );
-            // Accumulate the found witnesses.
-            ret.extend(witnesses);
-        }
+        // Transform witnesses for `spec_matrix` into witnesses for `matrix`.
+        witnesses.apply_constructor(pcx, &missing_ctors, &ctor, report_individual_missing_ctors);
+        // Accumulate the found witnesses.
+        ret.extend(witnesses);
 
         // A parent row is useful if any of its children is.
         for child_row in spec_matrix.rows() {