# Ticket #13394: weak_dict.pyx

File weak_dict.pyx, 39.5 KB (added by , 9 years ago) |
---|

Line | |
---|---|

1 | """ |

2 | Fast and safe weak value dictionary |

3 | |

4 | AUTHORS: |

5 | |

6 | - Simon King (2013-10) |

7 | - Nils Bruin (2013-10) |

8 | |

9 | Python's :mod:`weakref` module provides |

10 | :class:`~weakref.WeakValueDictionary`. This behaves similar to a dictionary, |

11 | but it does not prevent its values from garbage collection. Hence, it stores |

12 | the values by weak references with callback functions: The callback function |

13 | deletes a key-value pair from the dictionary, as soon as the value becomes |

14 | subject to garbage collection. |

15 | |

16 | However, a problem arises if hash and comparison of the key depend on the |

17 | value that is being garbage collected:: |

18 | |

19 | sage: import weakref |

20 | sage: class Vals(object): pass |

21 | sage: class Keys: |

22 | ....: def __init__(self, val): |

23 | ....: self.val = weakref.ref(val) |

24 | ....: def __hash__(self): |

25 | ....: return hash(self.val()) |

26 | ....: def __eq__(self, other): |

27 | ....: return self.val() == other.val() |

28 | sage: ValList = [Vals() for _ in range(10)] |

29 | sage: D = weakref.WeakValueDictionary() |

30 | sage: for v in ValList: |

31 | ....: D[Keys(v)] = v |

32 | sage: len(D) |

33 | 10 |

34 | sage: del ValList, v |

35 | Exception KeyError: (<__main__.Keys instance at ...>,) in <function remove at ...> ignored |

36 | Exception KeyError: (<__main__.Keys instance at ...>,) in <function remove at ...> ignored |

37 | Exception KeyError: (<__main__.Keys instance at ...>,) in <function remove at ...> ignored |

38 | Exception KeyError: (<__main__.Keys instance at ...>,) in <function remove at ...> ignored |

39 | ... |

40 | sage: len(D) > 1 |

41 | True |

42 | |

43 | Hence, there are scary error messages, and moreover the defunct items have not |

44 | been removed from the dictionary. |

45 | |

46 | Therefore, Sage provides an alternative implementation |

47 | :class:`sage.misc.weak_dict.WeakValueDictionary`, using a callback that |

48 | removes the defunct item not based on hash and equality check of the key (this |

49 | is what fails in the example above), but based on comparison by identity. This |

50 | is possible, since references with callback function are distinct even if they |

51 | point to the same object. Hence, even if the same object ``O`` occurs as value |

52 | for several keys, each reference to ``O`` corresponds to a unique key. We see |

53 | no error messages, and the items get correctly removed:: |

54 | |

55 | sage: ValList = [Vals() for _ in range(10)] |

56 | sage: import sage.misc.weak_dict |

57 | sage: D = sage.misc.weak_dict.WeakValueDictionary() |

58 | sage: for v in ValList: |

59 | ....: D[Keys(v)] = v |

60 | sage: len(D) |

61 | 10 |

62 | sage: del ValList |

63 | sage: len(D) |

64 | 1 |

65 | sage: del v |

66 | sage: len(D) |

67 | 0 |

68 | |

69 | Another problem arises when iterating over the items of a dictionary: If |

70 | garbage collection occurs during iteration, then the content of the dictionary |

71 | changes, and the iteration breaks for :class:`weakref.WeakValueDictionary`:: |

72 | |

73 | sage: class Cycle: |

74 | ....: def __init__(self): |

75 | ....: self.selfref = self |

76 | sage: C = [Cycle() for n in range(10)] |

77 | sage: D = weakref.WeakValueDictionary(enumerate(C)) |

78 | sage: import gc |

79 | sage: gc.disable() |

80 | sage: del C[:5] |

81 | sage: len(D) |

82 | 10 |

83 | sage: for k in D.iterkeys(): |

84 | ....: gc.enable() |

85 | ....: _ = gc.collect() |

86 | Traceback (most recent call last): |

87 | ... |

88 | RuntimeError: dictionary changed size during iteration |

89 | |

90 | With :class:`~sage.misc.weak_dict.WeakValueDictionary`, the behaviour is |

91 | safer. Note that iteration over a WeakValueDictionary is non-deterministic, |

92 | since the lifetime of values (and hence the presence of keys) in the dictionary |

93 | may depend on when garbage collection occurs. The method implemented here |

94 | will at least postpone dictionary mutations due to garbage collection callbacks. |

95 | This means that as long as there is at least one iterator active on a dictionary, |

96 | none of its keys will be deallocated (which could have side-effects). |

97 | Which entries are returned is of course still dependent on when garbage |

98 | collection occurs. Note that when a key gets returned as "present" in the |

99 | dictionary, there is no guarantee one can actually retrieve its value: it may |

100 | have been garbage collected in the mean time. |

101 | |

102 | Note that Sage's weak value dictionary is actually an instance of |

103 | :class:`dict`, in contrast to :mod:`weakref`'s weak value dictionary:: |

104 | |

105 | sage: issubclass(weakref.WeakValueDictionary, dict) |

106 | False |

107 | sage: issubclass(sage.misc.weak_dict.WeakValueDictionary, dict) |

108 | True |

109 | |

110 | See :trac:`13394` for a discussion of some of the design considerations. |

111 | """ |

