bstr/search/

twoway.rs

use core::cmp;

use bstr::BStr;
use cow::CowBStr;
use search::prefilter::{Freqy, PrefilterState};

/// An implementation of the TwoWay substring search algorithm, with heuristics
/// for accelerating search based on frequency analysis.
///
/// This searcher supports forward and reverse search, although not
/// simultaneously. It runs in O(n + m) time and O(1) space, where
/// `n ~ len(needle)` and `m ~ len(haystack)`.
///
/// The implementation here roughly matches that which was developed by
/// Crochemore and Perrin in their 1991 paper "Two-way string-matching." The
/// only change in this implementation is the use of zero-based indices and
/// the addition of heuristics for a fast skip loop. That is, this will detect
/// bytes that are believed to be rare in the needle and use fast vectorized
/// instructions to find their occurrences quickly. The Two-Way algorithm is
/// then used to confirm whether a match at that location occurred.
///
/// The heuristic for fast skipping is automatically shut off if it's
/// detected to be ineffective at search time. Generally, this only occurs in
/// pathological cases. But this is generally necessary in order to preserve
/// a `O(n + m)` time bound.
///
/// The code below is fairly complex and not obviously correct at all. It's
/// likely necessary to read the Two-Way paper cited above in order to fully
/// grok this code.
#[derive(Clone, Debug)]
pub struct TwoWay<'b> {
    /// The needle that we're looking for.
    needle: CowBStr<'b>,
    /// An implementation of a fast skip loop based on hard-coded frequency
    /// data. This is only used when conditions are deemed favorable.
    freqy: Freqy,
    /// A critical position in needle. Specifically, this position corresponds
    /// to beginning of either the minimal or maximal suffix in needle. (N.B.
    /// See SuffixType below for why "minimal" isn't quite the correct word
    /// here.)
    ///
    /// This is the position at which every search begins. Namely, search
    /// starts by scanning text to the right of this position, and only if
    /// there's a match does the text to the left of this position get scanned.
    critical_pos: usize,
    /// The amount we shift by in the Two-Way search algorithm. This
    /// corresponds to the "small period" and "large period" cases.
    shift: Shift,
}

