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