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