[borrowck] 5 questions about borrowing rules and mutability on a beginner project

As all new Rustaceans once went through, I'm currently in my phase of
fighting the borrow-checker. Instead of randomly throwing expedients and
hoping for the best to solve my errors and move on, I would like to deepen my
understanding of Rust and its borrowing techniques, which are fairly new
concepts to me coming from a C and C++ background. I'm looking for solutions
that are efficient, safe, and idiomatic to Rust.

This post contains 5 specific questions marked from (1) to (5).

Here is a minimal reproducible example of my first naive try:

pub struct Round {
    hands: ArrayVec<[Hand; 32]>,
    // ...
}

impl Round {
    pub fn run(mut self) -> RoundResult {
        // ...
        for hand in self.hands.iter_mut() {
            self.do_player_turn(hand);
        }
        // ...
    }

    fn do_player_turn(&mut self, hand: &mut Hand) {
        // ...
    }
}
error[E0499]: cannot borrow `self` as mutable more than once at a time
   --> src/round.rs:121:17
    |
117 |             for hand in self.hands.iter_mut() {
    |                         ---------------------
    |                         |
    |                         first mutable borrow occurs here
    |                         first borrow later used here
...
121 |                 self.do_player_turn(hand);
    |                 ^^^^ second mutable borrow occurs here

In run(), self has ownership of the Round struct: it is not borrowed; so,
calling Round::do_player_turn() which takes a &mut self requires a
mutable borrow. Yet, calling ArrayVec<_>::iter_mut() also requires a
mutable borrow, on self.hands this time. I suppose that borrowing part of
a struct mutably prevents borrowing the whole struct mutably; this would
create shared mutability over hands, hence the error on the call to
do_player_turn. (1) Is my assumption correct?

I understand the need for this restriction: do_player_turn may operate on
the ArrayVec instance and invalidate the iterator I'm iterating over. In
my case, the implementation is safe since the only operation that would
create such iterator invalidation would be to remove elements from the array,
something the function never does. But the compiler cannot know that and is
conservative.

Let's try another approach:

impl Round {
    pub fn run(mut self) -> RoundResult {
        // ...
        for i in 0..self.hands.len() {
            self.do_player_turn(i);
        }
        // ...
    }

    fn do_player_turn(&mut self, i: usize) {
        let hand = &mut self.hands[i];
        loop {
            // ...
            self.context.may_double = self.may_double(hand);
            // ...
        }
    }

    fn may_double(&self, hand: &Hand) -> bool { false }
}
error[E0502]: cannot borrow `*self` as immutable because it is also borrowed as mutable
   --> src/round.rs:169:39
    |
165 |         let hand = &mut self.hands[i];
    |                         ---------- mutable borrow occurs here
...
169 |             self.context.may_double = self.may_double(hand);
    |                                       ^^^^            ---- mutable borrow later used here
    |                                       |
    |                                       immutable borrow occurs here

This error is much more puzzling to me. First, the compiler says line 165
mutably borrows self while, in my understanding, it was already borrowed by
calling the function since it takes a &mut self. Without the call to
may_double(), this code compiles fine; (2) how could it? self is already
mutably borrowed yet I managed to mutably borrow one of its components (an
ArrayVec element). (3) Can't we really call a &self method on a mutably
borrowed struct? What's the rationale?

Let's make an immutable borrow instead:

/* 165 */ let hand = &self.hands[i];

This time, the call to may_double() works fine. (4) Why? The call requires
an immutable borrow but self is still mutably borrowed; I'm starting to
think my hypothesis that self is mutably borrowed in this function is wrong.

Of course it fails a few lines after inside the loop:

impl Hand {
    pub fn add(&mut self, card: Card) { /* ... */ }
}

hand.add(self.shoe.pick());

hand must be mutated in this function. Perhaps reborrowing it mutably would
help? It also implies to shorten the lifetime of the first borrow and do it
at each iteration:

loop {
    let hand = &self.hands[i];
    // ...
    self.context.may_double = self.may_double(hand);
    // ...
    let hand = &mut self.hands[i];
    // ...
    hand.add(self.shoe.pick());
}

This works! It is understandable, by borrowing only for the duration of one
iteration, there is no danger of invalidation, because each call to []
rechecks the validity. Unfortunately, I find this rather ugly and I'm afraid
this will cause measurable performance penalties. Performances are very
important in this project and I would like them to be as close to what I get
in the C++ implementation I'm rewritting it from in Rust.

(5) What would be the efficient and idiomatic way of addressing this issue?
I would like to avoid unsafe code but I'm willing to rely on it if the safe
alternatives perform poorly.

Thanks for reading so far!

I'm also very eager to read more about this topic if you know any good reference (apart from the Book, of course).

Yes.

Ah.. you didn’t tell me what these fields are anywhere.....

There is the concept of re-borrowing in Rust. You can think about is as: If you have borrowed a value you yourself have the ability to lend it to others. Just like the owner is not able to access the value they own while they mutably borrow it to e.g. a method, that method cannot access the borrowed value for the duration of the re-borrow. A minimal example is something like this:

fn main() {
    let mut x = 1;
    // can mutate x here
    x += 1;
    let y = &mut x;
    // cannot mutate x anymore until y is last used
    *y += 1;
    let z = &mut *y;
    // cannot use y anymore until z is last used
    *z += 1;
    // ^^ last usage of z
    // can use y again now
    *y += 1;
    // ^^ last usage of y
    // can access x again now
    x += 1;
    println!("{}", x); // -> 6
}

So through re-borrowing it is possible to have self mutably borrowed although self itself already β€œis a borrow” i.e. is a mutable reference.

Also, the compiler talks about borrowing self because:

  • &mut self parameter actually means self: &mut Self
  • you can borrow a mutable reference as you can any other type
  • so in a sense, you can think of re-borrowing as just borrowing the reference itself
  • note that by literally borrowing self: &mut Self, as in the expression &mut self, you would get a &mut &mut Self and it is possible to still mutate Self through that kind of double-indirection
  • in particular, taking lifetimes into account, it is possible to get a &'short mut Self short-lived mutable reference to the original value from a &'short mut &'long mut Self double-indirection reference

For demonstrating the last point, here’s an example:

// this compiles:
fn convert<'short, 'long, T>(r: &'short mut &'long mut T) -> &'short mut T {
    *r
}

