vim-snipe

Posted on
vim

Targeted linewise motions and edits in Vim.

I released vim-snipe today, which is a Vim plugin I use to make linewise motions and edits highly targeted and efficient. Currently several people have contributed bug reports and code.

What is Vim?

Vim1 is a modal text editor. It’s my favorite text editor as it overlays a grammar on text editing. I find that text manipulation is more efficient and pleasant when given a language for manipulating text. Beyond that, it keeps my hands on the keyboard, so I don’t have to clumsily poke around the screen with my mouse.

With a good set of plugins, and a terminal multiplexer like tmux, you can use Vim as a full blown IDE. If you don’t know about Vim, I’d recommend reading about it.

Motivation

vim-snipe has two goals: fast linewise edits and jumps.

Fast edits

I’m not the world’s best typist; I make a lot of mistakes when writing in Insert mode. I found that I kept performing the same Vim commands when fixing typos, which is an opportunity for automation.

Consider

“helol, wor”

where the cursor is at “r” (there’s some lag between when I make the typo and when I notice it, so the cursor is positioned ahead of the mistake). The steps to fix this are roughly

Normal mode commands Grammar What & why
mq Drop a mark named q This allows us to return to “r” after fixing the typo
Fl; Move the cursor to the first preceding “l” (Fl), then advance to the next one (;) This lands us at the “l” before “o”
xp Cut the token under the cursor (x), and paste it back (p) This has the effect of a swap, which fixes the typo
`q Move back to the mark q This brings us back to the original position “r”

This is fairly tedious, and doesn’t scale. For example, if there were many more “l”’s between the cursor and the typo, I’d have to manually count the number of advances in Step 2 leading to something like 6Fl, or hit Fl then keep typing ; until I reached the swap position.

When I’m typing, the last thing I want to do is disrupt my flow of thought; if I make a mistake, I want to be able to fix it as quickly and simply as possible.

Swapping isn’t the only common fix I find myself performing; there’s also:

  • replacing a character on the same line (example: typed “hemlo” instead of “hello”)
  • cutting a character on the same line (example: typed “helloo” instead of “hello”)
  • inserting a character on the same line (example: typed “helo” instead of “hello”)

Both of these require a similar amount of steps to perform (read: too many).

To save you the suspense, here’s what the final solution looks like for a swap (insert, replace and cut is similar):

Fix the typo 'smlal' by swapping a previous instance of 'l'

Fix the typo 'smlal' by swapping a previous instance of 'l'

Targeted jumps

Considering the problem above, a key part of a general solution is simplifying linewise navigation. More specifically, the problem to solve is

being able to jump backwards or forwards to any specified character or word boundary with minimal keystrokes and cognitive overhead.

Given this, Step 2 above would be require the same amount of keystrokes no matter how many “l”’s were between the cursor and the swap position.

Actually, this is a problem that I’d wanted to solve previously, but couldn’t find any good existing solutions for. Solving it means taking advantage of the fact that I almost always know where I want to go, but am forced to navigate incrementally there using ‘;’, or manually count the prefix of the motion (i.e. 5e), which is inefficient and disruptive.

The final solution - which has already been implemented by plugins like tmux-fingers - highlights the possible jump targets with a key, which the user then presses to get there.2

This is what it looks like:

Jump to the last 'o', with several in the way

Jump to the last 'o', with several in the way

Jumping to the end of 'to'

Jumping to the end of 'to'

Is this a solved problem?

The two plugins with the most overlap in concern are

Stupid-Easymotion (a fork of vim-easymotion) has an incomplete API: it’s missing mappings for most of the character and word motions in Vim (there are 11 cases that need to be handled, and it only handles 3). It has no support for targeted edits, and hasn’t seen any activity in a long time - 4+ years at the time of this writing.

vim-easymotion has a similarly incomplete (albeit less incomplete) API. Furthermore, it scans the entire buffer when performing word motions, which is inefficient and unnecessary with the advent of set relativenumber in recent versions of Vim.

It’s also sprawling (having 5000+ lines of code), and I’ve encountered some surprising quality issues while browsing it. Extending it would be unpleasant.

Implementation

Having determined that I’d have to write my own solution, I set out with the following goals for the software, in ascending order of priority:

  1. it should work, i.e. solve all my use cases
  2. it should be as small and focused as possible
  3. it should be easy to use

Preamble: help!

I was going to be spending a lot of time in Vimscript, which means a lot of time in Vim documentation, which is itself executed in Vim. I created the following mapping:

function! s:Help(type)
  if a:type ==# 'v'
    normal! `<v`>y
  elseif a:type ==# 'char'
    normal! `[v`]y
  else
    return
  endif
  let saved = @@
  silent execute "h " . @@
  let @@ = saved
endfunction
augroup vimscript
  autocmd!
  "
  " ...unimportant autocommands...
  "
  " F1 = help
  autocmd FileType vim vnoremap <F1> :<c-u>call <SID>Help(visualmode())<cr>
  autocmd FileType vim nnoremap <F1> :set operatorfunc=<SID>Help<cr>g@
  autocmd FileType vim nnoremap <F1><F1> :h <c-r><c-w><cr>
augroup END

This allows me to consult the help documentation more efficiently, as it gives me three options:

  • I can put my cursor on top of a <word>, press F1 twice, and Vim’s help documentation will pop up for that word
  • it’s a Vim operator so it can serve as a verb in the Vim grammar, i.e. I can say “open the documentation for what’s under the cursor until the next occurrence of ‘x’” (the command for this is <F1>tx)
  • I can highlight anything in Visual mode and press F1 to get help on it

A few weeks ago, I also wrote a command line tool to perform Google searches from the command line. I integrated it into my Vim workflow, with

function! s:Google(type)
  let saved = @@
  if a:type ==# 'V'
    normal! `<V`>y
  elseif a:type ==# 'v'
    normal! `<v`>y
  elseif a:type ==# 'char'
    normal! `[v`]y
  else
    return
  endif
  " remove trailing newline
  "
  "   https://stackoverflow.com/a/6228454
  let @@ = substitute(strtrans(@@), '\^@', '', 'g')
  call system('g ' . shellescape(@@))
  let @@ = saved
endfunction
vnoremap <F2> :<c-u>call <SID>Google(visualmode())<cr>
nnoremap <F2> :set operatorfunc=<SID>Google<cr>g@
nnoremap <F2><F2> :silent !g <c-r><c-w><cr>

This allowed me to execute Google queries with F2 in an efficient manner identical to the above.

Implementation notes

I studied the critical sections of vim-easymotion and realized I needed to borrow and revise only two things:

  • the algorithm for building the n-ary jump tree, which describes how the the jump targets are mapped to key sequences (highlighted yellow in the images above)
  • the highlighting initialization, which isn’t key or interesting, and thus which I was happy to cargo-cult

The important part was building the jump tree and flattening that data structure into a dictionary. This is the core data structure that’s consumed by the rest of the plugin code.

It’s useful to set expectations for what the tree should look like for various inputs and outputs. We optimize for the case where the jump target is reasonably close to the cursor, preferring a minimal key sequence in this case. (Actually, the jump functionality is most useful and thus most expected to be triggered for faraway jumps, but the alphabet size is usually larger than the number of targets, rendering this moot.)

Assume we have 4 possible jump tokens, this would be configured with let g:snipe_jump_tokens = 'abcd'.

Assume we have 4 targets on a line, occurring at columns 1, 3, 7 and 10. Then they should be highlighted in the order a, b, c, d. The expected jump tree in this case would be {'a': 1, 'b': 3, 'c': 7, 'd': 10}. (This means the user needs to hit a to get to column 1, b to get to column 3, etc.)

If we have 5 targets on a line, occurring at columns 1, 3, 7, 10, 14, then they should be highlighted in the order a, b, c, da, db. The expected jump tree in this case would be {'a': 1, 'b': 3, 'c': 7, 'd': {'a': 10, 'b': 14}}.

With this in mind, here’s the algorithm that builds the jump tree:

function! s:GetJumpTree(targets) " {{{
  let tree = {}

  " i: index into targets
  " j: index into jump tokens
  let i = 0
  let j = 0
  for n_children in s:GetHitCounts(len(a:targets))
    let node = g:snipe_jump_tokens[j]
    if n_children == 1
      let tree[node] = a:targets[i]
    elseif n_children > 1
      let tree[node] = s:GetJumpTree(a:targets[i:i + n_children - 1])
    else
      continue
    endif
    let j += 1
    let i += n_children
  endfor
  return tree
endfunction
" }}}

This returns a tree where the non-leaf nodes are jump tokens, and leaves are column numbers, which are the positions of the targets. Each level of the tree is filled such that the average path depth of the tree is minimized and the closest targets come first.

The helper function GetTargetCounts is shown below:

function! s:GetTargetCounts(targets_rem) " {{{
  let n_jump_tokens = len(g:snipe_jump_tokens)
  let n_targets = repeat([0], n_jump_tokens)
  let targets_rem = a:targets_rem

  let is_first_lvl = 1
  while targets_rem > 0
    " if we can't fit all the targets in the first lvl,
    " fit the remainder starting from the last jump token
    let n_children = is_first_lvl
          \ ? 1
          \ : n_jump_tokens - 1
    for j in range(n_jump_tokens)
      let n_targets[j] += n_children
      let targets_rem -= n_children
      if targets_rem <= 0
        let n_targets[j] += targets_rem
        break
      endif
    endfor
    let is_first_lvl = 0
  endwhile

  return reverse(n_targets)
endfunction
" }}}

This returns a list in bijective correspondence with the jump token alphabet. Each count represents how many targets are in the subtree rooted at the corresponding jump token.

The core idea came from vim-easymotion, but I was able to simplify it considerably.

The algorithms are straightforward, just simple recursion and iteration, but correctness - measured against the examples above - isn’t obvious. The best way to convince yourself is to step through the code for each case.

Finally, a textbook recursion flattens the tree. For our two examples above, respectively, they’d produce {'a': 1, 'b': 3, 'c': 7, 'd': 10} and {'a': 1, 'b': 3, 'c': 7, 'da': 10, 'db': 14} respectively.

function! s:GetJumpDict(jump_tree, ...) " {{{
  " returns a map of the jump key sequence to its jump position
  let dict = {}
  let prev_key = a:0 == 1 ? a:1 : ''

  for [jump_key, node] in items(a:jump_tree)
    let next_key = prev_key . jump_key
    if type(node) == v:t_number
      let dict[next_key] = node
    else
      call extend(dict, s:GetJumpDict(node, next_key))
    endif
  endfor

  return dict
endfunction
" }}}

The next most interesting part of the code is how this data structure is consumed to highlight the jump targets with their sequences and perform the jump or edit. As you might have guessed, we use recursion, but I’d rather not bore you with the technical details. If you’re really interested, consult the source.

Hello, world!

I finished vim-snipe, but I was still working in a vacuum. I knew it was useful for me, so I shared it online, and got some feedback from the Vim community.

I was reminded of some useful things:

  • I can’t assume software documentation that’s clear to me will be clear to others
  • writing comprehensive yet concise documentation is as important and challenging as doing the same for code
  • other people may have use for my work
  • other people may not have use for my work, but hopefully they can say so in a non-disparaging way
  • users and contributors are critical to improving software

Was it worth it?

I didn’t have huge expectations going into the project, so I was glad it was reasonably well-received, judging from the external contributions and feedback.

I use vim-snipe constantly in Vim (but not all the time - I’m an advocate for using the right tool for the right job), it simplifies my workflow, makes writing and editing more enjoyable and efficient, and I’ve acquired a working knowledge of Vimscript. I’m happy with the result.

All the goals I set at the outset have been met3. Best of all, I solved yet another of my (first-world) problems myself, and improved others’ lives in the process of doing so! It feels good to give back to a community that’s given me so much.


  1. Technically I use neovim, which is a fork of Vim. [return]
  2. What happens when the number of possible targets exceeds the number of unique keys? In this case we use a sequence of keys. Note that we only show the first token in the sequence (credit goes to @ychin), and update the highlighting with the next token in the sequence when the user makes a key choice. This is a new implementation, and it’s simpler from a user and code standpoint. [return]
  3. Note that the total lines of code in the plugin is at the time of this writing about 300, which is very small. [return]