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 12GenericAlias = type(list[int]) 13EllipsisType = type(...) 14def _f(): pass 15FunctionType = type(_f) 16del _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. 42bytes_iterator = type(iter(b'')) 43bytearray_iterator = type(iter(bytearray())) 44#callable_iterator = ??? 45dict_keyiterator = type(iter({}.keys())) 46dict_valueiterator = type(iter({}.values())) 47dict_itemiterator = type(iter({}.items())) 48list_iterator = type(iter([])) 49list_reverseiterator = type(iter(reversed([]))) 50range_iterator = type(iter(range(0))) 51longrange_iterator = type(iter(range(1 << 1000))) 52set_iterator = type(iter(set())) 53str_iterator = type(iter("")) 54tuple_iterator = type(iter(())) 55zip_iterator = type(iter(zip())) 56## views ## 57dict_keys = type({}.keys()) 58dict_values = type({}.values()) 59dict_items = type({}.items()) 60## misc ## 61mappingproxy = type(type.__dict__) 62generator = type((lambda: (yield))()) 63## coroutine ## 64async def _coro(): pass 65_coro = _coro() 66coroutine = type(_coro) 67_coro.close() # Prevent ResourceWarning 68del _coro 69## asynchronous generator ## 70async def _ag(): yield 71_ag = _ag() 72async_generator = type(_ag) 73del _ag 74 75 76### ONE-TRICK PONIES ### 77 78def _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 90class Hashable(metaclass=ABCMeta): 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 105class Awaitable(metaclass=ABCMeta): 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 122class Coroutine(Awaitable): 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 163Coroutine.register(coroutine) 164 165 166class AsyncIterable(metaclass=ABCMeta): 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 183class AsyncIterator(AsyncIterable): 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 202class AsyncGenerator(AsyncIterator): 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 250AsyncGenerator.register(async_generator) 251 252 253class Iterable(metaclass=ABCMeta): 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 271class Iterator(Iterable): 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 290Iterator.register(bytes_iterator) 291Iterator.register(bytearray_iterator) 292#Iterator.register(callable_iterator) 293Iterator.register(dict_keyiterator) 294Iterator.register(dict_valueiterator) 295Iterator.register(dict_itemiterator) 296Iterator.register(list_iterator) 297Iterator.register(list_reverseiterator) 298Iterator.register(range_iterator) 299Iterator.register(longrange_iterator) 300Iterator.register(set_iterator) 301Iterator.register(str_iterator) 302Iterator.register(tuple_iterator) 303Iterator.register(zip_iterator) 304 305 306class Reversible(Iterable): 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 322class Generator(Iterator): 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 370Generator.register(generator) 371 372 373class Sized(metaclass=ABCMeta): 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 388class Container(metaclass=ABCMeta): 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 405class Collection(Sized, Iterable, Container): 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 416class _CallableGenericAlias(GenericAlias): 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, 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 @property 441 def __parameters__(self): 442 params = [] 443 for arg in self.__args__: 444 # Looks like a genericalias 445 if hasattr(arg, "__parameters__") and isinstance(arg.__parameters__, tuple): 446 params.extend(arg.__parameters__) 447 else: 448 if _is_typevarlike(arg): 449 params.append(arg) 450 return tuple(dict.fromkeys(params)) 451 452 def __repr__(self): 453 if len(self.__args__) == 2 and _is_param_expr(self.__args__[0]): 454 return super().__repr__() 455 return (f'collections.abc.Callable' 456 f'[[{", ".join([_type_repr(a) for a in self.__args__[:-1]])}], ' 457 f'{_type_repr(self.__args__[-1])}]') 458 459 def __reduce__(self): 460 args = self.__args__ 461 if not (len(args) == 2 and _is_param_expr(args[0])): 462 args = list(args[:-1]), args[-1] 463 return _CallableGenericAlias, (Callable, args) 464 465 def __getitem__(self, item): 466 # Called during TypeVar substitution, returns the custom subclass 467 # rather than the default types.GenericAlias object. Most of the 468 # code is copied from typing's _GenericAlias and the builtin 469 # types.GenericAlias. 470 471 # A special case in PEP 612 where if X = Callable[P, int], 472 # then X[int, str] == X[[int, str]]. 473 param_len = len(self.__parameters__) 474 if param_len == 0: 475 raise TypeError(f'{self} is not a generic class') 476 if not isinstance(item, tuple): 477 item = (item,) 478 if (param_len == 1 and _is_param_expr(self.__parameters__[0]) 479 and item and not _is_param_expr(item[0])): 480 item = (list(item),) 481 item_len = len(item) 482 if item_len != param_len: 483 raise TypeError(f'Too {"many" if item_len > param_len else "few"}' 484 f' arguments for {self};' 485 f' actual {item_len}, expected {param_len}') 486 subst = dict(zip(self.__parameters__, item)) 487 new_args = [] 488 for arg in self.__args__: 489 if _is_typevarlike(arg): 490 if _is_param_expr(arg): 491 arg = subst[arg] 492 if not _is_param_expr(arg): 493 raise TypeError(f"Expected a list of types, an ellipsis, " 494 f"ParamSpec, or Concatenate. Got {arg}") 495 else: 496 arg = subst[arg] 497 # Looks like a GenericAlias 498 elif hasattr(arg, '__parameters__') and isinstance(arg.__parameters__, tuple): 499 subparams = arg.__parameters__ 500 if subparams: 501 subargs = tuple(subst[x] for x in subparams) 502 arg = arg[subargs] 503 new_args.append(arg) 504 505 # args[0] occurs due to things like Z[[int, str, bool]] from PEP 612 506 if not isinstance(new_args[0], list): 507 t_result = new_args[-1] 508 t_args = new_args[:-1] 509 new_args = (t_args, t_result) 510 return _CallableGenericAlias(Callable, tuple(new_args)) 511 512 513def _is_typevarlike(arg): 514 obj = type(arg) 515 # looks like a TypeVar/ParamSpec 516 return (obj.__module__ == 'typing' 517 and obj.__name__ in {'ParamSpec', 'TypeVar'}) 518 519def _is_param_expr(obj): 520 """Checks if obj matches either a list of types, ``...``, ``ParamSpec`` or 521 ``_ConcatenateGenericAlias`` from typing.py 522 """ 523 if obj is Ellipsis: 524 return True 525 if isinstance(obj, list): 526 return True 527 obj = type(obj) 528 names = ('ParamSpec', '_ConcatenateGenericAlias') 529 return obj.__module__ == 'typing' and any(obj.__name__ == name for name in names) 530 531def _type_repr(obj): 532 """Return the repr() of an object, special-casing types (internal helper). 533 534 Copied from :mod:`typing` since collections.abc 535 shouldn't depend on that module. 536 """ 537 if isinstance(obj, GenericAlias): 538 return repr(obj) 539 if isinstance(obj, type): 540 if obj.__module__ == 'builtins': 541 return obj.__qualname__ 542 return f'{obj.__module__}.{obj.__qualname__}' 543 if obj is Ellipsis: 544 return '...' 545 if isinstance(obj, FunctionType): 546 return obj.__name__ 547 return repr(obj) 548 549 550class Callable(metaclass=ABCMeta): 551 552 __slots__ = () 553 554 @abstractmethod 555 def __call__(self, *args, **kwds): 556 return False 557 558 @classmethod 559 def __subclasshook__(cls, C): 560 if cls is Callable: 561 return _check_methods(C, "__call__") 562 return NotImplemented 563 564 __class_getitem__ = classmethod(_CallableGenericAlias) 565 566 567### SETS ### 568 569 570class Set(Collection): 571 """A set is a finite, iterable container. 572 573 This class provides concrete generic implementations of all 574 methods except for __contains__, __iter__ and __len__. 575 576 To override the comparisons (presumably for speed, as the 577 semantics are fixed), redefine __le__ and __ge__, 578 then the other operations will automatically follow suit. 579 """ 580 581 __slots__ = () 582 583 def __le__(self, other): 584 if not isinstance(other, Set): 585 return NotImplemented 586 if len(self) > len(other): 587 return False 588 for elem in self: 589 if elem not in other: 590 return False 591 return True 592 593 def __lt__(self, other): 594 if not isinstance(other, Set): 595 return NotImplemented 596 return len(self) < len(other) and self.__le__(other) 597 598 def __gt__(self, other): 599 if not isinstance(other, Set): 600 return NotImplemented 601 return len(self) > len(other) and self.__ge__(other) 602 603 def __ge__(self, other): 604 if not isinstance(other, Set): 605 return NotImplemented 606 if len(self) < len(other): 607 return False 608 for elem in other: 609 if elem not in self: 610 return False 611 return True 612 613 def __eq__(self, other): 614 if not isinstance(other, Set): 615 return NotImplemented 616 return len(self) == len(other) and self.__le__(other) 617 618 @classmethod 619 def _from_iterable(cls, it): 620 '''Construct an instance of the class from any iterable input. 621 622 Must override this method if the class constructor signature 623 does not accept an iterable for an input. 624 ''' 625 return cls(it) 626 627 def __and__(self, other): 628 if not isinstance(other, Iterable): 629 return NotImplemented 630 return self._from_iterable(value for value in other if value in self) 631 632 __rand__ = __and__ 633 634 def isdisjoint(self, other): 635 'Return True if two sets have a null intersection.' 636 for value in other: 637 if value in self: 638 return False 639 return True 640 641 def __or__(self, other): 642 if not isinstance(other, Iterable): 643 return NotImplemented 644 chain = (e for s in (self, other) for e in s) 645 return self._from_iterable(chain) 646 647 __ror__ = __or__ 648 649 def __sub__(self, other): 650 if not isinstance(other, Set): 651 if not isinstance(other, Iterable): 652 return NotImplemented 653 other = self._from_iterable(other) 654 return self._from_iterable(value for value in self 655 if value not in other) 656 657 def __rsub__(self, other): 658 if not isinstance(other, Set): 659 if not isinstance(other, Iterable): 660 return NotImplemented 661 other = self._from_iterable(other) 662 return self._from_iterable(value for value in other 663 if value not in self) 664 665 def __xor__(self, other): 666 if not isinstance(other, Set): 667 if not isinstance(other, Iterable): 668 return NotImplemented 669 other = self._from_iterable(other) 670 return (self - other) | (other - self) 671 672 __rxor__ = __xor__ 673 674 def _hash(self): 675 """Compute the hash value of a set. 676 677 Note that we don't define __hash__: not all sets are hashable. 678 But if you define a hashable set type, its __hash__ should 679 call this function. 680 681 This must be compatible __eq__. 682 683 All sets ought to compare equal if they contain the same 684 elements, regardless of how they are implemented, and 685 regardless of the order of the elements; so there's not much 686 freedom for __eq__ or __hash__. We match the algorithm used 687 by the built-in frozenset type. 688 """ 689 MAX = sys.maxsize 690 MASK = 2 * MAX + 1 691 n = len(self) 692 h = 1927868237 * (n + 1) 693 h &= MASK 694 for x in self: 695 hx = hash(x) 696 h ^= (hx ^ (hx << 16) ^ 89869747) * 3644798167 697 h &= MASK 698 h ^= (h >> 11) ^ (h >> 25) 699 h = h * 69069 + 907133923 700 h &= MASK 701 if h > MAX: 702 h -= MASK + 1 703 if h == -1: 704 h = 590923713 705 return h 706 707 708Set.register(frozenset) 709 710 711class MutableSet(Set): 712 """A mutable set is a finite, iterable container. 713 714 This class provides concrete generic implementations of all 715 methods except for __contains__, __iter__, __len__, 716 add(), and discard(). 717 718 To override the comparisons (presumably for speed, as the 719 semantics are fixed), all you have to do is redefine __le__ and 720 then the other operations will automatically follow suit. 721 """ 722 723 __slots__ = () 724 725 @abstractmethod 726 def add(self, value): 727 """Add an element.""" 728 raise NotImplementedError 729 730 @abstractmethod 731 def discard(self, value): 732 """Remove an element. Do not raise an exception if absent.""" 733 raise NotImplementedError 734 735 def remove(self, value): 736 """Remove an element. If not a member, raise a KeyError.""" 737 if value not in self: 738 raise KeyError(value) 739 self.discard(value) 740 741 def pop(self): 742 """Return the popped value. Raise KeyError if empty.""" 743 it = iter(self) 744 try: 745 value = next(it) 746 except StopIteration: 747 raise KeyError from None 748 self.discard(value) 749 return value 750 751 def clear(self): 752 """This is slow (creates N new iterators!) but effective.""" 753 try: 754 while True: 755 self.pop() 756 except KeyError: 757 pass 758 759 def __ior__(self, it): 760 for value in it: 761 self.add(value) 762 return self 763 764 def __iand__(self, it): 765 for value in (self - it): 766 self.discard(value) 767 return self 768 769 def __ixor__(self, it): 770 if it is self: 771 self.clear() 772 else: 773 if not isinstance(it, Set): 774 it = self._from_iterable(it) 775 for value in it: 776 if value in self: 777 self.discard(value) 778 else: 779 self.add(value) 780 return self 781 782 def __isub__(self, it): 783 if it is self: 784 self.clear() 785 else: 786 for value in it: 787 self.discard(value) 788 return self 789 790 791MutableSet.register(set) 792 793 794### MAPPINGS ### 795 796class Mapping(Collection): 797 """A Mapping is a generic container for associating key/value 798 pairs. 799 800 This class provides concrete generic implementations of all 801 methods except for __getitem__, __iter__, and __len__. 802 """ 803 804 __slots__ = () 805 806 # Tell ABCMeta.__new__ that this class should have TPFLAGS_MAPPING set. 807 __abc_tpflags__ = 1 << 6 # Py_TPFLAGS_MAPPING 808 809 @abstractmethod 810 def __getitem__(self, key): 811 raise KeyError 812 813 def get(self, key, default=None): 814 'D.get(k[,d]) -> D[k] if k in D, else d. d defaults to None.' 815 try: 816 return self[key] 817 except KeyError: 818 return default 819 820 def __contains__(self, key): 821 try: 822 self[key] 823 except KeyError: 824 return False 825 else: 826 return True 827 828 def keys(self): 829 "D.keys() -> a set-like object providing a view on D's keys" 830 return KeysView(self) 831 832 def items(self): 833 "D.items() -> a set-like object providing a view on D's items" 834 return ItemsView(self) 835 836 def values(self): 837 "D.values() -> an object providing a view on D's values" 838 return ValuesView(self) 839 840 def __eq__(self, other): 841 if not isinstance(other, Mapping): 842 return NotImplemented 843 return dict(self.items()) == dict(other.items()) 844 845 __reversed__ = None 846 847Mapping.register(mappingproxy) 848 849 850class MappingView(Sized): 851 852 __slots__ = '_mapping', 853 854 def __init__(self, mapping): 855 self._mapping = mapping 856 857 def __len__(self): 858 return len(self._mapping) 859 860 def __repr__(self): 861 return '{0.__class__.__name__}({0._mapping!r})'.format(self) 862 863 __class_getitem__ = classmethod(GenericAlias) 864 865 866class KeysView(MappingView, Set): 867 868 __slots__ = () 869 870 @classmethod 871 def _from_iterable(self, it): 872 return set(it) 873 874 def __contains__(self, key): 875 return key in self._mapping 876 877 def __iter__(self): 878 yield from self._mapping 879 880 881KeysView.register(dict_keys) 882 883 884class ItemsView(MappingView, Set): 885 886 __slots__ = () 887 888 @classmethod 889 def _from_iterable(self, it): 890 return set(it) 891 892 def __contains__(self, item): 893 key, value = item 894 try: 895 v = self._mapping[key] 896 except KeyError: 897 return False 898 else: 899 return v is value or v == value 900 901 def __iter__(self): 902 for key in self._mapping: 903 yield (key, self._mapping[key]) 904 905 906ItemsView.register(dict_items) 907 908 909class ValuesView(MappingView, Collection): 910 911 __slots__ = () 912 913 def __contains__(self, value): 914 for key in self._mapping: 915 v = self._mapping[key] 916 if v is value or v == value: 917 return True 918 return False 919 920 def __iter__(self): 921 for key in self._mapping: 922 yield self._mapping[key] 923 924 925ValuesView.register(dict_values) 926 927 928class MutableMapping(Mapping): 929 """A MutableMapping is a generic container for associating 930 key/value pairs. 931 932 This class provides concrete generic implementations of all 933 methods except for __getitem__, __setitem__, __delitem__, 934 __iter__, and __len__. 935 """ 936 937 __slots__ = () 938 939 @abstractmethod 940 def __setitem__(self, key, value): 941 raise KeyError 942 943 @abstractmethod 944 def __delitem__(self, key): 945 raise KeyError 946 947 __marker = object() 948 949 def pop(self, key, default=__marker): 950 '''D.pop(k[,d]) -> v, remove specified key and return the corresponding value. 951 If key is not found, d is returned if given, otherwise KeyError is raised. 952 ''' 953 try: 954 value = self[key] 955 except KeyError: 956 if default is self.__marker: 957 raise 958 return default 959 else: 960 del self[key] 961 return value 962 963 def popitem(self): 964 '''D.popitem() -> (k, v), remove and return some (key, value) pair 965 as a 2-tuple; but raise KeyError if D is empty. 966 ''' 967 try: 968 key = next(iter(self)) 969 except StopIteration: 970 raise KeyError from None 971 value = self[key] 972 del self[key] 973 return key, value 974 975 def clear(self): 976 'D.clear() -> None. Remove all items from D.' 977 try: 978 while True: 979 self.popitem() 980 except KeyError: 981 pass 982 983 def update(self, other=(), /, **kwds): 984 ''' D.update([E, ]**F) -> None. Update D from mapping/iterable E and F. 985 If E present and has a .keys() method, does: for k in E: D[k] = E[k] 986 If E present and lacks .keys() method, does: for (k, v) in E: D[k] = v 987 In either case, this is followed by: for k, v in F.items(): D[k] = v 988 ''' 989 if isinstance(other, Mapping): 990 for key in other: 991 self[key] = other[key] 992 elif hasattr(other, "keys"): 993 for key in other.keys(): 994 self[key] = other[key] 995 else: 996 for key, value in other: 997 self[key] = value 998 for key, value in kwds.items(): 999 self[key] = value 1000 1001 def setdefault(self, key, default=None): 1002 'D.setdefault(k[,d]) -> D.get(k,d), also set D[k]=d if k not in D' 1003 try: 1004 return self[key] 1005 except KeyError: 1006 self[key] = default 1007 return default 1008 1009 1010MutableMapping.register(dict) 1011 1012 1013### SEQUENCES ### 1014 1015class Sequence(Reversible, Collection): 1016 """All the operations on a read-only sequence. 1017 1018 Concrete subclasses must override __new__ or __init__, 1019 __getitem__, and __len__. 1020 """ 1021 1022 __slots__ = () 1023 1024 # Tell ABCMeta.__new__ that this class should have TPFLAGS_SEQUENCE set. 1025 __abc_tpflags__ = 1 << 5 # Py_TPFLAGS_SEQUENCE 1026 1027 @abstractmethod 1028 def __getitem__(self, index): 1029 raise IndexError 1030 1031 def __iter__(self): 1032 i = 0 1033 try: 1034 while True: 1035 v = self[i] 1036 yield v 1037 i += 1 1038 except IndexError: 1039 return 1040 1041 def __contains__(self, value): 1042 for v in self: 1043 if v is value or v == value: 1044 return True 1045 return False 1046 1047 def __reversed__(self): 1048 for i in reversed(range(len(self))): 1049 yield self[i] 1050 1051 def index(self, value, start=0, stop=None): 1052 '''S.index(value, [start, [stop]]) -> integer -- return first index of value. 1053 Raises ValueError if the value is not present. 1054 1055 Supporting start and stop arguments is optional, but 1056 recommended. 1057 ''' 1058 if start is not None and start < 0: 1059 start = max(len(self) + start, 0) 1060 if stop is not None and stop < 0: 1061 stop += len(self) 1062 1063 i = start 1064 while stop is None or i < stop: 1065 try: 1066 v = self[i] 1067 if v is value or v == value: 1068 return i 1069 except IndexError: 1070 break 1071 i += 1 1072 raise ValueError 1073 1074 def count(self, value): 1075 'S.count(value) -> integer -- return number of occurrences of value' 1076 return sum(1 for v in self if v is value or v == value) 1077 1078Sequence.register(tuple) 1079Sequence.register(str) 1080Sequence.register(range) 1081Sequence.register(memoryview) 1082 1083 1084class ByteString(Sequence): 1085 """This unifies bytes and bytearray. 1086 1087 XXX Should add all their methods. 1088 """ 1089 1090 __slots__ = () 1091 1092ByteString.register(bytes) 1093ByteString.register(bytearray) 1094 1095 1096class MutableSequence(Sequence): 1097 """All the operations on a read-write sequence. 1098 1099 Concrete subclasses must provide __new__ or __init__, 1100 __getitem__, __setitem__, __delitem__, __len__, and insert(). 1101 """ 1102 1103 __slots__ = () 1104 1105 @abstractmethod 1106 def __setitem__(self, index, value): 1107 raise IndexError 1108 1109 @abstractmethod 1110 def __delitem__(self, index): 1111 raise IndexError 1112 1113 @abstractmethod 1114 def insert(self, index, value): 1115 'S.insert(index, value) -- insert value before index' 1116 raise IndexError 1117 1118 def append(self, value): 1119 'S.append(value) -- append value to the end of the sequence' 1120 self.insert(len(self), value) 1121 1122 def clear(self): 1123 'S.clear() -> None -- remove all items from S' 1124 try: 1125 while True: 1126 self.pop() 1127 except IndexError: 1128 pass 1129 1130 def reverse(self): 1131 'S.reverse() -- reverse *IN PLACE*' 1132 n = len(self) 1133 for i in range(n//2): 1134 self[i], self[n-i-1] = self[n-i-1], self[i] 1135 1136 def extend(self, values): 1137 'S.extend(iterable) -- extend sequence by appending elements from the iterable' 1138 if values is self: 1139 values = list(values) 1140 for v in values: 1141 self.append(v) 1142 1143 def pop(self, index=-1): 1144 '''S.pop([index]) -> item -- remove and return item at index (default last). 1145 Raise IndexError if list is empty or index is out of range. 1146 ''' 1147 v = self[index] 1148 del self[index] 1149 return v 1150 1151 def remove(self, value): 1152 '''S.remove(value) -- remove first occurrence of value. 1153 Raise ValueError if the value is not present. 1154 ''' 1155 del self[self.index(value)] 1156 1157 def __iadd__(self, values): 1158 self.extend(values) 1159 return self 1160 1161 1162MutableSequence.register(list) 1163MutableSequence.register(bytearray) # Multiply inheriting, see ByteString 1164