Rust Borrow Checker Explained Part 5: Escape Hatches
Published: 2023-11-11 21:14:40

## Intro

In part 4 we looked at how to declare structures with borrowed fields, and some of the limitations this introduces. In this final part of the Rust borrow checker series we will investigate some tools that allow us to "break the rules".

Specifically, we will see:
* How we can use "copy on write" to **possibly** avoid copying.
* How we can share a reference by counting each use and only releasing the value when the count drops to zero.
* How inner fields can be made mutable from an immutable context.

## Copy On Write

Rust has a [`Cow`](https://doc.rust-lang.org/std/borrow/enum.Cow.html) type which is a simple enumeration over two possible states:
* `Borrowed`
* `Owned`

This is useful if you want to be able to take an immutable reference with the possibility of changing it into an owned value. This technique is known as "copy on write", and thus the name `Cow`. Here is an example of using it to take an array of numbers and make sure that they are even:

```rust
use std::borrow::Cow;

fn main() {
    let input: &[isize] = &[1, 2, 3, 4];
    let mut output = Cow::Borrowed(input);
    make_even(&mut output);
    println!("input={input:?} output={output:?}");
}

fn make_even(input: &mut Cow<'_, [isize]>) {
    for idx in 0..input.len() {
        if input[idx] % 2 != 0 {
            input.to_mut()[idx] = input[idx] + 1;
        }
    }
}
```
[Try it!](https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=c81996a38b2edd9d7d6e5932479fbda8)

Note that if the input was all even, then no copy would take place. Only when the `to_mut()` call is made does it call `.clone()` on the underlying borrowed value.

Obviously, this only works on types that implement `Clone`.

## Breaking Single Ownership: Reference Counting

The single ownership rule can be broken by using reference counting, aka "smart pointers". Rust provides two variants: [`Arc`](https://doc.rust-lang.org/std/sync/struct.Arc.html) and [`Rc`](https://doc.rust-lang.org/std/rc/struct.Rc.html). `Arc` is short for "atomic reference count" and `Rc` is just "reference count". If there is a possibility of using multiple threads, then stick with `Arc`.

The only practical way of implementing a linked list is to use reference counts:

```rust
use std::rc::Rc;

#[derive(Debug)]
struct Node {
    val: i32,
    next: Option<Rc<Node>>
}

fn create_list() -> Node {
    let third = Node {
        val: 3,
        next: None,
    };
    let second = Node {
        val: 2,
        next: Some(Rc::new(third)),
    };
    let first = Node {
        val: 1,
        next: Some(Rc::new(second)),
    };
    return first;
}

fn main() {
    let list = create_list();
    println!("LL={list:?}");
}
```

Note that since we are no longer borrowing the next nodes, we can create the entire list in the `create_list()` function, and just return the first node in the list.

Smart pointers, aka reference counters:
* Implements `Clone.clone()` trait so that it increments the reference count.
* Implements [`Deref.deref()`](https://doc.rust-lang.org/std/ops/trait.Deref.html) trait so you can directly call the underlying methods of the value being pointed to. This also allows you to use the `*` syntax to get an immutable view of the value.
* Incur overhead for the extra space required to store the counter and the cost of incrementing and decrementing the counter.
* Leak memory if a cycle is formed, but since every smart pointer is immutable, and since `Rc::new()` takes ownership of the value, it is impossible to define a structure with a cycle... unless you read on.

## Breaking Immutability: RefCell & Mutex

If we want inner mutability, Rust provides two variants: [`RefCell`](https://doc.rust-lang.org/std/cell/struct.RefCell.html) and [`Mutex`](https://doc.rust-lang.org/std/sync/struct.Mutex.html). If there is the possibility of multi-threaded programming, then stick with `Mutex`, otherwise `RefCell` is sufficient.

Our linked list example above was still rather useless since there is no way to modify the list, since the value behind the `next` link is immutable. Let's fix this using `RefCell`:

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

#[derive(Debug)]
struct Node {
    val: i32,
    next: Option<Rc<RefCell<Node>>>
}

fn create_list() -> Node {
    let third = Node {
        val: 3,
        next: None,
    };
    let second = Node {
        val: 2,
        next: Some(Rc::new(RefCell::new(third))),
    };
    let first = Node {
        val: 1,
        next: Some(Rc::new(RefCell::new(second))),
    };
    return first;
}

fn main() {
    let list = create_list();
    list.next.as_ref().unwrap().borrow_mut().next = None;
    println!("LL={list:?}");
}
```
[Try it!](https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=7c2beb00d963077a322625d2c2c6cf61)

Here is a break down of the second line of the main:
* `list.next` obtains the `Option`.
* `as_ref()` borrows this so we now have `&Option`. Without this, the `unwrap()` call would take the ownership and we wouldn't be able to reference `list` in the print below.
* `unwrap()` returns the `&Rc` stored in the option.
* `borrow_mut()` returns the `&mut Node` stored in the `Rc`.
* We assign the value `None` which effectively removes the last element.

**NOTE:** The `RefCell::borow_mut()` still tries to enforce the mutual exclusion rule at runtime, and if it detects breaking that rule, then the program will crash.

This means, you need to be careful about what how long the scope of the `borrow_mut()` result exists.

The `Mutex::lock()` is the multi-threaded safe equivalent method.

## A Word On Linked Lists

* Use the builtin [`Vec`](https://doc.rust-lang.org/std/vec/struct.Vec.html) which is much more performant than any linked list implementation.
* If you do need single linked lists, a simple `Box<T>` is a better way to implement linked lists.
* If you need double linked lists, you will need either `Rc<RefCell<T>>` or `Arc<Mutex<T>>`.

## Conclusion

Sometimes the borrow checker limits what is possible in which case you can use several different escape hatches such as smart pointers or inner mutability, but these escape hatches do come with performance and/or safety losses. Therefore it is best if you can adhere to the borrow checker rules.

I hope this article series was helpful on your journey to Rust!