flipflop 0.2.0

//! [`Suite`] trait and impls.

use core::{cell::Cell, num::NonZero};

use crate::{
    accum::Accum,
    error::{AccumVerifyError, SuiteError, Unequal},
    side::Side,
    strategy::Alternate,
};

/// A collection of strategies and verifiers.
pub trait Suite {
    /// Item for suite.
    type Item;

    /// Verification error.
    type Error<'a>
    where
        Self: 'a;

    /// Applies the next strategy to an iterator.
    ///
    /// Indicates whether more strategies remain in the suite.
    fn accumulate_verify<
        'a,
        A: ?Sized + Accum<Item = Self::Item>,
        I: Clone + DoubleEndedIterator<Item = Self::Item>,
    >(
        &'a mut self,
        iter: &I,
        accum: &'a mut A,
    ) -> Result<bool, SuiteError<'a, A, Self::Error<'a>>>;

    /// Applies the entire suite to an iterator.
    fn run<
        'a,
        A: ?Sized + Accum<Item = Self::Item>,
        I: Clone + DoubleEndedIterator<Item = Self::Item>,
    >(
        &'a mut self,
        iter: &I,
        accum: &'a mut A,
    ) -> Result<(), SuiteError<'a, A, Self::Error<'a>>> {
        let cellf = Cell::from_mut(self);
        let cell_accum = Cell::from_mut(accum);
        // SAFETY: FIXME: Works on polonius.
        unsafe { while (*cellf.as_ptr()).accumulate_verify(iter, &mut (*cell_accum.as_ptr()))? {} }
        Ok(())
    }
}

/// Gets the next strategy after a given [`Alternate`] strategy.
fn next_strategy(strategy: Alternate) -> Option<Alternate> {
    if strategy.start == Side::Forward {
        Some(strategy.swap())
    } else {
        strategy.shrink()
    }
}

/// Fully deterministic suite that checks against an existing slice of items.
///
/// Tries alternating all periods between the length of the slice and 1, starting in either
/// direction.
#[derive(Copy, Clone, Debug)]
pub struct Simple<'a, T> {
    /// Verifier for suite.
    verifier: &'a [T],

    /// Current strategy.
    strategy: Alternate,
}
impl<'a, T> Simple<'a, T> {
    /// Creates the suite from a slice to verify.
    ///
    /// # Panics
    ///
    /// Panics if the slice is empty.
    pub fn new(slice: &'a [T]) -> Simple<'a, T> {
        let Some(period) = NonZero::new(slice.len()) else {
            panic!("cannot create simple strategy with empty slice")
        };
        Simple {
            verifier: slice,
            strategy: Alternate {
                start: Side::Forward,
                period,
            },
        }
    }
}
impl<'a, T: PartialEq> Suite for Simple<'a, T> {
    type Item = T;

    type Error<'b>
        = Unequal<'b, T>
    where
        'a: 'b;

    #[inline]
    fn accumulate_verify<
        'b,
        A: ?Sized + Accum<Item = T>,
        I: Clone + DoubleEndedIterator<Item = T>,
    >(
        &'b mut self,
        iter: &I,
        accum: &'b mut A,
    ) -> Result<bool, SuiteError<'b, A, Unequal<'b, T>>> {
        let cell_strategy = Cell::from_mut(&mut self.strategy);
        // SAFETY: FIXME: Works on polonius.
        unsafe {
            accum
                .accumulate_verify(iter.clone(), &(*cell_strategy.as_ptr()), self.verifier)
                .map_err(AccumVerifyError::erased_strategy)?;
        }
        if let Some(strategy) = next_strategy(cell_strategy.get()) {
            cell_strategy.set(strategy);
            Ok(true)
        } else {
            Ok(false)
        }
    }
}

/// Suites that require `alloc`.
#[cfg(any(doc, feature = "alloc"))]
#[cfg_attr(feature = "nightly", doc(cfg(feature = "alloc")))]
mod alloc {
    use alloc::vec::Vec;
    use core::{cell::Cell, num::NonZero};

    use crate::{
        accum::Accum,
        error::{FailedStrategy, Inconsistent, SuiteError},
        side::Side,
        strategy::{Alternate, Always},
        suite::{Suite, next_strategy},
    };

