Creating a simple linked list

Question

I'm having difficulty getting the borrow checker working for a simple iterative linked list builder.

fn main() {                                                        
    let v = vec![1,5,3,8,12,56,1230,2,1];                          
    let nodes = Vec::<Node>::with_capacity(v.len());               
    let mut root: Option<&mut Box<Node>> = None;                   
    let mut prev: &Option<&mut Box<Node>> = &None;                 

    for i in v {                                                   
        let curr = Some(&mut Box::new(Node { value: i, next: None }));
        match *prev {                                              
            Some(ref mut p) => {                                   
                p.next = curr;                                        
                prev = &mut p.next;                                
            },                                                     
            None => {                                              
                root = curr;                                          
                prev = &mut root;                                  
            }                                                      
        }                                                          
    }                                                              
}                                                                  

struct Node<'a> {                                                  
    value: i32,                                                    
    next: Option<&'a mut Box<Node<'a>>>,                           
}                         

The errors I'm receiving when I try to compile:

linked_list.rs:8:30: 8:69 error: borrowed value does not live long enough
linked_list.rs:8         let curr = Some(&mut Box::new(Node { value: i, next: None }));
                                              ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
note: in expansion of for loop expansion
linked_list.rs:7:5: 19:6 note: expansion site
linked_list.rs:4:49: 20:2 note: reference must be valid for the block suffix following statement 2 at 4:48...
linked_list.rs:4     let mut root: Option<&mut Box<Node>> = None;
linked_list.rs:5     let mut prev: &Option<&mut Box<Node>> = &None;
linked_list.rs:6 
linked_list.rs:7     for i in v {
linked_list.rs:8         let curr = Some(&mut Box::new(Node { value: i, next: None }));
linked_list.rs:9         match *prev {
                 ...
linked_list.rs:8:9: 8:71 note: ...but borrowed value is only valid for the statement at 8:8
linked_list.rs:8         let curr = Some(&mut Box::new(Node { value: i, next: None }));
                         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
linked_list.rs:8:9: 8:71 help: consider using a `let` binding to increase its lifetime
linked_list.rs:8         let curr = Some(&mut Box::new(Node { value: i, next: None }));
                         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
linked_list.rs:10:18: 10:27 error: cannot borrow immutable anonymous field `(prev:core::option::Some).0` as mutable
linked_list.rs:10             Some(ref mut p) => {
                                   ^~~~~~~~~
note: in expansion of for loop expansion
linked_list.rs:7:5: 19:6 note: expansion site
linked_list.rs:15:17: 15:28 error: cannot assign to `root` because it is borrowed
linked_list.rs:15                 root = curr;
                                  ^~~~~~~~~~~
note: in expansion of for loop expansion
linked_list.rs:7:5: 19:6 note: expansion site
linked_list.rs:16:29: 16:33 note: borrow of `root` occurs here
linked_list.rs:16                 prev = &mut root;
                                              ^~~~
note: in expansion of for loop expansion
linked_list.rs:7:5: 19:6 note: expansion site
linked_list.rs:16:29: 16:33 error: cannot borrow `root` as mutable more than once at a time
linked_list.rs:16                 prev = &mut root;
                                              ^~~~
note: in expansion of for loop expansion
linked_list.rs:7:5: 19:6 note: expansion site
linked_list.rs:16:29: 16:33 note: previous borrow of `root` occurs here; the mutable borrow prevents subsequent moves, borrows, or modification of `root` until the borrow ends
linked_list.rs:16                 prev = &mut root;
                                              ^~~~
note: in expansion of for loop expansion
linked_list.rs:7:5: 19:6 note: expansion site
linked_list.rs:20:2: 20:2 note: previous borrow ends here
linked_list.rs:1 fn main() {
...
linked_list.rs:20 }
                  ^
error: aborting due to 4 previous errors

What I'm trying to go for is fairly simple. We iterate through a Vec, creating a new node on each iteration. If prev is None this must be the start, so we make the root variable take ownership of that first node. If it's not, we update the previous node's next value to point to this node.

I'm new to Rust so I'm not sure where I'm going wrong. My interpretation is that the borrow checker isn't handling this well. It can't infer that the None branch in the match, containing the 'root' assignment, will only ever be called once, causing the two errors about root being borrowed twice. Am I correct?

Is this approach possible in Rust? Is there a more idiomatic way to do this sort of thing?

(A recursive approach is probably much easier but I'd like to complete an iterative one as a learning exercise.)

Answer 1

First of all, you should probably make sure you've read and understood the Rust Book chapters on Ownership and References and Borrowing. Your immediate problem is that you're borrowing things that aren't owned by anything, and will thus just disappear. You also have other problems like trying to mutate through an immutable pointer.

Let's get something that does, at least, work:

fn main() {
    let v = vec![1,5,3,8,12,56,1230,2,1];
    let mut root: Option<Box<Node>> = None;

    for i in v.into_iter().rev() {
        root = Some(Box::new(Node { value: i, next: root }));
    }

    println!("root: {}",
        root.map(|n| n.to_string()).unwrap_or(String::from("None")));
}

struct Node {
    value: i32,
    next: Option<Box<Node>>,
}

impl std::fmt::Display for Node {
    fn fmt(&self, fmt: &mut std::fmt::Formatter) -> Result<(), std::fmt::Error> {
        let mut cur = Some(self);
        let mut first = true;
        try!(write!(fmt, "["));
        while let Some(node) = cur {
            if !first { try!(write!(fmt, ", ")); }
            first = false;
            try!(write!(fmt, "{}", node.value));
            cur = node.next.as_ref().map(|n| &**n);
        }
        try!(write!(fmt, "]"));
        Ok(())
    }
}

This constructs a list and shows how you can iteratively display it. Note the complete lack of borrows in the construction code.

I have cheated somewhat, in that I've iterated the vector backwards to construct the list.

The problem with the original code is that, even if you strip out everything that isn't necessary, down to something like this:

let v = vec![1,5,3,8,12,56,1230,2,1];
let mut v = v.into_iter();

let mut root: Option<Box<Node>> = None;
if let Some(i) = v.next() {
    root = Some(Box::new(Node { value: i, next: None }));
    let mut prev: &mut Box<Node> = root.as_mut().unwrap();

    for i in v {
        let curr = Some(Box::new(Node { value: i, next: None }));
        prev.next = curr;
        prev = prev.next.as_mut().unwrap();
    }
}

You still end up in a situation where the compiler sees you mutating a thing you've borrowed by a second path. It's not quite smart enough to realise that re-assigning prev doesn't actually create any aliases. On the other hand, if you break the loop into an equivalent recursion:

if let Some(i) = v.next() {
    root = Some(Box::new(Node { value: i, next: None }));

    fn step<It>(prev: &mut Box<Node>, mut v: It) where It: Iterator<Item=i32> {
        if let Some(i) = v.next() {
            let curr = Some(Box::new(Node { value: i, next: None }));
            prev.next = curr;
            step(prev.next.as_mut().unwrap(), v)
        }
    }

    step(root.as_mut().unwrap(), v);
}

Then it's totally fine with it. Sadly, even with optimisations turned on, Rust doesn't perform tail call elimination in this case. So between borrow checker limitations and a lack of guaranteed tail call elimination, this design might be impossible to do in safe code.

I've run into this problem myself; loops and &mut pointers don't always play nicely with one another. You can work around this by switching to RefCell, with its associated runtime cost, although this then complicates iterating over such a list in a loop. Another alternative is to use usizes instead of pointers, and have all the nodes allocated into a Vec somewhere, although that introduces bounds checking overhead.

Failing all that, there's unsafe code, which lets you write more or less exactly what you would write in another language like C or C++, but without Rust's usual safety guarantees.

At the end of the day, writing data structures that are not just wrappers around an existing data structure in safe Rust without overhead is borderline impossible. It's why the fundamental data structures in Rust are all written using some amount of unsafe code.