uqa_graph/
rpq.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Regular path automata: algebraic simplification, Thompson NFA, and
8//! subset-construction DFA over the shared Core syntax. Together these power the
9//! `RegularPathQuery` operator (see [`crate::operators`]).
10//!
11//! Grammar:
12//! ```text
13//!     atom        := label | '(' alternation ')'
14//!     star        := atom ('*' | '{' int ',' int '}')*
15//!     concat      := star ('/' star)*
16//!     alternation := concat ('|' concat)*
17//! ```
18//! Precedence (low to high): alternation, concatenation, star.
19
20use std::collections::{BTreeMap, BTreeSet, VecDeque};
21
22pub use uqa_core::rpq::{parse_rpq, RPQParseError, RegularPathExpr};
23
24/// Hard limits keep user-provided path expressions from turning NFA or DFA
25/// compilation into an unbounded memory allocation. They are deliberately
26/// independent: a compact NFA can still have an exponential DFA.
27pub const MAX_RPQ_AST_DEPTH: usize = 256;
28pub const MAX_NFA_STATES: usize = 16_384;
29pub const MAX_DFA_STATES: usize = 16_384;
30
31#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
32pub enum RPQBuildError {
33    #[error("bounded repetition minimum {min} exceeds maximum {max}")]
34    InvalidBound { min: u32, max: u32 },
35    #[error("regular path expression depth {depth} exceeds limit {limit}")]
36    ExpressionTooDeep { depth: usize, limit: usize },
37    #[error("regular path NFA requires {required} states, exceeding limit {limit}")]
38    NfaStateLimitExceeded { required: usize, limit: usize },
39    #[error("regular path DFA exceeded state limit {limit}")]
40    DfaStateLimitExceeded { limit: usize },
41    #[error("invalid NFA: {0}")]
42    InvalidNfa(String),
43    #[error("unable to reserve memory for {states} NFA states")]
44    AllocationFailed { states: usize },
45}
46
47// -------------------------------------------------------------------------
48// Simplifier
49// -------------------------------------------------------------------------
50
51/// Algebraic simplification (Section 8.2, Paper 2):
52/// `a|a -> a`, `(a*)* -> a*`, `a*|a -> a*`, `a*/a* -> a*`, plus
53/// canonicalization of alternation operand order.
54pub fn simplify(expr: &RegularPathExpr) -> Result<RegularPathExpr, RPQBuildError> {
55    // Validate iteratively before entering the recursive rewriter so a
56    // programmatically constructed, deeply nested AST cannot overflow the
57    // stack before the compiler has a chance to reject it.
58    required_nfa_states(expr)?;
59    Ok(simplify_validated(expr))
60}
61
62fn simplify_validated(expr: &RegularPathExpr) -> RegularPathExpr {
63    match expr {
64        RegularPathExpr::Label(_) => expr.clone(),
65        RegularPathExpr::Alternation(l, r) => {
66            let mut left = simplify_validated(l);
67            let mut right = simplify_validated(r);
68            if left == right {
69                return left;
70            }
71            if let RegularPathExpr::KleeneStar(inner) = &left {
72                if **inner == right {
73                    return left;
74                }
75            }
76            if let RegularPathExpr::KleeneStar(inner) = &right {
77                if **inner == left {
78                    return right;
79                }
80            }
81            // Canonical: sort by debug repr.
82            let lr = format!("{left:?}");
83            let rr = format!("{right:?}");
84            if lr > rr {
85                std::mem::swap(&mut left, &mut right);
86            }
87            RegularPathExpr::alt(left, right)
88        }
89        RegularPathExpr::Concat(l, r) => {
90            let left = simplify_validated(l);
91            let right = simplify_validated(r);
92            if let (RegularPathExpr::KleeneStar(li), RegularPathExpr::KleeneStar(ri)) =
93                (&left, &right)
94            {
95                if li == ri {
96                    return left;
97                }
98            }
99            RegularPathExpr::concat(left, right)
100        }
101        RegularPathExpr::KleeneStar(inner) => {
102            let s = simplify_validated(inner);
103            if matches!(s, RegularPathExpr::KleeneStar(_)) {
104                s
105            } else {
106                RegularPathExpr::star(s)
107            }
108        }
109        RegularPathExpr::Bounded { inner, min, max } => {
110            RegularPathExpr::bounded(simplify_validated(inner), *min, *max)
111        }
112    }
113}
114
115// -------------------------------------------------------------------------
116// NFA (Thompson's construction)
117// -------------------------------------------------------------------------
118
119pub type StateId = u32;
120
121/// NFA transition target. `Some(label)` is a labeled edge consumed by
122/// matching that label; `None` is an epsilon transition.
123#[derive(Debug, Clone)]
124pub struct NfaTransition {
125    pub label: Option<String>,
126    pub target: StateId,
127}
128
129#[derive(Debug, Default)]
130pub struct Nfa {
131    /// `transitions[state_id]` lists every outgoing transition from that
132    /// state. Indexed densely; unused state ids hold an empty vec.
133    pub transitions: Vec<Vec<NfaTransition>>,
134    pub start: StateId,
135    pub accept: StateId,
136}
137
138impl Nfa {
139    fn new() -> Self {
140        Self {
141            transitions: Vec::new(),
142            start: 0,
143            accept: 0,
144        }
145    }
146
147    fn new_state(&mut self) -> Result<StateId, RPQBuildError> {
148        if self.transitions.len() >= MAX_NFA_STATES {
149            return Err(RPQBuildError::NfaStateLimitExceeded {
150                required: self.transitions.len().saturating_add(1),
151                limit: MAX_NFA_STATES,
152            });
153        }
154        let id = StateId::try_from(self.transitions.len()).map_err(|_| {
155            RPQBuildError::NfaStateLimitExceeded {
156                required: self.transitions.len().saturating_add(1),
157                limit: MAX_NFA_STATES,
158            }
159        })?;
160        self.transitions.push(Vec::new());
161        Ok(id)
162    }
163
164    fn add_transition(
165        &mut self,
166        from: StateId,
167        label: Option<String>,
168        to: StateId,
169    ) -> Result<(), RPQBuildError> {
170        if usize::try_from(to)
171            .ok()
172            .is_none_or(|target| target >= self.transitions.len())
173        {
174            return Err(RPQBuildError::InvalidNfa(format!(
175                "transition target {to} is outside {} states",
176                self.transitions.len()
177            )));
178        }
179        let state_count = self.transitions.len();
180        let transitions = self
181            .transitions
182            .get_mut(usize::try_from(from).map_err(|_| {
183                RPQBuildError::InvalidNfa(format!("transition source {from} is not addressable"))
184            })?)
185            .ok_or_else(|| {
186                RPQBuildError::InvalidNfa(format!(
187                    "transition source {from} is outside {state_count} states"
188                ))
189            })?;
190        transitions.push(NfaTransition { label, target: to });
191        Ok(())
192    }
193
194    pub fn states(&self) -> Result<Vec<StateId>, RPQBuildError> {
195        validate_nfa(self)?;
196        let end = StateId::try_from(self.transitions.len()).map_err(|_| {
197            RPQBuildError::NfaStateLimitExceeded {
198                required: self.transitions.len(),
199                limit: MAX_NFA_STATES,
200            }
201        })?;
202        Ok((0..end).collect())
203    }
204}
205
206/// Build an NFA from a regular path expression via Thompson's
207/// construction.
208pub fn build_nfa(expr: &RegularPathExpr) -> Result<Nfa, RPQBuildError> {
209    let required = required_nfa_states(expr)?;
210    let mut nfa = Nfa::new();
211    nfa.transitions
212        .try_reserve_exact(required)
213        .map_err(|_| RPQBuildError::AllocationFailed { states: required })?;
214    let (start, accept) = build_fragment(&mut nfa, expr)?;
215    nfa.start = start;
216    nfa.accept = accept;
217    Ok(nfa)
218}
219
220fn required_nfa_states(expr: &RegularPathExpr) -> Result<usize, RPQBuildError> {
221    let mut work = vec![(expr, 1_usize, false)];
222    let mut values = Vec::<usize>::new();
223    while let Some((current, depth, visited)) = work.pop() {
224        if depth > MAX_RPQ_AST_DEPTH {
225            return Err(RPQBuildError::ExpressionTooDeep {
226                depth,
227                limit: MAX_RPQ_AST_DEPTH,
228            });
229        }
230        if !visited {
231            work.push((current, depth, true));
232            match current {
233                RegularPathExpr::Label(_) => {}
234                RegularPathExpr::Concat(left, right)
235                | RegularPathExpr::Alternation(left, right) => {
236                    work.push((right, depth.saturating_add(1), false));
237                    work.push((left, depth.saturating_add(1), false));
238                }
239                RegularPathExpr::KleeneStar(inner) | RegularPathExpr::Bounded { inner, .. } => {
240                    work.push((inner, depth.saturating_add(1), false));
241                }
242            }
243            continue;
244        }
245
246        let required = match current {
247            RegularPathExpr::Label(_) => Some(2),
248            RegularPathExpr::Concat(_, _) => {
249                let right = values.pop().ok_or_else(|| {
250                    RPQBuildError::InvalidNfa("missing concat right fragment".into())
251                })?;
252                let left = values.pop().ok_or_else(|| {
253                    RPQBuildError::InvalidNfa("missing concat left fragment".into())
254                })?;
255                left.checked_add(right)
256            }
257            RegularPathExpr::Alternation(_, _) => {
258                let right = values.pop().ok_or_else(|| {
259                    RPQBuildError::InvalidNfa("missing alternation right fragment".into())
260                })?;
261                let left = values.pop().ok_or_else(|| {
262                    RPQBuildError::InvalidNfa("missing alternation left fragment".into())
263                })?;
264                left.checked_add(right).and_then(|sum| sum.checked_add(2))
265            }
266            RegularPathExpr::KleeneStar(_) => values
267                .pop()
268                .ok_or_else(|| RPQBuildError::InvalidNfa("missing Kleene-star fragment".into()))?
269                .checked_add(2),
270            RegularPathExpr::Bounded { min, max, .. } => {
271                if min > max {
272                    return Err(RPQBuildError::InvalidBound {
273                        min: *min,
274                        max: *max,
275                    });
276                }
277                let inner = values.pop().ok_or_else(|| {
278                    RPQBuildError::InvalidNfa("missing bounded-repeat fragment".into())
279                })?;
280                usize::try_from(*max)
281                    .ok()
282                    .and_then(|copies| inner.checked_mul(copies))
283                    .and_then(|states| states.checked_add(2))
284            }
285        }
286        .ok_or(RPQBuildError::NfaStateLimitExceeded {
287            required: usize::MAX,
288            limit: MAX_NFA_STATES,
289        })?;
290        if required > MAX_NFA_STATES {
291            return Err(RPQBuildError::NfaStateLimitExceeded {
292                required,
293                limit: MAX_NFA_STATES,
294            });
295        }
296        values.push(required);
297    }
298    values
299        .pop()
300        .ok_or_else(|| RPQBuildError::InvalidNfa("regular path expression has no fragment".into()))
301}
302
303fn build_fragment(
304    nfa: &mut Nfa,
305    expr: &RegularPathExpr,
306) -> Result<(StateId, StateId), RPQBuildError> {
307    match expr {
308        RegularPathExpr::Label(name) => {
309            let s = nfa.new_state()?;
310            let a = nfa.new_state()?;
311            nfa.add_transition(s, Some(name.clone()), a)?;
312            Ok((s, a))
313        }
314        RegularPathExpr::Concat(l, r) => {
315            let (ls, la) = build_fragment(nfa, l)?;
316            let (rs, ra) = build_fragment(nfa, r)?;
317            nfa.add_transition(la, None, rs)?;
318            Ok((ls, ra))
319        }
320        RegularPathExpr::Alternation(l, r) => {
321            let s = nfa.new_state()?;
322            let a = nfa.new_state()?;
323            let (ls, la) = build_fragment(nfa, l)?;
324            let (rs, ra) = build_fragment(nfa, r)?;
325            nfa.add_transition(s, None, ls)?;
326            nfa.add_transition(s, None, rs)?;
327            nfa.add_transition(la, None, a)?;
328            nfa.add_transition(ra, None, a)?;
329            Ok((s, a))
330        }
331        RegularPathExpr::KleeneStar(inner) => {
332            let s = nfa.new_state()?;
333            let a = nfa.new_state()?;
334            let (is, ia) = build_fragment(nfa, inner)?;
335            nfa.add_transition(s, None, is)?;
336            nfa.add_transition(s, None, a)?;
337            nfa.add_transition(ia, None, is)?;
338            nfa.add_transition(ia, None, a)?;
339            Ok((s, a))
340        }
341        RegularPathExpr::Bounded { inner, min, max } => {
342            if min > max {
343                return Err(RPQBuildError::InvalidBound {
344                    min: *min,
345                    max: *max,
346                });
347            }
348            let start = nfa.new_state()?;
349            let mut current_end = start;
350            for _ in 0..*min {
351                let (is, ia) = build_fragment(nfa, inner)?;
352                nfa.add_transition(current_end, None, is)?;
353                current_end = ia;
354            }
355            let accept = nfa.new_state()?;
356            if min == max {
357                nfa.add_transition(current_end, None, accept)?;
358            } else {
359                nfa.add_transition(current_end, None, accept)?;
360                for _ in 0..(*max - *min) {
361                    let (is, ia) = build_fragment(nfa, inner)?;
362                    nfa.add_transition(current_end, None, is)?;
363                    nfa.add_transition(ia, None, accept)?;
364                    current_end = ia;
365                }
366            }
367            Ok((start, accept))
368        }
369    }
370}
371
372/// Epsilon closure of a state set: every state reachable by zero or
373/// more epsilon (`label == None`) transitions.
374pub fn epsilon_closure(
375    nfa: &Nfa,
376    states: &BTreeSet<StateId>,
377) -> Result<BTreeSet<StateId>, RPQBuildError> {
378    validate_nfa(nfa)?;
379    let mut closure = states.clone();
380    let mut stack: Vec<StateId> = states.iter().copied().collect();
381    while let Some(s) = stack.pop() {
382        let outgoing = nfa
383            .transitions
384            .get(usize::try_from(s).map_err(|_| {
385                RPQBuildError::InvalidNfa(format!("closure state {s} is not addressable"))
386            })?)
387            .ok_or_else(|| {
388                RPQBuildError::InvalidNfa(format!("closure state {s} is outside the NFA"))
389            })?;
390        for t in outgoing {
391            if t.label.is_none() && !closure.contains(&t.target) {
392                closure.insert(t.target);
393                stack.push(t.target);
394            }
395        }
396    }
397    Ok(closure)
398}
399
400fn validate_nfa(nfa: &Nfa) -> Result<(), RPQBuildError> {
401    let state_count = nfa.transitions.len();
402    if state_count == 0 {
403        return Err(RPQBuildError::InvalidNfa("NFA has no states".into()));
404    }
405    if state_count > MAX_NFA_STATES {
406        return Err(RPQBuildError::NfaStateLimitExceeded {
407            required: state_count,
408            limit: MAX_NFA_STATES,
409        });
410    }
411    for (name, state) in [("start", nfa.start), ("accept", nfa.accept)] {
412        if usize::try_from(state)
413            .ok()
414            .is_none_or(|index| index >= state_count)
415        {
416            return Err(RPQBuildError::InvalidNfa(format!(
417                "{name} state {state} is outside {state_count} states"
418            )));
419        }
420    }
421    for (source, transitions) in nfa.transitions.iter().enumerate() {
422        for transition in transitions {
423            if usize::try_from(transition.target)
424                .ok()
425                .is_none_or(|target| target >= state_count)
426            {
427                return Err(RPQBuildError::InvalidNfa(format!(
428                    "transition from state {source} targets missing state {}",
429                    transition.target
430                )));
431            }
432        }
433    }
434    Ok(())
435}
436
437// -------------------------------------------------------------------------
438// DFA (subset construction)
439// -------------------------------------------------------------------------
440
441pub type DfaState = BTreeSet<StateId>;
442
443#[derive(Debug)]
444pub struct Dfa {
445    pub start: DfaState,
446    pub accepts: BTreeSet<DfaState>,
447    pub transitions: BTreeMap<DfaState, BTreeMap<String, DfaState>>,
448}
449
450/// Convert an NFA to a DFA via the standard subset construction.
451pub fn subset_construction(nfa: &Nfa) -> Result<Dfa, RPQBuildError> {
452    validate_nfa(nfa)?;
453    // Collect alphabet (non-epsilon transition labels).
454    let mut alphabet: BTreeSet<String> = BTreeSet::new();
455    for transitions in &nfa.transitions {
456        for t in transitions {
457            if let Some(label) = &t.label {
458                alphabet.insert(label.clone());
459            }
460        }
461    }
462
463    let initial = epsilon_closure(nfa, &BTreeSet::from([nfa.start]))?;
464    let mut transitions: BTreeMap<DfaState, BTreeMap<String, DfaState>> = BTreeMap::new();
465    let mut accepts: BTreeSet<DfaState> = BTreeSet::new();
466    let mut seen: BTreeSet<DfaState> = BTreeSet::from([initial.clone()]);
467    let mut work: VecDeque<DfaState> = VecDeque::from([initial.clone()]);
468
469    if initial.contains(&nfa.accept) {
470        accepts.insert(initial.clone());
471    }
472
473    while let Some(current) = work.pop_front() {
474        let mut step: BTreeMap<String, DfaState> = BTreeMap::new();
475        for label in &alphabet {
476            let mut next_nfa: BTreeSet<StateId> = BTreeSet::new();
477            for sid in &current {
478                let outgoing = nfa
479                    .transitions
480                    .get(usize::try_from(*sid).map_err(|_| {
481                        RPQBuildError::InvalidNfa(format!("DFA state {sid} is not addressable"))
482                    })?)
483                    .ok_or_else(|| {
484                        RPQBuildError::InvalidNfa(format!("DFA state {sid} is outside the NFA"))
485                    })?;
486                for t in outgoing {
487                    if t.label.as_deref() == Some(label.as_str()) {
488                        next_nfa.insert(t.target);
489                    }
490                }
491            }
492            if next_nfa.is_empty() {
493                continue;
494            }
495            let closed = epsilon_closure(nfa, &next_nfa)?;
496            step.insert(label.clone(), closed.clone());
497            if !seen.contains(&closed) {
498                if seen.len() >= MAX_DFA_STATES {
499                    return Err(RPQBuildError::DfaStateLimitExceeded {
500                        limit: MAX_DFA_STATES,
501                    });
502                }
503                seen.insert(closed.clone());
504                work.push_back(closed.clone());
505                if closed.contains(&nfa.accept) {
506                    accepts.insert(closed);
507                }
508            }
509        }
510        transitions.insert(current, step);
511    }
512
513    Ok(Dfa {
514        start: initial,
515        accepts,
516        transitions,
517    })
518}
519
520#[cfg(test)]
521mod tests {
522    use super::*;
523
524    #[test]
525    fn build_rejects_unbounded_state_allocation_before_expansion() {
526        let expr = RegularPathExpr::bounded(RegularPathExpr::label("a"), 0, u32::MAX);
527        assert!(matches!(
528            build_nfa(&expr),
529            Err(RPQBuildError::NfaStateLimitExceeded { .. })
530        ));
531    }
532
533    #[test]
534    fn build_rejects_programmatically_reversed_bound() {
535        let expr = RegularPathExpr::bounded(RegularPathExpr::label("a"), 5, 2);
536        assert_eq!(
537            build_nfa(&expr).unwrap_err(),
538            RPQBuildError::InvalidBound { min: 5, max: 2 }
539        );
540    }
541
542    #[test]
543    fn subset_construction_rejects_missing_transition_target() {
544        let malformed = Nfa {
545            transitions: vec![vec![NfaTransition {
546                label: None,
547                target: 1,
548            }]],
549            start: 0,
550            accept: 0,
551        };
552        assert!(matches!(
553            subset_construction(&malformed),
554            Err(RPQBuildError::InvalidNfa(message)) if message.contains("missing state")
555        ));
556    }
557
558    #[test]
559    fn simplify_idempotent_alternation() {
560        let e = RegularPathExpr::alt(RegularPathExpr::label("a"), RegularPathExpr::label("a"));
561        assert_eq!(simplify(&e).unwrap(), RegularPathExpr::label("a"));
562    }
563
564    #[test]
565    fn simplify_nested_kleene() {
566        let e = RegularPathExpr::star(RegularPathExpr::star(RegularPathExpr::label("a")));
567        assert_eq!(
568            simplify(&e).unwrap(),
569            RegularPathExpr::star(RegularPathExpr::label("a"))
570        );
571    }
572
573    #[test]
574    fn simplify_star_subsumes_label() {
575        let e = RegularPathExpr::alt(
576            RegularPathExpr::star(RegularPathExpr::label("a")),
577            RegularPathExpr::label("a"),
578        );
579        assert_eq!(
580            simplify(&e).unwrap(),
581            RegularPathExpr::star(RegularPathExpr::label("a"))
582        );
583    }
584
585    #[test]
586    fn nfa_label_two_states() {
587        let nfa = build_nfa(&RegularPathExpr::label("a")).unwrap();
588        assert_eq!(nfa.transitions.len(), 2);
589        assert_ne!(nfa.start, nfa.accept);
590    }
591
592    #[test]
593    fn dfa_recognizes_a_or_b() {
594        let nfa = build_nfa(&RegularPathExpr::alt(
595            RegularPathExpr::label("a"),
596            RegularPathExpr::label("b"),
597        ))
598        .unwrap();
599        let dfa = subset_construction(&nfa).unwrap();
600        // After reading 'a' from start, the DFA should reach an accept.
601        let after_a = dfa
602            .transitions
603            .get(&dfa.start)
604            .and_then(|m| m.get("a"))
605            .expect("no `a` transition");
606        assert!(dfa.accepts.contains(after_a));
607        let after_b = dfa
608            .transitions
609            .get(&dfa.start)
610            .and_then(|m| m.get("b"))
611            .expect("no `b` transition");
612        assert!(dfa.accepts.contains(after_b));
613        // And no `c`.
614        assert!(dfa
615            .transitions
616            .get(&dfa.start)
617            .and_then(|m| m.get("c"))
618            .is_none());
619    }
620
621    #[test]
622    fn dfa_recognizes_kleene_star() {
623        let nfa = build_nfa(&RegularPathExpr::star(RegularPathExpr::label("a"))).unwrap();
624        let dfa = subset_construction(&nfa).unwrap();
625        // Empty string accepted (start is in accepts).
626        assert!(dfa.accepts.contains(&dfa.start));
627    }
628}
uqa_graph/rpq.rs

uqa_graph/
rpq.rs
