Layout

First off, we need to come up with the struct layout. A Vec has three parts: a pointer to the allocation, the size of the allocation, and the number of elements that have been initialized.

Naively, this means we just want this design:

pub struct Vec<T> {
    ptr: *mut T,
    cap: usize,
    len: usize,
}

And indeed this would compile. Unfortunately, it would be incorrect. First, the compiler will give us too strict variance. So a &Vec<&'static str> couldn't be used where an &Vec<&'a str> was expected. More importantly, it will give incorrect ownership information to the drop checker, as it will conservatively assume we don't own any values of type T. See the chapter on ownership and lifetimes for all the details on variance and drop check.

As we saw in the ownership chapter, the standard library uses Unique<T> in place of *mut T when it has a raw pointer to an allocation that it owns. Unique is unstable, so we'd like to not use it if possible, though.

As a recap, Unique is a wrapper around a raw pointer that declares that:

We are covariant over T
We may own a value of type T (for drop check)
We are Send/Sync if T is Send/Sync
Our pointer is never null (so Option<Vec<T>> is null-pointer-optimized)

We can implement all of the above requirements in stable Rust. To do this, instead of using Unique<T> we will use NonNull<T>, another wrapper around a raw pointer, which gives us two of the above properties, namely it is covariant over T and is declared to never be null. By adding a PhantomData<T> (for drop check) and implementing Send/Sync if T is, we get the same results as using Unique<T>:

use std::ptr::NonNull;
use std::marker::PhantomData;

pub struct Vec<T> {
    ptr: NonNull<T>,
    cap: usize,
    len: usize,
    _marker: PhantomData<T>,
}

unsafe impl<T: Send> Send for Vec<T> {}
unsafe impl<T: Sync> Sync for Vec<T> {}
fn main() {}

The Rustonomicon

Layout