# Ticket #13394: weak_dict_nb.pyx

File weak_dict_nb.pyx, 35.8 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 proplem arises when iterating over the items of a dictionary: If |

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

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

72 | |

73 | sage: class Cycle: |

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

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

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

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

78 | sage: import gc |

79 | sage: gc.disable() |

80 | sage: del C[:5] |

81 | sage: len(D) |

82 | 10 |

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

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

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

86 | Traceback (most recent call last): |

87 | ... |

88 | RuntimeError: dictionary changed size during iteration |

89 | |

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

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

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

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

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

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

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

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

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

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

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

101 | |

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

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

104 | |

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

106 | False |

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

108 | True |

109 | |

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

111 | """ |

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

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

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

115 | # |

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

117 | # |

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

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

120 | |

121 | import weakref |

122 | from weakref import KeyedRef |

123 | from copy import deepcopy |

124 | |

125 | from cpython.dict cimport * |

126 | from cpython.weakref cimport * |

127 | from cpython.list cimport * |

128 | |

129 | from cpython cimport Py_XINCREF, Py_XDECREF |

130 | |

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

132 | ctypedef struct PyDictEntry: |

133 | Py_ssize_t me_hash |

134 | PyObject* me_key |

135 | PyObject* me_value |

136 | ctypedef struct PyDictObject: |

137 | Py_ssize_t ma_fill |

138 | Py_ssize_t ma_used |

139 | Py_ssize_t ma_mask |

140 | PyDictEntry* ma_table |

141 | |

142 | PyObject* Py_None |

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

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

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

146 | PyObject* PyWeakref_GetObject(PyObject * wr) |

147 | |

148 | #this one's just missing. |

149 | long PyObject_Hash(object obj) |

150 | |

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

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

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

154 | cdef dict D = dict() |

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

156 | cdef size_t mask |

157 | cdef PyDictEntry* ep0 = mp.ma_table |

158 | cdef PyDictEntry* ep |

159 | cdef size_t i |

160 | global dummy |

161 | |

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

163 | mask = mp.ma_mask |

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

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

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

167 | if ep.me_key != NULL: |

168 | return ep.me_key |

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

170 | |

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

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

173 | #to this object |

174 | cdef PyObject* dummy = init_dummy() |

175 | |

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

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

178 | cpdef del_dictitem_by_exact_value(dict D, object value, long hash): |

179 | """ |

180 | Given a dictionary `mp`, a hash `hash`, and `value`, remove a key k from the |

181 | dictionary satisfying `hash(k) == hash` and `D[k] is value`. If no such entry |

182 | exists in `mp`, do nothing. |

183 | |

184 | TESTS:: |

185 | |

186 | sage: from sage.misc.weak_dict import del_dictitem_by_exact_value |

187 | sage: B=1000 |

188 | sage: L=list(range(B)) |

189 | sage: D1=dict() |

190 | sage: D2=dict() |

191 | sage: for i in range(100000): |

192 | ....: assert D1 == D2 |

193 | ....: ki=L[floor(random()*B)] |

194 | ....: vi=L[floor(random()*B)] |

195 | ....: D1[ki]=vi |

196 | ....: D2[ki]=vi |

197 | ....: ko=L[floor(random()*B)] |

198 | ....: if ko in D1: |

199 | ....: vo=D1[ko] |

200 | ....: del D1[ko] |

201 | ....: del_dictitem_by_exact_value(D2,vo,hash(ko)) |

202 | sage: D1 == D2 |

203 | True |

204 | |

205 | """ |

206 | cdef size_t i |

207 | cdef size_t perturb |

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

209 | cdef size_t mask = <size_t> mp.ma_mask |

210 | cdef PyDictEntry* ep0 = mp.ma_table |

211 | cdef PyDictEntry* ep |

212 | i = hash & mask |

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

214 | |

215 | if ep.me_key == NULL: |

216 | # key not found |

217 | return |

218 | |

219 | perturb = hash |

220 | while (<void *>(ep.me_value) != <void *>value or ep.me_hash != hash): |

221 | i = (i << 2) + i + perturb +1 |

222 | ep = &ep0[i & mask] |

223 | if ep.me_key == NULL: |

224 | # key not found |

225 | return |

226 | perturb = perturb >> 5 #this is the value of PERTURB_SHIFT |

227 | |

228 | old_key = ep.me_key |

229 | if dummy == NULL: |

230 | raise RuntimeError("dummy needs to be initialized") |

231 | Py_XINCREF(dummy) |

232 | ep.me_key = dummy |

233 | old_value = ep.me_value |

234 | ep.me_value = NULL |

235 | mp.ma_used -= 1 |

236 | #in our case, the value is always a dead weakref, so decreffing that is |

237 | #fairly safe |

238 | Py_XDECREF(old_value) |

239 | #this could have any effect. |

240 | Py_XDECREF(old_key) |

241 | |

242 | cdef class WeakValueDictionary(dict): |

243 | """ |

