Rust borrow checker

ht_ref.rs

use std::{
    cell::RefCell,
    collections::{hash_map::Entry, HashMap},
    rc::Rc,
};

type BlockId = u64;

type InodeId = u64;

#[derive(Clone, Debug)]
struct Block {
    val: [u8; 4096],
}

#[derive(Clone)]
struct SimpleFs {
    cache: HashMap<BlockId, Block>,
    cache_refcell: HashMap<BlockId, Rc<RefCell<Block>>>,
}

impl SimpleFs {
    fn new() -> SimpleFs {
        SimpleFs {
            cache: HashMap::new(),
            cache_refcell: HashMap::new(),
        }
    }

    /// Complex borrow, won't compile
    fn get_or_load(&mut self, block_id: BlockId) -> &Block {
        if let Some(b) = self.cache.get(&block_id) {
            return b;
        }

        let b = Block { val: [0; 4096] };

        self.cache.insert(block_id, b);
        self.cache.get(&block_id).unwrap()
    }

    /// Option 1: use the entry API
    /// This is an ad-hoc api just for this use case.
    /// In practice, we won't have so many ad-hoc APIs to cover our use cases.
    fn get_or_load_entry(&mut self, block_id: BlockId) -> &Block {
        match self.cache.entry(block_id) {
            Entry::Occupied(o) => o.into_mut(),
            Entry::Vacant(v) => v.insert(Block { val: [0; 4096] }),
        }
    }

    /// Option 2: use reference cell (`RefCell`) to make it work
    /// Practical use case will combine `Rc` and `RefCell` to circumvent two jobs of a borrow checker:
    /// (1) Preventing multiple mutable borrows -> use `RefCell`
    /// (2) Track the lifetime of the reference -> use `Rc`
    fn get_or_load_refcell(&mut self, block_id: BlockId) -> Rc<RefCell<Block>> {
        if let Some(b) = self.cache_refcell.get(&block_id) {
            let v = b.clone();
            return v;
        }

        let b = Rc::new(RefCell::new(Block { val: [0; 4096] }));

        self.cache_refcell.insert(block_id, b.clone());
        b
    }

    /// Option 3: copy-on-write (CoW)
    /// The entire struct is immutable, we always create a new instance on every mutation
    /// Note:
    /// (1) we are not returning the `&Block`, but a new instance of `SimpleFs`
    /// (2) we are not borrowing `&mut self`, but `&self` -- the old self is not modified.
    fn get_or_load_cow(&self, block_id: BlockId) -> Self {
        let mut new_self = self.clone();

        if !new_self.cache.contains_key(&block_id) {
            new_self.cache.insert(block_id, Block { val: [0; 4096] });
        }

        new_self
    }
}

/// Compiler is smart enough to know figure out the lifetime of the reference
fn simple_borrow_example() {
    let mut val = 42;
    let foo = &mut val;
    *foo = 32;

    // Multiple mutable borrow works, as long as they don't overlap
    // To learn more: https://plv.mpi-sws.org/rustbelt/stacked-borrows/paper.pdf
    let bar = &mut val;
    *bar = 64;

    // Uncomment this line to see the error -- foo overlaps with bar
    // *foo = 128;
}

Rust playground link: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=fc7c04e948d72762b4cb22942e2d8642