impl<'b> TwoWay<'b> {
    /// Create a searcher that uses the Two-Way algorithm by searching forwards
    /// through any haystack.
    pub fn forward(needle: &'b BStr) -> TwoWay<'b> {
        let freqy = Freqy::forward(needle);
        if needle.is_empty() {
            return TwoWay {
                needle: CowBStr::new(needle),
                freqy,
                critical_pos: 0,
                shift: Shift::Large { shift: 0  },
            };
        }

        let min_suffix = Suffix::forward(needle, SuffixKind::Minimal);
        let max_suffix = Suffix::forward(needle, SuffixKind::Maximal);
        let (period_lower_bound, critical_pos) =
            if min_suffix.pos > max_suffix.pos {
                (min_suffix.period, min_suffix.pos)
            } else {
                (max_suffix.period, max_suffix.pos)
            };
        let shift = Shift::forward(needle, period_lower_bound, critical_pos);
        let needle = CowBStr::new(needle);
        TwoWay { needle, freqy, critical_pos, shift }
    }

    /// Create a searcher that uses the Two-Way algorithm by searching in
    /// reverse through any haystack.
    pub fn reverse(needle: &'b BStr) -> TwoWay<'b> {
        let freqy = Freqy::reverse(needle);
        if needle.is_empty() {
            return TwoWay {
                needle: CowBStr::new(needle),
                freqy,
                critical_pos: 0,
                shift: Shift::Large { shift: 0  },
            };
        }

        let min_suffix = Suffix::reverse(needle, SuffixKind::Minimal);
        let max_suffix = Suffix::reverse(needle, SuffixKind::Maximal);
        let (period_lower_bound, critical_pos) =
            if min_suffix.pos < max_suffix.pos {
                (min_suffix.period, min_suffix.pos)
            } else {
                (max_suffix.period, max_suffix.pos)
            };
        let shift = Shift::reverse(needle, period_lower_bound, critical_pos);
        let needle = CowBStr::new(needle);
        TwoWay { needle, freqy, critical_pos, shift }
    }

    /// Return a fresh prefilter state that can be used with this searcher.
    /// A prefilter state is used to track the effectiveness of a searcher's
    /// prefilter for speeding up searches. Therefore, the prefilter state
    /// should generally be reused on subsequent searches (such as in an
    /// iterator). For searches on a different haystack, then a new prefilter
    /// state should be used.
    ///
    /// This always initializes a valid prefilter state even if this searcher
    /// does not have a prefilter enabled.
    pub fn prefilter_state(&self) -> PrefilterState {
        self.freqy.prefilter_state()
    }

    /// Return the needle used by this searcher.
    pub fn needle(&self) -> &BStr {
        self.needle.as_bstr()
    }

    /// Convert this searched into an owned version, where the needle is
    /// copied if it isn't already owned.
    #[cfg(feature = "std")]
    pub fn into_owned(self) -> TwoWay<'static> {
        TwoWay {
            needle: self.needle.into_owned(),
            freqy: self.freqy,
            critical_pos: self.critical_pos,
            shift: self.shift,
        }
    }

    /// Find the position of the first occurrence of this searcher's needle in
    /// the given haystack. If one does not exist, then return None.
    ///
    /// This will automatically initialize prefilter state. This should only
    /// be used for one-off searches.
    pub fn find(&self, haystack: &BStr) -> Option<usize> {
        self.find_with(&mut self.prefilter_state(), haystack)
    }

    /// Find the position of the last occurrence of this searcher's needle
    /// in the given haystack. If one does not exist, then return None.
    ///
    /// This will automatically initialize prefilter state. This should only
    /// be used for one-off searches.
    pub fn rfind(&self, haystack: &BStr) -> Option<usize> {
        self.rfind_with(&mut self.prefilter_state(), haystack)
    }

    /// Find the position of the first occurrence of this searcher's needle in
    /// the given haystack. If one does not exist, then return None.
    ///
    /// This accepts prefilter state that is useful when using the same
    /// searcher multiple times, such as in an iterator.
    pub fn find_with(
        &self,
        prestate: &mut PrefilterState,
        haystack: &BStr,
    ) -> Option<usize> {
        if self.needle.is_empty() {
            return Some(0);
        } else if haystack.len() < self.needle.len() {
            return None;
        } else if self.needle.len() == 1 {
            return haystack.find_byte(self.needle[0]);
        }
        match self.shift {
            Shift::Small { period } => {
                self.find_small(prestate, haystack, period)
            }
            Shift::Large { shift } => {
                self.find_large(prestate, haystack, shift)
            }
        }
    }

    /// Find the position of the last occurrence of this searcher's needle
    /// in the given haystack. If one does not exist, then return None.
    ///
    /// This accepts prefilter state that is useful when using the same
    /// searcher multiple times, such as in an iterator.
    pub fn rfind_with(
        &self,
        prestate: &mut PrefilterState,
        haystack: &BStr,
    ) -> Option<usize> {
        if self.needle.is_empty() {
            return Some(haystack.len());
        } else if haystack.len() < self.needle.len() {
            return None;
        } else if self.needle.len() == 1 {
            return haystack.rfind_byte(self.needle[0]);
        }
        match self.shift {
            Shift::Small { period } => {
                self.rfind_small(prestate, haystack, period)
            }
            Shift::Large { shift } => {
                self.rfind_large(prestate, haystack, shift)
            }
        }
    }

    // Below is the actual implementation of TwoWay searching, including both
    // forwards and backwards searching. Each forward and reverse search has
    // two fairly similar implementations, each handling the small and large
    // period cases, for a total 4 different search routines.
    //
    // On top of that, each search implementation can be accelerated by a
    // Freqy prefilter, but it is not always enabled. To avoid its overhead
    // when its disabled, we explicitly inline each search implementation based
    // on whether Freqy will be used or not. This brings us up to a total of
    // 8 monomorphized versions of the search code.

    #[inline(never)]
    fn find_small(
        &self,
        prestate: &mut PrefilterState,
        haystack: &BStr,
        period: usize,
    ) -> Option<usize> {
        if prestate.is_effective() {
            self.find_small_imp(prestate, true, haystack, period)
        } else {
            self.find_small_imp(prestate, false, haystack, period)
        }
    }

    #[inline(always)]
    fn find_small_imp(
        &self,
        prestate: &mut PrefilterState,
        prefilter: bool,
        haystack: &BStr,
        period: usize,
    ) -> Option<usize> {
        let needle = self.needle.as_bstr();
        let mut pos = 0;
        let mut shift = 0;
        while pos + needle.len() <= haystack.len() {
            let mut i = cmp::max(self.critical_pos, shift);
            if prefilter && prestate.is_effective() {
                match self.freqy.find_candidate(prestate, &haystack[pos..]) {
                    None => return None,
                    Some(found) => {
                        shift = 0;
                        i = self.critical_pos;
                        pos += found;
                        if pos + needle.len() > haystack.len() {
                            return None;
                        }
                    }
                }
            }
            while i < needle.len() && needle[i] == haystack[pos + i] {
                i += 1;
            }
            if i < needle.len() {
                pos += i - self.critical_pos + 1;
                shift = 0;
            } else {
                let mut j = self.critical_pos;
                while j > shift && needle[j] == haystack[pos + j] {
                    j -= 1;
                }
                if j <= shift && needle[shift] == haystack[pos + shift] {
                    return Some(pos);
                }
                pos += period;
                shift = needle.len() - period;
            }
        }
        None
    }

    #[inline(never)]
    fn find_large(
        &self,
        prestate: &mut PrefilterState,
        haystack: &BStr,
        shift: usize,
    ) -> Option<usize> {
        if prestate.is_effective() {
            self.find_large_imp(prestate, true, haystack, shift)
        } else {
            self.find_large_imp(prestate, false, haystack, shift)
        }
    }

    #[inline(always)]
    fn find_large_imp(
        &self,
        prestate: &mut PrefilterState,
        prefilter: bool,
        haystack: &BStr,
        shift: usize,
    ) -> Option<usize> {
        let needle = self.needle.as_bstr();
        let mut pos = 0;
        while pos + needle.len() <= haystack.len() {
            let mut i = self.critical_pos;
            if prefilter && prestate.is_effective() {
                match self.freqy.find_candidate(prestate, &haystack[pos..]) {
                    None => return None,
                    Some(found) => {
                        pos += found;
                        if pos + needle.len() > haystack.len() {
                            return None;
                        }
                    }
                }
            }
            while i < needle.len() && needle[i] == haystack[pos + i] {
                i += 1;
            }
            if i < needle.len() {
                pos += i - self.critical_pos + 1;
            } else {
                let mut j = self.critical_pos;
                while j > 0 && needle[j] == haystack[pos + j] {
                    j -= 1;
                }
                if j == 0 && needle[0] == haystack[pos] {
                    return Some(pos);
                }
                pos += shift;
            }
        }
        None
    }

    #[inline(never)]
    fn rfind_small(
        &self,
        prestate: &mut PrefilterState,
        haystack: &BStr,
        period: usize,
    ) -> Option<usize> {
        if prestate.is_effective() {
            self.rfind_small_imp(prestate, true, haystack, period)
        } else {
            self.rfind_small_imp(prestate, false, haystack, period)
        }
    }

    #[inline(always)]
    fn rfind_small_imp(
        &self,
        prestate: &mut PrefilterState,
        prefilter: bool,
        haystack: &BStr,
        period: usize,
    ) -> Option<usize> {
        let needle = &*self.needle;
        let nlen = needle.len();
        let mut pos = haystack.len();
        let mut shift = nlen;
        while pos >= nlen {
            let mut i = cmp::min(self.critical_pos, shift);
            if prefilter && prestate.is_effective() {
                match self.freqy.rfind_candidate(prestate, &haystack[..pos]) {
                    None => return None,
                    Some(found) => {
                        shift = nlen;
                        i = self.critical_pos;
                        pos = found;
                        if pos < nlen {
                            return None;
                        }
                    }
                }
            }
            while i > 0 && needle[i - 1] == haystack[pos - nlen + i - 1] {
                i -= 1;
            }
            if i > 0 || needle[0] != haystack[pos - nlen] {
                pos -= self.critical_pos - i + 1;
                shift = nlen;
            } else {
                let mut j = self.critical_pos;
                while j < shift && needle[j] == haystack[pos - nlen + j] {
                    j += 1;
                }
                if j == shift {
                    return Some(pos - nlen);
                }
                pos -= period;
                shift = period;
            }
        }
        None
    }

    #[inline(never)]
    fn rfind_large(
        &self,
        prestate: &mut PrefilterState,
        haystack: &BStr,
        shift: usize,
    ) -> Option<usize> {
        if prestate.is_effective() {
            self.rfind_large_imp(prestate, true, haystack, shift)
        } else {
            self.rfind_large_imp(prestate, false, haystack, shift)
        }
    }

    #[inline(always)]
    fn rfind_large_imp(
        &self,
        prestate: &mut PrefilterState,
        prefilter: bool,
        haystack: &BStr,
        shift: usize,
    ) -> Option<usize> {
        let needle = &*self.needle;
        let nlen = needle.len();
        let mut pos = haystack.len();
        while pos >= nlen {
            if prefilter && prestate.is_effective() {
                match self.freqy.rfind_candidate(prestate, &haystack[..pos]) {
                    None => return None,
                    Some(found) => {
                        pos = found;
                        if pos < nlen {
                            return None;
                        }
                    }
                }
            }

            let mut i = self.critical_pos;
            while i > 0 && needle[i - 1] == haystack[pos - nlen + i - 1] {
                i -= 1;
            }
            if i > 0 || needle[0] != haystack[pos - nlen] {
                pos -= self.critical_pos - i + 1;
            } else {
                let mut j = self.critical_pos;
                while j < nlen && needle[j] == haystack[pos - nlen + j] {
                    j += 1;
                }
                if j == nlen {
                    return Some(pos - nlen);
                }
                pos -= shift;
            }
        }
        None
    }
}

/// A representation of the amount we're allowed to shift by during Two-Way
/// search.
///
/// When computing a critical factorization of the needle, we find the position
/// of the critical factorization by finding the needle's maximal (or minimal)
/// suffix, along with the period of that suffix. It turns out that the period
/// of that suffix is a lower bound on the period of the needle itself.
///
/// This lower bound is equivalent to the actual period of the needle in
/// some cases. To describe that case, we denote the needle as `x` where
/// `x = uv` and `v` is the lexicographic maximal suffix of `v`. The lower
/// bound given here is always the period of `v`, which is `<= period(x)`. The
/// case where `period(v) == period(x)` occurs when `len(u) < (len(x) / 2)` and
/// where `u` is a suffix of `v[0..period(v)]`.
///
/// This case is important because the search algorithm for when the
/// periods are equivalent is slightly different than the search algorithm
/// for when the periods are not equivalent. In particular, when they aren't
/// equivalent, we know that the period of the needle is no less than half its
/// length. In this case, we shift by an amount less than or equal to the
/// period of the needle (determined by the maximum length of the components
/// of the critical factorization of `x`, i.e., `max(len(u), len(v))`)..
///
/// The above two cases are represented by the variants below. Each entails
/// a different instantiation of the Two-Way search algorithm.
///
/// N.B. If we could find a way to compute the exact period in all cases,
/// then we could collapse this case analysis and simplify the algorithm. The
/// Two-Way paper suggests this is possible, but more reading is required to
/// grok why the authors didn't pursue that path.
#[derive(Clone, Debug)]
enum Shift {
    Small { period: usize },
    Large { shift: usize },
}

impl Shift {
    /// Compute the shift for a given needle in the forward direction.
    ///
    /// This requires a lower bound on the period and a critical position.
    /// These can be computed by extracting both the minimal and maximal
    /// lexicographic suffixes, and choosing the right-most starting position.
    /// The lower bound on the period is then the period of the chosen suffix.
    fn forward(
        needle: &BStr,
        period_lower_bound: usize,
        critical_pos: usize,
    ) -> Shift {
        let large = cmp::max(critical_pos, needle.len() - critical_pos);
        if critical_pos * 2 >= needle.len() {
            return Shift::Large { shift: large };
        }

        let (u, v) = needle.split_at(critical_pos);
        if !v[..period_lower_bound].ends_with(u) {
            return Shift::Large { shift: large };
        }
        Shift::Small { period: period_lower_bound }
    }

