Module trie 

KeymapTrie – the lookup data structure the keymap registry consults on the keystroke path. Audit slice 8.b of the M3 refactor; see docs/dev/architecture/keymap-architecture.md for the design.

Shape

Each TrieNode carries:

• children: HashMap<KeyChord, TrieNode> – exact-match descents indexed by chord. gd’s second descent comes from children[KeyChord::char('d')].
• char_wildcard: Option<Box<TrieNode>> – “any single printable char” descent. Used for marks ('a), registers ("a), find-char (fX / FX / tX / TX), macro names (@a / qa). Subsumes today’s BindingMode::AfterMark / AfterRegister / AfterFindChar special-case states.
• binding: Option<Arc<BoundCommand>> – terminal binding at this depth, if any. Internal nodes hold None.

Lookup walks chord-by-chord. Exact children match wins; if absent, fall back to char_wildcard (capturing the matched char). Returns:

• Bound when the walk ends at a node with a terminal binding (and the input is exhausted).
• Partial when the walk ends at an internal node with no terminal but with children – caller waits for the next chord.
• Unbound when no descent matches at some point.

Performance

Lookup is O(prefix_length) HashMap lookups. With ~500 bindings per layer and chord depths of 1-3, the inner cost is two HashMap::get calls plus a few branches; bench keymap_trie_lookup_* rows in BENCHMARKS.md measure it. Allocation-free on the hot path – the Vec<char> of captured wildcards is built only when the path actually crosses a wildcard, which is rare.

Mutation

insert / remove / merge_over are off the hot path (registry construction, layer push/pop, :bind invocations). They take &mut self; the registry handle (slice 8.c) wraps the trie in Arc<ArcSwap<KeymapTrie>> so wait-free reads coexist with these &mut-bound mutations – the registry builds a new trie, swaps the cell, and the old trie drops once readers release their Arc.

Structs

BoundCommand

What the trie returns at a terminal node.

ChildView

WK.1: one immediate child of a trie node, as which-key sees it.

KeymapTrie

One layer’s worth of bindings, indexed for O(prefix_length) lookup.

NodeView

WK.1: the immediate children of the node a prefix names — which-key’s view of the trie, as distinct from :describe-key’s KeymapTrie::walk_continuations, which wants the whole subtree with provenance. Same trie, different questions.

Enums

ChordPattern

One element of a keymap registration path.

KeymapLayer

Where in the five-layer model (DESIGN.md §5.2.3) a binding originated. Higher value wins on cross-layer conflict; the trie itself doesn’t enforce this, the registry does at merge time.

LookupResult

Lookup outcome.