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 ofelements that have been initialized.

Naively, this means we just want this design:

  1. pub struct Vec<T> {
  2.     ptr: *mut T,
  3.     cap: usize,
  4.     len: usize,
  5. }
  6. # fn main() {}

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

As we saw in the ownership chapter, we should use Unique<T> in place of*mut T when we have a raw pointer to an allocation we own. 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 variant 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 except for the lastone in stable Rust:

  1. use std::marker::PhantomData;
  2. use std::ops::Deref;
  3. use std::mem;
  5. struct Unique<T> {
  6.     ptr: *const T,              // *const for variance
  7.     _marker: PhantomData<T>,    // For the drop checker
  8. }
  10. // Deriving Send and Sync is safe because we are the Unique owners
  11. // of this data. It's like Unique<T> is "just" T.
  12. unsafe impl<T: Send> Send for Unique<T> {}
  13. unsafe impl<T: Sync> Sync for Unique<T> {}
  15. impl<T> Unique<T> {
  16.     pub fn new(ptr: *mut T) -> Self {
  17.         Unique { ptr: ptr, _marker: PhantomData }
  18.     }
  20.     pub fn as_ptr(&self) -> *mut T {
  21.         self.ptr as *mut T
  22.     }
  23. }
  25. # fn main() {}

Unfortunately the mechanism for stating that your value is non-zero isunstable and unlikely to be stabilized soon. As such we’re just going totake the hit and use std’s Unique:

  1. #![feature(ptr_internals)]
  3. use std::ptr::{Unique, self};
  5. pub struct Vec<T> {
  6.     ptr: Unique<T>,
  7.     cap: usize,
  8.     len: usize,
  9. }
  11. # fn main() {}

If you don’t care about the null-pointer optimization, then you can use thestable code. However we will be designing the rest of the code around enablingthis optimization. It should be noted that Unique::new is unsafe to call, becauseputting null inside of it is Undefined Behavior. Our stable Unique doesn’tneed new to be unsafe because it doesn’t make any interesting guarantees aboutits contents.