Yes, you can’t call a &self method if self was already mutably borrowed. The basic principle in Rust is that &mut T references are exclusive, or without aliasing. This ensures things like that data races are impossible. Also in a single-threaded context, e.g. holding an immutable reference into a vector, if you had a mutable reference to the vector at the same time, too, then you could start re-sizing the vector through that one invalidating the immutable one.

I’m by the way not 100% sure I understood your question (3) correctly, so if my answer makes no sense to you, feel free to re-phrase your question.

Re-borrowing again. Think of two & &mut Self references being created, i.e. self (as in the self: &mut Self, the reference to the value of type Round) just needs to be immutably borrowed for this. Or in other words, you can obtain an immutable &Self re-borrow from a mutable &mut Self borrow. Similarly to before, a &'short &'long mut Self can be turned into a &'short Self. Another way to approach this is by the fact that when you can re-borrow a &mut Self into a &Self, this resulting &Self is now a type that can be copied, just like integers can. (There is the Copy trait that handles this property.) So you can get multiple copies of the &Self and use them in parallel. Once all the &Self references are no longer used, the re-borrow can end and you can get back access to the original &mut Self. An example like the previous re-borrowing example:

fn main() {
    let mut x = 1;
    let y = &mut x;
    // can use y to mutate x
    *y += 1;
    let z = &*y;
    // cannot use y to mutate its target anymore
    // until z is no longer used
    //e.g. this wont work
    //*y += 1;
    // but this works:
    println!("{}", y);
    // using z
    println!("{}", z);
    // z can be copied:
    let z1 = z;
    // using both z1 and z
    println!("{}", z);
    println!("{}", z1);
    println!("{}", z);
    println!("{}", z1);
    // and y without mutating its target:
    println!("{}", y);
    println!("{}", z);
    println!("{}", z1);
    println!("{}", z);
    // ^^ last usage of z
    // still can’t use y to mutate:
    // *y += 1;
    println!("{}", z1);
    // last usage of z1
    // not y can be used again
    *y += 1;
}

