regex_lite/

nfa.rs

use core::{cell::RefCell, mem::size_of};

use alloc::{string::String, sync::Arc, vec, vec::Vec};

use crate::{
    error::Error,
    hir::{self, Hir, HirKind},
    int::U32,
};

pub(crate) type StateID = u32;

#[derive(Clone, Copy, Debug)]
pub(crate) struct Config {
    pub(crate) size_limit: Option<usize>,
}

impl Default for Config {
    fn default() -> Config {
        Config { size_limit: Some(10 * (1 << 20)) }
    }
}

#[derive(Clone)]
pub(crate) struct NFA {
    /// The pattern string this NFA was generated from.
    ///
    /// We put it here for lack of a better place to put it. ¯\_(ツ)_/¯
    pattern: String,
    /// The states that make up this NFA.
    states: Vec<State>,
    /// The ID of the start state.
    start: StateID,
    /// Whether this NFA can only match at the beginning of a haystack.
    is_start_anchored: bool,
    /// Whether this NFA can match the empty string.
    is_match_empty: bool,
    /// If every match has the same number of matching capture groups, then
    /// this corresponds to the number of groups.
    static_explicit_captures_len: Option<usize>,
    /// A map from capture group name to its corresponding index.
    cap_name_to_index: CaptureNameMap,
    /// A map from capture group index to the corresponding name, if one
    /// exists.
    cap_index_to_name: Vec<Option<Arc<str>>>,
    /// Heap memory used indirectly by NFA states and other things (like the
    /// various capturing group representations above). Since each state
    /// might use a different amount of heap, we need to keep track of this
    /// incrementally.
    memory_extra: usize,
}

impl NFA {
    /// Creates a new NFA from the given configuration and HIR.
    pub(crate) fn new(
        config: Config,
        pattern: String,
        hir: &Hir,
    ) -> Result<NFA, Error> {
        Compiler::new(config, pattern).compile(hir)
    }

    /// Returns the pattern string used to construct this NFA.
    pub(crate) fn pattern(&self) -> &str {
        &self.pattern
    }

    /// Returns the state corresponding to the given ID.
    ///
    /// # Panics
    ///
    /// If the ID does not refer to a valid state, then this panics.
    pub(crate) fn state(&self, id: StateID) -> &State {
        &self.states[id.as_usize()]
    }

    /// Returns the total number of states in this NFA.
    pub(crate) fn len(&self) -> usize {
        self.states.len()
    }

    /// Returns the ID of the starting state for this NFA.
    pub(crate) fn start(&self) -> StateID {
        self.start
    }

    /// Returns the capture group index for the corresponding named group.
    /// If no such group with the given name exists, then `None` is returned.
    pub(crate) fn to_index(&self, name: &str) -> Option<usize> {
        self.cap_name_to_index.get(name).cloned().map(|i| i.as_usize())
    }

    /*
    /// Returns the capture group name for the corresponding index.
    /// If no such group with the given index, then `None` is returned.
    pub(crate) fn to_name(&self, index: usize) -> Option<&str> {
        self.cap_index_to_name.get(index)?.as_deref()
    }
    */

    /// Returns an iterator over all of the capture groups, along with their
    /// names if they exist, in this NFA.
    pub(crate) fn capture_names(&self) -> CaptureNames<'_> {
        CaptureNames { it: self.cap_index_to_name.iter() }
    }

    /// Returns the total number of capture groups, including the first and
    /// implicit group, in this NFA.
    pub(crate) fn group_len(&self) -> usize {
        self.cap_index_to_name.len()
    }

    /// Returns true if and only if this NFA can only match at the beginning of
    /// a haystack.
    pub(crate) fn is_start_anchored(&self) -> bool {
        self.is_start_anchored
    }

    /// If the pattern always reports the same number of matching capture groups
    /// for every match, then this returns the number of those groups. This
    /// doesn't include the implicit group found in every pattern.
    pub(crate) fn static_explicit_captures_len(&self) -> Option<usize> {
        self.static_explicit_captures_len
    }

    /// Returns the heap memory usage, in bytes, used by this NFA.
    fn memory_usage(&self) -> usize {
        (self.states.len() * size_of::<State>())
            + (self.cap_index_to_name.len() * size_of::<Option<Arc<str>>>())
            + self.memory_extra
    }
}

