FerrousPath

Level 4 · Expert· Lesson 9 of 9 · 50 min

Capstone: implementing Vec

Build a growable array from raw allocation — NonNull, Layout, growth, zero-sized types, Drop, Deref, IntoIter — and audit it for soundness.

This capstone ties Level 4 together. You will build MyVec<T> from the allocator up, in the style of the Rustonomicon, and each design decision will call on an earlier lesson: layout, variance, drop check, panic safety, uninitialised memory.

The complete implementation is below as one runnable program. Read the commentary that follows with the code in view, then run it — and run it under Miri on the Playground.

use std::alloc::{self, Layout};
use std::marker::PhantomData;
use std::mem;
use std::ops::{Deref, DerefMut};
use std::ptr::{self, NonNull};

// ───────────────────────── RawVec: owns the allocation, not the elements ─────────────────────────

struct RawVec<T> {
    ptr: NonNull<T>,
    cap: usize,
}

impl<T> RawVec<T> {
    const IS_ZST: bool = mem::size_of::<T>() == 0;

    fn new() -> Self {
        // A ZST vector never allocates and can hold "infinitely" many elements.
        let cap = if Self::IS_ZST { usize::MAX } else { 0 };
        RawVec { ptr: NonNull::dangling(), cap }
    }

    fn grow(&mut self) {
        // With cap == usize::MAX a ZST vector can only get here by overflowing its length.
        assert!(!Self::IS_ZST, "capacity overflow");

        let (new_cap, new_layout) = if self.cap == 0 {
            (4, Layout::array::<T>(4).unwrap())
        } else {
            let new_cap = self.cap.checked_mul(2).expect("capacity overflow");
            // Layout::array fails if the size would exceed isize::MAX — a hard limit
            // that pointer offsets rely on.
            (new_cap, Layout::array::<T>(new_cap).expect("capacity overflow"))
        };

        let new_ptr = if self.cap == 0 {
            // SAFETY: new_layout has non-zero size (T is not a ZST, new_cap > 0).
            unsafe { alloc::alloc(new_layout) }
        } else {
            let old_layout = Layout::array::<T>(self.cap).unwrap();
            // SAFETY: ptr was allocated by this allocator with old_layout; the new size is
            // non-zero and does not overflow isize when rounded up to the alignment.
            unsafe { alloc::realloc(self.ptr.as_ptr().cast(), old_layout, new_layout.size()) }
        };

        // On failure the old allocation is untouched; abort rather than unwind.
        self.ptr = NonNull::new(new_ptr.cast()).unwrap_or_else(|| alloc::handle_alloc_error(new_layout));
        self.cap = new_cap;
    }
}

impl<T> Drop for RawVec<T> {
    fn drop(&mut self) {
        if self.cap != 0 && !Self::IS_ZST {
            // SAFETY: allocated in `grow` with exactly this layout.
            unsafe { alloc::dealloc(self.ptr.as_ptr().cast(), Layout::array::<T>(self.cap).unwrap()) };
        }
    }
}

// ───────────────────────── MyVec: tracks which elements are initialised ─────────────────────────

pub struct MyVec<T> {
    buf: RawVec<T>,
    len: usize,
    _owns: PhantomData<T>, // we own T values and will drop them
}

// SAFETY: MyVec<T> owns its elements uniquely, like Vec<T>.
unsafe impl<T: Send> Send for MyVec<T> {}
unsafe impl<T: Sync> Sync for MyVec<T> {}

impl<T> MyVec<T> {
    pub fn new() -> Self {
        MyVec { buf: RawVec::new(), len: 0, _owns: PhantomData }
    }

    fn ptr(&self) -> *mut T {
        self.buf.ptr.as_ptr()
    }

    pub fn push(&mut self, value: T) {
        if self.len == self.buf.cap {
            self.buf.grow();
        }
        // SAFETY: len < cap, so the slot is inside the allocation and uninitialised.
        // `write` does not drop the (garbage) previous contents.
        unsafe { self.ptr().add(self.len).write(value) };
        self.len += 1;
    }

    pub fn pop(&mut self) -> Option<T> {
        if self.len == 0 {
            return None;
        }
        self.len -= 1;
        // SAFETY: slot `len` was initialised; decrementing len first means we will never
        // read or drop it again, so moving the value out with `read` is not a double use.
        Some(unsafe { self.ptr().add(self.len).read() })
    }

    pub fn insert(&mut self, index: usize, value: T) {
        assert!(index <= self.len, "index out of bounds");
        if self.len == self.buf.cap {
            self.buf.grow();
        }
        // SAFETY: index <= len < cap. Shifting [index, len) up by one stays in bounds.
        // The ranges overlap, so this must be `copy` (memmove), not copy_nonoverlapping.
        unsafe {
            let p = self.ptr().add(index);
            ptr::copy(p, p.add(1), self.len - index);
            p.write(value);
        }
        self.len += 1;
    }