In this case, I would hope for (or even expect) the second index operation (into the same ArrayVec with the same index) to not actually compile down to a second bounds-check. Talking about alternatives

Your approach of using an index instead of the original version that used a &Hand reference for do_player_turn is already an idiomatic solution to this problem that you cannot mutably borrow the whole value while holding an (im)mutable reference into it.

One other approach would be to make do_player_turn not take a mutable reference to all of the Round but just the field(s) it needs access to. This could possibly be archived by refactoring Round so that the remaining fields are themselves only another struct (in case the partition of the borrows are: a mutable &mut Hand borrow into hands plus a mutable borrow to the remaining fields.

Or you could introduce multiple parameters to all the fields that do_player_turn needs access to for that method/function or even create a new helper struct that combines multiple borrowed fields of Round. This all is of course very dependent on what your code ultimately needs to be able to do. As a last option, in some situations interior mutability with Cell or even RefCell can help simplify your life sometimes. But it also can allow one to create more fragile interfaces (with RefCell’s ability to panic) and incur runtime overhead.

2 Likes

One worthwhile read of course is the Rustonomicon. I personally have, IIRC, first read through the whole Rust Book (skipping some of the big examples) and shortly after also through a big part of the Rustonomicon. There is a whole chapter on ownership in it.

Sometimes it makes sense to temporarily replace part of your struct to work on it.

    pub fn run(mut self) -> RoundResult {
        // replaces `self.hands` with `Default::default()`
        let mut hands = std::mem::take(&mut self.hands);

        // self is no longer borrowed at this point

        for hand in hands.iter_mut() {
            self.do_player_turn(hand);
        }

        // restore hands
        self.hands = hands;
        RoundResult
    }

The caveats are that this isn't a solution if do_player_turn needs self.hands to stay populated, and that an early return may result in you losing your hands.

I'd also recommend Niko Matsakis' After NLL articles:

The first is tangential to your situation, as it's about splitting borrows among different fields of a struct, whereas your situation involved a single field. But I still think it's instructive. The second is about the pitfalls of the above approach (e.g. maybe you need to future-proof things by ensuring do_player_turn doesn't need hands to be populated), and how to handle them.

2 Likes

Thank you very much @steffahn, this was very helpful and I really appreciate the time you took helping a stranger. I also now have some keywords to search.

Indeed, I didn't think this was relevant; in this case, here is the definition of context:

pub struct GameContext<'a> {
    // ...
    /// Whether the player may double down on his hand
    pub may_double: bool,
    // ...
}

Concerning question (3), the phrasing was bad I agree, English not being my first language; I was asking for a confirmation that calling a &self method on &mut T was impossible.

If we have:

fn do_something_immut<T>(vec_ref: &Vec<T>) -> usize { vec_ref.len() }

let mut v = vec![1, 2, 4, 8];
let v_ref = &mut v;
v_ref.push(42);
println!("size = {}", do_something_immut(&v_ref));
v_ref.push(42);

This compiles. I suppose that because there is no context where we can both access the &T and &mut T, the compiler allows it. But I can't see why the may_double call is different.

No problem : - )
I was just coding along, reproducing your example in the playground, and those two fields suddently had me going back to the struct definitions and adding new stuff. Their appearance just surprised me, nothing more.

No worries, it isn’t my first language either. The ability to phrase questions about Rust, especially about lifetimes, in an understandable manner of course correlates to how much one already understands about the topic. I wouldn’t blame your language skills but just the fact that Rust’s ownership system is hard and it’s even hard to ask questions about it ^^

Anyways... let me try to tackle your question again now:

