Dropping linked list without growing stack

tutorials
1

This can be implemented with tail calls (unstable feature as of now) but with some difficulty. Presented is the full solution.

#![expect(incomplete_features)]
#![feature(explicit_tail_calls)]


struct ScreamOnDrop(i32);
impl Drop for ScreamOnDrop {
    fn drop(&mut self) {
        println!("Dropping #{}", self.0);
    }
}



// The list is actually defined as usual.
struct LinkedList {
    now: ScreamOnDrop,
    // any data fields can be added here...
    next: Option<Box<LinkedList>>
}

impl LinkedList {
    // Now, we get to something unusual.
    // We are going to tail call dropping the next list element.
    //   It must have signature of Fn(LinkedList) -> ().
    //   Therefore, we cannot call it from anything but Fn(LinkedList) -> ();
    //     this mandates a `Self::drop` inherent function.

    fn drop(mut self) {
        if let Some(tail) = self.next.take() {
            // We got a Box<LinkedList>. It does not have inherent `drop` so
            //   we must dereference it.
            let tail: LinkedList = *tail;

            // Before the call starts, every other field in `self` is dropped.
            become tail.drop()
        }
        // else { panic!("uncomment to see that stack does not grow") }
    }
}

// We need to route Drop implementation to the inherent function.
// `Drop::drop` only gives us a mutable reference, so only elements from
//   the 2nd onwards will be dropped through inherent `LinkedList::drop`.
impl Drop for LinkedList {
    fn drop(&mut self) {
        // Checking if there is any list tail.
        // Other fields will be handled by the compiler automatically.
        if let Some(tail) = self.next.take() {
            (*tail).drop();  // tail call conditions are not met here
        }
    }
}


fn main() {
    let mut list = None;
    for i in 0..5 {
        let next_node = LinkedList { now: ScreamOnDrop(5 - i), next: list };
        list = Some(Box::new(next_node));
    }
}

It has somewhat unusual drop order:

Dropping #1
Dropping #2
Dropping #3
Dropping #4
Dropping #0
2

I think that should be equivalent to the following (which doesn't use unstable features):

struct ScreamOnDrop(i32);
impl Drop for ScreamOnDrop {
    fn drop(&mut self) {
        println!("Dropping #{}", self.0);
    }
}

// The list is actually defined as usual.
struct LinkedList {
    now: ScreamOnDrop,
    // any data fields can be added here...
    next: Option<Box<LinkedList>>
}

impl Drop for LinkedList {
    fn drop(&mut self) {
        println!("I was called. Empty tail? {}", self.next.is_none());
        while let Some(mut tail) = self.next.take() {
            self.next = tail.next.take();
        }
    }
}


fn main() {
    let mut list = None;
    for i in 0..5 {
        let next_node = LinkedList { now: ScreamOnDrop(5 - i), next: list };
        list = Some(Box::new(next_node));
    }
    println!("End of main");
}

(I added some printlns to see what happens. It has the same drop order as yours AFAICT.)

4 Likes
3

Perhaps you're looking for the discussion in Drop - Learning Rust With Entirely Too Many Linked Lists ?

2 Likes