kilo milestone: finished chapter 5 (text editor functionality) and chapter 6 (search)

One more chapter to go...

kilo commentary: changing the interface is bad, especially when you don't need to

Step 122 begins a series of modifications that handles the Enter key inserting a new line. The first step is to rename editorAppendRow to editorInsertRow and add a new parameter.

Now this, in and of itself, is fine. Inserting a line at some arbitrary point in the file is a generalization of appending one at the end, so it makes sense to use the guts of editorAppendRow to create editorInsertRow.

Where things go off the rails (IMO) is in step 123, where we are supposed to go through the code, and modify all the old calls to editorAppendRow to the corresponding editorInsertRow. Now there are only two places to change, so this isn't a huge modification to the codebase. However, I see two problems with it:

• It harms the readability of the code, editorAppendRow has a clearer meaning when we're specifically adding a line to the end of a file
• It's actually unnecessary

We can create a new implementation of editorAppendRow quite simply:

static inline editorAppendRow(char* line, ssize_t linelen)
{ editorInsertRow(E.numrows, line, linelen); }

Much, much better

kilo commentary: In which an array of text lines turns out to be a bad design choice

Way back in step 55, the step was taken to store the file the editor is working on as an array of lines. Steps 119 through 125 are dealing with joining two lines (deleting at the start of a line) or creating a new line with the Enter key. Because of the array-of-lines data structure chosen many steps ago, these are both relatively complicated operations.

In an editor that treats a file simply as a sequence of characters, these operations are as easy (or hard) as inserting or deleting a character anywhere else in the file.

I am reminded of one of Fred Brooks' aphorisms, "plan to throw one away; you will, anyhow." kilo is not something you really fix so much as work through to identify all the mistakes to avoid the second time through.

kilo: The horrible, no good, very bad quit confirmation

Step 115 implements a quit confirmation. That is, the user is prevented from quitting kilo while there are unsaved changes, Well, at first:

    case CTRL_KEY('q'):
      if (E.dirty && quit_times > 0) {
        editorSetStatusMessage("WARNING!!! File has unsaved changes. "
          "Press Ctrl-Q %d more times to quit.", quit_times);
        quit_times--;
        return;
      }

Yeah, that's pretty awful UX right there. Ironically, we're just a few steps away from implementing an editorPrompt function (used to prompt for a filename to save to) which could also be used for saying "You have unsaved changes, really quit? (N/y)", which is how virtually every "real" editor does it.

kilo commentary: Is this malloc Really Necessary?

Step 105 begins the process of saving the file to disk by mallocing a buffer the size of the entire file and then copying the file's text into it. Step 106 implements the code to write the contents of this buffer to a file.

There's really no good reason to do this. I suppose there's some speed gained by making a single call to write, rather than one for each line in the file. On the other hand, it seems unlikely to offset the cost of yet another dynamic allocation, and copying the entire contents of the file. A buffered writing system might be worth implementing, but this is not the way to do it.

kilo commentary: realloc is not magic

I'm now starting the "make this an actual text editor" part of implementing kilo. The first step, naturally, is to write code that inserts a new character. Here's the implementation of editorRowInsertChar given in step 101:

void editorRowInsertChar(erow *row, int at, int c) {
  if (at < 0 || at > row->size) at = row->size;
  row->chars = realloc(row->chars, row->size + 2);
  memmove(&row->chars[at + 1], &row->chars[at], row->size - at + 1);
  row->size++;
  row->chars[at] = c;
  editorUpdateRow(row);
}

So yeah, hence the title of this post. The call of memmove every time a character is inserted is pretty bad, too. But... well, this is actually probably good enough for a toy editor that no one is actually going to use for real editing work. Still, I wish the author had at least mentioned that this is very much a quick-and-dirty way to do it, and that there's better ways to do it.

kilo milestone: finished chapter 4

Which is the longest chapter of the booklet, and also marks passing the halfway point (at least in number of steps).

One of the cliché interview questions is, "what weakness do you have?" (or some such). Well, one weakness for me is that I have uncounted projects that I have started, worked on for a bit, and then abandoned long before they were finished, or even really more than started. This kilo project was headed down that same path, when it languished untouched for a year.

I've determined to be more diligent about finishing my projects, or at least bringing them to a reasonable "unhooking point". And so I plan to continue on with the kilo project, at least through the final three chapters, if for no other reason than as an exercise in sticking with a project to the finish.