244 | IMPLEMENTATION: |

245 | |

246 | The :class:`WeakValueDictionary` inherits from :class:`dict`. In its |

247 | implementation, it stores weakrefs to the actual values under the keys. |

248 | All access routines are wrapped to transparently place and remove these |

249 | weakrefs. |

250 | |

251 | NOTE: |

252 | |

253 | In contrast to :class:`weakref.WeakValueDictionary` in Python's |

254 | :mod:`weakref` module, the callback does not need to assume that the |

255 | dictionary key is a valid Python object when it is called. There is no |

256 | need to compute the hash or compare the dictionary keys. This is why |

257 | the example below would not work with |

258 | :class:`weakref.WeakValueDictionary`, but does work with |

259 | :class:`sage.misc.weak_dict.WeakValueDictionary`. |

260 | |

261 | EXAMPLES:: |

262 | |

263 | sage: import weakref |

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

265 | sage: class Keys: |

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

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

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

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

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

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

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

273 | sage: import sage.misc.weak_dict |

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

275 | sage: for v in ValList: |

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

277 | sage: len(D) |

278 | 10 |

279 | sage: del ValList |

280 | sage: len(D) |

281 | 1 |

282 | sage: del v |

283 | sage: len(D) |

284 | 0 |

285 | |

286 | TESTS: |

287 | |

288 | Check that deferred callbacks that are invalidated are silently |

289 | dealt with:: |

290 | |

291 | sage: from sage.misc.weak_dict import WeakValueDictionary |

292 | sage: D=WeakValueDictionary() |

293 | sage: V=set([2]) |

294 | sage: W=set([3]) |

295 | sage: D[1]=V |

296 | sage: i=D.iteritems(); d=i.next(); del d |

297 | sage: del V |

298 | sage: D[1]=W |

299 | sage: len(D) |

300 | 1 |

301 | sage: del i |

302 | sage: D.items() |

303 | [(1, set([3]))] |

304 | |

305 | |

306 | """ |

307 | cdef callback |

308 | cdef int _guard_level |

309 | cdef list _pending_removals |

310 | cdef _iteration_context |

311 | |

312 | def __init__(self, data=()): |

313 | """ |

314 | Create a :class:`WeakValueDictionary` with given initial data. |

315 | |

316 | INPUT: |

317 | |

318 | Optional iterable of key-value pairs |

319 | |

320 | EXAMPLES:: |

321 | |

322 | sage: L = [(p,GF(p)) for p in prime_range(10)] |

323 | sage: import sage.misc.weak_dict |

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

325 | sage: len(D) |

326 | 0 |

327 | sage: D = sage.misc.weak_dict.WeakValueDictionary(L) |

328 | sage: len(D) == len(L) |

329 | True |

330 | |

331 | """ |

332 | dict.__init__(self) |

333 | # Define a callback function. In contrast to what is done in Python's |

334 | # weakref.WeakValueDictionary, we use a closure and not a weak |

335 | # reference to refer to self. Reason: We trust that we will not create |

336 | # sub-classes of keyed references or weak value dictionaries providing |

337 | # a __del__ method. |

338 | def callback(r): |

339 | #The situation is the following: |

340 | #in the underlying dictionary, we have stored a KeyedRef r |

341 | #under a key k. The attribute r.key is the hash of k. |

342 | cdef WeakValueDictionary cself = self |

343 | if cself._guard_level: |

344 | cself._pending_removals.append(r) |

345 | else: |

346 | del_dictitem_by_exact_value(cself, r, r.key) |

347 | self.callback = callback |

348 | self._guard_level = 0 |

349 | self._pending_removals = [] |

350 | self._iteration_context = _IterationContext(self) |

351 | for k,v in data: |

352 | self[k] = v |

353 | |

354 | def __copy__(self): |

355 | """ |

356 | Return a copy of this weak dictionary. |

357 | |

358 | EXAMPLES:: |

359 | |

360 | sage: import sage.misc.weak_dict |

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

362 | sage: D[1] = QQ |

363 | sage: D[2] = ZZ |

