Skip to main content

qualia_core_db/sparql_library/
sparql_ast.rs

1//! SPARQL AST - Index-Based Zero-Allocation Query Representation
2//!
3//! Uses u16 indices into flat arrays to avoid Box allocation and recursive type errors.
4//! Fully compliant with AGENTS.md zero-allocation constraints.
5
6pub type PatternId = u16;
7pub type ExpressionId = u16;
8pub type VariableId = u8;
9
10/// Maximum number of patterns in a query context
11pub const MAX_PATTERNS: usize = 128;
12
13/// Maximum number of expressions in a query context
14pub const MAX_EXPRESSIONS: usize = 128;
15
16/// Maximum number of variables per query
17pub const MAX_VARIABLES: usize = 16;
18
19/// Maximum number of bindings per row
20pub const MAX_BINDINGS: usize = 16;
21
22/// Maximum number of order conditions
23pub const MAX_ORDER_CONDITIONS: usize = 16;
24
25/// SPARQL query forms
26#[repr(C)]
27#[derive(Debug, Clone, Copy, PartialEq, Eq)]
28pub enum SparqlQuery {
29    Select(SelectQuery),
30    Ask(AskQuery),
31    Construct(ConstructQuery),
32    Describe(DescribeQuery),
33}
34
35/// SELECT query
36#[repr(C)]
37#[derive(Debug, Clone, Copy, PartialEq, Eq)]
38pub struct SelectQuery {
39    pub distinct: bool,
40    pub reduced: bool,
41    pub variables: [VariableId; MAX_VARIABLES],
42    pub var_count: u8,
43    pub root_pattern: PatternId,
44    pub group_by: [VariableId; MAX_VARIABLES],
45    pub group_by_count: u8,
46    pub aggregates: [crate::sparql_planner::AggregateSpec; 16],
47    pub aggregate_count: u8,
48    pub having: Option<ExpressionId>,
49    pub order_by: [OrderCondition; MAX_ORDER_CONDITIONS],
50    pub order_by_count: u8,
51    pub limit: Option<u64>,
52    pub offset: u64,
53}
54
55impl Default for SelectQuery {
56    fn default() -> Self {
57        Self {
58            distinct: false,
59            reduced: false,
60            variables: [0; MAX_VARIABLES],
61            var_count: 0,
62            root_pattern: 0,
63            group_by: [0; MAX_VARIABLES],
64            group_by_count: 0,
65            aggregates: [crate::sparql_planner::AggregateSpec {
66                func: 0,
67                input_var: 0,
68                output_var: 0,
69            }; 16],
70            aggregate_count: 0,
71            having: None,
72            order_by: [OrderCondition::default(); MAX_ORDER_CONDITIONS],
73            order_by_count: 0,
74            limit: None,
75            offset: 0,
76        }
77    }
78}
79
80/// ASK query
81#[repr(C)]
82#[derive(Debug, Clone, Copy, PartialEq, Eq)]
83pub struct AskQuery {
84    pub root_pattern: PatternId,
85}
86
87/// CONSTRUCT query
88#[repr(C)]
89#[derive(Debug, Clone, Copy, PartialEq, Eq)]
90pub struct ConstructQuery {
91    pub template_pattern: PatternId,
92    pub root_pattern: PatternId,
93    pub group_by: [VariableId; MAX_VARIABLES],
94    pub group_by_count: u8,
95    pub having: Option<ExpressionId>,
96    pub order_by: [OrderCondition; MAX_ORDER_CONDITIONS],
97    pub order_by_count: u8,
98    pub limit: Option<u64>,
99    pub offset: u64,
100}
101
102/// DESCRIBE query
103#[repr(C)]
104#[derive(Debug, Clone, Copy, PartialEq, Eq)]
105pub struct DescribeQuery {
106    pub vars_or_ids: [u64; MAX_VARIABLES],
107    pub var_count: u8,
108    pub root_pattern: Option<PatternId>,
109}
110
111/// Temporal snapshot mode for `AS OF` / `AT TIME` queries.
112///
113/// Used in `Pattern::AsOf` and `PhysicalOperatorType::AsOf` (Phase 4).
114#[repr(u8)]
115#[derive(Debug, Clone, Copy, PartialEq, Eq)]
116pub enum TemporalMode {
117    /// Assertion-time snapshot: include quins with `prov:generatedAtTime ≤ timestamp_ms`.
118    AsOf = 0,
119    /// Valid-time point: include quins where `startedAtTime ≤ t ≤ endedAtTime`.
120    AtTime = 1,
121}
122
123/// Graph pattern - now uses PatternId indices instead of Box
124#[repr(C)]
125#[derive(Debug, Clone, Copy, PartialEq, Eq)]
126pub enum Pattern {
127    /// Basic triple pattern
128    Triple {
129        subject: u64,
130        predicate: u64,
131        object: u64,
132    },
133    /// OPTIONAL pattern - references inner pattern by ID
134    Optional { inner: PatternId },
135    /// UNION pattern - references left and right by IDs
136    Union { left: PatternId, right: PatternId },
137    /// GRAPH pattern - references graph var/IRI and inner pattern
138    Graph {
139        graph_var_or_id: u64,
140        inner: PatternId,
141    },
142    /// FILTER pattern - references pattern to filter and expression
143    Filter {
144        pattern: PatternId,
145        expression: ExpressionId,
146    },
147    /// BIND(expr AS ?var) — extends each solution of `pattern` with `var`
148    /// bound to the value of `expression` (SPARQL 1.1 Extend). If the
149    /// expression errors, `var` is left unbound and the row is kept.
150    Bind {
151        pattern: PatternId,
152        var: VariableId,
153        expression: ExpressionId,
154    },
155    /// MINUS pattern
156    Minus { inner: PatternId },
157    /// Group graph pattern - references range in child array
158    Group { start_idx: u16, len: u16 },
159    /// Property path pattern (SPARQL 1.1)
160    PropertyPath {
161        subject: u64,
162        path: PathId,
163        object: u64,
164    },
165    /// SERVICE pattern (Federated Query with DID)
166    Service {
167        endpoint_did_id: u64, // DID with 0x8 prefix for identity recognition
168        inner_pattern: PatternId,
169    },
170    /// AS OF / AT TIME temporal snapshot (Phase 4, §5).
171    ///
172    /// Wraps `inner` and filters its results to a historical snapshot.
173    /// The executor checks T_CONTEXT PROV-O quins for each bound subject.
174    AsOf {
175        inner: PatternId,
176        timestamp_ms: u64,
177        mode: TemporalMode,
178    },
179    /// RDF-Star quoted triple `<< s p o >> outerP outerO`.
180    StarTriple {
181        inner_subject: u64,
182        inner_predicate: u64,
183        inner_object: u64,
184        outer_predicate: u64,
185        outer_object: u64,
186    },
187    /// Sub-`SELECT` `{ SELECT … WHERE { … } }` — an independently-evaluated
188    /// nested query (index into `SparqlQueryContext::subqueries`) whose projected
189    /// solutions join with the enclosing group. Only the sub-select's SELECT
190    /// variables are visible outside it.
191    SubSelect { query_id: u16 },
192}
193
194/// Property path (SPARQL 1.1)
195#[repr(C)]
196#[derive(Debug, Clone, Copy, PartialEq, Eq)]
197pub enum Path {
198    /// Simple predicate
199    Predicate(u64),
200    /// Inverse predicate (^pred)
201    Inverse(PathId),
202    /// Sequence (pred1/pred2)
203    Sequence { left: PathId, right: PathId },
204    /// Alternation (pred1|pred2)
205    Alternative { left: PathId, right: PathId },
206    /// Zero or more (pred*)
207    ZeroOrMore(PathId),
208    /// One or more (pred+)
209    OneOrMore(PathId),
210    /// Zero or one (pred?)
211    ZeroOrOne(PathId),
212}
213
214pub type PathId = u16;
215
216/// Expression - uses ExpressionId for nested expressions
217#[repr(C)]
218#[derive(Debug, Clone, Copy, PartialEq, Eq)]
219pub enum Expression {
220    /// Variable reference
221    Variable(VariableId),
222    /// Literal value (index into literal table)
223    Literal(u64),
224    /// IRI reference
225    Iri(u64),
226    /// Unary operation
227    UnaryOp { op: UnaryOp, expr: ExpressionId },
228    /// Binary operation
229    BinaryOp {
230        op: BinaryOp,
231        left: ExpressionId,
232        right: ExpressionId,
233    },
234    /// Function call
235    Function {
236        func: Function,
237        args_start: u16,
238        args_len: u16,
239    },
240    /// Subquery
241    Subquery {
242        query_id: u16, // Index into query array
243    },
244    /// Embedded triple (RDF-Star)
245    EmbeddedTriple {
246        subject: u64,
247        predicate: u64,
248        object: u64,
249    },
250    /// `EXISTS { … }` / `NOT EXISTS { … }` — true iff the inner group graph
251    /// pattern has ≥1 solution when the current row's bindings are substituted
252    /// in. `negated` flips the result (NOT EXISTS). Evaluated by the executor
253    /// (it needs graph access), not the pure value evaluator; it is only valid
254    /// in a FILTER/HAVING boolean position.
255    Exists { pattern: PatternId, negated: bool },
256}
257
258/// Unary operators
259#[repr(C)]
260#[derive(Debug, Clone, Copy, PartialEq, Eq)]
261pub enum UnaryOp {
262    Not,
263    Plus,
264    Minus,
265}
266
267/// Binary operators
268#[repr(C)]
269#[derive(Debug, Clone, Copy, PartialEq, Eq)]
270pub enum BinaryOp {
271    Or,
272    And,
273    Equal,
274    NotEqual,
275    LessThan,
276    LessThanOrEqual,
277    GreaterThan,
278    GreaterThanOrEqual,
279    Add,
280    Subtract,
281    Multiply,
282    Divide,
283}
284
285/// Built-in SPARQL functions
286#[repr(C)]
287#[derive(Debug, Clone, Copy, PartialEq, Eq)]
288pub enum Function {
289    Str,
290    Lang,
291    LangMatches,
292    Datatype,
293    Bound,
294    Iri,
295    Uri,
296    Bnode,
297    Rand,
298    Abs,
299    Ceil,
300    Floor,
301    Round,
302    Concat,
303    Substring,
304    Strlen,
305    Ucase,
306    Lcase,
307    EncodeForUri,
308    Contains,
309    VarStarts,
310    VarEnds,
311    StrBefore,
312    StrAfter,
313    Year,
314    Month,
315    Day,
316    Hours,
317    Minutes,
318    Seconds,
319    Timezone,
320    Tz,
321    Now,
322    Uuid,
323    StrUuid,
324    Coalesce,
325    If,
326    StrLang,
327    StrDt,
328    SameTerm,
329    IsIri,
330    IsUri,
331    IsBlank,
332    IsLiteral,
333    IsNumeric,
334    Regex,
335    // SPARQL-Star functions
336    TripleSubject,
337    TriplePredicate,
338    TripleObject,
339    Triple,
340    Custom(u64), // Index into custom function table
341}
342
343/// ORDER BY condition
344#[repr(C)]
345#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
346pub struct OrderCondition {
347    pub ascending: bool,
348    pub expr: ExpressionId,
349}
350
351/// Flat query context arena - pre-allocated, no heap allocation
352#[repr(C)]
353pub struct SparqlQueryContext {
354    /// Flat array of all patterns in the query
355    pub patterns: [Pattern; MAX_PATTERNS],
356    /// Number of patterns currently allocated
357    pub pattern_count: usize,
358    /// Flat array of all expressions in the query
359    pub expressions: [Expression; MAX_EXPRESSIONS],
360    /// Number of expressions currently allocated
361    pub expression_count: usize,
362    /// Flat array of all property paths in the query
363    pub paths: [Path; MAX_PATTERNS],
364    /// Number of paths currently allocated
365    pub path_count: usize,
366    /// Flat array of subqueries (for nested queries)
367    pub subqueries: [SparqlQuery; 16],
368    /// Number of subqueries currently allocated
369    pub subquery_count: usize,
370    /// Variable name to ID mapping (simplified - stores as hash for now)
371    pub variable_hashes: [u64; MAX_VARIABLES],
372    /// Number of variables
373    pub variable_count: usize,
374    /// Argument storage for function calls (flat array)
375    pub function_args: [ExpressionId; 64],
376    /// Number of function args
377    pub function_arg_count: usize,
378}
379
380/// Query-scoped table of literal text (`hash -> string`) built by the parser for
381/// string/geometry constants. It lives **outside** the zero-heap
382/// `SparqlQueryContext` — it is a cold parse/eval-time structure — so functions
383/// that need literal text (`geof:*`, `STR`, `REGEX`, …) can recover it without
384/// putting `String`/`Vec` on the zero-heap execution hot path (CLAUDE.md §6).
385/// Canonical hash for a literal term, distinguishing a plain literal from a
386/// language-tagged or datatype-tagged one (`"x"`, `"x"@en`, and `"x"^^:t` are three
387/// distinct RDF terms). The parser and the [`StringSink`] both use this so a produced
388/// `STRLANG`/`STRDT` term round-trips its tag.
389pub fn literal_term_hash(text: &str, lang: Option<&str>, datatype: Option<&str>) -> u64 {
390    // Share the complete RDF-ingest term for finite typed binary64 constants.
391    // This concerns RDF term identity, not coercion of hash tokens to numbers.
392    if lang.is_none() && datatype == Some(crate::resolver::typed_double::DATATYPE) {
393        if let Some(term) = crate::resolver::typed_double::from_lexical(text) {
394            return crate::resolver::typed_double::token(&term);
395        }
396    }
397    match (lang, datatype) {
398        (None, None) => crate::lexicon::generate_60bit_token(text.as_bytes()),
399        (Some(l), _) => crate::lexicon::generate_60bit_token(format!("{text}@{l}").as_bytes()),
400        (None, Some(d)) => crate::lexicon::generate_60bit_token(format!("{text}^^{d}").as_bytes()),
401    }
402}
403
404/// Query-scoped table of literal text + optional language tag / datatype IRI,
405/// `hash -> (text, lang?, datatype?)`, built by the parser for string/geometry/typed
406/// constants. Lives **outside** the zero-heap `SparqlQueryContext` — a cold
407/// parse/eval-time structure — so builtins (`STR`/`LANG`/`DATATYPE`/`geof:*`/…) recover
408/// what they need without heap on the §6 hot path.
409#[derive(Debug, Default, Clone)]
410pub struct LiteralTable {
411    entries: Vec<(u64, String, Option<String>, Option<String>)>,
412}
413
414impl LiteralTable {
415    /// Creates an empty literal interning table.
416    pub fn new() -> Self {
417        Self::default()
418    }
419    /// Record the text for a plain literal hash (idempotent, no lang/datatype).
420    pub fn intern(&mut self, hash: u64, text: &str) {
421        self.intern_tagged(hash, text, None, None);
422    }
423    /// Record a literal with an optional language tag and/or datatype IRI.
424    pub fn intern_tagged(
425        &mut self,
426        hash: u64,
427        text: &str,
428        lang: Option<&str>,
429        datatype: Option<&str>,
430    ) {
431        if self.entries.iter().any(|(h, ..)| *h == hash) {
432            return;
433        }
434        self.entries.push((
435            hash,
436            text.to_string(),
437            lang.map(str::to_string),
438            datatype.map(str::to_string),
439        ));
440    }
441    /// Resolves a hash to its literal string, or `None`.
442    pub fn resolve(&self, hash: u64) -> Option<&str> {
443        self.entries
444            .iter()
445            .find(|(h, ..)| *h == hash)
446            .map(|(_, s, ..)| s.as_str())
447    }
448    /// The language tag of an interned literal, if it has one.
449    pub fn lang(&self, hash: u64) -> Option<&str> {
450        self.entries
451            .iter()
452            .find(|(h, ..)| *h == hash)
453            .and_then(|(_, _, l, _)| l.as_deref())
454    }
455    /// The datatype IRI of an interned literal, if it was tagged with one.
456    pub fn datatype(&self, hash: u64) -> Option<&str> {
457        self.entries
458            .iter()
459            .find(|(h, ..)| *h == hash)
460            .and_then(|(_, _, _, d)| d.as_deref())
461    }
462    /// Whether this hash names a known (interned) literal.
463    pub fn contains(&self, hash: u64) -> bool {
464        self.entries.iter().any(|(h, ..)| *h == hash)
465    }
466    /// `LiteralTable::len`.
467    pub fn len(&self) -> usize {
468        self.entries.len()
469    }
470    /// `true` when no literals are interned.
471    pub fn is_empty(&self) -> bool {
472        self.entries.is_empty()
473    }
474}
475
476/// Query-scoped sink for strings **produced** by expression evaluation — the result
477/// of `CONCAT`/`SUBSTR`/`UCASE`/…, an `xsd:dateTime` lexical from `NOW`, a `UUID`
478/// string, or a value-producing `BIND`. `EvalResult` only carries a `u64` hash, so a
479/// produced string must be interned somewhere its hash can be resolved again; this is
480/// that table.
481///
482/// It uses interior mutability (`RefCell`) so it can be carried by the `Copy`
483/// [`TextResolver`] and written during evaluation **without** threading `&mut` through
484/// the recursive evaluator. This is the *cold* expression-eval tier (which already
485/// allocates `String`s for text builtins), not the §6 zero-heap hot path, so a small
486/// interning table here does not violate the hot-path invariant.
487#[derive(Debug, Default)]
488pub struct StringSink {
489    produced: std::cell::RefCell<Vec<(u64, String, Option<String>, Option<String>)>>,
490}
491
492impl StringSink {
493    /// Creates an empty string accumulation sink.
494    pub fn new() -> Self {
495        Self::default()
496    }
497    /// Intern a produced plain string, returning its stable content-derived token.
498    /// Deterministic (same text → same token), so repeated/​reordered evaluation of a
499    /// pure builtin is referentially transparent (plan §4.4, QISP-R06).
500    pub fn intern(&self, text: &str) -> u64 {
501        self.intern_tagged(text, None, None)
502    }
503    /// Intern a produced string carrying an optional language tag / datatype IRI
504    /// (`STRLANG`/`STRDT`). The token distinguishes `"x"`, `"x"@en`, `"x"^^:t` via
505    /// [`literal_term_hash`], so `LANG`/`DATATYPE` can read the tag back.
506    pub fn intern_tagged(&self, text: &str, lang: Option<&str>, datatype: Option<&str>) -> u64 {
507        let hash = literal_term_hash(text, lang, datatype);
508        let mut v = self.produced.borrow_mut();
509        if !v.iter().any(|(h, ..)| *h == hash) {
510            v.push((
511                hash,
512                text.to_string(),
513                lang.map(str::to_string),
514                datatype.map(str::to_string),
515            ));
516        }
517        hash
518    }
519    /// Resolve a previously-interned produced string.
520    pub fn resolve(&self, hash: u64) -> Option<String> {
521        self.produced
522            .borrow()
523            .iter()
524            .find(|(h, ..)| *h == hash)
525            .map(|(_, s, ..)| s.clone())
526    }
527    /// The language tag of a produced string term, if any.
528    pub fn lang(&self, hash: u64) -> Option<String> {
529        self.produced
530            .borrow()
531            .iter()
532            .find(|(h, ..)| *h == hash)
533            .and_then(|(_, _, l, _)| l.clone())
534    }
535    /// The datatype IRI of a produced string term, if any.
536    pub fn datatype(&self, hash: u64) -> Option<String> {
537        self.produced
538            .borrow()
539            .iter()
540            .find(|(h, ..)| *h == hash)
541            .and_then(|(_, _, _, d)| d.clone())
542    }
543}
544
545/// Borrowed text resolver threaded into expression evaluation. Resolves a term
546/// hash to its literal text via, in order: the query-scoped `LiteralTable`
547/// (query constants), a [`StringSink`] of values produced during this query, an
548/// optional ingested-data lexicon closure (e.g. wrapping a `Q42LexMmap::lookup_hash`),
549/// and finally the global demo lexicon. Also carries the query-stable `now_ms` clock
550/// and `seed` used by the temporal / `UUID` / `RAND` builtins so their results are
551/// referentially transparent within one query snapshot (plan §4.4). All borrowed — no
552/// per-query heap in the evaluator, so the §6 hot-path invariant holds.
553#[derive(Clone, Copy)]
554pub struct TextResolver<'a> {
555    pub literals: &'a LiteralTable,
556    pub lexicon: Option<&'a dyn Fn(u64) -> Option<String>>,
557    /// Interner for strings produced by evaluation (`CONCAT`, `NOW`, `UUID`, …).
558    pub sink: Option<&'a StringSink>,
559    /// Query-stable wall clock, ms since the Unix epoch. `0` = unset (temporal
560    /// builtins then fail closed rather than fabricate a non-deterministic time).
561    pub now_ms: u64,
562    /// Query-stable RNG seed for `UUID`/`STRUUID`. `0` = unset.
563    pub seed: u64,
564}
565
566impl<'a> TextResolver<'a> {
567    /// Creates a resolver over `literals` with no extra lexicon.
568    pub fn new(literals: &'a LiteralTable) -> Self {
569        Self {
570            literals,
571            lexicon: None,
572            sink: None,
573            now_ms: 0,
574            seed: 0,
575        }
576    }
577    /// Resolver with an additional lexicon consulted after the literal table.
578    pub fn with_lexicon(
579        literals: &'a LiteralTable,
580        lexicon: &'a dyn Fn(u64) -> Option<String>,
581    ) -> Self {
582        Self {
583            literals,
584            lexicon: Some(lexicon),
585            sink: None,
586            now_ms: 0,
587            seed: 0,
588        }
589    }
590    /// Attach a [`StringSink`] so value-producing builtins can intern their results.
591    pub fn with_sink(mut self, sink: &'a StringSink) -> Self {
592        self.sink = Some(sink);
593        self
594    }
595    /// Set the query-stable clock (ms since epoch) and RNG seed used by `NOW`/date
596    /// and `UUID`/`STRUUID`. Both must be query-stable for referential transparency.
597    pub fn with_env(mut self, now_ms: u64, seed: u64) -> Self {
598        self.now_ms = now_ms;
599        self.seed = seed;
600        self
601    }
602    /// Resolve a term hash to its literal text, if known.
603    pub fn resolve_text(&self, hash: u64) -> Option<String> {
604        if let Some(s) = self.literals.resolve(hash) {
605            return Some(s.to_string());
606        }
607        if let Some(sink) = self.sink {
608            if let Some(s) = sink.resolve(hash) {
609                return Some(s);
610            }
611        }
612        if let Some(f) = self.lexicon {
613            if let Some(s) = f(hash) {
614                if let Some((lexical, _)) = crate::resolver::typed_double::decode(&s) {
615                    return Some(lexical.to_owned());
616                }
617                return Some(s);
618            }
619        }
620        crate::resolver::resolve_hash(hash).and_then(|b| String::from_utf8(b.to_vec()).ok())
621    }
622
623    /// The language tag of a literal term (`LANG`). A plain, non-tagged literal has the
624    /// empty tag `""` (correct SPARQL default); `None` only for a term that is not a
625    /// known literal at all.
626    pub fn lang_of(&self, hash: u64) -> Option<String> {
627        if let Some(l) = self.literals.lang(hash) {
628            return Some(l.to_string());
629        }
630        if let Some(sink) = self.sink {
631            if let Some(l) = sink.lang(hash) {
632                return Some(l);
633            }
634        }
635        if let Some(term) = self.lexicon.and_then(|lookup| lookup(hash)) {
636            if crate::resolver::typed_double::has_declared_datatype(&term) {
637                return Some(String::new());
638            }
639        }
640        // A known/resolvable literal with no lang tag → "".
641        if self.literals.contains(hash)
642            || self
643                .sink
644                .map(|s| s.resolve(hash).is_some())
645                .unwrap_or(false)
646            || crate::resolver::classify_inline_literal(hash).is_some()
647        {
648            return Some(String::new());
649        }
650        None
651    }
652
653    /// The datatype IRI of a literal term (`DATATYPE`): an explicit tag, else
654    /// `rdf:langString` for a lang-tagged literal, else the inline-encoded XSD type
655    /// (integer/decimal/double/boolean), else `xsd:string` for a plain known literal.
656    /// `None` for a term that is not a known/typed literal.
657    pub fn datatype_of(&self, hash: u64) -> Option<String> {
658        const XSD_STRING: &str = "http://www.w3.org/2001/XMLSchema#string";
659        const RDF_LANGSTRING: &str = "http://www.w3.org/1999/02/22-rdf-syntax-ns#langString";
660        if let Some(dt) = self.literals.datatype(hash) {
661            return Some(dt.to_string());
662        }
663        if let Some(sink) = self.sink {
664            if let Some(dt) = sink.datatype(hash) {
665                return Some(dt);
666            }
667            if sink.lang(hash).is_some() {
668                return Some(RDF_LANGSTRING.to_string());
669            }
670        }
671        if self.literals.lang(hash).is_some() {
672            return Some(RDF_LANGSTRING.to_string());
673        }
674        if let Some(term) = self.lexicon.and_then(|lookup| lookup(hash)) {
675            if crate::resolver::typed_double::has_declared_datatype(&term) {
676                return Some(crate::resolver::typed_double::DATATYPE.to_owned());
677            }
678        }
679        if let Some(lit) = crate::resolver::classify_inline_literal(hash) {
680            return Some(lit.datatype_iri().to_string());
681        }
682        if self.literals.contains(hash)
683            || self
684                .sink
685                .map(|s| s.resolve(hash).is_some())
686                .unwrap_or(false)
687        {
688            return Some(XSD_STRING.to_string());
689        }
690        None
691    }
692}
693
694impl SparqlQueryContext {
695    /// Creates an empty query context.
696    pub fn new() -> Self {
697        Self {
698            patterns: [Pattern::Triple {
699                subject: 0,
700                predicate: 0,
701                object: 0,
702            }; MAX_PATTERNS],
703            pattern_count: 0,
704            expressions: [Expression::Variable(0); MAX_EXPRESSIONS],
705            expression_count: 0,
706            paths: [Path::Predicate(0); MAX_PATTERNS],
707            path_count: 0,
708            subqueries: [SparqlQuery::Select(SelectQuery {
709                distinct: false,
710                reduced: false,
711                variables: [0; MAX_VARIABLES],
712                var_count: 0,
713                root_pattern: 0,
714                group_by: [0; MAX_VARIABLES],
715                group_by_count: 0,
716                aggregates: [crate::sparql_planner::AggregateSpec {
717                    func: 0,
718                    input_var: 0,
719                    output_var: 0,
720                }; 16],
721                aggregate_count: 0,
722                having: None,
723                order_by: [OrderCondition {
724                    expr: 0,
725                    ascending: true,
726                }; MAX_ORDER_CONDITIONS],
727                order_by_count: 0,
728                limit: None,
729                offset: 0,
730            }); 16],
731            subquery_count: 0,
732            variable_hashes: [0; MAX_VARIABLES],
733            variable_count: 0,
734            function_args: [0; 64],
735            function_arg_count: 0,
736        }
737    }
738
739    /// Allocate a new pattern, returns its ID
740    pub fn alloc_pattern(&mut self, pattern: Pattern) -> Result<PatternId, String> {
741        if self.pattern_count >= MAX_PATTERNS {
742            return Err("Pattern overflow".to_string());
743        }
744        let id = self.pattern_count as PatternId;
745        self.patterns[self.pattern_count] = pattern;
746        self.pattern_count += 1;
747        Ok(id)
748    }
749
750    /// Allocate a new expression, returns its ID
751    pub fn alloc_expression(&mut self, expr: Expression) -> Result<ExpressionId, String> {
752        if self.expression_count >= MAX_EXPRESSIONS {
753            return Err("Expression overflow".to_string());
754        }
755        let id = self.expression_count as ExpressionId;
756        self.expressions[self.expression_count] = expr;
757        self.expression_count += 1;
758        Ok(id)
759    }
760
761    /// Allocate a new property path, returns its ID
762    pub fn alloc_path(&mut self, path: Path) -> Result<PathId, String> {
763        if self.path_count >= MAX_PATTERNS {
764            return Err("Path overflow".to_string());
765        }
766        let id = self.path_count as PathId;
767        self.paths[self.path_count] = path;
768        self.path_count += 1;
769        Ok(id)
770    }
771
772    /// Allocate a new subquery, returns its ID
773    pub fn alloc_subquery(&mut self, query: SparqlQuery) -> Result<u16, String> {
774        if self.subquery_count >= 16 {
775            return Err("Subquery overflow".to_string());
776        }
777        let id = self.subquery_count as u16;
778        self.subqueries[self.subquery_count] = query;
779        self.subquery_count += 1;
780        Ok(id)
781    }
782
783    /// Register a variable name, returns its ID
784    pub fn register_variable(&mut self, name: &str) -> Result<VariableId, String> {
785        if self.variable_count >= MAX_VARIABLES {
786            return Err("Variable overflow".to_string());
787        }
788        let hash = crate::lexicon::generate_60bit_token(name.as_bytes());
789        // Check if variable already exists
790        for (i, var_hash) in self.variable_hashes.iter().enumerate() {
791            if *var_hash == hash {
792                return Ok(i as VariableId);
793            }
794        }
795        let id = self.variable_count as VariableId;
796        self.variable_hashes[self.variable_count] = hash;
797        self.variable_count += 1;
798        Ok(id)
799    }
800
801    /// Reset the context for reuse (clears all allocations)
802    pub fn reset(&mut self) {
803        self.pattern_count = 0;
804        self.expression_count = 0;
805        self.variable_count = 0;
806        self.function_arg_count = 0;
807        self.variable_hashes = [0; MAX_VARIABLES];
808    }
809}
810
811impl Default for SparqlQueryContext {
812    fn default() -> Self {
813        Self::new()
814    }
815}
816
817/// Binding row - stack-allocated row for variable bindings
818#[repr(C)]
819#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
820pub struct BindingRow {
821    /// Slot array - None means unbound
822    pub slots: [Option<u64>; MAX_BINDINGS],
823}
824
825impl BindingRow {
826    /// Creates an empty binding row.
827    pub fn new() -> Self {
828        Self {
829            slots: [None; MAX_BINDINGS],
830        }
831    }
832
833    /// Binds `var_id` to `value`.
834    pub fn set(&mut self, var_id: VariableId, value: u64) {
835        if (var_id as usize) < MAX_BINDINGS {
836            self.slots[var_id as usize] = Some(value);
837        }
838    }
839
840    /// Current binding for `var_id`, or `None`.
841    pub fn get(&self, var_id: VariableId) -> Option<u64> {
842        if (var_id as usize) < MAX_BINDINGS {
843            self.slots[var_id as usize]
844        } else {
845            None
846        }
847    }
848
849    /// Clears all bindings.
850    pub fn clear(&mut self) {
851        self.slots = [None; MAX_BINDINGS];
852    }
853}
854
855impl Default for BindingRow {
856    fn default() -> Self {
857        Self::new()
858    }
859}
860
861/// Physical operator trait for query execution
862pub trait PhysicalOperator {
863    /// Advance to next result, returns true if more results available
864    fn next(&mut self, ctx: &SparqlQueryContext, row: &mut BindingRow) -> bool;
865}
866
867#[cfg(test)]
868mod tests {
869    use super::*;
870
871    #[test]
872    fn test_query_context_allocation() {
873        let mut ctx = SparqlQueryContext::new();
874
875        let pattern = Pattern::Triple {
876            subject: 1,
877            predicate: 2,
878            object: 3,
879        };
880
881        let id = ctx.alloc_pattern(pattern).unwrap();
882        assert_eq!(id, 0);
883        assert_eq!(ctx.pattern_count, 1);
884    }
885
886    #[test]
887    fn test_variable_registration() {
888        let mut ctx = SparqlQueryContext::new();
889
890        let id1 = ctx.register_variable("?x").unwrap();
891        let id2 = ctx.register_variable("?y").unwrap();
892
893        assert_eq!(id1, 0);
894        assert_eq!(id2, 1);
895        assert_eq!(ctx.variable_count, 2);
896    }
897
898    #[test]
899    fn test_variable_duplicate() {
900        let mut ctx = SparqlQueryContext::new();
901
902        let id1 = ctx.register_variable("?x").unwrap();
903        let id2 = ctx.register_variable("?x").unwrap();
904
905        assert_eq!(id1, id2);
906        assert_eq!(ctx.variable_count, 1);
907    }
908
909    #[test]
910    fn test_binding_row() {
911        let mut row = BindingRow::new();
912
913        row.set(0, 42);
914        assert_eq!(row.get(0), Some(42));
915        assert_eq!(row.get(1), None);
916    }
917
918    #[test]
919    fn test_optional_pattern_index() {
920        let mut ctx = SparqlQueryContext::new();
921
922        let inner = Pattern::Triple {
923            subject: 1,
924            predicate: 2,
925            object: 3,
926        };
927        let inner_id = ctx.alloc_pattern(inner).unwrap();
928
929        let optional = Pattern::Optional { inner: inner_id };
930        let optional_id = ctx.alloc_pattern(optional).unwrap();
931
932        assert_eq!(ctx.pattern_count, 2);
933        if let Pattern::Optional { inner } = ctx.patterns[optional_id as usize] {
934            assert_eq!(inner, inner_id);
935        } else {
936            panic!("Expected Optional pattern");
937        }
938    }
939
940    #[test]
941    fn test_union_pattern_index() {
942        let mut ctx = SparqlQueryContext::new();
943
944        let left = Pattern::Triple {
945            subject: 1,
946            predicate: 2,
947            object: 3,
948        };
949        let right = Pattern::Triple {
950            subject: 4,
951            predicate: 5,
952            object: 6,
953        };
954
955        let left_id = ctx.alloc_pattern(left).unwrap();
956        let right_id = ctx.alloc_pattern(right).unwrap();
957
958        let union = Pattern::Union {
959            left: left_id,
960            right: right_id,
961        };
962        let union_id = ctx.alloc_pattern(union).unwrap();
963
964        assert_eq!(ctx.pattern_count, 3);
965        if let Pattern::Union { left, right } = ctx.patterns[union_id as usize] {
966            assert_eq!(left, left_id);
967            assert_eq!(right, right_id);
968        } else {
969            panic!("Expected Union pattern");
970        }
971    }
972}