A bug in the kilo code

Step 85 begins dealing with moving the cursor around tab characters, and step 88 gives the implementation of editorRowCxToRx, which calculates where the cursor should be based on how many tabs it's passed over in the line:

int editorRowCxToRx(erow *row, int cx) {
  int rx = 0;
  int j;
  for (j = 0; j < cx; j++) {
    if (row->chars[j] == '\t')
      rx += (KILO_TAB_STOP - 1) - (rx % KILO_TAB_STOP);
    rx++;
  }
  return rx;
}

Here, the parameter cx is the index into the array of characters of the line text, and the return value row offset of where the cursor should be placed on the screen

The problem comes when moving between two lines. Let's say you've got two lines, something like this:

\t
123456789

Now suppose that the cursor is on the first line, to the right of the tab character. Normally, the cursor will be displayed directly above the '9' character on the second line. Now suppose you press the down arrow to move to the next line, where should the cursor be? Virtually every editor I've ever used will place the cursor on the '9' of the second line.

However, the cx value will still be 1, and so for kilo, the cursor will be placed on the 2.

Maybe this will be fixed later in the project. I'm not going to try to deal with it now (honestly, this whole method of dealing with tabs feels like a botch anyway). Perhaps once I finish working through my first pass over the code.

kilo commentary:

Steps 80-84 of the kilo construction process have to do with rendering tab characters as spaces on the screen. Part of this is converting tab characters to the equivalent number of spaces, which is done by this bit of code:

      row->render[idx++] = ' ';
      while (idx % KILO_TAB_STOP != 0) row->render[idx++] = ' ';

Which... this is equivalent to this, right?

      do
          row->render[idx++] = ' ';
      while (idx % KILO_TAB_STOP != 0);

I mean, I realize that the do-while construct is relatively uncommon to use in C (at least in my experience), but this is a perfect example of where to use it.

kilo: revisiting the PAGE_UP and PAGE_DOWN keys

Back when I was implementing The PAGE_UP and PAGE_DOWN keys, I offered my own refactored implementation.

I've now just completed the steps to implement vertical scrolling in the text viewer phase of the project, I discover that my implementation no longer has the same effect once there is a file to be scrolled through. Fortunately, there is an easy fix:

    case PAGE_UP: 
        editor_move_cursor(0, -get_screen_height());
        break;
 
    case PAGE_DOWN:
        editor_move_cursor(0, get_screen_height());
        break;

As a side note, I found getting the scrolling code correct was surprisingly fiddly, due at least partially to my slightly different structure and very different naming conventions. I feel like there's some major structural refactoring that needs to be done, but I feel I'm already close to a place where many more changes will get me to the place where I can't map between the original version and my refactored version anymore. So I'm going to hold off on making any big changes at least until I work through the rest of the code.

kilo: refactoring access to g_editor_state

I've been continuing working through the steps to implement kilo, but I've been increasingly unhappy with the accesses to the global g_editor_state variable all over the code; it's ugly and makes too much of the code dependent on the precise declaration of that struct.

So I decided to refactor so that all accesses to the editor state are through aptly named functions. I'm a lot happier with the result. As an example, here's the current implementation of editor_draw_rows:

void editor_draw_rows(term_buffer* tb)
{
    for (int y = 0; y < get_screen_height(); y++)
    {
        if (y < get_file_lines())
        {
            int len = get_line_size();
            if (len > get_screen_width())
              len = get_screen_width();
            tb_append(tb, get_line_chars(), len);
        }
        else if (y != get_screen_height()/3)
            tb_append_str(tb, get_tilde_str());
        else if (get_file_lines() == 0)
            append_welcome_message(tb);
        
        tb_append_str(tb, get_clear_row_str());
        if (y + 1 < get_screen_height())
            tb_append_str(tb, get_rn_str());
    }
}

kilo commentary: Page Up and Page Down buttons

Oh, dear. Way back when I started this commentary, I said I didn't want to be critical, but how the Page Up and Page Down buttons are implemented is pretty ugly:

    case PAGE_UP:
    case PAGE_DOWN:
      {
        int times = E.screenrows;
        while (times--)
          editorMoveCursor(c == PAGE_UP ? ARROW_UP : ARROW_DOWN);
      }
      break;

