graph_safe_compare 0.2.1

pub use premade::*;

pub mod equiv_classes;


mod premade
{
    /// The primary variation of the algorithm, like that of the paper.
    pub mod precheck_interleave
    {
        #[allow(unreachable_pub)]
        mod sealed
        {
            use {
                super::{
                    super::super::equiv,
                    errors::{
                        InterleaveError,
                        PrecheckError,
                    },
                    Params,
                },
                crate::{
                    basic::modes::limited::Limited,
                    cycle_safe::modes::interleave::Interleave,
                    Node,
                },
                core::marker::PhantomData,
            };

            pub struct PrecheckArgs<N, P>(PhantomData<(N, P)>);

            impl<N: Node, P: Params<N>> equiv::Params for PrecheckArgs<N, P>
            {
                type DescendMode = Limited<u16>;
                type Error = PrecheckError<P::Error>;
                type Node = N;
                type RecurMode = P::PrecheckRecurMode;
            }

            pub struct InterleaveArgs<N, P>(PhantomData<(N, P)>);

            impl<N: Node, P: Params<N>> equiv::Params for InterleaveArgs<N, P>
            {
                type DescendMode = Interleave<P::InterleaveParams>;
                type Error = InterleaveError<P::Error>;
                type Node = N;
                type RecurMode = P::InterleaveRecurMode;
            }
        }

        mod errors
        {
            #[cfg(doc)]
            use super::super::precheck_interleave;
            use crate::{
                anticipated_or_like::Infallible,
                basic::modes::limited::LimitReached,
            };

            /// Variants of errors that can occur while doing a precheck.
            #[allow(clippy::exhaustive_enums)]
            pub enum PrecheckError<E>
            {
                /// [`LimitReached`] occurred.  Abort the precheck.
                LimitReached,
                /// The [`precheck_interleave::Params::PrecheckRecurMode`] errored.
                RecurError(E),
            }

            impl<E> From<LimitReached> for PrecheckError<E>
            {
                #[inline]
                fn from(_: LimitReached) -> Self
                {
                    PrecheckError::LimitReached
                }
            }

            impl<E> From<Infallible> for PrecheckError<E>
            {
                #[inline]
                fn from(_: Infallible) -> Self
                {
                    #![allow(clippy::unreachable)] // Truly unreachable.
                    unreachable!()
                }
            }

            /// The [`precheck_interleave::Params::InterleaveRecurMode`] errored while doing an
            /// interleave.
            #[allow(clippy::exhaustive_structs)]
            pub struct InterleaveError<E>(pub E);

            impl<E> From<Infallible> for InterleaveError<E>
            {
                #[inline]
                fn from(_: Infallible) -> Self
                {
                    #![allow(clippy::unreachable)] // Truly unreachable.
                    unreachable!()
                }
            }
        }

        pub use errors::{
            InterleaveError,
            PrecheckError,
        };
        use {
            super::super::equiv::{
                Equiv,
                RecurMode,
            },
            crate::{
                basic::modes::limited::Limited,
                cycle_safe::modes::interleave,
                Node,
            },
            sealed::{
                InterleaveArgs,
                PrecheckArgs,
            },
        };


        /// Generic parameters of [`equiv`].
        pub trait Params<N: Node>: Sized
        {
            /// Type of recursion mode for the precheck.
            type PrecheckRecurMode: RecurMode<PrecheckArgs<N, Self>>
                + Into<Self::InterleaveRecurMode>;
            /// Type of recursion mode for the interleave.
            type InterleaveRecurMode: RecurMode<InterleaveArgs<N, Self>>;
            /// Type that `impl`s the arguments for the generic parameters for the interleave.
            type InterleaveParams: interleave::Params<Node = N>;
            /// Type that represents the errors that can occur from [`Self::PrecheckRecurMode`]
            /// and [`Self::InterleaveRecurMode`].
            type Error;
        }