impl core::fmt::Debug for NFA {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        writeln!(f, "NFA(")?;
        writeln!(f, "pattern: {}", self.pattern)?;
        for (sid, state) in self.states.iter().enumerate() {
            writeln!(f, "{:07?}: {:?}", sid, state)?;
        }
        writeln!(f, ")")?;
        Ok(())
    }
}

/// An iterator over all capture groups in an NFA.
///
/// If a particular group has a name, then it is yielded. Otherwise, `None`
/// is yielded.
#[derive(Clone, Debug)]
pub(crate) struct CaptureNames<'a> {
    it: core::slice::Iter<'a, Option<Arc<str>>>,
}

impl<'a> Iterator for CaptureNames<'a> {
    type Item = Option<&'a str>;

    fn next(&mut self) -> Option<Option<&'a str>> {
        self.it.next().map(|n| n.as_deref())
    }
}

#[derive(Clone, Eq, PartialEq)]
pub(crate) enum State {
    Char { target: StateID, ch: char },
    Ranges { target: StateID, ranges: Vec<(char, char)> },
    Splits { targets: Vec<StateID>, reverse: bool },
    Goto { target: StateID, look: Option<hir::Look> },
    Capture { target: StateID, slot: u32 },
    Fail,
    Match,
}

impl State {
    /// Returns the heap memory usage of this NFA state in bytes.
    fn memory_usage(&self) -> usize {
        match *self {
            State::Char { .. }
            | State::Goto { .. }
            | State::Capture { .. }
            | State::Fail { .. }
            | State::Match => 0,
            State::Splits { ref targets, .. } => {
                targets.len() * size_of::<StateID>()
            }
            State::Ranges { ref ranges, .. } => {
                ranges.len() * size_of::<(char, char)>()
            }
        }
    }

    /// Returns an iterator over the given split targets. The order of the
    /// iterator yields elements in reverse when `reverse` is true.
    pub(crate) fn iter_splits<'a>(
        splits: &'a [StateID],
        reverse: bool,
    ) -> impl Iterator<Item = StateID> + 'a {
        let mut it = splits.iter();
        core::iter::from_fn(move || {
            if reverse { it.next_back() } else { it.next() }.copied()
        })
    }
}

impl core::fmt::Debug for State {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        match *self {
            State::Char { target, ch } => {
                write!(f, "{:?} => {:?}", ch, target)
            }
            State::Ranges { target, ref ranges } => {
                for (i, &(start, end)) in ranges.iter().enumerate() {
                    if i > 0 {
                        write!(f, ", ")?;
                    }
                    write!(f, "{:?}-{:?} => {:?}", start, end, target)?;
                }
                Ok(())
            }
            State::Splits { ref targets, reverse } => {
                write!(f, "splits(")?;
                for (i, sid) in
                    State::iter_splits(targets, reverse).enumerate()
                {
                    if i > 0 {
                        write!(f, ", ")?;
                    }
                    write!(f, "{:?}", sid)?;
                }
                write!(f, ")")
            }
            State::Goto { target, look: None } => {
                write!(f, "goto({:?})", target)
            }
            State::Goto { target, look: Some(look) } => {
                write!(f, "{:?} => {:?}", look, target)
            }
            State::Capture { target, slot } => {
                write!(f, "capture(slot={:?}) => {:?}", slot, target,)
            }
            State::Fail => write!(f, "FAIL"),
            State::Match => {
                write!(f, "MATCH")
            }
        }
    }
}

/// A map from capture group name to its corresponding capture group index.
///
/// We define a type alias here so that we can transparently use a `HashMap`
/// whenever it's available. We do so presumably because it's faster, although
/// there are no benchmarks verifying this.
#[cfg(feature = "std")]
type CaptureNameMap = std::collections::HashMap<Arc<str>, u32>;
#[cfg(not(feature = "std"))]
type CaptureNameMap = alloc::collections::BTreeMap<Arc<str>, u32>;

#[derive(Debug)]
struct Compiler {
    config: Config,
    nfa: RefCell<NFA>,
}