    /// Compute the shift for a given needle in the reverse direction.
    ///
    /// This requires a lower bound on the period and a critical position.
    /// These can be computed by extracting both the minimal and maximal
    /// lexicographic suffixes, and choosing the left-most starting position.
    /// The lower bound on the period is then the period of the chosen suffix.
    fn reverse(
        needle: &BStr,
        period_lower_bound: usize,
        critical_pos: usize,
    ) -> Shift {
        let large = cmp::max(critical_pos, needle.len() - critical_pos);
        if (needle.len() - critical_pos) * 2 >= needle.len() {
            return Shift::Large { shift: large };
        }

        let (v, u) = needle.split_at(critical_pos);
        if !v[v.len() - period_lower_bound..].starts_with(u) {
            return Shift::Large { shift: large };
        }
        Shift::Small { period: period_lower_bound }
    }
}

/// A suffix extracted from a needle along with its period.
#[derive(Debug)]
struct Suffix {
    /// The starting position of this suffix.
    ///
    /// If this is a forward suffix, then `&bytes[pos..]` can be used. If this
    /// is a reverse suffix, then `&bytes[..pos]` can be used. That is, for
    /// forward suffixes, this is an inclusive starting position, where as for
    /// reverse suffixes, this is an exclusive ending position.
    pos: usize,
    /// The period of this suffix.
    ///
    /// Note that this is NOT necessarily the period of the string from which
    /// this suffix comes from. (It is always less than or equal to the period
    /// of the original string.)
    period: usize,
}

impl Suffix {
    fn forward(needle: &BStr, kind: SuffixKind) -> Suffix {
        debug_assert!(!needle.is_empty());

        // suffix represents our maximal (or minimal) suffix, along with
        // its period.
        let mut suffix = Suffix { pos: 0, period: 1 };
        // The start of a suffix in `needle` that we are considering as a
        // more maximal (or minimal) suffix than what's in `suffix`.
        let mut candidate_start = 1;
        // The current offset of our suffixes that we're comparing.
        //
        // When the characters at this offset are the same, then we mush on
        // to the next position since no decision is possible. When the
        // candidate's character is greater (or lesser) than the corresponding
        // character than our current maximal (or minimal) suffix, then the
        // current suffix is changed over to the candidate and we restart our
        // search. Otherwise, the candidate suffix is no good and we restart
        // our search on the next candidate.
        //
        // The three cases above correspond to the three cases in the loop
        // below.
        let mut offset = 0;

        while candidate_start + offset < needle.len() {
            let current = needle[suffix.pos + offset];
            let candidate = needle[candidate_start + offset];
            match kind.cmp(current, candidate) {
                SuffixOrdering::Accept => {
                    suffix = Suffix { pos: candidate_start, period: 1 };
                    candidate_start += 1;
                    offset = 0;
                }
                SuffixOrdering::Skip => {
                    candidate_start += offset + 1;
                    offset = 0;
                    suffix.period = candidate_start - suffix.pos;
                }
                SuffixOrdering::Push => {
                    if offset + 1 == suffix.period {
                        candidate_start += suffix.period;
                        offset = 0;
                    } else {
                        offset += 1;
                    }
                }
            }
        }
        suffix
    }

