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

strop_engine/keymap/
lookup.rs
