#![feature(box_syntax)]
#![feature(box_into_raw_non_null)]
#![feature(map_first_last)]
#![allow(private_in_public)]
#[cfg(test)]
mod tests {
#[test]
fn it_works() {
panic!("TODO")
}
}
extern crate alloc;
use alloc::{boxed::Box, collections::btree_set::BTreeSet};
use core::{
cmp::{Ord, Ordering},
hash::{Hash, Hasher},
marker::PhantomData,
mem::swap,
ops::{Deref, Drop},
ptr::NonNull,
};
use derive_deref::Deref;
use hashbrown::HashSet;
use spin::{Mutex, MutexGuard};
pub mod trace {
pub use super::libbare::{Trace, Tracer};
}
pub mod liblifetime {
pub use super::trace::*;
use super::*;
pub struct Gc<'root, T: Trace> {
val: libcore::Gc<T>,
phantom: PhantomData<&'root libcore::Gc<T>>,
}
impl<T: Trace> Clone for Gc<'_, T> {
fn clone(&self) -> Self {
Self {
val: self.val,
phantom: PhantomData,
}
}
}
impl<T: Trace> Copy for Gc<'_, T> {}
pub struct RootedGc<'root, T: Trace> {
val: libcore::Root<libcore::Gc<T>>,
phantom: PhantomData<&'root libcore::Root<T>>,
}
impl<T: Trace> Deref for RootedGc<'_, T> {
type Target = T;
fn deref(&self) -> &Self::Target {
unsafe { self.val.deref().deref() }
}
}
impl<'root, T: Trace> RootedGc<'root, T> {
pub fn new(x: T, _rooter: &Rooter<'root>) -> Self {
Self {
val: libcore::Root::new(libcore::Gc::new(x)),
phantom: PhantomData,
}
}
}
impl<'root, T: Trace> Clone for RootedGc<'root, T> {
fn clone(&self) -> Self {
Self {
val: libcore::Root::new(*self.val),
phantom: PhantomData,
}
}
}
pub struct Rooter<'root>(PhantomData<&'root ()>);
impl<'root> Rooter<'root> {
#[doc(hidden)]
pub unsafe fn new(_: &'root ()) -> Self {
Rooter(PhantomData)
}
pub fn create_rooted_gc<T: Trace>(&self, x: T) -> RootedGc<'root, T> {
RootedGc::new(x, self)
}
}
#[macro_export]
macro_rules! letrooter {
($root:ident) => {
let root = ();
#[allow(unused_mut)]
let $root = unsafe { $crate::Rooter::new(&root) };
};
}
}
pub mod libcore {
pub use super::trace::*;
use super::*;
pub struct Gc<T: Trace>(libbare::Gc<T>);
impl<T: Trace> Clone for Gc<T> {
fn clone(&self) -> Self {
self.0.try_marksweep_step();
Self(self.0)
}
}
impl<T: Trace> Copy for Gc<T> {}
impl<T: Trace> Gc<T> {
pub fn new(x: T) -> Self {
Self(libbare::Gc::new(x))
}
pub unsafe fn deref(&self) -> &T {
self.0.try_marksweep_step();
self.0.deref()
}
}
impl<T: Trace> Trace for Gc<T> {
fn trace(&self, tracer: &mut Tracer) {
self.0.trace(tracer);
}
}
pub struct Root<T: Trace>(libbare::Root<T>);
impl<T: Trace> Root<T> {
pub fn new(x: T) -> Self {
Self(libbare::Root::new(x))
}
}
impl<T: Trace> Deref for Root<T> {
type Target = T;
fn deref(&self) -> &Self::Target {
self.0.try_marksweep_step();
&*self.0
}
}
}
pub mod libbare {
use super::*;
pub struct Tracer<'a>(Box<dyn FnMut(Box<dyn AnyGc>) + 'a>);
pub trait Trace: 'static {
fn trace(&self, tracer: &mut Tracer) {
let _ = tracer;
}
}
pub struct Gc<T: Trace> {
ptr: NonNull<GcInner<T>>,
phantom: PhantomData<GcInner<T>>,
}
impl<T: Trace> Clone for Gc<T> {
fn clone(&self) -> Self {
Gc {
ptr: self.ptr,
phantom: PhantomData,
}
}
}
impl<T: Trace> Copy for Gc<T> {}
unsafe impl<T: Trace + Sync + Send> Send for Gc<T> {}
unsafe impl<T: Trace + Sync + Send> Sync for Gc<T> {}
trait GcTraverse {
fn gc_traverse(&self, tracer: &mut Tracer);
}
trait AnyGc: GcTraverse {
fn clone_as_any(&self) -> Box<dyn AnyGc>;
fn get_unit_gcinner_ptr(&self) -> NonNull<()>;
unsafe fn get_space_nonnull_mutex(&self) -> NonNull<Mutex<NonNull<AutoGcSpace>>>;
unsafe fn destory(&self);
fn clone_as_gc_traverse(&self) -> Box<dyn GcTraverse>;
}
impl<T: Trace> GcTraverse for Gc<T> {
fn gc_traverse(&self, tracer: &mut Tracer) {
unsafe {
self.deref().trace(tracer);
}
}
}
impl<T: Trace> AnyGc for Gc<T> {
fn clone_as_any(&self) -> Box<dyn AnyGc> {
box *self
}
fn clone_as_gc_traverse(&self) -> Box<dyn GcTraverse> {
box *self
}
fn get_unit_gcinner_ptr(&self) -> NonNull<()> {
NonNull::cast(self.ptr)
}
unsafe fn get_space_nonnull_mutex(&self) -> NonNull<Mutex<NonNull<AutoGcSpace>>> {
let ptr = self.ptr;
let mut ptr = ptr;
NonNull::new_unchecked(&mut ptr.as_mut().space)
}
unsafe fn destory(&self) {
drop(Box::from_raw(self.ptr.as_ptr()));
}
}
impl<T: Trace> Trace for Gc<T>
where
Gc<T>: AnyGc,
{
fn trace(&self, tracer: &mut Tracer) {
tracer.0(self.clone_as_any());
}
}
#[derive(Deref)]
struct HashableAnyGc(Box<dyn AnyGc>);
impl Hash for HashableAnyGc {
fn hash<H: Hasher>(&self, state: &mut H) {
self.get_unit_gcinner_ptr().hash(state);
}
}
impl PartialEq for HashableAnyGc {
fn eq(&self, other: &Self) -> bool {
self.get_unit_gcinner_ptr() == other.get_unit_gcinner_ptr()
}
}
impl Eq for HashableAnyGc {}
impl Ord for HashableAnyGc {
fn cmp(&self, other: &Self) -> Ordering {
self.get_unit_gcinner_ptr()
.cmp(&other.get_unit_gcinner_ptr())
}
}
impl PartialOrd for HashableAnyGc {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
struct GcInner<T: Trace> {
space: Mutex<NonNull<AutoGcSpace>>,
data: T,
}
impl<T: Trace> Gc<T> {
pub fn new(x: T) -> Self {
let ptr = Box::into_raw_non_null(box GcInner {
space: Mutex::new(Box::into_raw_non_null(box AutoGcSpace::new())),
data: x,
});
let result = Gc {
ptr: ptr,
phantom: PhantomData,
};
unsafe {
ptr.as_ref()
.space
.lock()
.as_ref()
.add_element(result.clone_as_any());
}
result
}
pub unsafe fn deref(&self) -> &T {
&self.ptr.as_ref().data
}
pub fn try_marksweep_step(&self) {
unsafe {
if let Some(ptr) = {
let maybe_locked = self.ptr.as_ref().space.try_lock();
if let Some(ptr) = maybe_locked {
let result: NonNull<_> = *ptr;
Some(result)
} else {
None
}
} {
AutoGcSpace::try_marksweep_step(ptr);
}
}
}
}
#[derive(Deref)]
struct AutoGcSpace(Mutex<AutoGcSpaceInner>);
struct AutoGcSpaceInner {
elements: HashSet<HashableAnyGc>,
roots: HashSet<HashableAnyRoot>,
state: AutoGcSpaceState,
}
enum AutoGcSpaceState {
Mark {
marked: HashSet<HashableAnyGc>,
marking_gc: BTreeSet<HashableAnyGc>,
marking_root: BTreeSet<HashableAnyRoot>,
},
Sweep {
marked: HashSet<HashableAnyGc>,
elements: BTreeSet<HashableAnyGc>,
},
}
impl Drop for AutoGcSpace {
fn drop(&mut self) {
let this: NonNull<Self> = unsafe { NonNull::new_unchecked(self) };
let mut locked_self = self.lock();
locked_self.state = AutoGcSpaceState::Mark {
marked: HashSet::new(),
marking_gc: BTreeSet::new(),
marking_root: BTreeSet::new(),
};
for x in locked_self.elements.drain() {
unsafe {
debug_assert_eq!(*x.get_space_nonnull_mutex().as_ref().lock(), this);
x.destory();
}
}
}
}
impl AutoGcSpace {
fn new() -> Self {
AutoGcSpace(Mutex::new(AutoGcSpaceInner {
elements: HashSet::new(),
roots: HashSet::new(),
state: AutoGcSpaceState::Mark {
marked: HashSet::new(),
marking_gc: BTreeSet::new(),
marking_root: BTreeSet::new(),
},
}))
}
fn add_root(&self, x: Box<dyn AnyRoot>) {
Self::add_root_aux(&mut self.lock(), x);
}
fn add_root_aux(locked: &mut MutexGuard<AutoGcSpaceInner>, x: Box<dyn AnyRoot>) {
let should_be_false = locked.roots.insert(HashableAnyRoot(x.clone_as_any()));
debug_assert_eq!(should_be_false, false);
match &mut locked.state {
AutoGcSpaceState::Mark {
marked: _,
marking_gc: _,
marking_root,
} => {
let should_be_false = marking_root.insert(HashableAnyRoot(x));
debug_assert_eq!(should_be_false, false);
}
AutoGcSpaceState::Sweep {
marked: _,
elements: _,
} => {}
}
}
fn add_element(&self, x: Box<dyn AnyGc>) {
Self::add_element_aux(&mut self.lock(), x);
}
fn add_element_aux(locked: &mut MutexGuard<AutoGcSpaceInner>, x: Box<dyn AnyGc>) {
let should_be_false = locked.elements.insert(HashableAnyGc(x.clone_as_any()));
debug_assert_eq!(should_be_false, false);
match &mut locked.state {
AutoGcSpaceState::Mark {
marked: _,
marking_gc,
marking_root: _,
} => {
let should_be_false = marking_gc.insert(HashableAnyGc(x));
debug_assert_eq!(should_be_false, false);
}
AutoGcSpaceState::Sweep {
marked: _,
elements: _,
} => {}
}
}
unsafe fn destory(this: NonNull<Self>) {
drop(Box::from_raw(this.as_ptr()));
}
unsafe fn remove_root_and_destory_if_empty(this: NonNull<Self>, x: &HashableAnyRoot) {
let mut locked_this = this.as_ref().lock();
let should_be_true = locked_this.roots.remove(x);
debug_assert!(should_be_true);
match &mut locked_this.state {
AutoGcSpaceState::Mark {
marked: _,
marking_gc: _,
marking_root,
} => {
marking_root.remove(x);
}
AutoGcSpaceState::Sweep {
marked: _,
elements: _,
} => {}
}
drop(locked_this);
Self::destory_if_empty(this);
}
unsafe fn destory_if_empty(this: NonNull<Self>) {
let locked = this.as_ref().lock();
if locked.roots.is_empty() {
drop(locked);
Self::destory(this);
}
}
unsafe fn merge(
(this, locked_this): (NonNull<Self>, MutexGuard<AutoGcSpaceInner>),
(other, locked_other): (NonNull<Self>, MutexGuard<AutoGcSpaceInner>),
) {
let this_approximate_size =
locked_this.elements.capacity() + locked_this.roots.capacity();
let other_approximate_size =
locked_other.elements.capacity() + locked_other.roots.capacity();
if this_approximate_size > other_approximate_size {
Self::merge_aux((this, locked_this), (other, locked_other));
} else {
Self::merge_aux((other, locked_other), (this, locked_this));
}
}
unsafe fn merge_aux(
(this, locked_this): (NonNull<Self>, MutexGuard<AutoGcSpaceInner>),
(other, locked_other): (NonNull<Self>, MutexGuard<AutoGcSpaceInner>),
) {
let mut locked_this: MutexGuard<AutoGcSpaceInner> = locked_this;
let mut locked_other: MutexGuard<AutoGcSpaceInner> = locked_other;
debug_assert_eq!(
locked_this
.elements
.intersection(&locked_other.elements)
.count(),
0
);
debug_assert_eq!(
locked_this.roots.intersection(&locked_other.roots).count(),
0
);
let mut locked_this_space_refs: Vec<MutexGuard<NonNull<AutoGcSpace>>> = Vec::new();
for ptr in locked_this
.elements
.iter()
.map(|x| x.get_space_nonnull_mutex())
.chain(
locked_this
.roots
.iter()
.map(|x| x.get_space_nonnull_mutex()),
)
{
let lk = (*ptr.as_ptr()).lock();
debug_assert!(*lk == this);
locked_this_space_refs.push(lk);
}
let mut locked_other_space_refs: Vec<MutexGuard<NonNull<AutoGcSpace>>> = Vec::new();
for ptr in locked_other
.elements
.iter()
.map(|x| x.get_space_nonnull_mutex())
.chain(
locked_other
.roots
.iter()
.map(|x| x.get_space_nonnull_mutex()),
)
{
let lk = (*ptr.as_ptr()).lock();
debug_assert!(*lk == other);
locked_other_space_refs.push(lk);
}
for x in locked_other.elements.drain() {
Self::add_element_aux(&mut locked_this, x.0);
}
for x in locked_other.roots.drain() {
Self::add_root_aux(&mut locked_this, x.0);
}
drop(locked_other);
Self::destory(other);
for ptr in locked_other_space_refs.iter_mut() {
**ptr = this;
}
}
unsafe fn try_marksweep_step(this: NonNull<Self>) {
if let Some(locked_this) = this.as_ref().try_lock() {
let mut locked_this = locked_this;
match &mut locked_this.state {
AutoGcSpaceState::Mark {
marked,
marking_gc,
marking_root,
} => {
if let Some(x) = {
if let Some(x) = marking_root.pop_first() {
Some(x.clone_as_gc_traverse())
} else if let Some(x) = marking_gc.pop_first() {
Some(x.clone_as_gc_traverse())
} else {
None
}
} {
let mut to_mark_set = BTreeSet::new();
let mut tracer = Tracer(box |v: Box<dyn AnyGc>| {
let hashable_v = HashableAnyGc(v.clone_as_any());
if !marked.contains(&hashable_v) {
to_mark_set.insert(hashable_v);
}
});
x.gc_traverse(&mut tracer);
drop(tracer);
drop(x);
if let Some(other_space) = to_mark_set
.iter()
.map(|to_mark| *to_mark.get_space_nonnull_mutex().as_ref().lock())
.find(|&x| x != this)
{
if let Some(locked_other_space) = other_space.as_ref().try_lock() {
return Self::merge(
(this, locked_this),
(other_space, locked_other_space),
);
}
} else {
for x in to_mark_set.into_iter() {
debug_assert_eq!(
*x.get_space_nonnull_mutex().as_ref().lock(),
this
);
if marked.insert(HashableAnyGc(x.0.clone_as_any())) {
marking_gc.insert(x);
}
}
}
} else {
let cap = marked.capacity();
let mut owned_marked = HashSet::new();
swap(&mut owned_marked, marked);
debug_assert_eq!(cap, owned_marked.capacity());
locked_this.state = AutoGcSpaceState::Sweep {
marked: owned_marked,
elements: locked_this
.elements
.iter()
.map(|x| HashableAnyGc(x.clone_as_any()))
.collect(),
}
}
}
AutoGcSpaceState::Sweep { marked, elements } => {
if let Some(x) = elements.pop_first() {
if !marked.contains(&x) {
debug_assert_eq!(
*x.get_space_nonnull_mutex().as_ref().lock(),
this
);
x.destory();
}
} else {
locked_this.state = AutoGcSpaceState::Mark {
marked: HashSet::new(),
marking_gc: BTreeSet::new(),
marking_root: locked_this
.roots
.iter()
.map(|x| HashableAnyRoot(x.clone_as_any()))
.collect(),
}
}
}
}
}
}
}
trait AnyRoot: GcTraverse {
fn clone_as_any(&self) -> Box<dyn AnyRoot>;
fn get_unit_rootinner_ptr(&self) -> NonNull<()>;
unsafe fn get_space_nonnull_mutex(&self) -> NonNull<Mutex<NonNull<AutoGcSpace>>>;
fn clone_as_gc_traverse(&self) -> Box<dyn GcTraverse>;
}
impl<T: Trace> GcTraverse for Root<T> {
fn gc_traverse(&self, tracer: &mut Tracer) {
self.deref().trace(tracer);
}
}
impl<T: Trace> AnyRoot for Root<T> {
fn clone_as_any(&self) -> Box<dyn AnyRoot> {
box Root {
ptr: self.ptr,
phantom: PhantomData,
}
}
fn clone_as_gc_traverse(&self) -> Box<dyn GcTraverse> {
box Root {
ptr: self.ptr,
phantom: PhantomData,
}
}
fn get_unit_rootinner_ptr(&self) -> NonNull<()> {
NonNull::cast(self.ptr)
}
unsafe fn get_space_nonnull_mutex(&self) -> NonNull<Mutex<NonNull<AutoGcSpace>>> {
let ptr = self.ptr;
let mut ptr = ptr;
NonNull::new_unchecked(&mut ptr.as_mut().space)
}
}
#[derive(Deref)]
struct HashableAnyRoot(Box<dyn AnyRoot>);
impl Hash for HashableAnyRoot {
fn hash<H: Hasher>(&self, state: &mut H) {
self.get_unit_rootinner_ptr().hash(state);
}
}
impl PartialEq for HashableAnyRoot {
fn eq(&self, other: &Self) -> bool {
self.get_unit_rootinner_ptr() == other.get_unit_rootinner_ptr()
}
}
impl Eq for HashableAnyRoot {}
impl Ord for HashableAnyRoot {
fn cmp(&self, other: &Self) -> Ordering {
self.get_unit_rootinner_ptr()
.cmp(&other.get_unit_rootinner_ptr())
}
}
impl PartialOrd for HashableAnyRoot {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
pub struct Root<T: Trace> {
ptr: NonNull<RootInner<T>>,
phantom: PhantomData<RootInner<T>>,
}
struct RootInner<T: Trace> {
space: Mutex<NonNull<AutoGcSpace>>,
data: T,
}
impl<T: Trace> Root<T> {
pub fn new(x: T) -> Self {
let ptr = Box::into_raw_non_null(box RootInner {
space: Mutex::new(Box::into_raw_non_null(box AutoGcSpace::new())),
data: x,
});
let result = Root {
ptr: ptr,
phantom: PhantomData,
};
unsafe {
ptr.as_ref()
.space
.lock()
.as_ref()
.add_root(result.clone_as_any());
}
result
}
pub fn try_marksweep_step(&self) {
unsafe {
if let Some(ptr) = {
let maybe_locked = self.ptr.as_ref().space.try_lock();
if let Some(ptr) = maybe_locked {
let result: NonNull<_> = *ptr;
Some(result)
} else {
None
}
} {
AutoGcSpace::try_marksweep_step(ptr);
}
}
}
}
impl<T: Trace> Deref for Root<T> {
type Target = T;
fn deref(&self) -> &Self::Target {
unsafe { &self.ptr.as_ref().data }
}
}
impl<T: Trace> Drop for Root<T> {
fn drop(&mut self) {
unsafe {
let space_ref_locked = self.ptr.as_ref().space.lock();
AutoGcSpace::remove_root_and_destory_if_empty(
*space_ref_locked,
&HashableAnyRoot(self.clone_as_any()),
);
}
}
}
}