feat(commands): command palette (#1400)

* feat(commands): command palette

Add new command to display command pallete that can be used
to discover and execute available commands.

Fixes: https://github.com/helix-editor/helix/issues/559

* Make picker take the whole context, not just editor

* Bind command pallete

* Typable commands also in the palette

* Show key bindings for commands

* Fix tests, small refactor

* Refactor keymap mapping, fix typo

* Ignore sequence key bindings for now

* Apply suggestions

* Fix lint issues in tests

* Fix after rebase

Co-authored-by: Blaž Hrastnik <blaz@mxxn.io>

3 files changed, 142 insertions, 3 deletions

diff --git a/helix-term/src/commands.rs b/helix-term/src/commands.rs
index c07f44dc..bb74f9ec 100644
--- a/helix-term/src/commands.rs
+++ b/helix-term/src/commands.rs
@@ -44,7 +44,7 @@ use movement::Movement;
 use crate::{
     args,
     compositor::{self, Component, Compositor},
-    ui::{self, overlay::overlayed, FilePicker, Popup, Prompt, PromptEvent},
+    ui::{self, overlay::overlayed, FilePicker, Picker, Popup, Prompt, PromptEvent},
 };
 
 use crate::job::{self, Job, Jobs};
@@ -430,6 +430,7 @@ impl MappableCommand {
         decrement, "Decrement",
         record_macro, "Record macro",
         replay_macro, "Replay macro",
+        command_palette, "Open command pallete",
     );
 }
 
@@ -3692,6 +3693,69 @@ pub fn code_action(cx: &mut Context) {
     )
 }
 
