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