UnsafeCell: the only legal path to interior mutability

pub fn memo_fib(queries: Vec<u64>) -> Vec<u64>

Answer a list of Fibonacci queries using a memo table (a cache of answers already computed). The Fibonacci numbers are fib(0) == 0, fib(1) == 1, and fib(n) == fib(n - 1) + fib(n - 2) for n >= 2.

The contract:

• Every query is between 0 and 90 inclusive. fib(90) is 2,880,067,194,370,816,120, which fits in a u64, so no answer overflows.
• Queries may repeat and may arrive in any order. The list may be empty, in which case the answer is an empty list.
• The output has one answer per query, in the same order as the queries. For example, [10, 3, 10] gives [55, 2, 55].

The point of the exercise is how the cache is stored. It lives in struct Memo { cache: UnsafeCell<Vec<u64>> }, and the lookup method fib(&self, n: usize) -> u64 takes &self (a shared reference), not &mut self, yet it must add entries to the cache. The starter contains a helper method that Clippy (Rust's standard linter, run as cargo clippy) rejects; working out why is the lesson.

What UnsafeCell changes

A shared reference &T normally promises that the value it points to will not change while the reference is in use. The compiler is allowed to optimise on that promise, for example by reusing a value it already loaded instead of reading memory again. Changing data behind a plain &T is therefore undefined behaviour (UB): the program has broken a rule the compiler relies on, and Rust gives no guarantee about what it then does.

std::cell::UnsafeCell<T> is the type the language treats specially to lift that promise. Data inside an UnsafeCell may be changed while shared references to the cell exist. This is called interior mutability. The standard library's other interior-mutability types, such as Cell, RefCell, OnceCell, Mutex, RwLock and the atomic integer types, all store their data in an UnsafeCell and add their own rules (moving values in and out instead of lending a shared caller a reference to the contents, run-time borrow counting, locking, or atomic instructions) to make the mutation safe to use.

Three rules matter here:

1. It relaxes only the "shared means unchanged" promise. The promise that a &mut T is the only live reference to its target still holds. Two live &mut references to the same place are UB, inside an UnsafeCell or not.
2. To mutate the contents, get a raw pointer from the cell. get(&self) returns *mut T; raw_get does the same starting from a *const UnsafeCell<T>; and if you hold &mut UnsafeCell<T>, get_mut gives a &mut T safely. Do not cast a reference to a raw pointer and write through it (see the question below).
3. It does nothing about threads. UnsafeCell<T> does not implement Sync, so a type that contains one is not Sync unless its author writes an unsafe impl Sync and enforces a synchronisation rule (a lock or atomics) themselves. That is why Cell and RefCell cannot be shared between threads.

error: assigning to `&T` is undefined behavior, consider using an `UnsafeCell`

Why the starter's cache_mut helper is rejected

The starter contains this helper:

fn cache_mut(&self) -> &mut Vec<u64> {
    unsafe { &mut *self.cache.get() }
}

Clippy's mut_from_ref lint is in its correctness group, which is deny-by-default, and it rejects the signature:

error: mutable borrow from immutable input(s)

The problem is what the signature promises. Any number of &Memo references can exist at once, and this safe function turns each of them into a &mut Vec<u64>. Calling it twice and keeping both results gives two live &mut references to the same vector, which is UB, and neither call site contains the word unsafe. A safe function that lets safe callers cause UB is called unsound: the bug is in the API itself, however carefully it is called.

The fix is to keep the raw pointer and create the &mut only inside the method that uses it:

fn fib(&self, n: usize) -> u64 {
    // SAFETY: explain why no other reference to the cache is live here.
    let cache = unsafe { &mut *self.cache.get() };
    // ... extend and read `cache` ...
}

Here the &mut is a local variable. It cannot outlive the method body and is never returned, so the safety argument only has to cover this one function: nothing inside it calls fib again or creates another reference to the cache while cache is in use.

Writing the solution

1. Start the cache as UnsafeCell::new(vec![0, 1]), which holds fib(0) and fib(1).
2. For a query n, push new values (the sum of the last two entries) while cache.len() <= n, then return cache[n].
3. Use one Memo for the whole query list.

A repeated query, or one smaller than an earlier query, is answered from the table without new work, because filling up to n also fills every index below n.

Within the contract no addition overflows. The official solution uses wrapping_add only so that debug and release builds behave the same: in a debug build + panics on overflow, while a release build (with default settings) wraps silently. Either choice passes the tests.

The starter and solution also include impl Default for Memo. It is not required here. Clippy's new_without_default lint asks for it when a publicly reachable type has a public new() that takes no arguments, and this Memo is private, so the lint does not fire without it.

A note on threads

Because UnsafeCell<Vec<u64>> is not Sync, Memo is not Sync, so a &Memo cannot be sent to another thread. The compiler enforces this automatically. This design is sound with one thread; if two threads could call fib on the same Memo at once, they could write to the cache at the same time, which is a data race.

The standard library has SyncUnsafeCell, an UnsafeCell that is Sync when T: Sync, for code that provides its own synchronisation. It is still unstable in Rust 1.98.1 (using it on stable is error E0658). On stable you write a newtype around UnsafeCell<T> with an unsafe impl Sync, choose the bound on T that your synchronisation actually justifies (a lock that gives one thread at a time exclusive access, like Mutex, needs T: Send), and document that reasoning in a # Safety section.

What the tests cannot check

The grade is: the code compiles, the tests pass, and cargo clippy -- -D warnings reports nothing. If your safety comment is wrong and there is a path on which two &mut references into the cache are live at once, the tests can still pass, because UB does not reliably produce a wrong answer. Clippy's mut_from_ref catches the one helper shape above; other aliasing mistakes need a careful argument, or a run under Miri, which this grader does not do.