regex 0.1.33

// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
// file at the top-level directory of this distribution and at
// http://rust-lang.org/COPYRIGHT.
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.

// FIXME: Currently, the VM simulates an NFA. It would be nice to have another
// VM that simulates a DFA.
//
// According to Russ Cox[1], a DFA performs better than an NFA, principally
// because it reuses states previously computed by the machine *and* doesn't
// keep track of capture groups. The drawback of a DFA (aside from its
// complexity) is that it can't accurately return the locations of submatches.
// The NFA *can* do that. (This is my understanding anyway.)
//
// Cox suggests that a DFA ought to be used to answer "does this match" and
// "where does it match" questions. (In the latter, the starting position of
// the match is computed by executing the regex backwards.) Cox also suggests
// that a DFA should be run when asking "where are the submatches", which can
// 1) quickly answer "no" is there's no match and 2) discover the substring
// that matches, which means running the NFA on smaller input.
//
// Currently, the NFA simulation implemented below does some dirty tricks to
// avoid tracking capture groups when they aren't needed (which only works
// for 'is_match', not 'find'). This is a half-measure, but does provide some
// perf improvement.
//
// AFAIK, the DFA/NFA approach is implemented in RE2/C++ but *not* in RE2/Go.
//
// [1] - http://swtch.com/~rsc/regex/regex3.html

use self::MatchKind::*;
use self::StepState::*;

use std::cmp;
use std::mem;

use compile::Program;
use compile::Inst::*;
use syntax;

pub type CaptureLocs = Vec<Option<usize>>;

/// Indicates the type of match to be performed by the VM.
#[derive(Copy, Clone)]
pub enum MatchKind {
    /// Only checks if a match exists or not. Does not return location.
    Exists,
    /// Returns the start and end indices of the entire match in the input
    /// given.
    Location,
    /// Returns the start and end indices of each submatch in the input given.
    Submatches,
}

/// Runs an NFA simulation on the compiled expression given on the search text
/// `input`. The search begins at byte index `start` and ends at byte index
/// `end`. (The range is specified here so that zero-width assertions will work
/// correctly when searching for successive non-overlapping matches.)
///
/// The `which` parameter indicates what kind of capture information the caller
/// wants. There are three choices: match existence only, the location of the
/// entire match or the locations of the entire match in addition to the
/// locations of each submatch.
pub fn run<'r, 't>(which: MatchKind, prog: &'r Program, input: &'t str,
                   start: usize, end: usize) -> CaptureLocs {
    Nfa {
        which: which,
        prog: prog,
        input: input,
        start: start,
        end: end,
        ic: 0,
        chars: CharReader::new(input),
    }.run()
}

struct Nfa<'r, 't> {
    which: MatchKind,
    prog: &'r Program,
    input: &'t str,
    start: usize,
    end: usize,
    ic: usize,
    chars: CharReader<'t>,
}

/// Indicates the next action to take after a single non-empty instruction
/// is processed.
#[derive(Copy, Clone)]
pub enum StepState {
    /// This is returned if and only if a Match instruction is reached and
    /// we only care about the existence of a match. It instructs the VM to
    /// quit early.
    StepMatchEarlyReturn,
    /// Indicates that a match was found. Thus, the rest of the states in the
    /// *current* queue should be dropped (i.e., leftmost-first semantics).
    /// States in the "next" queue can still be processed.
    StepMatch,
    /// No match was found. Continue with the next state in the queue.
    StepContinue,
}

