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