1/// KeyDispatch is where GPUI deals with binding actions to key events.
2///
3/// The key pieces to making a key binding work are to define an action,
4/// implement a method that takes that action as a type parameter,
5/// and then to register the action during render on a focused node
6/// with a keymap context:
7///
8/// ```rust
9/// actions!(editor,[Undo, Redo]);
10///
11/// impl Editor {
12/// fn undo(&mut self, _: &Undo, _window: &mut Window, _cx: &mut Context<Self>) { ... }
13/// fn redo(&mut self, _: &Redo, _window: &mut Window, _cx: &mut Context<Self>) { ... }
14/// }
15///
16/// impl Render for Editor {
17/// fn render(&mut self, window: &mut Window, cx: &mut Context<Self>) -> impl IntoElement {
18/// div()
19/// .track_focus(&self.focus_handle(cx))
20/// .key_context("Editor")
21/// .on_action(cx.listener(Editor::undo))
22/// .on_action(cx.listener(Editor::redo))
23/// ...
24/// }
25/// }
26///```
27///
28/// The keybindings themselves are managed independently by calling cx.bind_keys().
29/// (Though mostly when developing Zed itself, you just need to add a new line to
30/// assets/keymaps/default-{platform}.json).
31///
32/// ```rust
33/// cx.bind_keys([
34/// KeyBinding::new("cmd-z", Editor::undo, Some("Editor")),
35/// KeyBinding::new("cmd-shift-z", Editor::redo, Some("Editor")),
36/// ])
37/// ```
38///
39/// With all of this in place, GPUI will ensure that if you have an Editor that contains
40/// the focus, hitting cmd-z will Undo.
41///
42/// In real apps, it is a little more complicated than this, because typically you have
43/// several nested views that each register keyboard handlers. In this case action matching
44/// bubbles up from the bottom. For example in Zed, the Workspace is the top-level view, which contains Pane's, which contain Editors. If there are conflicting keybindings defined
45/// then the Editor's bindings take precedence over the Pane's bindings, which take precedence over the Workspace.
46///
47/// In GPUI, keybindings are not limited to just single keystrokes, you can define
48/// sequences by separating the keys with a space:
49///
50/// KeyBinding::new("cmd-k left", pane::SplitLeft, Some("Pane"))
51///
52use crate::{
53 Action, ActionRegistry, App, BindingIndex, DispatchPhase, EntityId, FocusId, KeyBinding,
54 KeyContext, Keymap, Keystroke, ModifiersChangedEvent, Window,
55};
56use collections::FxHashMap;
57use smallvec::SmallVec;
58use std::{
59 any::{Any, TypeId},
60 cell::RefCell,
61 mem,
62 ops::Range,
63 rc::Rc,
64};
65
66/// ID of a node within `DispatchTree`. Note that these are **not** stable between frames, and so a
67/// `DispatchNodeId` should only be used with the `DispatchTree` that provided it.
68#[derive(Clone, Copy, Debug, Eq, PartialEq, Hash)]
69pub(crate) struct DispatchNodeId(usize);
70
71pub(crate) struct DispatchTree {
72 node_stack: Vec<DispatchNodeId>,
73 pub(crate) context_stack: Vec<KeyContext>,
74 view_stack: Vec<EntityId>,
75 nodes: Vec<DispatchNode>,
76 focusable_node_ids: FxHashMap<FocusId, DispatchNodeId>,
77 view_node_ids: FxHashMap<EntityId, DispatchNodeId>,
78 keymap: Rc<RefCell<Keymap>>,
79 action_registry: Rc<ActionRegistry>,
80}
81
82#[derive(Default)]
83pub(crate) struct DispatchNode {
84 pub key_listeners: Vec<KeyListener>,
85 pub action_listeners: Vec<DispatchActionListener>,
86 pub modifiers_changed_listeners: Vec<ModifiersChangedListener>,
87 pub context: Option<KeyContext>,
88 pub focus_id: Option<FocusId>,
89 view_id: Option<EntityId>,
90 parent: Option<DispatchNodeId>,
91}
92
93pub(crate) struct ReusedSubtree {
94 old_range: Range<usize>,
95 new_range: Range<usize>,
96 contains_focus: bool,
97}
98
99impl ReusedSubtree {
100 pub fn refresh_node_id(&self, node_id: DispatchNodeId) -> DispatchNodeId {
101 debug_assert!(
102 self.old_range.contains(&node_id.0),
103 "node {} was not part of the reused subtree {:?}",
104 node_id.0,
105 self.old_range
106 );
107 DispatchNodeId((node_id.0 - self.old_range.start) + self.new_range.start)
108 }
109
110 pub fn contains_focus(&self) -> bool {
111 self.contains_focus
112 }
113}
114
115#[derive(Default, Debug)]
116pub(crate) struct Replay {
117 pub(crate) keystroke: Keystroke,
118 pub(crate) bindings: SmallVec<[KeyBinding; 1]>,
119}
120
121#[derive(Default, Debug)]
122pub(crate) struct DispatchResult {
123 pub(crate) pending: SmallVec<[Keystroke; 1]>,
124 pub(crate) bindings: SmallVec<[KeyBinding; 1]>,
125 pub(crate) to_replay: SmallVec<[Replay; 1]>,
126 pub(crate) context_stack: Vec<KeyContext>,
127}
128
129type KeyListener = Rc<dyn Fn(&dyn Any, DispatchPhase, &mut Window, &mut App)>;
130type ModifiersChangedListener = Rc<dyn Fn(&ModifiersChangedEvent, &mut Window, &mut App)>;
131
132#[derive(Clone)]
133pub(crate) struct DispatchActionListener {
134 pub(crate) action_type: TypeId,
135 pub(crate) listener: Rc<dyn Fn(&dyn Any, DispatchPhase, &mut Window, &mut App)>,
136}
137
138impl DispatchTree {
139 pub fn new(keymap: Rc<RefCell<Keymap>>, action_registry: Rc<ActionRegistry>) -> Self {
140 Self {
141 node_stack: Vec::new(),
142 context_stack: Vec::new(),
143 view_stack: Vec::new(),
144 nodes: Vec::new(),
145 focusable_node_ids: FxHashMap::default(),
146 view_node_ids: FxHashMap::default(),
147 keymap,
148 action_registry,
149 }
150 }
151
152 pub fn clear(&mut self) {
153 self.node_stack.clear();
154 self.context_stack.clear();
155 self.view_stack.clear();
156 self.nodes.clear();
157 self.focusable_node_ids.clear();
158 self.view_node_ids.clear();
159 }
160
161 pub fn len(&self) -> usize {
162 self.nodes.len()
163 }
164
165 pub fn push_node(&mut self) -> DispatchNodeId {
166 let parent = self.node_stack.last().copied();
167 let node_id = DispatchNodeId(self.nodes.len());
168
169 self.nodes.push(DispatchNode {
170 parent,
171 ..Default::default()
172 });
173 self.node_stack.push(node_id);
174 node_id
175 }
176
177 pub fn set_active_node(&mut self, node_id: DispatchNodeId) {
178 let next_node_parent = self.nodes[node_id.0].parent;
179 while self.node_stack.last().copied() != next_node_parent && !self.node_stack.is_empty() {
180 self.pop_node();
181 }
182
183 if self.node_stack.last().copied() == next_node_parent {
184 self.node_stack.push(node_id);
185 let active_node = &self.nodes[node_id.0];
186 if let Some(view_id) = active_node.view_id {
187 self.view_stack.push(view_id)
188 }
189 if let Some(context) = active_node.context.clone() {
190 self.context_stack.push(context);
191 }
192 } else {
193 debug_assert_eq!(self.node_stack.len(), 0);
194
195 let mut current_node_id = Some(node_id);
196 while let Some(node_id) = current_node_id {
197 let node = &self.nodes[node_id.0];
198 if let Some(context) = node.context.clone() {
199 self.context_stack.push(context);
200 }
201 if node.view_id.is_some() {
202 self.view_stack.push(node.view_id.unwrap());
203 }
204 self.node_stack.push(node_id);
205 current_node_id = node.parent;
206 }
207
208 self.context_stack.reverse();
209 self.view_stack.reverse();
210 self.node_stack.reverse();
211 }
212 }
213
214 pub fn set_key_context(&mut self, context: KeyContext) {
215 self.active_node().context = Some(context.clone());
216 self.context_stack.push(context);
217 }
218
219 pub fn set_focus_id(&mut self, focus_id: FocusId) {
220 let node_id = *self.node_stack.last().unwrap();
221 self.nodes[node_id.0].focus_id = Some(focus_id);
222 self.focusable_node_ids.insert(focus_id, node_id);
223 }
224
225 pub fn set_view_id(&mut self, view_id: EntityId) {
226 if self.view_stack.last().copied() != Some(view_id) {
227 let node_id = *self.node_stack.last().unwrap();
228 self.nodes[node_id.0].view_id = Some(view_id);
229 self.view_node_ids.insert(view_id, node_id);
230 self.view_stack.push(view_id);
231 }
232 }
233
234 pub fn pop_node(&mut self) {
235 let node = &self.nodes[self.active_node_id().unwrap().0];
236 if node.context.is_some() {
237 self.context_stack.pop();
238 }
239 if node.view_id.is_some() {
240 self.view_stack.pop();
241 }
242 self.node_stack.pop();
243 }
244
245 fn move_node(&mut self, source: &mut DispatchNode) {
246 self.push_node();
247 if let Some(context) = source.context.clone() {
248 self.set_key_context(context);
249 }
250 if let Some(focus_id) = source.focus_id {
251 self.set_focus_id(focus_id);
252 }
253 if let Some(view_id) = source.view_id {
254 self.set_view_id(view_id);
255 }
256
257 let target = self.active_node();
258 target.key_listeners = mem::take(&mut source.key_listeners);
259 target.action_listeners = mem::take(&mut source.action_listeners);
260 target.modifiers_changed_listeners = mem::take(&mut source.modifiers_changed_listeners);
261 }
262
263 pub fn reuse_subtree(
264 &mut self,
265 old_range: Range<usize>,
266 source: &mut Self,
267 focus: Option<FocusId>,
268 ) -> ReusedSubtree {
269 let new_range = self.nodes.len()..self.nodes.len() + old_range.len();
270
271 let mut contains_focus = false;
272 let mut source_stack = vec![];
273 for (source_node_id, source_node) in source
274 .nodes
275 .iter_mut()
276 .enumerate()
277 .skip(old_range.start)
278 .take(old_range.len())
279 {
280 let source_node_id = DispatchNodeId(source_node_id);
281 while let Some(source_ancestor) = source_stack.last() {
282 if source_node.parent == Some(*source_ancestor) {
283 break;
284 } else {
285 source_stack.pop();
286 self.pop_node();
287 }
288 }
289
290 source_stack.push(source_node_id);
291 if source_node.focus_id.is_some() && source_node.focus_id == focus {
292 contains_focus = true;
293 }
294 self.move_node(source_node);
295 }
296
297 while !source_stack.is_empty() {
298 source_stack.pop();
299 self.pop_node();
300 }
301
302 ReusedSubtree {
303 old_range,
304 new_range,
305 contains_focus,
306 }
307 }
308
309 pub fn truncate(&mut self, index: usize) {
310 for node in &self.nodes[index..] {
311 if let Some(focus_id) = node.focus_id {
312 self.focusable_node_ids.remove(&focus_id);
313 }
314
315 if let Some(view_id) = node.view_id {
316 self.view_node_ids.remove(&view_id);
317 }
318 }
319 self.nodes.truncate(index);
320 }
321
322 pub fn on_key_event(&mut self, listener: KeyListener) {
323 self.active_node().key_listeners.push(listener);
324 }
325
326 pub fn on_modifiers_changed(&mut self, listener: ModifiersChangedListener) {
327 self.active_node()
328 .modifiers_changed_listeners
329 .push(listener);
330 }
331
332 pub fn on_action(
333 &mut self,
334 action_type: TypeId,
335 listener: Rc<dyn Fn(&dyn Any, DispatchPhase, &mut Window, &mut App)>,
336 ) {
337 self.active_node()
338 .action_listeners
339 .push(DispatchActionListener {
340 action_type,
341 listener,
342 });
343 }
344
345 pub fn focus_contains(&self, parent: FocusId, child: FocusId) -> bool {
346 if parent == child {
347 return true;
348 }
349
350 if let Some(parent_node_id) = self.focusable_node_ids.get(&parent) {
351 let mut current_node_id = self.focusable_node_ids.get(&child).copied();
352 while let Some(node_id) = current_node_id {
353 if node_id == *parent_node_id {
354 return true;
355 }
356 current_node_id = self.nodes[node_id.0].parent;
357 }
358 }
359 false
360 }
361
362 pub fn available_actions(&self, target: DispatchNodeId) -> Vec<Box<dyn Action>> {
363 let mut actions = Vec::<Box<dyn Action>>::new();
364 for node_id in self.dispatch_path(target) {
365 let node = &self.nodes[node_id.0];
366 for DispatchActionListener { action_type, .. } in &node.action_listeners {
367 if let Err(ix) = actions.binary_search_by_key(action_type, |a| a.as_any().type_id())
368 {
369 // Intentionally silence these errors without logging.
370 // If an action cannot be built by default, it's not available.
371 let action = self.action_registry.build_action_type(action_type).ok();
372 if let Some(action) = action {
373 actions.insert(ix, action);
374 }
375 }
376 }
377 }
378 actions
379 }
380
381 pub fn is_action_available(&self, action: &dyn Action, target: DispatchNodeId) -> bool {
382 for node_id in self.dispatch_path(target) {
383 let node = &self.nodes[node_id.0];
384 if node
385 .action_listeners
386 .iter()
387 .any(|listener| listener.action_type == action.as_any().type_id())
388 {
389 return true;
390 }
391 }
392 false
393 }
394
395 /// Returns key bindings that invoke an action on the currently focused element. Bindings are
396 /// returned in the order they were added. For display, the last binding should take precedence.
397 ///
398 /// Bindings are only included if they are the highest precedence match for their keystrokes, so
399 /// shadowed bindings are not included.
400 pub fn bindings_for_action(
401 &self,
402 action: &dyn Action,
403 context_stack: &[KeyContext],
404 ) -> Vec<KeyBinding> {
405 // Ideally this would return a `DoubleEndedIterator` to avoid `highest_precedence_*`
406 // methods, but this can't be done very cleanly since keymap must be borrowed.
407 let keymap = self.keymap.borrow();
408 keymap
409 .bindings_for_action_with_indices(action)
410 .filter(|(binding_index, binding)| {
411 Self::binding_matches_predicate_and_not_shadowed(
412 &keymap,
413 *binding_index,
414 &binding.keystrokes,
415 context_stack,
416 )
417 })
418 .map(|(_, binding)| binding.clone())
419 .collect()
420 }
421
422 /// Returns the highest precedence binding for the given action and context stack. This is the
423 /// same as the last result of `bindings_for_action`, but more efficient than getting all bindings.
424 pub fn highest_precedence_binding_for_action(
425 &self,
426 action: &dyn Action,
427 context_stack: &[KeyContext],
428 ) -> Option<KeyBinding> {
429 let keymap = self.keymap.borrow();
430 keymap
431 .bindings_for_action_with_indices(action)
432 .rev()
433 .find_map(|(binding_index, binding)| {
434 let found = Self::binding_matches_predicate_and_not_shadowed(
435 &keymap,
436 binding_index,
437 &binding.keystrokes,
438 context_stack,
439 );
440 if found { Some(binding.clone()) } else { None }
441 })
442 }
443
444 fn binding_matches_predicate_and_not_shadowed(
445 keymap: &Keymap,
446 binding_index: BindingIndex,
447 keystrokes: &[Keystroke],
448 context_stack: &[KeyContext],
449 ) -> bool {
450 let (bindings, _) = keymap.bindings_for_input_with_indices(&keystrokes, context_stack);
451 if let Some((highest_precedence_index, _)) = bindings.iter().next() {
452 binding_index == *highest_precedence_index
453 } else {
454 false
455 }
456 }
457
458 fn bindings_for_input(
459 &self,
460 input: &[Keystroke],
461 dispatch_path: &SmallVec<[DispatchNodeId; 32]>,
462 ) -> (SmallVec<[KeyBinding; 1]>, bool, Vec<KeyContext>) {
463 let context_stack: Vec<KeyContext> = dispatch_path
464 .iter()
465 .filter_map(|node_id| self.node(*node_id).context.clone())
466 .collect();
467
468 let (bindings, partial) = self
469 .keymap
470 .borrow()
471 .bindings_for_input(input, &context_stack);
472 return (bindings, partial, context_stack);
473 }
474
475 /// dispatch_key processes the keystroke
476 /// input should be set to the value of `pending` from the previous call to dispatch_key.
477 /// This returns three instructions to the input handler:
478 /// - bindings: any bindings to execute before processing this keystroke
479 /// - pending: the new set of pending keystrokes to store
480 /// - to_replay: any keystroke that had been pushed to pending, but are no-longer matched,
481 /// these should be replayed first.
482 pub fn dispatch_key(
483 &mut self,
484 mut input: SmallVec<[Keystroke; 1]>,
485 keystroke: Keystroke,
486 dispatch_path: &SmallVec<[DispatchNodeId; 32]>,
487 ) -> DispatchResult {
488 input.push(keystroke.clone());
489 let (bindings, pending, context_stack) = self.bindings_for_input(&input, dispatch_path);
490
491 if pending {
492 return DispatchResult {
493 pending: input,
494 context_stack,
495 ..Default::default()
496 };
497 } else if !bindings.is_empty() {
498 return DispatchResult {
499 bindings,
500 context_stack,
501 ..Default::default()
502 };
503 } else if input.len() == 1 {
504 return DispatchResult {
505 context_stack,
506 ..Default::default()
507 };
508 }
509 input.pop();
510
511 let (suffix, mut to_replay) = self.replay_prefix(input, dispatch_path);
512
513 let mut result = self.dispatch_key(suffix, keystroke, dispatch_path);
514 to_replay.extend(result.to_replay);
515 result.to_replay = to_replay;
516 result
517 }
518
519 /// If the user types a matching prefix of a binding and then waits for a timeout
520 /// flush_dispatch() converts any previously pending input to replay events.
521 pub fn flush_dispatch(
522 &mut self,
523 input: SmallVec<[Keystroke; 1]>,
524 dispatch_path: &SmallVec<[DispatchNodeId; 32]>,
525 ) -> SmallVec<[Replay; 1]> {
526 let (suffix, mut to_replay) = self.replay_prefix(input, dispatch_path);
527
528 if !suffix.is_empty() {
529 to_replay.extend(self.flush_dispatch(suffix, dispatch_path))
530 }
531
532 to_replay
533 }
534
535 /// Converts the longest prefix of input to a replay event and returns the rest.
536 fn replay_prefix(
537 &self,
538 mut input: SmallVec<[Keystroke; 1]>,
539 dispatch_path: &SmallVec<[DispatchNodeId; 32]>,
540 ) -> (SmallVec<[Keystroke; 1]>, SmallVec<[Replay; 1]>) {
541 let mut to_replay: SmallVec<[Replay; 1]> = Default::default();
542 for last in (0..input.len()).rev() {
543 let (bindings, _, _) = self.bindings_for_input(&input[0..=last], dispatch_path);
544 if !bindings.is_empty() {
545 to_replay.push(Replay {
546 keystroke: input.drain(0..=last).next_back().unwrap(),
547 bindings,
548 });
549 break;
550 }
551 }
552 if to_replay.is_empty() {
553 to_replay.push(Replay {
554 keystroke: input.remove(0),
555 ..Default::default()
556 });
557 }
558 (input, to_replay)
559 }
560
561 pub fn dispatch_path(&self, target: DispatchNodeId) -> SmallVec<[DispatchNodeId; 32]> {
562 let mut dispatch_path: SmallVec<[DispatchNodeId; 32]> = SmallVec::new();
563 let mut current_node_id = Some(target);
564 while let Some(node_id) = current_node_id {
565 dispatch_path.push(node_id);
566 current_node_id = self.nodes[node_id.0].parent;
567 }
568 dispatch_path.reverse(); // Reverse the path so it goes from the root to the focused node.
569 dispatch_path
570 }
571
572 pub fn focus_path(&self, focus_id: FocusId) -> SmallVec<[FocusId; 8]> {
573 println!("focus path requested for focus id: {:?}", focus_id);
574 let mut focus_path: SmallVec<[FocusId; 8]> = SmallVec::new();
575 let mut current_node_id = self.focusable_node_ids.get(&focus_id).copied();
576 while let Some(node_id) = current_node_id {
577 let node = self.node(node_id);
578 if let Some(focus_id) = node.focus_id {
579 focus_path.push(focus_id);
580 }
581 current_node_id = node.parent;
582 }
583 focus_path.reverse(); // Reverse the path so it goes from the root to the focused node.
584 focus_path
585 }
586
587 pub fn view_path(&self, view_id: EntityId) -> SmallVec<[EntityId; 8]> {
588 let mut view_path: SmallVec<[EntityId; 8]> = SmallVec::new();
589 let mut current_node_id = self.view_node_ids.get(&view_id).copied();
590 while let Some(node_id) = current_node_id {
591 let node = self.node(node_id);
592 if let Some(view_id) = node.view_id {
593 view_path.push(view_id);
594 }
595 current_node_id = node.parent;
596 }
597 view_path.reverse(); // Reverse the path so it goes from the root to the view node.
598 view_path
599 }
600
601 pub fn node(&self, node_id: DispatchNodeId) -> &DispatchNode {
602 &self.nodes[node_id.0]
603 }
604
605 fn active_node(&mut self) -> &mut DispatchNode {
606 let active_node_id = self.active_node_id().unwrap();
607 &mut self.nodes[active_node_id.0]
608 }
609
610 pub fn focusable_node_id(&self, target: FocusId) -> Option<DispatchNodeId> {
611 self.focusable_node_ids.get(&target).copied()
612 }
613
614 pub fn root_node_id(&self) -> DispatchNodeId {
615 debug_assert!(!self.nodes.is_empty());
616 DispatchNodeId(0)
617 }
618
619 pub fn active_node_id(&self) -> Option<DispatchNodeId> {
620 self.node_stack.last().copied()
621 }
622}
623
624#[cfg(test)]
625mod tests {
626 use std::{cell::RefCell, rc::Rc};
627
628 use crate::{Action, ActionRegistry, DispatchTree, KeyBinding, KeyContext, Keymap};
629
630 #[derive(PartialEq, Eq)]
631 struct TestAction;
632
633 impl Action for TestAction {
634 fn name(&self) -> &'static str {
635 "test::TestAction"
636 }
637
638 fn name_for_type() -> &'static str
639 where
640 Self: ::std::marker::Sized,
641 {
642 "test::TestAction"
643 }
644
645 fn partial_eq(&self, action: &dyn Action) -> bool {
646 action
647 .as_any()
648 .downcast_ref::<Self>()
649 .map_or(false, |a| self == a)
650 }
651
652 fn boxed_clone(&self) -> std::boxed::Box<dyn Action> {
653 Box::new(TestAction)
654 }
655
656 fn build(_value: serde_json::Value) -> anyhow::Result<Box<dyn Action>>
657 where
658 Self: Sized,
659 {
660 Ok(Box::new(TestAction))
661 }
662 }
663
664 #[test]
665 fn test_keybinding_for_action_bounds() {
666 let keymap = Keymap::new(vec![KeyBinding::new(
667 "cmd-n",
668 TestAction,
669 Some("ProjectPanel"),
670 )]);
671
672 let mut registry = ActionRegistry::default();
673
674 registry.load_action::<TestAction>();
675
676 let keymap = Rc::new(RefCell::new(keymap));
677
678 let tree = DispatchTree::new(keymap, Rc::new(registry));
679
680 let contexts = vec![
681 KeyContext::parse("Workspace").unwrap(),
682 KeyContext::parse("ProjectPanel").unwrap(),
683 ];
684
685 let keybinding = tree.bindings_for_action(&TestAction, &contexts);
686
687 assert!(keybinding[0].action.partial_eq(&TestAction))
688 }
689}