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

oxirs_core/query/
exec.rs
