src/doc/tarpl/vec-zsts.md

   1 % Handling Zero-Sized Types
   2
   3 It's time. We're going to fight the spectre that is zero-sized types. Safe Rust
   4 *never* needs to care about this, but Vec is very intensive on raw pointers and
   5 raw allocations, which are exactly the *only* two things that care about
   6 zero-sized types. We need to be careful of two things:
   7
   8 * The raw allocator API has undefined behaviour if you pass in 0 for an
   9   allocation size.
  10 * raw pointer offsets are no-ops for zero-sized types, which will break our
  11   C-style pointer iterator.
  12
  13 Thankfully we abstracted out pointer-iterators and allocating handling into
  14 RawValIter and RawVec respectively. How mysteriously convenient.
  15
  16
  17
  18
  19 ## Allocating Zero-Sized Types
  20
  21 So if the allocator API doesn't support zero-sized allocations, what on earth
  22 do we store as our allocation? Why, `heap::EMPTY` of course! Almost every operation
  23 with a ZST is a no-op since ZSTs have exactly one value, and therefore no state needs
  24 to be considered to store or load them. This actually extends to `ptr::read` and
  25 `ptr::write`: they won't actually look at the pointer at all. As such we *never* need
  26 to change the pointer.
  27
  28 Note however that our previous reliance on running out of memory before overflow is
  29 no longer valid with zero-sized types. We must explicitly guard against capacity
  30 overflow for zero-sized types.
  31
  32 Due to our current architecture, all this means is writing 3 guards, one in each
  33 method of RawVec.
  34
  35 ```rust,ignore
  36 impl<T> RawVec<T> {
  37     fn new() -> Self {
  38         unsafe {
  39             // !0 is usize::MAX. This branch should be stripped at compile time.
  40             let cap = if mem::size_of::<T>() == 0 { !0 } else { 0 };
  41
  42             // heap::EMPTY doubles as "unallocated" and "zero-sized allocation"
  43             RawVec { ptr: Unique::new(heap::EMPTY as *mut T), cap: cap }
  44         }
  45     }
  46
  47     fn grow(&mut self) {
  48         unsafe {
  49             let elem_size = mem::size_of::<T>();
  50
  51             // since we set the capacity to usize::MAX when elem_size is
  52             // 0, getting to here necessarily means the Vec is overfull.
  53             assert!(elem_size != 0, "capacity overflow");
  54
  55             let align = mem::align_of::<T>();
  56
  57             let (new_cap, ptr) = if self.cap == 0 {
  58                 let ptr = heap::allocate(elem_size, align);
  59                 (1, ptr)
  60             } else {
  61                 let new_cap = 2 * self.cap;
  62                 let ptr = heap::reallocate(*self.ptr as *mut _,
  63                                             self.cap * elem_size,
  64                                             new_cap * elem_size,
  65                                             align);
  66                 (new_cap, ptr)
  67             };
  68
  69             // If allocate or reallocate fail, we'll get `null` back
  70             if ptr.is_null() { oom() }
  71
  72             self.ptr = Unique::new(ptr as *mut _);
  73             self.cap = new_cap;
  74         }
  75     }
  76 }
  77
  78 impl<T> Drop for RawVec<T> {
  79     fn drop(&mut self) {
  80         let elem_size = mem::size_of::<T>();
  81
  82         // don't free zero-sized allocations, as they were never allocated.
  83         if self.cap != 0 && elem_size != 0 {
  84             let align = mem::align_of::<T>();
  85
  86             let num_bytes = elem_size * self.cap;
  87             unsafe {
  88                 heap::deallocate(*self.ptr as *mut _, num_bytes, align);
  89             }
  90         }
  91     }
  92 }
  93 ```
  94
  95 That's it. We support pushing and popping zero-sized types now. Our iterators
  96 (that aren't provided by slice Deref) are still busted, though.
  97
  98
  99
 100
 101 ## Iterating Zero-Sized Types
 102
 103 Zero-sized offsets are no-ops. This means that our current design will always
 104 initialize `start` and `end` as the same value, and our iterators will yield
 105 nothing. The current solution to this is to cast the pointers to integers,
 106 increment, and then cast them back:
 107
 108 ```rust,ignore
 109 impl<T> RawValIter<T> {
 110     unsafe fn new(slice: &[T]) -> Self {
 111         RawValIter {
 112             start: slice.as_ptr(),
 113             end: if mem::size_of::<T>() == 0 {
 114                 ((slice.as_ptr() as usize) + slice.len()) as *const _
 115             } else if slice.len() == 0 {
 116                 slice.as_ptr()
 117             } else {
 118                 slice.as_ptr().offset(slice.len() as isize)
 119             }
 120         }
 121     }
 122 }
 123 ```
 124
 125 Now we have a different bug. Instead of our iterators not running at all, our
 126 iterators now run *forever*. We need to do the same trick in our iterator impls.
 127 Also, our size_hint computation code will divide by 0 for ZSTs. Since we'll
 128 basically be treating the two pointers as if they point to bytes, we'll just
 129 map size 0 to divide by 1.
 130
 131 ```rust,ignore
 132 impl<T> Iterator for RawValIter<T> {
 133     type Item = T;
 134     fn next(&mut self) -> Option<T> {
 135         if self.start == self.end {
 136             None
 137         } else {
 138             unsafe {
 139                 let result = ptr::read(self.start);
 140                 self.start = if mem::size_of::<T>() == 0 {
 141                     (self.start as usize + 1) as *const _
 142                 } else {
 143                     self.start.offset(1);
 144                 }
 145                 Some(result)
 146             }
 147         }
 148     }
 149
 150     fn size_hint(&self) -> (usize, Option<usize>) {
 151         let elem_size = mem::size_of::<T>();
 152         let len = (self.end as usize - self.start as usize)
 153                   / if elem_size == 0 { 1 } else { elem_size };
 154         (len, Some(len))
 155     }
 156 }
 157
 158 impl<T> DoubleEndedIterator for RawValIter<T> {
 159     fn next_back(&mut self) -> Option<T> {
 160         if self.start == self.end {
 161             None
 162         } else {
 163             unsafe {
 164                 self.end = if mem::size_of::<T>() == 0 {
 165                     (self.end as usize - 1) as *const _
 166                 } else {
 167                     self.end.offset(-1);
 168                 }
 169                 Some(ptr::read(self.end))
 170             }
 171         }
 172     }
 173 }
 174 ```
 175
 176 And that's it. Iteration works!