Implement unstable RFC 1872 `exhaustive_patterns`

6 files changed, 265 insertions, 20 deletions

diff --git a/crates/hir-ty/src/diagnostics/expr.rs b/crates/hir-ty/src/diagnostics/expr.rs
index 642e03edd23..c8df4c796ef 100644
--- a/crates/hir-ty/src/diagnostics/expr.rs
+++ b/crates/hir-ty/src/diagnostics/expr.rs
@@ -159,12 +159,7 @@ impl ExprValidator {
         }
 
         let pattern_arena = Arena::new();
-        let cx = MatchCheckCtx {
-            module: self.owner.module(db.upcast()),
-            body: self.owner,
-            db,
-            pattern_arena: &pattern_arena,
-        };
+        let cx = MatchCheckCtx::new(self.owner.module(db.upcast()), self.owner, db, &pattern_arena);
 
         let mut m_arms = Vec::with_capacity(arms.len());
         let mut has_lowering_errors = false;
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 bbbe539c13f..47d60fc41e7 100644
--- a/crates/hir-ty/src/diagnostics/match_check/deconstruct_pat.rs
+++ b/crates/hir-ty/src/diagnostics/match_check/deconstruct_pat.rs
@@ -52,7 +52,10 @@ use hir_def::{EnumVariantId, HasModule, LocalFieldId, VariantId};
 use smallvec::{smallvec, SmallVec};
 use stdx::never;
 
