Compiler claims mutable reference being borrowed twice

I've got a type T as well as a function blackbox(&mut [T]) -> Option<&mut T>
and want to write a function f(x: &mut [T]) -> Result<&mut T, &mut [T]> that tries to
apply blackbox to x, and if it "fails" returns Err(x) like this:

fn f(x: &mut [T]) -> Result<&mut T, &mut [T]> {
    if let Some(x) = blackbox(x) {
        return Ok(x);
    }
    Err(x)
}

But now the compiler complains about *x being borrowed twice:

error[E0499]: cannot borrow `*x` as mutable more than once at a time
   |
 1 | fn f<T>(x: &mut [T]) -> Result<&mut T, &mut [T]> {
   |            - let's call the lifetime of this reference `'1`
 2 |     if let Some(x) = blackbox(x) {
   |                               - first mutable borrow occurs here
 3 |         return Ok(x);
   |                ----- returning this value requires that `*x` is borrowed for `'1`
 4 |     }
 5 |     Err(x)
   |         ^ second mutable borrow occurs here

Why exactly is x borrowed twice in line 5?

For blackbox = |x| x.get_mut(0) the problem is simple to solve with pattern matching

fn f(x: &mut [T]) -> Result<&mut T, &mut [T]> {
    match x {
        [x, ..] => Ok(x),
        x => Err(x),
    }
}

Of course exactly one of these options must apply:

  1. unsafe does not have to be used to construct such f => could you please tell me how to construct such f?
  2. unsafe must be used to construct such f
    2.1) It is possible to construct f so that it never causes UB => huh... Okay. Does any unstable feature solve this problem?
    2.2) f will cause UB => oh, ok... i really need explanation

The return value for both blackbox and f must live as long as the lifetime of the input parameter. When potentially returning a result of blackbox from f, this means that the return value of that blackbox call must live as long as the lifetime of the input parameter, and thus output parameter, of f.

Now, this is true even in the case when None is returned from blackbox. The compiler doesn't exploit any special information about Option for lifetimes. As soon as you call blackbox, the exclusive borrow of the input parameter is in a sense transferred to the return value of blackbox, with the same lifetime. The lifetime extends through the return of f, and that's why Err(x) is a second borrow. x is still being borrowed by the return value of blackbox, whatever that value is.

(This is a case where "mutable reference" is a bit misleading, and it's better to think of the logic in terms of exclusive borrows. The fact that None contains no reference doesn't matter.)

It's real ugly, and I don't know if it makes sense for your use case or not, but you could do this:

fn f(x: &mut [T]) -> Result<&mut T, &mut [T]> {
    // The return of `blackbox()` cannot be returned from `f` here.
    // So the borrow can be shorter than the return value of `f`.
    // (The exclusive borrow for `blackbox(x)` ends before we `return Err(x)`.)
    if blackbox(x).is_none() {
        return Err(x);
    }

    // This is a different borrow which is tied to the same lifetime, like your original code.
    Ok(blackbox(x).unwrap())
}

Or, you can combine the logic of f and blackbox into a single function.

3 Likes

Seconded -- if you manually inline blackbox into f the compiler will no longer be constrained by the type signature of blackbox (which it otherwise has to interpret strictly for borrow checking) and it'll be able to "see" that there's no mutable aliasing going on.

1 Like

I think, I now understand the error. Let x have the lifetime 'a. As in the if-let condition forced, the blackbox must return &'a mut T, so x is being borrowed for 'a.

Thank you for your help quinedot and cole-miller.

The problem is, that blackbox is an unknown function and will have side-effects, so calling blackbox twice as quinedot suggested is not an option. Inlining blackbox is as well not an option (because I don't know f). To better match this properties, I will extend f to this declaration:

fn f<T, F: FnMut(&mut [T]) -> Option<&mut T>>(
    x: &mut [T],
    blackbox: F,
) -> Result<&mut T, &mut [T]>;

Is there really no "safe" solution to this problem? Even not with a magic std-function I don't know about that does pretty much the job or dirty hacks?

If not, there is nothing to be said against this, isn't it?

fn f<T, F: FnMut(&mut [T]) -> Option<&mut T>>(
    x: &mut [T],
    mut blackbox: F,
) -> Result<&mut T, &mut [T]> {
    let p: *mut [T] = x;
    blackbox(unsafe { &mut *p }).ok_or(x)
}

I ran that program through the miri tool on the playground and got an error about undefined behavior (playground)

I coaxed it into this version that miri seems okay with, but miri doesn't catch all undefined behavior and I have very little experience with unsafe code. Maybe someone more experienced with unsafe can look it over.

You've run into a known short coming of the borrow checker. There's a new experimental borrow checker called polonius, and with it turned on, the original code compiles:

pub fn main() {
    let mut v: Vec<u8> = vec![1, 3, 7, 8];
    let res = f(&mut v, |x| x.get_mut(0));
    println!("{:?}", res);
}

pub fn f<T, F: FnMut(&mut [T]) -> Option<&mut T>>(
    x: &mut [T],
    mut blackbox: F,
) -> Result<&mut T, &mut [T]> {
    if let Some(x) = blackbox(x) {
        return Ok(x);
    }
    Err(x)
}
$ RUSTFLAGS="-Z polonius" cargo +nightly run
   Compiling pol v0.1.0 (/tmp/pol)
    Finished dev [unoptimized + debuginfo] target(s) in 0.47s
     Running `/tmp/pol/target/debug/pol`
Ok(1)

I remember that there is a similar issue with using stuff like HashMap, where the act of returning a reference from a function tied the lifetime of the borrow to the input parameter, preventing the use of that input parameter elsewhere. The workaround was the Entry API.
I don't know if it'll be possible to create a similar API for your use case as I don't really know too much about how that API is implemented/why it works.

6 Likes

Wrong. Why would you want to use unsafe if they showed you two ways of implementing the same thing in safe code?

1 Like

They explained that in the very same reply:

And yet, the "nothing wrong" implementation causes UB. That in itself is enough reason for not accepting it as a solution. I don't think trying to get away with UB is fine, even if the obvious/simple variant of the code doesn't compile because of a limitation in the language.

You can say that in a less dismissive manner. This sort of unnecessarily aggressive discourse is why I'm not very active on this forum.

3 Likes

Here's another unsafe version with no UB detected by Miri. It works just like the original code (which we know is safe because Polonius is able to compile it) but uses a raw pointer to bypass the borrow checker. When Polonius is stabilzed, you can easily convert it back to safe Rust.

fn f<T, F: FnMut(&mut [T]) -> Option<&mut T>>(
    x: &mut [T],
    mut blackbox: F,
) -> Result<&mut T, &mut [T]> {
    let ptr = x as *mut [T];
    unsafe {
        if let Some(x) = blackbox(&mut *ptr) {
            return Ok(x);
        }
        Err(&mut *ptr)
    }
}
4 Likes