Particularly when the Home and End keys are implemented more like I would expect:

    case HOME_KEY:
      E.cx = 0;
      break;
    case END_KEY:
      E.cx = E.screencols - 1;
      break;

My code:

    case PAGE_UP: 
        editor_set_cursor_row(0);
        break;
 
    case PAGE_DOWN:
        editor_set_cursor_row(g_editor_state.screenrows-1);
        break;

The code for editorReadKey (the final version, at least for this chapter, is here) has also become pretty ugly. Even in this relatively short implementation, all these nested ifs and elses make it very hard to see how the control logic works.

That said, I don't want to take time right now to work out a cleaner solution than the one I have right now (I'm more interested in the other parts of this code) so I'm going to leave this the way I have it. Probably the best answer is to break down and use a third-party library that has already solved this problem.

kilo commentary: Moving the cursor (steps 43-45)

In spite of a hiatus that's now more than a year long, I haven't forgotten about my kilo project. Steps 43-45 involve code to keep track of where the cursor is on the screen, and allow the user to move it around. Here's the original code that does that:

void editorMoveCursor(char key) {
  switch (key) {
    case 'a':
      E.cx--;
      break;
    case 'd':
      E.cx++;
      break;
    case 'w':
      E.cy--;
      break;
    case 's':
      E.cy++;
      break;
  }
}
void editorProcessKeypress() {
  char c = editorReadKey();
  switch (c) {
    case CTRL_KEY('q'):
      write(STDOUT_FILENO, "\x1b[2J", 4);
      write(STDOUT_FILENO, "\x1b[H", 3);
      exit(0);
      break;
    case 'w':
    case 's':
    case 'a':
    case 'd':
      editorMoveCursor(c);
      break;
  }
}

The code is basically decoding the w, s, a, and d characters twice: once to determine that the editorMoveCursor function should be called, and another to determine how the cursor should be moved. This is (IMO) another bug waiting to happen, in a large project these two points in the code could easily get out of sync. There's no reason not to do something like this (which is also my current solution):

void editor_move_cursor(int dcx, int dcy)
{
    g_editor_state.cx += dcx;
    g_editor_state.cy += dcy;
}


void editor_process_keypress(char c)
{
    string_const clear_screen = get_clear_screen_str();
    string_const home_cursor  = get_home_cursor_str();

    switch (c)
    {
    case CTRL_KEY('q'):
        write_str(clear_screen);
        write_str(home_cursor);
        exit(0);
        break;

    case 'w': editor_move_cursor( 0, -1); break;
    case 's': editor_move_cursor( 0,  1); break;
    case 'a': editor_move_cursor(-1,  0); break;
    case 'd': editor_move_cursor( 1,  0); break;
    }
}

Note that now only editor_process_keypress needs to know what keys move the cursor, and editor_move_cursor gets parameters that are directly interpretable.

kilo commentary: Wecome message (steps 41 and 42)

Steps 41 and 42 add a welcome message to our nascent editor implementation. It starts with another #define:

#define KILO_VERSION "0.0.1"

As I mentioned before, I'm not a fan of using the preprocessor when it can be avoided, and there's no reason not to declare this as a global character constant. But this is just awful:

void editorDrawRows(struct abuf *ab) {
  int y;
  for (y = 0; y < E.screenrows; y++) {
    if (y == E.screenrows / 3) {
      char welcome[80];
      int welcomelen = snprintf(welcome, sizeof(welcome),
        "Kilo editor -- version %s", KILO_VERSION);
      if (welcomelen > E.screencols) welcomelen = E.screencols;
      int padding = (E.screencols - welcomelen) / 2;
      if (padding) {
        abAppend(ab, "~", 1);
        padding--;
      }
      while (padding--) abAppend(ab, " ", 1);
      abAppend(ab, welcome, welcomelen);
    } else {
      abAppend(ab, "~", 1);
    }
    abAppend(ab, "\x1b[K", 3);
    if (y < E.screenrows - 1) {
      abAppend(ab, "\r\n", 2);
    }
  }
}

In a function called editorDrawRows fully half of the implementation is taken up with displaying the welcome message. We also see again the "reversed if" control flow organization:

if (condition)
  rare case
else
  usual case

I assume we'll see a lot of changes to this function as we go, but for now the implementation is greatly improved by reversing the ordering of the if statement, and moving the code to write the welcome message to its own function.

