58. Inside Vec, String, Box, and trait objects

58.1 Build a Vec to understand Vec

Vec<T> is a pointer, a capacity, and a length, plus a small amount of unsafe code that keeps this invariant: the first len slots are initialized, and the slots from len to cap are allocated but uninitialized. Here is a working version:

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

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

// SAFETY: MiniVec owns its elements, exactly like Vec<T>, so it is Send/Sync when T is.
unsafe impl<T: Send> Send for MiniVec<T> {}
unsafe impl<T: Sync> Sync for MiniVec<T> {}

impl<T> MiniVec<T> {
    pub const fn new() -> Self {
        assert!(size_of::<T>() != 0, "zero-sized types are not supported in this sketch");
        Self { ptr: NonNull::dangling(), cap: 0, len: 0 }   // no allocation until the first push
    }

    fn grow(&mut self) {
        let new_cap = if self.cap == 0 { 4 } else { self.cap.checked_mul(2).expect("capacity overflow") };
        let new_layout = Layout::array::<T>(new_cap).expect("allocation too large");
        // SAFETY: new_layout has non-zero size (T is not a ZST and new_cap > 0). For realloc, the old
        // pointer was allocated by us with exactly Layout::array::<T>(self.cap).
        let raw = unsafe {
            if self.cap == 0 {
                alloc::alloc(new_layout)
            } else {
                alloc::realloc(self.ptr.as_ptr().cast(), Layout::array::<T>(self.cap).unwrap(), new_layout.size())
            }
        };
        self.ptr = NonNull::new(raw.cast()).unwrap_or_else(|| alloc::handle_alloc_error(new_layout));
        self.cap = new_cap;
    }

    pub fn push(&mut self, value: T) {
        if self.len == self.cap { self.grow(); }
        // SAFETY: len < cap, so the slot is allocated, and it is uninitialized, so write (not assign).
        unsafe { ptr::write(self.ptr.as_ptr().add(self.len), value) };
        self.len += 1;
    }

    pub fn pop(&mut self) -> Option<T> {
        if self.len == 0 { return None; }
        self.len -= 1;
        // SAFETY: slot `len` was initialized; after decrementing len we treat it as moved out.
        Some(unsafe { ptr::read(self.ptr.as_ptr().add(self.len)) })
    }

    pub fn capacity(&self) -> usize { self.cap }
}

impl<T> Deref for MiniVec<T> {
    type Target = [T];
    fn deref(&self) -> &[T] {
        // SAFETY: the first `len` elements are initialized; ptr is non-null and aligned (dangling is fine for len 0).
        unsafe { std::slice::from_raw_parts(self.ptr.as_ptr(), self.len) }
    }
}
impl<T> DerefMut for MiniVec<T> {
    fn deref_mut(&mut self) -> &mut [T] {
        // SAFETY: as above, and &mut self guarantees exclusive access.
        unsafe { std::slice::from_raw_parts_mut(self.ptr.as_ptr(), self.len) }
    }
}

impl<T> Drop for MiniVec<T> {
    fn drop(&mut self) {
        // SAFETY: drop exactly the initialized elements, then free the buffer with the layout we allocated.
        unsafe {
            ptr::drop_in_place(ptr::slice_from_raw_parts_mut(self.ptr.as_ptr(), self.len));
            if self.cap != 0 { alloc::dealloc(self.ptr.as_ptr().cast(), Layout::array::<T>(self.cap).unwrap()); }
        }
    }
}

fn main() {
    let mut v = MiniVec::new();
    for i in 0..10 { v.push(format!("item-{i}")); }   // heap-owning elements exercise Drop
    v[0].push_str("-edited");                          // DerefMut to [String]
    let last = v.pop();                                // pop first: printing v[0] and calling pop() in one
                                                       // println! would borrow v twice (E0502, Ch 7)
    println!("len={} cap={} first={} last={last:?}", v.len(), v.capacity(), v[0]);
    println!("{}", v.iter().filter(|s| s.ends_with('3')).count()); // slice methods come free via Deref
}

cargo +nightly miri run --bin minivec    # checks every unsafe access; it reports leaks, UB, and double drops

Each unsafe block has a SAFETY comment that refers to the invariant. The public API (push, pop, indexing through Deref) cannot break that invariant, so safe code using MiniVec cannot cause UB. That is the whole technique behind the standard library's collections. The real Vec adds zero-sized-type support, allocator parameters, and a lot of performance work. The Rustonomicon builds it step by step.

58.2 String and Box

• String is a Vec<u8> plus the invariant "the bytes are valid UTF-8". Every method that could break that invariant either checks it or is unsafe (from_utf8_unchecked, as_mut_vec).
• Box<T> is a non-null pointer to a heap allocation that it owns. The compiler knows how to move a value out of it with *boxed, which no other type can do.

58.3 Trait objects vs Go interfaces