5 files changed, 387 insertions, 164 deletions

diff --git a/crates/hir_ty/src/diagnostics/expr.rs b/crates/hir_ty/src/diagnostics/expr.rs
index a62f0fa4f..8f141a308 100644
--- a/crates/hir_ty/src/diagnostics/expr.rs
+++ b/crates/hir_ty/src/diagnostics/expr.rs
@@ -2,7 +2,7 @@
 //! through the body using inference results: mismatched arg counts, missing
 //! fields, etc.
 
-use std::sync::Arc;
+use std::{cell::RefCell, sync::Arc};
 
 use hir_def::{expr::Statement, path::path, resolver::HasResolver, AssocItemId, DefWithBodyId};
 use hir_expand::name;
@@ -26,7 +26,13 @@ pub(crate) use hir_def::{
     LocalFieldId, VariantId,
 };
 
-use super::ReplaceFilterMapNextWithFindMap;
+use super::{
+    pattern::{
+        self,
+        usefulness::{expand_pattern, PatternArena},
+    },
+    ReplaceFilterMapNextWithFindMap,
+};
 
 pub(super) struct ExprValidator<'a, 'b: 'a> {
     owner: DefWithBodyId,
@@ -380,7 +386,16 @@ impl<'a, 'b> ExprValidator<'a, 'b> {
         };
         // eprintln!("ExprValidator::validate_match2({:?})", _match_expr_ty.kind(&Interner));
 
