Use regular reference instead of `Box` in recursive data structures

Question

I am new to Rust. When I read chapter 15 of The Rust Programming Language, I failed to know why one should use Boxes in recursive data structures instead of regular references. 15.1 of the book explains that indirection is required to avoid infinite-sized structures, but it does not explain why to use Box.

#[derive(Debug)]
enum FunctionalList<'a> {
    Cons(u32, &'a FunctionalList<'a>),
    Nil,
}

use FunctionalList::{Cons, Nil};

fn main() {
    let list = Cons(1, &Cons(2, &Cons(3, &Nil)));

    println!("{:?}", list);
}

The code above compiles and produces the desired output. It seems that using FunctionalList to store a small amount of data on stack works perfectly well. Does this code cause troubles?

Answer 1

It is true that the FunctionalList works in this simple case. However, we will run into some difficulties if we try to use this structure in other ways. For instance, suppose we tried to construct a FunctionalList and then return it from a function:

#[derive(Debug)]
enum FunctionalList<'a> {
    Cons(u32, &'a FunctionalList<'a>),
    Nil,
}

use FunctionalList::{Cons, Nil};

fn make_list(x: u32) -> FunctionalList {
    return Cons(x, &Cons(x + 1, &Cons(x + 2, &Nil)));
}

fn main() {
    let list = make_list(1);

    println!("{:?}", list);
}

This results in the following compile error:

error[E0106]: missing lifetime specifier
 --> src/main.rs:9:25
  |
9 | fn make_list(x: u32) -> FunctionalList {
  |                         ^^^^^^^^^^^^^^ help: consider giving it an explicit bounded or 'static lifetime: `FunctionalList + 'static`

If we follow the hint and add a 'static lifetime, then we instead get this error:

error[E0515]: cannot return value referencing temporary value
  --> src/main.rs:10:12
   |
10 |     return Cons(x, &Cons(x + 1, &Cons(x + 2, &Nil)));
   |            ^^^^^^^^^^^^^^^^^^^^^^-----------------^^
   |            |                     |
   |            |                     temporary value created here
   |            returns a value referencing data owned by the current function

The issue is that the inner FunctionalList values here are owned by implicit temporary variables whose scope ends at the end of the make_list function. These values would thus be dropped at the end of the function, leaving dangling references to them, which Rust disallows, hence the borrow checker rejects this code.

In contrast, if FunctionalList had been defined to Box its FunctionalList component, then ownership would have been moved from the temporary value into the containing FunctionalList, and we would have been able to return it without any problem.

With your original FunctionalList, the thing we have to think about is that every value in Rust has to have an owner somewhere; and so if, as in this case, the FunctionaList is not the owner of its inner FunctionalLists, then that ownership has to reside somewhere else. In your example, that owner was an implicit temporary variable, but in more complex situations we could use a different kind of external owner. Here's an example of using a TypedArena (from the typed-arena crate) to own the data, so that we can still implement a variation of the make_list function:

use typed_arena::Arena;

#[derive(Debug)]
enum FunctionalList<'a> {
    Cons(u32, &'a FunctionalList<'a>),
    Nil,
}

use FunctionalList::{Cons, Nil};

fn make_list<'a>(x: u32, arena: &'a Arena<FunctionalList<'a>>) -> &mut FunctionalList<'a> {
    let l0 = arena.alloc(Nil);
    let l1 = arena.alloc(Cons(x + 2, l0));
    let l2 = arena.alloc(Cons(x + 1, l1));
    let l3 = arena.alloc(Cons(x, l2));
    return l3;
}

fn main() {
    let arena = Arena::new();
    let list = make_list(1, &arena);

    println!("{:?}", list);
}

In this case, we adapted the return type of make_list to return only a mutable reference to a FunctionalList, instead of returning an owned FunctionalList, since now the ownership resides in the arena.