    fn reverse(needle: &BStr, kind: SuffixKind) -> Suffix {
        debug_assert!(!needle.is_empty());

        // See the comments in `forward` for how this works.
        let mut suffix = Suffix { pos: needle.len(), period: 1 };
        if needle.len() == 1 {
            return suffix;
        }
        let mut candidate_start = needle.len() - 1;
        let mut offset = 0;

        while offset < candidate_start {
            let current = needle[suffix.pos - offset - 1];
            let candidate = needle[candidate_start - offset - 1];
            match kind.cmp(current, candidate) {
                SuffixOrdering::Accept => {
                    suffix = Suffix { pos: candidate_start, period: 1 };
                    candidate_start -= 1;
                    offset = 0;
                }
                SuffixOrdering::Skip => {
                    candidate_start -= offset + 1;
                    offset = 0;
                    suffix.period = suffix.pos - candidate_start;
                }
                SuffixOrdering::Push => {
                    if offset + 1 == suffix.period {
                        candidate_start -= suffix.period;
                        offset = 0;
                    } else {
                        offset += 1;
                    }
                }
            }
        }
        suffix
    }
}

/// The kind of suffix to extract.
#[derive(Clone, Copy, Debug)]
enum SuffixKind {
    /// Extract the smallest lexicographic suffix from a string.
    ///
    /// Technically, this doesn't actually pick the smallest lexicographic
    /// suffix. e.g., Given the choice between `a` and `aa`, this will choose
    /// the latter over the former, even though `a < aa`. The reasoning for
    /// this isn't clear from the paper, but it still smells like a minimal
    /// suffix.
    Minimal,
    /// Extract the largest lexicographic suffix from a string.
    ///
    /// Unlike `Minimal`, this really does pick the maximum suffix. e.g., Given
    /// the choice between `z` and `zz`, this will choose the latter over the
    /// former.
    Maximal,
}

/// The result of comparing corresponding bytes between two suffixes.
#[derive(Clone, Copy, Debug)]
enum SuffixOrdering {
    /// This occurs when the given candidate byte indicates that the candidate
    /// suffix is better than the current maximal (or minimal) suffix. That is,
    /// the current candidate suffix should supplant the current maximal (or
    /// minimal) suffix.
    Accept,
    /// This occurs when the given candidate byte excludes the candidate suffix
    /// from being better than the current maximal (or minimal) suffix. That
    /// is, the current candidate suffix should be dropped and the next one
    /// should be considered.
    Skip,
    /// This occurs when no decision to accept or skip the candidate suffix
    /// can be made, e.g., when corresponding bytes are equivalent. In this
    /// case, the next corresponding bytes should be compared.
    Push,
}

impl SuffixKind {
    /// Returns true if and only if the given candidate byte indicates that
    /// it should replace the current suffix as the maximal (or minimal)
    /// suffix.
    fn cmp(self, current: u8, candidate: u8) -> SuffixOrdering {
        use self::SuffixOrdering::*;

        match self {
            SuffixKind::Minimal if candidate < current => Accept,
            SuffixKind::Minimal if candidate > current => Skip,
            SuffixKind::Minimal => Push,
            SuffixKind::Maximal if candidate > current => Accept,
            SuffixKind::Maximal if candidate < current => Skip,
            SuffixKind::Maximal => Push,
        }
    }
}

// N.B. There are more holistic tests in src/search/tests.rs.
#[cfg(test)]
mod tests {
    use bstr::{B, BStr};
    use bstring::BString;

    use super::*;

    /// Convenience wrapper for computing the suffix as a byte string.
    fn get_suffix_forward(needle: &BStr, kind: SuffixKind) -> (&BStr, usize) {
        let s = Suffix::forward(needle, kind);
        (&needle[s.pos..], s.period)
    }

    /// Convenience wrapper for computing the reverse suffix as a byte string.
    fn get_suffix_reverse(needle: &BStr, kind: SuffixKind) -> (&BStr, usize) {
        let s = Suffix::reverse(needle, kind);
        (&needle[..s.pos], s.period)
    }

    /// Return all of the non-empty suffixes in the given byte string.
    fn suffixes(bytes: &BStr) -> Vec<&BStr> {
        (0..bytes.len()).map(|i| &bytes[i..]).collect()
    }

    /// Return the lexicographically maximal suffix of the given byte string.
    fn naive_maximal_suffix_forward(needle: &BStr) -> &BStr {
        let mut sufs = suffixes(needle);
        sufs.sort();
        sufs.pop().unwrap()
    }

    /// Return the lexicographically maximal suffix of the reverse of the given
    /// byte string.
    fn naive_maximal_suffix_reverse(needle: &BStr) -> BString {
        let mut reversed = needle.to_bstring();
        reversed.reverse_bytes();
        let mut got = naive_maximal_suffix_forward(&reversed).to_bstring();
        got.reverse_bytes();
        got
    }

