oxirs_core/query/
exec.rs

1//! Query execution engine
2//!
3//! This module executes query plans against RDF stores.
4
5use crate::model::*;
6use crate::query::algebra::*;
7use crate::query::plan::ExecutionPlan;
8use crate::OxirsError;
9use crate::Store;
10use std::collections::{HashMap, HashSet};
11
12/// A solution mapping (binding of variables to values)
13#[derive(Debug, Clone, PartialEq)]
14pub struct Solution {
15    bindings: HashMap<Variable, Term>,
16}
17
18impl Solution {
19    /// Creates a new empty solution
20    pub fn new() -> Self {
21        Solution {
22            bindings: HashMap::new(),
23        }
24    }
25
26    /// Binds a variable to a value
27    pub fn bind(&mut self, var: Variable, value: Term) {
28        self.bindings.insert(var, value);
29    }
30
31    /// Gets the value bound to a variable
32    pub fn get(&self, var: &Variable) -> Option<&Term> {
33        self.bindings.get(var)
34    }
35
36    /// Merges two solutions (for joins)
37    pub fn merge(&self, other: &Solution) -> Option<Solution> {
38        let mut merged = self.clone();
39
40        for (var, value) in &other.bindings {
41            if let Some(existing) = merged.bindings.get(var) {
42                if existing != value {
43                    return None; // Incompatible bindings
44                }
45            } else {
46                merged.bindings.insert(var.clone(), value.clone());
47            }
48        }
49
50        Some(merged)
51    }
52
53    /// Projects specific variables
54    pub fn project(&self, vars: &[Variable]) -> Solution {
55        let mut projected = Solution::new();
56        for var in vars {
57            if let Some(value) = self.bindings.get(var) {
58                projected.bind(var.clone(), value.clone());
59            }
60        }
61        projected
62    }
63
64    /// Returns an iterator over the variable-term bindings
65    pub fn iter(&self) -> std::collections::hash_map::Iter<'_, Variable, Term> {
66        self.bindings.iter()
67    }
68
69    /// Returns an iterator over the variables in this solution
70    pub fn variables(&self) -> impl Iterator<Item = &Variable> {
71        self.bindings.keys()
72    }
73}
74
75/// Query results
76#[derive(Debug)]
77pub enum QueryResults {
78    /// Boolean result (for ASK queries)
79    Boolean(bool),
80    /// Solutions (for SELECT queries)
81    Solutions(Vec<Solution>),
82    /// Graph (for CONSTRUCT queries)
83    Graph(Vec<Triple>),
84}
85
86/// Query executor
87pub struct QueryExecutor<'a> {
88    store: &'a dyn Store,
89}
90
91impl<'a> QueryExecutor<'a> {
92    /// Creates a new query executor
93    pub fn new(store: &'a dyn Store) -> Self {
94        QueryExecutor { store }
95    }
96
97    /// Executes a query plan
98    pub fn execute(&self, plan: &ExecutionPlan) -> Result<Vec<Solution>, OxirsError> {
99        self.execute_plan(plan)
100    }
101
102    fn execute_plan(&self, plan: &ExecutionPlan) -> Result<Vec<Solution>, OxirsError> {
103        match plan {
104            ExecutionPlan::TripleScan { pattern } => self.execute_triple_scan(pattern),
105            ExecutionPlan::HashJoin {
106                left,
107                right,
108                join_vars,
109            } => self.execute_hash_join(left, right, join_vars),
110            ExecutionPlan::Filter { input, condition } => self.execute_filter(input, condition),
111            ExecutionPlan::Project { input, vars } => self.execute_project(input, vars),
112            ExecutionPlan::Sort { input, order_by } => self.execute_sort(input, order_by),
113            ExecutionPlan::Limit {
114                input,
115                limit,
116                offset,
117            } => self.execute_limit(input, *limit, *offset),
118            ExecutionPlan::Union { left, right } => self.execute_union(left, right),
119            ExecutionPlan::Distinct { input } => self.execute_distinct(input),
120        }
121    }
122
123    fn execute_triple_scan(
124        &self,
125        pattern: &crate::model::pattern::TriplePattern,
126    ) -> Result<Vec<Solution>, OxirsError> {
127        let mut solutions = Vec::new();
128
129        // Get all triples from the store
130        let triples = self.store.triples()?;
131
132        for triple in triples {
133            if let Some(solution) = self.match_triple_pattern(&triple, pattern) {
134                solutions.push(solution);
135            }
136        }
137
138        Ok(solutions)
139    }
140
141    fn match_triple_pattern(
142        &self,
143        triple: &Triple,
144        pattern: &crate::model::pattern::TriplePattern,
145    ) -> Option<Solution> {
146        let mut solution = Solution::new();
147
148        // Match subject
149        if let Some(ref subject_pattern) = pattern.subject {
150            if !self.match_subject_pattern(triple.subject(), subject_pattern, &mut solution) {
151                return None;
152            }
153        }
154
155        // Match predicate
156        if let Some(ref predicate_pattern) = pattern.predicate {
157            if !self.match_predicate_pattern(triple.predicate(), predicate_pattern, &mut solution) {
158                return None;
159            }
160        }
161
162        // Match object
163        if let Some(ref object_pattern) = pattern.object {
164            if !self.match_object_pattern(triple.object(), object_pattern, &mut solution) {
165                return None;
166            }
167        }
168
169        Some(solution)
170    }
171
172    #[allow(dead_code)]
173    fn match_term_pattern(
174        &self,
175        term: &Term,
176        pattern: &TermPattern,
177        solution: &mut Solution,
178    ) -> bool {
179        match pattern {
180            TermPattern::Variable(var) => {
181                if let Some(bound_value) = solution.get(var) {
182                    bound_value == term
183                } else {
184                    solution.bind(var.clone(), term.clone());
185                    true
186                }
187            }
188            TermPattern::NamedNode(n) => {
189                matches!(term, Term::NamedNode(nn) if nn == n)
190            }
191            TermPattern::BlankNode(b) => {
192                matches!(term, Term::BlankNode(bn) if bn == b)
193            }
194            TermPattern::Literal(l) => {
195                matches!(term, Term::Literal(lit) if lit == l)
196            }
197            TermPattern::QuotedTriple(_) => {
198                panic!("RDF-star quoted triples not yet supported in query execution")
199            }
200        }
201    }
202
203    fn match_subject_pattern(
204        &self,
205        subject: &Subject,
206        pattern: &crate::model::pattern::SubjectPattern,
207        solution: &mut Solution,
208    ) -> bool {
209        use crate::model::pattern::SubjectPattern;
210        match pattern {
211            SubjectPattern::Variable(var) => {
212                if let Some(bound_value) = solution.get(var) {
213                    match (subject, bound_value) {
214                        (Subject::NamedNode(n1), Term::NamedNode(n2)) => n1 == n2,
215                        (Subject::BlankNode(b1), Term::BlankNode(b2)) => b1 == b2,
216                        _ => false,
217                    }
218                } else {
219                    solution
220                        .bindings
221                        .insert(var.clone(), Term::from_subject(subject));
222                    true
223                }
224            }
225            SubjectPattern::NamedNode(n) => matches!(subject, Subject::NamedNode(nn) if nn == n),
226            SubjectPattern::BlankNode(b) => matches!(subject, Subject::BlankNode(bn) if bn == b),
227            // A quoted-triple pattern matches any quoted-triple subject; variable binding
228            // refinement for the inner triple is handled at a higher level.
229            SubjectPattern::QuotedTriple(_) => matches!(subject, Subject::QuotedTriple(_)),
230        }
231    }
232
233    fn match_predicate_pattern(
234        &self,
235        predicate: &Predicate,
236        pattern: &crate::model::pattern::PredicatePattern,
237        solution: &mut Solution,
238    ) -> bool {
239        use crate::model::pattern::PredicatePattern;
240        match pattern {
241            PredicatePattern::Variable(var) => {
242                if let Some(bound_value) = solution.get(var) {
243                    match (predicate, bound_value) {
244                        (Predicate::NamedNode(n1), Term::NamedNode(n2)) => n1 == n2,
245                        _ => false,
246                    }
247                } else {
248                    solution
249                        .bindings
250                        .insert(var.clone(), Term::from_predicate(predicate));
251                    true
252                }
253            }
254            PredicatePattern::NamedNode(n) => {
255                matches!(predicate, Predicate::NamedNode(nn) if nn == n)
256            }
257        }
258    }
259
260    fn match_object_pattern(
261        &self,
262        object: &Object,
263        pattern: &crate::model::pattern::ObjectPattern,
264        solution: &mut Solution,
265    ) -> bool {
266        use crate::model::pattern::ObjectPattern;
267        match pattern {
268            ObjectPattern::Variable(var) => {
269                if let Some(bound_value) = solution.get(var) {
270                    match (object, bound_value) {
271                        (Object::NamedNode(n1), Term::NamedNode(n2)) => n1 == n2,
272                        (Object::BlankNode(b1), Term::BlankNode(b2)) => b1 == b2,
273                        (Object::Literal(l1), Term::Literal(l2)) => l1 == l2,
274                        _ => false,
275                    }
276                } else {
277                    solution
278                        .bindings
279                        .insert(var.clone(), Term::from_object(object));
280                    true
281                }
282            }
283            ObjectPattern::NamedNode(n) => matches!(object, Object::NamedNode(nn) if nn == n),
284            ObjectPattern::BlankNode(b) => matches!(object, Object::BlankNode(bn) if bn == b),
285            ObjectPattern::Literal(l) => matches!(object, Object::Literal(lit) if lit == l),
286            // A quoted-triple pattern matches any quoted-triple object.
287            ObjectPattern::QuotedTriple(_) => matches!(object, Object::QuotedTriple(_)),
288        }
289    }
290
291    fn execute_hash_join(
292        &self,
293        left: &ExecutionPlan,
294        right: &ExecutionPlan,
295        join_vars: &[Variable],
296    ) -> Result<Vec<Solution>, OxirsError> {
297        let left_solutions = self.execute_plan(left)?;
298        let right_solutions = self.execute_plan(right)?;
299
300        let mut results = Vec::new();
301
302        // Build hash table from left solutions
303        let mut hash_table: HashMap<Vec<Term>, Vec<Solution>> = HashMap::new();
304        for solution in left_solutions {
305            let key: Vec<Term> = join_vars
306                .iter()
307                .filter_map(|var| solution.get(var).cloned())
308                .collect();
309            hash_table.entry(key).or_default().push(solution);
310        }
311
312        // Probe with right solutions
313        for right_solution in right_solutions {
314            let key: Vec<Term> = join_vars
315                .iter()
316                .filter_map(|var| right_solution.get(var).cloned())
317                .collect();
318
319            if let Some(left_solutions) = hash_table.get(&key) {
320                for left_solution in left_solutions {
321                    if let Some(merged) = left_solution.merge(&right_solution) {
322                        results.push(merged);
323                    }
324                }
325            }
326        }
327
328        Ok(results)
329    }
330
331    fn execute_filter(
332        &self,
333        input: &ExecutionPlan,
334        condition: &Expression,
335    ) -> Result<Vec<Solution>, OxirsError> {
336        let solutions = self.execute_plan(input)?;
337
338        Ok(solutions
339            .into_iter()
340            .filter(|solution| {
341                self.evaluate_expression(condition, solution)
342                    .unwrap_or(false)
343            })
344            .collect())
345    }
346
347    fn execute_project(
348        &self,
349        input: &ExecutionPlan,
350        vars: &[Variable],
351    ) -> Result<Vec<Solution>, OxirsError> {
352        let solutions = self.execute_plan(input)?;
353
354        Ok(solutions
355            .into_iter()
356            .map(|solution| solution.project(vars))
357            .collect())
358    }
359
360    fn execute_sort(
361        &self,
362        input: &ExecutionPlan,
363        _order_by: &[OrderExpression],
364    ) -> Result<Vec<Solution>, OxirsError> {
365        // Placeholder - would implement proper sorting
366        self.execute_plan(input)
367    }
368
369    fn execute_limit(
370        &self,
371        input: &ExecutionPlan,
372        limit: usize,
373        offset: usize,
374    ) -> Result<Vec<Solution>, OxirsError> {
375        let solutions = self.execute_plan(input)?;
376
377        Ok(solutions.into_iter().skip(offset).take(limit).collect())
378    }
379
380    fn execute_union(
381        &self,
382        left: &ExecutionPlan,
383        right: &ExecutionPlan,
384    ) -> Result<Vec<Solution>, OxirsError> {
385        let mut solutions = self.execute_plan(left)?;
386        solutions.extend(self.execute_plan(right)?);
387        Ok(solutions)
388    }
389
390    fn execute_distinct(&self, input: &ExecutionPlan) -> Result<Vec<Solution>, OxirsError> {
391        let solutions = self.execute_plan(input)?;
392        let mut seen = HashSet::new();
393        let mut distinct_solutions = Vec::new();
394
395        for solution in solutions {
396            if seen.insert(format!("{solution:?}")) {
397                distinct_solutions.push(solution);
398            }
399        }
400
401        Ok(distinct_solutions)
402    }
403
404    fn evaluate_expression(&self, expr: &Expression, solution: &Solution) -> Option<bool> {
405        match expr {
406            Expression::Variable(var) => {
407                if let Some(term) = solution.get(var) {
408                    // Convert term to boolean (non-empty strings and non-zero numbers are true)
409                    match term {
410                        Term::Literal(lit) => {
411                            let value = lit.as_str();
412                            match lit.datatype().as_str() {
413                                "http://www.w3.org/2001/XMLSchema#boolean" => {
414                                    value.parse::<bool>().ok()
415                                }
416                                "http://www.w3.org/2001/XMLSchema#integer"
417                                | "http://www.w3.org/2001/XMLSchema#decimal"
418                                | "http://www.w3.org/2001/XMLSchema#double" => {
419                                    value.parse::<f64>().map(|n| n != 0.0).ok()
420                                }
421                                "http://www.w3.org/2001/XMLSchema#string" => {
422                                    Some(!value.is_empty())
423                                }
424                                _ => Some(!value.is_empty()),
425                            }
426                        }
427                        _ => Some(true), // Non-literal terms are considered true
428                    }
429                } else {
430                    Some(false) // Unbound variables are false
431                }
432            }
433            Expression::Literal(lit) => {
434                let value = lit.as_str();
435                match lit.datatype().as_str() {
436                    "http://www.w3.org/2001/XMLSchema#boolean" => value.parse::<bool>().ok(),
437                    "http://www.w3.org/2001/XMLSchema#integer"
438                    | "http://www.w3.org/2001/XMLSchema#decimal"
439                    | "http://www.w3.org/2001/XMLSchema#double" => {
440                        value.parse::<f64>().map(|n| n != 0.0).ok()
441                    }
442                    _ => Some(!value.is_empty()),
443                }
444            }
445            Expression::And(left, right) => {
446                let left_result = self.evaluate_expression(left, solution)?;
447                let right_result = self.evaluate_expression(right, solution)?;
448                Some(left_result && right_result)
449            }
450            Expression::Or(left, right) => {
451                let left_result = self.evaluate_expression(left, solution)?;
452                let right_result = self.evaluate_expression(right, solution)?;
453                Some(left_result || right_result)
454            }
455            Expression::Not(expr) => {
456                let result = self.evaluate_expression(expr, solution)?;
457                Some(!result)
458            }
459            Expression::Equal(left, right) => {
460                let left_term = self.evaluate_expression_to_term(left, solution)?;
461                let right_term = self.evaluate_expression_to_term(right, solution)?;
462                Some(left_term == right_term)
463            }
464            Expression::NotEqual(left, right) => {
465                let left_term = self.evaluate_expression_to_term(left, solution)?;
466                let right_term = self.evaluate_expression_to_term(right, solution)?;
467                Some(left_term != right_term)
468            }
469            Expression::Less(left, right) => {
470                self.evaluate_numeric_comparison(left, right, solution, |a, b| a < b)
471            }
472            Expression::LessOrEqual(left, right) => {
473                self.evaluate_numeric_comparison(left, right, solution, |a, b| a <= b)
474            }
475            Expression::Greater(left, right) => {
476                self.evaluate_numeric_comparison(left, right, solution, |a, b| a > b)
477            }
478            Expression::GreaterOrEqual(left, right) => {
479                self.evaluate_numeric_comparison(left, right, solution, |a, b| a >= b)
480            }
481            Expression::Bound(var) => Some(solution.get(var).is_some()),
482            Expression::IsIri(expr) => {
483                if let Some(term) = self.evaluate_expression_to_term(expr, solution) {
484                    Some(matches!(term, Term::NamedNode(_)))
485                } else {
486                    Some(false)
487                }
488            }
489            Expression::IsBlank(expr) => {
490                if let Some(term) = self.evaluate_expression_to_term(expr, solution) {
491                    Some(matches!(term, Term::BlankNode(_)))
492                } else {
493                    Some(false)
494                }
495            }
496            Expression::IsLiteral(expr) => {
497                if let Some(term) = self.evaluate_expression_to_term(expr, solution) {
498                    Some(matches!(term, Term::Literal(_)))
499                } else {
500                    Some(false)
501                }
502            }
503            Expression::IsNumeric(expr) => {
504                if let Some(Term::Literal(lit)) = self.evaluate_expression_to_term(expr, solution) {
505                    let datatype_str = lit.datatype().as_str().to_string();
506                    Some(matches!(
507                        datatype_str.as_str(),
508                        "http://www.w3.org/2001/XMLSchema#integer"
509                            | "http://www.w3.org/2001/XMLSchema#decimal"
510                            | "http://www.w3.org/2001/XMLSchema#double"
511                            | "http://www.w3.org/2001/XMLSchema#float"
512                    ))
513                } else {
514                    Some(false)
515                }
516            }
517            Expression::Str(expr) => {
518                // STR() always succeeds, so it's always "true" for filtering purposes
519                Some(self.evaluate_expression_to_term(expr, solution).is_some())
520            }
521            Expression::Regex(text_expr, pattern_expr, flags_expr) => {
522                let text = self.evaluate_expression_to_string(text_expr, solution)?;
523                let pattern = self.evaluate_expression_to_string(pattern_expr, solution)?;
524
525                let flags = if let Some(flags_expr) = flags_expr {
526                    self.evaluate_expression_to_string(flags_expr, solution)
527                        .unwrap_or_default()
528                } else {
529                    String::new()
530                };
531
532                // Basic regex implementation (would need full regex crate for production)
533                if flags.is_empty() {
534                    Some(text.contains(&pattern))
535                } else {
536                    // For now, just do case-insensitive matching if 'i' flag is present
537                    if flags.contains('i') {
538                        Some(text.to_lowercase().contains(&pattern.to_lowercase()))
539                    } else {
540                        Some(text.contains(&pattern))
541                    }
542                }
543            }
544            _ => {
545                // For unsupported expressions, default to true
546                // This is a simplified implementation
547                Some(true)
548            }
549        }
550    }
551
552    /// Evaluate an expression to a term value
553    #[allow(clippy::only_used_in_recursion)]
554    fn evaluate_expression_to_term(&self, expr: &Expression, solution: &Solution) -> Option<Term> {
555        match expr {
556            Expression::Variable(var) => solution.get(var).cloned(),
557            Expression::Term(term) => Some(term.clone()),
558            Expression::FunctionCall(Function::Str, args) => {
559                if let Some(arg) = args.first() {
560                    if let Some(term) = self.evaluate_expression_to_term(arg, solution) {
561                        match term {
562                            Term::NamedNode(n) => Some(Term::Literal(Literal::new(n.as_str()))),
563                            Term::Literal(l) => Some(Term::Literal(Literal::new(l.as_str()))),
564                            Term::BlankNode(b) => Some(Term::Literal(Literal::new(b.as_str()))),
565                            _ => None,
566                        }
567                    } else {
568                        None
569                    }
570                } else {
571                    None
572                }
573            }
574            _ => None, // Other expressions don't directly evaluate to terms
575        }
576    }
577
578    /// Evaluate an expression to a string value
579    fn evaluate_expression_to_string(
580        &self,
581        expr: &Expression,
582        solution: &Solution,
583    ) -> Option<String> {
584        if let Some(term) = self.evaluate_expression_to_term(expr, solution) {
585            match term {
586                Term::NamedNode(n) => Some(n.as_str().to_string()),
587                Term::Literal(l) => Some(l.as_str().to_string()),
588                Term::BlankNode(b) => Some(b.as_str().to_string()),
589                _ => None,
590            }
591        } else {
592            None
593        }
594    }
595
596    /// Evaluate a numeric comparison
597    fn evaluate_numeric_comparison<F>(
598        &self,
599        left: &Expression,
600        right: &Expression,
601        solution: &Solution,
602        comparator: F,
603    ) -> Option<bool>
604    where
605        F: Fn(f64, f64) -> bool,
606    {
607        let left_val = self.evaluate_expression_to_numeric(left, solution)?;
608        let right_val = self.evaluate_expression_to_numeric(right, solution)?;
609        Some(comparator(left_val, right_val))
610    }
611
612    /// Evaluate an expression to a numeric value
613    fn evaluate_expression_to_numeric(
614        &self,
615        expr: &Expression,
616        solution: &Solution,
617    ) -> Option<f64> {
618        if let Some(Term::Literal(lit)) = self.evaluate_expression_to_term(expr, solution) {
619            let value = lit.as_str();
620            match lit.datatype().as_str() {
621                "http://www.w3.org/2001/XMLSchema#integer"
622                | "http://www.w3.org/2001/XMLSchema#decimal"
623                | "http://www.w3.org/2001/XMLSchema#double"
624                | "http://www.w3.org/2001/XMLSchema#float" => value.parse::<f64>().ok(),
625                _ => None,
626            }
627        } else {
628            None
629        }
630    }
631}
632
633impl Default for Solution {
634    fn default() -> Self {
635        Self::new()
636    }
637}
oxirs_core/query/exec.rs

oxirs_core/query/
exec.rs
