`UnsafeCell`: the only legal path to interior mutability

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

Answer a list of Fibonacci queries with a memo table. The cache lives in a struct Memo { cache: UnsafeCell<Vec<u64>> }, and the lookup method takes &self — not &mut self. Queries arrive in any order, repeat freely, and never exceed 90 (so every answer fits in a u64). fib(0) == 0, fib(1) == 1.

The starter contains the helper everybody writes first, and it is rejected by a deny-by-default clippy lint. That rejection is the lesson.

The one construct that retracts a language guarantee

Normally &T promises the pointee will not change while the reference is live. That promise is not a convention; the optimiser acts on it, caching loads across calls and reordering freely.

UnsafeCell<T> is the single language-level construct that retracts it. It is a #[repr(transparent)] wrapper the compiler knows about specially, and it is the foundation of every interior-mutability type in std: Cell, RefCell, Mutex, RwLock, AtomicUsize, OnceCell. All of them are UnsafeCell plus a bookkeeping strategy.

Three rules, stated exactly:

1. It relaxes only the shared-reference immutability guarantee. The &mut uniqueness guarantee is completely untouched — there is no legal way to obtain two live &mut to the same place, UnsafeCell or not.
2. The only valid way to get a *mut T to the contents of a shared UnsafeCell<T> is .get() or .raw_get(). Casting &UnsafeCell<T> to *const T and then to *mut T is not the same thing and is not sanctioned.
3. It does nothing about data races. Concurrent conflicting access still needs atomics or a lock. UnsafeCell<T> is !Sync, which is exactly why Cell and RefCell are single-threaded types.

::: question What does rustc say if you try the cast route — &x as *const T as *mut T — and write through it? It refuses, by name:

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

That is invalid_reference_casting, and it is deny-by-default. rustc grew the lint because the cast is the obvious-looking workaround and it is always wrong: the immutability guarantee attaches to the &T, and no amount of casting removes a guarantee that was already made.

Note what the diagnostic does: it names the correct tool. UnsafeCell is not a loophole you found; it is the sanctioned mechanism, and using it is how you tell the compiler “do not assume this place is frozen” — which it then does not. :::

Why fn cache_mut(&self) -> &mut Vec<u64> is rejected

It is the first thing everybody writes, and clippy’s mut_from_ref is correctness/deny and stops it:

error: mutable borrow from immutable input(s)

The lint is not being fussy about style. Think about what that signature promises. It says: given any &Memo — of which there may be arbitrarily many, simultaneously — hand back a &mut Vec<u64>. Call it twice and you have two live &mut to the same place, which is undefined behaviour, produced by entirely safe code, with no unsafe at either call site. The function is unsound: not “risky”, not “needs care” — a bug in the API regardless of how carefully anyone calls it.

The fix is the real lesson: keep the pointer raw, and mint the reference only at the point of use.

fn fib(&self, n: usize) -> u64 {
    // SAFETY: ... why no other reference is live right now ...
    let cache = unsafe { &mut *self.cache.get() };
    ...
}

Here the &mut is a local. Its lifetime is bounded by the body. Nothing escapes, so nothing can alias, and the safety argument is a statement about this function rather than about every possible caller — which is the only kind of statement you can actually verify.

::: question self.cache.get() returns *mut Vec<u64> and needs no unsafe. Why not? Because obtaining a raw pointer is always safe. The obligation is at the dereference.

This is the create-versus-deref asymmetry from item 17.5, and it is why the “keep it raw, mint late” tactic works at all: raw pointers can be stored, copied, offset and passed around with no aliasing consequences whatsoever. The aliasing models — Stacked Borrows, Tree Borrows — constrain references. Every & or &mut you create performs a retag that can invalidate siblings; a *mut does not.

So the discipline for shared-mutable data structures is: hold raw pointers in your fields, convert to a reference for the shortest possible window, and never return a reference whose lifetime you did not tie to a &mut self. Item 17.14 is the full story. :::

Writing this one

UnsafeCell::new(vec![0, 1]) seeds the table with fib(0) and fib(1). On a query for n, extend the table until cache.len() > n, then return cache[n]. Repeat queries hit the table and do no work; out-of-order queries are automatic, because filling to n fills everything below n too.

fib(90) is 2 880 067 194 370 816 120, comfortably inside u64. The problem guarantees n <= 90, but note that -O turns off overflow checks, so a larger n would wrap silently rather than panic — use wrapping_add and be explicit about it rather than relying on a check that is not there.

Note the impl Default. Clippy’s new_without_default is style/warn, which under -D warnings is a failure, and it fires on any pub type with a pub fn new() taking no arguments. Two lines, once.

A note on threads

UnsafeCell<T> is !Sync, so Memo is !Sync, so &Memo cannot cross a thread boundary. That is the auto-trait system doing exactly the right thing for free — and it is why this design is sound single-threaded and would be a data race if you forced it across threads.

Rust has a SyncUnsafeCell for the case where you want the shared-mutability relaxation and Sync, and have your own synchronisation. It is still unstable on 1.95, so if you need it you hand-roll it: a newtype around UnsafeCell<T> with an unsafe impl<T: Send> Sync and a # Safety section explaining what discipline makes it sound.

What this grader cannot check

If your safety comment is wrong — if there is a path on which two &mut into the cache are live at once — every test here still passes, because the aliasing violation is invisible at runtime on this input. The check is your argument, plus mut_from_ref catching the one shape that is unsound by construction. Item 17.14 is about the tool that would catch the rest, and why it cannot run here.

Remember the grade is compile + tests + clippy -D warnings.