impl<'r, 't> Nfa<'r, 't> {
    fn run(&mut self) -> CaptureLocs {
        let ncaps = match self.which {
            Exists => 0,
            Location => 1,
            Submatches => self.prog.num_captures(),
        };
        let mut matched = false;
        let ninsts = self.prog.insts.len();
        let mut clist = Threads::new(self.which, ninsts, ncaps);
        let mut nlist = Threads::new(self.which, ninsts, ncaps);
        let mut groups = vec![None; ncaps * 2];

        // Determine if the expression starts with a '^' so we can avoid
        // simulating .*?
        // Make sure multi-line mode isn't enabled for it, otherwise we can't
        // drop the initial .*?
        let prefix_anchor = match self.prog.insts[1] {
            StartText => true,
            _ => false,
        };

        self.ic = self.start;
        let mut next_ic = self.chars.set(self.start);
        while self.ic <= self.end {
            if clist.size == 0 {
                // We have a match and we're done exploring alternatives.
                // Time to quit.
                if matched {
                    break
                }

                // If the expression starts with a '^' we can terminate as soon
                // as the last thread dies.
                if self.ic != 0 && prefix_anchor {
                    break;
                }

                // If there are no threads to try, then we'll have to start
                // over at the beginning of the regex.
                // BUT, if there's a literal prefix for the program, try to
                // jump ahead quickly. If it can't be found, then we can bail
                // out early.
                if self.prog.prefix.len() > 0 {
                    let needle = self.prog.prefix.as_bytes();
                    let haystack = &self.input.as_bytes()[self.ic..];
                    match find_prefix(needle, haystack) {
                        None => break,
                        Some(i) => {
                            self.ic += i;
                            next_ic = self.chars.set(self.ic);
                        }
                    }
                }
            }

            // This simulates a preceding '.*?' for every regex by adding
            // a state starting at the current position in the input for the
            // beginning of the program only if we don't already have a match.
            if clist.size == 0 || (!prefix_anchor && !matched) {
                self.add(&mut clist, 0, &mut groups)
            }

            // Now we try to read the next character.
            // As a result, the 'step' method will look at the previous
            // character.
            self.ic = next_ic;
            next_ic = self.chars.advance();

            for i in 0..clist.size {
                let pc = clist.pc(i);
                let step_state = self.step(&mut groups, &mut nlist,
                                           clist.groups(i), pc);
                match step_state {
                    StepMatchEarlyReturn => return vec![Some(0), Some(0)],
                    StepMatch => { matched = true; break },
                    StepContinue => {},
                }
            }
            mem::swap(&mut clist, &mut nlist);
            nlist.empty();
        }
        match self.which {
            Exists if matched     => vec![Some(0), Some(0)],
            Exists                => vec![None, None],
            Location | Submatches => groups,
        }
    }

    fn step(&self, groups: &mut [Option<usize>], nlist: &mut Threads,
            caps: &mut [Option<usize>], pc: usize)
           -> StepState {
        match self.prog.insts[pc] {
            Match => {
                match self.which {
                    Exists => {
                        return StepMatchEarlyReturn
                    }
                    Location => {
                        groups[0] = caps[0];
                        groups[1] = caps[1];
                        return StepMatch
                    }
                    Submatches => {
                        for (slot, val) in groups.iter_mut().zip(caps.iter()) {
                            *slot = *val;
                        }
                        return StepMatch
                    }
                }
            }
            OneChar { c, casei } => {
                if self.char_eq(casei, self.chars.prev, c) {
                    self.add(nlist, pc+1, caps);
                }
            }
            CharClass(ref cls) => {
                if self.chars.prev.map(|c| cls.matches(c)).unwrap_or(false) {
                    self.add(nlist, pc+1, caps);
                }
            }
            Any => self.add(nlist, pc+1, caps),
            AnyNoNL => {
                if !self.char_eq(false, self.chars.prev, '\n') {
                    self.add(nlist, pc+1, caps)
                }
            }
            StartLine | EndLine | StartText | EndText
            | WordBoundary | NotWordBoundary
            | Save(_) | Jump(_) | Split(_, _) => {},
        }
        StepContinue
    }