impl Compiler {
    fn new(config: Config, pattern: String) -> Compiler {
        let nfa = RefCell::new(NFA {
            pattern,
            states: vec![],
            start: 0,
            is_start_anchored: false,
            is_match_empty: false,
            static_explicit_captures_len: None,
            cap_name_to_index: CaptureNameMap::default(),
            cap_index_to_name: vec![],
            memory_extra: 0,
        });
        Compiler { config, nfa }
    }

    fn compile(self, hir: &Hir) -> Result<NFA, Error> {
        self.nfa.borrow_mut().is_start_anchored = hir.is_start_anchored();
        self.nfa.borrow_mut().is_match_empty = hir.is_match_empty();
        self.nfa.borrow_mut().static_explicit_captures_len =
            hir.static_explicit_captures_len();
        let compiled = self.c_capture(0, None, hir)?;
        let mat = self.add(State::Match)?;
        self.patch(compiled.end, mat)?;
        self.nfa.borrow_mut().start = compiled.start;
        Ok(self.nfa.into_inner())
    }

    fn c(&self, hir: &Hir) -> Result<ThompsonRef, Error> {
        match *hir.kind() {
            HirKind::Empty => self.c_empty(),
            HirKind::Char(ch) => self.c_char(ch),
            HirKind::Class(ref class) => self.c_class(class),
            HirKind::Look(ref look) => self.c_look(look),
            HirKind::Repetition(ref rep) => self.c_repetition(rep),
            HirKind::Capture(ref cap) => {
                self.c_capture(cap.index, cap.name.as_deref(), &cap.sub)
            }
            HirKind::Concat(ref subs) => {
                self.c_concat(subs.iter().map(|s| self.c(s)))
            }
            HirKind::Alternation(ref subs) => {
                self.c_alternation(subs.iter().map(|s| self.c(s)))
            }
        }
    }

    /// Compile a "fail" state that can never be transitioned out of.
    fn c_fail(&self) -> Result<ThompsonRef, Error> {
        let id = self.add(State::Fail)?;
        Ok(ThompsonRef { start: id, end: id })
    }

    /// Compile an "empty" state with one unconditional epsilon transition.
    ///
    /// Both the `start` and `end` locations point to the state created.
    /// Callers will likely want to keep the `start`, but patch the `end` to
    /// point to some other state.
    fn c_empty(&self) -> Result<ThompsonRef, Error> {
        let id = self.add_empty()?;
        Ok(ThompsonRef { start: id, end: id })
    }

    /// Compile the given literal char to an NFA.
    fn c_char(&self, ch: char) -> Result<ThompsonRef, Error> {
        let id = self.add(State::Char { target: 0, ch })?;
        Ok(ThompsonRef { start: id, end: id })
    }

    /// Compile the given character class into an NFA.
    ///
    /// If the class is empty, then this compiles to a `Fail` state.
    fn c_class(&self, class: &hir::Class) -> Result<ThompsonRef, Error> {
        let id = if class.ranges.is_empty() {
            // Technically using an explicit fail state probably isn't
            // necessary. Because if you try to match against an empty Ranges,
            // then it should turn up with nothing regardless of input, and
            // thus "acts" like a Fail state. But it's better to be more
            // explicit, and there's no real cost to doing so.
            self.add(State::Fail)
        } else {
            let ranges =
                class.ranges.iter().map(|r| (r.start, r.end)).collect();
            self.add(State::Ranges { target: 0, ranges })
        }?;
        Ok(ThompsonRef { start: id, end: id })
    }

    /// Compile the given HIR look-around assertion to an NFA look-around
    /// assertion.
    fn c_look(&self, look: &hir::Look) -> Result<ThompsonRef, Error> {
        let id = self.add(State::Goto { target: 0, look: Some(*look) })?;
        Ok(ThompsonRef { start: id, end: id })
    }

    /// Compile the given repetition expression. This handles all types of
    /// repetitions and greediness.
    fn c_repetition(
        &self,
        rep: &hir::Repetition,
    ) -> Result<ThompsonRef, Error> {
        match (rep.min, rep.max) {
            (0, Some(1)) => self.c_zero_or_one(&rep.sub, rep.greedy),
            (min, None) => self.c_at_least(&rep.sub, rep.greedy, min),
            (min, Some(max)) if min == max => self.c_exactly(&rep.sub, min),
            (min, Some(max)) => self.c_bounded(&rep.sub, rep.greedy, min, max),
        }
    }

