https://github.com/python/cpython/commit/421ba589d02b53131f793889d221ef3b1f1410a4
commit: 421ba589d02b53131f793889d221ef3b1f1410a4
branch: main
author: Angela Liss <[email protected]>
committer: colesbury <[email protected]>
date: 2025-05-08T13:13:11-04:00
summary:
gh-132762: Fix underallocation bug in `dict.fromkeys()`(gh-133627)
The function `dict_set_fromkeys()` adds elements of a set to an existing
dictionary. The size of the expanded dictionary was estimated with
`PySet_GET_SIZE(iterable)`, which did not take into account the size of the
existing dictionary.
files:
A
Misc/NEWS.d/next/Core_and_Builtins/2025-05-08-13-48-02.gh-issue-132762.tKbygC.rst
M Lib/test/test_dict.py
M Objects/dictobject.c
diff --git a/Lib/test/test_dict.py b/Lib/test/test_dict.py
index 3104cbc66cb115..69f1a098920b94 100644
--- a/Lib/test/test_dict.py
+++ b/Lib/test/test_dict.py
@@ -338,17 +338,34 @@ def __setitem__(self, key, value):
self.assertRaises(Exc, baddict2.fromkeys, [1])
# test fast path for dictionary inputs
+ res = dict(zip(range(6), [0]*6))
d = dict(zip(range(6), range(6)))
- self.assertEqual(dict.fromkeys(d, 0), dict(zip(range(6), [0]*6)))
-
+ self.assertEqual(dict.fromkeys(d, 0), res)
+ # test fast path for set inputs
+ d = set(range(6))
+ self.assertEqual(dict.fromkeys(d, 0), res)
+ # test slow path for other iterable inputs
+ d = list(range(6))
+ self.assertEqual(dict.fromkeys(d, 0), res)
+
+ # test fast path when object's constructor returns large non-empty dict
class baddict3(dict):
def __new__(cls):
return d
- d = {i : i for i in range(10)}
+ d = {i : i for i in range(1000)}
res = d.copy()
res.update(a=None, b=None, c=None)
self.assertEqual(baddict3.fromkeys({"a", "b", "c"}), res)
+ # test slow path when object is a proper subclass of dict
+ class baddict4(dict):
+ def __init__(self):
+ dict.__init__(self, d)
+ d = {i : i for i in range(1000)}
+ res = d.copy()
+ res.update(a=None, b=None, c=None)
+ self.assertEqual(baddict4.fromkeys({"a", "b", "c"}), res)
+
def test_copy(self):
d = {1: 1, 2: 2, 3: 3}
self.assertIsNot(d.copy(), d)
diff --git
a/Misc/NEWS.d/next/Core_and_Builtins/2025-05-08-13-48-02.gh-issue-132762.tKbygC.rst
b/Misc/NEWS.d/next/Core_and_Builtins/2025-05-08-13-48-02.gh-issue-132762.tKbygC.rst
new file mode 100644
index 00000000000000..80b830ebd786f3
--- /dev/null
+++
b/Misc/NEWS.d/next/Core_and_Builtins/2025-05-08-13-48-02.gh-issue-132762.tKbygC.rst
@@ -0,0 +1 @@
+:meth:`~dict.fromkeys` no longer loops forever when adding a small set of keys
to a large base dict. Patch by Angela Liss.
diff --git a/Objects/dictobject.c b/Objects/dictobject.c
index 59b0cf1ce7d422..32356f0634db15 100644
--- a/Objects/dictobject.c
+++ b/Objects/dictobject.c
@@ -3178,9 +3178,10 @@ dict_set_fromkeys(PyInterpreterState *interp,
PyDictObject *mp,
Py_ssize_t pos = 0;
PyObject *key;
Py_hash_t hash;
-
- if (dictresize(interp, mp,
- estimate_log2_keysize(PySet_GET_SIZE(iterable)), 0)) {
+ uint8_t new_size = Py_MAX(
+ estimate_log2_keysize(PySet_GET_SIZE(iterable)),
+ DK_LOG_SIZE(mp->ma_keys));
+ if (dictresize(interp, mp, new_size, 0)) {
Py_DECREF(mp);
return NULL;
}
_______________________________________________
Python-checkins mailing list -- [email protected]
To unsubscribe send an email to [email protected]
https://mail.python.org/mailman3/lists/python-checkins.python.org/
Member address: [email protected]
