Skip to main content

rete_core/sparql/
lower.rs

1//! Lowering: parse a SPARQL query with `spargebra` and translate its algebra
2//! into the engine's [`Select`]/[`Plan`]/[`FExpr`] forms (SPEC.md §8). This is
3//! the front end — it only builds plan/expression values; evaluation lives in
4//! the parent module and its `eval`/`aggregate`/`path` siblings.
5
6use super::*;
7
8use crate::bgp::{PatternTerm, TriplePattern};
9use spargebra::algebra::{
10    AggregateExpression, AggregateFunction, Expression, Function, GraphPattern, OrderExpression,
11    PropertyPathExpression, QueryDataset,
12};
13use spargebra::term::{NamedNodePattern, TermPattern, TriplePattern as SpTriplePattern};
14use spargebra::Query;
15
16/// Lower a graph pattern (with its solution modifiers) into a [`Select`].
17pub(super) fn lower_pattern(pattern: &GraphPattern) -> Result<Select, SparqlError> {
18    let mut sel = Select::default();
19    let plan = build(pattern, &mut sel, false)?;
20    sel.plan = plan;
21    Ok(sel)
22}
23
24/// Lower a SELECT's pattern + dataset clause into a [`Select`].
25pub(super) fn lower_select(
26    pattern: &GraphPattern,
27    dataset: &Option<QueryDataset>,
28) -> Result<Select, SparqlError> {
29    let mut sel = lower_pattern(pattern)?;
30    if let Some(ds) = dataset {
31        sel.from = ds.default.iter().map(|n| n.to_string()).collect();
32        sel.from_named = ds
33            .named
34            .as_ref()
35            .map(|gs| gs.iter().map(|n| n.to_string()).collect());
36    }
37    Ok(sel)
38}
39
40/// SPARQL 1.2 permits a leading `VERSION "…"` declaration; the pinned parser
41/// (SPARQL 1.1) rejects it. Accept and drop it — there is one query language, so
42/// the version is advisory. Only a declaration at the very start (after leading
43/// whitespace and `#` comments) is removed; `VERSION` anywhere else is untouched.
44/// The result is always a subslice of `query`.
45pub(super) fn strip_version(query: &str) -> &str {
46    let mut rest = query;
47    loop {
48        let t = rest.trim_start();
49        if let Some(after_hash) = t.strip_prefix('#') {
50            match after_hash.split_once('\n') {
51                Some((_, r)) => rest = r, // skip a leading comment line, look again
52                None => return query,     // comment to EOF — no VERSION
53            }
54            continue;
55        }
56        if t.len() >= 7 && t[..7].eq_ignore_ascii_case("VERSION") {
57            let after = t[7..].trim_start();
58            if let Some(q) = after.chars().next().filter(|c| *c == '"' || *c == '\'') {
59                if let Some(close) = after[q.len_utf8()..].find(q) {
60                    return &after[q.len_utf8() + close + q.len_utf8()..];
61                }
62            }
63        }
64        return query; // no leading VERSION declaration
65    }
66}
67
68/// Parse a SPARQL query — the single entry point, so every caller drops a
69/// SPARQL-1.2 `VERSION` declaration, reads SPARQL 1.2 triple terms
70/// (`<<( s p o )>>`, and under `VERSION "1.2"` reified triples — see
71/// [`super::sparql12`]) and reports a uniform parse error.
72pub(super) fn parse_query(query: &str) -> Result<Query, SparqlError> {
73    let sparql12 = super::sparql12::is_sparql12(super::sparql12::version(query));
74    let text = super::sparql12::rewrite(strip_version(query), sparql12)?;
75    Query::parse(&text, None).map_err(|e| SparqlError::Parse(e.to_string()))
76}
77
78/// Parse a SPARQL `SELECT` query and lower it to a [`Select`].
79pub fn parse_select(query: &str) -> Result<Select, SparqlError> {
80    let parsed = parse_query(query)?;
81    match parsed {
82        Query::Select {
83            pattern, dataset, ..
84        } => lower_select(&pattern, &dataset),
85        _ => Err(SparqlError::Unsupported("only SELECT is supported")),
86    }
87}
88
89/// Collect the **concrete predicate IRIs** a query constrains on — i.e. every
90/// IRI that appears in the predicate position of a triple pattern, or as a plain
91/// predicate inside a property path. Variable predicates (`?p`) and the special
92/// `a` (`rdf:type`) keyword are normalized to their IRI tokens (`<…>`).
93///
94/// This is what `rete federate` uses to prune shards: a source whose predicate
95/// set is disjoint from this set cannot contribute a row and can be skipped.
96/// Returns an empty set when the query pins no concrete predicate (e.g. every
97/// pattern uses a variable predicate) — callers should then query every source.
98pub fn query_predicates(query: &str) -> Result<std::collections::BTreeSet<String>, SparqlError> {
99    let parsed = parse_query(query)?;
100    let mut preds = std::collections::BTreeSet::new();
101    let pattern = match &parsed {
102        Query::Select { pattern, .. } => pattern,
103        Query::Ask { pattern, .. } => pattern,
104        Query::Construct { pattern, .. } => pattern,
105        Query::Describe { pattern, .. } => pattern,
106    };
107    collect_pattern_predicates(pattern, &mut preds);
108    Ok(preds)
109}
110
111/// Walk a `GraphPattern`, adding every concrete predicate IRI to `out`.
112fn collect_pattern_predicates(p: &GraphPattern, out: &mut std::collections::BTreeSet<String>) {
113    match p {
114        GraphPattern::Bgp { patterns } => {
115            for tp in patterns {
116                if let NamedNodePattern::NamedNode(n) = &tp.predicate {
117                    out.insert(n.to_string());
118                }
119            }
120        }
121        GraphPattern::Path {
122            path: PropertyPathExpression::NamedNode(n),
123            ..
124        } => {
125            out.insert(n.to_string());
126        }
127        GraphPattern::Path { path, .. } => collect_path_predicates(path, out),
128        GraphPattern::Join { left, right }
129        | GraphPattern::Union { left, right }
130        | GraphPattern::Minus { left, right } => {
131            collect_pattern_predicates(left, out);
132            collect_pattern_predicates(right, out);
133        }
134        GraphPattern::LeftJoin { left, right, .. } => {
135            collect_pattern_predicates(left, out);
136            collect_pattern_predicates(right, out);
137        }
138        GraphPattern::Filter { inner, .. }
139        | GraphPattern::Extend { inner, .. }
140        | GraphPattern::OrderBy { inner, .. }
141        | GraphPattern::Project { inner, .. }
142        | GraphPattern::Distinct { inner }
143        | GraphPattern::Reduced { inner }
144        | GraphPattern::Slice { inner, .. }
145        | GraphPattern::Group { inner, .. }
146        | GraphPattern::Service { inner, .. }
147        | GraphPattern::Graph { inner, .. } => collect_pattern_predicates(inner, out),
148        _ => {}
149    }
150}
151
152/// Walk a (non-plain) property-path expression for its concrete predicate IRIs.
153fn collect_path_predicates(
154    path: &PropertyPathExpression,
155    out: &mut std::collections::BTreeSet<String>,
156) {
157    match path {
158        PropertyPathExpression::NamedNode(n) => {
159            out.insert(n.to_string());
160        }
161        PropertyPathExpression::Reverse(inner)
162        | PropertyPathExpression::ZeroOrMore(inner)
163        | PropertyPathExpression::OneOrMore(inner)
164        | PropertyPathExpression::ZeroOrOne(inner) => collect_path_predicates(inner, out),
165        PropertyPathExpression::Sequence(a, b) | PropertyPathExpression::Alternative(a, b) => {
166            collect_path_predicates(a, out);
167            collect_path_predicates(b, out);
168        }
169        PropertyPathExpression::NegatedPropertySet(_) => {}
170    }
171}
172
173/// `FILTER(e)` over `inner`, with every conjunct of `e` that the left side of
174/// an OPTIONAL decides on its own applied **there**.
175///
176/// A group's filters scope over the whole group, so `{ ?d :title ?t FILTER(...)
177/// OPTIONAL { ?d :year ?y } }` is `Filter(e, LeftJoin(Bgp, Bgp))`: the filter
178/// runs after the OPTIONAL, which then evaluates once per row of the left side
179/// the filter is about to throw away (G33: a `CONTAINS` that keeps a few in a
180/// million titles probed the year of every title it scanned). A conjunct whose
181/// variables are all bound in every left row sees the same values on the merged
182/// row, since the merge keeps the left row's bindings, so it accepts exactly
183/// the rows it accepted above. It moves onto the base of the left spine
184/// (`LeftJoin` binds nothing certainly beyond its left), where the CONTAINS
185/// push-down and the lazy streaming see it. A conjunct that reads a variable the
186/// OPTIONAL may bind, or holds an `EXISTS` (which reads the whole row), stays.
187fn filter_below_optional(expr: FExpr, mut inner: Plan) -> Plan {
188    if !matches!(inner, Plan::LeftJoin(..)) {
189        return Plan::Filter(expr, Box::new(inner));
190    }
191    // The base of the left spine, walked iteratively like `build_left_spine`.
192    let mut base = &mut inner;
193    while let Plan::LeftJoin(l, _, _) = base {
194        base = &mut **l;
195    }
196    let certain = certain_var_names(base);
197    let mut conjuncts = Vec::new();
198    split_and(expr, &mut conjuncts);
199    let (mut down, mut up) = (Vec::new(), Vec::new());
200    for c in conjuncts {
201        let mut vars = std::collections::BTreeSet::new();
202        if expr_vars(&c, &mut vars) && vars.iter().all(|v| certain.contains(v)) {
203            down.push(c);
204        } else {
205            up.push(c);
206        }
207    }
208    if let Some(cond) = and_all(down) {
209        let b = std::mem::replace(base, Plan::Bgp(Vec::new()));
210        *base = Plan::Filter(cond, Box::new(b));
211    }
212    match and_all(up) {
213        Some(cond) => Plan::Filter(cond, Box::new(inner)),
214        None => inner,
215    }
216}
217
218fn split_and(e: FExpr, out: &mut Vec<FExpr>) {
219    match e {
220        FExpr::And(a, b) => {
221            split_and(*a, out);
222            split_and(*b, out);
223        }
224        e => out.push(e),
225    }
226}
227
228fn and_all(parts: Vec<FExpr>) -> Option<FExpr> {
229    parts
230        .into_iter()
231        .reduce(|a, b| FExpr::And(Box::new(a), Box::new(b)))
232}
233
234/// The variables every solution of `plan` binds, by name: the same notion as
235/// the evaluator's `certain_bound`, without a slot table and conservative
236/// (a shape not listed binds nothing certainly).
237fn certain_var_names(plan: &Plan) -> std::collections::BTreeSet<String> {
238    fn add(t: &PatternTerm, out: &mut std::collections::BTreeSet<String>) {
239        if let PatternTerm::Var(v) = t {
240            out.insert(v.clone());
241        }
242    }
243    let mut out = std::collections::BTreeSet::new();
244    match plan {
245        Plan::Bgp(patterns) => {
246            for p in patterns {
247                for t in [&p.s, &p.p, &p.o] {
248                    add(t, &mut out);
249                }
250            }
251        }
252        Plan::Path(s, _, o) => {
253            add(s, &mut out);
254            add(o, &mut out);
255        }
256        Plan::Values(vars, rows) => {
257            for (i, v) in vars.iter().enumerate() {
258                if rows.iter().all(|r| r.get(i).is_some_and(Option::is_some)) {
259                    out.insert(v.clone());
260                }
261            }
262        }
263        Plan::Filter(_, inner) | Plan::Extend(_, _, inner) => out = certain_var_names(inner),
264        Plan::Join(l, r) => {
265            out = certain_var_names(l);
266            out.extend(certain_var_names(r));
267        }
268        Plan::LeftJoin(l, _, _) => out = certain_var_names(l),
269        _ => {}
270    }
271    out
272}
273
274/// Collect the variables `e` reads. `false` when it holds an `EXISTS`, which
275/// reads the whole row.
276fn expr_vars(e: &FExpr, out: &mut std::collections::BTreeSet<String>) -> bool {
277    match e {
278        FExpr::Var(v) | FExpr::Bound(v) => {
279            out.insert(v.clone());
280            true
281        }
282        FExpr::Const(_) => true,
283        FExpr::Exists(_) => false,
284        FExpr::Arith(_, a, b)
285        | FExpr::SameTerm(a, b)
286        | FExpr::Compare(_, a, b)
287        | FExpr::And(a, b)
288        | FExpr::Or(a, b) => expr_vars(a, out) && expr_vars(b, out),
289        FExpr::Not(a) => expr_vars(a, out),
290        FExpr::If(c, t, f) => expr_vars(c, out) && expr_vars(t, out) && expr_vars(f, out),
291        FExpr::In(x, list) => expr_vars(x, out) && list.iter().all(|e| expr_vars(e, out)),
292        FExpr::Func(_, args) | FExpr::Coalesce(args) => args.iter().all(|e| expr_vars(e, out)),
293    }
294}
295
296/// Lower a left-deep chain of `Join` / `LeftJoin` **iteratively** (see the note
297/// in `build`'s Join/LeftJoin arm). Walks the left spine collecting each
298/// operator (its right side, and a LeftJoin's optional condition), lowers the
299/// base and each right, then folds the plan back up — the identical plan tree
300/// the recursive lowering would produce, but the spine costs O(1) call-stack
301/// depth instead of one (large) frame per operand.
302fn build_left_spine(p: &GraphPattern, sel: &mut Select) -> Result<Plan, SparqlError> {
303    enum SpineOp {
304        Join(Plan),
305        LeftJoin(Plan, Option<FExpr>),
306    }
307    let mut ops: Vec<SpineOp> = Vec::new();
308    let mut cur = p;
309    loop {
310        match cur {
311            GraphPattern::Join { left, right } => {
312                ops.push(SpineOp::Join(build(right, sel, true)?));
313                cur = left;
314            }
315            GraphPattern::LeftJoin {
316                left,
317                right,
318                expression,
319            } => {
320                let cond = expression.as_ref().map(convert_expr).transpose()?;
321                ops.push(SpineOp::LeftJoin(build(right, sel, true)?, cond));
322                cur = left;
323            }
324            _ => break,
325        }
326    }
327    // `cur` now points at the spine's base (the first non-Join/LeftJoin node).
328    let mut plan = build(cur, sel, true)?;
329    // `ops` is outermost-first; fold innermost-first to rebuild the same tree.
330    for op in ops.into_iter().rev() {
331        plan = match op {
332            SpineOp::Join(r) => Plan::Join(Box::new(plan), Box::new(r)),
333            SpineOp::LeftJoin(r, c) => Plan::LeftJoin(Box::new(plan), Box::new(r), c),
334        };
335    }
336    Ok(plan)
337}
338
339/// Build the evaluation [`Plan`] for a graph pattern, capturing the solution
340/// modifiers (projection/DISTINCT/slice) into `sel` as transparent wrappers.
341///
342/// `in_where` is true once we have descended into the graph-pattern body (past
343/// any pattern operator or a GROUP BY's inner). It decides where an `Extend`
344/// (`BIND`) lands: an in-pattern BIND becomes an in-tree [`Plan::Extend`] so a
345/// following FILTER/join sees it, while a top-level projection alias goes to the
346/// post-evaluation [`Select::extends`] list (applied after any aggregation).
347fn build(mut p: &GraphPattern, sel: &mut Select, mut in_where: bool) -> Result<Plan, SparqlError> {
348    // Peel the transparent single-child solution modifiers ITERATIVELY. Each one
349    // only records state into `sel` (or flips `in_where`) before descending to
350    // its inner pattern, so a stack of Slice / ORDER BY / DISTINCT / projection /
351    // GROUP BY / top-level BIND nests without one `build` stack frame per level.
352    // With `build`'s large frame, that per-level recursion overflows iOS/iPad
353    // Safari's small WASM call stack even on shallow queries — a plain
354    // `GROUP BY … ORDER BY … LIMIT` is already four wrappers deep.
355    loop {
356        match p {
357            GraphPattern::Distinct { inner } | GraphPattern::Reduced { inner } => {
358                // Below the query's own projection (or anywhere inside the pattern
359                // body) this modifier belongs to a nested SELECT, not to us — the
360                // same rule the `Project` arm below already applies.
361                if in_where || !sel.project.is_empty() {
362                    return Ok(Plan::Subquery(Box::new(lower_pattern(p)?)));
363                }
364                sel.distinct = true;
365                p = inner;
366            }
367            GraphPattern::Slice {
368                inner,
369                start,
370                length,
371            } => {
372                // A sub-SELECT's LIMIT/OFFSET must not land on the outer query.
373                // Peeling it here overwrote the outer slice *and* stole the inner
374                // one before the nested `Project` could turn it into a subquery, so
375                // `SELECT … WHERE { { SELECT … LIMIT 10 } } LIMIT 3` returned 10.
376                if in_where || !sel.project.is_empty() {
377                    return Ok(Plan::Subquery(Box::new(lower_pattern(p)?)));
378                }
379                sel.offset = *start;
380                sel.limit = *length;
381                p = inner;
382            }
383            // A *top-level* projection (a nested SELECT stays a subquery — handled
384            // in the match below, where its guard still holds).
385            GraphPattern::Project { inner, variables } if !in_where && sel.project.is_empty() => {
386                for v in variables {
387                    sel.project.push(v.as_str().to_string());
388                }
389                p = inner;
390            }
391            GraphPattern::Group {
392                inner,
393                variables,
394                aggregates,
395            } => {
396                let by = variables.iter().map(|v| v.as_str().to_string()).collect();
397                let mut aggs = Vec::with_capacity(aggregates.len());
398                let mut pre: Vec<(String, FExpr)> = Vec::new();
399                for (var, ae) in aggregates {
400                    aggs.push((var.as_str().to_string(), convert_agg(ae, &mut pre)?));
401                }
402                sel.group = Some(GroupSpec { by, aggs, pre });
403                in_where = true; // the group's inner *is* the WHERE pattern
404                p = inner;
405            }
406            GraphPattern::OrderBy { inner, expression } => {
407                for oe in expression {
408                    let (e, desc) = match oe {
409                        OrderExpression::Asc(e) => (e, false),
410                        OrderExpression::Desc(e) => (e, true),
411                    };
412                    sel.order.push((convert_expr(e)?, desc));
413                }
414                p = inner;
415            }
416            // A top-level projection alias `(expr AS ?v)`; a BIND *inside* the
417            // pattern stays in the plan tree (the match's `Extend` arm).
418            GraphPattern::Extend {
419                inner,
420                variable,
421                expression,
422            } if !in_where => {
423                sel.extends
424                    .push((variable.as_str().to_string(), convert_expr(expression)?));
425                p = inner;
426            }
427            _ => break,
428        }
429    }
430    match p {
431        GraphPattern::Bgp { patterns } => Ok(lower_bgp(patterns, &mut sel.star_counter)),
432        // Join and LeftJoin nest left-deep — `A . B OPTIONAL C OPTIONAL D` is
433        // `LeftJoin(LeftJoin(Join(A,B),C),D)`. Recursing straight down that spine
434        // costs one (large) stack frame per operand, which overflows the small
435        // WASM call stack on iOS/iPad Safari for deep queries (several OPTIONALs)
436        // — before any data is even fetched. Walk the spine ITERATIVELY instead:
437        // collect its operators, build the base + each (shallow) right, then fold
438        // the plan back up. Same plan tree, O(1) recursion depth for the spine.
439        GraphPattern::Join { .. } | GraphPattern::LeftJoin { .. } => build_left_spine(p, sel),
440        GraphPattern::Union { left, right } => Ok(Plan::Union(
441            Box::new(build(left, sel, true)?),
442            Box::new(build(right, sel, true)?),
443        )),
444        GraphPattern::Minus { left, right } => Ok(Plan::Minus(
445            Box::new(build(left, sel, true)?),
446            Box::new(build(right, sel, true)?),
447        )),
448        GraphPattern::Graph { name, inner } => {
449            let target = match name {
450                NamedNodePattern::NamedNode(n) => GraphTarget::Named(n.to_string()),
451                NamedNodePattern::Variable(v) => GraphTarget::Var(v.as_str().to_string()),
452            };
453            Ok(Plan::Graph(target, Box::new(build(inner, sel, true)?)))
454        }
455        GraphPattern::Path {
456            subject,
457            path,
458            object,
459        } => Ok(Plan::Path(
460            term_to_pattern(subject),
461            lower_path(path)?,
462            term_to_pattern(object),
463        )),
464        GraphPattern::Values {
465            variables,
466            bindings,
467        } => {
468            let vars = variables.iter().map(|v| v.as_str().to_string()).collect();
469            let rows = bindings
470                .iter()
471                .map(|row| {
472                    row.iter()
473                        .map(|g| g.as_ref().map(|t| t.to_string()))
474                        .collect()
475                })
476                .collect();
477            Ok(Plan::Values(vars, rows))
478        }
479        GraphPattern::Filter { expr, inner } => {
480            // A filter sitting *above* a GROUP BY is a HAVING: it must run after
481            // aggregation, not on the raw bindings.
482            let had_group = sel.group.is_some();
483            let inner_plan = build(inner, sel, true)?;
484            let fexpr = convert_expr(expr)?;
485            if sel.group.is_some() && !had_group {
486                sel.having.push(fexpr);
487                Ok(inner_plan)
488            } else {
489                Ok(filter_below_optional(fexpr, inner_plan))
490            }
491        }
492        // Transparent solution-modifier wrappers: record and descend.
493        GraphPattern::Project { inner, variables } => {
494            // A Project reached *inside* the graph pattern (or after the query's
495            // own projection is already set) is a nested SELECT: lower it into
496            // its own independent `Select` and evaluate it as a subquery whose
497            // projected solutions join with the surrounding pattern.
498            if in_where || !sel.project.is_empty() {
499                let sub = lower_pattern(p)?;
500                return Ok(Plan::Subquery(Box::new(sub)));
501            }
502            for v in variables {
503                sel.project.push(v.as_str().to_string());
504            }
505            build(inner, sel, in_where)
506        }
507        GraphPattern::Distinct { inner } | GraphPattern::Reduced { inner } => {
508            if in_where || !sel.project.is_empty() {
509                return Ok(Plan::Subquery(Box::new(lower_pattern(p)?)));
510            }
511            sel.distinct = true;
512            build(inner, sel, in_where)
513        }
514        GraphPattern::Slice {
515            inner,
516            start,
517            length,
518        } => {
519            if in_where || !sel.project.is_empty() {
520                return Ok(Plan::Subquery(Box::new(lower_pattern(p)?)));
521            }
522            sel.offset = *start;
523            sel.limit = *length;
524            build(inner, sel, in_where)
525        }
526        GraphPattern::Group {
527            inner,
528            variables,
529            aggregates,
530        } => {
531            let by = variables.iter().map(|v| v.as_str().to_string()).collect();
532            let mut aggs = Vec::with_capacity(aggregates.len());
533            let mut pre: Vec<(String, FExpr)> = Vec::new();
534            for (var, ae) in aggregates {
535                aggs.push((var.as_str().to_string(), convert_agg(ae, &mut pre)?));
536            }
537            sel.group = Some(GroupSpec { by, aggs, pre });
538            // The group's inner *is* the WHERE pattern — any BIND inside it must
539            // run per-row before aggregation, so descend as in-pattern.
540            build(inner, sel, true)
541        }
542        GraphPattern::Extend {
543            inner,
544            variable,
545            expression,
546        } => {
547            let var = variable.as_str().to_string();
548            let fexpr = convert_expr(expression)?;
549            if in_where {
550                // A BIND inside the graph pattern: keep it in the plan tree so a
551                // following FILTER or join observes the bound variable.
552                Ok(Plan::Extend(var, fexpr, Box::new(build(inner, sel, true)?)))
553            } else {
554                // A top-level projection alias `(expr AS ?v)`: applied after the
555                // pattern (and after any aggregation) at projection time.
556                sel.extends.push((var, fexpr));
557                build(inner, sel, in_where)
558            }
559        }
560        GraphPattern::OrderBy { inner, expression } => {
561            for oe in expression {
562                let (e, desc) = match oe {
563                    OrderExpression::Asc(e) => (e, false),
564                    OrderExpression::Desc(e) => (e, true),
565                };
566                sel.order.push((convert_expr(e)?, desc));
567            }
568            build(inner, sel, in_where)
569        }
570        // SPARQL 1.1 federated query: the inner pattern is not lowered — it is
571        // re-serialized to SPARQL text (spargebra round-trips, prefixes already
572        // expanded) and shipped verbatim to the endpoint at evaluation time.
573        // Only the variables it can bind are collected, so the returned
574        // solutions land in slots and join like any other operand.
575        GraphPattern::Service {
576            name,
577            inner,
578            silent,
579        } => {
580            let endpoint = match name {
581                NamedNodePattern::NamedNode(n) => n.as_str().to_string(),
582                NamedNodePattern::Variable(_) => {
583                    return Err(SparqlError::Unsupported("SERVICE with a variable endpoint"))
584                }
585            };
586            let mut vars = std::collections::BTreeSet::new();
587            collect_pattern_variables(inner, &mut vars);
588            let query = Query::Select {
589                dataset: None,
590                pattern: (**inner).clone(),
591                base_iri: None,
592            }
593            .to_string();
594            Ok(Plan::Service {
595                silent: *silent,
596                endpoint,
597                vars: vars.into_iter().collect(),
598                query,
599            })
600        }
601    }
602}
603
604/// Collect the variables a graph pattern can bind — used to give a `SERVICE`
605/// block's results their slots. Deliberately an **over-approximation** (e.g. a
606/// nested SELECT's non-projected variables are included): an extra slot just
607/// stays unbound, while a missed one would silently drop a returned binding.
608fn collect_pattern_variables(p: &GraphPattern, out: &mut std::collections::BTreeSet<String>) {
609    let term_var = |t: &TermPattern, out: &mut std::collections::BTreeSet<String>| {
610        if let TermPattern::Variable(v) = t {
611            out.insert(v.as_str().to_string());
612        }
613    };
614    match p {
615        GraphPattern::Bgp { patterns } => {
616            for tp in patterns {
617                term_var(&tp.subject, out);
618                if let NamedNodePattern::Variable(v) = &tp.predicate {
619                    out.insert(v.as_str().to_string());
620                }
621                term_var(&tp.object, out);
622            }
623        }
624        GraphPattern::Path {
625            subject, object, ..
626        } => {
627            term_var(subject, out);
628            term_var(object, out);
629        }
630        GraphPattern::Values { variables, .. } => {
631            for v in variables {
632                out.insert(v.as_str().to_string());
633            }
634        }
635        GraphPattern::Join { left, right }
636        | GraphPattern::Union { left, right }
637        | GraphPattern::Minus { left, right } => {
638            collect_pattern_variables(left, out);
639            collect_pattern_variables(right, out);
640        }
641        GraphPattern::LeftJoin { left, right, .. } => {
642            collect_pattern_variables(left, out);
643            collect_pattern_variables(right, out);
644        }
645        GraphPattern::Extend {
646            inner, variable, ..
647        } => {
648            out.insert(variable.as_str().to_string());
649            collect_pattern_variables(inner, out);
650        }
651        GraphPattern::Group {
652            inner,
653            variables,
654            aggregates,
655        } => {
656            for v in variables {
657                out.insert(v.as_str().to_string());
658            }
659            for (v, _) in aggregates {
660                out.insert(v.as_str().to_string());
661            }
662            collect_pattern_variables(inner, out);
663        }
664        GraphPattern::Graph { name, inner } => {
665            if let NamedNodePattern::Variable(v) = name {
666                out.insert(v.as_str().to_string());
667            }
668            collect_pattern_variables(inner, out);
669        }
670        GraphPattern::Project { inner, variables } => {
671            for v in variables {
672                out.insert(v.as_str().to_string());
673            }
674            collect_pattern_variables(inner, out);
675        }
676        GraphPattern::Filter { inner, .. }
677        | GraphPattern::OrderBy { inner, .. }
678        | GraphPattern::Distinct { inner }
679        | GraphPattern::Reduced { inner }
680        | GraphPattern::Slice { inner, .. }
681        | GraphPattern::Service { inner, .. } => collect_pattern_variables(inner, out),
682    }
683}
684
685fn convert_agg(
686    ae: &AggregateExpression,
687    pre: &mut Vec<(String, FExpr)>,
688) -> Result<Agg, SparqlError> {
689    match ae {
690        AggregateExpression::CountSolutions { distinct } => Ok(Agg::CountStar {
691            distinct: *distinct,
692        }),
693        AggregateExpression::FunctionCall {
694            name,
695            expr,
696            distinct,
697        } => {
698            let var = match expr {
699                Expression::Variable(v) => v.as_str().to_string(),
700                // Aggregate over an EXPRESSION (e.g. SUM(?a * 2), AVG(?x + ?y)):
701                // compute it into a synthetic per-row column before grouping, then
702                // aggregate that column — so all the aggregate machinery (and the
703                // summary-safe COUNT path) keeps treating the argument as a slot.
704                other => {
705                    let name = format!("__agg{}", pre.len());
706                    pre.push((name.clone(), convert_expr(other)?));
707                    name
708                }
709            };
710            Ok(match name {
711                AggregateFunction::Count => Agg::Count(var, *distinct),
712                AggregateFunction::Sum => Agg::Sum(var),
713                AggregateFunction::Avg => Agg::Avg(var),
714                AggregateFunction::Min => Agg::Min(var),
715                AggregateFunction::Max => Agg::Max(var),
716                AggregateFunction::Sample => Agg::Sample(var),
717                AggregateFunction::GroupConcat { separator } => Agg::GroupConcat(
718                    var,
719                    separator.clone().unwrap_or_else(|| " ".to_string()),
720                    *distinct,
721                ),
722                _ => return Err(SparqlError::Unsupported("aggregate function")),
723            })
724        }
725    }
726}
727
728/// Lower a `spargebra` property path into a [`PathAst`].
729fn lower_path(p: &PropertyPathExpression) -> Result<PathAst, SparqlError> {
730    Ok(match p {
731        PropertyPathExpression::NamedNode(n) => PathAst::Pred(n.to_string(), false),
732        PropertyPathExpression::Reverse(inner) => reverse(lower_path(inner)?),
733        PropertyPathExpression::OneOrMore(inner) => {
734            PathAst::Rep(Box::new(lower_path(inner)?), Rep::OneOrMore)
735        }
736        PropertyPathExpression::ZeroOrMore(inner) => {
737            PathAst::Rep(Box::new(lower_path(inner)?), Rep::ZeroOrMore)
738        }
739        PropertyPathExpression::ZeroOrOne(inner) => {
740            PathAst::Rep(Box::new(lower_path(inner)?), Rep::ZeroOrOne)
741        }
742        PropertyPathExpression::Sequence(a, b) => {
743            PathAst::Seq(Box::new(lower_path(a)?), Box::new(lower_path(b)?))
744        }
745        PropertyPathExpression::Alternative(a, b) => {
746            PathAst::Alt(Box::new(lower_path(a)?), Box::new(lower_path(b)?))
747        }
748        PropertyPathExpression::NegatedPropertySet(preds) => {
749            PathAst::NegatedSet(preds.iter().map(|n| n.to_string()).collect(), false)
750        }
751    })
752}
753
754/// Translate a `spargebra` expression into the supported [`FExpr`] subset.
755fn convert_expr(e: &Expression) -> Result<FExpr, SparqlError> {
756    let bin = |op, l: &Expression, r: &Expression| -> Result<FExpr, SparqlError> {
757        Ok(FExpr::Compare(
758            op,
759            Box::new(convert_expr(l)?),
760            Box::new(convert_expr(r)?),
761        ))
762    };
763    let arith = |op, l: &Expression, r: &Expression| -> Result<FExpr, SparqlError> {
764        Ok(FExpr::Arith(
765            op,
766            Box::new(convert_expr(l)?),
767            Box::new(convert_expr(r)?),
768        ))
769    };
770    Ok(match e {
771        Expression::Variable(v) => FExpr::Var(v.as_str().to_string()),
772        Expression::NamedNode(n) => FExpr::Const(n.to_string()),
773        Expression::Literal(l) => FExpr::Const(l.to_string()),
774        Expression::Equal(l, r) => bin(Op::Eq, l, r)?,
775        Expression::Greater(l, r) => bin(Op::Gt, l, r)?,
776        Expression::GreaterOrEqual(l, r) => bin(Op::Ge, l, r)?,
777        Expression::Less(l, r) => bin(Op::Lt, l, r)?,
778        Expression::LessOrEqual(l, r) => bin(Op::Le, l, r)?,
779        Expression::And(l, r) => FExpr::And(Box::new(convert_expr(l)?), Box::new(convert_expr(r)?)),
780        Expression::Or(l, r) => FExpr::Or(Box::new(convert_expr(l)?), Box::new(convert_expr(r)?)),
781        Expression::Not(inner) => FExpr::Not(Box::new(convert_expr(inner)?)),
782        Expression::Bound(v) => FExpr::Bound(v.as_str().to_string()),
783        Expression::Add(l, r) => arith(ArithOp::Add, l, r)?,
784        Expression::Subtract(l, r) => arith(ArithOp::Sub, l, r)?,
785        Expression::Multiply(l, r) => arith(ArithOp::Mul, l, r)?,
786        Expression::Divide(l, r) => arith(ArithOp::Div, l, r)?,
787        Expression::Coalesce(items) => FExpr::Coalesce(
788            items
789                .iter()
790                .map(convert_expr)
791                .collect::<Result<Vec<_>, _>>()?,
792        ),
793        Expression::UnaryPlus(e) => convert_expr(e)?,
794        Expression::UnaryMinus(e) => FExpr::Arith(
795            ArithOp::Sub,
796            Box::new(FExpr::Const("0".into())),
797            Box::new(convert_expr(e)?),
798        ),
799        Expression::If(c, t, e) => FExpr::If(
800            Box::new(convert_expr(c)?),
801            Box::new(convert_expr(t)?),
802            Box::new(convert_expr(e)?),
803        ),
804        Expression::In(e, list) => FExpr::In(
805            Box::new(convert_expr(e)?),
806            list.iter().map(convert_expr).collect::<Result<_, _>>()?,
807        ),
808        Expression::SameTerm(l, r) => {
809            FExpr::SameTerm(Box::new(convert_expr(l)?), Box::new(convert_expr(r)?))
810        }
811        Expression::Exists(pattern) => {
812            // Build the sub-plan with a throwaway Select (its modifiers don't
813            // escape the EXISTS). The whole body is a WHERE pattern, so any BIND
814            // must stay in-tree (the discarded `sub.extends` would be lost).
815            let mut sub = Select::default();
816            let plan = build(pattern, &mut sub, true)?;
817            FExpr::Exists(Box::new(plan))
818        }
819        Expression::FunctionCall(func, params) => {
820            let builtin = match func {
821                Function::Str => Builtin::Str,
822                Function::Concat => Builtin::Concat,
823                Function::SubStr => Builtin::SubStr,
824                Function::StrBefore => Builtin::StrBefore,
825                Function::StrAfter => Builtin::StrAfter,
826                Function::StrLen => Builtin::StrLen,
827                Function::UCase => Builtin::UCase,
828                Function::LCase => Builtin::LCase,
829                Function::Abs => Builtin::Abs,
830                Function::Ceil => Builtin::Ceil,
831                Function::Floor => Builtin::Floor,
832                Function::Round => Builtin::Round,
833                Function::Contains => Builtin::Contains,
834                Function::StrStarts => Builtin::StrStarts,
835                Function::StrEnds => Builtin::StrEnds,
836                Function::IsIri => Builtin::IsIri,
837                Function::IsBlank => Builtin::IsBlank,
838                Function::IsLiteral => Builtin::IsLiteral,
839                Function::IsNumeric => Builtin::IsNumeric,
840                Function::Datatype => Builtin::Datatype,
841                Function::Lang => Builtin::Lang,
842                Function::Regex => Builtin::Regex,
843                Function::LangMatches => Builtin::LangMatches,
844                Function::StrDt => Builtin::StrDt,
845                Function::StrLang => Builtin::StrLang,
846                Function::Iri => Builtin::Iri,
847                Function::EncodeForUri => Builtin::EncodeForUri,
848                Function::Replace => Builtin::Replace,
849                Function::Md5 => Builtin::Md5,
850                Function::Sha1 => Builtin::Sha1,
851                Function::Sha256 => Builtin::Sha256,
852                Function::Sha384 => Builtin::Sha384,
853                Function::Sha512 => Builtin::Sha512,
854                Function::Year => Builtin::Year,
855                Function::Month => Builtin::Month,
856                Function::Day => Builtin::Day,
857                Function::Hours => Builtin::Hours,
858                Function::Minutes => Builtin::Minutes,
859                Function::Seconds => Builtin::Seconds,
860                Function::Timezone => Builtin::Timezone,
861                Function::Tz => Builtin::Tz,
862                Function::Rand => Builtin::Rand,
863                Function::Uuid => Builtin::Uuid,
864                Function::StrUuid => Builtin::StrUuid,
865                Function::BNode => Builtin::BNode,
866                // RDF-star / SPARQL-star.
867                Function::Triple => Builtin::TripleTerm,
868                Function::IsTriple => Builtin::IsTriple,
869                Function::Subject => Builtin::Subject,
870                Function::Predicate => Builtin::Predicate,
871                Function::Object => Builtin::Object,
872                // An `xsd:<type>(expr)` constructor parses as a call to the
873                // datatype IRI — map the supported XSD casts.
874                Function::Custom(nn) => match nn.as_str() {
875                    "http://www.w3.org/2001/XMLSchema#integer" => Builtin::CastInteger,
876                    "http://www.w3.org/2001/XMLSchema#decimal" => Builtin::CastDecimal,
877                    "http://www.w3.org/2001/XMLSchema#float" => Builtin::CastFloat,
878                    "http://www.w3.org/2001/XMLSchema#double" => Builtin::CastDouble,
879                    "http://www.w3.org/2001/XMLSchema#boolean" => Builtin::CastBoolean,
880                    "http://www.w3.org/2001/XMLSchema#string" => Builtin::CastString,
881                    // GeoSPARQL geof: functions.
882                    "http://www.opengis.net/def/function/geosparql/sfContains" => {
883                        Builtin::GeoSfContains
884                    }
885                    "http://www.opengis.net/def/function/geosparql/sfWithin" => {
886                        Builtin::GeoSfWithin
887                    }
888                    "http://www.opengis.net/def/function/geosparql/sfIntersects" => {
889                        Builtin::GeoSfIntersects
890                    }
891                    "http://www.opengis.net/def/function/geosparql/sfDisjoint" => {
892                        Builtin::GeoSfDisjoint
893                    }
894                    "http://www.opengis.net/def/function/geosparql/sfEquals" => {
895                        Builtin::GeoSfEquals
896                    }
897                    "http://www.opengis.net/def/function/geosparql/distance" => {
898                        Builtin::GeoDistance
899                    }
900                    "http://www.opengis.net/def/function/geosparql/envelope" => {
901                        Builtin::GeoEnvelope
902                    }
903                    // geo3: 3D extension of GeoSPARQL (see crate::geo3).
904                    "https://w3id.org/rete/geo3/function/distance3D" => Builtin::Geo3Distance,
905                    "https://w3id.org/rete/geo3/function/contains3D" => Builtin::Geo3Contains,
906                    "https://w3id.org/rete/geo3/function/within3D" => Builtin::Geo3Within,
907                    "https://w3id.org/rete/geo3/function/adjacent3D" => Builtin::Geo3Adjacent,
908                    _ => return Err(SparqlError::UnsupportedFunction(nn.as_str().to_string())),
909                },
910                _ => return Err(SparqlError::Unsupported("built-in function")),
911            };
912            let args = params
913                .iter()
914                .map(convert_expr)
915                .collect::<Result<Vec<_>, _>>()?;
916            FExpr::Func(builtin, args)
917        }
918    })
919}
920
921fn convert(tp: &SpTriplePattern) -> TriplePattern {
922    TriplePattern {
923        s: term_to_pattern(&tp.subject),
924        p: named_to_pattern(&tp.predicate),
925        o: term_to_pattern(&tp.object),
926    }
927}
928
929/// Whether a term position is an RDF-star quoted triple that carries INNER
930/// VARIABLES (`<< ?s :p ?o >>`) — a fully-concrete one is a plain constant term.
931fn is_var_quoted(t: &TermPattern) -> bool {
932    matches!(t, TermPattern::Triple(inner) if ground_quoted_token(inner).is_none())
933}
934
935/// Lower a BGP, desugaring RDF-star quoted-triple patterns with inner variables
936/// (Stage 3b). A quoted position `<< ?s :p ?o >>` is replaced by a fresh variable
937/// `?__qtN`, and the plan is wrapped so the quoted triple's components are
938/// constrained/bound: `FILTER(isTRIPLE(?__qtN))`, plus per component either a
939/// `sameTerm` FILTER (a concrete inner term, or an inner variable that is also
940/// bound by a regular pattern → a join) or a BIND via `Plan::Extend` (a fresh
941/// inner variable). Nested quoting recurses. A BGP with no inner-variable quoted
942/// pattern returns the plain `Plan::Bgp` unchanged (the hot path is untouched).
943fn lower_bgp(patterns: &[SpTriplePattern], counter: &mut usize) -> Plan {
944    if !patterns
945        .iter()
946        .any(|tp| is_var_quoted(&tp.subject) || is_var_quoted(&tp.object))
947    {
948        return Plan::Bgp(patterns.iter().map(convert).collect());
949    }
950
951    // Variables appearing in a REGULAR (non-quoted) position are bound by a scan,
952    // so an inner-quoted occurrence of one is a JOIN (FILTER sameTerm), not a BIND.
953    let mut regular_vars: std::collections::BTreeSet<String> = Default::default();
954    for tp in patterns {
955        for t in [&tp.subject, &tp.object] {
956            if let TermPattern::Variable(v) = t {
957                regular_vars.insert(v.as_str().to_string());
958            }
959        }
960        if let NamedNodePattern::Variable(v) = &tp.predicate {
961            regular_vars.insert(v.as_str().to_string());
962        }
963    }
964
965    let mut st = StarRewrite {
966        counter,
967        regular_vars,
968        filters: Vec::new(),
969        binds: Vec::new(),
970        bound: Default::default(),
971        seen: Default::default(),
972    };
973    let rewritten: Vec<TriplePattern> = patterns
974        .iter()
975        .map(|tp| TriplePattern {
976            s: st.rewrite_term(&tp.subject),
977            p: named_to_pattern(&tp.predicate),
978            o: st.rewrite_term(&tp.object),
979        })
980        .collect();
981
982    // Bgp innermost; each BIND (Extend) wraps it in the order recorded (a nested
983    // `?__qtN` is bound before the component vars extracted from it); the combined
984    // FILTER sits outermost — it may reference vars bound by those Extends.
985    let mut plan = Plan::Bgp(rewritten);
986    for (var, expr) in st.binds {
987        plan = Plan::Extend(var, expr, Box::new(plan));
988    }
989    if let Some(cond) = st
990        .filters
991        .into_iter()
992        .reduce(|a, b| FExpr::And(Box::new(a), Box::new(b)))
993    {
994        plan = Plan::Filter(cond, Box::new(plan));
995    }
996    plan
997}
998
999/// Scratch state for the quoted-pattern rewrite in [`lower_bgp`].
1000struct StarRewrite<'a> {
1001    counter: &'a mut usize,
1002    regular_vars: std::collections::BTreeSet<String>,
1003    filters: Vec<FExpr>,
1004    binds: Vec<(String, FExpr)>,
1005    bound: std::collections::BTreeSet<String>,
1006    /// Canonical quoted-triple text → the `__qtN` var already allocated for it,
1007    /// so a quoted triple that appears in more than one pattern (e.g.
1008    /// `<< s p o >> :a ?x ; :b ?y`, two annotations on one statement) REUSES the
1009    /// same var. Without this the two patterns share no variable and the BGP is
1010    /// a Cartesian product of every annotated triple against every other.
1011    seen: std::collections::BTreeMap<String, String>,
1012}
1013
1014fn star_accessor(f: Builtin, qt: &str) -> FExpr {
1015    FExpr::Func(f, vec![FExpr::Var(qt.to_string())])
1016}
1017fn star_same(a: FExpr, b: FExpr) -> FExpr {
1018    FExpr::SameTerm(Box::new(a), Box::new(b))
1019}
1020
1021impl StarRewrite<'_> {
1022    /// Rewrite a subject/object position; a quoted-with-vars becomes a fresh
1023    /// variable whose decomposition constraints are recorded.
1024    fn rewrite_term(&mut self, t: &TermPattern) -> PatternTerm {
1025        if is_var_quoted(t) {
1026            let TermPattern::Triple(inner) = t else {
1027                unreachable!("is_var_quoted implies Triple");
1028            };
1029            // Reuse the same fresh var for a quoted triple already seen in this
1030            // BGP, so repeated occurrences JOIN on it instead of forming a
1031            // Cartesian product (its decomposition constraints are added once).
1032            let key = format!("{inner:?}");
1033            if let Some(qt) = self.seen.get(&key) {
1034                return PatternTerm::Var(qt.clone());
1035            }
1036            *self.counter += 1;
1037            let qt = format!("__qt{}", self.counter);
1038            self.seen.insert(key, qt.clone());
1039            self.filters
1040                .push(FExpr::Func(Builtin::IsTriple, vec![FExpr::Var(qt.clone())]));
1041            self.decompose(inner, &qt);
1042            PatternTerm::Var(qt)
1043        } else {
1044            term_to_pattern(t)
1045        }
1046    }
1047
1048    /// Constrain the three components of quoted triple `inner` against the
1049    /// variable `qt` that holds it.
1050    fn decompose(&mut self, inner: &SpTriplePattern, qt: &str) {
1051        self.constrain(&inner.subject, star_accessor(Builtin::Subject, qt));
1052        match &inner.predicate {
1053            NamedNodePattern::NamedNode(n) => self.filters.push(star_same(
1054                star_accessor(Builtin::Predicate, qt),
1055                FExpr::Const(n.to_string()),
1056            )),
1057            NamedNodePattern::Variable(v) => {
1058                self.constrain_var(v.as_str(), star_accessor(Builtin::Predicate, qt))
1059            }
1060        }
1061        self.constrain(&inner.object, star_accessor(Builtin::Object, qt));
1062    }
1063
1064    fn constrain(&mut self, t: &TermPattern, acc: FExpr) {
1065        match t {
1066            TermPattern::NamedNode(n) => self
1067                .filters
1068                .push(star_same(acc, FExpr::Const(n.to_string()))),
1069            TermPattern::Literal(l) => self
1070                .filters
1071                .push(star_same(acc, FExpr::Const(l.to_string()))),
1072            TermPattern::Variable(v) => self.constrain_var(v.as_str(), acc),
1073            TermPattern::BlankNode(b) => self.constrain_var(&b.to_string(), acc),
1074            TermPattern::Triple(nested) => {
1075                if let Some(tok) = ground_quoted_token(nested) {
1076                    self.filters.push(star_same(acc, FExpr::Const(tok)));
1077                } else {
1078                    // Nested quoted-with-vars: bind a fresh var to this accessor,
1079                    // assert it is a triple, then recurse.
1080                    *self.counter += 1;
1081                    let qt2 = format!("__qt{}", self.counter);
1082                    self.binds.push((qt2.clone(), acc));
1083                    self.filters.push(FExpr::Func(
1084                        Builtin::IsTriple,
1085                        vec![FExpr::Var(qt2.clone())],
1086                    ));
1087                    self.decompose(nested, &qt2);
1088                }
1089            }
1090        }
1091    }
1092
1093    /// An inner variable: JOIN (FILTER sameTerm) if it is bound elsewhere,
1094    /// otherwise BIND it from the accessor.
1095    fn constrain_var(&mut self, name: &str, acc: FExpr) {
1096        let name = name.to_string();
1097        if self.regular_vars.contains(&name) || self.bound.contains(&name) {
1098            self.filters.push(star_same(acc, FExpr::Var(name)));
1099        } else {
1100            self.binds.push((name.clone(), acc));
1101            self.bound.insert(name);
1102        }
1103    }
1104}
1105
1106fn term_to_pattern(t: &TermPattern) -> PatternTerm {
1107    match t {
1108        TermPattern::NamedNode(n) => PatternTerm::Const(n.to_string()),
1109        TermPattern::Literal(l) => PatternTerm::Const(l.to_string()),
1110        // A blank node in a query pattern is a non-distinguished variable (and
1111        // spargebra uses one as the join var when expanding fixed paths like
1112        // `a/b`). Its label is stable across occurrences, so it joins correctly.
1113        TermPattern::BlankNode(b) => PatternTerm::Var(b.to_string()),
1114        TermPattern::Variable(v) => PatternTerm::Var(v.as_str().to_string()),
1115        // RDF-star: a FULLY-CONCRETE quoted triple (`<< :s :p :o >>`) lowers to
1116        // its canonical dictionary token — an ordinary constant, matched by the
1117        // existing BGP engine (annotation lookup on a known statement). A quoted
1118        // pattern with INNER VARIABLES (`<< ?s :p ?o >>`) can't be a Const/Var
1119        // yet; that needs a `PatternTerm::Quoted` matcher (rdf-star Stage 3). For
1120        // now it lowers to a token that cannot exist in the dictionary, so it
1121        // matches nothing (empty result) rather than mis-matching.
1122        TermPattern::Triple(tp) => match ground_quoted_token(tp) {
1123            Some(tok) => PatternTerm::Const(tok),
1124            None => PatternTerm::Const("<< rdf-star inner-var pattern >>".to_string()),
1125        },
1126    }
1127}
1128
1129/// The canonical `<< s p o >>` token for a quoted triple pattern, or `None` if
1130/// any inner term is a variable/blank (not yet a resolvable constant). Recurses
1131/// for nested quoting. Mirrors the ingest tokenizer + oxrdf's `Triple` Display.
1132fn ground_quoted_token(tp: &SpTriplePattern) -> Option<String> {
1133    fn ground(t: &TermPattern) -> Option<String> {
1134        match t {
1135            TermPattern::NamedNode(n) => Some(n.to_string()),
1136            TermPattern::Literal(l) => Some(l.to_string()),
1137            TermPattern::Triple(inner) => ground_quoted_token(inner),
1138            TermPattern::BlankNode(_) | TermPattern::Variable(_) => None,
1139        }
1140    }
1141    let s = ground(&tp.subject)?;
1142    let p = match &tp.predicate {
1143        NamedNodePattern::NamedNode(n) => n.to_string(),
1144        NamedNodePattern::Variable(_) => return None,
1145    };
1146    let o = ground(&tp.object)?;
1147    Some(format!("<<{s} {p} {o}>>"))
1148}
1149
1150fn named_to_pattern(n: &NamedNodePattern) -> PatternTerm {
1151    match n {
1152        NamedNodePattern::NamedNode(nn) => PatternTerm::Const(nn.to_string()),
1153        NamedNodePattern::Variable(v) => PatternTerm::Var(v.as_str().to_string()),
1154    }
1155}
1156
1157#[cfg(test)]
1158mod tests {
1159    use super::*;
1160
1161    #[test]
1162    fn version_parsing_select_only_and_uniform_errors() {
1163        let q = "  # leading\n VERSION \"1.2\" SELECT * WHERE {}";
1164        assert!(strip_version(q).trim_start().starts_with("SELECT"));
1165        assert!(parse_select(q).is_ok());
1166        assert_eq!(strip_version("# comment only"), "# comment only");
1167        assert_eq!(
1168            strip_version("VERSION invalid SELECT * WHERE {}"),
1169            "VERSION invalid SELECT * WHERE {}"
1170        );
1171        assert!(matches!(
1172            parse_select("ASK {}"),
1173            Err(SparqlError::Unsupported(_))
1174        ));
1175        assert!(matches!(
1176            parse_select("not sparql"),
1177            Err(SparqlError::Parse(_))
1178        ));
1179    }
1180
1181    #[test]
1182    fn lowers_every_graph_operator_dataset_modifier_and_subquery() {
1183        let query = r#"
1184            SELECT DISTINCT ?s ?x
1185            FROM <http://ex/default>
1186            FROM NAMED <http://ex/named>
1187            WHERE {
1188              { ?s <http://ex/p> ?o .
1189                OPTIONAL { ?s <http://ex/q> ?q FILTER(?q > 1) }
1190              }
1191              UNION { GRAPH ?g { ?s <http://ex/r> ?o } }
1192              MINUS { ?s <http://ex/bad> ?o }
1193              VALUES (?v ?u) { (1 UNDEF) (2 "two") }
1194              BIND(?v + 1 AS ?x)
1195              FILTER(BOUND(?x) && (?x IN (1, 2)))
1196            }
1197            ORDER BY ASC(?s) DESC(?x)
1198            OFFSET 1 LIMIT 2
1199        "#;
1200        let select = parse_select(query).unwrap();
1201        assert!(select.distinct);
1202        assert_eq!(select.project, ["s", "x"]);
1203        assert_eq!(select.offset, 1);
1204        assert_eq!(select.limit, Some(2));
1205        assert_eq!(select.order.len(), 2);
1206        assert_eq!(select.from, ["<http://ex/default>"]);
1207        assert_eq!(select.from_named.unwrap(), ["<http://ex/named>"]);
1208
1209        let subquery = parse_select(
1210            "SELECT ?s WHERE { ?s <http://ex/p> ?o . { SELECT REDUCED ?s WHERE { ?s <http://ex/q> ?v } LIMIT 1 } }",
1211        )
1212        .unwrap();
1213        assert!(matches!(subquery.plan, Plan::Join(..)));
1214
1215        let fixed_service = parse_select(
1216            "SELECT * WHERE { SERVICE SILENT <http://example.test/sparql> { ?s <http://ex/p> ?o OPTIONAL { ?s <http://ex/q> ?q } } }",
1217        )
1218        .unwrap();
1219        assert!(matches!(
1220            fixed_service.plan,
1221            Plan::Service { silent: true, .. }
1222        ));
1223        assert!(matches!(
1224            parse_select("SELECT * WHERE { SERVICE ?endpoint { ?s ?p ?o } }"),
1225            Err(SparqlError::Unsupported(_))
1226        ));
1227    }
1228
1229    #[test]
1230    fn lowers_aggregates_having_preexpressions_and_all_property_path_shapes() {
1231        let grouped = parse_select(
1232            r#"
1233            SELECT ?g
1234                   (COUNT(*) AS ?all)
1235                   (COUNT(DISTINCT ?v) AS ?count)
1236                   (SUM(?v * 2) AS ?sum)
1237                   (AVG(?v) AS ?avg)
1238                   (MIN(?v) AS ?min)
1239                   (MAX(?v) AS ?max)
1240                   (SAMPLE(?v) AS ?sample)
1241                   (GROUP_CONCAT(DISTINCT ?label; SEPARATOR="|") AS ?labels)
1242            WHERE { ?s <http://ex/g> ?g ; <http://ex/v> ?v ; <http://ex/label> ?label }
1243            GROUP BY ?g
1244            HAVING (SUM(?v) > 0)
1245            ORDER BY DESC(?sum)
1246            "#,
1247        )
1248        .unwrap();
1249        let group = grouped.group.unwrap();
1250        assert_eq!(group.by, ["g"]);
1251        assert_eq!(group.aggs.len(), 9);
1252        assert_eq!(group.pre.len(), 1);
1253        assert_eq!(grouped.having.len(), 1);
1254
1255        for path in [
1256            "<http://ex/p>",
1257            "^<http://ex/p>",
1258            "<http://ex/p>+",
1259            "<http://ex/p>*",
1260            "<http://ex/p>?",
1261            "<http://ex/p>/<http://ex/q>",
1262            "<http://ex/p>|<http://ex/q>",
1263            "!(<http://ex/p>|<http://ex/q>)",
1264        ] {
1265            let q = format!("SELECT * WHERE {{ ?s {path} ?o }}");
1266            assert!(parse_select(&q).is_ok(), "{path}");
1267        }
1268    }
1269
1270    #[test]
1271    fn lowers_expression_and_builtin_matrix_in_projection_aliases() {
1272        for expression in [
1273            "?v = 1",
1274            "?v > 1",
1275            "?v >= 1",
1276            "?v < 1",
1277            "?v <= 1",
1278            "(?v = 1) || (?v = 2)",
1279            "!(?v = 1)",
1280            "+?v",
1281            "-?v",
1282            "?v - 1",
1283            "?v * 2",
1284            "?v / 2",
1285            "COALESCE(?missing, ?v)",
1286            "IF(BOUND(?v), ?v, 0)",
1287            "sameTerm(?v, 1)",
1288            "EXISTS { ?s <http://ex/inside> ?v BIND(STR(?v) AS ?text) }",
1289            "STR(?v)",
1290            "CONCAT(\"a\", \"b\")",
1291            "SUBSTR(\"abc\", 2)",
1292            "STRBEFORE(\"abc\", \"b\")",
1293            "STRAFTER(\"abc\", \"b\")",
1294            "STRLEN(\"abc\")",
1295            "UCASE(\"abc\")",
1296            "LCASE(\"ABC\")",
1297            "ABS(-2)",
1298            "CEIL(1.2)",
1299            "FLOOR(1.2)",
1300            "ROUND(1.5)",
1301            "CONTAINS(\"abc\", \"b\")",
1302            "STRSTARTS(\"abc\", \"a\")",
1303            "STRENDS(\"abc\", \"c\")",
1304            "isIRI(<http://ex/a>)",
1305            "isBLANK(?v)",
1306            "isLITERAL(\"x\")",
1307            "isNUMERIC(1)",
1308            "DATATYPE(\"x\")",
1309            "LANG(\"x\"@en)",
1310            "REGEX(\"abc\", \"a\")",
1311            "LANGMATCHES(\"en-GB\", \"en\")",
1312            "STRDT(\"x\", <http://ex/type>)",
1313            "STRLANG(\"x\", \"en\")",
1314            "IRI(\"http://ex/a\")",
1315            "ENCODE_FOR_URI(\"a b\")",
1316            "REPLACE(\"abc\", \"b\", \"x\")",
1317            "MD5(\"abc\")",
1318            "SHA1(\"abc\")",
1319            "SHA256(\"abc\")",
1320            "SHA384(\"abc\")",
1321            "SHA512(\"abc\")",
1322            "YEAR(\"2024-01-01T00:00:00Z\"^^<http://www.w3.org/2001/XMLSchema#dateTime>)",
1323            "MONTH(\"2024-01-01T00:00:00Z\"^^<http://www.w3.org/2001/XMLSchema#dateTime>)",
1324            "DAY(\"2024-01-01T00:00:00Z\"^^<http://www.w3.org/2001/XMLSchema#dateTime>)",
1325            "HOURS(\"2024-01-01T00:00:00Z\"^^<http://www.w3.org/2001/XMLSchema#dateTime>)",
1326            "MINUTES(\"2024-01-01T00:00:00Z\"^^<http://www.w3.org/2001/XMLSchema#dateTime>)",
1327            "SECONDS(\"2024-01-01T00:00:00Z\"^^<http://www.w3.org/2001/XMLSchema#dateTime>)",
1328            "TIMEZONE(\"2024-01-01T00:00:00Z\"^^<http://www.w3.org/2001/XMLSchema#dateTime>)",
1329            "TZ(\"2024-01-01T00:00:00Z\"^^<http://www.w3.org/2001/XMLSchema#dateTime>)",
1330            "RAND()",
1331            "UUID()",
1332            "STRUUID()",
1333            "BNODE(\"x\")",
1334            "<http://www.w3.org/2001/XMLSchema#integer>(\"1\")",
1335            "<http://www.w3.org/2001/XMLSchema#decimal>(\"1.2\")",
1336            "<http://www.w3.org/2001/XMLSchema#float>(\"1\")",
1337            "<http://www.w3.org/2001/XMLSchema#double>(\"1\")",
1338            "<http://www.w3.org/2001/XMLSchema#boolean>(\"true\")",
1339            "<http://www.w3.org/2001/XMLSchema#string>(1)",
1340            "<http://www.opengis.net/def/function/geosparql/sfContains>(?a, ?b)",
1341            "<http://www.opengis.net/def/function/geosparql/sfWithin>(?a, ?b)",
1342            "<http://www.opengis.net/def/function/geosparql/sfIntersects>(?a, ?b)",
1343            "<http://www.opengis.net/def/function/geosparql/sfDisjoint>(?a, ?b)",
1344            "<http://www.opengis.net/def/function/geosparql/sfEquals>(?a, ?b)",
1345            "<http://www.opengis.net/def/function/geosparql/distance>(?a, ?b, <http://www.opengis.net/def/uom/OGC/1.0/metre>)",
1346            "<http://www.opengis.net/def/function/geosparql/envelope>(?a)",
1347            "<https://w3id.org/rete/geo3/function/distance3D>(?a, ?b)",
1348            "<https://w3id.org/rete/geo3/function/contains3D>(?a, ?b)",
1349            "<https://w3id.org/rete/geo3/function/within3D>(?a, ?b)",
1350            "<https://w3id.org/rete/geo3/function/adjacent3D>(?a, ?b)",
1351            "<https://w3id.org/rete/geo3/function/adjacent3D>(?a, ?b, 5)",
1352        ] {
1353            let q = format!("SELECT ({expression} AS ?result) WHERE {{ VALUES ?v {{ 1 }} }}");
1354            assert!(parse_select(&q).is_ok(), "{expression}");
1355        }
1356        assert!(matches!(
1357            parse_select("SELECT (<http://ex/unsupported>(1) AS ?x) WHERE {}"),
1358            Err(SparqlError::UnsupportedFunction(iri)) if iri == "http://ex/unsupported"
1359        ));
1360    }
1361
1362    #[test]
1363    fn predicate_collection_walks_query_forms_wrappers_and_complex_paths() {
1364        let select = query_predicates(
1365            "SELECT * WHERE { { ?s (<http://ex/p>|^<http://ex/q>)/<http://ex/r>* ?o } UNION { GRAPH <http://ex/g> { ?s <http://ex/s> ?o } } OPTIONAL { ?s ?variable ?o } MINUS { ?s <http://ex/t> ?o } }",
1366        )
1367        .unwrap();
1368        for p in ["p", "q", "r", "s", "t"] {
1369            assert!(select.contains(&format!("<http://ex/{p}>")));
1370        }
1371        assert_eq!(
1372            query_predicates("ASK { ?s <http://ex/ask> ?o }")
1373                .unwrap()
1374                .len(),
1375            1
1376        );
1377        assert_eq!(
1378            query_predicates("CONSTRUCT { ?s <http://ex/out> ?o } WHERE { ?s <http://ex/in> ?o }")
1379                .unwrap(),
1380            ["<http://ex/in>".to_string()].into_iter().collect()
1381        );
1382        assert_eq!(
1383            query_predicates("DESCRIBE ?s WHERE { ?s <http://ex/describe> ?o }")
1384                .unwrap()
1385                .len(),
1386            1
1387        );
1388        assert!(
1389            query_predicates("SELECT * WHERE { ?s !(<http://ex/p>|<http://ex/q>) ?o }")
1390                .unwrap()
1391                .is_empty()
1392        );
1393    }
1394
1395    #[test]
1396    fn rdf_star_lowering_handles_ground_variables_reuse_and_nested_terms() {
1397        for query in [
1398            "SELECT * WHERE { << <http://ex/s> <http://ex/p> \"o\" >> <http://ex/a> ?v }",
1399            "SELECT * WHERE { << ?s <http://ex/p> ?o >> <http://ex/a> ?v . << ?s <http://ex/p> ?o >> <http://ex/b> ?w }",
1400            "SELECT * WHERE { ?s <http://ex/p> ?o . << ?s ?pred ?o >> <http://ex/a> ?v }",
1401            "SELECT * WHERE { << << ?s <http://ex/p> ?o >> <http://ex/q> ?inner >> <http://ex/a> ?v }",
1402        ] {
1403            let lowered = parse_select(query).unwrap();
1404            assert!(lowered.star_counter > 0 || matches!(lowered.plan, Plan::Bgp(_)), "{query}");
1405        }
1406    }
1407
1408    #[test]
1409    fn sub_select_modifiers_stay_inside_the_subquery() {
1410        // The transparent-modifier peel used to walk straight through the nested
1411        // SELECT boundary, so the inner LIMIT overwrote the outer one AND never
1412        // reached the subquery: `… WHERE { { SELECT … LIMIT 10 } } LIMIT 3`
1413        // returned 10 rows. The outer slice must survive, and the inner one must
1414        // travel with its own Select.
1415        let outer = parse_select(
1416            "SELECT ?s WHERE { { SELECT ?s WHERE { ?s <http://ex/p> ?o } LIMIT 10 } } LIMIT 3",
1417        )
1418        .unwrap();
1419        assert_eq!(outer.limit, Some(3), "outer LIMIT was overwritten");
1420        assert!(
1421            matches!(outer.plan, Plan::Subquery(_)),
1422            "inner SELECT is not a subquery"
1423        );
1424        if let Plan::Subquery(inner) = &outer.plan {
1425            assert_eq!(
1426                inner.limit,
1427                Some(10),
1428                "inner LIMIT did not travel with the subquery"
1429            );
1430        }
1431
1432        // OFFSET rides along with LIMIT.
1433        let sliced = parse_select(
1434            "SELECT ?s WHERE { { SELECT ?s WHERE { ?s <http://ex/p> ?o } LIMIT 10 } } OFFSET 5 LIMIT 2",
1435        )
1436        .unwrap();
1437        assert_eq!((sliced.offset, sliced.limit), (5, Some(2)));
1438
1439        // A nested DISTINCT must not make the outer query DISTINCT.
1440        let distinct = parse_select(
1441            "SELECT ?s WHERE { { SELECT DISTINCT ?s WHERE { ?s <http://ex/p> ?o } } } LIMIT 3",
1442        )
1443        .unwrap();
1444        assert!(
1445            !distinct.distinct,
1446            "inner DISTINCT leaked to the outer query"
1447        );
1448        assert_eq!(distinct.limit, Some(3));
1449
1450        // A plain top-level slice still peels (no subquery in sight).
1451        let plain = parse_select("SELECT ?s WHERE { ?s <http://ex/p> ?o } LIMIT 3").unwrap();
1452        assert_eq!(plain.limit, Some(3));
1453        assert!(matches!(plain.plan, Plan::Bgp(_)));
1454    }
1455}