364 | sage: D[None] = CC |

365 | sage: E = copy(D) # indirect doctest |

366 | sage: set(E.items()) == set(D.items()) |

367 | True |

368 | |

369 | """ |

370 | return WeakValueDictionary(self.iteritems()) |

371 | |

372 | def __deepcopy__(self, memo): |

373 | """ |

374 | Return a copy of this dictionary using copies of the keys. |

375 | |

376 | NOTE: |

377 | |

378 | The values of the dictionary are not copied, since we can not copy the |

379 | external strong references to the values, which are decisive for |

380 | garbage collection. |

381 | |

382 | EXAMPLES:: |

383 | |

384 | sage: class C(object): pass |

385 | sage: V = [C(),C()] |

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

387 | sage: D[C()] = V[0] |

388 | sage: D[C()] = V[1] |

389 | sage: E = deepcopy(D) # indirect doctest |

390 | |

391 | The keys are copied (in this silly example, the copies of the keys are |

392 | actually not equal to the original keys):: |

393 | |

394 | sage: set(E.keys()) == set(D.keys()) |

395 | False |

396 | |

397 | However, the values are not copied:: |

398 | |

399 | sage: set(E.values()) == set(D.values()) == set(V) |

400 | True |

401 | |

402 | """ |

403 | out = WeakValueDictionary() |

404 | for k,v in self.iteritems(): |

405 | out[deepcopy(k, memo)] = v |

406 | return out |

407 | |

408 | def __repr__(self): |

409 | """ |

410 | EXAMPLES:: |

411 | |

412 | sage: import sage.misc.weak_dict |

413 | sage: repr(sage.misc.weak_dict.WeakValueDictionary([(1,ZZ),(2,QQ)])) # indirect doctest |

414 | '<WeakValueDictionary at 0x...>' |

415 | |

416 | """ |

417 | return "<WeakValueDictionary at 0x%x>" % id(self) |

418 | |

419 | def __str__(self): |

420 | """ |

421 | EXAMPLES:: |

422 | |

423 | sage: import sage.misc.weak_dict |

424 | sage: str(sage.misc.weak_dict.WeakValueDictionary([(1,ZZ),(2,QQ)])) # indirect doctest |

425 | '<WeakValueDictionary at 0x...>' |

426 | |

427 | """ |

428 | return "<WeakValueDictionary at 0x%x>" % id(self) |

429 | |

430 | def setdefault(self, k, default=None): |

431 | """ |

432 | Return the stored value for a given key; return and store a default |

433 | value if no previous value is stored. |

434 | |

435 | EXAMPLES:: |

436 | |

437 | sage: import sage.misc.weak_dict |

438 | sage: L = [(p,GF(p)) for p in prime_range(10)] |

439 | sage: D = sage.misc.weak_dict.WeakValueDictionary(L) |

440 | sage: len(D) |

441 | 4 |

442 | |

443 | The value for an existing key is returned and not overridden:: |

444 | |

445 | sage: D.setdefault(5, ZZ) |

446 | Finite Field of size 5 |

447 | sage: D[5] |

448 | Finite Field of size 5 |

449 | |

450 | For a non-existing key, the default value is stored and returned:: |

451 | |

452 | sage: D.has_key(4) |

453 | False |

454 | sage: D.setdefault(4, ZZ) |

455 | Integer Ring |

456 | sage: D.has_key(4) |

457 | True |

458 | sage: D[4] |

459 | Integer Ring |

460 | sage: len(D) |

461 | 5 |

462 | |

463 | """ |

464 | cdef PyObject* wr = PyDict_GetItem(self, k) |

465 | if wr != NULL: |

466 | out = PyWeakref_GetObject(wr) |

467 | if out != Py_None: |

468 | return <object>out |

469 | PyDict_SetItem(self,k,KeyedRef(default,self.callback,PyObject_Hash(k))) |

470 | return default |

471 | |

472 | def __setitem__(self, k, v): |

473 | """ |

474 | EXAMPLES:: |

475 | |

476 | sage: import sage.misc.weak_dict |

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

478 | sage: ZZ in D |

479 | False |

480 | |

481 | One can set new items:: |

482 | |

483 | sage: D[ZZ] = QQ # indirect doctest |

484 | sage: D[ZZ] |

485 | Rational Field |

486 | sage: len(D) |

487 | 1 |

488 | sage: ZZ in D |

489 | True |

490 | |

491 | One can also override existing items:: |

492 | |

493 | sage: D[ZZ] = RLF |