    /// Accumulates data and verifies that it's nonempty, returning the length.
    pub(super) fn first_run<
        'a,
        A: ?Sized + Accum,
        I: Clone + DoubleEndedIterator<Item = A::Item>,
    >(
        data: &mut Vec<A::Item>,
        iter: &I,
        accum: &'a mut A,
    ) -> Result<NonZero<usize>, SuiteError<'a, A, Inconsistent<'a, A::Item>>> {
        let cell_accum = Cell::from_mut(accum);
        let strategy = &Always(Side::Forward);

        // SAFETY: FIXME: Works on polonius.
        unsafe {
            (*cell_accum.as_ptr())
                .accumulate(iter.clone(), strategy)
                .map_err(Into::into)?;
            data.reserve((*cell_accum.as_ptr()).len());
            while let Some(item) = (*cell_accum.as_ptr()).pop_forward() {
                data.push(item);
            }
        }
        data.reverse();
        let Some(period) = NonZero::new(data.len()) else {
            return Err(FailedStrategy::empty(strategy, Inconsistent::Empty)
                .erased_strategy()
                .into());
        };
        Ok(period)
    }

    /// Fully deterministic suite that checks that all directions return the same results.
    ///
    /// Uses the same strategies as [`Simple`], but doesn't start with an input slice. Similarly to
    /// [`Simple`], also requires that the data be nonempty.
    ///
    /// [`Simple`]: crate::suite::Simple
    #[derive(Clone, Debug)]
    pub struct Consistent<T> {
        /// Data from first run.
        data: Vec<T>,

        /// Current strategy *after* first run.
        ///
        /// Set to nonsense for first run.
        strategy: Alternate,
    }
    impl<T> Consistent<T> {
        /// Creates a new suite without any data.
        #[inline]
        pub fn new() -> Consistent<T> {
            Consistent {
                data: Vec::new(),
                strategy: Alternate {
                    start: Side::Forward,
                    period: NonZero::new(1).unwrap(),
                },
            }
        }
    }
    impl<T> Default for Consistent<T> {
        #[inline]
        fn default() -> Consistent<T> {
            Consistent::new()
        }
    }
    impl<T: PartialEq> Suite for Consistent<T> {
        type Item = T;

        type Error<'a>
            = Inconsistent<'a, T>
        where
            T: 'a;

        fn accumulate_verify<
            'a,
            A: ?Sized + crate::Accum<Item = T>,
            I: Clone + DoubleEndedIterator<Item = T>,
        >(
            &'a mut self,
            iter: &I,
            accum: &'a mut A,
        ) -> Result<bool, SuiteError<'a, A, Inconsistent<'a, T>>> {
            let cell_strategy = Cell::from_mut(&mut self.strategy);
            if self.data.is_empty() {
                let period = first_run(&mut self.data, iter, accum)?;
                cell_strategy.set(Alternate {
                    start: Side::Backward,
                    period,
                });
                Ok(true)
            } else {
                // SAFETY: FIXME: Works on polonius.
                unsafe {
                    accum
                        .accumulate_verify(iter.clone(), &(*cell_strategy.as_ptr()), &self.data[..])
                        .map_err(|err| err.map(Inconsistent::Unequal).erased_strategy())?;
                }
                if let Some(strategy) = next_strategy(cell_strategy.get()) {
                    cell_strategy.set(strategy);
                    Ok(true)
                } else {
                    Ok(false)
                }
            }
        }
    }
}

#[cfg(any(doc, feature = "alloc"))]
#[cfg_attr(feature = "nightly", doc(cfg(feature = "alloc")))]
pub use self::alloc::Consistent;

/// Suites that require `rand` and `std`.
#[cfg(any(doc, all(feature = "rand", feature = "std")))]
#[cfg_attr(feature = "nightly", doc(cfg(all(feature = "rand", feature = "std"))))]
mod rand_std {

    use core::cell::Cell;

    use crate::{
        error::{Inconsistent, SuiteError},
        strategy::Random,
        suite::{Suite, alloc::first_run},
    };

