Github Fix stack overflow when checking for structural recursion by FabianWolff...

FabianWolff commented 28 days ago •

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:

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.:

struct Foo { x: Option<Option<Foo>> }

Special care needs to be taken for mutually recursive types, e.g.:

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.