When Unique mutable borrow rule is too restrictive

In order to ensure memory safety and to have consistent readability for single threaded and multi threaded code, rust has the following rules

1. A single mutable reference &mut T (or)

2. Multiple immutable references &T

These rules are too restrictive to write performant single threaded and multi threaded code. In this chapter we will see scenarios in single threaded code where these rules makes it impossible to write efficient code. Since Rust promises performance it provides us with types that can help the programmer to handle these scenarios without comprimising on speed!

Scenario 1: Caching of computations

Consider,

struct Point {
    x: f64,
    y: f64,
}

impl Point {
    fn distance_from_origin(&self) -> f64 {
        println!("doing the complex mathematical powers and square root");
        (self.x.powi(2) + self.y.powi(2)).sqrt()
    }
}

fn demo() {
    let p = Point {x: 23.3, y: -45.1342};
    println!("{}", p.distance_from_origin());
    println!("{}", p.distance_from_origin());
}

If you run the example, you can see that everytime the expensive mathematical computations are carried out.

To do the computation once but still have an immutable variable/reference we make use of the Cell type.

use std::cell::Cell;

struct Point {
    x: f64,
    y: f64,
    cache: Cell<Option<f64>>, // because initially the cache will be empty/none.
}
// By this stage you should know how to initialize a value for the above struct

impl Point {
    fn distance_from_origin(&self) -> f64 {
        match cache.get() {
            Some(d) => {
                println!("returning  cached value");
                d
            },
            None => {
                println!("doing the complex mathematical powers and square root");
                let d = (self.x.powi(2) + self.y.powi(2)).sqrt();
                self.set(Some(d));
                d
            }
        }
    }
}

fn demo() {
    let p = Point {x: 23.3, y: -45.1342};
    println!("{}", p.distance_from_origin());
    println!("{}", p.distance_from_origin());
}

Notice that in both the implementations we take an immutable reference but in the latter mutation happens interiorly.

Scenario 2: Tracking the clicks

use std::cell::Cell;

struct Button {
    label: String,
    click_count: Cell<u32>,
}

impl Button {
    fn new(label: &str) -> Self {
        Button {
            label: label.to_string(),
            click_count: Cell::new(0),
        }
    }

    fn click(&self) {
        let count = self.click_count.get();
        self.click_count.set(count + 1);
    }

    fn get_click_count(&self) -> u32 {
        self.click_count.get()
    }
}

NOTE: In both the scenarios that we saw, Cell comes in handy when we need to have a certain Copyable field mutable. So there is no overhead in using Cell and it is one of zero cost optimization.

Borrow checking at runtime

When you want to have interior mutability of types which are not copyable use RefCell. This comes with runtime over head because it checks in runtime whether there is a unique mutable borrow and panics in cases where borrow checking rules are violated.

Scenario 3: Graph with mutable nodes

A node in a graph can have muliple references to it, so we need to use Rc in conjunction with RefCell.

The example rust code to represent a GraphNode, with mutable value.

use std::cell::RefCell;
use std::rc::Rc;

struct GraphNode {
    value: RefCell<i32>,
    children: RefCell<Vec<Rc<GraphNode>>>,
}

impl GraphNode {
    fn new(value: i32) -> Rc<GraphNode> {
        Rc::new(GraphNode {
            value: RefCell::new(value),
            children: Vec::new(),
        })
    }

    fn add_child(parent: &Rc<GraphNode>, child: Rc<GraphNode>) {
        parent.children.borrow_mut().push(child);
    }

    fn set_value(&self, new_value: i32) {
        *self.value.borrow_mut() = new_value;
    }

    fn get_value(&self) -> i32 {
        *self.value.borrow()
    }
}

One should observe that without Cell and RefCell we would not be able to write safe Rust code. Yes you guessed it! Both these types uses unsafe type UnsafeCell under the hood.

Scenario 4: Updating a collection while iterating

Sometimes we might want to iterate over a structure, read its contents and modify one element while reading.

Rust won't allow this with the default rules because we would have to grab the entire structure as mutable while we are iterating over it.

Consider the following example:

#![allow(unused)]
use std::collections::HashMap;
use std::cell::RefCell;

fn main() {
    let mut map: HashMap<&str, u32> = HashMap::new();
    map.insert("hello", 123_u32);
    map.insert("world", 124_u32);
    
    println!("{:?}", map);

    // iterate over map
    for (key, value) in map.iter() {
        if key == &"hello" {
            let mut val = map.get_mut("world").unwrap();
            *val = 250;
        }
    }
    
    println!("{:?}", map);
}

This will fail to compile with the error message: error[E0502]: cannot borrow map as mutable because it is also borrowed as immutable

But we don't want to borrow the entire structure as mutable, just the individual element and modify it. We can do this with RefCell. See example below:

#![allow(unused)]
use std::collections::HashMap;
use std::cell::RefCell;

fn main() {
    let mut map: HashMap<&str, RefCell<u32>> = HashMap::new();
    map.insert("hello", RefCell::new(123));
    map.insert("world", RefCell::new(124));
    
    println!("{:?}", map);

    // iterate over map
    for (key, refcell_value) in map.iter() {
        if key == &"hello" {
            let mut val = map.get("world").unwrap().borrow_mut();
            *val = 250;
        }
    }
    
    println!("{:?}", map);
}

This will compile and correctly modify the value.