reddb_server/storage/query/engine/
op.rs

1//! Algebraic Query Operators
2//!
3//! Jena-inspired operator tree representing query algebra.
4//!
5//! # Operator Hierarchy
6//!
7//! ```text
8//! Op
9//! ├── OpBGP           - Basic Graph Pattern (triple patterns)
10//! ├── OpTriple        - Single triple pattern
11//! ├── OpJoin          - Join two operators
12//! ├── OpLeftJoin      - Left outer join (OPTIONAL)
13//! ├── OpFilter        - Filter with expression
14//! ├── OpUnion         - Union of two operators
15//! ├── OpProject       - Select variables
16//! ├── OpDistinct      - Remove duplicates
17//! ├── OpReduced       - Remove adjacent duplicates
18//! ├── OpSlice         - Offset and limit
19//! ├── OpOrder         - Sort results
20//! ├── OpGroup         - Group by with aggregation
21//! ├── OpExtend        - Assign expression to variable
22//! ├── OpMinus         - Set difference
23//! ├── OpTable         - Inline data
24//! ├── OpSequence      - Sequential execution
25//! ├── OpDisjunction   - OR pattern
26//! └── OpNull          - Empty pattern
27//! ```
28
29use super::binding::{Binding, Value, Var};
30use std::fmt;
31
32/// Triple pattern for graph matching
33#[derive(Debug, Clone, PartialEq, Eq)]
34pub struct Triple {
35    /// Subject
36    pub subject: Pattern,
37    /// Predicate
38    pub predicate: Pattern,
39    /// Object
40    pub object: Pattern,
41}
42
43impl Triple {
44    /// Create new triple pattern
45    pub fn new(subject: Pattern, predicate: Pattern, object: Pattern) -> Self {
46        Self {
47            subject,
48            predicate,
49            object,
50        }
51    }
52
53    /// Get all variables in this triple
54    pub fn vars(&self) -> Vec<Var> {
55        let mut vars = Vec::new();
56        if let Pattern::Var(v) = &self.subject {
57            vars.push(v.clone());
58        }
59        if let Pattern::Var(v) = &self.predicate {
60            vars.push(v.clone());
61        }
62        if let Pattern::Var(v) = &self.object {
63            vars.push(v.clone());
64        }
65        vars
66    }
67
68    /// Check if this triple is concrete (no variables)
69    pub fn is_concrete(&self) -> bool {
70        !matches!(self.subject, Pattern::Var(_))
71            && !matches!(self.predicate, Pattern::Var(_))
72            && !matches!(self.object, Pattern::Var(_))
73    }
74}
75
76impl fmt::Display for Triple {
77    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
78        write!(f, "({} {} {})", self.subject, self.predicate, self.object)
79    }
80}
81
82/// Pattern element (variable or concrete value)
83#[derive(Debug, Clone, PartialEq, Eq)]
84pub enum Pattern {
85    /// Variable
86    Var(Var),
87    /// URI/Node ID
88    Uri(String),
89    /// Literal string
90    Literal(String),
91    /// Literal with datatype
92    TypedLiteral(String, String),
93    /// Any (wildcard)
94    Any,
95}
96
97impl Pattern {
98    /// Check if this is a variable
99    pub fn is_var(&self) -> bool {
100        matches!(self, Pattern::Var(_))
101    }
102
103    /// Get variable if present
104    pub fn as_var(&self) -> Option<&Var> {
105        match self {
106            Pattern::Var(v) => Some(v),
107            _ => None,
108        }
109    }
110
111    /// Convert to Value
112    pub fn to_value(&self) -> Option<Value> {
113        match self {
114            Pattern::Var(_) => None,
115            Pattern::Uri(s) => Some(Value::Uri(s.clone())),
116            Pattern::Literal(s) => Some(Value::String(s.clone())),
117            Pattern::TypedLiteral(v, _) => Some(Value::String(v.clone())),
118            Pattern::Any => None,
119        }
120    }
121}
122
123impl fmt::Display for Pattern {
124    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
125        match self {
126            Pattern::Var(v) => write!(f, "{}", v),
127            Pattern::Uri(s) => write!(f, "<{}>", s),
128            Pattern::Literal(s) => write!(f, "\"{}\"", s),
129            Pattern::TypedLiteral(v, t) => write!(f, "\"{}\"^^<{}>", v, t),
130            Pattern::Any => write!(f, "_"),
131        }
132    }
133}
134
135/// Core algebraic operator type
136#[derive(Debug, Clone)]
137pub enum Op {
138    /// Basic graph pattern (set of triples)
139    BGP(OpBGP),
140    /// Single triple pattern
141    Triple(OpTriple),
142    /// Inner join
143    Join(OpJoin),
144    /// Left outer join (OPTIONAL)
145    LeftJoin(OpLeftJoin),
146    /// Right outer join
147    RightJoin(OpRightJoin),
148    /// Cross join (Cartesian product)
149    CrossJoin(OpCrossJoin),
150    /// Filter
151    Filter(OpFilter),
152    /// Union
153    Union(OpUnion),
154    /// Project to variables
155    Project(OpProject),
156    /// Distinct
157    Distinct(OpDistinct),
158    /// Reduced (remove adjacent duplicates)
159    Reduced(OpReduced),
160    /// Offset/Limit
161    Slice(OpSlice),
162    /// Order by
163    Order(OpOrder),
164    /// Group by
165    Group(OpGroup),
166    /// Extend (bind expression to variable)
167    Extend(OpExtend),
168    /// Set difference
169    Minus(OpMinus),
170    /// Set intersection
171    Intersect(OpIntersect),
172    /// Inline data
173    Table(OpTable),
174    /// Sequential execution
175    Sequence(OpSequence),
176    /// Disjunction (OR patterns)
177    Disjunction(OpDisjunction),
178    /// Empty pattern
179    Null(OpNull),
180}
181
182impl Op {
183    /// Get all variables in this operator
184    pub fn vars(&self) -> Vec<Var> {
185        match self {
186            Op::BGP(op) => op.vars(),
187            Op::Triple(op) => op.triple.vars(),
188            Op::Join(op) => {
189                let mut vars = op.left.vars();
190                for v in op.right.vars() {
191                    if !vars.contains(&v) {
192                        vars.push(v);
193                    }
194                }
195                vars
196            }
197            Op::LeftJoin(op) => {
198                let mut vars = op.left.vars();
199                for v in op.right.vars() {
200                    if !vars.contains(&v) {
201                        vars.push(v);
202                    }
203                }
204                vars
205            }
206            Op::RightJoin(op) => {
207                let mut vars = op.left.vars();
208                for v in op.right.vars() {
209                    if !vars.contains(&v) {
210                        vars.push(v);
211                    }
212                }
213                vars
214            }
215            Op::CrossJoin(op) => {
216                let mut vars = op.left.vars();
217                for v in op.right.vars() {
218                    if !vars.contains(&v) {
219                        vars.push(v);
220                    }
221                }
222                vars
223            }
224            Op::Filter(op) => op.sub_op.vars(),
225            Op::Union(op) => {
226                let mut vars = op.left.vars();
227                for v in op.right.vars() {
228                    if !vars.contains(&v) {
229                        vars.push(v);
230                    }
231                }
232                vars
233            }
234            Op::Project(op) => op.vars.clone(),
235            Op::Distinct(op) => op.sub_op.vars(),
236            Op::Reduced(op) => op.sub_op.vars(),
237            Op::Slice(op) => op.sub_op.vars(),
238            Op::Order(op) => op.sub_op.vars(),
239            Op::Group(op) => {
240                let mut vars = op.group_vars.clone();
241                for (v, _) in &op.aggregates {
242                    vars.push(v.clone());
243                }
244                vars
245            }
246            Op::Extend(op) => {
247                let mut vars = op.sub_op.vars();
248                if !vars.contains(&op.var) {
249                    vars.push(op.var.clone());
250                }
251                vars
252            }
253            Op::Minus(op) => op.left.vars(),
254            Op::Intersect(op) => {
255                // Intersection preserves common variables
256                let left_vars = op.left.vars();
257                let right_vars = op.right.vars();
258                left_vars
259                    .into_iter()
260                    .filter(|v| right_vars.contains(v))
261                    .collect()
262            }
263            Op::Table(op) => op.vars.clone(),
264            Op::Sequence(op) => {
265                let mut vars = Vec::new();
266                for sub in &op.ops {
267                    for v in sub.vars() {
268                        if !vars.contains(&v) {
269                            vars.push(v);
270                        }
271                    }
272                }
273                vars
274            }
275            Op::Disjunction(op) => {
276                let mut vars = Vec::new();
277                for sub in &op.ops {
278                    for v in sub.vars() {
279                        if !vars.contains(&v) {
280                            vars.push(v);
281                        }
282                    }
283                }
284                vars
285            }
286            Op::Null(_) => Vec::new(),
287        }
288    }
289
290    /// Check if this operator is a null/empty pattern
291    pub fn is_null(&self) -> bool {
292        matches!(self, Op::Null(_))
293    }
294}
295
296/// Basic Graph Pattern - set of triple patterns
297#[derive(Debug, Clone)]
298pub struct OpBGP {
299    /// Triple patterns
300    pub triples: Vec<Triple>,
301}
302
303impl OpBGP {
304    /// Create empty BGP
305    pub fn new() -> Self {
306        Self {
307            triples: Vec::new(),
308        }
309    }
310
311    /// Create from triples
312    pub fn from_triples(triples: Vec<Triple>) -> Self {
313        Self { triples }
314    }
315
316    /// Add triple
317    pub fn add(&mut self, triple: Triple) {
318        self.triples.push(triple);
319    }
320
321    /// Get all variables
322    pub fn vars(&self) -> Vec<Var> {
323        let mut vars = Vec::new();
324        for triple in &self.triples {
325            for v in triple.vars() {
326                if !vars.contains(&v) {
327                    vars.push(v);
328                }
329            }
330        }
331        vars
332    }
333
334    /// Check if empty
335    pub fn is_empty(&self) -> bool {
336        self.triples.is_empty()
337    }
338}
339
340impl Default for OpBGP {
341    fn default() -> Self {
342        Self::new()
343    }
344}
345
346/// Single triple pattern
347#[derive(Debug, Clone)]
348pub struct OpTriple {
349    pub triple: Triple,
350}
351
352impl OpTriple {
353    /// Create new triple op
354    pub fn new(triple: Triple) -> Self {
355        Self { triple }
356    }
357}
358
359/// Join two operators
360#[derive(Debug, Clone)]
361pub struct OpJoin {
362    pub left: Box<Op>,
363    pub right: Box<Op>,
364}
365
366impl OpJoin {
367    /// Create join
368    pub fn new(left: Op, right: Op) -> Self {
369        Self {
370            left: Box::new(left),
371            right: Box::new(right),
372        }
373    }
374
375    /// Create from multiple ops (left-associative join chain)
376    pub fn join_all(ops: Vec<Op>) -> Op {
377        if ops.is_empty() {
378            return Op::Null(OpNull);
379        }
380
381        let mut result = ops.into_iter();
382        let mut current = result.next().unwrap();
383
384        for op in result {
385            current = Op::Join(OpJoin::new(current, op));
386        }
387
388        current
389    }
390}
391
392/// Left outer join (OPTIONAL)
393#[derive(Debug, Clone)]
394pub struct OpLeftJoin {
395    pub left: Box<Op>,
396    pub right: Box<Op>,
397    /// Filter expression for the join
398    pub filter: Option<FilterExpr>,
399}
400
401impl OpLeftJoin {
402    /// Create left join
403    pub fn new(left: Op, right: Op) -> Self {
404        Self {
405            left: Box::new(left),
406            right: Box::new(right),
407            filter: None,
408        }
409    }
410
411    /// Create with filter
412    pub fn with_filter(left: Op, right: Op, filter: FilterExpr) -> Self {
413        Self {
414            left: Box::new(left),
415            right: Box::new(right),
416            filter: Some(filter),
417        }
418    }
419}
420
421/// Right outer join
422#[derive(Debug, Clone)]
423pub struct OpRightJoin {
424    pub left: Box<Op>,
425    pub right: Box<Op>,
426    /// Filter expression for the join
427    pub filter: Option<FilterExpr>,
428}
429
430impl OpRightJoin {
431    /// Create right join
432    pub fn new(left: Op, right: Op) -> Self {
433        Self {
434            left: Box::new(left),
435            right: Box::new(right),
436            filter: None,
437        }
438    }
439
440    /// Create with filter
441    pub fn with_filter(left: Op, right: Op, filter: FilterExpr) -> Self {
442        Self {
443            left: Box::new(left),
444            right: Box::new(right),
445            filter: Some(filter),
446        }
447    }
448}
449
450/// Cross join (Cartesian product)
451#[derive(Debug, Clone)]
452pub struct OpCrossJoin {
453    pub left: Box<Op>,
454    pub right: Box<Op>,
455}
456
457impl OpCrossJoin {
458    /// Create cross join
459    pub fn new(left: Op, right: Op) -> Self {
460        Self {
461            left: Box::new(left),
462            right: Box::new(right),
463        }
464    }
465}
466
467/// Filter expression for filtering bindings
468#[derive(Debug, Clone)]
469pub enum FilterExpr {
470    /// Equality
471    Eq(ExprTerm, ExprTerm),
472    /// Not equal
473    NotEq(ExprTerm, ExprTerm),
474    /// Less than
475    Lt(ExprTerm, ExprTerm),
476    /// Less than or equal
477    LtEq(ExprTerm, ExprTerm),
478    /// Greater than
479    Gt(ExprTerm, ExprTerm),
480    /// Greater than or equal
481    GtEq(ExprTerm, ExprTerm),
482    /// Logical AND
483    And(Box<FilterExpr>, Box<FilterExpr>),
484    /// Logical OR
485    Or(Box<FilterExpr>, Box<FilterExpr>),
486    /// Logical NOT
487    Not(Box<FilterExpr>),
488    /// Bound check
489    Bound(Var),
490    /// Regex match
491    Regex(ExprTerm, String, Option<String>),
492    /// String starts with
493    StartsWith(ExprTerm, String),
494    /// String ends with
495    EndsWith(ExprTerm, String),
496    /// String contains
497    Contains(ExprTerm, String),
498    /// Is IRI
499    IsUri(ExprTerm),
500    /// Is literal
501    IsLiteral(ExprTerm),
502    /// Is blank node
503    IsBlank(ExprTerm),
504    /// In list
505    In(ExprTerm, Vec<ExprTerm>),
506    /// Not in list
507    NotIn(ExprTerm, Vec<ExprTerm>),
508    /// True constant
509    True,
510    /// False constant
511    False,
512}
513
514impl FilterExpr {
515    /// Create AND expression
516    pub fn and(left: FilterExpr, right: FilterExpr) -> FilterExpr {
517        FilterExpr::And(Box::new(left), Box::new(right))
518    }
519
520    /// Create OR expression
521    pub fn or(left: FilterExpr, right: FilterExpr) -> FilterExpr {
522        FilterExpr::Or(Box::new(left), Box::new(right))
523    }
524
525    /// Create NOT expression
526    pub fn not(expr: FilterExpr) -> FilterExpr {
527        FilterExpr::Not(Box::new(expr))
528    }
529
530    /// Evaluate against a binding
531    pub fn evaluate(&self, binding: &Binding) -> bool {
532        match self {
533            FilterExpr::Eq(left, right) => {
534                let l = left.evaluate(binding);
535                let r = right.evaluate(binding);
536                l == r
537            }
538            FilterExpr::NotEq(left, right) => {
539                let l = left.evaluate(binding);
540                let r = right.evaluate(binding);
541                l != r
542            }
543            FilterExpr::Lt(left, right) => compare_terms(left, right, binding, |a, b| a < b),
544            FilterExpr::LtEq(left, right) => compare_terms(left, right, binding, |a, b| a <= b),
545            FilterExpr::Gt(left, right) => compare_terms(left, right, binding, |a, b| a > b),
546            FilterExpr::GtEq(left, right) => compare_terms(left, right, binding, |a, b| a >= b),
547            FilterExpr::And(left, right) => left.evaluate(binding) && right.evaluate(binding),
548            FilterExpr::Or(left, right) => left.evaluate(binding) || right.evaluate(binding),
549            FilterExpr::Not(expr) => !expr.evaluate(binding),
550            FilterExpr::Bound(var) => binding.contains(var),
551            FilterExpr::Regex(term, pattern, flags) => {
552                if let Some(Value::String(s)) = term.evaluate(binding) {
553                    // Simple regex matching (production would use regex crate)
554                    let case_insensitive = flags.as_ref().map(|f| f.contains('i')).unwrap_or(false);
555                    if case_insensitive {
556                        s.to_lowercase().contains(&pattern.to_lowercase())
557                    } else {
558                        s.contains(pattern)
559                    }
560                } else {
561                    false
562                }
563            }
564            FilterExpr::StartsWith(term, prefix) => {
565                if let Some(Value::String(s)) = term.evaluate(binding) {
566                    s.starts_with(prefix)
567                } else {
568                    false
569                }
570            }
571            FilterExpr::EndsWith(term, suffix) => {
572                if let Some(Value::String(s)) = term.evaluate(binding) {
573                    s.ends_with(suffix)
574                } else {
575                    false
576                }
577            }
578            FilterExpr::Contains(term, substring) => {
579                if let Some(Value::String(s)) = term.evaluate(binding) {
580                    s.contains(substring)
581                } else {
582                    false
583                }
584            }
585            FilterExpr::IsUri(term) => {
586                matches!(term.evaluate(binding), Some(Value::Uri(_)))
587            }
588            FilterExpr::IsLiteral(term) => {
589                matches!(
590                    term.evaluate(binding),
591                    Some(
592                        Value::String(_) | Value::Integer(_) | Value::Float(_) | Value::Boolean(_)
593                    )
594                )
595            }
596            FilterExpr::IsBlank(term) => {
597                if let Some(Value::Node(id)) = term.evaluate(binding) {
598                    id.starts_with("_:")
599                } else {
600                    false
601                }
602            }
603            FilterExpr::In(term, list) => {
604                if let Some(val) = term.evaluate(binding) {
605                    list.iter()
606                        .any(|t| t.evaluate(binding) == Some(val.clone()))
607                } else {
608                    false
609                }
610            }
611            FilterExpr::NotIn(term, list) => {
612                if let Some(val) = term.evaluate(binding) {
613                    !list
614                        .iter()
615                        .any(|t| t.evaluate(binding) == Some(val.clone()))
616                } else {
617                    true
618                }
619            }
620            FilterExpr::True => true,
621            FilterExpr::False => false,
622        }
623    }
624}
625
626/// Compare two terms with a comparison function
627fn compare_terms<F>(left: &ExprTerm, right: &ExprTerm, binding: &Binding, cmp: F) -> bool
628where
629    F: Fn(i64, i64) -> bool,
630{
631    match (left.evaluate(binding), right.evaluate(binding)) {
632        (Some(Value::Integer(a)), Some(Value::Integer(b))) => cmp(a, b),
633        (Some(Value::Float(a)), Some(Value::Float(b))) => cmp(a as i64, b as i64),
634        (Some(Value::Integer(a)), Some(Value::Float(b))) => cmp(a, b as i64),
635        (Some(Value::Float(a)), Some(Value::Integer(b))) => cmp(a as i64, b),
636        _ => false,
637    }
638}
639
640/// Expression term
641#[derive(Debug, Clone, PartialEq)]
642pub enum ExprTerm {
643    /// Variable reference
644    Var(Var),
645    /// Constant value
646    Const(Value),
647    /// String function result
648    Str(Box<ExprTerm>),
649    /// Lowercase
650    LCase(Box<ExprTerm>),
651    /// Uppercase
652    UCase(Box<ExprTerm>),
653    /// String length
654    StrLen(Box<ExprTerm>),
655    /// Concatenation
656    Concat(Vec<ExprTerm>),
657}
658
659impl ExprTerm {
660    /// Evaluate term against binding
661    pub fn evaluate(&self, binding: &Binding) -> Option<Value> {
662        match self {
663            ExprTerm::Var(var) => binding.get(var).cloned(),
664            ExprTerm::Const(val) => Some(val.clone()),
665            ExprTerm::Str(inner) => inner
666                .evaluate(binding)
667                .map(|v| Value::String(format!("{}", v))),
668            ExprTerm::LCase(inner) => {
669                if let Some(Value::String(s)) = inner.evaluate(binding) {
670                    Some(Value::String(s.to_lowercase()))
671                } else {
672                    None
673                }
674            }
675            ExprTerm::UCase(inner) => {
676                if let Some(Value::String(s)) = inner.evaluate(binding) {
677                    Some(Value::String(s.to_uppercase()))
678                } else {
679                    None
680                }
681            }
682            ExprTerm::StrLen(inner) => {
683                if let Some(Value::String(s)) = inner.evaluate(binding) {
684                    Some(Value::Integer(s.len() as i64))
685                } else {
686                    None
687                }
688            }
689            ExprTerm::Concat(terms) => {
690                let mut result = String::new();
691                for term in terms {
692                    if let Some(Value::String(s)) = term.evaluate(binding) {
693                        result.push_str(&s);
694                    } else if let Some(v) = term.evaluate(binding) {
695                        result.push_str(&format!("{}", v));
696                    }
697                }
698                Some(Value::String(result))
699            }
700        }
701    }
702}
703
704/// Filter operator
705#[derive(Debug, Clone)]
706pub struct OpFilter {
707    pub filter: FilterExpr,
708    pub sub_op: Box<Op>,
709}
710
711impl OpFilter {
712    /// Create filter
713    pub fn new(filter: FilterExpr, sub_op: Op) -> Self {
714        Self {
715            filter,
716            sub_op: Box::new(sub_op),
717        }
718    }
719}
720
721/// Union operator
722#[derive(Debug, Clone)]
723pub struct OpUnion {
724    pub left: Box<Op>,
725    pub right: Box<Op>,
726}
727
728impl OpUnion {
729    /// Create union
730    pub fn new(left: Op, right: Op) -> Self {
731        Self {
732            left: Box::new(left),
733            right: Box::new(right),
734        }
735    }
736}
737
738/// Project operator
739#[derive(Debug, Clone)]
740pub struct OpProject {
741    pub vars: Vec<Var>,
742    pub sub_op: Box<Op>,
743}
744
745impl OpProject {
746    /// Create project
747    pub fn new(vars: Vec<Var>, sub_op: Op) -> Self {
748        Self {
749            vars,
750            sub_op: Box::new(sub_op),
751        }
752    }
753}
754
755/// Distinct operator
756#[derive(Debug, Clone)]
757pub struct OpDistinct {
758    pub sub_op: Box<Op>,
759}
760
761impl OpDistinct {
762    /// Create distinct
763    pub fn new(sub_op: Op) -> Self {
764        Self {
765            sub_op: Box::new(sub_op),
766        }
767    }
768}
769
770/// Reduced operator (adjacent duplicate removal)
771#[derive(Debug, Clone)]
772pub struct OpReduced {
773    pub sub_op: Box<Op>,
774}
775
776impl OpReduced {
777    /// Create reduced
778    pub fn new(sub_op: Op) -> Self {
779        Self {
780            sub_op: Box::new(sub_op),
781        }
782    }
783}
784
785/// Slice operator (offset/limit)
786#[derive(Debug, Clone)]
787pub struct OpSlice {
788    pub sub_op: Box<Op>,
789    pub offset: u64,
790    pub limit: Option<u64>,
791}
792
793impl OpSlice {
794    /// Create slice
795    pub fn new(sub_op: Op, offset: u64, limit: Option<u64>) -> Self {
796        Self {
797            sub_op: Box::new(sub_op),
798            offset,
799            limit,
800        }
801    }
802
803    /// Create limit only
804    pub fn limit(sub_op: Op, limit: u64) -> Self {
805        Self::new(sub_op, 0, Some(limit))
806    }
807
808    /// Create offset only
809    pub fn offset(sub_op: Op, offset: u64) -> Self {
810        Self::new(sub_op, offset, None)
811    }
812}
813
814/// Order key
815#[derive(Debug, Clone)]
816pub struct OrderKey {
817    pub expr: ExprTerm,
818    pub ascending: bool,
819}
820
821impl OrderKey {
822    /// Create ascending key
823    pub fn asc(expr: ExprTerm) -> Self {
824        Self {
825            expr,
826            ascending: true,
827        }
828    }
829
830    /// Create descending key
831    pub fn desc(expr: ExprTerm) -> Self {
832        Self {
833            expr,
834            ascending: false,
835        }
836    }
837}
838
839/// Order operator
840#[derive(Debug, Clone)]
841pub struct OpOrder {
842    pub sub_op: Box<Op>,
843    pub keys: Vec<OrderKey>,
844}
845
846impl OpOrder {
847    /// Create order
848    pub fn new(sub_op: Op, keys: Vec<OrderKey>) -> Self {
849        Self {
850            sub_op: Box::new(sub_op),
851            keys,
852        }
853    }
854}
855
856/// Aggregate function
857#[derive(Debug, Clone)]
858pub enum Aggregate {
859    Count(Option<ExprTerm>),
860    CountDistinct(ExprTerm),
861    Sum(ExprTerm),
862    Avg(ExprTerm),
863    Min(ExprTerm),
864    Max(ExprTerm),
865    Sample(ExprTerm),
866    GroupConcat(ExprTerm, Option<String>),
867}
868
869/// Group operator
870#[derive(Debug, Clone)]
871pub struct OpGroup {
872    pub sub_op: Box<Op>,
873    pub group_vars: Vec<Var>,
874    pub aggregates: Vec<(Var, Aggregate)>,
875}
876
877impl OpGroup {
878    /// Create group
879    pub fn new(sub_op: Op, group_vars: Vec<Var>) -> Self {
880        Self {
881            sub_op: Box::new(sub_op),
882            group_vars,
883            aggregates: Vec::new(),
884        }
885    }
886
887    /// Add aggregate
888    pub fn with_aggregate(mut self, var: Var, agg: Aggregate) -> Self {
889        self.aggregates.push((var, agg));
890        self
891    }
892}
893
894/// Extend operator (bind expression to variable)
895#[derive(Debug, Clone)]
896pub struct OpExtend {
897    pub sub_op: Box<Op>,
898    pub var: Var,
899    pub expr: ExprTerm,
900}
901
902impl OpExtend {
903    /// Create extend
904    pub fn new(sub_op: Op, var: Var, expr: ExprTerm) -> Self {
905        Self {
906            sub_op: Box::new(sub_op),
907            var,
908            expr,
909        }
910    }
911}
912
913/// Minus operator (set difference)
914#[derive(Debug, Clone)]
915pub struct OpMinus {
916    pub left: Box<Op>,
917    pub right: Box<Op>,
918}
919
920impl OpMinus {
921    /// Create minus
922    pub fn new(left: Op, right: Op) -> Self {
923        Self {
924            left: Box::new(left),
925            right: Box::new(right),
926        }
927    }
928}
929
930/// Intersect operator (set intersection)
931#[derive(Debug, Clone)]
932pub struct OpIntersect {
933    pub left: Box<Op>,
934    pub right: Box<Op>,
935}
936
937impl OpIntersect {
938    /// Create intersect
939    pub fn new(left: Op, right: Op) -> Self {
940        Self {
941            left: Box::new(left),
942            right: Box::new(right),
943        }
944    }
945}
946
947/// Table operator (inline data VALUES)
948#[derive(Debug, Clone)]
949pub struct OpTable {
950    pub vars: Vec<Var>,
951    pub rows: Vec<Vec<Option<Value>>>,
952}
953
954impl OpTable {
955    /// Create table
956    pub fn new(vars: Vec<Var>, rows: Vec<Vec<Option<Value>>>) -> Self {
957        Self { vars, rows }
958    }
959
960    /// Create empty table
961    pub fn empty() -> Self {
962        Self {
963            vars: Vec::new(),
964            rows: Vec::new(),
965        }
966    }
967
968    /// Create single-row table
969    pub fn unit() -> Self {
970        Self {
971            vars: Vec::new(),
972            rows: vec![vec![]],
973        }
974    }
975}
976
977/// Sequence operator
978#[derive(Debug, Clone)]
979pub struct OpSequence {
980    pub ops: Vec<Op>,
981}
982
983impl OpSequence {
984    /// Create sequence
985    pub fn new(ops: Vec<Op>) -> Self {
986        Self { ops }
987    }
988}
989
990/// Disjunction operator (OR patterns)
991#[derive(Debug, Clone)]
992pub struct OpDisjunction {
993    pub ops: Vec<Op>,
994}
995
996impl OpDisjunction {
997    /// Create disjunction
998    pub fn new(ops: Vec<Op>) -> Self {
999        Self { ops }
1000    }
1001}
1002
1003/// Null operator (empty pattern)
1004#[derive(Debug, Clone, Copy)]
1005pub struct OpNull;
1006
1007impl OpNull {
1008    /// Create null op
1009    pub fn new() -> Self {
1010        Self
1011    }
1012}
1013
1014impl Default for OpNull {
1015    fn default() -> Self {
1016        Self::new()
1017    }
1018}
1019
1020#[cfg(test)]
1021mod tests {
1022    use super::*;
1023
1024    #[test]
1025    fn test_triple_pattern() {
1026        let triple = Triple::new(
1027            Pattern::Var(Var::new("s")),
1028            Pattern::Uri("http://example.org/knows".to_string()),
1029            Pattern::Var(Var::new("o")),
1030        );
1031
1032        assert_eq!(triple.vars().len(), 2);
1033        assert!(!triple.is_concrete());
1034    }
1035
1036    #[test]
1037    fn test_bgp() {
1038        let mut bgp = OpBGP::new();
1039        bgp.add(Triple::new(
1040            Pattern::Var(Var::new("s")),
1041            Pattern::Uri("http://example.org/name".to_string()),
1042            Pattern::Var(Var::new("name")),
1043        ));
1044        bgp.add(Triple::new(
1045            Pattern::Var(Var::new("s")),
1046            Pattern::Uri("http://example.org/age".to_string()),
1047            Pattern::Var(Var::new("age")),
1048        ));
1049
1050        assert_eq!(bgp.triples.len(), 2);
1051        assert_eq!(bgp.vars().len(), 3); // s, name, age
1052    }
1053
1054    #[test]
1055    fn test_filter_expr() {
1056        let binding = Binding::one(Var::new("x"), Value::Integer(10));
1057
1058        let expr = FilterExpr::Gt(
1059            ExprTerm::Var(Var::new("x")),
1060            ExprTerm::Const(Value::Integer(5)),
1061        );
1062
1063        assert!(expr.evaluate(&binding));
1064
1065        let expr2 = FilterExpr::Lt(
1066            ExprTerm::Var(Var::new("x")),
1067            ExprTerm::Const(Value::Integer(5)),
1068        );
1069
1070        assert!(!expr2.evaluate(&binding));
1071    }
1072
1073    #[test]
1074    fn test_filter_and_or() {
1075        let binding = Binding::two(
1076            Var::new("x"),
1077            Value::Integer(10),
1078            Var::new("y"),
1079            Value::Integer(20),
1080        );
1081
1082        let expr = FilterExpr::and(
1083            FilterExpr::Gt(
1084                ExprTerm::Var(Var::new("x")),
1085                ExprTerm::Const(Value::Integer(5)),
1086            ),
1087            FilterExpr::Lt(
1088                ExprTerm::Var(Var::new("y")),
1089                ExprTerm::Const(Value::Integer(30)),
1090            ),
1091        );
1092
1093        assert!(expr.evaluate(&binding));
1094    }
1095
1096    #[test]
1097    fn test_join_all() {
1098        let op1 = Op::BGP(OpBGP::new());
1099        let op2 = Op::BGP(OpBGP::new());
1100        let op3 = Op::BGP(OpBGP::new());
1101
1102        let joined = OpJoin::join_all(vec![op1, op2, op3]);
1103        assert!(matches!(joined, Op::Join(_)));
1104    }
1105
1106    #[test]
1107    fn test_op_vars() {
1108        let mut bgp = OpBGP::new();
1109        bgp.add(Triple::new(
1110            Pattern::Var(Var::new("s")),
1111            Pattern::Uri("pred".to_string()),
1112            Pattern::Var(Var::new("o")),
1113        ));
1114
1115        let filter = Op::Filter(OpFilter::new(FilterExpr::True, Op::BGP(bgp)));
1116
1117        let vars = filter.vars();
1118        assert!(vars.contains(&Var::new("s")));
1119        assert!(vars.contains(&Var::new("o")));
1120    }
1121
1122    #[test]
1123    fn test_table_op() {
1124        let table = OpTable::new(
1125            vec![Var::new("x"), Var::new("y")],
1126            vec![
1127                vec![Some(Value::Integer(1)), Some(Value::Integer(2))],
1128                vec![Some(Value::Integer(3)), None],
1129            ],
1130        );
1131
1132        assert_eq!(table.vars.len(), 2);
1133        assert_eq!(table.rows.len(), 2);
1134    }
1135
1136    #[test]
1137    fn test_string_functions() {
1138        let binding = Binding::one(Var::new("s"), Value::String("Hello World".to_string()));
1139
1140        let lower = ExprTerm::LCase(Box::new(ExprTerm::Var(Var::new("s"))));
1141        assert_eq!(
1142            lower.evaluate(&binding),
1143            Some(Value::String("hello world".to_string()))
1144        );
1145
1146        let upper = ExprTerm::UCase(Box::new(ExprTerm::Var(Var::new("s"))));
1147        assert_eq!(
1148            upper.evaluate(&binding),
1149            Some(Value::String("HELLO WORLD".to_string()))
1150        );
1151
1152        let len = ExprTerm::StrLen(Box::new(ExprTerm::Var(Var::new("s"))));
1153        assert_eq!(len.evaluate(&binding), Some(Value::Integer(11)));
1154    }
1155}
reddb_server/storage/query/engine/op.rs

reddb_server/storage/query/engine/
op.rs