    fn add(&self, nlist: &mut Threads, pc: usize, groups: &mut [Option<usize>]) {
        if nlist.contains(pc) {
            return
        }
        // We have to add states to the threads list even if their empty.
        // TL;DR - It prevents cycles.
        // If we didn't care about cycles, we'd *only* add threads that
        // correspond to non-jumping instructions (OneChar, Any, Match, etc.).
        // But, it's possible for valid regexs (like '(a*)*') to result in
        // a cycle in the instruction list. e.g., We'll keep chasing the Split
        // instructions forever.
        // So we add these instructions to our thread queue, but in the main
        // VM loop, we look for them but simply ignore them.
        // Adding them to the queue prevents them from being revisited so we
        // can avoid cycles (and the inevitable stack overflow).
        //
        // We make a minor optimization by indicating that the state is "empty"
        // so that its capture groups are not filled in.
        match self.prog.insts[pc] {
            StartLine => {
                nlist.add(pc, groups, true);
                if self.chars.is_begin() || self.char_is(self.chars.prev, '\n') {
                    self.add(nlist, pc + 1, groups);
                }
            }
            StartText => {
                nlist.add(pc, groups, true);
                if self.chars.is_begin() {
                    self.add(nlist, pc + 1, groups);
                }
            }
            EndLine => {
                nlist.add(pc, groups, true);
                if self.chars.is_end() || self.char_is(self.chars.cur, '\n') {
                    self.add(nlist, pc + 1, groups)
                }
            }
            EndText => {
                nlist.add(pc, groups, true);
                if self.chars.is_end() {
                    self.add(nlist, pc + 1, groups)
                }
            }
            WordBoundary => {
                nlist.add(pc, groups, true);
                if self.chars.is_word_boundary() {
                    self.add(nlist, pc + 1, groups);
                }
            }
            NotWordBoundary => {
                nlist.add(pc, groups, true);
                if !self.chars.is_word_boundary() {
                    self.add(nlist, pc + 1, groups);
                }
            }
            Save(slot) => {
                nlist.add(pc, groups, true);
                match self.which {
                    Location if slot <= 1 => {
                        let old = groups[slot];
                        groups[slot] = Some(self.ic);
                        self.add(nlist, pc + 1, groups);
                        groups[slot] = old;
                    }
                    Submatches => {
                        let old = groups[slot];
                        groups[slot] = Some(self.ic);
                        self.add(nlist, pc + 1, groups);
                        groups[slot] = old;
                    }
                    Exists | Location => self.add(nlist, pc + 1, groups),
                }
            }
            Jump(to) => {
                nlist.add(pc, groups, true);
                self.add(nlist, to, groups)
            }
            Split(x, y) => {
                nlist.add(pc, groups, true);
                self.add(nlist, x, groups);
                self.add(nlist, y, groups);
            }
            Match | OneChar{..} | CharClass(_) | Any | AnyNoNL => {
                nlist.add(pc, groups, false);
            }
        }
    }

    // Use Unicode simple case folding for case insensitive comparisons,
    // as we’re matching individual code points.
    #[inline]
    fn char_eq(&self, casei: bool, textc: Option<char>, regc: char) -> bool {
        match textc {
            None => false,
            Some(textc) => {
                regc == textc || (casei && syntax::simple_case_fold(regc) == syntax::simple_case_fold(textc))
            }
        }
    }

    #[inline]
    fn char_is(&self, textc: Option<char>, regc: char) -> bool {
        textc == Some(regc)
    }
}

/// CharReader is responsible for maintaining a "previous" and a "current"
/// character. This one-character lookahead is necessary for assertions that
/// look one character before or after the current position.
pub struct CharReader<'t> {
    /// The previous character read. It is None only when processing the first
    /// character of the input.
    pub prev: Option<char>,
    /// The current character.
    pub cur: Option<char>,
    input: &'t str,
    next: usize,
}

