Skip to main content

qualia_core_db/sparql_library/
sparql_executor.rs

1//! SPARQL Physical Query Executor
2//!
3//! Executes query plans against NQuin arrays using zero-allocation patterns.
4
5use crate::lexicon::generate_embedded_triple_id;
6use crate::rdf_star::is_virtual_id;
7use crate::sparql_aggregates::{AggregationContext, GroupKey};
8use crate::sparql_ast::*;
9use crate::sparql_filter::{EvalResult, ExpressionEvaluator};
10use crate::sparql_planner::*;
11use crate::NQuin;
12
13#[cfg(not(target_arch = "wasm32"))]
14mod range_q42_exec {
15    use super::*;
16
17    /// Resume state for a caller-buffered triple-pattern page over a range-backed
18    /// Q42 segment.  It is deliberately separate from the resident executor: no
19    /// graph-sized `Vec<NQuin>` is constructed on this path.
20    #[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
21    pub struct Q42RangeSparqlCursor {
22        pub scan: crate::q42_volume::Q42RangeQueryCursor,
23    }
24
25    #[derive(Clone, Copy, Debug, Eq, PartialEq)]
26    pub struct Q42RangeSparqlPage {
27        pub returned: usize,
28        pub next_cursor: Option<Q42RangeSparqlCursor>,
29    }
30
31    #[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
32    pub struct Q42RangeVolumeSetSparqlCursor {
33        pub scan: crate::q42_volume::Q42VolumeSetQueryCursor,
34    }
35
36    #[derive(Clone, Copy, Debug, Eq, PartialEq)]
37    pub struct Q42RangeVolumeSetSparqlPage {
38        pub returned: usize,
39        pub next_cursor: Option<Q42RangeVolumeSetSparqlCursor>,
40    }
41
42    /// A range-executable subset of a physical plan: one triple pattern with
43    /// optional projection and LIMIT/OFFSET. Unsupported trees are rejected so a
44    /// caller can deliberately choose the resident compatibility executor instead
45    /// of receiving a partial SPARQL result.
46    #[derive(Clone, Copy, Debug, Eq, PartialEq)]
47    pub struct Q42RangeTripleSelectPlan {
48        pub subject: u64,
49        pub predicate: u64,
50        pub object: u64,
51        pub projection: [VariableId; MAX_VARIABLES],
52        pub projection_count: u8,
53        pub filters: [ExpressionId; 8],
54        pub filter_count: u8,
55        pub limit: u64,
56        pub offset: u64,
57    }
58
59    #[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
60    pub struct Q42RangeTripleSelectCursor {
61        pub scan: Q42RangeSparqlCursor,
62        pub skipped: u64,
63        pub emitted: u64,
64    }
65
66    #[derive(Clone, Copy, Debug, Eq, PartialEq)]
67    pub struct Q42RangeTripleSelectPage {
68        pub returned: usize,
69        pub next_cursor: Option<Q42RangeTripleSelectCursor>,
70    }
71
72    #[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
73    pub struct Q42RangeVolumeSetTripleSelectCursor {
74        pub scan: Q42RangeVolumeSetSparqlCursor,
75        pub skipped: u64,
76        pub emitted: u64,
77    }
78
79    #[derive(Clone, Copy, Debug, Eq, PartialEq)]
80    pub struct Q42RangeVolumeSetTripleSelectPage {
81        pub returned: usize,
82        pub next_cursor: Option<Q42RangeVolumeSetTripleSelectCursor>,
83    }
84
85    #[derive(Clone, Copy, Debug, Eq, PartialEq)]
86    pub struct Q42RangeTriplePattern {
87        pub subject: u64,
88        pub predicate: u64,
89        pub object: u64,
90    }
91
92    #[derive(Clone, Copy, Debug, Eq, PartialEq)]
93    pub struct Q42RangeNestedLoopJoinPlan {
94        pub left: Q42RangeTriplePattern,
95        pub right: Q42RangeTriplePattern,
96    }
97
98    #[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
99    pub struct Q42RangeNestedLoopJoinState {
100        pub left_scan: Q42RangeSparqlCursor,
101        pub right_scan: Q42RangeSparqlCursor,
102        pub left_count: usize,
103        pub left_index: usize,
104        pub left_exhausted: bool,
105        pub right_active: bool,
106    }
107
108    #[derive(Clone, Copy, Debug, Eq, PartialEq)]
109    pub struct Q42RangeNestedLoopJoinPage {
110        pub returned: usize,
111        pub done: bool,
112    }
113
114    /// Resumable state for the logical-volume equivalent of
115    /// [`Q42RangeNestedLoopJoinState`].  The cursors include manifest child
116    /// positions, so a join never has to re-open or materialise a volume set.
117    #[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
118    pub struct Q42RangeVolumeSetNestedLoopJoinState {
119        pub left_scan: Q42RangeVolumeSetSparqlCursor,
120        pub right_scan: Q42RangeVolumeSetSparqlCursor,
121        pub left_count: usize,
122        pub left_index: usize,
123        pub left_exhausted: bool,
124        pub right_active: bool,
125    }
126
127    impl Q42RangeNestedLoopJoinPlan {
128        /// Snapshot the join plan from the plan's root operator.
129        pub fn from_execution_plan(plan: &ExecutionPlan) -> Result<Self, String> {
130            Self::from_join_root(plan, plan.root_operator)
131        }
132
133        /// Snapshot the operator subtree reachable from `root`.
134    pub fn from_join_root(plan: &ExecutionPlan, root: OperatorId) -> Result<Self, String> {
135            if plan.operator_count == 0 || root as usize >= plan.operator_count as usize {
136                return Err("range join requires a non-empty execution plan".to_string());
137            }
138            let PhysicalOperatorType::NestedLoopJoin { left, right, .. } =
139                plan.operators[root as usize].operator_type
140            else {
141                return Err("range join currently requires a NestedLoopJoin".to_string());
142            };
143            let triple = |operator: OperatorId| -> Result<Q42RangeTriplePattern, String> {
144                let Some(entry) = plan.operators.get(operator as usize) else {
145                    return Err("range join input operator is out of bounds".to_string());
146                };
147                match entry.operator_type {
148                    PhysicalOperatorType::TripleScan {
149                        subject,
150                        predicate,
151                        object,
152                    } => Ok(Q42RangeTriplePattern {
153                        subject,
154                        predicate,
155                        object,
156                    }),
157                    _ => Err("range join currently requires TripleScan inputs".to_string()),
158                }
159            };
160            Ok(Self {
161                left: triple(left)?,
162                right: triple(right)?,
163            })
164        }
165    }
166
167    /// Execute a bounded page of a two-pattern nested-loop join. `left_rows` and
168    /// `right_rows` remain owned by the caller across invocations; the state holds
169    /// only fixed-size cursors and counts. The output buffer must be at least as
170    /// large as the Quin scratch buffer so no right-page result is dropped.
171    pub fn execute_range_nested_loop_join_page_into<S: crate::q42_volume::Q42RangeSource>(
172        volume: &crate::q42_volume::Q42RangeVolume<S>,
173        plan: Q42RangeNestedLoopJoinPlan,
174        ctx: &SparqlQueryContext,
175        state: &mut Q42RangeNestedLoopJoinState,
176        compressed: &mut [u8],
177        decoded: &mut [u8],
178        quin_scratch: &mut [NQuin],
179        left_rows: &mut [BindingRow],
180        right_rows: &mut [BindingRow],
181        out: &mut [BindingRow],
182    ) -> Result<Q42RangeNestedLoopJoinPage, String> {
183        if quin_scratch.is_empty()
184            || left_rows.len() < quin_scratch.len()
185            || right_rows.len() < quin_scratch.len()
186            || out.len() < quin_scratch.len()
187        {
188            return Err(
189                "range nested-loop join requires row buffers at least as large as Quin scratch"
190                    .to_string(),
191            );
192        }
193        let mut returned = 0usize;
194        loop {
195            if returned + quin_scratch.len() > out.len() {
196                return Ok(Q42RangeNestedLoopJoinPage {
197                    returned,
198                    done: false,
199                });
200            }
201            if state.left_index >= state.left_count {
202                if state.left_exhausted {
203                    return Ok(Q42RangeNestedLoopJoinPage {
204                        returned,
205                        done: true,
206                    });
207                }
208                let page = execute_range_triple_page_into(
209                    volume,
210                    plan.left.subject,
211                    plan.left.predicate,
212                    plan.left.object,
213                    None,
214                    ctx,
215                    &BindingRow::default(),
216                    state.left_scan,
217                    compressed,
218                    decoded,
219                    quin_scratch,
220                    left_rows,
221                )?;
222                state.left_count = page.returned;
223                state.left_index = 0;
224                state.left_scan = page.next_cursor.unwrap_or_default();
225                state.left_exhausted = page.next_cursor.is_none();
226                state.right_active = false;
227                if state.left_count == 0 {
228                    if state.left_exhausted {
229                        return Ok(Q42RangeNestedLoopJoinPage {
230                            returned,
231                            done: true,
232                        });
233                    }
234                    continue;
235                }
236            }
237            let input = left_rows[state.left_index];
238            let page = execute_range_triple_page_into(
239                volume,
240                plan.right.subject,
241                plan.right.predicate,
242                plan.right.object,
243                None,
244                ctx,
245                &input,
246                if state.right_active {
247                    state.right_scan
248                } else {
249                    Q42RangeSparqlCursor::default()
250                },
251                compressed,
252                decoded,
253                quin_scratch,
254                right_rows,
255            )?;
256            out[returned..returned + page.returned].copy_from_slice(&right_rows[..page.returned]);
257            returned += page.returned;
258            match page.next_cursor {
259                Some(next) => {
260                    state.right_scan = next;
261                    state.right_active = true;
262                }
263                None => {
264                    state.left_index += 1;
265                    state.right_scan = Q42RangeSparqlCursor::default();
266                    state.right_active = false;
267                }
268            }
269            if returned + quin_scratch.len() > out.len() {
270                return Ok(Q42RangeNestedLoopJoinPage {
271                    returned,
272                    done: false,
273                });
274            }
275        }
276    }
277
278    /// Execute one bounded page of a two-pattern nested-loop join across a
279    /// manifest-backed Q42 snapshot.  It has the same binding and output contract
280    /// as [`execute_range_nested_loop_join_page_into`], while the child selection
281    /// remains inside `Q42RangeVolumeSet()`.
282    pub fn execute_range_volume_set_nested_loop_join_page_into<
283        S: crate::q42_volume::Q42RangeSource,
284    >(
285        volumes: &crate::q42_volume::Q42RangeVolumeSet<S>,
286        plan: Q42RangeNestedLoopJoinPlan,
287        ctx: &SparqlQueryContext,
288        state: &mut Q42RangeVolumeSetNestedLoopJoinState,
289        compressed: &mut [u8],
290        decoded: &mut [u8],
291        quin_scratch: &mut [NQuin],
292        left_rows: &mut [BindingRow],
293        right_rows: &mut [BindingRow],
294        out: &mut [BindingRow],
295    ) -> Result<Q42RangeNestedLoopJoinPage, String> {
296        if quin_scratch.is_empty()
297            || left_rows.len() < quin_scratch.len()
298            || right_rows.len() < quin_scratch.len()
299            || out.len() < quin_scratch.len()
300        {
301            return Err(
302                "range nested-loop join requires row buffers at least as large as Quin scratch"
303                    .to_string(),
304            );
305        }
306        let mut returned = 0usize;
307        loop {
308            if returned + quin_scratch.len() > out.len() {
309                return Ok(Q42RangeNestedLoopJoinPage {
310                    returned,
311                    done: false,
312                });
313            }
314            if state.left_index >= state.left_count {
315                if state.left_exhausted {
316                    return Ok(Q42RangeNestedLoopJoinPage {
317                        returned,
318                        done: true,
319                    });
320                }
321                let page = execute_range_volume_set_triple_page_into(
322                    volumes,
323                    plan.left.subject,
324                    plan.left.predicate,
325                    plan.left.object,
326                    None,
327                    ctx,
328                    &BindingRow::default(),
329                    state.left_scan,
330                    compressed,
331                    decoded,
332                    quin_scratch,
333                    left_rows,
334                )?;
335                state.left_count = page.returned;
336                state.left_index = 0;
337                state.left_scan = page.next_cursor.unwrap_or_default();
338                state.left_exhausted = page.next_cursor.is_none();
339                state.right_active = false;
340                if state.left_count == 0 {
341                    if state.left_exhausted {
342                        return Ok(Q42RangeNestedLoopJoinPage {
343                            returned,
344                            done: true,
345                        });
346                    }
347                    continue;
348                }
349            }
350            let input = left_rows[state.left_index];
351            let page = execute_range_volume_set_triple_page_into(
352                volumes,
353                plan.right.subject,
354                plan.right.predicate,
355                plan.right.object,
356                None,
357                ctx,
358                &input,
359                if state.right_active {
360                    state.right_scan
361                } else {
362                    Q42RangeVolumeSetSparqlCursor::default()
363                },
364                compressed,
365                decoded,
366                quin_scratch,
367                right_rows,
368            )?;
369            out[returned..returned + page.returned].copy_from_slice(&right_rows[..page.returned]);
370            returned += page.returned;
371            match page.next_cursor {
372                Some(next) => {
373                    state.right_scan = next;
374                    state.right_active = true;
375                }
376                None => {
377                    state.left_index += 1;
378                    state.right_scan = Q42RangeVolumeSetSparqlCursor::default();
379                    state.right_active = false;
380                }
381            }
382            if returned + quin_scratch.len() > out.len() {
383                return Ok(Q42RangeNestedLoopJoinPage {
384                    returned,
385                    done: false,
386                });
387            }
388        }
389    }
390
391    impl Q42RangeTripleSelectPlan {
392        /// Build a range triple-scan plan; requires a non-empty
393        /// execution plan with a valid root operator.
394        pub fn from_execution_plan(plan: &ExecutionPlan) -> Result<Self, String> {
395            if plan.operator_count == 0
396                || plan.root_operator as usize >= plan.operator_count as usize
397            {
398                return Err("range SPARQL requires a non-empty execution plan".to_string());
399            }
400            let mut operator = plan.root_operator;
401            let mut projection = [0; MAX_VARIABLES];
402            let mut projection_count = 0;
403            let mut filters = [0; 8];
404            let mut filter_count = 0usize;
405            let mut limit = u64::MAX;
406            let mut offset = 0;
407            loop {
408                match plan.operators[operator as usize].operator_type {
409                PhysicalOperatorType::Project { input, vars, var_count } => {
410                    if projection_count != 0 { return Err("range SPARQL does not support nested projections".to_string()); }
411                    projection = vars;
412                    projection_count = var_count;
413                    operator = input;
414                }
415                PhysicalOperatorType::Limit { input, limit: configured, offset: configured_offset } => {
416                    if limit != u64::MAX || offset != 0 { return Err("range SPARQL does not support nested limits".to_string()); }
417                    limit = configured;
418                    offset = configured_offset;
419                    operator = input;
420                }
421                PhysicalOperatorType::Filter { input, expression } => {
422                    if filter_count == filters.len() {
423                        return Err("range SPARQL supports at most eight stacked FILTER operators".to_string());
424                    }
425                    filters[filter_count] = expression;
426                    filter_count += 1;
427                    operator = input;
428                }
429                PhysicalOperatorType::TripleScan { subject, predicate, object } => {
430                    return Ok(Self { subject, predicate, object, projection, projection_count, filters, filter_count: filter_count as u8, limit, offset });
431                }
432                _ => return Err("range SPARQL currently supports one TripleScan with optional PROJECT and LIMIT/OFFSET".to_string()),
433            }
434            }
435        }
436    }
437
438    /// Execute one bounded page of a simple SELECT/ASK physical plan.
439    pub fn execute_range_triple_select_page_into<S: crate::q42_volume::Q42RangeSource>(
440        volume: &crate::q42_volume::Q42RangeVolume<S>,
441        plan: Q42RangeTripleSelectPlan,
442        ctx: &SparqlQueryContext,
443        cursor: Q42RangeTripleSelectCursor,
444        compressed: &mut [u8],
445        decoded: &mut [u8],
446        quin_scratch: &mut [NQuin],
447        out: &mut [BindingRow],
448    ) -> Result<Q42RangeTripleSelectPage, String> {
449        let source_page = execute_range_triple_page_into(
450            volume,
451            plan.subject,
452            plan.predicate,
453            plan.object,
454            None,
455            ctx,
456            &BindingRow::default(),
457            cursor.scan,
458            compressed,
459            decoded,
460            quin_scratch,
461            out,
462        )?;
463        let mut returned = 0usize;
464        let mut skipped = cursor.skipped;
465        let mut emitted = cursor.emitted;
466        for index in 0..source_page.returned {
467            let mut accepted = true;
468            for filter in plan.filters.iter().take(plan.filter_count as usize) {
469                if !matches!(
470                    ExpressionEvaluator::evaluate(*filter, ctx, &out[index]),
471                    Ok(EvalResult::Boolean(true))
472                ) {
473                    accepted = false;
474                    break;
475                }
476            }
477            if !accepted {
478                continue;
479            }
480            if skipped < plan.offset {
481                skipped += 1;
482                continue;
483            }
484            if emitted >= plan.limit {
485                return Ok(Q42RangeTripleSelectPage {
486                    returned,
487                    next_cursor: None,
488                });
489            }
490            let mut row = out[index];
491            if plan.projection_count != 0 {
492                let mut projected = BindingRow::default();
493                for variable in plan.projection.iter().take(plan.projection_count as usize) {
494                    if let Some(value) = row.get(*variable) {
495                        projected.set(*variable, value);
496                    }
497                }
498                row = projected;
499            }
500            out[returned] = row;
501            returned += 1;
502            emitted += 1;
503        }
504        Ok(Q42RangeTripleSelectPage {
505            returned,
506            next_cursor: if emitted >= plan.limit {
507                None
508            } else {
509                source_page
510                    .next_cursor
511                    .map(|scan| Q42RangeTripleSelectCursor {
512                        scan,
513                        skipped,
514                        emitted,
515                    })
516            },
517        })
518    }
519
520    /// Execute one bounded page of the same simple SELECT/ASK plan across a
521    /// front-manifested logical Q42 root.
522    pub fn execute_range_volume_set_triple_select_page_into<
523        S: crate::q42_volume::Q42RangeSource,
524    >(
525        volumes: &crate::q42_volume::Q42RangeVolumeSet<S>,
526        plan: Q42RangeTripleSelectPlan,
527        ctx: &SparqlQueryContext,
528        cursor: Q42RangeVolumeSetTripleSelectCursor,
529        compressed: &mut [u8],
530        decoded: &mut [u8],
531        quin_scratch: &mut [NQuin],
532        out: &mut [BindingRow],
533    ) -> Result<Q42RangeVolumeSetTripleSelectPage, String> {
534        let source_page = execute_range_volume_set_triple_page_into(
535            volumes,
536            plan.subject,
537            plan.predicate,
538            plan.object,
539            None,
540            ctx,
541            &BindingRow::default(),
542            cursor.scan,
543            compressed,
544            decoded,
545            quin_scratch,
546            out,
547        )?;
548        let mut returned = 0usize;
549        let mut skipped = cursor.skipped;
550        let mut emitted = cursor.emitted;
551        for index in 0..source_page.returned {
552            let mut accepted = true;
553            for filter in plan.filters.iter().take(plan.filter_count as usize) {
554                if !matches!(
555                    ExpressionEvaluator::evaluate(*filter, ctx, &out[index]),
556                    Ok(EvalResult::Boolean(true))
557                ) {
558                    accepted = false;
559                    break;
560                }
561            }
562            if !accepted {
563                continue;
564            }
565            if skipped < plan.offset {
566                skipped += 1;
567                continue;
568            }
569            if emitted >= plan.limit {
570                return Ok(Q42RangeVolumeSetTripleSelectPage {
571                    returned,
572                    next_cursor: None,
573                });
574            }
575            let mut row = out[index];
576            if plan.projection_count != 0 {
577                let mut projected = BindingRow::default();
578                for variable in plan.projection.iter().take(plan.projection_count as usize) {
579                    if let Some(value) = row.get(*variable) {
580                        projected.set(*variable, value);
581                    }
582                }
583                row = projected;
584            }
585            out[returned] = row;
586            returned += 1;
587            emitted += 1;
588        }
589        Ok(Q42RangeVolumeSetTripleSelectPage {
590            returned,
591            next_cursor: if emitted >= plan.limit {
592                None
593            } else {
594                source_page
595                    .next_cursor
596                    .map(|scan| Q42RangeVolumeSetTripleSelectCursor {
597                        scan,
598                        skipped,
599                        emitted,
600                    })
601            },
602        })
603    }
604
605    /// Execute one physical page of a SPARQL triple pattern against a Q42 range
606    /// source.  Constants and already-bound variables become on-disk filters; a
607    /// bound object selects BIDX pruning automatically. `quin_scratch` and `out`
608    /// are caller-owned, maintaining the zero-heap query kernel contract.
609    pub fn execute_range_triple_page_into<S: crate::q42_volume::Q42RangeSource>(
610        volume: &crate::q42_volume::Q42RangeVolume<S>,
611        subject: u64,
612        predicate: u64,
613        object: u64,
614        context: Option<u64>,
615        ctx: &SparqlQueryContext,
616        input: &BindingRow,
617        cursor: Q42RangeSparqlCursor,
618        compressed: &mut [u8],
619        decoded: &mut [u8],
620        quin_scratch: &mut [NQuin],
621        out: &mut [BindingRow],
622    ) -> Result<Q42RangeSparqlPage, String> {
623        if quin_scratch.is_empty() || out.is_empty() {
624            return Err("range SPARQL page requires non-empty Quin and row buffers".to_string());
625        }
626        let bound = |term: u64| match term_is_var(term, ctx) {
627            Some(variable) => input.get(variable),
628            None => Some(term),
629        };
630        let pattern = crate::q42_volume::Q42RangeQueryPattern {
631            subject: bound(subject),
632            predicate: bound(predicate),
633            object: bound(object),
634            context,
635        };
636        let page = volume
637            .execute_query_page_into(
638                crate::q42_volume::Q42RangeQueryPlan::for_pattern(pattern),
639                cursor.scan,
640                compressed,
641                decoded,
642                quin_scratch,
643            )
644            .map_err(|error| format!("range Q42 triple scan: {error}"))?;
645        let mut returned = 0usize;
646        for quin in &quin_scratch[..page.returned] {
647            let mut row = *input;
648            if !bind_var(&mut row, subject, quin.subject, ctx)
649                || !bind_var(&mut row, predicate, quin.predicate, ctx)
650                || !bind_var(&mut row, object, quin.object, ctx)
651            {
652                continue;
653            }
654            if returned == out.len() {
655                return Err(
656                    "range SPARQL row buffer is smaller than Quin scratch buffer".to_string(),
657                );
658            }
659            out[returned] = row;
660            returned += 1;
661        }
662        Ok(Q42RangeSparqlPage {
663            returned,
664            next_cursor: page.next_cursor.map(|scan| Q42RangeSparqlCursor { scan }),
665        })
666    }
667
668    /// The logical-volume counterpart of [`execute_range_triple_page_into`]. It
669    /// preserves exactly the same SPARQL binding semantics while the root manifest
670    /// prunes child segments before each range-backed SuperBlock scan.
671    pub fn execute_range_volume_set_triple_page_into<S: crate::q42_volume::Q42RangeSource>(
672        volumes: &crate::q42_volume::Q42RangeVolumeSet<S>,
673        subject: u64,
674        predicate: u64,
675        object: u64,
676        context: Option<u64>,
677        ctx: &SparqlQueryContext,
678        input: &BindingRow,
679        cursor: Q42RangeVolumeSetSparqlCursor,
680        compressed: &mut [u8],
681        decoded: &mut [u8],
682        quin_scratch: &mut [NQuin],
683        out: &mut [BindingRow],
684    ) -> Result<Q42RangeVolumeSetSparqlPage, String> {
685        if quin_scratch.is_empty() || out.is_empty() {
686            return Err("range SPARQL page requires non-empty Quin and row buffers".to_string());
687        }
688        let bound = |term: u64| match term_is_var(term, ctx) {
689            Some(variable) => input.get(variable),
690            None => Some(term),
691        };
692        let page = volumes
693            .execute_query_page_into(
694                crate::q42_volume::Q42RangeQueryPlan::for_pattern(
695                    crate::q42_volume::Q42RangeQueryPattern {
696                        subject: bound(subject),
697                        predicate: bound(predicate),
698                        object: bound(object),
699                        context,
700                    },
701                ),
702                cursor.scan,
703                compressed,
704                decoded,
705                quin_scratch,
706            )
707            .map_err(|error| format!("range Q42 volume-set triple scan: {error}"))?;
708        let mut returned = 0usize;
709        for quin in &quin_scratch[..page.returned] {
710            let mut row = *input;
711            if !bind_var(&mut row, subject, quin.subject, ctx)
712                || !bind_var(&mut row, predicate, quin.predicate, ctx)
713                || !bind_var(&mut row, object, quin.object, ctx)
714            {
715                continue;
716            }
717            if returned == out.len() {
718                return Err(
719                    "range SPARQL row buffer is smaller than Quin scratch buffer".to_string(),
720                );
721            }
722            out[returned] = row;
723            returned += 1;
724        }
725        Ok(Q42RangeVolumeSetSparqlPage {
726            returned,
727            next_cursor: page
728                .next_cursor
729                .map(|scan| Q42RangeVolumeSetSparqlCursor { scan }),
730        })
731    }
732} // range_q42_exec — native mmap/HTTP range SPARQL; not on wasm32.
733
734#[cfg(not(target_arch = "wasm32"))]
735pub use range_q42_exec::*;
736
737/// Resolve a term id to a `VariableId` when it names a query
738/// variable; `None` for constants.
739#[inline]
740fn term_is_var(term: u64, ctx: &SparqlQueryContext) -> Option<VariableId> {
741    let id = term as usize;
742    if id < ctx.variable_count {
743        Some(term as VariableId)
744    } else {
745        None
746    }
747}
748
749/// Bind `value` into `row` when `term` is a variable; verify
750/// equality when it's a constant. `false` on binding conflict.
751#[inline]
752fn bind_var(row: &mut BindingRow, term: u64, value: u64, ctx: &SparqlQueryContext) -> bool {
753    if let Some(var) = term_is_var(term, ctx) {
754        match row.get(var) {
755            Some(bound) if bound != value => false,
756            _ => {
757                row.set(var, value);
758                true
759            }
760        }
761    } else {
762        term == value
763    }
764}
765
766/// Query executor
767pub struct QueryExecutor<'a> {
768    pub quins: &'a [NQuin],
769    /// Optional text resolver for literal-text functions (`geof:*`, …). `None`
770    /// on the plain slice path; supplied when a lexicon / query-literal table is
771    /// available so extension functions can recover geometry/string text.
772    resolver: Option<crate::sparql_ast::TextResolver<'a>>,
773}
774
775impl<'a> QueryExecutor<'a> {
776    /// Executor over an in-memory Quin slice.
777    pub fn new(quins: &'a [NQuin]) -> Self {
778        Self {
779            quins,
780            resolver: None,
781        }
782    }
783
784    /// Executor with a text resolver, enabling `geof:*`/text extension functions.
785    pub fn with_resolver(
786        quins: &'a [NQuin],
787        resolver: crate::sparql_ast::TextResolver<'a>,
788    ) -> Self {
789        Self {
790            quins,
791            resolver: Some(resolver),
792        }
793    }
794
795    /// Execute a query plan and return results
796    pub fn execute(
797        &self,
798        plan: &ExecutionPlan,
799        ctx: &SparqlQueryContext,
800    ) -> Result<Vec<BindingRow>, String> {
801        if plan.operator_count == 0 {
802            return Err("Empty execution plan".to_string());
803        }
804        let mut results = Vec::new();
805        let mut row = BindingRow::new();
806
807        if self.execute_operator(plan.root_operator, plan, ctx, &mut row, &mut results)? {
808            return Ok(results);
809        }
810
811        Ok(results)
812    }
813
814    /// Execute ASK query
815    pub fn execute_ask(
816        &self,
817        plan: &ExecutionPlan,
818        ctx: &SparqlQueryContext,
819    ) -> Result<bool, String> {
820        let mut results = Vec::new();
821        let mut row = BindingRow::new();
822
823        self.execute_operator(plan.root_operator, plan, ctx, &mut row, &mut results)?;
824
825        Ok(!results.is_empty())
826    }
827
828    /// Collect the concrete triple patterns of a CONSTRUCT template into `out`
829    /// as `(subject, predicate, object)` term triples (each field still a
830    /// variable id or a constant hash). A template is either a single `Triple`
831    /// or a `Group` of triples; any non-triple child is ignored (a CONSTRUCT
832    /// template is a basic graph pattern, so only triples are meaningful).
833    fn collect_template_triples(
834        pattern_id: PatternId,
835        ctx: &SparqlQueryContext,
836        out: &mut Vec<(u64, u64, u64)>,
837    ) {
838        match ctx.patterns.get(pattern_id as usize) {
839            Some(Pattern::Triple {
840                subject,
841                predicate,
842                object,
843            }) => out.push((*subject, *predicate, *object)),
844            Some(Pattern::Group { start_idx, len }) => {
845                for i in *start_idx..(*start_idx + *len) {
846                    Self::collect_template_triples(i, ctx, out);
847                }
848            }
849            _ => {}
850        }
851    }
852
853    /// Execute a CONSTRUCT query: evaluate the WHERE pattern, then instantiate
854    /// the template for every solution. The returned rows are the constructed
855    /// triples themselves — variable slot 0 = subject, 1 = predicate, 2 = object
856    /// — which is exactly what the N-Triples/XML/JSON graph serialisers read.
857    ///
858    /// A template triple is emitted only when all three of its terms are bound
859    /// (SPARQL 1.1 §16.2.1: a template instantiation with an unbound term
860    /// produces no triple). Duplicate triples are collapsed.
861    pub fn execute_construct(
862        &self,
863        plan: &ExecutionPlan,
864        ctx: &SparqlQueryContext,
865        template_pattern: PatternId,
866    ) -> Result<Vec<BindingRow>, String> {
867        let solutions = self.execute(plan, ctx)?;
868
869        let mut templates: Vec<(u64, u64, u64)> = Vec::new();
870        Self::collect_template_triples(template_pattern, ctx, &mut templates);
871
872        let resolve = |term: u64, row: &BindingRow| -> Option<u64> {
873            match term_is_var(term, ctx) {
874                Some(var) => row.get(var), // unbound → None → triple skipped
875                None => Some(term),        // constant term
876            }
877        };
878
879        let mut seen = std::collections::HashSet::new();
880        let mut out = Vec::new();
881        for sol in &solutions {
882            for &(s, p, o) in &templates {
883                let (sv, pv, ov) = match (resolve(s, sol), resolve(p, sol), resolve(o, sol)) {
884                    (Some(sv), Some(pv), Some(ov)) => (sv, pv, ov),
885                    _ => continue,
886                };
887                if seen.insert((sv, pv, ov)) {
888                    let mut row = BindingRow::new();
889                    row.set(0, sv);
890                    row.set(1, pv);
891                    row.set(2, ov);
892                    out.push(row);
893                }
894            }
895        }
896        Ok(out)
897    }
898
899    /// Execute a DESCRIBE query: build the set of resources to describe (each
900    /// `vars_or_ids` entry is a constant IRI, or a variable bound by the WHERE
901    /// pattern; `DESCRIBE *` with a WHERE describes every value bound in the
902    /// solutions), then emit a Concise Bounded Description — every stored quin
903    /// whose subject is a described resource. Rows carry the triple in slots
904    /// 0/1/2, matching the graph serialisers. Duplicate triples are collapsed.
905    pub fn execute_describe(
906        &self,
907        plan: &ExecutionPlan,
908        ctx: &SparqlQueryContext,
909        describe: &DescribeQuery,
910    ) -> Result<Vec<BindingRow>, String> {
911        // WHERE solutions are only needed (and only valid) when a pattern exists
912        // — a bare `DESCRIBE <iri>` has an empty plan.
913        let solutions = if describe.root_pattern.is_some() {
914            self.execute(plan, ctx)?
915        } else {
916            Vec::new()
917        };
918
919        let mut resources: Vec<u64> = Vec::new();
920        let add = |r: u64, resources: &mut Vec<u64>| {
921            if !resources.contains(&r) {
922                resources.push(r);
923            }
924        };
925
926        if describe.var_count == 0 {
927            // DESCRIBE * — every value bound in the WHERE solutions.
928            for sol in &solutions {
929                for var in 0..ctx.variable_count as VariableId {
930                    if let Some(v) = sol.get(var) {
931                        add(v, &mut resources);
932                    }
933                }
934            }
935        } else {
936            for i in 0..describe.var_count as usize {
937                let term = describe.vars_or_ids[i];
938                match term_is_var(term, ctx) {
939                    Some(var) => {
940                        for sol in &solutions {
941                            if let Some(v) = sol.get(var) {
942                                add(v, &mut resources);
943                            }
944                        }
945                    }
946                    None => add(term, &mut resources),
947                }
948            }
949        }
950
951        let mut seen = std::collections::HashSet::new();
952        let mut out = Vec::new();
953        for &r in &resources {
954            for q in self.quins {
955                if q.subject == r && seen.insert((q.subject, q.predicate, q.object)) {
956                    let mut row = BindingRow::new();
957                    row.set(0, q.subject);
958                    row.set(1, q.predicate);
959                    row.set(2, q.object);
960                    out.push(row);
961                }
962            }
963        }
964        Ok(out)
965    }
966
967    /// Dispatch one plan operator: scans, joins, filters, and
968    /// solution modifiers. Returns `false` when the operator yields
969    /// no rows.
970    fn execute_operator(
971        &self,
972        op_id: OperatorId,
973        plan: &ExecutionPlan,
974        ctx: &SparqlQueryContext,
975        row: &mut BindingRow,
976        results: &mut Vec<BindingRow>,
977    ) -> Result<bool, String> {
978        let operator = plan
979            .operators
980            .get(op_id as usize)
981            .ok_or("Operator ID out of bounds")?;
982
983        match operator.operator_type {
984            PhysicalOperatorType::SubjectScan { subject } => {
985                self.execute_subject_scan(subject, ctx, row, results)
986            }
987            PhysicalOperatorType::PredicateScan { predicate } => {
988                self.execute_predicate_scan(predicate, ctx, row, results)
989            }
990            PhysicalOperatorType::ObjectScan { object } => {
991                self.execute_object_scan(object, ctx, row, results)
992            }
993            PhysicalOperatorType::TripleScan {
994                subject,
995                predicate,
996                object,
997            } => self.execute_triple_scan(subject, predicate, object, ctx, row, results),
998            PhysicalOperatorType::HashJoin {
999                left,
1000                right,
1001                join_var,
1002            } => self.execute_hash_join(left, right, join_var, plan, ctx, row, results),
1003            PhysicalOperatorType::NestedLoopJoin {
1004                left,
1005                right,
1006                join_var,
1007            } => self.execute_nested_loop_join(left, right, join_var, plan, ctx, row, results),
1008            PhysicalOperatorType::Filter { input, expression } => {
1009                self.execute_filter(input, expression, plan, ctx, row, results)
1010            }
1011            PhysicalOperatorType::Bind {
1012                input,
1013                var,
1014                expression,
1015            } => self.execute_bind(input, var, expression, plan, ctx, row, results),
1016            PhysicalOperatorType::Project {
1017                input,
1018                vars,
1019                var_count,
1020            } => self.execute_project(input, vars, var_count, plan, ctx, row, results),
1021            PhysicalOperatorType::Limit {
1022                input,
1023                limit,
1024                offset,
1025            } => self.execute_limit(input, limit, offset, plan, ctx, row, results),
1026            PhysicalOperatorType::Sort {
1027                input,
1028                order_by,
1029                order_count,
1030                ascending,
1031            } => self.execute_sort(
1032                input,
1033                &order_by,
1034                order_count,
1035                &ascending,
1036                plan,
1037                ctx,
1038                row,
1039                results,
1040            ),
1041            PhysicalOperatorType::Union { left, right } => {
1042                self.execute_union(left, right, plan, ctx, row, results)
1043            }
1044            PhysicalOperatorType::Optional { left, right } => {
1045                self.execute_optional(left, right, plan, ctx, row, results)
1046            }
1047            PhysicalOperatorType::AntiJoin { left, right } => {
1048                self.execute_anti_join(left, right, plan, ctx, row, results)
1049            }
1050            PhysicalOperatorType::Distinct { input } => {
1051                self.execute_distinct(input, plan, ctx, row, results)
1052            }
1053            PhysicalOperatorType::SubSelect { query_id } => {
1054                self.execute_sub_select(query_id, ctx, row, results)
1055            }
1056            PhysicalOperatorType::GroupBy {
1057                input,
1058                group_vars,
1059                group_var_count,
1060                aggregates,
1061                aggregate_count,
1062            } => self.execute_group_by(
1063                input,
1064                group_vars,
1065                group_var_count,
1066                aggregates,
1067                aggregate_count,
1068                plan,
1069                ctx,
1070                row,
1071                results,
1072            ),
1073            PhysicalOperatorType::Having { input, expression } => {
1074                self.execute_having(input, expression, plan, ctx, row, results)
1075            }
1076            PhysicalOperatorType::PropertyPath {
1077                subject,
1078                path_id,
1079                object,
1080            } => self.execute_property_path(subject, path_id, object, ctx, row, results),
1081            PhysicalOperatorType::Graph {
1082                graph_var_or_id,
1083                inner,
1084            } => self.execute_graph(graph_var_or_id, inner, plan, ctx, row, results),
1085            PhysicalOperatorType::Service {
1086                endpoint_did_id,
1087                inner_pattern,
1088            } => self.execute_service(endpoint_did_id, inner_pattern, plan, ctx, row, results),
1089            PhysicalOperatorType::AsOf {
1090                input,
1091                timestamp_ms,
1092                mode,
1093            } => self.execute_as_of(input, timestamp_ms, mode, plan, ctx, row, results),
1094            PhysicalOperatorType::StarTripleScan {
1095                inner_subject,
1096                inner_predicate,
1097                inner_object,
1098                outer_predicate,
1099                outer_object,
1100            } => self.execute_star_triple_scan(
1101                inner_subject,
1102                inner_predicate,
1103                inner_object,
1104                outer_predicate,
1105                outer_object,
1106                ctx,
1107                row,
1108                results,
1109            ),
1110        }
1111    }
1112
1113    /// Scan quins by subject term; bind remaining pattern variables.
1114    fn execute_subject_scan(
1115        &self,
1116        subject: u64,
1117        _ctx: &SparqlQueryContext,
1118        _row: &mut BindingRow,
1119        results: &mut Vec<BindingRow>,
1120    ) -> Result<bool, String> {
1121        // Scan all quins matching the subject
1122        for quin in self.quins {
1123            if quin.subject == subject {
1124                // Bind the subject if it's a variable
1125                // For now, just add the quin to results
1126                let mut new_row = BindingRow::new();
1127                new_row.slots[0] = Some(quin.subject);
1128                new_row.slots[1] = Some(quin.predicate);
1129                new_row.slots[2] = Some(quin.object);
1130                results.push(new_row);
1131            }
1132        }
1133        Ok(!results.is_empty())
1134    }
1135
1136    /// Scan quins by predicate term; bind remaining pattern
1137    /// variables.
1138    fn execute_predicate_scan(
1139        &self,
1140        predicate: u64,
1141        _ctx: &SparqlQueryContext,
1142        _row: &mut BindingRow,
1143        results: &mut Vec<BindingRow>,
1144    ) -> Result<bool, String> {
1145        for quin in self.quins {
1146            if quin.predicate == predicate {
1147                let mut new_row = BindingRow::new();
1148                new_row.slots[0] = Some(quin.subject);
1149                new_row.slots[1] = Some(quin.predicate);
1150                new_row.slots[2] = Some(quin.object);
1151                results.push(new_row);
1152            }
1153        }
1154        Ok(!results.is_empty())
1155    }
1156
1157    /// Scan quins by object term; bind remaining pattern variables.
1158    fn execute_object_scan(
1159        &self,
1160        object: u64,
1161        _ctx: &SparqlQueryContext,
1162        _row: &mut BindingRow,
1163        results: &mut Vec<BindingRow>,
1164    ) -> Result<bool, String> {
1165        for quin in self.quins {
1166            if quin.object == object {
1167                let mut new_row = BindingRow::new();
1168                new_row.slots[0] = Some(quin.subject);
1169                new_row.slots[1] = Some(quin.predicate);
1170                new_row.slots[2] = Some(quin.object);
1171                results.push(new_row);
1172            }
1173        }
1174        Ok(!results.is_empty())
1175    }
1176
1177    /// Full triple-pattern scan — match s/p/o constants, bind
1178    /// variables, honour context constraints.
1179    fn execute_triple_scan(
1180        &self,
1181        subject: u64,
1182        predicate: u64,
1183        object: u64,
1184        ctx: &SparqlQueryContext,
1185        row: &mut BindingRow,
1186        results: &mut Vec<BindingRow>,
1187    ) -> Result<bool, String> {
1188        for quin in self.quins {
1189            let mut candidate = *row;
1190            if !bind_var(&mut candidate, subject, quin.subject, ctx) {
1191                continue;
1192            }
1193            if !bind_var(&mut candidate, predicate, quin.predicate, ctx) {
1194                continue;
1195            }
1196            if !bind_var(&mut candidate, object, quin.object, ctx) {
1197                continue;
1198            }
1199            results.push(candidate);
1200        }
1201        Ok(!results.is_empty())
1202    }
1203
1204    /// RDF-Star triple scan — resolve embedded-triple virtual ids
1205    /// via the lexicon before binding.
1206    fn execute_star_triple_scan(
1207        &self,
1208        inner_subject: u64,
1209        inner_predicate: u64,
1210        inner_object: u64,
1211        outer_predicate: u64,
1212        outer_object: u64,
1213        ctx: &SparqlQueryContext,
1214        row: &mut BindingRow,
1215        results: &mut Vec<BindingRow>,
1216    ) -> Result<bool, String> {
1217        for quin in self.quins {
1218            if !is_virtual_id(quin.subject) {
1219                continue;
1220            }
1221            let mut candidate = *row;
1222            if !bind_var(&mut candidate, outer_predicate, quin.predicate, ctx) {
1223                continue;
1224            }
1225            if !bind_var(&mut candidate, outer_object, quin.object, ctx) {
1226                continue;
1227            }
1228
1229            if let (Some(s), Some(p), Some(o)) = (
1230                term_is_var(inner_subject, ctx),
1231                term_is_var(inner_predicate, ctx),
1232                term_is_var(inner_object, ctx),
1233            ) {
1234                if let Some(components) = self.lookup_star_components(quin.subject) {
1235                    candidate.set(s, components[0]);
1236                    candidate.set(p, components[1]);
1237                    candidate.set(o, components[2]);
1238                    results.push(candidate);
1239                }
1240            } else {
1241                let expected_vid = generate_embedded_triple_id(
1242                    if term_is_var(inner_subject, ctx).is_some() {
1243                        0
1244                    } else {
1245                        inner_subject
1246                    },
1247                    if term_is_var(inner_predicate, ctx).is_some() {
1248                        0
1249                    } else {
1250                        inner_predicate
1251                    },
1252                    if term_is_var(inner_object, ctx).is_some() {
1253                        0
1254                    } else {
1255                        inner_object
1256                    },
1257                );
1258                if quin.subject == expected_vid
1259                    && bind_var(&mut candidate, outer_predicate, quin.predicate, ctx)
1260                    && bind_var(&mut candidate, outer_object, quin.object, ctx)
1261                {
1262                    results.push(candidate);
1263                }
1264            }
1265        }
1266        Ok(!results.is_empty())
1267    }
1268
1269    /// Look up the [s,p,o] components of an embedded-triple virtual
1270    /// id in the Q42 lexicon.
1271    fn lookup_star_components(&self, virtual_id: u64) -> Option<[u64; 3]> {
1272        for quin in self.quins {
1273            let candidate = generate_embedded_triple_id(quin.subject, quin.predicate, quin.object);
1274            if candidate == virtual_id {
1275                return Some([quin.subject, quin.predicate, quin.object]);
1276            }
1277        }
1278        None
1279    }
1280
1281    /// Hash join on shared variable slots — build side hashed, probe
1282    /// side streamed.
1283    fn execute_hash_join(
1284        &self,
1285        left: OperatorId,
1286        right: OperatorId,
1287        join_var: VariableId,
1288        plan: &ExecutionPlan,
1289        ctx: &SparqlQueryContext,
1290        _row: &mut BindingRow,
1291        results: &mut Vec<BindingRow>,
1292    ) -> Result<bool, String> {
1293        let mut left_results = Vec::new();
1294        let mut left_row = BindingRow::new();
1295        self.execute_operator(left, plan, ctx, &mut left_row, &mut left_results)?;
1296
1297        let mut right_results = Vec::new();
1298        let mut right_row = BindingRow::new();
1299        self.execute_operator(right, plan, ctx, &mut right_row, &mut right_results)?;
1300
1301        // Zero-allocation Merge Join (O(N log N) + O(M log M))
1302        left_results
1303            .sort_unstable_by(|a, b| a.slots[join_var as usize].cmp(&b.slots[join_var as usize]));
1304        right_results
1305            .sort_unstable_by(|a, b| a.slots[join_var as usize].cmp(&b.slots[join_var as usize]));
1306
1307        let mut i = 0;
1308        let mut j = 0;
1309
1310        while i < left_results.len() && j < right_results.len() {
1311            let left_val = left_results[i].slots[join_var as usize];
1312            let right_val = right_results[j].slots[join_var as usize];
1313
1314            // If join_var is None on either side, it conceptually matches anything.
1315            // However, in BGP joins, join variables are practically always bound.
1316            // If they are unbound, we fall back to nested loop for those specific rows (not implemented here,
1317            // assume BGP variables are bound).
1318            if left_val < right_val {
1319                i += 1;
1320            } else if left_val > right_val {
1321                j += 1;
1322            } else {
1323                let mut left_end = i + 1;
1324                while left_end < left_results.len()
1325                    && left_results[left_end].slots[join_var as usize] == left_val
1326                {
1327                    left_end += 1;
1328                }
1329
1330                let mut right_end = j + 1;
1331                while right_end < right_results.len()
1332                    && right_results[right_end].slots[join_var as usize] == right_val
1333                {
1334                    right_end += 1;
1335                }
1336
1337                for l in &left_results[i..left_end] {
1338                    for r in &right_results[j..right_end] {
1339                        let mut compatible = true;
1340                        for k in 0..MAX_BINDINGS {
1341                            if let (Some(a), Some(b)) = (l.slots[k], r.slots[k]) {
1342                                if a != b {
1343                                    compatible = false;
1344                                    break;
1345                                }
1346                            }
1347                        }
1348
1349                        if compatible {
1350                            let mut joined = BindingRow::new();
1351                            for k in 0..MAX_BINDINGS {
1352                                joined.slots[k] = l.slots[k].or(r.slots[k]);
1353                            }
1354                            results.push(joined);
1355                        }
1356                    }
1357                }
1358
1359                i = left_end;
1360                j = right_end;
1361            }
1362        }
1363
1364        Ok(!results.is_empty())
1365    }
1366
1367    /// Nested-loop join — for each left row, re-execute the right
1368    /// operand under its bindings (supports range-page resume).
1369    fn execute_nested_loop_join(
1370        &self,
1371        left: OperatorId,
1372        right: OperatorId,
1373        _join_var: VariableId,
1374        plan: &ExecutionPlan,
1375        ctx: &SparqlQueryContext,
1376        _row: &mut BindingRow,
1377        results: &mut Vec<BindingRow>,
1378    ) -> Result<bool, String> {
1379        let mut left_results = Vec::new();
1380        let mut left_row = BindingRow::new();
1381        self.execute_operator(left, plan, ctx, &mut left_row, &mut left_results)?;
1382
1383        let mut right_results = Vec::new();
1384        let mut right_row = BindingRow::new();
1385        self.execute_operator(right, plan, ctx, &mut right_row, &mut right_results)?;
1386
1387        // Full Cross-Product with Compatibility Check
1388        for l in &left_results {
1389            for r in &right_results {
1390                let mut compatible = true;
1391                for i in 0..MAX_BINDINGS {
1392                    if let (Some(a), Some(b)) = (l.slots[i], r.slots[i]) {
1393                        if a != b {
1394                            compatible = false;
1395                            break;
1396                        }
1397                    }
1398                }
1399
1400                if compatible {
1401                    let mut joined = BindingRow::new();
1402                    for i in 0..MAX_BINDINGS {
1403                        joined.slots[i] = l.slots[i].or(r.slots[i]);
1404                    }
1405                    results.push(joined);
1406                }
1407            }
1408        }
1409
1410        Ok(!results.is_empty())
1411    }
1412
1413    /// FILTER — evaluate the expression per row, keep passing rows.
1414    fn execute_filter(
1415        &self,
1416        input: OperatorId,
1417        expression: ExpressionId,
1418        plan: &ExecutionPlan,
1419        ctx: &SparqlQueryContext,
1420        row: &mut BindingRow,
1421        results: &mut Vec<BindingRow>,
1422    ) -> Result<bool, String> {
1423        let mut input_results = Vec::new();
1424        self.execute_operator(input, plan, ctx, row, &mut input_results)?;
1425
1426        // Filter results based on expression evaluation. `eval_filter_bool`
1427        // handles FILTER (NOT) EXISTS in boolean position and delegates pure
1428        // value expressions to the expression evaluator.
1429        for input_row in input_results {
1430            if self.eval_filter_bool(expression, ctx, &input_row)? {
1431                results.push(input_row);
1432            }
1433        }
1434
1435        Ok(!results.is_empty())
1436    }
1437
1438    /// True iff the expression subtree contains an `EXISTS`/`NOT EXISTS` node
1439    /// (walking the boolean-combinator arms only — enough to route `&&`/`||`/`!`
1440    /// through `eval_filter_bool`; an EXISTS anywhere else falls through to the
1441    /// value evaluator, which rejects it honestly).
1442    fn expr_contains_exists(expr_id: ExpressionId, ctx: &SparqlQueryContext) -> bool {
1443        match ctx.expressions.get(expr_id as usize) {
1444            Some(Expression::Exists { .. }) => true,
1445            Some(Expression::UnaryOp { expr, .. }) => Self::expr_contains_exists(*expr, ctx),
1446            Some(Expression::BinaryOp { left, right, .. }) => {
1447                Self::expr_contains_exists(*left, ctx) || Self::expr_contains_exists(*right, ctx)
1448            }
1449            _ => false,
1450        }
1451    }
1452
1453    /// Evaluate `EXISTS { pattern }` for the current row: plan the inner group,
1454    /// execute it seeded with the row's bindings (pre-bound variables act as the
1455    /// SPARQL substitution μ), and report whether ≥1 solution exists.
1456    fn eval_exists(
1457        &self,
1458        pattern: PatternId,
1459        ctx: &SparqlQueryContext,
1460        row: &BindingRow,
1461    ) -> Result<bool, String> {
1462        let mut sub_plan = ExecutionPlan::new();
1463        let op = QueryPlanner::plan_pattern(pattern, ctx, &mut sub_plan)?;
1464        sub_plan.root_operator = op;
1465        let mut seed = *row;
1466        let mut local = Vec::new();
1467        self.execute_operator(op, &sub_plan, ctx, &mut seed, &mut local)?;
1468        Ok(!local.is_empty())
1469    }
1470
1471    /// Evaluate a FILTER/HAVING constraint to a boolean, resolving `EXISTS`/`NOT
1472    /// EXISTS` (which need graph access) at the top level and within `&&`/`||`/`!`
1473    /// combinators, and delegating everything else to the value evaluator.
1474    fn eval_filter_bool(
1475        &self,
1476        expr_id: ExpressionId,
1477        ctx: &SparqlQueryContext,
1478        row: &BindingRow,
1479    ) -> Result<bool, String> {
1480        let expr = *ctx
1481            .expressions
1482            .get(expr_id as usize)
1483            .ok_or("Expression ID out of bounds")?;
1484        match expr {
1485            Expression::Exists { pattern, negated } => {
1486                Ok(self.eval_exists(pattern, ctx, row)? ^ negated)
1487            }
1488            Expression::UnaryOp {
1489                op: UnaryOp::Not,
1490                expr,
1491            } if Self::expr_contains_exists(expr, ctx) => {
1492                Ok(!self.eval_filter_bool(expr, ctx, row)?)
1493            }
1494            Expression::BinaryOp {
1495                op: BinaryOp::And,
1496                left,
1497                right,
1498            } if Self::expr_contains_exists(left, ctx)
1499                || Self::expr_contains_exists(right, ctx) =>
1500            {
1501                Ok(self.eval_filter_bool(left, ctx, row)?
1502                    && self.eval_filter_bool(right, ctx, row)?)
1503            }
1504            Expression::BinaryOp {
1505                op: BinaryOp::Or,
1506                left,
1507                right,
1508            } if Self::expr_contains_exists(left, ctx)
1509                || Self::expr_contains_exists(right, ctx) =>
1510            {
1511                Ok(self.eval_filter_bool(left, ctx, row)?
1512                    || self.eval_filter_bool(right, ctx, row)?)
1513            }
1514            _ => {
1515                let r =
1516                    ExpressionEvaluator::evaluate_with_resolver(expr_id, ctx, row, self.resolver)?;
1517                Ok(r.as_bool())
1518            }
1519        }
1520    }
1521
1522    /// BIND — evaluate the expression and assign it to the target
1523    /// variable slot in each row.
1524    fn execute_bind(
1525        &self,
1526        input: OperatorId,
1527        var: VariableId,
1528        expression: ExpressionId,
1529        plan: &ExecutionPlan,
1530        ctx: &SparqlQueryContext,
1531        row: &mut BindingRow,
1532        results: &mut Vec<BindingRow>,
1533    ) -> Result<bool, String> {
1534        let mut input_results = Vec::new();
1535        self.execute_operator(input, plan, ctx, row, &mut input_results)?;
1536
1537        for mut input_row in input_results {
1538            // SPARQL 1.1 Extend: bind `var` to the value of the expression,
1539            // keeping every row. If the expression raises an error (e.g. a
1540            // not-yet-implemented string-producing builtin, or a type error),
1541            // the variable is simply left UNBOUND rather than failing the whole
1542            // query. Value-producing results (numeric / term / boolean /
1543            // already-interned string) map to the row's u64 slot.
1544            match ExpressionEvaluator::evaluate_with_resolver(
1545                expression,
1546                ctx,
1547                &input_row,
1548                self.resolver,
1549            ) {
1550                Ok(EvalResult::Numeric(n)) | Ok(EvalResult::Iri(n)) | Ok(EvalResult::String(n)) => {
1551                    input_row.set(var, n);
1552                }
1553                Ok(EvalResult::Boolean(b)) => {
1554                    input_row.set(var, b as u64);
1555                }
1556                Ok(EvalResult::Float(f)) => {
1557                    // BIND of a real value: store the IEEE-754 bit pattern in the u64 slot.
1558                    input_row.set(var, f.to_bits());
1559                }
1560                Err(_) => { /* expression error → leave `var` unbound */ }
1561            }
1562            results.push(input_row);
1563        }
1564
1565        Ok(!results.is_empty())
1566    }
1567
1568    /// PROJECT — keep only the listed variable slots in each row.
1569    fn execute_project(
1570        &self,
1571        input: OperatorId,
1572        vars: [VariableId; MAX_VARIABLES],
1573        var_count: u8,
1574        plan: &ExecutionPlan,
1575        ctx: &SparqlQueryContext,
1576        row: &mut BindingRow,
1577        results: &mut Vec<BindingRow>,
1578    ) -> Result<bool, String> {
1579        // Project each solution onto the selected variables only, dropping every
1580        // other binding. This is required for correctness — a downstream DISTINCT
1581        // must dedup on the *projected* columns, not on the full WHERE row (two
1582        // solutions identical in ?a but differing in an unselected ?b are one
1583        // DISTINCT ?a result). Variables keep their own slot ids (the serialiser
1584        // reads by variable id from the SELECT list).
1585        let mut input_results = Vec::new();
1586        self.execute_operator(input, plan, ctx, row, &mut input_results)?;
1587        for in_row in input_results {
1588            let mut projected = BindingRow::new();
1589            for &v in vars.iter().take(var_count as usize) {
1590                if let Some(val) = in_row.get(v) {
1591                    projected.set(v, val);
1592                }
1593            }
1594            results.push(projected);
1595        }
1596        Ok(!results.is_empty())
1597    }
1598
1599    /// LIMIT/OFFSET — truncate the result set.
1600    fn execute_limit(
1601        &self,
1602        input: OperatorId,
1603        limit: u64,
1604        offset: u64,
1605        plan: &ExecutionPlan,
1606        ctx: &SparqlQueryContext,
1607        row: &mut BindingRow,
1608        results: &mut Vec<BindingRow>,
1609    ) -> Result<bool, String> {
1610        let mut all_results = Vec::new();
1611        self.execute_operator(input, plan, ctx, row, &mut all_results)?;
1612
1613        // Apply offset and limit
1614        let start = offset as usize;
1615        let end = if limit == u64::MAX {
1616            all_results.len()
1617        } else {
1618            (start + limit as usize).min(all_results.len())
1619        };
1620
1621        if start < all_results.len() {
1622            results.extend_from_slice(&all_results[start..end]);
1623        }
1624
1625        Ok(!results.is_empty())
1626    }
1627
1628    /// ORDER BY — sort rows on the sort-key slots (stable,
1629    /// deterministic tie-break).
1630    fn execute_sort(
1631        &self,
1632        input: OperatorId,
1633        order_by: &[ExpressionId; MAX_ORDER_CONDITIONS],
1634        order_count: u8,
1635        ascending: &[bool; MAX_ORDER_CONDITIONS],
1636        plan: &ExecutionPlan,
1637        ctx: &SparqlQueryContext,
1638        row: &mut BindingRow,
1639        results: &mut Vec<BindingRow>,
1640    ) -> Result<bool, String> {
1641        let start_len = results.len();
1642        self.execute_operator(input, plan, ctx, row, results)?;
1643
1644        // Sort in-place using the order_by expressions
1645        let slice = &mut results[start_len..];
1646
1647        slice.sort_unstable_by(|a, b| {
1648            for i in 0..order_count as usize {
1649                let expr = order_by[i];
1650                let asc = ascending[i];
1651
1652                let val_a =
1653                    ExpressionEvaluator::evaluate_with_resolver(expr, ctx, a, self.resolver)
1654                        .unwrap_or(crate::sparql_filter::EvalResult::Numeric(0));
1655                let val_b =
1656                    ExpressionEvaluator::evaluate_with_resolver(expr, ctx, b, self.resolver)
1657                        .unwrap_or(crate::sparql_filter::EvalResult::Numeric(0));
1658
1659                let cmp = val_a.total_cmp(&val_b);
1660                if cmp != std::cmp::Ordering::Equal {
1661                    return if asc { cmp } else { cmp.reverse() };
1662                }
1663            }
1664            std::cmp::Ordering::Equal
1665        });
1666
1667        Ok(!results.is_empty())
1668    }
1669
1670    /// UNION — concatenate both operands' result rows.
1671    fn execute_union(
1672        &self,
1673        left: OperatorId,
1674        right: OperatorId,
1675        plan: &ExecutionPlan,
1676        ctx: &SparqlQueryContext,
1677        row: &mut BindingRow,
1678        results: &mut Vec<BindingRow>,
1679    ) -> Result<bool, String> {
1680        let _start_len = results.len();
1681
1682        // Execute left
1683        self.execute_operator(left, plan, ctx, row, results)?;
1684
1685        // Execute right
1686        self.execute_operator(right, plan, ctx, row, results)?;
1687
1688        // SPARQL UNION is a multiset union (bag union), so no deduplication is needed.
1689
1690        Ok(!results.is_empty())
1691    }
1692
1693    /// OPTIONAL / left join — emit left rows with right-side
1694    /// bindings where they join, unbound otherwise.
1695    fn execute_optional(
1696        &self,
1697        left: OperatorId,
1698        right: OperatorId,
1699        plan: &ExecutionPlan,
1700        ctx: &SparqlQueryContext,
1701        row: &mut BindingRow,
1702        results: &mut Vec<BindingRow>,
1703    ) -> Result<bool, String> {
1704        // Execute left pattern
1705        let mut left_results = Vec::new();
1706        let mut right_results = Vec::new();
1707        self.execute_operator(left, plan, ctx, row, &mut left_results)?;
1708
1709        // For each left result, try to execute right pattern
1710        for left_result in left_results {
1711            right_results.clear();
1712            let mut right_row = left_result; // Copy left bindings
1713            let right_matched =
1714                self.execute_operator(right, plan, ctx, &mut right_row, &mut right_results)?;
1715
1716            if right_matched && !right_results.is_empty() {
1717                // Right pattern matched - combine bindings
1718                results.extend_from_slice(&right_results);
1719            } else {
1720                // Right pattern didn't match - keep left result with NULL for right variables
1721                results.push(left_result);
1722            }
1723        }
1724
1725        Ok(!results.is_empty())
1726    }
1727
1728    /// SPARQL 1.1 MINUS (anti-join). Both sides are evaluated; a left solution
1729    /// is removed iff some right solution is **compatible** with it AND the two
1730    /// **share at least one bound variable** (the domain-intersection rule that
1731    /// distinguishes MINUS from NOT EXISTS — MINUS over disjoint domains removes
1732    /// nothing).
1733    fn execute_anti_join(
1734        &self,
1735        left: OperatorId,
1736        right: OperatorId,
1737        plan: &ExecutionPlan,
1738        ctx: &SparqlQueryContext,
1739        row: &mut BindingRow,
1740        results: &mut Vec<BindingRow>,
1741    ) -> Result<bool, String> {
1742        let mut left_results = Vec::new();
1743        self.execute_operator(left, plan, ctx, row, &mut left_results)?;
1744
1745        // The right side is evaluated independently (fresh bindings).
1746        let mut right_results = Vec::new();
1747        let mut right_row = BindingRow::new();
1748        self.execute_operator(right, plan, ctx, &mut right_row, &mut right_results)?;
1749
1750        for l in left_results {
1751            let excluded = right_results.iter().any(|r| {
1752                let mut compatible = true;
1753                let mut shares = false;
1754                for k in 0..MAX_BINDINGS {
1755                    if let (Some(a), Some(b)) = (l.slots[k], r.slots[k]) {
1756                        shares = true;
1757                        if a != b {
1758                            compatible = false;
1759                            break;
1760                        }
1761                    }
1762                }
1763                compatible && shares
1764            });
1765            if !excluded {
1766                results.push(l);
1767            }
1768        }
1769
1770        Ok(!results.is_empty())
1771    }
1772
1773    /// Execute a sub-`SELECT`: evaluate the stored subquery independently, then
1774    /// join each of its projected solutions with the current bindings on shared
1775    /// variables (a solution incompatible on any shared, differently-bound
1776    /// variable is dropped). Only the sub-select's projected variables are
1777    /// visible here — its internal variables were removed by its own projection.
1778    fn execute_sub_select(
1779        &self,
1780        query_id: u16,
1781        ctx: &SparqlQueryContext,
1782        row: &BindingRow,
1783        results: &mut Vec<BindingRow>,
1784    ) -> Result<bool, String> {
1785        let subquery = *ctx
1786            .subqueries
1787            .get(query_id as usize)
1788            .ok_or("Subquery ID out of bounds")?;
1789        let sub_plan = QueryPlanner::plan(&subquery, ctx)?;
1790        let sub_rows = self.execute(&sub_plan, ctx)?;
1791
1792        for sub_row in sub_rows {
1793            let mut merged = *row;
1794            let mut compatible = true;
1795            for var in 0..ctx.variable_count as VariableId {
1796                if let Some(v) = sub_row.get(var) {
1797                    match merged.get(var) {
1798                        Some(existing) if existing != v => {
1799                            compatible = false;
1800                            break;
1801                        }
1802                        _ => merged.set(var, v),
1803                    }
1804                }
1805            }
1806            if compatible {
1807                results.push(merged);
1808            }
1809        }
1810        Ok(!results.is_empty())
1811    }
1812
1813    /// DISTINCT — deduplicate rows by bound-slot equality.
1814    fn execute_distinct(
1815        &self,
1816        input: OperatorId,
1817        plan: &ExecutionPlan,
1818        ctx: &SparqlQueryContext,
1819        row: &mut BindingRow,
1820        results: &mut Vec<BindingRow>,
1821    ) -> Result<bool, String> {
1822        let start_len = results.len();
1823        self.execute_operator(input, plan, ctx, row, results)?;
1824
1825        let slice = &mut results[start_len..];
1826        slice.sort_unstable();
1827
1828        if results.len() > start_len {
1829            let mut write_idx = start_len + 1;
1830            for read_idx in (start_len + 1)..results.len() {
1831                if results[read_idx] != results[write_idx - 1] {
1832                    results[write_idx] = results[read_idx];
1833                    write_idx += 1;
1834                }
1835            }
1836            results.truncate(write_idx);
1837        }
1838
1839        Ok(!results.is_empty())
1840    }
1841
1842    /// GROUP BY — partition rows by key slots and evaluate
1843    /// aggregates per group.
1844    fn execute_group_by(
1845        &self,
1846        input: OperatorId,
1847        group_vars: [VariableId; MAX_VARIABLES],
1848        group_var_count: u8,
1849        aggregates: [crate::sparql_planner::AggregateSpec; 16],
1850        aggregate_count: u8,
1851        plan: &ExecutionPlan,
1852        ctx: &SparqlQueryContext,
1853        row: &mut BindingRow,
1854        results: &mut Vec<BindingRow>,
1855    ) -> Result<bool, String> {
1856        let mut all_results = Vec::new();
1857        self.execute_operator(input, plan, ctx, row, &mut all_results)?;
1858
1859        // Group results by group variables
1860        let mut agg_ctx = AggregationContext::new(&aggregates, aggregate_count);
1861
1862        for result in &all_results {
1863            let mut key = GroupKey::new();
1864            for i in 0..group_var_count as usize {
1865                let var_id = group_vars[i];
1866                if let Some(value) = result.get(var_id) {
1867                    key.set(var_id, value);
1868                }
1869            }
1870
1871            let group_idx = agg_ctx.find_or_create_group(key)?;
1872            agg_ctx.add_values_to_group(group_idx, result);
1873        }
1874
1875        // Convert groups to binding rows
1876        for i in 0..agg_ctx.group_count as usize {
1877            let (key, accumulators) = &agg_ctx.groups[i];
1878            let mut result_row = BindingRow::new();
1879            for j in 0..key.var_count as usize {
1880                result_row.slots[j] = Some(key.values[j]);
1881            }
1882
1883            // Write aggregate results to output variables
1884            for j in 0..aggregate_count as usize {
1885                if let Some(result_val) = accumulators[j].get_result() {
1886                    let out_var = aggregates[j].output_var;
1887                    result_row.slots[out_var as usize] = Some(result_val);
1888                }
1889            }
1890            results.push(result_row);
1891        }
1892
1893        Ok(!results.is_empty())
1894    }
1895
1896    /// HAVING — filter grouped rows by the post-aggregation
1897    /// expression.
1898    fn execute_having(
1899        &self,
1900        input: OperatorId,
1901        expression: ExpressionId,
1902        plan: &ExecutionPlan,
1903        ctx: &SparqlQueryContext,
1904        row: &mut BindingRow,
1905        results: &mut Vec<BindingRow>,
1906    ) -> Result<bool, String> {
1907        let mut all_results = Vec::new();
1908        self.execute_operator(input, plan, ctx, row, &mut all_results)?;
1909
1910        // Filter results based on HAVING expression (EXISTS-aware, like FILTER).
1911        for result in all_results {
1912            if self.eval_filter_bool(expression, ctx, &result)? {
1913                results.push(result);
1914            }
1915        }
1916
1917        Ok(!results.is_empty())
1918    }
1919
1920    /// Property-path traversal — sequence/alternative/one-or-more
1921    /// over the quin graph (bounded visited set).
1922    fn execute_property_path(
1923        &self,
1924        subject: u64,
1925        path_id: PathId,
1926        object: u64,
1927        ctx: &SparqlQueryContext,
1928        row: &mut BindingRow,
1929        results: &mut Vec<BindingRow>,
1930    ) -> Result<bool, String> {
1931        let path = ctx
1932            .paths
1933            .get(path_id as usize)
1934            .ok_or("Path ID out of bounds")?;
1935
1936        match path {
1937            crate::sparql_ast::Path::Predicate(pred) => {
1938                // Simple predicate - same as triple scan
1939                self.execute_triple_scan(subject, *pred, object, ctx, row, results)
1940            }
1941            crate::sparql_ast::Path::Inverse(inner_id) => {
1942                // Inverse - swap subject and object
1943                self.execute_property_path(object, *inner_id, subject, ctx, row, results)
1944            }
1945            crate::sparql_ast::Path::Sequence { left, right } => {
1946                // Sequence - execute left then right
1947                let mut intermediate_results = Vec::new();
1948                self.execute_property_path(subject, *left, 0, ctx, row, &mut intermediate_results)?;
1949
1950                for inter_result in intermediate_results {
1951                    let intermediate_val = inter_result.slots[0].unwrap_or(0);
1952                    self.execute_property_path(
1953                        intermediate_val,
1954                        *right,
1955                        object,
1956                        ctx,
1957                        row,
1958                        results,
1959                    )?;
1960                }
1961                Ok(!results.is_empty())
1962            }
1963            crate::sparql_ast::Path::Alternative { left, right } => {
1964                // Alternation - execute left OR right
1965                let mut left_results = Vec::new();
1966                let mut right_results = Vec::new();
1967
1968                self.execute_property_path(subject, *left, object, ctx, row, &mut left_results)?;
1969                self.execute_property_path(subject, *right, object, ctx, row, &mut right_results)?;
1970
1971                results.extend_from_slice(&left_results);
1972                results.extend_from_slice(&right_results);
1973                Ok(!results.is_empty())
1974            }
1975            crate::sparql_ast::Path::ZeroOrMore(inner_id) => {
1976                // Kleene star `*`: the FULL reflexive-transitive closure of the inner
1977                // path from `subject`, computed as a cycle-safe fixpoint (not a fixed
1978                // hop limit). `subject` itself matches the zero-length path.
1979                let mut reached = self.path_transitive_hops(subject, *inner_id, ctx, row)?;
1980                reached.insert(subject);
1981                Self::emit_path_nodes(reached, object, results);
1982                Ok(!results.is_empty())
1983            }
1984            crate::sparql_ast::Path::OneOrMore(inner_id) => {
1985                // `+`: the FULL (non-reflexive) transitive closure of the inner path from
1986                // `subject`, cycle-safe. `subject` is included only if a cycle reaches it
1987                // back via ≥1 hop.
1988                let reached = self.path_transitive_hops(subject, *inner_id, ctx, row)?;
1989                Self::emit_path_nodes(reached, object, results);
1990                Ok(!results.is_empty())
1991            }
1992            crate::sparql_ast::Path::ZeroOrOne(inner_id) => {
1993                // Zero or one - either direct or via path
1994                // Direct match
1995                if subject == object {
1996                    let mut direct_row = BindingRow::new();
1997                    direct_row.slots[0] = Some(subject);
1998                    results.push(direct_row);
1999                }
2000
2001                // Via path
2002                self.execute_property_path(subject, *inner_id, object, ctx, row, results)
2003            }
2004        }
2005    }
2006
2007    /// Nodes reachable from `subject` via **one or more** applications of the inner
2008    /// property path — the full transitive closure, made cycle-safe by expanding each
2009    /// node at most once. Replaces the former fixed "up to 3 hops" truncation, which
2010    /// silently returned incomplete results for longer paths.
2011    fn path_transitive_hops(
2012        &self,
2013        subject: u64,
2014        path_id: PathId,
2015        ctx: &SparqlQueryContext,
2016        row: &mut BindingRow,
2017    ) -> Result<std::collections::HashSet<u64>, String> {
2018        use std::collections::HashSet;
2019        let mut reached: HashSet<u64> = HashSet::new();
2020        let mut expanded: HashSet<u64> = HashSet::new();
2021        let mut frontier: Vec<u64> = vec![subject];
2022        while let Some(node) = frontier.pop() {
2023            if !expanded.insert(node) {
2024                continue; // cycle guard: expand each node's out-edges at most once
2025            }
2026            let mut hops = Vec::new();
2027            self.execute_property_path(node, path_id, 0, ctx, row, &mut hops)?;
2028            for hop in hops {
2029                let next = hop.slots[0].unwrap_or(0);
2030                reached.insert(next);
2031                frontier.push(next);
2032            }
2033        }
2034        Ok(reached)
2035    }
2036
2037    /// Emit a one-binding row (slot 0 = node) for each reachable node matching `object`
2038    /// (`object == 0` = unbound → emit all).
2039    fn emit_path_nodes(
2040        nodes: impl IntoIterator<Item = u64>,
2041        object: u64,
2042        results: &mut Vec<BindingRow>,
2043    ) {
2044        for node in nodes {
2045            if object == 0 || node == object {
2046                let mut r = BindingRow::new();
2047                r.slots[0] = Some(node);
2048                results.push(r);
2049            }
2050        }
2051    }
2052
2053    /// GRAPH — execute the inner pattern constrained to the named
2054    /// graph's context field.
2055    fn execute_graph(
2056        &self,
2057        graph_var_or_id: u64,
2058        inner: OperatorId,
2059        plan: &ExecutionPlan,
2060        ctx: &SparqlQueryContext,
2061        row: &mut BindingRow,
2062        results: &mut Vec<BindingRow>,
2063    ) -> Result<bool, String> {
2064        // GRAPH ?g { … } — the graph term is a variable. Enumerate every named
2065        // graph (distinct non-default context), evaluate the inner pattern within
2066        // it, and bind ?g to that graph IRI on each resulting solution.
2067        if let Some(graph_var) = term_is_var(graph_var_or_id, ctx) {
2068            let mut contexts: Vec<u64> = Vec::new();
2069            for q in self.quins {
2070                if q.context != 0 && !contexts.contains(&q.context) {
2071                    contexts.push(q.context);
2072                }
2073            }
2074
2075            let mut matched = false;
2076            for gctx in contexts {
2077                let graph_quins = crate::query_engine::filter_by_context(self.quins, gctx);
2078                if graph_quins.is_empty() {
2079                    continue;
2080                }
2081                let temp_executor = QueryExecutor {
2082                    quins: &graph_quins,
2083                    resolver: self.resolver,
2084                };
2085                // Seed the inner evaluation with ?g pre-bound so a join on ?g is
2086                // consistent; stamp it on every produced row as well.
2087                let mut seed = *row;
2088                seed.set(graph_var, gctx);
2089                let mut local = Vec::new();
2090                if temp_executor.execute_operator(inner, plan, ctx, &mut seed, &mut local)? {
2091                    matched = true;
2092                }
2093                for mut r in local {
2094                    r.set(graph_var, gctx);
2095                    results.push(r);
2096                }
2097            }
2098            return Ok(matched);
2099        }
2100
2101        // GRAPH <iri> { … } — a specific named graph.
2102        let graph_id = graph_var_or_id;
2103
2104        // Filter quins by graph context
2105        let graph_quins = crate::query_engine::filter_by_context(self.quins, graph_id);
2106
2107        if graph_quins.is_empty() {
2108            return Ok(false);
2109        }
2110
2111        // Create a temporary executor with graph-filtered quins, propagating the
2112        // text resolver so nested GRAPH/geo functions still resolve.
2113        let temp_executor = QueryExecutor {
2114            quins: &graph_quins,
2115            resolver: self.resolver,
2116        };
2117
2118        // Execute inner pattern with graph-filtered quins
2119        temp_executor.execute_operator(inner, plan, ctx, row, results)
2120    }
2121
2122    /// SERVICE — execute federated SPARQL pattern.
2123    ///
2124    /// Validates the endpoint DID. If the endpoint targets the local node context,
2125    /// it evaluates against local quins. For remote endpoints, it fails closed with an
2126    /// honest error unless dispatched through a configured `FederatedQueryHandler`.
2127    fn execute_service(
2128        &self,
2129        endpoint_did_id: u64,
2130        inner: OperatorId,
2131        plan: &ExecutionPlan,
2132        ctx: &SparqlQueryContext,
2133        row: &mut BindingRow,
2134        results: &mut Vec<BindingRow>,
2135    ) -> Result<bool, String> {
2136        // Check if DID has 0x8 prefix (identity recognition)
2137        let is_did = (endpoint_did_id & 0x8000_0000_0000_0000) != 0;
2138
2139        if !is_did {
2140            return Err("Invalid DID: missing 0x8 prefix".to_string());
2141        }
2142
2143        // Check if endpoint is local node selfhood / default graph context
2144        let is_local = endpoint_did_id == 0x8000_0000_0000_0000
2145            || self
2146                .quins
2147                .first()
2148                .is_some_and(|q| q.context == (endpoint_did_id & 0x7FFF_FFFF_FFFF_FFFF));
2149
2150        if is_local {
2151            self.execute_operator(inner, plan, ctx, row, results)
2152        } else {
2153            Err(format!(
2154                "SPARQL SERVICE federation to remote endpoint DID 0x{:016x} is not wired to local executor (fails closed; use FederatedQueryHandler with configured endpoint URL)",
2155                endpoint_did_id
2156            ))
2157        }
2158    }
2159
2160    /// AS OF / AT TIME — execute the inner pattern, then keep rows
2161    /// whose subject satisfies the PROV-O temporal constraint at
2162    /// `timestamp_ms` (open-world: unannotated subjects pass).
2163    fn execute_as_of(
2164        &self,
2165        input: OperatorId,
2166        timestamp_ms: u64,
2167        mode: TemporalMode,
2168        plan: &ExecutionPlan,
2169        ctx: &SparqlQueryContext,
2170        row: &mut BindingRow,
2171        results: &mut Vec<BindingRow>,
2172    ) -> Result<bool, String> {
2173        let mut inner_results = Vec::new();
2174        self.execute_operator(input, plan, ctx, row, &mut inner_results)?;
2175
2176        for candidate in inner_results {
2177            let subject_opt = candidate.slots.iter().find_map(|s| *s);
2178            let passes = if let Some(subject) = subject_opt {
2179                self.check_temporal_constraint(subject, timestamp_ms, mode)
2180            } else {
2181                true
2182            };
2183            if passes {
2184                results.push(candidate);
2185            }
2186        }
2187        Ok(!results.is_empty())
2188    }
2189
2190    /// Check whether `subject` satisfies the temporal constraint at `timestamp_ms`.
2191    ///
2192    /// Queries T_CONTEXT PROV-O quins for the subject.  Open-world assumption: if no
2193    /// temporal annotation is present, the quin is included.
2194    fn check_temporal_constraint(
2195        &self,
2196        subject: u64,
2197        timestamp_ms: u64,
2198        mode: TemporalMode,
2199    ) -> bool {
2200        use crate::kml_bridge::T_CONTEXT;
2201        use crate::sparql_filter::prov_predicates;
2202
2203        match mode {
2204            TemporalMode::AsOf => {
2205                let gen_time = self
2206                    .quins
2207                    .iter()
2208                    .find(|q| {
2209                        q.subject == subject
2210                            && q.predicate == prov_predicates::GENERATED_AT_TIME
2211                            && q.context == T_CONTEXT
2212                    })
2213                    .map(|q| q.object);
2214                gen_time.map(|t| t <= timestamp_ms).unwrap_or(true)
2215            }
2216            TemporalMode::AtTime => {
2217                let start = self
2218                    .quins
2219                    .iter()
2220                    .find(|q| {
2221                        q.subject == subject
2222                            && q.predicate == prov_predicates::STARTED_AT_TIME
2223                            && q.context == T_CONTEXT
2224                    })
2225                    .map(|q| q.object);
2226                let end = self
2227                    .quins
2228                    .iter()
2229                    .find(|q| {
2230                        q.subject == subject
2231                            && q.predicate == prov_predicates::ENDED_AT_TIME
2232                            && q.context == T_CONTEXT
2233                    })
2234                    .map(|q| q.object);
2235                start.map(|t| t <= timestamp_ms).unwrap_or(true)
2236                    && end.map(|t| timestamp_ms <= t).unwrap_or(true)
2237            }
2238        }
2239    }
2240}
2241
2242/// Unpack an embedded triple and map its components to variable indices in a BindingRow.
2243pub fn unpack_virtual_triple(
2244    virtual_id: u64,
2245    lexicon: &crate::q42_lex::Q42LexMmap<'_>,
2246    row: &mut crate::sparql_ast::BindingRow,
2247    s_var_idx: Option<u8>,
2248    p_var_idx: Option<u8>,
2249    o_var_idx: Option<u8>,
2250) -> Result<(), String> {
2251    if let Some([s_id, p_id, o_id]) = lexicon.lookup_embedded_triple(virtual_id) {
2252        if let Some(s_idx) = s_var_idx {
2253            row.slots[s_idx as usize] = Some(s_id);
2254        }
2255        if let Some(p_idx) = p_var_idx {
2256            row.slots[p_idx as usize] = Some(p_id);
2257        }
2258        if let Some(o_idx) = o_var_idx {
2259            row.slots[o_idx as usize] = Some(o_id);
2260        }
2261        Ok(())
2262    } else {
2263        Err("Virtual ID not found in lexicon or invalid".to_string())
2264    }
2265}
2266
2267#[cfg(test)]
2268mod tests {
2269    use super::*;
2270
2271    #[test]
2272    fn test_executor_creation() {
2273        let quins = vec![];
2274        let executor = QueryExecutor::new(&quins);
2275        assert_eq!(executor.quins.len(), 0);
2276    }
2277
2278    #[test]
2279    fn test_execute_empty_plan() {
2280        let quins = vec![];
2281        let executor = QueryExecutor::new(&quins);
2282        let plan = ExecutionPlan::new();
2283        let ctx = SparqlQueryContext::new();
2284
2285        let result = executor.execute(&plan, &ctx);
2286        // Should fail because root operator is invalid
2287        assert!(result.is_err());
2288    }
2289
2290    #[cfg(not(target_arch = "wasm32"))]
2291    #[test]
2292    fn range_triple_page_uses_q42_bidx_without_resident_graph() {
2293        let dir = tempfile::TempDir::new().unwrap();
2294        let path = dir.path().join("range.q42");
2295        let quin = NQuin {
2296            subject: 101,
2297            predicate: 202,
2298            object: 303,
2299            context: 0,
2300            metadata: 0,
2301            parity: 0,
2302        };
2303        crate::q42_volume::write_unified_volume(
2304            &path,
2305            &std::collections::HashMap::new(),
2306            &[(quin.object, quin.object)],
2307            &[vec![quin]],
2308        )
2309        .unwrap();
2310        let source = crate::q42_volume::LocalFileRangeSource::open(&path).unwrap();
2311        let volume = crate::q42_volume::Q42RangeVolume::open(source).unwrap();
2312        let context = SparqlQueryContext::new();
2313        let mut compressed = [0u8; crate::q42_volume::MAX_COMPRESSED_SUPERBLOCK_SIZE];
2314        let mut decoded = [0u8; crate::q42_volume::SUPERBLOCK_SIZE];
2315        let mut quins = [NQuin::default(); 1];
2316        let mut rows = [BindingRow::default(); 1];
2317        let page = execute_range_triple_page_into(
2318            &volume,
2319            quin.subject,
2320            quin.predicate,
2321            quin.object,
2322            None,
2323            &context,
2324            &BindingRow::default(),
2325            Q42RangeSparqlCursor::default(),
2326            &mut compressed,
2327            &mut decoded,
2328            &mut quins,
2329            &mut rows,
2330        )
2331        .unwrap();
2332        assert_eq!(page.returned, 1);
2333        assert_eq!(rows[0].slots[0], None);
2334    }
2335
2336    #[cfg(not(target_arch = "wasm32"))]
2337    #[test]
2338    fn range_nested_loop_join_resumes_without_a_resident_graph() {
2339        let dir = tempfile::TempDir::new().unwrap();
2340        let path = dir.path().join("range-join.q42");
2341        let left = NQuin {
2342            subject: 10,
2343            predicate: 20,
2344            object: 30,
2345            context: 0,
2346            metadata: 0,
2347            parity: 0,
2348        };
2349        let right = NQuin {
2350            subject: 30,
2351            predicate: 40,
2352            object: 50,
2353            context: 0,
2354            metadata: 0,
2355            parity: 0,
2356        };
2357        crate::q42_volume::write_unified_volume(
2358            &path,
2359            &std::collections::HashMap::new(),
2360            &[(left.object, right.object)],
2361            &[vec![left, right]],
2362        )
2363        .unwrap();
2364        let source = crate::q42_volume::LocalFileRangeSource::open(&path).unwrap();
2365        let volume = crate::q42_volume::Q42RangeVolume::open(source).unwrap();
2366        let mut context = SparqlQueryContext::new();
2367        context.variable_count = 1;
2368        let plan = Q42RangeNestedLoopJoinPlan {
2369            left: Q42RangeTriplePattern {
2370                subject: left.subject,
2371                predicate: left.predicate,
2372                object: 0,
2373            },
2374            right: Q42RangeTriplePattern {
2375                subject: 0,
2376                predicate: right.predicate,
2377                object: right.object,
2378            },
2379        };
2380        let mut compressed = [0u8; crate::q42_volume::MAX_COMPRESSED_SUPERBLOCK_SIZE];
2381        let mut decoded = [0u8; crate::q42_volume::SUPERBLOCK_SIZE];
2382        let mut quins = [NQuin::default(); 1];
2383        let mut left_rows = [BindingRow::default(); 1];
2384        let mut right_rows = [BindingRow::default(); 1];
2385        let mut out = [BindingRow::default(); 1];
2386        let mut state = Q42RangeNestedLoopJoinState::default();
2387
2388        let first = execute_range_nested_loop_join_page_into(
2389            &volume,
2390            plan,
2391            &context,
2392            &mut state,
2393            &mut compressed,
2394            &mut decoded,
2395            &mut quins,
2396            &mut left_rows,
2397            &mut right_rows,
2398            &mut out,
2399        )
2400        .unwrap();
2401        assert_eq!(first.returned, 1);
2402        assert_eq!(out[0].slots[0], Some(right.subject));
2403        assert!(!first.done);
2404
2405        let final_page = execute_range_nested_loop_join_page_into(
2406            &volume,
2407            plan,
2408            &context,
2409            &mut state,
2410            &mut compressed,
2411            &mut decoded,
2412            &mut quins,
2413            &mut left_rows,
2414            &mut right_rows,
2415            &mut out,
2416        )
2417        .unwrap();
2418        assert_eq!(final_page.returned, 0);
2419        assert!(final_page.done);
2420    }
2421
2422    #[cfg(not(target_arch = "wasm32"))]
2423    #[test]
2424    fn range_volume_set_nested_loop_join_scans_manifest_children() {
2425        let dir = tempfile::TempDir::new().unwrap();
2426        let child_path = dir.path().join("child.q42");
2427        let root_path = dir.path().join("root.q42");
2428        let left = NQuin {
2429            subject: 10,
2430            predicate: 20,
2431            object: 30,
2432            context: 0,
2433            metadata: 0,
2434            parity: 0,
2435        };
2436        let right = NQuin {
2437            subject: 30,
2438            predicate: 40,
2439            object: 50,
2440            context: 0,
2441            metadata: 0,
2442            parity: 0,
2443        };
2444        crate::q42_volume::write_unified_volume(
2445            &child_path,
2446            &std::collections::HashMap::new(),
2447            &[(left.object, right.object)],
2448            &[vec![left, right]],
2449        )
2450        .unwrap();
2451        let manifest = crate::q42_volume::Q42VolumeManifest {
2452            generation: 1,
2453            segments: vec![crate::q42_volume::Q42VolumeManifest::segment_from_file(
2454                &child_path,
2455                "child.q42".to_string(),
2456            )
2457            .unwrap()],
2458            lexicon_segments: Vec::new(),
2459        };
2460        crate::q42_volume::write_volume_root(&root_path, &manifest).unwrap();
2461        let root_source = crate::q42_volume::LocalFileRangeSource::open(&root_path).unwrap();
2462        let root = crate::q42_volume::Q42RangeVolume::open(root_source).unwrap();
2463        let factory = |entry: &crate::q42_volume::Q42VolumeSegment| {
2464            crate::q42_volume::LocalFileRangeSource::open(&dir.path().join(&entry.locator))
2465        };
2466        let volumes = crate::q42_volume::Q42RangeVolumeSet::open_root(&root, &factory).unwrap();
2467        let mut context = SparqlQueryContext::new();
2468        context.variable_count = 1;
2469        let plan = Q42RangeNestedLoopJoinPlan {
2470            left: Q42RangeTriplePattern {
2471                subject: left.subject,
2472                predicate: left.predicate,
2473                object: 0,
2474            },
2475            right: Q42RangeTriplePattern {
2476                subject: 0,
2477                predicate: right.predicate,
2478                object: right.object,
2479            },
2480        };
2481        let mut compressed = [0u8; crate::q42_volume::MAX_COMPRESSED_SUPERBLOCK_SIZE];
2482        let mut decoded = [0u8; crate::q42_volume::SUPERBLOCK_SIZE];
2483        let mut quins = [NQuin::default(); 1];
2484        let mut left_rows = [BindingRow::default(); 1];
2485        let mut right_rows = [BindingRow::default(); 1];
2486        let mut out = [BindingRow::default(); 1];
2487        let mut state = Q42RangeVolumeSetNestedLoopJoinState::default();
2488        let page = execute_range_volume_set_nested_loop_join_page_into(
2489            &volumes,
2490            plan,
2491            &context,
2492            &mut state,
2493            &mut compressed,
2494            &mut decoded,
2495            &mut quins,
2496            &mut left_rows,
2497            &mut right_rows,
2498            &mut out,
2499        )
2500        .unwrap();
2501        assert_eq!(page.returned, 1);
2502        assert_eq!(out[0].slots[0], Some(right.subject));
2503    }
2504}