Who owns a Box in the heap?

Question

I am learning Rust right now. I want to check my understanding of ownership in rust. I am confused with ownership and borrowing concepts in recursive structure. I see this code in rustbyexample.com

// Allow Cons and Nil to be referred to without namespacing
use List::{Cons, Nil};

// A linked list node, which can take on any of these two variants
enum List {
    // Cons: Tuple struct that wraps an element and a pointer to the next node
    Cons(u32, Box<List>),
    // Nil: A node that signifies the end of the linked list
    Nil,
}

// Methods can be attached to an enum
impl List {
    // Create an empty list
    fn new() -> List {
        // `Nil` has type `List`
        Nil
    }

    // Consume a list, and return the same list with a new element at its front
    fn prepend(self, elem: u32) -> List {
        // `Cons` also has type List
        Cons(elem, Box::new(self))
    }

    // Return the length of the list
    fn len(&self) -> u32 {
        // `self` has to be matched, because the behavior of this method
        // depends on the variant of `self`
        // `self` has type `&List`, and `*self` has type `List`, matching on a
        // concrete type `T` is preferred over a match on a reference `&T`
        match *self {
            // Can't take ownership of the tail, because `self` is borrowed;
            // instead take a reference to the tail
            Cons(_, ref tail) => 1 + tail.len(),
            // Base Case: An empty list has zero length
            Nil => 0
        }
    }

    // Return representation of the list as a (heap allocated) string
    fn stringify(&self) -> String {
        match *self {
            Cons(head, ref tail) => {
                // `format!` is similar to `print!`, but returns a heap
                // allocated string instead of printing to the console
                format!("{}, {}", head, tail.stringify())
            },
            Nil => {
                format!("Nil")
            },
        }
    }
}

fn main() {
    // Create an empty linked list
    let mut list = List::new();

    // Append some elements
    list = list.prepend(1);
    list = list.prepend(2);
    list = list.prepend(3);

    // Show the final state of the list
    println!("linked list has length: {}", list.len());
    println!("{}", list.stringify());
}

How to visualize the stack and the heap of this code?

From what I have learned, prepend takes ownership of list, allocate space in heap and move the list to heap. When prepend finishes, it moves (gives ownership) the newly created list to external variable.

Is this visualization correct?

First List::new return Nil so stack will contain Nil.

After list.prepend(1) executed Nil will be in the heap at address 0x0000(assumption), stack will contain Cons(1,0x0000).

After list.prepend(2) executed Cons(1,0x0000) will be in the heap at address 0x00002(assumption), stack will contain Cons(2,0x0002).

After list.prepend(3) executed Cons(2,0x0002) will be in the heap at address 0x00004(assumption), stack will contain Cons(3,0x0004).

Now, who have the ownership of Cons(1,0x0000)? Is Cons(2,0x0002) have the ownership of Cons(1,0x0000)? Is variable in heap allowed to have ownership of a resource?

From this code I am assuming that variable in heap may have the ownership of a resource, so if Rust deallocates that variable, it will deallocate the resource too. Is this correct?

Answer 1

Box<Foo> represents a Foo instance somewhere on the heap, managed and owned by the Box object.

So in your case of a list which final value is:

let list = Cons(3, Box::new(Cons(2, Box::new(Cons(1, Box::new(Nil))))))

• list owns a List object which is a Cons variant of the enum, owning itself a u32 of value 3 and a Box<List>
• This Box<List> manages and owns a List instance: a Cons variant owning itself a 2 value and an other Box<List>
• This second Box<List> manages and owns a List instance: a Cons variant owning itself a 1 value and a Box<List>
• This last Box<List> manages and owns a List instance: a Nil variant.

So yes, the contents of a Box may own other Boxes, and when a Box is destroyed, it will properly destroy its content, which is expected to itself properly destroy its contents as well, up to the bottom of the owning tree.