error[E0499]: cannot borrow `*txn` as mutable more than once at a time

help
1

Hello everyone,

I've looked through discussions on forum regarding challenges on mutable borrowing more than once, but none of them seems to have the same type of issue (or maybe i just missed it) as i am facing now.

The code is as follows:

use concread::bptree::{BptreeMap, BptreeMapWriteTxn};


fn main(){
    let tree = BptreeMap::<i64, i64>::new();

    let mut txn = tree.write();
    let _ = wrapper(
        &mut txn,
        &BptreeMapWriteTxn::<i64, i64>::first_key_value,
    );

    drop(txn);
}


fn wrapper<'a, 'b, KeyFn>(
    txn: &'a mut BptreeMapWriteTxn<'b, i64, i64>,
    kvn_fn: &KeyFn,
)
where
    KeyFn: Fn(&'a BptreeMapWriteTxn<'b, i64, i64>) -> Option<(&'a i64, &'a i64)>,
{
    just_a_call(txn);
    just_a_call(txn);

    // This introduces the problems with more than once borrowing on the next
    // call to just_a_call(..).
    call_with_cb(txn, kvn_fn);    

    just_a_call(txn);
}


fn just_a_call<'a, 'b>(
    _txn: &'a mut BptreeMapWriteTxn<'b, i64, i64>,
){}


fn call_with_cb<'a, 'b, KeyFn>(
    txn: &'a mut BptreeMapWriteTxn<'b, i64, i64>,
    kvn_fn: &KeyFn,
)
    where
        KeyFn: Fn(&'a BptreeMapWriteTxn<'b, i64, i64>) -> Option<(&'a i64, &'a i64)>,
{
    kvn_fn(txn);
}

The error i get:

error[E0499]: cannot borrow `*txn` as mutable more than once at a time
  --> src/main.rs:31:17
   |
19 | fn wrapper<'a, 'b, KeyFn>(
   |            -- lifetime `'a` defined here
...
29 |     call_with_cb(txn, kvn_fn);
   |     -------------------------
   |     |            |
   |     |            first mutable borrow occurs here
   |     argument requires that `*txn` is borrowed for `'a`
30 |     
31 |     just_a_call(txn);
   |                 ^^^ second mutable borrow occurs here

Maybe i am defining lifetimes for callback function incorrectly, but no matter of what i have tried, i can not get this to work. Have spent few hours already and it seems to be going nowhere.

The goal for the code is to allow to define key/value search function as generic, so i could use first_key_value or last_key_value, or similar. The KeyFn is used only inside the scope of called function body, called function does not return references, so i kind of don't understand the compilers complaints that multiple borrows have occurred; to me the call to call_with_cb seems the same as call to just_a_call function.

Have i defined callback the wrong way? Or the problem is caused due to wrong lifetime definitions?

My motivation to use generics in this situation is to reuse some code and maybe even allow more optimizations for compiler to do, because instead of having if statement within call_with_cb body to decide which function/method to call, a generics could compile code for each code path from the call site where the callback is already known.

Unfortunately i could not reproduce same/similar error scenario with std BTreeMap, since it has a bit different API, no transactions.

2

Rust borrowing system enforces that you either have one mutable borrow or multiple shared borrows (sometimes referred as shared XOR mutable).

Unfortunately, BptreeMapWriteTxn::<i64, i64>::first_key_value return value seems to keep references to the tree values, hence why you get the borrow check error.

3

Thank you for the reply.

Is it really that the cause for error is due to the fact that ::first_key_value returns value that keeps reference to tree itself?

Because from my point of view, i am passing to function the reference to tree itself, as a second argument i want to pass a callback function (or definition that takes tree as an argument), which does not reference tree in any way at that point, so it should not influence the borrow checker in any way.

Then inside the function body, i would call the passed in function, so, yes, there it borrows a reference, but it never returns that reference to the outside/caller, so for me it seems the cause is something else. Maybe wrong definition for passed in function/lifetimes or something else i just don't see.

5

There is a problem in your specification of the KeyFn signature:

fn wrapper<'a, 'b, KeyFn>(
    txn: &'a mut BptreeMapWriteTxn<'b, i64, i64>,
    kvn_fn: &KeyFn,
)
where
    KeyFn: Fn(&'a BptreeMapWriteTxn<'b, i64, i64>) -> Option<(&'a i64, &'a i64)>,

Here you are saying that, when you call kvn_fn, the referenced txn is borrowed (potentially used) for the whole lifetime 'a — thus, the entire scope of the wrapper() function body. This prevents you from further mutating txn because it is still borrowed. Instead, you should probably be using a HRTB lifetime to say that the KeyFn only needs it temporarily (if that's in fact true):

where
    for<'k> KeyFn: Fn(&'k BptreeMapWriteTxn<'b, i64, i64>) -> Option<(&'k i64, &'k i64)>,

This means that the KeyFn returns references derived from its input, but is not allowed to keep them around for the whole of 'a (not that it would have had any way to do so, but the borrow checker doesn’t care).

4 Likes
6

