shifty_algebra/
path.rs

1//! The path algebra `π` (doc 00 §2, Def. 3).
2//!
3//! ```text
4//! π ::= id | q | π⁻ | π · π′ | π ∪ π′ | π*        (q ∈ P)
5//! ```
6//!
7//! Paths are finite trees (no cycles), so plain `Box`/`Vec` nesting suffices.
8//! The smart constructors apply the *light* Kleene-with-converse laws that are
9//! always sound and cheap; heavier canonicalization is Layer 4 (`shifty-opt`).
10
11use crate::term::NamedNode;
12use serde::{Deserialize, Serialize};
13
14#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
15pub enum Path {
16    /// `id` — the identity relation / empty word.
17    Id,
18    /// `q` — a single predicate step.
19    Pred(NamedNode),
20    /// `π⁻` — inverse.
21    Inverse(Box<Path>),
22    /// `π · π′ · …` — sequential composition.
23    Seq(Vec<Path>),
24    /// `π ∪ π′ ∪ …` — alternation (relational union).
25    Alt(Vec<Path>),
26    /// `π*` — reflexive-transitive closure.
27    Star(Box<Path>),
28}
29
30impl Path {
31    /// Compose paths, flattening nested `Seq` and dropping `id` (the unit of
32    /// composition, `π · id = π`). An empty sequence is `id`.
33    pub fn seq(parts: Vec<Path>) -> Path {
34        let mut flat = Vec::with_capacity(parts.len());
35        for p in parts {
36            match p {
37                Path::Id => {}
38                Path::Seq(inner) => flat.extend(inner),
39                other => flat.push(other),
40            }
41        }
42        match flat.len() {
43            0 => Path::Id,
44            1 => flat.pop().unwrap(),
45            _ => Path::Seq(flat),
46        }
47    }
48
49    /// Alternate paths, flattening nested `Alt`. An empty alternation is the
50    /// empty relation (kept explicit as `Alt([])` — it matches nothing).
51    pub fn alt(parts: Vec<Path>) -> Path {
52        let mut flat = Vec::with_capacity(parts.len());
53        for p in parts {
54            match p {
55                Path::Alt(inner) => flat.extend(inner),
56                other => flat.push(other),
57            }
58        }
59        if flat.len() == 1 {
60            flat.pop().unwrap()
61        } else {
62            Path::Alt(flat)
63        }
64    }
65
66    /// Invert, using `id⁻ = id` and the involution `(π⁻)⁻ = π`.
67    pub fn inverse(self) -> Path {
68        match self {
69            Path::Id => Path::Id,
70            Path::Inverse(inner) => *inner,
71            other => Path::Inverse(Box::new(other)),
72        }
73    }
74
75    /// Reflexive-transitive closure, using `id* = id` and `(π*)* = π*`.
76    pub fn star(self) -> Path {
77        match self {
78            Path::Id => Path::Id,
79            Path::Star(_) => self,
80            other => Path::Star(Box::new(other)),
81        }
82    }
83
84    /// `π⁺ = π · π*` — one-or-more sugar (gap-analysis **P1**).
85    pub fn one_or_more(self) -> Path {
86        let star = self.clone().star();
87        Path::seq(vec![self, star])
88    }
89
90    /// `π? = π ∪ id` — zero-or-one sugar (gap-analysis **P1**).
91    pub fn zero_or_one(self) -> Path {
92        Path::alt(vec![self, Path::Id])
93    }
94}
95
96#[cfg(test)]
97mod tests {
98    use super::*;
99
100    fn pred(s: &str) -> Path {
101        Path::Pred(NamedNode::new(format!("http://ex/{s}")).unwrap())
102    }
103
104    #[test]
105    fn seq_flattens_and_drops_id() {
106        let p = Path::seq(vec![
107            pred("a"),
108            Path::Id,
109            Path::seq(vec![pred("b"), pred("c")]),
110        ]);
111        assert_eq!(p, Path::Seq(vec![pred("a"), pred("b"), pred("c")]));
112    }
113
114    #[test]
115    fn seq_units() {
116        assert_eq!(Path::seq(vec![]), Path::Id);
117        assert_eq!(Path::seq(vec![Path::Id, Path::Id]), Path::Id);
118        assert_eq!(Path::seq(vec![pred("a")]), pred("a"));
119    }
120
121    #[test]
122    fn alt_flattens_and_collapses_singleton() {
123        let p = Path::alt(vec![pred("a"), Path::alt(vec![pred("b"), pred("c")])]);
124        assert_eq!(p, Path::Alt(vec![pred("a"), pred("b"), pred("c")]));
125        assert_eq!(Path::alt(vec![pred("a")]), pred("a"));
126    }
127
128    #[test]
129    fn inverse_is_involution() {
130        assert_eq!(pred("a").inverse().inverse(), pred("a"));
131        assert_eq!(Path::Id.inverse(), Path::Id);
132    }
133
134    #[test]
135    fn star_is_idempotent() {
136        assert_eq!(pred("a").star().star(), pred("a").star());
137        assert_eq!(Path::Id.star(), Path::Id);
138    }
139
140    #[test]
141    fn sugar_expansions() {
142        assert_eq!(
143            pred("a").one_or_more(),
144            Path::Seq(vec![pred("a"), Path::Star(Box::new(pred("a")))])
145        );
146        assert_eq!(
147            pred("a").zero_or_one(),
148            Path::Alt(vec![pred("a"), Path::Id])
149        );
150    }
151}
shifty_algebra/path.rs

shifty_algebra/
path.rs
