regex_automata/

determinize.rs

use std::collections::HashMap;
use std::mem;
use std::rc::Rc;

use dense;
use error::Result;
use nfa::{self, NFA};
use sparse_set::SparseSet;
use state_id::{dead_id, StateID};

type DFARepr<S> = dense::Repr<Vec<S>, S>;

/// A determinizer converts an NFA to a DFA.
///
/// This determinizer follows the typical powerset construction, where each
/// DFA state is comprised of one or more NFA states. In the worst case, there
/// is one DFA state for every possible combination of NFA states. In practice,
/// this only happens in certain conditions, typically when there are bounded
/// repetitions.
///
/// The type variable `S` refers to the chosen state identifier representation
/// used for the DFA.
///
/// The lifetime variable `'a` refers to the lifetime of the NFA being
/// converted to a DFA.
#[derive(Debug)]
pub(crate) struct Determinizer<'a, S: StateID> {
    /// The NFA we're converting into a DFA.
    nfa: &'a NFA,
    /// The DFA we're building.
    dfa: DFARepr<S>,
    /// Each DFA state being built is defined as an *ordered* set of NFA
    /// states, along with a flag indicating whether the state is a match
    /// state or not.
    ///
    /// This is never empty. The first state is always a dummy state such that
    /// a state id == 0 corresponds to a dead state.
    builder_states: Vec<Rc<State>>,
    /// A cache of DFA states that already exist and can be easily looked up
    /// via ordered sets of NFA states.
    cache: HashMap<Rc<State>, S>,
    /// Scratch space for a stack of NFA states to visit, for depth first
    /// visiting without recursion.
    stack: Vec<nfa::StateID>,
    /// Scratch space for storing an ordered sequence of NFA states, for
    /// amortizing allocation.
    scratch_nfa_states: Vec<nfa::StateID>,
    /// Whether to build a DFA that finds the longest possible match.
    longest_match: bool,
}

/// An intermediate representation for a DFA state during determinization.
#[derive(Debug, Eq, Hash, PartialEq)]
struct State {
    /// Whether this state is a match state or not.
    is_match: bool,
    /// An ordered sequence of NFA states that make up this DFA state.
    nfa_states: Vec<nfa::StateID>,
}

impl<'a, S: StateID> Determinizer<'a, S> {
    /// Create a new determinizer for converting the given NFA to a DFA.
    pub fn new(nfa: &'a NFA) -> Determinizer<'a, S> {
        let dead = Rc::new(State::dead());
        let mut cache = HashMap::default();
        cache.insert(dead.clone(), dead_id());

        Determinizer {
            nfa,
            dfa: DFARepr::empty().anchored(nfa.is_anchored()),
            builder_states: vec![dead],
            cache,
            stack: vec![],
            scratch_nfa_states: vec![],
            longest_match: false,
        }
    }

    /// Instruct the determinizer to use equivalence classes as the transition
    /// alphabet instead of all possible byte values.
    pub fn with_byte_classes(mut self) -> Determinizer<'a, S> {
        let byte_classes = self.nfa.byte_classes().clone();
        self.dfa = DFARepr::empty_with_byte_classes(byte_classes)
            .anchored(self.nfa.is_anchored());
        self
    }

