//#![no_std] // https://github.com/sgrif/derive_deref/pull/9
#![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) };
        };
    }
}

/// Derefing Gc is unsafe. Auto marksweep.
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
        }
    }
}

/// Anything is manual and unsafe.
pub mod libbare {
    use super::*;
    pub struct Tracer<'a>(Box<dyn FnMut(Box<dyn AnyGc>) + 'a>);
    pub trait Trace: 'static {
        /// Define how to visit values referred by this value.
        ///
        /// For example, if `self.x` is a value referred by `self`,
        /// call `self.x.trace(tracer)` to visit it.
        ///
        /// The values that are visited must match the `Drop::drop`
        /// implementation. Otherwise memory leak or panic might
        /// happen. After the panic, dereferencing already collected
        /// `Cc<T>` can trigger:
        /// - Undefined behavior on release build.
        /// - Another panic on debug build.
        ///
        /// Ideally this can be generated by the compiler, since the
        /// compiler already knows how to generate `Drop::drop`.
        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);
    }
    /// Type-erased `Gc<T>` needed by GC.
    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(),
                            }
                        }
                    }
                }
            }
        }
    }
    /// Type-erased `Root<T>` needed by GC.
    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()),
                );
            }
        }
    }
}