User-defined dictionary keys and set members

Status: Structural-key policy implemented. Named enums whose payloads are supported key types now work as dictionary keys and set members, including nested enums. Classes whose fields are supported keys, including move-only classes and enums containing them, and the KeyType constraint are also implemented. Anonymous sums with supported key members are implemented. Custom-cleanup keys are admitted for borrowing and ownership transfer; copying operations reject them. Named enum and tuple sets with supported finite domains through 256 values now use bitsets, including boolean and nested enum/tuple payloads. The collection reference owns the current contract. The design and historical analysis below describe the broader proposal; enum/class admission and the explicit generic constraint have shipped. Generic bodies remain checked per concrete instance: unconstrained parameters are not rejected solely for appearing in a collection signature. The original eager-rejection analysis below is historical, not current behavior.

Problem

Before structural key admission, a program that wanted dict[Point, V], set[Color] or dict[UserId, V] had to flatten keys into tuples, losing their nominal types. Eligible classes and enums now work directly. Generic code can state its key requirement explicitly:

def count[K: KeyType](xs: &list[K]) -> Result[dict[K, i64], AllocError]:
    ...

The bound rejects unsupported arguments at instantiation. Unconstrained generic functions continue to work when their concrete keys are valid; requiring a bound on every collection signature is not part of the implemented contract.

The suggested direction is a __hash__ dunder and a protocol requiring it as the key bound. This page assesses that idea against the current implementation, then recommends a narrower design.

How dictionaries and sets work today

All dictionary and set operations enter one runtime function, plenty_collection(op, args, descriptor, site) (plenty-runtime/src/aggregates.rs:1423), with an opcode and the collection’s static type descriptor. Generated code never hashes or probes.

The runtime relies on two properties of every legal key, recorded in try_reserve: hashing never allocates and never calls user code. Table rebuilding computes hashes alone, in the middle of a reservation, with no error channel.

Issue #329 addressed two hash-quality defects independently of this proposal:

• The former FNV-1a path had no finalizer. Multiplication carries bits only upward, so the low k bits of a string’s hash depend only on the low k bits of each byte. A 16-bucket table (the minimum) puts "a", "q", "A", "Q", "1" and "!" in one bucket. Tables below 256 buckets are affected.
• It had no seed: colliding inputs could be precomputed. std.toml indexes parsed keys in dict[(i64, str), i64] (stdlib/std/toml.plenty:245), so untrusted TOML can force quadratic parsing. The dictionary reference already says adversarial collisions can make lookup linear.

The replacement keys the entire structured input, rather than applying a secret finalizer to an unkeyed prehash. It covers TOML’s index and duplicate-key set, and JSON’s duplicate-member set. HTTP and CSV currently use no dictionary/set tables in their implementations.

Historical cost of a composite key before keyed hashing

A probe on 2026-10-19 (release build of this branch, Linux x86-64, one pinned core; the machine had load average about 18, so treat these as indicative) ran 20 million membership tests, half hits, minimum of seven runs. These results predate issue #329’s keyed hashing and do not describe its current cost:

A two-field tuple key costs about 2.4 times an integer key, including building the probe tuple. Any user type admitted through the same descriptor path should cost about the same as the tuple with the same fields. This must be confirmed by the benchmark in Measurements.

Precedents

Python. __hash__ returns an integer and must agree with __eq__: a == b implies hash(a) == hash(b). Nothing enforces it. Defining __eq__ without __hash__ makes a class unhashable; mutable built-ins are unhashable by convention. A key mutated after insertion silently becomes unreachable. Dataclasses derive both from fields (frozen=True, eq=True).

Rust. Hash and Eq are separate traits, usually derived together. A type does not return a hash; it feeds its fields to a Hasher (fn hash<H: Hasher>(&self, state: &mut H)). The collection chooses the hasher, so seeding (SipHash with a random key in std), algorithm changes and mixing quality stay out of user code. Consistency with Eq is a documented logic requirement, not checked; violations cause wrong results but no memory unsafety. Interior mutability makes key mutation possible (Cell in a key), and is documented as a logic error.

