1 // Copyright 2014 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 // FIXME: Currently, the VM simulates an NFA. It would be nice to have another
12 // VM that simulates a DFA.
14 // According to Russ Cox[1], a DFA performs better than an NFA, principally
15 // because it reuses states previously computed by the machine *and* doesn't
16 // keep track of capture groups. The drawback of a DFA (aside from its
17 // complexity) is that it can't accurately return the locations of submatches.
18 // The NFA *can* do that. (This is my understanding anyway.)
20 // Cox suggests that a DFA ought to be used to answer "does this match" and
21 // "where does it match" questions. (In the latter, the starting position of
22 // the match is computed by executing the regex backwards.) Cox also suggests
23 // that a DFA should be run when asking "where are the submatches", which can
24 // 1) quickly answer "no" is there's no match and 2) discover the substring
25 // that matches, which means running the NFA on smaller input.
27 // Currently, the NFA simulation implemented below does some dirty tricks to
28 // avoid tracking capture groups when they aren't needed (which only works
29 // for 'is_match', not 'find'). This is a half-measure, but does provide some
32 // AFAIK, the DFA/NFA approach is implemented in RE2/C++ but *not* in RE2/Go.
34 // [1] - http://swtch.com/~rsc/regex/regex3.html
38 use std::slice::MutableVector;
41 Match, OneChar, CharClass, Any, EmptyBegin, EmptyEnd, EmptyWordBoundary,
44 use parse::{FLAG_NOCASE, FLAG_MULTI, FLAG_DOTNL, FLAG_NEGATED};
45 use unicode::regex::PERLW;
47 pub type CaptureLocs = Vec<Option<uint>>;
49 /// Indicates the type of match to be performed by the VM.
51 /// Only checks if a match exists or not. Does not return location.
53 /// Returns the start and end indices of the entire match in the input
56 /// Returns the start and end indices of each submatch in the input given.
60 /// Runs an NFA simulation on the compiled expression given on the search text
61 /// `input`. The search begins at byte index `start` and ends at byte index
62 /// `end`. (The range is specified here so that zero-width assertions will work
63 /// correctly when searching for successive non-overlapping matches.)
65 /// The `which` parameter indicates what kind of capture information the caller
66 /// wants. There are three choices: match existence only, the location of the
67 /// entire match or the locations of the entire match in addition to the
68 /// locations of each submatch.
69 pub fn run<'r, 't>(which: MatchKind, prog: &'r Program, input: &'t str,
70 start: uint, end: uint) -> CaptureLocs {
78 chars: CharReader::new(input),
89 chars: CharReader<'t>,
92 /// Indicates the next action to take after a single non-empty instruction
95 /// This is returned if and only if a Match instruction is reached and
96 /// we only care about the existence of a match. It instructs the VM to
99 /// Indicates that a match was found. Thus, the rest of the states in the
100 /// *current* queue should be dropped (i.e., leftmost-first semantics).
101 /// States in the "next" queue can still be processed.
103 /// No match was found. Continue with the next state in the queue.
107 impl<'r, 't> Nfa<'r, 't> {
108 fn run(&mut self) -> CaptureLocs {
109 let ncaps = match self.which {
112 Submatches => self.prog.num_captures(),
114 let mut matched = false;
115 let ninsts = self.prog.insts.len();
116 let mut clist = &mut Threads::new(self.which, ninsts, ncaps);
117 let mut nlist = &mut Threads::new(self.which, ninsts, ncaps);
119 let mut groups = Vec::from_elem(ncaps * 2, None);
121 // Determine if the expression starts with a '^' so we can avoid
123 // Make sure multi-line mode isn't enabled for it, otherwise we can't
124 // drop the initial .*?
126 match self.prog.insts[1] {
127 EmptyBegin(flags) if flags & FLAG_MULTI == 0 => true,
131 self.ic = self.start;
132 let mut next_ic = self.chars.set(self.start);
133 while self.ic <= self.end {
135 // We have a match and we're done exploring alternatives.
141 // If there are no threads to try, then we'll have to start
142 // over at the beginning of the regex.
143 // BUT, if there's a literal prefix for the program, try to
144 // jump ahead quickly. If it can't be found, then we can bail
146 if self.prog.prefix.len() > 0 && clist.size == 0 {
147 let needle = self.prog.prefix.as_slice().as_bytes();
148 let haystack = self.input.as_bytes().slice_from(self.ic);
149 match find_prefix(needle, haystack) {
153 next_ic = self.chars.set(self.ic);
159 // This simulates a preceding '.*?' for every regex by adding
160 // a state starting at the current position in the input for the
161 // beginning of the program only if we don't already have a match.
162 if clist.size == 0 || (!prefix_anchor && !matched) {
163 self.add(clist, 0, groups.as_mut_slice())
166 // Now we try to read the next character.
167 // As a result, the 'step' method will look at the previous
170 next_ic = self.chars.advance();
172 for i in range(0, clist.size) {
173 let pc = clist.pc(i);
174 let step_state = self.step(groups.as_mut_slice(), nlist,
175 clist.groups(i), pc);
177 StepMatchEarlyReturn => return vec![Some(0), Some(0)],
178 StepMatch => { matched = true; break },
182 mem::swap(&mut clist, &mut nlist);
186 Exists if matched => vec![Some(0), Some(0)],
187 Exists => vec![None, None],
188 Location | Submatches => groups,
192 fn step(&self, groups: &mut [Option<uint>], nlist: &mut Threads,
193 caps: &mut [Option<uint>], pc: uint)
195 match self.prog.insts[pc] {
199 return StepMatchEarlyReturn
207 for (slot, val) in groups.mut_iter().zip(caps.iter()) {
214 OneChar(c, flags) => {
215 if self.char_eq(flags & FLAG_NOCASE > 0, self.chars.prev, c) {
216 self.add(nlist, pc+1, caps);
219 CharClass(ref ranges, flags) => {
220 if self.chars.prev.is_some() {
221 let c = self.chars.prev.unwrap();
222 let negate = flags & FLAG_NEGATED > 0;
223 let casei = flags & FLAG_NOCASE > 0;
224 let found = ranges.as_slice();
225 let found = found.bsearch(|&rc| class_cmp(casei, c, rc));
226 let found = found.is_some();
228 self.add(nlist, pc+1, caps);
233 if flags & FLAG_DOTNL > 0
234 || !self.char_eq(false, self.chars.prev, '\n') {
235 self.add(nlist, pc+1, caps)
238 EmptyBegin(_) | EmptyEnd(_) | EmptyWordBoundary(_)
239 | Save(_) | Jump(_) | Split(_, _) => {},
244 fn add(&self, nlist: &mut Threads, pc: uint, groups: &mut [Option<uint>]) {
245 if nlist.contains(pc) {
248 // We have to add states to the threads list even if their empty.
249 // TL;DR - It prevents cycles.
250 // If we didn't care about cycles, we'd *only* add threads that
251 // correspond to non-jumping instructions (OneChar, Any, Match, etc.).
252 // But, it's possible for valid regexs (like '(a*)*') to result in
253 // a cycle in the instruction list. e.g., We'll keep chasing the Split
254 // instructions forever.
255 // So we add these instructions to our thread queue, but in the main
256 // VM loop, we look for them but simply ignore them.
257 // Adding them to the queue prevents them from being revisited so we
258 // can avoid cycles (and the inevitable stack overflow).
260 // We make a minor optimization by indicating that the state is "empty"
261 // so that its capture groups are not filled in.
262 match self.prog.insts[pc] {
263 EmptyBegin(flags) => {
264 let multi = flags & FLAG_MULTI > 0;
265 nlist.add(pc, groups, true);
266 if self.chars.is_begin()
267 || (multi && self.char_is(self.chars.prev, '\n')) {
268 self.add(nlist, pc + 1, groups)
272 let multi = flags & FLAG_MULTI > 0;
273 nlist.add(pc, groups, true);
274 if self.chars.is_end()
275 || (multi && self.char_is(self.chars.cur, '\n')) {
276 self.add(nlist, pc + 1, groups)
279 EmptyWordBoundary(flags) => {
280 nlist.add(pc, groups, true);
281 if self.chars.is_word_boundary() == !(flags & FLAG_NEGATED > 0) {
282 self.add(nlist, pc + 1, groups)
286 nlist.add(pc, groups, true);
288 Location if slot <= 1 => {
289 let old = groups[slot];
290 groups[slot] = Some(self.ic);
291 self.add(nlist, pc + 1, groups);
295 let old = groups[slot];
296 groups[slot] = Some(self.ic);
297 self.add(nlist, pc + 1, groups);
300 Exists | Location => self.add(nlist, pc + 1, groups),
304 nlist.add(pc, groups, true);
305 self.add(nlist, to, groups)
308 nlist.add(pc, groups, true);
309 self.add(nlist, x, groups);
310 self.add(nlist, y, groups);
312 Match | OneChar(_, _) | CharClass(_, _) | Any(_) => {
313 nlist.add(pc, groups, false);
318 // FIXME: For case insensitive comparisons, it uses the uppercase
319 // character and tests for equality. IIUC, this does not generalize to
320 // all of Unicode. I believe we need to check the entire fold for each
321 // character. This will be easy to add if and when it gets added to Rust's
324 fn char_eq(&self, casei: bool, textc: Option<char>, regc: char) -> bool {
329 || (casei && regc.to_uppercase() == textc.to_uppercase())
335 fn char_is(&self, textc: Option<char>, regc: char) -> bool {
340 /// CharReader is responsible for maintaining a "previous" and a "current"
341 /// character. This one-character lookahead is necessary for assertions that
342 /// look one character before or after the current position.
343 pub struct CharReader<'t> {
344 /// The previous character read. It is None only when processing the first
345 /// character of the input.
346 pub prev: Option<char>,
347 /// The current character.
348 pub cur: Option<char>,
353 impl<'t> CharReader<'t> {
354 /// Returns a new CharReader that advances through the input given.
355 /// Note that a CharReader has no knowledge of the range in which to search
357 pub fn new(input: &'t str) -> CharReader<'t> {
366 /// Sets the previous and current character given any arbitrary byte
367 /// index (at a unicode codepoint boundary).
369 pub fn set(&mut self, ic: uint) -> uint {
374 if self.input.len() == 0 {
378 let i = cmp::min(ic, self.input.len());
379 let prev = self.input.char_range_at_reverse(i);
380 self.prev = Some(prev.ch);
382 if ic < self.input.len() {
383 let cur = self.input.char_range_at(ic);
384 self.cur = Some(cur.ch);
385 self.next = cur.next;
392 /// Does the same as `set`, except it always advances to the next
393 /// character in the input (and therefore does half as many UTF8 decodings).
395 pub fn advance(&mut self) -> uint {
396 self.prev = self.cur;
397 if self.next < self.input.len() {
398 let cur = self.input.char_range_at(self.next);
399 self.cur = Some(cur.ch);
400 self.next = cur.next;
403 self.next = self.input.len() + 1;
408 /// Returns true if and only if this is the beginning of the input
409 /// (ignoring the range of the input to search).
411 pub fn is_begin(&self) -> bool { self.prev.is_none() }
413 /// Returns true if and only if this is the end of the input
414 /// (ignoring the range of the input to search).
416 pub fn is_end(&self) -> bool { self.cur.is_none() }
418 /// Returns true if and only if the current position is a word boundary.
419 /// (Ignoring the range of the input to search.)
420 pub fn is_word_boundary(&self) -> bool {
422 return is_word(self.cur)
425 return is_word(self.prev)
427 (is_word(self.cur) && !is_word(self.prev))
428 || (is_word(self.prev) && !is_word(self.cur))
434 groups: Vec<Option<uint>>,
445 // This is using a wicked neat trick to provide constant time lookup
446 // for threads in the queue using a sparse set. A queue of threads is
447 // allocated once with maximal size when the VM initializes and is reused
448 // throughout execution. That is, there should be zero allocation during
449 // the execution of a VM.
451 // See http://research.swtch.com/sparse for the deets.
452 fn new(which: MatchKind, num_insts: uint, ncaps: uint) -> Threads {
455 queue: Vec::from_fn(num_insts, |_| {
456 Thread { pc: 0, groups: Vec::from_elem(ncaps * 2, None) }
458 sparse: Vec::from_elem(num_insts, 0u),
463 fn add(&mut self, pc: uint, groups: &[Option<uint>], empty: bool) {
464 let t = self.queue.get_mut(self.size);
466 match (empty, self.which) {
467 (_, Exists) | (true, _) => {},
468 (false, Location) => {
469 *t.groups.get_mut(0) = groups[0];
470 *t.groups.get_mut(1) = groups[1];
472 (false, Submatches) => {
473 for (slot, val) in t.groups.mut_iter().zip(groups.iter()) {
478 *self.sparse.get_mut(pc) = self.size;
483 fn contains(&self, pc: uint) -> bool {
484 let s = self.sparse[pc];
485 s < self.size && self.queue[s].pc == pc
489 fn empty(&mut self) {
494 fn pc(&self, i: uint) -> uint {
499 fn groups<'r>(&'r mut self, i: uint) -> &'r mut [Option<uint>] {
500 self.queue.get_mut(i).groups.as_mut_slice()
504 /// Returns true if the character is a word character, according to the
505 /// (Unicode friendly) Perl character class '\w'.
506 /// Note that this is only use for testing word boundaries. The actual '\w'
507 /// is encoded as a CharClass instruction.
508 pub fn is_word(c: Option<char>) -> bool {
510 None => return false,
513 // Try the common ASCII case before invoking binary search.
515 '_' | '0' .. '9' | 'a' .. 'z' | 'A' .. 'Z' => true,
516 _ => PERLW.bsearch(|&(start, end)| {
517 if c >= start && c <= end {
519 } else if start > c {
528 /// Given a character and a single character class range, return an ordering
529 /// indicating whether the character is less than the start of the range,
530 /// in the range (inclusive) or greater than the end of the range.
532 /// If `casei` is `true`, then this ordering is computed case insensitively.
534 /// This function is meant to be used with a binary search.
536 fn class_cmp(casei: bool, mut textc: char,
537 (mut start, mut end): (char, char)) -> Ordering {
539 // FIXME: This is pretty ridiculous. All of this case conversion
540 // can be moved outside this function:
541 // 1) textc should be uppercased outside the bsearch.
542 // 2) the character class itself should be uppercased either in the
543 // parser or the compiler.
544 // FIXME: This is too simplistic for correct Unicode support.
546 textc = textc.to_uppercase();
547 start = start.to_uppercase();
548 end = end.to_uppercase();
550 if textc >= start && textc <= end {
552 } else if start > textc {
559 /// Returns the starting location of `needle` in `haystack`.
560 /// If `needle` is not in `haystack`, then `None` is returned.
562 /// Note that this is using a naive substring algorithm.
564 pub fn find_prefix(needle: &[u8], haystack: &[u8]) -> Option<uint> {
565 let (hlen, nlen) = (haystack.len(), needle.len());
566 if nlen > hlen || nlen == 0 {
569 for (offset, window) in haystack.windows(nlen).enumerate() {
570 if window == needle {