wrestling with borrow checker

Question

I'm new to Rust. As a learning exercise I'm trying to make a basic binary tree. This is what I have so far:

fn main() {
    let data = vec![6,1,2,3,4,5];

    let mut root = Node::<i32> { value: data[0], left: None, right: None };

    for val in data {
        createAndInsert::<i32>(&root, val);
    }
    println!("Root value: {}", root.value); 
}

fn createAndInsert<T: PartialOrd>(mut root: &Node<T>, value: T) {
    let mut n = Node::<T> { value: value, left: None, right: None };
    insert::<T>(&root, &n);
}

fn insert<T: PartialOrd>(mut curr: &Node<T>, new: &Node<T>) {
    if new.value > curr.value {
        match curr.right {
            Some(ref n) => insert(n, new),
            None => curr.right = Some(Box::new(*new))
        }
    } else {
        match curr.left {
            Some(ref n) => insert(n, new),
            None => curr.left = Some(Box::new(*new))
        }
    }
}

struct Node<T: PartialOrd> {
    value: T,
    left: Option<Box<Node<T>>>,
    right: Option<Box<Node<T>>>,
}

The compiler errors I'm getting:

test.rs:21:48: 21:52 error: cannot move out of borrowed content
test.rs:21             None => curr.right = Some(Box::new(*new))
                                                          ^~~~
test.rs:26:47: 26:51 error: cannot move out of borrowed content
test.rs:26             None => curr.left = Some(Box::new(*new))
                                                         ^~~~
test.rs:21:21: 21:54 error: cannot assign to immutable field `curr.right`
test.rs:21             None => curr.right = Some(Box::new(*new))
                               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
test.rs:26:21: 26:53 error: cannot assign to immutable field `curr.left`
test.rs:26             None => curr.left = Some(Box::new(*new))
                               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
error: aborting due to 4 previous errors

I've got myself tangled in all the refs and muts and &'s and *'s and I'm not sure how to get out. Where am I going wrong?

Answer 1

You have two problems:

• Cannot move out of borrowed context: see Cannot move out of borrowed content when borrowing a generic type for an explanation.

• Cannot assign to immutable field: you only have a &Node<T>; to modify the Node you need a &mut Node<T>. mut curr in the pattern merely makes the binding mutable, meaning that you can assign a new value to curr. You can’t, however, modify the contents of what curr refers to. Propagate the &-to-&mut conversion throughout the code and it’ll work.

Answer 2

Since you are new to Rust it might help to see how I would have written it:

struct Node<T> {
    value: T,
    left: Option<Box<Node<T>>>,
    right: Option<Box<Node<T>>>,
}

impl<T> Node<T> {
    fn new(x: T) -> Node<T> {
        Node { value: x, left: None, right: None }
    }
    fn boxed(x: T) -> Box<Node<T>> {
        Box::new(Node::new(x))
    }
}

fn insert<T: PartialOrd>(root: &mut Option<Box<Node<T>>>, new: Box<Node<T>>) {
    if let Some(ref mut rbx) = *root {
        if new.value < rbx.value {
            insert(&mut rbx.left, new);
        } else {
            insert(&mut rbx.right, new);
        }
    } else {
        *root = Some(new);
    }
}

fn main() {
    let data = vec![6,1,2,3,4,5];
    let mut root = None;
    for val in data {
        insert(&mut root, Node::boxed(val));
    }
    println!("Root value: {}", root.unwrap().value); 
}

I realize that this is more of an exercise but keep in mind that this kind of data structure should not grow beyond a certain tree depth since it might otherwise cause the stack to overflow when the nodes are recursivly deallocated.