So to be clear on the first, simple question, yes; calling a &self method on a &mut T is possible in general. I will try to explain the problem with your example involving may_double in the following sections:


After assigning hand in

fn do_player_turn(&mut self, i: usize) {
        let hand = &mut self.hands[i];
        loop {
            // ...
            self.context.may_double = self.may_double(hand);
            // ...
        }
    }

the situation looks about as follows

───┬ some value of type `Round` higher up on the stack
   └───┬ exclusively borrowed by self: &mut Round
       └───┬ (implitly) exclusively re-borrowed (as &mut Round)
           β”‚ for indexing operation `hands[i]`
           └──── the indexing returns a &mut Hand which got assigned
                 to `hand`; the &mut Hand requires the implicit &mut Round
                 re-borrow to stay alive due to the signature (*) of `index_mut`
                 so that this &mut Hand exclusively re-borrows the &mut Round


(*) signature of `index_mut`:
fn index_mut(&mut self, index: Idx) -> &mut Self::Output;
i.e.
fn index_mut<'a>(&'a mut self, index: Idx) -> &'a mut Self::Output;

if we want to pass hand to a method requiring a &Hand, we can do this as follows

───┬ Round value
   └───┬ self: &mut Round (exclusive borrow)
       └───┬ (implicit) &mut Round (exclusive re-borrow)
           └───┬ hand: &mut Hand (exclusive borrow)
               └──── (implicit) re-borrow of `hand` as &Hand (not exclusive)

Re-borrowing hand can also happen multiple times, so something like

───┬ Round value
   └───┬ self: &mut Round (exclusive borrow)
       └───┬ (implicit) &mut Round (exclusive re-borrow)
           └───┬ hand: &mut Hand (exclusive borrow)
               β”œβ”€β”€β”€β”€ (implicit) re-borrow of `hand` as &Hand (not exclusive)
               └──── another re-borrow of `hand` as &Hand
                     or a copy of the previous re-borrow (not exclusive)

is okay (this is what I mean by "not exclusive"). However for calling a &self method on self, we need to do this:

───┬ Round value
   └───┬ self: &mut Round (exclusive borrow)
       └──── (implicit) re-borrow of `self` as &Round (not exclusive)

which is only allowed once the previous, exclusive re-borrow is gone. Both in parallel, like this is not allowed:

// not allowed!!

───┬ Round value
   └───┬ self: &mut Round (exclusive borrow)
       β”œβ”€β”€β”€β”¬ (implicit) &mut Round (**EXCLUSIVE** re-borrow)
       β”‚   └───┬ hand: &mut Hand (exclusive borrow)
       β”‚       └──── (implicit) re-borrow of `hand` as &Hand (not exclusive)
       └──── (implicit) re-borrow of `self` as &Round (not exclusive,
             but collides with the EXCLUSIVE re-borrow further up)

But this is what would be needed for

self.may_double(hand);
^^^^            ^^^^
   β”‚               └─ the re-borrow of `hand` as &Hand
   └─ the re-borrow of `self` as &Round

This borrowing tree is not allowed since the two brances split at a point where the top one is an β€œexclusive”, i.e. mut borrow, which means there can be no such splitting at this level of the tree.


In the

/* a */ v_ref.push(42);
/* b */ println!("size = {}", do_something_immut(&v_ref));
/* c */ v_ref.push(42);

example, you instead have

───┬ Vec<i32> value
   └───┬ v_ref: &mut Vec<i32> (exclusive borrow)
       └──── (implicit) &mut Vec<i32> (exclusive re-borrow)

for the call /* a */, then

───┬ Vec<i32> value
   └───┬ v_ref: &mut Vec<i32> (exclusive borrow)
       └──── re-borrow of `v_ref` as &Vec<i32>  (not exclusive)

for the call /* b */ (the exclusive re-borrow of v_ref already ended after /* a */), and finally

───┬ Vec<i32> value
   └───┬ v_ref: &mut Vec<i32> (exclusive borrow)
       └──── (new, implicit) &mut Vec<i32> (exclusive re-borrow)

