Rust Borrow Checker Explained Part 5: Escape Hatches

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 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:

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!

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 and Rc. 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:

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() 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 and Mutex. 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:

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!

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 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!