It's possible that it has to. (I don't think it's relevant to the OP.)
1 Like
7

Thank you for the solution!

I'll have to do some research on HRTB lifetimes because reading the documentation somehow does not enlighten me enough, though the underlying problem i was facing seems to be the same as described in docs.

You exactly understood what i was trying to describe. I had seen in some crate code for<'lifetime> usage, but never had paid too much attention to it, thought it kind of described the same thing as "basic" lifetimes just with a different syntax.

Just for the reference and if someone stumbles upon this in future, i did try to define separate lifetime for KeyFn like so:

fn not_working_example<'a, 'b, 'k, KeyFn>(
    txn: &'a mut BptreeMapWriteTxn<'b, i64, i64>,
    kvn_fn: &KeyFn,
)
    where
        KeyFn: Fn(&'k BptreeMapWriteTxn<'b, i64, i64>) -> Option<(&'k i64, &'k i64)>,
{
    kvn_fn(txn);
}

where i got an error, like:

error[E0491]: in type `&'k concread::bptree::BptreeMapWriteTxn<'b, i64, i64>`, reference has a longer lifetime than the data it references
  --> src/main.rs:61:16
   |
61 |         KeyFn: Fn(&'k BptreeMapWriteTxn<'b, i64, i64>) -> Option<(&'k i64, &'k i64)>,
   |                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
note: the pointer is valid for the lifetime `'k` as defined here
  --> src/main.rs:56:31
   |
56 | fn wrong_call_with_cb<'a, 'b, 'k, KeyFn>(
   |                               ^^
note: but the referenced data is only valid for the lifetime `'b` as defined here
  --> src/main.rs:56:27
   |
56 | fn wrong_call_with_cb<'a, 'b, 'k, KeyFn>(
   |                           ^^

error: lifetime may not live long enough
  --> src/main.rs:63:5
   |
56 | fn wrong_call_with_cb<'a, 'b, 'k, KeyFn>(
   |                           --  -- lifetime `'k` defined here
   |                           |
   |                           lifetime `'b` defined here
...
63 |     kvn_fn(txn);
   |     ^^^^^^^^^^^ requires that `'b` must outlive `'k`
   |
   = help: consider adding the following bound: `'b: 'k`

error: lifetime may not live long enough
  --> src/main.rs:63:5
   |
56 | fn wrong_call_with_cb<'a, 'b, 'k, KeyFn>(
   |                       --      -- lifetime `'k` defined here
   |                       |
   |                       lifetime `'a` defined here
...
63 |     kvn_fn(txn);
   |     ^^^^^^^^^^^ argument requires that `'a` must outlive `'k`
   |
   = help: consider adding the following bound: `'a: 'k`

help: the following changes may resolve your lifetime errors
  |
  = help: add bound `'b: 'k`
  = help: add bound `'a: 'k`

Following the suggestion from compiler:

  = help: add bound `'b: 'k`
  = help: add bound `'a: 'k`

and adding those lifetime bounds basically gets you back to the starting position. It's like defining lifetimes in a loop, and you just can't break out of it with "basic" syntax (so i did not post it here since it did not seem to add any value to the question). This challenge is mentioned in docs as well.

So the error we get:

error[E0499]: cannot borrow `*txn` as mutable more than once at a time
  --> src/main.rs:36:17
   |
19 | fn wrapper<'a, 'b, 'k, KeyFn>(
   |                    -- lifetime `'k` defined here
...
34 |     not_working_example(txn, kvn_fn);    
   |     --------------------------------
   |     |                   |
   |     |                   first mutable borrow occurs here
   |     argument requires that `*txn` is borrowed for `'k`
35 |
36 |     just_a_call(txn);
   |                 ^^^ second mutable borrow occurs here

So this brings you back to square one, unless for<'lifetime> syntax is used.

While being at it, the docs state that:

There aren't many places outside of the Fn traits where we encounter HRTBs ..

What are those other places where HRTBs are (can be) used?

8

With traits that have lifetime parameters or get parameterized with references. The most commonly used example might be serde's DeserializeOwned = for<'de> Deserialize<'de>. Generally, uses will occur more often with traits that are more like Fn in that they are generic over an input type and an output type, rather than defining one or both of those types (and their lifetime relationships) in the trait’s function signatures.

In a loose sense, every fn signature in a trait is the same thing as a HRTB itself; consider how these two traits can be used in the same way:

trait Foo {
    fn do_thing<'a>(input: &'a str) -> &'a str;
}

trait Bar {
    type DoThing: for<'a> Fn(&'a str) -> &'a str;
    
    fn thing_doer() -> Self::DoThing;
}

Both of these introduce a binding for a lifetime variable 'a, that is independent of the trait as a whole — it's just that in Foo, it's built into the fn syntax, and in Bar it is separate. (Also, in Foo you can specify the lifetime when calling the function, since it's a generic parameter of the function, and in Bar you cannot, but the way lifetimes are inferred when not specified at the call site ends up being practically equivalent to for/forall/∀ anyway.)

3 Likes