impl<'t> CharReader<'t> {
    /// Returns a new CharReader that advances through the input given.
    /// Note that a CharReader has no knowledge of the range in which to search
    /// the input.
    pub fn new(input: &'t str) -> CharReader<'t> {
        CharReader {
            prev: None,
            cur: None,
            input: input,
            next: 0,
       }
    }

    /// Sets the previous and current character given any arbitrary byte
    /// index (at a Unicode codepoint boundary).
    #[inline]
    pub fn set(&mut self, ic: usize) -> usize {
        self.prev = None;
        self.cur = None;
        self.next = 0;

        if self.input.len() == 0 {
            return 1
        }
        if ic > 0 {
            let i = cmp::min(ic, self.input.len());
            self.prev = self.input[..i].chars().rev().next();
        }
        if ic < self.input.len() {
            let cur = self.input[ic..].chars().next().unwrap();
            self.cur = Some(cur);
            self.next = ic + cur.len_utf8();
            self.next
        } else {
            self.input.len() + 1
        }
    }

    /// Does the same as `set`, except it always advances to the next
    /// character in the input (and therefore does half as many UTF8 decodings).
    #[inline]
    pub fn advance(&mut self) -> usize {
        self.prev = self.cur;
        if self.next < self.input.len() {
            let cur = self.input[self.next..].chars().next().unwrap();
            self.cur = Some(cur);
            self.next += cur.len_utf8();
        } else {
            self.cur = None;
            self.next = self.input.len() + 1;
        }
        self.next
    }

    /// Returns true if and only if this is the beginning of the input
    /// (ignoring the range of the input to search).
    #[inline]
    pub fn is_begin(&self) -> bool { self.prev.is_none() }

    /// Returns true if and only if this is the end of the input
    /// (ignoring the range of the input to search).
    #[inline]
    pub fn is_end(&self) -> bool { self.cur.is_none() }

    /// Returns true if and only if the current position is a word boundary.
    /// (Ignoring the range of the input to search.)
    pub fn is_word_boundary(&self) -> bool {
        fn is_word(c: Option<char>) -> bool {
            c.map(syntax::is_word_char).unwrap_or(false)
        }

        if self.is_begin() {
            return is_word(self.cur);
        }
        if self.is_end() {
            return is_word(self.prev);
        }
        (is_word(self.cur) && !is_word(self.prev))
        || (is_word(self.prev) && !is_word(self.cur))
    }
}

#[derive(Clone)]
struct Thread {
    pc: usize,
    groups: Vec<Option<usize>>,
}

struct Threads {
    which: MatchKind,
    queue: Vec<Thread>,
    sparse: Vec<usize>,
    size: usize,
}

impl Threads {
    // This is using a wicked neat trick to provide constant time lookup
    // for threads in the queue using a sparse set. A queue of threads is
    // allocated once with maximal size when the VM initializes and is reused
    // throughout execution. That is, there should be zero allocation during
    // the execution of a VM.
    //
    // See http://research.swtch.com/sparse for the deets.
    fn new(which: MatchKind, num_insts: usize, ncaps: usize) -> Threads {
        let t = Thread { pc: 0, groups: vec![None; ncaps * 2] };
        Threads {
            which: which,
            queue: vec![t; num_insts],
            sparse: vec![0; num_insts],
            size: 0,
        }
    }

    fn add(&mut self, pc: usize, groups: &[Option<usize>], empty: bool) {
        let t = &mut self.queue[self.size];
        t.pc = pc;
        match (empty, self.which) {
            (_, Exists) | (true, _) => {},
            (false, Location) => {
                t.groups[0] = groups[0];
                t.groups[1] = groups[1];
            }
            (false, Submatches) => {
                for (slot, val) in t.groups.iter_mut().zip(groups.iter()) {
                    *slot = *val;
                }
            }
        }
        self.sparse[pc] = self.size;
        self.size += 1;
    }

    #[inline]
    fn contains(&self, pc: usize) -> bool {
        let s = self.sparse[pc];
        s < self.size && self.queue[s].pc == pc
    }

    #[inline]
    fn empty(&mut self) {
        self.size = 0;
    }

    #[inline]
    fn pc(&self, i: usize) -> usize {
        self.queue[i].pc
    }

    #[inline]
    fn groups(&mut self, i: usize) -> &mut [Option<usize>] {
        &mut self.queue[i].groups
    }
}

/// Returns the starting location of `needle` in `haystack`.
/// If `needle` is not in `haystack`, then `None` is returned.
///
/// Note that this is using a naive substring algorithm.
#[inline]
pub fn find_prefix(needle: &[u8], haystack: &[u8]) -> Option<usize> {
    let (hlen, nlen) = (haystack.len(), needle.len());
    if nlen > hlen || nlen == 0 {
        return None
    }
    for (offset, window) in haystack.windows(nlen).enumerate() {
        if window == needle {
            return Some(offset)
        }
    }
    None
}