Source code

Download source archive ↓

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)