494 | sage: ZZ in D |

495 | True |

496 | sage: D[ZZ] |

497 | Real Lazy Field |

498 | sage: len(D) |

499 | 1 |

500 | |

501 | TESTS: |

502 | |

503 | One may wonder whether it causes problems when garbage collection for |

504 | a previously exististing item happens *after* overriding the |

505 | item. The example shows that it is not a problem:: |

506 | |

507 | sage: class Cycle: |

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

509 | ....: self.selfref = self |

510 | sage: L = [Cycle() for _ in range(5)] |

511 | sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(L)) |

512 | sage: len(D) |

513 | 5 |

514 | sage: import gc |

515 | sage: gc.disable() |

516 | sage: del L |

517 | sage: len(D) |

518 | 5 |

519 | sage: D[2] = ZZ |

520 | sage: len(D) |

521 | 5 |

522 | sage: gc.enable() |

523 | sage: _ = gc.collect() |

524 | sage: len(D) |

525 | 1 |

526 | sage: D.items() |

527 | [(2, Integer Ring)] |

528 | |

529 | """ |

530 | PyDict_SetItem(self,k,KeyedRef(v,self.callback,PyObject_Hash(k))) |

531 | |

532 | #def __delitem__(self, k): |

533 | #we don't really have to override this method. |

534 | |

535 | def pop(self, k): |

536 | """ |

537 | Return the value for a given key, and delete it from the dictionary. |

538 | |

539 | EXAMPLES:: |

540 | |

541 | sage: import sage.misc.weak_dict |

542 | sage: L = [GF(p) for p in prime_range(10^3)] |

543 | sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(L)) |

544 | sage: 20 in D |

545 | True |

546 | sage: D.pop(20) |

547 | Finite Field of size 73 |

548 | sage: 20 in D |

549 | False |

550 | sage: D.pop(20) |

551 | Traceback (most recent call last): |

552 | ... |

553 | KeyError: 20 |

554 | |

555 | """ |

556 | cdef PyObject* wr = PyDict_GetItem(self, k) |

557 | if wr == NULL: |

558 | raise KeyError(k) |

559 | cdef PyObject* outref = PyWeakref_GetObject(wr) |

560 | if outref == Py_None: |

561 | raise KeyError(k) |

562 | #we turn the output into a new reference before deleting the item, |

563 | #because the deletion can cause any kind of havoc. |

564 | out = <object>outref |

565 | del self[k] |

566 | return out |

567 | |

568 | def popitem(self): |

569 | """ |

570 | Return and delete some item from the dictionary. |

571 | |

572 | EXAMPLES:: |

573 | |

574 | sage: import sage.misc.weak_dict |

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

576 | sage: D[1] = ZZ |

577 | |

578 | The dictionary only contains a single item, hence, it is clear which |

579 | one will be returned:: |

580 | |

581 | sage: D.popitem() |

582 | (1, Integer Ring) |

583 | |

584 | Now, the dictionary is empty, and hence the next attempt to pop an |

585 | item will fail with a ``KeyError``:: |

586 | |

587 | sage: D.popitem() |

588 | Traceback (most recent call last): |

589 | ... |

590 | KeyError: 'popitem(): weak value dictionary is empty' |

591 | |

592 | """ |

593 | for k,v in self.iteritems(): |

594 | del self[k] |

595 | return k, v |

596 | raise KeyError('popitem(): weak value dictionary is empty') |

597 | |

598 | def get(self, k, d=None): |

599 | """ |

600 | Return the stored value for a key, or a default value for unkown keys. |

601 | |

602 | The default value defaults to None. |

603 | |

604 | EXAMPLES:: |

605 | |

606 | sage: import sage.misc.weak_dict |

607 | sage: L = [GF(p) for p in prime_range(10^3)] |

608 | sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(L)) |

609 | sage: 100 in D |

610 | True |

611 | sage: 200 in D |

612 | False |

613 | sage: D.get(100, "not found") |

614 | Finite Field of size 547 |

615 | sage: D.get(200, "not found") |

616 | 'not found' |

617 | sage: D.get(200) is None |

618 | True |

619 | |

620 | """ |

621 | cdef PyObject * wr = PyDict_GetItem(self, k) |

622 | if wr == NULL: |

623 | return d |

624 | out = PyWeakref_GetObject(wr) |

625 | if out == Py_None: |

626 | return d |

627 | else: |

628 | return <object>out |

629 | |

630 | def __getitem__(self, k): |

631 | """ |

