Towards an Undo System

I've been thinking about building an undo system for ke. The first pass is going to be a linear system. Let's start with the basic definitions for an undo system:

typedef enum undo_kind {
        UNDO_INSERT  = 1 << 0,
        UNDO_UNKNOWN = 1 << 1,
        /* more types to follow */
} undo_kind;


typedef struct undo_node {
        undo_kind                op;
        size_t                   row, col;
        abuf                     text;
        struct undo_node        *next;
        struct undo_node        *parent;
} undo_node;


typedef struct undo_tree {
        /* the start of the undo sequence */
        undo_node       *root;
        /* where we are currently at */
        undo_node       *current;
        /* the current undo operations being built */
        undo_node       *pending;
} undo_tree;

The root is anchored at the last time the file was saved; when saving, the tree is freed. Current points to the end of the history, and pending is the sequence being built.

The lifecycle looks something like:

  • undo_tree_new and undo_tree_free --- called in init_editor and deathknell, respectively. The tree is initialized with all nodes set to NULL.
  • Once the user starts doing undoable things, undo_begin(undo_kind) gets called, calling undo_node_new(undo_kind) if needed to set up tree->pending. It may need to call undo_commit (below) if needed.
  • Until an undo_commit is called, some form of undo_append or undo_prepend is called.
  • Finally, at some point undo_commit is called. This needs to do a few things:
    1. If tree->current->next is not NULL, it must be freed.
    2. Set tree->current->next as pending, set tree->current to tree->current->next.
    3. Set tree->pending to NULL.

In th editor, if I try to undo or redo (C-k u / C-k C-u), the editor will need to call editor_undo or editor_redo. These are mostly wrappers around undo_apply, which will walk backwards in the tree (for undo) or forwards (for redo). In the sequences below, R is the root node, P is pending, and C is current.

The file has just been opened, the user is doing some undoable operation in the file:

R: NULL
C: NULL
P: n0

After the undo commit:

R: n0
C: n0
P: NULL

After a few undo commits:

R: n0 -> n1 -> n2 -> n3
C: n3
P: NULL

Let's undo thrice.

R: n0 -> n1 -> n2 -> n3
C: n0
P: NULL

And then redo:

R: n0 -> n1 -> n2 -> n3
C: n1
P: NULL

If the user starts typing or doing any kind of editing operation, the children of C will be discarded:

R: n0 -> n1 -> n2 -> n3
C: n1
P: n4

Note that an undo_commit is unavoidable at the time.

R: n0 -> n1 -> n4
C: n4
P: NULL

And editing continues apace:

R: n0 -> n1 -> n4 -> n5 -> n6
C: n6
P: NULL

The devil will be in the details, but I think this is a great first step. Once I've hammered on this for a bit, I'll start thinking about making it into an actual undo tree, like in emacs.

  0
  |
  1
  |
 / \
4   2
|   |
|   |
5   3
|
|
6
Tags: , ,