112 | ######################################################################## |

113 | # Copyright (C) 2013 Simon King <simon.king@uni-jena.de> |

114 | # Nils Bruin <nbruin@sfu.ca> |

115 | # |

116 | # Distributed under the terms of the GNU General Public License (GPL) |

117 | # |

118 | # http://www.gnu.org/licenses/ |

119 | ######################################################################## |

120 | |

121 | import weakref |

122 | from weakref import KeyedRef |

123 | from copy import deepcopy |

124 | |

125 | from cpython.dict cimport * |

126 | from cpython.weakref cimport * |

127 | from cpython.list cimport * |

128 | |

129 | from cpython cimport Py_XINCREF, Py_XDECREF |

130 | |

131 | cdef extern from "Python.h": |

132 | ctypedef struct PyDictEntry: |

133 | Py_ssize_t me_hash |

134 | PyObject* me_key |

135 | PyObject* me_value |

136 | ctypedef struct PyDictObject: |

137 | Py_ssize_t ma_fill |

138 | Py_ssize_t ma_used |

139 | Py_ssize_t ma_mask |

140 | PyDictEntry* ma_table |

141 | |

142 | PyObject* Py_None |

143 | #we need this redefinition because we want to be able to call |

144 | #PyWeakref_GetObject with borrowed references. This is the recommended |

145 | #strategy according to Cython/Includes/cpython/__init__.pxd |

146 | PyObject* PyWeakref_GetObject(PyObject * wr) |

147 | |

148 | #this one's just missing. |

149 | long PyObject_Hash(object obj) |

150 | |

151 | #this routine extracts the "dummy" sentinel value that is used in dicts to mark |

152 | #"freed" slots. We need that to delete things ourselves. |

153 | cdef PyObject* init_dummy() except NULL: |

154 | cdef dict D = dict() |

155 | cdef PyDictObject* mp = <PyDictObject *><void *>D |

156 | cdef size_t mask |

157 | cdef PyDictEntry* ep0 = mp.ma_table |

158 | cdef PyDictEntry* ep |

159 | cdef size_t i |

160 | global dummy |

161 | |

162 | D[0]=0; del D[0] #ensure that there is a "deleted" entry in the dict |

163 | mask = mp.ma_mask |

164 | #since our entry had hash 0, we should really succeed on the first iteration |

165 | for i in range(mask+1): |

166 | ep = &(ep0[i]) |

167 | if ep.me_key != NULL: |

168 | return ep.me_key |

169 | raise RuntimeError("Problem initializing dummy") |

170 | |

171 | #note that dummy here is a borrowed reference. That's not a problem because |

172 | #we're never giving it up and dictobject.c is also holding a permanent reference |

173 | #to this object |

174 | cdef PyObject* dummy = init_dummy() |

175 | |

176 | #this routine looks for the first entry in dict D with given hash of the |

177 | #key and given (identical!) value and deletes that entry. |

178 | cdef 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 | |

252 | def 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 | |

306 | cdef 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 | |

1105 | cdef 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 |