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

Infinite loop/stack overflow in rustc (dropck) on non-regular data type #22443

Closed
miv-ableton opened this issue Feb 17, 2015 · 6 comments · Fixed by #22777
Closed

Infinite loop/stack overflow in rustc (dropck) on non-regular data type #22443

miv-ableton opened this issue Feb 17, 2015 · 6 comments · Fixed by #22777
Assignees
@pnkfelix
Labels
A-destructors Area: Destructors (`Drop`, …)

Comments

@miv-ableton
Copy link

The compiler goes into an infinite loop compiling this code (an incomplete finger tree implementation):

struct Digit<T> {
    elem: T,
    next: Option<Box<Digit<T>>>
}

enum Node<T> {
    Node2(T, T),
    Node3(T, T, T)
}

enum FingerTree<T> {
    Empty,
    Single(T),
    Deep(Digit<T>, Box<FingerTree<Node<T>>>, Digit<T>)
}

impl <T> FingerTree<T> {
    fn dequeue(&self, elem: T) -> FingerTree<T> {
        match self {
            Empty => FingerTree::Single(elem)
        }
    }
}

fn main() {
    let ft = FingerTree::Empty;
    let ft2 = ft.dequeue(123);
}

Tested with latest nightly. I can also cause this to happen by pasting this into the box on the rust-lang homepage.
@miv-ableton
Copy link
Author

The bug seems to be caused by the recursive datatype:

    Deep(Digit<T>, Box<FingerTree<Node<T>>>, Digit<T>)

If I remove the Boxed thing, it compiles and runs.

@miv-ableton miv-ableton changed the title Infinite loop in compiler triggered by relatively simple code Infinite loop/stack overflow in rustc Feb 17, 2015
@japaric
Copy link
Member

japaric commented Feb 17, 2015

Reduced test cases:

 struct Digit<T> {
     elem: T,
 }

 enum Node<T> {}

 enum FingerTree<T> {
     Single(T),
     Deep(
-        Digit<T>,
         Box<FingerTree<Node<T>>>,
+        Digit<T>,
     )
 }

 fn main() {
     let ft = FingerTree::Single(1);
 }

The one with Digit<T> before the Box hangs, and the other one with Digit<T> after the Box ends up with a "thread 'rustc' has overflowed its stack" error. Upon inspecting the RUST_LOG=rustc_typeck of the second example, I can see that the infinite recursion happens in the new dropck (cc @pnkfelix):

