Why is it borrowed for too long?

help
1

In the following code: (play ground)

struct Item{
    value: i32
}
struct Test{
    list: Vec<Item>
}
impl Test {
    fn get_or_push_item_mut(&mut self, ni: Item) -> Option<&mut Item> {
        {
            for i in self.list.iter_mut() { //============> line 10
                if i.value == ni.value {
                    return Some(i);
                }
            }
        } //==============================================> line 15
        self.list.push(ni);
        None
    }   //================================================> line 18
}
fn main() {
    let mut test = Test { list: Vec::new() };
    test.get_or_push_item_mut(Item {value: 1} );
}

I think the borrow occured on line 10 should end at line 15. But the compiler say it last until line 18. Hence, it complain me about the second borrow on line 16?

Why? Here are details about the error:

error[E0499]: cannot borrow `self.list` as mutable more than once at a time
--> src/main.rs:16:9
10 |             for i in self.list.iter_mut() {
   |                      --------- first mutable borrow occurs here
...
16 |         self.list.push(ni);
   |         ^^^^^^^^^ second mutable borrow occurs here
17 |         None
18 |     }
   |     - first borrow ends here
2 Likes
2

That's a "nice" one, which reminds me of one of @nikomatsakis' blog posts about why we need non-lexical lifetimes.

In a nutshell, here's what I understand to be happening. Rust's borrow checker is purely based on the scope of values and references, and has little to no understanding of conditional control flow. Therefore, it understands that the scope of a returned reference, which exits the function, is greater than the scope of anything local to the function, including your "push" statement. But it does not understand that the "push" statement will never be reached when the return statement is invoked. As a result, it incorrectly infers that the returned reference might be in scope at the time where the "push" statement will be called, and errors out.

Working around this in a general fashion may be ugly. If even @nikomatsakis himself suggests using a potentially inefficient workaround based on testing whether the vector contains the reference before returning it, I don't think us mere mortals stand a chance of implementing this pattern efficiently in Safe Rust. But for the specific case of a Vec, you can always return an index instead of a reference at a relatively light cost...

Just out of curiosity, why are you using a Vec instead of a Set for this purpose? It seems to bring unneeded O(N) insertion and lookup complexity when you could easily bring this down to O(log(N)) or O(1).

2 Likes
3

This is the "conditional control flow across functions" case described in the non-lexical lifetimes RFC. That sections gives a workaround that should work here as well. In brief, the borrow checker sees that your function returns &mut Item which borrows from self. That value remains borrowed until some point in the caller, which encompasses the entire rest of this function call. A future version of Rust will handle this correctly and your code will work as written.

fn get_or_push_item_mut(&mut self, ni: Item) -> Option<&mut Item> {
    for i in 0..self.list.len() {
        if self.list[i].value == ni.value {
            return Some(&mut self.list[i]);
        }
    }
    self.list.push(ni);
    None
}
4

Here's an ugly index-based workaround that works for Vec only: Rust Playground .

While looking at this code, you may wonder for a second "hey, what's up with all this boilerplate around Option::map?". And the answer, of course, will be "limitations of the current Rust implementation" again.

If I wrote the code as...

self.get_or_push_item_mut_impl(ni).map(|idx| &mut self.list[idx])

...then rustc would yell at me because the closure incorrectly borrows self away. Blame excessively greedy closure captures. There's a desire to make them more selective in the future, given enough manpower and careful analysis of edge cases.

If I work around this in the usual way...

let list = &mut self.list;
self.get_or_push_item_mut_impl(ni).map(move |idx| &mut list[idx])

...then rustc will be like "hey, you can't call that method while self is mutably borrowed by the "list" local variable! :trollface:".

Therefore, I need one additional layer of workaround before this code satisfies the current Rust closure desugaring mechanism and borrow checker.

1 Like
5

A similar take on this is:

fn get_or_push_item_mut(&mut self, ni: Item) -> Option<&mut Item> {
        let pos = self.list.iter().position(|i| i.value == ni.value);
        if let Some(p) = pos {
            Some(&mut self.list[p])
        } else {
            self.list.push(ni);
            None
        }
    }

You can also condense it to fewer lines if that's one's thing :slight_smile: :

fn get_or_push_item_mut(&mut self, ni: Item) -> Option<&mut Item> {
        let pos = self.list.iter().position(|i| i.value == ni.value);
        if let Some(p) = pos { Some(&mut self.list[p]) } else { self.list.push(ni); None}
    }
1 Like
6

I reduced the code to the (possibly) simplest that cause the same error. The real struct Item is more complex, all Item's instances are arranged in a cyclic style, ItemN overlaps ItemN+1, ItemMax overlaps Item0. A function call like:

test.get_or_push_item_mut(item5);

can give 3 possible results:

  • item4, if there is already item4 and it is overlapped with item5,
  • item6, if there is already item6 and it is overlapped with item5,
  • None, if there is no overlap, or both item4 and item6 is not already in the list.

But your suggestion is unexpected to me. I am an inexperienced coder. I think I should consider using a Set every time a Vec appear in my code, after your advice. Thank you very much.

If I saw a solution like that for just a simple problem like this about 5 or 6 months ago (when I try my first code in Rust ) I think I must be discouraged and stay away from Rust.

To all replies, thank you for your suggestions. I think every crustaceans are waiting for non-lexical lifetimes

1 Like
7

Indeed, data containers do not make a good first programming project in Rust, because they are one area where the "no aliased mutability" rule and the current implementation limitations hit the hardest :slight_smile: Moreover, some specific containers, such as Vec, can only be efficiently implemented using raw pointer manipulation in unsafe code, AFAIK because Safe Rust has no way to manipulate memory blocks whose size is defined at runtime (as one is then unable to prove that out-of-bounds accesses won't happen at compile time).

The flip side to this coin is that parsers, which are notoriously hard to write in memory-unsafe languages like C or C++ or in languages where all checks are done at runtime like Python, are much easier to write in Rust. That's in part because the standard library offers a lot of support to this kind of task, and in part because the "no aliased mutability" and "no dangling pointers" rules will save you very often when trying to use efficient zero-copy techniques. In a parsing context, "no aliased mutability" also means "no iterator invalidation", and that's a priceless compile-time property.

8

The fact he used return causes the reference to go from that local scope to the scope of the entire function?

Would it be...somewhat ok to read the actual borrow checker code? Or would it be too difficult for a Rust intermediate?

9

Because the function returns a reference and because Rust currently uses lexical borrows, the borrow is extended out into the caller - that includes the rest of the function itself. @dtolnay mentioned this upthread. It is a limitation of how the current borrow system works, and non-lexical lifetimes implementation should be landing in Rust soon I believe; with that, the original code will work.

By the way, @limira’s code from the first post can be made to work by sprinkling a smidge of unsafe into the function. Namely, return Some(unsafe { std::mem::transmute(i) });. That will sever the borrow extension. Personally I’d use one of the alternatives mentioned in this thread for this particular case.

10

So yes, return "lifted" the scope of the lifetime to beyond the caller...right? Like instead of let a = &b, return &b also borrows.

I actually looked at the borrow_ck.rs code today and it doesn't make too much sense because it seems to be very abstracted from the syntax. I could see nothing about equal signs or return statements.

I did learn about Loan structures though, which was helpful. Learned about how each Loan has a set of Restrictions.

I wonder how NLL will change this. I should maybe check out the code they are going to merge.

This would be a great opportunity for an article where someone goes through the borrow checker code and explains the critical parts.

I understand almost everything about the borrow checker except lifetimes. They seem to have a bunch of edge cases.