Drop

Rust runs destructors automatically when a value goes out of scope — RAII, the way C++ does it but enforced by ownership instead of by convention. The default destructor for our list is correct but recursive, and a long list overflows the stack. We need to write a non-recursive Drop.

1. 01
   The default Drop for List drops head, which drops the Box<Node>, which drops the Node, which drops next, which drops the next Box<Node>, and so on. Every step is one stack frame. With a long list you blow the stack before any node is freed.

   // conceptually, the auto-generated Drop:
   impl Drop for List {
       fn drop(&mut self) {
           // drop self.head, which recurses into the Box<Node>...
       }
   }

2. 02
   Write Drop by hand. Walk the list with a while let loop, taking each link out by value with mem::replace, dropping it explicitly when the loop body ends. No recursion, constant stack usage.

   use std::mem;
   
   impl Drop for List {
       fn drop(&mut self) {
           let mut cur = mem::replace(&mut self.head, Link::Empty);
           while let Link::More(mut node) = cur {
               cur = mem::replace(&mut node.next, Link::Empty);
               // node falls out of scope here, freeing its Box.
           }
       }
   }

3. 03
   Why mem::replace again? When the while let binds node, we own the Box<Node>. We need to extract node.next (to keep iterating) before the box is dropped, but the box is about to disappear at the end of the iteration. Replacing node.next with Empty first means dropping the box doesn't recurse into next.

   // trace of the loop, list = [1, 2, 3]:
   // iter 1: cur = More(node{1, next: More(node{2, ...})})
   //         -> cur = More(node{2, next: More(node{3, ...})})
   //         -> drop node{1}
   // iter 2: -> cur = More(node{3, next: Empty})
   //         -> drop node{2}
   // iter 3: -> cur = Empty
   //         -> drop node{3}
   // loop exits.