54

In the following code (playground):

struct Node {
    datum: &'static str,
    edges: Vec<Node>,
}

fn add<'a>(node: &'a mut Node, data: &'static str) -> &'a Node {
    node.edges.push(Node {
        datum: data,
        edges: Vec::new(),
    });
    &node.edges[node.edges.len() - 1] // return just added one
}

fn traverse<F>(root: &Node, callback: &F)
where
    F: Fn(&'static str),
{
    callback(root.datum);
    for node in &root.edges {
        traverse(node, callback);
    }
}

fn main() {
    let mut tree = Node {
        datum: "start",
        edges: Vec::new(),
    };

    let lvl1 = add(&mut tree, "level1");

    traverse(&mut tree, &|x| println!("{:}", x)); //I actually don't need mutability here
}

I have this error:

error[E0499]: cannot borrow `tree` as mutable more than once at a time
  --> src/main.rs:32:19
   |
30 |     let lvl1 = add(&mut tree, "level1");
   |                         ---- first mutable borrow occurs here
31 | 
32 |     traverse(&mut tree, &|x| println!("{:}", x)); //I actually don't need mutability here
   |                   ^^^^ second mutable borrow occurs here
33 | }
   | - first borrow ends here

My question seems to be very similar to Why does Rust want to borrow a variable as mutable more than once at a time?, but I'm not sure. If so, is there a workaround for this case?

2
  • 3
    The above example compiles without any errors as of Rust 1.31+ Commented Apr 13, 2020 at 20:13
  • Note: it only compiles in this toy example because the compiler drops lvl1 before the second call since it won't be used anymore. But the semantical problems described in the answers are still present, and you wouldn't be able to use the lvl1 reference anyway.
    – SirDorius
    Commented Sep 7, 2023 at 7:18

2 Answers 2

39

This happens because of how add is defined:

fn add<'a>(node: &'a mut Node, data: &'static str) -> &'a Node

Here it is specified that the lifetime of the resulting reference should be equal to the lifetime of the incoming reference. The only way it is possible (except for unsafe code) is that the resulting reference is somehow derived from the incoming reference, for example, it references some field inside the object the incoming reference points at:

struct X {
    a: u32,
    b: u32,
}

fn borrow_a<'a>(x: &'a mut X) -> &'a mut u32 {
    &mut x.a
}

However, there is no way for the compiler to know what exactly from the incoming structure is borrowed by looking only at the function signature (which, in general, is the only thing it can do when compiling code which uses this function). Therefore, it can't know that the following code is technically correct:

let mut x = X { a: 1, b: 2 };
let a = borrow_a(&mut x);
let b = &mut x.b;

We know that a and b are disjoint because they point at different parts of the structure, but the compiler can't know that because there is nothing in borrow_a's signature which would suggest it (and there can't be, Rust does not support it).

Therefore, the only sensible thing the compiler could do is to consider the whole x to be borrowed until the reference returned by borrow_a() is dropped. Otherwise it would be possible to create two mutable references for the same data, which is a violation of Rust aliasing guarantees.

Note that the following code is correct:

let mut x = X { a: 1, b: 2 };
let a = &mut x.a;
let b = &mut x.b;

Here the compiler can see that a and b never point to the same data, even though they do point inside of the same structure.

There is no workaround for this, and the only solution would be to restructure the code so it doesn't have such borrowing patterns.

12
  • 3
    The compiler can process function bodies when they are in your crate, but how do you suggest to handle external binary dependencies? They don't contain enough information for the compiler. Therefore, this is the only way the model of ownership and borrowing can be made sound, so yes, "they did this" for a lot of things including fighting data races. As for how to code in such situations, well, there is no way than to restructure your code, for example, in your particular case you can split insertion and lookup into two methods, where insert won't return anything, thus avoiding the borrow. Commented Jul 8, 2015 at 14:22
  • 3
    Under "external" I meant arbitrary Rust code in external crate, not foreign C code for example (naturally, all foreign code should be handled via unsafe and raw pointers which do not contain borrowing information). You don't suggest making all external dependencies unsafe, do you? A lot of code in std, for example, contains functions like the one in your code. And it is not really restructuring code to make sense to the compiler, it is just following the ownership and borrowing model in general. Rust static analysis is very strict, but it is such for a good reason. Commented Jul 8, 2015 at 14:58
  • 1
    @tower120 There are a lot of reasons to depend only on the signature exposed. Yes, this makes parsing and checking much faster, since checks can be done without global analysis. But a more important reason is because the function signature defines the API. Having the true API subtly change when the implementation changes would be a nightmare for maintaining backwards compatibility. And of course one should restructure code to allow it to make sense to the compiler. It's well known that nearly any powerful static type system rejects some "valid" code. That's the price we pay.
    – Veedrac
    Commented Jul 8, 2015 at 16:46
  • 2
    @tower120, well, one of the notable examples are collections. All collections have methods which take them by reference or mutable reference and return a reference into themselves. Another example is BufReader which provides a reference to a buffer inside it. This is one of the most important and most often used patterns for structures which encapsulate complex piece of data and provide access to it. Commented Jul 8, 2015 at 18:04
  • 3
    @hdante, there is no workaround, and it is stated in my comment, although indeed it isn't stated in the answer itself. I probably should fix this. Commented Apr 24, 2017 at 10:31
5

The behaviour is logical. Consider what

fn add<'a>(node: &'a mut Node, data: &'static str) -> &'a Node

means.

This says that &mut Node has a lifetime equal to the lifetime of its return value. Because you assign the return value to a name, it lives until the end of the scope. Thus, the mutable borrow also lives that long.

If you can easily discard the return value, do so. You can just drop it on the floor:

let mut tree = Node {
    datum: "start",
    edges: Vec::new(),
};

add(&mut tree, "level1");

traverse(&mut tree, &|x| println!("{:}", x));

or you can use a lexical scope to constrain it without dropping it completely.

If you want to borrow the return without forcing the mutable borrow to live that long too, you are probably going to have to split the function in two. This is because you are not able to borrow the return value from the mutable borrow to do so.

9
  • "Because you extend the return value's lifetime by assigning it to a value..." - Can I do something like 'tree : 'node (node not exceed tree life) ? And if it extends lifetime, why it borrows variable (lifetime is a lifetime, variable is variable)?
    – tower120
    Commented Jul 8, 2015 at 3:22
  • The lifetime is for the reference, not for the referenced object. I'm not sure if this answers your question.
    – Veedrac
    Commented Jul 8, 2015 at 3:34
  • Ok, look here play.rust-lang.org/… . It seems that rust consider reference to object's element, as borrowing of object itself. Maybe this is the problem? Or am I wrong?
    – tower120
    Commented Jul 8, 2015 at 3:56
  • "It seems that rust consider reference to object's element, as borrowing of object itself." → That's the whole idea of borrowing, yes.
    – Veedrac
    Commented Jul 8, 2015 at 4:11
  • 1
    If it is possible, please consider not using "extend" word for lifetimes. This is not an official terminology, and there are a lot of questions here on how to "extend" lifetime in situations like fn ret_s<'a>() -> &'a str { let x = "abcde".to_owned(); &x } which is impossible. This may cause confusion for newcomers. Commented Jul 8, 2015 at 5:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.