4
<title>CodeMirror: Internals</title>
5
<link rel="stylesheet" type="text/css" href="http://fonts.googleapis.com/css?family=Droid+Sans|Droid+Sans:bold"/>
6
<link rel="stylesheet" type="text/css" href="docs.css"/>
7
<meta http-equiv="Content-Type" content="text/html; charset=utf-8"/>
8
<style>dl dl {margin: 0;} .update {color: #d40 !important}</style>
12
<h1><span class="logo-braces">{ }</span> <a href="http://codemirror.net/">CodeMirror</a></h1>
15
<img src="baboon.png" class="logo" alt="logo"/>/* (Re-) Implementing A Syntax-
16
Highlighting Editor in JavaScript */
19
<div class="clear"><div class="leftbig blk">
21
<p style="font-size: 85%" id="intro">
22
<strong>Topic:</strong> JavaScript, code editor implementation<br>
23
<strong>Author:</strong> Marijn Haverbeke<br>
24
<strong>Date:</strong> March 2nd 2011 (updated November 13th 2011)
27
<p>This is a followup to
28
my <a href="http://codemirror.net/story.html">Brutal Odyssey to the
29
Dark Side of the DOM Tree</a> story. That one describes the
30
mind-bending process of implementing (what would become) CodeMirror 1.
31
This one describes the internals of CodeMirror 2, a complete rewrite
32
and rethink of the old code base. I wanted to give this piece another
33
Hunter Thompson copycat subtitle, but somehow that would be out of
34
place—the process this time around was one of straightforward
35
engineering, requiring no serious mind-bending whatsoever.</p>
37
<p>So, what is wrong with CodeMirror 1? I'd estimate, by mailing list
38
activity and general search-engine presence, that it has been
39
integrated into about a thousand systems by now. The most prominent
40
one, since a few weeks,
41
being <a href="http://googlecode.blogspot.com/2011/01/make-quick-fixes-quicker-on-google.html">Google
42
code's project hosting</a>. It works, and it's being used widely.</a>
44
<p>Still, I did not start replacing it because I was bored. CodeMirror
45
1 was heavily reliant on <code>designMode</code>
46
or <code>contentEditable</code> (depending on the browser). Neither of
47
these are well specified (HTML5 tries
48
to <a href="http://www.w3.org/TR/html5/editing.html#contenteditable">specify</a>
49
their basics), and, more importantly, they tend to be one of the more
50
obscure and buggy areas of browser functionality—CodeMirror, by using
51
this functionality in a non-typical way, was constantly running up
52
against browser bugs. WebKit wouldn't show an empty line at the end of
53
the document, and in some releases would suddenly get unbearably slow.
54
Firefox would show the cursor in the wrong place. Internet Explorer
55
would insist on linkifying everything that looked like a URL or email
56
address, a behaviour that can't be turned off. Some bugs I managed to
57
work around (which was often a frustrating, painful process), others,
58
such as the Firefox cursor placement, I gave up on, and had to tell
59
user after user that they were known problems, but not something I
62
<p>Also, there is the fact that <code>designMode</code> (which seemed
63
to be less buggy than <code>contentEditable</code> in Webkit and
64
Firefox, and was thus used by CodeMirror 1 in those browsers) requires
65
a frame. Frames are another tricky area. It takes some effort to
66
prevent getting tripped up by domain restrictions, they don't
67
initialize synchronously, behave strangely in response to the back
68
button, and, on several browsers, can't be moved around the DOM
69
without having them re-initialize. They did provide a very nice way to
70
namespace the library, though—CodeMirror 1 could freely pollute the
71
namespace inside the frame.</p>
73
<p>Finally, working with an editable document means working with
74
selection in arbitrary DOM structures. Internet Explorer (8 and
75
before) has an utterly different (and awkward) selection API than all
76
of the other browsers, and even among the different implementations of
77
<code>document.selection</code>, details about how exactly a selection
78
is represented vary quite a bit. Add to that the fact that Opera's
79
selection support tended to be very buggy until recently, and you can
80
imagine why CodeMirror 1 contains 700 lines of selection-handling
83
<p>And that brings us to the main issue with the CodeMirror 1
84
code base: The proportion of browser-bug-workarounds to real
85
application code was getting dangerously high. By building on top of a
86
few dodgy features, I put the system in a vulnerable position—any
87
incompatibility and bugginess in these features, I had to paper over
88
with my own code. Not only did I have to do some serious stunt-work to
89
get it to work on older browsers (as detailed in the
90
previous <a href="http://codemirror.net/story.html">story</a>), things
91
also kept breaking in newly released versions, requiring me to come up
92
with <em>new</em> scary hacks in order to keep up. This was starting
93
to lose its appeal.</p>
95
<h2 id="approach">General Approach</h2>
97
<p>What CodeMirror 2 does is try to sidestep most of the hairy hacks
98
that came up in version 1. I owe a lot to the
99
<a href="http://ace.ajax.org">ACE</a> editor for inspiration on how to
102
<p>I absolutely did not want to be completely reliant on key events to
103
generate my input. Every JavaScript programmer knows that key event
104
information is horrible and incomplete. Some people (most awesomely
105
Mihai Bazon with <a href="http://ymacs.org">Ymacs</a>) have been able
106
to build more or less functioning editors by directly reading key
107
events, but it takes a lot of work (the kind of never-ending, fragile
108
work I described earlier), and will never be able to properly support
109
things like multi-keystoke international character
110
input. <a href="#keymap" class="update">[see below for caveat]</a></p>
112
<p>So what I do is focus a hidden textarea, and let the browser
113
believe that the user is typing into that. What we show to the user is
114
a DOM structure we built to represent his document. If this is updated
115
quickly enough, and shows some kind of believable cursor, it feels
116
like a real text-input control.</p>
118
<p>Another big win is that this DOM representation does not have to
119
span the whole document. Some CodeMirror 1 users insisted that they
120
needed to put a 30 thousand line XML document into CodeMirror. Putting
121
all that into the DOM takes a while, especially since, for some
122
reason, an editable DOM tree is slower than a normal one on most
123
browsers. If we have full control over what we show, we must only
124
ensure that the visible part of the document has been added, and can
125
do the rest only when needed. (Fortunately, the <code>onscroll</code>
126
event works almost the same on all browsers, and lends itself well to
127
displaying things only as they are scrolled into view.)</p>
129
<h2 id="input">Input</h2>
131
<p>ACE uses its hidden textarea only as a text input shim, and does
132
all cursor movement and things like text deletion itself by directly
133
handling key events. CodeMirror's way is to let the browser do its
134
thing as much as possible, and not, for example, define its own set of
135
key bindings. One way to do this would have been to have the whole
136
document inside the hidden textarea, and after each key event update
137
the display DOM to reflect what's in that textarea.</p>
139
<p>That'd be simple, but it is not realistic. For even medium-sized
140
document the editor would be constantly munging huge strings, and get
141
terribly slow. What CodeMirror 2 does is put the current selection,
142
along with an extra line on the top and on the bottom, into the
145
<p>This means that the arrow keys (and their ctrl-variations), home,
146
end, etcetera, do not have to be handled specially. We just read the
147
cursor position in the textarea, and update our cursor to match it.
148
Also, copy and paste work pretty much for free, and people get their
149
native key bindings, without any special work on my part. For example,
150
I have emacs key bindings configured for Chrome and Firefox. There is
151
no way for a script to detect this. <a class="update"
152
href="#keymap">[no longer the case]</a></p>
154
<p>Of course, since only a small part of the document sits in the
155
textarea, keys like page up and ctrl-end won't do the right thing.
156
CodeMirror is catching those events and handling them itself.</p>
158
<h2 id="selection">Selection</h2>
160
<p>Getting and setting the selection range of a textarea in modern
161
browsers is trivial—you just use the <code>selectionStart</code>
162
and <code>selectionEnd</code> properties. On IE you have to do some
163
insane stuff with temporary ranges and compensating for the fact that
164
moving the selection by a 'character' will treat \r\n as a single
165
character, but even there it is possible to build functions that
166
reliably set and get the selection range.</p>
168
<p>But consider this typical case: When I'm somewhere in my document,
169
press shift, and press the up arrow, something gets selected. Then, if
170
I, still holding shift, press the up arrow again, the top of my
171
selection is adjusted. The selection remembers where its <em>head</em>
172
and its <em>anchor</em> are, and moves the head when we shift-move.
173
This is a generally accepted property of selections, and done right by
174
every editing component built in the past twenty years.</p>
176
<p>But not something that the browser selection APIs expose.</p>
178
<p>Great. So when someone creates an 'upside-down' selection, the next
179
time CodeMirror has to update the textarea, it'll re-create the
180
selection as an 'upside-up' selection, with the anchor at the top, and
181
the next cursor motion will behave in an unexpected way—our second
182
up-arrow press in the example above will not do anything, since it is
183
interpreted in exactly the same way as the first.</p>
185
<p>No problem. We'll just, ehm, detect that the selection is
186
upside-down (you can tell by the way it was created), and then, when
187
an upside-down selection is present, and a cursor-moving key is
188
pressed in combination with shift, we quickly collapse the selection
189
in the textarea to its start, allow the key to take effect, and then
190
combine its new head with its old anchor to get the <em>real</em>
193
<p>In short, scary hacks could not be avoided entirely in CodeMirror
196
<p>And, the observant reader might ask, how do you even know that a
197
key combo is a cursor-moving combo, if you claim you support any
198
native key bindings? Well, we don't, but we can learn. The editor
199
keeps a set known cursor-movement combos (initialized to the
200
predictable defaults), and updates this set when it observes that
201
pressing a certain key had (only) the effect of moving the cursor.
202
This, of course, doesn't work if the first time the key is used was
203
for extending an inverted selection, but it works most of the
206
<h2 id="update">Intelligent Updating</h2>
208
<p>One thing that always comes up when you have a complicated internal
209
state that's reflected in some user-visible external representation
210
(in this case, the displayed code and the textarea's content) is
211
keeping the two in sync. The naive way is to just update the display
212
every time you change your state, but this is not only error prone
213
(you'll forget), it also easily leads to duplicate work on big,
214
composite operations. Then you start passing around flags indicating
215
whether the display should be updated in an attempt to be efficient
216
again and, well, at that point you might as well give up completely.</p>
218
<p>I did go down that road, but then switched to a much simpler model:
219
simply keep track of all the things that have been changed during an
220
action, and then, only at the end, use this information to update the
221
user-visible display.</p>
223
<p>CodeMirror uses a concept of <em>operations</em>, which start by
224
calling a specific set-up function that clears the state and end by
225
calling another function that reads this state and does the required
226
updating. Most event handlers, and all the user-visible methods that
227
change state are wrapped like this. There's a method
228
called <code>operation</code> that accepts a function, and returns
229
another function that wraps the given function as an operation.</p>
231
<p>It's trivial to extend this (as CodeMirror does) to detect nesting,
232
and, when an operation is started inside an operation, simply
233
increment the nesting count, and only do the updating when this count
234
reaches zero again.</p>
236
<p>If we have a set of changed ranges and know the currently shown
237
range, we can (with some awkward code to deal with the fact that
238
changes can add and remove lines, so we're dealing with a changing
239
coordinate system) construct a map of the ranges that were left
240
intact. We can then compare this map with the part of the document
241
that's currently visible (based on scroll offset and editor height) to
242
determine whether something needs to be updated.</p>
244
<p>CodeMirror uses two update algorithms—a full refresh, where it just
245
discards the whole part of the DOM that contains the edited text and
246
rebuilds it, and a patch algorithm, where it uses the information
247
about changed and intact ranges to update only the out-of-date parts
248
of the DOM. When more than 30 percent (which is the current heuristic,
249
might change) of the lines need to be updated, the full refresh is
250
chosen (since it's faster to do than painstakingly finding and
251
updating all the changed lines), in the other case it does the
252
patching (so that, if you scroll a line or select another character,
253
the whole screen doesn't have to be
254
re-rendered). <span class="update">[the full-refresh
255
algorithm was dropped, it wasn't really faster than the patching
258
<p>All updating uses <code>innerHTML</code> rather than direct DOM
259
manipulation, since that still seems to be by far the fastest way to
260
build documents. There's a per-line function that combines the
261
highlighting, <a href="manual.html#markText">marking</a>, and
262
selection info for that line into a snippet of HTML. The patch updater
263
uses this to reset individual lines, the refresh updater builds an
264
HTML chunk for the whole visible document at once, and then uses a
265
single <code>innerHTML</code> update to do the refresh.</p>
267
<h2 id="parse">Parsers can be Simple</h2>
269
<p>When I wrote CodeMirror 1, I
270
thought <a href="http://codemirror.net/story.html#parser">interruptable
271
parsers</a> were a hugely scary and complicated thing, and I used a
272
bunch of heavyweight abstractions to keep this supposed complexity
273
under control: parsers
274
were <a href="http://bob.pythonmac.org/archives/2005/07/06/iteration-in-javascript/">iterators</a>
275
that consumed input from another iterator, and used funny
276
closure-resetting tricks to copy and resume themselves.</p>
278
<p>This made for a rather nice system, in that parsers formed strictly
279
separate modules, and could be composed in predictable ways.
280
Unfortunately, it was quite slow (stacking three or four iterators on
281
top of each other), and extremely intimidating to people not used to a
282
functional programming style.</p>
284
<p>With a few small changes, however, we can keep all those
285
advantages, but simplify the API and make the whole thing less
286
indirect and inefficient. CodeMirror
287
2's <a href="manual.html#modeapi">mode API</a> uses explicit state
288
objects, and makes the parser/tokenizer a function that simply takes a
289
state and a character stream abstraction, advances the stream one
290
token, and returns the way the token should be styled. This state may
291
be copied, optionally in a mode-defined way, in order to be able to
292
continue a parse at a given point. Even someone who's never touched a
293
lambda in his life can understand this approach. Additionally, far
294
fewer objects are allocated in the course of parsing now.</p>
296
<p>The biggest speedup comes from the fact that the parsing no longer
297
has to touch the DOM though. In CodeMirror 1, on an older browser, you
298
could <em>see</em> the parser work its way through the document,
299
managing some twenty lines in each 50-millisecond time slice it got. It
300
was reading its input from the DOM, and updating the DOM as it went
301
along, which any experienced JavaScript programmer will immediately
302
spot as a recipe for slowness. In CodeMirror 2, the parser usually
303
finishes the whole document in a single 100-millisecond time slice—it
304
manages some 1500 lines during that time on Chrome. All it has to do
305
is munge strings, so there is no real reason for it to be slow
308
<h2 id="summary">What Gives?</h2>
310
<p>Given all this, what can you expect from CodeMirror 2?</p>
314
<li><strong>Small.</strong> the base library is
315
some <span class="update">45k</span> when minified
316
now, <span class="update">17k</span> when gzipped. It's smaller than
319
<li><strong>Lightweight.</strong> CodeMirror 2 initializes very
320
quickly, and does almost no work when it is not focused. This means
321
you can treat it almost like a textarea, have multiple instances on a
322
page without trouble.</li>
324
<li><strong>Huge document support.</strong> Since highlighting is
325
really fast, and no DOM structure is being built for non-visible
326
content, you don't have to worry about locking up your browser when a
327
user enters a megabyte-sized document.</li>
329
<li><strong>Extended API.</strong> Some things kept coming up in the
330
mailing list, such as marking pieces of text or lines, which were
331
extremely hard to do with CodeMirror 1. The new version has proper
332
support for these built in.</li>
334
<li><strong>Tab support.</strong> Tabs inside editable documents were,
335
for some reason, a no-go. At least six different people announced they
336
were going to add tab support to CodeMirror 1, none survived (I mean,
337
none delivered a working version). CodeMirror 2 no longer removes tabs
338
from your document.</li>
340
<li><strong>Sane styling.</strong> <code>iframe</code> nodes aren't
341
really known for respecting document flow. Now that an editor instance
342
is a plain <code>div</code> element, it is much easier to size it to
343
fit the surrounding elements. You don't even have to make it scroll if
344
you do not <a href="../demo/resize.html">want to</a>.</li>
348
<p>On the downside, a CodeMirror 2 instance is <em>not</em> a native
349
editable component. Though it does its best to emulate such a
350
component as much as possible, there is functionality that browsers
351
just do not allow us to hook into. Doing select-all from the context
352
menu, for example, is not currently detected by CodeMirror.</p>
354
<p id="changes" style="margin-top: 2em;"><span style="font-weight:
355
bold">[Updates from November 13th 2011]</span> Recently, I've made
356
some changes to the codebase that cause some of the text above to no
357
longer be current. I've left the text intact, but added markers at the
358
passages that are now inaccurate. The new situation is described
361
<h2 id="btree">Content Representation</h2>
363
<p>The original implementation of CodeMirror 2 represented the
364
document as a flat array of line objects. This worked well—splicing
365
arrays will require the part of the array after the splice to be
366
moved, but this is basically just a simple <code>memmove</code> of a
367
bunch of pointers, so it is cheap even for huge documents.</p>
369
<p>However, I recently added line wrapping and code folding (line
370
collapsing, basically). Once lines start taking up a non-constant
371
amount of vertical space, looking up a line by vertical position
372
(which is needed when someone clicks the document, and to determine
373
the visible part of the document during scrolling) can only be done
374
with a linear scan through the whole array, summing up line heights as
375
you go. Seeing how I've been going out of my way to make big documents
376
fast, this is not acceptable.</p>
378
<p>The new representation is based on a B-tree. The leaves of the tree
379
contain arrays of line objects, with a fixed minimum and maximum size,
380
and the non-leaf nodes simply hold arrays of child nodes. Each node
381
stores both the amount of lines that live below them and the vertical
382
space taken up by these lines. This allows the tree to be indexed both
383
by line number and by vertical position, and all access has
384
logarithmic complexity in relation to the document size.</p>
386
<p>I gave line objects and tree nodes parent pointers, to the node
387
above them. When a line has to update its height, it can simply walk
388
these pointers to the top of the tree, adding or subtracting the
389
difference in height from each node it encounters. The parent pointers
390
also make it cheaper (in complexity terms, the difference is probably
391
tiny in normal-sized documents) to find the current line number when
392
given a line object. In the old approach, the whole document array had
393
to be searched. Now, we can just walk up the tree and count the sizes
394
of the nodes coming before us at each level.</p>
396
<p>I chose B-trees, not regular binary trees, mostly because they
397
allow for very fast bulk insertions and deletions. When there is a big
398
change to a document, it typically involves adding, deleting, or
399
replacing a chunk of subsequent lines. In a regular balanced tree, all
400
these inserts or deletes would have to be done separately, which could
401
be really expensive. In a B-tree, to insert a chunk, you just walk
402
down the tree once to find where it should go, insert them all in one
403
shot, and then break up the node if needed. This breaking up might
404
involve breaking up nodes further up, but only requires a single pass
405
back up the tree. For deletion, I'm somewhat lax in keeping things
406
balanced—I just collapse nodes into a leaf when their child count goes
407
below a given number. This means that there are some weird editing
408
patterns that may result in a seriously unbalanced tree, but even such
409
an unbalanced tree will perform well, unless you spend a day making
410
strangely repeating edits to a really big document.</p>
412
<h2 id="keymap">Keymaps</h2>
414
<p><a href="#approach">Above</a>, I claimed that directly catching key
415
events for things like cursor movement is impractical because it
416
requires some browser-specific kludges. I then proceeded to explain
417
some awful <a href="#selection">hacks</a> that were needed to make it
418
possible for the selection changes to be detected through the
419
textarea. In fact, the second hack is about as bad as the first.</p>
421
<p>On top of that, in the presence of user-configurable tab sizes and
422
collapsed and wrapped lines, lining up cursor movement in the textarea
423
with what's visible on the screen becomes a nightmare. Thus, I've
424
decided to move to a model where the textarea's selection is no longer
427
<p>So I moved to a model where all cursor movement is handled by my
428
own code. This adds support for a goal column, proper interaction of
429
cursor movement with collapsed lines, and makes it possible for
430
vertical movement to move through wrapped lines properly, instead of
431
just treating them like non-wrapped lines.</p>
433
<p>The key event handlers now translate the key event into a string,
434
something like <code>Ctrl-Home</code> or <code>Shift-Cmd-R</code>, and
435
use that string to look up an action to perform. To make keybinding
436
customizable, this lookup goes through
437
a <a href="manual.html#option_keyMap">table</a>, using a scheme that
438
allows such tables to be chained together (for example, the default
439
Mac bindings fall through to a table named 'emacsy', which defines
440
basic Emacs-style bindings like <code>Ctrl-F</code>, and which is also
441
used by the custom Emacs bindings).</p>
444
option <a href="manual.html#option_extraKeys"><code>extraKeys</code></a>
445
allows ad-hoc keybindings to be defined in a much nicer way than what
446
was possible with the
447
old <a href="manual.html#option_onKeyEvent"><code>onKeyEvent</code></a>
448
callback. You simply provide an object mapping key identifiers to
449
functions, instead of painstakingly looking at raw key events.</p>
451
<p>Built-in commands map to strings, rather than functions, for
452
example <code>"goLineUp"</code> is the default action bound to the up
453
arrow key. This allows new keymaps to refer to them without
454
duplicating any code. New commands can be defined by assigning to
455
the <code>CodeMirror.commands</code> object, which maps such commands
458
<p>The hidden textarea now only holds the current selection, with no
459
extra characters around it. This has a nice advantage: polling for
460
input becomes much, much faster. If there's a big selection, this text
461
does not have to be read from the textarea every time—when we poll,
462
just noticing that something is still selected is enough to tell us
463
that no new text was typed.</p>
465
<p>The reason that cheap polling is important is that many browsers do
466
not fire useful events on IME (input method engine) input, which is
467
the thing where people inputting a language like Japanese or Chinese
468
use multiple keystrokes to create a character or sequence of
469
characters. Most modern browsers fire <code>input</code> when the
470
composing is finished, but many don't fire anything when the character
471
is updated <em>during</em> composition. So we poll, whenever the
472
editor is focused, to provide immediate updates of the display.</p>
474
</div><div class="rightsmall blk">
479
<li><a href="#intro">Introduction</a></li>
480
<li><a href="#approach">General Approach</a></li>
481
<li><a href="#input">Input</a></li>
482
<li><a href="#selection">Selection</a></li>
483
<li><a href="#update">Intelligent Updating</a></li>
484
<li><a href="#parse">Parsing</a></li>
485
<li><a href="#summary">What Gives?</a></li>
486
<li><a href="#btree">Content Representation</a></li>
487
<li><a href="#keymap">Key Maps</a></li>
492
<div style="height: 2em"> </div>
added
removed
doc/internals.html