    /// Compile the given expression such that it matches at least `min` times,
    /// but no more than `max` times.
    ///
    /// When `greedy` is true, then the preference is for the expression to
    /// match as much as possible. Otherwise, it will match as little as
    /// possible.
    fn c_bounded(
        &self,
        hir: &Hir,
        greedy: bool,
        min: u32,
        max: u32,
    ) -> Result<ThompsonRef, Error> {
        let prefix = self.c_exactly(hir, min)?;
        if min == max {
            return Ok(prefix);
        }

        // It is tempting here to compile the rest here as a concatenation
        // of zero-or-one matches. i.e., for `a{2,5}`, compile it as if it
        // were `aaa?a?a?`. The problem here is that it leads to this program:
        //
        //     >000000: 61 => 01
        //      000001: 61 => 02
        //      000002: union(03, 04)
        //      000003: 61 => 04
        //      000004: union(05, 06)
        //      000005: 61 => 06
        //      000006: union(07, 08)
        //      000007: 61 => 08
        //      000008: MATCH
        //
        // And effectively, once you hit state 2, the epsilon closure will
        // include states 3, 5, 6, 7 and 8, which is quite a bit. It is better
        // to instead compile it like so:
        //
        //     >000000: 61 => 01
        //      000001: 61 => 02
        //      000002: union(03, 08)
        //      000003: 61 => 04
        //      000004: union(05, 08)
        //      000005: 61 => 06
        //      000006: union(07, 08)
        //      000007: 61 => 08
        //      000008: MATCH
        //
        // So that the epsilon closure of state 2 is now just 3 and 8.
        let empty = self.add_empty()?;
        let mut prev_end = prefix.end;
        for _ in min..max {
            let splits =
                self.add(State::Splits { targets: vec![], reverse: !greedy })?;
            let compiled = self.c(hir)?;
            self.patch(prev_end, splits)?;
            self.patch(splits, compiled.start)?;
            self.patch(splits, empty)?;
            prev_end = compiled.end;
        }
        self.patch(prev_end, empty)?;
        Ok(ThompsonRef { start: prefix.start, end: empty })
    }

    /// Compile the given expression such that it may be matched `n` or more
    /// times, where `n` can be any integer. (Although a particularly large
    /// integer is likely to run afoul of any configured size limits.)
    ///
    /// When `greedy` is true, then the preference is for the expression to
    /// match as much as possible. Otherwise, it will match as little as
    /// possible.
    fn c_at_least(
        &self,
        hir: &Hir,
        greedy: bool,
        n: u32,
    ) -> Result<ThompsonRef, Error> {
        if n == 0 {
            // When the expression cannot match the empty string, then we
            // can get away with something much simpler: just one 'alt'
            // instruction that optionally repeats itself. But if the expr
            // can match the empty string... see below.
            if !hir.is_match_empty() {
                let splits = self.add(State::Splits {
                    targets: vec![],
                    reverse: !greedy,
                })?;
                let compiled = self.c(hir)?;
                self.patch(splits, compiled.start)?;
                self.patch(compiled.end, splits)?;
                return Ok(ThompsonRef { start: splits, end: splits });
            }

            // What's going on here? Shouldn't x* be simpler than this? It
            // turns out that when implementing leftmost-first (Perl-like)
            // match semantics, x* results in an incorrect preference order
            // when computing the transitive closure of states if and only if
            // 'x' can match the empty string. So instead, we compile x* as
            // (x+)?, which preserves the correct preference order.
            //
            // See: https://github.com/rust-lang/regex/issues/779
            let compiled = self.c(hir)?;
            let plus =
                self.add(State::Splits { targets: vec![], reverse: !greedy })?;
            self.patch(compiled.end, plus)?;
            self.patch(plus, compiled.start)?;

            let question =
                self.add(State::Splits { targets: vec![], reverse: !greedy })?;
            let empty = self.add_empty()?;
            self.patch(question, compiled.start)?;
            self.patch(question, empty)?;
            self.patch(plus, empty)?;
            Ok(ThompsonRef { start: question, end: empty })
        } else if n == 1 {
            let compiled = self.c(hir)?;
            let splits =
                self.add(State::Splits { targets: vec![], reverse: !greedy })?;
            self.patch(compiled.end, splits)?;
            self.patch(splits, compiled.start)?;
            Ok(ThompsonRef { start: compiled.start, end: splits })
        } else {
            let prefix = self.c_exactly(hir, n - 1)?;
            let last = self.c(hir)?;
            let splits =
                self.add(State::Splits { targets: vec![], reverse: !greedy })?;
            self.patch(prefix.end, last.start)?;
            self.patch(last.end, splits)?;
            self.patch(splits, last.start)?;
            Ok(ThompsonRef { start: prefix.start, end: splits })
        }
    }

