Handle more cases in `is_normalizable` (#13833)

By assuming that a recursive type is normalizable within the deeper
calls to `is_normalizable_helper()`, more cases can be handled by this
function.

In order to fix stack overflows, a recursion limit has also been added
for recursive generic type instantiations.

Fix #9798
Fix #10508
Fix #11915

changelog: [`large_enum_variant`]: more precise detection of variants
with large size differences

7 files changed, 236 insertions, 7 deletions

diff --git a/clippy_utils/src/ty/mod.rs b/clippy_utils/src/ty/mod.rs
index 0da540d2a4e..c68a166afb1 100644
--- a/clippy_utils/src/ty/mod.rs
+++ b/clippy_utils/src/ty/mod.rs
@@ -365,20 +365,26 @@ pub fn is_must_use_ty<'tcx>(cx: &LateContext<'tcx>, ty: Ty<'tcx>) -> bool {
 /// Checks if `Ty` is normalizable. This function is useful
 /// to avoid crashes on `layout_of`.
 pub fn is_normalizable<'tcx>(cx: &LateContext<'tcx>, param_env: ParamEnv<'tcx>, ty: Ty<'tcx>) -> bool {
-    is_normalizable_helper(cx, param_env, ty, &mut FxHashMap::default())
+    is_normalizable_helper(cx, param_env, ty, 0, &mut FxHashMap::default())
 }
 
 fn is_normalizable_helper<'tcx>(
     cx: &LateContext<'tcx>,
     param_env: ParamEnv<'tcx>,
     ty: Ty<'tcx>,
+    depth: usize,
     cache: &mut FxHashMap<Ty<'tcx>, bool>,
 ) -> bool {
     if let Some(&cached_result) = cache.get(&ty) {
         return cached_result;
     }
-    // prevent recursive loops, false-negative is better than endless loop leading to stack overflow
-    cache.insert(ty, false);
+    if !cx.tcx.recursion_limit().value_within_limit(depth) {
+        return false;
+    }
+    // Prevent recursive loops by answering `true` to recursive requests with the same
+    // type. This will be adjusted when the outermost call analyzes all the type
+    // components.
+    cache.insert(ty, true);
     let infcx = cx.tcx.infer_ctxt().build(cx.typing_mode());
     let cause = ObligationCause::dummy();
     let result = if infcx.at(&cause, param_env).query_normalize(ty).is_ok() {
@@ -387,11 +393,11 @@ fn is_normalizable_helper<'tcx>(
                 variant
                     .fields
                     .iter()
-                    .all(|field| is_normalizable_helper(cx, param_env, field.ty(cx.tcx, args), cache))
+                    .all(|field| is_normalizable_helper(cx, param_env, field.ty(cx.tcx, args), depth + 1, cache))
             }),
             _ => ty.walk().all(|generic_arg| match generic_arg.unpack() {
                 GenericArgKind::Type(inner_ty) if inner_ty != ty => {
-                    is_normalizable_helper(cx, param_env, inner_ty, cache)
+                    is_normalizable_helper(cx, param_env, inner_ty, depth + 1, cache)
                 },
                 _ => true, // if inner_ty == ty, we've already checked it
             }),
