sparopt/
algebra.rs

1//! [SPARQL 1.1 Query Algebra](https://www.w3.org/TR/sparql11-query/#sparqlQuery) representation.
2
3use oxrdf::vocab::xsd;
4use rand::random;
5use spargebra::algebra::{
6    AggregateExpression as AlAggregateExpression, AggregateFunction, Expression as AlExpression,
7    GraphPattern as AlGraphPattern, OrderExpression as AlOrderExpression,
8};
9pub use spargebra::algebra::{Function, PropertyPathExpression};
10use spargebra::term::{BlankNode, TermPattern, TriplePattern};
11pub use spargebra::term::{
12    GroundTerm, GroundTermPattern, Literal, NamedNode, NamedNodePattern, Variable,
13};
14#[cfg(feature = "sparql-12")]
15use spargebra::term::{GroundTriple, GroundTriplePattern};
16use std::collections::hash_map::DefaultHasher;
17use std::collections::{HashMap, HashSet};
18use std::hash::{Hash, Hasher};
19use std::ops::{Add, BitAnd, BitOr, Div, Mul, Neg, Not, Sub};
20
21/// An [expression](https://www.w3.org/TR/sparql11-query/#expressions).
22#[derive(Eq, PartialEq, Debug, Clone, Hash)]
23pub enum Expression {
24    NamedNode(NamedNode),
25    Literal(Literal),
26    Variable(Variable),
27    /// [Logical-or](https://www.w3.org/TR/sparql11-query/#func-logical-or).
28    Or(Vec<Self>),
29    /// [Logical-and](https://www.w3.org/TR/sparql11-query/#func-logical-and).
30    And(Vec<Self>),
31    /// [RDFterm-equal](https://www.w3.org/TR/sparql11-query/#func-RDFterm-equal) and all the XSD equalities.
32    Equal(Box<Self>, Box<Self>),
33    /// [sameTerm](https://www.w3.org/TR/sparql11-query/#func-sameTerm).
34    SameTerm(Box<Self>, Box<Self>),
35    /// [op:numeric-greater-than](https://www.w3.org/TR/xpath-functions-31/#func-numeric-greater-than) and other XSD greater than operators.
36    Greater(Box<Self>, Box<Self>),
37    GreaterOrEqual(Box<Self>, Box<Self>),
38    /// [op:numeric-less-than](https://www.w3.org/TR/xpath-functions-31/#func-numeric-less-than) and other XSD greater than operators.
39    Less(Box<Self>, Box<Self>),
40    LessOrEqual(Box<Self>, Box<Self>),
41    /// [op:numeric-add](https://www.w3.org/TR/xpath-functions-31/#func-numeric-add) and other XSD additions.
42    Add(Box<Self>, Box<Self>),
43    /// [op:numeric-subtract](https://www.w3.org/TR/xpath-functions-31/#func-numeric-subtract) and other XSD subtractions.
44    Subtract(Box<Self>, Box<Self>),
45    /// [op:numeric-multiply](https://www.w3.org/TR/xpath-functions-31/#func-numeric-multiply) and other XSD multiplications.
46    Multiply(Box<Self>, Box<Self>),
47    /// [op:numeric-divide](https://www.w3.org/TR/xpath-functions-31/#func-numeric-divide) and other XSD divides.
48    Divide(Box<Self>, Box<Self>),
49    /// [op:numeric-unary-plus](https://www.w3.org/TR/xpath-functions-31/#func-numeric-unary-plus) and other XSD unary plus.
50    UnaryPlus(Box<Self>),
51    /// [op:numeric-unary-minus](https://www.w3.org/TR/xpath-functions-31/#func-numeric-unary-minus) and other XSD unary minus.
52    UnaryMinus(Box<Self>),
53    /// [fn:not](https://www.w3.org/TR/xpath-functions-31/#func-not).
54    Not(Box<Self>),
55    /// [EXISTS](https://www.w3.org/TR/sparql11-query/#func-filter-exists).
56    Exists(Box<GraphPattern>),
57    /// [BOUND](https://www.w3.org/TR/sparql11-query/#func-bound).
58    Bound(Variable),
59    /// [IF](https://www.w3.org/TR/sparql11-query/#func-if).
60    If(Box<Self>, Box<Self>, Box<Self>),
61    /// [COALESCE](https://www.w3.org/TR/sparql11-query/#func-coalesce).
62    Coalesce(Vec<Self>),
63    /// A regular function call.
64    FunctionCall(Function, Vec<Self>),
65}
66
67impl Expression {
68    pub fn or_all(args: impl IntoIterator<Item = Self>) -> Self {
69        let args = args.into_iter();
70        let mut all = Vec::with_capacity(args.size_hint().0);
71        for arg in args {
72            if let Some(ebv) = arg.effective_boolean_value() {
73                if ebv {
74                    return true.into();
75                }
76                // We ignore false values
77            } else if let Self::Or(args) = arg {
78                all.extend(args);
79            } else {
80                all.push(arg);
81            }
82        }
83        match all.len() {
84            0 => false.into(),
85            1 => {
86                let result = all.pop().unwrap();
87                if result.returns_boolean() {
88                    result // It's already casted to boolean
89                } else {
90                    Self::And(vec![result])
91                }
92            }
93            _ => Self::Or(order_vec(all)),
94        }
95    }
96
97    pub fn and_all(args: impl IntoIterator<Item = Self>) -> Self {
98        let args = args.into_iter();
99        let mut all = Vec::with_capacity(args.size_hint().0);
100        for arg in args {
101            if let Some(ebv) = arg.effective_boolean_value() {
102                if !ebv {
103                    return false.into();
104                }
105                // We ignore true values
106            } else if let Self::And(args) = arg {
107                all.extend(args);
108            } else {
109                all.push(arg);
110            }
111        }
112        match all.len() {
113            0 => true.into(),
114            1 => {
115                let result = all.pop().unwrap();
116                if result.returns_boolean() {
117                    result
118                } else {
119                    Self::And(vec![result])
120                }
121            }
122            _ => Self::And(order_vec(all)),
123        }
124    }
125
126    pub fn equal(left: Self, right: Self) -> Self {
127        match (left, right) {
128            (Self::NamedNode(left), Self::NamedNode(right)) => (left == right).into(),
129            (Self::Literal(left), Self::Literal(right)) if left == right => true.into(),
130            (left, right) => {
131                let (left, right) = order_pair(left, right);
132                Self::Equal(Box::new(left), Box::new(right))
133            }
134        }
135    }
136
137    pub fn same_term(left: Self, right: Self) -> Self {
138        match (left, right) {
139            (Self::NamedNode(left), Self::NamedNode(right)) => (left == right).into(),
140            (Self::Literal(left), Self::Literal(right)) if left == right => true.into(),
141            (left, right) => {
142                let (left, right) = order_pair(left, right);
143                Self::SameTerm(Box::new(left), Box::new(right))
144            }
145        }
146    }
147
148    pub fn greater(left: Self, right: Self) -> Self {
149        Self::Greater(Box::new(left), Box::new(right))
150    }
151
152    pub fn greater_or_equal(left: Self, right: Self) -> Self {
153        Self::GreaterOrEqual(Box::new(left), Box::new(right))
154    }
155
156    pub fn less(left: Self, right: Self) -> Self {
157        Self::Less(Box::new(left), Box::new(right))
158    }
159
160    pub fn less_or_equal(left: Self, right: Self) -> Self {
161        Self::LessOrEqual(Box::new(left), Box::new(right))
162    }
163
164    pub fn unary_plus(inner: Self) -> Self {
165        Self::UnaryPlus(Box::new(inner))
166    }
167
168    pub fn exists(inner: GraphPattern) -> Self {
169        if inner.is_empty() {
170            return false.into();
171        }
172        if inner.is_empty_singleton() {
173            return true.into();
174        }
175        Self::Exists(Box::new(inner))
176    }
177
178    pub fn if_cond(cond: Self, then: Self, els: Self) -> Self {
179        match cond.effective_boolean_value() {
180            Some(true) => then,
181            Some(false) => els,
182            None => Self::If(Box::new(cond), Box::new(then), Box::new(els)),
183        }
184    }
185
186    pub fn coalesce(args: Vec<Self>) -> Self {
187        Self::Coalesce(args)
188    }
189
190    pub fn call(name: Function, args: Vec<Self>) -> Self {
191        Self::FunctionCall(name, args)
192    }
193
194    pub fn effective_boolean_value(&self) -> Option<bool> {
195        if let Self::Literal(literal) = self {
196            match literal.datatype() {
197                xsd::BOOLEAN => match literal.value() {
198                    "true" | "1" => Some(true),
199                    "false" | "0" => Some(false),
200                    _ => None, // TODO
201                },
202                xsd::STRING => Some(!literal.value().is_empty()),
203                _ => None, // TODO
204            }
205        } else {
206            None
207        }
208    }
209
210    pub fn used_variables(&self) -> HashSet<&Variable> {
211        let mut variables = HashSet::new();
212        self.lookup_used_variables(&mut |v| {
213            variables.insert(v);
214        });
215        variables
216    }
217
218    pub fn lookup_used_variables<'a>(&'a self, callback: &mut impl FnMut(&'a Variable)) {
219        match self {
220            Self::NamedNode(_) | Self::Literal(_) => {}
221            Self::Variable(v) | Self::Bound(v) => callback(v),
222            Self::Or(inner)
223            | Self::And(inner)
224            | Self::Coalesce(inner)
225            | Self::FunctionCall(_, inner) => {
226                for i in inner {
227                    i.lookup_used_variables(callback);
228                }
229            }
230            Self::Equal(a, b)
231            | Self::SameTerm(a, b)
232            | Self::Greater(a, b)
233            | Self::GreaterOrEqual(a, b)
234            | Self::Less(a, b)
235            | Self::LessOrEqual(a, b)
236            | Self::Add(a, b)
237            | Self::Subtract(a, b)
238            | Self::Multiply(a, b)
239            | Self::Divide(a, b) => {
240                a.lookup_used_variables(callback);
241                b.lookup_used_variables(callback);
242            }
243            Self::UnaryPlus(i) | Self::UnaryMinus(i) | Self::Not(i) => {
244                i.lookup_used_variables(callback)
245            }
246            Self::Exists(e) => e.lookup_used_variables(callback),
247            Self::If(a, b, c) => {
248                a.lookup_used_variables(callback);
249                b.lookup_used_variables(callback);
250                c.lookup_used_variables(callback);
251            }
252        }
253    }
254
255    fn from_sparql_algebra(
256        expression: &AlExpression,
257        graph_name: Option<&NamedNodePattern>,
258    ) -> Self {
259        match expression {
260            AlExpression::NamedNode(node) => Self::NamedNode(node.clone()),
261            AlExpression::Literal(literal) => Self::Literal(literal.clone()),
262            AlExpression::Variable(variable) => Self::Variable(variable.clone()),
263            AlExpression::Or(left, right) => Self::Or(vec![
264                Self::from_sparql_algebra(left, graph_name),
265                Self::from_sparql_algebra(right, graph_name),
266            ]),
267            AlExpression::And(left, right) => Self::And(vec![
268                Self::from_sparql_algebra(left, graph_name),
269                Self::from_sparql_algebra(right, graph_name),
270            ]),
271            AlExpression::Equal(left, right) => Self::Equal(
272                Box::new(Self::from_sparql_algebra(left, graph_name)),
273                Box::new(Self::from_sparql_algebra(right, graph_name)),
274            ),
275            AlExpression::SameTerm(left, right) => Self::SameTerm(
276                Box::new(Self::from_sparql_algebra(left, graph_name)),
277                Box::new(Self::from_sparql_algebra(right, graph_name)),
278            ),
279            AlExpression::Greater(left, right) => Self::Greater(
280                Box::new(Self::from_sparql_algebra(left, graph_name)),
281                Box::new(Self::from_sparql_algebra(right, graph_name)),
282            ),
283            AlExpression::GreaterOrEqual(left, right) => Self::GreaterOrEqual(
284                Box::new(Self::from_sparql_algebra(left, graph_name)),
285                Box::new(Self::from_sparql_algebra(right, graph_name)),
286            ),
287            AlExpression::Less(left, right) => Self::Less(
288                Box::new(Self::from_sparql_algebra(left, graph_name)),
289                Box::new(Self::from_sparql_algebra(right, graph_name)),
290            ),
291            AlExpression::LessOrEqual(left, right) => Self::LessOrEqual(
292                Box::new(Self::from_sparql_algebra(left, graph_name)),
293                Box::new(Self::from_sparql_algebra(right, graph_name)),
294            ),
295            AlExpression::In(left, right) => {
296                let left = Self::from_sparql_algebra(left, graph_name);
297                match right.len() {
298                    0 => Self::if_cond(left, false.into(), false.into()),
299                    1 => Self::Equal(
300                        Box::new(left),
301                        Box::new(Self::from_sparql_algebra(&right[0], graph_name)),
302                    ),
303                    _ => Self::Or(
304                        right
305                            .iter()
306                            .map(|e| {
307                                Self::Equal(
308                                    Box::new(left.clone()),
309                                    Box::new(Self::from_sparql_algebra(e, graph_name)),
310                                )
311                            })
312                            .collect(),
313                    ),
314                }
315            }
316            AlExpression::Add(left, right) => Self::Add(
317                Box::new(Self::from_sparql_algebra(left, graph_name)),
318                Box::new(Self::from_sparql_algebra(right, graph_name)),
319            ),
320            AlExpression::Subtract(left, right) => Self::Subtract(
321                Box::new(Self::from_sparql_algebra(left, graph_name)),
322                Box::new(Self::from_sparql_algebra(right, graph_name)),
323            ),
324            AlExpression::Multiply(left, right) => Self::Multiply(
325                Box::new(Self::from_sparql_algebra(left, graph_name)),
326                Box::new(Self::from_sparql_algebra(right, graph_name)),
327            ),
328            AlExpression::Divide(left, right) => Self::Divide(
329                Box::new(Self::from_sparql_algebra(left, graph_name)),
330                Box::new(Self::from_sparql_algebra(right, graph_name)),
331            ),
332            AlExpression::UnaryPlus(inner) => {
333                Self::UnaryPlus(Box::new(Self::from_sparql_algebra(inner, graph_name)))
334            }
335            AlExpression::UnaryMinus(inner) => {
336                Self::UnaryMinus(Box::new(Self::from_sparql_algebra(inner, graph_name)))
337            }
338            AlExpression::Not(inner) => {
339                Self::Not(Box::new(Self::from_sparql_algebra(inner, graph_name)))
340            }
341            AlExpression::Exists(inner) => Self::Exists(Box::new(
342                GraphPattern::from_sparql_algebra(inner, graph_name, &mut HashMap::new()),
343            )),
344            AlExpression::Bound(variable) => Self::Bound(variable.clone()),
345            AlExpression::If(cond, yes, no) => Self::If(
346                Box::new(Self::from_sparql_algebra(cond, graph_name)),
347                Box::new(Self::from_sparql_algebra(yes, graph_name)),
348                Box::new(Self::from_sparql_algebra(no, graph_name)),
349            ),
350            AlExpression::Coalesce(inner) => Self::Coalesce(
351                inner
352                    .iter()
353                    .map(|e| Self::from_sparql_algebra(e, graph_name))
354                    .collect(),
355            ),
356            AlExpression::FunctionCall(name, args) => Self::FunctionCall(
357                name.clone(),
358                args.iter()
359                    .map(|e| Self::from_sparql_algebra(e, graph_name))
360                    .collect(),
361            ),
362        }
363    }
364
365    fn returns_boolean(&self) -> bool {
366        match self {
367            Self::Or(_)
368            | Self::And(_)
369            | Self::Equal(_, _)
370            | Self::SameTerm(_, _)
371            | Self::Greater(_, _)
372            | Self::GreaterOrEqual(_, _)
373            | Self::Less(_, _)
374            | Self::LessOrEqual(_, _)
375            | Self::Not(_)
376            | Self::Exists(_)
377            | Self::Bound(_)
378            | Self::FunctionCall(
379                Function::IsBlank | Function::IsIri | Function::IsLiteral | Function::IsNumeric,
380                _,
381            ) => true,
382            #[cfg(feature = "sparql-12")]
383            Self::FunctionCall(Function::IsTriple, _) => true,
384            Self::Literal(literal) => literal.datatype() == xsd::BOOLEAN,
385            Self::If(_, a, b) => a.returns_boolean() && b.returns_boolean(),
386            _ => false,
387        }
388    }
389}
390
391impl From<NamedNode> for Expression {
392    fn from(value: NamedNode) -> Self {
393        Self::NamedNode(value)
394    }
395}
396
397impl From<Literal> for Expression {
398    fn from(value: Literal) -> Self {
399        Self::Literal(value)
400    }
401}
402
403impl From<GroundTerm> for Expression {
404    fn from(value: GroundTerm) -> Self {
405        match value {
406            GroundTerm::NamedNode(value) => value.into(),
407            GroundTerm::Literal(value) => value.into(),
408            #[cfg(feature = "sparql-12")]
409            GroundTerm::Triple(value) => (*value).into(),
410        }
411    }
412}
413
414impl From<NamedNodePattern> for Expression {
415    fn from(value: NamedNodePattern) -> Self {
416        match value {
417            NamedNodePattern::NamedNode(value) => value.into(),
418            NamedNodePattern::Variable(variable) => variable.into(),
419        }
420    }
421}
422
423impl From<GroundTermPattern> for Expression {
424    fn from(value: GroundTermPattern) -> Self {
425        match value {
426            GroundTermPattern::NamedNode(value) => value.into(),
427            GroundTermPattern::Literal(value) => value.into(),
428            #[cfg(feature = "sparql-12")]
429            GroundTermPattern::Triple(value) => (*value).into(),
430            GroundTermPattern::Variable(variable) => variable.into(),
431        }
432    }
433}
434
435#[cfg(feature = "sparql-12")]
436impl From<GroundTriple> for Expression {
437    fn from(value: GroundTriple) -> Self {
438        Self::FunctionCall(
439            Function::Triple,
440            vec![
441                value.subject.into(),
442                value.predicate.into(),
443                value.object.into(),
444            ],
445        )
446    }
447}
448
449#[cfg(feature = "sparql-12")]
450impl From<GroundTriplePattern> for Expression {
451    fn from(value: GroundTriplePattern) -> Self {
452        Self::FunctionCall(
453            Function::Triple,
454            vec![
455                value.subject.into(),
456                value.predicate.into(),
457                value.object.into(),
458            ],
459        )
460    }
461}
462
463impl From<Variable> for Expression {
464    fn from(value: Variable) -> Self {
465        Self::Variable(value)
466    }
467}
468
469impl From<bool> for Expression {
470    fn from(value: bool) -> Self {
471        Literal::from(value).into()
472    }
473}
474
475impl From<&Expression> for AlExpression {
476    fn from(expression: &Expression) -> Self {
477        match expression {
478            Expression::NamedNode(node) => Self::NamedNode(node.clone()),
479            Expression::Literal(literal) => Self::Literal(literal.clone()),
480            Expression::Variable(variable) => Self::Variable(variable.clone()),
481            Expression::Or(inner) => inner
482                .iter()
483                .map(Into::into)
484                .reduce(|a, b| Self::Or(Box::new(a), Box::new(b)))
485                .unwrap_or_else(|| Literal::from(false).into()),
486            Expression::And(inner) => inner
487                .iter()
488                .map(Into::into)
489                .reduce(|a, b| Self::And(Box::new(a), Box::new(b)))
490                .unwrap_or_else(|| Literal::from(true).into()),
491            Expression::Equal(left, right) => Self::Equal(
492                Box::new(left.as_ref().into()),
493                Box::new(right.as_ref().into()),
494            ),
495            Expression::SameTerm(left, right) => Self::SameTerm(
496                Box::new(left.as_ref().into()),
497                Box::new(right.as_ref().into()),
498            ),
499            Expression::Greater(left, right) => Self::Greater(
500                Box::new(left.as_ref().into()),
501                Box::new(right.as_ref().into()),
502            ),
503            Expression::GreaterOrEqual(left, right) => Self::GreaterOrEqual(
504                Box::new(left.as_ref().into()),
505                Box::new(right.as_ref().into()),
506            ),
507            Expression::Less(left, right) => Self::Less(
508                Box::new(left.as_ref().into()),
509                Box::new(right.as_ref().into()),
510            ),
511            Expression::LessOrEqual(left, right) => Self::LessOrEqual(
512                Box::new(left.as_ref().into()),
513                Box::new(right.as_ref().into()),
514            ),
515            Expression::Add(left, right) => Self::Add(
516                Box::new(left.as_ref().into()),
517                Box::new(right.as_ref().into()),
518            ),
519            Expression::Subtract(left, right) => Self::Subtract(
520                Box::new(left.as_ref().into()),
521                Box::new(right.as_ref().into()),
522            ),
523            Expression::Multiply(left, right) => Self::Multiply(
524                Box::new(left.as_ref().into()),
525                Box::new(right.as_ref().into()),
526            ),
527            Expression::Divide(left, right) => Self::Divide(
528                Box::new(left.as_ref().into()),
529                Box::new(right.as_ref().into()),
530            ),
531            Expression::UnaryPlus(inner) => Self::UnaryPlus(Box::new(inner.as_ref().into())),
532            Expression::UnaryMinus(inner) => Self::UnaryMinus(Box::new(inner.as_ref().into())),
533            Expression::Not(inner) => Self::Not(Box::new(inner.as_ref().into())),
534            Expression::Exists(inner) => Self::Exists(Box::new(inner.as_ref().into())),
535            Expression::Bound(variable) => Self::Bound(variable.clone()),
536            Expression::If(cond, yes, no) => Self::If(
537                Box::new(cond.as_ref().into()),
538                Box::new(yes.as_ref().into()),
539                Box::new(no.as_ref().into()),
540            ),
541            Expression::Coalesce(inner) => Self::Coalesce(inner.iter().map(Into::into).collect()),
542            Expression::FunctionCall(name, args) => {
543                Self::FunctionCall(name.clone(), args.iter().map(Into::into).collect())
544            }
545        }
546    }
547}
548
549impl BitAnd for Expression {
550    type Output = Self;
551
552    fn bitand(self, rhs: Self) -> Self::Output {
553        Self::and_all([self, rhs])
554    }
555}
556
557impl BitOr for Expression {
558    type Output = Self;
559
560    fn bitor(self, rhs: Self) -> Self {
561        Self::or_all([self, rhs])
562    }
563}
564
565impl Not for Expression {
566    type Output = Self;
567
568    fn not(self) -> Self {
569        if let Some(v) = self.effective_boolean_value() {
570            (!v).into()
571        } else if let Self::Not(v) = self {
572            if v.returns_boolean() {
573                *v
574            } else {
575                Self::Not(Box::new(Self::Not(v)))
576            }
577        } else {
578            Self::Not(Box::new(self))
579        }
580    }
581}
582
583impl Add for Expression {
584    type Output = Self;
585
586    fn add(self, rhs: Self) -> Self {
587        let (left, right) = order_pair(self, rhs);
588        Self::Add(Box::new(left), Box::new(right))
589    }
590}
591
592impl Sub for Expression {
593    type Output = Self;
594
595    fn sub(self, rhs: Self) -> Self {
596        Self::Subtract(Box::new(self), Box::new(rhs))
597    }
598}
599
600impl Mul for Expression {
601    type Output = Self;
602
603    fn mul(self, rhs: Self) -> Self {
604        let (left, right) = order_pair(self, rhs);
605        Self::Multiply(Box::new(left), Box::new(right))
606    }
607}
608
609impl Div for Expression {
610    type Output = Self;
611
612    fn div(self, rhs: Self) -> Self {
613        Self::Divide(Box::new(self), Box::new(rhs))
614    }
615}
616
617impl Neg for Expression {
618    type Output = Self;
619
620    fn neg(self) -> Self {
621        Self::UnaryMinus(Box::new(self))
622    }
623}
624
625/// A SPARQL query [graph pattern](https://www.w3.org/TR/sparql11-query/#sparqlQuery).
626#[derive(Eq, PartialEq, Debug, Clone, Hash)]
627pub enum GraphPattern {
628    /// A [basic graph pattern](https://www.w3.org/TR/sparql11-query/#defn_BasicGraphPattern).
629    QuadPattern {
630        subject: GroundTermPattern,
631        predicate: NamedNodePattern,
632        object: GroundTermPattern,
633        graph_name: Option<NamedNodePattern>, // None for the default graph
634    },
635    /// A [property path pattern](https://www.w3.org/TR/sparql11-query/#defn_evalPP_predicate).
636    Path {
637        subject: GroundTermPattern,
638        path: PropertyPathExpression,
639        object: GroundTermPattern,
640        graph_name: Option<NamedNodePattern>, // None for the default graph
641    },
642    /// Graph check
643    ///
644    /// Can yield all named graph like in `GRAPH ?g {}`
645    /// or only check if a graph exist like in `GRAPH ex:g {}`
646    Graph { graph_name: NamedNodePattern },
647    /// [Join](https://www.w3.org/TR/sparql11-query/#defn_algJoin).
648    Join {
649        left: Box<Self>,
650        right: Box<Self>,
651        algorithm: JoinAlgorithm,
652    },
653    /// [LeftJoin](https://www.w3.org/TR/sparql11-query/#defn_algLeftJoin).
654    LeftJoin {
655        left: Box<Self>,
656        right: Box<Self>,
657        expression: Expression,
658        algorithm: LeftJoinAlgorithm,
659    },
660    /// Lateral join i.e. evaluate right for all result row of left
661    #[cfg(feature = "sep-0006")]
662    Lateral { left: Box<Self>, right: Box<Self> },
663    /// [Filter](https://www.w3.org/TR/sparql11-query/#defn_algFilter).
664    Filter {
665        expression: Expression,
666        inner: Box<Self>,
667    },
668    /// [Union](https://www.w3.org/TR/sparql11-query/#defn_algUnion).
669    Union { inner: Vec<Self> },
670    /// [Extend](https://www.w3.org/TR/sparql11-query/#defn_extend).
671    Extend {
672        inner: Box<Self>,
673        variable: Variable,
674        expression: Expression,
675    },
676    /// [Minus](https://www.w3.org/TR/sparql11-query/#defn_algMinus).
677    Minus {
678        left: Box<Self>,
679        right: Box<Self>,
680        algorithm: MinusAlgorithm,
681    },
682    /// A table used to provide inline values
683    Values {
684        variables: Vec<Variable>,
685        bindings: Vec<Vec<Option<GroundTerm>>>,
686    },
687    /// [OrderBy](https://www.w3.org/TR/sparql11-query/#defn_algOrdered).
688    OrderBy {
689        inner: Box<Self>,
690        expression: Vec<OrderExpression>,
691    },
692    /// [Project](https://www.w3.org/TR/sparql11-query/#defn_algProjection).
693    Project {
694        inner: Box<Self>,
695        variables: Vec<Variable>,
696    },
697    /// [Distinct](https://www.w3.org/TR/sparql11-query/#defn_algDistinct).
698    Distinct { inner: Box<Self> },
699    /// [Reduced](https://www.w3.org/TR/sparql11-query/#defn_algReduced).
700    Reduced { inner: Box<Self> },
701    /// [Slice](https://www.w3.org/TR/sparql11-query/#defn_algSlice).
702    Slice {
703        inner: Box<Self>,
704        start: usize,
705        length: Option<usize>,
706    },
707    /// [Group](https://www.w3.org/TR/sparql11-query/#aggregateAlgebra).
708    Group {
709        inner: Box<Self>,
710        variables: Vec<Variable>,
711        aggregates: Vec<(Variable, AggregateExpression)>,
712    },
713    /// [Service](https://www.w3.org/TR/sparql11-federated-query/#defn_evalService).
714    Service {
715        name: NamedNodePattern,
716        inner: Box<Self>,
717        silent: bool,
718    },
719}
720
721impl GraphPattern {
722    pub fn empty() -> Self {
723        Self::Values {
724            variables: Vec::new(),
725            bindings: Vec::new(),
726        }
727    }
728
729    /// Check if the pattern is the empty table
730    fn is_empty(&self) -> bool {
731        if let Self::Values { bindings, .. } = self {
732            bindings.is_empty()
733        } else {
734            false
735        }
736    }
737
738    pub fn empty_singleton() -> Self {
739        Self::Values {
740            variables: Vec::new(),
741            bindings: vec![Vec::new()],
742        }
743    }
744
745    pub fn is_empty_singleton(&self) -> bool {
746        if let Self::Values { bindings, .. } = self {
747            bindings.len() == 1 && bindings.iter().all(|b| b.iter().all(Option::is_none))
748        } else {
749            false
750        }
751    }
752
753    pub fn join(left: Self, right: Self, algorithm: JoinAlgorithm) -> Self {
754        if left.is_empty() || right.is_empty() {
755            return Self::empty();
756        }
757        if left.is_empty_singleton() {
758            return right;
759        }
760        if right.is_empty_singleton() {
761            return left;
762        }
763        Self::Join {
764            left: Box::new(left),
765            right: Box::new(right),
766            algorithm,
767        }
768    }
769
770    #[cfg(feature = "sep-0006")]
771    pub fn lateral(left: Self, right: Self) -> Self {
772        if left.is_empty() || right.is_empty() {
773            return Self::empty();
774        }
775        if left.is_empty_singleton() {
776            return right;
777        }
778        if right.is_empty_singleton() {
779            return left;
780        }
781        Self::Lateral {
782            left: Box::new(left),
783            right: Box::new(right),
784        }
785    }
786
787    pub fn left_join(
788        left: Self,
789        right: Self,
790        expression: Expression,
791        algorithm: LeftJoinAlgorithm,
792    ) -> Self {
793        let expression_ebv = expression.effective_boolean_value();
794        if left.is_empty()
795            || right.is_empty()
796            || right.is_empty_singleton()
797            || expression_ebv == Some(false)
798        {
799            return left;
800        }
801        Self::LeftJoin {
802            left: Box::new(left),
803            right: Box::new(right),
804            expression: if expression_ebv == Some(true) {
805                true.into()
806            } else {
807                expression
808            },
809            algorithm,
810        }
811    }
812
813    pub fn minus(left: Self, right: Self, algorithm: MinusAlgorithm) -> Self {
814        if left.is_empty() {
815            return Self::empty();
816        }
817        if right.is_empty() {
818            return left;
819        }
820        Self::Minus {
821            left: Box::new(left),
822            right: Box::new(right),
823            algorithm,
824        }
825    }
826
827    pub fn union(left: Self, right: Self) -> Self {
828        Self::union_all([left, right])
829    }
830
831    pub fn union_all(args: impl IntoIterator<Item = Self>) -> Self {
832        let args = args.into_iter();
833        let mut all = Vec::with_capacity(args.size_hint().0);
834        for arg in args {
835            if arg.is_empty() {
836                continue;
837            }
838            if let Self::Union { inner } = arg {
839                all.extend(inner);
840            } else {
841                all.push(arg);
842            }
843        }
844        if all.is_empty() {
845            Self::empty()
846        } else {
847            Self::Union {
848                inner: order_vec(all),
849            }
850        }
851    }
852
853    pub fn filter(inner: Self, expression: Expression) -> Self {
854        if inner.is_empty() {
855            return Self::empty();
856        }
857        // We unwrap singleton And
858        let expression = match expression {
859            Expression::And(mut l) if l.len() == 1 => l.pop().unwrap(),
860            e => e,
861        };
862        match expression.effective_boolean_value() {
863            Some(true) => inner,
864            Some(false) => Self::empty(),
865            None => match inner {
866                Self::Filter {
867                    inner: nested_inner,
868                    expression: e2,
869                } => Self::Filter {
870                    inner: nested_inner,
871                    expression: expression & e2,
872                },
873                _ => Self::Filter {
874                    inner: Box::new(inner),
875                    expression,
876                },
877            },
878        }
879    }
880
881    pub fn extend(inner: Self, variable: Variable, expression: Expression) -> Self {
882        if inner.is_empty() {
883            return Self::empty();
884        }
885        Self::Extend {
886            inner: Box::new(inner),
887            variable,
888            expression,
889        }
890    }
891
892    pub fn values(
893        mut variables: Vec<Variable>,
894        mut bindings: Vec<Vec<Option<GroundTerm>>>,
895    ) -> Self {
896        let empty_rows = (0..variables.len())
897            .filter(|row| !bindings.iter().any(|binding| binding.get(*row).is_some()))
898            .collect::<Vec<_>>();
899        if !empty_rows.is_empty() {
900            // We remove empty rows
901            variables = variables
902                .into_iter()
903                .enumerate()
904                .filter_map(|(i, v)| {
905                    if empty_rows.contains(&i) {
906                        None
907                    } else {
908                        Some(v)
909                    }
910                })
911                .collect();
912            bindings = bindings
913                .into_iter()
914                .map(|binding| {
915                    binding
916                        .into_iter()
917                        .enumerate()
918                        .filter_map(|(i, v)| {
919                            if empty_rows.contains(&i) {
920                                None
921                            } else {
922                                Some(v)
923                            }
924                        })
925                        .collect()
926                })
927                .collect();
928        }
929        Self::Values {
930            variables,
931            bindings,
932        }
933    }
934
935    pub fn order_by(inner: Self, expression: Vec<OrderExpression>) -> Self {
936        if inner.is_empty() {
937            return Self::empty();
938        }
939        if expression.is_empty() {
940            return inner;
941        }
942        Self::OrderBy {
943            inner: Box::new(inner),
944            expression,
945        }
946    }
947
948    pub fn project(inner: Self, variables: Vec<Variable>) -> Self {
949        Self::Project {
950            inner: Box::new(inner),
951            variables,
952        }
953    }
954
955    pub fn distinct(inner: Self) -> Self {
956        if inner.is_empty() {
957            return Self::empty();
958        }
959        Self::Distinct {
960            inner: Box::new(inner),
961        }
962    }
963
964    pub fn reduced(inner: Self) -> Self {
965        if inner.is_empty() {
966            return Self::empty();
967        }
968        Self::Reduced {
969            inner: Box::new(inner),
970        }
971    }
972
973    pub fn slice(inner: Self, start: usize, length: Option<usize>) -> Self {
974        if inner.is_empty() {
975            return Self::empty();
976        }
977        if start == 0 && length.is_none() {
978            return inner;
979        }
980        Self::Slice {
981            inner: Box::new(inner),
982            start,
983            length,
984        }
985    }
986
987    pub fn group(
988        inner: Self,
989        variables: Vec<Variable>,
990        aggregates: Vec<(Variable, AggregateExpression)>,
991    ) -> Self {
992        if inner.is_empty() {
993            return Self::empty();
994        }
995        Self::Group {
996            inner: Box::new(inner),
997            variables,
998            aggregates,
999        }
1000    }
1001
1002    pub fn service(inner: Self, name: NamedNodePattern, silent: bool) -> Self {
1003        Self::Service {
1004            inner: Box::new(inner),
1005            name,
1006            silent,
1007        }
1008    }
1009
1010    pub fn lookup_used_variables<'a>(&'a self, callback: &mut impl FnMut(&'a Variable)) {
1011        match self {
1012            Self::Values { variables, .. } | Self::Project { variables, .. } => {
1013                for v in variables {
1014                    callback(v);
1015                }
1016            }
1017            Self::QuadPattern {
1018                subject,
1019                predicate,
1020                object,
1021                graph_name,
1022            } => {
1023                lookup_term_pattern_variables(subject, callback);
1024                if let NamedNodePattern::Variable(v) = predicate {
1025                    callback(v);
1026                }
1027                lookup_term_pattern_variables(object, callback);
1028                if let Some(NamedNodePattern::Variable(v)) = graph_name {
1029                    callback(v);
1030                }
1031            }
1032            Self::Path {
1033                subject,
1034                object,
1035                graph_name,
1036                ..
1037            } => {
1038                lookup_term_pattern_variables(subject, callback);
1039                lookup_term_pattern_variables(object, callback);
1040                if let Some(NamedNodePattern::Variable(v)) = graph_name {
1041                    callback(v);
1042                }
1043            }
1044            Self::Graph { graph_name } => {
1045                if let NamedNodePattern::Variable(v) = graph_name {
1046                    callback(v);
1047                }
1048            }
1049            Self::Filter { inner, expression } => {
1050                expression.lookup_used_variables(callback);
1051                inner.lookup_used_variables(callback);
1052            }
1053            Self::Union { inner } => {
1054                for child in inner {
1055                    child.lookup_used_variables(callback);
1056                }
1057            }
1058            Self::Join { left, right, .. } | Self::Minus { left, right, .. } => {
1059                left.lookup_used_variables(callback);
1060                right.lookup_used_variables(callback);
1061            }
1062            #[cfg(feature = "sep-0006")]
1063            Self::Lateral { left, right } => {
1064                left.lookup_used_variables(callback);
1065                right.lookup_used_variables(callback);
1066            }
1067            Self::LeftJoin {
1068                left,
1069                right,
1070                expression,
1071                ..
1072            } => {
1073                expression.lookup_used_variables(callback);
1074                left.lookup_used_variables(callback);
1075                right.lookup_used_variables(callback);
1076            }
1077            Self::Extend {
1078                inner,
1079                variable,
1080                expression,
1081            } => {
1082                callback(variable);
1083                expression.lookup_used_variables(callback);
1084                inner.lookup_used_variables(callback);
1085            }
1086            Self::OrderBy { inner, .. }
1087            | Self::Distinct { inner }
1088            | Self::Reduced { inner }
1089            | Self::Slice { inner, .. } => inner.lookup_used_variables(callback),
1090            Self::Service { inner, name, .. } => {
1091                if let NamedNodePattern::Variable(v) = name {
1092                    callback(v);
1093                }
1094                inner.lookup_used_variables(callback);
1095            }
1096            Self::Group {
1097                variables,
1098                aggregates,
1099                ..
1100            } => {
1101                for v in variables {
1102                    callback(v);
1103                }
1104                for (v, _) in aggregates {
1105                    callback(v);
1106                }
1107            }
1108        }
1109    }
1110
1111    fn from_sparql_algebra(
1112        pattern: &AlGraphPattern,
1113        graph_name: Option<&NamedNodePattern>,
1114        blank_nodes: &mut HashMap<BlankNode, Variable>,
1115    ) -> Self {
1116        match pattern {
1117            AlGraphPattern::Bgp { patterns } => patterns
1118                .iter()
1119                .map(|p| {
1120                    let (subject, predicate, object) =
1121                        Self::triple_pattern_from_algebra(p, blank_nodes);
1122                    Self::QuadPattern {
1123                        subject,
1124                        predicate,
1125                        object,
1126                        graph_name: graph_name.cloned(),
1127                    }
1128                })
1129                .reduce(|a, b| Self::Join {
1130                    left: Box::new(a),
1131                    right: Box::new(b),
1132                    algorithm: JoinAlgorithm::default(),
1133                })
1134                .unwrap_or_else(|| {
1135                    if let Some(graph_name) = graph_name {
1136                        Self::Graph {
1137                            graph_name: graph_name.clone(),
1138                        }
1139                    } else {
1140                        Self::empty_singleton()
1141                    }
1142                }),
1143            AlGraphPattern::Path {
1144                subject,
1145                path,
1146                object,
1147            } => Self::Path {
1148                subject: Self::term_pattern_from_algebra(subject, blank_nodes),
1149                path: path.clone(),
1150                object: Self::term_pattern_from_algebra(object, blank_nodes),
1151                graph_name: graph_name.cloned(),
1152            },
1153            AlGraphPattern::Join { left, right } => Self::Join {
1154                left: Box::new(Self::from_sparql_algebra(left, graph_name, blank_nodes)),
1155                right: Box::new(Self::from_sparql_algebra(right, graph_name, blank_nodes)),
1156                algorithm: JoinAlgorithm::default(),
1157            },
1158            AlGraphPattern::LeftJoin {
1159                left,
1160                right,
1161                expression,
1162            } => Self::LeftJoin {
1163                left: Box::new(Self::from_sparql_algebra(left, graph_name, blank_nodes)),
1164                right: Box::new(Self::from_sparql_algebra(right, graph_name, blank_nodes)),
1165                expression: expression.as_ref().map_or_else(
1166                    || true.into(),
1167                    |e| Expression::from_sparql_algebra(e, graph_name),
1168                ),
1169                algorithm: LeftJoinAlgorithm::default(),
1170            },
1171            #[cfg(feature = "sep-0006")]
1172            AlGraphPattern::Lateral { left, right } => Self::Lateral {
1173                left: Box::new(Self::from_sparql_algebra(left, graph_name, blank_nodes)),
1174                right: Box::new(Self::from_sparql_algebra(right, graph_name, blank_nodes)),
1175            },
1176            AlGraphPattern::Filter { inner, expr } => Self::Filter {
1177                inner: Box::new(Self::from_sparql_algebra(inner, graph_name, blank_nodes)),
1178                expression: Expression::from_sparql_algebra(expr, graph_name),
1179            },
1180            AlGraphPattern::Union { left, right } => Self::Union {
1181                inner: vec![
1182                    Self::from_sparql_algebra(left, graph_name, blank_nodes),
1183                    Self::from_sparql_algebra(right, graph_name, blank_nodes),
1184                ],
1185            },
1186            AlGraphPattern::Graph { inner, name } => {
1187                Self::from_sparql_algebra(inner, Some(name), blank_nodes)
1188            }
1189            AlGraphPattern::Extend {
1190                inner,
1191                expression,
1192                variable,
1193            } => Self::Extend {
1194                inner: Box::new(Self::from_sparql_algebra(inner, graph_name, blank_nodes)),
1195                expression: Expression::from_sparql_algebra(expression, graph_name),
1196                variable: variable.clone(),
1197            },
1198            AlGraphPattern::Minus { left, right } => Self::Minus {
1199                left: Box::new(Self::from_sparql_algebra(left, graph_name, blank_nodes)),
1200                right: Box::new(Self::from_sparql_algebra(right, graph_name, blank_nodes)),
1201                algorithm: MinusAlgorithm::default(),
1202            },
1203            AlGraphPattern::Values {
1204                variables,
1205                bindings,
1206            } => Self::Values {
1207                variables: variables.clone(),
1208                bindings: bindings.clone(),
1209            },
1210            AlGraphPattern::OrderBy { inner, expression } => {
1211                let mut inner = Self::from_sparql_algebra(inner, graph_name, blank_nodes);
1212                let mut expressions = Vec::with_capacity(expression.len());
1213                for e in expression {
1214                    expressions.push(match e {
1215                        AlOrderExpression::Asc(e) => {
1216                            let v;
1217                            (v, inner) = Self::algebra_expression_to_constant_or_variable(
1218                                e, inner, graph_name,
1219                            );
1220                            OrderExpression::Asc(Expression::Variable(v))
1221                        }
1222                        AlOrderExpression::Desc(e) => {
1223                            let v;
1224                            (v, inner) = Self::algebra_expression_to_constant_or_variable(
1225                                e, inner, graph_name,
1226                            );
1227                            OrderExpression::Desc(Expression::Variable(v))
1228                        }
1229                    });
1230                }
1231                Self::OrderBy {
1232                    inner: Box::new(inner),
1233                    expression: expressions,
1234                }
1235            }
1236            AlGraphPattern::Project { inner, variables } => {
1237                let graph_name = if let Some(NamedNodePattern::Variable(graph_name)) = graph_name {
1238                    Some(NamedNodePattern::Variable(
1239                        if variables.contains(graph_name) {
1240                            graph_name.clone()
1241                        } else {
1242                            new_var()
1243                        },
1244                    ))
1245                } else {
1246                    graph_name.cloned()
1247                };
1248                Self::Project {
1249                    inner: Box::new(Self::from_sparql_algebra(
1250                        inner,
1251                        graph_name.as_ref(),
1252                        &mut HashMap::new(),
1253                    )),
1254                    variables: variables.clone(),
1255                }
1256            }
1257            AlGraphPattern::Distinct { inner } => Self::Distinct {
1258                inner: Box::new(Self::from_sparql_algebra(inner, graph_name, blank_nodes)),
1259            },
1260            AlGraphPattern::Reduced { inner } => Self::Distinct {
1261                inner: Box::new(Self::from_sparql_algebra(inner, graph_name, blank_nodes)),
1262            },
1263            AlGraphPattern::Slice {
1264                inner,
1265                start,
1266                length,
1267            } => Self::Slice {
1268                inner: Box::new(Self::from_sparql_algebra(inner, graph_name, blank_nodes)),
1269                start: *start,
1270                length: *length,
1271            },
1272            AlGraphPattern::Group {
1273                inner,
1274                variables,
1275                aggregates,
1276            } => Self::Group {
1277                inner: Box::new(Self::from_sparql_algebra(inner, graph_name, blank_nodes)),
1278                variables: variables.clone(),
1279                aggregates: aggregates
1280                    .iter()
1281                    .map(|(var, expr)| {
1282                        (
1283                            var.clone(),
1284                            AggregateExpression::from_sparql_algebra(expr, graph_name),
1285                        )
1286                    })
1287                    .collect(),
1288            },
1289            AlGraphPattern::Service {
1290                inner,
1291                name,
1292                silent,
1293            } => Self::Service {
1294                inner: Box::new(Self::from_sparql_algebra(inner, graph_name, blank_nodes)),
1295                name: name.clone(),
1296                silent: *silent,
1297            },
1298        }
1299    }
1300
1301    fn triple_pattern_from_algebra(
1302        pattern: &TriplePattern,
1303        blank_nodes: &mut HashMap<BlankNode, Variable>,
1304    ) -> (GroundTermPattern, NamedNodePattern, GroundTermPattern) {
1305        (
1306            Self::term_pattern_from_algebra(&pattern.subject, blank_nodes),
1307            pattern.predicate.clone(),
1308            Self::term_pattern_from_algebra(&pattern.object, blank_nodes),
1309        )
1310    }
1311
1312    fn term_pattern_from_algebra(
1313        pattern: &TermPattern,
1314        blank_nodes: &mut HashMap<BlankNode, Variable>,
1315    ) -> GroundTermPattern {
1316        match pattern {
1317            TermPattern::NamedNode(node) => node.clone().into(),
1318            TermPattern::BlankNode(node) => blank_nodes
1319                .entry(node.clone())
1320                .or_insert_with(new_var)
1321                .clone()
1322                .into(),
1323            TermPattern::Literal(literal) => literal.clone().into(),
1324            #[cfg(feature = "sparql-12")]
1325            TermPattern::Triple(pattern) => {
1326                let (subject, predicate, object) =
1327                    Self::triple_pattern_from_algebra(pattern, blank_nodes);
1328                GroundTriplePattern {
1329                    subject,
1330                    predicate,
1331                    object,
1332                }
1333                .into()
1334            }
1335            TermPattern::Variable(variable) => variable.clone().into(),
1336        }
1337    }
1338
1339    /// Makes sure the expression is a variable, use Extend in the other cases
1340    fn algebra_expression_to_constant_or_variable(
1341        expression: &AlExpression,
1342        graph_pattern: GraphPattern,
1343        graph_name: Option<&NamedNodePattern>,
1344    ) -> (Variable, GraphPattern) {
1345        if let AlExpression::Variable(variable) = expression {
1346            (variable.clone(), graph_pattern)
1347        } else {
1348            let variable = Variable::new_unchecked(format!("{:x}", random::<u128>()));
1349            (
1350                variable.clone(),
1351                GraphPattern::Extend {
1352                    inner: Box::new(graph_pattern),
1353                    variable,
1354                    expression: Expression::from_sparql_algebra(expression, graph_name),
1355                },
1356            )
1357        }
1358    }
1359}
1360
1361impl From<&AlGraphPattern> for GraphPattern {
1362    fn from(pattern: &AlGraphPattern) -> Self {
1363        Self::from_sparql_algebra(pattern, None, &mut HashMap::new())
1364    }
1365}
1366
1367impl From<&GraphPattern> for AlGraphPattern {
1368    fn from(pattern: &GraphPattern) -> Self {
1369        match pattern {
1370            GraphPattern::QuadPattern {
1371                subject,
1372                predicate,
1373                object,
1374                graph_name,
1375            } => {
1376                let pattern = Self::Bgp {
1377                    patterns: vec![TriplePattern {
1378                        subject: subject.clone().into(),
1379                        predicate: predicate.clone(),
1380                        object: object.clone().into(),
1381                    }],
1382                };
1383                if let Some(graph_name) = graph_name {
1384                    Self::Graph {
1385                        inner: Box::new(pattern),
1386                        name: graph_name.clone(),
1387                    }
1388                } else {
1389                    pattern
1390                }
1391            }
1392            GraphPattern::Path {
1393                subject,
1394                path,
1395                object,
1396                graph_name,
1397            } => {
1398                let pattern = Self::Path {
1399                    subject: subject.clone().into(),
1400                    path: path.clone(),
1401                    object: object.clone().into(),
1402                };
1403                if let Some(graph_name) = graph_name {
1404                    Self::Graph {
1405                        inner: Box::new(pattern),
1406                        name: graph_name.clone(),
1407                    }
1408                } else {
1409                    pattern
1410                }
1411            }
1412            GraphPattern::Graph { graph_name } => Self::Graph {
1413                inner: Box::new(AlGraphPattern::Bgp {
1414                    patterns: Vec::new(),
1415                }),
1416                name: graph_name.clone(),
1417            },
1418            GraphPattern::Join { left, right, .. } => {
1419                match (left.as_ref().into(), right.as_ref().into()) {
1420                    (Self::Bgp { patterns: mut left }, Self::Bgp { patterns: right }) => {
1421                        left.extend(right);
1422                        Self::Bgp { patterns: left }
1423                    }
1424                    (left, right) => Self::Join {
1425                        left: Box::new(left),
1426                        right: Box::new(right),
1427                    },
1428                }
1429            }
1430            GraphPattern::LeftJoin {
1431                left,
1432                right,
1433                expression,
1434                ..
1435            } => {
1436                let empty_expr = if let Expression::Literal(l) = expression {
1437                    l.datatype() == xsd::BOOLEAN && l.value() == "true"
1438                } else {
1439                    false
1440                };
1441                Self::LeftJoin {
1442                    left: Box::new(left.as_ref().into()),
1443                    right: Box::new(right.as_ref().into()),
1444                    expression: if empty_expr {
1445                        None
1446                    } else {
1447                        Some(expression.into())
1448                    },
1449                }
1450            }
1451            #[cfg(feature = "sep-0006")]
1452            GraphPattern::Lateral { left, right } => {
1453                match (left.as_ref().into(), right.as_ref().into()) {
1454                    (Self::Bgp { patterns: mut left }, Self::Bgp { patterns: right }) => {
1455                        left.extend(right);
1456                        Self::Bgp { patterns: left }
1457                    }
1458                    (left, right) => Self::Lateral {
1459                        left: Box::new(left),
1460                        right: Box::new(right),
1461                    },
1462                }
1463            }
1464            GraphPattern::Filter { inner, expression } => Self::Filter {
1465                inner: Box::new(inner.as_ref().into()),
1466                expr: expression.into(),
1467            },
1468            GraphPattern::Union { inner } => inner
1469                .iter()
1470                .map(Into::into)
1471                .reduce(|a, b| Self::Union {
1472                    left: Box::new(a),
1473                    right: Box::new(b),
1474                })
1475                .unwrap_or_else(|| Self::Values {
1476                    variables: Vec::new(),
1477                    bindings: Vec::new(),
1478                }),
1479            GraphPattern::Extend {
1480                inner,
1481                expression,
1482                variable,
1483            } => Self::Extend {
1484                inner: Box::new(inner.as_ref().into()),
1485                expression: expression.into(),
1486                variable: variable.clone(),
1487            },
1488            GraphPattern::Minus { left, right, .. } => Self::Minus {
1489                left: Box::new(left.as_ref().into()),
1490                right: Box::new(right.as_ref().into()),
1491            },
1492            GraphPattern::Values {
1493                variables,
1494                bindings,
1495            } => Self::Values {
1496                variables: variables.clone(),
1497                bindings: bindings.clone(),
1498            },
1499            GraphPattern::OrderBy { inner, expression } => Self::OrderBy {
1500                inner: Box::new(inner.as_ref().into()),
1501                expression: expression.iter().map(Into::into).collect(),
1502            },
1503            GraphPattern::Project { inner, variables } => Self::Project {
1504                inner: Box::new(inner.as_ref().into()),
1505                variables: variables.clone(),
1506            },
1507            GraphPattern::Distinct { inner } => Self::Distinct {
1508                inner: Box::new(inner.as_ref().into()),
1509            },
1510            GraphPattern::Reduced { inner } => Self::Distinct {
1511                inner: Box::new(inner.as_ref().into()),
1512            },
1513            GraphPattern::Slice {
1514                inner,
1515                start,
1516                length,
1517            } => Self::Slice {
1518                inner: Box::new(inner.as_ref().into()),
1519                start: *start,
1520                length: *length,
1521            },
1522            GraphPattern::Group {
1523                inner,
1524                variables,
1525                aggregates,
1526            } => Self::Group {
1527                inner: Box::new(inner.as_ref().into()),
1528                variables: variables.clone(),
1529                aggregates: aggregates
1530                    .iter()
1531                    .map(|(var, expr)| (var.clone(), expr.into()))
1532                    .collect(),
1533            },
1534            GraphPattern::Service {
1535                inner,
1536                name,
1537                silent,
1538            } => Self::Service {
1539                inner: Box::new(inner.as_ref().into()),
1540                name: name.clone(),
1541                silent: *silent,
1542            },
1543        }
1544    }
1545}
1546
1547/// The join algorithm used (c.f. [`GraphPattern::Join`]).
1548#[derive(Eq, PartialEq, Debug, Clone, Hash)]
1549pub enum JoinAlgorithm {
1550    HashBuildLeftProbeRight { keys: Vec<Variable> },
1551}
1552
1553impl Default for JoinAlgorithm {
1554    fn default() -> Self {
1555        Self::HashBuildLeftProbeRight {
1556            keys: Vec::default(),
1557        }
1558    }
1559}
1560
1561/// The left join algorithm used (c.f. [`GraphPattern::LeftJoin`]).
1562#[derive(Eq, PartialEq, Debug, Clone, Hash)]
1563pub enum LeftJoinAlgorithm {
1564    HashBuildRightProbeLeft { keys: Vec<Variable> },
1565}
1566
1567impl Default for LeftJoinAlgorithm {
1568    fn default() -> Self {
1569        Self::HashBuildRightProbeLeft {
1570            keys: Vec::default(),
1571        }
1572    }
1573}
1574
1575/// The left join algorithm used (c.f. [`GraphPattern::Minus`]).
1576#[derive(Eq, PartialEq, Debug, Clone, Hash)]
1577pub enum MinusAlgorithm {
1578    HashBuildRightProbeLeft { keys: Vec<Variable> },
1579}
1580
1581impl Default for MinusAlgorithm {
1582    fn default() -> Self {
1583        Self::HashBuildRightProbeLeft {
1584            keys: Vec::default(),
1585        }
1586    }
1587}
1588
1589/// A set function used in aggregates (c.f. [`GraphPattern::Group`]).
1590#[derive(Eq, PartialEq, Debug, Clone, Hash)]
1591pub enum AggregateExpression {
1592    CountSolutions {
1593        distinct: bool,
1594    },
1595    FunctionCall {
1596        name: AggregateFunction,
1597        expr: Expression,
1598        distinct: bool,
1599    },
1600}
1601
1602impl AggregateExpression {
1603    fn from_sparql_algebra(
1604        expression: &AlAggregateExpression,
1605        graph_name: Option<&NamedNodePattern>,
1606    ) -> Self {
1607        match expression {
1608            AlAggregateExpression::CountSolutions { distinct } => Self::CountSolutions {
1609                distinct: *distinct,
1610            },
1611            AlAggregateExpression::FunctionCall {
1612                name,
1613                expr,
1614                distinct,
1615            } => Self::FunctionCall {
1616                name: name.clone(),
1617                expr: Expression::from_sparql_algebra(expr, graph_name),
1618                distinct: *distinct,
1619            },
1620        }
1621    }
1622}
1623
1624impl From<&AggregateExpression> for AlAggregateExpression {
1625    fn from(expression: &AggregateExpression) -> Self {
1626        match expression {
1627            AggregateExpression::CountSolutions { distinct } => Self::CountSolutions {
1628                distinct: *distinct,
1629            },
1630            AggregateExpression::FunctionCall {
1631                name,
1632                expr,
1633                distinct,
1634            } => Self::FunctionCall {
1635                name: name.clone(),
1636                expr: expr.into(),
1637                distinct: *distinct,
1638            },
1639        }
1640    }
1641}
1642
1643/// An ordering comparator used by [`GraphPattern::OrderBy`].
1644#[derive(Eq, PartialEq, Debug, Clone, Hash)]
1645pub enum OrderExpression {
1646    /// Ascending order
1647    Asc(Expression),
1648    /// Descending order
1649    Desc(Expression),
1650}
1651
1652impl From<&OrderExpression> for AlOrderExpression {
1653    fn from(expression: &OrderExpression) -> Self {
1654        match expression {
1655            OrderExpression::Asc(e) => Self::Asc(e.into()),
1656            OrderExpression::Desc(e) => Self::Desc(e.into()),
1657        }
1658    }
1659}
1660
1661fn new_var() -> Variable {
1662    Variable::new_unchecked(format!("{:x}", random::<u128>()))
1663}
1664
1665fn order_pair<T: Hash>(a: T, b: T) -> (T, T) {
1666    if hash(&a) <= hash(&b) { (a, b) } else { (b, a) }
1667}
1668
1669fn order_vec<T: Hash>(mut vec: Vec<T>) -> Vec<T> {
1670    vec.sort_unstable_by_key(|a| hash(a));
1671    vec
1672}
1673
1674fn hash(v: impl Hash) -> u64 {
1675    let mut hasher = DefaultHasher::new();
1676    v.hash(&mut hasher);
1677    hasher.finish()
1678}
1679
1680fn lookup_term_pattern_variables<'a>(
1681    pattern: &'a GroundTermPattern,
1682    callback: &mut impl FnMut(&'a Variable),
1683) {
1684    if let GroundTermPattern::Variable(v) = pattern {
1685        callback(v);
1686    }
1687    #[cfg(feature = "sparql-12")]
1688    if let GroundTermPattern::Triple(t) = pattern {
1689        lookup_term_pattern_variables(&t.subject, callback);
1690        if let NamedNodePattern::Variable(v) = &t.predicate {
1691            callback(v);
1692        }
1693        lookup_term_pattern_variables(&t.object, callback);
1694    }
1695}
sparopt/algebra.rs

sparopt/
algebra.rs
