#![doc(
html_root_url = "https://doc.rust-lang.org/nightly/nightly-rustc/",
test(no_crate_inject, attr(deny(warnings)))
)]
#![feature(dropck_eyepatch)]
#![feature(new_uninit)]
#![feature(maybe_uninit_slice)]
#![feature(min_specialization)]
#![cfg_attr(test, feature(test))]
use rustc_data_structures::sync;
use smallvec::SmallVec;
use std::alloc::Layout;
use std::cell::{Cell, RefCell};
use std::cmp;
use std::marker::{PhantomData, Send};
use std::mem::{self, MaybeUninit};
use std::ptr;
use std::slice;
#[inline(never)]
#[cold]
fn cold_path<F: FnOnce() -> R, R>(f: F) -> R {
f()
}
pub struct TypedArena<T> {
ptr: Cell<*mut T>,
end: Cell<*mut T>,
chunks: RefCell<Vec<TypedArenaChunk<T>>>,
_own: PhantomData<T>,
}
struct TypedArenaChunk<T> {
storage: Box<[MaybeUninit<T>]>,
entries: usize,
}
impl<T> TypedArenaChunk<T> {
#[inline]
unsafe fn new(capacity: usize) -> TypedArenaChunk<T> {
TypedArenaChunk { storage: Box::new_uninit_slice(capacity), entries: 0 }
}
#[inline]
unsafe fn destroy(&mut self, len: usize) {
if mem::needs_drop::<T>() {
ptr::drop_in_place(MaybeUninit::slice_assume_init_mut(&mut self.storage[..len]));
}
}
#[inline]
fn start(&mut self) -> *mut T {
MaybeUninit::slice_as_mut_ptr(&mut self.storage)
}
#[inline]
fn end(&mut self) -> *mut T {
unsafe {
if mem::size_of::<T>() == 0 {
!0 as *mut T
} else {
self.start().add(self.storage.len())
}
}
}
}
const PAGE: usize = 4096;
const HUGE_PAGE: usize = 2 * 1024 * 1024;
impl<T> Default for TypedArena<T> {
fn default() -> TypedArena<T> {
TypedArena {
ptr: Cell::new(ptr::null_mut()),
end: Cell::new(ptr::null_mut()),
chunks: RefCell::new(vec![]),
_own: PhantomData,
}
}
}
trait IterExt<T> {
fn alloc_from_iter(self, arena: &TypedArena<T>) -> &mut [T];
}
impl<I, T> IterExt<T> for I
where
I: IntoIterator<Item = T>,
{
#[inline]
default fn alloc_from_iter(self, arena: &TypedArena<T>) -> &mut [T] {
let vec: SmallVec<[_; 8]> = self.into_iter().collect();
vec.alloc_from_iter(arena)
}
}
impl<T, const N: usize> IterExt<T> for std::array::IntoIter<T, N> {
#[inline]
fn alloc_from_iter(self, arena: &TypedArena<T>) -> &mut [T] {
let len = self.len();
if len == 0 {
return &mut [];
}
unsafe {
let start_ptr = arena.alloc_raw_slice(len);
self.as_slice().as_ptr().copy_to_nonoverlapping(start_ptr, len);
mem::forget(self);
slice::from_raw_parts_mut(start_ptr, len)
}
}
}
impl<T> IterExt<T> for Vec<T> {
#[inline]
fn alloc_from_iter(mut self, arena: &TypedArena<T>) -> &mut [T] {
let len = self.len();
if len == 0 {
return &mut [];
}
unsafe {
let start_ptr = arena.alloc_raw_slice(len);
self.as_ptr().copy_to_nonoverlapping(start_ptr, len);
self.set_len(0);
slice::from_raw_parts_mut(start_ptr, len)
}
}
}
impl<A: smallvec::Array> IterExt<A::Item> for SmallVec<A> {
#[inline]
fn alloc_from_iter(mut self, arena: &TypedArena<A::Item>) -> &mut [A::Item] {
let len = self.len();
if len == 0 {
return &mut [];
}
unsafe {
let start_ptr = arena.alloc_raw_slice(len);
self.as_ptr().copy_to_nonoverlapping(start_ptr, len);
self.set_len(0);
slice::from_raw_parts_mut(start_ptr, len)
}
}
}
impl<T> TypedArena<T> {
#[inline]
pub fn alloc(&self, object: T) -> &mut T {
if self.ptr == self.end {
self.grow(1)
}
unsafe {
if mem::size_of::<T>() == 0 {
self.ptr.set((self.ptr.get() as *mut u8).wrapping_offset(1) as *mut T);
let ptr = mem::align_of::<T>() as *mut T;
ptr::write(ptr, object);
&mut *ptr
} else {
let ptr = self.ptr.get();
self.ptr.set(self.ptr.get().offset(1));
ptr::write(ptr, object);
&mut *ptr
}
}
}
#[inline]
fn can_allocate(&self, additional: usize) -> bool {
let available_bytes = self.end.get() as usize - self.ptr.get() as usize;
let additional_bytes = additional.checked_mul(mem::size_of::<T>()).unwrap();
available_bytes >= additional_bytes
}
#[inline]
fn ensure_capacity(&self, additional: usize) {
if !self.can_allocate(additional) {
self.grow(additional);
debug_assert!(self.can_allocate(additional));
}
}
#[inline]
unsafe fn alloc_raw_slice(&self, len: usize) -> *mut T {
assert!(mem::size_of::<T>() != 0);
assert!(len != 0);
self.ensure_capacity(len);
let start_ptr = self.ptr.get();
self.ptr.set(start_ptr.add(len));
start_ptr
}
#[inline]
pub fn alloc_slice(&self, slice: &[T]) -> &mut [T]
where
T: Copy,
{
unsafe {
let len = slice.len();
let start_ptr = self.alloc_raw_slice(len);
slice.as_ptr().copy_to_nonoverlapping(start_ptr, len);
slice::from_raw_parts_mut(start_ptr, len)
}
}
#[inline]
pub fn alloc_from_iter<I: IntoIterator<Item = T>>(&self, iter: I) -> &mut [T] {
assert!(mem::size_of::<T>() != 0);
iter.alloc_from_iter(self)
}
#[inline(never)]
#[cold]
fn grow(&self, additional: usize) {
unsafe {
let elem_size = cmp::max(1, mem::size_of::<T>());
let mut chunks = self.chunks.borrow_mut();
let mut new_cap;
if let Some(last_chunk) = chunks.last_mut() {
if mem::needs_drop::<T>() {
let used_bytes = self.ptr.get() as usize - last_chunk.start() as usize;
last_chunk.entries = used_bytes / mem::size_of::<T>();
}
new_cap = last_chunk.storage.len().min(HUGE_PAGE / elem_size / 2);
new_cap *= 2;
} else {
new_cap = PAGE / elem_size;
}
new_cap = cmp::max(additional, new_cap);
let mut chunk = TypedArenaChunk::<T>::new(new_cap);
self.ptr.set(chunk.start());
self.end.set(chunk.end());
chunks.push(chunk);
}
}
fn clear_last_chunk(&self, last_chunk: &mut TypedArenaChunk<T>) {
let start = last_chunk.start() as usize;
let end = self.ptr.get() as usize;
let diff = if mem::size_of::<T>() == 0 {
end - start
} else {
(end - start) / mem::size_of::<T>()
};
unsafe {
last_chunk.destroy(diff);
}
self.ptr.set(last_chunk.start());
}
}
unsafe impl<#[may_dangle] T> Drop for TypedArena<T> {
fn drop(&mut self) {
unsafe {
let mut chunks_borrow = self.chunks.borrow_mut();
if let Some(mut last_chunk) = chunks_borrow.pop() {
self.clear_last_chunk(&mut last_chunk);
for chunk in chunks_borrow.iter_mut() {
chunk.destroy(chunk.entries);
}
}
}
}
}
unsafe impl<T: Send> Send for TypedArena<T> {}
pub struct DroplessArena {
start: Cell<*mut u8>,
end: Cell<*mut u8>,
chunks: RefCell<Vec<TypedArenaChunk<u8>>>,
}
unsafe impl Send for DroplessArena {}
impl Default for DroplessArena {
#[inline]
fn default() -> DroplessArena {
DroplessArena {
start: Cell::new(ptr::null_mut()),
end: Cell::new(ptr::null_mut()),
chunks: Default::default(),
}
}
}
impl DroplessArena {
#[inline(never)]
#[cold]
fn grow(&self, additional: usize) {
unsafe {
let mut chunks = self.chunks.borrow_mut();
let mut new_cap;
if let Some(last_chunk) = chunks.last_mut() {
new_cap = last_chunk.storage.len().min(HUGE_PAGE / 2);
new_cap *= 2;
} else {
new_cap = PAGE;
}
new_cap = cmp::max(additional, new_cap);
let mut chunk = TypedArenaChunk::<u8>::new(new_cap);
self.start.set(chunk.start());
self.end.set(chunk.end());
chunks.push(chunk);
}
}
#[inline]
fn alloc_raw_without_grow(&self, layout: Layout) -> Option<*mut u8> {
let start = self.start.get() as usize;
let end = self.end.get() as usize;
let align = layout.align();
let bytes = layout.size();
let new_end = end.checked_sub(bytes)? & !(align - 1);
if start <= new_end {
let new_end = new_end as *mut u8;
self.end.set(new_end);
Some(new_end)
} else {
None
}
}
#[inline]
pub fn alloc_raw(&self, layout: Layout) -> *mut u8 {
assert!(layout.size() != 0);
loop {
if let Some(a) = self.alloc_raw_without_grow(layout) {
break a;
}
self.grow(layout.size());
}
}
#[inline]
pub fn alloc<T>(&self, object: T) -> &mut T {
assert!(!mem::needs_drop::<T>());
let mem = self.alloc_raw(Layout::for_value::<T>(&object)) as *mut T;
unsafe {
ptr::write(mem, object);
&mut *mem
}
}
#[inline]
pub fn alloc_slice<T>(&self, slice: &[T]) -> &mut [T]
where
T: Copy,
{
assert!(!mem::needs_drop::<T>());
assert!(mem::size_of::<T>() != 0);
assert!(!slice.is_empty());
let mem = self.alloc_raw(Layout::for_value::<[T]>(slice)) as *mut T;
unsafe {
mem.copy_from_nonoverlapping(slice.as_ptr(), slice.len());
slice::from_raw_parts_mut(mem, slice.len())
}
}
#[inline]
unsafe fn write_from_iter<T, I: Iterator<Item = T>>(
&self,
mut iter: I,
len: usize,
mem: *mut T,
) -> &mut [T] {
let mut i = 0;
loop {
let value = iter.next();
if i >= len || value.is_none() {
return slice::from_raw_parts_mut(mem, i);
}
ptr::write(mem.add(i), value.unwrap());
i += 1;
}
}
#[inline]
pub fn alloc_from_iter<T, I: IntoIterator<Item = T>>(&self, iter: I) -> &mut [T] {
let iter = iter.into_iter();
assert!(mem::size_of::<T>() != 0);
assert!(!mem::needs_drop::<T>());
let size_hint = iter.size_hint();
match size_hint {
(min, Some(max)) if min == max => {
let len = min;
if len == 0 {
return &mut [];
}
let mem = self.alloc_raw(Layout::array::<T>(len).unwrap()) as *mut T;
unsafe { self.write_from_iter(iter, len, mem) }
}
(_, _) => {
cold_path(move || -> &mut [T] {
let mut vec: SmallVec<[_; 8]> = iter.collect();
if vec.is_empty() {
return &mut [];
}
unsafe {
let len = vec.len();
let start_ptr =
self.alloc_raw(Layout::for_value::<[T]>(vec.as_slice())) as *mut T;
vec.as_ptr().copy_to_nonoverlapping(start_ptr, len);
vec.set_len(0);
slice::from_raw_parts_mut(start_ptr, len)
}
})
}
}
}
}
struct DropType {
drop_fn: unsafe fn(*mut u8),
obj: *mut u8,
}
#[cfg(parallel_compiler)]
unsafe impl sync::Send for DropType {}
impl DropType {
#[inline]
unsafe fn new<T: sync::Send>(obj: *mut T) -> Self {
unsafe fn drop_for_type<T>(to_drop: *mut u8) {
std::ptr::drop_in_place(to_drop as *mut T)
}
DropType { drop_fn: drop_for_type::<T>, obj: obj as *mut u8 }
}
}
impl Drop for DropType {
fn drop(&mut self) {
unsafe { (self.drop_fn)(self.obj) }
}
}
#[derive(Default)]
pub struct DropArena {
destructors: RefCell<Vec<DropType>>,
arena: DroplessArena,
}
impl DropArena {
#[inline]
pub unsafe fn alloc<T>(&self, object: T) -> &mut T
where
T: sync::Send,
{
let mem = self.arena.alloc_raw(Layout::new::<T>()) as *mut T;
ptr::write(mem, object);
let result = &mut *mem;
self.destructors.borrow_mut().push(DropType::new(result));
result
}
#[inline]
pub unsafe fn alloc_from_iter<T, I>(&self, iter: I) -> &mut [T]
where
T: sync::Send,
I: IntoIterator<Item = T>,
{
let mut vec: SmallVec<[_; 8]> = iter.into_iter().collect();
if vec.is_empty() {
return &mut [];
}
let len = vec.len();
let start_ptr = self.arena.alloc_raw(Layout::array::<T>(len).unwrap()) as *mut T;
let mut destructors = self.destructors.borrow_mut();
destructors.reserve(len);
vec.as_ptr().copy_to_nonoverlapping(start_ptr, len);
mem::forget(vec.drain(..));
for i in 0..len {
destructors.push(DropType::new(start_ptr.add(i)));
}
slice::from_raw_parts_mut(start_ptr, len)
}
}
#[macro_export]
macro_rules! arena_for_type {
([][$ty:ty]) => {
$crate::TypedArena<$ty>
};
([few $(, $attrs:ident)*][$ty:ty]) => {
::std::marker::PhantomData<$ty>
};
([$ignore:ident $(, $attrs:ident)*]$args:tt) => {
$crate::arena_for_type!([$($attrs),*]$args)
};
}
#[macro_export]
macro_rules! which_arena_for_type {
([][$arena:expr]) => {
::std::option::Option::Some($arena)
};
([few$(, $attrs:ident)*][$arena:expr]) => {
::std::option::Option::None
};
([$ignore:ident$(, $attrs:ident)*]$args:tt) => {
$crate::which_arena_for_type!([$($attrs),*]$args)
};
}
#[macro_export]
macro_rules! declare_arena {
([], [$($a:tt $name:ident: $ty:ty,)*], $tcx:lifetime) => {
#[derive(Default)]
pub struct Arena<$tcx> {
pub dropless: $crate::DroplessArena,
drop: $crate::DropArena,
$($name: $crate::arena_for_type!($a[$ty]),)*
}
pub trait ArenaAllocatable<'tcx, T = Self>: Sized {
fn allocate_on<'a>(self, arena: &'a Arena<'tcx>) -> &'a mut Self;
fn allocate_from_iter<'a>(
arena: &'a Arena<'tcx>,
iter: impl ::std::iter::IntoIterator<Item = Self>,
) -> &'a mut [Self];
}
impl<'tcx, T: Copy> ArenaAllocatable<'tcx, ()> for T {
#[inline]
fn allocate_on<'a>(self, arena: &'a Arena<'tcx>) -> &'a mut Self {
arena.dropless.alloc(self)
}
#[inline]
fn allocate_from_iter<'a>(
arena: &'a Arena<'tcx>,
iter: impl ::std::iter::IntoIterator<Item = Self>,
) -> &'a mut [Self] {
arena.dropless.alloc_from_iter(iter)
}
}
$(
impl<$tcx> ArenaAllocatable<$tcx, $ty> for $ty {
#[inline]
fn allocate_on<'a>(self, arena: &'a Arena<$tcx>) -> &'a mut Self {
if !::std::mem::needs_drop::<Self>() {
return arena.dropless.alloc(self);
}
match $crate::which_arena_for_type!($a[&arena.$name]) {
::std::option::Option::<&$crate::TypedArena<Self>>::Some(ty_arena) => {
ty_arena.alloc(self)
}
::std::option::Option::None => unsafe { arena.drop.alloc(self) },
}
}
#[inline]
fn allocate_from_iter<'a>(
arena: &'a Arena<$tcx>,
iter: impl ::std::iter::IntoIterator<Item = Self>,
) -> &'a mut [Self] {
if !::std::mem::needs_drop::<Self>() {
return arena.dropless.alloc_from_iter(iter);
}
match $crate::which_arena_for_type!($a[&arena.$name]) {
::std::option::Option::<&$crate::TypedArena<Self>>::Some(ty_arena) => {
ty_arena.alloc_from_iter(iter)
}
::std::option::Option::None => unsafe { arena.drop.alloc_from_iter(iter) },
}
}
}
)*
impl<'tcx> Arena<'tcx> {
#[inline]
pub fn alloc<T: ArenaAllocatable<'tcx, U>, U>(&self, value: T) -> &mut T {
value.allocate_on(self)
}
#[inline]
pub fn alloc_slice<T: ::std::marker::Copy>(&self, value: &[T]) -> &mut [T] {
if value.is_empty() {
return &mut [];
}
self.dropless.alloc_slice(value)
}
pub fn alloc_from_iter<'a, T: ArenaAllocatable<'tcx, U>, U>(
&'a self,
iter: impl ::std::iter::IntoIterator<Item = T>,
) -> &'a mut [T] {
T::allocate_from_iter(self, iter)
}
}
}
}
#[cfg(test)]
mod tests;