632 | TESTS:: |

633 | |

634 | sage: import sage.misc.weak_dict |

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

636 | sage: D[ZZ] = QQ |

637 | sage: D[QQ] |

638 | Traceback (most recent call last): |

639 | ... |

640 | KeyError: Rational Field |

641 | sage: D[ZZ] # indirect doctest |

642 | Rational Field |

643 | |

644 | As usual, the dictionary keys are compared by `==` and not by |

645 | identity:: |

646 | |

647 | sage: D[10] = ZZ |

648 | sage: D[int(10)] |

649 | Integer Ring |

650 | |

651 | """ |

652 | cdef PyObject* wr = PyDict_GetItem(self, k) |

653 | if wr == NULL: |

654 | raise KeyError(k) |

655 | out = PyWeakref_GetObject(wr) |

656 | if out == Py_None: |

657 | raise KeyError(k) |

658 | return <object>out |

659 | |

660 | def has_key(self, k): |

661 | """ |

662 | Returns True, if the key is known to the dictionary. |

663 | |

664 | EXAMPLES:: |

665 | |

666 | sage: import sage.misc.weak_dict |

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

668 | sage: L = [Vals() for _ in range(10)] |

669 | sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(L)) |

670 | sage: D.has_key(3) |

671 | True |

672 | |

673 | As usual, keys are compared by equality and not by identity:: |

674 | |

675 | sage: D.has_key(int(3)) |

676 | True |

677 | |

678 | This is a weak value dictionary. Hence, the existence of the |

679 | dictionary does not prevent the values from garbage collection, |

680 | thereby removing the corresponding key-value pairs:: |

681 | |

682 | sage: del L[3] |

683 | sage: D.has_key(3) |

684 | False |

685 | |

686 | """ |

687 | return k in self |

688 | |

689 | def __contains__(self, k): |

690 | """ |

691 | Containment in the set of keys. |

692 | |

693 | TESTS:: |

694 | |

695 | sage: import sage.misc.weak_dict |

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

697 | sage: L = [Vals() for _ in range(10)] |

698 | sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(L)) |

699 | sage: 3 in D # indirect doctest |

700 | True |

701 | |

702 | As usual, keys are compared by equality and not by identity:: |

703 | |

704 | sage: int(3) in D |

705 | True |

706 | |

707 | This is a weak value dictionary. Hence, the existence of the |

708 | dictionary does not prevent the values from garbage collection, |

709 | thereby removing the corresponding key-value pairs:: |

710 | |

711 | sage: del L[3] |

712 | sage: 3 in D |

713 | False |

714 | |

715 | """ |

716 | cdef PyObject* wr = PyDict_GetItem(self, k) |

717 | if wr==NULL: |

718 | return False |

719 | if PyWeakref_GetObject(wr)==Py_None: |

720 | return False |

721 | else: |

722 | return True |

723 | |

724 | #def __len__(self): |

725 | #since GC is not deterministic, neither is the length of a WeakValueDictionary, |

726 | #so we might as well just return the normal dictionary length. |

727 | |

728 | def iterkeys(self): |

729 | """ |

730 | Iterate over the keys of this dictionary. |

731 | |

732 | .. WARNING:: |

733 | |

734 | Iteration is unsafe, if the length of the dictionary changes |

735 | during the iteration! This can also happen by garbage collection. |

736 | |

737 | EXAMPLES:: |

738 | |

739 | sage: import sage.misc.weak_dict |

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

741 | sage: L = [Vals() for _ in range(10)] |

742 | sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(L)) |

743 | sage: del L[4] |

744 | |

745 | One item got deleted from the list ``L`` and hence the corresponding |

746 | item in the dictionary got deleted as well. Therefore, the |

747 | corresponding key 4 is missing in the list of keys:: |

748 | |

749 | sage: list(sorted(D.iterkeys())) |

750 | [0, 1, 2, 3, 5, 6, 7, 8, 9] |

751 | |

752 | """ |

753 | cdef PyObject *key, *wr |

754 | cdef Py_ssize_t pos = 0 |

755 | with self._iteration_context: |

756 | while PyDict_Next(self, &pos, &key, &wr): |

757 | #this check doesn't really say anything: by the time |

758 | #the key makes it to the customer, it may have already turned |

759 | #invalid. It's a cheap check, though. |

760 | if PyWeakref_GetObject(wr)!=Py_None: |

761 | yield <object>key |

762 | |

763 | def __iter__(self): |

764 | """ |

765 | Iterate over the keys of this dictionary. |

