Nuitka
The Python compiler
Loading...
Searching...
No Matches
HelpersDictionaries.c
1// Copyright 2026, 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// spell-checker: ignore qsbr,decref,dkix,ixsize
16
17// Only needed for 3.13t right now, but I suspect we'll need to remove this
18// guard later.
19#ifdef Py_GIL_DISABLED
20
21// From CPython
22#define PyDict_LOG_MINSIZE 3
23
24#if defined(WITH_FREELISTS) && PYTHON_VERSION >= 0x3d0
25static struct _Py_dictkeys_freelist *get_dictkeys_freelist(void) {
26 struct _Py_object_freelists *freelists = _Py_object_freelists_GET();
27 return &freelists->dictkeys;
28}
29#endif
30
31static void Nuitka_Py_dictkeys_free_keys_object(PyDictKeysObject *keys, bool use_qsbr) {
32#ifdef Py_GIL_DISABLED
33 if (use_qsbr) {
34 NuitkaMem_FreeDelayed(keys);
35 return;
36 }
37#endif
38
39#if defined(WITH_FREELISTS) && PYTHON_VERSION >= 0x3d0
40 struct _Py_dictkeys_freelist *freelist = get_dictkeys_freelist();
41 if (DK_LOG_SIZE(keys) == PyDict_LOG_MINSIZE && freelist->numfree < PyDict_MAXFREELIST && freelist->numfree >= 0 &&
42 DK_IS_UNICODE(keys)) {
43 freelist->items[freelist->numfree++] = keys;
44 return;
45 }
46#endif
47 PyMem_Free(keys);
48}
49
50#endif
51
52#ifdef Py_GIL_DISABLED
53
54static inline void ASSERT_DICT_LOCKED(PyObject *op) { _Py_CRITICAL_SECTION_ASSERT_OBJECT_LOCKED(op); }
55#define ASSERT_DICT_LOCKED(op) ASSERT_DICT_LOCKED(_Py_CAST(PyObject *, op))
56#define ASSERT_WORLD_STOPPED_OR_DICT_LOCKED(op) \
57 if (!_PyInterpreterState_GET()->stoptheworld.world_stopped) { \
58 ASSERT_DICT_LOCKED(op); \
59 }
60#define ASSERT_WORLD_STOPPED_OR_OBJ_LOCKED(op) \
61 if (!_PyInterpreterState_GET()->stoptheworld.world_stopped) { \
62 _Py_CRITICAL_SECTION_ASSERT_OBJECT_LOCKED(op); \
63 }
64
65#define IS_DICT_SHARED(mp) _PyObject_GC_IS_SHARED(mp)
66#define SET_DICT_SHARED(mp) _PyObject_GC_SET_SHARED(mp)
67#define LOAD_INDEX(keys, size, idx) \
68 _Py_atomic_load_int##size##_relaxed(&((const int##size##_t *)keys->dk_indices)[idx]);
69#define STORE_INDEX(keys, size, idx, value) \
70 _Py_atomic_store_int##size##_relaxed(&((int##size##_t *)keys->dk_indices)[idx], (int##size##_t)value);
71#define ASSERT_OWNED_OR_SHARED(mp) assert(_Py_IsOwnedByCurrentThread((PyObject *)mp) || IS_DICT_SHARED(mp));
72
73#define LOCK_KEYS_IF_SPLIT(keys, kind) \
74 if (kind == DICT_KEYS_SPLIT) { \
75 LOCK_KEYS(keys); \
76 }
77
78#define UNLOCK_KEYS_IF_SPLIT(keys, kind) \
79 if (kind == DICT_KEYS_SPLIT) { \
80 UNLOCK_KEYS(keys); \
81 }
82
83#define ASSERT_KEYS_LOCKED(keys) assert(PyMutex_IsLocked(&keys->dk_mutex))
84#define LOAD_SHARED_KEY(key) _Py_atomic_load_ptr_acquire(&key)
85#define STORE_SHARED_KEY(key, value) _Py_atomic_store_ptr_release(&key, value)
86// Inc refs the keys object, giving the previous value
87#define INCREF_KEYS(dk) _Py_atomic_add_ssize(&dk->dk_refcnt, 1)
88// Dec refs the keys object, giving the previous value
89#define DECREF_KEYS(dk) _Py_atomic_add_ssize(&dk->dk_refcnt, -1)
90#define LOAD_KEYS_NENTRIES(keys) _Py_atomic_load_ssize_relaxed(&keys->dk_nentries)
91
92static inline void Nuitka_Py_dictkeys_incref(PyDictKeysObject *dk) {
93 if (FT_ATOMIC_LOAD_SSIZE_RELAXED(dk->dk_refcnt) == _Py_IMMORTAL_REFCNT) {
94 return;
95 }
96#ifdef Py_REF_DEBUG
97 _Py_IncRefTotal(_PyThreadState_GET());
98#endif
99 INCREF_KEYS(dk);
100}
101
102static inline void Nuitka_Py_dictkeys_decref(PyInterpreterState *interp, PyDictKeysObject *dk, bool use_qsbr) {
103 if (FT_ATOMIC_LOAD_SSIZE_RELAXED(dk->dk_refcnt) == _Py_IMMORTAL_REFCNT) {
104 return;
105 }
106 assert(FT_ATOMIC_LOAD_SSIZE(dk->dk_refcnt) > 0);
107#ifdef Py_REF_DEBUG
108 _Py_DecRefTotal(_PyThreadState_GET());
109#endif
110 if (DECREF_KEYS(dk) == 1) {
111 if (DK_IS_UNICODE(dk)) {
112 PyDictUnicodeEntry *entries = DK_UNICODE_ENTRIES(dk);
113 Py_ssize_t i, n;
114 for (i = 0, n = dk->dk_nentries; i < n; i++) {
115 Py_XDECREF(entries[i].me_key);
116 Py_XDECREF(entries[i].me_value);
117 }
118 } else {
119 PyDictKeyEntry *entries = DK_ENTRIES(dk);
120 Py_ssize_t i, n;
121 for (i = 0, n = dk->dk_nentries; i < n; i++) {
122 Py_XDECREF(entries[i].me_key);
123 Py_XDECREF(entries[i].me_value);
124 }
125 }
126 Nuitka_Py_dictkeys_free_keys_object(dk, use_qsbr);
127 }
128}
129
130#define INCREF_KEYS_FT(dk) Nuitka_Py_dictkeys_incref(dk)
131#define DECREF_KEYS_FT(dk, shared) Nuitka_Py_dictkeys_decref(_PyInterpreterState_GET(), dk, shared)
132
133static inline void split_keys_entry_added(PyDictKeysObject *keys) {
134 ASSERT_KEYS_LOCKED(keys);
135
136 // We increase before we decrease so we never get too small of a value
137 // when we're racing with reads
138 _Py_atomic_store_ssize_relaxed(&keys->dk_nentries, keys->dk_nentries + 1);
139 _Py_atomic_store_ssize_release(&keys->dk_usable, keys->dk_usable - 1);
140}
141
142#else /* Py_GIL_DISABLED */
143
144#define ASSERT_DICT_LOCKED(op)
145#define ASSERT_WORLD_STOPPED_OR_DICT_LOCKED(op)
146#define ASSERT_WORLD_STOPPED_OR_OBJ_LOCKED(op)
147#define ASSERT_KEYS_LOCKED(keys)
148#define LOAD_SHARED_KEY(key) key
149#define STORE_SHARED_KEY(key, value) key = value
150#define INCREF_KEYS(dk) dk->dk_refcnt++
151#define DECREF_KEYS(dk) dk->dk_refcnt--
152#define LOAD_KEYS_NENTRIES(keys) keys->dk_nentries
153#define INCREF_KEYS_FT(dk)
154#define DECREF_KEYS_FT(dk, shared)
155#define LOCK_KEYS_IF_SPLIT(keys, kind)
156#define UNLOCK_KEYS_IF_SPLIT(keys, kind)
157#define IS_DICT_SHARED(mp) (false)
158#define SET_DICT_SHARED(mp)
159#define LOAD_INDEX(keys, size, idx) ((const int##size##_t *)(keys->dk_indices))[idx]
160#define STORE_INDEX(keys, size, idx, value) ((int##size##_t *)(keys->dk_indices))[idx] = (int##size##_t)value
161#endif
162
163Py_ssize_t Nuitka_Py_dict_lookup_threadsafe(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject **value_addr);
164
165PyObject *DICT_GET_ITEM0(PyThreadState *tstate, PyObject *dict, PyObject *key) {
166 CHECK_OBJECT(dict);
167 assert(PyDict_Check(dict));
168
169 CHECK_OBJECT(key);
170
171 Py_hash_t hash;
172
173// This variant is uncertain about the hashing.
174#if PYTHON_VERSION < 0x300
175 if (PyString_CheckExact(key)) {
176 hash = ((PyStringObject *)key)->ob_shash;
177
178 if (unlikely(hash == -1)) {
179 hash = HASH_VALUE_WITHOUT_ERROR(tstate, key);
180 }
181
182 if (unlikely(hash == -1)) {
183 return NULL;
184 }
185 } else {
186 hash = HASH_VALUE_WITHOUT_ERROR(tstate, key);
187
188 if (unlikely(hash == -1)) {
189 return NULL;
190 }
191 }
192
193 PyDictObject *dict_object = (PyDictObject *)dict;
194 PyDictEntry *entry = (dict_object->ma_lookup)(dict_object, key, hash);
195
196 if (unlikely(entry == NULL || entry->me_value == NULL)) {
197 return NULL;
198 }
199
200 CHECK_OBJECT(entry->me_value);
201 return entry->me_value;
202#else
203 if (!PyUnicode_CheckExact(key) || (hash = ((PyASCIIObject *)key)->hash) == -1) {
204 hash = HASH_VALUE_WITHOUT_ERROR(tstate, key);
205
206 if (unlikely(hash == -1)) {
207 return NULL;
208 }
209 }
210
211 PyDictObject *dict_object = (PyDictObject *)dict;
212
213#if PYTHON_VERSION < 0x360
214 PyObject **value_addr;
215 PyDictKeyEntry *entry = dict_object->ma_keys->dk_lookup(dict_object, key, hash, &value_addr);
216
217 if (unlikely(entry == NULL || *value_addr == NULL)) {
218 return NULL;
219 }
220#else
221#if PYTHON_VERSION < 0x370
222 PyObject **value_addr;
223 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &value_addr, NULL);
224#elif PYTHON_VERSION < 0x3b0
225 PyObject *result;
226 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &result);
227#elif defined(Py_GIL_DISABLED)
228 PyObject *result;
229 Py_ssize_t ix = Nuitka_Py_dict_lookup_threadsafe(dict_object, key, hash, &result);
230#else
231 PyObject **value_addr;
232 Py_ssize_t ix = Nuitka_PyDictLookup(dict_object, key, hash, &value_addr);
233#endif
234
235 if (unlikely(ix < 0)) {
236 return NULL;
237 }
238#endif
239
240#if PYTHON_VERSION < 0x370 || (PYTHON_VERSION >= 0x3b0 && !defined(Py_GIL_DISABLED))
241 assert(value_addr != NULL);
242 PyObject *result = *value_addr;
243#endif
244 if (unlikely(result == NULL)) {
245 return NULL;
246 }
247
248 CHECK_OBJECT(result);
249 return result;
250#endif
251}
252
253PyObject *DICT_GET_ITEM1(PyThreadState *tstate, PyObject *dict, PyObject *key) {
254 CHECK_OBJECT(dict);
255 assert(PyDict_Check(dict));
256
257 CHECK_OBJECT(key);
258
259 Py_hash_t hash;
260
261// This variant is uncertain about the hashing.
262#if PYTHON_VERSION < 0x300
263 if (PyString_CheckExact(key)) {
264 hash = ((PyStringObject *)key)->ob_shash;
265
266 if (unlikely(hash == -1)) {
267 hash = HASH_VALUE_WITHOUT_ERROR(tstate, key);
268 }
269
270 if (unlikely(hash == -1)) {
271 return NULL;
272 }
273 } else {
274 hash = HASH_VALUE_WITHOUT_ERROR(tstate, key);
275
276 if (unlikely(hash == -1)) {
277 return NULL;
278 }
279 }
280
281 PyDictObject *dict_object = (PyDictObject *)dict;
282 PyDictEntry *entry = (dict_object->ma_lookup)(dict_object, key, hash);
283
284 if (unlikely(entry == NULL || entry->me_value == NULL)) {
285 return NULL;
286 }
287
288 CHECK_OBJECT(entry->me_value);
289 Py_INCREF(entry->me_value);
290 return entry->me_value;
291#else
292 if (!PyUnicode_CheckExact(key) || (hash = ((PyASCIIObject *)key)->hash) == -1) {
293 hash = HASH_VALUE_WITHOUT_ERROR(tstate, key);
294
295 if (unlikely(hash == -1)) {
296 return NULL;
297 }
298 }
299
300 PyDictObject *dict_object = (PyDictObject *)dict;
301
302#if PYTHON_VERSION < 0x360
303 PyObject **value_addr;
304 PyDictKeyEntry *entry = dict_object->ma_keys->dk_lookup(dict_object, key, hash, &value_addr);
305
306 if (unlikely(entry == NULL || *value_addr == NULL)) {
307 return NULL;
308 }
309#else
310#if PYTHON_VERSION < 0x370
311 PyObject **value_addr;
312 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &value_addr, NULL);
313#elif PYTHON_VERSION < 0x3b0
314 PyObject *result;
315 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &result);
316#elif defined(Py_GIL_DISABLED)
317 PyObject *result;
318 Py_ssize_t ix = Nuitka_Py_dict_lookup_threadsafe(dict_object, key, hash, &result);
319#else
320 PyObject **value_addr;
321 Py_ssize_t ix = Nuitka_PyDictLookup(dict_object, key, hash, &value_addr);
322#endif
323
324 if (unlikely(ix < 0)) {
325 return NULL;
326 }
327#endif
328
329#if PYTHON_VERSION < 0x370 || (PYTHON_VERSION >= 0x3b0 && !defined(Py_GIL_DISABLED))
330 assert(value_addr != NULL);
331 PyObject *result = *value_addr;
332#endif
333 if (unlikely(result == NULL)) {
334 return NULL;
335 }
336
337 CHECK_OBJECT(result);
338 Py_INCREF(result);
339 return result;
340#endif
341}
342
343#if PYTHON_VERSION >= 0x3c0
344static PyObject *Nuitka_CreateKeyError(PyThreadState *tstate, PyObject *key) {
345 return (PyObject *)Nuitka_BaseExceptionSingleArg_new(tstate, (PyTypeObject *)PyExc_KeyError, key);
346}
347#endif
348
349static void SET_CURRENT_EXCEPTION_KEY_ERROR(PyThreadState *tstate, PyObject *key) {
350#if PYTHON_VERSION < 0x3c0
351 /* Wrap all kinds of tuples, because normalization will later unwrap
352 * it, but then that changes the key for the KeyError, which is not
353 * welcome. The check is inexact, as the unwrapping one is too.
354 */
355 if (PyTuple_Check(key) || key == Py_None) {
356 PyObject *tuple = MAKE_TUPLE1(tstate, key);
357
358 SET_CURRENT_EXCEPTION_TYPE0_VALUE1(tstate, PyExc_KeyError, tuple);
359 } else {
360 SET_CURRENT_EXCEPTION_TYPE0_VALUE0(tstate, PyExc_KeyError, key);
361 }
362#else
363 struct Nuitka_ExceptionPreservationItem exception_state = {Nuitka_CreateKeyError(tstate, key)};
364
365 RESTORE_ERROR_OCCURRED_STATE(tstate, &exception_state);
366#endif
367}
368
369// TODO: This gives a reference, where would often be one time immediate users
370// of the value, forcing temporary variable releases on the outside. We need
371// to add indication of how long a value is going to be used, so in case where
372// we have the knowledge, we can provide the reference or not. Maybe we can
373// also include temporary nature of the key and/or dict releases to be done
374// inside of such helper code, possibly in template generation, where also
375// the hashing check wouldn't be needed anymore.
376PyObject *DICT_GET_ITEM_WITH_ERROR(PyThreadState *tstate, PyObject *dict, PyObject *key) {
377 CHECK_OBJECT(dict);
378 assert(PyDict_CheckExact(dict));
379
380 CHECK_OBJECT(key);
381
382 Py_hash_t hash;
383
384// This variant is uncertain about the hashing.
385#if PYTHON_VERSION < 0x300
386 if (PyString_CheckExact(key)) {
387 hash = ((PyStringObject *)key)->ob_shash;
388
389 if (unlikely(hash == -1)) {
390 hash = HASH_VALUE_WITHOUT_ERROR(tstate, key);
391 }
392
393 if (unlikely(hash == -1)) {
394 return NULL;
395 }
396 } else {
397 hash = HASH_VALUE_WITH_ERROR(tstate, key);
398
399 if (unlikely(hash == -1)) {
400 return NULL;
401 }
402 }
403
404 PyDictObject *dict_object = (PyDictObject *)dict;
405 PyDictEntry *entry = (dict_object->ma_lookup)(dict_object, key, hash);
406
407 if (unlikely(entry == NULL || entry->me_value == NULL)) {
408 SET_CURRENT_EXCEPTION_KEY_ERROR(tstate, key);
409
410 return NULL;
411 }
412
413 CHECK_OBJECT(entry->me_value);
414 Py_INCREF(entry->me_value);
415 return entry->me_value;
416#else
417 if (!PyUnicode_CheckExact(key) || (hash = ((PyASCIIObject *)key)->hash) == -1) {
418 hash = HASH_VALUE_WITH_ERROR(tstate, key);
419 if (unlikely(hash == -1)) {
420 return NULL;
421 }
422 }
423
424 PyDictObject *dict_object = (PyDictObject *)dict;
425
426#if PYTHON_VERSION < 0x360
427 PyObject **value_addr;
428 PyDictKeyEntry *entry = dict_object->ma_keys->dk_lookup(dict_object, key, hash, &value_addr);
429
430 if (unlikely(entry == NULL || *value_addr == NULL)) {
431 if (unlikely(HAS_ERROR_OCCURRED(tstate))) {
432 return NULL;
433 }
434
435 SET_CURRENT_EXCEPTION_KEY_ERROR(tstate, key);
436
437 return NULL;
438 }
439#else
440#if PYTHON_VERSION < 0x370
441 PyObject **value_addr;
442 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &value_addr, NULL);
443#elif PYTHON_VERSION < 0x3b0
444 PyObject *result;
445 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &result);
446#elif defined(Py_GIL_DISABLED)
447 PyObject *result;
448 Py_ssize_t ix = Nuitka_Py_dict_lookup_threadsafe(dict_object, key, hash, &result);
449#else
450 PyObject **value_addr;
451 Py_ssize_t ix = Nuitka_PyDictLookup(dict_object, key, hash, &value_addr);
452#endif
453
454 if (unlikely(ix < 0)) {
455 if (unlikely(HAS_ERROR_OCCURRED(tstate))) {
456 return NULL;
457 }
458
459 SET_CURRENT_EXCEPTION_KEY_ERROR(tstate, key);
460
461 return NULL;
462 }
463#endif
464
465#if PYTHON_VERSION < 0x370 || (PYTHON_VERSION >= 0x3b0 && !defined(Py_GIL_DISABLED))
466 assert(value_addr != NULL);
467 PyObject *result = *value_addr;
468#endif
469
470 if (unlikely(result == NULL)) {
471 if (unlikely(HAS_ERROR_OCCURRED(tstate))) {
472 return NULL;
473 }
474
475 SET_CURRENT_EXCEPTION_KEY_ERROR(tstate, key);
476
477 return NULL;
478 }
479
480 CHECK_OBJECT(result);
481 Py_INCREF(result);
482 return result;
483#endif
484}
485
486PyObject *DICT_GET_ITEM_WITH_HASH_ERROR0(PyThreadState *tstate, PyObject *dict, PyObject *key) {
487 CHECK_OBJECT(dict);
488 assert(PyDict_CheckExact(dict));
489
490 CHECK_OBJECT(key);
491
492 Py_hash_t hash;
493
494// This variant is uncertain about the hashing.
495#if PYTHON_VERSION < 0x300
496 if (PyString_CheckExact(key)) {
497 hash = ((PyStringObject *)key)->ob_shash;
498
499 if (unlikely(hash == -1)) {
500 hash = HASH_VALUE_WITHOUT_ERROR(tstate, key);
501 }
502
503 if (unlikely(hash == -1)) {
504 return NULL;
505 }
506 } else {
507 hash = HASH_VALUE_WITH_ERROR(tstate, key);
508
509 if (unlikely(hash == -1)) {
510 return NULL;
511 }
512 }
513
514 PyDictObject *dict_object = (PyDictObject *)dict;
515 PyDictEntry *entry = (dict_object->ma_lookup)(dict_object, key, hash);
516
517 if (unlikely(entry == NULL || entry->me_value == NULL)) {
518 return NULL;
519 }
520
521 CHECK_OBJECT(entry->me_value);
522 return entry->me_value;
523#else
524 if (!PyUnicode_CheckExact(key) || (hash = ((PyASCIIObject *)key)->hash) == -1) {
525 hash = HASH_VALUE_WITH_ERROR(tstate, key);
526 if (unlikely(hash == -1)) {
527 return NULL;
528 }
529 }
530
531 PyDictObject *dict_object = (PyDictObject *)dict;
532
533#if PYTHON_VERSION < 0x360
534 PyObject **value_addr;
535 PyDictKeyEntry *entry = dict_object->ma_keys->dk_lookup(dict_object, key, hash, &value_addr);
536
537 if (unlikely(entry == NULL || *value_addr == NULL)) {
538 return NULL;
539 }
540#else
541#if PYTHON_VERSION < 0x370
542 PyObject **value_addr;
543 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &value_addr, NULL);
544#elif PYTHON_VERSION < 0x3b0
545 PyObject *result;
546 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &result);
547#elif defined(Py_GIL_DISABLED)
548 PyObject *result;
549 Py_ssize_t ix = Nuitka_Py_dict_lookup_threadsafe(dict_object, key, hash, &result);
550#else
551 PyObject **value_addr;
552 Py_ssize_t ix = Nuitka_PyDictLookup(dict_object, key, hash, &value_addr);
553#endif
554
555 if (unlikely(ix < 0)) {
556 return NULL;
557 }
558#endif
559
560#if PYTHON_VERSION < 0x370 || (PYTHON_VERSION >= 0x3b0 && !defined(Py_GIL_DISABLED))
561 assert(value_addr != NULL);
562 PyObject *result = *value_addr;
563#endif
564
565 if (unlikely(result == NULL)) {
566 return NULL;
567 }
568
569 CHECK_OBJECT(result);
570 return result;
571#endif
572}
573
574// TODO: Exact copy of DICT_GET_ITEM_WITH_HASH_ERROR0 with just a Py_INCREF added, we should
575// generate these and all other variants rather than manually maintaining them, so we can
576// also specialize by type and not just result needs.
577PyObject *DICT_GET_ITEM_WITH_HASH_ERROR1(PyThreadState *tstate, PyObject *dict, PyObject *key) {
578 CHECK_OBJECT(dict);
579 assert(PyDict_CheckExact(dict));
580
581 CHECK_OBJECT(key);
582
583 Py_hash_t hash;
584
585// This variant is uncertain about the hashing.
586#if PYTHON_VERSION < 0x300
587 if (PyString_CheckExact(key)) {
588 hash = ((PyStringObject *)key)->ob_shash;
589
590 if (unlikely(hash == -1)) {
591 hash = HASH_VALUE_WITHOUT_ERROR(tstate, key);
592 }
593
594 if (unlikely(hash == -1)) {
595 return NULL;
596 }
597 } else {
598 hash = HASH_VALUE_WITH_ERROR(tstate, key);
599
600 if (unlikely(hash == -1)) {
601 return NULL;
602 }
603 }
604
605 PyDictObject *dict_object = (PyDictObject *)dict;
606 PyDictEntry *entry = (dict_object->ma_lookup)(dict_object, key, hash);
607
608 if (unlikely(entry == NULL || entry->me_value == NULL)) {
609 return NULL;
610 }
611
612 CHECK_OBJECT(entry->me_value);
613 Py_INCREF(entry->me_value);
614 return entry->me_value;
615#else
616 if (!PyUnicode_CheckExact(key) || (hash = ((PyASCIIObject *)key)->hash) == -1) {
617 hash = HASH_VALUE_WITH_ERROR(tstate, key);
618 if (unlikely(hash == -1)) {
619 return NULL;
620 }
621 }
622
623 PyDictObject *dict_object = (PyDictObject *)dict;
624
625#if PYTHON_VERSION < 0x360
626 PyObject **value_addr;
627 PyDictKeyEntry *entry = dict_object->ma_keys->dk_lookup(dict_object, key, hash, &value_addr);
628
629 if (unlikely(entry == NULL || *value_addr == NULL)) {
630 return NULL;
631 }
632#else
633#if PYTHON_VERSION < 0x370
634 PyObject **value_addr;
635 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &value_addr, NULL);
636#elif PYTHON_VERSION < 0x3b0
637 PyObject *result;
638 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &result);
639#elif defined(Py_GIL_DISABLED)
640 PyObject *result;
641 Py_ssize_t ix = Nuitka_Py_dict_lookup_threadsafe(dict_object, key, hash, &result);
642#else
643 PyObject **value_addr;
644 Py_ssize_t ix = Nuitka_PyDictLookup(dict_object, key, hash, &value_addr);
645#endif
646
647 if (unlikely(ix < 0)) {
648 return NULL;
649 }
650#endif
651
652#if PYTHON_VERSION < 0x370 || (PYTHON_VERSION >= 0x3b0 && !defined(Py_GIL_DISABLED))
653 assert(value_addr != NULL);
654 PyObject *result = *value_addr;
655#endif
656
657 if (unlikely(result == NULL)) {
658 return NULL;
659 }
660
661 CHECK_OBJECT(result);
662 Py_INCREF(result);
663 return result;
664#endif
665}
666
667int DICT_HAS_ITEM(PyThreadState *tstate, PyObject *dict, PyObject *key) {
668 CHECK_OBJECT(dict);
669 assert(PyDict_Check(dict));
670
671 CHECK_OBJECT(key);
672
673 Py_hash_t hash;
674
675// This variant is uncertain about the hashing.
676#if PYTHON_VERSION < 0x300
677 if (PyString_CheckExact(key)) {
678 hash = ((PyStringObject *)key)->ob_shash;
679
680 if (unlikely(hash == -1)) {
681 hash = HASH_VALUE_WITHOUT_ERROR(tstate, key);
682 }
683
684 if (unlikely(hash == -1)) {
685 return -1;
686 }
687 } else {
688 hash = HASH_VALUE_WITH_ERROR(tstate, key);
689
690 if (unlikely(hash == -1)) {
691 return -1;
692 }
693 }
694
695 PyDictObject *dict_object = (PyDictObject *)dict;
696 PyDictEntry *entry = (dict_object->ma_lookup)(dict_object, key, hash);
697
698 if (unlikely(entry == NULL || entry->me_value == NULL)) {
699 return 0;
700 }
701
702 return 1;
703#else
704 if (!PyUnicode_CheckExact(key) || (hash = ((PyASCIIObject *)key)->hash) == -1) {
705 hash = HASH_VALUE_WITH_ERROR(tstate, key);
706 if (unlikely(hash == -1)) {
707 return -1;
708 }
709 }
710
711 PyDictObject *dict_object = (PyDictObject *)dict;
712
713#if PYTHON_VERSION < 0x360
714 PyObject **value_addr;
715 PyDictKeyEntry *entry = dict_object->ma_keys->dk_lookup(dict_object, key, hash, &value_addr);
716
717 if (unlikely(entry == NULL || *value_addr == NULL)) {
718 return 0;
719 }
720
721 return 1;
722#else
723#if PYTHON_VERSION < 0x370
724 PyObject **value_addr;
725 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &value_addr, NULL);
726#elif PYTHON_VERSION < 0x3b0
727 PyObject *result;
728 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &result);
729#elif defined(Py_GIL_DISABLED)
730 PyObject *result;
731 Py_ssize_t ix = Nuitka_Py_dict_lookup_threadsafe(dict_object, key, hash, &result);
732#else
733 PyObject **value_addr;
734 Py_ssize_t ix = Nuitka_PyDictLookup(dict_object, key, hash, &value_addr);
735#endif
736
737 if (unlikely(ix < 0)) {
738 if (unlikely(HAS_ERROR_OCCURRED(tstate))) {
739 return -1;
740 }
741
742 return 0;
743 }
744
745#if PYTHON_VERSION < 0x370 || (PYTHON_VERSION >= 0x3b0 && !defined(Py_GIL_DISABLED))
746 assert(value_addr != NULL);
747 PyObject *result = *value_addr;
748#endif
749
750 if (unlikely(result == NULL)) {
751 return 0;
752 }
753#endif
754 return 1;
755#endif
756}
757
758#if PYTHON_VERSION < 0x300
759PyObject *DICT_ITEMS(PyObject *dict) {
760 CHECK_OBJECT(dict);
761 assert(PyDict_Check(dict));
762
763 PyDictObject *mp = (PyDictObject *)dict;
764
765 PyObject *result;
766 Py_ssize_t size;
767
768 /* Preallocate the list of tuples, to avoid allocations during
769 * the loop over the items, which could trigger GC, which
770 * could resize the dict. :-(
771 */
772retry:
773 size = mp->ma_used;
774 result = MAKE_LIST_EMPTY(tstate, size);
775 CHECK_OBJECT(result);
776
777 for (Py_ssize_t i = 0; i < size; i++) {
778 // Later populated.
779 PyObject *item = MAKE_TUPLE_EMPTY(tstate, 2);
780 CHECK_OBJECT(item);
781
782 PyList_SET_ITEM(result, i, item);
783 }
784
785 if (unlikely(size != mp->ma_used)) {
786 // Garbage collection can compactify dictionaries.
787 Py_DECREF(result);
788 goto retry;
789 }
790
791 // Nothing must cause any functions to be called
792 PyDictEntry *ep = mp->ma_table;
793 Py_ssize_t mask = mp->ma_mask;
794
795 for (Py_ssize_t i = 0, j = 0; i <= mask; i++) {
796 PyObject *value = ep[i].me_value;
797 if (value != NULL) {
798 PyObject *key = ep[i].me_key;
799 PyObject *item = PyList_GET_ITEM(result, j);
800 PyTuple_SET_ITEM0(item, 0, key);
801 PyTuple_SET_ITEM0(item, 1, value);
802
803 j++;
804 }
805 }
806
807 assert(PyList_GET_SIZE(result) == size);
808
809 return result;
810}
811
812#if PYTHON_VERSION < 0x300
813PyObject *DICT_KEYS(PyObject *dict) {
814 CHECK_OBJECT(dict);
815 assert(PyDict_Check(dict));
816
817 PyDictObject *mp = (PyDictObject *)dict;
818
819 PyObject *result;
820 Py_ssize_t size;
821
822 /* Preallocate the list of tuples, to avoid allocations during
823 * the loop over the items, which could trigger GC, which
824 * could resize the dict. :-(
825 */
826retry:
827 size = mp->ma_used;
828 result = MAKE_LIST_EMPTY(tstate, size);
829 CHECK_OBJECT(result);
830
831 if (unlikely(size != mp->ma_used)) {
832 // Garbage collection can compactify dictionaries.
833 Py_DECREF(result);
834 goto retry;
835 }
836
837 // Nothing must cause any functions to be called
838 PyDictEntry *ep = mp->ma_table;
839 Py_ssize_t mask = mp->ma_mask;
840
841 for (Py_ssize_t i = 0, j = 0; i <= mask; i++) {
842 PyObject *value = ep[i].me_value;
843 if (value != NULL) {
844 PyObject *key = ep[i].me_key;
845 PyList_SET_ITEM0(result, j, key);
846
847 j++;
848 }
849 }
850
851 assert(PyList_GET_SIZE(result) == size);
852
853 return result;
854}
855#endif
856
857#if PYTHON_VERSION < 0x300
858PyObject *DICT_VALUES(PyObject *dict) {
859 CHECK_OBJECT(dict);
860 assert(PyDict_Check(dict));
861
862 PyDictObject *mp = (PyDictObject *)dict;
863
864 PyObject *result;
865 Py_ssize_t size;
866
867 /* Preallocate the list of tuples, to avoid allocations during
868 * the loop over the items, which could trigger GC, which
869 * could resize the dict. :-(
870 */
871retry:
872 size = mp->ma_used;
873 result = MAKE_LIST_EMPTY(tstate, size);
874 CHECK_OBJECT(result);
875
876 if (unlikely(size != mp->ma_used)) {
877 // Garbage collection can compactify dictionaries.
878 Py_DECREF(result);
879 goto retry;
880 }
881
882 // Nothing must cause any functions to be called
883 PyDictEntry *ep = mp->ma_table;
884 Py_ssize_t mask = mp->ma_mask;
885
886 for (Py_ssize_t i = 0, j = 0; i <= mask; i++) {
887 PyObject *value = ep[i].me_value;
888 if (value != NULL) {
889 PyList_SET_ITEM0(result, j, value);
890
891 j++;
892 }
893 }
894
895 assert(PyList_GET_SIZE(result) == size);
896
897 return result;
898}
899#endif
900
901#endif
902
903#if PYTHON_VERSION < 0x300
904typedef struct {
905 PyObject_HEAD PyDictObject *di_dict;
906 Py_ssize_t di_used;
907 Py_ssize_t di_pos;
908 PyObject *di_result;
909 Py_ssize_t len;
910} dictiterobject;
911#endif
912
913#if PYTHON_VERSION >= 0x300 && PYTHON_VERSION < 0x350
914typedef struct {
915 PyObject_HEAD PyDictObject *dv_dict;
916} _PyDictViewObject;
917
918#endif
919
920// Generic helper for various dictionary iterations, to be inlined.
921static inline PyObject *_MAKE_DICT_ITERATOR(PyThreadState *tstate, PyDictObject *dict, PyTypeObject *type,
922 bool is_iteritems) {
923 CHECK_OBJECT((PyObject *)dict);
924 assert(PyDict_CheckExact((PyObject *)dict));
925
926#if PYTHON_VERSION < 0x300
927 dictiterobject *di = (dictiterobject *)Nuitka_GC_New(type);
928 CHECK_OBJECT(di);
929 Py_INCREF(dict);
930 di->di_dict = dict;
931 di->di_used = dict->ma_used;
932 di->di_pos = 0;
933 di->len = dict->ma_used;
934 if (is_iteritems) {
935 // TODO: Have this as faster variants, we do these sometimes.
936 di->di_result = MAKE_TUPLE2(tstate, Py_None, Py_None);
937 CHECK_OBJECT(di->di_result);
938 } else {
939 di->di_result = NULL;
940 }
941
942 Nuitka_GC_Track(di);
943 return (PyObject *)di;
944#else
945 _PyDictViewObject *dv = (_PyDictViewObject *)Nuitka_GC_New(type);
946 CHECK_OBJECT(dv);
947
948 Py_INCREF(dict);
949 dv->dv_dict = dict;
950
951 Nuitka_GC_Track(dv);
952 return (PyObject *)dv;
953#endif
954}
955
956PyObject *DICT_ITERITEMS(PyThreadState *tstate, PyObject *dict) {
957#if PYTHON_VERSION < 0x270
958 static PyTypeObject *dictiteritems_type = NULL;
959
960 if (unlikely(dictiteritems_type == NULL)) {
961 dictiteritems_type =
962 Py_TYPE(CALL_FUNCTION_NO_ARGS(tstate, PyObject_GetAttrString(const_dict_empty, "iteritems")));
963 }
964
965 return _MAKE_DICT_ITERATOR(tstate, (PyDictObject *)dict, dictiteritems_type, true);
966#elif PYTHON_VERSION < 0x300
967 return _MAKE_DICT_ITERATOR(tstate, (PyDictObject *)dict, &PyDictIterItem_Type, true);
968#else
969 return _MAKE_DICT_ITERATOR(tstate, (PyDictObject *)dict, &PyDictItems_Type, true);
970#endif
971}
972
973PyObject *DICT_ITERKEYS(PyThreadState *tstate, PyObject *dict) {
974#if PYTHON_VERSION < 0x270
975 static PyTypeObject *dictiterkeys_type = NULL;
976
977 if (unlikely(dictiterkeys_type == NULL)) {
978 dictiterkeys_type =
979 Py_TYPE(CALL_FUNCTION_NO_ARGS(tstate, PyObject_GetAttrString(const_dict_empty, "iterkeys")));
980 }
981
982 return _MAKE_DICT_ITERATOR(tstate, (PyDictObject *)dict, dictiterkeys_type, false);
983#elif PYTHON_VERSION < 0x300
984 return _MAKE_DICT_ITERATOR(tstate, (PyDictObject *)dict, &PyDictIterKey_Type, false);
985#else
986 return _MAKE_DICT_ITERATOR(tstate, (PyDictObject *)dict, &PyDictKeys_Type, false);
987#endif
988}
989
990PyObject *DICT_ITERVALUES(PyThreadState *tstate, PyObject *dict) {
991#if PYTHON_VERSION < 0x270
992 static PyTypeObject *dictitervalues_type = NULL;
993
994 if (unlikely(dictitervalues_type == NULL)) {
995 dictitervalues_type =
996 Py_TYPE(CALL_FUNCTION_NO_ARGS(tstate, PyObject_GetAttrString(const_dict_empty, "itervalues")));
997 }
998
999 return _MAKE_DICT_ITERATOR(tstate, (PyDictObject *)dict, dictitervalues_type, false);
1000#elif PYTHON_VERSION < 0x300
1001 return _MAKE_DICT_ITERATOR(tstate, (PyDictObject *)dict, &PyDictIterValue_Type, false);
1002#else
1003 return _MAKE_DICT_ITERATOR(tstate, (PyDictObject *)dict, &PyDictValues_Type, false);
1004#endif
1005}
1006
1007typedef struct {
1008 PyObject_HEAD PyDictObject *dv_dict;
1009} dictviewobject;
1010
1011static PyObject *_MAKE_DICT_VIEW(PyDictObject *dict, PyTypeObject *type) {
1012 CHECK_OBJECT((PyObject *)dict);
1013 assert(PyDict_CheckExact((PyObject *)dict));
1014
1015 dictviewobject *dv = (dictviewobject *)Nuitka_GC_New(type);
1016
1017 CHECK_OBJECT(dv);
1018 Py_INCREF(dict);
1019 dv->dv_dict = (PyDictObject *)dict;
1020 Nuitka_GC_Track(dv);
1021 return (PyObject *)dv;
1022}
1023
1024PyObject *DICT_VIEWKEYS(PyObject *dict) {
1025#if PYTHON_VERSION < 0x270
1026 static PyTypeObject *dictkeysview_type = NULL;
1027
1028 if (unlikely(dictkeysview_type)) {
1029 dictkeysview_type = Py_TYPE(PyObject_GetIter(PyObject_GetAttrString(const_dict_empty, "viewkeys")));
1030 }
1031
1032 return _MAKE_DICT_VIEW((PyDictObject *)dict, dictkeysview_type);
1033#else
1034 return _MAKE_DICT_VIEW((PyDictObject *)dict, &PyDictKeys_Type);
1035#endif
1036}
1037
1038PyObject *DICT_VIEWVALUES(PyObject *dict) {
1039#if PYTHON_VERSION < 0x270
1040 static PyTypeObject *dictvaluesview_type = NULL;
1041
1042 if (unlikely(dictvaluesview_type)) {
1043 dictvaluesview_type = Py_TYPE(PyObject_GetIter(PyObject_GetAttrString(const_dict_empty, "viewvalues")));
1044 }
1045
1046 return _MAKE_DICT_VIEW((PyDictObject *)dict, dictvaluesview_type);
1047#else
1048 return _MAKE_DICT_VIEW((PyDictObject *)dict, &PyDictValues_Type);
1049#endif
1050}
1051
1052PyObject *DICT_VIEWITEMS(PyObject *dict) {
1053#if PYTHON_VERSION < 0x270
1054 static PyTypeObject *dictvaluesview_type = NULL;
1055
1056 if (unlikely(dictvaluesview_type)) {
1057 dictvaluesview_type = Py_TYPE(PyObject_GetIter(PyObject_GetAttrString(const_dict_empty, "viewitems")));
1058 }
1059
1060 return _MAKE_DICT_VIEW((PyDictObject *)dict, dictvaluesview_type);
1061#else
1062 return _MAKE_DICT_VIEW((PyDictObject *)dict, &PyDictItems_Type);
1063#endif
1064}
1065
1066#if PYTHON_VERSION >= 0x3e0
1067static PyDictObject *_Nuitka_AllocatePyDictObjectFresh(void) {
1068 size_t pre_size = _PyType_PreHeaderSize(&PyDict_Type);
1069 size_t size = _PyObject_SIZE(&PyDict_Type);
1070
1071 char *alloc = (char *)NuitkaObject_Malloc(size + pre_size);
1072 assert(alloc != NULL);
1073
1074 ((PyObject **)alloc)[0] = NULL;
1075 ((PyObject **)alloc)[1] = NULL;
1076
1077 PyObject *obj = (PyObject *)(alloc + pre_size);
1078
1079 Nuitka_PyObject_GC_Link(obj);
1080 _PyObject_Init(obj, &PyDict_Type);
1081
1082 return (PyDictObject *)obj;
1083}
1084#endif
1085
1086#if PYTHON_VERSION >= 0x300 && (NUITKA_DICT_HAS_FREELIST || !_NUITKA_EXPERIMENTAL_DISABLE_DICT_OPT)
1087static PyDictObject *_Nuitka_AllocatePyDictObject(PyThreadState *tstate) {
1088 PyDictObject *result_mp;
1089
1090#if NUITKA_DICT_HAS_FREELIST
1091#if PYTHON_VERSION < 0x3d0
1092 // This is the CPython name, spell-checker: ignore numfree
1093 PyDictObject **items = tstate->interp->dict_state.free_list;
1094 int *numfree = &tstate->interp->dict_state.numfree;
1095#elif PYTHON_VERSION < 0x3e0
1096 struct _Py_object_freelists *freelists = _Nuitka_object_freelists_GET(tstate);
1097 struct _Py_dict_freelist *state = &freelists->dicts;
1098 PyDictObject **items = state->items;
1099 int *numfree = &state->numfree;
1100#endif
1101
1102#if PYTHON_VERSION >= 0x3e0
1103 struct _Py_freelists *freelists = Nuitka_Py_freelists_GET(tstate);
1104
1105 result_mp = (PyDictObject *)Nuitka_PyFreeList_Pop(&freelists->dicts);
1106
1107 if (result_mp != NULL) {
1108 Nuitka_Py_NewReference((PyObject *)result_mp);
1109 } else {
1110 result_mp = _Nuitka_AllocatePyDictObjectFresh();
1111 }
1112#else
1113 if (*numfree) {
1114 (*numfree) -= 1;
1115 result_mp = items[*numfree];
1116
1117 Nuitka_Py_NewReference((PyObject *)result_mp);
1118 } else {
1119#if PYTHON_VERSION >= 0x3e0
1120 result_mp = _Nuitka_AllocatePyDictObjectFresh();
1121#else
1122 result_mp = (PyDictObject *)Nuitka_GC_New(&PyDict_Type);
1123#endif
1124 }
1125#endif
1126#else
1127#if PYTHON_VERSION >= 0x3e0
1128 result_mp = _Nuitka_AllocatePyDictObjectFresh();
1129#else
1130 result_mp = (PyDictObject *)Nuitka_GC_New(&PyDict_Type);
1131#endif
1132#endif
1133#if PYTHON_VERSION >= 0x3e0
1134 result_mp->_ma_watcher_tag = 0;
1135#endif
1136
1137 CHECK_OBJECT(result_mp);
1138 assert(PyDict_CheckExact((PyObject *)result_mp));
1139 return result_mp;
1140}
1141#endif
1142
1143#if PYTHON_VERSION >= 0x360
1144static PyDictKeysObject *_Nuitka_AllocatePyDictKeysObject(PyThreadState *tstate, Py_ssize_t keys_size) {
1145 // CPython names, spell-checker: ignore numfree,dictkeys
1146 PyDictKeysObject *dk;
1147
1148// TODO: Cannot always use cached objects. Need to also consider
1149// "log2_size == PyDict_LOG_MINSIZE && unicode" as a criterion,
1150// seems it can only be used for the smallest keys type.
1151#if NUITKA_DICT_HAS_FREELIST && 0
1152#if PYTHON_VERSION < 0x3d0
1153 PyDictKeysObject **items = tstate->interp->dict_state.keys_free_list;
1154 int *numfree = &tstate->interp->dict_state.keys_numfree;
1155#else
1156 struct _Py_object_freelists *freelists = _Nuitka_object_freelists_GET(tstate);
1157 struct _Py_dictkeys_freelist *state = &freelists->dictkeys;
1158 PyDictKeysObject **items = state->items;
1159 int *numfree = &state->numfree;
1160#endif
1161
1162 if (*numfree) {
1163 (*numfree) -= 1;
1164 dk = items[*numfree];
1165 } else
1166#endif
1167 {
1168#if PYTHON_VERSION < 0x3d0
1169 dk = (PyDictKeysObject *)NuitkaObject_Malloc(keys_size);
1170#else
1171 dk = (PyDictKeysObject *)NuitkaMem_Malloc(keys_size);
1172#endif
1173 }
1174
1175 return dk;
1176}
1177#endif
1178
1179#if PYTHON_VERSION >= 0x360 && !_NUITKA_EXPERIMENTAL_DISABLE_DICT_OPT
1180
1181// Usable fraction of keys.
1182#define DK_USABLE_FRACTION(n) (((n) << 1) / 3)
1183
1184static Py_ssize_t _Nuitka_Py_PyDict_KeysSize(PyDictKeysObject *keys) {
1185#if PYTHON_VERSION < 0x360
1186 return sizeof(PyDictKeysObject) + (DK_SIZE(keys) - 1) * sizeof(PyDictKeyEntry);
1187#elif PYTHON_VERSION < 0x370
1188 return (sizeof(PyDictKeysObject) - Py_MEMBER_SIZE(PyDictKeysObject, dk_indices) + DK_IXSIZE(keys) * DK_SIZE(keys) +
1189 DK_USABLE_FRACTION(DK_SIZE(keys)) * sizeof(PyDictKeyEntry));
1190#elif PYTHON_VERSION < 0x3b0
1191 return (sizeof(PyDictKeysObject) + DK_IXSIZE(keys) * DK_SIZE(keys) +
1192 DK_USABLE_FRACTION(DK_SIZE(keys)) * sizeof(PyDictKeyEntry));
1193#else
1194 size_t entry_size = keys->dk_kind == DICT_KEYS_GENERAL ? sizeof(PyDictKeyEntry) : sizeof(PyDictUnicodeEntry);
1195 return (sizeof(PyDictKeysObject) + ((size_t)1 << keys->dk_log2_index_bytes) +
1196 DK_USABLE_FRACTION(DK_SIZE(keys)) * entry_size);
1197#endif
1198}
1199#endif
1200
1201#if PYTHON_VERSION < 0x3b0
1202typedef PyObject *PyDictValues;
1203#endif
1204
1205#if PYTHON_VERSION < 0x360
1206#define DK_ENTRIES_SIZE(keys) (keys->dk_size)
1207#elif PYTHON_VERSION < 0x3b0
1208#define DK_ENTRIES_SIZE(keys) DK_USABLE_FRACTION(DK_SIZE(keys))
1209#else
1210#define DK_ENTRIES_SIZE(keys) (keys->dk_nentries)
1211#endif
1212
1213// More than 2/3 of the keys are used, i.e. no space is wasted.
1214#if PYTHON_VERSION < 0x360
1215#define IS_COMPACT(dict_mp) (dict_mp->ma_used >= (dict_mp->ma_keys->dk_size * 2) / 3)
1216#else
1217#define IS_COMPACT(dict_mp) (dict_mp->ma_used >= (dict_mp->ma_keys->dk_nentries * 2) / 3)
1218#endif
1219
1220static inline PyDictValues *_Nuitka_PyDict_new_values(Py_ssize_t size) {
1221#if PYTHON_VERSION < 0x3b0
1222 Py_ssize_t values_size = sizeof(PyObject *) * size;
1223
1224 return (PyDictValues *)NuitkaMem_Malloc(values_size);
1225#elif PYTHON_VERSION < 0x3d0
1226 Py_ssize_t values_size = sizeof(PyObject *) * size;
1227
1228 // With Python3.11-3.12 a prefix is allocated too.
1229 size_t prefix_size = _Py_SIZE_ROUND_UP(size + 2, sizeof(PyObject *));
1230 size_t n = prefix_size + values_size;
1231 uint8_t *mem = (uint8_t *)NuitkaMem_Malloc(n);
1232 assert(mem != NULL);
1233
1234 assert(prefix_size % sizeof(PyObject *) == 0);
1235 mem[prefix_size - 1] = (uint8_t)prefix_size;
1236
1237 return (PyDictValues *)(mem + prefix_size);
1238#else
1239 assert(size >= 1);
1240 size_t suffix_size = _Py_SIZE_ROUND_UP(size, sizeof(PyObject *));
1241 assert(suffix_size < 128);
1242 assert(suffix_size % sizeof(PyObject *) == 0);
1243 size_t n = (size + 1) * sizeof(PyObject *) + suffix_size;
1244 PyDictValues *result = (PyDictValues *)NuitkaMem_Malloc(n);
1245
1246 result->embedded = 0;
1247 result->size = 0;
1248 assert(size < 256);
1249 result->capacity = (uint8_t)size;
1250 return result;
1251#endif
1252}
1253
1254#if PYTHON_VERSION >= 0x3d0
1255
1256static PyDictValues *_Nuitka_PyDict_copy_values(PyDictValues *values) {
1257 PyDictValues *new_values = _Nuitka_PyDict_new_values(values->capacity);
1258 if (unlikely(new_values == NULL)) {
1259 return NULL;
1260 }
1261
1262 new_values->size = values->size;
1263
1264 uint8_t *values_order = get_insertion_order_array(values);
1265 uint8_t *new_values_order = get_insertion_order_array(new_values);
1266
1267 memcpy(new_values_order, values_order, values->capacity);
1268
1269 for (int i = 0; i < values->capacity; i++) {
1270 new_values->values[i] = values->values[i];
1271 }
1272 assert(new_values->embedded == 0);
1273 return new_values;
1274}
1275#endif
1276
1277#include "HelpersDictionariesGenerated.c"
1278
1279void DICT_CLEAR(PyObject *dict) {
1280 CHECK_OBJECT(dict);
1281 assert(PyDict_CheckExact(dict));
1282
1283 // TODO: Could inline this for enhanced optimization, but it does
1284 // some pretty sophisticated memory handling.
1285 PyDict_Clear(dict);
1286}
1287
1288#if PYTHON_VERSION >= 0x3b0
1289static inline int Nuitka_py_get_index_from_order(PyDictObject *mp, Py_ssize_t i) {
1290 assert(mp->ma_used <= SHARED_KEYS_MAX_SIZE);
1291#if PYTHON_VERSION < 0x3d0
1292 assert(i < (((char *)mp->ma_values)[-2]));
1293 return ((char *)mp->ma_values)[-3 - i];
1294#else
1295 assert(i < mp->ma_values->size);
1296 uint8_t *array = get_insertion_order_array(mp->ma_values);
1297 return array[i];
1298#endif
1299}
1300#endif
1301
1302#if PYTHON_VERSION >= 0x3b0
1303
1304static inline Py_ssize_t Nuitka_Py_dictkeys_get_index(const PyDictKeysObject *keys, Py_ssize_t i) {
1305 int log2size = DK_LOG_SIZE(keys);
1306 Py_ssize_t ix;
1307
1308 if (log2size < 8) {
1309 ix = LOAD_INDEX(keys, 8, i);
1310
1311 } else if (log2size < 16) {
1312 ix = LOAD_INDEX(keys, 16, i);
1313 }
1314#if SIZEOF_VOID_P > 4
1315 else if (log2size >= 32) {
1316 ix = LOAD_INDEX(keys, 64, i);
1317 }
1318#endif
1319 else {
1320 ix = LOAD_INDEX(keys, 32, i);
1321 }
1322
1323 assert(ix >= DKIX_DUMMY);
1324 return ix;
1325}
1326
1327// From CPython
1328#define PERTURB_SHIFT 5
1329
1330// 3.13+
1331#if PYTHON_VERSION >= 0x3d0
1332
1333static inline Py_ALWAYS_INLINE Py_ssize_t Nuitka_Py_dictkeys_do_lookup(
1334 PyDictObject *mp, PyDictKeysObject *dk, PyObject *key, Py_hash_t hash,
1335 int (*check_lookup)(PyDictObject *, PyDictKeysObject *, void *, Py_ssize_t ix, PyObject *key, Py_hash_t)) {
1336 void *ep0 = _DK_ENTRIES(dk);
1337 size_t mask = DK_MASK(dk);
1338 size_t perturb = hash;
1339 size_t i = (size_t)hash & mask;
1340 Py_ssize_t ix;
1341 for (;;) {
1342 ix = Nuitka_Py_dictkeys_get_index(dk, i);
1343 if (ix >= 0) {
1344 int cmp = check_lookup(mp, dk, ep0, ix, key, hash);
1345 if (cmp < 0) {
1346 return cmp;
1347 } else if (cmp) {
1348 return ix;
1349 }
1350 } else if (ix == DKIX_EMPTY) {
1351 return DKIX_EMPTY;
1352 }
1353 perturb >>= PERTURB_SHIFT;
1354 i = mask & (i * 5 + perturb + 1);
1355
1356 // Manual loop unrolling
1357 ix = Nuitka_Py_dictkeys_get_index(dk, i);
1358 if (ix >= 0) {
1359 int cmp = check_lookup(mp, dk, ep0, ix, key, hash);
1360 if (cmp < 0) {
1361 return cmp;
1362 } else if (cmp) {
1363 return ix;
1364 }
1365 } else if (ix == DKIX_EMPTY) {
1366 return DKIX_EMPTY;
1367 }
1368 perturb >>= PERTURB_SHIFT;
1369 i = mask & (i * 5 + perturb + 1);
1370 }
1371 NUITKA_CANNOT_GET_HERE("Nuitka_Py_dictkeys_do_lookup failed");
1372}
1373
1374static inline int Nuitka_Py_dictkeys_compare_unicode_generic(PyDictObject *mp, PyDictKeysObject *dk, void *ep0,
1375 Py_ssize_t ix, PyObject *key, Py_hash_t hash) {
1376 PyDictUnicodeEntry *ep = &((PyDictUnicodeEntry *)ep0)[ix];
1377 assert(ep->me_key != NULL);
1378 assert(PyUnicode_CheckExact(ep->me_key));
1379 assert(!PyUnicode_CheckExact(key));
1380
1381 if (Nuitka_Py_unicode_get_hash(ep->me_key) == hash) {
1382 PyObject *startkey = ep->me_key;
1383 Py_INCREF(startkey);
1384 int cmp = RICH_COMPARE_EQ_NBOOL_OBJECT_OBJECT(startkey, key);
1385 Py_DECREF(startkey);
1386 if (cmp < 0) {
1387 return DKIX_ERROR;
1388 }
1389 if (dk == mp->ma_keys && ep->me_key == startkey) {
1390 return cmp;
1391 } else {
1392 /* The dict was mutated, restart */
1393 return DKIX_KEY_CHANGED;
1394 }
1395 }
1396 return 0;
1397}
1398
1399static Py_ssize_t Nuitka_Py_unicodekeys_lookup_generic(PyDictObject *mp, PyDictKeysObject *dk, PyObject *key,
1400 Py_hash_t hash) {
1401 return Nuitka_Py_dictkeys_do_lookup(mp, dk, key, hash, Nuitka_Py_dictkeys_compare_unicode_generic);
1402}
1403
1404static inline int Nuitka_Py_dictkeys_compare_generic(PyDictObject *mp, PyDictKeysObject *dk, void *ep0, Py_ssize_t ix,
1405 PyObject *key, Py_hash_t hash) {
1406 PyDictKeyEntry *ep = &((PyDictKeyEntry *)ep0)[ix];
1407 assert(ep->me_key != NULL);
1408 if (ep->me_key == key) {
1409 return 1;
1410 }
1411 if (ep->me_hash == hash) {
1412 PyObject *startkey = ep->me_key;
1413 Py_INCREF(startkey);
1414 int cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
1415 Py_DECREF(startkey);
1416 if (cmp < 0) {
1417 return DKIX_ERROR;
1418 }
1419 if (dk == mp->ma_keys && ep->me_key == startkey) {
1420 return cmp;
1421 } else {
1422 /* The dict was mutated, restart */
1423 return DKIX_KEY_CHANGED;
1424 }
1425 }
1426 return 0;
1427}
1428
1429// Search non-Unicode key from Unicode table
1430static Py_ssize_t Nuitka_Py_dictkeys_generic_lookup(PyDictObject *mp, PyDictKeysObject *dk, PyObject *key,
1431 Py_hash_t hash) {
1432 return Nuitka_Py_dictkeys_do_lookup(mp, dk, key, hash, Nuitka_Py_dictkeys_compare_generic);
1433}
1434
1435static inline int Nuitka_Py_dictkeys_compare_unicode_unicode(PyDictObject *mp, PyDictKeysObject *dk, void *ep0,
1436 Py_ssize_t ix, PyObject *key, Py_hash_t hash) {
1437 PyDictUnicodeEntry *ep = &((PyDictUnicodeEntry *)ep0)[ix];
1438 PyObject *ep_key = FT_ATOMIC_LOAD_PTR_RELAXED(ep->me_key);
1439 assert(ep_key != NULL);
1440 assert(PyUnicode_CheckExact(ep_key));
1441 if (ep_key == key ||
1442 (Nuitka_Py_unicode_get_hash(ep_key) == hash && RICH_COMPARE_EQ_CBOOL_UNICODE_UNICODE(ep_key, key))) {
1443 return 1;
1444 }
1445 return 0;
1446}
1447
1448Py_ssize_t _Py_HOT_FUNCTION Nuitka_Py_unicodekeys_lookup_unicode(PyDictKeysObject *dk, PyObject *key, Py_hash_t hash) {
1449 return Nuitka_Py_dictkeys_do_lookup(NULL, dk, key, hash, Nuitka_Py_dictkeys_compare_unicode_unicode);
1450}
1451
1452#ifdef Py_GIL_DISABLED
1453
1454static inline Py_ALWAYS_INLINE int
1455Nuitka_Py_dictkeys_compare_unicode_generic_threadsafe(PyDictObject *mp, PyDictKeysObject *dk, void *ep0, Py_ssize_t ix,
1456 PyObject *key, Py_hash_t hash) {
1457 PyDictUnicodeEntry *ep = &((PyDictUnicodeEntry *)ep0)[ix];
1458 PyObject *startkey = _Py_atomic_load_ptr_relaxed(&ep->me_key);
1459 assert(startkey == NULL || PyUnicode_CheckExact(ep->me_key));
1460 assert(!PyUnicode_CheckExact(key));
1461
1462 if (startkey != NULL) {
1463 if (!_Py_TryIncrefCompare(&ep->me_key, startkey)) {
1464 return DKIX_KEY_CHANGED;
1465 }
1466
1467 if (Nuitka_Py_unicode_get_hash(startkey) == hash) {
1468 int cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
1469 Py_DECREF(startkey);
1470 if (cmp < 0) {
1471 return DKIX_ERROR;
1472 }
1473 if (dk == _Py_atomic_load_ptr_relaxed(&mp->ma_keys) &&
1474 startkey == _Py_atomic_load_ptr_relaxed(&ep->me_key)) {
1475 return cmp;
1476 } else {
1477 /* The dict was mutated, restart */
1478 return DKIX_KEY_CHANGED;
1479 }
1480 } else {
1481 Py_DECREF(startkey);
1482 }
1483 }
1484 return 0;
1485}
1486
1487// Search non-Unicode key from Unicode table
1488static Py_ssize_t Nuitka_Py_unicodekeys_lookup_generic_threadsafe(PyDictObject *mp, PyDictKeysObject *dk, PyObject *key,
1489 Py_hash_t hash) {
1490 return Nuitka_Py_dictkeys_do_lookup(mp, dk, key, hash, Nuitka_Py_dictkeys_compare_unicode_generic_threadsafe);
1491}
1492
1493static inline Py_ALWAYS_INLINE int
1494Nuitka_Py_dictkeys_compare_unicode_unicode_threadsafe(PyDictObject *mp, PyDictKeysObject *dk, void *ep0, Py_ssize_t ix,
1495 PyObject *key, Py_hash_t hash) {
1496 PyDictUnicodeEntry *ep = &((PyDictUnicodeEntry *)ep0)[ix];
1497 PyObject *startkey = _Py_atomic_load_ptr_relaxed(&ep->me_key);
1498 assert(startkey == NULL || PyUnicode_CheckExact(startkey));
1499 if (startkey == key) {
1500 return 1;
1501 }
1502 if (startkey != NULL) {
1503 if (_Py_IsImmortal(startkey)) {
1504 return Nuitka_Py_unicode_get_hash(startkey) == hash && RICH_COMPARE_EQ_CBOOL_UNICODE_UNICODE(startkey, key);
1505 } else {
1506 if (!_Py_TryIncrefCompare(&ep->me_key, startkey)) {
1507 return DKIX_KEY_CHANGED;
1508 }
1509 if (Nuitka_Py_unicode_get_hash(startkey) == hash && RICH_COMPARE_EQ_CBOOL_UNICODE_UNICODE(startkey, key)) {
1510 Py_DECREF(startkey);
1511 return 1;
1512 }
1513 Py_DECREF(startkey);
1514 }
1515 }
1516 return 0;
1517}
1518
1519static Py_ssize_t _Py_HOT_FUNCTION Nuitka_Py_unicodekeys_lookup_unicode_threadsafe(PyDictKeysObject *dk, PyObject *key,
1520 Py_hash_t hash) {
1521 return Nuitka_Py_dictkeys_do_lookup(NULL, dk, key, hash, Nuitka_Py_dictkeys_compare_unicode_unicode_threadsafe);
1522}
1523
1524static inline Py_ALWAYS_INLINE int Nuitka_Py_dictkeys_compare_generic_threadsafe(PyDictObject *mp, PyDictKeysObject *dk,
1525 void *ep0, Py_ssize_t ix,
1526 PyObject *key, Py_hash_t hash) {
1527 PyDictKeyEntry *ep = &((PyDictKeyEntry *)ep0)[ix];
1528 PyObject *startkey = _Py_atomic_load_ptr_relaxed(&ep->me_key);
1529 if (startkey == key) {
1530 return 1;
1531 }
1532 Py_ssize_t ep_hash = _Py_atomic_load_ssize_relaxed(&ep->me_hash);
1533 if (ep_hash == hash) {
1534 if (startkey == NULL || !_Py_TryIncrefCompare(&ep->me_key, startkey)) {
1535 return DKIX_KEY_CHANGED;
1536 }
1537 int cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
1538 Py_DECREF(startkey);
1539 if (cmp < 0) {
1540 return DKIX_ERROR;
1541 }
1542 if (dk == _Py_atomic_load_ptr_relaxed(&mp->ma_keys) && startkey == _Py_atomic_load_ptr_relaxed(&ep->me_key)) {
1543 return cmp;
1544 } else {
1545 /* The dict was mutated, restart */
1546 return DKIX_KEY_CHANGED;
1547 }
1548 }
1549 return 0;
1550}
1551
1552static Py_ssize_t Nuitka_Py_dictkeys_generic_lookup_threadsafe(PyDictObject *mp, PyDictKeysObject *dk, PyObject *key,
1553 Py_hash_t hash) {
1554 return Nuitka_Py_dictkeys_do_lookup(mp, dk, key, hash, Nuitka_Py_dictkeys_compare_generic_threadsafe);
1555}
1556
1557static inline void Nuitka_Py_dict_ensure_shared_on_read(PyDictObject *mp) {
1558 if (!_Py_IsOwnedByCurrentThread((PyObject *)mp) && !IS_DICT_SHARED(mp)) {
1559 // The first time we access a dict from a non-owning thread we mark it
1560 // as shared. This ensures that a concurrent resize operation will
1561 // delay freeing the old keys or values using QSBR, which is necessary
1562 // to safely allow concurrent reads without locking...
1563 Py_BEGIN_CRITICAL_SECTION(mp);
1564 if (!IS_DICT_SHARED(mp)) {
1565 SET_DICT_SHARED(mp);
1566 }
1567 Py_END_CRITICAL_SECTION();
1568 }
1569}
1570
1571Py_ssize_t Nuitka_Py_dict_lookup_threadsafe(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject **value_addr) {
1572 PyDictKeysObject *dk;
1573 DictKeysKind kind;
1574 Py_ssize_t ix;
1575 PyObject *value;
1576
1577 Nuitka_Py_dict_ensure_shared_on_read(mp);
1578
1579 dk = _Py_atomic_load_ptr(&mp->ma_keys);
1580 kind = dk->dk_kind;
1581
1582 if (kind != DICT_KEYS_GENERAL) {
1583 if (PyUnicode_CheckExact(key)) {
1584 ix = Nuitka_Py_unicodekeys_lookup_unicode_threadsafe(dk, key, hash);
1585 } else {
1586 ix = Nuitka_Py_unicodekeys_lookup_generic_threadsafe(mp, dk, key, hash);
1587 }
1588 if (ix == DKIX_KEY_CHANGED) {
1589 goto read_failed;
1590 }
1591
1592 if (ix >= 0) {
1593 if (kind == DICT_KEYS_SPLIT) {
1594 PyDictValues *values = _Py_atomic_load_ptr(&mp->ma_values);
1595 if (values == NULL)
1596 goto read_failed;
1597
1598 uint8_t capacity = _Py_atomic_load_uint8_relaxed(&values->capacity);
1599 if (ix >= (Py_ssize_t)capacity)
1600 goto read_failed;
1601
1602 value = _Py_TryXGetRef(&values->values[ix]);
1603 if (value == NULL)
1604 goto read_failed;
1605
1606 if (values != _Py_atomic_load_ptr(&mp->ma_values)) {
1607 Py_DECREF(value);
1608 goto read_failed;
1609 }
1610 } else {
1611 value = _Py_TryXGetRef(&DK_UNICODE_ENTRIES(dk)[ix].me_value);
1612 if (value == NULL) {
1613 goto read_failed;
1614 }
1615
1616 if (dk != _Py_atomic_load_ptr(&mp->ma_keys)) {
1617 Py_DECREF(value);
1618 goto read_failed;
1619 }
1620 }
1621 } else {
1622 value = NULL;
1623 }
1624 } else {
1625 ix = Nuitka_Py_dictkeys_generic_lookup_threadsafe(mp, dk, key, hash);
1626 if (ix == DKIX_KEY_CHANGED) {
1627 goto read_failed;
1628 }
1629 if (ix >= 0) {
1630 value = _Py_TryXGetRef(&DK_ENTRIES(dk)[ix].me_value);
1631 if (value == NULL)
1632 goto read_failed;
1633
1634 if (dk != _Py_atomic_load_ptr(&mp->ma_keys)) {
1635 Py_DECREF(value);
1636 goto read_failed;
1637 }
1638 } else {
1639 value = NULL;
1640 }
1641 }
1642
1643 *value_addr = value;
1644 return ix;
1645
1646read_failed:
1647 // In addition to the normal races of the dict being modified the _Py_TryXGetRef
1648 // can all fail if they don't yet have a shared ref count. That can happen here
1649 // or in the *_lookup_* helper. In that case we need to take the lock to avoid
1650 // mutation and do a normal incref which will make them shared.
1651 Py_BEGIN_CRITICAL_SECTION(mp);
1652 PyObject **locked_value_addr = NULL;
1653 ix = Nuitka_PyDictLookup(mp, key, hash, &locked_value_addr);
1654 value = locked_value_addr == NULL ? NULL : *locked_value_addr;
1655 *value_addr = value;
1656 if (value != NULL) {
1657 assert(ix >= 0);
1658 _Py_NewRefWithLock(value);
1659 }
1660 Py_END_CRITICAL_SECTION();
1661 return ix;
1662}
1663
1664#else // Py_GIL_DISABLED
1665
1666Py_ssize_t Nuitka_Py_dict_lookup_threadsafe(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject **value_addr) {
1667 Py_ssize_t ix = Nuitka_PyDictLookup(mp, key, hash, &value_addr);
1668 Py_XNewRef(*value_addr);
1669 return ix;
1670}
1671
1672#endif
1673
1674Py_ssize_t Nuitka_PyDictLookup(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject ***value_addr) {
1675 PyDictKeysObject *dk;
1676 DictKeysKind kind;
1677 Py_ssize_t ix;
1678
1679 _Py_CRITICAL_SECTION_ASSERT_OBJECT_LOCKED(mp);
1680restart:
1681 dk = mp->ma_keys;
1682 kind = (DictKeysKind)dk->dk_kind;
1683
1684 if (kind != DICT_KEYS_GENERAL) {
1685 if (PyUnicode_CheckExact(key)) {
1686#ifdef Py_GIL_DISABLED
1687 if (kind == DICT_KEYS_SPLIT) {
1688 ix = Nuitka_Py_unicodekeys_lookup_unicode_threadsafe(dk, key, hash);
1689
1690 if (ix == DKIX_KEY_CHANGED) {
1691 LOCK_KEYS(dk);
1692 ix = Nuitka_Py_unicodekeys_lookup_unicode(dk, key, hash);
1693 UNLOCK_KEYS(dk);
1694 }
1695 } else
1696#endif
1697 {
1698 ix = Nuitka_Py_unicodekeys_lookup_unicode(dk, key, hash);
1699 }
1700 } else {
1701 INCREF_KEYS_FT(dk);
1702 LOCK_KEYS_IF_SPLIT(dk, kind);
1703
1704 ix = Nuitka_Py_unicodekeys_lookup_generic(mp, dk, key, hash);
1705
1706 UNLOCK_KEYS_IF_SPLIT(dk, kind);
1707 DECREF_KEYS_FT(dk, IS_DICT_SHARED(mp));
1708
1709 // Dictionary lookup changed the dictionary, retry.
1710 if (ix == DKIX_KEY_CHANGED) {
1711 goto restart;
1712 }
1713 }
1714
1715 if (ix >= 0) {
1716 if (kind == DICT_KEYS_SPLIT) {
1717 *value_addr = &mp->ma_values->values[ix];
1718 } else {
1719 *value_addr = &DK_UNICODE_ENTRIES(dk)[ix].me_value;
1720 }
1721 } else {
1722 *value_addr = NULL;
1723 }
1724 } else {
1725 ix = Nuitka_Py_dictkeys_generic_lookup(mp, dk, key, hash);
1726
1727 // Dictionary lookup changed the dictionary, retry.
1728 if (ix == DKIX_KEY_CHANGED) {
1729 goto restart;
1730 }
1731
1732 if (ix >= 0) {
1733 *value_addr = &DK_ENTRIES(dk)[ix].me_value;
1734 } else {
1735 *value_addr = NULL;
1736 }
1737 }
1738
1739 return ix;
1740}
1741
1742#else
1743static Py_ssize_t Nuitka_Py_unicodekeys_lookup_generic(PyDictObject *mp, PyDictKeysObject *dk, PyObject *key,
1744 Py_hash_t hash) {
1745 PyDictUnicodeEntry *ep0 = DK_UNICODE_ENTRIES(dk);
1746
1747 size_t mask = DK_MASK(dk);
1748 size_t perturb = hash;
1749 size_t i = (size_t)hash & mask;
1750
1751 while (1) {
1752 Py_ssize_t ix = Nuitka_Py_dictkeys_get_index(dk, i);
1753
1754 if (ix >= 0) {
1755 PyDictUnicodeEntry *ep = &ep0[ix];
1756
1757 assert(ep->me_key != NULL);
1758 assert(PyUnicode_CheckExact(ep->me_key));
1759
1760 if (ep->me_key == key) {
1761 return ix;
1762 }
1763
1764 if (Nuitka_Py_unicode_get_hash(ep->me_key) == hash) {
1765 PyObject *startkey = ep->me_key;
1766 Py_INCREF(startkey);
1767 nuitka_bool cmp = RICH_COMPARE_EQ_NBOOL_UNICODE_OBJECT(startkey, key);
1768 Py_DECREF(startkey);
1769
1770 if (unlikely(cmp == NUITKA_BOOL_EXCEPTION)) {
1771 return DKIX_ERROR;
1772 }
1773
1774 if (dk == mp->ma_keys && ep->me_key == startkey) {
1775 if (cmp == NUITKA_BOOL_TRUE) {
1776 return ix;
1777 }
1778 } else {
1779 // In case of changed dictionary, trigger restart in caller.
1780 return DKIX_KEY_CHANGED;
1781 }
1782 }
1783 } else if (ix == DKIX_EMPTY) {
1784 return DKIX_EMPTY;
1785 }
1786 perturb >>= PERTURB_SHIFT;
1787 i = mask & (i * 5 + perturb + 1);
1788 }
1789
1790 NUITKA_CANNOT_GET_HERE("Nuitka_Py_unicodekeys_lookup_generic failed");
1791}
1792
1793Py_ssize_t Nuitka_Py_unicodekeys_lookup_unicode(PyDictKeysObject *dk, PyObject *key, Py_hash_t hash) {
1794 assert(PyUnicode_CheckExact(key));
1795 assert(dk->dk_kind != DICT_KEYS_GENERAL);
1796
1797 PyDictUnicodeEntry *ep0 = DK_UNICODE_ENTRIES(dk);
1798
1799 size_t mask = DK_MASK(dk);
1800 size_t perturb = hash;
1801 size_t i = (size_t)hash & mask;
1802
1803 while (true) {
1804 Py_ssize_t ix = Nuitka_Py_dictkeys_get_index(dk, i);
1805
1806 // Found it.
1807 if (ix >= 0) {
1808 PyDictUnicodeEntry *ep = &ep0[ix];
1809 assert(ep->me_key != NULL);
1810 assert(PyUnicode_CheckExact(ep->me_key));
1811
1812 if (ep->me_key == key || (Nuitka_Py_unicode_get_hash(ep->me_key) == hash &&
1813 RICH_COMPARE_EQ_CBOOL_UNICODE_UNICODE(ep->me_key, key))) {
1814 return ix;
1815 }
1816 } else if (ix == DKIX_EMPTY) {
1817 return DKIX_EMPTY;
1818 }
1819 perturb >>= PERTURB_SHIFT;
1820
1821 i = mask & (i * 5 + perturb + 1);
1822 ix = Nuitka_Py_dictkeys_get_index(dk, i);
1823
1824 if (ix >= 0) {
1825 PyDictUnicodeEntry *ep = &ep0[ix];
1826
1827 assert(ep->me_key != NULL);
1828 assert(PyUnicode_CheckExact(ep->me_key));
1829
1830 if (ep->me_key == key || (Nuitka_Py_unicode_get_hash(ep->me_key) == hash &&
1831 RICH_COMPARE_EQ_CBOOL_UNICODE_UNICODE(ep->me_key, key))) {
1832 return ix;
1833 }
1834 } else if (ix == DKIX_EMPTY) {
1835 return DKIX_EMPTY;
1836 }
1837
1838 perturb >>= PERTURB_SHIFT;
1839 i = mask & (i * 5 + perturb + 1);
1840 }
1841
1842 NUITKA_CANNOT_GET_HERE("Nuitka_Py_unicodekeys_lookup_unicode failed");
1843}
1844
1845// Search key from Generic table.
1846static Py_ssize_t Nuitka_Py_dictkeys_generic_lookup(PyDictObject *mp, PyDictKeysObject *dk, PyObject *key,
1847 Py_hash_t hash) {
1848 PyDictKeyEntry *ep0 = DK_ENTRIES(dk);
1849
1850 size_t mask = DK_MASK(dk);
1851 size_t perturb = hash;
1852 size_t i = (size_t)hash & mask;
1853
1854 while (1) {
1855 Py_ssize_t ix = Nuitka_Py_dictkeys_get_index(dk, i);
1856
1857 if (ix >= 0) {
1858 PyDictKeyEntry *ep = &ep0[ix];
1859 assert(ep->me_key != NULL);
1860 if (ep->me_key == key) {
1861 return ix;
1862 }
1863 if (ep->me_hash == hash) {
1864 PyObject *startkey = ep->me_key;
1865 Py_INCREF(startkey);
1866 nuitka_bool cmp = RICH_COMPARE_EQ_NBOOL_OBJECT_OBJECT(startkey, key);
1867 Py_DECREF(startkey);
1868
1869 if (unlikely(cmp == NUITKA_BOOL_EXCEPTION)) {
1870 return DKIX_ERROR;
1871 }
1872 if (dk == mp->ma_keys && ep->me_key == startkey) {
1873 if (cmp == NUITKA_BOOL_TRUE) {
1874 return ix;
1875 }
1876 } else {
1877 // In case of changed dictionary, trigger restart in caller.
1878 return DKIX_KEY_CHANGED;
1879 }
1880 }
1881 } else if (ix == DKIX_EMPTY) {
1882 return DKIX_EMPTY;
1883 }
1884 perturb >>= PERTURB_SHIFT;
1885 i = mask & (i * 5 + perturb + 1);
1886 }
1887}
1888
1889Py_ssize_t Nuitka_PyDictLookup(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject ***value_addr) {
1890 PyDictKeysObject *dk;
1891 DictKeysKind kind;
1892 Py_ssize_t ix;
1893
1894 _Py_CRITICAL_SECTION_ASSERT_OBJECT_LOCKED(mp);
1895restart:
1896 dk = mp->ma_keys;
1897 kind = (DictKeysKind)dk->dk_kind;
1898
1899 if (kind != DICT_KEYS_GENERAL) {
1900 if (PyUnicode_CheckExact(key)) {
1901#ifdef Py_GIL_DISABLED
1902 if (kind == DICT_KEYS_SPLIT) {
1903 ix = Nuitka_Py_unicodekeys_lookup_unicode_threadsafe(dk, key, hash);
1904
1905 if (ix == DKIX_KEY_CHANGED) {
1906 LOCK_KEYS(dk);
1907 ix = Nuitka_Py_unicodekeys_lookup_unicode(dk, key, hash);
1908 UNLOCK_KEYS(dk);
1909 }
1910 } else
1911#endif
1912 {
1913 ix = Nuitka_Py_unicodekeys_lookup_unicode(dk, key, hash);
1914 }
1915 } else {
1916 INCREF_KEYS_FT(dk);
1917 LOCK_KEYS_IF_SPLIT(dk, kind);
1918
1919 ix = Nuitka_Py_unicodekeys_lookup_generic(mp, dk, key, hash);
1920
1921 UNLOCK_KEYS_IF_SPLIT(dk, kind);
1922 DECREF_KEYS_FT(dk, IS_DICT_SHARED(mp));
1923
1924 // Dictionary lookup changed the dictionary, retry.
1925 if (ix == DKIX_KEY_CHANGED) {
1926 goto restart;
1927 }
1928 }
1929
1930 if (ix >= 0) {
1931 if (kind == DICT_KEYS_SPLIT) {
1932 *value_addr = &mp->ma_values->values[ix];
1933 } else {
1934 *value_addr = &DK_UNICODE_ENTRIES(dk)[ix].me_value;
1935 }
1936 } else {
1937 *value_addr = NULL;
1938 }
1939 } else {
1940 ix = Nuitka_Py_dictkeys_generic_lookup(mp, dk, key, hash);
1941
1942 // Dictionary lookup changed the dictionary, retry.
1943 if (ix == DKIX_KEY_CHANGED) {
1944 goto restart;
1945 }
1946
1947 if (ix >= 0) {
1948 *value_addr = &DK_ENTRIES(dk)[ix].me_value;
1949 } else {
1950 *value_addr = NULL;
1951 }
1952 }
1953
1954 return ix;
1955}
1956#endif
1957
1958Py_ssize_t Nuitka_PyDictLookupStr(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject ***value_addr) {
1959 assert(PyUnicode_CheckExact(key));
1960
1961 PyDictKeysObject *dk = mp->ma_keys;
1962 assert(dk->dk_kind != DICT_KEYS_GENERAL);
1963
1964 Py_ssize_t ix = Nuitka_Py_unicodekeys_lookup_unicode(dk, key, hash);
1965
1966 if (ix >= 0) {
1967 if (dk->dk_kind == DICT_KEYS_SPLIT) {
1968 *value_addr = &mp->ma_values->values[ix];
1969 } else {
1970 *value_addr = &DK_UNICODE_ENTRIES(dk)[ix].me_value;
1971 }
1972 } else {
1973 *value_addr = NULL;
1974 }
1975
1976 return ix;
1977}
1978
1979#endif
1980
1981bool Nuitka_DictNext(PyObject *dict, Py_ssize_t *pos, PyObject **key_ptr, PyObject **value_ptr) {
1982 CHECK_OBJECT(dict);
1983 assert(PyDict_CheckExact(dict));
1984 assert(key_ptr != NULL);
1985 assert(value_ptr != NULL);
1986
1987#if PYTHON_VERSION < 0x300
1988 Py_ssize_t i = *pos;
1989
1990 PyDictEntry *ep = ((PyDictObject *)dict)->ma_table;
1991 Py_ssize_t mask = ((PyDictObject *)dict)->ma_mask;
1992
1993 while (i <= mask && ep[i].me_value == NULL) {
1994 i++;
1995 }
1996
1997 *pos = i + 1;
1998
1999 if (i > mask) {
2000 return false;
2001 }
2002
2003 *key_ptr = ep[i].me_key;
2004 *value_ptr = ep[i].me_value;
2005
2006 return true;
2007
2008#elif PYTHON_VERSION < 0x360
2009 PyDictObject *mp = (PyDictObject *)dict;
2010 PyObject **dict_value_ptr;
2011 Py_ssize_t offset;
2012
2013 Py_ssize_t i = *pos;
2014 assert(i >= 0);
2015
2016 if (mp->ma_values) {
2017 dict_value_ptr = &mp->ma_values[i];
2018 offset = sizeof(PyObject *);
2019 } else {
2020 dict_value_ptr = &mp->ma_keys->dk_entries[i].me_value;
2021 offset = sizeof(PyDictKeyEntry);
2022 }
2023
2024 Py_ssize_t mask = DK_MASK(mp->ma_keys);
2025
2026 while ((i <= mask) && (*dict_value_ptr == NULL)) {
2027 dict_value_ptr = (PyObject **)(((char *)dict_value_ptr) + offset);
2028 i++;
2029 }
2030
2031 if (i > mask) {
2032 return false;
2033 }
2034
2035 *key_ptr = mp->ma_keys->dk_entries[i].me_key;
2036 *value_ptr = *dict_value_ptr;
2037 *pos = i + 1;
2038
2039 return true;
2040
2041#elif PYTHON_VERSION < 0x3b0
2042 PyDictObject *mp = (PyDictObject *)dict;
2043 PyDictKeyEntry *entry;
2044 PyObject *value;
2045
2046 Py_ssize_t i = *pos;
2047 assert(i >= 0);
2048
2049 if (mp->ma_values) {
2050 if (i >= mp->ma_used) {
2051 return false;
2052 }
2053
2054 entry = &DK_ENTRIES(mp->ma_keys)[i];
2055 value = DK_VALUE(mp, i);
2056
2057 assert(value != NULL);
2058 } else {
2059 Py_ssize_t n = mp->ma_keys->dk_nentries;
2060
2061 if (i >= n) {
2062 return false;
2063 }
2064
2065 entry = &DK_ENTRIES(mp->ma_keys)[i];
2066
2067 while (i < n && entry->me_value == NULL) {
2068 entry += 1;
2069 i += 1;
2070 }
2071
2072 if (i >= n) {
2073 return false;
2074 }
2075
2076 value = entry->me_value;
2077 }
2078
2079 *pos = i + 1;
2080
2081 *key_ptr = entry->me_key;
2082 *value_ptr = value;
2083
2084 return true;
2085#else
2086 PyDictObject *mp = (PyDictObject *)dict;
2087 Py_ssize_t i = *pos;
2088 PyObject *key, *value;
2089
2090 if (mp->ma_values) {
2091 // Shared keys dictionary.
2092 assert(mp->ma_used <= SHARED_KEYS_MAX_SIZE);
2093
2094 if (i >= mp->ma_used) {
2095 return false;
2096 }
2097
2098 int index = Nuitka_py_get_index_from_order(mp, i);
2099 value = mp->ma_values->values[index];
2100
2101 key = DK_UNICODE_ENTRIES(mp->ma_keys)[index].me_key;
2102
2103 assert(value != NULL);
2104 } else {
2105 Py_ssize_t n = mp->ma_keys->dk_nentries;
2106
2107 if (i >= n) {
2108 return false;
2109 }
2110
2111 // Unicode keys or general keys have different sizes, make sure to index
2112 // the right type, the algorithm is the same however.
2113 if (DK_IS_UNICODE(mp->ma_keys)) {
2114 PyDictUnicodeEntry *entry_ptr = &DK_UNICODE_ENTRIES(mp->ma_keys)[i];
2115
2116 while (i < n && entry_ptr->me_value == NULL) {
2117 entry_ptr++;
2118 i++;
2119 }
2120
2121 if (i >= n) {
2122 return false;
2123 }
2124
2125 key = entry_ptr->me_key;
2126 value = entry_ptr->me_value;
2127 } else {
2128 PyDictKeyEntry *entry_ptr = &DK_ENTRIES(mp->ma_keys)[i];
2129
2130 while (i < n && entry_ptr->me_value == NULL) {
2131 entry_ptr++;
2132 i++;
2133 }
2134
2135 if (i >= n) {
2136 return false;
2137 }
2138
2139 key = entry_ptr->me_key;
2140 value = entry_ptr->me_value;
2141 }
2142 }
2143
2144 *pos = i + 1;
2145
2146 *key_ptr = key;
2147 *value_ptr = value;
2148
2149 return true;
2150#endif
2151}
2152
2153PyObject *TO_DICT(PyThreadState *tstate, PyObject *seq_obj, PyObject *dict_obj) {
2154 PyObject *result;
2155
2156 if (seq_obj != NULL) {
2157 CHECK_OBJECT(seq_obj);
2158
2159 // Fast path for dictionaries.
2160 if (PyDict_CheckExact(seq_obj)) {
2161 result = DICT_COPY(tstate, seq_obj);
2162 } else {
2163 result = MAKE_DICT_EMPTY(tstate);
2164
2165 Py_INCREF(seq_obj);
2166
2167#if PYTHON_VERSION >= 0x300
2168 int res = HAS_ATTR_BOOL2(tstate, seq_obj, const_str_plain_keys);
2169
2170 if (unlikely(res == -1)) {
2171 Py_DECREF(seq_obj);
2172 return NULL;
2173 }
2174#else
2175 int res = HAS_ATTR_BOOL(tstate, seq_obj, const_str_plain_keys) ? 1 : 0;
2176#endif
2177
2178 if (res) {
2179 res = PyDict_Merge(result, seq_obj, 1);
2180 } else {
2181 res = PyDict_MergeFromSeq2(result, seq_obj, 1);
2182 }
2183
2184 Py_DECREF(seq_obj);
2185
2186 if (unlikely(res == -1)) {
2187 return NULL;
2188 }
2189 }
2190 } else {
2191 result = MAKE_DICT_EMPTY(tstate);
2192 }
2193
2194 // TODO: Should specialize for dict_obj/seq_obj presence to save a bit of time
2195 // and complexity.
2196 if (dict_obj != NULL) {
2197 CHECK_OBJECT(dict_obj);
2198
2199 int res = PyDict_Merge(result, dict_obj, 1);
2200
2201 if (unlikely(res == -1)) {
2202 return NULL;
2203 }
2204 }
2205
2206 return result;
2207}
2208
2209#if _NUITKA_MAINTAIN_DICT_VERSION_TAG
2210uint64_t nuitka_dict_version_tag_counter = ((uint64_t)1) << 32;
2211#endif
2212
2213#if NUITKA_DICT_HAS_FREELIST
2214PyObject *MAKE_DICT_EMPTY(PyThreadState *tstate) {
2215 PyDictObject *empty_dict_mp = (PyDictObject *)const_dict_empty;
2216
2217#if PYTHON_VERSION < 0x3c0
2218 empty_dict_mp->ma_keys->dk_refcnt++;
2219#endif
2220
2221 PyDictObject *result_mp = _Nuitka_AllocatePyDictObject(tstate);
2222
2223 result_mp->ma_keys = empty_dict_mp->ma_keys;
2224#if PYTHON_VERSION < 0x3b0
2225 result_mp->ma_values = empty_dict_mp->ma_values;
2226#else
2227 assert(empty_dict_mp->ma_values == NULL);
2228 result_mp->ma_values = NULL;
2229#endif
2230 result_mp->ma_used = 0;
2231#if PYTHON_VERSION >= 0x3c0 && PYTHON_VERSION < 0x3e0
2232 result_mp->ma_version_tag = DICT_NEXT_VERSION(_PyInterpreterState_GET());
2233#elif PYTHON_VERSION >= 0x360 && PYTHON_VERSION < 0x3e0
2234 result_mp->ma_version_tag = 1;
2235#endif
2236
2237 // Key reference needs to be counted on older Python
2238#if PYTHON_VERSION < 0x3c0
2239 Nuitka_Py_IncRefTotal(tstate);
2240#endif
2241
2242 // Python 3.14 tracks even empty dicts, older versions did not.
2243#if PYTHON_VERSION >= 0x3e0
2244 Nuitka_GC_Track(result_mp);
2245#endif
2246
2247 return (PyObject *)result_mp;
2248}
2249#endif
2250
2251PyObject *MAKE_DICT(PyObject **pairs, Py_ssize_t size) {
2252 PyObject *result = _PyDict_NewPresized(size);
2253
2254 // Reject usage like this.
2255 assert(size > 0);
2256 for (Py_ssize_t i = 0; i < size; i++) {
2257 PyObject *key = pairs[i * 2];
2258 PyObject *value = pairs[i * 2 + 1];
2259
2260 int res = PyDict_SetItem(result, key, value);
2261
2262 if (unlikely(res != 0)) {
2263 Py_DECREF(result);
2264 return NULL;
2265 }
2266 }
2267
2268 return result;
2269}
2270
2271PyObject *MAKE_DICT_X(PyObject **pairs, Py_ssize_t size) {
2272 PyObject *result = _PyDict_NewPresized(size);
2273
2274 // Reject usage like this.
2275 assert(size > 0);
2276 for (Py_ssize_t i = 0; i < size; i++) {
2277 PyObject *value = pairs[i * 2 + 1];
2278
2279 if (value != NULL) {
2280 PyObject *key = pairs[i * 2];
2281 CHECK_OBJECT(key);
2282 CHECK_OBJECT(value);
2283
2284 int res = PyDict_SetItem(result, key, value);
2285
2286 if (unlikely(res != 0)) {
2287 Py_DECREF(result);
2288 return NULL;
2289 }
2290 }
2291 }
2292
2293 return result;
2294}
2295
2296PyObject *MAKE_DICT_X_CSTR(char const **keys, PyObject **values, Py_ssize_t size) {
2297 PyObject *result = _PyDict_NewPresized(size);
2298
2299 // Reject usage like this.
2300 assert(size > 0);
2301 for (Py_ssize_t i = 0; i < size; i++) {
2302 PyObject *value = values[i];
2303
2304 if (value != NULL) {
2305 CHECK_OBJECT(value);
2306
2307 int res = PyDict_SetItemString(result, keys[i], value);
2308
2309 if (unlikely(res != 0)) {
2310 Py_DECREF(result);
2311 return NULL;
2312 }
2313 }
2314 }
2315
2316 return result;
2317}
2318
2319// Part of "Nuitka", an optimizing Python compiler that is compatible and
2320// integrates with CPython, but also works on its own.
2321//
2322// Licensed under the GNU Affero General Public License, Version 3 (the "License");
2323// you may not use this file except in compliance with the License.
2324// You may obtain a copy of the License at
2325//
2326// http://www.gnu.org/licenses/agpl.txt
2327//
2328// Unless required by applicable law or agreed to in writing, software
2329// distributed under the License is distributed on an "AS IS" BASIS,
2330// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
2331// See the License for the specific language governing permissions and
2332// limitations under the License.
Nuitka_ExceptionPreservationItem
Definition exceptions.h:712
dictiterobject
Definition HelpersDictionaries.c:904
dictviewobject
Definition HelpersDictionaries.c:1007