Single threaded code : mutable borrow in loop


#1

I am writing a single thread code for learning BTree. It is in rust :slight_smile:

Can i have multiple mutable refs of same object in a scope ?
Since this is single threaded, i don’t see why this will cause any problem ? Is there a way to tell compiler this ?

Code : https://github.com/ashishnegi/learndb/blob/master/src/sqliters/table.rs#L54

$ cargo build
54 | let l_leaf_page = self.pager.get_page(leaf_page_num as usize)?;
| ^^^^^^^^^^ mutable borrow starts in previous iteration of loop

From references chapter i see 3 conditions for which multiple borrows in same scope are not allowed :

The benefit of having this restriction is that Rust can prevent data races at compile time. A data race is similar to a race condition and happens when these three behaviors occur:

    Two or more pointers access the same data at the same time.
    At least one of the pointers is being used to write to the data.
    There’s no mechanism being used to synchronize access to the data.

My program is single threaded and needs no synchronization.

Please let me know how can i change my code to move forward.


#2

The Problem With Single-threaded Shared Mutability

Without looking at your code, I have a feeling this will help: Cannot obtain a mutable reference when iterating a recursive structure: cannot borrow as mutable more than once at a time


#3

@shepmaster I tried the suggestions to my understanding. Here is the code

 pub fn find_key_pos(&mut self, key: i32) -> Result<(u64, u64), String> {
        // root is always 0
        let mut leaf_page = Err("");
        let mut leaf_page_num = 0;
        let mut pager = &mut self.pager;
        // return page_num and cell_num
        loop
        {
            let tmp = pager;
            let l_leaf_page = tmp.get_page(leaf_page_num as usize)?;
            if !l_leaf_page.is_leaf() {
                break;
            }

            leaf_page_num = l_leaf_page.find_key_pos(key);
            leaf_page = Ok(l_leaf_page);
        }

        Ok ((leaf_page_num, leaf_page.unwrap().find_key_pos(key)))
}
error[E0382]: use of moved value: `pager`
  --> src\sqliters\table.rs:54:17
   |
54 |             let tmp = pager;
   |                 ^^^ value moved here in previous iteration of loop
   |
   = note: move occurs because `pager` has type `&mut sqliters::pager::Pager`, 
which does not implement the `Copy` trait

However, the pager object has Vec<page::Page> and fs::File so i can’t implement copy trait. Is this right ?

I moved the fn find_key_pos from table to pager and now it is working.


#4

I don’t see the purpose/need for this line in that code snippet since you never change what pager references. You should be able to just call pager.get_page(...) inside the loop.


#5

I can’t use pager as this code is inside the loop and i can’t do mutable work on pager in a loop.

error[E0499]: cannot borrow `*pager` as mutable more than once at a time
  --> src\sqliters\table.rs:54:31
   |
54 |             let l_leaf_page = pager.get_page(leaf_page_num as usize)?;
   |                               ^^^^^ mutable borrow starts here in previous iteration of loop
...
64 |     }
   |     - mutable borrow ends here

Can someone try ?

git clone https://github.com/ashishnegi/learndb.git
cd learndb
git checkout 10177c7a2a40db542abef624c7c360a1fc1cf7fc
cargo build

#6

@vitalyd I tried let tmp = pager; after looking at above answer. I admit that i don’t understand it completely. I am re reading it again multiple times. I have tried few times already.

Can someone point me to reasoning ?


#7

Oh I see the issue now - I missed that leaf_page is storing a reference to the l_leaf_page you got inside the loop.

Yeah, this is a bit unfortunate. As the compiler sees it, you’re holding a reference to something inside pager on each successive loop iteration, where you need to borrow pager mutably again – in its view, that equates to multiple mutable borrows to pager at the same time. It’s possible that NLL is able to reason more precisely about this, but I’ve not tried it.

A couple of workarounds:

 pub fn find_key_pos(&mut self, key: i32) -> Result<(u64, u64), String> {
        // root is always 0
        let mut leaf_page_num = 0;
        loop
        {
            let l_leaf_page = self.pager.get_page(leaf_page_num as usize)?;
            if !l_leaf_page.is_leaf() {
                return Ok((leaf_page_num, l_leaf_page.find_key_pos(key)));
            }
            leaf_page_num = l_leaf_page.find_key_pos(key);        
        };
        unreachable!()
    }

or similar:

pub fn find_key_pos(&mut self, key: i32) -> Result<(u64, u64), String> {
        // root is always 0
        let mut leaf_page_num = 0;
        // return page_num and cell_num
        let key_pos = loop
        {
            let l_leaf_page = self.pager.get_page(leaf_page_num as usize)?;
            if !l_leaf_page.is_leaf() {
                break l_leaf_page.find_key_pos(key);
            }
            leaf_page_num = l_leaf_page.find_key_pos(key);
        };
        Ok ((leaf_page_num, key_pos))
    }

In both cases, you don’t actually need to keep leaf_page outside the loop - once the leaf is found, we can query it for the key pos and return that; this keeps the borrow of pager constrained to a single loop iteration.


#8

I’d write it as

    pub fn find_key_pos(&mut self, key: i32) -> Result<(u64, u64), String> {
        let mut page_num = 0;

        loop {
            let page = self.pager.get_page(page_num as usize)?;

            let key_pos = page.find_key_pos(key);

            if page.is_leaf() {
                page_num = key_pos;
            } else {
                return Ok((page_num, key_pos));
            }
        }

#9

Thanks. This works.

I see. Interestingly, i had done the same thing when i moved the function to Pager type from Table. That time i had written the function again from scratch and had kept page object locally with in loop. Code

The unfortunate thing is in original code, compiler was complaining about self.pager being mutably borrowed multiple times. And with my limited knowledge, i got distracted into playing around with self.pager and pager object.

Is the conclusion that : “in errors of mutably borrow multiple times we need to focus on returned values of multiply borrowed object and minimize their scope” : right ?


#10

Just in case, someone is pondering, in all these code snippets, we need to return from function when we are at leaf_page. This was my mistake in original non working snippet.


#11

@vitalyd Can you please help me with the reasoning here ? Is above correct ?


#12

If I’m understanding you correctly, yes, that’s correct.


#13

Sorry, I lost track of this one and @steveklabnik’s reply just reminded me of it :slight_smile:. But as he says, yes, that’s the approach. In general, you want to keep borrows as short as possible.