Add Entry API for TriHashMap

[sunshowers]

The Entry API exists for the other map crates, but hadn't had time to implement it for that one. It's pretty complex to do and would benefit from some close attention to the API.

[SG-devel]

Proposal

Update after implementation: The PR follows the core proposal: arity-specific public APIs, a small crate-internal lookup-state primitive, BiHashMap public API compatibility, and accessor-backed TriHashMap non-unique views. A few implementation details changed during development and review:

• the shared lookup primitive uses the crate’s existing internal ItemIndex directly rather than a generic test index type;
• occupied replacement uses the same prepared replacement/validation path for both unique and non-unique occupied entries, instead of a separate direct in-place replacement path for unique entries;
• the final test strategy uses targeted deterministic tests for public TriHashMap entry semantics and also adds TRI property-test operations for entry removal and occupied entry replacement.

I propose implementing TriHashMap’s Entry API with arity-specific public APIs, while extracting only the small shared internal state machine that BiHashMap and TriHashMap both need.

The implementation should not introduce a generic public Entry framework. It should keep bi_hash_map::Entry and tri_hash_map::Entry separate, but avoid duplicating the correctness-critical logic for entry lookup state.

The shared abstraction would be limited to:

• vacant / unique / non-unique classification
• partial-hit semantics
• per-key index preservation
• distinct-index projection in deterministic first-key-hit order
• key-position to distinct-slot mapping for accessor-backed non-unique views

The goal is a TriHashMap Entry API with BiHashMap feature parity at the endpoint/semantics level, without copying a BiHashMap public shape that is unsafe or misleading for three-key overlap patterns.

BiHashMap should remain source-compatible. Its current public enum field shape can be preserved, while BiHashMap can still use the shared internal state machine. Accessor methods could be added later, but this proposal does not require a breaking BiHashMap API change.

The proposal does not abstract the public API or the map backend. It only abstracts the small lookup-state primitive that BiHashMap and TriHashMap already need to agree on.

The implementation should remain no_std compatible. The shared primitive should use fixed arrays and core only; the Entry API can continue using the crate’s existing alloc-backed abstractions where allocation is already part of the API.

I have done a preliminary local feasibility check of this shape (cf. “Reviewability and feasibility” for the exact commands).

I have since implemented this shape in a draft PR, with the implementation differences noted above.

Unique vs. non-unique semantics and mutable non-unique access

Unique means the full entry key tuple identifies exactly one existing item.

A partial hit is occupied, but not unique. A mixed hit is occupied, but not unique.

For TriHashMap:

None / None / None
    => Vacant

Some(A) / Some(A) / Some(A)
    => Unique(A)

anything else with at least one hit
    => NonUnique

Therefore:

A / A / A    => Unique
A / A / None => NonUnique
A / A / B    => NonUnique
A / B / C    => NonUnique

A / A / None is non-unique because the full three-key entry does not exist. Some keys found an existing item, but not all keys identified the same item.

TriHashMap should not expose public mutable fields for non-unique entries, because TriHashMap can have overlapping non-unique matches:

key1 -> A
key2 -> A
key3 -> B

A public field API like this would be unsafe or misleading:

NonUnique {
    by_key1: Option<RefMut<_>>,
    by_key2: Option<RefMut<_>>,
    by_key3: Option<RefMut<_>>,
}

It would either need to expose two live mutable references to A, which is invalid, or fail to preserve the fact that both key1 and key2 matched A.

Instead, TriHashMap should use an accessor-backed view:

pub struct NonUniqueEntryMut<'a, T, S> {
    refs: [Option<RefMut<'a, T, S>>; 3],
    key_to_slot: [Option<usize>; 3],
}

With methods:

by_key1()
by_key2()
by_key3()
for_each()

For example:

input:
    key1 -> A
    key2 -> A
    key3 -> B

deduplicated refs:
    refs = [A, B, None]

mapping:
    key_to_slot = [Some(0), Some(0), Some(1)]

by_key1() and by_key2() can both resolve to A, but only sequentially through &mut self. The API never exposes two live RefMuts to the same item.

Alternative considered: partial-unique occupied entries

One alternative is to distinguish a “partial unique” occupied state from both full unique and mixed non-unique states. Under that model, lookups would classify as:

None / None / None => Vacant
A / A / A          => Unique(A)
A / A / None       => PartialUnique(A)
A / A / B          => NonUnique
A / B / C          => NonUnique

This is semantically precise: it separates “all present hits resolve to the same item” from “all entry key positions are present and resolve to the same item.” It also makes cases like A / None / A easier to describe without grouping them with mixed multi-item conflicts.