-        let pattern_arena = usefulness::PatternArena::clone_from(&body.pats);
+        let pattern_arena = RefCell::new(PatternArena::new());
+
+        let m_arms: Vec<_> = arms
+            .iter()
+            .map(|arm| usefulness::MatchArm {
+                pat: self.lower_pattern(arm.pat, &mut pattern_arena.borrow_mut(), db, &body),
+                has_guard: arm.guard.is_some(),
+            })
+            .collect();
+
         let cx = usefulness::MatchCheckCtx {
             module: self.owner.module(db.upcast()),
             match_expr,
@@ -389,12 +404,6 @@ impl<'a, 'b> ExprValidator<'a, 'b> {
             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
@@ -427,6 +436,18 @@ impl<'a, 'b> ExprValidator<'a, 'b> {
         }
     }
 
+    fn lower_pattern(
+        &self,
+        pat: PatId,
+        pattern_arena: &mut PatternArena,
+        db: &dyn HirDatabase,
+        body: &Body,
+    ) -> pattern::PatId {
+        let mut patcx = pattern::PatCtxt::new(db, &self.infer, body);
+        let pattern = patcx.lower_pattern(pat);
+        pattern_arena.alloc(expand_pattern(pattern))
+    }
+
     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
index 044506d66..6646826b3 100644
--- a/crates/hir_ty/src/diagnostics/pattern.rs
+++ b/crates/hir_ty/src/diagnostics/pattern.rs
@@ -2,8 +2,199 @@
 #![allow(unused)] // todo remove
 
 mod deconstruct_pat;
+// TODO: find a better place for this?
+mod pat_util;
 pub mod usefulness;
 
+use hir_def::{body::Body, EnumVariantId, LocalFieldId, VariantId};
+use la_arena::Idx;
+
+use crate::{db::HirDatabase, AdtId, InferenceResult, Interner, Substitution, Ty, TyKind};
+
+use self::{deconstruct_pat::ToDo, pat_util::EnumerateAndAdjustIterator};
+
+pub type PatId = Idx<Pat>;
+
+#[derive(Clone, Debug)]
+pub(crate) enum PatternError {
+    Unimplemented,
+}
+
+#[derive(Clone, Debug, PartialEq)]
+pub struct FieldPat {
+    pub field: LocalFieldId,
+    pub pattern: Pat,
+}
+
+#[derive(Clone, Debug, PartialEq)]
+pub struct Pat {
+    pub ty: Ty,
+    pub kind: Box<PatKind>,
+}
+
+impl Pat {
+    pub(crate) fn wildcard_from_ty(ty: &Ty) -> Self {
+        Pat { ty: ty.clone(), kind: Box::new(PatKind::Wild) }
+    }
+}
+
+#[derive(Clone, Debug, PartialEq)]
+pub enum PatKind {
+    Wild,
+
+    /// `x`, `ref x`, `x @ P`, etc.
+    Binding {
+        subpattern: Option<Pat>,
+        // todo: ToDo,
+    },
+
+    /// `Foo(...)` or `Foo{...}` or `Foo`, where `Foo` is a variant name from an ADT with
+    /// multiple variants.
+    Variant {
+        substs: Substitution,
+        enum_variant: EnumVariantId,
+        subpatterns: Vec<FieldPat>,
+    },
+
+    /// `(...)`, `Foo(...)`, `Foo{...}`, or `Foo`, where `Foo` is a variant name from an ADT with
+    /// a single variant.
+    Leaf {
+        subpatterns: Vec<FieldPat>,
+    },
+
+    /// `box P`, `&P`, `&mut P`, etc.
+    Deref {
+        subpattern: Pat,
+    },
+
+    /// An or-pattern, e.g. `p | q`.
+    /// Invariant: `pats.len() >= 2`.
+    Or {
+        pats: Vec<Pat>,
+    },
+}
+
+pub(crate) struct PatCtxt<'a> {
+    db: &'a dyn HirDatabase,
+    infer: &'a InferenceResult,
+    body: &'a Body,
+    pub(crate) errors: Vec<PatternError>,
+}
+
+impl<'a> PatCtxt<'a> {
+    pub(crate) fn new(db: &'a dyn HirDatabase, infer: &'a InferenceResult, body: &'a Body) -> Self {
+        Self { db, infer, body, errors: Vec::new() }
+    }
+
+    pub(crate) fn lower_pattern(&mut self, pat: hir_def::expr::PatId) -> Pat {
+        // TODO: pattern adjustments (implicit dereference)
+        // More info https://github.com/rust-lang/rust/issues/42640#issuecomment-313535089
+        let unadjusted_pat = self.lower_pattern_unadjusted(pat);
+        unadjusted_pat
+    }
+
+    fn lower_pattern_unadjusted(&mut self, pat: hir_def::expr::PatId) -> Pat {
+        let ty = &self.infer[pat];
+
+        let kind = match self.body[pat] {
+            hir_def::expr::Pat::Wild => PatKind::Wild,
+
+            hir_def::expr::Pat::Tuple { ref args, ellipsis } => {
+                let arity = match *ty.kind(&Interner) {
+                    TyKind::Tuple(arity, _) => arity,
+                    _ => panic!("unexpected type for tuple pattern: {:?}", ty),
+                };
+                let subpatterns = self.lower_tuple_subpats(args, arity, ellipsis);
+                PatKind::Leaf { subpatterns }
+            }
+
+            hir_def::expr::Pat::TupleStruct { ref args, ellipsis, .. } => {
+                let variant_data = match self.infer.variant_resolution_for_pat(pat) {
+                    Some(variant_id) => variant_id.variant_data(self.db.upcast()),
+                    None => panic!("tuple struct pattern not applied to an ADT {:?}", ty),
+                };
+                let subpatterns =
+                    self.lower_tuple_subpats(args, variant_data.fields().len(), ellipsis);
+                self.lower_variant_or_leaf(pat, ty, subpatterns)
+            }
+
+            hir_def::expr::Pat::Record { ref args, .. } => {
+                let variant_data = match self.infer.variant_resolution_for_pat(pat) {
+                    Some(variant_id) => variant_id.variant_data(self.db.upcast()),
+                    None => panic!("record pattern not applied to an ADT {:?}", ty),
+                };
+                let subpatterns = args
+                    .iter()
+                    .map(|field| FieldPat {
+                        // XXX(iDawer): field lookup is inefficient
+                        field: variant_data.field(&field.name).unwrap_or_else(|| todo!()),
+                        pattern: self.lower_pattern(field.pat),
+                    })
+                    .collect();
+                self.lower_variant_or_leaf(pat, ty, subpatterns)
+            }
+
+            hir_def::expr::Pat::Or(ref pats) => PatKind::Or { pats: self.lower_patterns(pats) },
+
+            _ => {
+                self.errors.push(PatternError::Unimplemented);
+                PatKind::Wild
+            }
+        };
+
+        Pat { ty: ty.clone(), kind: Box::new(kind) }
+    }
+
+    fn lower_tuple_subpats(
+        &mut self,
+        pats: &[hir_def::expr::PatId],
+        expected_len: usize,
+        ellipsis: Option<usize>,
+    ) -> Vec<FieldPat> {
+        pats.iter()
+            .enumerate_and_adjust(expected_len, ellipsis)
+            .map(|(i, &subpattern)| FieldPat {
+                field: LocalFieldId::from_raw((i as u32).into()),
+                pattern: self.lower_pattern(subpattern),
+            })
+            .collect()
+    }
+
+    fn lower_patterns(&mut self, pats: &[hir_def::expr::PatId]) -> Vec<Pat> {
+        pats.iter().map(|&p| self.lower_pattern(p)).collect()
+    }
+
+    fn lower_variant_or_leaf(
+        &mut self,
+        pat: hir_def::expr::PatId,
+        ty: &Ty,
+        subpatterns: Vec<FieldPat>,
+    ) -> PatKind {
+        let kind = match self.infer.variant_resolution_for_pat(pat) {
+            Some(variant_id) => {
+                if let VariantId::EnumVariantId(enum_variant) = variant_id {
+                    let substs = match ty.kind(&Interner) {
+                        TyKind::Adt(_, substs) | TyKind::FnDef(_, substs) => substs.clone(),
+                        TyKind::Error => {
+                            return PatKind::Wild;
+                        }
+                        _ => panic!("inappropriate type for def: {:?}", ty),
+                    };
+                    PatKind::Variant { substs, enum_variant, subpatterns }
+                } else {
+                    PatKind::Leaf { subpatterns }
+                }
+            }
+            None => {
+                self.errors.push(PatternError::Unimplemented);
+                PatKind::Wild
+            }
+        };
+        // TODO: do we need PatKind::AscribeUserType ?
+        kind
+    }
+}
+
 #[cfg(test)]
 mod tests {
     use crate::diagnostics::tests::check_diagnostics;
diff --git a/crates/hir_ty/src/diagnostics/pattern/deconstruct_pat.rs b/crates/hir_ty/src/diagnostics/pattern/deconstruct_pat.rs
index 248a379b3..479e0dc73 100644
--- a/crates/hir_ty/src/diagnostics/pattern/deconstruct_pat.rs
+++ b/crates/hir_ty/src/diagnostics/pattern/deconstruct_pat.rs
@@ -5,18 +5,18 @@ use std::{
 };
 
 use hir_def::{
-    expr::{Expr, Literal, Pat, PatId, RecordFieldPat},
-    find_path::find_path,
-    item_scope::ItemInNs,
-    path::Path,
+    expr::{Expr, Literal, RecordFieldPat},
     type_ref::Mutability,
-    AttrDefId, EnumVariantId, HasModule, VariantId,
+    AttrDefId, EnumVariantId, HasModule, LocalFieldId, VariantId,
 };
 use smallvec::{smallvec, SmallVec};
 
 use crate::{AdtId, Interner, Scalar, Ty, TyExt, TyKind};
 
-use super::usefulness::{MatchCheckCtx, PatCtxt};
+use super::{
+    usefulness::{MatchCheckCtx, PatCtxt},
+    FieldPat, Pat, PatId, PatKind,
+};
 
 use self::Constructor::*;
 
@@ -271,29 +271,18 @@ impl Constructor {
     /// Determines the constructor that the given pattern can be specialized to.
     pub(super) fn from_pat(cx: &MatchCheckCtx<'_>, pat: PatId) -> Self {
         let ty = cx.type_of(pat);
-        match &cx.pattern_arena.borrow()[pat] {
-            Pat::Bind { .. } | Pat::Wild => Wildcard,
-            Pat::Tuple { .. } | Pat::Ref { .. } | Pat::Box { .. } => Single,
-            Pat::Record { .. } | Pat::Path(_) | Pat::TupleStruct { .. } => {
-                // TODO: path to const
-                let variant_id =
-                    cx.infer.variant_resolution_for_pat(pat).unwrap_or_else(|| todo!());
-                match variant_id {
-                    VariantId::EnumVariantId(id) => Variant(id),
-                    VariantId::StructId(_) | VariantId::UnionId(_) => Single,
-                }
-            }
-            &Pat::Lit(expr_id) => match cx.body[expr_id] {
-                Expr::Literal(Literal::Bool(val)) => IntRange(IntRange::from_bool(val)),
-                _ => todo!(),
-            },
-
-            Pat::Or(..) => panic!("bug: Or-pattern should have been expanded earlier on."),
-            Pat::Missing => todo!("Fail gracefully when there is an error in a pattern"),
+        match cx.pattern_arena.borrow()[pat].kind.as_ref() {
+            PatKind::Binding { .. } | PatKind::Wild => Wildcard,
+            PatKind::Leaf { .. } | PatKind::Deref { .. } => Single,
+            &PatKind::Variant { enum_variant, .. } => Variant(enum_variant),
+
+            //Todo
+            // &Pat::Lit(expr_id) => match cx.body[expr_id] {
+            //     Expr::Literal(Literal::Bool(val)) => IntRange(IntRange::from_bool(val)),
+            //     _ => todo!(),
+            // },
+            PatKind::Or { .. } => panic!("bug: Or-pattern should have been expanded earlier on."),
             pat => todo!("Constructor::from_pat {:?}", pat),
-            // Pat::Range { start, end } => {}
-            // Pat::Slice { prefix, slice, suffix } => {}
-            // Pat::ConstBlock(_) => {}
         }
     }
 
@@ -620,15 +609,15 @@ impl Fields {
         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();
+        let wilds = tys.into_iter().map(Pat::wildcard_from_ty);
+        let pats = wilds.map(|pat| cx.alloc_pat(pat)).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 wildcard_from_ty = |ty| cx.alloc_pat(Pat::wildcard_from_ty(ty));
 
         let ret = match constructor {
             Single | Variant(_) => match ty.kind(&Interner) {
@@ -696,64 +685,60 @@ impl Fields {
     /// 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);
-        // TODO witnesses are not yet used
-        const TODO: Pat = Pat::Wild;
+        let mut subpatterns =
+            subpatterns_and_indices.iter().map(|&(_, p)| pcx.cx.pattern_arena.borrow()[p].clone());
+        // FIXME(iDawer) witnesses are not yet used
+        const UNIMPLEMENTED: PatKind = PatKind::Wild;
 
-        match ctor {
+        let pat = match ctor {
             Single | Variant(_) => match pcx.ty.kind(&Interner) {
                 TyKind::Adt(..) | TyKind::Tuple(..) => {
                     // We want the real indices here.
-                    // TODO indices and ellipsis interaction, tests
-                    let subpatterns = subpatterns_and_indices.iter().map(|&(_, pat)| pat).collect();
+                    let subpatterns = subpatterns_and_indices
+                        .iter()
+                        .map(|&(field, pat)| FieldPat {
+                            field,
+                            pattern: pcx.cx.pattern_arena.borrow()[pat].clone(),
+                        })
+                        .collect();
 
                     if let Some((adt, substs)) = pcx.ty.as_adt() {
-                        let item = ItemInNs::Types(adt.into());
-                        let path = find_path(pcx.cx.db.upcast(), item, pcx.cx.module)
-                            .map(|mpath| Path::from_known_path(mpath, Vec::new()).into());
-                        match adt {
-                            hir_def::AdtId::EnumId(id) => TODO,
-                            hir_def::AdtId::StructId(id) => {
-                                let variant_data = &pcx.cx.db.struct_data(id).variant_data;
-                                let args = subpatterns_and_indices
-                                    .iter()
-                                    .zip(variant_data.fields().iter())
-                                    .map(|(&(_, pat), (_, field_data))| RecordFieldPat {
-                                        name: field_data.name.clone(),
-                                        pat,
-                                    })
-                                    .collect();
-                                Pat::Record { path, args, ellipsis: false }
-                            }
-                            hir_def::AdtId::UnionId(_) => Pat::Wild,
+                        if let hir_def::AdtId::EnumId(_) = adt {
+                            let enum_variant = match ctor {
+                                &Variant(id) => id,
+                                _ => unreachable!(),
+                            };
+                            PatKind::Variant { substs: substs.clone(), enum_variant, subpatterns }
+                        } else {
+                            PatKind::Leaf { subpatterns }
                         }
                     } else {
-                        Pat::Tuple { args: subpatterns, ellipsis: None }
+                        PatKind::Leaf { subpatterns }
                     }
                 }
                 // Note: given the expansion of `&str` patterns done in `expand_pattern`, we should
                 // be careful to reconstruct the correct constant pattern here. However a string
                 // literal pattern will never be reported as a non-exhaustiveness witness, so we
                 // can ignore this issue.
-                TyKind::Ref(..) => {
-                    Pat::Ref { pat: subpatterns.next().unwrap(), mutability: Mutability::Shared }
-                }
+                TyKind::Ref(..) => PatKind::Deref { subpattern: subpatterns.next().unwrap() },
                 TyKind::Slice(..) | TyKind::Array(..) => {
                     panic!("bug: bad slice pattern {:?} {:?}", ctor, pcx.ty)
                 }
-                _ => Pat::Wild,
+                _ => PatKind::Wild,
             },
-            Constructor::Slice(slice) => TODO,
-            Str(_) => TODO,
-            FloatRange(..) => TODO,
-            Constructor::IntRange(_) => TODO,
-            NonExhaustive => Pat::Wild,
-            Wildcard => Pat::Wild,
+            Constructor::Slice(slice) => UNIMPLEMENTED,
+            Str(_) => UNIMPLEMENTED,
+            FloatRange(..) => UNIMPLEMENTED,
+            Constructor::IntRange(_) => UNIMPLEMENTED,
+            NonExhaustive => PatKind::Wild,
+            Wildcard => return Pat::wildcard_from_ty(pcx.ty),
             Opaque => panic!("bug: we should not try to apply an opaque constructor"),
             Missing => {
                 panic!("bug: trying to apply the `Missing` constructor; this should have been done in `apply_constructors`")
             }
-        }
+        };
+
+        Pat { ty: pcx.ty.clone(), kind: Box::new(pat) }
     }
 
     /// Returns the number of patterns. This is the same as the arity of the constructor used to
@@ -765,9 +750,14 @@ impl Fields {
     }
 
     /// Returns the list of patterns along with the corresponding field indices.
-    fn patterns_and_indices(&self) -> SmallVec<[(usize, PatId); 2]> {
+    fn patterns_and_indices(&self) -> SmallVec<[(LocalFieldId, PatId); 2]> {
         match self {
-            Fields::Vec(pats) => pats.iter().copied().enumerate().collect(),
+            Fields::Vec(pats) => pats
+                .iter()
+                .copied()
+                .enumerate()
+                .map(|(i, p)| (LocalFieldId::from_raw((i as u32).into()), p))
+                .collect(),
         }
     }
 
@@ -779,8 +769,13 @@ impl Fields {
 
     /// 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())
+    fn replace_with_fieldpats(
+        &self,
+        new_pats: impl IntoIterator<Item = (LocalFieldId, PatId)>,
+    ) -> Self {
+        self.replace_fields_indexed(
+            new_pats.into_iter().map(|(field, pat)| (u32::from(field.into_raw()) as usize, pat)),
+        )
     }
 
     /// Overrides some of the fields with the provided patterns. This is used when a pattern
@@ -814,10 +809,7 @@ impl Fields {
             let tys: SmallVec<[Ty; 2]> = match self {
                 Fields::Vec(pats) => pats.iter().copied().map(|pat| cx.type_of(pat)).collect(),
             };
-            pats.into_iter()
-                .zip(tys.into_iter())
-                .map(move |(pat, ty)| cx.alloc_pat(pat, &ty))
-                .collect()
+            pats.into_iter().zip(tys.into_iter()).map(move |(pat, ty)| cx.alloc_pat(pat)).collect()
         };
 
         match self {
@@ -845,42 +837,24 @@ impl Fields {
         pat: PatId,
         cx: &MatchCheckCtx<'_>,
     ) -> Self {
-        match &cx.pattern_arena.borrow()[pat] {
-            Pat::Ref { pat: subpattern, .. } | Pat::Box { inner: subpattern } => {
+        // TODO: these alocations are so unfortunate (+1 for switching to references)
+        match cx.pattern_arena.borrow()[pat].kind.as_ref() {
+            PatKind::Deref { subpattern } => {
                 assert_eq!(self.len(), 1);
-                Fields::from_single_pattern(*subpattern)
+                let subpattern = cx.pattern_arena.borrow_mut().alloc(subpattern.clone());
+                Fields::from_single_pattern(subpattern)
             }
-            Pat::Tuple { args, ellipsis } | Pat::TupleStruct { args, 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(args.iter().copied())
-            }
-            Pat::Record { args, ellipsis, .. } => {
-                let variant_id =
-                    cx.infer.variant_resolution_for_pat(pat).unwrap_or_else(|| todo!());
-                let variant_data = variant_id.variant_data(cx.db.upcast());
-
-                let new_pats = args.iter().map(|field_pat| {
-                    // TODO: field lookup is inefficient
-                    let raw =
-                        variant_data.field(&field_pat.name).unwrap_or_else(|| todo!()).into_raw();
-                    let idx = u32::from(raw) as usize;
-                    (idx, field_pat.pat)
+            PatKind::Leaf { subpatterns } | PatKind::Variant { subpatterns, .. } => {
+                let subpatterns = subpatterns.iter().map(|field_pat| {
+                    (
+                        field_pat.field,
+                        cx.pattern_arena.borrow_mut().alloc(field_pat.pattern.clone()),
+                    )
                 });
-                self.replace_fields_indexed(new_pats)
-            }
-            Pat::Slice { .. } => {
-                todo!()
+                self.replace_with_fieldpats(subpatterns)
             }
-            Pat::Missing
-            | Pat::Wild
-            | Pat::Or(_)
-            | Pat::Range { .. }
-            | Pat::Path(_)
-            | Pat::Lit(_)
-            | Pat::Bind { .. }
-            | Pat::ConstBlock(_) => self.clone(),
+
+            PatKind::Wild | PatKind::Binding { .. } | PatKind::Or { .. } => self.clone(),
         }
     }
 }
diff --git a/crates/hir_ty/src/diagnostics/pattern/pat_util.rs b/crates/hir_ty/src/diagnostics/pattern/pat_util.rs
new file mode 100644
index 000000000..f8ad4e7c6
--- /dev/null
+++ b/crates/hir_ty/src/diagnostics/pattern/pat_util.rs
@@ -0,0 +1,52 @@
+use std::iter::{Enumerate, ExactSizeIterator};
+
+pub struct EnumerateAndAdjust<I> {
+    enumerate: Enumerate<I>,
+    gap_pos: usize,
+    gap_len: usize,
+}
+
+impl<I> Iterator for EnumerateAndAdjust<I>
+where
+    I: Iterator,
+{
+    type Item = (usize, <I as Iterator>::Item);
+
+    fn next(&mut self) -> Option<(usize, <I as Iterator>::Item)> {
+        self.enumerate
+            .next()
+            .map(|(i, elem)| (if i < self.gap_pos { i } else { i + self.gap_len }, elem))
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.enumerate.size_hint()
+    }
+}
+
+pub trait EnumerateAndAdjustIterator {
+    fn enumerate_and_adjust(
+        self,
+        expected_len: usize,
+        gap_pos: Option<usize>,
+    ) -> EnumerateAndAdjust<Self>
+    where
+        Self: Sized;
+}
+
+impl<T: ExactSizeIterator> EnumerateAndAdjustIterator for T {
+    fn enumerate_and_adjust(
+        self,
+        expected_len: usize,
+        gap_pos: Option<usize>,
+    ) -> EnumerateAndAdjust<Self>
+    where
+        Self: Sized,
+    {
+        let actual_len = self.len();
+        EnumerateAndAdjust {
+            enumerate: self.enumerate(),
+            gap_pos: gap_pos.unwrap_or(expected_len),
+            gap_len: expected_len - actual_len,
+        }
+    }
+}
diff --git a/crates/hir_ty/src/diagnostics/pattern/usefulness.rs b/crates/hir_ty/src/diagnostics/pattern/usefulness.rs
index 2df87ccea..28b9e71f8 100644
--- a/crates/hir_ty/src/diagnostics/pattern/usefulness.rs
+++ b/crates/hir_ty/src/diagnostics/pattern/usefulness.rs
@@ -3,11 +3,7 @@
 
 use std::{cell::RefCell, iter::FromIterator, ops::Index, sync::Arc};
 
-use hir_def::{
-    body::Body,
-    expr::{ExprId, Pat, PatId},
-    HasModule, ModuleId,
-};
+use hir_def::{body::Body, expr::ExprId, HasModule, ModuleId};
 use la_arena::Arena;
 use once_cell::unsync::OnceCell;
 use rustc_hash::FxHashMap;
@@ -15,7 +11,10 @@ use smallvec::{smallvec, SmallVec};
 
 use crate::{db::HirDatabase, InferenceResult, Ty};
 
-use super::deconstruct_pat::{Constructor, Fields, SplitWildcard};
+use super::{
+    deconstruct_pat::{Constructor, Fields, SplitWildcard},
+    Pat, PatId, PatKind,
+};
 
 use self::{
     helper::{Captures, PatIdExt},
@@ -55,14 +54,13 @@ impl<'a> MatchCheckCtx<'a> {
         false
     }
 
-    pub(super) fn alloc_pat(&self, pat: Pat, ty: &Ty) -> PatId {
-        self.pattern_arena.borrow_mut().alloc(pat, ty)
+    pub(super) fn alloc_pat(&self, pat: Pat) -> PatId {
+        self.pattern_arena.borrow_mut().alloc(pat)
     }
 
     /// 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())
+        self.pattern_arena.borrow()[pat].ty.clone()
     }
 }
 
@@ -76,30 +74,40 @@ pub(super) struct PatCtxt<'a> {
     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)
+pub(crate) fn expand_pattern(pat: Pat) -> Pat {
+    // TODO: LiteralExpander, it is about string literal patterns
+    pat
+}
+
+impl Pat {
+    fn is_wildcard(&self) -> bool {
+        matches!(*self.kind, PatKind::Binding { subpattern: None, .. } | PatKind::Wild)
     }
+}
 
+impl PatIdExt for PatId {
     fn is_or_pat(self, cx: &MatchCheckCtx<'_>) -> bool {
-        matches!(cx.pattern_arena.borrow()[self], Pat::Or(..))
+        matches!(*cx.pattern_arena.borrow()[self].kind, PatKind::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);
-                }
+        fn expand(pat: PatId, vec: &mut Vec<PatId>, mut pat_arena: &mut PatternArena) {
+            if let PatKind::Or { pats } = pat_arena[pat].kind.as_ref() {
+                // for pat in pats {
+                //     // TODO(iDawer): Ugh, I want to go back to references (PatId -> &Pat)
+                //     let pat = pat_arena.alloc(pat.clone());
+                //     expand(pat, vec, pat_arena);
+                // }
+                todo!()
             } else {
                 vec.push(pat)
             }
         }
 
-        let pat_arena = cx.pattern_arena.borrow();
+        let mut pat_arena = cx.pattern_arena.borrow_mut();
         let mut pats = Vec::new();
-        expand(self, &mut pats, &pat_arena);
+        expand(self, &mut pats, &mut pat_arena);
         pats
     }
 }
@@ -866,7 +874,8 @@ pub(crate) fn compute_match_usefulness(
         })
         .collect();
 
-    let wild_pattern = cx.pattern_arena.borrow_mut().alloc(Pat::Wild, &cx.infer[cx.match_expr]);
+    let wild_pattern =
+        cx.pattern_arena.borrow_mut().alloc(Pat::wildcard_from_ty(&cx.infer[cx.match_expr]));
     let v = PatStack::from_pattern(wild_pattern);
     let usefulness = is_useful(cx, &matrix, &v, ConstructWitness, false, true);
     let non_exhaustiveness_witnesses = match usefulness {
@@ -876,31 +885,7 @@ pub(crate) fn compute_match_usefulness(
     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]
-    }
-}
+pub(crate) type PatternArena = Arena<Pat>;
 
 mod helper {
     use hir_def::expr::{Pat, PatId};
@@ -908,7 +893,7 @@ mod helper {
     use super::MatchCheckCtx;
 
     pub(super) trait PatIdExt: Sized {
-        fn is_wildcard(self, cx: &MatchCheckCtx<'_>) -> bool;
+        // fn is_wildcard(self, cx: &MatchCheckCtx<'_>) -> bool;
         fn is_or_pat(self, cx: &MatchCheckCtx<'_>) -> bool;
         fn expand_or_pat(self, cx: &MatchCheckCtx<'_>) -> Vec<Self>;
     }