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    // `sh:` is part of the public shape-map API: its default `name_path` is
272    // `sh:name`. Shapes may be supplied without prefix declarations (for
273    // example, as N-Triples), where the public default must still resolve.
274    let namespace = prefixes
275        .iter()
276        .find(|(p, _)| p == prefix)
277        .map(|(_, namespace)| namespace.as_str())
278        // `sh:` is a standard fallback, not an override: an explicit
279        // document declaration retains its normal SPARQL meaning.
280        .or_else(|| (prefix == "sh").then_some("http://www.w3.org/ns/shacl#"))
281        .ok_or_else(|| format!("undeclared prefix {prefix:?} in property path {token:?}"))?;
282    NamedNode::new(format!("{namespace}{local}"))
283        .map_err(|e| format!("invalid IRI from {token:?}: {e}"))
284}
285
286#[cfg(test)]
287mod tests {
288    use super::*;
289    use crate::graph::Loaded;
290
291    fn shapes_with_prefixes() -> Loaded {
292        Loaded::from_turtle(
293            b"@prefix ex: <http://ex/> . @prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#> . ex:s ex:p ex:o .",
294            None,
295        )
296        .unwrap()
297    }
298
299    fn pred(iri: &str) -> Path {
300        Path::Pred(NamedNode::new(iri).unwrap())
301    }
302
303    #[test]
304    fn single_predicate() {
305        let shapes = shapes_with_prefixes();
306        assert_eq!(
307            parse_property_path("ex:p", &shapes).unwrap(),
308            pred("http://ex/p")
309        );
310    }
311
312    #[test]
313    fn absolute_iri() {
314        let shapes = shapes_with_prefixes();
315        assert_eq!(
316            parse_property_path("<http://ex/p>", &shapes).unwrap(),
317            pred("http://ex/p")
318        );
319    }
320
321    #[test]
322    fn sequence() {
323        let shapes = shapes_with_prefixes();
324        assert_eq!(
325            parse_property_path("ex:p/rdfs:label", &shapes).unwrap(),
326            Path::Seq(vec![
327                pred("http://ex/p"),
328                pred("http://www.w3.org/2000/01/rdf-schema#label")
329            ])
330        );
331    }
332
333    #[test]
334    fn inverse() {
335        let shapes = shapes_with_prefixes();
336        assert_eq!(
337            parse_property_path("^ex:p", &shapes).unwrap(),
338            pred("http://ex/p").inverse()
339        );
340    }
341
342    #[test]
343    fn inverse_then_sequence() {
344        let shapes = shapes_with_prefixes();
345        assert_eq!(
346            parse_property_path("^ex:p/rdfs:label", &shapes).unwrap(),
347            Path::Seq(vec![
348                pred("http://ex/p").inverse(),
349                pred("http://www.w3.org/2000/01/rdf-schema#label")
350            ])
351        );
352    }
353
354    #[test]
355    fn alternation() {
356        let shapes = shapes_with_prefixes();
357        assert_eq!(
358            parse_property_path("ex:p|ex:q", &shapes).unwrap(),
359            Path::Alt(vec![pred("http://ex/p"), pred("http://ex/q")])
360        );
361    }
362
363    #[test]
364    fn zero_or_more() {
365        let shapes = shapes_with_prefixes();
366        assert_eq!(
367            parse_property_path("ex:p*", &shapes).unwrap(),
368            pred("http://ex/p").star()
369        );
370    }
371
372    #[test]
373    fn one_or_more() {
374        let shapes = shapes_with_prefixes();
375        assert_eq!(
376            parse_property_path("ex:p+", &shapes).unwrap(),
377            pred("http://ex/p").one_or_more()
378        );
379    }
380
381    #[test]
382    fn zero_or_one() {
383        let shapes = shapes_with_prefixes();
384        assert_eq!(
385            parse_property_path("ex:p?", &shapes).unwrap(),
386            pred("http://ex/p").zero_or_one()
387        );
388    }
389
390    #[test]
391    fn grouping_changes_precedence() {
392        let shapes = shapes_with_prefixes();
393        // Without grouping, / binds tighter than |, so this is p/(q|r).
394        assert_eq!(
395            parse_property_path("ex:p/(ex:q|ex:r)", &shapes).unwrap(),
396            Path::Seq(vec![
397                pred("http://ex/p"),
398                Path::Alt(vec![pred("http://ex/q"), pred("http://ex/r")]),
399            ])
400        );
401    }
402
403    #[test]
404    fn a_keyword_is_rdf_type() {
405        let shapes = shapes_with_prefixes();
406        assert_eq!(
407            parse_property_path("a", &shapes).unwrap(),
408            pred("http://www.w3.org/1999/02/22-rdf-syntax-ns#type")
409        );
410    }
411
412    #[test]
413    fn unknown_prefix_is_an_error() {
414        let shapes = shapes_with_prefixes();
415        assert!(parse_property_path("nope:p", &shapes).is_err());
416    }
417
418    #[test]
419    fn negated_property_set_is_rejected() {
420        let shapes = shapes_with_prefixes();
421        let err = parse_property_path("!ex:p", &shapes).unwrap_err();
422        assert!(err.contains("negated property set"), "{err}");
423    }
424
425    #[test]
426    fn trailing_garbage_is_an_error() {
427        let shapes = shapes_with_prefixes();
428        assert!(parse_property_path("ex:p )", &shapes).is_err());
429    }
430}
shifty_parse/sparql_path.rs

shifty_parse/
sparql_path.rs
