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

[bblum]

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()) });
    }
}

[bblum]

This can be avoided by hand with the following destructor:

impl Drop for Foo {
    fn drop(&self) {
        let this: &mut Foo = unsafe { use std::cast; cast::transmute(self) };
        while this.next.is_some() {
            do this.next.take().map_consume |mut next| {
                this.next = next.next.take();
            };
        }
    }
}

[bblum]

Unfortunately we can't even rely on tail-call optimization in some cases, for example, a tree where each stack frame has to recurse once on each branch. I wonder if the above hand-coded destructor can be generalized.

Nominating well-covered.

[bluss]

Previous issue (solved) for DList in particular #8295

[bblum]

Oh yeah thanks for the link. I suppose I should tag this an RFC to see if we can solve it in the general case.

[thestinger]

At least with optimizations enabled this would already be a non-issue in many cases if we weren't making so many possibly invalid casts.

[bblum]

With optimizations disabled we should have well-defined behaviour too :P

[thestinger]

The behaviour would still be well-defined, it would just use a lot more memory than necessary. That's really no different than how we use a ridiculous amount of stack space everywhere else without optimizations.

[bblum]

It occurred to me on the way in this morning that this would be very hard if not impossible to do for tree-like types, struct Foo { left: Option<~Foo>, right: Option<~Foo> }.

[thestinger]

@bblum: yeah, there are cases where you fundamentally require a stack of some sort - luckily, for self-balancing binary search trees the depth is log2(length) so it's a non-issue

[catamorphism]

Just a bug (this may never get fixed)

[huonw]

Triage: no change. (I updated the example.)