#to build:
#python3 setup.py build_ext --inplace
"""
Fast and safe weak value dictionary
AUTHORS:
- Simon King (2013-10)
- Nils Bruin (2013-10, 2017-04)
- Julian Rueth (2014-03-16): improved handling of unhashable objects
Python's :mod:`weakref` module provides
:class:`~weakref.WeakValueDictionary`. This behaves similar to a dictionary,
but it does not prevent its values from garbage collection. Hence, it stores
the values by weak references with callback functions: The callback function
deletes a key-value pair from the dictionary, as soon as the value becomes
subject to garbage collection.
However, a problem arises if hash and comparison of the key depend on the
value that is being garbage collected::
sage: import weakref
sage: class Vals(object): pass
sage: class Keys:
....: def __init__(self, val):
....: self.val = weakref.ref(val)
....: def __hash__(self):
....: return hash(self.val())
....: def __eq__(self, other):
....: return self.val() == other.val()
....: def __ne__(self, other):
....: return self.val() != other.val()
sage: ValList = [Vals() for _ in range(10)]
sage: D = weakref.WeakValueDictionary()
sage: for v in ValList:
....: D[Keys(v)] = v
sage: len(D)
10
sage: del ValList, v
Exception KeyError: (<__main__.Keys instance at ...>,) in ignored
Exception KeyError: (<__main__.Keys instance at ...>,) in ignored
Exception KeyError: (<__main__.Keys instance at ...>,) in ignored
Exception KeyError: (<__main__.Keys instance at ...>,) in ignored
...
sage: len(D) > 1
True
Hence, there are scary error messages, and moreover the defunct items have not
been removed from the dictionary.
Therefore, Sage provides an alternative implementation
:class:`sage.misc.weak_dict.WeakValueDictionary`, using a callback that
removes the defunct item not based on hash and equality check of the key (this
is what fails in the example above), but based on comparison by identity. This
is possible, since references with callback function are distinct even if they
point to the same object. Hence, even if the same object ``O`` occurs as value
for several keys, each reference to ``O`` corresponds to a unique key. We see
no error messages, and the items get correctly removed::
sage: ValList = [Vals() for _ in range(10)]
sage: import sage.misc.weak_dict
sage: D = sage.misc.weak_dict.WeakValueDictionary()
sage: for v in ValList:
....: D[Keys(v)] = v
sage: len(D)
10
sage: del ValList
sage: len(D)
1
sage: del v
sage: len(D)
0
Another problem arises when iterating over the items of a dictionary: If
garbage collection occurs during iteration, then the content of the dictionary
changes, and the iteration breaks for :class:`weakref.WeakValueDictionary`::
sage: class Cycle:
....: def __init__(self):
....: self.selfref = self
sage: C = [Cycle() for n in range(10)]
sage: D = weakref.WeakValueDictionary(enumerate(C))
sage: import gc
sage: gc.disable()
sage: del C[:5]
sage: len(D)
10
With :class:`~sage.misc.weak_dict.WeakValueDictionary`, the behaviour is
safer. Note that iteration over a WeakValueDictionary is non-deterministic,
since the lifetime of values (and hence the presence of keys) in the dictionary
may depend on when garbage collection occurs. The method implemented here
will at least postpone dictionary mutations due to garbage collection callbacks.
This means that as long as there is at least one iterator active on a dictionary,
none of its keys will be deallocated (which could have side-effects).
Which entries are returned is of course still dependent on when garbage
collection occurs. Note that when a key gets returned as "present" in the
dictionary, there is no guarantee one can actually retrieve its value: it may
have been garbage collected in the mean time.
Note that Sage's weak value dictionary is actually an instance of
:class:`dict`, in contrast to :mod:`weakref`'s weak value dictionary::
sage: issubclass(weakref.WeakValueDictionary, dict)
False
sage: issubclass(sage.misc.weak_dict.WeakValueDictionary, dict)
True
See :trac:`13394` for a discussion of some of the design considerations.
"""
########################################################################
# Copyright (C) 2013 Simon King
# Nils Bruin
# Julian Rueth
#
# Distributed under the terms of the GNU General Public License (GPL)
#
# http://www.gnu.org/licenses/
########################################################################
from __future__ import print_function
import weakref
from weakref import KeyedRef
from copy import deepcopy
from cpython.dict cimport *
from cpython.weakref cimport PyWeakref_NewRef
from cpython.list cimport PyList_New
from cpython.object cimport PyObject_Hash
from cpython cimport Py_XINCREF, Py_XDECREF
from libc.stdint cimport int8_t,int16_t,int32_t,int64_t
cdef extern from "Python.h":
ctypedef struct PyDictEntry:
Py_ssize_t me_hash
PyObject* me_key
PyObject* me_value
ctypedef struct PyDictObject:
Py_ssize_t ma_used
PyDictKeysObject * ma_keys
PyObject ** ma_values
PyObject* Py_None
#we need this redefinition because we want to be able to call
#PyWeakref_GetObject with borrowed references. This is the recommended
#strategy according to Cython/Includes/cpython/__init__.pxd
PyObject* PyWeakref_GetObject(PyObject * wr)
int PyList_SetItem(object list, Py_ssize_t index, PyObject * item) except -1
PyObject* PyDict_GetItemWithError(dict op, object key) except? NULL
int PyWeakref_Check(PyObject * ob)
ctypedef struct PyDictKeysObject
####
#definitions replicated from CPython's Objects/dict-common.h
#(this file is not exported fron CPython, so we need to be
#careful the definitions are in step with what happens there.
ctypedef union IndexBlock:
int8_t as_1[8]
int16_t as_2[4]
int32_t as_4[2]
int64_t as_8[1]
ctypedef struct MyPyDictKeysObject:
Py_ssize_t dk_refcnt
Py_ssize_t dk_size
Py_ssize_t (*dk_lookup)(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject ** value_addr, Py_ssize_t *hashpos)
Py_ssize_t dk_usable
Py_ssize_t dk_nentries
IndexBlock dk_indices
ctypedef struct PyDictKeyEntry:
Py_hash_t me_hash
PyObject * me_key
PyObject * me_value
cdef Py_ssize_t DKIX_EMPTY = -1
cdef Py_ssize_t DKIX_DUMMY = -2
cdef Py_ssize_t DKIX_ERROR = -3
#####
#These routines are copied from CPython's Object/dictobject.c
#in order to access PyDictKeysObject fields
cdef inline int DK_IXSIZE(MyPyDictKeysObject *keys):
cdef Py_ssize_t s = keys.dk_size
cdef int i
if s <= 0xff:
i = 1
elif s <= 0xffff:
i = 2
elif s <= 0xffffffff:
i = 4
else:
i = 8
return i
cdef inline PyDictKeyEntry * DK_ENTRIES(MyPyDictKeysObject *keys):
return &(keys.dk_indices.as_1[keys.dk_size * DK_IXSIZE(keys)])
cdef inline Py_ssize_t dk_get_index(MyPyDictKeysObject *keys, Py_ssize_t i):
cdef Py_ssize_t s = keys.dk_size
cdef Py_ssize_t ix
if s <= 0xff:
ix = keys.dk_indices.as_1[i]
elif s <= 0xffff:
ix = keys.dk_indices.as_2[i]
elif s <= 0xffffffff:
ix = keys.dk_indices.as_4[i]
else:
ix = keys.dk_indices.as_8[i]
return ix
cdef inline dk_set_index(MyPyDictKeysObject *keys, Py_ssize_t i, Py_ssize_t ix):
cdef Py_ssize_t s = keys.dk_size
if s <= 0xff:
keys.dk_indices.as_1[i] = ix
elif s <= 0xffff:
keys.dk_indices.as_2[i] = ix
elif s <= 0xffffffff:
keys.dk_indices.as_4[i] = ix
else:
keys.dk_indices.as_8[i] = ix
return ix
####
class NullClass(object):
def __repr__(self):
return "NULL"
PyNULL=NullClass()
cdef void * lookdict
cdef void * DK_LOOKUP(PyDictObject *mp):
return (((mp.ma_keys)).dk_lookup)
def init_lookdict():
global lookdict
cdef dict D={}
#this should trigger the initialization of the general
#lookup function on the dict.
PyDict_GetItemWithError(D,None)
#which we store in a global variable
lookdict=DK_LOOKUP(D)
init_lookdict()
cpdef debug_dict(O):
cdef dO = O
cdef PyDictObject *mp = dO
cdef MyPyDictKeysObject *keys = mp.ma_keys
cdef PyDictKeyEntry* entries = DK_ENTRIES(keys)
indices=[dk_get_index(keys,i) for i in range(keys.dk_size)]
L=[]
for i in range(keys.dk_nentries):
if entries[i].me_key == NULL:
kk = PyNULL
else:
kk = entries[i].me_key
if entries[i].me_value == NULL:
vv = PyNULL
else:
vv = entries[i].me_value
L.append( (kk,vv))
if mp.ma_values == NULL:
V = PyNULL
else:
V=[]
for i in range(keys.dk_nentries):
if mp.ma_values[i] == NULL:
V.append(PyNULL)
else:
V.append(mp.ma_values[i])
return [mp.ma_used,[keys.dk_refcnt,keys.dk_size,(keys.dk_lookup),keys.dk_usable,keys.dk_nentries,indices,L],V]
cdef ensure_allows_deletions(PyDictObject *mp):
if DK_LOOKUP(mp) != lookdict:
#on normal dictionaries (non-split table), looking up a key
#that is not a unicode object triggers installation of the
#general lookup function (which can deal with DKIX_DUMMY)
PyDict_GetItemWithError(mp,None)
#this can actually fail if mp is a dictionary with split table
assert DK_LOOKUP(mp) == lookdict
cdef del_dictitem_by_exact_value(PyDictObject *mp, PyObject *value, Py_hash_t hash):
"""
This is used in callbacks for the weak values of :class:`WeakValueDictionary`.
INPUT:
- ``PyDictObject *mp`` -- pointer to a dict
- ``PyObject *value`` -- pointer to a value of the dictionary
- ``Py_hash_t hash`` -- hash of the key by which the value is stored in the dict
The hash bucket determined by the given hash is searched for the item
containing the given value. If this item cannot be found, the function is
silently returning. Otherwise, the item is removed from the dict.
TESTS:
The following is an indirect doctest, as discussed on :trac:`13394`.
::
sage: from sage.misc.weak_dict import WeakValueDictionary
sage: V = [set(range(n)) for n in range(5)]
sage: D = WeakValueDictionary(enumerate(V))
The line ``V[k] = None`` triggers execution of the callback functions of
the dict values. However, the actual deletion is postponed till after the
iteration over the dictionary has finished. Hence, when the callbacks are
executed, the values which the callback belongs to has already been
overridded by a new value. Therefore, the callback does not delete the
item::
sage: for k in D: # indirect doctest
....: V[k] = None
....: D[k] = ZZ
sage: len(D)
5
sage: D[1]
Integer Ring
TESTS:
The following shows that the deletion of deeply nested structures does not
result in an error, by :trac:`15506`::
sage: class A: pass
sage: a = A(); prev = a
sage: M = WeakValueDictionary()
sage: for i in range(10^3+10): newA = A(); M[newA] = prev; prev = newA
sage: del a
"""
cdef size_t i
cdef MyPyDictKeysObject * keys = (mp.ma_keys)
cdef size_t perturb
cdef size_t mask = keys.dk_size-1
cdef PyDictKeyEntry *entries, *ep
entries = DK_ENTRIES(keys)
if mp.ma_values != NULL:
print ("del_dictitem_by_exact_value cannot be applied to a shared key dict")
return
i = hash & mask
ix = dk_get_index(keys, i)
if ix == DKIX_EMPTY:
# key not found
return
ep = &(entries[ix])
perturb = hash
while (ep.me_value != value or ep.me_hash != hash):
perturb = perturb >> 5 #this is the value of PERTURB_SHIFT
i = ((i << 2) + i + perturb +1) & mask
ix = dk_get_index(keys, i)
if ix == DKIX_EMPTY:
# key not found
return
ep = &(entries[ix])
ensure_allows_deletes(mp)
T=PyList_New(2)
PyList_SetItem(T, 0, ep.me_key)
PyList_SetItem(T, 1, ep.me_value)
ep.me_key = NULL
ep.me_value = NULL
mp.ma_used -= 1
dk_set_index(keys, i, DKIX_DUMMY)
#We have transferred the to-be-deleted references to the list T
#we now delete the list so that the actual decref happens through a
#deallocation routine that uses the Python Trashcan macros to
#avoid stack overflow in deleting deep structures.
del T
def test_del_dictitem_by_exact_value(D, value, h):
"""
This function helps testing some cdef function used to delete dictionary items.
INPUT:
- ``D`` -- a Python ````.
- ``value`` -- an object that is value ``D``.
- ``h`` -- the hash of the key under which to find ``value`` in ``D``.
The underlying cdef function deletes an item from ``D`` that is in the
hash bucket determined by ``h`` and whose value is identic with
``value``. Of course, this only makes sense if the pairs ``(h, value)``
corresponding to items in ``D`` are pair-wise distinct.
If a matching item can not be found, the function does nothing and
silently returns.
TESTS:
See :trac:`13394` for a discussion.
::
sage: from sage.misc.weak_dict import test_del_dictitem_by_exact_value
sage: B=1000
sage: L=list(range(B))
sage: D1=dict()
sage: D2=dict()
sage: for i in range(100000): # long time
....: ki=L[floor(random()*B)]
....: vi=L[floor(random()*B)]
....: D1[ki]=vi
....: D2[ki]=vi
....: ko=L[floor(random()*B)]
....: if ko in D1:
....: vo=D1[ko]
....: del D1[ko]
....: test_del_dictitem_by_exact_value(D2,vo,hash(ko))
....: assert D1 == D2
No action is taken if the item prescribed by key hash and value does not
exist in the dictionary::
sage: D = {1: ZZ}
sage: test_del_dictitem_by_exact_value(D, ZZ, 2)
sage: D
{1: Integer Ring}
sage: test_del_dictitem_by_exact_value(D, QQ, 1)
sage: D
{1: Integer Ring}
"""
return del_dictitem_by_exact_value(D, value, h)
cdef class WeakValueDictEraser:
"""
Erases items from a :class:`sage.misc.weak_dict.WeakValueDictionary` when
a weak reference becomes invalid.
This is of internal use only. Instances of this class will be passed as a
callback function when creating a weak reference.
EXAMPLES::
sage: from sage.misc.weak_dict import WeakValueDictionary
sage: v = frozenset([1])
sage: D = WeakValueDictionary({1 : v})
sage: len(D)
1
sage: del v
sage: len(D)
0
AUTHOR:
- Nils Bruin (2013-11)
"""
cdef D
def __init__(self, D):
"""
INPUT:
A :class:`sage.misc.weak_dict.WeakValueDictionary`.
EXAMPLES::
sage: v = frozenset([1])
sage: D = sage.misc.weak_dict.WeakValueDictionary({ 1 : v })
sage: len(D)
1
sage: del v
sage: len(D) #indirect doctest
0
"""
self.D = PyWeakref_NewRef(D, None)
def __call__(self, r):
"""
INPUT:
A weak reference with key.
When this is called with a weak reference ``r``, then an entry from the
dictionary pointed to by ``self.D`` is removed that has ``r`` as a value
identically, stored under a key with hash ``r.key``. If no such key
exists, or if the dictionary itself does not exist any more, then nothing
happens.
If the dictionary has an iterator active on it then the object is
queued for removal when all iterators have concluded.
EXAMPLES::
sage: v = frozenset([1])
sage: D = sage.misc.weak_dict.WeakValueDictionary({ 1 : v })
sage: len(D)
1
sage: del v
sage: len(D) #indirect doctest
0
"""
cdef WeakValueDictionary D = PyWeakref_GetObject( self.D)
if D is None:
return
#The situation is the following:
#in the underlying dictionary, we have stored a KeyedRef r
#under a key k. The attribute r.key is the hash of k.
if D._guard_level:
D._pending_removals.append(r)
else:
del_dictitem_by_exact_value(D, r, r.key)
cdef class WeakValueDictionary(dict):
"""
IMPLEMENTATION:
The :class:`WeakValueDictionary` inherits from :class:`dict`. In its
implementation, it stores weakrefs to the actual values under the keys.
All access routines are wrapped to transparently place and remove these
weakrefs.
NOTE:
In contrast to :class:`weakref.WeakValueDictionary` in Python's
:mod:`weakref` module, the callback does not need to assume that the
dictionary key is a valid Python object when it is called. There is no
need to compute the hash or compare the dictionary keys. This is why
the example below would not work with
:class:`weakref.WeakValueDictionary`, but does work with
:class:`sage.misc.weak_dict.WeakValueDictionary`.
EXAMPLES::
sage: import weakref
sage: class Vals(object): pass
sage: class Keys:
....: def __init__(self, val):
....: self.val = weakref.ref(val)
....: def __hash__(self):
....: return hash(self.val())
....: def __eq__(self, other):
....: return self.val() == other.val()
....: def __ne__(self, other):
....: return self.val() != other.val()
sage: ValList = [Vals() for _ in range(10)]
sage: import sage.misc.weak_dict
sage: D = sage.misc.weak_dict.WeakValueDictionary()
sage: for v in ValList:
....: D[Keys(v)] = v
sage: len(D)
10
sage: del ValList
sage: len(D)
1
sage: del v
sage: len(D)
0
TESTS:
The following reflects the behaviour of the callback on weak dict values,
as discussed on :trac:`13394`. ::
sage: from sage.misc.weak_dict import WeakValueDictionary
sage: V = [set(range(n)) for n in range(5)]
sage: D = WeakValueDictionary(enumerate(V))
The line ``V[k] = None`` triggers execution of the callback functions of
the dictionary values. However, the actual deletion is postponed till
after the iteration over the dictionary has finished. Hence, when the
callbacks are executed, the values which the callback belongs to has
already been overridded by a new value. Therefore, the callback does not
delete the item::
sage: for k in D: # indirect doctest
....: V[k] = None
....: D[k] = ZZ
sage: len(D)
5
sage: D[1]
Integer Ring
The following is a stress test for weak value dictionaries::
sage: class C(object):
....: def __init__(self, n):
....: self.n = n
....: def __lt__(self, other):
....: return self.n < other.n
....: def __eq__(self, other):
....: return self.n == other.n
....: def __ne__(self, other):
....: return self.val() != other.val()
sage: B = 100
sage: L = [None]*B
sage: D1 = WeakValueDictionary()
sage: D2 = WeakValueDictionary()
sage: for i in range(10000):
....: ki = floor(random()*B)
....: vi = C(floor(random()*B))
....: D1[ki] = vi
....: D2[ki] = vi
....: L[ki] = vi
....: del vi
....: ko = floor(random()*B)
....: if ko in D1:
....: del D1[ko]
....: L[ko] = None
....: assert D1 == D2
"""
def __init__(self, data=()):
"""
Create a :class:`WeakValueDictionary` with given initial data.
INPUT:
Optional iterable of key-value pairs
EXAMPLES::
sage: L = [(p,GF(p)) for p in prime_range(10)]
sage: import sage.misc.weak_dict
sage: D = sage.misc.weak_dict.WeakValueDictionary()
sage: len(D)
0
sage: D = sage.misc.weak_dict.WeakValueDictionary(L)
sage: len(D) == len(L)
True
"""
dict.__init__(self)
self.callback = WeakValueDictEraser(self)
self._guard_level = 0
self._pending_removals = []
try:
data=data.iteritems()
except AttributeError:
pass
for k,v in data:
self[k] = v
def __copy__(self):
"""
Return a copy of this weak dictionary.
EXAMPLES::
sage: import sage.misc.weak_dict
sage: D = sage.misc.weak_dict.WeakValueDictionary()
sage: D[1] = QQ
sage: D[2] = ZZ
sage: D[None] = CC
sage: E = copy(D) # indirect doctest
sage: set(E.items()) == set(D.items())
True
"""
return WeakValueDictionary(self.iteritems())
def __deepcopy__(self, memo):
"""
Return a copy of this dictionary using copies of the keys.
NOTE:
The values of the dictionary are not copied, since we can not copy the
external strong references to the values, which are decisive for
garbage collection.
EXAMPLES::
sage: class C(object): pass
sage: V = [C(),C()]
sage: D = sage.misc.weak_dict.WeakValueDictionary()
sage: D[C()] = V[0]
sage: D[C()] = V[1]
sage: E = deepcopy(D) # indirect doctest
The keys are copied (in this silly example, the copies of the keys are
actually not equal to the original keys)::
sage: set(E.keys()) == set(D.keys())
False
However, the values are not copied::
sage: set(E.values()) == set(D.values()) == set(V)
True
"""
out = WeakValueDictionary()
for k,v in self.iteritems():
out[deepcopy(k, memo)] = v
return out
def __repr__(self):
"""
EXAMPLES::
sage: import sage.misc.weak_dict
sage: repr(sage.misc.weak_dict.WeakValueDictionary([(1,ZZ),(2,QQ)])) # indirect doctest
''
"""
return "" % id(self)
def __str__(self):
"""
EXAMPLES::
sage: import sage.misc.weak_dict
sage: str(sage.misc.weak_dict.WeakValueDictionary([(1,ZZ),(2,QQ)])) # indirect doctest
''
"""
return "" % id(self)
def setdefault(self, k, default=None):
"""
Return the stored value for a given key; return and store a default
value if no previous value is stored.
EXAMPLES::
sage: import sage.misc.weak_dict
sage: L = [(p,GF(p)) for p in prime_range(10)]
sage: D = sage.misc.weak_dict.WeakValueDictionary(L)
sage: len(D)
4
The value for an existing key is returned and not overridden::
sage: D.setdefault(5, ZZ)
Finite Field of size 5
sage: D[5]
Finite Field of size 5
For a non-existing key, the default value is stored and returned::
sage: 4 in D
False
sage: D.setdefault(4, ZZ)
Integer Ring
sage: 4 in D
True
sage: D[4]
Integer Ring
sage: len(D)
5
TESTS:
Check that :trac:`15956` has been fixed, i.e., a ``TypeError`` is
raised for unhashable objects::
sage: D = sage.misc.weak_dict.WeakValueDictionary()
sage: D.setdefault(matrix([]),ZZ)
Traceback (most recent call last):
...
TypeError: mutable matrices are unhashable
"""
cdef PyObject* wr = PyDict_GetItemWithError(self, k)
if wr != NULL:
out = PyWeakref_GetObject(wr)
if out != Py_None:
return out
PyDict_SetItem(self,k,KeyedRef(default,self.callback,PyObject_Hash(k)))
return default
def __setitem__(self, k, v):
"""
EXAMPLES::
sage: import sage.misc.weak_dict
sage: D = sage.misc.weak_dict.WeakValueDictionary()
sage: ZZ in D
False
One can set new items::
sage: D[ZZ] = QQ # indirect doctest
sage: D[ZZ]
Rational Field
sage: len(D)
1
sage: ZZ in D
True
One can also override existing items::
sage: D[ZZ] = RLF
sage: ZZ in D
True
sage: D[ZZ]
Real Lazy Field
sage: len(D)
1
TESTS:
One may wonder whether it causes problems when garbage collection for
a previously existing item happens *after* overriding the item. The
example shows that it is not a problem::
sage: class Cycle:
....: def __init__(self):
....: self.selfref = self
sage: L = [Cycle() for _ in range(5)]
sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(L))
sage: len(D)
5
sage: import gc
sage: gc.disable()
sage: del L
sage: len(D)
5
sage: D[2] = ZZ
sage: len(D)
5
sage: gc.enable()
sage: _ = gc.collect()
sage: len(D)
1
sage: D.items()
[(2, Integer Ring)]
Check that :trac:`15956` has been fixed, i.e., a ``TypeError`` is
raised for unhashable objects::
sage: D = sage.misc.weak_dict.WeakValueDictionary()
sage: D[matrix([])] = ZZ
Traceback (most recent call last):
...
TypeError: mutable matrices are unhashable
"""
PyDict_SetItem(self,k,KeyedRef(v,self.callback,PyObject_Hash(k)))
#def __delitem__(self, k):
#we do not really have to override this method.
def pop(self, k):
"""
Return the value for a given key, and delete it from the dictionary.
EXAMPLES::
sage: import sage.misc.weak_dict
sage: L = [GF(p) for p in prime_range(10^3)]
sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(L))
sage: 20 in D
True
sage: D.pop(20)
Finite Field of size 73
sage: 20 in D
False
sage: D.pop(20)
Traceback (most recent call last):
...
KeyError: 20
TESTS:
Check that :trac:`15956` has been fixed, i.e., a ``TypeError`` is
raised for unhashable objects::
sage: D = sage.misc.weak_dict.WeakValueDictionary()
sage: D.pop(matrix([]))
Traceback (most recent call last):
...
TypeError: mutable matrices are unhashable
"""
cdef PyObject* wr = PyDict_GetItemWithError(self, k)
if wr == NULL:
raise KeyError(k)
cdef PyObject* outref = PyWeakref_GetObject(wr)
if outref == Py_None:
raise KeyError(k)
#we turn the output into a new reference before deleting the item,
#because the deletion can cause any kind of havoc.
out = outref
del self[k]
return out
def popitem(self):
"""
Return and delete some item from the dictionary.
EXAMPLES::
sage: import sage.misc.weak_dict
sage: D = sage.misc.weak_dict.WeakValueDictionary()
sage: D[1] = ZZ
The dictionary only contains a single item, hence, it is clear which
one will be returned::
sage: D.popitem()
(1, Integer Ring)
Now, the dictionary is empty, and hence the next attempt to pop an
item will fail with a ``KeyError``::
sage: D.popitem()
Traceback (most recent call last):
...
KeyError: 'popitem(): weak value dictionary is empty'
"""
for k,v in self.iteritems():
del self[k]
return k, v
raise KeyError('popitem(): weak value dictionary is empty')
def get(self, k, d=None):
"""
Return the stored value for a key, or a default value for unknown keys.
The default value defaults to ``None``.
EXAMPLES::
sage: import sage.misc.weak_dict
sage: L = [GF(p) for p in prime_range(10^3)]
sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(L))
sage: 100 in D
True
sage: 200 in D
False
sage: D.get(100, "not found")
Finite Field of size 547
sage: D.get(200, "not found")
'not found'
sage: D.get(200) is None
True
TESTS:
Check that :trac:`15956` has been fixed, i.e., a ``TypeError`` is
raised for unhashable objects::
sage: D = sage.misc.weak_dict.WeakValueDictionary()
sage: D.get(matrix([]))
Traceback (most recent call last):
...
TypeError: mutable matrices are unhashable
"""
cdef PyObject * wr = PyDict_GetItemWithError(self, k)
if wr == NULL:
return d
out = PyWeakref_GetObject(wr)
if out == Py_None:
return d
else:
return out
def __getitem__(self, k):
"""
TESTS::
sage: import sage.misc.weak_dict
sage: D = sage.misc.weak_dict.WeakValueDictionary()
sage: D[ZZ] = QQ
sage: D[QQ]
Traceback (most recent call last):
...
KeyError: Rational Field
sage: D[ZZ] # indirect doctest
Rational Field
As usual, the dictionary keys are compared by ``==`` and not by
identity::
sage: D[10] = ZZ
sage: D[int(10)]
Integer Ring
Check that :trac:`15956` has been fixed, i.e., a ``TypeError`` is
raised for unhashable objects::
sage: D = sage.misc.weak_dict.WeakValueDictionary()
sage: D[matrix([])]
Traceback (most recent call last):
...
TypeError: mutable matrices are unhashable
"""
cdef PyObject* wr = PyDict_GetItemWithError(self, k)
if wr == NULL:
raise KeyError(k)
out = PyWeakref_GetObject(wr)
if out == Py_None:
raise KeyError(k)
return out
def __contains__(self, k):
"""
Containment in the set of keys.
TESTS::
sage: import sage.misc.weak_dict
sage: class Vals(object): pass
sage: L = [Vals() for _ in range(10)]
sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(L))
sage: 3 in D # indirect doctest
True
As usual, keys are compared by equality and not by identity::
sage: int(3) in D
True
This is a weak value dictionary. Hence, the existence of the
dictionary does not prevent the values from garbage collection,
thereby removing the corresponding key-value pairs::
sage: del L[3]
sage: 3 in D
False
Check that :trac:`15956` has been fixed, i.e., a ``TypeError`` is
raised for unhashable objects::
sage: D = sage.misc.weak_dict.WeakValueDictionary()
sage: matrix([]) in D
Traceback (most recent call last):
...
TypeError: mutable matrices are unhashable
"""
cdef PyObject * value = PyDict_GetItemWithError(self, k)
if value == NULL:
return False
return PyWeakref_GetObject(value) != Py_None
def __iter__(self):
"""
Iterate over the keys of this dictionary.
.. WARNING::
Iteration is unsafe, if the length of the dictionary changes
during the iteration! This can also happen by garbage collection.
EXAMPLES::
sage: import sage.misc.weak_dict
sage: class Vals(object): pass
sage: L = [Vals() for _ in range(10)]
sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(L))
sage: del L[4]
One item got deleted from the list ``L`` and hence the corresponding
item in the dictionary got deleted as well. Therefore, the
corresponding key 4 is missing in the list of keys::
sage: list(sorted(D))
[0, 1, 2, 3, 5, 6, 7, 8, 9]
"""
cdef PyObject *key
cdef PyObject *wr
cdef Py_ssize_t pos = 0
try:
self._enter_iter()
while PyDict_Next(self, &pos, &key, &wr):
#this check does not really say anything: by the time
#the key makes it to the customer, it may have already turned
#invalid. It's a cheap check, though.
if PyWeakref_GetObject(wr)!=Py_None:
yield key
finally:
self._exit_iter()
def keys(self):
"""
The list of keys.
EXAMPLES::
sage: import sage.misc.weak_dict
sage: class Vals(object): pass
sage: L = [Vals() for _ in range(10)]
sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(L))
sage: del L[4]
One item got deleted from the list ``L`` and hence the corresponding
item in the dictionary got deleted as well. Therefore, the
corresponding key 4 is missing in the list of keys::
sage: sorted(D.keys())
[0, 1, 2, 3, 5, 6, 7, 8, 9]
"""
return list(iter(self))
def itervalues(self):
"""
Iterate over the values of this dictionary.
.. WARNING::
Iteration is unsafe, if the length of the dictionary changes
during the iteration! This can also happen by garbage collection.
EXAMPLES::
sage: import sage.misc.weak_dict
sage: class Vals:
....: def __init__(self, n):
....: self.n = n
....: def __repr__(self):
....: return "<%s>" % self.n
....: def __lt__(self, other):
....: return self.n < other.n
....: def __eq__(self, other):
....: return self.n == other.n
....: def __ne__(self, other):
....: return self.val() != other.val()
sage: L = [Vals(n) for n in range(10)]
sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(L))
We delete one item from ``D`` and we delete one item from the list
``L``. The latter implies that the corresponding item from ``D`` gets
deleted as well. Hence, there remain eight values::
sage: del D[2]
sage: del L[5]
sage: for v in sorted(D.itervalues()):
....: print(v)
<0>
<1>
<3>
<4>
<6>
<7>
<8>
<9>
"""
cdef PyObject *key
cdef PyObject *wr
cdef Py_ssize_t pos = 0
try:
self._enter_iter()
while PyDict_Next(self, &pos, &key, &wr):
out = PyWeakref_GetObject(wr)
if out != Py_None:
yield out
finally:
self._exit_iter()
def values(self):
"""
Return the list of values.
EXAMPLES::
sage: import sage.misc.weak_dict
sage: class Vals:
....: def __init__(self, n):
....: self.n = n
....: def __repr__(self):
....: return "<%s>" % self.n
....: def __lt__(self, other):
....: return self.n < other.n
....: def __eq__(self, other):
....: return self.n == other.n
....: def __ne__(self, other):
....: return self.val() != other.val()
sage: L = [Vals(n) for n in range(10)]
sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(L))
We delete one item from ``D`` and we delete one item from the list
``L``. The latter implies that the corresponding item from ``D`` gets
deleted as well. Hence, there remain eight values::
sage: del D[2]
sage: del L[5]
sage: sorted(D.values())
[<0>, <1>, <3>, <4>, <6>, <7>, <8>, <9>]
"""
return list(self.itervalues())
def iteritems(self):
"""
Iterate over the items of this dictionary.
.. WARNING::
Iteration is unsafe, if the length of the dictionary changes
during the iteration! This can also happen by garbage collection.
EXAMPLES::
sage: import sage.misc.weak_dict
sage: class Vals:
....: def __init__(self, n):
....: self.n = n
....: def __repr__(self):
....: return "<%s>" % self.n
....: def __lt__(self, other):
....: return self.n < other.n
....: def __eq__(self, other):
....: return self.n == other.n
....: def __ne__(self, other):
....: return self.val() != other.val()
sage: class Keys(object):
....: def __init__(self, n):
....: self.n = n
....: def __hash__(self):
....: if self.n%2:
....: return 5
....: return 3
....: def __repr__(self):
....: return "[%s]" % self.n
....: def __lt__(self, other):
....: return self.n < other.n
....: def __eq__(self, other):
....: return self.n == other.n
....: def __ne__(self, other):
....: return self.val() != other.val()
sage: L = [(Keys(n), Vals(n)) for n in range(10)]
sage: D = sage.misc.weak_dict.WeakValueDictionary(L)
We remove one dictionary item directly. Another item is removed by
means of garbage collection. By consequence, there remain eight
items in the dictionary::
sage: del D[Keys(2)]
sage: del L[5]
sage: for k,v in sorted(D.iteritems()):
....: print("{} {}".format(k, v))
[0] <0>
[1] <1>
[3] <3>
[4] <4>
[6] <6>
[7] <7>
[8] <8>
[9] <9>
"""
cdef PyObject *key
cdef PyObject *wr
cdef Py_ssize_t pos = 0
try:
self._enter_iter()
while PyDict_Next(self, &pos, &key, &wr):
out = PyWeakref_GetObject(wr)
if out != Py_None:
yield key, out
finally:
self._exit_iter()
def items(self):
"""
The key-value pairs of this dictionary.
EXAMPLES::
sage: import sage.misc.weak_dict
sage: class Vals:
....: def __init__(self, n):
....: self.n = n
....: def __repr__(self):
....: return "<%s>" % self.n
....: def __lt__(self, other):
....: return self.n < other.n
....: def __eq__(self, other):
....: return self.n == other.n
....: def __ne__(self, other):
....: return self.val() != other.val()
sage: class Keys(object):
....: def __init__(self, n):
....: self.n = n
....: def __hash__(self):
....: if self.n%2:
....: return 5
....: return 3
....: def __repr__(self):
....: return "[%s]" % self.n
....: def __lt__(self, other):
....: return self.n < other.n
....: def __eq__(self, other):
....: return self.n == other.n
....: def __ne__(self, other):
....: return self.val() != other.val()
sage: L = [(Keys(n), Vals(n)) for n in range(10)]
sage: D = sage.misc.weak_dict.WeakValueDictionary(L)
We remove one dictionary item directly. Another item is removed by
means of garbage collection. By consequence, there remain eight
items in the dictionary::
sage: del D[Keys(2)]
sage: del L[5]
sage: sorted(D.items())
[([0], <0>),
([1], <1>),
([3], <3>),
([4], <4>),
([6], <6>),
([7], <7>),
([8], <8>),
([9], <9>)]
"""
return list(self.iteritems())
cdef int _enter_iter(self) except -1:
"""
Make sure that items of a weak value dictionary are not actually
deleted, but only *marked* for deletion.
TESTS::
sage: from sage.misc.weak_dict import WeakValueDictionary
sage: K = [frozenset([i]) for i in range(11)]
sage: D = WeakValueDictionary((K[i],K[i+1]) for i in range(10))
sage: k = K[10]
sage: del K
sage: i = iter(D); d = next(i); del d
sage: len(D.keys())
10
sage: del k
sage: len(D.keys())
9
sage: del i
sage: len(D.keys())
0
"""
self._guard_level += 1
return 0
cdef int _exit_iter(self) except -1:
"""
Make sure that all items of a weak value dictionary that are marked
for deletion are actually deleted, as soon as there is no iteration
over the dictionary.
TESTS::
sage: from sage.misc.weak_dict import WeakValueDictionary
sage: K = [frozenset([i]) for i in range(11)]
sage: D = WeakValueDictionary((K[i],K[i+1]) for i in range(10))
sage: k = K[10]
sage: del K
sage: i = iter(D); d = next(i); del d
sage: len(D.keys())
10
sage: del k
sage: len(D.keys())
9
sage: del i
sage: len(D.keys())
0
"""
self._guard_level -= 1
#when the guard_level drops to zero, we try to remove all the
#pending removals. Note that this could trigger another iterator
#to become active, in which case we should back off.
while (not self._guard_level) and self._pending_removals:
self.callback(self._pending_removals.pop())
return 0