oxirs_arq/
exists_evaluator.rs

1//! SPARQL EXISTS and NOT EXISTS evaluation.
2//!
3//! This module implements the EXISTS and NOT EXISTS graph pattern evaluation
4//! as defined in SPARQL 1.1 specification (section 18.2.1).
5//!
6//! # Overview
7//!
8//! EXISTS checks whether a graph pattern matches at least one solution given
9//! the current input bindings. NOT EXISTS is its negation.
10//!
11//! The evaluator supports:
12//! - Triple patterns with variable bindings
13//! - AND (join) patterns
14//! - OPTIONAL (left outer join) patterns
15//! - FILTER patterns
16//! - UNION patterns
17
18use std::collections::HashMap;
19
20/// A single RDF triple fact in the dataset.
21#[derive(Debug, Clone, PartialEq, Eq, Hash)]
22pub struct TripleFact {
23    pub subject: String,
24    pub predicate: String,
25    pub object: String,
26}
27
28impl TripleFact {
29    pub fn new(
30        subject: impl Into<String>,
31        predicate: impl Into<String>,
32        object: impl Into<String>,
33    ) -> Self {
34        Self {
35            subject: subject.into(),
36            predicate: predicate.into(),
37            object: object.into(),
38        }
39    }
40}
41
42/// A SPARQL graph pattern.
43#[derive(Debug, Clone)]
44pub enum GraphPattern {
45    /// A single triple pattern (may contain variables starting with `?`)
46    Triple(TripleFact),
47    /// Conjunction of multiple patterns
48    And(Vec<GraphPattern>),
49    /// Optional (left outer join) pattern
50    Optional(Box<GraphPattern>),
51    /// Filter with a condition expression (simplified: just variable=value)
52    Filter {
53        pattern: Box<GraphPattern>,
54        condition: String,
55    },
56    /// Union of two patterns
57    Union(Box<GraphPattern>, Box<GraphPattern>),
58}
59
60/// A solution mapping: variable name (without `?`) → bound value.
61pub type SolutionMapping = HashMap<String, String>;
62
63/// Evaluates SPARQL EXISTS and NOT EXISTS graph patterns.
64#[derive(Debug, Default)]
65pub struct ExistsEvaluator;
66
67impl ExistsEvaluator {
68    /// Create a new `ExistsEvaluator`.
69    pub fn new() -> Self {
70        Self
71    }
72
73    /// Returns `true` if the pattern has at least one solution given `input` bindings.
74    pub fn evaluate_exists(
75        &self,
76        facts: &[TripleFact],
77        pattern: &GraphPattern,
78        input: &SolutionMapping,
79    ) -> bool {
80        let solutions = self.inner_match(facts, pattern, input.clone());
81        !solutions.is_empty()
82    }
83
84    /// Returns `true` if the pattern has NO solutions given `input` bindings.
85    pub fn evaluate_not_exists(
86        &self,
87        facts: &[TripleFact],
88        pattern: &GraphPattern,
89        input: &SolutionMapping,
90    ) -> bool {
91        !self.evaluate_exists(facts, pattern, input)
92    }
93
94    /// Recursively match a pattern against facts, extending `bindings`.
95    ///
96    /// Returns all possible solution mappings that satisfy the pattern.
97    pub fn inner_match(
98        &self,
99        facts: &[TripleFact],
100        pattern: &GraphPattern,
101        bindings: SolutionMapping,
102    ) -> Vec<SolutionMapping> {
103        match pattern {
104            GraphPattern::Triple(triple) => self.match_triple(facts, triple, bindings),
105
106            GraphPattern::And(patterns) => {
107                // Start with the initial bindings as a single solution, then
108                // progressively join each pattern.
109                let mut current_solutions = vec![bindings];
110                for sub_pattern in patterns {
111                    let mut next_solutions = Vec::new();
112                    for sol in current_solutions {
113                        let results = self.inner_match(facts, sub_pattern, sol);
114                        next_solutions.extend(results);
115                    }
116                    current_solutions = next_solutions;
117                }
118                current_solutions
119            }
120
121            GraphPattern::Optional(sub_pattern) => {
122                // Left outer join: if sub_pattern has solutions, return them;
123                // otherwise return the original bindings unchanged.
124                let results = self.inner_match(facts, sub_pattern, bindings.clone());
125                if results.is_empty() {
126                    vec![bindings]
127                } else {
128                    results
129                }
130            }
131
132            GraphPattern::Filter {
133                pattern: sub_pattern,
134                condition,
135            } => {
136                let solutions = self.inner_match(facts, sub_pattern, bindings);
137                solutions
138                    .into_iter()
139                    .filter(|sol| self.evaluate_filter_condition(sol, condition))
140                    .collect()
141            }
142
143            GraphPattern::Union(left, right) => {
144                let mut left_solutions = self.inner_match(facts, left, bindings.clone());
145                let right_solutions = self.inner_match(facts, right, bindings);
146                left_solutions.extend(right_solutions);
147                left_solutions
148            }
149        }
150    }
151
152    /// Match a single triple pattern against all facts.
153    fn match_triple(
154        &self,
155        facts: &[TripleFact],
156        triple: &TripleFact,
157        bindings: SolutionMapping,
158    ) -> Vec<SolutionMapping> {
159        let mut results = Vec::new();
160        for fact in facts {
161            if let Some(new_bindings) = self.try_bind_triple(triple, fact, bindings.clone()) {
162                results.push(new_bindings);
163            }
164        }
165        results
166    }
167
168    /// Try to bind a triple pattern to a concrete fact, extending `bindings`.
169    ///
170    /// Returns `None` if the triple pattern conflicts with the fact or bindings.
171    fn try_bind_triple(
172        &self,
173        pattern: &TripleFact,
174        fact: &TripleFact,
175        mut bindings: SolutionMapping,
176    ) -> Option<SolutionMapping> {
177        // Attempt to match each component
178        bindings = self.try_bind_term(&pattern.subject, &fact.subject, bindings)?;
179        bindings = self.try_bind_term(&pattern.predicate, &fact.predicate, bindings)?;
180        bindings = self.try_bind_term(&pattern.object, &fact.object, bindings)?;
181        Some(bindings)
182    }
183
184    /// Try to bind a pattern term (variable or constant) to a concrete value.
185    fn try_bind_term(
186        &self,
187        term: &str,
188        value: &str,
189        mut bindings: SolutionMapping,
190    ) -> Option<SolutionMapping> {
191        if Self::is_variable(term) {
192            let var_name = term.trim_start_matches('?').to_string();
193            if let Some(existing) = bindings.get(&var_name) {
194                if existing != value {
195                    return None; // Conflicting binding
196                }
197                // Already bound to same value — OK
198            } else {
199                bindings.insert(var_name, value.to_string());
200            }
201            Some(bindings)
202        } else {
203            // Constant: must match exactly
204            if term == value {
205                Some(bindings)
206            } else {
207                None
208            }
209        }
210    }
211
212    /// Evaluate a simplified filter condition string.
213    ///
214    /// Supports formats:
215    /// - `?var=value` — variable equals literal
216    /// - `?var!=value` — variable not equals literal
217    fn evaluate_filter_condition(&self, bindings: &SolutionMapping, condition: &str) -> bool {
218        if let Some(pos) = condition.find("!=") {
219            let lhs = condition[..pos].trim();
220            let rhs = condition[pos + 2..].trim();
221            if Self::is_variable(lhs) {
222                let var_name = lhs.trim_start_matches('?');
223                if let Some(val) = bindings.get(var_name) {
224                    return val != rhs;
225                }
226                // Unbound variable: condition is false (conservative)
227                return false;
228            }
229        } else if let Some(pos) = condition.find('=') {
230            let lhs = condition[..pos].trim();
231            let rhs = condition[pos + 1..].trim();
232            if Self::is_variable(lhs) {
233                let var_name = lhs.trim_start_matches('?');
234                if let Some(val) = bindings.get(var_name) {
235                    return val == rhs;
236                }
237                return false;
238            }
239        }
240        // Unrecognised condition: pass through
241        true
242    }
243
244    /// Returns `true` if the term is a SPARQL variable (starts with `?`).
245    pub fn is_variable(term: &str) -> bool {
246        term.starts_with('?')
247    }
248
249    /// Returns `true` if two solution mappings have no conflicting bindings.
250    ///
251    /// Two mappings are *compatible* if for every variable bound in both, they
252    /// agree on the same value.
253    pub fn compatible(m1: &SolutionMapping, m2: &SolutionMapping) -> bool {
254        for (var, val1) in m1 {
255            if let Some(val2) = m2.get(var) {
256                if val1 != val2 {
257                    return false;
258                }
259            }
260        }
261        true
262    }
263
264    /// Merge two compatible solution mappings into one.
265    ///
266    /// Bindings from `m2` are added to `m1`; `m1` values win on conflicts.
267    pub fn merge(mut m1: SolutionMapping, m2: SolutionMapping) -> SolutionMapping {
268        for (k, v) in m2 {
269            m1.entry(k).or_insert(v);
270        }
271        m1
272    }
273}
274
275// ─── Tests ───────────────────────────────────────────────────────────────────
276
277#[cfg(test)]
278mod tests {
279    use super::*;
280
281    fn evaluator() -> ExistsEvaluator {
282        ExistsEvaluator::new()
283    }
284
285    fn empty_input() -> SolutionMapping {
286        SolutionMapping::new()
287    }
288
289    fn facts_abc() -> Vec<TripleFact> {
290        vec![
291            TripleFact::new(":Alice", "knows", ":Bob"),
292            TripleFact::new(":Bob", "knows", ":Carol"),
293            TripleFact::new(":Alice", "age", "30"),
294            TripleFact::new(":Bob", "age", "25"),
295        ]
296    }
297
298    // ── is_variable ──────────────────────────────────────────────────────────
299
300    #[test]
301    fn test_is_variable_true() {
302        assert!(ExistsEvaluator::is_variable("?x"));
303    }
304
305    #[test]
306    fn test_is_variable_false_constant() {
307        assert!(!ExistsEvaluator::is_variable(":Alice"));
308    }
309
310    #[test]
311    fn test_is_variable_empty_string() {
312        assert!(!ExistsEvaluator::is_variable(""));
313    }
314
315    #[test]
316    fn test_is_variable_question_mark_only() {
317        assert!(ExistsEvaluator::is_variable("?"));
318    }
319
320    // ── compatible ───────────────────────────────────────────────────────────
321
322    #[test]
323    fn test_compatible_empty_maps() {
324        let m1 = SolutionMapping::new();
325        let m2 = SolutionMapping::new();
326        assert!(ExistsEvaluator::compatible(&m1, &m2));
327    }
328
329    #[test]
330    fn test_compatible_same_bindings() {
331        let m1: SolutionMapping = [("x".into(), "1".into())].into();
332        let m2: SolutionMapping = [("x".into(), "1".into())].into();
333        assert!(ExistsEvaluator::compatible(&m1, &m2));
334    }
335
336    #[test]
337    fn test_compatible_different_vars() {
338        let m1: SolutionMapping = [("x".into(), "1".into())].into();
339        let m2: SolutionMapping = [("y".into(), "2".into())].into();
340        assert!(ExistsEvaluator::compatible(&m1, &m2));
341    }
342
343    #[test]
344    fn test_compatible_conflict() {
345        let m1: SolutionMapping = [("x".into(), "1".into())].into();
346        let m2: SolutionMapping = [("x".into(), "2".into())].into();
347        assert!(!ExistsEvaluator::compatible(&m1, &m2));
348    }
349
350    // ── merge ─────────────────────────────────────────────────────────────────
351
352    #[test]
353    fn test_merge_disjoint() {
354        let m1: SolutionMapping = [("x".into(), "1".into())].into();
355        let m2: SolutionMapping = [("y".into(), "2".into())].into();
356        let merged = ExistsEvaluator::merge(m1, m2);
357        assert_eq!(merged.get("x").map(|s| s.as_str()), Some("1"));
358        assert_eq!(merged.get("y").map(|s| s.as_str()), Some("2"));
359    }
360
361    #[test]
362    fn test_merge_m1_wins_on_overlap() {
363        let m1: SolutionMapping = [("x".into(), "1".into())].into();
364        let m2: SolutionMapping = [("x".into(), "99".into())].into();
365        let merged = ExistsEvaluator::merge(m1, m2);
366        assert_eq!(merged.get("x").map(|s| s.as_str()), Some("1"));
367    }
368
369    // ── EXISTS basic ──────────────────────────────────────────────────────────
370
371    #[test]
372    fn test_exists_simple_triple_found() {
373        let e = evaluator();
374        let facts = facts_abc();
375        let pattern = GraphPattern::Triple(TripleFact::new(":Alice", "knows", ":Bob"));
376        assert!(e.evaluate_exists(&facts, &pattern, &empty_input()));
377    }
378
379    #[test]
380    fn test_exists_simple_triple_not_found() {
381        let e = evaluator();
382        let facts = facts_abc();
383        let pattern = GraphPattern::Triple(TripleFact::new(":Alice", "knows", ":Dave"));
384        assert!(!e.evaluate_exists(&facts, &pattern, &empty_input()));
385    }
386
387    #[test]
388    fn test_exists_variable_subject() {
389        let e = evaluator();
390        let facts = facts_abc();
391        let pattern = GraphPattern::Triple(TripleFact::new("?x", "knows", ":Bob"));
392        assert!(e.evaluate_exists(&facts, &pattern, &empty_input()));
393    }
394
395    #[test]
396    fn test_exists_all_variables() {
397        let e = evaluator();
398        let facts = facts_abc();
399        let pattern = GraphPattern::Triple(TripleFact::new("?s", "?p", "?o"));
400        assert!(e.evaluate_exists(&facts, &pattern, &empty_input()));
401    }
402
403    #[test]
404    fn test_exists_empty_graph() {
405        let e = evaluator();
406        let facts: Vec<TripleFact> = vec![];
407        let pattern = GraphPattern::Triple(TripleFact::new("?s", "?p", "?o"));
408        assert!(!e.evaluate_exists(&facts, &pattern, &empty_input()));
409    }
410
411    #[test]
412    fn test_exists_with_pre_bound_input_matching() {
413        let e = evaluator();
414        let facts = facts_abc();
415        let pattern = GraphPattern::Triple(TripleFact::new("?x", "knows", "?y"));
416        let mut input = SolutionMapping::new();
417        input.insert("x".into(), ":Alice".into());
418        assert!(e.evaluate_exists(&facts, &pattern, &input));
419    }
420
421    #[test]
422    fn test_exists_with_pre_bound_input_not_matching() {
423        let e = evaluator();
424        let facts = facts_abc();
425        let pattern = GraphPattern::Triple(TripleFact::new("?x", "knows", "?y"));
426        // Dave doesn't know anyone
427        let mut input = SolutionMapping::new();
428        input.insert("x".into(), ":Dave".into());
429        assert!(!e.evaluate_exists(&facts, &pattern, &input));
430    }
431
432    #[test]
433    fn test_exists_scoped_binding_not_leaked() {
434        // EXISTS evaluation must not affect the outer solution mapping.
435        let e = evaluator();
436        let facts = facts_abc();
437        let pattern = GraphPattern::Triple(TripleFact::new("?x", "knows", ":Bob"));
438        let input = empty_input();
439        e.evaluate_exists(&facts, &pattern, &input);
440        // Original input unchanged
441        assert!(input.is_empty());
442    }
443
444    // ── NOT EXISTS basic ──────────────────────────────────────────────────────
445
446    #[test]
447    fn test_not_exists_simple_triple_absent() {
448        let e = evaluator();
449        let facts = facts_abc();
450        let pattern = GraphPattern::Triple(TripleFact::new(":Nobody", "knows", ":Bob"));
451        assert!(e.evaluate_not_exists(&facts, &pattern, &empty_input()));
452    }
453
454    #[test]
455    fn test_not_exists_simple_triple_present() {
456        let e = evaluator();
457        let facts = facts_abc();
458        let pattern = GraphPattern::Triple(TripleFact::new(":Alice", "knows", ":Bob"));
459        assert!(!e.evaluate_not_exists(&facts, &pattern, &empty_input()));
460    }
461
462    #[test]
463    fn test_not_exists_all_variables_nonempty_graph() {
464        let e = evaluator();
465        let facts = facts_abc();
466        let pattern = GraphPattern::Triple(TripleFact::new("?s", "?p", "?o"));
467        assert!(!e.evaluate_not_exists(&facts, &pattern, &empty_input()));
468    }
469
470    #[test]
471    fn test_not_exists_empty_graph() {
472        let e = evaluator();
473        let facts: Vec<TripleFact> = vec![];
474        let pattern = GraphPattern::Triple(TripleFact::new("?s", "?p", "?o"));
475        assert!(e.evaluate_not_exists(&facts, &pattern, &empty_input()));
476    }
477
478    // ── AND patterns ──────────────────────────────────────────────────────────
479
480    #[test]
481    fn test_and_both_match() {
482        let e = evaluator();
483        let facts = facts_abc();
484        let pattern = GraphPattern::And(vec![
485            GraphPattern::Triple(TripleFact::new("?x", "knows", ":Bob")),
486            GraphPattern::Triple(TripleFact::new("?x", "age", "?a")),
487        ]);
488        assert!(e.evaluate_exists(&facts, &pattern, &empty_input()));
489    }
490
491    #[test]
492    fn test_and_second_fails() {
493        let e = evaluator();
494        let facts = facts_abc();
495        let pattern = GraphPattern::And(vec![
496            GraphPattern::Triple(TripleFact::new("?x", "knows", ":Bob")),
497            GraphPattern::Triple(TripleFact::new("?x", "flies", "?a")),
498        ]);
499        assert!(!e.evaluate_exists(&facts, &pattern, &empty_input()));
500    }
501
502    #[test]
503    fn test_and_variable_join() {
504        let e = evaluator();
505        let facts = facts_abc();
506        // Find ?x that knows ?y, and ?y also knows someone
507        let pattern = GraphPattern::And(vec![
508            GraphPattern::Triple(TripleFact::new("?x", "knows", "?y")),
509            GraphPattern::Triple(TripleFact::new("?y", "knows", "?z")),
510        ]);
511        assert!(e.evaluate_exists(&facts, &pattern, &empty_input()));
512    }
513
514    #[test]
515    fn test_and_empty_pattern_list() {
516        let e = evaluator();
517        let facts = facts_abc();
518        let pattern = GraphPattern::And(vec![]);
519        // Empty AND → trivially satisfied (vacuous join)
520        assert!(e.evaluate_exists(&facts, &pattern, &empty_input()));
521    }
522
523    // ── OPTIONAL patterns ─────────────────────────────────────────────────────
524
525    #[test]
526    fn test_optional_pattern_present() {
527        let e = evaluator();
528        let facts = facts_abc();
529        let pattern = GraphPattern::Optional(Box::new(GraphPattern::Triple(TripleFact::new(
530            ":Alice", "knows", ":Bob",
531        ))));
532        assert!(e.evaluate_exists(&facts, &pattern, &empty_input()));
533    }
534
535    #[test]
536    fn test_optional_pattern_absent_still_exists() {
537        let e = evaluator();
538        let facts = facts_abc();
539        // Optional triple that doesn't exist: still returns the empty input binding
540        let pattern = GraphPattern::Optional(Box::new(GraphPattern::Triple(TripleFact::new(
541            ":Nobody", "knows", ":Bob",
542        ))));
543        // Should return 1 solution (the empty input)
544        let solutions = e.inner_match(&facts, &pattern, empty_input());
545        assert_eq!(solutions.len(), 1);
546        assert!(solutions[0].is_empty());
547    }
548
549    #[test]
550    fn test_optional_extends_bindings_when_found() {
551        let e = evaluator();
552        let facts = facts_abc();
553        let pattern = GraphPattern::Optional(Box::new(GraphPattern::Triple(TripleFact::new(
554            "?s", "age", "?a",
555        ))));
556        let solutions = e.inner_match(&facts, &pattern, empty_input());
557        // Each fact with predicate "age" should produce a binding
558        assert!(solutions.iter().any(|sol| sol.contains_key("a")));
559    }
560
561    // ── UNION patterns ────────────────────────────────────────────────────────
562
563    #[test]
564    fn test_union_left_matches() {
565        let e = evaluator();
566        let facts = facts_abc();
567        let pattern = GraphPattern::Union(
568            Box::new(GraphPattern::Triple(TripleFact::new(
569                ":Alice", "knows", ":Bob",
570            ))),
571            Box::new(GraphPattern::Triple(TripleFact::new(
572                ":Nobody", "knows", ":Bob",
573            ))),
574        );
575        assert!(e.evaluate_exists(&facts, &pattern, &empty_input()));
576    }
577
578    #[test]
579    fn test_union_right_matches() {
580        let e = evaluator();
581        let facts = facts_abc();
582        let pattern = GraphPattern::Union(
583            Box::new(GraphPattern::Triple(TripleFact::new(
584                ":Nobody", "knows", ":Bob",
585            ))),
586            Box::new(GraphPattern::Triple(TripleFact::new(
587                ":Alice", "knows", ":Bob",
588            ))),
589        );
590        assert!(e.evaluate_exists(&facts, &pattern, &empty_input()));
591    }
592
593    #[test]
594    fn test_union_neither_matches() {
595        let e = evaluator();
596        let facts = facts_abc();
597        let pattern = GraphPattern::Union(
598            Box::new(GraphPattern::Triple(TripleFact::new(
599                ":Nobody", "knows", ":Bob",
600            ))),
601            Box::new(GraphPattern::Triple(TripleFact::new(
602                ":Noone", "knows", ":Bob",
603            ))),
604        );
605        assert!(!e.evaluate_exists(&facts, &pattern, &empty_input()));
606    }
607
608    #[test]
609    fn test_union_both_match_returns_all_solutions() {
610        let e = evaluator();
611        let facts = facts_abc();
612        // Both branches match: should have 2 solutions
613        let pattern = GraphPattern::Union(
614            Box::new(GraphPattern::Triple(TripleFact::new(
615                ":Alice", "knows", ":Bob",
616            ))),
617            Box::new(GraphPattern::Triple(TripleFact::new(
618                ":Bob", "knows", ":Carol",
619            ))),
620        );
621        let solutions = e.inner_match(&facts, &pattern, empty_input());
622        assert_eq!(solutions.len(), 2);
623    }
624
625    // ── FILTER patterns ───────────────────────────────────────────────────────
626
627    #[test]
628    fn test_filter_passing() {
629        let e = evaluator();
630        let facts = facts_abc();
631        let pattern = GraphPattern::Filter {
632            pattern: Box::new(GraphPattern::Triple(TripleFact::new("?x", "age", "?a"))),
633            condition: "?a=30".to_string(),
634        };
635        let solutions = e.inner_match(&facts, &pattern, empty_input());
636        assert_eq!(solutions.len(), 1);
637        assert_eq!(solutions[0].get("x").map(|s| s.as_str()), Some(":Alice"));
638    }
639
640    #[test]
641    fn test_filter_not_equals() {
642        let e = evaluator();
643        let facts = facts_abc();
644        let pattern = GraphPattern::Filter {
645            pattern: Box::new(GraphPattern::Triple(TripleFact::new("?x", "age", "?a"))),
646            condition: "?a!=30".to_string(),
647        };
648        let solutions = e.inner_match(&facts, &pattern, empty_input());
649        assert_eq!(solutions.len(), 1);
650        assert_eq!(solutions[0].get("x").map(|s| s.as_str()), Some(":Bob"));
651    }
652
653    #[test]
654    fn test_filter_removes_all() {
655        let e = evaluator();
656        let facts = facts_abc();
657        let pattern = GraphPattern::Filter {
658            pattern: Box::new(GraphPattern::Triple(TripleFact::new("?x", "age", "?a"))),
659            condition: "?a=999".to_string(),
660        };
661        let solutions = e.inner_match(&facts, &pattern, empty_input());
662        assert!(solutions.is_empty());
663    }
664
665    // ── inner_match detailed ──────────────────────────────────────────────────
666
667    #[test]
668    fn test_inner_match_returns_multiple_solutions() {
669        let e = evaluator();
670        let facts = facts_abc();
671        // ?x knows ?y: should find 2 solutions
672        let pattern = GraphPattern::Triple(TripleFact::new("?x", "knows", "?y"));
673        let solutions = e.inner_match(&facts, &pattern, empty_input());
674        assert_eq!(solutions.len(), 2);
675    }
676
677    #[test]
678    fn test_inner_match_pre_bound_narrows_results() {
679        let e = evaluator();
680        let facts = facts_abc();
681        let pattern = GraphPattern::Triple(TripleFact::new("?x", "knows", "?y"));
682        let mut input = SolutionMapping::new();
683        input.insert("x".into(), ":Alice".into());
684        let solutions = e.inner_match(&facts, &pattern, input);
685        assert_eq!(solutions.len(), 1);
686        assert_eq!(solutions[0].get("y").map(|s| s.as_str()), Some(":Bob"));
687    }
688
689    #[test]
690    fn test_inner_match_constant_predicate() {
691        let e = evaluator();
692        let facts = facts_abc();
693        let pattern = GraphPattern::Triple(TripleFact::new("?s", "age", "?o"));
694        let solutions = e.inner_match(&facts, &pattern, empty_input());
695        assert_eq!(solutions.len(), 2);
696    }
697
698    #[test]
699    fn test_inner_match_no_matching_facts() {
700        let e = evaluator();
701        let facts = facts_abc();
702        let pattern = GraphPattern::Triple(TripleFact::new("?s", "flies", "?o"));
703        let solutions = e.inner_match(&facts, &pattern, empty_input());
704        assert!(solutions.is_empty());
705    }
706
707    // ── scoped bindings (EXISTS must not leak) ─────────────────────────────────
708
709    #[test]
710    fn test_exists_bindings_scoped_does_not_modify_input() {
711        let e = evaluator();
712        let facts = facts_abc();
713        let pattern = GraphPattern::Triple(TripleFact::new("?newvar", "knows", ":Bob"));
714        let input = SolutionMapping::new();
715        let result = e.evaluate_exists(&facts, &pattern, &input);
716        assert!(result);
717        // The original `input` is unchanged (Rust ownership ensures this)
718        assert!(input.is_empty());
719    }
720
721    // ── complex nested patterns ───────────────────────────────────────────────
722
723    #[test]
724    fn test_and_within_union() {
725        let e = evaluator();
726        let facts = facts_abc();
727        let knows_bob = GraphPattern::Triple(TripleFact::new("?x", "knows", ":Bob"));
728        let bob_old = GraphPattern::And(vec![
729            GraphPattern::Triple(TripleFact::new("?x", "knows", ":Carol")),
730            GraphPattern::Triple(TripleFact::new("?x", "age", "?a")),
731        ]);
732        let pattern = GraphPattern::Union(Box::new(knows_bob), Box::new(bob_old));
733        assert!(e.evaluate_exists(&facts, &pattern, &empty_input()));
734    }
735
736    #[test]
737    fn test_optional_within_and() {
738        let e = evaluator();
739        let facts = facts_abc();
740        let pattern = GraphPattern::And(vec![
741            GraphPattern::Triple(TripleFact::new("?x", "knows", "?y")),
742            GraphPattern::Optional(Box::new(GraphPattern::Triple(TripleFact::new(
743                "?x", "email", "?e",
744            )))),
745        ]);
746        // Should return solutions (email is optional, won't block)
747        let solutions = e.inner_match(&facts, &pattern, empty_input());
748        assert!(!solutions.is_empty());
749    }
750
751    #[test]
752    fn test_filter_within_and() {
753        let e = evaluator();
754        let facts = facts_abc();
755        let pattern = GraphPattern::And(vec![
756            GraphPattern::Triple(TripleFact::new("?x", "knows", "?y")),
757            GraphPattern::Filter {
758                pattern: Box::new(GraphPattern::Triple(TripleFact::new("?x", "age", "?a"))),
759                condition: "?a=30".to_string(),
760            },
761        ]);
762        let solutions = e.inner_match(&facts, &pattern, empty_input());
763        assert_eq!(solutions.len(), 1);
764        assert_eq!(solutions[0].get("x").map(|s| s.as_str()), Some(":Alice"));
765    }
766
767    #[test]
768    fn test_not_exists_with_bound_variable() {
769        let e = evaluator();
770        let facts = facts_abc();
771        let pattern = GraphPattern::Triple(TripleFact::new("?x", "flies", "?z"));
772        let mut input = SolutionMapping::new();
773        input.insert("x".into(), ":Alice".into());
774        assert!(e.evaluate_not_exists(&facts, &pattern, &input));
775    }
776
777    #[test]
778    fn test_triple_fact_new_constructor() {
779        let t = TripleFact::new(":s", ":p", ":o");
780        assert_eq!(t.subject, ":s");
781        assert_eq!(t.predicate, ":p");
782        assert_eq!(t.object, ":o");
783    }
784
785    #[test]
786    fn test_merge_empty_maps() {
787        let m1 = SolutionMapping::new();
788        let m2 = SolutionMapping::new();
789        let merged = ExistsEvaluator::merge(m1, m2);
790        assert!(merged.is_empty());
791    }
792
793    #[test]
794    fn test_exists_single_fact_dataset_match() {
795        let e = evaluator();
796        let facts = vec![TripleFact::new("ex:Alice", "foaf:knows", "ex:Bob")];
797        let pattern = GraphPattern::Triple(TripleFact::new("?s", "foaf:knows", "?o"));
798        assert!(e.evaluate_exists(&facts, &pattern, &empty_input()));
799    }
800
801    #[test]
802    fn test_not_exists_on_empty_dataset() {
803        let e = evaluator();
804        let pattern =
805            GraphPattern::And(vec![GraphPattern::Triple(TripleFact::new("?x", "p", "?y"))]);
806        assert!(e.evaluate_not_exists(&[], &pattern, &empty_input()));
807    }
808}
oxirs_arq/exists_evaluator.rs

oxirs_arq/
exists_evaluator.rs
