Skip to content

Commit e5ea128

Browse files
committed
prefilter: fix bug when doing a stream search
This fixes yet another bug in the prefilter. Sigh. This only occurs when doing a stream search. The problem is that the stream handling code assumes that if no match is found at the end of the buffer, then the current state of the automaton is correctly updated and the buffer can be rolled. With most prefilters that look for a candidate *start* of a match, this is okay. If a prefilter can't find anything, then there's nothing to start and the current state remains in the starting state. But if the prefilter looks for a byte that may not be at the start of the match---like the rare byte prefilter---then we cannot assume that a match doesn't begin near the end of the buffer searched. And in this case, the internal implementation of search doesn't correctly hold up it's contract because the current state won't be updated. That is, there is an embedded assumption that if a prefilter fails then there is no match and thus there is no need to update the current state ID. But of course, this is just not true in a streaming context. The right way to fix this is unfortunately to rethink how we've implemented stream searching and make it aware of these kinds of prefilters. I think, anyway. The other option would be to fix the lower level search APIs to always make sure the current state ID is correct. That would fix everything, but that seems tricky and probably requires some delicate handling. So for now, we just disable a prefilter entirely if it's a rare byte prefilter and we're doing a stream search. We could build a backup prefilter and still use that, but it feels like a gross hack. At least now, we preserve correctness. Kudos to @ogoffart who did the initial investigation here and came up with a regression test, which is included in this commit. Note though, that some tests do fail when the buffer's size is set to its minimum. So there was a regression at some point because we aren't getting the best test coverage. We should just bite the buffer and make the buffer size configurable as an internal API so that tests can tweak it and provoke more edge cases. Fixes #64
1 parent 39b029b commit e5ea128

5 files changed

Lines changed: 190 additions & 24 deletions

File tree

‎src/ahocorasick.rs‎

Lines changed: 24 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -6,7 +6,7 @@ use dfa::{self, DFA};
66
use error::Result;
77
use nfa::{self, NFA};
88
use packed;
9-
use prefilter::PrefilterState;
9+
use prefilter::{Prefilter, PrefilterState};
1010
use state_id::StateID;
1111
use Match;
1212

@@ -1075,6 +1075,24 @@ impl<S: StateID> Imp<S> {
10751075
}
10761076
}
10771077

