src/rdflib/paths.py
1r"""
2This module implements the SPARQL 1.1 Property path operators, as
3defined in:
4[http://www.w3.org/TR/sparql11-query/#propertypaths](http://www.w3.org/TR/sparql11-query/#propertypaths)
5
6In SPARQL the syntax is as follows:
7
8| Syntax | Matches |
9|---------------------|-------------------------------------------------------------------------|
10| `iri` | An IRI. A path of length one. |
11| `^elt` | Inverse path (object to subject). |
12| `elt1 / elt2` | A sequence path of `elt1` followed by `elt2`. |
13| `elt1 \| elt2` | An alternative path of `elt1` or `elt2` (all possibilities are tried). |
14| `elt*` | A path that connects subject and object by zero or more matches of `elt`.|
15| `elt+` | A path that connects subject and object by one or more matches of `elt`.|
16| `elt?` | A path that connects subject and object by zero or one matches of `elt`.|
17| `!iri` or <br> `!(iri1 \| ... \| irin)` | Negated property set. An IRI not among `iri1` to `irin`. <br> `!iri` is short for `!(iri)`. |
18| `!^iri` or <br> `!(^iri1 \| ... \| ^irin)` | Negated reverse property set. Excludes `^iri1` to `^irin` as reverse paths. <br> `!^iri` is short for `!(^iri)`. |
19| `!(iri1 \| ... \| irij \| ^irij+1 \| ... \| ^irin)` | A combination of forward and reverse properties in a negated property set. |
20| `(elt)` | A grouped path `elt`, where parentheses control precedence. |
21
22This module is used internally by the SPARQL engine, but the property paths
23can also be used to query RDFLib Graphs directly.
24
25Where possible the SPARQL syntax is mapped to Python operators, and property
26path objects can be constructed from existing URIRefs.
27
28```python
29>>> from rdflib import Graph, Namespace
30>>> from rdflib.namespace import FOAF
31
32>>> ~FOAF.knows
33Path(~http://xmlns.com/foaf/0.1/knows)
34
35>>> FOAF.knows/FOAF.name
36Path(http://xmlns.com/foaf/0.1/knows / http://xmlns.com/foaf/0.1/name)
37
38>>> FOAF.name|FOAF.givenName
39Path(http://xmlns.com/foaf/0.1/name | http://xmlns.com/foaf/0.1/givenName)
40
41```
42
43Modifiers (?, \*, +) are done using \* (the multiplication operator) and
44the strings '\*', '?', '+', also defined as constants in this file.
45
46```python
47>>> FOAF.knows*OneOrMore
48Path(http://xmlns.com/foaf/0.1/knows+)
49
50```
51
52The path objects can also be used with the normal graph methods.
53
54First some example data:
55
56```python
57>>> g=Graph()
58
59>>> g=g.parse(data='''
60... @prefix : <ex:> .
61...
62... :a :p1 :c ; :p2 :f .
63... :c :p2 :e ; :p3 :g .
64... :g :p3 :h ; :p2 :j .
65... :h :p3 :a ; :p2 :g .
66...
67... :q :px :q .
68...
69... ''', format='n3') # doctest: +ELLIPSIS
70
71>>> e = Namespace('ex:')
72
73```
74
75Graph contains:
76
77```python
78>>> (e.a, e.p1/e.p2, e.e) in g
79True
80
81```
82
83Graph generator functions, triples, subjects, objects, etc. :
84
85```python
86>>> list(g.objects(e.c, (e.p3*OneOrMore)/e.p2)) # doctest: +NORMALIZE_WHITESPACE
87[rdflib.term.URIRef('ex:j'), rdflib.term.URIRef('ex:g'),
88 rdflib.term.URIRef('ex:f')]
89
90```
91
92A more complete set of tests:
93
94```python
95>>> list(eval_path(g, (None, e.p1/e.p2, None)))==[(e.a, e.e)]
96True
97>>> list(eval_path(g, (e.a, e.p1|e.p2, None)))==[(e.a,e.c), (e.a,e.f)]
98True
99>>> list(eval_path(g, (e.c, ~e.p1, None))) == [ (e.c, e.a) ]
100True
101>>> list(eval_path(g, (e.a, e.p1*ZeroOrOne, None))) == [(e.a, e.a), (e.a, e.c)]
102True
103>>> list(eval_path(g, (e.c, e.p3*OneOrMore, None))) == [
104... (e.c, e.g), (e.c, e.h), (e.c, e.a)]
105True
106>>> list(eval_path(g, (e.c, e.p3*ZeroOrMore, None))) == [(e.c, e.c),
107... (e.c, e.g), (e.c, e.h), (e.c, e.a)]
108True
109>>> list(eval_path(g, (e.a, -e.p1, None))) == [(e.a, e.f)]
110True
111>>> list(eval_path(g, (e.a, -(e.p1|e.p2), None))) == []
112True
113>>> list(eval_path(g, (e.g, -~e.p2, None))) == [(e.g, e.j)]
114True
115>>> list(eval_path(g, (e.e, ~(e.p1/e.p2), None))) == [(e.e, e.a)]
116True
117>>> list(eval_path(g, (e.a, e.p1/e.p3/e.p3, None))) == [(e.a, e.h)]
118True
119
120>>> list(eval_path(g, (e.q, e.px*OneOrMore, None)))
121[(rdflib.term.URIRef('ex:q'), rdflib.term.URIRef('ex:q'))]
122
123>>> list(eval_path(g, (None, e.p1|e.p2, e.c)))
124[(rdflib.term.URIRef('ex:a'), rdflib.term.URIRef('ex:c'))]
125
126>>> list(eval_path(g, (None, ~e.p1, e.a))) == [ (e.c, e.a) ]
127True
128>>> list(eval_path(g, (None, e.p1*ZeroOrOne, e.c))) # doctest: +NORMALIZE_WHITESPACE
129[(rdflib.term.URIRef('ex:c'), rdflib.term.URIRef('ex:c')),
130 (rdflib.term.URIRef('ex:a'), rdflib.term.URIRef('ex:c'))]
131
132>>> list(eval_path(g, (None, e.p3*OneOrMore, e.a))) # doctest: +NORMALIZE_WHITESPACE
133[(rdflib.term.URIRef('ex:h'), rdflib.term.URIRef('ex:a')),
134 (rdflib.term.URIRef('ex:g'), rdflib.term.URIRef('ex:a')),
135 (rdflib.term.URIRef('ex:c'), rdflib.term.URIRef('ex:a'))]
136
137>>> list(eval_path(g, (None, e.p3*ZeroOrMore, e.a))) # doctest: +NORMALIZE_WHITESPACE
138[(rdflib.term.URIRef('ex:a'), rdflib.term.URIRef('ex:a')),
139 (rdflib.term.URIRef('ex:h'), rdflib.term.URIRef('ex:a')),
140 (rdflib.term.URIRef('ex:g'), rdflib.term.URIRef('ex:a')),
141 (rdflib.term.URIRef('ex:c'), rdflib.term.URIRef('ex:a'))]
142
143>>> list(eval_path(g, (None, -e.p1, e.f))) == [(e.a, e.f)]
144True
145>>> list(eval_path(g, (None, -(e.p1|e.p2), e.c))) == []
146True
147>>> list(eval_path(g, (None, -~e.p2, e.j))) == [(e.g, e.j)]
148True
149>>> list(eval_path(g, (None, ~(e.p1/e.p2), e.a))) == [(e.e, e.a)]
150True
151>>> list(eval_path(g, (None, e.p1/e.p3/e.p3, e.h))) == [(e.a, e.h)]
152True
153
154>>> list(eval_path(g, (e.q, e.px*OneOrMore, None)))
155[(rdflib.term.URIRef('ex:q'), rdflib.term.URIRef('ex:q'))]
156
157>>> list(eval_path(g, (e.c, (e.p2|e.p3)*ZeroOrMore, e.j)))
158[(rdflib.term.URIRef('ex:c'), rdflib.term.URIRef('ex:j'))]
159
160```
161
162No vars specified:
163
164```python
165>>> sorted(list(eval_path(g, (None, e.p3*OneOrMore, None)))) #doctest: +NORMALIZE_WHITESPACE
166[(rdflib.term.URIRef('ex:c'), rdflib.term.URIRef('ex:a')),
167 (rdflib.term.URIRef('ex:c'), rdflib.term.URIRef('ex:g')),
168 (rdflib.term.URIRef('ex:c'), rdflib.term.URIRef('ex:h')),
169 (rdflib.term.URIRef('ex:g'), rdflib.term.URIRef('ex:a')),
170 (rdflib.term.URIRef('ex:g'), rdflib.term.URIRef('ex:h')),
171 (rdflib.term.URIRef('ex:h'), rdflib.term.URIRef('ex:a'))]
172
173```
174"""
175
176from __future__ import annotations
177
178import warnings
179from abc import ABC, abstractmethod
180from functools import total_ordering
181from typing import (
182 TYPE_CHECKING,
183 Any,
184 Callable,
185 Generator,
186 Iterator,
187 List,
188 Optional,
189 Set,
190 Tuple,
191 Union,
192)
193
194from rdflib.term import Node, URIRef
195
196if TYPE_CHECKING:
197 from rdflib._type_checking import _MulPathMod
198 from rdflib.graph import Graph, _ObjectType, _PredicateType, _SubjectType
199 from rdflib.namespace import NamespaceManager
200
201
202# property paths
203
204ZeroOrMore = "*"
205OneOrMore = "+"
206ZeroOrOne = "?"
207
208
209def _n3(
210 arg: Union[URIRef, Path], namespace_manager: Optional[NamespaceManager] = None
211) -> str:
212 if isinstance(arg, (SequencePath, AlternativePath)) and len(arg.args) > 1:
213 return "(%s)" % arg.n3(namespace_manager)
214 return arg.n3(namespace_manager)
215
216
217@total_ordering
218class Path(ABC):
219 """Base class for all property paths."""
220
221 __or__: Callable[[Path, Union[URIRef, Path]], AlternativePath]
222 __invert__: Callable[[Path], InvPath]
223 __neg__: Callable[[Path], NegatedPath]
224 __truediv__: Callable[[Path, Union[URIRef, Path]], SequencePath]
225 __mul__: Callable[[Path, str], MulPath]
226
227 @abstractmethod
228 def eval(
229 self,
230 graph: Graph,
231 subj: Optional[_SubjectType] = None,
232 obj: Optional[_ObjectType] = None,
233 ) -> Iterator[Tuple[_SubjectType, _ObjectType]]: ...
234
235 @abstractmethod
236 def n3(self, namespace_manager: Optional[NamespaceManager] = None) -> str: ...
237
238 def __hash__(self):
239 return hash(repr(self))
240
241 def __eq__(self, other):
242 return repr(self) == repr(other)
243
244 def __lt__(self, other: Any) -> bool:
245 if not isinstance(other, (Path, Node)):
246 raise TypeError(
247 "unorderable types: %s() < %s()" % (repr(self), repr(other))
248 )
249 return repr(self) < repr(other)
250
251
252class InvPath(Path):
253 def __init__(self, arg: Union[Path, URIRef]):
254 self.arg = arg
255
256 def eval(
257 self,
258 graph: Graph,
259 subj: Optional[_SubjectType] = None,
260 obj: Optional[_ObjectType] = None,
261 ) -> Generator[Tuple[_ObjectType, _SubjectType], None, None]:
262 for s, o in eval_path(graph, (obj, self.arg, subj)):
263 yield o, s
264
265 def __repr__(self) -> str:
266 return "Path(~%s)" % (self.arg,)
267
268 def n3(self, namespace_manager: Optional[NamespaceManager] = None) -> str:
269 return "^%s" % _n3(self.arg, namespace_manager)
270
271
272class SequencePath(Path):
273 def __init__(self, *args: Union[Path, URIRef]):
274 self.args: List[Union[Path, URIRef]] = []
275 for a in args:
276 if isinstance(a, SequencePath):
277 self.args += a.args
278 else:
279 self.args.append(a)
280
281 def eval(
282 self,
283 graph: Graph,
284 subj: Optional[_SubjectType] = None,
285 obj: Optional[_ObjectType] = None,
286 ) -> Generator[Tuple[_SubjectType, _ObjectType], None, None]:
287 def _eval_seq(
288 paths: List[Union[Path, URIRef]],
289 subj: Optional[_SubjectType],
290 obj: Optional[_ObjectType],
291 ) -> Generator[Tuple[_SubjectType, _ObjectType], None, None]:
292 if paths[1:]:
293 for s, o in eval_path(graph, (subj, paths[0], None)):
294 for r in _eval_seq(paths[1:], o, obj):
295 yield s, r[1]
296
297 else:
298 for s, o in eval_path(graph, (subj, paths[0], obj)):
299 yield s, o
300
301 def _eval_seq_bw(
302 paths: List[Union[Path, URIRef]],
303 subj: Optional[_SubjectType],
304 obj: _ObjectType,
305 ) -> Generator[Tuple[_SubjectType, _ObjectType], None, None]:
306 if paths[:-1]:
307 for s, o in eval_path(graph, (None, paths[-1], obj)):
308 for r in _eval_seq(paths[:-1], subj, s):
309 yield r[0], o
310
311 else:
312 for s, o in eval_path(graph, (subj, paths[0], obj)):
313 yield s, o
314
315 if subj:
316 return _eval_seq(self.args, subj, obj)
317 elif obj:
318 return _eval_seq_bw(self.args, subj, obj)
319 else: # no vars bound, we can start anywhere
320 return _eval_seq(self.args, subj, obj)
321
322 def __repr__(self) -> str:
323 return "Path(%s)" % " / ".join(str(x) for x in self.args)
324
325 def n3(self, namespace_manager: Optional[NamespaceManager] = None) -> str:
326 return "/".join(_n3(a, namespace_manager) for a in self.args)
327
328
329class AlternativePath(Path):
330 def __init__(self, *args: Union[Path, URIRef]):
331 self.args: List[Union[Path, URIRef]] = []
332 for a in args:
333 if isinstance(a, AlternativePath):
334 self.args += a.args
335 else:
336 self.args.append(a)
337
338 def eval(
339 self,
340 graph: Graph,
341 subj: Optional[_SubjectType] = None,
342 obj: Optional[_ObjectType] = None,
343 ) -> Generator[Tuple[_SubjectType, _ObjectType], None, None]:
344 for x in self.args:
345 for y in eval_path(graph, (subj, x, obj)):
346 yield y
347
348 def __repr__(self) -> str:
349 return "Path(%s)" % " | ".join(str(x) for x in self.args)
350
351 def n3(self, namespace_manager: Optional[NamespaceManager] = None) -> str:
352 return "|".join(_n3(a, namespace_manager) for a in self.args)
353
354
355class MulPath(Path):
356 def __init__(self, path: Union[Path, URIRef], mod: _MulPathMod):
357 self.path = path
358 self.mod = mod
359
360 if mod == ZeroOrOne:
361 self.zero = True
362 self.more = False
363 elif mod == ZeroOrMore:
364 self.zero = True
365 self.more = True
366 elif mod == OneOrMore:
367 self.zero = False
368 self.more = True
369 else:
370 raise Exception("Unknown modifier %s" % mod)
371
372 def eval(
373 self,
374 graph: Graph,
375 subj: Optional[_SubjectType] = None,
376 obj: Optional[_ObjectType] = None,
377 first: bool = True,
378 ) -> Generator[Tuple[_SubjectType, _ObjectType], None, None]:
379 if self.zero and first:
380 if subj and obj:
381 if subj == obj:
382 yield subj, obj
383 elif subj:
384 yield subj, subj
385 elif obj:
386 yield obj, obj
387
388 def _fwd(
389 subj: Optional[_SubjectType] = None,
390 obj: Optional[_ObjectType] = None,
391 seen: Optional[Set[_SubjectType]] = None,
392 ) -> Generator[Tuple[_SubjectType, _ObjectType], None, None]:
393 # type error: Item "None" of "Optional[Set[Node]]" has no attribute "add"
394 # type error: Argument 1 to "add" of "set" has incompatible type "Optional[Node]"; expected "Node"
395 seen.add(subj) # type: ignore[union-attr, arg-type]
396
397 for s, o in eval_path(graph, (subj, self.path, None)):
398 if not obj or o == obj:
399 yield s, o
400 if self.more:
401 # type error: Unsupported right operand type for in ("Optional[Set[Node]]")
402 if o in seen: # type: ignore[operator]
403 continue
404 for s2, o2 in _fwd(o, obj, seen):
405 yield s, o2
406
407 def _bwd(
408 subj: Optional[_SubjectType] = None,
409 obj: Optional[_ObjectType] = None,
410 seen: Optional[Set[_ObjectType]] = None,
411 ) -> Generator[Tuple[_SubjectType, _ObjectType], None, None]:
412 # type error: Item "None" of "Optional[Set[Node]]" has no attribute "add"
413 # type error: Argument 1 to "add" of "set" has incompatible type "Optional[Node]"; expected "Node"
414 seen.add(obj) # type: ignore[union-attr, arg-type]
415
416 for s, o in eval_path(graph, (None, self.path, obj)):
417 if not subj or subj == s:
418 yield s, o
419 if self.more:
420 # type error: Unsupported right operand type for in ("Optional[Set[Node]]")
421 if s in seen: # type: ignore[operator]
422 continue
423
424 for s2, o2 in _bwd(None, s, seen):
425 yield s2, o
426
427 def _all_fwd_paths() -> Generator[Tuple[_SubjectType, _ObjectType], None, None]:
428 if self.zero:
429 seen1 = set()
430 # According to the spec, ALL nodes are possible solutions
431 # (even literals)
432 # we cannot do this without going through ALL triples
433 # unless we keep an index of all terms somehow
434 # but let's just hope this query doesn't happen very often...
435 for s, o in graph.subject_objects(None):
436 if s not in seen1:
437 seen1.add(s)
438 yield s, s
439 if o not in seen1:
440 seen1.add(o)
441 yield o, o
442
443 seen = set()
444 for s, o in eval_path(graph, (None, self.path, None)):
445 if not self.more:
446 yield s, o
447 else:
448 if s not in seen:
449 seen.add(s)
450 f = list(_fwd(s, None, set()))
451 for s1, o1 in f:
452 assert s1 == s
453 yield s1, o1
454
455 done = set() # the spec does, by defn, not allow duplicates
456 if subj:
457 for x in _fwd(subj, obj, set()):
458 if x not in done:
459 done.add(x)
460 yield x
461 elif obj:
462 for x in _bwd(subj, obj, set()):
463 if x not in done:
464 done.add(x)
465 yield x
466 else:
467 for x in _all_fwd_paths():
468 if x not in done:
469 done.add(x)
470 yield x
471
472 def __repr__(self) -> str:
473 return "Path(%s%s)" % (self.path, self.mod)
474
475 def n3(self, namespace_manager: Optional[NamespaceManager] = None) -> str:
476 return "%s%s" % (_n3(self.path, namespace_manager), self.mod)
477
478
479class NegatedPath(Path):
480 def __init__(self, arg: Union[AlternativePath, InvPath, URIRef]):
481 self.args: List[Union[URIRef, Path]]
482 if isinstance(arg, (URIRef, InvPath)):
483 self.args = [arg]
484 elif isinstance(arg, AlternativePath):
485 self.args = arg.args
486 else:
487 raise Exception(
488 "Can only negate URIRefs, InvPaths or "
489 + "AlternativePaths, not: %s" % (arg,)
490 )
491
492 def eval(self, graph, subj=None, obj=None):
493 for s, p, o in graph.triples((subj, None, obj)):
494 for a in self.args:
495 if isinstance(a, URIRef):
496 if p == a:
497 break
498 elif isinstance(a, InvPath):
499 if (o, a.arg, s) in graph:
500 break
501 else:
502 raise Exception("Invalid path in NegatedPath: %s" % a)
503 else:
504 yield s, o
505
506 def __repr__(self) -> str:
507 return "Path(! %s)" % ",".join(str(x) for x in self.args)
508
509 def n3(self, namespace_manager: Optional[NamespaceManager] = None) -> str:
510 return "!(%s)" % ("|".join(_n3(arg, namespace_manager) for arg in self.args))
511
512
513class PathList(list):
514 pass
515
516
517def path_alternative(self: Union[URIRef, Path], other: Union[URIRef, Path]):
518 """
519 alternative path
520 """
521 if not isinstance(other, (URIRef, Path)):
522 raise Exception("Only URIRefs or Paths can be in paths!")
523 return AlternativePath(self, other)
524
525
526def path_sequence(self: Union[URIRef, Path], other: Union[URIRef, Path]):
527 """
528 sequence path
529 """
530 if not isinstance(other, (URIRef, Path)):
531 raise Exception("Only URIRefs or Paths can be in paths!")
532 return SequencePath(self, other)
533
534
535def evalPath( # noqa: N802
536 graph: Graph,
537 t: Tuple[
538 Optional[_SubjectType],
539 Union[None, Path, _PredicateType],
540 Optional[_ObjectType],
541 ],
542) -> Iterator[Tuple[_SubjectType, _ObjectType]]:
543 warnings.warn(
544 DeprecationWarning(
545 "rdflib.path.evalPath() is deprecated, use the (snake-cased) eval_path(). "
546 "The mixed-case evalPath() function name is incompatible with PEP8 "
547 "recommendations and will be replaced by eval_path() in rdflib 7.0.0."
548 )
549 )
550 return eval_path(graph, t)
551
552
553def eval_path(
554 graph: Graph,
555 t: Tuple[
556 Optional[_SubjectType],
557 Union[None, Path, _PredicateType],
558 Optional[_ObjectType],
559 ],
560) -> Iterator[Tuple[_SubjectType, _ObjectType]]:
561 return ((s, o) for s, p, o in graph.triples(t))
562
563
564def mul_path(p: Union[URIRef, Path], mul: _MulPathMod) -> MulPath:
565 """
566 cardinality path
567 """
568 return MulPath(p, mul)
569
570
571def inv_path(p: Union[URIRef, Path]) -> InvPath:
572 """
573 inverse path
574 """
575 return InvPath(p)
576
577
578def neg_path(p: Union[URIRef, AlternativePath, InvPath]) -> NegatedPath:
579 """
580 negated path
581 """
582 return NegatedPath(p)
583
584
585if __name__ == "__main__":
586 pass
587else:
588 # monkey patch
589 # (these cannot be directly in terms.py
590 # as it would introduce circular imports)
591
592 URIRef.__or__ = path_alternative
593 # ignore typing here as URIRef inherits from str,
594 # which has an incompatible definition of __mul__.
595 URIRef.__mul__ = mul_path # type: ignore
596 URIRef.__invert__ = inv_path
597 URIRef.__neg__ = neg_path
598 URIRef.__truediv__ = path_sequence
599
600 Path.__invert__ = inv_path
601 # type error: Incompatible types in assignment (expression has type "Callable[[Union[URIRef, AlternativePath, InvPath]], NegatedPath]", variable has type "Callable[[Path], NegatedPath]")
602 Path.__neg__ = neg_path # type: ignore[assignment]
603 # type error: Incompatible types in assignment (expression has type "Callable[[Union[URIRef, Path], Literal['*', '+', '?']], MulPath]", variable has type "Callable[[Path, str], MulPath]")
604 Path.__mul__ = mul_path # type: ignore[assignment]
605 Path.__or__ = path_alternative
606 Path.__truediv__ = path_sequence