766 | |

767 | .. WARNING:: |

768 | |

769 | Iteration is unsafe, if the length of the dictionary changes |

770 | during the iteration! This can also happen by garbage collection. |

771 | |

772 | EXAMPLES:: |

773 | |

774 | sage: import sage.misc.weak_dict |

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

776 | sage: L = [Vals() for _ in range(10)] |

777 | sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(L)) |

778 | sage: del L[4] |

779 | |

780 | One item got deleted from the list ``L`` and hence the corresponding |

781 | item in the dictionary got deleted as well. Therefore, the |

782 | corresponding key 4 is missing in the list of keys:: |

783 | |

784 | sage: sorted(list(D)) # indirect doctest |

785 | [0, 1, 2, 3, 5, 6, 7, 8, 9] |

786 | |

787 | """ |

788 | return self.iterkeys() |

789 | |

790 | def keys(self): |

791 | """ |

792 | The list of keys. |

793 | |

794 | EXAMPLES:: |

795 | |

796 | sage: import sage.misc.weak_dict |

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

798 | sage: L = [Vals() for _ in range(10)] |

799 | sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(L)) |

800 | sage: del L[4] |

801 | |

802 | One item got deleted from the list ``L`` and hence the corresponding |

803 | item in the dictionary got deleted as well. Therefore, the |

804 | corresponding key 4 is missing in the list of keys:: |

805 | |

806 | sage: sorted(D.keys()) |

807 | [0, 1, 2, 3, 5, 6, 7, 8, 9] |

808 | |

809 | """ |

810 | return list(self.iterkeys()) |

811 | |

812 | def itervalues(self): |

813 | """ |

814 | Iterate over the values of this dictionary. |

815 | |

816 | .. WARNING:: |

817 | |

818 | Iteration is unsafe, if the length of the dictionary changes |

819 | during the iteration! This can also happen by garbage collection. |

820 | |

821 | EXAMPLES:: |

822 | |

823 | sage: import sage.misc.weak_dict |

824 | sage: class Vals: |

825 | ....: def __init__(self, n): |

826 | ....: self.n = n |

827 | ....: def __repr__(self): |

828 | ....: return "<%s>"%self.n |

829 | ....: def __cmp__(self, other): |

830 | ....: c = cmp(type(self),type(other)) |

831 | ....: if c: |

832 | ....: return c |

833 | ....: return cmp(self.n,other.n) |

834 | sage: L = [Vals(n) for n in range(10)] |

835 | sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(L)) |

836 | |

837 | We delete one item from ``D`` and we delete one item from the list |

838 | ``L``. The latter implies that the corresponding item from ``D`` gets |

839 | deleted as well. Hence, there remain eight values:: |

840 | |

841 | sage: del D[2] |

842 | sage: del L[5] |

843 | sage: for v in sorted(D.itervalues()): |

844 | ....: print v |

845 | <0> |

846 | <1> |

847 | <3> |

848 | <4> |

849 | <6> |

850 | <7> |

851 | <8> |

852 | <9> |

853 | |

854 | """ |

855 | cdef PyObject *key, *wr |

856 | cdef Py_ssize_t pos = 0 |

857 | with self._iteration_context: |

858 | while PyDict_Next(self, &pos, &key, &wr): |

859 | out = PyWeakref_GetObject(wr) |

860 | if out != Py_None: |

861 | yield <object>out |

862 | |

863 | def values(self): |

864 | """ |

865 | Return the list of values. |

866 | |

867 | EXAMPLES:: |

868 | |

869 | sage: import sage.misc.weak_dict |

870 | sage: class Vals: |

871 | ....: def __init__(self, n): |

872 | ....: self.n = n |

873 | ....: def __repr__(self): |

874 | ....: return "<%s>"%self.n |

875 | ....: def __cmp__(self, other): |

876 | ....: c = cmp(type(self),type(other)) |

877 | ....: if c: |

878 | ....: return c |

879 | ....: return cmp(self.n,other.n) |

880 | sage: L = [Vals(n) for n in range(10)] |

881 | sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(L)) |

882 | |

883 | We delete one item from ``D`` and we delete one item from the list |

884 | ``L``. The latter implies that the corresponding item from ``D`` gets |

885 | deleted as well. Hence, there remain eight values:: |

886 | |

887 | sage: del D[2] |

888 | sage: del L[5] |

889 | sage: sorted(D.values()) |

890 | [<0>, <1>, <3>, <4>, <6>, <7>, <8>, <9>] |

