rustc_transmute/layout/
nfa.rs

Help
1use std::fmt;
2use std::sync::atomic::{AtomicU32, Ordering};
3
4use super::{Byte, Ref, Tree, Uninhabited};
5use crate::{Map, Set};
6
7/// A non-deterministic finite automaton (NFA) that represents the layout of a type.
8/// The transmutability of two given types is computed by comparing their `Nfa`s.
9#[derive(PartialEq, Debug)]
10pub(crate) struct Nfa<R>
11where
12    R: Ref,
13{
14    pub(crate) transitions: Map<State, Map<Transition<R>, Set<State>>>,
15    pub(crate) start: State,
16    pub(crate) accepting: State,
17}
18
19/// The states in a `Nfa` represent byte offsets.
20#[derive(Hash, Eq, PartialEq, PartialOrd, Ord, Copy, Clone)]
21pub(crate) struct State(u32);
22
23/// The transitions between states in a `Nfa` reflect bit validity.
24#[derive(Hash, Eq, PartialEq, Clone, Copy)]
25pub(crate) enum Transition<R>
26where
27    R: Ref,
28{
29    Byte(Byte),
30    Ref(R),
31}
32
33impl fmt::Debug for State {
34    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
35        write!(f, "S_{}", self.0)
36    }
37}
38
39impl<R> fmt::Debug for Transition<R>
40where
41    R: Ref,
42{
43    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
44        match &self {
45            Self::Byte(b) => b.fmt(f),
46            Self::Ref(r) => r.fmt(f),
47        }
48    }
49}
50
51impl<R> Nfa<R>
52where
53    R: Ref,
54{
55    pub(crate) fn unit() -> Self {
56        let transitions: Map<State, Map<Transition<R>, Set<State>>> = Map::default();
57        let start = State::new();
58        let accepting = start;
59
60        Nfa { transitions, start, accepting }
61    }
62
63    pub(crate) fn from_byte(byte: Byte) -> Self {
64        let mut transitions: Map<State, Map<Transition<R>, Set<State>>> = Map::default();
65        let start = State::new();
66        let accepting = State::new();
67
68        let source = transitions.entry(start).or_default();
69        let edge = source.entry(Transition::Byte(byte)).or_default();
70        edge.insert(accepting);
71
72        Nfa { transitions, start, accepting }
73    }
74
75    pub(crate) fn from_ref(r: R) -> Self {
76        let mut transitions: Map<State, Map<Transition<R>, Set<State>>> = Map::default();
77        let start = State::new();
78        let accepting = State::new();
79
80        let source = transitions.entry(start).or_default();
81        let edge = source.entry(Transition::Ref(r)).or_default();
82        edge.insert(accepting);
83
84        Nfa { transitions, start, accepting }
85    }
86
87    pub(crate) fn from_tree(tree: Tree<!, R>) -> Result<Self, Uninhabited> {
88        Ok(match tree {
89            Tree::Byte(b) => Self::from_byte(b),
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).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).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    #[allow(dead_code)]
164    pub(crate) fn edges_from(&self, start: State) -> Option<&Map<Transition<R>, Set<State>>> {
165        self.transitions.get(&start)
166    }
167}
168
169impl State {
170    pub(crate) fn new() -> Self {
171        static COUNTER: AtomicU32 = AtomicU32::new(0);
172        Self(COUNTER.fetch_add(1, Ordering::SeqCst))
173    }
174}
rustc_transmute/layout/nfa.rs

rustc_transmute/layout/
nfa.rs
