Box and recursive data

Linked lists and trees need connections to values of their own type. Read structs and enums and ownership before continuing.

Why direct containment fails

This definition deliberately fails under xen check recursive_size_error.xen:

recursive_size_error.xen

struct Node { value: Int, next: Node }
fn main() {}

recursive_size_error.stderr

recursive value layout involving 'Node'

Calculating the size of one Node requires the size of its next: Node, which requires another Node, indefinitely. No finite value layout results. Recursive connections need a Box or Vec boundary.

Represent both a connection and its end

Box<Node> expresses an owned connection to another node. In Option<Box<Node>>, Some means a next node exists, and None marks the end of the list. Adding a box and expressing termination solve separate parts of the problem.

Save this as recursive_ownership.xen. prepend adds nodes and sum consumes the list:

recursive_ownership.xen

struct Node { value: Int, next: Option<Box<Node>> }
fn prepend(value: Int, tail: Option<Box<Node>>) -> Option<Box<Node>> {
    return Option.Some(box(Node { value: value, next: tail }));
}
fn sum(list: Option<Box<Node>>) -> Int {
    return match list {
        Option.Some(link) => {
            let node = link.into_inner();
            node.value + sum(node.next)
        },
        Option.None => 0,
    };
}
fn main() {
    let empty: Option<Box<Node>> = Option.None;
    let tail = prepend(20, empty);
    let list = prepend(10, tail);
    println(sum(list));
}

xen check recursive_ownership.xen
xen run recursive_ownership.xen

recursive_ownership.stdout

30

Follow ownership step by step

1. empty is a typed None. Its lack of a payload requires the explicit Option<Box<Node>> type.
2. prepend(20, empty) puts a node in a box and wraps it in Some.
3. prepend(10, tail) moves the existing tail into the new node’s next field. The caller does not use tail again.
4. sum(list) takes the list. In Some(link), link.into_inner() consumes the box and yields its Node.
5. The current integer is added to sum(node.next). None returns 0 and ends recursion.

A Box is move-only even when it contains a copyable Int. Types containing boxes, such as Option<Box<Node>>, are move-only too. This sum function takes ownership instead of borrowing the list.

Diagnose reuse after a move

The following fails under xen check moved_box_error.xen:

moved_box_error.xen

fn main() {
    let original = box(42);
    let transferred = original;
    println(original.into_inner());
}

moved_box_error.stderr

value moved here

Replace the last line with println(transferred.into_inner()); to print 42. Assigning the box to another name did not create a second box.

To read without consuming a box, consider as_ref(); to change its contents, consider as_mut() and the borrowing rules. Boxes cannot contain references, slices, or pointers. If you simply need many values of one type, a Vec<T> may match the representation you need.

Termination and cleanup

Owned values are released when a block exits, including through return, break, continue, and ?. A panic or runtime error terminates immediately without normal cleanup.

Recursive calls have a depth limit. This example explains a small connected structure; do not extend it unchanged to input of unbounded length. Consider loops and vectors for long inputs. See functions and control flow and the ownership reference for related rules.

Try it

Create a new head with prepend(5, list), pass the returned value to sum, and check that it prints 35. Then try using the old list again and identify the call that moved it.