Why does returning early not finish outstanding borrows?

Question

I'm trying to write a function which pushes an element onto the end of a sorted vector only if the element is larger than the last element already in the vector, otherwise returns an error with a ref to the largest element. This doesn't seem to violate any borrowing rules as far as I cant tell, but the borrow checker doesn't like it. I don't understand why.

struct MyArray<K, V>(Vec<(K, V)>);

impl<K: Ord, V> MyArray<K, V> {
    pub fn insert_largest(&mut self, k: K, v: V) -> Result<(), &K> {
        {
            match self.0.iter().next_back() {
                None => (),
                Some(&(ref lk, _)) => {
                    if lk > &k {
                        return Err(lk);
                    }
                }
            };
        }
        self.0.push((k, v));
        Ok(())
    }
}

error[E0502]: cannot borrow `self.0` as mutable because it is also borrowed as immutable
  --> src/main.rs:15:9
   |
6  |             match self.0.iter().next_back() {
   |                   ------ immutable borrow occurs here
...
15 |         self.0.push((k, v));
   |         ^^^^^^ mutable borrow occurs here
16 |         Ok(())
17 |     }
   |     - immutable borrow ends here

Why doesn't this work?

---

In response to Paolo Falabella's answer.

We can translate any function with a return statement into one without a return statement as follows:

fn my_func() -> &MyType {
    'inner: {
        // Do some stuff
        return &x;
    }
    // And some more stuff
}

Into

fn my_func() -> &MyType {
    let res;
    'outer: {
        'inner: {
            // Do some stuff
            res = &x;
            break 'outer;
        }
        // And some more stuff
    }
    res
}

From this, it becomes clear that the borrow outlives the scope of 'inner.

Is there any problem with instead using the following rewrite for the purpose of borrow-checking?

fn my_func() -> &MyType {
    'outer: {
        'inner: {
            // Do some stuff
            break 'outer;
        }
        // And some more stuff
    }
    panic!()
}

Considering that return statements preclude anything from happening afterwards which might otherwise violate the borrowing rules.

Answer 1

If we name lifetimes explicitly, the signature of insert_largest becomes fn insert_largest<'a>(&'a mut self, k: K, v: V) -> Result<(), &'a K>. So, when you create your return type &K, its lifetime will be the same as the &mut self.

And, in fact, you are taking and returning lk from inside self. The compiler is seeing that the reference to lk escapes the scope of the match (as it is assigned to the return value of the function, so it must outlive the function itself) and it can't let the borrow end when the match is over.

I think you're saying that the compiler should be smarter and realize that the self.0.push can only ever be reached if lk was not returned. But it is not. And I'm not even sure how hard it would be to teach it that sort of analysis, as it's a bit more sophisticated than the way I understand the borrow checker reasons today.

Today, the compiler sees a reference and basically tries to answer one question ("how long does this live?"). When it sees that your return value is lk, it assigns lk the lifetime it expects for the return value from the fn's signature ('a with the explicit name we gave it above) and calls it a day.

So, in short:

• should an early return end the mutable borrow on self? No. As said the borrow should extend outside of the function and follow its return value
• is the borrow checker a bit too strict in the code that goes from the early return to the end of the function? Yes, I think so. The part after the early return and before the end of the function is only reachable if the function has NOT returned early, so I think you have a point that the borrow checked might be less strict with borrows in that specific area of code
• do I think it's feasible/desirable to change the compiler to enable that pattern? I have no clue. The borrow checker is one of the most complex pieces of the Rust compiler and I'm not qualified to give you an answer on that. This seems related to (and might even be a subset of) the discussion on non-lexical borrow scopes, so I encourage you to look into it and possibly contribute if you're interested in this topic.

For the time being I'd suggest just returning a clone instead of a reference, if possible. I assume returning an Err is not the typical case, so performance should not be a particular worry, but I'm not sure how the K:Clone bound might work with the types you're using.

impl <K, V> MyArray<K, V> where K:Clone + Ord { // 1. now K is also Clone
    pub fn insert_largest(&mut self, k: K, v: V) -> 
                                    Result<(), K> { // 2. returning K (not &K)
        match self.0.iter().next_back() {
            None => (),
            Some(&(ref lk, _)) => {
                if lk > &k {
                    return Err(lk.clone()); // 3. returning a clone
                }
            }
        };
        self.0.push((k, v));
        Ok(())
    }
}

Answer 2

Why does returning early not finish outstanding borrows?

Because the current implementation of the borrow checker is overly conservative.

Your code works as-is once non-lexical lifetimes are enabled, but only with the experimental "Polonius" implementation. Polonius is what enables conditional tracking of borrows.

I've also simplified your code a bit:

#![feature(nll)]

struct MyArray<K, V>(Vec<(K, V)>);

impl<K: Ord, V> MyArray<K, V> {
    pub fn insert_largest(&mut self, k: K, v: V) -> Result<(), &K> {
        if let Some((lk, _)) = self.0.iter().next_back() {
            if lk > &k {
                return Err(lk);
            }
        }

        self.0.push((k, v));
        Ok(())
    }
}