Unable to borrow self.chunks as mutable twice

Hi,

I am trying to understand why this code fails to compile:

const CHUNK_SIZE: usize = 1024;
struct StringChunk {
    chunk: [u8; CHUNK_SIZE],
    pos: usize
}

struct StringAllocator {
    chunks: Vec<Box<StringChunk>>,
}

impl StringAllocator {
    fn new() -> Self {
        StringAllocator {
            chunks : vec![Box::new(StringChunk{ chunk: [0; CHUNK_SIZE], pos: 0 })],
        }
    }

    fn alloc_string(&mut self, n: usize) -> Option<&mut [u8]> {
        let mut cur : Option<&mut Box<StringChunk>> = None;
        for i in 0..self.chunks.len() {
            let c = &self.chunks[i];
            if c.pos + n <= CHUNK_SIZE {
                cur = Some(&mut self.chunks[i]);
                break;
            }
        }
        if cur.is_none() {
            self.chunks.push(Box::new(StringChunk{ chunk: [0; CHUNK_SIZE], pos: 0 }));
            cur = self.chunks.last_mut();
        }
        match cur {
            None => None,
            Some(stringchunk) => {
                let pos = stringchunk.pos;
                stringchunk.pos = stringchunk.pos + n;
                Some(&mut stringchunk.chunk[pos .. n])
            }
        }
    }
}

I get this error:

error[E0499]: cannot borrow `self.chunks` as mutable more than once at a time

As far as I can tell the borrows are not in the same scope?

Regards
Dibyendu

Hello. I have moved your post to a new topic.

2 Likes

The problem is your borrow of self.chunks when you assigned it to cur in the for loop is still active when you reach the match, and your call to self.chunks.push happens between those, so they are overlapping.

So the compiler can't tell by following:

if cur.is_none() {

that the borrow is not active?

You can use std::cell::RefCell for moving borrow checking process from compile time to runtime time, this would fix your problem if your code is in fact a safe code. But I don't know if this is the best solution here, I'm new to Rust too.

I don't know whether it is possible to proof that your code is safe; but even if it is, Rust compiler prefers only accepting a subset of possible safe codes and rejecting every unsafe code. That is, every valid rust code is safe but not every safe code is a valid rust code.

No, the problem has nothing to do with cur.is_none() – it only borrows cur until it's evaluated.

The problem is that first you write cur = Some(&mut self.chunks[i]); which mutably borrows self.chunks for the entire scope of cur, then you subsequently write cur = self.chunks.last_mut();, which also borrows self.chunks mutably, even though cur is still in scope.


Or are you expecting the compiler to be able to tell that cur is None by seeing the cur.is_none() call? That's impossible in the general case, the compiler can't just look into the implementation of a method in order to tell what's it doing globally. And even if it could, that approach would have a whole lot of serious downsides, much worse ones than having to rearrange a small piece of code. Globality makes program analysis excruciatingly hard, and thus it is almost always the wrong thing to do.

1 Like

I am new to Rust so I don't exactly know what to expect.

I guess I assumed that the compiler had some understanding of Option type and therefore could 'see' that the inside the if branch cur hasn't borrowed anything.

I was able to rewrite the method as follows:

    fn alloc_string(&mut self, n: usize) -> Option<&mut [u8]> {
        if n > CHUNK_SIZE {
            return None;
        }
        let mut j: usize = self.chunks.len();
        for i in 0..self.chunks.len() {
            let c = &self.chunks[i];
            if c.pos + n <= CHUNK_SIZE {
                j = i;
            }
        }
        if j == self.chunks.len() {
            self.chunks.push(Box::new(StringChunk{ chunk: [0; CHUNK_SIZE], pos: 0 }));
        }
        let cur = &mut self.chunks[j];
        let pos = cur.pos;
        cur.pos = cur.pos + n;
        Some(&mut cur.chunk[pos .. n])
    }

The Option type is not special in Rust. It's just another type defined by the standard library, and is_none is just another method call.

1 Like

This is not specific to Rust – it is a computational theoretical limitation. No language to my knowledge does such global semantic analysis. In general, predicting at compile time what a program does at runtime is an unsolvable problem, and even when it is solvable, it's completely unfeasible complexity-wise for all but the most trivial programs. (Search for "the Halting Problem" if you are interested in more.)

The compiler does have an understanding of enums and of the fact that their variants are exclusive. I can imagine that the borrow checker is smart enough to deduce this if you manually rewrite your code using an explicit match instead of using if cur.is_none().

However, functions represent abstraction boundaries, and the compiler is neither able nor allowed to "see through" them. Whether the usage of a function is correct should be able to (and in Rust, can) be deduced solely from its signature. Again, not having this property would make compilation basically impossibly difficult and slow.

1 Like

Hi,

I have a follow up question.
So I have a struct with a vector of arrays - and am returning slices as explained above.
How can can I express a lifetime relationship - i.e. express that the slices are owned by the struct and have a lifetime same as the struct?

When you are defining the struct, that is not a lifetime relationship, but an ownership relation. It is specified by using an owned type such as Vec<T> rather than a slice such as &[T].

struct MyStruct {
    // This field uses only owned types, so it is owned by the struct.
    has_vec: Vec<[u8; 16]>,
}

Where lifetime relations come into play are in function definitions:

impl MyStruct {
    // The returned slice has the same lifetime as &self.
    fn get_slice<'a>(&'a self, idx: usize) -> &'a [u8] {
        &self.has_vec[idx]
    }
}

Note that if you do not write the lifetimes in the above example, then the compiler can figure it out by itself.

// this is the same as above
impl MyStruct {
    fn get_slice(&self, idx: usize) -> &[u8] {
        &self.has_vec[idx]
    }
}

When you have lifetimes inside a struct definition, that always means "this is not owned by the struct, but some other thing".

1 Like

Okay thank you