third-party/codemirror-3.15/doc/internals.html

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