| 1 |
use core::mem; |
| 2 |
|
| 3 |
use alloc::{vec, vec::Vec}; |
| 4 |
|
| 5 |
use crate::{ |
| 6 |
nfa::thompson::{self, compiler::ThompsonRef, BuildError, Builder}, |
| 7 |
util::primitives::{IteratorIndexExt, StateID}, |
| 8 |
}; |
| 9 |
|
| 10 |
/// A trie that preserves leftmost-first match semantics. |
| 11 |
/// |
| 12 |
/// This is a purpose-built data structure for optimizing 'lit1|lit2|..|litN' |
| 13 |
/// patterns. It can *only* handle alternations of literals, which makes it |
| 14 |
/// somewhat restricted in its scope, but literal alternations are fairly |
| 15 |
/// common. |
| 16 |
/// |
| 17 |
/// At a 5,000 foot level, the main idea of this trie is make an alternation of |
| 18 |
/// literals look more like a DFA than an NFA via epsilon removal. |
| 19 |
/// |
| 20 |
/// More precisely, the main issue is in how alternations are compiled into |
| 21 |
/// a Thompson NFA. Namely, each alternation gets a single NFA "union" state |
| 22 |
/// with an epsilon transition for every branch of the alternation pointing to |
| 23 |
/// an NFA state corresponding to the start of that branch. The main problem |
| 24 |
/// with this representation is the cost of computing an epsilon closure. Once |
| 25 |
/// you hit the alternation's start state, it acts as a sort of "clog" that |
| 26 |
/// requires you to traverse all of the epsilon transitions to compute the full |
| 27 |
/// closure. |
| 28 |
/// |
| 29 |
/// While fixing such clogs in the general case is pretty tricky without going |
| 30 |
/// to a DFA (or perhaps a Glushkov NFA, but that comes with other problems). |
| 31 |
/// But at least in the case of an alternation of literals, we can convert |
| 32 |
/// that to a prefix trie without too much cost. In theory, that's all you |
| 33 |
/// really need to do: build the trie and then compile it to a Thompson NFA. |
| 34 |
/// For example, if you have the pattern 'bar|baz|foo', then using a trie, it |
| 35 |
/// is transformed to something like 'b(a(r|z))|f'. This reduces the clog by |
| 36 |
/// reducing the number of epsilon transitions out of the alternation's start |
| 37 |
/// state from 3 to 2 (it actually gets down to 1 when you use a sparse state, |
| 38 |
/// which we do below). It's a small effect here, but when your alternation is |
| 39 |
/// huge, the savings is also huge. |
| 40 |
/// |
| 41 |
/// And that is... essentially what a LiteralTrie does. But there is one |
| 42 |
/// hiccup. Consider a regex like 'sam|samwise'. How does a prefix trie compile |
| 43 |
/// that when leftmost-first semantics are used? If 'sam|samwise' was the |
| 44 |
/// entire regex, then you could just drop the 'samwise' branch entirely since |
| 45 |
/// it is impossible to match ('sam' will always take priority, and since it |
| 46 |
/// is a prefix of 'samwise', 'samwise' will never match). But what about the |
| 47 |
/// regex '\b(sam|samwise)\b'? In that case, you can't remove 'samwise' because |
| 48 |
/// it might match when 'sam' doesn't fall on a word boundary. |
| 49 |
/// |
| 50 |
/// The main idea is that 'sam|samwise' can be translated to 'sam(?:|wise)', |
| 51 |
/// which is a precisely equivalent regex that also gets rid of the clog. |
| 52 |
/// |
| 53 |
/// Another example is 'zapper|z|zap'. That gets translated to |
| 54 |
/// 'z(?:apper||ap)'. |
| 55 |
/// |
| 56 |
/// We accomplish this by giving each state in the trie multiple "chunks" of |
| 57 |
/// transitions. Each chunk barrier represents a match. The idea is that once |
| 58 |
/// you know a match occurs, none of the transitions after the match can be |
| 59 |
/// re-ordered and mixed in with the transitions before the match. Otherwise, |
| 60 |
/// the match semantics could be changed. |
| 61 |
/// |
| 62 |
/// See the 'State' data type for a bit more detail. |
| 63 |
/// |
| 64 |
/// Future work: |
| 65 |
/// |
| 66 |
/// * In theory, it would be nice to generalize the idea of removing clogs and |
| 67 |
/// apply it to the NFA graph itself. Then this could in theory work for |
| 68 |
/// case insensitive alternations of literals, or even just alternations where |
| 69 |
/// each branch starts with a non-epsilon transition. |
| 70 |
/// * Could we instead use the Aho-Corasick algorithm here? The aho-corasick |
| 71 |
/// crate deals with leftmost-first matches correctly, but I think this implies |
| 72 |
/// encoding failure transitions into a Thompson NFA somehow. Which seems fine, |
| 73 |
/// because failure transitions are just unconditional epsilon transitions? |
| 74 |
/// * Or perhaps even better, could we use an aho_corasick::AhoCorasick |
| 75 |
/// directly? At time of writing, 0.7 is the current version of the |
| 76 |
/// aho-corasick crate, and that definitely cannot be used as-is. But if we |
| 77 |
/// expose the underlying finite state machine API, then could we use it? That |
| 78 |
/// would be super. If we could figure that out, it might also lend itself to |
| 79 |
/// more general composition of finite state machines. |
| 80 |
#[derive(Clone)] |
| 81 |
pub(crate) struct LiteralTrie { |
| 82 |
/// The set of trie states. Each state contains one or more chunks, where |
| 83 |
/// each chunk is a sparse set of transitions to other states. A leaf state |
| 84 |
/// is always a match state that contains only empty chunks (i.e., no |
| 85 |
/// transitions). |
| 86 |
states: Vec<State>, |
| 87 |
/// Whether to add literals in reverse to the trie. Useful when building |
| 88 |
/// a reverse NFA automaton. |
| 89 |
rev: bool, |
| 90 |
} |
| 91 |
|
| 92 |
impl LiteralTrie { |
| 93 |
/// Create a new literal trie that adds literals in the forward direction. |
| 94 |
pub(crate) fn forward() -> LiteralTrie { |
| 95 |
let root = State::default(); |
| 96 |
LiteralTrie { states: vec![root], rev: false } |
| 97 |
} |
| 98 |
|
| 99 |
/// Create a new literal trie that adds literals in reverse. |
| 100 |
pub(crate) fn reverse() -> LiteralTrie { |
| 101 |
let root = State::default(); |
| 102 |
LiteralTrie { states: vec![root], rev: true } |
| 103 |
} |
| 104 |
|
| 105 |
/// Add the given literal to this trie. |
| 106 |
/// |
| 107 |
/// If the literal could not be added because the `StateID` space was |
| 108 |
/// exhausted, then an error is returned. If an error returns, the trie |
| 109 |
/// is in an unspecified state. |
| 110 |
pub(crate) fn add(&mut self, bytes: &[u8]) -> Result<(), BuildError> { |
| 111 |
let mut prev = StateID::ZERO; |
| 112 |
let mut it = bytes.iter().copied(); |
| 113 |
while let Some(b) = if self.rev { it.next_back() } else { it.next() } { |
| 114 |
prev = self.get_or_add_state(prev, b)?; |
| 115 |
} |
| 116 |
self.states[prev].add_match(); |
| 117 |
Ok(()) |
| 118 |
} |
| 119 |
|
| 120 |
/// If the given transition is defined, then return the next state ID. |
| 121 |
/// Otherwise, add the transition to `from` and point it to a new state. |
| 122 |
/// |
| 123 |
/// If a new state ID could not be allocated, then an error is returned. |
| 124 |
fn get_or_add_state( |
| 125 |
&mut self, |
| 126 |
from: StateID, |
| 127 |
byte: u8, |
| 128 |
) -> Result<StateID, BuildError> { |
| 129 |
let active = self.states[from].active_chunk(); |
| 130 |
match active.binary_search_by_key(&byte, |t| t.byte) { |
| 131 |
Ok(i) => Ok(active[i].next), |
| 132 |
Err(i) => { |
| 133 |
// Add a new state and get its ID. |
| 134 |
let next = StateID::new(self.states.len()).map_err(|_| { |
| 135 |
BuildError::too_many_states(self.states.len()) |
| 136 |
})?; |
| 137 |
self.states.push(State::default()); |
| 138 |
// Offset our position to account for all transitions and not |
| 139 |
// just the ones in the active chunk. |
| 140 |
let i = self.states[from].active_chunk_start() + i; |
| 141 |
let t = Transition { byte, next }; |
| 142 |
self.states[from].transitions.insert(i, t); |
| 143 |
Ok(next) |
| 144 |
} |
| 145 |
} |
| 146 |
} |
| 147 |
|
| 148 |
/// Compile this literal trie to the NFA builder given. |
| 149 |
/// |
| 150 |
/// This forwards any errors that may occur while using the given builder. |
| 151 |
pub(crate) fn compile( |
| 152 |
&self, |
| 153 |
builder: &mut Builder, |
| 154 |
) -> Result<ThompsonRef, BuildError> { |
| 155 |
// Compilation proceeds via depth-first traversal of the trie. |
| 156 |
// |
| 157 |
// This is overall pretty brutal. The recursive version of this is |
| 158 |
// deliciously simple. (See 'compile_to_hir' below for what it might |
| 159 |
// look like.) But recursion on a trie means your call stack grows |
| 160 |
// in accordance with the longest literal, which just does not seem |
| 161 |
// appropriate. So we push the call stack to the heap. But as a result, |
| 162 |
// the trie traversal becomes pretty brutal because we essentially |
| 163 |
// have to encode the state of a double for-loop into an explicit call |
| 164 |
// frame. If someone can simplify this without using recursion, that'd |
| 165 |
// be great. |
| 166 |
|
| 167 |
// 'end' is our match state for this trie, but represented in the the |
| 168 |
// NFA. Any time we see a match in the trie, we insert a transition |
| 169 |
// from the current state we're in to 'end'. |
| 170 |
let end = builder.add_empty()?; |
| 171 |
let mut stack = vec![]; |
| 172 |
let mut f = Frame::new(&self.states[StateID::ZERO]); |
| 173 |
loop { |
| 174 |
if let Some(t) = f.transitions.next() { |
| 175 |
if self.states[t.next].is_leaf() { |
| 176 |
f.sparse.push(thompson::Transition { |
| 177 |
start: t.byte, |
| 178 |
end: t.byte, |
| 179 |
next: end, |
| 180 |
}); |
| 181 |
} else { |
| 182 |
f.sparse.push(thompson::Transition { |
| 183 |
start: t.byte, |
| 184 |
end: t.byte, |
| 185 |
// This is a little funny, but when the frame we create |
| 186 |
// below completes, it will pop this parent frame off |
| 187 |
// and modify this transition to point to the correct |
| 188 |
// state. |
| 189 |
next: StateID::ZERO, |
| 190 |
}); |
| 191 |
stack.push(f); |
| 192 |
f = Frame::new(&self.states[t.next]); |
| 193 |
} |
| 194 |
continue; |
| 195 |
} |
| 196 |
// At this point, we have visited all transitions in f.chunk, so |
| 197 |
// add it as a sparse NFA state. Unless the chunk was empty, in |
| 198 |
// which case, we don't do anything. |
| 199 |
if !f.sparse.is_empty() { |
| 200 |
let chunk_id = if f.sparse.len() == 1 { |
| 201 |
builder.add_range(f.sparse.pop().unwrap())? |
| 202 |
} else { |
| 203 |
let sparse = mem::replace(&mut f.sparse, vec![]); |
| 204 |
builder.add_sparse(sparse)? |
| 205 |
}; |
| 206 |
f.union.push(chunk_id); |
| 207 |
} |
| 208 |
// Now we need to look to see if there are other chunks to visit. |
| 209 |
if let Some(chunk) = f.chunks.next() { |
| 210 |
// If we're here, it means we're on the second (or greater) |
| 211 |
// chunk, which implies there is a match at this point. So |
| 212 |
// connect this state to the final end state. |
| 213 |
f.union.push(end); |
| 214 |
// Advance to the next chunk. |
| 215 |
f.transitions = chunk.iter(); |
| 216 |
continue; |
| 217 |
} |
| 218 |
// Now that we are out of chunks, we have completely visited |
| 219 |
// this state. So turn our union of chunks into an NFA union |
| 220 |
// state, and add that union state to the parent state's current |
| 221 |
// sparse state. (If there is no parent, we're done.) |
| 222 |
let start = builder.add_union(f.union)?; |
| 223 |
match stack.pop() { |
| 224 |
None => { |
| 225 |
return Ok(ThompsonRef { start, end }); |
| 226 |
} |
| 227 |
Some(mut parent) => { |
| 228 |
// OK because the only way a frame gets pushed on to the |
| 229 |
// stack (aside from the root) is when a transition has |
| 230 |
// been added to 'sparse'. |
| 231 |
parent.sparse.last_mut().unwrap().next = start; |
| 232 |
f = parent; |
| 233 |
} |
| 234 |
} |
| 235 |
} |
| 236 |
} |
| 237 |
|
| 238 |
/// Converts this trie to an equivalent HIR expression. |
| 239 |
/// |
| 240 |
/// We don't actually use this, but it's useful for tests. In particular, |
| 241 |
/// it provides a (somewhat) human readable representation of the trie |
| 242 |
/// itself. |
| 243 |
#[cfg(test)] |
| 244 |
fn compile_to_hir(&self) -> regex_syntax::hir::Hir { |
| 245 |
self.compile_state_to_hir(StateID::ZERO) |
| 246 |
} |
| 247 |
|
| 248 |
/// The recursive implementation of 'to_hir'. |
| 249 |
/// |
| 250 |
/// Notice how simple this is compared to 'compile' above. 'compile' could |
| 251 |
/// be similarly simple, but we opt to not use recursion in order to avoid |
| 252 |
/// overflowing the stack in the case of a longer literal. |
| 253 |
#[cfg(test)] |
| 254 |
fn compile_state_to_hir(&self, sid: StateID) -> regex_syntax::hir::Hir { |
| 255 |
use regex_syntax::hir::Hir; |
| 256 |
|
| 257 |
let mut alt = vec![]; |
| 258 |
for (i, chunk) in self.states[sid].chunks().enumerate() { |
| 259 |
if i > 0 { |
| 260 |
alt.push(Hir::empty()); |
| 261 |
} |
| 262 |
if chunk.is_empty() { |
| 263 |
continue; |
| 264 |
} |
| 265 |
let mut chunk_alt = vec![]; |
| 266 |
for t in chunk.iter() { |
| 267 |
chunk_alt.push(Hir::concat(vec![ |
| 268 |
Hir::literal(vec![t.byte]), |
| 269 |
self.compile_state_to_hir(t.next), |
| 270 |
])); |
| 271 |
} |
| 272 |
alt.push(Hir::alternation(chunk_alt)); |
| 273 |
} |
| 274 |
Hir::alternation(alt) |
| 275 |
} |
| 276 |
} |
| 277 |
|
| 278 |
impl core::fmt::Debug for LiteralTrie { |
| 279 |
fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result { |
| 280 |
writeln!(f, "LiteralTrie(")?; |
| 281 |
for (sid, state) in self.states.iter().with_state_ids() { |
| 282 |
writeln!(f, "{:06?}: {:?}", sid.as_usize(), state)?; |
| 283 |
} |
| 284 |
writeln!(f, ")")?; |
| 285 |
Ok(()) |
| 286 |
} |
| 287 |
} |
| 288 |
|
| 289 |
/// An explicit stack frame used for traversing the trie without using |
| 290 |
/// recursion. |
| 291 |
/// |
| 292 |
/// Each frame is tied to the traversal of a single trie state. The frame is |
| 293 |
/// dropped once the entire state (and all of its children) have been visited. |
| 294 |
/// The "output" of compiling a state is the 'union' vector, which is turn |
| 295 |
/// converted to a NFA union state. Each branch of the union corresponds to a |
| 296 |
/// chunk in the trie state. |
| 297 |
/// |
| 298 |
/// 'sparse' corresponds to the set of transitions for a particular chunk in a |
| 299 |
/// trie state. It is ultimately converted to an NFA sparse state. The 'sparse' |
| 300 |
/// field, after being converted to a sparse NFA state, is reused for any |
| 301 |
/// subsequent chunks in the trie state, if any exist. |
| 302 |
#[derive(Debug)] |
| 303 |
struct Frame<'a> { |
| 304 |
/// The remaining chunks to visit for a trie state. |
| 305 |
chunks: StateChunksIter<'a>, |
| 306 |
/// The transitions of the current chunk that we're iterating over. Since |
| 307 |
/// every trie state has at least one chunk, every frame is initialized |
| 308 |
/// with the first chunk's transitions ready to be consumed. |
| 309 |
transitions: core::slice::Iter<'a, Transition>, |
| 310 |
/// The NFA state IDs pointing to the start of each chunk compiled by |
| 311 |
/// this trie state. This ultimately gets converted to an NFA union once |
| 312 |
/// the entire trie state (and all of its children) have been compiled. |
| 313 |
/// The order of these matters for leftmost-first match semantics, since |
| 314 |
/// earlier matches in the union are preferred over later ones. |
| 315 |
union: Vec<StateID>, |
| 316 |
/// The actual NFA transitions for a single chunk in a trie state. This |
| 317 |
/// gets converted to an NFA sparse state, and its corresponding NFA state |
| 318 |
/// ID should get added to 'union'. |
| 319 |
sparse: Vec<thompson::Transition>, |
| 320 |
} |
| 321 |
|
| 322 |
impl<'a> Frame<'a> { |
| 323 |
/// Create a new stack frame for trie traversal. This initializes the |
| 324 |
/// 'transitions' iterator to the transitions for the first chunk, with the |
| 325 |
/// 'chunks' iterator being every chunk after the first one. |
| 326 |
fn new(state: &'a State) -> Frame<'a> { |
| 327 |
let mut chunks = state.chunks(); |
| 328 |
// every state has at least 1 chunk |
| 329 |
let chunk = chunks.next().unwrap(); |
| 330 |
let transitions = chunk.iter(); |
| 331 |
Frame { chunks, transitions, union: vec![], sparse: vec![] } |
| 332 |
} |
| 333 |
} |
| 334 |
|
| 335 |
/// A state in a trie. |
| 336 |
/// |
| 337 |
/// This uses a sparse representation. Since we don't use literal tries |
| 338 |
/// for searching, and ultimately (and compilation requires visiting every |
| 339 |
/// transition anyway), we use a sparse representation for transitions. This |
| 340 |
/// means we save on memory, at the expense of 'LiteralTrie::add' being perhaps |
| 341 |
/// a bit slower. |
| 342 |
/// |
| 343 |
/// While 'transitions' is pretty standard as far as tries goes, the 'chunks' |
| 344 |
/// piece here is more unusual. In effect, 'chunks' defines a partitioning |
| 345 |
/// of 'transitions', where each chunk corresponds to a distinct set of |
| 346 |
/// transitions. The key invariant is that a transition in one chunk cannot |
| 347 |
/// be moved to another chunk. This is the secret sauce that preserve |
| 348 |
/// leftmost-first match semantics. |
| 349 |
/// |
| 350 |
/// A new chunk is added whenever we mark a state as a match state. Once a |
| 351 |
/// new chunk is added, the old active chunk is frozen and is never mutated |
| 352 |
/// again. The new chunk becomes the active chunk, which is defined as |
| 353 |
/// '&transitions[chunks.last().map_or(0, |c| c.1)..]'. Thus, a state where |
| 354 |
/// 'chunks' is empty actually contains one chunk. Thus, every state contains |
| 355 |
/// at least one (possibly empty) chunk. |
| 356 |
/// |
| 357 |
/// A "leaf" state is a state that has no outgoing transitions (so |
| 358 |
/// 'transitions' is empty). Note that there is no way for a leaf state to be a |
| 359 |
/// non-matching state. (Although while building the trie, within 'add', a leaf |
| 360 |
/// state may exist while not containing any matches. But this invariant is |
| 361 |
/// only broken within 'add'. Once 'add' returns, the invariant is upheld.) |
| 362 |
#[derive(Clone, Default)] |
| 363 |
struct State { |
| 364 |
transitions: Vec<Transition>, |
| 365 |
chunks: Vec<(usize, usize)>, |
| 366 |
} |
| 367 |
|
| 368 |
impl State { |
| 369 |
/// Mark this state as a match state and freeze the active chunk such that |
| 370 |
/// it can not be further mutated. |
| 371 |
fn add_match(&mut self) { |
| 372 |
// This is not strictly necessary, but there's no point in recording |
| 373 |
// another match by adding another chunk if the state has no |
| 374 |
// transitions. Note though that we only skip this if we already know |
| 375 |
// this is a match state, which is only true if 'chunks' is not empty. |
| 376 |
// Basically, if we didn't do this, nothing semantically would change, |
| 377 |
// but we'd end up pushing another chunk and potentially triggering an |
| 378 |
// alloc. |
| 379 |
if self.transitions.is_empty() && !self.chunks.is_empty() { |
| 380 |
return; |
| 381 |
} |
| 382 |
let chunk_start = self.active_chunk_start(); |
| 383 |
let chunk_end = self.transitions.len(); |
| 384 |
self.chunks.push((chunk_start, chunk_end)); |
| 385 |
} |
| 386 |
|
| 387 |
/// Returns true if and only if this state is a leaf state. That is, a |
| 388 |
/// state that has no outgoing transitions. |
| 389 |
fn is_leaf(&self) -> bool { |
| 390 |
self.transitions.is_empty() |
| 391 |
} |
| 392 |
|
| 393 |
/// Returns an iterator over all of the chunks (including the currently |
| 394 |
/// active chunk) in this state. Since the active chunk is included, the |
| 395 |
/// iterator is guaranteed to always yield at least one chunk (although the |
| 396 |
/// chunk may be empty). |
| 397 |
fn chunks(&self) -> StateChunksIter<'_> { |
| 398 |
StateChunksIter { |
| 399 |
transitions: &*self.transitions, |
| 400 |
chunks: self.chunks.iter(), |
| 401 |
active: Some(self.active_chunk()), |
| 402 |
} |
| 403 |
} |
| 404 |
|
| 405 |
/// Returns the active chunk as a slice of transitions. |
| 406 |
fn active_chunk(&self) -> &[Transition] { |
| 407 |
let start = self.active_chunk_start(); |
| 408 |
&self.transitions[start..] |
| 409 |
} |
| 410 |
|
| 411 |
/// Returns the index into 'transitions' where the active chunk starts. |
| 412 |
fn active_chunk_start(&self) -> usize { |
| 413 |
self.chunks.last().map_or(0, |&(_, end)| end) |
| 414 |
} |
| 415 |
} |
| 416 |
|
| 417 |
impl core::fmt::Debug for State { |
| 418 |
fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result { |
| 419 |
let mut spacing = " "; |
| 420 |
for (i, chunk) in self.chunks().enumerate() { |
| 421 |
if i > 0 { |
| 422 |
write!(f, "{}MATCH", spacing)?; |
| 423 |
} |
| 424 |
spacing = ""; |
| 425 |
for (j, t) in chunk.iter().enumerate() { |
| 426 |
spacing = " "; |
| 427 |
if j == 0 && i > 0 { |
| 428 |
write!(f, " ")?; |
| 429 |
} else if j > 0 { |
| 430 |
write!(f, ", ")?; |
| 431 |
} |
| 432 |
write!(f, "{:?}", t)?; |
| 433 |
} |
| 434 |
} |
| 435 |
Ok(()) |
| 436 |
} |
| 437 |
} |
| 438 |
|
| 439 |
/// An iterator over all of the chunks in a state, including the active chunk. |
| 440 |
/// |
| 441 |
/// This iterator is created by `State::chunks`. We name this iterator so that |
| 442 |
/// we can include it in the `Frame` type for non-recursive trie traversal. |
| 443 |
#[derive(Debug)] |
| 444 |
struct StateChunksIter<'a> { |
| 445 |
transitions: &'a [Transition], |
| 446 |
chunks: core::slice::Iter<'a, (usize, usize)>, |
| 447 |
active: Option<&'a [Transition]>, |
| 448 |
} |
| 449 |
|
| 450 |
impl<'a> Iterator for StateChunksIter<'a> { |
| 451 |
type Item = &'a [Transition]; |
| 452 |
|
| 453 |
fn next(&mut self) -> Option<&'a [Transition]> { |
| 454 |
if let Some(&(start, end)) = self.chunks.next() { |
| 455 |
return Some(&self.transitions[start..end]); |
| 456 |
} |
| 457 |
if let Some(chunk) = self.active.take() { |
| 458 |
return Some(chunk); |
| 459 |
} |
| 460 |
None |
| 461 |
} |
| 462 |
} |
| 463 |
|
| 464 |
/// A single transition in a trie to another state. |
| 465 |
#[derive(Clone, Copy)] |
| 466 |
struct Transition { |
| 467 |
byte: u8, |
| 468 |
next: StateID, |
| 469 |
} |
| 470 |
|
| 471 |
impl core::fmt::Debug for Transition { |
| 472 |
fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result { |
| 473 |
write!( |
| 474 |
f, |
| 475 |
"{:?} => {}", |
| 476 |
crate::util::escape::DebugByte(self.byte), |
| 477 |
self.next.as_usize() |
| 478 |
) |
| 479 |
} |
| 480 |
} |
| 481 |
|
| 482 |
#[cfg(test)] |
| 483 |
mod tests { |
| 484 |
use bstr::B; |
| 485 |
use regex_syntax::hir::Hir; |
| 486 |
|
| 487 |
use super::*; |
| 488 |
|
| 489 |
#[test] |
| 490 |
fn zap() { |
| 491 |
let mut trie = LiteralTrie::forward(); |
| 492 |
trie.add(b"zapper").unwrap(); |
| 493 |
trie.add(b"z").unwrap(); |
| 494 |
trie.add(b"zap").unwrap(); |
| 495 |
|
| 496 |
let got = trie.compile_to_hir(); |
| 497 |
let expected = Hir::concat(vec![ |
| 498 |
Hir::literal(B("z")), |
| 499 |
Hir::alternation(vec![ |
| 500 |
Hir::literal(B("apper")), |
| 501 |
Hir::empty(), |
| 502 |
Hir::literal(B("ap")), |
| 503 |
]), |
| 504 |
]); |
| 505 |
assert_eq!(expected, got); |
| 506 |
} |
| 507 |
|
| 508 |
#[test] |
| 509 |
fn maker() { |
| 510 |
let mut trie = LiteralTrie::forward(); |
| 511 |
trie.add(b"make").unwrap(); |
| 512 |
trie.add(b"maple").unwrap(); |
| 513 |
trie.add(b"maker").unwrap(); |
| 514 |
|
| 515 |
let got = trie.compile_to_hir(); |
| 516 |
let expected = Hir::concat(vec![ |
| 517 |
Hir::literal(B("ma")), |
| 518 |
Hir::alternation(vec![ |
| 519 |
Hir::concat(vec![ |
| 520 |
Hir::literal(B("ke")), |
| 521 |
Hir::alternation(vec![Hir::empty(), Hir::literal(B("r"))]), |
| 522 |
]), |
| 523 |
Hir::literal(B("ple")), |
| 524 |
]), |
| 525 |
]); |
| 526 |
assert_eq!(expected, got); |
| 527 |
} |
| 528 |
} |