/*
 * @Copyright 2020 Jason Carr
 *
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
 */

#![doc(html_root_url = "https://docs.rs/moving_gc_arena/0.2.4")]
#![no_std]

#[allow(unused_imports)]
#[macro_use] // vec! in tests
extern crate alloc;

mod types;
#[cfg(feature = "debug-arena")]
mod nonce;
mod entry;
mod region;

pub use types::{Ix, Weak, Error, HasIx, Root};
pub use region::{Region, MutEntry};

impl <T> Ix<T> {
    /**
     * If this crate has been compiled with support for validity checking,
     * this method will verify that an index is valid. In such cases,
     * a result of Ok indicates that this index points to a valid location
     * in the given region and has been updated.
     *
     * Otherwise, Ok will always be returned.
     */
    pub fn check_region(self, region: &Region<T>) -> Result<(), Error> {
        region.check_ix(self)
    }
    /**
     * Get the value pointd to by this index in its corresponding region.
     *
     * If the region is incorrect, the behavior of this function is
     * unspecified, and it may panic (but may also return a valid T reference).
     * Use try_get to avoid panics.
     */
    #[inline]
    pub fn get(self, region: &Region<T>) -> &T {
        self.try_get(region).expect("Ix::get")
    }
    #[inline]
    pub fn get_mut(self, region: &mut Region<T>) -> &mut T {
        self.try_get_mut(region).expect("Ix::get_mut")
    }
    #[inline]
    pub fn try_get(self, region: &Region<T>) -> Result<&T, Error> {
        region.try_get(self)
    }
    #[inline]
    pub fn try_get_mut(self, region: &mut Region<T>) -> Result<&mut T, Error> {
        region.try_get_mut(self)
    }

    #[inline]
    pub fn root(self, region: &Region<T>) -> Root<T> {
        self.try_root(region).unwrap()
    }
    #[inline]
    pub fn weak(self, region: &Region<T>) -> Weak<T> {
        self.try_weak(region).unwrap()
    }
    #[inline]
    pub fn try_root(self, region: &Region<T>) -> Result<Root<T>, Error> {
        region.root(self)
    }
    #[inline]
    pub fn try_weak(self, region: &Region<T>) -> Result<Weak<T>, Error> {
        region.weak(self)
    }
}

impl <T> Weak<T> {
    /**
     * Gets the value at this location, when
     * passed the correct region. As with Ix,
     * the behavior when the region or location is
     * unspecified (but is still safe).
     */
    #[inline]
    pub fn get<'a>(&self, r: &'a Region<T>) -> &'a T {
        self.try_get(r).unwrap()
    }
    #[inline]
    pub fn get_mut<'a>(&self, r: &'a mut Region<T>) -> &'a mut T {
        self.try_get_mut(r).unwrap()
    }
    /**
     * Try to get a reference to this data, possibly returning an error.
     *
     * If the region is correct, then an error always indicates that the pointed-to
     * entry is no longer valid
     */
    #[inline]
    pub fn try_get<'a>(&self, r: &'a Region<T>) -> Result<&'a T, Error> {
        match self.ix() {
            Some(i) => i.try_get(r),
            None => Err(Error::EntryExpired)
        }
    }
    #[inline]
    pub fn try_get_mut<'a>(&self, r: &'a mut Region<T>) -> Result<&'a mut T, Error> {
        match self.ix() {
            Some(i) => i.try_get_mut(r),
            None => Err(Error::EntryExpired)
        }
    }


    #[inline(always)]
    pub fn root(self) -> Root<T> {
        self.try_root().unwrap()
    }
    #[inline(always)]
    pub fn try_root(&self) -> Result<Root<T>, Error> {
        Ok(Root {
            cell: self.cell.upgrade().ok_or(Error::EntryExpired)?
        })
    }
}


#[cfg(test)]
mod tests {
    use super::{Ix, Root, Region, HasIx};
    use core::mem::drop;
    use alloc::vec::Vec;