1078+
/// Returns the prefilter object, if one exists, for the underlying
1079+
/// automaton.
1080+
fn prefilter(&self) -> Option<&dyn Prefilter> {
1081+
match *self {
1082+
Imp::NFA(ref nfa) => nfa.prefilter(),
1083+
Imp::DFA(ref dfa) => dfa.prefilter(),
1084+
}
1085+
}
1086+
1087+
/// Returns true if and only if we should attempt to use a prefilter.
1088+
fn use_prefilter(&self) -> bool {
1089+
let p = match self.prefilter() {
1090+
None => return false,
1091+
Some(p) => p,
1092+
};
1093+
!p.looks_for_non_start_of_match()
1094+
}
1095+
10781096
#[inline(always)]
10791097
fn overlapping_find_at(
10801098
&self,
@@ -1363,7 +1381,11 @@ impl<'a, R: io::Read, S: StateID> StreamChunkIter<'a, R, S> {
13631381
"stream searching is only supported for Standard match semantics"
13641382
);
13651383

1366-
let prestate = PrefilterState::new(ac.max_pattern_len());
1384+
let prestate = if ac.imp.use_prefilter() {
1385+
PrefilterState::new(ac.max_pattern_len())
1386+
} else {
1387+
PrefilterState::disabled()
1388+
};
13671389
let buf = Buffer::new(ac.imp.max_pattern_len());
13681390
let state_id = ac.imp.start_state();
13691391
StreamChunkIter {

‎src/buffer.rs‎

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -50,7 +50,9 @@ impl Buffer {
5050
// reasons, so we set a lower bound of `8 * min`.
5151
//
5252
// TODO: It would be good to find a way to test the streaming
53-
// implementation with the minimal buffer size.
53+
// implementation with the minimal buffer size. For now, we just
54+
// uncomment out the next line and comment out the subsequent line.
55+
// let capacity = 1 + min;
5456
let capacity = cmp::max(min * 8, DEFAULT_BUFFER_CAPACITY);
5557
Buffer { buf: vec![0; capacity], min, end: 0 }
5658
}

‎src/dfa.rs‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -43,6 +43,10 @@ impl<S: StateID> DFA<S> {
4343
self.repr().pattern_count
4444
}
4545

46+
pub fn prefilter(&self) -> Option<&dyn Prefilter> {
47+
self.repr().prefilter.as_ref().map(|p| p.as_ref())
48+
}
49+
4650
pub fn start_state(&self) -> S {
4751
self.repr().start_id
4852
}

‎src/prefilter.rs‎

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -80,6 +80,17 @@ pub trait Prefilter:
8080
fn reports_false_positives(&self) -> bool {
8181
true
8282
}
83+
84+
/// Returns true if and only if this prefilter may look for a non-starting
85+
/// position of a match.
86+
///
87+
/// This is useful in a streaming context where prefilters that don't look
88+
/// for a starting position of a match can be quite difficult to deal with.
89+
///
90+
/// This returns false by default.
91+
fn looks_for_non_start_of_match(&self) -> bool {
92+
false
93+
}
8394
}
8495

8596
impl<'a, P: Prefilter + ?Sized> Prefilter for &'a P {
@@ -191,6 +202,17 @@ impl PrefilterState {
191202
}
192203
}
193204

205+
/// Create a prefilter state that always disables the prefilter.
206+
pub fn disabled() -> PrefilterState {
207+
PrefilterState {
208+
skips: 0,
209+
skipped: 0,
210+
max_match_len: 0,
211+
inert: true,
212+
last_scan_at: 0,
213+
}
214+
}
215+
194216
/// Update this state with the number of bytes skipped on the last
195217
/// invocation of the prefilter.
196218
#[inline]
@@ -285,6 +307,7 @@ impl Builder {
285307
/// All patterns added to an Aho-Corasick automaton should be added to this
286308
/// builder before attempting to construct the prefilter.
287309
pub fn build(&self) -> Option<PrefilterObj> {
310+
// match (self.start_bytes.build(), self.rare_bytes.build()) {
288311
match (self.start_bytes.build(), self.rare_bytes.build()) {
289312
// If we could build both start and rare prefilters, then there are
290313
// a few cases in which we'd want to use the start-byte prefilter
@@ -663,6 +686,33 @@ impl Prefilter for RareBytesOne {
663686
fn heap_bytes(&self) -> usize {
664687
0
665688
}
689+
690+
fn looks_for_non_start_of_match(&self) -> bool {
691+
// TODO: It should be possible to use a rare byte prefilter in a
692+
// streaming context. The main problem is that we usually assume that
693+
// if a prefilter has scanned some text and not found anything, then no
694+
// match *starts* in that text. This doesn't matter in non-streaming
695+
// contexts, but in a streaming context, if we're looking for a byte
696+
// that doesn't start at the beginning of a match and don't find it,
697+
// then it's still possible for a match to start at the end of the
698+
// current buffer content. In order to fix this, the streaming searcher
699+
// would need to become aware of prefilters that do this and use the
700+
// appropriate offset in various places. It is quite a delicate change
701+
// and probably shouldn't be attempted until streaming search has a
702+
// better testing strategy. In particular, we'd really like to be able
703+
// to vary the buffer size to force strange cases that occur at the
704+
// edge of the buffer. If we make the buffer size minimal, then these
705+
// cases occur more frequently and easier.
706+
//
707+
// This is also a bummer because this means that if the prefilter
708+
// builder chose a rare byte prefilter, then a streaming search won't
709+
// use any prefilter at all because the builder doesn't know how it's
710+
// going to be used. Assuming we don't make streaming search aware of
711+
// these special types of prefilters as described above, we could fix
712+
// this by building a "backup" prefilter that could be used when the
713+
// rare byte prefilter could not. But that's a bandaide. Sigh.
714+
true
715+
}
666716
}
667717

668718
/// A prefilter for scanning for two "rare" bytes.
@@ -697,6 +747,11 @@ impl Prefilter for RareBytesTwo {
697747
fn heap_bytes(&self) -> usize {
698748
0
699749
}
750+
751+
fn looks_for_non_start_of_match(&self) -> bool {
752+
// TODO: See Prefilter impl for RareBytesOne.
753+
true
754+
}
700755
}
701756

702757
/// A prefilter for scanning for three "rare" bytes.
@@ -732,6 +787,11 @@ impl Prefilter for RareBytesThree {
732787
fn heap_bytes(&self) -> usize {
733788
0
734789
}
790+
791+
fn looks_for_non_start_of_match(&self) -> bool {
792+
// TODO: See Prefilter impl for RareBytesOne.
793+
true
794+
}
735795
}
736796

737797
/// A builder for constructing a starting byte prefilter.

‎src/tests.rs‎

Lines changed: 99 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -998,6 +998,31 @@ testconfig!(
998998
}
999999
);
10001000

1001+
fn run_search_tests<F: FnMut(&SearchTest) -> Vec<Match>>(
1002+
which: TestCollection,
1003+
mut f: F,
1004+
) {
1005+
let get_match_triples =
1006+
|matches: Vec<Match>| -> Vec<(usize, usize, usize)> {
1007+
matches
1008+
.into_iter()
1009+
.map(|m| (m.pattern(), m.start(), m.end()))
1010+
.collect()
1011+
};
1012+
for &tests in which {
1013+
for test in tests {
1014+
assert_eq!(
1015+
test.matches,
1016+
get_match_triples(f(&test)).as_slice(),
1017+
"test: {}, patterns: {:?}, haystack: {:?}",
1018+
test.name,
1019+
test.patterns,
1020+
test.haystack
1021+
);
1022+
}
1023+
}
1024+
}
1025+
10011026
#[test]
10021027
fn search_tests_have_unique_names() {
10031028
let assert = |constname, tests: &[SearchTest]| {
@@ -1126,27 +1151,80 @@ fn regression_case_insensitive_prefilter() {
11261151
}
11271152
}
11281153

1129-
fn run_search_tests<F: FnMut(&SearchTest) -> Vec<Match>>(
1130-
which: TestCollection,
1131-
mut f: F,
1132-
) {
1133-
let get_match_triples =
1134-
|matches: Vec<Match>| -> Vec<(usize, usize, usize)> {
1135-
matches
1136-
.into_iter()
1137-
.map(|m| (m.pattern(), m.start(), m.end()))
1138-
.collect()
1139-
};
1140-
for &tests in which {
1141-
for test in tests {
1142-
assert_eq!(
1143-
test.matches,
1144-
get_match_triples(f(&test)).as_slice(),
1145-
"test: {}, patterns: {:?}, haystack: {:?}",
1146-
test.name,
1147-
test.patterns,
1148-
test.haystack
1149-
);
1154+
// See: https://github.com/BurntSushi/aho-corasick/issues/64
1155+
//
1156+
// This occurs when the rare byte prefilter is active
1157+
#[test]
1158+
fn regression_stream_rare_byte_prefilter() {
1159+
use std::io::Read;
1160+
1161+
// NOTE: The test only fails if this ends with j.
1162+
const MAGIC: [u8; 5] = *b"1234j";
1163+
1164+
// NOTE: The test fails for value in 8188..=8191 These value put the string
1165+
// to search accross two call to read because the buffer size is 8192 by
1166+
// default.
1167+
const BEGIN: usize = 8191;
1168+
1169+
/// This is just a structure that implements Reader. The reader
1170+
/// implementation will simulate a file filled with 0, except for the MAGIC
1171+
/// string at offset BEGIN.
1172+
#[derive(Default)]
1173+
struct R {
1174+
read: usize,
1175+
}
1176+
1177+
impl Read for R {
1178+
fn read(&mut self, buf: &mut [u8]) -> ::std::io::Result<usize> {
1179+
//dbg!(buf.len());
1180+
if self.read > 100000 {
1181+
return Ok(0);
1182+
}
1183+
let mut from = 0;
1184+
if self.read < BEGIN {
1185+
from = buf.len().min(BEGIN - self.read);
1186+
for x in 0..from {
1187+
buf[x] = 0;
1188+
}
1189+
self.read += from;
1190+
}
1191+
if self.read >= BEGIN && self.read <= BEGIN + MAGIC.len() {
1192+
let to = buf.len().min(BEGIN + MAGIC.len() - self.read + from);
1193+
if to > from {
1194+
buf[from..to].copy_from_slice(
1195+
&MAGIC
1196+
[self.read - BEGIN..self.read - BEGIN + to - from],
1197+
);
1198+
self.read += to - from;
1199+
from = to;
1200+
}
1201+
}
1202+
for x in from..buf.len() {
1203+
buf[x] = 0;
1204+
self.read += 1;
1205+
}
1206+
Ok(buf.len())
11501207
}
11511208
}
1209+
1210+
fn run() -> ::std::io::Result<()> {
1211+
let aut = AhoCorasickBuilder::new().build(&[&MAGIC]);
1212+
1213+
// While reading from a vector, it works:
1214+
let mut buf = vec![];
1215+
R::default().read_to_end(&mut buf)?;
1216+
let from_whole = aut.find_iter(&buf).next().unwrap().start();
1217+
1218+
//But using stream_find_iter fails!
1219+
let mut file = R::default();
1220+
let begin = aut
1221+
.stream_find_iter(&mut file)
1222+
.next()
1223+
.expect("NOT FOUND!!!!")? // Panic here
1224+
.start();
1225+
assert_eq!(from_whole, begin);
1226+
Ok(())
1227+
}
1228+
1229+
run().unwrap()
11521230
}

0 commit comments

Comments
 (0)