This article discusses algorithms for implementing text editors. You may perhaps think that such a subject is passe: "Why do I need to know about this? My nifty new programming language (or class library or application framework) lets me write a text-editor application in just 12 lines of code." That may be true--and if your application's text-editing requirements are fully satisfied by the built-in edit widget that came with your programming environment--then party on, dude.
But, in the Windows environment at least, most text-editing chores ultimately fall on the shoulders of the built-in Edit control, which is poorly equipped to handle tasks like tabbing, multiple fonts and point sizes, and large files. Those 12 lines of code using your whizzy class library are often just the overhead for invoking a class that ultimately invokes the built-in Edit control.
Ironically, the genesis for this article was a conversation with the designer of an award-winning app framework, in which I was asked to suggest articles on text-editor algorithms that could be of help in creating a more powerful text-edit class for his tool. It turns out there isn't much written on the subject, despite the dozens of public-domain editors available in source-code form. Instead, there is an oral history of text-editor algorithms, passed down from master to novice as part of a rite of passage.
The Simplest Case
Let's consider the simplest example of text editing. Listing One consists of one routine, EditLine(), which allows the user to edit a single line of text on the screen. Chances are you've written a routine resembling this. The sample spreadsheet program in Borland's Turbo C++ package, for example, has a similar routine (and, in fact, this example is an adaptation of that routine).
Listing One
/* EditLine() -- The simplest text editing routine */
void EditLine(char* buffer, int max_length, int curr_row)
{
int c, str_length = strlen(buffer), curr_column = str_length,
insert_mode = TRUE;
ChangeCursorShape(insert_mode);
do
{ vt_ClearLineAt(curr_row,0);
vt_OutputStringAt(buffer, curr_row,0);
vt_SetCursorPositionAt(curr_row,curr_column);
switch(c = vt_GetKeystroke()) /* dispatch on user's keystroke */
{
/*-------- keystrokes that terminate the editing session-----*/
case ESCAPE_KEY:
case ENTER_KEY: break;
/*--------- keystrokes that merely change the cursor position---*/
case HOME_KEY: curr_column = 0; break;
case END_KEY: curr_column = str_length; break;
case LEFT_KEY: if (curr_column > 0) curr_column--; break;
case RIGHT_KEY: if (curr_column < str_length) curr_column++;
break;
case INSERT_KEY: insert_mode = !insert_mode;
ChangeCursorShape(insert_mode);
break;
/*------ keystrokes that alter the contents of the buffer----*/
case BACKSPACE_KEY: if (curr_column > 0)
{
movmem( &buffer[curr_column], /*source*/
&buffer[curr_column-1], /*dest*/
str_length - curr_column + 1);
curr_column--;
str_length--;
}
break;
case DELETE_KEY: if (curr_column < str_length)
{
movmem( &buffer[curr_column+1], /*source*/
&buffer[curr_column], /*dest*/
str_length - curr_column);
str_length--;
}
break;
default: if (((c >= ' ') && (c <= '~')) &&
(str_length < max_length))
{
if (insert_mode)
{
movmem(
&buffer[curr_column],
&buffer[curr_column + 1],
str_length - curr_column + 1);
str_length++;
}
else if (curr_column >= str_length)
str_length++;
buffer[curr_column] = c;
curr_column++;
}
break;
}
buffer[str_length] = '\0';
}
while ((c != ENTER_KEY) && (c != ESCAPE_KEY));
}
EditLine() accomplishes, in scaled-down form, many of the basic tasks that required of a full-fledged text editor:
- Display the initial contents of the text buffer on the screen.
- Get a keystroke from the user.
- If the keystroke is a command (like delete or backspace), dispatch or carry out that command.
- If the keystroke is a character, insert it into the text buffer (or replace the current character if not in insert mode).
- Display the updated contents of the text buffer on the screen.
This sequence repeats endlessly until the Return key is pressed, providing us with the most primitive example of an event-driven program.
In looking at the code, you'll notice that this routine does a lot of unnecessary work (which, in the case of small amounts of text, does not impact the user). For example, when only the cursor is moved and no text has changed, the entire line of text is cleared and redrawn. Further, the same happens in cases where only one character has changed. Likewise, when a character is deleted, it's only necessary to display the text on the right-hand side of the cursor. Not printed here, but included with the electronic version of the listings (see "Availability," page 5), is an improved EditLine2() routine, which contains these and other obvious optimizations.
Scaling Up to Spaghetti
Although a full-fledged word processor or commercial desktop-publishing program is in some sense a beefed-up version of EditLine(), it isn't a trivial matter to scale up this routine to a real program. Time and again, novice programmers have followed the garden path of extrapolating from this simple function into a full-screen text editor via incremental improvements. Sometimes the result is eminently usable, but just as often the program collapses under the accumulated weight of haphazard changes. Those who persist end up rediscovering many of the architectural principles and algorithms described here.
Because text editors aren't traditional subjects for computer-science textbooks, written materials on implementing them is scarce. By themselves, the algorithms used in text editors aren't complex or challenging in a formal mathematical sense. Rather, the challenge is more pragmatic in nature--to make a disparate collection of simple algorithms work together in a coherent manner. Still, I did run across one excellent resource, Craig Finseth's The Craft of Text Editing: Emacs for the Modern World (Springer-Verlag, 1991). Finseth is coauthor of several Emacs-type editors, including Mince, FinalWord, and Freyja. I also found a similar, but less complete, discussion in the electronic archives of the Internet news group comp.editors. The files editech.[1-4].Z contain short but illuminating comments by Joseph Allen and Stephen Trier on how to implement a text editor.
However, none of these authors place text-editor algorithms in the larger context of interactive graphics programs. Implementing a text editor is a subclass of a more general problem--the same problem faced by implementors of "draw" programs and other graphical editing tools. Whether manipulating textual or graphical objects, the fundamental goal is the same: to maintain a consistent mapping between a data model that exists in an application-specific data space, and a visual representation of that model that exists in a graphics coordinate space. The well-known Smalltalk Model/View/Controller paradigm is an equivalent way of expressing this relationship.
Implementation decisions fall into the following categories:
- How text is stored and represented.
- How text is formatted for presentation.
- How the screen gets updated.
- How the program is made customizable, extensible, and modular.
For each category, there are various choices, each reflecting a trade-off between performance, resource consumption, and ease of implementation.
Over the years, I've written a number of editors for DOS, Sun, Windows, and Macintosh platforms and have worked with the code for a number of high-end electronic publishing systems. I've also gone over the code for a number of publicly available editors, including Richard Stallman's GnuEmacs, Craig Finseth's Freyja, Dan Lawrence's Micro-Emacs, Jonathan Payne's Jove, and on the DOS platform, Marc Adler's ME, Al Stevens's MemoPad, and Fook Eng's Chi. These implementations span a range of functionality and implementation strategies, from the monumental 1.5 million lines of code in Interleaf 5.0 and the 150,000 lines of Lisp and C code that constitute GnuEmacs, to the medium-weight 25,000 lines of MicroEmacs and 14,000 lines of MemoPad, to the modest 4000 lines of Chi. Each implementation is a unique mix of choices and trade-offs.
The topic of text editors is among the most deeply personal of subjects for many programmers, giving rise to many a flame war on Usenet, CompuServe, and BBS systems. It's no surprise that one of the Internet newsgroups is called alt.religion.emacs. The following survey of techniques tries to be as nondenominational as possible.
Conceptual View of Data
Perhaps the most basic design decision is what conceptual view of text data to present to the user. Most programming editors regard a text file as a one-dimensional array of ASCII characters that gets mapped to a two-dimensional grid of screen positions. An exception is Chi, which treats text as a one-dimensional array of lines, each of which is a one-dimensional array of characters. This means that lines do not wrap at the right edge of the screen, making for a simple and fast implementation--but one that's cumbersome to use when typing narrative text (as opposed to source code).