    pub fn remove(&mut self, index: usize) -> T {
        assert!(index < self.len, "index out of bounds");
        self.len -= 1;
        // SAFETY: index < old len. Read the element out, then close the gap.
        unsafe {
            let p = self.ptr().add(index);
            let value = p.read();
            ptr::copy(p.add(1), p, self.len - index);
            value
        }
    }
}

impl<T> Drop for MyVec<T> {
    fn drop(&mut self) {
        // SAFETY: the first `len` elements are initialised and are dropped exactly once.
        // Dropping them as a slice also handles a panicking element destructor correctly.
        unsafe { ptr::drop_in_place(ptr::slice_from_raw_parts_mut(self.ptr(), self.len)) };
        // `buf` is dropped afterwards (field drop glue) and frees the memory.
    }
}

// Deref to a slice gives us len, iter, sort, indexing, binary_search… for free.
impl<T> Deref for MyVec<T> {
    type Target = [T];
    fn deref(&self) -> &[T] {
        // SAFETY: ptr is non-null and aligned (dangling is fine for len 0 or ZSTs);
        // the first `len` elements are initialised.
        unsafe { std::slice::from_raw_parts(self.ptr(), self.len) }
    }
}

impl<T> DerefMut for MyVec<T> {
    fn deref_mut(&mut self) -> &mut [T] {
        // SAFETY: as above, and &mut self guarantees uniqueness.
        unsafe { std::slice::from_raw_parts_mut(self.ptr(), self.len) }
    }
}

// ───────────────────────── IntoIter: consuming iteration ─────────────────────────

pub struct IntoIter<T> {
    _buf: RawVec<T>, // keeps the allocation alive; frees it on drop
    start: *const T,
    end: *const T,   // for ZSTs: start + remaining count, as an address
}

impl<T> IntoIterator for MyVec<T> {
    type Item = T;
    type IntoIter = IntoIter<T>;

    fn into_iter(self) -> IntoIter<T> {
        // Take the buffer out without running MyVec's destructor (which would drop the elements).
        let this = mem::ManuallyDrop::new(self);
        // SAFETY: `this` is never used or dropped again, so the buffer is moved out exactly once.
        let buf = unsafe { ptr::read(&this.buf) };
        let start = buf.ptr.as_ptr() as *const T;
        let end = if RawVec::<T>::IS_ZST {
            start.wrapping_byte_add(this.len)
        } else {
            // SAFETY: len <= cap, so this is at most one past the end of the allocation.
            unsafe { start.add(this.len) }
        };
        IntoIter { _buf: buf, start, end }
    }
}

impl<T> Iterator for IntoIter<T> {
    type Item = T;

    fn next(&mut self) -> Option<T> {
        if self.start == self.end {
            return None;
        }
        if RawVec::<T>::IS_ZST {
            self.end = self.end.wrapping_byte_sub(1);
            // SAFETY: a ZST can be "read" from any non-null aligned pointer.
            Some(unsafe { NonNull::<T>::dangling().as_ptr().read() })
        } else {
            let item = self.start;
            // SAFETY: start < end, so `item` is initialised and start+1 is in bounds.
            unsafe {
                self.start = self.start.add(1);
                Some(item.read())
            }
        }
    }
}

impl<T> Drop for IntoIter<T> {
    fn drop(&mut self) {
        for _ in &mut *self {} // drop the elements that were not consumed
        // `_buf` then frees the allocation.
    }
}

// ───────────────────────── exercising it ─────────────────────────

fn main() {
    let mut v = MyVec::new();
    for word in ["delta", "alpha", "charlie"] {
        v.push(String::from(word));
    }
    v.insert(1, String::from("bravo"));
    v.sort(); // slice method, via DerefMut
    println!("{:?}  len={}", &*v, v.len());
    println!("removed {:?}, popped {:?}", v.remove(0), v.pop());

    let upper: Vec<String> = v.into_iter().map(|s| s.to_uppercase()).collect();
    println!("{upper:?}");

    // Zero-sized elements: no allocation at all.
    let mut units = MyVec::new();
    for _ in 0..1_000 {
        units.push(());
    }
    println!("{} units, then {} via IntoIter", units.len(), units.into_iter().count());

    // Partially consumed iterator: the rest must still be dropped (check under Miri).
    let mut it = {
        let mut v = MyVec::new();
        for i in 0..5 { v.push(Box::new(i)); }
        v.into_iter()
    };
    println!("{:?} {:?}", it.next(), it.next());
}

Design notes

NonNull<T>, not *mut T

From the variance lesson: *mut T is invariant, which would make MyVec<&'static str> unusable where MyVec<&'a str> is expected. NonNull<T> is covariant and gives Option<MyVec<T>> a niche. It also removes Send and Sync, so we restore them with bounded unsafe impls.

