Repository: rust-analyzer/rust-analyzer
Pull request #11069 (2021-12-20 16:50:20)

fix: Partially fix `ide_db::search` for crate roots
Fixes https://github.com/rust-analyzer/rust-analyzer/issues/10007
bors r+


Patch:
diff --git a/Cargo.lock b/Cargo.lock
index 7d6446ea6b..cd4324cf3c 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -559,7 +559,6 @@ dependencies = [
  "tracing",
  "tracing-subscriber",
  "tracing-tree",
- "typed-arena",
 ]
 
 [[package]]
@@ -1776,12 +1775,6 @@ dependencies = [
  "stdx",
 ]
 
-[[package]]
-name = "typed-arena"
-version = "2.0.1"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "0685c84d5d54d1c26f7d3eb96cd41550adb97baed141a761cf335d3d33bcd0ae"
-
 [[package]]
 name = "ungrammar"
 version = "1.14.9"
diff --git a/crates/base_db/Cargo.toml b/crates/base_db/Cargo.toml
index 7ef82f6a34..5ba8255ddd 100644
--- a/crates/base_db/Cargo.toml
+++ b/crates/base_db/Cargo.toml
@@ -4,7 +4,7 @@ version = "0.0.0"
 description = "TBD"
 license = "MIT OR Apache-2.0"
 edition = "2021"
-rust-version = "1.57"
+rust-version = "1.56"
 
 [lib]
 doctest = false
diff --git a/crates/base_db/src/input.rs b/crates/base_db/src/input.rs
index f182427e47..08d3bc93ff 100644
--- a/crates/base_db/src/input.rs
+++ b/crates/base_db/src/input.rs
@@ -97,6 +97,10 @@ impl CrateName {
     pub fn normalize_dashes(name: &str) -> CrateName {
         Self(SmolStr::new(name.replace('-', "_")))
     }
+
+    pub fn as_smol_str(&self) -> &SmolStr {
+        &self.0
+    }
 }
 
 impl fmt::Display for CrateName {
diff --git a/crates/cfg/Cargo.toml b/crates/cfg/Cargo.toml
index 8f9437d8e7..df652c41d8 100644
--- a/crates/cfg/Cargo.toml
+++ b/crates/cfg/Cargo.toml
@@ -4,7 +4,7 @@ version = "0.0.0"
 description = "TBD"
 license = "MIT OR Apache-2.0"
 edition = "2021"
-rust-version = "1.57"
+rust-version = "1.56"
 
 [lib]
 doctest = false
diff --git a/crates/flycheck/Cargo.toml b/crates/flycheck/Cargo.toml
index 6284ebfc82..929089a9e2 100644
--- a/crates/flycheck/Cargo.toml
+++ b/crates/flycheck/Cargo.toml
@@ -4,7 +4,7 @@ version = "0.0.0"
 description = "TBD"
 license = "MIT OR Apache-2.0"
 edition = "2021"
-rust-version = "1.57"
+rust-version = "1.56"
 
 [lib]
 doctest = false
diff --git a/crates/hir/Cargo.toml b/crates/hir/Cargo.toml
index 68cfb5d324..316167d7e1 100644
--- a/crates/hir/Cargo.toml
+++ b/crates/hir/Cargo.toml
@@ -4,7 +4,7 @@ version = "0.0.0"
 description = "TBD"
 license = "MIT OR Apache-2.0"
 edition = "2021"
-rust-version = "1.57"
+rust-version = "1.56"
 
 [lib]
 doctest = false
diff --git a/crates/hir/src/display.rs b/crates/hir/src/display.rs
index 46815cff86..91ff171312 100644
--- a/crates/hir/src/display.rs
+++ b/crates/hir/src/display.rs
@@ -12,7 +12,10 @@ use hir_ty::{
     },
     Interner, TraitRefExt, WhereClause,
 };
