oxirs_core/model/
property_path_evaluator.rs

1//! SPARQL 1.1 Property Path Evaluation
2//!
3//! This module implements the property path evaluation semantics as defined in
4//! the SPARQL 1.1 specification (<https://www.w3.org/TR/sparql11-query/#propertypaths>).
5
6use std::collections::{HashMap, HashSet, VecDeque};
7use std::fmt;
8
9/// A SPARQL 1.1 property path expression.
10#[derive(Debug, Clone, PartialEq)]
11pub enum PropertyPath {
12    /// A single IRI predicate: `<iri>`
13    Iri(String),
14    /// Sequence path: `path1/path2`
15    Sequence(Box<PropertyPath>, Box<PropertyPath>),
16    /// Alternative path: `path1|path2`
17    Alternative(Box<PropertyPath>, Box<PropertyPath>),
18    /// Zero-or-more: `path*`
19    ZeroOrMore(Box<PropertyPath>),
20    /// One-or-more: `path+`
21    OneOrMore(Box<PropertyPath>),
22    /// Zero-or-one: `path?`
23    ZeroOrOne(Box<PropertyPath>),
24    /// Inverse path: `^path`
25    Inverse(Box<PropertyPath>),
26    /// Negated property set: `!(iri1|iri2|...)`
27    NegatedSet(Vec<String>),
28}
29
30/// Error type for property path parsing.
31#[derive(Debug, Clone, PartialEq)]
32pub enum PathError {
33    /// Unknown or unsupported syntax encountered.
34    UnknownSyntax(String),
35    /// An empty path was provided.
36    EmptyPath,
37}
38
39impl fmt::Display for PathError {
40    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
41        match self {
42            PathError::UnknownSyntax(s) => write!(f, "Unknown path syntax: {s}"),
43            PathError::EmptyPath => write!(f, "Empty path expression"),
44        }
45    }
46}
47
48impl std::error::Error for PathError {}
49
50/// An in-memory RDF graph for property path evaluation.
51///
52/// Stores triples as `subject -> [(predicate, object)]` for efficient lookup.
53#[derive(Debug, Default, Clone)]
54pub struct PathGraph {
55    /// Forward index: subject -> list of (predicate, object)
56    forward: HashMap<String, Vec<(String, String)>>,
57    /// Reverse index: object -> list of (predicate, subject)
58    reverse: HashMap<String, Vec<(String, String)>>,
59}
60
61impl PathGraph {
62    /// Create a new empty graph.
63    pub fn new() -> Self {
64        Self::default()
65    }
66
67    /// Add a triple to the graph.
68    pub fn add_triple(&mut self, subject: &str, predicate: &str, object: &str) {
69        self.forward
70            .entry(subject.to_string())
71            .or_default()
72            .push((predicate.to_string(), object.to_string()));
73        self.reverse
74            .entry(object.to_string())
75            .or_default()
76            .push((predicate.to_string(), subject.to_string()));
77    }
78
79    /// Return all distinct subjects in the graph.
80    pub fn subjects(&self) -> Vec<String> {
81        self.forward.keys().cloned().collect()
82    }
83
84    /// Return all objects reachable from `subject` via `predicate`.
85    pub fn objects_of(&self, subject: &str, predicate: &str) -> Vec<String> {
86        self.forward
87            .get(subject)
88            .map(|pairs| {
89                pairs
90                    .iter()
91                    .filter(|(p, _)| p == predicate)
92                    .map(|(_, o)| o.clone())
93                    .collect()
94            })
95            .unwrap_or_default()
96    }
97
98    /// Return all subjects that have `predicate` pointing to `object`.
99    pub fn subjects_of(&self, object: &str, predicate: &str) -> Vec<String> {
100        self.reverse
101            .get(object)
102            .map(|pairs| {
103                pairs
104                    .iter()
105                    .filter(|(p, _)| p == predicate)
106                    .map(|(_, s)| s.clone())
107                    .collect()
108            })
109            .unwrap_or_default()
110    }
111
112    /// Return all distinct predicates in the graph.
113    pub fn all_predicates(&self) -> Vec<String> {
114        let mut preds: HashSet<String> = HashSet::new();
115        for pairs in self.forward.values() {
116            for (p, _) in pairs {
117                preds.insert(p.clone());
118            }
119        }
120        preds.into_iter().collect()
121    }
122
123    /// Return all objects reachable from `subject` via any predicate not in `excluded`.
124    pub fn objects_via_any_except(&self, subject: &str, excluded: &[String]) -> Vec<String> {
125        let excluded_set: HashSet<&String> = excluded.iter().collect();
126        self.forward
127            .get(subject)
128            .map(|pairs| {
129                pairs
130                    .iter()
131                    .filter(|(p, _)| !excluded_set.contains(p))
132                    .map(|(_, o)| o.clone())
133                    .collect()
134            })
135            .unwrap_or_default()
136    }
137}
138
139/// Evaluator for SPARQL 1.1 property path expressions.
140pub struct PropertyPathEvaluator;
141
142impl PropertyPathEvaluator {
143    /// Create a new evaluator.
144    pub fn new() -> Self {
145        Self
146    }
147
148    /// Evaluate a property path starting from `start_node` in `graph`.
149    ///
150    /// Returns the list of distinct reachable nodes (no duplicates).
151    pub fn evaluate(
152        &self,
153        graph: &PathGraph,
154        path: &PropertyPath,
155        start_node: &str,
156    ) -> Vec<String> {
157        let mut results = self.eval_inner(graph, path, start_node);
158        results.sort();
159        results.dedup();
160        results
161    }
162
163    fn eval_inner(&self, graph: &PathGraph, path: &PropertyPath, start: &str) -> Vec<String> {
164        match path {
165            PropertyPath::Iri(iri) => graph.objects_of(start, iri),
166
167            PropertyPath::Sequence(a, b) => {
168                let mid_nodes = self.eval_inner(graph, a, start);
169                let mut results = Vec::new();
170                for mid in &mid_nodes {
171                    let mut tail = self.eval_inner(graph, b, mid);
172                    results.append(&mut tail);
173                }
174                results
175            }
176
177            PropertyPath::Alternative(a, b) => {
178                let mut ra = self.eval_inner(graph, a, start);
179                let mut rb = self.eval_inner(graph, b, start);
180                ra.append(&mut rb);
181                ra
182            }
183
184            PropertyPath::ZeroOrMore(inner) => {
185                // BFS closure including start_node itself
186                self.bfs_closure(graph, inner, start, true)
187            }
188
189            PropertyPath::OneOrMore(inner) => {
190                // BFS closure excluding start_node (unless reachable via path)
191                self.bfs_closure(graph, inner, start, false)
192            }
193
194            PropertyPath::ZeroOrOne(inner) => {
195                // Direct objects + start_node itself
196                let mut results = self.eval_inner(graph, inner, start);
197                results.push(start.to_string());
198                results
199            }
200
201            PropertyPath::Inverse(inner) => {
202                // Evaluate with reversed graph
203                let reversed = Self::build_reverse_graph(graph);
204                self.eval_inner(&reversed, inner, start)
205            }
206
207            PropertyPath::NegatedSet(iris) => graph.objects_via_any_except(start, iris),
208        }
209    }
210
211    /// BFS transitive closure.
212    ///
213    /// `include_start` = true means ZeroOrMore (start node is always in results).
214    /// `include_start` = false means OneOrMore (start node only included if reachable).
215    fn bfs_closure(
216        &self,
217        graph: &PathGraph,
218        path: &PropertyPath,
219        start: &str,
220        include_start: bool,
221    ) -> Vec<String> {
222        let mut visited: HashSet<String> = HashSet::new();
223        let mut queue: VecDeque<String> = VecDeque::new();
224        let mut results: Vec<String> = Vec::new();
225
226        if include_start {
227            visited.insert(start.to_string());
228            results.push(start.to_string());
229        }
230
231        // Seed the queue with direct successors
232        let direct = self.eval_inner(graph, path, start);
233        for node in direct {
234            if visited.insert(node.clone()) {
235                results.push(node.clone());
236                queue.push_back(node);
237            }
238        }
239
240        // BFS
241        while let Some(current) = queue.pop_front() {
242            let next_nodes = self.eval_inner(graph, path, &current);
243            for node in next_nodes {
244                if visited.insert(node.clone()) {
245                    results.push(node.clone());
246                    queue.push_back(node);
247                }
248            }
249        }
250
251        results
252    }
253
254    /// Build a graph with all edges reversed (used for Inverse paths).
255    fn build_reverse_graph(graph: &PathGraph) -> PathGraph {
256        let mut reversed = PathGraph::new();
257        for (subject, pairs) in &graph.forward {
258            for (predicate, object) in pairs {
259                reversed.add_triple(object, predicate, subject);
260            }
261        }
262        reversed
263    }
264}
265
266impl Default for PropertyPathEvaluator {
267    fn default() -> Self {
268        Self::new()
269    }
270}
271
272/// Parse a simple property path string into a `PropertyPath`.
273///
274/// Handles the following forms:
275/// - `<iri>` — single IRI
276/// - `path/path` — sequence
277/// - `path|path` — alternative
278/// - `path*` — zero or more
279/// - `path+` — one or more
280/// - `path?` — zero or one
281/// - `^path` — inverse
282/// - `!(iri)` — negated set (single IRI)
283/// - `!(<iri1>|<iri2>|...)` — negated set (multiple IRIs)
284pub fn parse_path(s: &str) -> Result<PropertyPath, PathError> {
285    let s = s.trim();
286    if s.is_empty() {
287        return Err(PathError::EmptyPath);
288    }
289    parse_alternative(s)
290}
291
292/// Parse at the lowest precedence level: alternative (`|`).
293fn parse_alternative(s: &str) -> Result<PropertyPath, PathError> {
294    // Split on `|` but only at the top level (not inside angle brackets or parens)
295    let parts = split_top_level(s, '|');
296    if parts.len() == 1 {
297        return parse_sequence(s);
298    }
299    // Fold: a|b|c => Alternative(a, Alternative(b, c))
300    let mut iter = parts.iter().rev();
301    let last = parse_sequence(iter.next().ok_or(PathError::EmptyPath)?.trim())?;
302    let mut result = last;
303    for part in iter {
304        let left = parse_sequence(part.trim())?;
305        result = PropertyPath::Alternative(Box::new(left), Box::new(result));
306    }
307    Ok(result)
308}
309
310/// Parse sequence (`/`) at higher precedence than alternative.
311fn parse_sequence(s: &str) -> Result<PropertyPath, PathError> {
312    let parts = split_top_level(s, '/');
313    if parts.len() == 1 {
314        return parse_postfix(s);
315    }
316    let mut iter = parts.iter();
317    let first_str = iter.next().ok_or(PathError::EmptyPath)?.trim();
318    let mut result = parse_postfix(first_str)?;
319    for part in iter {
320        let right = parse_postfix(part.trim())?;
321        result = PropertyPath::Sequence(Box::new(result), Box::new(right));
322    }
323    Ok(result)
324}
325
326/// Parse postfix operators (`*`, `+`, `?`) and prefix `^` and `!`.
327fn parse_postfix(s: &str) -> Result<PropertyPath, PathError> {
328    if s.is_empty() {
329        return Err(PathError::EmptyPath);
330    }
331
332    // Handle inverse: ^path
333    if let Some(rest) = s.strip_prefix('^') {
334        let inner = parse_postfix(rest.trim())?;
335        return Ok(PropertyPath::Inverse(Box::new(inner)));
336    }
337
338    // Handle negated property set: !(iri) or !(<iri1>|<iri2>)
339    if let Some(stripped) = s.strip_prefix('!') {
340        let inner_str = stripped.trim();
341        // Must be wrapped in parens
342        if inner_str.starts_with('(') && inner_str.ends_with(')') {
343            let content = &inner_str[1..inner_str.len() - 1];
344            // Split by | to get individual IRIs
345            let iri_parts: Vec<&str> = content.split('|').collect();
346            let mut iris = Vec::new();
347            for part in iri_parts {
348                let p = part.trim();
349                if p.starts_with('<') && p.ends_with('>') {
350                    iris.push(p[1..p.len() - 1].to_string());
351                } else if !p.is_empty() {
352                    iris.push(p.to_string());
353                }
354            }
355            if iris.is_empty() {
356                return Err(PathError::UnknownSyntax(s.to_string()));
357            }
358            return Ok(PropertyPath::NegatedSet(iris));
359        }
360        return Err(PathError::UnknownSyntax(s.to_string()));
361    }
362
363    // Check for postfix suffix: *, +, ?
364    // The suffix is the last character if the string is wrapped in parens or an IRI
365    let (base_str, suffix) = extract_postfix_suffix(s);
366
367    let base = parse_atom(base_str)?;
368    match suffix {
369        Some('*') => Ok(PropertyPath::ZeroOrMore(Box::new(base))),
370        Some('+') => Ok(PropertyPath::OneOrMore(Box::new(base))),
371        Some('?') => Ok(PropertyPath::ZeroOrOne(Box::new(base))),
372        Some(c) => Err(PathError::UnknownSyntax(format!("Unknown postfix: {c}"))),
373        None => Ok(base),
374    }
375}
376
377/// Extract the postfix suffix character from a path string, returning (base, suffix).
378fn extract_postfix_suffix(s: &str) -> (&str, Option<char>) {
379    if s.is_empty() {
380        return (s, None);
381    }
382    let last = s.chars().next_back();
383    match last {
384        Some('*') | Some('+') | Some('?') => {
385            let suffix_char = last;
386            let base = s[..s.len() - 1].trim_end();
387            // Only strip the suffix if the base makes sense
388            if !base.is_empty() {
389                (base, suffix_char)
390            } else {
391                (s, None)
392            }
393        }
394        _ => (s, None),
395    }
396}
397
398/// Parse an atom: a parenthesized expression or a bare IRI.
399fn parse_atom(s: &str) -> Result<PropertyPath, PathError> {
400    let s = s.trim();
401    if s.is_empty() {
402        return Err(PathError::EmptyPath);
403    }
404
405    // Parenthesized group: (expr)
406    if s.starts_with('(') && s.ends_with(')') {
407        let inner = &s[1..s.len() - 1];
408        return parse_alternative(inner);
409    }
410
411    // IRI in angle brackets: <iri>
412    if s.starts_with('<') && s.ends_with('>') {
413        let iri = &s[1..s.len() - 1];
414        return Ok(PropertyPath::Iri(iri.to_string()));
415    }
416
417    // Bare name (prefix:local or just a name for testing)
418    if s.chars()
419        .all(|c| c.is_alphanumeric() || c == ':' || c == '_' || c == '-' || c == '.')
420    {
421        return Ok(PropertyPath::Iri(s.to_string()));
422    }
423
424    Err(PathError::UnknownSyntax(s.to_string()))
425}
426
427/// Split a string on `delimiter` only at the top level (not inside `<>` or `()`).
428fn split_top_level(s: &str, delimiter: char) -> Vec<&str> {
429    let mut parts = Vec::new();
430    let mut depth_angle = 0usize;
431    let mut depth_paren = 0usize;
432    let mut start = 0;
433
434    for (i, c) in s.char_indices() {
435        match c {
436            '<' => depth_angle += 1,
437            '>' => depth_angle = depth_angle.saturating_sub(1),
438            '(' => depth_paren += 1,
439            ')' => depth_paren = depth_paren.saturating_sub(1),
440            _ if c == delimiter && depth_angle == 0 && depth_paren == 0 => {
441                parts.push(&s[start..i]);
442                start = i + delimiter.len_utf8();
443            }
444            _ => {}
445        }
446    }
447    parts.push(&s[start..]);
448    parts
449}
450
451#[cfg(test)]
452mod tests {
453    use super::*;
454
455    fn make_graph() -> PathGraph {
456        let mut g = PathGraph::new();
457        // Simple chain: a -p-> b -p-> c -p-> d
458        g.add_triple("a", "p", "b");
459        g.add_triple("b", "p", "c");
460        g.add_triple("c", "p", "d");
461        // Alternative predicate
462        g.add_triple("a", "q", "e");
463        // Inverse: e -r-> a (so ^r from a is nothing, but from e via ^r gives a's predecessors)
464        g.add_triple("e", "r", "a");
465        g
466    }
467
468    fn evaluator() -> PropertyPathEvaluator {
469        PropertyPathEvaluator::new()
470    }
471
472    // ── IRI path ──────────────────────────────────────────────────────────────
473
474    #[test]
475    fn test_iri_path_simple() {
476        let g = make_graph();
477        let ev = evaluator();
478        let path = PropertyPath::Iri("p".to_string());
479        let mut r = ev.evaluate(&g, &path, "a");
480        r.sort();
481        assert_eq!(r, vec!["b"]);
482    }
483
484    #[test]
485    fn test_iri_path_no_match() {
486        let g = make_graph();
487        let ev = evaluator();
488        let path = PropertyPath::Iri("p".to_string());
489        let r = ev.evaluate(&g, &path, "d"); // d has no outgoing p
490        assert!(r.is_empty());
491    }
492
493    #[test]
494    fn test_iri_path_multiple_objects() {
495        let mut g = PathGraph::new();
496        g.add_triple("a", "p", "b");
497        g.add_triple("a", "p", "c");
498        let ev = evaluator();
499        let path = PropertyPath::Iri("p".to_string());
500        let mut r = ev.evaluate(&g, &path, "a");
501        r.sort();
502        assert_eq!(r, vec!["b", "c"]);
503    }
504
505    // ── Sequence path ─────────────────────────────────────────────────────────
506
507    #[test]
508    fn test_sequence_two_hops() {
509        let g = make_graph();
510        let ev = evaluator();
511        let path = PropertyPath::Sequence(
512            Box::new(PropertyPath::Iri("p".to_string())),
513            Box::new(PropertyPath::Iri("p".to_string())),
514        );
515        let r = ev.evaluate(&g, &path, "a");
516        assert_eq!(r, vec!["c"]);
517    }
518
519    #[test]
520    fn test_sequence_three_hops() {
521        let g = make_graph();
522        let ev = evaluator();
523        let path = PropertyPath::Sequence(
524            Box::new(PropertyPath::Sequence(
525                Box::new(PropertyPath::Iri("p".to_string())),
526                Box::new(PropertyPath::Iri("p".to_string())),
527            )),
528            Box::new(PropertyPath::Iri("p".to_string())),
529        );
530        let r = ev.evaluate(&g, &path, "a");
531        assert_eq!(r, vec!["d"]);
532    }
533
534    #[test]
535    fn test_sequence_no_match() {
536        let g = make_graph();
537        let ev = evaluator();
538        let path = PropertyPath::Sequence(
539            Box::new(PropertyPath::Iri("p".to_string())),
540            Box::new(PropertyPath::Iri("q".to_string())), // no q after p
541        );
542        let r = ev.evaluate(&g, &path, "a");
543        assert!(r.is_empty());
544    }
545
546    // ── Alternative path ──────────────────────────────────────────────────────
547
548    #[test]
549    fn test_alternative_both_branches() {
550        let g = make_graph();
551        let ev = evaluator();
552        let path = PropertyPath::Alternative(
553            Box::new(PropertyPath::Iri("p".to_string())),
554            Box::new(PropertyPath::Iri("q".to_string())),
555        );
556        let mut r = ev.evaluate(&g, &path, "a");
557        r.sort();
558        assert_eq!(r, vec!["b", "e"]);
559    }
560
561    #[test]
562    fn test_alternative_dedup() {
563        let mut g = PathGraph::new();
564        g.add_triple("a", "p", "b");
565        g.add_triple("a", "q", "b"); // both reach b
566        let ev = evaluator();
567        let path = PropertyPath::Alternative(
568            Box::new(PropertyPath::Iri("p".to_string())),
569            Box::new(PropertyPath::Iri("q".to_string())),
570        );
571        let r = ev.evaluate(&g, &path, "a");
572        assert_eq!(r, vec!["b"]); // deduped
573    }
574
575    #[test]
576    fn test_alternative_one_empty() {
577        let g = make_graph();
578        let ev = evaluator();
579        let path = PropertyPath::Alternative(
580            Box::new(PropertyPath::Iri("p".to_string())),
581            Box::new(PropertyPath::Iri("z".to_string())), // z doesn't exist
582        );
583        let r = ev.evaluate(&g, &path, "a");
584        assert_eq!(r, vec!["b"]);
585    }
586
587    // ── ZeroOrMore path ───────────────────────────────────────────────────────
588
589    #[test]
590    fn test_zero_or_more_includes_start() {
591        let g = make_graph();
592        let ev = evaluator();
593        let path = PropertyPath::ZeroOrMore(Box::new(PropertyPath::Iri("p".to_string())));
594        let mut r = ev.evaluate(&g, &path, "a");
595        r.sort();
596        assert_eq!(r, vec!["a", "b", "c", "d"]);
597    }
598
599    #[test]
600    fn test_zero_or_more_no_outgoing() {
601        let g = make_graph();
602        let ev = evaluator();
603        let path = PropertyPath::ZeroOrMore(Box::new(PropertyPath::Iri("p".to_string())));
604        let r = ev.evaluate(&g, &path, "d"); // d has no outgoing p
605        assert_eq!(r, vec!["d"]); // just start
606    }
607
608    #[test]
609    fn test_zero_or_more_cycle_safety() {
610        let mut g = PathGraph::new();
611        g.add_triple("a", "p", "b");
612        g.add_triple("b", "p", "a"); // cycle
613        let ev = evaluator();
614        let path = PropertyPath::ZeroOrMore(Box::new(PropertyPath::Iri("p".to_string())));
615        let mut r = ev.evaluate(&g, &path, "a");
616        r.sort();
617        assert_eq!(r, vec!["a", "b"]); // no infinite loop
618    }
619
620    // ── OneOrMore path ────────────────────────────────────────────────────────
621
622    #[test]
623    fn test_one_or_more_excludes_start() {
624        let g = make_graph();
625        let ev = evaluator();
626        let path = PropertyPath::OneOrMore(Box::new(PropertyPath::Iri("p".to_string())));
627        let mut r = ev.evaluate(&g, &path, "a");
628        r.sort();
629        assert_eq!(r, vec!["b", "c", "d"]);
630    }
631
632    #[test]
633    fn test_one_or_more_no_outgoing() {
634        let g = make_graph();
635        let ev = evaluator();
636        let path = PropertyPath::OneOrMore(Box::new(PropertyPath::Iri("p".to_string())));
637        let r = ev.evaluate(&g, &path, "d");
638        assert!(r.is_empty());
639    }
640
641    #[test]
642    fn test_one_or_more_cycle_safety() {
643        let mut g = PathGraph::new();
644        g.add_triple("a", "p", "b");
645        g.add_triple("b", "p", "a");
646        let ev = evaluator();
647        let path = PropertyPath::OneOrMore(Box::new(PropertyPath::Iri("p".to_string())));
648        let mut r = ev.evaluate(&g, &path, "a");
649        r.sort();
650        // b is reachable; a is reachable via b->a but we only add if not visited
651        // "a" is not in initial visited set (OneOrMore), so it will be added when b->a is found
652        assert!(r.contains(&"b".to_string()));
653    }
654
655    // ── ZeroOrOne path ────────────────────────────────────────────────────────
656
657    #[test]
658    fn test_zero_or_one_includes_start() {
659        let g = make_graph();
660        let ev = evaluator();
661        let path = PropertyPath::ZeroOrOne(Box::new(PropertyPath::Iri("p".to_string())));
662        let mut r = ev.evaluate(&g, &path, "a");
663        r.sort();
664        assert_eq!(r, vec!["a", "b"]);
665    }
666
667    #[test]
668    fn test_zero_or_one_no_outgoing() {
669        let g = make_graph();
670        let ev = evaluator();
671        let path = PropertyPath::ZeroOrOne(Box::new(PropertyPath::Iri("p".to_string())));
672        let mut r = ev.evaluate(&g, &path, "d");
673        r.sort();
674        assert_eq!(r, vec!["d"]); // just start node
675    }
676
677    // ── Inverse path ──────────────────────────────────────────────────────────
678
679    #[test]
680    fn test_inverse_path() {
681        let g = make_graph();
682        let ev = evaluator();
683        let path = PropertyPath::Inverse(Box::new(PropertyPath::Iri("p".to_string())));
684        let r = ev.evaluate(&g, &path, "b"); // who points to b via p?
685        assert_eq!(r, vec!["a"]);
686    }
687
688    #[test]
689    fn test_inverse_chain() {
690        let g = make_graph();
691        let ev = evaluator();
692        // From d, go backwards via p twice = b
693        let path = PropertyPath::Sequence(
694            Box::new(PropertyPath::Inverse(Box::new(PropertyPath::Iri(
695                "p".to_string(),
696            )))),
697            Box::new(PropertyPath::Inverse(Box::new(PropertyPath::Iri(
698                "p".to_string(),
699            )))),
700        );
701        let r = ev.evaluate(&g, &path, "d");
702        assert_eq!(r, vec!["b"]);
703    }
704
705    #[test]
706    fn test_inverse_no_match() {
707        let g = make_graph();
708        let ev = evaluator();
709        let path = PropertyPath::Inverse(Box::new(PropertyPath::Iri("p".to_string())));
710        let r = ev.evaluate(&g, &path, "a"); // nobody points to a via p
711        assert!(r.is_empty());
712    }
713
714    // ── NegatedSet path ───────────────────────────────────────────────────────
715
716    #[test]
717    fn test_negated_set_excludes_predicate() {
718        let g = make_graph();
719        let ev = evaluator();
720        let path = PropertyPath::NegatedSet(vec!["q".to_string()]);
721        let mut r = ev.evaluate(&g, &path, "a"); // a has p->b and q->e; exclude q
722        r.sort();
723        assert_eq!(r, vec!["b"]);
724    }
725
726    #[test]
727    fn test_negated_set_all_excluded() {
728        let g = make_graph();
729        let ev = evaluator();
730        let path = PropertyPath::NegatedSet(vec!["p".to_string(), "q".to_string()]);
731        let r = ev.evaluate(&g, &path, "a"); // all predicates excluded
732        assert!(r.is_empty());
733    }
734
735    #[test]
736    fn test_negated_set_empty_exclusion() {
737        let g = make_graph();
738        let ev = evaluator();
739        let path = PropertyPath::NegatedSet(vec![]); // exclude nothing = all
740        let mut r = ev.evaluate(&g, &path, "a");
741        r.sort();
742        assert_eq!(r, vec!["b", "e"]);
743    }
744
745    // ── PathGraph methods ─────────────────────────────────────────────────────
746
747    #[test]
748    fn test_path_graph_subjects() {
749        let g = make_graph();
750        let mut s = g.subjects();
751        s.sort();
752        assert!(s.contains(&"a".to_string()));
753        assert!(s.contains(&"e".to_string()));
754    }
755
756    #[test]
757    fn test_path_graph_objects_of() {
758        let g = make_graph();
759        let r = g.objects_of("a", "p");
760        assert_eq!(r, vec!["b"]);
761    }
762
763    #[test]
764    fn test_path_graph_add_multiple() {
765        let mut g = PathGraph::new();
766        g.add_triple("x", "pred", "y1");
767        g.add_triple("x", "pred", "y2");
768        g.add_triple("x", "pred", "y3");
769        let mut r = g.objects_of("x", "pred");
770        r.sort();
771        assert_eq!(r, vec!["y1", "y2", "y3"]);
772    }
773
774    // ── parse_path ────────────────────────────────────────────────────────────
775
776    #[test]
777    fn test_parse_iri() {
778        let p = parse_path("<http://example.org/p>").expect("path parse should succeed");
779        assert_eq!(p, PropertyPath::Iri("http://example.org/p".to_string()));
780    }
781
782    #[test]
783    fn test_parse_empty_error() {
784        let r = parse_path("");
785        assert_eq!(r, Err(PathError::EmptyPath));
786    }
787
788    #[test]
789    fn test_parse_sequence() {
790        let p = parse_path("<a>/<b>").expect("path parse should succeed");
791        assert_eq!(
792            p,
793            PropertyPath::Sequence(
794                Box::new(PropertyPath::Iri("a".to_string())),
795                Box::new(PropertyPath::Iri("b".to_string())),
796            )
797        );
798    }
799
800    #[test]
801    fn test_parse_alternative() {
802        let p = parse_path("<a>|<b>").expect("path parse should succeed");
803        assert_eq!(
804            p,
805            PropertyPath::Alternative(
806                Box::new(PropertyPath::Iri("a".to_string())),
807                Box::new(PropertyPath::Iri("b".to_string())),
808            )
809        );
810    }
811
812    #[test]
813    fn test_parse_zero_or_more() {
814        let p = parse_path("<a>*").expect("path parse should succeed");
815        assert_eq!(
816            p,
817            PropertyPath::ZeroOrMore(Box::new(PropertyPath::Iri("a".to_string())))
818        );
819    }
820
821    #[test]
822    fn test_parse_one_or_more() {
823        let p = parse_path("<a>+").expect("path parse should succeed");
824        assert_eq!(
825            p,
826            PropertyPath::OneOrMore(Box::new(PropertyPath::Iri("a".to_string())))
827        );
828    }
829
830    #[test]
831    fn test_parse_zero_or_one() {
832        let p = parse_path("<a>?").expect("path parse should succeed");
833        assert_eq!(
834            p,
835            PropertyPath::ZeroOrOne(Box::new(PropertyPath::Iri("a".to_string())))
836        );
837    }
838
839    #[test]
840    fn test_parse_inverse() {
841        let p = parse_path("^<a>").expect("path parse should succeed");
842        assert_eq!(
843            p,
844            PropertyPath::Inverse(Box::new(PropertyPath::Iri("a".to_string())))
845        );
846    }
847
848    #[test]
849    fn test_parse_negated_set_single() {
850        let p = parse_path("!(<http://example.org/p>)").expect("path parse should succeed");
851        assert_eq!(
852            p,
853            PropertyPath::NegatedSet(vec!["http://example.org/p".to_string()])
854        );
855    }
856
857    #[test]
858    fn test_parse_negated_set_multiple() {
859        let p = parse_path("!(<a>|<b>)").expect("path parse should succeed");
860        assert_eq!(
861            p,
862            PropertyPath::NegatedSet(vec!["a".to_string(), "b".to_string()])
863        );
864    }
865
866    #[test]
867    fn test_parse_bare_name() {
868        let p = parse_path("rdf:type").expect("path parse should succeed");
869        assert_eq!(p, PropertyPath::Iri("rdf:type".to_string()));
870    }
871
872    // ── BFS cycle detection ───────────────────────────────────────────────────
873
874    #[test]
875    fn test_zero_or_more_complex_cycle() {
876        let mut g = PathGraph::new();
877        g.add_triple("a", "p", "b");
878        g.add_triple("b", "p", "c");
879        g.add_triple("c", "p", "a"); // back to a
880        let ev = evaluator();
881        let path = PropertyPath::ZeroOrMore(Box::new(PropertyPath::Iri("p".to_string())));
882        let mut r = ev.evaluate(&g, &path, "a");
883        r.sort();
884        assert_eq!(r, vec!["a", "b", "c"]);
885    }
886
887    #[test]
888    fn test_one_or_more_self_loop() {
889        let mut g = PathGraph::new();
890        g.add_triple("a", "p", "a"); // self loop
891        let ev = evaluator();
892        let path = PropertyPath::OneOrMore(Box::new(PropertyPath::Iri("p".to_string())));
893        let mut r = ev.evaluate(&g, &path, "a");
894        r.sort();
895        assert_eq!(r, vec!["a"]);
896    }
897
898    // ── PathError display ─────────────────────────────────────────────────────
899
900    #[test]
901    fn test_path_error_display() {
902        let e = PathError::UnknownSyntax("???".to_string());
903        assert!(e.to_string().contains("Unknown path syntax"));
904
905        let e2 = PathError::EmptyPath;
906        assert!(e2.to_string().contains("Empty path"));
907    }
908
909    // ── default impl ──────────────────────────────────────────────────────────
910
911    #[test]
912    fn test_evaluator_default() {
913        let ev = PropertyPathEvaluator;
914        let g = PathGraph::new();
915        let path = PropertyPath::Iri("p".to_string());
916        let r = ev.evaluate(&g, &path, "x");
917        assert!(r.is_empty());
918    }
919
920    #[test]
921    fn test_graph_default() {
922        let g = PathGraph::default();
923        assert!(g.subjects().is_empty());
924    }
925}
oxirs_core/model/property_path_evaluator.rs

oxirs_core/model/
property_path_evaluator.rs