        /// Equivalence predicate that can handle cyclic graphs, but first tries the precheck that
        /// is faster for small acyclic graphs, and that requires choosing specific type arguments
        /// that determine the implementations of internal dynamic data structures.  Safe for
        /// very-deep graphs only when the interleave recursion-mode type is.
        ///
        /// # Errors
        /// If the [`P::PrecheckRecurMode`](Params::PrecheckRecurMode) or
        /// [`P::InterleaveRecurMode`](Params::InterleaveRecurMode) error, return an `Err` with
        /// a [`P::Error`](Params::Error) that represents the error.
        #[inline]
        pub fn equiv<N, P>(
            a: N,
            b: N,
        ) -> Result<N::Cmp, P::Error>
        where
            N: Node + Clone,
            P: Params<N>,
        {
            use interleave::Params as _;

            let mut e =
                Equiv::<PrecheckArgs<N, P>>::new(Limited(P::InterleaveParams::PRECHECK_LIMIT));

            match e.equiv(a.clone(), b.clone()) {
                Ok(cmp) => Ok(cmp),
                Err(PrecheckError::RecurError(e)) => Err(e),
                Err(PrecheckError::LimitReached) => {
                    let mut e: Equiv<InterleaveArgs<N, P>> = e.into();
                    e.equiv(a, b).map_err(|InterleaveError(error)| error)
                },
            }
        }
    }
}


mod modes
{
    use super::equiv::Params;

    /// Controls if node edges are descended into.
    pub trait DescendMode<P: Params>
    {
        /// Type of error that can occur.
        type Error: Into<P::Error>;

        /// Controls if all the descendents of a pair of nodes being compared should be
        /// immediately skipped.
        ///
        /// Returning `true` causes all the descendents to begin to be compared, individually
        /// under the control of [`Self::do_traverse`].
        ///
        /// Returning `false` causes all the descendents to be skipped, and assumes they are
        /// already known to satisfy equivalence with their counterparts, and causes the
        /// comparison traversal to immediately continue on to the next non-descendent
        /// (i.e. sibling or ancestor) nodes.
        ///
        /// # Errors
        /// Returning `Err` causes the invocation of the algorithm to abort early and immediately
        /// return the converted error.
        fn do_edges(
            &mut self,
            a: &P::Node,
            b: &P::Node,
        ) -> Result<bool, Self::Error>;

        /// Controls if each node-counterparts will be traversed.
        ///
        /// Returning `true` causes the next counterparts to be compared.
        ///
        /// Returning `false` causes them to be skipped, and assumes they are already known to
        /// satisfy equivalence, and causes the comparison traversal to immediately continue on to
        /// the next nodes.
        ///
        /// # Errors
        /// Returning `Err` causes the invocation of the algorithm to abort early and immediately
        /// return the converted error.
        fn do_traverse(&mut self) -> Result<bool, Self::Error>;
    }
}


mod recursion
{
    use {
        super::equiv::{
            EdgesIter,
            Equiv,
            Params,
        },
        crate::Node,
    };

    /// [`Node`]s at the same position in the input graphs to compare.
    pub type Counterparts<N> = [N; 2];
    /// `Ok` when there are [`Counterparts`] descendents from ancestors.  `Err` when ancestors do
    /// not have the same amount of edges.
    pub type CounterpartsResult<N> = Result<Counterparts<N>, <N as Node>::Cmp>;

    /// Abstraction of recursion continuations.
    pub trait RecurMode<P: Params>: Default
    {
        /// Type of error that can occur.
        type Error: Into<P::Error>;

        /// Arrange for the given nodes to be recurred on, either immediately or later.
        ///
        /// The `it` parameter enables accessing the entire [`Equiv`] value.
        ///
        /// When recurred on immediately, the result must be that of comparing the given nodes
        /// (`Ok`) or attempting to (`Err`).  When saved for later, the result must be `Ok(cmp)`
        /// where `cmp.is_equiv()` is true, and [`Self::next`] must supply these nodes at some
        /// point, or the result must be `Err` if an error occurred.
        ///
        /// Returning `Ok(cmp)` where `cmp.is_equiv()` is false causes the invocation of the
        /// algorithm to immediately return `cmp` that represents inequivalence.
        ///
        /// # Errors
        /// Returning `Err` causes the invocation of the algorithm to abort early and immediately
        /// return the converted error.
        fn recur(
            it: &mut Equiv<P>,
            edges_iter: EdgesIter<P::Node>,
        ) -> Result<<P::Node as Node>::Cmp, Self::Error>;

        /// Supply the next counterpart nodes for the algorithm to compare, if any were saved for
        /// later by [`Self::recur`].
        ///
        /// # Errors
        /// If there are not the same amount of counterparts (i.e. their ancestor nodes have
        /// different amounts of edges), then `Err(cmp)` indicates which ancestor has less.
        fn next(&mut self) -> Option<CounterpartsResult<P::Node>>;

