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     pub(crate) fn from_nfa(nfa: Nfa<R>) -> Self {
 108         let Nfa { transitions: nfa_transitions, start: nfa_start, accepting: nfa_accepting } = nfa;
 109
 110         let mut dfa_transitions: Map<State, Transitions<R>> = Map::default();
 111         let mut nfa_to_dfa: Map<nfa::State, State> = Map::default();
 112         let dfa_start = State::new();
 113         nfa_to_dfa.insert(nfa_start, dfa_start);
 114
 115         let mut queue = vec![(nfa_start, dfa_start)];
 116
 117         while let Some((nfa_state, dfa_state)) = queue.pop() {
 118             if nfa_state == nfa_accepting {
 119                 continue;
 120             }
 121
 122             for (nfa_transition, next_nfa_states) in nfa_transitions[&nfa_state].iter() {
 123                 let dfa_transitions =
 124                     dfa_transitions.entry(dfa_state).or_insert_with(Default::default);
 125
 126                 let mapped_state = next_nfa_states.iter().find_map(|x| nfa_to_dfa.get(x).copied());
 127
 128                 let next_dfa_state = match nfa_transition {
 129                     &nfa::Transition::Byte(b) => *dfa_transitions
 130                         .byte_transitions
 131                         .entry(b)
 132                         .or_insert_with(|| mapped_state.unwrap_or_else(State::new)),
 133                     &nfa::Transition::Ref(r) => *dfa_transitions
 134                         .ref_transitions
 135                         .entry(r)
 136                         .or_insert_with(|| mapped_state.unwrap_or_else(State::new)),
 137                 };
 138
 139                 for &next_nfa_state in next_nfa_states {
 140                     nfa_to_dfa.entry(next_nfa_state).or_insert_with(|| {
 141                         queue.push((next_nfa_state, next_dfa_state));
 142                         next_dfa_state
 143                     });
 144                 }
 145             }
 146         }
 147
 148         let dfa_accepting = nfa_to_dfa[&nfa_accepting];
 149
 150         Self { transitions: dfa_transitions, start: dfa_start, accepting: dfa_accepting }
 151     }
 152
 153     pub(crate) fn bytes_from(&self, start: State) -> Option<&Map<Byte, State>> {
 154         Some(&self.transitions.get(&start)?.byte_transitions)
 155     }
 156
 157     pub(crate) fn byte_from(&self, start: State, byte: Byte) -> Option<State> {
 158         self.transitions.get(&start)?.byte_transitions.get(&byte).copied()
 159     }
 160
 161     pub(crate) fn refs_from(&self, start: State) -> Option<&Map<R, State>> {
 162         Some(&self.transitions.get(&start)?.ref_transitions)
 163     }
 164 }
 165
 166 impl State {
 167     pub(crate) fn new() -> Self {
 168         static COUNTER: AtomicU32 = AtomicU32::new(0);
 169         Self(COUNTER.fetch_add(1, Ordering::SeqCst))
 170     }
 171 }
 172
 173 impl<R> From<nfa::Transition<R>> for Transition<R>
 174 where
 175     R: Ref,
 176 {
 177     fn from(nfa_transition: nfa::Transition<R>) -> Self {
 178         match nfa_transition {
 179             nfa::Transition::Byte(byte) => Transition::Byte(byte),
 180             nfa::Transition::Ref(r) => Transition::Ref(r),
 181         }
 182     }
 183 }