Previously. Lately, I have been trying out the Vim emulation plugins of some “modern” text editors like Atom and Visual Studio Code, but my main gripe with them is how hard it is to configure the key mapping.

Table of Contents

  1. What’s Wrong with “Modern” Text Editors and What’s Right with Vimscript
  2. Designing the Key Map Layer
  3. Evolution of PrefixTreeNode
  4. Implementing Lookup
  5. Class Members
  6. Epilogue
  7. Takeaways

What’s Wrong with “Modern” Text Editors and What’s Right with Vimscript

When I started using VSCode, I had a hard time trying to configure some basic Emacs-like bindings in insert mode, and this is how I did it in Vim:

inoremap <C-p> <Up>
inoremap <C-n> <Down>

And I just took a look at my VSCode configuration, and this is what the part looks like in my keybindings.json:

{
    "key": "ctrl+p",
    "when": "editorTextFocus && vim.active && !suggestWidgetMultipleSuggestions && !suggestWidgetVisible",
    "command": "cursorUp",
},
{
    "key": "ctrl+n",
    "when": "editorTextFocus && vim.active && !suggestWidgetMultipleSuggestions && !suggestWidgetVisible",
    "command": "cursorDown",
},

And all these state checking in "when" isn’t even the worst part yet, normal mode bindings must be defined in a different file (settings.json) as they are a part of the plugin configurations, which looks like:

"vim.normalModeKeyBindingsNonRecursive": [
    {
      "before": ["s"],
      "after": [":"]
    },
    {
      "before": ["<leader>", "s"],
      "commands": ["workbench.action.files.save"]
    },
    {
      "before": ["<leader>", "q"],
      "after": [":", "q", "<CR>"],
      // "commands": ["workbench.files.action.closeFile"]
    },
    // ....
],

Atom is much better in this regard, but still, I have to find the long list of editor actions and paste something like editor:delete-to-previous-word-boundary whenever I want to fiddle with my key binding, instead of just adding a inoremap to <C-w>. (The real question is why Atom’s Vim plugin does not include Ctrl-W by default?) Also, there’s no way to define recursive bindings (luckily recursive bindings are not that useful anyway).

'atom-text-editor.vim-mode-plus.insert-mode':
    'ctrl-d': 'editor:outdent-selected-rows'
    'ctrl-t': 'editor:indent-selected-rows'
    'ctrl-w': 'editor:delete-to-previous-word-boundary'

'atom-text-editor.vim-mode-plus:not(.insert-mode)':
    's': 'command-palette:toggle'
    'space s': 'core:save'
    'space q': 'core:close'
    'space n': 'pane:show-next-item'
    'space p': 'pane:show-previous-item'
    'space a': 'vim-mode-plus:insert-after-end-of-line'
    'space i': 'vim-mode-plus:insert-at-first-character-of-line'

To be clear, I think Vimscript is terrible as a programming language, but it is excellent as a configuration language. Despite puzzling keywords like inoremap, nothing quite compares with Vimscript in terms of easiness of configuring key maps (and some other editor settings).

Designing the Key Map Layer

Therefore, the next thing that I built for Vvvim is a configurable key map layer. A naive implementation only needs a dictionary mapping each keystroke before executing them, but that’s too boring. I want Vvvim’s key map as powerful as Vim’s. Therefore I need to implement:

  1. Both recursive and nonrecursive mappings. A recursive mapping can trigger other mappings before executing, whereas nonrecursive mapping triggers the mapped actions directly without consulting other mappings.

  2. Support for key sequences. In Vim, you can create mappings between sequences of keys, the most famous example being inoremap jk <Esc> which maps jk to Esc in insert mode. When the user presses the first j, the editor will not insert it immediately but wait for further keystrokes to decide which action to fire.

The reflexes from whiteboard interviews tell me that a prefix tree is no doubt the best data structure. Again, it is interesting to be able to apply those “interview knowledge” to a real engineering project.

Also, as mappings can be created for one specific mode, we need one prefix for each editor mode.

Evolution of PrefixTreeNode

Having recently finished my compiler assignments in C, my intuition tells me to use pointers and new for everything, like:

struct PrefixTreeNode {
    PrefixTreeNode *children_[ASCII_LENGTH]{nullptr};
    bool is_end_ = false;
    bool is_recursive = false;
    std::string target_;
};

While I was writing the destructor which recursively frees each node like usual, I decided to give std::unique_ptr a try. It feels great not to need to manage memory with bare hands (this almost feel like languages with GC).

struct PrefixTreeNode {
    std::vector<std::unique_ptr<PrefixTreeNode>> children_;
    bool is_end_ = false;
    bool is_recursive = false;
    std::string target_;
};

However, something doesn’t feel right. If each node is the unique owner of its children, and it never transfers ownership to anyone else, then why don’t we use an unordered_map<char, PrefixTreeNode> and store the subtree within the hash table?

struct PrefixTreeNode {
    std::unordered_map<char, PrefixTreeNode> children_;
    bool is_end_ = false;
    bool is_recursive = false;
    std::string target_;
};

PrefixTreeNode: This isn’t even my final form!

In the end I switched std::unordered_map to absl::flat_hash_map for the contains() function. I’m surprised by how a contains() method still isn’t a part of the current C++ standard in 2019.

Implementing Lookup

Initially, I chose a linear design (as one does), so these happen in time order:

  1. Keystroke
  2. ncurses getch()
  3. Key map layer (Repeat this step if the binding is recursive)
  4. Key action fired by ProcessKeyPress()

This worked well until I found one corner case. When there exists mapping:

nmap s iabc
imap b c

And the key s is pressed in normal mode, according to this logic the calls to ProcessKeyPress would be iabc in sequential order, but they should have been ibbc because the b should have triggered the insert mode mapping. Why? Because a mode switch happened within the mapped sequence and the key map layer does not know that. Of course, I can hardcode mode transition logic into the key map layer as well, but that would be quite ugly. Therefore I redesigned the key map layer to function like this:

ncurses         Editor               KeyMap     Editor
getch() -> MapAndExecuteKey ---------> Map --> ExecuteKey --> action
                  ^                     |
                  |                     |
                   <--- if recursive ---

Therefore, the signature of Map is now:

std::pair<KeyMap::Action, std::string> KeyMap::Map(EditorMode mode, char key)

Where Action is an enum that can be either:

  • EXECUTE_DIRECTLY: only used on noremap commands, execute the corresponding key actions directly
  • NEEDS_RECURSION: signals the caller of Map to pass the return value into this function again
  • NOTHING: do nothing

Class Members

PrefixTreeNode root_of_mode_[mode_count_]; // EditorMode -> PrefixTreeNode*
PrefixTreeNode *sequence_progress_ = &root_of_mode_[NORMAL];
EditorMode current_mode_ = NORMAL;
std::stringstream replay_; // For replaying keystrokes when sequence failed
  • One prefix tree is stored for each mode
  • sequence_progress is a pointer pointing to the progress in the current mode’s prefix tree
  • current_mode_ is used for resetting progress upon a mode switch
  • replay_ stores the current progress with a string stream so that when a binding fails to match, the key sequence will be returned as-is and marked NEEDS_RECURSION

Epilogue

With most of the infrastructure work finished, in the next episode, I’m finally going to build the actual key actions, spoiler alert: I thought it would be the most tedious part of the project, but it turned out to be the most exciting part yet.

Takeaways

  • Don’t manage memory with bare hands
  • Don’t use std::unique_ptr when you don’t need to transfer the ownership of the resource
  • Try to capture all the corner cases before you design the system

Next episode.