| 1 |
import builtins |
| 2 |
import contextlib |
| 3 |
import copy |
| 4 |
import gc |
| 5 |
import operator |
| 6 |
import pickle |
| 7 |
import re |
| 8 |
from random import randrange, shuffle |
| 9 |
import struct |
| 10 |
import sys |
| 11 |
import unittest |
| 12 |
import weakref |
| 13 |
from collections.abc import MutableMapping |
| 14 |
from test import mapping_tests, support |
| 15 |
from test.support import import_helper |
| 16 |
|
| 17 |
|
| 18 |
py_coll = import_helper.import_fresh_module('collections', |
| 19 |
blocked=['_collections']) |
| 20 |
c_coll = import_helper.import_fresh_module('collections', |
| 21 |
fresh=['_collections']) |
| 22 |
|
| 23 |
|
| 24 |
@contextlib.contextmanager |
| 25 |
def replaced_module(name, replacement): |
| 26 |
original_module = sys.modules[name] |
| 27 |
sys.modules[name] = replacement |
| 28 |
try: |
| 29 |
yield |
| 30 |
finally: |
| 31 |
sys.modules[name] = original_module |
| 32 |
|
| 33 |
|
| 34 |
class OrderedDictTests: |
| 35 |
|
| 36 |
def test_init(self): |
| 37 |
OrderedDict = self.OrderedDict |
| 38 |
with self.assertRaises(TypeError): |
| 39 |
OrderedDict([('a', 1), ('b', 2)], None) # too many args |
| 40 |
pairs = [('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5)] |
| 41 |
self.assertEqual(sorted(OrderedDict(dict(pairs)).items()), pairs) # dict input |
| 42 |
self.assertEqual(sorted(OrderedDict(**dict(pairs)).items()), pairs) # kwds input |
| 43 |
self.assertEqual(list(OrderedDict(pairs).items()), pairs) # pairs input |
| 44 |
self.assertEqual(list(OrderedDict([('a', 1), ('b', 2), ('c', 9), ('d', 4)], |
| 45 |
c=3, e=5).items()), pairs) # mixed input |
| 46 |
|
| 47 |
# make sure no positional args conflict with possible kwdargs |
| 48 |
self.assertEqual(list(OrderedDict(self=42).items()), [('self', 42)]) |
| 49 |
self.assertEqual(list(OrderedDict(other=42).items()), [('other', 42)]) |
| 50 |
self.assertRaises(TypeError, OrderedDict, 42) |
| 51 |
self.assertRaises(TypeError, OrderedDict, (), ()) |
| 52 |
self.assertRaises(TypeError, OrderedDict.__init__) |
| 53 |
|
| 54 |
# Make sure that direct calls to __init__ do not clear previous contents |
| 55 |
d = OrderedDict([('a', 1), ('b', 2), ('c', 3), ('d', 44), ('e', 55)]) |
| 56 |
d.__init__([('e', 5), ('f', 6)], g=7, d=4) |
| 57 |
self.assertEqual(list(d.items()), |
| 58 |
[('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5), ('f', 6), ('g', 7)]) |
| 59 |
|
| 60 |
def test_468(self): |
| 61 |
OrderedDict = self.OrderedDict |
| 62 |
items = [('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5), ('f', 6), ('g', 7)] |
| 63 |
shuffle(items) |
| 64 |
argdict = OrderedDict(items) |
| 65 |
d = OrderedDict(**argdict) |
| 66 |
self.assertEqual(list(d.items()), items) |
| 67 |
|
| 68 |
def test_update(self): |
| 69 |
OrderedDict = self.OrderedDict |
| 70 |
with self.assertRaises(TypeError): |
| 71 |
OrderedDict().update([('a', 1), ('b', 2)], None) # too many args |
| 72 |
pairs = [('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5)] |
| 73 |
od = OrderedDict() |
| 74 |
od.update(dict(pairs)) |
| 75 |
self.assertEqual(sorted(od.items()), pairs) # dict input |
| 76 |
od = OrderedDict() |
| 77 |
od.update(**dict(pairs)) |
| 78 |
self.assertEqual(sorted(od.items()), pairs) # kwds input |
| 79 |
od = OrderedDict() |
| 80 |
od.update(pairs) |
| 81 |
self.assertEqual(list(od.items()), pairs) # pairs input |
| 82 |
od = OrderedDict() |
| 83 |
od.update([('a', 1), ('b', 2), ('c', 9), ('d', 4)], c=3, e=5) |
| 84 |
self.assertEqual(list(od.items()), pairs) # mixed input |
| 85 |
|
| 86 |
# Issue 9137: Named argument called 'other' or 'self' |
| 87 |
# shouldn't be treated specially. |
| 88 |
od = OrderedDict() |
| 89 |
od.update(self=23) |
| 90 |
self.assertEqual(list(od.items()), [('self', 23)]) |
| 91 |
od = OrderedDict() |
| 92 |
od.update(other={}) |
| 93 |
self.assertEqual(list(od.items()), [('other', {})]) |
| 94 |
od = OrderedDict() |
| 95 |
od.update(red=5, blue=6, other=7, self=8) |
| 96 |
self.assertEqual(sorted(list(od.items())), |
| 97 |
[('blue', 6), ('other', 7), ('red', 5), ('self', 8)]) |
| 98 |
|
| 99 |
# Make sure that direct calls to update do not clear previous contents |
| 100 |
# add that updates items are not moved to the end |
| 101 |
d = OrderedDict([('a', 1), ('b', 2), ('c', 3), ('d', 44), ('e', 55)]) |
| 102 |
d.update([('e', 5), ('f', 6)], g=7, d=4) |
| 103 |
self.assertEqual(list(d.items()), |
| 104 |
[('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5), ('f', 6), ('g', 7)]) |
| 105 |
|
| 106 |
self.assertRaises(TypeError, OrderedDict().update, 42) |
| 107 |
self.assertRaises(TypeError, OrderedDict().update, (), ()) |
| 108 |
self.assertRaises(TypeError, OrderedDict.update) |
| 109 |
|
| 110 |
self.assertRaises(TypeError, OrderedDict().update, 42) |
| 111 |
self.assertRaises(TypeError, OrderedDict().update, (), ()) |
| 112 |
self.assertRaises(TypeError, OrderedDict.update) |
| 113 |
|
| 114 |
def test_init_calls(self): |
| 115 |
calls = [] |
| 116 |
class Spam: |
| 117 |
def keys(self): |
| 118 |
calls.append('keys') |
| 119 |
return () |
| 120 |
def items(self): |
| 121 |
calls.append('items') |
| 122 |
return () |
| 123 |
|
| 124 |
self.OrderedDict(Spam()) |
| 125 |
self.assertEqual(calls, ['keys']) |
| 126 |
|
| 127 |
def test_overridden_init(self): |
| 128 |
# Sync-up pure Python OD class with C class where |
| 129 |
# a consistent internal state is created in __new__ |
| 130 |
# rather than __init__. |
| 131 |
OrderedDict = self.OrderedDict |
| 132 |
class ODNI(OrderedDict): |
| 133 |
def __init__(*args, **kwargs): |
| 134 |
pass |
| 135 |
od = ODNI() |
| 136 |
od['a'] = 1 # This used to fail because __init__ was bypassed |
| 137 |
|
| 138 |
def test_fromkeys(self): |
| 139 |
OrderedDict = self.OrderedDict |
| 140 |
od = OrderedDict.fromkeys('abc') |
| 141 |
self.assertEqual(list(od.items()), [(c, None) for c in 'abc']) |
| 142 |
od = OrderedDict.fromkeys('abc', value=None) |
| 143 |
self.assertEqual(list(od.items()), [(c, None) for c in 'abc']) |
| 144 |
od = OrderedDict.fromkeys('abc', value=0) |
| 145 |
self.assertEqual(list(od.items()), [(c, 0) for c in 'abc']) |
| 146 |
|
| 147 |
def test_abc(self): |
| 148 |
OrderedDict = self.OrderedDict |
| 149 |
self.assertIsInstance(OrderedDict(), MutableMapping) |
| 150 |
self.assertIsSubclass(OrderedDict, MutableMapping) |
| 151 |
|
| 152 |
def test_clear(self): |
| 153 |
OrderedDict = self.OrderedDict |
| 154 |
pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] |
| 155 |
shuffle(pairs) |
| 156 |
od = OrderedDict(pairs) |
| 157 |
self.assertEqual(len(od), len(pairs)) |
| 158 |
od.clear() |
| 159 |
self.assertEqual(len(od), 0) |
| 160 |
|
| 161 |
def test_delitem(self): |
| 162 |
OrderedDict = self.OrderedDict |
| 163 |
pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] |
| 164 |
od = OrderedDict(pairs) |
| 165 |
del od['a'] |
| 166 |
self.assertNotIn('a', od) |
| 167 |
with self.assertRaises(KeyError): |
| 168 |
del od['a'] |
| 169 |
self.assertEqual(list(od.items()), pairs[:2] + pairs[3:]) |
| 170 |
|
| 171 |
def test_setitem(self): |
| 172 |
OrderedDict = self.OrderedDict |
| 173 |
od = OrderedDict([('d', 1), ('b', 2), ('c', 3), ('a', 4), ('e', 5)]) |
| 174 |
od['c'] = 10 # existing element |
| 175 |
od['f'] = 20 # new element |
| 176 |
self.assertEqual(list(od.items()), |
| 177 |
[('d', 1), ('b', 2), ('c', 10), ('a', 4), ('e', 5), ('f', 20)]) |
| 178 |
|
| 179 |
def test_iterators(self): |
| 180 |
OrderedDict = self.OrderedDict |
| 181 |
pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] |
| 182 |
shuffle(pairs) |
| 183 |
od = OrderedDict(pairs) |
| 184 |
self.assertEqual(list(od), [t[0] for t in pairs]) |
| 185 |
self.assertEqual(list(od.keys()), [t[0] for t in pairs]) |
| 186 |
self.assertEqual(list(od.values()), [t[1] for t in pairs]) |
| 187 |
self.assertEqual(list(od.items()), pairs) |
| 188 |
self.assertEqual(list(reversed(od)), |
| 189 |
[t[0] for t in reversed(pairs)]) |
| 190 |
self.assertEqual(list(reversed(od.keys())), |
| 191 |
[t[0] for t in reversed(pairs)]) |
| 192 |
self.assertEqual(list(reversed(od.values())), |
| 193 |
[t[1] for t in reversed(pairs)]) |
| 194 |
self.assertEqual(list(reversed(od.items())), list(reversed(pairs))) |
| 195 |
|
| 196 |
def test_detect_deletion_during_iteration(self): |
| 197 |
OrderedDict = self.OrderedDict |
| 198 |
od = OrderedDict.fromkeys('abc') |
| 199 |
it = iter(od) |
| 200 |
key = next(it) |
| 201 |
del od[key] |
| 202 |
with self.assertRaises(Exception): |
| 203 |
# Note, the exact exception raised is not guaranteed |
| 204 |
# The only guarantee that the next() will not succeed |
| 205 |
next(it) |
| 206 |
|
| 207 |
def test_sorted_iterators(self): |
| 208 |
OrderedDict = self.OrderedDict |
| 209 |
with self.assertRaises(TypeError): |
| 210 |
OrderedDict([('a', 1), ('b', 2)], None) |
| 211 |
pairs = [('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5)] |
| 212 |
od = OrderedDict(pairs) |
| 213 |
self.assertEqual(sorted(od), [t[0] for t in pairs]) |
| 214 |
self.assertEqual(sorted(od.keys()), [t[0] for t in pairs]) |
| 215 |
self.assertEqual(sorted(od.values()), [t[1] for t in pairs]) |
| 216 |
self.assertEqual(sorted(od.items()), pairs) |
| 217 |
self.assertEqual(sorted(reversed(od)), |
| 218 |
sorted([t[0] for t in reversed(pairs)])) |
| 219 |
|
| 220 |
def test_iterators_empty(self): |
| 221 |
OrderedDict = self.OrderedDict |
| 222 |
od = OrderedDict() |
| 223 |
empty = [] |
| 224 |
self.assertEqual(list(od), empty) |
| 225 |
self.assertEqual(list(od.keys()), empty) |
| 226 |
self.assertEqual(list(od.values()), empty) |
| 227 |
self.assertEqual(list(od.items()), empty) |
| 228 |
self.assertEqual(list(reversed(od)), empty) |
| 229 |
self.assertEqual(list(reversed(od.keys())), empty) |
| 230 |
self.assertEqual(list(reversed(od.values())), empty) |
| 231 |
self.assertEqual(list(reversed(od.items())), empty) |
| 232 |
|
| 233 |
def test_popitem(self): |
| 234 |
OrderedDict = self.OrderedDict |
| 235 |
pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] |
| 236 |
shuffle(pairs) |
| 237 |
od = OrderedDict(pairs) |
| 238 |
while pairs: |
| 239 |
self.assertEqual(od.popitem(), pairs.pop()) |
| 240 |
with self.assertRaises(KeyError): |
| 241 |
od.popitem() |
| 242 |
self.assertEqual(len(od), 0) |
| 243 |
|
| 244 |
def test_popitem_last(self): |
| 245 |
OrderedDict = self.OrderedDict |
| 246 |
pairs = [(i, i) for i in range(30)] |
| 247 |
|
| 248 |
obj = OrderedDict(pairs) |
| 249 |
for i in range(8): |
| 250 |
obj.popitem(True) |
| 251 |
obj.popitem(True) |
| 252 |
obj.popitem(last=True) |
| 253 |
self.assertEqual(len(obj), 20) |
| 254 |
|
| 255 |
def test_pop(self): |
| 256 |
OrderedDict = self.OrderedDict |
| 257 |
pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] |
| 258 |
shuffle(pairs) |
| 259 |
od = OrderedDict(pairs) |
| 260 |
shuffle(pairs) |
| 261 |
while pairs: |
| 262 |
k, v = pairs.pop() |
| 263 |
self.assertEqual(od.pop(k), v) |
| 264 |
with self.assertRaises(KeyError): |
| 265 |
od.pop('xyz') |
| 266 |
self.assertEqual(len(od), 0) |
| 267 |
self.assertEqual(od.pop(k, 12345), 12345) |
| 268 |
|
| 269 |
# make sure pop still works when __missing__ is defined |
| 270 |
class Missing(OrderedDict): |
| 271 |
def __missing__(self, key): |
| 272 |
return 0 |
| 273 |
m = Missing(a=1) |
| 274 |
self.assertEqual(m.pop('b', 5), 5) |
| 275 |
self.assertEqual(m.pop('a', 6), 1) |
| 276 |
self.assertEqual(m.pop('a', 6), 6) |
| 277 |
self.assertEqual(m.pop('a', default=6), 6) |
| 278 |
with self.assertRaises(KeyError): |
| 279 |
m.pop('a') |
| 280 |
|
| 281 |
def test_equality(self): |
| 282 |
OrderedDict = self.OrderedDict |
| 283 |
pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] |
| 284 |
shuffle(pairs) |
| 285 |
od1 = OrderedDict(pairs) |
| 286 |
od2 = OrderedDict(pairs) |
| 287 |
self.assertEqual(od1, od2) # same order implies equality |
| 288 |
pairs = pairs[2:] + pairs[:2] |
| 289 |
od2 = OrderedDict(pairs) |
| 290 |
self.assertNotEqual(od1, od2) # different order implies inequality |
| 291 |
# comparison to regular dict is not order sensitive |
| 292 |
self.assertEqual(od1, dict(od2)) |
| 293 |
self.assertEqual(dict(od2), od1) |
| 294 |
# different length implied inequality |
| 295 |
self.assertNotEqual(od1, OrderedDict(pairs[:-1])) |
| 296 |
|
| 297 |
def test_copying(self): |
| 298 |
OrderedDict = self.OrderedDict |
| 299 |
# Check that ordered dicts are copyable, deepcopyable, picklable, |
| 300 |
# and have a repr/eval round-trip |
| 301 |
pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] |
| 302 |
od = OrderedDict(pairs) |
| 303 |
od.x = ['x'] |
| 304 |
od.z = ['z'] |
| 305 |
def check(dup): |
| 306 |
msg = "\ncopy: %s\nod: %s" % (dup, od) |
| 307 |
self.assertIsNot(dup, od, msg) |
| 308 |
self.assertEqual(dup, od) |
| 309 |
self.assertEqual(list(dup.items()), list(od.items())) |
| 310 |
self.assertEqual(len(dup), len(od)) |
| 311 |
self.assertEqual(type(dup), type(od)) |
| 312 |
check(od.copy()) |
| 313 |
dup = copy.copy(od) |
| 314 |
check(dup) |
| 315 |
self.assertIs(dup.x, od.x) |
| 316 |
self.assertIs(dup.z, od.z) |
| 317 |
self.assertNotHasAttr(dup, 'y') |
| 318 |
dup = copy.deepcopy(od) |
| 319 |
check(dup) |
| 320 |
self.assertEqual(dup.x, od.x) |
| 321 |
self.assertIsNot(dup.x, od.x) |
| 322 |
self.assertEqual(dup.z, od.z) |
| 323 |
self.assertIsNot(dup.z, od.z) |
| 324 |
self.assertNotHasAttr(dup, 'y') |
| 325 |
# pickle directly pulls the module, so we have to fake it |
| 326 |
with replaced_module('collections', self.module): |
| 327 |
for proto in range(pickle.HIGHEST_PROTOCOL + 1): |
| 328 |
with self.subTest(proto=proto): |
| 329 |
dup = pickle.loads(pickle.dumps(od, proto)) |
| 330 |
check(dup) |
| 331 |
self.assertEqual(dup.x, od.x) |
| 332 |
self.assertEqual(dup.z, od.z) |
| 333 |
self.assertNotHasAttr(dup, 'y') |
| 334 |
check(eval(repr(od))) |
| 335 |
update_test = OrderedDict() |
| 336 |
update_test.update(od) |
| 337 |
check(update_test) |
| 338 |
check(OrderedDict(od)) |
| 339 |
|
| 340 |
def test_yaml_linkage(self): |
| 341 |
OrderedDict = self.OrderedDict |
| 342 |
# Verify that __reduce__ is setup in a way that supports PyYAML's dump() feature. |
| 343 |
# In yaml, lists are native but tuples are not. |
| 344 |
pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] |
| 345 |
od = OrderedDict(pairs) |
| 346 |
# yaml.dump(od) --> |
| 347 |
# '!!python/object/apply:__main__.OrderedDict\n- - [a, 1]\n - [b, 2]\n' |
| 348 |
self.assertTrue(all(type(pair)==list for pair in od.__reduce__()[1])) |
| 349 |
|
| 350 |
def test_reduce_not_too_fat(self): |
| 351 |
OrderedDict = self.OrderedDict |
| 352 |
# do not save instance dictionary if not needed |
| 353 |
pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] |
| 354 |
od = OrderedDict(pairs) |
| 355 |
self.assertIsInstance(od.__dict__, dict) |
| 356 |
self.assertIsNone(od.__reduce__()[2]) |
| 357 |
od.x = 10 |
| 358 |
self.assertEqual(od.__dict__['x'], 10) |
| 359 |
self.assertEqual(od.__reduce__()[2], {'x': 10}) |
| 360 |
|
| 361 |
def test_pickle_recursive(self): |
| 362 |
OrderedDict = self.OrderedDict |
| 363 |
od = OrderedDict() |
| 364 |
od[1] = od |
| 365 |
|
| 366 |
# pickle directly pulls the module, so we have to fake it |
| 367 |
with replaced_module('collections', self.module): |
| 368 |
for proto in range(-1, pickle.HIGHEST_PROTOCOL + 1): |
| 369 |
dup = pickle.loads(pickle.dumps(od, proto)) |
| 370 |
self.assertIsNot(dup, od) |
| 371 |
self.assertEqual(list(dup.keys()), [1]) |
| 372 |
self.assertIs(dup[1], dup) |
| 373 |
|
| 374 |
def test_repr(self): |
| 375 |
OrderedDict = self.OrderedDict |
| 376 |
od = OrderedDict([('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]) |
| 377 |
self.assertEqual(repr(od), |
| 378 |
"OrderedDict({'c': 1, 'b': 2, 'a': 3, 'd': 4, 'e': 5, 'f': 6})") |
| 379 |
self.assertEqual(eval(repr(od)), od) |
| 380 |
self.assertEqual(repr(OrderedDict()), "OrderedDict()") |
| 381 |
|
| 382 |
def test_repr_recursive(self): |
| 383 |
OrderedDict = self.OrderedDict |
| 384 |
# See issue #9826 |
| 385 |
od = OrderedDict.fromkeys('abc') |
| 386 |
od['x'] = od |
| 387 |
self.assertEqual(repr(od), |
| 388 |
"OrderedDict({'a': None, 'b': None, 'c': None, 'x': ...})") |
| 389 |
|
| 390 |
def test_repr_recursive_values(self): |
| 391 |
OrderedDict = self.OrderedDict |
| 392 |
od = OrderedDict() |
| 393 |
od[42] = od.values() |
| 394 |
r = repr(od) |
| 395 |
# Cannot perform a stronger test, as the contents of the repr |
| 396 |
# are implementation-dependent. All we can say is that we |
| 397 |
# want a str result, not an exception of any sort. |
| 398 |
self.assertIsInstance(r, str) |
| 399 |
od[42] = od.items() |
| 400 |
r = repr(od) |
| 401 |
# Again. |
| 402 |
self.assertIsInstance(r, str) |
| 403 |
|
| 404 |
def test_setdefault(self): |
| 405 |
OrderedDict = self.OrderedDict |
| 406 |
pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] |
| 407 |
shuffle(pairs) |
| 408 |
od = OrderedDict(pairs) |
| 409 |
pair_order = list(od.items()) |
| 410 |
self.assertEqual(od.setdefault('a', 10), 3) |
| 411 |
# make sure order didn't change |
| 412 |
self.assertEqual(list(od.items()), pair_order) |
| 413 |
self.assertEqual(od.setdefault('x', 10), 10) |
| 414 |
# make sure 'x' is added to the end |
| 415 |
self.assertEqual(list(od.items())[-1], ('x', 10)) |
| 416 |
self.assertEqual(od.setdefault('g', default=9), 9) |
| 417 |
|
| 418 |
# make sure setdefault still works when __missing__ is defined |
| 419 |
class Missing(OrderedDict): |
| 420 |
def __missing__(self, key): |
| 421 |
return 0 |
| 422 |
self.assertEqual(Missing().setdefault(5, 9), 9) |
| 423 |
|
| 424 |
def test_reinsert(self): |
| 425 |
OrderedDict = self.OrderedDict |
| 426 |
# Given insert a, insert b, delete a, re-insert a, |
| 427 |
# verify that a is now later than b. |
| 428 |
od = OrderedDict() |
| 429 |
od['a'] = 1 |
| 430 |
od['b'] = 2 |
| 431 |
del od['a'] |
| 432 |
self.assertEqual(list(od.items()), [('b', 2)]) |
| 433 |
od['a'] = 1 |
| 434 |
self.assertEqual(list(od.items()), [('b', 2), ('a', 1)]) |
| 435 |
|
| 436 |
def test_move_to_end(self): |
| 437 |
OrderedDict = self.OrderedDict |
| 438 |
od = OrderedDict.fromkeys('abcde') |
| 439 |
self.assertEqual(list(od), list('abcde')) |
| 440 |
od.move_to_end('c') |
| 441 |
self.assertEqual(list(od), list('abdec')) |
| 442 |
od.move_to_end('c', False) |
| 443 |
self.assertEqual(list(od), list('cabde')) |
| 444 |
od.move_to_end('c', False) |
| 445 |
self.assertEqual(list(od), list('cabde')) |
| 446 |
od.move_to_end('e') |
| 447 |
self.assertEqual(list(od), list('cabde')) |
| 448 |
od.move_to_end('b', last=False) |
| 449 |
self.assertEqual(list(od), list('bcade')) |
| 450 |
with self.assertRaises(KeyError): |
| 451 |
od.move_to_end('x') |
| 452 |
with self.assertRaises(KeyError): |
| 453 |
od.move_to_end('x', False) |
| 454 |
|
| 455 |
def test_move_to_end_issue25406(self): |
| 456 |
OrderedDict = self.OrderedDict |
| 457 |
od = OrderedDict.fromkeys('abc') |
| 458 |
od.move_to_end('c', last=False) |
| 459 |
self.assertEqual(list(od), list('cab')) |
| 460 |
od.move_to_end('a', last=False) |
| 461 |
self.assertEqual(list(od), list('acb')) |
| 462 |
|
| 463 |
od = OrderedDict.fromkeys('abc') |
| 464 |
od.move_to_end('a') |
| 465 |
self.assertEqual(list(od), list('bca')) |
| 466 |
od.move_to_end('c') |
| 467 |
self.assertEqual(list(od), list('bac')) |
| 468 |
|
| 469 |
def test_sizeof(self): |
| 470 |
OrderedDict = self.OrderedDict |
| 471 |
# Wimpy test: Just verify the reported size is larger than a regular dict |
| 472 |
d = dict(a=1) |
| 473 |
od = OrderedDict(**d) |
| 474 |
self.assertGreater(sys.getsizeof(od), sys.getsizeof(d)) |
| 475 |
|
| 476 |
def test_views(self): |
| 477 |
OrderedDict = self.OrderedDict |
| 478 |
# See http://bugs.python.org/issue24286 |
| 479 |
s = 'the quick brown fox jumped over a lazy dog yesterday before dawn'.split() |
| 480 |
od = OrderedDict.fromkeys(s) |
| 481 |
self.assertEqual(od.keys(), dict(od).keys()) |
| 482 |
self.assertEqual(od.items(), dict(od).items()) |
| 483 |
|
| 484 |
def test_override_update(self): |
| 485 |
OrderedDict = self.OrderedDict |
| 486 |
# Verify that subclasses can override update() without breaking __init__() |
| 487 |
class MyOD(OrderedDict): |
| 488 |
def update(self, *args, **kwds): |
| 489 |
raise Exception() |
| 490 |
items = [('a', 1), ('c', 3), ('b', 2)] |
| 491 |
self.assertEqual(list(MyOD(items).items()), items) |
| 492 |
|
| 493 |
def test_highly_nested(self): |
| 494 |
# Issues 25395 and 35983: test that the trashcan mechanism works |
| 495 |
# correctly for OrderedDict: deleting a highly nested OrderDict |
| 496 |
# should not crash Python. |
| 497 |
OrderedDict = self.OrderedDict |
| 498 |
obj = None |
| 499 |
for _ in range(1000): |
| 500 |
obj = OrderedDict([(None, obj)]) |
| 501 |
del obj |
| 502 |
support.gc_collect() |
| 503 |
|
| 504 |
def test_highly_nested_subclass(self): |
| 505 |
# Issues 25395 and 35983: test that the trashcan mechanism works |
| 506 |
# correctly for OrderedDict: deleting a highly nested OrderDict |
| 507 |
# should not crash Python. |
| 508 |
OrderedDict = self.OrderedDict |
| 509 |
deleted = [] |
| 510 |
class MyOD(OrderedDict): |
| 511 |
def __del__(self): |
| 512 |
deleted.append(self.i) |
| 513 |
obj = None |
| 514 |
for i in range(100): |
| 515 |
obj = MyOD([(None, obj)]) |
| 516 |
obj.i = i |
| 517 |
del obj |
| 518 |
support.gc_collect() |
| 519 |
self.assertEqual(deleted, list(reversed(range(100)))) |
| 520 |
|
| 521 |
def test_delitem_hash_collision(self): |
| 522 |
OrderedDict = self.OrderedDict |
| 523 |
|
| 524 |
class Key: |
| 525 |
def __init__(self, hash): |
| 526 |
self._hash = hash |
| 527 |
self.value = str(id(self)) |
| 528 |
def __hash__(self): |
| 529 |
return self._hash |
| 530 |
def __eq__(self, other): |
| 531 |
try: |
| 532 |
return self.value == other.value |
| 533 |
except AttributeError: |
| 534 |
return False |
| 535 |
def __repr__(self): |
| 536 |
return self.value |
| 537 |
|
| 538 |
def blocking_hash(hash): |
| 539 |
# See the collision-handling in lookdict (in Objects/dictobject.c). |
| 540 |
MINSIZE = 8 |
| 541 |
i = (hash & MINSIZE-1) |
| 542 |
return (i << 2) + i + hash + 1 |
| 543 |
|
| 544 |
COLLIDING = 1 |
| 545 |
|
| 546 |
key = Key(COLLIDING) |
| 547 |
colliding = Key(COLLIDING) |
| 548 |
blocking = Key(blocking_hash(COLLIDING)) |
| 549 |
|
| 550 |
od = OrderedDict() |
| 551 |
od[key] = ... |
| 552 |
od[blocking] = ... |
| 553 |
od[colliding] = ... |
| 554 |
od['after'] = ... |
| 555 |
|
| 556 |
del od[blocking] |
| 557 |
del od[colliding] |
| 558 |
self.assertEqual(list(od.items()), [(key, ...), ('after', ...)]) |
| 559 |
|
| 560 |
def test_issue24347(self): |
| 561 |
OrderedDict = self.OrderedDict |
| 562 |
|
| 563 |
class Key: |
| 564 |
def __hash__(self): |
| 565 |
return randrange(100000) |
| 566 |
|
| 567 |
od = OrderedDict() |
| 568 |
for i in range(100): |
| 569 |
key = Key() |
| 570 |
od[key] = i |
| 571 |
|
| 572 |
# These should not crash. |
| 573 |
with self.assertRaises(KeyError): |
| 574 |
list(od.values()) |
| 575 |
with self.assertRaises(KeyError): |
| 576 |
list(od.items()) |
| 577 |
with self.assertRaises(KeyError): |
| 578 |
repr(od) |
| 579 |
with self.assertRaises(KeyError): |
| 580 |
od.copy() |
| 581 |
|
| 582 |
def test_issue24348(self): |
| 583 |
OrderedDict = self.OrderedDict |
| 584 |
|
| 585 |
class Key: |
| 586 |
def __hash__(self): |
| 587 |
return 1 |
| 588 |
|
| 589 |
od = OrderedDict() |
| 590 |
od[Key()] = 0 |
| 591 |
# This should not crash. |
| 592 |
od.popitem() |
| 593 |
|
| 594 |
def test_issue24667(self): |
| 595 |
""" |
| 596 |
dict resizes after a certain number of insertion operations, |
| 597 |
whether or not there were deletions that freed up slots in the |
| 598 |
hash table. During fast node lookup, OrderedDict must correctly |
| 599 |
respond to all resizes, even if the current "size" is the same |
| 600 |
as the old one. We verify that here by forcing a dict resize |
| 601 |
on a sparse odict and then perform an operation that should |
| 602 |
trigger an odict resize (e.g. popitem). One key aspect here is |
| 603 |
that we will keep the size of the odict the same at each popitem |
| 604 |
call. This verifies that we handled the dict resize properly. |
| 605 |
""" |
| 606 |
OrderedDict = self.OrderedDict |
| 607 |
|
| 608 |
od = OrderedDict() |
| 609 |
for c0 in '0123456789ABCDEF': |
| 610 |
for c1 in '0123456789ABCDEF': |
| 611 |
if len(od) == 4: |
| 612 |
# This should not raise a KeyError. |
| 613 |
od.popitem(last=False) |
| 614 |
key = c0 + c1 |
| 615 |
od[key] = key |
| 616 |
|
| 617 |
# Direct use of dict methods |
| 618 |
|
| 619 |
def test_dict_setitem(self): |
| 620 |
OrderedDict = self.OrderedDict |
| 621 |
od = OrderedDict() |
| 622 |
dict.__setitem__(od, 'spam', 1) |
| 623 |
self.assertNotIn('NULL', repr(od)) |
| 624 |
|
| 625 |
def test_dict_delitem(self): |
| 626 |
OrderedDict = self.OrderedDict |
| 627 |
od = OrderedDict() |
| 628 |
od['spam'] = 1 |
| 629 |
od['ham'] = 2 |
| 630 |
dict.__delitem__(od, 'spam') |
| 631 |
with self.assertRaises(KeyError): |
| 632 |
repr(od) |
| 633 |
|
| 634 |
def test_dict_clear(self): |
| 635 |
OrderedDict = self.OrderedDict |
| 636 |
od = OrderedDict() |
| 637 |
od['spam'] = 1 |
| 638 |
od['ham'] = 2 |
| 639 |
dict.clear(od) |
| 640 |
self.assertNotIn('NULL', repr(od)) |
| 641 |
|
| 642 |
def test_dict_pop(self): |
| 643 |
OrderedDict = self.OrderedDict |
| 644 |
od = OrderedDict() |
| 645 |
od['spam'] = 1 |
| 646 |
od['ham'] = 2 |
| 647 |
dict.pop(od, 'spam') |
| 648 |
with self.assertRaises(KeyError): |
| 649 |
repr(od) |
| 650 |
|
| 651 |
def test_dict_popitem(self): |
| 652 |
OrderedDict = self.OrderedDict |
| 653 |
od = OrderedDict() |
| 654 |
od['spam'] = 1 |
| 655 |
od['ham'] = 2 |
| 656 |
dict.popitem(od) |
| 657 |
with self.assertRaises(KeyError): |
| 658 |
repr(od) |
| 659 |
|
| 660 |
def test_dict_setdefault(self): |
| 661 |
OrderedDict = self.OrderedDict |
| 662 |
od = OrderedDict() |
| 663 |
dict.setdefault(od, 'spam', 1) |
| 664 |
self.assertNotIn('NULL', repr(od)) |
| 665 |
|
| 666 |
def test_dict_update(self): |
| 667 |
OrderedDict = self.OrderedDict |
| 668 |
od = OrderedDict() |
| 669 |
dict.update(od, [('spam', 1)]) |
| 670 |
self.assertNotIn('NULL', repr(od)) |
| 671 |
|
| 672 |
def test_reference_loop(self): |
| 673 |
# Issue 25935 |
| 674 |
OrderedDict = self.OrderedDict |
| 675 |
class A: |
| 676 |
od = OrderedDict() |
| 677 |
A.od[A] = None |
| 678 |
r = weakref.ref(A) |
| 679 |
del A |
| 680 |
gc.collect() |
| 681 |
self.assertIsNone(r()) |
| 682 |
|
| 683 |
def test_free_after_iterating(self): |
| 684 |
support.check_free_after_iterating(self, iter, self.OrderedDict) |
| 685 |
support.check_free_after_iterating(self, lambda d: iter(d.keys()), self.OrderedDict) |
| 686 |
support.check_free_after_iterating(self, lambda d: iter(d.values()), self.OrderedDict) |
| 687 |
support.check_free_after_iterating(self, lambda d: iter(d.items()), self.OrderedDict) |
| 688 |
|
| 689 |
def test_merge_operator(self): |
| 690 |
OrderedDict = self.OrderedDict |
| 691 |
|
| 692 |
a = OrderedDict({0: 0, 1: 1, 2: 1}) |
| 693 |
b = OrderedDict({1: 1, 2: 2, 3: 3}) |
| 694 |
|
| 695 |
c = a.copy() |
| 696 |
d = a.copy() |
| 697 |
c |= b |
| 698 |
d |= list(b.items()) |
| 699 |
expected = OrderedDict({0: 0, 1: 1, 2: 2, 3: 3}) |
| 700 |
self.assertEqual(a | dict(b), expected) |
| 701 |
self.assertEqual(a | b, expected) |
| 702 |
self.assertEqual(c, expected) |
| 703 |
self.assertEqual(d, expected) |
| 704 |
|
| 705 |
c = b.copy() |
| 706 |
c |= a |
| 707 |
expected = OrderedDict({1: 1, 2: 1, 3: 3, 0: 0}) |
| 708 |
self.assertEqual(dict(b) | a, expected) |
| 709 |
self.assertEqual(b | a, expected) |
| 710 |
self.assertEqual(c, expected) |
| 711 |
|
| 712 |
self.assertIs(type(a | b), OrderedDict) |
| 713 |
self.assertIs(type(dict(a) | b), OrderedDict) |
| 714 |
self.assertIs(type(a | dict(b)), OrderedDict) |
| 715 |
|
| 716 |
expected = a.copy() |
| 717 |
a |= () |
| 718 |
a |= "" |
| 719 |
self.assertEqual(a, expected) |
| 720 |
|
| 721 |
with self.assertRaises(TypeError): |
| 722 |
a | None |
| 723 |
with self.assertRaises(TypeError): |
| 724 |
a | () |
| 725 |
with self.assertRaises(TypeError): |
| 726 |
a | "BAD" |
| 727 |
with self.assertRaises(TypeError): |
| 728 |
a | "" |
| 729 |
with self.assertRaises(ValueError): |
| 730 |
a |= "BAD" |
| 731 |
|
| 732 |
@support.cpython_only |
| 733 |
def test_ordered_dict_items_result_gc(self): |
| 734 |
# bpo-42536: OrderedDict.items's tuple-reuse speed trick breaks the GC's |
| 735 |
# assumptions about what can be untracked. Make sure we re-track result |
| 736 |
# tuples whenever we reuse them. |
| 737 |
it = iter(self.OrderedDict({None: []}).items()) |
| 738 |
gc.collect() |
| 739 |
# That GC collection probably untracked the recycled internal result |
| 740 |
# tuple, which is initialized to (None, None). Make sure it's re-tracked |
| 741 |
# when it's mutated and returned from __next__: |
| 742 |
self.assertTrue(gc.is_tracked(next(it))) |
| 743 |
|
| 744 |
|
| 745 |
class _TriggerSideEffectOnEqual: |
| 746 |
count = 0 # number of calls to __eq__ |
| 747 |
trigger = 1 # count value when to trigger side effect |
| 748 |
|
| 749 |
def __eq__(self, other): |
| 750 |
if self.__class__.count == self.__class__.trigger: |
| 751 |
self.side_effect() |
| 752 |
self.__class__.count += 1 |
| 753 |
return True |
| 754 |
|
| 755 |
def __hash__(self): |
| 756 |
# all instances represent the same key |
| 757 |
return -1 |
| 758 |
|
| 759 |
def side_effect(self): |
| 760 |
raise NotImplementedError |
| 761 |
|
| 762 |
class PurePythonOrderedDictTests(OrderedDictTests, unittest.TestCase): |
| 763 |
|
| 764 |
module = py_coll |
| 765 |
OrderedDict = py_coll.OrderedDict |
| 766 |
|
| 767 |
def test_issue119004_attribute_error(self): |
| 768 |
class Key(_TriggerSideEffectOnEqual): |
| 769 |
def side_effect(self): |
| 770 |
del dict1[TODEL] |
| 771 |
|
| 772 |
TODEL = Key() |
| 773 |
dict1 = self.OrderedDict(dict.fromkeys((0, TODEL, 4.2))) |
| 774 |
dict2 = self.OrderedDict(dict.fromkeys((0, Key(), 4.2))) |
| 775 |
# This causes an AttributeError due to the linked list being changed |
| 776 |
msg = re.escape("'NoneType' object has no attribute 'key'") |
| 777 |
self.assertRaisesRegex(AttributeError, msg, operator.eq, dict1, dict2) |
| 778 |
self.assertEqual(Key.count, 2) |
| 779 |
self.assertDictEqual(dict1, dict.fromkeys((0, 4.2))) |
| 780 |
self.assertDictEqual(dict2, dict.fromkeys((0, Key(), 4.2))) |
| 781 |
|
| 782 |
|
| 783 |
class CPythonBuiltinDictTests(unittest.TestCase): |
| 784 |
"""Builtin dict preserves insertion order. |
| 785 |
|
| 786 |
Reuse some of tests in OrderedDict selectively. |
| 787 |
""" |
| 788 |
|
| 789 |
module = builtins |
| 790 |
OrderedDict = dict |
| 791 |
|
| 792 |
for method in ( |
| 793 |
"test_init test_update test_abc test_clear test_delitem " + |
| 794 |
"test_setitem test_detect_deletion_during_iteration " + |
| 795 |
"test_popitem test_reinsert test_override_update " + |
| 796 |
"test_highly_nested test_highly_nested_subclass " + |
| 797 |
"test_delitem_hash_collision ").split(): |
| 798 |
setattr(CPythonBuiltinDictTests, method, getattr(OrderedDictTests, method)) |
| 799 |
del method |
| 800 |
|
| 801 |
|
| 802 |
class CPythonOrderedDictSideEffects: |
| 803 |
|
| 804 |
def check_runtime_error_issue119004(self, dict1, dict2): |
| 805 |
msg = re.escape("OrderedDict mutated during iteration") |
| 806 |
self.assertRaisesRegex(RuntimeError, msg, operator.eq, dict1, dict2) |
| 807 |
|
| 808 |
def test_issue119004_change_size_by_clear(self): |
| 809 |
class Key(_TriggerSideEffectOnEqual): |
| 810 |
def side_effect(self): |
| 811 |
dict1.clear() |
| 812 |
|
| 813 |
dict1 = self.OrderedDict(dict.fromkeys((0, Key(), 4.2))) |
| 814 |
dict2 = self.OrderedDict(dict.fromkeys((0, Key(), 4.2))) |
| 815 |
self.check_runtime_error_issue119004(dict1, dict2) |
| 816 |
self.assertEqual(Key.count, 2) |
| 817 |
self.assertDictEqual(dict1, {}) |
| 818 |
self.assertDictEqual(dict2, dict.fromkeys((0, Key(), 4.2))) |
| 819 |
|
| 820 |
def test_issue119004_change_size_by_delete_key(self): |
| 821 |
class Key(_TriggerSideEffectOnEqual): |
| 822 |
def side_effect(self): |
| 823 |
del dict1[TODEL] |
| 824 |
|
| 825 |
TODEL = Key() |
| 826 |
dict1 = self.OrderedDict(dict.fromkeys((0, TODEL, 4.2))) |
| 827 |
dict2 = self.OrderedDict(dict.fromkeys((0, Key(), 4.2))) |
| 828 |
self.check_runtime_error_issue119004(dict1, dict2) |
| 829 |
self.assertEqual(Key.count, 2) |
| 830 |
self.assertDictEqual(dict1, dict.fromkeys((0, 4.2))) |
| 831 |
self.assertDictEqual(dict2, dict.fromkeys((0, Key(), 4.2))) |
| 832 |
|
| 833 |
def test_issue119004_change_linked_list_by_clear(self): |
| 834 |
class Key(_TriggerSideEffectOnEqual): |
| 835 |
def side_effect(self): |
| 836 |
dict1.clear() |
| 837 |
dict1['a'] = dict1['b'] = 'c' |
| 838 |
|
| 839 |
dict1 = self.OrderedDict(dict.fromkeys((0, Key(), 4.2))) |
| 840 |
dict2 = self.OrderedDict(dict.fromkeys((0, Key(), 4.2))) |
| 841 |
self.check_runtime_error_issue119004(dict1, dict2) |
| 842 |
self.assertEqual(Key.count, 2) |
| 843 |
self.assertDictEqual(dict1, dict.fromkeys(('a', 'b'), 'c')) |
| 844 |
self.assertDictEqual(dict2, dict.fromkeys((0, Key(), 4.2))) |
| 845 |
|
| 846 |
def test_issue119004_change_linked_list_by_delete_key(self): |
| 847 |
class Key(_TriggerSideEffectOnEqual): |
| 848 |
def side_effect(self): |
| 849 |
del dict1[TODEL] |
| 850 |
dict1['a'] = 'c' |
| 851 |
|
| 852 |
TODEL = Key() |
| 853 |
dict1 = self.OrderedDict(dict.fromkeys((0, TODEL, 4.2))) |
| 854 |
dict2 = self.OrderedDict(dict.fromkeys((0, Key(), 4.2))) |
| 855 |
self.check_runtime_error_issue119004(dict1, dict2) |
| 856 |
self.assertEqual(Key.count, 2) |
| 857 |
self.assertDictEqual(dict1, {0: None, 'a': 'c', 4.2: None}) |
| 858 |
self.assertDictEqual(dict2, dict.fromkeys((0, Key(), 4.2))) |
| 859 |
|
| 860 |
def test_issue119004_change_size_by_delete_key_in_dict_eq(self): |
| 861 |
class Key(_TriggerSideEffectOnEqual): |
| 862 |
trigger = 0 |
| 863 |
def side_effect(self): |
| 864 |
del dict1[TODEL] |
| 865 |
|
| 866 |
TODEL = Key() |
| 867 |
dict1 = self.OrderedDict(dict.fromkeys((0, TODEL, 4.2))) |
| 868 |
dict2 = self.OrderedDict(dict.fromkeys((0, Key(), 4.2))) |
| 869 |
self.assertEqual(Key.count, 0) |
| 870 |
# the side effect is in dict.__eq__ and modifies the length |
| 871 |
self.assertNotEqual(dict1, dict2) |
| 872 |
self.assertEqual(Key.count, 2) |
| 873 |
self.assertDictEqual(dict1, dict.fromkeys((0, 4.2))) |
| 874 |
self.assertDictEqual(dict2, dict.fromkeys((0, Key(), 4.2))) |
| 875 |
|
| 876 |
|
| 877 |
@unittest.skipUnless(c_coll, 'requires the C version of the collections module') |
| 878 |
class CPythonOrderedDictTests(OrderedDictTests, |
| 879 |
CPythonOrderedDictSideEffects, |
| 880 |
unittest.TestCase): |
| 881 |
|
| 882 |
module = c_coll |
| 883 |
OrderedDict = c_coll.OrderedDict |
| 884 |
check_sizeof = support.check_sizeof |
| 885 |
|
| 886 |
@support.cpython_only |
| 887 |
def test_sizeof_exact(self): |
| 888 |
OrderedDict = self.OrderedDict |
| 889 |
calcsize = struct.calcsize |
| 890 |
size = support.calcobjsize |
| 891 |
check = self.check_sizeof |
| 892 |
|
| 893 |
basicsize = size('nQ2P' + '3PnPn2P') |
| 894 |
keysize = calcsize('n2BI2n') |
| 895 |
|
| 896 |
entrysize = calcsize('n2P') |
| 897 |
p = calcsize('P') |
| 898 |
nodesize = calcsize('Pn2P') |
| 899 |
|
| 900 |
od = OrderedDict() |
| 901 |
check(od, basicsize) # 8byte indices + 8*2//3 * entry table |
| 902 |
od.x = 1 |
| 903 |
check(od, basicsize) |
| 904 |
od.update([(i, i) for i in range(3)]) |
| 905 |
check(od, basicsize + keysize + 8*p + 8 + 5*entrysize + 3*nodesize) |
| 906 |
od.update([(i, i) for i in range(3, 10)]) |
| 907 |
check(od, basicsize + keysize + 16*p + 16 + 10*entrysize + 10*nodesize) |
| 908 |
|
| 909 |
check(od.keys(), size('P')) |
| 910 |
check(od.items(), size('P')) |
| 911 |
check(od.values(), size('P')) |
| 912 |
|
| 913 |
itersize = size('iP2n2P') |
| 914 |
check(iter(od), itersize) |
| 915 |
check(iter(od.keys()), itersize) |
| 916 |
check(iter(od.items()), itersize) |
| 917 |
check(iter(od.values()), itersize) |
| 918 |
|
| 919 |
def test_key_change_during_iteration(self): |
| 920 |
OrderedDict = self.OrderedDict |
| 921 |
|
| 922 |
od = OrderedDict.fromkeys('abcde') |
| 923 |
self.assertEqual(list(od), list('abcde')) |
| 924 |
with self.assertRaises(RuntimeError): |
| 925 |
for i, k in enumerate(od): |
| 926 |
od.move_to_end(k) |
| 927 |
self.assertLess(i, 5) |
| 928 |
with self.assertRaises(RuntimeError): |
| 929 |
for k in od: |
| 930 |
od['f'] = None |
| 931 |
with self.assertRaises(RuntimeError): |
| 932 |
for k in od: |
| 933 |
del od['c'] |
| 934 |
self.assertEqual(list(od), list('bdeaf')) |
| 935 |
|
| 936 |
def test_iterators_pickling(self): |
| 937 |
OrderedDict = self.OrderedDict |
| 938 |
pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] |
| 939 |
od = OrderedDict(pairs) |
| 940 |
|
| 941 |
for method_name in ('keys', 'values', 'items'): |
| 942 |
meth = getattr(od, method_name) |
| 943 |
expected = list(meth())[1:] |
| 944 |
for i in range(pickle.HIGHEST_PROTOCOL + 1): |
| 945 |
with self.subTest(method_name=method_name, protocol=i): |
| 946 |
it = iter(meth()) |
| 947 |
next(it) |
| 948 |
p = pickle.dumps(it, i) |
| 949 |
unpickled = pickle.loads(p) |
| 950 |
self.assertEqual(list(unpickled), expected) |
| 951 |
self.assertEqual(list(it), expected) |
| 952 |
|
| 953 |
@support.cpython_only |
| 954 |
def test_weakref_list_is_not_traversed(self): |
| 955 |
# Check that the weakref list is not traversed when collecting |
| 956 |
# OrderedDict objects. See bpo-39778 for more information. |
| 957 |
|
| 958 |
gc.collect() |
| 959 |
|
| 960 |
x = self.OrderedDict() |
| 961 |
x.cycle = x |
| 962 |
|
| 963 |
cycle = [] |
| 964 |
cycle.append(cycle) |
| 965 |
|
| 966 |
x_ref = weakref.ref(x) |
| 967 |
cycle.append(x_ref) |
| 968 |
|
| 969 |
del x, cycle, x_ref |
| 970 |
|
| 971 |
gc.collect() |
| 972 |
|
| 973 |
|
| 974 |
class PurePythonOrderedDictSubclassTests(PurePythonOrderedDictTests): |
| 975 |
|
| 976 |
module = py_coll |
| 977 |
class OrderedDict(py_coll.OrderedDict): |
| 978 |
pass |
| 979 |
|
| 980 |
|
| 981 |
class CPythonOrderedDictSubclassTests(CPythonOrderedDictTests): |
| 982 |
|
| 983 |
module = c_coll |
| 984 |
class OrderedDict(c_coll.OrderedDict): |
| 985 |
pass |
| 986 |
|
| 987 |
|
| 988 |
class PurePythonOrderedDictWithSlotsCopyingTests(unittest.TestCase): |
| 989 |
|
| 990 |
module = py_coll |
| 991 |
class OrderedDict(py_coll.OrderedDict): |
| 992 |
__slots__ = ('x', 'y') |
| 993 |
test_copying = OrderedDictTests.test_copying |
| 994 |
|
| 995 |
|
| 996 |
@unittest.skipUnless(c_coll, 'requires the C version of the collections module') |
| 997 |
class CPythonOrderedDictWithSlotsCopyingTests(unittest.TestCase): |
| 998 |
|
| 999 |
module = c_coll |
| 1000 |
class OrderedDict(c_coll.OrderedDict): |
| 1001 |
__slots__ = ('x', 'y') |
| 1002 |
test_copying = OrderedDictTests.test_copying |
| 1003 |
|
| 1004 |
|
| 1005 |
class PurePythonGeneralMappingTests(mapping_tests.BasicTestMappingProtocol): |
| 1006 |
|
| 1007 |
@classmethod |
| 1008 |
def setUpClass(cls): |
| 1009 |
cls.type2test = py_coll.OrderedDict |
| 1010 |
|
| 1011 |
def test_popitem(self): |
| 1012 |
d = self._empty_mapping() |
| 1013 |
self.assertRaises(KeyError, d.popitem) |
| 1014 |
|
| 1015 |
|
| 1016 |
@unittest.skipUnless(c_coll, 'requires the C version of the collections module') |
| 1017 |
class CPythonGeneralMappingTests(mapping_tests.BasicTestMappingProtocol): |
| 1018 |
|
| 1019 |
@classmethod |
| 1020 |
def setUpClass(cls): |
| 1021 |
cls.type2test = c_coll.OrderedDict |
| 1022 |
|
| 1023 |
def test_popitem(self): |
| 1024 |
d = self._empty_mapping() |
| 1025 |
self.assertRaises(KeyError, d.popitem) |
| 1026 |
|
| 1027 |
|
| 1028 |
class PurePythonSubclassMappingTests(mapping_tests.BasicTestMappingProtocol): |
| 1029 |
|
| 1030 |
@classmethod |
| 1031 |
def setUpClass(cls): |
| 1032 |
class MyOrderedDict(py_coll.OrderedDict): |
| 1033 |
pass |
| 1034 |
cls.type2test = MyOrderedDict |
| 1035 |
|
| 1036 |
def test_popitem(self): |
| 1037 |
d = self._empty_mapping() |
| 1038 |
self.assertRaises(KeyError, d.popitem) |
| 1039 |
|
| 1040 |
|
| 1041 |
@unittest.skipUnless(c_coll, 'requires the C version of the collections module') |
| 1042 |
class CPythonSubclassMappingTests(mapping_tests.BasicTestMappingProtocol): |
| 1043 |
|
| 1044 |
@classmethod |
| 1045 |
def setUpClass(cls): |
| 1046 |
class MyOrderedDict(c_coll.OrderedDict): |
| 1047 |
pass |
| 1048 |
cls.type2test = MyOrderedDict |
| 1049 |
|
| 1050 |
def test_popitem(self): |
| 1051 |
d = self._empty_mapping() |
| 1052 |
self.assertRaises(KeyError, d.popitem) |
| 1053 |
|
| 1054 |
|
| 1055 |
class SimpleLRUCache: |
| 1056 |
|
| 1057 |
def __init__(self, size): |
| 1058 |
super().__init__() |
| 1059 |
self.size = size |
| 1060 |
self.counts = dict.fromkeys(('get', 'set', 'del'), 0) |
| 1061 |
|
| 1062 |
def __getitem__(self, item): |
| 1063 |
self.counts['get'] += 1 |
| 1064 |
value = super().__getitem__(item) |
| 1065 |
self.move_to_end(item) |
| 1066 |
return value |
| 1067 |
|
| 1068 |
def __setitem__(self, key, value): |
| 1069 |
self.counts['set'] += 1 |
| 1070 |
while key not in self and len(self) >= self.size: |
| 1071 |
self.popitem(last=False) |
| 1072 |
super().__setitem__(key, value) |
| 1073 |
self.move_to_end(key) |
| 1074 |
|
| 1075 |
def __delitem__(self, key): |
| 1076 |
self.counts['del'] += 1 |
| 1077 |
super().__delitem__(key) |
| 1078 |
|
| 1079 |
|
| 1080 |
class SimpleLRUCacheTests: |
| 1081 |
|
| 1082 |
def test_add_after_full(self): |
| 1083 |
c = self.type2test(2) |
| 1084 |
c['t1'] = 1 |
| 1085 |
c['t2'] = 2 |
| 1086 |
c['t3'] = 3 |
| 1087 |
self.assertEqual(c.counts, {'get': 0, 'set': 3, 'del': 0}) |
| 1088 |
self.assertEqual(list(c), ['t2', 't3']) |
| 1089 |
self.assertEqual(c.counts, {'get': 0, 'set': 3, 'del': 0}) |
| 1090 |
|
| 1091 |
def test_popitem(self): |
| 1092 |
c = self.type2test(3) |
| 1093 |
for i in range(1, 4): |
| 1094 |
c[i] = i |
| 1095 |
self.assertEqual(c.popitem(last=False), (1, 1)) |
| 1096 |
self.assertEqual(c.popitem(last=True), (3, 3)) |
| 1097 |
self.assertEqual(c.counts, {'get': 0, 'set': 3, 'del': 0}) |
| 1098 |
|
| 1099 |
def test_pop(self): |
| 1100 |
c = self.type2test(3) |
| 1101 |
for i in range(1, 4): |
| 1102 |
c[i] = i |
| 1103 |
self.assertEqual(c.counts, {'get': 0, 'set': 3, 'del': 0}) |
| 1104 |
self.assertEqual(c.pop(2), 2) |
| 1105 |
self.assertEqual(c.counts, {'get': 0, 'set': 3, 'del': 0}) |
| 1106 |
self.assertEqual(c.pop(4, 0), 0) |
| 1107 |
self.assertEqual(c.counts, {'get': 0, 'set': 3, 'del': 0}) |
| 1108 |
self.assertRaises(KeyError, c.pop, 4) |
| 1109 |
self.assertEqual(c.counts, {'get': 0, 'set': 3, 'del': 0}) |
| 1110 |
|
| 1111 |
def test_change_order_on_get(self): |
| 1112 |
c = self.type2test(3) |
| 1113 |
for i in range(1, 4): |
| 1114 |
c[i] = i |
| 1115 |
self.assertEqual(list(c), list(range(1, 4))) |
| 1116 |
self.assertEqual(c.counts, {'get': 0, 'set': 3, 'del': 0}) |
| 1117 |
self.assertEqual(c[2], 2) |
| 1118 |
self.assertEqual(c.counts, {'get': 1, 'set': 3, 'del': 0}) |
| 1119 |
self.assertEqual(list(c), [1, 3, 2]) |
| 1120 |
|
| 1121 |
|
| 1122 |
class PySimpleLRUCacheTests(SimpleLRUCacheTests, unittest.TestCase): |
| 1123 |
|
| 1124 |
class type2test(SimpleLRUCache, py_coll.OrderedDict): |
| 1125 |
pass |
| 1126 |
|
| 1127 |
|
| 1128 |
@unittest.skipUnless(c_coll, 'requires the C version of the collections module') |
| 1129 |
class CSimpleLRUCacheTests(SimpleLRUCacheTests, unittest.TestCase): |
| 1130 |
|
| 1131 |
@classmethod |
| 1132 |
def setUpClass(cls): |
| 1133 |
class type2test(SimpleLRUCache, c_coll.OrderedDict): |
| 1134 |
pass |
| 1135 |
cls.type2test = type2test |
| 1136 |
|
| 1137 |
|
| 1138 |
if __name__ == "__main__": |
| 1139 |
unittest.main() |