bufferring 0.0.2

//! Utilities for property-based testing.
//!
//! This module, enabled under the `proptest` feature, provides utilities for
//! defining randomized generation of ring buffers for property-based testing.
//!
//! The [`proptest`] crate requires defining a measurement of complication for
//! the values of a type, in order to generate them for property-based testing.
//! For the ring buffers in this crate, complication is defined thusly:
//!
//! - Ring buffers with a greater capacity are more complicated.
//! - Ring buffers with more elements are more complicated.
//! - Ring buffers with more complicated initial elements are more complicated.

#![cfg(feature = "proptest")]

use core::fmt::Debug;
use core::num::NonZeroUsize;

extern crate alloc;
use alloc::{boxed::Box, vec::Vec};

use proptest::strategy::{NewTree, Strategy, ValueTree};
use proptest::test_runner::TestRunner;

use bit_vec::BitVec;


/// A [`Strategy`] for ring buffers.
///
/// This generates iterators over items, which then need to be inserted into the
/// ring buffer of choice.  Insertion can be performed using [`enqueue()`] or by
/// directly accessing the underlying [`Storage`] (for ring buffers using it).
///
/// [`enqueue()`]: crate::RingBuffer::enqueue()
/// [`Storage`]: crate::Storage
///
/// This tree can be used for ring buffers with compile-time-fixed capacities as
/// well as for ring buffers with run-time-fixed capacities, depending upon how
/// it is initialized.
#[derive(Debug)]
pub struct BufferStrategy<C, T>
where C: Strategy<Value = NonZeroUsize>, T: Strategy {
    /// The strategy for capacities.
    capacity: C,
    /// The strategy for items.
    items: T,
}

impl<C, T> BufferStrategy<C, T>
where C: Strategy<Value = NonZeroUsize>, T: Strategy {
    /// Construct a new [`BufferStrategy`].
    pub fn new(capacity: C, items: T) -> Self {
        Self { capacity, items }
    }
}

impl<C, T> Strategy for BufferStrategy<C, T>
where C: Strategy<Value = NonZeroUsize>, T: Strategy {
    type Tree = BufferValueTree<C::Tree, T::Tree>;
    type Value = (NonZeroUsize, Vec<T::Value>);

    fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
        let capacity = self.capacity.new_tree(runner)?;
        let max_capacity = capacity.current().get();
        let items = (0 .. max_capacity)
            .map(|_| self.items.new_tree(runner))
            .collect::<Result<Vec<T::Tree>, _>>()?
            .into_boxed_slice();
        Ok(BufferValueTree {
            capacity,
            items,
            in_use: BitVec::from_elem(max_capacity, true),
            next_step: Some(BufferShrink::Capacity),
            prev_step: None,
        })
    }
}

/// A [`ValueTree`] for ring buffers.
#[derive(Debug)]
pub struct BufferValueTree<C, T>
where C: ValueTree<Value = NonZeroUsize>, T: ValueTree {
    /// The value tree of the capacity.
    capacity: C,
    /// The value trees of all items being used.
    items: Box<[T]>,
    /// The currently-selected items.
    in_use: BitVec,
    /// The next shrink step to perform.
    next_step: Option<BufferShrink>,
    /// The last-performed shrink step, if undoable.
    prev_step: Option<BufferShrink>,
}

impl<C, T> ValueTree for BufferValueTree<C, T>
where C: ValueTree<Value = NonZeroUsize>, T: ValueTree {
    type Value = (NonZeroUsize, Vec<T::Value>);

    fn current(&self) -> Self::Value {
        (self.capacity.current(), self.items.iter()
            .zip(self.in_use.iter())
            .filter_map(|(i, u)| u.then(|| i.current()))
            .collect())
    }

    fn simplify(&mut self) -> bool {
        // Try to reduce the buffer's capacity.
        if let Some(BufferShrink::Capacity) = self.next_step {
            let old_cap = self.capacity.current();
            if self.capacity.simplify() && self.capacity.current() < old_cap {
                let new_cap = self.capacity.current();
                for i in new_cap.get() .. old_cap.get() {
                    self.in_use.set(i, false);
                }
                self.prev_step = Some(BufferShrink::Capacity);
                return true;
            } else {
                self.next_step = Some(BufferShrink::Remove(0));
            }
        }

        // Try to remove an element.
        if let Some(BufferShrink::Remove(i)) = self.next_step {
            if let Some(true) = self.in_use.get(i) {
                self.in_use.set(i, false);
                self.prev_step = Some(BufferShrink::Remove(i));
                self.next_step = Some(BufferShrink::Remove(i + 1));
                return true;
            } else {
                self.next_step = Some(BufferShrink::Shrink(0));
            }
        }

        // Try (repeatedly) to shrink an element.
        while let Some(BufferShrink::Shrink(i)) = self.next_step {
            if let Some(true) = self.in_use.get(i) {
                if self.items[i].simplify() {
                    self.prev_step = Some(BufferShrink::Shrink(i));
                    return true;
                } else {
                    self.next_step = Some(BufferShrink::Shrink(i + 1));
                }
            } else {
                self.next_step = None;
                return false;
            }
        }

        false
    }

    fn complicate(&mut self) -> bool {
        match self.prev_step.take() {
            None => false,
            Some(BufferShrink::Capacity) => {
                let old = self.capacity.current();
                if self.capacity.complicate() && old < self.capacity.current() {
                    for i in old.get() .. self.capacity.current().get() {
                        self.in_use.set(i, true);
                    }
                    self.prev_step = Some(BufferShrink::Capacity);
                    true
                } else {
                    self.prev_step = None;
                    false
                }
            },
            Some(BufferShrink::Remove(i)) => {
                self.in_use.set(i, true);
                self.prev_step = None;
                true
            },
            Some(BufferShrink::Shrink(i)) => {
                if self.items[i].complicate() {
                    self.prev_step = Some(BufferShrink::Shrink(i));
                    true
                } else {
                    self.prev_step = None;
                    false
                }
            },
        }
    }
}

/// A shrinking step for a [`RingBufferValueTree`].
#[derive(Copy, Clone, Debug, PartialEq, Eq)]
enum BufferShrink {
    /// The capacity was shrunk.
    Capacity,
    /// An element was removed from the buffer.
    Remove(usize),
    /// An element was shrunk in the buffer.
    Shrink(usize),
}