# Towards an Undo System

date  
2025-11-27 20:14

tags  
ked, hacks, text-editors

I've been thinking about building an undo system for
[ke](https://git.wntrmute.dev/kyle/ke). The first pass is going to be a
linear system. Let's start with the basic definitions for an undo
system:

``` c
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`.

Once the e

- `undo_node_new(undo_kind)` and `undo_node_free`