strop_engine/keymap/
lookup.rs

1//! Table-derived dispatch trie and which-key index, compiled once.
2//! Querying dispatch never expands notation or allocates key sequences.
3
4use std::sync::LazyLock;
5
6use super::{Binding, BINDINGS, SECTIONS};
7
8/// Expand a row's notation into sequences of table tokens.
9pub fn expand(keys: &str) -> Vec<Vec<&str>> {
10    let toks: Vec<&str> = keys.split(' ').filter(|t| !t.is_empty()).collect();
11    let mut seqs: Vec<Vec<&str>> = Vec::new();
12    let mut i = 0;
13    while i < toks.len() {
14        match toks[i] {
15            "/" if seqs.is_empty() => seqs.push(vec!["/"]),
16            "/" => {
17                let base = match seqs.last() {
18                    Some(s) => s[..s.len() - 1].to_vec(),
19                    None => Vec::new(),
20                };
21                for alt in &toks[i + 1..] {
22                    if *alt != "/" {
23                        let mut seq = base.clone();
24                        seq.push(alt);
25                        seqs.push(seq);
26                    }
27                }
28                break;
29            }
30            "space" => {
31                let end = match (i + 1..toks.len()).find(|&j| toks[j] == "/" && j + 1 < toks.len())
32                {
33                    Some(end) => end,
34                    None => toks.len(),
35                };
36                seqs.push(toks[i..end].to_vec());
37                i = end;
38                continue;
39            }
40            "ctrl-w" => {
41                if let Some(k) = toks.get(i + 1) {
42                    seqs.push(vec!["ctrl-w", k]);
43                    i += 2;
44                } else {
45                    seqs.push(vec!["ctrl-w"]);
46                    i += 1;
47                }
48                continue;
49            }
50            t => seqs.push(vec![t]),
51        }
52        i += 1;
53    }
54    seqs
55}
56
57fn per_key(seq: &[&str]) -> Vec<String> {
58    let mut out = Vec::new();
59    for &t in seq {
60        if t.len() > 1 && !t.starts_with('<') && !t.starts_with(':') && !NAMED.contains(&t) {
61            if let Some(i) = t.find('<') {
62                out.extend(t[..i].chars().map(|c| c.to_string()));
63                out.push(t[i..].to_string());
64            } else {
65                out.extend(t.chars().map(|c| c.to_string()));
66            }
67        } else {
68            out.push(t.to_string());
69        }
70    }
71    out
72}
73
74pub(crate) const NAMED: &[&str] = &[
75    "space",
76    "ctrl-w",
77    "ctrl-o",
78    "ctrl-i",
79    "up",
80    "down",
81    "left",
82    "right",
83    "tab",
84    "s-tab",
85    "esc",
86    "enter",
87    "backspace",
88    "ctrl-r",
89    "ctrl-x",
90    "ctrl-d",
91    "ctrl-u",
92    "ctrl-f",
93    "ctrl-b",
94    "ctrl-^",
95    "ctrl-v",
96    "ctrl-l",
97];
98
99/// The single-key operator `<` is literal, not a placeholder.
100fn is_placeholder(k: &str) -> bool {
101    k.len() > 1 && k.starts_with('<')
102}
103
104#[derive(Clone, Copy)]
105struct NodeId(usize);
106
107const ROOT: NodeId = NodeId(0);
108
109#[derive(Default)]
110struct Node {
111    literals: Vec<(String, NodeId)>,
112    wildcard: Option<NodeId>,
113    row: Option<usize>,
114    // Strict descendants, not the node's own terminal row.
115    live_child: bool,
116}
117
118struct HintSequence {
119    row: usize,
120    tokens: Vec<&'static str>,
121    flat: String,
122    bounds: Vec<usize>,
123    char_len: usize,
124    weight: usize,
125}
126
127impl HintSequence {
128    fn new(row: usize, tokens: Vec<&'static str>) -> Self {
129        let mut flat = String::new();
130        let mut bounds = Vec::new();
131        let mut weight = 0;
132        for &t in &tokens {
133            bounds.push(flat.len());
134            let text = if t == "space" { " " } else { t };
135            flat.push_str(text);
136            weight += text.len();
137        }
138        let char_len = flat.chars().count();
139        Self {
140            row,
141            tokens,
142            flat,
143            bounds,
144            char_len,
145            weight,
146        }
147    }
148
149    // Preserve table-token hint boundaries (m<a> -> <a>, gg -> g),
150    // rather than displaying dispatch's per-key representation.
151    fn child_key(&self, prefix: &str, plen: usize) -> Option<String> {
152        if plen == 0 || !self.flat.starts_with(prefix) || self.char_len <= plen {
153            return None;
154        }
155        match self.bounds.iter().position(|&b| b == plen) {
156            Some(i) => Some(self.tokens[i].to_string()),
157            None => {
158                let i = self.bounds.iter().rposition(|&b| b < plen)?;
159                Some(self.tokens[i].chars().skip(plen - self.bounds[i]).collect())
160            }
161        }
162    }
163}
164
165struct Index {
166    nodes: Vec<Node>,
167    hints: Vec<HintSequence>,
168}
169
170static INDEX: LazyLock<Index> = LazyLock::new(Index::compile);
171
172impl Index {
173    fn compile() -> Self {
174        let mut index = Self {
175            nodes: vec![Node::default()],
176            hints: Vec::new(),
177        };
178        for (row, binding) in BINDINGS.iter().enumerate() {
179            for tokens in expand(binding.keys) {
180                if binding.live {
181                    index.insert(row, per_key(&tokens));
182                }
183                index.hints.push(HintSequence::new(row, tokens));
184            }
185        }
186        // Stable sorting preserves row and alternative order for equal weights.
187        index.hints.sort_by_key(|seq| seq.weight);
188        index
189    }
190
191    fn insert(&mut self, row: usize, keys: Vec<String>) {
192        let mut at = ROOT;
193        for key in keys {
194            self.nodes[at.0].live_child = true;
195            let wildcard = is_placeholder(&key);
196            let existing = if wildcard {
197                self.nodes[at.0].wildcard
198            } else {
199                self.nodes[at.0]
200                    .literals
201                    .iter()
202                    .find(|(literal, _)| literal == &key)
203                    .map(|(_, id)| *id)
204            };
205            at = match existing {
206                Some(id) => id,
207                None => {
208                    let id = NodeId(self.nodes.len());
209                    self.nodes.push(Node::default());
210                    if wildcard {
211                        self.nodes[at.0].wildcard = Some(id);
212                    } else {
213                        self.nodes[at.0].literals.push((key, id));
214                    }
215                    id
216                }
217            };
218        }
219        // Compilation follows table order, so the first terminal wins.
220        if self.nodes[at.0].row.is_none() {
221            self.nodes[at.0].row = Some(row);
222        }
223    }
224
225    fn literal_child(&self, at: NodeId, key: &str) -> Option<NodeId> {
226        self.nodes[at.0]
227            .literals
228            .iter()
229            .find(|(literal, _)| literal == key)
230            .map(|(_, id)| *id)
231    }
232
233    fn find(&self, at: NodeId, path: &[String]) -> Option<usize> {
234        let Some((key, rest)) = path.split_first() else {
235            return self.nodes[at.0].row;
236        };
237        let literal = self
238            .literal_child(at, key)
239            .and_then(|id| self.find(id, rest));
240        let wildcard = self.nodes[at.0].wildcard.and_then(|id| self.find(id, rest));
241        // A literal must not automatically outrank an earlier placeholder row.
242        match (literal, wildcard) {
243            (Some(a), Some(b)) => Some(a.min(b)),
244            (Some(a), None) => Some(a),
245            (None, b) => b,
246        }
247    }
248
249    fn has_child(&self, at: NodeId, path: &[String]) -> bool {
250        let Some((key, rest)) = path.split_first() else {
251            return self.nodes[at.0].live_child;
252        };
253        self.literal_child(at, key)
254            .is_some_and(|id| self.has_child(id, rest))
255            || self.nodes[at.0]
256                .wildcard
257                .is_some_and(|id| self.has_child(id, rest))
258    }
259}
260
261/// The first live table row completed by this path, including placeholders.
262pub fn find_row(path: &[String]) -> Option<&'static Binding> {
263    INDEX.find(ROOT, path).map(|row| &BINDINGS[row])
264}
265
266/// Whether a live sequence strictly extends this path.
267pub fn any_child(path: &[String]) -> bool {
268    INDEX.has_child(ROOT, path)
269}
270
271/// One which-key hint row: the next key after a pending prefix.
272pub struct Hint {
273    pub key: String,
274    pub desc: &'static str,
275    pub live: bool,
276}
277
278/// Mode-appropriate hints, including planned rows. Shortest sequences win;
279/// table order and then alternative order break ties.
280pub fn children_of(prefix: &str, mode: crate::editor::Mode) -> Vec<Hint> {
281    use crate::editor::Mode;
282    let sections: &[&str] = match mode {
283        Mode::Normal => &["normal", "leader", "git", "ex+panes"],
284        Mode::Visual | Mode::VisualLine | Mode::VisualBlock => &["visual"],
285        Mode::Insert => &[],
286    };
287    let mut out: Vec<Hint> = Vec::new();
288    let plen = prefix.chars().count();
289    for seq in &INDEX.hints {
290        let b = &BINDINGS[seq.row];
291        if !sections.contains(&b.section) {
292            continue;
293        }
294        if let Some(key) = seq.child_key(prefix, plen) {
295            if !out.iter().any(|hint| hint.key == key) {
296                out.push(Hint {
297                    key,
298                    desc: b.desc,
299                    live: b.live,
300                });
301            }
302        }
303    }
304    out
305}
306
307/// The vim-compatibility report, generated from the single binding table.
308pub fn compat_report() -> String {
309    let mut out = String::from(
310        "# Vim compatibility\n\nGenerated from the command table (`cargo test` pins freshness; \
311         STROP_REGEN=1 rewrites).\n`✓` ships exactly; `(soon)` is a planned slot.\n",
312    );
313    for section in SECTIONS {
314        out.push_str(&format!("\n## {section}\n\n"));
315        for b in BINDINGS.iter().filter(|b| b.section == *section) {
316            let mark = if b.live { "✓" } else { "·" };
317            let soon = if b.live { "" } else { " (soon)" };
318            out.push_str(&format!("- `{mark} {}` — {}{}\n", b.keys, b.desc, soon));
319        }
320    }
321    out
322}
323
324#[cfg(test)]
325mod index_tests {
326    use super::*;
327
328    #[test]
329    fn table_precedence_wins_over_literal_specificity() {
330        let mut index = Index {
331            nodes: vec![Node::default()],
332            hints: Vec::new(),
333        };
334        index.insert(1, vec!["g".into(), "<c>".into()]);
335        index.insert(3, vec!["g".into(), "x".into()]);
336        assert_eq!(index.find(ROOT, &["g".into(), "x".into()]), Some(1));
337        assert_eq!(index.find(ROOT, &["g".into(), "z".into()]), Some(1));
338        assert!(index.has_child(ROOT, &["g".into()]));
339        assert!(!index.has_child(ROOT, &["g".into(), "x".into()]));
340    }
341
342    #[test]
343    fn literals_and_longer_paths_keep_independent_terminals() {
344        let mut index = Index {
345            nodes: vec![Node::default()],
346            hints: Vec::new(),
347        };
348        index.insert(0, vec!["g".into(), "x".into()]);
349        index.insert(2, vec!["g".into(), "<c>".into()]);
350        index.insert(4, vec!["g".into(), "x".into(), "y".into()]);
351        assert_eq!(index.find(ROOT, &["g".into(), "x".into()]), Some(0));
352        assert_eq!(index.find(ROOT, &["g".into(), "z".into()]), Some(2));
353        assert!(index.has_child(ROOT, &["g".into(), "x".into()]));
354        assert_eq!(
355            index.find(ROOT, &["g".into(), "x".into(), "y".into()]),
356            Some(4)
357        );
358    }
359}
strop_engine/keymap/lookup.rs

strop_engine/keymap/
lookup.rs
