RFC: Can we make drop glue for recursive types not stack overflow?

Issue by bblum
Thursday Aug 08, 2013 at 20:01 GMT

For earlier discussion, see https://github.com/rust-lang/rust/issues/8399

This issue was labelled with: A-codegen, B-RFC, E-hard, I-wishlist in the Rust repository

Example 2014-02-23

struct Foo { data: int, next: Option<~Foo> }

fn main() {
    let mut foo = Some(~Foo { data: 0, next: None });
    for i in range(0, 17_000_000) {
        if i % 1000000 == 0 {
            error!("{}", i);
        }
        foo = Some(~Foo { data: i, next: foo.take() });
    }
}

Original example

use std::cell::Cell;

struct Foo { data: int, next: Option<~Foo> }

fn main() {
    let foo = Cell::new(Foo { data: 0, next: None });
    let mut i = 0;
    do 17_000_000.times {
        i += 1;
        if i % 1000000 == 0 {
            error!("%d", i);
        }
        foo.put_back(Foo { data: i, next: Some(~foo.take()) });
    }
}

Start by reading the earlier discussion in Rust issue 8399 and reproducing the recursive Foo example from this issue. Determine how recursive drop glue causes stack overflow at the demonstrated depth, then define and document a viable design for avoiding it.