    /// Compile the given expression such that it may be matched zero or one
    /// times.
    ///
    /// When `greedy` is true, then the preference is for the expression to
    /// match as much as possible. Otherwise, it will match as little as
    /// possible.
    fn c_zero_or_one(
        &self,
        hir: &Hir,
        greedy: bool,
    ) -> Result<ThompsonRef, Error> {
        let splits =
            self.add(State::Splits { targets: vec![], reverse: !greedy })?;
        let compiled = self.c(hir)?;
        let empty = self.add_empty()?;
        self.patch(splits, compiled.start)?;
        self.patch(splits, empty)?;
        self.patch(compiled.end, empty)?;
        Ok(ThompsonRef { start: splits, end: empty })
    }

    /// Compile the given HIR expression exactly `n` times.
    fn c_exactly(&self, hir: &Hir, n: u32) -> Result<ThompsonRef, Error> {
        self.c_concat((0..n).map(|_| self.c(hir)))
    }

    /// Compile the given expression and insert capturing states at the
    /// beginning and end of it. The slot for the capture states is computed
    /// from the index.
    fn c_capture(
        &self,
        index: u32,
        name: Option<&str>,
        hir: &Hir,
    ) -> Result<ThompsonRef, Error> {
        // For discontiguous indices, push placeholders for earlier capture
        // groups that weren't explicitly added. This can happen, for example,
        // with patterns like '(a){0}(a)' where '(a){0}' is completely removed
        // from the pattern.
        let existing_groups_len = self.nfa.borrow().cap_index_to_name.len();
        for _ in 0..(index.as_usize().saturating_sub(existing_groups_len)) {
            self.nfa.borrow_mut().cap_index_to_name.push(None);
        }
        if index.as_usize() >= existing_groups_len {
            if let Some(name) = name {
                let name = Arc::from(name);
                let mut nfa = self.nfa.borrow_mut();
                nfa.cap_name_to_index.insert(Arc::clone(&name), index);
                nfa.cap_index_to_name.push(Some(Arc::clone(&name)));
                // This is an approximation.
                nfa.memory_extra += name.len() + size_of::<u32>();
            } else {
                self.nfa.borrow_mut().cap_index_to_name.push(None);
            }
        }

        let Some(slot) = index.checked_mul(2) else {
            return Err(Error::new("capture group slots exhausted"));
        };
        let start = self.add(State::Capture { target: 0, slot })?;
        let inner = self.c(hir)?;
        let Some(slot) = slot.checked_add(1) else {
            return Err(Error::new("capture group slots exhausted"));
        };
        let end = self.add(State::Capture { target: 0, slot })?;
        self.patch(start, inner.start)?;
        self.patch(inner.end, end)?;

        Ok(ThompsonRef { start, end })
    }

    /// Compile a concatenation of the sub-expressions yielded by the given
    /// iterator. If the iterator yields no elements, then this compiles down
    /// to an "empty" state that always matches.
    fn c_concat<I>(&self, mut it: I) -> Result<ThompsonRef, Error>
    where
        I: Iterator<Item = Result<ThompsonRef, Error>>,
    {
        let ThompsonRef { start, mut end } = match it.next() {
            Some(result) => result?,
            None => return self.c_empty(),
        };
        for result in it {
            let compiled = result?;
            self.patch(end, compiled.start)?;
            end = compiled.end;
        }
        Ok(ThompsonRef { start, end })
    }