891 | |

892 | """ |

893 | return list(self.itervalues()) |

894 | |

895 | def iteritems(self): |

896 | """ |

897 | Iterate over the items of this dictionary. |

898 | |

899 | .. WARNING:: |

900 | |

901 | Iteration is unsafe, if the length of the dictionary changes |

902 | during the iteration! This can also happen by garbage collection. |

903 | |

904 | EXAMPLES:: |

905 | |

906 | sage: import sage.misc.weak_dict |

907 | sage: class Vals: |

908 | ....: def __init__(self, n): |

909 | ....: self.n = n |

910 | ....: def __repr__(self): |

911 | ....: return "<%s>"%self.n |

912 | ....: def __cmp__(self, other): |

913 | ....: c = cmp(type(self),type(other)) |

914 | ....: if c: |

915 | ....: return c |

916 | ....: return cmp(self.n,other.n) |

917 | sage: class Keys(object): |

918 | ....: def __init__(self, n): |

919 | ....: self.n = n |

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

921 | ....: if self.n%2: |

922 | ....: return 5 |

923 | ....: return 3 |

924 | ....: def __repr__(self): |

925 | ....: return "[%s]"%self.n |

926 | ....: def __cmp__(self, other): |

927 | ....: c = cmp(type(self),type(other)) |

928 | ....: if c: |

929 | ....: return c |

930 | ....: return cmp(self.n,other.n) |

931 | sage: L = [(Keys(n), Vals(n)) for n in range(10)] |

932 | sage: D = sage.misc.weak_dict.WeakValueDictionary(L) |

933 | |

934 | We remove one dictionary item directly. Another item is removed by |

935 | means of garbage collection. By consequence, there remain eight |

936 | items in the dictionary:: |

937 | |

938 | sage: del D[Keys(2)] |

939 | sage: del L[5] |

940 | sage: for k,v in sorted(D.iteritems()): |

941 | ....: print k, v |

942 | [0] <0> |

943 | [1] <1> |

944 | [3] <3> |

945 | [4] <4> |

946 | [6] <6> |

947 | [7] <7> |

948 | [8] <8> |

949 | [9] <9> |

950 | |

951 | """ |

952 | cdef PyObject *key, *wr |

953 | cdef Py_ssize_t pos = 0 |

954 | with self._iteration_context: |

955 | while PyDict_Next(self, &pos, &key, &wr): |

956 | out = PyWeakref_GetObject(wr) |

957 | if out != Py_None: |

958 | yield <object>key, <object>out |

959 | |

960 | def items(self): |

961 | """ |

962 | The key-value pairs of this dictionary. |

963 | |

964 | EXAMPLES:: |

965 | |

966 | sage: import sage.misc.weak_dict |

967 | sage: class Vals: |

968 | ....: def __init__(self, n): |

969 | ....: self.n = n |

970 | ....: def __repr__(self): |

971 | ....: return "<%s>"%self.n |

972 | ....: def __cmp__(self, other): |

973 | ....: c = cmp(type(self),type(other)) |

974 | ....: if c: |

975 | ....: return c |

976 | ....: return cmp(self.n,other.n) |

977 | sage: class Keys(object): |

978 | ....: def __init__(self, n): |

979 | ....: self.n = n |

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

981 | ....: if self.n%2: |

982 | ....: return 5 |

983 | ....: return 3 |

984 | ....: def __repr__(self): |

985 | ....: return "[%s]"%self.n |

986 | ....: def __cmp__(self, other): |

987 | ....: c = cmp(type(self),type(other)) |

988 | ....: if c: |

989 | ....: return c |

990 | ....: return cmp(self.n,other.n) |

991 | sage: L = [(Keys(n), Vals(n)) for n in range(10)] |

992 | sage: D = sage.misc.weak_dict.WeakValueDictionary(L) |

993 | |

994 | We remove one dictionary item directly. Another item is removed by |

995 | means of garbage collection. By consequence, there remain eight |

996 | items in the dictionary:: |

997 | |

998 | sage: del D[Keys(2)] |

999 | sage: del L[5] |

1000 | sage: sorted(D.items()) |

1001 | [([0], <0>), |

1002 | ([1], <1>), |

1003 | ([3], <3>), |

1004 | ([4], <4>), |

1005 | ([6], <6>), |

1006 | ([7], <7>), |

1007 | ([8], <8>), |

1008 | ([9], <9>)] |

1009 | |

1010 | """ |

1011 | return list(self.iteritems()) |

1012 | |

1013 | cdef class _IterationContext: |

1014 | """ |

