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