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 { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result33 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 { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result42 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 { unit() -> Self54 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 from_byte(byte: Byte) -> Self62 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 from_ref(r: R) -> Self74 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 from_tree(tree: Tree<!, R>) -> Result<Self, Uninhabited>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. concat(self, other: Self) -> Self110 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).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. union(self, other: Self) -> Self137 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).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 edges_from(&self, start: State) -> Option<&Map<Transition<R>, Set<State>>>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 { new() -> Self169 pub(crate) fn new() -> Self { 170 static COUNTER: AtomicU32 = AtomicU32::new(0); 171 Self(COUNTER.fetch_add(1, Ordering::SeqCst)) 172 } 173 } 174