Skip to content

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

New issue

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

#

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

Already on GitHub? # to your account

Jump to bottom
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
# for free to join this conversation on GitHub. Already have an account? # 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