use std::cmp;
use std::mem;
use aho_corasick::{self, packed, AhoCorasick, AhoCorasickBuilder};
use memchr::{memchr, memchr2, memchr3};
use syntax::hir::literal::{Literal, Literals};
use freqs::BYTE_FREQUENCIES;
#[derive(Clone, Debug)]
pub struct LiteralSearcher {
complete: bool,
lcp: FreqyPacked,
lcs: FreqyPacked,
matcher: Matcher,
}
#[derive(Clone, Debug)]
enum Matcher {
Empty,
Bytes(SingleByteSet),
FreqyPacked(FreqyPacked),
BoyerMoore(BoyerMooreSearch),
AC { ac: AhoCorasick<u32>, lits: Vec<Literal> },
Packed { s: packed::Searcher, lits: Vec<Literal> },
}
impl LiteralSearcher {
pub fn empty() -> Self {
Self::new(Literals::empty(), Matcher::Empty)
}
pub fn prefixes(lits: Literals) -> Self {
let matcher = Matcher::prefixes(&lits);
Self::new(lits, matcher)
}
pub fn suffixes(lits: Literals) -> Self {
let matcher = Matcher::suffixes(&lits);
Self::new(lits, matcher)
}
fn new(lits: Literals, matcher: Matcher) -> Self {
let complete = lits.all_complete();
LiteralSearcher {
complete: complete,
lcp: FreqyPacked::new(lits.longest_common_prefix().to_vec()),
lcs: FreqyPacked::new(lits.longest_common_suffix().to_vec()),
matcher: matcher,
}
}
pub fn complete(&self) -> bool {
self.complete && !self.is_empty()
}
#[cfg_attr(feature = "perf-inline", inline(always))]
pub fn find(&self, haystack: &[u8]) -> Option<(usize, usize)> {
use self::Matcher::*;
match self.matcher {
Empty => Some((0, 0)),
Bytes(ref sset) => sset.find(haystack).map(|i| (i, i + 1)),
FreqyPacked(ref s) => s.find(haystack).map(|i| (i, i + s.len())),
BoyerMoore(ref s) => s.find(haystack).map(|i| (i, i + s.len())),
AC { ref ac, .. } => {
ac.find(haystack).map(|m| (m.start(), m.end()))
}
Packed { ref s, .. } => {
s.find(haystack).map(|m| (m.start(), m.end()))
}
}
}
pub fn find_start(&self, haystack: &[u8]) -> Option<(usize, usize)> {
for lit in self.iter() {
if lit.len() > haystack.len() {
continue;
}
if lit == &haystack[0..lit.len()] {
return Some((0, lit.len()));
}
}
None
}
pub fn find_end(&self, haystack: &[u8]) -> Option<(usize, usize)> {
for lit in self.iter() {
if lit.len() > haystack.len() {
continue;
}
if lit == &haystack[haystack.len() - lit.len()..] {
return Some((haystack.len() - lit.len(), haystack.len()));
}
}
None
}
pub fn iter(&self) -> LiteralIter {
match self.matcher {
Matcher::Empty => LiteralIter::Empty,
Matcher::Bytes(ref sset) => LiteralIter::Bytes(&sset.dense),
Matcher::FreqyPacked(ref s) => LiteralIter::Single(&s.pat),
Matcher::BoyerMoore(ref s) => LiteralIter::Single(&s.pattern),
Matcher::AC { ref lits, .. } => LiteralIter::AC(lits),
Matcher::Packed { ref lits, .. } => LiteralIter::Packed(lits),
}
}
pub fn lcp(&self) -> &FreqyPacked {
&self.lcp
}
pub fn lcs(&self) -> &FreqyPacked {
&self.lcs
}
pub fn is_empty(&self) -> bool {
self.len() == 0
}
pub fn len(&self) -> usize {
use self::Matcher::*;
match self.matcher {
Empty => 0,
Bytes(ref sset) => sset.dense.len(),
FreqyPacked(_) => 1,
BoyerMoore(_) => 1,
AC { ref ac, .. } => ac.pattern_count(),
Packed { ref lits, .. } => lits.len(),
}
}
pub fn approximate_size(&self) -> usize {
use self::Matcher::*;
match self.matcher {
Empty => 0,
Bytes(ref sset) => sset.approximate_size(),
FreqyPacked(ref single) => single.approximate_size(),
BoyerMoore(ref single) => single.approximate_size(),
AC { ref ac, .. } => ac.heap_bytes(),
Packed { ref s, .. } => s.heap_bytes(),
}
}
}
impl Matcher {
fn prefixes(lits: &Literals) -> Self {
let sset = SingleByteSet::prefixes(lits);
Matcher::new(lits, sset)
}
fn suffixes(lits: &Literals) -> Self {
let sset = SingleByteSet::suffixes(lits);
Matcher::new(lits, sset)
}
fn new(lits: &Literals, sset: SingleByteSet) -> Self {
if lits.literals().is_empty() {
return Matcher::Empty;
}
if sset.dense.len() >= 26 {
return Matcher::Empty;
}
if sset.complete {
return Matcher::Bytes(sset);
}
if lits.literals().len() == 1 {
let lit = lits.literals()[0].to_vec();
if BoyerMooreSearch::should_use(lit.as_slice()) {
return Matcher::BoyerMoore(BoyerMooreSearch::new(lit));
} else {
return Matcher::FreqyPacked(FreqyPacked::new(lit));
}
}
let pats = lits.literals().to_owned();
let is_aho_corasick_fast = sset.dense.len() <= 1 && sset.all_ascii;
if lits.literals().len() <= 100 && !is_aho_corasick_fast {
let mut builder = packed::Config::new()
.match_kind(packed::MatchKind::LeftmostFirst)
.builder();
if let Some(s) = builder.extend(&pats).build() {
return Matcher::Packed { s, lits: pats };
}
}
let ac = AhoCorasickBuilder::new()
.match_kind(aho_corasick::MatchKind::LeftmostFirst)
.dfa(true)
.build_with_size::<u32, _, _>(&pats)
.unwrap();
Matcher::AC { ac, lits: pats }
}
}
#[derive(Debug)]
pub enum LiteralIter<'a> {
Empty,
Bytes(&'a [u8]),
Single(&'a [u8]),
AC(&'a [Literal]),
Packed(&'a [Literal]),
}
impl<'a> Iterator for LiteralIter<'a> {
type Item = &'a [u8];
fn next(&mut self) -> Option<Self::Item> {
match *self {
LiteralIter::Empty => None,
LiteralIter::Bytes(ref mut many) => {
if many.is_empty() {
None
} else {
let next = &many[0..1];
*many = &many[1..];
Some(next)
}
}
LiteralIter::Single(ref mut one) => {
if one.is_empty() {
None
} else {
let next = &one[..];
*one = &[];
Some(next)
}
}
LiteralIter::AC(ref mut lits) => {
if lits.is_empty() {
None
} else {
let next = &lits[0];
*lits = &lits[1..];
Some(&**next)
}
}
LiteralIter::Packed(ref mut lits) => {
if lits.is_empty() {
None
} else {
let next = &lits[0];
*lits = &lits[1..];
Some(&**next)
}
}
}
}
}
#[derive(Clone, Debug)]
struct SingleByteSet {
sparse: Vec<bool>,
dense: Vec<u8>,
complete: bool,
all_ascii: bool,
}
impl SingleByteSet {
fn new() -> SingleByteSet {
SingleByteSet {
sparse: vec![false; 256],
dense: vec![],
complete: true,
all_ascii: true,
}
}
fn prefixes(lits: &Literals) -> SingleByteSet {
let mut sset = SingleByteSet::new();
for lit in lits.literals() {
sset.complete = sset.complete && lit.len() == 1;
if let Some(&b) = lit.get(0) {
if !sset.sparse[b as usize] {
if b > 0x7F {
sset.all_ascii = false;
}
sset.dense.push(b);
sset.sparse[b as usize] = true;
}
}
}
sset
}
fn suffixes(lits: &Literals) -> SingleByteSet {
let mut sset = SingleByteSet::new();
for lit in lits.literals() {
sset.complete = sset.complete && lit.len() == 1;
if let Some(&b) = lit.get(lit.len().checked_sub(1).unwrap()) {
if !sset.sparse[b as usize] {
if b > 0x7F {
sset.all_ascii = false;
}
sset.dense.push(b);
sset.sparse[b as usize] = true;
}
}
}
sset
}
#[cfg_attr(feature = "perf-inline", inline(always))]
fn find(&self, text: &[u8]) -> Option<usize> {
match self.dense.len() {
0 => None,
1 => memchr(self.dense[0], text),
2 => memchr2(self.dense[0], self.dense[1], text),
3 => memchr3(self.dense[0], self.dense[1], self.dense[2], text),
_ => self._find(text),
}
}
fn _find(&self, haystack: &[u8]) -> Option<usize> {
for (i, &b) in haystack.iter().enumerate() {
if self.sparse[b as usize] {
return Some(i);
}
}
None
}
fn approximate_size(&self) -> usize {
(self.dense.len() * mem::size_of::<u8>())
+ (self.sparse.len() * mem::size_of::<bool>())
}
}
#[derive(Clone, Debug)]
pub struct FreqyPacked {
pat: Vec<u8>,
char_len: usize,
rare1: u8,
rare1i: usize,
rare2: u8,
rare2i: usize,
}
impl FreqyPacked {
fn new(pat: Vec<u8>) -> FreqyPacked {
if pat.is_empty() {
return FreqyPacked::empty();
}
let mut rare1 = pat[0];
let mut rare2 = pat[0];
for b in pat[1..].iter().cloned() {
if freq_rank(b) < freq_rank(rare1) {
rare1 = b;
}
}
for &b in &pat {
if rare1 == rare2 {
rare2 = b
} else if b != rare1 && freq_rank(b) < freq_rank(rare2) {
rare2 = b;
}
}
let rare1i = pat.iter().rposition(|&b| b == rare1).unwrap();
let rare2i = pat.iter().rposition(|&b| b == rare2).unwrap();
let char_len = char_len_lossy(&pat);
FreqyPacked {
pat: pat,
char_len: char_len,
rare1: rare1,
rare1i: rare1i,
rare2: rare2,
rare2i: rare2i,
}
}
fn empty() -> FreqyPacked {
FreqyPacked {
pat: vec![],
char_len: 0,
rare1: 0,
rare1i: 0,
rare2: 0,
rare2i: 0,
}
}
#[cfg_attr(feature = "perf-inline", inline(always))]
pub fn find(&self, haystack: &[u8]) -> Option<usize> {
let pat = &*self.pat;
if haystack.len() < pat.len() || pat.is_empty() {
return None;
}
let mut i = self.rare1i;
while i < haystack.len() {
i += match memchr(self.rare1, &haystack[i..]) {
None => return None,
Some(i) => i,
};
let start = i - self.rare1i;
let end = start + pat.len();
if end > haystack.len() {
return None;
}
let aligned = &haystack[start..end];
if aligned[self.rare2i] == self.rare2 && aligned == &*self.pat {
return Some(start);
}
i += 1;
}
None
}
#[cfg_attr(feature = "perf-inline", inline(always))]
pub fn is_suffix(&self, text: &[u8]) -> bool {
if text.len() < self.len() {
return false;
}
text[text.len() - self.len()..] == *self.pat
}
pub fn len(&self) -> usize {
self.pat.len()
}
pub fn char_len(&self) -> usize {
self.char_len
}
fn approximate_size(&self) -> usize {
self.pat.len() * mem::size_of::<u8>()
}
}
fn char_len_lossy(bytes: &[u8]) -> usize {
String::from_utf8_lossy(bytes).chars().count()
}
#[derive(Clone, Debug)]
pub struct BoyerMooreSearch {
pattern: Vec<u8>,
skip_table: Vec<usize>,
guard: u8,
guard_reverse_idx: usize,
md2_shift: usize,
}
impl BoyerMooreSearch {
fn new(pattern: Vec<u8>) -> Self {
debug_assert!(!pattern.is_empty());
let (g, gi) = Self::select_guard(pattern.as_slice());
let skip_table = Self::compile_skip_table(pattern.as_slice());
let md2_shift = Self::compile_md2_shift(pattern.as_slice());
BoyerMooreSearch {
pattern: pattern,
skip_table: skip_table,
guard: g,
guard_reverse_idx: gi,
md2_shift: md2_shift,
}
}
#[inline]
fn find(&self, haystack: &[u8]) -> Option<usize> {
if haystack.len() < self.pattern.len() {
return None;
}
let mut window_end = self.pattern.len() - 1;
const NUM_UNROLL: usize = 10;
let short_circut = (NUM_UNROLL + 2) * self.pattern.len();
if haystack.len() > short_circut {
let backstop =
haystack.len() - ((NUM_UNROLL + 1) * self.pattern.len());
loop {
window_end =
match self.skip_loop(haystack, window_end, backstop) {
Some(i) => i,
None => return None,
};
if window_end >= backstop {
break;
}
if self.check_match(haystack, window_end) {
return Some(window_end - (self.pattern.len() - 1));
} else {
let skip = self.skip_table[haystack[window_end] as usize];
window_end +=
if skip == 0 { self.md2_shift } else { skip };
continue;
}
}
}
while window_end < haystack.len() {
let mut skip = self.skip_table[haystack[window_end] as usize];
if skip == 0 {
if self.check_match(haystack, window_end) {
return Some(window_end - (self.pattern.len() - 1));
} else {
skip = self.md2_shift;
}
}
window_end += skip;
}
None
}
fn len(&self) -> usize {
return self.pattern.len();
}
fn should_use(pattern: &[u8]) -> bool {
const MIN_LEN: usize = 9;
const MIN_CUTOFF: usize = 150;
const MAX_CUTOFF: usize = 255;
const LEN_CUTOFF_PROPORTION: usize = 4;
let scaled_rank = pattern.len().wrapping_mul(LEN_CUTOFF_PROPORTION);
let cutoff = cmp::max(
MIN_CUTOFF,
MAX_CUTOFF - cmp::min(MAX_CUTOFF, scaled_rank),
);
pattern.len() > MIN_LEN
&& pattern.iter().all(|c| freq_rank(*c) >= cutoff)
}
#[inline]
fn check_match(&self, haystack: &[u8], window_end: usize) -> bool {
if haystack[window_end - self.guard_reverse_idx] != self.guard {
return false;
}
let window_start = window_end - (self.pattern.len() - 1);
for i in 0..self.pattern.len() {
if self.pattern[i] != haystack[window_start + i] {
return false;
}
}
true
}
#[inline]
fn skip_loop(
&self,
haystack: &[u8],
mut window_end: usize,
backstop: usize,
) -> Option<usize> {
let window_end_snapshot = window_end;
let skip_of = |we: usize| -> usize {
self.skip_table[haystack[we] as usize]
};
loop {
let mut skip = skip_of(window_end);
window_end += skip;
skip = skip_of(window_end);
window_end += skip;
if skip != 0 {
skip = skip_of(window_end);
window_end += skip;
skip = skip_of(window_end);
window_end += skip;
skip = skip_of(window_end);
window_end += skip;
if skip != 0 {
skip = skip_of(window_end);
window_end += skip;
skip = skip_of(window_end);
window_end += skip;
skip = skip_of(window_end);
window_end += skip;
if skip != 0 {
skip = skip_of(window_end);
window_end += skip;
skip = skip_of(window_end);
window_end += skip;
if window_end - window_end_snapshot
> 16 * mem::size_of::<usize>()
{
if window_end >= backstop {
return Some(window_end);
}
continue;
} else {
window_end = window_end
.checked_sub(1 + self.guard_reverse_idx)
.unwrap_or(0);
match memchr(self.guard, &haystack[window_end..]) {
None => return None,
Some(g_idx) => {
return Some(
window_end
+ g_idx
+ self.guard_reverse_idx,
);
}
}
}
}
}
}
return Some(window_end);
}
}
fn compile_skip_table(pattern: &[u8]) -> Vec<usize> {
let mut tab = vec![pattern.len(); 256];
for (i, c) in pattern.iter().enumerate() {
tab[*c as usize] = (pattern.len() - 1) - i;
}
tab
}
fn select_guard(pattern: &[u8]) -> (u8, usize) {
let mut rarest = pattern[0];
let mut rarest_rev_idx = pattern.len() - 1;
for (i, c) in pattern.iter().enumerate() {
if freq_rank(*c) < freq_rank(rarest) {
rarest = *c;
rarest_rev_idx = (pattern.len() - 1) - i;
}
}
(rarest, rarest_rev_idx)
}
fn compile_md2_shift(pattern: &[u8]) -> usize {
let shiftc = *pattern.last().unwrap();
if pattern.len() == 1 {
return 0xDEADBEAF;
}
let mut i = pattern.len() - 2;
while i > 0 {
if pattern[i] == shiftc {
return (pattern.len() - 1) - i;
}
i -= 1;
}
pattern.len() - 1
}
fn approximate_size(&self) -> usize {
(self.pattern.len() * mem::size_of::<u8>())
+ (256 * mem::size_of::<usize>())
}
}
fn freq_rank(b: u8) -> usize {
BYTE_FREQUENCIES[b as usize] as usize
}
#[cfg(test)]
mod tests {
use super::{BoyerMooreSearch, FreqyPacked};
#[test]
fn bm_find_subs() {
let searcher = BoyerMooreSearch::new(Vec::from(&b"pattern"[..]));
let haystack = b"I keep seeing patterns in this text";
assert_eq!(14, searcher.find(haystack).unwrap());
}
#[test]
fn bm_find_no_subs() {
let searcher = BoyerMooreSearch::new(Vec::from(&b"pattern"[..]));
let haystack = b"I keep seeing needles in this text";
assert_eq!(None, searcher.find(haystack));
}
#[test]
fn bm_skip_reset_bug() {
let haystack = vec![0, 0, 0, 0, 0, 1, 1, 0];
let needle = vec![0, 1, 1, 0];
let searcher = BoyerMooreSearch::new(needle);
let offset = searcher.find(haystack.as_slice()).unwrap();
assert_eq!(4, offset);
}
#[test]
fn bm_backstop_underflow_bug() {
let haystack = vec![0, 0];
let needle = vec![0, 0];
let searcher = BoyerMooreSearch::new(needle);
let offset = searcher.find(haystack.as_slice()).unwrap();
assert_eq!(0, offset);
}
#[test]
fn bm_naive_off_by_one_bug() {
let haystack = vec![91];
let needle = vec![91];
let naive_offset = naive_find(&needle, &haystack).unwrap();
assert_eq!(0, naive_offset);
}
#[test]
fn bm_memchr_fallback_indexing_bug() {
let mut haystack = vec![
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 87, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
];
let needle = vec![1, 1, 1, 1, 32, 32, 87];
let needle_start = haystack.len();
haystack.extend(needle.clone());
let searcher = BoyerMooreSearch::new(needle);
assert_eq!(needle_start, searcher.find(haystack.as_slice()).unwrap());
}
#[test]
fn bm_backstop_boundary() {
let haystack = b"\
// aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
e_data.clone_created(entity_id, entity_to_add.entity_id);
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
"
.to_vec();
let needle = b"clone_created".to_vec();
let searcher = BoyerMooreSearch::new(needle);
let result = searcher.find(&haystack);
assert_eq!(Some(43), result);
}
#[test]
fn bm_win_gnu_indexing_bug() {
let haystack_raw = vec![
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
];
let needle = vec![1, 1, 1, 1, 1, 1, 1];
let haystack = haystack_raw.as_slice();
BoyerMooreSearch::new(needle.clone()).find(haystack);
}
use quickcheck::TestResult;
fn naive_find(needle: &[u8], haystack: &[u8]) -> Option<usize> {
assert!(needle.len() <= haystack.len());
for i in 0..(haystack.len() - (needle.len() - 1)) {
if haystack[i] == needle[0]
&& &haystack[i..(i + needle.len())] == needle
{
return Some(i);
}
}
None
}
quickcheck! {
fn qc_bm_equals_nieve_find(pile1: Vec<u8>, pile2: Vec<u8>) -> TestResult {
if pile1.len() == 0 || pile2.len() == 0 {
return TestResult::discard();
}
let (needle, haystack) = if pile1.len() < pile2.len() {
(pile1, pile2.as_slice())
} else {
(pile2, pile1.as_slice())
};
let searcher = BoyerMooreSearch::new(needle.clone());
TestResult::from_bool(
searcher.find(haystack) == naive_find(&needle, haystack))
}
fn qc_bm_equals_single(pile1: Vec<u8>, pile2: Vec<u8>) -> TestResult {
if pile1.len() == 0 || pile2.len() == 0 {
return TestResult::discard();
}
let (needle, haystack) = if pile1.len() < pile2.len() {
(pile1, pile2.as_slice())
} else {
(pile2, pile1.as_slice())
};
let bm_searcher = BoyerMooreSearch::new(needle.clone());
let freqy_memchr = FreqyPacked::new(needle);
TestResult::from_bool(
bm_searcher.find(haystack) == freqy_memchr.find(haystack))
}
fn qc_bm_finds_trailing_needle(
haystack_pre: Vec<u8>,
needle: Vec<u8>
) -> TestResult {
if needle.len() == 0 {
return TestResult::discard();
}
let mut haystack = haystack_pre.clone();
let searcher = BoyerMooreSearch::new(needle.clone());
if haystack.len() >= needle.len() &&
searcher.find(haystack.as_slice()).is_some() {
return TestResult::discard();
}
haystack.extend(needle.clone());
let start = haystack_pre.len()
.checked_sub(needle.len())
.unwrap_or(0);
for i in 0..(needle.len() - 1) {
if searcher.find(&haystack[(i + start)..]).is_some() {
return TestResult::discard();
}
}
TestResult::from_bool(
searcher.find(haystack.as_slice())
.map(|x| x == haystack_pre.len())
.unwrap_or(false))
}
fn qc_bm_finds_subslice(
haystack: Vec<u8>,
needle_start: usize,
needle_length: usize
) -> TestResult {
if haystack.len() == 0 {
return TestResult::discard();
}
let needle_start = needle_start % haystack.len();
let needle_length = needle_length % (haystack.len() - needle_start);
if needle_length == 0 {
return TestResult::discard();
}
let needle = &haystack[needle_start..(needle_start + needle_length)];
let bm_searcher = BoyerMooreSearch::new(needle.to_vec());
let start = naive_find(&needle, &haystack);
match start {
None => TestResult::from_bool(false),
Some(nf_start) =>
TestResult::from_bool(
nf_start <= needle_start
&& bm_searcher.find(&haystack) == start
)
}
}
fn qc_bm_finds_first(needle: Vec<u8>) -> TestResult {
if needle.len() == 0 {
return TestResult::discard();
}
let mut haystack = needle.clone();
let searcher = BoyerMooreSearch::new(needle.clone());
haystack.extend(needle);
TestResult::from_bool(
searcher.find(haystack.as_slice())
.map(|x| x == 0)
.unwrap_or(false))
}
}
}