The downside is API complexity. The entry API would need either another public variant or another occupied substate, and callers would still need per-key accessors because the API must preserve which key positions missed. Operationally, PartialUnique behaves more like non-unique than unique for insertion and replacement: the full key tuple is not present, and insertion/replacement must still account for the missing key positions. That makes the extra state mostly descriptive rather than simplifying the mutation API.

For this reason, the proposal keeps the core classification simpler: Unique means every key position hit the same item; partial hits remain occupied but non-unique.

Possible extension: more precise occupied predicates

The proposal keeps the same top-level entry shape as BiHashMap:

Vacant   = no provided keys hit
Occupied = at least one provided key hit

Within Occupied, the current API exposes the essential distinction:

Unique    = every key position hit the same item
NonUnique = partial hits or mixed hits

If callers need more introspection later, this can be added without changing the core model. For example:

impl OccupiedEntry {
    pub fn is_partial(&self) -> bool;
    pub fn is_mixed(&self) -> bool;
    pub fn is_full_match(&self) -> bool;
}

These would be additive convenience predicates:

A / A / A          => full match, unique
A / A / None       => partial, non-unique
A / None / A       => partial, non-unique
A / A / B          => mixed, non-unique
A / B / C          => mixed, non-unique

This preserves the conservative core semantics while leaving room for more descriptive APIs if real callers need them.

Testing strategy

Use broad property-based tests (PBT) for:

* entry classification
* entry deduplication invariants
* existing overwrite / panic-safety behavior

Use targeted deterministic tests for new public TriHashMap Entry semantics, add TRI property-test operations for entry removal and occupied entry replacement, and continue relying on the existing overwrite, pathological, and panic-safety coverage for broad mutation behavior.

The implementation adds oracle-backed property-test operations for:

• TriHashMap::entry(...).insert(...) on occupied entries
• TriHashMap::entry(...).remove()

These compare the map against NaiveMap and preserve the documented first-key-hit return order rather than sorting returned items.

Use targeted bespoke tests for new public TriHashMap Entry semantics:

• vacant insert_entry returns unique
• A/A/A is unique
• A/A/None is occupied non-unique
• A/A/B shared access preserves per-key mapping
• A/A/B mutable access does not alias
• A/A/B remove removes each distinct item once
• A/A/B insert returns removed items in key order
• A/B/C insert returns removed items in key order
• overlap permutations such as A/B/A preserve per-key mapping and deduplicate visitor order
• partial duplicate-hit permutations such as A/None/A and None/A/A remain occupied non-unique
• non-unique and_modify visits each distinct item once, not once per key
• or_insert does not insert for partial or mixed occupied entries
• or_insert_with remains lazy for unique, partial, and mixed occupied entries
• removal / replacement order is tested where key-hit order differs from insertion or item-index order, such as None/B/A => [B, A]
• non-unique replacement rejects replacements whose distinct conflict set is the same but whose per-key lookup state differs
• public vacant insertion methods validate entry key hashes before mutation

Existing overwrite and panic-safety tests should continue to cover broad mutation behavior. New bespoke tests should focus on Entry-specific semantics and TriHashMap overlap cases.

Tests that remove or overwrite multiple items should use the existing non-compact validation expectation where appropriate, since removal can leave vacant ItemSet slots.

Non-goals

This proposal does not attempt to:

• introduce a generic public Entry API
• introduce a generic map backend
• change BiHashMap’s public enum field shape
• design an N-key hash map abstraction
• replace the existing prepared overwrite machinery

Implementation plan

1. Normalize hash helper naming

Use a consistent naming convention in both BiHashMap and TriHashMap:

// BiHashMap
make_hashes(&key1, &key2)
make_hashes_for_item(&item)

// TriHashMap
make_hashes(&key1, &key2, &key3)
make_hashes_for_item(&item)

make_hashes(...) should mean explicit entry keys. make_hashes_for_item(...) should mean keys derived from an item.

2. Extract a small shared entry-state primitive

Add crate-internal / hidden implementation support for the correctness-critical logic shared by BiHashMap and TriHashMap:

• per-key lookup classification
• vacant / unique / non-unique state
• per-key index preservation
• first-key-hit distinct-index deduplication
• key-position to distinct-slot mapping

It should not know about:

• BiHashMap / TriHashMap
• BiHashItem / TriHashItem
• RefMut
• DormantMutRef
• hash tables
• allocators
• public Entry APIs

The implementation should be small, pure, no_std compatible, and easy to test. It does not commit the crate to a generic public Entry framework.

From local experimentation, I expected this to look like:

