/*
 * @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/.
 */

mod collect;
/**
 * This package contains the components for traversal definitions
 * and algorithms.
 *
 * Many traversal methods will take a Strategy as a parameter. In
 * many cases, the strategy CallStack will work for this, but there are
 * a few limitations described there.
 *
 * The rest of this class is supporting different sorts of traversals,
 * and configurable traversal state.
 */
pub mod traverse;
mod types;

pub use types::*;

use crate::entry::{Present, Spot};
use crate::types::{Error, HasIx, Ix, Root, Weak};
use alloc::vec::Vec;

impl<T> Region<T> {
    /**
     * Return the current capacity of this region. A collection won't
     * be triggered by allocation unless the desired amount exceeds the capacity.
     */
    #[inline]
    pub fn capacity(&self) -> usize {
        self.data.capacity()
    }
    /**
     * Return the current number of entries in the region.
     */
    #[inline]
    pub fn len(&self) -> usize {
        self.data.len()
    }
    /**
     * Returns true if there are currently no entries in this region.
     */
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.data.is_empty()
    }

    #[inline]
    #[allow(unused)]
    pub(crate) fn check_ix(&self, ix: Ix<T>) -> Result<(), Error> {
        #[cfg(feature = "debug-arena")]
        ix.check_nonce((self.nonce, self.generation))?;
        Ok(())
    }

    pub(crate) fn entry_raw_mut(&mut self, ix: Ix<T>) -> Entry<T> {
        let entry = self.data.get_mut(ix.ix()).unwrap();
        Entry {
            ix,
            present: entry.get_mut().unwrap(),
            roots: &self.roots,
        }
    }

    pub(crate) fn entry(&self, ix: Ix<T>) -> Result<Present<T>, Error> {
        self.check_ix(ix)?;
        let entry = self
            .data
            .get(ix.ix())
            // correct region and generation, but invalid index
            .ok_or(Error::Indeterminable)?;
        Ok(entry.get().ok_or(Error::UnexpectedInternalState)?)
    }

    pub(crate) fn weak(&self, ix: Ix<T>) -> Result<Weak<T>, Error> {
        self.check_ix(ix)?;
        Ok(self.entry(ix)?.weak(ix))
    }

    pub(crate) fn root(&self, ix: Ix<T>) -> Result<Root<T>, Error> {
        self.check_ix(ix)?;
        let e = self.entry(ix)?;
        let r = e.root(ix);
        // there will be two copies of the roots,
        // there is a strong reference inside the entry
        // and one in this method.
        // The entry will handle clearing its version if there
        // are no weak references

        // This is one copy, so it's already in the vec
        // only this method considers it already rooted
        if !r.is_otherwise_rooted() {
            // new root, push to list
            self.roots.borrow_mut().push(r.clone());
        }
        Ok(r)
    }

    pub(crate) fn try_get_mut(&mut self, ix: Ix<T>) -> Result<&mut T, Error> {
        self.check_ix(ix)?;
        let entry = self.data.get_mut(ix.ix()).ok_or(Error::Indeterminable)?;
        let present = entry.get_mut().ok_or(Error::UnexpectedInternalState)?;
        Ok(present.get_mut())
    }

    pub(crate) fn try_get(&self, ix: Ix<T>) -> Result<&T, Error> {
        self.check_ix(ix)?;
        let entry = self.data.get(ix.ix()).ok_or(Error::Indeterminable)?;
        let present = entry.get().ok_or(Error::UnexpectedInternalState)?;
        Ok(present.get())
    }
}

