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