Implementing `Vec`: layout, allocation, push, pop

pub struct MyVec<T> { ptr: NonNull<T>, len: usize, cap: usize }

pub fn vec_script(ops: Vec<String>) -> Vec<String>

Build Vec from scratch — allocator, growth, push, pop, get, Drop, and the two unsafe impls — then run a script of operations over a MyVec<String>. One string comes out per operation:

Capacity starts at 4 on the first push and doubles thereafter — the cap_at_least cases depend on that exact schedule. T = String, so every bookkeeping mistake has a real allocation behind it.

This is the item that ties the track together. It is also the point at which Vec stops being magic.

The four design decisions, in order

Why NonNull<T> and not *mut T? Two reasons from item 17.9: the niche (so Option<MyVec<T>> can pack) and covariance. *mut T is invariant; NonNull<T> is covariant, which is what an owning collection should be. It also means you must opt back out of covariance later if you ever hand out &mut T — item 17.19.

Why does an empty vec store NonNull::dangling()? Because Layout::array::<T>(0) is a zero-sized layout and passing one to alloc is undefined behaviour. There is no allocation to point at, and the field must still hold something non-null and aligned. cap == 0 is the flag that says “the pointer is a sentinel, do not free it”.

How does grow work? Layout::array::<T>(n) builds the layout. The first growth calls alloc; every later one calls realloc with the old layout and the new size — realloc copies the live bytes for you. A null return means allocation failure, and the correct response is alloc::handle_alloc_error(layout), not unwrap: it aborts with a proper message rather than unwinding through a half-grown vector.

What about the size limit? The Rust Reference requires that no single allocation exceed isize::MAX bytes, because pointer offsets are computed in isize. Layout::array catches the arithmetic overflow; the explicit isize::MAX assertion catches the case where it does not overflow but is still too large.

::: question push writes with ptr::write and pop reads with ptr::read. Why can neither be replaced by an ordinary assignment or an ordinary read? Because both slots are in the wrong state for the safe operation.

In push, slot len is uninitialised. An ordinary assignment *p = value would first drop whatever it believes is already there — which is garbage bytes interpreted as a String, so it would free a pointer that was never allocated. ptr::write stores without dropping, which is exactly right for an empty slot.

In pop, the slot is initialised and you need to move out of a place the compiler does not know you own. *p would be a copy, and String is not Copy (E0507). ptr::read produces a bitwise copy and hands you ownership — which duplicates ownership for an instant. That is only sound because you lowered len first, so the vector no longer counts that slot and Drop will never touch it.

The ordering is the safety argument, not a detail. Lower the length, then read. Write, then raise the length. :::

Drop, and exactly the layout you allocated with

impl<T> Drop for MyVec<T> {
    fn drop(&mut self) {
        if self.cap == 0 { return; }
        while self.pop().is_some() {}
        let layout = Layout::array::<T>(self.cap).expect("layout");
        // SAFETY: ...
        unsafe { alloc::dealloc(self.ptr.as_ptr().cast::<u8>(), layout) };
    }
}

Three things are load-bearing.

Elements first, then the buffer. Freeing the allocation before running the destructors leaks every String‘s heap buffer.

Exactly the layout that was allocated. The classic bug is deallocating with the new capacity after a growth path took a different branch than you thought — the allocator is told a size it never handed out, and on most allocators that is heap corruption rather than a clean failure.

Nothing at all when cap == 0. NonNull::dangling() was never allocated.

::: question while self.pop().is_some() {} runs every destructor. Why not ptr::drop_in_place on a slice of the whole buffer? You can, and std does — drop_in_place(slice::from_raw_parts_mut(ptr, len)) — but only over len, never over cap.

That is the trap worth naming. The allocation holds cap slots; only len of them contain values. Dropping cap slots runs String::drop on uninitialised memory: cap - len frees of pointers that were never allocated.

pop in a loop is slower and completely immune to that mistake, because it derives the count from len on every step. For a first implementation, prefer the version whose safety argument you can state in one clause. :::

The two unsafe impls

// SAFETY: ...
unsafe impl<T: Send> Send for MyVec<T> {}
// SAFETY: ...
unsafe impl<T: Sync> Sync for MyVec<T> {}

These are needed because MyVec<T> contains a NonNull<T>, and raw pointers are !Send and !Sync — so without them MyVec<String> would not be Send even though it plainly owns its data. The bounds are the whole content of the claim: a MyVec<T> is safe to move to another thread exactly when a T is, and safe to share exactly when a T is. Writing unsafe impl<T> Send for MyVec<T> {} without the bound would let you smuggle an Rc across a thread boundary, which is a data race on a non-atomic refcount.

Note that the auto-trait rules got it right by default; you are overriding a conservative answer, and the // SAFETY: comment is where you say why the conservative answer was too conservative.

Two style lints that will fail you

Both are style/warn, both are fatal under -D warnings, and both were hit while writing the reference solution:

• new_without_default — a pub fn new() with no arguments needs an impl Default.
• len_without_is_empty — a public len needs a public is_empty.

Two small impls. Write them first and forget about them.

Pitfalls that are real bugs

• dealloc with a different Layout than alloc used.
• dealloc when cap == 0 — the pointer is the dangling sentinel.
• cap * 2 overflowing on a 32-bit target.
• Bumping len before the write succeeds.
• Dropping cap elements instead of len.

Zero-sized types are excluded by the assert!(size_of::<T>() != 0) in new. Layout::array::<ZST>(n) is zero-sized for every n, so the whole allocation story degenerates and needs a completely separate code path. std has one. You are not writing it today.

What this grader cannot check

A leak is invisible: if Drop frees the buffer without dropping the elements, every test here passes. A double free or a wrong layout usually aborts, and the harness allocates two thousand strings after your script finishes so a corrupted heap has somewhere to fall over — but “usually” is the honest word. Miri would settle it; Miri cannot run here.

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