impl<T: 'static + HasIx<T>> Region<T> {
    /**
     * Ensure that the capacity supports new_elems more
     * elements, collecting garbage if necessary.
     */
    // Note for future reference. This is called while
    // some entries are marked, for cloning, so this
    // can't interact with marks
    pub fn ensure(&mut self, additional: usize) {
        let len = self.data.len();
        let cap = self.data.capacity();
        if cap >= len + additional {
            return;
        }
        let mut dst = Vec::with_capacity(len + core::cmp::max(len, additional));

        #[cfg(feature = "debug-arena")]
        let new_gen = (self.nonce, self.generation + 1);

        let roots = self.roots.get_mut();
        Self::prim_gc_to(
            &mut self.data,
            &mut dst,
            roots,
            #[cfg(feature = "debug-arena")]
            (self.nonce, self.generation),
            #[cfg(feature = "debug-arena")]
            new_gen,
        );
        *roots = roots.drain(..).filter(Root::is_otherwise_rooted).collect();
        self.data = dst;

        #[cfg(feature = "debug-arena")]
        {
            self.generation = new_gen.1;
        }
    }

    /**
     * Allocate a new object, returning a temporary handle,
     * which can be used to mutate the object and to get
     * roots, weak pointers, and internal pointers to
     * the object.
     *
     * This may trigger a garbage collection and invalidate
     * raw indices.  As such, a function is used to
     * generate the new value, which
     * can query the state of the world post-collection.
     */
    pub fn alloc<F>(&mut self, make_t: F) -> Entry<T>
    where
        F: FnOnce(&Self) -> T,
    {
        //else the index could be incorrect
        self.ensure(1);
        let n = self.data.len();
        self.data.push(Spot::new(make_t(&self)));
        self.entry_raw_mut(Ix::new(
            n,
            #[cfg(feature = "debug-arena")]
            self.nonce,
            #[cfg(feature = "debug-arena")]
            self.generation,
        ))
    }

    /**
     * Immediately trigger a standard garbage collection.
     *
     * This invalidates raw indices.
     *
     * ```rust
     * use moving_gc_arena as gc;
     * let mut r = gc::Region::new();
     *
     * r.alloc(|_|{()});
     * r.gc();
     * assert!(r.is_empty());
     * ```
     */
    pub fn gc(&mut self) {
        let mut dst = Vec::with_capacity(self.data.len());
        let roots = self.roots.get_mut();
        Self::prim_gc_to(
            &mut self.data,
            &mut dst,
            roots,
            #[cfg(feature = "debug-arena")]
            (self.nonce, self.generation),
            #[cfg(feature = "debug-arena")]
            (self.nonce, self.generation + 1),
        );
        let new_roots = self.take_valid_roots().collect();
        self.roots.replace(new_roots);
        self.data = dst;
        #[cfg(feature = "debug-arena")]
        {
            self.generation = self.generation + 1;
        }
    }
    /**
     * Move the elements of this region onto the end of another Region.
     * This can trigger a collection in the other region if it
     * must be re-allocated.
     */
    pub fn gc_into(mut self, other: &mut Region<T>) {
        other.ensure(self.data.len());
        Self::prim_gc_to(
            &mut self.data,
            &mut other.data,
            self.roots.get_mut(),
            #[cfg(feature = "debug-arena")]
            (self.nonce, self.generation),
            #[cfg(feature = "debug-arena")]
            (other.nonce, other.generation),
        );
        other.roots.get_mut().extend(self.take_valid_roots());
    }
    fn take_valid_roots(&mut self) -> impl Iterator<Item = Root<T>> + '_ {
        self.roots
            .get_mut()
            .drain(..)
            .filter(Root::is_otherwise_rooted)
    }

    #[inline(always)]
    /**
     * Traverse all reachable objects, applying a mutating function
     * to each of the values passed over in pre-order.
     *
     * The traverse::CallStack startegy can be used with any type
     * whatsoever, and produces a depth-first search using the
     * indices provided by HasIx::foreach_ix.
     *
     * In order to ensure that this function performs well, the
     * HasIx implementation for T must be deterministic: it
     * should always return the same references. This is so
     * that we can correctly maintain marking information.
     *
     * There is no immutable implementation of this function,
     * as it relies on unique access to object headers
     * (but in exchange, requires no allocations).
     */
    pub fn traverse<'a, I, Strategy, Pre, Post>(
        &'a mut self,
        strategy: Strategy,
        start: I,
        pre: Pre,
        post: Post,
    ) where
        T: HasIx<T>,
        Pre: FnMut(Entry<T>),
        Post: FnMut(Entry<T>),
        Strategy: traverse::Strategy<T, traverse::PreAndPost>,
        Strategy: traverse::Strategy<T, traverse::PreOnly>,
        I: IntoIterator<Item = &'a Ix<T>>,
        I::IntoIter: Clone,
    {
        Self::traverse_base::<_, _, traverse::PreAndPost, _>(
            strategy,
            &mut self.data,
            start.into_iter(),
            &self.roots,
            traverse::PrePostVisitor { pre, post },
            #[cfg(feature = "debug-arena")]
            (self.nonce, self.generation),
        )
    }

    /**
     * Provides a more general state than traverse. This allows
     * a specialized strategy to provide visitors beyond the
     * simple pre- and post-actions provided by a blind DFS.
     *
     * ```
     * use moving_gc_arena::{traverse, Region, Entry};
     *
     * let mut r = Region::new();
     * let mut count = 0;
     * let r1 = r.alloc(|_| ()).root();
     *
     * // Annotations are usually needed when
     * // constructing generic visitors
     * let visitor = traverse::PrePostVisitor {
     *   pre: |_: Entry<_>| { count += 1 },
     *   post: ()
     * };
     * r.traverse_with(traverse::CallStack, &[r1.ix()], visitor);
     *
     * assert_eq!(count, 1);
     * ```
     */
    pub fn traverse_with<'a, I, Strategy, State, Visit>(
        &'a mut self,
        strategy: Strategy,
        start: I,
        visitor: Visit,
    ) where
        T: HasIx<T>,
        Strategy: traverse::Strategy<T, State>,
        Strategy: traverse::Strategy<T, traverse::PreOnly>,
        Visit: traverse::Visitor<T, State>,
        I: IntoIterator<Item = &'a Ix<T>>,
        I::IntoIter: Clone,
    {
        Self::traverse_base::<_, _, State, _>(
            strategy,
            &mut self.data,
            start.into_iter(),
            &self.roots,
            visitor,
            #[cfg(feature = "debug-arena")]
            (self.nonce, self.generation),
        )
    }

    #[deprecated(
        since = "0.3.0",
        note = "Use Region::traverse with traverse::CallStack instead"
    )]
    pub fn dfs_mut_cstack<'a, I, F>(&'a mut self, start: I, pre: F)
    where
        T: HasIx<T>,
        F: FnMut(Entry<T>),
        I: IntoIterator<Item = &'a Ix<T>>,
        I::IntoIter: Clone,
    {
        self.traverse(traverse::CallStack, start, pre, |_| {});
    }

    /**
     * Create a deep clone of the object subgraph starting at a particular root.
     * Instead of using a standard Clone implementation, any clone function may be used.
     *
     * This method assumes that the size of the graph reachable will not change. If the
     * clone function does change it, then enough space for the result must be reserved
     * to avoid panics or leaks.
     */
    pub fn deep_clone_with<F>(&mut self, mut start: Root<T>, do_clone: F) -> Root<T>
    where
        F: FnMut(Entry<T>) -> T,
    {
        #[allow(deprecated)]
        Self::deep_clone_with_mut(self, &mut start, do_clone);
        start
    }

    /**
     * As dep_clone_with, but cloning into a different Region
     */
    pub fn deep_clone_into_with<F>(
        &mut self,
        other: &mut Region<T>,
        mut start: Root<T>,
        do_clone: F,
    ) -> Root<T>
    where
        F: FnMut(Entry<T>) -> T,
    {
        #[allow(deprecated)]
        Self::deep_clone_into_with_mut(self, other, &mut start, do_clone);
        start
    }

    #[deprecated(since = "0.3.0", note = "Use Region::deep_clone_with instead")]
    pub fn deep_clone_with_mut<F>(&mut self, start: &mut Root<T>, do_clone: F)
    where
        F: FnMut(Entry<T>) -> T,
    {
        self.prim_clone_cstack_into(traverse::CallStack, None, start, do_clone);
    }

    #[deprecated(since = "0.3.0", note = "Use Region::deep_clone_into_with instead")]
    pub fn deep_clone_into_with_mut<F>(
        &mut self,
        other: &mut Region<T>,
        start: &mut Root<T>,
        do_clone: F,
    ) where
        F: FnMut(Entry<T>) -> T,
    {
        self.prim_clone_cstack_into(traverse::CallStack, Some(other), start, do_clone);
    }
}

impl<T: 'static + HasIx<T> + Clone> Region<T> {
    /**
     * Create a deep clone of the object subgraph starting at a particular root.
     * Each T instance which is reachable from this root object will be cloned
     * exactly once, and all connections will be preserved. Each cloned object points
     * only at cloned objects, and each original object points only at original objects.
     *
     * Currently, the method of traversal is not yet configurable and always uses
     * the CallStack, as special functionality is needed for this method beyond
     * the normal traverse strategies.
     */
    pub fn deep_clone(&mut self, mut start: Root<T>) -> Root<T> {
        self.prim_clone_cstack_into(traverse::CallStack, None, &mut start, |e| e.get().clone());
        start
    }

    /**
     * As deep_clone, but clones entries into a different Region.
     */
    pub fn deep_clone_into(&mut self, other: &mut Region<T>, mut start: Root<T>) -> Root<T> {
        self.prim_clone_cstack_into(traverse::CallStack, Some(other), &mut start, |e| {
            e.get().clone()
        });
        start
    }
}