rustc_transmute/layout/
dfa.rs

Help
1use std::fmt;
2use std::sync::atomic::{AtomicU32, Ordering};
3
4use tracing::instrument;
5
6use super::{Byte, Nfa, Ref, nfa};
7use crate::Map;
8
9#[derive(PartialEq, Clone, Debug)]
10pub(crate) struct Dfa<R>
11where
12    R: Ref,
13{
14    pub(crate) transitions: Map<State, Transitions<R>>,
15    pub(crate) start: State,
16    pub(crate) accepting: State,
17}
18
19#[derive(PartialEq, Clone, Debug)]
20pub(crate) struct Transitions<R>
21where
22    R: Ref,
23{
24    byte_transitions: Map<Byte, State>,
25    ref_transitions: Map<R, State>,
26}
27
28impl<R> Default for Transitions<R>
29where
30    R: Ref,
31{
32    fn default() -> Self {
33        Self { byte_transitions: Map::default(), ref_transitions: Map::default() }
34    }
35}
36
37impl<R> Transitions<R>
38where
39    R: Ref,
40{
41    #[allow(dead_code)]
42    fn insert(&mut self, transition: Transition<R>, state: State) {
43        match transition {
44            Transition::Byte(b) => {
45                self.byte_transitions.insert(b, state);
46            }
47            Transition::Ref(r) => {
48                self.ref_transitions.insert(r, state);
49            }
50        }
51    }
52}
53
54/// The states in a `Nfa` represent byte offsets.
55#[derive(Hash, Eq, PartialEq, PartialOrd, Ord, Copy, Clone)]
56pub(crate) struct State(u32);
57
58#[derive(Hash, Eq, PartialEq, Clone, Copy)]
59pub(crate) enum Transition<R>
60where
61    R: Ref,
62{
63    Byte(Byte),
64    Ref(R),
65}
66
67impl fmt::Debug for State {
68    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
69        write!(f, "S_{}", self.0)
70    }
71}
72
73impl<R> fmt::Debug for Transition<R>
74where
75    R: Ref,
76{
77    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
78        match &self {
79            Self::Byte(b) => b.fmt(f),
80            Self::Ref(r) => r.fmt(f),
81        }
82    }
83}
84
85impl<R> Dfa<R>
86where
87    R: Ref,
88{
89    #[allow(dead_code)]
90    pub(crate) fn unit() -> Self {
91        let transitions: Map<State, Transitions<R>> = Map::default();
92        let start = State::new();
93        let accepting = start;
94
95        Self { transitions, start, accepting }
96    }
97
98    #[cfg(test)]
99    pub(crate) fn bool() -> Self {
100        let mut transitions: Map<State, Transitions<R>> = Map::default();
101        let start = State::new();
102        let accepting = State::new();
103
104        transitions.entry(start).or_default().insert(Transition::Byte(Byte::Init(0x00)), accepting);
105
106        transitions.entry(start).or_default().insert(Transition::Byte(Byte::Init(0x01)), accepting);
107
108        Self { transitions, start, accepting }
109    }
110
111    #[instrument(level = "debug")]
112    pub(crate) fn from_nfa(nfa: Nfa<R>) -> Self {
113        let Nfa { transitions: nfa_transitions, start: nfa_start, accepting: nfa_accepting } = nfa;
114
115        let mut dfa_transitions: Map<State, Transitions<R>> = Map::default();
116        let mut nfa_to_dfa: Map<nfa::State, State> = Map::default();
117        let dfa_start = State::new();
118        nfa_to_dfa.insert(nfa_start, dfa_start);
119
120        let mut queue = vec![(nfa_start, dfa_start)];
121
122        while let Some((nfa_state, dfa_state)) = queue.pop() {
123            if nfa_state == nfa_accepting {
124                continue;
125            }
126
127            for (nfa_transition, next_nfa_states) in nfa_transitions[&nfa_state].iter() {
128                let dfa_transitions =
129                    dfa_transitions.entry(dfa_state).or_insert_with(Default::default);
130
131                let mapped_state = next_nfa_states.iter().find_map(|x| nfa_to_dfa.get(x).copied());
132
133                let next_dfa_state = match nfa_transition {
134                    &nfa::Transition::Byte(b) => *dfa_transitions
135                        .byte_transitions
136                        .entry(b)
137                        .or_insert_with(|| mapped_state.unwrap_or_else(State::new)),
138                    &nfa::Transition::Ref(r) => *dfa_transitions
139                        .ref_transitions
140                        .entry(r)
141                        .or_insert_with(|| mapped_state.unwrap_or_else(State::new)),
142                };
143
144                for &next_nfa_state in next_nfa_states {
145                    nfa_to_dfa.entry(next_nfa_state).or_insert_with(|| {
146                        queue.push((next_nfa_state, next_dfa_state));
147                        next_dfa_state
148                    });
149                }
150            }
151        }
152
153        let dfa_accepting = nfa_to_dfa[&nfa_accepting];
154
155        Self { transitions: dfa_transitions, start: dfa_start, accepting: dfa_accepting }
156    }
157
158    pub(crate) fn bytes_from(&self, start: State) -> Option<&Map<Byte, State>> {
159        Some(&self.transitions.get(&start)?.byte_transitions)
160    }
161
162    pub(crate) fn byte_from(&self, start: State, byte: Byte) -> Option<State> {
163        self.transitions.get(&start)?.byte_transitions.get(&byte).copied()
164    }
165
166    pub(crate) fn refs_from(&self, start: State) -> Option<&Map<R, State>> {
167        Some(&self.transitions.get(&start)?.ref_transitions)
168    }
169}
170
171impl State {
172    pub(crate) fn new() -> Self {
173        static COUNTER: AtomicU32 = AtomicU32::new(0);
174        Self(COUNTER.fetch_add(1, Ordering::SeqCst))
175    }
176}
177
178impl<R> From<nfa::Transition<R>> for Transition<R>
179where
180    R: Ref,
181{
182    fn from(nfa_transition: nfa::Transition<R>) -> Self {
183        match nfa_transition {
184            nfa::Transition::Byte(byte) => Transition::Byte(byte),
185            nfa::Transition::Ref(r) => Transition::Ref(r),
186        }
187    }
188}
rustc_transmute/layout/dfa.rs

rustc_transmute/layout/
dfa.rs
