src/librustc/arena.rs

   1 use arena::{TypedArena, DroplessArena};
   2 use std::mem;
   3 use std::ptr;
   4 use std::slice;
   5 use std::cell::RefCell;
   6 use std::marker::PhantomData;
   7 use smallvec::SmallVec;
   8
   9 #[macro_export]
  10 macro_rules! arena_types {
  11     ($macro:path, $args:tt, $tcx:lifetime) => (
  12         $macro!($args, [
  13             [] vtable_method: Option<(
  14                 rustc::hir::def_id::DefId,
  15                 rustc::ty::subst::SubstsRef<$tcx>
  16             )>,
  17             [few] mir_keys: rustc::util::nodemap::DefIdSet,
  18             [decode] specialization_graph: rustc::traits::specialization_graph::Graph,
  19             [] region_scope_tree: rustc::middle::region::ScopeTree,
  20             [] item_local_set: rustc::util::nodemap::ItemLocalSet,
  21             [decode] mir_const_qualif: rustc_data_structures::bit_set::BitSet<rustc::mir::Local>,
  22             [] trait_impls_of: rustc::ty::trait_def::TraitImpls,
  23             [] dropck_outlives:
  24                 rustc::infer::canonical::Canonical<'tcx,
  25                     rustc::infer::canonical::QueryResponse<'tcx,
  26                         rustc::traits::query::dropck_outlives::DropckOutlivesResult<'tcx>
  27                     >
  28                 >,
  29             [] normalize_projection_ty:
  30                 rustc::infer::canonical::Canonical<'tcx,
  31                     rustc::infer::canonical::QueryResponse<'tcx,
  32                         rustc::traits::query::normalize::NormalizationResult<'tcx>
  33                     >
  34                 >,
  35             [] implied_outlives_bounds:
  36                 rustc::infer::canonical::Canonical<'tcx,
  37                     rustc::infer::canonical::QueryResponse<'tcx,
  38                         Vec<rustc::traits::query::outlives_bounds::OutlivesBound<'tcx>>
  39                     >
  40                 >,
  41             [] type_op_subtype:
  42                 rustc::infer::canonical::Canonical<'tcx,
  43                     rustc::infer::canonical::QueryResponse<'tcx, ()>
  44                 >,
  45             [] type_op_normalize_poly_fn_sig:
  46                 rustc::infer::canonical::Canonical<'tcx,
  47                     rustc::infer::canonical::QueryResponse<'tcx, rustc::ty::PolyFnSig<'tcx>>
  48                 >,
  49             [] type_op_normalize_fn_sig:
  50                 rustc::infer::canonical::Canonical<'tcx,
  51                     rustc::infer::canonical::QueryResponse<'tcx, rustc::ty::FnSig<'tcx>>
  52                 >,
  53             [] type_op_normalize_predicate:
  54                 rustc::infer::canonical::Canonical<'tcx,
  55                     rustc::infer::canonical::QueryResponse<'tcx, rustc::ty::Predicate<'tcx>>
  56                 >,
  57             [] type_op_normalize_ty:
  58                 rustc::infer::canonical::Canonical<'tcx,
  59                     rustc::infer::canonical::QueryResponse<'tcx, rustc::ty::Ty<'tcx>>
  60                 >,
  61             [few] crate_inherent_impls: rustc::ty::CrateInherentImpls,
  62             [decode] borrowck: rustc::middle::borrowck::BorrowCheckResult,
  63         ], $tcx);
  64     )
  65 }
  66
  67 macro_rules! arena_for_type {
  68     ([][$ty:ty]) => {
  69         TypedArena<$ty>
  70     };
  71     ([few $(, $attrs:ident)*][$ty:ty]) => {
  72         PhantomData<$ty>
  73     };
  74     ([$ignore:ident $(, $attrs:ident)*]$args:tt) => {
  75         arena_for_type!([$($attrs),*]$args)
  76     };
  77 }
  78
  79 macro_rules! declare_arena {
  80     ([], [$($a:tt $name:ident: $ty:ty,)*], $tcx:lifetime) => {
  81         #[derive(Default)]
  82         pub struct Arena<$tcx> {
  83             dropless: DroplessArena,
  84             drop: DropArena,
  85             $($name: arena_for_type!($a[$ty]),)*
  86         }
  87     }
  88 }
  89
  90 macro_rules! which_arena_for_type {
  91     ([][$arena:expr]) => {
  92         Some($arena)
  93     };
  94     ([few$(, $attrs:ident)*][$arena:expr]) => {
  95         None
  96     };
  97     ([$ignore:ident$(, $attrs:ident)*]$args:tt) => {
  98         which_arena_for_type!([$($attrs),*]$args)
  99     };
 100 }
 101
 102 macro_rules! impl_arena_allocatable {
 103     ([], [$($a:tt $name:ident: $ty:ty,)*], $tcx:lifetime) => {
 104         $(
 105             impl ArenaAllocatable for $ty {}
 106             unsafe impl<$tcx> ArenaField<$tcx> for $ty {
 107                 #[inline]
 108                 fn arena<'a>(_arena: &'a Arena<$tcx>) -> Option<&'a TypedArena<Self>> {
 109                     which_arena_for_type!($a[&_arena.$name])
 110                 }
 111             }
 112         )*
 113     }
 114 }
 115
 116 arena_types!(declare_arena, [], 'tcx);
 117
 118 arena_types!(impl_arena_allocatable, [], 'tcx);
 119
 120 pub trait ArenaAllocatable {}
 121
 122 impl<T: Copy> ArenaAllocatable for T {}
 123
 124 pub unsafe trait ArenaField<'tcx>: Sized {
 125     /// Returns a specific arena to allocate from.
 126     /// If None is returned, the DropArena will be used.
 127     fn arena<'a>(arena: &'a Arena<'tcx>) -> Option<&'a TypedArena<Self>>;
 128 }
 129
 130 unsafe impl<'tcx, T> ArenaField<'tcx> for T {
 131     #[inline]
 132     default fn arena<'a>(_: &'a Arena<'tcx>) -> Option<&'a TypedArena<Self>> {
 133         panic!()
 134     }
 135 }
 136
 137 impl<'tcx> Arena<'tcx> {
 138     #[inline]
 139     pub fn alloc<T: ArenaAllocatable>(&self, value: T) -> &mut T {
 140         if !mem::needs_drop::<T>() {
 141             return self.dropless.alloc(value);
 142         }
 143         match <T as ArenaField<'tcx>>::arena(self) {
 144             Some(arena) => arena.alloc(value),
 145             None => unsafe { self.drop.alloc(value) },
 146         }
 147     }
 148
 149     #[inline]
 150     pub fn alloc_slice<T: Copy>(&self, value: &[T]) -> &mut [T] {
 151         if value.len() == 0 {
 152             return &mut []
 153         }
 154         self.dropless.alloc_slice(value)
 155     }
 156
 157     pub fn alloc_from_iter<
 158         T: ArenaAllocatable,
 159         I: IntoIterator<Item = T>
 160     >(
 161         &'a self,
 162         iter: I
 163     ) -> &'a mut [T] {
 164         if !mem::needs_drop::<T>() {
 165             return self.dropless.alloc_from_iter(iter);
 166         }
 167         match <T as ArenaField<'tcx>>::arena(self) {
 168             Some(arena) => arena.alloc_from_iter(iter),
 169             None => unsafe { self.drop.alloc_from_iter(iter) },
 170         }
 171     }
 172 }
 173
 174 /// Calls the destructor for an object when dropped.
 175 struct DropType {
 176     drop_fn: unsafe fn(*mut u8),
 177     obj: *mut u8,
 178 }
 179
 180 unsafe fn drop_for_type<T>(to_drop: *mut u8) {
 181     std::ptr::drop_in_place(to_drop as *mut T)
 182 }
 183
 184 impl Drop for DropType {
 185     fn drop(&mut self) {
 186         unsafe {
 187             (self.drop_fn)(self.obj)
 188         }
 189     }
 190 }
 191
 192 /// An arena which can be used to allocate any type.
 193 /// Allocating in this arena is unsafe since the type system
 194 /// doesn't know which types it contains. In order to
 195 /// allocate safely, you must store a PhantomData<T>
 196 /// alongside this arena for each type T you allocate.
 197 #[derive(Default)]
 198 struct DropArena {
 199     /// A list of destructors to run when the arena drops.
 200     /// Ordered so `destructors` gets dropped before the arena
 201     /// since its destructor can reference memory in the arena.
 202     destructors: RefCell<Vec<DropType>>,
 203     arena: DroplessArena,
 204 }
 205
 206 impl DropArena {
 207     #[inline]
 208     unsafe fn alloc<T>(&self, object: T) -> &mut T {
 209         let mem = self.arena.alloc_raw(
 210             mem::size_of::<T>(),
 211             mem::align_of::<T>()
 212         ) as *mut _ as *mut T;
 213         // Write into uninitialized memory.
 214         ptr::write(mem, object);
 215         let result = &mut *mem;
 216         // Record the destructor after doing the allocation as that may panic
 217         // and would cause `object`'s destuctor to run twice if it was recorded before
 218         self.destructors.borrow_mut().push(DropType {
 219             drop_fn: drop_for_type::<T>,
 220             obj: result as *mut T as *mut u8,
 221         });
 222         result
 223     }
 224
 225     #[inline]
 226     unsafe fn alloc_from_iter<T, I: IntoIterator<Item = T>>(&self, iter: I) -> &mut [T] {
 227         let mut vec: SmallVec<[_; 8]> = iter.into_iter().collect();
 228         if vec.is_empty() {
 229             return &mut [];
 230         }
 231         let len = vec.len();
 232
 233         let start_ptr = self.arena.alloc_raw(
 234             len.checked_mul(mem::size_of::<T>()).unwrap(),
 235             mem::align_of::<T>()
 236         ) as *mut _ as *mut T;
 237
 238         let mut destructors = self.destructors.borrow_mut();
 239         // Reserve space for the destructors so we can't panic while adding them
 240         destructors.reserve(len);
 241
 242         // Move the content to the arena by copying it and then forgetting
 243         // the content of the SmallVec
 244         vec.as_ptr().copy_to_nonoverlapping(start_ptr, len);
 245         mem::forget(vec.drain());
 246
 247         // Record the destructors after doing the allocation as that may panic
 248         // and would cause `object`'s destuctor to run twice if it was recorded before
 249         for i in 0..len {
 250             destructors.push(DropType {
 251                 drop_fn: drop_for_type::<T>,
 252                 obj: start_ptr.offset(i as isize) as *mut u8,
 253             });
 254         }
 255
 256         slice::from_raw_parts_mut(start_ptr, len)
 257     }
 258 }