#![cfg_attr(
feature = "nightly",
feature(coerce_unsized, optin_builtin_traits, unsize, specialization)
)]
use gc::GcBox;
use std::alloc::Layout;
use std::cell::{Cell, UnsafeCell};
use std::cmp::Ordering;
use std::fmt::{self, Debug, Display};
use std::hash::{Hash, Hasher};
use std::marker::PhantomData;
use std::mem::{self, align_of_val};
use std::ops::{Deref, DerefMut};
use std::ptr::{self, NonNull};
use std::rc::Rc;
#[cfg(feature = "nightly")]
use std::marker::Unsize;
#[cfg(feature = "nightly")]
use std::ops::CoerceUnsized;
mod gc;
mod trace;
pub use gc::{finalizer_safe, force_collect};
pub use trace::{Finalize, Trace};
pub struct Gc<T: Trace + ?Sized + 'static> {
ptr_root: Cell<NonNull<GcBox<T>>>,
marker: PhantomData<Rc<T>>,
}
#[cfg(feature = "nightly")]
impl<T: Trace + ?Sized + Unsize<U>, U: Trace + ?Sized> CoerceUnsized<Gc<U>> for Gc<T> {}
impl<T: Trace> Gc<T> {
pub fn new(value: T) -> Self {
assert!(mem::align_of::<GcBox<T>>() > 1);
unsafe {
let ptr = GcBox::new(value);
(*ptr.as_ptr()).value().unroot();
let gc = Gc {
ptr_root: Cell::new(NonNull::new_unchecked(ptr.as_ptr())),
marker: PhantomData,
};
gc.set_root();
gc
}
}
}
unsafe fn clear_root_bit<T: ?Sized + Trace>(ptr: NonNull<GcBox<T>>) -> NonNull<GcBox<T>> {
let mut ptr = ptr.as_ptr();
*(&mut ptr as *mut _ as *mut usize) &= !1;
NonNull::new_unchecked(ptr)
}
impl<T: Trace + ?Sized> Gc<T> {
fn rooted(&self) -> bool {
self.ptr_root.get().as_ptr() as *mut u8 as usize & 1 != 0
}
unsafe fn set_root(&self) {
let mut ptr = self.ptr_root.get().as_ptr();
*(&mut ptr as *mut *mut GcBox<T> as *mut usize) |= 1;
self.ptr_root.set(NonNull::new_unchecked(ptr));
}
unsafe fn clear_root(&self) {
self.ptr_root.set(clear_root_bit(self.ptr_root.get()));
}
#[inline]
fn inner(&self) -> &GcBox<T> {
assert!(finalizer_safe());
unsafe { &*clear_root_bit(self.ptr_root.get()).as_ptr() }
}
}
impl<T: Trace + ?Sized> Gc<T> {
pub fn into_raw(this: Self) -> *const T {
let ptr: *const T = &*this;
mem::forget(this);
ptr
}
pub unsafe fn from_raw(ptr: *const T) -> Self {
let align = align_of_val(&*ptr);
let layout = Layout::new::<GcBox<()>>();
let offset = (layout.size() + padding_needed_for_gc(align)) as isize;
let fake_ptr = ptr as *mut GcBox<T>;
let rc_ptr = set_data_ptr(fake_ptr, (ptr as *mut u8).offset(-offset));
Gc {
ptr_root: Cell::new(NonNull::new_unchecked(rc_ptr)),
marker: PhantomData,
}
}
}
impl<T: Trace + ?Sized> Finalize for Gc<T> {}
unsafe impl<T: Trace + ?Sized> Trace for Gc<T> {
#[inline]
unsafe fn trace(&self) {
self.inner().trace_inner();
}
#[inline]
unsafe fn root(&self) {
assert!(!self.rooted(), "Can't double-root a Gc<T>");
self.inner().root_inner();
self.set_root();
}
#[inline]
unsafe fn unroot(&self) {
assert!(self.rooted(), "Can't double-unroot a Gc<T>");
self.inner().unroot_inner();
self.clear_root();
}
#[inline]
fn finalize_glue(&self) {
Finalize::finalize(self);
}
}
impl<T: Trace + ?Sized> Clone for Gc<T> {
#[inline]
fn clone(&self) -> Self {
unsafe {
self.inner().root_inner();
let gc = Gc {
ptr_root: Cell::new(self.ptr_root.get()),
marker: PhantomData,
};
gc.set_root();
gc
}
}
}
impl<T: Trace + ?Sized> Deref for Gc<T> {
type Target = T;
#[inline]
fn deref(&self) -> &T {
&self.inner().value()
}
}
impl<T: Trace + ?Sized> Drop for Gc<T> {
#[inline]
fn drop(&mut self) {
if self.rooted() {
unsafe {
self.inner().unroot_inner();
}
}
}
}
impl<T: Trace + Default> Default for Gc<T> {
#[inline]
fn default() -> Self {
Self::new(Default::default())
}
}
impl<T: Trace + ?Sized + PartialEq> PartialEq for Gc<T> {
#[inline(always)]
fn eq(&self, other: &Self) -> bool {
**self == **other
}
#[inline(always)]
fn ne(&self, other: &Self) -> bool {
**self != **other
}
}
impl<T: Trace + ?Sized + Eq> Eq for Gc<T> {}
impl<T: Trace + ?Sized + PartialOrd> PartialOrd for Gc<T> {
#[inline(always)]
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
(**self).partial_cmp(&**other)
}
#[inline(always)]
fn lt(&self, other: &Self) -> bool {
**self < **other
}
#[inline(always)]
fn le(&self, other: &Self) -> bool {
**self <= **other
}
#[inline(always)]
fn gt(&self, other: &Self) -> bool {
**self > **other
}
#[inline(always)]
fn ge(&self, other: &Self) -> bool {
**self >= **other
}
}
impl<T: Trace + ?Sized + Ord> Ord for Gc<T> {
#[inline]
fn cmp(&self, other: &Self) -> Ordering {
(**self).cmp(&**other)
}
}
impl<T: Trace + ?Sized + Hash> Hash for Gc<T> {
fn hash<H: Hasher>(&self, state: &mut H) {
(**self).hash(state);
}
}
impl<T: Trace + ?Sized + Display> Display for Gc<T> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
Display::fmt(&**self, f)
}
}
impl<T: Trace + ?Sized + Debug> Debug for Gc<T> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
Debug::fmt(&**self, f)
}
}
impl<T: Trace> fmt::Pointer for Gc<T> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
fmt::Pointer::fmt(&self.inner(), f)
}
}
impl<T: Trace> From<T> for Gc<T> {
fn from(t: T) -> Self {
Self::new(t)
}
}
#[derive(Copy, Clone)]
struct BorrowFlag(usize);
#[derive(Copy, Clone, Debug, Eq, PartialEq)]
enum BorrowState {
Reading,
Writing,
Unused,
}
const ROOT: usize = 1;
const WRITING: usize = !1;
const UNUSED: usize = 0;
const BORROWFLAG_INIT: BorrowFlag = BorrowFlag(1);
impl BorrowFlag {
fn borrowed(self) -> BorrowState {
match self.0 & !ROOT {
UNUSED => BorrowState::Unused,
WRITING => BorrowState::Writing,
_ => BorrowState::Reading,
}
}
fn rooted(self) -> bool {
match self.0 & ROOT {
0 => false,
_ => true,
}
}
fn set_writing(self) -> Self {
BorrowFlag(self.0 | WRITING)
}
fn set_unused(self) -> Self {
BorrowFlag(self.0 & ROOT)
}
fn add_reading(self) -> Self {
assert!(self.borrowed() != BorrowState::Writing);
BorrowFlag(self.0 + 0b10)
}
fn sub_reading(self) -> Self {
assert!(self.borrowed() == BorrowState::Reading);
BorrowFlag(self.0 - 0b10)
}
fn set_rooted(self, rooted: bool) -> Self {
BorrowFlag((self.0 & !ROOT) | (rooted as usize))
}
}
pub struct GcCell<T: ?Sized + 'static> {
flags: Cell<BorrowFlag>,
cell: UnsafeCell<T>,
}
impl<T: Trace> GcCell<T> {
#[inline]
pub fn new(value: T) -> Self {
GcCell {
flags: Cell::new(BORROWFLAG_INIT),
cell: UnsafeCell::new(value),
}
}
#[inline]
pub fn into_inner(self) -> T {
self.cell.into_inner()
}
}
impl<T: Trace + ?Sized> GcCell<T> {
#[inline]
pub fn borrow(&self) -> GcCellRef<T> {
if self.flags.get().borrowed() == BorrowState::Writing {
panic!("GcCell<T> already mutably borrowed");
}
self.flags.set(self.flags.get().add_reading());
assert!(self.flags.get().borrowed() == BorrowState::Reading);
unsafe {
GcCellRef {
flags: &self.flags,
value: &*self.cell.get(),
}
}
}
#[inline]
pub fn borrow_mut(&self) -> GcCellRefMut<T> {
if self.flags.get().borrowed() != BorrowState::Unused {
panic!("GcCell<T> already borrowed");
}
self.flags.set(self.flags.get().set_writing());
unsafe {
if !self.flags.get().rooted() {
(*self.cell.get()).root();
}
GcCellRefMut {
flags: &self.flags,
value: &mut *self.cell.get(),
}
}
}
}
impl<T: Trace + ?Sized> Finalize for GcCell<T> {}
unsafe impl<T: Trace + ?Sized> Trace for GcCell<T> {
#[inline]
unsafe fn trace(&self) {
match self.flags.get().borrowed() {
BorrowState::Writing => (),
_ => (*self.cell.get()).trace(),
}
}
#[inline]
unsafe fn root(&self) {
assert!(!self.flags.get().rooted(), "Can't root a GcCell twice!");
self.flags.set(self.flags.get().set_rooted(true));
match self.flags.get().borrowed() {
BorrowState::Writing => (),
_ => (*self.cell.get()).root(),
}
}
#[inline]
unsafe fn unroot(&self) {
assert!(self.flags.get().rooted(), "Can't unroot a GcCell twice!");
self.flags.set(self.flags.get().set_rooted(false));
match self.flags.get().borrowed() {
BorrowState::Writing => (),
_ => (*self.cell.get()).unroot(),
}
}
#[inline]
fn finalize_glue(&self) {
Finalize::finalize(self);
match self.flags.get().borrowed() {
BorrowState::Writing => (),
_ => unsafe { (*self.cell.get()).finalize_glue() },
}
}
}
pub struct GcCellRef<'a, T: Trace + ?Sized + 'static> {
flags: &'a Cell<BorrowFlag>,
value: &'a T,
}
impl<'a, T: Trace + ?Sized> Deref for GcCellRef<'a, T> {
type Target = T;
#[inline]
fn deref(&self) -> &T {
self.value
}
}
impl<'a, T: Trace + ?Sized> Drop for GcCellRef<'a, T> {
fn drop(&mut self) {
debug_assert!(self.flags.get().borrowed() == BorrowState::Reading);
self.flags.set(self.flags.get().sub_reading());
}
}
impl<'a, T: Trace + ?Sized + Debug> Debug for GcCellRef<'a, T> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
Debug::fmt(&**self, f)
}
}
pub struct GcCellRefMut<'a, T: Trace + ?Sized + 'static> {
flags: &'a Cell<BorrowFlag>,
value: &'a mut T,
}
impl<'a, T: Trace + ?Sized> Deref for GcCellRefMut<'a, T> {
type Target = T;
#[inline]
fn deref(&self) -> &T {
self.value
}
}
impl<'a, T: Trace + ?Sized> DerefMut for GcCellRefMut<'a, T> {
#[inline]
fn deref_mut(&mut self) -> &mut T {
self.value
}
}
impl<'a, T: Trace + ?Sized> Drop for GcCellRefMut<'a, T> {
#[inline]
fn drop(&mut self) {
debug_assert!(self.flags.get().borrowed() == BorrowState::Writing);
if !self.flags.get().rooted() {
unsafe {
self.value.unroot();
}
}
self.flags.set(self.flags.get().set_unused());
}
}
impl<'a, T: Trace + ?Sized + Debug> Debug for GcCellRefMut<'a, T> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
Debug::fmt(&*(self.deref()), f)
}
}
unsafe impl<T: ?Sized + Send> Send for GcCell<T> {}
impl<T: Trace + Clone> Clone for GcCell<T> {
#[inline]
fn clone(&self) -> Self {
Self::new(self.borrow().clone())
}
}
impl<T: Trace + Default> Default for GcCell<T> {
#[inline]
fn default() -> Self {
Self::new(Default::default())
}
}
impl<T: Trace + ?Sized + PartialEq> PartialEq for GcCell<T> {
#[inline(always)]
fn eq(&self, other: &Self) -> bool {
*self.borrow() == *other.borrow()
}
#[inline(always)]
fn ne(&self, other: &Self) -> bool {
*self.borrow() != *other.borrow()
}
}
impl<T: Trace + ?Sized + Eq> Eq for GcCell<T> {}
impl<T: Trace + ?Sized + PartialOrd> PartialOrd for GcCell<T> {
#[inline(always)]
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
(*self.borrow()).partial_cmp(&*other.borrow())
}
#[inline(always)]
fn lt(&self, other: &Self) -> bool {
*self.borrow() < *other.borrow()
}
#[inline(always)]
fn le(&self, other: &Self) -> bool {
*self.borrow() <= *other.borrow()
}
#[inline(always)]
fn gt(&self, other: &Self) -> bool {
*self.borrow() > *other.borrow()
}
#[inline(always)]
fn ge(&self, other: &Self) -> bool {
*self.borrow() >= *other.borrow()
}
}
impl<T: Trace + ?Sized + Ord> Ord for GcCell<T> {
#[inline]
fn cmp(&self, other: &GcCell<T>) -> Ordering {
(*self.borrow()).cmp(&*other.borrow())
}
}
impl<T: Trace + ?Sized + Debug> Debug for GcCell<T> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
match self.flags.get().borrowed() {
BorrowState::Unused | BorrowState::Reading => f
.debug_struct("GcCell")
.field("value", &self.borrow())
.finish(),
BorrowState::Writing => f
.debug_struct("GcCell")
.field("value", &"<borrowed>")
.finish(),
}
}
}
unsafe fn set_data_ptr<T: ?Sized, U>(mut ptr: *mut T, data: *mut U) -> *mut T {
ptr::write(&mut ptr as *mut _ as *mut *mut u8, data as *mut u8);
ptr
}
fn padding_needed_for_gc(align: usize) -> usize {
assert!(align.count_ones() == 1, "align must be a power-of-two!");
let misaligned = mem::size_of::<GcBox<()>>() & (align - 1);
if misaligned > 0 {
align - misaligned
} else {
0
}
}