Assessing the __hash__ protocol idea

The idea needs several things Plenty lacks, and most of them work against the project’s goals.

1. A protocol cannot express the bound. Protocols match ordinary methods (protocols). Integers, bool, and str have no methods, so dict[i64, V] would not satisfy a method protocol unless the compiler special-cased it. Every user key type would also need a hand-written method even when the derived answer is the only correct one. A bound that admits built-ins and derived types is a built-in constraint like IntType, not a protocol.
2. Custom hash without custom equality is nearly useless. With structural, non-overridable equality, any pure function of the fields is a consistent hash. The only gain from a custom one is speed (hash an id field and skip the rest), at the price of a callback per hash. The cases people actually write __hash__ for (case-insensitive names, ignoring a cache field) change equality.
3. Custom equality is a larger change than hashing. == would stop being structural for that type, equal in the runtime would need a callback, and collection equality, in, set algebra and dictionary comparison would all run user code. The classes reference promises equality “neither invokes user-defined magic methods”. Allowing __hash__ and __eq__ separately also imports Python’s unenforced consistency rule, which is exactly the kind of soft rule this language avoids.
4. Callbacks break runtime invariants. A user hash would run inside try_reserve’s rebuild, inside removal’s cluster repair (once per displaced entry), and during set algebra. It would need a no-allocation, no-trap-on-error contract, an effect restriction, and a new descriptor slot. See Where hashing runs.

The idea is right that keys need a named, generic bound. It does not need a dunder.

Where hashing runs

Measured context: in-cache integer lookups cost about 18 ns, almost all of it call, dispatch, and probing rather than hashing an integer. A callback adds an indirect call, an adapter that unpacks the slot, and possibly a Hasher object; expect a few nanoseconds per hash and per equality probe, on top of the tuple-equivalent cost. That estimate needs the measurement below before B is considered.

D gives the best per-operation speed and the worst compile time, code size, and correctness surface. It would duplicate aggregates.rs’s allocation-failure and destruction-order guarantees per type. It is the right tool only if the dispatcher itself, not hashing, dominates. Issue #18 gave list reads narrow runtime helpers for that reason; the same approach could apply to hashed lookups for all key types at once.

Recommendation

Derived structural keys, a built-in KeyType constraint, and no user hash or equality hooks. The rule has no exceptions and cannot be violated:

A key type is an integer, bool, str, byte string, or a tuple, class, or enum whose every field or payload is a key type. Recursive types are not key types. Dictionary keys, set members, and KeyType arguments must be key types. Hashing and equality are structural, so a == b always implies equal hashes.

class Point:
    x: i64
    y: i64

enum Shape:
    Dot(Point)
    Segment(Point, Point)

def count[K: KeyType](xs: &list[K]) -> Result[dict[K, i64], AllocError]:
    ...

seen: set[Shape] = set[Shape]()?          # accepted
weights: dict[Point, f64] = {}?           # accepted: values may be floats
bad: set[Sample] = set[Sample]()?         # rejected if Sample has an f64 field

Rationale

• Consistency is impossible to break. One structural equal serves == and lookup; one structural hash reads the same fields. There is no __hash__ to forget, no __eq__ to disagree with it.
• No new runtime invariant. Hashing still never allocates or calls user code, so try_reserve, removal repair, and worker-thread eligibility need no new rules. Effects are Compute only by construction (src/effects.rs).
• Small change. The runtime already hashes kind B structurally; it needs a class branch. The frontend needs one predicate, one constraint, and better diagnostics. Existing keys keep identical code paths.
• Custom identity stays explicit. A case-insensitive key is a key built from the normalized text (Name(text.lower()?)), not a hidden equality. The allocation is visible at construction, not repeated per probe.

