Ticket #13394: weak_dict_nb.2.pyx

File weak_dict_nb.2.pyx, 35.8 KB (added by nbruin, 5 years ago)

Updated git commit

Line 
1"""
2Fast and safe weak value dictionary
3
4AUTHORS:
5
6- Simon King (2013-10)
7- Nils Bruin (2013-10)
8
9Python's :mod:`weakref` module provides
10:class:`~weakref.WeakValueDictionary`. This behaves similar to a dictionary,
11but it does not prevent its values from garbage collection. Hence, it stores
12the values by weak references with callback functions: The callback function
13deletes a key-value pair from the dictionary, as soon as the value becomes
14subject to garbage collection.
15
16However, a problem arises if hash and comparison of the key depend on the
17value 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
43Hence, there are scary error messages, and moreover the defunct items have not
44been removed from the dictionary.
45
46Therefore, Sage provides an alternative implementation
47:class:`sage.misc.weak_dict.WeakValueDictionary`, using a callback that
48removes the defunct item not based on hash and equality check of the key (this
49is what fails in the example above), but based on comparison by identity. This
50is possible, since references with callback function are distinct even if they
51point to the same object. Hence, even if the same object ``O`` occurs as value
52for several keys, each reference to ``O`` corresponds to a unique key. We see
53no 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
69Another proplem arises when iterating over the items of a dictionary: If
70garbage collection occurs during iteration, then the content of the dictionary
71changes, 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
90With :class:`~sage.misc.weak_dict.WeakValueDictionary`, the behaviour is
91safer. Note that iteration over a WeakValueDictionary is non-deterministic,
92since the lifetime of values (and hence the presence of keys) in the dictionary
93may depend on when garbage collection occurs. The method implemented here
94will at least postpone dictionary mutations due to garbage collection callbacks.
95This means that as long as there is at least one iterator active on a dictionary,
96none of its keys will be deallocated (which could have side-effects).
97Which entries are returned is of course still dependent on when garbage
98collection occurs. Note that when a key gets returned as "present" in the
99dictionary, there is no guarantee one can actually retrieve its value: it may
100have been garbage collected in the mean time.
101
102Note 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
110See :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
121import weakref
122from weakref import KeyedRef
123from copy import deepcopy
124
125from cpython.dict cimport *
126from cpython.weakref cimport *
127from cpython.list cimport *
128
129from cpython cimport Py_XINCREF, Py_XDECREF
130
131cdef 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.
153cdef 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
174cdef 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.
178cpdef 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
242cdef 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
1013cdef 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