_collections_abc.py revision 584e8aedc3d66721efcdcbd1a43d4c5b7476427b 
1# Copyright 2007 Google, Inc. All Rights Reserved.
2# Licensed to PSF under a Contributor Agreement.
3
4"""Abstract Base Classes (ABCs) for collections, according to PEP 3119.
5
6Unit tests are in test_collections.
7"""
8
9from abc import ABCMeta, abstractmethod
10import sys
11
12__all__ = ["Awaitable", "Coroutine", "AsyncIterable", "AsyncIterator",
13           "Hashable", "Iterable", "Iterator", "Generator", "Reversible",
14           "Sized", "Container", "Callable",
15           "Set", "MutableSet",
16           "Mapping", "MutableMapping",
17           "MappingView", "KeysView", "ItemsView", "ValuesView",
18           "Sequence", "MutableSequence",
19           "ByteString",
20           ]
21
22# This module has been renamed from collections.abc to _collections_abc to
23# speed up interpreter startup. Some of the types such as MutableMapping are
24# required early but collections module imports a lot of other modules.
25# See issue #19218
26__name__ = "collections.abc"
27
28# Private list of types that we want to register with the various ABCs
29# so that they will pass tests like:
30#       it = iter(somebytearray)
31#       assert isinstance(it, Iterable)
32# Note:  in other implementations, these types many not be distinct
33# and they make have their own implementation specific types that
34# are not included on this list.
35bytes_iterator = type(iter(b''))
36bytearray_iterator = type(iter(bytearray()))
37#callable_iterator = ???
38dict_keyiterator = type(iter({}.keys()))
39dict_valueiterator = type(iter({}.values()))
40dict_itemiterator = type(iter({}.items()))
41list_iterator = type(iter([]))
42list_reverseiterator = type(iter(reversed([])))
43range_iterator = type(iter(range(0)))
44set_iterator = type(iter(set()))
45str_iterator = type(iter(""))
46tuple_iterator = type(iter(()))
47zip_iterator = type(iter(zip()))
48## views ##
49dict_keys = type({}.keys())
50dict_values = type({}.values())
51dict_items = type({}.items())
52## misc ##
53mappingproxy = type(type.__dict__)
54generator = type((lambda: (yield))())
55## coroutine ##
56async def _coro(): pass
57_coro = _coro()
58coroutine = type(_coro)
59_coro.close()  # Prevent ResourceWarning
60del _coro
61
62
63### ONE-TRICK PONIES ###
64
65class Hashable(metaclass=ABCMeta):
66
67    __slots__ = ()
68
69    @abstractmethod
70    def __hash__(self):
71        return 0
72
73    @classmethod
74    def __subclasshook__(cls, C):
75        if cls is Hashable:
76            for B in C.__mro__:
77                if "__hash__" in B.__dict__:
78                    if B.__dict__["__hash__"]:
79                        return True
80                    break
81        return NotImplemented
82
83
84class Awaitable(metaclass=ABCMeta):
85
86    __slots__ = ()
87
88    @abstractmethod
89    def __await__(self):
90        yield
91
92    @classmethod
93    def __subclasshook__(cls, C):
94        if cls is Awaitable:
95            for B in C.__mro__:
96                if "__await__" in B.__dict__:
97                    if B.__dict__["__await__"]:
98                        return True
99                    break
100        return NotImplemented
101
102
103class Coroutine(Awaitable):
104
105    __slots__ = ()
106
107    @abstractmethod
108    def send(self, value):
109        """Send a value into the coroutine.
110        Return next yielded value or raise StopIteration.
111        """
112        raise StopIteration
113
114    @abstractmethod
115    def throw(self, typ, val=None, tb=None):
116        """Raise an exception in the coroutine.
117        Return next yielded value or raise StopIteration.
118        """
119        if val is None:
120            if tb is None:
121                raise typ
122            val = typ()
123        if tb is not None:
124            val = val.with_traceback(tb)
125        raise val
126
127    def close(self):
128        """Raise GeneratorExit inside coroutine.
129        """
130        try:
131            self.throw(GeneratorExit)
132        except (GeneratorExit, StopIteration):
133            pass
134        else:
135            raise RuntimeError("coroutine ignored GeneratorExit")
136
137    @classmethod
138    def __subclasshook__(cls, C):
139        if cls is Coroutine:
140            mro = C.__mro__
141            for method in ('__await__', 'send', 'throw', 'close'):
142                for base in mro:
143                    if method in base.__dict__:
144                        break
145                else:
146                    return NotImplemented
147            return True
148        return NotImplemented
149
150
151Coroutine.register(coroutine)
152
153
154class AsyncIterable(metaclass=ABCMeta):
155
156    __slots__ = ()
157
158    @abstractmethod
159    async def __aiter__(self):
160        return AsyncIterator()
161
162    @classmethod
163    def __subclasshook__(cls, C):
164        if cls is AsyncIterable:
165            if any("__aiter__" in B.__dict__ for B in C.__mro__):
166                return True
167        return NotImplemented
168
169
170class AsyncIterator(AsyncIterable):
171
172    __slots__ = ()
173
174    @abstractmethod
175    async def __anext__(self):
176        """Return the next item or raise StopAsyncIteration when exhausted."""
177        raise StopAsyncIteration
178
179    async def __aiter__(self):
180        return self
181
182    @classmethod
183    def __subclasshook__(cls, C):
184        if cls is AsyncIterator:
185            if (any("__anext__" in B.__dict__ for B in C.__mro__) and
186                any("__aiter__" in B.__dict__ for B in C.__mro__)):
187                return True
188        return NotImplemented
189
190
191class Iterable(metaclass=ABCMeta):
192
193    __slots__ = ()
194
195    @abstractmethod
196    def __iter__(self):
197        while False:
198            yield None
199
200    @classmethod
201    def __subclasshook__(cls, C):
202        if cls is Iterable:
203            if any("__iter__" in B.__dict__ for B in C.__mro__):
204                return True
205        return NotImplemented
206
207
208class Iterator(Iterable):
209
210    __slots__ = ()
211
212    @abstractmethod
213    def __next__(self):
214        'Return the next item from the iterator. When exhausted, raise StopIteration'
215        raise StopIteration
216
217    def __iter__(self):
218        return self
219
220    @classmethod
221    def __subclasshook__(cls, C):
222        if cls is Iterator:
223            if (any("__next__" in B.__dict__ for B in C.__mro__) and
224                any("__iter__" in B.__dict__ for B in C.__mro__)):
225                return True
226        return NotImplemented
227
228Iterator.register(bytes_iterator)
229Iterator.register(bytearray_iterator)
230#Iterator.register(callable_iterator)
231Iterator.register(dict_keyiterator)
232Iterator.register(dict_valueiterator)
233Iterator.register(dict_itemiterator)
234Iterator.register(list_iterator)
235Iterator.register(list_reverseiterator)
236Iterator.register(range_iterator)
237Iterator.register(set_iterator)
238Iterator.register(str_iterator)
239Iterator.register(tuple_iterator)
240Iterator.register(zip_iterator)
241
242
243class Reversible(Iterable):
244
245    __slots__ = ()
246
247    @abstractmethod
248    def __reversed__(self):
249        return NotImplemented
250
251    @classmethod
252    def __subclasshook__(cls, C):
253        if cls is Reversible:
254            for B in C.__mro__:
255                if "__reversed__" in B.__dict__:
256                    if B.__dict__["__reversed__"] is not None:
257                        return True
258                    break
259        return NotImplemented
260
261
262class Generator(Iterator):
263
264    __slots__ = ()
265
266    def __next__(self):
267        """Return the next item from the generator.
268        When exhausted, raise StopIteration.
269        """
270        return self.send(None)
271
272    @abstractmethod
273    def send(self, value):
274        """Send a value into the generator.
275        Return next yielded value or raise StopIteration.
276        """
277        raise StopIteration
278
279    @abstractmethod
280    def throw(self, typ, val=None, tb=None):
281        """Raise an exception in the generator.
282        Return next yielded value or raise StopIteration.
283        """
284        if val is None:
285            if tb is None:
286                raise typ
287            val = typ()
288        if tb is not None:
289            val = val.with_traceback(tb)
290        raise val
291
292    def close(self):
293        """Raise GeneratorExit inside generator.
294        """
295        try:
296            self.throw(GeneratorExit)
297        except (GeneratorExit, StopIteration):
298            pass
299        else:
300            raise RuntimeError("generator ignored GeneratorExit")
301
302    @classmethod
303    def __subclasshook__(cls, C):
304        if cls is Generator:
305            mro = C.__mro__
306            for method in ('__iter__', '__next__', 'send', 'throw', 'close'):
307                for base in mro:
308                    if method in base.__dict__:
309                        break
310                else:
311                    return NotImplemented
312            return True
313        return NotImplemented
314
315
316Generator.register(generator)
317
318
319class Sized(metaclass=ABCMeta):
320
321    __slots__ = ()
322
323    @abstractmethod
324    def __len__(self):
325        return 0
326
327    @classmethod
328    def __subclasshook__(cls, C):
329        if cls is Sized:
330            if any("__len__" in B.__dict__ for B in C.__mro__):
331                return True
332        return NotImplemented
333
334
335class Container(metaclass=ABCMeta):
336
337    __slots__ = ()
338
339    @abstractmethod
340    def __contains__(self, x):
341        return False
342
343    @classmethod
344    def __subclasshook__(cls, C):
345        if cls is Container:
346            if any("__contains__" in B.__dict__ for B in C.__mro__):
347                return True
348        return NotImplemented
349
350
351class Callable(metaclass=ABCMeta):
352
353    __slots__ = ()
354
355    @abstractmethod
356    def __call__(self, *args, **kwds):
357        return False
358
359    @classmethod
360    def __subclasshook__(cls, C):
361        if cls is Callable:
362            if any("__call__" in B.__dict__ for B in C.__mro__):
363                return True
364        return NotImplemented
365
366
367### SETS ###
368
369
370class Set(Sized, Iterable, Container):
371
372    """A set is a finite, iterable container.
373
374    This class provides concrete generic implementations of all
375    methods except for __contains__, __iter__ and __len__.
376
377    To override the comparisons (presumably for speed, as the
378    semantics are fixed), redefine __le__ and __ge__,
379    then the other operations will automatically follow suit.
380    """
381
382    __slots__ = ()
383
384    def __le__(self, other):
385        if not isinstance(other, Set):
386            return NotImplemented
387        if len(self) > len(other):
388            return False
389        for elem in self:
390            if elem not in other:
391                return False
392        return True
393
394    def __lt__(self, other):
395        if not isinstance(other, Set):
396            return NotImplemented
397        return len(self) < len(other) and self.__le__(other)
398
399    def __gt__(self, other):
400        if not isinstance(other, Set):
401            return NotImplemented
402        return len(self) > len(other) and self.__ge__(other)
403
404    def __ge__(self, other):
405        if not isinstance(other, Set):
406            return NotImplemented
407        if len(self) < len(other):
408            return False
409        for elem in other:
410            if elem not in self:
411                return False
412        return True
413
414    def __eq__(self, other):
415        if not isinstance(other, Set):
416            return NotImplemented
417        return len(self) == len(other) and self.__le__(other)
418
419    @classmethod
420    def _from_iterable(cls, it):
421        '''Construct an instance of the class from any iterable input.
422
423        Must override this method if the class constructor signature
424        does not accept an iterable for an input.
425        '''
426        return cls(it)
427
428    def __and__(self, other):
429        if not isinstance(other, Iterable):
430            return NotImplemented
431        return self._from_iterable(value for value in other if value in self)
432
433    __rand__ = __and__
434
435    def isdisjoint(self, other):
436        'Return True if two sets have a null intersection.'
437        for value in other:
438            if value in self:
439                return False
440        return True
441
442    def __or__(self, other):
443        if not isinstance(other, Iterable):
444            return NotImplemented
445        chain = (e for s in (self, other) for e in s)
446        return self._from_iterable(chain)
447
448    __ror__ = __or__
449
450    def __sub__(self, other):
451        if not isinstance(other, Set):
452            if not isinstance(other, Iterable):
453                return NotImplemented
454            other = self._from_iterable(other)
455        return self._from_iterable(value for value in self
456                                   if value not in other)
457
458    def __rsub__(self, other):
459        if not isinstance(other, Set):
460            if not isinstance(other, Iterable):
461                return NotImplemented
462            other = self._from_iterable(other)
463        return self._from_iterable(value for value in other
464                                   if value not in self)
465
466    def __xor__(self, other):
467        if not isinstance(other, Set):
468            if not isinstance(other, Iterable):
469                return NotImplemented
470            other = self._from_iterable(other)
471        return (self - other) | (other - self)
472
473    __rxor__ = __xor__
474
475    def _hash(self):
476        """Compute the hash value of a set.
477
478        Note that we don't define __hash__: not all sets are hashable.
479        But if you define a hashable set type, its __hash__ should
480        call this function.
481
482        This must be compatible __eq__.
483
484        All sets ought to compare equal if they contain the same
485        elements, regardless of how they are implemented, and
486        regardless of the order of the elements; so there's not much
487        freedom for __eq__ or __hash__.  We match the algorithm used
488        by the built-in frozenset type.
489        """
490        MAX = sys.maxsize
491        MASK = 2 * MAX + 1
492        n = len(self)
493        h = 1927868237 * (n + 1)
494        h &= MASK
495        for x in self:
496            hx = hash(x)
497            h ^= (hx ^ (hx << 16) ^ 89869747)  * 3644798167
498            h &= MASK
499        h = h * 69069 + 907133923
500        h &= MASK
501        if h > MAX:
502            h -= MASK + 1
503        if h == -1:
504            h = 590923713
505        return h
506
507Set.register(frozenset)
508
509
510class MutableSet(Set):
511    """A mutable set is a finite, iterable container.
512
513    This class provides concrete generic implementations of all
514    methods except for __contains__, __iter__, __len__,
515    add(), and discard().
516
517    To override the comparisons (presumably for speed, as the
518    semantics are fixed), all you have to do is redefine __le__ and
519    then the other operations will automatically follow suit.
520    """
521
522    __slots__ = ()
523
524    @abstractmethod
525    def add(self, value):
526        """Add an element."""
527        raise NotImplementedError
528
529    @abstractmethod
530    def discard(self, value):
531        """Remove an element.  Do not raise an exception if absent."""
532        raise NotImplementedError
533
534    def remove(self, value):
535        """Remove an element. If not a member, raise a KeyError."""
536        if value not in self:
537            raise KeyError(value)
538        self.discard(value)
539
540    def pop(self):
541        """Return the popped value.  Raise KeyError if empty."""
542        it = iter(self)
543        try:
544            value = next(it)
545        except StopIteration:
546            raise KeyError
547        self.discard(value)
548        return value
549
550    def clear(self):
551        """This is slow (creates N new iterators!) but effective."""
552        try:
553            while True:
554                self.pop()
555        except KeyError:
556            pass
557
558    def __ior__(self, it):
559        for value in it:
560            self.add(value)
561        return self
562
563    def __iand__(self, it):
564        for value in (self - it):
565            self.discard(value)
566        return self
567
568    def __ixor__(self, it):
569        if it is self:
570            self.clear()
571        else:
572            if not isinstance(it, Set):
573                it = self._from_iterable(it)
574            for value in it:
575                if value in self:
576                    self.discard(value)
577                else:
578                    self.add(value)
579        return self
580
581    def __isub__(self, it):
582        if it is self:
583            self.clear()
584        else:
585            for value in it:
586                self.discard(value)
587        return self
588
589MutableSet.register(set)
590
591
592### MAPPINGS ###
593
594
595class Mapping(Sized, Iterable, Container):
596
597    __slots__ = ()
598
599    """A Mapping is a generic container for associating key/value
600    pairs.
601
602    This class provides concrete generic implementations of all
603    methods except for __getitem__, __iter__, and __len__.
604
605    """
606
607    @abstractmethod
608    def __getitem__(self, key):
609        raise KeyError
610
611    def get(self, key, default=None):
612        'D.get(k[,d]) -> D[k] if k in D, else d.  d defaults to None.'
613        try:
614            return self[key]
615        except KeyError:
616            return default
617
618    def __contains__(self, key):
619        try:
620            self[key]
621        except KeyError:
622            return False
623        else:
624            return True
625
626    def keys(self):
627        "D.keys() -> a set-like object providing a view on D's keys"
628        return KeysView(self)
629
630    def items(self):
631        "D.items() -> a set-like object providing a view on D's items"
632        return ItemsView(self)
633
634    def values(self):
635        "D.values() -> an object providing a view on D's values"
636        return ValuesView(self)
637
638    def __eq__(self, other):
639        if not isinstance(other, Mapping):
640            return NotImplemented
641        return dict(self.items()) == dict(other.items())
642
643Mapping.register(mappingproxy)
644
645
646class MappingView(Sized):
647
648    __slots__ = '_mapping',
649
650    def __init__(self, mapping):
651        self._mapping = mapping
652
653    def __len__(self):
654        return len(self._mapping)
655
656    def __repr__(self):
657        return '{0.__class__.__name__}({0._mapping!r})'.format(self)
658
659
660class KeysView(MappingView, Set):
661
662    __slots__ = ()
663
664    @classmethod
665    def _from_iterable(self, it):
666        return set(it)
667
668    def __contains__(self, key):
669        return key in self._mapping
670
671    def __iter__(self):
672        yield from self._mapping
673
674KeysView.register(dict_keys)
675
676
677class ItemsView(MappingView, Set):
678
679    __slots__ = ()
680
681    @classmethod
682    def _from_iterable(self, it):
683        return set(it)
684
685    def __contains__(self, item):
686        key, value = item
687        try:
688            v = self._mapping[key]
689        except KeyError:
690            return False
691        else:
692            return v is value or v == value
693
694    def __iter__(self):
695        for key in self._mapping:
696            yield (key, self._mapping[key])
697
698ItemsView.register(dict_items)
699
700
701class ValuesView(MappingView):
702
703    __slots__ = ()
704
705    def __contains__(self, value):
706        for key in self._mapping:
707            v = self._mapping[key]
708            if v is value or v == value:
709                return True
710        return False
711
712    def __iter__(self):
713        for key in self._mapping:
714            yield self._mapping[key]
715
716ValuesView.register(dict_values)
717
718
719class MutableMapping(Mapping):
720
721    __slots__ = ()
722
723    """A MutableMapping is a generic container for associating
724    key/value pairs.
725
726    This class provides concrete generic implementations of all
727    methods except for __getitem__, __setitem__, __delitem__,
728    __iter__, and __len__.
729
730    """
731
732    @abstractmethod
733    def __setitem__(self, key, value):
734        raise KeyError
735
736    @abstractmethod
737    def __delitem__(self, key):
738        raise KeyError
739
740    __marker = object()
741
742    def pop(self, key, default=__marker):
743        '''D.pop(k[,d]) -> v, remove specified key and return the corresponding value.
744          If key is not found, d is returned if given, otherwise KeyError is raised.
745        '''
746        try:
747            value = self[key]
748        except KeyError:
749            if default is self.__marker:
750                raise
751            return default
752        else:
753            del self[key]
754            return value
755
756    def popitem(self):
757        '''D.popitem() -> (k, v), remove and return some (key, value) pair
758           as a 2-tuple; but raise KeyError if D is empty.
759        '''
760        try:
761            key = next(iter(self))
762        except StopIteration:
763            raise KeyError
764        value = self[key]
765        del self[key]
766        return key, value
767
768    def clear(self):
769        'D.clear() -> None.  Remove all items from D.'
770        try:
771            while True:
772                self.popitem()
773        except KeyError:
774            pass
775
776    def update(*args, **kwds):
777        ''' D.update([E, ]**F) -> None.  Update D from mapping/iterable E and F.
778            If E present and has a .keys() method, does:     for k in E: D[k] = E[k]
779            If E present and lacks .keys() method, does:     for (k, v) in E: D[k] = v
780            In either case, this is followed by: for k, v in F.items(): D[k] = v
781        '''
782        if not args:
783            raise TypeError("descriptor 'update' of 'MutableMapping' object "
784                            "needs an argument")
785        self, *args = args
786        if len(args) > 1:
787            raise TypeError('update expected at most 1 arguments, got %d' %
788                            len(args))
789        if args:
790            other = args[0]
791            if isinstance(other, Mapping):
792                for key in other:
793                    self[key] = other[key]
794            elif hasattr(other, "keys"):
795                for key in other.keys():
796                    self[key] = other[key]
797            else:
798                for key, value in other:
799                    self[key] = value
800        for key, value in kwds.items():
801            self[key] = value
802
803    def setdefault(self, key, default=None):
804        'D.setdefault(k[,d]) -> D.get(k,d), also set D[k]=d if k not in D'
805        try:
806            return self[key]
807        except KeyError:
808            self[key] = default
809        return default
810
811MutableMapping.register(dict)
812
813
814### SEQUENCES ###
815
816
817class Sequence(Sized, Reversible, Container):
818
819    """All the operations on a read-only sequence.
820
821    Concrete subclasses must override __new__ or __init__,
822    __getitem__, and __len__.
823    """
824
825    __slots__ = ()
826
827    @abstractmethod
828    def __getitem__(self, index):
829        raise IndexError
830
831    def __iter__(self):
832        i = 0
833        try:
834            while True:
835                v = self[i]
836                yield v
837                i += 1
838        except IndexError:
839            return
840
841    def __contains__(self, value):
842        for v in self:
843            if v is value or v == value:
844                return True
845        return False
846
847    def __reversed__(self):
848        for i in reversed(range(len(self))):
849            yield self[i]
850
851    def index(self, value, start=0, stop=None):
852        '''S.index(value, [start, [stop]]) -> integer -- return first index of value.
853           Raises ValueError if the value is not present.
854        '''
855        if start is not None and start < 0:
856            start = max(len(self) + start, 0)
857        if stop is not None and stop < 0:
858            stop += len(self)
859
860        i = start
861        while stop is None or i < stop:
862            try:
863                if self[i] == value:
864                    return i
865            except IndexError:
866                break
867            i += 1
868        raise ValueError
869
870    def count(self, value):
871        'S.count(value) -> integer -- return number of occurrences of value'
872        return sum(1 for v in self if v == value)
873
874Sequence.register(tuple)
875Sequence.register(str)
876Sequence.register(range)
877Sequence.register(memoryview)
878
879
880class ByteString(Sequence):
881
882    """This unifies bytes and bytearray.
883
884    XXX Should add all their methods.
885    """
886
887    __slots__ = ()
888
889ByteString.register(bytes)
890ByteString.register(bytearray)
891
892
893class MutableSequence(Sequence):
894
895    __slots__ = ()
896
897    """All the operations on a read-write sequence.
898
899    Concrete subclasses must provide __new__ or __init__,
900    __getitem__, __setitem__, __delitem__, __len__, and insert().
901
902    """
903
904    @abstractmethod
905    def __setitem__(self, index, value):
906        raise IndexError
907
908    @abstractmethod
909    def __delitem__(self, index):
910        raise IndexError
911
912    @abstractmethod
913    def insert(self, index, value):
914        'S.insert(index, value) -- insert value before index'
915        raise IndexError
916
917    def append(self, value):
918        'S.append(value) -- append value to the end of the sequence'
919        self.insert(len(self), value)
920
921    def clear(self):
922        'S.clear() -> None -- remove all items from S'
923        try:
924            while True:
925                self.pop()
926        except IndexError:
927            pass
928
929    def reverse(self):
930        'S.reverse() -- reverse *IN PLACE*'
931        n = len(self)
932        for i in range(n//2):
933            self[i], self[n-i-1] = self[n-i-1], self[i]
934
935    def extend(self, values):
936        'S.extend(iterable) -- extend sequence by appending elements from the iterable'
937        for v in values:
938            self.append(v)
939
940    def pop(self, index=-1):
941        '''S.pop([index]) -> item -- remove and return item at index (default last).
942           Raise IndexError if list is empty or index is out of range.
943        '''
944        v = self[index]
945        del self[index]
946        return v
947
948    def remove(self, value):
949        '''S.remove(value) -- remove first occurrence of value.
950           Raise ValueError if the value is not present.
951        '''
952        del self[self.index(value)]
953
954    def __iadd__(self, values):
955        self.extend(values)
956        return self
957
958MutableSequence.register(list)
959MutableSequence.register(bytearray)  # Multiply inheriting, see ByteString
960