Key immutability

Keys cannot change while stored, by existing rules plus the key-type rule:

• Insertion moves an affine key in or copies a copyable one.
• Every read of a stored key is a shared &K; no API lends &mut K, including mutable items() views and replace(d[k], v), which targets values.
• Key types contain no interior mutability. Excluded by the rule, without a separate list: floats (NaN != NaN, and 0.0 == -0.0 with different bits), references, Box and recursive data, collections, closures and callables, generators, atomics (std.atomic), std.sync.Mutex, channels, CancellationToken, tasks, files, sockets and other handles. A class holding any of these is not a key type.
• Strings share immutable storage, so retaining a str key is safe.

Affine keys

Every class not declared @copy is affine (moves and copies), so class keys are the first affine keys. Operations that today retain keys into new storage need the same treatment affine values already have:

Copyable enums (payloads of copyable key types) avoid this table entirely, which motivates the staging below.

Generic bound

KeyType is a built-in constraint beside IntType and FloatType (src/frontend/generics.rs). It accepts exactly the current collection key predicate, on functions, methods, classes and enums. An unsuitable argument reports TYPE does not satisfy KeyType, even if the generic body does not use hashing. Unconstrained generic bodies remain checked per concrete instance; dict[K, V] and set[K] do not independently require an explicit bound.

Diagnostics now name the first unsupported component in declaration order, including class field names, enum variants and payload positions, and tuple element positions. The path ends with the rejected type or a specific reason such as an unsupported anonymous-sum member; see key diagnostics.

DoS resistance and seeding

This runtime concern was implemented independently of user key admission in issue #329. SipHash-2-4 consumes all structural bytes with one OS-generated key per process. Adding a finalizer alone would improve low-bit distribution but would not prevent precomputed full-hash collisions. The key is initialized lazily and atomically; interrupted entropy reads retry, short reads accumulate, and other failures trap rather than weaken the key. Constructing empty collections does not require entropy. See the collection contract.

Dictionary iteration stays deterministic through its entry order, so tests need no public seed override. Set order remains unspecified. Keyed hashing does not remove the table’s theoretical linear-probe worst case.

The pinned siphasher 1.0.4 backend uses the original SipHash-2-4 schedule: two compression rounds and four finalization rounds. SipHash-1-3 uses fewer rounds to reduce hashing cost; this change chooses the original schedule as a conservative security margin. The collection benchmarks quantify the cost: short-key lookup is more expensive, especially for integers. Hashing remains a runtime policy, so callers need no new API or manual mixing.

