oxirs_core/sparql/
subquery_builder.rs

1//! SPARQL subquery construction and nesting utilities.
2//!
3//! Provides a fluent builder API for constructing SPARQL subqueries,
4//! including SELECT subqueries, EXISTS/NOT EXISTS filters, and MINUS clauses.
5//! Includes normalization (flattening double-nested subqueries) and
6//! optimization (pushing filters inside subqueries when safe).
7
8use std::collections::HashSet;
9
10// ---------------------------------------------------------------------------
11// Core types
12// ---------------------------------------------------------------------------
13
14/// A triple pattern with subject, predicate, and object as strings.
15#[derive(Debug, Clone, PartialEq)]
16pub struct TriplePattern {
17    pub subject: String,
18    pub predicate: String,
19    pub object: String,
20}
21
22impl TriplePattern {
23    /// Create a new triple pattern.
24    pub fn new(
25        subject: impl Into<String>,
26        predicate: impl Into<String>,
27        object: impl Into<String>,
28    ) -> Self {
29        Self {
30            subject: subject.into(),
31            predicate: predicate.into(),
32            object: object.into(),
33        }
34    }
35
36    /// Render the pattern as a SPARQL token.
37    pub fn to_sparql(&self) -> String {
38        format!("{} {} {} .", self.subject, self.predicate, self.object)
39    }
40}
41
42/// A filter expression string (e.g. `?x > 5`, `LANG(?label) = "en"`).
43#[derive(Debug, Clone, PartialEq)]
44pub struct FilterExpr(pub String);
45
46impl FilterExpr {
47    pub fn new(expr: impl Into<String>) -> Self {
48        Self(expr.into())
49    }
50
51    pub fn as_str(&self) -> &str {
52        &self.0
53    }
54
55    /// Render as a SPARQL FILTER clause.
56    pub fn to_sparql(&self) -> String {
57        format!("FILTER ( {} )", self.0)
58    }
59
60    /// Returns the set of variable names referenced in the expression.
61    /// A simple heuristic: scan for `?<word>` tokens.
62    pub fn referenced_vars(&self) -> HashSet<String> {
63        let mut vars = HashSet::new();
64        let mut chars = self.0.chars().peekable();
65        while let Some(ch) = chars.next() {
66            if ch == '?' {
67                let name: String = chars
68                    .by_ref()
69                    .take_while(|c| c.is_alphanumeric() || *c == '_')
70                    .collect();
71                if !name.is_empty() {
72                    vars.insert(name);
73                }
74            }
75        }
76        vars
77    }
78}
79
80// ---------------------------------------------------------------------------
81// SubqueryNode
82// ---------------------------------------------------------------------------
83
84/// A node in the subquery tree.
85#[derive(Debug, Clone, PartialEq)]
86pub enum SubqueryNode {
87    /// A SELECT subquery.
88    Select {
89        /// Projected variables (e.g. `["?x", "?y"]`). Empty means `SELECT *`.
90        vars: Vec<String>,
91        /// Triple patterns in the WHERE clause.
92        patterns: Vec<TriplePattern>,
93        /// FILTER expressions in the WHERE clause.
94        filters: Vec<FilterExpr>,
95        /// An optional inner subquery wrapped in `{ SELECT … }`.
96        inner: Option<Box<SubqueryNode>>,
97    },
98    /// `EXISTS { … }` graph pattern.
99    Exists(Box<SubqueryNode>),
100    /// `NOT EXISTS { … }` graph pattern.
101    NotExists(Box<SubqueryNode>),
102    /// `MINUS { … }` graph pattern.
103    Minus(Box<SubqueryNode>),
104}
105
106impl SubqueryNode {
107    /// Render this node as a SPARQL fragment.
108    pub fn to_sparql(&self) -> String {
109        match self {
110            SubqueryNode::Select {
111                vars,
112                patterns,
113                filters,
114                inner,
115            } => {
116                let var_list = if vars.is_empty() {
117                    "*".to_string()
118                } else {
119                    vars.join(" ")
120                };
121
122                let mut body = String::new();
123
124                // Inner subquery if present
125                if let Some(inner_node) = inner {
126                    body.push_str("  {\n");
127                    let inner_sparql = inner_node.to_sparql();
128                    for line in inner_sparql.lines() {
129                        body.push_str("    ");
130                        body.push_str(line);
131                        body.push('\n');
132                    }
133                    body.push_str("  }\n");
134                }
135
136                for pat in patterns {
137                    body.push_str("  ");
138                    body.push_str(&pat.to_sparql());
139                    body.push('\n');
140                }
141                for filt in filters {
142                    body.push_str("  ");
143                    body.push_str(&filt.to_sparql());
144                    body.push('\n');
145                }
146
147                format!("SELECT {var_list} WHERE {{\n{body}}}")
148            }
149            SubqueryNode::Exists(inner) => {
150                let inner_str = inner.to_sparql();
151                let indented: String = inner_str
152                    .lines()
153                    .map(|l| format!("  {l}"))
154                    .collect::<Vec<_>>()
155                    .join("\n");
156                format!("EXISTS {{\n{indented}\n}}")
157            }
158            SubqueryNode::NotExists(inner) => {
159                let inner_str = inner.to_sparql();
160                let indented: String = inner_str
161                    .lines()
162                    .map(|l| format!("  {l}"))
163                    .collect::<Vec<_>>()
164                    .join("\n");
165                format!("NOT EXISTS {{\n{indented}\n}}")
166            }
167            SubqueryNode::Minus(inner) => {
168                let inner_str = inner.to_sparql();
169                let indented: String = inner_str
170                    .lines()
171                    .map(|l| format!("  {l}"))
172                    .collect::<Vec<_>>()
173                    .join("\n");
174                format!("MINUS {{\n{indented}\n}}")
175            }
176        }
177    }
178
179    /// Returns all projected variables if this is a `Select` node.
180    pub fn projected_vars(&self) -> Vec<String> {
181        match self {
182            SubqueryNode::Select { vars, .. } => vars.clone(),
183            _ => vec![],
184        }
185    }
186
187    /// Returns whether this node has no patterns and no filters (i.e. is empty).
188    pub fn is_empty(&self) -> bool {
189        match self {
190            SubqueryNode::Select {
191                patterns,
192                filters,
193                inner,
194                ..
195            } => patterns.is_empty() && filters.is_empty() && inner.is_none(),
196            SubqueryNode::Exists(inner)
197            | SubqueryNode::NotExists(inner)
198            | SubqueryNode::Minus(inner) => inner.is_empty(),
199        }
200    }
201
202    /// Returns the depth of nesting.
203    pub fn depth(&self) -> usize {
204        match self {
205            SubqueryNode::Select { inner, .. } => {
206                1 + inner.as_ref().map(|n| n.depth()).unwrap_or(0)
207            }
208            SubqueryNode::Exists(inner)
209            | SubqueryNode::NotExists(inner)
210            | SubqueryNode::Minus(inner) => 1 + inner.depth(),
211        }
212    }
213}
214
215// ---------------------------------------------------------------------------
216// SubqueryBuilder
217// ---------------------------------------------------------------------------
218
219/// Fluent builder for `SubqueryNode::Select`.
220#[derive(Debug, Default)]
221pub struct SubqueryBuilder {
222    vars: Vec<String>,
223    patterns: Vec<TriplePattern>,
224    filters: Vec<FilterExpr>,
225    inner: Option<Box<SubqueryNode>>,
226}
227
228impl SubqueryBuilder {
229    /// Create a new builder.
230    pub fn new() -> Self {
231        Self::default()
232    }
233
234    /// Set the projected variables.
235    pub fn select(mut self, vars: impl IntoIterator<Item = impl Into<String>>) -> Self {
236        self.vars = vars.into_iter().map(Into::into).collect();
237        self
238    }
239
240    /// Add a triple pattern.
241    pub fn add_pattern(
242        mut self,
243        s: impl Into<String>,
244        p: impl Into<String>,
245        o: impl Into<String>,
246    ) -> Self {
247        self.patterns.push(TriplePattern::new(s, p, o));
248        self
249    }
250
251    /// Add a FILTER expression.
252    pub fn add_filter(mut self, expr: impl Into<String>) -> Self {
253        self.filters.push(FilterExpr::new(expr));
254        self
255    }
256
257    /// Set an inner `SubqueryNode` (creates a nested subquery).
258    pub fn nest(mut self, inner: SubqueryNode) -> Self {
259        self.inner = Some(Box::new(inner));
260        self
261    }
262
263    /// Deduplicate projected variables (preserves first occurrence order).
264    fn dedup_vars(vars: Vec<String>) -> Vec<String> {
265        let mut seen = HashSet::new();
266        vars.into_iter()
267            .filter(|v| seen.insert(v.clone()))
268            .collect()
269    }
270
271    /// Build the `SubqueryNode`.
272    pub fn build(self) -> SubqueryNode {
273        SubqueryNode::Select {
274            vars: Self::dedup_vars(self.vars),
275            patterns: self.patterns,
276            filters: self.filters,
277            inner: self.inner,
278        }
279    }
280
281    /// Wrap the built node in an `EXISTS`.
282    pub fn build_exists(self) -> SubqueryNode {
283        SubqueryNode::Exists(Box::new(self.build()))
284    }
285
286    /// Wrap the built node in a `NOT EXISTS`.
287    pub fn build_not_exists(self) -> SubqueryNode {
288        SubqueryNode::NotExists(Box::new(self.build()))
289    }
290
291    /// Wrap the built node in a `MINUS`.
292    pub fn build_minus(self) -> SubqueryNode {
293        SubqueryNode::Minus(Box::new(self.build()))
294    }
295}
296
297// ---------------------------------------------------------------------------
298// SubqueryNormalizer
299// ---------------------------------------------------------------------------
300
301/// Flattens doubly-nested `Select` subqueries.
302///
303/// A doubly-nested subquery is:
304/// ```sparql
305/// SELECT … WHERE {
306///   {
307///     SELECT … WHERE {
308///       {
309///         SELECT … WHERE { … }   ← this innermost is merged up
310///       }
311///     }
312///   }
313/// }
314/// ```
315///
316/// The normalizer merges the innermost `Select` into its parent when the
317/// parent has no patterns or filters of its own and the vars are compatible.
318pub struct SubqueryNormalizer;
319
320impl SubqueryNormalizer {
321    /// Create a new normalizer.
322    pub fn new() -> Self {
323        Self
324    }
325
326    /// Normalize `node`, returning an equivalent (possibly simplified) `SubqueryNode`.
327    pub fn normalize(&self, node: SubqueryNode) -> SubqueryNode {
328        match node {
329            SubqueryNode::Select {
330                vars,
331                patterns,
332                filters,
333                inner,
334            } => {
335                let normalized_inner = inner.map(|n| Box::new(self.normalize(*n)));
336
337                // Collapse: if outer Select has no own patterns/filters and the
338                // inner is also a plain Select with compatible vars, merge them.
339                if let Some(inner_node) = normalized_inner {
340                    if let SubqueryNode::Select {
341                        vars: inner_vars,
342                        patterns: inner_patterns,
343                        filters: inner_filters,
344                        inner: inner_inner,
345                    } = *inner_node
346                    {
347                        if patterns.is_empty() && filters.is_empty() {
348                            // Merge: adopt inner's patterns/filters; keep outer vars if set.
349                            let merged_vars = if vars.is_empty() { inner_vars } else { vars };
350                            return self.normalize(SubqueryNode::Select {
351                                vars: merged_vars,
352                                patterns: inner_patterns,
353                                filters: inner_filters,
354                                inner: inner_inner,
355                            });
356                        }
357                        // Cannot merge; put inner back.
358                        SubqueryNode::Select {
359                            vars,
360                            patterns,
361                            filters,
362                            inner: Some(Box::new(SubqueryNode::Select {
363                                vars: inner_vars,
364                                patterns: inner_patterns,
365                                filters: inner_filters,
366                                inner: inner_inner,
367                            })),
368                        }
369                    } else {
370                        SubqueryNode::Select {
371                            vars,
372                            patterns,
373                            filters,
374                            inner: Some(inner_node),
375                        }
376                    }
377                } else {
378                    SubqueryNode::Select {
379                        vars,
380                        patterns,
381                        filters,
382                        inner: None,
383                    }
384                }
385            }
386            SubqueryNode::Exists(inner) => SubqueryNode::Exists(Box::new(self.normalize(*inner))),
387            SubqueryNode::NotExists(inner) => {
388                SubqueryNode::NotExists(Box::new(self.normalize(*inner)))
389            }
390            SubqueryNode::Minus(inner) => SubqueryNode::Minus(Box::new(self.normalize(*inner))),
391        }
392    }
393}
394
395impl Default for SubqueryNormalizer {
396    fn default() -> Self {
397        Self::new()
398    }
399}
400
401// ---------------------------------------------------------------------------
402// SubqueryOptimizer
403// ---------------------------------------------------------------------------
404
405/// Pushes FILTER expressions inside subqueries when safe to do so.
406///
407/// A filter is "safe" to push down into an inner `Select` subquery when every
408/// variable referenced by the filter is projected by (i.e. available from) the
409/// inner subquery.
410pub struct SubqueryOptimizer;
411
412impl SubqueryOptimizer {
413    /// Create a new optimizer.
414    pub fn new() -> Self {
415        Self
416    }
417
418    /// Optimize `node` by pushing filters inward.
419    pub fn optimize(&self, node: SubqueryNode) -> SubqueryNode {
420        match node {
421            SubqueryNode::Select {
422                vars,
423                patterns,
424                mut filters,
425                inner,
426            } => {
427                if let Some(inner_node) = inner {
428                    let optimized_inner = self.optimize(*inner_node);
429
430                    // Determine which filters can be pushed into the inner node.
431                    let (push_down, keep): (Vec<FilterExpr>, Vec<FilterExpr>) =
432                        if let SubqueryNode::Select {
433                            vars: ref inner_vars,
434                            ..
435                        } = optimized_inner
436                        {
437                            let available: HashSet<String> = inner_vars
438                                .iter()
439                                .map(|v| v.trim_start_matches('?').to_string())
440                                .collect();
441
442                            filters.drain(..).partition(|f| {
443                                // Push down only when all referenced vars are in the inner SELECT.
444                                // If inner vars is empty it means SELECT * — push nothing (safety).
445                                if available.is_empty() {
446                                    false
447                                } else {
448                                    f.referenced_vars()
449                                        .iter()
450                                        .all(|v| available.contains(v.as_str()))
451                                }
452                            })
453                        } else {
454                            (vec![], std::mem::take(&mut filters))
455                        };
456
457                    let new_inner = if push_down.is_empty() {
458                        optimized_inner
459                    } else {
460                        self.add_filters_to_select(optimized_inner, push_down)
461                    };
462
463                    SubqueryNode::Select {
464                        vars,
465                        patterns,
466                        filters: keep,
467                        inner: Some(Box::new(new_inner)),
468                    }
469                } else {
470                    SubqueryNode::Select {
471                        vars,
472                        patterns,
473                        filters,
474                        inner: None,
475                    }
476                }
477            }
478            SubqueryNode::Exists(inner) => SubqueryNode::Exists(Box::new(self.optimize(*inner))),
479            SubqueryNode::NotExists(inner) => {
480                SubqueryNode::NotExists(Box::new(self.optimize(*inner)))
481            }
482            SubqueryNode::Minus(inner) => SubqueryNode::Minus(Box::new(self.optimize(*inner))),
483        }
484    }
485
486    /// Add `extra_filters` to a `Select` node (panics if node is not Select — caller must ensure).
487    fn add_filters_to_select(
488        &self,
489        node: SubqueryNode,
490        extra_filters: Vec<FilterExpr>,
491    ) -> SubqueryNode {
492        match node {
493            SubqueryNode::Select {
494                vars,
495                patterns,
496                mut filters,
497                inner,
498            } => {
499                filters.extend(extra_filters);
500                SubqueryNode::Select {
501                    vars,
502                    patterns,
503                    filters,
504                    inner,
505                }
506            }
507            other => other,
508        }
509    }
510}
511
512impl Default for SubqueryOptimizer {
513    fn default() -> Self {
514        Self::new()
515    }
516}
517
518// ---------------------------------------------------------------------------
519// Tests
520// ---------------------------------------------------------------------------
521
522#[cfg(test)]
523mod tests {
524    use super::*;
525
526    // -----------------------------------------------------------------------
527    // Helper
528    // -----------------------------------------------------------------------
529
530    fn select_xy() -> SubqueryNode {
531        SubqueryBuilder::new()
532            .select(["?x", "?y"])
533            .add_pattern("?x", "<p:name>", "?y")
534            .build()
535    }
536
537    // -----------------------------------------------------------------------
538    // TriplePattern tests
539    // -----------------------------------------------------------------------
540
541    #[test]
542    fn test_triple_pattern_new() {
543        let tp = TriplePattern::new("?s", "<p:pred>", "?o");
544        assert_eq!(tp.subject, "?s");
545        assert_eq!(tp.predicate, "<p:pred>");
546        assert_eq!(tp.object, "?o");
547    }
548
549    #[test]
550    fn test_triple_pattern_to_sparql() {
551        let tp = TriplePattern::new("?s", "<p:pred>", "?o");
552        assert_eq!(tp.to_sparql(), "?s <p:pred> ?o .");
553    }
554
555    // -----------------------------------------------------------------------
556    // FilterExpr tests
557    // -----------------------------------------------------------------------
558
559    #[test]
560    fn test_filter_expr_to_sparql() {
561        let f = FilterExpr::new("?x > 5");
562        assert!(f.to_sparql().contains("FILTER"));
563        assert!(f.to_sparql().contains("?x > 5"));
564    }
565
566    #[test]
567    fn test_filter_expr_referenced_vars_single() {
568        let f = FilterExpr::new("?age > 18");
569        let vars = f.referenced_vars();
570        assert!(vars.contains("age"));
571    }
572
573    #[test]
574    fn test_filter_expr_referenced_vars_multiple() {
575        let f = FilterExpr::new("?x < ?y && ?z > 0");
576        let vars = f.referenced_vars();
577        assert!(vars.contains("x"));
578        assert!(vars.contains("y"));
579        assert!(vars.contains("z"));
580    }
581
582    #[test]
583    fn test_filter_expr_no_vars() {
584        let f = FilterExpr::new("1 = 1");
585        assert!(f.referenced_vars().is_empty());
586    }
587
588    // -----------------------------------------------------------------------
589    // SubqueryBuilder basic tests
590    // -----------------------------------------------------------------------
591
592    #[test]
593    fn test_builder_new_builds_empty_select() {
594        let node = SubqueryBuilder::new().build();
595        match &node {
596            SubqueryNode::Select {
597                vars,
598                patterns,
599                filters,
600                inner,
601            } => {
602                assert!(vars.is_empty());
603                assert!(patterns.is_empty());
604                assert!(filters.is_empty());
605                assert!(inner.is_none());
606            }
607            _ => panic!("expected Select"),
608        }
609    }
610
611    #[test]
612    fn test_builder_select_vars() {
613        let node = SubqueryBuilder::new().select(["?a", "?b"]).build();
614        assert_eq!(node.projected_vars(), vec!["?a", "?b"]);
615    }
616
617    #[test]
618    fn test_builder_add_pattern() {
619        let node = SubqueryBuilder::new()
620            .add_pattern("?s", "<p:type>", "<p:Thing>")
621            .build();
622        match &node {
623            SubqueryNode::Select { patterns, .. } => {
624                assert_eq!(patterns.len(), 1);
625                assert_eq!(patterns[0].subject, "?s");
626            }
627            _ => panic!("expected Select"),
628        }
629    }
630
631    #[test]
632    fn test_builder_add_filter() {
633        let node = SubqueryBuilder::new().add_filter("?x > 0").build();
634        match &node {
635            SubqueryNode::Select { filters, .. } => {
636                assert_eq!(filters.len(), 1);
637            }
638            _ => panic!("expected Select"),
639        }
640    }
641
642    #[test]
643    fn test_builder_multiple_patterns() {
644        let node = SubqueryBuilder::new()
645            .add_pattern("?s", "<p:a>", "?x")
646            .add_pattern("?s", "<p:b>", "?y")
647            .build();
648        match &node {
649            SubqueryNode::Select { patterns, .. } => assert_eq!(patterns.len(), 2),
650            _ => panic!("expected Select"),
651        }
652    }
653
654    #[test]
655    fn test_builder_multiple_filters() {
656        let node = SubqueryBuilder::new()
657            .add_filter("?x > 0")
658            .add_filter("?x < 100")
659            .build();
660        match &node {
661            SubqueryNode::Select { filters, .. } => assert_eq!(filters.len(), 2),
662            _ => panic!("expected Select"),
663        }
664    }
665
666    #[test]
667    fn test_builder_dedup_vars() {
668        let node = SubqueryBuilder::new().select(["?x", "?y", "?x"]).build();
669        let vars = node.projected_vars();
670        assert_eq!(vars, vec!["?x", "?y"]);
671    }
672
673    // -----------------------------------------------------------------------
674    // SubqueryNode::to_sparql tests
675    // -----------------------------------------------------------------------
676
677    #[test]
678    fn test_to_sparql_empty_select_star() {
679        let node = SubqueryBuilder::new().build();
680        let sparql = node.to_sparql();
681        assert!(sparql.contains("SELECT *"));
682        assert!(sparql.contains("WHERE"));
683    }
684
685    #[test]
686    fn test_to_sparql_select_vars() {
687        let node = SubqueryBuilder::new().select(["?x", "?y"]).build();
688        let sparql = node.to_sparql();
689        assert!(sparql.contains("SELECT ?x ?y"));
690    }
691
692    #[test]
693    fn test_to_sparql_with_pattern() {
694        let node = SubqueryBuilder::new()
695            .select(["?s"])
696            .add_pattern("?s", "<rdf:type>", "<owl:Class>")
697            .build();
698        let sparql = node.to_sparql();
699        assert!(sparql.contains("?s <rdf:type> <owl:Class> ."));
700    }
701
702    #[test]
703    fn test_to_sparql_with_filter() {
704        let node = SubqueryBuilder::new()
705            .select(["?x"])
706            .add_pattern("?s", "<p:age>", "?x")
707            .add_filter("?x >= 18")
708            .build();
709        let sparql = node.to_sparql();
710        assert!(sparql.contains("FILTER"));
711        assert!(sparql.contains("?x >= 18"));
712    }
713
714    // -----------------------------------------------------------------------
715    // EXISTS / NOT EXISTS / MINUS tests
716    // -----------------------------------------------------------------------
717
718    #[test]
719    fn test_build_exists() {
720        let node = SubqueryBuilder::new()
721            .add_pattern("?s", "<p:type>", "<p:A>")
722            .build_exists();
723        match &node {
724            SubqueryNode::Exists(_) => {}
725            _ => panic!("expected Exists"),
726        }
727        let sparql = node.to_sparql();
728        assert!(sparql.starts_with("EXISTS"));
729    }
730
731    #[test]
732    fn test_build_not_exists() {
733        let node = SubqueryBuilder::new()
734            .add_pattern("?s", "<p:type>", "<p:B>")
735            .build_not_exists();
736        match &node {
737            SubqueryNode::NotExists(_) => {}
738            _ => panic!("expected NotExists"),
739        }
740        let sparql = node.to_sparql();
741        assert!(sparql.starts_with("NOT EXISTS"));
742    }
743
744    #[test]
745    fn test_build_minus() {
746        let node = SubqueryBuilder::new()
747            .add_pattern("?s", "<p:type>", "<p:C>")
748            .build_minus();
749        match &node {
750            SubqueryNode::Minus(_) => {}
751            _ => panic!("expected Minus"),
752        }
753        let sparql = node.to_sparql();
754        assert!(sparql.starts_with("MINUS"));
755    }
756
757    #[test]
758    fn test_exists_to_sparql_contains_inner() {
759        let node = SubqueryBuilder::new()
760            .select(["?x"])
761            .add_pattern("?x", "<p:a>", "?y")
762            .build_exists();
763        let sparql = node.to_sparql();
764        assert!(sparql.contains("EXISTS"));
765        assert!(sparql.contains("?x <p:a> ?y"));
766    }
767
768    #[test]
769    fn test_minus_to_sparql_contains_inner() {
770        let node = SubqueryBuilder::new()
771            .select(["?x"])
772            .add_pattern("?x", "<p:b>", "?z")
773            .build_minus();
774        let sparql = node.to_sparql();
775        assert!(sparql.contains("MINUS"));
776        assert!(sparql.contains("?x <p:b> ?z"));
777    }
778
779    // -----------------------------------------------------------------------
780    // Nesting tests
781    // -----------------------------------------------------------------------
782
783    #[test]
784    fn test_nest_inner() {
785        let inner = SubqueryBuilder::new()
786            .select(["?x"])
787            .add_pattern("?x", "<p:type>", "<p:A>")
788            .build();
789        let outer = SubqueryBuilder::new().select(["?x"]).nest(inner).build();
790        match &outer {
791            SubqueryNode::Select { inner, .. } => assert!(inner.is_some()),
792            _ => panic!("expected Select"),
793        }
794    }
795
796    #[test]
797    fn test_nest_to_sparql_contains_inner_query() {
798        let inner = SubqueryBuilder::new()
799            .select(["?x"])
800            .add_pattern("?x", "<p:type>", "<p:A>")
801            .build();
802        let outer = SubqueryBuilder::new().select(["?x"]).nest(inner).build();
803        let sparql = outer.to_sparql();
804        assert!(sparql.contains("SELECT ?x WHERE"));
805        // Inner query should appear inside the outer
806        assert!(sparql.contains("?x <p:type> <p:A>"));
807    }
808
809    #[test]
810    fn test_depth_unnested() {
811        let node = select_xy();
812        assert_eq!(node.depth(), 1);
813    }
814
815    #[test]
816    fn test_depth_nested() {
817        let inner = select_xy();
818        let outer = SubqueryBuilder::new().select(["?x"]).nest(inner).build();
819        assert_eq!(outer.depth(), 2);
820    }
821
822    #[test]
823    fn test_is_empty_true() {
824        let node = SubqueryBuilder::new().build();
825        assert!(node.is_empty());
826    }
827
828    #[test]
829    fn test_is_empty_false_with_pattern() {
830        let node = SubqueryBuilder::new()
831            .add_pattern("?s", "<p>", "?o")
832            .build();
833        assert!(!node.is_empty());
834    }
835
836    // -----------------------------------------------------------------------
837    // SubqueryNormalizer tests
838    // -----------------------------------------------------------------------
839
840    #[test]
841    fn test_normalizer_no_op_on_flat() {
842        let node = SubqueryBuilder::new()
843            .select(["?x"])
844            .add_pattern("?x", "<p>", "?o")
845            .build();
846        let normalizer = SubqueryNormalizer::new();
847        let result = normalizer.normalize(node.clone());
848        assert_eq!(result, node);
849    }
850
851    #[test]
852    fn test_normalizer_merges_empty_outer() {
853        // Outer has no patterns/filters, inner has patterns → merge
854        let inner = SubqueryBuilder::new()
855            .select(["?x"])
856            .add_pattern("?x", "<p:type>", "<p:A>")
857            .build();
858        let outer = SubqueryBuilder::new().select(["?x"]).nest(inner).build();
859        let normalizer = SubqueryNormalizer::new();
860        let result = normalizer.normalize(outer);
861        // After merging, there should be no nested inner
862        match &result {
863            SubqueryNode::Select {
864                patterns, inner, ..
865            } => {
866                assert!(!patterns.is_empty(), "patterns should be merged up");
867                assert!(inner.is_none(), "inner should be collapsed");
868            }
869            _ => panic!("expected Select"),
870        }
871    }
872
873    #[test]
874    fn test_normalizer_keeps_nested_when_outer_has_patterns() {
875        let inner = SubqueryBuilder::new()
876            .select(["?x"])
877            .add_pattern("?x", "<p:type>", "<p:A>")
878            .build();
879        let outer = SubqueryBuilder::new()
880            .select(["?x"])
881            .add_pattern("?y", "<p:knows>", "?x")
882            .nest(inner)
883            .build();
884        let normalizer = SubqueryNormalizer::new();
885        let result = normalizer.normalize(outer);
886        match &result {
887            SubqueryNode::Select { inner, .. } => {
888                assert!(
889                    inner.is_some(),
890                    "should NOT collapse when outer has patterns"
891                );
892            }
893            _ => panic!("expected Select"),
894        }
895    }
896
897    #[test]
898    fn test_normalizer_exists_delegates() {
899        let inner = SubqueryBuilder::new()
900            .select(["?x"])
901            .add_pattern("?x", "<p>", "?o")
902            .build();
903        let node = SubqueryNode::Exists(Box::new(inner));
904        let normalizer = SubqueryNormalizer::new();
905        let result = normalizer.normalize(node);
906        match result {
907            SubqueryNode::Exists(_) => {}
908            _ => panic!("expected Exists wrapper to be preserved"),
909        }
910    }
911
912    #[test]
913    fn test_normalizer_not_exists_delegates() {
914        let inner = SubqueryBuilder::new()
915            .select(["?x"])
916            .add_pattern("?x", "<p>", "?o")
917            .build();
918        let node = SubqueryNode::NotExists(Box::new(inner));
919        let normalizer = SubqueryNormalizer::new();
920        let result = normalizer.normalize(node);
921        match result {
922            SubqueryNode::NotExists(_) => {}
923            _ => panic!("expected NotExists wrapper preserved"),
924        }
925    }
926
927    #[test]
928    fn test_normalizer_minus_delegates() {
929        let inner = SubqueryBuilder::new()
930            .select(["?x"])
931            .add_pattern("?x", "<p>", "?o")
932            .build();
933        let node = SubqueryNode::Minus(Box::new(inner));
934        let normalizer = SubqueryNormalizer::new();
935        let result = normalizer.normalize(node);
936        match result {
937            SubqueryNode::Minus(_) => {}
938            _ => panic!("expected Minus wrapper preserved"),
939        }
940    }
941
942    // -----------------------------------------------------------------------
943    // SubqueryOptimizer tests
944    // -----------------------------------------------------------------------
945
946    #[test]
947    fn test_optimizer_no_push_when_no_inner() {
948        let node = SubqueryBuilder::new()
949            .select(["?x"])
950            .add_pattern("?x", "<p>", "?o")
951            .add_filter("?x > 0")
952            .build();
953        let optimizer = SubqueryOptimizer::new();
954        let result = optimizer.optimize(node);
955        match &result {
956            SubqueryNode::Select { filters, .. } => {
957                assert_eq!(filters.len(), 1, "filter should remain when no inner");
958            }
959            _ => panic!("expected Select"),
960        }
961    }
962
963    #[test]
964    fn test_optimizer_pushes_filter_into_inner() {
965        // Outer has ?x filter; inner projects ?x → push down
966        let inner = SubqueryBuilder::new()
967            .select(["?x"])
968            .add_pattern("?x", "<p:type>", "<p:A>")
969            .build();
970        let outer = SubqueryBuilder::new()
971            .select(["?x"])
972            .add_filter("?x > 5") // references ?x which is projected by inner
973            .nest(inner)
974            .build();
975        let optimizer = SubqueryOptimizer::new();
976        let result = optimizer.optimize(outer);
977        match &result {
978            SubqueryNode::Select { filters, inner, .. } => {
979                assert!(
980                    filters.is_empty(),
981                    "filter should have been pushed into inner"
982                );
983                if let Some(inner_node) = inner {
984                    match inner_node.as_ref() {
985                        SubqueryNode::Select { filters, .. } => {
986                            assert_eq!(filters.len(), 1, "inner should have received filter");
987                        }
988                        _ => panic!("expected Select inner"),
989                    }
990                } else {
991                    panic!("inner expected");
992                }
993            }
994            _ => panic!("expected Select"),
995        }
996    }
997
998    #[test]
999    fn test_optimizer_keeps_filter_when_var_not_projected() {
1000        // Inner projects only ?x; filter references ?z which is not projected
1001        let inner = SubqueryBuilder::new()
1002            .select(["?x"])
1003            .add_pattern("?x", "<p:type>", "<p:A>")
1004            .build();
1005        let outer = SubqueryBuilder::new()
1006            .select(["?x"])
1007            .add_filter("?z > 5")
1008            .nest(inner)
1009            .build();
1010        let optimizer = SubqueryOptimizer::new();
1011        let result = optimizer.optimize(outer);
1012        match &result {
1013            SubqueryNode::Select { filters, .. } => {
1014                assert_eq!(filters.len(), 1, "filter with ?z must stay in outer");
1015            }
1016            _ => panic!("expected Select"),
1017        }
1018    }
1019
1020    #[test]
1021    fn test_optimizer_partial_push() {
1022        // Two filters: one pushable (?x), one not (?z)
1023        let inner = SubqueryBuilder::new()
1024            .select(["?x"])
1025            .add_pattern("?x", "<p:type>", "<p:A>")
1026            .build();
1027        let outer = SubqueryBuilder::new()
1028            .select(["?x"])
1029            .add_filter("?x > 5")
1030            .add_filter("?z < 100")
1031            .nest(inner)
1032            .build();
1033        let optimizer = SubqueryOptimizer::new();
1034        let result = optimizer.optimize(outer);
1035        match &result {
1036            SubqueryNode::Select { filters, inner, .. } => {
1037                assert_eq!(filters.len(), 1, "one non-pushable filter stays in outer");
1038                if let Some(inner_node) = inner {
1039                    match inner_node.as_ref() {
1040                        SubqueryNode::Select { filters, .. } => {
1041                            assert_eq!(filters.len(), 1, "one filter pushed into inner");
1042                        }
1043                        _ => panic!("expected Select inner"),
1044                    }
1045                } else {
1046                    panic!("inner expected");
1047                }
1048            }
1049            _ => panic!("expected Select"),
1050        }
1051    }
1052
1053    #[test]
1054    fn test_optimizer_exists_delegates() {
1055        let inner = SubqueryBuilder::new()
1056            .select(["?x"])
1057            .add_pattern("?x", "<p>", "?o")
1058            .build();
1059        let node = SubqueryNode::Exists(Box::new(inner));
1060        let optimizer = SubqueryOptimizer::new();
1061        let result = optimizer.optimize(node);
1062        match result {
1063            SubqueryNode::Exists(_) => {}
1064            _ => panic!("Exists wrapper should be preserved"),
1065        }
1066    }
1067
1068    #[test]
1069    fn test_optimizer_not_exists_delegates() {
1070        let inner = SubqueryBuilder::new()
1071            .select(["?x"])
1072            .add_pattern("?x", "<p>", "?o")
1073            .build();
1074        let node = SubqueryNode::NotExists(Box::new(inner));
1075        let optimizer = SubqueryOptimizer::new();
1076        let result = optimizer.optimize(node);
1077        match result {
1078            SubqueryNode::NotExists(_) => {}
1079            _ => panic!("NotExists wrapper should be preserved"),
1080        }
1081    }
1082
1083    #[test]
1084    fn test_optimizer_minus_delegates() {
1085        let inner = SubqueryBuilder::new()
1086            .select(["?x"])
1087            .add_pattern("?x", "<p>", "?o")
1088            .build();
1089        let node = SubqueryNode::Minus(Box::new(inner));
1090        let optimizer = SubqueryOptimizer::new();
1091        let result = optimizer.optimize(node);
1092        match result {
1093            SubqueryNode::Minus(_) => {}
1094            _ => panic!("Minus wrapper should be preserved"),
1095        }
1096    }
1097
1098    // -----------------------------------------------------------------------
1099    // Edge cases
1100    // -----------------------------------------------------------------------
1101
1102    #[test]
1103    fn test_empty_patterns_select_star_sparql() {
1104        let node = SubqueryBuilder::new().build();
1105        let sparql = node.to_sparql();
1106        assert!(sparql.contains("SELECT *"));
1107    }
1108
1109    #[test]
1110    fn test_select_with_all_components() {
1111        let node = SubqueryBuilder::new()
1112            .select(["?s", "?p", "?o"])
1113            .add_pattern("?s", "?p", "?o")
1114            .add_filter("isIRI(?s)")
1115            .build();
1116        let sparql = node.to_sparql();
1117        assert!(sparql.contains("SELECT ?s ?p ?o"));
1118        assert!(sparql.contains("?s ?p ?o ."));
1119        assert!(sparql.contains("FILTER"));
1120        assert!(sparql.contains("isIRI(?s)"));
1121    }
1122
1123    #[test]
1124    fn test_triple_nesting_depth() {
1125        let l1 = SubqueryBuilder::new()
1126            .select(["?a"])
1127            .add_pattern("?a", "<p>", "?b")
1128            .build();
1129        let l2 = SubqueryBuilder::new().select(["?a"]).nest(l1).build();
1130        let l3 = SubqueryBuilder::new().select(["?a"]).nest(l2).build();
1131        assert_eq!(l3.depth(), 3);
1132    }
1133
1134    #[test]
1135    fn test_normalizer_triple_nesting_collapses() {
1136        let l1 = SubqueryBuilder::new()
1137            .select(["?a"])
1138            .add_pattern("?a", "<p>", "?b")
1139            .build();
1140        let l2 = SubqueryBuilder::new().select(["?a"]).nest(l1).build();
1141        let l3 = SubqueryBuilder::new().select(["?a"]).nest(l2).build();
1142        let normalizer = SubqueryNormalizer::new();
1143        let result = normalizer.normalize(l3);
1144        // After full collapse all empty wrappers are removed
1145        assert!(
1146            result.depth() <= 2,
1147            "triple nesting should collapse to ≤2 levels"
1148        );
1149    }
1150
1151    #[test]
1152    fn test_projected_vars_non_select() {
1153        let node = SubqueryBuilder::new()
1154            .add_pattern("?x", "<p>", "?o")
1155            .build_exists();
1156        assert!(node.projected_vars().is_empty());
1157    }
1158
1159    #[test]
1160    fn test_filter_expr_as_str() {
1161        let f = FilterExpr::new("LANG(?label) = \"en\"");
1162        assert_eq!(f.as_str(), "LANG(?label) = \"en\"");
1163    }
1164
1165    #[test]
1166    fn test_no_push_when_inner_projects_star() {
1167        // Inner uses SELECT * (empty vars) — optimizer must NOT push filters (safety)
1168        let inner = SubqueryBuilder::new()
1169            .add_pattern("?x", "<p:type>", "<p:A>")
1170            .build(); // vars is empty → SELECT *
1171        let outer = SubqueryBuilder::new()
1172            .select(["?x"])
1173            .add_filter("?x > 5")
1174            .nest(inner)
1175            .build();
1176        let optimizer = SubqueryOptimizer::new();
1177        let result = optimizer.optimize(outer);
1178        match &result {
1179            SubqueryNode::Select { filters, .. } => {
1180                assert_eq!(filters.len(), 1, "filter must not be pushed into SELECT *");
1181            }
1182            _ => panic!("expected Select"),
1183        }
1184    }
1185}
oxirs_core/sparql/subquery_builder.rs

oxirs_core/sparql/
subquery_builder.rs
