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

strop_engine/keymap/
lookup.rs
