qualia_core_db/sparql_library/sparql_grammar/
expr.rs

1//! SPARQL expression parser — precedence-climbing recursive descent over the
2//! token stream, producing `Expression` nodes into the `SparqlQueryContext`
3//! arena. Used for `FILTER`, `BIND`, and `HAVING` expressions.
4//!
5//! Precedence (lowest → highest), per the SPARQL 1.1 grammar:
6//! `||` < `&&` < (`=` `!=` `<` `<=` `>` `>=`) < (`+` `-`) < (`*` `/`) < unary < primary.
7//!
8//! ## Encoding note (matches the evaluator's model)
9//! `ExpressionEvaluator` maps both `Variable` and `Literal` to
10//! `EvalResult::Numeric(u64)`, and comparisons require both operands to be the
11//! same `EvalResult` variant. So a constant used in an expression (IRI, string,
12//! number, boolean) is encoded as `Expression::Literal(hash_or_value)` — using
13//! exactly the same term encoding the triple-pattern parser (`parse_term`) uses
14//! — so `?x = <iri>` / `?name = "Alice"` / `?age >= 18` all compare correctly.
15
16use std::cell::RefCell;
17use std::collections::HashMap;
18
19use crate::sparql_ast::{
20    BinaryOp, Expression, ExpressionId, Function, LiteralTable, SparqlQueryContext, UnaryOp,
21};
22use crate::sparql_library::sparql_grammar::tokenizer::Token;
23
24thread_local! {
25    /// Literal text (`hash -> string`) collected while parsing the current query,
26    /// so `geof:*`/text functions can recover it. SPARQL parsing is single-
27    /// threaded and non-reentrant here, so a thread-local avoids threading a
28    /// `&mut LiteralTable` through every parser function. `parse_sparql` resets
29    /// it before and takes it after a parse.
30    static PARSE_LITERALS: RefCell<LiteralTable> = RefCell::new(LiteralTable::new());
31}
32
33/// Clear the parse-time literal table (call before parsing a query).
34pub fn reset_parse_literals() {
35    PARSE_LITERALS.with(|l| *l.borrow_mut() = LiteralTable::new());
36}
37
38/// Take the literal table collected during the last parse.
39pub fn take_parse_literals() -> LiteralTable {
40    PARSE_LITERALS.with(|l| std::mem::take(&mut *l.borrow_mut()))
41}
42
43fn record_parse_literal_tagged(hash: u64, text: &str, lang: Option<&str>, datatype: Option<&str>) {
44    PARSE_LITERALS.with(|l| l.borrow_mut().intern_tagged(hash, text, lang, datatype));
45}
46
47/// Parse a full expression from `tokens`, allocating nodes into `ctx`.
48/// Returns the root `ExpressionId`. Errors on malformed syntax or arena overflow.
49pub fn parse_expression(
50    tokens: &[Token],
51    ctx: &mut SparqlQueryContext,
52    prefixes: &HashMap<String, String>,
53) -> Result<ExpressionId, String> {
54    let mut p = ExprParser {
55        tokens,
56        pos: 0,
57        ctx,
58        prefixes,
59    };
60    let id = p.parse_or()?;
61    if p.pos != tokens.len() {
62        return Err(format!(
63            "unexpected trailing tokens in expression at index {}",
64            p.pos
65        ));
66    }
67    Ok(id)
68}
69
70struct ExprParser<'a> {
71    tokens: &'a [Token],
72    pos: usize,
73    ctx: &'a mut SparqlQueryContext,
74    prefixes: &'a HashMap<String, String>,
75}
76
77impl<'a> ExprParser<'a> {
78    fn peek(&self) -> Option<&Token> {
79        self.tokens.get(self.pos)
80    }
81
82    fn bump(&mut self) -> Option<&Token> {
83        let t = self.tokens.get(self.pos);
84        if t.is_some() {
85            self.pos += 1;
86        }
87        t
88    }
89
90    fn eat_op(&mut self, op: &str) -> bool {
91        if let Some(Token::Op(o)) = self.peek() {
92            if *o == op {
93                self.pos += 1;
94                return true;
95            }
96        }
97        false
98    }
99
100    fn eat_punct(&mut self, c: char) -> bool {
101        if let Some(Token::Punct(p)) = self.peek() {
102            if *p == c {
103                self.pos += 1;
104                return true;
105            }
106        }
107        false
108    }
109
110    fn expect_punct(&mut self, c: char) -> Result<(), String> {
111        if self.eat_punct(c) {
112            Ok(())
113        } else {
114            Err(format!("expected '{c}' at token {}", self.pos))
115        }
116    }
117
118    // `||`
119    fn parse_or(&mut self) -> Result<ExpressionId, String> {
120        let mut left = self.parse_and()?;
121        while self.eat_op("||") {
122            let right = self.parse_and()?;
123            left = self.alloc(Expression::BinaryOp {
124                op: BinaryOp::Or,
125                left,
126                right,
127            })?;
128        }
129        Ok(left)
130    }
131
132    // `&&`
133    fn parse_and(&mut self) -> Result<ExpressionId, String> {
134        let mut left = self.parse_comparison()?;
135        while self.eat_op("&&") {
136            let right = self.parse_comparison()?;
137            left = self.alloc(Expression::BinaryOp {
138                op: BinaryOp::And,
139                left,
140                right,
141            })?;
142        }
143        Ok(left)
144    }
145
146    // `=` `!=` `<` `<=` `>` `>=`
147    fn parse_comparison(&mut self) -> Result<ExpressionId, String> {
148        let left = self.parse_additive()?;
149        let op = match self.peek() {
150            Some(Token::Op("=")) => Some(BinaryOp::Equal),
151            Some(Token::Op("!=")) => Some(BinaryOp::NotEqual),
152            Some(Token::Op("<")) => Some(BinaryOp::LessThan),
153            Some(Token::Op("<=")) => Some(BinaryOp::LessThanOrEqual),
154            Some(Token::Op(">")) => Some(BinaryOp::GreaterThan),
155            Some(Token::Op(">=")) => Some(BinaryOp::GreaterThanOrEqual),
156            _ => None,
157        };
158        if let Some(op) = op {
159            self.pos += 1;
160            let right = self.parse_additive()?;
161            return self.alloc(Expression::BinaryOp { op, left, right });
162        }
163        Ok(left)
164    }
165
166    // `+` `-`
167    fn parse_additive(&mut self) -> Result<ExpressionId, String> {
168        let mut left = self.parse_multiplicative()?;
169        loop {
170            let op = if self.eat_op("+") {
171                BinaryOp::Add
172            } else if self.eat_op("-") {
173                BinaryOp::Subtract
174            } else {
175                break;
176            };
177            let right = self.parse_multiplicative()?;
178            left = self.alloc(Expression::BinaryOp { op, left, right })?;
179        }
180        Ok(left)
181    }
182
183    // `*` `/`
184    fn parse_multiplicative(&mut self) -> Result<ExpressionId, String> {
185        let mut left = self.parse_unary()?;
186        loop {
187            let op = if self.eat_op("*") {
188                BinaryOp::Multiply
189            } else if self.eat_op("/") {
190                BinaryOp::Divide
191            } else {
192                break;
193            };
194            let right = self.parse_unary()?;
195            left = self.alloc(Expression::BinaryOp { op, left, right })?;
196        }
197        Ok(left)
198    }
199
200    // unary `!` `+` `-`
201    fn parse_unary(&mut self) -> Result<ExpressionId, String> {
202        let op = match self.peek() {
203            Some(Token::Op("!")) => Some(UnaryOp::Not),
204            Some(Token::Op("+")) => Some(UnaryOp::Plus),
205            Some(Token::Op("-")) => Some(UnaryOp::Minus),
206            _ => None,
207        };
208        if let Some(op) = op {
209            self.pos += 1;
210            let expr = self.parse_unary()?;
211            return self.alloc(Expression::UnaryOp { op, expr });
212        }
213        self.parse_primary()
214    }
215
216    fn parse_primary(&mut self) -> Result<ExpressionId, String> {
217        // `( expr )`
218        if self.eat_punct('(') {
219            let inner = self.parse_or()?;
220            self.expect_punct(')')?;
221            return Ok(inner);
222        }
223
224        // `<< s p o >>` embedded triple (constant or variable terms).
225        if let Some(Token::StarOpen) = self.peek() {
226            return self.parse_embedded_triple();
227        }
228
229        // `EXISTS { … }` / `NOT EXISTS { … }` inside a bracketed expression
230        // (e.g. `FILTER( EXISTS { … } && ?x > 1 )`). The inner group is parsed by
231        // the group-graph-pattern parser over the current token slice.
232        let is_exists =
233            matches!(self.peek(), Some(Token::Word(w)) if w.eq_ignore_ascii_case("EXISTS"));
234        let is_not_exists = matches!(self.peek(), Some(Token::Word(w)) if w.eq_ignore_ascii_case("NOT"))
235            && matches!(self.tokens.get(self.pos + 1),
236                    Some(Token::Word(w)) if w.eq_ignore_ascii_case("EXISTS"));
237        if is_exists || is_not_exists {
238            let mut negated = false;
239            if is_not_exists {
240                self.pos += 1; // consume NOT
241                negated = true;
242            }
243            self.pos += 1; // consume EXISTS; self.pos now indexes '{'
244            let (pattern, new_pos) =
245                super::pattern::parse_group_tokens(self.tokens, self.pos, self.ctx, self.prefixes)?;
246            self.pos = new_pos;
247            return self.alloc(Expression::Exists { pattern, negated });
248        }
249
250        let tok = self
251            .bump()
252            .ok_or_else(|| "unexpected end of expression".to_string())?
253            .clone();
254
255        match tok {
256            Token::Var(name) => {
257                let vid = self.ctx.register_variable(&name)?;
258                self.alloc(Expression::Variable(vid))
259            }
260            Token::Num(text) => {
261                let value = encode_number(&text);
262                self.alloc(Expression::Literal(value))
263            }
264            Token::Bool(b) => self.alloc(Expression::Literal(if b { 1 } else { 0 })),
265            Token::Str {
266                value,
267                lang,
268                datatype,
269            } => {
270                // Expand a prefixed datatype (e.g. `xsd:integer`) against the prefix map
271                // so DATATYPE(?x) is comparable to the query's own datatype IRI term.
272                let dt = datatype.as_ref().map(|d| {
273                    if d.contains("://") {
274                        d.clone()
275                    } else if let Some((p, local)) = d.split_once(':') {
276                        match self.prefixes.get(p) {
277                            Some(base) => format!("{base}{local}"),
278                            None => d.clone(),
279                        }
280                    } else {
281                        d.clone()
282                    }
283                });
284                // A plain, lang-tagged, and datatyped literal of the same text are
285                // distinct terms — hash accordingly so LANG/DATATYPE read the tag back.
286                let h =
287                    crate::sparql_ast::literal_term_hash(&value, lang.as_deref(), dt.as_deref());
288                record_parse_literal_tagged(h, &value, lang.as_deref(), dt.as_deref());
289                self.alloc(Expression::Literal(h))
290            }
291            Token::Iri(iri) => {
292                // An IRI directly followed by `(` is an extension function call.
293                if matches!(self.peek(), Some(Token::Punct('('))) {
294                    return self.parse_custom_call(&iri);
295                }
296                let h = crate::lexicon::generate_60bit_token(iri.as_bytes());
297                self.alloc(Expression::Literal(h))
298            }
299            Token::Prefixed(prefix, local) => {
300                // A prefixed name followed by `(` is an extension function call;
301                // otherwise a constant IRI.
302                if matches!(self.peek(), Some(Token::Punct('('))) {
303                    let iri = self.expand_function_iri(&prefix, &local);
304                    return self.parse_custom_call(&iri);
305                }
306                let expanded = match self.prefixes.get(&prefix) {
307                    Some(base) => format!("{base}{local}"),
308                    None => format!("{prefix}:{local}"),
309                };
310                let h = crate::lexicon::generate_60bit_token(expanded.as_bytes());
311                self.alloc(Expression::Literal(h))
312            }
313            Token::Word(word) => self.parse_word_or_call(&word),
314            other => Err(format!("unexpected token in expression: {other:?}")),
315        }
316    }
317
318    /// A bare word is either a builtin function call (`WORD ( args )`) or the
319    /// boolean/`a` keyword handled elsewhere. Unknown words error rather than
320    /// silently passing.
321    fn parse_word_or_call(&mut self, word: &str) -> Result<ExpressionId, String> {
322        let func = builtin_function(word)
323            .ok_or_else(|| format!("unknown function or identifier '{word}'"))?;
324        self.expect_punct('(')?;
325        // Parse comma-separated argument expressions.
326        let mut arg_ids: Vec<ExpressionId> = Vec::new();
327        if !matches!(self.peek(), Some(Token::Punct(')'))) {
328            loop {
329                arg_ids.push(self.parse_or()?);
330                if self.eat_punct(',') {
331                    continue;
332                }
333                break;
334            }
335        }
336        self.expect_punct(')')?;
337
338        // Copy arg ids into the ctx.function_args table; the Function node stores
339        // (args_start, args_len) into it.
340        let args_start = self.ctx.function_arg_count as u16;
341        for id in &arg_ids {
342            if (self.ctx.function_arg_count as usize) >= self.ctx.function_args.len() {
343                return Err("too many function arguments (arena full)".to_string());
344            }
345            self.ctx.function_args[self.ctx.function_arg_count as usize] = *id;
346            self.ctx.function_arg_count += 1;
347        }
348        self.alloc(Expression::Function {
349            func,
350            args_start,
351            args_len: arg_ids.len() as u16,
352        })
353    }
354
355    /// Expand a prefixed function name to its IRI. Known extension prefixes with
356    /// no declared mapping fall back to their standard base (currently `geof:`),
357    /// so `geof:sfWithin(...)` works even without a `PREFIX geof:` declaration.
358    fn expand_function_iri(&self, prefix: &str, local: &str) -> String {
359        if let Some(base) = self.prefixes.get(prefix) {
360            return format!("{base}{local}");
361        }
362        if prefix == "geof" {
363            if let Some(iri) = crate::sparql_library::geosparql::geo_function_iri(local) {
364                return iri.to_string();
365            }
366            return format!("http://www.opengis.net/def/function/geosparql/{local}");
367        }
368        format!("{prefix}:{local}")
369    }
370
371    /// Parse an extension-function call `IRI ( args )` into
372    /// `Expression::Function { func: Function::Custom(q_hash(iri)), … }`.
373    fn parse_custom_call(&mut self, iri: &str) -> Result<ExpressionId, String> {
374        let func = Function::Custom(crate::lexicon::generate_60bit_token(iri.as_bytes()));
375        self.expect_punct('(')?;
376        let mut arg_ids: Vec<ExpressionId> = Vec::new();
377        if !matches!(self.peek(), Some(Token::Punct(')'))) {
378            loop {
379                arg_ids.push(self.parse_or()?);
380                if self.eat_punct(',') {
381                    continue;
382                }
383                break;
384            }
385        }
386        self.expect_punct(')')?;
387        let args_start = self.ctx.function_arg_count as u16;
388        for id in &arg_ids {
389            if (self.ctx.function_arg_count as usize) >= self.ctx.function_args.len() {
390                return Err("too many function arguments (arena full)".to_string());
391            }
392            self.ctx.function_args[self.ctx.function_arg_count as usize] = *id;
393            self.ctx.function_arg_count += 1;
394        }
395        self.alloc(Expression::Function {
396            func,
397            args_start,
398            args_len: arg_ids.len() as u16,
399        })
400    }
401
402    fn parse_embedded_triple(&mut self) -> Result<ExpressionId, String> {
403        // consume `<<`
404        self.bump();
405        let s = self.embedded_term()?;
406        let p = self.embedded_term()?;
407        let o = self.embedded_term()?;
408        match self.peek() {
409            Some(Token::StarClose) => {
410                self.pos += 1;
411            }
412            _ => return Err("expected '>>' to close embedded triple".to_string()),
413        }
414        self.alloc(Expression::EmbeddedTriple {
415            subject: s,
416            predicate: p,
417            object: o,
418        })
419    }
420
421    /// A term inside an embedded triple resolves to a `u64` (constant hash or,
422    /// for a variable, its id) — matching the `parse_term` convention.
423    fn embedded_term(&mut self) -> Result<u64, String> {
424        let tok = self
425            .bump()
426            .ok_or_else(|| "unexpected end inside embedded triple".to_string())?
427            .clone();
428        match tok {
429            Token::Var(name) => Ok(self.ctx.register_variable(&name)? as u64),
430            Token::Iri(iri) => Ok(crate::lexicon::generate_60bit_token(iri.as_bytes())),
431            Token::Prefixed(prefix, local) => {
432                let expanded = match self.prefixes.get(&prefix) {
433                    Some(base) => format!("{base}{local}"),
434                    None => format!("{prefix}:{local}"),
435                };
436                Ok(crate::lexicon::generate_60bit_token(expanded.as_bytes()))
437            }
438            Token::Str { value, .. } => Ok(crate::lexicon::generate_60bit_token(value.as_bytes())),
439            Token::Num(text) => Ok(encode_number(&text)),
440            other => Err(format!("invalid term inside embedded triple: {other:?}")),
441        }
442    }
443
444    fn alloc(&mut self, expr: Expression) -> Result<ExpressionId, String> {
445        self.ctx.alloc_expression(expr)
446    }
447}
448
449/// Encode a numeric literal to match the triple-pattern convention: an integer
450/// is stored as its raw `u64` value (so numeric comparisons work against
451/// raw-encoded object values); a non-integer is interned by text (equality only).
452fn encode_number(text: &str) -> u64 {
453    if let Ok(n) = text.parse::<u64>() {
454        n
455    } else if let Ok(n) = text.parse::<i64>() {
456        n as u64
457    } else {
458        crate::lexicon::generate_60bit_token(text.as_bytes())
459    }
460}
461
462/// Map a builtin function name (case-insensitive) to the `Function` enum.
463/// Extension functions (prefixed / IRI names) are handled by the registry slice.
464fn builtin_function(word: &str) -> Option<Function> {
465    let up = word.to_ascii_uppercase();
466    Some(match up.as_str() {
467        "STR" => Function::Str,
468        "LANG" => Function::Lang,
469        "LANGMATCHES" => Function::LangMatches,
470        "DATATYPE" => Function::Datatype,
471        "BOUND" => Function::Bound,
472        "IRI" => Function::Iri,
473        "URI" => Function::Uri,
474        "BNODE" => Function::Bnode,
475        "RAND" => Function::Rand,
476        "ABS" => Function::Abs,
477        "CEIL" => Function::Ceil,
478        "FLOOR" => Function::Floor,
479        "ROUND" => Function::Round,
480        "CONCAT" => Function::Concat,
481        "SUBSTR" => Function::Substring,
482        "STRLEN" => Function::Strlen,
483        "UCASE" => Function::Ucase,
484        "LCASE" => Function::Lcase,
485        "ENCODE_FOR_URI" => Function::EncodeForUri,
486        "CONTAINS" => Function::Contains,
487        "STRSTARTS" => Function::VarStarts,
488        "STRENDS" => Function::VarEnds,
489        "STRBEFORE" => Function::StrBefore,
490        "STRAFTER" => Function::StrAfter,
491        "YEAR" => Function::Year,
492        "MONTH" => Function::Month,
493        "DAY" => Function::Day,
494        "HOURS" => Function::Hours,
495        "MINUTES" => Function::Minutes,
496        "SECONDS" => Function::Seconds,
497        "TIMEZONE" => Function::Timezone,
498        "TZ" => Function::Tz,
499        "NOW" => Function::Now,
500        "UUID" => Function::Uuid,
501        "STRUUID" => Function::StrUuid,
502        "COALESCE" => Function::Coalesce,
503        "IF" => Function::If,
504        "STRLANG" => Function::StrLang,
505        "STRDT" => Function::StrDt,
506        "SAMETERM" => Function::SameTerm,
507        "ISIRI" => Function::IsIri,
508        "ISURI" => Function::IsUri,
509        "ISBLANK" => Function::IsBlank,
510        "ISLITERAL" => Function::IsLiteral,
511        "ISNUMERIC" => Function::IsNumeric,
512        "REGEX" => Function::Regex,
513        "TRIPLE" => Function::Triple,
514        "SUBJECT" => Function::TripleSubject,
515        "PREDICATE" => Function::TriplePredicate,
516        "OBJECT" => Function::TripleObject,
517        _ => return None,
518    })
519}
520
521#[cfg(test)]
522mod tests {
523    use super::*;
524    use crate::sparql_ast::SparqlQueryContext;
525    use crate::sparql_library::sparql_grammar::tokenizer::tokenize;
526
527    fn parse(input: &str) -> (SparqlQueryContext, ExpressionId) {
528        let mut ctx = SparqlQueryContext::new();
529        let toks = tokenize(input).unwrap();
530        let prefixes = HashMap::new();
531        let id = parse_expression(&toks, &mut ctx, &prefixes).unwrap();
532        (ctx, id)
533    }
534
535    #[test]
536    fn parses_numeric_comparison() {
537        let (ctx, root) = parse("?age >= 18");
538        match ctx.expressions[root as usize] {
539            Expression::BinaryOp {
540                op: BinaryOp::GreaterThanOrEqual,
541                left,
542                right,
543            } => {
544                assert!(matches!(
545                    ctx.expressions[left as usize],
546                    Expression::Variable(_)
547                ));
548                assert_eq!(ctx.expressions[right as usize], Expression::Literal(18));
549            }
550            other => panic!("expected >= comparison, got {other:?}"),
551        }
552    }
553
554    #[test]
555    fn respects_and_or_precedence() {
556        // a || b && c  parses as  a || (b && c)
557        let (ctx, root) = parse("?a || ?b && ?c");
558        match ctx.expressions[root as usize] {
559            Expression::BinaryOp {
560                op: BinaryOp::Or,
561                right,
562                ..
563            } => {
564                assert!(matches!(
565                    ctx.expressions[right as usize],
566                    Expression::BinaryOp {
567                        op: BinaryOp::And,
568                        ..
569                    }
570                ));
571            }
572            other => panic!("expected top-level OR, got {other:?}"),
573        }
574    }
575
576    #[test]
577    fn arithmetic_precedence() {
578        // 1 + 2 * 3  →  1 + (2 * 3)
579        let (ctx, root) = parse("1 + 2 * 3");
580        match ctx.expressions[root as usize] {
581            Expression::BinaryOp {
582                op: BinaryOp::Add,
583                right,
584                ..
585            } => assert!(matches!(
586                ctx.expressions[right as usize],
587                Expression::BinaryOp {
588                    op: BinaryOp::Multiply,
589                    ..
590                }
591            )),
592            other => panic!("expected top-level Add, got {other:?}"),
593        }
594    }
595
596    #[test]
597    fn parses_function_call_with_args() {
598        let (ctx, root) = parse("REGEX(?name, \"^A\")");
599        match ctx.expressions[root as usize] {
600            Expression::Function {
601                func: Function::Regex,
602                args_start,
603                args_len,
604            } => {
605                assert_eq!(args_len, 2);
606                let a0 = ctx.function_args[args_start as usize];
607                assert!(matches!(
608                    ctx.expressions[a0 as usize],
609                    Expression::Variable(_)
610                ));
611            }
612            other => panic!("expected REGEX function, got {other:?}"),
613        }
614    }
615
616    #[test]
617    fn parses_parenthesised_grouping() {
618        // (?a || ?b) && ?c  →  top-level AND
619        let (ctx, root) = parse("(?a || ?b) && ?c");
620        assert!(matches!(
621            ctx.expressions[root as usize],
622            Expression::BinaryOp {
623                op: BinaryOp::And,
624                ..
625            }
626        ));
627    }
628
629    #[test]
630    fn unknown_function_errors() {
631        let mut ctx = SparqlQueryContext::new();
632        let toks = tokenize("NOTAFUNC(?x)").unwrap();
633        assert!(parse_expression(&toks, &mut ctx, &HashMap::new()).is_err());
634    }
635
636    #[test]
637    fn parses_embedded_triple_expression() {
638        let (ctx, root) = parse("<< ?s ?p ?o >>");
639        assert!(matches!(
640            ctx.expressions[root as usize],
641            Expression::EmbeddedTriple { .. }
642        ));
643    }
644}
qualia_core_db/sparql_library/sparql_grammar/expr.rs

qualia_core_db/sparql_library/sparql_grammar/
expr.rs