    #[derive(Debug)]
    struct Elem {
        ix: Vec<Ix<Elem>>,
    }
    impl Elem {
        pub fn new() -> Self {
            Elem { ix: vec![] }
        }
    }
    impl HasIx<Elem> for Elem {
        fn foreach_ix<'b, 'a : 'b, F>(&'a mut self, f: F) where
            F: FnMut(&'b mut Ix<Elem>)
        {
            self.ix.iter_mut().for_each(f)
        }
    }
    impl Default for Elem {
        fn default() -> Self { Self::new() }
    }

    #[test]
    pub fn weaks_are_weak() {
        let mut r = Region::new();
        let w1 = r.alloc(|_| {Elem::new()}).weak();

        let e2 = r.alloc(|_| {Elem::new()});
        let w2 = e2.weak();
        let r2 = e2.root();

        r.gc();
        let w3 = r.alloc(|_| {Elem::new()}).weak();

        // first is collected by now
        assert!(w1.try_get(&r).is_err());

        // root and new version are both accessible
        assert!(w2.try_get(&r).is_ok());
        assert!(w3.try_get(&r).is_ok());

        // touch r
        drop(r2);
    }

    #[test]
    pub fn roots_are_root() {
        let mut r = Region::new();
        let e1 = r.alloc(|_| {Elem::new()});
        let w1 = e1.weak();
        let r1 = e1.root();
        let r2 = r.alloc(|_| {Elem::new()}).root();
        drop(r1);
        r.gc();

        //r1 should have stopped being root on drop
        assert!(w1.try_get(&r).is_err());

        //r2 is still a root
        assert!(r2.try_get(&r).is_ok());
    }

    #[test]
    pub fn indirect_correct() {
        let mut r = Region::new();

        let e1 = r.alloc(|_| {Elem::new()});
        let w1 = e1.weak();
        let r1 = e1.root();
        let r2 = r.alloc(|_| {Elem {ix: vec![r1.ix()]}}).root();
        drop(r1);

        let mut e3 = r.alloc(|_| {Elem::new()});
        e3.get_mut().ix = vec![e3.ix()];
        let w3 = e3.weak();

        let r4 = r.alloc(|_| {Elem::new()}).root();
        let w5 = r.alloc(|_| {Elem::new()}).weak();

        r4.get_mut(&mut r).ix = vec![w5.ix().unwrap()];
        w5.get_mut(&mut r).ix = vec![r4.ix()];

        //nothing changed with r4 and w5 during access
        assert!(r4.try_get(&r).is_ok());
        assert!(w5.try_get(&r).is_ok());
        drop(r4);

        r.gc();

        //entries 1 and 2 are still good.
        assert!(match w1.try_get(&r) {
            Ok(Elem { ix: s }) => s.is_empty(),
            x => panic!("{:?}", x),
        });
        assert!(match r2.try_get(&r) {
            Ok(Elem { ix: s }) => !s.is_empty(),
            x => panic!("{:?}", x),
        });

        // entries 3, 4 and 5 should be collected
        // despite cycles
        assert!(w3.try_get(&r).is_err());
        assert!(w5.try_get(&r).is_err());

    }

    #[test]
    pub fn upgrades_well_behaved() {
        let mut r = Region::new();

        let e1 = r.alloc(|_| {Elem::new()});
        let r1 = e1.root();
        let w1 = e1.weak();
        let r2 = r.alloc(|_| {Elem {ix: vec![r1.ix()]}}).root();
        let w2 = r2.weak();
        drop(r1);

        r.gc();

        let r1 = r2.get(&r).ix[0].root(&r);
        drop(r2);
        r.gc();

        // the new root for 1 is still valid
        assert!(r1.try_get(&r).is_ok());
        assert!(w1.try_get(&r).is_ok());
        // but the old location is gone
        assert!(w2.try_get(&r).is_err());
        assert!(r.len() == 1);
        drop(w1);

        // re-create root from ix,
        // dropping the old one
        let r1_ = r1.ix().root(&r);
        drop(r1);
        let r1 = r1_;
        r.gc();
        let w1 = r1.ix().weak(&r);
        assert!(w1.try_get(&r).is_ok());

        // re-create weak from ix,
        // don't gc
        let i1 = r1.ix();
        drop(r1);
        let w1 = i1.weak(&r);

        // new weak is valid for live location
        assert!(w1.try_get(&r).is_ok());
        r.gc();
        // still weak on the location,
        assert!(w1.try_get(&r).is_err());

        // nothing allocated in r now
        assert!(r.is_empty());
    }

