src/doc/nomicon/vec-layout.md

   1 % Layout
   2
   3 First off, we need to come up with the struct layout. A Vec has three parts:
   4 a pointer to the allocation, the size of the allocation, and the number of
   5 elements that have been initialized.
   6
   7 Naively, this means we just want this design:
   8
   9 ```rust
  10 pub struct Vec<T> {
  11     ptr: *mut T,
  12     cap: usize,
  13     len: usize,
  14 }
  15 # fn main() {}
  16 ```
  17
  18 And indeed this would compile. Unfortunately, it would be incorrect. First, the
  19 compiler will give us too strict variance. So a `&Vec<&'static str>`
  20 couldn't be used where an `&Vec<&'a str>` was expected. More importantly, it
  21 will give incorrect ownership information to the drop checker, as it will
  22 conservatively assume we don't own any values of type `T`. See [the chapter
  23 on ownership and lifetimes][ownership] for all the details on variance and
  24 drop check.
  25
  26 As we saw in the ownership chapter, we should use `Unique<T>` in place of
  27 `*mut T` when we have a raw pointer to an allocation we own. Unique is unstable,
  28 so we'd like to not use it if possible, though.
  29
  30 As a recap, Unique is a wrapper around a raw pointer that declares that:
  31
  32 * We are variant over `T`
  33 * We may own a value of type `T` (for drop check)
  34 * We are Send/Sync if `T` is Send/Sync
  35 * We deref to `*mut T` (so it largely acts like a `*mut` in our code)
  36 * Our pointer is never null (so `Option<Vec<T>>` is null-pointer-optimized)
  37
  38 We can implement all of the above requirements except for the last
  39 one in stable Rust:
  40
  41 ```rust
  42 use std::marker::PhantomData;
  43 use std::ops::Deref;
  44 use std::mem;
  45
  46 struct Unique<T> {
  47     ptr: *const T,              // *const for variance
  48     _marker: PhantomData<T>,    // For the drop checker
  49 }
  50
  51 // Deriving Send and Sync is safe because we are the Unique owners
  52 // of this data. It's like Unique<T> is "just" T.
  53 unsafe impl<T: Send> Send for Unique<T> {}
  54 unsafe impl<T: Sync> Sync for Unique<T> {}
  55
  56 impl<T> Unique<T> {
  57     pub fn new(ptr: *mut T) -> Self {
  58         Unique { ptr: ptr, _marker: PhantomData }
  59     }
  60 }
  61
  62 impl<T> Deref for Unique<T> {
  63     type Target = *mut T;
  64     fn deref(&self) -> &*mut T {
  65         // There's no way to cast the *const to a *mut
  66         // while also taking a reference. So we just
  67         // transmute it since it's all "just pointers".
  68         unsafe { mem::transmute(&self.ptr) }
  69     }
  70 }
  71 # fn main() {}
  72 ```
  73
  74 Unfortunately the mechanism for stating that your value is non-zero is
  75 unstable and unlikely to be stabilized soon. As such we're just going to
  76 take the hit and use std's Unique:
  77
  78
  79 ```rust
  80 #![feature(unique)]
  81
  82 use std::ptr::{Unique, self};
  83
  84 pub struct Vec<T> {
  85     ptr: Unique<T>,
  86     cap: usize,
  87     len: usize,
  88 }
  89
  90 # fn main() {}
  91 ```
  92
  93 If you don't care about the null-pointer optimization, then you can use the
  94 stable code. However we will be designing the rest of the code around enabling
  95 the optimization. In particular, `Unique::new` is unsafe to call, because
  96 putting `null` inside of it is Undefined Behaviour. Our stable Unique doesn't
  97 need `new` to be unsafe because it doesn't make any interesting guarantees about
  98 its contents.
  99
 100 [ownership]: ownership.html