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