compiler/rustc_transmute/src/layout/nfa.rs

   1 use super::{Byte, Ref, Tree, Uninhabited};
   2 use crate::{Map, Set};
   3 use std::fmt;
   4 use std::sync::atomic::{AtomicU32, Ordering};
   5
   6 /// A non-deterministic finite automaton (NFA) that represents the layout of a type.
   7 /// The transmutability of two given types is computed by comparing their `Nfa`s.
   8 #[derive(PartialEq, Debug)]
   9 pub(crate) struct Nfa<R>
  10 where
  11     R: Ref,
  12 {
  13     pub(crate) transitions: Map<State, Map<Transition<R>, Set<State>>>,
  14     pub(crate) start: State,
  15     pub(crate) accepting: State,
  16 }
  17
  18 /// The states in a `Nfa` represent byte offsets.
  19 #[derive(Hash, Eq, PartialEq, PartialOrd, Ord, Copy, Clone)]
  20 pub(crate) struct State(u32);
  21
  22 /// The transitions between states in a `Nfa` reflect bit validity.
  23 #[derive(Hash, Eq, PartialEq, Clone, Copy)]
  24 pub(crate) enum Transition<R>
  25 where
  26     R: Ref,
  27 {
  28     Byte(Byte),
  29     Ref(R),
  30 }
  31
  32 impl fmt::Debug for State {
  33     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  34         write!(f, "S_{}", self.0)
  35     }
  36 }
  37
  38 impl<R> fmt::Debug for Transition<R>
  39 where
  40     R: Ref,
  41 {
  42     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  43         match &self {
  44             Self::Byte(b) => b.fmt(f),
  45             Self::Ref(r) => r.fmt(f),
  46         }
  47     }
  48 }
  49
  50 impl<R> Nfa<R>
  51 where
  52     R: Ref,
  53 {
  54     pub(crate) fn unit() -> Self {
  55         let transitions: Map<State, Map<Transition<R>, Set<State>>> = Map::default();
  56         let start = State::new();
  57         let accepting = start;
  58
  59         Nfa { transitions, start, accepting }
  60     }
  61
  62     pub(crate) fn from_byte(byte: Byte) -> Self {
  63         let mut transitions: Map<State, Map<Transition<R>, Set<State>>> = Map::default();
  64         let start = State::new();
  65         let accepting = State::new();
  66
  67         let source = transitions.entry(start).or_default();
  68         let edge = source.entry(Transition::Byte(byte)).or_default();
  69         edge.insert(accepting);
  70
  71         Nfa { transitions, start, accepting }
  72     }
  73
  74     pub(crate) fn from_ref(r: R) -> Self {
  75         let mut transitions: Map<State, Map<Transition<R>, Set<State>>> = Map::default();
  76         let start = State::new();
  77         let accepting = State::new();
  78
  79         let source = transitions.entry(start).or_default();
  80         let edge = source.entry(Transition::Ref(r)).or_default();
  81         edge.insert(accepting);
  82
  83         Nfa { transitions, start, accepting }
  84     }
  85
  86     pub(crate) fn from_tree(tree: Tree<!, R>) -> Result<Self, Uninhabited> {
  87         Ok(match tree {
  88             Tree::Byte(b) => Self::from_byte(b),
  89             Tree::Def(..) => unreachable!(),
  90             Tree::Ref(r) => Self::from_ref(r),
  91             Tree::Alt(alts) => {
  92                 let mut alts = alts.into_iter().map(Self::from_tree);
  93                 let mut nfa = alts.next().ok_or(Uninhabited)??;
  94                 for alt in alts {
  95                     nfa = nfa.union(alt?);
  96                 }
  97                 nfa
  98             }
  99             Tree::Seq(elts) => {
 100                 let mut nfa = Self::unit();
 101                 for elt in elts.into_iter().map(Self::from_tree) {
 102                     nfa = nfa.concat(elt?);
 103                 }
 104                 nfa
 105             }
 106         })
 107     }
 108
 109     /// Concatenate two `Nfa`s.
 110     pub(crate) fn concat(self, other: Self) -> Self {
 111         if self.start == self.accepting {
 112             return other;
 113         } else if other.start == other.accepting {
 114             return self;
 115         }
 116
 117         let start = self.start;
 118         let accepting = other.accepting;
 119
 120         let mut transitions: Map<State, Map<Transition<R>, Set<State>>> = self.transitions;
 121
 122         for (source, transition) in other.transitions {
 123             let fix_state = |state| if state == other.start { self.accepting } else { state };
 124             let entry = transitions.entry(fix_state(source)).or_default();
 125             for (edge, destinations) in transition {
 126                 let entry = entry.entry(edge.clone()).or_default();
 127                 for destination in destinations {
 128                     entry.insert(fix_state(destination));
 129                 }
 130             }
 131         }
 132
 133         Self { transitions, start, accepting }
 134     }
 135
 136     /// Compute the union of two `Nfa`s.
 137     pub(crate) fn union(self, other: Self) -> Self {
 138         let start = self.start;
 139         let accepting = self.accepting;
 140
 141         let mut transitions: Map<State, Map<Transition<R>, Set<State>>> = self.transitions.clone();
 142
 143         for (&(mut source), transition) in other.transitions.iter() {
 144             // if source is starting state of `other`, replace with starting state of `self`
 145             if source == other.start {
 146                 source = self.start;
 147             }
 148             let entry = transitions.entry(source).or_default();
 149             for (edge, destinations) in transition {
 150                 let entry = entry.entry(edge.clone()).or_default();
 151                 for &(mut destination) in destinations {
 152                     // if dest is accepting state of `other`, replace with accepting state of `self`
 153                     if destination == other.accepting {
 154                         destination = self.accepting;
 155                     }
 156                     entry.insert(destination);
 157                 }
 158             }
 159         }
 160         Self { transitions, start, accepting }
 161     }
 162
 163     pub(crate) fn edges_from(&self, start: State) -> Option<&Map<Transition<R>, Set<State>>> {
 164         self.transitions.get(&start)
 165     }
 166 }
 167
 168 impl State {
 169     pub(crate) fn new() -> Self {
 170         static COUNTER: AtomicU32 = AtomicU32::new(0);
 171         Self(COUNTER.fetch_add(1, Ordering::SeqCst))
 172     }
 173 }