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 "builtins.h"
5#include "frame.h"
6#include "globals.h"
7#include "int-builtins.h"
8#include "interpreter.h"
9#include "objects.h"
10#include "runtime.h"
11#include "str-builtins.h"
12#include "thread.h"
13#include "type-builtins.h"
14#include "utils.h"
15
16namespace py {
17
18namespace {
19
20// Helper functions for accessing sparse array from dict.indices().
21static const uint32_t kTombstoneValue = 0xFFFFFFFE;
22static const uint32_t kEmptyValue = 0xFFFFFFFF;
23static const word kNumBytesExponent = 2;
24
25static word probeBegin(word num_indices, word hash, word* indices_mask,
26 uword* perturb) {
27 DCHECK(Utils::isPowerOfTwo(num_indices), "%ld is not a power of 2",
28 num_indices);
29 DCHECK(num_indices > 0, "indicesxs size <= 0");
30 DCHECK(RawSmallInt::isValid(hash), "hash out of range");
31 *perturb = static_cast<uword>(hash);
32 *indices_mask = num_indices - 1;
33 return *indices_mask & hash;
34}
35
36static word probeNext(word current, word indices_mask, uword* perturb) {
37 // Given that current stands for the index into dict.indices, this advances
38 // current to (5 * current + 1 + perturb). Note that it's guaranteed that
39 // keeping calling this function returns a permutation of all indices when
40 // the number of the indices is power of two. See
41 // https://en.wikipedia.org/wiki/Linear_congruential_generator#c_%E2%89%A0_0.
42 *perturb >>= 5;
43 return (current * 5 + 1 + *perturb) & indices_mask;
44}
45
46// Returns the bytes offset into the indices array given an index
47static word indexOffset(word index) { return index << kNumBytesExponent; }
48
49// Return the item index stored at indices[bytes_offset].
50static uint32_t itemIndexAt(RawMutableBytes indices, word bytes_offset) {
51 DCHECK(bytes_offset % 4 == 0, "bytes_offset must be a multiple of 4");
52 return indices.uint32At(bytes_offset);
53}
54
55// Set `item_index` at indices[bytes_offset].
56static void itemIndexAtPut(RawMutableBytes indices, word bytes_offset,
57 uint32_t item_index) {
58 indices.uint32AtPut(bytes_offset, item_index);
59}
60
61// Set a tombstone at indices[bytes_offset] given `data_length` from
62// data.length().
63static void indicesSetTombstone(RawMutableBytes indices, word bytes_offset) {
64 itemIndexAtPut(indices, bytes_offset, kTombstoneValue);
65}
66
67// Return true if the indices[bytes_offset] is filled with an active item.
68static bool indicesIsFull(RawMutableBytes indices, word bytes_offset,
69 uint32_t* item_index) {
70 *item_index = itemIndexAt(indices, bytes_offset);
71 return *item_index < kTombstoneValue;
72}
73
74// Return true if the indices[bytes_offset] is never used.
75static bool indicesIsEmpty(RawMutableBytes indices, word bytes_offset) {
76 return itemIndexAt(indices, bytes_offset) == kEmptyValue;
77}
78
79// Helper functions for accessing dict items from dict.data().
80
81// Data tuple Layout.
82static const word kItemHashOffset = 0;
83static const word kItemKeyOffset = 1;
84static const word kItemValueOffset = 2;
85static const word kItemNumPointers = 3;
86
87static RawObject itemKey(RawMutableTuple data, word index) {
88 return data.at(index + kItemKeyOffset);
89}
90
91static RawObject itemValue(RawMutableTuple data, word index) {
92 return data.at(index + kItemValueOffset);
93}
94
95static word itemHash(RawMutableTuple data, word index) {
96 return SmallInt::cast(data.at(index + kItemHashOffset)).value();
97}
98
99static RawObject itemHashRaw(RawMutableTuple data, word index) {
100 return data.at(index + kItemHashOffset);
101}
102
103static void itemSet(RawMutableTuple data, word index, word hash, RawObject key,
104 RawObject value) {
105 data.atPut(index + kItemHashOffset, SmallInt::fromWordTruncated(hash));
106 data.atPut(index + kItemKeyOffset, key);
107 data.atPut(index + kItemValueOffset, value);
108}
109
110static void itemSetTombstone(RawMutableTuple data, word index) {
111 data.atPut(index + kItemHashOffset, Unbound::object());
112 data.atPut(index + kItemKeyOffset, NoneType::object());
113 data.atPut(index + kItemValueOffset, NoneType::object());
114}
115
116static void itemSetValue(RawMutableTuple data, word index, RawObject value) {
117 data.atPut(index + kItemValueOffset, value);
118}
119
120static bool itemIsEmpty(RawMutableTuple data, word index) {
121 return data.at(index + kItemHashOffset).isNoneType();
122}
123
124static bool itemIsFull(RawMutableTuple data, word index) {
125 return data.at(index + kItemHashOffset).isSmallInt();
126}
127
128static bool itemIsTombstone(RawMutableTuple data, word index) {
129 return data.at(index + kItemHashOffset).isUnbound();
130}
131
132} // namespace
133
134// Returns one of the three possible values:
135// - `key` was found at indices[bytes_offset] : SmallInt::fromWord(bytes_offset)
136// - `key` was not found : SmallInt::fromWord(-1)
137// - Exception that was raised from key comparison __eq__ function.
138static RawObject dictLookup(Thread* thread, const MutableTuple& data,
139 MutableBytes& indices, word num_indices,
140 const Object& key, word hash) {
141 DCHECK(data.length() > 0, "data shouldn't be empty");
142 uword perturb;
143 word indices_mask;
144 RawSmallInt hash_int = SmallInt::fromWord(hash);
145 for (word current_index =
146 probeBegin(num_indices, hash, &indices_mask, &perturb);
147 ; current_index = probeNext(current_index, indices_mask, &perturb)) {
148 word bytes_offset = indexOffset(current_index);
149 uint32_t item_index;
150 if (indicesIsFull(*indices, bytes_offset, &item_index)) {
151 if (itemHashRaw(*data, item_index) == hash_int) {
152 RawObject eq =
153 Runtime::objectEquals(thread, itemKey(*data, item_index), *key);
154 if (eq == Bool::trueObj()) {
155 return SmallInt::fromWord(bytes_offset);
156 }
157 if (UNLIKELY(eq.isErrorException())) {
158 return eq;
159 }
160 }
161 continue;
162 }
163 if (indicesIsEmpty(*indices, bytes_offset)) {
164 return SmallInt::fromWord(-1);
165 }
166 }
167 UNREACHABLE("Expected to have found an empty index");
168}
169
170// Returns one of the three possible values:
171// - `key` was found at indices[bytes_offset] : SmallInt::fromWord(bytes_offset)
172// - `key` was not found, but insertion can be done to indices[bytes_offset] :
173// SmallInt::fromWord(bytes_offset - data.length())
174// - Exception that was raised from key comparison __eq__ function.
175static RawObject dictLookupForInsertion(Thread* thread,
176 const MutableTuple& data,
177 MutableBytes& indices, word num_indices,
178 const Object& key, word hash) {
179 DCHECK(data.length() > 0, "data shouldn't be empty");
180 word next_free_index = -1;
181 uword perturb;
182 word indices_mask;
183 RawSmallInt hash_int = SmallInt::fromWord(hash);
184 for (word current_index =
185 probeBegin(num_indices, hash, &indices_mask, &perturb);
186 ; current_index = probeNext(current_index, indices_mask, &perturb)) {
187 word bytes_offset = indexOffset(current_index);
188 uint32_t item_index;
189 if (indicesIsFull(*indices, bytes_offset, &item_index)) {
190 if (itemHashRaw(*data, item_index) == hash_int) {
191 RawObject eq =
192 Runtime::objectEquals(thread, itemKey(*data, item_index), *key);
193 if (eq == Bool::trueObj()) {
194 return SmallInt::fromWord(bytes_offset);
195 }
196 if (UNLIKELY(eq.isErrorException())) {
197 return eq;
198 }
199 }
200 continue;
201 }
202 if (next_free_index == -1) {
203 next_free_index = bytes_offset;
204 }
205 if (indicesIsEmpty(*indices, bytes_offset)) {
206 return SmallInt::fromWord(next_free_index - indexOffset(num_indices));
207 }
208 }
209 UNREACHABLE("Expected to have found an empty index");
210}
211
212static word nextItemIndex(RawObject data, word* index, word end) {
213 for (word i = *index; i < end; i += kItemNumPointers) {
214 if (!itemIsFull(MutableTuple::cast(data), i)) continue;
215 *index = i + kItemNumPointers;
216 return i;
217 }
218 return -1;
219}
220
221bool dictNextItem(const Dict& dict, word* index, Object* key_out,
222 Object* value_out) {
223 RawObject data = dict.data();
224 word next_item_index = nextItemIndex(data, index, dict.firstEmptyItemIndex());
225 if (next_item_index < 0) {
226 return false;
227 }
228 *key_out = itemKey(MutableTuple::cast(data), next_item_index);
229 *value_out = itemValue(MutableTuple::cast(data), next_item_index);
230 return true;
231}
232
233bool dictNextItemHash(const Dict& dict, word* index, Object* key_out,
234 Object* value_out, word* hash_out) {
235 RawObject data = dict.data();
236 word next_item_index = nextItemIndex(data, index, dict.firstEmptyItemIndex());
237 if (next_item_index < 0) {
238 return false;
239 }
240 *key_out = itemKey(MutableTuple::cast(data), next_item_index);
241 *value_out = itemValue(MutableTuple::cast(data), next_item_index);
242 *hash_out = itemHash(MutableTuple::cast(data), next_item_index);
243 return true;
244}
245
246bool dictNextKey(const Dict& dict, word* index, Object* key_out) {
247 RawObject data = dict.data();
248 word next_item_index = nextItemIndex(data, index, dict.firstEmptyItemIndex());
249 if (next_item_index < 0) {
250 return false;
251 }
252 *key_out = itemKey(MutableTuple::cast(data), next_item_index);
253 return true;
254}
255
256bool dictNextKeyHash(const Dict& dict, word* index, Object* key_out,
257 word* hash_out) {
258 RawObject data = dict.data();
259 word next_item_index = nextItemIndex(data, index, dict.firstEmptyItemIndex());
260 if (next_item_index < 0) {
261 return false;
262 }
263 *key_out = itemKey(MutableTuple::cast(data), next_item_index);
264 *hash_out = itemHash(MutableTuple::cast(data), next_item_index);
265 return true;
266}
267
268bool dictNextValue(const Dict& dict, word* index, Object* value_out) {
269 RawObject data = dict.data();
270 word next_item_index = nextItemIndex(data, index, dict.firstEmptyItemIndex());
271 if (next_item_index < 0) {
272 return false;
273 }
274 *value_out = itemValue(MutableTuple::cast(data), next_item_index);
275 return true;
276}
277
278static word sizeOfDataTuple(word num_indices) { return (num_indices * 2) / 3; }
279
280static const word kDictGrowthFactor = 2;
281// Initial size of the dict. According to comments in CPython's
282// dictobject.c this accommodates the majority of dictionaries without needing
283// a resize (obviously this depends on the load factor used to resize the
284// dict).
285static const word kInitialDictIndicesLength = 8;
286
287void dictAllocateArrays(Thread* thread, const Dict& dict, word num_indices) {
288 num_indices = Utils::maximum(num_indices, kInitialDictIndicesLength);
289 DCHECK(Utils::isPowerOfTwo(num_indices), "%ld is not a power of 2",
290 num_indices);
291 Runtime* runtime = thread->runtime();
292 dict.setData(runtime->newMutableTuple(sizeOfDataTuple(num_indices) *
293 kItemNumPointers));
294 MutableTuple::cast(dict.data()).fill(NoneType::object());
295 dict.setIndices(
296 runtime->mutableBytesWith(indexOffset(num_indices), kMaxByte));
297 dict.setFirstEmptyItemIndex(0);
298}
299
300// Return true if `dict` has an available item for insertion.
301static bool dictHasUsableItem(const Dict& dict) {
302 return dict.firstEmptyItemIndex() <
303 RawMutableTuple::cast(dict.data()).length();
304}
305
306// Insert `key`/`value` into dictionary assuming no item with an equivalent
307// key and no tombstones exist.
308static void dictInsertNoUpdate(const MutableTuple& data,
309 const MutableBytes& indices, word num_indices,
310 word item_count, const Object& key, word hash,
311 const Object& value) {
312 DCHECK(data.length() > 0, "dict must not be empty");
313 uword perturb;
314 word indices_mask;
315 for (word current_index =
316 probeBegin(num_indices, hash, &indices_mask, &perturb);
317 ; current_index = probeNext(current_index, indices_mask, &perturb)) {
318 word bytes_offset = indexOffset(current_index);
319 if (indicesIsEmpty(*indices, bytes_offset)) {
320 uint32_t item_index = item_count * kItemNumPointers;
321 itemSet(*data, item_index, hash, *key, *value);
322 itemIndexAtPut(*indices, bytes_offset, item_index);
323 return;
324 }
325 }
326}
327
328static void dictEnsureCapacity(Thread* thread, const Dict& dict) {
329 DCHECK(dict.numIndices() && Utils::isPowerOfTwo(dict.numIndices()),
330 "dict capacity must be power of two, greater than zero");
331 if (dictHasUsableItem(dict)) {
332 return;
333 }
334
335 // TODO(T44247845): Handle overflow here.
336 word new_num_indices = dict.numIndices() * kDictGrowthFactor;
337 DCHECK(new_num_indices < kTombstoneValue,
338 "new_num_indices is expected to be less than kTombstoneValue");
339 HandleScope scope(thread);
340 Runtime* runtime = thread->runtime();
341 MutableTuple new_data(
342 &scope, runtime->newMutableTuple(sizeOfDataTuple(new_num_indices) *
343 kItemNumPointers));
344 new_data.fill(NoneType::object());
345 MutableBytes new_indices(&scope, runtime->mutableBytesWith(
346 indexOffset(new_num_indices), kMaxByte));
347
348 // Re-insert items
349 Object key(&scope, NoneType::object());
350 Object value(&scope, NoneType::object());
351 word hash;
352 word item_count = 0;
353 for (word i = 0; dictNextItemHash(dict, &i, &key, &value, &hash);
354 item_count++) {
355 dictInsertNoUpdate(new_data, new_indices, new_num_indices, item_count, key,
356 hash, value);
357 }
358 DCHECK(item_count == dict.numItems(), "found entries != dictNumItems()");
359 dict.setData(*new_data);
360 dict.setIndices(*new_indices);
361 dict.setFirstEmptyItemIndex(dict.numItems() * kItemNumPointers);
362}
363
364RawObject dictAtPut(Thread* thread, const Dict& dict, const Object& key,
365 word hash, const Object& value) {
366 if (dict.indices() == SmallInt::fromWord(0)) {
367 dictAllocateArrays(thread, dict, kInitialDictIndicesLength);
368 }
369 HandleScope scope(thread);
370 MutableTuple data(&scope, dict.data());
371 MutableBytes indices(&scope, dict.indices());
372 word num_indices = dict.numIndices();
373 RawObject lookup_result =
374 dictLookupForInsertion(thread, data, indices, num_indices, key, hash);
375 if (UNLIKELY(lookup_result.isErrorException())) {
376 return lookup_result;
377 }
378 word bytes_offset = SmallInt::cast(lookup_result).value();
379 if (bytes_offset >= 0) {
380 uint32_t item_index = itemIndexAt(*indices, bytes_offset);
381 itemSetValue(*data, item_index, *value);
382 return NoneType::object();
383 }
384
385 bytes_offset += indexOffset(num_indices);
386 word item_index = dict.firstEmptyItemIndex();
387 DCHECK(itemIsEmpty(*data, item_index), "item is expected to be empty");
388 itemSet(*data, item_index, hash, *key, *value);
389 itemIndexAtPut(*indices, bytes_offset, item_index);
390 dict.setNumItems(dict.numItems() + 1);
391 dict.setFirstEmptyItemIndex(dict.firstEmptyItemIndex() + kItemNumPointers);
392 dictEnsureCapacity(thread, dict);
393 DCHECK(dictHasUsableItem(dict), "dict must have an empty item left");
394 return NoneType::object();
395}
396
397void dictAtPutByStr(Thread* thread, const Dict& dict, const Object& name,
398 const Object& value) {
399 word hash = strHash(thread, *name);
400 UNUSED RawObject result = dictAtPut(thread, dict, name, hash, value);
401 DCHECK(!result.isError(), "result must not be an error");
402}
403
404void dictAtPutById(Thread* thread, const Dict& dict, SymbolId id,
405 const Object& value) {
406 HandleScope scope(thread);
407 Object name(&scope, thread->runtime()->symbols()->at(id));
408 dictAtPutByStr(thread, dict, name, value);
409}
410
411RawObject dictAt(Thread* thread, const Dict& dict, const Object& key,
412 word hash) {
413 if (dict.numItems() == 0) {
414 return Error::notFound();
415 }
416 HandleScope scope(thread);
417 MutableTuple data(&scope, dict.data());
418 MutableBytes indices(&scope, dict.indices());
419 RawObject lookup_result =
420 dictLookup(thread, data, indices, dict.numIndices(), key, hash);
421 if (UNLIKELY(lookup_result.isErrorException())) {
422 return lookup_result;
423 }
424 word bytes_offset = SmallInt::cast(lookup_result).value();
425 if (bytes_offset >= 0) {
426 uint32_t item_index = itemIndexAt(*indices, bytes_offset);
427 return itemValue(*data, item_index);
428 }
429 return Error::notFound();
430}
431
432RawObject dictAtByStr(Thread* thread, const Dict& dict, const Object& name) {
433 word hash = strHash(thread, *name);
434 return dictAt(thread, dict, name, hash);
435}
436
437RawObject dictAtById(Thread* thread, const Dict& dict, SymbolId id) {
438 HandleScope scope(thread);
439 Object name(&scope, thread->runtime()->symbols()->at(id));
440 return dictAtByStr(thread, dict, name);
441}
442
443RawObject dictAtPutInValueCellByStr(Thread* thread, const Dict& dict,
444 const Object& name, const Object& value) {
445 if (dict.indices() == SmallInt::fromWord(0)) {
446 dictAllocateArrays(thread, dict, kInitialDictIndicesLength);
447 }
448 HandleScope scope(thread);
449 MutableTuple data(&scope, dict.data());
450 MutableBytes indices(&scope, dict.indices());
451 word num_indices = dict.numIndices();
452 word hash = strHash(thread, *name);
453 RawObject lookup_result =
454 dictLookupForInsertion(thread, data, indices, num_indices, name, hash);
455 if (UNLIKELY(lookup_result.isErrorException())) {
456 return lookup_result;
457 }
458 word bytes_offset = SmallInt::cast(lookup_result).value();
459 if (bytes_offset >= 0) {
460 uint32_t item_index = itemIndexAt(*indices, bytes_offset);
461 RawValueCell value_cell = ValueCell::cast(itemValue(*data, item_index));
462 value_cell.setValue(*value);
463 return value_cell;
464 }
465 bytes_offset += indexOffset(num_indices);
466 word item_index = dict.firstEmptyItemIndex();
467 DCHECK(itemIsEmpty(*data, item_index), "item is expected to be empty");
468 ValueCell value_cell(&scope, thread->runtime()->newValueCell());
469 itemSet(*data, item_index, hash, *name, *value_cell);
470 itemIndexAtPut(*indices, bytes_offset, item_index);
471 dict.setNumItems(dict.numItems() + 1);
472 dict.setFirstEmptyItemIndex(dict.firstEmptyItemIndex() + kItemNumPointers);
473 dictEnsureCapacity(thread, dict);
474 DCHECK(dictHasUsableItem(dict), "dict must have an empty item left");
475 value_cell.setValue(*value);
476 return *value_cell;
477}
478
479void dictClear(Thread* thread, const Dict& dict) {
480 if (dict.indices() == SmallInt::fromWord(0)) return;
481
482 HandleScope scope(thread);
483 MutableTuple data(&scope, dict.data());
484 data.fill(NoneType::object());
485 MutableBytes indices(&scope, dict.indices());
486 indices.replaceFromWithByte(0, kMaxByte, indices.length());
487 dict.setNumItems(0);
488 dict.setFirstEmptyItemIndex(0);
489}
490
491RawObject dictIncludes(Thread* thread, const Dict& dict, const Object& key,
492 word hash) {
493 if (dict.numItems() == 0) {
494 return Bool::falseObj();
495 }
496 HandleScope scope(thread);
497 MutableTuple data(&scope, dict.data());
498 MutableBytes indices(&scope, dict.indices());
499 word num_indices = dict.numIndices();
500 RawObject lookup_result =
501 dictLookup(thread, data, indices, num_indices, key, hash);
502 if (UNLIKELY(lookup_result.isErrorException())) {
503 return lookup_result;
504 }
505 return Bool::fromBool(SmallInt::cast(lookup_result).value() >= 0);
506}
507
508RawObject dictRemoveByStr(Thread* thread, const Dict& dict,
509 const Object& name) {
510 word hash = strHash(thread, *name);
511 return dictRemove(thread, dict, name, hash);
512}
513
514RawObject dictRemove(Thread* thread, const Dict& dict, const Object& key,
515 word hash) {
516 if (dict.numItems() == 0) {
517 return Error::notFound();
518 }
519 HandleScope scope(thread);
520 MutableTuple data(&scope, dict.data());
521 MutableBytes indices(&scope, dict.indices());
522 word num_indices = dict.numIndices();
523 RawObject lookup_result =
524 dictLookup(thread, data, indices, num_indices, key, hash);
525 if (UNLIKELY(lookup_result.isErrorException())) {
526 return lookup_result;
527 }
528 word bytes_offset = SmallInt::cast(lookup_result).value();
529 if (bytes_offset < 0) {
530 return Error::notFound();
531 }
532 uint32_t item_index = itemIndexAt(*indices, bytes_offset);
533 Object result(&scope, itemValue(*data, item_index));
534 itemSetTombstone(*data, item_index);
535 indicesSetTombstone(*indices, bytes_offset);
536 dict.setNumItems(dict.numItems() - 1);
537 return *result;
538}
539
540RawObject dictKeys(Thread* thread, const Dict& dict) {
541 word len = dict.numItems();
542 Runtime* runtime = thread->runtime();
543 if (len == 0) {
544 return runtime->newList();
545 }
546 HandleScope scope(thread);
547 MutableTuple keys(&scope, runtime->newMutableTuple(len));
548 Object key(&scope, NoneType::object());
549 word num_keys = 0;
550 for (word i = 0; dictNextKey(dict, &i, &key);) {
551 DCHECK(num_keys < keys.length(), "%ld ! < %ld", num_keys, keys.length());
552 keys.atPut(num_keys, *key);
553 num_keys++;
554 }
555 List result(&scope, runtime->newList());
556 result.setItems(*keys);
557 result.setNumItems(len);
558 return *result;
559}
560
561RawObject dictCopy(Thread* thread, const Dict& dict) {
562 HandleScope scope(thread);
563 Dict copy(&scope, thread->runtime()->newDict());
564 Object result(&scope, dictMergeError(thread, copy, dict));
565 if (result.isError()) {
566 return *result;
567 }
568 return *copy;
569}
570
571namespace {
572enum class Override {
573 kIgnore,
574 kOverride,
575 kError,
576};
577
578RawObject dictMergeDict(Thread* thread, const Dict& dict, const Object& mapping,
579 Override do_override) {
580 HandleScope scope(thread);
581 if (*mapping == *dict) return NoneType::object();
582
583 Object key(&scope, NoneType::object());
584 Object value(&scope, NoneType::object());
585 word hash;
586 Dict other(&scope, *mapping);
587 Object included(&scope, NoneType::object());
588 Object dict_result(&scope, NoneType::object());
589 for (word i = 0; dictNextItemHash(other, &i, &key, &value, &hash);) {
590 if (do_override == Override::kOverride) {
591 dict_result = dictAtPut(thread, dict, key, hash, value);
592 if (dict_result.isErrorException()) return *dict_result;
593 } else {
594 included = dictIncludes(thread, dict, key, hash);
595 if (included.isErrorException()) return *included;
596 if (included == Bool::falseObj()) {
597 dict_result = dictAtPut(thread, dict, key, hash, value);
598 if (dict_result.isErrorException()) return *dict_result;
599 } else if (do_override == Override::kError) {
600 return thread->raise(LayoutId::kKeyError, *key);
601 }
602 }
603 }
604 return NoneType::object();
605}
606
607RawObject dictMergeImpl(Thread* thread, const Dict& dict, const Object& mapping,
608 Override do_override) {
609 Runtime* runtime = thread->runtime();
610 if (runtime->isInstanceOfDict(*mapping)) {
611 return dictMergeDict(thread, dict, mapping, do_override);
612 }
613
614 HandleScope scope(thread);
615 Object key(&scope, NoneType::object());
616 Object hash_obj(&scope, NoneType::object());
617 Object value(&scope, NoneType::object());
618 Object included(&scope, NoneType::object());
619 Object keys_method(&scope,
620 runtime->attributeAtById(thread, mapping, ID(keys)));
621 if (keys_method.isError()) {
622 return *keys_method;
623 }
624
625 // Generic mapping, use keys() and __getitem__()
626 Object subscr_method(
627 &scope, runtime->attributeAtById(thread, mapping, ID(__getitem__)));
628
629 if (subscr_method.isError()) {
630 return *subscr_method;
631 }
632 Object keys(&scope, Interpreter::callMethod1(thread, keys_method, mapping));
633 if (keys.isError()) return *keys;
634
635 if (keys.isList()) {
636 List keys_list(&scope, *keys);
637 Object dict_result(&scope, NoneType::object());
638 for (word i = 0; i < keys_list.numItems(); ++i) {
639 key = keys_list.at(i);
640 hash_obj = Interpreter::hash(thread, key);
641 if (hash_obj.isErrorException()) return *hash_obj;
642 word hash = SmallInt::cast(*hash_obj).value();
643 if (do_override == Override::kOverride) {
644 value = Interpreter::callMethod2(thread, subscr_method, mapping, key);
645 if (value.isError()) return *value;
646 dict_result = dictAtPut(thread, dict, key, hash, value);
647 if (dict_result.isErrorException()) return *dict_result;
648 } else {
649 included = dictIncludes(thread, dict, key, hash);
650 if (included.isErrorException()) return *included;
651 if (included == Bool::falseObj()) {
652 value = Interpreter::callMethod2(thread, subscr_method, mapping, key);
653 if (value.isError()) return *value;
654 dict_result = dictAtPut(thread, dict, key, hash, value);
655 if (dict_result.isErrorException()) return *dict_result;
656 } else if (do_override == Override::kError) {
657 return thread->raise(LayoutId::kKeyError, *key);
658 }
659 }
660 }
661 return NoneType::object();
662 }
663
664 if (keys.isTuple()) {
665 Tuple keys_tuple(&scope, *keys);
666 Object dict_result(&scope, NoneType::object());
667 for (word i = 0; i < keys_tuple.length(); ++i) {
668 key = keys_tuple.at(i);
669 hash_obj = Interpreter::hash(thread, key);
670 if (hash_obj.isErrorException()) return *hash_obj;
671 word hash = SmallInt::cast(*hash_obj).value();
672 if (do_override == Override::kOverride) {
673 value = Interpreter::callMethod2(thread, subscr_method, mapping, key);
674 if (value.isError()) return *value;
675 dict_result = dictAtPut(thread, dict, key, hash, value);
676 if (dict_result.isErrorException()) return *dict_result;
677 } else {
678 included = dictIncludes(thread, dict, key, hash);
679 if (included.isErrorException()) return *included;
680 if (included == Bool::falseObj()) {
681 value = Interpreter::callMethod2(thread, subscr_method, mapping, key);
682 if (value.isError()) return *value;
683 dict_result = dictAtPut(thread, dict, key, hash, value);
684 if (dict_result.isErrorException()) return *dict_result;
685 } else if (do_override == Override::kError) {
686 return thread->raise(LayoutId::kKeyError, *key);
687 }
688 }
689 }
690 return NoneType::object();
691 }
692
693 // keys is probably an iterator
694 Object iter_method(&scope,
695 Interpreter::lookupMethod(thread, keys, ID(__iter__)));
696 if (iter_method.isError()) {
697 return thread->raiseWithFmt(LayoutId::kTypeError, "keys() is not iterable");
698 }
699
700 Object iterator(&scope, Interpreter::callMethod1(thread, iter_method, keys));
701 if (iterator.isError()) {
702 return thread->raiseWithFmt(LayoutId::kTypeError, "keys() is not iterable");
703 }
704 Object next_method(&scope,
705 Interpreter::lookupMethod(thread, iterator, ID(__next__)));
706 if (next_method.isError()) {
707 return thread->raiseWithFmt(LayoutId::kTypeError, "keys() is not iterable");
708 }
709 Object dict_result(&scope, NoneType::object());
710 for (;;) {
711 key = Interpreter::callMethod1(thread, next_method, iterator);
712 if (key.isError()) {
713 if (thread->clearPendingStopIteration()) break;
714 return *key;
715 }
716 hash_obj = Interpreter::hash(thread, key);
717 if (hash_obj.isErrorException()) return *hash_obj;
718 word hash = SmallInt::cast(*hash_obj).value();
719 if (do_override == Override::kOverride) {
720 value = Interpreter::callMethod2(thread, subscr_method, mapping, key);
721 if (value.isError()) return *value;
722 dict_result = dictAtPut(thread, dict, key, hash, value);
723 if (dict_result.isErrorException()) return *dict_result;
724 } else {
725 included = dictIncludes(thread, dict, key, hash);
726 if (included.isErrorException()) return *included;
727 if (included == Bool::falseObj()) {
728 value = Interpreter::callMethod2(thread, subscr_method, mapping, key);
729 if (value.isError()) return *value;
730 dict_result = dictAtPut(thread, dict, key, hash, value);
731 if (dict_result.isErrorException()) return *dict_result;
732 } else if (do_override == Override::kError) {
733 return thread->raise(LayoutId::kKeyError, *key);
734 }
735 }
736 }
737 return NoneType::object();
738}
739} // namespace
740
741RawObject dictMergeOverride(Thread* thread, const Dict& dict,
742 const Object& mapping) {
743 return dictMergeImpl(thread, dict, mapping, Override::kOverride);
744}
745
746RawObject dictMergeError(Thread* thread, const Dict& dict,
747 const Object& mapping) {
748 return dictMergeImpl(thread, dict, mapping, Override::kError);
749}
750
751RawObject dictMergeIgnore(Thread* thread, const Dict& dict,
752 const Object& mapping) {
753 return dictMergeImpl(thread, dict, mapping, Override::kIgnore);
754}
755
756RawObject dictEq(Thread* thread, const Dict& left, const Dict& right) {
757 if (left.numItems() != right.numItems()) {
758 return Bool::falseObj();
759 }
760 HandleScope scope(thread);
761 Object key(&scope, NoneType::object());
762 Object left_value(&scope, NoneType::object());
763 word hash;
764 Object right_value(&scope, NoneType::object());
765 Object result(&scope, NoneType::object());
766 for (word i = 0; dictNextItemHash(left, &i, &key, &left_value, &hash);) {
767 right_value = dictAt(thread, right, key, hash);
768 if (right_value.isErrorNotFound()) {
769 return Bool::falseObj();
770 }
771 if (left_value == right_value) {
772 continue;
773 }
774 result = Interpreter::compareOperation(thread, EQ, left_value, right_value);
775 if (result.isErrorException()) {
776 // equality comparison raised
777 return *result;
778 }
779 result = Interpreter::isTrue(thread, *result);
780 if (result != Bool::trueObj()) {
781 // bool conversion raised or returned false
782 return *result;
783 }
784 }
785 return Bool::trueObj();
786}
787
788RawObject dictItemIteratorNext(Thread* thread, const DictItemIterator& iter) {
789 HandleScope scope(thread);
790 Dict dict(&scope, iter.iterable());
791 Object key(&scope, NoneType::object());
792 Object value(&scope, NoneType::object());
793 word i = iter.index();
794 if (dictNextItem(dict, &i, &key, &value)) {
795 iter.setIndex(i);
796 iter.setNumFound(iter.numFound() + 1);
797 return thread->runtime()->newTupleWith2(key, value);
798 }
799
800 // We hit the end.
801 iter.setIndex(i);
802 return Error::noMoreItems();
803}
804
805RawObject dictKeyIteratorNext(Thread* thread, const DictKeyIterator& iter) {
806 HandleScope scope(thread);
807 Dict dict(&scope, iter.iterable());
808 Object key(&scope, NoneType::object());
809 word i = iter.index();
810 if (dictNextKey(dict, &i, &key)) {
811 iter.setIndex(i);
812 iter.setNumFound(iter.numFound() + 1);
813 return *key;
814 }
815
816 // We hit the end.
817 iter.setIndex(i);
818 return Error::noMoreItems();
819}
820
821RawObject dictValueIteratorNext(Thread* thread, const DictValueIterator& iter) {
822 HandleScope scope(thread);
823 Dict dict(&scope, iter.iterable());
824 Object value(&scope, NoneType::object());
825 word i = iter.index();
826 if (dictNextValue(dict, &i, &value)) {
827 iter.setIndex(i);
828 iter.setNumFound(iter.numFound() + 1);
829 return *value;
830 }
831
832 // We hit the end.
833 iter.setIndex(i);
834 return Error::noMoreItems();
835}
836
837static const BuiltinAttribute kDictAttributes[] = {
838 {ID(_dict__num_items), RawDict::kNumItemsOffset, AttributeFlags::kHidden},
839 {ID(_dict__data), RawDict::kDataOffset, AttributeFlags::kHidden},
840 {ID(_dict__sparse), RawDict::kIndicesOffset, AttributeFlags::kHidden},
841 {ID(_dict__first_empty_item_index), RawDict::kFirstEmptyItemIndexOffset,
842 AttributeFlags::kHidden},
843};
844
845static const BuiltinAttribute kDictItemIteratorAttributes[] = {
846 {ID(_dict_item_iterator__iterable), RawDictItemIterator::kIterableOffset,
847 AttributeFlags::kHidden},
848 {ID(_dict_item_iterator__index), RawDictItemIterator::kIndexOffset,
849 AttributeFlags::kHidden},
850 {ID(_dict_item_iterator__num_found), RawDictItemIterator::kNumFoundOffset,
851 AttributeFlags::kHidden},
852};
853
854static const BuiltinAttribute kDictItemsAttributes[] = {
855 {ID(_dict_items__dict), RawDictItems::kDictOffset, AttributeFlags::kHidden},
856};
857
858static const BuiltinAttribute kDictKeyIteratorAttributes[] = {
859 {ID(_dict_key_iterator__iterable), RawDictKeyIterator::kIterableOffset,
860 AttributeFlags::kHidden},
861 {ID(_dict_key_iterator__index), RawDictKeyIterator::kIndexOffset,
862 AttributeFlags::kHidden},
863 {ID(_dict_key_iterator__num_found), RawDictKeyIterator::kNumFoundOffset,
864 AttributeFlags::kHidden},
865};
866
867static const BuiltinAttribute kDictKeysAttributes[] = {
868 {ID(_dict_keys__dict), RawDictKeys::kDictOffset, AttributeFlags::kHidden},
869};
870
871static const BuiltinAttribute kDictValueIteratorAttributes[] = {
872 {ID(_dict_value_iterator__iterable), RawDictValueIterator::kIterableOffset,
873 AttributeFlags::kHidden},
874 {ID(_dict_value_iterator__index), RawDictValueIterator::kIndexOffset,
875 AttributeFlags::kHidden},
876 {ID(_dict_value_iterator__num_found), RawDictValueIterator::kNumFoundOffset,
877 AttributeFlags::kHidden},
878};
879
880static const BuiltinAttribute kDictValuesAttributes[] = {
881 {ID(_dict_values__dict), RawDictValues::kDictOffset,
882 AttributeFlags::kHidden},
883};
884
885void initializeDictTypes(Thread* thread) {
886 addBuiltinType(thread, ID(dict), LayoutId::kDict,
887 /*superclass_id=*/LayoutId::kObject, kDictAttributes,
888 Dict::kSize, /*basetype=*/true);
889
890 addBuiltinType(thread, ID(dict_itemiterator), LayoutId::kDictItemIterator,
891 /*superclass_id=*/LayoutId::kObject,
892 kDictItemIteratorAttributes, DictItemIterator::kSize,
893 /*basetype=*/false);
894
895 addBuiltinType(thread, ID(dict_items), LayoutId::kDictItems,
896 /*superclass_id=*/LayoutId::kObject, kDictItemsAttributes,
897 DictItems::kSize, /*basetype=*/false);
898
899 addBuiltinType(thread, ID(dict_keyiterator), LayoutId::kDictKeyIterator,
900 /*superclass_id=*/LayoutId::kObject,
901 kDictKeyIteratorAttributes, DictKeyIterator::kSize,
902 /*basetype=*/false);
903
904 addBuiltinType(thread, ID(dict_keys), LayoutId::kDictKeys,
905 /*superclass_id=*/LayoutId::kObject, kDictKeysAttributes,
906 DictKeys::kSize, /*basetype=*/false);
907
908 addBuiltinType(thread, ID(dict_valueiterator), LayoutId::kDictValueIterator,
909 /*superclass_id=*/LayoutId::kObject,
910 kDictValueIteratorAttributes, DictValueIterator::kSize,
911 /*basetype=*/false);
912
913 addBuiltinType(thread, ID(dict_values), LayoutId::kDictValues,
914 /*superclass_id=*/LayoutId::kObject, kDictValuesAttributes,
915 DictValues::kSize, /*basetype=*/false);
916}
917
918RawObject METH(dict, clear)(Thread* thread, Arguments args) {
919 HandleScope scope(thread);
920 Object self(&scope, args.get(0));
921 if (!thread->runtime()->isInstanceOfDict(*self)) {
922 return thread->raiseRequiresType(self, ID(dict));
923 }
924 Dict dict(&scope, *self);
925 dictClear(thread, dict);
926 return NoneType::object();
927}
928
929RawObject METH(dict, __delitem__)(Thread* thread, Arguments args) {
930 HandleScope scope(thread);
931 Object self(&scope, args.get(0));
932 Object key(&scope, args.get(1));
933 Runtime* runtime = thread->runtime();
934 if (!runtime->isInstanceOfDict(*self)) {
935 return thread->raiseRequiresType(self, ID(dict));
936 }
937 Dict dict(&scope, *self);
938 Object hash_obj(&scope, Interpreter::hash(thread, key));
939 if (hash_obj.isErrorException()) return *hash_obj;
940 word hash = SmallInt::cast(*hash_obj).value();
941 // Remove the key. If it doesn't exist, throw a KeyError.
942 if (dictRemove(thread, dict, key, hash).isError()) {
943 return thread->raise(LayoutId::kKeyError, *key);
944 }
945 return NoneType::object();
946}
947
948RawObject METH(dict, __eq__)(Thread* thread, Arguments args) {
949 Runtime* runtime = thread->runtime();
950 HandleScope scope(thread);
951 Object self_obj(&scope, args.get(0));
952 if (!runtime->isInstanceOfDict(*self_obj)) {
953 return thread->raiseRequiresType(self_obj, ID(dict));
954 }
955 Object other_obj(&scope, args.get(1));
956 if (!runtime->isInstanceOfDict(*other_obj)) {
957 return NotImplementedType::object();
958 }
959 Dict a(&scope, *self_obj);
960 Dict b(&scope, *other_obj);
961 return dictEq(thread, a, b);
962}
963
964RawObject METH(dict, __len__)(Thread* thread, Arguments args) {
965 HandleScope scope(thread);
966 Object self(&scope, args.get(0));
967 if (!thread->runtime()->isInstanceOfDict(*self)) {
968 return thread->raiseRequiresType(self, ID(dict));
969 }
970 Dict dict(&scope, *self);
971 return SmallInt::fromWord(dict.numItems());
972}
973
974RawObject METH(dict, __iter__)(Thread* thread, Arguments args) {
975 HandleScope scope(thread);
976 Object self(&scope, args.get(0));
977 Runtime* runtime = thread->runtime();
978 if (!runtime->isInstanceOfDict(*self)) {
979 return thread->raiseRequiresType(self, ID(dict));
980 }
981 Dict dict(&scope, *self);
982 // .iter() on a dict returns a keys iterator
983 return runtime->newDictKeyIterator(thread, dict);
984}
985
986RawObject METH(dict, items)(Thread* thread, Arguments args) {
987 HandleScope scope(thread);
988 Object self(&scope, args.get(0));
989 Runtime* runtime = thread->runtime();
990 if (!runtime->isInstanceOfDict(*self)) {
991 return thread->raiseRequiresType(self, ID(dict));
992 }
993 Dict dict(&scope, *self);
994 return runtime->newDictItems(thread, dict);
995}
996
997RawObject METH(dict, keys)(Thread* thread, Arguments args) {
998 HandleScope scope(thread);
999 Object self(&scope, args.get(0));
1000 Runtime* runtime = thread->runtime();
1001 if (!runtime->isInstanceOfDict(*self)) {
1002 return thread->raiseRequiresType(self, ID(dict));
1003 }
1004 Dict dict(&scope, *self);
1005 return runtime->newDictKeys(thread, dict);
1006}
1007
1008RawObject METH(dict, popitem)(Thread* thread, Arguments args) {
1009 HandleScope scope(thread);
1010 Object self(&scope, args.get(0));
1011 Runtime* runtime = thread->runtime();
1012 if (!runtime->isInstanceOfDict(*self)) {
1013 return thread->raiseRequiresType(self, ID(dict));
1014 }
1015 Dict dict(&scope, *self);
1016 if (dict.numItems() == 0) {
1017 return thread->raiseWithFmt(LayoutId::kKeyError,
1018 "popitem(): dictionary is empty");
1019 }
1020 MutableTuple data(&scope, dict.data());
1021 for (word item_index = dict.firstEmptyItemIndex() - kItemNumPointers;
1022 item_index >= 0; item_index -= kItemNumPointers) {
1023 if (!itemIsEmpty(*data, item_index) &&
1024 !itemIsTombstone(*data, item_index)) {
1025 Object key(&scope, itemKey(*data, item_index));
1026 Object value(&scope, itemValue(*data, item_index));
1027 Tuple result(&scope, runtime->newTupleWith2(key, value));
1028 // Find the item for the entry and set a tombstone in it.
1029 // Note that this would take amortized cost O(1).
1030 word indices_index = -1;
1031 MutableBytes indices(&scope, dict.indices());
1032 uword perturb;
1033 word indices_mask;
1034 word hash = itemHash(*data, item_index);
1035 word num_indices = dict.numIndices();
1036 for (word current_index =
1037 probeBegin(num_indices, hash, &indices_mask, &perturb);
1038 ; current_index = probeNext(current_index, indices_mask, &perturb)) {
1039 word bytes_offset = indexOffset(current_index);
1040 uint32_t comp;
1041 if (indicesIsFull(*indices, bytes_offset, &comp) &&
1042 comp == item_index) {
1043 indices_index = current_index;
1044 break;
1045 }
1046 }
1047 DCHECK(indices_index >= 0, "cannot find index for entry in dict.sparse");
1048 itemSetTombstone(*data, item_index);
1049 indicesSetTombstone(*indices, indexOffset(indices_index));
1050 dict.setNumItems(dict.numItems() - 1);
1051 return *result;
1052 }
1053 }
1054 UNREACHABLE("dict.numItems() > 0, but couldn't find any active item");
1055}
1056
1057RawObject METH(dict, values)(Thread* thread, Arguments args) {
1058 HandleScope scope(thread);
1059 Object self(&scope, args.get(0));
1060 Runtime* runtime = thread->runtime();
1061 if (!runtime->isInstanceOfDict(*self)) {
1062 return thread->raiseRequiresType(self, ID(dict));
1063 }
1064 Dict dict(&scope, *self);
1065 return runtime->newDictValues(thread, dict);
1066}
1067
1068RawObject METH(dict, __new__)(Thread* thread, Arguments args) {
1069 HandleScope scope(thread);
1070 Object type_obj(&scope, args.get(0));
1071 Runtime* runtime = thread->runtime();
1072 if (!runtime->isInstanceOfType(*type_obj)) {
1073 return thread->raiseWithFmt(LayoutId::kTypeError, "not a type object");
1074 }
1075 Type type(&scope, *type_obj);
1076 if (type.builtinBase() != LayoutId::kDict) {
1077 return thread->raiseWithFmt(LayoutId::kTypeError, "not a subtype of dict");
1078 }
1079 Layout layout(&scope, type.instanceLayout());
1080 Dict result(&scope, runtime->newInstance(layout));
1081 result.setNumItems(0);
1082 result.setData(SmallInt::fromWord(0));
1083 result.setIndices(SmallInt::fromWord(0));
1084 result.setFirstEmptyItemIndex(0);
1085 return *result;
1086}
1087
1088RawObject METH(dict, __contains__)(Thread* thread, Arguments args) {
1089 HandleScope scope(thread);
1090 Object self(&scope, args.get(0));
1091 Object key(&scope, args.get(1));
1092 Runtime* runtime = thread->runtime();
1093 if (!runtime->isInstanceOfDict(*self)) {
1094 return thread->raiseRequiresType(self, ID(dict));
1095 }
1096 Object hash_obj(&scope, Interpreter::hash(thread, key));
1097 if (hash_obj.isErrorException()) {
1098 return *hash_obj;
1099 }
1100 Dict dict(&scope, *self);
1101 word hash = SmallInt::cast(*hash_obj).value();
1102 return dictIncludes(thread, dict, key, hash);
1103}
1104
1105RawObject METH(dict, pop)(Thread* thread, Arguments args) {
1106 HandleScope scope(thread);
1107 Object self(&scope, args.get(0));
1108 Object key(&scope, args.get(1));
1109 Runtime* runtime = thread->runtime();
1110 if (!runtime->isInstanceOfDict(*self)) {
1111 return thread->raiseRequiresType(self, ID(dict));
1112 }
1113 Dict dict(&scope, *self);
1114 Object hash_obj(&scope, Interpreter::hash(thread, key));
1115 if (hash_obj.isErrorException()) {
1116 return *hash_obj;
1117 }
1118 word hash = SmallInt::cast(*hash_obj).value();
1119 Object result(&scope, dictRemove(thread, dict, key, hash));
1120 if (result.isErrorNotFound()) {
1121 Object default_obj(&scope, args.get(2));
1122 return default_obj.isUnbound() ? thread->raise(LayoutId::kKeyError, *key)
1123 : *default_obj;
1124 }
1125 return *result;
1126}
1127
1128// TODO(T35787656): Instead of re-writing everything for every class, make a
1129// helper function that takes a member function (type check) and string for the
1130// Python symbol name
1131
1132RawObject METH(dict_itemiterator, __iter__)(Thread* thread, Arguments args) {
1133 HandleScope scope(thread);
1134 Object self(&scope, args.get(0));
1135 if (!self.isDictItemIterator()) {
1136 return thread->raiseRequiresType(self, ID(dict_itemiterator));
1137 }
1138 return *self;
1139}
1140
1141RawObject METH(dict_itemiterator, __next__)(Thread* thread, Arguments args) {
1142 HandleScope scope(thread);
1143 Object self(&scope, args.get(0));
1144 if (!self.isDictItemIterator()) {
1145 return thread->raiseRequiresType(self, ID(dict_itemiterator));
1146 }
1147 DictItemIterator iter(&scope, *self);
1148 Object value(&scope, dictItemIteratorNext(thread, iter));
1149 if (value.isError()) {
1150 return thread->raise(LayoutId::kStopIteration, NoneType::object());
1151 }
1152 return *value;
1153}
1154
1155RawObject METH(dict_itemiterator, __length_hint__)(Thread* thread,
1156 Arguments args) {
1157 HandleScope scope(thread);
1158 Object self(&scope, args.get(0));
1159 if (!self.isDictItemIterator()) {
1160 return thread->raiseRequiresType(self, ID(dict_itemiterator));
1161 }
1162 DictItemIterator iter(&scope, *self);
1163 Dict dict(&scope, iter.iterable());
1164 return SmallInt::fromWord(dict.numItems() - iter.numFound());
1165}
1166
1167RawObject METH(dict_items, __iter__)(Thread* thread, Arguments args) {
1168 HandleScope scope(thread);
1169 Object self(&scope, args.get(0));
1170 if (!self.isDictItems()) {
1171 return thread->raiseRequiresType(self, ID(dict_items));
1172 }
1173
1174 Dict dict(&scope, DictItems::cast(*self).dict());
1175 return thread->runtime()->newDictItemIterator(thread, dict);
1176}
1177
1178RawObject METH(dict_items, __len__)(Thread* thread, Arguments args) {
1179 HandleScope scope(thread);
1180 Object self(&scope, args.get(0));
1181 if (!self.isDictItems()) {
1182 return thread->raiseRequiresType(self, ID(dict_items));
1183 }
1184
1185 Dict dict(&scope, DictItems::cast(*self).dict());
1186 return thread->runtime()->newInt(dict.numItems());
1187}
1188
1189RawObject METH(dict_keyiterator, __iter__)(Thread* thread, Arguments args) {
1190 HandleScope scope(thread);
1191 Object self(&scope, args.get(0));
1192 if (!self.isDictKeyIterator()) {
1193 return thread->raiseRequiresType(self, ID(dict_keyiterator));
1194 }
1195 return *self;
1196}
1197
1198RawObject METH(dict_keyiterator, __next__)(Thread* thread, Arguments args) {
1199 HandleScope scope(thread);
1200 Object self(&scope, args.get(0));
1201 if (!self.isDictKeyIterator()) {
1202 return thread->raiseRequiresType(self, ID(dict_keyiterator));
1203 }
1204 DictKeyIterator iter(&scope, *self);
1205 Object value(&scope, dictKeyIteratorNext(thread, iter));
1206 if (value.isError()) {
1207 return thread->raise(LayoutId::kStopIteration, NoneType::object());
1208 }
1209 return *value;
1210}
1211
1212RawObject METH(dict_keyiterator, __length_hint__)(Thread* thread,
1213 Arguments args) {
1214 HandleScope scope(thread);
1215 Object self(&scope, args.get(0));
1216 if (!self.isDictKeyIterator()) {
1217 return thread->raiseRequiresType(self, ID(dict_keyiterator));
1218 }
1219 DictKeyIterator iter(&scope, *self);
1220 Dict dict(&scope, iter.iterable());
1221 return SmallInt::fromWord(dict.numItems() - iter.numFound());
1222}
1223
1224RawObject METH(dict_keys, __iter__)(Thread* thread, Arguments args) {
1225 HandleScope scope(thread);
1226 Object self(&scope, args.get(0));
1227 if (!self.isDictKeys()) {
1228 return thread->raiseRequiresType(self, ID(dict_keys));
1229 }
1230
1231 Dict dict(&scope, DictKeys::cast(*self).dict());
1232 return thread->runtime()->newDictKeyIterator(thread, dict);
1233}
1234
1235RawObject METH(dict_keys, __len__)(Thread* thread, Arguments args) {
1236 HandleScope scope(thread);
1237 Object self(&scope, args.get(0));
1238 if (!self.isDictKeys()) {
1239 return thread->raiseRequiresType(self, ID(dict_keys));
1240 }
1241
1242 Dict dict(&scope, DictKeys::cast(*self).dict());
1243 return thread->runtime()->newInt(dict.numItems());
1244}
1245
1246RawObject METH(dict_valueiterator, __iter__)(Thread* thread, Arguments args) {
1247 HandleScope scope(thread);
1248 Object self(&scope, args.get(0));
1249 if (!self.isDictValueIterator()) {
1250 return thread->raiseRequiresType(self, ID(dict_valueiterator));
1251 }
1252 return *self;
1253}
1254
1255RawObject METH(dict_valueiterator, __next__)(Thread* thread, Arguments args) {
1256 HandleScope scope(thread);
1257 Object self(&scope, args.get(0));
1258 if (!self.isDictValueIterator()) {
1259 return thread->raiseRequiresType(self, ID(dict_valueiterator));
1260 }
1261 DictValueIterator iter(&scope, *self);
1262 Object value(&scope, dictValueIteratorNext(thread, iter));
1263 if (value.isError()) {
1264 return thread->raise(LayoutId::kStopIteration, NoneType::object());
1265 }
1266 return *value;
1267}
1268
1269RawObject METH(dict_valueiterator, __length_hint__)(Thread* thread,
1270 Arguments args) {
1271 HandleScope scope(thread);
1272 Object self(&scope, args.get(0));
1273 if (!self.isDictValueIterator()) {
1274 return thread->raiseRequiresType(self, ID(dict_valueiterator));
1275 }
1276 DictValueIterator iter(&scope, *self);
1277 Dict dict(&scope, iter.iterable());
1278 return SmallInt::fromWord(dict.numItems() - iter.numFound());
1279}
1280
1281RawObject METH(dict_values, __iter__)(Thread* thread, Arguments args) {
1282 HandleScope scope(thread);
1283 Object self(&scope, args.get(0));
1284 if (!self.isDictValues()) {
1285 return thread->raiseRequiresType(self, ID(dict_values));
1286 }
1287
1288 Dict dict(&scope, DictValues::cast(*self).dict());
1289 return thread->runtime()->newDictValueIterator(thread, dict);
1290}
1291
1292RawObject METH(dict_values, __len__)(Thread* thread, Arguments args) {
1293 HandleScope scope(thread);
1294 Object self(&scope, args.get(0));
1295 if (!self.isDictValues()) {
1296 return thread->raiseRequiresType(self, ID(dict_values));
1297 }
1298
1299 Dict dict(&scope, DictValues::cast(*self).dict());
1300 return thread->runtime()->newInt(dict.numItems());
1301}
1302
1303} // namespace py