    /// Compile an alternation, where each element yielded by the given
    /// iterator represents an item in the alternation. If the iterator yields
    /// no elements, then this compiles down to a "fail" state.
    ///
    /// In an alternation, expressions appearing earlier are "preferred" at
    /// match time over expressions appearing later. (This is currently always
    /// true, as this crate only supports leftmost-first semantics.)
    fn c_alternation<I>(&self, mut it: I) -> Result<ThompsonRef, Error>
    where
        I: Iterator<Item = Result<ThompsonRef, Error>>,
    {
        let first = match it.next() {
            None => return self.c_fail(),
            Some(result) => result?,
        };
        let second = match it.next() {
            None => return Ok(first),
            Some(result) => result?,
        };

        let splits =
            self.add(State::Splits { targets: vec![], reverse: false })?;
        let end = self.add_empty()?;
        self.patch(splits, first.start)?;
        self.patch(first.end, end)?;
        self.patch(splits, second.start)?;
        self.patch(second.end, end)?;
        for result in it {
            let compiled = result?;
            self.patch(splits, compiled.start)?;
            self.patch(compiled.end, end)?;
        }
        Ok(ThompsonRef { start: splits, end })
    }

    /// A convenience routine for adding an empty state, also known as an
    /// unconditional epsilon transition. These are quite useful for making
    /// NFA construction simpler.
    ///
    /// (In the regex crate, we do a second pass to remove these, but don't
    /// bother with that here.)
    fn add_empty(&self) -> Result<StateID, Error> {
        self.add(State::Goto { target: 0, look: None })
    }

    /// The common implementation of "add a state." It handles the common
    /// error cases of state ID exhausting (by owning state ID allocation) and
    /// whether the size limit has been exceeded.
    fn add(&self, state: State) -> Result<StateID, Error> {
        let id = u32::try_from(self.nfa.borrow().states.len())
            .map_err(|_| Error::new("exhausted state IDs, too many states"))?;
        self.nfa.borrow_mut().memory_extra += state.memory_usage();
        self.nfa.borrow_mut().states.push(state);
        self.check_size_limit()?;
        Ok(id)
    }

    /// Add a transition from one state to another.
    ///
    /// This routine is called "patch" since it is very common to add the
    /// states you want, typically with "dummy" state ID transitions, and then
    /// "patch" in the real state IDs later. This is because you don't always
    /// know all of the necessary state IDs to add because they might not
    /// exist yet.
    ///
    /// # Errors
    ///
    /// This may error if patching leads to an increase in heap usage beyond
    /// the configured size limit. Heap usage only grows when patching adds a
    /// new transition (as in the case of a "splits" state).
    fn patch(&self, from: StateID, to: StateID) -> Result<(), Error> {
        let mut new_memory_extra = self.nfa.borrow().memory_extra;
        match self.nfa.borrow_mut().states[from.as_usize()] {
            State::Char { ref mut target, .. } => {
                *target = to;
            }
            State::Ranges { ref mut target, .. } => {
                *target = to;
            }
            State::Splits { ref mut targets, .. } => {
                targets.push(to);
                new_memory_extra += size_of::<StateID>();
            }
            State::Goto { ref mut target, .. } => {
                *target = to;
            }
            State::Capture { ref mut target, .. } => {
                *target = to;
            }
            State::Fail | State::Match => {}
        }
        if new_memory_extra != self.nfa.borrow().memory_extra {
            self.nfa.borrow_mut().memory_extra = new_memory_extra;
            self.check_size_limit()?;
        }
        Ok(())
    }

    /// Checks that the current heap memory usage of the NFA being compiled
    /// doesn't exceed the configured size limit. If it does, an error is
    /// returned.
    fn check_size_limit(&self) -> Result<(), Error> {
        if let Some(limit) = self.config.size_limit {
            if self.nfa.borrow().memory_usage() > limit {
                return Err(Error::new("compiled regex exceeded size limit"));
            }
        }
        Ok(())
    }
}

/// A value that represents the result of compiling a sub-expression of a
/// regex's HIR. Specifically, this represents a sub-graph of the NFA that
/// has an initial state at `start` and a final state at `end`.
#[derive(Clone, Copy, Debug)]
struct ThompsonRef {
    start: StateID,
    end: StateID,
}