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