Source code

Download source archive ↓

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