Skip to content

is_type_structurally_recursive diverges on some structurally recursive types #74224

Closed
@tmiasko

Description

@tmiasko

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

Metadata

Metadata

Assignees

No one assigned

    Labels

    C-bugCategory: This is a bug.I-hangIssue: The compiler never terminates, due to infinite loops, deadlock, livelock, etc.P-mediumMedium priorityT-compilerRelevant to the compiler team, which will review and decide on the PR/issue.regression-from-stable-to-stablePerformance or correctness regression from one stable version to another.

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions