twoway/

lib.rs

#![cfg_attr(not(feature = "use_std"), no_std)]
#![cfg_attr(feature = "pattern", feature(pattern))]

//! **This crate is deprecated. Use crate `memchr` instead.**
//!
//! Fast substring search for strings and byte strings, using the [two-way algorithm][tw].
//! 
//! This is the same code as is included in Rust's libstd that powers
//! `str::find(&str)`, but here it is exposed with some improvements:
//! 
//! - Available for byte string searches using ``&[u8]``
//! - Having an optional SSE4.2 accelerated version (if detected at runtime) which is even faster.
//!   Runtime detection requires the default std feature.
//! - Using `memchr` for the single byte case, which is ultra fast.
//! 
//! [tw]: http://www-igm.univ-mlv.fr/~lecroq/string/node26.html

#[cfg(not(feature = "use_std"))]
extern crate core as std;

use std::cmp;
use std::usize;

extern crate memchr;

mod tw;
#[cfg(all(feature="benchmarks", any(target_arch = "x86", target_arch = "x86_64")))]
pub mod pcmp;
#[cfg(all(not(feature="benchmarks"), any(target_arch = "x86", target_arch = "x86_64")))]
mod pcmp;

#[cfg(feature="benchmarks")]
pub mod bmh;

#[cfg(feature = "pattern")]
use std::str::pattern::{
    Pattern,
    Searcher,
    ReverseSearcher,
    SearchStep,
};

/// `find_str` finds the first ocurrence of `pattern` in the `text`.
///
/// Uses the SSE42 version if it is available at runtime.
#[inline]
pub fn find_str(text: &str, pattern: &str) -> Option<usize> {
    find_bytes(text.as_bytes(), pattern.as_bytes())
}

/// `find_bytes` finds the first ocurrence of `pattern` in the `text`.
///
/// Uses the SSE42 version if it is available at runtime.
pub fn find_bytes(text: &[u8], pattern: &[u8]) -> Option<usize> {
    if pattern.is_empty() {
        Some(0)
    } else if text.len() < pattern.len() {
        return None;
    } else if pattern.len() == 1 {
        memchr::memchr(pattern[0], text)
    } else {
        #[cfg(any(target_arch = "x86", target_arch = "x86_64"))] {
            let compile_time_disable = option_env!("TWOWAY_TEST_DISABLE_PCMP")
                .map(|s| !s.is_empty())
                .unwrap_or(false);
            if !compile_time_disable && pcmp::is_supported() {
                return unsafe { pcmp::find_inner(text, pattern) };
            }
        }
        let mut searcher = TwoWaySearcher::new(pattern, text.len());
        let is_long = searcher.memory == usize::MAX;
        // write out `true` and `false` cases to encourage the compiler
        // to specialize the two cases separately.
        if is_long {
            searcher.next::<MatchOnly>(text, pattern, true).map(|t| t.0)
        } else {
            searcher.next::<MatchOnly>(text, pattern, false).map(|t| t.0)
        }
    }
}

/// `rfind_str` finds the last ocurrence of `pattern` in the `text`
/// and returns the index of the start of the match.
///
/// As of this writing, this function uses the two way algorithm
/// in pure rust (with no SSE4.2 support).
#[inline]
pub fn rfind_str(text: &str, pattern: &str) -> Option<usize> {
    rfind_bytes(text.as_bytes(), pattern.as_bytes())
}

/// `rfind_bytes` finds the last ocurrence of `pattern` in the `text`,
/// and returns the index of the start of the match.
///
/// As of this writing, this function uses the two way algorithm
/// in pure rust (with no SSE4.2 support).
pub fn rfind_bytes(text: &[u8], pattern: &[u8]) -> Option<usize> {
    if pattern.is_empty() {
        Some(text.len())
    } else if pattern.len() == 1 {
        memchr::memrchr(pattern[0], text)
    } else {
        let mut searcher = TwoWaySearcher::new(pattern, text.len());
        let is_long = searcher.memory == usize::MAX;
        // write out `true` and `false` cases to encourage the compiler
        // to specialize the two cases separately.
        if is_long {
            searcher.next_back::<MatchOnly>(text, pattern, true).map(|t| t.0)
        } else {
            searcher.next_back::<MatchOnly>(text, pattern, false).map(|t| t.0)
        }
    }
}


/// Dummy wrapper for &str
#[doc(hidden)]
pub struct Str<'a>(pub &'a str);

#[cfg(feature = "pattern")]
/// Non-allocating substring search.
///
/// Will handle the pattern `""` as returning empty matches at each character
/// boundary.
impl<'a, 'b> Pattern<'a> for Str<'b> {
    type Searcher = StrSearcher<'a, 'b>;

    #[inline]
    fn into_searcher(self, haystack: &'a str) -> StrSearcher<'a, 'b> {
        StrSearcher::new(haystack, self.0)
    }

    /// Checks whether the pattern matches at the front of the haystack
    #[inline]
    fn is_prefix_of(self, haystack: &'a str) -> bool {
        let self_ = self.0;
        haystack.is_char_boundary(self_.len()) &&
            self_ == &haystack[..self_.len()]
    }

    /// Checks whether the pattern matches at the back of the haystack
    #[inline]
    fn is_suffix_of(self, haystack: &'a str) -> bool {
        let self_ = self.0;
        self_.len() <= haystack.len() &&
            haystack.is_char_boundary(haystack.len() - self_.len()) &&
            self_ == &haystack[haystack.len() - self_.len()..]
    }

}

#[derive(Clone, Debug)]
#[doc(hidden)]
/// Associated type for `<&str as Pattern<'a>>::Searcher`.
pub struct StrSearcher<'a, 'b> {
    haystack: &'a str,
    needle: &'b str,

    searcher: StrSearcherImpl,
}

#[derive(Clone, Debug)]
enum StrSearcherImpl {
    Empty(EmptyNeedle),
    TwoWay(TwoWaySearcher),
}

#[derive(Clone, Debug)]
struct EmptyNeedle {
    position: usize,
    end: usize,
    is_match_fw: bool,
    is_match_bw: bool,
}

impl<'a, 'b> StrSearcher<'a, 'b> {
    pub fn new(haystack: &'a str, needle: &'b str) -> StrSearcher<'a, 'b> {
        if needle.is_empty() {
            StrSearcher {
                haystack: haystack,
                needle: needle,
                searcher: StrSearcherImpl::Empty(EmptyNeedle {
                    position: 0,
                    end: haystack.len(),
                    is_match_fw: true,
                    is_match_bw: true,
                }),
            }
        } else {
            StrSearcher {
                haystack: haystack,
                needle: needle,
                searcher: StrSearcherImpl::TwoWay(
                    TwoWaySearcher::new(needle.as_bytes(), haystack.len())
                ),
            }
        }
    }
}

#[cfg(feature = "pattern")]
unsafe impl<'a, 'b> Searcher<'a> for StrSearcher<'a, 'b> {
    fn haystack(&self) -> &'a str { self.haystack }

    #[inline]
    fn next(&mut self) -> SearchStep {
        match self.searcher {
            StrSearcherImpl::Empty(ref mut searcher) => {
                // empty needle rejects every char and matches every empty string between them
                let is_match = searcher.is_match_fw;
                searcher.is_match_fw = !searcher.is_match_fw;
                let pos = searcher.position;
                match self.haystack[pos..].chars().next() {
                    _ if is_match => SearchStep::Match(pos, pos),
                    None => SearchStep::Done,
                    Some(ch) => {
                        searcher.position += ch.len_utf8();
                        SearchStep::Reject(pos, searcher.position)
                    }
                }
            }
            StrSearcherImpl::TwoWay(ref mut searcher) => {
                // TwoWaySearcher produces valid *Match* indices that split at char boundaries
                // as long as it does correct matching and that haystack and needle are
                // valid UTF-8
                // *Rejects* from the algorithm can fall on any indices, but we will walk them
                // manually to the next character boundary, so that they are utf-8 safe.
                if searcher.position == self.haystack.len() {
                    return SearchStep::Done;
                }
                let is_long = searcher.memory == usize::MAX;
                match searcher.next::<RejectAndMatch>(self.haystack.as_bytes(),
                                                      self.needle.as_bytes(),
                                                      is_long)
                {
                    SearchStep::Reject(a, mut b) => {
                        // skip to next char boundary
                        while !self.haystack.is_char_boundary(b) {
                            b += 1;
                        }
                        searcher.position = cmp::max(b, searcher.position);
                        SearchStep::Reject(a, b)
                    }
                    otherwise => otherwise,
                }
            }
        }
    }

    #[inline(always)]
    fn next_match(&mut self) -> Option<(usize, usize)> {
        match self.searcher {
            StrSearcherImpl::Empty(..) => {
                loop {
                    match self.next() {
                        SearchStep::Match(a, b) => return Some((a, b)),
                        SearchStep::Done => return None,
                        SearchStep::Reject(..) => { }
                    }
                }
            }

            StrSearcherImpl::TwoWay(ref mut searcher) => {
                let is_long = searcher.memory == usize::MAX;
                // write out `true` and `false` cases to encourage the compiler
                // to specialize the two cases separately.
                if is_long {
                    searcher.next::<MatchOnly>(self.haystack.as_bytes(),
                                               self.needle.as_bytes(),
                                               true)
                } else {
                    searcher.next::<MatchOnly>(self.haystack.as_bytes(),
                                               self.needle.as_bytes(),
                                               false)
                }
            }
        }
    }
}

#[cfg(feature = "pattern")]
unsafe impl<'a, 'b> ReverseSearcher<'a> for StrSearcher<'a, 'b> {
    #[inline]
    fn next_back(&mut self) -> SearchStep {
        match self.searcher {
            StrSearcherImpl::Empty(ref mut searcher) => {
                let is_match = searcher.is_match_bw;
                searcher.is_match_bw = !searcher.is_match_bw;
                let end = searcher.end;
                match self.haystack[..end].chars().next_back() {
                    _ if is_match => SearchStep::Match(end, end),
                    None => SearchStep::Done,
                    Some(ch) => {
                        searcher.end -= ch.len_utf8();
                        SearchStep::Reject(searcher.end, end)
                    }
                }
            }
            StrSearcherImpl::TwoWay(ref mut searcher) => {
                if searcher.end == 0 {
                    return SearchStep::Done;
                }
                let is_long = searcher.memory == usize::MAX;
                match searcher.next_back::<RejectAndMatch>(self.haystack.as_bytes(),
                                                           self.needle.as_bytes(),
                                                           is_long)
                {
                    SearchStep::Reject(mut a, b) => {
                        // skip to next char boundary
                        while !self.haystack.is_char_boundary(a) {
                            a -= 1;
                        }
                        searcher.end = cmp::min(a, searcher.end);
                        SearchStep::Reject(a, b)
                    }
                    otherwise => otherwise,
                }
            }
        }
    }

    #[inline]
    fn next_match_back(&mut self) -> Option<(usize, usize)> {
        match self.searcher {
            StrSearcherImpl::Empty(..) => {
                loop {
                    match self.next_back() {
                        SearchStep::Match(a, b) => return Some((a, b)),
                        SearchStep::Done => return None,
                        SearchStep::Reject(..) => { }
                    }
                }
            }
            StrSearcherImpl::TwoWay(ref mut searcher) => {
                let is_long = searcher.memory == usize::MAX;
                // write out `true` and `false`, like `next_match`
                if is_long {
                    searcher.next_back::<MatchOnly>(self.haystack.as_bytes(),
                                                    self.needle.as_bytes(),
                                                    true)
                } else {
                    searcher.next_back::<MatchOnly>(self.haystack.as_bytes(),
                                                    self.needle.as_bytes(),
                                                    false)
                }
            }
        }
    }
}

/// The internal state of the two-way substring search algorithm.
#[derive(Clone, Debug)]
#[doc(hidden)]
pub struct TwoWaySearcher {
    // constants
    /// critical factorization index
    crit_pos: usize,
    /// critical factorization index for reversed needle
    crit_pos_back: usize,
    period: usize,
    /// `byteset` is an extension (not part of the two way algorithm);
    /// it's a 64-bit "fingerprint" where each set bit `j` corresponds
    /// to a (byte & 63) == j present in the needle.
    byteset: u64,

    // variables
    position: usize,
    end: usize,
    /// index into needle before which we have already matched
    memory: usize,
    /// index into needle after which we have already matched
    memory_back: usize,
}

/*
    This is the Two-Way search algorithm, which was introduced in the paper:
    Crochemore, M., Perrin, D., 1991, Two-way string-matching, Journal of the ACM 38(3):651-675.

    Here's some background information.

    A *word* is a string of symbols. The *length* of a word should be a familiar
    notion, and here we denote it for any word x by |x|.
    (We also allow for the possibility of the *empty word*, a word of length zero).

    If x is any non-empty word, then an integer p with 0 < p <= |x| is said to be a
    *period* for x iff for all i with 0 <= i <= |x| - p - 1, we have x[i] == x[i+p].
    For example, both 1 and 2 are periods for the string "aa". As another example,
    the only period of the string "abcd" is 4.

    We denote by period(x) the *smallest* period of x (provided that x is non-empty).
    This is always well-defined since every non-empty word x has at least one period,
    |x|. We sometimes call this *the period* of x.

    If u, v and x are words such that x = uv, where uv is the concatenation of u and
    v, then we say that (u, v) is a *factorization* of x.

    Let (u, v) be a factorization for a word x. Then if w is a non-empty word such
    that both of the following hold

      - either w is a suffix of u or u is a suffix of w
      - either w is a prefix of v or v is a prefix of w

    then w is said to be a *repetition* for the factorization (u, v).

    Just to unpack this, there are four possibilities here. Let w = "abc". Then we
    might have:

      - w is a suffix of u and w is a prefix of v. ex: ("lolabc", "abcde")
      - w is a suffix of u and v is a prefix of w. ex: ("lolabc", "ab")
      - u is a suffix of w and w is a prefix of v. ex: ("bc", "abchi")
      - u is a suffix of w and v is a prefix of w. ex: ("bc", "a")

    Note that the word vu is a repetition for any factorization (u,v) of x = uv,
    so every factorization has at least one repetition.

    If x is a string and (u, v) is a factorization for x, then a *local period* for
    (u, v) is an integer r such that there is some word w such that |w| = r and w is
    a repetition for (u, v).

    We denote by local_period(u, v) the smallest local period of (u, v). We sometimes
    call this *the local period* of (u, v). Provided that x = uv is non-empty, this
    is well-defined (because each non-empty word has at least one factorization, as
    noted above).

    It can be proven that the following is an equivalent definition of a local period
    for a factorization (u, v): any positive integer r such that x[i] == x[i+r] for
    all i such that |u| - r <= i <= |u| - 1 and such that both x[i] and x[i+r] are
    defined. (i.e. i > 0 and i + r < |x|).

    Using the above reformulation, it is easy to prove that

        1 <= local_period(u, v) <= period(uv)

    A factorization (u, v) of x such that local_period(u,v) = period(x) is called a
    *critical factorization*.

    The algorithm hinges on the following theorem, which is stated without proof:

    **Critical Factorization Theorem** Any word x has at least one critical
    factorization (u, v) such that |u| < period(x).

    The purpose of maximal_suffix is to find such a critical factorization.

    If the period is short, compute another factorization x = u' v' to use
    for reverse search, chosen instead so that |v'| < period(x).

*/
impl TwoWaySearcher {
    pub fn new(needle: &[u8], end: usize) -> TwoWaySearcher {
        let (crit_pos, period) = TwoWaySearcher::crit_params(needle);

        // A particularly readable explanation of what's going on here can be found
        // in Crochemore and Rytter's book "Text Algorithms", ch 13. Specifically
        // see the code for "Algorithm CP" on p. 323.
        //
        // What's going on is we have some critical factorization (u, v) of the
        // needle, and we want to determine whether u is a suffix of
        // &v[..period]. If it is, we use "Algorithm CP1". Otherwise we use
        // "Algorithm CP2", which is optimized for when the period of the needle
        // is large.
        if &needle[..crit_pos] == &needle[period.. period + crit_pos] {
            // short period case -- the period is exact
            // compute a separate critical factorization for the reversed needle
            // x = u' v' where |v'| < period(x).
            //
            // This is sped up by the period being known already.
            // Note that a case like x = "acba" may be factored exactly forwards
            // (crit_pos = 1, period = 3) while being factored with approximate
            // period in reverse (crit_pos = 2, period = 2). We use the given
            // reverse factorization but keep the exact period.
            let crit_pos_back = needle.len() - cmp::max(
                TwoWaySearcher::reverse_maximal_suffix(needle, period, false),
                TwoWaySearcher::reverse_maximal_suffix(needle, period, true));

            TwoWaySearcher {
                crit_pos: crit_pos,
                crit_pos_back: crit_pos_back,
                period: period,
                byteset: Self::byteset_create(&needle[..period]),

                position: 0,
                end: end,
                memory: 0,
                memory_back: needle.len(),
            }
        } else {
            // long period case -- we have an approximation to the actual period,
            // and don't use memorization.
            //
            // Approximate the period by lower bound max(|u|, |v|) + 1.
            // The critical factorization is efficient to use for both forward and
            // reverse search.

            TwoWaySearcher {
                crit_pos: crit_pos,
                crit_pos_back: crit_pos,
                period: cmp::max(crit_pos, needle.len() - crit_pos) + 1,
                byteset: Self::byteset_create(needle),

                position: 0,
                end: end,
                memory: usize::MAX, // Dummy value to signify that the period is long
                memory_back: usize::MAX,
            }
        }
    }

    /// Return the zero-based critical position and period of the provided needle.
    ///
    /// The returned period is incorrect when the actual period is "long." In
    /// that case the approximation must be computed separately.
    #[inline(always)]
    fn crit_params(needle: &[u8]) -> (usize, usize) {
        let (crit_pos_false, period_false) = TwoWaySearcher::maximal_suffix(needle, false);
        let (crit_pos_true, period_true) = TwoWaySearcher::maximal_suffix(needle, true);

        if crit_pos_false > crit_pos_true {
            (crit_pos_false, period_false)
        } else {
            (crit_pos_true, period_true)
        }
    }

    #[inline]
    fn byteset_create(bytes: &[u8]) -> u64 {
        bytes.iter().fold(0, |a, &b| (1 << (b & 0x3f)) | a)
    }

    #[inline(always)]
    fn byteset_contains(&self, byte: u8) -> bool {
        (self.byteset >> ((byte & 0x3f) as usize)) & 1 != 0
    }

    // One of the main ideas of Two-Way is that we factorize the needle into
    // two halves, (u, v), and begin trying to find v in the haystack by scanning
    // left to right. If v matches, we try to match u by scanning right to left.
    // How far we can jump when we encounter a mismatch is all based on the fact
    // that (u, v) is a critical factorization for the needle.
    #[inline(always)]
    fn next<S>(&mut self, haystack: &[u8], needle: &[u8], long_period: bool)
        -> S::Output
        where S: TwoWayStrategy
    {
        // `next()` uses `self.position` as its cursor
        let old_pos = self.position;
        let needle_last = needle.len() - 1;
        'search: loop {
            // Check that we have room to search in
            // position + needle_last can not overflow if we assume slices
            // are bounded by isize's range.
            let tail_byte = match haystack.get(self.position + needle_last) {
                Some(&b) => b,
                None => {
                    self.position = haystack.len();
                    return S::rejecting(old_pos, self.position);
                }
            };

            if S::use_early_reject() && old_pos != self.position {
                return S::rejecting(old_pos, self.position);
            }

            // Quickly skip by large portions unrelated to our substring
            if !self.byteset_contains(tail_byte) {
                self.position += needle.len();
                if !long_period {
                    self.memory = 0;
                }
                continue 'search;
            }

            // See if the right part of the needle matches
            let start = if long_period { self.crit_pos }
                        else { cmp::max(self.crit_pos, self.memory) };
            for i in start..needle.len() {
                if needle[i] != haystack[self.position + i] {
                    self.position += i - self.crit_pos + 1;
                    if !long_period {
                        self.memory = 0;
                    }
                    continue 'search;
                }
            }

            // See if the left part of the needle matches
            let start = if long_period { 0 } else { self.memory };
            for i in (start..self.crit_pos).rev() {
                if needle[i] != haystack[self.position + i] {
                    self.position += self.period;
                    if !long_period {
                        self.memory = needle.len() - self.period;
                    }
                    continue 'search;
                }
            }

            // We have found a match!
            let match_pos = self.position;

            // Note: add self.period instead of needle.len() to have overlapping matches
            self.position += needle.len();
            if !long_period {
                self.memory = 0; // set to needle.len() - self.period for overlapping matches
            }

            return S::matching(match_pos, match_pos + needle.len());
        }
    }

    // Follows the ideas in `next()`.
    //
    // The definitions are symmetrical, with period(x) = period(reverse(x))
    // and local_period(u, v) = local_period(reverse(v), reverse(u)), so if (u, v)
    // is a critical factorization, so is (reverse(v), reverse(u)).
    //
    // For the reverse case we have computed a critical factorization x = u' v'
    // (field `crit_pos_back`). We need |u| < period(x) for the forward case and
    // thus |v'| < period(x) for the reverse.
    //
    // To search in reverse through the haystack, we search forward through
    // a reversed haystack with a reversed needle, matching first u' and then v'.
    #[inline]
    fn next_back<S>(&mut self, haystack: &[u8], needle: &[u8], long_period: bool)
        -> S::Output
        where S: TwoWayStrategy
    {
        // `next_back()` uses `self.end` as its cursor -- so that `next()` and `next_back()`
        // are independent.
        let old_end = self.end;
        'search: loop {
            // Check that we have room to search in
            // end - needle.len() will wrap around when there is no more room,
            // but due to slice length limits it can never wrap all the way back
            // into the length of haystack.
            let front_byte = match haystack.get(self.end.wrapping_sub(needle.len())) {
                Some(&b) => b,
                None => {
                    self.end = 0;
                    return S::rejecting(0, old_end);
                }
            };

            if S::use_early_reject() && old_end != self.end {
                return S::rejecting(self.end, old_end);
            }

            // Quickly skip by large portions unrelated to our substring
            if !self.byteset_contains(front_byte) {
                self.end -= needle.len();
                if !long_period {
                    self.memory_back = needle.len();
                }
                continue 'search;
            }

            // See if the left part of the needle matches
            let crit = if long_period { self.crit_pos_back }
                       else { cmp::min(self.crit_pos_back, self.memory_back) };
            for i in (0..crit).rev() {
                if needle[i] != haystack[self.end - needle.len() + i] {
                    self.end -= self.crit_pos_back - i;
                    if !long_period {
                        self.memory_back = needle.len();
                    }
                    continue 'search;
                }
            }

            // See if the right part of the needle matches
            let needle_end = if long_period { needle.len() }
                             else { self.memory_back };
            for i in self.crit_pos_back..needle_end {
                if needle[i] != haystack[self.end - needle.len() + i] {
                    self.end -= self.period;
                    if !long_period {
                        self.memory_back = self.period;
                    }
                    continue 'search;
                }
            }

            // We have found a match!
            let match_pos = self.end - needle.len();
            // Note: sub self.period instead of needle.len() to have overlapping matches
            self.end -= needle.len();
            if !long_period {
                self.memory_back = needle.len();
            }

            return S::matching(match_pos, match_pos + needle.len());
        }
    }

    // Compute the maximal suffix of `arr`.
    //
    // The maximal suffix is a possible critical factorization (u, v) of `arr`.
    //
    // Returns (`i`, `p`) where `i` is the starting index of v and `p` is the
    // period of v.
    //
    // `order_greater` determines if lexical order is `<` or `>`. Both
    // orders must be computed -- the ordering with the largest `i` gives
    // a critical factorization.
    //
    // For long period cases, the resulting period is not exact (it is too short).
    #[inline]
    pub fn maximal_suffix(arr: &[u8], order_greater: bool) -> (usize, usize) {
        let mut left = 0; // Corresponds to i in the paper
        let mut right = 1; // Corresponds to j in the paper
        let mut offset = 0; // Corresponds to k in the paper, but starting at 0
                            // to match 0-based indexing.
        let mut period = 1; // Corresponds to p in the paper

        while let Some(&a) = arr.get(right + offset) {
            // `left` will be inbounds when `right` is.
            let b = arr[left + offset];
            if (a < b && !order_greater) || (a > b && order_greater) {
                // Suffix is smaller, period is entire prefix so far.
                right += offset + 1;
                offset = 0;
                period = right - left;
            } else if a == b {
                // Advance through repetition of the current period.
                if offset + 1 == period {
                    right += offset + 1;
                    offset = 0;
                } else {
                    offset += 1;
                }
            } else {
                // Suffix is larger, start over from current location.
                left = right;
                right += 1;
                offset = 0;
                period = 1;
            }
        }
        (left, period)
    }

    // Compute the maximal suffix of the reverse of `arr`.
    //
    // The maximal suffix is a possible critical factorization (u', v') of `arr`.
    //
    // Returns `i` where `i` is the starting index of v', from the back;
    // returns immedately when a period of `known_period` is reached.
    //
    // `order_greater` determines if lexical order is `<` or `>`. Both
    // orders must be computed -- the ordering with the largest `i` gives
    // a critical factorization.
    //
    // For long period cases, the resulting period is not exact (it is too short).
    pub fn reverse_maximal_suffix(arr: &[u8], known_period: usize,
                                  order_greater: bool) -> usize
    {
        let mut left = 0; // Corresponds to i in the paper
        let mut right = 1; // Corresponds to j in the paper
        let mut offset = 0; // Corresponds to k in the paper, but starting at 0
                            // to match 0-based indexing.
        let mut period = 1; // Corresponds to p in the paper
        let n = arr.len();

        while right + offset < n {
            let a = arr[n - (1 + right + offset)];
            let b = arr[n - (1 + left + offset)];
            if (a < b && !order_greater) || (a > b && order_greater) {
                // Suffix is smaller, period is entire prefix so far.
                right += offset + 1;
                offset = 0;
                period = right - left;
            } else if a == b {
                // Advance through repetition of the current period.
                if offset + 1 == period {
                    right += offset + 1;
                    offset = 0;
                } else {
                    offset += 1;
                }
            } else {
                // Suffix is larger, start over from current location.
                left = right;
                right += 1;
                offset = 0;
                period = 1;
            }
            if period == known_period {
                break;
            }
        }
        debug_assert!(period <= known_period);
        left
    }
}

// TwoWayStrategy allows the algorithm to either skip non-matches as quickly
// as possible, or to work in a mode where it emits Rejects relatively quickly.
trait TwoWayStrategy {
    type Output;
    fn use_early_reject() -> bool;
    fn rejecting(usize, usize) -> Self::Output;
    fn matching(usize, usize) -> Self::Output;
}

/// Skip to match intervals as quickly as possible
enum MatchOnly { }

impl TwoWayStrategy for MatchOnly {
    type Output = Option<(usize, usize)>;

    #[inline]
    fn use_early_reject() -> bool { false }
    #[inline]
    fn rejecting(_a: usize, _b: usize) -> Self::Output { None }
    #[inline]
    fn matching(a: usize, b: usize) -> Self::Output { Some((a, b)) }
}

#[cfg(feature = "pattern")]
/// Emit Rejects regularly
enum RejectAndMatch { }

#[cfg(feature = "pattern")]
impl TwoWayStrategy for RejectAndMatch {
    type Output = SearchStep;

    #[inline]
    fn use_early_reject() -> bool { true }
    #[inline]
    fn rejecting(a: usize, b: usize) -> Self::Output { SearchStep::Reject(a, b) }
    #[inline]
    fn matching(a: usize, b: usize) -> Self::Output { SearchStep::Match(a, b) }
}


#[cfg(feature = "pattern")]
#[cfg(test)]
impl<'a, 'b> StrSearcher<'a, 'b> {
    fn twoway(&self) -> &TwoWaySearcher {
        match self.searcher {
            StrSearcherImpl::TwoWay(ref inner) => inner,
            _ => panic!("Not a TwoWaySearcher"),
        }
    }
}

#[cfg(feature = "pattern")]
#[test]
fn test_basic() {
    let t = StrSearcher::new("", "aab");
    println!("{:?}", t);
    let t = StrSearcher::new("", "abaaaba");
    println!("{:?}", t);
    let mut t = StrSearcher::new("GCATCGCAGAGAGTATACAGTACG", "GCAGAGAG");
    println!("{:?}", t);

    loop {
        match t.next() {
            SearchStep::Done => break,
            m => println!("{:?}", m),
        }
    }

    let mut t = StrSearcher::new("GCATCGCAGAGAGTATACAGTACG", "GCAGAGAG");
    println!("{:?}", t);

    loop {
        match t.next_back() {
            SearchStep::Done => break,
            m => println!("{:?}", m),
        }
    }

    let mut t = StrSearcher::new("banana", "nana");
    println!("{:?}", t);

    loop {
        match t.next() {
            SearchStep::Done => break,
            m => println!("{:?}", m),
        }
    }
}

#[cfg(feature = "pattern")]
#[cfg(test)]
fn contains(hay: &str, n: &str) -> bool {
    let mut tws = StrSearcher::new(hay, n);
    loop {
        match tws.next() {
            SearchStep::Done => return false,
            SearchStep::Match(..) => return true,
            _ => { }
        }
    }
}

#[cfg(feature = "pattern")]
#[cfg(test)]
fn contains_rev(hay: &str, n: &str) -> bool {
    let mut tws = StrSearcher::new(hay, n);
    loop {
        match tws.next_back() {
            SearchStep::Done => return false,
            SearchStep::Match(..) => return true,
            rej => { println!("{:?}", rej); }
        }
    }
}


#[cfg(feature = "pattern")]
#[test]
fn test_contains() {
    let h = "";
    let n = "";
    assert!(contains(h, n));
    assert!(contains_rev(h, n));

    let h = "BDC\0\0\0";
    let n = "BDC\u{0}";
    assert!(contains(h, n));
    assert!(contains_rev(h, n));


    let h = "ADA\0";
    let n = "ADA";
    assert!(contains(h, n));
    assert!(contains_rev(h, n));

    let h = "\u{0}\u{0}\u{0}\u{0}";
    let n = "\u{0}";
    assert!(contains(h, n));
    assert!(contains_rev(h, n));
}

#[cfg(feature = "pattern")]
#[test]
fn test_rev_2() {
    let h = "BDC\0\0\0";
    let n = "BDC\u{0}";
    let mut t = StrSearcher::new(h, n);
    println!("{:?}", t);
    println!("{:?}", h.contains(&n));

    loop {
        match t.next_back() {
            SearchStep::Done => break,
            m => println!("{:?}", m),
        }
    }

    let h = "aabaabx";
    let n = "aabaab";
    let mut t = StrSearcher::new(h, n);
    println!("{:?}", t);
    assert_eq!(t.twoway().crit_pos, 2);
    assert_eq!(t.twoway().crit_pos_back, 5);

    loop {
        match t.next_back() {
            SearchStep::Done => break,
            m => println!("{:?}", m),
        }
    }

    let h = "abababac";
    let n = "ababab";
    let mut t = StrSearcher::new(h, n);
    println!("{:?}", t);
    assert_eq!(t.twoway().crit_pos, 1);
    assert_eq!(t.twoway().crit_pos_back, 5);

    loop {
        match t.next_back() {
            SearchStep::Done => break,
            m => println!("{:?}", m),
        }
    }

    let h = "abababac";
    let n = "abab";
    let mut t = StrSearcher::new(h, n);
    println!("{:?}", t);

    loop {
        match t.next_back() {
            SearchStep::Done => break,
            m => println!("{:?}", m),
        }
    }

    let h = "baabbbaabc";
    let n = "baabb";
    let t = StrSearcher::new(h, n);
    println!("{:?}", t);
    assert_eq!(t.twoway().crit_pos, 3);
    assert_eq!(t.twoway().crit_pos_back, 3);

    let h = "aabaaaabaabxx";
    let n = "aabaaaabaa";
    let mut t = StrSearcher::new(h, n);
    println!("{:?}", t);

    loop {
        match t.next_back() {
            SearchStep::Done => break,
            m => println!("{:?}", m),
        }
    }

    let h = "babbabax";
    let n = "babbab";
    let mut t = StrSearcher::new(h, n);
    println!("{:?}", t);
    assert_eq!(t.twoway().crit_pos, 2);
    assert_eq!(t.twoway().crit_pos_back, 4);

    loop {
        match t.next_back() {
            SearchStep::Done => break,
            m => println!("{:?}", m),
        }
    }

    let h = "xacbaabcax";
    let n = "abca";
    let mut t = StrSearcher::new(h, n);
    assert_eq!(t.next_match_back(), Some((5, 9)));

    let h = "xacbaacbxxcba";
    let m = "acba";
    let mut s = StrSearcher::new(h, m);
    assert_eq!(s.next_match_back(), Some((1, 5)));
    assert_eq!(s.twoway().crit_pos, 1);
    assert_eq!(s.twoway().crit_pos_back, 2);
}

#[cfg(feature = "pattern")]
#[test]
fn test_rev_unicode() {
    let h = "ααααααβ";
    let n = "αβ";
    let mut t = StrSearcher::new(h, n);
    println!("{:?}", t);

    loop {
        match t.next() {
            SearchStep::Done => break,
            m => println!("{:?}", m),
        }
    }

    let mut t = StrSearcher::new(h, n);
    loop {
        match t.next_back() {
            SearchStep::Done => break,
            m => println!("{:?}", m),
        }
    }
}

#[test]
fn maximal_suffix() {
    assert_eq!((2, 1), TwoWaySearcher::maximal_suffix(b"aab", false));
    assert_eq!((0, 3), TwoWaySearcher::maximal_suffix(b"aab", true));

    assert_eq!((0, 3), TwoWaySearcher::maximal_suffix(b"aabaa", true));
    assert_eq!((2, 3), TwoWaySearcher::maximal_suffix(b"aabaa", false));

    assert_eq!((0, 7), TwoWaySearcher::maximal_suffix(b"gcagagag", false));
    assert_eq!((2, 2), TwoWaySearcher::maximal_suffix(b"gcagagag", true));

    // both of these factorizations are critial factorizations
    assert_eq!((2, 2), TwoWaySearcher::maximal_suffix(b"banana", false));
    assert_eq!((1, 2), TwoWaySearcher::maximal_suffix(b"banana", true));
    assert_eq!((0, 6), TwoWaySearcher::maximal_suffix(b"zanana", false));
    assert_eq!((1, 2), TwoWaySearcher::maximal_suffix(b"zanana", true));
}

#[test]
fn maximal_suffix_verbose() {
    fn maximal_suffix(arr: &[u8], order_greater: bool) -> (usize, usize) {
        let mut left: usize = 0; // Corresponds to i in the paper
        let mut right = 1; // Corresponds to j in the paper
        let mut offset = 0; // Corresponds to k in the paper
        let mut period = 1; // Corresponds to p in the paper

        macro_rules! asstr {
            ($e:expr) => (::std::str::from_utf8($e).unwrap())
        }

        while let Some(&a) = arr.get(right + offset) {
            // `left` will be inbounds when `right` is.
            debug_assert!(left <= right);
            let b = unsafe { *arr.get_unchecked(left + offset) };
            println!("str={}, l={}, r={}, offset={}, p={}", asstr!(arr), left, right, offset, period);
            if (a < b && !order_greater) || (a > b && order_greater) {
                // Suffix is smaller, period is entire prefix so far.
                right += offset + 1;
                offset = 0;
                period = right - left;
            } else if a == b {
                // Advance through repetition of the current period.
                if offset + 1 == period {
                    right += offset + 1;
                    offset = 0;
                } else {
                    offset += 1;
                }
            } else {
                // Suffix is larger, start over from current location.
                left = right;
                right += 1;
                offset = 0;
                period = 1;
            }
        }
        println!("str={}, l={}, r={}, offset={}, p={} ==END==", asstr!(arr), left, right, offset, period);
        (left, period)
    }

    fn reverse_maximal_suffix(arr: &[u8], known_period: usize, order_greater: bool) -> usize {
        let n = arr.len();
        let mut left: usize = 0; // Corresponds to i in the paper
        let mut right = 1; // Corresponds to j in the paper
        let mut offset = 0; // Corresponds to k in the paper
        let mut period = 1; // Corresponds to p in the paper

        macro_rules! asstr {
            ($e:expr) => (::std::str::from_utf8($e).unwrap())
        }

        while right + offset < n {
            // `left` will be inbounds when `right` is.
            debug_assert!(left <= right);
            let a = unsafe { *arr.get_unchecked(n - (1 + right + offset)) };
            let b = unsafe { *arr.get_unchecked(n - (1 + left + offset)) };
            println!("str={}, l={}, r={}, offset={}, p={}", asstr!(arr), left, right, offset, period);
            if (a < b && !order_greater) || (a > b && order_greater) {
                // Suffix is smaller, period is entire prefix so far.
                right += offset + 1;
                offset = 0;
                period = right - left;
                if period == known_period {
                    break;
                }
            } else if a == b {
                // Advance through repetition of the current period.
                if offset + 1 == period {
                    right += offset + 1;
                    offset = 0;
                } else {
                    offset += 1;
                }
            } else {
                // Suffix is larger, start over from current location.
                left = right;
                right += 1;
                offset = 0;
                period = 1;
            }
        }
        println!("str={}, l={}, r={}, offset={}, p={} ==END==", asstr!(arr), left, right, offset, period);
        debug_assert!(period == known_period);
        left
    }

    assert_eq!((2, 2), maximal_suffix(b"banana", false));
    assert_eq!((1, 2), maximal_suffix(b"banana", true));
    assert_eq!((0, 7), maximal_suffix(b"gcagagag", false));
    assert_eq!((2, 2), maximal_suffix(b"gcagagag", true));
    assert_eq!((2, 1), maximal_suffix(b"bac", false));
    assert_eq!((1, 2), maximal_suffix(b"bac", true));
    assert_eq!((0, 9), maximal_suffix(b"baaaaaaaa", false));
    assert_eq!((1, 1), maximal_suffix(b"baaaaaaaa", true));

    assert_eq!((2, 3), maximal_suffix(b"babbabbab", false));
    assert_eq!((1, 3), maximal_suffix(b"babbabbab", true));

    assert_eq!(2, reverse_maximal_suffix(b"babbabbab", 3, false));
    assert_eq!(1, reverse_maximal_suffix(b"babbabbab", 3, true));

    assert_eq!((0, 2), maximal_suffix(b"bababa", false));
    assert_eq!((1, 2), maximal_suffix(b"bababa", true));

    assert_eq!(1, reverse_maximal_suffix(b"bababa", 2, false));
    assert_eq!(0, reverse_maximal_suffix(b"bababa", 2, true));

    // NOTE: returns "long period" case per = 2, which is an approximation
    assert_eq!((2, 2), maximal_suffix(b"abca", false));
    assert_eq!((0, 3), maximal_suffix(b"abca", true));

    assert_eq!((3, 2), maximal_suffix(b"abcda", false));
    assert_eq!((0, 4), maximal_suffix(b"abcda", true));

    // "aöa"
    assert_eq!((1, 3), maximal_suffix(b"acba", false));
    assert_eq!((0, 3), maximal_suffix(b"acba", true));
    //assert_eq!(2, reverse_maximal_suffix(b"acba", 3, false));
    //assert_eq!(0, reverse_maximal_suffix(b"acba", 3, true));
}

#[cfg(feature = "pattern")]
#[test]
fn test_find_rfind() {
    fn find(hay: &str, pat: &str) -> Option<usize> {
        let mut t = pat.into_searcher(hay);
        t.next_match().map(|(x, _)| x)
    }

    fn rfind(hay: &str, pat: &str) -> Option<usize> {
        let mut t = pat.into_searcher(hay);
        t.next_match_back().map(|(x, _)| x)
    }

    // find every substring -- assert that it finds it, or an earlier occurence.
    let string = "Việt Namacbaabcaabaaba";
    for (i, ci) in string.char_indices() {
        let ip = i + ci.len_utf8();
        for j in string[ip..].char_indices()
                             .map(|(i, _)| i)
                             .chain(Some(string.len() - ip))
        {
            let pat = &string[i..ip + j];
            assert!(match find(string, pat) {
                None => false,
                Some(x) => x <= i,
            });
            assert!(match rfind(string, pat) {
                None => false,
                Some(x) => x >= i,
            });
        }
    }
}