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)