Krolyxon
Commit 8b10288

Branches

Tags

Refs →

remagesrcinputkeymap.rs

437 lines · 14.2 KB · Rust

Raw Blame History Download
1//! Per-mode key trie: pending sequences, counts and which-key candidates.
2
3use std::collections::BTreeMap;
4
5use super::keys::{Key, KeySeq};
6use crate::action::Action;
7use crate::state::Mode;
8
9/// Bindings from one config layer, in file order. `None` is `"none"`: remove the binding.
10pub type Bindings = Vec<(KeySeq, Option<Vec<Action>>)>;
11
12/// One layer's `[keys.*]` tables.
13#[derive(Clone, Debug, Default, PartialEq)]
14pub struct KeyTables {
15 pub global: Bindings,
16 pub image: Bindings,
17 pub grid: Bindings,
18 pub visual: Bindings,
19}
20
21/// A completed binding: the actions to run and the count typed before it.
22#[derive(Clone, Debug, PartialEq)]
23pub struct Run {
24 pub actions: Vec<Action>,
25 pub count: Option<usize>,
26}
27
28impl Run {
29 /// The actions with the count applied.
30 pub fn counted(self) -> Vec<Action> {
31 match self.count {
32 Some(n) => self.actions.into_iter().map(|a| a.with_count(n)).collect(),
33 None => self.actions,
34 }
35 }
36}
37
38/// A next key that would continue the pending sequence.
39#[derive(Clone, Debug, PartialEq)]
40pub struct Candidate {
41 pub key: Key,
42 pub actions: Option<Vec<Action>>,
43 /// Longer sequences continue through this key.
44 pub prefix: bool,
45}
46
47#[derive(Clone, Debug, Default)]
48struct Node {
49 actions: Option<Vec<Action>>,
50 children: BTreeMap<Key, Node>,
51}
52
53impl Node {
54 fn walk(&self, keys: &[Key]) -> Option<&Node> {
55 keys.iter().try_fold(self, |n, k| n.children.get(k))
56 }
57
58 fn insert(&mut self, keys: &[Key], actions: Vec<Action>) {
59 let node = keys
60 .iter()
61 .fold(self, |n, k| n.children.entry(*k).or_default());
62 node.actions = Some(actions);
63 }
64
65 fn collect(&self, prefix: &mut Vec<Key>, out: &mut Vec<(KeySeq, Vec<Action>)>) {
66 if let Some(a) = &self.actions {
67 out.push((KeySeq(prefix.clone()), a.clone()));
68 }
69 for (k, child) in &self.children {
70 prefix.push(*k);
71 child.collect(prefix, out);
72 prefix.pop();
73 }
74 }
75}
76
77/// Largest count accepted; more digits are ignored.
78const MAX_COUNT: usize = 9_999_999;
79
80#[derive(Clone, Debug, Default)]
81pub struct Keymap {
82 /// Image, grid, visual.
83 tries: [Node; 3],
84 pending: Vec<Key>,
85 count: Option<usize>,
86}
87
88fn idx(mode: Mode) -> usize {
89 match mode {
90 Mode::Image => 0,
91 Mode::Grid => 1,
92 Mode::Visual => 2,
93 }
94}
95
96impl Keymap {
97 /// Build from config layers, lowest priority first. Within each mode the levels stack
98 /// global < mode (< visual for visual mode, which sits on grid); later layers win inside a
99 /// level, and `"none"` removes whatever a lower level bound.
100 pub fn new(layers: &[&KeyTables]) -> Self {
101 type Level = fn(&KeyTables) -> &Bindings;
102 let global: Level = |t| &t.global;
103 let image: Level = |t| &t.image;
104 let grid: Level = |t| &t.grid;
105 let visual: Level = |t| &t.visual;
106 let chains: [&[Level]; 3] = [&[global, image], &[global, grid], &[global, grid, visual]];
107 let mut km = Keymap::default();
108 for (trie, chain) in km.tries.iter_mut().zip(chains) {
109 let mut flat: BTreeMap<&KeySeq, &Vec<Action>> = BTreeMap::new();
110 for level in chain {
111 let mut merged: BTreeMap<&KeySeq, Option<&Vec<Action>>> = BTreeMap::new();
112 for layer in layers {
113 for (k, v) in level(layer) {
114 merged.insert(k, v.as_ref());
115 }
116 }
117 for (k, v) in merged {
118 match v {
119 Some(a) => flat.insert(k, a),
120 None => flat.remove(k),
121 };
122 }
123 }
124 for (k, a) in flat {
125 trie.insert(&k.0, a.clone());
126 }
127 }
128 km
129 }
130
131 fn root(&self, mode: Mode) -> &Node {
132 &self.tries[idx(mode)]
133 }
134
135 /// Feed one key press. Returns the bindings it completed (usually none or one; an
136 /// ambiguous prefix followed by a non-continuing key yields the prefix's binding first).
137 pub fn feed(&mut self, mode: Mode, key: Key) -> Vec<Run> {
138 if self.pending.is_empty()
139 && let Some(d) = key.digit()
140 && (d != 0 || self.count.is_some())
141 {
142 let c = self.count.unwrap_or(0).saturating_mul(10) + d as usize;
143 self.count = Some(c.min(MAX_COUNT));
144 return Vec::new();
145 }
146 self.pending.push(key);
147 match self.root(mode).walk(&self.pending) {
148 Some(node) if node.children.is_empty() => {
149 let actions = node.actions.clone().unwrap_or_default();
150 self.pending.clear();
151 vec![Run {
152 actions,
153 count: self.count.take(),
154 }]
155 }
156 Some(_) => Vec::new(),
157 None => {
158 self.pending.pop();
159 let prefix = self
160 .root(mode)
161 .walk(&self.pending)
162 .and_then(|n| n.actions.clone())
163 .filter(|_| !self.pending.is_empty());
164 self.pending.clear();
165 match prefix {
166 // `g` is bound and so is `gg`: `gx` runs `g`, then `x` on its own.
167 Some(actions) => {
168 let mut out = vec![Run {
169 actions,
170 count: self.count.take(),
171 }];
172 out.extend(self.feed(mode, key));
173 out
174 }
175 None => {
176 self.count = None;
177 Vec::new()
178 }
179 }
180 }
181 }
182 }
183
184 /// The pending sequence is itself bound and also a prefix of longer ones.
185 pub fn is_ambiguous(&self, mode: Mode) -> bool {
186 !self.pending.is_empty()
187 && self
188 .root(mode)
189 .walk(&self.pending)
190 .is_some_and(|n| n.actions.is_some() && !n.children.is_empty())
191 }
192
193 /// The user stopped typing: an ambiguous sequence runs its own binding.
194 pub fn timeout(&mut self, mode: Mode) -> Vec<Run> {
195 if !self.is_ambiguous(mode) {
196 return Vec::new();
197 }
198 let actions = self
199 .root(mode)
200 .walk(&self.pending)
201 .and_then(|n| n.actions.clone())
202 .unwrap_or_default();
203 self.pending.clear();
204 vec![Run {
205 actions,
206 count: self.count.take(),
207 }]
208 }
209
210 /// A key sequence (not a count) is waiting for more keys.
211 pub fn is_pending(&self) -> bool {
212 !self.pending.is_empty()
213 }
214
215 /// The keys of the pending sequence.
216 pub fn pending_keys(&self) -> &[Key] {
217 &self.pending
218 }
219
220 pub fn cancel(&mut self) {
221 self.pending.clear();
222 self.count = None;
223 }
224
225 /// The count and keys typed so far, for the status bar.
226 pub fn pending_display(&self) -> String {
227 let mut s = self.count.map(|c| c.to_string()).unwrap_or_default();
228 if !self.pending.is_empty() {
229 s.push_str(&KeySeq(self.pending.clone()).to_string());
230 }
231 s
232 }
233
234 /// The binding of a complete sequence (mouse buttons and the wheel bypass the trie).
235 pub fn lookup(&self, mode: Mode, keys: &[Key]) -> Option<&[Action]> {
236 self.root(mode).walk(keys)?.actions.as_deref()
237 }
238
239 /// The keys that continue the pending sequence, for which-key.
240 pub fn candidates(&self, mode: Mode) -> Vec<Candidate> {
241 let Some(node) = self.root(mode).walk(&self.pending) else {
242 return Vec::new();
243 };
244 node.children
245 .iter()
246 .map(|(k, n)| Candidate {
247 key: *k,
248 actions: n.actions.clone(),
249 prefix: !n.children.is_empty(),
250 })
251 .collect()
252 }
253
254 /// Every binding in a mode, in key order.
255 pub fn bindings(&self, mode: Mode) -> Vec<(KeySeq, Vec<Action>)> {
256 let mut out = Vec::new();
257 self.root(mode).collect(&mut Vec::new(), &mut out);
258 out
259 }
260
261 /// The sequences bound to exactly `action` in a mode, shortest first.
262 pub fn keys_for(&self, mode: Mode, action: &Action) -> Vec<KeySeq> {
263 let mut keys: Vec<KeySeq> = self
264 .bindings(mode)
265 .into_iter()
266 .filter(|(_, a)| a.len() == 1 && a[0] == *action)
267 .map(|(k, _)| k)
268 .collect();
269 keys.sort_by_key(|k| k.0.len());
270 keys
271 }
272}
273
274#[cfg(test)]
275mod tests {
276 use super::*;
277 use crate::action::Zoom;
278
279 fn bind(pairs: &[(&str, &str)]) -> Bindings {
280 pairs
281 .iter()
282 .map(|(k, a)| {
283 let actions = (*a != "none").then(|| vec![a.parse().unwrap()]);
284 (k.parse().unwrap(), actions)
285 })
286 .collect()
287 }
288
289 fn keys(s: &str) -> Vec<Key> {
290 s.parse::<KeySeq>().unwrap().0
291 }
292
293 /// Feed a whole string and collect the counted actions.
294 fn type_(km: &mut Keymap, mode: Mode, s: &str) -> Vec<Action> {
295 keys(s)
296 .into_iter()
297 .flat_map(|k| km.feed(mode, k))
298 .flat_map(Run::counted)
299 .collect()
300 }
301
302 fn defaults() -> KeyTables {
303 KeyTables {
304 global: bind(&[
305 ("n", "next"),
306 ("gg", "first"),
307 ("G", "last"),
308 ("q", "quit"),
309 ("0", "first"),
310 ("<Space>w", "run wallpaper"),
311 ("<Space>c", "run copy"),
312 ]),
313 image: bind(&[("+", "zoom in"), ("h", "pan left")]),
314 grid: bind(&[("h", "prev"), ("v", "visual")]),
315 visual: bind(&[("m", "mark-all")]),
316 }
317 }
318
319 #[test]
320 fn sequences_and_counts() {
321 let t = defaults();
322 let mut km = Keymap::new(&[&t]);
323 let m = Mode::Image;
324 assert_eq!(type_(&mut km, m, "n"), [Action::Next(1)]);
325 assert_eq!(type_(&mut km, m, "g"), []);
326 assert_eq!(km.pending_display(), "g");
327 assert_eq!(type_(&mut km, m, "g"), [Action::First]);
328 assert_eq!(type_(&mut km, m, "12G"), [Action::Goto(12)]);
329 assert_eq!(type_(&mut km, m, "5gg"), [Action::Goto(5)]);
330 assert_eq!(type_(&mut km, m, "3n"), [Action::Next(3)]);
331 assert_eq!(type_(&mut km, m, "3+"), [Action::Zoom(Zoom::In(3))]);
332 // `0` is a key unless a count is pending.
333 assert_eq!(type_(&mut km, m, "0"), [Action::First]);
334 assert_eq!(type_(&mut km, m, "10n"), [Action::Next(10)]);
335 assert_eq!(km.pending_display(), "");
336 }
337
338 #[test]
339 fn broken_sequences_are_dropped() {
340 let t = defaults();
341 let mut km = Keymap::new(&[&t]);
342 let m = Mode::Image;
343 assert_eq!(type_(&mut km, m, "5gx"), []);
344 assert!(!km.is_pending());
345 assert_eq!(km.pending_display(), "");
346 assert_eq!(type_(&mut km, m, "<Space>"), []);
347 assert_eq!(type_(&mut km, m, "<Esc>"), []);
348 assert_eq!(type_(&mut km, m, "n"), [Action::Next(1)]);
349 assert_eq!(type_(&mut km, m, "Z"), []);
350 }
351
352 #[test]
353 fn modes_override_global() {
354 let t = defaults();
355 let mut km = Keymap::new(&[&t]);
356 assert_eq!(
357 type_(&mut km, Mode::Image, "h"),
358 [Action::Pan(crate::state::view::Dir::Left)]
359 );
360 assert_eq!(type_(&mut km, Mode::Grid, "h"), [Action::Prev(1)]);
361 // Visual sits on grid.
362 assert_eq!(type_(&mut km, Mode::Visual, "h"), [Action::Prev(1)]);
363 assert_eq!(type_(&mut km, Mode::Visual, "m"), [Action::MarkAll]);
364 assert_eq!(type_(&mut km, Mode::Grid, "m"), []);
365 }
366
367 #[test]
368 fn later_layers_win_and_none_removes() {
369 let base = defaults();
370 let user = KeyTables {
371 global: bind(&[("n", "prev"), ("q", "none")]),
372 image: bind(&[("+", "none"), ("G", "none")]),
373 ..Default::default()
374 };
375 let mut km = Keymap::new(&[&base, &user]);
376 assert_eq!(type_(&mut km, Mode::Image, "n"), [Action::Prev(1)]);
377 assert_eq!(type_(&mut km, Mode::Image, "q"), []);
378 assert_eq!(type_(&mut km, Mode::Image, "+"), []);
379 // A mode's "none" masks the global binding in that mode only.
380 assert_eq!(type_(&mut km, Mode::Image, "G"), []);
381 assert_eq!(type_(&mut km, Mode::Grid, "G"), [Action::Last]);
382 }
383
384 #[test]
385 fn ambiguous_prefix_waits_then_resolves() {
386 let t = KeyTables {
387 global: bind(&[("g", "first"), ("gg", "last"), ("n", "next")]),
388 ..Default::default()
389 };
390 let mut km = Keymap::new(&[&t]);
391 let m = Mode::Image;
392 assert_eq!(type_(&mut km, m, "g"), []);
393 assert!(km.is_ambiguous(m));
394 assert_eq!(type_(&mut km, m, "g"), [Action::Last]);
395 // A non-continuing key runs the prefix, then itself.
396 assert_eq!(type_(&mut km, m, "gn"), [Action::First, Action::Next(1)]);
397 type_(&mut km, m, "4g");
398 let fired: Vec<Action> = km.timeout(m).into_iter().flat_map(Run::counted).collect();
399 assert_eq!(fired, [Action::Goto(4)]);
400 assert!(!km.is_pending());
401 }
402
403 #[test]
404 fn which_key_candidates() {
405 let t = defaults();
406 let mut km = Keymap::new(&[&t]);
407 type_(&mut km, Mode::Image, "<Space>");
408 let c = km.candidates(Mode::Image);
409 assert_eq!(c.len(), 2);
410 assert_eq!(c[0].key, Key::plain('c'));
411 assert_eq!(c[0].actions, Some(vec![Action::Run("copy".into())]));
412 assert!(!c[0].prefix);
413 km.cancel();
414 let root = km.candidates(Mode::Image);
415 assert!(root.iter().any(|c| c.key == Key::plain('g') && c.prefix));
416 }
417
418 #[test]
419 fn lookup_and_reverse_lookup() {
420 let t = defaults();
421 let km = Keymap::new(&[&t]);
422 assert_eq!(
423 km.lookup(Mode::Image, &keys("n")),
424 Some(&[Action::Next(1)][..])
425 );
426 assert_eq!(km.lookup(Mode::Image, &keys("g")), None);
427 assert_eq!(
428 km.keys_for(Mode::Image, &Action::First),
429 vec!["0".parse().unwrap(), "gg".parse().unwrap()]
430 );
431 assert!(
432 km.bindings(Mode::Grid)
433 .iter()
434 .any(|(k, _)| k.to_string() == "v")
435 );
436 }
437}