1use std::cmp::Ordering;
2use std::collections::BTreeSet;
3
4use crate::{Automaton, StateId, Step, Transition};
5
6#[derive(Clone, Debug, Eq, PartialEq)]
29pub struct PathExpr {
30 node: Node,
31}
32
33#[derive(Clone, Debug, Eq, PartialEq)]
34enum Node {
35 Atom(Step),
36 Sequence(Vec<PathExpr>),
37 Alternative(Vec<PathExpr>),
38 Star(Box<PathExpr>),
39 Plus(Box<PathExpr>),
40 Optional(Box<PathExpr>),
41}
42
43const TAG_ATOM: u8 = 0;
47const TAG_SEQUENCE: u8 = 1;
48const TAG_ALTERNATIVE: u8 = 2;
49const TAG_STAR: u8 = 3;
50const TAG_PLUS: u8 = 4;
51const TAG_OPTIONAL: u8 = 5;
52
53fn node_tag(node: &Node) -> u8 {
54 match node {
55 Node::Atom(_) => TAG_ATOM,
56 Node::Sequence(_) => TAG_SEQUENCE,
57 Node::Alternative(_) => TAG_ALTERNATIVE,
58 Node::Star(_) => TAG_STAR,
59 Node::Plus(_) => TAG_PLUS,
60 Node::Optional(_) => TAG_OPTIONAL,
61 }
62}
63
64fn step_tag(step: &Step) -> u8 {
65 match step {
66 Step::Forward(_) => 0,
67 Step::Reverse(_) => 1,
68 Step::ForwardExcept(_) => 2,
69 Step::ReverseExcept(_) => 3,
70 }
71}
72
73fn cmp_steps(left: &Step, right: &Step) -> Ordering {
74 step_tag(left)
75 .cmp(&step_tag(right))
76 .then_with(|| match (left, right) {
77 (Step::Forward(left), Step::Forward(right))
78 | (Step::Reverse(left), Step::Reverse(right)) => left.cmp(right),
79 (Step::ForwardExcept(left), Step::ForwardExcept(right))
80 | (Step::ReverseExcept(left), Step::ReverseExcept(right)) => left.cmp(right),
81 _ => Ordering::Equal,
82 })
83}
84
85impl Ord for PathExpr {
86 fn cmp(&self, other: &Self) -> Ordering {
87 node_tag(&self.node)
88 .cmp(&node_tag(&other.node))
89 .then_with(|| match (&self.node, &other.node) {
90 (Node::Atom(left), Node::Atom(right)) => cmp_steps(left, right),
91 (Node::Sequence(left), Node::Sequence(right))
92 | (Node::Alternative(left), Node::Alternative(right)) => left.cmp(right),
93 (Node::Star(left), Node::Star(right))
94 | (Node::Plus(left), Node::Plus(right))
95 | (Node::Optional(left), Node::Optional(right)) => left.cmp(right),
96 _ => Ordering::Equal,
97 })
98 }
99}
100
101impl PartialOrd for PathExpr {
102 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
103 Some(self.cmp(other))
104 }
105}
106
107impl From<Step> for PathExpr {
108 fn from(step: Step) -> Self {
109 Self {
110 node: Node::Atom(canonical_step(step)),
111 }
112 }
113}
114
115impl PathExpr {
116 #[must_use]
120 pub fn then(self, next: impl Into<Self>) -> Self {
121 Self::sequence([self, next.into()])
122 }
123
124 #[must_use]
129 pub fn or(self, alternative: impl Into<Self>) -> Self {
130 Self::alternative([self, alternative.into()])
131 }
132
133 #[must_use]
135 pub fn star(self) -> Self {
136 Self {
137 node: Node::Star(Box::new(self)),
138 }
139 }
140
141 #[must_use]
143 pub fn plus(self) -> Self {
144 Self {
145 node: Node::Plus(Box::new(self)),
146 }
147 }
148
149 #[must_use]
151 pub fn optional(self) -> Self {
152 Self {
153 node: Node::Optional(Box::new(self)),
154 }
155 }
156
157 #[must_use]
162 pub fn inverse(self) -> Self {
163 match self.node {
164 Node::Atom(step) => canonical_step(inverse_step(step)).into(),
165 Node::Sequence(parts) => Self::sequence(parts.into_iter().rev().map(Self::inverse)),
166 Node::Alternative(arms) => Self::alternative(arms.into_iter().map(Self::inverse)),
167 Node::Star(body) => body.inverse().star(),
168 Node::Plus(body) => body.inverse().plus(),
169 Node::Optional(body) => body.inverse().optional(),
170 }
171 }
172
173 pub fn is_nullable(&self) -> bool {
175 match &self.node {
176 Node::Atom(_) => false,
177 Node::Sequence(parts) => parts.iter().all(Self::is_nullable),
178 Node::Alternative(arms) => arms.iter().any(Self::is_nullable),
179 Node::Star(_) | Node::Optional(_) => true,
180 Node::Plus(body) => body.is_nullable(),
181 }
182 }
183
184 pub fn compile(&self) -> Automaton {
198 let mut compiler = PositionCompiler::default();
199 let fragment = compiler.analyze(self);
200 let position_count = compiler.steps.len();
201 let state_count = position_count
202 .checked_add(1)
203 .and_then(|count| StateId::try_from(count).ok())
204 .expect("path expression exceeds the u32 automaton state space");
205
206 let mut transitions = Vec::new();
207 for position in &fragment.first {
208 transitions.push(Transition::new(
209 0,
210 *position,
211 compiler.step(*position).clone(),
212 ));
213 }
214 for (from, targets) in compiler.follow.iter().enumerate() {
215 let from = StateId::try_from(from + 1).expect("position checked above");
216 for to in targets {
217 transitions.push(Transition::new(from, *to, compiler.step(*to).clone()));
218 }
219 }
220
221 let mut accepting = fragment.last;
222 if fragment.nullable {
223 accepting.insert(0);
224 }
225 Automaton::new(state_count, [0], accepting, transitions)
226 .expect("the position construction emits a valid fixed automaton")
227 }
228
229 fn sequence(parts: impl IntoIterator<Item = Self>) -> Self {
230 let mut flattened = Vec::new();
231 for part in parts {
232 match part.node {
233 Node::Sequence(nested) => flattened.extend(nested),
234 node => flattened.push(Self { node }),
235 }
236 }
237 debug_assert!(!flattened.is_empty());
238 if flattened.len() == 1 {
239 flattened.pop().expect("checked length")
240 } else {
241 Self {
242 node: Node::Sequence(flattened),
243 }
244 }
245 }
246
247 fn alternative(arms: impl IntoIterator<Item = Self>) -> Self {
248 let mut flattened = Vec::new();
249 for arm in arms {
250 match arm.node {
251 Node::Alternative(nested) => flattened.extend(nested),
252 node => flattened.push(Self { node }),
253 }
254 }
255 flattened.sort_unstable();
256 flattened.dedup();
257 debug_assert!(!flattened.is_empty());
258 if flattened.len() == 1 {
259 flattened.pop().expect("checked length")
260 } else {
261 Self {
262 node: Node::Alternative(flattened),
263 }
264 }
265 }
266}
267
268fn canonical_step(step: Step) -> Step {
269 match step {
270 Step::ForwardExcept(mut excluded) => {
271 excluded.sort_unstable();
272 excluded.dedup();
273 Step::ForwardExcept(excluded)
274 }
275 Step::ReverseExcept(mut excluded) => {
276 excluded.sort_unstable();
277 excluded.dedup();
278 Step::ReverseExcept(excluded)
279 }
280 step @ (Step::Forward(_) | Step::Reverse(_)) => step,
281 }
282}
283
284fn inverse_step(step: Step) -> Step {
285 match step {
286 Step::Forward(attribute) => Step::Reverse(attribute),
287 Step::Reverse(attribute) => Step::Forward(attribute),
288 Step::ForwardExcept(excluded) => Step::ReverseExcept(excluded),
289 Step::ReverseExcept(excluded) => Step::ForwardExcept(excluded),
290 }
291}
292
293#[derive(Default)]
294struct PositionCompiler {
295 steps: Vec<Step>,
296 follow: Vec<BTreeSet<StateId>>,
297}
298
299struct Fragment {
300 nullable: bool,
301 first: BTreeSet<StateId>,
302 last: BTreeSet<StateId>,
303}
304
305impl PositionCompiler {
306 fn analyze(&mut self, expression: &PathExpr) -> Fragment {
307 match &expression.node {
308 Node::Atom(step) => {
309 let position = StateId::try_from(self.steps.len() + 1)
310 .expect("path expression exceeds the u32 automaton state space");
311 self.steps.push(step.clone());
312 self.follow.push(BTreeSet::new());
313 Fragment {
314 nullable: false,
315 first: BTreeSet::from([position]),
316 last: BTreeSet::from([position]),
317 }
318 }
319 Node::Sequence(parts) => {
320 let mut parts = parts.iter();
321 let mut result =
322 self.analyze(parts.next().expect("canonical sequence is nonempty"));
323 for part in parts {
324 let right = self.analyze(part);
325 self.link(&result.last, &right.first);
326
327 let mut first = result.first;
328 if result.nullable {
329 first.extend(right.first.iter().copied());
330 }
331 let mut last = right.last;
332 if right.nullable {
333 last.extend(result.last.iter().copied());
334 }
335 result = Fragment {
336 nullable: result.nullable && right.nullable,
337 first,
338 last,
339 };
340 }
341 result
342 }
343 Node::Alternative(arms) => {
344 let mut nullable = false;
345 let mut first = BTreeSet::new();
346 let mut last = BTreeSet::new();
347 for arm in arms {
348 let fragment = self.analyze(arm);
349 nullable |= fragment.nullable;
350 first.extend(fragment.first);
351 last.extend(fragment.last);
352 }
353 Fragment {
354 nullable,
355 first,
356 last,
357 }
358 }
359 Node::Star(body) => {
360 let fragment = self.analyze(body);
361 self.link(&fragment.last, &fragment.first);
362 Fragment {
363 nullable: true,
364 ..fragment
365 }
366 }
367 Node::Plus(body) => {
368 let fragment = self.analyze(body);
369 self.link(&fragment.last, &fragment.first);
370 fragment
371 }
372 Node::Optional(body) => {
373 let fragment = self.analyze(body);
374 Fragment {
375 nullable: true,
376 ..fragment
377 }
378 }
379 }
380 }
381
382 fn link(&mut self, from: &BTreeSet<StateId>, to: &BTreeSet<StateId>) {
383 for &source in from {
384 self.follow[source as usize - 1].extend(to.iter().copied());
385 }
386 }
387
388 fn step(&self, position: StateId) -> &Step {
389 &self.steps[position as usize - 1]
390 }
391}
392
393#[cfg(test)]
394mod tests {
395 use super::*;
396
397 type Token = (bool, [u8; 16]);
398
399 fn label(byte: u8) -> [u8; 16] {
400 [byte; 16]
401 }
402
403 fn atom(byte: u8) -> PathExpr {
404 Step::Forward(label(byte)).into()
405 }
406
407 fn step_matches(step: &Step, token: Token) -> bool {
408 step.is_reverse() == token.0 && step.matches(&token.1)
409 }
410
411 fn direct_ends(expression: &PathExpr, word: &[Token], start: usize) -> BTreeSet<usize> {
412 match &expression.node {
413 Node::Atom(step) => {
414 if word
415 .get(start)
416 .is_some_and(|&token| step_matches(step, token))
417 {
418 BTreeSet::from([start + 1])
419 } else {
420 BTreeSet::new()
421 }
422 }
423 Node::Sequence(parts) => {
424 let mut positions = BTreeSet::from([start]);
425 for part in parts {
426 positions = positions
427 .into_iter()
428 .flat_map(|position| direct_ends(part, word, position))
429 .collect();
430 }
431 positions
432 }
433 Node::Alternative(arms) => arms
434 .iter()
435 .flat_map(|arm| direct_ends(arm, word, start))
436 .collect(),
437 Node::Star(body) => repeat_ends(body, word, start, true),
438 Node::Plus(body) => repeat_ends(body, word, start, false),
439 Node::Optional(body) => {
440 let mut ends = direct_ends(body, word, start);
441 ends.insert(start);
442 ends
443 }
444 }
445 }
446
447 fn repeat_ends(
448 body: &PathExpr,
449 word: &[Token],
450 start: usize,
451 include_empty: bool,
452 ) -> BTreeSet<usize> {
453 let mut result = if include_empty {
454 BTreeSet::from([start])
455 } else {
456 BTreeSet::new()
457 };
458 let mut frontier = direct_ends(body, word, start);
459 while let Some(position) = frontier.pop_first() {
460 if result.insert(position) {
461 frontier.extend(direct_ends(body, word, position));
462 }
463 }
464 result
465 }
466
467 fn automaton_accepts(automaton: &Automaton, word: &[Token]) -> bool {
468 let mut active = automaton.initial_states().collect::<BTreeSet<_>>();
469 for &token in word {
470 active = automaton
471 .transitions()
472 .iter()
473 .filter(|transition| {
474 active.contains(&transition.from) && step_matches(&transition.step, token)
475 })
476 .map(|transition| transition.to)
477 .collect();
478 }
479 active
480 .into_iter()
481 .any(|state| automaton.is_accepting(state))
482 }
483
484 fn words(alphabet: &[Token], max_len: usize) -> Vec<Vec<Token>> {
485 let mut words = vec![Vec::new()];
486 let mut frontier = vec![Vec::new()];
487 for _ in 0..max_len {
488 frontier = frontier
489 .iter()
490 .flat_map(|prefix| {
491 alphabet.iter().map(move |&token| {
492 let mut word = prefix.clone();
493 word.push(token);
494 word
495 })
496 })
497 .collect();
498 words.extend(frontier.iter().cloned());
499 }
500 words
501 }
502
503 #[test]
504 fn exhaustive_small_expressions_match_the_direct_word_oracle() {
505 let base = vec![
506 atom(1),
507 atom(2),
508 PathExpr::from(Step::Reverse(label(1))),
509 PathExpr::from(Step::ForwardExcept(vec![label(2)])),
510 PathExpr::from(Step::ReverseExcept(vec![label(1)])),
511 PathExpr::from(Step::forward_any()),
512 PathExpr::from(Step::reverse_any()),
513 ];
514 let mut expressions = base.iter().cloned().collect::<BTreeSet<_>>();
515 for body in &base {
516 expressions.extend([
517 body.clone().star(),
518 body.clone().plus(),
519 body.clone().optional(),
520 body.clone().inverse(),
521 ]);
522 }
523 for left in &base {
524 for right in &base {
525 expressions.insert(left.clone().then(right.clone()));
526 expressions.insert(left.clone().or(right.clone()));
527 }
528 }
529 let first_layer = expressions.iter().cloned().collect::<Vec<_>>();
530 for expression in &first_layer {
531 expressions.extend([
532 expression.clone().star(),
533 expression.clone().plus(),
534 expression.clone().optional(),
535 expression.clone().inverse(),
536 ]);
537 for right in &base {
538 expressions.insert(expression.clone().then(right.clone()));
539 expressions.insert(right.clone().then(expression.clone()));
540 expressions.insert(expression.clone().or(right.clone()));
541 }
542 }
543
544 let alphabet = [
545 (false, label(1)),
546 (false, label(2)),
547 (true, label(1)),
548 (true, label(2)),
549 ];
550 let words = words(&alphabet, 3);
551 for (expression_index, expression) in expressions.iter().enumerate() {
552 let automaton = expression.compile();
553 assert_eq!(expression.is_nullable(), automaton.is_accepting(0));
554 for word in &words {
555 assert_eq!(
556 automaton_accepts(&automaton, word),
557 direct_ends(expression, word, 0).contains(&word.len()),
558 "expression {expression_index}: {expression:?}, word {word:?}"
559 );
560 }
561 }
562 }
563
564 #[test]
565 fn repeated_sequence_completes_a_second_cycle() {
566 let expression = atom(1).then(atom(2)).star();
567 let word = [
568 (false, label(1)),
569 (false, label(2)),
570 (false, label(1)),
571 (false, label(2)),
572 ];
573
574 assert!(direct_ends(&expression, &word, 0).contains(&word.len()));
575 assert!(automaton_accepts(&expression.compile(), &word));
576 }
577
578 #[test]
579 fn canonical_builders_stabilize_structure_and_automata() {
580 let a = atom(1);
581 let b = atom(2);
582 let c = atom(3);
583
584 assert_eq!(
585 a.clone().then(b.clone()).then(c.clone()),
586 a.clone().then(b.clone().then(c.clone()))
587 );
588 assert_eq!(
589 a.clone().or(b.clone()).or(a.clone()).or(c.clone()),
590 c.clone().or(b.clone().or(a.clone()))
591 );
592 assert_eq!(
593 PathExpr::from(Step::ForwardExcept(vec![label(2), label(1), label(1)])),
594 PathExpr::from(Step::ForwardExcept(vec![label(1), label(2)]))
595 );
596
597 let left = a.clone().or(b.clone()).or(a.clone()).compile();
598 let right = b.or(a).compile();
599 assert_eq!(left, right);
600 assert_eq!(
601 crate::automaton_fingerprint(&left),
602 crate::automaton_fingerprint(&right)
603 );
604 }
605
606 #[test]
607 fn inverse_is_an_involution_and_reverses_sequences() {
608 let expression = atom(1)
609 .then(atom(2).optional())
610 .or(PathExpr::from(Step::ForwardExcept(vec![label(3)])).plus());
611 assert_eq!(expression.clone().inverse().inverse(), expression);
612
613 let forward = atom(1).then(atom(2));
614 let expected =
615 PathExpr::from(Step::Reverse(label(2))).then(PathExpr::from(Step::Reverse(label(1))));
616 assert_eq!(forward.inverse(), expected);
617 }
618}