/// A description of a single test against an Aho-Corasick automaton. /// /// A single test may not necessarily pass on every configuration of an /// Aho-Corasick automaton. The tests are categorized and grouped appropriately /// below. #[derive(Clone, Debug, Eq, PartialEq)] struct SearchTest { /// The name of this test, for debugging.
name: &'static str, /// The patterns to search for.
patterns: &'static [&'static str], /// The text to search.
haystack: &'static str, /// Each match is a triple of (pattern_index, start, end), where /// pattern_index is an index into `patterns` and `start`/`end` are indices /// into `haystack`.
matches: &'static [(usize, usize, usize)],
}
/// Short-hand constructor for SearchTest. We use it a lot below.
macro_rules! t {
($name:ident, $patterns:expr, $haystack:expr, $matches:expr) => {
SearchTest {
name: stringify!($name),
patterns: $patterns,
haystack: $haystack,
matches: $matches,
}
};
}
/// A collection of test groups. type TestCollection = &'static [&'static [SearchTest]];
// Define several collections corresponding to the different type of match // semantics supported by Aho-Corasick. These collections have some overlap, // but each collection should have some tests that no other collection has.
/// Tests for Aho-Corasick's standard non-overlapping match semantics. const AC_STANDARD_NON_OVERLAPPING: TestCollection =
&[BASICS, NON_OVERLAPPING, STANDARD, REGRESSION];
/// Tests for Aho-Corasick's anchored standard non-overlapping match semantics. const AC_STANDARD_ANCHORED_NON_OVERLAPPING: TestCollection =
&[ANCHORED_BASICS, ANCHORED_NON_OVERLAPPING, STANDARD_ANCHORED];
/// Tests for Aho-Corasick's standard overlapping match semantics. const AC_STANDARD_OVERLAPPING: TestCollection =
&[BASICS, OVERLAPPING, REGRESSION];
/* IteratorsofanchoredoverlappingsearcheswereremovedfromtheAPIin after0.7,butweleavethetestscommentedoutforposterity. /// Tests for Aho-Corasick's anchored standard overlapping match semantics. constAC_STANDARD_ANCHORED_OVERLAPPING:TestCollection= &[ANCHORED_BASICS,ANCHORED_OVERLAPPING];
*/
/// Tests for Aho-Corasick's leftmost-first match semantics. const AC_LEFTMOST_FIRST: TestCollection =
&[BASICS, NON_OVERLAPPING, LEFTMOST, LEFTMOST_FIRST, REGRESSION];
/// Tests for Aho-Corasick's anchored leftmost-first match semantics. const AC_LEFTMOST_FIRST_ANCHORED: TestCollection = &[
ANCHORED_BASICS,
ANCHORED_NON_OVERLAPPING,
ANCHORED_LEFTMOST,
ANCHORED_LEFTMOST_FIRST,
];
/// Tests for Aho-Corasick's leftmost-longest match semantics. const AC_LEFTMOST_LONGEST: TestCollection =
&[BASICS, NON_OVERLAPPING, LEFTMOST, LEFTMOST_LONGEST, REGRESSION];
/// Tests for Aho-Corasick's anchored leftmost-longest match semantics. const AC_LEFTMOST_LONGEST_ANCHORED: TestCollection = &[
ANCHORED_BASICS,
ANCHORED_NON_OVERLAPPING,
ANCHORED_LEFTMOST,
ANCHORED_LEFTMOST_LONGEST,
];
// Now define the individual tests that make up the collections above.
/* IteratorsofanchoredoverlappingsearcheswereremovedfromtheAPIin after0.7,butweleavethetestscommentedoutforposterity. /// Like OVERLAPPING, but for anchored searches. constANCHORED_OVERLAPPING:&'static[SearchTest]=&[ t!(aover000,&["abcd","bcd","cd","b"],"abcd",&[(0,0,4)]), t!(aover010,&["bcd","cd","b","abcd"],"abcd",&[(3,0,4)]), t!(aover020,&["abcd","bcd","cd"],"abcd",&[(0,0,4)]), t!(aover030,&["bcd","abcd","cd"],"abcd",&[(1,0,4)]), t!(aover040,&["bcd","cd","abcd"],"abcd",&[(2,0,4)]), t!(aover050,&["abc","bc"],"zazabcz",&[]), t!(aover100,&["ab","ba"],"abababa",&[(0,0,2)]), t!(aover200,&["foo","foo"],"foobarfoo",&[(0,0,3),(1,0,3)]), t!(aover300,&["",""],"",&[(0,0,0),(1,0,0),]), t!(aover310,&["",""],"a",&[(0,0,0),(1,0,0)]), t!(aover320,&["","a"],"a",&[(0,0,0),(1,0,1)]), t!(aover330,&["","a",""],"a",&[(0,0,0),(2,0,0),(1,0,1)]), t!(aover340,&["a","",""],"a",&[(1,0,0),(2,0,0),(0,0,1)]), t!(aover350,&["","","a"],"a",&[(0,0,0),(1,0,0),(2,0,1)]), t!(aover360,&["foo","foofoo"],"foofoo",&[(0,0,3),(1,0,6)]), ];
*/
/// Tests for ASCII case insensitivity. /// /// These tests should all have the same behavior regardless of match semantics /// or whether the search is overlapping. const ASCII_CASE_INSENSITIVE: &'static [SearchTest] = &[
t!(acasei000, &["a"], "A", &[(0, 0, 1)]),
t!(acasei010, &["Samwise"], "SAMWISE", &[(0, 0, 7)]),
t!(acasei011, &["Samwise"], "SAMWISE.abcd", &[(0, 0, 7)]),
t!(acasei020, &["fOoBaR"], "quux foobar baz", &[(0, 5, 11)]),
];
/// Like ASCII_CASE_INSENSITIVE, but specifically for overlapping tests. const ASCII_CASE_INSENSITIVE_OVERLAPPING: &'static [SearchTest] = &[
t!(acasei000, &["foo", "FOO"], "fOo", &[(0, 0, 3), (1, 0, 3)]),
t!(acasei001, &["FOO", "foo"], "fOo", &[(0, 0, 3), (1, 0, 3)]), // This is a regression test from: // https://github.com/BurntSushi/aho-corasick/issues/68 // Previously, it was reporting a duplicate (1, 3, 6) match.
t!(
acasei010,
&["abc", "def", "abcdef"], "abcdef",
&[(0, 0, 3), (2, 0, 6), (1, 3, 6)]
),
];
/// Regression tests that are applied to all Aho-Corasick combinations. /// /// If regression tests are needed for specific match semantics, then add them /// to the appropriate group above. const REGRESSION: &'static [SearchTest] = &[
t!(regression010, &["inf", "ind"], "infind", &[(0, 0, 3), (1, 3, 6),]),
t!(regression020, &["ind", "inf"], "infind", &[(1, 0, 3), (0, 3, 6),]),
t!(
regression030,
&["libcore/", "libstd/"], "libcore/char/methods.rs",
&[(0, 0, 8),]
),
t!(
regression040,
&["libstd/", "libcore/"], "libcore/char/methods.rs",
&[(1, 0, 8),]
),
t!(
regression050,
&["\x00\x00\x01", "\x00\x00\x00"], "\x00\x00\x00",
&[(1, 0, 3),]
),
t!(
regression060,
&["\x00\x00\x00", "\x00\x00\x01"], "\x00\x00\x00",
&[(0, 0, 3),]
),
];
// Now define a test for each combination of things above that we want to run. // Since there are a few different combinations for each collection of tests, // we define a couple of macros to avoid repetition drudgery. The testconfig // macro constructs the automaton from a given match kind, and runs the search // tests one-by-one over the given collection. The `with` parameter allows one // to configure the builder with additional parameters. The testcombo macro // invokes testconfig in precisely this way: it sets up several tests where // each one turns a different knob on AhoCorasickBuilder.
// Write out the various combinations of match semantics given the variety of // configurations tested by 'testcombo!'.
testcombo!(search_leftmost_longest, AC_LEFTMOST_LONGEST, LeftmostLongest);
testcombo!(search_leftmost_first, AC_LEFTMOST_FIRST, LeftmostFirst);
testcombo!(
search_standard_nonoverlapping,
AC_STANDARD_NON_OVERLAPPING,
Standard
);
// Also write out tests manually for streams, since we only test the standard // match semantics. We also don't bother testing different automaton // configurations, since those are well covered by tests above. #[cfg(feature = "std")]
testconfig!(
stream,
search_standard_stream_default,
AC_STANDARD_NON_OVERLAPPING,
Standard,
|_| ()
); #[cfg(feature = "std")]
testconfig!(
stream,
search_standard_stream_nfa_noncontig_default,
AC_STANDARD_NON_OVERLAPPING,
Standard,
|b: &mut AhoCorasickBuilder| {
b.kind(Some(AhoCorasickKind::NoncontiguousNFA));
}
); #[cfg(feature = "std")]
testconfig!(
stream,
search_standard_stream_nfa_contig_default,
AC_STANDARD_NON_OVERLAPPING,
Standard,
|b: &mut AhoCorasickBuilder| {
b.kind(Some(AhoCorasickKind::ContiguousNFA));
}
); #[cfg(feature = "std")]
testconfig!(
stream,
search_standard_stream_dfa_default,
AC_STANDARD_NON_OVERLAPPING,
Standard,
|b: &mut AhoCorasickBuilder| {
b.kind(Some(AhoCorasickKind::DFA));
}
);
fn run_search_tests<F: FnMut(&SearchTest) -> Vec<Match>>(
which: TestCollection, mut f: F,
) { let get_match_triples =
|matches: Vec<Match>| -> Vec<(usize, usize, usize)> {
matches
.into_iter()
.map(|m| (m.pattern().as_usize(), m.start(), m.end()))
.collect()
}; for &tests in which { for test in tests {
assert_eq!(
test.matches,
get_match_triples(f(&test)).as_slice(), "test: {}, patterns: {:?}, haystack: {:?}",
test.name,
test.patterns,
test.haystack
);
}
}
}
// Like 'run_search_tests', but we skip any tests that contain the empty // pattern because stream searching doesn't support it. #[cfg(feature = "std")] fn run_stream_search_tests<F: FnMut(&SearchTest) -> Vec<Match>>(
which: TestCollection, mut f: F,
) { let get_match_triples =
|matches: Vec<Match>| -> Vec<(usize, usize, usize)> {
matches
.into_iter()
.map(|m| (m.pattern().as_usize(), m.start(), m.end()))
.collect()
}; for &tests in which { for test in tests { if test.patterns.iter().any(|p| p.is_empty()) { continue;
}
assert_eq!(
test.matches,
get_match_triples(f(&test)).as_slice(), "test: {}, patterns: {:?}, haystack: {:?}",
test.name,
test.patterns,
test.haystack
);
}
}
}
#[test] fn search_tests_have_unique_names() { let assert = |constname, tests: &[SearchTest]| { letmut seen = HashMap::new(); // map from test name to position for (i, test) in tests.iter().enumerate() { if !seen.contains_key(test.name) {
seen.insert(test.name, i);
} else { let last = seen[test.name];
panic!( "{} tests have duplicate names at positions {} and {}",
constname, last, i
);
}
}
};
assert("BASICS", BASICS);
assert("STANDARD", STANDARD);
assert("LEFTMOST", LEFTMOST);
assert("LEFTMOST_FIRST", LEFTMOST_FIRST);
assert("LEFTMOST_LONGEST", LEFTMOST_LONGEST);
assert("NON_OVERLAPPING", NON_OVERLAPPING);
assert("OVERLAPPING", OVERLAPPING);
assert("REGRESSION", REGRESSION);
}
// This tests that if we build an AC matcher with an "unanchored" start kind, // then we can't run an anchored search even if the underlying searcher // supports it. // // The key bit here is that both of the NFAs in this crate unconditionally // support both unanchored and anchored searches, but the DFA does not because // of the added cost of doing so. To avoid the top-level AC matcher sometimes // supporting anchored and sometimes not (depending on which searcher it // chooses to use internally), we ensure that the given 'StartKind' is always // respected. #[test] fn anchored_not_allowed_even_if_technically_available() { let ac = AhoCorasick::builder()
.kind(Some(AhoCorasickKind::NoncontiguousNFA))
.start_kind(StartKind::Unanchored)
.build(&["foo"])
.unwrap();
assert!(ac.try_find(Input::new("foo").anchored(Anchored::Yes)).is_err());
let ac = AhoCorasick::builder()
.kind(Some(AhoCorasickKind::ContiguousNFA))
.start_kind(StartKind::Unanchored)
.build(&["foo"])
.unwrap();
assert!(ac.try_find(Input::new("foo").anchored(Anchored::Yes)).is_err());
// For completeness, check that the DFA returns an error too. let ac = AhoCorasick::builder()
.kind(Some(AhoCorasickKind::DFA))
.start_kind(StartKind::Unanchored)
.build(&["foo"])
.unwrap();
assert!(ac.try_find(Input::new("foo").anchored(Anchored::Yes)).is_err());
}
// This is like the test aboved, but with unanchored and anchored flipped. That // is, we asked for an AC searcher with anchored support and we check that // unanchored searches return an error even if the underlying searcher would // technically support it. #[test] fn unanchored_not_allowed_even_if_technically_available() { let ac = AhoCorasick::builder()
.kind(Some(AhoCorasickKind::NoncontiguousNFA))
.start_kind(StartKind::Anchored)
.build(&["foo"])
.unwrap();
assert!(ac.try_find(Input::new("foo").anchored(Anchored::No)).is_err());
let ac = AhoCorasick::builder()
.kind(Some(AhoCorasickKind::ContiguousNFA))
.start_kind(StartKind::Anchored)
.build(&["foo"])
.unwrap();
assert!(ac.try_find(Input::new("foo").anchored(Anchored::No)).is_err());
// For completeness, check that the DFA returns an error too. let ac = AhoCorasick::builder()
.kind(Some(AhoCorasickKind::DFA))
.start_kind(StartKind::Anchored)
.build(&["foo"])
.unwrap();
assert!(ac.try_find(Input::new("foo").anchored(Anchored::No)).is_err());
}
// This tests that a prefilter does not cause a search to report a match // outside the bounds provided by the caller. // // This is a regression test for a bug I introduced during the rewrite of most // of the crate after 0.7. It was never released. The tricky part here is // ensuring we get a prefilter that can report matches on its own (such as the // packed searcher). Otherwise, prefilters that report false positives might // have searched past the bounds provided by the caller, but confirming the // match would subsequently fail. #[test] fn prefilter_stays_in_bounds() { let ac = AhoCorasick::builder()
.match_kind(MatchKind::LeftmostFirst)
.build(&["sam", "frodo", "pippin", "merry", "gandalf", "sauron"])
.unwrap(); let haystack = "foo gandalf";
assert_eq!(None, ac.find(Input::new(haystack).range(0..10)));
}
// See: https://github.com/BurntSushi/aho-corasick/issues/44 // // In short, this test ensures that enabling ASCII case insensitivity does not // visit an exponential number of states when filling in failure transitions. #[test] fn regression_ascii_case_insensitive_no_exponential() { let ac = AhoCorasick::builder()
.ascii_case_insensitive(true)
.build(&["Tsubaki House-Triple Shot Vol01校花三姐妹"])
.unwrap();
assert!(ac.find("").is_none());
}
// See: https://github.com/BurntSushi/aho-corasick/issues/53 // // This test ensures that the rare byte prefilter works in a particular corner // case. In particular, the shift offset detected for '/' in the patterns below // was incorrect, leading to a false negative. #[test] fn regression_rare_byte_prefilter() { usecrate::AhoCorasick;
let ac = AhoCorasick::new(&["ab/j/", "x/"]).unwrap();
assert!(ac.is_match("ab/j/"));
}
#[test] fn regression_case_insensitive_prefilter() { for c in b'a'..b'z' { for c2 in b'a'..b'z' { let c = c as char; let c2 = c2 as char; let needle = format!("{}{}", c, c2).to_lowercase(); let haystack = needle.to_uppercase(); let ac = AhoCorasick::builder()
.ascii_case_insensitive(true)
.prefilter(true)
.build(&[&needle])
.unwrap();
assert_eq!( 1,
ac.find_iter(&haystack).count(), "failed to find {:?} in {:?}\n\nautomaton:\n{:?}",
needle,
haystack,
ac,
);
}
}
}
// See: https://github.com/BurntSushi/aho-corasick/issues/64 // // This occurs when the rare byte prefilter is active. #[cfg(feature = "std")] #[test] fn regression_stream_rare_byte_prefilter() { use std::io::Read;
// NOTE: The test only fails if this ends with j. const MAGIC: [u8; 5] = *b"1234j";
// NOTE: The test fails for value in 8188..=8191 These value put the string // to search accross two call to read because the buffer size is 64KB by // default. const BEGIN: usize = 65_535;
/// This is just a structure that implements Reader. The reader /// implementation will simulate a file filled with 0, except for the MAGIC /// string at offset BEGIN. #[derive(Default)] struct R {
read: usize,
}
impl Read for R { fn read(&mutself, buf: &mut [u8]) -> std::io::Result<usize> { ifself.read > 100000 { return Ok(0);
} letmut from = 0; ifself.read < BEGIN {
from = buf.len().min(BEGIN - self.read); for x in0..from {
buf[x] = 0;
} self.read += from;
} ifself.read >= BEGIN && self.read <= BEGIN + MAGIC.len() { let to = buf.len().min(BEGIN + MAGIC.len() - self.read + from); if to > from {
buf[from..to].copy_from_slice(
&MAGIC
[self.read - BEGIN..self.read - BEGIN + to - from],
); self.read += to - from;
from = to;
}
} for x in from..buf.len() {
buf[x] = 0; self.read += 1;
}
Ok(buf.len())
}
}
fn run() -> std::io::Result<()> { let aut = AhoCorasick::builder() // Enable byte classes to make debugging the automaton easier. It // should have no effect on the test result.
.byte_classes(false)
.build(&[&MAGIC])
.unwrap();
// While reading from a vector, it works: letmut buf = alloc::vec![];
R::default().read_to_end(&mut buf)?; let from_whole = aut.find_iter(&buf).next().unwrap().start();
// But using stream_find_iter fails! letmut file = std::io::BufReader::new(R::default()); let begin = aut
.stream_find_iter(&mut file)
.next()
.expect("NOT FOUND!!!!")? // Panic here
.start();
assert_eq!(from_whole, begin);
Ok(())
}
run().unwrap()
}
Messung V0.5 in Prozent
¤ Dauer der Verarbeitung: 0.26 Sekunden
(vorverarbeitet am 2026-06-19)
¤
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung und die Messung sind noch experimentell.
