At the end of the previous post, Matt and I finally got the bright idea to patch Vim. Both of us had experience contributing to open source projects, but we knew very little about contributing to Vim. To maximize our chance of success, we decided on a few guidelines:
- Our patch should make Vim better for everyone, not just us.
- Any new API we create should be familiar to as many developers as possible.
- We should make the minimum necessary change.
Step 0 was to clone Vim and start poking around. The Vim codebase is intimidating, to put it mildly. A quarter-century of development has created a text editor that, while powerful and extensible, is not without cruft. Vim was originally written for Amiga, and
os_amiga.c still exists. There appears to be support for VMX, 16-bit Windows, BeOS, and even MS-DOS.
As mentioned previously, Vim is input-driven. For the most part, Vim reacts to input from the user. There’s no easy way to tell Vim, “run this in 500 milliseconds” or “run this every 500 milliseconds.” There’s only, “run this after the user does X.” This assumption is built into every level of Vim, down to the architecture-specific input functions. We discovered this by following the code.
If you want to see for yourself, try building Vim and running it in
gdb. This example is slightly simplified. Most of the time, we used
gdb attach to avoid corrupting Vim’s terminal.
You’ll have to do this for a little while to get past Vim’s initialization code. You may also have to hit backspace to get rid of some control characters.
After playing around more in
gdb, we got a good idea of Vim’s control flow. Vim’s main loop is, naturally, a function called
main.c. There are a few ways the main loop can call low-level input functions, but eventually control is passed to
select(), or falls back to
select() isn’t available.
Running Vim in a GUI follows a different path, but it still boils down to one function:
Armed with our newfound knowledge, we set off to build
Our desired API was simple. The plan was to make three new Vimscript functions:
setinterval() would take a number in milliseconds and a command to evaluate. For example…
…would print “hello” after two seconds. Calling…
…would cancel the timeout. Nothing too crazy there.
Representing timeouts is pretty straightforward. Timeouts are run in order, so a linked-list sorted by time makes a lot of sense. There are more efficient data structures for timeouts, but this is a decent first-pass.
Ordered insertion is
O(n), but fortunately
n is very small in most cases.
Calling timeouts isn’t too complicated either. Just go through list until there’s an interval in the future.
Now all we have to do is run
call_timeouts() often enough and the job is done!
RealWaitForChar() can take a timeout, or it can block until there’s user input. The initial plan was to put a loop in
RealWaitForChar() and periodically run
call_timeouts() while waiting for user input.
Once we delved deeper into the code, we noticed much of our work was already done.
RealWaitForChar() had a loop in it. It even called
select(). To make our lives easier and minimize the number of changes, we decided to take advantage of this
The idea behind the loop is pretty simple: until
RealWaitForChar()’s timeout is reached, run
call_timeouts() every 100 milliseconds. The implementation in Vim is a little tricky, but a typical
select() loop looks like this:
This loop runs
call_timeouts() every 100 milliseconds, or more often if the user types something. Reducing
tv will give more accurate timer resolution at the cost of more CPU usage. It’s also possible to set
tv based on the next timeout in the linked list. If there are a few widely-spaced timeouts, this can be more efficient. On the other hand, it also makes it easier to waste tons of CPU time.
Submitting the Patch
Once we thought our work was ready for others to see, we posted the patch to Vim-dev. After some healthy discussion (and a little bikeshedding), we followed some suggestions to improve our patch. The biggest change was implementing cross-platform monotonic timers. It’s often forgotten that
gettimeofday() is not required to increase. A user can change the clock, causing timeouts to be called too early or too late. Worse, services like
ntpd can tweak the system clock without the user noticing. There is no cross-platform monotonic clock API, so we had to write code specific to Linux, OS X, BSD, and Windows.
We’ve learned a lot from this project, but we’re glad the finish line is in sight. There is no shortage of editors we want to support.