dict.fromkeys() re-hashes keys taken from a set, frozenset, or dict #8490

Summary

dict.fromkeys() recomputes __hash__ for every key when the iterable is a set, frozenset, or dict — all of which already store a hash per entry. CPython's dict_fromkeys_impl (Objects/dictobject.c) branches on PyAnySet_Check / PyDict_CheckExact and feeds the hash from _PySet_NextEntry / _PyDict_Next straight into insertdict.

This is the dict-target counterpart of #8489 (set/frozenset target).

Reproduction

class HashCountingInt(int):
    def __init__(self, *args):
        self.hash_count = 0
    def __hash__(self):
        self.hash_count += 1
        return int.__hash__(self)

d = dict.fromkeys(map(HashCountingInt, range(10)))
print(sum(e.hash_count for e in d))   # 10
dict.fromkeys(set(d))
print(sum(e.hash_count for e in d))   # CPython: 10, RustPython: 20

Lib/test/test_set.py:333 — TestJointOps.test_do_not_rehash_dict_keys asserts on both directions, so its @unittest.expectedFailure # TODO: RUSTPYTHON marker can only be dropped once both this issue and #8489 are done. It is inherited by TestSet, TestSetSubclass, TestFrozenSet and TestFrozenSetSubclass (4 of the 10 expected failures in test_set.py).

Analysis

PyDict::fromkeys (crates/vm/src/builtins/dict.rs:377) iterates generically regardless of what the source is:

match d.downcast_exact::<Self>(vm) {
    Ok(pydict) => {
        for key in iterable.iter(vm)? {
            pydict.__setitem__(key?, value.clone(), vm)?;
        }
        Ok(pydict.into_pyref().into())
    }
    ...
}

__setitem__ → inner_setitem (:302) → entries.insert() ends up calling key.key_hash(vm), so a source that already knows the hash pays for it twice.