Adding upstream version 1.64.0+dfsg1.upstream/1.64.0+dfsg1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 1048 insertions, 0 deletions

diff --git a/vendor/regex-automata/src/nfa/range_trie.rs b/vendor/regex-automata/src/nfa/range_trie.rs
new file mode 100644
index 000000000..50767c7c6
--- /dev/null
+++ b/vendor/regex-automata/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.
+}