Skip to main content

triblespace_paths/
automaton.rs

1use std::collections::BTreeSet;
2use std::error::Error;
3use std::fmt;
4
5use triblespace_core::id::RawId;
6
7/// Dense state number in a fixed automaton.
8pub type StateId = u32;
9
10/// One epsilon-free property-path step.
11///
12/// Empty exclusion lists are wildcards. Exclusion lists are sorted and
13/// deduplicated by [`Automaton::new`].
14#[derive(Clone, Debug, Eq, PartialEq, Ord, PartialOrd)]
15pub enum Step {
16    /// Follow an edge with exactly this attribute.
17    Forward(RawId),
18    /// Follow an edge with exactly this attribute in reverse.
19    Reverse(RawId),
20    /// Follow any forward edge except the listed attributes.
21    ForwardExcept(Vec<RawId>),
22    /// Follow any reverse edge except the listed attributes.
23    ReverseExcept(Vec<RawId>),
24}
25
26impl Step {
27    /// Matches every forward edge.
28    pub fn forward_any() -> Self {
29        Self::ForwardExcept(Vec::new())
30    }
31
32    /// Matches every reverse edge.
33    pub fn reverse_any() -> Self {
34        Self::ReverseExcept(Vec::new())
35    }
36
37    fn canonicalize(&mut self) {
38        let excluded = match self {
39            Self::ForwardExcept(excluded) | Self::ReverseExcept(excluded) => excluded,
40            Self::Forward(_) | Self::Reverse(_) => return,
41        };
42        excluded.sort_unstable();
43        excluded.dedup();
44    }
45
46    pub(crate) fn matches(&self, attribute: &RawId) -> bool {
47        match self {
48            Self::Forward(expected) | Self::Reverse(expected) => expected == attribute,
49            Self::ForwardExcept(excluded) | Self::ReverseExcept(excluded) => {
50                excluded.binary_search(attribute).is_err()
51            }
52        }
53    }
54
55    pub(crate) fn is_reverse(&self) -> bool {
56        matches!(self, Self::Reverse(_) | Self::ReverseExcept(_))
57    }
58}
59
60/// A labeled transition between two automaton states.
61#[derive(Clone, Debug, Eq, PartialEq, Ord, PartialOrd)]
62pub struct Transition {
63    /// Source state.
64    pub from: StateId,
65    /// Destination state.
66    pub to: StateId,
67    /// Graph step consumed by the transition.
68    pub step: Step,
69}
70
71impl Transition {
72    /// Creates one transition.
73    pub fn new(from: StateId, to: StateId, step: Step) -> Self {
74        Self { from, to, step }
75    }
76}
77
78/// A canonical fixed, epsilon-free nondeterministic automaton.
79///
80/// Epsilon behavior belongs in the compiler: nullable expressions accept an
81/// initial state, and epsilon transitions are eliminated before construction.
82#[derive(Clone, Debug, Eq, PartialEq)]
83pub struct Automaton {
84    state_count: StateId,
85    initial: BTreeSet<StateId>,
86    accepting: BTreeSet<StateId>,
87    transitions: Vec<Transition>,
88}
89
90/// Invalid fixed-automaton description.
91#[derive(Clone, Debug, Eq, PartialEq)]
92pub enum AutomatonError {
93    /// An automaton needs at least one state.
94    NoStates,
95    /// An automaton needs at least one initial state.
96    NoInitialState,
97    /// A referenced state lies outside `0..state_count`.
98    StateOutOfRange {
99        /// Invalid state.
100        state: StateId,
101        /// Exclusive state bound.
102        state_count: StateId,
103    },
104}
105
106impl fmt::Display for AutomatonError {
107    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
108        match self {
109            Self::NoStates => write!(f, "an automaton needs at least one state"),
110            Self::NoInitialState => write!(f, "an automaton needs an initial state"),
111            Self::StateOutOfRange { state, state_count } => {
112                write!(f, "automaton state {state} is outside 0..{state_count}")
113            }
114        }
115    }
116}
117
118impl Error for AutomatonError {}
119
120impl Automaton {
121    /// Validates and canonicalizes a fixed automaton.
122    pub fn new(
123        state_count: StateId,
124        initial: impl IntoIterator<Item = StateId>,
125        accepting: impl IntoIterator<Item = StateId>,
126        transitions: impl IntoIterator<Item = Transition>,
127    ) -> Result<Self, AutomatonError> {
128        if state_count == 0 {
129            return Err(AutomatonError::NoStates);
130        }
131
132        let initial = initial.into_iter().collect::<BTreeSet<_>>();
133        if initial.is_empty() {
134            return Err(AutomatonError::NoInitialState);
135        }
136        let accepting = accepting.into_iter().collect::<BTreeSet<_>>();
137        let mut transitions = transitions.into_iter().collect::<Vec<_>>();
138
139        for state in initial.iter().chain(&accepting).copied().chain(
140            transitions
141                .iter()
142                .flat_map(|transition| [transition.from, transition.to]),
143        ) {
144            if state >= state_count {
145                return Err(AutomatonError::StateOutOfRange { state, state_count });
146            }
147        }
148
149        for transition in &mut transitions {
150            transition.step.canonicalize();
151        }
152        transitions.sort_unstable();
153        transitions.dedup();
154
155        Ok(Self {
156            state_count,
157            initial,
158            accepting,
159            transitions,
160        })
161    }
162
163    /// Number of states, exactly `0..state_count`.
164    pub fn state_count(&self) -> StateId {
165        self.state_count
166    }
167
168    /// Canonically ordered initial states.
169    pub fn initial_states(&self) -> impl Iterator<Item = StateId> + '_ {
170        self.initial.iter().copied()
171    }
172
173    /// Canonically ordered accepting states.
174    pub fn accepting_states(&self) -> impl Iterator<Item = StateId> + '_ {
175        self.accepting.iter().copied()
176    }
177
178    /// Whether the automaton accepts the empty path.
179    ///
180    /// The automaton is epsilon-free, so this is exactly the overlap between
181    /// its initial and accepting state sets.
182    pub fn accepts_empty(&self) -> bool {
183        self.initial
184            .iter()
185            .any(|state| self.accepting.contains(state))
186    }
187
188    /// Whether `state` accepts a completed path.
189    pub fn is_accepting(&self, state: StateId) -> bool {
190        self.accepting.contains(&state)
191    }
192
193    /// Canonically ordered, duplicate-free transitions.
194    pub fn transitions(&self) -> &[Transition] {
195        &self.transitions
196    }
197}