6 files changed, 1471 insertions, 1 deletions
diff --git a/crates/hir_ty/Cargo.toml b/crates/hir_ty/Cargo.toml
index c3d02424d..4b714c6d8 100644
--- a/crates/hir_ty/Cargo.toml
+++ b/crates/hir_ty/Cargo.toml
@@ -22,6 +22,7 @@ chalk-solve = { version = "0.68", default-features = false }
 chalk-ir = "0.68"
 chalk-recursive = "0.68"
 la-arena = { version = "0.2.0", path = "../../lib/arena" }
+once_cell = { version = "1.5.0" }
 stdx = { path = "../stdx", version = "0.0.0" }
 hir_def = { path = "../hir_def", version = "0.0.0" }
diff --git a/crates/hir_ty/src/diagnostics.rs b/crates/hir_ty/src/diagnostics.rs
index 283894704..87a3594c5 100644
--- a/crates/hir_ty/src/diagnostics.rs
+++ b/crates/hir_ty/src/diagnostics.rs
@@ -1,6 +1,8 @@
 //! Type inference-based diagnostics.
 mod expr;
+#[allow(unused)] //todo
 mod match_check;
+mod pattern;
 mod unsafe_check;
 mod decl_check;
diff --git a/crates/hir_ty/src/diagnostics/expr.rs b/crates/hir_ty/src/diagnostics/expr.rs
index 86f82e3fa..ea70a5f9f 100644
--- a/crates/hir_ty/src/diagnostics/expr.rs
+++ b/crates/hir_ty/src/diagnostics/expr.rs
@@ -62,7 +62,7 @@ impl<'a, 'b> ExprValidator<'a, 'b> {
            match expr {
                Expr::Match { expr, arms } => {
-                    self.validate_match(id, *expr, arms, db, self.infer.clone());
+                    self.validate_match2(id, *expr, arms, db, self.infer.clone());
                }
                Expr::Call { .. } | Expr::MethodCall { .. } => {
                    self.validate_call(db, id, expr);
@@ -277,6 +277,7 @@ impl<'a, 'b> ExprValidator<'a, 'b> {
        }
    }
+    #[allow(dead_code)]
    fn validate_match(
        &mut self,
        id: ExprId,
@@ -358,6 +359,73 @@ impl<'a, 'b> ExprValidator<'a, 'b> {
        }
    }
+    fn validate_match2(
+        &mut self,
+        id: ExprId,
+        match_expr: ExprId,
+        arms: &[MatchArm],
+        db: &dyn HirDatabase,
+        infer: Arc<InferenceResult>,
+    ) {
+        use crate::diagnostics::pattern::usefulness;
+        use hir_def::HasModule;
+        let (body, source_map): (Arc<Body>, Arc<BodySourceMap>) =
+            db.body_with_source_map(self.owner);
+        let match_expr_ty = if infer.type_of_expr[match_expr].is_unknown() {
+            return;
+        } else {
+            &infer.type_of_expr[match_expr]
+        };
+        eprintln!("ExprValidator::validate_match2({:?})", match_expr_ty.kind(&Interner));
+        let pattern_arena = usefulness::PatternArena::clone_from(&body.pats);
+        let cx = usefulness::MatchCheckCtx {
+            krate: self.owner.module(db.upcast()).krate(),
+            match_expr,
+            body,
+            infer: &infer,
+            db,
+            pattern_arena: &pattern_arena,
+        };
+        let m_arms: Vec<_> = arms
+            .iter()
+            .map(|arm| usefulness::MatchArm { pat: arm.pat, has_guard: arm.guard.is_some() })
+            .collect();
+        let report = usefulness::compute_match_usefulness(&cx, &m_arms);
+        // TODO Report unreacheble arms
+        // let mut catchall = None;
+        // for (arm_index, (arm, is_useful)) in report.arm_usefulness.iter().enumerate() {
+        //     match is_useful{
+        //         Unreachable => {
+        //         }
+        //         Reachable(_) => {}
+        //     }
+        // }
+        let witnesses = report.non_exhaustiveness_witnesses;
+        if !witnesses.is_empty() {
+            if let Ok(source_ptr) = source_map.expr_syntax(id) {
+                let root = source_ptr.file_syntax(db.upcast());
+                if let ast::Expr::MatchExpr(match_expr) = &source_ptr.value.to_node(&root) {
+                    if let (Some(match_expr), Some(arms)) =
+                        (match_expr.expr(), match_expr.match_arm_list())
+                    {
+                        self.sink.push(MissingMatchArms {
+                            file: source_ptr.file_id,
+                            match_expr: AstPtr::new(&match_expr),
+                            arms: AstPtr::new(&arms),
+                        })
+                    }
+                }
+            }
+        }
+    }
    fn validate_results_in_tail_expr(&mut self, body_id: ExprId, id: ExprId, db: &dyn HirDatabase) {
        // the mismatch will be on the whole block currently
        let mismatch = match self.infer.type_mismatch_for_expr(body_id) {
diff --git a/crates/hir_ty/src/diagnostics/pattern.rs b/crates/hir_ty/src/diagnostics/pattern.rs
new file mode 100644
index 000000000..28c7a244d
--- /dev/null
+++ b/crates/hir_ty/src/diagnostics/pattern.rs
@@ -0,0 +1,36 @@
+#![deny(elided_lifetimes_in_paths)]
+#![allow(unused)] // todo remove
+mod deconstruct_pat;
+pub mod usefulness;
+#[cfg(test)]
+mod tests {
+    use crate::diagnostics::tests::check_diagnostics;
+    use super::*;
+    #[test]
+    fn unit_exhaustive() {
+        check_diagnostics(
+            r#"
+fn main() {
+    match ()   { ()   => {} }
+    match ()   { _    => {} }
+}
+"#,
+        );
+    }
+    #[test]
+    fn unit_non_exhaustive() {
+        check_diagnostics(
+            r#"
+fn main() {
+    match ()   {            }
+        //^^ Missing match arm
+}
+"#,
+        );
+    }
+}
diff --git a/crates/hir_ty/src/diagnostics/pattern/deconstruct_pat.rs b/crates/hir_ty/src/diagnostics/pattern/deconstruct_pat.rs
new file mode 100644
index 000000000..cde04409e
--- /dev/null
+++ b/crates/hir_ty/src/diagnostics/pattern/deconstruct_pat.rs
@@ -0,0 +1,627 @@
+use hir_def::{
+    expr::{Pat, PatId},
+    AttrDefId, EnumVariantId, HasModule, VariantId,
+};
+use smallvec::{smallvec, SmallVec};
+use crate::{AdtId, Interner, Scalar, Ty, TyExt, TyKind};
+use super::usefulness::{MatchCheckCtx, PatCtxt};
+use self::Constructor::*;
+#[derive(Copy, Clone, Debug, PartialEq, Eq)]
+pub(super) enum ToDo {}
+#[derive(Clone, Debug, PartialEq, Eq)]
+pub(super) struct IntRange {
+    range: ToDo,
+}
+impl IntRange {
+    #[inline]
+    fn is_integral(ty: &Ty) -> bool {
+        match ty.kind(&Interner) {
+            TyKind::Scalar(Scalar::Char)
+            | TyKind::Scalar(Scalar::Int(_))
+            | TyKind::Scalar(Scalar::Uint(_))
+            | TyKind::Scalar(Scalar::Bool) => true,
+            _ => false,
+        }
+    }
+    /// See `Constructor::is_covered_by`
+    fn is_covered_by(&self, other: &Self) -> bool {
+        todo!()
+    }
+}
+/// A constructor for array and slice patterns.
+#[derive(Copy, Clone, Debug, PartialEq, Eq)]
+pub(super) struct Slice {
+    todo: ToDo,
+}
+impl Slice {
+    /// See `Constructor::is_covered_by`
+    fn is_covered_by(self, other: Self) -> bool {
+        todo!()
+    }
+}
+/// A value can be decomposed into a constructor applied to some fields. This struct represents
+/// the constructor. See also `Fields`.
+///
+/// `pat_constructor` retrieves the constructor corresponding to a pattern.
+/// `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)]
+pub(super) enum Constructor {
+    /// The constructor for patterns that have a single constructor, like tuples, struct patterns
+    /// and fixed-length arrays.
+    Single,
+    /// Enum variants.
+    Variant(EnumVariantId),
+    /// Ranges of integer literal values (`2`, `2..=5` or `2..5`).
+    IntRange(IntRange),
+    /// Array and slice patterns.
+    Slice(Slice),
+    /// Stands for constructors that are not seen in the matrix, as explained in the documentation
+    /// for [`SplitWildcard`].
+    Missing,
+    /// Wildcard pattern.
+    Wildcard,
+}
+impl Constructor {
+    pub(super) fn is_wildcard(&self) -> bool {
+        matches!(self, Wildcard)
+    }
+    fn as_int_range(&self) -> Option<&IntRange> {
+        match self {
+            IntRange(range) => Some(range),
+            _ => None,
+        }
+    }
+    fn as_slice(&self) -> Option<Slice> {
+        match self {
+            Slice(slice) => Some(*slice),
+            _ => None,
+        }
+    }
+    fn variant_id_for_adt(&self, adt: hir_def::AdtId, cx: &MatchCheckCtx<'_>) -> VariantId {
+        match *self {
+            Variant(id) => id.into(),
+            Single => {
+                assert!(!matches!(adt, hir_def::AdtId::EnumId(_)));
+                match adt {
+                    hir_def::AdtId::EnumId(_) => unreachable!(),
+                    hir_def::AdtId::StructId(id) => id.into(),
+                    hir_def::AdtId::UnionId(id) => id.into(),
+                }
+            }
+            _ => panic!("bad constructor {:?} for adt {:?}", self, adt),
+        }
+    }
+    pub(super) fn from_pat(cx: &MatchCheckCtx<'_>, pat: PatId) -> Self {
+        match &cx.pattern_arena.borrow()[pat] {
+            Pat::Bind { .. } | Pat::Wild => Wildcard,
+            Pat::Tuple { .. } | Pat::Ref { .. } | Pat::Box { .. } => Single,
+            pat => todo!("Constructor::from_pat {:?}", pat),
+            // Pat::Missing => {}
+            // Pat::Or(_) => {}
+            // Pat::Record { path, args, ellipsis } => {}
+            // Pat::Range { start, end } => {}
+            // Pat::Slice { prefix, slice, suffix } => {}
+            // Pat::Path(_) => {}
+            // Pat::Lit(_) => {}
+            // Pat::TupleStruct { path, args, ellipsis } => {}
+            // Pat::ConstBlock(_) => {}
+        }
+    }
+    /// Some constructors (namely `Wildcard`, `IntRange` and `Slice`) actually stand for a set of actual
+    /// constructors (like variants, integers or fixed-sized slices). When specializing for these
+    /// constructors, we want to be specialising for the actual underlying constructors.
+    /// Naively, we would simply return the list of constructors they correspond to. We instead are
+    /// more clever: if there are constructors that we know will behave the same wrt the current
+    /// matrix, we keep them grouped. For example, all slices of a sufficiently large length
+    /// will either be all useful or all non-useful with a given matrix.
+    ///
+    /// See the branches for details on how the splitting is done.
+    ///
+    /// This function may discard some irrelevant constructors if this preserves behavior and
+    /// diagnostics. Eg. for the `_` case, we ignore the constructors already present in the
+    /// matrix, unless all of them are.
+    pub(super) fn split<'a>(
+        &self,
+        pcx: &PatCtxt<'_>,
+        ctors: impl Iterator<Item = &'a Constructor> + Clone,
+    ) -> SmallVec<[Self; 1]> {
+        match self {
+            Wildcard => {
+                let mut split_wildcard = SplitWildcard::new(pcx);
+                split_wildcard.split(pcx, ctors);
+                split_wildcard.into_ctors(pcx)
+            }
+            // Fast-track if the range is trivial. In particular, we don't do the overlapping
+            // ranges check.
+            IntRange(_) => todo!("Constructor::split IntRange"),
+            Slice(_) => todo!("Constructor::split Slice"),
+            // Any other constructor can be used unchanged.
+            _ => smallvec![self.clone()],
+        }
+    }
+    /// Returns whether `self` is covered by `other`, i.e. whether `self` is a subset of `other`.
+    /// For the simple cases, this is simply checking for equality. For the "grouped" constructors,
+    /// this checks for inclusion.
+    // We inline because this has a single call site in `Matrix::specialize_constructor`.
+    #[inline]
+    pub(super) fn is_covered_by(&self, pcx: &PatCtxt<'_>, other: &Self) -> bool {
+        // This must be kept in sync with `is_covered_by_any`.
+        match (self, other) {
+            // Wildcards cover anything
+            (_, Wildcard) => true,
+            // The missing ctors are not covered by anything in the matrix except wildcards.
+            (Missing, _) | (Wildcard, _) => false,
+            (Single, Single) => true,
+            (Variant(self_id), Variant(other_id)) => self_id == other_id,
+            (Constructor::IntRange(_), Constructor::IntRange(_)) => todo!(),
+            (Constructor::Slice(_), Constructor::Slice(_)) => todo!(),
+            _ => panic!("bug"),
+        }
+    }
+    /// Faster version of `is_covered_by` when applied to many constructors. `used_ctors` is
+    /// assumed to be built from `matrix.head_ctors()` with wildcards filtered out, and `self` is
+    /// assumed to have been split from a wildcard.
+    fn is_covered_by_any(&self, pcx: &PatCtxt<'_>, used_ctors: &[Constructor]) -> bool {
+        if used_ctors.is_empty() {
+            return false;
+        }
+        // This must be kept in sync with `is_covered_by`.
+        match self {
+            // If `self` is `Single`, `used_ctors` cannot contain anything else than `Single`s.
+            Single => !used_ctors.is_empty(),
+            Variant(_) => used_ctors.iter().any(|c| c == self),
+            IntRange(range) => used_ctors
+                .iter()
+                .filter_map(|c| c.as_int_range())
+                .any(|other| range.is_covered_by(other)),
+            Slice(slice) => used_ctors
+                .iter()
+                .filter_map(|c| c.as_slice())
+                .any(|other| slice.is_covered_by(other)),
+            _ => todo!(),
+        }
+    }
+}
+/// A wildcard constructor that we split relative to the constructors in the matrix, as explained
+/// at the top of the file.
+///
+/// A constructor that is not present in the matrix rows will only be covered by the rows that have
+/// wildcards. Thus we can group all of those constructors together; we call them "missing
+/// constructors". Splitting a wildcard would therefore list all present constructors individually
+/// (or grouped if they are integers or slices), and then all missing constructors together as a
+/// group.
+///
+/// However we can go further: since any constructor will match the wildcard rows, and having more
+/// rows can only reduce the amount of usefulness witnesses, we can skip the present constructors
+/// and only try the missing ones.
+/// This will not preserve the whole list of witnesses, but will preserve whether the list is empty
+/// or not. In fact this is quite natural from the point of view of diagnostics too. This is done
+/// in `to_ctors`: in some cases we only return `Missing`.
+#[derive(Debug)]
+pub(super) struct SplitWildcard {
+    /// Constructors seen in the matrix.
+    matrix_ctors: Vec<Constructor>,
+    /// All the constructors for this type
+    all_ctors: SmallVec<[Constructor; 1]>,
+}
+impl SplitWildcard {
+    pub(super) fn new(pcx: &PatCtxt<'_>) -> Self {
+        // let cx = pcx.cx;
+        // let make_range = |start, end| IntRange(todo!());
+        // This determines the set of all possible constructors for the type `pcx.ty`. For numbers,
+        // arrays and slices we use ranges and variable-length slices when appropriate.
+        //
+        // If the `exhaustive_patterns` feature is enabled, we make sure to omit constructors that
+        // are statically impossible. E.g., for `Option<!>`, we do not include `Some(_)` in the
+        // returned list of constructors.
+        // Invariant: this is empty if and only if the type is uninhabited (as determined by
+        // `cx.is_uninhabited()`).
+        let all_ctors = match pcx.ty.kind(&Interner) {
+            TyKind::Adt(AdtId(hir_def::AdtId::EnumId(_)), _) => todo!(),
+            TyKind::Adt(..) | TyKind::Tuple(..) | TyKind::Ref(..) => smallvec![Single],
+            _ => todo!(),
+        };
+        SplitWildcard { matrix_ctors: Vec::new(), all_ctors }
+    }
+    /// Pass a set of constructors relative to which to split this one. Don't call twice, it won't
+    /// do what you want.
+    pub(super) fn split<'a>(
+        &mut self,
+        pcx: &PatCtxt<'_>,
+        ctors: impl Iterator<Item = &'a Constructor> + Clone,
+    ) {
+        // Since `all_ctors` never contains wildcards, this won't recurse further.
+        self.all_ctors =
+            self.all_ctors.iter().flat_map(|ctor| ctor.split(pcx, ctors.clone())).collect();
+        self.matrix_ctors = ctors.filter(|c| !c.is_wildcard()).cloned().collect();
+    }
+    /// Whether there are any value constructors for this type that are not present in the matrix.
+    fn any_missing(&self, pcx: &PatCtxt<'_>) -> bool {
+        self.iter_missing(pcx).next().is_some()
+    }
+    /// Iterate over the constructors for this type that are not present in the matrix.
+    pub(super) fn iter_missing<'a>(
+        &'a self,
+        pcx: &'a PatCtxt<'_>,
+    ) -> impl Iterator<Item = &'a Constructor> {
+        self.all_ctors.iter().filter(move |ctor| !ctor.is_covered_by_any(pcx, &self.matrix_ctors))
+    }
+    /// Return the set of constructors resulting from splitting the wildcard. As explained at the
+    /// top of the file, if any constructors are missing we can ignore the present ones.
+    fn into_ctors(self, pcx: &PatCtxt<'_>) -> SmallVec<[Constructor; 1]> {
+        if self.any_missing(pcx) {
+            // Some constructors are missing, thus we can specialize with the special `Missing`
+            // constructor, which stands for those constructors that are not seen in the matrix,
+            // and matches the same rows as any of them (namely the wildcard rows). See the top of
+            // the file for details.
+            // However, when all constructors are missing we can also specialize with the full
+            // `Wildcard` constructor. The difference will depend on what we want in diagnostics.
+            // If some constructors are missing, we typically want to report those constructors,
+            // e.g.:
+            // ```
+            //     enum Direction { N, S, E, W }
+            //     let Direction::N = ...;
+            // ```
+            // we can report 3 witnesses: `S`, `E`, and `W`.
+            //
+            // However, if the user didn't actually specify a constructor
+            // in this arm, e.g., in
+            // ```
+            //     let x: (Direction, Direction, bool) = ...;
+            //     let (_, _, false) = x;
+            // ```
+            // we don't want to show all 16 possible witnesses `(<direction-1>, <direction-2>,
+            // true)` - we are satisfied with `(_, _, true)`. So if all constructors are missing we
+            // prefer to report just a wildcard `_`.
+            //
+            // The exception is: if we are at the top-level, for example in an empty match, we
+            // sometimes prefer reporting the list of constructors instead of just `_`.
+            let report_when_all_missing = pcx.is_top_level && !IntRange::is_integral(&pcx.ty);
+            let ctor = if !self.matrix_ctors.is_empty() || report_when_all_missing {
+                Missing
+            } else {
+                Wildcard
+            };
+            return smallvec![ctor];
+        }
+        // All the constructors are present in the matrix, so we just go through them all.
+        self.all_ctors
+    }
+}
+#[test]
+fn it_works2() {}
+/// Some fields need to be explicitly hidden away in certain cases; see the comment above the
+/// `Fields` struct. This struct represents such a potentially-hidden field.
+#[derive(Debug, Copy, Clone)]
+pub(super) enum FilteredField {
+    Kept(PatId),
+    Hidden,
+}
+impl FilteredField {
+    fn kept(self) -> Option<PatId> {
+        match self {
+            FilteredField::Kept(p) => Some(p),
+            FilteredField::Hidden => None,
+        }
+    }
+}
+/// A value can be decomposed into a constructor applied to some fields. This struct represents
+/// those fields, generalized to allow patterns in each field. See also `Constructor`.
+/// This is constructed from a constructor using [`Fields::wildcards()`].
+///
+/// If a private or `non_exhaustive` field is uninhabited, the code mustn't observe that it is
+/// uninhabited. For that, we filter these fields out of the matrix. This is handled automatically
+/// in `Fields`. This filtering is uncommon in practice, because uninhabited fields are rarely used,
+/// so we avoid it when possible to preserve performance.
+#[derive(Debug, Clone)]
+pub(super) enum Fields {
+    /// Lists of patterns that don't contain any filtered fields.
+    /// `Slice` and `Vec` behave the same; the difference is only to avoid allocating and
+    /// triple-dereferences when possible. Frankly this is premature optimization, I (Nadrieril)
+    /// have not measured if it really made a difference.
+    Vec(SmallVec<[PatId; 2]>),
+}
+impl Fields {
+    /// Internal use. Use `Fields::wildcards()` instead.
+    /// Must not be used if the pattern is a field of a struct/tuple/variant.
+    fn from_single_pattern(pat: PatId) -> Self {
+        Fields::Vec(smallvec![pat])
+    }
+    /// Convenience; internal use.
+    fn wildcards_from_tys<'a>(
+        cx: &MatchCheckCtx<'_>,
+        tys: impl IntoIterator<Item = &'a Ty>,
+    ) -> Self {
+        let wilds = tys.into_iter().map(|ty| (Pat::Wild, ty));
+        let pats = wilds.map(|(pat, ty)| cx.alloc_pat(pat, ty)).collect();
+        Fields::Vec(pats)
+    }
+    pub(crate) fn wildcards(pcx: &PatCtxt<'_>, constructor: &Constructor) -> Self {
+        let ty = &pcx.ty;
+        let cx = pcx.cx;
+        let wildcard_from_ty = |ty| cx.alloc_pat(Pat::Wild, ty);
+        let ret = match constructor {
+            Single | Variant(_) => match ty.kind(&Interner) {
+                TyKind::Tuple(_, substs) => {
+                    let tys = substs.iter(&Interner).map(|ty| ty.assert_ty_ref(&Interner));
+                    Fields::wildcards_from_tys(cx, tys)
+                }
+                TyKind::Ref(.., rty) => Fields::from_single_pattern(wildcard_from_ty(rty)),
+                TyKind::Adt(AdtId(adt), substs) => {
+                    let adt_is_box = false; // TODO(iDawer): handle box patterns
+                    if adt_is_box {
+                        // Use T as the sub pattern type of Box<T>.
+                        let ty = substs.at(&Interner, 0).assert_ty_ref(&Interner);
+                        Fields::from_single_pattern(wildcard_from_ty(ty))
+                    } else {
+                        let variant_id = constructor.variant_id_for_adt(*adt, cx);
+                        let variant = variant_id.variant_data(cx.db.upcast());
+                        let adt_is_local = variant_id.module(cx.db.upcast()).krate() == cx.krate;
+                        // Whether we must not match the fields of this variant exhaustively.
+                        let is_non_exhaustive =
+                            is_field_list_non_exhaustive(variant_id, cx) && !adt_is_local;
+                        let field_ty_arena = cx.db.field_types(variant_id);
+                        let field_tys =
+                            || field_ty_arena.iter().map(|(_, binders)| binders.skip_binders());
+                        // In the following cases, we don't need to filter out any fields. This is
+                        // the vast majority of real cases, since uninhabited fields are uncommon.
+                        let has_no_hidden_fields = (matches!(adt, hir_def::AdtId::EnumId(_))
+                            && !is_non_exhaustive)
+                            || !field_tys().any(|ty| cx.is_uninhabited(ty));
+                        if has_no_hidden_fields {
+                            Fields::wildcards_from_tys(cx, field_tys())
+                        } else {
+                            //FIXME(iDawer): see MatchCheckCtx::is_uninhabited
+                            unimplemented!("exhaustive_patterns feature")
+                        }
+                    }
+                }
+                _ => panic!("Unexpected type for `Single` constructor: {:?}", ty),
+            },
+            Missing | Wildcard => Fields::Vec(Default::default()),
+            _ => todo!(),
+        };
+        ret
+    }
+    /// Apply a constructor to a list of patterns, yielding a new pattern. `self`
+    /// must have as many elements as this constructor's arity.
+    ///
+    /// This is roughly the inverse of `specialize_constructor`.
+    ///
+    /// Examples:
+    /// `ctor`: `Constructor::Single`
+    /// `ty`: `Foo(u32, u32, u32)`
+    /// `self`: `[10, 20, _]`
+    /// returns `Foo(10, 20, _)`
+    ///
+    /// `ctor`: `Constructor::Variant(Option::Some)`
+    /// `ty`: `Option<bool>`
+    /// `self`: `[false]`
+    /// returns `Some(false)`
+    pub(super) fn apply(self, pcx: &PatCtxt<'_>, ctor: &Constructor) -> Pat {
+        let subpatterns_and_indices = self.patterns_and_indices();
+        let mut subpatterns = subpatterns_and_indices.iter().map(|&(_, p)| p);
+        match ctor {
+            Single | Variant(_) => match pcx.ty.kind(&Interner) {
+                TyKind::Adt(..) | TyKind::Tuple(..) => {
+                    // We want the real indices here.
+                    // TODO indices
+                    let subpatterns = subpatterns_and_indices.iter().map(|&(_, pat)| pat).collect();
+                    if let Some((adt, substs)) = pcx.ty.as_adt() {
+                        if let hir_def::AdtId::EnumId(_) = adt {
+                            todo!()
+                        } else {
+                            todo!()
+                        }
+                    } else {
+                        // TODO ellipsis
+                        Pat::Tuple { args: subpatterns, ellipsis: None }
+                    }
+                }
+                _ => todo!(),
+                // TyKind::AssociatedType(_, _) => {}
+                // TyKind::Scalar(_) => {}
+                // TyKind::Array(_, _) => {}
+                // TyKind::Slice(_) => {}
+                // TyKind::Raw(_, _) => {}
+                // TyKind::Ref(_, _, _) => {}
+                // TyKind::OpaqueType(_, _) => {}
+                // TyKind::FnDef(_, _) => {}
+                // TyKind::Str => {}
+                // TyKind::Never => {}
+                // TyKind::Closure(_, _) => {}
+                // TyKind::Generator(_, _) => {}
+                // TyKind::GeneratorWitness(_, _) => {}
+                // TyKind::Foreign(_) => {}
+                // TyKind::Error => {}
+                // TyKind::Placeholder(_) => {}
+                // TyKind::Dyn(_) => {}
+                // TyKind::Alias(_) => {}
+                // TyKind::Function(_) => {}
+                // TyKind::BoundVar(_) => {}
+                // TyKind::InferenceVar(_, _) => {}
+            },
+            _ => todo!(),
+            // Constructor::IntRange(_) => {}
+            // Constructor::Slice(_) => {}
+            // Missing => {}
+            // Wildcard => {}
+        }
+    }
+    /// Returns the number of patterns. This is the same as the arity of the constructor used to
+    /// construct `self`.
+    pub(super) fn len(&self) -> usize {
+        match self {
+            Fields::Vec(pats) => pats.len(),
+        }
+    }
+    /// Returns the list of patterns along with the corresponding field indices.
+    fn patterns_and_indices(&self) -> SmallVec<[(usize, PatId); 2]> {
+        match self {
+            Fields::Vec(pats) => pats.iter().copied().enumerate().collect(),
+        }
+    }
+    pub(super) fn into_patterns(self) -> SmallVec<[PatId; 2]> {
+        match self {
+            Fields::Vec(pats) => pats,
+        }
+    }
+    /// Overrides some of the fields with the provided patterns. Exactly like
+    /// `replace_fields_indexed`, except that it takes `FieldPat`s as input.
+    fn replace_with_fieldpats(&self, new_pats: impl IntoIterator<Item = PatId>) -> Self {
+        self.replace_fields_indexed(new_pats.into_iter().enumerate())
+    }
+    /// Overrides some of the fields with the provided patterns. This is used when a pattern
+    /// defines some fields but not all, for example `Foo { field1: Some(_), .. }`: here we start
+    /// with a `Fields` that is just one wildcard per field of the `Foo` struct, and override the
+    /// entry corresponding to `field1` with the pattern `Some(_)`. This is also used for slice
+    /// patterns for the same reason.
+    fn replace_fields_indexed(&self, new_pats: impl IntoIterator<Item = (usize, PatId)>) -> Self {
+        let mut fields = self.clone();
+        match &mut fields {
+            Fields::Vec(pats) => {
+                for (i, pat) in new_pats {
+                    if let Some(p) = pats.get_mut(i) {
+                        *p = pat;
+                    }
+                }
+            }
+        }
+        fields
+    }
+    /// Replaces contained fields with the given list of patterns. There must be `len()` patterns
+    /// in `pats`.
+    pub(super) fn replace_fields(
+        &self,
+        cx: &MatchCheckCtx<'_>,
+        pats: impl IntoIterator<Item = Pat>,
+    ) -> Self {
+        let pats = {
+            let mut arena = cx.pattern_arena.borrow_mut();
+            pats.into_iter().map(move |pat| /* arena.alloc(pat) */ todo!()).collect()
+        };
+        match self {
+            Fields::Vec(_) => Fields::Vec(pats),
+        }
+    }
+    /// Replaces contained fields with the arguments of the given pattern. Only use on a pattern
+    /// that is compatible with the constructor used to build `self`.
+    /// This is meant to be used on the result of `Fields::wildcards()`. The idea is that
+    /// `wildcards` constructs a list of fields where all entries are wildcards, and the pattern
+    /// provided to this function fills some of the fields with non-wildcards.
+    /// In the following example `Fields::wildcards` would return `[_, _, _, _]`. If we call
+    /// `replace_with_pattern_arguments` on it with the pattern, the result will be `[Some(0), _,
+    /// _, _]`.
+    /// ```rust
+    /// let x: [Option<u8>; 4] = foo();
+    /// match x {
+    ///     [Some(0), ..] => {}
+    /// }
+    /// ```
+    /// This is guaranteed to preserve the number of patterns in `self`.
+    pub(super) fn replace_with_pattern_arguments(
+        &self,
+        pat: PatId,
+        cx: &MatchCheckCtx<'_>,
+    ) -> Self {
+        match &cx.pattern_arena.borrow()[pat] {
+            Pat::Ref { pat: subpattern, .. } => {
+                assert_eq!(self.len(), 1);
+                Fields::from_single_pattern(*subpattern)
+            }
+            Pat::Tuple { args: subpatterns, ellipsis } => {
+                // FIXME(iDawer) handle ellipsis.
+                // XXX(iDawer): in rustc, this is handled by HIR->TypedHIR lowering
+                // rustc_mir_build::thir::pattern::PatCtxt::lower_tuple_subpats(..)
+                self.replace_with_fieldpats(subpatterns.iter().copied())
+            }
+            Pat::Wild => self.clone(),
+            pat => todo!("Fields::replace_with_pattern_arguments({:?})", pat),
+            // Pat::Missing => {}
+            // Pat::Or(_) => {}
+            // Pat::Record { path, args, ellipsis } => {}
+            // Pat::Range { start, end } => {}
+            // Pat::Slice { prefix, slice, suffix } => {}
+            // Pat::Path(_) => {}
+            // Pat::Lit(_) => {}
+            // Pat::Bind { mode, name, subpat } => {}
+            // Pat::TupleStruct { path, args, ellipsis } => {}
+            // Pat::Box { inner } => {}
+            // Pat::ConstBlock(_) => {}
+        }
+    }
+}
+fn is_field_list_non_exhaustive(variant_id: VariantId, cx: &MatchCheckCtx<'_>) -> bool {
+    let attr_def_id = match variant_id {
+        VariantId::EnumVariantId(id) => id.into(),
+        VariantId::StructId(id) => id.into(),
+        VariantId::UnionId(id) => id.into(),
+    };
+    cx.db.attrs(attr_def_id).by_key("non_exhaustive").exists()
+}
+#[test]
+fn it_works() {}
diff --git a/crates/hir_ty/src/diagnostics/pattern/usefulness.rs b/crates/hir_ty/src/diagnostics/pattern/usefulness.rs
new file mode 100644
index 000000000..f5f6bf494
--- /dev/null
+++ b/crates/hir_ty/src/diagnostics/pattern/usefulness.rs
@@ -0,0 +1,736 @@
+// Based on rust-lang/rust 1.52.0-nightly (25c15cdbe 2021-04-22)
+// rust/compiler/rustc_mir_build/src/thir/pattern/usefulness.rs
+use std::{cell::RefCell, iter::FromIterator, ops::Index, sync::Arc};
+use base_db::CrateId;
+use hir_def::{
+    body::Body,
+    expr::{ExprId, Pat, PatId},
+};
+use la_arena::Arena;
+use once_cell::unsync::OnceCell;
+use rustc_hash::FxHashMap;
+use smallvec::{smallvec, SmallVec};
+use crate::{db::HirDatabase, InferenceResult, Ty};
+use super::deconstruct_pat::{Constructor, Fields, SplitWildcard};
+use self::{
+    helper::{Captures, PatIdExt},
+    Usefulness::*,
+    WitnessPreference::*,
+};
+pub(crate) struct MatchCheckCtx<'a> {
+    pub(crate) krate: CrateId,
+    pub(crate) match_expr: ExprId,
+    pub(crate) body: Arc<Body>,
+    pub(crate) infer: &'a InferenceResult,
+    pub(crate) db: &'a dyn HirDatabase,
+    /// Patterns from self.body.pats plus generated by the check.
+    pub(crate) pattern_arena: &'a RefCell<PatternArena>,
+}
+impl<'a> MatchCheckCtx<'a> {
+    pub(super) fn is_uninhabited(&self, ty: &Ty) -> bool {
+        // FIXME(iDawer) implement exhaustive_patterns feature. More info in:
+        // Tracking issue for RFC 1872: exhaustive_patterns feature https://github.com/rust-lang/rust/issues/51085
+        false
+    }
+    pub(super) fn alloc_pat(&self, pat: Pat, ty: &Ty) -> PatId {
+        self.pattern_arena.borrow_mut().alloc(pat, ty)
+    }
+    /// Get type of a pattern. Handles expanded patterns.
+    pub(super) fn type_of(&self, pat: PatId) -> Ty {
+        let type_of_expanded_pat = self.pattern_arena.borrow().type_of_epat.get(&pat).cloned();
+        type_of_expanded_pat.unwrap_or_else(|| self.infer[pat].clone())
+    }
+}
+#[derive(Clone)]
+pub(super) struct PatCtxt<'a> {
+    pub(super) cx: &'a MatchCheckCtx<'a>,
+    /// Type of the current column under investigation.
+    pub(super) ty: Ty,
+    /// Whether the current pattern is the whole pattern as found in a match arm, or if it's a
+    /// subpattern.
+    pub(super) is_top_level: bool,
+}
+impl PatIdExt for PatId {
+    fn is_wildcard(self, cx: &MatchCheckCtx<'_>) -> bool {
+        matches!(cx.pattern_arena.borrow()[self], Pat::Bind { subpat: None, .. } | Pat::Wild)
+    }
+    fn is_or_pat(self, cx: &MatchCheckCtx<'_>) -> bool {
+        matches!(cx.pattern_arena.borrow()[self], Pat::Or(..))
+    }
+    /// Recursively expand this pattern into its subpatterns. Only useful for or-patterns.
+    fn expand_or_pat(self, cx: &MatchCheckCtx<'_>) -> Vec<Self> {
+        fn expand(pat: PatId, vec: &mut Vec<PatId>, pat_arena: &PatternArena) {
+            if let Pat::Or(pats) = &pat_arena[pat] {
+                for &pat in pats {
+                    expand(pat, vec, pat_arena);
+                }
+            } else {
+                vec.push(pat)
+            }
+        }
+        let pat_arena = cx.pattern_arena.borrow();
+        let mut pats = Vec::new();
+        expand(self, &mut pats, &pat_arena);
+        pats
+    }
+}
+/// A row of a matrix. Rows of len 1 are very common, which is why `SmallVec[_; 2]`
+/// works well.
+#[derive(Clone)]
+pub(super) struct PatStack {
+    pats: SmallVec<[PatId; 2]>,
+    /// Cache for the constructor of the head
+    head_ctor: OnceCell<Constructor>,
+}
+impl PatStack {
+    fn from_pattern(pat: PatId) -> Self {
+        Self::from_vec(smallvec![pat])
+    }
+    fn from_vec(vec: SmallVec<[PatId; 2]>) -> Self {
+        PatStack { pats: vec, head_ctor: OnceCell::new() }
+    }
+    fn is_empty(&self) -> bool {
+        self.pats.is_empty()
+    }
+    fn len(&self) -> usize {
+        self.pats.len()
+    }
+    fn head(&self) -> PatId {
+        self.pats[0]
+    }
+    #[inline]
+    fn head_ctor(&self, cx: &MatchCheckCtx<'_>) -> &Constructor {
+        self.head_ctor.get_or_init(|| Constructor::from_pat(cx, self.head()))
+    }
+    fn iter(&self) -> impl Iterator<Item = PatId> + '_ {
+        self.pats.iter().copied()
+    }
+    // Recursively expand the first pattern into its subpatterns. Only useful if the pattern is an
+    // or-pattern. Panics if `self` is empty.
+    fn expand_or_pat(&self, cx: &MatchCheckCtx<'_>) -> impl Iterator<Item = PatStack> + '_ {
+        self.head().expand_or_pat(cx).into_iter().map(move |pat| {
+            let mut new_patstack = PatStack::from_pattern(pat);
+            new_patstack.pats.extend_from_slice(&self.pats[1..]);
+            new_patstack
+        })
+    }
+    /// This computes `S(self.head_ctor(), self)`. See top of the file for explanations.
+    ///
+    /// Structure patterns with a partial wild pattern (Foo { a: 42, .. }) have their missing
+    /// fields filled with wild patterns.
+    ///
+    /// This is roughly the inverse of `Constructor::apply`.
+    fn pop_head_constructor(
+        &self,
+        ctor_wild_subpatterns: &Fields,
+        cx: &MatchCheckCtx<'_>,
+    ) -> PatStack {
+        // We pop the head pattern and push the new fields extracted from the arguments of
+        // `self.head()`.
+        let mut new_fields =
+            ctor_wild_subpatterns.replace_with_pattern_arguments(self.head(), cx).into_patterns();
+        new_fields.extend_from_slice(&self.pats[1..]);
+        PatStack::from_vec(new_fields)
+    }
+}
+impl Default for PatStack {
+    fn default() -> Self {
+        Self::from_vec(smallvec![])
+    }
+}
+impl PartialEq for PatStack {
+    fn eq(&self, other: &Self) -> bool {
+        self.pats == other.pats
+    }
+}
+impl FromIterator<PatId> for PatStack {
+    fn from_iter<T>(iter: T) -> Self
+    where
+        T: IntoIterator<Item = PatId>,
+    {
+        Self::from_vec(iter.into_iter().collect())
+    }
+}
+#[derive(Clone)]
+pub(super) struct Matrix {
+    patterns: Vec<PatStack>,
+}
+impl Matrix {
+    fn empty() -> Self {
+        Matrix { patterns: vec![] }
+    }
+    /// Number of columns of this matrix. `None` is the matrix is empty.
+    pub(super) fn column_count(&self) -> Option<usize> {
+        self.patterns.get(0).map(|r| r.len())
+    }
+    /// Pushes a new row to the matrix. If the row starts with an or-pattern, this recursively
+    /// expands it.
+    fn push(&mut self, row: PatStack, cx: &MatchCheckCtx<'_>) {
+        if !row.is_empty() && row.head().is_or_pat(cx) {
+            for row in row.expand_or_pat(cx) {
+                self.patterns.push(row);
+            }
+        } else {
+            self.patterns.push(row);
+        }
+    }
+    /// Iterate over the first component of each row
+    fn heads(&self) -> impl Iterator<Item = PatId> + '_ {
+        self.patterns.iter().map(|r| r.head())
+    }
+    /// Iterate over the first constructor of each row.
+    fn head_ctors<'a>(
+        &'a self,
+        cx: &'a MatchCheckCtx<'_>,
+    ) -> impl Iterator<Item = &'a Constructor> + Clone {
+        self.patterns.iter().map(move |r| r.head_ctor(cx))
+    }
+    /// This computes `S(constructor, self)`. See top of the file for explanations.
+    fn specialize_constructor(
+        &self,
+        pcx: &PatCtxt<'_>,
+        ctor: &Constructor,
+        ctor_wild_subpatterns: &Fields,
+    ) -> Matrix {
+        let rows = self
+            .patterns
+            .iter()
+            .filter(|r| ctor.is_covered_by(pcx, r.head_ctor(pcx.cx)))
+            .map(|r| r.pop_head_constructor(ctor_wild_subpatterns, pcx.cx));
+        Matrix::from_iter(rows, pcx.cx)
+    }
+    fn from_iter(rows: impl IntoIterator<Item = PatStack>, cx: &MatchCheckCtx<'_>) -> Matrix {
+        let mut matrix = Matrix::empty();
+        for x in rows {
+            // Using `push` ensures we correctly expand or-patterns.
+            matrix.push(x, cx);
+        }
+        matrix
+    }
+}
+#[derive(Debug, Clone)]
+enum SubPatSet {
+    /// The empty set. This means the pattern is unreachable.
+    Empty,
+    /// The set containing the full pattern.
+    Full,
+    /// If the pattern is a pattern with a constructor or a pattern-stack, we store a set for each
+    /// of its subpatterns. Missing entries in the map are implicitly full, because that's the
+    /// common case.
+    Seq { subpats: FxHashMap<usize, SubPatSet> },
+    /// If the pattern is an or-pattern, we store a set for each of its alternatives. Missing
+    /// entries in the map are implicitly empty. Note: we always flatten nested or-patterns.
+    Alt {
+        subpats: FxHashMap<usize, SubPatSet>,
+        /// Counts the total number of alternatives in the pattern
+        alt_count: usize,
+        /// We keep the pattern around to retrieve spans.
+        pat: PatId,
+    },
+}
+impl SubPatSet {
+    fn full() -> Self {
+        SubPatSet::Full
+    }
+    fn empty() -> Self {
+        SubPatSet::Empty
+    }
+    fn is_empty(&self) -> bool {
+        match self {
+            SubPatSet::Empty => true,
+            SubPatSet::Full => false,
+            // If any subpattern in a sequence is unreachable, the whole pattern is unreachable.
+            SubPatSet::Seq { subpats } => subpats.values().any(|set| set.is_empty()),
+            // An or-pattern is reachable if any of its alternatives is.
+            SubPatSet::Alt { subpats, .. } => subpats.values().all(|set| set.is_empty()),
+        }
+    }
+    fn is_full(&self) -> bool {
+        match self {
+            SubPatSet::Empty => false,
+            SubPatSet::Full => true,
+            // The whole pattern is reachable only when all its alternatives are.
+            SubPatSet::Seq { subpats } => subpats.values().all(|sub_set| sub_set.is_full()),
+            // The whole or-pattern is reachable only when all its alternatives are.
+            SubPatSet::Alt { subpats, alt_count, .. } => {
+                subpats.len() == *alt_count && subpats.values().all(|set| set.is_full())
+            }
+        }
+    }
+    /// Union `self` with `other`, mutating `self`.
+    fn union(&mut self, other: Self) {
+        use SubPatSet::*;
+        // Union with full stays full; union with empty changes nothing.
+        if self.is_full() || other.is_empty() {
+            return;
+        } else if self.is_empty() {
+            *self = other;
+            return;
+        } else if other.is_full() {
+            *self = Full;
+            return;
+        }
+        match (&mut *self, other) {
+            (Seq { .. }, Seq { .. }) => {
+                todo!()
+            }
+            (Alt { .. }, Alt { .. }) => {
+                todo!()
+            }
+            _ => panic!("bug"),
+        }
+    }
+    /// Returns a list of the spans of the unreachable subpatterns. If `self` is empty (i.e. the
+    /// whole pattern is unreachable) we return `None`.
+    fn list_unreachable_spans(&self) -> Option<Vec<()>> {
+        if self.is_empty() {
+            return None;
+        }
+        if self.is_full() {
+            // No subpatterns are unreachable.
+            return Some(Vec::new());
+        }
+        todo!()
+    }
+    /// When `self` refers to a patstack that was obtained from specialization, after running
+    /// `unspecialize` it will refer to the original patstack before specialization.
+    fn unspecialize(self, arity: usize) -> Self {
+        use SubPatSet::*;
+        match self {
+            Full => Full,
+            Empty => Empty,
+            Seq { subpats } => {
+                todo!()
+            }
+            Alt { .. } => panic!("bug"),
+        }
+    }
+    /// When `self` refers to a patstack that was obtained from splitting an or-pattern, after
+    /// running `unspecialize` it will refer to the original patstack before splitting.
+    ///
+    /// For example:
+    /// ```
+    /// match Some(true) {
+    ///     Some(true) => {}
+    ///     None | Some(true | false) => {}
+    /// }
+    /// ```
+    /// Here `None` would return the full set and `Some(true | false)` would return the set
+    /// containing `false`. After `unsplit_or_pat`, we want the set to contain `None` and `false`.
+    /// This is what this function does.
+    fn unsplit_or_pat(mut self, alt_id: usize, alt_count: usize, pat: PatId) -> Self {
+        todo!()
+    }
+}
+/// This carries the results of computing usefulness, as described at the top of the file. When
+/// checking usefulness of a match branch, we use the `NoWitnesses` variant, which also keeps track
+/// of potential unreachable sub-patterns (in the presence of or-patterns). When checking
+/// exhaustiveness of a whole match, we use the `WithWitnesses` variant, which carries a list of
+/// witnesses of non-exhaustiveness when there are any.
+/// Which variant to use is dictated by `WitnessPreference`.
+#[derive(Clone, Debug)]
+enum Usefulness {
+    /// Carries a set of subpatterns that have been found to be reachable. If empty, this indicates
+    /// the whole pattern is unreachable. If not, this indicates that the pattern is reachable but
+    /// that some sub-patterns may be unreachable (due to or-patterns). In the absence of
+    /// or-patterns this will always be either `Empty` (the whole pattern is unreachable) or `Full`
+    /// (the whole pattern is reachable).
+    NoWitnesses(SubPatSet),
+    /// Carries a list of witnesses of non-exhaustiveness. If empty, indicates that the whole
+    /// pattern is unreachable.
+    WithWitnesses(Vec<Witness>),
+}
+impl Usefulness {
+    fn new_useful(preference: WitnessPreference) -> Self {
+        match preference {
+            ConstructWitness => WithWitnesses(vec![Witness(vec![])]),
+            LeaveOutWitness => NoWitnesses(SubPatSet::full()),
+        }
+    }
+    fn new_not_useful(preference: WitnessPreference) -> Self {
+        match preference {
+            ConstructWitness => WithWitnesses(vec![]),
+            LeaveOutWitness => NoWitnesses(SubPatSet::empty()),
+        }
+    }
+    /// Combine usefulnesses from two branches. This is an associative operation.
+    fn extend(&mut self, other: Self) {
+        match (&mut *self, other) {
+            (WithWitnesses(_), WithWitnesses(o)) if o.is_empty() => {}
+            (WithWitnesses(s), WithWitnesses(o)) if s.is_empty() => *self = WithWitnesses(o),
+            (WithWitnesses(s), WithWitnesses(o)) => s.extend(o),
+            (NoWitnesses(s), NoWitnesses(o)) => s.union(o),
+            _ => unreachable!(),
+        }
+    }
+    /// When trying several branches and each returns a `Usefulness`, we need to combine the
+    /// results together.
+    fn merge(pref: WitnessPreference, usefulnesses: impl Iterator<Item = Self>) -> Self {
+        let mut ret = Self::new_not_useful(pref);
+        for u in usefulnesses {
+            ret.extend(u);
+            if let NoWitnesses(subpats) = &ret {
+                if subpats.is_full() {
+                    // Once we reach the full set, more unions won't change the result.
+                    return ret;
+                }
+            }
+        }
+        ret
+    }
+    /// After calculating the usefulness for a branch of an or-pattern, call this to make this
+    /// usefulness mergeable with those from the other branches.
+    fn unsplit_or_pat(self, alt_id: usize, alt_count: usize, pat: PatId) -> Self {
+        match self {
+            NoWitnesses(subpats) => NoWitnesses(subpats.unsplit_or_pat(alt_id, alt_count, pat)),
+            WithWitnesses(_) => panic!("bug"),
+        }
+    }
+    /// After calculating usefulness after a specialization, call this to recontruct a usefulness
+    /// that makes sense for the matrix pre-specialization. This new usefulness can then be merged
+    /// with the results of specializing with the other constructors.
+    fn apply_constructor(
+        self,
+        pcx: &PatCtxt<'_>,
+        matrix: &Matrix,
+        ctor: &Constructor,
+        ctor_wild_subpatterns: &Fields,
+    ) -> Self {
+        match self {
+            WithWitnesses(witnesses) if witnesses.is_empty() => WithWitnesses(witnesses),
+            WithWitnesses(w) => {
+                let new_witnesses = if matches!(ctor, Constructor::Missing) {
+                    let mut split_wildcard = SplitWildcard::new(pcx);
+                    split_wildcard.split(pcx, matrix.head_ctors(pcx.cx));
+                } else {
+                    todo!("Usefulness::apply_constructor({:?})", ctor)
+                };
+                todo!("Usefulness::apply_constructor({:?})", ctor)
+            }
+            NoWitnesses(subpats) => NoWitnesses(subpats.unspecialize(ctor_wild_subpatterns.len())),
+        }
+    }
+}
+#[derive(Copy, Clone, Debug)]
+enum WitnessPreference {
+    ConstructWitness,
+    LeaveOutWitness,
+}
+#[derive(Clone, Debug)]
+pub(crate) struct Witness(Vec<Pat>);
+impl Witness {
+    /// Asserts that the witness contains a single pattern, and returns it.
+    fn single_pattern(self) -> Pat {
+        assert_eq!(self.0.len(), 1);
+        self.0.into_iter().next().unwrap()
+    }
+    /// Constructs a partial witness for a pattern given a list of
+    /// patterns expanded by the specialization step.
+    ///
+    /// When a pattern P is discovered to be useful, this function is used bottom-up
+    /// to reconstruct a complete witness, e.g., a pattern P' that covers a subset
+    /// of values, V, where each value in that set is not covered by any previously
+    /// used patterns and is covered by the pattern P'. Examples:
+    ///
+    /// left_ty: tuple of 3 elements
+    /// pats: [10, 20, _]           => (10, 20, _)
+    ///
+    /// left_ty: struct X { a: (bool, &'static str), b: usize}
+    /// pats: [(false, "foo"), 42]  => X { a: (false, "foo"), b: 42 }
+    fn apply_constructor(
+        mut self,
+        pcx: &PatCtxt<'_>,
+        ctor: &Constructor,
+        ctor_wild_subpatterns: &Fields,
+    ) -> Self {
+        let pat = {
+            let len = self.0.len();
+            let arity = ctor_wild_subpatterns.len();
+            let pats = self.0.drain((len - arity)..).rev();
+            ctor_wild_subpatterns.replace_fields(pcx.cx, pats).apply(pcx, ctor)
+        };
+        self.0.push(pat);
+        self
+    }
+}
+/// Algorithm from <http://moscova.inria.fr/~maranget/papers/warn/index.html>.
+/// The algorithm from the paper has been modified to correctly handle empty
+/// types. The changes are:
+///   (0) We don't exit early if the pattern matrix has zero rows. We just
+///       continue to recurse over columns.
+///   (1) all_constructors will only return constructors that are statically
+///       possible. E.g., it will only return `Ok` for `Result<T, !>`.
+///
+/// This finds whether a (row) vector `v` of patterns is 'useful' in relation
+/// to a set of such vectors `m` - this is defined as there being a set of
+/// inputs that will match `v` but not any of the sets in `m`.
+///
+/// All the patterns at each column of the `matrix ++ v` matrix must have the same type.
+///
+/// This is used both for reachability checking (if a pattern isn't useful in
+/// relation to preceding patterns, it is not reachable) and exhaustiveness
+/// checking (if a wildcard pattern is useful in relation to a matrix, the
+/// matrix isn't exhaustive).
+///
+/// `is_under_guard` is used to inform if the pattern has a guard. If it
+/// has one it must not be inserted into the matrix. This shouldn't be
+/// relied on for soundness.
+fn is_useful(
+    cx: &MatchCheckCtx<'_>,
+    matrix: &Matrix,
+    v: &PatStack,
+    witness_preference: WitnessPreference,
+    is_under_guard: bool,
+    is_top_level: bool,
+) -> Usefulness {
+    let Matrix { patterns: rows, .. } = matrix;
+    // The base case. We are pattern-matching on () and the return value is
+    // based on whether our matrix has a row or not.
+    // NOTE: This could potentially be optimized by checking rows.is_empty()
+    // first and then, if v is non-empty, the return value is based on whether
+    // the type of the tuple we're checking is inhabited or not.
+    if v.is_empty() {
+        let ret = if rows.is_empty() {
+            Usefulness::new_useful(witness_preference)
+        } else {
+            Usefulness::new_not_useful(witness_preference)
+        };
+        return ret;
+    }
+    assert!(rows.iter().all(|r| r.len() == v.len()));
+    // FIXME(Nadrieril): Hack to work around type normalization issues (see rust-lang/rust#72476).
+    // TODO(iDawer): ty.as_reference()
+    let ty = matrix.heads().next().map_or(cx.type_of(v.head()), |r| cx.type_of(r));
+    let pcx = PatCtxt { cx, ty, is_top_level };
+    // If the first pattern is an or-pattern, expand it.
+    let ret = if v.head().is_or_pat(cx) {
+        //expanding or-pattern
+        let v_head = v.head();
+        let vs: Vec<_> = v.expand_or_pat(cx).collect();
+        let alt_count = vs.len();
+        // We try each or-pattern branch in turn.
+        let mut matrix = matrix.clone();
+        let usefulnesses = vs.into_iter().enumerate().map(|(i, v)| {
+            let usefulness = is_useful(cx, &matrix, &v, witness_preference, is_under_guard, false);
+            // If pattern has a guard don't add it to the matrix.
+            if !is_under_guard {
+                // We push the already-seen patterns into the matrix in order to detect redundant
+                // branches like `Some(_) | Some(0)`.
+                matrix.push(v, cx);
+            }
+            usefulness.unsplit_or_pat(i, alt_count, v_head)
+        });
+        Usefulness::merge(witness_preference, usefulnesses)
+    } else {
+        let v_ctor = v.head_ctor(cx);
+        // if let Constructor::IntRange(ctor_range) = v_ctor {
+        //     // Lint on likely incorrect range patterns (#63987)
+        //     ctor_range.lint_overlapping_range_endpoints(
+        //         pcx,
+        //         matrix.head_ctors_and_spans(cx),
+        //         matrix.column_count().unwrap_or(0),
+        //         hir_id,
+        //     )
+        // }
+        // We split the head constructor of `v`.
+        let split_ctors = v_ctor.split(&pcx, matrix.head_ctors(cx));
+        // For each constructor, we compute whether there's a value that starts with it that would
+        // witness the usefulness of `v`.
+        let start_matrix = matrix;
+        let usefulnesses = split_ctors.into_iter().map(|ctor| {
+            // debug!("specialize({:?})", ctor);
+            // We cache the result of `Fields::wildcards` because it is used a lot.
+            let ctor_wild_subpatterns = Fields::wildcards(&pcx, &ctor);
+            let spec_matrix =
+                start_matrix.specialize_constructor(&pcx, &ctor, &ctor_wild_subpatterns);
+            let v = v.pop_head_constructor(&ctor_wild_subpatterns, cx);
+            let usefulness =
+                is_useful(cx, &spec_matrix, &v, witness_preference, is_under_guard, false);
+            usefulness.apply_constructor(&pcx, start_matrix, &ctor, &ctor_wild_subpatterns)
+        });
+        Usefulness::merge(witness_preference, usefulnesses)
+    };
+    ret
+}
+/// The arm of a match expression.
+#[derive(Clone, Copy)]
+pub(crate) struct MatchArm {
+    pub(crate) pat: PatId,
+    pub(crate) has_guard: bool,
+}
+/// Indicates whether or not a given arm is reachable.
+#[derive(Clone, Debug)]
+pub(crate) enum Reachability {
+    /// The arm is reachable. This additionally carries a set of or-pattern branches that have been
+    /// found to be unreachable despite the overall arm being reachable. Used only in the presence
+    /// of or-patterns, otherwise it stays empty.
+    Reachable(Vec<()>),
+    /// The arm is unreachable.
+    Unreachable,
+}
+/// The output of checking a match for exhaustiveness and arm reachability.
+pub(crate) struct UsefulnessReport {
+    /// For each arm of the input, whether that arm is reachable after the arms above it.
+    pub(crate) arm_usefulness: Vec<(MatchArm, Reachability)>,
+    /// If the match is exhaustive, this is empty. If not, this contains witnesses for the lack of
+    /// exhaustiveness.
+    pub(crate) non_exhaustiveness_witnesses: Vec<Pat>,
+}
+pub(crate) fn compute_match_usefulness(
+    cx: &MatchCheckCtx<'_>,
+    arms: &[MatchArm],
+) -> UsefulnessReport {
+    let mut matrix = Matrix::empty();
+    let arm_usefulness: Vec<_> = arms
+        .iter()
+        .copied()
+        .map(|arm| {
+            let v = PatStack::from_pattern(arm.pat);
+            let usefulness = is_useful(cx, &matrix, &v, LeaveOutWitness, arm.has_guard, true);
+            if !arm.has_guard {
+                matrix.push(v, cx);
+            }
+            let reachability = match usefulness {
+                NoWitnesses(subpats) if subpats.is_empty() => Reachability::Unreachable,
+                NoWitnesses(subpats) => {
+                    Reachability::Reachable(subpats.list_unreachable_spans().unwrap())
+                }
+                WithWitnesses(..) => panic!("bug"),
+            };
+            (arm, reachability)
+        })
+        .collect();
+    let wild_pattern = cx.pattern_arena.borrow_mut().alloc(Pat::Wild, &cx.infer[cx.match_expr]);
+    let v = PatStack::from_pattern(wild_pattern);
+    let usefulness = is_useful(cx, &matrix, &v, LeaveOutWitness, false, true);
+    let non_exhaustiveness_witnesses = match usefulness {
+        // TODO: ConstructWitness
+        // WithWitnesses(pats) => pats.into_iter().map(Witness::single_pattern).collect(),
+        // NoWitnesses(_) => panic!("bug"),
+        NoWitnesses(subpats) if subpats.is_empty() => Vec::new(),
+        NoWitnesses(subpats) => vec![Pat::Wild],
+        WithWitnesses(..) => panic!("bug"),
+    };
+    UsefulnessReport { arm_usefulness, non_exhaustiveness_witnesses }
+}
+pub(crate) struct PatternArena {
+    arena: Arena<Pat>,
+    /// Types of expanded patterns.
+    type_of_epat: FxHashMap<PatId, Ty>,
+}
+impl PatternArena {
+    pub(crate) fn clone_from(pats: &Arena<Pat>) -> RefCell<Self> {
+        PatternArena { arena: pats.clone(), type_of_epat: Default::default() }.into()
+    }
+    fn alloc(&mut self, pat: Pat, ty: &Ty) -> PatId {
+        let id = self.arena.alloc(pat);
+        self.type_of_epat.insert(id, ty.clone());
+        id
+    }
+}
+impl Index<PatId> for PatternArena {
+    type Output = Pat;
+    fn index(&self, pat: PatId) -> &Pat {
+        &self.arena[pat]
+    }
+}
+mod helper {
+    use hir_def::expr::{Pat, PatId};
+    use super::MatchCheckCtx;
+    pub(super) trait PatIdExt: Sized {
+        fn is_wildcard(self, cx: &MatchCheckCtx<'_>) -> bool;
+        fn is_or_pat(self, cx: &MatchCheckCtx<'_>) -> bool;
+        fn expand_or_pat(self, cx: &MatchCheckCtx<'_>) -> Vec<Self>;
+    }
+    // Copy-pasted from rust/compiler/rustc_data_structures/src/captures.rs
+    /// "Signaling" trait used in impl trait to tag lifetimes that you may
+    /// need to capture but don't really need for other reasons.
+    /// Basically a workaround; see [this comment] for details.
+    ///
+    /// [this comment]: https://github.com/rust-lang/rust/issues/34511#issuecomment-373423999
+    // FIXME(eddyb) false positive, the lifetime parameter is "phantom" but needed.
+    #[allow(unused_lifetimes)]
+    pub trait Captures<'a> {}
+    impl<'a, T: ?Sized> Captures<'a> for T {}
+}
+#[test]
+fn it_works() {}