    #[test]
    fn suffix_forward() {
        macro_rules! assert_suffix_min {
            ($given:expr, $expected:expr, $period:expr) => {
                let (got_suffix, got_period) = get_suffix_forward(
                    B($given),
                    SuffixKind::Minimal,
                );
                assert_eq!((B($expected), $period), (got_suffix, got_period));
            };
        }

        macro_rules! assert_suffix_max {
            ($given:expr, $expected:expr, $period:expr) => {
                let (got_suffix, got_period) = get_suffix_forward(
                    B($given),
                    SuffixKind::Maximal,
                );
                assert_eq!((B($expected), $period), (got_suffix, got_period));
            };
        }

        assert_suffix_min!("a", "a", 1);
        assert_suffix_max!("a", "a", 1);

        assert_suffix_min!("ab", "ab", 2);
        assert_suffix_max!("ab", "b", 1);

        assert_suffix_min!("ba", "a", 1);
        assert_suffix_max!("ba", "ba", 2);

        assert_suffix_min!("abc", "abc", 3);
        assert_suffix_max!("abc", "c", 1);

        assert_suffix_min!("acb", "acb", 3);
        assert_suffix_max!("acb", "cb", 2);

        assert_suffix_min!("cba", "a", 1);
        assert_suffix_max!("cba", "cba", 3);

        assert_suffix_min!("abcabc", "abcabc", 3);
        assert_suffix_max!("abcabc", "cabc", 3);

        assert_suffix_min!("abcabcabc", "abcabcabc", 3);
        assert_suffix_max!("abcabcabc", "cabcabc", 3);

        assert_suffix_min!("abczz", "abczz", 5);
        assert_suffix_max!("abczz", "zz", 1);

        assert_suffix_min!("zzabc", "abc", 3);
        assert_suffix_max!("zzabc", "zzabc", 5);

        assert_suffix_min!("aaa", "aaa", 1);
        assert_suffix_max!("aaa", "aaa", 1);

        assert_suffix_min!("foobar", "ar", 2);
        assert_suffix_max!("foobar", "r", 1);
    }

