oxirs_arq/
optional_evaluator.rs

1/// SPARQL 1.1 OPTIONAL clause evaluator.
2///
3/// Implements left outer join semantics for the OPTIONAL keyword, keeping all
4/// left-side bindings and extending them with matching right-side bindings when
5/// available.  Supports nested OPTIONAL, OPTIONAL with FILTER, BIND
6/// expressions, and hash-based join for large result sets.
7use std::collections::{HashMap, HashSet};
8
9// ── Error type ────────────────────────────────────────────────────────────────
10
11/// Errors that can occur during OPTIONAL clause evaluation.
12#[derive(Debug, Clone, PartialEq, Eq)]
13pub enum OptionalError {
14    /// A variable referenced in a filter or bind is invalid.
15    InvalidVariable(String),
16    /// The nesting depth of OPTIONAL clauses exceeds the configured limit.
17    NestingDepthExceeded {
18        /// The maximum allowed nesting depth.
19        max_depth: usize,
20    },
21    /// A BIND expression references a variable that is already bound.
22    BindConflict {
23        /// The conflicting variable name.
24        variable: String,
25    },
26    /// Generic evaluation failure.
27    EvaluationError(String),
28}
29
30impl std::fmt::Display for OptionalError {
31    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
32        match self {
33            Self::InvalidVariable(v) => write!(f, "invalid variable: {v}"),
34            Self::NestingDepthExceeded { max_depth } => {
35                write!(f, "OPTIONAL nesting depth exceeded (max {max_depth})")
36            }
37            Self::BindConflict { variable } => {
38                write!(f, "BIND conflict: variable ?{variable} already bound")
39            }
40            Self::EvaluationError(msg) => write!(f, "evaluation error: {msg}"),
41        }
42    }
43}
44
45impl std::error::Error for OptionalError {}
46
47// ── Solution mapping ──────────────────────────────────────────────────────────
48
49/// A single SPARQL solution: a mapping from variable names to values.
50///
51/// Variables are stored without the leading `?` sigil.
52#[derive(Debug, Clone, PartialEq, Eq)]
53pub struct SolutionMapping {
54    bindings: HashMap<String, String>,
55}
56
57impl SolutionMapping {
58    /// Create an empty solution mapping.
59    pub fn new() -> Self {
60        Self {
61            bindings: HashMap::new(),
62        }
63    }
64
65    /// Create a mapping from an iterator of `(variable, value)` pairs.
66    pub fn from_pairs(iter: impl IntoIterator<Item = (String, String)>) -> Self {
67        Self {
68            bindings: iter.into_iter().collect(),
69        }
70    }
71
72    /// Bind a variable to a value.
73    pub fn bind(&mut self, var: impl Into<String>, val: impl Into<String>) {
74        self.bindings.insert(var.into(), val.into());
75    }
76
77    /// Look up the value bound to a variable.
78    pub fn get(&self, var: &str) -> Option<&str> {
79        self.bindings.get(var).map(|s| s.as_str())
80    }
81
82    /// Returns `true` if the variable is bound.
83    pub fn is_bound(&self, var: &str) -> bool {
84        self.bindings.contains_key(var)
85    }
86
87    /// Returns the set of bound variable names.
88    pub fn variables(&self) -> HashSet<&str> {
89        self.bindings.keys().map(|k| k.as_str()).collect()
90    }
91
92    /// Returns the number of bound variables.
93    pub fn len(&self) -> usize {
94        self.bindings.len()
95    }
96
97    /// Returns `true` if no variables are bound.
98    pub fn is_empty(&self) -> bool {
99        self.bindings.is_empty()
100    }
101
102    /// Check whether two mappings are *compatible*: they agree on every
103    /// shared variable.
104    pub fn is_compatible_with(&self, other: &SolutionMapping) -> bool {
105        for (k, v) in &self.bindings {
106            if let Some(other_v) = other.bindings.get(k) {
107                if v != other_v {
108                    return false;
109                }
110            }
111        }
112        true
113    }
114
115    /// Merge two compatible mappings.  Returns `None` if they are incompatible.
116    pub fn merge(&self, other: &SolutionMapping) -> Option<SolutionMapping> {
117        if !self.is_compatible_with(other) {
118            return None;
119        }
120        let mut merged = self.clone();
121        for (k, v) in &other.bindings {
122            merged
123                .bindings
124                .entry(k.clone())
125                .or_insert_with(|| v.clone());
126        }
127        Some(merged)
128    }
129
130    /// Return an immutable reference to the inner map.
131    pub fn inner(&self) -> &HashMap<String, String> {
132        &self.bindings
133    }
134}
135
136impl Default for SolutionMapping {
137    fn default() -> Self {
138        Self::new()
139    }
140}
141
142impl FromIterator<(String, String)> for SolutionMapping {
143    fn from_iter<I: IntoIterator<Item = (String, String)>>(iter: I) -> Self {
144        Self {
145            bindings: iter.into_iter().collect(),
146        }
147    }
148}
149
150// ── Filter expression ─────────────────────────────────────────────────────────
151
152/// A simple filter expression that can be evaluated against a `SolutionMapping`.
153#[derive(Debug, Clone, PartialEq, Eq)]
154pub enum FilterExpr {
155    /// BOUND(?var) — true when the variable is bound.
156    Bound(String),
157    /// !BOUND(?var) — true when the variable is *not* bound.
158    NotBound(String),
159    /// ?var = "value" — equality check.
160    Equals { var: String, value: String },
161    /// ?var != "value" — inequality check.
162    NotEquals { var: String, value: String },
163    /// Logical AND.
164    And(Box<FilterExpr>, Box<FilterExpr>),
165    /// Logical OR.
166    Or(Box<FilterExpr>, Box<FilterExpr>),
167    /// Logical NOT.
168    Not(Box<FilterExpr>),
169    /// ?var > "value" (lexicographic comparison).
170    GreaterThan { var: String, value: String },
171    /// ?var < "value" (lexicographic comparison).
172    LessThan { var: String, value: String },
173    /// Always true.
174    True,
175    /// Always false.
176    False,
177}
178
179impl FilterExpr {
180    /// Evaluate the filter against a solution mapping.
181    pub fn evaluate(&self, mapping: &SolutionMapping) -> bool {
182        match self {
183            Self::Bound(var) => mapping.is_bound(var),
184            Self::NotBound(var) => !mapping.is_bound(var),
185            Self::Equals { var, value } => mapping.get(var).is_some_and(|v| v == value),
186            Self::NotEquals { var, value } => mapping.get(var).map_or(true, |v| v != value),
187            Self::And(a, b) => a.evaluate(mapping) && b.evaluate(mapping),
188            Self::Or(a, b) => a.evaluate(mapping) || b.evaluate(mapping),
189            Self::Not(inner) => !inner.evaluate(mapping),
190            Self::GreaterThan { var, value } => {
191                mapping.get(var).is_some_and(|v| v > value.as_str())
192            }
193            Self::LessThan { var, value } => mapping.get(var).is_some_and(|v| v < value.as_str()),
194            Self::True => true,
195            Self::False => false,
196        }
197    }
198
199    /// Collect all variables referenced by this expression.
200    pub fn referenced_variables(&self) -> HashSet<String> {
201        let mut vars = HashSet::new();
202        self.collect_vars(&mut vars);
203        vars
204    }
205
206    fn collect_vars(&self, vars: &mut HashSet<String>) {
207        match self {
208            Self::Bound(v) | Self::NotBound(v) => {
209                vars.insert(v.clone());
210            }
211            Self::Equals { var, .. }
212            | Self::NotEquals { var, .. }
213            | Self::GreaterThan { var, .. }
214            | Self::LessThan { var, .. } => {
215                vars.insert(var.clone());
216            }
217            Self::And(a, b) | Self::Or(a, b) => {
218                a.collect_vars(vars);
219                b.collect_vars(vars);
220            }
221            Self::Not(inner) => inner.collect_vars(vars),
222            Self::True | Self::False => {}
223        }
224    }
225}
226
227// ── BIND expression ───────────────────────────────────────────────────────────
228
229/// A BIND expression: `BIND(expr AS ?var)`.
230#[derive(Debug, Clone, PartialEq, Eq)]
231pub struct BindExpr {
232    /// The target variable name (without `?`).
233    pub variable: String,
234    /// The expression producing the value.
235    pub expression: BindValue,
236}
237
238/// The value side of a BIND expression.
239#[derive(Debug, Clone, PartialEq, Eq)]
240pub enum BindValue {
241    /// A constant value.
242    Constant(String),
243    /// Copy the value from another variable.
244    Variable(String),
245    /// Concatenation of two expressions.
246    Concat(Box<BindValue>, Box<BindValue>),
247}
248
249impl BindValue {
250    /// Evaluate the bind value in the context of a solution mapping.
251    pub fn evaluate(&self, mapping: &SolutionMapping) -> Option<String> {
252        match self {
253            Self::Constant(c) => Some(c.clone()),
254            Self::Variable(var) => mapping.get(var).map(|s| s.to_string()),
255            Self::Concat(a, b) => {
256                let a_val = a.evaluate(mapping)?;
257                let b_val = b.evaluate(mapping)?;
258                Some(format!("{a_val}{b_val}"))
259            }
260        }
261    }
262}
263
264// ── Triple pattern (right-side data) ──────────────────────────────────────────
265
266/// A triple pattern used in the optional clause body.
267#[derive(Debug, Clone, PartialEq, Eq)]
268pub struct OptionalTriplePattern {
269    /// Subject (variable or constant).
270    pub subject: String,
271    /// Predicate (variable or constant).
272    pub predicate: String,
273    /// Object (variable or constant).
274    pub object: String,
275}
276
277impl OptionalTriplePattern {
278    /// Create a new triple pattern.
279    pub fn new(
280        subject: impl Into<String>,
281        predicate: impl Into<String>,
282        object: impl Into<String>,
283    ) -> Self {
284        Self {
285            subject: subject.into(),
286            predicate: predicate.into(),
287            object: object.into(),
288        }
289    }
290
291    /// Returns `true` if a term is a variable (starts with `?`).
292    pub fn is_variable(term: &str) -> bool {
293        term.starts_with('?')
294    }
295
296    /// Collect all variables appearing in this pattern.
297    pub fn variables(&self) -> Vec<&str> {
298        let mut vars = Vec::new();
299        if Self::is_variable(&self.subject) {
300            vars.push(self.subject.as_str());
301        }
302        if Self::is_variable(&self.predicate) {
303            vars.push(self.predicate.as_str());
304        }
305        if Self::is_variable(&self.object) {
306            vars.push(self.object.as_str());
307        }
308        vars
309    }
310
311    /// Try to match this pattern against a concrete triple `(s, p, o)` given
312    /// the current bindings, returning an extended mapping on success.
313    pub fn match_triple(
314        &self,
315        s: &str,
316        p: &str,
317        o: &str,
318        current: &SolutionMapping,
319    ) -> Option<SolutionMapping> {
320        let mut extended = current.clone();
321        if !self.match_term(&self.subject, s, &mut extended) {
322            return None;
323        }
324        if !self.match_term(&self.predicate, p, &mut extended) {
325            return None;
326        }
327        if !self.match_term(&self.object, o, &mut extended) {
328            return None;
329        }
330        Some(extended)
331    }
332
333    fn match_term(&self, pattern: &str, value: &str, mapping: &mut SolutionMapping) -> bool {
334        if Self::is_variable(pattern) {
335            let var_name = &pattern[1..];
336            if let Some(bound) = mapping.get(var_name) {
337                bound == value
338            } else {
339                mapping.bind(var_name.to_string(), value.to_string());
340                true
341            }
342        } else {
343            pattern == value
344        }
345    }
346}
347
348// ── Optional clause ───────────────────────────────────────────────────────────
349
350/// Represents one `OPTIONAL { ... }` clause in a SPARQL query.
351#[derive(Debug, Clone)]
352pub struct OptionalClause {
353    /// Triple patterns in the optional body.
354    pub patterns: Vec<OptionalTriplePattern>,
355    /// Filter expression applied within the optional scope.
356    pub filter: Option<FilterExpr>,
357    /// BIND expressions inside the optional scope.
358    pub bind_exprs: Vec<BindExpr>,
359    /// Nested OPTIONAL clauses.
360    pub nested: Vec<OptionalClause>,
361}
362
363impl OptionalClause {
364    /// Create an optional clause with the given patterns.
365    pub fn new(patterns: Vec<OptionalTriplePattern>) -> Self {
366        Self {
367            patterns,
368            filter: None,
369            bind_exprs: Vec::new(),
370            nested: Vec::new(),
371        }
372    }
373
374    /// Set a filter for this optional scope.
375    pub fn with_filter(mut self, filter: FilterExpr) -> Self {
376        self.filter = Some(filter);
377        self
378    }
379
380    /// Add a BIND expression.
381    pub fn with_bind(mut self, bind: BindExpr) -> Self {
382        self.bind_exprs.push(bind);
383        self
384    }
385
386    /// Add a nested OPTIONAL clause.
387    pub fn with_nested(mut self, nested: OptionalClause) -> Self {
388        self.nested.push(nested);
389        self
390    }
391}
392
393// ── Evaluator configuration ──────────────────────────────────────────────────
394
395/// Configuration for the OPTIONAL evaluator.
396#[derive(Debug, Clone)]
397pub struct OptionalConfig {
398    /// Maximum allowed nesting depth for OPTIONAL clauses.
399    pub max_nesting_depth: usize,
400    /// When `true`, use a hash-based join strategy for large result sets.
401    pub use_hash_join: bool,
402    /// Threshold number of right-side solutions above which hash join is used.
403    pub hash_join_threshold: usize,
404}
405
406impl Default for OptionalConfig {
407    fn default() -> Self {
408        Self {
409            max_nesting_depth: 16,
410            use_hash_join: true,
411            hash_join_threshold: 64,
412        }
413    }
414}
415
416// ── Evaluation statistics ────────────────────────────────────────────────────
417
418/// Statistics gathered during OPTIONAL evaluation.
419#[derive(Debug, Clone, Default)]
420pub struct OptionalStats {
421    /// Number of left-side solutions processed.
422    pub left_solutions: usize,
423    /// Number of right-side solutions considered.
424    pub right_solutions: usize,
425    /// Number of successful joins (left matched at least one right).
426    pub joined_count: usize,
427    /// Number of left solutions that had no right-side match (pass-through).
428    pub unmatched_count: usize,
429    /// Number of nested OPTIONAL evaluations performed.
430    pub nested_evaluations: usize,
431    /// Number of solutions eliminated by filters.
432    pub filtered_count: usize,
433}
434
435// ── Evaluator ────────────────────────────────────────────────────────────────
436
437/// SPARQL 1.1 OPTIONAL clause evaluator implementing left outer join.
438pub struct OptionalEvaluator {
439    config: OptionalConfig,
440}
441
442impl OptionalEvaluator {
443    /// Create a new evaluator with default configuration.
444    pub fn new() -> Self {
445        Self {
446            config: OptionalConfig::default(),
447        }
448    }
449
450    /// Create a new evaluator with the given configuration.
451    pub fn with_config(config: OptionalConfig) -> Self {
452        Self { config }
453    }
454
455    /// Evaluate an OPTIONAL clause against left-side solutions and a set of
456    /// data triples, returning the resulting solution sequence and statistics.
457    ///
458    /// This implements the left outer join: for each left solution, attempt to
459    /// match the optional patterns against the data.  If matching succeeds,
460    /// extend the solution; otherwise, keep the original left solution.
461    pub fn evaluate(
462        &self,
463        left: &[SolutionMapping],
464        clause: &OptionalClause,
465        data: &[(String, String, String)],
466    ) -> Result<(Vec<SolutionMapping>, OptionalStats), OptionalError> {
467        self.evaluate_at_depth(left, clause, data, 0)
468    }
469
470    fn evaluate_at_depth(
471        &self,
472        left: &[SolutionMapping],
473        clause: &OptionalClause,
474        data: &[(String, String, String)],
475        depth: usize,
476    ) -> Result<(Vec<SolutionMapping>, OptionalStats), OptionalError> {
477        if depth > self.config.max_nesting_depth {
478            return Err(OptionalError::NestingDepthExceeded {
479                max_depth: self.config.max_nesting_depth,
480            });
481        }
482
483        // Compute right-side solutions by matching patterns against data.
484        let right = self.match_patterns(&clause.patterns, data);
485
486        let mut stats = OptionalStats {
487            left_solutions: left.len(),
488            right_solutions: right.len(),
489            ..OptionalStats::default()
490        };
491
492        // Choose join strategy based on configuration and data size.
493        let use_hash = self.config.use_hash_join && right.len() >= self.config.hash_join_threshold;
494
495        let mut result = Vec::new();
496
497        if use_hash {
498            // Determine shared variables for hash key.
499            let shared_vars = self.shared_variables(left, &right);
500            let hash_index = self.build_hash_index(&right, &shared_vars);
501
502            for left_sol in left {
503                let key = self.hash_key(left_sol, &shared_vars);
504                let mut matched = false;
505
506                if let Some(candidates) = hash_index.get(&key) {
507                    for right_sol in candidates {
508                        if let Some(merged) = left_sol.merge(right_sol) {
509                            let merged = self.apply_binds(&merged, &clause.bind_exprs)?;
510                            if self.passes_filter(&merged, &clause.filter) {
511                                result.push(merged);
512                                matched = true;
513                            } else {
514                                stats.filtered_count += 1;
515                            }
516                        }
517                    }
518                }
519
520                if !matched {
521                    result.push(left_sol.clone());
522                    stats.unmatched_count += 1;
523                } else {
524                    stats.joined_count += 1;
525                }
526            }
527        } else {
528            // Nested-loop join.
529            for left_sol in left {
530                let mut matched = false;
531
532                for right_sol in &right {
533                    if let Some(merged) = left_sol.merge(right_sol) {
534                        let merged = self.apply_binds(&merged, &clause.bind_exprs)?;
535                        if self.passes_filter(&merged, &clause.filter) {
536                            result.push(merged);
537                            matched = true;
538                        } else {
539                            stats.filtered_count += 1;
540                        }
541                    }
542                }
543
544                if !matched {
545                    result.push(left_sol.clone());
546                    stats.unmatched_count += 1;
547                } else {
548                    stats.joined_count += 1;
549                }
550            }
551        }
552
553        // Process nested OPTIONAL clauses.
554        for nested in &clause.nested {
555            stats.nested_evaluations += 1;
556            let (nested_result, nested_stats) =
557                self.evaluate_at_depth(&result, nested, data, depth + 1)?;
558            result = nested_result;
559            stats.joined_count += nested_stats.joined_count;
560            stats.unmatched_count += nested_stats.unmatched_count;
561            stats.filtered_count += nested_stats.filtered_count;
562            stats.nested_evaluations += nested_stats.nested_evaluations;
563        }
564
565        Ok((result, stats))
566    }
567
568    /// Match a set of triple patterns against data, producing all matching
569    /// solution mappings.
570    fn match_patterns(
571        &self,
572        patterns: &[OptionalTriplePattern],
573        data: &[(String, String, String)],
574    ) -> Vec<SolutionMapping> {
575        if patterns.is_empty() {
576            return vec![SolutionMapping::new()];
577        }
578
579        let mut solutions = vec![SolutionMapping::new()];
580
581        for pattern in patterns {
582            let mut next_solutions = Vec::new();
583            for sol in &solutions {
584                for (s, p, o) in data {
585                    if let Some(extended) = pattern.match_triple(s, p, o, sol) {
586                        next_solutions.push(extended);
587                    }
588                }
589            }
590            solutions = next_solutions;
591        }
592
593        solutions
594    }
595
596    /// Compute the set of variable names (without `?`) that appear bound in
597    /// both left and right solution sequences.
598    fn shared_variables(&self, left: &[SolutionMapping], right: &[SolutionMapping]) -> Vec<String> {
599        let left_vars: HashSet<String> = left
600            .iter()
601            .flat_map(|s| s.bindings.keys().cloned())
602            .collect();
603        let right_vars: HashSet<String> = right
604            .iter()
605            .flat_map(|s| s.bindings.keys().cloned())
606            .collect();
607        left_vars.intersection(&right_vars).cloned().collect()
608    }
609
610    /// Build a hash index over right-side solutions keyed by the shared
611    /// variables.
612    fn build_hash_index(
613        &self,
614        right: &[SolutionMapping],
615        shared_vars: &[String],
616    ) -> HashMap<Vec<Option<String>>, Vec<SolutionMapping>> {
617        let mut index: HashMap<Vec<Option<String>>, Vec<SolutionMapping>> = HashMap::new();
618        for sol in right {
619            let key = self.hash_key(sol, shared_vars);
620            index.entry(key).or_default().push(sol.clone());
621        }
622        index
623    }
624
625    /// Produce a key from a solution mapping over the given shared variables.
626    fn hash_key(&self, sol: &SolutionMapping, shared_vars: &[String]) -> Vec<Option<String>> {
627        shared_vars
628            .iter()
629            .map(|v| sol.get(v).map(|s| s.to_string()))
630            .collect()
631    }
632
633    /// Apply BIND expressions to a solution, returning a new extended mapping.
634    fn apply_binds(
635        &self,
636        mapping: &SolutionMapping,
637        binds: &[BindExpr],
638    ) -> Result<SolutionMapping, OptionalError> {
639        let mut result = mapping.clone();
640        for bind in binds {
641            if result.is_bound(&bind.variable) {
642                return Err(OptionalError::BindConflict {
643                    variable: bind.variable.clone(),
644                });
645            }
646            if let Some(val) = bind.expression.evaluate(&result) {
647                result.bind(bind.variable.clone(), val);
648            }
649        }
650        Ok(result)
651    }
652
653    /// Check whether a mapping passes the optional-scope filter.
654    fn passes_filter(&self, mapping: &SolutionMapping, filter: &Option<FilterExpr>) -> bool {
655        match filter {
656            Some(expr) => expr.evaluate(mapping),
657            None => true,
658        }
659    }
660
661    /// Convenience: evaluate multiple OPTIONAL clauses in sequence (left-to-right
662    /// composition).
663    pub fn evaluate_sequence(
664        &self,
665        initial: &[SolutionMapping],
666        clauses: &[OptionalClause],
667        data: &[(String, String, String)],
668    ) -> Result<(Vec<SolutionMapping>, Vec<OptionalStats>), OptionalError> {
669        let mut current = initial.to_vec();
670        let mut all_stats = Vec::new();
671
672        for clause in clauses {
673            let (next, stats) = self.evaluate(&current, clause, data)?;
674            current = next;
675            all_stats.push(stats);
676        }
677
678        Ok((current, all_stats))
679    }
680}
681
682impl Default for OptionalEvaluator {
683    fn default() -> Self {
684        Self::new()
685    }
686}
687
688// ── Tests ────────────────────────────────────────────────────────────────────
689
690#[cfg(test)]
691mod tests {
692    use super::*;
693
694    // ── helper ──────────────────────────────────────────────────────────────
695
696    fn mapping(pairs: &[(&str, &str)]) -> SolutionMapping {
697        SolutionMapping::from_iter(pairs.iter().map(|(k, v)| (k.to_string(), v.to_string())))
698    }
699
700    fn data() -> Vec<(String, String, String)> {
701        vec![
702            ("alice".into(), "name".into(), "Alice".into()),
703            ("alice".into(), "age".into(), "30".into()),
704            ("alice".into(), "email".into(), "alice@example.com".into()),
705            ("bob".into(), "name".into(), "Bob".into()),
706            ("bob".into(), "age".into(), "25".into()),
707            ("charlie".into(), "name".into(), "Charlie".into()),
708        ]
709    }
710
711    // ── SolutionMapping tests ───────────────────────────────────────────────
712
713    #[test]
714    fn test_solution_mapping_new() {
715        let m = SolutionMapping::new();
716        assert!(m.is_empty());
717        assert_eq!(m.len(), 0);
718    }
719
720    #[test]
721    fn test_solution_mapping_bind_and_get() {
722        let mut m = SolutionMapping::new();
723        m.bind("x", "1");
724        assert_eq!(m.get("x"), Some("1"));
725        assert_eq!(m.get("y"), None);
726        assert!(m.is_bound("x"));
727        assert!(!m.is_bound("y"));
728    }
729
730    #[test]
731    fn test_solution_mapping_from_iter() {
732        let m = mapping(&[("x", "1"), ("y", "2")]);
733        assert_eq!(m.len(), 2);
734        assert_eq!(m.get("x"), Some("1"));
735        assert_eq!(m.get("y"), Some("2"));
736    }
737
738    #[test]
739    fn test_solution_mapping_variables() {
740        let m = mapping(&[("a", "1"), ("b", "2"), ("c", "3")]);
741        let vars = m.variables();
742        assert!(vars.contains("a"));
743        assert!(vars.contains("b"));
744        assert!(vars.contains("c"));
745        assert_eq!(vars.len(), 3);
746    }
747
748    #[test]
749    fn test_solution_mapping_compatible_same_values() {
750        let a = mapping(&[("x", "1"), ("y", "2")]);
751        let b = mapping(&[("x", "1"), ("z", "3")]);
752        assert!(a.is_compatible_with(&b));
753    }
754
755    #[test]
756    fn test_solution_mapping_incompatible() {
757        let a = mapping(&[("x", "1")]);
758        let b = mapping(&[("x", "99")]);
759        assert!(!a.is_compatible_with(&b));
760    }
761
762    #[test]
763    fn test_solution_mapping_merge_compatible() {
764        let a = mapping(&[("x", "1")]);
765        let b = mapping(&[("y", "2")]);
766        let merged = a.merge(&b);
767        assert!(merged.is_some());
768        let m = merged.expect("merge should succeed");
769        assert_eq!(m.get("x"), Some("1"));
770        assert_eq!(m.get("y"), Some("2"));
771    }
772
773    #[test]
774    fn test_solution_mapping_merge_incompatible() {
775        let a = mapping(&[("x", "1")]);
776        let b = mapping(&[("x", "2")]);
777        assert!(a.merge(&b).is_none());
778    }
779
780    #[test]
781    fn test_solution_mapping_merge_overlapping_same() {
782        let a = mapping(&[("x", "1"), ("y", "2")]);
783        let b = mapping(&[("x", "1"), ("z", "3")]);
784        let merged = a.merge(&b);
785        assert!(merged.is_some());
786        let m = merged.expect("merge should succeed");
787        assert_eq!(m.get("x"), Some("1"));
788        assert_eq!(m.get("y"), Some("2"));
789        assert_eq!(m.get("z"), Some("3"));
790    }
791
792    #[test]
793    fn test_solution_mapping_default() {
794        let m = SolutionMapping::default();
795        assert!(m.is_empty());
796    }
797
798    // ── FilterExpr tests ────────────────────────────────────────────────────
799
800    #[test]
801    fn test_filter_bound() {
802        let m = mapping(&[("x", "1")]);
803        assert!(FilterExpr::Bound("x".into()).evaluate(&m));
804        assert!(!FilterExpr::Bound("y".into()).evaluate(&m));
805    }
806
807    #[test]
808    fn test_filter_not_bound() {
809        let m = mapping(&[("x", "1")]);
810        assert!(!FilterExpr::NotBound("x".into()).evaluate(&m));
811        assert!(FilterExpr::NotBound("y".into()).evaluate(&m));
812    }
813
814    #[test]
815    fn test_filter_equals() {
816        let m = mapping(&[("x", "hello")]);
817        let eq = FilterExpr::Equals {
818            var: "x".into(),
819            value: "hello".into(),
820        };
821        assert!(eq.evaluate(&m));
822        let ne = FilterExpr::Equals {
823            var: "x".into(),
824            value: "world".into(),
825        };
826        assert!(!ne.evaluate(&m));
827    }
828
829    #[test]
830    fn test_filter_not_equals() {
831        let m = mapping(&[("x", "hello")]);
832        let ne = FilterExpr::NotEquals {
833            var: "x".into(),
834            value: "world".into(),
835        };
836        assert!(ne.evaluate(&m));
837    }
838
839    #[test]
840    fn test_filter_and() {
841        let m = mapping(&[("x", "1"), ("y", "2")]);
842        let f = FilterExpr::And(
843            Box::new(FilterExpr::Bound("x".into())),
844            Box::new(FilterExpr::Bound("y".into())),
845        );
846        assert!(f.evaluate(&m));
847    }
848
849    #[test]
850    fn test_filter_or() {
851        let m = mapping(&[("x", "1")]);
852        let f = FilterExpr::Or(
853            Box::new(FilterExpr::Bound("x".into())),
854            Box::new(FilterExpr::Bound("z".into())),
855        );
856        assert!(f.evaluate(&m));
857    }
858
859    #[test]
860    fn test_filter_not() {
861        let m = mapping(&[("x", "1")]);
862        let f = FilterExpr::Not(Box::new(FilterExpr::Bound("z".into())));
863        assert!(f.evaluate(&m));
864    }
865
866    #[test]
867    fn test_filter_greater_than() {
868        let m = mapping(&[("x", "b")]);
869        let f = FilterExpr::GreaterThan {
870            var: "x".into(),
871            value: "a".into(),
872        };
873        assert!(f.evaluate(&m));
874    }
875
876    #[test]
877    fn test_filter_less_than() {
878        let m = mapping(&[("x", "a")]);
879        let f = FilterExpr::LessThan {
880            var: "x".into(),
881            value: "b".into(),
882        };
883        assert!(f.evaluate(&m));
884    }
885
886    #[test]
887    fn test_filter_true_false() {
888        let m = SolutionMapping::new();
889        assert!(FilterExpr::True.evaluate(&m));
890        assert!(!FilterExpr::False.evaluate(&m));
891    }
892
893    #[test]
894    fn test_filter_referenced_variables() {
895        let f = FilterExpr::And(
896            Box::new(FilterExpr::Bound("x".into())),
897            Box::new(FilterExpr::Equals {
898                var: "y".into(),
899                value: "v".into(),
900            }),
901        );
902        let vars = f.referenced_variables();
903        assert!(vars.contains("x"));
904        assert!(vars.contains("y"));
905        assert_eq!(vars.len(), 2);
906    }
907
908    // ── BindValue / BindExpr tests ──────────────────────────────────────────
909
910    #[test]
911    fn test_bind_value_constant() {
912        let m = SolutionMapping::new();
913        let bv = BindValue::Constant("hello".into());
914        assert_eq!(bv.evaluate(&m), Some("hello".into()));
915    }
916
917    #[test]
918    fn test_bind_value_variable() {
919        let m = mapping(&[("x", "world")]);
920        let bv = BindValue::Variable("x".into());
921        assert_eq!(bv.evaluate(&m), Some("world".into()));
922    }
923
924    #[test]
925    fn test_bind_value_variable_unbound() {
926        let m = SolutionMapping::new();
927        let bv = BindValue::Variable("x".into());
928        assert_eq!(bv.evaluate(&m), None);
929    }
930
931    #[test]
932    fn test_bind_value_concat() {
933        let m = mapping(&[("first", "John"), ("last", "Doe")]);
934        let bv = BindValue::Concat(
935            Box::new(BindValue::Variable("first".into())),
936            Box::new(BindValue::Concat(
937                Box::new(BindValue::Constant(" ".into())),
938                Box::new(BindValue::Variable("last".into())),
939            )),
940        );
941        assert_eq!(bv.evaluate(&m), Some("John Doe".into()));
942    }
943
944    // ── OptionalTriplePattern tests ─────────────────────────────────────────
945
946    #[test]
947    fn test_triple_pattern_is_variable() {
948        assert!(OptionalTriplePattern::is_variable("?x"));
949        assert!(!OptionalTriplePattern::is_variable("alice"));
950    }
951
952    #[test]
953    fn test_triple_pattern_variables() {
954        let p = OptionalTriplePattern::new("?s", "?p", "?o");
955        let vars = p.variables();
956        assert_eq!(vars.len(), 3);
957    }
958
959    #[test]
960    fn test_triple_pattern_match_all_vars() {
961        let p = OptionalTriplePattern::new("?s", "?p", "?o");
962        let m = SolutionMapping::new();
963        let result = p.match_triple("alice", "name", "Alice", &m);
964        assert!(result.is_some());
965        let r = result.expect("should match");
966        assert_eq!(r.get("s"), Some("alice"));
967        assert_eq!(r.get("p"), Some("name"));
968        assert_eq!(r.get("o"), Some("Alice"));
969    }
970
971    #[test]
972    fn test_triple_pattern_match_with_constant() {
973        let p = OptionalTriplePattern::new("?s", "name", "?o");
974        let m = SolutionMapping::new();
975        let result = p.match_triple("alice", "name", "Alice", &m);
976        assert!(result.is_some());
977        let fail = p.match_triple("alice", "age", "30", &m);
978        assert!(fail.is_none());
979    }
980
981    #[test]
982    fn test_triple_pattern_match_existing_binding() {
983        let p = OptionalTriplePattern::new("?s", "name", "?o");
984        let m = mapping(&[("s", "alice")]);
985        let result = p.match_triple("alice", "name", "Alice", &m);
986        assert!(result.is_some());
987        let fail = p.match_triple("bob", "name", "Bob", &m);
988        assert!(fail.is_none());
989    }
990
991    // ── OptionalClause builder tests ────────────────────────────────────────
992
993    #[test]
994    fn test_optional_clause_new() {
995        let patterns = vec![OptionalTriplePattern::new("?s", "email", "?e")];
996        let clause = OptionalClause::new(patterns);
997        assert_eq!(clause.patterns.len(), 1);
998        assert!(clause.filter.is_none());
999        assert!(clause.bind_exprs.is_empty());
1000        assert!(clause.nested.is_empty());
1001    }
1002
1003    #[test]
1004    fn test_optional_clause_with_filter() {
1005        let clause = OptionalClause::new(vec![]).with_filter(FilterExpr::Bound("x".into()));
1006        assert!(clause.filter.is_some());
1007    }
1008
1009    #[test]
1010    fn test_optional_clause_with_bind() {
1011        let bind = BindExpr {
1012            variable: "full".into(),
1013            expression: BindValue::Constant("test".into()),
1014        };
1015        let clause = OptionalClause::new(vec![]).with_bind(bind);
1016        assert_eq!(clause.bind_exprs.len(), 1);
1017    }
1018
1019    #[test]
1020    fn test_optional_clause_with_nested() {
1021        let inner = OptionalClause::new(vec![]);
1022        let clause = OptionalClause::new(vec![]).with_nested(inner);
1023        assert_eq!(clause.nested.len(), 1);
1024    }
1025
1026    // ── OptionalEvaluator: basic left outer join ────────────────────────────
1027
1028    #[test]
1029    fn test_basic_left_outer_join() {
1030        let eval = OptionalEvaluator::new();
1031        let left = vec![mapping(&[("s", "alice")]), mapping(&[("s", "charlie")])];
1032        let clause = OptionalClause::new(vec![OptionalTriplePattern::new("?s", "email", "?e")]);
1033        let d = data();
1034        let (result, stats) = eval
1035            .evaluate(&left, &clause, &d)
1036            .expect("evaluation should succeed");
1037
1038        // alice has email, charlie does not
1039        assert_eq!(result.len(), 2);
1040        // alice should have email binding
1041        let alice_sol = result.iter().find(|m| m.get("s") == Some("alice"));
1042        assert!(alice_sol.is_some());
1043        assert_eq!(
1044            alice_sol.expect("alice exists").get("e"),
1045            Some("alice@example.com")
1046        );
1047        // charlie should not have email binding
1048        let charlie_sol = result.iter().find(|m| m.get("s") == Some("charlie"));
1049        assert!(charlie_sol.is_some());
1050        assert!(charlie_sol.expect("charlie exists").get("e").is_none());
1051        assert_eq!(stats.joined_count, 1);
1052        assert_eq!(stats.unmatched_count, 1);
1053    }
1054
1055    #[test]
1056    fn test_optional_all_match() {
1057        let eval = OptionalEvaluator::new();
1058        let left = vec![mapping(&[("s", "alice")]), mapping(&[("s", "bob")])];
1059        let clause = OptionalClause::new(vec![OptionalTriplePattern::new("?s", "name", "?n")]);
1060        let d = data();
1061        let (result, stats) = eval
1062            .evaluate(&left, &clause, &d)
1063            .expect("evaluation should succeed");
1064        assert_eq!(result.len(), 2);
1065        assert_eq!(stats.joined_count, 2);
1066        assert_eq!(stats.unmatched_count, 0);
1067    }
1068
1069    #[test]
1070    fn test_optional_none_match() {
1071        let eval = OptionalEvaluator::new();
1072        let left = vec![mapping(&[("s", "alice")]), mapping(&[("s", "bob")])];
1073        let clause = OptionalClause::new(vec![OptionalTriplePattern::new("?s", "phone", "?p")]);
1074        let d = data();
1075        let (result, stats) = eval
1076            .evaluate(&left, &clause, &d)
1077            .expect("evaluation should succeed");
1078        // All should pass through unmatched
1079        assert_eq!(result.len(), 2);
1080        assert_eq!(stats.unmatched_count, 2);
1081        assert_eq!(stats.joined_count, 0);
1082    }
1083
1084    #[test]
1085    fn test_optional_empty_left() {
1086        let eval = OptionalEvaluator::new();
1087        let clause = OptionalClause::new(vec![OptionalTriplePattern::new("?s", "name", "?n")]);
1088        let d = data();
1089        let (result, _stats) = eval
1090            .evaluate(&[], &clause, &d)
1091            .expect("evaluation should succeed");
1092        assert!(result.is_empty());
1093    }
1094
1095    #[test]
1096    fn test_optional_empty_patterns() {
1097        let eval = OptionalEvaluator::new();
1098        let left = vec![mapping(&[("x", "1")])];
1099        let clause = OptionalClause::new(vec![]);
1100        let d = data();
1101        let (result, _stats) = eval
1102            .evaluate(&left, &clause, &d)
1103            .expect("evaluation should succeed");
1104        // Empty pattern matches anything; left solution is extended with empty.
1105        assert!(!result.is_empty());
1106    }
1107
1108    // ── OPTIONAL with FILTER ────────────────────────────────────────────────
1109
1110    #[test]
1111    fn test_optional_with_filter_passes() {
1112        let eval = OptionalEvaluator::new();
1113        let left = vec![mapping(&[("s", "alice")])];
1114        let clause = OptionalClause::new(vec![OptionalTriplePattern::new("?s", "age", "?a")])
1115            .with_filter(FilterExpr::Equals {
1116                var: "a".into(),
1117                value: "30".into(),
1118            });
1119        let d = data();
1120        let (result, stats) = eval
1121            .evaluate(&left, &clause, &d)
1122            .expect("evaluation should succeed");
1123        assert_eq!(result.len(), 1);
1124        assert_eq!(result[0].get("a"), Some("30"));
1125        assert_eq!(stats.filtered_count, 0);
1126    }
1127
1128    #[test]
1129    fn test_optional_with_filter_rejects() {
1130        let eval = OptionalEvaluator::new();
1131        let left = vec![mapping(&[("s", "alice")])];
1132        let clause = OptionalClause::new(vec![OptionalTriplePattern::new("?s", "age", "?a")])
1133            .with_filter(FilterExpr::Equals {
1134                var: "a".into(),
1135                value: "99".into(), // alice's age is 30, not 99
1136            });
1137        let d = data();
1138        let (result, stats) = eval
1139            .evaluate(&left, &clause, &d)
1140            .expect("evaluation should succeed");
1141        // Filter rejects the match, so alice gets pass-through without age binding.
1142        assert_eq!(result.len(), 1);
1143        assert!(result[0].get("a").is_none());
1144        assert_eq!(stats.filtered_count, 1);
1145        assert_eq!(stats.unmatched_count, 1);
1146    }
1147
1148    // ── OPTIONAL with BIND ──────────────────────────────────────────────────
1149
1150    #[test]
1151    fn test_optional_with_bind() {
1152        let eval = OptionalEvaluator::new();
1153        let left = vec![mapping(&[("s", "alice")])];
1154        let bind = BindExpr {
1155            variable: "label".into(),
1156            expression: BindValue::Concat(
1157                Box::new(BindValue::Variable("n".into())),
1158                Box::new(BindValue::Constant("!".into())),
1159            ),
1160        };
1161        let clause = OptionalClause::new(vec![OptionalTriplePattern::new("?s", "name", "?n")])
1162            .with_bind(bind);
1163        let d = data();
1164        let (result, _stats) = eval
1165            .evaluate(&left, &clause, &d)
1166            .expect("evaluation should succeed");
1167        assert_eq!(result.len(), 1);
1168        assert_eq!(result[0].get("label"), Some("Alice!"));
1169    }
1170
1171    #[test]
1172    fn test_optional_bind_conflict() {
1173        let eval = OptionalEvaluator::new();
1174        let left = vec![mapping(&[("s", "alice"), ("n", "existing")])];
1175        let bind = BindExpr {
1176            variable: "n".into(), // conflict: already bound
1177            expression: BindValue::Constant("other".into()),
1178        };
1179        let clause = OptionalClause::new(vec![OptionalTriplePattern::new("?s", "email", "?e")])
1180            .with_bind(bind);
1181        let d = data();
1182        let result = eval.evaluate(&left, &clause, &d);
1183        assert!(result.is_err());
1184        match result {
1185            Err(OptionalError::BindConflict { variable }) => {
1186                assert_eq!(variable, "n");
1187            }
1188            other => panic!("expected BindConflict, got {other:?}"),
1189        }
1190    }
1191
1192    // ── Nested OPTIONAL ─────────────────────────────────────────────────────
1193
1194    #[test]
1195    fn test_nested_optional() {
1196        let eval = OptionalEvaluator::new();
1197        let left = vec![mapping(&[("s", "alice")]), mapping(&[("s", "charlie")])];
1198        let inner = OptionalClause::new(vec![OptionalTriplePattern::new("?s", "email", "?e")]);
1199        let clause = OptionalClause::new(vec![OptionalTriplePattern::new("?s", "name", "?n")])
1200            .with_nested(inner);
1201        let d = data();
1202        let (result, stats) = eval
1203            .evaluate(&left, &clause, &d)
1204            .expect("evaluation should succeed");
1205        // alice: name=Alice, email=alice@example.com
1206        // charlie: name=Charlie, email=<unbound>
1207        assert_eq!(result.len(), 2);
1208        let alice = result
1209            .iter()
1210            .find(|m| m.get("s") == Some("alice"))
1211            .expect("alice exists");
1212        assert_eq!(alice.get("n"), Some("Alice"));
1213        assert_eq!(alice.get("e"), Some("alice@example.com"));
1214        let charlie = result
1215            .iter()
1216            .find(|m| m.get("s") == Some("charlie"))
1217            .expect("charlie exists");
1218        assert_eq!(charlie.get("n"), Some("Charlie"));
1219        assert!(charlie.get("e").is_none());
1220        assert!(stats.nested_evaluations > 0);
1221    }
1222
1223    #[test]
1224    fn test_deeply_nested_optional() {
1225        let eval = OptionalEvaluator::new();
1226        let left = vec![mapping(&[("s", "alice")])];
1227        let inner2 = OptionalClause::new(vec![OptionalTriplePattern::new("?s", "email", "?e")]);
1228        let inner1 = OptionalClause::new(vec![OptionalTriplePattern::new("?s", "age", "?a")])
1229            .with_nested(inner2);
1230        let clause = OptionalClause::new(vec![OptionalTriplePattern::new("?s", "name", "?n")])
1231            .with_nested(inner1);
1232        let d = data();
1233        let (result, _stats) = eval
1234            .evaluate(&left, &clause, &d)
1235            .expect("evaluation should succeed");
1236        assert_eq!(result.len(), 1);
1237        let sol = &result[0];
1238        assert_eq!(sol.get("n"), Some("Alice"));
1239        assert_eq!(sol.get("a"), Some("30"));
1240        assert_eq!(sol.get("e"), Some("alice@example.com"));
1241    }
1242
1243    // ── Nesting depth limit ─────────────────────────────────────────────────
1244
1245    #[test]
1246    fn test_nesting_depth_exceeded() {
1247        // max_nesting_depth=0 means no nested OPTIONAL is allowed.
1248        // The top-level evaluate starts at depth=0; the nested clause will
1249        // attempt depth=1 which exceeds 0.
1250        let config = OptionalConfig {
1251            max_nesting_depth: 0,
1252            ..OptionalConfig::default()
1253        };
1254        let eval = OptionalEvaluator::with_config(config);
1255        let left = vec![mapping(&[("s", "alice")])];
1256        let inner = OptionalClause::new(vec![OptionalTriplePattern::new("?s", "email", "?e")]);
1257        let clause = OptionalClause::new(vec![OptionalTriplePattern::new("?s", "name", "?n")])
1258            .with_nested(inner);
1259        let d = data();
1260        let result = eval.evaluate(&left, &clause, &d);
1261        assert!(result.is_err());
1262        match result {
1263            Err(OptionalError::NestingDepthExceeded { max_depth }) => {
1264                assert_eq!(max_depth, 0);
1265            }
1266            other => panic!("expected NestingDepthExceeded, got {other:?}"),
1267        }
1268    }
1269
1270    // ── Multi-variable optional binding ─────────────────────────────────────
1271
1272    #[test]
1273    fn test_multi_variable_optional() {
1274        let eval = OptionalEvaluator::new();
1275        let left = vec![mapping(&[("s", "alice")])];
1276        let clause = OptionalClause::new(vec![OptionalTriplePattern::new("?s", "?p", "?o")]);
1277        let d = data();
1278        let (result, _stats) = eval
1279            .evaluate(&left, &clause, &d)
1280            .expect("evaluation should succeed");
1281        // alice has 3 triples: name, age, email
1282        assert_eq!(result.len(), 3);
1283    }
1284
1285    // ── Hash-based join ─────────────────────────────────────────────────────
1286
1287    #[test]
1288    fn test_hash_join_threshold() {
1289        let config = OptionalConfig {
1290            use_hash_join: true,
1291            hash_join_threshold: 1, // force hash join even for small sets
1292            ..OptionalConfig::default()
1293        };
1294        let eval = OptionalEvaluator::with_config(config);
1295        let left = vec![mapping(&[("s", "alice")]), mapping(&[("s", "bob")])];
1296        let clause = OptionalClause::new(vec![OptionalTriplePattern::new("?s", "name", "?n")]);
1297        let d = data();
1298        let (result, _stats) = eval
1299            .evaluate(&left, &clause, &d)
1300            .expect("evaluation should succeed");
1301        assert_eq!(result.len(), 2);
1302    }
1303
1304    #[test]
1305    fn test_hash_join_disabled() {
1306        let config = OptionalConfig {
1307            use_hash_join: false,
1308            ..OptionalConfig::default()
1309        };
1310        let eval = OptionalEvaluator::with_config(config);
1311        let left = vec![mapping(&[("s", "alice")])];
1312        let clause = OptionalClause::new(vec![OptionalTriplePattern::new("?s", "name", "?n")]);
1313        let d = data();
1314        let (result, _stats) = eval
1315            .evaluate(&left, &clause, &d)
1316            .expect("evaluation should succeed");
1317        assert_eq!(result.len(), 1);
1318        assert_eq!(result[0].get("n"), Some("Alice"));
1319    }
1320
1321    // ── evaluate_sequence ──────────────────────────────────────────────────
1322
1323    #[test]
1324    fn test_evaluate_sequence() {
1325        let eval = OptionalEvaluator::new();
1326        let left = vec![mapping(&[("s", "alice")])];
1327        let clauses = vec![
1328            OptionalClause::new(vec![OptionalTriplePattern::new("?s", "name", "?n")]),
1329            OptionalClause::new(vec![OptionalTriplePattern::new("?s", "email", "?e")]),
1330        ];
1331        let d = data();
1332        let (result, stats_vec) = eval
1333            .evaluate_sequence(&left, &clauses, &d)
1334            .expect("evaluation should succeed");
1335        assert_eq!(result.len(), 1);
1336        assert_eq!(result[0].get("n"), Some("Alice"));
1337        assert_eq!(result[0].get("e"), Some("alice@example.com"));
1338        assert_eq!(stats_vec.len(), 2);
1339    }
1340
1341    #[test]
1342    fn test_evaluate_sequence_empty_clauses() {
1343        let eval = OptionalEvaluator::new();
1344        let left = vec![mapping(&[("x", "1")])];
1345        let d = data();
1346        let (result, stats_vec) = eval
1347            .evaluate_sequence(&left, &[], &d)
1348            .expect("evaluation should succeed");
1349        assert_eq!(result.len(), 1);
1350        assert!(stats_vec.is_empty());
1351    }
1352
1353    // ── Bound/unbound variable propagation ──────────────────────────────────
1354
1355    #[test]
1356    fn test_bound_unbound_propagation() {
1357        let eval = OptionalEvaluator::new();
1358        let left = vec![mapping(&[("s", "alice"), ("x", "extra")])];
1359        let clause = OptionalClause::new(vec![OptionalTriplePattern::new("?s", "name", "?n")]);
1360        let d = data();
1361        let (result, _stats) = eval
1362            .evaluate(&left, &clause, &d)
1363            .expect("evaluation should succeed");
1364        // Existing bindings should be preserved
1365        assert_eq!(result.len(), 1);
1366        assert_eq!(result[0].get("x"), Some("extra"));
1367        assert_eq!(result[0].get("n"), Some("Alice"));
1368    }
1369
1370    // ── Empty optional result handling ──────────────────────────────────────
1371
1372    #[test]
1373    fn test_empty_data() {
1374        let eval = OptionalEvaluator::new();
1375        let left = vec![mapping(&[("s", "alice")])];
1376        let clause = OptionalClause::new(vec![OptionalTriplePattern::new("?s", "name", "?n")]);
1377        let empty_data: Vec<(String, String, String)> = vec![];
1378        let (result, stats) = eval
1379            .evaluate(&left, &clause, &empty_data)
1380            .expect("evaluation should succeed");
1381        // No data means no match; left passes through.
1382        assert_eq!(result.len(), 1);
1383        assert!(result[0].get("n").is_none());
1384        assert_eq!(stats.unmatched_count, 1);
1385    }
1386
1387    // ── Config tests ────────────────────────────────────────────────────────
1388
1389    #[test]
1390    fn test_default_config() {
1391        let config = OptionalConfig::default();
1392        assert_eq!(config.max_nesting_depth, 16);
1393        assert!(config.use_hash_join);
1394        assert_eq!(config.hash_join_threshold, 64);
1395    }
1396
1397    // ── Error display ───────────────────────────────────────────────────────
1398
1399    #[test]
1400    fn test_error_display() {
1401        let err = OptionalError::InvalidVariable("foo".into());
1402        assert!(err.to_string().contains("foo"));
1403
1404        let err2 = OptionalError::NestingDepthExceeded { max_depth: 5 };
1405        assert!(err2.to_string().contains("5"));
1406
1407        let err3 = OptionalError::BindConflict {
1408            variable: "x".into(),
1409        };
1410        assert!(err3.to_string().contains("x"));
1411
1412        let err4 = OptionalError::EvaluationError("oops".into());
1413        assert!(err4.to_string().contains("oops"));
1414    }
1415
1416    // ── Compatible binding merge ─────────────────────────────────────────────
1417
1418    #[test]
1419    fn test_compatible_binding_merge_join_on_shared() {
1420        let eval = OptionalEvaluator::new();
1421        // Two left solutions with different "s" values
1422        let left = vec![
1423            mapping(&[("s", "alice"), ("g", "group1")]),
1424            mapping(&[("s", "bob"), ("g", "group2")]),
1425        ];
1426        let clause = OptionalClause::new(vec![OptionalTriplePattern::new("?s", "age", "?a")]);
1427        let d = data();
1428        let (result, _stats) = eval
1429            .evaluate(&left, &clause, &d)
1430            .expect("evaluation should succeed");
1431        assert_eq!(result.len(), 2);
1432        let alice_sol = result
1433            .iter()
1434            .find(|m| m.get("s") == Some("alice"))
1435            .expect("alice exists");
1436        assert_eq!(alice_sol.get("a"), Some("30"));
1437        assert_eq!(alice_sol.get("g"), Some("group1"));
1438        let bob_sol = result
1439            .iter()
1440            .find(|m| m.get("s") == Some("bob"))
1441            .expect("bob exists");
1442        assert_eq!(bob_sol.get("a"), Some("25"));
1443        assert_eq!(bob_sol.get("g"), Some("group2"));
1444    }
1445
1446    #[test]
1447    fn test_optional_multiple_matches_per_left() {
1448        let eval = OptionalEvaluator::new();
1449        // alice has name AND age AND email — matching ?s ?p ?o gives 3 results
1450        let left = vec![mapping(&[("s", "alice")])];
1451        let clause = OptionalClause::new(vec![OptionalTriplePattern::new("?s", "?p", "?val")]);
1452        let d = data();
1453        let (result, stats) = eval
1454            .evaluate(&left, &clause, &d)
1455            .expect("evaluation should succeed");
1456        assert_eq!(result.len(), 3);
1457        assert_eq!(stats.joined_count, 1);
1458    }
1459
1460    // ── Filter with BOUND check ─────────────────────────────────────────────
1461
1462    #[test]
1463    fn test_optional_filter_bound_check() {
1464        let eval = OptionalEvaluator::new();
1465        let left = vec![mapping(&[("s", "alice")])];
1466        let clause = OptionalClause::new(vec![OptionalTriplePattern::new("?s", "name", "?n")])
1467            .with_filter(FilterExpr::Bound("n".into()));
1468        let d = data();
1469        let (result, _stats) = eval
1470            .evaluate(&left, &clause, &d)
1471            .expect("evaluation should succeed");
1472        assert_eq!(result.len(), 1);
1473        assert_eq!(result[0].get("n"), Some("Alice"));
1474    }
1475
1476    // ── Statistics ──────────────────────────────────────────────────────────
1477
1478    #[test]
1479    fn test_stats_default() {
1480        let stats = OptionalStats::default();
1481        assert_eq!(stats.left_solutions, 0);
1482        assert_eq!(stats.right_solutions, 0);
1483        assert_eq!(stats.joined_count, 0);
1484        assert_eq!(stats.unmatched_count, 0);
1485        assert_eq!(stats.nested_evaluations, 0);
1486        assert_eq!(stats.filtered_count, 0);
1487    }
1488
1489    #[test]
1490    fn test_evaluator_default() {
1491        let eval = OptionalEvaluator::default();
1492        let left = vec![mapping(&[("s", "alice")])];
1493        let clause = OptionalClause::new(vec![]);
1494        let d = data();
1495        let (result, _) = eval
1496            .evaluate(&left, &clause, &d)
1497            .expect("evaluation should succeed");
1498        assert!(!result.is_empty());
1499    }
1500}
oxirs_arq/optional_evaluator.rs

oxirs_arq/
optional_evaluator.rs
