compiler/rustc_transmute/src/layout/dfa.rs

   1 use super::{nfa, Byte, Nfa, Ref};
   2 use crate::Map;
   3 use std::fmt;
   4 use std::sync::atomic::{AtomicU32, Ordering};
   5
   6 #[derive(PartialEq, Clone, Debug)]
   7 pub(crate) struct Dfa<R>
   8 where
   9     R: Ref,
  10 {
  11     pub(crate) transitions: Map<State, Transitions<R>>,
  12     pub(crate) start: State,
  13     pub(crate) accepting: State,
  14 }
  15
  16 #[derive(PartialEq, Clone, Debug)]
  17 pub(crate) struct Transitions<R>
  18 where
  19     R: Ref,
  20 {
  21     byte_transitions: Map<Byte, State>,
  22     ref_transitions: Map<R, State>,
  23 }
  24
  25 impl<R> Default for Transitions<R>
  26 where
  27     R: Ref,
  28 {
  29     fn default() -> Self {
  30         Self { byte_transitions: Map::default(), ref_transitions: Map::default() }
  31     }
  32 }
  33
  34 impl<R> Transitions<R>
  35 where
  36     R: Ref,
  37 {
  38     fn insert(&mut self, transition: Transition<R>, state: State) {
  39         match transition {
  40             Transition::Byte(b) => {
  41                 self.byte_transitions.insert(b, state);
  42             }
  43             Transition::Ref(r) => {
  44                 self.ref_transitions.insert(r, state);
  45             }
  46         }
  47     }
  48 }
  49
  50 /// The states in a `Nfa` represent byte offsets.
  51 #[derive(Hash, Eq, PartialEq, PartialOrd, Ord, Copy, Clone)]
  52 pub(crate) struct State(u32);
  53
  54 #[derive(Hash, Eq, PartialEq, Clone, Copy)]
  55 pub(crate) enum Transition<R>
  56 where
  57     R: Ref,
  58 {
  59     Byte(Byte),
  60     Ref(R),
  61 }
  62
  63 impl fmt::Debug for State {
  64     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  65         write!(f, "S_{}", self.0)
  66     }
  67 }
  68
  69 impl<R> fmt::Debug for Transition<R>
  70 where
  71     R: Ref,
  72 {
  73     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  74         match &self {
  75             Self::Byte(b) => b.fmt(f),
  76             Self::Ref(r) => r.fmt(f),
  77         }
  78     }
  79 }
  80
  81 impl<R> Dfa<R>
  82 where
  83     R: Ref,
  84 {
  85     pub(crate) fn unit() -> Self {
  86         let transitions: Map<State, Transitions<R>> = Map::default();
  87         let start = State::new();
  88         let accepting = start;
  89
  90         Self { transitions, start, accepting }
  91     }
  92
  93     #[cfg(test)]
  94     pub(crate) fn bool() -> Self {
  95         let mut transitions: Map<State, Transitions<R>> = Map::default();
  96         let start = State::new();
  97         let accepting = State::new();
  98
  99         transitions.entry(start).or_default().insert(Transition::Byte(Byte::Init(0x00)), accepting);
 100
 101         transitions.entry(start).or_default().insert(Transition::Byte(Byte::Init(0x01)), accepting);
 102
 103         Self { transitions, start, accepting }
 104     }
 105
 106     #[instrument(level = "debug")]
 107     #[cfg_attr(feature = "rustc", allow(rustc::potential_query_instability))]
 108     pub(crate) fn from_nfa(nfa: Nfa<R>) -> Self {
 109         let Nfa { transitions: nfa_transitions, start: nfa_start, accepting: nfa_accepting } = nfa;
 110
 111         let mut dfa_transitions: Map<State, Transitions<R>> = Map::default();
 112         let mut nfa_to_dfa: Map<nfa::State, State> = Map::default();
 113         let dfa_start = State::new();
 114         nfa_to_dfa.insert(nfa_start, dfa_start);
 115
 116         let mut queue = vec![(nfa_start, dfa_start)];
 117
 118         while let Some((nfa_state, dfa_state)) = queue.pop() {
 119             if nfa_state == nfa_accepting {
 120                 continue;
 121             }
 122
 123             for (nfa_transition, next_nfa_states) in nfa_transitions[&nfa_state].iter() {
 124                 let dfa_transitions =
 125                     dfa_transitions.entry(dfa_state).or_insert_with(Default::default);
 126
 127                 let mapped_state = next_nfa_states.iter().find_map(|x| nfa_to_dfa.get(x).copied());
 128
 129                 let next_dfa_state = match nfa_transition {
 130                     &nfa::Transition::Byte(b) => *dfa_transitions
 131                         .byte_transitions
 132                         .entry(b)
 133                         .or_insert_with(|| mapped_state.unwrap_or_else(State::new)),
 134                     &nfa::Transition::Ref(r) => *dfa_transitions
 135                         .ref_transitions
 136                         .entry(r)
 137                         .or_insert_with(|| mapped_state.unwrap_or_else(State::new)),
 138                 };
 139
 140                 for &next_nfa_state in next_nfa_states {
 141                     nfa_to_dfa.entry(next_nfa_state).or_insert_with(|| {
 142                         queue.push((next_nfa_state, next_dfa_state));
 143                         next_dfa_state
 144                     });
 145                 }
 146             }
 147         }
 148
 149         let dfa_accepting = nfa_to_dfa[&nfa_accepting];
 150
 151         Self { transitions: dfa_transitions, start: dfa_start, accepting: dfa_accepting }
 152     }
 153
 154     pub(crate) fn bytes_from(&self, start: State) -> Option<&Map<Byte, State>> {
 155         Some(&self.transitions.get(&start)?.byte_transitions)
 156     }
 157
 158     pub(crate) fn byte_from(&self, start: State, byte: Byte) -> Option<State> {
 159         self.transitions.get(&start)?.byte_transitions.get(&byte).copied()
 160     }
 161
 162     pub(crate) fn refs_from(&self, start: State) -> Option<&Map<R, State>> {
 163         Some(&self.transitions.get(&start)?.ref_transitions)
 164     }
 165 }
 166
 167 impl State {
 168     pub(crate) fn new() -> Self {
 169         static COUNTER: AtomicU32 = AtomicU32::new(0);
 170         Self(COUNTER.fetch_add(1, Ordering::SeqCst))
 171     }
 172 }
 173
 174 impl<R> From<nfa::Transition<R>> for Transition<R>
 175 where
 176     R: Ref,
 177 {
 178     fn from(nfa_transition: nfa::Transition<R>) -> Self {
 179         match nfa_transition {
 180             nfa::Transition::Byte(byte) => Transition::Byte(byte),
 181             nfa::Transition::Ref(r) => Transition::Ref(r),
 182         }
 183     }
 184 }