1015 | An iterator that protects :class:`WeakValueDictionary` from some negative |

1016 | effects of deletions due to garbage collection during iteration. |

1017 | It's still not safe to explicitly mutate a dictionary during iteration, |

1018 | though. Doing so is a bug in a program (since iteration order is |

1019 | non-deterministic the results are not well-defined) |

1020 | |

1021 | This is implemented by putting all items that are deleted during iteration |

1022 | are not actually deleted, but only *marked* for deletion. Note, however, |

1023 | that they behave like items that actually *are* deleted. E.g., it is not |

1024 | possible to delete the same item twice:: |

1025 | |

1026 | sage: class Val: pass |

1027 | sage: V = [Val() for n in range(3)] |

1028 | sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(V)) |

1029 | sage: for k,v in D.iteritems(): |

1030 | ....: print k in D.keys() |

1031 | ....: del D[k] |

1032 | ....: print k in D.keys() |

1033 | ....: try: |

1034 | ....: del D[k] |

1035 | ....: except KeyError: |

1036 | ....: print "due error" |

1037 | True |

1038 | False |

1039 | due error |

1040 | True |

1041 | False |

1042 | due error |

1043 | True |

1044 | False |

1045 | due error |

1046 | |

1047 | """ |

1048 | cdef WeakValueDictionary Dict |

1049 | def __init__(self, Dict): |

1050 | """ |

1051 | INPUT: |

1052 | |

1053 | A :class:`WeakValueDictionary` |

1054 | |

1055 | This context manager is used during iteration over the given |

1056 | dictionary, and prevents negative side-effects of item deletions |

1057 | during iteration. |

1058 | |

1059 | EXAMPLES:: |

1060 | |

1061 | sage: import sage.misc.weak_dict |

1062 | sage: class Val: pass |

1063 | sage: V = [Val() for n in range(3)] |

1064 | sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(V)) |

1065 | sage: for k,v in D.iteritems(): # indirect doctest |

1066 | ....: k in D.keys() |

1067 | ....: del D[k] |

1068 | ....: k in D.keys() |

1069 | True |

1070 | False |

1071 | True |

1072 | False |

1073 | True |

1074 | False |

1075 | |

1076 | """ |

1077 | self.Dict = Dict |

1078 | |

1079 | def __enter__(self): |

1080 | """ |

1081 | Make sure that items of a weak value dictionary are not actually |

1082 | deleted, but only *marked* for deletion. |

1083 | |

1084 | TESTS:: |

1085 | |

1086 | sage: import sage.misc.weak_dict |

1087 | sage: class Val: pass |

1088 | sage: V = [Val() for n in range(3)] |

1089 | sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(V)) |

1090 | sage: for k,v in D.iteritems(): # indirect doctest |

1091 | ....: k in D.keys() |

1092 | ....: del D[k] |

1093 | ....: k in D.keys() |

1094 | True |

1095 | False |

1096 | True |

1097 | False |

1098 | True |

1099 | False |

1100 | |

1101 | """ |

1102 | self.Dict._guard_level += 1 |

1103 | return self |

1104 | |

1105 | def __exit__(self, exc_type, exc_val, exc_tb): |

1106 | """ |

1107 | Make sure that all items of a weak value dictionary that are marked |

1108 | for deletion are actually deleted, as soon as there is no iteration |

1109 | over the dictionary. |

1110 | |

1111 | TESTS:: |

1112 | |

1113 | sage: import sage.misc.weak_dict |

1114 | sage: class Val: pass |

1115 | sage: V = [Val() for n in range(3)] |

1116 | sage: D = sage.misc.weak_dict.WeakValueDictionary(enumerate(V)) |

1117 | sage: for k,v in D.iteritems(): # indirect doctest |

1118 | ....: k in D.keys() |

1119 | ....: del D[k] |

1120 | ....: k in D.keys() |

1121 | True |

1122 | False |

1123 | True |

1124 | False |

1125 | True |

1126 | False |

1127 | |

1128 | """ |

1129 | # Propagate errors by returning "False" |

1130 | self.Dict._guard_level -= 1 |

1131 | #when the guard_level drops to zero, we try to remove all the |

1132 | #pending removals. Note that this could trigger another iterator |

1133 | #to become active, in which case we should back off. |

1134 | while (not self.Dict._guard_level) and self.Dict._pending_removals: |

1135 | self.Dict.callback(self.Dict._pending_removals.pop()) |

1136 | return False |