RefCell, why borrowing is checked only in runtime

Is there any reason why ownership/borrowing is checked only in runtime not in compile time?
Surely compiler can follow identical rules to "non-refcell" bindings and infer if we broken the rules of borrowing?

If you want the borrowing rules to be checked at compile time, just use normal references.

A RefCell is useful in situations where you know something may only be accessed mutably once or immutably several times (e.g. by construction), but the situation is dynamic enough that you can't prove this at compile time.

The canonical example is when implementing some sort of doubly-linked list, where your LinkedList type will ensure the borrowing rules are followed (e.g. by taking &self and &mut self in methods), but Nodes may need to have references to the previous and next Nodes. If you didn't have RefCell you wouldn't be able to mutate a Node because it's always referred to by one or two other Nodes.

A Bad but Safe Doubly-Linked Deque from Learning Rust With Entirely Too Many Linked Lists provides an example of this.

6 Likes

Sure, in most cases the compiler is perfectly capable of checking the borrowing rules at compile time, and this is what happens when you write code normally without any cell type. However one of these borrowing rules are:

To modify a value, you must have exclusive access.

However what if the shape of your program is such that you don't have exclusive access to the value, but still want to change it? If your value is shared, then the compiler will fail to verify that it is not shared, because, well, it is shared.

This is where the cell types comes in. With RefCell you can have multiple references to the same shared value, but mark various regions of code with "this region reads the value" or "this region modifies the value". As long as no modify regions overlap with other regions, this would be perfectly fine, and with RefCell, you can check at run-time that no such overlap happens, at the cost of a panic if you were wrong.

There are other approaches too. The Cell type guarantees at compile time that the read and write regions are so small that no overlap can happen, so a Cell allows shared mutation without the risk of panics. This comes at the cost that some kinds of modifications are not possible with Cell.

I have a blog post about this you might like: Temporarily opt-in to shared mutation

4 Likes

Hi and thanks for your reply and link. I'll definitely check it.
I still believe that compiler is capable of checking at compile time if accessing RefCell breaks the borrowing rules, just like with other types of variables. Why wouldn't be capable of it? It has access to the entire source code and can check if we borrowing mutably whilst borrowing immutably by checking borrow vs borrow_mut on RefCell. Just like it does on other "non RefCell" variables. It checks mutable borrows and non mutable borrows and if the rules are broken it won't compile.

Short answer - because Rust was designed this way.

A little more detailed answer: Rust deliberately limits its analysis to the local checks, within one function. It's certainly possible in theory to make global analysis, but it'll increase compile time considerably - possibly by the orders of magnitude. And locally accessible data is fairly limited - because, again, if you try to encode more information in types (as it is done in dependently-typed languages, for example), compilation would be a lot slower, and the types themselves would be a lot harder to write in any non-trivial case, with little profit.

I actually disagree with the statement that having checks with regards to borrowing rules during compile time is of little profit.

Well, we have them anywhere we can - that's what all borrowing system is about. "Of little profit" is trying to extend these checks to every possible case.

RefCell is specifically intended for the cases that are too complicated for the compiler's checks to verify.

1 Like

I really don't understand it. My fault. No doubt about it. But when I think of it in terms:

let x: i64 = 1;
let borr_mut_x = &mut x;
let borr_x = &x

Here^ the compiler is able to check if the rules are broken or not, so what is different if instead of i64 in the example we use RefCell? I'm really struggling to understand what's the issue here?

I mean, if you explicitly opt-out of the in-built compile-time check, you shouldn't be surprised when the in-built compile-time check doesn't catch it.

2 Likes

How do I explicitly opt-out? And why is it that I'm opting out instead of applying the same rules to RefCell as to other types? It would (obviously it is not) seem that all is needed to check calls for borrow and borrow_mut.

You opt-out when you use RefCell's borrow_mut method.

use std::cell::RefCell;

fn main() {
    let x = RefCell::new(1i64);
    let mut borr_mut_x = x.borrow_mut();
    let borr_x = x.borrow();

    *borr_mut_x += 1;
}
thread 'main' panicked at 'already mutably borrowed: BorrowError', src/main.rs:6:20
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

This will panic at runtime. The compiler doesn't catch it because borrow_mut takes a shared reference &self rather than &mut self, which is necessary for the compiler's check to catch it.

Be aware that when using RefCell, you don't have to always opt-out. If you use RefCell::get_mut, then the compile-time check is still applied. This is because get_mut takes &mut self.

use std::cell::RefCell;

fn main() {
    let mut x = RefCell::new(1i64);
    let borr_mut_x = x.get_mut();
    let borr_x = x.borrow();
    
    *borr_mut_x += 1;
}
error[E0502]: cannot borrow `x` as immutable because it is also borrowed as mutable
 --> src/main.rs:6:18
  |
5 |     let borr_mut_x = x.get_mut();
  |                      - mutable borrow occurs here
6 |     let borr_x = x.borrow();
  |                  ^ immutable borrow occurs here
7 |     
8 |     *borr_mut_x += 1;
  |     ---------------- mutable borrow later used here

The above fails at compile-time.

3 Likes

As far as I understand such full program analysis is still a largely unsolved research topic.

You know how sometimes you can be studying the source of some program to find out what on Earth it is doing and why for a whole day, week, month...?

Can we really expect our compilers to do that?

Also, I'm pretty sure that some checks are just not possible at compile time. When programs run what they do is dependent on the input data, which the compiler knows nothing about.

3 Likes

To me it seems that this could be detected at compile time by checking x.borrow_mut and x.borrow. If we have x.borrow after x.borrow_mut and after that we try to write to it it should detect the borrowing rules are broken and the compilation shouldn't proceed.

Perhaps, but that would require the compiler to understand what RefCell is. It's just an ordinary type, and all Rust sees is two methods that take &self, which is ok according to the compile-time checks.

Of course, you could extend the compiler to catch a few more cases, but it doesn't because:

  1. You can never catch all cases, no matter what you do.
  2. It already catches many cases.
  3. The current implementation has the advantage that the compiler only has to look at one function at the time, which has many other advantages.

For example, the third reason has the advantage that, without it, writing libraries that are backwards compatible with previous versions is nearly impossible.

1 Like

Sure, but to me it looks like a really missed opportunity. NM.
Thanks

Ultimately handling it would require special-casing RefCell in the compiler, and I think that is a pretty large cost.

You might be able to get a check like it added to clippy.

I think that having compile time check outweighs that to be honest.

Fair enough. In any case, I hope you understand better why the compiler does not catch this case :slight_smile:

1 Like