A lot of volatile borrowing when creating a tree structure with a recursive function in Rust
I am having a problem implementing a recursive function that generates a binary tree by manipulating a mutable list of indices that are indexed 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 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 cannot take *indices
as mutable more than once at a time, where the first borrowing happens in a tagged comment BORROW 1
and the second is borrowed when BORROW 2
.
I can clearly see what is *points
borrowed in both of these places, but it seems to me that the first borrow *points
should only continue until the end of this single recursive call build_tree
to let left_subtree
. However, Rust claims that this loan actually lasts until the end of the entire function build_tree
.
Can someone explain:
- Why does the first loan last until the end of the function
build_tree
and - How can such a function be properly implemented in Rust?
build_tree
only for your side effects on
indices
and pass
None
in
Node
), the code compiles just fine and doesn't complain about multiple borrowings. Why is this?
source to share
The result build_tree
is Box<Tree<'r, T>>
. The logs continue until the end of the function because the result is still borrowing from the slice, as evidenced by the lifetime to parameter Tree
.
EDIT : The changes below are completely unnecessary in your case. Simply remove 'r
from the parameter indices
: indices: &mut [uint]
. Otherwise, the compiler assumes that you are still borrowing from the slice, because the one returned Tree
has that lifetime as a parameter. By removing the lifetime on indices
, the compiler will output a distinct lifetime.
To split the changed fragment in two, use split_at_mut
. split_at_mut
uses unsafe
code to work with compiler constraints, 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)
}
source to share