void editorDrawRows(struct abuf *ab) {
  int y;
  for (y = 0; y < E.screenrows; y++) {
    if (y != E.screenrows / 3) {
      abAppend(ab, "~", 1);
    } else {
      addWelcomeMessage(ab);
    }

    abAppend(ab, "\x1b[K", 3); /* erase to end of line */
    if (y < E.screenrows - 1) {
      abAppend(ab, "\r\n", 2);
    }
  }
}

kilo commentary: Append Buffer (steps 36, 37, 38)

Starting with step 36, an "append buffer" implementation is presented, starting with these declarations:

struct abuf {
  char *b;
  int len;
};
#define ABUF_INIT {NULL, 0}

First of all, abuf is a exceedingly short and non-specific name to be putting in the global namespace. I know this is meant to be a relatively short program, but it's an old proverb in software development that big programs start their lives as small programs. I'm also not a huge fan of using the preprocessor to abstract away the initialization of a struct abuf value (I really don't like using the preprocessor at all when it can be avoided.) A compiler with a decent optimizer should generate comparable code for a call to something like this:

static inline void abInit(struct abuf* ab) {
  ab->b = NULL;
  ab->len = 0;
}

Another question I have about this implementation is, why use a dynamic buffer at all? As is shown in later steps, this is used to buffer output to the screen, instead of writing lots of short strings one at a time. It remains to be seen (by me, anyway) if this is its only use this data structure has, but it seems to me a relatively small fixed-size buffer would serve as well, without putting load on the dynamic allocation system:

struct abuf {
  char b[1024];
  int len;
};

I'd also point out that I'd really like to see clearing of the struct abuf fields in abFree:

void abFree(struct abuf& ab)
{
  free(ab->b);
  ab->b = NULL;
  ab->len = 0;
}

Leaving these with their old values is another bug waiting to happen. Finally, I'd add these utility abstraction functions to clarify the calling code:

static inline void abAppendStr(struct abuf* ab, const char* string) {
  abAppend(ab, string, strlen(string));
}

static inline void abWrite(struct sbuf* ab) {
  write(STDOUT_FILENO, ab->b, ab->len);
}

Note the use of static inline, so this adds a very helpful abstraction layer with zero cost at runtime.

kilo commentary: getCursorPosition (step 33)

In step 33, this version of the getCursorPosition function is presented:

int getCursorPosition(int *rows, int *cols) {
  char buf[32];
  unsigned int i = 0;
  if (write(STDOUT_FILENO, "\x1b[6n", 4) != 4) return -1;
  while (i < sizeof(buf) - 1) {
    if (read(STDIN_FILENO, &buf[i], 1) != 1) break;
    if (buf[i] == 'R') break;
    i++;
  }
  buf[i] = '\0';
  if (buf[0] != '\x1b' || buf[1] != '[') return -1;
  if (sscanf(&buf[2], "%d;%d", rows, cols) != 2) return -1;
  return 0;
}

This is more of a minor stylistic issue compared to the previous stuff I've commented on, but I prefer to write loops like this using for:

int getCursorPosition(int *rows, int *cols) {
  if (write(STDOUT_FILENO, "\x1b[6n", 4) != 4) return -1;

  unsigned int i = 0;
  char buf[32];
  for (i = 0; i < sizeof(buf) - 1; i++) {
    if (read(STDIN_FILENO, &buf[i], 1) != 1) break;
    if (buf[i] == 'R') break;
  }
  buf[i] = '\0';

  if (buf[0] != '\x1b' || buf[1] != '[') return -1;
  if (sscanf(&buf[2], "%d;%d", rows, cols) != 2) return -1;
  return 0;
}

In this version, the initialization of i = 0 is contained within the loop, and the loop structure (IMO, anyway) is clearer. Whenever a loop is iterating on an integer variable with a hard upper bound, I just feel like a for loop makes it clearer what's happening. Also, since this project explicitly uses C99, there's no reason declare variables until they're actually needed.

kilo commentary: getWindowSize (step 30)

In step 30 of implementing the kilo editor, this version of the getWindowSize function is presented:

int getWindowSize(int *rows, int *cols) {
  struct winsize ws;

  /* Note that the "1 ||" in the condition is deliberate, to force execution of the error arm of the if. */
  if (1 || ioctl(STDOUT_FILENO, TIOCGWINSZ, &ws) == -1 || ws.ws_col == 0) {
    if (write(STDOUT_FILENO, "\x1b[999C\x1b[999B", 12) != 12) return -1;
    editorReadKey();
    return -1;
  } else {
    *cols = ws.ws_col;
    *rows = ws.ws_row;
    return 0;
  }
}

This is a really ugly function, particularly considering how short it is. (For what it's worth, this is also where I got in reading through the kilo implementation when I decided I wanted to start blogging my reactions to it.)

First of all, there's another magic string and constant here, "\x1b[999C\x1b[999B" and this is definitely a place where it really feels like a bug waiting to happen. Another problem is that the outer if statement is structured backwards:

if (try something) {
  handle error case
} else {
  handle success case
}

I think it's best to keep the success case code close to the test, so having the error case code in between becomes problematic, especially as and when the error code becomes more complex. A second, related issue is that the error case code is essentially (the start of) an alternate strategy for retrieving the terminal dimensions, nested within the code for the first strategy. Notice how much nicer this reads with just a bit of refactoring:

int getWindowSize(int *rows, int* cols) {
  struct winsize ws;
  /* Note the De Morgan-ized condition to move the success condition to the "then" part of the if. */
  if (0 && ioctl(STDOUT_FILENO, TIOCGWINSZ, &ws) != -1 && ws.ws_col != 0) {
    *cols = ws.ws_col;
    *rows = ws.ws_row;
    return 0;
  }

  if (write(STDOUT_FILENO, "\x1b[999C\x1b[999B", 12) == 12) {
    editorReadKey();
  }

  return -1;
}

Now the two strategies for determining the terminal window size are separated, and the success code is right next to the test in both cases. Also note how much clearer it is here that the second strategy is incomplete, largely because it is no longer hidden inside the logic of the first strategy. Fix up the magic strings and numbers, and this code is vastly improved over the original presentation. Also note we appear to be doing a partial re-implementation of ncurses...

kilo commentary: editorProcessKeypress (step 21)

In part 3 of Build Your Own Text Editor, the following preliminary implementation is presented for a function called editorProcessKeypress:

void editorProcessKeypress() {
  char c = editorReadKey();
  switch (c) {
    case CTRL_KEY('q'):
      exit(0);
      break;
  }
}

It's a very short function, but it's already got a problem: it's doing two different things: 1) reading input from the user, and 2) processing that input. If you're not seeing the problem, imagine if you wanted to use the editor in a scripting environment to modify a file. As it's written above, reading the input from the terminal is a part of editorProcessKeypress. Fortunately, this is easy enough to fix, just move the call to editorReadKey up one level, and pass the result in as a parameter:

void editorProcessKeypress(char c) {
  switch (c) {
    case CTRL_KEY('q'):
      exit(0);
      break;
  }
}

/* ... */

   editorProcessKeypress(editorReadKey());

Note how this also gives us a couple of functions that can be composed together in a nicely satisfying way. Discussion of Curly's Law.

Build Your Own Text Editor!

I was reading Hacker News a while back, and came across this link on how to code a simple text editor. This seemed pretty interesting, so I clicked over, spun up an Ubuntu VM, and started following along.

Almost immediately I noticed the coding style was somewhat problematic (at least to my eye), and so one of the things I want to do in this blog is document my thoughts about how the could can be made better.

Perhaps the first question I had was why the ncurses library was not used for terminal I/O. The author does mention this briefly in the third section of the article:

If we wanted to support the maximum number of terminals out there, we could use the ncurses library, which uses the terminfo database to figure out the capabilities of a terminal and what escape sequences to use for that particular terminal.

He doesn't offer any justification for avoiding ncurses, and we are instead simply plunged headlong into the rather arcane world of ioctl and terminal escape sequences. antirez, the original author, does say that his goal was to write:

...a text editor in less than 1000 lines of code that does not depend on ncurses...

Avoiding dependencies to third party libraries is a reasonable enough goal, I suppose. But I think it's at least worth mentioning the fact that avoiding ncurses adds extra inertia to the project.

I should also add by way of disclaimer, that this (as well as future posts about kilo or other software) is not meant as criticism on the various authors involved. They had their own goals in mind when they wrote their code, and I'll let them speak for themselves as to how well they achieved them.

My purpose is to work out my own thoughts on how best to write code that is clear, correct, and easy to modify. If you get something out of it too, that's on the bonus side.