support::entry::EntryLookup<I, const N: usize>
support::entry::EntryIndexes<I, const N: usize>
support::entry::DistinctEntryIndexes<I, const N: usize>

The generic index type I is not intended as a public abstraction. Production aliases use ItemIndex; I only keeps ItemIndex private while allowing integration tests to exercise the state machine with a simple test index type.

In the implementation, the shared primitive remains crate-internal and uses the crate’s existing ItemIndex directly:

support::entry::EntryLookup<const N: usize>
support::entry::EntryIndexes<const N: usize>
support::entry::NonUniqueIndexes<const N: usize>
support::entry::DistinctIndexes<const N: usize>

This keeps the implementation smaller and avoids introducing a generic index abstraction that is not needed by the current BiHashMap / TriHashMap internals.

3. Migrate BiHashMap internals to the shared primitive

This proves the shared state machine preserves existing BiHashMap semantics before TriHashMap builds on it.

This proposal does not require replacing BiHashMap’s public fields with accessor-only wrappers. BiHashMap’s current public field-shaped variants should remain unless a future semver-major cleanup intentionally changes them.

That means preserving existing public variants such as:

OccupiedEntryRef::NonUnique {
    by_key1,
    by_key2,
}

OccupiedEntryMut::NonUnique {
    by_key1,
    by_key2,
}

Internally, BiHashMap can use:

type EntryIndexes = support::entry::EntryIndexes<2>;
type EntryLookup = support::entry::EntryLookup<2>;

4. Implement TriHashMap Entry API separately

The public API should remain readable and TriHashMap-specific. It should mirror BiHashMap’s Entry capabilities where possible, but it should not copy BiHashMap’s mutable non-unique enum field layout.

This gives:

• feature parity with BiHashMap at the endpoint level
• a TriHashMap API that remains understandable as a three-key map
• no generic public arity framework

5. Use accessor-backed mutable non-unique views for TriHashMap

TriHashMap should use an accessor-backed NonUniqueEntryMut, as described above, to preserve per-key semantics without exposing aliased mutable references.

6. Reuse prepared overwrite machinery

Non-unique occupied Entry insertion should use the prepared overwrite path from the panic-safety work. Unique occupied replacement can use direct in-place replacement after validating that the replacement remains compatible with the stored entry hashes and key state.

In the implementation, occupied replacement uses the prepared replacement/validation path for both unique and non-unique occupied entries. This keeps the mutation path uniform and preserves the same validation and panic-safety structure.

For TriHashMap occupied insert:

1. Compute replacement hashes and duplicate indexes before mutation.
2. Validate replacement key hashes against the Entry’s stored hashes.
3. Validate prepared duplicate indexes against the Entry’s per-key lookup state.
4. Reserve commit capacity before mutation.
5. Remove each distinct conflicting item once.
6. Insert the replacement item.
7. Return removed items in deterministic first-key-hit order.

Return order should be independent of hash table order:

key1 conflict first
key2 conflict second, if distinct
key3 conflict third, if distinct

Examples:

A / A / B => [A, B]
A / B / A => [A, B]
A / B / C => [A, B, C]
None / B / A => [B, A]

Entry replacement must validate that the replacement is compatible with the entry state before mutation. In practice, this means validating replacement key hashes against the entry hashes and validating the prepared per-key duplicate indexes against the entry’s stored per-key lookup state. Occupied replacement goes through the same panic-safety path as insert_overwrite.

Reviewability and feasibility

I have implemented this shape in a draft PR. The branch is structured as a sequence of reviewable commits covering:

1. hash helper naming cleanup
2. shared entry-state primitive and tests
3. BiHashMap internal migration with public API compatibility preserved
4. TriHashMap read-only Entry API
5. TriHashMap mutable Entry views
6. TriHashMap occupied entry mutation
7. documentation and API hardening
8. entry debug-output cleanup
9. targeted repeated non-unique mapping coverage
10. TRI property-test coverage for entry remove and occupied entry replacement

The main correctness-sensitive review points are:

• the shared EntryIndexes classification and deduplication invariants
• BiHashMap behavior/source compatibility after the internal migration
• TriHashMap semantics for A/A/None, A/A/B, and A/B/A
• NonUniqueEntryMut aliasing prevention
• occupied Entry insertion paths: prepared validation/replacement for both unique and non-unique occupied entries
• first-key-hit return ordering for removal and replacement
• vacant insertion hash validation before mutation

AI assistance disclosure: I used ChatGPT (GPT-5.5 Thinking) throughout development of this proposal, preliminary implementation work, and local feasibility checks, including reasoning about the issue, drafting code and tests, and reviewing outputs.