DEBUG:rustc_typeck::check::dropck: check_safety_of_destructor_if_necessary typ: FingerTree<i32> scope: Remainder(BlockRemainder { block: 37, first_statement_index: 0 })
DEBUG:rustc_typeck::check::dropck: iterate_over_potentially_unsafe_regions_in_type typ: FingerTree<i32> scope: Remainder(BlockRemainder { block: 37, first_statement_index: 0 }) opt_dtor: None
DEBUG:rustc_typeck::check::dropck: typ: FingerTree<i32> has no dtor, and thus is uninteresting
DEBUG:rustc_typeck::check::dropck: iterate_over_potentially_unsafe_regions_in_type  typ: i32 scope: Remainder(BlockRemainder { block: 37, first_statement_index: 0 }) opt_dtor: None
DEBUG:rustc_typeck::check::dropck: typ: i32 has no dtor, and thus is uninteresting
DEBUG:rustc_typeck::check::dropck: iterate_over_potentially_unsafe_regions_in_type  typ: Box<FingerTree<Node<i32>>> scope: Remainder(BlockRemainder { block: 37, first_statement_index: 0 }) opt_dtor: None
DEBUG:rustc_typeck::check::dropck: typ: Box<FingerTree<Node<i32>>> has no dtor, and thus is uninteresting
DEBUG:rustc_typeck::check::dropck: iterate_over_potentially_unsafe_regions_in_type  typ: FingerTree<Node<i32>> scope: Remainder(BlockRemainder { block: 37, first_statement_index: 0 }) opt_dtor: None
DEBUG:rustc_typeck::check::dropck: typ: FingerTree<Node<i32>> has no dtor, and thus is uninteresting
DEBUG:rustc_typeck::check::dropck: iterate_over_potentially_unsafe_regions_in_type   typ: Node<i32> scope: Remainder(BlockRemainder { block: 37, first_statement_index: 0 }) opt_dtor: None
DEBUG:rustc_typeck::check::dropck: typ: Node<i32> has no dtor, and thus is uninteresting
DEBUG:rustc_typeck::check::dropck: iterate_over_potentially_unsafe_regions_in_type   typ: Box<FingerTree<Node<Node<i32>>>> scope: Remainder(BlockRemainder { block: 37, first_statement_index: 0 }) opt_dtor: None
DEBUG:rustc_typeck::check::dropck: typ: Box<FingerTree<Node<Node<i32>>>> has no dtor, and thus is uninteresting
DEBUG:rustc_typeck::check::dropck: iterate_over_potentially_unsafe_regions_in_type   typ: FingerTree<Node<Node<i32>>> scope: Remainder(BlockRemainder { block: 37, first_statement_index: 0 }) opt_dtor: None
DEBUG:rustc_typeck::check::dropck: typ: FingerTree<Node<Node<i32>>> has no dtor, and thus is uninteresting
DEBUG:rustc_typeck::check::dropck: iterate_over_potentially_unsafe_regions_in_type    typ: Node<Node<i32>> scope: Remainder(BlockRemainder { block: 37, first_statement_index: 0 }) opt_dtor: None
DEBUG:rustc_typeck::check::dropck: typ: Node<Node<i32>> has no dtor, and thus is uninteresting
DEBUG:rustc_typeck::check::dropck: iterate_over_potentially_unsafe_regions_in_type    typ: Box<FingerTree<Node<Node<Node<i32>>>>> scope: Remainder(BlockRemainder { block: 37, first_statement_index: 0 }) opt_dtor: None
DEBUG:rustc_typeck::check::dropck: typ: Box<FingerTree<Node<Node<Node<i32>>>>> has no dtor, and thus is uninteresting
DEBUG:rustc_typeck::check::dropck: iterate_over_potentially_unsafe_regions_in_type    typ: FingerTree<Node<Node<Node<i32>>>> scope: Remainder(BlockRemainder { block: 37, first_statement_index: 0 }) opt_dtor: None
DEBUG:rustc_typeck::check::dropck: typ: FingerTree<Node<Node<Node<i32>>>> has no dtor, and thus is uninteresting
DEBUG:rustc_typeck::check::dropck: iterate_over_potentially_unsafe_regions_in_type     typ: Node<Node<Node<i32>>> scope: Remainder(BlockRemainder { block: 37, first_statement_index: 0 }) opt_dtor: None
DEBUG:rustc_typeck::check::dropck: typ: Node<Node<Node<i32>>> has no dtor, and thus is uninteresting
DEBUG:rustc_typeck::check::dropck: iterate_over_potentially_unsafe_regions_in_type     typ: Box<FingerTree<Node<Node<Node<Node<i32>>>>>> scope: Remainder(BlockRemainder { block: 37, first_statement_index: 0 }) opt_dtor: None
DEBUG:rustc_typeck::check::dropck: typ: Box<FingerTree<Node<Node<Node<Node<i32>>>>>> has no dtor, and thus is uninteresting
DEBUG:rustc_typeck::check::dropck: iterate_over_potentially_unsafe_regions_in_type     typ: FingerTree<Node<Node<Node<Node<i32>>>>> scope: Remainder(BlockRemainder { block: 37, first_statement_index: 0 }) opt_dtor: None
DEBUG:rustc_typeck::check::dropck: typ: FingerTree<Node<Node<Node<Node<i32>>>>> has no dtor, and thus is uninteresting
DEBUG:rustc_typeck::check::dropck: iterate_over_potentially_unsafe_regions_in_type      typ: Node<Node<Node<Node<i32>>>> scope: Remainder(BlockRemainder { block: 37, first_statement_index: 0 }) opt_dtor: None
DEBUG:rustc_typeck::check::dropck: typ: Node<Node<Node<Node<i32>>>> has no dtor, and thus is uninteresting
DEBUG:rustc_typeck::check::dropck: iterate_over_potentially_unsafe_regions_in_type      typ: Box<FingerTree<Node<Node<Node<Node<Node<i32>>>>>>> scope: Remainder(BlockRemainder { block: 37, first_statement_index: 0 }) opt_dtor: None
DEBUG:rustc_typeck::check::dropck: typ: Box<FingerTree<Node<Node<Node<Node<Node<i32>>>>>>> has no dtor, and thus is uninteresting
DEBUG:rustc_typeck::check::dropck: iterate_over_potentially_unsafe_regions_in_type      typ: FingerTree<Node<Node<Node<Node<Node<i32>>>>>> scope: Remainder(BlockRemainder { block: 37, first_statement_index: 0 }) opt_dtor: None
DEBUG:rustc_typeck::check::dropck: typ: FingerTree<Node<Node<Node<Node<Node<i32>>>>>> has no dtor, and thus is uninteresting
DEBUG:rustc_typeck::check::dropck: iterate_over_potentially_unsafe_regions_in_type       typ: Node<Node<Node<Node<Node<i32>>>>> scope: Remainder(BlockRemainder { block: 37, first_statement_index: 0 }) opt_dtor: None
DEBUG:rustc_typeck::check::dropck: typ: Node<Node<Node<Node<Node<i32>>>>> has no dtor, and thus is uninteresting
DEBUG:rustc_typeck::check::dropck: iterate_over_potentially_unsafe_regions_in_type       typ: Box<FingerTree<Node<Node<Node<Node<Node<Node<i32>>>>>>>> scope: Remainder(BlockRemainder { block: 37, first_statement_index: 0 }) opt_dtor: None
DEBUG:rustc_typeck::check::dropck: typ: Box<FingerTree<Node<Node<Node<Node<Node<Node<i32>>>>>>>> has no dtor, and thus is uninteresting
DEBUG:rustc_typeck::check::dropck: iterate_over_potentially_unsafe_regions_in_type       typ: FingerTree<Node<Node<Node<Node<Node<Node<i32>>>>>>> scope: Remainder(BlockRemainder { block: 37, first_statement_index: 0 }) opt_dtor: None
DEBUG:rustc_typeck::check::dropck: typ: FingerTree<Node<Node<Node<Node<Node<Node<i32>>>>>>> has no dtor, and thus is uninteresting
DEBUG:rustc_typeck::check::dropck: iterate_over_potentially_unsafe_regions_in_type        typ: Node<Node<Node<Node<Node<Node<i32>>>>>> scope: Remainder(BlockRemainder { block: 37, first_statement_index: 0 }) opt_dtor: None
DEBUG:rustc_typeck::check::dropck: typ: Node<Node<Node<Node<Node<Node<i32>>>>>> has no dtor, and thus is uninteresting
DEBUG:rustc_typeck::check::dropck: iterate_over_potentially_unsafe_regions_in_type        typ: Box<FingerTree<Node<Node<Node<Node<Node<Node<Node<i32>>>>>>>>> scope: Remainder(BlockRemainder { block: 37, first_statement_index: 0 }) opt_dtor: None
DEBUG:rustc_typeck::check::dropck: typ: Box<FingerTree<Node<Node<Node<Node<Node<Node<Node<i32>>>>>>>>> has no dtor, and thus is uninteresting
DEBUG:rustc_typeck::check::dropck: iterate_over_potentially_unsafe_regions_in_type        typ: FingerTree<Node<Node<Node<Node<Node<Node<Node<i32>>>>>>>> scope: Remainder(BlockRemainder { block: 37, first_statement_index: 0 }) opt_dtor: None
DEBUG:rustc_typeck::check::dropck: typ: FingerTree<Node<Node<Node<Node<Node<Node<Node<i32>>>>>>>> has no dtor, and thus is uninteresting
DEBUG:rustc_typeck::check::dropck: iterate_over_potentially_unsafe_regions_in_type         typ: Node<Node<Node<Node<Node<Node<Node<i32>>>>>>> scope: Remainder(BlockRemainder { block: 37, first_statement_index: 0 }) opt_dtor: None
DEBUG:rustc_typeck::check::dropck: typ: Node<Node<Node<Node<Node<Node<Node<i32>>>>>>> has no dtor, and thus is uninteresting
DEBUG:rustc_typeck::check::dropck: iterate_over_potentially_unsafe_regions_in_type         typ: Box<FingerTree<Node<Node<Node<Node<Node<Node<Node<Node<i32>>>>>>>>>> scope: Remainder(BlockRemainder { block: 37, first_statement_index: 0 }) opt_dtor: None
DEBUG:rustc_typeck::check::dropck: typ: Box<FingerTree<Node<Node<Node<Node<Node<Node<Node<Node<i32>>>>>>>>>> has no dtor, and thus is uninteresting
DEBUG:rustc_typeck::check::dropck: iterate_over_potentially_unsafe_regions_in_type         typ: FingerTree<Node<Node<Node<Node<Node<Node<Node<Node<i32>>>>>>>>> scope: Remainder(BlockRemainder { block: 37, first_statement_index: 0 }) opt_dtor: None
DEBUG:rustc_typeck::check::dropck: typ: FingerTree<Node<Node<Node<Node<Node<Node<Node<Node<i32>>>>>>>>> has no dtor, and thus is uninteresting
DEBUG:rustc_typeck::check::dropck: iterate_over_potentially_unsafe_regions_in_type          typ: Node<Node<Node<Node<Node<Node<Node<Node<i32>>>>>>>> scope: Remainder(BlockRemainder { block: 37, first_statement_index: 0 }) opt_dtor: None
DEBUG:rustc_typeck::check::dropck: typ: Node<Node<Node<Node<Node<Node<Node<Node<i32>>>>>>>> has no dtor, and thus is uninteresting
DEBUG:rustc_typeck::check::dropck: iterate_over_potentially_unsafe_regions_in_type          typ: Box<FingerTree<Node<Node<Node<Node<Node<Node<Node<Node<Node<i32>>>>>>>>>>> scope: Remainder(BlockRemainder { block: 37, first_statement_index: 0 }) opt_dtor: None
DEBUG:rustc_typeck::check::dropck: typ: Box<FingerTree<Node<Node<Node<Node<Node<Node<Node<Node<Node<i32>>>>>>>>>>> has no dtor, and thus is uninteresting
DEBUG:rustc_typeck::check::dropck: iterate_over_potentially_unsafe_regions_in_type          typ: FingerTree<Node<Node<Node<Node<Node<Node<Node<Node<Node<i32>>>>>>>>>> scope: Remainder(BlockRemainder { block: 37, first_statement_index: 0 }) opt_dtor: None
DEBUG:rustc_typeck::check::dropck: typ: FingerTree<Node<Node<Node<Node<Node<Node<Node<Node<Node<i32>>>>>>>>>> has no dtor, and thus is uninteresting
DEBUG:rustc_typeck::check::dropck: iterate_over_potentially_unsafe_regions_in_type           typ: Node<Node<Node<Node<Node<Node<Node<Node<Node<i32>>>>>>>>> scope: Remainder(BlockRemainder { block: 37, first_statement_index: 0 }) opt_dtor: None
DEBUG:rustc_typeck::check::dropck: typ: Node<Node<Node<Node<Node<Node<Node<Node<Node<i32>>>>>>>>> has no dtor, and thus is uninteresting
DEBUG:rustc_typeck::check::dropck: iterate_over_potentially_unsafe_regions_in_type           typ: Box<FingerTree<Node<Node<Node<Node<Node<Node<Node<Node<Node<Node<i32>>>>>>>>>>>> scope: Remainder(BlockRemainder { block: 37, first_statement_index: 0 }) opt_dtor: None
DEBUG:rustc_typeck::check::dropck: typ: Box<FingerTree<Node<Node<Node<Node<Node<Node<Node<Node<Node<Node<i32>>>>>>>>>>>> has no dtor, and thus is uninteresting
DEBUG:rustc_typeck::check::dropck: iterate_over_potentially_unsafe_regions_in_type           typ: FingerTree<Node<Node<Node<Node<Node<Node<Node<Node<Node<Node<i32>>>>>>>>>>> scope: Remainder(BlockRemainder { block: 37, first_statement_index: 0 }) opt_dtor: None
DEBUG:rustc_typeck::check::dropck: typ: FingerTree<Node<Node<Node<Node<Node<Node<Node<Node<Node<Node<i32>>>>>>>>>>> has no dtor, and thus is uninteresting
DEBUG:rustc_typeck::check::dropck: iterate_over_potentially_unsafe_regions_in_type            typ: Node<Node<Node<Node<Node<Node<Node<Node<Node<Node<i32>>>>>>>>>> scope: Remainder(BlockRemainder { block: 37, first_statement_index: 0 }) opt_dtor: None
DEBUG:rustc_typeck::check::dropck: typ: Node<Node<Node<Node<Node<Node<Node<Node<Node<Node<i32>>>>>>>>>> has no dtor, and thus is uninteresting
DEBUG:rustc_typeck::check::dropck: iterate_over_potentially_unsafe_regions_in_type            typ: Box<FingerTree<Node<Node<Node<Node<Node<Node<Node<Node<Node<Node<Node<i32>>>>>>>>>>>>> scope: Remainder(BlockRemainder { block: 37, first_statement_index: 0 }) opt_dtor: None
DEBUG:rustc_typeck::check::dropck: typ: Box<FingerTree<Node<Node<Node<Node<Node<Node<Node<Node<Node<Node<Node<i32>>>>>>>>>>>>> has no dtor, and thus is uninteresting
DEBUG:rustc_typeck::check::dropck: iterate_over_potentially_unsafe_regions_in_type            typ: FingerTree<Node<Node<Node<Node<Node<Node<Node<Node<Node<Node<Node<i32>>>>>>>>>>>> scope: Remainder(BlockRemainder { block: 37, first_statement_index: 0 }) opt_dtor: None
DEBUG:rustc_typeck::check::dropck: typ: FingerTree<Node<Node<Node<Node<Node<Node<Node<Node<Node<Node<Node<i32>>>>>>>>>>>> has no dtor, and thus is uninteresting
DEBUG:rustc_typeck::check::dropck: iterate_over_potentially_unsafe_regions_in_type             typ: Node<Node<Node<Node<Node<Node<Node<Node<Node<Node<Node<i32>>>>>>>>>>> scope: Remainder(BlockRemainder { block: 37, first_statement_index: 0 }) opt_dtor: None
DEBUG:rustc_typeck::check::dropck: typ: Node<Node<Node<Node<Node<Node<Node<Node<Node<Node<Node<i32>>>>>>>>>>> has no dtor, and thus is uninteresting

