Skip to main content

triblespace_paths/
expr.rs

1use std::cmp::Ordering;
2use std::collections::BTreeSet;
3
4use crate::{Automaton, StateId, Step, Transition};
5
6/// A canonical regular expression over graph-property [`Step`]s.
7///
8/// Construction normalizes exclusion lists, flattens associative sequences,
9/// and flattens, sorts, and deduplicates alternatives. This is structural
10/// canonicalization, not full language minimization: distributively equivalent
11/// expressions may still compile to different (but language-equivalent)
12/// automata. The durable alternative order is atom, sequence, alternative,
13/// star, plus, optional; atom kinds are forward, reverse, forward-except,
14/// reverse-except, with payloads ordered lexicographically.
15///
16/// ```
17/// use triblespace_paths::{PathExpr, Step};
18///
19/// let parent = [1; 16];
20/// let sibling = [2; 16];
21/// let expression = PathExpr::from(Step::Forward(parent))
22///     .plus()
23///     .or(PathExpr::from(Step::Forward(sibling)).inverse());
24/// let automaton = expression.compile();
25///
26/// assert_eq!(automaton.initial_states().collect::<Vec<_>>(), vec![0]);
27/// ```
28#[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
43// This order is part of PathExpr's canonical form. Keep the explicit tags
44// stable: changing source enum order must not perturb alternative order or the
45// automaton fingerprint produced by `compile`.
46const 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    /// Concatenates this expression with `next`.
117    ///
118    /// Nested sequences are flattened without reordering their operands.
119    #[must_use]
120    pub fn then(self, next: impl Into<Self>) -> Self {
121        Self::sequence([self, next.into()])
122    }
123
124    /// Forms the set union of this expression and `alternative`.
125    ///
126    /// Nested alternatives are flattened, sorted by an explicit stable node
127    /// order, and deduplicated.
128    #[must_use]
129    pub fn or(self, alternative: impl Into<Self>) -> Self {
130        Self::alternative([self, alternative.into()])
131    }
132
133    /// Matches zero or more repetitions of this expression.
134    #[must_use]
135    pub fn star(self) -> Self {
136        Self {
137            node: Node::Star(Box::new(self)),
138        }
139    }
140
141    /// Matches one or more repetitions of this expression.
142    #[must_use]
143    pub fn plus(self) -> Self {
144        Self {
145            node: Node::Plus(Box::new(self)),
146        }
147    }
148
149    /// Matches this expression zero or one time.
150    #[must_use]
151    pub fn optional(self) -> Self {
152        Self {
153            node: Node::Optional(Box::new(self)),
154        }
155    }
156
157    /// Reverses path direction.
158    ///
159    /// Inversion flips every atomic step, reverses sequence order, distributes
160    /// through alternatives, and preserves repetition operators.
161    #[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    /// Whether this expression accepts the empty path.
174    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    /// Compiles to a fixed epsilon-free position automaton.
185    ///
186    /// Atomic occurrences are numbered deterministically in canonical-tree
187    /// order. State zero is the sole initial state; every other state denotes
188    /// the most recently consumed atomic occurrence. The construction is
189    /// output-sensitive in the expression and generated `follow` relation;
190    /// ordered-set maintenance may add logarithmic factors. It introduces no
191    /// epsilon transitions or determinization step.
192    ///
193    /// # Panics
194    ///
195    /// Panics if the expression contains `u32::MAX` atomic occurrences. Such
196    /// an expression cannot be represented by [`StateId`].
197    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}