diff --git a/tests/ui/crashes/ice-10508a.rs b/tests/ui/crashes/ice-10508a.rs
new file mode 100644
index 00000000000..f45057217b4
--- /dev/null
+++ b/tests/ui/crashes/ice-10508a.rs
@@ -0,0 +1,19 @@
+// Used to overflow in `is_normalizable`
+
+use std::marker::PhantomData;
+
+struct Node<T: 'static> {
+    m: PhantomData<&'static T>,
+}
+
+struct Digit<T> {
+    elem: T,
+}
+
+enum FingerTree<T: 'static> {
+    Single(T),
+
+    Deep(Digit<T>, Box<FingerTree<Node<T>>>),
+}
+
+fn main() {}
diff --git a/tests/ui/crashes/ice-10508b.rs b/tests/ui/crashes/ice-10508b.rs
new file mode 100644
index 00000000000..41d4f0234b9
--- /dev/null
+++ b/tests/ui/crashes/ice-10508b.rs
@@ -0,0 +1,24 @@
+use std::marker::PhantomData;
+
+struct Digit<T> {
+    elem: T,
+}
+
+struct Node<T: 'static> {
+    m: PhantomData<&'static T>,
+}
+
+enum FingerTree<T: 'static> {
+    Single(T),
+
+    Deep(Digit<T>, Node<FingerTree<Node<T>>>),
+}
+
+enum Wrapper<T: 'static> {
+    Simple,
+    Other(FingerTree<T>),
+}
+
+fn main() {
+    let w = Some(Wrapper::Simple::<u32>);
+}
diff --git a/tests/ui/crashes/ice-10508c.rs b/tests/ui/crashes/ice-10508c.rs
new file mode 100644
index 00000000000..fb84d85fd67
--- /dev/null
+++ b/tests/ui/crashes/ice-10508c.rs
@@ -0,0 +1,7 @@
+#[derive(Debug)]
+struct S<T> {
+    t: T,
+    s: Box<S<fn(u: T)>>,
+}
+
+fn main() {}
diff --git a/tests/ui/large_enum_variant.32bit.stderr b/tests/ui/large_enum_variant.32bit.stderr
index ff4f1a7f312..36f3d930b53 100644
--- a/tests/ui/large_enum_variant.32bit.stderr
+++ b/tests/ui/large_enum_variant.32bit.stderr
@@ -276,5 +276,37 @@ help: consider boxing the large fields to reduce the total size of the enum
 LL |     Error(Box<PossiblyLargeEnumWithConst<256>>),
    |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
-error: aborting due to 16 previous errors
+error: large size difference between variants
+  --> tests/ui/large_enum_variant.rs:158:1
+   |
+LL | / enum WithRecursion {
+LL | |     Large([u64; 64]),
+   | |     ---------------- the largest variant contains at least 512 bytes
+LL | |     Recursive(Box<WithRecursion>),
+   | |     ----------------------------- the second-largest variant contains at least 4 bytes
+LL | | }
+   | |_^ the entire enum is at least 516 bytes
+   |
+help: consider boxing the large fields to reduce the total size of the enum
+   |
+LL |     Large(Box<[u64; 64]>),
+   |           ~~~~~~~~~~~~~~
+
+error: large size difference between variants
+  --> tests/ui/large_enum_variant.rs:168:1
+   |
+LL | / enum LargeEnumWithGenericsAndRecursive {
+LL | |     Ok(),
+   | |     ---- the second-largest variant carries no data at all
+LL | |     Error(WithRecursionAndGenerics<u64>),
+   | |     ------------------------------------ the largest variant contains at least 516 bytes
+LL | | }
+   | |_^ the entire enum is at least 516 bytes
+   |
+help: consider boxing the large fields to reduce the total size of the enum
+   |
+LL |     Error(Box<WithRecursionAndGenerics<u64>>),
+   |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+error: aborting due to 18 previous errors
 
diff --git a/tests/ui/large_enum_variant.64bit.stderr b/tests/ui/large_enum_variant.64bit.stderr
index 805cb406f83..31576a5863f 100644
--- a/tests/ui/large_enum_variant.64bit.stderr
+++ b/tests/ui/large_enum_variant.64bit.stderr
@@ -276,5 +276,69 @@ help: consider boxing the large fields to reduce the total size of the enum
 LL |     Error(Box<PossiblyLargeEnumWithConst<256>>),
    |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
