Auto merge of #85012 - FabianWolff:struct-rec, r=davidtwco

Fix stack overflow when checking for structural recursion

This pull request aims to fix #74224 and fix #84611. The current logic for detecting ADTs with structural recursion is flawed because it only looks at the root type, and then for exact matches. What I mean by this is that for examples such as:
```rust
struct A<T> {
    x: T,
    y: A<A<T>>,
}

struct B {
    z: A<usize>
}

fn main() {}
```
When checking `A`, the compiler correctly determines that it has an infinite size (because the "root" type is `A`, and `A` occurs, albeit with different type arguments, as a nested type in `A`).

However, when checking `B`, it also recurses into `A`, but now `B` is the root type, and it only checks for _exact_ matches of `A`, but since `A` never precisely contains itself (only `A<A<T>>`, `A<A<A<T>>>`, etc.), an endless recursion ensues until the stack overflows.

In this PR, I have attempted to fix this behavior by implementing a two-phase checking: When checking `B`, my code first checks `A` _separately_ and stops if `A` already turns out to be infinite. If not (such as for `Option<T>`), the second phase checks whether the root type (`B`) is ever nested inside itself, e.g.:
```rust
struct Foo { x: Option<Option<Foo>> }
```

Special care needs to be taken for mutually recursive types, e.g.:
```rust
struct A<T> {
    z: T,
    x: B<T>,
}

struct B<T> {
    y: A<T>
}
```
Here, both `A` and `B` both _are_ `SelfRecursive` and _contain_ a recursive type. The current behavior, which I have maintained, is to treat both `A` and `B` as `SelfRecursive`, and accordingly report errors for both.

6 files changed, 138 insertions, 0 deletions