    /// Fully random suite with a given number of iterations.
    ///
    /// Verifies that the data is consistent.
    #[derive(Clone, Debug)]
    pub struct RandomConsistent<T, R: rand::SeedableRng> {
        /// Iterations left.
        iters_left: usize,

        /// Data from first run.
        data: Vec<T>,

        /// Strategy.
        strategy: Random<R>,
    }
    impl<T, R: rand::SeedableRng> RandomConsistent<T, R> {
        /// Creates a new suite.
        #[inline]
        pub fn new(iters: usize) -> RandomConsistent<T, R> {
            RandomConsistent {
                iters_left: iters,
                data: Vec::new(),
                strategy: Random::random(0.5),
            }
        }
    }
    impl<T: PartialEq, R: rand::SeedableRng + rand::RngCore> Suite for RandomConsistent<T, R> {
        type Item = T;

        type Error<'a>
            = Inconsistent<'a, T>
        where
            T: 'a,
            R: 'a;

        fn accumulate_verify<
            'a,
            A: ?Sized + crate::Accum<Item = T>,
            I: Clone + DoubleEndedIterator<Item = T>,
        >(
            &'a mut self,
            iter: &I,
            accum: &'a mut A,
        ) -> Result<bool, SuiteError<'a, A, Inconsistent<'a, T>>> {
            let cell_strategy = Cell::from_mut(&mut self.strategy);
            if self.data.is_empty() {
                let _ = first_run(&mut self.data, iter, accum)?;
                Ok(true)
            } else {
                // SAFETY: FIXME: Works on polonius.
                unsafe {
                    accum
                        .accumulate_verify(iter.clone(), &(*cell_strategy.as_ptr()), &self.data[..])
                        .map_err(|err| err.map(Inconsistent::Unequal).erased_strategy())?;
                    if self.iters_left > 0 {
                        (*cell_strategy.as_ptr()) = Random::random(0.5);
                        self.iters_left -= 1;
                        Ok(true)
                    } else {
                        Ok(false)
                    }
                }
            }
        }
    }
}

#[cfg(any(doc, all(feature = "rand", feature = "std")))]
#[cfg_attr(feature = "nightly", doc(cfg(all(feature = "rand", feature = "std"))))]
pub use self::rand_std::RandomConsistent;

#[cfg(test)]
mod tests {
    #[cfg(feature = "alloc")]
    use {
        crate::{accum::Unbounded, suite::Consistent},
        core::iter,
    };

    use crate::{
        accum::{Accum, Bounded},
        suite::{Simple, Suite},
    };

    #[test]
    #[cfg(feature = "alloc")]
    fn inconsistent_empty() {
        let mut suite = Consistent::new();
        let mut accum = <Bounded<u32, 0>>::new();
        let result = suite.run(&iter::empty(), &mut accum);
        assert!(result.is_err());
        let result = result.unwrap_err();
        assert_eq!(
            result.to_string(),
            r#"failed strategy "always forward": [..] due to verification error: no data was returned by iterator"#
        );
    }

    #[test]
    #[cfg(feature = "alloc")]
    fn consistent_weird_iterator() {
        let mut suite = Consistent::new();
        let mut accum = Unbounded::new();
        let iter = (1..10).rev().flat_map(|x| 0..x);
        let result = suite.run(&iter, &mut accum);
        if let Err(err) = result {
            panic!("{}", err);
        }
    }

    #[test]
    fn simple_weird_iterator() {
        let mut suite = Simple::new(&[
            0, 1, 2, 3, 4, 5, 6, 7, 8, // 0..9
            0, 1, 2, 3, 4, 5, 6, 7, // 0..8
            0, 1, 2, 3, 4, 5, 6, // 0..7
            0, 1, 2, 3, 4, 5, // 0..6
            0, 1, 2, 3, 4, // 0..5
            0, 1, 2, 3, // 0..4
            0, 1, 2, // 0..3
            0, 1, // 0..2
            0, // 0..1
        ]);
        let mut accum = <Bounded<u32, 45>>::new();
        let iter = (1..10).rev().flat_map(|x| 0..x);
        let result = suite.run(&iter, &mut accum);
        if let Err(err) = result {
            panic!("{}", err);
        }
    }
}