        /// Reset to be empty while preserving capacity, if relevant.
        ///
        /// An aborted precheck, that uses particular types of recursion-modes, might leave some
        /// elements on such a structure, in which case it needs to be reset before doing the
        /// interleave using the same structure.
        ///
        /// Also, some things that take ownership of a `Self` might call this to ensure a
        /// structure is in a fresh state.
        ///
        /// When it is more efficient, the `self` value should be reset and then returned.  But a
        /// newly-created value may be returned if desired.
        #[must_use]
        fn reset(self) -> Self;
    }
}


mod edges_iter
{
    use {
        super::recursion::{
            Counterparts,
            CounterpartsResult,
        },
        crate::{
            utils::NonAdvancingIterator,
            Cmp as _,
            Node,
            Step,
        },
        cfg_if::cfg_if,
        core::cmp::Ordering,
    };

    /// [`Node::Index`] types must give their "zero" value, for their implementation of
    /// [`Default`].
    fn zero<T: Default>() -> T
    {
        T::default()
    }

    /// Get edges lazily, in increasing-index order.
    ///
    /// Enables avoiding consuming excessive space for `RecurMode` types like `RecurStack` and
    /// `RecurQueue`.
    pub struct EdgesIter<N: Node>
    {
        pub(super) counterparts: Counterparts<N>,
        next_index:              Option<N::Index>,
    }

    impl<N: Node> EdgesIter<N>
    {
        /// Prepare to get the edges from `counterparts`.
        pub(super) fn new(counterparts: Counterparts<N>) -> Self
        {
            Self { counterparts, next_index: Some(zero()) }
        }

        fn get_next(
            &mut self,
            advance: bool,
        ) -> Option<<Self as Iterator>::Item>
        {
            if let Some(i) = &self.next_index {
                let [a, b] = &self.counterparts;
                match [a.get_edge(i), b.get_edge(i)] {
                    [Some(ae), Some(be)] => {
                        if advance {
                            self.next_index = increment_index(i);
                        }
                        Some(Ok([ae, be]))
                    },
                    [None, None] => {
                        if advance {
                            self.next_index = None;
                        }
                        None
                    },
                    [None, Some(_)] => Some(Err(N::Cmp::from_ord(Ordering::Less))),
                    [Some(_), None] => Some(Err(N::Cmp::from_ord(Ordering::Greater))),
                }
            }
            else {
                None
            }
        }
    }

    impl<N: Node> Iterator for EdgesIter<N>
    {
        type Item = CounterpartsResult<N>;

        #[inline]
        fn next(&mut self) -> Option<Self::Item>
        {
            self.get_next(true)
        }
    }

    impl<N: Node> NonAdvancingIterator for EdgesIter<N>
    {
        fn next_no_adv(&mut self) -> Option<Self::Item>
        {
            self.get_next(false)
        }
    }

    fn increment_index<T: Step>(i: &T) -> Option<T>
    {
        cfg_if! {
            if #[cfg(feature = "anticipate")] {
                Step::forward_checked(i.clone(), 1)
            }
            else {
                i.increment()
            }
        }
    }
}


/// The central parts of the algorithm.
pub mod equiv
{
    pub use super::{
        edges_iter::EdgesIter,
        modes::DescendMode,
        recursion::{
            Counterparts,
            CounterpartsResult,
            RecurMode,
        },
    };
    use crate::{
        utils::NonAdvancingIterator as _,
        Cmp,
        Node,
    };

    /// Generic parameters of [`Equiv`] and its operations.
    pub trait Params: Sized
    {
        /// Type of node to handle.
        type Node: Node;
        /// Type that controls descending node edges.
        type DescendMode: DescendMode<Self>;
        /// Type that provides recursion continuations.
        type RecurMode: RecurMode<Self>;
        /// Type that represents the errors that can occur from [`Self::DescendMode`] and
        /// [`Self::RecurMode`].
        type Error;
    }

    /// The state for an invocation of a variation of the algorithm.
    #[non_exhaustive]
    pub struct Equiv<P: Params>
    {
        /// Controls if node edges are descended into.
        pub(crate) descend_mode: P::DescendMode,
        /// Representation of recursion continuations.
        pub recur_mode:          P::RecurMode,
    }

    impl<P: Params> Equiv<P>
    {
        /// Create a new instance to use once for a single invocation of the algorithm.
        ///
        /// For use with [`DescendMode`] types that cannot implement `Default`.
        #[inline]
        pub fn new(descend_mode: P::DescendMode) -> Self
        {
            Self { descend_mode, recur_mode: P::RecurMode::default() }
        }
    }

