Source code

Download source archive ↓

src/rdflib/plugins/sparql/evaluate.py

1"""
2These method recursively evaluate the SPARQL Algebra
3
4evalQuery is the entry-point, it will setup context and
5return the SPARQLResult object
6
7evalPart is called on each level and will delegate to the right method
8
9A `rdflib.plugins.sparql.sparql.QueryContext` is passed along, keeping
10information needed for evaluation
11
12A list of dicts (solution mappings) is returned, apart from GroupBy which may
13also return a dict of list of dicts
14"""
15
16from __future__ import annotations
17
18import collections
19import itertools
20import re
21from typing import (
22    TYPE_CHECKING,
23    Any,
24    Deque,
25    Dict,
26    Generator,
27    Iterable,
28    List,
29    Mapping,
30    Optional,
31    Tuple,
32    Union,
33)
34from urllib.parse import urlencode
35from urllib.request import Request, urlopen
36
37from pyparsing import ParseException
38
39from rdflib.graph import Graph
40from rdflib.plugins.sparql import CUSTOM_EVALS, parser
41from rdflib.plugins.sparql.aggregates import Aggregator
42from rdflib.plugins.sparql.evalutils import (
43    _ebv,
44    _eval,
45    _fillTemplate,
46    _join,
47    _minus,
48    _val,
49)
50from rdflib.plugins.sparql.parserutils import CompValue, value
51from rdflib.plugins.sparql.sparql import (
52    AlreadyBound,
53    FrozenBindings,
54    FrozenDict,
55    Query,
56    QueryContext,
57    SPARQLError,
58)
59from rdflib.term import BNode, Identifier, Literal, URIRef, Variable
60
61if TYPE_CHECKING:
62    from rdflib.paths import Path
63
64import json
65
66try:
67    import orjson
68
69    _HAS_ORJSON = True
70except ImportError:
71    orjson = None  # type: ignore[assignment, unused-ignore]
72    _HAS_ORJSON = False
73
74_Triple = Tuple[Identifier, Identifier, Identifier]
75
76
77def evalBGP(
78    ctx: QueryContext, bgp: List[_Triple]
79) -> Generator[FrozenBindings, None, None]:
80    """
81    A basic graph pattern
82    """
83
84    if not bgp:
85        yield ctx.solution()
86        return
87
88    s, p, o = bgp[0]
89
90    _s = ctx[s]
91    _p = ctx[p]
92    _o = ctx[o]
93
94    # type error: Item "None" of "Optional[Graph]" has no attribute "triples"
95    # type Argument 1 to "triples" of "Graph" has incompatible type "Tuple[Union[str, Path, None], Union[str, Path, None], Union[str, Path, None]]"; expected "Tuple[Optional[Node], Optional[Node], Optional[Node]]"
96    for ss, sp, so in ctx.graph.triples((_s, _p, _o)):  # type: ignore[union-attr, arg-type]
97        if None in (_s, _p, _o):
98            c = ctx.push()
99        else:
100            c = ctx
101
102        if _s is None:
103            # type error: Incompatible types in assignment (expression has type "Union[Node, Any]", target has type "Identifier")
104            c[s] = ss  # type: ignore[assignment]
105
106        try:
107            if _p is None:
108                # type error: Incompatible types in assignment (expression has type "Union[Node, Any]", target has type "Identifier")
109                c[p] = sp  # type: ignore[assignment]
110        except AlreadyBound:
111            continue
112
113        try:
114            if _o is None:
115                # type error: Incompatible types in assignment (expression has type "Union[Node, Any]", target has type "Identifier")
116                c[o] = so  # type: ignore[assignment]
117        except AlreadyBound:
118            continue
119
120        for x in evalBGP(c, bgp[1:]):
121            yield x
122
123
124def evalExtend(
125    ctx: QueryContext, extend: CompValue
126) -> Generator[FrozenBindings, None, None]:
127    # TODO: Deal with dict returned from evalPart from GROUP BY
128
129    for c in evalPart(ctx, extend.p):
130        try:
131            e = _eval(extend.expr, c.forget(ctx, _except=extend._vars))
132            if isinstance(e, SPARQLError):
133                raise e
134
135            yield c.merge({extend.var: e})
136
137        except SPARQLError:
138            yield c
139
140
141def evalLazyJoin(
142    ctx: QueryContext, join: CompValue
143) -> Generator[FrozenBindings, None, None]:
144    """
145    A lazy join will push the variables bound
146    in the first part to the second part,
147    essentially doing the join implicitly
148    hopefully evaluating much fewer triples
149    """
150    for a in evalPart(ctx, join.p1):
151        c = ctx.thaw(a)
152        for b in evalPart(c, join.p2):
153            yield b.merge(a)  # merge, as some bindings may have been forgotten
154
155
156def evalJoin(ctx: QueryContext, join: CompValue) -> Generator[FrozenDict, None, None]:
157    # TODO: Deal with dict returned from evalPart from GROUP BY
158    # only ever for join.p1
159
160    if join.lazy:
161        return evalLazyJoin(ctx, join)
162    else:
163        a = evalPart(ctx, join.p1)
164        b = set(evalPart(ctx, join.p2))
165        return _join(a, b)
166
167
168def evalUnion(ctx: QueryContext, union: CompValue) -> List[Any]:
169    branch1_branch2 = []
170    for x in evalPart(ctx, union.p1):
171        branch1_branch2.append(x)
172    for x in evalPart(ctx, union.p2):
173        branch1_branch2.append(x)
174    return branch1_branch2
175
176
177def evalMinus(ctx: QueryContext, minus: CompValue) -> Generator[FrozenDict, None, None]:
178    a = evalPart(ctx, minus.p1)
179    b = set(evalPart(ctx, minus.p2))
180    return _minus(a, b)
181
182
183def evalLeftJoin(
184    ctx: QueryContext, join: CompValue
185) -> Generator[FrozenBindings, None, None]:
186    # import pdb; pdb.set_trace()
187    for a in evalPart(ctx, join.p1):
188        ok = False
189        c = ctx.thaw(a)
190        for b in evalPart(c, join.p2):
191            if _ebv(join.expr, b.forget(ctx)):
192                ok = True
193                yield b.merge(a)
194        if not ok:
195            # we've cheated, the ctx above may contain
196            # vars bound outside our scope
197            # before we yield a solution without the OPTIONAL part
198            # check that we would have had no OPTIONAL matches
199            # even without prior bindings...
200            p1_vars = join.p1._vars
201            if p1_vars is None or not any(
202                _ebv(join.expr, b)
203                for b in evalPart(ctx.thaw(a.remember(p1_vars)), join.p2)
204            ):
205                yield a
206
207
208def evalFilter(
209    ctx: QueryContext, part: CompValue
210) -> Generator[FrozenBindings, None, None]:
211    # TODO: Deal with dict returned from evalPart!
212    for c in evalPart(ctx, part.p):
213        if _ebv(
214            part.expr,
215            c.forget(ctx, _except=part._vars) if not part.no_isolated_scope else c,
216        ):
217            yield c
218
219
220def evalGraph(
221    ctx: QueryContext, part: CompValue
222) -> Generator[FrozenBindings, None, None]:
223    if ctx.dataset is None:
224        raise Exception(
225            "Non-conjunctive-graph doesn't know about "
226            + "graphs. Try a query without GRAPH."
227        )
228
229    ctx = ctx.clone()
230    graph: Union[str, Path, None, Graph] = ctx[part.term]
231    prev_graph = ctx.graph
232    if graph is None:
233        for graph in ctx.dataset.contexts():
234            # in SPARQL the default graph is NOT a named graph
235            if graph == ctx.dataset.default_context:
236                continue
237
238            c = ctx.pushGraph(graph)
239            c = c.push()
240            graphSolution = [{part.term: graph.identifier}]
241            for x in _join(evalPart(c, part.p), graphSolution):
242                x.ctx.graph = prev_graph
243                yield x
244
245    else:
246        if TYPE_CHECKING:
247            assert not isinstance(graph, Graph)
248        # type error: Argument 1 to "get_context" of "ConjunctiveGraph" has incompatible type "Union[str, Path]"; expected "Union[Node, str, None]"
249        c = ctx.pushGraph(ctx.dataset.get_context(graph))  # type: ignore[arg-type]
250        for x in evalPart(c, part.p):
251            x.ctx.graph = prev_graph
252            yield x
253
254
255def evalValues(
256    ctx: QueryContext, part: CompValue
257) -> Generator[FrozenBindings, None, None]:
258    for r in part.p.res:
259        c = ctx.push()
260        try:
261            for k, v in r.items():
262                if v != "UNDEF":
263                    c[k] = v
264        except AlreadyBound:
265            continue
266
267        yield c.solution()
268
269
270def evalMultiset(ctx: QueryContext, part: CompValue):
271    if part.p.name == "values":
272        return evalValues(ctx, part)
273
274    return evalPart(ctx, part.p)
275
276
277def evalPart(ctx: QueryContext, part: CompValue) -> Any:
278    # try custom evaluation functions
279    for name, c in CUSTOM_EVALS.items():
280        try:
281            return c(ctx, part)
282        except NotImplementedError:
283            pass  # the given custome-function did not handle this part
284
285    if part.name == "BGP":
286        # Reorder triples patterns by number of bound nodes in the current ctx
287        # Do patterns with more bound nodes first
288        triples = sorted(
289            part.triples, key=lambda t: len([n for n in t if ctx[n] is None])
290        )
291
292        return evalBGP(ctx, triples)
293    elif part.name == "Filter":
294        return evalFilter(ctx, part)
295    elif part.name == "Join":
296        return evalJoin(ctx, part)
297    elif part.name == "LeftJoin":
298        return evalLeftJoin(ctx, part)
299    elif part.name == "Graph":
300        return evalGraph(ctx, part)
301    elif part.name == "Union":
302        return evalUnion(ctx, part)
303    elif part.name == "ToMultiSet":
304        return evalMultiset(ctx, part)
305    elif part.name == "Extend":
306        return evalExtend(ctx, part)
307    elif part.name == "Minus":
308        return evalMinus(ctx, part)
309
310    elif part.name == "Project":
311        return evalProject(ctx, part)
312    elif part.name == "Slice":
313        return evalSlice(ctx, part)
314    elif part.name == "Distinct":
315        return evalDistinct(ctx, part)
316    elif part.name == "Reduced":
317        return evalReduced(ctx, part)
318
319    elif part.name == "OrderBy":
320        return evalOrderBy(ctx, part)
321    elif part.name == "Group":
322        return evalGroup(ctx, part)
323    elif part.name == "AggregateJoin":
324        return evalAggregateJoin(ctx, part)
325
326    elif part.name == "SelectQuery":
327        return evalSelectQuery(ctx, part)
328    elif part.name == "AskQuery":
329        return evalAskQuery(ctx, part)
330    elif part.name == "ConstructQuery":
331        return evalConstructQuery(ctx, part)
332
333    elif part.name == "ServiceGraphPattern":
334        return evalServiceQuery(ctx, part)
335
336    elif part.name == "DescribeQuery":
337        return evalDescribeQuery(ctx, part)
338
339    else:
340        raise Exception("I dont know: %s" % part.name)
341
342
343def evalServiceQuery(ctx: QueryContext, part: CompValue):
344    res = {}
345    match = re.match(
346        "^service <(.*)>[ \n]*{(.*)}[ \n]*$",
347        # type error: Argument 2 to "get" of "CompValue" has incompatible type "str"; expected "bool"  [arg-type]
348        part.get("service_string", ""),  # type: ignore[arg-type]
349        re.DOTALL | re.I,
350    )
351
352    if match:
353        service_url = match.group(1)
354        service_query = _buildQueryStringForServiceCall(ctx, match.group(2))
355
356        query_settings = {"query": service_query, "output": "json"}
357        headers = {
358            "accept": "application/sparql-results+json",
359            "user-agent": "rdflibForAnUser",
360        }
361        # GET is easier to cache so prefer that if the query is not to long
362        if len(service_query) < 600:
363            response = urlopen(
364                Request(service_url + "?" + urlencode(query_settings), headers=headers)
365            )
366        else:
367            response = urlopen(
368                Request(
369                    service_url,
370                    data=urlencode(query_settings).encode(),
371                    headers=headers,
372                )
373            )
374        if response.status == 200:
375            if _HAS_ORJSON:
376                json_dict = orjson.loads(response.read())
377            else:
378                json_dict = json.loads(response.read())
379            variables = res["vars_"] = json_dict["head"]["vars"]
380            # or just return the bindings?
381            res = json_dict["results"]["bindings"]
382            if len(res) > 0:
383                for r in res:
384                    # type error: Argument 2 to "_yieldBindingsFromServiceCallResult" has incompatible type "str"; expected "Dict[str, Dict[str, str]]"
385                    for bound in _yieldBindingsFromServiceCallResult(ctx, r, variables):  # type: ignore[arg-type]
386                        yield bound
387        else:
388            raise Exception(
389                "Service: %s responded with code: %s", service_url, response.status
390            )
391
392
393"""
394    Build a query string to be used by the service call.
395    It is supposed to pass in the existing bound solutions.
396    Re-adds prefixes if added and sets the base.
397    Wraps it in select if needed.
398"""
399
400
401def _buildQueryStringForServiceCall(ctx: QueryContext, service_query: str) -> str:
402    try:
403        parser.parseQuery(service_query)
404    except ParseException:
405        # This could be because we don't have a select around the service call.
406        service_query = "SELECT REDUCED * WHERE {" + service_query + "}"
407        # type error: Item "None" of "Optional[Prologue]" has no attribute "namespace_manager"
408        for p in ctx.prologue.namespace_manager.store.namespaces():  # type: ignore[union-attr]
409            service_query = "PREFIX " + p[0] + ":" + p[1].n3() + " " + service_query
410        # re add the base if one was defined
411        # type error: Item "None" of "Optional[Prologue]" has no attribute "base"
412        base = ctx.prologue.base  # type: ignore[union-attr]
413        if base is not None and len(base) > 0:
414            service_query = "BASE <" + base + "> " + service_query
415    sol = [v for v in ctx.solution() if isinstance(v, Variable)]
416    if len(sol) > 0:
417        variables = " ".join([v.n3() for v in sol])
418        variables_bound = " ".join([ctx.get(v).n3() for v in sol])
419        service_query = (
420            service_query + "VALUES (" + variables + ") {(" + variables_bound + ")}"
421        )
422    return service_query
423
424
425def _yieldBindingsFromServiceCallResult(
426    ctx: QueryContext, r: Dict[str, Dict[str, str]], variables: List[str]
427) -> Generator[FrozenBindings, None, None]:
428    res_dict: Dict[Variable, Identifier] = {}
429    for var in variables:
430        if var in r and r[var]:
431            var_binding = r[var]
432            var_type = var_binding["type"]
433            if var_type == "uri":
434                res_dict[Variable(var)] = URIRef(var_binding["value"])
435            elif var_type == "literal":
436                res_dict[Variable(var)] = Literal(
437                    var_binding["value"],
438                    datatype=var_binding.get("datatype"),
439                    lang=var_binding.get("xml:lang"),
440                )
441            # This is here because of
442            # https://www.w3.org/TR/2006/NOTE-rdf-sparql-json-res-20061004/#variable-binding-results
443            elif var_type == "typed-literal":
444                res_dict[Variable(var)] = Literal(
445                    var_binding["value"], datatype=URIRef(var_binding["datatype"])
446                )
447            elif var_type == "bnode":
448                res_dict[Variable(var)] = BNode(var_binding["value"])
449            else:
450                raise ValueError(f"invalid type {var_type!r} for variable {var!r}")
451    yield FrozenBindings(ctx, res_dict)
452
453
454def evalGroup(ctx: QueryContext, group: CompValue):
455    """
456    http://www.w3.org/TR/sparql11-query/#defn_algGroup
457    """
458    # grouping should be implemented by evalAggregateJoin
459    return evalPart(ctx, group.p)
460
461
462def evalAggregateJoin(
463    ctx: QueryContext, agg: CompValue
464) -> Generator[FrozenBindings, None, None]:
465    # import pdb ; pdb.set_trace()
466    p = evalPart(ctx, agg.p)
467    # p is always a Group, we always get a dict back
468
469    group_expr = agg.p.expr
470    res: Dict[Any, Any] = collections.defaultdict(
471        lambda: Aggregator(aggregations=agg.A)
472    )
473
474    if group_expr is None:
475        # no grouping, just COUNT in SELECT clause
476        # get 1 aggregator for counting
477        aggregator = res[True]
478        for row in p:
479            aggregator.update(row)
480    else:
481        for row in p:
482            # determine right group aggregator for row
483            k = tuple(_eval(e, row, False) for e in group_expr)
484            res[k].update(row)
485
486    # all rows are done; yield aggregated values
487    for aggregator in res.values():
488        yield FrozenBindings(ctx, aggregator.get_bindings())
489
490    # there were no matches
491    if len(res) == 0:
492        yield FrozenBindings(ctx)
493
494
495def evalOrderBy(
496    ctx: QueryContext, part: CompValue
497) -> Generator[FrozenBindings, None, None]:
498    res = evalPart(ctx, part.p)
499
500    for e in reversed(part.expr):
501        reverse = bool(e.order and e.order == "DESC")
502        res = sorted(
503            res, key=lambda x: _val(value(x, e.expr, variables=True)), reverse=reverse
504        )
505
506    return res
507
508
509def evalSlice(ctx: QueryContext, slice: CompValue):
510    res = evalPart(ctx, slice.p)
511
512    return itertools.islice(
513        res,
514        slice.start,
515        slice.start + slice.length if slice.length is not None else None,
516    )
517
518
519def evalReduced(
520    ctx: QueryContext, part: CompValue
521) -> Generator[FrozenBindings, None, None]:
522    """apply REDUCED to result
523
524    REDUCED is not as strict as DISTINCT, but if the incoming rows were sorted
525    it should produce the same result with limited extra memory and time per
526    incoming row.
527    """
528
529    # This implementation uses a most recently used strategy and a limited
530    # buffer size. It relates to a LRU caching algorithm:
531    # https://en.wikipedia.org/wiki/Cache_algorithms#Least_Recently_Used_.28LRU.29
532    MAX = 1
533    # TODO: add configuration or determine "best" size for most use cases
534    # 0: No reduction
535    # 1: compare only with the last row, almost no reduction with
536    #    unordered incoming rows
537    # N: The greater the buffer size the greater the reduction but more
538    #    memory and time are needed
539
540    # mixed data structure: set for lookup, deque for append/pop/remove
541    mru_set = set()
542    mru_queue: Deque[Any] = collections.deque()
543
544    for row in evalPart(ctx, part.p):
545        if row in mru_set:
546            # forget last position of row
547            mru_queue.remove(row)
548        else:
549            # row seems to be new
550            yield row
551            mru_set.add(row)
552            if len(mru_set) > MAX:
553                # drop the least recently used row from buffer
554                mru_set.remove(mru_queue.pop())
555        # put row to the front
556        mru_queue.appendleft(row)
557
558
559def evalDistinct(
560    ctx: QueryContext, part: CompValue
561) -> Generator[FrozenBindings, None, None]:
562    res = evalPart(ctx, part.p)
563
564    done = set()
565    for x in res:
566        if x not in done:
567            yield x
568            done.add(x)
569
570
571def evalProject(ctx: QueryContext, project: CompValue):
572    res = evalPart(ctx, project.p)
573    return (row.project(project.PV) for row in res)
574
575
576def evalSelectQuery(
577    ctx: QueryContext, query: CompValue
578) -> Mapping[str, Union[str, List[Variable], Iterable[FrozenDict]]]:
579    res: Dict[str, Union[str, List[Variable], Iterable[FrozenDict]]] = {}
580    res["type_"] = "SELECT"
581    res["bindings"] = evalPart(ctx, query.p)
582    res["vars_"] = query.PV
583    return res
584
585
586def evalAskQuery(ctx: QueryContext, query: CompValue) -> Mapping[str, Union[str, bool]]:
587    res: Dict[str, Union[bool, str]] = {}
588    res["type_"] = "ASK"
589    res["askAnswer"] = False
590    for x in evalPart(ctx, query.p):
591        res["askAnswer"] = True
592        break
593
594    return res
595
596
597def evalConstructQuery(
598    ctx: QueryContext, query: CompValue
599) -> Mapping[str, Union[str, Graph]]:
600    template = query.template
601
602    if not template:
603        # a construct-where query
604        template = query.p.p.triples  # query->project->bgp ...
605
606    graph = Graph()
607
608    for c in evalPart(ctx, query.p):
609        graph += _fillTemplate(template, c)
610
611    res: Dict[str, Union[str, Graph]] = {}
612    res["type_"] = "CONSTRUCT"
613    res["graph"] = graph
614
615    return res
616
617
618def evalDescribeQuery(ctx: QueryContext, query) -> Dict[str, Union[str, Graph]]:
619    # Create a result graph and bind namespaces from the graph being queried
620    graph = Graph()
621    # type error: Item "None" of "Optional[Graph]" has no attribute "namespaces"
622    for pfx, ns in ctx.graph.namespaces():  # type: ignore[union-attr]
623        graph.bind(pfx, ns)
624
625    to_describe = set()
626
627    # Explicit IRIs may be provided to a DESCRIBE query.
628    # If there is a WHERE clause, explicit IRIs may be provided in
629    # addition to projected variables. Find those explicit IRIs and
630    # prepare to describe them.
631    for iri in query.PV:
632        if isinstance(iri, URIRef):
633            to_describe.add(iri)
634
635    # If there is a WHERE clause, evaluate it then find the unique set of
636    # resources to describe across all bindings and projected variables
637    if query.p is not None:
638        bindings = evalPart(ctx, query.p)
639        to_describe.update(*(set(binding.values()) for binding in bindings))
640
641    # Get a CBD for all resources identified to describe
642    for resource in to_describe:
643        # type error: Item "None" of "Optional[Graph]" has no attribute "cbd"
644        ctx.graph.cbd(resource, target_graph=graph)  # type: ignore[union-attr]
645
646    res: Dict[str, Union[str, Graph]] = {}
647    res["type_"] = "DESCRIBE"
648    res["graph"] = graph
649
650    return res
651
652
653def evalQuery(
654    graph: Graph,
655    query: Query,
656    initBindings: Optional[Mapping[str, Identifier]] = None,
657    base: Optional[str] = None,
658) -> Mapping[Any, Any]:
659    """Evaluate a SPARQL query against a graph.
660
661    !!! warning "Caution"
662
663        This method can access indirectly requested network endpoints, for
664        example, query processing will attempt to access network endpoints
665        specified in `SERVICE` directives.
666
667        When processing untrusted or potentially malicious queries, measures
668        should be taken to restrict network and file access.
669
670        For information on available security measures, see the RDFLib
671        [Security Considerations](../security_considerations.md)
672        documentation.
673    """
674    main = query.algebra
675
676    initBindings = dict((Variable(k), v) for k, v in (initBindings or {}).items())
677
678    ctx = QueryContext(
679        graph, initBindings=initBindings, datasetClause=main.datasetClause
680    )
681
682    ctx.prologue = query.prologue
683
684    return evalPart(ctx, main)