Context Navigation

Back to Ticket #13394

Ticket #13394: weak_dict_nb.2.pyx

File weak_dict_nb.2.pyx, 35.8 KB (added by nbruin, 9 years ago)
Updated git commit

Line
1	"""
2	Fast and safe weak value dictionary
3
4	AUTHORS:
5
6	- Simon King (2013-10)
7	- Nils Bruin (2013-10)
8
9	Python's :mod:`weakref` module provides
10	:class:`~weakref.WeakValueDictionary`. This behaves similar to a dictionary,
11	but it does not prevent its values from garbage collection. Hence, it stores
12	the values by weak references with callback functions: The callback function
13	deletes a key-value pair from the dictionary, as soon as the value becomes
14	subject to garbage collection.
15
16	However, a problem arises if hash and comparison of the key depend on the
17	value that is being garbage collected::
18
19	sage: import weakref
20	sage: class Vals(object): pass
21	sage: class Keys:
22	....: def __init__(self, val):
23	....: self.val = weakref.ref(val)
24	....: def __hash__(self):
25	....: return hash(self.val())
26	....: def __eq__(self, other):
27	....: return self.val() == other.val()
28	sage: ValList = [Vals() for _ in range(10)]
29	sage: D = weakref.WeakValueDictionary()
30	sage: for v in ValList:
31	....: D[Keys(v)] = v
32	sage: len(D)
33	10
34	sage: del ValList, v
35	Exception KeyError: (<__main__.Keys instance at ...>,) in <function remove at ...> ignored
36	Exception KeyError: (<__main__.Keys instance at ...>,) in <function remove at ...> ignored
37	Exception KeyError: (<__main__.Keys instance at ...>,) in <function remove at ...> ignored
38	Exception KeyError: (<__main__.Keys instance at ...>,) in <function remove at ...> ignored
39	...
40	sage: len(D) > 1
41	True
42
43	Hence, there are scary error messages, and moreover the defunct items have not
44	been removed from the dictionary.
45
46	Therefore, Sage provides an alternative implementation
47	:class:`sage.misc.weak_dict.WeakValueDictionary`, using a callback that
48	removes the defunct item not based on hash and equality check of the key (this
49	is what fails in the example above), but based on comparison by identity. This
50	is possible, since references with callback function are distinct even if they
51	point to the same object. Hence, even if the same object ``O`` occurs as value
52	for several keys, each reference to ``O`` corresponds to a unique key. We see
53	no error messages, and the items get correctly removed::
54
55	sage: ValList = [Vals() for _ in range(10)]
56	sage: import sage.misc.weak_dict
57	sage: D = sage.misc.weak_dict.WeakValueDictionary()
58	sage: for v in ValList:
59	....: D[Keys(v)] = v
60	sage: len(D)
61	10
62	sage: del ValList
63	sage: len(D)
64	1
65	sage: del v
66	sage: len(D)
67	0
68
69	Another proplem arises when iterating over the items of a dictionary: If
70	garbage collection occurs during iteration, then the content of the dictionary
71	changes, and the iteration breaks for :class:`weakref.WeakValueDictionary`::
72
73	sage: class Cycle:
74	....: def __init__(self):
75	....: self.selfref = self
76	sage: C = [Cycle() for n in range(10)]
77	sage: D = weakref.WeakValueDictionary(enumerate(C))
78	sage: import gc
79	sage: gc.disable()
80	sage: del C[:5]
81	sage: len(D)
82	10
83	sage: for k in D.iterkeys():
84	....: gc.enable()
85	....: _ = gc.collect()
86	Traceback (most recent call last):
87	...
88	RuntimeError: dictionary changed size during iteration
89
90	With :class:`~sage.misc.weak_dict.WeakValueDictionary`, the behaviour is
91	safer. Note that iteration over a WeakValueDictionary is non-deterministic,
92	since the lifetime of values (and hence the presence of keys) in the dictionary
93	may depend on when garbage collection occurs. The method implemented here
94	will at least postpone dictionary mutations due to garbage collection callbacks.
95	This means that as long as there is at least one iterator active on a dictionary,
96	none of its keys will be deallocated (which could have side-effects).
97	Which entries are returned is of course still dependent on when garbage
98	collection occurs. Note that when a key gets returned as "present" in the
99	dictionary, there is no guarantee one can actually retrieve its value: it may
100	have been garbage collected in the mean time.
101
102	Note that Sage's weak value dictionary is actually an instance of
103	:class:`dict`, in contrast to :mod:`weakref`'s weak value dictionary::
104
105	sage: issubclass(weakref.WeakValueDictionary, dict)
106	False
107	sage: issubclass(sage.misc.weak_dict.WeakValueDictionary, dict)
108	True
109
110	See :trac:`13394` for a discussion of some of the design considerations.
111	"""
112	########################################################################
113	# Copyright (C) 2013 Simon King <simon.king@uni-jena.de>
114	# Nils Bruin <nbruin@sfu.ca>
115	#
116	# Distributed under the terms of the GNU General Public License (GPL)
117	#
118	# http://www.gnu.org/licenses/
119	########################################################################
120
121	import weakref
122	from weakref import KeyedRef
123	from copy import deepcopy
124
125	from cpython.dict cimport *
126	from cpython.weakref cimport *
127	from cpython.list cimport *
128
129	from cpython cimport Py_XINCREF, Py_XDECREF
130
131	cdef extern from "Python.h":
132	ctypedef struct PyDictEntry:
133	Py_ssize_t me_hash
134	PyObject* me_key
135	PyObject* me_value
136	ctypedef struct PyDictObject:
137	Py_ssize_t ma_fill
138	Py_ssize_t ma_used
139	Py_ssize_t ma_mask
140	PyDictEntry* ma_table
141
142	PyObject* Py_None
143	#we need this redefinition because we want to be able to call
144	#PyWeakref_GetObject with borrowed references. This is the recommended
145	#strategy according to Cython/Includes/cpython/__init__.pxd
146	PyObject* PyWeakref_GetObject(PyObject * wr)
147
148	#this one's just missing.
149	long PyObject_Hash(object obj)
150
151	#this routine extracts the "dummy" sentinel value that is used in dicts to mark
152	#"freed" slots. We need that to delete things ourselves.
153	cdef PyObject* init_dummy() except NULL:
154	cdef dict D = dict()
155	cdef PyDictObject* mp = <PyDictObject ><void >D
156	cdef size_t mask
157	cdef PyDictEntry* ep0 = mp.ma_table
158	cdef PyDictEntry* ep
159	cdef size_t i
160	global dummy
161
162	D[0]=0; del D[0] #ensure that there is a "deleted" entry in the dict
163	mask = mp.ma_mask
164	#since our entry had hash 0, we should really succeed on the first iteration
165	for i in range(mask+1):
166	ep = &(ep0[i])
167	if ep.me_key != NULL:
168	return ep.me_key
169	raise RuntimeError("Problem initializing dummy")
170
171	#note that dummy here is a borrowed reference. That's not a problem because
172	#we're never giving it up and dictobject.c is also holding a permanent reference
173	#to this object
174	cdef PyObject* dummy = init_dummy()
175
176	#this routine looks for the first entry in dict D with given hash of the
177	#key and given (identical!) value and deletes that entry.
178	cpdef del_dictitem_by_exact_value(dict D, object value, long hash):
179	"""
180	Given a dictionary `mp`, a hash `hash`, and `value`, remove a key k from the
181	dictionary satisfying `hash(k) == hash` and `D[k] is value`. If no such entry
182	exists in `mp`, do nothing.
183
184	TESTS::
185
186	sage: from sage.misc.weak_dict import del_dictitem_by_exact_value
187	sage: B=1000
188	sage: L=list(range(B))
189	sage: D1=dict()
190	sage: D2=dict()
191	sage: for i in range(100000):
192	....: assert D1 == D2
193	....: ki=L[floor(random()*B)]
194	....: vi=L[floor(random()*B)]
195	....: D1[ki]=vi
196	....: D2[ki]=vi
197	....: ko=L[floor(random()*B)]
198	....: if ko in D1:
199	....: vo=D1[ko]
200	....: del D1[ko]
201	....: del_dictitem_by_exact_value(D2,vo,hash(ko))
202	sage: D1 == D2
203	True
204
205	"""
206	cdef size_t i
207	cdef size_t perturb
208	cdef PyDictObject* mp = <PyDictObject ><void >D
209	cdef size_t mask = <size_t> mp.ma_mask
210	cdef PyDictEntry* ep0 = mp.ma_table
211	cdef PyDictEntry* ep
212	i = hash & mask
213	ep = &(ep0[i])
214
215	if ep.me_key == NULL:
216	# key not found
217	return
218
219	perturb = hash
220	while (<void >(ep.me_value) != <void >value or ep.me_hash != hash):
221	i = (i << 2) + i + perturb +1
222	ep = &ep0[i & mask]
223	if ep.me_key == NULL:
224	# key not found
225	return
226	perturb = perturb >> 5 #this is the value of PERTURB_SHIFT
227
228	old_key = ep.me_key
229	if dummy == NULL:
230	raise RuntimeError("dummy needs to be initialized")
231	Py_XINCREF(dummy)
232	ep.me_key = dummy
233	old_value = ep.me_value
234	ep.me_value = NULL
235	mp.ma_used -= 1
236	#in our case, the value is always a dead weakref, so decreffing that is
237	#fairly safe
238	Py_XDECREF(old_value)
239	#this could have any effect.
240	Py_XDECREF(old_key)
241
242	cdef class WeakValueDictionary(dict):
243	"""
244	IMPLEMENTATION:
245
246	The :class:`WeakValueDictionary` inherits from :class:`dict`. In its
247	implementation, it stores weakrefs to the actual values under the keys.
248	All access routines are wrapped to transparently place and remove these
249	weakrefs.
250
251	NOTE:
252
253	In contrast to :class:`weakref.WeakValueDictionary` in Python's
254	:mod:`weakref` module, the callback does not need to assume that the
255	dictionary key is a valid Python object when it is called. There is no
256	need to compute the hash or compare the dictionary keys. This is why
257	the example below would not work with
258	:class:`weakref.WeakValueDictionary`, but does work with
259	:class:`sage.misc.weak_dict.WeakValueDictionary`.
260
261	EXAMPLES::
262
263	sage: import weakref
264	sage: class Vals(object): pass
265	sage: class Keys:
266	....: def __init__(self, val):
267	....: self.val = weakref.ref(val)
268	....: def __hash__(self):
269	....: return hash(self.val())
270	....: def __eq__(self, other):
271	....: return self.val() == other.val()
272	sage: ValList = [Vals() for _ in range(10)]
273	sage: import sage.misc.weak_dict
274	sage: D = sage.misc.weak_dict.WeakValueDictionary()
275	sage: for v in ValList:
276	....: D[Keys(v)] = v
277	sage: len(D)
278	10
279	sage: del ValList
280	sage: len(D)
281	1
282	sage: del v
283	sage: len(D)
284	0
285
286	TESTS:
287
288	Check that deferred callbacks that are invalidated are silently
289	dealt with::
290
291	sage: from sage.misc.weak_dict import WeakValueDictionary
292	sage: D=WeakValueDictionary()
293	sage: V=set([2])
294	sage: W=set([3])
295	sage: D[1]=V
296	sage: i=D.iteritems(); d=i.next(); del d
297	sage: del V
298	sage: D[1]=W
299	sage: len(D)
300	1
301	sage: del i
302	sage: D.items()
303	[(1, set([3]))]
304
305
306	"""
307	cdef callback
308	cdef int _guard_level
309	cdef list _pending_removals
310	cdef _iteration_context
311
312	def __init__(self, data=()):
313	"""
314	Create a :class:`WeakValueDictionary` with given initial data.
315
316	INPUT:
317
318	Optional iterable of key-value pairs
319
320	EXAMPLES::
321
322	sage: L = [(p,GF(p)) for p in prime_range(10)]
323	sage: import sage.misc.weak_dict
324	sage: D = sage.misc.weak_dict.WeakValueDictionary()
325	sage: len(D)
326	0
327	sage: D = sage.misc.weak_dict.WeakValueDictionary(L)
328	sage: len(D) == len(L)
329	True
330
331	"""
332	dict.__init__(self)
333	# Define a callback function. In contrast to what is done in Python's
334	# weakref.WeakValueDictionary, we use a closure and not a weak
335	# reference to refer to self. Reason: We trust that we will not create
336	# sub-classes of keyed references or weak value dictionaries providing
337	# a __del__ method.
338	def callback(r):
339	#The situation is the following:
340	#in the underlying dictionary, we have stored a KeyedRef r
341	#under a key k. The attribute r.key is the hash of k.
342	cdef WeakValueDictionary cself = self
343	if cself._guard_level:
344	cself._pending_removals.append(r)
345	else:
346	del_dictitem_by_exact_value(cself, r, r.key)
347	self.callback = callback
348	self._guard_level = 0
349	self._pending_removals = []
350	self._iteration_context = _IterationContext(self)
351	for k,v in data:
352	self[k] = v
353
354	def __copy__(self):
355	"""
356	Return a copy of this weak dictionary.
357
358	EXAMPLES::
359
360	sage: import sage.misc.weak_dict
361	sage: D = sage.misc.weak_dict.WeakValueDictionary()
362	sage: D[1] = QQ
363	sage: D[2] = ZZ
364	sage: D[None] = CC
365	sage: E = copy(D) # indirect doctest
366	sage: set(E.items()) == set(D.items())
367	True
368
369	"""
370	return WeakValueDictionary(self.iteritems())
371
372	def __deepcopy__(self, memo):
373	"""
374	Return a copy of this dictionary using copies of the keys.
375
376	NOTE:
377
378	The values of the dictionary are not copied, since we can not copy the
379	external strong references to the values, which are decisive for
380	garbage collection.
381
382	EXAMPLES::
383
384	sage: class C(object): pass
385	sage: V = [C(),C()]
386	sage: D = sage.misc.weak_dict.WeakValueDictionary()
387	sage: D[C()] = V[0]
388	sage: D[C()] = V[1]
389	sage: E = deepcopy(D) # indirect doctest
390
391	The keys are copied (in this silly example, the copies of the keys are
392	actually not equal to the original keys)::
393
394	sage: set(E.keys()) == set(D.keys())
395	False
396
397	However, the values are not copied::
398
399	sage: set(E.values()) == set(D.values()) == set(V)
400	True
401
402	"""
403	out = WeakValueDictionary()
404	for k,v in self.iteritems():
405	out[deepcopy(k, memo)] = v
406	return out
407
408	def __repr__(self):
409	"""
410	EXAMPLES::
411
412	sage: import sage.misc.weak_dict
413	sage: repr(sage.misc.weak_dict.WeakValueDictionary([(1,ZZ),(2,QQ)])) # indirect doctest
414	'<WeakValueDictionary at 0x...>'
415
416	"""
417	return "<WeakValueDictionary at 0x%x>" % id(self)
418
419	def __str__(self):
420	"""
421	EXAMPLES::
422
423	sage: import sage.misc.weak_dict
424	sage: str(sage.misc.weak_dict.WeakValueDictionary([(1,ZZ),(2,QQ)])) # indirect doctest
425	'<WeakValueDictionary at 0x...>'
426
427	"""
428	return "<WeakValueDictionary at 0x%x>" % id(self)
429
430	def setdefault(self, k, default=None):
431	"""
432	Return the stored value for a given key; return and store a default
433	value if no previous value is stored.
434
435	EXAMPLES::
436
437	sage: import sage.misc.weak_dict
438	sage: L = [(p,GF(p)) for p in prime_range(10)]
439	sage: D = sage.misc.weak_dict.WeakValueDictionary(L)
440	sage: len(D)
441	4
442
443	The value for an existing key is returned and not overridden::
444
445	sage: D.setdefault(5, ZZ)
446	Finite Field of size 5
447	sage: D[5]
448	Finite Field of size 5
449
450	For a non-existing key, the default value is stored and returned::
451
452	sage: D.has_key(4)
453	False
454	sage: D.setdefault(4, ZZ)
455	Integer Ring
456	sage: D.has_key(4)
457	True
458	sage: D[4]
459	Integer Ring
460	sage: len(D)
461	5
462
463	"""
464	cdef PyObject* wr = PyDict_GetItem(self, k)
465	if wr != NULL:
466	out = PyWeakref_GetObject(wr)
467	if out != Py_None:
468	return <object>out
469	PyDict_SetItem(self,k,KeyedRef(default,self.callback,PyObject_Hash(k)))
470	return default
471
472	def __setitem__(self, k, v):
473	"""
474	EXAMPLES::
475
476	sage: import sage.misc.weak_dict
477	sage: D = sage.misc.weak_dict.WeakValueDictionary()
478	sage: ZZ in D
479	False
480
481	One can set new items::
482
483	sage: D[ZZ] = QQ # indirect doctest
484	sage: D[ZZ]
485	Rational Field
486	sage: len(D)
487	1
488	sage: ZZ in D
489	True
490
491	One can also override existing items::
492
493	sage: D[ZZ] = RLF
494	sage: ZZ in D
495	True
496	sage: D[ZZ]
497	Real Lazy Field
498	sage: len(D)
499	1
500
501	TESTS:
502
503	One may wonder whether it causes problems when garbage collection for
504	a previously exististing item happens after overriding the
505	item. The example shows that it is not a problem::
506
507	sage: class Cycle:
508	....: def __init__(self):
509	....: self.selfref = self
510	sage: L = [Cycle() for _ in range(5)]
511	sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(L))
512	sage: len(D)
513	5
514	sage: import gc
515	sage: gc.disable()
516	sage: del L
517	sage: len(D)
518	5
519	sage: D[2] = ZZ
520	sage: len(D)
521	5
522	sage: gc.enable()
523	sage: _ = gc.collect()
524	sage: len(D)
525	1
526	sage: D.items()
527	[(2, Integer Ring)]
528
529	"""
530	PyDict_SetItem(self,k,KeyedRef(v,self.callback,PyObject_Hash(k)))
531
532	#def __delitem__(self, k):
533	#we don't really have to override this method.
534
535	def pop(self, k):
536	"""
537	Return the value for a given key, and delete it from the dictionary.
538
539	EXAMPLES::
540
541	sage: import sage.misc.weak_dict
542	sage: L = [GF(p) for p in prime_range(10^3)]
543	sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(L))
544	sage: 20 in D
545	True
546	sage: D.pop(20)
547	Finite Field of size 73
548	sage: 20 in D
549	False
550	sage: D.pop(20)
551	Traceback (most recent call last):
552	...
553	KeyError: 20
554
555	"""
556	cdef PyObject* wr = PyDict_GetItem(self, k)
557	if wr == NULL:
558	raise KeyError(k)
559	cdef PyObject* outref = PyWeakref_GetObject(wr)
560	if outref == Py_None:
561	raise KeyError(k)
562	#we turn the output into a new reference before deleting the item,
563	#because the deletion can cause any kind of havoc.
564	out = <object>outref
565	del self[k]
566	return out
567
568	def popitem(self):
569	"""
570	Return and delete some item from the dictionary.
571
572	EXAMPLES::
573
574	sage: import sage.misc.weak_dict
575	sage: D = sage.misc.weak_dict.WeakValueDictionary()
576	sage: D[1] = ZZ
577
578	The dictionary only contains a single item, hence, it is clear which
579	one will be returned::
580
581	sage: D.popitem()
582	(1, Integer Ring)
583
584	Now, the dictionary is empty, and hence the next attempt to pop an
585	item will fail with a ``KeyError``::
586
587	sage: D.popitem()
588	Traceback (most recent call last):
589	...
590	KeyError: 'popitem(): weak value dictionary is empty'
591
592	"""
593	for k,v in self.iteritems():
594	del self[k]
595	return k, v
596	raise KeyError('popitem(): weak value dictionary is empty')
597
598	def get(self, k, d=None):
599	"""
600	Return the stored value for a key, or a default value for unkown keys.
601
602	The default value defaults to None.
603
604	EXAMPLES::
605
606	sage: import sage.misc.weak_dict
607	sage: L = [GF(p) for p in prime_range(10^3)]
608	sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(L))
609	sage: 100 in D
610	True
611	sage: 200 in D
612	False
613	sage: D.get(100, "not found")
614	Finite Field of size 547
615	sage: D.get(200, "not found")
616	'not found'
617	sage: D.get(200) is None
618	True
619
620	"""
621	cdef PyObject * wr = PyDict_GetItem(self, k)
622	if wr == NULL:
623	return d
624	out = PyWeakref_GetObject(wr)
625	if out == Py_None:
626	return d
627	else:
628	return <object>out
629
630	def __getitem__(self, k):
631	"""
632	TESTS::
633
634	sage: import sage.misc.weak_dict
635	sage: D = sage.misc.weak_dict.WeakValueDictionary()
636	sage: D[ZZ] = QQ
637	sage: D[QQ]
638	Traceback (most recent call last):
639	...
640	KeyError: Rational Field
641	sage: D[ZZ] # indirect doctest
642	Rational Field
643
644	As usual, the dictionary keys are compared by `==` and not by
645	identity::
646
647	sage: D[10] = ZZ
648	sage: D[int(10)]
649	Integer Ring
650
651	"""
652	cdef PyObject* wr = PyDict_GetItem(self, k)
653	if wr == NULL:
654	raise KeyError(k)
655	out = PyWeakref_GetObject(wr)
656	if out == Py_None:
657	raise KeyError(k)
658	return <object>out
659
660	def has_key(self, k):
661	"""
662	Returns True, if the key is known to the dictionary.
663
664	EXAMPLES::
665
666	sage: import sage.misc.weak_dict
667	sage: class Vals(object): pass
668	sage: L = [Vals() for _ in range(10)]
669	sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(L))
670	sage: D.has_key(3)
671	True
672
673	As usual, keys are compared by equality and not by identity::
674
675	sage: D.has_key(int(3))
676	True
677
678	This is a weak value dictionary. Hence, the existence of the
679	dictionary does not prevent the values from garbage collection,
680	thereby removing the corresponding key-value pairs::
681
682	sage: del L[3]
683	sage: D.has_key(3)
684	False
685
686	"""
687	return k in self
688
689	def __contains__(self, k):
690	"""
691	Containment in the set of keys.
692
693	TESTS::
694
695	sage: import sage.misc.weak_dict
696	sage: class Vals(object): pass
697	sage: L = [Vals() for _ in range(10)]
698	sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(L))
699	sage: 3 in D # indirect doctest
700	True
701
702	As usual, keys are compared by equality and not by identity::
703
704	sage: int(3) in D
705	True
706
707	This is a weak value dictionary. Hence, the existence of the
708	dictionary does not prevent the values from garbage collection,
709	thereby removing the corresponding key-value pairs::
710
711	sage: del L[3]
712	sage: 3 in D
713	False
714
715	"""
716	cdef PyObject* wr = PyDict_GetItem(self, k)
717	if wr==NULL:
718	return False
719	if PyWeakref_GetObject(wr)==Py_None:
720	return False
721	else:
722	return True
723
724	#def __len__(self):
725	#since GC is not deterministic, neither is the length of a WeakValueDictionary,
726	#so we might as well just return the normal dictionary length.
727
728	def iterkeys(self):
729	"""
730	Iterate over the keys of this dictionary.
731
732	.. WARNING::
733
734	Iteration is unsafe, if the length of the dictionary changes
735	during the iteration! This can also happen by garbage collection.
736
737	EXAMPLES::
738
739	sage: import sage.misc.weak_dict
740	sage: class Vals(object): pass
741	sage: L = [Vals() for _ in range(10)]
742	sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(L))
743	sage: del L[4]
744
745	One item got deleted from the list ``L`` and hence the corresponding
746	item in the dictionary got deleted as well. Therefore, the
747	corresponding key 4 is missing in the list of keys::
748
749	sage: list(sorted(D.iterkeys()))
750	[0, 1, 2, 3, 5, 6, 7, 8, 9]
751
752	"""
753	cdef PyObject key, wr
754	cdef Py_ssize_t pos = 0
755	with self._iteration_context:
756	while PyDict_Next(self, &pos, &key, &wr):
757	#this check doesn't really say anything: by the time
758	#the key makes it to the customer, it may have already turned
759	#invalid. It's a cheap check, though.
760	if PyWeakref_GetObject(wr)!=Py_None:
761	yield <object>key
762
763	def __iter__(self):
764	"""
765	Iterate over the keys of this dictionary.
766
767	.. WARNING::
768
769	Iteration is unsafe, if the length of the dictionary changes
770	during the iteration! This can also happen by garbage collection.
771
772	EXAMPLES::
773
774	sage: import sage.misc.weak_dict
775	sage: class Vals(object): pass
776	sage: L = [Vals() for _ in range(10)]
777	sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(L))
778	sage: del L[4]
779
780	One item got deleted from the list ``L`` and hence the corresponding
781	item in the dictionary got deleted as well. Therefore, the
782	corresponding key 4 is missing in the list of keys::
783
784	sage: sorted(list(D)) # indirect doctest
785	[0, 1, 2, 3, 5, 6, 7, 8, 9]
786
787	"""
788	return self.iterkeys()
789
790	def keys(self):
791	"""
792	The list of keys.
793
794	EXAMPLES::
795
796	sage: import sage.misc.weak_dict
797	sage: class Vals(object): pass
798	sage: L = [Vals() for _ in range(10)]
799	sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(L))
800	sage: del L[4]
801
802	One item got deleted from the list ``L`` and hence the corresponding
803	item in the dictionary got deleted as well. Therefore, the
804	corresponding key 4 is missing in the list of keys::
805
806	sage: sorted(D.keys())
807	[0, 1, 2, 3, 5, 6, 7, 8, 9]
808
809	"""
810	return list(self.iterkeys())
811
812	def itervalues(self):
813	"""
814	Iterate over the values of this dictionary.
815
816	.. WARNING::
817
818	Iteration is unsafe, if the length of the dictionary changes
819	during the iteration! This can also happen by garbage collection.
820
821	EXAMPLES::
822
823	sage: import sage.misc.weak_dict
824	sage: class Vals:
825	....: def __init__(self, n):
826	....: self.n = n
827	....: def __repr__(self):
828	....: return "<%s>"%self.n
829	....: def __cmp__(self, other):
830	....: c = cmp(type(self),type(other))
831	....: if c:
832	....: return c
833	....: return cmp(self.n,other.n)
834	sage: L = [Vals(n) for n in range(10)]
835	sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(L))
836
837	We delete one item from ``D`` and we delete one item from the list
838	``L``. The latter implies that the corresponding item from ``D`` gets
839	deleted as well. Hence, there remain eight values::
840
841	sage: del D[2]
842	sage: del L[5]
843	sage: for v in sorted(D.itervalues()):
844	....: print v
845	<0>
846	<1>
847	<3>
848	<4>
849	<6>
850	<7>
851	<8>
852	<9>
853
854	"""
855	cdef PyObject key, wr
856	cdef Py_ssize_t pos = 0
857	with self._iteration_context:
858	while PyDict_Next(self, &pos, &key, &wr):
859	out = PyWeakref_GetObject(wr)
860	if out != Py_None:
861	yield <object>out
862
863	def values(self):
864	"""
865	Return the list of values.
866
867	EXAMPLES::
868
869	sage: import sage.misc.weak_dict
870	sage: class Vals:
871	....: def __init__(self, n):
872	....: self.n = n
873	....: def __repr__(self):
874	....: return "<%s>"%self.n
875	....: def __cmp__(self, other):
876	....: c = cmp(type(self),type(other))
877	....: if c:
878	....: return c
879	....: return cmp(self.n,other.n)
880	sage: L = [Vals(n) for n in range(10)]
881	sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(L))
882
883	We delete one item from ``D`` and we delete one item from the list
884	``L``. The latter implies that the corresponding item from ``D`` gets
885	deleted as well. Hence, there remain eight values::
886
887	sage: del D[2]
888	sage: del L[5]
889	sage: sorted(D.values())
890	[<0>, <1>, <3>, <4>, <6>, <7>, <8>, <9>]
891
892	"""
893	return list(self.itervalues())
894
895	def iteritems(self):
896	"""
897	Iterate over the items of this dictionary.
898
899	.. WARNING::
900
901	Iteration is unsafe, if the length of the dictionary changes
902	during the iteration! This can also happen by garbage collection.
903
904	EXAMPLES::
905
906	sage: import sage.misc.weak_dict
907	sage: class Vals:
908	....: def __init__(self, n):
909	....: self.n = n
910	....: def __repr__(self):
911	....: return "<%s>"%self.n
912	....: def __cmp__(self, other):
913	....: c = cmp(type(self),type(other))
914	....: if c:
915	....: return c
916	....: return cmp(self.n,other.n)
917	sage: class Keys(object):
918	....: def __init__(self, n):
919	....: self.n = n
920	....: def __hash__(self):
921	....: if self.n%2:
922	....: return 5
923	....: return 3
924	....: def __repr__(self):
925	....: return "[%s]"%self.n
926	....: def __cmp__(self, other):
927	....: c = cmp(type(self),type(other))
928	....: if c:
929	....: return c
930	....: return cmp(self.n,other.n)
931	sage: L = [(Keys(n), Vals(n)) for n in range(10)]
932	sage: D = sage.misc.weak_dict.WeakValueDictionary(L)
933
934	We remove one dictionary item directly. Another item is removed by
935	means of garbage collection. By consequence, there remain eight
936	items in the dictionary::
937
938	sage: del D[Keys(2)]
939	sage: del L[5]
940	sage: for k,v in sorted(D.iteritems()):
941	....: print k, v
942	[0] <0>
943	[1] <1>
944	[3] <3>
945	[4] <4>
946	[6] <6>
947	[7] <7>
948	[8] <8>
949	[9] <9>
950
951	"""
952	cdef PyObject key, wr
953	cdef Py_ssize_t pos = 0
954	with self._iteration_context:
955	while PyDict_Next(self, &pos, &key, &wr):
956	out = PyWeakref_GetObject(wr)
957	if out != Py_None:
958	yield <object>key, <object>out
959
960	def items(self):
961	"""
962	The key-value pairs of this dictionary.
963
964	EXAMPLES::
965
966	sage: import sage.misc.weak_dict
967	sage: class Vals:
968	....: def __init__(self, n):
969	....: self.n = n
970	....: def __repr__(self):
971	....: return "<%s>"%self.n
972	....: def __cmp__(self, other):
973	....: c = cmp(type(self),type(other))
974	....: if c:
975	....: return c
976	....: return cmp(self.n,other.n)
977	sage: class Keys(object):
978	....: def __init__(self, n):
979	....: self.n = n
980	....: def __hash__(self):
981	....: if self.n%2:
982	....: return 5
983	....: return 3
984	....: def __repr__(self):
985	....: return "[%s]"%self.n
986	....: def __cmp__(self, other):
987	....: c = cmp(type(self),type(other))
988	....: if c:
989	....: return c
990	....: return cmp(self.n,other.n)
991	sage: L = [(Keys(n), Vals(n)) for n in range(10)]
992	sage: D = sage.misc.weak_dict.WeakValueDictionary(L)
993
994	We remove one dictionary item directly. Another item is removed by
995	means of garbage collection. By consequence, there remain eight
996	items in the dictionary::
997
998	sage: del D[Keys(2)]
999	sage: del L[5]
1000	sage: sorted(D.items())
1001	[([0], <0>),
1002	([1], <1>),
1003	([3], <3>),
1004	([4], <4>),
1005	([6], <6>),
1006	([7], <7>),
1007	([8], <8>),
1008	([9], <9>)]
1009
1010	"""
1011	return list(self.iteritems())
1012
1013	cdef class _IterationContext:
1014	"""
1015	An iterator that protects :class:`WeakValueDictionary` from some negative
1016	effects of deletions due to garbage collection during iteration.
1017	It's still not safe to explicitly mutate a dictionary during iteration,
1018	though. Doing so is a bug in a program (since iteration order is
1019	non-deterministic the results are not well-defined)
1020
1021	This is implemented by putting all items that are deleted during iteration
1022	are not actually deleted, but only marked for deletion. Note, however,
1023	that they behave like items that actually are deleted. E.g., it is not
1024	possible to delete the same item twice::
1025
1026	sage: class Val: pass
1027	sage: V = [Val() for n in range(3)]
1028	sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(V))
1029	sage: for k,v in D.iteritems():
1030	....: print k in D.keys()
1031	....: del D[k]
1032	....: print k in D.keys()
1033	....: try:
1034	....: del D[k]
1035	....: except KeyError:
1036	....: print "due error"
1037	True
1038	False
1039	due error
1040	True
1041	False
1042	due error
1043	True
1044	False
1045	due error
1046
1047	"""
1048	cdef WeakValueDictionary Dict
1049	def __init__(self, Dict):
1050	"""
1051	INPUT:
1052
1053	A :class:`WeakValueDictionary`
1054
1055	This context manager is used during iteration over the given
1056	dictionary, and prevents negative side-effects of item deletions
1057	during iteration.
1058
1059	EXAMPLES::
1060
1061	sage: import sage.misc.weak_dict
1062	sage: class Val: pass
1063	sage: V = [Val() for n in range(3)]
1064	sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(V))
1065	sage: for k,v in D.iteritems(): # indirect doctest
1066	....: k in D.keys()
1067	....: del D[k]
1068	....: k in D.keys()
1069	True
1070	False
1071	True
1072	False
1073	True
1074	False
1075
1076	"""
1077	self.Dict = Dict
1078
1079	def __enter__(self):
1080	"""
1081	Make sure that items of a weak value dictionary are not actually
1082	deleted, but only marked for deletion.
1083
1084	TESTS::
1085
1086	sage: import sage.misc.weak_dict
1087	sage: class Val: pass
1088	sage: V = [Val() for n in range(3)]
1089	sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(V))
1090	sage: for k,v in D.iteritems(): # indirect doctest
1091	....: k in D.keys()
1092	....: del D[k]
1093	....: k in D.keys()
1094	True
1095	False
1096	True
1097	False
1098	True
1099	False
1100
1101	"""
1102	self.Dict._guard_level += 1
1103	return self
1104
1105	def __exit__(self, exc_type, exc_val, exc_tb):
1106	"""
1107	Make sure that all items of a weak value dictionary that are marked
1108	for deletion are actually deleted, as soon as there is no iteration
1109	over the dictionary.
1110
1111	TESTS::
1112
1113	sage: import sage.misc.weak_dict
1114	sage: class Val: pass
1115	sage: V = [Val() for n in range(3)]
1116	sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(V))
1117	sage: for k,v in D.iteritems(): # indirect doctest
1118	....: k in D.keys()
1119	....: del D[k]
1120	....: k in D.keys()
1121	True
1122	False
1123	True
1124	False
1125	True
1126	False
1127
1128	"""
1129	# Propagate errors by returning "False"
1130	self.Dict._guard_level -= 1
1131	#when the guard_level drops to zero, we try to remove all the
1132	#pending removals. Note that this could trigger another iterator
1133	#to become active, in which case we should back off.
1134	while (not self.Dict._guard_level) and self.Dict._pending_removals:
1135	self.Dict.callback(self.Dict._pending_removals.pop())
1136	return False

Download in other formats:

Original Format