    #[test]
    fn suffix_reverse() {
        macro_rules! assert_suffix_min {
            ($given:expr, $expected:expr, $period:expr) => {
                let (got_suffix, got_period) = get_suffix_reverse(
                    B($given),
                    SuffixKind::Minimal,
                );
                assert_eq!((B($expected), $period), (got_suffix, got_period));
            };
        }

        macro_rules! assert_suffix_max {
            ($given:expr, $expected:expr, $period:expr) => {
                let (got_suffix, got_period) = get_suffix_reverse(
                    B($given),
                    SuffixKind::Maximal,
                );
                assert_eq!((B($expected), $period), (got_suffix, got_period));
            };
        }

        assert_suffix_min!("a", "a", 1);
        assert_suffix_max!("a", "a", 1);

        assert_suffix_min!("ab", "a", 1);
        assert_suffix_max!("ab", "ab", 2);

        assert_suffix_min!("ba", "ba", 2);
        assert_suffix_max!("ba", "b", 1);

        assert_suffix_min!("abc", "a", 1);
        assert_suffix_max!("abc", "abc", 3);

        assert_suffix_min!("acb", "a", 1);
        assert_suffix_max!("acb", "ac", 2);

        assert_suffix_min!("cba", "cba", 3);
        assert_suffix_max!("cba", "c", 1);

        assert_suffix_min!("abcabc", "abca", 3);
        assert_suffix_max!("abcabc", "abcabc", 3);

        assert_suffix_min!("abcabcabc", "abcabca", 3);
        assert_suffix_max!("abcabcabc", "abcabcabc", 3);

        assert_suffix_min!("abczz", "a", 1);
        assert_suffix_max!("abczz", "abczz", 5);

        assert_suffix_min!("zzabc", "zza", 3);
        assert_suffix_max!("zzabc", "zz", 1);

        assert_suffix_min!("aaa", "aaa", 1);
        assert_suffix_max!("aaa", "aaa", 1);
    }

    quickcheck! {
        fn qc_suffix_forward_maximal(bytes: Vec<u8>) -> bool {
            let bytes = BString::from(bytes);
            if bytes.is_empty() {
                return true;
            }

            let (got, _) = get_suffix_forward(&bytes, SuffixKind::Maximal);
            let expected = naive_maximal_suffix_forward(&bytes);
            got == expected
        }

        fn qc_suffix_reverse_maximal(bytes: Vec<u8>) -> bool {
            let bytes = BString::from(bytes);
            if bytes.is_empty() {
                return true;
            }

            let (got, _) = get_suffix_reverse(&bytes, SuffixKind::Maximal);
            let expected = naive_maximal_suffix_reverse(&bytes);
            got == expected
        }
    }
}