Skip to main content

rete_core/
sparql.rs

1//! SPARQL parsing, lowering, and evaluation (SPEC.md §8).
2//!
3//! Queries are parsed with `spargebra`, lowered into a small plan algebra, and
4//! evaluated against the `.rete` indexes. BGPs use the integer-space hash-join
5//! engine in [`bgp`]; filters, joins, OPTIONAL, UNION, MINUS, VALUES, property
6//! paths, named graphs, aggregates, and query forms are handled in the sibling
7//! lowering/evaluation modules. Unsupported features are rejected explicitly
8//! rather than silently dropped.
9//!
10//! [`bgp`]: crate::bgp
11
12use spargebra::Query;
13
14use crate::bgp::{Binding, PatternTerm, TriplePattern};
15use crate::file::Rete;
16
17mod aggregate;
18mod diag;
19mod distinct;
20mod distinct_union;
21mod eval;
22mod expr;
23mod fedmerge;
24mod lower;
25mod par_agg;
26mod partition;
27mod path;
28mod prefetch;
29mod ql;
30mod sparql12;
31mod value;
32
33pub use diag::{warnings_json, QueryWarning, WarningSeverity};
34use eval::{
35    ask_solution, instantiate, raw_solutions, run_select, run_select_communities, run_select_ids,
36};
37pub use fedmerge::FederationPlan;
38use lower::{lower_pattern, lower_select, parse_query};
39pub use lower::{parse_select, query_predicates};
40pub use par_agg::{query_threads, set_query_threads, sharded_queries};
41pub use partition::PartitionPlan;
42// Re-exported so the sibling modules' `use super::*` can reach the evaluator
43// (expr's FILTER EXISTS evaluates a sub-plan via `eval_plan_in`).
44pub(crate) use eval::eval_plan_in;
45
46#[derive(Debug, thiserror::Error)]
47#[non_exhaustive]
48pub enum SparqlError {
49    #[error("parse error: {0}")]
50    Parse(String),
51    #[error("unsupported query feature: {0}")]
52    Unsupported(&'static str),
53    /// A function call whose IRI is neither a SPARQL built-in nor one of the
54    /// extension functions rete implements (XSD casts, GeoSPARQL `geof:`, `geo3:`).
55    #[error("unsupported query feature: function <{0}> is not implemented")]
56    UnsupportedFunction(String),
57    /// A (non-SILENT) `SERVICE` block failed: the endpoint errored, returned
58    /// unparseable results, or no [`ServiceClient`](crate::ServiceClient) is
59    /// attached to the file handle. Partial results are never returned.
60    #[error("SERVICE federation: {0}")]
61    Service(String),
62    /// [`partition_plan`] / [`eval_query_partitioned`] refused to split a
63    /// query by a variable, because the chunks' answers together would not be
64    /// the query's answer; the message says why and what to do instead.
65    #[error("cannot split this query {0}")]
66    Partition(String),
67    /// [`FederationPlan::new`] refused a query whose solution modifiers or aggregates cannot be
68    /// merged from several sources' answers; the message says why and what to do instead.
69    #[error("cannot federate this query: {0}")]
70    Federation(String),
71}
72
73/// A lowered SELECT query: solution modifiers plus the evaluation plan tree.
74#[derive(Debug, Clone)]
75pub struct Select {
76    /// Projected variable names (empty = SELECT *).
77    pub project: Vec<String>,
78    /// DISTINCT (or REDUCED) requested.
79    pub distinct: bool,
80    /// OFFSET (solutions to skip).
81    pub offset: usize,
82    /// LIMIT (max solutions), if any.
83    pub limit: Option<usize>,
84    /// GROUP BY + aggregates, applied after the plan and before projection.
85    pub group: Option<GroupSpec>,
86    /// BIND/aggregate-alias assignments `(result_var, expr)`, applied after
87    /// aggregation (e.g. `(COUNT(?f) AS ?n)` aliases an internal var to `?n`).
88    pub extends: Vec<(String, FExpr)>,
89    /// ORDER BY keys `(expr, descending)`, applied before projection/slice.
90    pub order: Vec<(FExpr, bool)>,
91    /// HAVING conditions, applied after aggregation.
92    pub having: Vec<FExpr>,
93    /// `FROM <iri>` graphs: when non-empty, the query's default graph is the
94    /// union (RDF merge) of these named graphs.
95    pub from: Vec<String>,
96    /// `FROM NAMED <iri>` graphs: when `Some`, `GRAPH` may only see these.
97    pub from_named: Option<Vec<String>>,
98    /// **Union default graph** (opt-in, non-standard): when set and the query
99    /// has no `FROM` of its own, the active default graph becomes the RDF merge
100    /// of the file's default graph and *every* named graph — the mode Virtuoso,
101    /// GraphDB and Jena TDB (`tdb:unionDefaultGraph`) offer. Plain SPARQL says a
102    /// pattern outside `GRAPH` matches only the real default graph, so this is
103    /// NEVER set by the parser — only by [`eval_query_with`] when the caller
104    /// asked for it. An explicit `FROM` wins (the query named its own dataset).
105    pub union_default: bool,
106    /// The graph-pattern evaluation plan.
107    pub plan: Plan,
108    /// Monotonic counter for minting query-unique fresh variable names while
109    /// lowering (e.g. the `?__qtN` holders that desugar RDF-star quoted-triple
110    /// patterns). Kept on `Select` so it stays unique across every BGP in one
111    /// query — two joined BGPs must not both mint `__qt1` and get unified.
112    pub star_counter: usize,
113}
114
115impl Default for Select {
116    fn default() -> Self {
117        Select {
118            project: Vec::new(),
119            distinct: false,
120            offset: 0,
121            limit: None,
122            group: None,
123            extends: Vec::new(),
124            order: Vec::new(),
125            having: Vec::new(),
126            from: Vec::new(),
127            from_named: None,
128            union_default: false,
129            plan: Plan::Bgp(Vec::new()),
130            star_counter: 0,
131        }
132    }
133}
134
135/// GROUP BY specification: grouping variables and result aggregates.
136#[derive(Debug, Clone)]
137pub struct GroupSpec {
138    /// Variables to group by (empty = single group over all solutions).
139    pub by: Vec<String>,
140    /// `(result_variable, aggregate)` pairs.
141    pub aggs: Vec<(String, Agg)>,
142    /// Synthetic per-row columns computed *before* grouping — `(var, expr)` for
143    /// each aggregate whose argument is an expression rather than a bare variable
144    /// (e.g. `SUM(?a * 2)` lowers to a hidden `__aggN = ?a * 2`, then `SUM(__aggN)`).
145    /// Empty for the common case (aggregating a plain variable).
146    pub pre: Vec<(String, FExpr)>,
147}
148
149/// A supported aggregate function.
150#[derive(Debug, Clone)]
151pub enum Agg {
152    /// COUNT(*) — number of solutions in the group.
153    CountStar {
154        distinct: bool,
155    },
156    /// COUNT(?v) — number of (optionally distinct) bound values.
157    Count(String, bool),
158    Sum(String),
159    Avg(String),
160    Min(String),
161    Max(String),
162    /// SAMPLE(?v) — any one value from the group.
163    Sample(String),
164    /// GROUP_CONCAT(\[DISTINCT\] ?v; SEPARATOR=...) — values joined by the
165    /// separator (deduplicated when `distinct`).
166    GroupConcat(String, String, bool),
167}
168
169/// A SPARQL graph-pattern evaluation plan (the supported algebra subset).
170#[derive(Debug, Clone)]
171#[must_use]
172pub enum Plan {
173    /// Basic graph pattern: triple patterns joined on shared variables.
174    Bgp(Vec<TriplePattern>),
175    /// Conjunction of two patterns (inner join on shared variables).
176    Join(Box<Plan>, Box<Plan>),
177    /// UNION: all solutions of either side.
178    Union(Box<Plan>, Box<Plan>),
179    /// OPTIONAL (left join): left solutions, extended by the right where it
180    /// matches (and passes the optional condition), kept as-is where it doesn't.
181    LeftJoin(Box<Plan>, Box<Plan>, Option<FExpr>),
182    /// FILTER over an inner pattern.
183    Filter(FExpr, Box<Plan>),
184    /// In-pattern `BIND(expr AS ?var)`: each inner solution extended with `?var`
185    /// (left unbound where `expr` errors). Distinct from the projection-time
186    /// alias list (`Select::extends`) — this one is *inside* the graph pattern,
187    /// so a following FILTER or join sees the bound variable.
188    Extend(String, FExpr, Box<Plan>),
189    /// A property path `subject <path> object`.
190    Path(PatternTerm, PathAst, PatternTerm),
191    /// Inline `VALUES`: variable names and rows of optional ground-term tokens
192    /// (`None` = UNDEF).
193    Values(Vec<String>, Vec<Vec<Option<String>>>),
194    /// `MINUS`: left solutions, minus those compatible with a right solution
195    /// that shares at least one bound variable.
196    Minus(Box<Plan>, Box<Plan>),
197    /// `GRAPH <iri>|?g { … }` — evaluate the inner pattern against a named graph.
198    Graph(GraphTarget, Box<Plan>),
199    /// The **distinct** bindings of `vars` over the union of single triple
200    /// patterns (`sources`) — each solution once, however many sources (or
201    /// triples of one source) produce it. Every variable of a source that is
202    /// not in `vars` is anonymous: matched, never bound in the output. With
203    /// `vars` empty it is an existence test (one empty solution or none).
204    ///
205    /// Built only by the OWL 2 QL rewriter (`ql`): an entailed atom such as
206    /// `?x a C` holds once per entailed triple, while its rewriting
207    /// (`?x a C₁`, `?x a C₂`, `?x p ?_` for a `p` with domain `C`, …) matches
208    /// it once per *asserted* triple. The sources stream sorted on the key
209    /// and are merged, so deduplicating costs one cursor per source, not a
210    /// set of every solution.
211    DistinctUnion {
212        vars: Vec<String>,
213        sources: Vec<TriplePattern>,
214    },
215    /// A nested `SELECT` subquery: evaluated independently to its projected
216    /// solutions, which then join with the surrounding pattern on shared
217    /// variables (only the subquery's projected variables are visible outside).
218    Subquery(Box<Select>),
219    /// `SERVICE [SILENT] <endpoint> { … }` — SPARQL 1.1 federated query. The
220    /// inner pattern is shipped (as `query`, its re-serialized SPARQL text) to
221    /// the remote endpoint through the file's attached
222    /// [`ServiceClient`](crate::ServiceClient) at evaluation time; the returned
223    /// solutions join the surrounding pattern on shared variables like any
224    /// other operand. Under `silent`, a failed call degrades to one empty
225    /// solution (per the spec); otherwise it fails the whole query.
226    Service {
227        silent: bool,
228        /// The endpoint IRI (no angle brackets) — where the sub-query is sent.
229        endpoint: String,
230        /// Variables the inner pattern can bind (an over-approximation is fine:
231        /// unreturned variables just stay unbound).
232        vars: Vec<String>,
233        /// The inner pattern as a standalone `SELECT`, exactly what is sent.
234        query: String,
235    },
236}
237
238/// The target of a `GRAPH` block.
239#[derive(Debug, Clone)]
240pub enum GraphTarget {
241    /// `GRAPH <iri>` — one specific named graph.
242    Named(String),
243    /// `GRAPH ?g` — every named graph, binding the variable to its IRI.
244    Var(String),
245}
246
247/// Path repetition operator.
248#[derive(Debug, Clone, Copy, PartialEq, Eq)]
249pub enum Rep {
250    /// exactly one hop (a plain predicate)
251    One,
252    /// `+` — one or more hops (transitive closure)
253    OneOrMore,
254    /// `*` — zero or more hops (reflexive-transitive closure)
255    ZeroOrMore,
256    /// `?` — zero or one hop
257    ZeroOrOne,
258}
259
260/// A lowered property path expression, evaluated as a binary relation over the
261/// graph's nodes.
262#[derive(Debug, Clone)]
263pub enum PathAst {
264    /// A single predicate, optionally reversed.
265    Pred(String, bool),
266    /// Repetition (`*`/`+`/`?`) of a sub-path.
267    Rep(Box<PathAst>, Rep),
268    /// Sequence `a/b` (relational composition).
269    Seq(Box<PathAst>, Box<PathAst>),
270    /// Alternative `a|b` (union).
271    Alt(Box<PathAst>, Box<PathAst>),
272    /// Negated property set `!(p1|…|pn)` — one step over any predicate **not**
273    /// in the set, in the given direction (`reversed` for the `^p` members,
274    /// which `spargebra` wraps in a `Reverse`).
275    NegatedSet(Vec<String>, bool),
276}
277
278/// Comparison operators supported in FILTER.
279#[derive(Debug, Clone, Copy, PartialEq, Eq)]
280pub enum Op {
281    Eq,
282    Ne,
283    Lt,
284    Le,
285    Gt,
286    Ge,
287}
288
289/// Arithmetic operators (numeric).
290#[derive(Debug, Clone, Copy, PartialEq, Eq)]
291pub enum ArithOp {
292    Add,
293    Sub,
294    Mul,
295    Div,
296}
297
298/// Supported SPARQL built-in functions (the unambiguous subset over our
299/// term-token model).
300#[derive(Debug, Clone, Copy, PartialEq, Eq)]
301pub enum Builtin {
302    Str,
303    StrLen,
304    UCase,
305    LCase,
306    Abs,
307    Ceil,
308    Floor,
309    Round,
310    Concat,
311    SubStr,
312    StrBefore,
313    StrAfter,
314    Contains,
315    StrStarts,
316    StrEnds,
317    IsIri,
318    IsBlank,
319    IsLiteral,
320    IsNumeric,
321    Datatype,
322    Lang,
323    Regex,
324    LangMatches,
325    StrDt,
326    StrLang,
327    Iri,
328    EncodeForUri,
329    Replace,
330    Md5,
331    Sha1,
332    Sha256,
333    Sha384,
334    Sha512,
335    Year,
336    Month,
337    Day,
338    Hours,
339    Minutes,
340    Seconds,
341    Timezone,
342    Tz,
343    CastInteger,
344    CastDecimal,
345    CastFloat,
346    CastDouble,
347    CastBoolean,
348    CastString,
349    Rand,
350    Uuid,
351    StrUuid,
352    BNode,
353    // GeoSPARQL (geof:) — topological relations → xsd:boolean, distance →
354    // xsd:double, envelope → geo:wktLiteral. See crate::geo.
355    GeoSfContains,
356    GeoSfWithin,
357    GeoSfIntersects,
358    GeoSfDisjoint,
359    GeoSfEquals,
360    GeoDistance,
361    GeoEnvelope,
362    // geo3 — 3D extension of GeoSPARQL (AABB topology + distance). See crate::geo3.
363    Geo3Distance,
364    Geo3Contains,
365    Geo3Within,
366    Geo3Adjacent,
367    // RDF-star / SPARQL-star: construct + inspect quoted triples (`<<s p o>>`).
368    /// `TRIPLE(s, p, o)` → the quoted triple term.
369    TripleTerm,
370    /// `isTRIPLE(t)` → whether `t` is a quoted triple (a boolean builtin).
371    IsTriple,
372    /// `SUBJECT(t)` / `PREDICATE(t)` / `OBJECT(t)` → the component of a quoted triple.
373    Subject,
374    Predicate,
375    Object,
376}
377
378/// A small boolean/comparison expression for FILTER (a subset of SPARQL exprs).
379#[derive(Debug, Clone)]
380pub enum FExpr {
381    Var(String),
382    /// A constant term token (IRI/literal) or numeric literal's text.
383    Const(String),
384    /// Numeric arithmetic on two sub-expressions.
385    Arith(ArithOp, Box<FExpr>, Box<FExpr>),
386    /// A built-in function call.
387    Func(Builtin, Vec<FExpr>),
388    /// `COALESCE(...)` — first sub-expression that yields a value.
389    Coalesce(Vec<FExpr>),
390    /// `IF(cond, then, else)` — evaluate `cond` as a boolean and pick a branch.
391    If(Box<FExpr>, Box<FExpr>, Box<FExpr>),
392    /// `expr IN (a, b, …)` — true if `expr` value-equals any list member.
393    In(Box<FExpr>, Vec<FExpr>),
394    /// `sameTerm(a, b)` — strict term identity (no value coercion).
395    SameTerm(Box<FExpr>, Box<FExpr>),
396    Compare(Op, Box<FExpr>, Box<FExpr>),
397    And(Box<FExpr>, Box<FExpr>),
398    Or(Box<FExpr>, Box<FExpr>),
399    Not(Box<FExpr>),
400    Bound(String),
401    /// `EXISTS { … }` — true if the sub-pattern has a solution compatible with
402    /// the current binding. (`NOT EXISTS` is `Not(Exists(..))`.)
403    Exists(Box<Plan>),
404}
405
406/// Memoizes each EXISTS sub-plan's solutions (plus a lazily-built semi-join
407/// index) within one filter application.
408type ExistsCache = std::collections::HashMap<*const Plan, ExistsEntry>;
409
410/// A cached EXISTS sub-plan: its solutions and a semi-join index built on first
411/// probe, so repeated probes are O(1) instead of O(sols) — turning FILTER (NOT)
412/// EXISTS over a BGP from O(L×R) into O(L+R), like the MINUS anti-join.
413struct ExistsEntry {
414    /// The sub-plan's solutions; filled on first need (`loaded`).
415    sols: std::sync::Arc<Vec<crate::row::Row>>,
416    loaded: bool,
417    probe: Option<std::sync::Arc<ExistsProbe>>,
418    /// Where the solutions and their index are kept for every shard of a
419    /// grouped query run on several threads ([`ExistsCell`]).
420    cell: Option<std::sync::Arc<ExistsCell>>,
421    /// A fat BGP sub-plan probed per outer row instead of loaded (`None` when
422    /// loading it whole is the cheaper plan).
423    corr: Option<crate::bgp::CorrelatedProbe>,
424}
425
426/// An EXISTS sub-plan's solutions and their index, made once for all the
427/// shards of a grouped query run on several threads: the first shard whose
428/// row needs them evaluates the sub-plan, the others wait for it and read the
429/// same rows.
430#[derive(Default)]
431pub(crate) struct ExistsCell {
432    sols: std::sync::OnceLock<std::sync::Arc<Vec<crate::row::Row>>>,
433    probe: std::sync::OnceLock<std::sync::Arc<ExistsProbe>>,
434}
435
436/// The semi-join index: solution rows keyed by the slots they share with the
437/// probing rows. A probe `b` satisfies EXISTS iff some solution is compatible
438/// with it (agrees on every shared slot).
439struct ExistsProbe {
440    /// All slots bound by some solution (ascending).
441    svars: Vec<usize>,
442    /// The shared slots with the probing rows (ascending) — the index key.
443    jvars: Vec<usize>,
444    /// `jvars`-value tuples of the solutions bound on all of `jvars`.
445    keys: std::collections::HashSet<Vec<crate::row::Val>>,
446    /// Solutions missing a `jvars` slot (e.g. via a nested OPTIONAL): scanned.
447    partial: Vec<crate::row::Row>,
448}
449
450/// Build the semi-join index for `sols`, keyed by the slots shared with the
451/// probe row `b`.
452fn build_exists_probe(b: &crate::row::Row, sols: &[crate::row::Row]) -> ExistsProbe {
453    let mask = crate::row::bound_mask(sols, b.len());
454    let svars: Vec<usize> = (0..b.len()).filter(|&i| mask[i]).collect();
455    let jvars: Vec<usize> = svars.iter().copied().filter(|&i| b[i].is_some()).collect();
456    let mut keys = std::collections::HashSet::new();
457    let mut partial = Vec::new();
458    for s in sols {
459        match jvars
460            .iter()
461            .map(|&i| s[i].clone())
462            .collect::<Option<Vec<crate::row::Val>>>()
463        {
464            Some(k) => {
465                keys.insert(k);
466            }
467            None => partial.push(s.clone()),
468        }
469    }
470    ExistsProbe {
471        svars,
472        jvars,
473        keys,
474        partial,
475    }
476}
477
478/// Does `b` satisfy the cached EXISTS? Uses the keyed index when `b`'s shared
479/// slots match the index's `jvars` (the common, homogeneous case); otherwise
480/// falls back to scanning all solutions (exact semantics on irregular rows).
481fn exists_matches(b: &crate::row::Row, entry: &ExistsEntry) -> bool {
482    let probe = entry.probe.as_ref().unwrap();
483    let bj: Vec<usize> = probe
484        .svars
485        .iter()
486        .copied()
487        .filter(|&i| b[i].is_some())
488        .collect();
489    if bj == probe.jvars {
490        let k: Vec<crate::row::Val> = probe.jvars.iter().map(|&i| b[i].clone().unwrap()).collect();
491        probe.keys.contains(&k)
492            || probe
493                .partial
494                .iter()
495                .any(|s| crate::row::compatible_rows(b, s))
496    } else {
497        entry.sols.iter().any(|s| crate::row::compatible_rows(b, s))
498    }
499}
500
501/// Lexical value of a term token: a literal's body with its N-Triples escapes
502/// resolved (the `@lang` / `^^<dt>` suffix dropped), else the IRI/blank-node
503/// token unchanged. The literal branch defers to [`crate::terms`] so that an
504/// escaped `\"` inside the body is part of the value — a naive scan to the
505/// first `"` cut `"He said \"hi\" loudly"` down to `He said \`, so CONTAINS /
506/// REGEX / STRSTARTS / STRENDS / LANGMATCHES / GROUP_CONCAT never saw the rest.
507fn lexical(token: &str) -> String {
508    crate::terms::literal_lexical(token).unwrap_or_else(|| token.to_string())
509}
510
511/// Numeric value of a term for SUM / AVG: a literal of a numeric datatype with
512/// a valid lexical form, else `None` — `"30"^^xsd:int` is 30, the string
513/// `"30"` is not a number (§18.5.1.3 folds `op:numeric-add`). The crate-visible
514/// name used by the row resolver's memoized parse.
515pub(crate) fn term_number(s: &str) -> Option<f64> {
516    value::numeric(s)
517}
518
519use crate::terms::as_number;
520
521/// The result of evaluating any SPARQL query form.
522#[derive(Debug, Clone)]
523#[must_use]
524#[non_exhaustive]
525pub enum QueryOutput {
526    /// SELECT: projected variables and their solution rows.
527    Select(Vec<String>, Vec<Binding>),
528    /// ASK: whether the pattern has any solution.
529    Ask(bool),
530    /// CONSTRUCT: the constructed triples as `(s, p, o)` term tokens.
531    Construct(Vec<(String, String, String)>),
532}
533
534/// Query shapes that can be answered exactly from [`crate::range::SummaryView`] predicate
535/// totals, without opening the triple index.
536#[derive(Debug, Clone, PartialEq, Eq)]
537#[must_use]
538#[non_exhaustive]
539pub enum SummaryQueryShape {
540    /// `SELECT (COUNT(*) AS ?n) WHERE { ?s <p> ?o }`
541    PredicateCount { predicate: String, variable: String },
542    /// `SELECT (COUNT(*) AS ?n) WHERE { ?s ?p ?o }`
543    TripleCount { variable: String },
544    /// `SELECT ?p (COUNT(*) AS ?n) WHERE { ?s ?p ?o } GROUP BY ?p`
545    PredicateTotals {
546        predicate_variable: String,
547        count_variable: String,
548    },
549    /// `SELECT DISTINCT ?p WHERE { ?s ?p ?o }`
550    PredicateList { variable: String },
551    /// `SELECT (COUNT(DISTINCT ?p) AS ?n) WHERE { ?s ?p ?o }`
552    PredicateDistinctCount { variable: String },
553    /// `ASK { ?s ?p ?o }`
554    TripleExists,
555    /// `ASK { ?s <p> ?o }`
556    PredicateExists { predicate: String },
557}
558
559/// A single triple pattern that can be answered by the range-routed permutation
560/// reader. `None` means the position is a variable/wildcard; `Some(term)` means
561/// the query pins that term.
562#[derive(Debug, Clone, PartialEq, Eq)]
563pub struct RoutedTriplePattern {
564    pub subject: Option<String>,
565    pub predicate: Option<String>,
566    pub object: Option<String>,
567}
568
569/// Classify queries whose graph access is exactly one default-graph triple
570/// pattern. Solution modifiers (projection, LIMIT, aggregate wrappers) do not
571/// change the underlying range access, but named graphs, FROM, joins, filters,
572/// paths, and other algebra need the full SPARQL evaluator.
573pub fn routed_triple_pattern(query: &str) -> Result<Option<RoutedTriplePattern>, SparqlError> {
574    let parsed = parse_query(query)?;
575    let sel = match parsed {
576        Query::Select {
577            pattern, dataset, ..
578        } => lower_select(&pattern, &dataset)?,
579        Query::Ask { pattern, .. } => lower_pattern(&pattern)?,
580        Query::Construct { pattern, .. } => lower_pattern(&pattern)?,
581        Query::Describe { pattern, .. } => lower_pattern(&pattern)?,
582    };
583    if !sel.from.is_empty() || sel.from_named.is_some() {
584        return Ok(None);
585    }
586    let Plan::Bgp(patterns) = sel.plan else {
587        return Ok(None);
588    };
589    let [tp] = patterns.as_slice() else {
590        return Ok(None);
591    };
592    Ok(Some(RoutedTriplePattern {
593        subject: term_const(&tp.s),
594        predicate: term_const(&tp.p),
595        object: term_const(&tp.o),
596    }))
597}
598
599fn term_const(term: &PatternTerm) -> Option<String> {
600    match term {
601        PatternTerm::Const(t) => Some(t.clone()),
602        PatternTerm::Var(_) => None,
603    }
604}
605
606/// Classify SPARQL queries that can be answered exactly from the pyramid
607/// summary's per-predicate totals. This is intentionally conservative: anything
608/// with constants, repeated variables, filters, joins, paths, named graphs,
609/// ORDER BY, OFFSET/LIMIT, or non-summary-safe aggregates still requires the
610/// index. The only accepted DISTINCT shape is a predicate list over one fully
611/// unbound triple pattern.
612pub fn summary_query_shape(query: &str) -> Result<Option<SummaryQueryShape>, SparqlError> {
613    let parsed = parse_query(query)?;
614    match parsed {
615        Query::Select {
616            pattern, dataset, ..
617        } => {
618            let sel = lower_select(&pattern, &dataset)?;
619            if !sel.from.is_empty()
620                || sel.from_named.is_some()
621                || sel.offset != 0
622                || sel.limit.is_some()
623                || !sel.order.is_empty()
624                || !sel.having.is_empty()
625            {
626                return Ok(None);
627            }
628            if sel.distinct {
629                if sel.group.is_some() || !sel.extends.is_empty() {
630                    return Ok(None);
631                }
632                let [projected] = sel.project.as_slice() else {
633                    return Ok(None);
634                };
635                let Some(SummaryPatternShape::AnyPredicate { variable }) =
636                    single_summary_pattern(&sel.plan)
637                else {
638                    return Ok(None);
639                };
640                return if projected == &variable {
641                    Ok(Some(SummaryQueryShape::PredicateList { variable }))
642                } else {
643                    Ok(None)
644                };
645            }
646            let Some(group) = &sel.group else {
647                return Ok(None);
648            };
649            if group.aggs.len() != 1 {
650                return Ok(None);
651            }
652            match group.by.as_slice() {
653                [] => match &group.aggs[0].1 {
654                    Agg::CountStar { distinct: false } => {
655                        let Some(variable) = public_aggregate_variable(&sel, &group.aggs[0].0)
656                        else {
657                            return Ok(None);
658                        };
659                        Ok(single_summary_pattern(&sel.plan).map(|shape| match shape {
660                            SummaryPatternShape::Predicate(predicate) => {
661                                SummaryQueryShape::PredicateCount {
662                                    predicate,
663                                    variable,
664                                }
665                            }
666                            SummaryPatternShape::AnyPredicate { .. } => {
667                                SummaryQueryShape::TripleCount { variable }
668                            }
669                        }))
670                    }
671                    Agg::Count(counted, true) => {
672                        let Some(public_variable) =
673                            public_aggregate_variable(&sel, &group.aggs[0].0)
674                        else {
675                            return Ok(None);
676                        };
677                        let Some(SummaryPatternShape::AnyPredicate { variable }) =
678                            single_summary_pattern(&sel.plan)
679                        else {
680                            return Ok(None);
681                        };
682                        if &variable != counted {
683                            return Ok(None);
684                        }
685                        Ok(Some(SummaryQueryShape::PredicateDistinctCount {
686                            variable: public_variable,
687                        }))
688                    }
689                    _ => Ok(None),
690                },
691                [group_var] => {
692                    if !matches!(group.aggs[0].1, Agg::CountStar { distinct: false }) {
693                        return Ok(None);
694                    }
695                    let Some(SummaryPatternShape::AnyPredicate { variable }) =
696                        single_summary_pattern(&sel.plan)
697                    else {
698                        return Ok(None);
699                    };
700                    if &variable != group_var {
701                        return Ok(None);
702                    }
703                    let Some(count_variable) =
704                        public_group_aggregate_variable(&sel, &group.aggs[0].0, group_var)
705                    else {
706                        return Ok(None);
707                    };
708                    Ok(Some(SummaryQueryShape::PredicateTotals {
709                        predicate_variable: group_var.clone(),
710                        count_variable,
711                    }))
712                }
713                _ => Ok(None),
714            }
715        }
716        Query::Ask { pattern, .. } => {
717            let sel = lower_pattern(&pattern)?;
718            Ok(single_summary_pattern(&sel.plan).map(|shape| match shape {
719                SummaryPatternShape::Predicate(predicate) => {
720                    SummaryQueryShape::PredicateExists { predicate }
721                }
722                SummaryPatternShape::AnyPredicate { .. } => SummaryQueryShape::TripleExists,
723            }))
724        }
725        Query::Construct { .. } | Query::Describe { .. } => Ok(None),
726    }
727}
728
729enum SummaryPatternShape {
730    Predicate(String),
731    AnyPredicate { variable: String },
732}
733
734fn single_summary_pattern(plan: &Plan) -> Option<SummaryPatternShape> {
735    let Plan::Bgp(patterns) = plan else {
736        return None;
737    };
738    let [tp] = patterns.as_slice() else {
739        return None;
740    };
741    let (PatternTerm::Var(s), PatternTerm::Var(o)) = (&tp.s, &tp.o) else {
742        return None;
743    };
744    if s == o {
745        return None;
746    }
747    match &tp.p {
748        PatternTerm::Const(p) => Some(SummaryPatternShape::Predicate(p.clone())),
749        PatternTerm::Var(p) if p != s && p != o => Some(SummaryPatternShape::AnyPredicate {
750            variable: p.clone(),
751        }),
752        _ => None,
753    }
754}
755
756fn public_aggregate_variable(sel: &Select, aggregate_var: &str) -> Option<String> {
757    let [projected] = sel.project.as_slice() else {
758        return None;
759    };
760    if projected == aggregate_var {
761        return Some(projected.clone());
762    }
763    sel.extends.iter().find_map(|(var, expr)| match expr {
764        FExpr::Var(source) if var == projected && source == aggregate_var => Some(var.clone()),
765        _ => None,
766    })
767}
768
769fn public_group_aggregate_variable(
770    sel: &Select,
771    aggregate_var: &str,
772    group_var: &str,
773) -> Option<String> {
774    let [projected_group, projected_aggregate] = sel.project.as_slice() else {
775        return None;
776    };
777    if projected_group != group_var {
778        return None;
779    }
780    if projected_aggregate == aggregate_var {
781        return Some(projected_aggregate.clone());
782    }
783    sel.extends.iter().find_map(|(var, expr)| match expr {
784        FExpr::Var(source) if var == projected_aggregate && source == aggregate_var => {
785            Some(var.clone())
786        }
787        _ => None,
788    })
789}
790
791/// One community's contribution to a community-split evaluation: how many
792/// member subjects it holds and how many solution rows it produced.
793#[derive(Debug, Clone, Copy)]
794pub struct CommunityPartial {
795    pub community: usize,
796    pub subjects: usize,
797    pub rows: usize,
798}
799
800/// The outcome of a community-split SELECT: the projected variables, the
801/// merged solution rows, and each community's contribution.
802pub type CommunitySelect = (Vec<String>, Vec<Binding>, Vec<CommunityPartial>);
803
804/// Evaluate a SELECT **per pyramid community**, then merge: each community's
805/// subjects are pushed into the plan as a VALUES binding, the partial rows
806/// are concatenated, and the solution modifiers (GROUP BY / ORDER BY / LIMIT
807/// / DISTINCT) run once on the union — so the rows are identical to
808/// [`eval_query`]'s answer. Sound only for subject-star queries over the
809/// default graph (every triple pattern sharing one subject variable; FILTERs
810/// allowed); anything else returns [`SparqlError::Unsupported`] rather than a
811/// possibly-wrong split answer. `round` picks the dendrogram granularity
812/// (`None` = the build's tile-budget round). Also returns each community's
813/// subject and row counts for display.
814pub fn eval_select_communities(
815    rete: &Rete,
816    query: &str,
817    round: Option<usize>,
818) -> Result<CommunitySelect, SparqlError> {
819    let parsed = parse_query(query)?;
820    let out = match parsed {
821        Query::Select {
822            pattern, dataset, ..
823        } => run_select_communities(rete, &lower_select(&pattern, &dataset)?, round),
824        _ => Err(SparqlError::Unsupported(
825            "community-split evaluation supports SELECT queries only",
826        )),
827    };
828    // See `eval_query`: a failed non-SILENT SERVICE call must become an error
829    // (and must not linger to poison a later query on the same handle).
830    match rete.take_service_error() {
831        Some(e) => Err(SparqlError::Service(e)),
832        None => out,
833    }
834}
835
836/// Evaluate any supported SPARQL query form (SELECT / ASK / CONSTRUCT).
837pub fn eval_query(rete: &Rete, query: &str) -> Result<QueryOutput, SparqlError> {
838    eval_query_with(rete, query, QueryOpts::default())
839}
840
841/// Like [`eval_query`], but with **OWL 2 QL entailment** on: the lowered plan is
842/// rewritten by the internal QL lowering pass so the answer includes ontology-entailed solutions
843/// (Stage 1a: `rdfs:subClassOf`), computed over the raw data with no
844/// materialization. Opt-in — a plain [`eval_query`] is byte-identical to before.
845pub fn eval_query_reasoned(rete: &Rete, query: &str) -> Result<QueryOutput, SparqlError> {
846    eval_query_with(
847        rete,
848        query,
849        QueryOpts {
850            reason: true,
851            ..QueryOpts::default()
852        },
853    )
854}
855
856/// Evaluation options for [`eval_query_with`]. Every flag defaults to off, and
857/// off reproduces [`eval_query`] byte-for-byte — the W3C conformance suite runs
858/// with this default.
859#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
860pub struct QueryOpts {
861    /// OWL 2 QL entailment by query rewriting — see [`eval_query_reasoned`].
862    pub reason: bool,
863    /// Union default graph (non-standard, opt-in): a pattern outside `GRAPH`
864    /// matches the RDF merge of the default graph and every named graph, the
865    /// mode Virtuoso / GraphDB / Jena TDB offer. A query with its own `FROM`
866    /// keeps its `FROM` dataset; `GRAPH ?g` still enumerates the named graphs
867    /// exactly as before. See [`Select::union_default`].
868    pub union_default_graph: bool,
869}
870
871/// [`eval_query`] with explicit [`QueryOpts`] — the single entry point the
872/// opt-in toggles (🧠 reasoning, union default graph) funnel through.
873pub fn eval_query_with(
874    rete: &Rete,
875    query: &str,
876    opts: QueryOpts,
877) -> Result<QueryOutput, SparqlError> {
878    // A fresh diagnostics scope: the expression type errors this query raises
879    // are counted on the side (see `diag`); `eval_query_with_warnings` reads
880    // them, plain callers just never look.
881    diag::begin();
882    let out = eval_query_inner(rete, query, opts);
883    // A failed non-SILENT SERVICE call is recorded out-of-band (the row
884    // pipeline is infallible, like lazy tile fetches) — surface it here so a
885    // partial answer is never returned as if it were complete.
886    match rete.take_service_error() {
887        Some(e) => Err(SparqlError::Service(e)),
888        None => out,
889    }
890}
891
892/// [`eval_query_with`], plus the diagnostics the evaluation produced.
893///
894/// SPARQL turns an expression **type error** into `false` inside FILTER (and
895/// into an unbound value in BIND / projection / ORDER BY): `CONTAINS(?iri, "x")`
896/// or `STRSTARTS(?year, "15")` on an `xsd:integer` silently drop every row. The
897/// result here is exactly what [`eval_query_with`] returns — nothing is coerced
898/// — but each class of such error comes back as a [`QueryWarning`]: the
899/// function, the argument position, what the argument was (IRI, number,
900/// language-incompatible literal, unbound, invalid regex, …), a count, one
901/// sample value and a hint (`wrap it in STR()`). When the result is empty and no
902/// error explains it, a case-sensitivity [`WarningSeverity::Hint`] may be added
903/// for a constant CONTAINS / STRSTARTS / STRENDS / REGEX (no `i` flag) needle.
904///
905/// Errors are recorded only where they happen, so a query that raises none
906/// pays nothing beyond a per-query reset; work per error is bounded (a count
907/// and one sample per `(function, position, kind)`).
908pub fn eval_query_with_warnings(
909    rete: &Rete,
910    query: &str,
911    opts: QueryOpts,
912) -> Result<(QueryOutput, Vec<QueryWarning>), SparqlError> {
913    let out = eval_query_with(rete, query, opts)?;
914    let warnings = diag::finish(&out);
915    Ok((out, warnings))
916}
917
918/// Plan running `query` as many smaller queries, split by the values of
919/// `var` (`?w`, `$w` or `w`), so a long extraction can go in short chunks
920/// that each finish quickly and can be retried or resumed one by one.
921///
922/// Refused — [`SparqlError::Partition`], saying why — when the chunks'
923/// answers together would not be the query's answer: an ASK or DESCRIBE, an
924/// ORDER BY, an aggregate not grouped by `var`, or a `var` some solution may
925/// leave unbound. Otherwise the plan carries the **keys query**, which lists
926/// the values to split (a superset: a value with no solution makes an empty
927/// chunk), and the top-level OFFSET/LIMIT the chunks drop and the caller
928/// applies once to the merged rows. Run each chunk with
929/// [`eval_query_partitioned`].
930///
931/// Reads only the tile directory (to pick the cheapest pattern for the keys
932/// query), never tile data.
933pub fn partition_plan(rete: &Rete, query: &str, var: &str) -> Result<PartitionPlan, SparqlError> {
934    partition::plan(rete, query, var)
935}
936
937/// [`eval_query_with_warnings`] for one chunk of a [`partition_plan`]: the
938/// query restricted to the solutions whose `var` is one of `keys` (term
939/// tokens as the keys query returned them, e.g. `<https://…>`), without its
940/// top-level OFFSET/LIMIT. The keys are joined in as `VALUES` on the first
941/// required pattern block that binds `var`, so each one is an index lookup.
942///
943/// The chunks' rows, taken in the keys' order, are the query's rows — except
944/// that the caller applies the plan's OFFSET/LIMIT and, when the plan says
945/// `dedupe`, drops repeated rows.
946pub fn eval_query_partitioned(
947    rete: &Rete,
948    query: &str,
949    opts: QueryOpts,
950    var: &str,
951    keys: &[String],
952) -> Result<(QueryOutput, Vec<QueryWarning>), SparqlError> {
953    diag::begin();
954    let out = eval_partition_inner(rete, query, opts, partition::var_name(var), keys);
955    let out = match rete.take_service_error() {
956        Some(e) => Err(SparqlError::Service(e)),
957        None => out,
958    }?;
959    let warnings = diag::finish(&out);
960    Ok((out, warnings))
961}
962
963fn eval_partition_inner(
964    rete: &Rete,
965    query: &str,
966    opts: QueryOpts,
967    var: &str,
968    keys: &[String],
969) -> Result<QueryOutput, SparqlError> {
970    let parsed = parse_query(query)?;
971    partition::check(&parsed, var)?;
972    // Seeded after reasoning, so the VALUES lands on the pattern block the
973    // engine will actually scan.
974    let chunk = |sel: Select| -> Select {
975        let mut sel = maybe_reason(rete, apply_opts(sel, opts), opts.reason);
976        sel.offset = 0;
977        sel.limit = None;
978        sel.plan = partition::seed(sel.plan, var, keys);
979        sel
980    };
981    match parsed {
982        Query::Select {
983            pattern, dataset, ..
984        } => {
985            let (vars, rows) = run_select(rete, &chunk(lower_select(&pattern, &dataset)?));
986            Ok(QueryOutput::Select(vars, rows))
987        }
988        Query::Construct {
989            template, pattern, ..
990        } => {
991            let sel = chunk(lower_pattern(&pattern)?);
992            let (ctx, sols) = raw_solutions(rete, &sel);
993            Ok(QueryOutput::Construct(instantiate(&ctx, &template, &sols)))
994        }
995        // `check` refused every other form.
996        _ => Err(SparqlError::Unsupported(
997            "only SELECT and CONSTRUCT can be split",
998        )),
999    }
1000}
1001
1002/// A SELECT answered to the **id level**: the variables and every solution row
1003/// as dictionary ids, with no term decoded for output. [`SelectRows::len`] is
1004/// the exact row count; [`SelectRows::page`] decodes one window of rows on
1005/// demand, as one batch of dictionary chunk reads. Built by
1006/// [`eval_select_rows`].
1007///
1008/// What the query itself needed has been decoded: the keys an `ORDER BY`
1009/// sorts on (none, when the file is `0x08` and the key is a plain variable
1010/// of an order-exact group: ids sort), the values a `FILTER` or an aggregate reads. Every other column
1011/// of every row stays an id until a page asks for it, so a result of 650,000
1012/// rows costs the terms of the page shown, not of the result. `DISTINCT` and
1013/// `GROUP BY` already work on ids.
1014///
1015/// The rows are only meaningful against the [`Rete`] that produced them.
1016#[derive(Debug, Clone)]
1017pub struct SelectRows {
1018    vars: Vec<String>,
1019    rows: Vec<Vec<Option<crate::row::Val>>>,
1020    warnings: Vec<QueryWarning>,
1021}
1022
1023impl SelectRows {
1024    pub(crate) fn new(vars: Vec<String>, rows: Vec<Vec<Option<crate::row::Val>>>) -> Self {
1025        SelectRows {
1026            vars,
1027            rows,
1028            warnings: Vec::new(),
1029        }
1030    }
1031
1032    /// The diagnostics the query raised, as [`eval_query_with_warnings`] reports
1033    /// them (the type errors a FILTER absorbed, a case-sensitivity hint for an
1034    /// empty result).
1035    pub fn warnings(&self) -> &[QueryWarning] {
1036        &self.warnings
1037    }
1038
1039    /// The projected variables (for `SELECT *`, every variable some row binds,
1040    /// in name order), the keys of every row [`page`](Self::page) returns.
1041    pub fn vars(&self) -> &[String] {
1042        &self.vars
1043    }
1044
1045    /// How many solution rows the query has.
1046    pub fn len(&self) -> usize {
1047        self.rows.len()
1048    }
1049
1050    /// Does the query have no solution?
1051    pub fn is_empty(&self) -> bool {
1052        self.rows.is_empty()
1053    }
1054
1055    /// Rows `offset..offset + limit` (fewer at the end, none past it) decoded
1056    /// to term tokens, an unbound variable left out of its row, exactly as
1057    /// [`eval_query`] returns them. The dictionary chunks the window needs are
1058    /// faulted in one batch first. `rete` must be the file the rows came from.
1059    pub fn page(&self, rete: &Rete, offset: usize, limit: usize) -> Vec<Binding> {
1060        let start = offset.min(self.rows.len());
1061        let end = start.saturating_add(limit).min(self.rows.len());
1062        let window = &self.rows[start..end];
1063        let resolver = crate::row::Resolver::new(rete.dictionary());
1064        resolver.prefetch(window.iter().flat_map(|r| r.iter().flatten()));
1065        window
1066            .iter()
1067            .map(|row| {
1068                let mut b = Binding::new();
1069                for (v, val) in self.vars.iter().zip(row) {
1070                    if let Some(t) = val.as_ref().and_then(|val| resolver.str_once(val)) {
1071                        b.insert(v.clone(), t);
1072                    }
1073                }
1074                b
1075            })
1076            .collect()
1077    }
1078}
1079
1080/// Run a SELECT to the id level ([`SelectRows`]): the same solutions as
1081/// [`eval_query_with`], but nothing is decoded for output until
1082/// [`SelectRows::page`] asks. A query that is not a SELECT is
1083/// [`SparqlError::Unsupported`].
1084pub fn eval_select_rows(
1085    rete: &Rete,
1086    query: &str,
1087    opts: QueryOpts,
1088) -> Result<SelectRows, SparqlError> {
1089    diag::begin();
1090    let parsed = parse_query(query)?;
1091    let out = match parsed {
1092        Query::Select {
1093            pattern, dataset, ..
1094        } => {
1095            let sel = maybe_reason(
1096                rete,
1097                apply_opts(lower_select(&pattern, &dataset)?, opts),
1098                opts.reason,
1099            );
1100            let mut rows = run_select_ids(rete, &sel);
1101            // The diagnostics only look at whether the result is empty.
1102            let probe = if rows.is_empty() {
1103                Vec::new()
1104            } else {
1105                vec![Binding::new()]
1106            };
1107            rows.warnings = diag::finish(&QueryOutput::Select(rows.vars.clone(), probe));
1108            Ok(rows)
1109        }
1110        _ => Err(SparqlError::Unsupported(
1111            "a result handle is for SELECT queries",
1112        )),
1113    };
1114    // A failed non-SILENT SERVICE call must become an error, as in `eval_query`.
1115    match rete.take_service_error() {
1116        Some(e) => Err(SparqlError::Service(e)),
1117        None => out,
1118    }
1119}
1120
1121/// Apply OWL 2 QL plan rewriting when reasoning is on (no-op otherwise). Reads a
1122/// small TBox slice from `rete` to gate the rewrite (see [`ql`]).
1123fn maybe_reason(rete: &Rete, mut sel: Select, reason: bool) -> Select {
1124    if reason {
1125        let projected = sel.project.clone();
1126        sel.plan = ql::reason_rewrite(sel.plan, rete, &projected);
1127    }
1128    sel
1129}
1130
1131/// Stamp the caller's union-default-graph choice onto the lowered top-level
1132/// `Select` (dataset clauses are top-level-only in the SPARQL grammar, so this
1133/// never needs to descend into subqueries — they evaluate against the same
1134/// active index).
1135fn apply_opts(mut sel: Select, opts: QueryOpts) -> Select {
1136    sel.union_default = opts.union_default_graph;
1137    sel
1138}
1139
1140fn eval_query_inner(rete: &Rete, query: &str, opts: QueryOpts) -> Result<QueryOutput, SparqlError> {
1141    let reason = opts.reason;
1142    let parsed = parse_query(query)?;
1143    match parsed {
1144        Query::Select {
1145            pattern, dataset, ..
1146        } => {
1147            let (vars, rows) = run_select(
1148                rete,
1149                &maybe_reason(
1150                    rete,
1151                    apply_opts(lower_select(&pattern, &dataset)?, opts),
1152                    reason,
1153                ),
1154            );
1155            Ok(QueryOutput::Select(vars, rows))
1156        }
1157        Query::Ask { pattern, .. } => {
1158            let sel = maybe_reason(rete, apply_opts(lower_pattern(&pattern)?, opts), reason);
1159            Ok(QueryOutput::Ask(ask_solution(rete, &sel)))
1160        }
1161        Query::Construct {
1162            template, pattern, ..
1163        } => {
1164            let sel = maybe_reason(rete, apply_opts(lower_pattern(&pattern)?, opts), reason);
1165            let (ctx, sols) = raw_solutions(rete, &sel);
1166            Ok(QueryOutput::Construct(instantiate(&ctx, &template, &sols)))
1167        }
1168        Query::Describe {
1169            pattern, dataset, ..
1170        } => {
1171            // The projected variables' values are the resources to describe;
1172            // we return each one's outgoing triples (concise bounded description).
1173            let sel = maybe_reason(
1174                rete,
1175                apply_opts(lower_select(&pattern, &dataset)?, opts),
1176                reason,
1177            );
1178            let (ctx, rows) = raw_solutions(rete, &sel);
1179            let mut resources = std::collections::BTreeSet::new();
1180            for row in &rows {
1181                if sel.project.is_empty() {
1182                    for val in row.iter().flatten() {
1183                        if let Some(t) = ctx.resolver.str_of(val) {
1184                            resources.insert(t.to_string());
1185                        }
1186                    }
1187                } else {
1188                    for v in &sel.project {
1189                        if let Some(val) = ctx.slots.slot(v).and_then(|s| row[s].as_ref()) {
1190                            if let Some(t) = ctx.resolver.str_of(val) {
1191                                resources.insert(t.to_string());
1192                            }
1193                        }
1194                    }
1195                }
1196            }
1197            // Described from the query's active default graph, the same graph
1198            // its WHERE clause matched: the file's default graph, the `FROM`
1199            // graphs, or (union-default toggle, no FROM) the default graph plus
1200            // every named graph.
1201            // A quad index streams the union: no walk over its graphs.
1202            let streamed = if sel.union_default && sel.from.is_empty() {
1203                rete.union_default_index()
1204            } else {
1205                None
1206            };
1207            let mut graphs: Vec<Option<&str>> = Vec::new();
1208            if streamed.is_some() {
1209            } else if !sel.from.is_empty() {
1210                graphs.extend(sel.from.iter().map(|g| Some(g.as_str())));
1211            } else {
1212                graphs.push(None);
1213                if sel.union_default {
1214                    graphs.extend(rete.graph_names().into_iter().map(Some));
1215                }
1216            }
1217            let mut triples = std::collections::BTreeSet::new();
1218            for r in &resources {
1219                if let Some(union) = &streamed {
1220                    triples.extend(rete.query_in_index(union, Some(r), None, None));
1221                    continue;
1222                }
1223                for g in &graphs {
1224                    for t in rete.query_in_graph(*g, Some(r), None, None) {
1225                        triples.insert(t);
1226                    }
1227                }
1228            }
1229            Ok(QueryOutput::Construct(triples.into_iter().collect()))
1230        }
1231    }
1232}
1233
1234/// Parse and evaluate a SELECT against a file, applying the plan then
1235/// projection, DISTINCT, OFFSET, and LIMIT. Returns `(projected_vars,
1236/// solutions)`.
1237pub fn eval_sparql(rete: &Rete, query: &str) -> Result<(Vec<String>, Vec<Binding>), SparqlError> {
1238    eval_sparql_opts(rete, query, false)
1239}
1240
1241/// Like [`eval_sparql`], but with OWL 2 QL entailment on (see [`eval_query_reasoned`]).
1242pub fn eval_sparql_reasoned(
1243    rete: &Rete,
1244    query: &str,
1245) -> Result<(Vec<String>, Vec<Binding>), SparqlError> {
1246    eval_sparql_opts(rete, query, true)
1247}
1248
1249fn eval_sparql_opts(
1250    rete: &Rete,
1251    query: &str,
1252    reason: bool,
1253) -> Result<(Vec<String>, Vec<Binding>), SparqlError> {
1254    let sel = maybe_reason(rete, parse_select(query)?, reason);
1255    let out = run_select(rete, &sel);
1256    // See `eval_query`: a failed non-SILENT SERVICE call must become an error.
1257    match rete.take_service_error() {
1258        Some(e) => Err(SparqlError::Service(e)),
1259        None => Ok(out),
1260    }
1261}
1262
1263/// Format a computed number as an N-Triples *typed* literal so the result
1264/// serializer emits its datatype (SPARQL requires arithmetic/aggregates/numeric
1265/// functions to yield typed numerics, not bare strings). Whole values are
1266/// `xsd:integer`; fractional ones `xsd:decimal` — the common cases in the data
1267/// (`xsd:double` would need operand-type tracking we don't carry through `f64`).
1268pub(crate) fn fmt_num_typed(x: f64) -> String {
1269    if x.fract() == 0.0 {
1270        format!(
1271            "\"{}\"^^<http://www.w3.org/2001/XMLSchema#integer>",
1272            x as i64
1273        )
1274    } else {
1275        // Round to 15 significant digits before emitting the shortest form, so a
1276        // sum/avg of decimals that lands on a binary-float artifact (e.g.
1277        // 11.100000000000001) serializes as the intended "11.1".
1278        let cleaned: f64 = format!("{x:.14e}").parse().unwrap_or(x);
1279        format!("\"{cleaned}\"^^<http://www.w3.org/2001/XMLSchema#decimal>")
1280    }
1281}
1282
1283/// Push a reverse through a path (reverses each predicate and swaps sequences).
1284fn reverse(ast: PathAst) -> PathAst {
1285    match ast {
1286        PathAst::Pred(p, r) => PathAst::Pred(p, !r),
1287        PathAst::Rep(inner, rep) => PathAst::Rep(Box::new(reverse(*inner)), rep),
1288        PathAst::Seq(a, b) => PathAst::Seq(Box::new(reverse(*b)), Box::new(reverse(*a))),
1289        PathAst::Alt(a, b) => PathAst::Alt(Box::new(reverse(*a)), Box::new(reverse(*b))),
1290        PathAst::NegatedSet(s, r) => PathAst::NegatedSet(s, !r),
1291    }
1292}
1293
1294#[cfg(test)]
1295mod tests {
1296    use super::*;
1297    use crate::dictionary::DictionaryBuilder;
1298    use crate::index::GraphIndexBuilder;
1299    use crate::write_file_v05 as write_file;
1300
1301    fn rete_from(triples: &[(&str, &str, &str)]) -> Vec<u8> {
1302        let mut db = DictionaryBuilder::new();
1303        for (s, p, o) in triples {
1304            db.observe(s, p, o);
1305        }
1306        let dict = db.build();
1307        let mut ib = GraphIndexBuilder::new();
1308        for (s, p, o) in triples {
1309            ib.push(dict.encode(s, p, o).unwrap());
1310        }
1311        write_file(&dict, &ib.build(), false, &[], 0)
1312    }
1313
1314    #[test]
1315    fn parses_select_with_two_patterns() {
1316        let q = r#"
1317            PREFIX ex: <http://ex/>
1318            SELECT ?x ?z WHERE { ?x ex:knows ?y . ?y ex:knows ?z }
1319        "#;
1320        let sel = parse_select(q).unwrap();
1321        assert_eq!(sel.project, vec!["x", "z"]);
1322        match &sel.plan {
1323            Plan::Bgp(p) => assert_eq!(p.len(), 2),
1324            other => panic!("expected a BGP plan, got {other:?}"),
1325        }
1326    }
1327
1328    #[test]
1329    fn evaluates_two_hop_select() {
1330        let bytes = rete_from(&[
1331            ("<http://ex/Alice>", "<http://ex/knows>", "<http://ex/Bob>"),
1332            ("<http://ex/Bob>", "<http://ex/knows>", "<http://ex/Carol>"),
1333        ]);
1334        let rete = Rete::open(&bytes).unwrap();
1335        let q = r#"PREFIX ex: <http://ex/>
1336                   SELECT ?x ?z WHERE { ?x ex:knows ?y . ?y ex:knows ?z }"#;
1337        let (proj, sols) = eval_sparql(&rete, q).unwrap();
1338        assert_eq!(proj, vec!["x", "z"]);
1339        assert_eq!(sols.len(), 1);
1340        assert_eq!(sols[0]["x"], "<http://ex/Alice>");
1341        assert_eq!(sols[0]["z"], "<http://ex/Carol>");
1342    }
1343
1344    #[test]
1345    fn union_returns_both_sides() {
1346        let bytes = rete_from(&[
1347            ("<http://ex/Alice>", "<http://ex/likes>", "<http://ex/Tea>"),
1348            ("<http://ex/Bob>", "<http://ex/hates>", "<http://ex/Tea>"),
1349        ]);
1350        let rete = Rete::open(&bytes).unwrap();
1351        let q = "PREFIX ex: <http://ex/> SELECT ?p WHERE { \
1352                 { ?p ex:likes ex:Tea } UNION { ?p ex:hates ex:Tea } }";
1353        let (_, sols) = eval_sparql(&rete, q).unwrap();
1354        let mut who: Vec<&str> = sols.iter().map(|b| b["p"].as_str()).collect();
1355        who.sort();
1356        assert_eq!(who, vec!["<http://ex/Alice>", "<http://ex/Bob>"]);
1357    }
1358
1359    #[test]
1360    fn optional_keeps_left_when_right_absent() {
1361        // Alice has an email, Bob doesn't. OPTIONAL email keeps both people.
1362        let bytes = rete_from(&[
1363            ("<http://ex/Alice>", "<http://ex/name>", "\"Alice\""),
1364            ("<http://ex/Bob>", "<http://ex/name>", "\"Bob\""),
1365            ("<http://ex/Alice>", "<http://ex/email>", "\"a@ex\""),
1366        ]);
1367        let rete = Rete::open(&bytes).unwrap();
1368        let q = "PREFIX ex: <http://ex/> SELECT ?p ?e WHERE { \
1369                 ?p ex:name ?n . OPTIONAL { ?p ex:email ?e } }";
1370        let (_, sols) = eval_sparql(&rete, q).unwrap();
1371        assert_eq!(sols.len(), 2, "both people present");
1372        let alice = sols.iter().find(|b| b["p"] == "<http://ex/Alice>").unwrap();
1373        assert_eq!(alice["e"], "\"a@ex\"");
1374        let bob = sols.iter().find(|b| b["p"] == "<http://ex/Bob>").unwrap();
1375        assert!(!bob.contains_key("e"), "Bob has no email binding");
1376    }
1377
1378    #[test]
1379    fn numeric_filter_on_typed_literal() {
1380        // ages 30 and 25; FILTER(?age > 27) keeps only Alice.
1381        let xsd = "<http://www.w3.org/2001/XMLSchema#integer>";
1382        let bytes = rete_from(&[
1383            (
1384                "<http://ex/Alice>",
1385                "<http://ex/age>",
1386                &format!("\"30\"^^{xsd}"),
1387            ),
1388            (
1389                "<http://ex/Bob>",
1390                "<http://ex/age>",
1391                &format!("\"25\"^^{xsd}"),
1392            ),
1393        ]);
1394        let rete = Rete::open(&bytes).unwrap();
1395        let q = "PREFIX ex: <http://ex/> \
1396                 SELECT ?p WHERE { ?p ex:age ?age . FILTER(?age > 27) }";
1397        let (_, sols) = eval_sparql(&rete, q).unwrap();
1398        assert_eq!(sols.len(), 1);
1399        assert_eq!(sols[0]["p"], "<http://ex/Alice>");
1400    }
1401
1402    #[test]
1403    fn filter_equality_and_boolean_logic() {
1404        let bytes = rete_from(&[
1405            ("<http://ex/Alice>", "<http://ex/city>", "<http://ex/NYC>"),
1406            ("<http://ex/Bob>", "<http://ex/city>", "<http://ex/LA>"),
1407            ("<http://ex/Carol>", "<http://ex/city>", "<http://ex/NYC>"),
1408        ]);
1409        let rete = Rete::open(&bytes).unwrap();
1410        let q = "PREFIX ex: <http://ex/> \
1411                 SELECT ?p WHERE { ?p ex:city ?c . FILTER(?c = ex:NYC && ?p != ex:Carol) }";
1412        let (_, sols) = eval_sparql(&rete, q).unwrap();
1413        assert_eq!(sols.len(), 1);
1414        assert_eq!(sols[0]["p"], "<http://ex/Alice>");
1415    }
1416
1417    #[test]
1418    fn distinct_collapses_duplicate_projections() {
1419        // Dave is reachable in two hops via both Bob and Carol.
1420        let bytes = rete_from(&[
1421            ("<http://ex/Alice>", "<http://ex/knows>", "<http://ex/Bob>"),
1422            (
1423                "<http://ex/Alice>",
1424                "<http://ex/knows>",
1425                "<http://ex/Carol>",
1426            ),
1427            ("<http://ex/Bob>", "<http://ex/knows>", "<http://ex/Dave>"),
1428            ("<http://ex/Carol>", "<http://ex/knows>", "<http://ex/Dave>"),
1429        ]);
1430        let rete = Rete::open(&bytes).unwrap();
1431        let base = "PREFIX ex: <http://ex/> SELECT {} ?z WHERE { ?x ex:knows ?y . ?y ex:knows ?z }";
1432
1433        let (_, non_distinct) = eval_sparql(&rete, &base.replace("{}", "")).unwrap();
1434        assert_eq!(non_distinct.len(), 2); // {z:Dave} twice
1435
1436        let (proj, distinct) = eval_sparql(&rete, &base.replace("{}", "DISTINCT")).unwrap();
1437        assert_eq!(proj, vec!["z"]);
1438        assert_eq!(distinct.len(), 1);
1439        assert_eq!(distinct[0]["z"], "<http://ex/Dave>");
1440        // Projection dropped ?x and ?y.
1441        assert!(!distinct[0].contains_key("x"));
1442    }
1443
1444    #[test]
1445    fn transitive_path_reachability() {
1446        // A -> B -> C -> D chain.
1447        let bytes = rete_from(&[
1448            ("<http://ex/A>", "<http://ex/k>", "<http://ex/B>"),
1449            ("<http://ex/B>", "<http://ex/k>", "<http://ex/C>"),
1450            ("<http://ex/C>", "<http://ex/k>", "<http://ex/D>"),
1451        ]);
1452        let rete = Rete::open(&bytes).unwrap();
1453
1454        // A k+ ?y  → B, C, D (one or more hops).
1455        let q = "PREFIX ex: <http://ex/> SELECT ?y WHERE { ex:A ex:k+ ?y }";
1456        let (_, sols) = eval_sparql(&rete, q).unwrap();
1457        let mut ys: Vec<&str> = sols.iter().map(|b| b["y"].as_str()).collect();
1458        ys.sort();
1459        assert_eq!(ys, vec!["<http://ex/B>", "<http://ex/C>", "<http://ex/D>"]);
1460
1461        // A k* ?y includes A itself (zero-length).
1462        let q0 = "PREFIX ex: <http://ex/> SELECT ?y WHERE { ex:A ex:k* ?y }";
1463        let (_, s0) = eval_sparql(&rete, q0).unwrap();
1464        assert!(s0.iter().any(|b| b["y"] == "<http://ex/A>"));
1465        assert_eq!(s0.len(), 4); // A, B, C, D
1466    }
1467
1468    #[test]
1469    fn sequence_and_alternative_paths() {
1470        // Alice -parent-> Bob -parent-> Carol; Alice -stepparent-> Dave.
1471        let bytes = rete_from(&[
1472            ("<http://ex/Alice>", "<http://ex/parent>", "<http://ex/Bob>"),
1473            ("<http://ex/Bob>", "<http://ex/parent>", "<http://ex/Carol>"),
1474            (
1475                "<http://ex/Alice>",
1476                "<http://ex/stepparent>",
1477                "<http://ex/Dave>",
1478            ),
1479        ]);
1480        let rete = Rete::open(&bytes).unwrap();
1481
1482        // grandparent = parent/parent : Alice -> Carol.
1483        let q = "PREFIX ex: <http://ex/> SELECT ?g WHERE { ex:Alice ex:parent/ex:parent ?g }";
1484        let (_, sols) = eval_sparql(&rete, q).unwrap();
1485        assert_eq!(sols.len(), 1);
1486        assert_eq!(sols[0]["g"], "<http://ex/Carol>");
1487
1488        // any-parent = parent|stepparent : Alice -> {Bob, Dave}.
1489        let qa = "PREFIX ex: <http://ex/> \
1490                  SELECT ?p WHERE { ex:Alice ex:parent|ex:stepparent ?p }";
1491        let (_, sa) = eval_sparql(&rete, qa).unwrap();
1492        let mut ps: Vec<&str> = sa.iter().map(|b| b["p"].as_str()).collect();
1493        ps.sort();
1494        assert_eq!(ps, vec!["<http://ex/Bob>", "<http://ex/Dave>"]);
1495    }
1496
1497    #[test]
1498    fn group_concat_aggregate() {
1499        let bytes = rete_from(&[
1500            ("<http://ex/Alice>", "<http://ex/knows>", "<http://ex/Bob>"),
1501            (
1502                "<http://ex/Alice>",
1503                "<http://ex/knows>",
1504                "<http://ex/Carol>",
1505            ),
1506        ]);
1507        let rete = Rete::open(&bytes).unwrap();
1508        let q = "PREFIX ex: <http://ex/> \
1509                 SELECT (GROUP_CONCAT(STR(?f); SEPARATOR=\"|\") AS ?fs) WHERE { ex:Alice ex:knows ?f }";
1510        let (_, sols) = eval_sparql(&rete, q).unwrap();
1511        assert_eq!(sols.len(), 1);
1512        // GROUP_CONCAT yields a simple literal — strip the quotes before splitting.
1513        let fs = sols[0]["fs"].trim_matches('"');
1514        let mut parts: Vec<&str> = fs.split('|').collect();
1515        parts.sort();
1516        assert_eq!(parts, vec!["http://ex/Bob", "http://ex/Carol"]);
1517        // The bare IRI is an element CONCAT rejects: unbound, not `<http://ex/Bob>`.
1518        let q = "PREFIX ex: <http://ex/> \n                 SELECT (GROUP_CONCAT(?f) AS ?fs) WHERE { ex:Alice ex:knows ?f }";
1519        let (_, sols) = eval_sparql(&rete, q).unwrap();
1520        assert_eq!(sols.len(), 1);
1521        assert_eq!(sols[0].get("fs"), None);
1522    }
1523
1524    #[test]
1525    fn group_by_having() {
1526        // Alice knows 2, Bob knows 1.
1527        let bytes = rete_from(&[
1528            ("<http://ex/Alice>", "<http://ex/knows>", "<http://ex/Bob>"),
1529            (
1530                "<http://ex/Alice>",
1531                "<http://ex/knows>",
1532                "<http://ex/Carol>",
1533            ),
1534            ("<http://ex/Bob>", "<http://ex/knows>", "<http://ex/Carol>"),
1535        ]);
1536        let rete = Rete::open(&bytes).unwrap();
1537        // Only people who know more than one person → Alice.
1538        let q = "PREFIX ex: <http://ex/> SELECT ?p (COUNT(?f) AS ?n) \
1539                 WHERE { ?p ex:knows ?f } GROUP BY ?p HAVING (COUNT(?f) > 1)";
1540        let (_, sols) = eval_sparql(&rete, q).unwrap();
1541        assert_eq!(sols.len(), 1);
1542        assert_eq!(sols[0]["p"], "<http://ex/Alice>");
1543        assert_eq!(
1544            sols[0]["n"],
1545            "\"2\"^^<http://www.w3.org/2001/XMLSchema#integer>"
1546        );
1547    }
1548
1549    #[test]
1550    fn count_group_by() {
1551        // Alice knows Bob & Carol (2); Bob knows Carol (1).
1552        let bytes = rete_from(&[
1553            ("<http://ex/Alice>", "<http://ex/knows>", "<http://ex/Bob>"),
1554            (
1555                "<http://ex/Alice>",
1556                "<http://ex/knows>",
1557                "<http://ex/Carol>",
1558            ),
1559            ("<http://ex/Bob>", "<http://ex/knows>", "<http://ex/Carol>"),
1560        ]);
1561        let rete = Rete::open(&bytes).unwrap();
1562        let q = "PREFIX ex: <http://ex/> \
1563                 SELECT ?p (COUNT(?f) AS ?n) WHERE { ?p ex:knows ?f } GROUP BY ?p";
1564        let (_, sols) = eval_sparql(&rete, q).unwrap();
1565        let mut counts: Vec<(String, String)> = sols
1566            .iter()
1567            .map(|b| (b["p"].clone(), b["n"].clone()))
1568            .collect();
1569        counts.sort();
1570        assert_eq!(
1571            counts,
1572            vec![
1573                (
1574                    "<http://ex/Alice>".into(),
1575                    "\"2\"^^<http://www.w3.org/2001/XMLSchema#integer>".into()
1576                ),
1577                (
1578                    "<http://ex/Bob>".into(),
1579                    "\"1\"^^<http://www.w3.org/2001/XMLSchema#integer>".into()
1580                ),
1581            ]
1582        );
1583    }
1584
1585    #[test]
1586    fn global_count_star() {
1587        let bytes = rete_from(&[
1588            ("<http://ex/a>", "<http://ex/p>", "<http://ex/1>"),
1589            ("<http://ex/b>", "<http://ex/p>", "<http://ex/2>"),
1590        ]);
1591        let rete = Rete::open(&bytes).unwrap();
1592        let (_, sols) = eval_sparql(&rete, "SELECT (COUNT(*) AS ?n) WHERE { ?s ?p ?o }").unwrap();
1593        assert_eq!(sols.len(), 1);
1594        assert_eq!(
1595            sols[0]["n"],
1596            "\"2\"^^<http://www.w3.org/2001/XMLSchema#integer>"
1597        );
1598    }
1599
1600    #[test]
1601    fn summary_query_shape_classifies_only_exact_predicate_totals() {
1602        let count = summary_query_shape(
1603            "PREFIX ex: <http://ex/> SELECT (COUNT(*) AS ?n) WHERE { ?s ex:p ?o }",
1604        )
1605        .unwrap();
1606        assert_eq!(
1607            count,
1608            Some(SummaryQueryShape::PredicateCount {
1609                predicate: "<http://ex/p>".into(),
1610                variable: "n".into(),
1611            })
1612        );
1613
1614        let total = summary_query_shape("SELECT (COUNT(*) AS ?n) WHERE { ?s ?p ?o }").unwrap();
1615        assert_eq!(
1616            total,
1617            Some(SummaryQueryShape::TripleCount {
1618                variable: "n".into(),
1619            })
1620        );
1621
1622        let by_pred =
1623            summary_query_shape("SELECT ?p (COUNT(*) AS ?n) WHERE { ?s ?p ?o } GROUP BY ?p")
1624                .unwrap();
1625        assert_eq!(
1626            by_pred,
1627            Some(SummaryQueryShape::PredicateTotals {
1628                predicate_variable: "p".into(),
1629                count_variable: "n".into(),
1630            })
1631        );
1632
1633        let predicates = summary_query_shape("SELECT DISTINCT ?p WHERE { ?s ?p ?o }").unwrap();
1634        assert_eq!(
1635            predicates,
1636            Some(SummaryQueryShape::PredicateList {
1637                variable: "p".into(),
1638            })
1639        );
1640
1641        let predicate_count =
1642            summary_query_shape("SELECT (COUNT(DISTINCT ?p) AS ?n) WHERE { ?s ?p ?o }").unwrap();
1643        assert_eq!(
1644            predicate_count,
1645            Some(SummaryQueryShape::PredicateDistinctCount {
1646                variable: "n".into(),
1647            })
1648        );
1649
1650        let ask = summary_query_shape("PREFIX ex: <http://ex/> ASK { ?s ex:p ?o }").unwrap();
1651        assert_eq!(
1652            ask,
1653            Some(SummaryQueryShape::PredicateExists {
1654                predicate: "<http://ex/p>".into(),
1655            })
1656        );
1657
1658        let any_ask = summary_query_shape("ASK { ?s ?p ?o }").unwrap();
1659        assert_eq!(any_ask, Some(SummaryQueryShape::TripleExists));
1660
1661        let constrained =
1662            summary_query_shape("PREFIX ex: <http://ex/> ASK { ex:a ex:p ?o }").unwrap();
1663        assert_eq!(constrained, None);
1664
1665        let filtered =
1666            summary_query_shape("PREFIX ex: <http://ex/> ASK { ?s ex:p ?o FILTER(?s = ?o) }")
1667                .unwrap();
1668        assert_eq!(filtered, None);
1669    }
1670
1671    #[test]
1672    fn filter_exists_and_not_exists() {
1673        // Alice knows Bob & Carol; Bob knows Dave; Carol knows nobody.
1674        let bytes = rete_from(&[
1675            ("<http://ex/Alice>", "<http://ex/knows>", "<http://ex/Bob>"),
1676            (
1677                "<http://ex/Alice>",
1678                "<http://ex/knows>",
1679                "<http://ex/Carol>",
1680            ),
1681            ("<http://ex/Bob>", "<http://ex/knows>", "<http://ex/Dave>"),
1682        ]);
1683        let rete = Rete::open(&bytes).unwrap();
1684
1685        // Friends of Alice who themselves know someone → Bob.
1686        let q_exists = "PREFIX ex: <http://ex/> SELECT ?f WHERE { \
1687            ex:Alice ex:knows ?f . FILTER EXISTS { ?f ex:knows ?x } }";
1688        let (_, e) = eval_sparql(&rete, q_exists).unwrap();
1689        assert_eq!(
1690            e.iter().map(|b| b["f"].as_str()).collect::<Vec<_>>(),
1691            vec!["<http://ex/Bob>"]
1692        );
1693
1694        // Friends of Alice who know nobody → Carol.
1695        let q_not = "PREFIX ex: <http://ex/> SELECT ?f WHERE { \
1696            ex:Alice ex:knows ?f . FILTER NOT EXISTS { ?f ex:knows ?x } }";
1697        let (_, n) = eval_sparql(&rete, q_not).unwrap();
1698        assert_eq!(
1699            n.iter().map(|b| b["f"].as_str()).collect::<Vec<_>>(),
1700            vec!["<http://ex/Carol>"]
1701        );
1702    }
1703
1704    #[test]
1705    fn ask_repeated_variable_pattern() {
1706        // ASK's fast path must NOT take the single-pattern scan shortcut when a
1707        // variable repeats across positions (`?x knows ?x`) — only Bob self-knows.
1708        let yes = rete_from(&[
1709            ("<http://ex/Alice>", "<http://ex/knows>", "<http://ex/Bob>"),
1710            ("<http://ex/Bob>", "<http://ex/knows>", "<http://ex/Bob>"),
1711        ]);
1712        let rete = Rete::open(&yes).unwrap();
1713        match eval_query(&rete, "PREFIX ex: <http://ex/> ASK { ?x ex:knows ?x }").unwrap() {
1714            QueryOutput::Ask(b) => assert!(b, "Bob knows himself"),
1715            other => panic!("expected Ask, got {other:?}"),
1716        }
1717        // With no self-edge, the index still has a `knows` triple, so a naive
1718        // first-match probe would wrongly say true; the guard must reject it.
1719        let no = rete_from(&[("<http://ex/Alice>", "<http://ex/knows>", "<http://ex/Bob>")]);
1720        let rete = Rete::open(&no).unwrap();
1721        match eval_query(&rete, "PREFIX ex: <http://ex/> ASK { ?x ex:knows ?x }").unwrap() {
1722            QueryOutput::Ask(b) => assert!(!b, "nobody knows themselves"),
1723            other => panic!("expected Ask, got {other:?}"),
1724        }
1725    }
1726
1727    #[test]
1728    fn minus_excludes_compatible() {
1729        // Alice knows Bob and Carol; Bob knows Carol; Carol knows no one.
1730        let bytes = rete_from(&[
1731            ("<http://ex/Alice>", "<http://ex/knows>", "<http://ex/Bob>"),
1732            (
1733                "<http://ex/Alice>",
1734                "<http://ex/knows>",
1735                "<http://ex/Carol>",
1736            ),
1737            ("<http://ex/Bob>", "<http://ex/knows>", "<http://ex/Carol>"),
1738        ]);
1739        let rete = Rete::open(&bytes).unwrap();
1740        // People Alice knows who themselves know nobody → Carol.
1741        let q = "PREFIX ex: <http://ex/> SELECT ?f WHERE { \
1742                 ex:Alice ex:knows ?f . MINUS { ?f ex:knows ?x } }";
1743        let (_, sols) = eval_sparql(&rete, q).unwrap();
1744        let fs: Vec<&str> = sols.iter().map(|b| b["f"].as_str()).collect();
1745        assert_eq!(fs, vec!["<http://ex/Carol>"]);
1746    }
1747
1748    #[test]
1749    fn filter_exists_disjoint_variable() {
1750        // EXISTS over a sub-pattern that shares NO variable with the outer row is
1751        // true iff the sub-pattern has any solution — so NOT EXISTS removes ALL
1752        // rows (the exact case where NOT EXISTS differs from MINUS). Guards the
1753        // semi-join index's empty-`jvars` path.
1754        let bytes = rete_from(&[
1755            ("<http://ex/Alice>", "<http://ex/a>", "<http://ex/Person>"),
1756            ("<http://ex/Bob>", "<http://ex/a>", "<http://ex/Person>"),
1757            ("<http://ex/Tea>", "<http://ex/a>", "<http://ex/Drink>"),
1758        ]);
1759        let rete = Rete::open(&bytes).unwrap();
1760        let q_none = "PREFIX ex: <http://ex/> SELECT ?x WHERE { \
1761            ?x ex:a ex:Person FILTER NOT EXISTS { ?y ex:a ex:Drink } }";
1762        assert!(eval_sparql(&rete, q_none).unwrap().1.is_empty());
1763        let q_all = "PREFIX ex: <http://ex/> SELECT ?x WHERE { \
1764            ?x ex:a ex:Person FILTER EXISTS { ?y ex:a ex:Drink } }";
1765        assert_eq!(eval_sparql(&rete, q_all).unwrap().1.len(), 2);
1766    }
1767
1768    #[test]
1769    fn minus_disjoint_domain_keeps_all() {
1770        // MINUS with no shared variable must remove nothing (SPARQL semantics) —
1771        // the hash anti-join's `jv.is_empty()` guard. Alice/Bob both kept even
1772        // though the right pattern has solutions.
1773        let bytes = rete_from(&[
1774            ("<http://ex/Alice>", "<http://ex/a>", "<http://ex/Person>"),
1775            ("<http://ex/Bob>", "<http://ex/a>", "<http://ex/Person>"),
1776            ("<http://ex/Tea>", "<http://ex/a>", "<http://ex/Drink>"),
1777        ]);
1778        let rete = Rete::open(&bytes).unwrap();
1779        let q = "PREFIX ex: <http://ex/> SELECT ?x WHERE { \
1780                 ?x ex:a ex:Person MINUS { ?y ex:a ex:Drink } }";
1781        let (_, sols) = eval_sparql(&rete, q).unwrap();
1782        let mut xs: Vec<&str> = sols.iter().map(|b| b["x"].as_str()).collect();
1783        xs.sort();
1784        assert_eq!(xs, vec!["<http://ex/Alice>", "<http://ex/Bob>"]);
1785    }
1786
1787    #[test]
1788    fn values_pushdown_selects_subset() {
1789        // VALUES with several rows pushes each into the scan; the result must be
1790        // exactly the union (here: two of three disciplines).
1791        let bytes = rete_from(&[
1792            ("<http://ex/a>", "<http://ex/d>", "<http://ex/Bio>"),
1793            ("<http://ex/b>", "<http://ex/d>", "<http://ex/Phys>"),
1794            ("<http://ex/c>", "<http://ex/d>", "<http://ex/Chem>"),
1795        ]);
1796        let rete = Rete::open(&bytes).unwrap();
1797        let q = "PREFIX ex: <http://ex/> SELECT ?p ?disc WHERE { \
1798            VALUES ?disc { ex:Bio ex:Phys } ?p ex:d ?disc }";
1799        let (_, sols) = eval_sparql(&rete, q).unwrap();
1800        let mut got: Vec<(String, String)> = sols
1801            .iter()
1802            .map(|b| (b["p"].clone(), b["disc"].clone()))
1803            .collect();
1804        got.sort();
1805        assert_eq!(
1806            got,
1807            vec![
1808                ("<http://ex/a>".into(), "<http://ex/Bio>".into()),
1809                ("<http://ex/b>".into(), "<http://ex/Phys>".into()),
1810            ]
1811        );
1812    }
1813
1814    #[test]
1815    fn values_inline_data_joins() {
1816        let bytes = rete_from(&[
1817            ("<http://ex/Alice>", "<http://ex/knows>", "<http://ex/Bob>"),
1818            (
1819                "<http://ex/Alice>",
1820                "<http://ex/knows>",
1821                "<http://ex/Carol>",
1822            ),
1823            ("<http://ex/Dave>", "<http://ex/knows>", "<http://ex/Eve>"),
1824        ]);
1825        let rete = Rete::open(&bytes).unwrap();
1826        // Restrict to Alice's friends via VALUES.
1827        let q = "PREFIX ex: <http://ex/> \
1828                 SELECT ?f WHERE { VALUES ?p { ex:Alice } ?p ex:knows ?f }";
1829        let (_, sols) = eval_sparql(&rete, q).unwrap();
1830        let mut fs: Vec<&str> = sols.iter().map(|b| b["f"].as_str()).collect();
1831        fs.sort();
1832        assert_eq!(fs, vec!["<http://ex/Bob>", "<http://ex/Carol>"]);
1833    }
1834
1835    #[test]
1836    fn graph_queries_over_named_graphs() {
1837        use crate::write_dataset_v05 as write_dataset;
1838        // Shared dict; social graph has knows edges, profile graph has ages.
1839        let mut db = DictionaryBuilder::new();
1840        let edges = [
1841            ("<http://ex/Alice>", "<http://ex/knows>", "<http://ex/Bob>"),
1842            ("<http://ex/Bob>", "<http://ex/age>", "\"25\""),
1843        ];
1844        for (s, p, o) in edges {
1845            db.observe(s, p, o);
1846        }
1847        let dict = db.build();
1848        let mut social = GraphIndexBuilder::new();
1849        social.push(dict.encode(edges[0].0, edges[0].1, edges[0].2).unwrap());
1850        let mut profile = GraphIndexBuilder::new();
1851        profile.push(dict.encode(edges[1].0, edges[1].1, edges[1].2).unwrap());
1852        let named = vec![
1853            ("<http://ex/social>".to_string(), social.build()),
1854            ("<http://ex/profile>".to_string(), profile.build()),
1855        ];
1856        let bytes = write_dataset(
1857            &dict,
1858            &GraphIndexBuilder::new().build(),
1859            &named,
1860            true,
1861            &[],
1862            0,
1863        );
1864        let rete = Rete::open(&bytes).unwrap();
1865
1866        // GRAPH <iri>: knows edge only in the social graph.
1867        let q = "PREFIX ex: <http://ex/> \
1868                 SELECT ?f WHERE { GRAPH ex:social { ex:Alice ex:knows ?f } }";
1869        let (_, s) = eval_sparql(&rete, q).unwrap();
1870        assert_eq!(s.len(), 1);
1871        assert_eq!(s[0]["f"], "<http://ex/Bob>");
1872
1873        // GRAPH ?g: which graph holds the age triple?
1874        let q2 = "PREFIX ex: <http://ex/> \
1875                  SELECT ?g WHERE { GRAPH ?g { ex:Bob ex:age ?a } }";
1876        let (_, s2) = eval_sparql(&rete, q2).unwrap();
1877        assert_eq!(s2.len(), 1);
1878        assert_eq!(s2[0]["g"], "<http://ex/profile>");
1879
1880        // EXISTS inside GRAPH evaluates in that graph: the `age` triple exists in
1881        // the profile graph but NOT in the social graph.
1882        let q3 = "PREFIX ex: <http://ex/> SELECT ?f WHERE { \
1883                  GRAPH ex:profile { ?f ex:age ?a . FILTER EXISTS { ?f ex:age ?a2 } } }";
1884        assert_eq!(eval_sparql(&rete, q3).unwrap().1.len(), 1);
1885        let q4 = "PREFIX ex: <http://ex/> SELECT ?s WHERE { \
1886                  GRAPH ex:social { ?s ex:knows ?o . FILTER NOT EXISTS { ?s ex:age ?a } } }";
1887        // In the social graph, no `age` triples exist → NOT EXISTS keeps the row.
1888        assert_eq!(eval_sparql(&rete, q4).unwrap().1.len(), 1);
1889    }
1890
1891    #[test]
1892    fn from_unions_named_graphs() {
1893        use crate::write_dataset_v05 as write_dataset;
1894        // social graph: Alice knows Bob. profile graph: Bob knows Carol.
1895        // A join spanning both only works if FROM merges them into the default.
1896        let mut db = DictionaryBuilder::new();
1897        let t = [
1898            ("<http://ex/Alice>", "<http://ex/knows>", "<http://ex/Bob>"),
1899            ("<http://ex/Bob>", "<http://ex/knows>", "<http://ex/Carol>"),
1900        ];
1901        for (s, p, o) in t {
1902            db.observe(s, p, o);
1903        }
1904        let dict = db.build();
1905        let mut g1 = GraphIndexBuilder::new();
1906        g1.push(dict.encode(t[0].0, t[0].1, t[0].2).unwrap());
1907        let mut g2 = GraphIndexBuilder::new();
1908        g2.push(dict.encode(t[1].0, t[1].1, t[1].2).unwrap());
1909        let named = vec![
1910            ("<http://ex/social>".to_string(), g1.build()),
1911            ("<http://ex/profile>".to_string(), g2.build()),
1912        ];
1913        let bytes = write_dataset(
1914            &dict,
1915            &GraphIndexBuilder::new().build(),
1916            &named,
1917            true,
1918            &[],
1919            0,
1920        );
1921        let rete = Rete::open(&bytes).unwrap();
1922
1923        // Without FROM the default graph is empty → no join.
1924        let q0 = "PREFIX ex: <http://ex/> SELECT ?z WHERE { ?x ex:knows ?y . ?y ex:knows ?z }";
1925        assert!(eval_sparql(&rete, q0).unwrap().1.is_empty());
1926
1927        // FROM both graphs → the cross-graph join (Alice→Bob→Carol) succeeds.
1928        let q = "PREFIX ex: <http://ex/> \
1929                 SELECT ?z FROM ex:social FROM ex:profile \
1930                 WHERE { ?x ex:knows ?y . ?y ex:knows ?z }";
1931        let (_, s) = eval_sparql(&rete, q).unwrap();
1932        assert_eq!(s.len(), 1);
1933        assert_eq!(s[0]["z"], "<http://ex/Carol>");
1934
1935        // FROM NAMED restricts GRAPH ?g to the listed graph only.
1936        let qn = "PREFIX ex: <http://ex/> SELECT ?g FROM NAMED ex:social \
1937                  WHERE { GRAPH ?g { ?x ex:knows ?y } }";
1938        let (_, sn) = eval_sparql(&rete, qn).unwrap();
1939        let gs: Vec<&str> = sn.iter().map(|b| b["g"].as_str()).collect();
1940        assert_eq!(gs, vec!["<http://ex/social>"]); // profile excluded
1941    }
1942
1943    #[test]
1944    fn union_default_graph_opt_in() {
1945        use crate::write_dataset_v05 as write_dataset;
1946        // default graph: Root knows Alice. social: Alice knows Bob (twice — once
1947        // duplicated in profile, to pin set-union dedup). profile: the duplicate
1948        // plus Bob knows Carol.
1949        let mut db = DictionaryBuilder::new();
1950        let t = [
1951            ("<http://ex/Root>", "<http://ex/knows>", "<http://ex/Alice>"),
1952            ("<http://ex/Alice>", "<http://ex/knows>", "<http://ex/Bob>"),
1953            ("<http://ex/Bob>", "<http://ex/knows>", "<http://ex/Carol>"),
1954        ];
1955        for (s, p, o) in t {
1956            db.observe(s, p, o);
1957        }
1958        let dict = db.build();
1959        let enc = |i: usize| dict.encode(t[i].0, t[i].1, t[i].2).unwrap();
1960        let mut def = GraphIndexBuilder::new();
1961        def.push(enc(0));
1962        let mut g1 = GraphIndexBuilder::new();
1963        g1.push(enc(1));
1964        let mut g2 = GraphIndexBuilder::new();
1965        g2.push(enc(1)); // the SAME triple as social's — a set union keeps one
1966        g2.push(enc(2));
1967        let named = vec![
1968            ("<http://ex/social>".to_string(), g1.build()),
1969            ("<http://ex/profile>".to_string(), g2.build()),
1970        ];
1971        let bytes = write_dataset(&dict, &def.build(), &named, true, &[], 0);
1972        let rete = Rete::open(&bytes).unwrap();
1973        let union = QueryOpts {
1974            union_default_graph: true,
1975            ..QueryOpts::default()
1976        };
1977        let rows = |out: QueryOutput| match out {
1978            QueryOutput::Select(_, rows) => rows,
1979            other => panic!("expected Select, got {other:?}"),
1980        };
1981
1982        // OFF (the default): a pattern outside GRAPH sees only the real default
1983        // graph — one triple. This is the standard-semantics baseline the W3C
1984        // conformance suite runs on.
1985        let q = "PREFIX ex: <http://ex/> SELECT ?s ?o WHERE { ?s ex:knows ?o }";
1986        assert_eq!(rows(eval_query(&rete, q).unwrap()).len(), 1);
1987
1988        // ON: default ∪ social ∪ profile, deduplicated — 3 distinct triples,
1989        // not 4 (the duplicate collapses: RDF merge is a set union). The
1990        // default graph's own triple is INCLUDED (unlike a bare FROM).
1991        let got = rows(eval_query_with(&rete, q, union).unwrap());
1992        assert_eq!(got.len(), 3);
1993        assert!(got.iter().any(|b| b["s"] == "<http://ex/Root>"));
1994
1995        // ON: a cross-graph join (default→social→profile) now succeeds.
1996        let qj = "PREFIX ex: <http://ex/> SELECT ?z WHERE { \
1997                  ex:Root ex:knows ?x . ?x ex:knows ?y . ?y ex:knows ?z }";
1998        let sj = rows(eval_query_with(&rete, qj, union).unwrap());
1999        assert_eq!(sj.len(), 1);
2000        assert_eq!(sj[0]["z"], "<http://ex/Carol>");
2001
2002        // ON: GRAPH ?g still enumerates the named graphs exactly as before.
2003        let qg = "PREFIX ex: <http://ex/> SELECT DISTINCT ?g WHERE { GRAPH ?g { ?s ex:knows ?o } }";
2004        assert_eq!(rows(eval_query_with(&rete, qg, union).unwrap()).len(), 2);
2005
2006        // ON + explicit FROM: the query's own dataset clause wins — FROM social
2007        // alone excludes both the default graph and profile.
2008        let qf = "PREFIX ex: <http://ex/> SELECT ?s ?o FROM ex:social WHERE { ?s ex:knows ?o }";
2009        let sf = rows(eval_query_with(&rete, qf, union).unwrap());
2010        assert_eq!(sf.len(), 1);
2011        assert_eq!(sf[0]["s"], "<http://ex/Alice>");
2012
2013        // ON, empty-default single-named-graph shape (the zero-copy borrow arm):
2014        // build a second dataset with an empty default and ONE named graph.
2015        let mut db2 = DictionaryBuilder::new();
2016        db2.observe(t[1].0, t[1].1, t[1].2);
2017        let dict2 = db2.build();
2018        let mut only = GraphIndexBuilder::new();
2019        only.push(dict2.encode(t[1].0, t[1].1, t[1].2).unwrap());
2020        let named2 = vec![("<http://ex/only>".to_string(), only.build())];
2021        let bytes2 = write_dataset(
2022            &dict2,
2023            &GraphIndexBuilder::new().build(),
2024            &named2,
2025            true,
2026            &[],
2027            0,
2028        );
2029        let rete2 = Rete::open(&bytes2).unwrap();
2030        assert_eq!(rows(eval_query(&rete2, q).unwrap()).len(), 0); // standard: 0
2031        assert_eq!(rows(eval_query_with(&rete2, q, union).unwrap()).len(), 1);
2032    }
2033
2034    #[test]
2035    fn describe_resource() {
2036        let bytes = rete_from(&[
2037            ("<http://ex/Alice>", "<http://ex/knows>", "<http://ex/Bob>"),
2038            ("<http://ex/Alice>", "<http://ex/age>", "\"30\""),
2039            ("<http://ex/Bob>", "<http://ex/age>", "\"25\""),
2040        ]);
2041        let rete = Rete::open(&bytes).unwrap();
2042        // DESCRIBE <Alice> → Alice's two outgoing triples.
2043        match eval_query(&rete, "DESCRIBE <http://ex/Alice>").unwrap() {
2044            QueryOutput::Construct(t) => assert_eq!(t.len(), 2),
2045            other => panic!("expected Construct, got {other:?}"),
2046        }
2047        // DESCRIBE ?x WHERE { ?x ex:age ?a } → describes Alice and Bob.
2048        let q = "PREFIX ex: <http://ex/> DESCRIBE ?x WHERE { ?x ex:age ?a }";
2049        match eval_query(&rete, q).unwrap() {
2050            QueryOutput::Construct(t) => {
2051                // Alice has 2 triples, Bob has 1 → 3 total.
2052                assert_eq!(t.len(), 3);
2053            }
2054            other => panic!("expected Construct, got {other:?}"),
2055        }
2056    }
2057
2058    #[test]
2059    fn ask_and_construct() {
2060        let bytes = rete_from(&[
2061            ("<http://ex/Alice>", "<http://ex/knows>", "<http://ex/Bob>"),
2062            ("<http://ex/Bob>", "<http://ex/knows>", "<http://ex/Carol>"),
2063        ]);
2064        let rete = Rete::open(&bytes).unwrap();
2065
2066        // ASK: is there any knows edge? yes; a likes edge? no.
2067        match eval_query(&rete, "PREFIX ex: <http://ex/> ASK { ?a ex:knows ?b }").unwrap() {
2068            QueryOutput::Ask(b) => assert!(b),
2069            other => panic!("expected Ask, got {other:?}"),
2070        }
2071        match eval_query(&rete, "PREFIX ex: <http://ex/> ASK { ?a ex:likes ?b }").unwrap() {
2072            QueryOutput::Ask(b) => assert!(!b),
2073            other => panic!("expected Ask, got {other:?}"),
2074        }
2075
2076        // CONSTRUCT a reverse `knownBy` graph.
2077        let q = "PREFIX ex: <http://ex/> \
2078                 CONSTRUCT { ?b ex:knownBy ?a } WHERE { ?a ex:knows ?b }";
2079        match eval_query(&rete, q).unwrap() {
2080            QueryOutput::Construct(mut triples) => {
2081                triples.sort();
2082                assert_eq!(triples.len(), 2);
2083                assert!(triples.contains(&(
2084                    "<http://ex/Bob>".into(),
2085                    "<http://ex/knownBy>".into(),
2086                    "<http://ex/Alice>".into(),
2087                )));
2088            }
2089            other => panic!("expected Construct, got {other:?}"),
2090        }
2091    }
2092
2093    #[test]
2094    fn substr_strbefore_strafter() {
2095        let bytes = rete_from(&[("<http://ex/a>", "<http://ex/name>", "\"Alice Smith\"")]);
2096        let rete = Rete::open(&bytes).unwrap();
2097        let q = "PREFIX ex: <http://ex/> SELECT ?first ?last ?ini WHERE { \
2098            ?p ex:name ?n . \
2099            BIND(STRBEFORE(?n, \" \") AS ?first) \
2100            BIND(STRAFTER(?n, \" \") AS ?last) \
2101            BIND(SUBSTR(?n, 1, 1) AS ?ini) }";
2102        let (_, sols) = eval_sparql(&rete, q).unwrap();
2103        // String built-ins return proper literal terms (quoted), not bare text.
2104        assert_eq!(sols[0]["first"], "\"Alice\"");
2105        assert_eq!(sols[0]["last"], "\"Smith\"");
2106        assert_eq!(sols[0]["ini"], "\"A\"");
2107    }
2108
2109    #[test]
2110    fn concat_and_coalesce() {
2111        // Alice has a nickname, Bob doesn't.
2112        let bytes = rete_from(&[
2113            ("<http://ex/Alice>", "<http://ex/name>", "\"Alice\""),
2114            ("<http://ex/Alice>", "<http://ex/nick>", "\"Al\""),
2115            ("<http://ex/Bob>", "<http://ex/name>", "\"Bob\""),
2116        ]);
2117        let rete = Rete::open(&bytes).unwrap();
2118        // COALESCE falls back to name when nick is unbound; CONCAT builds a label.
2119        let q = "PREFIX ex: <http://ex/> SELECT ?label WHERE { \
2120            ?p ex:name ?name . OPTIONAL { ?p ex:nick ?nick } \
2121            BIND(CONCAT(\"@\", COALESCE(?nick, ?name)) AS ?label) }";
2122        let (_, sols) = eval_sparql(&rete, q).unwrap();
2123        let mut labels: Vec<&str> = sols.iter().map(|b| b["label"].as_str()).collect();
2124        labels.sort();
2125        assert_eq!(labels, vec!["\"@Al\"", "\"@Bob\""]);
2126    }
2127
2128    #[test]
2129    fn builtin_functions() {
2130        let bytes = rete_from(&[
2131            ("<http://ex/Alice>", "<http://ex/name>", "\"Alice Smith\""),
2132            ("<http://ex/Bob>", "<http://ex/name>", "\"Bob Jones\""),
2133        ]);
2134        let rete = Rete::open(&bytes).unwrap();
2135        // CONTAINS on the literal value, and STRLEN as a computed value.
2136        let q = "PREFIX ex: <http://ex/> SELECT ?p ?len WHERE { \
2137            ?p ex:name ?n . FILTER(CONTAINS(?n, \"Smith\")) BIND(STRLEN(?n) AS ?len) }";
2138        let (_, sols) = eval_sparql(&rete, q).unwrap();
2139        assert_eq!(sols.len(), 1);
2140        assert_eq!(sols[0]["p"], "<http://ex/Alice>");
2141        assert_eq!(
2142            sols[0]["len"],
2143            "\"11\"^^<http://www.w3.org/2001/XMLSchema#integer>"
2144        ); // "Alice Smith"
2145    }
2146
2147    #[test]
2148    fn geosparql_filter_and_functions() {
2149        let wkt = "\"POLYGON((0 0,10 0,10 10,0 10,0 0))\"^^\
2150            <http://www.opengis.net/ont/geosparql#wktLiteral>";
2151        let bytes = rete_from(&[
2152            (
2153                "<http://ex/f>",
2154                "<http://www.opengis.net/ont/geosparql#hasGeometry>",
2155                "<http://ex/f/g>",
2156            ),
2157            (
2158                "<http://ex/f/g>",
2159                "<http://www.opengis.net/ont/geosparql#asWKT>",
2160                wkt,
2161            ),
2162            (
2163                "<http://ex/f>",
2164                "<http://ex/year>",
2165                "\"1815\"^^<http://www.w3.org/2001/XMLSchema#integer>",
2166            ),
2167        ]);
2168        let rete = Rete::open(&bytes).unwrap();
2169        let pre = "PREFIX geo: <http://www.opengis.net/ont/geosparql#> \
2170            PREFIX geof: <http://www.opengis.net/def/function/geosparql/> \
2171            PREFIX uom: <http://www.opengis.net/def/uom/OGC/1.0/> PREFIX ex: <http://ex/> ";
2172
2173        // Headline: temporal FILTER + spatial point-in-polygon compose.
2174        let (_, s) = eval_sparql(
2175            &rete,
2176            &format!(
2177                "{pre}SELECT ?f WHERE {{ ?f ex:year ?y ; \
2178            geo:hasGeometry/geo:asWKT ?w . \
2179            FILTER(?y = 1815 && geof:sfContains(?w, \"POINT(5 5)\"^^geo:wktLiteral)) }}"
2180            ),
2181        )
2182        .unwrap();
2183        assert_eq!(s.len(), 1, "point inside the polygon in year 1815");
2184        assert_eq!(s[0]["f"], "<http://ex/f>");
2185
2186        // Point outside → no rows.
2187        let (_, s) = eval_sparql(
2188            &rete,
2189            &format!(
2190                "{pre}SELECT ?f WHERE {{ \
2191            ?f geo:hasGeometry/geo:asWKT ?w . \
2192            FILTER(geof:sfContains(?w, \"POINT(50 50)\"^^geo:wktLiteral)) }}"
2193            ),
2194        )
2195        .unwrap();
2196        assert!(s.is_empty());
2197
2198        // sfWithin is the argument-swapped relation.
2199        let (_, s) = eval_sparql(
2200            &rete,
2201            &format!(
2202                "{pre}SELECT ?f WHERE {{ \
2203            ?f geo:hasGeometry/geo:asWKT ?w . \
2204            FILTER(geof:sfWithin(\"POINT(5 5)\"^^geo:wktLiteral, ?w)) }}"
2205            ),
2206        )
2207        .unwrap();
2208        assert_eq!(s.len(), 1);
2209
2210        // Malformed WKT is a type error → 0 rows, but the query must NOT error.
2211        let (_, s) = eval_sparql(
2212            &rete,
2213            &format!(
2214                "{pre}SELECT ?f WHERE {{ \
2215            ?f geo:hasGeometry/geo:asWKT ?w . \
2216            FILTER(geof:sfContains(?w, \"garbage\"^^geo:wktLiteral)) }}"
2217            ),
2218        )
2219        .unwrap();
2220        assert!(s.is_empty());
2221
2222        // Relation in BIND (value position) → typed xsd:boolean.
2223        let (_, s) = eval_sparql(
2224            &rete,
2225            &format!(
2226                "{pre}SELECT ?hit WHERE {{ \
2227            ?f geo:hasGeometry/geo:asWKT ?w . \
2228            BIND(geof:sfContains(?w, \"POINT(5 5)\"^^geo:wktLiteral) AS ?hit) }}"
2229            ),
2230        )
2231        .unwrap();
2232        assert_eq!(
2233            s[0]["hit"],
2234            "\"true\"^^<http://www.w3.org/2001/XMLSchema#boolean>"
2235        );
2236
2237        // distance → xsd:double; envelope → geo:wktLiteral.
2238        let (_, s) = eval_sparql(
2239            &rete,
2240            &format!(
2241                "{pre}SELECT ?d WHERE {{ BIND(geof:distance(\
2242            \"POINT(0 0)\"^^geo:wktLiteral, \"POINT(0 1)\"^^geo:wktLiteral, uom:metre) AS ?d) }}"
2243            ),
2244        )
2245        .unwrap();
2246        assert!(
2247            s[0]["d"].ends_with("XMLSchema#double>"),
2248            "distance is xsd:double: {}",
2249            s[0]["d"]
2250        );
2251        let (_, s) = eval_sparql(
2252            &rete,
2253            &format!(
2254                "{pre}SELECT ?e WHERE {{ \
2255            ?f geo:hasGeometry/geo:asWKT ?w . BIND(geof:envelope(?w) AS ?e) }}"
2256            ),
2257        )
2258        .unwrap();
2259        assert!(s[0]["e"].contains("wktLiteral") && s[0]["e"].contains("POLYGON"));
2260
2261        // An unsupported geof: function is rejected cleanly at parse/lower time.
2262        assert!(eval_sparql(
2263            &rete,
2264            &format!(
2265                "{pre}SELECT ?x WHERE {{ \
2266            BIND(geof:buffer(\"POINT(0 0)\"^^geo:wktLiteral, 1) AS ?x) }}"
2267            )
2268        )
2269        .is_err());
2270    }
2271
2272    #[test]
2273    fn bind_arithmetic() {
2274        let xsd = "<http://www.w3.org/2001/XMLSchema#integer>";
2275        let bytes = rete_from(&[(
2276            "<http://ex/a>",
2277            "<http://ex/age>",
2278            &format!("\"30\"^^{xsd}"),
2279        )]);
2280        let rete = Rete::open(&bytes).unwrap();
2281        // BIND a computed value, and FILTER on arithmetic.
2282        let q = "PREFIX ex: <http://ex/> \
2283                 SELECT ?next WHERE { ?p ex:age ?age . BIND(?age + 1 AS ?next) FILTER(?age * 2 > 50) }";
2284        let (_, sols) = eval_sparql(&rete, q).unwrap();
2285        assert_eq!(sols.len(), 1);
2286        assert_eq!(
2287            sols[0]["next"],
2288            "\"31\"^^<http://www.w3.org/2001/XMLSchema#integer>"
2289        );
2290    }
2291
2292    #[test]
2293    fn bind_value_is_visible_to_a_following_filter_and_join() {
2294        // A BIND inside the WHERE pattern must be evaluated before a *following*
2295        // FILTER (and join) can reference it — the bound var is in-tree, not a
2296        // projection-time alias.
2297        let xsd = "<http://www.w3.org/2001/XMLSchema#integer>";
2298        let n = |v: i32| format!("\"{v}\"^^{xsd}");
2299        let bytes = rete_from(&[
2300            ("<http://ex/a>", "<http://ex/v>", &n(1)),
2301            ("<http://ex/b>", "<http://ex/v>", &n(2)),
2302            ("<http://ex/c>", "<http://ex/v>", &n(3)),
2303            // a node whose :v equals b's value+1, for the join case
2304            ("<http://ex/x>", "<http://ex/v>", &n(3)),
2305        ]);
2306        let rete = Rete::open(&bytes).unwrap();
2307
2308        // FILTER references the BIND'd ?z.
2309        let q1 = "PREFIX ex: <http://ex/> SELECT ?s WHERE { \
2310            ?s ex:v ?o . BIND(?o + 1 AS ?z) FILTER(?z = 3) }";
2311        let (_, s1) = eval_sparql(&rete, q1).unwrap();
2312        assert_eq!(s1.len(), 1, "only b (2+1=3) passes");
2313        assert_eq!(s1[0]["s"], "<http://ex/b>");
2314
2315        // A following triple pattern joins on the BIND'd ?z.
2316        let q2 = "PREFIX ex: <http://ex/> SELECT ?s ?s2 WHERE { \
2317            ?s ex:v ?o . BIND(?o + 1 AS ?z) ?s2 ex:v ?z }";
2318        let (_, s2) = eval_sparql(&rete, q2).unwrap();
2319        // a (1→2) joins b (:v 2); b (2→3) joins c and x (:v 3); c (3→4) no match.
2320        let mut pairs: Vec<(String, String)> = s2
2321            .iter()
2322            .map(|b| (b["s"].clone(), b["s2"].clone()))
2323            .collect();
2324        pairs.sort();
2325        assert_eq!(
2326            pairs,
2327            vec![
2328                ("<http://ex/a>".to_string(), "<http://ex/b>".to_string()),
2329                ("<http://ex/b>".to_string(), "<http://ex/c>".to_string()),
2330                ("<http://ex/b>".to_string(), "<http://ex/x>".to_string()),
2331            ]
2332        );
2333    }
2334
2335    #[test]
2336    fn order_by_numeric_desc_then_limit() {
2337        let xsd = "<http://www.w3.org/2001/XMLSchema#integer>";
2338        let bytes = rete_from(&[
2339            (
2340                "<http://ex/a>",
2341                "<http://ex/age>",
2342                &format!("\"30\"^^{xsd}"),
2343            ),
2344            (
2345                "<http://ex/b>",
2346                "<http://ex/age>",
2347                &format!("\"25\"^^{xsd}"),
2348            ),
2349            (
2350                "<http://ex/c>",
2351                "<http://ex/age>",
2352                &format!("\"40\"^^{xsd}"),
2353            ),
2354        ]);
2355        let rete = Rete::open(&bytes).unwrap();
2356        // Oldest two, descending by age.
2357        let q = "PREFIX ex: <http://ex/> \
2358                 SELECT ?p WHERE { ?p ex:age ?age } ORDER BY DESC(?age) LIMIT 2";
2359        let (_, sols) = eval_sparql(&rete, q).unwrap();
2360        let ps: Vec<&str> = sols.iter().map(|b| b["p"].as_str()).collect();
2361        assert_eq!(ps, vec!["<http://ex/c>", "<http://ex/a>"]); // 40, 30
2362    }
2363
2364    #[test]
2365    fn limit_early_out_two_hop_join() {
2366        // A→B, B→C, B→D, C→E. Two-hop join (?x k ?y . ?y k ?z) has 3 solutions:
2367        // (A,B,C), (A,B,D), (B,C,E). The LIMIT early-out must preserve the count
2368        // contract and only ever yield genuine solutions.
2369        let bytes = rete_from(&[
2370            ("<http://ex/A>", "<http://ex/k>", "<http://ex/B>"),
2371            ("<http://ex/B>", "<http://ex/k>", "<http://ex/C>"),
2372            ("<http://ex/B>", "<http://ex/k>", "<http://ex/D>"),
2373            ("<http://ex/C>", "<http://ex/k>", "<http://ex/E>"),
2374        ]);
2375        let rete = Rete::open(&bytes).unwrap();
2376        let q = "PREFIX ex: <http://ex/> SELECT ?x ?z WHERE { ?x ex:k ?y . ?y ex:k ?z }";
2377        let (_, full) = eval_sparql(&rete, q).unwrap();
2378        assert_eq!(full.len(), 3);
2379
2380        let (_, one) = eval_sparql(&rete, &format!("{q} LIMIT 1")).unwrap();
2381        assert_eq!(one.len(), 1);
2382        // The early-out row must be a real solution of the full query.
2383        assert!(one.iter().all(|r| full.contains(r)));
2384
2385        // LIMIT above the total returns everything; OFFSET composes.
2386        let (_, all) = eval_sparql(&rete, &format!("{q} LIMIT 100")).unwrap();
2387        assert_eq!(all.len(), 3);
2388        let (_, off) = eval_sparql(&rete, &format!("{q} LIMIT 100 OFFSET 2")).unwrap();
2389        assert_eq!(off.len(), 1);
2390    }
2391
2392    #[test]
2393    fn limit_early_out_filter_over_bgp() {
2394        // FILTER over a BGP under LIMIT streams and stops early; the result must
2395        // match the unlimited filtered query's prefix.
2396        let xsd = "<http://www.w3.org/2001/XMLSchema#integer>";
2397        let bytes = rete_from(&[
2398            ("<http://ex/a>", "<http://ex/n>", &format!("\"10\"^^{xsd}")),
2399            ("<http://ex/b>", "<http://ex/n>", &format!("\"20\"^^{xsd}")),
2400            ("<http://ex/c>", "<http://ex/n>", &format!("\"30\"^^{xsd}")),
2401            ("<http://ex/d>", "<http://ex/n>", &format!("\"40\"^^{xsd}")),
2402        ]);
2403        let rete = Rete::open(&bytes).unwrap();
2404        let q = "PREFIX ex: <http://ex/> SELECT ?p WHERE { ?p ex:n ?v FILTER(?v > 15) }";
2405        let (_, full) = eval_sparql(&rete, q).unwrap();
2406        assert_eq!(full.len(), 3); // b, c, d
2407        let (_, two) = eval_sparql(&rete, &format!("{q} LIMIT 2")).unwrap();
2408        assert_eq!(two.len(), 2);
2409        assert!(two.iter().all(|r| full.contains(r)));
2410    }
2411
2412    #[test]
2413    fn distinct_bgp_fast_matches_general() {
2414        // a/b both →x, b→y, c→z. The integer-DISTINCT fast path must collapse on
2415        // the projection and apply OFFSET/LIMIT after dedup.
2416        let bytes = rete_from(&[
2417            ("<http://ex/a>", "<http://ex/p>", "<http://ex/x>"),
2418            ("<http://ex/b>", "<http://ex/p>", "<http://ex/x>"),
2419            ("<http://ex/b>", "<http://ex/p>", "<http://ex/y>"),
2420            ("<http://ex/c>", "<http://ex/p>", "<http://ex/z>"),
2421        ]);
2422        let rete = Rete::open(&bytes).unwrap();
2423        // DISTINCT ?o → {x, y, z} = 3 (the two ?s→x rows collapse).
2424        let q = "PREFIX ex: <http://ex/> SELECT DISTINCT ?o WHERE { ?s ex:p ?o }";
2425        let (proj, sols) = eval_sparql(&rete, q).unwrap();
2426        assert_eq!(proj, vec!["o"]);
2427        let mut os: Vec<&str> = sols.iter().map(|b| b["o"].as_str()).collect();
2428        os.sort();
2429        assert_eq!(os, vec!["<http://ex/x>", "<http://ex/y>", "<http://ex/z>"]);
2430        // LIMIT applies after dedup.
2431        assert_eq!(
2432            eval_sparql(&rete, &format!("{q} LIMIT 2")).unwrap().1.len(),
2433            2
2434        );
2435        // A 2-var DISTINCT keeps every (s, o) pair → 4 rows.
2436        let q2 = "PREFIX ex: <http://ex/> SELECT DISTINCT ?s ?o WHERE { ?s ex:p ?o }";
2437        assert_eq!(eval_sparql(&rete, q2).unwrap().1.len(), 4);
2438    }
2439
2440    #[test]
2441    fn limit_caps_solutions() {
2442        let bytes = rete_from(&[
2443            ("<http://ex/a>", "<http://ex/p>", "<http://ex/1>"),
2444            ("<http://ex/b>", "<http://ex/p>", "<http://ex/2>"),
2445            ("<http://ex/c>", "<http://ex/p>", "<http://ex/3>"),
2446        ]);
2447        let rete = Rete::open(&bytes).unwrap();
2448        let (_, sols) =
2449            eval_sparql(&rete, "SELECT ?x WHERE { ?x <http://ex/p> ?y } LIMIT 2").unwrap();
2450        assert_eq!(sols.len(), 2);
2451    }
2452
2453    /// End to end through the file and the memoizing resolver: a literal with an
2454    /// escaped quote in its value matches on the text AFTER the quote. The
2455    /// boolean string predicates used to read the stored token only up to its
2456    /// first `"`, so of these four labels CONTAINS("Quantum") found one instead
2457    /// of three and CONTAINS("Gases") none — while STRLEN, on the other code
2458    /// path, already saw all 25 characters.
2459    #[test]
2460    fn string_filters_see_past_an_embedded_quote() {
2461        let bytes = rete_from(&[
2462            (
2463                "<http://ex/a>",
2464                "<http://ex/label>",
2465                "\"plain Quantum here\"",
2466            ),
2467            (
2468                "<http://ex/b>",
2469                "<http://ex/label>",
2470                r#""He said \"Quantum\" loudly"@en"#,
2471            ),
2472            (
2473                "<http://ex/c>",
2474                "<http://ex/label>",
2475                r#""Theory of \"Quantum\" Gases""#,
2476            ),
2477            ("<http://ex/d>", "<http://ex/label>", "\"no match at all\""),
2478            (
2479                "<http://ex/e>",
2480                "<http://ex/label>",
2481                "\"tab\\there\\nline two\"^^<http://www.w3.org/2001/XMLSchema#string>",
2482            ),
2483        ]);
2484        let rete = Rete::open(&bytes).unwrap();
2485        let subjects = |filter: &str| {
2486            let q = format!("SELECT ?s WHERE {{ ?s <http://ex/label> ?l FILTER({filter}) }}");
2487            let (_, sols) = eval_sparql(&rete, &q).unwrap();
2488            let mut out: Vec<String> = sols.iter().map(|b| b["s"].clone()).collect();
2489            out.sort();
2490            out
2491        };
2492        let (a, b, c, e) = (
2493            "<http://ex/a>",
2494            "<http://ex/b>",
2495            "<http://ex/c>",
2496            "<http://ex/e>",
2497        );
2498        assert_eq!(subjects(r#"CONTAINS(?l, "Quantum")"#), vec![a, b, c]);
2499        assert_eq!(subjects(r#"CONTAINS(?l, "Gases")"#), vec![c]);
2500        assert_eq!(subjects(r#"STRENDS(?l, "loudly")"#), vec![b]);
2501        assert_eq!(subjects(r#"STRSTARTS(?l, "Theory of \"Q")"#), vec![c]);
2502        assert_eq!(subjects(r#"REGEX(?l, "gases$", "i")"#), vec![c]);
2503        assert_eq!(subjects(r#"REGEX(?l, "^line two$", "m")"#), vec![e]);
2504        assert_eq!(subjects(r#"CONTAINS(?l, "\there")"#), vec![e]);
2505        assert_eq!(subjects(r#"LANGMATCHES(LANG(?l), "en")"#), vec![b]);
2506        assert_eq!(subjects(r#"STRAFTER(?l, "Quantum") = "\" Gases""#), vec![c]);
2507        assert_eq!(
2508            subjects(r#"STRBEFORE(?l, " loudly") = "He said \"Quantum\""@en"#),
2509            vec![b]
2510        );
2511        assert_eq!(subjects(r#"STRLEN(?l) = 25"#), vec![c]);
2512        assert_eq!(subjects(r#"STRLEN(?l) = 24"#), vec![b]);
2513    }
2514
2515    /// The OWL 2 QL rewrite is gated PER ATOM: one `rdfs:domain` axiom on a
2516    /// property the data never uses used to add a domain branch to every class
2517    /// atom of every reasoned query (0.30 s became 1.02 s, 4.2 MB became
2518    /// 11.8 MB fetched, on OpenCitations with its ontology). A class with no
2519    /// subclass and no domain/range property the file uses keeps its plain
2520    /// pattern; a class that gains members becomes a `DistinctUnion` holding
2521    /// exactly the sources that can produce them.
2522    #[test]
2523    fn reasoning_rewrites_only_the_atoms_it_can_extend() {
2524        let dom = "<http://www.w3.org/2000/01/rdf-schema#domain>";
2525        let sub = "<http://www.w3.org/2000/01/rdf-schema#subClassOf>";
2526        let ty = "<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>";
2527        let bytes = rete_from(&[
2528            (
2529                "<http://ex/hasCharacterisation>",
2530                dom,
2531                "<http://ex/Citation>",
2532            ),
2533            ("<http://ex/SelfCitation>", sub, "<http://ex/Citation>"),
2534            ("<http://ex/writtenBy>", dom, "<http://ex/Work>"),
2535            ("<http://ex/r1>", ty, "<http://ex/Role>"),
2536            ("<http://ex/w1>", ty, "<http://ex/Work>"),
2537            ("<http://ex/w2>", "<http://ex/writtenBy>", "<http://ex/ann>"),
2538        ]);
2539        let rete = Rete::open(&bytes).unwrap();
2540        let rewrite = |q: &str| {
2541            let sel = parse_select(q).unwrap();
2542            ql::reason_rewrite(sel.plan, &rete, &sel.project)
2543        };
2544        // No subclass, and the one domain axiom is about another class: as is.
2545        assert!(matches!(
2546            rewrite("SELECT ?s WHERE { ?s a <http://ex/Role> ; ?p ?o }"),
2547            Plan::Bgp(p) if p.len() == 2
2548        ));
2549        // The domain axiom's own class: its property and its subclass are
2550        // never used, so there is nothing to add.
2551        assert!(matches!(
2552            rewrite("SELECT ?s WHERE { ?s a <http://ex/Citation> }"),
2553            Plan::Bgp(p) if p.len() == 1
2554        ));
2555        // Work gains the subjects of writtenBy: two sources, one per way.
2556        match rewrite("SELECT ?s WHERE { ?s a <http://ex/Work> }") {
2557            Plan::DistinctUnion { vars, sources } => {
2558                assert_eq!(vars, vec!["s".to_string()]);
2559                assert_eq!(sources.len(), 2);
2560            }
2561            other => panic!("expected a DistinctUnion, got {other:?}"),
2562        }
2563        let (_, sols) =
2564            eval_sparql_reasoned(&rete, "SELECT ?s WHERE { ?s a <http://ex/Work> }").unwrap();
2565        let mut got: Vec<&str> = sols.iter().map(|b| b["s"].as_str()).collect();
2566        got.sort();
2567        assert_eq!(got, vec!["<http://ex/w1>", "<http://ex/w2>"]);
2568    }
2569
2570    /// A join whose left side turns out far smaller than the right BGP probes
2571    /// the BGP per left row instead of evaluating it whole — the same rows
2572    /// either way. Driven here with the probe floor removed, so the small
2573    /// graph takes the path a 2.9 B-triple file takes for real.
2574    #[test]
2575    fn a_small_left_side_probes_the_right_bgp() {
2576        let mut t: Vec<(String, String, String)> = Vec::new();
2577        let e = |n: String| format!("<http://ex/{n}>");
2578        for i in 0..200 {
2579            t.push((e(format!("j{i}")), e("a".into()), e("Journal".into())));
2580            t.push((e(format!("j{i}")), e("title".into()), format!("\"T{i}\"")));
2581            t.push((e(format!("j{i}")), e("id".into()), e(format!("id{i}"))));
2582            t.push((e(format!("id{i}")), e("value".into()), format!("\"{i}\"")));
2583        }
2584        t.push((e("work".into()), e("partOf".into()), e("issue".into())));
2585        t.push((e("issue".into()), e("partOf".into()), e("j7".into())));
2586        let refs: Vec<(&str, &str, &str)> = t
2587            .iter()
2588            .map(|(s, p, o)| (s.as_str(), p.as_str(), o.as_str()))
2589            .collect();
2590        let rete = Rete::open(&rete_from(&refs)).unwrap();
2591        let queries = [
2592            "PREFIX ex: <http://ex/> SELECT ?j ?t ?v WHERE { ex:work ex:partOf+ ?j . \
2593             ?j ex:a ex:Journal ; ex:title ?t ; ex:id ?i . ?i ex:value ?v }",
2594            "PREFIX ex: <http://ex/> SELECT ?j ?t WHERE { ex:work ex:partOf+ ?j \
2595             OPTIONAL { ?j ex:title ?t } }",
2596        ];
2597        for q in queries {
2598            let run = |floor: f64| {
2599                crate::bgp::with_probe_floor(floor, || {
2600                    let (_, sols) = eval_sparql(&rete, q).unwrap();
2601                    let mut v: Vec<String> = sols.iter().map(|b| format!("{b:?}")).collect();
2602                    v.sort();
2603                    v
2604                })
2605            };
2606            let hashed = run(f64::MAX);
2607            assert!(!hashed.is_empty());
2608            assert_eq!(run(0.0), hashed, "{q}");
2609        }
2610    }
2611    /// 200 people: each `knows` the next, the even ones have an `age`, every
2612    /// tenth is a `Manager`; two of them carry a second type.
2613    fn people() -> Rete {
2614        const TYPE: &str = "<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>";
2615        let e = |n: String| format!("<http://ex/{n}>");
2616        let mut t: Vec<(String, String, String)> = Vec::new();
2617        for i in 0..200 {
2618            t.push((
2619                e(format!("p{i}")),
2620                e("knows".into()),
2621                e(format!("p{}", (i + 1) % 200)),
2622            ));
2623            t.push((e(format!("p{i}")), e("name".into()), format!("\"N{i}\"")));
2624            if i % 2 == 0 {
2625                t.push((e(format!("p{i}")), e("age".into()), format!("\"{i}\"")));
2626            }
2627            let class = if i % 10 == 0 { "Manager" } else { "Person" };
2628            t.push((e(format!("p{i}")), TYPE.into(), e(class.into())));
2629        }
2630        for i in [3, 4] {
2631            t.push((e(format!("p{i}")), TYPE.into(), e("Agent".into())));
2632        }
2633        let refs: Vec<(&str, &str, &str)> = t
2634            .iter()
2635            .map(|(s, p, o)| (s.as_str(), p.as_str(), o.as_str()))
2636            .collect();
2637        Rete::open(&rete_from(&refs)).unwrap()
2638    }
2639
2640    /// Rows of `q` as sorted strings, under the given probe floor
2641    /// (`f64::MAX`: the hash and whole-evaluation plans; `0.0`: every probe
2642    /// path a 2.9 B-triple file takes for real).
2643    fn rows_at(rete: &Rete, q: &str, floor: f64) -> Vec<String> {
2644        crate::bgp::with_probe_floor(floor, || {
2645            let (_, sols) = eval_sparql(rete, q).unwrap();
2646            let mut v: Vec<String> = sols.iter().map(|b| format!("{b:?}")).collect();
2647            v.sort();
2648            v
2649        })
2650    }
2651
2652    /// `FILTER (NOT) EXISTS` and `MINUS` over a fat BGP probe it per outer
2653    /// row: the same rows as loading it, in every shape.
2654    #[test]
2655    fn correlated_exists_and_minus_match_whole_evaluation() {
2656        let rete = people();
2657        let pre = "PREFIX ex: <http://ex/> ";
2658        let bodies = [
2659            // NOT EXISTS / EXISTS on a shared subject
2660            "SELECT ?s WHERE { ?s ex:knows ?o . FILTER NOT EXISTS { ?s ex:age ?a } }",
2661            "SELECT ?s WHERE { ?s ex:knows ?o . FILTER EXISTS { ?s ex:age ?a } }",
2662            // two inner patterns, joined through a variable the outer side lacks
2663            "SELECT ?s WHERE { ?s ex:name ?n . FILTER NOT EXISTS { ?s ex:knows ?o . ?o ex:age ?a } }",
2664            // shared object, an unrelated inner variable
2665            "SELECT ?o WHERE { ?s ex:knows ?o . FILTER NOT EXISTS { ?x ex:knows ?o . ?x ex:age ?a } }",
2666            // an inner constant the file does not hold: EXISTS is false for every row
2667            "SELECT ?s WHERE { ?s ex:name ?n . FILTER NOT EXISTS { ?s ex:nothere ?a } }",
2668            "SELECT ?s WHERE { ?s ex:name ?n . FILTER EXISTS { ?s ex:nothere ?a } }",
2669            // no variable shared: the whole-evaluation answer
2670            "SELECT ?s WHERE { ?s ex:name ?n . FILTER NOT EXISTS { ?z ex:age \"4\" } }",
2671            // a ground inner pattern
2672            "SELECT ?s WHERE { ?s ex:name ?n . FILTER EXISTS { ex:p4 ex:age \"4\" } }",
2673            // an outer value the inner side can never hold
2674            "SELECT ?s WHERE { ?s ex:name ?n . BIND(CONCAT(?n, \"!\") AS ?m) FILTER NOT EXISTS { ?m ex:age ?a } }",
2675            // MINUS: shared subject, shared object, disjoint domain, unknown constant
2676            "SELECT ?s WHERE { ?s ex:knows ?o . MINUS { ?s ex:age ?a } }",
2677            "SELECT ?o WHERE { ?s ex:knows ?o . MINUS { ?x ex:knows ?o . ?x ex:age ?a } }",
2678            "SELECT ?s WHERE { ?s ex:name ?n . MINUS { ?z ex:age ?a } }",
2679            "SELECT ?s WHERE { ?s ex:name ?n . MINUS { ?s ex:nothere ?a } }",
2680            // OPTIONAL on the left: MINUS keeps the rows that share no binding
2681            "SELECT ?s ?a WHERE { ?s ex:name ?n . OPTIONAL { ?s ex:age ?a } MINUS { ?a ex:nothing ?z } }",
2682            // under VALUES
2683            "SELECT ?s WHERE { VALUES ?s { ex:p1 ex:p2 ex:p3 } FILTER NOT EXISTS { ?s ex:age ?a } }",
2684        ];
2685        for body in bodies {
2686            let q = format!("{pre}{body}");
2687            let whole = rows_at(&rete, &q, f64::MAX);
2688            assert_eq!(rows_at(&rete, &q, 0.0), whole, "{body}");
2689        }
2690        // The answers themselves, so "same as before" is not "both empty".
2691        let n = |body: &str| rows_at(&rete, &format!("{pre}{body}"), 0.0).len();
2692        assert_eq!(n(bodies[0]), 100);
2693        assert_eq!(n(bodies[9]), 100);
2694        assert_eq!(n(bodies[11]), 200);
2695    }
2696
2697    /// EXISTS in value position — a BIND, a projected expression, a
2698    /// sub-select's projection, a function's argument, an aggregate's argument,
2699    /// a GROUP BY key, an ORDER BY key — is decided per row against the graph,
2700    /// as it is in a FILTER. It used to be `false` on every row, so
2701    /// `BIND(IF(NOT EXISTS { … }, …))` took the same branch for all of them.
2702    #[test]
2703    fn exists_in_value_position_reads_the_row() {
2704        let rete = people();
2705        let t = "\"true\"^^<http://www.w3.org/2001/XMLSchema#boolean>";
2706        let f = "\"false\"^^<http://www.w3.org/2001/XMLSchema#boolean>";
2707        // p0 has an age (every even person does), p1 has none.
2708        let both = "VALUES ?s { ex:p0 ex:p1 }";
2709        let sols = |body: &str| {
2710            eval_sparql(&rete, &format!("PREFIX ex: <http://ex/> {body}"))
2711                .unwrap()
2712                .1
2713        };
2714        let col = |body: &str, var: &str| -> Vec<String> {
2715            let rows = sols(body);
2716            rows.iter()
2717                .map(|b| b.get(var).cloned().unwrap_or_default())
2718                .collect()
2719        };
2720        for floor in [f64::MAX, 0.0] {
2721            crate::bgp::with_probe_floor(floor, || {
2722                let bind = format!(
2723                    "SELECT ?x WHERE {{ {both} BIND(IF(NOT EXISTS {{ ?s ex:age ?a }}, \"no\", \"yes\") AS ?x) }} ORDER BY ?s"
2724                );
2725                assert_eq!(col(&bind, "x"), ["\"yes\"", "\"no\""]);
2726                let bare =
2727                    format!("SELECT ?x WHERE {{ {both} BIND(EXISTS {{ ?s ex:age ?a }} AS ?x) }} ORDER BY ?s");
2728                assert_eq!(col(&bare, "x"), [t, f]);
2729                let projected = format!(
2730                    "SELECT (NOT EXISTS {{ ?s ex:age ?a }} AS ?x) WHERE {{ {both} }} ORDER BY ?s"
2731                );
2732                assert_eq!(col(&projected, "x"), [f, t]);
2733                let sub = format!(
2734                    "SELECT ?x WHERE {{ {{ SELECT ?s (EXISTS {{ ?s ex:age ?a }} AS ?x) WHERE {{ {both} }} }} }} ORDER BY ?s"
2735                );
2736                assert_eq!(col(&sub, "x"), [t, f]);
2737                let arg = format!(
2738                    "SELECT ?x WHERE {{ {both} BIND(STR(EXISTS {{ ?s ex:age ?a }}) AS ?x) }} ORDER BY ?s"
2739                );
2740                assert_eq!(col(&arg, "x"), ["\"true\"", "\"false\""]);
2741
2742                // 100 of the 200 people have an age.
2743                let sum = "SELECT (SUM(IF(EXISTS { ?s ex:age ?a }, 1, 0)) AS ?with) WHERE { ?s ex:name ?n }";
2744                assert!(
2745                    col(sum, "with")[0].starts_with("\"100\""),
2746                    "{:?}",
2747                    col(sum, "with")
2748                );
2749                let grouped = "SELECT ?e (COUNT(*) AS ?c) WHERE { ?s ex:name ?n } \
2750                               GROUP BY (EXISTS { ?s ex:age ?a } AS ?e) ORDER BY ?e";
2751                assert_eq!(col(grouped, "e"), [f, t]);
2752                assert!(col(grouped, "c").iter().all(|c| c.starts_with("\"100\"")));
2753
2754                // false sorts before true; with a LIMIT the top-k path sorts.
2755                let order =
2756                    format!("SELECT ?s WHERE {{ {both} }} ORDER BY (EXISTS {{ ?s ex:age ?a }})");
2757                assert_eq!(col(&order, "s"), ["<http://ex/p1>", "<http://ex/p0>"]);
2758                assert_eq!(col(&format!("{order} LIMIT 1"), "s"), ["<http://ex/p1>"]);
2759            });
2760        }
2761    }
2762
2763    /// A UNION joined with a small bound side takes that side's bindings into
2764    /// each branch (a `VALUES`, or a preceding pattern): the same rows as
2765    /// evaluating every branch whole.
2766    #[test]
2767    fn a_union_receives_the_bindings_of_the_side_joined_with_it() {
2768        let rete = people();
2769        let pre = "PREFIX ex: <http://ex/> ";
2770        let bodies = [
2771            "SELECT ?r ?p ?v WHERE { VALUES ?r { ex:p1 ex:p2 ex:p3 ex:nobody } \
2772             { ?r ?p ?v } UNION { ?r ex:knows ?n . ?n ?p ?v } }",
2773            "SELECT ?r ?p ?v WHERE { { ?r ?p ?v } UNION { ?r ex:knows ?n . ?n ?p ?v } \
2774             VALUES ?r { ex:p1 ex:p2 ex:p3 } }",
2775            // three branches, one with an unknown constant
2776            "SELECT ?r ?v WHERE { VALUES ?r { ex:p4 ex:p8 } { ?r ex:age ?v } UNION \
2777             { ?r ex:nothere ?v } UNION { ?r ex:knows ?v } }",
2778            // a preceding pattern is the bound side
2779            "SELECT ?x ?v WHERE { ?x ex:age \"4\" . { ?x ex:knows ?v } UNION { ?x ex:name ?v } }",
2780            // a variable only some branches bind
2781            "SELECT ?r ?v ?w WHERE { VALUES ?r { ex:p3 ex:p6 } { ?r ex:knows ?v } UNION \
2782             { ?r ex:age ?w } }",
2783            // UNDEF in the VALUES block: no certain binding, the plain join
2784            "SELECT ?r ?v WHERE { VALUES ?r { ex:p3 UNDEF } { ?r ex:age ?v } UNION { ?r ex:name ?v } }",
2785        ];
2786        for body in bodies {
2787            let q = format!("{pre}{body}");
2788            let whole = rows_at(&rete, &q, f64::MAX);
2789            assert!(!whole.is_empty(), "{body}");
2790            assert_eq!(rows_at(&rete, &q, 0.0), whole, "{body}");
2791        }
2792        // p1: knows, name, type; p2: knows, name, age, type; p3: those and a
2793        // second type = 11 rows from the first branch; the second branch walks
2794        // to p2 (4), p3 (4) and p4 (5: age, a second type).
2795        let q = format!("{pre}{}", bodies[0]);
2796        assert_eq!(rows_at(&rete, &q, 0.0).len(), 11 + 13);
2797    }
2798
2799    /// An unbound class pattern whose subject an earlier pattern binds is
2800    /// probed per subject; the same rows as scanning every type statement.
2801    #[test]
2802    fn an_unbound_class_joined_on_a_bound_subject_probes_per_subject() {
2803        let rete = people();
2804        let pre = "PREFIX ex: <http://ex/> ";
2805        let bodies = [
2806            "SELECT ?s ?c WHERE { ?s ex:age ?a . ?s a ?c }",
2807            "SELECT ?s ?o ?c WHERE { ?s ex:knows ?o . ?o a ?c }",
2808            "SELECT ?c (COUNT(*) AS ?n) WHERE { ?s ex:age ?a . ?s a ?c } GROUP BY ?c",
2809            // a class variable bound on both sides
2810            "SELECT ?s ?c WHERE { ?s ex:knows ?o . ?o a ?c . ?s a ?c }",
2811            // nothing binds the subject: the scan stays
2812            "SELECT ?s ?c WHERE { ?s ?p ?x . ?s a ?c . FILTER(?p = ex:age) }",
2813        ];
2814        for body in bodies {
2815            let q = format!("{pre}{body}");
2816            let whole = rows_at(&rete, &q, f64::MAX);
2817            assert!(!whole.is_empty(), "{body}");
2818            assert_eq!(rows_at(&rete, &q, 0.0), whole, "{body}");
2819        }
2820        // 100 even people; p4 has a second type.
2821        let q = format!("{pre}{}", bodies[0]);
2822        assert_eq!(rows_at(&rete, &q, 0.0).len(), 101);
2823    }
2824
2825    /// A pattern inside `GRAPH <g>` is sized by the graph, not by the file.
2826    #[test]
2827    fn a_named_graph_is_sized_by_its_own_triples() {
2828        use crate::write_dataset_v05 as write_dataset;
2829        let mut db = DictionaryBuilder::new();
2830        let big: Vec<(String, String, String)> = (0..300)
2831            .map(|i| {
2832                (
2833                    format!("<http://ex/s{i}>"),
2834                    "<http://ex/p>".to_string(),
2835                    format!("<http://ex/o{i}>"),
2836                )
2837            })
2838            .collect();
2839        let tiny = (
2840            "<http://ex/s0>".to_string(),
2841            "<http://ex/q>".to_string(),
2842            "<http://ex/o0>".to_string(),
2843        );
2844        for (s, p, o) in big.iter().chain(std::iter::once(&tiny)) {
2845            db.observe(s, p, o);
2846        }
2847        let dict = db.build();
2848        let mut default = GraphIndexBuilder::new();
2849        for (s, p, o) in &big {
2850            default.push(dict.encode(s, p, o).unwrap());
2851        }
2852        let mut small = GraphIndexBuilder::new();
2853        small.push(dict.encode(&tiny.0, &tiny.1, &tiny.2).unwrap());
2854        let named = vec![("<http://ex/g>".to_string(), small.build())];
2855        let bytes = write_dataset(&dict, &default.build(), &named, true, &[], 0);
2856        let rete = Rete::open(&bytes).unwrap();
2857        let g = rete.graph_index("<http://ex/g>").unwrap();
2858        assert_eq!(rete.index_triples(g), 1, "the graph's own count");
2859        assert_eq!(
2860            rete.index_triples(rete.default_index()),
2861            rete.header().quad_count,
2862            "the default graph keeps the file's total"
2863        );
2864        let (_, sols) = eval_sparql(
2865            &rete,
2866            "SELECT ?o WHERE { GRAPH <http://ex/g> { <http://ex/s0> <http://ex/q> ?o } }",
2867        )
2868        .unwrap();
2869        assert_eq!(sols.len(), 1);
2870    }
2871
2872    /// The same, in the quad index: a graph's view takes its quad count from
2873    /// the directory.
2874    #[test]
2875    fn a_quad_index_graph_is_sized_by_its_directory_count() {
2876        use crate::ingest::{assemble_dataset_with_layout, GraphLayout};
2877        let q = |s: &str, g: Option<&str>| -> crate::ingest::RawQuad {
2878            (
2879                format!("<http://ex/{s}>"),
2880                "<http://ex/p>".to_string(),
2881                "<http://ex/o>".to_string(),
2882                g.map(|g| format!("<http://ex/{g}>")),
2883            )
2884        };
2885        let mut quads: Vec<_> = (0..50).map(|i| q(&format!("d{i}"), None)).collect();
2886        quads.extend((0..7).map(|i| q(&format!("a{i}"), Some("ga"))));
2887        quads.extend((0..3).map(|i| q(&format!("b{i}"), Some("gb"))));
2888        let (bytes, _) = assemble_dataset_with_layout(
2889            quads,
2890            false,
2891            false,
2892            None,
2893            crate::pyramid::PyramidAlgo::Louvain,
2894            crate::index::PermSet::ALL,
2895            GraphLayout::Quad,
2896            |_, _| Vec::<u8>::new(),
2897        );
2898        let rete = Rete::open(&bytes).unwrap();
2899        assert_eq!(
2900            rete.index_triples(rete.graph_index("<http://ex/ga>").unwrap()),
2901            7
2902        );
2903        assert_eq!(
2904            rete.index_triples(rete.graph_index("<http://ex/gb>").unwrap()),
2905            3
2906        );
2907        let (_, sols) = eval_sparql(
2908            &rete,
2909            "SELECT ?s WHERE { GRAPH <http://ex/ga> { ?s <http://ex/p> <http://ex/o> . \
2910             FILTER NOT EXISTS { ?s <http://ex/p> <http://ex/zz> } } }",
2911        )
2912        .unwrap();
2913        assert_eq!(sols.len(), 7);
2914    }
2915}