bernsteinbear.com
this repo has no description
1// Copyright (c) Facebook, Inc. and its affiliates. (http://www.facebook.com)
2#include "dict-builtins.h"
3
4#include "gtest/gtest.h"
5
6#include "builtins-module.h"
7#include "builtins.h"
8#include "int-builtins.h"
9#include "runtime.h"
10#include "str-builtins.h"
11#include "test-utils.h"
12
13namespace py {
14namespace testing {
15
16using DictBuiltinsTest = RuntimeFixture;
17using DictItemIteratorBuiltinsTest = RuntimeFixture;
18using DictItemsBuiltinsTest = RuntimeFixture;
19using DictKeyIteratorBuiltinsTest = RuntimeFixture;
20using DictKeysBuiltinsTest = RuntimeFixture;
21using DictValueIteratorBuiltinsTest = RuntimeFixture;
22using DictValuesBuiltinsTest = RuntimeFixture;
23
24TEST_F(DictBuiltinsTest, EmptyDictInvariants) {
25 HandleScope scope(thread_);
26 Dict dict(&scope, runtime_->newDict());
27
28 EXPECT_EQ(dict.numItems(), 0);
29 ASSERT_TRUE(isIntEqualsWord(dict.data(), 0));
30}
31
32TEST_F(DictBuiltinsTest, DictAtPutRetainsExistingKeyObject) {
33 HandleScope scope(thread_);
34 Dict dict(&scope, runtime_->newDict());
35 Str key0(&scope, runtime_->newStrFromCStr("foobarbazbam"));
36 word key0_hash = strHash(thread_, *key0);
37 Object value0(&scope, SmallInt::fromWord(123));
38 Str key1(&scope, runtime_->newStrFromCStr("foobarbazbam"));
39 word key1_hash = strHash(thread_, *key1);
40 Object value1(&scope, SmallInt::fromWord(456));
41 ASSERT_NE(key0, key1);
42 ASSERT_EQ(key0_hash, key1_hash);
43
44 ASSERT_TRUE(dictAtPut(thread_, dict, key0, key0_hash, value0).isNoneType());
45 ASSERT_EQ(dict.numItems(), 1);
46 ASSERT_EQ(dictAt(thread_, dict, key0, key0_hash), *value0);
47
48 // Overwrite the stored value
49 ASSERT_TRUE(dictAtPut(thread_, dict, key1, key1_hash, value1).isNoneType());
50 ASSERT_EQ(dict.numItems(), 1);
51 ASSERT_EQ(dictAt(thread_, dict, key1, key1_hash), *value1);
52
53 word i = 0;
54 Object key(&scope, NoneType::object());
55 ASSERT_TRUE(dictNextKey(dict, &i, &key));
56 EXPECT_EQ(key, key0);
57}
58
59TEST_F(DictBuiltinsTest, GetSet) {
60 HandleScope scope(thread_);
61 Dict dict(&scope, runtime_->newDict());
62 Object key(&scope, SmallInt::fromWord(12345));
63 word hash = intHash(*key);
64
65 // Looking up a key that doesn't exist should fail
66 EXPECT_TRUE(dictAt(thread_, dict, key, hash).isError());
67
68 // Store a value
69 Object stored(&scope, SmallInt::fromWord(67890));
70 ASSERT_TRUE(dictAtPut(thread_, dict, key, hash, stored).isNoneType());
71 EXPECT_EQ(dict.numItems(), 1);
72
73 // Retrieve the stored value
74 RawObject retrieved = dictAt(thread_, dict, key, hash);
75 EXPECT_EQ(retrieved, *stored);
76
77 // Overwrite the stored value
78 Object new_value(&scope, SmallInt::fromWord(5555));
79 ASSERT_TRUE(dictAtPut(thread_, dict, key, hash, new_value).isNoneType());
80 EXPECT_EQ(dict.numItems(), 1);
81
82 // Get the new value
83 retrieved = dictAt(thread_, dict, key, hash);
84 EXPECT_EQ(retrieved, *new_value);
85}
86
87TEST_F(DictBuiltinsTest, Remove) {
88 HandleScope scope(thread_);
89 Dict dict(&scope, runtime_->newDict());
90 Object key(&scope, SmallInt::fromWord(12345));
91 word hash = intHash(*key);
92
93 // Removing a key that doesn't exist should fail
94 bool is_missing = dictRemove(thread_, dict, key, hash).isError();
95 EXPECT_TRUE(is_missing);
96
97 // Removing a key that exists should succeed and return the value that was
98 // stored.
99 Object stored(&scope, SmallInt::fromWord(54321));
100
101 ASSERT_TRUE(dictAtPut(thread_, dict, key, hash, stored).isNoneType());
102 EXPECT_EQ(dict.numItems(), 1);
103
104 RawObject retrieved = dictRemove(thread_, dict, key, hash);
105 ASSERT_FALSE(retrieved.isError());
106 ASSERT_EQ(SmallInt::cast(retrieved).value(), SmallInt::cast(*stored).value());
107
108 // Looking up a key that was deleted should fail
109 EXPECT_TRUE(dictAt(thread_, dict, key, hash).isError());
110 EXPECT_EQ(dict.numItems(), 0);
111}
112
113TEST_F(DictBuiltinsTest, Length) {
114 HandleScope scope(thread_);
115 Dict dict(&scope, runtime_->newDict());
116
117 // Add 10 items and make sure length reflects it
118 for (int i = 0; i < 10; i++) {
119 Object key(&scope, SmallInt::fromWord(i));
120 word hash = intHash(*key);
121 ASSERT_TRUE(dictAtPut(thread_, dict, key, hash, key).isNoneType());
122 }
123 EXPECT_EQ(dict.numItems(), 10);
124
125 // Remove half the items
126 for (int i = 0; i < 5; i++) {
127 Object key(&scope, SmallInt::fromWord(i));
128 word hash = intHash(*key);
129 ASSERT_FALSE(dictRemove(thread_, dict, key, hash).isError());
130 }
131 EXPECT_EQ(dict.numItems(), 5);
132}
133
134TEST_F(DictBuiltinsTest, DictAtPutInValueCellByStrCreatesValueCell) {
135 HandleScope scope(thread_);
136 Dict dict(&scope, runtime_->newDict());
137 Object name(&scope, Runtime::internStrFromCStr(thread_, "foo"));
138 Object value(&scope, Runtime::internStrFromCStr(thread_, "bar"));
139 Object result(&scope, dictAtPutInValueCellByStr(thread_, dict, name, value));
140 ASSERT_TRUE(result.isValueCell());
141 EXPECT_EQ(ValueCell::cast(*result).value(), value);
142 EXPECT_EQ(dictAtByStr(thread_, dict, name), result);
143}
144
145TEST_F(DictBuiltinsTest, DictAtPutInValueCellByStrReusesExistingValueCell) {
146 HandleScope scope(thread_);
147 Dict dict(&scope, runtime_->newDict());
148 Object name(&scope, Runtime::internStrFromCStr(thread_, "foo"));
149 Object value0(&scope, Runtime::internStrFromCStr(thread_, "bar"));
150 Object result0(&scope,
151 dictAtPutInValueCellByStr(thread_, dict, name, value0));
152 ASSERT_TRUE(result0.isValueCell());
153 EXPECT_EQ(ValueCell::cast(*result0).value(), value0);
154
155 Object value1(&scope, Runtime::internStrFromCStr(thread_, "baz"));
156 Object result1(&scope,
157 dictAtPutInValueCellByStr(thread_, dict, name, value1));
158 EXPECT_EQ(result0, result1);
159 EXPECT_EQ(dictAtByStr(thread_, dict, name), result1);
160 EXPECT_EQ(ValueCell::cast(*result1).value(), value1);
161}
162
163// Should be synced with dict-builtins.cpp.
164static const word kInitialDictIndicesLength = 8;
165static const word kItemNumPointers = 3;
166
167TEST_F(DictBuiltinsTest, DictAtPutGrowsDictWhenDictIsEmpty) {
168 HandleScope scope(thread_);
169 Dict dict(&scope, runtime_->newDict());
170 EXPECT_EQ(dict.numIndices(), 0);
171
172 Object first_key(&scope, SmallInt::fromWord(0));
173 word hash = intHash(*first_key);
174 Object first_value(&scope, SmallInt::fromWord(1));
175 ASSERT_TRUE(
176 dictAtPut(thread_, dict, first_key, hash, first_value).isNoneType());
177
178 word initial_capacity = kInitialDictIndicesLength;
179 EXPECT_EQ(dict.numItems(), 1);
180 EXPECT_EQ(dict.numIndices(), initial_capacity);
181}
182
183TEST_F(DictBuiltinsTest, DictAtPutGrowsDictWhenTwoThirdsUsed) {
184 HandleScope scope(thread_);
185 Dict dict(&scope, runtime_->newDict());
186
187 // Fill in one fewer keys than would require growing the underlying object
188 // array again.
189 word threshold = ((kInitialDictIndicesLength * 2) / 3) - 1;
190 for (word i = 0; i < threshold; i++) {
191 Object key(&scope, SmallInt::fromWord(i));
192 word hash = intHash(*key);
193 Object value(&scope, SmallInt::fromWord(-i));
194 ASSERT_TRUE(dictAtPut(thread_, dict, key, hash, value).isNoneType());
195 }
196 EXPECT_EQ(dict.numItems(), threshold);
197 EXPECT_EQ(dict.firstEmptyItemIndex() / kItemNumPointers, threshold);
198 word initial_capacity = kInitialDictIndicesLength;
199 EXPECT_EQ(dict.numIndices(), initial_capacity);
200
201 // Add another key which should force us to double the capacity
202 Object last_key(&scope, SmallInt::fromWord(threshold));
203 word last_key_hash = intHash(*last_key);
204 Object last_value(&scope, SmallInt::fromWord(-threshold));
205 ASSERT_TRUE(dictAtPut(thread_, dict, last_key, last_key_hash, last_value)
206 .isNoneType());
207 EXPECT_EQ(dict.numItems(), threshold + 1);
208 // 2 == kDictGrowthFactor.
209 EXPECT_EQ(dict.numIndices(), initial_capacity * 2);
210 EXPECT_EQ(dict.firstEmptyItemIndex() / kItemNumPointers, threshold + 1);
211
212 // Make sure we can still read all the stored keys/values.
213 for (word i = 0; i <= threshold; i++) {
214 Object key(&scope, SmallInt::fromWord(i));
215 word hash = intHash(*key);
216 RawObject value = dictAt(thread_, dict, key, hash);
217 ASSERT_FALSE(value.isError());
218 EXPECT_TRUE(isIntEqualsWord(value, -i));
219 }
220}
221
222TEST_F(DictBuiltinsTest, CollidingKeys) {
223 HandleScope scope(thread_);
224 ASSERT_FALSE(runFromCStr(runtime_, R"(
225class C:
226 def __eq__(self, other):
227 return self is other
228 def __hash__(self):
229 return 0
230i0 = C()
231i1 = C()
232)")
233 .isError());
234 Object i0(&scope, mainModuleAt(runtime_, "i0"));
235 Object i0_hash_obj(&scope, Interpreter::hash(thread_, i0));
236 ASSERT_FALSE(i0_hash_obj.isErrorException());
237 word i0_hash = SmallInt::cast(*i0_hash_obj).value();
238 Object i1(&scope, mainModuleAt(runtime_, "i1"));
239 Object i1_hash_obj(&scope, Interpreter::hash(thread_, i1));
240 ASSERT_FALSE(i1_hash_obj.isErrorException());
241 word i1_hash = SmallInt::cast(*i1_hash_obj).value();
242 ASSERT_EQ(i0_hash, i1_hash);
243
244 Dict dict(&scope, runtime_->newDict());
245
246 // Add two different keys with different values using the same hash
247 ASSERT_TRUE(dictAtPut(thread_, dict, i0, i0_hash, i0).isNoneType());
248 ASSERT_TRUE(dictAtPut(thread_, dict, i1, i1_hash, i1).isNoneType());
249
250 // Make sure we get both back
251 Object retrieved(&scope, dictAt(thread_, dict, i0, i0_hash));
252 EXPECT_EQ(retrieved, i0);
253
254 retrieved = dictAt(thread_, dict, i1, i1_hash);
255 EXPECT_EQ(retrieved, i1);
256}
257
258TEST_F(DictBuiltinsTest, MixedKeys) {
259 HandleScope scope(thread_);
260 Dict dict(&scope, runtime_->newDict());
261
262 // Add keys of different type
263 Object int_key(&scope, SmallInt::fromWord(100));
264 word int_key_hash = intHash(*int_key);
265 ASSERT_TRUE(
266 dictAtPut(thread_, dict, int_key, int_key_hash, int_key).isNoneType());
267
268 Object str_key(&scope, runtime_->newStrFromCStr("testing 123"));
269 word str_key_hash = strHash(thread_, *str_key);
270 ASSERT_TRUE(
271 dictAtPut(thread_, dict, str_key, str_key_hash, str_key).isNoneType());
272
273 // Make sure we get the appropriate values back out
274 RawObject retrieved = dictAt(thread_, dict, int_key, int_key_hash);
275 EXPECT_EQ(retrieved, *int_key);
276
277 retrieved = dictAt(thread_, dict, str_key, str_key_hash);
278 ASSERT_TRUE(retrieved.isStr());
279 EXPECT_EQ(*str_key, retrieved);
280}
281
282TEST_F(DictBuiltinsTest, GetKeys) {
283 HandleScope scope(thread_);
284
285 // Create keys
286 Object obj1(&scope, SmallInt::fromWord(100));
287 Object obj2(&scope, runtime_->newStrFromCStr("testing 123"));
288 Object obj3(&scope, Bool::trueObj());
289 Object obj4(&scope, NoneType::object());
290 Tuple keys(&scope, runtime_->newTupleWith4(obj1, obj2, obj3, obj4));
291
292 // Add keys to dict
293 Dict dict(&scope, runtime_->newDict());
294 for (word i = 0; i < keys.length(); i++) {
295 Object key(&scope, keys.at(i));
296 Object hash_obj(&scope, Interpreter::hash(thread_, key));
297 ASSERT_FALSE(hash_obj.isErrorException());
298 word hash = SmallInt::cast(*hash_obj).value();
299 ASSERT_TRUE(dictAtPut(thread_, dict, key, hash, key).isNoneType());
300 }
301
302 // Grab the keys and verify everything is there
303 List retrieved(&scope, dictKeys(thread_, dict));
304 ASSERT_EQ(retrieved.numItems(), keys.length());
305 for (word i = 0; i < keys.length(); i++) {
306 Object key(&scope, keys.at(i));
307 EXPECT_TRUE(listContains(retrieved, key)) << " missing key " << i;
308 }
309}
310
311TEST_F(DictBuiltinsTest, CanCreateDictItems) {
312 HandleScope scope(thread_);
313 Dict dict(&scope, runtime_->newDict());
314 RawObject iter = runtime_->newDictItemIterator(thread_, dict);
315 ASSERT_TRUE(iter.isDictItemIterator());
316}
317
318TEST_F(DictBuiltinsTest, DictAtGrowsToInitialCapacity) {
319 HandleScope scope(thread_);
320 Dict dict(&scope, runtime_->newDict());
321 EXPECT_EQ(dict.numIndices(), 0);
322
323 Object key(&scope, runtime_->newInt(123));
324 word hash = intHash(*key);
325 Object value(&scope, runtime_->newInt(456));
326 ASSERT_TRUE(dictAtPut(thread_, dict, key, hash, value).isNoneType());
327 int expected = kInitialDictIndicesLength;
328 EXPECT_EQ(dict.numIndices(), expected);
329}
330
331TEST_F(DictBuiltinsTest, ClearWithEmptyDictIsNoop) {
332 HandleScope scope(thread_);
333 Dict dict(&scope, runtime_->newDict());
334 EXPECT_EQ(runBuiltin(METH(dict, clear), dict), NoneType::object());
335}
336
337TEST_F(DictBuiltinsTest, ClearWithNonEmptyDictRemovesAllElements) {
338 ASSERT_FALSE(runFromCStr(runtime_, R"(
339class C:
340 pass
341d = {'a': C()}
342)")
343 .isError());
344
345 HandleScope scope(thread_);
346 Dict dict(&scope, mainModuleAt(runtime_, "d"));
347 Object ref_obj(&scope, NoneType::object());
348 {
349 Str key(&scope, runtime_->newStrFromCStr("a"));
350 Object c(&scope, dictAtByStr(thread_, dict, key));
351 ref_obj = runtime_->newWeakRef(thread_, c);
352 }
353 WeakRef ref(&scope, *ref_obj);
354 EXPECT_NE(ref.referent(), NoneType::object());
355 runBuiltin(METH(dict, clear), dict);
356 runtime_->collectGarbage();
357 EXPECT_EQ(ref.referent(), NoneType::object());
358}
359
360TEST_F(DictBuiltinsTest, CopyWithDictReturnsNewInstance) {
361 ASSERT_FALSE(runFromCStr(runtime_, R"(
362d = {'a': 3}
363result = dict.copy(d)
364)")
365 .isError());
366 HandleScope scope(thread_);
367 Object dict(&scope, mainModuleAt(runtime_, "d"));
368 EXPECT_TRUE(dict.isDict());
369 Object result_obj(&scope, mainModuleAt(runtime_, "result"));
370 EXPECT_TRUE(result_obj.isDict());
371 Dict result(&scope, *result_obj);
372 EXPECT_NE(*dict, *result);
373 EXPECT_EQ(result.numItems(), 1);
374 EXPECT_EQ(result.firstEmptyItemIndex() / kItemNumPointers, 1);
375}
376
377TEST_F(DictBuiltinsTest, DunderContainsWithExistingKeyReturnsTrue) {
378 ASSERT_FALSE(runFromCStr(runtime_, "result = {'foo': 0}.__contains__('foo')")
379 .isError());
380 HandleScope scope(thread_);
381 Object result(&scope, mainModuleAt(runtime_, "result"));
382 ASSERT_TRUE(result.isBool());
383 EXPECT_TRUE(Bool::cast(*result).value());
384}
385
386TEST_F(DictBuiltinsTest, DunderContainsWithNonexistentKeyReturnsFalse) {
387 ASSERT_FALSE(
388 runFromCStr(runtime_, "result = {}.__contains__('foo')").isError());
389 HandleScope scope(thread_);
390 Object result(&scope, mainModuleAt(runtime_, "result"));
391 ASSERT_TRUE(result.isBool());
392 EXPECT_FALSE(Bool::cast(*result).value());
393}
394
395TEST_F(DictBuiltinsTest, DunderContainsWithUnhashableTypeRaisesTypeError) {
396 ASSERT_FALSE(runFromCStr(runtime_, R"(
397class C:
398 __hash__ = None
399c = C()
400)")
401 .isError());
402 EXPECT_TRUE(raised(runFromCStr(runtime_, "{}.__contains__(C())"),
403 LayoutId::kTypeError));
404}
405
406TEST_F(DictBuiltinsTest,
407 DunderContainsWithNonCallableDunderHashRaisesTypeError) {
408 ASSERT_FALSE(runFromCStr(runtime_, R"(
409class C:
410 __hash__ = 4
411)")
412 .isError());
413 EXPECT_TRUE(raised(runFromCStr(runtime_, "{}.__contains__(C())"),
414 LayoutId::kTypeError));
415}
416
417TEST_F(DictBuiltinsTest,
418 DunderContainsWithTypeWithDunderHashReturningNonIntRaisesTypeError) {
419 ASSERT_FALSE(runFromCStr(runtime_, R"(
420class C:
421 def __hash__(self):
422 return "boo"
423)")
424 .isError());
425 EXPECT_TRUE(raised(runFromCStr(runtime_, "{}.__contains__(C())"),
426 LayoutId::kTypeError));
427}
428
429TEST_F(DictBuiltinsTest, InWithExistingKeyReturnsTrue) {
430 ASSERT_FALSE(runFromCStr(runtime_, R"(
431d = {"foo": 1}
432foo_in_d = "foo" in d
433)")
434 .isError());
435 HandleScope scope(thread_);
436 Bool foo_in_d(&scope, mainModuleAt(runtime_, "foo_in_d"));
437
438 EXPECT_TRUE(foo_in_d.value());
439}
440
441TEST_F(DictBuiltinsTest, InWithNonexistentKeyReturnsFalse) {
442 ASSERT_FALSE(runFromCStr(runtime_, R"(
443d = {}
444foo_in_d = "foo" in d
445)")
446 .isError());
447 HandleScope scope(thread_);
448 Bool foo_in_d(&scope, mainModuleAt(runtime_, "foo_in_d"));
449
450 EXPECT_FALSE(foo_in_d.value());
451}
452
453TEST_F(DictBuiltinsTest, DunderDelitemOnExistingKeyReturnsNone) {
454 HandleScope scope(thread_);
455 Dict dict(&scope, runtime_->newDictWithSize(1));
456 Str key(&scope, runtime_->newStrFromCStr("foo"));
457 Object val(&scope, runtime_->newInt(0));
458 dictAtPutByStr(thread_, dict, key, val);
459 RawObject result = runBuiltin(METH(dict, __delitem__), dict, key);
460 EXPECT_TRUE(result.isNoneType());
461}
462
463TEST_F(DictBuiltinsTest, DunderDelitemOnNonexistentKeyRaisesKeyError) {
464 HandleScope scope(thread_);
465 Dict dict(&scope, runtime_->newDictWithSize(1));
466 Str key(&scope, runtime_->newStrFromCStr("foo"));
467 Object val(&scope, runtime_->newInt(0));
468 dictAtPutByStr(thread_, dict, key, val);
469
470 // "bar" doesn't exist in this dictionary, attempting to delete it should
471 // cause a KeyError.
472 Object key2(&scope, runtime_->newStrFromCStr("bar"));
473 RawObject result = runBuiltin(METH(dict, __delitem__), dict, key2);
474 ASSERT_TRUE(result.isError());
475}
476
477TEST_F(DictBuiltinsTest, DelOnObjectHashReturningNonIntRaisesTypeError) {
478 EXPECT_TRUE(raisedWithStr(runFromCStr(runtime_, R"(
479class E:
480 def __hash__(self): return "non int"
481
482d = {}
483del d[E()]
484)"),
485 LayoutId::kTypeError,
486 "__hash__ method should return an integer"));
487}
488
489TEST_F(DictBuiltinsTest, DelOnExistingKeyDeletesKey) {
490 ASSERT_FALSE(runFromCStr(runtime_, R"(
491d = {"foo": 1}
492del d["foo"]
493)")
494 .isError());
495 HandleScope scope(thread_);
496 Dict d(&scope, mainModuleAt(runtime_, "d"));
497 Str foo(&scope, runtime_->newStrFromCStr("foo"));
498
499 EXPECT_EQ(dictIncludes(thread_, d, foo, strHash(thread_, *foo)),
500 Bool::falseObj());
501}
502
503TEST_F(DictBuiltinsTest, DelOnNonexistentKeyRaisesKeyError) {
504 EXPECT_TRUE(raisedWithStr(runFromCStr(runtime_, R"(
505d = {}
506del d["foo"]
507)"),
508 LayoutId::kKeyError, "foo"));
509}
510
511TEST_F(DictBuiltinsTest, NonTypeInDunderNew) {
512 EXPECT_TRUE(raisedWithStr(runFromCStr(runtime_, R"(
513dict.__new__(1)
514)"),
515 LayoutId::kTypeError, "not a type object"));
516}
517
518TEST_F(DictBuiltinsTest, NonSubclassInDunderNew) {
519 EXPECT_TRUE(raisedWithStr(runFromCStr(runtime_, R"(
520class Foo: pass
521dict.__new__(Foo)
522)"),
523 LayoutId::kTypeError, "not a subtype of dict"));
524}
525
526TEST_F(DictBuiltinsTest, DunderNewConstructsDict) {
527 HandleScope scope(thread_);
528 Type type(&scope, runtime_->typeAt(LayoutId::kDict));
529 Object result(&scope, runBuiltin(METH(dict, __new__), type));
530 ASSERT_TRUE(result.isDict());
531}
532
533TEST_F(DictBuiltinsTest, DunderIterReturnsDictKeyIter) {
534 HandleScope scope(thread_);
535 Dict dict(&scope, runtime_->newDict());
536 Object iter(&scope, runBuiltin(METH(dict, __iter__), dict));
537 ASSERT_TRUE(iter.isDictKeyIterator());
538}
539
540TEST_F(DictBuiltinsTest, DunderItemsReturnsDictItems) {
541 HandleScope scope(thread_);
542 Dict dict(&scope, runtime_->newDict());
543 Object items(&scope, runBuiltin(METH(dict, items), dict));
544 ASSERT_TRUE(items.isDictItems());
545}
546
547TEST_F(DictBuiltinsTest, KeysReturnsDictKeys) {
548 HandleScope scope(thread_);
549 Dict dict(&scope, runtime_->newDict());
550 Object keys(&scope, runBuiltin(METH(dict, keys), dict));
551 ASSERT_TRUE(keys.isDictKeys());
552}
553
554TEST_F(DictBuiltinsTest, ValuesReturnsDictValues) {
555 HandleScope scope(thread_);
556 Dict dict(&scope, runtime_->newDict());
557 Object values(&scope, runBuiltin(METH(dict, values), dict));
558 ASSERT_TRUE(values.isDictValues());
559}
560
561TEST_F(DictBuiltinsTest, UpdateWithNoArgumentsRaisesTypeError) {
562 EXPECT_TRUE(raisedWithStr(
563 runFromCStr(runtime_, "dict.update()"), LayoutId::kTypeError,
564 "'dict.update' takes min 1 positional arguments but 0 given"));
565}
566
567TEST_F(DictBuiltinsTest, UpdateWithNonDictRaisesTypeError) {
568 EXPECT_TRUE(raised(runFromCStr(runtime_, "dict.update([], None)"),
569 LayoutId::kTypeError));
570}
571
572TEST_F(DictBuiltinsTest, UpdateWithNonMappingTypeRaisesTypeError) {
573 EXPECT_TRUE(raisedWithStr(runFromCStr(runtime_, "dict.update({}, 1)"),
574 LayoutId::kTypeError,
575 "'int' object is not iterable"));
576}
577
578TEST_F(DictBuiltinsTest,
579 UpdateWithListContainerWithObjectHashReturningNonIntRaisesTypeError) {
580 EXPECT_TRUE(raisedWithStr(runFromCStr(runtime_, R"(
581class E:
582 def __hash__(self): return "non int"
583
584class C:
585 def __init__(self):
586 self.item = E()
587
588 def __getitem__(self, idx):
589 return self.item
590
591 def keys(self):
592 return [self.item]
593
594dict.update({1:4}, C())
595)"),
596 LayoutId::kTypeError,
597 "__hash__ method should return an integer"));
598}
599
600TEST_F(DictBuiltinsTest,
601 UpdateWithTupleContainerWithObjectHashReturningNonIntRaisesTypeError) {
602 EXPECT_TRUE(raisedWithStr(runFromCStr(runtime_, R"(
603class E:
604 def __hash__(self): return "non int"
605
606class C:
607 def __init__(self):
608 self.item = E()
609
610 def __getitem__(self, idx):
611 return self.item
612
613 def keys(self):
614 return (self.item,)
615
616dict.update({1:4}, C())
617)"),
618 LayoutId::kTypeError,
619 "__hash__ method should return an integer"));
620}
621
622TEST_F(DictBuiltinsTest,
623 UpdateWithIterContainerWithObjectHashReturningNonIntRaisesTypeError) {
624 EXPECT_TRUE(raisedWithStr(runFromCStr(runtime_, R"(
625class E:
626 def __hash__(self): return "non int"
627
628class C:
629 def __init__(self):
630 self.item = E()
631
632 def __getitem__(self, idx):
633 return self.item
634
635 def keys(self):
636 return iter([self.item])
637
638dict.update({1:4}, C())
639)"),
640 LayoutId::kTypeError,
641 "__hash__ method should return an integer"));
642}
643
644TEST_F(DictBuiltinsTest, UpdateWithDictReturnsUpdatedDict) {
645 ASSERT_FALSE(runFromCStr(runtime_, R"(
646d1 = {"a": 1, "b": 2}
647d2 = {"c": 3, "d": 4}
648d3 = {"a": 123}
649)")
650 .isError());
651 HandleScope scope(thread_);
652 Dict d1(&scope, mainModuleAt(runtime_, "d1"));
653 Dict d2(&scope, mainModuleAt(runtime_, "d2"));
654 ASSERT_EQ(d1.numItems(), 2);
655 EXPECT_EQ(d1.firstEmptyItemIndex() / kItemNumPointers, 2);
656 ASSERT_EQ(d2.numItems(), 2);
657 EXPECT_EQ(d2.firstEmptyItemIndex() / kItemNumPointers, 2);
658 ASSERT_TRUE(runFromCStr(runtime_, "d1.update(d2)").isNoneType());
659 EXPECT_EQ(d1.numItems(), 4);
660 EXPECT_EQ(d1.firstEmptyItemIndex() / kItemNumPointers, 4);
661 EXPECT_EQ(d2.numItems(), 2);
662 EXPECT_EQ(d2.firstEmptyItemIndex() / kItemNumPointers, 2);
663
664 ASSERT_TRUE(runFromCStr(runtime_, "d1.update(d3)").isNoneType());
665 EXPECT_EQ(d1.numItems(), 4);
666 EXPECT_EQ(d1.firstEmptyItemIndex() / kItemNumPointers, 4);
667 Str a(&scope, runtime_->newStrFromCStr("a"));
668 Object a_val(&scope, dictAtByStr(thread_, d1, a));
669 EXPECT_TRUE(isIntEqualsWord(*a_val, 123));
670}
671
672TEST_F(DictItemsBuiltinsTest, DunderIterReturnsIter) {
673 HandleScope scope(thread_);
674 Dict dict(&scope, runtime_->newDict());
675 DictItems items(&scope, runtime_->newDictItems(thread_, dict));
676 Object iter(&scope, runBuiltin(METH(dict_items, __iter__), items));
677 ASSERT_TRUE(iter.isDictItemIterator());
678}
679
680TEST_F(DictKeysBuiltinsTest, DunderIterReturnsIter) {
681 HandleScope scope(thread_);
682 Dict dict(&scope, runtime_->newDict());
683 DictKeys keys(&scope, runtime_->newDictKeys(thread_, dict));
684 Object iter(&scope, runBuiltin(METH(dict_keys, __iter__), keys));
685 ASSERT_TRUE(iter.isDictKeyIterator());
686}
687
688TEST_F(DictValuesBuiltinsTest, DunderIterReturnsIter) {
689 HandleScope scope(thread_);
690 Dict dict(&scope, runtime_->newDict());
691 DictValues values(&scope, runtime_->newDictValues(thread_, dict));
692 Object iter(&scope, runBuiltin(METH(dict_values, __iter__), values));
693 ASSERT_TRUE(iter.isDictValueIterator());
694}
695
696TEST_F(DictItemIteratorBuiltinsTest, CallDunderIterReturnsSelf) {
697 HandleScope scope(thread_);
698 Dict dict(&scope, runtime_->newDict());
699 DictItemIterator iter(&scope, runtime_->newDictItemIterator(thread_, dict));
700 // Now call __iter__ on the iterator object
701 Object result(&scope, runBuiltin(METH(dict_itemiterator, __iter__), iter));
702 ASSERT_EQ(*result, *iter);
703}
704
705TEST_F(DictKeyIteratorBuiltinsTest, CallDunderIterReturnsSelf) {
706 HandleScope scope(thread_);
707 Dict dict(&scope, runtime_->newDict());
708 DictKeyIterator iter(&scope, runtime_->newDictKeyIterator(thread_, dict));
709 // Now call __iter__ on the iterator object
710 Object result(&scope, runBuiltin(METH(dict_keyiterator, __iter__), iter));
711 ASSERT_EQ(*result, *iter);
712}
713
714TEST_F(DictValueIteratorBuiltinsTest, CallDunderIterReturnsSelf) {
715 HandleScope scope(thread_);
716 Dict dict(&scope, runtime_->newDict());
717 DictValueIterator iter(&scope, runtime_->newDictValueIterator(thread_, dict));
718 // Now call __iter__ on the iterator object
719 Object result(&scope, runBuiltin(METH(dict_valueiterator, __iter__), iter));
720 ASSERT_EQ(*result, *iter);
721}
722
723TEST_F(DictItemIteratorBuiltinsTest,
724 DunderLengthHintOnEmptyDictItemIteratorReturnsZero) {
725 HandleScope scope(thread_);
726 Dict empty_dict(&scope, runtime_->newDict());
727 DictItemIterator iter(&scope,
728 runtime_->newDictItemIterator(thread_, empty_dict));
729 Object length_hint(
730 &scope, runBuiltin(METH(dict_itemiterator, __length_hint__), iter));
731 EXPECT_TRUE(isIntEqualsWord(*length_hint, 0));
732}
733
734TEST_F(DictKeyIteratorBuiltinsTest,
735 DunderLengthHintOnEmptyDictKeyIteratorReturnsZero) {
736 HandleScope scope(thread_);
737 Dict empty_dict(&scope, runtime_->newDict());
738 DictKeyIterator iter(&scope,
739 runtime_->newDictKeyIterator(thread_, empty_dict));
740 Object length_hint(&scope,
741 runBuiltin(METH(dict_keyiterator, __length_hint__), iter));
742 EXPECT_TRUE(isIntEqualsWord(*length_hint, 0));
743}
744
745TEST_F(DictValueIteratorBuiltinsTest,
746 DunderLengthHintOnEmptyDictValueIteratorReturnsZero) {
747 HandleScope scope(thread_);
748 Dict empty_dict(&scope, runtime_->newDict());
749 DictValueIterator iter(&scope,
750 runtime_->newDictValueIterator(thread_, empty_dict));
751 Object length_hint(
752 &scope, runBuiltin(METH(dict_valueiterator, __length_hint__), iter));
753 EXPECT_TRUE(isIntEqualsWord(*length_hint, 0));
754}
755
756TEST_F(DictItemIteratorBuiltinsTest, CallDunderNextReadsItemsSequentially) {
757 HandleScope scope(thread_);
758 Dict dict(&scope, runtime_->newDictWithSize(5));
759 Str hello(&scope, runtime_->newStrFromCStr("hello"));
760 Object world(&scope, runtime_->newStrFromCStr("world"));
761 Str goodbye(&scope, runtime_->newStrFromCStr("goodbye"));
762 Object moon(&scope, runtime_->newStrFromCStr("moon"));
763 dictAtPutByStr(thread_, dict, hello, world);
764 dictAtPutByStr(thread_, dict, goodbye, moon);
765 DictItemIterator iter(&scope, runtime_->newDictItemIterator(thread_, dict));
766
767 Object item1(&scope, runBuiltin(METH(dict_itemiterator, __next__), iter));
768 ASSERT_TRUE(item1.isTuple());
769 EXPECT_EQ(Tuple::cast(*item1).at(0), hello);
770 EXPECT_EQ(Tuple::cast(*item1).at(1), world);
771
772 Object item2(&scope, runBuiltin(METH(dict_itemiterator, __next__), iter));
773 ASSERT_TRUE(item2.isTuple());
774 EXPECT_EQ(Tuple::cast(*item2).at(0), goodbye);
775 EXPECT_EQ(Tuple::cast(*item2).at(1), moon);
776
777 Object item3(&scope, runBuiltin(METH(dict_itemiterator, __next__), iter));
778 ASSERT_TRUE(item3.isError());
779}
780
781TEST_F(DictKeyIteratorBuiltinsTest, CallDunderNextReadsKeysSequentially) {
782 HandleScope scope(thread_);
783 Dict dict(&scope, runtime_->newDictWithSize(5));
784 Str hello(&scope, runtime_->newStrFromCStr("hello"));
785 Object world(&scope, runtime_->newStrFromCStr("world"));
786 Str goodbye(&scope, runtime_->newStrFromCStr("goodbye"));
787 Object moon(&scope, runtime_->newStrFromCStr("moon"));
788 dictAtPutByStr(thread_, dict, hello, world);
789 dictAtPutByStr(thread_, dict, goodbye, moon);
790 DictKeyIterator iter(&scope, runtime_->newDictKeyIterator(thread_, dict));
791
792 Object item1(&scope, runBuiltin(METH(dict_keyiterator, __next__), iter));
793 ASSERT_TRUE(item1.isStr());
794 EXPECT_EQ(Str::cast(*item1), hello);
795
796 Object item2(&scope, runBuiltin(METH(dict_keyiterator, __next__), iter));
797 ASSERT_TRUE(item2.isStr());
798 EXPECT_EQ(Str::cast(*item2), goodbye);
799
800 Object item3(&scope, runBuiltin(METH(dict_keyiterator, __next__), iter));
801 ASSERT_TRUE(item3.isError());
802}
803
804TEST_F(DictValueIteratorBuiltinsTest, CallDunderNextReadsValuesSequentially) {
805 HandleScope scope(thread_);
806 Dict dict(&scope, runtime_->newDictWithSize(5));
807 Str hello(&scope, runtime_->newStrFromCStr("hello"));
808 Object world(&scope, runtime_->newStrFromCStr("world"));
809 Str goodbye(&scope, runtime_->newStrFromCStr("goodbye"));
810 Object moon(&scope, runtime_->newStrFromCStr("moon"));
811 dictAtPutByStr(thread_, dict, hello, world);
812 dictAtPutByStr(thread_, dict, goodbye, moon);
813 DictValueIterator iter(&scope, runtime_->newDictValueIterator(thread_, dict));
814
815 Object item1(&scope, runBuiltin(METH(dict_valueiterator, __next__), iter));
816 ASSERT_TRUE(item1.isStr());
817 EXPECT_EQ(Str::cast(*item1), world);
818
819 Object item2(&scope, runBuiltin(METH(dict_valueiterator, __next__), iter));
820 ASSERT_TRUE(item2.isStr());
821 EXPECT_EQ(Str::cast(*item2), moon);
822
823 Object item3(&scope, runBuiltin(METH(dict_valueiterator, __next__), iter));
824 ASSERT_TRUE(item3.isError());
825}
826
827TEST_F(DictItemIteratorBuiltinsTest,
828 DunderLengthHintOnConsumedDictItemIteratorReturnsZero) {
829 HandleScope scope(thread_);
830 Dict dict(&scope, runtime_->newDict());
831 Str hello(&scope, runtime_->newStrFromCStr("hello"));
832 Object world(&scope, runtime_->newStrFromCStr("world"));
833 dictAtPutByStr(thread_, dict, hello, world);
834 DictItemIterator iter(&scope, runtime_->newDictItemIterator(thread_, dict));
835
836 Object item1(&scope, runBuiltin(METH(dict_itemiterator, __next__), iter));
837 ASSERT_FALSE(item1.isError());
838
839 Object length_hint(
840 &scope, runBuiltin(METH(dict_itemiterator, __length_hint__), iter));
841 EXPECT_TRUE(isIntEqualsWord(*length_hint, 0));
842}
843
844TEST_F(DictKeyIteratorBuiltinsTest,
845 DunderLengthHintOnConsumedDictKeyIteratorReturnsZero) {
846 HandleScope scope(thread_);
847 Dict dict(&scope, runtime_->newDict());
848 Str hello(&scope, runtime_->newStrFromCStr("hello"));
849 Object world(&scope, runtime_->newStrFromCStr("world"));
850 dictAtPutByStr(thread_, dict, hello, world);
851 DictKeyIterator iter(&scope, runtime_->newDictKeyIterator(thread_, dict));
852
853 Object item1(&scope, runBuiltin(METH(dict_keyiterator, __next__), iter));
854 ASSERT_FALSE(item1.isError());
855
856 Object length_hint(&scope,
857 runBuiltin(METH(dict_keyiterator, __length_hint__), iter));
858 EXPECT_TRUE(isIntEqualsWord(*length_hint, 0));
859}
860
861TEST_F(DictValueIteratorBuiltinsTest,
862 DunderLengthHintOnConsumedDictValueIteratorReturnsZero) {
863 HandleScope scope(thread_);
864 Dict dict(&scope, runtime_->newDict());
865 Str hello(&scope, runtime_->newStrFromCStr("hello"));
866 Object world(&scope, runtime_->newStrFromCStr("world"));
867 dictAtPutByStr(thread_, dict, hello, world);
868 DictValueIterator iter(&scope, runtime_->newDictValueIterator(thread_, dict));
869
870 Object item1(&scope, runBuiltin(METH(dict_valueiterator, __next__), iter));
871 ASSERT_FALSE(item1.isError());
872
873 Object length_hint(
874 &scope, runBuiltin(METH(dict_valueiterator, __length_hint__), iter));
875 EXPECT_TRUE(isIntEqualsWord(*length_hint, 0));
876}
877
878TEST_F(DictBuiltinsTest, ItemIteratorNextOnOneElementDictReturnsElement) {
879 HandleScope scope(thread_);
880 Dict dict(&scope, runtime_->newDict());
881 Str key(&scope, runtime_->newStrFromCStr("hello"));
882 Object value(&scope, runtime_->newStrFromCStr("world"));
883 dictAtPutByStr(thread_, dict, key, value);
884 DictItemIterator iter(&scope, runtime_->newDictItemIterator(thread_, dict));
885 Object next(&scope, dictItemIteratorNext(thread_, iter));
886 ASSERT_TRUE(next.isTuple());
887 EXPECT_EQ(Tuple::cast(*next).at(0), key);
888 EXPECT_EQ(Tuple::cast(*next).at(1), value);
889
890 next = dictItemIteratorNext(thread_, iter);
891 ASSERT_TRUE(next.isError());
892}
893
894TEST_F(DictBuiltinsTest, KeyIteratorNextOnOneElementDictReturnsElement) {
895 HandleScope scope(thread_);
896 Dict dict(&scope, runtime_->newDict());
897 Str key(&scope, runtime_->newStrFromCStr("hello"));
898 Object value(&scope, runtime_->newStrFromCStr("world"));
899 dictAtPutByStr(thread_, dict, key, value);
900 DictKeyIterator iter(&scope, runtime_->newDictKeyIterator(thread_, dict));
901 Object next(&scope, dictKeyIteratorNext(thread_, iter));
902 EXPECT_EQ(next, key);
903
904 next = dictKeyIteratorNext(thread_, iter);
905 ASSERT_TRUE(next.isError());
906}
907
908TEST_F(DictBuiltinsTest, ValueIteratorNextOnOneElementDictReturnsElement) {
909 HandleScope scope(thread_);
910 Dict dict(&scope, runtime_->newDict());
911 Str key(&scope, runtime_->newStrFromCStr("hello"));
912 Object value(&scope, runtime_->newStrFromCStr("world"));
913 dictAtPutByStr(thread_, dict, key, value);
914 DictValueIterator iter(&scope, runtime_->newDictValueIterator(thread_, dict));
915 Object next(&scope, dictValueIteratorNext(thread_, iter));
916 EXPECT_EQ(next, value);
917
918 next = dictValueIteratorNext(thread_, iter);
919 ASSERT_TRUE(next.isError());
920}
921
922TEST_F(DictBuiltinsTest, NextOnDictWithOnlyTombstonesReturnsFalse) {
923 HandleScope scope(thread_);
924 Dict dict(&scope, runtime_->newDict());
925 Str key(&scope, runtime_->newStrFromCStr("hello"));
926 Object value(&scope, runtime_->newStrFromCStr("world"));
927 dictAtPutByStr(thread_, dict, key, value);
928 ASSERT_FALSE(dictRemoveByStr(thread_, dict, key).isError());
929
930 word i = 0;
931 Object dict_key(&scope, NoneType::object());
932 Object dict_value(&scope, NoneType::object());
933 EXPECT_FALSE(dictNextItem(dict, &i, &dict_key, &dict_value));
934}
935
936TEST_F(DictBuiltinsTest, RecursiveDictPrintsEllipsis) {
937 ASSERT_FALSE(runFromCStr(runtime_, R"(
938class C:
939 def __init__(self, obj):
940 self.val = obj
941 def __repr__(self):
942 return self.val.__repr__()
943 def __hash__(self):
944 return 5
945
946d = dict()
947c = C(d)
948d['hello'] = c
949result = d.__repr__()
950)")
951 .isError());
952 EXPECT_TRUE(
953 isStrEqualsCStr(mainModuleAt(runtime_, "result"), "{'hello': {...}}"));
954}
955
956TEST_F(DictBuiltinsTest, PopWithKeyPresentReturnsValue) {
957 ASSERT_FALSE(runFromCStr(runtime_, R"(
958d = {"hello": "world"}
959result = d.pop("hello")
960)")
961 .isError());
962 HandleScope scope(thread_);
963 EXPECT_TRUE(isStrEqualsCStr(mainModuleAt(runtime_, "result"), "world"));
964 Dict dict(&scope, mainModuleAt(runtime_, "d"));
965 EXPECT_EQ(dict.numItems(), 0);
966 EXPECT_EQ(dict.firstEmptyItemIndex() / kItemNumPointers, 1);
967}
968
969TEST_F(DictBuiltinsTest, PopWithMissingKeyAndDefaultReturnsDefault) {
970 ASSERT_FALSE(runFromCStr(runtime_, R"(
971d = {}
972result = d.pop("hello", "world")
973)")
974 .isError());
975 HandleScope scope(thread_);
976 Dict dict(&scope, mainModuleAt(runtime_, "d"));
977 EXPECT_EQ(dict.numItems(), 0);
978 EXPECT_EQ(dict.firstEmptyItemIndex() / kItemNumPointers, 0);
979 EXPECT_TRUE(isStrEqualsCStr(mainModuleAt(runtime_, "result"), "world"));
980}
981
982TEST_F(DictBuiltinsTest, PopitemAfterInsert) {
983 HandleScope scope(thread_);
984 Dict dict(&scope, runtime_->newDict());
985
986 Object key(&scope, SmallInt::fromWord(0));
987 Object key1(&scope, SmallInt::fromWord(1));
988 word hash = intHash(*key);
989 word hash1 = intHash(*key1);
990 ASSERT_TRUE(dictAtPut(thread_, dict, key, hash, key).isNoneType());
991 ASSERT_TRUE(dictAtPut(thread_, dict, key1, hash1, key1).isNoneType());
992
993 for (int i = 0; i < 2; i++) {
994 runBuiltin(METH(dict, popitem), dict);
995 }
996 ASSERT_EQ(dict.numItems(), 0);
997}
998
999TEST_F(DictBuiltinsTest, PopWithMisingKeyRaisesKeyError) {
1000 EXPECT_TRUE(
1001 raised(runFromCStr(runtime_, "{}.pop('hello')"), LayoutId::kKeyError));
1002}
1003
1004TEST_F(DictBuiltinsTest, PopWithSubclassDoesNotCallDunderDelitem) {
1005 ASSERT_FALSE(runFromCStr(runtime_, R"(
1006class C(dict):
1007 def __delitem__(self, key):
1008 raise Exception(key)
1009c = C({'hello': 'world'})
1010result = c.pop('hello')
1011)")
1012 .isError());
1013 ASSERT_FALSE(thread_->hasPendingException());
1014 HandleScope scope(thread_);
1015 Dict dict(&scope, mainModuleAt(runtime_, "c"));
1016 EXPECT_EQ(dict.numItems(), 0);
1017 EXPECT_EQ(dict.firstEmptyItemIndex() / kItemNumPointers, 1);
1018 EXPECT_TRUE(isStrEqualsCStr(mainModuleAt(runtime_, "result"), "world"));
1019}
1020
1021TEST_F(DictBuiltinsTest, DictInitWithSubclassInitializesElements) {
1022 ASSERT_FALSE(runFromCStr(runtime_, R"(
1023class C(dict):
1024 pass
1025c = C({'hello': 'world'})
1026)")
1027 .isError());
1028 HandleScope scope(thread_);
1029 Dict dict(&scope, mainModuleAt(runtime_, "c"));
1030 EXPECT_EQ(dict.numItems(), 1);
1031}
1032
1033TEST_F(DictBuiltinsTest, SetDefaultWithNoDefaultSetsToNone) {
1034 ASSERT_FALSE(runFromCStr(runtime_, R"(
1035d = {}
1036d.setdefault("hello")
1037result = d["hello"]
1038)")
1039 .isError());
1040 EXPECT_EQ(mainModuleAt(runtime_, "result"), NoneType::object());
1041}
1042
1043TEST_F(DictBuiltinsTest, SetDefaultWithNotKeyInDictSetsDefault) {
1044 ASSERT_FALSE(runFromCStr(runtime_, R"(
1045d = {}
1046d.setdefault("hello", 4)
1047result = d["hello"]
1048)")
1049 .isError());
1050 EXPECT_TRUE(isIntEqualsWord(mainModuleAt(runtime_, "result"), 4));
1051}
1052
1053TEST_F(DictBuiltinsTest, SetDefaultWithKeyInDictReturnsValue) {
1054 ASSERT_FALSE(runFromCStr(runtime_, R"(
1055d = {"hello": 5}
1056d.setdefault("hello", 4)
1057result = d["hello"]
1058)")
1059 .isError());
1060 EXPECT_TRUE(isIntEqualsWord(mainModuleAt(runtime_, "result"), 5));
1061}
1062
1063TEST_F(DictBuiltinsTest, NumAttributesMatchesObjectSize) {
1064 HandleScope scope(thread_);
1065 Layout layout(&scope, runtime_->layoutAt(LayoutId::kDict));
1066 EXPECT_EQ(layout.numInObjectAttributes(),
1067 (RawDict::kSize - RawHeapObject::kSize) / kPointerSize);
1068}
1069
1070} // namespace testing
1071} // namespace py