ke's undo system

• undo_node_free destroys an entire timeline, including children and next.
• undo_node_free_branch only discards next.
• undo_discard_redo_branches kills child and next.

Basic invariants of the undo system:

• root->parent == NULL
• root->current is reachable from root via repeated child walk
• saved is NULL or reachable the same way
• pending is either NULL or a brand-new node not yet linked
• when we commit, pending becomes current->child and current moves forward
• when we undo, current = current->parent
• when we type after undo, we free current->child (redo branch) first

Or, visually,

root ──> N1 ──> N2 ──> N3 ──> N4* ──> N5 ──> N6   (main timeline)
         ^               ^               ^
         |               |               |
      saved           pending        current

• root : first edit ever, never has a parent
• current : where we are right now in history
• saved : points to the node that matches the on-disk file
• pending : temporary node being built (committed → becomes current->child)

If I do a double undo then type something:

root ──> N1 ──> N2 ──> N3* ──> N4 ──> N5   (old N4→N5→N6 discarded)
                ^           ^
                |           |
             current     pending (new edit)
                |
              saved

All four pointers point into the same tree → and should only be memory managed via the root node.

The lifecycle looks something like:

1. undo_begin(UNDO_INSERT)
   • creates a brand-new undo_node
   • stores row/col at that moment
   • puts it in editor.tree->pending
   • tree->current is still pointing at the previous node
   • nothing is linked yet
2. Start typing…
   • undo_append_char('h')
   • undo_append_char('e')
   • undo_append_char('l')
   • undo_append_char('l')
   • undo_append_char('o')
   • all five bytes go into pending->text abuf
   • still completely detached from the tree
3. cursor moves \(->\) undo_commit() is called
   • undo_commit() does the real linking:
     • discards any existing redo branches (current->child = NULL)
     • sets current->child = pending
     • moves tree->current = pending
     • clears tree->pending = NULL
   • now the node is officially part of the tree

Before undo_begin():
    root ──> A ──> B ──> C*          ← tree->current = C
                         pending = NULL

After undo_begin(UNDO_INSERT):
    root ──> A ──> B ──> C*          ← tree->current still C
                         pending ──> [new node, type=INSERT, text=""]

After typing "hello" + undo_commit():
    root ──> A ──> B ──> C ──> D*     ← tree->current now D
                                 ← pending = NULL
        D->text = "hello"

/* Discard all redo branches starting at 'from' */
void undo_discard_redo_branches(struct undo_node *from)

• Called right before you attach a new node after an undo.
• Frees from->child and everything reachable via ->child and ->next.
• Leaves from itself untouched.
• Typical call: undo_discard_redo_branches(editor.tree->current);

/* Return the parent of a node (O(depth) walk – fine, depth is tiny) */
undo_node_t *undo_parent_of(undo_node_t *n)

• Walks backward from root following ->child links until it finds the node whose ->child​=​=​n.
• Returns NULL if n is the root.
• Used only by editor_redo() (to move current forward) and optionally by editor_undo() if you don't store ->parent.

/* User-facing undo – ^_ or ^X u */
void editor_undo(void)

• If nothing to undo (current == root), do nothing + status "No further undo".
• Otherwise:
  1. Reverse-apply the operation stored in current.
  2. Move current = parent_of(current) (or stored ->parent).
  3. display_refresh();
• Must work whether the last action was insert, delete, newline, delete-row, paste, etc.

/* User-facing redo – ^X r or ^_ again */
void editor_redo(void)

• If current->child == NULL, nothing to redo → status "No further redo".
• Otherwise:
  1. Move current = current->child.
  2. Forward-apply the operation stored in the new current.
  3. display_refresh();

/* Called immediately after successful save_file() */
void undo_mark_saved(void)

• Simply does: editor.tree->saved = editor.tree->current;
• Used so that:
  • editor.dirty = 0 can be restored correctly
  • status bar can show "clean" when current == saved

/* How many undo steps back from current? */
int undo_depth(const undo_tree_t *t)

• Returns number of steps you can still undo.
• Walk from current to root counting links.
• Mainly for status line: U3 means three undos available.

/* Can we undo right now? */
int undo_can_undo(const undo_tree_t *t)

• Returns (t->current ! t->root && t->current != NULL)=
• Used to dim/grey the undo menu item if you ever add one.

/* Can we redo right now? */
int undo_can_redo(const undo_tree_t *t)

• Returns (t->current ! NULL && t->current->child != NULL)=
• Symmetric to undo_can_undo().

/* Debug helper – prints the whole tree */
void undo_tree_debug_dump(const undo_tree_t *t)

• Recursively walks the tree and prints something like:

  [root] ──> [I "hello "] ──> [I "world"]* ──> [D 1]   current
                     └─> [I "there"]                redo branch
  saved @ "hello world"
  

• Incredibly useful when you enable -d debugging.