-use syntax::SmolStr;
+use syntax::{
+    ast::{self, HasName},
+    SmolStr,
+};
 
 use crate::{
     Adt, Const, ConstParam, Enum, Field, Function, GenericParam, HasCrate, HasVisibility,
@@ -66,7 +69,7 @@ impl HirDisplay for Function {
         };
 
         let mut first = true;
-        for (name, type_ref) in &data.params {
+        for (param, type_ref) in self.assoc_fn_params(f.db).into_iter().zip(&data.params) {
             if !first {
                 write!(f, ", ")?;
             } else {
@@ -76,9 +79,11 @@ impl HirDisplay for Function {
                     continue;
                 }
             }
-            match name {
-                Some(name) => write!(f, "{}: ", name)?,
-                None => write!(f, "_: ")?,
+            match param.pattern_source(f.db) {
+                Some(ast::Pat::IdentPat(p)) if p.name().is_some() => {
+                    write!(f, "{}: ", p.name().unwrap())?
+                }
+                _ => write!(f, "_: ")?,
             }
             // FIXME: Use resolved `param.ty` or raw `type_ref`?
             // The former will ignore lifetime arguments currently.
diff --git a/crates/hir/src/lib.rs b/crates/hir/src/lib.rs
index b57f49690a..a80668f1fe 100644
--- a/crates/hir/src/lib.rs
+++ b/crates/hir/src/lib.rs
@@ -1343,7 +1343,7 @@ impl Function {
             .params
             .iter()
             .enumerate()
-            .map(|(idx, (_, type_ref))| {
+            .map(|(idx, type_ref)| {
                 let ty = Type { krate, env: environment.clone(), ty: ctx.lower_ty(type_ref) };
                 Param { func: self, ty, idx }
             })
@@ -1421,10 +1421,6 @@ impl Param {
         &self.ty
     }
 
-    pub fn name(&self, db: &dyn HirDatabase) -> Option<Name> {
-        db.function_data(self.func.id).params[self.idx].0.clone()
-    }
-
     pub fn as_local(&self, db: &dyn HirDatabase) -> Local {
         let parent = DefWithBodyId::FunctionId(self.func.into());
         let body = db.body(parent);
@@ -1458,7 +1454,7 @@ impl SelfParam {
         func_data
             .params
             .first()
-            .map(|(_, param)| match &**param {
+            .map(|param| match &**param {
                 TypeRef::Reference(.., mutability) => match mutability {
                     hir_def::type_ref::Mutability::Shared => Access::Shared,
                     hir_def::type_ref::Mutability::Mut => Access::Exclusive,
diff --git a/crates/hir/src/semantics.rs b/crates/hir/src/semantics.rs
index a299aa4498..d27869450e 100644
--- a/crates/hir/src/semantics.rs
+++ b/crates/hir/src/semantics.rs
@@ -528,7 +528,7 @@ impl<'db> SemanticsImpl<'db> {
         if first == last {
             self.descend_into_macros_impl(
                 first,
-                &mut |InFile { value, .. }| {
+                |InFile { value, .. }| {
                     if let Some(node) = value.ancestors().find_map(N::cast) {
                         res.push(node)
                     }
@@ -540,7 +540,7 @@ impl<'db> SemanticsImpl<'db> {
             let mut scratch: SmallVec<[_; 1]> = smallvec![];
             self.descend_into_macros_impl(
                 first,
-                &mut |token| {
+                |token| {
                     scratch.push(token);
                 },
                 false,
@@ -549,7 +549,7 @@ impl<'db> SemanticsImpl<'db> {
             let mut scratch = scratch.into_iter();
             self.descend_into_macros_impl(
                 last,
-                &mut |InFile { value: last, file_id: last_fid }| {
+                |InFile { value: last, file_id: last_fid }| {
                     if let Some(InFile { value: first, file_id: first_fid }) = scratch.next() {
                         if first_fid == last_fid {
                             if let Some(p) = first.parent() {
@@ -574,20 +574,20 @@ impl<'db> SemanticsImpl<'db> {
 
     fn descend_into_macros(&self, token: SyntaxToken) -> SmallVec<[SyntaxToken; 1]> {
         let mut res = smallvec![];
-        self.descend_into_macros_impl(token, &mut |InFile { value, .. }| res.push(value), false);
+        self.descend_into_macros_impl(token, |InFile { value, .. }| res.push(value), false);
         res
     }
 
     fn descend_into_macros_single(&self, token: SyntaxToken) -> SyntaxToken {
         let mut res = token.clone();
-        self.descend_into_macros_impl(token, &mut |InFile { value, .. }| res = value, true);
+        self.descend_into_macros_impl(token, |InFile { value, .. }| res = value, true);
         res
     }
 
     fn descend_into_macros_impl(
         &self,
         token: SyntaxToken,
-        f: &mut dyn FnMut(InFile<SyntaxToken>),
+        mut f: impl FnMut(InFile<SyntaxToken>),
         single: bool,
     ) {
         let _p = profile::span("descend_into_macros");
@@ -595,7 +595,7 @@ impl<'db> SemanticsImpl<'db> {
             Some(it) => it,
             None => return,
         };
-        let sa = self.analyze_no_infer(&parent);
+        let sa = self.analyze(&parent);
         let mut stack: SmallVec<[_; 4]> = smallvec![InFile::new(sa.file_id, token)];
         let mut cache = self.expansion_info_cache.borrow_mut();
         let mut mcache = self.macro_call_cache.borrow_mut();
@@ -927,23 +927,14 @@ impl<'db> SemanticsImpl<'db> {
     }
 
     fn analyze(&self, node: &SyntaxNode) -> SourceAnalyzer {
-        self.analyze_impl(node, None, true)
+        self.analyze_impl(node, None)
     }
 
     fn analyze_with_offset(&self, node: &SyntaxNode, offset: TextSize) -> SourceAnalyzer {
-        self.analyze_impl(node, Some(offset), true)
+        self.analyze_impl(node, Some(offset))
     }
 
-    fn analyze_no_infer(&self, node: &SyntaxNode) -> SourceAnalyzer {
-        self.analyze_impl(node, None, false)
-    }
-
-    fn analyze_impl(
-        &self,
-        node: &SyntaxNode,
-        offset: Option<TextSize>,
-        infer_body: bool,
-    ) -> SourceAnalyzer {
+    fn analyze_impl(&self, node: &SyntaxNode, offset: Option<TextSize>) -> SourceAnalyzer {
         let _p = profile::span("Semantics::analyze_impl");
         let node = self.find_file(node.clone());
         let node = node.as_ref();
@@ -955,11 +946,7 @@ impl<'db> SemanticsImpl<'db> {
 
         let resolver = match container {
             ChildContainer::DefWithBodyId(def) => {
-                return if infer_body {
-                    SourceAnalyzer::new_for_body(self.db, def, node, offset)
-                } else {
-                    SourceAnalyzer::new_for_body_no_infer(self.db, def, node, offset)
-                }
+                return SourceAnalyzer::new_for_body(self.db, def, node, offset)
             }
             ChildContainer::TraitId(it) => it.resolver(self.db.upcast()),
             ChildContainer::ImplId(it) => it.resolver(self.db.upcast()),
@@ -1130,7 +1117,6 @@ to_def_impls![
     (crate::TypeParam, ast::TypeParam, type_param_to_def),
     (crate::LifetimeParam, ast::LifetimeParam, lifetime_param_to_def),
     (crate::ConstParam, ast::ConstParam, const_param_to_def),
-    (crate::GenericParam, ast::GenericParam, generic_param_to_def),
     (crate::MacroDef, ast::Macro, macro_to_def),
     (crate::Local, ast::IdentPat, bind_pat_to_def),
     (crate::Local, ast::SelfParam, self_param_to_def),
diff --git a/crates/hir/src/semantics/source_to_def.rs b/crates/hir/src/semantics/source_to_def.rs
index 9b8e563592..877d385fbd 100644
--- a/crates/hir/src/semantics/source_to_def.rs
+++ b/crates/hir/src/semantics/source_to_def.rs
@@ -92,8 +92,8 @@ use hir_def::{
     expr::{LabelId, PatId},
     keys::{self, Key},
     AdtId, ConstId, ConstParamId, DefWithBodyId, EnumId, EnumVariantId, FieldId, FunctionId,
-    GenericDefId, GenericParamId, ImplId, LifetimeParamId, ModuleId, StaticId, StructId, TraitId,
-    TypeAliasId, TypeParamId, UnionId, VariantId,
+    GenericDefId, ImplId, LifetimeParamId, ModuleId, StaticId, StructId, TraitId, TypeAliasId,
+    TypeParamId, UnionId, VariantId,
 };
 use hir_expand::{name::AsName, AstId, HirFileId, MacroCallId, MacroDefId, MacroDefKind};
 use rustc_hash::FxHashMap;
@@ -299,23 +299,6 @@ impl SourceToDefCtx<'_, '_> {
         dyn_map[keys::CONST_PARAM].get(&src).copied()
     }
 
-    pub(super) fn generic_param_to_def(
-        &mut self,
-        InFile { file_id, value }: InFile<ast::GenericParam>,
-    ) -> Option<GenericParamId> {
-        match value {
-            ast::GenericParam::ConstParam(it) => {
-                self.const_param_to_def(InFile::new(file_id, it)).map(GenericParamId::ConstParamId)
-            }
-            ast::GenericParam::LifetimeParam(it) => self
-                .lifetime_param_to_def(InFile::new(file_id, it))
-                .map(GenericParamId::LifetimeParamId),
-            ast::GenericParam::TypeParam(it) => {
-                self.type_param_to_def(InFile::new(file_id, it)).map(GenericParamId::TypeParamId)
-            }
-        }
-    }
-
     pub(super) fn macro_to_def(&mut self, src: InFile<ast::Macro>) -> Option<MacroDefId> {
         let makro = self.dyn_map(src.as_ref()).and_then(|it| it[keys::MACRO].get(&src).copied());
         if let res @ Some(_) = makro {
diff --git a/crates/hir/src/source_analyzer.rs b/crates/hir/src/source_analyzer.rs
index 2d779393f0..4f987db651 100644
--- a/crates/hir/src/source_analyzer.rs
+++ b/crates/hir/src/source_analyzer.rs
@@ -50,7 +50,7 @@ impl SourceAnalyzer {
     pub(crate) fn new_for_body(
         db: &dyn HirDatabase,
         def: DefWithBodyId,
-        node @ InFile { file_id, .. }: InFile<&SyntaxNode>,
+        node: InFile<&SyntaxNode>,
         offset: Option<TextSize>,
     ) -> SourceAnalyzer {
         let (body, source_map) = db.body_with_source_map(def);
@@ -65,29 +65,7 @@ impl SourceAnalyzer {
             body: Some(body),
             body_source_map: Some(source_map),
             infer: Some(db.infer(def)),
-            file_id,
-        }
-    }
-
-    pub(crate) fn new_for_body_no_infer(
-        db: &dyn HirDatabase,
-        def: DefWithBodyId,
-        node @ InFile { file_id, .. }: InFile<&SyntaxNode>,
-        offset: Option<TextSize>,
-    ) -> SourceAnalyzer {
-        let (body, source_map) = db.body_with_source_map(def);
-        let scopes = db.expr_scopes(def);
-        let scope = match offset {
-            None => scope_for(&scopes, &source_map, node),
-            Some(offset) => scope_for_offset(db, &scopes, &source_map, node.with_value(offset)),
-        };
-        let resolver = resolver_for_scope(db.upcast(), def, scope);
-        SourceAnalyzer {
-            resolver,
-            body: Some(body),
-            body_source_map: Some(source_map),
-            infer: None,
-            file_id,
+            file_id: node.file_id,
         }
     }
 
diff --git a/crates/hir_def/Cargo.toml b/crates/hir_def/Cargo.toml
index 0fca025e18..8672ce6615 100644
--- a/crates/hir_def/Cargo.toml
+++ b/crates/hir_def/Cargo.toml
@@ -4,7 +4,7 @@ version = "0.0.0"
 description = "TBD"
 license = "MIT OR Apache-2.0"
 edition = "2021"
-rust-version = "1.57"
+rust-version = "1.56"
 
 [lib]
 doctest = false
diff --git a/crates/hir_def/src/data.rs b/crates/hir_def/src/data.rs
index aa2844461b..bf8bd931a5 100644
--- a/crates/hir_def/src/data.rs
+++ b/crates/hir_def/src/data.rs
@@ -20,7 +20,7 @@ use crate::{
 #[derive(Debug, Clone, PartialEq, Eq)]
 pub struct FunctionData {
     pub name: Name,
-    pub params: Vec<(Option<Name>, Interned<TypeRef>)>,
+    pub params: Vec<Interned<TypeRef>>,
     pub ret_type: Interned<TypeRef>,
     pub async_ret_type: Option<Interned<TypeRef>>,
     pub attrs: Attrs,
@@ -72,7 +72,7 @@ impl FunctionData {
             params: enabled_params
                 .clone()
                 .filter_map(|id| match &item_tree[id] {
-                    Param::Normal(name, ty) => Some((name.clone(), ty.clone())),
+                    Param::Normal(ty) => Some(ty.clone()),
                     Param::Varargs => None,
                 })
                 .collect(),
diff --git a/crates/hir_def/src/generics.rs b/crates/hir_def/src/generics.rs
index c4bd5b39c5..98eafa9000 100644
--- a/crates/hir_def/src/generics.rs
+++ b/crates/hir_def/src/generics.rs
@@ -113,7 +113,7 @@ impl GenericParams {
                 // Don't create an `Expander` nor call `loc.source(db)` if not needed since this
                 // causes a reparse after the `ItemTree` has been created.
                 let mut expander = Lazy::new(|| Expander::new(db, loc.source(db).file_id, module));
-                for (_, param) in &func_data.params {
+                for param in &func_data.params {
                     generic_params.fill_implicit_impl_trait_args(db, &mut expander, param);
                 }
 
diff --git a/crates/hir_def/src/item_tree.rs b/crates/hir_def/src/item_tree.rs
index aafda49693..2449e4f3e2 100644
--- a/crates/hir_def/src/item_tree.rs
+++ b/crates/hir_def/src/item_tree.rs
@@ -598,7 +598,7 @@ pub struct Function {
 
 #[derive(Debug, Clone, Eq, PartialEq)]
 pub enum Param {
-    Normal(Option<Name>, Interned<TypeRef>),
+    Normal(Interned<TypeRef>),
     Varargs,
 }
 
diff --git a/crates/hir_def/src/item_tree/lower.rs b/crates/hir_def/src/item_tree/lower.rs
index acc26bcf63..4396801116 100644
--- a/crates/hir_def/src/item_tree/lower.rs
+++ b/crates/hir_def/src/item_tree/lower.rs
@@ -269,7 +269,7 @@ impl<'a> Ctx<'a> {
                     }
                 };
                 let ty = Interned::new(self_type);
-                let idx = self.data().params.alloc(Param::Normal(None, ty));
+                let idx = self.data().params.alloc(Param::Normal(ty));
                 self.add_attrs(idx.into(), RawAttrs::new(self.db, &self_param, &self.hygiene));
                 has_self_param = true;
             }
@@ -279,19 +279,7 @@ impl<'a> Ctx<'a> {
                     None => {
                         let type_ref = TypeRef::from_ast_opt(&self.body_ctx, param.ty());
                         let ty = Interned::new(type_ref);
-                        let mut pat = param.pat();
-                        // FIXME: This really shouldn't be here, in fact FunctionData/ItemTree's function shouldn't know about
-                        // pattern names at all
-                        let name = loop {
-                            match pat {
-                                Some(ast::Pat::RefPat(ref_pat)) => pat = ref_pat.pat(),
-                                Some(ast::Pat::IdentPat(ident)) => {
-                                    break ident.name().map(|it| it.as_name())
-                                }
-                                _ => break None,
-                            }
-                        };
-                        self.data().params.alloc(Param::Normal(name, ty))
+                        self.data().params.alloc(Param::Normal(ty))
                     }
                 };
                 self.add_attrs(idx.into(), RawAttrs::new(self.db, &param, &self.hygiene));
diff --git a/crates/hir_def/src/item_tree/pretty.rs b/crates/hir_def/src/item_tree/pretty.rs
index eaaff5a21f..4b46283743 100644
--- a/crates/hir_def/src/item_tree/pretty.rs
+++ b/crates/hir_def/src/item_tree/pretty.rs
@@ -257,11 +257,8 @@ impl<'a> Printer<'a> {
                         for param in params.clone() {
                             this.print_attrs_of(param);
                             match &this.tree[param] {
-                                Param::Normal(name, ty) => {
-                                    match name {
-                                        Some(name) => w!(this, "{}: ", name),
-                                        None => w!(this, "_: "),
-                                    }
+                                Param::Normal(ty) => {
+                                    w!(this, "_: ");
                                     this.print_type_ref(ty);
                                     wln!(this, ",");
                                 }
diff --git a/crates/hir_expand/Cargo.toml b/crates/hir_expand/Cargo.toml
index cd1dd54163..039861f7f7 100644
--- a/crates/hir_expand/Cargo.toml
+++ b/crates/hir_expand/Cargo.toml
@@ -4,7 +4,7 @@ version = "0.0.0"
 description = "TBD"
 license = "MIT OR Apache-2.0"
 edition = "2021"
-rust-version = "1.57"
+rust-version = "1.56"
 
 [lib]
 doctest = false
diff --git a/crates/hir_ty/Cargo.toml b/crates/hir_ty/Cargo.toml
index d317fe6830..a1a7063d48 100644
--- a/crates/hir_ty/Cargo.toml
+++ b/crates/hir_ty/Cargo.toml
@@ -4,7 +4,7 @@ version = "0.0.0"
 description = "TBD"
 license = "MIT OR Apache-2.0"
 edition = "2021"
-rust-version = "1.57"
+rust-version = "1.56"
 
 [lib]
 doctest = false
@@ -23,7 +23,6 @@ chalk-ir = "0.75"
 chalk-recursive = { version = "0.75", default-features = false }
 la-arena = { version = "0.3.0", path = "../../lib/arena" }
 once_cell = { version = "1.5.0" }
-typed-arena = "2.0.1"
 
 stdx = { path = "../stdx", version = "0.0.0" }
 hir_def = { path = "../hir_def", version = "0.0.0" }
diff --git a/crates/hir_ty/src/diagnostics/expr.rs b/crates/hir_ty/src/diagnostics/expr.rs
index a8c4026e31..d3a0100123 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, type_ref::Mutability, AssocItemId,
@@ -11,14 +11,12 @@ use hir_def::{
 use hir_expand::name;
 use itertools::Either;
 use rustc_hash::FxHashSet;
-use typed_arena::Arena;
 
 use crate::{
     db::HirDatabase,
     diagnostics::match_check::{
         self,
-        deconstruct_pat::DeconstructedPat,
-        usefulness::{compute_match_usefulness, MatchCheckCtx},
+        usefulness::{compute_match_usefulness, expand_pattern, MatchCheckCtx, PatternArena},
     },
     AdtId, InferenceResult, Interner, Ty, TyExt, TyKind,
 };
@@ -277,20 +275,15 @@ impl ExprValidator {
     ) {
         let body = db.body(self.owner);
 
-        let match_expr_ty = &infer[match_expr];
-        if match_expr_ty.is_unknown() {
+        let match_expr_ty = if infer.type_of_expr[match_expr].is_unknown() {
             return;
-        }
-
-        let pattern_arena = Arena::new();
-        let cx = MatchCheckCtx {
-            module: self.owner.module(db.upcast()),
-            body: self.owner,
-            db,
-            pattern_arena: &pattern_arena,
+        } else {
+            &infer.type_of_expr[match_expr]
         };
 
-        let mut m_arms = Vec::with_capacity(arms.len());
+        let pattern_arena = RefCell::new(PatternArena::new());
+
+        let mut m_arms = Vec::new();
         let mut has_lowering_errors = false;
         for arm in arms {
             if let Some(pat_ty) = infer.type_of_pat.get(arm.pat) {
@@ -315,7 +308,13 @@ impl ExprValidator {
                     // check the usefulness of each pattern as we added it
                     // to the matrix here.
                     let m_arm = match_check::MatchArm {
-                        pat: self.lower_pattern(&cx, arm.pat, db, &body, &mut has_lowering_errors),
+                        pat: self.lower_pattern(
+                            arm.pat,
+                            &mut pattern_arena.borrow_mut(),
+                            db,
+                            &body,
+                            &mut has_lowering_errors,
+                        ),
                         has_guard: arm.guard.is_some(),
                     };
                     m_arms.push(m_arm);
@@ -333,10 +332,17 @@ impl ExprValidator {
             return;
         }
 
-        let report = compute_match_usefulness(&cx, &m_arms, match_expr_ty);
+        let cx = MatchCheckCtx {
+            module: self.owner.module(db.upcast()),
+            match_expr,
+            infer: &infer,
+            db,
+            pattern_arena: &pattern_arena,
+        };
+        let report = compute_match_usefulness(&cx, &m_arms);
 
         // FIXME Report unreacheble arms
-        // https://github.com/rust-lang/rust/blob/f31622a50/compiler/rustc_mir_build/src/thir/pattern/check_match.rs#L200
+        // https://github.com/rust-lang/rust/blob/25c15cdbe/compiler/rustc_mir_build/src/thir/pattern/check_match.rs#L200-L201
 
         let witnesses = report.non_exhaustiveness_witnesses;
         // FIXME Report witnesses
@@ -346,17 +352,17 @@ impl ExprValidator {
         }
     }
 
-    fn lower_pattern<'p>(
+    fn lower_pattern(
         &self,
-        cx: &MatchCheckCtx<'_, 'p>,
         pat: PatId,
+        pattern_arena: &mut PatternArena,
         db: &dyn HirDatabase,
         body: &Body,
         have_errors: &mut bool,
-    ) -> &'p DeconstructedPat<'p> {
+    ) -> match_check::PatId {
         let mut patcx = match_check::PatCtxt::new(db, &self.infer, body);
         let pattern = patcx.lower_pattern(pat);
-        let pattern = cx.pattern_arena.alloc(DeconstructedPat::from_pat(cx, &pattern));
+        let pattern = pattern_arena.alloc(expand_pattern(pattern));
         if !patcx.errors.is_empty() {
             *have_errors = true;
         }
diff --git a/crates/hir_ty/src/diagnostics/match_check.rs b/crates/hir_ty/src/diagnostics/match_check.rs
index 87a8579761..b3cc83b340 100644
--- a/crates/hir_ty/src/diagnostics/match_check.rs
+++ b/crates/hir_ty/src/diagnostics/match_check.rs
@@ -5,26 +5,25 @@
 //!
 //! It is modeled on the rustc module `rustc_mir_build::thir::pattern`.
 
+mod deconstruct_pat;
 mod pat_util;
 
-pub(crate) mod deconstruct_pat;
 pub(crate) mod usefulness;
 
-use hir_def::{body::Body, expr::PatId, EnumVariantId, LocalFieldId, VariantId};
-use stdx::never;
+use hir_def::{body::Body, EnumVariantId, LocalFieldId, VariantId};
+use la_arena::Idx;
 
-use crate::{
-    db::HirDatabase, infer::BindingMode, InferenceResult, Interner, Substitution, Ty, TyKind,
-};
+use crate::{db::HirDatabase, InferenceResult, Interner, Substitution, Ty, TyKind};
 
 use self::pat_util::EnumerateAndAdjustIterator;
 
 pub(crate) use self::usefulness::MatchArm;
 
+pub(crate) type PatId = Idx<Pat>;
+
 #[derive(Clone, Debug)]
 pub(crate) enum PatternError {
     Unimplemented,
-    UnexpectedType,
     UnresolvedVariant,
     MissingField,
     ExtraFields,
@@ -42,6 +41,12 @@ pub(crate) struct Pat {
     pub(crate) kind: Box<PatKind>,
 }
 
+impl Pat {
+    pub(crate) fn wildcard_from_ty(ty: Ty) -> Self {
+        Pat { ty, kind: Box::new(PatKind::Wild) }
+    }
+}
+
 /// Close relative to `rustc_mir_build::thir::pattern::PatKind`
 #[derive(Clone, Debug, PartialEq)]
 pub(crate) enum PatKind {
@@ -95,7 +100,7 @@ impl<'a> PatCtxt<'a> {
         Self { db, infer, body, errors: Vec::new() }
     }
 
-    pub(crate) fn lower_pattern(&mut self, pat: PatId) -> Pat {
+    pub(crate) fn lower_pattern(&mut self, pat: hir_def::expr::PatId) -> Pat {
         // XXX(iDawer): Collecting pattern adjustments feels imprecise to me.
         // When lowering of & and box patterns are implemented this should be tested
         // in a manner of `match_ergonomics_issue_9095` test.
@@ -111,7 +116,7 @@ impl<'a> PatCtxt<'a> {
         )
     }
 
-    fn lower_pattern_unadjusted(&mut self, pat: PatId) -> Pat {
+    fn lower_pattern_unadjusted(&mut self, pat: hir_def::expr::PatId) -> Pat {
         let mut ty = &self.infer[pat];
         let variant = self.infer.variant_resolution_for_pat(pat);
 
@@ -133,16 +138,9 @@ impl<'a> PatCtxt<'a> {
                 PatKind::Leaf { subpatterns }
             }
 
-            hir_def::expr::Pat::Bind { ref name, subpat, .. } => {
-                let bm = self.infer.pat_binding_modes[&pat];
-                match (bm, ty.kind(Interner)) {
-                    (BindingMode::Ref(_), TyKind::Ref(.., rty)) => ty = rty,
-                    (BindingMode::Ref(_), _) => {
-                        never!("`ref {}` has wrong type {:?}", name, ty);
-                        self.errors.push(PatternError::UnexpectedType);
-                        return Pat { ty: ty.clone(), kind: PatKind::Wild.into() };
-                    }
-                    _ => (),
+            hir_def::expr::Pat::Bind { subpat, .. } => {
+                if let TyKind::Ref(.., rty) = ty.kind(Interner) {
+                    ty = rty;
                 }
                 PatKind::Binding { subpattern: self.lower_opt_pattern(subpat) }
             }
@@ -191,7 +189,7 @@ impl<'a> PatCtxt<'a> {
 
     fn lower_tuple_subpats(
         &mut self,
-        pats: &[PatId],
+        pats: &[hir_def::expr::PatId],
         expected_len: usize,
         ellipsis: Option<usize>,
     ) -> Vec<FieldPat> {
@@ -209,17 +207,17 @@ impl<'a> PatCtxt<'a> {
             .collect()
     }
 
-    fn lower_patterns(&mut self, pats: &[PatId]) -> Vec<Pat> {
+    fn lower_patterns(&mut self, pats: &[hir_def::expr::PatId]) -> Vec<Pat> {
         pats.iter().map(|&p| self.lower_pattern(p)).collect()
     }
 
-    fn lower_opt_pattern(&mut self, pat: Option<PatId>) -> Option<Pat> {
+    fn lower_opt_pattern(&mut self, pat: Option<hir_def::expr::PatId>) -> Option<Pat> {
         pat.map(|p| self.lower_pattern(p))
     }
 
     fn lower_variant_or_leaf(
         &mut self,
-        pat: PatId,
+        pat: hir_def::expr::PatId,
         ty: &Ty,
         subpatterns: Vec<FieldPat>,
     ) -> PatKind {
@@ -246,7 +244,7 @@ impl<'a> PatCtxt<'a> {
         kind
     }
 
-    fn lower_path(&mut self, pat: PatId, _path: &hir_def::path::Path) -> Pat {
+    fn lower_path(&mut self, pat: hir_def::expr::PatId, _path: &hir_def::path::Path) -> Pat {
         let ty = &self.infer[pat];
 
         let pat_from_kind = |kind| Pat { ty: ty.clone(), kind: Box::new(kind) };
diff --git a/crates/hir_ty/src/diagnostics/match_check/deconstruct_pat.rs b/crates/hir_ty/src/diagnostics/match_check/deconstruct_pat.rs
index 84ded517ba..eb7d5e5e48 100644
--- a/crates/hir_ty/src/diagnostics/match_check/deconstruct_pat.rs
+++ b/crates/hir_ty/src/diagnostics/match_check/deconstruct_pat.rs
@@ -42,7 +42,6 @@
 //! wildcards, see [`SplitWildcard`]; for integer ranges, see [`SplitIntRange`].
 
 use std::{
-    cell::Cell,
     cmp::{max, min},
     iter::once,
     ops::RangeInclusive,
@@ -53,32 +52,15 @@ use smallvec::{smallvec, SmallVec};
 use stdx::never;
 use syntax::SmolStr;
 
-use crate::{infer::normalize, AdtId, Interner, Scalar, Ty, TyExt, TyKind};
+use crate::{AdtId, Interner, Scalar, Ty, TyExt, TyKind};
 
 use super::{
-    usefulness::{helper::Captures, MatchCheckCtx, PatCtxt},
-    Pat, PatKind,
+    usefulness::{MatchCheckCtx, PatCtxt},
+    FieldPat, Pat, PatId, PatKind,
 };
 
 use self::Constructor::*;
 
-/// Recursively expand this pattern into its subpatterns. Only useful for or-patterns.
-fn expand_or_pat(pat: &Pat) -> Vec<&Pat> {
-    fn expand<'p>(pat: &'p Pat, vec: &mut Vec<&'p Pat>) {
-        if let PatKind::Or { pats } = pat.kind.as_ref() {
-            for pat in pats {
-                expand(pat, vec);
-            }
-        } else {
-            vec.push(pat)
-        }
-    }
-
-    let mut pats = Vec::new();
-    expand(pat, &mut pats);
-    pats
-}
-
 /// [Constructor] uses this in umimplemented variants.
 /// It allows porting match expressions from upstream algorithm without losing semantics.
 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
@@ -259,10 +241,6 @@ pub(super) struct Slice {
 }
 
 impl Slice {
-    fn arity(self) -> usize {
-        unimplemented!()
-    }
-
     /// See `Constructor::is_covered_by`
     fn is_covered_by(self, _other: Self) -> bool {
         unimplemented!() // never called as Slice contains Void
@@ -300,13 +278,10 @@ pub(super) enum Constructor {
     /// for those types for which we cannot list constructors explicitly, like `f64` and `str`.
     NonExhaustive,
     /// Stands for constructors that are not seen in the matrix, as explained in the documentation
-    /// for [`SplitWildcard`]. The carried `bool` is used for the `non_exhaustive_omitted_patterns`
-    /// lint.
-    Missing { nonexhaustive_enum_missing_real_variants: bool },
+    /// for [`SplitWildcard`].
+    Missing,
     /// Wildcard pattern.
     Wildcard,
-    /// Or-pattern.
-    Or,
 }
 
 impl Constructor {
@@ -314,10 +289,6 @@ impl Constructor {
         matches!(self, Wildcard)
     }
 
-    pub(super) fn is_non_exhaustive(&self) -> bool {
-        matches!(self, NonExhaustive)
-    }
-
     fn as_int_range(&self) -> Option<&IntRange> {
         match self {
             IntRange(range) => Some(range),
@@ -332,14 +303,6 @@ impl Constructor {
         }
     }
 
-    pub(super) fn is_unstable_variant(&self, _pcx: PatCtxt<'_, '_>) -> bool {
-        false //FIXME: implement this
-    }
-
-    pub(super) fn is_doc_hidden_variant(&self, _pcx: PatCtxt<'_, '_>) -> bool {
-        false //FIXME: implement this
-    }
-
     fn variant_id_for_adt(&self, adt: hir_def::AdtId) -> VariantId {
         match *self {
             Variant(id) => id.into(),
@@ -355,39 +318,16 @@ impl Constructor {
         }
     }
 
-    /// The number of fields for this constructor. This must be kept in sync with
-    /// `Fields::wildcards`.
-    pub(super) fn arity(&self, pcx: PatCtxt<'_, '_>) -> usize {
-        match self {
-            Single | Variant(_) => match *pcx.ty.kind(Interner) {
-                TyKind::Tuple(arity, ..) => arity,
-                TyKind::Ref(..) => 1,
-                TyKind::Adt(adt, ..) => {
-                    if adt_is_box(adt.0, pcx.cx) {
-                        // The only legal patterns of type `Box` (outside `std`) are `_` and box
-                        // patterns. If we're here we can assume this is a box pattern.
-                        1
-                    } else {
-                        let variant = self.variant_id_for_adt(adt.0);
-                        Fields::list_variant_nonhidden_fields(pcx.cx, pcx.ty, variant).count()
-                    }
-                }
-                _ => {
-                    never!("Unexpected type for `Single` constructor: {:?}", pcx.ty);
-                    0
-                }
-            },
-            Slice(slice) => slice.arity(),
-            Str(..)
-            | FloatRange(..)
-            | IntRange(..)
-            | NonExhaustive
-            | Opaque
-            | Missing { .. }
-            | Wildcard => 0,
-            Or => {
-                never!("The `Or` constructor doesn't have a fixed arity");
-                0
+    /// Determines the constructor that the given pattern can be specialized to.
+    pub(super) fn from_pat(cx: &MatchCheckCtx<'_>, pat: PatId) -> Self {
+        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),
+            &PatKind::LiteralBool { value } => IntRange(IntRange::from_bool(value)),
+            PatKind::Or { .. } => {
+                never!("Or-pattern should have been expanded earlier on.");
+                Wildcard
             }
         }
     }
@@ -407,7 +347,7 @@ impl Constructor {
     /// matrix, unless all of them are.
     pub(super) fn split<'a>(
         &self,
-        pcx: PatCtxt<'_, '_>,
+        pcx: PatCtxt<'_>,
         ctors: impl Iterator<Item = &'a Constructor> + Clone,
     ) -> SmallVec<[Self; 1]> {
         match self {
@@ -435,13 +375,13 @@ impl Constructor {
     /// 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 {
+    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,
+            (Missing | Wildcard, _) => false,
 
             (Single, Single) => true,
             (Variant(self_id), Variant(other_id)) => self_id == other_id,
@@ -471,7 +411,7 @@ impl Constructor {
     /// 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 {
+    fn is_covered_by_any(&self, _pcx: PatCtxt<'_>, used_ctors: &[Constructor]) -> bool {
         if used_ctors.is_empty() {
             return false;
         }
@@ -491,7 +431,7 @@ impl Constructor {
                 .any(|other| slice.is_covered_by(other)),
             // This constructor is never covered by anything else
             NonExhaustive => false,
-            Str(..) | FloatRange(..) | Opaque | Missing { .. } | Wildcard | Or => {
+            Str(..) | FloatRange(..) | Opaque | Missing | Wildcard => {
                 never!("found unexpected ctor in all_ctors: {:?}", self);
                 true
             }
@@ -523,7 +463,7 @@ pub(super) struct SplitWildcard {
 }
 
 impl SplitWildcard {
-    pub(super) fn new(pcx: PatCtxt<'_, '_>) -> Self {
+    pub(super) fn new(pcx: PatCtxt<'_>) -> Self {
         let cx = pcx.cx;
         let make_range = |start, end, scalar| IntRange(IntRange::from_range(start, end, scalar));
 
@@ -543,7 +483,7 @@ impl SplitWildcard {
             TyKind::Scalar(Scalar::Bool) => smallvec![make_range(0, 1, Scalar::Bool)],
             // TyKind::Array(..) if ... => unhandled(),
             TyKind::Array(..) | TyKind::Slice(..) => unhandled(),
-            &TyKind::Adt(AdtId(hir_def::AdtId::EnumId(enum_id)), ..) => {
+            &TyKind::Adt(AdtId(hir_def::AdtId::EnumId(enum_id)), ref _substs) => {
                 let enum_data = cx.db.enum_data(enum_id);
 
                 // If the enum is declared as `#[non_exhaustive]`, we treat it as if it had an
@@ -562,35 +502,27 @@ impl SplitWildcard {
                 //
                 // we don't want to show every possible IO error, but instead have only `_` as the
                 // witness.
-                let is_declared_nonexhaustive = cx.is_foreign_non_exhaustive_enum(pcx.ty);
-
-                let is_exhaustive_pat_feature = cx.feature_exhaustive_patterns();
+                let is_declared_nonexhaustive = cx.is_foreign_non_exhaustive_enum(enum_id);
 
                 // If `exhaustive_patterns` is disabled and our scrutinee is an empty enum, we treat it
                 // as though it had an "unknown" constructor to avoid exposing its emptiness. The
                 // exception is if the pattern is at the top level, because we want empty matches to be
                 // considered exhaustive.
                 let is_secretly_empty = enum_data.variants.is_empty()
-                    && !is_exhaustive_pat_feature
+                    && !cx.feature_exhaustive_patterns()
                     && !pcx.is_top_level;
 
-                let mut ctors: SmallVec<[_; 1]> = enum_data
-                    .variants
-                    .iter()
-                    .filter(|&(_, _v)| {
-                        // If `exhaustive_patterns` is enabled, we exclude variants known to be
-                        // uninhabited.
-                        let is_uninhabited = is_exhaustive_pat_feature
-                            && unimplemented!("after MatchCheckCtx.feature_exhaustive_patterns()");
-                        !is_uninhabited
-                    })
-                    .map(|(local_id, _)| Variant(EnumVariantId { parent: enum_id, local_id }))
-                    .collect();
-
                 if is_secretly_empty || is_declared_nonexhaustive {
-                    ctors.push(NonExhaustive);
+                    smallvec![NonExhaustive]
+                } else if cx.feature_exhaustive_patterns() {
+                    unimplemented!() // see MatchCheckCtx.feature_exhaustive_patterns()
+                } else {
+                    enum_data
+                        .variants
+                        .iter()
+                        .map(|(local_id, ..)| Variant(EnumVariantId { parent: enum_id, local_id }))
+                        .collect()
                 }
-                ctors
             }
             TyKind::Scalar(Scalar::Char) => unhandled(),
             TyKind::Scalar(Scalar::Int(..) | Scalar::Uint(..)) => unhandled(),
@@ -603,7 +535,6 @@ impl SplitWildcard {
             // This type is one for which we cannot list constructors, like `str` or `f64`.
             _ => smallvec![NonExhaustive],
         };
-
         SplitWildcard { matrix_ctors: Vec::new(), all_ctors }
     }
 
@@ -611,7 +542,7 @@ impl SplitWildcard {
     /// do what you want.
     pub(super) fn split<'a>(
         &mut self,
-        pcx: PatCtxt<'_, '_>,
+        pcx: PatCtxt<'_>,
         ctors: impl Iterator<Item = &'a Constructor> + Clone,
     ) {
         // Since `all_ctors` never contains wildcards, this won't recurse further.
@@ -621,21 +552,21 @@ impl SplitWildcard {
     }
 
     /// Whether there are any value constructors for this type that are not present in the matrix.
-    fn any_missing(&self, pcx: PatCtxt<'_, '_>) -> bool {
+    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, 'p>(
+    pub(super) fn iter_missing<'a>(
         &'a self,
-        pcx: PatCtxt<'a, 'p>,
-    ) -> impl Iterator<Item = &'a Constructor> + Captures<'p> {
+        pcx: PatCtxt<'a>,
+    ) -> 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]> {
+    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,
@@ -666,15 +597,7 @@ impl SplitWildcard {
             // 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 {
-                if pcx.is_non_exhaustive {
-                    Missing {
-                        nonexhaustive_enum_missing_real_variants: self
-                            .iter_missing(pcx)
-                            .any(|c| !(c.is_non_exhaustive() || c.is_unstable_variant(pcx))),
-                    }
-                } else {
-                    Missing { nonexhaustive_enum_missing_real_variants: false }
-                }
+                Missing
             } else {
                 Wildcard
             };
@@ -688,334 +611,291 @@ impl SplitWildcard {
 
 /// 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()`].
 ///
-/// This is constructed for a constructor using [`Fields::wildcards()`]. The idea is that
-/// [`Fields::wildcards()`] constructs a list of fields where all entries are wildcards, and then
-/// given a pattern we fill some of the fields with its subpatterns.
-/// In the following example `Fields::wildcards` returns `[_, _, _, _]`. Then in
-/// `extract_pattern_arguments` we fill some of the entries, and the result is
-/// `[Some(0), _, _, _]`.
-/// ```rust
-/// let x: [Option<u8>; 4] = foo();
-/// match x {
-///     [Some(0), ..] => {}
-/// }
-/// ```
-///
-/// Note that the number of fields of a constructor may not match the fields declared in the
-/// original struct/variant. This happens if a private or `non_exhaustive` field is uninhabited,
-/// because the code mustn't observe that it is uninhabited. In that case that field is not
-/// included in `fields`. For that reason, when you have a `mir::Field` you must use
-/// `index_with_declared_idx`.
-#[derive(Clone, Copy)]
-pub(super) struct Fields<'p> {
-    fields: &'p [DeconstructedPat<'p>],
+/// 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<'p> Fields<'p> {
-    fn empty() -> Self {
-        Fields { fields: &[] }
-    }
-
-    fn singleton(cx: &MatchCheckCtx<'_, 'p>, field: DeconstructedPat<'p>) -> Self {
-        let field = cx.pattern_arena.alloc(field);
-        Fields { fields: std::slice::from_ref(field) }
+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])
     }
 
-    pub(super) fn from_iter(
-        cx: &MatchCheckCtx<'_, 'p>,
-        fields: impl IntoIterator<Item = DeconstructedPat<'p>>,
-    ) -> Self {
-        let fields: &[_] = cx.pattern_arena.alloc_extend(fields);
-        Fields { fields }
-    }
-
-    fn wildcards_from_tys(cx: &MatchCheckCtx<'_, 'p>, tys: impl IntoIterator<Item = Ty>) -> Self {
-        Fields::from_iter(cx, tys.into_iter().map(DeconstructedPat::wildcard))
+    /// Convenience; internal use.
+    fn wildcards_from_tys(cx: &MatchCheckCtx<'_>, tys: impl IntoIterator<Item = Ty>) -> Self {
+        let wilds = tys.into_iter().map(Pat::wildcard_from_ty);
+        let pats = wilds.map(|pat| cx.alloc_pat(pat)).collect();
+        Fields::Vec(pats)
     }
 
-    // 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.
-    fn list_variant_nonhidden_fields<'a>(
-        cx: &'a MatchCheckCtx<'a, 'p>,
-        ty: &'a Ty,
-        variant: VariantId,
-    ) -> impl Iterator<Item = (LocalFieldId, Ty)> + Captures<'a> + Captures<'p> {
-        let (adt, substs) = ty.as_adt().unwrap();
-
-        let adt_is_local = variant.module(cx.db.upcast()).krate() == cx.module.krate();
-        // Whether we must not match the fields of this variant exhaustively.
-        let is_non_exhaustive = is_field_list_non_exhaustive(variant, cx) && !adt_is_local;
-
-        let visibility = cx.db.field_visibilities(variant);
-        let field_ty = cx.db.field_types(variant);
-        let fields_len = variant.variant_data(cx.db.upcast()).fields().len() as u32;
-
-        (0..fields_len).map(|idx| LocalFieldId::from_raw(idx.into())).filter_map(move |fid| {
-            let ty = field_ty[fid].clone().substitute(Interner, substs);
-            let ty = normalize(cx.db, cx.body, ty);
-            let is_visible = matches!(adt, hir_def::AdtId::EnumId(..))
-                || visibility[fid].is_visible_from(cx.db.upcast(), cx.module);
-            let is_uninhabited = cx.is_uninhabited(&ty);
-
-            if is_uninhabited && (!is_visible || is_non_exhaustive) {
-                None
-            } else {
-                Some((fid, ty))
-            }
-        })
-    }
+    /// Creates a new list of wildcard fields for a given constructor.
+    pub(crate) fn wildcards(pcx: PatCtxt<'_>, constructor: &Constructor) -> Self {
+        let ty = pcx.ty;
+        let cx = pcx.cx;
+        let wildcard_from_ty = |ty: &Ty| cx.alloc_pat(Pat::wildcard_from_ty(ty.clone()));
 
-    /// Creates a new list of wildcard fields for a given constructor. The result must have a
-    /// length of `constructor.arity()`.
-    pub(crate) fn wildcards(
-        cx: &MatchCheckCtx<'_, 'p>,
-        ty: &Ty,
-        constructor: &Constructor,
-    ) -> Self {
         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.cloned())
                 }
-                TyKind::Ref(.., rty) => Fields::wildcards_from_tys(cx, once(rty.clone())),
+                TyKind::Ref(.., rty) => Fields::from_single_pattern(wildcard_from_ty(rty)),
                 &TyKind::Adt(AdtId(adt), ref substs) => {
                     if adt_is_box(adt, cx) {
-                        // The only legal patterns of type `Box` (outside `std`) are `_` and box
-                        // patterns. If we're here we can assume this is a box pattern.
-                        let subst_ty = substs.at(Interner, 0).assert_ty_ref(Interner).clone();
-                        Fields::wildcards_from_tys(cx, once(subst_ty))
+                        // Use T as the sub pattern type of Box<T>.
+                        let subst_ty = substs.at(Interner, 0).assert_ty_ref(Interner);
+                        Fields::from_single_pattern(wildcard_from_ty(subst_ty))
                     } else {
-                        let variant = constructor.variant_id_for_adt(adt);
-                        let tys = Fields::list_variant_nonhidden_fields(cx, ty, variant)
-                            .map(|(_, ty)| ty);
-                        Fields::wildcards_from_tys(cx, tys)
+                        let variant_id = constructor.variant_id_for_adt(adt);
+                        let adt_is_local =
+                            variant_id.module(cx.db.upcast()).krate() == cx.module.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;
+
+                        cov_mark::hit!(match_check_wildcard_expanded_to_substitutions);
+                        let field_ty_data = cx.db.field_types(variant_id);
+                        let field_tys = || {
+                            field_ty_data
+                                .iter()
+                                .map(|(_, binders)| binders.clone().substitute(Interner, substs))
+                        };
+
+                        // 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, has_no_hidden_fields is always true
+                            unimplemented!("exhaustive_patterns feature")
+                        }
                     }
                 }
                 ty_kind => {
                     never!("Unexpected type for `Single` constructor: {:?}", ty_kind);
-                    Fields::wildcards_from_tys(cx, once(ty.clone()))
+                    Fields::from_single_pattern(wildcard_from_ty(ty))
                 }
             },
             Slice(..) => {
                 unimplemented!()
             }
-            Str(..)
-            | FloatRange(..)
-            | IntRange(..)
-            | NonExhaustive
-            | Opaque
-            | Missing { .. }
-            | Wildcard => Fields::empty(),
-            Or => {
-                never!("called `Fields::wildcards` on an `Or` ctor");
-                Fields::empty()
-            }
+            Str(..) | FloatRange(..) | IntRange(..) | NonExhaustive | Opaque | Missing
+            | Wildcard => Fields::Vec(Default::default()),
         };
         ret
     }
 
-    /// Returns the list of patterns.
-    pub(super) fn iter_patterns<'a>(
-        &'a self,
-    ) -> impl Iterator<Item = &'p DeconstructedPat<'p>> + Captures<'a> {
-        self.fields.iter()
-    }
-}
+    /// 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)| pcx.cx.pattern_arena.borrow()[p].clone());
+        // FIXME(iDawer) witnesses are not yet used
+        const UNHANDLED: PatKind = PatKind::Wild;
+
+        let pat = match ctor {
+            Single | Variant(_) => match pcx.ty.kind(Interner) {
+                TyKind::Adt(..) | TyKind::Tuple(..) => {
+                    // We want the real indices here.
+                    let subpatterns = subpatterns_and_indices
+                        .iter()
+                        .map(|&(field, pat)| FieldPat {
+                            field,
+                            pattern: pcx.cx.pattern_arena.borrow()[pat].clone(),
+                        })
+                        .collect();
+
+                    if let Some((hir_def::AdtId::EnumId(_), substs)) = pcx.ty.as_adt() {
+                        let enum_variant = match ctor {
+                            &Variant(id) => id,
+                            _ => unreachable!(),
+                        };
+                        PatKind::Variant { substs: substs.clone(), enum_variant, subpatterns }
+                    } else {
+                        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(..) => PatKind::Deref { subpattern: subpatterns.next().unwrap() },
+                TyKind::Slice(..) | TyKind::Array(..) => {
+                    never!("bad slice pattern {:?} {:?}", ctor, pcx.ty);
+                    PatKind::Wild
+                }
+                _ => PatKind::Wild,
+            },
+            Constructor::Slice(_) => UNHANDLED,
+            Str(_) => UNHANDLED,
+            FloatRange(..) => UNHANDLED,
+            Constructor::IntRange(_) => UNHANDLED,
+            NonExhaustive => PatKind::Wild,
+            Wildcard => return Pat::wildcard_from_ty(pcx.ty.clone()),
+            Opaque => {
+                never!("we should not try to apply an opaque constructor");
+                PatKind::Wild
+            }
+            Missing => {
+                never!(
+                    "trying to apply the `Missing` constructor; \
+                    this should have been done in `apply_constructors`",
+                );
+                PatKind::Wild
+            }
+        };
 
-/// Values and patterns can be represented as a constructor applied to some fields. This represents
-/// a pattern in this form.
-/// This also keeps track of whether the pattern has been found reachable during analysis. For this
-/// reason we should be careful not to clone patterns for which we care about that. Use
-/// `clone_and_forget_reachability` if you're sure.
-pub(crate) struct DeconstructedPat<'p> {
-    ctor: Constructor,
-    fields: Fields<'p>,
-    ty: Ty,
-    reachable: Cell<bool>,
-}
+        Pat { ty: pcx.ty.clone(), kind: Box::new(pat) }
+    }
 
-impl<'p> DeconstructedPat<'p> {
-    pub(super) fn wildcard(ty: Ty) -> Self {
-        Self::new(Wildcard, Fields::empty(), ty)
+    /// 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(),
+        }
     }
 
-    pub(super) fn new(ctor: Constructor, fields: Fields<'p>, ty: Ty) -> Self {
-        DeconstructedPat { ctor, fields, ty, reachable: Cell::new(false) }
+    /// Returns the list of patterns along with the corresponding field indices.
+    fn patterns_and_indices(&self) -> SmallVec<[(LocalFieldId, PatId); 2]> {
+        match self {
+            Fields::Vec(pats) => pats
+                .iter()
+                .copied()
+                .enumerate()
+                .map(|(i, p)| (LocalFieldId::from_raw((i as u32).into()), p))
+                .collect(),
+        }
     }
 
-    /// Construct a pattern that matches everything that starts with this constructor.
-    /// For example, if `ctor` is a `Constructor::Variant` for `Option::Some`, we get the pattern
-    /// `Some(_)`.
-    pub(super) fn wild_from_ctor(pcx: PatCtxt<'_, 'p>, ctor: Constructor) -> Self {
-        let fields = Fields::wildcards(pcx.cx, pcx.ty, &ctor);
-        DeconstructedPat::new(ctor, fields, pcx.ty.clone())
+    pub(super) fn into_patterns(self) -> SmallVec<[PatId; 2]> {
+        match self {
+            Fields::Vec(pats) => pats,
+        }
     }
 
-    /// Clone this value. This method emphasizes that cloning loses reachability information and
-    /// should be done carefully.
-    pub(super) fn clone_and_forget_reachability(&self) -> Self {
-        DeconstructedPat::new(self.ctor.clone(), self.fields, self.ty.clone())
+    /// 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 = (LocalFieldId, PatId)>,
+    ) -> Self {
+        self.replace_fields_indexed(
+            new_pats.into_iter().map(|(field, pat)| (u32::from(field.into_raw()) as usize, pat)),
+        )
     }
 
-    pub(crate) fn from_pat(cx: &MatchCheckCtx<'_, 'p>, pat: &Pat) -> Self {
-        let mkpat = |pat| DeconstructedPat::from_pat(cx, pat);
-        let ctor;
-        let fields;
-        match pat.kind.as_ref() {
-            PatKind::Binding { subpattern: Some(subpat) } => return mkpat(subpat),
-            PatKind::Binding { subpattern: None } | PatKind::Wild => {
-                ctor = Wildcard;
-                fields = Fields::empty();
-            }
-            PatKind::Deref { subpattern } => {
-                ctor = Single;
-                fields = Fields::singleton(cx, mkpat(subpattern));
-            }
-            PatKind::Leaf { subpatterns } | PatKind::Variant { subpatterns, .. } => {
-                match pat.ty.kind(Interner) {
-                    TyKind::Tuple(_, substs) => {
-                        ctor = Single;
-                        let mut wilds: SmallVec<[_; 2]> = substs
-                            .iter(Interner)
-                            .map(|arg| arg.assert_ty_ref(Interner).clone())
-                            .map(DeconstructedPat::wildcard)
-                            .collect();
-                        for pat in subpatterns {
-                            let idx: u32 = pat.field.into_raw().into();
-                            wilds[idx as usize] = mkpat(&pat.pattern);
-                        }
-                        fields = Fields::from_iter(cx, wilds)
-                    }
-                    TyKind::Adt(adt, substs) if adt_is_box(adt.0, cx) => {
-                        // The only legal patterns of type `Box` (outside `std`) are `_` and box
-                        // patterns. If we're here we can assume this is a box pattern.
-                        // FIXME(Nadrieril): A `Box` can in theory be matched either with `Box(_,
-                        // _)` or a box pattern. As a hack to avoid an ICE with the former, we
-                        // ignore other fields than the first one. This will trigger an error later
-                        // anyway.
-                        // See https://github.com/rust-lang/rust/issues/82772 ,
-                        // explanation: https://github.com/rust-lang/rust/pull/82789#issuecomment-796921977
-                        // The problem is that we can't know from the type whether we'll match
-                        // normally or through box-patterns. We'll have to figure out a proper
-                        // solution when we introduce generalized deref patterns. Also need to
-                        // prevent mixing of those two options.
-                        let pat =
-                            subpatterns.iter().find(|pat| pat.field.into_raw() == 0u32.into());
-                        let field = if let Some(pat) = pat {
-                            mkpat(&pat.pattern)
-                        } else {
-                            let ty = substs.at(Interner, 0).assert_ty_ref(Interner).clone();
-                            DeconstructedPat::wildcard(ty)
-                        };
-                        ctor = Single;
-                        fields = Fields::singleton(cx, field)
-                    }
-                    &TyKind::Adt(adt, _) => {
-                        ctor = match pat.kind.as_ref() {
-                            PatKind::Leaf { .. } => Single,
-                            PatKind::Variant { enum_variant, .. } => Variant(*enum_variant),
-                            _ => {
-                                never!();
-                                Wildcard
-                            }
-                        };
-                        let variant = ctor.variant_id_for_adt(adt.0);
-                        let fields_len = variant.variant_data(cx.db.upcast()).fields().len();
-                        // For each field in the variant, we store the relevant index into `self.fields` if any.
-                        let mut field_id_to_id: Vec<Option<usize>> = vec![None; fields_len];
-                        let tys = Fields::list_variant_nonhidden_fields(cx, &pat.ty, variant)
-                            .enumerate()
-                            .map(|(i, (fid, ty))| {
-                                let field_idx: u32 = fid.into_raw().into();
-                                field_id_to_id[field_idx as usize] = Some(i);
-                                ty
-                            });
-                        let mut wilds: SmallVec<[_; 2]> =
-                            tys.map(DeconstructedPat::wildcard).collect();
-                        for pat in subpatterns {
-                            let field_idx: u32 = pat.field.into_raw().into();
-                            if let Some(i) = field_id_to_id[field_idx as usize] {
-                                wilds[i] = mkpat(&pat.pattern);
-                            }
-                        }
-                        fields = Fields::from_iter(cx, wilds);
-                    }
-                    _ => {
-                        never!("pattern has unexpected type: pat: {:?}, ty: {:?}", pat, &pat.ty);
-                        ctor = Wildcard;
-                        fields = Fields::empty();
+    /// 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;
                     }
                 }
             }
-            &PatKind::LiteralBool { value } => {
-                ctor = IntRange(IntRange::from_bool(value));
-                fields = Fields::empty();
-            }
-            PatKind::Or { .. } => {
-                ctor = Or;
-                let pats: SmallVec<[_; 2]> = expand_or_pat(pat).into_iter().map(mkpat).collect();
-                fields = Fields::from_iter(cx, pats)
-            }
         }
-        DeconstructedPat::new(ctor, fields, pat.ty.clone())
+        fields
     }
 
-    // // FIXME(iDawer): implement reporting of noncovered patterns
-    // pub(crate) fn to_pat(&self, _cx: &MatchCheckCtx<'_, 'p>) -> Pat {
-    //     Pat { ty: self.ty.clone(), kind: PatKind::Wild.into() }
-    // }
-
-    pub(super) fn is_or_pat(&self) -> bool {
-        matches!(self.ctor, Or)
-    }
-
-    pub(super) fn ctor(&self) -> &Constructor {
-        &self.ctor
-    }
-
-    pub(super) fn ty(&self) -> &Ty {
-        &self.ty
-    }
+    /// 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 = pats.into_iter().map(|pat| cx.alloc_pat(pat)).collect();
 
-    pub(super) fn iter_fields<'a>(&'a self) -> impl Iterator<Item = &'a DeconstructedPat<'a>> + 'a {
-        self.fields.iter_patterns()
+        match self {
+            Fields::Vec(_) => Fields::Vec(pats),
+        }
     }
 
-    /// Specialize this pattern with a constructor.
-    /// `other_ctor` can be different from `self.ctor`, but must be covered by it.
-    pub(super) fn specialize<'a>(
-        &'a self,
-        cx: &MatchCheckCtx<'_, 'p>,
-        other_ctor: &Constructor,
-    ) -> SmallVec<[&'p DeconstructedPat<'p>; 2]> {
-        match (&self.ctor, other_ctor) {
-            (Wildcard, _) => {
-                // We return a wildcard for each field of `other_ctor`.
-                Fields::wildcards(cx, &self.ty, other_ctor).iter_patterns().collect()
+    /// 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 {
+        // FIXME(iDawer): Factor out pattern deep cloning. See discussion:
+        // https://github.com/rust-analyzer/rust-analyzer/pull/8717#discussion_r633086640
+        let mut arena = cx.pattern_arena.borrow_mut();
+        match arena[pat].kind.as_ref() {
+            PatKind::Deref { subpattern } => {
+                assert_eq!(self.len(), 1);
+                let subpattern = subpattern.clone();
+                Fields::from_single_pattern(arena.alloc(subpattern))
             }
-            (Slice(self_slice), Slice(other_slice))
-                if self_slice.arity() != other_slice.arity() =>
-            {
-                unimplemented!()
+            PatKind::Leaf { subpatterns } | PatKind::Variant { subpatterns, .. } => {
+                let subpatterns = subpatterns.clone();
+                let subpatterns = subpatterns
+                    .iter()
+                    .map(|field_pat| (field_pat.field, arena.alloc(field_pat.pattern.clone())));
+                self.replace_with_fieldpats(subpatterns)
             }
-            _ => self.fields.iter_patterns().collect(),
-        }
-    }
 
-    /// We keep track for each pattern if it was ever reachable during the analysis. This is used
-    /// with `unreachable_spans` to report unreachable subpatterns arising from or patterns.
-    pub(super) fn set_reachable(&self) {
-        self.reachable.set(true)
-    }
-    pub(super) fn is_reachable(&self) -> bool {
-        self.reachable.get()
+            PatKind::Wild
+            | PatKind::Binding { .. }
+            | PatKind::LiteralBool { .. }
+            | PatKind::Or { .. } => self.clone(),
+        }
     }
 }
 
-fn is_field_list_non_exhaustive(variant_id: VariantId, cx: &MatchCheckCtx<'_, '_>) -> bool {
+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(),
@@ -1024,7 +904,7 @@ fn is_field_list_non_exhaustive(variant_id: VariantId, cx: &MatchCheckCtx<'_, '_
     cx.db.attrs(attr_def_id).by_key("non_exhaustive").exists()
 }
 
-fn adt_is_box(adt: hir_def::AdtId, cx: &MatchCheckCtx<'_, '_>) -> bool {
+fn adt_is_box(adt: hir_def::AdtId, cx: &MatchCheckCtx<'_>) -> bool {
     use hir_def::lang_item::LangItemTarget;
     match cx.db.lang_item(cx.module.krate(), SmolStr::new_inline("owned_box")) {
         Some(LangItemTarget::StructId(box_id)) => adt == box_id.into(),
diff --git a/crates/hir_ty/src/diagnostics/match_check/usefulness.rs b/crates/hir_ty/src/diagnostics/match_check/usefulness.rs
index e8a13955d2..43545708e5 100644
--- a/crates/hir_ty/src/diagnostics/match_check/usefulness.rs
+++ b/crates/hir_ty/src/diagnostics/match_check/usefulness.rs
@@ -1,5 +1,5 @@
-//! Based on rust-lang/rust (last sync f31622a50 2021-11-12)
-//! <https://github.com/rust-lang/rust/blob/f31622a50/compiler/rustc_mir_build/src/thir/pattern/usefulness.rs>
+//! Based on rust-lang/rust 1.52.0-nightly (25c15cdbe 2021-04-22)
+//! <https://github.com/rust-lang/rust/blob/25c15cdbe/compiler/rustc_mir_build/src/thir/pattern/usefulness.rs>
 //!
 //! -----
 //!
@@ -271,27 +271,33 @@
 //! The details are not necessary to understand this file, so we explain them in
 //! [`super::deconstruct_pat`]. Splitting is done by the [`Constructor::split`] function.
 
-use std::iter::once;
+use std::{cell::RefCell, iter::FromIterator};
 
-use hir_def::{AdtId, DefWithBodyId, HasModule, ModuleId};
+use hir_def::{expr::ExprId, HasModule, ModuleId};
+use la_arena::Arena;
+use once_cell::unsync::OnceCell;
+use rustc_hash::FxHashMap;
 use smallvec::{smallvec, SmallVec};
-use typed_arena::Arena;
 
-use crate::{db::HirDatabase, Ty, TyExt};
+use crate::{db::HirDatabase, InferenceResult, Interner, Ty};
 
-use super::deconstruct_pat::{Constructor, DeconstructedPat, Fields, SplitWildcard};
+use super::{
+    deconstruct_pat::{Constructor, Fields, SplitWildcard},
+    Pat, PatId, PatKind, PatternFoldable, PatternFolder,
+};
 
-use self::{helper::Captures, ArmType::*, Usefulness::*};
+use self::{helper::PatIdExt, Usefulness::*, WitnessPreference::*};
 
-pub(crate) struct MatchCheckCtx<'a, 'p> {
+pub(crate) struct MatchCheckCtx<'a> {
     pub(crate) module: ModuleId,
-    pub(crate) body: DefWithBodyId,
+    pub(crate) match_expr: ExprId,
+    pub(crate) infer: &'a InferenceResult,
     pub(crate) db: &'a dyn HirDatabase,
     /// Lowered patterns from arms plus generated by the check.
-    pub(crate) pattern_arena: &'p Arena<DeconstructedPat<'p>>,
+    pub(crate) pattern_arena: &'a RefCell<PatternArena>,
 }
 
-impl<'a, 'p> MatchCheckCtx<'a, 'p> {
+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
@@ -299,16 +305,12 @@ impl<'a, 'p> MatchCheckCtx<'a, 'p> {
     }
 
     /// Returns whether the given type is an enum from another crate declared `#[non_exhaustive]`.
-    pub(super) fn is_foreign_non_exhaustive_enum(&self, ty: &Ty) -> bool {
-        match ty.as_adt() {
-            Some((adt @ AdtId::EnumId(_), _)) => {
-                let has_non_exhaustive_attr =
-                    self.db.attrs(adt.into()).by_key("non_exhaustive").exists();
-                let is_local = adt.module(self.db.upcast()).krate() == self.module.krate();
-                has_non_exhaustive_attr && !is_local
-            }
-            _ => false,
-        }
+    pub(super) fn is_foreign_non_exhaustive_enum(&self, enum_id: hir_def::EnumId) -> bool {
+        let has_non_exhaustive_attr =
+            self.db.attrs(enum_id.into()).by_key("non_exhaustive").exists();
+        let is_local =
+            hir_def::AdtId::from(enum_id).module(self.db.upcast()).krate() == self.module.krate();
+        has_non_exhaustive_attr && !is_local
     }
 
     // Rust feature described as "Allows exhaustive pattern matching on types that contain uninhabited types."
@@ -316,34 +318,92 @@ impl<'a, 'p> MatchCheckCtx<'a, 'p> {
         // FIXME see MatchCheckCtx::is_uninhabited
         false
     }
+
+    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 {
+        self.pattern_arena.borrow()[pat].ty.clone()
+    }
 }
 
 #[derive(Copy, Clone)]
-pub(super) struct PatCtxt<'a, 'p> {
-    pub(super) cx: &'a MatchCheckCtx<'a, 'p>,
+pub(super) struct PatCtxt<'a> {
+    pub(super) cx: &'a MatchCheckCtx<'a>,
     /// Type of the current column under investigation.
     pub(super) ty: &'a 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,
-    /// Wether the current pattern is from a `non_exhaustive` enum.
-    pub(super) is_non_exhaustive: bool,
+}
+
+pub(crate) fn expand_pattern(pat: Pat) -> Pat {
+    LiteralExpander.fold_pattern(&pat)
+}
+
+struct LiteralExpander;
+
+impl PatternFolder for LiteralExpander {
+    fn fold_pattern(&mut self, pat: &Pat) -> Pat {
+        match (pat.ty.kind(Interner), pat.kind.as_ref()) {
+            (_, PatKind::Binding { subpattern: Some(s), .. }) => s.fold_with(self),
+            _ => pat.super_fold_with(self),
+        }
+    }
+}
+
+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].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: &mut PatternArena) {
+            if let PatKind::Or { pats } = pat_arena[pat].kind.as_ref() {
+                // FIXME(iDawer): Factor out pattern deep cloning. See discussion:
+                // https://github.com/rust-analyzer/rust-analyzer/pull/8717#discussion_r633086640
+                let pats = pats.clone();
+                for pat in pats {
+                    let pat = pat_arena.alloc(pat.clone());
+                    expand(pat, vec, pat_arena);
+                }
+            } else {
+                vec.push(pat)
+            }
+        }
+
+        let mut pat_arena = cx.pattern_arena.borrow_mut();
+        let mut pats = Vec::new();
+        expand(self, &mut pats, &mut 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<'p> {
-    pats: SmallVec<[&'p DeconstructedPat<'p>; 2]>,
+pub(super) struct PatStack {
+    pats: SmallVec<[PatId; 2]>,
+    /// Cache for the constructor of the head
+    head_ctor: OnceCell<Constructor>,
 }
 
-impl<'p> PatStack<'p> {
-    fn from_pattern(pat: &'p DeconstructedPat<'p>) -> Self {
+impl PatStack {
+    fn from_pattern(pat: PatId) -> Self {
         Self::from_vec(smallvec![pat])
     }
 
-    fn from_vec(vec: SmallVec<[&'p DeconstructedPat<'p>; 2]>) -> Self {
-        PatStack { pats: vec }
+    fn from_vec(vec: SmallVec<[PatId; 2]>) -> Self {
+        PatStack { pats: vec, head_ctor: OnceCell::new() }
     }
 
     fn is_empty(&self) -> bool {
@@ -354,42 +414,73 @@ impl<'p> PatStack<'p> {
         self.pats.len()
     }
 
-    fn head(&self) -> &'p DeconstructedPat<'p> {
+    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()))
+    }
+
     // 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) -> impl Iterator<Item = PatStack<'p>> + Captures<'_> {
-        self.head().iter_fields().map(move |pat| {
+    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.
+    /// 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, cx: &MatchCheckCtx<'_, 'p>, ctor: &Constructor) -> PatStack<'p> {
+    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: SmallVec<[_; 2]> = self.head().specialize(cx, ctor);
+        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())
+    }
+}
+
 /// A 2D matrix.
 #[derive(Clone)]
-pub(super) struct Matrix<'p> {
-    patterns: Vec<PatStack<'p>>,
+pub(super) struct Matrix {
+    patterns: Vec<PatStack>,
 }
 
-impl<'p> Matrix<'p> {
+impl Matrix {
     fn empty() -> Self {
         Matrix { patterns: vec![] }
     }
@@ -401,65 +492,328 @@ impl<'p> Matrix<'p> {
 
     /// 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<'p>) {
-        if !row.is_empty() && row.head().is_or_pat() {
-            self.patterns.extend(row.expand_or_pat());
+    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 = &'p DeconstructedPat<'p>> + Clone + Captures<'_> {
+    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<'_, 'p>, ctor: &Constructor) -> Matrix<'p> {
+    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 row in &self.patterns {
-            if ctor.is_covered_by(pcx, row.head().ctor()) {
-                let new_row = row.pop_head_constructor(pcx.cx, ctor);
-                matrix.push(new_row);
-            }
+        for x in rows {
+            // Using `push` ensures we correctly expand or-patterns.
+            matrix.push(x, cx);
         }
         matrix
     }
 }
 
+/// Given a pattern or a pattern-stack, this struct captures a set of its subpatterns. We use that
+/// to track reachable sub-patterns arising from 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). When there are or-patterns, some subpatterns may be reachable while others
+/// aren't. In this case the whole pattern still counts as reachable, but we will lint the
+/// unreachable subpatterns.
+///
+/// This supports a limited set of operations, so not all possible sets of subpatterns can be
+/// represented. That's ok, we only want the ones that make sense for our usage.
+///
+/// What we're doing is illustrated by this:
+/// ```
+/// match (true, 0) {
+///     (true, 0) => {}
+///     (_, 1) => {}
+///     (true | false, 0 | 1) => {}
+/// }
+/// ```
+/// When we try the alternatives of the `true | false` or-pattern, the last `0` is reachable in the
+/// `false` alternative but not the `true`. So overall it is reachable. By contrast, the last `1`
+/// is not reachable in either alternative, so we want to signal this to the user.
+/// Therefore we take the union of sets of reachable patterns coming from different alternatives in
+/// order to figure out which subpatterns are overall reachable.
+///
+/// Invariant: we try to construct the smallest representation we can. In particular if
+/// `self.is_empty()` we ensure that `self` is `Empty`, and same with `Full`. This is not important
+/// for correctness currently.
+#[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 { subpats: s_set }, Seq { subpats: mut o_set }) => {
+                s_set.retain(|i, s_sub_set| {
+                    // Missing entries count as full.
+                    let o_sub_set = o_set.remove(i).unwrap_or(Full);
+                    s_sub_set.union(o_sub_set);
+                    // We drop full entries.
+                    !s_sub_set.is_full()
+                });
+                // Everything left in `o_set` is missing from `s_set`, i.e. counts as full. Since
+                // unioning with full returns full, we can drop those entries.
+            }
+            (Alt { subpats: s_set, .. }, Alt { subpats: mut o_set, .. }) => {
+                s_set.retain(|i, s_sub_set| {
+                    // Missing entries count as empty.
+                    let o_sub_set = o_set.remove(i).unwrap_or(Empty);
+                    s_sub_set.union(o_sub_set);
+                    // We drop empty entries.
+                    !s_sub_set.is_empty()
+                });
+                // Everything left in `o_set` is missing from `s_set`, i.e. counts as empty. Since
+                // unioning with empty changes nothing, we can take those entries as is.
+                s_set.extend(o_set);
+            }
+            _ => panic!("bug"),
+        }
+
+        if self.is_full() {
+            *self = Full;
+        }
+    }
+
+    /// Returns a list of the unreachable subpatterns. If `self` is empty (i.e. the
+    /// whole pattern is unreachable) we return `None`.
+    fn list_unreachable_subpatterns(&self, cx: &MatchCheckCtx<'_>) -> Option<Vec<PatId>> {
+        /// Panics if `set.is_empty()`.
+        fn fill_subpats(
+            set: &SubPatSet,
+            unreachable_pats: &mut Vec<PatId>,
+            cx: &MatchCheckCtx<'_>,
+        ) {
+            match set {
+                SubPatSet::Empty => panic!("bug"),
+                SubPatSet::Full => {}
+                SubPatSet::Seq { subpats } => {
+                    for sub_set in subpats.values() {
+                        fill_subpats(sub_set, unreachable_pats, cx);
+                    }
+                }
+                SubPatSet::Alt { subpats, pat, alt_count, .. } => {
+                    let expanded = pat.expand_or_pat(cx);
+                    for (i, &expanded) in expanded.iter().enumerate().take(*alt_count) {
+                        let sub_set = subpats.get(&i).unwrap_or(&SubPatSet::Empty);
+                        if sub_set.is_empty() {
+                            // Found an unreachable subpattern.
+                            unreachable_pats.push(expanded);
+                        } else {
+                            fill_subpats(sub_set, unreachable_pats, cx);
+                        }
+                    }
+                }
+            }
+        }
+
+        if self.is_empty() {
+            return None;
+        }
+        if self.is_full() {
+            // No subpatterns are unreachable.
+            return Some(Vec::new());
+        }
+        let mut unreachable_pats = Vec::new();
+        fill_subpats(self, &mut unreachable_pats, cx);
+        Some(unreachable_pats)
+    }
+
+    /// 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 } => {
+                // We gather the first `arity` subpatterns together and shift the remaining ones.
+                let mut new_subpats = FxHashMap::default();
+                let mut new_subpats_first_col = FxHashMap::default();
+                for (i, sub_set) in subpats {
+                    if i < arity {
+                        // The first `arity` indices are now part of the pattern in the first
+                        // column.
+                        new_subpats_first_col.insert(i, sub_set);
+                    } else {
+                        // Indices after `arity` are simply shifted
+                        new_subpats.insert(i - arity + 1, sub_set);
+                    }
+                }
+                // If `new_subpats_first_col` has no entries it counts as full, so we can omit it.
+                if !new_subpats_first_col.is_empty() {
+                    new_subpats.insert(0, Seq { subpats: new_subpats_first_col });
+                }
+                Seq { subpats: new_subpats }
+            }
+            Alt { .. } => panic!("bug"), // `self` is a patstack
+        }
+    }
+
+    /// 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 {
+        use SubPatSet::*;
+        if self.is_empty() {
+            return Empty;
+        }
+
+        // Subpatterns coming from inside the or-pattern alternative itself, e.g. in `None | Some(0
+        // | 1)`.
+        let set_first_col = match &mut self {
+            Full => Full,
+            Seq { subpats } => subpats.remove(&0).unwrap_or(Full),
+            Empty => unreachable!(),
+            Alt { .. } => panic!("bug"), // `self` is a patstack
+        };
+        let mut subpats_first_col = FxHashMap::default();
+        subpats_first_col.insert(alt_id, set_first_col);
+        let set_first_col = Alt { subpats: subpats_first_col, pat, alt_count };
+
+        let mut subpats = match self {
+            Full => FxHashMap::default(),
+            Seq { subpats } => subpats,
+            Empty => unreachable!(),
+            Alt { .. } => panic!("bug"), // `self` is a patstack
+        };
+        subpats.insert(0, set_first_col);
+        Seq { subpats }
+    }
+}
+
 /// 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 `ArmType`.
-enum Usefulness<'p> {
-    /// If we don't care about witnesses, simply remember if the pattern was useful.
-    NoWitnesses { useful: bool },
+/// 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<'p>>),
+    WithWitnesses(Vec<Witness>),
 }
 
-impl<'p> Usefulness<'p> {
-    fn new_useful(preference: ArmType) -> Self {
+impl Usefulness {
+    fn new_useful(preference: WitnessPreference) -> Self {
         match preference {
-            // A single (empty) witness of reachability.
-            FakeExtraWildcard => WithWitnesses(vec![Witness(vec![])]),
-            RealArm => NoWitnesses { useful: true },
+            ConstructWitness => WithWitnesses(vec![Witness(vec![])]),
+            LeaveOutWitness => NoWitnesses(SubPatSet::full()),
         }
     }
-    fn new_not_useful(preference: ArmType) -> Self {
+    fn new_not_useful(preference: WitnessPreference) -> Self {
         match preference {
-            FakeExtraWildcard => WithWitnesses(vec![]),
-            RealArm => NoWitnesses { useful: false },
-        }
-    }
-
-    fn is_useful(&self) -> bool {
-        match self {
-            Usefulness::NoWitnesses { useful } => *useful,
-            Usefulness::WithWitnesses(witnesses) => !witnesses.is_empty(),
+            ConstructWitness => WithWitnesses(vec![]),
+            LeaveOutWitness => NoWitnesses(SubPatSet::empty()),
         }
     }
 
@@ -469,96 +823,89 @@ impl<'p> Usefulness<'p> {
             (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 { useful: s_useful }, NoWitnesses { useful: o_useful }) => {
-                *s_useful = *s_useful || o_useful
-            }
+            (NoWitnesses(s), NoWitnesses(o)) => s.union(o),
             _ => unreachable!(),
         }
     }
 
-    /// After calculating usefulness after a specialization, call this to reconstruct a usefulness
+    /// 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<'_, 'p>,
-        matrix: &Matrix<'p>,
+        pcx: PatCtxt<'_>,
+        matrix: &Matrix,
         ctor: &Constructor,
+        ctor_wild_subpatterns: &Fields,
     ) -> Self {
         match self {
-            NoWitnesses { .. } => self,
-            WithWitnesses(ref witnesses) if witnesses.is_empty() => self,
+            WithWitnesses(witnesses) if witnesses.is_empty() => WithWitnesses(witnesses),
             WithWitnesses(witnesses) => {
-                let new_witnesses = if let Constructor::Missing { .. } = ctor {
-                    // We got the special `Missing` constructor, so each of the missing constructors
-                    // gives a new pattern that is not caught by the match. We list those patterns.
-                    let new_patterns = if pcx.is_non_exhaustive {
-                        // Here we don't want the user to try to list all variants, we want them to add
-                        // a wildcard, so we only suggest that.
-                        vec![DeconstructedPat::wildcard(pcx.ty.clone())]
-                    } else {
-                        let mut split_wildcard = SplitWildcard::new(pcx);
-                        split_wildcard.split(pcx, matrix.heads().map(DeconstructedPat::ctor));
-
-                        // This lets us know if we skipped any variants because they are marked
-                        // `doc(hidden)` or they are unstable feature gate (only stdlib types).
-                        let mut hide_variant_show_wild = false;
-                        // Construct for each missing constructor a "wild" version of this
-                        // constructor, that matches everything that can be built with
-                        // it. For example, if `ctor` is a `Constructor::Variant` for
-                        // `Option::Some`, we get the pattern `Some(_)`.
-                        let mut new: Vec<DeconstructedPat<'_>> = split_wildcard
-                            .iter_missing(pcx)
-                            .filter_map(|missing_ctor| {
-                                // Check if this variant is marked `doc(hidden)`
-                                if missing_ctor.is_doc_hidden_variant(pcx)
-                                    || missing_ctor.is_unstable_variant(pcx)
-                                {
-                                    hide_variant_show_wild = true;
-                                    return None;
-                                }
-                                Some(DeconstructedPat::wild_from_ctor(pcx, missing_ctor.clone()))
-                            })
-                            .collect();
-
-                        if hide_variant_show_wild {
-                            new.push(DeconstructedPat::wildcard(pcx.ty.clone()))
-                        }
-
-                        new
-                    };
-
+                let new_witnesses = if matches!(ctor, Constructor::Missing) {
+                    let mut split_wildcard = SplitWildcard::new(pcx);
+                    split_wildcard.split(pcx, matrix.head_ctors(pcx.cx));
+                    // Construct for each missing constructor a "wild" version of this
+                    // constructor, that matches everything that can be built with
+                    // it. For example, if `ctor` is a `Constructor::Variant` for
+                    // `Option::Some`, we get the pattern `Some(_)`.
+                    let new_patterns: Vec<_> = split_wildcard
+                        .iter_missing(pcx)
+                        .map(|missing_ctor| {
+                            Fields::wildcards(pcx, missing_ctor).apply(pcx, missing_ctor)
+                        })
+                        .collect();
                     witnesses
                         .into_iter()
                         .flat_map(|witness| {
                             new_patterns.iter().map(move |pat| {
-                                Witness(
-                                    witness
-                                        .0
-                                        .iter()
-                                        .chain(once(pat))
-                                        .map(DeconstructedPat::clone_and_forget_reachability)
-                                        .collect(),
-                                )
+                                let mut witness = witness.clone();
+                                witness.0.push(pat.clone());
+                                witness
                             })
                         })
                         .collect()
                 } else {
                     witnesses
                         .into_iter()
-                        .map(|witness| witness.apply_constructor(pcx, ctor))
+                        .map(|witness| witness.apply_constructor(pcx, ctor, ctor_wild_subpatterns))
                         .collect()
                 };
                 WithWitnesses(new_witnesses)
             }
+            NoWitnesses(subpats) => NoWitnesses(subpats.unspecialize(ctor_wild_subpatterns.len())),
         }
     }
 }
 
 #[derive(Copy, Clone, Debug)]
-enum ArmType {
-    FakeExtraWildcard,
-    RealArm,
+enum WitnessPreference {
+    ConstructWitness,
+    LeaveOutWitness,
 }
 
 /// A witness of non-exhaustiveness for error reporting, represented
@@ -594,11 +941,12 @@ enum ArmType {
 ///     `Witness(vec![Pair(Some(_), true)])`
 ///
 /// The final `Pair(Some(_), true)` is then the resulting witness.
-pub(crate) struct Witness<'p>(Vec<DeconstructedPat<'p>>);
+#[derive(Clone, Debug)]
+pub(crate) struct Witness(Vec<Pat>);
 
-impl<'p> Witness<'p> {
+impl Witness {
     /// Asserts that the witness contains a single pattern, and returns it.
-    fn single_pattern(self) -> DeconstructedPat<'p> {
+    fn single_pattern(self) -> Pat {
         assert_eq!(self.0.len(), 1);
         self.0.into_iter().next().unwrap()
     }
@@ -616,13 +964,17 @@ impl<'p> Witness<'p> {
     ///
     /// 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<'_, 'p>, ctor: &Constructor) -> Self {
+    fn apply_constructor(
+        mut self,
+        pcx: PatCtxt<'_>,
+        ctor: &Constructor,
+        ctor_wild_subpatterns: &Fields,
+    ) -> Self {
         let pat = {
             let len = self.0.len();
-            let arity = ctor.arity(pcx);
+            let arity = ctor_wild_subpatterns.len();
             let pats = self.0.drain((len - arity)..).rev();
-            let fields = Fields::from_iter(pcx.cx, pats);
-            DeconstructedPat::new(ctor.clone(), fields, pcx.ty.clone())
+            ctor_wild_subpatterns.replace_fields(pcx.cx, pats).apply(pcx, ctor)
         };
 
         self.0.push(pat);
@@ -653,14 +1005,14 @@ impl<'p> Witness<'p> {
 /// `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<'p>(
-    cx: &MatchCheckCtx<'_, 'p>,
-    matrix: &Matrix<'p>,
-    v: &PatStack<'p>,
-    witness_preference: ArmType,
+fn is_useful(
+    cx: &MatchCheckCtx<'_>,
+    matrix: &Matrix,
+    v: &PatStack,
+    witness_preference: WitnessPreference,
     is_under_guard: bool,
     is_top_level: bool,
-) -> Usefulness<'p> {
+) -> Usefulness {
     let Matrix { patterns: rows, .. } = matrix;
 
     // The base case. We are pattern-matching on () and the return value is
@@ -677,62 +1029,69 @@ fn is_useful<'p>(
         return ret;
     }
 
-    debug_assert!(rows.iter().all(|r| r.len() == v.len()));
+    assert!(rows.iter().all(|r| r.len() == v.len()));
 
-    let ty = v.head().ty();
-    let is_non_exhaustive = cx.is_foreign_non_exhaustive_enum(ty);
-    let pcx = PatCtxt { cx, ty, is_top_level, is_non_exhaustive };
+    // FIXME(Nadrieril): Hack to work around type normalization issues (see rust-lang/rust#72476).
+    let ty = matrix.heads().next().map_or(cx.type_of(v.head()), |r| cx.type_of(r));
+    let pcx = PatCtxt { cx, ty: &ty, is_top_level };
 
     // If the first pattern is an or-pattern, expand it.
-    let mut ret = Usefulness::new_not_useful(witness_preference);
-    if v.head().is_or_pat() {
+    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();
-        for v in v.expand_or_pat() {
+        let usefulnesses = vs.into_iter().enumerate().map(|(i, v)| {
             let usefulness = is_useful(cx, &matrix, &v, witness_preference, is_under_guard, false);
-            ret.extend(usefulness);
             // 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);
+                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();
-
-        // FIXME: implement `overlapping_range_endpoints` lint
+        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.heads().map(DeconstructedPat::ctor));
+        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;
-        for ctor in split_ctors {
+        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 spec_matrix = start_matrix.specialize_constructor(pcx, &ctor);
-            let v = v.pop_head_constructor(cx, &ctor);
+            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);
-            let usefulness = usefulness.apply_constructor(pcx, start_matrix, &ctor);
-
-            // FIXME: implement `non_exhaustive_omitted_patterns` lint
-
-            ret.extend(usefulness);
-        }
+            usefulness.apply_constructor(pcx, start_matrix, &ctor, &ctor_wild_subpatterns)
+        });
+        Usefulness::merge(witness_preference, usefulnesses)
     };
 
-    if ret.is_useful() {
-        v.head().set_reachable();
-    }
-
     ret
 }
 
 /// The arm of a match expression.
 #[derive(Clone, Copy)]
-pub(crate) struct MatchArm<'p> {
-    pub(crate) pat: &'p DeconstructedPat<'p>,
+pub(crate) struct MatchArm {
+    pub(crate) pat: PatId,
     pub(crate) has_guard: bool,
 }
 
@@ -742,19 +1101,18 @@ 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.
-    // FIXME: store ureachable subpattern IDs
-    Reachable,
+    Reachable(Vec<PatId>),
     /// The arm is unreachable.
     Unreachable,
 }
 
 /// The output of checking a match for exhaustiveness and arm reachability.
-pub(crate) struct UsefulnessReport<'p> {
+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<'p>, Reachability)>,
+    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<DeconstructedPat<'p>>,
+    pub(crate) non_exhaustiveness_witnesses: Vec<Pat>,
 }
 
 /// The entrypoint for the usefulness algorithm. Computes whether a match is exhaustive and which
@@ -762,41 +1120,53 @@ pub(crate) struct UsefulnessReport<'p> {
 ///
 /// Note: the input patterns must have been lowered through
 /// `check_match::MatchVisitor::lower_pattern`.
-pub(crate) fn compute_match_usefulness<'p>(
-    cx: &MatchCheckCtx<'_, 'p>,
-    arms: &[MatchArm<'p>],
-    scrut_ty: &Ty,
-) -> UsefulnessReport<'p> {
+pub(crate) fn compute_match_usefulness(
+    cx: &MatchCheckCtx<'_>,
+    arms: &[MatchArm],
+) -> UsefulnessReport {
     let mut matrix = Matrix::empty();
     let arm_usefulness = arms
         .iter()
         .copied()
         .map(|arm| {
             let v = PatStack::from_pattern(arm.pat);
-            is_useful(cx, &matrix, &v, RealArm, arm.has_guard, true);
+            let usefulness = is_useful(cx, &matrix, &v, LeaveOutWitness, arm.has_guard, true);
             if !arm.has_guard {
-                matrix.push(v);
+                matrix.push(v, cx);
             }
-            let reachability = if arm.pat.is_reachable() {
-                Reachability::Reachable
-            } else {
-                Reachability::Unreachable
+            let reachability = match usefulness {
+                NoWitnesses(subpats) if subpats.is_empty() => Reachability::Unreachable,
+                NoWitnesses(subpats) => {
+                    Reachability::Reachable(subpats.list_unreachable_subpatterns(cx).unwrap())
+                }
+                WithWitnesses(..) => panic!("bug"),
             };
             (arm, reachability)
         })
         .collect();
 
-    let wild_pattern = cx.pattern_arena.alloc(DeconstructedPat::wildcard(scrut_ty.clone()));
+    let wild_pattern =
+        cx.pattern_arena.borrow_mut().alloc(Pat::wildcard_from_ty(cx.infer[cx.match_expr].clone()));
     let v = PatStack::from_pattern(wild_pattern);
-    let usefulness = is_useful(cx, &matrix, &v, FakeExtraWildcard, false, true);
+    let usefulness = is_useful(cx, &matrix, &v, ConstructWitness, false, true);
     let non_exhaustiveness_witnesses = match usefulness {
         WithWitnesses(pats) => pats.into_iter().map(Witness::single_pattern).collect(),
-        NoWitnesses { .. } => panic!("bug"),
+        NoWitnesses(_) => panic!("bug"),
     };
     UsefulnessReport { _arm_usefulness: arm_usefulness, non_exhaustiveness_witnesses }
 }
 
-pub(crate) mod helper {
+pub(crate) type PatternArena = Arena<Pat>;
+
+mod helper {
+    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.
diff --git a/crates/hir_ty/src/infer.rs b/crates/hir_ty/src/infer.rs
index a6c91f9d27..1bc19323da 100644
--- a/crates/hir_ty/src/infer.rs
+++ b/crates/hir_ty/src/infer.rs
@@ -16,7 +16,7 @@
 use std::ops::Index;
 use std::sync::Arc;
 
-use chalk_ir::{cast::Cast, DebruijnIndex, Mutability, Safety, Scalar, TypeFlags};
+use chalk_ir::{cast::Cast, DebruijnIndex, Mutability, Safety, Scalar};
 use hir_def::{
     body::Body,
     data::{ConstData, FunctionData, StaticData},
@@ -70,26 +70,6 @@ pub(crate) fn infer_query(db: &dyn HirDatabase, def: DefWithBodyId) -> Arc<Infer
     Arc::new(ctx.resolve_all())
 }
 
-/// Fully normalize all the types found within `ty` in context of `owner` body definition.
-///
-/// This is appropriate to use only after type-check: it assumes
-/// that normalization will succeed, for example.
-pub(crate) fn normalize(db: &dyn HirDatabase, owner: DefWithBodyId, ty: Ty) -> Ty {
-    if !ty.data(Interner).flags.intersects(TypeFlags::HAS_PROJECTION) {
-        return ty;
-    }
-    let krate = owner.module(db.upcast()).krate();
-    let trait_env = owner
-        .as_generic_def_id()
-        .map_or_else(|| Arc::new(TraitEnvironment::empty(krate)), |d| db.trait_environment(d));
-    let mut table = unify::InferenceTable::new(db, trait_env.clone());
-
-    let ty_with_vars = table.normalize_associated_types_in(ty);
-    table.resolve_obligations_as_possible();
-    table.propagate_diverging_flag();
-    table.resolve_completely(ty_with_vars)
-}
-
 #[derive(Debug, Copy, Clone, Hash, PartialEq, Eq)]
 enum ExprOrPatId {
     ExprId(ExprId),
@@ -100,7 +80,7 @@ impl_from!(ExprId, PatId for ExprOrPatId);
 /// Binding modes inferred for patterns.
 /// <https://doc.rust-lang.org/reference/patterns.html#binding-modes>
 #[derive(Copy, Clone, Debug, Eq, PartialEq)]
-pub enum BindingMode {
+enum BindingMode {
     Move,
     Ref(Mutability),
 }
@@ -292,7 +272,6 @@ pub struct InferenceResult {
     standard_types: InternedStandardTypes,
     /// Stores the types which were implicitly dereferenced in pattern binding modes.
     pub pat_adjustments: FxHashMap<PatId, Vec<Adjustment>>,
-    pub pat_binding_modes: FxHashMap<PatId, BindingMode>,
     pub expr_adjustments: FxHashMap<ExprId, Vec<Adjustment>>,
 }
 
@@ -718,7 +697,7 @@ impl<'a> InferenceContext<'a> {
         let ctx = crate::lower::TyLoweringContext::new(self.db, &self.resolver)
             .with_impl_trait_mode(ImplTraitLoweringMode::Param);
         let param_tys =
-            data.params.iter().map(|(_, type_ref)| ctx.lower_ty(type_ref)).collect::<Vec<_>>();
+            data.params.iter().map(|type_ref| ctx.lower_ty(type_ref)).collect::<Vec<_>>();
         for (ty, pat) in param_tys.into_iter().zip(body.params.iter()) {
             let ty = self.insert_type_vars(ty);
             let ty = self.normalize_associated_types_in(ty);
diff --git a/crates/hir_ty/src/infer/pat.rs b/crates/hir_ty/src/infer/pat.rs
index 50fd2dd749..64e72abf0f 100644
--- a/crates/hir_ty/src/infer/pat.rs
+++ b/crates/hir_ty/src/infer/pat.rs
@@ -204,8 +204,6 @@ impl<'a> InferenceContext<'a> {
                 } else {
                     BindingMode::convert(*mode)
                 };
-                self.result.pat_binding_modes.insert(pat, mode);
-
                 let inner_ty = match subpat {
                     Some(subpat) => self.infer_pat(*subpat, &expected, default_bm),
                     None => expected,
diff --git a/crates/hir_ty/src/lower.rs b/crates/hir_ty/src/lower.rs
index a450f6c75c..a22d15dd81 100644
--- a/crates/hir_ty/src/lower.rs
+++ b/crates/hir_ty/src/lower.rs
@@ -1278,7 +1278,7 @@ fn fn_sig_for_fn(db: &dyn HirDatabase, def: FunctionId) -> PolyFnSig {
     let ctx_params = TyLoweringContext::new(db, &resolver)
         .with_impl_trait_mode(ImplTraitLoweringMode::Variable)
         .with_type_param_mode(TypeParamLoweringMode::Variable);
-    let params = data.params.iter().map(|(_, tr)| ctx_params.lower_ty(tr)).collect::<Vec<_>>();
+    let params = data.params.iter().map(|tr| ctx_params.lower_ty(tr)).collect::<Vec<_>>();
     let ctx_ret = TyLoweringContext::new(db, &resolver)
         .with_impl_trait_mode(ImplTraitLoweringMode::Opaque)
         .with_type_param_mode(TypeParamLoweringMode::Variable);
diff --git a/crates/ide/Cargo.toml b/crates/ide/Cargo.toml
index c5e79838fc..0f3311cb71 100644
--- a/crates/ide/Cargo.toml
+++ b/crates/ide/Cargo.toml
@@ -4,7 +4,7 @@ version = "0.0.0"
 description = "TBD"
 license = "MIT OR Apache-2.0"
 edition = "2021"
-rust-version = "1.57"
+rust-version = "1.56"
 
 [lib]
 doctest = false
diff --git a/crates/ide/src/highlight_related.rs b/crates/ide/src/highlight_related.rs
index de6afaef8e..054b8f297b 100644
--- a/crates/ide/src/highlight_related.rs
+++ b/crates/ide/src/highlight_related.rs
@@ -378,7 +378,22 @@ struct Foo;
     fn test_hl_self_in_crate_root() {
         check(
             r#"
-use self$0;
+use crate$0;
+  //^^^^^
+use self;
+  //^^^^
+mod __ {
+    use super;
+      //^^^^^
+}
+"#,
+        );
+        check(
+            r#"
+//- /main.rs crate:main deps:lib
+use lib$0;
+  //^^^
+//- /lib.rs crate:lib
 "#,
         );
     }
diff --git a/crates/ide/src/references.rs b/crates/ide/src/references.rs
index c5fe7d30c9..949c6dc686 100644
--- a/crates/ide/src/references.rs
+++ b/crates/ide/src/references.rs
@@ -756,7 +756,7 @@ use self$0;
             expect![[r#"
                 Module FileId(0) 0..10
 
-                (no references)
+                FileId(0) 4..8
             "#]],
         );
     }
diff --git a/crates/ide_assists/Cargo.toml b/crates/ide_assists/Cargo.toml
index 878c556d77..3cd186fdf5 100644
--- a/crates/ide_assists/Cargo.toml
+++ b/crates/ide_assists/Cargo.toml
@@ -4,7 +4,7 @@ version = "0.0.0"
 description = "TBD"
 license = "MIT OR Apache-2.0"
 edition = "2021"
-rust-version = "1.57"
+rust-version = "1.56"
 
 [lib]
 doctest = false
diff --git a/crates/ide_completion/Cargo.toml b/crates/ide_completion/Cargo.toml
index 5d8cad4389..f9ce03bce2 100644
--- a/crates/ide_completion/Cargo.toml
+++ b/crates/ide_completion/Cargo.toml
@@ -4,7 +4,7 @@ version = "0.0.0"
 description = "TBD"
 license = "MIT OR Apache-2.0"
 edition = "2021"
-rust-version = "1.57"
+rust-version = "1.56"
 
 [lib]
 doctest = false
diff --git a/crates/ide_completion/src/render/builder_ext.rs b/crates/ide_completion/src/render/builder_ext.rs
index 8f8bd1dfcd..4d04054445 100644
--- a/crates/ide_completion/src/render/builder_ext.rs
+++ b/crates/ide_completion/src/render/builder_ext.rs
@@ -1,19 +1,21 @@
 //! Extensions for `Builder` structure required for item rendering.
 
+use either::Either;
 use itertools::Itertools;
+use syntax::ast::{self, HasName};
 
 use crate::{context::PathKind, item::Builder, patterns::ImmediateLocation, CompletionContext};
 
 #[derive(Debug)]
 pub(super) enum Params {
-    Named(Option<hir::SelfParam>, Vec<hir::Param>),
+    Named(Vec<(Either<ast::SelfParam, ast::Param>, hir::Param)>),
     Anonymous(usize),
 }
 
 impl Params {
     pub(super) fn len(&self) -> usize {
         match self {
-            Params::Named(selv, params) => params.len() + if selv.is_some() { 1 } else { 0 },
+            Params::Named(xs) => xs.len(),
             Params::Anonymous(len) => *len,
         }
     }
@@ -75,34 +77,48 @@ impl Builder {
         } else {
             self.trigger_call_info();
             let snippet = match (ctx.config.add_call_argument_snippets, params) {
-                (true, Params::Named(self_param, params)) => {
-                    let offset = if self_param.is_some() { 2 } else { 1 };
+                (true, Params::Named(params)) => {
                     let function_params_snippet = params.iter().enumerate().format_with(
                         ", ",
-                        |(index, param), f| match param.name(ctx.db) {
-                            Some(n) => {
-                                let smol_str = n.to_smol_str();
-                                let text = smol_str.as_str().trim_start_matches('_');
-                                let ref_ = ref_of_param(ctx, text, param.ty());
-                                f(&format_args!("${{{}:{}{}}}", index + offset, ref_, text))
-                            }
-                            None => f(&format_args!("${{{}:_}}", index + offset,)),
+                        |(index, (param_source, param)), f| {
+                            let name;
+                            let text;
+                            let (ref_, name) = match param_source {
+                                Either::Left(self_param) => (
+                                    match self_param.kind() {
+                                        ast::SelfParamKind::Owned => "",
+                                        ast::SelfParamKind::Ref => "&",
+                                        ast::SelfParamKind::MutRef => "&mut ",
+                                    },
+                                    "self",
+                                ),
+                                Either::Right(it) => {
+                                    let n = (|| {
+                                        let mut pat = it.pat()?;
+                                        loop {
+                                            match pat {
+                                                ast::Pat::IdentPat(pat) => break pat.name(),
+                                                ast::Pat::RefPat(it) => pat = it.pat()?,
+                                                _ => return None,
+                                            }
+                                        }
+                                    })();
+                                    match n {
+                                        Some(n) => {
+                                            name = n;
+                                            text = name.text();
+                                            let text = text.as_str().trim_start_matches('_');
+                                            let ref_ = ref_of_param(ctx, text, param.ty());
+                                            (ref_, text)
+                                        }
+                                        None => ("", "_"),
+                                    }
+                                }
+                            };
+                            f(&format_args!("${{{}:{}{}}}", index + 1, ref_, name))
                         },
                     );
-                    match self_param {
-                        Some(self_param) => {
-                            format!(
-                                "{}(${{1:{}}}{}{})$0",
-                                name,
-                                self_param.display(ctx.db),
-                                if params.is_empty() { "" } else { ", " },
-                                function_params_snippet
-                            )
-                        }
-                        None => {
-                            format!("{}({})$0", name, function_params_snippet)
-                        }
-                    }
+                    format!("{}({})$0", name, function_params_snippet)
                 }
                 _ => {
                     cov_mark::hit!(suppress_arg_snippets);
diff --git a/crates/ide_completion/src/render/function.rs b/crates/ide_completion/src/render/function.rs
index 918210f2f3..86dfbf7fc8 100644
--- a/crates/ide_completion/src/render/function.rs
+++ b/crates/ide_completion/src/render/function.rs
@@ -1,9 +1,11 @@
 //! Renderer for function calls.
 
-use hir::{AsAssocItem, HirDisplay};
+use either::Either;
+use hir::{AsAssocItem, HasSource, HirDisplay};
 use ide_db::SymbolKind;
 use itertools::Itertools;
 use stdx::format_to;
+use syntax::ast;
 
 use crate::{
     item::{CompletionItem, CompletionItemKind, CompletionRelevance, ImportEdit},
@@ -40,6 +42,21 @@ struct FunctionRender<'a> {
     name: hir::Name,
     receiver: Option<hir::Name>,
     func: hir::Function,
+    /// NB: having `ast::Fn` here might or might not be a good idea. The problem
+    /// with it is that, to get an `ast::`, you want to parse the corresponding
+    /// source file. So, when flyimport completions suggest a bunch of
+    /// functions, we spend quite some time parsing many files.
+    ///
+    /// We need ast because we want to access parameter names (patterns). We can
+    /// add them to the hir of the function itself, but parameter names are not
+    /// something hir cares otherwise.
+    ///
+    /// Alternatively we can reconstruct params from the function body, but that
+    /// would require parsing anyway.
+    ///
+    /// It seems that just using `ast` is the best choice -- most of parses
+    /// should be cached anyway.
+    ast_node: ast::Fn,
     is_method: bool,
 }
 
@@ -52,8 +69,9 @@ impl<'a> FunctionRender<'a> {
         is_method: bool,
     ) -> Option<FunctionRender<'a>> {
         let name = local_name.unwrap_or_else(|| fn_.name(ctx.db()));
+        let ast_node = fn_.source(ctx.db())?.value;
 
-        Some(FunctionRender { ctx, name, receiver, func: fn_, is_method })
+        Some(FunctionRender { ctx, name, receiver, func: fn_, ast_node, is_method })
     }
 
     fn render(self, import_to_add: Option<ImportEdit>) -> CompletionItem {
@@ -134,20 +152,25 @@ impl<'a> FunctionRender<'a> {
     }
 
     fn params(&self) -> Params {
-        let (params, self_param) =
-            if self.ctx.completion.has_dot_receiver() || self.receiver.is_some() {
-                (self.func.method_params(self.ctx.db()).unwrap_or_default(), None)
-            } else {
-                let self_param = self.func.self_param(self.ctx.db());
-
-                let mut assoc_params = self.func.assoc_fn_params(self.ctx.db());
-                if self_param.is_some() {
-                    assoc_params.remove(0);
-                }
-                (assoc_params, self_param)
-            };
+        let ast_params = match self.ast_node.param_list() {
+            Some(it) => it,
+            None => return Params::Named(Vec::new()),
+        };
+        let params = ast_params.params().map(Either::Right);
+
+        let params = if self.ctx.completion.has_dot_receiver() || self.receiver.is_some() {
+            params.zip(self.func.method_params(self.ctx.db()).unwrap_or_default()).collect()
+        } else {
+            ast_params
+                .self_param()
+                .map(Either::Left)
+                .into_iter()
+                .chain(params)
+                .zip(self.func.assoc_fn_params(self.ctx.db()))
+                .collect()
+        };
 
-        Params::Named(self_param, params)
+        Params::Named(params)
     }
 
     fn kind(&self) -> CompletionItemKind {
diff --git a/crates/ide_db/Cargo.toml b/crates/ide_db/Cargo.toml
index e00803708b..cfcf9f56c8 100644
--- a/crates/ide_db/Cargo.toml
+++ b/crates/ide_db/Cargo.toml
@@ -4,7 +4,7 @@ version = "0.0.0"
 description = "TBD"
 license = "MIT OR Apache-2.0"
 edition = "2021"
-rust-version = "1.57"
+rust-version = "1.56"
 
 [lib]
 doctest = false
diff --git a/crates/ide_db/src/defs.rs b/crates/ide_db/src/defs.rs
index b5a13cea91..30ebf7828a 100644
--- a/crates/ide_db/src/defs.rs
+++ b/crates/ide_db/src/defs.rs
@@ -224,93 +224,125 @@ impl NameClass {
 
         let parent = name.syntax().parent()?;
 
-        let def = if let Some(item) = ast::Item::cast(parent.clone()) {
-            match item {
-                ast::Item::MacroRules(it) => {
-                    Definition::Macro(sema.to_def(&ast::Macro::MacroRules(it))?)
-                }
-                ast::Item::MacroDef(it) => {
-                    Definition::Macro(sema.to_def(&ast::Macro::MacroDef(it))?)
-                }
-                ast::Item::Const(it) => Definition::Const(sema.to_def(&it)?),
-                ast::Item::Fn(it) => Definition::Function(sema.to_def(&it)?),
-                ast::Item::Module(it) => Definition::Module(sema.to_def(&it)?),
-                ast::Item::Static(it) => Definition::Static(sema.to_def(&it)?),
-                ast::Item::Trait(it) => Definition::Trait(sema.to_def(&it)?),
-                ast::Item::TypeAlias(it) => Definition::TypeAlias(sema.to_def(&it)?),
-                ast::Item::Enum(it) => Definition::Adt(hir::Adt::Enum(sema.to_def(&it)?)),
-                ast::Item::Struct(it) => Definition::Adt(hir::Adt::Struct(sema.to_def(&it)?)),
-                ast::Item::Union(it) => Definition::Adt(hir::Adt::Union(sema.to_def(&it)?)),
-                _ => return None,
-            }
-        } else if let Some(it) = ast::IdentPat::cast(parent.clone()) {
-            if let Some(def) = sema.resolve_bind_pat_to_const(&it) {
+        if let Some(bind_pat) = ast::IdentPat::cast(parent.clone()) {
+            if let Some(def) = sema.resolve_bind_pat_to_const(&bind_pat) {
                 return Some(NameClass::ConstReference(Definition::from(def)));
             }
+        }
 
-            let local = sema.to_def(&it)?;
-            let pat_parent = it.syntax().parent();
-            if let Some(record_pat_field) = pat_parent.and_then(ast::RecordPatField::cast) {
-                if record_pat_field.name_ref().is_none() {
-                    if let Some(field) = sema.resolve_record_pat_field(&record_pat_field) {
-                        return Some(NameClass::PatFieldShorthand {
-                            local_def: local,
-                            field_ref: field,
-                        });
-                    }
-                }
-            }
+        match_ast! {
+            match parent {
+                ast::Rename(it) => {
+                    if let Some(use_tree) = it.syntax().parent().and_then(ast::UseTree::cast) {
+                        let path = use_tree.path()?;
+                        let path_segment = path.segment()?;
+                        let name_ref = path_segment.name_ref()?;
+                        let name_ref = if name_ref.self_token().is_some() {
+                             use_tree
+                                .syntax()
+                                .parent()
+                                .as_ref()
+                                // Skip over UseTreeList
+                                .and_then(|it| {
+                                    let use_tree = it.parent().and_then(ast::UseTree::cast)?;
+                                    let path = use_tree.path()?;
+                                    let path_segment = path.segment()?;
+                                    path_segment.name_ref()
+                                }).unwrap_or(name_ref)
+                        } else {
+                            name_ref
+                        };
+                        let name_ref_class = NameRefClass::classify(sema, &name_ref)?;
 
-            Definition::Local(local)
-        } else if let Some(it) = ast::Rename::cast(parent.clone()) {
-            if let Some(use_tree) = it.syntax().parent().and_then(ast::UseTree::cast) {
-                let path = use_tree.path()?;
-                let path_segment = path.segment()?;
-                let name_ref = path_segment.name_ref()?;
-                let name_ref = if name_ref.self_token().is_some() {
-                    use_tree
-                        .syntax()
-                        .parent()
-                        .as_ref()
-                        // Skip over UseTreeList
-                        .and_then(|it| {
-                            let use_tree = it.parent().and_then(ast::UseTree::cast)?;
-                            let path = use_tree.path()?;
-                            let path_segment = path.segment()?;
-                            path_segment.name_ref()
-                        })
-                        .unwrap_or(name_ref)
-                } else {
-                    name_ref
-                };
-                let name_ref_class = NameRefClass::classify(sema, &name_ref)?;
+                        Some(NameClass::Definition(match name_ref_class {
+                            NameRefClass::Definition(def) => def,
+                            NameRefClass::FieldShorthand { local_ref: _, field_ref } => {
+                                Definition::Field(field_ref)
+                            }
+                        }))
+                    } else {
+                        let extern_crate = it.syntax().parent().and_then(ast::ExternCrate::cast)?;
+                        let krate = sema.resolve_extern_crate(&extern_crate)?;
+                        let root_module = krate.root_module(sema.db);
+                        Some(NameClass::Definition(Definition::Module(root_module)))
+                    }
+                },
+                ast::IdentPat(it) => {
+                    let local = sema.to_def(&it)?;
 
-                match name_ref_class {
-                    NameRefClass::Definition(def) => def,
-                    NameRefClass::FieldShorthand { local_ref: _, field_ref } => {
-                        Definition::Field(field_ref)
+                    if let Some(record_pat_field) = it.syntax().parent().and_then(ast::RecordPatField::cast) {
+                        if record_pat_field.name_ref().is_none() {
+                            if let Some(field) = sema.resolve_record_pat_field(&record_pat_field) {
+                                return Some(NameClass::PatFieldShorthand { local_def: local, field_ref: field });
+                            }
+                        }
                     }
-                }
-            } else {
-                let extern_crate = it.syntax().parent().and_then(ast::ExternCrate::cast)?;
-                let krate = sema.resolve_extern_crate(&extern_crate)?;
-                let root_module = krate.root_module(sema.db);
-                Definition::Module(root_module)
-            }
-        } else {
-            match_ast! {
-                match parent {
-                    ast::SelfParam(it) => Definition::Local(sema.to_def(&it)?),
-                    ast::RecordField(it) => Definition::Field(sema.to_def(&it)?),
-                    ast::Variant(it) => Definition::Variant(sema.to_def(&it)?),
-                    ast::TypeParam(it) => Definition::GenericParam(sema.to_def(&it)?.into()),
-                    ast::ConstParam(it) => Definition::GenericParam(sema.to_def(&it)?.into()),
-                    _ => return None,
-                }
-            }
-        };
 
-        Some(NameClass::Definition(def))
+                    Some(NameClass::Definition(Definition::Local(local)))
+                },
+                ast::SelfParam(it) => {
+                    let def = sema.to_def(&it)?;
+                    Some(NameClass::Definition(Definition::Local(def)))
+                },
+                ast::RecordField(it) => {
+                    let field: hir::Field = sema.to_def(&it)?;
+                    Some(NameClass::Definition(Definition::Field(field)))
+                },
+                ast::Module(it) => {
+                    let def = sema.to_def(&it)?;
+                    Some(NameClass::Definition(Definition::Module(def)))
+                },
+                ast::Struct(it) => {
+                    let def: hir::Struct = sema.to_def(&it)?;
+                    Some(NameClass::Definition(Definition::Adt(def.into())))
+                },
+                ast::Union(it) => {
+                    let def: hir::Union = sema.to_def(&it)?;
+                    Some(NameClass::Definition(Definition::Adt(def.into())))
+                },
+                ast::Enum(it) => {
+                    let def: hir::Enum = sema.to_def(&it)?;
+                    Some(NameClass::Definition(Definition::Adt(def.into())))
+                },
+                ast::Trait(it) => {
+                    let def: hir::Trait = sema.to_def(&it)?;
+                    Some(NameClass::Definition(Definition::Trait(def)))
+                },
+                ast::Static(it) => {
+                    let def: hir::Static = sema.to_def(&it)?;
+                    Some(NameClass::Definition(Definition::Static(def)))
+                },
+                ast::Variant(it) => {
+                    let def: hir::Variant = sema.to_def(&it)?;
+                    Some(NameClass::Definition(Definition::Variant(def)))
+                },
+                ast::Fn(it) => {
+                    let def: hir::Function = sema.to_def(&it)?;
+                    Some(NameClass::Definition(Definition::Function(def)))
+                },
+                ast::Const(it) => {
+                    let def: hir::Const = sema.to_def(&it)?;
+                    Some(NameClass::Definition(Definition::Const(def)))
+                },
+                ast::TypeAlias(it) => {
+                    let def: hir::TypeAlias = sema.to_def(&it)?;
+                    Some(NameClass::Definition(Definition::TypeAlias(def)))
+                },
+                ast::Macro(it) => {
+                    let def = sema.to_def(&it)?;
+                    Some(NameClass::Definition(Definition::Macro(def)))
+                },
+                ast::TypeParam(it) => {
+                    let def = sema.to_def(&it)?;
+                    Some(NameClass::Definition(Definition::GenericParam(def.into())))
+                },
+                ast::ConstParam(it) => {
+                    let def = sema.to_def(&it)?;
+                    Some(NameClass::Definition(Definition::GenericParam(def.into())))
+                },
+                _ => None,
+            }
+        }
     }
 
     pub fn classify_lifetime(
diff --git a/crates/ide_db/src/search.rs b/crates/ide_db/src/search.rs
index 0d0f7b78d8..dcfc2b7bfc 100644
--- a/crates/ide_db/src/search.rs
+++ b/crates/ide_db/src/search.rs
@@ -4,7 +4,7 @@
 //! get a super-set of matches. Then, we we confirm each match using precise
 //! name resolution.
 
-use std::{convert::TryInto, mem};
+use std::{convert::TryInto, mem, sync::Arc};
 
 use base_db::{FileId, FileRange, SourceDatabase, SourceDatabaseExt};
 use hir::{
@@ -376,32 +376,63 @@ impl<'a> FindUsages<'a> {
             }
         };
 
-        let name = self.def.name(sema.db).or_else(|| {
-            self.include_self_kw_refs.as_ref().and_then(|ty| {
-                ty.as_adt()
-                    .map(|adt| adt.name(self.sema.db))
-                    .or_else(|| ty.as_builtin().map(|builtin| builtin.name()))
-            })
-        });
-        let name = match name {
-            Some(name) => name.to_smol_str(),
+        let name = match self.def {
+            // special case crate modules as these do not have a proper name
+            Definition::Module(module) if module.crate_root(self.sema.db) == module => {
+                // FIXME: This assumes the crate name is always equal to its display name when it really isn't
+                module
+                    .krate()
+                    .display_name(self.sema.db)
+                    .map(|crate_name| crate_name.crate_name().as_smol_str().clone())
+            }
+            _ => {
+                let self_kw_refs = || {
+                    self.include_self_kw_refs.as_ref().and_then(|ty| {
+                        ty.as_adt()
+                            .map(|adt| adt.name(self.sema.db))
+                            .or_else(|| ty.as_builtin().map(|builtin| builtin.name()))
+                    })
+                };
+                self.def.name(sema.db).or_else(self_kw_refs).map(|it| it.to_smol_str())
+            }
+        };
+        let name = match &name {
+            Some(s) => s.as_str(),
             None => return,
         };
-        let name = name.as_str();
-
-        for (file_id, search_range) in search_scope {
-            let text = sema.db.file_text(file_id);
-            let search_range =
-                search_range.unwrap_or_else(|| TextRange::up_to(TextSize::of(text.as_str())));
-
-            let tree = Lazy::new(|| sema.parse(file_id).syntax().clone());
 
-            for (idx, _) in text.match_indices(name) {
+        // these can't be closures because rust infers the lifetimes wrong ...
+        fn match_indices<'a>(
+            text: &'a str,
+            name: &'a str,
+            search_range: TextRange,
+        ) -> impl Iterator<Item = TextSize> + 'a {
+            text.match_indices(name).filter_map(move |(idx, _)| {
                 let offset: TextSize = idx.try_into().unwrap();
                 if !search_range.contains_inclusive(offset) {
-                    continue;
+                    return None;
                 }
+                Some(offset)
+            })
+        }
+        fn scope_files<'a>(
+            sema: &'a Semantics<RootDatabase>,
+            scope: &'a SearchScope,
+        ) -> impl Iterator<Item = (Arc<String>, FileId, TextRange)> + 'a {
+            scope.entries.iter().map(|(&file_id, &search_range)| {
+                let text = sema.db.file_text(file_id);
+                let search_range =
+                    search_range.unwrap_or_else(|| TextRange::up_to(TextSize::of(text.as_str())));
+
+                (text, file_id, search_range)
+            })
+        }
+
+        for (text, file_id, search_range) in scope_files(sema, &search_scope) {
+            let tree = Lazy::new(move || sema.parse(file_id).syntax().clone());
 
+            // Search for occurrences of the items name
+            for offset in match_indices(&text, name, search_range) {
                 for name in sema.find_nodes_at_offset_with_descend(&tree, offset) {
                     if match name {
                         ast::NameLike::NameRef(name_ref) => self.found_name_ref(&name_ref, sink),
@@ -412,13 +443,9 @@ impl<'a> FindUsages<'a> {
                     }
                 }
             }
+            // Search for occurrences of the `Self` referring to our type
             if let Some(self_ty) = &self.include_self_kw_refs {
-                for (idx, _) in text.match_indices("Self") {
-                    let offset: TextSize = idx.try_into().unwrap();
-                    if !search_range.contains_inclusive(offset) {
-                        continue;
-                    }
-
+                for offset in match_indices(&text, "Self", search_range) {
                     for name_ref in sema.find_nodes_at_offset_with_descend(&tree, offset) {
                         if self.found_self_ty_name_ref(self_ty, &name_ref, sink) {
                             return;
@@ -428,6 +455,37 @@ impl<'a> FindUsages<'a> {
             }
         }
 
+        // Search for `super` and `crate` resolving to our module
+        match self.def {
+            Definition::Module(module) => {
+                let scope = search_scope.intersection(&SearchScope::module(self.sema.db, module));
+
+                let is_crate_root = module.crate_root(self.sema.db) == module;
+
+                for (text, file_id, search_range) in scope_files(sema, &scope) {
+                    let tree = Lazy::new(move || sema.parse(file_id).syntax().clone());
+
+                    for offset in match_indices(&text, "super", search_range) {
+                        for name_ref in sema.find_nodes_at_offset_with_descend(&tree, offset) {
+                            if self.found_name_ref(&name_ref, sink) {
+                                return;
+                            }
+                        }
+                    }
+                    if is_crate_root {
+                        for offset in match_indices(&text, "crate", search_range) {
+                            for name_ref in sema.find_nodes_at_offset_with_descend(&tree, offset) {
+                                if self.found_name_ref(&name_ref, sink) {
+                                    return;
+                                }
+                            }
+                        }
+                    }
+                }
+            }
+            _ => (),
+        }
+
         // search for module `self` references in our module's definition source
         match self.def {
             Definition::Module(module) if self.search_self_mod => {
@@ -439,18 +497,25 @@ impl<'a> FindUsages<'a> {
                     ModuleSource::SourceFile(_) => (file_id, None),
                 };
 
+                let search_range = if let Some(&range) = search_scope.entries.get(&file_id) {
+                    match (range, search_range) {
+                        (None, range) | (range, None) => range,
+                        (Some(range), Some(search_range)) => match range.intersect(search_range) {
+                            Some(range) => Some(range),
+                            None => return,
+                        },
+                    }
+                } else {
+                    return;
+                };
+
                 let text = sema.db.file_text(file_id);
                 let search_range =
                     search_range.unwrap_or_else(|| TextRange::up_to(TextSize::of(text.as_str())));
 
                 let tree = Lazy::new(|| sema.parse(file_id).syntax().clone());
 
-                for (idx, _) in text.match_indices("self") {
-                    let offset: TextSize = idx.try_into().unwrap();
-                    if !search_range.contains_inclusive(offset) {
-                        continue;
-                    }
-
+                for offset in match_indices(&text, "self", search_range) {
                     for name_ref in sema.find_nodes_at_offset_with_descend(&tree, offset) {
                         if self.found_self_module_name_ref(&name_ref, sink) {
                             return;
diff --git a/crates/ide_diagnostics/Cargo.toml b/crates/ide_diagnostics/Cargo.toml
index ba926c3719..160293c7da 100644
--- a/crates/ide_diagnostics/Cargo.toml
+++ b/crates/ide_diagnostics/Cargo.toml
@@ -4,7 +4,7 @@ version = "0.0.0"
 description = "TBD"
 license = "MIT OR Apache-2.0"
 edition = "2021"
-rust-version = "1.57"
+rust-version = "1.56"
 
 [lib]
 doctest = false
diff --git a/crates/ide_diagnostics/src/handlers/missing_match_arms.rs b/crates/ide_diagnostics/src/handlers/missing_match_arms.rs
index 6e2764e59f..947b0f2e2e 100644
--- a/crates/ide_diagnostics/src/handlers/missing_match_arms.rs
+++ b/crates/ide_diagnostics/src/handlers/missing_match_arms.rs
@@ -821,6 +821,7 @@ fn main() {
 
     #[test]
     fn pattern_type_is_of_substitution() {
+        cov_mark::check!(match_check_wildcard_expanded_to_substitutions);
         check_diagnostics_no_bails(
             r#"
 struct Foo<T>(T);
@@ -863,43 +864,6 @@ fn main() {
         );
     }
 
-    #[test]
-    fn normalize_field_ty() {
-        check_diagnostics_no_bails(
-            r"
-trait Trait { type Projection; }
-enum E {Foo, Bar}
-struct A;
-impl Trait for A { type Projection = E; }
-struct Next<T: Trait>(T::Projection);
-static __: () = {
-    let n: Next<A> = Next(E::Foo);
-    match n { Next(E::Foo) => {} }
-    //    ^ error: missing match arm
-    match n { Next(E::Foo | E::Bar) => {} }
-    match n { Next(E::Foo | _     ) => {} }
-    match n { Next(_      | E::Bar) => {} }
-    match n {      _ | Next(E::Bar) => {} }
-    match &n { Next(E::Foo | E::Bar) => {} }
-    match &n {      _ | Next(E::Bar) => {} }
-};",
-        );
-    }
-
-    #[test]
-    fn binding_mode_by_ref() {
-        check_diagnostics_no_bails(
-            r"
-enum E{ A, B }
-fn foo() {
-    match &E::A {
-        E::A => {}
-        x => {}
-    }
-}",
-        );
-    }
-
     mod false_negatives {
         //! The implementation of match checking here is a work in progress. As we roll this out, we
         //! prefer false negatives to false positives (ideally there would be no false positives). This
diff --git a/crates/ide_ssr/Cargo.toml b/crates/ide_ssr/Cargo.toml
index a725f7847c..9a8221ac6c 100644
--- a/crates/ide_ssr/Cargo.toml
+++ b/crates/ide_ssr/Cargo.toml
@@ -5,7 +5,7 @@ description = "Structural search and replace of Rust code"
 license = "MIT OR Apache-2.0"
 repository = "https://github.com/rust-analyzer/rust-analyzer"
 edition = "2021"
-rust-version = "1.57"
+rust-version = "1.56"
 
 [lib]
 doctest = false
diff --git a/crates/limit/Cargo.toml b/crates/limit/Cargo.toml
index 893db436d8..aa6e0bedea 100644
--- a/crates/limit/Cargo.toml
+++ b/crates/limit/Cargo.toml
@@ -4,7 +4,7 @@ version = "0.0.0"
 description = "TBD"
 license = "MIT OR Apache-2.0"
 edition = "2021"
-rust-version = "1.57"
+rust-version = "1.56"
 
 [features]
 tracking = []
diff --git a/crates/mbe/Cargo.toml b/crates/mbe/Cargo.toml
index c29c570bf5..651ca409c6 100644
--- a/crates/mbe/Cargo.toml
+++ b/crates/mbe/Cargo.toml
@@ -4,7 +4,7 @@ version = "0.0.0"
 description = "TBD"
 license = "MIT OR Apache-2.0"
 edition = "2021"
-rust-version = "1.57"
+rust-version = "1.56"
 
 [lib]
 doctest = false
diff --git a/crates/parser/Cargo.toml b/crates/parser/Cargo.toml
index f8477e751d..4028082d08 100644
--- a/crates/parser/Cargo.toml
+++ b/crates/parser/Cargo.toml
@@ -4,7 +4,7 @@ version = "0.0.0"
 description = "TBD"
 license = "MIT OR Apache-2.0"
 edition = "2021"
-rust-version = "1.57"
+rust-version = "1.56"
 
 [lib]
 doctest = false
diff --git a/crates/paths/Cargo.toml b/crates/paths/Cargo.toml
index 5e83de7d99..f9ea5018cc 100644
--- a/crates/paths/Cargo.toml
+++ b/crates/paths/Cargo.toml
@@ -4,7 +4,7 @@ version = "0.0.0"
 description = "TBD"
 license = "MIT OR Apache-2.0"
 edition = "2021"
-rust-version = "1.57"
+rust-version = "1.56"
 
 [lib]
 doctest = false
diff --git a/crates/proc_macro_api/Cargo.toml b/crates/proc_macro_api/Cargo.toml
index fde5b80141..9dd0ca9044 100644
--- a/crates/proc_macro_api/Cargo.toml
+++ b/crates/proc_macro_api/Cargo.toml
@@ -4,7 +4,7 @@ version = "0.0.0"
 description = "TBD"
 license = "MIT OR Apache-2.0"
 edition = "2021"
-rust-version = "1.57"
+rust-version = "1.56"
 
 [lib]
 doctest = false
diff --git a/crates/proc_macro_srv/Cargo.toml b/crates/proc_macro_srv/Cargo.toml
index 28e759cd87..6877bca598 100644
--- a/crates/proc_macro_srv/Cargo.toml
+++ b/crates/proc_macro_srv/Cargo.toml
@@ -4,7 +4,7 @@ version = "0.0.0"
 description = "TBD"
 license = "MIT OR Apache-2.0"
 edition = "2021"
-rust-version = "1.57"
+rust-version = "1.56"
 
 [lib]
 doctest = false
diff --git a/crates/profile/Cargo.toml b/crates/profile/Cargo.toml
index ac0a06ca5a..b16a3951c2 100644
--- a/crates/profile/Cargo.toml
+++ b/crates/profile/Cargo.toml
@@ -4,7 +4,7 @@ version = "0.0.0"
 description = "TBD"
 license = "MIT OR Apache-2.0"
 edition = "2021"
-rust-version = "1.57"
+rust-version = "1.56"
 
 [lib]
 doctest = false
diff --git a/crates/project_model/Cargo.toml b/crates/project_model/Cargo.toml
index 4932e7d012..97c73ca11c 100644
--- a/crates/project_model/Cargo.toml
+++ b/crates/project_model/Cargo.toml
@@ -4,7 +4,7 @@ version = "0.0.0"
 description = "TBD"
 license = "MIT OR Apache-2.0"
 edition = "2021"
-rust-version = "1.57"
+rust-version = "1.56"
 
 [lib]
 doctest = false
diff --git a/crates/rust-analyzer/Cargo.toml b/crates/rust-analyzer/Cargo.toml
index 0ab866a707..6d2f042ccb 100644
--- a/crates/rust-analyzer/Cargo.toml
+++ b/crates/rust-analyzer/Cargo.toml
@@ -8,7 +8,7 @@ documentation = "https://rust-analyzer.github.io/manual.html"
 license = "MIT OR Apache-2.0"
 autobins = false
 edition = "2021"
-rust-version = "1.57"
+rust-version = "1.56"
 
 [lib]
 doctest = false
diff --git a/crates/sourcegen/Cargo.toml b/crates/sourcegen/Cargo.toml
index 9cfe181c2e..34cebb34ec 100644
--- a/crates/sourcegen/Cargo.toml
+++ b/crates/sourcegen/Cargo.toml
@@ -4,7 +4,7 @@ version = "0.0.0"
 description = "TBD"
 license = "MIT OR Apache-2.0"
 edition = "2021"
-rust-version = "1.57"
+rust-version = "1.56"
 
 [lib]
 doctest = false
diff --git a/crates/stdx/Cargo.toml b/crates/stdx/Cargo.toml
index bdde9fc8c9..9bdf22188a 100644
--- a/crates/stdx/Cargo.toml
+++ b/crates/stdx/Cargo.toml
@@ -4,7 +4,7 @@ version = "0.0.0"
 description = "TBD"
 license = "MIT OR Apache-2.0"
 edition = "2021"
-rust-version = "1.57"
+rust-version = "1.56"
 
 [lib]
 doctest = false
diff --git a/crates/syntax/Cargo.toml b/crates/syntax/Cargo.toml
index 43c1f2fa80..526024a836 100644
--- a/crates/syntax/Cargo.toml
+++ b/crates/syntax/Cargo.toml
@@ -5,7 +5,7 @@ description = "Comment and whitespace preserving parser for the Rust language"
 license = "MIT OR Apache-2.0"
 repository = "https://github.com/rust-analyzer/rust-analyzer"
 edition = "2021"
-rust-version = "1.57"
+rust-version = "1.56"
 
 [lib]
 doctest = false
diff --git a/crates/syntax/fuzz/Cargo.toml b/crates/syntax/fuzz/Cargo.toml
index ba2f515b0b..119a5651b8 100644
--- a/crates/syntax/fuzz/Cargo.toml
+++ b/crates/syntax/fuzz/Cargo.toml
@@ -4,7 +4,7 @@ name = "syntax-fuzz"
 version = "0.0.1"
 publish = false
 edition = "2021"
-rust-version = "1.57"
+rust-version = "1.56"
 
 [package.metadata]
 cargo-fuzz = true
diff --git a/crates/text_edit/Cargo.toml b/crates/text_edit/Cargo.toml
index e9c6bb3348..7cbe3412c9 100644
--- a/crates/text_edit/Cargo.toml
+++ b/crates/text_edit/Cargo.toml
@@ -4,7 +4,7 @@ version = "0.0.0"
 description = "TBD"
 license = "MIT OR Apache-2.0"
 edition = "2021"
-rust-version = "1.57"
+rust-version = "1.56"
 
 [lib]
 doctest = false
diff --git a/crates/toolchain/Cargo.toml b/crates/toolchain/Cargo.toml
index 7d3b9e09ec..f0dc019fb9 100644
--- a/crates/toolchain/Cargo.toml
+++ b/crates/toolchain/Cargo.toml
@@ -4,7 +4,7 @@ version = "0.0.0"
 description = "TBD"
 license = "MIT OR Apache-2.0"
 edition = "2021"
-rust-version = "1.57"
+rust-version = "1.56"
 
 [lib]
 doctest = false
diff --git a/crates/tt/Cargo.toml b/crates/tt/Cargo.toml
index 3fb39355fe..23b56e3309 100644
--- a/crates/tt/Cargo.toml
+++ b/crates/tt/Cargo.toml
@@ -4,7 +4,7 @@ version = "0.0.0"
 description = "TBD"
 license = "MIT OR Apache-2.0"
 edition = "2021"
-rust-version = "1.57"
+rust-version = "1.56"
 
 [lib]
 doctest = false
diff --git a/crates/vfs-notify/Cargo.toml b/crates/vfs-notify/Cargo.toml
index a670852d63..7f7a9df375 100644
--- a/crates/vfs-notify/Cargo.toml
+++ b/crates/vfs-notify/Cargo.toml
@@ -4,7 +4,7 @@ version = "0.0.0"
 description = "TBD"
 license = "MIT OR Apache-2.0"
 edition = "2021"
-rust-version = "1.57"
+rust-version = "1.56"
 
 [lib]
 doctest = false
diff --git a/crates/vfs/Cargo.toml b/crates/vfs/Cargo.toml
index 24f380e25f..2c62626b75 100644
--- a/crates/vfs/Cargo.toml
+++ b/crates/vfs/Cargo.toml
@@ -4,7 +4,7 @@ version = "0.0.0"
 description = "TBD"
 license = "MIT OR Apache-2.0"
 edition = "2021"
-rust-version = "1.57"
+rust-version = "1.56"
 
 [lib]
 doctest = false
diff --git a/xtask/Cargo.toml b/xtask/Cargo.toml
index 0acbaf8176..a111b9d94f 100644
--- a/xtask/Cargo.toml
+++ b/xtask/Cargo.toml
@@ -4,7 +4,7 @@ version = "0.1.0"
 publish = false
 license = "MIT OR Apache-2.0"
 edition = "2021"
-rust-version = "1.57"
+rust-version = "1.56"
 
 [dependencies]
 anyhow = "1.0.26"


Test patch:
diff --git a/crates/hir_def/src/item_tree/tests.rs b/crates/hir_def/src/item_tree/tests.rs
index 63d177eaab..1969913bf9 100644
--- a/crates/hir_def/src/item_tree/tests.rs
+++ b/crates/hir_def/src/item_tree/tests.rs
@@ -176,7 +176,7 @@ trait Tr: SuperTrait + 'lifetime {
             // flags = 0x2
             pub(self) fn f(
                 #[attr]  // AttrId { is_doc_comment: false, ast_index: 0 }
-                arg: u8,
+                _: u8,
                 _: (),
             ) -> ();
 
@@ -341,7 +341,7 @@ trait Tr<'a, T: 'a>: Super where Self: for<'a> Tr<'a, T> {}
             {
                 // flags = 0x2
                 pub(self) fn f<G>(
-                    arg: impl Copy,
+                    _: impl Copy,
                 ) -> impl Copy
                 where
                     G: 'a;
diff --git a/crates/proc_macro_test/Cargo.toml b/crates/proc_macro_test/Cargo.toml
index 85c6de390a..b5f18276ca 100644
--- a/crates/proc_macro_test/Cargo.toml
+++ b/crates/proc_macro_test/Cargo.toml
@@ -3,7 +3,7 @@ name = "proc_macro_test"
 version = "0.0.0"
 license = "MIT OR Apache-2.0"
 edition = "2021"
-rust-version = "1.57"
+rust-version = "1.56"
 publish = false
 
 [lib]
diff --git a/crates/proc_macro_test/imp/Cargo.toml b/crates/proc_macro_test/imp/Cargo.toml
index dfb71ce57d..760c867817 100644
--- a/crates/proc_macro_test/imp/Cargo.toml
+++ b/crates/proc_macro_test/imp/Cargo.toml
@@ -3,7 +3,7 @@ name = "proc_macro_test_impl"
 version = "0.0.0"
 license = "MIT OR Apache-2.0"
 edition = "2021"
-rust-version = "1.57"
+rust-version = "1.56"
 publish = false
 
 [lib]
diff --git a/crates/test_utils/Cargo.toml b/crates/test_utils/Cargo.toml
index 36293155f2..d0e4b465fa 100644
--- a/crates/test_utils/Cargo.toml
+++ b/crates/test_utils/Cargo.toml
@@ -4,7 +4,7 @@ version = "0.0.0"
 description = "TBD"
 license = "MIT OR Apache-2.0"
 edition = "2021"
-rust-version = "1.57"
+rust-version = "1.56"
 
 [lib]
 doctest = false