oxirs_arq/query/queryparser_parsing.rs
1//! # QueryParser - parsing Methods
2//!
3//! This module contains method implementations for `QueryParser`.
4//!
5//! 🤖 Generated with [SplitRS](https://github.com/cool-japan/splitrs)
6
7use crate::algebra::{Algebra, PropertyPath, Term, TriplePattern, Variable};
8use anyhow::{anyhow, bail, Result};
9use oxirs_core::model::NamedNode;
10use std::collections::{HashMap, HashSet};
11
12use super::types::{
13 DatasetClause, DatatypeRef, DescribeTarget, ProjectionItem, Query, QueryType, Token,
14};
15
16use super::queryparser_type::QueryParser;
17
18/// Compose the next group-graph-pattern element onto the accumulated pattern.
19///
20/// `OPTIONAL`, `MINUS` and a leading `UNION` are each parsed with the unit table
21/// (`Algebra::Table`) as their left operand, because a group element is written
22/// standalone. At the group level, however, they operate on the pattern that
23/// PRECEDES them, so they must be re-rooted on the accumulated `prev` rather
24/// than joined as an independent unit:
25///
26/// * `Join(prev, Minus(Table, r))` makes `MINUS` a silent no-op — a `Table` left
27/// shares no variables with `r`, and SPARQL `MINUS` removes nothing when the
28/// operands are variable-disjoint. Re-rooting to `Minus(prev, r)` restores the
29/// difference.
30/// * `Join(prev, LeftJoin(Table, r))` collapses `OPTIONAL` into an inner join
31/// (dropping `prev` rows without an `r` match). Re-rooting to
32/// `LeftJoin(prev, r)` restores proper optional semantics.
33fn compose_group_element(prev: Algebra, element: Algebra) -> Algebra {
34 match element {
35 Algebra::LeftJoin {
36 left,
37 right,
38 filter,
39 } if matches!(*left, Algebra::Table) => Algebra::LeftJoin {
40 left: Box::new(prev),
41 right,
42 filter,
43 },
44 Algebra::Minus { left, right } if matches!(*left, Algebra::Table) => Algebra::Minus {
45 left: Box::new(prev),
46 right,
47 },
48 other => Algebra::join(prev, other),
49 }
50}
51
52impl QueryParser {
53 pub fn new() -> Self {
54 Self {
55 tokens: Vec::new(),
56 position: 0,
57 prefixes: HashMap::new(),
58 base_iri: None,
59 variables: HashSet::new(),
60 blank_node_counter: 0,
61 in_construct_template: false,
62 }
63 }
64 /// Tokenize SPARQL query string
65 pub(super) fn tokenize(&mut self, input: &str) -> Result<()> {
66 let mut chars = input.chars().peekable();
67 let mut tokens = Vec::new();
68 while let Some(&ch) = chars.peek() {
69 match ch {
70 ' ' | '\t' | '\r' => {
71 chars.next();
72 }
73 '\n' => {
74 chars.next();
75 tokens.push(Token::Newline);
76 }
77 '#' => {
78 while let Some(&ch) = chars.peek() {
79 chars.next();
80 if ch == '\n' {
81 tokens.push(Token::Newline);
82 break;
83 }
84 }
85 }
86 '(' => {
87 chars.next();
88 tokens.push(Token::LeftParen);
89 }
90 ')' => {
91 chars.next();
92 tokens.push(Token::RightParen);
93 }
94 '{' => {
95 chars.next();
96 tokens.push(Token::LeftBrace);
97 }
98 '}' => {
99 chars.next();
100 tokens.push(Token::RightBrace);
101 }
102 '[' => {
103 chars.next();
104 tokens.push(Token::LeftBracket);
105 }
106 ']' => {
107 chars.next();
108 tokens.push(Token::RightBracket);
109 }
110 '.' => {
111 chars.next();
112 tokens.push(Token::Dot);
113 }
114 ';' => {
115 chars.next();
116 tokens.push(Token::Semicolon);
117 }
118 ',' => {
119 chars.next();
120 tokens.push(Token::Comma);
121 }
122 ':' => {
123 chars.next();
124 if chars
125 .peek()
126 .map_or(true, |c| !c.is_ascii_alphanumeric() && *c != '_')
127 {
128 tokens.push(Token::Colon);
129 } else {
130 let mut id = ":".to_string();
131 id.push_str(&self.parse_identifier(&mut chars));
132 tokens.push(self.classify_identifier(&id));
133 }
134 }
135 '=' => {
136 chars.next();
137 if chars.peek() == Some(&'=') {
138 chars.next();
139 tokens.push(Token::Equal);
140 } else {
141 tokens.push(Token::Equal);
142 }
143 }
144 '<' => {
145 chars.next();
146 if chars.peek() == Some(&'=') {
147 chars.next();
148 tokens.push(Token::LessEqual);
149 } else {
150 // Disambiguate a full IRIREF (`<urn:p>`, `<http://…>`,
151 // `<https://…#f>`, relative `<p>`) from the `<` / `<=`
152 // comparison operators. Per SPARQL 1.1,
153 // IRIREF ::= '<' ([^<>"{}|^`\] - [#x00-#x20])* '>'.
154 // Scan a CLONE of the iterator: only when the closing `>`
155 // is reached before any character excluded from an IRIREF
156 // (which includes every control/space char, so `?x < ?y`
157 // and `?x<5` never misread as IRIs) do we commit a
158 // `Token::Iri`. Otherwise fall back to the `<` operator
159 // with the real iterator untouched (only the opening `<`
160 // already consumed).
161 let mut lookahead = chars.clone();
162 let mut iri = String::new();
163 let mut closed = false;
164 for ch in lookahead.by_ref() {
165 if ch == '>' {
166 closed = true;
167 break;
168 }
169 // Excluded from IRIREF content: <>"{}|^`\ and every
170 // control or space code point (<= U+0020). Everything
171 // else — including non-ASCII ucschar — is permitted.
172 if matches!(ch, '<' | '"' | '{' | '}' | '|' | '^' | '`' | '\\')
173 || ch <= '\u{20}'
174 {
175 break;
176 }
177 iri.push(ch);
178 }
179 if closed {
180 // Commit: `lookahead` already sits just past the `>`.
181 chars = lookahead;
182 tokens.push(Token::Iri(iri));
183 } else {
184 tokens.push(Token::Less);
185 }
186 }
187 }
188 '>' => {
189 chars.next();
190 if chars.peek() == Some(&'=') {
191 chars.next();
192 tokens.push(Token::GreaterEqual);
193 } else {
194 tokens.push(Token::Greater);
195 }
196 }
197 '+' => {
198 chars.next();
199 tokens.push(Token::Plus);
200 }
201 '-' => {
202 chars.next();
203 tokens.push(Token::Minus_);
204 }
205 '/' => {
206 chars.next();
207 tokens.push(Token::Divide);
208 }
209 '|' => {
210 chars.next();
211 if chars.peek() == Some(&'|') {
212 chars.next();
213 tokens.push(Token::Or);
214 } else {
215 tokens.push(Token::Pipe);
216 }
217 }
218 '^' => {
219 chars.next();
220 tokens.push(Token::Caret);
221 }
222 '?' => {
223 chars.next();
224 if chars.peek().is_some_and(|c| c.is_ascii_alphabetic()) {
225 let var = self.parse_identifier(&mut chars);
226 tokens.push(Token::Variable(var));
227 } else {
228 tokens.push(Token::Question);
229 }
230 continue;
231 }
232 '*' => {
233 chars.next();
234 tokens.push(Token::Star);
235 }
236 '!' => {
237 chars.next();
238 if chars.peek() == Some(&'=') {
239 chars.next();
240 tokens.push(Token::NotEqual);
241 } else {
242 tokens.push(Token::Bang);
243 }
244 continue;
245 }
246 '&' => {
247 chars.next();
248 if chars.peek() == Some(&'&') {
249 chars.next();
250 tokens.push(Token::And);
251 } else {
252 return Err(anyhow!("Unexpected '&' - did you mean '&&'?"));
253 }
254 continue;
255 }
256 '$' => {
257 chars.next();
258 let var = self.parse_identifier(&mut chars);
259 tokens.push(Token::Variable(var));
260 }
261 '"' | '\'' => {
262 let quote = ch;
263 chars.next();
264 let mut literal = String::new();
265 while let Some(&ch) = chars.peek() {
266 chars.next();
267 if ch == quote {
268 break;
269 }
270 if ch == '\\' {
271 if let Some(&escaped) = chars.peek() {
272 chars.next();
273 match escaped {
274 'n' => literal.push('\n'),
275 't' => literal.push('\t'),
276 'r' => literal.push('\r'),
277 '\\' => literal.push('\\'),
278 '\'' => literal.push('\''),
279 '"' => literal.push('"'),
280 _ => {
281 literal.push('\\');
282 literal.push(escaped);
283 }
284 }
285 }
286 } else {
287 literal.push(ch);
288 }
289 }
290 // Optional RDF literal suffix: a language tag (`@ja`, with
291 // subtags such as `@ja-JP`) or an explicit datatype
292 // (`^^<iri>` / `^^prefix:local`). A plain literal keeps the
293 // simple `StringLiteral` token so existing call sites are
294 // unaffected.
295 if chars.peek() == Some(&'@') {
296 chars.next();
297 let mut lang = String::new();
298 while let Some(&c) = chars.peek() {
299 if c.is_ascii_alphanumeric() || c == '-' {
300 lang.push(c);
301 chars.next();
302 } else {
303 break;
304 }
305 }
306 tokens.push(Token::RdfLiteral {
307 value: literal,
308 language: Some(lang),
309 datatype: None,
310 });
311 } else if chars.peek() == Some(&'^') {
312 chars.next();
313 if chars.peek() == Some(&'^') {
314 chars.next();
315 let datatype = self.parse_datatype_iri(&mut chars);
316 tokens.push(Token::RdfLiteral {
317 value: literal,
318 language: None,
319 datatype: Some(datatype),
320 });
321 } else {
322 // A lone `^` after a string is not a datatype marker;
323 // keep the literal and emit the caret separately.
324 tokens.push(Token::StringLiteral(literal));
325 tokens.push(Token::Caret);
326 }
327 } else {
328 tokens.push(Token::StringLiteral(literal));
329 }
330 }
331 '_' => {
332 chars.next();
333 if chars.peek() == Some(&':') {
334 chars.next();
335 let id = self.parse_identifier(&mut chars);
336 tokens.push(Token::BlankNode(id));
337 } else {
338 let mut id = "_".to_string();
339 id.push_str(&self.parse_identifier(&mut chars));
340 tokens.push(self.classify_identifier(&id));
341 }
342 }
343 _ if ch.is_ascii_alphabetic() || ch == '_' => {
344 let identifier = self.parse_identifier(&mut chars);
345 tokens.push(self.classify_identifier(&identifier));
346 }
347 _ if ch.is_ascii_digit() => {
348 let number = self.parse_number(&mut chars);
349 tokens.push(Token::NumericLiteral(number));
350 }
351 _ => {
352 chars.next();
353 }
354 }
355 }
356 tokens.push(Token::Eof);
357 self.tokens = tokens;
358 self.position = 0;
359 Ok(())
360 }
361 pub(super) fn parse_identifier(
362 &self,
363 chars: &mut std::iter::Peekable<std::str::Chars>,
364 ) -> String {
365 let mut identifier = String::new();
366 let mut found_colon = false;
367 while let Some(&ch) = chars.peek() {
368 if ch.is_ascii_alphanumeric() || ch == '_' || ch == '-' || ch == '.' {
369 identifier.push(ch);
370 chars.next();
371 } else if ch == ':' && !found_colon {
372 identifier.push(ch);
373 chars.next();
374 found_colon = true;
375 } else {
376 break;
377 }
378 }
379 identifier
380 }
381 /// Read the datatype that follows a `^^` marker, PRESERVING how it was
382 /// written so resolution treats it correctly:
383 ///
384 /// * `<iri>` → [`DatatypeRef::Iri`] with the brackets stripped — an
385 /// absolute IRI used verbatim (so `^^<urn:x>` / `^^<tag:y>` are honoured,
386 /// never prefix-resolved).
387 /// * `prefix:local` → [`DatatypeRef::Prefixed`] — resolved against the
388 /// declared prefixes at parse time.
389 pub(super) fn parse_datatype_iri(
390 &self,
391 chars: &mut std::iter::Peekable<std::str::Chars>,
392 ) -> DatatypeRef {
393 if chars.peek() == Some(&'<') {
394 chars.next();
395 let mut iri = String::new();
396 while let Some(&c) = chars.peek() {
397 chars.next();
398 if c == '>' {
399 break;
400 }
401 iri.push(c);
402 }
403 DatatypeRef::Iri(iri)
404 } else {
405 DatatypeRef::Prefixed(self.parse_identifier(chars))
406 }
407 }
408 /// Scan a single SPARQL numeric literal, consuming ONLY the characters that
409 /// form a valid number so terminators and operators are left in the stream:
410 ///
411 /// * a trailing `.` with no following digit is a statement terminator, not a
412 /// decimal point (`:s :p 30. ?x …` → number `30`, then `.`), so it is not
413 /// consumed;
414 /// * `+`/`-` are only accepted immediately after an exponent marker
415 /// (`1e-3`), never as a leading sign or an infix operator — so `5-3` /
416 /// `5+2` tokenise as subtraction/addition, not a single malformed number;
417 /// * at most one decimal point and one exponent are accepted.
418 ///
419 /// A leading sign, when present, is handled by the caller before this is
420 /// invoked; here the first character is always a digit or `.`.
421 pub(super) fn parse_number(&self, chars: &mut std::iter::Peekable<std::str::Chars>) -> String {
422 let mut number = String::new();
423 // Integer part (digits).
424 while let Some(&ch) = chars.peek() {
425 if ch.is_ascii_digit() {
426 number.push(ch);
427 chars.next();
428 } else {
429 break;
430 }
431 }
432 // Optional fractional part: a '.' is only part of the number when it is
433 // followed by a digit; otherwise it is a statement terminator.
434 if chars.peek() == Some(&'.') {
435 let mut lookahead = chars.clone();
436 lookahead.next(); // skip the '.'
437 if matches!(lookahead.peek(), Some(c) if c.is_ascii_digit()) {
438 number.push('.');
439 chars.next();
440 while let Some(&ch) = chars.peek() {
441 if ch.is_ascii_digit() {
442 number.push(ch);
443 chars.next();
444 } else {
445 break;
446 }
447 }
448 }
449 }
450 // Optional exponent: 'e'/'E', an optional sign, then required digits.
451 if matches!(chars.peek(), Some(&'e') | Some(&'E')) {
452 let mut lookahead = chars.clone();
453 lookahead.next(); // skip the exponent marker
454 if matches!(lookahead.peek(), Some(&'+') | Some(&'-')) {
455 lookahead.next();
456 }
457 if matches!(lookahead.peek(), Some(c) if c.is_ascii_digit()) {
458 // Commit: copy the exponent marker, optional sign and digits.
459 number.push(chars.next().unwrap_or('e'));
460 if matches!(chars.peek(), Some(&'+') | Some(&'-')) {
461 if let Some(sign) = chars.next() {
462 number.push(sign);
463 }
464 }
465 while let Some(&ch) = chars.peek() {
466 if ch.is_ascii_digit() {
467 number.push(ch);
468 chars.next();
469 } else {
470 break;
471 }
472 }
473 }
474 }
475 number
476 }
477 pub(super) fn parse_query(&mut self) -> Result<Query> {
478 let mut query = Query {
479 query_type: QueryType::Select,
480 select_variables: Vec::new(),
481 where_clause: Algebra::Zero,
482 order_by: Vec::new(),
483 group_by: Vec::new(),
484 having: None,
485 limit: None,
486 offset: None,
487 distinct: false,
488 reduced: false,
489 construct_template: Vec::new(),
490 prefixes: HashMap::new(),
491 base_iri: None,
492 dataset: DatasetClause::default(),
493 projection_items: Vec::new(),
494 describe_targets: Vec::new(),
495 describe_all: false,
496 };
497 self.skip_whitespace();
498 self.parse_prologue(&mut query)?;
499 self.skip_whitespace();
500 match self.peek() {
501 Some(Token::Select) => {
502 query.query_type = QueryType::Select;
503 self.parse_select_query(&mut query)?;
504 }
505 Some(Token::Construct) => {
506 query.query_type = QueryType::Construct;
507 self.parse_construct_query(&mut query)?;
508 }
509 Some(Token::Ask) => {
510 query.query_type = QueryType::Ask;
511 self.parse_ask_query(&mut query)?;
512 }
513 Some(Token::Describe) => {
514 query.query_type = QueryType::Describe;
515 self.parse_describe_query(&mut query)?;
516 }
517 _ => bail!("Expected query type (SELECT, CONSTRUCT, ASK, DESCRIBE)"),
518 }
519 // The whole token stream must be consumed: trailing tokens after a
520 // complete query (e.g. `SELECT * { ?s ?p ?o } garbage`) are a syntax
521 // error, not silently-dropped input.
522 self.skip_whitespace_and_newlines();
523 if !self.is_at_end() {
524 bail!("Unexpected trailing tokens after query: {:?}", self.peek());
525 }
526 Ok(query)
527 }
528 pub(super) fn parse_prologue(&mut self, query: &mut Query) -> Result<()> {
529 while let Some(token) = self.peek() {
530 match token {
531 Token::Prefix => {
532 self.advance();
533 let prefix = match self.peek() {
534 Some(Token::PrefixedName(prefix, local)) => {
535 if prefix.is_empty() && local.is_empty() {
536 self.advance();
537 String::new()
538 } else {
539 let p = prefix.clone();
540 self.advance();
541 p
542 }
543 }
544 Some(Token::Colon) => {
545 self.advance();
546 String::new()
547 }
548 _ => {
549 eprintln!("Debug: Got token: {:?}", self.peek());
550 bail!("Expected prefix name or colon after PREFIX")
551 }
552 };
553 let iri = self.expect_iri()?;
554 query.prefixes.insert(prefix.clone(), iri.clone());
555 self.prefixes.insert(prefix, iri);
556 }
557 Token::Base => {
558 self.advance();
559 let iri = self.expect_iri()?;
560 query.base_iri = Some(iri.clone());
561 self.base_iri = Some(iri);
562 }
563 Token::Newline => {
564 self.advance();
565 }
566 _ => break,
567 }
568 }
569 Ok(())
570 }
571 pub(super) fn parse_select_query(&mut self, query: &mut Query) -> Result<()> {
572 self.expect_token(Token::Select)?;
573 if self.match_token(&Token::Distinct) {
574 query.distinct = true;
575 } else if self.match_token(&Token::Reduced) {
576 query.reduced = true;
577 }
578 // `SELECT *`: the tokenizer emits `Token::Star` for `*`, so the legacy
579 // `Token::Multiply` check never matched and `SELECT *` failed to parse.
580 // Accept either. An empty `select_variables` (and empty
581 // `projection_items`) means "project all in-scope variables".
582 if self.match_token(&Token::Star) || self.match_token(&Token::Multiply) {
583 } else {
584 while !self.is_at_end()
585 && !matches!(self.peek(), Some(Token::Where) | Some(Token::From))
586 {
587 match self.peek() {
588 Some(Token::Variable(var)) => {
589 let variable = Variable::new(var.clone())?;
590 self.advance();
591 query.select_variables.push(variable.clone());
592 query
593 .projection_items
594 .push(ProjectionItem::Variable(variable));
595 }
596 // A parenthesized projection: `( Expression AS ?var )`,
597 // including SPARQL aggregates such as `(COUNT(*) AS ?n)`.
598 Some(Token::LeftParen) => {
599 let item = self.parse_projection_paren_item()?;
600 // The projected output variable is the alias; record it
601 // in `select_variables` too so the output column set is
602 // complete regardless of which field a consumer reads.
603 let alias = match &item {
604 ProjectionItem::Variable(v) => v.clone(),
605 ProjectionItem::Expression { alias, .. }
606 | ProjectionItem::Aggregate { alias, .. } => alias.clone(),
607 };
608 query.select_variables.push(alias);
609 query.projection_items.push(item);
610 }
611 _ => break,
612 }
613 }
614 }
615 self.parse_dataset_clause(&mut query.dataset)?;
616 self.skip_whitespace_and_newlines();
617 // The `WHERE` keyword is optional in a SPARQL 1.1 SELECT
618 // (`SELECT ?s { … }` and `SELECT * { … }` are both valid); only the
619 // group-graph-pattern braces are required. Mirror the ASK handling
620 // (`match_token`) rather than demanding the keyword. The projection loop
621 // above already stops on `{` (`Token::LeftBrace` hits its `_ => break`),
622 // so the brace that opens the pattern is still available here.
623 self.match_token(&Token::Where);
624 // A newline may separate the (optional) `WHERE` keyword from the
625 // group's opening `{`, e.g. `SELECT ?s WHERE\n{ … }` — skip it before
626 // the brace lookahead, same as the other query heads.
627 self.skip_whitespace_and_newlines();
628 self.expect_token(Token::LeftBrace)?;
629 query.where_clause = self.parse_group_graph_pattern()?;
630 self.expect_token(Token::RightBrace)?;
631 self.parse_solution_modifiers(query)?;
632 Ok(())
633 }
634 pub(super) fn parse_describe_query(&mut self, query: &mut Query) -> Result<()> {
635 self.expect_token(Token::Describe)?;
636 self.skip_whitespace_and_newlines();
637 // `DESCRIBE *` describes every in-scope variable binding; it takes no
638 // explicit target list.
639 if self.match_token(&Token::Star) || self.match_token(&Token::Multiply) {
640 query.describe_all = true;
641 } else {
642 // `DESCRIBE VarOrIri+`: one or more IRIs and/or variables. Prefixed
643 // names are expanded against the prologue exactly like other term
644 // positions; the raw targets are RETAINED in `describe_targets`.
645 loop {
646 self.skip_whitespace_and_newlines();
647 match self.peek() {
648 Some(Token::Variable(var)) => {
649 let variable = Variable::new(var.clone())?;
650 self.advance();
651 query
652 .describe_targets
653 .push(DescribeTarget::Variable(variable.clone()));
654 query.select_variables.push(variable);
655 }
656 Some(Token::Iri(iri)) => {
657 let iri = iri.clone();
658 self.advance();
659 query
660 .describe_targets
661 .push(DescribeTarget::Iri(NamedNode::new_unchecked(iri)));
662 }
663 Some(Token::PrefixedName(prefix, local)) => {
664 let prefix = prefix.clone();
665 let local = local.clone();
666 self.advance();
667 let full_iri = self.resolve_prefixed_name(&prefix, &local)?;
668 query
669 .describe_targets
670 .push(DescribeTarget::Iri(NamedNode::new_unchecked(full_iri)));
671 }
672 _ => break,
673 }
674 }
675 if query.describe_targets.is_empty() {
676 bail!("DESCRIBE requires at least one IRI or variable target, or '*'");
677 }
678 }
679 // Skip any newline(s) between the target list (or `*`) and the
680 // dataset clause — mirrors the CONSTRUCT/SELECT/ASK hardening so
681 // `DESCRIBE ?x\nWHERE { … }` (targets on one line, dataset/WHERE on
682 // the next) does not fail with a spurious "Expected X, found
683 // Newline". `parse_dataset_clause` already skips at each of its own
684 // lookaheads, but the skip here also covers a newline directly after
685 // the target list when there is no dataset clause at all.
686 self.skip_whitespace_and_newlines();
687 self.parse_dataset_clause(&mut query.dataset)?;
688 self.skip_whitespace_and_newlines();
689 // `WhereClause ::= 'WHERE'? GroupGraphPattern` — the WHERE keyword is
690 // optional, so accept `DESCRIBE ?x { … }` as well as
691 // `DESCRIBE ?x WHERE { … }`.
692 if self.match_token(&Token::Where) {
693 self.skip_whitespace_and_newlines();
694 self.expect_token(Token::LeftBrace)?;
695 query.where_clause = self.parse_group_graph_pattern()?;
696 self.expect_token(Token::RightBrace)?;
697 } else if self.match_token(&Token::LeftBrace) {
698 query.where_clause = self.parse_group_graph_pattern()?;
699 self.expect_token(Token::RightBrace)?;
700 }
701 self.parse_solution_modifiers(query)?;
702 Ok(())
703 }
704 pub(super) fn parse_group_graph_pattern(&mut self) -> Result<Algebra> {
705 // A group graph pattern is a sequence of graph patterns interleaved with
706 // `FILTER` / `BIND` modifiers, and the two modifiers scope DIFFERENTLY:
707 //
708 // * `FILTER` constrains the WHOLE group regardless of its textual
709 // position, so bare filters are collected and applied once, wrapping
710 // the fully-joined group (SPARQL 1.1 §18.2.2 "collect FILTERs").
711 //
712 // * `BIND` is POSITIONAL: `BIND(expr AS ?v)` extends the solution
713 // produced by the elements written BEFORE it, and elements written
714 // AFTER it join against the extended solution. `{ ?s ?p ?o .
715 // BIND(?o AS ?x) . ?x ?q ?r }` therefore means
716 // `Join(Extend(BGP(?s ?p ?o), ?x, ?o), BGP(?x ?q ?r))`. Deferring
717 // the `BIND` to the group end (as `FILTER` is deferred) would join
718 // both BGPs first and only then extend, letting the second BGP bind
719 // `?x` and be silently mis-joined/overwritten. A leading `BIND`
720 // extends the unit table (join identity), so `{ BIND(1 AS ?v) … }`
721 // still works.
722 //
723 // Modifiers are recognised SYNTACTICALLY, by the leading `FILTER` /
724 // `BIND` token of THIS group — never structurally by matching a
725 // `Filter/Extend { pattern: Table, .. }` shape. A nested single-element
726 // group such as `{ ?s ?p ?o { FILTER(?o > 5) } }` also parses to
727 // `Filter { pattern: Table, .. }`, but it is a JOIN operand of the outer
728 // group, not an outer-group modifier, and must not be re-scoped.
729 //
730 // A top-level `UNION` needs no special-casing: it is parsed by
731 // `parse_graph_pattern_or_union` as one element of the loop below, so a
732 // trailing `FILTER`/`BIND` after a union is still scoped to the group.
733 let mut acc: Option<Algebra> = None;
734 let mut filters: Vec<Algebra> = Vec::new();
735 while !self.is_at_end() && !matches!(self.peek(), Some(Token::RightBrace)) {
736 self.skip_whitespace_and_newlines();
737 if self.is_at_end() || matches!(self.peek(), Some(Token::RightBrace)) {
738 break;
739 }
740 if matches!(self.peek(), Some(Token::Filter)) {
741 // Bare FILTER: whole-group scope, deferred to the group end.
742 filters.push(self.parse_filter_pattern()?);
743 } else if matches!(self.peek(), Some(Token::Bind)) {
744 // Bare BIND: positional Extend over the algebra accumulated so
745 // far (the unit table when the BIND leads the group).
746 match self.parse_bind_pattern()? {
747 Algebra::Extend { variable, expr, .. } => {
748 let base = acc.take().unwrap_or(Algebra::Table);
749 acc = Some(Algebra::Extend {
750 pattern: Box::new(base),
751 variable,
752 expr,
753 });
754 }
755 other => bail!("BIND parser returned unexpected algebra: {other:?}"),
756 }
757 } else {
758 let pattern = self.parse_graph_pattern_or_union()?;
759 acc = Some(match acc.take() {
760 Some(prev) => compose_group_element(prev, pattern),
761 None => pattern,
762 });
763 }
764 self.match_token(&Token::Dot);
765 self.skip_whitespace_and_newlines();
766 }
767 let mut result = acc.unwrap_or(Algebra::Table);
768 for modifier in filters {
769 match modifier {
770 Algebra::Filter { condition, .. } => {
771 result = Algebra::Filter {
772 pattern: Box::new(result),
773 condition,
774 };
775 }
776 other => bail!("FILTER parser returned unexpected algebra: {other:?}"),
777 }
778 }
779 Ok(result)
780 }
781 pub(super) fn parse_graph_pattern_or_union(&mut self) -> Result<Algebra> {
782 let left = self.parse_graph_pattern()?;
783 self.skip_whitespace_and_newlines();
784 if self.match_token(&Token::Union) {
785 self.skip_whitespace_and_newlines();
786 let right = self.parse_graph_pattern_or_union()?;
787 return Ok(Algebra::Union {
788 left: Box::new(left),
789 right: Box::new(right),
790 });
791 }
792 Ok(left)
793 }
794 pub(super) fn parse_basic_graph_pattern(&mut self) -> Result<Algebra> {
795 let mut triples = Vec::new();
796 while !self.is_at_end() {
797 self.skip_whitespace_and_newlines();
798 if self.is_pattern_end() {
799 break;
800 }
801 if matches!(self.peek(), Some(Token::Newline)) {
802 self.advance();
803 continue;
804 }
805 triples.extend(self.parse_triples_same_subject()?);
806 if !self.match_token(&Token::Dot) {
807 break;
808 }
809 }
810 Ok(Algebra::Bgp(triples))
811 }
812 /// Parse a `TriplesSameSubjectPath`: one subject followed by a
813 /// predicate-object list, expanding the SPARQL 1.1 abbreviations `;`
814 /// (predicate-object list) and `,` (object list) into every triple that
815 /// shares the subject. `{ ?s :p ?o ; :q ?r , ?t }` therefore yields the
816 /// three triples `(?s :p ?o)`, `(?s :q ?r)`, `(?s :q ?t)`.
817 pub(super) fn parse_triples_same_subject(&mut self) -> Result<Vec<TriplePattern>> {
818 self.skip_whitespace_and_newlines();
819 let mut triples = Vec::new();
820 // The subject may be a `TriplesNode` — a blank-node property list
821 // `[ … ]` or an RDF collection `( … )` — which expands to its own
822 // triples and yields a fresh anchor node. Its trailing property list is
823 // OPTIONAL (`[ :p :o ] :q :r`, but also the standalone `[ :p :o ] .` and
824 // `( :a :b ) .`), so only parse one when a verb actually follows.
825 if matches!(
826 self.peek(),
827 Some(Token::LeftBracket) | Some(Token::LeftParen)
828 ) {
829 let subject = self.parse_triples_node(&mut triples)?;
830 self.skip_whitespace_and_newlines();
831 if self.is_verb_start() {
832 self.parse_predicate_object_list(&subject, &mut triples)?;
833 }
834 } else {
835 let subject = self.parse_term()?;
836 self.parse_predicate_object_list(&subject, &mut triples)?;
837 }
838 Ok(triples)
839 }
840 /// Parse a `PropertyListPathNotEmpty`:
841 /// `verb objectList ( ';' ( verb objectList )? )*`. A trailing `;` (and a
842 /// repeated `;;`) with no following verb is valid SPARQL and tolerated.
843 pub(super) fn parse_predicate_object_list(
844 &mut self,
845 subject: &Term,
846 out: &mut Vec<TriplePattern>,
847 ) -> Result<()> {
848 loop {
849 self.skip_whitespace_and_newlines();
850 let predicate = self.parse_verb()?;
851 self.parse_object_list(subject, &predicate, out)?;
852 self.skip_whitespace_and_newlines();
853 if !self.match_token(&Token::Semicolon) {
854 break;
855 }
856 // After ';', a further `verb objectList` is optional. Skip any run of
857 // extra `;` and stop when no verb follows (a trailing semicolon).
858 self.skip_whitespace_and_newlines();
859 while self.match_token(&Token::Semicolon) {
860 self.skip_whitespace_and_newlines();
861 }
862 if !self.is_verb_start() {
863 break;
864 }
865 }
866 Ok(())
867 }
868 /// Parse an `ObjectListPath`: one or more objects separated by `,`, emitting
869 /// one triple per object with the shared subject and predicate.
870 pub(super) fn parse_object_list(
871 &mut self,
872 subject: &Term,
873 predicate: &Term,
874 out: &mut Vec<TriplePattern>,
875 ) -> Result<()> {
876 loop {
877 self.skip_whitespace_and_newlines();
878 // An object is a `GraphNode`: a plain term OR a nested `TriplesNode`
879 // (`[ … ]` / `( … )`), whose expansion triples are appended to `out`.
880 let object = self.parse_graph_node(out)?;
881 out.push(TriplePattern::new(
882 subject.clone(),
883 predicate.clone(),
884 object,
885 ));
886 self.skip_whitespace_and_newlines();
887 if !self.match_token(&Token::Comma) {
888 break;
889 }
890 }
891 Ok(())
892 }
893 /// Parse a verb (predicate): a property path (`IRI`, `a`, `p1/p2`, `p+`, …)
894 /// or a plain variable predicate.
895 pub(super) fn parse_verb(&mut self) -> Result<Term> {
896 if self.is_property_path_start() {
897 Ok(Term::PropertyPath(self.parse_property_path()?))
898 } else {
899 self.parse_term()
900 }
901 }
902 /// Whether the current token can begin a verb (predicate): a property-path
903 /// start (`IRI` / prefixed name / `a` / `^` / `(` / `!`) or a variable.
904 pub(super) fn is_verb_start(&self) -> bool {
905 self.is_property_path_start() || matches!(self.peek(), Some(Token::Variable(_)))
906 }
907 /// Parse primary property path expressions
908 pub(super) fn parse_property_path_primary(&mut self) -> Result<PropertyPath> {
909 match self.peek() {
910 Some(Token::Caret) => {
911 self.advance();
912 let path = self.parse_property_path_primary()?;
913 Ok(PropertyPath::inverse(path))
914 }
915 Some(Token::Iri(iri)) => {
916 let iri = iri.clone();
917 self.advance();
918 Ok(PropertyPath::iri(NamedNode::new_unchecked(iri)))
919 }
920 Some(Token::PrefixedName(prefix, local)) => {
921 let prefix = prefix.clone();
922 let local = local.clone();
923 self.advance();
924 let full_iri = self.resolve_prefixed_name(&prefix, &local)?;
925 Ok(PropertyPath::iri(NamedNode::new_unchecked(full_iri)))
926 }
927 Some(Token::A) => {
928 // `a` is the SPARQL shorthand for the rdf:type predicate.
929 self.advance();
930 Ok(PropertyPath::iri(NamedNode::new_unchecked(
931 "http://www.w3.org/1999/02/22-rdf-syntax-ns#type",
932 )))
933 }
934 Some(Token::Variable(var)) => {
935 let var = var.clone();
936 self.advance();
937 Ok(PropertyPath::Variable(Variable::new(var)?))
938 }
939 Some(Token::LeftParen) => {
940 self.advance();
941 let path = self.parse_property_path()?;
942 self.expect_token(Token::RightParen)?;
943 Ok(path)
944 }
945 Some(Token::Bang) => {
946 self.advance();
947 self.expect_token(Token::LeftParen)?;
948 let mut negated_paths = Vec::new();
949 loop {
950 negated_paths.push(self.parse_property_path_primary()?);
951 if !self.match_token(&Token::Pipe) {
952 break;
953 }
954 }
955 self.expect_token(Token::RightParen)?;
956 Ok(PropertyPath::NegatedPropertySet(negated_paths))
957 }
958 _ => bail!("Expected property path expression"),
959 }
960 }
961}