    /// Instruct the determinizer to build a DFA that recognizes the longest
    /// possible match instead of the leftmost first match. This is useful when
    /// constructing reverse DFAs for finding the start of a match.
    pub fn longest_match(mut self, yes: bool) -> Determinizer<'a, S> {
        self.longest_match = yes;
        self
    }

    /// Build the DFA. If there was a problem constructing the DFA (e.g., if
    /// the chosen state identifier representation is too small), then an error
    /// is returned.
    pub fn build(mut self) -> Result<DFARepr<S>> {
        let representative_bytes: Vec<u8> =
            self.dfa.byte_classes().representatives().collect();
        let mut sparse = self.new_sparse_set();
        let mut uncompiled = vec![self.add_start(&mut sparse)?];
        while let Some(dfa_id) = uncompiled.pop() {
            for &b in &representative_bytes {
                let (next_dfa_id, is_new) =
                    self.cached_state(dfa_id, b, &mut sparse)?;
                self.dfa.add_transition(dfa_id, b, next_dfa_id);
                if is_new {
                    uncompiled.push(next_dfa_id);
                }
            }
        }

        // At this point, we shuffle the matching states in the final DFA to
        // the beginning. This permits a DFA's match loop to detect a match
        // condition by merely inspecting the current state's identifier, and
        // avoids the need for any additional auxiliary storage.
        let is_match: Vec<bool> =
            self.builder_states.iter().map(|s| s.is_match).collect();
        self.dfa.shuffle_match_states(&is_match);
        Ok(self.dfa)
    }

    /// Return the identifier for the next DFA state given an existing DFA
    /// state and an input byte. If the next DFA state already exists, then
    /// return its identifier from the cache. Otherwise, build the state, cache
    /// it and return its identifier.
    ///
    /// The given sparse set is used for scratch space. It must have a capacity
    /// equivalent to the total number of NFA states, but its contents are
    /// otherwise unspecified.
    ///
    /// This routine returns a boolean indicating whether a new state was
    /// built. If a new state is built, then the caller needs to add it to its
    /// frontier of uncompiled DFA states to compute transitions for.
    fn cached_state(
        &mut self,
        dfa_id: S,
        b: u8,
        sparse: &mut SparseSet,
    ) -> Result<(S, bool)> {
        sparse.clear();
        // Compute the set of all reachable NFA states, including epsilons.
        self.next(dfa_id, b, sparse);
        // Build a candidate state and check if it has already been built.
        let state = self.new_state(sparse);
        if let Some(&cached_id) = self.cache.get(&state) {
            // Since we have a cached state, put the constructed state's
            // memory back into our scratch space, so that it can be reused.
            mem::replace(&mut self.scratch_nfa_states, state.nfa_states);
            return Ok((cached_id, false));
        }
        // Nothing was in the cache, so add this state to the cache.
        self.add_state(state).map(|s| (s, true))
    }

    /// Compute the set of all eachable NFA states, including the full epsilon
    /// closure, from a DFA state for a single byte of input.
    fn next(&mut self, dfa_id: S, b: u8, next_nfa_states: &mut SparseSet) {
        next_nfa_states.clear();
        for i in 0..self.builder_states[dfa_id.to_usize()].nfa_states.len() {
            let nfa_id = self.builder_states[dfa_id.to_usize()].nfa_states[i];
            match *self.nfa.state(nfa_id) {
                nfa::State::Union { .. }
                | nfa::State::Fail
                | nfa::State::Match => {}
                nfa::State::Range { range: ref r } => {
                    if r.start <= b && b <= r.end {
                        self.epsilon_closure(r.next, next_nfa_states);
                    }
                }
                nfa::State::Sparse { ref ranges } => {
                    for r in ranges.iter() {
                        if r.start > b {
                            break;
                        } else if r.start <= b && b <= r.end {
                            self.epsilon_closure(r.next, next_nfa_states);
                            break;
                        }
                    }
                }
            }
        }
    }

    /// Compute the epsilon closure for the given NFA state.
    fn epsilon_closure(&mut self, start: nfa::StateID, set: &mut SparseSet) {
        if !self.nfa.state(start).is_epsilon() {
            set.insert(start);
            return;
        }

        self.stack.push(start);
        while let Some(mut id) = self.stack.pop() {
            loop {
                if set.contains(id) {
                    break;
                }
                set.insert(id);
                match *self.nfa.state(id) {
                    nfa::State::Range { .. }
                    | nfa::State::Sparse { .. }
                    | nfa::State::Fail
                    | nfa::State::Match => break,
                    nfa::State::Union { ref alternates } => {
                        id = match alternates.get(0) {
                            None => break,
                            Some(&id) => id,
                        };
                        self.stack.extend(alternates[1..].iter().rev());
                    }
                }
            }
        }
    }

    /// Compute the initial DFA state and return its identifier.
    ///
    /// The sparse set given is used for scratch space, and must have capacity
    /// equal to the total number of NFA states. Its contents are unspecified.
    fn add_start(&mut self, sparse: &mut SparseSet) -> Result<S> {
        sparse.clear();
        self.epsilon_closure(self.nfa.start(), sparse);
        let state = self.new_state(&sparse);
        let id = self.add_state(state)?;
        self.dfa.set_start_state(id);
        Ok(id)
    }

    /// Add the given state to the DFA and make it available in the cache.
    ///
    /// The state initially has no transitions. That is, it transitions to the
    /// dead state for all possible inputs.
    fn add_state(&mut self, state: State) -> Result<S> {
        let id = self.dfa.add_empty_state()?;
        let rstate = Rc::new(state);
        self.builder_states.push(rstate.clone());
        self.cache.insert(rstate, id);
        Ok(id)
    }

    /// Convert the given set of ordered NFA states to a DFA state.
    fn new_state(&mut self, set: &SparseSet) -> State {
        let mut state = State {
            is_match: false,
            nfa_states: mem::replace(&mut self.scratch_nfa_states, vec![]),
        };
        state.nfa_states.clear();

        for &id in set {
            match *self.nfa.state(id) {
                nfa::State::Range { .. } => {
                    state.nfa_states.push(id);
                }
                nfa::State::Sparse { .. } => {
                    state.nfa_states.push(id);
                }
                nfa::State::Fail => {
                    break;
                }
                nfa::State::Match => {
                    state.is_match = true;
                    if !self.longest_match {
                        break;
                    }
                }
                nfa::State::Union { .. } => {}
            }
        }
        state
    }

    /// Create a new sparse set with enough capacity to hold all NFA states.
    fn new_sparse_set(&self) -> SparseSet {
        SparseSet::new(self.nfa.len())
    }
}

impl State {
    /// Create a new empty dead state.
    fn dead() -> State {
        State { nfa_states: vec![], is_match: false }
    }
}