`OnceCell`: write-once interior mutability

Memoise an expensive computation behind a read-only API, and make the memoisation observable.

pub fn cached_stats(data: Vec<i64>, queries: Vec<String>) -> (Vec<i64>, usize)

A Stats value owns data, a lazily-computed sorted copy, and a counter of how many times the sort actually ran. All of its query methods take &self.

On empty data every numeric answer is 0 (but the sort still counts as having run if it was needed).

Return (the answers in query order, the number of times the sort ran). That second number is the real assertion: it must be exactly 1 no matter how many queries needed it, and exactly 0 if none did.

The third blessed use of interior mutability

The standard library says interior mutability should be a last resort, and then names three cases where it is right. One of them is this: a logically immutable operation that caches internally.

stats.median() does not change the statistics. From the caller’s point of view nothing happened except a number came back. That it computed and remembered a sorted copy on the way is an implementation detail — so the method should take &self, and something inside has to be able to write through that shared reference.

Why RefCell<Option<T>> is the wrong tool, exactly

Almost everyone reaches for it, and the starter shows why it does not work:

fn sorted(&self) -> &[i64] {
    …
    self.sorted.borrow().as_ref().unwrap()
}

error[E0515]: cannot return reference to temporary value

The Ref guard is a local. Handing out a reference into it would let the caller keep reading after the borrow flag had been cleared — the same E0515 you met when you first tried to return a &Vec out of a RefCell. Your options with a RefCell are to return the guard (which forces every caller to think about borrow scopes, and reintroduces the panic risk) or to clone on every call (which defeats the point of caching).

OnceCell<T>: the hybrid the other cells could not be

sorted: OnceCell<Vec<i64>>
…
self.sorted.get_or_init(|| /* expensive */)   // -> &Vec<i64>

OnceCell hands out a real &T, with the lifetime of &self, like RefCell cannot — and it needs no runtime borrow bookkeeping, like Cell does not. Both at once, and the reason is one restriction:

The value can only be written once. After that it never moves, so a reference to it can never be invalidated while the cell lives.

There is no borrow counter, because there is nothing to count: no writer can ever appear after a reader. get_or_init runs your closure on the first call and returns the stored value on every subsequent call, which is exactly a memoisation and exactly what makes the sort counter come out at 1.

The other methods: get() returns Option<&T> without initialising; set(v) returns Result<(), T> — note that carefully, it gives your value back in the Err when the cell was already full, and ignoring the result silently drops it; into_inner() consumes the cell.

One rule to respect: get_or_init‘s closure must not touch the same cell. Re-entering it panics. In this problem the closure reads self.data and self.sorts, never self.sorted, so there is no way in.

LazyCell, and the thread-safe twins

LazyCell<T, F> is OnceCell with the initialiser baked in at construction — you write LazyCell::new(|| expensive()) and then just deref it. Use it when the initialiser is fixed and known at the definition site; use OnceCell when the initialiser needs data that only the call site has, which is the common case in a method.

Both are !Sync, so neither can live in a static. The thread-safe twins are OnceLock and LazyLock, and they are what you want for a global configuration or a compiled-once table. Same API shape, an atomic instead of a plain flag.

Two limits worth knowing

After initialisation you still cannot mutate without &mut self. OnceCell is a cache, not a mutable field. If the cached value needs to be invalidated — the underlying data changed — OnceCell is the wrong type and you are back to RefCell, with the panic risk you now know how to reason about.

The counter is a Cell, not a RefCell. It holds a usize, which is Copy and swapped wholesale — the exact shape Cell exists for. Reaching for RefCell<usize> here would add a runtime borrow check and a panic path to an increment.