Superseded 2026-11-05 (issue #747): the runtime now uses SipHash-1-3, the schedule of Rust’s HashMap, CPython and Swift, and hashes top-level str, bytes, integer and bool keys directly without the descriptor walk. Nested keys keep the framed encoding. See the collection contract.

Costs

Caching hashes is not part of the recommendation. It would cut rehash and removal cost and give a cheap pre-equality filter, for 8 bytes per bucket (doubling the table) or per row. Measure before adding it.

Measurements

Before implementation and before any follow-up optimization:

1. Extend examples/collection_bench.py (method in examples/collection-bench.md) with insert, hit, miss and remove workloads at 1,024 and 65,536 entries for dict[i64, i64], dict[(i64, i64), i64], dict[Point, i64] (two i64 fields), a copyable enum key, and dict[str, i64] with short keys. Pin to physical cores as in profiling.
2. Rerun against keyed hashing; report per-operation deltas for existing key types.
3. To evaluate design B at all: prototype a descriptor hook that returns the structural hash through an adapter and compare against A on the same workloads.
4. Compile time: compile_bench -- 1000 10 --workload aot before and after, per profiling; expected neutral.

Rejected alternatives

• __hash__(self) -> u64. User mixing, no seeding, and consistency is unenforced. Adds a callback for no correctness gain under structural equality.
• __hash__(self, h: &mut Hasher). Fixes distribution and seeding, but the only benefit without custom equality is skipping fields, paid for with a callback per hash and new runtime invariants.
• __eq__ plus __hash__. Makes == non-structural, puts user code inside every collection algorithm, and reintroduces a consistency rule the compiler cannot check.
• A method protocol as the bound. Cannot admit built-ins without a special case and forces boilerplate on every key type.
• Monomorphized tables (D). Compile time, code size, and duplicated failure semantics, against fast compilation. Revisit only if dispatch, not hashing, dominates measured cost, and then prefer narrow runtime helpers.
• Hashing floats by bits. Breaks a == b ⇒ hash(a) == hash(b) for 0.0/-0.0 and makes NaN keys unreachable. A user who needs float keys can store a canonical integer encoding explicitly.

Possible later extension: key projection

If custom identity proves necessary, the consistent form is one method that defines both equality and hashing by returning a key-type value:

class Name:
    text: str

    def __key__(self) -> str:
        ...  # normalized text

==, hash, in and lookup would all compare __key__() results, so they cannot disagree. It still needs a runtime callback (design B), a no-allocation rule on the projection (normalizing text usually allocates, which defeats the motivating example), and a change to the structural-equality promise. Explicit key construction covers the same cases today; this is not recommended now.

Ordering and sorted maps

Out of scope. User-defined ordering faces the same choice for < and sort: compare (aggregates.rs:808) is descriptor- interpreted like hash, and the same derived, structural rule keeps ordering consistent with equality. A sorted map would need both bounds; if ordering is derived structurally, every key type with no float fields is also totally ordered, and the two constraints could share one admission walk.

That proposal recommends a __cmp__ hook that also defines ==. A type that defines __cmp__ is therefore not a key type: its equality is user code, so a structural hash would not agree with it. Such values are keyed by a projection of the fields their __cmp__ compares.

Open questions

1. Name: KeyType, Hashable, or Key. KeyType matches IntType.
2. Resolved: classes with __del__, including nested cleanup, are keys when their fields are keys. Hashability does not imply duplicability. Non-mutating set algebra and key-view to_set() require explicit-copy eligibility, while insertion, borrowed views, relationships, in-place updates and owned extraction work without copying. Equal incoming keys are destroyed; existing key owners remain in the collection. No user-defined clone hook is added.
3. Private fields: structural hashing reads them, as equality already does. Confirm that is acceptable for public key types across modules.
4. Resolved: anonymous sums are key types when every member is.
5. Whether to cache hashes, after measurement.

Implementation sketch

1. Copyable enums. Extend Ty::hashable (src/collection.rs:189) to user and standard enums whose payloads are key types, rejecting recursion through type_facts (src/type_facts.rs). The runtime path already works for kind B. Update the three diagnostics (src/frontend.rs:885, src/frontend/collections.rs:891, :3138) to name the offending field. Tests in tests/test_collections.rs, test_dictionary_lookup.rs and test_set_operations.rs; reference updates to collections.md, enums.md, sets.md (which still lists only integers, booleans, and strings) and tutorial/04-collections/dictionaries.md.
2. KeyType constraint. Add it to the built-in constraint table (src/frontend/generics.rs:19, diagnostic at :1001); let dict[K, V] resolve in generic signatures when K: KeyType. Update generics.
3. Classes and affine enums. Add a class branch to write_key (plenty-runtime/src/aggregates/hashing.rs) over Record fields, plus a unit test beside aggregates/hash_tests.rs that equal classes in different storage hash equally. Audit each operation in Affine keys in src/frontend/collections.rs and the runtime’s retain/release paths (try_insert, Collection::at, set algebra). Use the runtime’s running-offset record iterator; field-offset traversal is already linear per pass (issue #330). Hash quality and per-process seeding are already implemented independently (issue #329); this sketch does not change their policy.