1mod binding;
2mod context;
3
4pub use binding::*;
5pub use context::*;
6
7use crate::{Action, AsKeystroke, Keystroke, is_no_action};
8use collections::{HashMap, HashSet};
9use smallvec::SmallVec;
10use std::any::TypeId;
11
12/// An opaque identifier of which version of the keymap is currently active.
13/// The keymap's version is changed whenever bindings are added or removed.
14#[derive(Copy, Clone, Eq, PartialEq, Default)]
15pub struct KeymapVersion(usize);
16
17/// A collection of key bindings for the user's application.
18#[derive(Default)]
19pub struct Keymap {
20 bindings: Vec<KeyBinding>,
21 binding_indices_by_action_id: HashMap<TypeId, SmallVec<[usize; 3]>>,
22 no_action_binding_indices: Vec<usize>,
23 version: KeymapVersion,
24}
25
26/// Index of a binding within a keymap.
27#[derive(Copy, Clone, Debug, Eq, PartialEq, Ord, PartialOrd)]
28pub struct BindingIndex(usize);
29
30impl Keymap {
31 /// Create a new keymap with the given bindings.
32 pub fn new(bindings: Vec<KeyBinding>) -> Self {
33 let mut this = Self::default();
34 this.add_bindings(bindings);
35 this
36 }
37
38 /// Get the current version of the keymap.
39 pub fn version(&self) -> KeymapVersion {
40 self.version
41 }
42
43 /// Add more bindings to the keymap.
44 pub fn add_bindings<T: IntoIterator<Item = KeyBinding>>(&mut self, bindings: T) {
45 for binding in bindings {
46 let action_id = binding.action().as_any().type_id();
47 if is_no_action(&*binding.action) {
48 self.no_action_binding_indices.push(self.bindings.len());
49 } else {
50 self.binding_indices_by_action_id
51 .entry(action_id)
52 .or_default()
53 .push(self.bindings.len());
54 }
55 self.bindings.push(binding);
56 }
57
58 self.version.0 += 1;
59 }
60
61 /// Reset this keymap to its initial state.
62 pub fn clear(&mut self) {
63 self.bindings.clear();
64 self.binding_indices_by_action_id.clear();
65 self.no_action_binding_indices.clear();
66 self.version.0 += 1;
67 }
68
69 /// Iterate over all bindings, in the order they were added.
70 pub fn bindings(&self) -> impl DoubleEndedIterator<Item = &KeyBinding> + ExactSizeIterator {
71 self.bindings.iter()
72 }
73
74 /// Iterate over all bindings for the given action, in the order they were added. For display,
75 /// the last binding should take precedence.
76 pub fn bindings_for_action<'a>(
77 &'a self,
78 action: &'a dyn Action,
79 ) -> impl 'a + DoubleEndedIterator<Item = &'a KeyBinding> {
80 let action_id = action.type_id();
81 let binding_indices = self
82 .binding_indices_by_action_id
83 .get(&action_id)
84 .map_or(&[] as _, SmallVec::as_slice)
85 .iter();
86
87 binding_indices.filter_map(|ix| {
88 let binding = &self.bindings[*ix];
89 if !binding.action().partial_eq(action) {
90 return None;
91 }
92
93 for null_ix in &self.no_action_binding_indices {
94 if null_ix > ix {
95 let null_binding = &self.bindings[*null_ix];
96 if null_binding.keystrokes == binding.keystrokes {
97 let null_binding_matches =
98 match (&null_binding.context_predicate, &binding.context_predicate) {
99 (None, _) => true,
100 (Some(_), None) => false,
101 (Some(null_predicate), Some(predicate)) => {
102 null_predicate.is_superset(predicate)
103 }
104 };
105 if null_binding_matches {
106 return None;
107 }
108 }
109 }
110 }
111
112 Some(binding)
113 })
114 }
115
116 /// Returns all bindings that might match the input without checking context. The bindings
117 /// returned in precedence order (reverse of the order they were added to the keymap).
118 pub fn all_bindings_for_input(&self, input: &[Keystroke]) -> Vec<KeyBinding> {
119 self.bindings()
120 .rev()
121 .filter_map(|binding| {
122 binding.match_keystrokes(input).filter(|pending| !pending)?;
123 Some(binding.clone())
124 })
125 .collect()
126 }
127
128 /// Returns a list of bindings that match the given input, and a boolean indicating whether or
129 /// not more bindings might match if the input was longer. Bindings are returned in precedence
130 /// order (higher precedence first, reverse of the order they were added to the keymap).
131 ///
132 /// Precedence is defined by the depth in the tree (matches on the Editor take precedence over
133 /// matches on the Pane, then the Workspace, etc.). Bindings with no context are treated as the
134 /// same as the deepest context.
135 ///
136 /// In the case of multiple bindings at the same depth, the ones added to the keymap later take
137 /// precedence. User bindings are added after built-in bindings so that they take precedence.
138 ///
139 /// If a user has disabled a binding with `"x": null` it will not be returned. Disabled bindings
140 /// are evaluated with the same precedence rules so you can disable a rule in a given context
141 /// only.
142 pub fn bindings_for_input(
143 &self,
144 input: &[impl AsKeystroke],
145 context_stack: &[KeyContext],
146 ) -> (SmallVec<[KeyBinding; 1]>, bool) {
147 let mut matched_bindings = SmallVec::<[(usize, BindingIndex, &KeyBinding); 1]>::new();
148 let mut pending_bindings = SmallVec::<[(BindingIndex, &KeyBinding); 1]>::new();
149
150 for (ix, binding) in self.bindings().enumerate().rev() {
151 let Some(depth) = self.binding_enabled(binding, context_stack) else {
152 continue;
153 };
154 let Some(pending) = binding.match_keystrokes(input) else {
155 continue;
156 };
157
158 if !pending {
159 matched_bindings.push((depth, BindingIndex(ix), binding));
160 } else {
161 pending_bindings.push((BindingIndex(ix), binding));
162 }
163 }
164
165 matched_bindings.sort_by(|(depth_a, ix_a, _), (depth_b, ix_b, _)| {
166 depth_b.cmp(depth_a).then(ix_b.cmp(ix_a))
167 });
168
169 let mut bindings: SmallVec<[_; 1]> = SmallVec::new();
170 let mut first_binding_index = None;
171 for (_, ix, binding) in matched_bindings {
172 if is_no_action(&*binding.action) {
173 break;
174 }
175 bindings.push(binding.clone());
176 first_binding_index.get_or_insert(ix);
177 }
178
179 let mut pending = HashSet::default();
180 for (ix, binding) in pending_bindings.into_iter().rev() {
181 if let Some(binding_ix) = first_binding_index
182 && binding_ix > ix
183 {
184 continue;
185 }
186 if is_no_action(&*binding.action) {
187 pending.remove(&&binding.keystrokes);
188 continue;
189 }
190 pending.insert(&binding.keystrokes);
191 }
192
193 (bindings, !pending.is_empty())
194 }
195 /// Check if the given binding is enabled, given a certain key context.
196 /// Returns the deepest depth at which the binding matches, or None if it doesn't match.
197 fn binding_enabled(&self, binding: &KeyBinding, contexts: &[KeyContext]) -> Option<usize> {
198 if let Some(predicate) = &binding.context_predicate {
199 predicate.depth_of(contexts)
200 } else {
201 Some(contexts.len())
202 }
203 }
204}
205
206#[cfg(test)]
207mod tests {
208 use super::*;
209 use crate as gpui;
210 use gpui::NoAction;
211
212 actions!(
213 test_only,
214 [ActionAlpha, ActionBeta, ActionGamma, ActionDelta,]
215 );
216
217 #[test]
218 fn test_keymap() {
219 let bindings = [
220 KeyBinding::new("ctrl-a", ActionAlpha {}, None),
221 KeyBinding::new("ctrl-a", ActionBeta {}, Some("pane")),
222 KeyBinding::new("ctrl-a", ActionGamma {}, Some("editor && mode==full")),
223 ];
224
225 let mut keymap = Keymap::default();
226 keymap.add_bindings(bindings.clone());
227
228 // global bindings are enabled in all contexts
229 assert_eq!(keymap.binding_enabled(&bindings[0], &[]), Some(0));
230 assert_eq!(
231 keymap.binding_enabled(&bindings[0], &[KeyContext::parse("terminal").unwrap()]),
232 Some(1)
233 );
234
235 // contextual bindings are enabled in contexts that match their predicate
236 assert_eq!(
237 keymap.binding_enabled(&bindings[1], &[KeyContext::parse("barf x=y").unwrap()]),
238 None
239 );
240 assert_eq!(
241 keymap.binding_enabled(&bindings[1], &[KeyContext::parse("pane x=y").unwrap()]),
242 Some(1)
243 );
244
245 assert_eq!(
246 keymap.binding_enabled(&bindings[2], &[KeyContext::parse("editor").unwrap()]),
247 None
248 );
249 assert_eq!(
250 keymap.binding_enabled(
251 &bindings[2],
252 &[KeyContext::parse("editor mode=full").unwrap()]
253 ),
254 Some(1)
255 );
256 }
257
258 #[test]
259 fn test_depth_precedence() {
260 let bindings = [
261 KeyBinding::new("ctrl-a", ActionBeta {}, Some("pane")),
262 KeyBinding::new("ctrl-a", ActionGamma {}, Some("editor")),
263 ];
264
265 let mut keymap = Keymap::default();
266 keymap.add_bindings(bindings);
267
268 let (result, pending) = keymap.bindings_for_input(
269 &[Keystroke::parse("ctrl-a").unwrap()],
270 &[
271 KeyContext::parse("pane").unwrap(),
272 KeyContext::parse("editor").unwrap(),
273 ],
274 );
275
276 assert!(!pending);
277 assert_eq!(result.len(), 2);
278 assert!(result[0].action.partial_eq(&ActionGamma {}));
279 assert!(result[1].action.partial_eq(&ActionBeta {}));
280 }
281
282 #[test]
283 fn test_keymap_disabled() {
284 let bindings = [
285 KeyBinding::new("ctrl-a", ActionAlpha {}, Some("editor")),
286 KeyBinding::new("ctrl-b", ActionAlpha {}, Some("editor")),
287 KeyBinding::new("ctrl-a", NoAction {}, Some("editor && mode==full")),
288 KeyBinding::new("ctrl-b", NoAction {}, None),
289 ];
290
291 let mut keymap = Keymap::default();
292 keymap.add_bindings(bindings);
293
294 // binding is only enabled in a specific context
295 assert!(
296 keymap
297 .bindings_for_input(
298 &[Keystroke::parse("ctrl-a").unwrap()],
299 &[KeyContext::parse("barf").unwrap()],
300 )
301 .0
302 .is_empty()
303 );
304 assert!(
305 !keymap
306 .bindings_for_input(
307 &[Keystroke::parse("ctrl-a").unwrap()],
308 &[KeyContext::parse("editor").unwrap()],
309 )
310 .0
311 .is_empty()
312 );
313
314 // binding is disabled in a more specific context
315 assert!(
316 keymap
317 .bindings_for_input(
318 &[Keystroke::parse("ctrl-a").unwrap()],
319 &[KeyContext::parse("editor mode=full").unwrap()],
320 )
321 .0
322 .is_empty()
323 );
324
325 // binding is globally disabled
326 assert!(
327 keymap
328 .bindings_for_input(
329 &[Keystroke::parse("ctrl-b").unwrap()],
330 &[KeyContext::parse("barf").unwrap()],
331 )
332 .0
333 .is_empty()
334 );
335 }
336
337 #[test]
338 /// Tests for https://github.com/zed-industries/zed/issues/30259
339 fn test_multiple_keystroke_binding_disabled() {
340 let bindings = [
341 KeyBinding::new("space w w", ActionAlpha {}, Some("workspace")),
342 KeyBinding::new("space w w", NoAction {}, Some("editor")),
343 ];
344
345 let mut keymap = Keymap::default();
346 keymap.add_bindings(bindings);
347
348 let space = || Keystroke::parse("space").unwrap();
349 let w = || Keystroke::parse("w").unwrap();
350
351 let space_w = [space(), w()];
352 let space_w_w = [space(), w(), w()];
353
354 let workspace_context = || [KeyContext::parse("workspace").unwrap()];
355
356 let editor_workspace_context = || {
357 [
358 KeyContext::parse("workspace").unwrap(),
359 KeyContext::parse("editor").unwrap(),
360 ]
361 };
362
363 // Ensure `space` results in pending input on the workspace, but not editor
364 let space_workspace = keymap.bindings_for_input(&[space()], &workspace_context());
365 assert!(space_workspace.0.is_empty());
366 assert!(space_workspace.1);
367
368 let space_editor = keymap.bindings_for_input(&[space()], &editor_workspace_context());
369 assert!(space_editor.0.is_empty());
370 assert!(!space_editor.1);
371
372 // Ensure `space w` results in pending input on the workspace, but not editor
373 let space_w_workspace = keymap.bindings_for_input(&space_w, &workspace_context());
374 assert!(space_w_workspace.0.is_empty());
375 assert!(space_w_workspace.1);
376
377 let space_w_editor = keymap.bindings_for_input(&space_w, &editor_workspace_context());
378 assert!(space_w_editor.0.is_empty());
379 assert!(!space_w_editor.1);
380
381 // Ensure `space w w` results in the binding in the workspace, but not in the editor
382 let space_w_w_workspace = keymap.bindings_for_input(&space_w_w, &workspace_context());
383 assert!(!space_w_w_workspace.0.is_empty());
384 assert!(!space_w_w_workspace.1);
385
386 let space_w_w_editor = keymap.bindings_for_input(&space_w_w, &editor_workspace_context());
387 assert!(space_w_w_editor.0.is_empty());
388 assert!(!space_w_w_editor.1);
389
390 // Now test what happens if we have another binding defined AFTER the NoAction
391 // that should result in pending
392 let bindings = [
393 KeyBinding::new("space w w", ActionAlpha {}, Some("workspace")),
394 KeyBinding::new("space w w", NoAction {}, Some("editor")),
395 KeyBinding::new("space w x", ActionAlpha {}, Some("editor")),
396 ];
397 let mut keymap = Keymap::default();
398 keymap.add_bindings(bindings);
399
400 let space_editor = keymap.bindings_for_input(&[space()], &editor_workspace_context());
401 assert!(space_editor.0.is_empty());
402 assert!(space_editor.1);
403
404 // Now test what happens if we have another binding defined BEFORE the NoAction
405 // that should result in pending
406 let bindings = [
407 KeyBinding::new("space w w", ActionAlpha {}, Some("workspace")),
408 KeyBinding::new("space w x", ActionAlpha {}, Some("editor")),
409 KeyBinding::new("space w w", NoAction {}, Some("editor")),
410 ];
411 let mut keymap = Keymap::default();
412 keymap.add_bindings(bindings);
413
414 let space_editor = keymap.bindings_for_input(&[space()], &editor_workspace_context());
415 assert!(space_editor.0.is_empty());
416 assert!(space_editor.1);
417
418 // Now test what happens if we have another binding defined at a higher context
419 // that should result in pending
420 let bindings = [
421 KeyBinding::new("space w w", ActionAlpha {}, Some("workspace")),
422 KeyBinding::new("space w x", ActionAlpha {}, Some("workspace")),
423 KeyBinding::new("space w w", NoAction {}, Some("editor")),
424 ];
425 let mut keymap = Keymap::default();
426 keymap.add_bindings(bindings);
427
428 let space_editor = keymap.bindings_for_input(&[space()], &editor_workspace_context());
429 assert!(space_editor.0.is_empty());
430 assert!(space_editor.1);
431 }
432
433 #[test]
434 fn test_override_multikey() {
435 let bindings = [
436 KeyBinding::new("ctrl-w left", ActionAlpha {}, Some("editor")),
437 KeyBinding::new("ctrl-w", NoAction {}, Some("editor")),
438 ];
439
440 let mut keymap = Keymap::default();
441 keymap.add_bindings(bindings);
442
443 // Ensure `space` results in pending input on the workspace, but not editor
444 let (result, pending) = keymap.bindings_for_input(
445 &[Keystroke::parse("ctrl-w").unwrap()],
446 &[KeyContext::parse("editor").unwrap()],
447 );
448 assert!(result.is_empty());
449 assert!(pending);
450
451 let bindings = [
452 KeyBinding::new("ctrl-w left", ActionAlpha {}, Some("editor")),
453 KeyBinding::new("ctrl-w", ActionBeta {}, Some("editor")),
454 ];
455
456 let mut keymap = Keymap::default();
457 keymap.add_bindings(bindings);
458
459 // Ensure `space` results in pending input on the workspace, but not editor
460 let (result, pending) = keymap.bindings_for_input(
461 &[Keystroke::parse("ctrl-w").unwrap()],
462 &[KeyContext::parse("editor").unwrap()],
463 );
464 assert_eq!(result.len(), 1);
465 assert!(!pending);
466 }
467
468 #[test]
469 fn test_simple_disable() {
470 let bindings = [
471 KeyBinding::new("ctrl-x", ActionAlpha {}, Some("editor")),
472 KeyBinding::new("ctrl-x", NoAction {}, Some("editor")),
473 ];
474
475 let mut keymap = Keymap::default();
476 keymap.add_bindings(bindings);
477
478 // Ensure `space` results in pending input on the workspace, but not editor
479 let (result, pending) = keymap.bindings_for_input(
480 &[Keystroke::parse("ctrl-x").unwrap()],
481 &[KeyContext::parse("editor").unwrap()],
482 );
483 assert!(result.is_empty());
484 assert!(!pending);
485 }
486
487 #[test]
488 fn test_fail_to_disable() {
489 // disabled at the wrong level
490 let bindings = [
491 KeyBinding::new("ctrl-x", ActionAlpha {}, Some("editor")),
492 KeyBinding::new("ctrl-x", NoAction {}, Some("workspace")),
493 ];
494
495 let mut keymap = Keymap::default();
496 keymap.add_bindings(bindings);
497
498 // Ensure `space` results in pending input on the workspace, but not editor
499 let (result, pending) = keymap.bindings_for_input(
500 &[Keystroke::parse("ctrl-x").unwrap()],
501 &[
502 KeyContext::parse("workspace").unwrap(),
503 KeyContext::parse("editor").unwrap(),
504 ],
505 );
506 assert_eq!(result.len(), 1);
507 assert!(!pending);
508 }
509
510 #[test]
511 fn test_disable_deeper() {
512 let bindings = [
513 KeyBinding::new("ctrl-x", ActionAlpha {}, Some("workspace")),
514 KeyBinding::new("ctrl-x", NoAction {}, Some("editor")),
515 ];
516
517 let mut keymap = Keymap::default();
518 keymap.add_bindings(bindings);
519
520 // Ensure `space` results in pending input on the workspace, but not editor
521 let (result, pending) = keymap.bindings_for_input(
522 &[Keystroke::parse("ctrl-x").unwrap()],
523 &[
524 KeyContext::parse("workspace").unwrap(),
525 KeyContext::parse("editor").unwrap(),
526 ],
527 );
528 assert_eq!(result.len(), 0);
529 assert!(!pending);
530 }
531
532 #[test]
533 fn test_pending_match_enabled() {
534 let bindings = [
535 KeyBinding::new("ctrl-x", ActionBeta, Some("vim_mode == normal")),
536 KeyBinding::new("ctrl-x 0", ActionAlpha, Some("Workspace")),
537 ];
538 let mut keymap = Keymap::default();
539 keymap.add_bindings(bindings);
540
541 let matched = keymap.bindings_for_input(
542 &[Keystroke::parse("ctrl-x")].map(Result::unwrap),
543 &[
544 KeyContext::parse("Workspace"),
545 KeyContext::parse("Pane"),
546 KeyContext::parse("Editor vim_mode=normal"),
547 ]
548 .map(Result::unwrap),
549 );
550 assert_eq!(matched.0.len(), 1);
551 assert!(matched.0[0].action.partial_eq(&ActionBeta));
552 assert!(matched.1);
553 }
554
555 #[test]
556 fn test_pending_match_enabled_extended() {
557 let bindings = [
558 KeyBinding::new("ctrl-x", ActionBeta, Some("vim_mode == normal")),
559 KeyBinding::new("ctrl-x 0", NoAction, Some("Workspace")),
560 ];
561 let mut keymap = Keymap::default();
562 keymap.add_bindings(bindings);
563
564 let matched = keymap.bindings_for_input(
565 &[Keystroke::parse("ctrl-x")].map(Result::unwrap),
566 &[
567 KeyContext::parse("Workspace"),
568 KeyContext::parse("Pane"),
569 KeyContext::parse("Editor vim_mode=normal"),
570 ]
571 .map(Result::unwrap),
572 );
573 assert_eq!(matched.0.len(), 1);
574 assert!(matched.0[0].action.partial_eq(&ActionBeta));
575 assert!(!matched.1);
576 let bindings = [
577 KeyBinding::new("ctrl-x", ActionBeta, Some("Workspace")),
578 KeyBinding::new("ctrl-x 0", NoAction, Some("vim_mode == normal")),
579 ];
580 let mut keymap = Keymap::default();
581 keymap.add_bindings(bindings);
582
583 let matched = keymap.bindings_for_input(
584 &[Keystroke::parse("ctrl-x")].map(Result::unwrap),
585 &[
586 KeyContext::parse("Workspace"),
587 KeyContext::parse("Pane"),
588 KeyContext::parse("Editor vim_mode=normal"),
589 ]
590 .map(Result::unwrap),
591 );
592 assert_eq!(matched.0.len(), 1);
593 assert!(matched.0[0].action.partial_eq(&ActionBeta));
594 assert!(!matched.1);
595 }
596
597 #[test]
598 fn test_overriding_prefix() {
599 let bindings = [
600 KeyBinding::new("ctrl-x 0", ActionAlpha, Some("Workspace")),
601 KeyBinding::new("ctrl-x", ActionBeta, Some("vim_mode == normal")),
602 ];
603 let mut keymap = Keymap::default();
604 keymap.add_bindings(bindings);
605
606 let matched = keymap.bindings_for_input(
607 &[Keystroke::parse("ctrl-x")].map(Result::unwrap),
608 &[
609 KeyContext::parse("Workspace"),
610 KeyContext::parse("Pane"),
611 KeyContext::parse("Editor vim_mode=normal"),
612 ]
613 .map(Result::unwrap),
614 );
615 assert_eq!(matched.0.len(), 1);
616 assert!(matched.0[0].action.partial_eq(&ActionBeta));
617 assert!(!matched.1);
618 }
619
620 #[test]
621 fn test_bindings_for_action() {
622 let bindings = [
623 KeyBinding::new("ctrl-a", ActionAlpha {}, Some("pane")),
624 KeyBinding::new("ctrl-b", ActionBeta {}, Some("editor && mode == full")),
625 KeyBinding::new("ctrl-c", ActionGamma {}, Some("workspace")),
626 KeyBinding::new("ctrl-a", NoAction {}, Some("pane && active")),
627 KeyBinding::new("ctrl-b", NoAction {}, Some("editor")),
628 ];
629
630 let mut keymap = Keymap::default();
631 keymap.add_bindings(bindings);
632
633 assert_bindings(&keymap, &ActionAlpha {}, &["ctrl-a"]);
634 assert_bindings(&keymap, &ActionBeta {}, &[]);
635 assert_bindings(&keymap, &ActionGamma {}, &["ctrl-c"]);
636
637 #[track_caller]
638 fn assert_bindings(keymap: &Keymap, action: &dyn Action, expected: &[&str]) {
639 let actual = keymap
640 .bindings_for_action(action)
641 .map(|binding| binding.keystrokes[0].inner().unparse())
642 .collect::<Vec<_>>();
643 assert_eq!(actual, expected, "{:?}", action);
644 }
645 }
646}