-error: aborting due to 16 previous errors
+error: large size difference between variants
+  --> tests/ui/large_enum_variant.rs:158:1
+   |
+LL | / enum WithRecursion {
+LL | |     Large([u64; 64]),
+   | |     ---------------- the largest variant contains at least 512 bytes
+LL | |     Recursive(Box<WithRecursion>),
+   | |     ----------------------------- the second-largest variant contains at least 8 bytes
+LL | | }
+   | |_^ the entire enum is at least 520 bytes
+   |
+help: consider boxing the large fields to reduce the total size of the enum
+   |
+LL |     Large(Box<[u64; 64]>),
+   |           ~~~~~~~~~~~~~~
+
+error: large size difference between variants
+  --> tests/ui/large_enum_variant.rs:168:1
+   |
+LL | / enum LargeEnumWithGenericsAndRecursive {
+LL | |     Ok(),
+   | |     ---- the second-largest variant carries no data at all
+LL | |     Error(WithRecursionAndGenerics<u64>),
+   | |     ------------------------------------ the largest variant contains at least 520 bytes
+LL | | }
+   | |_^ the entire enum is at least 520 bytes
+   |
+help: consider boxing the large fields to reduce the total size of the enum
+   |
+LL |     Error(Box<WithRecursionAndGenerics<u64>>),
+   |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+error: large size difference between variants
+  --> tests/ui/large_enum_variant.rs:203:5
+   |
+LL | /     enum NoWarnings {
+LL | |         BigBoi(PublishWithBytes),
+   | |         ------------------------ the largest variant contains at least 296 bytes
+LL | |         _SmallBoi(u8),
+   | |         ------------- the second-largest variant contains at least 1 bytes
+LL | |     }
+   | |_____^ the entire enum is at least 296 bytes
+   |
+help: consider boxing the large fields to reduce the total size of the enum
+   |
+LL |         BigBoi(Box<PublishWithBytes>),
+   |                ~~~~~~~~~~~~~~~~~~~~~
+
+error: large size difference between variants
+  --> tests/ui/large_enum_variant.rs:208:5
+   |
+LL | /     enum MakesClippyAngry {
+LL | |         BigBoi(PublishWithVec),
+   | |         ---------------------- the largest variant contains at least 224 bytes
+LL | |         _SmallBoi(u8),
+   | |         ------------- the second-largest variant contains at least 1 bytes
+LL | |     }
+   | |_____^ the entire enum is at least 224 bytes
+   |
+help: consider boxing the large fields to reduce the total size of the enum
+   |
+LL |         BigBoi(Box<PublishWithVec>),
+   |                ~~~~~~~~~~~~~~~~~~~
+
+error: aborting due to 20 previous errors
 
diff --git a/tests/ui/large_enum_variant.rs b/tests/ui/large_enum_variant.rs
index 3625c011dbf..57722f63b22 100644
--- a/tests/ui/large_enum_variant.rs
+++ b/tests/ui/large_enum_variant.rs
@@ -155,6 +155,21 @@ enum LargeEnumOfConst {
     Error(PossiblyLargeEnumWithConst<256>),
 }
 
+enum WithRecursion {
+    Large([u64; 64]),
+    Recursive(Box<WithRecursion>),
+}
+
+enum WithRecursionAndGenerics<T> {
+    Large([T; 64]),
+    Recursive(Box<WithRecursionAndGenerics<T>>),
+}
+
+enum LargeEnumWithGenericsAndRecursive {
+    Ok(),
+    Error(WithRecursionAndGenerics<u64>),
+}
+
 fn main() {
     external!(
         enum LargeEnumInMacro {
@@ -163,3 +178,65 @@ fn main() {
         }
     );
 }
+
+mod issue11915 {
+    use std::sync::atomic::AtomicPtr;
+
+    pub struct Bytes {
+        ptr: *const u8,
+        len: usize,
+        // inlined "trait object"
+        data: AtomicPtr<()>,
+        vtable: &'static Vtable,
+    }
+    pub(crate) struct Vtable {
+        /// fn(data, ptr, len)
+        pub clone: unsafe fn(&AtomicPtr<()>, *const u8, usize) -> Bytes,
+        /// fn(data, ptr, len)
+        ///
+        /// takes `Bytes` to value
+        pub to_vec: unsafe fn(&AtomicPtr<()>, *const u8, usize) -> Vec<u8>,
+        /// fn(data, ptr, len)
+        pub drop: unsafe fn(&mut AtomicPtr<()>, *const u8, usize),
+    }
+
+    enum NoWarnings {
+        BigBoi(PublishWithBytes),
+        _SmallBoi(u8),
+    }
+
+    enum MakesClippyAngry {
+        BigBoi(PublishWithVec),
+        _SmallBoi(u8),
+    }
+
+    struct PublishWithBytes {
+        _dup: bool,
+        _retain: bool,
+        _topic: Bytes,
+        __topic: Bytes,
+        ___topic: Bytes,
+        ____topic: Bytes,
+        _pkid: u16,
+        _payload: Bytes,
+        __payload: Bytes,
+        ___payload: Bytes,
+        ____payload: Bytes,
+        _____payload: Bytes,
+    }
+
+    struct PublishWithVec {
+        _dup: bool,
+        _retain: bool,
+        _topic: Vec<u8>,
+        __topic: Vec<u8>,
+        ___topic: Vec<u8>,
+        ____topic: Vec<u8>,
+        _pkid: u16,
+        _payload: Vec<u8>,
+        __payload: Vec<u8>,
+        ___payload: Vec<u8>,
+        ____payload: Vec<u8>,
+        _____payload: Vec<u8>,
+    }
+}