@pnkfelix pnkfelix self-assigned this Feb 17, 2015
@pnkfelix pnkfelix added the A-destructors Area: Destructors (`Drop`, …) label Feb 17, 2015
@pnkfelix
Copy link
Member

Note that

 enum Tree<T> {
     Single(T),
     Deep(Box<Tree<Node<T>>>)
}

and variations thereof, is a non-regular data type (see also polymorphic recursion).

Rust doesn't handle such types very well, because it implements type-parametric code via monomorphization, but you need infinite codegen to monomorphize non-regular data types in general.

I should (and will) put a recursion counter into dropck so that we at least do not infinite loop in such cases.

@miv-ableton
Copy link
Author

Thanks for the update. Yes, the restriction makes sense. I'll try and implement the algorithm using some runtime typecast "Any" magic.

@pnkfelix pnkfelix changed the title Infinite loop/stack overflow in rustc Infinite loop/stack overflow in rustc (dropck) on non-regular data type Feb 17, 2015
@pnkfelix
Copy link
Member

(this could be considered part of #22321, though really it probably should be given slightly higher priority given the undesirability of infinite looping here.)

@pnkfelix
Copy link
Member

@miv-ableton by the way, you probably do not need to drop all the way down to working in terms of Any; I bet you could make a trait-object abstraction for FingerTree that would work.

@pnkfelix pnkfelix mentioned this issue Feb 24, 2015
Merged
pnkfelix added a commit to pnkfelix/rust that referenced this issue Feb 26, 2015
@pnkfelix
Add regression test for issue 22443.
ed18e6b 
Fix rust-lang#22443.
steveklabnik added a commit to steveklabnik/rust that referenced this issue Feb 26, 2015
@steveklabnik
Rollup merge of rust-lang#22777 - pnkfelix:issue-22443, r=nikomatsakis
41c6c35 
Check for unbounded recursion during dropck.

Such recursion can be introduced by the erroneous use of non-regular types (aka types employing polymorphic recursion), which Rust does not support.

Fix rust-lang#22443
pnkfelix added a commit to pnkfelix/rust that referenced this issue Mar 1, 2015
@pnkfelix
Add regression tests for issue 22443.
180ef47 
Fix rust-lang#22443.
Manishearth added a commit to Manishearth/rust that referenced this issue Mar 1, 2015
@Manishearth
Rollup merge of rust-lang#22777 - pnkfelix:issue-22443, r=nikomatsakis
85bdb31 
 Check for unbounded recursion during dropck.

Such recursion can be introduced by the erroneous use of non-regular types (aka types employing polymorphic recursion), which Rust does not support.

Fix rust-lang#22443
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@pnkfelix pnkfelix

Labels
A-destructors Area: Destructors (`Drop`, …)
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Check for unbounded recursion during dropck pnkfelix/rust
3 participants
@pnkfelix @japaric @miv-ableton