    impl<P: Params> Default for Equiv<P>
    where P::DescendMode: Default
    {
        /// Create a new instance to use once for a single invocation of the algorithm.
        ///
        /// For use with [`DescendMode`] types that implement `Default`.
        #[inline]
        fn default() -> Self
        {
            Self {
                descend_mode: P::DescendMode::default(),
                recur_mode:   P::RecurMode::default(),
            }
        }
    }

    /// Enables the same recursion-mode value to be reused across the precheck and the interleave,
    /// which is more efficient for some types since this avoids dropping it and creating another.
    ///
    /// [`From`] or [`Into`] cannot be `impl`ed for this, because that would conflict with the
    /// blanket implementations provided by the `core` library.
    impl<PT: Params> Equiv<PT>
    where PT::DescendMode: Default
    {
        /// Like [`From::from`].
        #[inline]
        pub fn from<PF: Params>(e: Equiv<PF>) -> Self
        where PF::RecurMode: Into<PT::RecurMode>
        {
            Self {
                descend_mode: PT::DescendMode::default(),
                recur_mode:   e.recur_mode.reset().into(),
            }
        }
    }

    impl<PF: Params> Equiv<PF>
    {
        /// Like [`Into::into`].
        #[inline]
        pub fn into<PT: Params>(self) -> Equiv<PT>
        where
            PF::RecurMode: Into<PT::RecurMode>,
            PT::DescendMode: Default,
        {
            Equiv::from(self)
        }
    }

    /// The primary logic of the algorithm.
    ///
    /// This generic design works with the [`Node`], [`DescendMode`], and [`RecurMode`] traits to
    /// enable variations.
    impl<P: Params> Equiv<P>
    {
        /// The entry-point of the algorithm.
        ///
        /// Returns `Ok` with a value that represents the result of comparison, according to the
        /// trait implementations that define the variation of the logic.
        ///
        /// # Errors
        /// If a [`DescendMode`] or [`RecurMode`] method gives an error, returns that error
        /// converted.
        #[inline]
        pub fn equiv(
            &mut self,
            mut a: P::Node,
            mut b: P::Node,
        ) -> Result<<P::Node as Node>::Cmp, P::Error>
        {
            // This loop, when used in conjunction with certain `RecurMode::recur` and
            // `RecurMode::next` implementations, is what prevents growing the call-stack, and so
            // prevents the possibility of stack overflow, when traversing descendents.  For other
            // implementations where the `RecurMode::recur` does grow the call-stack, the
            // `RecurMode::next` always returns `None` and so this loop should be optimized away.
            loop {
                match self.equiv_main(a, b) {
                    Ok(cmp) if cmp.is_equiv() => match self.recur_mode.next() {
                        Some(Ok([an, bn])) => {
                            a = an;
                            b = bn;
                        },
                        Some(Err(cmp_amount_edges)) => return Ok(cmp_amount_edges),
                        None => return Ok(cmp),
                    },
                    result => return result,
                }
            }
        }

        /// The main logic of the algorithm.
        ///
        /// Must not be used as the initial entry-point, but may be called by
        /// [`RecurMode::recur`] implementations.
        ///
        /// Returns same as [`Self::equiv`].
        ///
        /// # Errors
        /// Same as [`Self::equiv`].
        #[inline]
        pub fn equiv_main(
            &mut self,
            a: P::Node,
            b: P::Node,
        ) -> Result<<P::Node as Node>::Cmp, P::Error>
        {
            // Needed only because the `?` operator uses `From` instead of `Into`.
            macro_rules! try_into {
                ($e:expr) => {
                    ($e).map_err(Into::into)?
                };
            }

            let mut cmp = Cmp::new_equiv();

            // For trait method implementations that always return the same constant, dead
            // branches should be eliminated by the optimizer.  For the other methods, inlining
            // should be doable by the optimizer.

            if try_into!(self.descend_mode.do_traverse()) && a.id() != b.id() {
                cmp = a.equiv_modulo_edges(&b);
                if cmp.is_equiv() {
                    let mut edges_iter = EdgesIter::new([a, b]);
                    match edges_iter.next_no_adv() {
                        Some(Ok(_)) => {
                            #[allow(clippy::shadow_unrelated)]
                            let [a, b] = &edges_iter.counterparts;
                            if try_into!(self.descend_mode.do_edges(a, b)) {
                                cmp = try_into!(P::RecurMode::recur(self, edges_iter));
                            }
                        },
                        Some(Err(cmp_amount_edges)) => cmp = cmp_amount_edges,
                        None => (),
                    }
                }
            }

            Ok(cmp)
        }
    }
}