diff --git a/src/test/ui/structs-enums/struct-rec/issue-74224.rs b/src/test/ui/structs-enums/struct-rec/issue-74224.rs
new file mode 100644
index 00000000000..f3b72c5df7f
--- /dev/null
+++ b/src/test/ui/structs-enums/struct-rec/issue-74224.rs
@@ -0,0 +1,11 @@
+struct A<T> {
+//~^ ERROR recursive type `A` has infinite size
+    x: T,
+    y: A<A<T>>,
+}
+
+struct B {
+    z: A<usize>
+}
+
+fn main() {}
diff --git a/src/test/ui/structs-enums/struct-rec/issue-74224.stderr b/src/test/ui/structs-enums/struct-rec/issue-74224.stderr
new file mode 100644
index 00000000000..d61ab1952f9
--- /dev/null
+++ b/src/test/ui/structs-enums/struct-rec/issue-74224.stderr
@@ -0,0 +1,17 @@
+error[E0072]: recursive type `A` has infinite size
+  --> $DIR/issue-74224.rs:1:1
+   |
+LL | struct A<T> {
+   | ^^^^^^^^^^^ recursive type has infinite size
+...
+LL |     y: A<A<T>>,
+   |        ------- recursive without indirection
+   |
+help: insert some indirection (e.g., a `Box`, `Rc`, or `&`) to make `A` representable
+   |
+LL |     y: Box<A<A<T>>>,
+   |        ^^^^       ^
+
+error: aborting due to previous error
+
+For more information about this error, try `rustc --explain E0072`.
diff --git a/src/test/ui/structs-enums/struct-rec/issue-84611.rs b/src/test/ui/structs-enums/struct-rec/issue-84611.rs
new file mode 100644
index 00000000000..4c356af3eb8
--- /dev/null
+++ b/src/test/ui/structs-enums/struct-rec/issue-84611.rs
@@ -0,0 +1,11 @@
+struct Foo<T> {
+//~^ ERROR recursive type `Foo` has infinite size
+    x: Foo<[T; 1]>,
+    y: T,
+}
+
+struct Bar {
+    x: Foo<Bar>,
+}
+
+fn main() {}
diff --git a/src/test/ui/structs-enums/struct-rec/issue-84611.stderr b/src/test/ui/structs-enums/struct-rec/issue-84611.stderr
new file mode 100644
index 00000000000..0a898e5c46d
--- /dev/null
+++ b/src/test/ui/structs-enums/struct-rec/issue-84611.stderr
@@ -0,0 +1,17 @@
+error[E0072]: recursive type `Foo` has infinite size
+  --> $DIR/issue-84611.rs:1:1
+   |
+LL | struct Foo<T> {
+   | ^^^^^^^^^^^^^ recursive type has infinite size
+LL |
+LL |     x: Foo<[T; 1]>,
+   |        ----------- recursive without indirection
+   |
+help: insert some indirection (e.g., a `Box`, `Rc`, or `&`) to make `Foo` representable
+   |
+LL |     x: Box<Foo<[T; 1]>>,
+   |        ^^^^           ^
+
+error: aborting due to previous error
+
+For more information about this error, try `rustc --explain E0072`.
diff --git a/src/test/ui/structs-enums/struct-rec/mutual-struct-recursion.rs b/src/test/ui/structs-enums/struct-rec/mutual-struct-recursion.rs
new file mode 100644
index 00000000000..cca97f43eff
--- /dev/null
+++ b/src/test/ui/structs-enums/struct-rec/mutual-struct-recursion.rs
@@ -0,0 +1,23 @@
+struct A<T> {
+//~^ ERROR recursive type `A` has infinite size
+    x: T,
+    y: B<T>,
+}
+
+struct B<T> {
+//~^ ERROR recursive type `B` has infinite size
+    z: A<T>
+}
+
+struct C<T> {
+//~^ ERROR recursive type `C` has infinite size
+    x: T,
+    y: Option<Option<D<T>>>,
+}
+
+struct D<T> {
+//~^ ERROR recursive type `D` has infinite size
+    z: Option<Option<C<T>>>,
+}
+
+fn main() {}
diff --git a/src/test/ui/structs-enums/struct-rec/mutual-struct-recursion.stderr b/src/test/ui/structs-enums/struct-rec/mutual-struct-recursion.stderr
new file mode 100644
index 00000000000..efc4ba93f0a
--- /dev/null
+++ b/src/test/ui/structs-enums/struct-rec/mutual-struct-recursion.stderr
@@ -0,0 +1,59 @@
+error[E0072]: recursive type `A` has infinite size
+  --> $DIR/mutual-struct-recursion.rs:1:1
+   |
+LL | struct A<T> {
+   | ^^^^^^^^^^^ recursive type has infinite size
+...
+LL |     y: B<T>,
+   |        ---- recursive without indirection
+   |
+help: insert some indirection (e.g., a `Box`, `Rc`, or `&`) to make `A` representable
+   |
+LL |     y: Box<B<T>>,
+   |        ^^^^    ^
+
+error[E0072]: recursive type `B` has infinite size
+  --> $DIR/mutual-struct-recursion.rs:7:1
+   |
+LL | struct B<T> {
+   | ^^^^^^^^^^^ recursive type has infinite size
+LL |
+LL |     z: A<T>
+   |        ---- recursive without indirection
+   |
+help: insert some indirection (e.g., a `Box`, `Rc`, or `&`) to make `B` representable
+   |
+LL |     z: Box<A<T>>
+   |        ^^^^    ^
+
+error[E0072]: recursive type `C` has infinite size
+  --> $DIR/mutual-struct-recursion.rs:12:1
+   |
+LL | struct C<T> {
+   | ^^^^^^^^^^^ recursive type has infinite size
+...
+LL |     y: Option<Option<D<T>>>,
+   |        -------------------- recursive without indirection
+   |
+help: insert some indirection (e.g., a `Box`, `Rc`, or `&`) to make `C` representable
+   |
+LL |     y: Box<Option<Option<D<T>>>>,
+   |        ^^^^                    ^
+
+error[E0072]: recursive type `D` has infinite size
+  --> $DIR/mutual-struct-recursion.rs:18:1
+   |
+LL | struct D<T> {
+   | ^^^^^^^^^^^ recursive type has infinite size
+LL |
+LL |     z: Option<Option<C<T>>>,
+   |        -------------------- recursive without indirection
+   |
+help: insert some indirection (e.g., a `Box`, `Rc`, or `&`) to make `D` representable
+   |
+LL |     z: Box<Option<Option<C<T>>>>,
+   |        ^^^^                    ^
+
+error: aborting due to 4 previous errors
+
+For more information about this error, try `rustc --explain E0072`.