PhantomData<T>

NonNull<T> says “points at T”, not “owns T”. The marker states ownership for the drop checker. Because our Drop impl is not #[may_dangle], the compiler is already conservative; the field documents intent and matches what std does.

Separating RawVec from MyVec

RawVec owns memory: allocate, grow, free. MyVec and IntoIter own elements: which slots are initialised. Each has its own Drop. This is exactly how the standard library is organised, and it lets IntoIter reuse the deallocation logic without duplicating it.

The safety invariants

Everything in the module relies on these, and every method must restore them before returning or panicking:

  1. buf.ptr is either dangling (when cap == 0 or T is a ZST) or points to an allocation for exactly cap values of T.
  2. len <= cap.
  3. The elements at indices 0..len are initialised; those at len..cap are not.
  4. The allocation is at most isize::MAX bytes.

len and buf are private fields. That privacy is load-bearing: if safe code outside the module could set len, every unsafe block here would be unsound. The unit of unsafe reasoning is the module, not the block.

Allocation

  • Layout::array::<T>(n) computes size and alignment and fails on overflow past isize::MAX.
  • alloc with a zero-sized layout is undefined behaviour — hence the special cases for cap == 0 and for ZSTs.
  • Allocation failure calls handle_alloc_error, which aborts. Unwinding from an out-of-memory condition inside a collection would make panic safety almost impossible.
  • Growth doubles the capacity, giving amortised O(1) push.

Moving values in and out

Operation Use Because
Put a value into uninitialised memory ptr.write(v) does not drop the old contents
Take a value out, leaving the slot logically uninitialised ptr.read() bitwise copy; you must ensure it is never read or dropped again
Shift a range ptr::copy memmove; overlap allowed
Drop in place ptr::drop_in_place runs destructors without moving

In pop and remove, len is decremented before the value is read out. If the order were reversed and something panicked in between, the destructor could drop the element a second time.

Panic safety

Which calls in this code can panic? assert!, expect, and — crucially — nothing user-defined while the structure is inconsistent. push, insert and remove call no user code between breaking and restoring an invariant. A Clone-based extend_from_slice, or retain with a user closure, would need the guard technique from the drop-check lesson.

Zero-sized types

For a ZST, ptr.add(n) does not change the address, so start == end would always hold and the iterator would be empty. The implementation instead treats the pointer as a counter with wrapping_byte_add. This is the same trick the standard library uses.

Auditing

Do not trust the code because it prints the right thing. Verify it:

  1. Miri. Copy the program to the Playground and press Miri. It checks every access for bounds, initialisation, aliasing and leaks. A clean run over tests that exercise growth, ZSTs, and a partially consumed IntoIter is strong evidence.
  2. Adversarial element types. Test with a type that counts drops (assert each value is dropped exactly once), and with one whose Drop panics.
  3. Compare with the source. Read library/alloc/src/raw_vec.rs and vec/mod.rs in the Rust repository. You will recognise nearly everything, and the differences — the allocator parameter, #[may_dangle], in-place collection specialisations — are instructive.

Level 4 checkpoint

You are ready for Level 5 if you can:

  • Compute the layout of a repr(C) struct and explain niche optimisation.
  • State the variance of &'a mut T, Cell<T> and fn(T), and justify each with an exploit that would otherwise compile.
  • Explain what Pin guarantees and write a projection.
  • Choose orderings for a publish/consume protocol and say which happens-before edge each provides.
  • Explain ABA and one reclamation scheme.
  • Write a waker and an executor loop.
  • Argue the soundness of a small unsafe abstraction in terms of its invariants.

Exercises

  1. Add with_capacity, reserve, truncate and clear. Which of these must think about panics in element destructors?
  2. Implement drain(..) returning an iterator that removes all elements. Make it leak-safe: if the Drain is forgotten with mem::forget, the vector must not expose moved-out elements. (Hint: set len = 0 up front.)
  3. Implement retain(&mut self, f: impl FnMut(&T) -> bool) and make it panic-safe with a drop guard. Test with a closure that panics halfway.
  4. Implement Clone for MyVec<T: Clone>. If the third element’s clone panics, what happens to the two clones already made? Make sure they are dropped and the buffer freed.
  5. Write a DropCounter test type and a property test that performs random sequences of operations on MyVec and Vec in parallel, asserting equal contents and exactly-once drops. Run it under Miri.
  6. Add an allocator parameter MyVec<T, A: Allocator> on nightly and compare with std.

Check your understanding

Pick an answer to see the explanation.

  1. 1.Why does the implementation use ptr::write(slot, value) rather than *slot = value when pushing?

  2. 2.Why must capacity for a zero-sized T be treated specially?

  3. 3.In insert, why is ptr::copy used and not ptr::copy_nonoverlapping?

Finished the lesson and the exercises?