_collections_abc.py revision 153866ea9ab80323d247a9c49d1fdf50e07e7330
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__ = ["Hashable", "Iterable", "Iterator", 13 "Sized", "Container", "Callable", 14 "Set", "MutableSet", 15 "Mapping", "MutableMapping", 16 "MappingView", "KeysView", "ItemsView", "ValuesView", 17 "Sequence", "MutableSequence", 18 "ByteString", 19 ] 20 21# Private list of types that we want to register with the various ABCs 22# so that they will pass tests like: 23# it = iter(somebytearray) 24# assert isinstance(it, Iterable) 25# Note: in other implementations, these types many not be distinct 26# and they make have their own implementation specific types that 27# are not included on this list. 28bytes_iterator = type(iter(b'')) 29bytearray_iterator = type(iter(bytearray())) 30#callable_iterator = ??? 31dict_keyiterator = type(iter({}.keys())) 32dict_valueiterator = type(iter({}.values())) 33dict_itemiterator = type(iter({}.items())) 34list_iterator = type(iter([])) 35list_reverseiterator = type(iter(reversed([]))) 36range_iterator = type(iter(range(0))) 37set_iterator = type(iter(set())) 38str_iterator = type(iter("")) 39tuple_iterator = type(iter(())) 40zip_iterator = type(iter(zip())) 41## views ## 42dict_keys = type({}.keys()) 43dict_values = type({}.values()) 44dict_items = type({}.items()) 45## misc ## 46mappingproxy = type(type.__dict__) 47 48 49### ONE-TRICK PONIES ### 50 51class Hashable(metaclass=ABCMeta): 52 53 __slots__ = () 54 55 @abstractmethod 56 def __hash__(self): 57 return 0 58 59 @classmethod 60 def __subclasshook__(cls, C): 61 if cls is Hashable: 62 for B in C.__mro__: 63 if "__hash__" in B.__dict__: 64 if B.__dict__["__hash__"]: 65 return True 66 break 67 return NotImplemented 68 69 70class Iterable(metaclass=ABCMeta): 71 72 __slots__ = () 73 74 @abstractmethod 75 def __iter__(self): 76 while False: 77 yield None 78 79 @classmethod 80 def __subclasshook__(cls, C): 81 if cls is Iterable: 82 if any("__iter__" in B.__dict__ for B in C.__mro__): 83 return True 84 return NotImplemented 85 86 87class Iterator(Iterable): 88 89 __slots__ = () 90 91 @abstractmethod 92 def __next__(self): 93 'Return the next item from the iterator. When exhausted, raise StopIteration' 94 raise StopIteration 95 96 def __iter__(self): 97 return self 98 99 @classmethod 100 def __subclasshook__(cls, C): 101 if cls is Iterator: 102 if (any("__next__" in B.__dict__ for B in C.__mro__) and 103 any("__iter__" in B.__dict__ for B in C.__mro__)): 104 return True 105 return NotImplemented 106 107Iterator.register(bytes_iterator) 108Iterator.register(bytearray_iterator) 109#Iterator.register(callable_iterator) 110Iterator.register(dict_keyiterator) 111Iterator.register(dict_valueiterator) 112Iterator.register(dict_itemiterator) 113Iterator.register(list_iterator) 114Iterator.register(list_reverseiterator) 115Iterator.register(range_iterator) 116Iterator.register(set_iterator) 117Iterator.register(str_iterator) 118Iterator.register(tuple_iterator) 119Iterator.register(zip_iterator) 120 121class Sized(metaclass=ABCMeta): 122 123 __slots__ = () 124 125 @abstractmethod 126 def __len__(self): 127 return 0 128 129 @classmethod 130 def __subclasshook__(cls, C): 131 if cls is Sized: 132 if any("__len__" in B.__dict__ for B in C.__mro__): 133 return True 134 return NotImplemented 135 136 137class Container(metaclass=ABCMeta): 138 139 __slots__ = () 140 141 @abstractmethod 142 def __contains__(self, x): 143 return False 144 145 @classmethod 146 def __subclasshook__(cls, C): 147 if cls is Container: 148 if any("__contains__" in B.__dict__ for B in C.__mro__): 149 return True 150 return NotImplemented 151 152 153class Callable(metaclass=ABCMeta): 154 155 __slots__ = () 156 157 @abstractmethod 158 def __call__(self, *args, **kwds): 159 return False 160 161 @classmethod 162 def __subclasshook__(cls, C): 163 if cls is Callable: 164 if any("__call__" in B.__dict__ for B in C.__mro__): 165 return True 166 return NotImplemented 167 168 169### SETS ### 170 171 172class Set(Sized, Iterable, Container): 173 174 """A set is a finite, iterable container. 175 176 This class provides concrete generic implementations of all 177 methods except for __contains__, __iter__ and __len__. 178 179 To override the comparisons (presumably for speed, as the 180 semantics are fixed), all you have to do is redefine __le__ and 181 then the other operations will automatically follow suit. 182 """ 183 184 __slots__ = () 185 186 def __le__(self, other): 187 if not isinstance(other, Set): 188 return NotImplemented 189 if len(self) > len(other): 190 return False 191 for elem in self: 192 if elem not in other: 193 return False 194 return True 195 196 def __lt__(self, other): 197 if not isinstance(other, Set): 198 return NotImplemented 199 return len(self) < len(other) and self.__le__(other) 200 201 def __gt__(self, other): 202 if not isinstance(other, Set): 203 return NotImplemented 204 return other.__lt__(self) 205 206 def __ge__(self, other): 207 if not isinstance(other, Set): 208 return NotImplemented 209 return other.__le__(self) 210 211 def __eq__(self, other): 212 if not isinstance(other, Set): 213 return NotImplemented 214 return len(self) == len(other) and self.__le__(other) 215 216 def __ne__(self, other): 217 return not (self == other) 218 219 @classmethod 220 def _from_iterable(cls, it): 221 '''Construct an instance of the class from any iterable input. 222 223 Must override this method if the class constructor signature 224 does not accept an iterable for an input. 225 ''' 226 return cls(it) 227 228 def __and__(self, other): 229 if not isinstance(other, Iterable): 230 return NotImplemented 231 return self._from_iterable(value for value in other if value in self) 232 233 def isdisjoint(self, other): 234 'Return True if two sets have a null intersection.' 235 for value in other: 236 if value in self: 237 return False 238 return True 239 240 def __or__(self, other): 241 if not isinstance(other, Iterable): 242 return NotImplemented 243 chain = (e for s in (self, other) for e in s) 244 return self._from_iterable(chain) 245 246 def __sub__(self, other): 247 if not isinstance(other, Set): 248 if not isinstance(other, Iterable): 249 return NotImplemented 250 other = self._from_iterable(other) 251 return self._from_iterable(value for value in self 252 if value not in other) 253 254 def __xor__(self, other): 255 if not isinstance(other, Set): 256 if not isinstance(other, Iterable): 257 return NotImplemented 258 other = self._from_iterable(other) 259 return (self - other) | (other - self) 260 261 def _hash(self): 262 """Compute the hash value of a set. 263 264 Note that we don't define __hash__: not all sets are hashable. 265 But if you define a hashable set type, its __hash__ should 266 call this function. 267 268 This must be compatible __eq__. 269 270 All sets ought to compare equal if they contain the same 271 elements, regardless of how they are implemented, and 272 regardless of the order of the elements; so there's not much 273 freedom for __eq__ or __hash__. We match the algorithm used 274 by the built-in frozenset type. 275 """ 276 MAX = sys.maxsize 277 MASK = 2 * MAX + 1 278 n = len(self) 279 h = 1927868237 * (n + 1) 280 h &= MASK 281 for x in self: 282 hx = hash(x) 283 h ^= (hx ^ (hx << 16) ^ 89869747) * 3644798167 284 h &= MASK 285 h = h * 69069 + 907133923 286 h &= MASK 287 if h > MAX: 288 h -= MASK + 1 289 if h == -1: 290 h = 590923713 291 return h 292 293Set.register(frozenset) 294 295 296class MutableSet(Set): 297 """A mutable set is a finite, iterable container. 298 299 This class provides concrete generic implementations of all 300 methods except for __contains__, __iter__, __len__, 301 add(), and discard(). 302 303 To override the comparisons (presumably for speed, as the 304 semantics are fixed), all you have to do is redefine __le__ and 305 then the other operations will automatically follow suit. 306 """ 307 308 __slots__ = () 309 310 @abstractmethod 311 def add(self, value): 312 """Add an element.""" 313 raise NotImplementedError 314 315 @abstractmethod 316 def discard(self, value): 317 """Remove an element. Do not raise an exception if absent.""" 318 raise NotImplementedError 319 320 def remove(self, value): 321 """Remove an element. If not a member, raise a KeyError.""" 322 if value not in self: 323 raise KeyError(value) 324 self.discard(value) 325 326 def pop(self): 327 """Return the popped value. Raise KeyError if empty.""" 328 it = iter(self) 329 try: 330 value = next(it) 331 except StopIteration: 332 raise KeyError 333 self.discard(value) 334 return value 335 336 def clear(self): 337 """This is slow (creates N new iterators!) but effective.""" 338 try: 339 while True: 340 self.pop() 341 except KeyError: 342 pass 343 344 def __ior__(self, it): 345 for value in it: 346 self.add(value) 347 return self 348 349 def __iand__(self, it): 350 for value in (self - it): 351 self.discard(value) 352 return self 353 354 def __ixor__(self, it): 355 if it is self: 356 self.clear() 357 else: 358 if not isinstance(it, Set): 359 it = self._from_iterable(it) 360 for value in it: 361 if value in self: 362 self.discard(value) 363 else: 364 self.add(value) 365 return self 366 367 def __isub__(self, it): 368 if it is self: 369 self.clear() 370 else: 371 for value in it: 372 self.discard(value) 373 return self 374 375MutableSet.register(set) 376 377 378### MAPPINGS ### 379 380 381class Mapping(Sized, Iterable, Container): 382 383 __slots__ = () 384 385 """A Mapping is a generic container for associating key/value 386 pairs. 387 388 This class provides concrete generic implementations of all 389 methods except for __getitem__, __iter__, and __len__. 390 391 """ 392 393 @abstractmethod 394 def __getitem__(self, key): 395 raise KeyError 396 397 def get(self, key, default=None): 398 'D.get(k[,d]) -> D[k] if k in D, else d. d defaults to None.' 399 try: 400 return self[key] 401 except KeyError: 402 return default 403 404 def __contains__(self, key): 405 try: 406 self[key] 407 except KeyError: 408 return False 409 else: 410 return True 411 412 def keys(self): 413 "D.keys() -> a set-like object providing a view on D's keys" 414 return KeysView(self) 415 416 def items(self): 417 "D.items() -> a set-like object providing a view on D's items" 418 return ItemsView(self) 419 420 def values(self): 421 "D.values() -> an object providing a view on D's values" 422 return ValuesView(self) 423 424 def __eq__(self, other): 425 if not isinstance(other, Mapping): 426 return NotImplemented 427 return dict(self.items()) == dict(other.items()) 428 429 def __ne__(self, other): 430 return not (self == other) 431 432Mapping.register(mappingproxy) 433 434 435class MappingView(Sized): 436 437 def __init__(self, mapping): 438 self._mapping = mapping 439 440 def __len__(self): 441 return len(self._mapping) 442 443 def __repr__(self): 444 return '{0.__class__.__name__}({0._mapping!r})'.format(self) 445 446 447class KeysView(MappingView, Set): 448 449 @classmethod 450 def _from_iterable(self, it): 451 return set(it) 452 453 def __contains__(self, key): 454 return key in self._mapping 455 456 def __iter__(self): 457 for key in self._mapping: 458 yield key 459 460KeysView.register(dict_keys) 461 462 463class ItemsView(MappingView, Set): 464 465 @classmethod 466 def _from_iterable(self, it): 467 return set(it) 468 469 def __contains__(self, item): 470 key, value = item 471 try: 472 v = self._mapping[key] 473 except KeyError: 474 return False 475 else: 476 return v == value 477 478 def __iter__(self): 479 for key in self._mapping: 480 yield (key, self._mapping[key]) 481 482ItemsView.register(dict_items) 483 484 485class ValuesView(MappingView): 486 487 def __contains__(self, value): 488 for key in self._mapping: 489 if value == self._mapping[key]: 490 return True 491 return False 492 493 def __iter__(self): 494 for key in self._mapping: 495 yield self._mapping[key] 496 497ValuesView.register(dict_values) 498 499 500class MutableMapping(Mapping): 501 502 __slots__ = () 503 504 """A MutableMapping is a generic container for associating 505 key/value pairs. 506 507 This class provides concrete generic implementations of all 508 methods except for __getitem__, __setitem__, __delitem__, 509 __iter__, and __len__. 510 511 """ 512 513 @abstractmethod 514 def __setitem__(self, key, value): 515 raise KeyError 516 517 @abstractmethod 518 def __delitem__(self, key): 519 raise KeyError 520 521 __marker = object() 522 523 def pop(self, key, default=__marker): 524 '''D.pop(k[,d]) -> v, remove specified key and return the corresponding value. 525 If key is not found, d is returned if given, otherwise KeyError is raised. 526 ''' 527 try: 528 value = self[key] 529 except KeyError: 530 if default is self.__marker: 531 raise 532 return default 533 else: 534 del self[key] 535 return value 536 537 def popitem(self): 538 '''D.popitem() -> (k, v), remove and return some (key, value) pair 539 as a 2-tuple; but raise KeyError if D is empty. 540 ''' 541 try: 542 key = next(iter(self)) 543 except StopIteration: 544 raise KeyError 545 value = self[key] 546 del self[key] 547 return key, value 548 549 def clear(self): 550 'D.clear() -> None. Remove all items from D.' 551 try: 552 while True: 553 self.popitem() 554 except KeyError: 555 pass 556 557 def update(*args, **kwds): 558 ''' D.update([E, ]**F) -> None. Update D from mapping/iterable E and F. 559 If E present and has a .keys() method, does: for k in E: D[k] = E[k] 560 If E present and lacks .keys() method, does: for (k, v) in E: D[k] = v 561 In either case, this is followed by: for k, v in F.items(): D[k] = v 562 ''' 563 if len(args) > 2: 564 raise TypeError("update() takes at most 2 positional " 565 "arguments ({} given)".format(len(args))) 566 elif not args: 567 raise TypeError("update() takes at least 1 argument (0 given)") 568 self = args[0] 569 other = args[1] if len(args) >= 2 else () 570 571 if isinstance(other, Mapping): 572 for key in other: 573 self[key] = other[key] 574 elif hasattr(other, "keys"): 575 for key in other.keys(): 576 self[key] = other[key] 577 else: 578 for key, value in other: 579 self[key] = value 580 for key, value in kwds.items(): 581 self[key] = value 582 583 def setdefault(self, key, default=None): 584 'D.setdefault(k[,d]) -> D.get(k,d), also set D[k]=d if k not in D' 585 try: 586 return self[key] 587 except KeyError: 588 self[key] = default 589 return default 590 591MutableMapping.register(dict) 592 593 594### SEQUENCES ### 595 596 597class Sequence(Sized, Iterable, Container): 598 599 """All the operations on a read-only sequence. 600 601 Concrete subclasses must override __new__ or __init__, 602 __getitem__, and __len__. 603 """ 604 605 __slots__ = () 606 607 @abstractmethod 608 def __getitem__(self, index): 609 raise IndexError 610 611 def __iter__(self): 612 i = 0 613 try: 614 while True: 615 v = self[i] 616 yield v 617 i += 1 618 except IndexError: 619 return 620 621 def __contains__(self, value): 622 for v in self: 623 if v == value: 624 return True 625 return False 626 627 def __reversed__(self): 628 for i in reversed(range(len(self))): 629 yield self[i] 630 631 def index(self, value): 632 '''S.index(value) -> integer -- return first index of value. 633 Raises ValueError if the value is not present. 634 ''' 635 for i, v in enumerate(self): 636 if v == value: 637 return i 638 raise ValueError 639 640 def count(self, value): 641 'S.count(value) -> integer -- return number of occurrences of value' 642 return sum(1 for v in self if v == value) 643 644Sequence.register(tuple) 645Sequence.register(str) 646Sequence.register(range) 647 648 649class ByteString(Sequence): 650 651 """This unifies bytes and bytearray. 652 653 XXX Should add all their methods. 654 """ 655 656 __slots__ = () 657 658ByteString.register(bytes) 659ByteString.register(bytearray) 660 661 662class MutableSequence(Sequence): 663 664 __slots__ = () 665 666 """All the operations on a read-only sequence. 667 668 Concrete subclasses must provide __new__ or __init__, 669 __getitem__, __setitem__, __delitem__, __len__, and insert(). 670 671 """ 672 673 @abstractmethod 674 def __setitem__(self, index, value): 675 raise IndexError 676 677 @abstractmethod 678 def __delitem__(self, index): 679 raise IndexError 680 681 @abstractmethod 682 def insert(self, index, value): 683 'S.insert(index, value) -- insert value before index' 684 raise IndexError 685 686 def append(self, value): 687 'S.append(value) -- append value to the end of the sequence' 688 self.insert(len(self), value) 689 690 def clear(self): 691 'S.clear() -> None -- remove all items from S' 692 try: 693 while True: 694 self.pop() 695 except IndexError: 696 pass 697 698 def reverse(self): 699 'S.reverse() -- reverse *IN PLACE*' 700 n = len(self) 701 for i in range(n//2): 702 self[i], self[n-i-1] = self[n-i-1], self[i] 703 704 def extend(self, values): 705 'S.extend(iterable) -- extend sequence by appending elements from the iterable' 706 for v in values: 707 self.append(v) 708 709 def pop(self, index=-1): 710 '''S.pop([index]) -> item -- remove and return item at index (default last). 711 Raise IndexError if list is empty or index is out of range. 712 ''' 713 v = self[index] 714 del self[index] 715 return v 716 717 def remove(self, value): 718 '''S.remove(value) -- remove first occurrence of value. 719 Raise ValueError if the value is not present. 720 ''' 721 del self[self.index(value)] 722 723 def __iadd__(self, values): 724 self.extend(values) 725 return self 726 727MutableSequence.register(list) 728MutableSequence.register(bytearray) # Multiply inheriting, see ByteString 729