fix stack overflow in `is_ty_uninhabited_from`

2 files changed, 59 insertions, 5 deletions

diff --git a/crates/hir-ty/src/inhabitedness.rs b/crates/hir-ty/src/inhabitedness.rs
index 36af78153d4..505f80f324f 100644
--- a/crates/hir-ty/src/inhabitedness.rs
+++ b/crates/hir-ty/src/inhabitedness.rs
@@ -1,5 +1,8 @@
 //! Type inhabitedness logic.
-use std::ops::ControlFlow::{self, Break, Continue};
+use std::{
+    collections::HashMap,
+    ops::ControlFlow::{self, Break, Continue},
+};
 
 use chalk_ir::{
     visit::{TypeSuperVisitable, TypeVisitable, TypeVisitor},
@@ -9,6 +12,7 @@ use hir_def::{
     adt::VariantData, attr::Attrs, visibility::Visibility, AdtId, EnumVariantId, HasModule, Lookup,
     ModuleId, VariantId,
 };
+use rustc_hash::FxHashMap;
 
 use crate::{
     consteval::try_const_usize, db::HirDatabase, Binders, Interner, Substitution, Ty, TyKind,
@@ -16,7 +20,8 @@ use crate::{
 
 /// Checks whether a type is visibly uninhabited from a particular module.
 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 mut uninhabited_from =
+        UninhabitedFrom { target_mod, db, max_depth: 500, recursive_ty: HashMap::default() };
     let inhabitedness = ty.visit_with(&mut uninhabited_from, DebruijnIndex::INNERMOST);
     inhabitedness == BREAK_VISIBLY_UNINHABITED
 }
@@ -32,7 +37,8 @@ pub(crate) fn is_enum_variant_uninhabited_from(
     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 mut uninhabited_from =
+        UninhabitedFrom { target_mod, db, max_depth: 500, recursive_ty: HashMap::default() };
     let inhabitedness = uninhabited_from.visit_variant(
         variant.into(),
         &enum_data.variants[variant.local_id].variant_data,
@@ -45,6 +51,9 @@ pub(crate) fn is_enum_variant_uninhabited_from(
 
 struct UninhabitedFrom<'a> {
     target_mod: ModuleId,
+    recursive_ty: FxHashMap<Ty, ()>,
+    // guard for preventing stack overflow in non trivial non terminating types
+    max_depth: usize,
     db: &'a dyn HirDatabase,
 }
 
@@ -65,7 +74,14 @@ impl TypeVisitor<Interner> for UninhabitedFrom<'_> {
         ty: &Ty,
         outer_binder: DebruijnIndex,
     ) -> ControlFlow<VisiblyUninhabited> {
-        match ty.kind(Interner) {
+        if self.recursive_ty.contains_key(ty) || self.max_depth == 0 {
+            // rustc considers recursive types always inhabited. I think it is valid to consider
+            // recursive types as always uninhabited, but we should do what rustc is doing.
+            return CONTINUE_OPAQUELY_INHABITED;
+        }
+        self.recursive_ty.insert(ty.clone(), ());
+        self.max_depth -= 1;
+        let r = 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),
@@ -75,7 +91,10 @@ impl TypeVisitor<Interner> for UninhabitedFrom<'_> {
             },
 
             TyKind::Ref(..) | _ => CONTINUE_OPAQUELY_INHABITED,
-        }
+        };
+        self.recursive_ty.remove(ty);
+        self.max_depth += 1;
+        r
     }
 
     fn interner(&self) -> Interner {
diff --git a/crates/ide-diagnostics/src/handlers/mutability_errors.rs b/crates/ide-diagnostics/src/handlers/mutability_errors.rs
index 17a70f5701b..0b66350894a 100644
--- a/crates/ide-diagnostics/src/handlers/mutability_errors.rs
+++ b/crates/ide-diagnostics/src/handlers/mutability_errors.rs
@@ -693,6 +693,41 @@ fn f(inp: (Foo, Foo, Foo, Foo)) {
     }
 
     #[test]
+    // FIXME: We should have tests for `is_ty_uninhabited_from`
+    fn regression_14421() {
+        check_diagnostics(
+            r#"
+pub enum Tree {
+    Node(TreeNode),
+    Leaf(TreeLeaf),
+}
+
+struct Box<T>(&T);
+
+pub struct TreeNode {
+    pub depth: usize,
+    pub children: [Box<Tree>; 8]
+}
+
+pub struct TreeLeaf {
+    pub depth: usize,
+    pub data: u8
+}
+
+pub fn test() {
+    let mut tree = Tree::Leaf(
+      //^^^^^^^^ 💡 weak: variable does not need to be mutable
+        TreeLeaf {
+            depth: 0,
+            data: 0
+        }
+    );
+}
+"#,
+        );
+    }
+
+    #[test]
     fn fn_traits() {
         check_diagnostics(
             r#"