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