src/librustc/arena.rs

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