    #[test]
    pub fn check_impls() {

        struct Anything;

        #[derive(Debug)]
        struct Debugged;

        use crate::types::{Error, Weak, Root, Ix};
        use crate::region::{Region, MutEntry};
        use core::fmt::{Debug, Display};
        fn is_send<T: Send>(){}
        fn is_sync<T: Sync>(){}
        fn is_debug<T: Debug>(){}
        fn is_display<T: Display>(){}
        fn is_eq<T: Eq>(){}

        is_send::<Error>();
        is_sync::<Error>();
        is_debug::<Error>();
        is_display::<Error>();
        // Unfortunately we can't implement
        // std::error::Error until it's
        // available for no_std

        is_debug::<Root<Anything>>();
        is_debug::<Weak<Anything>>();
        is_debug::<Ix<Anything>>();
        is_debug::<Region<Debugged>>();
        is_debug::<MutEntry<Debugged>>();

        is_eq::<Ix<Anything>>();
        is_eq::<Weak<Anything>>();
        is_eq::<Root<Anything>>();

        is_send::<Ix<Anything>>();
        is_sync::<Ix<Anything>>();
    }

    #[cfg(all(feature = "packed-headers", not(feature="debug-arena")))]
    #[test]
    pub fn header_ix_layout_same() {
        use alloc::alloc::Layout;
        use crate::entry::Spot;
        assert!(
            Layout::new::<Ix<()>>() ==
            Layout::new::<Spot<()>>());
        let mut ix: Ix<()> = Ix::new(0);
        let ix2 = ix;
        unsafe {
            // mostly for testing with miri
            let mut s = Spot::new(());

            core::mem::swap(s.header_as_ix(), &mut ix);
            core::mem::swap(s.header_as_ix(), &mut ix);

            assert!(ix.identifier() == ix2.identifier());
        }
    }

    #[test]
    pub fn traverse_sound() {

        fn make_triangle(r: &mut Region<Elem>) -> [Root<Elem>; 3] {
            let r1 = r.alloc(|_|{ Default::default() }).root();
            let r2 = r.alloc(|_|{ Default::default() }).root();
            let r3 = r.alloc(|_|{ Default::default() }).root();

            r1.get_mut(r).ix.push(r2.ix());
            r2.get_mut(r).ix.push(r3.ix());
            r3.get_mut(r).ix.push(r1.ix());
            [r1, r2, r3]
        }
        fn component_size(r: &mut Region<Elem>, start: Root<Elem>) -> usize {
            let mut c = 0;
            r.dfs_mut_cstack(&[start.ix()], |_, _| {c += 1});
            c
        }
        let mut r = Region::new();

        let r1 = make_triangle(&mut r)[0].clone();
        let r2 = make_triangle(&mut r)[0].clone();

        // self loop for extra soundness testing
        r1.get_mut(&mut r).ix.push(r1.ix());

        let r3 = r.alloc(|_|{ Elem { ix: vec![r1.ix(), r2.ix()] }}).root();


        assert!(3 == component_size(&mut r, r1.clone()));
        assert!(7 == component_size(&mut r, r3.clone()));
        assert!(3 == component_size(&mut r, r2.clone()));

        r2.get_mut(&mut r).ix.push(r3.ix());

        // cause a GC for extra noise
        let rs = make_triangle(&mut r);
        core::mem::drop(rs);
        r.gc();

        assert!(3 == component_size(&mut r, r1));
        assert!(7 == component_size(&mut r, r3));
        // we just made r2 -> r3
        assert!(7 == component_size(&mut r, r2));

    }
}