Ticket #13394: weak_dict.pyx

File weak_dict.pyx, 39.5 KB (added by nbruin, 6 years ago)

update

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 problem 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.
178cdef del_dictitem_by_exact_value(PyDictObject *mp, PyObject *value, long hash):
179    """
180    This is used in callbacks for the weak values of :class:`WeakValueDictionary`.
181
182    INPUT:
183
184    - ``PyDictObject *mp`` -- pointer to a dict
185    - ``PyObject *value``  -- pointer to a value of the dictionary
186    - ``long hash``        -- hash of the key by which the value is stored in the dict
187
188    The hash bucket determined by the given hash is searched for the item
189    containing the given value. If this item can't be found, the function is
190    silently returning. Otherwise, the item is removed from the dict.
191
192    TESTS:
193
194    The following is an indirect doctest, as discussed on :trac:`13394`.
195    ::
196
197        sage: from sage.misc.weak_dict import WeakValueDictionary
198        sage: V = [set(range(n)) for n in range(5)]
199        sage: D = WeakValueDictionary(enumerate(V))
200
201    The line ``V[k] = None`` triggers execution of the callback functions of
202    the dict values. However, the actual deletion is postponed till after the
203    iteration over the dictionary has finished. Hence, when the callbacks are
204    executed, the values which the callback belongs to has already been
205    overridded by a new value. Therefore, the callback does not delete the
206    item::
207
208        sage: for k in D.iterkeys():    # indirect doctest
209        ....:     V[k] = None
210        ....:     D[k] = ZZ
211        sage: len(D)
212        5
213        sage: D[1]
214        Integer Ring
215
216    """
217    cdef size_t i
218    cdef size_t perturb
219    cdef size_t mask = <size_t> mp.ma_mask
220    cdef PyDictEntry* ep0 = mp.ma_table
221    cdef PyDictEntry* ep
222    i = hash & mask
223    ep = &(ep0[i])
224
225    if ep.me_key == NULL:
226        # key not found
227        return
228
229    perturb = hash
230    while (<PyObject *>(ep.me_value) != value or ep.me_hash != hash):
231        i = (i << 2) + i + perturb +1
232        ep = &ep0[i & mask]
233        if ep.me_key == NULL:
234            # key not found
235            return
236        perturb = perturb >> 5 #this is the value of PERTURB_SHIFT
237
238    old_key = ep.me_key
239    if dummy == NULL:
240        raise RuntimeError("dummy needs to be initialized")
241    Py_XINCREF(dummy)
242    ep.me_key = dummy
243    old_value = ep.me_value
244    ep.me_value = NULL
245    mp.ma_used -= 1
246    #in our case, the value is always a dead weakref, so decreffing that is
247    #fairly safe
248    Py_XDECREF(old_value) 
249    #this could have any effect.
250    Py_XDECREF(old_key)
251
252def test_del_dictitem_by_exact_value(D, value, h):
253    """
254    This function helps testing some cdef function used to delete dictionary items.
255
256    INPUT:
257
258    - ``D`` -- a Python ``<dict>``.
259    - ``value`` -- an object that is value ``D``.
260    - ``h`` -- the hash of the key under which to find ``value`` in ``D``.
261
262    The underlying cdef function deletes an item from ``D`` that is in the
263    hash bucket determined by ``h`` and whose value is identic with
264    ``value``. Of course, this only makes sense if the pairs ``(h, value)``
265    corresponding to items in ``D`` are pair-wise distinct.
266
267    If a matching item can not be found, the function does nothing and
268    silently returns.
269
270    TESTS:
271
272    See :trac:`13394` for a discussion.
273    ::
274
275        sage: from sage.misc.weak_dict import test_del_dictitem_by_exact_value
276        sage: B=1000
277        sage: L=list(range(B))
278        sage: D1=dict()
279        sage: D2=dict()
280        sage: for i in range(100000):        # long time
281        ....:     ki=L[floor(random()*B)]
282        ....:     vi=L[floor(random()*B)]
283        ....:     D1[ki]=vi
284        ....:     D2[ki]=vi
285        ....:     ko=L[floor(random()*B)]
286        ....:     if ko in D1:
287        ....:         vo=D1[ko]
288        ....:         del D1[ko]
289        ....:         test_del_dictitem_by_exact_value(D2,vo,hash(ko))
290        ....:     assert D1 == D2
291
292    No action is taken if the item prescribed by key hash and value does not
293    exist in the dictionary::
294
295        sage: D = {1: ZZ}
296        sage: test_del_dictitem_by_exact_value(D, ZZ, 2)
297        sage: D
298        {1: Integer Ring}
299        sage: test_del_dictitem_by_exact_value(D, QQ, 1)
300        sage: D
301        {1: Integer Ring}
302
303    """
304    return del_dictitem_by_exact_value(<PyDictObject *>D, <PyObject *>value, h)
305
306cdef class WeakValueDictionary(dict):
307    """
308    IMPLEMENTATION:
309
310    The :class:`WeakValueDictionary` inherits from :class:`dict`. In its
311    implementation, it stores weakrefs to the actual values under the keys.
312    All access routines are wrapped to transparently place and remove these
313    weakrefs.
314
315    NOTE:
316
317    In contrast to :class:`weakref.WeakValueDictionary` in Python's
318    :mod:`weakref` module, the callback does not need to assume that the
319    dictionary key is a valid Python object when it is called. There is no
320    need to compute the hash or compare the dictionary keys. This is why
321    the example below would not work with
322    :class:`weakref.WeakValueDictionary`, but does work with
323    :class:`sage.misc.weak_dict.WeakValueDictionary`.
324
325    EXAMPLES::
326
327        sage: import weakref
328        sage: class Vals(object): pass
329        sage: class Keys:
330        ....:     def __init__(self, val):
331        ....:         self.val = weakref.ref(val)
332        ....:     def __hash__(self):
333        ....:         return hash(self.val())
334        ....:     def __eq__(self, other):
335        ....:         return self.val() == other.val()
336        sage: ValList = [Vals() for _ in range(10)]
337        sage: import sage.misc.weak_dict
338        sage: D = sage.misc.weak_dict.WeakValueDictionary()
339        sage: for v in ValList:
340        ....:     D[Keys(v)] = v
341        sage: len(D)
342        10
343        sage: del ValList
344        sage: len(D)
345        1
346        sage: del v
347        sage: len(D)
348        0
349
350    TESTS::
351
352    The following reflects the behaviour of the callback on weak dict values,
353    as discussed on :trac:`13394`.  ::
354
355        sage: from sage.misc.weak_dict import WeakValueDictionary
356        sage: V = [set(range(n)) for n in range(5)]
357        sage: D = WeakValueDictionary(enumerate(V))
358
359    The line ``V[k] = None`` triggers execution of the callback functions of
360    the dictionary values. However, the actual deletion is postponed till
361    after the iteration over the dictionary has finished. Hence, when the
362    callbacks are executed, the values which the callback belongs to has
363    already been overridded by a new value. Therefore, the callback does not
364    delete the item::
365
366        sage: for k in D.iterkeys():    # indirect doctest
367        ....:     V[k] = None
368        ....:     D[k] = ZZ
369        sage: len(D)
370        5
371        sage: D[1]
372        Integer Ring
373
374    The following is a stress test for weak value dictionaries::
375
376        sage: class C(object):
377        ....:     def __init__(self, n):
378        ....:         self.n = n
379        ....:     def __cmp__(self, other):
380        ....:         return cmp(type(self),type(other)) or cmp(self.n, other.n)
381        sage: B = 100
382        sage: L = [None]*B
383        sage: D1 = WeakValueDictionary()
384        sage: D2 = WeakValueDictionary()
385        sage: for i in range(10000):
386        ....:     ki = floor(random()*B)
387        ....:     vi = C(floor(random()*B))
388        ....:     D1[ki] = vi
389        ....:     D2[ki] = vi
390        ....:     L[ki]  = vi
391        ....:     del vi
392        ....:     ko = floor(random()*B)
393        ....:     if ko in D1:
394        ....:         del D1[ko]
395        ....:         L[ko] = None
396        ....:     assert D1 == D2
397
398    """
399    cdef callback
400    cdef int _guard_level
401    cdef list _pending_removals
402    cdef _iteration_context
403
404    def __init__(self, data=()):
405        """
406        Create a :class:`WeakValueDictionary` with given initial data.
407
408        INPUT:
409
410        Optional iterable of key-value pairs
411
412        EXAMPLES::
413
414            sage: L = [(p,GF(p)) for p in prime_range(10)]
415            sage: import sage.misc.weak_dict
416            sage: D = sage.misc.weak_dict.WeakValueDictionary()
417            sage: len(D)
418            0
419            sage: D = sage.misc.weak_dict.WeakValueDictionary(L)
420            sage: len(D) == len(L)
421            True
422
423        """
424        dict.__init__(self)
425        # Define a callback function. In contrast to what is done in Python's
426        # weakref.WeakValueDictionary, we use a closure and not a weak
427        # reference to refer to self. Reason: We trust that we will not create
428        # sub-classes of keyed references or weak value dictionaries providing
429        # a __del__ method.
430        def callback(r):
431            #The situation is the following:
432            #in the underlying dictionary, we have stored a KeyedRef r
433            #under a key k. The attribute r.key is the hash of k.
434            cdef WeakValueDictionary cself = self
435            if cself._guard_level:
436                cself._pending_removals.append(r)
437            else:
438                del_dictitem_by_exact_value(<PyDictObject *>cself, <PyObject *>r, r.key)
439        self.callback = callback
440        self._guard_level = 0
441        self._pending_removals = []
442        self._iteration_context = _IterationContext(self)
443        for k,v in data:
444            self[k] = v
445
446    def __copy__(self):
447        """
448        Return a copy of this weak dictionary.
449
450        EXAMPLES::
451
452            sage: import sage.misc.weak_dict
453            sage: D = sage.misc.weak_dict.WeakValueDictionary()
454            sage: D[1] = QQ
455            sage: D[2] = ZZ
456            sage: D[None] = CC
457            sage: E = copy(D)    # indirect doctest
458            sage: set(E.items()) == set(D.items())
459            True
460
461        """
462        return WeakValueDictionary(self.iteritems())
463
464    def __deepcopy__(self, memo):
465        """
466        Return a copy of this dictionary using copies of the keys.
467
468        NOTE:
469
470        The values of the dictionary are not copied, since we can not copy the
471        external strong references to the values, which are decisive for
472        garbage collection.
473
474        EXAMPLES::
475
476            sage: class C(object): pass
477            sage: V = [C(),C()]
478            sage: D = sage.misc.weak_dict.WeakValueDictionary()
479            sage: D[C()] = V[0]
480            sage: D[C()] = V[1]
481            sage: E = deepcopy(D)     # indirect doctest
482
483        The keys are copied (in this silly example, the copies of the keys are
484        actually not equal to the original keys)::
485
486            sage: set(E.keys()) == set(D.keys())
487            False
488
489        However, the values are not copied::
490
491            sage: set(E.values()) == set(D.values()) == set(V)
492            True
493
494        """
495        out = WeakValueDictionary()
496        for k,v in self.iteritems():
497            out[deepcopy(k, memo)] = v
498        return out
499
500    def __repr__(self):
501        """
502        EXAMPLES::
503
504            sage: import sage.misc.weak_dict
505            sage: repr(sage.misc.weak_dict.WeakValueDictionary([(1,ZZ),(2,QQ)]))  # indirect doctest
506            '<WeakValueDictionary at 0x...>'
507
508        """
509        return "<WeakValueDictionary at 0x%x>" % id(self)
510
511    def __str__(self):
512        """
513        EXAMPLES::
514
515            sage: import sage.misc.weak_dict
516            sage: str(sage.misc.weak_dict.WeakValueDictionary([(1,ZZ),(2,QQ)]))  # indirect doctest
517            '<WeakValueDictionary at 0x...>'
518
519        """
520        return "<WeakValueDictionary at 0x%x>" % id(self)
521
522    def setdefault(self, k, default=None):
523        """
524        Return the stored value for a given key; return and store a default
525        value if no previous value is stored.
526
527        EXAMPLES::
528
529            sage: import sage.misc.weak_dict
530            sage: L = [(p,GF(p)) for p in prime_range(10)]
531            sage: D = sage.misc.weak_dict.WeakValueDictionary(L)
532            sage: len(D)
533            4
534
535        The value for an existing key is returned and not overridden::
536
537            sage: D.setdefault(5, ZZ)
538            Finite Field of size 5
539            sage: D[5]
540            Finite Field of size 5
541
542        For a non-existing key, the default value is stored and returned::
543
544            sage: D.has_key(4)
545            False
546            sage: D.setdefault(4, ZZ)
547            Integer Ring
548            sage: D.has_key(4)
549            True
550            sage: D[4]
551            Integer Ring
552            sage: len(D)
553            5
554
555        """
556        cdef PyObject* wr = PyDict_GetItem(self, k)
557        if wr != NULL:
558            out = PyWeakref_GetObject(wr)
559            if out != Py_None:
560                return <object>out
561        PyDict_SetItem(self,k,KeyedRef(default,self.callback,PyObject_Hash(k)))
562        return default
563
564    def __setitem__(self, k, v):
565        """
566        EXAMPLES::
567
568            sage: import sage.misc.weak_dict
569            sage: D = sage.misc.weak_dict.WeakValueDictionary()
570            sage: ZZ in D
571            False
572
573        One can set new items::
574
575            sage: D[ZZ] = QQ   # indirect doctest
576            sage: D[ZZ]
577            Rational Field
578            sage: len(D)
579            1
580            sage: ZZ in D
581            True
582
583       One can also override existing items::
584
585           sage: D[ZZ] = RLF
586           sage: ZZ in D
587           True
588           sage: D[ZZ]
589           Real Lazy Field
590           sage: len(D)
591           1
592
593        TESTS:
594
595        One may wonder whether it causes problems when garbage collection for
596        a previously existing item happens *after* overriding the item. The
597        example shows that it is not a problem::
598
599            sage: class Cycle:
600            ....:     def __init__(self):
601            ....:         self.selfref = self
602            sage: L = [Cycle() for _ in range(5)]
603            sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(L))
604            sage: len(D)
605            5
606            sage: import gc
607            sage: gc.disable()
608            sage: del L
609            sage: len(D)
610            5
611            sage: D[2] = ZZ
612            sage: len(D)
613            5
614            sage: gc.enable()
615            sage: _ = gc.collect()
616            sage: len(D)
617            1
618            sage: D.items()
619            [(2, Integer Ring)]
620
621        """
622        PyDict_SetItem(self,k,KeyedRef(v,self.callback,PyObject_Hash(k)))
623
624    #def __delitem__(self, k):
625    #we don't really have to override this method.
626   
627    def pop(self, k):
628        """
629        Return the value for a given key, and delete it from the dictionary.
630
631        EXAMPLES::
632
633            sage: import sage.misc.weak_dict
634            sage: L = [GF(p) for p in prime_range(10^3)]
635            sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(L))
636            sage: 20 in D
637            True
638            sage: D.pop(20)
639            Finite Field of size 73
640            sage: 20 in D
641            False
642            sage: D.pop(20)
643            Traceback (most recent call last):
644            ...
645            KeyError: 20
646
647        """
648        cdef PyObject* wr = PyDict_GetItem(self, k)
649        if wr == NULL:
650            raise KeyError(k)
651        cdef PyObject* outref = PyWeakref_GetObject(wr)
652        if outref == Py_None:
653            raise KeyError(k)
654        #we turn the output into a new reference before deleting the item,
655        #because the deletion can cause any kind of havoc.
656        out = <object>outref
657        del self[k]
658        return out
659
660    def popitem(self):
661        """
662        Return and delete some item from the dictionary.
663
664        EXAMPLES::
665
666            sage: import sage.misc.weak_dict
667            sage: D = sage.misc.weak_dict.WeakValueDictionary()
668            sage: D[1] = ZZ
669
670        The dictionary only contains a single item, hence, it is clear which
671        one will be returned::
672
673            sage: D.popitem()
674            (1, Integer Ring)
675
676        Now, the dictionary is empty, and hence the next attempt to pop an
677        item will fail with a ``KeyError``::
678
679            sage: D.popitem()
680            Traceback (most recent call last):
681            ...
682            KeyError: 'popitem(): weak value dictionary is empty'
683
684        """
685        for k,v in self.iteritems():
686            del self[k]
687            return k, v
688        raise KeyError('popitem(): weak value dictionary is empty')
689
690    def get(self, k, d=None):
691        """
692        Return the stored value for a key, or a default value for unkown keys.
693
694        The default value defaults to None.
695
696        EXAMPLES::
697
698            sage: import sage.misc.weak_dict
699            sage: L = [GF(p) for p in prime_range(10^3)]
700            sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(L))
701            sage: 100 in D
702            True
703            sage: 200 in D
704            False
705            sage: D.get(100, "not found")
706            Finite Field of size 547
707            sage: D.get(200, "not found")
708            'not found'
709            sage: D.get(200) is None
710            True
711
712        """
713        cdef PyObject * wr = PyDict_GetItem(self, k)
714        if wr == NULL:
715            return d
716        out = PyWeakref_GetObject(wr)
717        if out == Py_None:
718            return d
719        else:
720            return <object>out
721
722    def __getitem__(self, k):
723        """
724        TESTS::
725
726            sage: import sage.misc.weak_dict
727            sage: D = sage.misc.weak_dict.WeakValueDictionary()
728            sage: D[ZZ] = QQ
729            sage: D[QQ]
730            Traceback (most recent call last):
731            ...
732            KeyError: Rational Field
733            sage: D[ZZ]     # indirect doctest
734            Rational Field
735
736        As usual, the dictionary keys are compared by `==` and not by
737        identity::
738
739            sage: D[10] = ZZ
740            sage: D[int(10)]
741            Integer Ring
742
743        """
744        cdef PyObject* wr = PyDict_GetItem(self, k)
745        if wr == NULL:
746            raise KeyError(k)
747        out = PyWeakref_GetObject(wr)
748        if out == Py_None:
749            raise KeyError(k)
750        return <object>out
751
752    def has_key(self, k):
753        """
754        Returns True, if the key is known to the dictionary.
755
756        EXAMPLES::
757
758            sage: import sage.misc.weak_dict
759            sage: class Vals(object): pass
760            sage: L = [Vals() for _ in range(10)]
761            sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(L))
762            sage: D.has_key(3)
763            True
764
765        As usual, keys are compared by equality and not by identity::
766
767            sage: D.has_key(int(3))
768            True
769
770        This is a weak value dictionary. Hence, the existence of the
771        dictionary does not prevent the values from garbage collection,
772        thereby removing the corresponding key-value pairs::
773
774            sage: del L[3]
775            sage: D.has_key(3)
776            False
777
778        """
779        return k in self
780
781    def __contains__(self, k):
782        """
783        Containment in the set of keys.
784
785        TESTS::
786
787            sage: import sage.misc.weak_dict
788            sage: class Vals(object): pass
789            sage: L = [Vals() for _ in range(10)]
790            sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(L))
791            sage: 3 in D     # indirect doctest
792            True
793
794        As usual, keys are compared by equality and not by identity::
795
796            sage: int(3) in D
797            True
798
799        This is a weak value dictionary. Hence, the existence of the
800        dictionary does not prevent the values from garbage collection,
801        thereby removing the corresponding key-value pairs::
802
803            sage: del L[3]
804            sage: 3 in D
805            False
806
807        """
808        cdef PyObject* wr = PyDict_GetItem(self, k)
809        if wr==NULL:
810            return False
811        if PyWeakref_GetObject(wr)==Py_None:
812            return False
813        else:
814            return True
815
816    #def __len__(self):
817    #since GC is not deterministic, neither is the length of a WeakValueDictionary,
818    #so we might as well just return the normal dictionary length.
819
820    def iterkeys(self):
821        """
822        Iterate over the keys of this dictionary.
823
824        .. WARNING::
825
826            Iteration is unsafe, if the length of the dictionary changes
827            during the iteration! This can also happen by garbage collection.
828
829        EXAMPLES::
830
831            sage: import sage.misc.weak_dict
832            sage: class Vals(object): pass
833            sage: L = [Vals() for _ in range(10)]
834            sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(L))
835            sage: del L[4]
836
837        One item got deleted from the list ``L`` and hence the corresponding
838        item in the dictionary got deleted as well. Therefore, the
839        corresponding key 4 is missing in the list of keys::
840
841            sage: list(sorted(D.iterkeys()))
842            [0, 1, 2, 3, 5, 6, 7, 8, 9]
843
844        """
845        cdef PyObject *key, *wr
846        cdef Py_ssize_t pos = 0
847        with self._iteration_context:
848            while PyDict_Next(self, &pos, &key, &wr):
849                #this check doesn't really say anything: by the time
850                #the key makes it to the customer, it may have already turned
851                #invalid. It's a cheap check, though.
852                if PyWeakref_GetObject(wr)!=Py_None:
853                    yield <object>key
854
855    def __iter__(self):
856        """
857        Iterate over the keys of this dictionary.
858
859        .. WARNING::
860
861            Iteration is unsafe, if the length of the dictionary changes
862            during the iteration! This can also happen by garbage collection.
863
864        EXAMPLES::
865
866            sage: import sage.misc.weak_dict
867            sage: class Vals(object): pass
868            sage: L = [Vals() for _ in range(10)]
869            sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(L))
870            sage: del L[4]
871
872        One item got deleted from the list ``L`` and hence the corresponding
873        item in the dictionary got deleted as well. Therefore, the
874        corresponding key 4 is missing in the list of keys::
875
876            sage: sorted(list(D))    # indirect doctest
877            [0, 1, 2, 3, 5, 6, 7, 8, 9]
878
879        """
880        return self.iterkeys()
881
882    def keys(self):
883        """
884        The list of keys.
885
886        EXAMPLES::
887
888            sage: import sage.misc.weak_dict
889            sage: class Vals(object): pass
890            sage: L = [Vals() for _ in range(10)]
891            sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(L))
892            sage: del L[4]
893
894        One item got deleted from the list ``L`` and hence the corresponding
895        item in the dictionary got deleted as well. Therefore, the
896        corresponding key 4 is missing in the list of keys::
897
898            sage: sorted(D.keys())
899            [0, 1, 2, 3, 5, 6, 7, 8, 9]
900
901        """
902        return list(self.iterkeys())
903
904    def itervalues(self):
905        """
906        Iterate over the values of this dictionary.
907
908        .. WARNING::
909
910            Iteration is unsafe, if the length of the dictionary changes
911            during the iteration! This can also happen by garbage collection.
912
913        EXAMPLES::
914
915            sage: import sage.misc.weak_dict
916            sage: class Vals:
917            ....:     def __init__(self, n):
918            ....:         self.n = n
919            ....:     def __repr__(self):
920            ....:         return "<%s>"%self.n
921            ....:     def __cmp__(self, other):
922            ....:         c = cmp(type(self),type(other))
923            ....:         if c:
924            ....:             return c
925            ....:         return cmp(self.n,other.n)
926            sage: L = [Vals(n) for n in range(10)]
927            sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(L))
928
929        We delete one item from ``D`` and we delete one item from the list
930        ``L``. The latter implies that the corresponding item from ``D`` gets
931        deleted as well. Hence, there remain eight values::
932
933            sage: del D[2]
934            sage: del L[5]
935            sage: for v in sorted(D.itervalues()):
936            ....:     print v
937            <0>
938            <1>
939            <3>
940            <4>
941            <6>
942            <7>
943            <8>
944            <9>
945
946        """
947        cdef PyObject *key, *wr
948        cdef Py_ssize_t pos = 0
949        with self._iteration_context:
950            while PyDict_Next(self, &pos, &key, &wr):
951                out = PyWeakref_GetObject(wr)
952                if out != Py_None:
953                    yield <object>out
954
955    def values(self):
956        """
957        Return the list of values.
958
959        EXAMPLES::
960
961            sage: import sage.misc.weak_dict
962            sage: class Vals:
963            ....:     def __init__(self, n):
964            ....:         self.n = n
965            ....:     def __repr__(self):
966            ....:         return "<%s>"%self.n
967            ....:     def __cmp__(self, other):
968            ....:         c = cmp(type(self),type(other))
969            ....:         if c:
970            ....:             return c
971            ....:         return cmp(self.n,other.n)
972            sage: L = [Vals(n) for n in range(10)]
973            sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(L))
974
975        We delete one item from ``D`` and we delete one item from the list
976        ``L``. The latter implies that the corresponding item from ``D`` gets
977        deleted as well. Hence, there remain eight values::
978
979            sage: del D[2]
980            sage: del L[5]
981            sage: sorted(D.values())
982            [<0>, <1>, <3>, <4>, <6>, <7>, <8>, <9>]
983
984        """
985        return list(self.itervalues())
986
987    def iteritems(self):
988        """
989        Iterate over the items of this dictionary.
990
991        .. WARNING::
992
993            Iteration is unsafe, if the length of the dictionary changes
994            during the iteration! This can also happen by garbage collection.
995
996        EXAMPLES::
997
998            sage: import sage.misc.weak_dict
999            sage: class Vals:
1000            ....:     def __init__(self, n):
1001            ....:         self.n = n
1002            ....:     def __repr__(self):
1003            ....:         return "<%s>"%self.n
1004            ....:     def __cmp__(self, other):
1005            ....:         c = cmp(type(self),type(other))
1006            ....:         if c:
1007            ....:             return c
1008            ....:         return cmp(self.n,other.n)
1009            sage: class Keys(object):
1010            ....:     def __init__(self, n):
1011            ....:         self.n = n
1012            ....:     def __hash__(self):
1013            ....:         if self.n%2:
1014            ....:             return 5
1015            ....:         return 3
1016            ....:     def __repr__(self):
1017            ....:         return "[%s]"%self.n
1018            ....:     def __cmp__(self, other):
1019            ....:         c = cmp(type(self),type(other))
1020            ....:         if c:
1021            ....:             return c
1022            ....:         return cmp(self.n,other.n)
1023            sage: L = [(Keys(n), Vals(n)) for n in range(10)]
1024            sage: D = sage.misc.weak_dict.WeakValueDictionary(L)
1025
1026        We remove one dictionary item directly. Another item is removed by
1027        means of garbage collection. By consequence, there remain eight
1028        items in the dictionary::
1029
1030            sage: del D[Keys(2)]
1031            sage: del L[5]
1032            sage: for k,v in sorted(D.iteritems()):
1033            ....:     print k, v
1034            [0] <0>
1035            [1] <1>
1036            [3] <3>
1037            [4] <4>
1038            [6] <6>
1039            [7] <7>
1040            [8] <8>
1041            [9] <9>
1042
1043        """
1044        cdef PyObject *key, *wr
1045        cdef Py_ssize_t pos = 0
1046        with self._iteration_context:
1047            while PyDict_Next(self, &pos, &key, &wr):
1048                out = PyWeakref_GetObject(wr)
1049                if out != Py_None:
1050                    yield <object>key, <object>out
1051
1052    def items(self):
1053        """
1054        The key-value pairs of this dictionary.
1055
1056        EXAMPLES::
1057
1058            sage: import sage.misc.weak_dict
1059            sage: class Vals:
1060            ....:     def __init__(self, n):
1061            ....:         self.n = n
1062            ....:     def __repr__(self):
1063            ....:         return "<%s>"%self.n
1064            ....:     def __cmp__(self, other):
1065            ....:         c = cmp(type(self),type(other))
1066            ....:         if c:
1067            ....:             return c
1068            ....:         return cmp(self.n,other.n)
1069            sage: class Keys(object):
1070            ....:     def __init__(self, n):
1071            ....:         self.n = n
1072            ....:     def __hash__(self):
1073            ....:         if self.n%2:
1074            ....:             return 5
1075            ....:         return 3
1076            ....:     def __repr__(self):
1077            ....:         return "[%s]"%self.n
1078            ....:     def __cmp__(self, other):
1079            ....:         c = cmp(type(self),type(other))
1080            ....:         if c:
1081            ....:             return c
1082            ....:         return cmp(self.n,other.n)
1083            sage: L = [(Keys(n), Vals(n)) for n in range(10)]
1084            sage: D = sage.misc.weak_dict.WeakValueDictionary(L)
1085
1086        We remove one dictionary item directly. Another item is removed by
1087        means of garbage collection. By consequence, there remain eight
1088        items in the dictionary::
1089
1090            sage: del D[Keys(2)]
1091            sage: del L[5]
1092            sage: sorted(D.items())
1093            [([0], <0>),
1094             ([1], <1>),
1095             ([3], <3>),
1096             ([4], <4>),
1097             ([6], <6>),
1098             ([7], <7>),
1099             ([8], <8>),
1100             ([9], <9>)]
1101
1102        """
1103        return list(self.iteritems())
1104
1105cdef class _IterationContext:
1106    """
1107    An iterator that protects :class:`WeakValueDictionary` from some negative
1108    effects of deletions due to garbage collection during iteration.
1109    It's still not safe to explicitly mutate a dictionary during iteration,
1110    though. Doing so is a bug in a program (since iteration order is
1111    non-deterministic the results are not well-defined)
1112
1113    This is implemented by only marking entries for deletion if their values
1114    become deallocated while an iterator is active. Once the iterator finishes,
1115    the keys are deallocated. Note that because the weakrefs will be dead, the
1116    keys in question do not appear to be in the dictionary anymore::
1117   
1118        sage: from sage.misc.weak_dict import WeakValueDictionary
1119        sage: K = [frozenset([i]) for i in range(11)]
1120        sage: D = WeakValueDictionary((K[i],K[i+1]) for i in range(10))
1121        sage: k = K[10]
1122        sage: del K
1123        sage: i = D.iterkeys(); d = i.next(); del d
1124        sage: len(D.keys())
1125        10
1126        sage: del k
1127
1128    At this point, the entry for `k` appears to have disappeared out of `D`,
1129    but a reference to `k` is still kept, so the other entries in `D` survive::
1130
1131        sage: len(D.keys())
1132        9
1133   
1134    if we delete the iterator `i` the reference to `k` is dropped, and as a result
1135    all entries will disappear from `D`::
1136
1137        sage: del i
1138        sage: len(D.keys())
1139        0
1140   
1141    """
1142    cdef WeakValueDictionary Dict
1143    def __init__(self, Dict):
1144        """
1145        INPUT:
1146
1147        A :class:`WeakValueDictionary`
1148
1149        This context manager is used during iteration over the given
1150        dictionary, and prevents negative side-effects of item deletions
1151        during iteration.
1152
1153        EXAMPLES::
1154
1155            sage: from sage.misc.weak_dict import WeakValueDictionary
1156            sage: K = [frozenset([i]) for i in range(11)]
1157            sage: D = WeakValueDictionary((K[i],K[i+1]) for i in range(10))
1158            sage: k = K[10]
1159            sage: del K
1160            sage: i = D.iterkeys(); d = i.next(); del d
1161            sage: len(D.keys())
1162            10
1163            sage: del k
1164            sage: len(D.keys())
1165            9
1166            sage: del i
1167            sage: len(D.keys())
1168            0
1169
1170        """
1171        self.Dict = Dict
1172
1173    def __enter__(self):
1174        """
1175        Make sure that items of a weak value dictionary are not actually
1176        deleted, but only *marked* for deletion.
1177
1178        TESTS::
1179
1180            sage: from sage.misc.weak_dict import WeakValueDictionary
1181            sage: K = [frozenset([i]) for i in range(11)]
1182            sage: D = WeakValueDictionary((K[i],K[i+1]) for i in range(10))
1183            sage: k = K[10]
1184            sage: del K
1185            sage: i = D.iterkeys(); d = i.next(); del d
1186            sage: len(D.keys())
1187            10
1188            sage: del k
1189            sage: len(D.keys())
1190            9
1191            sage: del i
1192            sage: len(D.keys())
1193            0
1194
1195        """
1196        self.Dict._guard_level += 1
1197        return self
1198
1199    def __exit__(self, exc_type, exc_val, exc_tb):
1200        """
1201        Make sure that all items of a weak value dictionary that are marked
1202        for deletion are actually deleted, as soon as there is no iteration
1203        over the dictionary.
1204
1205        TESTS::
1206
1207            sage: from sage.misc.weak_dict import WeakValueDictionary
1208            sage: K = [frozenset([i]) for i in range(11)]
1209            sage: D = WeakValueDictionary((K[i],K[i+1]) for i in range(10))
1210            sage: k = K[10]
1211            sage: del K
1212            sage: i = D.iterkeys(); d = i.next(); del d
1213            sage: len(D.keys())
1214            10
1215            sage: del k
1216            sage: len(D.keys())
1217            9
1218            sage: del i
1219            sage: len(D.keys())
1220            0
1221
1222       """
1223       # Propagate errors by returning "False"
1224        self.Dict._guard_level -= 1
1225        #when the guard_level drops to zero, we try to remove all the
1226        #pending removals. Note that this could trigger another iterator
1227        #to become active, in which case we should back off.
1228        while (not self.Dict._guard_level) and self.Dict._pending_removals:
1229            self.Dict.callback(self.Dict._pending_removals.pop())
1230        return False