Skip to content

Commit 2a6d8f3

Browse files
committed
nfa: massively simplify leftmost failure transitions
The key insight here is that all we need to do to support leftmost semantics is to omit ALL failure transitions that appear after a match state in the trie. (And to omit any entries in the trie that cross a previously existing match state for leftmost-first semantics, and keep them for leftmost-longest.) Previously, I had somehow convinced myself that the subset was more difficult to identify and required comparing depths. But this is just not the case. Moreover, once you set the match state to have a failure transition to the dead state, it automatically propagates to all subsequent states. This is such a huge simplification that I combined the 'standard' and 'leftmost' failure transition construction into a single method. Fixes #92
1 parent 979cf73 commit 2a6d8f3

3 files changed

Lines changed: 86 additions & 247 deletions

File tree

‎src/automaton.rs‎

Lines changed: 7 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -68,11 +68,11 @@ use crate::Match;
6868
///
6969
/// Every automaton has exactly one fail state, one dead state and exactly one
7070
/// start state. Generally, these correspond to the first, second and third
71-
/// states, respectively. The failure state is always treated as a sentinel.
72-
/// That is, no correct Aho-Corasick automaton will ever transition into the
73-
/// fail state. The dead state, however, can be transitioned into, but only
74-
/// when leftmost-first or leftmost-longest match semantics are enabled and
75-
/// only when at least one match has been observed.
71+
/// states, respectively. The dead state is always treated as a sentinel. That
72+
/// is, no correct Aho-Corasick automaton will ever transition into the fail
73+
/// state. The dead state, however, can be transitioned into, but only when
74+
/// leftmost-first or leftmost-longest match semantics are enabled and only
75+
/// when at least one match has been observed.
7676
///
7777
/// Every automaton also has one or more match states, such that
7878
/// `Automaton::is_match_state(id)` returns `true` if and only if `id`
@@ -340,7 +340,7 @@ pub trait Automaton {
340340
// dead states are used to stop a search.)
341341
debug_assert!(
342342
last_match.is_some() || self.anchored(),
343-
"failure state should only be seen after match"
343+
"dead state should only be seen after match"
344344
);
345345
return last_match;
346346
}
@@ -455,7 +455,7 @@ pub trait Automaton {
455455
// case, dead states are used to stop a search.)
456456
debug_assert!(
457457
last_match.is_some() || self.anchored(),
458-
"failure state should only be seen after match"
458+
"dead state should only be seen after match"
459459
);
460460
return last_match;
461461
}

0 commit comments

Comments
 (0)