1pub type PatternId = u16;
7pub type ExpressionId = u16;
8pub type VariableId = u8;
9
10pub const MAX_PATTERNS: usize = 128;
12
13pub const MAX_EXPRESSIONS: usize = 128;
15
16pub const MAX_VARIABLES: usize = 16;
18
19pub const MAX_BINDINGS: usize = 16;
21
22pub const MAX_ORDER_CONDITIONS: usize = 16;
24
25#[repr(C)]
27#[derive(Debug, Clone, Copy, PartialEq, Eq)]
28pub enum SparqlQuery {
29 Select(SelectQuery),
30 Ask(AskQuery),
31 Construct(ConstructQuery),
32 Describe(DescribeQuery),
33}
34
35#[repr(C)]
37#[derive(Debug, Clone, Copy, PartialEq, Eq)]
38pub struct SelectQuery {
39 pub distinct: bool,
40 pub reduced: bool,
41 pub variables: [VariableId; MAX_VARIABLES],
42 pub var_count: u8,
43 pub root_pattern: PatternId,
44 pub group_by: [VariableId; MAX_VARIABLES],
45 pub group_by_count: u8,
46 pub aggregates: [crate::sparql_planner::AggregateSpec; 16],
47 pub aggregate_count: u8,
48 pub having: Option<ExpressionId>,
49 pub order_by: [OrderCondition; MAX_ORDER_CONDITIONS],
50 pub order_by_count: u8,
51 pub limit: Option<u64>,
52 pub offset: u64,
53}
54
55impl Default for SelectQuery {
56 fn default() -> Self {
57 Self {
58 distinct: false,
59 reduced: false,
60 variables: [0; MAX_VARIABLES],
61 var_count: 0,
62 root_pattern: 0,
63 group_by: [0; MAX_VARIABLES],
64 group_by_count: 0,
65 aggregates: [crate::sparql_planner::AggregateSpec {
66 func: 0,
67 input_var: 0,
68 output_var: 0,
69 }; 16],
70 aggregate_count: 0,
71 having: None,
72 order_by: [OrderCondition::default(); MAX_ORDER_CONDITIONS],
73 order_by_count: 0,
74 limit: None,
75 offset: 0,
76 }
77 }
78}
79
80#[repr(C)]
82#[derive(Debug, Clone, Copy, PartialEq, Eq)]
83pub struct AskQuery {
84 pub root_pattern: PatternId,
85}
86
87#[repr(C)]
89#[derive(Debug, Clone, Copy, PartialEq, Eq)]
90pub struct ConstructQuery {
91 pub template_pattern: PatternId,
92 pub root_pattern: PatternId,
93 pub group_by: [VariableId; MAX_VARIABLES],
94 pub group_by_count: u8,
95 pub having: Option<ExpressionId>,
96 pub order_by: [OrderCondition; MAX_ORDER_CONDITIONS],
97 pub order_by_count: u8,
98 pub limit: Option<u64>,
99 pub offset: u64,
100}
101
102#[repr(C)]
104#[derive(Debug, Clone, Copy, PartialEq, Eq)]
105pub struct DescribeQuery {
106 pub vars_or_ids: [u64; MAX_VARIABLES],
107 pub var_count: u8,
108 pub root_pattern: Option<PatternId>,
109}
110
111#[repr(u8)]
115#[derive(Debug, Clone, Copy, PartialEq, Eq)]
116pub enum TemporalMode {
117 AsOf = 0,
119 AtTime = 1,
121}
122
123#[repr(C)]
125#[derive(Debug, Clone, Copy, PartialEq, Eq)]
126pub enum Pattern {
127 Triple {
129 subject: u64,
130 predicate: u64,
131 object: u64,
132 },
133 Optional { inner: PatternId },
135 Union { left: PatternId, right: PatternId },
137 Graph {
139 graph_var_or_id: u64,
140 inner: PatternId,
141 },
142 Filter {
144 pattern: PatternId,
145 expression: ExpressionId,
146 },
147 Bind {
151 pattern: PatternId,
152 var: VariableId,
153 expression: ExpressionId,
154 },
155 Minus { inner: PatternId },
157 Group { start_idx: u16, len: u16 },
159 PropertyPath {
161 subject: u64,
162 path: PathId,
163 object: u64,
164 },
165 Service {
167 endpoint_did_id: u64, inner_pattern: PatternId,
169 },
170 AsOf {
175 inner: PatternId,
176 timestamp_ms: u64,
177 mode: TemporalMode,
178 },
179 StarTriple {
181 inner_subject: u64,
182 inner_predicate: u64,
183 inner_object: u64,
184 outer_predicate: u64,
185 outer_object: u64,
186 },
187 SubSelect { query_id: u16 },
192}
193
194#[repr(C)]
196#[derive(Debug, Clone, Copy, PartialEq, Eq)]
197pub enum Path {
198 Predicate(u64),
200 Inverse(PathId),
202 Sequence { left: PathId, right: PathId },
204 Alternative { left: PathId, right: PathId },
206 ZeroOrMore(PathId),
208 OneOrMore(PathId),
210 ZeroOrOne(PathId),
212}
213
214pub type PathId = u16;
215
216#[repr(C)]
218#[derive(Debug, Clone, Copy, PartialEq, Eq)]
219pub enum Expression {
220 Variable(VariableId),
222 Literal(u64),
224 Iri(u64),
226 UnaryOp { op: UnaryOp, expr: ExpressionId },
228 BinaryOp {
230 op: BinaryOp,
231 left: ExpressionId,
232 right: ExpressionId,
233 },
234 Function {
236 func: Function,
237 args_start: u16,
238 args_len: u16,
239 },
240 Subquery {
242 query_id: u16, },
244 EmbeddedTriple {
246 subject: u64,
247 predicate: u64,
248 object: u64,
249 },
250 Exists { pattern: PatternId, negated: bool },
256}
257
258#[repr(C)]
260#[derive(Debug, Clone, Copy, PartialEq, Eq)]
261pub enum UnaryOp {
262 Not,
263 Plus,
264 Minus,
265}
266
267#[repr(C)]
269#[derive(Debug, Clone, Copy, PartialEq, Eq)]
270pub enum BinaryOp {
271 Or,
272 And,
273 Equal,
274 NotEqual,
275 LessThan,
276 LessThanOrEqual,
277 GreaterThan,
278 GreaterThanOrEqual,
279 Add,
280 Subtract,
281 Multiply,
282 Divide,
283}
284
285#[repr(C)]
287#[derive(Debug, Clone, Copy, PartialEq, Eq)]
288pub enum Function {
289 Str,
290 Lang,
291 LangMatches,
292 Datatype,
293 Bound,
294 Iri,
295 Uri,
296 Bnode,
297 Rand,
298 Abs,
299 Ceil,
300 Floor,
301 Round,
302 Concat,
303 Substring,
304 Strlen,
305 Ucase,
306 Lcase,
307 EncodeForUri,
308 Contains,
309 VarStarts,
310 VarEnds,
311 StrBefore,
312 StrAfter,
313 Year,
314 Month,
315 Day,
316 Hours,
317 Minutes,
318 Seconds,
319 Timezone,
320 Tz,
321 Now,
322 Uuid,
323 StrUuid,
324 Coalesce,
325 If,
326 StrLang,
327 StrDt,
328 SameTerm,
329 IsIri,
330 IsUri,
331 IsBlank,
332 IsLiteral,
333 IsNumeric,
334 Regex,
335 TripleSubject,
337 TriplePredicate,
338 TripleObject,
339 Triple,
340 Custom(u64), }
342
343#[repr(C)]
345#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
346pub struct OrderCondition {
347 pub ascending: bool,
348 pub expr: ExpressionId,
349}
350
351#[repr(C)]
353pub struct SparqlQueryContext {
354 pub patterns: [Pattern; MAX_PATTERNS],
356 pub pattern_count: usize,
358 pub expressions: [Expression; MAX_EXPRESSIONS],
360 pub expression_count: usize,
362 pub paths: [Path; MAX_PATTERNS],
364 pub path_count: usize,
366 pub subqueries: [SparqlQuery; 16],
368 pub subquery_count: usize,
370 pub variable_hashes: [u64; MAX_VARIABLES],
372 pub variable_count: usize,
374 pub function_args: [ExpressionId; 64],
376 pub function_arg_count: usize,
378}
379
380pub fn literal_term_hash(text: &str, lang: Option<&str>, datatype: Option<&str>) -> u64 {
390 if lang.is_none() && datatype == Some(crate::resolver::typed_double::DATATYPE) {
393 if let Some(term) = crate::resolver::typed_double::from_lexical(text) {
394 return crate::resolver::typed_double::token(&term);
395 }
396 }
397 match (lang, datatype) {
398 (None, None) => crate::lexicon::generate_60bit_token(text.as_bytes()),
399 (Some(l), _) => crate::lexicon::generate_60bit_token(format!("{text}@{l}").as_bytes()),
400 (None, Some(d)) => crate::lexicon::generate_60bit_token(format!("{text}^^{d}").as_bytes()),
401 }
402}
403
404#[derive(Debug, Default, Clone)]
410pub struct LiteralTable {
411 entries: Vec<(u64, String, Option<String>, Option<String>)>,
412}
413
414impl LiteralTable {
415 pub fn new() -> Self {
417 Self::default()
418 }
419 pub fn intern(&mut self, hash: u64, text: &str) {
421 self.intern_tagged(hash, text, None, None);
422 }
423 pub fn intern_tagged(
425 &mut self,
426 hash: u64,
427 text: &str,
428 lang: Option<&str>,
429 datatype: Option<&str>,
430 ) {
431 if self.entries.iter().any(|(h, ..)| *h == hash) {
432 return;
433 }
434 self.entries.push((
435 hash,
436 text.to_string(),
437 lang.map(str::to_string),
438 datatype.map(str::to_string),
439 ));
440 }
441 pub fn resolve(&self, hash: u64) -> Option<&str> {
443 self.entries
444 .iter()
445 .find(|(h, ..)| *h == hash)
446 .map(|(_, s, ..)| s.as_str())
447 }
448 pub fn lang(&self, hash: u64) -> Option<&str> {
450 self.entries
451 .iter()
452 .find(|(h, ..)| *h == hash)
453 .and_then(|(_, _, l, _)| l.as_deref())
454 }
455 pub fn datatype(&self, hash: u64) -> Option<&str> {
457 self.entries
458 .iter()
459 .find(|(h, ..)| *h == hash)
460 .and_then(|(_, _, _, d)| d.as_deref())
461 }
462 pub fn contains(&self, hash: u64) -> bool {
464 self.entries.iter().any(|(h, ..)| *h == hash)
465 }
466 pub fn len(&self) -> usize {
468 self.entries.len()
469 }
470 pub fn is_empty(&self) -> bool {
472 self.entries.is_empty()
473 }
474}
475
476#[derive(Debug, Default)]
488pub struct StringSink {
489 produced: std::cell::RefCell<Vec<(u64, String, Option<String>, Option<String>)>>,
490}
491
492impl StringSink {
493 pub fn new() -> Self {
495 Self::default()
496 }
497 pub fn intern(&self, text: &str) -> u64 {
501 self.intern_tagged(text, None, None)
502 }
503 pub fn intern_tagged(&self, text: &str, lang: Option<&str>, datatype: Option<&str>) -> u64 {
507 let hash = literal_term_hash(text, lang, datatype);
508 let mut v = self.produced.borrow_mut();
509 if !v.iter().any(|(h, ..)| *h == hash) {
510 v.push((
511 hash,
512 text.to_string(),
513 lang.map(str::to_string),
514 datatype.map(str::to_string),
515 ));
516 }
517 hash
518 }
519 pub fn resolve(&self, hash: u64) -> Option<String> {
521 self.produced
522 .borrow()
523 .iter()
524 .find(|(h, ..)| *h == hash)
525 .map(|(_, s, ..)| s.clone())
526 }
527 pub fn lang(&self, hash: u64) -> Option<String> {
529 self.produced
530 .borrow()
531 .iter()
532 .find(|(h, ..)| *h == hash)
533 .and_then(|(_, _, l, _)| l.clone())
534 }
535 pub fn datatype(&self, hash: u64) -> Option<String> {
537 self.produced
538 .borrow()
539 .iter()
540 .find(|(h, ..)| *h == hash)
541 .and_then(|(_, _, _, d)| d.clone())
542 }
543}
544
545#[derive(Clone, Copy)]
554pub struct TextResolver<'a> {
555 pub literals: &'a LiteralTable,
556 pub lexicon: Option<&'a dyn Fn(u64) -> Option<String>>,
557 pub sink: Option<&'a StringSink>,
559 pub now_ms: u64,
562 pub seed: u64,
564}
565
566impl<'a> TextResolver<'a> {
567 pub fn new(literals: &'a LiteralTable) -> Self {
569 Self {
570 literals,
571 lexicon: None,
572 sink: None,
573 now_ms: 0,
574 seed: 0,
575 }
576 }
577 pub fn with_lexicon(
579 literals: &'a LiteralTable,
580 lexicon: &'a dyn Fn(u64) -> Option<String>,
581 ) -> Self {
582 Self {
583 literals,
584 lexicon: Some(lexicon),
585 sink: None,
586 now_ms: 0,
587 seed: 0,
588 }
589 }
590 pub fn with_sink(mut self, sink: &'a StringSink) -> Self {
592 self.sink = Some(sink);
593 self
594 }
595 pub fn with_env(mut self, now_ms: u64, seed: u64) -> Self {
598 self.now_ms = now_ms;
599 self.seed = seed;
600 self
601 }
602 pub fn resolve_text(&self, hash: u64) -> Option<String> {
604 if let Some(s) = self.literals.resolve(hash) {
605 return Some(s.to_string());
606 }
607 if let Some(sink) = self.sink {
608 if let Some(s) = sink.resolve(hash) {
609 return Some(s);
610 }
611 }
612 if let Some(f) = self.lexicon {
613 if let Some(s) = f(hash) {
614 if let Some((lexical, _)) = crate::resolver::typed_double::decode(&s) {
615 return Some(lexical.to_owned());
616 }
617 return Some(s);
618 }
619 }
620 crate::resolver::resolve_hash(hash).and_then(|b| String::from_utf8(b.to_vec()).ok())
621 }
622
623 pub fn lang_of(&self, hash: u64) -> Option<String> {
627 if let Some(l) = self.literals.lang(hash) {
628 return Some(l.to_string());
629 }
630 if let Some(sink) = self.sink {
631 if let Some(l) = sink.lang(hash) {
632 return Some(l);
633 }
634 }
635 if let Some(term) = self.lexicon.and_then(|lookup| lookup(hash)) {
636 if crate::resolver::typed_double::has_declared_datatype(&term) {
637 return Some(String::new());
638 }
639 }
640 if self.literals.contains(hash)
642 || self
643 .sink
644 .map(|s| s.resolve(hash).is_some())
645 .unwrap_or(false)
646 || crate::resolver::classify_inline_literal(hash).is_some()
647 {
648 return Some(String::new());
649 }
650 None
651 }
652
653 pub fn datatype_of(&self, hash: u64) -> Option<String> {
658 const XSD_STRING: &str = "http://www.w3.org/2001/XMLSchema#string";
659 const RDF_LANGSTRING: &str = "http://www.w3.org/1999/02/22-rdf-syntax-ns#langString";
660 if let Some(dt) = self.literals.datatype(hash) {
661 return Some(dt.to_string());
662 }
663 if let Some(sink) = self.sink {
664 if let Some(dt) = sink.datatype(hash) {
665 return Some(dt);
666 }
667 if sink.lang(hash).is_some() {
668 return Some(RDF_LANGSTRING.to_string());
669 }
670 }
671 if self.literals.lang(hash).is_some() {
672 return Some(RDF_LANGSTRING.to_string());
673 }
674 if let Some(term) = self.lexicon.and_then(|lookup| lookup(hash)) {
675 if crate::resolver::typed_double::has_declared_datatype(&term) {
676 return Some(crate::resolver::typed_double::DATATYPE.to_owned());
677 }
678 }
679 if let Some(lit) = crate::resolver::classify_inline_literal(hash) {
680 return Some(lit.datatype_iri().to_string());
681 }
682 if self.literals.contains(hash)
683 || self
684 .sink
685 .map(|s| s.resolve(hash).is_some())
686 .unwrap_or(false)
687 {
688 return Some(XSD_STRING.to_string());
689 }
690 None
691 }
692}
693
694impl SparqlQueryContext {
695 pub fn new() -> Self {
697 Self {
698 patterns: [Pattern::Triple {
699 subject: 0,
700 predicate: 0,
701 object: 0,
702 }; MAX_PATTERNS],
703 pattern_count: 0,
704 expressions: [Expression::Variable(0); MAX_EXPRESSIONS],
705 expression_count: 0,
706 paths: [Path::Predicate(0); MAX_PATTERNS],
707 path_count: 0,
708 subqueries: [SparqlQuery::Select(SelectQuery {
709 distinct: false,
710 reduced: false,
711 variables: [0; MAX_VARIABLES],
712 var_count: 0,
713 root_pattern: 0,
714 group_by: [0; MAX_VARIABLES],
715 group_by_count: 0,
716 aggregates: [crate::sparql_planner::AggregateSpec {
717 func: 0,
718 input_var: 0,
719 output_var: 0,
720 }; 16],
721 aggregate_count: 0,
722 having: None,
723 order_by: [OrderCondition {
724 expr: 0,
725 ascending: true,
726 }; MAX_ORDER_CONDITIONS],
727 order_by_count: 0,
728 limit: None,
729 offset: 0,
730 }); 16],
731 subquery_count: 0,
732 variable_hashes: [0; MAX_VARIABLES],
733 variable_count: 0,
734 function_args: [0; 64],
735 function_arg_count: 0,
736 }
737 }
738
739 pub fn alloc_pattern(&mut self, pattern: Pattern) -> Result<PatternId, String> {
741 if self.pattern_count >= MAX_PATTERNS {
742 return Err("Pattern overflow".to_string());
743 }
744 let id = self.pattern_count as PatternId;
745 self.patterns[self.pattern_count] = pattern;
746 self.pattern_count += 1;
747 Ok(id)
748 }
749
750 pub fn alloc_expression(&mut self, expr: Expression) -> Result<ExpressionId, String> {
752 if self.expression_count >= MAX_EXPRESSIONS {
753 return Err("Expression overflow".to_string());
754 }
755 let id = self.expression_count as ExpressionId;
756 self.expressions[self.expression_count] = expr;
757 self.expression_count += 1;
758 Ok(id)
759 }
760
761 pub fn alloc_path(&mut self, path: Path) -> Result<PathId, String> {
763 if self.path_count >= MAX_PATTERNS {
764 return Err("Path overflow".to_string());
765 }
766 let id = self.path_count as PathId;
767 self.paths[self.path_count] = path;
768 self.path_count += 1;
769 Ok(id)
770 }
771
772 pub fn alloc_subquery(&mut self, query: SparqlQuery) -> Result<u16, String> {
774 if self.subquery_count >= 16 {
775 return Err("Subquery overflow".to_string());
776 }
777 let id = self.subquery_count as u16;
778 self.subqueries[self.subquery_count] = query;
779 self.subquery_count += 1;
780 Ok(id)
781 }
782
783 pub fn register_variable(&mut self, name: &str) -> Result<VariableId, String> {
785 if self.variable_count >= MAX_VARIABLES {
786 return Err("Variable overflow".to_string());
787 }
788 let hash = crate::lexicon::generate_60bit_token(name.as_bytes());
789 for (i, var_hash) in self.variable_hashes.iter().enumerate() {
791 if *var_hash == hash {
792 return Ok(i as VariableId);
793 }
794 }
795 let id = self.variable_count as VariableId;
796 self.variable_hashes[self.variable_count] = hash;
797 self.variable_count += 1;
798 Ok(id)
799 }
800
801 pub fn reset(&mut self) {
803 self.pattern_count = 0;
804 self.expression_count = 0;
805 self.variable_count = 0;
806 self.function_arg_count = 0;
807 self.variable_hashes = [0; MAX_VARIABLES];
808 }
809}
810
811impl Default for SparqlQueryContext {
812 fn default() -> Self {
813 Self::new()
814 }
815}
816
817#[repr(C)]
819#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
820pub struct BindingRow {
821 pub slots: [Option<u64>; MAX_BINDINGS],
823}
824
825impl BindingRow {
826 pub fn new() -> Self {
828 Self {
829 slots: [None; MAX_BINDINGS],
830 }
831 }
832
833 pub fn set(&mut self, var_id: VariableId, value: u64) {
835 if (var_id as usize) < MAX_BINDINGS {
836 self.slots[var_id as usize] = Some(value);
837 }
838 }
839
840 pub fn get(&self, var_id: VariableId) -> Option<u64> {
842 if (var_id as usize) < MAX_BINDINGS {
843 self.slots[var_id as usize]
844 } else {
845 None
846 }
847 }
848
849 pub fn clear(&mut self) {
851 self.slots = [None; MAX_BINDINGS];
852 }
853}
854
855impl Default for BindingRow {
856 fn default() -> Self {
857 Self::new()
858 }
859}
860
861pub trait PhysicalOperator {
863 fn next(&mut self, ctx: &SparqlQueryContext, row: &mut BindingRow) -> bool;
865}
866
867#[cfg(test)]
868mod tests {
869 use super::*;
870
871 #[test]
872 fn test_query_context_allocation() {
873 let mut ctx = SparqlQueryContext::new();
874
875 let pattern = Pattern::Triple {
876 subject: 1,
877 predicate: 2,
878 object: 3,
879 };
880
881 let id = ctx.alloc_pattern(pattern).unwrap();
882 assert_eq!(id, 0);
883 assert_eq!(ctx.pattern_count, 1);
884 }
885
886 #[test]
887 fn test_variable_registration() {
888 let mut ctx = SparqlQueryContext::new();
889
890 let id1 = ctx.register_variable("?x").unwrap();
891 let id2 = ctx.register_variable("?y").unwrap();
892
893 assert_eq!(id1, 0);
894 assert_eq!(id2, 1);
895 assert_eq!(ctx.variable_count, 2);
896 }
897
898 #[test]
899 fn test_variable_duplicate() {
900 let mut ctx = SparqlQueryContext::new();
901
902 let id1 = ctx.register_variable("?x").unwrap();
903 let id2 = ctx.register_variable("?x").unwrap();
904
905 assert_eq!(id1, id2);
906 assert_eq!(ctx.variable_count, 1);
907 }
908
909 #[test]
910 fn test_binding_row() {
911 let mut row = BindingRow::new();
912
913 row.set(0, 42);
914 assert_eq!(row.get(0), Some(42));
915 assert_eq!(row.get(1), None);
916 }
917
918 #[test]
919 fn test_optional_pattern_index() {
920 let mut ctx = SparqlQueryContext::new();
921
922 let inner = Pattern::Triple {
923 subject: 1,
924 predicate: 2,
925 object: 3,
926 };
927 let inner_id = ctx.alloc_pattern(inner).unwrap();
928
929 let optional = Pattern::Optional { inner: inner_id };
930 let optional_id = ctx.alloc_pattern(optional).unwrap();
931
932 assert_eq!(ctx.pattern_count, 2);
933 if let Pattern::Optional { inner } = ctx.patterns[optional_id as usize] {
934 assert_eq!(inner, inner_id);
935 } else {
936 panic!("Expected Optional pattern");
937 }
938 }
939
940 #[test]
941 fn test_union_pattern_index() {
942 let mut ctx = SparqlQueryContext::new();
943
944 let left = Pattern::Triple {
945 subject: 1,
946 predicate: 2,
947 object: 3,
948 };
949 let right = Pattern::Triple {
950 subject: 4,
951 predicate: 5,
952 object: 6,
953 };
954
955 let left_id = ctx.alloc_pattern(left).unwrap();
956 let right_id = ctx.alloc_pattern(right).unwrap();
957
958 let union = Pattern::Union {
959 left: left_id,
960 right: right_id,
961 };
962 let union_id = ctx.alloc_pattern(union).unwrap();
963
964 assert_eq!(ctx.pattern_count, 3);
965 if let Pattern::Union { left, right } = ctx.patterns[union_id as usize] {
966 assert_eq!(left, left_id);
967 assert_eq!(right, right_id);
968 } else {
969 panic!("Expected Union pattern");
970 }
971 }
972}