1use spargebra::Query;
13
14use crate::bgp::{Binding, PatternTerm, TriplePattern};
15use crate::file::Rete;
16
17mod aggregate;
18mod diag;
19mod distinct;
20mod distinct_union;
21mod eval;
22mod expr;
23mod fedmerge;
24mod lower;
25mod partition;
26mod path;
27mod prefetch;
28mod ql;
29mod sparql12;
30mod value;
31
32pub use diag::{warnings_json, QueryWarning, WarningSeverity};
33use eval::{ask_solution, instantiate, raw_solutions, run_select, run_select_communities};
34pub use fedmerge::FederationPlan;
35use lower::{lower_pattern, lower_select, parse_query};
36pub use lower::{parse_select, query_predicates};
37pub use partition::PartitionPlan;
38pub(crate) use eval::eval_plan_in;
41
42#[derive(Debug, thiserror::Error)]
43#[non_exhaustive]
44pub enum SparqlError {
45 #[error("parse error: {0}")]
46 Parse(String),
47 #[error("unsupported query feature: {0}")]
48 Unsupported(&'static str),
49 #[error("unsupported query feature: function <{0}> is not implemented")]
52 UnsupportedFunction(String),
53 #[error("SERVICE federation: {0}")]
57 Service(String),
58 #[error("cannot split this query {0}")]
62 Partition(String),
63 #[error("cannot federate this query: {0}")]
66 Federation(String),
67}
68
69#[derive(Debug, Clone)]
71pub struct Select {
72 pub project: Vec<String>,
74 pub distinct: bool,
76 pub offset: usize,
78 pub limit: Option<usize>,
80 pub group: Option<GroupSpec>,
82 pub extends: Vec<(String, FExpr)>,
85 pub order: Vec<(FExpr, bool)>,
87 pub having: Vec<FExpr>,
89 pub from: Vec<String>,
92 pub from_named: Option<Vec<String>>,
94 pub union_default: bool,
102 pub plan: Plan,
104 pub star_counter: usize,
109}
110
111impl Default for Select {
112 fn default() -> Self {
113 Select {
114 project: Vec::new(),
115 distinct: false,
116 offset: 0,
117 limit: None,
118 group: None,
119 extends: Vec::new(),
120 order: Vec::new(),
121 having: Vec::new(),
122 from: Vec::new(),
123 from_named: None,
124 union_default: false,
125 plan: Plan::Bgp(Vec::new()),
126 star_counter: 0,
127 }
128 }
129}
130
131#[derive(Debug, Clone)]
133pub struct GroupSpec {
134 pub by: Vec<String>,
136 pub aggs: Vec<(String, Agg)>,
138 pub pre: Vec<(String, FExpr)>,
143}
144
145#[derive(Debug, Clone)]
147pub enum Agg {
148 CountStar {
150 distinct: bool,
151 },
152 Count(String, bool),
154 Sum(String),
155 Avg(String),
156 Min(String),
157 Max(String),
158 Sample(String),
160 GroupConcat(String, String, bool),
163}
164
165#[derive(Debug, Clone)]
167#[must_use]
168pub enum Plan {
169 Bgp(Vec<TriplePattern>),
171 Join(Box<Plan>, Box<Plan>),
173 Union(Box<Plan>, Box<Plan>),
175 LeftJoin(Box<Plan>, Box<Plan>, Option<FExpr>),
178 Filter(FExpr, Box<Plan>),
180 Extend(String, FExpr, Box<Plan>),
185 Path(PatternTerm, PathAst, PatternTerm),
187 Values(Vec<String>, Vec<Vec<Option<String>>>),
190 Minus(Box<Plan>, Box<Plan>),
193 Graph(GraphTarget, Box<Plan>),
195 DistinctUnion {
208 vars: Vec<String>,
209 sources: Vec<TriplePattern>,
210 },
211 Subquery(Box<Select>),
215 Service {
223 silent: bool,
224 endpoint: String,
226 vars: Vec<String>,
229 query: String,
231 },
232}
233
234#[derive(Debug, Clone)]
236pub enum GraphTarget {
237 Named(String),
239 Var(String),
241}
242
243#[derive(Debug, Clone, Copy, PartialEq, Eq)]
245pub enum Rep {
246 One,
248 OneOrMore,
250 ZeroOrMore,
252 ZeroOrOne,
254}
255
256#[derive(Debug, Clone)]
259pub enum PathAst {
260 Pred(String, bool),
262 Rep(Box<PathAst>, Rep),
264 Seq(Box<PathAst>, Box<PathAst>),
266 Alt(Box<PathAst>, Box<PathAst>),
268 NegatedSet(Vec<String>, bool),
272}
273
274#[derive(Debug, Clone, Copy, PartialEq, Eq)]
276pub enum Op {
277 Eq,
278 Ne,
279 Lt,
280 Le,
281 Gt,
282 Ge,
283}
284
285#[derive(Debug, Clone, Copy, PartialEq, Eq)]
287pub enum ArithOp {
288 Add,
289 Sub,
290 Mul,
291 Div,
292}
293
294#[derive(Debug, Clone, Copy, PartialEq, Eq)]
297pub enum Builtin {
298 Str,
299 StrLen,
300 UCase,
301 LCase,
302 Abs,
303 Ceil,
304 Floor,
305 Round,
306 Concat,
307 SubStr,
308 StrBefore,
309 StrAfter,
310 Contains,
311 StrStarts,
312 StrEnds,
313 IsIri,
314 IsBlank,
315 IsLiteral,
316 IsNumeric,
317 Datatype,
318 Lang,
319 Regex,
320 LangMatches,
321 StrDt,
322 StrLang,
323 Iri,
324 EncodeForUri,
325 Replace,
326 Md5,
327 Sha1,
328 Sha256,
329 Sha384,
330 Sha512,
331 Year,
332 Month,
333 Day,
334 Hours,
335 Minutes,
336 Seconds,
337 Timezone,
338 Tz,
339 CastInteger,
340 CastDecimal,
341 CastFloat,
342 CastDouble,
343 CastBoolean,
344 CastString,
345 Rand,
346 Uuid,
347 StrUuid,
348 BNode,
349 GeoSfContains,
352 GeoSfWithin,
353 GeoSfIntersects,
354 GeoSfDisjoint,
355 GeoSfEquals,
356 GeoDistance,
357 GeoEnvelope,
358 Geo3Distance,
360 Geo3Contains,
361 Geo3Within,
362 Geo3Adjacent,
363 TripleTerm,
366 IsTriple,
368 Subject,
370 Predicate,
371 Object,
372}
373
374#[derive(Debug, Clone)]
376pub enum FExpr {
377 Var(String),
378 Const(String),
380 Arith(ArithOp, Box<FExpr>, Box<FExpr>),
382 Func(Builtin, Vec<FExpr>),
384 Coalesce(Vec<FExpr>),
386 If(Box<FExpr>, Box<FExpr>, Box<FExpr>),
388 In(Box<FExpr>, Vec<FExpr>),
390 SameTerm(Box<FExpr>, Box<FExpr>),
392 Compare(Op, Box<FExpr>, Box<FExpr>),
393 And(Box<FExpr>, Box<FExpr>),
394 Or(Box<FExpr>, Box<FExpr>),
395 Not(Box<FExpr>),
396 Bound(String),
397 Exists(Box<Plan>),
400}
401
402type ExistsCache = std::collections::HashMap<*const Plan, ExistsEntry>;
405
406struct ExistsEntry {
410 sols: Vec<crate::row::Row>,
412 loaded: bool,
413 probe: Option<ExistsProbe>,
414 corr: Option<crate::bgp::CorrelatedProbe>,
417}
418
419struct ExistsProbe {
423 svars: Vec<usize>,
425 jvars: Vec<usize>,
427 keys: std::collections::HashSet<Vec<crate::row::Val>>,
429 partial: Vec<crate::row::Row>,
431}
432
433fn build_exists_probe(b: &crate::row::Row, sols: &[crate::row::Row]) -> ExistsProbe {
436 let mask = crate::row::bound_mask(sols, b.len());
437 let svars: Vec<usize> = (0..b.len()).filter(|&i| mask[i]).collect();
438 let jvars: Vec<usize> = svars.iter().copied().filter(|&i| b[i].is_some()).collect();
439 let mut keys = std::collections::HashSet::new();
440 let mut partial = Vec::new();
441 for s in sols {
442 match jvars
443 .iter()
444 .map(|&i| s[i].clone())
445 .collect::<Option<Vec<crate::row::Val>>>()
446 {
447 Some(k) => {
448 keys.insert(k);
449 }
450 None => partial.push(s.clone()),
451 }
452 }
453 ExistsProbe {
454 svars,
455 jvars,
456 keys,
457 partial,
458 }
459}
460
461fn exists_matches(b: &crate::row::Row, entry: &ExistsEntry) -> bool {
465 let probe = entry.probe.as_ref().unwrap();
466 let bj: Vec<usize> = probe
467 .svars
468 .iter()
469 .copied()
470 .filter(|&i| b[i].is_some())
471 .collect();
472 if bj == probe.jvars {
473 let k: Vec<crate::row::Val> = probe.jvars.iter().map(|&i| b[i].clone().unwrap()).collect();
474 probe.keys.contains(&k)
475 || probe
476 .partial
477 .iter()
478 .any(|s| crate::row::compatible_rows(b, s))
479 } else {
480 entry.sols.iter().any(|s| crate::row::compatible_rows(b, s))
481 }
482}
483
484fn lexical(token: &str) -> String {
491 crate::terms::literal_lexical(token).unwrap_or_else(|| token.to_string())
492}
493
494pub(crate) fn term_number(s: &str) -> Option<f64> {
499 value::numeric(s)
500}
501
502use crate::terms::as_number;
503
504#[derive(Debug, Clone)]
506#[must_use]
507#[non_exhaustive]
508pub enum QueryOutput {
509 Select(Vec<String>, Vec<Binding>),
511 Ask(bool),
513 Construct(Vec<(String, String, String)>),
515}
516
517#[derive(Debug, Clone, PartialEq, Eq)]
520#[must_use]
521#[non_exhaustive]
522pub enum SummaryQueryShape {
523 PredicateCount { predicate: String, variable: String },
525 TripleCount { variable: String },
527 PredicateTotals {
529 predicate_variable: String,
530 count_variable: String,
531 },
532 PredicateList { variable: String },
534 PredicateDistinctCount { variable: String },
536 TripleExists,
538 PredicateExists { predicate: String },
540}
541
542#[derive(Debug, Clone, PartialEq, Eq)]
546pub struct RoutedTriplePattern {
547 pub subject: Option<String>,
548 pub predicate: Option<String>,
549 pub object: Option<String>,
550}
551
552pub fn routed_triple_pattern(query: &str) -> Result<Option<RoutedTriplePattern>, SparqlError> {
557 let parsed = parse_query(query)?;
558 let sel = match parsed {
559 Query::Select {
560 pattern, dataset, ..
561 } => lower_select(&pattern, &dataset)?,
562 Query::Ask { pattern, .. } => lower_pattern(&pattern)?,
563 Query::Construct { pattern, .. } => lower_pattern(&pattern)?,
564 Query::Describe { pattern, .. } => lower_pattern(&pattern)?,
565 };
566 if !sel.from.is_empty() || sel.from_named.is_some() {
567 return Ok(None);
568 }
569 let Plan::Bgp(patterns) = sel.plan else {
570 return Ok(None);
571 };
572 let [tp] = patterns.as_slice() else {
573 return Ok(None);
574 };
575 Ok(Some(RoutedTriplePattern {
576 subject: term_const(&tp.s),
577 predicate: term_const(&tp.p),
578 object: term_const(&tp.o),
579 }))
580}
581
582fn term_const(term: &PatternTerm) -> Option<String> {
583 match term {
584 PatternTerm::Const(t) => Some(t.clone()),
585 PatternTerm::Var(_) => None,
586 }
587}
588
589pub fn summary_query_shape(query: &str) -> Result<Option<SummaryQueryShape>, SparqlError> {
596 let parsed = parse_query(query)?;
597 match parsed {
598 Query::Select {
599 pattern, dataset, ..
600 } => {
601 let sel = lower_select(&pattern, &dataset)?;
602 if !sel.from.is_empty()
603 || sel.from_named.is_some()
604 || sel.offset != 0
605 || sel.limit.is_some()
606 || !sel.order.is_empty()
607 || !sel.having.is_empty()
608 {
609 return Ok(None);
610 }
611 if sel.distinct {
612 if sel.group.is_some() || !sel.extends.is_empty() {
613 return Ok(None);
614 }
615 let [projected] = sel.project.as_slice() else {
616 return Ok(None);
617 };
618 let Some(SummaryPatternShape::AnyPredicate { variable }) =
619 single_summary_pattern(&sel.plan)
620 else {
621 return Ok(None);
622 };
623 return if projected == &variable {
624 Ok(Some(SummaryQueryShape::PredicateList { variable }))
625 } else {
626 Ok(None)
627 };
628 }
629 let Some(group) = &sel.group else {
630 return Ok(None);
631 };
632 if group.aggs.len() != 1 {
633 return Ok(None);
634 }
635 match group.by.as_slice() {
636 [] => match &group.aggs[0].1 {
637 Agg::CountStar { distinct: false } => {
638 let Some(variable) = public_aggregate_variable(&sel, &group.aggs[0].0)
639 else {
640 return Ok(None);
641 };
642 Ok(single_summary_pattern(&sel.plan).map(|shape| match shape {
643 SummaryPatternShape::Predicate(predicate) => {
644 SummaryQueryShape::PredicateCount {
645 predicate,
646 variable,
647 }
648 }
649 SummaryPatternShape::AnyPredicate { .. } => {
650 SummaryQueryShape::TripleCount { variable }
651 }
652 }))
653 }
654 Agg::Count(counted, true) => {
655 let Some(public_variable) =
656 public_aggregate_variable(&sel, &group.aggs[0].0)
657 else {
658 return Ok(None);
659 };
660 let Some(SummaryPatternShape::AnyPredicate { variable }) =
661 single_summary_pattern(&sel.plan)
662 else {
663 return Ok(None);
664 };
665 if &variable != counted {
666 return Ok(None);
667 }
668 Ok(Some(SummaryQueryShape::PredicateDistinctCount {
669 variable: public_variable,
670 }))
671 }
672 _ => Ok(None),
673 },
674 [group_var] => {
675 if !matches!(group.aggs[0].1, Agg::CountStar { distinct: false }) {
676 return Ok(None);
677 }
678 let Some(SummaryPatternShape::AnyPredicate { variable }) =
679 single_summary_pattern(&sel.plan)
680 else {
681 return Ok(None);
682 };
683 if &variable != group_var {
684 return Ok(None);
685 }
686 let Some(count_variable) =
687 public_group_aggregate_variable(&sel, &group.aggs[0].0, group_var)
688 else {
689 return Ok(None);
690 };
691 Ok(Some(SummaryQueryShape::PredicateTotals {
692 predicate_variable: group_var.clone(),
693 count_variable,
694 }))
695 }
696 _ => Ok(None),
697 }
698 }
699 Query::Ask { pattern, .. } => {
700 let sel = lower_pattern(&pattern)?;
701 Ok(single_summary_pattern(&sel.plan).map(|shape| match shape {
702 SummaryPatternShape::Predicate(predicate) => {
703 SummaryQueryShape::PredicateExists { predicate }
704 }
705 SummaryPatternShape::AnyPredicate { .. } => SummaryQueryShape::TripleExists,
706 }))
707 }
708 Query::Construct { .. } | Query::Describe { .. } => Ok(None),
709 }
710}
711
712enum SummaryPatternShape {
713 Predicate(String),
714 AnyPredicate { variable: String },
715}
716
717fn single_summary_pattern(plan: &Plan) -> Option<SummaryPatternShape> {
718 let Plan::Bgp(patterns) = plan else {
719 return None;
720 };
721 let [tp] = patterns.as_slice() else {
722 return None;
723 };
724 let (PatternTerm::Var(s), PatternTerm::Var(o)) = (&tp.s, &tp.o) else {
725 return None;
726 };
727 if s == o {
728 return None;
729 }
730 match &tp.p {
731 PatternTerm::Const(p) => Some(SummaryPatternShape::Predicate(p.clone())),
732 PatternTerm::Var(p) if p != s && p != o => Some(SummaryPatternShape::AnyPredicate {
733 variable: p.clone(),
734 }),
735 _ => None,
736 }
737}
738
739fn public_aggregate_variable(sel: &Select, aggregate_var: &str) -> Option<String> {
740 let [projected] = sel.project.as_slice() else {
741 return None;
742 };
743 if projected == aggregate_var {
744 return Some(projected.clone());
745 }
746 sel.extends.iter().find_map(|(var, expr)| match expr {
747 FExpr::Var(source) if var == projected && source == aggregate_var => Some(var.clone()),
748 _ => None,
749 })
750}
751
752fn public_group_aggregate_variable(
753 sel: &Select,
754 aggregate_var: &str,
755 group_var: &str,
756) -> Option<String> {
757 let [projected_group, projected_aggregate] = sel.project.as_slice() else {
758 return None;
759 };
760 if projected_group != group_var {
761 return None;
762 }
763 if projected_aggregate == aggregate_var {
764 return Some(projected_aggregate.clone());
765 }
766 sel.extends.iter().find_map(|(var, expr)| match expr {
767 FExpr::Var(source) if var == projected_aggregate && source == aggregate_var => {
768 Some(var.clone())
769 }
770 _ => None,
771 })
772}
773
774#[derive(Debug, Clone, Copy)]
777pub struct CommunityPartial {
778 pub community: usize,
779 pub subjects: usize,
780 pub rows: usize,
781}
782
783pub type CommunitySelect = (Vec<String>, Vec<Binding>, Vec<CommunityPartial>);
786
787pub fn eval_select_communities(
798 rete: &Rete,
799 query: &str,
800 round: Option<usize>,
801) -> Result<CommunitySelect, SparqlError> {
802 let parsed = parse_query(query)?;
803 let out = match parsed {
804 Query::Select {
805 pattern, dataset, ..
806 } => run_select_communities(rete, &lower_select(&pattern, &dataset)?, round),
807 _ => Err(SparqlError::Unsupported(
808 "community-split evaluation supports SELECT queries only",
809 )),
810 };
811 match rete.take_service_error() {
814 Some(e) => Err(SparqlError::Service(e)),
815 None => out,
816 }
817}
818
819pub fn eval_query(rete: &Rete, query: &str) -> Result<QueryOutput, SparqlError> {
821 eval_query_with(rete, query, QueryOpts::default())
822}
823
824pub fn eval_query_reasoned(rete: &Rete, query: &str) -> Result<QueryOutput, SparqlError> {
829 eval_query_with(
830 rete,
831 query,
832 QueryOpts {
833 reason: true,
834 ..QueryOpts::default()
835 },
836 )
837}
838
839#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
843pub struct QueryOpts {
844 pub reason: bool,
846 pub union_default_graph: bool,
852}
853
854pub fn eval_query_with(
857 rete: &Rete,
858 query: &str,
859 opts: QueryOpts,
860) -> Result<QueryOutput, SparqlError> {
861 diag::begin();
865 let out = eval_query_inner(rete, query, opts);
866 match rete.take_service_error() {
870 Some(e) => Err(SparqlError::Service(e)),
871 None => out,
872 }
873}
874
875pub fn eval_query_with_warnings(
892 rete: &Rete,
893 query: &str,
894 opts: QueryOpts,
895) -> Result<(QueryOutput, Vec<QueryWarning>), SparqlError> {
896 let out = eval_query_with(rete, query, opts)?;
897 let warnings = diag::finish(&out);
898 Ok((out, warnings))
899}
900
901pub fn partition_plan(rete: &Rete, query: &str, var: &str) -> Result<PartitionPlan, SparqlError> {
917 partition::plan(rete, query, var)
918}
919
920pub fn eval_query_partitioned(
930 rete: &Rete,
931 query: &str,
932 opts: QueryOpts,
933 var: &str,
934 keys: &[String],
935) -> Result<(QueryOutput, Vec<QueryWarning>), SparqlError> {
936 diag::begin();
937 let out = eval_partition_inner(rete, query, opts, partition::var_name(var), keys);
938 let out = match rete.take_service_error() {
939 Some(e) => Err(SparqlError::Service(e)),
940 None => out,
941 }?;
942 let warnings = diag::finish(&out);
943 Ok((out, warnings))
944}
945
946fn eval_partition_inner(
947 rete: &Rete,
948 query: &str,
949 opts: QueryOpts,
950 var: &str,
951 keys: &[String],
952) -> Result<QueryOutput, SparqlError> {
953 let parsed = parse_query(query)?;
954 partition::check(&parsed, var)?;
955 let chunk = |sel: Select| -> Select {
958 let mut sel = maybe_reason(rete, apply_opts(sel, opts), opts.reason);
959 sel.offset = 0;
960 sel.limit = None;
961 sel.plan = partition::seed(sel.plan, var, keys);
962 sel
963 };
964 match parsed {
965 Query::Select {
966 pattern, dataset, ..
967 } => {
968 let (vars, rows) = run_select(rete, &chunk(lower_select(&pattern, &dataset)?));
969 Ok(QueryOutput::Select(vars, rows))
970 }
971 Query::Construct {
972 template, pattern, ..
973 } => {
974 let sel = chunk(lower_pattern(&pattern)?);
975 let (ctx, sols) = raw_solutions(rete, &sel);
976 Ok(QueryOutput::Construct(instantiate(&ctx, &template, &sols)))
977 }
978 _ => Err(SparqlError::Unsupported(
980 "only SELECT and CONSTRUCT can be split",
981 )),
982 }
983}
984
985fn maybe_reason(rete: &Rete, mut sel: Select, reason: bool) -> Select {
988 if reason {
989 let projected = sel.project.clone();
990 sel.plan = ql::reason_rewrite(sel.plan, rete, &projected);
991 }
992 sel
993}
994
995fn apply_opts(mut sel: Select, opts: QueryOpts) -> Select {
1000 sel.union_default = opts.union_default_graph;
1001 sel
1002}
1003
1004fn eval_query_inner(rete: &Rete, query: &str, opts: QueryOpts) -> Result<QueryOutput, SparqlError> {
1005 let reason = opts.reason;
1006 let parsed = parse_query(query)?;
1007 match parsed {
1008 Query::Select {
1009 pattern, dataset, ..
1010 } => {
1011 let (vars, rows) = run_select(
1012 rete,
1013 &maybe_reason(
1014 rete,
1015 apply_opts(lower_select(&pattern, &dataset)?, opts),
1016 reason,
1017 ),
1018 );
1019 Ok(QueryOutput::Select(vars, rows))
1020 }
1021 Query::Ask { pattern, .. } => {
1022 let sel = maybe_reason(rete, apply_opts(lower_pattern(&pattern)?, opts), reason);
1023 Ok(QueryOutput::Ask(ask_solution(rete, &sel)))
1024 }
1025 Query::Construct {
1026 template, pattern, ..
1027 } => {
1028 let sel = maybe_reason(rete, apply_opts(lower_pattern(&pattern)?, opts), reason);
1029 let (ctx, sols) = raw_solutions(rete, &sel);
1030 Ok(QueryOutput::Construct(instantiate(&ctx, &template, &sols)))
1031 }
1032 Query::Describe {
1033 pattern, dataset, ..
1034 } => {
1035 let sel = maybe_reason(
1038 rete,
1039 apply_opts(lower_select(&pattern, &dataset)?, opts),
1040 reason,
1041 );
1042 let (ctx, rows) = raw_solutions(rete, &sel);
1043 let mut resources = std::collections::BTreeSet::new();
1044 for row in &rows {
1045 if sel.project.is_empty() {
1046 for val in row.iter().flatten() {
1047 if let Some(t) = ctx.resolver.str_of(val) {
1048 resources.insert(t.to_string());
1049 }
1050 }
1051 } else {
1052 for v in &sel.project {
1053 if let Some(val) = ctx.slots.slot(v).and_then(|s| row[s].as_ref()) {
1054 if let Some(t) = ctx.resolver.str_of(val) {
1055 resources.insert(t.to_string());
1056 }
1057 }
1058 }
1059 }
1060 }
1061 let mut graphs: Vec<Option<&str>> = Vec::new();
1066 if !sel.from.is_empty() {
1067 graphs.extend(sel.from.iter().map(|g| Some(g.as_str())));
1068 } else {
1069 graphs.push(None);
1070 if sel.union_default {
1071 graphs.extend(rete.graph_names().into_iter().map(Some));
1072 }
1073 }
1074 let mut triples = std::collections::BTreeSet::new();
1075 for r in &resources {
1076 for g in &graphs {
1077 for t in rete.query_in_graph(*g, Some(r), None, None) {
1078 triples.insert(t);
1079 }
1080 }
1081 }
1082 Ok(QueryOutput::Construct(triples.into_iter().collect()))
1083 }
1084 }
1085}
1086
1087pub fn eval_sparql(rete: &Rete, query: &str) -> Result<(Vec<String>, Vec<Binding>), SparqlError> {
1091 eval_sparql_opts(rete, query, false)
1092}
1093
1094pub fn eval_sparql_reasoned(
1096 rete: &Rete,
1097 query: &str,
1098) -> Result<(Vec<String>, Vec<Binding>), SparqlError> {
1099 eval_sparql_opts(rete, query, true)
1100}
1101
1102fn eval_sparql_opts(
1103 rete: &Rete,
1104 query: &str,
1105 reason: bool,
1106) -> Result<(Vec<String>, Vec<Binding>), SparqlError> {
1107 let sel = maybe_reason(rete, parse_select(query)?, reason);
1108 let out = run_select(rete, &sel);
1109 match rete.take_service_error() {
1111 Some(e) => Err(SparqlError::Service(e)),
1112 None => Ok(out),
1113 }
1114}
1115
1116pub(crate) fn fmt_num_typed(x: f64) -> String {
1122 if x.fract() == 0.0 {
1123 format!(
1124 "\"{}\"^^<http://www.w3.org/2001/XMLSchema#integer>",
1125 x as i64
1126 )
1127 } else {
1128 let cleaned: f64 = format!("{x:.14e}").parse().unwrap_or(x);
1132 format!("\"{cleaned}\"^^<http://www.w3.org/2001/XMLSchema#decimal>")
1133 }
1134}
1135
1136fn reverse(ast: PathAst) -> PathAst {
1138 match ast {
1139 PathAst::Pred(p, r) => PathAst::Pred(p, !r),
1140 PathAst::Rep(inner, rep) => PathAst::Rep(Box::new(reverse(*inner)), rep),
1141 PathAst::Seq(a, b) => PathAst::Seq(Box::new(reverse(*b)), Box::new(reverse(*a))),
1142 PathAst::Alt(a, b) => PathAst::Alt(Box::new(reverse(*a)), Box::new(reverse(*b))),
1143 PathAst::NegatedSet(s, r) => PathAst::NegatedSet(s, !r),
1144 }
1145}
1146
1147#[cfg(test)]
1148mod tests {
1149 use super::*;
1150 use crate::dictionary::DictionaryBuilder;
1151 use crate::index::GraphIndexBuilder;
1152 use crate::write_file_v05 as write_file;
1153
1154 fn rete_from(triples: &[(&str, &str, &str)]) -> Vec<u8> {
1155 let mut db = DictionaryBuilder::new();
1156 for (s, p, o) in triples {
1157 db.observe(s, p, o);
1158 }
1159 let dict = db.build();
1160 let mut ib = GraphIndexBuilder::new();
1161 for (s, p, o) in triples {
1162 ib.push(dict.encode(s, p, o).unwrap());
1163 }
1164 write_file(&dict, &ib.build(), false, &[], 0)
1165 }
1166
1167 #[test]
1168 fn parses_select_with_two_patterns() {
1169 let q = r#"
1170 PREFIX ex: <http://ex/>
1171 SELECT ?x ?z WHERE { ?x ex:knows ?y . ?y ex:knows ?z }
1172 "#;
1173 let sel = parse_select(q).unwrap();
1174 assert_eq!(sel.project, vec!["x", "z"]);
1175 match &sel.plan {
1176 Plan::Bgp(p) => assert_eq!(p.len(), 2),
1177 other => panic!("expected a BGP plan, got {other:?}"),
1178 }
1179 }
1180
1181 #[test]
1182 fn evaluates_two_hop_select() {
1183 let bytes = rete_from(&[
1184 ("<http://ex/Alice>", "<http://ex/knows>", "<http://ex/Bob>"),
1185 ("<http://ex/Bob>", "<http://ex/knows>", "<http://ex/Carol>"),
1186 ]);
1187 let rete = Rete::open(&bytes).unwrap();
1188 let q = r#"PREFIX ex: <http://ex/>
1189 SELECT ?x ?z WHERE { ?x ex:knows ?y . ?y ex:knows ?z }"#;
1190 let (proj, sols) = eval_sparql(&rete, q).unwrap();
1191 assert_eq!(proj, vec!["x", "z"]);
1192 assert_eq!(sols.len(), 1);
1193 assert_eq!(sols[0]["x"], "<http://ex/Alice>");
1194 assert_eq!(sols[0]["z"], "<http://ex/Carol>");
1195 }
1196
1197 #[test]
1198 fn union_returns_both_sides() {
1199 let bytes = rete_from(&[
1200 ("<http://ex/Alice>", "<http://ex/likes>", "<http://ex/Tea>"),
1201 ("<http://ex/Bob>", "<http://ex/hates>", "<http://ex/Tea>"),
1202 ]);
1203 let rete = Rete::open(&bytes).unwrap();
1204 let q = "PREFIX ex: <http://ex/> SELECT ?p WHERE { \
1205 { ?p ex:likes ex:Tea } UNION { ?p ex:hates ex:Tea } }";
1206 let (_, sols) = eval_sparql(&rete, q).unwrap();
1207 let mut who: Vec<&str> = sols.iter().map(|b| b["p"].as_str()).collect();
1208 who.sort();
1209 assert_eq!(who, vec!["<http://ex/Alice>", "<http://ex/Bob>"]);
1210 }
1211
1212 #[test]
1213 fn optional_keeps_left_when_right_absent() {
1214 let bytes = rete_from(&[
1216 ("<http://ex/Alice>", "<http://ex/name>", "\"Alice\""),
1217 ("<http://ex/Bob>", "<http://ex/name>", "\"Bob\""),
1218 ("<http://ex/Alice>", "<http://ex/email>", "\"a@ex\""),
1219 ]);
1220 let rete = Rete::open(&bytes).unwrap();
1221 let q = "PREFIX ex: <http://ex/> SELECT ?p ?e WHERE { \
1222 ?p ex:name ?n . OPTIONAL { ?p ex:email ?e } }";
1223 let (_, sols) = eval_sparql(&rete, q).unwrap();
1224 assert_eq!(sols.len(), 2, "both people present");
1225 let alice = sols.iter().find(|b| b["p"] == "<http://ex/Alice>").unwrap();
1226 assert_eq!(alice["e"], "\"a@ex\"");
1227 let bob = sols.iter().find(|b| b["p"] == "<http://ex/Bob>").unwrap();
1228 assert!(!bob.contains_key("e"), "Bob has no email binding");
1229 }
1230
1231 #[test]
1232 fn numeric_filter_on_typed_literal() {
1233 let xsd = "<http://www.w3.org/2001/XMLSchema#integer>";
1235 let bytes = rete_from(&[
1236 (
1237 "<http://ex/Alice>",
1238 "<http://ex/age>",
1239 &format!("\"30\"^^{xsd}"),
1240 ),
1241 (
1242 "<http://ex/Bob>",
1243 "<http://ex/age>",
1244 &format!("\"25\"^^{xsd}"),
1245 ),
1246 ]);
1247 let rete = Rete::open(&bytes).unwrap();
1248 let q = "PREFIX ex: <http://ex/> \
1249 SELECT ?p WHERE { ?p ex:age ?age . FILTER(?age > 27) }";
1250 let (_, sols) = eval_sparql(&rete, q).unwrap();
1251 assert_eq!(sols.len(), 1);
1252 assert_eq!(sols[0]["p"], "<http://ex/Alice>");
1253 }
1254
1255 #[test]
1256 fn filter_equality_and_boolean_logic() {
1257 let bytes = rete_from(&[
1258 ("<http://ex/Alice>", "<http://ex/city>", "<http://ex/NYC>"),
1259 ("<http://ex/Bob>", "<http://ex/city>", "<http://ex/LA>"),
1260 ("<http://ex/Carol>", "<http://ex/city>", "<http://ex/NYC>"),
1261 ]);
1262 let rete = Rete::open(&bytes).unwrap();
1263 let q = "PREFIX ex: <http://ex/> \
1264 SELECT ?p WHERE { ?p ex:city ?c . FILTER(?c = ex:NYC && ?p != ex:Carol) }";
1265 let (_, sols) = eval_sparql(&rete, q).unwrap();
1266 assert_eq!(sols.len(), 1);
1267 assert_eq!(sols[0]["p"], "<http://ex/Alice>");
1268 }
1269
1270 #[test]
1271 fn distinct_collapses_duplicate_projections() {
1272 let bytes = rete_from(&[
1274 ("<http://ex/Alice>", "<http://ex/knows>", "<http://ex/Bob>"),
1275 (
1276 "<http://ex/Alice>",
1277 "<http://ex/knows>",
1278 "<http://ex/Carol>",
1279 ),
1280 ("<http://ex/Bob>", "<http://ex/knows>", "<http://ex/Dave>"),
1281 ("<http://ex/Carol>", "<http://ex/knows>", "<http://ex/Dave>"),
1282 ]);
1283 let rete = Rete::open(&bytes).unwrap();
1284 let base = "PREFIX ex: <http://ex/> SELECT {} ?z WHERE { ?x ex:knows ?y . ?y ex:knows ?z }";
1285
1286 let (_, non_distinct) = eval_sparql(&rete, &base.replace("{}", "")).unwrap();
1287 assert_eq!(non_distinct.len(), 2); let (proj, distinct) = eval_sparql(&rete, &base.replace("{}", "DISTINCT")).unwrap();
1290 assert_eq!(proj, vec!["z"]);
1291 assert_eq!(distinct.len(), 1);
1292 assert_eq!(distinct[0]["z"], "<http://ex/Dave>");
1293 assert!(!distinct[0].contains_key("x"));
1295 }
1296
1297 #[test]
1298 fn transitive_path_reachability() {
1299 let bytes = rete_from(&[
1301 ("<http://ex/A>", "<http://ex/k>", "<http://ex/B>"),
1302 ("<http://ex/B>", "<http://ex/k>", "<http://ex/C>"),
1303 ("<http://ex/C>", "<http://ex/k>", "<http://ex/D>"),
1304 ]);
1305 let rete = Rete::open(&bytes).unwrap();
1306
1307 let q = "PREFIX ex: <http://ex/> SELECT ?y WHERE { ex:A ex:k+ ?y }";
1309 let (_, sols) = eval_sparql(&rete, q).unwrap();
1310 let mut ys: Vec<&str> = sols.iter().map(|b| b["y"].as_str()).collect();
1311 ys.sort();
1312 assert_eq!(ys, vec!["<http://ex/B>", "<http://ex/C>", "<http://ex/D>"]);
1313
1314 let q0 = "PREFIX ex: <http://ex/> SELECT ?y WHERE { ex:A ex:k* ?y }";
1316 let (_, s0) = eval_sparql(&rete, q0).unwrap();
1317 assert!(s0.iter().any(|b| b["y"] == "<http://ex/A>"));
1318 assert_eq!(s0.len(), 4); }
1320
1321 #[test]
1322 fn sequence_and_alternative_paths() {
1323 let bytes = rete_from(&[
1325 ("<http://ex/Alice>", "<http://ex/parent>", "<http://ex/Bob>"),
1326 ("<http://ex/Bob>", "<http://ex/parent>", "<http://ex/Carol>"),
1327 (
1328 "<http://ex/Alice>",
1329 "<http://ex/stepparent>",
1330 "<http://ex/Dave>",
1331 ),
1332 ]);
1333 let rete = Rete::open(&bytes).unwrap();
1334
1335 let q = "PREFIX ex: <http://ex/> SELECT ?g WHERE { ex:Alice ex:parent/ex:parent ?g }";
1337 let (_, sols) = eval_sparql(&rete, q).unwrap();
1338 assert_eq!(sols.len(), 1);
1339 assert_eq!(sols[0]["g"], "<http://ex/Carol>");
1340
1341 let qa = "PREFIX ex: <http://ex/> \
1343 SELECT ?p WHERE { ex:Alice ex:parent|ex:stepparent ?p }";
1344 let (_, sa) = eval_sparql(&rete, qa).unwrap();
1345 let mut ps: Vec<&str> = sa.iter().map(|b| b["p"].as_str()).collect();
1346 ps.sort();
1347 assert_eq!(ps, vec!["<http://ex/Bob>", "<http://ex/Dave>"]);
1348 }
1349
1350 #[test]
1351 fn group_concat_aggregate() {
1352 let bytes = rete_from(&[
1353 ("<http://ex/Alice>", "<http://ex/knows>", "<http://ex/Bob>"),
1354 (
1355 "<http://ex/Alice>",
1356 "<http://ex/knows>",
1357 "<http://ex/Carol>",
1358 ),
1359 ]);
1360 let rete = Rete::open(&bytes).unwrap();
1361 let q = "PREFIX ex: <http://ex/> \
1362 SELECT (GROUP_CONCAT(STR(?f); SEPARATOR=\"|\") AS ?fs) WHERE { ex:Alice ex:knows ?f }";
1363 let (_, sols) = eval_sparql(&rete, q).unwrap();
1364 assert_eq!(sols.len(), 1);
1365 let fs = sols[0]["fs"].trim_matches('"');
1367 let mut parts: Vec<&str> = fs.split('|').collect();
1368 parts.sort();
1369 assert_eq!(parts, vec!["http://ex/Bob", "http://ex/Carol"]);
1370 let q = "PREFIX ex: <http://ex/> \n SELECT (GROUP_CONCAT(?f) AS ?fs) WHERE { ex:Alice ex:knows ?f }";
1372 let (_, sols) = eval_sparql(&rete, q).unwrap();
1373 assert_eq!(sols.len(), 1);
1374 assert_eq!(sols[0].get("fs"), None);
1375 }
1376
1377 #[test]
1378 fn group_by_having() {
1379 let bytes = rete_from(&[
1381 ("<http://ex/Alice>", "<http://ex/knows>", "<http://ex/Bob>"),
1382 (
1383 "<http://ex/Alice>",
1384 "<http://ex/knows>",
1385 "<http://ex/Carol>",
1386 ),
1387 ("<http://ex/Bob>", "<http://ex/knows>", "<http://ex/Carol>"),
1388 ]);
1389 let rete = Rete::open(&bytes).unwrap();
1390 let q = "PREFIX ex: <http://ex/> SELECT ?p (COUNT(?f) AS ?n) \
1392 WHERE { ?p ex:knows ?f } GROUP BY ?p HAVING (COUNT(?f) > 1)";
1393 let (_, sols) = eval_sparql(&rete, q).unwrap();
1394 assert_eq!(sols.len(), 1);
1395 assert_eq!(sols[0]["p"], "<http://ex/Alice>");
1396 assert_eq!(
1397 sols[0]["n"],
1398 "\"2\"^^<http://www.w3.org/2001/XMLSchema#integer>"
1399 );
1400 }
1401
1402 #[test]
1403 fn count_group_by() {
1404 let bytes = rete_from(&[
1406 ("<http://ex/Alice>", "<http://ex/knows>", "<http://ex/Bob>"),
1407 (
1408 "<http://ex/Alice>",
1409 "<http://ex/knows>",
1410 "<http://ex/Carol>",
1411 ),
1412 ("<http://ex/Bob>", "<http://ex/knows>", "<http://ex/Carol>"),
1413 ]);
1414 let rete = Rete::open(&bytes).unwrap();
1415 let q = "PREFIX ex: <http://ex/> \
1416 SELECT ?p (COUNT(?f) AS ?n) WHERE { ?p ex:knows ?f } GROUP BY ?p";
1417 let (_, sols) = eval_sparql(&rete, q).unwrap();
1418 let mut counts: Vec<(String, String)> = sols
1419 .iter()
1420 .map(|b| (b["p"].clone(), b["n"].clone()))
1421 .collect();
1422 counts.sort();
1423 assert_eq!(
1424 counts,
1425 vec![
1426 (
1427 "<http://ex/Alice>".into(),
1428 "\"2\"^^<http://www.w3.org/2001/XMLSchema#integer>".into()
1429 ),
1430 (
1431 "<http://ex/Bob>".into(),
1432 "\"1\"^^<http://www.w3.org/2001/XMLSchema#integer>".into()
1433 ),
1434 ]
1435 );
1436 }
1437
1438 #[test]
1439 fn global_count_star() {
1440 let bytes = rete_from(&[
1441 ("<http://ex/a>", "<http://ex/p>", "<http://ex/1>"),
1442 ("<http://ex/b>", "<http://ex/p>", "<http://ex/2>"),
1443 ]);
1444 let rete = Rete::open(&bytes).unwrap();
1445 let (_, sols) = eval_sparql(&rete, "SELECT (COUNT(*) AS ?n) WHERE { ?s ?p ?o }").unwrap();
1446 assert_eq!(sols.len(), 1);
1447 assert_eq!(
1448 sols[0]["n"],
1449 "\"2\"^^<http://www.w3.org/2001/XMLSchema#integer>"
1450 );
1451 }
1452
1453 #[test]
1454 fn summary_query_shape_classifies_only_exact_predicate_totals() {
1455 let count = summary_query_shape(
1456 "PREFIX ex: <http://ex/> SELECT (COUNT(*) AS ?n) WHERE { ?s ex:p ?o }",
1457 )
1458 .unwrap();
1459 assert_eq!(
1460 count,
1461 Some(SummaryQueryShape::PredicateCount {
1462 predicate: "<http://ex/p>".into(),
1463 variable: "n".into(),
1464 })
1465 );
1466
1467 let total = summary_query_shape("SELECT (COUNT(*) AS ?n) WHERE { ?s ?p ?o }").unwrap();
1468 assert_eq!(
1469 total,
1470 Some(SummaryQueryShape::TripleCount {
1471 variable: "n".into(),
1472 })
1473 );
1474
1475 let by_pred =
1476 summary_query_shape("SELECT ?p (COUNT(*) AS ?n) WHERE { ?s ?p ?o } GROUP BY ?p")
1477 .unwrap();
1478 assert_eq!(
1479 by_pred,
1480 Some(SummaryQueryShape::PredicateTotals {
1481 predicate_variable: "p".into(),
1482 count_variable: "n".into(),
1483 })
1484 );
1485
1486 let predicates = summary_query_shape("SELECT DISTINCT ?p WHERE { ?s ?p ?o }").unwrap();
1487 assert_eq!(
1488 predicates,
1489 Some(SummaryQueryShape::PredicateList {
1490 variable: "p".into(),
1491 })
1492 );
1493
1494 let predicate_count =
1495 summary_query_shape("SELECT (COUNT(DISTINCT ?p) AS ?n) WHERE { ?s ?p ?o }").unwrap();
1496 assert_eq!(
1497 predicate_count,
1498 Some(SummaryQueryShape::PredicateDistinctCount {
1499 variable: "n".into(),
1500 })
1501 );
1502
1503 let ask = summary_query_shape("PREFIX ex: <http://ex/> ASK { ?s ex:p ?o }").unwrap();
1504 assert_eq!(
1505 ask,
1506 Some(SummaryQueryShape::PredicateExists {
1507 predicate: "<http://ex/p>".into(),
1508 })
1509 );
1510
1511 let any_ask = summary_query_shape("ASK { ?s ?p ?o }").unwrap();
1512 assert_eq!(any_ask, Some(SummaryQueryShape::TripleExists));
1513
1514 let constrained =
1515 summary_query_shape("PREFIX ex: <http://ex/> ASK { ex:a ex:p ?o }").unwrap();
1516 assert_eq!(constrained, None);
1517
1518 let filtered =
1519 summary_query_shape("PREFIX ex: <http://ex/> ASK { ?s ex:p ?o FILTER(?s = ?o) }")
1520 .unwrap();
1521 assert_eq!(filtered, None);
1522 }
1523
1524 #[test]
1525 fn filter_exists_and_not_exists() {
1526 let bytes = rete_from(&[
1528 ("<http://ex/Alice>", "<http://ex/knows>", "<http://ex/Bob>"),
1529 (
1530 "<http://ex/Alice>",
1531 "<http://ex/knows>",
1532 "<http://ex/Carol>",
1533 ),
1534 ("<http://ex/Bob>", "<http://ex/knows>", "<http://ex/Dave>"),
1535 ]);
1536 let rete = Rete::open(&bytes).unwrap();
1537
1538 let q_exists = "PREFIX ex: <http://ex/> SELECT ?f WHERE { \
1540 ex:Alice ex:knows ?f . FILTER EXISTS { ?f ex:knows ?x } }";
1541 let (_, e) = eval_sparql(&rete, q_exists).unwrap();
1542 assert_eq!(
1543 e.iter().map(|b| b["f"].as_str()).collect::<Vec<_>>(),
1544 vec!["<http://ex/Bob>"]
1545 );
1546
1547 let q_not = "PREFIX ex: <http://ex/> SELECT ?f WHERE { \
1549 ex:Alice ex:knows ?f . FILTER NOT EXISTS { ?f ex:knows ?x } }";
1550 let (_, n) = eval_sparql(&rete, q_not).unwrap();
1551 assert_eq!(
1552 n.iter().map(|b| b["f"].as_str()).collect::<Vec<_>>(),
1553 vec!["<http://ex/Carol>"]
1554 );
1555 }
1556
1557 #[test]
1558 fn ask_repeated_variable_pattern() {
1559 let yes = rete_from(&[
1562 ("<http://ex/Alice>", "<http://ex/knows>", "<http://ex/Bob>"),
1563 ("<http://ex/Bob>", "<http://ex/knows>", "<http://ex/Bob>"),
1564 ]);
1565 let rete = Rete::open(&yes).unwrap();
1566 match eval_query(&rete, "PREFIX ex: <http://ex/> ASK { ?x ex:knows ?x }").unwrap() {
1567 QueryOutput::Ask(b) => assert!(b, "Bob knows himself"),
1568 other => panic!("expected Ask, got {other:?}"),
1569 }
1570 let no = rete_from(&[("<http://ex/Alice>", "<http://ex/knows>", "<http://ex/Bob>")]);
1573 let rete = Rete::open(&no).unwrap();
1574 match eval_query(&rete, "PREFIX ex: <http://ex/> ASK { ?x ex:knows ?x }").unwrap() {
1575 QueryOutput::Ask(b) => assert!(!b, "nobody knows themselves"),
1576 other => panic!("expected Ask, got {other:?}"),
1577 }
1578 }
1579
1580 #[test]
1581 fn minus_excludes_compatible() {
1582 let bytes = rete_from(&[
1584 ("<http://ex/Alice>", "<http://ex/knows>", "<http://ex/Bob>"),
1585 (
1586 "<http://ex/Alice>",
1587 "<http://ex/knows>",
1588 "<http://ex/Carol>",
1589 ),
1590 ("<http://ex/Bob>", "<http://ex/knows>", "<http://ex/Carol>"),
1591 ]);
1592 let rete = Rete::open(&bytes).unwrap();
1593 let q = "PREFIX ex: <http://ex/> SELECT ?f WHERE { \
1595 ex:Alice ex:knows ?f . MINUS { ?f ex:knows ?x } }";
1596 let (_, sols) = eval_sparql(&rete, q).unwrap();
1597 let fs: Vec<&str> = sols.iter().map(|b| b["f"].as_str()).collect();
1598 assert_eq!(fs, vec!["<http://ex/Carol>"]);
1599 }
1600
1601 #[test]
1602 fn filter_exists_disjoint_variable() {
1603 let bytes = rete_from(&[
1608 ("<http://ex/Alice>", "<http://ex/a>", "<http://ex/Person>"),
1609 ("<http://ex/Bob>", "<http://ex/a>", "<http://ex/Person>"),
1610 ("<http://ex/Tea>", "<http://ex/a>", "<http://ex/Drink>"),
1611 ]);
1612 let rete = Rete::open(&bytes).unwrap();
1613 let q_none = "PREFIX ex: <http://ex/> SELECT ?x WHERE { \
1614 ?x ex:a ex:Person FILTER NOT EXISTS { ?y ex:a ex:Drink } }";
1615 assert!(eval_sparql(&rete, q_none).unwrap().1.is_empty());
1616 let q_all = "PREFIX ex: <http://ex/> SELECT ?x WHERE { \
1617 ?x ex:a ex:Person FILTER EXISTS { ?y ex:a ex:Drink } }";
1618 assert_eq!(eval_sparql(&rete, q_all).unwrap().1.len(), 2);
1619 }
1620
1621 #[test]
1622 fn minus_disjoint_domain_keeps_all() {
1623 let bytes = rete_from(&[
1627 ("<http://ex/Alice>", "<http://ex/a>", "<http://ex/Person>"),
1628 ("<http://ex/Bob>", "<http://ex/a>", "<http://ex/Person>"),
1629 ("<http://ex/Tea>", "<http://ex/a>", "<http://ex/Drink>"),
1630 ]);
1631 let rete = Rete::open(&bytes).unwrap();
1632 let q = "PREFIX ex: <http://ex/> SELECT ?x WHERE { \
1633 ?x ex:a ex:Person MINUS { ?y ex:a ex:Drink } }";
1634 let (_, sols) = eval_sparql(&rete, q).unwrap();
1635 let mut xs: Vec<&str> = sols.iter().map(|b| b["x"].as_str()).collect();
1636 xs.sort();
1637 assert_eq!(xs, vec!["<http://ex/Alice>", "<http://ex/Bob>"]);
1638 }
1639
1640 #[test]
1641 fn values_pushdown_selects_subset() {
1642 let bytes = rete_from(&[
1645 ("<http://ex/a>", "<http://ex/d>", "<http://ex/Bio>"),
1646 ("<http://ex/b>", "<http://ex/d>", "<http://ex/Phys>"),
1647 ("<http://ex/c>", "<http://ex/d>", "<http://ex/Chem>"),
1648 ]);
1649 let rete = Rete::open(&bytes).unwrap();
1650 let q = "PREFIX ex: <http://ex/> SELECT ?p ?disc WHERE { \
1651 VALUES ?disc { ex:Bio ex:Phys } ?p ex:d ?disc }";
1652 let (_, sols) = eval_sparql(&rete, q).unwrap();
1653 let mut got: Vec<(String, String)> = sols
1654 .iter()
1655 .map(|b| (b["p"].clone(), b["disc"].clone()))
1656 .collect();
1657 got.sort();
1658 assert_eq!(
1659 got,
1660 vec![
1661 ("<http://ex/a>".into(), "<http://ex/Bio>".into()),
1662 ("<http://ex/b>".into(), "<http://ex/Phys>".into()),
1663 ]
1664 );
1665 }
1666
1667 #[test]
1668 fn values_inline_data_joins() {
1669 let bytes = rete_from(&[
1670 ("<http://ex/Alice>", "<http://ex/knows>", "<http://ex/Bob>"),
1671 (
1672 "<http://ex/Alice>",
1673 "<http://ex/knows>",
1674 "<http://ex/Carol>",
1675 ),
1676 ("<http://ex/Dave>", "<http://ex/knows>", "<http://ex/Eve>"),
1677 ]);
1678 let rete = Rete::open(&bytes).unwrap();
1679 let q = "PREFIX ex: <http://ex/> \
1681 SELECT ?f WHERE { VALUES ?p { ex:Alice } ?p ex:knows ?f }";
1682 let (_, sols) = eval_sparql(&rete, q).unwrap();
1683 let mut fs: Vec<&str> = sols.iter().map(|b| b["f"].as_str()).collect();
1684 fs.sort();
1685 assert_eq!(fs, vec!["<http://ex/Bob>", "<http://ex/Carol>"]);
1686 }
1687
1688 #[test]
1689 fn graph_queries_over_named_graphs() {
1690 use crate::write_dataset_v05 as write_dataset;
1691 let mut db = DictionaryBuilder::new();
1693 let edges = [
1694 ("<http://ex/Alice>", "<http://ex/knows>", "<http://ex/Bob>"),
1695 ("<http://ex/Bob>", "<http://ex/age>", "\"25\""),
1696 ];
1697 for (s, p, o) in edges {
1698 db.observe(s, p, o);
1699 }
1700 let dict = db.build();
1701 let mut social = GraphIndexBuilder::new();
1702 social.push(dict.encode(edges[0].0, edges[0].1, edges[0].2).unwrap());
1703 let mut profile = GraphIndexBuilder::new();
1704 profile.push(dict.encode(edges[1].0, edges[1].1, edges[1].2).unwrap());
1705 let named = vec![
1706 ("<http://ex/social>".to_string(), social.build()),
1707 ("<http://ex/profile>".to_string(), profile.build()),
1708 ];
1709 let bytes = write_dataset(
1710 &dict,
1711 &GraphIndexBuilder::new().build(),
1712 &named,
1713 true,
1714 &[],
1715 0,
1716 );
1717 let rete = Rete::open(&bytes).unwrap();
1718
1719 let q = "PREFIX ex: <http://ex/> \
1721 SELECT ?f WHERE { GRAPH ex:social { ex:Alice ex:knows ?f } }";
1722 let (_, s) = eval_sparql(&rete, q).unwrap();
1723 assert_eq!(s.len(), 1);
1724 assert_eq!(s[0]["f"], "<http://ex/Bob>");
1725
1726 let q2 = "PREFIX ex: <http://ex/> \
1728 SELECT ?g WHERE { GRAPH ?g { ex:Bob ex:age ?a } }";
1729 let (_, s2) = eval_sparql(&rete, q2).unwrap();
1730 assert_eq!(s2.len(), 1);
1731 assert_eq!(s2[0]["g"], "<http://ex/profile>");
1732
1733 let q3 = "PREFIX ex: <http://ex/> SELECT ?f WHERE { \
1736 GRAPH ex:profile { ?f ex:age ?a . FILTER EXISTS { ?f ex:age ?a2 } } }";
1737 assert_eq!(eval_sparql(&rete, q3).unwrap().1.len(), 1);
1738 let q4 = "PREFIX ex: <http://ex/> SELECT ?s WHERE { \
1739 GRAPH ex:social { ?s ex:knows ?o . FILTER NOT EXISTS { ?s ex:age ?a } } }";
1740 assert_eq!(eval_sparql(&rete, q4).unwrap().1.len(), 1);
1742 }
1743
1744 #[test]
1745 fn from_unions_named_graphs() {
1746 use crate::write_dataset_v05 as write_dataset;
1747 let mut db = DictionaryBuilder::new();
1750 let t = [
1751 ("<http://ex/Alice>", "<http://ex/knows>", "<http://ex/Bob>"),
1752 ("<http://ex/Bob>", "<http://ex/knows>", "<http://ex/Carol>"),
1753 ];
1754 for (s, p, o) in t {
1755 db.observe(s, p, o);
1756 }
1757 let dict = db.build();
1758 let mut g1 = GraphIndexBuilder::new();
1759 g1.push(dict.encode(t[0].0, t[0].1, t[0].2).unwrap());
1760 let mut g2 = GraphIndexBuilder::new();
1761 g2.push(dict.encode(t[1].0, t[1].1, t[1].2).unwrap());
1762 let named = vec![
1763 ("<http://ex/social>".to_string(), g1.build()),
1764 ("<http://ex/profile>".to_string(), g2.build()),
1765 ];
1766 let bytes = write_dataset(
1767 &dict,
1768 &GraphIndexBuilder::new().build(),
1769 &named,
1770 true,
1771 &[],
1772 0,
1773 );
1774 let rete = Rete::open(&bytes).unwrap();
1775
1776 let q0 = "PREFIX ex: <http://ex/> SELECT ?z WHERE { ?x ex:knows ?y . ?y ex:knows ?z }";
1778 assert!(eval_sparql(&rete, q0).unwrap().1.is_empty());
1779
1780 let q = "PREFIX ex: <http://ex/> \
1782 SELECT ?z FROM ex:social FROM ex:profile \
1783 WHERE { ?x ex:knows ?y . ?y ex:knows ?z }";
1784 let (_, s) = eval_sparql(&rete, q).unwrap();
1785 assert_eq!(s.len(), 1);
1786 assert_eq!(s[0]["z"], "<http://ex/Carol>");
1787
1788 let qn = "PREFIX ex: <http://ex/> SELECT ?g FROM NAMED ex:social \
1790 WHERE { GRAPH ?g { ?x ex:knows ?y } }";
1791 let (_, sn) = eval_sparql(&rete, qn).unwrap();
1792 let gs: Vec<&str> = sn.iter().map(|b| b["g"].as_str()).collect();
1793 assert_eq!(gs, vec!["<http://ex/social>"]); }
1795
1796 #[test]
1797 fn union_default_graph_opt_in() {
1798 use crate::write_dataset_v05 as write_dataset;
1799 let mut db = DictionaryBuilder::new();
1803 let t = [
1804 ("<http://ex/Root>", "<http://ex/knows>", "<http://ex/Alice>"),
1805 ("<http://ex/Alice>", "<http://ex/knows>", "<http://ex/Bob>"),
1806 ("<http://ex/Bob>", "<http://ex/knows>", "<http://ex/Carol>"),
1807 ];
1808 for (s, p, o) in t {
1809 db.observe(s, p, o);
1810 }
1811 let dict = db.build();
1812 let enc = |i: usize| dict.encode(t[i].0, t[i].1, t[i].2).unwrap();
1813 let mut def = GraphIndexBuilder::new();
1814 def.push(enc(0));
1815 let mut g1 = GraphIndexBuilder::new();
1816 g1.push(enc(1));
1817 let mut g2 = GraphIndexBuilder::new();
1818 g2.push(enc(1)); g2.push(enc(2));
1820 let named = vec![
1821 ("<http://ex/social>".to_string(), g1.build()),
1822 ("<http://ex/profile>".to_string(), g2.build()),
1823 ];
1824 let bytes = write_dataset(&dict, &def.build(), &named, true, &[], 0);
1825 let rete = Rete::open(&bytes).unwrap();
1826 let union = QueryOpts {
1827 union_default_graph: true,
1828 ..QueryOpts::default()
1829 };
1830 let rows = |out: QueryOutput| match out {
1831 QueryOutput::Select(_, rows) => rows,
1832 other => panic!("expected Select, got {other:?}"),
1833 };
1834
1835 let q = "PREFIX ex: <http://ex/> SELECT ?s ?o WHERE { ?s ex:knows ?o }";
1839 assert_eq!(rows(eval_query(&rete, q).unwrap()).len(), 1);
1840
1841 let got = rows(eval_query_with(&rete, q, union).unwrap());
1845 assert_eq!(got.len(), 3);
1846 assert!(got.iter().any(|b| b["s"] == "<http://ex/Root>"));
1847
1848 let qj = "PREFIX ex: <http://ex/> SELECT ?z WHERE { \
1850 ex:Root ex:knows ?x . ?x ex:knows ?y . ?y ex:knows ?z }";
1851 let sj = rows(eval_query_with(&rete, qj, union).unwrap());
1852 assert_eq!(sj.len(), 1);
1853 assert_eq!(sj[0]["z"], "<http://ex/Carol>");
1854
1855 let qg = "PREFIX ex: <http://ex/> SELECT DISTINCT ?g WHERE { GRAPH ?g { ?s ex:knows ?o } }";
1857 assert_eq!(rows(eval_query_with(&rete, qg, union).unwrap()).len(), 2);
1858
1859 let qf = "PREFIX ex: <http://ex/> SELECT ?s ?o FROM ex:social WHERE { ?s ex:knows ?o }";
1862 let sf = rows(eval_query_with(&rete, qf, union).unwrap());
1863 assert_eq!(sf.len(), 1);
1864 assert_eq!(sf[0]["s"], "<http://ex/Alice>");
1865
1866 let mut db2 = DictionaryBuilder::new();
1869 db2.observe(t[1].0, t[1].1, t[1].2);
1870 let dict2 = db2.build();
1871 let mut only = GraphIndexBuilder::new();
1872 only.push(dict2.encode(t[1].0, t[1].1, t[1].2).unwrap());
1873 let named2 = vec![("<http://ex/only>".to_string(), only.build())];
1874 let bytes2 = write_dataset(
1875 &dict2,
1876 &GraphIndexBuilder::new().build(),
1877 &named2,
1878 true,
1879 &[],
1880 0,
1881 );
1882 let rete2 = Rete::open(&bytes2).unwrap();
1883 assert_eq!(rows(eval_query(&rete2, q).unwrap()).len(), 0); assert_eq!(rows(eval_query_with(&rete2, q, union).unwrap()).len(), 1);
1885 }
1886
1887 #[test]
1888 fn describe_resource() {
1889 let bytes = rete_from(&[
1890 ("<http://ex/Alice>", "<http://ex/knows>", "<http://ex/Bob>"),
1891 ("<http://ex/Alice>", "<http://ex/age>", "\"30\""),
1892 ("<http://ex/Bob>", "<http://ex/age>", "\"25\""),
1893 ]);
1894 let rete = Rete::open(&bytes).unwrap();
1895 match eval_query(&rete, "DESCRIBE <http://ex/Alice>").unwrap() {
1897 QueryOutput::Construct(t) => assert_eq!(t.len(), 2),
1898 other => panic!("expected Construct, got {other:?}"),
1899 }
1900 let q = "PREFIX ex: <http://ex/> DESCRIBE ?x WHERE { ?x ex:age ?a }";
1902 match eval_query(&rete, q).unwrap() {
1903 QueryOutput::Construct(t) => {
1904 assert_eq!(t.len(), 3);
1906 }
1907 other => panic!("expected Construct, got {other:?}"),
1908 }
1909 }
1910
1911 #[test]
1912 fn ask_and_construct() {
1913 let bytes = rete_from(&[
1914 ("<http://ex/Alice>", "<http://ex/knows>", "<http://ex/Bob>"),
1915 ("<http://ex/Bob>", "<http://ex/knows>", "<http://ex/Carol>"),
1916 ]);
1917 let rete = Rete::open(&bytes).unwrap();
1918
1919 match eval_query(&rete, "PREFIX ex: <http://ex/> ASK { ?a ex:knows ?b }").unwrap() {
1921 QueryOutput::Ask(b) => assert!(b),
1922 other => panic!("expected Ask, got {other:?}"),
1923 }
1924 match eval_query(&rete, "PREFIX ex: <http://ex/> ASK { ?a ex:likes ?b }").unwrap() {
1925 QueryOutput::Ask(b) => assert!(!b),
1926 other => panic!("expected Ask, got {other:?}"),
1927 }
1928
1929 let q = "PREFIX ex: <http://ex/> \
1931 CONSTRUCT { ?b ex:knownBy ?a } WHERE { ?a ex:knows ?b }";
1932 match eval_query(&rete, q).unwrap() {
1933 QueryOutput::Construct(mut triples) => {
1934 triples.sort();
1935 assert_eq!(triples.len(), 2);
1936 assert!(triples.contains(&(
1937 "<http://ex/Bob>".into(),
1938 "<http://ex/knownBy>".into(),
1939 "<http://ex/Alice>".into(),
1940 )));
1941 }
1942 other => panic!("expected Construct, got {other:?}"),
1943 }
1944 }
1945
1946 #[test]
1947 fn substr_strbefore_strafter() {
1948 let bytes = rete_from(&[("<http://ex/a>", "<http://ex/name>", "\"Alice Smith\"")]);
1949 let rete = Rete::open(&bytes).unwrap();
1950 let q = "PREFIX ex: <http://ex/> SELECT ?first ?last ?ini WHERE { \
1951 ?p ex:name ?n . \
1952 BIND(STRBEFORE(?n, \" \") AS ?first) \
1953 BIND(STRAFTER(?n, \" \") AS ?last) \
1954 BIND(SUBSTR(?n, 1, 1) AS ?ini) }";
1955 let (_, sols) = eval_sparql(&rete, q).unwrap();
1956 assert_eq!(sols[0]["first"], "\"Alice\"");
1958 assert_eq!(sols[0]["last"], "\"Smith\"");
1959 assert_eq!(sols[0]["ini"], "\"A\"");
1960 }
1961
1962 #[test]
1963 fn concat_and_coalesce() {
1964 let bytes = rete_from(&[
1966 ("<http://ex/Alice>", "<http://ex/name>", "\"Alice\""),
1967 ("<http://ex/Alice>", "<http://ex/nick>", "\"Al\""),
1968 ("<http://ex/Bob>", "<http://ex/name>", "\"Bob\""),
1969 ]);
1970 let rete = Rete::open(&bytes).unwrap();
1971 let q = "PREFIX ex: <http://ex/> SELECT ?label WHERE { \
1973 ?p ex:name ?name . OPTIONAL { ?p ex:nick ?nick } \
1974 BIND(CONCAT(\"@\", COALESCE(?nick, ?name)) AS ?label) }";
1975 let (_, sols) = eval_sparql(&rete, q).unwrap();
1976 let mut labels: Vec<&str> = sols.iter().map(|b| b["label"].as_str()).collect();
1977 labels.sort();
1978 assert_eq!(labels, vec!["\"@Al\"", "\"@Bob\""]);
1979 }
1980
1981 #[test]
1982 fn builtin_functions() {
1983 let bytes = rete_from(&[
1984 ("<http://ex/Alice>", "<http://ex/name>", "\"Alice Smith\""),
1985 ("<http://ex/Bob>", "<http://ex/name>", "\"Bob Jones\""),
1986 ]);
1987 let rete = Rete::open(&bytes).unwrap();
1988 let q = "PREFIX ex: <http://ex/> SELECT ?p ?len WHERE { \
1990 ?p ex:name ?n . FILTER(CONTAINS(?n, \"Smith\")) BIND(STRLEN(?n) AS ?len) }";
1991 let (_, sols) = eval_sparql(&rete, q).unwrap();
1992 assert_eq!(sols.len(), 1);
1993 assert_eq!(sols[0]["p"], "<http://ex/Alice>");
1994 assert_eq!(
1995 sols[0]["len"],
1996 "\"11\"^^<http://www.w3.org/2001/XMLSchema#integer>"
1997 ); }
1999
2000 #[test]
2001 fn geosparql_filter_and_functions() {
2002 let wkt = "\"POLYGON((0 0,10 0,10 10,0 10,0 0))\"^^\
2003 <http://www.opengis.net/ont/geosparql#wktLiteral>";
2004 let bytes = rete_from(&[
2005 (
2006 "<http://ex/f>",
2007 "<http://www.opengis.net/ont/geosparql#hasGeometry>",
2008 "<http://ex/f/g>",
2009 ),
2010 (
2011 "<http://ex/f/g>",
2012 "<http://www.opengis.net/ont/geosparql#asWKT>",
2013 wkt,
2014 ),
2015 (
2016 "<http://ex/f>",
2017 "<http://ex/year>",
2018 "\"1815\"^^<http://www.w3.org/2001/XMLSchema#integer>",
2019 ),
2020 ]);
2021 let rete = Rete::open(&bytes).unwrap();
2022 let pre = "PREFIX geo: <http://www.opengis.net/ont/geosparql#> \
2023 PREFIX geof: <http://www.opengis.net/def/function/geosparql/> \
2024 PREFIX uom: <http://www.opengis.net/def/uom/OGC/1.0/> PREFIX ex: <http://ex/> ";
2025
2026 let (_, s) = eval_sparql(
2028 &rete,
2029 &format!(
2030 "{pre}SELECT ?f WHERE {{ ?f ex:year ?y ; \
2031 geo:hasGeometry/geo:asWKT ?w . \
2032 FILTER(?y = 1815 && geof:sfContains(?w, \"POINT(5 5)\"^^geo:wktLiteral)) }}"
2033 ),
2034 )
2035 .unwrap();
2036 assert_eq!(s.len(), 1, "point inside the polygon in year 1815");
2037 assert_eq!(s[0]["f"], "<http://ex/f>");
2038
2039 let (_, s) = eval_sparql(
2041 &rete,
2042 &format!(
2043 "{pre}SELECT ?f WHERE {{ \
2044 ?f geo:hasGeometry/geo:asWKT ?w . \
2045 FILTER(geof:sfContains(?w, \"POINT(50 50)\"^^geo:wktLiteral)) }}"
2046 ),
2047 )
2048 .unwrap();
2049 assert!(s.is_empty());
2050
2051 let (_, s) = eval_sparql(
2053 &rete,
2054 &format!(
2055 "{pre}SELECT ?f WHERE {{ \
2056 ?f geo:hasGeometry/geo:asWKT ?w . \
2057 FILTER(geof:sfWithin(\"POINT(5 5)\"^^geo:wktLiteral, ?w)) }}"
2058 ),
2059 )
2060 .unwrap();
2061 assert_eq!(s.len(), 1);
2062
2063 let (_, s) = eval_sparql(
2065 &rete,
2066 &format!(
2067 "{pre}SELECT ?f WHERE {{ \
2068 ?f geo:hasGeometry/geo:asWKT ?w . \
2069 FILTER(geof:sfContains(?w, \"garbage\"^^geo:wktLiteral)) }}"
2070 ),
2071 )
2072 .unwrap();
2073 assert!(s.is_empty());
2074
2075 let (_, s) = eval_sparql(
2077 &rete,
2078 &format!(
2079 "{pre}SELECT ?hit WHERE {{ \
2080 ?f geo:hasGeometry/geo:asWKT ?w . \
2081 BIND(geof:sfContains(?w, \"POINT(5 5)\"^^geo:wktLiteral) AS ?hit) }}"
2082 ),
2083 )
2084 .unwrap();
2085 assert_eq!(
2086 s[0]["hit"],
2087 "\"true\"^^<http://www.w3.org/2001/XMLSchema#boolean>"
2088 );
2089
2090 let (_, s) = eval_sparql(
2092 &rete,
2093 &format!(
2094 "{pre}SELECT ?d WHERE {{ BIND(geof:distance(\
2095 \"POINT(0 0)\"^^geo:wktLiteral, \"POINT(0 1)\"^^geo:wktLiteral, uom:metre) AS ?d) }}"
2096 ),
2097 )
2098 .unwrap();
2099 assert!(
2100 s[0]["d"].ends_with("XMLSchema#double>"),
2101 "distance is xsd:double: {}",
2102 s[0]["d"]
2103 );
2104 let (_, s) = eval_sparql(
2105 &rete,
2106 &format!(
2107 "{pre}SELECT ?e WHERE {{ \
2108 ?f geo:hasGeometry/geo:asWKT ?w . BIND(geof:envelope(?w) AS ?e) }}"
2109 ),
2110 )
2111 .unwrap();
2112 assert!(s[0]["e"].contains("wktLiteral") && s[0]["e"].contains("POLYGON"));
2113
2114 assert!(eval_sparql(
2116 &rete,
2117 &format!(
2118 "{pre}SELECT ?x WHERE {{ \
2119 BIND(geof:buffer(\"POINT(0 0)\"^^geo:wktLiteral, 1) AS ?x) }}"
2120 )
2121 )
2122 .is_err());
2123 }
2124
2125 #[test]
2126 fn bind_arithmetic() {
2127 let xsd = "<http://www.w3.org/2001/XMLSchema#integer>";
2128 let bytes = rete_from(&[(
2129 "<http://ex/a>",
2130 "<http://ex/age>",
2131 &format!("\"30\"^^{xsd}"),
2132 )]);
2133 let rete = Rete::open(&bytes).unwrap();
2134 let q = "PREFIX ex: <http://ex/> \
2136 SELECT ?next WHERE { ?p ex:age ?age . BIND(?age + 1 AS ?next) FILTER(?age * 2 > 50) }";
2137 let (_, sols) = eval_sparql(&rete, q).unwrap();
2138 assert_eq!(sols.len(), 1);
2139 assert_eq!(
2140 sols[0]["next"],
2141 "\"31\"^^<http://www.w3.org/2001/XMLSchema#integer>"
2142 );
2143 }
2144
2145 #[test]
2146 fn bind_value_is_visible_to_a_following_filter_and_join() {
2147 let xsd = "<http://www.w3.org/2001/XMLSchema#integer>";
2151 let n = |v: i32| format!("\"{v}\"^^{xsd}");
2152 let bytes = rete_from(&[
2153 ("<http://ex/a>", "<http://ex/v>", &n(1)),
2154 ("<http://ex/b>", "<http://ex/v>", &n(2)),
2155 ("<http://ex/c>", "<http://ex/v>", &n(3)),
2156 ("<http://ex/x>", "<http://ex/v>", &n(3)),
2158 ]);
2159 let rete = Rete::open(&bytes).unwrap();
2160
2161 let q1 = "PREFIX ex: <http://ex/> SELECT ?s WHERE { \
2163 ?s ex:v ?o . BIND(?o + 1 AS ?z) FILTER(?z = 3) }";
2164 let (_, s1) = eval_sparql(&rete, q1).unwrap();
2165 assert_eq!(s1.len(), 1, "only b (2+1=3) passes");
2166 assert_eq!(s1[0]["s"], "<http://ex/b>");
2167
2168 let q2 = "PREFIX ex: <http://ex/> SELECT ?s ?s2 WHERE { \
2170 ?s ex:v ?o . BIND(?o + 1 AS ?z) ?s2 ex:v ?z }";
2171 let (_, s2) = eval_sparql(&rete, q2).unwrap();
2172 let mut pairs: Vec<(String, String)> = s2
2174 .iter()
2175 .map(|b| (b["s"].clone(), b["s2"].clone()))
2176 .collect();
2177 pairs.sort();
2178 assert_eq!(
2179 pairs,
2180 vec![
2181 ("<http://ex/a>".to_string(), "<http://ex/b>".to_string()),
2182 ("<http://ex/b>".to_string(), "<http://ex/c>".to_string()),
2183 ("<http://ex/b>".to_string(), "<http://ex/x>".to_string()),
2184 ]
2185 );
2186 }
2187
2188 #[test]
2189 fn order_by_numeric_desc_then_limit() {
2190 let xsd = "<http://www.w3.org/2001/XMLSchema#integer>";
2191 let bytes = rete_from(&[
2192 (
2193 "<http://ex/a>",
2194 "<http://ex/age>",
2195 &format!("\"30\"^^{xsd}"),
2196 ),
2197 (
2198 "<http://ex/b>",
2199 "<http://ex/age>",
2200 &format!("\"25\"^^{xsd}"),
2201 ),
2202 (
2203 "<http://ex/c>",
2204 "<http://ex/age>",
2205 &format!("\"40\"^^{xsd}"),
2206 ),
2207 ]);
2208 let rete = Rete::open(&bytes).unwrap();
2209 let q = "PREFIX ex: <http://ex/> \
2211 SELECT ?p WHERE { ?p ex:age ?age } ORDER BY DESC(?age) LIMIT 2";
2212 let (_, sols) = eval_sparql(&rete, q).unwrap();
2213 let ps: Vec<&str> = sols.iter().map(|b| b["p"].as_str()).collect();
2214 assert_eq!(ps, vec!["<http://ex/c>", "<http://ex/a>"]); }
2216
2217 #[test]
2218 fn limit_early_out_two_hop_join() {
2219 let bytes = rete_from(&[
2223 ("<http://ex/A>", "<http://ex/k>", "<http://ex/B>"),
2224 ("<http://ex/B>", "<http://ex/k>", "<http://ex/C>"),
2225 ("<http://ex/B>", "<http://ex/k>", "<http://ex/D>"),
2226 ("<http://ex/C>", "<http://ex/k>", "<http://ex/E>"),
2227 ]);
2228 let rete = Rete::open(&bytes).unwrap();
2229 let q = "PREFIX ex: <http://ex/> SELECT ?x ?z WHERE { ?x ex:k ?y . ?y ex:k ?z }";
2230 let (_, full) = eval_sparql(&rete, q).unwrap();
2231 assert_eq!(full.len(), 3);
2232
2233 let (_, one) = eval_sparql(&rete, &format!("{q} LIMIT 1")).unwrap();
2234 assert_eq!(one.len(), 1);
2235 assert!(one.iter().all(|r| full.contains(r)));
2237
2238 let (_, all) = eval_sparql(&rete, &format!("{q} LIMIT 100")).unwrap();
2240 assert_eq!(all.len(), 3);
2241 let (_, off) = eval_sparql(&rete, &format!("{q} LIMIT 100 OFFSET 2")).unwrap();
2242 assert_eq!(off.len(), 1);
2243 }
2244
2245 #[test]
2246 fn limit_early_out_filter_over_bgp() {
2247 let xsd = "<http://www.w3.org/2001/XMLSchema#integer>";
2250 let bytes = rete_from(&[
2251 ("<http://ex/a>", "<http://ex/n>", &format!("\"10\"^^{xsd}")),
2252 ("<http://ex/b>", "<http://ex/n>", &format!("\"20\"^^{xsd}")),
2253 ("<http://ex/c>", "<http://ex/n>", &format!("\"30\"^^{xsd}")),
2254 ("<http://ex/d>", "<http://ex/n>", &format!("\"40\"^^{xsd}")),
2255 ]);
2256 let rete = Rete::open(&bytes).unwrap();
2257 let q = "PREFIX ex: <http://ex/> SELECT ?p WHERE { ?p ex:n ?v FILTER(?v > 15) }";
2258 let (_, full) = eval_sparql(&rete, q).unwrap();
2259 assert_eq!(full.len(), 3); let (_, two) = eval_sparql(&rete, &format!("{q} LIMIT 2")).unwrap();
2261 assert_eq!(two.len(), 2);
2262 assert!(two.iter().all(|r| full.contains(r)));
2263 }
2264
2265 #[test]
2266 fn distinct_bgp_fast_matches_general() {
2267 let bytes = rete_from(&[
2270 ("<http://ex/a>", "<http://ex/p>", "<http://ex/x>"),
2271 ("<http://ex/b>", "<http://ex/p>", "<http://ex/x>"),
2272 ("<http://ex/b>", "<http://ex/p>", "<http://ex/y>"),
2273 ("<http://ex/c>", "<http://ex/p>", "<http://ex/z>"),
2274 ]);
2275 let rete = Rete::open(&bytes).unwrap();
2276 let q = "PREFIX ex: <http://ex/> SELECT DISTINCT ?o WHERE { ?s ex:p ?o }";
2278 let (proj, sols) = eval_sparql(&rete, q).unwrap();
2279 assert_eq!(proj, vec!["o"]);
2280 let mut os: Vec<&str> = sols.iter().map(|b| b["o"].as_str()).collect();
2281 os.sort();
2282 assert_eq!(os, vec!["<http://ex/x>", "<http://ex/y>", "<http://ex/z>"]);
2283 assert_eq!(
2285 eval_sparql(&rete, &format!("{q} LIMIT 2")).unwrap().1.len(),
2286 2
2287 );
2288 let q2 = "PREFIX ex: <http://ex/> SELECT DISTINCT ?s ?o WHERE { ?s ex:p ?o }";
2290 assert_eq!(eval_sparql(&rete, q2).unwrap().1.len(), 4);
2291 }
2292
2293 #[test]
2294 fn limit_caps_solutions() {
2295 let bytes = rete_from(&[
2296 ("<http://ex/a>", "<http://ex/p>", "<http://ex/1>"),
2297 ("<http://ex/b>", "<http://ex/p>", "<http://ex/2>"),
2298 ("<http://ex/c>", "<http://ex/p>", "<http://ex/3>"),
2299 ]);
2300 let rete = Rete::open(&bytes).unwrap();
2301 let (_, sols) =
2302 eval_sparql(&rete, "SELECT ?x WHERE { ?x <http://ex/p> ?y } LIMIT 2").unwrap();
2303 assert_eq!(sols.len(), 2);
2304 }
2305
2306 #[test]
2313 fn string_filters_see_past_an_embedded_quote() {
2314 let bytes = rete_from(&[
2315 (
2316 "<http://ex/a>",
2317 "<http://ex/label>",
2318 "\"plain Quantum here\"",
2319 ),
2320 (
2321 "<http://ex/b>",
2322 "<http://ex/label>",
2323 r#""He said \"Quantum\" loudly"@en"#,
2324 ),
2325 (
2326 "<http://ex/c>",
2327 "<http://ex/label>",
2328 r#""Theory of \"Quantum\" Gases""#,
2329 ),
2330 ("<http://ex/d>", "<http://ex/label>", "\"no match at all\""),
2331 (
2332 "<http://ex/e>",
2333 "<http://ex/label>",
2334 "\"tab\\there\\nline two\"^^<http://www.w3.org/2001/XMLSchema#string>",
2335 ),
2336 ]);
2337 let rete = Rete::open(&bytes).unwrap();
2338 let subjects = |filter: &str| {
2339 let q = format!("SELECT ?s WHERE {{ ?s <http://ex/label> ?l FILTER({filter}) }}");
2340 let (_, sols) = eval_sparql(&rete, &q).unwrap();
2341 let mut out: Vec<String> = sols.iter().map(|b| b["s"].clone()).collect();
2342 out.sort();
2343 out
2344 };
2345 let (a, b, c, e) = (
2346 "<http://ex/a>",
2347 "<http://ex/b>",
2348 "<http://ex/c>",
2349 "<http://ex/e>",
2350 );
2351 assert_eq!(subjects(r#"CONTAINS(?l, "Quantum")"#), vec![a, b, c]);
2352 assert_eq!(subjects(r#"CONTAINS(?l, "Gases")"#), vec![c]);
2353 assert_eq!(subjects(r#"STRENDS(?l, "loudly")"#), vec![b]);
2354 assert_eq!(subjects(r#"STRSTARTS(?l, "Theory of \"Q")"#), vec![c]);
2355 assert_eq!(subjects(r#"REGEX(?l, "gases$", "i")"#), vec![c]);
2356 assert_eq!(subjects(r#"REGEX(?l, "^line two$", "m")"#), vec![e]);
2357 assert_eq!(subjects(r#"CONTAINS(?l, "\there")"#), vec![e]);
2358 assert_eq!(subjects(r#"LANGMATCHES(LANG(?l), "en")"#), vec![b]);
2359 assert_eq!(subjects(r#"STRAFTER(?l, "Quantum") = "\" Gases""#), vec![c]);
2360 assert_eq!(
2361 subjects(r#"STRBEFORE(?l, " loudly") = "He said \"Quantum\""@en"#),
2362 vec![b]
2363 );
2364 assert_eq!(subjects(r#"STRLEN(?l) = 25"#), vec![c]);
2365 assert_eq!(subjects(r#"STRLEN(?l) = 24"#), vec![b]);
2366 }
2367
2368 #[test]
2376 fn reasoning_rewrites_only_the_atoms_it_can_extend() {
2377 let dom = "<http://www.w3.org/2000/01/rdf-schema#domain>";
2378 let sub = "<http://www.w3.org/2000/01/rdf-schema#subClassOf>";
2379 let ty = "<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>";
2380 let bytes = rete_from(&[
2381 (
2382 "<http://ex/hasCharacterisation>",
2383 dom,
2384 "<http://ex/Citation>",
2385 ),
2386 ("<http://ex/SelfCitation>", sub, "<http://ex/Citation>"),
2387 ("<http://ex/writtenBy>", dom, "<http://ex/Work>"),
2388 ("<http://ex/r1>", ty, "<http://ex/Role>"),
2389 ("<http://ex/w1>", ty, "<http://ex/Work>"),
2390 ("<http://ex/w2>", "<http://ex/writtenBy>", "<http://ex/ann>"),
2391 ]);
2392 let rete = Rete::open(&bytes).unwrap();
2393 let rewrite = |q: &str| {
2394 let sel = parse_select(q).unwrap();
2395 ql::reason_rewrite(sel.plan, &rete, &sel.project)
2396 };
2397 assert!(matches!(
2399 rewrite("SELECT ?s WHERE { ?s a <http://ex/Role> ; ?p ?o }"),
2400 Plan::Bgp(p) if p.len() == 2
2401 ));
2402 assert!(matches!(
2405 rewrite("SELECT ?s WHERE { ?s a <http://ex/Citation> }"),
2406 Plan::Bgp(p) if p.len() == 1
2407 ));
2408 match rewrite("SELECT ?s WHERE { ?s a <http://ex/Work> }") {
2410 Plan::DistinctUnion { vars, sources } => {
2411 assert_eq!(vars, vec!["s".to_string()]);
2412 assert_eq!(sources.len(), 2);
2413 }
2414 other => panic!("expected a DistinctUnion, got {other:?}"),
2415 }
2416 let (_, sols) =
2417 eval_sparql_reasoned(&rete, "SELECT ?s WHERE { ?s a <http://ex/Work> }").unwrap();
2418 let mut got: Vec<&str> = sols.iter().map(|b| b["s"].as_str()).collect();
2419 got.sort();
2420 assert_eq!(got, vec!["<http://ex/w1>", "<http://ex/w2>"]);
2421 }
2422
2423 #[test]
2428 fn a_small_left_side_probes_the_right_bgp() {
2429 let mut t: Vec<(String, String, String)> = Vec::new();
2430 let e = |n: String| format!("<http://ex/{n}>");
2431 for i in 0..200 {
2432 t.push((e(format!("j{i}")), e("a".into()), e("Journal".into())));
2433 t.push((e(format!("j{i}")), e("title".into()), format!("\"T{i}\"")));
2434 t.push((e(format!("j{i}")), e("id".into()), e(format!("id{i}"))));
2435 t.push((e(format!("id{i}")), e("value".into()), format!("\"{i}\"")));
2436 }
2437 t.push((e("work".into()), e("partOf".into()), e("issue".into())));
2438 t.push((e("issue".into()), e("partOf".into()), e("j7".into())));
2439 let refs: Vec<(&str, &str, &str)> = t
2440 .iter()
2441 .map(|(s, p, o)| (s.as_str(), p.as_str(), o.as_str()))
2442 .collect();
2443 let rete = Rete::open(&rete_from(&refs)).unwrap();
2444 let queries = [
2445 "PREFIX ex: <http://ex/> SELECT ?j ?t ?v WHERE { ex:work ex:partOf+ ?j . \
2446 ?j ex:a ex:Journal ; ex:title ?t ; ex:id ?i . ?i ex:value ?v }",
2447 "PREFIX ex: <http://ex/> SELECT ?j ?t WHERE { ex:work ex:partOf+ ?j \
2448 OPTIONAL { ?j ex:title ?t } }",
2449 ];
2450 for q in queries {
2451 let run = |floor: f64| {
2452 crate::bgp::with_probe_floor(floor, || {
2453 let (_, sols) = eval_sparql(&rete, q).unwrap();
2454 let mut v: Vec<String> = sols.iter().map(|b| format!("{b:?}")).collect();
2455 v.sort();
2456 v
2457 })
2458 };
2459 let hashed = run(f64::MAX);
2460 assert!(!hashed.is_empty());
2461 assert_eq!(run(0.0), hashed, "{q}");
2462 }
2463 }
2464 fn people() -> Rete {
2467 const TYPE: &str = "<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>";
2468 let e = |n: String| format!("<http://ex/{n}>");
2469 let mut t: Vec<(String, String, String)> = Vec::new();
2470 for i in 0..200 {
2471 t.push((
2472 e(format!("p{i}")),
2473 e("knows".into()),
2474 e(format!("p{}", (i + 1) % 200)),
2475 ));
2476 t.push((e(format!("p{i}")), e("name".into()), format!("\"N{i}\"")));
2477 if i % 2 == 0 {
2478 t.push((e(format!("p{i}")), e("age".into()), format!("\"{i}\"")));
2479 }
2480 let class = if i % 10 == 0 { "Manager" } else { "Person" };
2481 t.push((e(format!("p{i}")), TYPE.into(), e(class.into())));
2482 }
2483 for i in [3, 4] {
2484 t.push((e(format!("p{i}")), TYPE.into(), e("Agent".into())));
2485 }
2486 let refs: Vec<(&str, &str, &str)> = t
2487 .iter()
2488 .map(|(s, p, o)| (s.as_str(), p.as_str(), o.as_str()))
2489 .collect();
2490 Rete::open(&rete_from(&refs)).unwrap()
2491 }
2492
2493 fn rows_at(rete: &Rete, q: &str, floor: f64) -> Vec<String> {
2497 crate::bgp::with_probe_floor(floor, || {
2498 let (_, sols) = eval_sparql(rete, q).unwrap();
2499 let mut v: Vec<String> = sols.iter().map(|b| format!("{b:?}")).collect();
2500 v.sort();
2501 v
2502 })
2503 }
2504
2505 #[test]
2508 fn correlated_exists_and_minus_match_whole_evaluation() {
2509 let rete = people();
2510 let pre = "PREFIX ex: <http://ex/> ";
2511 let bodies = [
2512 "SELECT ?s WHERE { ?s ex:knows ?o . FILTER NOT EXISTS { ?s ex:age ?a } }",
2514 "SELECT ?s WHERE { ?s ex:knows ?o . FILTER EXISTS { ?s ex:age ?a } }",
2515 "SELECT ?s WHERE { ?s ex:name ?n . FILTER NOT EXISTS { ?s ex:knows ?o . ?o ex:age ?a } }",
2517 "SELECT ?o WHERE { ?s ex:knows ?o . FILTER NOT EXISTS { ?x ex:knows ?o . ?x ex:age ?a } }",
2519 "SELECT ?s WHERE { ?s ex:name ?n . FILTER NOT EXISTS { ?s ex:nothere ?a } }",
2521 "SELECT ?s WHERE { ?s ex:name ?n . FILTER EXISTS { ?s ex:nothere ?a } }",
2522 "SELECT ?s WHERE { ?s ex:name ?n . FILTER NOT EXISTS { ?z ex:age \"4\" } }",
2524 "SELECT ?s WHERE { ?s ex:name ?n . FILTER EXISTS { ex:p4 ex:age \"4\" } }",
2526 "SELECT ?s WHERE { ?s ex:name ?n . BIND(CONCAT(?n, \"!\") AS ?m) FILTER NOT EXISTS { ?m ex:age ?a } }",
2528 "SELECT ?s WHERE { ?s ex:knows ?o . MINUS { ?s ex:age ?a } }",
2530 "SELECT ?o WHERE { ?s ex:knows ?o . MINUS { ?x ex:knows ?o . ?x ex:age ?a } }",
2531 "SELECT ?s WHERE { ?s ex:name ?n . MINUS { ?z ex:age ?a } }",
2532 "SELECT ?s WHERE { ?s ex:name ?n . MINUS { ?s ex:nothere ?a } }",
2533 "SELECT ?s ?a WHERE { ?s ex:name ?n . OPTIONAL { ?s ex:age ?a } MINUS { ?a ex:nothing ?z } }",
2535 "SELECT ?s WHERE { VALUES ?s { ex:p1 ex:p2 ex:p3 } FILTER NOT EXISTS { ?s ex:age ?a } }",
2537 ];
2538 for body in bodies {
2539 let q = format!("{pre}{body}");
2540 let whole = rows_at(&rete, &q, f64::MAX);
2541 assert_eq!(rows_at(&rete, &q, 0.0), whole, "{body}");
2542 }
2543 let n = |body: &str| rows_at(&rete, &format!("{pre}{body}"), 0.0).len();
2545 assert_eq!(n(bodies[0]), 100);
2546 assert_eq!(n(bodies[9]), 100);
2547 assert_eq!(n(bodies[11]), 200);
2548 }
2549
2550 #[test]
2554 fn a_union_receives_the_bindings_of_the_side_joined_with_it() {
2555 let rete = people();
2556 let pre = "PREFIX ex: <http://ex/> ";
2557 let bodies = [
2558 "SELECT ?r ?p ?v WHERE { VALUES ?r { ex:p1 ex:p2 ex:p3 ex:nobody } \
2559 { ?r ?p ?v } UNION { ?r ex:knows ?n . ?n ?p ?v } }",
2560 "SELECT ?r ?p ?v WHERE { { ?r ?p ?v } UNION { ?r ex:knows ?n . ?n ?p ?v } \
2561 VALUES ?r { ex:p1 ex:p2 ex:p3 } }",
2562 "SELECT ?r ?v WHERE { VALUES ?r { ex:p4 ex:p8 } { ?r ex:age ?v } UNION \
2564 { ?r ex:nothere ?v } UNION { ?r ex:knows ?v } }",
2565 "SELECT ?x ?v WHERE { ?x ex:age \"4\" . { ?x ex:knows ?v } UNION { ?x ex:name ?v } }",
2567 "SELECT ?r ?v ?w WHERE { VALUES ?r { ex:p3 ex:p6 } { ?r ex:knows ?v } UNION \
2569 { ?r ex:age ?w } }",
2570 "SELECT ?r ?v WHERE { VALUES ?r { ex:p3 UNDEF } { ?r ex:age ?v } UNION { ?r ex:name ?v } }",
2572 ];
2573 for body in bodies {
2574 let q = format!("{pre}{body}");
2575 let whole = rows_at(&rete, &q, f64::MAX);
2576 assert!(!whole.is_empty(), "{body}");
2577 assert_eq!(rows_at(&rete, &q, 0.0), whole, "{body}");
2578 }
2579 let q = format!("{pre}{}", bodies[0]);
2583 assert_eq!(rows_at(&rete, &q, 0.0).len(), 11 + 13);
2584 }
2585
2586 #[test]
2589 fn an_unbound_class_joined_on_a_bound_subject_probes_per_subject() {
2590 let rete = people();
2591 let pre = "PREFIX ex: <http://ex/> ";
2592 let bodies = [
2593 "SELECT ?s ?c WHERE { ?s ex:age ?a . ?s a ?c }",
2594 "SELECT ?s ?o ?c WHERE { ?s ex:knows ?o . ?o a ?c }",
2595 "SELECT ?c (COUNT(*) AS ?n) WHERE { ?s ex:age ?a . ?s a ?c } GROUP BY ?c",
2596 "SELECT ?s ?c WHERE { ?s ex:knows ?o . ?o a ?c . ?s a ?c }",
2598 "SELECT ?s ?c WHERE { ?s ?p ?x . ?s a ?c . FILTER(?p = ex:age) }",
2600 ];
2601 for body in bodies {
2602 let q = format!("{pre}{body}");
2603 let whole = rows_at(&rete, &q, f64::MAX);
2604 assert!(!whole.is_empty(), "{body}");
2605 assert_eq!(rows_at(&rete, &q, 0.0), whole, "{body}");
2606 }
2607 let q = format!("{pre}{}", bodies[0]);
2609 assert_eq!(rows_at(&rete, &q, 0.0).len(), 101);
2610 }
2611
2612 #[test]
2614 fn a_named_graph_is_sized_by_its_own_triples() {
2615 use crate::write_dataset_v05 as write_dataset;
2616 let mut db = DictionaryBuilder::new();
2617 let big: Vec<(String, String, String)> = (0..300)
2618 .map(|i| {
2619 (
2620 format!("<http://ex/s{i}>"),
2621 "<http://ex/p>".to_string(),
2622 format!("<http://ex/o{i}>"),
2623 )
2624 })
2625 .collect();
2626 let tiny = (
2627 "<http://ex/s0>".to_string(),
2628 "<http://ex/q>".to_string(),
2629 "<http://ex/o0>".to_string(),
2630 );
2631 for (s, p, o) in big.iter().chain(std::iter::once(&tiny)) {
2632 db.observe(s, p, o);
2633 }
2634 let dict = db.build();
2635 let mut default = GraphIndexBuilder::new();
2636 for (s, p, o) in &big {
2637 default.push(dict.encode(s, p, o).unwrap());
2638 }
2639 let mut small = GraphIndexBuilder::new();
2640 small.push(dict.encode(&tiny.0, &tiny.1, &tiny.2).unwrap());
2641 let named = vec![("<http://ex/g>".to_string(), small.build())];
2642 let bytes = write_dataset(&dict, &default.build(), &named, true, &[], 0);
2643 let rete = Rete::open(&bytes).unwrap();
2644 let g = rete.graph_index("<http://ex/g>").unwrap();
2645 assert_eq!(rete.index_triples(g), 1, "the graph's own count");
2646 assert_eq!(
2647 rete.index_triples(rete.default_index()),
2648 rete.header().quad_count,
2649 "the default graph keeps the file's total"
2650 );
2651 let (_, sols) = eval_sparql(
2652 &rete,
2653 "SELECT ?o WHERE { GRAPH <http://ex/g> { <http://ex/s0> <http://ex/q> ?o } }",
2654 )
2655 .unwrap();
2656 assert_eq!(sols.len(), 1);
2657 }
2658
2659 #[test]
2662 fn a_quad_index_graph_is_sized_by_its_directory_count() {
2663 use crate::ingest::{assemble_dataset_with_layout, GraphLayout};
2664 let q = |s: &str, g: Option<&str>| -> crate::ingest::RawQuad {
2665 (
2666 format!("<http://ex/{s}>"),
2667 "<http://ex/p>".to_string(),
2668 "<http://ex/o>".to_string(),
2669 g.map(|g| format!("<http://ex/{g}>")),
2670 )
2671 };
2672 let mut quads: Vec<_> = (0..50).map(|i| q(&format!("d{i}"), None)).collect();
2673 quads.extend((0..7).map(|i| q(&format!("a{i}"), Some("ga"))));
2674 quads.extend((0..3).map(|i| q(&format!("b{i}"), Some("gb"))));
2675 let (bytes, _) = assemble_dataset_with_layout(
2676 quads,
2677 false,
2678 false,
2679 None,
2680 crate::pyramid::PyramidAlgo::Louvain,
2681 crate::index::PermSet::ALL,
2682 GraphLayout::Quad,
2683 |_, _| Vec::<u8>::new(),
2684 );
2685 let rete = Rete::open(&bytes).unwrap();
2686 assert_eq!(
2687 rete.index_triples(rete.graph_index("<http://ex/ga>").unwrap()),
2688 7
2689 );
2690 assert_eq!(
2691 rete.index_triples(rete.graph_index("<http://ex/gb>").unwrap()),
2692 3
2693 );
2694 let (_, sols) = eval_sparql(
2695 &rete,
2696 "SELECT ?s WHERE { GRAPH <http://ex/ga> { ?s <http://ex/p> <http://ex/o> . \
2697 FILTER NOT EXISTS { ?s <http://ex/p> <http://ex/zz> } } }",
2698 )
2699 .unwrap();
2700 assert_eq!(sols.len(), 7);
2701 }
2702}