diff options
Diffstat (limited to 'compiler/rustc_transmute/src/layout/nfa.rs')
-rw-r--r-- | compiler/rustc_transmute/src/layout/nfa.rs | 179 |
1 files changed, 179 insertions, 0 deletions
diff --git a/compiler/rustc_transmute/src/layout/nfa.rs b/compiler/rustc_transmute/src/layout/nfa.rs new file mode 100644 index 000000000..f25e3c1fd --- /dev/null +++ b/compiler/rustc_transmute/src/layout/nfa.rs @@ -0,0 +1,179 @@ +use super::{Byte, Ref, Tree, Uninhabited}; +use crate::{Map, Set}; +use std::fmt; +use std::sync::atomic::{AtomicU32, Ordering}; + +/// A non-deterministic finite automaton (NFA) that represents the layout of a type. +/// The transmutability of two given types is computed by comparing their `Nfa`s. +#[derive(PartialEq, Debug)] +pub(crate) struct Nfa<R> +where + R: Ref, +{ + pub(crate) transitions: Map<State, Map<Transition<R>, Set<State>>>, + pub(crate) start: State, + pub(crate) accepting: State, +} + +/// The states in a `Nfa` represent byte offsets. +#[derive(Hash, Eq, PartialEq, PartialOrd, Ord, Copy, Clone)] +pub(crate) struct State(u32); + +/// The transitions between states in a `Nfa` reflect bit validity. +#[derive(Hash, Eq, PartialEq, Clone, Copy)] +pub(crate) enum Transition<R> +where + R: Ref, +{ + Byte(Byte), + Ref(R), +} + +impl fmt::Debug for State { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "S_{}", self.0) + } +} + +impl<R> fmt::Debug for Transition<R> +where + R: Ref, +{ + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + match &self { + Self::Byte(b) => b.fmt(f), + Self::Ref(r) => r.fmt(f), + } + } +} + +impl<R> Nfa<R> +where + R: Ref, +{ + pub(crate) fn unit() -> Self { + let transitions: Map<State, Map<Transition<R>, Set<State>>> = Map::default(); + let start = State::new(); + let accepting = start; + + Nfa { transitions, start, accepting } + } + + pub(crate) fn from_byte(byte: Byte) -> Self { + let mut transitions: Map<State, Map<Transition<R>, Set<State>>> = Map::default(); + let start = State::new(); + let accepting = State::new(); + + let source = transitions.entry(start).or_default(); + let edge = source.entry(Transition::Byte(byte)).or_default(); + edge.insert(accepting); + + Nfa { transitions, start, accepting } + } + + pub(crate) fn from_ref(r: R) -> Self { + let mut transitions: Map<State, Map<Transition<R>, Set<State>>> = Map::default(); + let start = State::new(); + let accepting = State::new(); + + let source = transitions.entry(start).or_default(); + let edge = source.entry(Transition::Ref(r)).or_default(); + edge.insert(accepting); + + Nfa { transitions, start, accepting } + } + + pub(crate) fn from_tree(tree: Tree<!, R>) -> Result<Self, Uninhabited> { + Ok(match tree { + Tree::Byte(b) => Self::from_byte(b), + Tree::Def(..) => unreachable!(), + Tree::Ref(r) => Self::from_ref(r), + Tree::Alt(alts) => { + let mut alts = alts.into_iter().map(Self::from_tree); + let mut nfa = alts.next().ok_or(Uninhabited)??; + for alt in alts { + nfa = nfa.union(alt?); + } + nfa + } + Tree::Seq(elts) => { + let mut nfa = Self::unit(); + for elt in elts.into_iter().map(Self::from_tree) { + nfa = nfa.concat(elt?); + } + nfa + } + }) + } + + /// Concatenate two `Nfa`s. + pub(crate) fn concat(self, other: Self) -> Self { + if self.start == self.accepting { + return other; + } else if other.start == other.accepting { + return self; + } + + let start = self.start; + let accepting = other.accepting; + + let mut transitions: Map<State, Map<Transition<R>, Set<State>>> = self.transitions; + + // the iteration order doesn't matter + #[cfg_attr(feature = "rustc", allow(rustc::potential_query_instability))] + for (source, transition) in other.transitions { + let fix_state = |state| if state == other.start { self.accepting } else { state }; + let entry = transitions.entry(fix_state(source)).or_default(); + for (edge, destinations) in transition { + let entry = entry.entry(edge.clone()).or_default(); + for destination in destinations { + entry.insert(fix_state(destination)); + } + } + } + + Self { transitions, start, accepting } + } + + /// Compute the union of two `Nfa`s. + pub(crate) fn union(self, other: Self) -> Self { + let start = self.start; + let accepting = self.accepting; + + let mut transitions: Map<State, Map<Transition<R>, Set<State>>> = self.transitions.clone(); + + // the iteration order doesn't matter + #[cfg_attr(feature = "rustc", allow(rustc::potential_query_instability))] + for (&(mut source), transition) in other.transitions.iter() { + // if source is starting state of `other`, replace with starting state of `self` + if source == other.start { + source = self.start; + } + let entry = transitions.entry(source).or_default(); + for (edge, destinations) in transition { + let entry = entry.entry(edge.clone()).or_default(); + // the iteration order doesn't matter + #[cfg_attr(feature = "rustc", allow(rustc::potential_query_instability))] + for &(mut destination) in destinations { + // if dest is accepting state of `other`, replace with accepting state of `self` + if destination == other.accepting { + destination = self.accepting; + } + entry.insert(destination); + } + } + } + Self { transitions, start, accepting } + } + + pub(crate) fn edges_from(&self, start: State) -> Option<&Map<Transition<R>, Set<State>>> { + self.transitions.get(&start) + } +} + +impl State { + pub(crate) fn new() -> Self { + static COUNTER: AtomicU32 = AtomicU32::new(0); + Self(COUNTER.fetch_add(1, Ordering::SeqCst)) + } +} |