again for call /* c */.


The main takeaway is that in the may_double example, while the compiler knows that hand comes from self (as a re-borrow), it cannot have an immutable use of hand sort-of β€œpropagate down” the re-borrow tree to retroactively make all the borrows this builds upon be immutable. On the other hand, if you use let hand = &self.hands[i]; instead, then the situation looks like this to begin with:

───┬ some value of type `Round` higher up on the stack
   └───┬ exclusively borrowed by self: &mut Round
       └───┬ (implitly) re-borrowed self as &Round (not exclusive)
           β”‚ for indexing operation `hands[i]`
           └──── the indexing returns a &Hand which got assigned
                 to `hand`; the &Hand requires the implicit &Round
                 re-borrow to stay alive due to the signature (*) of `index`
                 so that this &Hand re-borrows the &mut Round
                 (but not exclusively re-borrows it)


(*) signature of `index`:
fn index(&self, index: Idx) -> &Self::Output;
i.e.
fn index<'a>(&'a self, index: Idx) -> &'a Self::Output;

This means that now, something like this is possible:

// allowed

───┬ Round value
   └───┬ self: &mut Round (exclusive borrow)
       β”œβ”€β”€β”€β”¬ (implitly) re-borrow of `self` as &Round (not exclusive)
       β”‚   └──── hand: &Hand (not exclusive)
       └──── (implicit) re-borrow of `self` as &Round (not exclusive)

for a call to self.may_double(hand). The variable hand does not need to be re-borrowed since re-borrows are only necessary for mutable references (immutable ones can be passed to e.g. may_double by copying the reference). This borrowing tree is allowed since the two brances split at a point where neither node is an β€œexclusive”, i.e. mut borrow.


For some further reading there is this great post on github that has this chapter covering pretty much this very topic of β€œdowngrading” a mutable reference and why it doesn’t have the desired effect.


Additional note: I was ignoring the modification of .context in my diagrams above. To understand why that is okay, too, one would need to consider that actually Rust allows multiple (even mutable) re-borrows of self: &mut Self into references to individual fields to happen in parallel as long as they are accessing different fields. This is why .context can be mutated while the shared reference in hand, reborrowing the .hands field of *self still exists.

Edit: Here’s some diagrams for the full picture:

self.context.may_double = self.may_double(hand);

Initial situation:

───┬ Round value
   └───┬ self: &mut Round (exclusive borrow)
       └───┬ (implitly) re-borrow of `self.hands` as &ArrayVec<[Hand; 32]> (not exclusive)
           β”‚ (ONLY BORROWS the `.hands` field)
           └──── hand: &Hand (not exclusive)

First step: evaluating the right-hand-side self.may_double(hand)

───┬ Round value
   └───┬ self: &mut Round (exclusive borrow)
       β”œβ”€β”€β”€β”¬ (implitly) re-borrow of `self.hands` as &ArrayVec<[Hand; 32]> (not exclusive)
       β”‚   β”‚ (ONLY BORROWS the `.hands` field)
       β”‚   └──── hand: &Hand (not exclusive)
       └──── (implicit) re-borrow of `self` as &Round (not exclusive)

(the re-borrows of self and self.hands overlap but both are not exclusive)

Second step: modifying self.context.may_double

───┬ Round value
   └───┬ self: &mut Round (exclusive borrow)
       β”œβ”€β”€β”€β”¬ (implitly) re-borrow of `self.hands` as &ArrayVec<[Hand; 32]> (not exclusive)
       β”‚   β”‚ (ONLY BORROWS the `.hands` field)
       β”‚   └──── hand: &Hand (not exclusive)
       └──── (implicit) re-borrow of `self.context.may_double` as &mut bool (exclusive)
             (ONLY BORROWS the `.may_double` field of the `.context` field)

(the re-borrow of self.context.may_double is exclusive but does refer to a different field than the re-borrow of self.hands, so it’s okay)

4 Likes