48

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?

Shepmaster
  • 388,571
  • 95
  • 1,107
  • 1,366
tower120
  • 5,007
  • 6
  • 40
  • 88

2 Answers2

35

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.

Shepmaster
  • 388,571
  • 95
  • 1,107
  • 1,366
Vladimir Matveev
  • 120,085
  • 34
  • 287
  • 296
  • The hell it is. If compiler can't process function body to determine affected parts of structures, and there is no way to give a clue about this... Then a)Why they did this? (in the name of data races?); b)How do they suggest to code in such situations? – tower120 Jul 08 '15 at 14:03
  • 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. – Vladimir Matveev Jul 08 '15 at 14:22
  • "The compiler can process function bodies when they are in your crate, but how do you suggest to handle external binary dependencies?" - Mark unsafe, do not handle (they are external, afterall). "As for how to code in such situations, well, there is no way than to restructure your code" - I don't like this. Restructure code just to make some sense to compiler? It doesn't sound right at all... – tower120 Jul 08 '15 at 14:50
  • 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. – Vladimir Matveev Jul 08 '15 at 14:58
  • "Under "external" I meant arbitrary Rust code in external crate" - And why it can't parse it too / add additional info about borrowing to binaries? "A lot of code in std, for example, contains functions like the one in your code. " - can you show them? I would like to look at them. – tower120 Jul 08 '15 at 15:02
  • 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 Jul 08 '15 at 16:46
  • 1
    @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. – Vladimir Matveev Jul 08 '15 at 18:04
  • I'm just curious, is this rfc https://github.com/rust-lang/rfcs/issues/811 fix this problem? I reduced code to this https://play.rust-lang.org/?gist=5b6b60a8b2798d5086d3&version=stable, and now it looks very simmiliar to this one https://github.com/rust-lang/rust/issues/6268 – tower120 Jul 08 '15 at 22:48
  • 1
    No, this is a different thing. Issue 6268 refers to code like `self.method(self.another_method())` where `method()` takes `&mut self`. In this case `self.another_method()` can't be called because of borrowing conflicts. It is only related to scoping (i.e. borrowing behavior inside the same lexical block), it is not related to borrow checking across function boundaries. – Vladimir Matveev Jul 09 '15 at 07:26
  • 1
    Why was this answer upvoted and marked as correct ? The question was whether there was any workaround for the problem. This answer only explained what the problem was, it neither said if there were any workarounds, nor showed the workaround if it existed. – hdante Apr 21 '17 at 21:08
  • 2
    @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. – Vladimir Matveev Apr 24 '17 at 10:31
  • "The only way it is possible (except for unsafe code) is that the resulting reference is somehow derived from the incoming reference" - [it is possible with `static` too](https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=2759d741b146f5fa8a0c4d0040e851a5) (but the answer is still correct). – Chayim Friedman Jul 10 '22 at 19:12
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.

Shepmaster
  • 388,571
  • 95
  • 1,107
  • 1,366
Veedrac
  • 58,273
  • 15
  • 112
  • 169
  • "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 Jul 08 '15 at 03:22
  • The lifetime is for the reference, not for the referenced object. I'm not sure if this answers your question. – Veedrac Jul 08 '15 at 03:34
  • Ok, look here https://play.rust-lang.org/?gist=9728baf56379ee4699ec&version=stable . 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 Jul 08 '15 at 03: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 Jul 08 '15 at 04: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. – Vladimir Matveev Jul 08 '15 at 05:24
  • Yes, I believe you're right, but that's how things are now :( No, I don't have a synonym, probably because I've never thought about this behavior like that. – Vladimir Matveev Jul 08 '15 at 08:30
  • Ok, but I still don't understand why "->&'a Node" becomes "&mut". – tower120 Jul 08 '15 at 14:07
  • @VladimirMatveev Well, I've removed the word. – Veedrac Jul 08 '15 at 16:36
  • @tower120 It doesn't. Declaring the return as `&'a` forces the `&'a mut` to live longer. – Veedrac Jul 08 '15 at 16:38