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