oxirs_ttl/toolkit/
pattern_matcher.rs

1//! Pattern Matching and Query Utilities
2//!
3//! This module provides simple SPARQL-like pattern matching for in-memory RDF graphs.
4//! Useful for quick queries without setting up a full SPARQL engine.
5//!
6//! # Examples
7//!
8//! ## Basic Pattern Matching
9//!
10//! ```rust
11//! use oxirs_ttl::toolkit::pattern_matcher::{PatternMatcher, TriplePattern};
12//! use oxirs_core::model::{Triple, NamedNode};
13//!
14//! let triples = vec![
15//!     Triple::new(
16//!         NamedNode::new("http://example.org/alice")?,
17//!         NamedNode::new("http://xmlns.com/foaf/0.1/knows")?,
18//!         NamedNode::new("http://example.org/bob")?,
19//!     ),
20//!     Triple::new(
21//!         NamedNode::new("http://example.org/bob")?,
22//!         NamedNode::new("http://xmlns.com/foaf/0.1/knows")?,
23//!         NamedNode::new("http://example.org/charlie")?,
24//!     ),
25//! ];
26//!
27//! let matcher = PatternMatcher::new(&triples);
28//!
29//! // Find all triples with "knows" predicate
30//! let pattern = TriplePattern::new()
31//!     .with_predicate("http://xmlns.com/foaf/0.1/knows");
32//!
33//! let results = matcher.find_matches(&pattern);
34//! assert_eq!(results.len(), 2);
35//! # Ok::<(), Box<dyn std::error::Error>>(())
36//! ```
37//!
38//! ## Variable Binding
39//!
40//! ```rust
41//! use oxirs_ttl::toolkit::pattern_matcher::{PatternMatcher, TriplePattern};
42//! use oxirs_core::model::{Triple, NamedNode};
43//!
44//! let triples = vec![
45//!     Triple::new(
46//!         NamedNode::new("http://example.org/alice")?,
47//!         NamedNode::new("http://example.org/age")?,
48//!         NamedNode::new("http://example.org/30")?,
49//!     ),
50//! ];
51//!
52//! let matcher = PatternMatcher::new(&triples);
53//! let pattern = TriplePattern::new()
54//!     .with_subject("http://example.org/alice");
55//!
56//! let results = matcher.find_matches(&pattern);
57//! assert_eq!(results.len(), 1);
58//! # Ok::<(), Box<dyn std::error::Error>>(())
59//! ```
60
61use oxirs_core::model::Triple;
62use oxirs_core::RdfTerm;
63use std::collections::HashMap;
64
65/// A pattern for matching RDF triples
66///
67/// Patterns can specify exact values or leave components unbound (wildcard).
68#[derive(Debug, Clone)]
69pub struct TriplePattern {
70    subject: Option<String>,
71    predicate: Option<String>,
72    object: Option<String>,
73}
74
75impl TriplePattern {
76    /// Create a new empty pattern (matches all triples)
77    pub fn new() -> Self {
78        Self {
79            subject: None,
80            predicate: None,
81            object: None,
82        }
83    }
84
85    /// Set the subject pattern
86    pub fn with_subject(mut self, subject: &str) -> Self {
87        self.subject = Some(subject.to_string());
88        self
89    }
90
91    /// Set the predicate pattern
92    pub fn with_predicate(mut self, predicate: &str) -> Self {
93        self.predicate = Some(predicate.to_string());
94        self
95    }
96
97    /// Set the object pattern
98    pub fn with_object(mut self, object: &str) -> Self {
99        self.object = Some(object.to_string());
100        self
101    }
102
103    /// Check if a triple matches this pattern
104    pub fn matches(&self, triple: &Triple) -> bool {
105        if let Some(ref subject) = self.subject {
106            if !triple.subject().as_str().contains(subject) {
107                return false;
108            }
109        }
110
111        if let Some(ref predicate) = self.predicate {
112            if !triple.predicate().as_str().contains(predicate) {
113                return false;
114            }
115        }
116
117        if let Some(ref object) = self.object {
118            if !triple.object().as_str().contains(object) {
119                return false;
120            }
121        }
122
123        true
124    }
125
126    /// Check if pattern is empty (matches all)
127    pub fn is_empty(&self) -> bool {
128        self.subject.is_none() && self.predicate.is_none() && self.object.is_none()
129    }
130}
131
132impl Default for TriplePattern {
133    fn default() -> Self {
134        Self::new()
135    }
136}
137
138/// Pattern matcher for RDF triples
139///
140/// Provides efficient pattern matching over in-memory triple collections.
141#[derive(Debug)]
142pub struct PatternMatcher<'a> {
143    triples: &'a [Triple],
144    // Index for faster lookups
145    subject_index: HashMap<String, Vec<usize>>,
146    predicate_index: HashMap<String, Vec<usize>>,
147    object_index: HashMap<String, Vec<usize>>,
148}
149
150impl<'a> PatternMatcher<'a> {
151    /// Create a new pattern matcher for a collection of triples
152    ///
153    /// This builds indices for efficient pattern matching.
154    pub fn new(triples: &'a [Triple]) -> Self {
155        let mut subject_index: HashMap<String, Vec<usize>> = HashMap::new();
156        let mut predicate_index: HashMap<String, Vec<usize>> = HashMap::new();
157        let mut object_index: HashMap<String, Vec<usize>> = HashMap::new();
158
159        for (idx, triple) in triples.iter().enumerate() {
160            subject_index
161                .entry(triple.subject().to_string())
162                .or_default()
163                .push(idx);
164
165            predicate_index
166                .entry(triple.predicate().to_string())
167                .or_default()
168                .push(idx);
169
170            object_index
171                .entry(triple.object().to_string())
172                .or_default()
173                .push(idx);
174        }
175
176        Self {
177            triples,
178            subject_index,
179            predicate_index,
180            object_index,
181        }
182    }
183
184    /// Find all triples matching a pattern
185    ///
186    /// Returns references to matching triples.
187    pub fn find_matches(&self, pattern: &TriplePattern) -> Vec<&Triple> {
188        if pattern.is_empty() {
189            return self.triples.iter().collect();
190        }
191
192        // Use indices for more efficient lookup
193        let candidates = if let Some(ref subject) = pattern.subject {
194            self.subject_index
195                .iter()
196                .filter(|(k, _)| k.contains(subject))
197                .flat_map(|(_, indices)| indices.iter().copied())
198                .collect::<Vec<_>>()
199        } else if let Some(ref predicate) = pattern.predicate {
200            self.predicate_index
201                .iter()
202                .filter(|(k, _)| k.contains(predicate))
203                .flat_map(|(_, indices)| indices.iter().copied())
204                .collect::<Vec<_>>()
205        } else if let Some(ref object) = pattern.object {
206            self.object_index
207                .iter()
208                .filter(|(k, _)| k.contains(object))
209                .flat_map(|(_, indices)| indices.iter().copied())
210                .collect::<Vec<_>>()
211        } else {
212            (0..self.triples.len()).collect()
213        };
214
215        candidates
216            .into_iter()
217            .filter_map(|idx| {
218                let triple = &self.triples[idx];
219                if pattern.matches(triple) {
220                    Some(triple)
221                } else {
222                    None
223                }
224            })
225            .collect()
226    }
227
228    /// Count matches for a pattern without collecting results
229    pub fn count_matches(&self, pattern: &TriplePattern) -> usize {
230        if pattern.is_empty() {
231            return self.triples.len();
232        }
233
234        self.triples.iter().filter(|t| pattern.matches(t)).count()
235    }
236
237    /// Check if any triple matches the pattern
238    pub fn has_match(&self, pattern: &TriplePattern) -> bool {
239        if pattern.is_empty() {
240            return !self.triples.is_empty();
241        }
242
243        self.triples.iter().any(|t| pattern.matches(t))
244    }
245
246    /// Get all unique subjects
247    pub fn subjects(&self) -> Vec<String> {
248        self.subject_index.keys().cloned().collect()
249    }
250
251    /// Get all unique predicates
252    pub fn predicates(&self) -> Vec<String> {
253        self.predicate_index.keys().cloned().collect()
254    }
255
256    /// Get all unique objects
257    pub fn objects(&self) -> Vec<String> {
258        self.object_index.keys().cloned().collect()
259    }
260}
261
262/// Query builder for more complex patterns
263#[derive(Debug)]
264pub struct QueryBuilder {
265    patterns: Vec<TriplePattern>,
266    limit: Option<usize>,
267    offset: usize,
268}
269
270impl QueryBuilder {
271    /// Create a new query builder
272    pub fn new() -> Self {
273        Self {
274            patterns: Vec::new(),
275            limit: None,
276            offset: 0,
277        }
278    }
279
280    /// Add a pattern to the query
281    pub fn pattern(mut self, pattern: TriplePattern) -> Self {
282        self.patterns.push(pattern);
283        self
284    }
285
286    /// Set a limit on results
287    pub fn limit(mut self, limit: usize) -> Self {
288        self.limit = Some(limit);
289        self
290    }
291
292    /// Set an offset for results
293    pub fn offset(mut self, offset: usize) -> Self {
294        self.offset = offset;
295        self
296    }
297
298    /// Execute the query against a matcher
299    pub fn execute<'a>(&self, matcher: &'a PatternMatcher) -> Vec<&'a Triple> {
300        if self.patterns.is_empty() {
301            return Vec::new();
302        }
303
304        // Start with first pattern
305        let mut results = matcher.find_matches(&self.patterns[0]);
306
307        // Intersect with remaining patterns
308        for pattern in &self.patterns[1..] {
309            let pattern_results = matcher.find_matches(pattern);
310            results.retain(|t| pattern_results.contains(t));
311        }
312
313        // Apply offset and limit
314        let results: Vec<_> = results.into_iter().skip(self.offset).collect();
315
316        if let Some(limit) = self.limit {
317            results.into_iter().take(limit).collect()
318        } else {
319            results
320        }
321    }
322
323    /// Count results without collecting
324    pub fn count(&self, matcher: &PatternMatcher) -> usize {
325        if self.patterns.is_empty() {
326            return 0;
327        }
328
329        let mut results = matcher.find_matches(&self.patterns[0]);
330
331        for pattern in &self.patterns[1..] {
332            let pattern_results = matcher.find_matches(pattern);
333            results.retain(|t| pattern_results.contains(t));
334        }
335
336        if self.offset >= results.len() {
337            return 0;
338        }
339
340        let remaining = results.len() - self.offset;
341        self.limit.map_or(remaining, |limit| remaining.min(limit))
342    }
343}
344
345impl Default for QueryBuilder {
346    fn default() -> Self {
347        Self::new()
348    }
349}
350
351#[cfg(test)]
352mod tests {
353    use super::*;
354    use oxirs_core::model::NamedNode;
355
356    fn create_test_triple(s: &str, p: &str, o: &str) -> Triple {
357        Triple::new(
358            NamedNode::new(s).expect("valid IRI"),
359            NamedNode::new(p).expect("valid IRI"),
360            NamedNode::new(o).expect("valid IRI"),
361        )
362    }
363
364    #[test]
365    fn test_pattern_matching() {
366        let triples = vec![
367            create_test_triple(
368                "http://example.org/alice",
369                "http://xmlns.com/foaf/0.1/knows",
370                "http://example.org/bob",
371            ),
372            create_test_triple(
373                "http://example.org/bob",
374                "http://xmlns.com/foaf/0.1/knows",
375                "http://example.org/charlie",
376            ),
377            create_test_triple(
378                "http://example.org/alice",
379                "http://example.org/age",
380                "http://example.org/30",
381            ),
382        ];
383
384        let matcher = PatternMatcher::new(&triples);
385
386        // Match by predicate
387        let pattern = TriplePattern::new().with_predicate("foaf/0.1/knows");
388        let results = matcher.find_matches(&pattern);
389        assert_eq!(results.len(), 2);
390
391        // Match by subject
392        let pattern = TriplePattern::new().with_subject("alice");
393        let results = matcher.find_matches(&pattern);
394        assert_eq!(results.len(), 2);
395
396        // Match by multiple criteria
397        let pattern = TriplePattern::new()
398            .with_subject("alice")
399            .with_predicate("knows");
400        let results = matcher.find_matches(&pattern);
401        assert_eq!(results.len(), 1);
402    }
403
404    #[test]
405    fn test_count_and_has_match() {
406        let triples = vec![create_test_triple(
407            "http://example.org/s",
408            "http://example.org/p",
409            "http://example.org/o",
410        )];
411
412        let matcher = PatternMatcher::new(&triples);
413        let pattern = TriplePattern::new().with_subject("example.org/s");
414
415        assert_eq!(matcher.count_matches(&pattern), 1);
416        assert!(matcher.has_match(&pattern));
417
418        let no_match = TriplePattern::new().with_subject("notfound");
419        assert!(!matcher.has_match(&no_match));
420    }
421
422    #[test]
423    fn test_query_builder() {
424        let triples = vec![
425            create_test_triple(
426                "http://example.org/alice",
427                "http://xmlns.com/foaf/0.1/knows",
428                "http://example.org/bob",
429            ),
430            create_test_triple(
431                "http://example.org/bob",
432                "http://xmlns.com/foaf/0.1/knows",
433                "http://example.org/charlie",
434            ),
435            create_test_triple(
436                "http://example.org/alice",
437                "http://example.org/age",
438                "http://example.org/30",
439            ),
440        ];
441
442        let matcher = PatternMatcher::new(&triples);
443
444        let query = QueryBuilder::new()
445            .pattern(TriplePattern::new().with_predicate("knows"))
446            .limit(1);
447
448        let results = query.execute(&matcher);
449        assert_eq!(results.len(), 1);
450
451        let count = query.count(&matcher);
452        assert_eq!(count, 1);
453    }
454
455    #[test]
456    fn test_empty_pattern() {
457        let triples = vec![create_test_triple(
458            "http://example.org/s",
459            "http://example.org/p",
460            "http://example.org/o",
461        )];
462
463        let matcher = PatternMatcher::new(&triples);
464        let pattern = TriplePattern::new();
465
466        assert!(pattern.is_empty());
467        assert_eq!(matcher.find_matches(&pattern).len(), 1);
468    }
469
470    #[test]
471    fn test_index_queries() {
472        let triples = vec![
473            create_test_triple(
474                "http://example.org/s1",
475                "http://example.org/p",
476                "http://example.org/o1",
477            ),
478            create_test_triple(
479                "http://example.org/s2",
480                "http://example.org/p",
481                "http://example.org/o2",
482            ),
483        ];
484
485        let matcher = PatternMatcher::new(&triples);
486
487        let subjects = matcher.subjects();
488        assert_eq!(subjects.len(), 2);
489
490        let predicates = matcher.predicates();
491        assert_eq!(predicates.len(), 1);
492
493        let objects = matcher.objects();
494        assert_eq!(objects.len(), 2);
495    }
496
497    #[test]
498    fn test_query_with_offset() {
499        let triples = vec![
500            create_test_triple(
501                "http://example.org/s1",
502                "http://example.org/p",
503                "http://example.org/o1",
504            ),
505            create_test_triple(
506                "http://example.org/s2",
507                "http://example.org/p",
508                "http://example.org/o2",
509            ),
510            create_test_triple(
511                "http://example.org/s3",
512                "http://example.org/p",
513                "http://example.org/o3",
514            ),
515        ];
516
517        let matcher = PatternMatcher::new(&triples);
518
519        let query = QueryBuilder::new()
520            .pattern(TriplePattern::new().with_predicate("example.org/p"))
521            .offset(1)
522            .limit(1);
523
524        let results = query.execute(&matcher);
525        assert_eq!(results.len(), 1);
526    }
527}
oxirs_ttl/toolkit/pattern_matcher.rs

oxirs_ttl/toolkit/
pattern_matcher.rs
