37.2 RefCell

The RefCell pointer type implements single ownership like Box, but enforces borrowing rules only at runtime.

By default the following borrowing rules are enforced at compile time:

• At any given time, an object can have either one mutable reference or any number of immutable references (but not both).

• References must always be valid.

The implementation of RefCell, on the other hand, enforces these same rules at runtime. This means that:

• RefCell allows the checking of mutable borrow at runtime for its internal value.

• RefCell does this while itself is immutable.

• RefCell allows multiple immutable borrows at the same time.

• RefCell allows only one mutable borrow at a time.

• If the borrowing rules are violated, a panic!() is issued.

As an example we are going to create a Fib structure that computes numbers from the Fibonacci sequence, but uses a cache to speed up computing of the current request and future requests. As the computing method get() should not modify anything from the perspective of the Fib’s caller, it takes an immutable self instance. But since it possibly needs to modify the cache, we will use a RefCell for the cache. This caching technique for a function is called Memoization.

Here is the code of our Fib structure, we use a vector of 64-bit integers for the cache:

:clear

use std::cell::RefCell;

struct Fib {
  cache: RefCell<Vec<u64>>,
}

The constructor initializes the cache with an empty vector:

impl Fib {
  fn new() -> Self {
    Fib { cache: RefCell::new(Vec::new()) }
  }
}

The get() method computes a Fibonacci value, checking if the value is already computed and stored into the cache, or computing the value and storing it into the cache:

impl Fib {
  fn get(&self, n: u64) -> u64 {

    // Stop condition
    if n < 2 { return n; }

    // Cached value
    let i = n as usize; // Convert to index
    let cached = self.cache.borrow().get(i).copied();
    if let Some(v) = cached && v != 0 {
      return v;
    }

    // Compute new value
    let v = self.get(n - 1) + self.get(n - 2);

    // Store new value
    let mut cache = self.cache.borrow_mut();
    if cache.len() <= i {
      cache.resize(i + 1, 0); // Grow the Vec so index n exists
    }
    cache[i] = v;

    // Return computed value
    v
  }
}

We create a new instance of Fib:

let fib = Fib::new();

Here is the computing of the 50th number of the Fibonacci sequence:

fib.get(50)

see solution