Multiple mutable borrows when generating a tree structure with a recursive function in Rust

Question

I'm having trouble implementing a recursive function that generates a binary tree by manipulating a mutable list of indices that index into an immutable list.

Here's the code:

enum Tree<'r, T:'r> {                                                                                                                                                                                     
    Node(Box<Tree<'r, T>>,                                                                                                                                                                                
         &'r T,                                                                                                                                                                                           
         Box<Tree<'r, T>>),                                                                                                                                                                               
    Empty                                                                                                                                                                                                 
}                                                                                                                                                                                                         

fn process_elements<T>(xs: &mut [T]) {
    // interesting things happen here                                                                                                                                                                     
}

// This function creates a tree of references to elements in a list 'xs' by                                                                                                                               
// generating a permutation 'indices' of a list of indices into 'xs',                                                                                                                                  
// creating a tree node out of the center element, then recursively building                                                                                                                              
// the new node's left and right subtrees out of the elements to the left and                                                                                                                             
// right of the center element.                                                                                                                                                                           
fn build_tree<'r, T>(xs: &'r [T],
                     indices: &'r mut [uint]) -> Box<Tree<'r, T>> {
    let n = xs.len();
    if n == 0 { return box Empty; }
    process_elements(indices);
    let pivot_index = n / 2;
    let left_subtree =
        // BORROW 1 ~~~v
        build_tree(xs, indices.slice_to_or_fail_mut(&pivot_index));
    let right_subtree =
        // BORROW 2 ~~~v
        build_tree(xs, indices.slice_from_or_fail_mut(&(pivot_index + 1)));
    box Node(left_subtree, &xs[pivot_index], right_subtree)
}

When I try to compile this, I get an error saying that I can't borrow *indices as mutable more than once at a time, where the first borrow occurs at the comment marked BORROW 1 and the second borrow occurs at BORROW 2.

I clearly see that *points does get borrowed at both of those locations, but it appears to me that the first borrow of *points should only last until the end of that single recursive call to build_tree in the let left_subtree statement. However, Rust claims that this borrow actually lasts until the end of the entire build_tree function.

Can anyone please explain:

Why the first borrow lasts until the end of the build_tree function, and
How a function like this could be correctly implemented in Rust?

By the way: if I remove the "let left_subtree =" and "let right_subtree =" (i.e., use the recursive calls to build_tree only for their side-effects on indices and pass Nones to the Node constructor), the code compiles just fine and does not complain about multiple borrows. Why is this?

Francis Gagné Francis Gagné · Accepted Answer · 2014-10-25T16:23:34

The result of build_tree is Box<Tree<'r, T>>. The borrows extend until the end of the function because the result still borrows from the slice, as evidenced by the lifetime parameter to Tree.

EDIT: The changes below are completely unnecessary in your case. Simply remove 'r from the indices parameter: indices: &mut [uint]. Otherwise, the compiler assumes that you still borrow from the slice because the returned Tree has that lifetime as a parameter. By removing the lifetime on indices, the compiler will infer a distinct lifetime.

To split a mutable slice into two, use split_at_mut. split_at_mut uses unsafe code to work around compiler limitations, but the method itself is not unsafe.

fn build_tree<'r, T>(xs: &'r [T],
                     indices: &'r mut [uint]) -> Box<Tree<'r, T>> {
    let n = xs.len();
    if n == 0 { return box Empty; }
    process_elements(indices);
    let pivot_index = n / 2;
    let (indices_left, indices_right) = indices.split_at_mut(pivot_index);
    let (_, indices_right) = indices_right.split_at_mut(1);
    let left_subtree = build_tree(xs, indices_left);
    let right_subtree = build_tree(xs, indices_right);
    box Node(left_subtree, &xs[pivot_index], right_subtree)
}

Multiple mutable borrows when generating a tree structure with a recursive function in Rust

1 Answers