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, GroundSubject, TermPattern, TriplePattern};
11pub use spargebra::term::{
12    GroundTerm, GroundTermPattern, Literal, NamedNode, NamedNodePattern, Variable,
13};
14#[cfg(feature = "rdf-star")]
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 = "rdf-star")]
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<GroundSubject> for Expression {
404    fn from(value: GroundSubject) -> Self {
405        match value {
406            GroundSubject::NamedNode(value) => value.into(),
407            #[cfg(feature = "rdf-star")]
408            GroundSubject::Triple(value) => (*value).into(),
409        }
410    }
411}
412
413impl From<GroundTerm> for Expression {
414    fn from(value: GroundTerm) -> Self {
415        match value {
416            GroundTerm::NamedNode(value) => value.into(),
417            GroundTerm::Literal(value) => value.into(),
418            #[cfg(feature = "rdf-star")]
419            GroundTerm::Triple(value) => (*value).into(),
420        }
421    }
422}
423
424impl From<NamedNodePattern> for Expression {
425    fn from(value: NamedNodePattern) -> Self {
426        match value {
427            NamedNodePattern::NamedNode(value) => value.into(),
428            NamedNodePattern::Variable(variable) => variable.into(),
429        }
430    }
431}
432
433impl From<GroundTermPattern> for Expression {
434    fn from(value: GroundTermPattern) -> Self {
435        match value {
436            GroundTermPattern::NamedNode(value) => value.into(),
437            GroundTermPattern::Literal(value) => value.into(),
438            #[cfg(feature = "rdf-star")]
439            GroundTermPattern::Triple(value) => (*value).into(),
440            GroundTermPattern::Variable(variable) => variable.into(),
441        }
442    }
443}
444
445#[cfg(feature = "rdf-star")]
446impl From<GroundTriple> for Expression {
447    fn from(value: GroundTriple) -> Self {
448        Self::FunctionCall(
449            Function::Triple,
450            vec![
451                value.subject.into(),
452                value.predicate.into(),
453                value.object.into(),
454            ],
455        )
456    }
457}
458
459#[cfg(feature = "rdf-star")]
460impl From<GroundTriplePattern> for Expression {
461    fn from(value: GroundTriplePattern) -> Self {
462        Self::FunctionCall(
463            Function::Triple,
464            vec![
465                value.subject.into(),
466                value.predicate.into(),
467                value.object.into(),
468            ],
469        )
470    }
471}
472
473impl From<Variable> for Expression {
474    fn from(value: Variable) -> Self {
475        Self::Variable(value)
476    }
477}
478
479impl From<bool> for Expression {
480    fn from(value: bool) -> Self {
481        Literal::from(value).into()
482    }
483}
484
485impl From<&Expression> for AlExpression {
486    fn from(expression: &Expression) -> Self {
487        match expression {
488            Expression::NamedNode(node) => Self::NamedNode(node.clone()),
489            Expression::Literal(literal) => Self::Literal(literal.clone()),
490            Expression::Variable(variable) => Self::Variable(variable.clone()),
491            Expression::Or(inner) => inner
492                .iter()
493                .map(Into::into)
494                .reduce(|a, b| Self::Or(Box::new(a), Box::new(b)))
495                .unwrap_or_else(|| Literal::from(false).into()),
496            Expression::And(inner) => inner
497                .iter()
498                .map(Into::into)
499                .reduce(|a, b| Self::And(Box::new(a), Box::new(b)))
500                .unwrap_or_else(|| Literal::from(true).into()),
501            Expression::Equal(left, right) => Self::Equal(
502                Box::new(left.as_ref().into()),
503                Box::new(right.as_ref().into()),
504            ),
505            Expression::SameTerm(left, right) => Self::SameTerm(
506                Box::new(left.as_ref().into()),
507                Box::new(right.as_ref().into()),
508            ),
509            Expression::Greater(left, right) => Self::Greater(
510                Box::new(left.as_ref().into()),
511                Box::new(right.as_ref().into()),
512            ),
513            Expression::GreaterOrEqual(left, right) => Self::GreaterOrEqual(
514                Box::new(left.as_ref().into()),
515                Box::new(right.as_ref().into()),
516            ),
517            Expression::Less(left, right) => Self::Less(
518                Box::new(left.as_ref().into()),
519                Box::new(right.as_ref().into()),
520            ),
521            Expression::LessOrEqual(left, right) => Self::LessOrEqual(
522                Box::new(left.as_ref().into()),
523                Box::new(right.as_ref().into()),
524            ),
525            Expression::Add(left, right) => Self::Add(
526                Box::new(left.as_ref().into()),
527                Box::new(right.as_ref().into()),
528            ),
529            Expression::Subtract(left, right) => Self::Subtract(
530                Box::new(left.as_ref().into()),
531                Box::new(right.as_ref().into()),
532            ),
533            Expression::Multiply(left, right) => Self::Multiply(
534                Box::new(left.as_ref().into()),
535                Box::new(right.as_ref().into()),
536            ),
537            Expression::Divide(left, right) => Self::Divide(
538                Box::new(left.as_ref().into()),
539                Box::new(right.as_ref().into()),
540            ),
541            Expression::UnaryPlus(inner) => Self::UnaryPlus(Box::new(inner.as_ref().into())),
542            Expression::UnaryMinus(inner) => Self::UnaryMinus(Box::new(inner.as_ref().into())),
543            Expression::Not(inner) => Self::Not(Box::new(inner.as_ref().into())),
544            Expression::Exists(inner) => Self::Exists(Box::new(inner.as_ref().into())),
545            Expression::Bound(variable) => Self::Bound(variable.clone()),
546            Expression::If(cond, yes, no) => Self::If(
547                Box::new(cond.as_ref().into()),
548                Box::new(yes.as_ref().into()),
549                Box::new(no.as_ref().into()),
550            ),
551            Expression::Coalesce(inner) => Self::Coalesce(inner.iter().map(Into::into).collect()),
552            Expression::FunctionCall(name, args) => {
553                Self::FunctionCall(name.clone(), args.iter().map(Into::into).collect())
554            }
555        }
556    }
557}
558
559impl BitAnd for Expression {
560    type Output = Self;
561
562    fn bitand(self, rhs: Self) -> Self::Output {
563        Self::and_all([self, rhs])
564    }
565}
566
567impl BitOr for Expression {
568    type Output = Self;
569
570    fn bitor(self, rhs: Self) -> Self {
571        Self::or_all([self, rhs])
572    }
573}
574
575impl Not for Expression {
576    type Output = Self;
577
578    fn not(self) -> Self {
579        if let Some(v) = self.effective_boolean_value() {
580            (!v).into()
581        } else if let Self::Not(v) = self {
582            if v.returns_boolean() {
583                *v
584            } else {
585                Self::And(vec![*v])
586            }
587        } else {
588            Self::Not(Box::new(self))
589        }
590    }
591}
592
593impl Add for Expression {
594    type Output = Self;
595
596    fn add(self, rhs: Self) -> Self {
597        let (left, right) = order_pair(self, rhs);
598        Self::Add(Box::new(left), Box::new(right))
599    }
600}
601
602impl Sub for Expression {
603    type Output = Self;
604
605    fn sub(self, rhs: Self) -> Self {
606        Self::Subtract(Box::new(self), Box::new(rhs))
607    }
608}
609
610impl Mul for Expression {
611    type Output = Self;
612
613    fn mul(self, rhs: Self) -> Self {
614        let (left, right) = order_pair(self, rhs);
615        Self::Multiply(Box::new(left), Box::new(right))
616    }
617}
618
619impl Div for Expression {
620    type Output = Self;
621
622    fn div(self, rhs: Self) -> Self {
623        Self::Divide(Box::new(self), Box::new(rhs))
624    }
625}
626
627impl Neg for Expression {
628    type Output = Self;
629
630    fn neg(self) -> Self {
631        Self::UnaryMinus(Box::new(self))
632    }
633}
634
635/// A SPARQL query [graph pattern](https://www.w3.org/TR/sparql11-query/#sparqlQuery).
636#[derive(Eq, PartialEq, Debug, Clone, Hash)]
637pub enum GraphPattern {
638    /// A [basic graph pattern](https://www.w3.org/TR/sparql11-query/#defn_BasicGraphPattern).
639    QuadPattern {
640        subject: GroundTermPattern,
641        predicate: NamedNodePattern,
642        object: GroundTermPattern,
643        graph_name: Option<NamedNodePattern>,
644    },
645    /// A [property path pattern](https://www.w3.org/TR/sparql11-query/#defn_evalPP_predicate).
646    Path {
647        subject: GroundTermPattern,
648        path: PropertyPathExpression,
649        object: GroundTermPattern,
650        graph_name: Option<NamedNodePattern>,
651    },
652    /// Graph check
653    ///
654    /// Can yield all named graph like in `GRAPH ?g {}`
655    /// or only check if a graph exist like in `GRAPH ex:g {}`
656    Graph { graph_name: NamedNodePattern },
657    /// [Join](https://www.w3.org/TR/sparql11-query/#defn_algJoin).
658    Join {
659        left: Box<Self>,
660        right: Box<Self>,
661        algorithm: JoinAlgorithm,
662    },
663    /// [LeftJoin](https://www.w3.org/TR/sparql11-query/#defn_algLeftJoin).
664    LeftJoin {
665        left: Box<Self>,
666        right: Box<Self>,
667        expression: Expression,
668        algorithm: LeftJoinAlgorithm,
669    },
670    /// Lateral join i.e. evaluate right for all result row of left
671    #[cfg(feature = "sep-0006")]
672    Lateral { left: Box<Self>, right: Box<Self> },
673    /// [Filter](https://www.w3.org/TR/sparql11-query/#defn_algFilter).
674    Filter {
675        expression: Expression,
676        inner: Box<Self>,
677    },
678    /// [Union](https://www.w3.org/TR/sparql11-query/#defn_algUnion).
679    Union { inner: Vec<Self> },
680    /// [Extend](https://www.w3.org/TR/sparql11-query/#defn_extend).
681    Extend {
682        inner: Box<Self>,
683        variable: Variable,
684        expression: Expression,
685    },
686    /// [Minus](https://www.w3.org/TR/sparql11-query/#defn_algMinus).
687    Minus {
688        left: Box<Self>,
689        right: Box<Self>,
690        algorithm: MinusAlgorithm,
691    },
692    /// A table used to provide inline values
693    Values {
694        variables: Vec<Variable>,
695        bindings: Vec<Vec<Option<GroundTerm>>>,
696    },
697    /// [OrderBy](https://www.w3.org/TR/sparql11-query/#defn_algOrdered).
698    OrderBy {
699        inner: Box<Self>,
700        expression: Vec<OrderExpression>,
701    },
702    /// [Project](https://www.w3.org/TR/sparql11-query/#defn_algProjection).
703    Project {
704        inner: Box<Self>,
705        variables: Vec<Variable>,
706    },
707    /// [Distinct](https://www.w3.org/TR/sparql11-query/#defn_algDistinct).
708    Distinct { inner: Box<Self> },
709    /// [Reduced](https://www.w3.org/TR/sparql11-query/#defn_algReduced).
710    Reduced { inner: Box<Self> },
711    /// [Slice](https://www.w3.org/TR/sparql11-query/#defn_algSlice).
712    Slice {
713        inner: Box<Self>,
714        start: usize,
715        length: Option<usize>,
716    },
717    /// [Group](https://www.w3.org/TR/sparql11-query/#aggregateAlgebra).
718    Group {
719        inner: Box<Self>,
720        variables: Vec<Variable>,
721        aggregates: Vec<(Variable, AggregateExpression)>,
722    },
723    /// [Service](https://www.w3.org/TR/sparql11-federated-query/#defn_evalService).
724    Service {
725        name: NamedNodePattern,
726        inner: Box<Self>,
727        silent: bool,
728    },
729}
730
731impl GraphPattern {
732    pub fn empty() -> Self {
733        Self::Values {
734            variables: Vec::new(),
735            bindings: Vec::new(),
736        }
737    }
738
739    /// Check if the pattern is the empty table
740    fn is_empty(&self) -> bool {
741        if let Self::Values { bindings, .. } = self {
742            bindings.is_empty()
743        } else {
744            false
745        }
746    }
747
748    pub fn empty_singleton() -> Self {
749        Self::Values {
750            variables: Vec::new(),
751            bindings: vec![Vec::new()],
752        }
753    }
754
755    pub fn is_empty_singleton(&self) -> bool {
756        if let Self::Values { bindings, .. } = self {
757            bindings.len() == 1 && bindings.iter().all(|b| b.iter().all(Option::is_none))
758        } else {
759            false
760        }
761    }
762
763    pub fn join(left: Self, right: Self, algorithm: JoinAlgorithm) -> Self {
764        if left.is_empty() || right.is_empty() {
765            return Self::empty();
766        }
767        if left.is_empty_singleton() {
768            return right;
769        }
770        if right.is_empty_singleton() {
771            return left;
772        }
773        Self::Join {
774            left: Box::new(left),
775            right: Box::new(right),
776            algorithm,
777        }
778    }
779
780    #[cfg(feature = "sep-0006")]
781    pub fn lateral(left: Self, right: Self) -> Self {
782        if left.is_empty() || right.is_empty() {
783            return Self::empty();
784        }
785        if left.is_empty_singleton() {
786            return right;
787        }
788        if right.is_empty_singleton() {
789            return left;
790        }
791        Self::Lateral {
792            left: Box::new(left),
793            right: Box::new(right),
794        }
795    }
796
797    pub fn left_join(
798        left: Self,
799        right: Self,
800        expression: Expression,
801        algorithm: LeftJoinAlgorithm,
802    ) -> Self {
803        let expression_ebv = expression.effective_boolean_value();
804        if left.is_empty()
805            || right.is_empty()
806            || right.is_empty_singleton()
807            || expression_ebv == Some(false)
808        {
809            return left;
810        }
811        Self::LeftJoin {
812            left: Box::new(left),
813            right: Box::new(right),
814            expression: if expression_ebv == Some(true) {
815                true.into()
816            } else {
817                expression
818            },
819            algorithm,
820        }
821    }
822
823    pub fn minus(left: Self, right: Self, algorithm: MinusAlgorithm) -> Self {
824        if left.is_empty() {
825            return Self::empty();
826        }
827        if right.is_empty() {
828            return left;
829        }
830        Self::Minus {
831            left: Box::new(left),
832            right: Box::new(right),
833            algorithm,
834        }
835    }
836
837    pub fn union(left: Self, right: Self) -> Self {
838        Self::union_all([left, right])
839    }
840
841    pub fn union_all(args: impl IntoIterator<Item = Self>) -> Self {
842        let args = args.into_iter();
843        let mut all = Vec::with_capacity(args.size_hint().0);
844        for arg in args {
845            if arg.is_empty() {
846                continue;
847            }
848            if let Self::Union { inner } = arg {
849                all.extend(inner);
850            } else {
851                all.push(arg);
852            }
853        }
854        if all.is_empty() {
855            Self::empty()
856        } else {
857            Self::Union {
858                inner: order_vec(all),
859            }
860        }
861    }
862
863    pub fn filter(inner: Self, expression: Expression) -> Self {
864        if inner.is_empty() {
865            return Self::empty();
866        }
867        // We unwrap singleton And
868        let expression = match expression {
869            Expression::And(mut l) if l.len() == 1 => l.pop().unwrap(),
870            e => e,
871        };
872        match expression.effective_boolean_value() {
873            Some(true) => inner,
874            Some(false) => Self::empty(),
875            None => match inner {
876                Self::Filter {
877                    inner: nested_inner,
878                    expression: e2,
879                } => Self::Filter {
880                    inner: nested_inner,
881                    expression: expression & e2,
882                },
883                _ => Self::Filter {
884                    inner: Box::new(inner),
885                    expression,
886                },
887            },
888        }
889    }
890
891    pub fn extend(inner: Self, variable: Variable, expression: Expression) -> Self {
892        if inner.is_empty() {
893            return Self::empty();
894        }
895        Self::Extend {
896            inner: Box::new(inner),
897            variable,
898            expression,
899        }
900    }
901
902    pub fn values(
903        mut variables: Vec<Variable>,
904        mut bindings: Vec<Vec<Option<GroundTerm>>>,
905    ) -> Self {
906        let empty_rows = (0..variables.len())
907            .filter(|row| !bindings.iter().any(|binding| binding.get(*row).is_some()))
908            .collect::<Vec<_>>();
909        if !empty_rows.is_empty() {
910            // We remove empty rows
911            variables = variables
912                .into_iter()
913                .enumerate()
914                .filter_map(|(i, v)| {
915                    if empty_rows.contains(&i) {
916                        None
917                    } else {
918                        Some(v)
919                    }
920                })
921                .collect();
922            bindings = bindings
923                .into_iter()
924                .map(|binding| {
925                    binding
926                        .into_iter()
927                        .enumerate()
928                        .filter_map(|(i, v)| {
929                            if empty_rows.contains(&i) {
930                                None
931                            } else {
932                                Some(v)
933                            }
934                        })
935                        .collect()
936                })
937                .collect();
938        }
939        Self::Values {
940            variables,
941            bindings,
942        }
943    }
944
945    pub fn order_by(inner: Self, expression: Vec<OrderExpression>) -> Self {
946        if inner.is_empty() {
947            return Self::empty();
948        }
949        if expression.is_empty() {
950            return inner;
951        }
952        Self::OrderBy {
953            inner: Box::new(inner),
954            expression,
955        }
956    }
957
958    pub fn project(inner: Self, variables: Vec<Variable>) -> Self {
959        Self::Project {
960            inner: Box::new(inner),
961            variables,
962        }
963    }
964
965    pub fn distinct(inner: Self) -> Self {
966        if inner.is_empty() {
967            return Self::empty();
968        }
969        Self::Distinct {
970            inner: Box::new(inner),
971        }
972    }
973
974    pub fn reduced(inner: Self) -> Self {
975        if inner.is_empty() {
976            return Self::empty();
977        }
978        Self::Reduced {
979            inner: Box::new(inner),
980        }
981    }
982
983    pub fn slice(inner: Self, start: usize, length: Option<usize>) -> Self {
984        if inner.is_empty() {
985            return Self::empty();
986        }
987        if start == 0 && length.is_none() {
988            return inner;
989        }
990        Self::Slice {
991            inner: Box::new(inner),
992            start,
993            length,
994        }
995    }
996
997    pub fn group(
998        inner: Self,
999        variables: Vec<Variable>,
1000        aggregates: Vec<(Variable, AggregateExpression)>,
1001    ) -> Self {
1002        if inner.is_empty() {
1003            return Self::empty();
1004        }
1005        Self::Group {
1006            inner: Box::new(inner),
1007            variables,
1008            aggregates,
1009        }
1010    }
1011
1012    pub fn service(inner: Self, name: NamedNodePattern, silent: bool) -> Self {
1013        Self::Service {
1014            inner: Box::new(inner),
1015            name,
1016            silent,
1017        }
1018    }
1019
1020    pub fn lookup_used_variables<'a>(&'a self, callback: &mut impl FnMut(&'a Variable)) {
1021        match self {
1022            Self::Values { variables, .. } | Self::Project { variables, .. } => {
1023                for v in variables {
1024                    callback(v);
1025                }
1026            }
1027            Self::QuadPattern {
1028                subject,
1029                predicate,
1030                object,
1031                graph_name,
1032            } => {
1033                lookup_term_pattern_variables(subject, callback);
1034                if let NamedNodePattern::Variable(v) = predicate {
1035                    callback(v);
1036                }
1037                lookup_term_pattern_variables(object, callback);
1038                if let Some(NamedNodePattern::Variable(v)) = graph_name {
1039                    callback(v);
1040                }
1041            }
1042            Self::Path {
1043                subject,
1044                object,
1045                graph_name,
1046                ..
1047            } => {
1048                lookup_term_pattern_variables(subject, callback);
1049                lookup_term_pattern_variables(object, callback);
1050                if let Some(NamedNodePattern::Variable(v)) = graph_name {
1051                    callback(v);
1052                }
1053            }
1054            Self::Graph { graph_name } => {
1055                if let NamedNodePattern::Variable(v) = graph_name {
1056                    callback(v);
1057                }
1058            }
1059            Self::Filter { inner, expression } => {
1060                expression.lookup_used_variables(callback);
1061                inner.lookup_used_variables(callback);
1062            }
1063            Self::Union { inner } => {
1064                for child in inner {
1065                    child.lookup_used_variables(callback);
1066                }
1067            }
1068            Self::Join { left, right, .. } | Self::Minus { left, right, .. } => {
1069                left.lookup_used_variables(callback);
1070                right.lookup_used_variables(callback);
1071            }
1072            #[cfg(feature = "sep-0006")]
1073            Self::Lateral { left, right } => {
1074                left.lookup_used_variables(callback);
1075                right.lookup_used_variables(callback);
1076            }
1077            Self::LeftJoin {
1078                left,
1079                right,
1080                expression,
1081                ..
1082            } => {
1083                expression.lookup_used_variables(callback);
1084                left.lookup_used_variables(callback);
1085                right.lookup_used_variables(callback);
1086            }
1087            Self::Extend {
1088                inner,
1089                variable,
1090                expression,
1091            } => {
1092                callback(variable);
1093                expression.lookup_used_variables(callback);
1094                inner.lookup_used_variables(callback);
1095            }
1096            Self::OrderBy { inner, .. }
1097            | Self::Distinct { inner }
1098            | Self::Reduced { inner }
1099            | Self::Slice { inner, .. } => inner.lookup_used_variables(callback),
1100            Self::Service { inner, name, .. } => {
1101                if let NamedNodePattern::Variable(v) = name {
1102                    callback(v);
1103                }
1104                inner.lookup_used_variables(callback);
1105            }
1106            Self::Group {
1107                variables,
1108                aggregates,
1109                ..
1110            } => {
1111                for v in variables {
1112                    callback(v);
1113                }
1114                for (v, _) in aggregates {
1115                    callback(v);
1116                }
1117            }
1118        }
1119    }
1120
1121    fn from_sparql_algebra(
1122        pattern: &AlGraphPattern,
1123        graph_name: Option<&NamedNodePattern>,
1124        blank_nodes: &mut HashMap<BlankNode, Variable>,
1125    ) -> Self {
1126        match pattern {
1127            AlGraphPattern::Bgp { patterns } => patterns
1128                .iter()
1129                .map(|p| {
1130                    let (subject, predicate, object) =
1131                        Self::triple_pattern_from_algebra(p, blank_nodes);
1132                    Self::QuadPattern {
1133                        subject,
1134                        predicate,
1135                        object,
1136                        graph_name: graph_name.cloned(),
1137                    }
1138                })
1139                .reduce(|a, b| Self::Join {
1140                    left: Box::new(a),
1141                    right: Box::new(b),
1142                    algorithm: JoinAlgorithm::default(),
1143                })
1144                .unwrap_or_else(|| {
1145                    if let Some(graph_name) = graph_name {
1146                        Self::Graph {
1147                            graph_name: graph_name.clone(),
1148                        }
1149                    } else {
1150                        Self::empty_singleton()
1151                    }
1152                }),
1153            AlGraphPattern::Path {
1154                subject,
1155                path,
1156                object,
1157            } => Self::Path {
1158                subject: Self::term_pattern_from_algebra(subject, blank_nodes),
1159                path: path.clone(),
1160                object: Self::term_pattern_from_algebra(object, blank_nodes),
1161                graph_name: graph_name.cloned(),
1162            },
1163            AlGraphPattern::Join { left, right } => Self::Join {
1164                left: Box::new(Self::from_sparql_algebra(left, graph_name, blank_nodes)),
1165                right: Box::new(Self::from_sparql_algebra(right, graph_name, blank_nodes)),
1166                algorithm: JoinAlgorithm::default(),
1167            },
1168            AlGraphPattern::LeftJoin {
1169                left,
1170                right,
1171                expression,
1172            } => Self::LeftJoin {
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                expression: expression.as_ref().map_or_else(
1176                    || true.into(),
1177                    |e| Expression::from_sparql_algebra(e, graph_name),
1178                ),
1179                algorithm: LeftJoinAlgorithm::default(),
1180            },
1181            #[cfg(feature = "sep-0006")]
1182            AlGraphPattern::Lateral { left, right } => Self::Lateral {
1183                left: Box::new(Self::from_sparql_algebra(left, graph_name, blank_nodes)),
1184                right: Box::new(Self::from_sparql_algebra(right, graph_name, blank_nodes)),
1185            },
1186            AlGraphPattern::Filter { inner, expr } => Self::Filter {
1187                inner: Box::new(Self::from_sparql_algebra(inner, graph_name, blank_nodes)),
1188                expression: Expression::from_sparql_algebra(expr, graph_name),
1189            },
1190            AlGraphPattern::Union { left, right } => Self::Union {
1191                inner: vec![
1192                    Self::from_sparql_algebra(left, graph_name, blank_nodes),
1193                    Self::from_sparql_algebra(right, graph_name, blank_nodes),
1194                ],
1195            },
1196            AlGraphPattern::Graph { inner, name } => {
1197                Self::from_sparql_algebra(inner, Some(name), blank_nodes)
1198            }
1199            AlGraphPattern::Extend {
1200                inner,
1201                expression,
1202                variable,
1203            } => Self::Extend {
1204                inner: Box::new(Self::from_sparql_algebra(inner, graph_name, blank_nodes)),
1205                expression: Expression::from_sparql_algebra(expression, graph_name),
1206                variable: variable.clone(),
1207            },
1208            AlGraphPattern::Minus { left, right } => Self::Minus {
1209                left: Box::new(Self::from_sparql_algebra(left, graph_name, blank_nodes)),
1210                right: Box::new(Self::from_sparql_algebra(right, graph_name, blank_nodes)),
1211                algorithm: MinusAlgorithm::default(),
1212            },
1213            AlGraphPattern::Values {
1214                variables,
1215                bindings,
1216            } => Self::Values {
1217                variables: variables.clone(),
1218                bindings: bindings.clone(),
1219            },
1220            AlGraphPattern::OrderBy { inner, expression } => Self::OrderBy {
1221                inner: Box::new(Self::from_sparql_algebra(inner, graph_name, blank_nodes)),
1222                expression: expression
1223                    .iter()
1224                    .map(|e| OrderExpression::from_sparql_algebra(e, graph_name))
1225                    .collect(),
1226            },
1227            AlGraphPattern::Project { inner, variables } => {
1228                let graph_name = if let Some(NamedNodePattern::Variable(graph_name)) = graph_name {
1229                    Some(NamedNodePattern::Variable(
1230                        if variables.contains(graph_name) {
1231                            graph_name.clone()
1232                        } else {
1233                            new_var()
1234                        },
1235                    ))
1236                } else {
1237                    graph_name.cloned()
1238                };
1239                Self::Project {
1240                    inner: Box::new(Self::from_sparql_algebra(
1241                        inner,
1242                        graph_name.as_ref(),
1243                        &mut HashMap::new(),
1244                    )),
1245                    variables: variables.clone(),
1246                }
1247            }
1248            AlGraphPattern::Distinct { inner } => Self::Distinct {
1249                inner: Box::new(Self::from_sparql_algebra(inner, graph_name, blank_nodes)),
1250            },
1251            AlGraphPattern::Reduced { inner } => Self::Distinct {
1252                inner: Box::new(Self::from_sparql_algebra(inner, graph_name, blank_nodes)),
1253            },
1254            AlGraphPattern::Slice {
1255                inner,
1256                start,
1257                length,
1258            } => Self::Slice {
1259                inner: Box::new(Self::from_sparql_algebra(inner, graph_name, blank_nodes)),
1260                start: *start,
1261                length: *length,
1262            },
1263            AlGraphPattern::Group {
1264                inner,
1265                variables,
1266                aggregates,
1267            } => Self::Group {
1268                inner: Box::new(Self::from_sparql_algebra(inner, graph_name, blank_nodes)),
1269                variables: variables.clone(),
1270                aggregates: aggregates
1271                    .iter()
1272                    .map(|(var, expr)| {
1273                        (
1274                            var.clone(),
1275                            AggregateExpression::from_sparql_algebra(expr, graph_name),
1276                        )
1277                    })
1278                    .collect(),
1279            },
1280            AlGraphPattern::Service {
1281                inner,
1282                name,
1283                silent,
1284            } => Self::Service {
1285                inner: Box::new(Self::from_sparql_algebra(inner, graph_name, blank_nodes)),
1286                name: name.clone(),
1287                silent: *silent,
1288            },
1289        }
1290    }
1291
1292    fn triple_pattern_from_algebra(
1293        pattern: &TriplePattern,
1294        blank_nodes: &mut HashMap<BlankNode, Variable>,
1295    ) -> (GroundTermPattern, NamedNodePattern, GroundTermPattern) {
1296        (
1297            Self::term_pattern_from_algebra(&pattern.subject, blank_nodes),
1298            pattern.predicate.clone(),
1299            Self::term_pattern_from_algebra(&pattern.object, blank_nodes),
1300        )
1301    }
1302
1303    fn term_pattern_from_algebra(
1304        pattern: &TermPattern,
1305        blank_nodes: &mut HashMap<BlankNode, Variable>,
1306    ) -> GroundTermPattern {
1307        match pattern {
1308            TermPattern::NamedNode(node) => node.clone().into(),
1309            TermPattern::BlankNode(node) => blank_nodes
1310                .entry(node.clone())
1311                .or_insert_with(new_var)
1312                .clone()
1313                .into(),
1314            TermPattern::Literal(literal) => literal.clone().into(),
1315            #[cfg(feature = "rdf-star")]
1316            TermPattern::Triple(pattern) => {
1317                let (subject, predicate, object) =
1318                    Self::triple_pattern_from_algebra(pattern, blank_nodes);
1319                GroundTriplePattern {
1320                    subject,
1321                    predicate,
1322                    object,
1323                }
1324                .into()
1325            }
1326            TermPattern::Variable(variable) => variable.clone().into(),
1327        }
1328    }
1329}
1330
1331impl From<&AlGraphPattern> for GraphPattern {
1332    fn from(pattern: &AlGraphPattern) -> Self {
1333        Self::from_sparql_algebra(pattern, None, &mut HashMap::new())
1334    }
1335}
1336
1337impl From<&GraphPattern> for AlGraphPattern {
1338    fn from(pattern: &GraphPattern) -> Self {
1339        match pattern {
1340            GraphPattern::QuadPattern {
1341                subject,
1342                predicate,
1343                object,
1344                graph_name,
1345            } => {
1346                let pattern = Self::Bgp {
1347                    patterns: vec![TriplePattern {
1348                        subject: subject.clone().into(),
1349                        predicate: predicate.clone(),
1350                        object: object.clone().into(),
1351                    }],
1352                };
1353                if let Some(graph_name) = graph_name {
1354                    Self::Graph {
1355                        inner: Box::new(pattern),
1356                        name: graph_name.clone(),
1357                    }
1358                } else {
1359                    pattern
1360                }
1361            }
1362            GraphPattern::Path {
1363                subject,
1364                path,
1365                object,
1366                graph_name,
1367            } => {
1368                let pattern = Self::Path {
1369                    subject: subject.clone().into(),
1370                    path: path.clone(),
1371                    object: object.clone().into(),
1372                };
1373                if let Some(graph_name) = graph_name {
1374                    Self::Graph {
1375                        inner: Box::new(pattern),
1376                        name: graph_name.clone(),
1377                    }
1378                } else {
1379                    pattern
1380                }
1381            }
1382            GraphPattern::Graph { graph_name } => Self::Graph {
1383                inner: Box::new(AlGraphPattern::Bgp {
1384                    patterns: Vec::new(),
1385                }),
1386                name: graph_name.clone(),
1387            },
1388            GraphPattern::Join { left, right, .. } => {
1389                match (left.as_ref().into(), right.as_ref().into()) {
1390                    (Self::Bgp { patterns: mut left }, Self::Bgp { patterns: right }) => {
1391                        left.extend(right);
1392                        Self::Bgp { patterns: left }
1393                    }
1394                    (left, right) => Self::Join {
1395                        left: Box::new(left),
1396                        right: Box::new(right),
1397                    },
1398                }
1399            }
1400            GraphPattern::LeftJoin {
1401                left,
1402                right,
1403                expression,
1404                ..
1405            } => {
1406                let empty_expr = if let Expression::Literal(l) = expression {
1407                    l.datatype() == xsd::BOOLEAN && l.value() == "true"
1408                } else {
1409                    false
1410                };
1411                Self::LeftJoin {
1412                    left: Box::new(left.as_ref().into()),
1413                    right: Box::new(right.as_ref().into()),
1414                    expression: if empty_expr {
1415                        None
1416                    } else {
1417                        Some(expression.into())
1418                    },
1419                }
1420            }
1421            #[cfg(feature = "sep-0006")]
1422            GraphPattern::Lateral { left, right } => {
1423                match (left.as_ref().into(), right.as_ref().into()) {
1424                    (Self::Bgp { patterns: mut left }, Self::Bgp { patterns: right }) => {
1425                        left.extend(right);
1426                        Self::Bgp { patterns: left }
1427                    }
1428                    (left, right) => Self::Lateral {
1429                        left: Box::new(left),
1430                        right: Box::new(right),
1431                    },
1432                }
1433            }
1434            GraphPattern::Filter { inner, expression } => Self::Filter {
1435                inner: Box::new(inner.as_ref().into()),
1436                expr: expression.into(),
1437            },
1438            GraphPattern::Union { inner } => inner
1439                .iter()
1440                .map(Into::into)
1441                .reduce(|a, b| Self::Union {
1442                    left: Box::new(a),
1443                    right: Box::new(b),
1444                })
1445                .unwrap_or_else(|| Self::Values {
1446                    variables: Vec::new(),
1447                    bindings: Vec::new(),
1448                }),
1449            GraphPattern::Extend {
1450                inner,
1451                expression,
1452                variable,
1453            } => Self::Extend {
1454                inner: Box::new(inner.as_ref().into()),
1455                expression: expression.into(),
1456                variable: variable.clone(),
1457            },
1458            GraphPattern::Minus { left, right, .. } => Self::Minus {
1459                left: Box::new(left.as_ref().into()),
1460                right: Box::new(right.as_ref().into()),
1461            },
1462            GraphPattern::Values {
1463                variables,
1464                bindings,
1465            } => Self::Values {
1466                variables: variables.clone(),
1467                bindings: bindings.clone(),
1468            },
1469            GraphPattern::OrderBy { inner, expression } => Self::OrderBy {
1470                inner: Box::new(inner.as_ref().into()),
1471                expression: expression.iter().map(Into::into).collect(),
1472            },
1473            GraphPattern::Project { inner, variables } => Self::Project {
1474                inner: Box::new(inner.as_ref().into()),
1475                variables: variables.clone(),
1476            },
1477            GraphPattern::Distinct { inner } => Self::Distinct {
1478                inner: Box::new(inner.as_ref().into()),
1479            },
1480            GraphPattern::Reduced { inner } => Self::Distinct {
1481                inner: Box::new(inner.as_ref().into()),
1482            },
1483            GraphPattern::Slice {
1484                inner,
1485                start,
1486                length,
1487            } => Self::Slice {
1488                inner: Box::new(inner.as_ref().into()),
1489                start: *start,
1490                length: *length,
1491            },
1492            GraphPattern::Group {
1493                inner,
1494                variables,
1495                aggregates,
1496            } => Self::Group {
1497                inner: Box::new(inner.as_ref().into()),
1498                variables: variables.clone(),
1499                aggregates: aggregates
1500                    .iter()
1501                    .map(|(var, expr)| (var.clone(), expr.into()))
1502                    .collect(),
1503            },
1504            GraphPattern::Service {
1505                inner,
1506                name,
1507                silent,
1508            } => Self::Service {
1509                inner: Box::new(inner.as_ref().into()),
1510                name: name.clone(),
1511                silent: *silent,
1512            },
1513        }
1514    }
1515}
1516
1517/// The join algorithm used (c.f. [`GraphPattern::Join`]).
1518#[derive(Eq, PartialEq, Debug, Clone, Hash)]
1519pub enum JoinAlgorithm {
1520    HashBuildLeftProbeRight { keys: Vec<Variable> },
1521}
1522
1523impl Default for JoinAlgorithm {
1524    fn default() -> Self {
1525        Self::HashBuildLeftProbeRight {
1526            keys: Vec::default(),
1527        }
1528    }
1529}
1530
1531/// The left join algorithm used (c.f. [`GraphPattern::LeftJoin`]).
1532#[derive(Eq, PartialEq, Debug, Clone, Hash)]
1533pub enum LeftJoinAlgorithm {
1534    HashBuildRightProbeLeft { keys: Vec<Variable> },
1535}
1536
1537impl Default for LeftJoinAlgorithm {
1538    fn default() -> Self {
1539        Self::HashBuildRightProbeLeft {
1540            keys: Vec::default(),
1541        }
1542    }
1543}
1544
1545/// The left join algorithm used (c.f. [`GraphPattern::Minus`]).
1546#[derive(Eq, PartialEq, Debug, Clone, Hash)]
1547pub enum MinusAlgorithm {
1548    HashBuildRightProbeLeft { keys: Vec<Variable> },
1549}
1550
1551impl Default for MinusAlgorithm {
1552    fn default() -> Self {
1553        Self::HashBuildRightProbeLeft {
1554            keys: Vec::default(),
1555        }
1556    }
1557}
1558
1559/// A set function used in aggregates (c.f. [`GraphPattern::Group`]).
1560#[derive(Eq, PartialEq, Debug, Clone, Hash)]
1561pub enum AggregateExpression {
1562    CountSolutions {
1563        distinct: bool,
1564    },
1565    FunctionCall {
1566        name: AggregateFunction,
1567        expr: Expression,
1568        distinct: bool,
1569    },
1570}
1571
1572impl AggregateExpression {
1573    fn from_sparql_algebra(
1574        expression: &AlAggregateExpression,
1575        graph_name: Option<&NamedNodePattern>,
1576    ) -> Self {
1577        match expression {
1578            AlAggregateExpression::CountSolutions { distinct } => Self::CountSolutions {
1579                distinct: *distinct,
1580            },
1581            AlAggregateExpression::FunctionCall {
1582                name,
1583                expr,
1584                distinct,
1585            } => Self::FunctionCall {
1586                name: name.clone(),
1587                expr: Expression::from_sparql_algebra(expr, graph_name),
1588                distinct: *distinct,
1589            },
1590        }
1591    }
1592}
1593
1594impl From<&AggregateExpression> for AlAggregateExpression {
1595    fn from(expression: &AggregateExpression) -> Self {
1596        match expression {
1597            AggregateExpression::CountSolutions { distinct } => Self::CountSolutions {
1598                distinct: *distinct,
1599            },
1600            AggregateExpression::FunctionCall {
1601                name,
1602                expr,
1603                distinct,
1604            } => Self::FunctionCall {
1605                name: name.clone(),
1606                expr: expr.into(),
1607                distinct: *distinct,
1608            },
1609        }
1610    }
1611}
1612
1613/// An ordering comparator used by [`GraphPattern::OrderBy`].
1614#[derive(Eq, PartialEq, Debug, Clone, Hash)]
1615pub enum OrderExpression {
1616    /// Ascending order
1617    Asc(Expression),
1618    /// Descending order
1619    Desc(Expression),
1620}
1621
1622impl OrderExpression {
1623    fn from_sparql_algebra(
1624        expression: &AlOrderExpression,
1625        graph_name: Option<&NamedNodePattern>,
1626    ) -> Self {
1627        match expression {
1628            AlOrderExpression::Asc(e) => Self::Asc(Expression::from_sparql_algebra(e, graph_name)),
1629            AlOrderExpression::Desc(e) => {
1630                Self::Desc(Expression::from_sparql_algebra(e, graph_name))
1631            }
1632        }
1633    }
1634}
1635
1636impl From<&OrderExpression> for AlOrderExpression {
1637    fn from(expression: &OrderExpression) -> Self {
1638        match expression {
1639            OrderExpression::Asc(e) => Self::Asc(e.into()),
1640            OrderExpression::Desc(e) => Self::Desc(e.into()),
1641        }
1642    }
1643}
1644
1645fn new_var() -> Variable {
1646    Variable::new_unchecked(format!("{:x}", random::<u128>()))
1647}
1648
1649fn order_pair<T: Hash>(a: T, b: T) -> (T, T) {
1650    if hash(&a) <= hash(&b) {
1651        (a, b)
1652    } else {
1653        (b, a)
1654    }
1655}
1656
1657fn order_vec<T: Hash>(mut vec: Vec<T>) -> Vec<T> {
1658    vec.sort_unstable_by_key(|a| hash(a));
1659    vec
1660}
1661
1662fn hash(v: impl Hash) -> u64 {
1663    let mut hasher = DefaultHasher::new();
1664    v.hash(&mut hasher);
1665    hasher.finish()
1666}
1667
1668fn lookup_term_pattern_variables<'a>(
1669    pattern: &'a GroundTermPattern,
1670    callback: &mut impl FnMut(&'a Variable),
1671) {
1672    if let GroundTermPattern::Variable(v) = pattern {
1673        callback(v);
1674    }
1675    #[cfg(feature = "rdf-star")]
1676    if let GroundTermPattern::Triple(t) = pattern {
1677        lookup_term_pattern_variables(&t.subject, callback);
1678        if let NamedNodePattern::Variable(v) = &t.predicate {
1679            callback(v);
1680        }
1681        lookup_term_pattern_variables(&t.object, callback);
1682    }
1683}
sparopt/algebra.rs

sparopt/
algebra.rs
