ke/undo.md

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

Once the e

• undo_node_new(undo_kind) and undo_node_free