use core::iter::FusedIterator;
use super::Truffle;
pub struct TruffleFinder<'a, 'h> {
inner: TruffleIter<'a, 'h, false>,
}
pub struct TruffleMismatcher<'a, 'h> {
inner: TruffleIter<'a, 'h, true>,
}
impl<'a, 'h> TruffleFinder<'a, 'h> {
#[inline]
pub(super) fn new(matcher: &'a Truffle, haystack: &'h [u8]) -> Self {
Self {
inner: TruffleIter::new(matcher, haystack),
}
}
}
impl<'a, 'h> TruffleMismatcher<'a, 'h> {
#[inline]
pub(super) fn new(matcher: &'a Truffle, haystack: &'h [u8]) -> Self {
Self {
inner: TruffleIter::new(matcher, haystack),
}
}
}
impl Iterator for TruffleFinder<'_, '_> {
type Item = usize;
#[inline]
fn next(&mut self) -> Option<usize> {
self.inner.next()
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
self.inner.size_hint()
}
}
impl DoubleEndedIterator for TruffleFinder<'_, '_> {
#[inline]
fn next_back(&mut self) -> Option<usize> {
self.inner.next_back()
}
}
impl FusedIterator for TruffleFinder<'_, '_> {}
impl Iterator for TruffleMismatcher<'_, '_> {
type Item = usize;
#[inline]
fn next(&mut self) -> Option<usize> {
self.inner.next()
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
self.inner.size_hint()
}
}
impl DoubleEndedIterator for TruffleMismatcher<'_, '_> {
#[inline]
fn next_back(&mut self) -> Option<usize> {
self.inner.next_back()
}
}
impl FusedIterator for TruffleMismatcher<'_, '_> {}
struct TruffleIter<'a, 'h, const REVERT: bool> {
matcher: &'a Truffle,
haystack: &'h [u8],
front: usize,
back: usize,
}
impl<const REVERT: bool> Iterator for TruffleIter<'_, '_, REVERT> {
type Item = usize;
#[inline]
fn next(&mut self) -> Option<usize> {
if self.is_empty() {
return None;
}
match self.matcher.search::<REVERT>(self.haystack()) {
Some(offset) => {
let index = self.front + offset;
self.front = index + 1;
Some(index)
}
None => {
self.front = self.back;
None
}
}
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
(0, Some(self.len()))
}
}
impl<const REVERT: bool> DoubleEndedIterator for TruffleIter<'_, '_, REVERT> {
#[inline]
fn next_back(&mut self) -> Option<usize> {
if self.is_empty() {
return None;
}
match self.matcher.rsearch::<REVERT>(self.haystack()) {
Some(relative) => {
let index = self.front + relative;
self.back = index;
Some(index)
}
None => {
self.front = self.back;
None
}
}
}
}
impl<const REVERT: bool> FusedIterator for TruffleIter<'_, '_, REVERT> {}
impl<'a, 'h, const REVERT: bool> TruffleIter<'a, 'h, REVERT> {
#[inline]
fn new(matcher: &'a Truffle, haystack: &'h [u8]) -> Self {
Self {
matcher,
haystack,
front: 0,
back: haystack.len(),
}
}
#[inline]
fn is_empty(&self) -> bool {
self.len() == 0
}
#[inline]
fn len(&self) -> usize {
self.back - self.front
}
#[inline]
fn haystack(&self) -> &[u8] {
debug_assert!(self.front <= self.back && self.back <= self.haystack.len());
unsafe { self.haystack.get_unchecked(self.front..self.back) }
}
}
#[cfg(test)]
mod tests {
extern crate std;
use std::vec::Vec;
use super::{Truffle, TruffleFinder, TruffleMismatcher};
#[test]
fn finder_next_yields_ascending_indices() {
let matcher = Truffle::new(b"A");
let mut haystack = [b'!'; 130];
for index in [1, 63, 64, 65, 128] {
haystack[index] = b'A';
}
let iter = TruffleFinder::new(&matcher, &haystack);
assert_eq!(iter.collect::<Vec<_>>(), [1, 63, 64, 65, 128]);
}
#[test]
fn finder_next_stays_exhausted() {
let matcher = Truffle::new(b"A");
let mut iter = TruffleFinder::new(&matcher, b"!A!");
assert_eq!(iter.next(), Some(1));
for _ in 0..3 {
assert_eq!(iter.next(), None);
}
}
#[test]
fn finder_next_back_yields_descending_indices() {
let matcher = Truffle::new(b"A");
let mut haystack = [b'!'; 130];
for index in [1, 63, 64, 65, 128] {
haystack[index] = b'A';
}
let iter = TruffleFinder::new(&matcher, &haystack);
assert_eq!(iter.rev().collect::<Vec<_>>(), [128, 65, 64, 63, 1]);
}
#[test]
fn finder_next_back_stays_exhausted() {
let matcher = Truffle::new(b"A");
let mut iter = TruffleFinder::new(&matcher, b"!A!");
assert_eq!(iter.next_back(), Some(1));
for _ in 0..3 {
assert_eq!(iter.next_back(), None);
}
}
#[test]
fn finder_size_hint_bounds_the_remaining_results() {
let matcher = Truffle::new(b"A");
let mut iter = TruffleFinder::new(&matcher, b"A!A!A");
for remaining in (0..=3).rev() {
let (lower, upper) = iter.size_hint();
assert!(lower <= remaining);
assert!(upper.is_some_and(|upper| upper >= remaining));
iter.next();
}
}
#[test]
fn finder_size_hint_is_zero_after_exhaustion() {
let matcher = Truffle::new(b"A");
let mut iter = TruffleFinder::new(&matcher, b"!A!");
while iter.next().is_some() {}
assert_eq!(iter.size_hint(), (0, Some(0)));
}
#[test]
fn finder_next_and_next_back_share_the_remaining_range() {
let matcher = Truffle::new(b"A");
let mut haystack = [b'!'; 130];
for index in [1, 63, 64, 65, 128] {
haystack[index] = b'A';
}
let mut iter = TruffleFinder::new(&matcher, &haystack);
assert_eq!(iter.next(), Some(1));
assert_eq!(iter.next_back(), Some(128));
assert_eq!(iter.next(), Some(63));
assert_eq!(iter.next_back(), Some(65));
assert_eq!(iter.next(), Some(64));
assert_eq!(iter.next(), None);
assert_eq!(iter.next_back(), None);
}
#[test]
fn finder_next_is_exhausted_after_next_back() {
let matcher = Truffle::new(b"A");
let mut iter = TruffleFinder::new(&matcher, b"!A!");
while iter.next_back().is_some() {}
assert_eq!(iter.next(), None);
}
#[test]
fn finder_returns_no_indices_without_a_match() {
let matcher = Truffle::new(b"A");
let iter = TruffleFinder::new(&matcher, b"!!!");
assert_eq!(iter.collect::<Vec<_>>(), []);
}
#[test]
fn finder_next_yields_every_position_across_block_boundaries() {
let matcher = Truffle::new(b"A");
for len in [
0, 1, 7, 15, 16, 17, 31, 32, 33, 63, 64, 65, 127, 128, 129, 255, 256, 257, 511,
] {
for offset in 0..64 {
let mut storage = [b'!'; 576];
let haystack = &mut storage[offset..offset + len];
haystack.fill(b'A');
let expected: Vec<_> = (0..len).collect();
let iter = TruffleFinder::new(&matcher, haystack);
assert_eq!(
iter.collect::<Vec<_>>(),
expected,
"len={len}, offset={offset}"
);
}
}
}
#[test]
fn finder_next_back_yields_every_position_across_block_boundaries() {
let matcher = Truffle::new(b"A");
for len in [
0, 1, 7, 15, 16, 17, 31, 32, 33, 63, 64, 65, 127, 128, 129, 255, 256, 257, 511,
] {
for offset in 0..64 {
let mut storage = [b'!'; 576];
let haystack = &mut storage[offset..offset + len];
haystack.fill(b'A');
let expected: Vec<_> = (0..len).rev().collect();
let iter = TruffleFinder::new(&matcher, haystack);
assert_eq!(
iter.rev().collect::<Vec<_>>(),
expected,
"len={len}, offset={offset}"
);
}
}
}
#[test]
fn finder_next_keeps_spaced_matches_across_block_boundaries() {
let matcher = Truffle::new(b"A");
for len in [
0, 1, 7, 15, 16, 17, 31, 32, 33, 63, 64, 65, 127, 128, 129, 255, 256, 257, 511,
] {
for offset in 0..64 {
let mut storage = [b'!'; 576];
let haystack = &mut storage[offset..offset + len];
for index in (0..len).step_by(3) {
haystack[index] = b'A';
}
let expected: Vec<_> = (0..len).step_by(3).collect();
let iter = TruffleFinder::new(&matcher, haystack);
assert_eq!(
iter.collect::<Vec<_>>(),
expected,
"len={len}, offset={offset}"
);
}
}
}
#[test]
fn finder_next_back_keeps_spaced_matches_across_block_boundaries() {
let matcher = Truffle::new(b"A");
for len in [
0, 1, 7, 15, 16, 17, 31, 32, 33, 63, 64, 65, 127, 128, 129, 255, 256, 257, 511,
] {
for offset in 0..64 {
let mut storage = [b'!'; 576];
let haystack = &mut storage[offset..offset + len];
for index in (0..len).step_by(3) {
haystack[index] = b'A';
}
let expected: Vec<_> = (0..len).step_by(3).rev().collect();
let iter = TruffleFinder::new(&matcher, haystack);
assert_eq!(
iter.rev().collect::<Vec<_>>(),
expected,
"len={len}, offset={offset}"
);
}
}
}
#[test]
fn mismatcher_next_yields_ascending_indices() {
let matcher = Truffle::new(b"A");
let mut haystack = [b'A'; 130];
for index in [1, 63, 64, 65, 128] {
haystack[index] = b'!';
}
let iter = TruffleMismatcher::new(&matcher, &haystack);
assert_eq!(iter.collect::<Vec<_>>(), [1, 63, 64, 65, 128]);
}
#[test]
fn mismatcher_next_stays_exhausted() {
let matcher = Truffle::new(b"A");
let mut iter = TruffleMismatcher::new(&matcher, b"A!A");
assert_eq!(iter.next(), Some(1));
for _ in 0..3 {
assert_eq!(iter.next(), None);
}
}
#[test]
fn mismatcher_next_back_yields_descending_indices() {
let matcher = Truffle::new(b"A");
let mut haystack = [b'A'; 130];
for index in [1, 63, 64, 65, 128] {
haystack[index] = b'!';
}
let iter = TruffleMismatcher::new(&matcher, &haystack);
assert_eq!(iter.rev().collect::<Vec<_>>(), [128, 65, 64, 63, 1]);
}
#[test]
fn mismatcher_next_back_stays_exhausted() {
let matcher = Truffle::new(b"A");
let mut iter = TruffleMismatcher::new(&matcher, b"A!A");
assert_eq!(iter.next_back(), Some(1));
for _ in 0..3 {
assert_eq!(iter.next_back(), None);
}
}
#[test]
fn mismatcher_size_hint_bounds_the_remaining_results() {
let matcher = Truffle::new(b"A");
let mut iter = TruffleMismatcher::new(&matcher, b"!A!A!");
for remaining in (0..=3).rev() {
let (lower, upper) = iter.size_hint();
assert!(lower <= remaining);
assert!(upper.is_some_and(|upper| upper >= remaining));
iter.next();
}
}
#[test]
fn mismatcher_size_hint_is_zero_after_exhaustion() {
let matcher = Truffle::new(b"A");
let mut iter = TruffleMismatcher::new(&matcher, b"A!A");
while iter.next().is_some() {}
assert_eq!(iter.size_hint(), (0, Some(0)));
}
#[test]
fn mismatcher_next_and_next_back_share_the_remaining_range() {
let matcher = Truffle::new(b"A");
let mut haystack = [b'A'; 130];
for index in [1, 63, 64, 65, 128] {
haystack[index] = b'!';
}
let mut iter = TruffleMismatcher::new(&matcher, &haystack);
assert_eq!(iter.next(), Some(1));
assert_eq!(iter.next_back(), Some(128));
assert_eq!(iter.next(), Some(63));
assert_eq!(iter.next_back(), Some(65));
assert_eq!(iter.next(), Some(64));
assert_eq!(iter.next(), None);
assert_eq!(iter.next_back(), None);
}
#[test]
fn mismatcher_next_is_exhausted_after_next_back() {
let matcher = Truffle::new(b"A");
let mut iter = TruffleMismatcher::new(&matcher, b"A!A");
while iter.next_back().is_some() {}
assert_eq!(iter.next(), None);
}
#[test]
fn mismatcher_returns_no_indices_without_a_match() {
let matcher = Truffle::new(b"A");
let iter = TruffleMismatcher::new(&matcher, b"AAA");
assert_eq!(iter.collect::<Vec<_>>(), []);
}
#[test]
fn mismatcher_next_yields_every_position_across_block_boundaries() {
let matcher = Truffle::new(b"A");
for len in [
0, 1, 7, 15, 16, 17, 31, 32, 33, 63, 64, 65, 127, 128, 129, 255, 256, 257, 511,
] {
for offset in 0..64 {
let mut storage = [b'A'; 576];
let haystack = &mut storage[offset..offset + len];
haystack.fill(b'!');
let expected: Vec<_> = (0..len).collect();
let iter = TruffleMismatcher::new(&matcher, haystack);
assert_eq!(
iter.collect::<Vec<_>>(),
expected,
"len={len}, offset={offset}"
);
}
}
}
#[test]
fn mismatcher_next_back_yields_every_position_across_block_boundaries() {
let matcher = Truffle::new(b"A");
for len in [
0, 1, 7, 15, 16, 17, 31, 32, 33, 63, 64, 65, 127, 128, 129, 255, 256, 257, 511,
] {
for offset in 0..64 {
let mut storage = [b'A'; 576];
let haystack = &mut storage[offset..offset + len];
haystack.fill(b'!');
let expected: Vec<_> = (0..len).rev().collect();
let iter = TruffleMismatcher::new(&matcher, haystack);
assert_eq!(
iter.rev().collect::<Vec<_>>(),
expected,
"len={len}, offset={offset}"
);
}
}
}
#[test]
fn mismatcher_next_keeps_spaced_matches_across_block_boundaries() {
let matcher = Truffle::new(b"A");
for len in [
0, 1, 7, 15, 16, 17, 31, 32, 33, 63, 64, 65, 127, 128, 129, 255, 256, 257, 511,
] {
for offset in 0..64 {
let mut storage = [b'A'; 576];
let haystack = &mut storage[offset..offset + len];
for index in (0..len).step_by(3) {
haystack[index] = b'!';
}
let expected: Vec<_> = (0..len).step_by(3).collect();
let iter = TruffleMismatcher::new(&matcher, haystack);
assert_eq!(
iter.collect::<Vec<_>>(),
expected,
"len={len}, offset={offset}"
);
}
}
}
#[test]
fn mismatcher_next_back_keeps_spaced_matches_across_block_boundaries() {
let matcher = Truffle::new(b"A");
for len in [
0, 1, 7, 15, 16, 17, 31, 32, 33, 63, 64, 65, 127, 128, 129, 255, 256, 257, 511,
] {
for offset in 0..64 {
let mut storage = [b'A'; 576];
let haystack = &mut storage[offset..offset + len];
for index in (0..len).step_by(3) {
haystack[index] = b'!';
}
let expected: Vec<_> = (0..len).step_by(3).rev().collect();
let iter = TruffleMismatcher::new(&matcher, haystack);
assert_eq!(
iter.rev().collect::<Vec<_>>(),
expected,
"len={len}, offset={offset}"
);
}
}
}
}