1use std::collections::HashMap;
26
27use crate::sparql_ast::{
28 Expression, ExpressionId, Pattern, PatternId, SparqlQuery, SparqlQueryContext, VariableId,
29};
30
31fn render_tokens(tokens: &[Token]) -> String {
36 let mut parts: Vec<String> = Vec::with_capacity(tokens.len());
37 for t in tokens {
38 parts.push(match t {
39 Token::Var(v) => v.clone(),
40 Token::Iri(i) => format!("<{i}>"),
41 Token::Prefixed(p, l) => format!("{p}:{l}"),
42 Token::Str {
43 value,
44 lang,
45 datatype,
46 } => {
47 let mut s = format!("\"{value}\"");
48 if let Some(l) = lang {
49 s.push('@');
50 s.push_str(l);
51 } else if let Some(d) = datatype {
52 if d.contains("://") {
53 s.push_str(&format!("^^<{d}>"));
54 } else {
55 s.push_str(&format!("^^{d}"));
56 }
57 }
58 s
59 }
60 Token::Num(n) => n.clone(),
61 Token::Bool(b) => (if *b { "true" } else { "false" }).to_string(),
62 Token::Word(w) => w.clone(),
63 Token::Punct(c) => c.to_string(),
64 Token::Op(o) => (*o).to_string(),
65 Token::StarOpen => "<<".to_string(),
66 Token::StarClose => ">>".to_string(),
67 });
68 }
69 parts.join(" ")
70}
71use crate::sparql_library::sparql_grammar::expr::parse_expression;
72use crate::sparql_library::sparql_grammar::tokenizer::{tokenize, Token};
73
74pub fn parse_where_group(
77 input: &str,
78 ctx: &mut SparqlQueryContext,
79 prefixes: &HashMap<String, String>,
80) -> Result<PatternId, String> {
81 let tokens = tokenize(input)?;
82 let mut p = PatternParser {
83 tokens: &tokens,
84 pos: 0,
85 ctx,
86 prefixes,
87 };
88 if let Some(Token::Word(w)) = p.peek() {
90 if w.eq_ignore_ascii_case("WHERE") {
91 p.pos += 1;
92 }
93 }
94 p.parse_group()
95}
96
97pub(crate) fn parse_group_tokens(
102 tokens: &[Token],
103 pos: usize,
104 ctx: &mut SparqlQueryContext,
105 prefixes: &HashMap<String, String>,
106) -> Result<(PatternId, usize), String> {
107 let mut p = PatternParser {
108 tokens,
109 pos,
110 ctx,
111 prefixes,
112 };
113 let id = p.parse_group()?;
114 Ok((id, p.pos))
115}
116
117enum ChildSpec {
120 Triple {
121 s: u64,
122 p: u64,
123 o: u64,
124 },
125 StarTriple {
126 is: u64,
127 ip: u64,
128 io: u64,
129 op: u64,
130 oo: u64,
131 },
132 Optional(PatternId),
133 Union(PatternId, PatternId),
134 Minus(PatternId),
135 Service {
136 endpoint: u64,
137 inner: PatternId,
138 },
139 Graph {
140 graph_var_or_id: u64,
141 inner: PatternId,
142 },
143 SubSelect {
144 query_id: u16,
145 },
146}
147
148struct PatternParser<'a> {
149 tokens: &'a [Token],
150 pos: usize,
151 ctx: &'a mut SparqlQueryContext,
152 prefixes: &'a HashMap<String, String>,
153}
154
155impl<'a> PatternParser<'a> {
156 fn peek(&self) -> Option<&Token> {
157 self.tokens.get(self.pos)
158 }
159
160 fn eat_punct(&mut self, c: char) -> bool {
161 if matches!(self.peek(), Some(Token::Punct(p)) if *p == c) {
162 self.pos += 1;
163 true
164 } else {
165 false
166 }
167 }
168
169 fn expect_punct(&mut self, c: char) -> Result<(), String> {
170 if self.eat_punct(c) {
171 Ok(())
172 } else {
173 Err(format!("expected '{c}' at token {}", self.pos))
174 }
175 }
176
177 fn peek_word_ci(&self, kw: &str) -> bool {
178 matches!(self.peek(), Some(Token::Word(w)) if w.eq_ignore_ascii_case(kw))
179 }
180
181 fn parse_group(&mut self) -> Result<PatternId, String> {
183 self.expect_punct('{')?;
184 let (specs, filters, binds) = self.parse_group_body()?;
185 let mut root = self.materialize(specs)?;
186 for (expr_id, var) in binds {
191 root = self.ctx.alloc_pattern(Pattern::Bind {
192 pattern: root,
193 var,
194 expression: expr_id,
195 })?;
196 }
197 for expr_id in filters {
198 root = self.ctx.alloc_pattern(Pattern::Filter {
199 pattern: root,
200 expression: expr_id,
201 })?;
202 }
203 Ok(root)
204 }
205
206 #[allow(clippy::type_complexity)]
210 fn parse_group_body(
211 &mut self,
212 ) -> Result<
213 (
214 Vec<ChildSpec>,
215 Vec<ExpressionId>,
216 Vec<(ExpressionId, VariableId)>,
217 ),
218 String,
219 > {
220 let mut specs: Vec<ChildSpec> = Vec::new();
221 let mut filters: Vec<ExpressionId> = Vec::new();
222 let mut binds: Vec<(ExpressionId, VariableId)> = Vec::new();
223
224 loop {
225 match self.peek() {
226 None => return Err("unterminated group (missing '}')".to_string()),
227 Some(Token::Punct('}')) => {
228 self.pos += 1;
229 break;
230 }
231 Some(Token::Punct('.')) => {
232 self.pos += 1; }
234 Some(Token::Word(w)) if w.eq_ignore_ascii_case("OPTIONAL") => {
235 self.pos += 1;
236 let inner = self.parse_group()?;
237 specs.push(ChildSpec::Optional(inner));
238 }
239 Some(Token::Word(w)) if w.eq_ignore_ascii_case("MINUS") => {
240 self.pos += 1;
241 let inner = self.parse_group()?;
242 specs.push(ChildSpec::Minus(inner));
243 }
244 Some(Token::Word(w)) if w.eq_ignore_ascii_case("SERVICE") => {
245 self.pos += 1;
246 if self.peek_word_ci("SILENT") {
248 self.pos += 1;
249 }
250 let endpoint = self.service_endpoint()?;
251 let inner = self.parse_group()?;
252 specs.push(ChildSpec::Service { endpoint, inner });
253 }
254 Some(Token::Word(w)) if w.eq_ignore_ascii_case("GRAPH") => {
255 self.pos += 1;
256 let graph_var_or_id = self.term()?;
261 let inner = self.parse_group()?;
262 specs.push(ChildSpec::Graph {
263 graph_var_or_id,
264 inner,
265 });
266 }
267 Some(Token::Word(w)) if w.eq_ignore_ascii_case("FILTER") => {
268 self.pos += 1;
269 let expr_id = self.parse_filter_expr()?;
270 filters.push(expr_id);
271 }
272 Some(Token::Word(w)) if w.eq_ignore_ascii_case("BIND") => {
273 self.pos += 1;
274 let (expr_id, var_id) = self.parse_bind()?;
275 binds.push((expr_id, var_id));
276 }
277 Some(Token::Punct('{'))
278 if matches!(self.tokens.get(self.pos + 1),
279 Some(Token::Word(w)) if w.eq_ignore_ascii_case("SELECT")) =>
280 {
281 let query_id = self.parse_sub_select()?;
283 specs.push(ChildSpec::SubSelect { query_id });
284 }
285 Some(Token::Punct('{')) => {
286 let left = self.parse_group()?;
289 if self.peek_word_ci("UNION") {
290 self.pos += 1;
291 let right = self.parse_group()?;
292 specs.push(ChildSpec::Union(left, right));
293 } else {
294 self.flatten_group_into(left, &mut specs, &mut filters, &mut binds);
299 }
300 }
301 Some(Token::StarOpen) => {
302 let spec = self.parse_star_triple()?;
303 specs.push(spec);
304 }
305 _ => {
306 let spec = self.parse_triple()?;
307 specs.push(spec);
308 }
309 }
310 }
311 Ok((specs, filters, binds))
312 }
313
314 fn materialize(&mut self, specs: Vec<ChildSpec>) -> Result<PatternId, String> {
317 if specs.is_empty() {
318 return Err("empty group graph pattern".to_string());
319 }
320 let start = self.ctx.pattern_count as u16;
321 let len = specs.len() as u16;
322 for spec in specs {
323 match spec {
324 ChildSpec::Triple { s, p, o } => {
325 self.ctx.alloc_pattern(Pattern::Triple {
326 subject: s,
327 predicate: p,
328 object: o,
329 })?;
330 }
331 ChildSpec::StarTriple { is, ip, io, op, oo } => {
332 self.ctx.alloc_pattern(Pattern::StarTriple {
333 inner_subject: is,
334 inner_predicate: ip,
335 inner_object: io,
336 outer_predicate: op,
337 outer_object: oo,
338 })?;
339 }
340 ChildSpec::Optional(inner) => {
341 self.ctx.alloc_pattern(Pattern::Optional { inner })?;
342 }
343 ChildSpec::Union(left, right) => {
344 self.ctx.alloc_pattern(Pattern::Union { left, right })?;
345 }
346 ChildSpec::Minus(inner) => {
347 self.ctx.alloc_pattern(Pattern::Minus { inner })?;
348 }
349 ChildSpec::Service { endpoint, inner } => {
350 self.ctx.alloc_pattern(Pattern::Service {
351 endpoint_did_id: endpoint,
352 inner_pattern: inner,
353 })?;
354 }
355 ChildSpec::Graph {
356 graph_var_or_id,
357 inner,
358 } => {
359 self.ctx.alloc_pattern(Pattern::Graph {
360 graph_var_or_id,
361 inner,
362 })?;
363 }
364 ChildSpec::SubSelect { query_id } => {
365 self.ctx.alloc_pattern(Pattern::SubSelect { query_id })?;
366 }
367 }
368 }
369 if len == 1 {
370 Ok(start)
371 } else {
372 self.ctx.alloc_pattern(Pattern::Group {
373 start_idx: start,
374 len,
375 })
376 }
377 }
378
379 fn parse_filter_expr(&mut self) -> Result<ExpressionId, String> {
382 let not_exists = self.peek_word_ci("NOT")
385 && matches!(self.tokens.get(self.pos + 1),
386 Some(Token::Word(w)) if w.eq_ignore_ascii_case("EXISTS"));
387 if self.peek_word_ci("EXISTS") || not_exists {
388 return self.parse_exists_constraint();
389 }
390
391 if !matches!(self.peek(), Some(Token::Punct('('))) {
393 return Err("expected '(' after FILTER".to_string());
394 }
395 let start = self.pos + 1;
396 let mut depth = 0i32;
397 let mut i = self.pos;
398 while i < self.tokens.len() {
399 match &self.tokens[i] {
400 Token::Punct('(') => depth += 1,
401 Token::Punct(')') => {
402 depth -= 1;
403 if depth == 0 {
404 break;
405 }
406 }
407 _ => {}
408 }
409 i += 1;
410 }
411 if depth != 0 {
412 return Err("unbalanced parentheses in FILTER".to_string());
413 }
414 let expr_tokens = &self.tokens[start..i];
415 self.pos = i + 1; parse_expression(expr_tokens, self.ctx, self.prefixes)
417 }
418
419 fn parse_exists_constraint(&mut self) -> Result<ExpressionId, String> {
422 let mut negated = false;
423 if self.peek_word_ci("NOT") {
424 self.pos += 1;
425 negated = true;
426 }
427 if !self.peek_word_ci("EXISTS") {
428 return Err("expected EXISTS".to_string());
429 }
430 self.pos += 1;
431 let pattern = self.parse_group()?;
432 self.ctx
433 .alloc_expression(Expression::Exists { pattern, negated })
434 }
435
436 fn matching_brace(&self, open: usize) -> Result<usize, String> {
438 let mut depth = 0i32;
439 for (i, t) in self.tokens.iter().enumerate().skip(open) {
440 match t {
441 Token::Punct('{') => depth += 1,
442 Token::Punct('}') => {
443 depth -= 1;
444 if depth == 0 {
445 return Ok(i);
446 }
447 }
448 _ => {}
449 }
450 }
451 Err("unbalanced braces in sub-SELECT".to_string())
452 }
453
454 fn parse_sub_select(&mut self) -> Result<u16, String> {
461 let open = self.pos;
462 let close = self.matching_brace(open)?;
463 let query_str = render_tokens(&self.tokens[open + 1..close]);
464 self.pos = close + 1; let select = crate::sparql_library::sparql_parser::parse_select_query(
466 &query_str,
467 self.ctx,
468 self.prefixes,
469 )?;
470 self.ctx.alloc_subquery(SparqlQuery::Select(select))
471 }
472
473 fn parse_bind(&mut self) -> Result<(ExpressionId, VariableId), String> {
482 if !matches!(self.peek(), Some(Token::Punct('('))) {
483 return Err("expected '(' after BIND".to_string());
484 }
485 let start = self.pos + 1;
487 let mut depth = 0i32;
488 let mut i = self.pos;
489 while i < self.tokens.len() {
490 match &self.tokens[i] {
491 Token::Punct('(') => depth += 1,
492 Token::Punct(')') => {
493 depth -= 1;
494 if depth == 0 {
495 break;
496 }
497 }
498 _ => {}
499 }
500 i += 1;
501 }
502 if depth != 0 {
503 return Err("unbalanced parentheses in BIND".to_string());
504 }
505 let span = &self.tokens[start..i];
506 self.pos = i + 1; let as_pos = span
510 .iter()
511 .position(|t| matches!(t, Token::Word(w) if w.eq_ignore_ascii_case("AS")))
512 .ok_or("BIND requires the form `BIND(expr AS ?var)`")?;
513 let expr_tokens = &span[..as_pos];
514 let var_tokens = &span[as_pos + 1..];
515 if expr_tokens.is_empty() {
516 return Err("BIND has no expression before AS".to_string());
517 }
518 let var_name = match var_tokens {
519 [Token::Var(name)] => name.clone(),
520 _ => return Err("BIND target must be a single ?variable".to_string()),
521 };
522 let expr_id = parse_expression(expr_tokens, self.ctx, self.prefixes)?;
523 let var_id = self.ctx.register_variable(&var_name)?;
524 Ok((expr_id, var_id))
525 }
526
527 fn parse_triple(&mut self) -> Result<ChildSpec, String> {
528 let s = self.term()?;
529 let p = self.term()?;
530 while matches!(self.peek(), Some(Token::Op(o)) if *o == "+" || *o == "*") {
535 self.pos += 1;
536 }
537 let o = self.term()?;
538 Ok(ChildSpec::Triple { s, p, o })
539 }
540
541 fn service_endpoint(&mut self) -> Result<u64, String> {
549 const DID_PREFIX: u64 = 0x8000_0000_0000_0000;
550 let tok = self
551 .tokens
552 .get(self.pos)
553 .ok_or_else(|| "expected SERVICE endpoint".to_string())?
554 .clone();
555 self.pos += 1;
556 let iri = match tok {
557 Token::Iri(iri) => iri,
558 Token::Prefixed(prefix, local) => match self.prefixes.get(&prefix) {
559 Some(base) => format!("{base}{local}"),
560 None => format!("{prefix}:{local}"),
561 },
562 Token::Var(_) => {
563 return Err("dynamic SERVICE endpoint (a variable) is not supported yet".to_string())
564 }
565 other => return Err(format!("invalid SERVICE endpoint token: {other:?}")),
566 };
567 let lower = iri.to_ascii_lowercase();
568 if iri == "local:graph" {
569 Ok(DID_PREFIX)
570 } else if lower.starts_with("local:") || lower.starts_with("qualia:") || lower.starts_with("did:")
571 {
572 Ok(crate::lexicon::generate_60bit_token(iri.as_bytes()) | DID_PREFIX)
573 } else if lower.starts_with("http://") || lower.starts_with("https://") {
574 Err(format!(
575 "remote SERVICE endpoint <{iri}> is not supported — network egress is \
576 governance-gated; use a local: or qualia: endpoint"
577 ))
578 } else {
579 Ok(crate::lexicon::generate_60bit_token(iri.as_bytes()) | DID_PREFIX)
581 }
582 }
583
584 fn parse_star_triple(&mut self) -> Result<ChildSpec, String> {
585 self.pos += 1;
587 let is = self.term()?;
588 let ip = self.term()?;
589 let io = self.term()?;
590 if !matches!(self.peek(), Some(Token::StarClose)) {
591 return Err("expected '>>' in quoted triple pattern".to_string());
592 }
593 self.pos += 1;
594 let op = self.term()?;
595 let oo = self.term()?;
596 Ok(ChildSpec::StarTriple { is, ip, io, op, oo })
597 }
598
599 fn flatten_group_into(
604 &mut self,
605 id: PatternId,
606 specs: &mut Vec<ChildSpec>,
607 filters: &mut Vec<ExpressionId>,
608 binds: &mut Vec<(ExpressionId, VariableId)>,
609 ) {
610 let pat = self.ctx.patterns[id as usize];
611 match pat {
612 Pattern::Group { start_idx, len } => {
613 for i in start_idx..(start_idx + len) {
614 self.flatten_group_into(i, specs, filters, binds);
615 }
616 }
617 Pattern::Filter {
618 pattern,
619 expression,
620 } => {
621 filters.push(expression);
622 self.flatten_group_into(pattern, specs, filters, binds);
623 }
624 Pattern::Bind {
625 pattern,
626 var,
627 expression,
628 } => {
629 binds.push((expression, var));
630 self.flatten_group_into(pattern, specs, filters, binds);
631 }
632 Pattern::Triple {
633 subject,
634 predicate,
635 object,
636 } => specs.push(ChildSpec::Triple {
637 s: subject,
638 p: predicate,
639 o: object,
640 }),
641 Pattern::StarTriple {
642 inner_subject,
643 inner_predicate,
644 inner_object,
645 outer_predicate,
646 outer_object,
647 } => specs.push(ChildSpec::StarTriple {
648 is: inner_subject,
649 ip: inner_predicate,
650 io: inner_object,
651 op: outer_predicate,
652 oo: outer_object,
653 }),
654 Pattern::Union { left, right } => specs.push(ChildSpec::Union(left, right)),
655 Pattern::Optional { inner } => specs.push(ChildSpec::Optional(inner)),
656 Pattern::Minus { inner } => specs.push(ChildSpec::Minus(inner)),
657 Pattern::Graph {
658 graph_var_or_id,
659 inner,
660 } => specs.push(ChildSpec::Graph {
661 graph_var_or_id,
662 inner,
663 }),
664 Pattern::SubSelect { query_id } => specs.push(ChildSpec::SubSelect { query_id }),
665 _ => specs.push(ChildSpec::Optional(id)),
669 }
670 }
671
672 fn term(&mut self) -> Result<u64, String> {
675 let tok = self
676 .tokens
677 .get(self.pos)
678 .ok_or_else(|| "unexpected end of pattern (expected a term)".to_string())?
679 .clone();
680 self.pos += 1;
681 match tok {
682 Token::Var(name) => Ok(self.ctx.register_variable(&name)? as u64),
683 Token::Iri(iri) => Ok(crate::lexicon::generate_60bit_token(iri.as_bytes())),
684 Token::Prefixed(prefix, local) => {
685 let expanded = match self.prefixes.get(&prefix) {
686 Some(base) => format!("{base}{local}"),
687 None => format!("{prefix}:{local}"),
688 };
689 Ok(crate::lexicon::generate_60bit_token(expanded.as_bytes()))
690 }
691 Token::Str { value, .. } => Ok(crate::lexicon::generate_60bit_token(value.as_bytes())),
692 Token::Num(text) => Ok(text
693 .parse::<u64>()
694 .unwrap_or_else(|_| crate::lexicon::generate_60bit_token(text.as_bytes()))),
695 Token::Bool(b) => Ok(crate::lexicon::generate_60bit_token(if b {
696 b"true"
697 } else {
698 b"false"
699 })),
700 Token::Word(w) if w == "a" => Ok(crate::lexicon::generate_60bit_token(
701 b"http://www.w3.org/1999/02/22-rdf-syntax-ns#type",
702 )),
703 Token::Word(w) => Ok(crate::lexicon::generate_60bit_token(w.as_bytes())),
706 other => Err(format!("invalid term token: {other:?}")),
707 }
708 }
709}
710
711#[cfg(test)]
712mod tests {
713 use super::*;
714 use crate::sparql_ast::SparqlQueryContext;
715
716 fn root_pattern(input: &str) -> (SparqlQueryContext, Pattern) {
717 let mut ctx = SparqlQueryContext::new();
718 let id = parse_where_group(input, &mut ctx, &HashMap::new()).unwrap();
719 let pat = ctx.patterns[id as usize];
720 (ctx, pat)
721 }
722
723 #[test]
724 fn parses_optional() {
725 let (_ctx, pat) = root_pattern("{ ?s ?p ?o . OPTIONAL { ?s ?x ?y } }");
726 assert!(matches!(pat, Pattern::Group { len: 2, .. }));
728 }
729
730 #[test]
731 fn parses_union() {
732 let (ctx, pat) = root_pattern("{ { ?s ?p ?o } UNION { ?a ?b ?c } }");
733 assert!(matches!(pat, Pattern::Union { .. }), "got {pat:?}");
735 let _ = ctx;
736 }
737
738 #[test]
739 fn parses_minus() {
740 let (_ctx, pat) = root_pattern("{ ?s ?p ?o . MINUS { ?s ?x ?y } }");
741 assert!(matches!(pat, Pattern::Group { len: 2, .. }));
742 }
743
744 #[test]
745 fn parses_filter_in_group() {
746 let (_ctx, pat) = root_pattern("{ ?s ?p ?o . FILTER(?o >= 18) }");
747 assert!(matches!(pat, Pattern::Filter { .. }));
748 }
749
750 #[test]
751 fn parses_plain_bgp() {
752 let (_ctx, pat) = root_pattern("{ ?s ?p ?o . ?a ?b ?c }");
753 assert!(matches!(pat, Pattern::Group { len: 2, .. }));
754 }
755
756 #[test]
757 fn parses_local_service() {
758 let (_ctx, pat) = root_pattern("{ SERVICE <local:health> { ?s ?p ?o } }");
759 assert!(matches!(pat, Pattern::Service { .. }), "got {pat:?}");
760 }
761
762 #[test]
763 fn only_exact_reserved_local_graph_selects_the_default_graph() {
764 let (_, local) = root_pattern("{ SERVICE <local:graph> { ?s ?p ?o } }");
765 assert!(matches!(local, Pattern::Service { endpoint_did_id: 0x8000_0000_0000_0000, .. }));
766 for endpoint in ["local:health", "LOCAL:graph", "qualia:graph", "did:example:remote"] {
767 let (_, qualified) = root_pattern(&format!("{{ SERVICE <{endpoint}> {{ ?s ?p ?o }} }}"));
768 assert!(matches!(qualified, Pattern::Service { endpoint_did_id, .. } if endpoint_did_id != 0x8000_0000_0000_0000));
769 }
770 }
771
772 #[test]
773 fn remote_service_is_rejected() {
774 let mut ctx = SparqlQueryContext::new();
775 let err = parse_where_group(
776 "{ SERVICE <https://dbpedia.org/sparql> { ?s ?p ?o } }",
777 &mut ctx,
778 &HashMap::new(),
779 )
780 .unwrap_err();
781 assert!(err.contains("egress"), "got {err}");
782 }
783
784 #[test]
785 fn parses_bind_into_bind_node() {
786 let (ctx, pat) = root_pattern("{ ?s ?p ?o . BIND(?o AS ?x) }");
787 match pat {
789 Pattern::Bind { var, .. } => {
790 let x = ctx
792 .variable_hashes
793 .iter()
794 .position(|h| *h == crate::lexicon::generate_60bit_token(b"?x"))
795 .unwrap();
796 assert_eq!(var as usize, x);
797 }
798 other => panic!("expected Pattern::Bind, got {other:?}"),
799 }
800 }
801
802 #[test]
803 fn bind_requires_as_var_form() {
804 let mut ctx = SparqlQueryContext::new();
805 let err =
806 parse_where_group("{ ?s ?p ?o . BIND(?o) }", &mut ctx, &HashMap::new()).unwrap_err();
807 assert!(err.contains("AS"), "got {err}");
808 }
809}