Repository: rust
Issue: Recursive Drop causes stack overflow even for object trees
Labels: C-enhancement,A-destructors,T-lang,A-docs

The issue seems to be that the way Drop is currently compiled is fatally flawed for recursive data structures.

The following code doesn't seem to have an fundamental issues that would cause it to fail, but it ends up causing a stack overflow, even for the version which uses Box instead of CustomBox.

```rust
use std::alloc::{alloc, dealloc, Layout, handle_alloc_error};
use std::ptr::{NonNull, drop_in_place, write};
use std::mem::drop;
use std::borrow::Borrow;

struct CustomBox<T> {
    wrapped: NonNull<T>
}

impl<T> CustomBox<T> {
    fn new(data: T) -> CustomBox<T> {
        let wrapped = unsafe {
            let layout = Layout::new::<T>();
            let memory = alloc(layout);
            if memory.is_null() {
                handle_alloc_error(layout);
            }
            let result = NonNull::new_unchecked(memory as *mut T);
            write(result.as_ptr(), data);
            result
        };
        CustomBox {
            wrapped
        }
    }

    fn borrow(&self) -> &T {
        unsafe {
            self.wrapped.as_ref()
        }
    }
}


impl<T> Drop for CustomBox<T> {
    fn drop(&mut self) {
        let layout = Layout::new::<T>();
        unsafe {
            drop_in_place(self.wrapped.as_ptr());
            dealloc(self.wrapped.as_ptr() as *mut u8, layout);
        }
    }
}

macro_rules! create_linked_list {
    ($name:ident, $box_type:ident) => {
        struct $name {
            data: u32,
            next: Option<$box_type<$name>>
        }

        impl $name {
            fn new(size: usize) -> Option<$box_type<$name>> {
                let mut result: Option<$box_type<$name>> = None;
                for i in 0..size {
                    let new_node = $box_type::new($name {
                        data: i as u32,
                        next: result.take()
                    });

                    result = Some(new_node);
                }

                result
            }

            fn sum(mut list: &Option<$box_type<$name>>) -> u64 {
                let mut result = 0;
                while let Some(node) = list.as_ref() {
                    let node_ref: &$name = node.borrow();
                    result += node_ref.data as u64;
                    list = &node_ref.next;
                }
                result
            }
        }
    };
}

create_linked_list!(LinkedList, CustomBox);
create_linked_list!(BoxLinkedList, Box);


fn main() {
    let list = BoxLinkedList::new(10_000_000);
    println!("{}", BoxLinkedList::sum(&list));
    println!("Trying to drop normal Box");
    drop(list);
    println!("Dropped successfully.");

    let list = LinkedList::new(10_000_000);
    println!("{}", LinkedList::sum(&list));
    println!("Trying to drop CustomBox");
    drop(list);
    println!("Dropped successfully.");
}
```

I expected to see this happen: It should have run this code sample and printed each println.

Instead, this happened: It crashes when drop(list) is called the first time.

Currently, the LinkedList implementation in `std::collections` seems to explicitly deal with deallocating nodes without recursion so it is not affected.

I'm not sure if this was an intentional design decision or not, but if it it was intentional, it should be better documented, there isn't much indication in the [official docs](https://doc.rust-lang.org/std/ops/trait.Drop.html) that dropping is actually done as non-tail call recursive functions.

One way to potentially fix this could be to make a `lazy_drop_in_place ` macro which has the same signature as `drop_in_place`, except that instead of immediately dropping that item, it instead saves these pointers at the top of the stack (which is why this should be a macro instead of a function) in a static sized buffer.

This API would not allow variable size deallocations, but it would solve the problem since then then the compiler could avoid recursion for things like linked lists.

## Meta

`rustc --version --verbose`:

```
rustc 1.33.0-nightly (e2f221c75 2019-01-15)
binary: rustc
commit-hash: e2f221c75932de7a29845c8d6f1f73536ad00c41
commit-date: 2019-01-15
host: x86_64-pc-windows-msvc
release: 1.33.0-nightly
LLVM version: 8.0
```

Backtrace:

```
   Compiling large-stack-drop v0.1.0 (C:\codedump\alloc-serialize\large-stack-drop)
    Finished release [optimized] target(s) in 0.43s
     Running `target\release\large-stack-drop.exe`
49999995000000
Trying to drop normal Box

thread 'main' has overflowed its stack
error: process didn't exit successfully: `target\release\large-stack-drop.exe` (exit code: 0xc00000fd, STATUS_STACK_OVERFLOW)
```