1mod binding;
2mod context;
3
4pub use binding::*;
5pub use context::*;
6
7use crate::{Action, 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: &[Keystroke],
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
196 /// Check if the given binding is enabled, given a certain key context.
197 /// Returns the deepest depth at which the binding matches, or None if it doesn't match.
198 fn binding_enabled(&self, binding: &KeyBinding, contexts: &[KeyContext]) -> Option<usize> {
199 if let Some(predicate) = &binding.context_predicate {
200 predicate.depth_of(contexts)
201 } else {
202 Some(contexts.len())
203 }
204 }
205}
206
207#[cfg(test)]
208mod tests {
209 use super::*;
210 use crate as gpui;
211 use gpui::NoAction;
212
213 actions!(
214 test_only,
215 [ActionAlpha, ActionBeta, ActionGamma, ActionDelta,]
216 );
217
218 #[test]
219 fn test_keymap() {
220 let bindings = [
221 KeyBinding::new("ctrl-a", ActionAlpha {}, None),
222 KeyBinding::new("ctrl-a", ActionBeta {}, Some("pane")),
223 KeyBinding::new("ctrl-a", ActionGamma {}, Some("editor && mode==full")),
224 ];
225
226 let mut keymap = Keymap::default();
227 keymap.add_bindings(bindings.clone());
228
229 // global bindings are enabled in all contexts
230 assert_eq!(keymap.binding_enabled(&bindings[0], &[]), Some(0));
231 assert_eq!(
232 keymap.binding_enabled(&bindings[0], &[KeyContext::parse("terminal").unwrap()]),
233 Some(1)
234 );
235
236 // contextual bindings are enabled in contexts that match their predicate
237 assert_eq!(
238 keymap.binding_enabled(&bindings[1], &[KeyContext::parse("barf x=y").unwrap()]),
239 None
240 );
241 assert_eq!(
242 keymap.binding_enabled(&bindings[1], &[KeyContext::parse("pane x=y").unwrap()]),
243 Some(1)
244 );
245
246 assert_eq!(
247 keymap.binding_enabled(&bindings[2], &[KeyContext::parse("editor").unwrap()]),
248 None
249 );
250 assert_eq!(
251 keymap.binding_enabled(
252 &bindings[2],
253 &[KeyContext::parse("editor mode=full").unwrap()]
254 ),
255 Some(1)
256 );
257 }
258
259 #[test]
260 fn test_depth_precedence() {
261 let bindings = [
262 KeyBinding::new("ctrl-a", ActionBeta {}, Some("pane")),
263 KeyBinding::new("ctrl-a", ActionGamma {}, Some("editor")),
264 ];
265
266 let mut keymap = Keymap::default();
267 keymap.add_bindings(bindings);
268
269 let (result, pending) = keymap.bindings_for_input(
270 &[Keystroke::parse("ctrl-a").unwrap()],
271 &[
272 KeyContext::parse("pane").unwrap(),
273 KeyContext::parse("editor").unwrap(),
274 ],
275 );
276
277 assert!(!pending);
278 assert_eq!(result.len(), 2);
279 assert!(result[0].action.partial_eq(&ActionGamma {}));
280 assert!(result[1].action.partial_eq(&ActionBeta {}));
281 }
282
283 #[test]
284 fn test_keymap_disabled() {
285 let bindings = [
286 KeyBinding::new("ctrl-a", ActionAlpha {}, Some("editor")),
287 KeyBinding::new("ctrl-b", ActionAlpha {}, Some("editor")),
288 KeyBinding::new("ctrl-a", NoAction {}, Some("editor && mode==full")),
289 KeyBinding::new("ctrl-b", NoAction {}, None),
290 ];
291
292 let mut keymap = Keymap::default();
293 keymap.add_bindings(bindings);
294
295 // binding is only enabled in a specific context
296 assert!(
297 keymap
298 .bindings_for_input(
299 &[Keystroke::parse("ctrl-a").unwrap()],
300 &[KeyContext::parse("barf").unwrap()],
301 )
302 .0
303 .is_empty()
304 );
305 assert!(
306 !keymap
307 .bindings_for_input(
308 &[Keystroke::parse("ctrl-a").unwrap()],
309 &[KeyContext::parse("editor").unwrap()],
310 )
311 .0
312 .is_empty()
313 );
314
315 // binding is disabled in a more specific context
316 assert!(
317 keymap
318 .bindings_for_input(
319 &[Keystroke::parse("ctrl-a").unwrap()],
320 &[KeyContext::parse("editor mode=full").unwrap()],
321 )
322 .0
323 .is_empty()
324 );
325
326 // binding is globally disabled
327 assert!(
328 keymap
329 .bindings_for_input(
330 &[Keystroke::parse("ctrl-b").unwrap()],
331 &[KeyContext::parse("barf").unwrap()],
332 )
333 .0
334 .is_empty()
335 );
336 }
337
338 #[test]
339 /// Tests for https://github.com/zed-industries/zed/issues/30259
340 fn test_multiple_keystroke_binding_disabled() {
341 let bindings = [
342 KeyBinding::new("space w w", ActionAlpha {}, Some("workspace")),
343 KeyBinding::new("space w w", NoAction {}, Some("editor")),
344 ];
345
346 let mut keymap = Keymap::default();
347 keymap.add_bindings(bindings);
348
349 let space = || Keystroke::parse("space").unwrap();
350 let w = || Keystroke::parse("w").unwrap();
351
352 let space_w = [space(), w()];
353 let space_w_w = [space(), w(), w()];
354
355 let workspace_context = || [KeyContext::parse("workspace").unwrap()];
356
357 let editor_workspace_context = || {
358 [
359 KeyContext::parse("workspace").unwrap(),
360 KeyContext::parse("editor").unwrap(),
361 ]
362 };
363
364 // Ensure `space` results in pending input on the workspace, but not editor
365 let space_workspace = keymap.bindings_for_input(&[space()], &workspace_context());
366 assert!(space_workspace.0.is_empty());
367 assert!(space_workspace.1);
368
369 let space_editor = keymap.bindings_for_input(&[space()], &editor_workspace_context());
370 assert!(space_editor.0.is_empty());
371 assert!(!space_editor.1);
372
373 // Ensure `space w` results in pending input on the workspace, but not editor
374 let space_w_workspace = keymap.bindings_for_input(&space_w, &workspace_context());
375 assert!(space_w_workspace.0.is_empty());
376 assert!(space_w_workspace.1);
377
378 let space_w_editor = keymap.bindings_for_input(&space_w, &editor_workspace_context());
379 assert!(space_w_editor.0.is_empty());
380 assert!(!space_w_editor.1);
381
382 // Ensure `space w w` results in the binding in the workspace, but not in the editor
383 let space_w_w_workspace = keymap.bindings_for_input(&space_w_w, &workspace_context());
384 assert!(!space_w_w_workspace.0.is_empty());
385 assert!(!space_w_w_workspace.1);
386
387 let space_w_w_editor = keymap.bindings_for_input(&space_w_w, &editor_workspace_context());
388 assert!(space_w_w_editor.0.is_empty());
389 assert!(!space_w_w_editor.1);
390
391 // Now test what happens if we have another binding defined AFTER the NoAction
392 // that should result in pending
393 let bindings = [
394 KeyBinding::new("space w w", ActionAlpha {}, Some("workspace")),
395 KeyBinding::new("space w w", NoAction {}, Some("editor")),
396 KeyBinding::new("space w x", ActionAlpha {}, Some("editor")),
397 ];
398 let mut keymap = Keymap::default();
399 keymap.add_bindings(bindings);
400
401 let space_editor = keymap.bindings_for_input(&[space()], &editor_workspace_context());
402 assert!(space_editor.0.is_empty());
403 assert!(space_editor.1);
404
405 // Now test what happens if we have another binding defined BEFORE the NoAction
406 // that should result in pending
407 let bindings = [
408 KeyBinding::new("space w w", ActionAlpha {}, Some("workspace")),
409 KeyBinding::new("space w x", ActionAlpha {}, Some("editor")),
410 KeyBinding::new("space w w", NoAction {}, Some("editor")),
411 ];
412 let mut keymap = Keymap::default();
413 keymap.add_bindings(bindings);
414
415 let space_editor = keymap.bindings_for_input(&[space()], &editor_workspace_context());
416 assert!(space_editor.0.is_empty());
417 assert!(space_editor.1);
418
419 // Now test what happens if we have another binding defined at a higher context
420 // that should result in pending
421 let bindings = [
422 KeyBinding::new("space w w", ActionAlpha {}, Some("workspace")),
423 KeyBinding::new("space w x", ActionAlpha {}, Some("workspace")),
424 KeyBinding::new("space w w", NoAction {}, Some("editor")),
425 ];
426 let mut keymap = Keymap::default();
427 keymap.add_bindings(bindings);
428
429 let space_editor = keymap.bindings_for_input(&[space()], &editor_workspace_context());
430 assert!(space_editor.0.is_empty());
431 assert!(space_editor.1);
432 }
433
434 #[test]
435 fn test_override_multikey() {
436 let bindings = [
437 KeyBinding::new("ctrl-w left", ActionAlpha {}, Some("editor")),
438 KeyBinding::new("ctrl-w", NoAction {}, Some("editor")),
439 ];
440
441 let mut keymap = Keymap::default();
442 keymap.add_bindings(bindings);
443
444 // Ensure `space` results in pending input on the workspace, but not editor
445 let (result, pending) = keymap.bindings_for_input(
446 &[Keystroke::parse("ctrl-w").unwrap()],
447 &[KeyContext::parse("editor").unwrap()],
448 );
449 assert!(result.is_empty());
450 assert!(pending);
451
452 let bindings = [
453 KeyBinding::new("ctrl-w left", ActionAlpha {}, Some("editor")),
454 KeyBinding::new("ctrl-w", ActionBeta {}, Some("editor")),
455 ];
456
457 let mut keymap = Keymap::default();
458 keymap.add_bindings(bindings);
459
460 // Ensure `space` results in pending input on the workspace, but not editor
461 let (result, pending) = keymap.bindings_for_input(
462 &[Keystroke::parse("ctrl-w").unwrap()],
463 &[KeyContext::parse("editor").unwrap()],
464 );
465 assert_eq!(result.len(), 1);
466 assert!(!pending);
467 }
468
469 #[test]
470 fn test_simple_disable() {
471 let bindings = [
472 KeyBinding::new("ctrl-x", ActionAlpha {}, Some("editor")),
473 KeyBinding::new("ctrl-x", NoAction {}, Some("editor")),
474 ];
475
476 let mut keymap = Keymap::default();
477 keymap.add_bindings(bindings);
478
479 // Ensure `space` results in pending input on the workspace, but not editor
480 let (result, pending) = keymap.bindings_for_input(
481 &[Keystroke::parse("ctrl-x").unwrap()],
482 &[KeyContext::parse("editor").unwrap()],
483 );
484 assert!(result.is_empty());
485 assert!(!pending);
486 }
487
488 #[test]
489 fn test_fail_to_disable() {
490 // disabled at the wrong level
491 let bindings = [
492 KeyBinding::new("ctrl-x", ActionAlpha {}, Some("editor")),
493 KeyBinding::new("ctrl-x", NoAction {}, Some("workspace")),
494 ];
495
496 let mut keymap = Keymap::default();
497 keymap.add_bindings(bindings);
498
499 // Ensure `space` results in pending input on the workspace, but not editor
500 let (result, pending) = keymap.bindings_for_input(
501 &[Keystroke::parse("ctrl-x").unwrap()],
502 &[
503 KeyContext::parse("workspace").unwrap(),
504 KeyContext::parse("editor").unwrap(),
505 ],
506 );
507 assert_eq!(result.len(), 1);
508 assert!(!pending);
509 }
510
511 #[test]
512 fn test_disable_deeper() {
513 let bindings = [
514 KeyBinding::new("ctrl-x", ActionAlpha {}, Some("workspace")),
515 KeyBinding::new("ctrl-x", NoAction {}, Some("editor")),
516 ];
517
518 let mut keymap = Keymap::default();
519 keymap.add_bindings(bindings);
520
521 // Ensure `space` results in pending input on the workspace, but not editor
522 let (result, pending) = keymap.bindings_for_input(
523 &[Keystroke::parse("ctrl-x").unwrap()],
524 &[
525 KeyContext::parse("workspace").unwrap(),
526 KeyContext::parse("editor").unwrap(),
527 ],
528 );
529 assert_eq!(result.len(), 0);
530 assert!(!pending);
531 }
532
533 #[test]
534 fn test_pending_match_enabled() {
535 let bindings = [
536 KeyBinding::new("ctrl-x", ActionBeta, Some("vim_mode == normal")),
537 KeyBinding::new("ctrl-x 0", ActionAlpha, Some("Workspace")),
538 ];
539 let mut keymap = Keymap::default();
540 keymap.add_bindings(bindings);
541
542 let matched = keymap.bindings_for_input(
543 &[Keystroke::parse("ctrl-x")].map(Result::unwrap),
544 &[
545 KeyContext::parse("Workspace"),
546 KeyContext::parse("Pane"),
547 KeyContext::parse("Editor vim_mode=normal"),
548 ]
549 .map(Result::unwrap),
550 );
551 assert_eq!(matched.0.len(), 1);
552 assert!(matched.0[0].action.partial_eq(&ActionBeta));
553 assert!(matched.1);
554 }
555
556 #[test]
557 fn test_pending_match_enabled_extended() {
558 let bindings = [
559 KeyBinding::new("ctrl-x", ActionBeta, Some("vim_mode == normal")),
560 KeyBinding::new("ctrl-x 0", NoAction, Some("Workspace")),
561 ];
562 let mut keymap = Keymap::default();
563 keymap.add_bindings(bindings);
564
565 let matched = keymap.bindings_for_input(
566 &[Keystroke::parse("ctrl-x")].map(Result::unwrap),
567 &[
568 KeyContext::parse("Workspace"),
569 KeyContext::parse("Pane"),
570 KeyContext::parse("Editor vim_mode=normal"),
571 ]
572 .map(Result::unwrap),
573 );
574 assert_eq!(matched.0.len(), 1);
575 assert!(matched.0[0].action.partial_eq(&ActionBeta));
576 assert!(!matched.1);
577 let bindings = [
578 KeyBinding::new("ctrl-x", ActionBeta, Some("Workspace")),
579 KeyBinding::new("ctrl-x 0", NoAction, Some("vim_mode == normal")),
580 ];
581 let mut keymap = Keymap::default();
582 keymap.add_bindings(bindings);
583
584 let matched = keymap.bindings_for_input(
585 &[Keystroke::parse("ctrl-x")].map(Result::unwrap),
586 &[
587 KeyContext::parse("Workspace"),
588 KeyContext::parse("Pane"),
589 KeyContext::parse("Editor vim_mode=normal"),
590 ]
591 .map(Result::unwrap),
592 );
593 assert_eq!(matched.0.len(), 1);
594 assert!(matched.0[0].action.partial_eq(&ActionBeta));
595 assert!(!matched.1);
596 }
597
598 #[test]
599 fn test_overriding_prefix() {
600 let bindings = [
601 KeyBinding::new("ctrl-x 0", ActionAlpha, Some("Workspace")),
602 KeyBinding::new("ctrl-x", ActionBeta, Some("vim_mode == normal")),
603 ];
604 let mut keymap = Keymap::default();
605 keymap.add_bindings(bindings);
606
607 let matched = keymap.bindings_for_input(
608 &[Keystroke::parse("ctrl-x")].map(Result::unwrap),
609 &[
610 KeyContext::parse("Workspace"),
611 KeyContext::parse("Pane"),
612 KeyContext::parse("Editor vim_mode=normal"),
613 ]
614 .map(Result::unwrap),
615 );
616 assert_eq!(matched.0.len(), 1);
617 assert!(matched.0[0].action.partial_eq(&ActionBeta));
618 assert!(!matched.1);
619 }
620
621 #[test]
622 fn test_bindings_for_action() {
623 let bindings = [
624 KeyBinding::new("ctrl-a", ActionAlpha {}, Some("pane")),
625 KeyBinding::new("ctrl-b", ActionBeta {}, Some("editor && mode == full")),
626 KeyBinding::new("ctrl-c", ActionGamma {}, Some("workspace")),
627 KeyBinding::new("ctrl-a", NoAction {}, Some("pane && active")),
628 KeyBinding::new("ctrl-b", NoAction {}, Some("editor")),
629 ];
630
631 let mut keymap = Keymap::default();
632 keymap.add_bindings(bindings);
633
634 assert_bindings(&keymap, &ActionAlpha {}, &["ctrl-a"]);
635 assert_bindings(&keymap, &ActionBeta {}, &[]);
636 assert_bindings(&keymap, &ActionGamma {}, &["ctrl-c"]);
637
638 #[track_caller]
639 fn assert_bindings(keymap: &Keymap, action: &dyn Action, expected: &[&str]) {
640 let actual = keymap
641 .bindings_for_action(action)
642 .map(|binding| binding.keystrokes[0].unparse())
643 .collect::<Vec<_>>();
644 assert_eq!(actual, expected, "{:?}", action);
645 }
646 }
647}