Struct KeymapTrie

Source

pub struct KeymapTrie { /* private fields */ }

Expand description

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

A plain value type: no locking, no layering. The KeymapRegistry keeps one per (layer, BindingMode) and merges them with Self::merge_over; callers build one directly to hand a whole layer to KeymapHandle::push_layer.

§Examples

use std::sync::Arc;
use lattice_grammar::{CommandId, CommandInvocation, SourceLocation};
use lattice_keymap::{BoundCommand, ChordPattern, KeymapLayer, KeymapTrie, LookupResult};
use lattice_protocol::KeyChord;

let bound = |id| Arc::new(BoundCommand::from_invocation(
    CommandInvocation::of(CommandId::new(id)),
    SourceLocation::synthetic("doc"),
    KeymapLayer::Builtin,
));
let lit = |c| ChordPattern::Literal(KeyChord::char(c));

let mut trie = KeymapTrie::new();
trie.insert(&[lit('g'), lit('g')], bound(1));             // gg
trie.insert(&[lit('f'), ChordPattern::CharLiteral], bound(2)); // f{char}

let k = KeyChord::char;
assert!(matches!(trie.lookup(&[k('g')]), LookupResult::Partial));
assert!(matches!(trie.lookup(&[k('g'), k('g')]), LookupResult::Bound { .. }));
assert!(matches!(trie.lookup(&[k('q')]), LookupResult::Unbound));
// The wildcard captures the typed char...
match trie.lookup(&[k('f'), k('x')]) {
    LookupResult::Bound { captured, .. } => assert_eq!(captured, vec!['x']),
    other => panic!("{other:?}"),
}
// ...but never a modified chord.
assert!(matches!(trie.lookup(&[k('f'), KeyChord::ctrl('x')]), LookupResult::Unbound));
assert_eq!(trie.binding_count(), 2);

Implementations§

Source §

impl KeymapTrie

Source

pub fn new() -> Self

Empty trie. Use insert to populate.

Source

pub fn insert(&mut self, path: &[ChordPattern], bound: Arc<BoundCommand>)

Register bound at the chord path path. Replaces any existing binding at the same path (last-bind-wins within a single trie / layer). Empty path is a no-op (no “bind nothing”).

Source

pub fn remove(&mut self, path: &[ChordPattern]) -> Option<Arc<BoundCommand>>

Remove the binding at path if present. Returns the dropped Arc<BoundCommand> for callers that want to surface “what was unbound” in echo messages. Does not prune empty intermediate nodes – a future bind at the same prefix should reuse them, and the wasted nodes are bounded by the trie’s lifetime.

Source

pub fn get(&self, path: &[ChordPattern]) -> Option<&Arc<BoundCommand>>

VM.4: the binding registered at EXACTLY path, if any.

Not Self::lookup, and the difference is why this exists. lookup answers “what does this sequence of PRESSED chords resolve to”, and falls back to the {char} wildcard when no exact child matches, so it can’t tell the registration [f, {char}] from [f, x], and it can’t be asked about a pattern path at all. The motion mirror needs “is this exact registration slot occupied”, which is a question about PATTERNS. Here a CharLiteral segment walks the wildcard slot and only that slot, never as a fallback.

Source

pub fn lookup(&self, chords: &[KeyChord]) -> LookupResult

Walk the input chord sequence and return what we found.

Lookup precedence at each depth: exact children match first; if absent, fall back to char_wildcard when the input chord is a bare printable char (no modifiers). Modifier-bearing chords (<C-x>) never match the wildcard – the wildcard’s job is “any single typed char” for marks / registers / find-char.

Source

pub fn walk_continuations<F>(&self, prefix: &[KeyChord], f: F)
where F: FnMut(&[ChordPattern], &Arc<BoundCommand>),

DK.4: walk every binding registered strictly BELOW prefix, invoking f with the SUFFIX path (the chords that follow prefix) and the binding at that path.

This is the subtree :describe-key renders when the chord it was asked about is a prefix rather than a binding — the answer “<C-c><C-x> is not bound” is true and useless, “it is a prefix with eight continuations” is the answer the user came for.

A binding sitting exactly AT prefix is not emitted; that is the Self::lookup answer and is reported separately.

O(subtree) walk. Telemetry path; never on the keystroke path.

Source

pub fn node_view(&self, prefix: &[KeyChord]) -> Option<NodeView>

WK.1: the immediate children of the node prefix names, as a NodeView. None when the prefix leaves the trie — which-key shows nothing for a chord the keymap does not know.

Distinct from Self::walk_continuations, which flattens the whole subtree for :describe-key. Which-key wants one row per next keystroke, so it needs depth one plus a count of what hangs off each child.

O(children + subtree) — the descendant counts walk each child’s subtree once. Runs on the actor thread after the idle delay, never on the keystroke path.

Source

pub fn merge_over(&mut self, other: &KeymapTrie)

Overlay other on top of self. other’s bindings win on conflict; the merge is structural so paths in other that don’t conflict simply add to self’s tree.

§Examples

use std::sync::Arc;
use lattice_grammar::{CommandId, CommandInvocation, SourceLocation};
use lattice_keymap::{BoundCommand, ChordPattern, KeymapLayer, KeymapTrie};
use lattice_protocol::KeyChord;

let bound = |id, layer| Arc::new(BoundCommand::from_invocation(
    CommandInvocation::of(CommandId::new(id)), SourceLocation::synthetic("doc"), layer,
));
let x = [ChordPattern::Literal(KeyChord::char('x'))];
let y = [ChordPattern::Literal(KeyChord::char('y'))];

let mut base = KeymapTrie::new();
base.insert(&x, bound(1, KeymapLayer::Builtin));
base.insert(&y, bound(2, KeymapLayer::Builtin));
let mut user = KeymapTrie::new();
user.insert(&x, bound(3, KeymapLayer::User));

base.merge_over(&user);
assert_eq!(base.get(&x).unwrap().layer, KeymapLayer::User); // overridden
assert_eq!(base.get(&y).unwrap().layer, KeymapLayer::Builtin); // kept

The registry’s layer-stack collapse calls this in priority order (lowest first) so the highest-priority layer’s bindings end up authoritative. See docs/dev/architecture/keymap-architecture.md §2 + §4 (layer-merge on write, not on read).

Source

pub fn binding_count(&self) -> usize

Number of terminal bindings in the trie. O(N) walk; useful for tests + registry telemetry, not on the hot path.

Source

pub fn walk_bindings<F>(&self, f: F)
where F: FnMut(&[ChordPattern], &Arc<BoundCommand>),

MARG.2 (2026-06-03): walk every terminal binding, invoking f with the chord path that reaches it and the Arc<BoundCommand> at that path. Used by the reverse-keymap-cache builder in KeymapRegistry to produce a command_name → Vec<KeyChord> map for the keybinding annotator (see docs/dev/architecture/marginalia.md §6).

Path slice is borrowed; the closure must capture-by- clone if it wants to retain the chord sequence. O(N) over the bound-chord count — same cost class as Self::binding_count, not on the hot path.