shifty_parse/
sparql_path.rs

1//! Parse a SPARQL 1.1 property path expression (the `Path` production, SPARQL
2//! 1.1 §18.2 grammar rules [88]-[94]) into the [`Path`] algebra.
3//!
4//! This exists as its own small recursive-descent parser rather than reusing
5//! `spargebra`'s query parser: `spargebra` lowers a parsed `SELECT ?s <path>
6//! ?o` straight to algebra, and for "simple" paths (no alternation/Kleene
7//! forms) that lowering silently rewrites the path into a chain of joined
8//! triple patterns rather than keeping a `PropertyPathExpression` tree —
9//! there is no reliable way to recover an arbitrary [`Path`] from the result.
10//! The `Path` grammar production itself is small and has been stable since
11//! SPARQL 1.1, so parsing it directly is the more robust option.
12//!
13//! Supported: sequence (`/`), alternation (`|`), inverse (`^`), the Kleene
14//! forms (`*`, `+`, `?`), grouping (`( … )`), and the `a` keyword for
15//! `rdf:type`. Negated property sets (`!…`) have no equivalent in the [`Path`]
16//! algebra and are rejected with a clear error.
17
18use crate::graph::Loaded;
19use crate::vocab;
20use oxrdf::NamedNode;
21use shifty_algebra::Path;
22
23/// Parse a SPARQL 1.1 property path expression, resolving prefixed names
24/// (`prefix:local`) against `shapes`' declared `@prefix`es and `a` against
25/// `rdf:type`. `<absolute IRI>` forms are also accepted.
26pub fn parse_property_path(expr: &str, shapes: &Loaded) -> Result<Path, String> {
27    let tokens = lex(expr)?;
28    let mut parser = Parser {
29        tokens: &tokens,
30        pos: 0,
31        prefixes: &shapes.prefixes,
32    };
33    let path = parser.parse_path_alternative()?;
34    if parser.pos != parser.tokens.len() {
35        return Err(format!(
36            "unexpected trailing input in property path {expr:?} at token {}",
37            parser.pos
38        ));
39    }
40    Ok(path)
41}
42
43#[derive(Debug, Clone, PartialEq, Eq)]
44enum Token {
45    /// From `<...>` — already an absolute IRI, used as-is.
46    AbsoluteIri(String),
47    /// From a bare `prefix:local` — must resolve through `prefixes`.
48    PrefixedName(String),
49    A,
50    Caret,
51    Slash,
52    Pipe,
53    Star,
54    Plus,
55    Question,
56    Bang,
57    LParen,
58    RParen,
59}
60
61fn lex(expr: &str) -> Result<Vec<Token>, String> {
62    let mut tokens = Vec::new();
63    let mut chars = expr.char_indices().peekable();
64    while let Some(&(i, c)) = chars.peek() {
65        match c {
66            c if c.is_whitespace() => {
67                chars.next();
68            }
69            '^' => {
70                tokens.push(Token::Caret);
71                chars.next();
72            }
73            '/' => {
74                tokens.push(Token::Slash);
75                chars.next();
76            }
77            '|' => {
78                tokens.push(Token::Pipe);
79                chars.next();
80            }
81            '*' => {
82                tokens.push(Token::Star);
83                chars.next();
84            }
85            '+' => {
86                tokens.push(Token::Plus);
87                chars.next();
88            }
89            '?' => {
90                tokens.push(Token::Question);
91                chars.next();
92            }
93            '!' => {
94                tokens.push(Token::Bang);
95                chars.next();
96            }
97            '(' => {
98                tokens.push(Token::LParen);
99                chars.next();
100            }
101            ')' => {
102                tokens.push(Token::RParen);
103                chars.next();
104            }
105            '<' => {
106                chars.next();
107                let start = i + 1;
108                let mut end = expr.len();
109                let mut closed = false;
110                for (j, c2) in chars.by_ref() {
111                    if c2 == '>' {
112                        end = j;
113                        closed = true;
114                        break;
115                    }
116                }
117                if !closed {
118                    return Err(format!("unterminated <IRI> in property path {expr:?}"));
119                }
120                tokens.push(Token::AbsoluteIri(expr[start..end].to_string()));
121            }
122            c if is_name_char(c) => {
123                let start = i;
124                let mut end = expr.len();
125                while let Some(&(j, c2)) = chars.peek() {
126                    if is_name_char(c2) {
127                        chars.next();
128                    } else {
129                        end = j;
130                        break;
131                    }
132                }
133                let word = &expr[start..end];
134                if word == "a" {
135                    tokens.push(Token::A);
136                } else if word.contains(':') {
137                    tokens.push(Token::PrefixedName(word.to_string()));
138                } else {
139                    return Err(format!(
140                        "expected 'prefix:local' or 'a' in property path, got {word:?}"
141                    ));
142                }
143            }
144            other => {
145                return Err(format!(
146                    "unexpected character {other:?} in property path {expr:?}"
147                ));
148            }
149        }
150    }
151    Ok(tokens)
152}
153
154fn is_name_char(c: char) -> bool {
155    c.is_alphanumeric() || matches!(c, '_' | '-' | '.' | ':')
156}
157
158struct Parser<'a> {
159    tokens: &'a [Token],
160    pos: usize,
161    prefixes: &'a [(String, String)],
162}
163
164impl Parser<'_> {
165    fn peek(&self) -> Option<&Token> {
166        self.tokens.get(self.pos)
167    }
168
169    fn eat(&mut self, token: &Token) -> bool {
170        if self.peek() == Some(token) {
171            self.pos += 1;
172            true
173        } else {
174            false
175        }
176    }
177
178    fn expect(&mut self, token: Token) -> Result<(), String> {
179        if self.eat(&token) {
180            Ok(())
181        } else {
182            Err(format!(
183                "expected {token:?} in property path, got {:?}",
184                self.peek()
185            ))
186        }
187    }
188
189    // PathAlternative ::= PathSequence ( '|' PathSequence )*
190    fn parse_path_alternative(&mut self) -> Result<Path, String> {
191        let mut parts = vec![self.parse_path_sequence()?];
192        while self.eat(&Token::Pipe) {
193            parts.push(self.parse_path_sequence()?);
194        }
195        Ok(Path::alt(parts))
196    }
197
198    // PathSequence ::= PathEltOrInverse ( '/' PathEltOrInverse )*
199    fn parse_path_sequence(&mut self) -> Result<Path, String> {
200        let mut parts = vec![self.parse_path_elt_or_inverse()?];
201        while self.eat(&Token::Slash) {
202            parts.push(self.parse_path_elt_or_inverse()?);
203        }
204        Ok(Path::seq(parts))
205    }
206
207    // PathEltOrInverse ::= PathElt | '^' PathElt
208    fn parse_path_elt_or_inverse(&mut self) -> Result<Path, String> {
209        if self.eat(&Token::Caret) {
210            Ok(self.parse_path_elt()?.inverse())
211        } else {
212            self.parse_path_elt()
213        }
214    }
215
216    // PathElt ::= PathPrimary PathMod?
217    fn parse_path_elt(&mut self) -> Result<Path, String> {
218        let primary = self.parse_path_primary()?;
219        if self.eat(&Token::Star) {
220            Ok(primary.star())
221        } else if self.eat(&Token::Plus) {
222            Ok(primary.one_or_more())
223        } else if self.eat(&Token::Question) {
224            Ok(primary.zero_or_one())
225        } else {
226            Ok(primary)
227        }
228    }
229
230    // PathPrimary ::= iri | 'a' | '!' PathNegatedPropertySet | '(' Path ')'
231    fn parse_path_primary(&mut self) -> Result<Path, String> {
232        match self.tokens.get(self.pos).cloned() {
233            Some(Token::AbsoluteIri(iri)) => {
234                self.pos += 1;
235                let named =
236                    NamedNode::new(&iri).map_err(|e| format!("invalid IRI <{iri}>: {e}"))?;
237                Ok(Path::Pred(named))
238            }
239            Some(Token::PrefixedName(name)) => {
240                self.pos += 1;
241                let named = resolve_prefixed_name(&name, self.prefixes)?;
242                Ok(Path::Pred(named))
243            }
244            Some(Token::A) => {
245                self.pos += 1;
246                Ok(Path::Pred(vocab::rdf_type()))
247            }
248            Some(Token::LParen) => {
249                self.pos += 1;
250                let inner = self.parse_path_alternative()?;
251                self.expect(Token::RParen)?;
252                Ok(inner)
253            }
254            Some(Token::Bang) => Err(
255                "negated property sets ('!...') have no equivalent in the path algebra".to_string(),
256            ),
257            other => Err(format!("unexpected token {other:?} in property path")),
258        }
259    }
260}
261
262/// Resolve a bare `prefix:local` token against `prefixes`. Unlike `<...>`,
263/// this never falls back to treating the token as an already-absolute IRI:
264/// `prefix:local` is only ever a CURIE here, and an undeclared prefix (e.g. a
265/// typo) must be a hard error rather than silently accepted as some other
266/// IRI scheme (`nope:p` is, syntactically, itself a valid absolute IRI).
267fn resolve_prefixed_name(token: &str, prefixes: &[(String, String)]) -> Result<NamedNode, String> {
268    let (prefix, local) = token
269        .split_once(':')
270        .expect("PrefixedName tokens always contain ':'");
271    let (_, namespace) = prefixes
272        .iter()
273        .find(|(p, _)| p == prefix)
274        .ok_or_else(|| format!("undeclared prefix {prefix:?} in property path {token:?}"))?;
275    NamedNode::new(format!("{namespace}{local}"))
276        .map_err(|e| format!("invalid IRI from {token:?}: {e}"))
277}
278
279#[cfg(test)]
280mod tests {
281    use super::*;
282    use crate::graph::Loaded;
283
284    fn shapes_with_prefixes() -> Loaded {
285        Loaded::from_turtle(
286            b"@prefix ex: <http://ex/> . @prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#> . ex:s ex:p ex:o .",
287            None,
288        )
289        .unwrap()
290    }
291
292    fn pred(iri: &str) -> Path {
293        Path::Pred(NamedNode::new(iri).unwrap())
294    }
295
296    #[test]
297    fn single_predicate() {
298        let shapes = shapes_with_prefixes();
299        assert_eq!(
300            parse_property_path("ex:p", &shapes).unwrap(),
301            pred("http://ex/p")
302        );
303    }
304
305    #[test]
306    fn absolute_iri() {
307        let shapes = shapes_with_prefixes();
308        assert_eq!(
309            parse_property_path("<http://ex/p>", &shapes).unwrap(),
310            pred("http://ex/p")
311        );
312    }
313
314    #[test]
315    fn sequence() {
316        let shapes = shapes_with_prefixes();
317        assert_eq!(
318            parse_property_path("ex:p/rdfs:label", &shapes).unwrap(),
319            Path::Seq(vec![
320                pred("http://ex/p"),
321                pred("http://www.w3.org/2000/01/rdf-schema#label")
322            ])
323        );
324    }
325
326    #[test]
327    fn inverse() {
328        let shapes = shapes_with_prefixes();
329        assert_eq!(
330            parse_property_path("^ex:p", &shapes).unwrap(),
331            pred("http://ex/p").inverse()
332        );
333    }
334
335    #[test]
336    fn inverse_then_sequence() {
337        let shapes = shapes_with_prefixes();
338        assert_eq!(
339            parse_property_path("^ex:p/rdfs:label", &shapes).unwrap(),
340            Path::Seq(vec![
341                pred("http://ex/p").inverse(),
342                pred("http://www.w3.org/2000/01/rdf-schema#label")
343            ])
344        );
345    }
346
347    #[test]
348    fn alternation() {
349        let shapes = shapes_with_prefixes();
350        assert_eq!(
351            parse_property_path("ex:p|ex:q", &shapes).unwrap(),
352            Path::Alt(vec![pred("http://ex/p"), pred("http://ex/q")])
353        );
354    }
355
356    #[test]
357    fn zero_or_more() {
358        let shapes = shapes_with_prefixes();
359        assert_eq!(
360            parse_property_path("ex:p*", &shapes).unwrap(),
361            pred("http://ex/p").star()
362        );
363    }
364
365    #[test]
366    fn one_or_more() {
367        let shapes = shapes_with_prefixes();
368        assert_eq!(
369            parse_property_path("ex:p+", &shapes).unwrap(),
370            pred("http://ex/p").one_or_more()
371        );
372    }
373
374    #[test]
375    fn zero_or_one() {
376        let shapes = shapes_with_prefixes();
377        assert_eq!(
378            parse_property_path("ex:p?", &shapes).unwrap(),
379            pred("http://ex/p").zero_or_one()
380        );
381    }
382
383    #[test]
384    fn grouping_changes_precedence() {
385        let shapes = shapes_with_prefixes();
386        // Without grouping, / binds tighter than |, so this is p/(q|r).
387        assert_eq!(
388            parse_property_path("ex:p/(ex:q|ex:r)", &shapes).unwrap(),
389            Path::Seq(vec![
390                pred("http://ex/p"),
391                Path::Alt(vec![pred("http://ex/q"), pred("http://ex/r")]),
392            ])
393        );
394    }
395
396    #[test]
397    fn a_keyword_is_rdf_type() {
398        let shapes = shapes_with_prefixes();
399        assert_eq!(
400            parse_property_path("a", &shapes).unwrap(),
401            pred("http://www.w3.org/1999/02/22-rdf-syntax-ns#type")
402        );
403    }
404
405    #[test]
406    fn unknown_prefix_is_an_error() {
407        let shapes = shapes_with_prefixes();
408        assert!(parse_property_path("nope:p", &shapes).is_err());
409    }
410
411    #[test]
412    fn negated_property_set_is_rejected() {
413        let shapes = shapes_with_prefixes();
414        let err = parse_property_path("!ex:p", &shapes).unwrap_err();
415        assert!(err.contains("negated property set"), "{err}");
416    }
417
418    #[test]
419    fn trailing_garbage_is_an_error() {
420        let shapes = shapes_with_prefixes();
421        assert!(parse_property_path("ex:p )", &shapes).is_err());
422    }
423}
shifty_parse/sparql_path.rs

shifty_parse/
sparql_path.rs
