src/tests/substring/prop.rs

/*!
This module defines a few quickcheck properties for substring search.

It also provides a forward and reverse macro for conveniently defining
quickcheck tests that run these properties over any substring search
implementation.
*/

use crate::tests::substring::naive;

/// $fwd is a `impl FnMut(haystack, needle) -> Option<Option<usize>>`. When the
/// routine returns `None`, then it's skipped, which is useful for substring
/// implementations that don't work for all inputs.
#[macro_export]
macro_rules! define_substring_forward_quickcheck {
    ($fwd:expr) => {
        #[cfg(not(miri))]
        quickcheck::quickcheck! {
            fn qc_fwd_prefix_is_substring(bs: alloc::vec::Vec<u8>) -> bool {
                crate::tests::substring::prop::prefix_is_substring(&bs, $fwd)
            }

            fn qc_fwd_suffix_is_substring(bs: alloc::vec::Vec<u8>) -> bool {
                crate::tests::substring::prop::suffix_is_substring(&bs, $fwd)
            }

            fn qc_fwd_matches_naive(
                haystack: alloc::vec::Vec<u8>,
                needle: alloc::vec::Vec<u8>
            ) -> bool {
                crate::tests::substring::prop::same_as_naive(
                    false,
                    &haystack,
                    &needle,
                    $fwd,
                )
            }
        }
    };
}

/// $rev is a `impl FnMut(haystack, needle) -> Option<Option<usize>>`. When the
/// routine returns `None`, then it's skipped, which is useful for substring
/// implementations that don't work for all inputs.
#[macro_export]
macro_rules! define_substring_reverse_quickcheck {
    ($rev:expr) => {
        #[cfg(not(miri))]
        quickcheck::quickcheck! {
            fn qc_rev_prefix_is_substring(bs: alloc::vec::Vec<u8>) -> bool {
                crate::tests::substring::prop::prefix_is_substring(&bs, $rev)
            }

            fn qc_rev_suffix_is_substring(bs: alloc::vec::Vec<u8>) -> bool {
                crate::tests::substring::prop::suffix_is_substring(&bs, $rev)
            }

            fn qc_rev_matches_naive(
                haystack: alloc::vec::Vec<u8>,
                needle: alloc::vec::Vec<u8>
            ) -> bool {
                crate::tests::substring::prop::same_as_naive(
                    true,
                    &haystack,
                    &needle,
                    $rev,
                )
            }
        }
    };
}

/// Check that every prefix of the given byte string is a substring.
pub(crate) fn prefix_is_substring(
    bs: &[u8],
    mut search: impl FnMut(&[u8], &[u8]) -> Option<Option<usize>>,
) -> bool {
    for i in 0..bs.len().saturating_sub(1) {
        let prefix = &bs[..i];
        let result = match search(bs, prefix) {
            None => continue,
            Some(result) => result,
        };
        if !result.is_some() {
            return false;
        }
    }
    true
}

/// Check that every suffix of the given byte string is a substring.
pub(crate) fn suffix_is_substring(
    bs: &[u8],
    mut search: impl FnMut(&[u8], &[u8]) -> Option<Option<usize>>,
) -> bool {
    for i in 0..bs.len().saturating_sub(1) {
        let suffix = &bs[i..];
        let result = match search(bs, suffix) {
            None => continue,
            Some(result) => result,
        };
        if !result.is_some() {
            return false;
        }
    }
    true
}

/// Check that naive substring search matches the result of the given search
/// algorithm.
pub(crate) fn same_as_naive(
    reverse: bool,
    haystack: &[u8],
    needle: &[u8],
    mut search: impl FnMut(&[u8], &[u8]) -> Option<Option<usize>>,
) -> bool {
    let result = match search(haystack, needle) {
        None => return true,
        Some(result) => result,
    };
    if reverse {
        result == naive::rfind(haystack, needle)
    } else {
        result == naive::find(haystack, needle)
    }
}