Initial import of regex-automata-0.1.9.
Bug: 155309706
Change-Id: I20031167cbe49d12754936285a0781eb7a3b8bfd
diff --git a/src/nfa/compiler.rs b/src/nfa/compiler.rs
new file mode 100644
index 0000000..d9b3945
--- /dev/null
+++ b/src/nfa/compiler.rs
@@ -0,0 +1,1193 @@
+// This module provides an NFA compiler using Thompson's construction
+// algorithm. The compiler takes a regex-syntax::Hir as input and emits an NFA
+// graph as output. The NFA graph is structured in a way that permits it to be
+// executed by a virtual machine and also used to efficiently build a DFA.
+//
+// The compiler deals with a slightly expanded set of NFA states that notably
+// includes an empty node that has exactly one epsilon transition to the next
+// state. In other words, it's a "goto" instruction if one views Thompson's NFA
+// as a set of bytecode instructions. These goto instructions are removed in
+// a subsequent phase before returning the NFA to the caller. The purpose of
+// these empty nodes is that they make the construction algorithm substantially
+// simpler to implement. We remove them before returning to the caller because
+// they can represent substantial overhead when traversing the NFA graph
+// (either while searching using the NFA directly or while building a DFA).
+//
+// In the future, it would be nice to provide a Glushkov compiler as well,
+// as it would work well as a bit-parallel NFA for smaller regexes. But
+// the Thompson construction is one I'm more familiar with and seems more
+// straight-forward to deal with when it comes to large Unicode character
+// classes.
+//
+// Internally, the compiler uses interior mutability to improve composition
+// in the face of the borrow checker. In particular, we'd really like to be
+// able to write things like this:
+//
+// self.c_concat(exprs.iter().map(|e| self.c(e)))
+//
+// Which elegantly uses iterators to build up a sequence of compiled regex
+// sub-expressions and then hands it off to the concatenating compiler
+// routine. Without interior mutability, the borrow checker won't let us
+// borrow `self` mutably both inside and outside the closure at the same
+// time.
+
+use std::cell::RefCell;
+use std::mem;
+
+use regex_syntax::hir::{self, Hir, HirKind};
+use regex_syntax::utf8::{Utf8Range, Utf8Sequences};
+
+use classes::ByteClassSet;
+use error::{Error, Result};
+use nfa::map::{Utf8BoundedMap, Utf8SuffixKey, Utf8SuffixMap};
+use nfa::range_trie::RangeTrie;
+use nfa::{State, StateID, Transition, NFA};
+
+/// Config knobs for the NFA compiler. See the builder's methods for more
+/// docs on each one.
+#[derive(Clone, Copy, Debug)]
+struct Config {
+ anchored: bool,
+ allow_invalid_utf8: bool,
+ reverse: bool,
+ shrink: bool,
+}
+
+impl Default for Config {
+ fn default() -> Config {
+ Config {
+ anchored: false,
+ allow_invalid_utf8: false,
+ reverse: false,
+ shrink: true,
+ }
+ }
+}
+
+/// A builder for compiling an NFA.
+#[derive(Clone, Debug)]
+pub struct Builder {
+ config: Config,
+}
+
+impl Builder {
+ /// Create a new NFA builder with its default configuration.
+ pub fn new() -> Builder {
+ Builder { config: Config::default() }
+ }
+
+ /// Compile the given high level intermediate representation of a regular
+ /// expression into an NFA.
+ ///
+ /// If there was a problem building the NFA, then an error is returned.
+ /// For example, if the regex uses unsupported features (such as zero-width
+ /// assertions), then an error is returned.
+ pub fn build(&self, expr: &Hir) -> Result<NFA> {
+ let mut nfa = NFA::always_match();
+ self.build_with(&mut Compiler::new(), &mut nfa, expr)?;
+ Ok(nfa)
+ }
+
+ /// Compile the given high level intermediate representation of a regular
+ /// expression into the NFA given using the given compiler. Callers may
+ /// prefer this over `build` if they would like to reuse allocations while
+ /// compiling many regular expressions.
+ ///
+ /// On success, the given NFA is completely overwritten with the NFA
+ /// produced by the compiler.
+ ///
+ /// If there was a problem building the NFA, then an error is returned. For
+ /// example, if the regex uses unsupported features (such as zero-width
+ /// assertions), then an error is returned. When an error is returned,
+ /// the contents of `nfa` are unspecified and should not be relied upon.
+ /// However, it can still be reused in subsequent calls to this method.
+ pub fn build_with(
+ &self,
+ compiler: &mut Compiler,
+ nfa: &mut NFA,
+ expr: &Hir,
+ ) -> Result<()> {
+ compiler.clear();
+ compiler.configure(self.config);
+ compiler.compile(nfa, expr)
+ }
+
+ /// Set whether matching must be anchored at the beginning of the input.
+ ///
+ /// When enabled, a match must begin at the start of the input. When
+ /// disabled, the NFA will act as if the pattern started with a `.*?`,
+ /// which enables a match to appear anywhere.
+ ///
+ /// By default this is disabled.
+ pub fn anchored(&mut self, yes: bool) -> &mut Builder {
+ self.config.anchored = yes;
+ self
+ }
+
+ /// When enabled, the builder will permit the construction of an NFA that
+ /// may match invalid UTF-8.
+ ///
+ /// When disabled (the default), the builder is guaranteed to produce a
+ /// regex that will only ever match valid UTF-8 (otherwise, the builder
+ /// will return an error).
+ pub fn allow_invalid_utf8(&mut self, yes: bool) -> &mut Builder {
+ self.config.allow_invalid_utf8 = yes;
+ self
+ }
+
+ /// Reverse the NFA.
+ ///
+ /// A NFA reversal is performed by reversing all of the concatenated
+ /// sub-expressions in the original pattern, recursively. The resulting
+ /// NFA can be used to match the pattern starting from the end of a string
+ /// instead of the beginning of a string.
+ ///
+ /// Reversing the NFA is useful for building a reverse DFA, which is most
+ /// useful for finding the start of a match.
+ pub fn reverse(&mut self, yes: bool) -> &mut Builder {
+ self.config.reverse = yes;
+ self
+ }
+
+ /// Apply best effort heuristics to shrink the NFA at the expense of more
+ /// time/memory.
+ ///
+ /// This is enabled by default. Generally speaking, if one is using an NFA
+ /// to compile DFA, then the extra time used to shrink the NFA will be
+ /// more than made up for during DFA construction (potentially by a lot).
+ /// In other words, enabling this can substantially decrease the overall
+ /// amount of time it takes to build a DFA.
+ ///
+ /// The only reason to disable this if you want to compile an NFA and start
+ /// using it as quickly as possible without needing to build a DFA.
+ pub fn shrink(&mut self, yes: bool) -> &mut Builder {
+ self.config.shrink = yes;
+ self
+ }
+}
+
+/// A compiler that converts a regex abstract syntax to an NFA via Thompson's
+/// construction. Namely, this compiler permits epsilon transitions between
+/// states.
+///
+/// Users of this crate cannot use a compiler directly. Instead, all one can
+/// do is create one and use it via the
+/// [`Builder::build_with`](struct.Builder.html#method.build_with)
+/// method. This permits callers to reuse compilers in order to amortize
+/// allocations.
+#[derive(Clone, Debug)]
+pub struct Compiler {
+ /// The set of compiled NFA states. Once a state is compiled, it is
+ /// assigned a state ID equivalent to its index in this list. Subsequent
+ /// compilation can modify previous states by adding new transitions.
+ states: RefCell<Vec<CState>>,
+ /// The configuration from the builder.
+ config: Config,
+ /// State used for compiling character classes to UTF-8 byte automata.
+ /// State is not retained between character class compilations. This just
+ /// serves to amortize allocation to the extent possible.
+ utf8_state: RefCell<Utf8State>,
+ /// State used for arranging character classes in reverse into a trie.
+ trie_state: RefCell<RangeTrie>,
+ /// State used for caching common suffixes when compiling reverse UTF-8
+ /// automata (for Unicode character classes).
+ utf8_suffix: RefCell<Utf8SuffixMap>,
+ /// A map used to re-map state IDs when translating the compiler's internal
+ /// NFA state representation to the external NFA representation.
+ remap: RefCell<Vec<StateID>>,
+ /// A set of compiler internal state IDs that correspond to states that are
+ /// exclusively epsilon transitions, i.e., goto instructions, combined with
+ /// the state that they point to. This is used to record said states while
+ /// transforming the compiler's internal NFA representation to the external
+ /// form.
+ empties: RefCell<Vec<(StateID, StateID)>>,
+}
+
+/// A compiler intermediate state representation for an NFA that is only used
+/// during compilation. Once compilation is done, `CState`s are converted to
+/// `State`s, which have a much simpler representation.
+#[derive(Clone, Debug, Eq, PartialEq)]
+enum CState {
+ /// An empty state whose only purpose is to forward the automaton to
+ /// another state via en epsilon transition. These are useful during
+ /// compilation but are otherwise removed at the end.
+ Empty { next: StateID },
+ /// A state that only transitions to `next` if the current input byte is
+ /// in the range `[start, end]` (inclusive on both ends).
+ Range { range: Transition },
+ /// A state with possibly many transitions, represented in a sparse
+ /// fashion. Transitions are ordered lexicographically by input range.
+ /// As such, this may only be used when every transition has equal
+ /// priority. (In practice, this is only used for encoding large UTF-8
+ /// automata.)
+ Sparse { ranges: Vec<Transition> },
+ /// An alternation such that there exists an epsilon transition to all
+ /// states in `alternates`, where matches found via earlier transitions
+ /// are preferred over later transitions.
+ Union { alternates: Vec<StateID> },
+ /// An alternation such that there exists an epsilon transition to all
+ /// states in `alternates`, where matches found via later transitions
+ /// are preferred over earlier transitions.
+ ///
+ /// This "reverse" state exists for convenience during compilation that
+ /// permits easy construction of non-greedy combinations of NFA states.
+ /// At the end of compilation, Union and UnionReverse states are merged
+ /// into one Union type of state, where the latter has its epsilon
+ /// transitions reversed to reflect the priority inversion.
+ UnionReverse { alternates: Vec<StateID> },
+ /// A match state. There is exactly one such occurrence of this state in
+ /// an NFA.
+ Match,
+}
+
+/// 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)]
+pub struct ThompsonRef {
+ start: StateID,
+ end: StateID,
+}
+
+impl Compiler {
+ /// Create a new compiler.
+ pub fn new() -> Compiler {
+ Compiler {
+ states: RefCell::new(vec![]),
+ config: Config::default(),
+ utf8_state: RefCell::new(Utf8State::new()),
+ trie_state: RefCell::new(RangeTrie::new()),
+ utf8_suffix: RefCell::new(Utf8SuffixMap::new(1000)),
+ remap: RefCell::new(vec![]),
+ empties: RefCell::new(vec![]),
+ }
+ }
+
+ /// Clear any memory used by this compiler such that it is ready to compile
+ /// a new regex.
+ ///
+ /// It is preferrable to reuse a compiler if possible in order to reuse
+ /// allocations.
+ fn clear(&self) {
+ self.states.borrow_mut().clear();
+ // We don't need to clear anything else since they are cleared on
+ // their own and only when they are used.
+ }
+
+ /// Configure this compiler from the builder's knobs.
+ ///
+ /// The compiler is always reconfigured by the builder before using it to
+ /// build an NFA.
+ fn configure(&mut self, config: Config) {
+ self.config = config;
+ }
+
+ /// Convert the current intermediate NFA to its final compiled form.
+ fn compile(&self, nfa: &mut NFA, expr: &Hir) -> Result<()> {
+ nfa.anchored = self.config.anchored;
+
+ let mut start = self.add_empty();
+ if !nfa.anchored {
+ let compiled = if self.config.allow_invalid_utf8 {
+ self.c_unanchored_prefix_invalid_utf8()?
+ } else {
+ self.c_unanchored_prefix_valid_utf8()?
+ };
+ self.patch(start, compiled.start);
+ start = compiled.end;
+ }
+ let compiled = self.c(&expr)?;
+ let match_id = self.add_match();
+ self.patch(start, compiled.start);
+ self.patch(compiled.end, match_id);
+ self.finish(nfa);
+ Ok(())
+ }
+
+ /// Finishes the compilation process and populates the provide NFA with
+ /// the final graph.
+ fn finish(&self, nfa: &mut NFA) {
+ let mut bstates = self.states.borrow_mut();
+ let mut remap = self.remap.borrow_mut();
+ remap.resize(bstates.len(), 0);
+ let mut empties = self.empties.borrow_mut();
+ empties.clear();
+
+ // We don't reuse allocations here becuase this is what we're
+ // returning.
+ nfa.states.clear();
+ let mut byteset = ByteClassSet::new();
+
+ // The idea here is to convert our intermediate states to their final
+ // form. The only real complexity here is the process of converting
+ // transitions, which are expressed in terms of state IDs. The new
+ // set of states will be smaller because of partial epsilon removal,
+ // so the state IDs will not be the same.
+ for (id, bstate) in bstates.iter_mut().enumerate() {
+ match *bstate {
+ CState::Empty { next } => {
+ // Since we're removing empty states, we need to handle
+ // them later since we don't yet know which new state this
+ // empty state will be mapped to.
+ empties.push((id, next));
+ }
+ CState::Range { ref range } => {
+ remap[id] = nfa.states.len();
+ byteset.set_range(range.start, range.end);
+ nfa.states.push(State::Range { range: range.clone() });
+ }
+ CState::Sparse { ref mut ranges } => {
+ remap[id] = nfa.states.len();
+
+ let ranges = mem::replace(ranges, vec![]);
+ for r in &ranges {
+ byteset.set_range(r.start, r.end);
+ }
+ nfa.states.push(State::Sparse {
+ ranges: ranges.into_boxed_slice(),
+ });
+ }
+ CState::Union { ref mut alternates } => {
+ remap[id] = nfa.states.len();
+
+ let alternates = mem::replace(alternates, vec![]);
+ nfa.states.push(State::Union {
+ alternates: alternates.into_boxed_slice(),
+ });
+ }
+ CState::UnionReverse { ref mut alternates } => {
+ remap[id] = nfa.states.len();
+
+ let mut alternates = mem::replace(alternates, vec![]);
+ alternates.reverse();
+ nfa.states.push(State::Union {
+ alternates: alternates.into_boxed_slice(),
+ });
+ }
+ CState::Match => {
+ remap[id] = nfa.states.len();
+ nfa.states.push(State::Match);
+ }
+ }
+ }
+ for &(empty_id, mut empty_next) in empties.iter() {
+ // empty states can point to other empty states, forming a chain.
+ // So we must follow the chain until the end, which must end at
+ // a non-empty state, and therefore, a state that is correctly
+ // remapped. We are guaranteed to terminate because our compiler
+ // never builds a loop among empty states.
+ while let CState::Empty { next } = bstates[empty_next] {
+ empty_next = next;
+ }
+ remap[empty_id] = remap[empty_next];
+ }
+ for state in &mut nfa.states {
+ state.remap(&remap);
+ }
+ // The compiler always begins the NFA at the first state.
+ nfa.start = remap[0];
+ nfa.byte_classes = byteset.byte_classes();
+ }
+
+ fn c(&self, expr: &Hir) -> Result<ThompsonRef> {
+ match *expr.kind() {
+ HirKind::Empty => {
+ let id = self.add_empty();
+ Ok(ThompsonRef { start: id, end: id })
+ }
+ HirKind::Literal(hir::Literal::Unicode(ch)) => {
+ let mut buf = [0; 4];
+ let it = ch
+ .encode_utf8(&mut buf)
+ .as_bytes()
+ .iter()
+ .map(|&b| Ok(self.c_range(b, b)));
+ self.c_concat(it)
+ }
+ HirKind::Literal(hir::Literal::Byte(b)) => Ok(self.c_range(b, b)),
+ HirKind::Class(hir::Class::Bytes(ref cls)) => {
+ self.c_byte_class(cls)
+ }
+ HirKind::Class(hir::Class::Unicode(ref cls)) => {
+ self.c_unicode_class(cls)
+ }
+ HirKind::Repetition(ref rep) => self.c_repetition(rep),
+ HirKind::Group(ref group) => self.c(&*group.hir),
+ HirKind::Concat(ref exprs) => {
+ self.c_concat(exprs.iter().map(|e| self.c(e)))
+ }
+ HirKind::Alternation(ref exprs) => {
+ self.c_alternation(exprs.iter().map(|e| self.c(e)))
+ }
+ HirKind::Anchor(_) => Err(Error::unsupported_anchor()),
+ HirKind::WordBoundary(_) => Err(Error::unsupported_word()),
+ }
+ }
+
+ fn c_concat<I>(&self, mut it: I) -> Result<ThompsonRef>
+ where
+ I: DoubleEndedIterator<Item = Result<ThompsonRef>>,
+ {
+ let first =
+ if self.config.reverse { it.next_back() } else { it.next() };
+ let ThompsonRef { start, mut end } = match first {
+ Some(result) => result?,
+ None => return Ok(self.c_empty()),
+ };
+ loop {
+ let next =
+ if self.config.reverse { it.next_back() } else { it.next() };
+ let compiled = match next {
+ Some(result) => result?,
+ None => break,
+ };
+ self.patch(end, compiled.start);
+ end = compiled.end;
+ }
+ Ok(ThompsonRef { start, end })
+ }
+
+ fn c_alternation<I>(&self, mut it: I) -> Result<ThompsonRef>
+ where
+ I: Iterator<Item = Result<ThompsonRef>>,
+ {
+ let first = it.next().expect("alternations must be non-empty")?;
+ let second = match it.next() {
+ None => return Ok(first),
+ Some(result) => result?,
+ };
+
+ let union = self.add_union();
+ let end = self.add_empty();
+ self.patch(union, first.start);
+ self.patch(first.end, end);
+ self.patch(union, second.start);
+ self.patch(second.end, end);
+ for result in it {
+ let compiled = result?;
+ self.patch(union, compiled.start);
+ self.patch(compiled.end, end);
+ }
+ Ok(ThompsonRef { start: union, end })
+ }
+
+ fn c_repetition(&self, rep: &hir::Repetition) -> Result<ThompsonRef> {
+ match rep.kind {
+ hir::RepetitionKind::ZeroOrOne => {
+ self.c_zero_or_one(&rep.hir, rep.greedy)
+ }
+ hir::RepetitionKind::ZeroOrMore => {
+ self.c_at_least(&rep.hir, rep.greedy, 0)
+ }
+ hir::RepetitionKind::OneOrMore => {
+ self.c_at_least(&rep.hir, rep.greedy, 1)
+ }
+ hir::RepetitionKind::Range(ref rng) => match *rng {
+ hir::RepetitionRange::Exactly(count) => {
+ self.c_exactly(&rep.hir, count)
+ }
+ hir::RepetitionRange::AtLeast(m) => {
+ self.c_at_least(&rep.hir, rep.greedy, m)
+ }
+ hir::RepetitionRange::Bounded(min, max) => {
+ self.c_bounded(&rep.hir, rep.greedy, min, max)
+ }
+ },
+ }
+ }
+
+ fn c_bounded(
+ &self,
+ expr: &Hir,
+ greedy: bool,
+ min: u32,
+ max: u32,
+ ) -> Result<ThompsonRef> {
+ let prefix = self.c_exactly(expr, 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: alt(03, 04)
+ // 000003: 61 => 04
+ // 000004: alt(05, 06)
+ // 000005: 61 => 06
+ // 000006: alt(07, 08)
+ // 000007: 61 => 08
+ // 000008: MATCH
+ //
+ // And effectively, once you hit state 2, the epsilon closure will
+ // include states 3, 5, 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: alt(03, 08)
+ // 000003: 61 => 04
+ // 000004: alt(05, 08)
+ // 000005: 61 => 06
+ // 000006: alt(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 union = if greedy {
+ self.add_union()
+ } else {
+ self.add_reverse_union()
+ };
+ let compiled = self.c(expr)?;
+ self.patch(prev_end, union);
+ self.patch(union, compiled.start);
+ self.patch(union, empty);
+ prev_end = compiled.end;
+ }
+ self.patch(prev_end, empty);
+ Ok(ThompsonRef { start: prefix.start, end: empty })
+ }
+
+ fn c_at_least(
+ &self,
+ expr: &Hir,
+ greedy: bool,
+ n: u32,
+ ) -> Result<ThompsonRef> {
+ if n == 0 {
+ let union = if greedy {
+ self.add_union()
+ } else {
+ self.add_reverse_union()
+ };
+ let compiled = self.c(expr)?;
+ self.patch(union, compiled.start);
+ self.patch(compiled.end, union);
+ Ok(ThompsonRef { start: union, end: union })
+ } else if n == 1 {
+ let compiled = self.c(expr)?;
+ let union = if greedy {
+ self.add_union()
+ } else {
+ self.add_reverse_union()
+ };
+ self.patch(compiled.end, union);
+ self.patch(union, compiled.start);
+ Ok(ThompsonRef { start: compiled.start, end: union })
+ } else {
+ let prefix = self.c_exactly(expr, n - 1)?;
+ let last = self.c(expr)?;
+ let union = if greedy {
+ self.add_union()
+ } else {
+ self.add_reverse_union()
+ };
+ self.patch(prefix.end, last.start);
+ self.patch(last.end, union);
+ self.patch(union, last.start);
+ Ok(ThompsonRef { start: prefix.start, end: union })
+ }
+ }
+
+ fn c_zero_or_one(&self, expr: &Hir, greedy: bool) -> Result<ThompsonRef> {
+ let union =
+ if greedy { self.add_union() } else { self.add_reverse_union() };
+ let compiled = self.c(expr)?;
+ let empty = self.add_empty();
+ self.patch(union, compiled.start);
+ self.patch(union, empty);
+ self.patch(compiled.end, empty);
+ Ok(ThompsonRef { start: union, end: empty })
+ }
+
+ fn c_exactly(&self, expr: &Hir, n: u32) -> Result<ThompsonRef> {
+ let it = (0..n).map(|_| self.c(expr));
+ self.c_concat(it)
+ }
+
+ fn c_byte_class(&self, cls: &hir::ClassBytes) -> Result<ThompsonRef> {
+ let end = self.add_empty();
+ let mut trans = Vec::with_capacity(cls.ranges().len());
+ for r in cls.iter() {
+ trans.push(Transition {
+ start: r.start(),
+ end: r.end(),
+ next: end,
+ });
+ }
+ Ok(ThompsonRef { start: self.add_sparse(trans), end })
+ }
+
+ fn c_unicode_class(&self, cls: &hir::ClassUnicode) -> Result<ThompsonRef> {
+ // If all we have are ASCII ranges wrapped in a Unicode package, then
+ // there is zero reason to bring out the big guns. We can fit all ASCII
+ // ranges within a single sparse transition.
+ if cls.is_all_ascii() {
+ let end = self.add_empty();
+ let mut trans = Vec::with_capacity(cls.ranges().len());
+ for r in cls.iter() {
+ assert!(r.start() <= '\x7F');
+ assert!(r.end() <= '\x7F');
+ trans.push(Transition {
+ start: r.start() as u8,
+ end: r.end() as u8,
+ next: end,
+ });
+ }
+ Ok(ThompsonRef { start: self.add_sparse(trans), end })
+ } else if self.config.reverse {
+ if !self.config.shrink {
+ // When we don't want to spend the extra time shrinking, we
+ // compile the UTF-8 automaton in reverse using something like
+ // the "naive" approach, but will attempt to re-use common
+ // suffixes.
+ self.c_unicode_class_reverse_with_suffix(cls)
+ } else {
+ // When we want to shrink our NFA for reverse UTF-8 automata,
+ // we cannot feed UTF-8 sequences directly to the UTF-8
+ // compiler, since the UTF-8 compiler requires all sequences
+ // to be lexicographically sorted. Instead, we organize our
+ // sequences into a range trie, which can then output our
+ // sequences in the correct order. Unfortunately, building the
+ // range trie is fairly expensive (but not nearly as expensive
+ // as building a DFA). Hence the reason why the 'shrink' option
+ // exists, so that this path can be toggled off.
+ let mut trie = self.trie_state.borrow_mut();
+ trie.clear();
+
+ for rng in cls.iter() {
+ for mut seq in Utf8Sequences::new(rng.start(), rng.end()) {
+ seq.reverse();
+ trie.insert(seq.as_slice());
+ }
+ }
+ let mut utf8_state = self.utf8_state.borrow_mut();
+ let mut utf8c = Utf8Compiler::new(self, &mut *utf8_state);
+ trie.iter(|seq| {
+ utf8c.add(&seq);
+ });
+ Ok(utf8c.finish())
+ }
+ } else {
+ // In the forward direction, we always shrink our UTF-8 automata
+ // because we can stream it right into the UTF-8 compiler. There
+ // is almost no downside (in either memory or time) to using this
+ // approach.
+ let mut utf8_state = self.utf8_state.borrow_mut();
+ let mut utf8c = Utf8Compiler::new(self, &mut *utf8_state);
+ for rng in cls.iter() {
+ for seq in Utf8Sequences::new(rng.start(), rng.end()) {
+ utf8c.add(seq.as_slice());
+ }
+ }
+ Ok(utf8c.finish())
+ }
+
+ // For reference, the code below is the "naive" version of compiling a
+ // UTF-8 automaton. It is deliciously simple (and works for both the
+ // forward and reverse cases), but will unfortunately produce very
+ // large NFAs. When compiling a forward automaton, the size difference
+ // can sometimes be an order of magnitude. For example, the '\w' regex
+ // will generate about ~3000 NFA states using the naive approach below,
+ // but only 283 states when using the approach above. This is because
+ // the approach above actually compiles a *minimal* (or near minimal,
+ // because of the bounded hashmap) UTF-8 automaton.
+ //
+ // The code below is kept as a reference point in order to make it
+ // easier to understand the higher level goal here.
+ /*
+ let it = cls
+ .iter()
+ .flat_map(|rng| Utf8Sequences::new(rng.start(), rng.end()))
+ .map(|seq| {
+ let it = seq
+ .as_slice()
+ .iter()
+ .map(|rng| Ok(self.c_range(rng.start, rng.end)));
+ self.c_concat(it)
+ });
+ self.c_alternation(it);
+ */
+ }
+
+ fn c_unicode_class_reverse_with_suffix(
+ &self,
+ cls: &hir::ClassUnicode,
+ ) -> Result<ThompsonRef> {
+ // N.B. It would likely be better to cache common *prefixes* in the
+ // reverse direction, but it's not quite clear how to do that. The
+ // advantage of caching suffixes is that it does give us a win, and
+ // has a very small additional overhead.
+ let mut cache = self.utf8_suffix.borrow_mut();
+ cache.clear();
+
+ let union = self.add_union();
+ let alt_end = self.add_empty();
+ for urng in cls.iter() {
+ for seq in Utf8Sequences::new(urng.start(), urng.end()) {
+ let mut end = alt_end;
+ for brng in seq.as_slice() {
+ let key = Utf8SuffixKey {
+ from: end,
+ start: brng.start,
+ end: brng.end,
+ };
+ let hash = cache.hash(&key);
+ if let Some(id) = cache.get(&key, hash) {
+ end = id;
+ continue;
+ }
+
+ let compiled = self.c_range(brng.start, brng.end);
+ self.patch(compiled.end, end);
+ end = compiled.start;
+ cache.set(key, hash, end);
+ }
+ self.patch(union, end);
+ }
+ }
+ Ok(ThompsonRef { start: union, end: alt_end })
+ }
+
+ fn c_range(&self, start: u8, end: u8) -> ThompsonRef {
+ let id = self.add_range(start, end);
+ ThompsonRef { start: id, end: id }
+ }
+
+ fn c_empty(&self) -> ThompsonRef {
+ let id = self.add_empty();
+ ThompsonRef { start: id, end: id }
+ }
+
+ fn c_unanchored_prefix_valid_utf8(&self) -> Result<ThompsonRef> {
+ self.c(&Hir::repetition(hir::Repetition {
+ kind: hir::RepetitionKind::ZeroOrMore,
+ greedy: false,
+ hir: Box::new(Hir::any(false)),
+ }))
+ }
+
+ fn c_unanchored_prefix_invalid_utf8(&self) -> Result<ThompsonRef> {
+ self.c(&Hir::repetition(hir::Repetition {
+ kind: hir::RepetitionKind::ZeroOrMore,
+ greedy: false,
+ hir: Box::new(Hir::any(true)),
+ }))
+ }
+
+ fn patch(&self, from: StateID, to: StateID) {
+ match self.states.borrow_mut()[from] {
+ CState::Empty { ref mut next } => {
+ *next = to;
+ }
+ CState::Range { ref mut range } => {
+ range.next = to;
+ }
+ CState::Sparse { .. } => {
+ panic!("cannot patch from a sparse NFA state")
+ }
+ CState::Union { ref mut alternates } => {
+ alternates.push(to);
+ }
+ CState::UnionReverse { ref mut alternates } => {
+ alternates.push(to);
+ }
+ CState::Match => {}
+ }
+ }
+
+ fn add_empty(&self) -> StateID {
+ let id = self.states.borrow().len();
+ self.states.borrow_mut().push(CState::Empty { next: 0 });
+ id
+ }
+
+ fn add_range(&self, start: u8, end: u8) -> StateID {
+ let id = self.states.borrow().len();
+ let trans = Transition { start, end, next: 0 };
+ let state = CState::Range { range: trans };
+ self.states.borrow_mut().push(state);
+ id
+ }
+
+ fn add_sparse(&self, ranges: Vec<Transition>) -> StateID {
+ if ranges.len() == 1 {
+ let id = self.states.borrow().len();
+ let state = CState::Range { range: ranges[0] };
+ self.states.borrow_mut().push(state);
+ return id;
+ }
+ let id = self.states.borrow().len();
+ let state = CState::Sparse { ranges };
+ self.states.borrow_mut().push(state);
+ id
+ }
+
+ fn add_union(&self) -> StateID {
+ let id = self.states.borrow().len();
+ let state = CState::Union { alternates: vec![] };
+ self.states.borrow_mut().push(state);
+ id
+ }
+
+ fn add_reverse_union(&self) -> StateID {
+ let id = self.states.borrow().len();
+ let state = CState::UnionReverse { alternates: vec![] };
+ self.states.borrow_mut().push(state);
+ id
+ }
+
+ fn add_match(&self) -> StateID {
+ let id = self.states.borrow().len();
+ self.states.borrow_mut().push(CState::Match);
+ id
+ }
+}
+
+#[derive(Debug)]
+struct Utf8Compiler<'a> {
+ nfac: &'a Compiler,
+ state: &'a mut Utf8State,
+ target: StateID,
+}
+
+#[derive(Clone, Debug)]
+struct Utf8State {
+ compiled: Utf8BoundedMap,
+ uncompiled: Vec<Utf8Node>,
+}
+
+#[derive(Clone, Debug)]
+struct Utf8Node {
+ trans: Vec<Transition>,
+ last: Option<Utf8LastTransition>,
+}
+
+#[derive(Clone, Debug)]
+struct Utf8LastTransition {
+ start: u8,
+ end: u8,
+}
+
+impl Utf8State {
+ fn new() -> Utf8State {
+ Utf8State { compiled: Utf8BoundedMap::new(5000), uncompiled: vec![] }
+ }
+
+ fn clear(&mut self) {
+ self.compiled.clear();
+ self.uncompiled.clear();
+ }
+}
+
+impl<'a> Utf8Compiler<'a> {
+ fn new(nfac: &'a Compiler, state: &'a mut Utf8State) -> Utf8Compiler<'a> {
+ let target = nfac.add_empty();
+ state.clear();
+ let mut utf8c = Utf8Compiler { nfac, state, target };
+ utf8c.add_empty();
+ utf8c
+ }
+
+ fn finish(&mut self) -> ThompsonRef {
+ self.compile_from(0);
+ let node = self.pop_root();
+ let start = self.compile(node);
+ ThompsonRef { start, end: self.target }
+ }
+
+ fn add(&mut self, ranges: &[Utf8Range]) {
+ let prefix_len = ranges
+ .iter()
+ .zip(&self.state.uncompiled)
+ .take_while(|&(range, node)| {
+ node.last.as_ref().map_or(false, |t| {
+ (t.start, t.end) == (range.start, range.end)
+ })
+ })
+ .count();
+ assert!(prefix_len < ranges.len());
+ self.compile_from(prefix_len);
+ self.add_suffix(&ranges[prefix_len..]);
+ }
+
+ fn compile_from(&mut self, from: usize) {
+ let mut next = self.target;
+ while from + 1 < self.state.uncompiled.len() {
+ let node = self.pop_freeze(next);
+ next = self.compile(node);
+ }
+ self.top_last_freeze(next);
+ }
+
+ fn compile(&mut self, node: Vec<Transition>) -> StateID {
+ let hash = self.state.compiled.hash(&node);
+ if let Some(id) = self.state.compiled.get(&node, hash) {
+ return id;
+ }
+ let id = self.nfac.add_sparse(node.clone());
+ self.state.compiled.set(node, hash, id);
+ id
+ }
+
+ fn add_suffix(&mut self, ranges: &[Utf8Range]) {
+ assert!(!ranges.is_empty());
+ let last = self
+ .state
+ .uncompiled
+ .len()
+ .checked_sub(1)
+ .expect("non-empty nodes");
+ assert!(self.state.uncompiled[last].last.is_none());
+ self.state.uncompiled[last].last = Some(Utf8LastTransition {
+ start: ranges[0].start,
+ end: ranges[0].end,
+ });
+ for r in &ranges[1..] {
+ self.state.uncompiled.push(Utf8Node {
+ trans: vec![],
+ last: Some(Utf8LastTransition { start: r.start, end: r.end }),
+ });
+ }
+ }
+
+ fn add_empty(&mut self) {
+ self.state.uncompiled.push(Utf8Node { trans: vec![], last: None });
+ }
+
+ fn pop_freeze(&mut self, next: StateID) -> Vec<Transition> {
+ let mut uncompiled = self.state.uncompiled.pop().unwrap();
+ uncompiled.set_last_transition(next);
+ uncompiled.trans
+ }
+
+ fn pop_root(&mut self) -> Vec<Transition> {
+ assert_eq!(self.state.uncompiled.len(), 1);
+ assert!(self.state.uncompiled[0].last.is_none());
+ self.state.uncompiled.pop().expect("non-empty nodes").trans
+ }
+
+ fn top_last_freeze(&mut self, next: StateID) {
+ let last = self
+ .state
+ .uncompiled
+ .len()
+ .checked_sub(1)
+ .expect("non-empty nodes");
+ self.state.uncompiled[last].set_last_transition(next);
+ }
+}
+
+impl Utf8Node {
+ fn set_last_transition(&mut self, next: StateID) {
+ if let Some(last) = self.last.take() {
+ self.trans.push(Transition {
+ start: last.start,
+ end: last.end,
+ next,
+ });
+ }
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use regex_syntax::hir::Hir;
+ use regex_syntax::ParserBuilder;
+
+ use super::{Builder, State, StateID, Transition, NFA};
+
+ fn parse(pattern: &str) -> Hir {
+ ParserBuilder::new().build().parse(pattern).unwrap()
+ }
+
+ fn build(pattern: &str) -> NFA {
+ Builder::new().anchored(true).build(&parse(pattern)).unwrap()
+ }
+
+ fn s_byte(byte: u8, next: StateID) -> State {
+ let trans = Transition { start: byte, end: byte, next };
+ State::Range { range: trans }
+ }
+
+ fn s_range(start: u8, end: u8, next: StateID) -> State {
+ let trans = Transition { start, end, next };
+ State::Range { range: trans }
+ }
+
+ fn s_sparse(ranges: &[(u8, u8, StateID)]) -> State {
+ let ranges = ranges
+ .iter()
+ .map(|&(start, end, next)| Transition { start, end, next })
+ .collect();
+ State::Sparse { ranges }
+ }
+
+ fn s_union(alts: &[StateID]) -> State {
+ State::Union { alternates: alts.to_vec().into_boxed_slice() }
+ }
+
+ fn s_match() -> State {
+ State::Match
+ }
+
+ #[test]
+ fn errors() {
+ // unsupported anchors
+ assert!(Builder::new().build(&parse(r"^")).is_err());
+ assert!(Builder::new().build(&parse(r"$")).is_err());
+ assert!(Builder::new().build(&parse(r"\A")).is_err());
+ assert!(Builder::new().build(&parse(r"\z")).is_err());
+
+ // unsupported word boundaries
+ assert!(Builder::new().build(&parse(r"\b")).is_err());
+ assert!(Builder::new().build(&parse(r"\B")).is_err());
+ assert!(Builder::new().build(&parse(r"(?-u)\b")).is_err());
+ }
+
+ // Test that building an unanchored NFA has an appropriate `.*?` prefix.
+ #[test]
+ fn compile_unanchored_prefix() {
+ // When the machine can only match valid UTF-8.
+ let nfa = Builder::new().anchored(false).build(&parse(r"a")).unwrap();
+ // There should be many states since the `.` in `.*?` matches any
+ // Unicode scalar value.
+ assert_eq!(11, nfa.len());
+ assert_eq!(nfa.states[10], s_match());
+ assert_eq!(nfa.states[9], s_byte(b'a', 10));
+
+ // When the machine can match invalid UTF-8.
+ let nfa = Builder::new()
+ .anchored(false)
+ .allow_invalid_utf8(true)
+ .build(&parse(r"a"))
+ .unwrap();
+ assert_eq!(
+ nfa.states,
+ &[
+ s_union(&[2, 1]),
+ s_range(0, 255, 0),
+ s_byte(b'a', 3),
+ s_match(),
+ ]
+ );
+ }
+
+ #[test]
+ fn compile_empty() {
+ assert_eq!(build("").states, &[s_match(),]);
+ }
+
+ #[test]
+ fn compile_literal() {
+ assert_eq!(build("a").states, &[s_byte(b'a', 1), s_match(),]);
+ assert_eq!(
+ build("ab").states,
+ &[s_byte(b'a', 1), s_byte(b'b', 2), s_match(),]
+ );
+ assert_eq!(
+ build("☃").states,
+ &[s_byte(0xE2, 1), s_byte(0x98, 2), s_byte(0x83, 3), s_match(),]
+ );
+
+ // Check that non-UTF-8 literals work.
+ let hir = ParserBuilder::new()
+ .allow_invalid_utf8(true)
+ .build()
+ .parse(r"(?-u)\xFF")
+ .unwrap();
+ let nfa = Builder::new()
+ .anchored(true)
+ .allow_invalid_utf8(true)
+ .build(&hir)
+ .unwrap();
+ assert_eq!(nfa.states, &[s_byte(b'\xFF', 1), s_match(),]);
+ }
+
+ #[test]
+ fn compile_class() {
+ assert_eq!(
+ build(r"[a-z]").states,
+ &[s_range(b'a', b'z', 1), s_match(),]
+ );
+ assert_eq!(
+ build(r"[x-za-c]").states,
+ &[s_sparse(&[(b'a', b'c', 1), (b'x', b'z', 1)]), s_match()]
+ );
+ assert_eq!(
+ build(r"[\u03B1-\u03B4]").states,
+ &[s_range(0xB1, 0xB4, 2), s_byte(0xCE, 0), s_match()]
+ );
+ assert_eq!(
+ build(r"[\u03B1-\u03B4\u{1F919}-\u{1F91E}]").states,
+ &[
+ s_range(0xB1, 0xB4, 5),
+ s_range(0x99, 0x9E, 5),
+ s_byte(0xA4, 1),
+ s_byte(0x9F, 2),
+ s_sparse(&[(0xCE, 0xCE, 0), (0xF0, 0xF0, 3)]),
+ s_match(),
+ ]
+ );
+ assert_eq!(
+ build(r"[a-z☃]").states,
+ &[
+ s_byte(0x83, 3),
+ s_byte(0x98, 0),
+ s_sparse(&[(b'a', b'z', 3), (0xE2, 0xE2, 1)]),
+ s_match(),
+ ]
+ );
+ }
+
+ #[test]
+ fn compile_repetition() {
+ assert_eq!(
+ build(r"a?").states,
+ &[s_union(&[1, 2]), s_byte(b'a', 2), s_match(),]
+ );
+ assert_eq!(
+ build(r"a??").states,
+ &[s_union(&[2, 1]), s_byte(b'a', 2), s_match(),]
+ );
+ }
+
+ #[test]
+ fn compile_group() {
+ assert_eq!(
+ build(r"ab+").states,
+ &[s_byte(b'a', 1), s_byte(b'b', 2), s_union(&[1, 3]), s_match(),]
+ );
+ assert_eq!(
+ build(r"(ab)").states,
+ &[s_byte(b'a', 1), s_byte(b'b', 2), s_match(),]
+ );
+ assert_eq!(
+ build(r"(ab)+").states,
+ &[s_byte(b'a', 1), s_byte(b'b', 2), s_union(&[0, 3]), s_match(),]
+ );
+ }
+
+ #[test]
+ fn compile_alternation() {
+ assert_eq!(
+ build(r"a|b").states,
+ &[s_byte(b'a', 3), s_byte(b'b', 3), s_union(&[0, 1]), s_match(),]
+ );
+ assert_eq!(
+ build(r"|b").states,
+ &[s_byte(b'b', 2), s_union(&[2, 0]), s_match(),]
+ );
+ assert_eq!(
+ build(r"a|").states,
+ &[s_byte(b'a', 2), s_union(&[0, 2]), s_match(),]
+ );
+ }
+}
diff --git a/src/nfa/map.rs b/src/nfa/map.rs
new file mode 100644
index 0000000..e636c0d
--- /dev/null
+++ b/src/nfa/map.rs
@@ -0,0 +1,282 @@
+// This module contains a couple simple and purpose built hash maps. The key
+// trade off they make is that they serve as caches rather than true maps. That
+// is, inserting a new entry may cause eviction of another entry. This gives
+// us two things. First, there's less overhead associated with inserts and
+// lookups. Secondly, it lets us control our memory usage.
+//
+// These maps are used in some fairly hot code when generating NFA states for
+// large Unicode character classes.
+//
+// Instead of exposing a rich hashmap entry API, we just permit the caller
+// to produce a hash of the key directly. The hash can then be reused for both
+// lookups and insertions at the cost of leaking things a bit. But these are
+// for internal use only, so it's fine.
+//
+// The Utf8BoundedMap is used for Daciuk's algorithm for constructing a
+// (almost) minimal DFA for large Unicode character classes in linear time.
+// (Daciuk's algorithm is always used when compiling forward NFAs. For reverse
+// NFAs, it's only used when the compiler is configured to 'shrink' the NFA,
+// since there's a bit more expense in the reverse direction.)
+//
+// The Utf8SuffixMap is used when compiling large Unicode character classes for
+// reverse NFAs when 'shrink' is disabled. Specifically, it augments the naive
+// construction of UTF-8 automata by caching common suffixes. This doesn't
+// get the same space savings as Daciuk's algorithm, but it's basically as
+// fast as the naive approach and typically winds up using less memory (since
+// it generates smaller NFAs) despite the presence of the cache.
+//
+// These maps effectively represent caching mechanisms for CState::Sparse and
+// CState::Range, respectively. The former represents a single NFA state with
+// many transitions of equivalent priority while the latter represents a single
+// NFA state with a single transition. (Neither state ever has or is an
+// epsilon transition.) Thus, they have different key types. It's likely we
+// could make one generic map, but the machinery didn't seem worth it. They
+// are simple enough.
+
+use nfa::{StateID, Transition};
+
+// Basic FNV-1a hash constants as described in:
+// https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
+const PRIME: u64 = 1099511628211;
+const INIT: u64 = 14695981039346656037;
+
+/// A bounded hash map where the key is a sequence of NFA transitions and the
+/// value is a pre-existing NFA state ID.
+///
+/// std's hashmap can be used for this, however, this map has two important
+/// advantages. Firstly, it has lower overhead. Secondly, it permits us to
+/// control our memory usage by limited the number of slots. In general, the
+/// cost here is that this map acts as a cache. That is, inserting a new entry
+/// may remove an old entry. We are okay with this, since it does not impact
+/// correctness in the cases where it is used. The only effect that dropping
+/// states from the cache has is that the resulting NFA generated may be bigger
+/// than it otherwise would be.
+///
+/// This improves benchmarks that compile large Unicode character classes,
+/// since it makes the generation of (almost) minimal UTF-8 automaton faster.
+/// Specifically, one could observe the difference with std's hashmap via
+/// something like the following benchmark:
+///
+/// hyperfine "regex-automata-debug debug -acqr '\w{40} ecurB'"
+///
+/// But to observe that difference, you'd have to modify the code to use
+/// std's hashmap.
+///
+/// It is quite possible that there is a better way to approach this problem.
+/// For example, if there happens to be a very common state that collides with
+/// a lot of less frequent states, then we could wind up with very poor caching
+/// behavior. Alas, the effectiveness of this cache has not been measured.
+/// Instead, ad hoc experiments suggest that it is "good enough." Additional
+/// smarts (such as an LRU eviction policy) have to be weighed against the
+/// amount of extra time they cost.
+#[derive(Clone, Debug)]
+pub struct Utf8BoundedMap {
+ /// The current version of this map. Only entries with matching versions
+ /// are considered during lookups. If an entry is found with a mismatched
+ /// version, then the map behaves as if the entry does not exist.
+ version: u16,
+ /// The total number of entries this map can store.
+ capacity: usize,
+ /// The actual entries, keyed by hash. Collisions between different states
+ /// result in the old state being dropped.
+ map: Vec<Utf8BoundedEntry>,
+}
+
+/// An entry in this map.
+#[derive(Clone, Debug, Default)]
+struct Utf8BoundedEntry {
+ /// The version of the map used to produce this entry. If this entry's
+ /// version does not match the current version of the map, then the map
+ /// should behave as if this entry does not exist.
+ version: u16,
+ /// The key, which is a sorted sequence of non-overlapping NFA transitions.
+ key: Vec<Transition>,
+ /// The state ID corresponding to the state containing the transitions in
+ /// this entry.
+ val: StateID,
+}
+
+impl Utf8BoundedMap {
+ /// Create a new bounded map with the given capacity. The map will never
+ /// grow beyond the given size.
+ ///
+ /// Note that this does not allocate. Instead, callers must call `clear`
+ /// before using this map. `clear` will allocate space if necessary.
+ ///
+ /// This avoids the need to pay for the allocation of this map when
+ /// compiling regexes that lack large Unicode character classes.
+ pub fn new(capacity: usize) -> Utf8BoundedMap {
+ assert!(capacity > 0);
+ Utf8BoundedMap { version: 0, capacity, map: vec![] }
+ }
+
+ /// Clear this map of all entries, but permit the reuse of allocation
+ /// if possible.
+ ///
+ /// This must be called before the map can be used.
+ pub fn clear(&mut self) {
+ if self.map.is_empty() {
+ self.map = vec![Utf8BoundedEntry::default(); self.capacity];
+ } else {
+ self.version = self.version.wrapping_add(1);
+ if self.version == 0 {
+ self.map = vec![Utf8BoundedEntry::default(); self.capacity];
+ }
+ }
+ }
+
+ /// Return a hash of the given transitions.
+ pub fn hash(&self, key: &[Transition]) -> usize {
+ let mut h = INIT;
+ for t in key {
+ h = (h ^ (t.start as u64)).wrapping_mul(PRIME);
+ h = (h ^ (t.end as u64)).wrapping_mul(PRIME);
+ h = (h ^ (t.next as u64)).wrapping_mul(PRIME);
+ }
+ (h as usize) % self.map.len()
+ }
+
+ /// Retrieve the cached state ID corresponding to the given key. The hash
+ /// given must have been computed with `hash` using the same key value.
+ ///
+ /// If there is no cached state with the given transitions, then None is
+ /// returned.
+ pub fn get(&mut self, key: &[Transition], hash: usize) -> Option<StateID> {
+ let entry = &self.map[hash];
+ if entry.version != self.version {
+ return None;
+ }
+ // There may be a hash collision, so we need to confirm real equality.
+ if entry.key != key {
+ return None;
+ }
+ Some(entry.val)
+ }
+
+ /// Add a cached state to this map with the given key. Callers should
+ /// ensure that `state_id` points to a state that contains precisely the
+ /// NFA transitions given.
+ ///
+ /// `hash` must have been computed using the `hash` method with the same
+ /// key.
+ pub fn set(
+ &mut self,
+ key: Vec<Transition>,
+ hash: usize,
+ state_id: StateID,
+ ) {
+ self.map[hash] =
+ Utf8BoundedEntry { version: self.version, key, val: state_id };
+ }
+}
+
+/// A cache of suffixes used to modestly compress UTF-8 automata for large
+/// Unicode character classes.
+#[derive(Clone, Debug)]
+pub struct Utf8SuffixMap {
+ /// The current version of this map. Only entries with matching versions
+ /// are considered during lookups. If an entry is found with a mismatched
+ /// version, then the map behaves as if the entry does not exist.
+ version: u16,
+ /// The total number of entries this map can store.
+ capacity: usize,
+ /// The actual entries, keyed by hash. Collisions between different states
+ /// result in the old state being dropped.
+ map: Vec<Utf8SuffixEntry>,
+}
+
+/// A key that uniquely identifies an NFA state. It is a triple that represents
+/// a transition from one state for a particular byte range.
+#[derive(Clone, Debug, Default, Eq, PartialEq)]
+pub struct Utf8SuffixKey {
+ pub from: StateID,
+ pub start: u8,
+ pub end: u8,
+}
+
+/// An entry in this map.
+#[derive(Clone, Debug, Default)]
+struct Utf8SuffixEntry {
+ /// The version of the map used to produce this entry. If this entry's
+ /// version does not match the current version of the map, then the map
+ /// should behave as if this entry does not exist.
+ version: u16,
+ /// The key, which consists of a transition in a particular state.
+ key: Utf8SuffixKey,
+ /// The identifier that the transition in the key maps to.
+ val: StateID,
+}
+
+impl Utf8SuffixMap {
+ /// Create a new bounded map with the given capacity. The map will never
+ /// grow beyond the given size.
+ ///
+ /// Note that this does not allocate. Instead, callers must call `clear`
+ /// before using this map. `clear` will allocate space if necessary.
+ ///
+ /// This avoids the need to pay for the allocation of this map when
+ /// compiling regexes that lack large Unicode character classes.
+ pub fn new(capacity: usize) -> Utf8SuffixMap {
+ assert!(capacity > 0);
+ Utf8SuffixMap { version: 0, capacity, map: vec![] }
+ }
+
+ /// Clear this map of all entries, but permit the reuse of allocation
+ /// if possible.
+ ///
+ /// This must be called before the map can be used.
+ pub fn clear(&mut self) {
+ if self.map.is_empty() {
+ self.map = vec![Utf8SuffixEntry::default(); self.capacity];
+ } else {
+ self.version = self.version.wrapping_add(1);
+ if self.version == 0 {
+ self.map = vec![Utf8SuffixEntry::default(); self.capacity];
+ }
+ }
+ }
+
+ /// Return a hash of the given transition.
+ pub fn hash(&self, key: &Utf8SuffixKey) -> usize {
+ // Basic FNV-1a hash as described:
+ // https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
+ const PRIME: u64 = 1099511628211;
+ const INIT: u64 = 14695981039346656037;
+
+ let mut h = INIT;
+ h = (h ^ (key.from as u64)).wrapping_mul(PRIME);
+ h = (h ^ (key.start as u64)).wrapping_mul(PRIME);
+ h = (h ^ (key.end as u64)).wrapping_mul(PRIME);
+ (h as usize) % self.map.len()
+ }
+
+ /// Retrieve the cached state ID corresponding to the given key. The hash
+ /// given must have been computed with `hash` using the same key value.
+ ///
+ /// If there is no cached state with the given key, then None is returned.
+ pub fn get(
+ &mut self,
+ key: &Utf8SuffixKey,
+ hash: usize,
+ ) -> Option<StateID> {
+ let entry = &self.map[hash];
+ if entry.version != self.version {
+ return None;
+ }
+ if key != &entry.key {
+ return None;
+ }
+ Some(entry.val)
+ }
+
+ /// Add a cached state to this map with the given key. Callers should
+ /// ensure that `state_id` points to a state that contains precisely the
+ /// NFA transition given.
+ ///
+ /// `hash` must have been computed using the `hash` method with the same
+ /// key.
+ pub fn set(&mut self, key: Utf8SuffixKey, hash: usize, state_id: StateID) {
+ self.map[hash] =
+ Utf8SuffixEntry { version: self.version, key, val: state_id };
+ }
+}
diff --git a/src/nfa/mod.rs b/src/nfa/mod.rs
new file mode 100644
index 0000000..02d0501
--- /dev/null
+++ b/src/nfa/mod.rs
@@ -0,0 +1,252 @@
+use std::fmt;
+
+use classes::ByteClasses;
+pub use nfa::compiler::Builder;
+
+mod compiler;
+mod map;
+mod range_trie;
+
+/// The representation for an NFA state identifier.
+pub type StateID = usize;
+
+/// A final compiled NFA.
+///
+/// The states of the NFA are indexed by state IDs, which are how transitions
+/// are expressed.
+#[derive(Clone)]
+pub struct NFA {
+ /// Whether this NFA can only match at the beginning of input or not.
+ ///
+ /// When true, a match should only be reported if it begins at the 0th
+ /// index of the haystack.
+ anchored: bool,
+ /// The starting state of this NFA.
+ start: StateID,
+ /// The state list. This list is guaranteed to be indexable by the starting
+ /// state ID, and it is also guaranteed to contain exactly one `Match`
+ /// state.
+ states: Vec<State>,
+ /// A mapping from any byte value to its corresponding equivalence class
+ /// identifier. Two bytes in the same equivalence class cannot discriminate
+ /// between a match or a non-match. This map can be used to shrink the
+ /// total size of a DFA's transition table with a small match-time cost.
+ ///
+ /// Note that the NFA's transitions are *not* defined in terms of these
+ /// equivalence classes. The NFA's transitions are defined on the original
+ /// byte values. For the most part, this is because they wouldn't really
+ /// help the NFA much since the NFA already uses a sparse representation
+ /// to represent transitions. Byte classes are most effective in a dense
+ /// representation.
+ byte_classes: ByteClasses,
+}
+
+impl NFA {
+ /// Returns an NFA that always matches at every position.
+ pub fn always_match() -> NFA {
+ NFA {
+ anchored: false,
+ start: 0,
+ states: vec![State::Match],
+ byte_classes: ByteClasses::empty(),
+ }
+ }
+
+ /// Returns an NFA that never matches at any position.
+ pub fn never_match() -> NFA {
+ NFA {
+ anchored: false,
+ start: 0,
+ states: vec![State::Fail],
+ byte_classes: ByteClasses::empty(),
+ }
+ }
+
+ /// Returns true if and only if this NFA is anchored.
+ pub fn is_anchored(&self) -> bool {
+ self.anchored
+ }
+
+ /// Return the number of states in this NFA.
+ pub fn len(&self) -> usize {
+ self.states.len()
+ }
+
+ /// Return the ID of the initial state of this NFA.
+ pub fn start(&self) -> StateID {
+ self.start
+ }
+
+ /// Return the NFA state corresponding to the given ID.
+ pub fn state(&self, id: StateID) -> &State {
+ &self.states[id]
+ }
+
+ /// Return the set of equivalence classes for this NFA. The slice returned
+ /// always has length 256 and maps each possible byte value to its
+ /// corresponding equivalence class ID (which is never more than 255).
+ pub fn byte_classes(&self) -> &ByteClasses {
+ &self.byte_classes
+ }
+}
+
+impl fmt::Debug for NFA {
+ fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ for (i, state) in self.states.iter().enumerate() {
+ let status = if i == self.start { '>' } else { ' ' };
+ writeln!(f, "{}{:06}: {:?}", status, i, state)?;
+ }
+ Ok(())
+ }
+}
+
+/// A state in a final compiled NFA.
+#[derive(Clone, Eq, PartialEq)]
+pub enum State {
+ /// A state that transitions to `next` if and only if the current input
+ /// byte is in the range `[start, end]` (inclusive).
+ ///
+ /// This is a special case of Sparse in that it encodes only one transition
+ /// (and therefore avoids the allocation).
+ Range { range: Transition },
+ /// A state with possibly many transitions, represented in a sparse
+ /// fashion. Transitions are ordered lexicographically by input range.
+ /// As such, this may only be used when every transition has equal
+ /// priority. (In practice, this is only used for encoding large UTF-8
+ /// automata.)
+ Sparse { ranges: Box<[Transition]> },
+ /// An alternation such that there exists an epsilon transition to all
+ /// states in `alternates`, where matches found via earlier transitions
+ /// are preferred over later transitions.
+ Union { alternates: Box<[StateID]> },
+ /// A fail state. When encountered, the automaton is guaranteed to never
+ /// reach a match state.
+ Fail,
+ /// A match state. There is exactly one such occurrence of this state in
+ /// an NFA.
+ Match,
+}
+
+/// A transition to another state, only if the given byte falls in the
+/// inclusive range specified.
+#[derive(Clone, Copy, Eq, Hash, PartialEq)]
+pub struct Transition {
+ pub start: u8,
+ pub end: u8,
+ pub next: StateID,
+}
+
+impl State {
+ /// Returns true if and only if this state contains one or more epsilon
+ /// transitions.
+ pub fn is_epsilon(&self) -> bool {
+ match *self {
+ State::Range { .. }
+ | State::Sparse { .. }
+ | State::Fail
+ | State::Match => false,
+ State::Union { .. } => true,
+ }
+ }
+
+ /// Remap the transitions in this state using the given map. Namely, the
+ /// given map should be indexed according to the transitions currently
+ /// in this state.
+ ///
+ /// This is used during the final phase of the NFA compiler, which turns
+ /// its intermediate NFA into the final NFA.
+ fn remap(&mut self, remap: &[StateID]) {
+ match *self {
+ State::Range { ref mut range } => range.next = remap[range.next],
+ State::Sparse { ref mut ranges } => {
+ for r in ranges.iter_mut() {
+ r.next = remap[r.next];
+ }
+ }
+ State::Union { ref mut alternates } => {
+ for alt in alternates.iter_mut() {
+ *alt = remap[*alt];
+ }
+ }
+ State::Fail => {}
+ State::Match => {}
+ }
+ }
+}
+
+impl fmt::Debug for State {
+ fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ match *self {
+ State::Range { ref range } => range.fmt(f),
+ State::Sparse { ref ranges } => {
+ let rs = ranges
+ .iter()
+ .map(|t| format!("{:?}", t))
+ .collect::<Vec<String>>()
+ .join(", ");
+ write!(f, "sparse({})", rs)
+ }
+ State::Union { ref alternates } => {
+ let alts = alternates
+ .iter()
+ .map(|id| format!("{}", id))
+ .collect::<Vec<String>>()
+ .join(", ");
+ write!(f, "alt({})", alts)
+ }
+ State::Fail => write!(f, "FAIL"),
+ State::Match => write!(f, "MATCH"),
+ }
+ }
+}
+
+impl fmt::Debug for Transition {
+ fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ let Transition { start, end, next } = *self;
+ if self.start == self.end {
+ write!(f, "{} => {}", escape(start), next)
+ } else {
+ write!(f, "{}-{} => {}", escape(start), escape(end), next)
+ }
+ }
+}
+
+/// Return the given byte as its escaped string form.
+fn escape(b: u8) -> String {
+ use std::ascii;
+
+ String::from_utf8(ascii::escape_default(b).collect::<Vec<_>>()).unwrap()
+}
+
+#[cfg(test)]
+mod tests {
+ use super::*;
+ use dense;
+ use dfa::DFA;
+
+ #[test]
+ fn always_match() {
+ let nfa = NFA::always_match();
+ let dfa = dense::Builder::new().build_from_nfa::<usize>(&nfa).unwrap();
+
+ assert_eq!(Some(0), dfa.find_at(b"", 0));
+ assert_eq!(Some(0), dfa.find_at(b"a", 0));
+ assert_eq!(Some(1), dfa.find_at(b"a", 1));
+ assert_eq!(Some(0), dfa.find_at(b"ab", 0));
+ assert_eq!(Some(1), dfa.find_at(b"ab", 1));
+ assert_eq!(Some(2), dfa.find_at(b"ab", 2));
+ }
+
+ #[test]
+ fn never_match() {
+ let nfa = NFA::never_match();
+ let dfa = dense::Builder::new().build_from_nfa::<usize>(&nfa).unwrap();
+
+ assert_eq!(None, dfa.find_at(b"", 0));
+ assert_eq!(None, dfa.find_at(b"a", 0));
+ assert_eq!(None, dfa.find_at(b"a", 1));
+ assert_eq!(None, dfa.find_at(b"ab", 0));
+ assert_eq!(None, dfa.find_at(b"ab", 1));
+ assert_eq!(None, dfa.find_at(b"ab", 2));
+ }
+}
diff --git a/src/nfa/range_trie.rs b/src/nfa/range_trie.rs
new file mode 100644
index 0000000..50767c7
--- /dev/null
+++ b/src/nfa/range_trie.rs
@@ -0,0 +1,1048 @@
+// I've called the primary data structure in this module a "range trie." As far
+// as I can tell, there is no prior art on a data structure like this, however,
+// it's likely someone somewhere has built something like it. Searching for
+// "range trie" turns up the paper "Range Tries for Scalable Address Lookup,"
+// but it does not appear relevant.
+//
+// The range trie is just like a trie in that it is a special case of a
+// deterministic finite state machine. It has states and each state has a set
+// of transitions to other states. It is acyclic, and, like a normal trie,
+// it makes no attempt to reuse common suffixes among its elements. The key
+// difference between a normal trie and a range trie below is that a range trie
+// operates on *contiguous sequences* of bytes instead of singleton bytes.
+// One could say say that our alphabet is ranges of bytes instead of bytes
+// themselves, except a key part of range trie construction is splitting ranges
+// apart to ensure there is at most one transition that can be taken for any
+// byte in a given state.
+//
+// I've tried to explain the details of how the range trie works below, so
+// for now, we are left with trying to understand what problem we're trying to
+// solve. Which is itself fairly involved!
+//
+// At the highest level, here's what we want to do. We want to convert a
+// sequence of Unicode codepoints into a finite state machine whose transitions
+// are over *bytes* and *not* Unicode codepoints. We want this because it makes
+// said finite state machines much smaller and much faster to execute. As a
+// simple example, consider a byte oriented automaton for all Unicode scalar
+// values (0x00 through 0x10FFFF, not including surrogate codepoints):
+//
+// [00-7F]
+// [C2-DF][80-BF]
+// [E0-E0][A0-BF][80-BF]
+// [E1-EC][80-BF][80-BF]
+// [ED-ED][80-9F][80-BF]
+// [EE-EF][80-BF][80-BF]
+// [F0-F0][90-BF][80-BF][80-BF]
+// [F1-F3][80-BF][80-BF][80-BF]
+// [F4-F4][80-8F][80-BF][80-BF]
+//
+// (These byte ranges are generated via the regex-syntax::utf8 module, which
+// was based on Russ Cox's code in RE2, which was in turn based on Ken
+// Thompson's implementation of the same idea in his Plan9 implementation of
+// grep.)
+//
+// It should be fairly straight-forward to see how one could compile this into
+// a DFA. The sequences are sorted and non-overlapping. Essentially, you could
+// build a trie from this fairly easy. The problem comes when your initial
+// range (in this case, 0x00-0x10FFFF) isn't so nice. For example, the class
+// represented by '\w' contains only a tenth of the codepoints that
+// 0x00-0x10FFFF contains, but if we were to write out the byte based ranges
+// as we did above, the list would stretch to 892 entries! This turns into
+// quite a large NFA with a few thousand states. Turning this beast into a DFA
+// takes quite a bit of time. We are thus left with trying to trim down the
+// number of states we produce as early as possible.
+//
+// One approach (used by RE2 and still by the regex crate, at time of writing)
+// is to try to find common suffixes while building NFA states for the above
+// and reuse them. This is very cheap to do and one can control precisely how
+// much extra memory you want to use for the cache.
+//
+// Another approach, however, is to reuse an algorithm for constructing a
+// *minimal* DFA from a sorted sequence of inputs. I don't want to go into
+// the full details here, but I explain it in more depth in my blog post on
+// FSTs[1]. Note that the algorithm not invented by me, but was published
+// in paper by Daciuk et al. in 2000 called "Incremental Construction of
+// MinimalAcyclic Finite-State Automata." Like the suffix cache approach above,
+// it is also possible to control the amount of extra memory one uses, although
+// this usually comes with the cost of sacrificing true minimality. (But it's
+// typically close enough with a reasonably sized cache of states.)
+//
+// The catch is that Daciuk's algorithm only works if you add your keys in
+// lexicographic ascending order. In our case, since we're dealing with ranges,
+// we also need the additional requirement that ranges are either equivalent
+// or do not overlap at all. For example, if one were given the following byte
+// ranges:
+//
+// [BC-BF][80-BF]
+// [BC-BF][90-BF]
+//
+// Then Daciuk's algorithm also would not work, since there is nothing to
+// handle the fact that the ranges overlap. They would need to be split apart.
+// Thankfully, Thompson's algorithm for producing byte ranges for Unicode
+// codepoint ranges meets both of our requirements.
+//
+// ... however, we would also like to be able to compile UTF-8 automata in
+// reverse. We want this because in order to find the starting location of a
+// match using a DFA, we need to run a second DFA---a reversed version of the
+// forward DFA---backwards to discover the match location. Unfortunately, if
+// we reverse our byte sequences for 0x00-0x10FFFF, we get sequences that are
+// can overlap, even if they are sorted:
+//
+// [00-7F]
+// [80-BF][80-9F][ED-ED]
+// [80-BF][80-BF][80-8F][F4-F4]
+// [80-BF][80-BF][80-BF][F1-F3]
+// [80-BF][80-BF][90-BF][F0-F0]
+// [80-BF][80-BF][E1-EC]
+// [80-BF][80-BF][EE-EF]
+// [80-BF][A0-BF][E0-E0]
+// [80-BF][C2-DF]
+//
+// For example, '[80-BF][80-BF][EE-EF]' and '[80-BF][A0-BF][E0-E0]' have
+// overlapping ranges between '[80-BF]' and '[A0-BF]'. Thus, there is no
+// simple way to apply Daciuk's algorithm.
+//
+// And thus, the range trie was born. The range trie's only purpose is to take
+// sequences of byte ranges like the ones above, collect them into a trie and
+// then spit them in a sorted fashion with no overlapping ranges. For example,
+// 0x00-0x10FFFF gets translated to:
+//
+// [0-7F]
+// [80-BF][80-9F][80-8F][F1-F3]
+// [80-BF][80-9F][80-8F][F4]
+// [80-BF][80-9F][90-BF][F0]
+// [80-BF][80-9F][90-BF][F1-F3]
+// [80-BF][80-9F][E1-EC]
+// [80-BF][80-9F][ED]
+// [80-BF][80-9F][EE-EF]
+// [80-BF][A0-BF][80-8F][F1-F3]
+// [80-BF][A0-BF][80-8F][F4]
+// [80-BF][A0-BF][90-BF][F0]
+// [80-BF][A0-BF][90-BF][F1-F3]
+// [80-BF][A0-BF][E0]
+// [80-BF][A0-BF][E1-EC]
+// [80-BF][A0-BF][EE-EF]
+// [80-BF][C2-DF]
+//
+// We've thus satisfied our requirements for running Daciuk's algorithm. All
+// sequences of ranges are sorted, and any corresponding ranges are either
+// exactly equivalent or non-overlapping.
+//
+// In effect, a range trie is building a DFA from a sequence of arbitrary
+// byte ranges. But it uses an algoritm custom tailored to its input, so it
+// is not as costly as traditional DFA construction. While it is still quite
+// a bit more costly than the forward's case (which only needs Daciuk's
+// algorithm), it winds up saving a substantial amount of time if one is doing
+// a full DFA powerset construction later by virtue of producing a much much
+// smaller NFA.
+//
+// [1] - https://blog.burntsushi.net/transducers/
+// [2] - https://www.mitpressjournals.org/doi/pdfplus/10.1162/089120100561601
+
+use std::cell::RefCell;
+use std::fmt;
+use std::mem;
+use std::ops::RangeInclusive;
+use std::u32;
+
+use regex_syntax::utf8::Utf8Range;
+
+/// A smaller state ID means more effective use of the CPU cache and less
+/// time spent copying. The implementation below will panic if the state ID
+/// space is exhausted, but in order for that to happen, the range trie itself
+/// would use well over 100GB of memory. Moreover, it's likely impossible
+/// for the state ID space to get that big. In fact, it's likely that even a
+/// u16 would be good enough here. But it's not quite clear how to prove this.
+type StateID = u32;
+
+/// There is only one final state in this trie. Every sequence of byte ranges
+/// added shares the same final state.
+const FINAL: StateID = 0;
+
+/// The root state of the trie.
+const ROOT: StateID = 1;
+
+/// A range trie represents an ordered set of sequences of bytes.
+///
+/// A range trie accepts as input a sequence of byte ranges and merges
+/// them into the existing set such that the trie can produce a sorted
+/// non-overlapping sequence of byte ranges. The sequence emitted corresponds
+/// precisely to the sequence of bytes matched by the given keys, although the
+/// byte ranges themselves may be split at different boundaries.
+///
+/// The order complexity of this data structure seems difficult to analyze.
+/// If the size of a byte is held as a constant, then insertion is clearly
+/// O(n) where n is the number of byte ranges in the input key. However, if
+/// k=256 is our alphabet size, then insertion could be O(k^2 * n). In
+/// particular it seems possible for pathological inputs to cause insertion
+/// to do a lot of work. However, for what we use this data structure for,
+/// there should be no pathological inputs since the ultimate source is always
+/// a sorted set of Unicode scalar value ranges.
+///
+/// Internally, this trie is setup like a finite state machine. Note though
+/// that it is acyclic.
+#[derive(Clone)]
+pub struct RangeTrie {
+ /// The states in this trie. The first is always the shared final state.
+ /// The second is always the root state. Otherwise, there is no
+ /// particular order.
+ states: Vec<State>,
+ /// A free-list of states. When a range trie is cleared, all of its states
+ /// are added to list. Creating a new state reuses states from this list
+ /// before allocating a new one.
+ free: Vec<State>,
+ /// A stack for traversing this trie to yield sequences of byte ranges in
+ /// lexicographic order.
+ iter_stack: RefCell<Vec<NextIter>>,
+ /// A bufer that stores the current sequence during iteration.
+ iter_ranges: RefCell<Vec<Utf8Range>>,
+ /// A stack used for traversing the trie in order to (deeply) duplicate
+ /// a state.
+ dupe_stack: Vec<NextDupe>,
+ /// A stack used for traversing the trie during insertion of a new
+ /// sequence of byte ranges.
+ insert_stack: Vec<NextInsert>,
+}
+
+/// A single state in this trie.
+#[derive(Clone)]
+struct State {
+ /// A sorted sequence of non-overlapping transitions to other states. Each
+ /// transition corresponds to a single range of bytes.
+ transitions: Vec<Transition>,
+}
+
+/// A transition is a single range of bytes. If a particular byte is in this
+/// range, then the corresponding machine may transition to the state pointed
+/// to by `next_id`.
+#[derive(Clone)]
+struct Transition {
+ /// The byte range.
+ range: Utf8Range,
+ /// The next state to transition to.
+ next_id: StateID,
+}
+
+impl RangeTrie {
+ /// Create a new empty range trie.
+ pub fn new() -> RangeTrie {
+ let mut trie = RangeTrie {
+ states: vec![],
+ free: vec![],
+ iter_stack: RefCell::new(vec![]),
+ iter_ranges: RefCell::new(vec![]),
+ dupe_stack: vec![],
+ insert_stack: vec![],
+ };
+ trie.clear();
+ trie
+ }
+
+ /// Clear this range trie such that it is empty. Clearing a range trie
+ /// and reusing it can beneficial because this may reuse allocations.
+ pub fn clear(&mut self) {
+ self.free.extend(self.states.drain(..));
+ self.add_empty(); // final
+ self.add_empty(); // root
+ }
+
+ /// Iterate over all of the sequences of byte ranges in this trie, and
+ /// call the provided function for each sequence. Iteration occurs in
+ /// lexicographic order.
+ pub fn iter<F: FnMut(&[Utf8Range])>(&self, mut f: F) {
+ let mut stack = self.iter_stack.borrow_mut();
+ stack.clear();
+ let mut ranges = self.iter_ranges.borrow_mut();
+ ranges.clear();
+
+ // We do iteration in a way that permits us to use a single buffer
+ // for our keys. We iterate in a depth first fashion, while being
+ // careful to expand our frontier as we move deeper in the trie.
+ stack.push(NextIter { state_id: ROOT, tidx: 0 });
+ while let Some(NextIter { mut state_id, mut tidx }) = stack.pop() {
+ // This could be implemented more simply without an inner loop
+ // here, but at the cost of more stack pushes.
+ loop {
+ let state = self.state(state_id);
+ // If we're visited all transitions in this state, then pop
+ // back to the parent state.
+ if tidx >= state.transitions.len() {
+ ranges.pop();
+ break;
+ }
+
+ let t = &state.transitions[tidx];
+ ranges.push(t.range);
+ if t.next_id == FINAL {
+ f(&ranges);
+ ranges.pop();
+ tidx += 1;
+ } else {
+ // Expand our frontier. Once we come back to this state
+ // via the stack, start in on the next transition.
+ stack.push(NextIter { state_id, tidx: tidx + 1 });
+ // Otherwise, move to the first transition of the next
+ // state.
+ state_id = t.next_id;
+ tidx = 0;
+ }
+ }
+ }
+ }
+
+ /// Inserts a new sequence of ranges into this trie.
+ ///
+ /// The sequence given must be non-empty and must not have a length
+ /// exceeding 4.
+ pub fn insert(&mut self, ranges: &[Utf8Range]) {
+ assert!(!ranges.is_empty());
+ assert!(ranges.len() <= 4);
+
+ let mut stack = mem::replace(&mut self.insert_stack, vec![]);
+ stack.clear();
+
+ stack.push(NextInsert::new(ROOT, ranges));
+ while let Some(next) = stack.pop() {
+ let (state_id, ranges) = (next.state_id(), next.ranges());
+ assert!(!ranges.is_empty());
+
+ let (mut new, rest) = (ranges[0], &ranges[1..]);
+
+ // i corresponds to the position of the existing transition on
+ // which we are operating. Typically, the result is to remove the
+ // transition and replace it with two or more new transitions
+ // corresponding to the partitions generated by splitting the
+ // 'new' with the ith transition's range.
+ let mut i = self.state(state_id).find(new);
+
+ // In this case, there is no overlap *and* the new range is greater
+ // than all existing ranges. So we can just add it to the end.
+ if i == self.state(state_id).transitions.len() {
+ let next_id = NextInsert::push(self, &mut stack, rest);
+ self.add_transition(state_id, new, next_id);
+ continue;
+ }
+
+ // The need for this loop is a bit subtle, buf basically, after
+ // we've handled the partitions from our initial split, it's
+ // possible that there will be a partition leftover that overlaps
+ // with a subsequent transition. If so, then we have to repeat
+ // the split process again with the leftovers and that subsequent
+ // transition.
+ 'OUTER: loop {
+ let old = self.state(state_id).transitions[i].clone();
+ let split = match Split::new(old.range, new) {
+ Some(split) => split,
+ None => {
+ let next_id = NextInsert::push(self, &mut stack, rest);
+ self.add_transition_at(i, state_id, new, next_id);
+ continue;
+ }
+ };
+ let splits = split.as_slice();
+ // If we only have one partition, then the ranges must be
+ // equivalent. There's nothing to do here for this state, so
+ // just move on to the next one.
+ if splits.len() == 1 {
+ // ... but only if we have anything left to do.
+ if !rest.is_empty() {
+ stack.push(NextInsert::new(old.next_id, rest));
+ }
+ break;
+ }
+ // At this point, we know that 'split' is non-empty and there
+ // must be some overlap AND that the two ranges are not
+ // equivalent. Therefore, the existing range MUST be removed
+ // and split up somehow. Instead of actually doing the removal
+ // and then a subsequent insertion---with all the memory
+ // shuffling that entails---we simply overwrite the transition
+ // at position `i` for the first new transition we want to
+ // insert. After that, we're forced to do expensive inserts.
+ let mut first = true;
+ let mut add_trans =
+ |trie: &mut RangeTrie, pos, from, range, to| {
+ if first {
+ trie.set_transition_at(pos, from, range, to);
+ first = false;
+ } else {
+ trie.add_transition_at(pos, from, range, to);
+ }
+ };
+ for (j, &srange) in splits.iter().enumerate() {
+ match srange {
+ SplitRange::Old(r) => {
+ // Deep clone the state pointed to by the ith
+ // transition. This is always necessary since 'old'
+ // is always coupled with at least a 'both'
+ // partition. We don't want any new changes made
+ // via the 'both' partition to impact the part of
+ // the transition that doesn't overlap with the
+ // new range.
+ let dup_id = self.duplicate(old.next_id);
+ add_trans(self, i, state_id, r, dup_id);
+ }
+ SplitRange::New(r) => {
+ // This is a bit subtle, but if this happens to be
+ // the last partition in our split, it is possible
+ // that this overlaps with a subsequent transition.
+ // If it does, then we must repeat the whole
+ // splitting process over again with `r` and the
+ // subsequent transition.
+ {
+ let trans = &self.state(state_id).transitions;
+ if j + 1 == splits.len()
+ && i < trans.len()
+ && intersects(r, trans[i].range)
+ {
+ new = r;
+ continue 'OUTER;
+ }
+ }
+
+ // ... otherwise, setup exploration for a new
+ // empty state and add a brand new transition for
+ // this new range.
+ let next_id =
+ NextInsert::push(self, &mut stack, rest);
+ add_trans(self, i, state_id, r, next_id);
+ }
+ SplitRange::Both(r) => {
+ // Continue adding the remaining ranges on this
+ // path and update the transition with the new
+ // range.
+ if !rest.is_empty() {
+ stack.push(NextInsert::new(old.next_id, rest));
+ }
+ add_trans(self, i, state_id, r, old.next_id);
+ }
+ }
+ i += 1;
+ }
+ // If we've reached this point, then we know that there are
+ // no subsequent transitions with any overlap. Therefore, we
+ // can stop processing this range and move on to the next one.
+ break;
+ }
+ }
+ self.insert_stack = stack;
+ }
+
+ pub fn add_empty(&mut self) -> StateID {
+ if self.states.len() as u64 > u32::MAX as u64 {
+ // This generally should not happen since a range trie is only
+ // ever used to compile a single sequence of Unicode scalar values.
+ // If we ever got to this point, we would, at *minimum*, be using
+ // 96GB in just the range trie alone.
+ panic!("too many sequences added to range trie");
+ }
+ let id = self.states.len() as StateID;
+ // If we have some free states available, then use them to avoid
+ // more allocations.
+ if let Some(mut state) = self.free.pop() {
+ state.clear();
+ self.states.push(state);
+ } else {
+ self.states.push(State { transitions: vec![] });
+ }
+ id
+ }
+
+ /// Performs a deep clone of the given state and returns the duplicate's
+ /// state ID.
+ ///
+ /// A "deep clone" in this context means that the state given along with
+ /// recursively all states that it points to are copied. Once complete,
+ /// the given state ID and the returned state ID share nothing.
+ ///
+ /// This is useful during range trie insertion when a new range overlaps
+ /// with an existing range that is bigger than the new one. The part of
+ /// the existing range that does *not* overlap with the new one is that
+ /// duplicated so that adding the new range to the overlap doesn't disturb
+ /// the non-overlapping portion.
+ ///
+ /// There's one exception: if old_id is the final state, then it is not
+ /// duplicated and the same final state is returned. This is because all
+ /// final states in this trie are equivalent.
+ fn duplicate(&mut self, old_id: StateID) -> StateID {
+ if old_id == FINAL {
+ return FINAL;
+ }
+
+ let mut stack = mem::replace(&mut self.dupe_stack, vec![]);
+ stack.clear();
+
+ let new_id = self.add_empty();
+ // old_id is the state we're cloning and new_id is the ID of the
+ // duplicated state for old_id.
+ stack.push(NextDupe { old_id, new_id });
+ while let Some(NextDupe { old_id, new_id }) = stack.pop() {
+ for i in 0..self.state(old_id).transitions.len() {
+ let t = self.state(old_id).transitions[i].clone();
+ if t.next_id == FINAL {
+ // All final states are the same, so there's no need to
+ // duplicate it.
+ self.add_transition(new_id, t.range, FINAL);
+ continue;
+ }
+
+ let new_child_id = self.add_empty();
+ self.add_transition(new_id, t.range, new_child_id);
+ stack.push(NextDupe {
+ old_id: t.next_id,
+ new_id: new_child_id,
+ });
+ }
+ }
+ self.dupe_stack = stack;
+ new_id
+ }
+
+ /// Adds the given transition to the given state.
+ ///
+ /// Callers must ensure that all previous transitions in this state
+ /// are lexicographically smaller than the given range.
+ fn add_transition(
+ &mut self,
+ from_id: StateID,
+ range: Utf8Range,
+ next_id: StateID,
+ ) {
+ self.state_mut(from_id)
+ .transitions
+ .push(Transition { range, next_id });
+ }
+
+ /// Like `add_transition`, except this inserts the transition just before
+ /// the ith transition.
+ fn add_transition_at(
+ &mut self,
+ i: usize,
+ from_id: StateID,
+ range: Utf8Range,
+ next_id: StateID,
+ ) {
+ self.state_mut(from_id)
+ .transitions
+ .insert(i, Transition { range, next_id });
+ }
+
+ /// Overwrites the transition at position i with the given transition.
+ fn set_transition_at(
+ &mut self,
+ i: usize,
+ from_id: StateID,
+ range: Utf8Range,
+ next_id: StateID,
+ ) {
+ self.state_mut(from_id).transitions[i] = Transition { range, next_id };
+ }
+
+ /// Return an immutable borrow for the state with the given ID.
+ fn state(&self, id: StateID) -> &State {
+ &self.states[id as usize]
+ }
+
+ /// Return a mutable borrow for the state with the given ID.
+ fn state_mut(&mut self, id: StateID) -> &mut State {
+ &mut self.states[id as usize]
+ }
+}
+
+impl State {
+ /// Find the position at which the given range should be inserted in this
+ /// state.
+ ///
+ /// The position returned is always in the inclusive range
+ /// [0, transitions.len()]. If 'transitions.len()' is returned, then the
+ /// given range overlaps with no other range in this state *and* is greater
+ /// than all of them.
+ ///
+ /// For all other possible positions, the given range either overlaps
+ /// with the transition at that position or is otherwise less than it
+ /// with no overlap (and is greater than the previous transition). In the
+ /// former case, careful attention must be paid to inserting this range
+ /// as a new transition. In the latter case, the range can be inserted as
+ /// a new transition at the given position without disrupting any other
+ /// transitions.
+ fn find(&self, range: Utf8Range) -> usize {
+ /// Returns the position `i` at which `pred(xs[i])` first returns true
+ /// such that for all `j >= i`, `pred(xs[j]) == true`. If `pred` never
+ /// returns true, then `xs.len()` is returned.
+ ///
+ /// We roll our own binary search because it doesn't seem like the
+ /// standard library's binary search can be used here. Namely, if
+ /// there is an overlapping range, then we want to find the first such
+ /// occurrence, but there may be many. Or at least, it's not quite
+ /// clear to me how to do it.
+ fn binary_search<T, F>(xs: &[T], mut pred: F) -> usize
+ where
+ F: FnMut(&T) -> bool,
+ {
+ let (mut left, mut right) = (0, xs.len());
+ while left < right {
+ // Overflow is impossible because xs.len() <= 256.
+ let mid = (left + right) / 2;
+ if pred(&xs[mid]) {
+ right = mid;
+ } else {
+ left = mid + 1;
+ }
+ }
+ left
+ }
+
+ // Benchmarks suggest that binary search is just a bit faster than
+ // straight linear search. Specifically when using the debug tool:
+ //
+ // hyperfine "regex-automata-debug debug -acqr '\w{40} ecurB'"
+ binary_search(&self.transitions, |t| range.start <= t.range.end)
+ }
+
+ /// Clear this state such that it has zero transitions.
+ fn clear(&mut self) {
+ self.transitions.clear();
+ }
+}
+
+/// The next state to process during duplication.
+#[derive(Clone, Debug)]
+struct NextDupe {
+ /// The state we want to duplicate.
+ old_id: StateID,
+ /// The ID of the new state that is a duplicate of old_id.
+ new_id: StateID,
+}
+
+/// The next state (and its corresponding transition) that we want to visit
+/// during iteration in lexicographic order.
+#[derive(Clone, Debug)]
+struct NextIter {
+ state_id: StateID,
+ tidx: usize,
+}
+
+/// The next state to process during insertion and any remaining ranges that we
+/// want to add for a partcular sequence of ranges. The first such instance
+/// is always the root state along with all ranges given.
+#[derive(Clone, Debug)]
+struct NextInsert {
+ /// The next state to begin inserting ranges. This state should be the
+ /// state at which `ranges[0]` should be inserted.
+ state_id: StateID,
+ /// The ranges to insert. We used a fixed-size array here to avoid an
+ /// allocation.
+ ranges: [Utf8Range; 4],
+ /// The number of valid ranges in the above array.
+ len: u8,
+}
+
+impl NextInsert {
+ /// Create the next item to visit. The given state ID should correspond
+ /// to the state at which the first range in the given slice should be
+ /// inserted. The slice given must not be empty and it must be no longer
+ /// than 4.
+ fn new(state_id: StateID, ranges: &[Utf8Range]) -> NextInsert {
+ let len = ranges.len();
+ assert!(len > 0);
+ assert!(len <= 4);
+
+ let mut tmp = [Utf8Range { start: 0, end: 0 }; 4];
+ tmp[..len].copy_from_slice(ranges);
+ NextInsert { state_id, ranges: tmp, len: len as u8 }
+ }
+
+ /// Push a new empty state to visit along with any remaining ranges that
+ /// still need to be inserted. The ID of the new empty state is returned.
+ ///
+ /// If ranges is empty, then no new state is created and FINAL is returned.
+ fn push(
+ trie: &mut RangeTrie,
+ stack: &mut Vec<NextInsert>,
+ ranges: &[Utf8Range],
+ ) -> StateID {
+ if ranges.is_empty() {
+ FINAL
+ } else {
+ let next_id = trie.add_empty();
+ stack.push(NextInsert::new(next_id, ranges));
+ next_id
+ }
+ }
+
+ /// Return the ID of the state to visit.
+ fn state_id(&self) -> StateID {
+ self.state_id
+ }
+
+ /// Return the remaining ranges to insert.
+ fn ranges(&self) -> &[Utf8Range] {
+ &self.ranges[..self.len as usize]
+ }
+}
+
+/// Split represents a partitioning of two ranges into one or more ranges. This
+/// is the secret sauce that makes a range trie work, as it's what tells us
+/// how to deal with two overlapping but unequal ranges during insertion.
+///
+/// Essentially, either two ranges overlap or they don't. If they don't, then
+/// handling insertion is easy: just insert the new range into its
+/// lexicographically correct position. Since it does not overlap with anything
+/// else, no other transitions are impacted by the new range.
+///
+/// If they do overlap though, there are generally three possible cases to
+/// handle:
+///
+/// 1. The part where the two ranges actually overlap. i.e., The intersection.
+/// 2. The part of the existing range that is not in the the new range.
+/// 3. The part of the new range that is not in the old range.
+///
+/// (1) is guaranteed to always occur since all overlapping ranges have a
+/// non-empty intersection. If the two ranges are not equivalent, then at
+/// least one of (2) or (3) is guaranteed to occur as well. In some cases,
+/// e.g., `[0-4]` and `[4-9]`, all three cases will occur.
+///
+/// This `Split` type is responsible for providing (1), (2) and (3) for any
+/// possible pair of byte ranges.
+///
+/// As for insertion, for the overlap in (1), the remaining ranges to insert
+/// should be added by following the corresponding transition. However, this
+/// should only be done for the overlapping parts of the range. If there was
+/// a part of the existing range that was not in the new range, then that
+/// existing part must be split off from the transition and duplicated. The
+/// remaining parts of the overlap can then be added to using the new ranges
+/// without disturbing the existing range.
+///
+/// Handling the case for the part of a new range that is not in an existing
+/// range is seemingly easy. Just treat it as if it were a non-overlapping
+/// range. The problem here is that if this new non-overlapping range occurs
+/// after both (1) and (2), then it's possible that it can overlap with the
+/// next transition in the current state. If it does, then the whole process
+/// must be repeated!
+///
+/// # Details of the 3 cases
+///
+/// The following details the various cases that are implemented in code
+/// below. It's plausible that the number of cases is not actually minimal,
+/// but it's important for this code to remain at least somewhat readable.
+///
+/// Given [a,b] and [x,y], where a <= b, x <= y, b < 256 and y < 256, we define
+/// the follow distinct relationships where at least one must apply. The order
+/// of these matters, since multiple can match. The first to match applies.
+///
+/// 1. b < x <=> [a,b] < [x,y]
+/// 2. y < a <=> [x,y] < [a,b]
+///
+/// In the case of (1) and (2), these are the only cases where there is no
+/// overlap. Or otherwise, the intersection of [a,b] and [x,y] is empty. In
+/// order to compute the intersection, one can do [max(a,x), min(b,y)]. The
+/// intersection in all of the following cases is non-empty.
+///
+/// 3. a = x && b = y <=> [a,b] == [x,y]
+/// 4. a = x && b < y <=> [x,y] right-extends [a,b]
+/// 5. b = y && a > x <=> [x,y] left-extends [a,b]
+/// 6. x = a && y < b <=> [a,b] right-extends [x,y]
+/// 7. y = b && x > a <=> [a,b] left-extends [x,y]
+/// 8. a > x && b < y <=> [x,y] covers [a,b]
+/// 9. x > a && y < b <=> [a,b] covers [x,y]
+/// 10. b = x && a < y <=> [a,b] is left-adjacent to [x,y]
+/// 11. y = a && x < b <=> [x,y] is left-adjacent to [a,b]
+/// 12. b > x && b < y <=> [a,b] left-overlaps [x,y]
+/// 13. y > a && y < b <=> [x,y] left-overlaps [a,b]
+///
+/// In cases 3-13, we can form rules that partition the ranges into a
+/// non-overlapping ordered sequence of ranges:
+///
+/// 3. [a,b]
+/// 4. [a,b], [b+1,y]
+/// 5. [x,a-1], [a,b]
+/// 6. [x,y], [y+1,b]
+/// 7. [a,x-1], [x,y]
+/// 8. [x,a-1], [a,b], [b+1,y]
+/// 9. [a,x-1], [x,y], [y+1,b]
+/// 10. [a,b-1], [b,b], [b+1,y]
+/// 11. [x,y-1], [y,y], [y+1,b]
+/// 12. [a,x-1], [x,b], [b+1,y]
+/// 13. [x,a-1], [a,y], [y+1,b]
+///
+/// In the code below, we go a step further and identify each of the above
+/// outputs as belonging either to the overlap of the two ranges or to one
+/// of [a,b] or [x,y] exclusively.
+#[derive(Clone, Debug, Eq, PartialEq)]
+struct Split {
+ partitions: [SplitRange; 3],
+ len: usize,
+}
+
+/// A tagged range indicating how it was derived from a pair of ranges.
+#[derive(Clone, Copy, Debug, Eq, PartialEq)]
+enum SplitRange {
+ Old(Utf8Range),
+ New(Utf8Range),
+ Both(Utf8Range),
+}
+
+impl Split {
+ /// Create a partitioning of the given ranges.
+ ///
+ /// If the given ranges have an empty intersection, then None is returned.
+ fn new(o: Utf8Range, n: Utf8Range) -> Option<Split> {
+ let range = |r: RangeInclusive<u8>| Utf8Range {
+ start: *r.start(),
+ end: *r.end(),
+ };
+ let old = |r| SplitRange::Old(range(r));
+ let new = |r| SplitRange::New(range(r));
+ let both = |r| SplitRange::Both(range(r));
+
+ // Use same names as the comment above to make it easier to compare.
+ let (a, b, x, y) = (o.start, o.end, n.start, n.end);
+
+ if b < x || y < a {
+ // case 1, case 2
+ None
+ } else if a == x && b == y {
+ // case 3
+ Some(Split::parts1(both(a..=b)))
+ } else if a == x && b < y {
+ // case 4
+ Some(Split::parts2(both(a..=b), new(b + 1..=y)))
+ } else if b == y && a > x {
+ // case 5
+ Some(Split::parts2(new(x..=a - 1), both(a..=b)))
+ } else if x == a && y < b {
+ // case 6
+ Some(Split::parts2(both(x..=y), old(y + 1..=b)))
+ } else if y == b && x > a {
+ // case 7
+ Some(Split::parts2(old(a..=x - 1), both(x..=y)))
+ } else if a > x && b < y {
+ // case 8
+ Some(Split::parts3(new(x..=a - 1), both(a..=b), new(b + 1..=y)))
+ } else if x > a && y < b {
+ // case 9
+ Some(Split::parts3(old(a..=x - 1), both(x..=y), old(y + 1..=b)))
+ } else if b == x && a < y {
+ // case 10
+ Some(Split::parts3(old(a..=b - 1), both(b..=b), new(b + 1..=y)))
+ } else if y == a && x < b {
+ // case 11
+ Some(Split::parts3(new(x..=y - 1), both(y..=y), old(y + 1..=b)))
+ } else if b > x && b < y {
+ // case 12
+ Some(Split::parts3(old(a..=x - 1), both(x..=b), new(b + 1..=y)))
+ } else if y > a && y < b {
+ // case 13
+ Some(Split::parts3(new(x..=a - 1), both(a..=y), old(y + 1..=b)))
+ } else {
+ unreachable!()
+ }
+ }
+
+ /// Create a new split with a single partition. This only occurs when two
+ /// ranges are equivalent.
+ fn parts1(r1: SplitRange) -> Split {
+ // This value doesn't matter since it is never accessed.
+ let nada = SplitRange::Old(Utf8Range { start: 0, end: 0 });
+ Split { partitions: [r1, nada, nada], len: 1 }
+ }
+
+ /// Create a new split with two partitions.
+ fn parts2(r1: SplitRange, r2: SplitRange) -> Split {
+ // This value doesn't matter since it is never accessed.
+ let nada = SplitRange::Old(Utf8Range { start: 0, end: 0 });
+ Split { partitions: [r1, r2, nada], len: 2 }
+ }
+
+ /// Create a new split with three partitions.
+ fn parts3(r1: SplitRange, r2: SplitRange, r3: SplitRange) -> Split {
+ Split { partitions: [r1, r2, r3], len: 3 }
+ }
+
+ /// Return the partitions in this split as a slice.
+ fn as_slice(&self) -> &[SplitRange] {
+ &self.partitions[..self.len]
+ }
+}
+
+impl fmt::Debug for RangeTrie {
+ fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ writeln!(f, "")?;
+ for (i, state) in self.states.iter().enumerate() {
+ let status = if i == FINAL as usize { '*' } else { ' ' };
+ writeln!(f, "{}{:06}: {:?}", status, i, state)?;
+ }
+ Ok(())
+ }
+}
+
+impl fmt::Debug for State {
+ fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ let rs = self
+ .transitions
+ .iter()
+ .map(|t| format!("{:?}", t))
+ .collect::<Vec<String>>()
+ .join(", ");
+ write!(f, "{}", rs)
+ }
+}
+
+impl fmt::Debug for Transition {
+ fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ if self.range.start == self.range.end {
+ write!(f, "{:02X} => {:02X}", self.range.start, self.next_id)
+ } else {
+ write!(
+ f,
+ "{:02X}-{:02X} => {:02X}",
+ self.range.start, self.range.end, self.next_id
+ )
+ }
+ }
+}
+
+/// Returns true if and only if the given ranges intersect.
+fn intersects(r1: Utf8Range, r2: Utf8Range) -> bool {
+ !(r1.end < r2.start || r2.end < r1.start)
+}
+
+#[cfg(test)]
+mod tests {
+ use std::ops::RangeInclusive;
+
+ use regex_syntax::utf8::Utf8Range;
+
+ use super::*;
+
+ fn r(range: RangeInclusive<u8>) -> Utf8Range {
+ Utf8Range { start: *range.start(), end: *range.end() }
+ }
+
+ fn split_maybe(
+ old: RangeInclusive<u8>,
+ new: RangeInclusive<u8>,
+ ) -> Option<Split> {
+ Split::new(r(old), r(new))
+ }
+
+ fn split(
+ old: RangeInclusive<u8>,
+ new: RangeInclusive<u8>,
+ ) -> Vec<SplitRange> {
+ split_maybe(old, new).unwrap().as_slice().to_vec()
+ }
+
+ #[test]
+ fn no_splits() {
+ // case 1
+ assert_eq!(None, split_maybe(0..=1, 2..=3));
+ // case 2
+ assert_eq!(None, split_maybe(2..=3, 0..=1));
+ }
+
+ #[test]
+ fn splits() {
+ let range = |r: RangeInclusive<u8>| Utf8Range {
+ start: *r.start(),
+ end: *r.end(),
+ };
+ let old = |r| SplitRange::Old(range(r));
+ let new = |r| SplitRange::New(range(r));
+ let both = |r| SplitRange::Both(range(r));
+
+ // case 3
+ assert_eq!(split(0..=0, 0..=0), vec![both(0..=0)]);
+ assert_eq!(split(9..=9, 9..=9), vec![both(9..=9)]);
+
+ // case 4
+ assert_eq!(split(0..=5, 0..=6), vec![both(0..=5), new(6..=6)]);
+ assert_eq!(split(0..=5, 0..=8), vec![both(0..=5), new(6..=8)]);
+ assert_eq!(split(5..=5, 5..=8), vec![both(5..=5), new(6..=8)]);
+
+ // case 5
+ assert_eq!(split(1..=5, 0..=5), vec![new(0..=0), both(1..=5)]);
+ assert_eq!(split(3..=5, 0..=5), vec![new(0..=2), both(3..=5)]);
+ assert_eq!(split(5..=5, 0..=5), vec![new(0..=4), both(5..=5)]);
+
+ // case 6
+ assert_eq!(split(0..=6, 0..=5), vec![both(0..=5), old(6..=6)]);
+ assert_eq!(split(0..=8, 0..=5), vec![both(0..=5), old(6..=8)]);
+ assert_eq!(split(5..=8, 5..=5), vec![both(5..=5), old(6..=8)]);
+
+ // case 7
+ assert_eq!(split(0..=5, 1..=5), vec![old(0..=0), both(1..=5)]);
+ assert_eq!(split(0..=5, 3..=5), vec![old(0..=2), both(3..=5)]);
+ assert_eq!(split(0..=5, 5..=5), vec![old(0..=4), both(5..=5)]);
+
+ // case 8
+ assert_eq!(
+ split(3..=6, 2..=7),
+ vec![new(2..=2), both(3..=6), new(7..=7)],
+ );
+ assert_eq!(
+ split(3..=6, 1..=8),
+ vec![new(1..=2), both(3..=6), new(7..=8)],
+ );
+
+ // case 9
+ assert_eq!(
+ split(2..=7, 3..=6),
+ vec![old(2..=2), both(3..=6), old(7..=7)],
+ );
+ assert_eq!(
+ split(1..=8, 3..=6),
+ vec![old(1..=2), both(3..=6), old(7..=8)],
+ );
+
+ // case 10
+ assert_eq!(
+ split(3..=6, 6..=7),
+ vec![old(3..=5), both(6..=6), new(7..=7)],
+ );
+ assert_eq!(
+ split(3..=6, 6..=8),
+ vec![old(3..=5), both(6..=6), new(7..=8)],
+ );
+ assert_eq!(
+ split(5..=6, 6..=7),
+ vec![old(5..=5), both(6..=6), new(7..=7)],
+ );
+
+ // case 11
+ assert_eq!(
+ split(6..=7, 3..=6),
+ vec![new(3..=5), both(6..=6), old(7..=7)],
+ );
+ assert_eq!(
+ split(6..=8, 3..=6),
+ vec![new(3..=5), both(6..=6), old(7..=8)],
+ );
+ assert_eq!(
+ split(6..=7, 5..=6),
+ vec![new(5..=5), both(6..=6), old(7..=7)],
+ );
+
+ // case 12
+ assert_eq!(
+ split(3..=7, 5..=9),
+ vec![old(3..=4), both(5..=7), new(8..=9)],
+ );
+ assert_eq!(
+ split(3..=5, 4..=6),
+ vec![old(3..=3), both(4..=5), new(6..=6)],
+ );
+
+ // case 13
+ assert_eq!(
+ split(5..=9, 3..=7),
+ vec![new(3..=4), both(5..=7), old(8..=9)],
+ );
+ assert_eq!(
+ split(4..=6, 3..=5),
+ vec![new(3..=3), both(4..=5), old(6..=6)],
+ );
+ }
+
+ // Arguably there should be more tests here, but in practice, this data
+ // structure is well covered by the huge number of regex tests.
+}