compiler/rustc_arena/src/lib.rs

   1 //! The arena, a fast but limited type of allocator.
   2 //!
   3 //! Arenas are a type of allocator that destroy the objects within, all at
   4 //! once, once the arena itself is destroyed. They do not support deallocation
   5 //! of individual objects while the arena itself is still alive. The benefit
   6 //! of an arena is very fast allocation; just a pointer bump.
   7 //!
   8 //! This crate implements several kinds of arena.
   9
  10 #![doc(
  11     html_root_url = "https://doc.rust-lang.org/nightly/nightly-rustc/",
  12     test(no_crate_inject, attr(deny(warnings)))
  13 )]
  14 #![feature(dropck_eyepatch)]
  15 #![feature(new_uninit)]
  16 #![feature(maybe_uninit_slice)]
  17 #![cfg_attr(bootstrap, feature(min_const_generics))]
  18 #![feature(min_specialization)]
  19 #![cfg_attr(test, feature(test))]
  20
  21 use smallvec::SmallVec;
  22
  23 use std::alloc::Layout;
  24 use std::cell::{Cell, RefCell};
  25 use std::cmp;
  26 use std::marker::{PhantomData, Send};
  27 use std::mem::{self, MaybeUninit};
  28 use std::ptr;
  29 use std::slice;
  30
  31 #[inline(never)]
  32 #[cold]
  33 fn cold_path<F: FnOnce() -> R, R>(f: F) -> R {
  34     f()
  35 }
  36
  37 /// An arena that can hold objects of only one type.
  38 pub struct TypedArena<T> {
  39     /// A pointer to the next object to be allocated.
  40     ptr: Cell<*mut T>,
  41
  42     /// A pointer to the end of the allocated area. When this pointer is
  43     /// reached, a new chunk is allocated.
  44     end: Cell<*mut T>,
  45
  46     /// A vector of arena chunks.
  47     chunks: RefCell<Vec<TypedArenaChunk<T>>>,
  48
  49     /// Marker indicating that dropping the arena causes its owned
  50     /// instances of `T` to be dropped.
  51     _own: PhantomData<T>,
  52 }
  53
  54 struct TypedArenaChunk<T> {
  55     /// The raw storage for the arena chunk.
  56     storage: Box<[MaybeUninit<T>]>,
  57     /// The number of valid entries in the chunk.
  58     entries: usize,
  59 }
  60
  61 impl<T> TypedArenaChunk<T> {
  62     #[inline]
  63     unsafe fn new(capacity: usize) -> TypedArenaChunk<T> {
  64         TypedArenaChunk { storage: Box::new_uninit_slice(capacity), entries: 0 }
  65     }
  66
  67     /// Destroys this arena chunk.
  68     #[inline]
  69     unsafe fn destroy(&mut self, len: usize) {
  70         // The branch on needs_drop() is an -O1 performance optimization.
  71         // Without the branch, dropping TypedArena<u8> takes linear time.
  72         if mem::needs_drop::<T>() {
  73             ptr::drop_in_place(MaybeUninit::slice_assume_init_mut(&mut self.storage[..len]));
  74         }
  75     }
  76
  77     // Returns a pointer to the first allocated object.
  78     #[inline]
  79     fn start(&mut self) -> *mut T {
  80         MaybeUninit::slice_as_mut_ptr(&mut self.storage)
  81     }
  82
  83     // Returns a pointer to the end of the allocated space.
  84     #[inline]
  85     fn end(&mut self) -> *mut T {
  86         unsafe {
  87             if mem::size_of::<T>() == 0 {
  88                 // A pointer as large as possible for zero-sized elements.
  89                 !0 as *mut T
  90             } else {
  91                 self.start().add(self.storage.len())
  92             }
  93         }
  94     }
  95 }
  96
  97 // The arenas start with PAGE-sized chunks, and then each new chunk is twice as
  98 // big as its predecessor, up until we reach HUGE_PAGE-sized chunks, whereupon
  99 // we stop growing. This scales well, from arenas that are barely used up to
 100 // arenas that are used for 100s of MiBs. Note also that the chosen sizes match
 101 // the usual sizes of pages and huge pages on Linux.
 102 const PAGE: usize = 4096;
 103 const HUGE_PAGE: usize = 2 * 1024 * 1024;
 104
 105 impl<T> Default for TypedArena<T> {
 106     /// Creates a new `TypedArena`.
 107     fn default() -> TypedArena<T> {
 108         TypedArena {
 109             // We set both `ptr` and `end` to 0 so that the first call to
 110             // alloc() will trigger a grow().
 111             ptr: Cell::new(ptr::null_mut()),
 112             end: Cell::new(ptr::null_mut()),
 113             chunks: RefCell::new(vec![]),
 114             _own: PhantomData,
 115         }
 116     }
 117 }
 118
 119 trait IterExt<T> {
 120     fn alloc_from_iter(self, arena: &TypedArena<T>) -> &mut [T];
 121 }
 122
 123 impl<I, T> IterExt<T> for I
 124 where
 125     I: IntoIterator<Item = T>,
 126 {
 127     #[inline]
 128     default fn alloc_from_iter(self, arena: &TypedArena<T>) -> &mut [T] {
 129         let vec: SmallVec<[_; 8]> = self.into_iter().collect();
 130         vec.alloc_from_iter(arena)
 131     }
 132 }
 133
 134 impl<T, const N: usize> IterExt<T> for std::array::IntoIter<T, N> {
 135     #[inline]
 136     fn alloc_from_iter(self, arena: &TypedArena<T>) -> &mut [T] {
 137         let len = self.len();
 138         if len == 0 {
 139             return &mut [];
 140         }
 141         // Move the content to the arena by copying and then forgetting it
 142         unsafe {
 143             let start_ptr = arena.alloc_raw_slice(len);
 144             self.as_slice().as_ptr().copy_to_nonoverlapping(start_ptr, len);
 145             mem::forget(self);
 146             slice::from_raw_parts_mut(start_ptr, len)
 147         }
 148     }
 149 }
 150
 151 impl<T> IterExt<T> for Vec<T> {
 152     #[inline]
 153     fn alloc_from_iter(mut self, arena: &TypedArena<T>) -> &mut [T] {
 154         let len = self.len();
 155         if len == 0 {
 156             return &mut [];
 157         }
 158         // Move the content to the arena by copying and then forgetting it
 159         unsafe {
 160             let start_ptr = arena.alloc_raw_slice(len);
 161             self.as_ptr().copy_to_nonoverlapping(start_ptr, len);
 162             self.set_len(0);
 163             slice::from_raw_parts_mut(start_ptr, len)
 164         }
 165     }
 166 }
 167
 168 impl<A: smallvec::Array> IterExt<A::Item> for SmallVec<A> {
 169     #[inline]
 170     fn alloc_from_iter(mut self, arena: &TypedArena<A::Item>) -> &mut [A::Item] {
 171         let len = self.len();
 172         if len == 0 {
 173             return &mut [];
 174         }
 175         // Move the content to the arena by copying and then forgetting it
 176         unsafe {
 177             let start_ptr = arena.alloc_raw_slice(len);
 178             self.as_ptr().copy_to_nonoverlapping(start_ptr, len);
 179             self.set_len(0);
 180             slice::from_raw_parts_mut(start_ptr, len)
 181         }
 182     }
 183 }
 184
 185 impl<T> TypedArena<T> {
 186     /// Allocates an object in the `TypedArena`, returning a reference to it.
 187     #[inline]
 188     pub fn alloc(&self, object: T) -> &mut T {
 189         if self.ptr == self.end {
 190             self.grow(1)
 191         }
 192
 193         unsafe {
 194             if mem::size_of::<T>() == 0 {
 195                 self.ptr.set((self.ptr.get() as *mut u8).wrapping_offset(1) as *mut T);
 196                 let ptr = mem::align_of::<T>() as *mut T;
 197                 // Don't drop the object. This `write` is equivalent to `forget`.
 198                 ptr::write(ptr, object);
 199                 &mut *ptr
 200             } else {
 201                 let ptr = self.ptr.get();
 202                 // Advance the pointer.
 203                 self.ptr.set(self.ptr.get().offset(1));
 204                 // Write into uninitialized memory.
 205                 ptr::write(ptr, object);
 206                 &mut *ptr
 207             }
 208         }
 209     }
 210
 211     #[inline]
 212     fn can_allocate(&self, additional: usize) -> bool {
 213         let available_bytes = self.end.get() as usize - self.ptr.get() as usize;
 214         let additional_bytes = additional.checked_mul(mem::size_of::<T>()).unwrap();
 215         available_bytes >= additional_bytes
 216     }
 217
 218     /// Ensures there's enough space in the current chunk to fit `len` objects.
 219     #[inline]
 220     fn ensure_capacity(&self, additional: usize) {
 221         if !self.can_allocate(additional) {
 222             self.grow(additional);
 223             debug_assert!(self.can_allocate(additional));
 224         }
 225     }
 226
 227     #[inline]
 228     unsafe fn alloc_raw_slice(&self, len: usize) -> *mut T {
 229         assert!(mem::size_of::<T>() != 0);
 230         assert!(len != 0);
 231
 232         self.ensure_capacity(len);
 233
 234         let start_ptr = self.ptr.get();
 235         self.ptr.set(start_ptr.add(len));
 236         start_ptr
 237     }
 238
 239     /// Allocates a slice of objects that are copied into the `TypedArena`, returning a mutable
 240     /// reference to it. Will panic if passed a zero-sized types.
 241     ///
 242     /// Panics:
 243     ///
 244     ///  - Zero-sized types
 245     ///  - Zero-length slices
 246     #[inline]
 247     pub fn alloc_slice(&self, slice: &[T]) -> &mut [T]
 248     where
 249         T: Copy,
 250     {
 251         unsafe {
 252             let len = slice.len();
 253             let start_ptr = self.alloc_raw_slice(len);
 254             slice.as_ptr().copy_to_nonoverlapping(start_ptr, len);
 255             slice::from_raw_parts_mut(start_ptr, len)
 256         }
 257     }
 258
 259     #[inline]
 260     pub fn alloc_from_iter<I: IntoIterator<Item = T>>(&self, iter: I) -> &mut [T] {
 261         assert!(mem::size_of::<T>() != 0);
 262         iter.alloc_from_iter(self)
 263     }
 264
 265     /// Grows the arena.
 266     #[inline(never)]
 267     #[cold]
 268     fn grow(&self, additional: usize) {
 269         unsafe {
 270             // We need the element size to convert chunk sizes (ranging from
 271             // PAGE to HUGE_PAGE bytes) to element counts.
 272             let elem_size = cmp::max(1, mem::size_of::<T>());
 273             let mut chunks = self.chunks.borrow_mut();
 274             let mut new_cap;
 275             if let Some(last_chunk) = chunks.last_mut() {
 276                 // If a type is `!needs_drop`, we don't need to keep track of how many elements
 277                 // the chunk stores - the field will be ignored anyway.
 278                 if mem::needs_drop::<T>() {
 279                     let used_bytes = self.ptr.get() as usize - last_chunk.start() as usize;
 280                     last_chunk.entries = used_bytes / mem::size_of::<T>();
 281                 }
 282
 283                 // If the previous chunk's len is less than HUGE_PAGE
 284                 // bytes, then this chunk will be least double the previous
 285                 // chunk's size.
 286                 new_cap = last_chunk.storage.len().min(HUGE_PAGE / elem_size / 2);
 287                 new_cap *= 2;
 288             } else {
 289                 new_cap = PAGE / elem_size;
 290             }
 291             // Also ensure that this chunk can fit `additional`.
 292             new_cap = cmp::max(additional, new_cap);
 293
 294             let mut chunk = TypedArenaChunk::<T>::new(new_cap);
 295             self.ptr.set(chunk.start());
 296             self.end.set(chunk.end());
 297             chunks.push(chunk);
 298         }
 299     }
 300
 301     /// Clears the arena. Deallocates all but the longest chunk which may be reused.
 302     pub fn clear(&mut self) {
 303         unsafe {
 304             // Clear the last chunk, which is partially filled.
 305             let mut chunks_borrow = self.chunks.borrow_mut();
 306             if let Some(mut last_chunk) = chunks_borrow.last_mut() {
 307                 self.clear_last_chunk(&mut last_chunk);
 308                 let len = chunks_borrow.len();
 309                 // If `T` is ZST, code below has no effect.
 310                 for mut chunk in chunks_borrow.drain(..len - 1) {
 311                     chunk.destroy(chunk.entries);
 312                 }
 313             }
 314         }
 315     }
 316
 317     // Drops the contents of the last chunk. The last chunk is partially empty, unlike all other
 318     // chunks.
 319     fn clear_last_chunk(&self, last_chunk: &mut TypedArenaChunk<T>) {
 320         // Determine how much was filled.
 321         let start = last_chunk.start() as usize;
 322         // We obtain the value of the pointer to the first uninitialized element.
 323         let end = self.ptr.get() as usize;
 324         // We then calculate the number of elements to be dropped in the last chunk,
 325         // which is the filled area's length.
 326         let diff = if mem::size_of::<T>() == 0 {
 327             // `T` is ZST. It can't have a drop flag, so the value here doesn't matter. We get
 328             // the number of zero-sized values in the last and only chunk, just out of caution.
 329             // Recall that `end` was incremented for each allocated value.
 330             end - start
 331         } else {
 332             (end - start) / mem::size_of::<T>()
 333         };
 334         // Pass that to the `destroy` method.
 335         unsafe {
 336             last_chunk.destroy(diff);
 337         }
 338         // Reset the chunk.
 339         self.ptr.set(last_chunk.start());
 340     }
 341 }
 342
 343 unsafe impl<#[may_dangle] T> Drop for TypedArena<T> {
 344     fn drop(&mut self) {
 345         unsafe {
 346             // Determine how much was filled.
 347             let mut chunks_borrow = self.chunks.borrow_mut();
 348             if let Some(mut last_chunk) = chunks_borrow.pop() {
 349                 // Drop the contents of the last chunk.
 350                 self.clear_last_chunk(&mut last_chunk);
 351                 // The last chunk will be dropped. Destroy all other chunks.
 352                 for chunk in chunks_borrow.iter_mut() {
 353                     chunk.destroy(chunk.entries);
 354                 }
 355             }
 356             // Box handles deallocation of `last_chunk` and `self.chunks`.
 357         }
 358     }
 359 }
 360
 361 unsafe impl<T: Send> Send for TypedArena<T> {}
 362
 363 pub struct DroplessArena {
 364     /// A pointer to the start of the free space.
 365     start: Cell<*mut u8>,
 366
 367     /// A pointer to the end of free space.
 368     ///
 369     /// The allocation proceeds from the end of the chunk towards the start.
 370     /// When this pointer crosses the start pointer, a new chunk is allocated.
 371     end: Cell<*mut u8>,
 372
 373     /// A vector of arena chunks.
 374     chunks: RefCell<Vec<TypedArenaChunk<u8>>>,
 375 }
 376
 377 unsafe impl Send for DroplessArena {}
 378
 379 impl Default for DroplessArena {
 380     #[inline]
 381     fn default() -> DroplessArena {
 382         DroplessArena {
 383             start: Cell::new(ptr::null_mut()),
 384             end: Cell::new(ptr::null_mut()),
 385             chunks: Default::default(),
 386         }
 387     }
 388 }
 389
 390 impl DroplessArena {
 391     #[inline(never)]
 392     #[cold]
 393     fn grow(&self, additional: usize) {
 394         unsafe {
 395             let mut chunks = self.chunks.borrow_mut();
 396             let mut new_cap;
 397             if let Some(last_chunk) = chunks.last_mut() {
 398                 // There is no need to update `last_chunk.entries` because that
 399                 // field isn't used by `DroplessArena`.
 400
 401                 // If the previous chunk's len is less than HUGE_PAGE
 402                 // bytes, then this chunk will be least double the previous
 403                 // chunk's size.
 404                 new_cap = last_chunk.storage.len().min(HUGE_PAGE / 2);
 405                 new_cap *= 2;
 406             } else {
 407                 new_cap = PAGE;
 408             }
 409             // Also ensure that this chunk can fit `additional`.
 410             new_cap = cmp::max(additional, new_cap);
 411
 412             let mut chunk = TypedArenaChunk::<u8>::new(new_cap);
 413             self.start.set(chunk.start());
 414             self.end.set(chunk.end());
 415             chunks.push(chunk);
 416         }
 417     }
 418
 419     /// Allocates a byte slice with specified layout from the current memory
 420     /// chunk. Returns `None` if there is no free space left to satisfy the
 421     /// request.
 422     #[inline]
 423     fn alloc_raw_without_grow(&self, layout: Layout) -> Option<*mut u8> {
 424         let start = self.start.get() as usize;
 425         let end = self.end.get() as usize;
 426
 427         let align = layout.align();
 428         let bytes = layout.size();
 429
 430         let new_end = end.checked_sub(bytes)? & !(align - 1);
 431         if start <= new_end {
 432             let new_end = new_end as *mut u8;
 433             self.end.set(new_end);
 434             Some(new_end)
 435         } else {
 436             None
 437         }
 438     }
 439
 440     #[inline]
 441     pub fn alloc_raw(&self, layout: Layout) -> *mut u8 {
 442         assert!(layout.size() != 0);
 443         loop {
 444             if let Some(a) = self.alloc_raw_without_grow(layout) {
 445                 break a;
 446             }
 447             // No free space left. Allocate a new chunk to satisfy the request.
 448             // On failure the grow will panic or abort.
 449             self.grow(layout.size());
 450         }
 451     }
 452
 453     #[inline]
 454     pub fn alloc<T>(&self, object: T) -> &mut T {
 455         assert!(!mem::needs_drop::<T>());
 456
 457         let mem = self.alloc_raw(Layout::for_value::<T>(&object)) as *mut T;
 458
 459         unsafe {
 460             // Write into uninitialized memory.
 461             ptr::write(mem, object);
 462             &mut *mem
 463         }
 464     }
 465
 466     /// Allocates a slice of objects that are copied into the `DroplessArena`, returning a mutable
 467     /// reference to it. Will panic if passed a zero-sized type.
 468     ///
 469     /// Panics:
 470     ///
 471     ///  - Zero-sized types
 472     ///  - Zero-length slices
 473     #[inline]
 474     pub fn alloc_slice<T>(&self, slice: &[T]) -> &mut [T]
 475     where
 476         T: Copy,
 477     {
 478         assert!(!mem::needs_drop::<T>());
 479         assert!(mem::size_of::<T>() != 0);
 480         assert!(!slice.is_empty());
 481
 482         let mem = self.alloc_raw(Layout::for_value::<[T]>(slice)) as *mut T;
 483
 484         unsafe {
 485             mem.copy_from_nonoverlapping(slice.as_ptr(), slice.len());
 486             slice::from_raw_parts_mut(mem, slice.len())
 487         }
 488     }
 489
 490     #[inline]
 491     unsafe fn write_from_iter<T, I: Iterator<Item = T>>(
 492         &self,
 493         mut iter: I,
 494         len: usize,
 495         mem: *mut T,
 496     ) -> &mut [T] {
 497         let mut i = 0;
 498         // Use a manual loop since LLVM manages to optimize it better for
 499         // slice iterators
 500         loop {
 501             let value = iter.next();
 502             if i >= len || value.is_none() {
 503                 // We only return as many items as the iterator gave us, even
 504                 // though it was supposed to give us `len`
 505                 return slice::from_raw_parts_mut(mem, i);
 506             }
 507             ptr::write(mem.add(i), value.unwrap());
 508             i += 1;
 509         }
 510     }
 511
 512     #[inline]
 513     pub fn alloc_from_iter<T, I: IntoIterator<Item = T>>(&self, iter: I) -> &mut [T] {
 514         let iter = iter.into_iter();
 515         assert!(mem::size_of::<T>() != 0);
 516         assert!(!mem::needs_drop::<T>());
 517
 518         let size_hint = iter.size_hint();
 519
 520         match size_hint {
 521             (min, Some(max)) if min == max => {
 522                 // We know the exact number of elements the iterator will produce here
 523                 let len = min;
 524
 525                 if len == 0 {
 526                     return &mut [];
 527                 }
 528
 529                 let mem = self.alloc_raw(Layout::array::<T>(len).unwrap()) as *mut T;
 530                 unsafe { self.write_from_iter(iter, len, mem) }
 531             }
 532             (_, _) => {
 533                 cold_path(move || -> &mut [T] {
 534                     let mut vec: SmallVec<[_; 8]> = iter.collect();
 535                     if vec.is_empty() {
 536                         return &mut [];
 537                     }
 538                     // Move the content to the arena by copying it and then forgetting
 539                     // the content of the SmallVec
 540                     unsafe {
 541                         let len = vec.len();
 542                         let start_ptr =
 543                             self.alloc_raw(Layout::for_value::<[T]>(vec.as_slice())) as *mut T;
 544                         vec.as_ptr().copy_to_nonoverlapping(start_ptr, len);
 545                         vec.set_len(0);
 546                         slice::from_raw_parts_mut(start_ptr, len)
 547                     }
 548                 })
 549             }
 550         }
 551     }
 552 }
 553
 554 /// Calls the destructor for an object when dropped.
 555 struct DropType {
 556     drop_fn: unsafe fn(*mut u8),
 557     obj: *mut u8,
 558 }
 559
 560 unsafe fn drop_for_type<T>(to_drop: *mut u8) {
 561     std::ptr::drop_in_place(to_drop as *mut T)
 562 }
 563
 564 impl Drop for DropType {
 565     fn drop(&mut self) {
 566         unsafe { (self.drop_fn)(self.obj) }
 567     }
 568 }
 569
 570 /// An arena which can be used to allocate any type.
 571 ///
 572 /// # Safety
 573 ///
 574 /// Allocating in this arena is unsafe since the type system
 575 /// doesn't know which types it contains. In order to
 576 /// allocate safely, you must store a `PhantomData<T>`
 577 /// alongside this arena for each type `T` you allocate.
 578 #[derive(Default)]
 579 pub struct DropArena {
 580     /// A list of destructors to run when the arena drops.
 581     /// Ordered so `destructors` gets dropped before the arena
 582     /// since its destructor can reference memory in the arena.
 583     destructors: RefCell<Vec<DropType>>,
 584     arena: DroplessArena,
 585 }
 586
 587 impl DropArena {
 588     #[inline]
 589     pub unsafe fn alloc<T>(&self, object: T) -> &mut T {
 590         let mem = self.arena.alloc_raw(Layout::new::<T>()) as *mut T;
 591         // Write into uninitialized memory.
 592         ptr::write(mem, object);
 593         let result = &mut *mem;
 594         // Record the destructor after doing the allocation as that may panic
 595         // and would cause `object`'s destructor to run twice if it was recorded before.
 596         self.destructors
 597             .borrow_mut()
 598             .push(DropType { drop_fn: drop_for_type::<T>, obj: result as *mut T as *mut u8 });
 599         result
 600     }
 601
 602     #[inline]
 603     pub unsafe fn alloc_from_iter<T, I: IntoIterator<Item = T>>(&self, iter: I) -> &mut [T] {
 604         let mut vec: SmallVec<[_; 8]> = iter.into_iter().collect();
 605         if vec.is_empty() {
 606             return &mut [];
 607         }
 608         let len = vec.len();
 609
 610         let start_ptr = self.arena.alloc_raw(Layout::array::<T>(len).unwrap()) as *mut T;
 611
 612         let mut destructors = self.destructors.borrow_mut();
 613         // Reserve space for the destructors so we can't panic while adding them.
 614         destructors.reserve(len);
 615
 616         // Move the content to the arena by copying it and then forgetting
 617         // the content of the SmallVec.
 618         vec.as_ptr().copy_to_nonoverlapping(start_ptr, len);
 619         mem::forget(vec.drain(..));
 620
 621         // Record the destructors after doing the allocation as that may panic
 622         // and would cause `object`'s destructor to run twice if it was recorded before.
 623         for i in 0..len {
 624             destructors
 625                 .push(DropType { drop_fn: drop_for_type::<T>, obj: start_ptr.add(i) as *mut u8 });
 626         }
 627
 628         slice::from_raw_parts_mut(start_ptr, len)
 629     }
 630 }
 631
 632 #[macro_export]
 633 macro_rules! arena_for_type {
 634     ([][$ty:ty]) => {
 635         $crate::TypedArena<$ty>
 636     };
 637     ([few $(, $attrs:ident)*][$ty:ty]) => {
 638         ::std::marker::PhantomData<$ty>
 639     };
 640     ([$ignore:ident $(, $attrs:ident)*]$args:tt) => {
 641         $crate::arena_for_type!([$($attrs),*]$args)
 642     };
 643 }
 644
 645 #[macro_export]
 646 macro_rules! which_arena_for_type {
 647     ([][$arena:expr]) => {
 648         ::std::option::Option::Some($arena)
 649     };
 650     ([few$(, $attrs:ident)*][$arena:expr]) => {
 651         ::std::option::Option::None
 652     };
 653     ([$ignore:ident$(, $attrs:ident)*]$args:tt) => {
 654         $crate::which_arena_for_type!([$($attrs),*]$args)
 655     };
 656 }
 657
 658 #[macro_export]
 659 macro_rules! declare_arena {
 660     ([], [$($a:tt $name:ident: $ty:ty,)*], $tcx:lifetime) => {
 661         #[derive(Default)]
 662         pub struct Arena<$tcx> {
 663             pub dropless: $crate::DroplessArena,
 664             drop: $crate::DropArena,
 665             $($name: $crate::arena_for_type!($a[$ty]),)*
 666         }
 667
 668         pub trait ArenaAllocatable<'tcx, T = Self>: Sized {
 669             fn allocate_on<'a>(self, arena: &'a Arena<'tcx>) -> &'a mut Self;
 670             fn allocate_from_iter<'a>(
 671                 arena: &'a Arena<'tcx>,
 672                 iter: impl ::std::iter::IntoIterator<Item = Self>,
 673             ) -> &'a mut [Self];
 674         }
 675
 676         impl<'tcx, T: Copy> ArenaAllocatable<'tcx, ()> for T {
 677             #[inline]
 678             fn allocate_on<'a>(self, arena: &'a Arena<'tcx>) -> &'a mut Self {
 679                 arena.dropless.alloc(self)
 680             }
 681             #[inline]
 682             fn allocate_from_iter<'a>(
 683                 arena: &'a Arena<'tcx>,
 684                 iter: impl ::std::iter::IntoIterator<Item = Self>,
 685             ) -> &'a mut [Self] {
 686                 arena.dropless.alloc_from_iter(iter)
 687             }
 688
 689         }
 690         $(
 691             impl<$tcx> ArenaAllocatable<$tcx, $ty> for $ty {
 692                 #[inline]
 693                 fn allocate_on<'a>(self, arena: &'a Arena<$tcx>) -> &'a mut Self {
 694                     if !::std::mem::needs_drop::<Self>() {
 695                         return arena.dropless.alloc(self);
 696                     }
 697                     match $crate::which_arena_for_type!($a[&arena.$name]) {
 698                         ::std::option::Option::<&$crate::TypedArena<Self>>::Some(ty_arena) => {
 699                             ty_arena.alloc(self)
 700                         }
 701                         ::std::option::Option::None => unsafe { arena.drop.alloc(self) },
 702                     }
 703                 }
 704
 705                 #[inline]
 706                 fn allocate_from_iter<'a>(
 707                     arena: &'a Arena<$tcx>,
 708                     iter: impl ::std::iter::IntoIterator<Item = Self>,
 709                 ) -> &'a mut [Self] {
 710                     if !::std::mem::needs_drop::<Self>() {
 711                         return arena.dropless.alloc_from_iter(iter);
 712                     }
 713                     match $crate::which_arena_for_type!($a[&arena.$name]) {
 714                         ::std::option::Option::<&$crate::TypedArena<Self>>::Some(ty_arena) => {
 715                             ty_arena.alloc_from_iter(iter)
 716                         }
 717                         ::std::option::Option::None => unsafe { arena.drop.alloc_from_iter(iter) },
 718                     }
 719                 }
 720             }
 721         )*
 722
 723         impl<'tcx> Arena<'tcx> {
 724             #[inline]
 725             pub fn alloc<T: ArenaAllocatable<'tcx, U>, U>(&self, value: T) -> &mut T {
 726                 value.allocate_on(self)
 727             }
 728
 729             #[inline]
 730             pub fn alloc_slice<T: ::std::marker::Copy>(&self, value: &[T]) -> &mut [T] {
 731                 if value.is_empty() {
 732                     return &mut [];
 733                 }
 734                 self.dropless.alloc_slice(value)
 735             }
 736
 737             pub fn alloc_from_iter<'a, T: ArenaAllocatable<'tcx, U>, U>(
 738                 &'a self,
 739                 iter: impl ::std::iter::IntoIterator<Item = T>,
 740             ) -> &'a mut [T] {
 741                 T::allocate_from_iter(self, iter)
 742             }
 743         }
 744     }
 745 }
 746
 747 #[cfg(test)]
 748 mod tests;