+pub fn command_palette(cx: &mut Context) {
+    cx.callback = Some(Box::new(
+        move |compositor: &mut Compositor, cx: &mut compositor::Context| {
+            let doc = doc_mut!(cx.editor);
+            let keymap =
+                compositor.find::<ui::EditorView>().unwrap().keymaps[&doc.mode].reverse_map();
+
+            let mut commands: Vec<MappableCommand> = MappableCommand::STATIC_COMMAND_LIST.into();
+            commands.extend(
+                cmd::TYPABLE_COMMAND_LIST
+                    .iter()
+                    .map(|cmd| MappableCommand::Typable {
+                        name: cmd.name.to_owned(),
+                        doc: cmd.doc.to_owned(),
+                        args: Vec::new(),
+                    }),
+            );
+
+            // formats key bindings, multiple bindings are comma separated,
+            // individual key presses are joined with `+`
+            let fmt_binding = |bindings: &Vec<Vec<KeyEvent>>| -> String {
+                bindings
+                    .iter()
+                    .map(|bind| {
+                        bind.iter()
+                            .map(|key| key.to_string())
+                            .collect::<Vec<String>>()
+                            .join("+")
+                    })
+                    .collect::<Vec<String>>()
+                    .join(", ")
+            };
+
+            let picker = Picker::new(
+                commands,
+                move |command| match command {
+                    MappableCommand::Typable { doc, name, .. } => match keymap.get(name as &String)
+                    {
+                        Some(bindings) => format!("{} ({})", doc, fmt_binding(bindings)).into(),
+                        None => doc.into(),
+                    },
+                    MappableCommand::Static { doc, name, .. } => match keymap.get(*name) {
+                        Some(bindings) => format!("{} ({})", doc, fmt_binding(bindings)).into(),
+                        None => (*doc).into(),
+                    },
+                },
+                move |cx, command, _action| {
+                    let mut ctx = Context {
+                        register: None,
+                        count: std::num::NonZeroUsize::new(1),
+                        editor: cx.editor,
+                        callback: None,
+                        on_next_key_callback: None,
+                        jobs: cx.jobs,
+                    };
+                    command.execute(&mut ctx);
+                },
+            );
+            compositor.push(Box::new(picker));
+        },
+    ));
+}
+
 pub fn execute_lsp_command(editor: &mut Editor, cmd: lsp::Command) {
     let doc = doc!(editor);
     let language_server = match doc.language_server() {
diff --git a/helix-term/src/keymap.rs b/helix-term/src/keymap.rs
index f414f797..0147f58e 100644
--- a/helix-term/src/keymap.rs
+++ b/helix-term/src/keymap.rs
@@ -343,13 +343,46 @@ pub struct Keymap {
 
 impl Keymap {
     pub fn new(root: KeyTrie) -> Self {
-        Self {
+        Keymap {
             root,
             state: Vec::new(),
             sticky: None,
         }
     }
 
+    pub fn reverse_map(&self) -> HashMap<String, Vec<Vec<KeyEvent>>> {
+        // recursively visit all nodes in keymap
+        fn map_node(
+            cmd_map: &mut HashMap<String, Vec<Vec<KeyEvent>>>,
+            node: &KeyTrie,
+            keys: &mut Vec<KeyEvent>,
+        ) {
+            match node {
+                KeyTrie::Leaf(cmd) => match cmd {
+                    MappableCommand::Typable { name, .. } => {
+                        cmd_map.entry(name.into()).or_default().push(keys.clone())
+                    }
+                    MappableCommand::Static { name, .. } => cmd_map
+                        .entry(name.to_string())
+                        .or_default()
+                        .push(keys.clone()),
+                },
+                KeyTrie::Node(next) => {
+                    for (key, trie) in &next.map {
+                        keys.push(*key);
+                        map_node(cmd_map, trie, keys);
+                        keys.pop();
+                    }
+                }
+                KeyTrie::Sequence(_) => {}
+            };
+        }
+
+        let mut res = HashMap::new();
+        map_node(&mut res, &self.root, &mut Vec::new());
+        res
+    }
+
     pub fn root(&self) -> &KeyTrie {
         &self.root
     }
@@ -706,6 +739,7 @@ impl Default for Keymaps {
                 "/" => global_search,
                 "k" => hover,
                 "r" => rename_symbol,
+                "?" => command_palette,
             },
             "z" => { "View"
                 "z" | "c" => align_view_center,
@@ -958,4 +992,45 @@ mod tests {
             "Mismatch for view mode on `z` and `Z`"
         );
     }
+
+    #[test]
+    fn reverse_map() {
+        let normal_mode = keymap!({ "Normal mode"
+            "i" => insert_mode,
+            "g" => { "Goto"
+                "g" => goto_file_start,
+                "e" => goto_file_end,
+            },
+            "j" | "k" => move_line_down,
+        });
+        let keymap = Keymap::new(normal_mode);
+        let mut reverse_map = keymap.reverse_map();
+
+        // sort keybindings in order to have consistent tests
+        // HashMaps can be compared but we can still get different ordering of bindings
+        // for commands that have multiple bindings assigned
+        for v in reverse_map.values_mut() {
+            v.sort()
+        }
+
+        assert_eq!(
+            reverse_map,
+            HashMap::from([
+                ("insert_mode".to_string(), vec![vec![key!('i')]]),
+                (
+                    "goto_file_start".to_string(),
+                    vec![vec![key!('g'), key!('g')]]
+                ),
+                (
+                    "goto_file_end".to_string(),
+                    vec![vec![key!('g'), key!('e')]]
+                ),
+                (
+                    "move_line_down".to_string(),
+                    vec![vec![key!('j')], vec![key!('k')]]
+                ),
+            ]),
+            "Mistmatch"
+        )
+    }
 }
diff --git a/helix-term/src/ui/editor.rs b/helix-term/src/ui/editor.rs
index a2131abe..fc749ebb 100644
--- a/helix-term/src/ui/editor.rs
+++ b/helix-term/src/ui/editor.rs
@@ -31,7 +31,7 @@ use crossterm::event::{Event, MouseButton, MouseEvent, MouseEventKind};
 use tui::buffer::Buffer as Surface;
 
 pub struct EditorView {
-    keymaps: Keymaps,
+    pub keymaps: Keymaps,
     on_next_key: Option<Box<dyn FnOnce(&mut commands::Context, KeyEvent)>>,
     last_insert: (commands::MappableCommand, Vec<KeyEvent>),
     pub(crate) completion: Option<Completion>,