-use crate::{infer::normalize, AdtId, Interner, Scalar, Ty, TyExt, TyKind};
+use crate::{
+    infer::normalize, inhabitedness::is_enum_variant_uninhabited_from, AdtId, Interner, Scalar, Ty,
+    TyExt, TyKind,
+};
 
 use super::{
     is_box,
@@ -557,8 +560,8 @@ 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)), ..) => {
-                let enum_data = cx.db.enum_data(enum_id);
+            TyKind::Adt(AdtId(hir_def::AdtId::EnumId(enum_id)), subst) => {
+                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
                 // additional "unknown" constructor.
@@ -591,14 +594,15 @@ impl SplitWildcard {
                 let mut ctors: SmallVec<[_; 1]> = enum_data
                     .variants
                     .iter()
-                    .filter(|&(_, _v)| {
+                    .map(|(local_id, _)| EnumVariantId { parent: *enum_id, local_id })
+                    .filter(|&variant| {
                         // 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_enum_variant_uninhabited_from(variant, subst, cx.module, cx.db);
                         !is_uninhabited
                     })
-                    .map(|(local_id, _)| Variant(EnumVariantId { parent: enum_id, local_id }))
+                    .map(Variant)
                     .collect();
 
                 if is_secretly_empty || is_declared_nonexhaustive {
diff --git a/crates/hir-ty/src/diagnostics/match_check/usefulness.rs b/crates/hir-ty/src/diagnostics/match_check/usefulness.rs
index 1221327b951..4bb4ff8f10a 100644
--- a/crates/hir-ty/src/diagnostics/match_check/usefulness.rs
+++ b/crates/hir-ty/src/diagnostics/match_check/usefulness.rs
@@ -274,10 +274,11 @@
 use std::iter::once;
 
 use hir_def::{AdtId, DefWithBodyId, HasModule, ModuleId};
+use once_cell::unsync::OnceCell;
 use smallvec::{smallvec, SmallVec};
 use typed_arena::Arena;
 
-use crate::{db::HirDatabase, Ty, TyExt};
+use crate::{db::HirDatabase, inhabitedness::is_ty_uninhabited_from, Ty, TyExt};
 
 use super::deconstruct_pat::{Constructor, DeconstructedPat, Fields, SplitWildcard};
 
@@ -289,13 +290,25 @@ pub(crate) struct MatchCheckCtx<'a, 'p> {
     pub(crate) db: &'a dyn HirDatabase,
     /// Lowered patterns from arms plus generated by the check.
     pub(crate) pattern_arena: &'p Arena<DeconstructedPat<'p>>,
+    feature_exhaustive_patterns: OnceCell<bool>,
 }
 
 impl<'a, 'p> MatchCheckCtx<'a, 'p> {
-    pub(super) fn is_uninhabited(&self, _ty: &Ty) -> bool {
-        // FIXME(iDawer) implement exhaustive_patterns feature. More info in:
-        // Tracking issue for RFC 1872: exhaustive_patterns feature https://github.com/rust-lang/rust/issues/51085
-        false
+    pub(crate) fn new(
+        module: ModuleId,
+        body: DefWithBodyId,
+        db: &'a dyn HirDatabase,
+        pattern_arena: &'p Arena<DeconstructedPat<'p>>,
+    ) -> Self {
+        Self { module, body, db, pattern_arena, feature_exhaustive_patterns: Default::default() }
+    }
+
+    pub(super) fn is_uninhabited(&self, ty: &Ty) -> bool {
+        if self.feature_exhaustive_patterns() {
+            is_ty_uninhabited_from(ty, self.module, self.db)
+        } else {
+            false
+        }
     }
 
     /// Returns whether the given type is an enum from another crate declared `#[non_exhaustive]`.
@@ -311,10 +324,22 @@ impl<'a, 'p> MatchCheckCtx<'a, 'p> {
         }
     }
 
-    // Rust feature described as "Allows exhaustive pattern matching on types that contain uninhabited types."
+    // Rust's unstable feature described as "Allows exhaustive pattern matching on types that contain uninhabited types."
     pub(super) fn feature_exhaustive_patterns(&self) -> bool {
-        // FIXME see MatchCheckCtx::is_uninhabited
-        false
+        *self.feature_exhaustive_patterns.get_or_init(|| {
+            let def_map = self.db.crate_def_map(self.module.krate());
+            let root_mod = def_map.module_id(def_map.root());
+            let rood_attrs = self.db.attrs(root_mod.into());
+            let mut nightly_features = rood_attrs
+                .by_key("feature")
+                .attrs()
+                .map(|attr| attr.parse_path_comma_token_tree())
+                .flatten()
+                .flatten();
+            nightly_features.any(
+            |feat| matches!(feat.segments(), [name] if name.to_smol_str() == "exhaustive_patterns"),
+        )
+        })
     }
 }
 
diff --git a/crates/hir-ty/src/inhabitedness.rs b/crates/hir-ty/src/inhabitedness.rs
new file mode 100644
index 00000000000..f4d822b9c70
--- /dev/null
+++ b/crates/hir-ty/src/inhabitedness.rs
@@ -0,0 +1,176 @@
+use std::ops::ControlFlow::{self, Break, Continue};
+
+use chalk_ir::{
+    visit::{TypeSuperVisitable, TypeVisitable, TypeVisitor},
+    DebruijnIndex,
+};
+use hir_def::{
+    adt::VariantData, attr::Attrs, type_ref::ConstScalar, visibility::Visibility, AdtId,
+    EnumVariantId, HasModule, Lookup, ModuleId, VariantId,
+};
+
+use crate::{
+    db::HirDatabase, Binders, ConcreteConst, Const, ConstValue, Interner, Substitution, Ty, TyKind,
+};
+
+pub(crate) fn is_ty_uninhabited_from(ty: &Ty, target_mod: ModuleId, db: &dyn HirDatabase) -> bool {
+    let mut uninhabited_from = UninhabitedFrom { target_mod, db };
+    let inhabitedness = ty.visit_with(&mut uninhabited_from, DebruijnIndex::INNERMOST);
+    inhabitedness == BREAK_VISIBLY_UNINHABITED
+}
+
+pub(crate) fn is_enum_variant_uninhabited_from(
+    variant: EnumVariantId,
+    subst: &Substitution,
+    target_mod: ModuleId,
+    db: &dyn HirDatabase,
+) -> bool {
+    let enum_data = db.enum_data(variant.parent);
+    let vars_attrs = db.variants_attrs(variant.parent);
+    let is_local = variant.parent.lookup(db.upcast()).container.krate() == target_mod.krate();
+
+    let mut uninhabited_from = UninhabitedFrom { target_mod, db };
+    let inhabitedness = uninhabited_from.visit_variant(
+        variant.into(),
+        &enum_data.variants[variant.local_id].variant_data,
+        subst,
+        &vars_attrs[variant.local_id],
+        is_local,
+    );
+    inhabitedness == BREAK_VISIBLY_UNINHABITED
+}
+
+struct UninhabitedFrom<'a> {
+    target_mod: ModuleId,
+    db: &'a dyn HirDatabase,
+}
+
+const CONTINUE_OPAQUELY_INHABITED: ControlFlow<VisiblyUninhabited> = Continue(());
+const BREAK_VISIBLY_UNINHABITED: ControlFlow<VisiblyUninhabited> = Break(VisiblyUninhabited);
+#[derive(PartialEq, Eq)]
+struct VisiblyUninhabited;
+
+impl TypeVisitor<Interner> for UninhabitedFrom<'_> {
+    type BreakTy = VisiblyUninhabited;
+
+    fn as_dyn(&mut self) -> &mut dyn TypeVisitor<Interner, BreakTy = VisiblyUninhabited> {
+        self
+    }
+
+    fn visit_ty(
+        &mut self,
+        ty: &Ty,
+        outer_binder: DebruijnIndex,
+    ) -> ControlFlow<VisiblyUninhabited> {
+        match ty.kind(Interner) {
+            TyKind::Adt(adt, subst) => self.visit_adt(adt.0, subst),
+            TyKind::Never => BREAK_VISIBLY_UNINHABITED,
+            TyKind::Tuple(..) => ty.super_visit_with(self, outer_binder),
+            TyKind::Array(item_ty, len) => match try_usize_const(len) {
+                Some(0) | None => CONTINUE_OPAQUELY_INHABITED,
+                Some(1..) => item_ty.super_visit_with(self, outer_binder),
+            },
+
+            TyKind::Ref(..) | _ => CONTINUE_OPAQUELY_INHABITED,
+        }
+    }
+
+    fn interner(&self) -> Interner {
+        Interner
+    }
+}
+
+impl UninhabitedFrom<'_> {
+    fn visit_adt(&mut self, adt: AdtId, subst: &Substitution) -> ControlFlow<VisiblyUninhabited> {
+        let attrs = self.db.attrs(adt.into());
+        let adt_non_exhaustive = attrs.by_key("non_exhaustive").exists();
+        let is_local = adt.module(self.db.upcast()).krate() == self.target_mod.krate();
+        if adt_non_exhaustive && !is_local {
+            return CONTINUE_OPAQUELY_INHABITED;
+        }
+
+        // An ADT is uninhabited iff all its variants uninhabited.
+        match adt {
+            // rustc: For now, `union`s are never considered uninhabited.
+            AdtId::UnionId(_) => CONTINUE_OPAQUELY_INHABITED,
+            AdtId::StructId(s) => {
+                let struct_data = self.db.struct_data(s);
+                self.visit_variant(s.into(), &struct_data.variant_data, subst, &attrs, is_local)
+            }
+            AdtId::EnumId(e) => {
+                let vars_attrs = self.db.variants_attrs(e);
+                let enum_data = self.db.enum_data(e);
+
+                for (local_id, enum_var) in enum_data.variants.iter() {
+                    let variant_inhabitedness = self.visit_variant(
+                        EnumVariantId { parent: e, local_id }.into(),
+                        &enum_var.variant_data,
+                        subst,
+                        &vars_attrs[local_id],
+                        is_local,
+                    );
+                    match variant_inhabitedness {
+                        Break(VisiblyUninhabited) => continue,
+                        Continue(()) => return CONTINUE_OPAQUELY_INHABITED,
+                    }
+                }
+                BREAK_VISIBLY_UNINHABITED
+            }
+        }
+    }
+
+    fn visit_variant(
+        &mut self,
+        variant: VariantId,
+        variant_data: &VariantData,
+        subst: &Substitution,
+        attrs: &Attrs,
+        is_local: bool,
+    ) -> ControlFlow<VisiblyUninhabited> {
+        let non_exhaustive_field_list = attrs.by_key("non_exhaustive").exists();
+        if non_exhaustive_field_list && !is_local {
+            return CONTINUE_OPAQUELY_INHABITED;
+        }
+
+        let is_enum = matches!(variant, VariantId::EnumVariantId(..));
+        let field_tys = self.db.field_types(variant);
+        let field_vis = self.db.field_visibilities(variant);
+
+        for (fid, _) in variant_data.fields().iter() {
+            self.visit_field(field_vis[fid], &field_tys[fid], subst, is_enum)?;
+        }
+        CONTINUE_OPAQUELY_INHABITED
+    }
+
+    fn visit_field(
+        &mut self,
+        vis: Visibility,
+        ty: &Binders<Ty>,
+        subst: &Substitution,
+        is_enum: bool,
+    ) -> ControlFlow<VisiblyUninhabited> {
+        let target_mod = self.target_mod;
+        let mut data_uninhabitedness =
+            || ty.clone().substitute(Interner, subst).visit_with(self, DebruijnIndex::INNERMOST);
+        if is_enum {
+            data_uninhabitedness()
+        } else {
+            match vis {
+                Visibility::Module(mod_id) if mod_id == target_mod => data_uninhabitedness(),
+                Visibility::Module(_) => CONTINUE_OPAQUELY_INHABITED,
+                Visibility::Public => data_uninhabitedness(),
+            }
+        }
+    }
+}
+
+fn try_usize_const(c: &Const) -> Option<u128> {
+    let data = &c.data(Interner);
+    if data.ty.kind(Interner) != &TyKind::Scalar(chalk_ir::Scalar::Uint(chalk_ir::UintTy::Usize)) {
+        return None;
+    }
+    match data.value {
+        ConstValue::Concrete(ConcreteConst { interned: ConstScalar::UInt(value) }) => Some(value),
+        _ => None,
+    }
+}
diff --git a/crates/hir-ty/src/lib.rs b/crates/hir-ty/src/lib.rs
index 5a5d610e360..a82a331d4b8 100644
--- a/crates/hir-ty/src/lib.rs
+++ b/crates/hir-ty/src/lib.rs
@@ -14,6 +14,7 @@ mod chalk_db;
 mod chalk_ext;
 pub mod consteval;
 mod infer;
+mod inhabitedness;
 mod interner;
 mod lower;
 mod mapping;
diff --git a/crates/ide-diagnostics/src/handlers/missing_match_arms.rs b/crates/ide-diagnostics/src/handlers/missing_match_arms.rs
index 5fcaf405b14..c24430ce604 100644
--- a/crates/ide-diagnostics/src/handlers/missing_match_arms.rs
+++ b/crates/ide-diagnostics/src/handlers/missing_match_arms.rs
@@ -947,6 +947,50 @@ fn f() {
         );
     }
 
+    mod rust_unstable {
+        use super::*;
+
+        #[test]
+        fn rfc_1872_exhaustive_patterns() {
+            check_diagnostics_no_bails(
+                r"
+//- minicore: option, result
+#![feature(exhaustive_patterns)]
+enum Void {}
+fn test() {
+    match None::<!> { None => () }
+    match Result::<u8, !>::Ok(2) { Ok(_) => () }
+    match Result::<u8, Void>::Ok(2) { Ok(_) => () }
+    match (2, loop {}) {}
+    match Result::<!, !>::Ok(loop {}) {}
+    match (&loop {}) {} // https://github.com/rust-lang/rust/issues/50642#issuecomment-388234919
+    //    ^^^^^^^^^^ error: missing match arm: type `&!` is non-empty
+}",
+            );
+        }
+
+        #[test]
+        fn rfc_1872_private_uninhabitedness() {
+            check_diagnostics_no_bails(
+                r"
+//- minicore: option
+//- /lib.rs crate:lib
+#![feature(exhaustive_patterns)]
+pub struct PrivatelyUninhabited { private_field: Void }
+enum Void {}
+fn test_local(x: Option<PrivatelyUninhabited>) {
+    match x {}
+} //      ^ error: missing match arm: `None` not covered
+//- /main.rs crate:main deps:lib
+#![feature(exhaustive_patterns)]
+fn test(x: Option<lib::PrivatelyUninhabited>) {
+    match x {}
+    //    ^ error: missing match arm: `None` and `Some(_)` not covered
+}",
+            );
+        }
+    }
+
     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