Partial initialisation and leak-free unwinding: a `MaybeUninit` ring buffer

pub struct Ring<T> { buf: Box<[MaybeUninit<T>]>, head: usize, len: usize }

pub fn ring_script(cap: usize, ops: Vec<String>) -> Vec<String>

Build a fixed-capacity double-ended ring buffer on top of Box<[MaybeUninit<T>]>, then run a script over a Ring<String>.

cap may be 0. It may be 1. The window will wrap past the end of the array and straddle it, repeatedly. T = String, so a missed destructor leaks and a repeated one aborts.

The starter does not compile — extracting a T from a MaybeUninit<T> is a promise, and promises are unsafe.

The soundness burden, in one sentence

At every instant, exactly the slots in the logical window [head, head + len) (mod capacity) are initialised, and every other slot is not. Drop must call the destructor on exactly those and no others.

Get the wraparound wrong in one direction and you leak a slot; wrong in the other and you drop one twice. With T = String both are real: the leak is invisible, and the double free is a free() on a pointer the allocator has already reclaimed.

This is why a ring buffer is the canonical partially-initialised structure. A Vec has one boundary — len — and everything below it is live. A ring has two, and they move independently, and one of them wraps.

::: question What does MaybeUninit<T> actually do? It has the same size and alignment as T. It changes what the compiler is allowed to assume about the bytes — which is the only thing that ever mattered.

MaybeUninit<T> is a #[repr(transparent)] union containing a T and a zero-sized alternative. Same size, same alignment, same ABI. At runtime it is nothing. At the language level it says: these bytes may be uninitialised, may be an invalid value of T, and I promise nothing about them.

Without it there is no way to express a half-built array at all. [String; 8] is a type whose validity invariant demands eight valid Strings the moment the array exists; you cannot have seven. mem::uninitialized::<[String; 8]>() is instant undefined behaviour — and so is mem::uninitialized::<u32>(), because uninitialised bytes are formally invalid for every type with restricted values, not “some arbitrary number”. rustc’s invalid_value lint fires on both.

So MaybeUninit is not ceremony around a pointer cast. It is the type-level way to say “not yet a T“, and it is the only one. :::

The API you need

• MaybeUninit::uninit() — a slot with no promises;
• slot.write(value) — stores a value without dropping whatever was notionally there (correct for an empty slot, catastrophic for a full one);
• slot.assume_init_read() — moves the value out, leaving the bytes behind;
• slot.assume_init_ref() — borrows it as &T;
• slot.assume_init_drop() — runs the destructor in place.

Every assume_init* has the same total contract: fully initialised, and a valid T. Padding bytes are exempt.

Two construction gotchas, both of which will bite in the first five minutes:

vec![MaybeUninit::uninit(); n]                    // does NOT compile
(0..n).map(|_| MaybeUninit::uninit()).collect()   // this is the idiom
[const { MaybeUninit::uninit() }; N]              // for a fixed-size array

vec![x; n] needs Clone, and MaybeUninit<String> is not Clone. uninit_array never stabilised; the inline-const form replaced it.

::: question Drop for this type could iterate the whole array and call assume_init_drop on every slot. Why is that a bug rather than a shortcut? Because most of the array is uninitialised, and dropping an uninitialised String frees a garbage pointer.

The array has cap slots; only len of them hold values, and they are the ones in a window that may start anywhere and wrap. Dropping all cap runs String::drop on cap - len slots of whatever the allocator left there — usually a segfault, occasionally a silent corruption, and on a zeroed page a quiet no-op that makes the bug look intermittent.

The robust implementation derives the window on every step rather than computing it once:

impl<T> Drop for Ring<T> {
    fn drop(&mut self) {
        while self.pop_front().is_some() {}
    }
}

pop_front already knows how to find the front and how to shrink the window. Reusing it means the wraparound arithmetic exists in exactly one place, and a bug in it fails the ordinary pop_front tests rather than only the destructor. Prefer the implementation whose correctness you have already tested. :::

The real bugs, named

• (head + i) % cap when cap == 0 — a division by zero panic, and cap genuinely can be zero. Guard before you reach the modulo: at capacity zero every push is "full" and every pop is "none", so no slot is ever addressed.
• Using % where the index can exceed 2 * cap — % is fine for head + len when both are < cap, but if you ever add more than one capacity’s worth you need a real reduction, not a subtraction.
• push_front computing head - 1 with usize arithmetic — that underflows at head == 0. Write (head + cap - 1) % cap.
• Incrementing len before the write succeeds — see below.
• assume_init_read on a slot still inside the window — the value is now owned twice.

Exception safety, made concrete

A ring buffer is the natural place to see this, because a Drop running during unwinding over a half-updated structure is exactly the scenario.

If T‘s Clone, or a caller’s closure, or an allocation can panic partway through your push, the buffer must be left in a state whose Drop is still correct.

In practice that means: do the operation that can panic first, and update len last. Raise len before the value exists and an unwind runs Drop over a window containing an uninitialised slot — which is the double-free bug wearing a panic costume.

The general shape from item 17.21 applies here unchanged: update the length last, or use a drop guard whose own Drop repairs the invariant. And a drop guard whose Drop can itself panic aborts the process.

Lints

clippy::uninit_assumed_init is deny and catches MaybeUninit::uninit().assume_init() — the shortest possible undefined behaviour. clippy::len_without_is_empty and clippy::new_without_default are style/warn and fatal under -D warnings; with_capacity avoids the second, but you still need is_empty. clippy::manual_slice_size_calculation catches slice.len() * size_of::<T>() if you go looking for byte counts you do not need.

What this grader cannot check

A leak is invisible. If Drop returns immediately, every test here passes and every String in the buffer is gone forever. A double free usually aborts — and the harness allocates two thousand strings after the script to give a corrupted heap somewhere to fall over — but “usually” is the honest word, and the 50 000-operation case is there to make “usually” as close to “always” as a test can get.

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