aboutsummaryrefslogtreecommitdiff
path: root/src/minimize.rs
diff options
context:
space:
mode:
Diffstat (limited to 'src/minimize.rs')
-rw-r--r--src/minimize.rs373
1 files changed, 373 insertions, 0 deletions
diff --git a/src/minimize.rs b/src/minimize.rs
new file mode 100644
index 0000000..ededa5f
--- /dev/null
+++ b/src/minimize.rs
@@ -0,0 +1,373 @@
+use std::cell::RefCell;
+use std::fmt;
+use std::mem;
+use std::rc::Rc;
+
+use dense;
+use state_id::{dead_id, StateID};
+
+type DFARepr<S> = dense::Repr<Vec<S>, S>;
+
+/// An implementation of Hopcroft's algorithm for minimizing DFAs.
+///
+/// The algorithm implemented here is mostly taken from Wikipedia:
+/// https://en.wikipedia.org/wiki/DFA_minimization#Hopcroft's_algorithm
+///
+/// This code has had some light optimization attention paid to it,
+/// particularly in the form of reducing allocation as much as possible.
+/// However, it is still generally slow. Future optimization work should
+/// probably focus on the bigger picture rather than micro-optimizations. For
+/// example:
+///
+/// 1. Figure out how to more intelligently create initial partitions. That is,
+/// Hopcroft's algorithm starts by creating two partitions of DFA states
+/// that are known to NOT be equivalent: match states and non-match states.
+/// The algorithm proceeds by progressively refining these partitions into
+/// smaller partitions. If we could start with more partitions, then we
+/// could reduce the amount of work that Hopcroft's algorithm needs to do.
+/// 2. For every partition that we visit, we find all incoming transitions to
+/// every state in the partition for *every* element in the alphabet. (This
+/// is why using byte classes can significantly decrease minimization times,
+/// since byte classes shrink the alphabet.) This is quite costly and there
+/// is perhaps some redundant work being performed depending on the specific
+/// states in the set. For example, we might be able to only visit some
+/// elements of the alphabet based on the transitions.
+/// 3. Move parts of minimization into determinization. If minimization has
+/// fewer states to deal with, then it should run faster. A prime example
+/// of this might be large Unicode classes, which are generated in way that
+/// can create a lot of redundant states. (Some work has been done on this
+/// point during NFA compilation via the algorithm described in the
+/// "Incremental Construction of MinimalAcyclic Finite-State Automata"
+/// paper.)
+pub(crate) struct Minimizer<'a, S: 'a> {
+ dfa: &'a mut DFARepr<S>,
+ in_transitions: Vec<Vec<Vec<S>>>,
+ partitions: Vec<StateSet<S>>,
+ waiting: Vec<StateSet<S>>,
+}
+
+impl<'a, S: StateID> fmt::Debug for Minimizer<'a, S> {
+ fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ f.debug_struct("Minimizer")
+ .field("dfa", &self.dfa)
+ .field("in_transitions", &self.in_transitions)
+ .field("partitions", &self.partitions)
+ .field("waiting", &self.waiting)
+ .finish()
+ }
+}
+
+/// A set of states. A state set makes up a single partition in Hopcroft's
+/// algorithm.
+///
+/// It is represented by an ordered set of state identifiers. We use shared
+/// ownership so that a single state set can be in both the set of partitions
+/// and in the set of waiting sets simultaneously without an additional
+/// allocation. Generally, once a state set is built, it becomes immutable.
+///
+/// We use this representation because it avoids the overhead of more
+/// traditional set data structures (HashSet/BTreeSet), and also because
+/// computing intersection/subtraction on this representation is especially
+/// fast.
+#[derive(Clone, Debug, Eq, PartialEq, PartialOrd, Ord)]
+struct StateSet<S>(Rc<RefCell<Vec<S>>>);
+
+impl<'a, S: StateID> Minimizer<'a, S> {
+ pub fn new(dfa: &'a mut DFARepr<S>) -> Minimizer<'a, S> {
+ let in_transitions = Minimizer::incoming_transitions(dfa);
+ let partitions = Minimizer::initial_partitions(dfa);
+ let waiting = vec![partitions[0].clone()];
+
+ Minimizer { dfa, in_transitions, partitions, waiting }
+ }
+
+ pub fn run(mut self) {
+ let mut incoming = StateSet::empty();
+ let mut scratch1 = StateSet::empty();
+ let mut scratch2 = StateSet::empty();
+ let mut newparts = vec![];
+
+ while let Some(set) = self.waiting.pop() {
+ for b in (0..self.dfa.alphabet_len()).map(|b| b as u8) {
+ self.find_incoming_to(b, &set, &mut incoming);
+
+ for p in 0..self.partitions.len() {
+ self.partitions[p].intersection(&incoming, &mut scratch1);
+ if scratch1.is_empty() {
+ newparts.push(self.partitions[p].clone());
+ continue;
+ }
+
+ self.partitions[p].subtract(&incoming, &mut scratch2);
+ if scratch2.is_empty() {
+ newparts.push(self.partitions[p].clone());
+ continue;
+ }
+
+ let (x, y) =
+ (scratch1.deep_clone(), scratch2.deep_clone());
+ newparts.push(x.clone());
+ newparts.push(y.clone());
+ match self.find_waiting(&self.partitions[p]) {
+ Some(i) => {
+ self.waiting[i] = x;
+ self.waiting.push(y);
+ }
+ None => {
+ if x.len() <= y.len() {
+ self.waiting.push(x);
+ } else {
+ self.waiting.push(y);
+ }
+ }
+ }
+ }
+ newparts = mem::replace(&mut self.partitions, newparts);
+ newparts.clear();
+ }
+ }
+
+ // At this point, we now have a minimal partitioning of states, where
+ // each partition is an equivalence class of DFA states. Now we need to
+ // use this partioning to update the DFA to only contain one state for
+ // each partition.
+
+ // Create a map from DFA state ID to the representative ID of the
+ // equivalence class to which it belongs. The representative ID of an
+ // equivalence class of states is the minimum ID in that class.
+ let mut state_to_part = vec![dead_id(); self.dfa.state_count()];
+ for p in &self.partitions {
+ p.iter(|id| state_to_part[id.to_usize()] = p.min());
+ }
+
+ // Generate a new contiguous sequence of IDs for minimal states, and
+ // create a map from equivalence IDs to the new IDs. Thus, the new
+ // minimal ID of *any* state in the unminimized DFA can be obtained
+ // with minimals_ids[state_to_part[old_id]].
+ let mut minimal_ids = vec![dead_id(); self.dfa.state_count()];
+ let mut new_id = S::from_usize(0);
+ for (id, _) in self.dfa.states() {
+ if state_to_part[id.to_usize()] == id {
+ minimal_ids[id.to_usize()] = new_id;
+ new_id = S::from_usize(new_id.to_usize() + 1);
+ }
+ }
+ // The total number of states in the minimal DFA.
+ let minimal_count = new_id.to_usize();
+
+ // Re-map this DFA in place such that the only states remaining
+ // correspond to the representative states of every equivalence class.
+ for id in (0..self.dfa.state_count()).map(S::from_usize) {
+ // If this state isn't a representative for an equivalence class,
+ // then we skip it since it won't appear in the minimal DFA.
+ if state_to_part[id.to_usize()] != id {
+ continue;
+ }
+ for (_, next) in self.dfa.get_state_mut(id).iter_mut() {
+ *next = minimal_ids[state_to_part[next.to_usize()].to_usize()];
+ }
+ self.dfa.swap_states(id, minimal_ids[id.to_usize()]);
+ }
+ // Trim off all unused states from the pre-minimized DFA. This
+ // represents all states that were merged into a non-singleton
+ // equivalence class of states, and appeared after the first state
+ // in each such class. (Because the state with the smallest ID in each
+ // equivalence class is its representative ID.)
+ self.dfa.truncate_states(minimal_count);
+
+ // Update the new start state, which is now just the minimal ID of
+ // whatever state the old start state was collapsed into.
+ let old_start = self.dfa.start_state();
+ self.dfa.set_start_state(
+ minimal_ids[state_to_part[old_start.to_usize()].to_usize()],
+ );
+
+ // In order to update the ID of the maximum match state, we need to
+ // find the maximum ID among all of the match states in the minimized
+ // DFA. This is not necessarily the new ID of the unminimized maximum
+ // match state, since that could have been collapsed with a much
+ // earlier match state. Therefore, to find the new max match state,
+ // we iterate over all previous match states, find their corresponding
+ // new minimal ID, and take the maximum of those.
+ let old_max = self.dfa.max_match_state();
+ self.dfa.set_max_match_state(dead_id());
+ for id in (0..(old_max.to_usize() + 1)).map(S::from_usize) {
+ let part = state_to_part[id.to_usize()];
+ let new_id = minimal_ids[part.to_usize()];
+ if new_id > self.dfa.max_match_state() {
+ self.dfa.set_max_match_state(new_id);
+ }
+ }
+ }
+
+ fn find_waiting(&self, set: &StateSet<S>) -> Option<usize> {
+ self.waiting.iter().position(|s| s == set)
+ }
+
+ fn find_incoming_to(
+ &self,
+ b: u8,
+ set: &StateSet<S>,
+ incoming: &mut StateSet<S>,
+ ) {
+ incoming.clear();
+ set.iter(|id| {
+ for &inid in &self.in_transitions[id.to_usize()][b as usize] {
+ incoming.add(inid);
+ }
+ });
+ incoming.canonicalize();
+ }
+
+ fn initial_partitions(dfa: &DFARepr<S>) -> Vec<StateSet<S>> {
+ let mut is_match = StateSet::empty();
+ let mut no_match = StateSet::empty();
+ for (id, _) in dfa.states() {
+ if dfa.is_match_state(id) {
+ is_match.add(id);
+ } else {
+ no_match.add(id);
+ }
+ }
+
+ let mut sets = vec![is_match];
+ if !no_match.is_empty() {
+ sets.push(no_match);
+ }
+ sets.sort_by_key(|s| s.len());
+ sets
+ }
+
+ fn incoming_transitions(dfa: &DFARepr<S>) -> Vec<Vec<Vec<S>>> {
+ let mut incoming = vec![];
+ for _ in dfa.states() {
+ incoming.push(vec![vec![]; dfa.alphabet_len()]);
+ }
+ for (id, state) in dfa.states() {
+ for (b, next) in state.transitions() {
+ incoming[next.to_usize()][b as usize].push(id);
+ }
+ }
+ incoming
+ }
+}
+
+impl<S: StateID> StateSet<S> {
+ fn empty() -> StateSet<S> {
+ StateSet(Rc::new(RefCell::new(vec![])))
+ }
+
+ fn add(&mut self, id: S) {
+ self.0.borrow_mut().push(id);
+ }
+
+ fn min(&self) -> S {
+ self.0.borrow()[0]
+ }
+
+ fn canonicalize(&mut self) {
+ self.0.borrow_mut().sort();
+ self.0.borrow_mut().dedup();
+ }
+
+ fn clear(&mut self) {
+ self.0.borrow_mut().clear();
+ }
+
+ fn len(&self) -> usize {
+ self.0.borrow().len()
+ }
+
+ fn is_empty(&self) -> bool {
+ self.len() == 0
+ }
+
+ fn deep_clone(&self) -> StateSet<S> {
+ let ids = self.0.borrow().iter().cloned().collect();
+ StateSet(Rc::new(RefCell::new(ids)))
+ }
+
+ fn iter<F: FnMut(S)>(&self, mut f: F) {
+ for &id in self.0.borrow().iter() {
+ f(id);
+ }
+ }
+
+ fn intersection(&self, other: &StateSet<S>, dest: &mut StateSet<S>) {
+ dest.clear();
+ if self.is_empty() || other.is_empty() {
+ return;
+ }
+
+ let (seta, setb) = (self.0.borrow(), other.0.borrow());
+ let (mut ita, mut itb) = (seta.iter().cloned(), setb.iter().cloned());
+ let (mut a, mut b) = (ita.next().unwrap(), itb.next().unwrap());
+ loop {
+ if a == b {
+ dest.add(a);
+ a = match ita.next() {
+ None => break,
+ Some(a) => a,
+ };
+ b = match itb.next() {
+ None => break,
+ Some(b) => b,
+ };
+ } else if a < b {
+ a = match ita.next() {
+ None => break,
+ Some(a) => a,
+ };
+ } else {
+ b = match itb.next() {
+ None => break,
+ Some(b) => b,
+ };
+ }
+ }
+ }
+
+ fn subtract(&self, other: &StateSet<S>, dest: &mut StateSet<S>) {
+ dest.clear();
+ if self.is_empty() || other.is_empty() {
+ self.iter(|s| dest.add(s));
+ return;
+ }
+
+ let (seta, setb) = (self.0.borrow(), other.0.borrow());
+ let (mut ita, mut itb) = (seta.iter().cloned(), setb.iter().cloned());
+ let (mut a, mut b) = (ita.next().unwrap(), itb.next().unwrap());
+ loop {
+ if a == b {
+ a = match ita.next() {
+ None => break,
+ Some(a) => a,
+ };
+ b = match itb.next() {
+ None => {
+ dest.add(a);
+ break;
+ }
+ Some(b) => b,
+ };
+ } else if a < b {
+ dest.add(a);
+ a = match ita.next() {
+ None => break,
+ Some(a) => a,
+ };
+ } else {
+ b = match itb.next() {
+ None => {
+ dest.add(a);
+ break;
+ }
+ Some(b) => b,
+ };
+ }
+ }
+ for a in ita {
+ dest.add(a);
+ }
+ }
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-13 20:58:09 +0000