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        }
198    }
199
200    fn match_subject_pattern(
201        &self,
202        subject: &Subject,
203        pattern: &crate::model::pattern::SubjectPattern,
204        solution: &mut Solution,
205    ) -> bool {
206        use crate::model::pattern::SubjectPattern;
207        match pattern {
208            SubjectPattern::Variable(var) => {
209                if let Some(bound_value) = solution.get(var) {
210                    match (subject, bound_value) {
211                        (Subject::NamedNode(n1), Term::NamedNode(n2)) => n1 == n2,
212                        (Subject::BlankNode(b1), Term::BlankNode(b2)) => b1 == b2,
213                        _ => false,
214                    }
215                } else {
216                    solution
217                        .bindings
218                        .insert(var.clone(), Term::from_subject(subject));
219                    true
220                }
221            }
222            SubjectPattern::NamedNode(n) => matches!(subject, Subject::NamedNode(nn) if nn == n),
223            SubjectPattern::BlankNode(b) => matches!(subject, Subject::BlankNode(bn) if bn == b),
224        }
225    }
226
227    fn match_predicate_pattern(
228        &self,
229        predicate: &Predicate,
230        pattern: &crate::model::pattern::PredicatePattern,
231        solution: &mut Solution,
232    ) -> bool {
233        use crate::model::pattern::PredicatePattern;
234        match pattern {
235            PredicatePattern::Variable(var) => {
236                if let Some(bound_value) = solution.get(var) {
237                    match (predicate, bound_value) {
238                        (Predicate::NamedNode(n1), Term::NamedNode(n2)) => n1 == n2,
239                        _ => false,
240                    }
241                } else {
242                    solution
243                        .bindings
244                        .insert(var.clone(), Term::from_predicate(predicate));
245                    true
246                }
247            }
248            PredicatePattern::NamedNode(n) => {
249                matches!(predicate, Predicate::NamedNode(nn) if nn == n)
250            }
251        }
252    }
253
254    fn match_object_pattern(
255        &self,
256        object: &Object,
257        pattern: &crate::model::pattern::ObjectPattern,
258        solution: &mut Solution,
259    ) -> bool {
260        use crate::model::pattern::ObjectPattern;
261        match pattern {
262            ObjectPattern::Variable(var) => {
263                if let Some(bound_value) = solution.get(var) {
264                    match (object, bound_value) {
265                        (Object::NamedNode(n1), Term::NamedNode(n2)) => n1 == n2,
266                        (Object::BlankNode(b1), Term::BlankNode(b2)) => b1 == b2,
267                        (Object::Literal(l1), Term::Literal(l2)) => l1 == l2,
268                        _ => false,
269                    }
270                } else {
271                    solution
272                        .bindings
273                        .insert(var.clone(), Term::from_object(object));
274                    true
275                }
276            }
277            ObjectPattern::NamedNode(n) => matches!(object, Object::NamedNode(nn) if nn == n),
278            ObjectPattern::BlankNode(b) => matches!(object, Object::BlankNode(bn) if bn == b),
279            ObjectPattern::Literal(l) => matches!(object, Object::Literal(lit) if lit == l),
280        }
281    }
282
283    fn execute_hash_join(
284        &self,
285        left: &ExecutionPlan,
286        right: &ExecutionPlan,
287        join_vars: &[Variable],
288    ) -> Result<Vec<Solution>, OxirsError> {
289        let left_solutions = self.execute_plan(left)?;
290        let right_solutions = self.execute_plan(right)?;
291
292        let mut results = Vec::new();
293
294        // Build hash table from left solutions
295        let mut hash_table: HashMap<Vec<Term>, Vec<Solution>> = HashMap::new();
296        for solution in left_solutions {
297            let key: Vec<Term> = join_vars
298                .iter()
299                .filter_map(|var| solution.get(var).cloned())
300                .collect();
301            hash_table.entry(key).or_default().push(solution);
302        }
303
304        // Probe with right solutions
305        for right_solution in right_solutions {
306            let key: Vec<Term> = join_vars
307                .iter()
308                .filter_map(|var| right_solution.get(var).cloned())
309                .collect();
310
311            if let Some(left_solutions) = hash_table.get(&key) {
312                for left_solution in left_solutions {
313                    if let Some(merged) = left_solution.merge(&right_solution) {
314                        results.push(merged);
315                    }
316                }
317            }
318        }
319
320        Ok(results)
321    }
322
323    fn execute_filter(
324        &self,
325        input: &ExecutionPlan,
326        condition: &Expression,
327    ) -> Result<Vec<Solution>, OxirsError> {
328        let solutions = self.execute_plan(input)?;
329
330        Ok(solutions
331            .into_iter()
332            .filter(|solution| {
333                self.evaluate_expression(condition, solution)
334                    .unwrap_or(false)
335            })
336            .collect())
337    }
338
339    fn execute_project(
340        &self,
341        input: &ExecutionPlan,
342        vars: &[Variable],
343    ) -> Result<Vec<Solution>, OxirsError> {
344        let solutions = self.execute_plan(input)?;
345
346        Ok(solutions
347            .into_iter()
348            .map(|solution| solution.project(vars))
349            .collect())
350    }
351
352    fn execute_sort(
353        &self,
354        input: &ExecutionPlan,
355        _order_by: &[OrderExpression],
356    ) -> Result<Vec<Solution>, OxirsError> {
357        // Placeholder - would implement proper sorting
358        self.execute_plan(input)
359    }
360
361    fn execute_limit(
362        &self,
363        input: &ExecutionPlan,
364        limit: usize,
365        offset: usize,
366    ) -> Result<Vec<Solution>, OxirsError> {
367        let solutions = self.execute_plan(input)?;
368
369        Ok(solutions.into_iter().skip(offset).take(limit).collect())
370    }
371
372    fn execute_union(
373        &self,
374        left: &ExecutionPlan,
375        right: &ExecutionPlan,
376    ) -> Result<Vec<Solution>, OxirsError> {
377        let mut solutions = self.execute_plan(left)?;
378        solutions.extend(self.execute_plan(right)?);
379        Ok(solutions)
380    }
381
382    fn execute_distinct(&self, input: &ExecutionPlan) -> Result<Vec<Solution>, OxirsError> {
383        let solutions = self.execute_plan(input)?;
384        let mut seen = HashSet::new();
385        let mut distinct_solutions = Vec::new();
386
387        for solution in solutions {
388            if seen.insert(format!("{solution:?}")) {
389                distinct_solutions.push(solution);
390            }
391        }
392
393        Ok(distinct_solutions)
394    }
395
396    fn evaluate_expression(&self, expr: &Expression, solution: &Solution) -> Option<bool> {
397        match expr {
398            Expression::Variable(var) => {
399                if let Some(term) = solution.get(var) {
400                    // Convert term to boolean (non-empty strings and non-zero numbers are true)
401                    match term {
402                        Term::Literal(lit) => {
403                            let value = lit.as_str();
404                            match lit.datatype().as_str() {
405                                "http://www.w3.org/2001/XMLSchema#boolean" => {
406                                    value.parse::<bool>().ok()
407                                }
408                                "http://www.w3.org/2001/XMLSchema#integer"
409                                | "http://www.w3.org/2001/XMLSchema#decimal"
410                                | "http://www.w3.org/2001/XMLSchema#double" => {
411                                    value.parse::<f64>().map(|n| n != 0.0).ok()
412                                }
413                                "http://www.w3.org/2001/XMLSchema#string" => {
414                                    Some(!value.is_empty())
415                                }
416                                _ => Some(!value.is_empty()),
417                            }
418                        }
419                        _ => Some(true), // Non-literal terms are considered true
420                    }
421                } else {
422                    Some(false) // Unbound variables are false
423                }
424            }
425            Expression::Literal(lit) => {
426                let value = lit.as_str();
427                match lit.datatype().as_str() {
428                    "http://www.w3.org/2001/XMLSchema#boolean" => value.parse::<bool>().ok(),
429                    "http://www.w3.org/2001/XMLSchema#integer"
430                    | "http://www.w3.org/2001/XMLSchema#decimal"
431                    | "http://www.w3.org/2001/XMLSchema#double" => {
432                        value.parse::<f64>().map(|n| n != 0.0).ok()
433                    }
434                    _ => Some(!value.is_empty()),
435                }
436            }
437            Expression::And(left, right) => {
438                let left_result = self.evaluate_expression(left, solution)?;
439                let right_result = self.evaluate_expression(right, solution)?;
440                Some(left_result && right_result)
441            }
442            Expression::Or(left, right) => {
443                let left_result = self.evaluate_expression(left, solution)?;
444                let right_result = self.evaluate_expression(right, solution)?;
445                Some(left_result || right_result)
446            }
447            Expression::Not(expr) => {
448                let result = self.evaluate_expression(expr, solution)?;
449                Some(!result)
450            }
451            Expression::Equal(left, right) => {
452                let left_term = self.evaluate_expression_to_term(left, solution)?;
453                let right_term = self.evaluate_expression_to_term(right, solution)?;
454                Some(left_term == right_term)
455            }
456            Expression::NotEqual(left, right) => {
457                let left_term = self.evaluate_expression_to_term(left, solution)?;
458                let right_term = self.evaluate_expression_to_term(right, solution)?;
459                Some(left_term != right_term)
460            }
461            Expression::Less(left, right) => {
462                self.evaluate_numeric_comparison(left, right, solution, |a, b| a < b)
463            }
464            Expression::LessOrEqual(left, right) => {
465                self.evaluate_numeric_comparison(left, right, solution, |a, b| a <= b)
466            }
467            Expression::Greater(left, right) => {
468                self.evaluate_numeric_comparison(left, right, solution, |a, b| a > b)
469            }
470            Expression::GreaterOrEqual(left, right) => {
471                self.evaluate_numeric_comparison(left, right, solution, |a, b| a >= b)
472            }
473            Expression::Bound(var) => Some(solution.get(var).is_some()),
474            Expression::IsIri(expr) => {
475                if let Some(term) = self.evaluate_expression_to_term(expr, solution) {
476                    Some(matches!(term, Term::NamedNode(_)))
477                } else {
478                    Some(false)
479                }
480            }
481            Expression::IsBlank(expr) => {
482                if let Some(term) = self.evaluate_expression_to_term(expr, solution) {
483                    Some(matches!(term, Term::BlankNode(_)))
484                } else {
485                    Some(false)
486                }
487            }
488            Expression::IsLiteral(expr) => {
489                if let Some(term) = self.evaluate_expression_to_term(expr, solution) {
490                    Some(matches!(term, Term::Literal(_)))
491                } else {
492                    Some(false)
493                }
494            }
495            Expression::IsNumeric(expr) => {
496                if let Some(Term::Literal(lit)) = self.evaluate_expression_to_term(expr, solution) {
497                    let datatype_str = lit.datatype().as_str().to_string();
498                    Some(matches!(
499                        datatype_str.as_str(),
500                        "http://www.w3.org/2001/XMLSchema#integer"
501                            | "http://www.w3.org/2001/XMLSchema#decimal"
502                            | "http://www.w3.org/2001/XMLSchema#double"
503                            | "http://www.w3.org/2001/XMLSchema#float"
504                    ))
505                } else {
506                    Some(false)
507                }
508            }
509            Expression::Str(expr) => {
510                // STR() always succeeds, so it's always "true" for filtering purposes
511                Some(self.evaluate_expression_to_term(expr, solution).is_some())
512            }
513            Expression::Regex(text_expr, pattern_expr, flags_expr) => {
514                let text = self.evaluate_expression_to_string(text_expr, solution)?;
515                let pattern = self.evaluate_expression_to_string(pattern_expr, solution)?;
516
517                let flags = if let Some(flags_expr) = flags_expr {
518                    self.evaluate_expression_to_string(flags_expr, solution)
519                        .unwrap_or_default()
520                } else {
521                    String::new()
522                };
523
524                // Basic regex implementation (would need full regex crate for production)
525                if flags.is_empty() {
526                    Some(text.contains(&pattern))
527                } else {
528                    // For now, just do case-insensitive matching if 'i' flag is present
529                    if flags.contains('i') {
530                        Some(text.to_lowercase().contains(&pattern.to_lowercase()))
531                    } else {
532                        Some(text.contains(&pattern))
533                    }
534                }
535            }
536            _ => {
537                // For unsupported expressions, default to true
538                // This is a simplified implementation
539                Some(true)
540            }
541        }
542    }
543
544    /// Evaluate an expression to a term value
545    #[allow(clippy::only_used_in_recursion)]
546    fn evaluate_expression_to_term(&self, expr: &Expression, solution: &Solution) -> Option<Term> {
547        match expr {
548            Expression::Variable(var) => solution.get(var).cloned(),
549            Expression::Term(term) => Some(term.clone()),
550            Expression::FunctionCall(Function::Str, args) => {
551                if let Some(arg) = args.first() {
552                    if let Some(term) = self.evaluate_expression_to_term(arg, solution) {
553                        match term {
554                            Term::NamedNode(n) => Some(Term::Literal(Literal::new(n.as_str()))),
555                            Term::Literal(l) => Some(Term::Literal(Literal::new(l.as_str()))),
556                            Term::BlankNode(b) => Some(Term::Literal(Literal::new(b.as_str()))),
557                            _ => None,
558                        }
559                    } else {
560                        None
561                    }
562                } else {
563                    None
564                }
565            }
566            _ => None, // Other expressions don't directly evaluate to terms
567        }
568    }
569
570    /// Evaluate an expression to a string value
571    fn evaluate_expression_to_string(
572        &self,
573        expr: &Expression,
574        solution: &Solution,
575    ) -> Option<String> {
576        if let Some(term) = self.evaluate_expression_to_term(expr, solution) {
577            match term {
578                Term::NamedNode(n) => Some(n.as_str().to_string()),
579                Term::Literal(l) => Some(l.as_str().to_string()),
580                Term::BlankNode(b) => Some(b.as_str().to_string()),
581                _ => None,
582            }
583        } else {
584            None
585        }
586    }
587
588    /// Evaluate a numeric comparison
589    fn evaluate_numeric_comparison<F>(
590        &self,
591        left: &Expression,
592        right: &Expression,
593        solution: &Solution,
594        comparator: F,
595    ) -> Option<bool>
596    where
597        F: Fn(f64, f64) -> bool,
598    {
599        let left_val = self.evaluate_expression_to_numeric(left, solution)?;
600        let right_val = self.evaluate_expression_to_numeric(right, solution)?;
601        Some(comparator(left_val, right_val))
602    }
603
604    /// Evaluate an expression to a numeric value
605    fn evaluate_expression_to_numeric(
606        &self,
607        expr: &Expression,
608        solution: &Solution,
609    ) -> Option<f64> {
610        if let Some(Term::Literal(lit)) = self.evaluate_expression_to_term(expr, solution) {
611            let value = lit.as_str();
612            match lit.datatype().as_str() {
613                "http://www.w3.org/2001/XMLSchema#integer"
614                | "http://www.w3.org/2001/XMLSchema#decimal"
615                | "http://www.w3.org/2001/XMLSchema#double"
616                | "http://www.w3.org/2001/XMLSchema#float" => value.parse::<f64>().ok(),
617                _ => None,
618            }
619        } else {
620            None
621        }
622    }
623}
624
625impl Default for Solution {
626    fn default() -> Self {
627        Self::new()
628    }
629}
oxirs_core/query/exec.rs

oxirs_core/query/
exec.rs
