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 #![feature(min_specialization)]
  18 #![feature(decl_macro)]
  19 #![feature(rustc_attrs)]
  20 #![cfg_attr(test, feature(test))]
  21 #![feature(strict_provenance)]
  22 #![feature(ptr_const_cast)]
  23
  24 use smallvec::SmallVec;
  25
  26 use std::alloc::Layout;
  27 use std::cell::{Cell, RefCell};
  28 use std::cmp;
  29 use std::marker::{PhantomData, Send};
  30 use std::mem::{self, MaybeUninit};
  31 use std::ptr::{self, NonNull};
  32 use std::slice;
  33
  34 #[inline(never)]
  35 #[cold]
  36 fn cold_path<F: FnOnce() -> R, R>(f: F) -> R {
  37     f()
  38 }
  39
  40 /// An arena that can hold objects of only one type.
  41 pub struct TypedArena<T> {
  42     /// A pointer to the next object to be allocated.
  43     ptr: Cell<*mut T>,
  44
  45     /// A pointer to the end of the allocated area. When this pointer is
  46     /// reached, a new chunk is allocated.
  47     end: Cell<*mut T>,
  48
  49     /// A vector of arena chunks.
  50     chunks: RefCell<Vec<ArenaChunk<T>>>,
  51
  52     /// Marker indicating that dropping the arena causes its owned
  53     /// instances of `T` to be dropped.
  54     _own: PhantomData<T>,
  55 }
  56
  57 struct ArenaChunk<T = u8> {
  58     /// The raw storage for the arena chunk.
  59     storage: NonNull<[MaybeUninit<T>]>,
  60     /// The number of valid entries in the chunk.
  61     entries: usize,
  62 }
  63
  64 unsafe impl<#[may_dangle] T> Drop for ArenaChunk<T> {
  65     fn drop(&mut self) {
  66         unsafe { Box::from_raw(self.storage.as_mut()) };
  67     }
  68 }
  69
  70 impl<T> ArenaChunk<T> {
  71     #[inline]
  72     unsafe fn new(capacity: usize) -> ArenaChunk<T> {
  73         ArenaChunk {
  74             storage: NonNull::new(Box::into_raw(Box::new_uninit_slice(capacity))).unwrap(),
  75             entries: 0,
  76         }
  77     }
  78
  79     /// Destroys this arena chunk.
  80     #[inline]
  81     unsafe fn destroy(&mut self, len: usize) {
  82         // The branch on needs_drop() is an -O1 performance optimization.
  83         // Without the branch, dropping TypedArena<u8> takes linear time.
  84         if mem::needs_drop::<T>() {
  85             let slice = &mut *(self.storage.as_mut());
  86             ptr::drop_in_place(MaybeUninit::slice_assume_init_mut(&mut slice[..len]));
  87         }
  88     }
  89
  90     // Returns a pointer to the first allocated object.
  91     #[inline]
  92     fn start(&mut self) -> *mut T {
  93         self.storage.as_ptr() as *mut T
  94     }
  95
  96     // Returns a pointer to the end of the allocated space.
  97     #[inline]
  98     fn end(&mut self) -> *mut T {
  99         unsafe {
 100             if mem::size_of::<T>() == 0 {
 101                 // A pointer as large as possible for zero-sized elements.
 102                 ptr::invalid_mut(!0)
 103             } else {
 104                 self.start().add((*self.storage.as_ptr()).len())
 105             }
 106         }
 107     }
 108 }
 109
 110 // The arenas start with PAGE-sized chunks, and then each new chunk is twice as
 111 // big as its predecessor, up until we reach HUGE_PAGE-sized chunks, whereupon
 112 // we stop growing. This scales well, from arenas that are barely used up to
 113 // arenas that are used for 100s of MiBs. Note also that the chosen sizes match
 114 // the usual sizes of pages and huge pages on Linux.
 115 const PAGE: usize = 4096;
 116 const HUGE_PAGE: usize = 2 * 1024 * 1024;
 117
 118 impl<T> Default for TypedArena<T> {
 119     /// Creates a new `TypedArena`.
 120     fn default() -> TypedArena<T> {
 121         TypedArena {
 122             // We set both `ptr` and `end` to 0 so that the first call to
 123             // alloc() will trigger a grow().
 124             ptr: Cell::new(ptr::null_mut()),
 125             end: Cell::new(ptr::null_mut()),
 126             chunks: Default::default(),
 127             _own: PhantomData,
 128         }
 129     }
 130 }
 131
 132 trait IterExt<T> {
 133     fn alloc_from_iter(self, arena: &TypedArena<T>) -> &mut [T];
 134 }
 135
 136 impl<I, T> IterExt<T> for I
 137 where
 138     I: IntoIterator<Item = T>,
 139 {
 140     // This default collects into a `SmallVec` and then allocates by copying
 141     // from it. The specializations below for types like `Vec` are more
 142     // efficient, copying directly without the intermediate collecting step.
 143     // This default could be made more efficient, like
 144     // `DroplessArena::alloc_from_iter`, but it's not hot enough to bother.
 145     #[inline]
 146     default fn alloc_from_iter(self, arena: &TypedArena<T>) -> &mut [T] {
 147         let vec: SmallVec<[_; 8]> = self.into_iter().collect();
 148         vec.alloc_from_iter(arena)
 149     }
 150 }
 151
 152 impl<T, const N: usize> IterExt<T> for std::array::IntoIter<T, N> {
 153     #[inline]
 154     fn alloc_from_iter(self, arena: &TypedArena<T>) -> &mut [T] {
 155         let len = self.len();
 156         if len == 0 {
 157             return &mut [];
 158         }
 159         // Move the content to the arena by copying and then forgetting it.
 160         unsafe {
 161             let start_ptr = arena.alloc_raw_slice(len);
 162             self.as_slice().as_ptr().copy_to_nonoverlapping(start_ptr, len);
 163             mem::forget(self);
 164             slice::from_raw_parts_mut(start_ptr, len)
 165         }
 166     }
 167 }
 168
 169 impl<T> IterExt<T> for Vec<T> {
 170     #[inline]
 171     fn alloc_from_iter(mut self, arena: &TypedArena<T>) -> &mut [T] {
 172         let len = self.len();
 173         if len == 0 {
 174             return &mut [];
 175         }
 176         // Move the content to the arena by copying and then forgetting it.
 177         unsafe {
 178             let start_ptr = arena.alloc_raw_slice(len);
 179             self.as_ptr().copy_to_nonoverlapping(start_ptr, len);
 180             self.set_len(0);
 181             slice::from_raw_parts_mut(start_ptr, len)
 182         }
 183     }
 184 }
 185
 186 impl<A: smallvec::Array> IterExt<A::Item> for SmallVec<A> {
 187     #[inline]
 188     fn alloc_from_iter(mut self, arena: &TypedArena<A::Item>) -> &mut [A::Item] {
 189         let len = self.len();
 190         if len == 0 {
 191             return &mut [];
 192         }
 193         // Move the content to the arena by copying and then forgetting it.
 194         unsafe {
 195             let start_ptr = arena.alloc_raw_slice(len);
 196             self.as_ptr().copy_to_nonoverlapping(start_ptr, len);
 197             self.set_len(0);
 198             slice::from_raw_parts_mut(start_ptr, len)
 199         }
 200     }
 201 }
 202
 203 impl<T> TypedArena<T> {
 204     /// Allocates an object in the `TypedArena`, returning a reference to it.
 205     #[inline]
 206     pub fn alloc(&self, object: T) -> &mut T {
 207         if self.ptr == self.end {
 208             self.grow(1)
 209         }
 210
 211         unsafe {
 212             if mem::size_of::<T>() == 0 {
 213                 self.ptr.set((self.ptr.get() as *mut u8).wrapping_offset(1) as *mut T);
 214                 let ptr = ptr::NonNull::<T>::dangling().as_ptr();
 215                 // Don't drop the object. This `write` is equivalent to `forget`.
 216                 ptr::write(ptr, object);
 217                 &mut *ptr
 218             } else {
 219                 let ptr = self.ptr.get();
 220                 // Advance the pointer.
 221                 self.ptr.set(self.ptr.get().offset(1));
 222                 // Write into uninitialized memory.
 223                 ptr::write(ptr, object);
 224                 &mut *ptr
 225             }
 226         }
 227     }
 228
 229     #[inline]
 230     fn can_allocate(&self, additional: usize) -> bool {
 231         // FIXME: this should *likely* use `offset_from`, but more
 232         // investigation is needed (including running tests in miri).
 233         let available_bytes = self.end.get().addr() - self.ptr.get().addr();
 234         let additional_bytes = additional.checked_mul(mem::size_of::<T>()).unwrap();
 235         available_bytes >= additional_bytes
 236     }
 237
 238     /// Ensures there's enough space in the current chunk to fit `len` objects.
 239     #[inline]
 240     fn ensure_capacity(&self, additional: usize) {
 241         if !self.can_allocate(additional) {
 242             self.grow(additional);
 243             debug_assert!(self.can_allocate(additional));
 244         }
 245     }
 246
 247     #[inline]
 248     unsafe fn alloc_raw_slice(&self, len: usize) -> *mut T {
 249         assert!(mem::size_of::<T>() != 0);
 250         assert!(len != 0);
 251
 252         self.ensure_capacity(len);
 253
 254         let start_ptr = self.ptr.get();
 255         self.ptr.set(start_ptr.add(len));
 256         start_ptr
 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                     // FIXME: this should *likely* use `offset_from`, but more
 280                     // investigation is needed (including running tests in miri).
 281                     let used_bytes = self.ptr.get().addr() - last_chunk.start().addr();
 282                     last_chunk.entries = used_bytes / mem::size_of::<T>();
 283                 }
 284
 285                 // If the previous chunk's len is less than HUGE_PAGE
 286                 // bytes, then this chunk will be least double the previous
 287                 // chunk's size.
 288                 new_cap = (*last_chunk.storage.as_ptr()).len().min(HUGE_PAGE / elem_size / 2);
 289                 new_cap *= 2;
 290             } else {
 291                 new_cap = PAGE / elem_size;
 292             }
 293             // Also ensure that this chunk can fit `additional`.
 294             new_cap = cmp::max(additional, new_cap);
 295
 296             let mut chunk = ArenaChunk::<T>::new(new_cap);
 297             self.ptr.set(chunk.start());
 298             self.end.set(chunk.end());
 299             chunks.push(chunk);
 300         }
 301     }
 302
 303     // Drops the contents of the last chunk. The last chunk is partially empty, unlike all other
 304     // chunks.
 305     fn clear_last_chunk(&self, last_chunk: &mut ArenaChunk<T>) {
 306         // Determine how much was filled.
 307         let start = last_chunk.start().addr();
 308         // We obtain the value of the pointer to the first uninitialized element.
 309         let end = self.ptr.get().addr();
 310         // We then calculate the number of elements to be dropped in the last chunk,
 311         // which is the filled area's length.
 312         let diff = if mem::size_of::<T>() == 0 {
 313             // `T` is ZST. It can't have a drop flag, so the value here doesn't matter. We get
 314             // the number of zero-sized values in the last and only chunk, just out of caution.
 315             // Recall that `end` was incremented for each allocated value.
 316             end - start
 317         } else {
 318             // FIXME: this should *likely* use `offset_from`, but more
 319             // investigation is needed (including running tests in miri).
 320             (end - start) / mem::size_of::<T>()
 321         };
 322         // Pass that to the `destroy` method.
 323         unsafe {
 324             last_chunk.destroy(diff);
 325         }
 326         // Reset the chunk.
 327         self.ptr.set(last_chunk.start());
 328     }
 329 }
 330
 331 unsafe impl<#[may_dangle] T> Drop for TypedArena<T> {
 332     fn drop(&mut self) {
 333         unsafe {
 334             // Determine how much was filled.
 335             let mut chunks_borrow = self.chunks.borrow_mut();
 336             if let Some(mut last_chunk) = chunks_borrow.pop() {
 337                 // Drop the contents of the last chunk.
 338                 self.clear_last_chunk(&mut last_chunk);
 339                 // The last chunk will be dropped. Destroy all other chunks.
 340                 for chunk in chunks_borrow.iter_mut() {
 341                     chunk.destroy(chunk.entries);
 342                 }
 343             }
 344             // Box handles deallocation of `last_chunk` and `self.chunks`.
 345         }
 346     }
 347 }
 348
 349 unsafe impl<T: Send> Send for TypedArena<T> {}
 350
 351 /// An arena that can hold objects of multiple different types that impl `Copy`
 352 /// and/or satisfy `!mem::needs_drop`.
 353 pub struct DroplessArena {
 354     /// A pointer to the start of the free space.
 355     start: Cell<*mut u8>,
 356
 357     /// A pointer to the end of free space.
 358     ///
 359     /// The allocation proceeds downwards from the end of the chunk towards the
 360     /// start. (This is slightly simpler and faster than allocating upwards,
 361     /// see <https://fitzgeraldnick.com/2019/11/01/always-bump-downwards.html>.)
 362     /// When this pointer crosses the start pointer, a new chunk is allocated.
 363     end: Cell<*mut u8>,
 364
 365     /// A vector of arena chunks.
 366     chunks: RefCell<Vec<ArenaChunk>>,
 367 }
 368
 369 unsafe impl Send for DroplessArena {}
 370
 371 impl Default for DroplessArena {
 372     #[inline]
 373     fn default() -> DroplessArena {
 374         DroplessArena {
 375             start: Cell::new(ptr::null_mut()),
 376             end: Cell::new(ptr::null_mut()),
 377             chunks: Default::default(),
 378         }
 379     }
 380 }
 381
 382 impl DroplessArena {
 383     #[inline(never)]
 384     #[cold]
 385     fn grow(&self, additional: usize) {
 386         unsafe {
 387             let mut chunks = self.chunks.borrow_mut();
 388             let mut new_cap;
 389             if let Some(last_chunk) = chunks.last_mut() {
 390                 // There is no need to update `last_chunk.entries` because that
 391                 // field isn't used by `DroplessArena`.
 392
 393                 // If the previous chunk's len is less than HUGE_PAGE
 394                 // bytes, then this chunk will be least double the previous
 395                 // chunk's size.
 396                 new_cap = (*last_chunk.storage.as_ptr()).len().min(HUGE_PAGE / 2);
 397                 new_cap *= 2;
 398             } else {
 399                 new_cap = PAGE;
 400             }
 401             // Also ensure that this chunk can fit `additional`.
 402             new_cap = cmp::max(additional, new_cap);
 403
 404             let mut chunk = ArenaChunk::new(new_cap);
 405             self.start.set(chunk.start());
 406             self.end.set(chunk.end());
 407             chunks.push(chunk);
 408         }
 409     }
 410
 411     /// Allocates a byte slice with specified layout from the current memory
 412     /// chunk. Returns `None` if there is no free space left to satisfy the
 413     /// request.
 414     #[inline]
 415     fn alloc_raw_without_grow(&self, layout: Layout) -> Option<*mut u8> {
 416         let start = self.start.get().addr();
 417         let old_end = self.end.get();
 418         let end = old_end.addr();
 419
 420         let align = layout.align();
 421         let bytes = layout.size();
 422
 423         let new_end = end.checked_sub(bytes)? & !(align - 1);
 424         if start <= new_end {
 425             let new_end = old_end.with_addr(new_end);
 426             self.end.set(new_end);
 427             Some(new_end)
 428         } else {
 429             None
 430         }
 431     }
 432
 433     #[inline]
 434     pub fn alloc_raw(&self, layout: Layout) -> *mut u8 {
 435         assert!(layout.size() != 0);
 436         loop {
 437             if let Some(a) = self.alloc_raw_without_grow(layout) {
 438                 break a;
 439             }
 440             // No free space left. Allocate a new chunk to satisfy the request.
 441             // On failure the grow will panic or abort.
 442             self.grow(layout.size());
 443         }
 444     }
 445
 446     #[inline]
 447     pub fn alloc<T>(&self, object: T) -> &mut T {
 448         assert!(!mem::needs_drop::<T>());
 449
 450         let mem = self.alloc_raw(Layout::for_value::<T>(&object)) as *mut T;
 451
 452         unsafe {
 453             // Write into uninitialized memory.
 454             ptr::write(mem, object);
 455             &mut *mem
 456         }
 457     }
 458
 459     /// Allocates a slice of objects that are copied into the `DroplessArena`, returning a mutable
 460     /// reference to it. Will panic if passed a zero-sized type.
 461     ///
 462     /// Panics:
 463     ///
 464     ///  - Zero-sized types
 465     ///  - Zero-length slices
 466     #[inline]
 467     pub fn alloc_slice<T>(&self, slice: &[T]) -> &mut [T]
 468     where
 469         T: Copy,
 470     {
 471         assert!(!mem::needs_drop::<T>());
 472         assert!(mem::size_of::<T>() != 0);
 473         assert!(!slice.is_empty());
 474
 475         let mem = self.alloc_raw(Layout::for_value::<[T]>(slice)) as *mut T;
 476
 477         unsafe {
 478             mem.copy_from_nonoverlapping(slice.as_ptr(), slice.len());
 479             slice::from_raw_parts_mut(mem, slice.len())
 480         }
 481     }
 482
 483     #[inline]
 484     unsafe fn write_from_iter<T, I: Iterator<Item = T>>(
 485         &self,
 486         mut iter: I,
 487         len: usize,
 488         mem: *mut T,
 489     ) -> &mut [T] {
 490         let mut i = 0;
 491         // Use a manual loop since LLVM manages to optimize it better for
 492         // slice iterators
 493         loop {
 494             let value = iter.next();
 495             if i >= len || value.is_none() {
 496                 // We only return as many items as the iterator gave us, even
 497                 // though it was supposed to give us `len`
 498                 return slice::from_raw_parts_mut(mem, i);
 499             }
 500             ptr::write(mem.add(i), value.unwrap());
 501             i += 1;
 502         }
 503     }
 504
 505     #[inline]
 506     pub fn alloc_from_iter<T, I: IntoIterator<Item = T>>(&self, iter: I) -> &mut [T] {
 507         let iter = iter.into_iter();
 508         assert!(mem::size_of::<T>() != 0);
 509         assert!(!mem::needs_drop::<T>());
 510
 511         let size_hint = iter.size_hint();
 512
 513         match size_hint {
 514             (min, Some(max)) if min == max => {
 515                 // We know the exact number of elements the iterator will produce here
 516                 let len = min;
 517
 518                 if len == 0 {
 519                     return &mut [];
 520                 }
 521
 522                 let mem = self.alloc_raw(Layout::array::<T>(len).unwrap()) as *mut T;
 523                 unsafe { self.write_from_iter(iter, len, mem) }
 524             }
 525             (_, _) => {
 526                 cold_path(move || -> &mut [T] {
 527                     let mut vec: SmallVec<[_; 8]> = iter.collect();
 528                     if vec.is_empty() {
 529                         return &mut [];
 530                     }
 531                     // Move the content to the arena by copying it and then forgetting
 532                     // the content of the SmallVec
 533                     unsafe {
 534                         let len = vec.len();
 535                         let start_ptr =
 536                             self.alloc_raw(Layout::for_value::<[T]>(vec.as_slice())) as *mut T;
 537                         vec.as_ptr().copy_to_nonoverlapping(start_ptr, len);
 538                         vec.set_len(0);
 539                         slice::from_raw_parts_mut(start_ptr, len)
 540                     }
 541                 })
 542             }
 543         }
 544     }
 545 }
 546
 547 /// Declare an `Arena` containing one dropless arena and many typed arenas (the
 548 /// types of the typed arenas are specified by the arguments).
 549 ///
 550 /// There are three cases of interest.
 551 /// - Types that are `Copy`: these need not be specified in the arguments. They
 552 ///   will use the `DroplessArena`.
 553 /// - Types that are `!Copy` and `!Drop`: these must be specified in the
 554 ///   arguments. An empty `TypedArena` will be created for each one, but the
 555 ///   `DroplessArena` will always be used and the `TypedArena` will stay empty.
 556 ///   This is odd but harmless, because an empty arena allocates no memory.
 557 /// - Types that are `!Copy` and `Drop`: these must be specified in the
 558 ///   arguments. The `TypedArena` will be used for them.
 559 ///
 560 #[rustc_macro_transparency = "semitransparent"]
 561 pub macro declare_arena([$($a:tt $name:ident: $ty:ty,)*]) {
 562     #[derive(Default)]
 563     pub struct Arena<'tcx> {
 564         pub dropless: $crate::DroplessArena,
 565         $($name: $crate::TypedArena<$ty>,)*
 566     }
 567
 568     pub trait ArenaAllocatable<'tcx, C = rustc_arena::IsNotCopy>: Sized {
 569         fn allocate_on<'a>(self, arena: &'a Arena<'tcx>) -> &'a mut Self;
 570         fn allocate_from_iter<'a>(
 571             arena: &'a Arena<'tcx>,
 572             iter: impl ::std::iter::IntoIterator<Item = Self>,
 573         ) -> &'a mut [Self];
 574     }
 575
 576     // Any type that impls `Copy` can be arena-allocated in the `DroplessArena`.
 577     impl<'tcx, T: Copy> ArenaAllocatable<'tcx, rustc_arena::IsCopy> for T {
 578         #[inline]
 579         fn allocate_on<'a>(self, arena: &'a Arena<'tcx>) -> &'a mut Self {
 580             arena.dropless.alloc(self)
 581         }
 582         #[inline]
 583         fn allocate_from_iter<'a>(
 584             arena: &'a Arena<'tcx>,
 585             iter: impl ::std::iter::IntoIterator<Item = Self>,
 586         ) -> &'a mut [Self] {
 587             arena.dropless.alloc_from_iter(iter)
 588         }
 589     }
 590     $(
 591         impl<'tcx> ArenaAllocatable<'tcx, rustc_arena::IsNotCopy> for $ty {
 592             #[inline]
 593             fn allocate_on<'a>(self, arena: &'a Arena<'tcx>) -> &'a mut Self {
 594                 if !::std::mem::needs_drop::<Self>() {
 595                     arena.dropless.alloc(self)
 596                 } else {
 597                     arena.$name.alloc(self)
 598                 }
 599             }
 600
 601             #[inline]
 602             fn allocate_from_iter<'a>(
 603                 arena: &'a Arena<'tcx>,
 604                 iter: impl ::std::iter::IntoIterator<Item = Self>,
 605             ) -> &'a mut [Self] {
 606                 if !::std::mem::needs_drop::<Self>() {
 607                     arena.dropless.alloc_from_iter(iter)
 608                 } else {
 609                     arena.$name.alloc_from_iter(iter)
 610                 }
 611             }
 612         }
 613     )*
 614
 615     impl<'tcx> Arena<'tcx> {
 616         #[inline]
 617         pub fn alloc<T: ArenaAllocatable<'tcx, C>, C>(&self, value: T) -> &mut T {
 618             value.allocate_on(self)
 619         }
 620
 621         // Any type that impls `Copy` can have slices be arena-allocated in the `DroplessArena`.
 622         #[inline]
 623         pub fn alloc_slice<T: ::std::marker::Copy>(&self, value: &[T]) -> &mut [T] {
 624             if value.is_empty() {
 625                 return &mut [];
 626             }
 627             self.dropless.alloc_slice(value)
 628         }
 629
 630         pub fn alloc_from_iter<'a, T: ArenaAllocatable<'tcx, C>, C>(
 631             &'a self,
 632             iter: impl ::std::iter::IntoIterator<Item = T>,
 633         ) -> &'a mut [T] {
 634             T::allocate_from_iter(self, iter)
 635         }
 636     }
 637 }
 638
 639 // Marker types that let us give different behaviour for arenas allocating
 640 // `Copy` types vs `!Copy` types.
 641 pub struct IsCopy;
 642 pub struct IsNotCopy;
 643
 644 #[cfg(test)]
 645 mod tests;