Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

is_type_structurally_recursive diverges on some structurally recursive types #74224

Closed
tmiasko opened this issue Jul 10, 2020 · 1 comment · Fixed by #85012
Closed

is_type_structurally_recursive diverges on some structurally recursive types #74224

tmiasko opened this issue Jul 10, 2020 · 1 comment · Fixed by #85012
Labels
C-bug Category: This is a bug. I-hang Issue: The compiler never terminates, due to infinite loops, deadlock, livelock, etc. P-medium Medium priority regression-from-stable-to-stable Performance or correctness regression from one stable version to another. T-compiler Relevant to the compiler team, which will review and decide on the PR/issue.

Comments

@tmiasko
Copy link
Contributor

tmiasko commented Jul 10, 2020 •
edited
Loading

For example, compilation of the following program diverges:

struct A<T> {
    x: T,
    y: A<A<T>>,
}

struct B {
    z: A<usize>
}

fn main() {}

Found while examining issue from #74201, but this one has a different root cause.

rustc log 

[DEBUG rustc_middle::ty::util] is_type_representable: A<T>
[DEBUG rustc_middle::ty::util] is_type_structurally_recursive: A<T> x.rs:1:1: 4:2 (#0)
[DEBUG rustc_middle::ty::util] is_type_structurally_recursive: T x.rs:2:8: 2:9 (#0)
[DEBUG rustc_middle::ty::util] is_type_structurally_recursive: A<A<T>> x.rs:3:8: 3:15 (#0)
[DEBUG rustc_middle::ty::util] SelfRecursive: A<T> contains A<A<T>>
[DEBUG rustc_middle::ty::util] is_type_representable: A<T> is SelfRecursive([x.rs:3:8: 3:15 (#0)])
error[E0072]: recursive type `A` has infinite size
 --> x.rs:1:1
  |
1 | struct A<T> {
  | ^^^^^^^^^^^ recursive type has infinite size
2 |     x: T,
3 |     y: A<A<T>>,
  |        ------- recursive without indirection
  |
help: insert some indirection (e.g., a `Box`, `Rc`, or `&`) to make `A` representable
  |
3 |     y: Box<A<A<T>>>,
  |        ^^^^       ^

[DEBUG rustc_middle::ty::util] is_type_representable: B
[DEBUG rustc_middle::ty::util] is_type_structurally_recursive: B x.rs:6:1: 8:2 (#0)
[DEBUG rustc_middle::ty::util] is_type_structurally_recursive: A<usize> x.rs:7:8: 7:16 (#0)
[DEBUG rustc_middle::ty::util] is_type_structurally_recursive: usize x.rs:2:8: 2:9 (#0)
[DEBUG rustc_middle::ty::util] is_type_structurally_recursive: A<A<usize>> x.rs:3:8: 3:15 (#0)
[DEBUG rustc_middle::ty::util] is_type_structurally_recursive: A<usize> x.rs:2:8: 2:9 (#0)
[DEBUG rustc_middle::ty::util] ContainsRecursive: A<usize> contains A<usize>
[DEBUG rustc_middle::ty::util] is_type_structurally_recursive: A<A<A<usize>>> x.rs:3:8: 3:15 (#0)
...

@tmiasko tmiasko added the C-bug Category: This is a bug. label Jul 10, 2020
@jonas-schievink jonas-schievink added I-hang Issue: The compiler never terminates, due to infinite loops, deadlock, livelock, etc. T-compiler Relevant to the compiler team, which will review and decide on the PR/issue. I-prioritize Issue: Indicates that prioritization has been requested for this issue. labels Jul 10, 2020
@wesleywiser wesleywiser added the regression-from-stable-to-stable Performance or correctness regression from one stable version to another. label Jul 15, 2020
@spastorino
Copy link
Member

Assigning P-medium as discussed as part of the Prioritization Working Group procedure and removing I-prioritize.

@spastorino spastorino added P-medium Medium priority and removed I-prioritize Issue: Indicates that prioritization has been requested for this issue. labels Jul 15, 2020
@lcnr lcnr mentioned this issue Apr 27, 2021
Closed
@FabianWolff FabianWolff mentioned this issue May 6, 2021
Merged
Dylan-DPC-zz pushed a commit to Dylan-DPC-zz/rust that referenced this issue May 10, 2021
@Dylan-DPC
Rollup merge of rust-lang#85012 - FabianWolff:struct-rec, r=davidtwco
9243c1e 
Fix stack overflow when checking for structural recursion

This pull request aims to fix rust-lang#74224 and fix rust-lang#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.
@bors bors closed this as completed in d4d129d May 11, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
C-bug Category: This is a bug. I-hang Issue: The compiler never terminates, due to infinite loops, deadlock, livelock, etc. P-medium Medium priority regression-from-stable-to-stable Performance or correctness regression from one stable version to another. T-compiler Relevant to the compiler team, which will review and decide on the PR/issue.
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Fix stack overflow when checking for structural recursion FabianWolff/rust
4 participants
@spastorino @wesleywiser @jonas-schievink @tmiasko