Nuitka
The Python compiler
Loading...
Searching...
No Matches
HelpersDictionaries.c
1// Copyright 2025, Kay Hayen, mailto:kay.hayen@gmail.com find license text at end of file
2
3/* These helpers are used to work with dictionaries.
4
5*/
6
7// This file is included from another C file, help IDEs to still parse it on
8// its own.
9#ifdef __IDE_ONLY__
10#include "nuitka/prelude.h"
11#endif
12
13// spell-checker: ignore ob_shash,dictiterobject,dictiteritems_type,dictiterkeys_type
14// spell-checker: ignore dictitervalues_type,dictviewobject dictvaluesview_type,dictkeysview_type
15
16#ifdef Py_GIL_DISABLED
17
18#define IS_DICT_SHARED(mp) _PyObject_GC_IS_SHARED(mp)
19#define SET_DICT_SHARED(mp) _PyObject_GC_SET_SHARED(mp)
20#define LOAD_INDEX(keys, size, idx) \
21 _Py_atomic_load_int##size##_relaxed(&((const int##size##_t *)keys->dk_indices)[idx]);
22#define STORE_INDEX(keys, size, idx, value) \
23 _Py_atomic_store_int##size##_relaxed(&((int##size##_t *)keys->dk_indices)[idx], (int##size##_t)value);
24
25#define LOCK_KEYS(keys) PyMutex_LockFlags(&keys->dk_mutex, _Py_LOCK_DONT_DETACH)
26#define UNLOCK_KEYS(keys) PyMutex_Unlock(&keys->dk_mutex)
27
28#define INCREF_KEYS_FT(dk) Nuitka_Py_dictkeys_incref(dk)
29#define DECREF_KEYS_FT(dk, shared) Nuitka_Py_dictkeys_decref(_PyInterpreterState_GET(), dk, shared)
30
31#define LOCK_KEYS_IF_SPLIT(keys, kind) \
32 if (kind == DICT_KEYS_SPLIT) { \
33 LOCK_KEYS(keys); \
34 }
35
36#define UNLOCK_KEYS_IF_SPLIT(keys, kind) \
37 if (kind == DICT_KEYS_SPLIT) { \
38 UNLOCK_KEYS(keys); \
39 }
40
41#else
42
43#define LOAD_INDEX(keys, size, idx) ((const int##size##_t *)(keys->dk_indices))[idx]
44#define STORE_INDEX(keys, size, idx, value) ((int##size##_t *)(keys->dk_indices))[idx] = (int##size##_t)value
45
46#define LOCK_KEYS(keys)
47#define UNLOCK_KEYS(keys)
48#define INCREF_KEYS_FT(dk)
49#define DECREF_KEYS_FT(dk, shared)
50#define LOCK_KEYS_IF_SPLIT(keys, kind)
51#define UNLOCK_KEYS_IF_SPLIT(keys, kind)
52
53#endif
54
55PyObject *DICT_GET_ITEM0(PyThreadState *tstate, PyObject *dict, PyObject *key) {
56 CHECK_OBJECT(dict);
57 assert(PyDict_Check(dict));
58
59 CHECK_OBJECT(key);
60
61 Py_hash_t hash;
62
63// This variant is uncertain about the hashing.
64#if PYTHON_VERSION < 0x300
65 if (PyString_CheckExact(key)) {
66 hash = ((PyStringObject *)key)->ob_shash;
67
68 if (unlikely(hash == -1)) {
69 hash = HASH_VALUE_WITHOUT_ERROR(tstate, key);
70 }
71
72 if (unlikely(hash == -1)) {
73 return NULL;
74 }
75 } else {
76 hash = HASH_VALUE_WITHOUT_ERROR(tstate, key);
77
78 if (unlikely(hash == -1)) {
79 return NULL;
80 }
81 }
82
83 PyDictObject *dict_object = (PyDictObject *)dict;
84 PyDictEntry *entry = (dict_object->ma_lookup)(dict_object, key, hash);
85
86 if (unlikely(entry == NULL || entry->me_value == NULL)) {
87 return NULL;
88 }
89
90 CHECK_OBJECT(entry->me_value);
91 return entry->me_value;
92#else
93 if (!PyUnicode_CheckExact(key) || (hash = ((PyASCIIObject *)key)->hash) == -1) {
94 hash = HASH_VALUE_WITHOUT_ERROR(tstate, key);
95
96 if (unlikely(hash == -1)) {
97 return NULL;
98 }
99 }
100
101 PyDictObject *dict_object = (PyDictObject *)dict;
102
103#if PYTHON_VERSION < 0x360
104 PyObject **value_addr;
105 PyDictKeyEntry *entry = dict_object->ma_keys->dk_lookup(dict_object, key, hash, &value_addr);
106
107 if (unlikely(entry == NULL || *value_addr == NULL)) {
108 return NULL;
109 }
110#else
111#if PYTHON_VERSION < 0x370
112 PyObject **value_addr;
113 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &value_addr, NULL);
114#elif PYTHON_VERSION < 0x3b0
115 PyObject *result;
116 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &result);
117#else
118 PyObject **value_addr;
119 Py_ssize_t ix = Nuitka_PyDictLookup(dict_object, key, hash, &value_addr);
120#endif
121
122 if (unlikely(ix < 0)) {
123 return NULL;
124 }
125#endif
126
127#if PYTHON_VERSION < 0x370 || PYTHON_VERSION >= 0x3b0
128 assert(value_addr != NULL);
129 PyObject *result = *value_addr;
130#endif
131 if (unlikely(result == NULL)) {
132 return NULL;
133 }
134
135 CHECK_OBJECT(result);
136 return result;
137#endif
138}
139
140PyObject *DICT_GET_ITEM1(PyThreadState *tstate, PyObject *dict, PyObject *key) {
141 CHECK_OBJECT(dict);
142 assert(PyDict_Check(dict));
143
144 CHECK_OBJECT(key);
145
146 Py_hash_t hash;
147
148// This variant is uncertain about the hashing.
149#if PYTHON_VERSION < 0x300
150 if (PyString_CheckExact(key)) {
151 hash = ((PyStringObject *)key)->ob_shash;
152
153 if (unlikely(hash == -1)) {
154 hash = HASH_VALUE_WITHOUT_ERROR(tstate, key);
155 }
156
157 if (unlikely(hash == -1)) {
158 return NULL;
159 }
160 } else {
161 hash = HASH_VALUE_WITHOUT_ERROR(tstate, key);
162
163 if (unlikely(hash == -1)) {
164 return NULL;
165 }
166 }
167
168 PyDictObject *dict_object = (PyDictObject *)dict;
169 PyDictEntry *entry = (dict_object->ma_lookup)(dict_object, key, hash);
170
171 if (unlikely(entry == NULL || entry->me_value == NULL)) {
172 return NULL;
173 }
174
175 CHECK_OBJECT(entry->me_value);
176 Py_INCREF(entry->me_value);
177 return entry->me_value;
178#else
179 if (!PyUnicode_CheckExact(key) || (hash = ((PyASCIIObject *)key)->hash) == -1) {
180 hash = HASH_VALUE_WITHOUT_ERROR(tstate, key);
181
182 if (unlikely(hash == -1)) {
183 return NULL;
184 }
185 }
186
187 PyDictObject *dict_object = (PyDictObject *)dict;
188
189#if PYTHON_VERSION < 0x360
190 PyObject **value_addr;
191 PyDictKeyEntry *entry = dict_object->ma_keys->dk_lookup(dict_object, key, hash, &value_addr);
192
193 if (unlikely(entry == NULL || *value_addr == NULL)) {
194 return NULL;
195 }
196#else
197#if PYTHON_VERSION < 0x370
198 PyObject **value_addr;
199 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &value_addr, NULL);
200#elif PYTHON_VERSION < 0x3b0
201 PyObject *result;
202 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &result);
203#else
204 PyObject **value_addr;
205 Py_ssize_t ix = Nuitka_PyDictLookup(dict_object, key, hash, &value_addr);
206#endif
207
208 if (unlikely(ix < 0)) {
209 return NULL;
210 }
211#endif
212
213#if PYTHON_VERSION < 0x370 || PYTHON_VERSION >= 0x3b0
214 assert(value_addr != NULL);
215 PyObject *result = *value_addr;
216#endif
217 if (unlikely(result == NULL)) {
218 return NULL;
219 }
220
221 CHECK_OBJECT(result);
222 Py_INCREF(result);
223 return result;
224#endif
225}
226
227#if PYTHON_VERSION >= 0x3c0
228static PyObject *Nuitka_CreateKeyError(PyThreadState *tstate, PyObject *key) {
229 return (PyObject *)Nuitka_BaseExceptionSingleArg_new(tstate, (PyTypeObject *)PyExc_KeyError, key);
230}
231#endif
232
233static void SET_CURRENT_EXCEPTION_KEY_ERROR(PyThreadState *tstate, PyObject *key) {
234#if PYTHON_VERSION < 0x3c0
235 /* Wrap all kinds of tuples, because normalization will later unwrap
236 * it, but then that changes the key for the KeyError, which is not
237 * welcome. The check is inexact, as the unwrapping one is too.
238 */
239 if (PyTuple_Check(key) || key == Py_None) {
240 PyObject *tuple = MAKE_TUPLE1(tstate, key);
241
242 SET_CURRENT_EXCEPTION_TYPE0_VALUE1(tstate, PyExc_KeyError, tuple);
243 } else {
244 SET_CURRENT_EXCEPTION_TYPE0_VALUE0(tstate, PyExc_KeyError, key);
245 }
246#else
247 struct Nuitka_ExceptionPreservationItem exception_state = {Nuitka_CreateKeyError(tstate, key)};
248
249 RESTORE_ERROR_OCCURRED_STATE(tstate, &exception_state);
250#endif
251}
252
253// TODO: This gives a reference, where would often be one time immediate users
254// of the value, forcing temporary variable releases on the outside. We need
255// to add indication of how long a value is going to be used, so in case where
256// we have the knowledge, we can provide the reference or not. Maybe we can
257// also include temporary nature of the key and/or dict releases to be done
258// inside of such helper code, possibly in template generation, where also
259// the hashing check wouldn't be needed anymore.
260PyObject *DICT_GET_ITEM_WITH_ERROR(PyThreadState *tstate, PyObject *dict, PyObject *key) {
261 CHECK_OBJECT(dict);
262 assert(PyDict_CheckExact(dict));
263
264 CHECK_OBJECT(key);
265
266 Py_hash_t hash;
267
268// This variant is uncertain about the hashing.
269#if PYTHON_VERSION < 0x300
270 if (PyString_CheckExact(key)) {
271 hash = ((PyStringObject *)key)->ob_shash;
272
273 if (unlikely(hash == -1)) {
274 hash = HASH_VALUE_WITHOUT_ERROR(tstate, key);
275 }
276
277 if (unlikely(hash == -1)) {
278 return NULL;
279 }
280 } else {
281 hash = HASH_VALUE_WITH_ERROR(tstate, key);
282
283 if (unlikely(hash == -1)) {
284 return NULL;
285 }
286 }
287
288 PyDictObject *dict_object = (PyDictObject *)dict;
289 PyDictEntry *entry = (dict_object->ma_lookup)(dict_object, key, hash);
290
291 if (unlikely(entry == NULL || entry->me_value == NULL)) {
292 SET_CURRENT_EXCEPTION_KEY_ERROR(tstate, key);
293
294 return NULL;
295 }
296
297 CHECK_OBJECT(entry->me_value);
298 Py_INCREF(entry->me_value);
299 return entry->me_value;
300#else
301 if (!PyUnicode_CheckExact(key) || (hash = ((PyASCIIObject *)key)->hash) == -1) {
302 hash = HASH_VALUE_WITH_ERROR(tstate, key);
303 if (unlikely(hash == -1)) {
304 return NULL;
305 }
306 }
307
308 PyDictObject *dict_object = (PyDictObject *)dict;
309
310#if PYTHON_VERSION < 0x360
311 PyObject **value_addr;
312 PyDictKeyEntry *entry = dict_object->ma_keys->dk_lookup(dict_object, key, hash, &value_addr);
313
314 if (unlikely(entry == NULL || *value_addr == NULL)) {
315 if (unlikely(HAS_ERROR_OCCURRED(tstate))) {
316 return NULL;
317 }
318
319 SET_CURRENT_EXCEPTION_KEY_ERROR(tstate, key);
320
321 return NULL;
322 }
323#else
324#if PYTHON_VERSION < 0x370
325 PyObject **value_addr;
326 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &value_addr, NULL);
327#elif PYTHON_VERSION < 0x3b0
328 PyObject *result;
329 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &result);
330#else
331 PyObject **value_addr;
332 Py_ssize_t ix = Nuitka_PyDictLookup(dict_object, key, hash, &value_addr);
333#endif
334
335 if (unlikely(ix < 0)) {
336 if (unlikely(HAS_ERROR_OCCURRED(tstate))) {
337 return NULL;
338 }
339
340 SET_CURRENT_EXCEPTION_KEY_ERROR(tstate, key);
341
342 return NULL;
343 }
344#endif
345
346#if PYTHON_VERSION < 0x370 || PYTHON_VERSION >= 0x3b0
347 assert(value_addr != NULL);
348 PyObject *result = *value_addr;
349#endif
350
351 if (unlikely(result == NULL)) {
352 if (unlikely(HAS_ERROR_OCCURRED(tstate))) {
353 return NULL;
354 }
355
356 SET_CURRENT_EXCEPTION_KEY_ERROR(tstate, key);
357
358 return NULL;
359 }
360
361 CHECK_OBJECT(result);
362 Py_INCREF(result);
363 return result;
364#endif
365}
366
367PyObject *DICT_GET_ITEM_WITH_HASH_ERROR0(PyThreadState *tstate, PyObject *dict, PyObject *key) {
368 CHECK_OBJECT(dict);
369 assert(PyDict_CheckExact(dict));
370
371 CHECK_OBJECT(key);
372
373 Py_hash_t hash;
374
375// This variant is uncertain about the hashing.
376#if PYTHON_VERSION < 0x300
377 if (PyString_CheckExact(key)) {
378 hash = ((PyStringObject *)key)->ob_shash;
379
380 if (unlikely(hash == -1)) {
381 hash = HASH_VALUE_WITHOUT_ERROR(tstate, key);
382 }
383
384 if (unlikely(hash == -1)) {
385 return NULL;
386 }
387 } else {
388 hash = HASH_VALUE_WITH_ERROR(tstate, key);
389
390 if (unlikely(hash == -1)) {
391 return NULL;
392 }
393 }
394
395 PyDictObject *dict_object = (PyDictObject *)dict;
396 PyDictEntry *entry = (dict_object->ma_lookup)(dict_object, key, hash);
397
398 if (unlikely(entry == NULL || entry->me_value == NULL)) {
399 return NULL;
400 }
401
402 CHECK_OBJECT(entry->me_value);
403 return entry->me_value;
404#else
405 if (!PyUnicode_CheckExact(key) || (hash = ((PyASCIIObject *)key)->hash) == -1) {
406 hash = HASH_VALUE_WITH_ERROR(tstate, key);
407 if (unlikely(hash == -1)) {
408 return NULL;
409 }
410 }
411
412 PyDictObject *dict_object = (PyDictObject *)dict;
413
414#if PYTHON_VERSION < 0x360
415 PyObject **value_addr;
416 PyDictKeyEntry *entry = dict_object->ma_keys->dk_lookup(dict_object, key, hash, &value_addr);
417
418 if (unlikely(entry == NULL || *value_addr == NULL)) {
419 return NULL;
420 }
421#else
422#if PYTHON_VERSION < 0x370
423 PyObject **value_addr;
424 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &value_addr, NULL);
425#elif PYTHON_VERSION < 0x3b0
426 PyObject *result;
427 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &result);
428#else
429 PyObject **value_addr;
430 Py_ssize_t ix = Nuitka_PyDictLookup(dict_object, key, hash, &value_addr);
431#endif
432
433 if (unlikely(ix < 0)) {
434 return NULL;
435 }
436#endif
437
438#if PYTHON_VERSION < 0x370 || PYTHON_VERSION >= 0x3b0
439 assert(value_addr != NULL);
440 PyObject *result = *value_addr;
441#endif
442
443 if (unlikely(result == NULL)) {
444 return NULL;
445 }
446
447 CHECK_OBJECT(result);
448 return result;
449#endif
450}
451
452// TODO: Exact copy of DICT_GET_ITEM_WITH_HASH_ERROR0 with just a Py_INCREF added, we should
453// generate these and all other variants rather than manually maintaining them, so we can
454// also specialize by type and not just result needs.
455PyObject *DICT_GET_ITEM_WITH_HASH_ERROR1(PyThreadState *tstate, PyObject *dict, PyObject *key) {
456 CHECK_OBJECT(dict);
457 assert(PyDict_CheckExact(dict));
458
459 CHECK_OBJECT(key);
460
461 Py_hash_t hash;
462
463// This variant is uncertain about the hashing.
464#if PYTHON_VERSION < 0x300
465 if (PyString_CheckExact(key)) {
466 hash = ((PyStringObject *)key)->ob_shash;
467
468 if (unlikely(hash == -1)) {
469 hash = HASH_VALUE_WITHOUT_ERROR(tstate, key);
470 }
471
472 if (unlikely(hash == -1)) {
473 return NULL;
474 }
475 } else {
476 hash = HASH_VALUE_WITH_ERROR(tstate, key);
477
478 if (unlikely(hash == -1)) {
479 return NULL;
480 }
481 }
482
483 PyDictObject *dict_object = (PyDictObject *)dict;
484 PyDictEntry *entry = (dict_object->ma_lookup)(dict_object, key, hash);
485
486 if (unlikely(entry == NULL || entry->me_value == NULL)) {
487 return NULL;
488 }
489
490 CHECK_OBJECT(entry->me_value);
491 Py_INCREF(entry->me_value);
492 return entry->me_value;
493#else
494 if (!PyUnicode_CheckExact(key) || (hash = ((PyASCIIObject *)key)->hash) == -1) {
495 hash = HASH_VALUE_WITH_ERROR(tstate, key);
496 if (unlikely(hash == -1)) {
497 return NULL;
498 }
499 }
500
501 PyDictObject *dict_object = (PyDictObject *)dict;
502
503#if PYTHON_VERSION < 0x360
504 PyObject **value_addr;
505 PyDictKeyEntry *entry = dict_object->ma_keys->dk_lookup(dict_object, key, hash, &value_addr);
506
507 if (unlikely(entry == NULL || *value_addr == NULL)) {
508 return NULL;
509 }
510#else
511#if PYTHON_VERSION < 0x370
512 PyObject **value_addr;
513 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &value_addr, NULL);
514#elif PYTHON_VERSION < 0x3b0
515 PyObject *result;
516 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &result);
517#else
518 PyObject **value_addr;
519 Py_ssize_t ix = Nuitka_PyDictLookup(dict_object, key, hash, &value_addr);
520#endif
521
522 if (unlikely(ix < 0)) {
523 return NULL;
524 }
525#endif
526
527#if PYTHON_VERSION < 0x370 || PYTHON_VERSION >= 0x3b0
528 assert(value_addr != NULL);
529 PyObject *result = *value_addr;
530#endif
531
532 if (unlikely(result == NULL)) {
533 return NULL;
534 }
535
536 CHECK_OBJECT(result);
537 Py_INCREF(result);
538 return result;
539#endif
540}
541
542int DICT_HAS_ITEM(PyThreadState *tstate, PyObject *dict, PyObject *key) {
543 CHECK_OBJECT(dict);
544 assert(PyDict_Check(dict));
545
546 CHECK_OBJECT(key);
547
548 Py_hash_t hash;
549
550// This variant is uncertain about the hashing.
551#if PYTHON_VERSION < 0x300
552 if (PyString_CheckExact(key)) {
553 hash = ((PyStringObject *)key)->ob_shash;
554
555 if (unlikely(hash == -1)) {
556 hash = HASH_VALUE_WITHOUT_ERROR(tstate, key);
557 }
558
559 if (unlikely(hash == -1)) {
560 return -1;
561 }
562 } else {
563 hash = HASH_VALUE_WITH_ERROR(tstate, key);
564
565 if (unlikely(hash == -1)) {
566 return -1;
567 }
568 }
569
570 PyDictObject *dict_object = (PyDictObject *)dict;
571 PyDictEntry *entry = (dict_object->ma_lookup)(dict_object, key, hash);
572
573 if (unlikely(entry == NULL || entry->me_value == NULL)) {
574 return 0;
575 }
576
577 return 1;
578#else
579 if (!PyUnicode_CheckExact(key) || (hash = ((PyASCIIObject *)key)->hash) == -1) {
580 hash = HASH_VALUE_WITH_ERROR(tstate, key);
581 if (unlikely(hash == -1)) {
582 return -1;
583 }
584 }
585
586 PyDictObject *dict_object = (PyDictObject *)dict;
587
588#if PYTHON_VERSION < 0x360
589 PyObject **value_addr;
590 PyDictKeyEntry *entry = dict_object->ma_keys->dk_lookup(dict_object, key, hash, &value_addr);
591
592 if (unlikely(entry == NULL || *value_addr == NULL)) {
593 return 0;
594 }
595
596 return 1;
597#else
598#if PYTHON_VERSION < 0x370
599 PyObject **value_addr;
600 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &value_addr, NULL);
601#elif PYTHON_VERSION < 0x3b0
602 PyObject *result;
603 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &result);
604#else
605 PyObject **value_addr;
606 Py_ssize_t ix = Nuitka_PyDictLookup(dict_object, key, hash, &value_addr);
607#endif
608
609 if (unlikely(ix < 0)) {
610 if (unlikely(HAS_ERROR_OCCURRED(tstate))) {
611 return -1;
612 }
613
614 return 0;
615 }
616
617#if PYTHON_VERSION < 0x370 || PYTHON_VERSION >= 0x3b0
618 assert(value_addr != NULL);
619 PyObject *result = *value_addr;
620#endif
621
622 if (unlikely(result == NULL)) {
623 return 0;
624 }
625#endif
626 return 1;
627#endif
628}
629
630#if PYTHON_VERSION < 0x300
631PyObject *DICT_ITEMS(PyObject *dict) {
632 CHECK_OBJECT(dict);
633 assert(PyDict_Check(dict));
634
635 PyDictObject *mp = (PyDictObject *)dict;
636
637 PyObject *result;
638 Py_ssize_t size;
639
640 /* Preallocate the list of tuples, to avoid allocations during
641 * the loop over the items, which could trigger GC, which
642 * could resize the dict. :-(
643 */
644retry:
645 size = mp->ma_used;
646 result = MAKE_LIST_EMPTY(tstate, size);
647 CHECK_OBJECT(result);
648
649 for (Py_ssize_t i = 0; i < size; i++) {
650 // Later populated.
651 PyObject *item = MAKE_TUPLE_EMPTY(tstate, 2);
652 CHECK_OBJECT(item);
653
654 PyList_SET_ITEM(result, i, item);
655 }
656
657 if (unlikely(size != mp->ma_used)) {
658 // Garbage collection can compactify dictionaries.
659 Py_DECREF(result);
660 goto retry;
661 }
662
663 // Nothing must cause any functions to be called
664 PyDictEntry *ep = mp->ma_table;
665 Py_ssize_t mask = mp->ma_mask;
666
667 for (Py_ssize_t i = 0, j = 0; i <= mask; i++) {
668 PyObject *value = ep[i].me_value;
669 if (value != NULL) {
670 PyObject *key = ep[i].me_key;
671 PyObject *item = PyList_GET_ITEM(result, j);
672 PyTuple_SET_ITEM0(item, 0, key);
673 PyTuple_SET_ITEM0(item, 1, value);
674
675 j++;
676 }
677 }
678
679 assert(PyList_GET_SIZE(result) == size);
680
681 return result;
682}
683
684#if PYTHON_VERSION < 0x300
685PyObject *DICT_KEYS(PyObject *dict) {
686 CHECK_OBJECT(dict);
687 assert(PyDict_Check(dict));
688
689 PyDictObject *mp = (PyDictObject *)dict;
690
691 PyObject *result;
692 Py_ssize_t size;
693
694 /* Preallocate the list of tuples, to avoid allocations during
695 * the loop over the items, which could trigger GC, which
696 * could resize the dict. :-(
697 */
698retry:
699 size = mp->ma_used;
700 result = MAKE_LIST_EMPTY(tstate, size);
701 CHECK_OBJECT(result);
702
703 if (unlikely(size != mp->ma_used)) {
704 // Garbage collection can compactify dictionaries.
705 Py_DECREF(result);
706 goto retry;
707 }
708
709 // Nothing must cause any functions to be called
710 PyDictEntry *ep = mp->ma_table;
711 Py_ssize_t mask = mp->ma_mask;
712
713 for (Py_ssize_t i = 0, j = 0; i <= mask; i++) {
714 PyObject *value = ep[i].me_value;
715 if (value != NULL) {
716 PyObject *key = ep[i].me_key;
717 PyList_SET_ITEM0(result, j, key);
718
719 j++;
720 }
721 }
722
723 assert(PyList_GET_SIZE(result) == size);
724
725 return result;
726}
727#endif
728
729#if PYTHON_VERSION < 0x300
730PyObject *DICT_VALUES(PyObject *dict) {
731 CHECK_OBJECT(dict);
732 assert(PyDict_Check(dict));
733
734 PyDictObject *mp = (PyDictObject *)dict;
735
736 PyObject *result;
737 Py_ssize_t size;
738
739 /* Preallocate the list of tuples, to avoid allocations during
740 * the loop over the items, which could trigger GC, which
741 * could resize the dict. :-(
742 */
743retry:
744 size = mp->ma_used;
745 result = MAKE_LIST_EMPTY(tstate, size);
746 CHECK_OBJECT(result);
747
748 if (unlikely(size != mp->ma_used)) {
749 // Garbage collection can compactify dictionaries.
750 Py_DECREF(result);
751 goto retry;
752 }
753
754 // Nothing must cause any functions to be called
755 PyDictEntry *ep = mp->ma_table;
756 Py_ssize_t mask = mp->ma_mask;
757
758 for (Py_ssize_t i = 0, j = 0; i <= mask; i++) {
759 PyObject *value = ep[i].me_value;
760 if (value != NULL) {
761 PyList_SET_ITEM0(result, j, value);
762
763 j++;
764 }
765 }
766
767 assert(PyList_GET_SIZE(result) == size);
768
769 return result;
770}
771#endif
772
773#endif
774
775#if PYTHON_VERSION < 0x300
776typedef struct {
777 PyObject_HEAD PyDictObject *di_dict;
778 Py_ssize_t di_used;
779 Py_ssize_t di_pos;
780 PyObject *di_result;
781 Py_ssize_t len;
782} dictiterobject;
783#endif
784
785#if PYTHON_VERSION >= 0x300 && PYTHON_VERSION < 0x350
786typedef struct {
787 PyObject_HEAD PyDictObject *dv_dict;
788} _PyDictViewObject;
789
790#endif
791
792// Generic helper for various dictionary iterations, to be inlined.
793static inline PyObject *_MAKE_DICT_ITERATOR(PyThreadState *tstate, PyDictObject *dict, PyTypeObject *type,
794 bool is_iteritems) {
795 CHECK_OBJECT((PyObject *)dict);
796 assert(PyDict_CheckExact((PyObject *)dict));
797
798#if PYTHON_VERSION < 0x300
799 dictiterobject *di = (dictiterobject *)Nuitka_GC_New(type);
800 CHECK_OBJECT(di);
801 Py_INCREF(dict);
802 di->di_dict = dict;
803 di->di_used = dict->ma_used;
804 di->di_pos = 0;
805 di->len = dict->ma_used;
806 if (is_iteritems) {
807 // TODO: Have this as faster variants, we do these sometimes.
808 di->di_result = MAKE_TUPLE2(tstate, Py_None, Py_None);
809 CHECK_OBJECT(di->di_result);
810 } else {
811 di->di_result = NULL;
812 }
813
814 Nuitka_GC_Track(di);
815 return (PyObject *)di;
816#else
817 _PyDictViewObject *dv = (_PyDictViewObject *)Nuitka_GC_New(type);
818 CHECK_OBJECT(dv);
819
820 Py_INCREF(dict);
821 dv->dv_dict = dict;
822
823 Nuitka_GC_Track(dv);
824 return (PyObject *)dv;
825#endif
826}
827
828PyObject *DICT_ITERITEMS(PyThreadState *tstate, PyObject *dict) {
829#if PYTHON_VERSION < 0x270
830 static PyTypeObject *dictiteritems_type = NULL;
831
832 if (unlikely(dictiteritems_type == NULL)) {
833 dictiteritems_type =
834 Py_TYPE(CALL_FUNCTION_NO_ARGS(tstate, PyObject_GetAttrString(const_dict_empty, "iteritems")));
835 }
836
837 return _MAKE_DICT_ITERATOR(tstate, (PyDictObject *)dict, dictiteritems_type, true);
838#elif PYTHON_VERSION < 0x300
839 return _MAKE_DICT_ITERATOR(tstate, (PyDictObject *)dict, &PyDictIterItem_Type, true);
840#else
841 return _MAKE_DICT_ITERATOR(tstate, (PyDictObject *)dict, &PyDictItems_Type, true);
842#endif
843}
844
845PyObject *DICT_ITERKEYS(PyThreadState *tstate, PyObject *dict) {
846#if PYTHON_VERSION < 0x270
847 static PyTypeObject *dictiterkeys_type = NULL;
848
849 if (unlikely(dictiterkeys_type == NULL)) {
850 dictiterkeys_type =
851 Py_TYPE(CALL_FUNCTION_NO_ARGS(tstate, PyObject_GetAttrString(const_dict_empty, "iterkeys")));
852 }
853
854 return _MAKE_DICT_ITERATOR(tstate, (PyDictObject *)dict, dictiterkeys_type, false);
855#elif PYTHON_VERSION < 0x300
856 return _MAKE_DICT_ITERATOR(tstate, (PyDictObject *)dict, &PyDictIterKey_Type, false);
857#else
858 return _MAKE_DICT_ITERATOR(tstate, (PyDictObject *)dict, &PyDictKeys_Type, false);
859#endif
860}
861
862PyObject *DICT_ITERVALUES(PyThreadState *tstate, PyObject *dict) {
863#if PYTHON_VERSION < 0x270
864 static PyTypeObject *dictitervalues_type = NULL;
865
866 if (unlikely(dictitervalues_type == NULL)) {
867 dictitervalues_type =
868 Py_TYPE(CALL_FUNCTION_NO_ARGS(tstate, PyObject_GetAttrString(const_dict_empty, "itervalues")));
869 }
870
871 return _MAKE_DICT_ITERATOR(tstate, (PyDictObject *)dict, dictitervalues_type, false);
872#elif PYTHON_VERSION < 0x300
873 return _MAKE_DICT_ITERATOR(tstate, (PyDictObject *)dict, &PyDictIterValue_Type, false);
874#else
875 return _MAKE_DICT_ITERATOR(tstate, (PyDictObject *)dict, &PyDictValues_Type, false);
876#endif
877}
878
879typedef struct {
880 PyObject_HEAD PyDictObject *dv_dict;
881} dictviewobject;
882
883static PyObject *_MAKE_DICT_VIEW(PyDictObject *dict, PyTypeObject *type) {
884 CHECK_OBJECT((PyObject *)dict);
885 assert(PyDict_CheckExact((PyObject *)dict));
886
887 dictviewobject *dv = (dictviewobject *)Nuitka_GC_New(type);
888
889 CHECK_OBJECT(dv);
890 Py_INCREF(dict);
891 dv->dv_dict = (PyDictObject *)dict;
892 Nuitka_GC_Track(dv);
893 return (PyObject *)dv;
894}
895
896PyObject *DICT_VIEWKEYS(PyObject *dict) {
897#if PYTHON_VERSION < 0x270
898 static PyTypeObject *dictkeysview_type = NULL;
899
900 if (unlikely(dictkeysview_type)) {
901 dictkeysview_type = Py_TYPE(PyObject_GetIter(PyObject_GetAttrString(const_dict_empty, "viewkeys")));
902 }
903
904 return _MAKE_DICT_VIEW((PyDictObject *)dict, dictkeysview_type);
905#else
906 return _MAKE_DICT_VIEW((PyDictObject *)dict, &PyDictKeys_Type);
907#endif
908}
909
910PyObject *DICT_VIEWVALUES(PyObject *dict) {
911#if PYTHON_VERSION < 0x270
912 static PyTypeObject *dictvaluesview_type = NULL;
913
914 if (unlikely(dictvaluesview_type)) {
915 dictvaluesview_type = Py_TYPE(PyObject_GetIter(PyObject_GetAttrString(const_dict_empty, "viewvalues")));
916 }
917
918 return _MAKE_DICT_VIEW((PyDictObject *)dict, dictvaluesview_type);
919#else
920 return _MAKE_DICT_VIEW((PyDictObject *)dict, &PyDictValues_Type);
921#endif
922}
923
924PyObject *DICT_VIEWITEMS(PyObject *dict) {
925#if PYTHON_VERSION < 0x270
926 static PyTypeObject *dictvaluesview_type = NULL;
927
928 if (unlikely(dictvaluesview_type)) {
929 dictvaluesview_type = Py_TYPE(PyObject_GetIter(PyObject_GetAttrString(const_dict_empty, "viewitems")));
930 }
931
932 return _MAKE_DICT_VIEW((PyDictObject *)dict, dictvaluesview_type);
933#else
934 return _MAKE_DICT_VIEW((PyDictObject *)dict, &PyDictItems_Type);
935#endif
936}
937
938#if PYTHON_VERSION >= 0x300
939static PyDictObject *_Nuitka_AllocatePyDictObject(PyThreadState *tstate) {
940 PyDictObject *result_mp;
941
942#if NUITKA_DICT_HAS_FREELIST
943 // This is the CPython name, spell-checker: ignore numfree
944
945#if PYTHON_VERSION < 0x3d0
946 PyDictObject **items = tstate->interp->dict_state.free_list;
947 int *numfree = &tstate->interp->dict_state.numfree;
948#else
949 struct _Py_object_freelists *freelists = _Nuitka_object_freelists_GET(tstate);
950 struct _Py_dict_freelist *state = &freelists->dicts;
951 PyDictObject **items = state->items;
952 int *numfree = &state->numfree;
953#endif
954
955 if (*numfree) {
956 (*numfree) -= 1;
957 result_mp = items[*numfree];
958
959 Nuitka_Py_NewReference((PyObject *)result_mp);
960
961 assert(PyDict_CheckExact((PyObject *)result_mp));
962 assert(result_mp != NULL);
963 } else
964#endif
965 {
966 result_mp = (PyDictObject *)Nuitka_GC_New(&PyDict_Type);
967 }
968
969 return result_mp;
970}
971#endif
972
973#if PYTHON_VERSION >= 0x360
974static PyDictKeysObject *_Nuitka_AllocatePyDictKeysObject(PyThreadState *tstate, Py_ssize_t keys_size) {
975 // CPython names, spell-checker: ignore numfree,dictkeys
976 PyDictKeysObject *dk;
977
978// TODO: Cannot always use cached objects. Need to also consider
979// "log2_size == PyDict_LOG_MINSIZE && unicode" as a criterion,
980// seems it can only be used for the smallest keys type.
981#if NUITKA_DICT_HAS_FREELIST && 0
982#if PYTHON_VERSION < 0x3d0
983 PyDictKeysObject **items = tstate->interp->dict_state.keys_free_list;
984 int *numfree = &tstate->interp->dict_state.keys_numfree;
985#else
986 struct _Py_object_freelists *freelists = _Nuitka_object_freelists_GET(tstate);
987 struct _Py_dictkeys_freelist *state = &freelists->dictkeys;
988 PyDictKeysObject **items = state->items;
989 int *numfree = &state->numfree;
990#endif
991
992 if (*numfree) {
993 (*numfree) -= 1;
994 dk = items[*numfree];
995 } else
996#endif
997 {
998#if PYTHON_VERSION < 0x3d0
999 dk = (PyDictKeysObject *)NuitkaObject_Malloc(keys_size);
1000#else
1001 dk = (PyDictKeysObject *)NuitkaMem_Malloc(keys_size);
1002#endif
1003 }
1004
1005 return dk;
1006}
1007#endif
1008
1009#if PYTHON_VERSION >= 0x360 && !defined(_NUITKA_EXPERIMENTAL_DISABLE_DICT_OPT)
1010
1011// Usable fraction of keys.
1012#define DK_USABLE_FRACTION(n) (((n) << 1) / 3)
1013
1014static Py_ssize_t _Nuitka_Py_PyDict_KeysSize(PyDictKeysObject *keys) {
1015#if PYTHON_VERSION < 0x360
1016 return sizeof(PyDictKeysObject) + (DK_SIZE(keys) - 1) * sizeof(PyDictKeyEntry);
1017#elif PYTHON_VERSION < 0x370
1018 return (sizeof(PyDictKeysObject) - Py_MEMBER_SIZE(PyDictKeysObject, dk_indices) + DK_IXSIZE(keys) * DK_SIZE(keys) +
1019 DK_USABLE_FRACTION(DK_SIZE(keys)) * sizeof(PyDictKeyEntry));
1020#elif PYTHON_VERSION < 0x3b0
1021 return (sizeof(PyDictKeysObject) + DK_IXSIZE(keys) * DK_SIZE(keys) +
1022 DK_USABLE_FRACTION(DK_SIZE(keys)) * sizeof(PyDictKeyEntry));
1023#else
1024 size_t entry_size = keys->dk_kind == DICT_KEYS_GENERAL ? sizeof(PyDictKeyEntry) : sizeof(PyDictUnicodeEntry);
1025 return (sizeof(PyDictKeysObject) + ((size_t)1 << keys->dk_log2_index_bytes) +
1026 DK_USABLE_FRACTION(DK_SIZE(keys)) * entry_size);
1027#endif
1028}
1029#endif
1030
1031#if PYTHON_VERSION < 0x3b0
1032typedef PyObject *PyDictValues;
1033#endif
1034
1035#if PYTHON_VERSION < 0x360
1036#define DK_ENTRIES_SIZE(keys) (keys->dk_size)
1037#elif PYTHON_VERSION < 0x3b0
1038#define DK_ENTRIES_SIZE(keys) DK_USABLE_FRACTION(DK_SIZE(keys))
1039#else
1040#define DK_ENTRIES_SIZE(keys) (keys->dk_nentries)
1041#endif
1042
1043// More than 2/3 of the keys are used, i.e. no space is wasted.
1044#if PYTHON_VERSION < 0x360
1045#define IS_COMPACT(dict_mp) (dict_mp->ma_used >= (dict_mp->ma_keys->dk_size * 2) / 3)
1046#else
1047#define IS_COMPACT(dict_mp) (dict_mp->ma_used >= (dict_mp->ma_keys->dk_nentries * 2) / 3)
1048#endif
1049
1050static inline PyDictValues *_Nuitka_PyDict_new_values(Py_ssize_t size) {
1051#if PYTHON_VERSION < 0x3b0
1052 Py_ssize_t values_size = sizeof(PyObject *) * size;
1053
1054 return (PyDictValues *)NuitkaMem_Malloc(values_size);
1055#elif PYTHON_VERSION < 0x3d0
1056 Py_ssize_t values_size = sizeof(PyObject *) * size;
1057
1058 // With Python3.11-3.12 a prefix is allocated too.
1059 size_t prefix_size = _Py_SIZE_ROUND_UP(size + 2, sizeof(PyObject *));
1060 size_t n = prefix_size + values_size;
1061 uint8_t *mem = (uint8_t *)NuitkaMem_Malloc(n);
1062 assert(mem != NULL);
1063
1064 assert(prefix_size % sizeof(PyObject *) == 0);
1065 mem[prefix_size - 1] = (uint8_t)prefix_size;
1066
1067 return (PyDictValues *)(mem + prefix_size);
1068#else
1069 assert(size >= 1);
1070 size_t suffix_size = _Py_SIZE_ROUND_UP(size, sizeof(PyObject *));
1071 assert(suffix_size < 128);
1072 assert(suffix_size % sizeof(PyObject *) == 0);
1073 size_t n = (size + 1) * sizeof(PyObject *) + suffix_size;
1074 PyDictValues *result = (PyDictValues *)NuitkaMem_Malloc(n);
1075
1076 result->embedded = 0;
1077 result->size = 0;
1078 assert(size < 256);
1079 result->capacity = (uint8_t)size;
1080 return result;
1081#endif
1082}
1083
1084#if PYTHON_VERSION >= 0x3d0
1085
1086static PyDictValues *_Nuitka_PyDict_copy_values(PyDictValues *values) {
1087 PyDictValues *new_values = _Nuitka_PyDict_new_values(values->capacity);
1088 if (unlikely(new_values == NULL)) {
1089 return NULL;
1090 }
1091
1092 new_values->size = values->size;
1093
1094 uint8_t *values_order = get_insertion_order_array(values);
1095 uint8_t *new_values_order = get_insertion_order_array(new_values);
1096
1097 memcpy(new_values_order, values_order, values->capacity);
1098
1099 for (int i = 0; i < values->capacity; i++) {
1100 new_values->values[i] = values->values[i];
1101 }
1102 assert(new_values->embedded == 0);
1103 return new_values;
1104}
1105#endif
1106
1107#include "HelpersDictionariesGenerated.c"
1108
1109void DICT_CLEAR(PyObject *dict) {
1110 CHECK_OBJECT(dict);
1111 assert(PyDict_CheckExact(dict));
1112
1113 // TODO: Could inline this for enhanced optimization, but it does
1114 // some pretty sophisticated memory handling.
1115 PyDict_Clear(dict);
1116}
1117
1118#if PYTHON_VERSION >= 0x3b0
1119static inline int Nuitka_py_get_index_from_order(PyDictObject *mp, Py_ssize_t i) {
1120 assert(mp->ma_used <= SHARED_KEYS_MAX_SIZE);
1121#if PYTHON_VERSION < 0x3d0
1122 assert(i < (((char *)mp->ma_values)[-2]));
1123 return ((char *)mp->ma_values)[-3 - i];
1124#else
1125 assert(i < mp->ma_values->size);
1126 uint8_t *array = get_insertion_order_array(mp->ma_values);
1127 return array[i];
1128#endif
1129}
1130#endif
1131
1132#if PYTHON_VERSION >= 0x3b0
1133
1134static inline Py_ssize_t Nuitka_Py_dictkeys_get_index(const PyDictKeysObject *keys, Py_ssize_t i) {
1135 int log2size = DK_LOG_SIZE(keys);
1136 Py_ssize_t ix;
1137
1138 if (log2size < 8) {
1139 ix = LOAD_INDEX(keys, 8, i);
1140
1141 } else if (log2size < 16) {
1142 ix = LOAD_INDEX(keys, 16, i);
1143 }
1144#if SIZEOF_VOID_P > 4
1145 else if (log2size >= 32) {
1146 ix = LOAD_INDEX(keys, 64, i);
1147 }
1148#endif
1149 else {
1150 ix = LOAD_INDEX(keys, 32, i);
1151 }
1152
1153 assert(ix >= DKIX_DUMMY);
1154 return ix;
1155}
1156
1157// From CPython
1158#define PERTURB_SHIFT 5
1159
1160static Py_ssize_t Nuitka_Py_unicodekeys_lookup_generic(PyDictObject *mp, PyDictKeysObject *dk, PyObject *key,
1161 Py_hash_t hash) {
1162 PyDictUnicodeEntry *ep0 = DK_UNICODE_ENTRIES(dk);
1163
1164 size_t mask = DK_MASK(dk);
1165 size_t perturb = hash;
1166 size_t i = (size_t)hash & mask;
1167
1168 while (1) {
1169 Py_ssize_t ix = Nuitka_Py_dictkeys_get_index(dk, i);
1170
1171 if (ix >= 0) {
1172 PyDictUnicodeEntry *ep = &ep0[ix];
1173
1174 assert(ep->me_key != NULL);
1175 assert(PyUnicode_CheckExact(ep->me_key));
1176
1177 if (ep->me_key == key) {
1178 return ix;
1179 }
1180
1181 if (Nuitka_Py_unicode_get_hash(ep->me_key) == hash) {
1182 PyObject *startkey = ep->me_key;
1183 Py_INCREF(startkey);
1184 nuitka_bool cmp = RICH_COMPARE_EQ_NBOOL_UNICODE_OBJECT(startkey, key);
1185 Py_DECREF(startkey);
1186
1187 if (unlikely(cmp == NUITKA_BOOL_EXCEPTION)) {
1188 return DKIX_ERROR;
1189 }
1190
1191 if (dk == mp->ma_keys && ep->me_key == startkey) {
1192 if (cmp == NUITKA_BOOL_TRUE) {
1193 return ix;
1194 }
1195 } else {
1196 // In case of changed dictionary, trigger restart in caller.
1197 return DKIX_KEY_CHANGED;
1198 }
1199 }
1200 } else if (ix == DKIX_EMPTY) {
1201 return DKIX_EMPTY;
1202 }
1203 perturb >>= PERTURB_SHIFT;
1204 i = mask & (i * 5 + perturb + 1);
1205 }
1206
1207 NUITKA_CANNOT_GET_HERE("Nuitka_Py_unicodekeys_lookup_generic failed");
1208}
1209
1210Py_ssize_t Nuitka_Py_unicodekeys_lookup_unicode(PyDictKeysObject *dk, PyObject *key, Py_hash_t hash) {
1211 assert(PyUnicode_CheckExact(key));
1212 assert(dk->dk_kind != DICT_KEYS_GENERAL);
1213
1214 PyDictUnicodeEntry *ep0 = DK_UNICODE_ENTRIES(dk);
1215
1216 size_t mask = DK_MASK(dk);
1217 size_t perturb = hash;
1218 size_t i = (size_t)hash & mask;
1219
1220 while (true) {
1221 Py_ssize_t ix = Nuitka_Py_dictkeys_get_index(dk, i);
1222
1223 // Found it.
1224 if (ix >= 0) {
1225 PyDictUnicodeEntry *ep = &ep0[ix];
1226 assert(ep->me_key != NULL);
1227 assert(PyUnicode_CheckExact(ep->me_key));
1228
1229 if (ep->me_key == key || (Nuitka_Py_unicode_get_hash(ep->me_key) == hash &&
1230 RICH_COMPARE_EQ_CBOOL_UNICODE_UNICODE(ep->me_key, key))) {
1231 return ix;
1232 }
1233 } else if (ix == DKIX_EMPTY) {
1234 return DKIX_EMPTY;
1235 }
1236 perturb >>= PERTURB_SHIFT;
1237
1238 i = mask & (i * 5 + perturb + 1);
1239 ix = Nuitka_Py_dictkeys_get_index(dk, i);
1240
1241 if (ix >= 0) {
1242 PyDictUnicodeEntry *ep = &ep0[ix];
1243
1244 assert(ep->me_key != NULL);
1245 assert(PyUnicode_CheckExact(ep->me_key));
1246
1247 if (ep->me_key == key || (Nuitka_Py_unicode_get_hash(ep->me_key) == hash &&
1248 RICH_COMPARE_EQ_CBOOL_UNICODE_UNICODE(ep->me_key, key))) {
1249 return ix;
1250 }
1251 } else if (ix == DKIX_EMPTY) {
1252 return DKIX_EMPTY;
1253 }
1254
1255 perturb >>= PERTURB_SHIFT;
1256 i = mask & (i * 5 + perturb + 1);
1257 }
1258
1259 NUITKA_CANNOT_GET_HERE("Nuitka_Py_unicodekeys_lookup_unicode failed");
1260}
1261
1262// Search key from Generic table.
1263static Py_ssize_t Nuitka_Py_dictkeys_generic_lookup(PyDictObject *mp, PyDictKeysObject *dk, PyObject *key,
1264 Py_hash_t hash) {
1265 PyDictKeyEntry *ep0 = DK_ENTRIES(dk);
1266
1267 size_t mask = DK_MASK(dk);
1268 size_t perturb = hash;
1269 size_t i = (size_t)hash & mask;
1270
1271 while (1) {
1272 Py_ssize_t ix = Nuitka_Py_dictkeys_get_index(dk, i);
1273
1274 if (ix >= 0) {
1275 PyDictKeyEntry *ep = &ep0[ix];
1276 assert(ep->me_key != NULL);
1277 if (ep->me_key == key) {
1278 return ix;
1279 }
1280 if (ep->me_hash == hash) {
1281 PyObject *startkey = ep->me_key;
1282 Py_INCREF(startkey);
1283 nuitka_bool cmp = RICH_COMPARE_EQ_NBOOL_OBJECT_OBJECT(startkey, key);
1284 Py_DECREF(startkey);
1285
1286 if (unlikely(cmp == NUITKA_BOOL_EXCEPTION)) {
1287 return DKIX_ERROR;
1288 }
1289 if (dk == mp->ma_keys && ep->me_key == startkey) {
1290 if (cmp == NUITKA_BOOL_TRUE) {
1291 return ix;
1292 }
1293 } else {
1294 // In case of changed dictionary, trigger restart in caller.
1295 return DKIX_KEY_CHANGED;
1296 }
1297 }
1298 } else if (ix == DKIX_EMPTY) {
1299 return DKIX_EMPTY;
1300 }
1301 perturb >>= PERTURB_SHIFT;
1302 i = mask & (i * 5 + perturb + 1);
1303 }
1304}
1305
1306Py_ssize_t Nuitka_PyDictLookup(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject ***value_addr) {
1307 PyDictKeysObject *dk;
1308 DictKeysKind kind;
1309 Py_ssize_t ix;
1310
1311 _Py_CRITICAL_SECTION_ASSERT_OBJECT_LOCKED(mp);
1312restart:
1313 dk = mp->ma_keys;
1314 kind = (DictKeysKind)dk->dk_kind;
1315
1316 if (kind != DICT_KEYS_GENERAL) {
1317 if (PyUnicode_CheckExact(key)) {
1318#ifdef Py_GIL_DISABLED
1319 if (kind == DICT_KEYS_SPLIT) {
1320 ix = Nuitka_Py_unicodekeys_lookup_unicode_threadsafe(dk, key, hash);
1321
1322 if (ix == DKIX_KEY_CHANGED) {
1323 LOCK_KEYS(dk);
1324 ix = Nuitka_Py_unicodekeys_lookup_unicode(dk, key, hash);
1325 UNLOCK_KEYS(dk);
1326 }
1327 } else
1328#endif
1329 {
1330 ix = Nuitka_Py_unicodekeys_lookup_unicode(dk, key, hash);
1331 }
1332 } else {
1333 INCREF_KEYS_FT(dk);
1334 LOCK_KEYS_IF_SPLIT(dk, kind);
1335
1336 ix = Nuitka_Py_unicodekeys_lookup_generic(mp, dk, key, hash);
1337
1338 UNLOCK_KEYS_IF_SPLIT(dk, kind);
1339 DECREF_KEYS_FT(dk, IS_DICT_SHARED(mp));
1340
1341 // Dictionary lookup changed the dictionary, retry.
1342 if (ix == DKIX_KEY_CHANGED) {
1343 goto restart;
1344 }
1345 }
1346
1347 if (ix >= 0) {
1348 if (kind == DICT_KEYS_SPLIT) {
1349 *value_addr = &mp->ma_values->values[ix];
1350 } else {
1351 *value_addr = &DK_UNICODE_ENTRIES(dk)[ix].me_value;
1352 }
1353 } else {
1354 *value_addr = NULL;
1355 }
1356 } else {
1357 ix = Nuitka_Py_dictkeys_generic_lookup(mp, dk, key, hash);
1358
1359 // Dictionary lookup changed the dictionary, retry.
1360 if (ix == DKIX_KEY_CHANGED) {
1361 goto restart;
1362 }
1363
1364 if (ix >= 0) {
1365 *value_addr = &DK_ENTRIES(dk)[ix].me_value;
1366 } else {
1367 *value_addr = NULL;
1368 }
1369 }
1370
1371 return ix;
1372}
1373
1374Py_ssize_t Nuitka_PyDictLookupStr(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject ***value_addr) {
1375 assert(PyUnicode_CheckExact(key));
1376
1377 PyDictKeysObject *dk = mp->ma_keys;
1378 assert(dk->dk_kind != DICT_KEYS_GENERAL);
1379
1380 Py_ssize_t ix = Nuitka_Py_unicodekeys_lookup_unicode(dk, key, hash);
1381
1382 if (ix >= 0) {
1383 if (dk->dk_kind == DICT_KEYS_SPLIT) {
1384 *value_addr = &mp->ma_values->values[ix];
1385 } else {
1386 *value_addr = &DK_UNICODE_ENTRIES(dk)[ix].me_value;
1387 }
1388 } else {
1389 *value_addr = NULL;
1390 }
1391
1392 return ix;
1393}
1394
1395#endif
1396
1397bool Nuitka_DictNext(PyObject *dict, Py_ssize_t *pos, PyObject **key_ptr, PyObject **value_ptr) {
1398 CHECK_OBJECT(dict);
1399 assert(PyDict_CheckExact(dict));
1400 assert(key_ptr != NULL);
1401 assert(value_ptr != NULL);
1402
1403#if PYTHON_VERSION < 0x300
1404 Py_ssize_t i = *pos;
1405
1406 PyDictEntry *ep = ((PyDictObject *)dict)->ma_table;
1407 Py_ssize_t mask = ((PyDictObject *)dict)->ma_mask;
1408
1409 while (i <= mask && ep[i].me_value == NULL) {
1410 i++;
1411 }
1412
1413 *pos = i + 1;
1414
1415 if (i > mask) {
1416 return false;
1417 }
1418
1419 *key_ptr = ep[i].me_key;
1420 *value_ptr = ep[i].me_value;
1421
1422 return true;
1423
1424#elif PYTHON_VERSION < 0x360
1425 PyDictObject *mp = (PyDictObject *)dict;
1426 PyObject **dict_value_ptr;
1427 Py_ssize_t offset;
1428
1429 Py_ssize_t i = *pos;
1430 assert(i >= 0);
1431
1432 if (mp->ma_values) {
1433 dict_value_ptr = &mp->ma_values[i];
1434 offset = sizeof(PyObject *);
1435 } else {
1436 dict_value_ptr = &mp->ma_keys->dk_entries[i].me_value;
1437 offset = sizeof(PyDictKeyEntry);
1438 }
1439
1440 Py_ssize_t mask = DK_MASK(mp->ma_keys);
1441
1442 while ((i <= mask) && (*dict_value_ptr == NULL)) {
1443 dict_value_ptr = (PyObject **)(((char *)dict_value_ptr) + offset);
1444 i++;
1445 }
1446
1447 if (i > mask) {
1448 return false;
1449 }
1450
1451 *key_ptr = mp->ma_keys->dk_entries[i].me_key;
1452 *value_ptr = *dict_value_ptr;
1453 *pos = i + 1;
1454
1455 return true;
1456
1457#elif PYTHON_VERSION < 0x3b0
1458 PyDictObject *mp = (PyDictObject *)dict;
1459 PyDictKeyEntry *entry;
1460 PyObject *value;
1461
1462 Py_ssize_t i = *pos;
1463 assert(i >= 0);
1464
1465 if (mp->ma_values) {
1466 if (i >= mp->ma_used) {
1467 return false;
1468 }
1469
1470 entry = &DK_ENTRIES(mp->ma_keys)[i];
1471 value = DK_VALUE(mp, i);
1472
1473 assert(value != NULL);
1474 } else {
1475 Py_ssize_t n = mp->ma_keys->dk_nentries;
1476
1477 if (i >= n) {
1478 return false;
1479 }
1480
1481 entry = &DK_ENTRIES(mp->ma_keys)[i];
1482
1483 while (i < n && entry->me_value == NULL) {
1484 entry += 1;
1485 i += 1;
1486 }
1487
1488 if (i >= n) {
1489 return false;
1490 }
1491
1492 value = entry->me_value;
1493 }
1494
1495 *pos = i + 1;
1496
1497 *key_ptr = entry->me_key;
1498 *value_ptr = value;
1499
1500 return true;
1501#else
1502 PyDictObject *mp = (PyDictObject *)dict;
1503 Py_ssize_t i = *pos;
1504 PyObject *key, *value;
1505
1506 if (mp->ma_values) {
1507 // Shared keys dictionary.
1508 assert(mp->ma_used <= SHARED_KEYS_MAX_SIZE);
1509
1510 if (i >= mp->ma_used) {
1511 return false;
1512 }
1513
1514 int index = Nuitka_py_get_index_from_order(mp, i);
1515 value = mp->ma_values->values[index];
1516
1517 key = DK_UNICODE_ENTRIES(mp->ma_keys)[index].me_key;
1518
1519 assert(value != NULL);
1520 } else {
1521 Py_ssize_t n = mp->ma_keys->dk_nentries;
1522
1523 if (i >= n) {
1524 return false;
1525 }
1526
1527 // Unicode keys or general keys have different sizes, make sure to index
1528 // the right type, the algorithm is the same however.
1529 if (DK_IS_UNICODE(mp->ma_keys)) {
1530 PyDictUnicodeEntry *entry_ptr = &DK_UNICODE_ENTRIES(mp->ma_keys)[i];
1531
1532 while (i < n && entry_ptr->me_value == NULL) {
1533 entry_ptr++;
1534 i++;
1535 }
1536
1537 if (i >= n) {
1538 return false;
1539 }
1540
1541 key = entry_ptr->me_key;
1542 value = entry_ptr->me_value;
1543 } else {
1544 PyDictKeyEntry *entry_ptr = &DK_ENTRIES(mp->ma_keys)[i];
1545
1546 while (i < n && entry_ptr->me_value == NULL) {
1547 entry_ptr++;
1548 i++;
1549 }
1550
1551 if (i >= n) {
1552 return false;
1553 }
1554
1555 key = entry_ptr->me_key;
1556 value = entry_ptr->me_value;
1557 }
1558 }
1559
1560 *pos = i + 1;
1561
1562 *key_ptr = key;
1563 *value_ptr = value;
1564
1565 return true;
1566#endif
1567}
1568
1569PyObject *TO_DICT(PyThreadState *tstate, PyObject *seq_obj, PyObject *dict_obj) {
1570 PyObject *result;
1571
1572 if (seq_obj != NULL) {
1573 CHECK_OBJECT(seq_obj);
1574
1575 // Fast path for dictionaries.
1576 if (PyDict_CheckExact(seq_obj)) {
1577 result = DICT_COPY(tstate, seq_obj);
1578 } else {
1579 result = MAKE_DICT_EMPTY(tstate);
1580
1581 Py_INCREF(seq_obj);
1582
1583#if PYTHON_VERSION >= 0x300
1584 int res = HAS_ATTR_BOOL2(tstate, seq_obj, const_str_plain_keys);
1585
1586 if (unlikely(res == -1)) {
1587 Py_DECREF(seq_obj);
1588 return NULL;
1589 }
1590#else
1591 int res = HAS_ATTR_BOOL(tstate, seq_obj, const_str_plain_keys) ? 1 : 0;
1592#endif
1593
1594 if (res) {
1595 res = PyDict_Merge(result, seq_obj, 1);
1596 } else {
1597 res = PyDict_MergeFromSeq2(result, seq_obj, 1);
1598 }
1599
1600 Py_DECREF(seq_obj);
1601
1602 if (unlikely(res == -1)) {
1603 return NULL;
1604 }
1605 }
1606 } else {
1607 result = MAKE_DICT_EMPTY(tstate);
1608 }
1609
1610 // TODO: Should specialize for dict_obj/seq_obj presence to save a bit of time
1611 // and complexity.
1612 if (dict_obj != NULL) {
1613 CHECK_OBJECT(dict_obj);
1614
1615 int res = PyDict_Merge(result, dict_obj, 1);
1616
1617 if (unlikely(res == -1)) {
1618 return NULL;
1619 }
1620 }
1621
1622 return result;
1623}
1624
1625#if _NUITKA_MAINTAIN_DICT_VERSION_TAG
1626uint64_t nuitka_dict_version_tag_counter = ((uint64_t)1) << 32;
1627#endif
1628
1629#if NUITKA_DICT_HAS_FREELIST
1630PyObject *MAKE_DICT_EMPTY(PyThreadState *tstate) {
1631 PyDictObject *empty_dict_mp = (PyDictObject *)const_dict_empty;
1632
1633#if PYTHON_VERSION < 0x3c0
1634 empty_dict_mp->ma_keys->dk_refcnt++;
1635#endif
1636
1637 PyDictObject *result_mp = _Nuitka_AllocatePyDictObject(tstate);
1638
1639 result_mp->ma_keys = empty_dict_mp->ma_keys;
1640 result_mp->ma_values = empty_dict_mp->ma_values;
1641 result_mp->ma_used = 0;
1642#if PYTHON_VERSION >= 0x3c0
1643 result_mp->ma_version_tag = DICT_NEXT_VERSION(_PyInterpreterState_GET());
1644#elif PYTHON_VERSION >= 0x360
1645 result_mp->ma_version_tag = 1;
1646#endif
1647
1648 // Key reference needs to be counted on older Python
1649#if defined(Py_REF_DEBUG) && PYTHON_VERSION < 0x3c0
1650 _Py_RefTotal++;
1651#endif
1652
1653 // No Nuitka_GC_Track for the empty dictionary.
1654 return (PyObject *)result_mp;
1655}
1656#endif
1657
1658PyObject *MAKE_DICT(PyObject **pairs, Py_ssize_t size) {
1659 PyObject *result = _PyDict_NewPresized(size);
1660
1661 // Reject usage like this.
1662 assert(size > 0);
1663 for (Py_ssize_t i = 0; i < size; i++) {
1664 PyObject *key = pairs[i * 2];
1665 PyObject *value = pairs[i * 2 + 1];
1666
1667 int res = PyDict_SetItem(result, key, value);
1668
1669 if (unlikely(res != 0)) {
1670 Py_DECREF(result);
1671 return NULL;
1672 }
1673 }
1674
1675 return result;
1676}
1677
1678PyObject *MAKE_DICT_X(PyObject **pairs, Py_ssize_t size) {
1679 PyObject *result = _PyDict_NewPresized(size);
1680
1681 // Reject usage like this.
1682 assert(size > 0);
1683 for (Py_ssize_t i = 0; i < size; i++) {
1684 PyObject *value = pairs[i * 2 + 1];
1685
1686 if (value != NULL) {
1687 PyObject *key = pairs[i * 2];
1688 CHECK_OBJECT(key);
1689 CHECK_OBJECT(value);
1690
1691 int res = PyDict_SetItem(result, key, value);
1692
1693 if (unlikely(res != 0)) {
1694 Py_DECREF(result);
1695 return NULL;
1696 }
1697 }
1698 }
1699
1700 return result;
1701}
1702
1703PyObject *MAKE_DICT_X_CSTR(char const **keys, PyObject **values, Py_ssize_t size) {
1704 PyObject *result = _PyDict_NewPresized(size);
1705
1706 // Reject usage like this.
1707 assert(size > 0);
1708 for (Py_ssize_t i = 0; i < size; i++) {
1709 PyObject *value = values[i];
1710
1711 if (value != NULL) {
1712 CHECK_OBJECT(value);
1713
1714 int res = PyDict_SetItemString(result, keys[i], value);
1715
1716 if (unlikely(res != 0)) {
1717 Py_DECREF(result);
1718 return NULL;
1719 }
1720 }
1721 }
1722
1723 return result;
1724}
1725
1726// Part of "Nuitka", an optimizing Python compiler that is compatible and
1727// integrates with CPython, but also works on its own.
1728//
1729// Licensed under the Apache License, Version 2.0 (the "License");
1730// you may not use this file except in compliance with the License.
1731// You may obtain a copy of the License at
1732//
1733// http://www.apache.org/licenses/LICENSE-2.0
1734//
1735// Unless required by applicable law or agreed to in writing, software
1736// distributed under the License is distributed on an "AS IS" BASIS,
1737// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
1738// See the License for the specific language governing permissions and
1739// limitations under the License.
Nuitka_ExceptionPreservationItem
Definition exceptions.h:712
dictiterobject
Definition HelpersDictionaries.c:776
dictviewobject
Definition HelpersDictionaries.c:879