Python code coverage for Lib/_abcoll.py

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