src/rdflib/plugins/sparql/algebra.py
1"""
2Converting the 'parse-tree' output of pyparsing to a SPARQL Algebra expression
3
4http://www.w3.org/TR/sparql11-query/#sparqlQuery
5"""
6
7from __future__ import annotations
8
9import collections
10import functools
11import operator
12import typing
13from functools import reduce
14from typing import (
15 Any,
16 Callable,
17 DefaultDict,
18 Dict,
19 Iterable,
20 List,
21 Mapping,
22 Optional,
23 Set,
24 Tuple,
25 overload,
26)
27
28from pyparsing import ParseResults
29
30from rdflib.paths import (
31 AlternativePath,
32 InvPath,
33 MulPath,
34 NegatedPath,
35 Path,
36 SequencePath,
37)
38from rdflib.plugins.sparql.operators import TrueFilter, and_
39from rdflib.plugins.sparql.operators import simplify as simplifyFilters
40from rdflib.plugins.sparql.parserutils import CompValue, Expr
41from rdflib.plugins.sparql.sparql import Prologue, Query, Update
42
43# ---------------------------
44# Some convenience methods
45from rdflib.term import BNode, Identifier, Literal, URIRef, Variable
46
47
48def OrderBy(p: CompValue, expr: List[CompValue]) -> CompValue:
49 return CompValue("OrderBy", p=p, expr=expr)
50
51
52def ToMultiSet(p: typing.Union[List[Dict[Variable, str]], CompValue]) -> CompValue:
53 return CompValue("ToMultiSet", p=p)
54
55
56def Union(p1: CompValue, p2: CompValue) -> CompValue:
57 return CompValue("Union", p1=p1, p2=p2)
58
59
60def Join(p1: CompValue, p2: Optional[CompValue]) -> CompValue:
61 return CompValue("Join", p1=p1, p2=p2)
62
63
64def Minus(p1: CompValue, p2: CompValue) -> CompValue:
65 return CompValue("Minus", p1=p1, p2=p2)
66
67
68def Graph(term: Identifier, graph: CompValue) -> CompValue:
69 return CompValue("Graph", term=term, p=graph)
70
71
72def BGP(
73 triples: Optional[List[Tuple[Identifier, Identifier, Identifier]]] = None
74) -> CompValue:
75 return CompValue("BGP", triples=triples or [])
76
77
78def LeftJoin(p1: CompValue, p2: CompValue, expr) -> CompValue:
79 return CompValue("LeftJoin", p1=p1, p2=p2, expr=expr)
80
81
82def Filter(expr: Expr, p: CompValue) -> CompValue:
83 return CompValue("Filter", expr=expr, p=p)
84
85
86def Extend(
87 p: CompValue, expr: typing.Union[Identifier, Expr], var: Variable
88) -> CompValue:
89 return CompValue("Extend", p=p, expr=expr, var=var)
90
91
92def Values(res: List[Dict[Variable, str]]) -> CompValue:
93 return CompValue("values", res=res)
94
95
96def Project(p: CompValue, PV: List[Variable]) -> CompValue:
97 return CompValue("Project", p=p, PV=PV)
98
99
100def Group(p: CompValue, expr: Optional[List[Variable]] = None) -> CompValue:
101 return CompValue("Group", p=p, expr=expr)
102
103
104def _knownTerms(
105 triple: Tuple[Identifier, Identifier, Identifier],
106 varsknown: Set[typing.Union[BNode, Variable]],
107 varscount: Dict[Identifier, int],
108) -> Tuple[int, int, bool]:
109 return (
110 len(
111 [
112 x
113 for x in triple
114 if x not in varsknown and isinstance(x, (Variable, BNode))
115 ]
116 ),
117 -sum(varscount.get(x, 0) for x in triple),
118 not isinstance(triple[2], Literal),
119 )
120
121
122def reorderTriples(
123 l_: Iterable[Tuple[Identifier, Identifier, Identifier]]
124) -> List[Tuple[Identifier, Identifier, Identifier]]:
125 """
126 Reorder triple patterns so that we execute the
127 ones with most bindings first
128 """
129
130 def _addvar(term: str, varsknown: Set[typing.Union[Variable, BNode]]):
131 if isinstance(term, (Variable, BNode)):
132 varsknown.add(term)
133
134 # NOTE on type errors: most of these are because the same variable is used
135 # for different types.
136
137 # type error: List comprehension has incompatible type List[Tuple[None, Tuple[Identifier, Identifier, Identifier]]]; expected List[Tuple[Identifier, Identifier, Identifier]]
138 l_ = [(None, x) for x in l_] # type: ignore[misc]
139 varsknown: Set[typing.Union[BNode, Variable]] = set()
140 varscount: Dict[Identifier, int] = collections.defaultdict(int)
141 for t in l_:
142 for c in t[1]:
143 if isinstance(c, (Variable, BNode)):
144 varscount[c] += 1
145 i = 0
146
147 # Done in steps, sort by number of bound terms
148 # the top block of patterns with the most bound terms is kept
149 # the rest is resorted based on the vars bound after the first
150 # block is evaluated
151
152 # we sort by decorate/undecorate, since we need the value of the sort keys
153
154 while i < len(l_):
155 # type error: Generator has incompatible item type "Tuple[Any, Identifier]"; expected "Tuple[Identifier, Identifier, Identifier]"
156 # type error: Argument 1 to "_knownTerms" has incompatible type "Identifier"; expected "Tuple[Identifier, Identifier, Identifier]"
157 l_[i:] = sorted((_knownTerms(x[1], varsknown, varscount), x[1]) for x in l_[i:]) # type: ignore[misc,arg-type]
158 # type error: Incompatible types in assignment (expression has type "str", variable has type "Tuple[Identifier, Identifier, Identifier]")
159 t = l_[i][0][0] # type: ignore[assignment] # top block has this many terms bound
160 j = 0
161 while i + j < len(l_) and l_[i + j][0][0] == t:
162 for c in l_[i + j][1]:
163 _addvar(c, varsknown)
164 j += 1
165 i += 1
166
167 # type error: List comprehension has incompatible type List[Identifier]; expected List[Tuple[Identifier, Identifier, Identifier]]
168 return [x[1] for x in l_] # type: ignore[misc]
169
170
171def triples(
172 l: typing.Union[ # noqa: E741
173 List[List[Identifier]], List[Tuple[Identifier, Identifier, Identifier]]
174 ]
175) -> List[Tuple[Identifier, Identifier, Identifier]]:
176 _l = reduce(lambda x, y: x + y, l)
177 if (len(_l) % 3) != 0:
178 raise Exception("these aint triples")
179 return reorderTriples((_l[x], _l[x + 1], _l[x + 2]) for x in range(0, len(_l), 3))
180
181
182# type error: Missing return statement
183def translatePName( # type: ignore[return]
184 p: typing.Union[CompValue, str], prologue: Prologue
185) -> Optional[Identifier]:
186 """
187 Expand prefixed/relative URIs
188 """
189 if isinstance(p, CompValue):
190 if p.name == "pname":
191 # type error: Incompatible return value type (got "Union[CompValue, str, None]", expected "Optional[Identifier]")
192 return prologue.absolutize(p) # type: ignore[return-value]
193 if p.name == "literal":
194 # type error: Argument "datatype" to "Literal" has incompatible type "Union[CompValue, str, None]"; expected "Optional[str]"
195 return Literal(
196 p.string, lang=p.lang, datatype=prologue.absolutize(p.datatype) # type: ignore[arg-type]
197 )
198 elif isinstance(p, URIRef):
199 # type error: Incompatible return value type (got "Union[CompValue, str, None]", expected "Optional[Identifier]")
200 return prologue.absolutize(p) # type: ignore[return-value]
201
202
203@overload
204def translatePath(p: URIRef) -> None: ...
205
206
207@overload
208def translatePath(p: CompValue) -> Path: ...
209
210
211# type error: Missing return statement
212def translatePath(p: typing.Union[CompValue, URIRef]) -> Optional[Path]: # type: ignore[return]
213 """
214 Translate PropertyPath expressions
215 """
216
217 if isinstance(p, CompValue):
218 if p.name == "PathAlternative":
219 if len(p.part) == 1:
220 return p.part[0]
221 else:
222 return AlternativePath(*p.part)
223
224 elif p.name == "PathSequence":
225 if len(p.part) == 1:
226 return p.part[0]
227 else:
228 return SequencePath(*p.part)
229
230 elif p.name == "PathElt":
231 if not p.mod:
232 return p.part
233 else:
234 if isinstance(p.part, list):
235 if len(p.part) != 1:
236 raise Exception("Denkfehler!")
237
238 return MulPath(p.part[0], p.mod)
239 else:
240 return MulPath(p.part, p.mod)
241
242 elif p.name == "PathEltOrInverse":
243 if isinstance(p.part, list):
244 if len(p.part) != 1:
245 raise Exception("Denkfehler!")
246 return InvPath(p.part[0])
247 else:
248 return InvPath(p.part)
249
250 elif p.name == "PathNegatedPropertySet":
251 if isinstance(p.part, list):
252 return NegatedPath(AlternativePath(*p.part))
253 else:
254 return NegatedPath(p.part)
255
256
257def translateExists(
258 e: typing.Union[Expr, Literal, Variable, URIRef]
259) -> typing.Union[Expr, Literal, Variable, URIRef]:
260 """
261 Translate the graph pattern used by EXISTS and NOT EXISTS
262 http://www.w3.org/TR/sparql11-query/#sparqlCollectFilters
263 """
264
265 def _c(n):
266 if isinstance(n, CompValue):
267 if n.name in ("Builtin_EXISTS", "Builtin_NOTEXISTS"):
268 n.graph = translateGroupGraphPattern(n.graph)
269 if n.graph.name == "Filter":
270 # filters inside (NOT) EXISTS can see vars bound outside
271 n.graph.no_isolated_scope = True
272
273 e = traverse(e, visitPost=_c)
274
275 return e
276
277
278def collectAndRemoveFilters(parts: List[CompValue]) -> Optional[Expr]:
279 """FILTER expressions apply to the whole group graph pattern in which
280 they appear.
281
282 http://www.w3.org/TR/sparql11-query/#sparqlCollectFilters
283 """
284
285 filters = []
286
287 i = 0
288 while i < len(parts):
289 p = parts[i]
290 if p.name == "Filter":
291 filters.append(translateExists(p.expr))
292 parts.pop(i)
293 else:
294 i += 1
295
296 if filters:
297 # type error: Argument 1 to "and_" has incompatible type "*List[Union[Expr, Literal, Variable]]"; expected "Expr"
298 return and_(*filters) # type: ignore[arg-type]
299
300 return None
301
302
303def translateGroupOrUnionGraphPattern(graphPattern: CompValue) -> Optional[CompValue]:
304 A: Optional[CompValue] = None
305
306 for g in graphPattern.graph:
307 g = translateGroupGraphPattern(g)
308 if not A:
309 A = g
310 else:
311 A = Union(A, g)
312 return A
313
314
315def translateGraphGraphPattern(graphPattern: CompValue) -> CompValue:
316 return Graph(graphPattern.term, translateGroupGraphPattern(graphPattern.graph))
317
318
319def translateInlineData(graphPattern: CompValue) -> CompValue:
320 return ToMultiSet(translateValues(graphPattern))
321
322
323def translateGroupGraphPattern(graphPattern: CompValue) -> CompValue:
324 """
325 http://www.w3.org/TR/sparql11-query/#convertGraphPattern
326 """
327
328 if graphPattern.translated:
329 # This occurs if it is attempted to translate a group graph pattern twice,
330 # which occurs with nested (NOT) EXISTS filters. Simply return the already
331 # translated pattern instead.
332 return graphPattern
333 if graphPattern.name == "SubSelect":
334 # The first output from translate cannot be None for a subselect query
335 # as it can only be None for certain DESCRIBE queries.
336 # type error: Argument 1 to "ToMultiSet" has incompatible type "Optional[CompValue]";
337 # expected "Union[List[Dict[Variable, str]], CompValue]"
338 return ToMultiSet(translate(graphPattern)[0]) # type: ignore[arg-type]
339
340 if not graphPattern.part:
341 graphPattern.part = [] # empty { }
342
343 filters = collectAndRemoveFilters(graphPattern.part)
344
345 g: List[CompValue] = []
346 for p in graphPattern.part:
347 if p.name == "TriplesBlock":
348 # merge adjacent TripleBlocks
349 if not (g and g[-1].name == "BGP"):
350 g.append(BGP())
351 g[-1]["triples"] += triples(p.triples)
352 else:
353 g.append(p)
354
355 G = BGP()
356 for p in g:
357 if p.name == "OptionalGraphPattern":
358 A = translateGroupGraphPattern(p.graph)
359 if A.name == "Filter":
360 G = LeftJoin(G, A.p, A.expr)
361 else:
362 G = LeftJoin(G, A, TrueFilter)
363 elif p.name == "MinusGraphPattern":
364 G = Minus(p1=G, p2=translateGroupGraphPattern(p.graph))
365 elif p.name == "GroupOrUnionGraphPattern":
366 G = Join(p1=G, p2=translateGroupOrUnionGraphPattern(p))
367 elif p.name == "GraphGraphPattern":
368 G = Join(p1=G, p2=translateGraphGraphPattern(p))
369 elif p.name == "InlineData":
370 G = Join(p1=G, p2=translateInlineData(p))
371 elif p.name == "ServiceGraphPattern":
372 G = Join(p1=G, p2=p)
373 elif p.name in ("BGP", "Extend"):
374 G = Join(p1=G, p2=p)
375 elif p.name == "Bind":
376 # translateExists will translate the expression if it is EXISTS, and otherwise return
377 # the expression as is. This is needed because EXISTS has a graph pattern
378 # which must be translated to work properly during evaluation.
379 G = Extend(G, translateExists(p.expr), p.var)
380
381 else:
382 raise Exception(
383 "Unknown part in GroupGraphPattern: %s - %s" % (type(p), p.name)
384 )
385
386 if filters:
387 G = Filter(expr=filters, p=G)
388
389 # Mark this graph pattern as translated
390 G.translated = True
391
392 return G
393
394
395class StopTraversal(Exception): # noqa: N818
396 def __init__(self, rv: bool):
397 self.rv = rv
398
399
400def _traverse(
401 e: Any,
402 visitPre: Callable[[Any], Any] = lambda n: None,
403 visitPost: Callable[[Any], Any] = lambda n: None,
404):
405 """Traverse a parse-tree, visit each node
406
407 if visit functions return a value, replace current node
408 """
409 _e = visitPre(e)
410 if _e is not None:
411 return _e
412
413 if e is None:
414 return None
415
416 if isinstance(e, (list, ParseResults)):
417 return [_traverse(x, visitPre, visitPost) for x in e]
418 elif isinstance(e, tuple):
419 return tuple([_traverse(x, visitPre, visitPost) for x in e])
420
421 elif isinstance(e, CompValue):
422 for k, val in e.items():
423 e[k] = _traverse(val, visitPre, visitPost)
424
425 _e = visitPost(e)
426 if _e is not None:
427 return _e
428
429 return e
430
431
432def _traverseAgg(e: Any, visitor: Callable[[Any, Any], Any] = lambda n, v: None):
433 """
434 Traverse a parse-tree, visit each node
435
436 if visit functions return a value, replace current node
437 """
438
439 res = []
440
441 if isinstance(e, (list, ParseResults, tuple)):
442 res = [_traverseAgg(x, visitor) for x in e]
443 elif isinstance(e, CompValue):
444 for k, val in e.items():
445 if val is not None:
446 res.append(_traverseAgg(val, visitor))
447
448 return visitor(e, res)
449
450
451def traverse(
452 tree,
453 visitPre: Callable[[Any], Any] = lambda n: None,
454 visitPost: Callable[[Any], Any] = lambda n: None,
455 complete: Optional[bool] = None,
456) -> Any:
457 """
458 Traverse tree, visit each node with visit function
459 visit function may raise StopTraversal to stop traversal
460 if complete!=None, it is returned on complete traversal,
461 otherwise the transformed tree is returned
462 """
463 try:
464 r = _traverse(tree, visitPre, visitPost)
465 if complete is not None:
466 return complete
467 return r
468 except StopTraversal as st:
469 return st.rv
470
471
472def _hasAggregate(x) -> None:
473 """
474 Traverse parse(sub)Tree
475 return true if any aggregates are used
476 """
477
478 if isinstance(x, CompValue):
479 if x.name.startswith("Aggregate_"):
480 raise StopTraversal(True)
481
482
483# type error: Missing return statement
484def _aggs(e, A) -> Optional[Variable]: # type: ignore[return]
485 """
486 Collect Aggregates in A
487 replaces aggregates with variable references
488 """
489
490 # TODO: nested Aggregates?
491
492 if isinstance(e, CompValue) and e.name.startswith("Aggregate_"):
493 A.append(e)
494 aggvar = Variable("__agg_%d__" % len(A))
495 e["res"] = aggvar
496 return aggvar
497
498
499# type error: Missing return statement
500def _findVars(x, res: Set[Variable]) -> Optional[CompValue]: # type: ignore[return]
501 """
502 Find all variables in a tree
503 """
504 if isinstance(x, Variable):
505 res.add(x)
506 if isinstance(x, CompValue):
507 if x.name == "Bind":
508 res.add(x.var)
509 return x # stop recursion and finding vars in the expr
510 elif x.name == "SubSelect":
511 if x.projection:
512 res.update(v.var or v.evar for v in x.projection)
513
514 return x
515
516
517def _addVars(x, children: List[Set[Variable]]) -> Set[Variable]:
518 """
519 find which variables may be bound by this part of the query
520 """
521 if isinstance(x, Variable):
522 return set([x])
523 elif isinstance(x, CompValue):
524 if x.name == "RelationalExpression":
525 x["_vars"] = set()
526 elif x.name == "Extend":
527 # vars only used in the expr for a bind should not be included
528 x["_vars"] = reduce(
529 operator.or_,
530 [child for child, part in zip(children, x) if part != "expr"],
531 set(),
532 )
533
534 else:
535 x["_vars"] = set(reduce(operator.or_, children, set()))
536
537 if x.name == "SubSelect":
538 if x.projection:
539 s = set(v.var or v.evar for v in x.projection)
540 else:
541 s = set()
542
543 return s
544
545 return x["_vars"]
546
547 return reduce(operator.or_, children, set())
548
549
550# type error: Missing return statement
551def _sample(e: typing.Union[CompValue, List[Expr], Expr, List[str], Variable], v: Optional[Variable] = None) -> Optional[CompValue]: # type: ignore[return]
552 """
553 For each unaggregated variable V in expr
554 Replace V with Sample(V)
555 """
556 if isinstance(e, CompValue) and e.name.startswith("Aggregate_"):
557 return e # do not replace vars in aggregates
558 if isinstance(e, Variable) and v != e:
559 return CompValue("Aggregate_Sample", vars=e)
560
561
562def _simplifyFilters(e: Any) -> Any:
563 if isinstance(e, Expr):
564 return simplifyFilters(e)
565
566
567def translateAggregates(
568 q: CompValue, M: CompValue
569) -> Tuple[CompValue, List[Tuple[Variable, Variable]]]:
570 E: List[Tuple[Variable, Variable]] = []
571 A: List[CompValue] = []
572
573 # collect/replace aggs in :
574 # select expr as ?var
575 if q.projection:
576 for v in q.projection:
577 if v.evar:
578 v.expr = traverse(v.expr, functools.partial(_sample, v=v.evar))
579 v.expr = traverse(v.expr, functools.partial(_aggs, A=A))
580
581 # having clause
582 if traverse(q.having, _hasAggregate, complete=True):
583 q.having = traverse(q.having, _sample)
584 traverse(q.having, functools.partial(_aggs, A=A))
585
586 # order by
587 if traverse(q.orderby, _hasAggregate, complete=False):
588 q.orderby = traverse(q.orderby, _sample)
589 traverse(q.orderby, functools.partial(_aggs, A=A))
590
591 # sample all other select vars
592 # TODO: only allowed for vars in group-by?
593 if q.projection:
594 for v in q.projection:
595 if v.var:
596 rv = Variable("__agg_%d__" % (len(A) + 1))
597 A.append(CompValue("Aggregate_Sample", vars=v.var, res=rv))
598 E.append((rv, v.var))
599
600 return CompValue("AggregateJoin", A=A, p=M), E
601
602
603def translateValues(
604 v: CompValue,
605) -> typing.Union[List[Dict[Variable, str]], CompValue]:
606 # if len(v.var)!=len(v.value):
607 # raise Exception("Unmatched vars and values in ValueClause: "+str(v))
608
609 res: List[Dict[Variable, str]] = []
610 if not v.var:
611 return res
612 if not v.value:
613 return res
614 if not isinstance(v.value[0], list):
615 for val in v.value:
616 res.append({v.var[0]: val})
617 else:
618 for vals in v.value:
619 res.append(dict(zip(v.var, vals)))
620
621 return Values(res)
622
623
624def translate(q: CompValue) -> Tuple[Optional[CompValue], List[Variable]]:
625 """
626 http://www.w3.org/TR/sparql11-query/#convertSolMod
627 """
628
629 _traverse(q, _simplifyFilters)
630
631 q.where = traverse(q.where, visitPost=translatePath)
632
633 # TODO: Var scope test
634 VS: Set[Variable] = set()
635
636 # All query types have a WHERE clause EXCEPT some DESCRIBE queries
637 # where only explicit IRIs are provided.
638 if q.name == "DescribeQuery":
639 # For DESCRIBE queries, use the vars provided in q.var.
640 # If there is no WHERE clause, vars should be explicit IRIs to describe.
641 # If there is a WHERE clause, vars can be any combination of explicit IRIs
642 # and variables.
643 VS = set(q.var)
644
645 # If there is no WHERE clause, just return the vars projected
646 if q.where is None:
647 return None, list(VS)
648
649 # Otherwise, evaluate the WHERE clause like SELECT DISTINCT
650 else:
651 q.modifier = "DISTINCT"
652
653 else:
654 traverse(q.where, functools.partial(_findVars, res=VS))
655
656 # depth-first recursive generation of mapped query tree
657 M = translateGroupGraphPattern(q.where)
658
659 aggregate = False
660 if q.groupby:
661 conditions = []
662 # convert "GROUP BY (?expr as ?var)" to an Extend
663 for c in q.groupby.condition:
664 if isinstance(c, CompValue) and c.name == "GroupAs":
665 M = Extend(M, c.expr, c.var)
666 c = c.var
667 conditions.append(c)
668
669 M = Group(p=M, expr=conditions)
670 aggregate = True
671 elif (
672 traverse(q.having, _hasAggregate, complete=False)
673 or traverse(q.orderby, _hasAggregate, complete=False)
674 or any(
675 traverse(x.expr, _hasAggregate, complete=False)
676 for x in q.projection or []
677 if x.evar
678 )
679 ):
680 # if any aggregate is used, implicit group by
681 M = Group(p=M)
682 aggregate = True
683
684 if aggregate:
685 M, aggregateAliases = translateAggregates(q, M)
686 else:
687 aggregateAliases = []
688
689 # Need to remove the aggregate var aliases before joining to VALUES;
690 # else the variable names won't match up correctly when aggregating.
691 for alias, var in aggregateAliases:
692 M = Extend(M, alias, var)
693
694 # HAVING
695 if q.having:
696 M = Filter(expr=and_(*q.having.condition), p=M)
697
698 # VALUES
699 if q.valuesClause:
700 M = Join(p1=M, p2=ToMultiSet(translateValues(q.valuesClause)))
701
702 if not q.projection:
703 # select *
704
705 # Find the first child projection in each branch of the mapped query tree,
706 # then include the variables it projects out in our projected variables.
707 for child_projection in _find_first_child_projections(M):
708 VS |= set(child_projection.PV)
709
710 PV = list(VS)
711 else:
712 E = list()
713 PV = list()
714 for v in q.projection:
715 if v.var:
716 if v not in PV:
717 PV.append(v.var)
718 elif v.evar:
719 if v not in PV:
720 PV.append(v.evar)
721
722 E.append((v.expr, v.evar))
723 else:
724 raise Exception("I expected a var or evar here!")
725
726 for e, v in E:
727 M = Extend(M, e, v)
728
729 # ORDER BY
730 if q.orderby:
731 M = OrderBy(
732 M,
733 [
734 CompValue("OrderCondition", expr=c.expr, order=c.order)
735 for c in q.orderby.condition
736 ],
737 )
738
739 # PROJECT
740 M = Project(M, PV)
741
742 if q.modifier:
743 if q.modifier == "DISTINCT":
744 M = CompValue("Distinct", p=M)
745 elif q.modifier == "REDUCED":
746 M = CompValue("Reduced", p=M)
747
748 if q.limitoffset:
749 offset = 0
750 if q.limitoffset.offset is not None:
751 offset = q.limitoffset.offset.toPython()
752
753 if q.limitoffset.limit is not None:
754 M = CompValue(
755 "Slice", p=M, start=offset, length=q.limitoffset.limit.toPython()
756 )
757 else:
758 M = CompValue("Slice", p=M, start=offset)
759
760 return M, PV
761
762
763def _find_first_child_projections(M: CompValue) -> Iterable[CompValue]:
764 """
765 Recursively find the first child instance of a Projection operation in each of
766 the branches of the query execution plan/tree.
767 """
768
769 for child_op in M.values():
770 if isinstance(child_op, CompValue):
771 if child_op.name == "Project":
772 yield child_op
773 else:
774 for child_projection in _find_first_child_projections(child_op):
775 yield child_projection
776
777
778# type error: Missing return statement
779def simplify(n: Any) -> Optional[CompValue]: # type: ignore[return]
780 """Remove joins to empty BGPs"""
781 if isinstance(n, CompValue):
782 if n.name == "Join":
783 if n.p1.name == "BGP" and len(n.p1.triples) == 0:
784 return n.p2
785 if n.p2.name == "BGP" and len(n.p2.triples) == 0:
786 return n.p1
787 elif n.name == "BGP":
788 n["triples"] = reorderTriples(n.triples)
789 return n
790
791
792def analyse(n: Any, children: Any) -> bool:
793 """
794 Some things can be lazily joined.
795 This propegates whether they can up the tree
796 and sets lazy flags for all joins
797 """
798
799 if isinstance(n, CompValue):
800 if n.name == "Join":
801 n["lazy"] = all(children)
802 return False
803 elif n.name in ("Slice", "Distinct"):
804 return False
805 else:
806 return all(children)
807 else:
808 return True
809
810
811def translatePrologue(
812 p: ParseResults,
813 base: Optional[str],
814 initNs: Optional[Mapping[str, Any]] = None,
815 prologue: Optional[Prologue] = None,
816) -> Prologue:
817 if prologue is None:
818 prologue = Prologue()
819 prologue.base = ""
820 if base:
821 prologue.base = base
822 if initNs:
823 for k, v in initNs.items():
824 prologue.bind(k, v)
825
826 x: CompValue
827 for x in p:
828 if x.name == "Base":
829 prologue.base = x.iri
830 elif x.name == "PrefixDecl":
831 prologue.bind(x.prefix, prologue.absolutize(x.iri))
832
833 return prologue
834
835
836def translateQuads(
837 quads: CompValue,
838) -> Tuple[
839 List[Tuple[Identifier, Identifier, Identifier]],
840 DefaultDict[str, List[Tuple[Identifier, Identifier, Identifier]]],
841]:
842 if quads.triples:
843 alltriples = triples(quads.triples)
844 else:
845 alltriples = []
846
847 allquads: DefaultDict[str, List[Tuple[Identifier, Identifier, Identifier]]] = (
848 collections.defaultdict(list)
849 )
850
851 if quads.quadsNotTriples:
852 for q in quads.quadsNotTriples:
853 if q.triples:
854 allquads[q.term] += triples(q.triples)
855
856 return alltriples, allquads
857
858
859def translateUpdate1(u: CompValue, prologue: Prologue) -> CompValue:
860 if u.name in ("Load", "Clear", "Drop", "Create"):
861 pass # no translation needed
862 elif u.name in ("Add", "Move", "Copy"):
863 pass
864 elif u.name in ("InsertData", "DeleteData", "DeleteWhere"):
865 t, q = translateQuads(u.quads)
866 u["quads"] = q
867 u["triples"] = t
868 if u.name in ("DeleteWhere", "DeleteData"):
869 pass # TODO: check for bnodes in triples
870 elif u.name == "Modify":
871 if u.delete:
872 u.delete["triples"], u.delete["quads"] = translateQuads(u.delete.quads)
873 if u.insert:
874 u.insert["triples"], u.insert["quads"] = translateQuads(u.insert.quads)
875 u["where"] = translateGroupGraphPattern(u.where)
876 else:
877 raise Exception("Unknown type of update operation: %s" % u)
878
879 u.prologue = prologue
880 return u
881
882
883def translateUpdate(
884 q: CompValue,
885 base: Optional[str] = None,
886 initNs: Optional[Mapping[str, Any]] = None,
887) -> Update:
888 """
889 Returns a list of SPARQL Update Algebra expressions
890 """
891
892 res: List[CompValue] = []
893 prologue = None
894 if not q.request:
895 # type error: Incompatible return value type (got "List[CompValue]", expected "Update")
896 return res # type: ignore[return-value]
897 for p, u in zip(q.prologue, q.request):
898 prologue = translatePrologue(p, base, initNs, prologue)
899
900 # absolutize/resolve prefixes
901 u = traverse(u, visitPost=functools.partial(translatePName, prologue=prologue))
902 u = _traverse(u, _simplifyFilters)
903
904 u = traverse(u, visitPost=translatePath)
905
906 res.append(translateUpdate1(u, prologue))
907
908 # type error: Argument 1 to "Update" has incompatible type "Optional[Any]"; expected "Prologue"
909 return Update(prologue, res) # type: ignore[arg-type]
910
911
912def translateQuery(
913 q: ParseResults,
914 base: Optional[str] = None,
915 initNs: Optional[Mapping[str, Any]] = None,
916) -> Query:
917 """
918 Translate a query-parsetree to a SPARQL Algebra Expression
919
920 Return a rdflib.plugins.sparql.sparql.Query object
921 """
922
923 # We get in: (prologue, query)
924
925 prologue = translatePrologue(q[0], base, initNs)
926
927 # absolutize/resolve prefixes
928 q[1] = traverse(
929 q[1], visitPost=functools.partial(translatePName, prologue=prologue)
930 )
931
932 P, PV = translate(q[1])
933 datasetClause = q[1].datasetClause
934 if q[1].name == "ConstructQuery":
935 template = triples(q[1].template) if q[1].template else None
936
937 res = CompValue(q[1].name, p=P, template=template, datasetClause=datasetClause)
938 else:
939 res = CompValue(q[1].name, p=P, datasetClause=datasetClause, PV=PV)
940
941 res = traverse(res, visitPost=simplify)
942 _traverseAgg(res, visitor=analyse)
943 _traverseAgg(res, _addVars)
944
945 return Query(prologue, res)
946
947
948class ExpressionNotCoveredException(Exception): # noqa: N818
949 pass
950
951
952class _AlgebraTranslator:
953 """Translator of a Query's algebra to its equivalent SPARQL (string).
954
955 Coded as a class to support storage of state during the translation process,
956 without use of a file.
957
958 Anticipated Usage:
959
960 ```python
961 translated_query = _AlgebraTranslator(query).translateAlgebra()
962 ```
963
964 An external convenience function which wraps the above call,
965 `translateAlgebra`, is supplied, so this class does not need to be
966 referenced by client code at all in normal use.
967 """
968
969 def __init__(self, query_algebra: Query):
970 self.query_algebra = query_algebra
971 self.aggr_vars: DefaultDict[Identifier, List[Identifier]] = (
972 collections.defaultdict(list)
973 )
974 self._alg_translation: str = ""
975
976 def _replace(
977 self,
978 old: str,
979 new: str,
980 search_from_match: str = None,
981 search_from_match_occurrence: int = None,
982 count: int = 1,
983 ):
984 def find_nth(haystack, needle, n):
985 start = haystack.lower().find(needle)
986 while start >= 0 and n > 1:
987 start = haystack.lower().find(needle, start + len(needle))
988 n -= 1
989 return start
990
991 if search_from_match and search_from_match_occurrence:
992 position = find_nth(
993 self._alg_translation, search_from_match, search_from_match_occurrence
994 )
995 filedata_pre = self._alg_translation[:position]
996 filedata_post = self._alg_translation[position:].replace(old, new, count)
997 self._alg_translation = filedata_pre + filedata_post
998 else:
999 self._alg_translation = self._alg_translation.replace(old, new, count)
1000
1001 def convert_node_arg(
1002 self, node_arg: typing.Union[Identifier, CompValue, Expr, str]
1003 ) -> str:
1004 if isinstance(node_arg, Identifier):
1005 if node_arg in self.aggr_vars.keys():
1006 grp_var = self.aggr_vars[node_arg].pop(0).n3()
1007 return grp_var
1008 else:
1009 return node_arg.n3()
1010 elif isinstance(node_arg, CompValue):
1011 return "{" + node_arg.name + "}"
1012 elif isinstance(node_arg, str):
1013 return node_arg
1014 else:
1015 raise ExpressionNotCoveredException(
1016 "The expression {0} might not be covered yet.".format(node_arg)
1017 )
1018
1019 def sparql_query_text(self, node):
1020 """<https://www.w3.org/TR/sparql11-query/#sparqlSyntax>"""
1021
1022 if isinstance(node, CompValue):
1023 # 18.2 Query Forms
1024 if node.name == "SelectQuery":
1025 self._alg_translation = "-*-SELECT-*- " + "{" + node.p.name + "}"
1026
1027 # 18.2 Graph Patterns
1028 elif node.name == "BGP":
1029 # Identifiers or Paths
1030 # Negated path throws a type error. Probably n3() method of negated paths should be fixed
1031 triples = "".join(
1032 triple[0].n3() + " " + triple[1].n3() + " " + triple[2].n3() + "."
1033 for triple in node.triples
1034 )
1035 self._replace("{BGP}", triples)
1036 # The dummy -*-SELECT-*- is placed during a SelectQuery or Multiset pattern in order to be able
1037 # to match extended variables in a specific Select-clause (see "Extend" below)
1038 self._replace("-*-SELECT-*-", "SELECT", count=-1)
1039 # If there is no "Group By" clause the placeholder will simply be deleted. Otherwise there will be
1040 # no matching {GroupBy} placeholder because it has already been replaced by "group by variables"
1041 self._replace("{GroupBy}", "", count=-1)
1042 self._replace("{Having}", "", count=-1)
1043 elif node.name == "Join":
1044 self._replace(
1045 "{Join}", "{" + node.p1.name + "}{" + node.p2.name + "}"
1046 ) #
1047 elif node.name == "LeftJoin":
1048 self._replace(
1049 "{LeftJoin}",
1050 "{" + node.p1.name + "}OPTIONAL{{" + node.p2.name + "}}",
1051 )
1052 elif node.name == "Filter":
1053 if isinstance(node.expr, CompValue):
1054 expr = node.expr.name
1055 else:
1056 raise ExpressionNotCoveredException(
1057 "This expression might not be covered yet."
1058 )
1059 if node.p:
1060 # Filter with p=AggregateJoin = Having
1061 if node.p.name == "AggregateJoin":
1062 self._replace("{Filter}", "{" + node.p.name + "}")
1063 self._replace("{Having}", "HAVING({" + expr + "})")
1064 else:
1065 self._replace(
1066 "{Filter}", "FILTER({" + expr + "}) {" + node.p.name + "}"
1067 )
1068 else:
1069 self._replace("{Filter}", "FILTER({" + expr + "})")
1070
1071 elif node.name == "Union":
1072 self._replace(
1073 "{Union}", "{{" + node.p1.name + "}}UNION{{" + node.p2.name + "}}"
1074 )
1075 elif node.name == "Graph":
1076 expr = "GRAPH " + node.term.n3() + " {{" + node.p.name + "}}"
1077 self._replace("{Graph}", expr)
1078 elif node.name == "Extend":
1079 query_string = self._alg_translation.lower()
1080 select_occurrences = query_string.count("-*-select-*-")
1081 self._replace(
1082 node.var.n3(),
1083 "("
1084 + self.convert_node_arg(node.expr)
1085 + " as "
1086 + node.var.n3()
1087 + ")",
1088 search_from_match="-*-select-*-",
1089 search_from_match_occurrence=select_occurrences,
1090 )
1091 self._replace("{Extend}", "{" + node.p.name + "}")
1092 elif node.name == "Minus":
1093 expr = "{" + node.p1.name + "}MINUS{{" + node.p2.name + "}}"
1094 self._replace("{Minus}", expr)
1095 elif node.name == "Group":
1096 group_by_vars = []
1097 if node.expr:
1098 for var in node.expr:
1099 if isinstance(var, Identifier):
1100 group_by_vars.append(var.n3())
1101 else:
1102 raise ExpressionNotCoveredException(
1103 "This expression might not be covered yet."
1104 )
1105 self._replace("{Group}", "{" + node.p.name + "}")
1106 self._replace(
1107 "{GroupBy}", "GROUP BY " + " ".join(group_by_vars) + " "
1108 )
1109 else:
1110 self._replace("{Group}", "{" + node.p.name + "}")
1111 elif node.name == "AggregateJoin":
1112 self._replace("{AggregateJoin}", "{" + node.p.name + "}")
1113 for agg_func in node.A:
1114 if isinstance(agg_func.res, Identifier):
1115 identifier = agg_func.res.n3()
1116 else:
1117 raise ExpressionNotCoveredException(
1118 "This expression might not be covered yet."
1119 )
1120 self.aggr_vars[agg_func.res].append(agg_func.vars)
1121
1122 agg_func_name = agg_func.name.split("_")[1]
1123 distinct = ""
1124 if agg_func.distinct:
1125 distinct = agg_func.distinct + " "
1126 if agg_func_name == "GroupConcat":
1127 self._replace(
1128 identifier,
1129 "GROUP_CONCAT"
1130 + "("
1131 + distinct
1132 + agg_func.vars.n3()
1133 + ";SEPARATOR="
1134 + agg_func.separator.n3()
1135 + ")",
1136 )
1137 else:
1138 self._replace(
1139 identifier,
1140 agg_func_name.upper()
1141 + "("
1142 + distinct
1143 + self.convert_node_arg(agg_func.vars)
1144 + ")",
1145 )
1146 # For non-aggregated variables the aggregation function "sample" is automatically assigned.
1147 # However, we do not want to have "sample" wrapped around non-aggregated variables. That is
1148 # why we replace it. If "sample" is used on purpose it will not be replaced as the alias
1149 # must be different from the variable in this case.
1150 self._replace(
1151 "(SAMPLE({0}) as {0})".format(
1152 self.convert_node_arg(agg_func.vars)
1153 ),
1154 self.convert_node_arg(agg_func.vars),
1155 )
1156 elif node.name == "GroupGraphPatternSub":
1157 self._replace(
1158 "GroupGraphPatternSub",
1159 " ".join([self.convert_node_arg(pattern) for pattern in node.part]),
1160 )
1161 elif node.name == "TriplesBlock":
1162 self._replace(
1163 "{TriplesBlock}",
1164 "".join(
1165 triple[0].n3()
1166 + " "
1167 + triple[1].n3()
1168 + " "
1169 + triple[2].n3()
1170 + "."
1171 for triple in node.triples
1172 ),
1173 )
1174
1175 # 18.2 Solution modifiers
1176 elif node.name == "ToList":
1177 raise ExpressionNotCoveredException(
1178 "This expression might not be covered yet."
1179 )
1180 elif node.name == "OrderBy":
1181 order_conditions = []
1182 for c in node.expr:
1183 if isinstance(c.expr, Identifier):
1184 var = c.expr.n3()
1185 if c.order is not None:
1186 cond = c.order + "(" + var + ")"
1187 else:
1188 cond = var
1189 order_conditions.append(cond)
1190 else:
1191 raise ExpressionNotCoveredException(
1192 "This expression might not be covered yet."
1193 )
1194 self._replace("{OrderBy}", "{" + node.p.name + "}")
1195 self._replace("{OrderConditions}", " ".join(order_conditions) + " ")
1196 elif node.name == "Project":
1197 project_variables = []
1198 for var in node.PV:
1199 if isinstance(var, Identifier):
1200 project_variables.append(var.n3())
1201 else:
1202 raise ExpressionNotCoveredException(
1203 "This expression might not be covered yet."
1204 )
1205 order_by_pattern = ""
1206 if node.p.name == "OrderBy":
1207 order_by_pattern = "ORDER BY {OrderConditions}"
1208 self._replace(
1209 "{Project}",
1210 " ".join(project_variables)
1211 + "{{"
1212 + node.p.name
1213 + "}}"
1214 + "{GroupBy}"
1215 + order_by_pattern
1216 + "{Having}",
1217 )
1218 elif node.name == "Distinct":
1219 self._replace("{Distinct}", "DISTINCT {" + node.p.name + "}")
1220 elif node.name == "Reduced":
1221 self._replace("{Reduced}", "REDUCED {" + node.p.name + "}")
1222 elif node.name == "Slice":
1223 slice = "OFFSET " + str(node.start) + " LIMIT " + str(node.length)
1224 self._replace("{Slice}", "{" + node.p.name + "}" + slice)
1225 elif node.name == "ToMultiSet":
1226 if node.p.name == "values":
1227 self._replace("{ToMultiSet}", "{{" + node.p.name + "}}")
1228 else:
1229 self._replace(
1230 "{ToMultiSet}", "{-*-SELECT-*- " + "{" + node.p.name + "}" + "}"
1231 )
1232
1233 # 18.2 Property Path
1234
1235 # 17 Expressions and Testing Values
1236 # # 17.3 Operator Mapping
1237 elif node.name == "RelationalExpression":
1238 expr = self.convert_node_arg(node.expr)
1239 op = node.op
1240 if isinstance(list, type(node.other)):
1241 other = (
1242 "("
1243 + ", ".join(self.convert_node_arg(expr) for expr in node.other)
1244 + ")"
1245 )
1246 else:
1247 other = self.convert_node_arg(node.other)
1248 condition = "{left} {operator} {right}".format(
1249 left=expr, operator=op, right=other
1250 )
1251 self._replace("{RelationalExpression}", condition)
1252 elif node.name == "ConditionalAndExpression":
1253 inner_nodes = " && ".join(
1254 [self.convert_node_arg(expr) for expr in node.other]
1255 )
1256 self._replace(
1257 "{ConditionalAndExpression}",
1258 self.convert_node_arg(node.expr) + " && " + inner_nodes,
1259 )
1260 elif node.name == "ConditionalOrExpression":
1261 inner_nodes = " || ".join(
1262 [self.convert_node_arg(expr) for expr in node.other]
1263 )
1264 self._replace(
1265 "{ConditionalOrExpression}",
1266 "(" + self.convert_node_arg(node.expr) + " || " + inner_nodes + ")",
1267 )
1268 elif node.name == "MultiplicativeExpression":
1269 left_side = self.convert_node_arg(node.expr)
1270 multiplication = left_side
1271 for i, operator in enumerate(node.op):
1272 multiplication += (
1273 operator + " " + self.convert_node_arg(node.other[i]) + " "
1274 )
1275 self._replace("{MultiplicativeExpression}", multiplication)
1276 elif node.name == "AdditiveExpression":
1277 left_side = self.convert_node_arg(node.expr)
1278 addition = left_side
1279 for i, operator in enumerate(node.op):
1280 addition += (
1281 operator + " " + self.convert_node_arg(node.other[i]) + " "
1282 )
1283 self._replace("{AdditiveExpression}", addition)
1284 elif node.name == "UnaryNot":
1285 self._replace("{UnaryNot}", "!" + self.convert_node_arg(node.expr))
1286
1287 # # 17.4 Function Definitions
1288 # # # 17.4.1 Functional Forms
1289 elif node.name.endswith("BOUND"):
1290 bound_var = self.convert_node_arg(node.arg)
1291 self._replace("{Builtin_BOUND}", "bound(" + bound_var + ")")
1292 elif node.name.endswith("IF"):
1293 arg2 = self.convert_node_arg(node.arg2)
1294 arg3 = self.convert_node_arg(node.arg3)
1295
1296 if_expression = (
1297 "IF(" + "{" + node.arg1.name + "}, " + arg2 + ", " + arg3 + ")"
1298 )
1299 self._replace("{Builtin_IF}", if_expression)
1300 elif node.name.endswith("COALESCE"):
1301 self._replace(
1302 "{Builtin_COALESCE}",
1303 "COALESCE("
1304 + ", ".join(self.convert_node_arg(arg) for arg in node.arg)
1305 + ")",
1306 )
1307 elif node.name.endswith("Builtin_EXISTS"):
1308 # The node's name which we get with node.graph.name returns "Join" instead of GroupGraphPatternSub
1309 # According to https://www.w3.org/TR/2013/REC-sparql11-query-20130321/#rExistsFunc
1310 # ExistsFunc can only have a GroupGraphPattern as parameter. However, when we print the query algebra
1311 # we get a GroupGraphPatternSub
1312 self._replace(
1313 "{Builtin_EXISTS}", "EXISTS " + "{{" + node.graph.name + "}}"
1314 )
1315 traverse(node.graph, visitPre=self.sparql_query_text)
1316 return node.graph
1317 elif node.name.endswith("Builtin_NOTEXISTS"):
1318 # The node's name which we get with node.graph.name returns "Join" instead of GroupGraphPatternSub
1319 # According to https://www.w3.org/TR/2013/REC-sparql11-query-20130321/#rNotExistsFunc
1320 # NotExistsFunc can only have a GroupGraphPattern as parameter. However, when we print the query algebra
1321 # we get a GroupGraphPatternSub
1322 self._replace(
1323 "{Builtin_NOTEXISTS}", "NOT EXISTS " + "{{" + node.graph.name + "}}"
1324 )
1325 traverse(node.graph, visitPre=self.sparql_query_text)
1326 return node.graph
1327 # # # # 17.4.1.5 logical-or: Covered in "RelationalExpression"
1328 # # # # 17.4.1.6 logical-and: Covered in "RelationalExpression"
1329 # # # # 17.4.1.7 RDFterm-equal: Covered in "RelationalExpression"
1330 elif node.name.endswith("sameTerm"):
1331 self._replace(
1332 "{Builtin_sameTerm}",
1333 "SAMETERM("
1334 + self.convert_node_arg(node.arg1)
1335 + ", "
1336 + self.convert_node_arg(node.arg2)
1337 + ")",
1338 )
1339 # # # # IN: Covered in "RelationalExpression"
1340 # # # # NOT IN: Covered in "RelationalExpression"
1341
1342 # # # 17.4.2 Functions on RDF Terms
1343 elif node.name.endswith("Builtin_isIRI"):
1344 self._replace(
1345 "{Builtin_isIRI}", "isIRI(" + self.convert_node_arg(node.arg) + ")"
1346 )
1347 elif node.name.endswith("Builtin_isBLANK"):
1348 self._replace(
1349 "{Builtin_isBLANK}",
1350 "isBLANK(" + self.convert_node_arg(node.arg) + ")",
1351 )
1352 elif node.name.endswith("Builtin_isLITERAL"):
1353 self._replace(
1354 "{Builtin_isLITERAL}",
1355 "isLITERAL(" + self.convert_node_arg(node.arg) + ")",
1356 )
1357 elif node.name.endswith("Builtin_isNUMERIC"):
1358 self._replace(
1359 "{Builtin_isNUMERIC}",
1360 "isNUMERIC(" + self.convert_node_arg(node.arg) + ")",
1361 )
1362 elif node.name.endswith("Builtin_STR"):
1363 self._replace(
1364 "{Builtin_STR}", "STR(" + self.convert_node_arg(node.arg) + ")"
1365 )
1366 elif node.name.endswith("Builtin_LANG"):
1367 self._replace(
1368 "{Builtin_LANG}", "LANG(" + self.convert_node_arg(node.arg) + ")"
1369 )
1370 elif node.name.endswith("Builtin_DATATYPE"):
1371 self._replace(
1372 "{Builtin_DATATYPE}",
1373 "DATATYPE(" + self.convert_node_arg(node.arg) + ")",
1374 )
1375 elif node.name.endswith("Builtin_IRI"):
1376 self._replace(
1377 "{Builtin_IRI}", "IRI(" + self.convert_node_arg(node.arg) + ")"
1378 )
1379 elif node.name.endswith("Builtin_BNODE"):
1380 self._replace(
1381 "{Builtin_BNODE}", "BNODE(" + self.convert_node_arg(node.arg) + ")"
1382 )
1383 elif node.name.endswith("STRDT"):
1384 self._replace(
1385 "{Builtin_STRDT}",
1386 "STRDT("
1387 + self.convert_node_arg(node.arg1)
1388 + ", "
1389 + self.convert_node_arg(node.arg2)
1390 + ")",
1391 )
1392 elif node.name.endswith("Builtin_STRLANG"):
1393 self._replace(
1394 "{Builtin_STRLANG}",
1395 "STRLANG("
1396 + self.convert_node_arg(node.arg1)
1397 + ", "
1398 + self.convert_node_arg(node.arg2)
1399 + ")",
1400 )
1401 elif node.name.endswith("Builtin_UUID"):
1402 self._replace("{Builtin_UUID}", "UUID()")
1403 elif node.name.endswith("Builtin_STRUUID"):
1404 self._replace("{Builtin_STRUUID}", "STRUUID()")
1405
1406 # # # 17.4.3 Functions on Strings
1407 elif node.name.endswith("Builtin_STRLEN"):
1408 self._replace(
1409 "{Builtin_STRLEN}",
1410 "STRLEN(" + self.convert_node_arg(node.arg) + ")",
1411 )
1412 elif node.name.endswith("Builtin_SUBSTR"):
1413 args = [self.convert_node_arg(node.arg), node.start]
1414 if node.length:
1415 args.append(node.length)
1416 expr = "SUBSTR(" + ", ".join(args) + ")"
1417 self._replace("{Builtin_SUBSTR}", expr)
1418 elif node.name.endswith("Builtin_UCASE"):
1419 self._replace(
1420 "{Builtin_UCASE}", "UCASE(" + self.convert_node_arg(node.arg) + ")"
1421 )
1422 elif node.name.endswith("Builtin_LCASE"):
1423 self._replace(
1424 "{Builtin_LCASE}", "LCASE(" + self.convert_node_arg(node.arg) + ")"
1425 )
1426 elif node.name.endswith("Builtin_STRSTARTS"):
1427 self._replace(
1428 "{Builtin_STRSTARTS}",
1429 "STRSTARTS("
1430 + self.convert_node_arg(node.arg1)
1431 + ", "
1432 + self.convert_node_arg(node.arg2)
1433 + ")",
1434 )
1435 elif node.name.endswith("Builtin_STRENDS"):
1436 self._replace(
1437 "{Builtin_STRENDS}",
1438 "STRENDS("
1439 + self.convert_node_arg(node.arg1)
1440 + ", "
1441 + self.convert_node_arg(node.arg2)
1442 + ")",
1443 )
1444 elif node.name.endswith("Builtin_CONTAINS"):
1445 self._replace(
1446 "{Builtin_CONTAINS}",
1447 "CONTAINS("
1448 + self.convert_node_arg(node.arg1)
1449 + ", "
1450 + self.convert_node_arg(node.arg2)
1451 + ")",
1452 )
1453 elif node.name.endswith("Builtin_STRBEFORE"):
1454 self._replace(
1455 "{Builtin_STRBEFORE}",
1456 "STRBEFORE("
1457 + self.convert_node_arg(node.arg1)
1458 + ", "
1459 + self.convert_node_arg(node.arg2)
1460 + ")",
1461 )
1462 elif node.name.endswith("Builtin_STRAFTER"):
1463 self._replace(
1464 "{Builtin_STRAFTER}",
1465 "STRAFTER("
1466 + self.convert_node_arg(node.arg1)
1467 + ", "
1468 + self.convert_node_arg(node.arg2)
1469 + ")",
1470 )
1471 elif node.name.endswith("Builtin_ENCODE_FOR_URI"):
1472 self._replace(
1473 "{Builtin_ENCODE_FOR_URI}",
1474 "ENCODE_FOR_URI(" + self.convert_node_arg(node.arg) + ")",
1475 )
1476 elif node.name.endswith("Builtin_CONCAT"):
1477 expr = "CONCAT({vars})".format(
1478 vars=", ".join(self.convert_node_arg(elem) for elem in node.arg)
1479 )
1480 self._replace("{Builtin_CONCAT}", expr)
1481 elif node.name.endswith("Builtin_LANGMATCHES"):
1482 self._replace(
1483 "{Builtin_LANGMATCHES}",
1484 "LANGMATCHES("
1485 + self.convert_node_arg(node.arg1)
1486 + ", "
1487 + self.convert_node_arg(node.arg2)
1488 + ")",
1489 )
1490 elif node.name.endswith("REGEX"):
1491 args = [
1492 self.convert_node_arg(node.text),
1493 self.convert_node_arg(node.pattern),
1494 ]
1495 expr = "REGEX(" + ", ".join(args) + ")"
1496 self._replace("{Builtin_REGEX}", expr)
1497 elif node.name.endswith("REPLACE"):
1498 self._replace(
1499 "{Builtin_REPLACE}",
1500 "REPLACE("
1501 + self.convert_node_arg(node.arg)
1502 + ", "
1503 + self.convert_node_arg(node.pattern)
1504 + ", "
1505 + self.convert_node_arg(node.replacement)
1506 + ")",
1507 )
1508
1509 # # # 17.4.4 Functions on Numerics
1510 elif node.name == "Builtin_ABS":
1511 self._replace(
1512 "{Builtin_ABS}", "ABS(" + self.convert_node_arg(node.arg) + ")"
1513 )
1514 elif node.name == "Builtin_ROUND":
1515 self._replace(
1516 "{Builtin_ROUND}", "ROUND(" + self.convert_node_arg(node.arg) + ")"
1517 )
1518 elif node.name == "Builtin_CEIL":
1519 self._replace(
1520 "{Builtin_CEIL}", "CEIL(" + self.convert_node_arg(node.arg) + ")"
1521 )
1522 elif node.name == "Builtin_FLOOR":
1523 self._replace(
1524 "{Builtin_FLOOR}", "FLOOR(" + self.convert_node_arg(node.arg) + ")"
1525 )
1526 elif node.name == "Builtin_RAND":
1527 self._replace("{Builtin_RAND}", "RAND()")
1528
1529 # # # 17.4.5 Functions on Dates and Times
1530 elif node.name == "Builtin_NOW":
1531 self._replace("{Builtin_NOW}", "NOW()")
1532 elif node.name == "Builtin_YEAR":
1533 self._replace(
1534 "{Builtin_YEAR}", "YEAR(" + self.convert_node_arg(node.arg) + ")"
1535 )
1536 elif node.name == "Builtin_MONTH":
1537 self._replace(
1538 "{Builtin_MONTH}", "MONTH(" + self.convert_node_arg(node.arg) + ")"
1539 )
1540 elif node.name == "Builtin_DAY":
1541 self._replace(
1542 "{Builtin_DAY}", "DAY(" + self.convert_node_arg(node.arg) + ")"
1543 )
1544 elif node.name == "Builtin_HOURS":
1545 self._replace(
1546 "{Builtin_HOURS}", "HOURS(" + self.convert_node_arg(node.arg) + ")"
1547 )
1548 elif node.name == "Builtin_MINUTES":
1549 self._replace(
1550 "{Builtin_MINUTES}",
1551 "MINUTES(" + self.convert_node_arg(node.arg) + ")",
1552 )
1553 elif node.name == "Builtin_SECONDS":
1554 self._replace(
1555 "{Builtin_SECONDS}",
1556 "SECONDS(" + self.convert_node_arg(node.arg) + ")",
1557 )
1558 elif node.name == "Builtin_TIMEZONE":
1559 self._replace(
1560 "{Builtin_TIMEZONE}",
1561 "TIMEZONE(" + self.convert_node_arg(node.arg) + ")",
1562 )
1563 elif node.name == "Builtin_TZ":
1564 self._replace(
1565 "{Builtin_TZ}", "TZ(" + self.convert_node_arg(node.arg) + ")"
1566 )
1567
1568 # # # 17.4.6 Hash functions
1569 elif node.name == "Builtin_MD5":
1570 self._replace(
1571 "{Builtin_MD5}", "MD5(" + self.convert_node_arg(node.arg) + ")"
1572 )
1573 elif node.name == "Builtin_SHA1":
1574 self._replace(
1575 "{Builtin_SHA1}", "SHA1(" + self.convert_node_arg(node.arg) + ")"
1576 )
1577 elif node.name == "Builtin_SHA256":
1578 self._replace(
1579 "{Builtin_SHA256}",
1580 "SHA256(" + self.convert_node_arg(node.arg) + ")",
1581 )
1582 elif node.name == "Builtin_SHA384":
1583 self._replace(
1584 "{Builtin_SHA384}",
1585 "SHA384(" + self.convert_node_arg(node.arg) + ")",
1586 )
1587 elif node.name == "Builtin_SHA512":
1588 self._replace(
1589 "{Builtin_SHA512}",
1590 "SHA512(" + self.convert_node_arg(node.arg) + ")",
1591 )
1592
1593 # Other
1594 elif node.name == "values":
1595 columns = []
1596 for key in node.res[0].keys():
1597 if isinstance(key, Identifier):
1598 columns.append(key.n3())
1599 else:
1600 raise ExpressionNotCoveredException(
1601 "The expression {0} might not be covered yet.".format(key)
1602 )
1603 values = "VALUES (" + " ".join(columns) + ")"
1604
1605 rows = ""
1606 for elem in node.res:
1607 row = []
1608 for term in elem.values():
1609 if isinstance(term, Identifier):
1610 row.append(
1611 term.n3()
1612 ) # n3() is not part of Identifier class but every subclass has it
1613 elif isinstance(term, str):
1614 row.append(term)
1615 else:
1616 raise ExpressionNotCoveredException(
1617 "The expression {0} might not be covered yet.".format(
1618 term
1619 )
1620 )
1621 rows += "(" + " ".join(row) + ")"
1622
1623 self._replace("values", values + "{" + rows + "}")
1624 elif node.name == "ServiceGraphPattern":
1625 self._replace(
1626 "{ServiceGraphPattern}",
1627 "SERVICE "
1628 + self.convert_node_arg(node.term)
1629 + "{"
1630 + node.graph.name
1631 + "}",
1632 )
1633 traverse(node.graph, visitPre=self.sparql_query_text)
1634 return node.graph
1635 # else:
1636 # raise ExpressionNotCoveredException("The expression {0} might not be covered yet.".format(node.name))
1637
1638 def translateAlgebra(self) -> str:
1639 traverse(self.query_algebra.algebra, visitPre=self.sparql_query_text)
1640 return self._alg_translation
1641
1642
1643def translateAlgebra(query_algebra: Query) -> str:
1644 """
1645 Translates a SPARQL 1.1 algebra tree into the corresponding query string.
1646
1647 Args:
1648 query_algebra: An algebra returned by `translateQuery`.
1649
1650 Returns:
1651 The query form generated from the SPARQL 1.1 algebra tree for
1652 SELECT queries.
1653 """
1654 query_from_algebra = _AlgebraTranslator(
1655 query_algebra=query_algebra
1656 ).translateAlgebra()
1657 return query_from_algebra
1658
1659
1660def pprintAlgebra(q) -> None:
1661 def pp(p, ind=" "):
1662 # if isinstance(p, list):
1663 # print "[ "
1664 # for x in p: pp(x,ind)
1665 # print "%s ]"%ind
1666 # return
1667 if not isinstance(p, CompValue):
1668 print(p)
1669 return
1670 print("%s(" % (p.name,))
1671 for k in p:
1672 print(
1673 "%s%s ="
1674 % (
1675 ind,
1676 k,
1677 ),
1678 end=" ",
1679 )
1680 pp(p[k], ind + " ")
1681 print("%s)" % ind)
1682
1683 try:
1684 pp(q.algebra)
1685 except AttributeError:
1686 # it's update, just a list
1687 for x in q:
1688 pp(x)