HashMap/HashSet key that cannot be hashed passes the checker and fails in rustc (the sibling of D15)Open and answer this issue on GitHub.
compiler, ready · opened 2026-10-12 · updated 2026-11-03 · 4 comments
A HashMap finds a value by hashing its key, so the key type must be hashable and have an equality that is an equivalence (Rust: Hash + Eq). A float is neither (NaN != NaN), and a struct the program declares derives PartialEq, Eq and Copy where its parts allow, but not Hash.
struct P { x: i64 }
let mut a: collections::HashMap[P, i64] = collections::HashMap()
a.insert(P { x: 1 }, 1) // the checker accepts; rustc refusesFound while building NK1247 for #589 (ordered maps: ADR-010 D10), which refuses a BTreeMap/BTreeSet key with no order. The same question for the hash maps was not asked then. Nobody’s program needs it yet; it is a Part III C.1 hole: a rustc error about generated code reaches the user.
nikaia run)HashMap[P, i64] (declared struct), HashMap[f64, i64] and HashMap[Q, i64] (a struct holding an f64) all pass the checker; each fails in rustc with the method insert exists for struct HashMap<..>, but its trait bounds were not satisfied (three errors, one per map). Comparable::asking already has Strength::Totally (Eq), used only to decide derives (compares_totally); nothing asks it for a map key.
Eq-comparable and whose type cannot be hashed, with a Nikaia message, as NK1247 does for order. Declared types stay unhashable. Cheapest; a user keys by text or number.Hash for a declared type whose parts hash (the same walk as compares_totally), so HashMap[P, V] works. More useful; field order then matters to nothing (a hash is not an order), so the risk is small. Adds a ledger column hashes for library types (as orders was added).(a): none beyond refusing programs that never compiled. (b): a derived Hash for a type with a custom == (there is none: equality is always derived) is the only way the two could disagree; and with #581 (hasher per class) the derive must work with both Fast and Keyed hashers (it does: Hash is hasher-independent).
(b), by the NK1247 pattern: Strength::Hashes in check/mod.rs, ledger column hashes, describe writes it where the crate derives Hash, the emitter derives Hash where compares_totally holds. Code NK1248 (check that it is free). If the owner wants the smaller step first: (a).
crates/nikaia/tests/hashed_keys.rs): keys that hash pass (numbers, String, bool, char, tuples/lists/options of those, declared structs and enums of those under (b)); f64, a struct holding one, a library type without hashes are refused in Nikaia’s words; BTreeMap is not asked.describe + described.contracts (Symbol hashes).Related: #589 (ordered keys, built), #586 (checker-accepts-rustc-refuses family), #581, #497 (an unknown type is not refused: this check inherits that).
Note from #592 (ADR-341): NK1248 and NK1249 are taken by that decision, so this issue’s check takes the next free code, not NK1248. Hash as a bound is the follow-up to #592 and shares the ledger-column pattern (orders, equates, and here hashes).
Generated by Claude Code
The owner took it as settled that a declared type used as a hash-map key gets a hash derived from its values. No record said so, so it is recorded now.
Where the question stood before. No ADR decided it. Two records left it to this issue:
Hash follows with the hash-map key check (#591)”.The closest decided rules are ADR-204 and ADR-341 D4 (equality derived from the parts) and ADR-010 D10 (ordered keys, NK1247, #589). D10 refused a derived order because field order would become a promise. A hash makes no such promise. No other issue covers this.
One fact changed since this issue was written. ADR-341 D5 now lets a program write impl Eq for its own type. “Equality is always derived” (Risk above) no longer holds. A hash derived from the fields would disagree with a hand-written equality, so such a type does not hash.
Recorded in ADR-010 D11. Part I (map keys), Part III 13.5 (ledger column hashes) and C.3 (NK1260; NK1248 went to ADR-341 and NK1257 to ADR-354). ADR-204 §4 and ADR-341 §6 now point to D11. Version 0.0.942, commit 5488b2d.
In short:
HashMap/HashSet key is checked by the structural walk == uses (NK1188).struct or enum hashes where every field hashes. The hash is derived from its fields in the order written, as equality is, so equal values hash alike. No one writes hasher.add(...).impl Eq do not hash. A library type hashes only where its ledger says hashes = true.NK1260 at every position a type is written. The message names the part that does not hash, or the hand-written equality.Not decided: Hash as a bound ([T: Hash]), ADR-341 §6.
crates/nikaia/tests/hashed_keys.rs).
String, bool, char, Bytes, tuples/lists/options of those, and declared structs and enums of those, used in insert, get, contains_key and a HashSet.NK1260 in Nikaia’s words for: f64; a struct holding one; a declared type with impl Eq; a library type without hashes.BTreeMap is not asked.Strength::Hashes beside compares_totally in the walk, with impl Eq read as does not hash. Report NK1260 at every type position.hashes column, read for library types. nikaia describe writes it where the crate derives Hash. Add hashes = true in std.contracts / described.contracts where it holds (Symbol among them).#[derive(Hash)] on a declared type where the walk says it hashes.HashMap[P, i64] keyed by a two-field struct, two equal keys find one entry, at both hash classes (a Trusted and an Untrusted map).The commit that builds the last step says Fixes #591.
Generated by Claude Code
Addendum (owner’s decision): a type with its own impl Eq hashes through an impl Hash.
The decision above refused every declared type with a hand-written impl Eq as a hash key. The owner narrowed that: such a type is refused unless it also writes impl Hash. Recorded as ADR-010 D12, Part I (map keys, the traits paragraph) and Part III (NK1249, NK1260), 0.0.944 (58e366d).
impl Hash for Name {
fn hash(ref self, mut into: Hasher) sync {
into.add(self.text.to_lowercase())
}
}Hash is a trait of the language, in scope like Eq and Ord; Hasher’s one method add(x) takes a value that hashes. It lowers to Rust’s Hash (into.add(x) is x.hash(state)). The hash function stays the map’s (D5): the body feeds values and never returns a number, so it cannot weaken a hardened map.impl Hash is allowed for any declared type that is Eq, by derivation or by impl Eq; it replaces the derived hash. Writing it for a foreign type or for a type that is not Eq is NK1249. A body that can pause is NK1129. A value handed to add that does not hash is NK1260.eq calls equal feed add the same values) is the program’s and is not checked, as for Eq (ADR-341 D5).[T: Hash] as a bound stays open (ADR-341 §6).To build, in addition to steps 1-5 above:
Hash and Hasher as language names. Answer the key check with “hashes” for a type with an impl Hash. Apply NK1249 (foreign type, or not Eq), NK1129 (pausing body) and NK1260 (argument of add).impl std::hash::Hash for P { fn hash<H: std::hash::Hasher>(&self, into: &mut H) { … } } with into.add(x) as (x).hash(into), and omit the Hash derive for P.Name with case-insensitive impl Eq + impl Hash as a HashMap key: "A" and "a" find the same entry;impl Hash is NK1260, and the message names the impl Hash;impl Hash on a type that is not Eq is NK1249;into.add(1.5) is NK1260.Generated by Claude Code
Still there at 31e2ea7 (language 0.0.1341), and it now blocks a planned piece: the e-graph of ADR-270 D13 keeps a signature table keyed by a declared struct (an operator and its children’s ids). Part I 2.x states the rule this issue builds: a struct or an enum the program declares is [a key] where every field is, hashed from its fields as == compares them.
use std::collections
struct Key { op: u32, a: u32, b: u32 }
fn main() {
let mut table: collections::HashMap[Key, u32] = collections::HashMap()
table.insert(Key { op: 1, a: 2, b: 3 }, 7)
let got = table[Key { op: 1, a: 2, b: 3 }] ?? 99
println(f"{got}")
}nikaia check accepts it; nikaia run fails in rustc: The method insert exists for struct HashMap<Key, u32>, but its trait bounds were not satisfied … Key: Hash. Expected: 7. Tuple keys work; per CLAUDE.md the solver does not write around this with tuples, so this probe belongs in step 1’s tests (as a tests/compiler/tests/*.nika with its .stdout, per the rule on new tests, instead of a new Rust test file).
Generated by Claude Code