18 files changed, 667 insertions, 54 deletions

diff --git a/common.mk b/common.mk
index 83f0e2b..e9c134d 100644
--- a/common.mk
+++ b/common.mk
@@ -1,16 +1,16 @@
 .POSIX:
-.PHONY: default clean check run debug debug-tests install
+.PHONY: default clean check run debug debug-tests install format
 
 default: dged
 
 SOURCES = src/binding.c src/buffer.c src/command.c src/display.c \
 	src/keyboard.c src/minibuffer.c src/text.c \
-	src/utf8.c src/buffers.c src/window.c src/allocator.c
+	src/utf8.c src/buffers.c src/window.c src/allocator.c src/undo.c
 
 DGED_SOURCES = $(SOURCES) src/main.c
 TEST_SOURCES = test/assert.c test/buffer.c test/text.c test/utf8.c test/main.c \
 	test/command.c test/keyboard.c test/fake-reactor.c test/allocator.c \
-	test/minibuffer.c
+	test/minibuffer.c test/undo.c
 
 prefix != if [ -n "$$prefix" ]; then echo "$$prefix"; else echo "/usr"; fi
 
diff --git a/src/buffer.c b/src/buffer.c
index 3812386..5cdc22b 100644
--- a/src/buffer.c
+++ b/src/buffer.c
@@ -28,6 +28,7 @@ static struct kill_ring {
   uint32_t curr_idx;
   uint32_t paste_idx;
 } g_kill_ring = {.curr_idx = 0,
+                 .buffer = {0},
                  .last_paste = {0},
                  .paste_idx = 0,
                  .paste_up_to_date = false};
@@ -52,6 +53,9 @@ struct buffer buffer_create(char *name, bool modeline) {
       .dot = {0},
       .mark = {0},
       .mark_set = false,
+      .modified = false,
+      .readonly = false,
+      .modeline = NULL,
       .keymaps = calloc(10, sizeof(struct keymap)),
       .nkeymaps = 1,
       .scroll = {0},
@@ -59,6 +63,8 @@ struct buffer buffer_create(char *name, bool modeline) {
       .nkeymaps_max = 10,
   };
 
+  undo_init(&b.undo, 100);
+
   b.keymaps[0] = keymap_create("buffer-default", 128);
   struct binding bindings[] = {
       BINDING(Ctrl, 'B', "backward-char"),
@@ -94,14 +100,17 @@ struct buffer buffer_create(char *name, bool modeline) {
       BINDING(Ctrl, 'Y', "paste"),
       BINDING(Meta, 'y', "paste-older"),
       BINDING(Meta, 'w', "copy"),
+
+      BINDING(Ctrl, '_', "undo"),
   };
   keymap_bind_keys(&b.keymaps[0], bindings,
                    sizeof(bindings) / sizeof(bindings[0]));
 
   if (modeline) {
-    struct modeline *modeline = calloc(1, sizeof(struct modeline));
-    modeline->buffer = malloc(1024);
-    buffer_add_update_hook(&b, buffer_modeline_hook, modeline);
+    b.modeline = calloc(1, sizeof(struct modeline));
+    b.modeline->buffer = malloc(1024);
+    b.modeline->buffer[0] = '\0';
+    buffer_add_update_hook(&b, buffer_modeline_hook, b.modeline);
   }
 
   if (modeline) {
@@ -113,13 +122,26 @@ struct buffer buffer_create(char *name, bool modeline) {
 
 void buffer_destroy(struct buffer *buffer) {
   text_destroy(buffer->text);
-  free(buffer->text);
+  buffer->text = NULL;
+
   free(buffer->name);
+  buffer->name = NULL;
+
   free(buffer->filename);
+  buffer->filename = NULL;
+
   for (uint32_t keymapi = 0; keymapi < buffer->nkeymaps; ++keymapi) {
     keymap_destroy(&buffer->keymaps[keymapi]);
   }
   free(buffer->keymaps);
+  buffer->keymaps = NULL;
+
+  if (buffer->modeline != NULL) {
+    free(buffer->modeline->buffer);
+    free(buffer->modeline);
+  }
+
+  undo_destroy(&buffer->undo);
 }
 
 void buffer_clear(struct buffer *buffer) {
@@ -127,10 +149,48 @@ void buffer_clear(struct buffer *buffer) {
   buffer->dot.col = buffer->dot.line = 0;
 }
 
+void buffer_static_teardown() {
+  for (uint32_t i = 0; i < KILL_RING_SZ; ++i) {
+    if (g_kill_ring.buffer[i].allocated) {
+      free(g_kill_ring.buffer[i].text);
+    }
+  }
+}
+
 bool buffer_is_empty(struct buffer *buffer) {
   return text_num_lines(buffer->text) == 0;
 }
 
+bool buffer_is_modified(struct buffer *buffer) { return buffer->modified; }
+
+bool buffer_is_readonly(struct buffer *buffer) { return buffer->readonly; }
+void buffer_set_readonly(struct buffer *buffer, bool readonly) {
+  buffer->readonly = readonly;
+}
+
+void delete_with_undo(struct buffer *buffer, struct buffer_location start,
+                      struct buffer_location end) {
+  if (buffer->readonly) {
+    minibuffer_echo_timeout(4, "buffer is read-only");
+    return;
+  }
+
+  struct text_chunk txt =
+      text_get_region(buffer->text, start.line, start.col, end.line, end.col);
+
+  undo_push_delete(
+      &buffer->undo,
+      (struct undo_delete){.data = txt.text,
+                           .nbytes = txt.nbytes,
+                           .pos = {.row = start.line, .col = start.col}});
+
+  undo_push_boundary(&buffer->undo,
+                     (struct undo_boundary){.save_point = false});
+
+  text_delete(buffer->text, start.line, start.col, end.line, end.col);
+  buffer->modified = true;
+}
+
 uint32_t buffer_keymaps(struct buffer *buffer, struct keymap **keymaps_out) {
   *keymaps_out = buffer->keymaps;
   return buffer->nkeymaps;
@@ -196,6 +256,14 @@ bool moveh(struct buffer *buffer, int coldelta) {
   return true;
 }
 
+void buffer_goto(struct buffer *buffer, uint32_t line, uint32_t col) {
+  int64_t linedelta = (int64_t)line - (int64_t)buffer->dot.line;
+  movev(buffer, linedelta);
+
+  int64_t coldelta = (int64_t)col - (int64_t)buffer->dot.col;
+  moveh(buffer, coldelta);
+}
+
 struct region {
   struct buffer_location begin;
   struct buffer_location end;
@@ -227,8 +295,12 @@ struct text_chunk *copy_region(struct buffer *buffer, struct region region) {
   struct text_chunk *curr = &g_kill_ring.buffer[g_kill_ring.curr_idx];
   g_kill_ring.curr_idx = g_kill_ring.curr_idx + 1 % KILL_RING_SZ;
 
-  if (curr != NULL) {
+  if (curr->allocated) {
     free(curr->text);
+    curr->text = NULL;
+    curr->nbytes = curr->nchars = 0;
+    curr->line = 0;
+    curr->allocated = false;
   }
 
   struct text_chunk txt =
@@ -249,7 +321,7 @@ void buffer_copy(struct buffer *buffer) {
 void paste(struct buffer *buffer, uint32_t ring_idx) {
   if (ring_idx > 0) {
     struct text_chunk *curr = &g_kill_ring.buffer[ring_idx - 1];
-    if (curr != NULL) {
+    if (curr->text != NULL) {
       g_kill_ring.last_paste = buffer->mark_set ? buffer->mark : buffer->dot;
       buffer_add_text(buffer, curr->text, curr->nbytes);
       g_kill_ring.paste_up_to_date = true;
@@ -267,8 +339,7 @@ void buffer_paste_older(struct buffer *buffer) {
 
     // remove previous paste
     struct text_chunk *curr = &g_kill_ring.buffer[g_kill_ring.curr_idx];
-    text_delete(buffer->text, g_kill_ring.last_paste.line,
-                g_kill_ring.last_paste.col, buffer->dot.line, buffer->dot.col);
+    delete_with_undo(buffer, g_kill_ring.last_paste, buffer->dot);
 
     // place ourselves right
     buffer->dot = g_kill_ring.last_paste;
@@ -291,8 +362,7 @@ void buffer_cut(struct buffer *buffer) {
   if (buffer_region_has_size(buffer)) {
     struct region reg = buffer_get_region(buffer);
     copy_region(buffer, reg);
-    text_delete(buffer->text, reg.begin.line, reg.begin.col, reg.end.line,
-                reg.end.col);
+    delete_with_undo(buffer, reg.begin, reg.end);
     buffer_clear_mark(buffer);
     buffer->dot = reg.begin;
   }
@@ -301,9 +371,7 @@ void buffer_cut(struct buffer *buffer) {
 bool maybe_delete_region(struct buffer *buffer) {
   if (buffer_region_has_size(buffer)) {
     struct region reg = buffer_get_region(buffer);
-    text_delete(buffer->text, reg.begin.line, reg.begin.col, reg.end.line,
-                reg.end.col);
-
+    delete_with_undo(buffer, reg.begin, reg.end);
     buffer_clear_mark(buffer);
     buffer->dot = reg.begin;
     return true;
@@ -327,8 +395,11 @@ void buffer_kill_line(struct buffer *buffer) {
           },
   };
   copy_region(buffer, reg);
-  text_delete(buffer->text, buffer->dot.line, buffer->dot.col, buffer->dot.line,
-              buffer->dot.col + nchars);
+  delete_with_undo(buffer, buffer->dot,
+                   (struct buffer_location){
+                       .line = buffer->dot.line,
+                       .col = buffer->dot.col + nchars,
+                   });
 }
 
 void buffer_forward_delete_char(struct buffer *buffer) {
@@ -336,8 +407,11 @@ void buffer_forward_delete_char(struct buffer *buffer) {
     return;
   }
 
-  text_delete(buffer->text, buffer->dot.line, buffer->dot.col, buffer->dot.line,
-              buffer->dot.col + 1);
+  delete_with_undo(buffer, buffer->dot,
+                   (struct buffer_location){
+                       .line = buffer->dot.line,
+                       .col = buffer->dot.col + 1,
+                   });
 }
 
 void buffer_backward_delete_char(struct buffer *buffer) {
@@ -425,6 +499,7 @@ struct buffer buffer_from_file(char *filename) {
     fclose(file);
   }
 
+  undo_push_boundary(&b.undo, (struct undo_boundary){.save_point = true});
   return b;
 }
 
@@ -458,6 +533,8 @@ void buffer_to_file(struct buffer *buffer) {
   minibuffer_echo_timeout(4, "wrote %d lines to %s", nlines_to_write,
                           buffer->filename);
   fclose(file);
+
+  undo_push_boundary(&buffer->undo, (struct undo_boundary){.save_point = true});
 }
 
 void buffer_write_to(struct buffer *buffer, const char *filename) {
@@ -466,6 +543,11 @@ void buffer_write_to(struct buffer *buffer, const char *filename) {
 }
 
 int buffer_add_text(struct buffer *buffer, uint8_t *text, uint32_t nbytes) {
+  if (buffer->readonly) {
+    minibuffer_echo_timeout(4, "buffer is read-only");
+    return 0;
+  }
+
   // invalidate last paste
   g_kill_ring.paste_up_to_date = false;
 
@@ -473,17 +555,32 @@ int buffer_add_text(struct buffer *buffer, uint8_t *text, uint32_t nbytes) {
    * replace it with the text to insert. */
   maybe_delete_region(buffer);
 
+  struct buffer_location initial = buffer->dot;
+
   uint32_t lines_added, cols_added;
-  text_insert_at(buffer->text, buffer->dot.line, buffer->dot.col, text, nbytes,
+  text_insert_at(buffer->text, initial.line, initial.col, text, nbytes,
                  &lines_added, &cols_added);
-  movev(buffer, lines_added);
 
+  // move to after inserted text
+  movev(buffer, lines_added);
   if (lines_added > 0) {
     // does not make sense to use position from another line
     buffer->dot.col = 0;
   }
   moveh(buffer, cols_added);
 
+  struct buffer_location final = buffer->dot;
+  undo_push_add(
+      &buffer->undo,
+      (struct undo_add){.begin = {.row = initial.line, .col = initial.col},
+                        .end = {.row = final.line, .col = final.col}});
+
+  if (lines_added > 0) {
+    undo_push_boundary(&buffer->undo,
+                       (struct undo_boundary){.save_point = false});
+  }
+
+  buffer->modified = true;
   return lines_added;
 }
 
@@ -527,6 +624,61 @@ void buffer_set_mark_at(struct buffer *buffer, uint32_t line, uint32_t col) {
   minibuffer_echo_timeout(2, "mark set");
 }
 
+void buffer_undo(struct buffer *buffer) {
+  struct undo_stack *undo = &buffer->undo;
+  undo_begin(undo);
+
+  // fetch and handle records
+  struct undo_record *records = NULL;
+  uint32_t nrecords = 0;
+
+  if (undo_current_position(undo) == INVALID_TOP) {
+    minibuffer_echo_timeout(4,
+                            "no more undo information, starting from top...");
+  }
+
+  undo_next(undo, &records, &nrecords);
+
+  undo_push_boundary(undo, (struct undo_boundary){.save_point = false});
+  for (uint32_t reci = 0; reci < nrecords; ++reci) {
+    struct undo_record *rec = &records[reci];
+    switch (rec->type) {
+    case Undo_Boundary: {
+      struct undo_boundary *b = &rec->boundary;
+      if (b->save_point) {
+        buffer->modified = false;
+      }
+      break;
+    }
+    case Undo_Add: {
+      struct undo_add *add = &rec->add;
+
+      delete_with_undo(buffer,
+                       (struct buffer_location){
+                           .line = add->begin.row,
+                           .col = add->begin.col,
+                       },
+                       (struct buffer_location){
+                           .line = add->end.row,
+                           .col = add->end.col,
+                       });
+
+      buffer_goto(buffer, add->begin.row, add->begin.col);
+      break;
+    }
+    case Undo_Delete: {
+      struct undo_delete *del = &rec->delete;
+      buffer_goto(buffer, del->pos.row, del->pos.col);
+      buffer_add_text(buffer, del->data, del->nbytes);
+      break;
+    }
+    }
+  }
+
+  free(records);
+  undo_end(undo);
+}
+
 struct cmdbuf {
   struct command_list *cmds;
   struct buffer_location scroll;
@@ -542,7 +694,6 @@ struct cmdbuf {
 };
 
 void render_line(struct text_chunk *line, void *userdata) {
-
   struct cmdbuf *cmdbuf = (struct cmdbuf *)userdata;
   uint32_t visual_line = line->line - cmdbuf->scroll.line + cmdbuf->line_offset;
 
@@ -701,7 +852,8 @@ struct update_hook_result buffer_modeline_hook(struct buffer *buffer,
   struct tm *lt = localtime(&now);
   char left[128], right[128];
 
-  snprintf(left, 128, "  %-16s (%d, %d)", buffer->name, buffer->dot.line + 1,
+  snprintf(left, 128, "  %c%c %-16s (%d, %d)", buffer->modified ? '*' : '-',
+           buffer->readonly ? '%' : '-', buffer->name, buffer->dot.line + 1,
            visual_dot_col(buffer, buffer->dot.col));
   snprintf(right, 128, "(%.2f ms) %02d:%02d", frame_time / 1e6, lt->tm_hour,
            lt->tm_min);
@@ -732,7 +884,6 @@ struct linenumdata {
 
 void linenum_render_hook(struct text_chunk *line_data, uint32_t line,
                          struct command_list *commands, void *userdata) {
-
   struct linenumdata *data = (struct linenumdata *)userdata;
   static char buf[16];
   command_list_set_index_color_bg(commands, 236);
@@ -794,7 +945,6 @@ struct update_hook_result buffer_linenum_hook(struct buffer *buffer,
 void buffer_update(struct buffer *buffer, uint32_t width, uint32_t height,
                    struct command_list *commands, uint64_t frame_time,
                    uint32_t *relline, uint32_t *relcol) {
-
   if (width == 0 || height == 0) {
     return;
   }
diff --git a/src/buffer.h b/src/buffer.h
index afb32b1..57f7d4e 100644
--- a/src/buffer.h
+++ b/src/buffer.h
@@ -4,6 +4,7 @@
 
 #include "command.h"
 #include "text.h"
+#include "undo.h"
 #include "window.h"
 
 struct keymap;
@@ -123,10 +124,23 @@ struct buffer {
 
   /** Buffer update hooks */
   struct update_hooks update_hooks;
+
+  /** Buffer undo stack */
+  struct undo_stack undo;
+
+  /** Has this buffer been modified from when it was last saved */
+  bool modified;
+
+  /** Can this buffer be changed */
+  bool readonly;
+
+  /** Modeline buffer (may be NULL) */
+  struct modeline *modeline;
 };
 
 struct buffer buffer_create(char *name, bool modeline);
 void buffer_destroy(struct buffer *buffer);
+void buffer_static_teardown();
 
 uint32_t buffer_keymaps(struct buffer *buffer, struct keymap **keymaps_out);
 void buffer_add_keymap(struct buffer *buffer, struct keymap *keymap);
@@ -134,6 +148,9 @@ void buffer_add_keymap(struct buffer *buffer, struct keymap *keymap);
 int buffer_add_text(struct buffer *buffer, uint8_t *text, uint32_t nbytes);
 void buffer_clear(struct buffer *buffer);
 bool buffer_is_empty(struct buffer *buffer);
+bool buffer_is_modified(struct buffer *buffer);
+bool buffer_is_readonly(struct buffer *buffer);
+void buffer_set_readonly(struct buffer *buffer, bool readonly);
 
 void buffer_kill_line(struct buffer *buffer);
 void buffer_forward_delete_char(struct buffer *buffer);
@@ -149,8 +166,11 @@ void buffer_beginning_of_line(struct buffer *buffer);
 void buffer_newline(struct buffer *buffer);
 void buffer_indent(struct buffer *buffer);
 
+void buffer_undo(struct buffer *buffer);
+
 void buffer_goto_beginning(struct buffer *buffer);
 void buffer_goto_end(struct buffer *buffer);
+void buffer_goto(struct buffer *buffer, uint32_t line, uint32_t col);
 
 void buffer_set_mark(struct buffer *buffer);
 void buffer_clear_mark(struct buffer *buffer);
@@ -204,6 +224,7 @@ BUFFER_WRAPCMD(buffer_paste);
 BUFFER_WRAPCMD(buffer_paste_older);
 BUFFER_WRAPCMD(buffer_goto_beginning);
 BUFFER_WRAPCMD(buffer_goto_end);
+BUFFER_WRAPCMD(buffer_undo);
 
 static struct command BUFFER_COMMANDS[] = {
     {.name = "kill-line", .fn = buffer_kill_line_cmd},
@@ -228,4 +249,5 @@ static struct command BUFFER_COMMANDS[] = {
     {.name = "paste-older", .fn = buffer_paste_older_cmd},
     {.name = "goto-beginning", .fn = buffer_goto_beginning_cmd},
     {.name = "goto-end", .fn = buffer_goto_end_cmd},
+    {.name = "undo", .fn = buffer_undo_cmd},
 };
diff --git a/src/command.c b/src/command.c
index cccbd2c..be021fe 100644
--- a/src/command.c
+++ b/src/command.c
@@ -100,7 +100,7 @@ int32_t find_file(struct command_ctx ctx, int argc, const char *argv[]) {
       return 1;
     }
 
-    if (S_ISDIR(sb.st_mode)) {
+    if (S_ISDIR(sb.st_mode) && errno != ENOENT) {
       minibuffer_echo("TODO: implement dired!");
       return 1;
     }
@@ -109,6 +109,7 @@ int32_t find_file(struct command_ctx ctx, int argc, const char *argv[]) {
                       buffers_add(ctx.buffers, buffer_from_file((char *)pth)));
     minibuffer_echo_timeout(4, "buffer \"%s\" loaded",
                             ctx.active_window->buffer->name);
+
   } else {
     minibuffer_prompt(ctx, "find file: ");
   }
diff --git a/src/display.c b/src/display.c
index 39993ef..77b5b32 100644
--- a/src/display.c
+++ b/src/display.c
@@ -90,7 +90,7 @@ struct display *display_create() {
   tcgetattr(0, &orig_term);
 
   // set terminal to raw mode
-  struct termios term;
+  struct termios term = {0};
   cfmakeraw(&term);
 
   tcsetattr(0, TCSADRAIN, &term);
diff --git a/src/main.c b/src/main.c
index b4f512b..6a84dd4 100644
--- a/src/main.c
+++ b/src/main.c
@@ -129,6 +129,7 @@ int main(int argc, char *argv[]) {
   buffers_init(&buflist, 32);
   struct buffer initial_buffer = buffer_create("welcome", true);
   if (filename != NULL) {
+    buffer_destroy(&initial_buffer);
     initial_buffer = buffer_from_file(filename);
   } else {
     const char *welcome_txt = "Welcome to the editor for datagubbar 👴\n";
@@ -147,12 +148,11 @@ int main(int argc, char *argv[]) {
   };
 
   // and one for the minibuffer
-  struct buffer *minibuffer =
-      buffers_add(&buflist, buffer_create("minibuffer", false));
+  struct buffer minibuffer = buffer_create("minibuffer", false);
 
-  minibuffer_init(minibuffer);
+  minibuffer_init(&minibuffer);
   struct window minibuffer_window = (struct window){
-      .buffer = minibuffer,
+      .buffer = &minibuffer,
       .prev_buffer = NULL,
       .x = 0,
       .y = display_height(display) - 1,
@@ -307,6 +307,7 @@ int main(int argc, char *argv[]) {
     frame_allocator_clear(&frame_allocator);
   }
 
+  buffer_destroy(&minibuffer);
   buffers_destroy(&buflist);
   display_clear(display);
   display_destroy(display);
@@ -315,6 +316,7 @@ int main(int argc, char *argv[]) {
   command_registry_destroy(&commands);
   reactor_destroy(reactor);
   frame_allocator_destroy(&frame_allocator);
+  buffer_static_teardown();
 
   return 0;
 }
diff --git a/src/text.c b/src/text.c
index 04efcaa..115fb13 100644
--- a/src/text.c
+++ b/src/text.c
@@ -46,10 +46,14 @@ void text_destroy(struct text *text) {
   }
 
   free(text->lines);
+
+  free(text);
 }
 
 void text_clear(struct text *text) {
   for (uint32_t li = 0; li < text->nlines; ++li) {
+    free(text->lines[li].data);
+    text->lines[li].data = NULL;
     text->lines[li].flags = 0;
     text->lines[li].nbytes = 0;
     text->lines[li].nchars = 0;
@@ -237,6 +241,7 @@ void delete_line(struct text *text, uint32_t line) {
   }
 
   --text->nlines;
+  free(text->lines[text->nlines].data);
   text->lines[text->nlines].data = NULL;
   text->lines[text->nlines].nbytes = 0;
   text->lines[text->nlines].nchars = 0;
@@ -264,7 +269,8 @@ void text_insert_at(struct text *text, uint32_t line, uint32_t col,
 
       insert_at(text, line, col, line_data, linelen, nchars);
 
-      if (linelen == 0) {
+      col += nchars;
+      if (linelen == 0 || col < text_line_length(text, line)) {
         new_line_at(text, line, col);
       }
 
@@ -290,17 +296,38 @@ void text_insert_at(struct text *text, uint32_t line, uint32_t col,
 void text_delete(struct text *text, uint32_t start_line, uint32_t start_col,
                  uint32_t end_line, uint32_t end_col) {
 
+  uint32_t maxline = text->nlines > 0 ? text->nlines - 1 : 0;
+
+  // make sure we stay inside
+  if (start_line > maxline) {
+    start_line = maxline;
+    start_col = text->lines[start_line].nchars > 0
+                    ? text->lines[start_line].nchars - 1
+                    : 0;
+  }
+
+  if (end_line > maxline) {
+    end_line = maxline;
+    end_col = text->lines[end_line].nchars;
+  }
+
   struct line *firstline = &text->lines[start_line];
   struct line *lastline = &text->lines[end_line];
+
+  // clamp column
   if (start_col > firstline->nchars) {
-    return;
+    start_col = firstline->nchars > 0 ? firstline->nchars - 1 : 0;
   }
 
   // handle deletion of newlines
   if (end_col > lastline->nchars) {
-    ++end_line;
-    end_col = 0;
-    lastline = &text->lines[end_line];
+    if (end_line + 1 < text->nlines) {
+      end_col = 0;
+      ++end_line;
+      lastline = &text->lines[end_line];
+    } else {
+      end_col = lastline->nchars;
+    }
   }
 
   uint32_t bytei = utf8_nbytes(lastline->data, lastline->nbytes, end_col);
diff --git a/src/undo.c b/src/undo.c
new file mode 100644
index 0000000..6ebec12
--- /dev/null
+++ b/src/undo.c
@@ -0,0 +1,200 @@
+#include "undo.h"
+#include "string.h"
+
+#include <stdio.h>
+#include <stdlib.h>
+
+void undo_init(struct undo_stack *undo, uint32_t initial_capacity) {
+  undo->top = INVALID_TOP;
+  undo->nrecords = 0;
+  undo->undo_in_progress = false;
+
+  undo->records = calloc(initial_capacity, sizeof(struct undo_record));
+  undo->capacity = initial_capacity;
+}
+
+void grow_if_needed(struct undo_stack *undo, uint32_t needed_capacity) {
+  if (needed_capacity > undo->capacity) {
+    undo->capacity += undo->capacity + needed_capacity > undo->capacity * 2
+                          ? needed_capacity
+                          : undo->capacity;
+
+    undo->records =
+        realloc(undo->records, sizeof(struct undo_record) * undo->capacity);
+  }
+}
+
+void undo_clear(struct undo_stack *undo) {
+  undo->top = INVALID_TOP;
+  undo->nrecords = 0;
+}
+
+void undo_destroy(struct undo_stack *undo) {
+  for (uint32_t i = 0; i < undo->nrecords; ++i) {
+    struct undo_record *rec = &undo->records[i];
+    if (rec->type == Undo_Delete && rec->delete.data != NULL &&
+        rec->delete.nbytes > 0) {
+      free(rec->delete.data);
+    }
+  }
+  undo_clear(undo);
+  undo->capacity = 0;
+
+  free(undo->records);
+  undo->records = NULL;
+}
+
+uint32_t undo_push_boundary(struct undo_stack *undo,
+                            struct undo_boundary boundary) {
+  grow_if_needed(undo, undo->nrecords + 1);
+
+  undo->records[undo->nrecords].type = Undo_Boundary;
+  undo->records[undo->nrecords].boundary = boundary;
+
+  if (!undo->undo_in_progress) {
+    undo->top = undo->nrecords;
+  }
+
+  // we can only have one save point
+  if (boundary.save_point) {
+    for (uint32_t i = 0; i < undo->nrecords; ++i) {
+      if (undo->records[i].type && Undo_Boundary &&
+          undo->records[i].boundary.save_point) {
+        undo->records[i].boundary.save_point = false;
+      }
+    }
+  }
+
+  ++undo->nrecords;
+  return undo->nrecords - 1;
+}
+
+bool pos_equal(struct position *a, struct position *b) {
+  return a->row == b->row && a->col == b->col;
+}
+
+uint32_t undo_push_add(struct undo_stack *undo, struct undo_add add) {
+  grow_if_needed(undo, undo->nrecords + 1);
+
+  // "compress"
+  if (undo->nrecords > 0 &&
+      undo->records[undo->nrecords - 1].type == Undo_Add &&
+      pos_equal(&undo->records[undo->nrecords - 1].add.end, &add.begin)) {
+    undo->records[undo->nrecords - 1].add.end = add.end;
+    return undo->nrecords;
+  }
+
+  undo->records[undo->nrecords].type = Undo_Add;
+  undo->records[undo->nrecords].add = add;
+
+  if (!undo->undo_in_progress) {
+    undo->top = undo->nrecords;
+  }
+
+  ++undo->nrecords;
+  return undo->nrecords - 1;
+}
+
+uint32_t undo_push_delete(struct undo_stack *undo, struct undo_delete delete) {
+  grow_if_needed(undo, undo->nrecords + 1);
+
+  undo->records[undo->nrecords].type = Undo_Delete;
+  undo->records[undo->nrecords].delete = delete;
+
+  if (!undo->undo_in_progress) {
+    undo->top = undo->nrecords;
+  }
+
+  ++undo->nrecords;
+  return undo->nrecords - 1;
+}
+
+void undo_begin(struct undo_stack *undo) { undo->undo_in_progress = true; }
+
+void undo_next(struct undo_stack *undo, struct undo_record **records_out,
+               uint32_t *nrecords_out) {
+  *nrecords_out = 0;
+  *records_out = NULL;
+
+  if (undo->nrecords == 0) {
+    return;
+  }
+
+  if (undo->top == INVALID_TOP) {
+    // reset back to the top (redo)
+    undo->top = undo->nrecords - 1;
+  }
+
+  uint32_t nrecords = 1;
+  struct undo_record *current = &undo->records[undo->top];
+  while (undo->top > 0 && current->type == Undo_Boundary) {
+    ++nrecords;
+    --undo->top;
+    current = &undo->records[undo->top];
+  }
+
+  while (undo->top > 0 && current->type != Undo_Boundary) {
+    ++nrecords;
+    --undo->top;
+    current = &undo->records[undo->top];
+  }
+
+  if (nrecords > 0) {
+    *records_out = calloc(nrecords, sizeof(struct undo_record));
+    *nrecords_out = nrecords;
+
+    struct undo_record *dest = *records_out;
+
+    // copy backwards
+    for (uint32_t reci = undo->top + nrecords, outi = 0; reci > undo->top;
+         --reci, ++outi) {
+      dest[outi] = undo->records[reci - 1];
+    }
+  }
+
+  if (undo->top > 0) {
+    --undo->top;
+  } else {
+    undo->top = INVALID_TOP;
+  }
+}
+
+void undo_end(struct undo_stack *undo) { undo->undo_in_progress = false; }
+
+uint32_t undo_size(struct undo_stack *undo) { return undo->nrecords; }
+uint32_t undo_current_position(struct undo_stack *undo) { return undo->top; }
+
+size_t rec_to_str(struct undo_record *rec, char *buffer, size_t n) {
+  switch (rec->type) {
+  case Undo_Add:
+    return snprintf(buffer, n, "add { begin: (%d, %d) end: (%d, %d)}",
+                    rec->add.begin.row, rec->add.begin.col, rec->add.end.row,
+                    rec->add.end.col);
+  case Undo_Delete:
+    return snprintf(buffer, n, "delete { pos: (%d, %d), ptr: 0x%p, nbytes: %d}",
+                    rec->delete.pos.row, rec->delete.pos.col, rec->delete.data,
+                    rec->delete.nbytes);
+  default:
+    return snprintf(buffer, n, "boundary { save_point: %s }",
+                    rec->boundary.save_point ? "yes" : "no");
+  }
+}
+
+const char *undo_dump(struct undo_stack *undo) {
+  uint32_t left = 8192;
+  const char *buf = malloc(left);
+  char *pos = (char *)buf;
+  pos[0] = '\0';
+
+  char rec_buf[256];
+  for (uint32_t reci = 0; reci < undo->nrecords && left > 0; ++reci) {
+    struct undo_record *rec = &undo->records[reci];
+    rec_to_str(rec, rec_buf, 256);
+    uint32_t written = snprintf(pos, left, "%d: [%s]%s\n", reci, rec_buf,
+                                reci == undo->top ? " <- top" : "");
+    left = written > left ? 0 : left - written;
+    pos += written;
+  }
+
+  return buf;
+}
diff --git a/src/undo.h b/src/undo.h
new file mode 100644
index 0000000..42022c5
--- /dev/null
+++ b/src/undo.h
@@ -0,0 +1,67 @@
+#include <stdbool.h>
+#include <stdint.h>
+
+enum undo_record_type {
+  Undo_Boundary = 1,
+  Undo_Add = 2,
+  Undo_Delete = 3,
+};
+
+struct position {
+  uint32_t row;
+  uint32_t col;
+};
+
+struct undo_boundary {
+  bool save_point;
+};
+
+struct undo_add {
+  struct position begin;
+  struct position end;
+};
+
+struct undo_delete {
+  struct position pos;
+  uint8_t *data;
+  uint32_t nbytes;
+};
+
+struct undo_record {
+  enum undo_record_type type;
+
+  union {
+    struct undo_boundary boundary;
+    struct undo_add add;
+    struct undo_delete delete;
+  };
+};
+
+#define INVALID_TOP -1
+
+struct undo_stack {
+  struct undo_record *records;
+  uint32_t nrecords;
+  uint32_t top;
+  uint32_t capacity;
+  bool undo_in_progress;
+};
+
+void undo_init(struct undo_stack *undo, uint32_t initial_capacity);
+void undo_clear(struct undo_stack *undo);
+void undo_destroy(struct undo_stack *undo);
+
+uint32_t undo_push_boundary(struct undo_stack *undo,
+                            struct undo_boundary boundary);
+
+uint32_t undo_push_add(struct undo_stack *undo, struct undo_add add);
+uint32_t undo_push_delete(struct undo_stack *undo, struct undo_delete delete);
+
+void undo_begin(struct undo_stack *undo);
+void undo_next(struct undo_stack *undo, struct undo_record **records_out,
+               uint32_t *nrecords_out);
+void undo_end(struct undo_stack *undo);
+
+uint32_t undo_size(struct undo_stack *undo);
+uint32_t undo_current_position(struct undo_stack *undo);
+const char *undo_dump(struct undo_stack *undo);
diff --git a/targets.mk b/targets.mk
index c130237..a0b66bd 100644
--- a/targets.mk
+++ b/targets.mk
@@ -17,8 +17,12 @@ run-tests: $(TEST_OBJS) $(OBJS)
 	$(CC) $(LDFLAGS) $(TEST_OBJS) $(OBJS) -o run-tests
 
 check: run-tests
+	clang-format --dry-run --Werror $(DGED_SOURCES) $(TEST_SOURCES)
 	./run-tests
 
+format:
+	clang-format -i $(DGED_SOURCES) $(TEST_SOURCES)
+
 run: dged
 	./dged
 
diff --git a/test/buffer.c b/test/buffer.c
index 9781a6d..38ce468 100644
--- a/test/buffer.c
+++ b/test/buffer.c
@@ -41,6 +41,8 @@ void test_move() {
   ASSERT(
       b.dot.col == 0 && b.dot.line == 0,
       "Expected to not be able to move backwards when at beginning of buffer");
+
+  buffer_destroy(&b);
 }
 
 void run_buffer_tests() { run_test(test_move); }
diff --git a/test/command.c b/test/command.c
index be5fffc..09de7f4 100644
--- a/test/command.c
+++ b/test/command.c
@@ -53,6 +53,8 @@ void test_register_command() {
          "Expected number of commands to be 3 after inserting two more");
   ASSERT(cmds.capacity > 1,
          "Expected capacity to have increased to accommodate new commands");
+
+  command_registry_destroy(&cmds);
 }
 
 void test_lookup_command() {
@@ -70,6 +72,8 @@ void test_lookup_command() {
          "Expected to be able to look up inserted command by hash");
   ASSERT_STR_EQ(cmd->name, "fake",
                 "Expected the found function to have the correct name");
+
+  command_registry_destroy(&cmds);
 }
 
 int32_t failing_command(struct command_ctx ctx, int argc, const char *argv[]) {
@@ -91,6 +95,8 @@ void test_execute_command() {
   struct command *fail_cmd = lookup_command(&cmds, "fejl");
   int32_t res2 = execute_command(fail_cmd, &cmds, NULL, NULL, 0, NULL);
   ASSERT(res2 != 0, "Expected failing command to fail");
+
+  command_registry_destroy(&cmds);
 }
 
 void run_command_tests() {
diff --git a/test/keyboard.c b/test/keyboard.c
index b85c4ad..a76d2a7 100644
--- a/test/keyboard.c
+++ b/test/keyboard.c
@@ -68,6 +68,7 @@ void fake_keyboard_close_write(struct fake_keyboard *kbd) {
 
 void fake_keyboard_destroy(struct fake_keyboard *kbd) {
   fake_keyboard_close_write(kbd);
+  reactor_destroy(kbd->reactor);
 }
 
 void simple_key() {
diff --git a/test/main.c b/test/main.c
index 7663f8f..a999b43 100644
--- a/test/main.c
+++ b/test/main.c
@@ -21,6 +21,9 @@ int main() {
   printf("\n📜 \x1b[1;36mRunning text tests...\x1b[0m\n");
   run_text_tests();
 
+  printf("\n⏪ \x1b[1;36mRunning undo tests...\x1b[0m\n");
+  run_undo_tests();
+
   printf("\n🕴️ \x1b[1;36mRunning buffer tests...\x1b[0m\n");
   run_buffer_tests();
 
diff --git a/test/minibuffer.c b/test/minibuffer.c
index dc29648..0e41c7b 100644
--- a/test/minibuffer.c
+++ b/test/minibuffer.c
@@ -2,12 +2,17 @@
 #include "stdlib.h"
 #include "test.h"
 
+#include "allocator.h"
 #include "buffer.h"
 #include "display.h"
 #include "minibuffer.h"
 
 static struct buffer b = {0};
 
+static struct frame_allocator *g_alloc = NULL;
+
+void *alloc_fn(size_t sz) { return frame_allocator_alloc(g_alloc, sz); }
+
 void init() {
   if (b.name == NULL) {
     b = buffer_create("minibuffer", false);
@@ -16,12 +21,21 @@ void init() {
   minibuffer_init(&b);
 }
 
+void destroy() {
+  if (b.name != NULL) {
+    buffer_destroy(&b);
+  }
+}
+
 void test_minibuffer_echo() {
   uint32_t relline, relcol;
 
   // TODO: how to clear this?
+  struct frame_allocator alloc = frame_allocator_create(1024);
+  g_alloc = &alloc;
+
   struct command_list *list =
-      command_list_create(10, malloc, 0, 0, "minibuffer");
+      command_list_create(10, alloc_fn, 0, 0, "minibuffer");
 
   init();
   ASSERT(!minibuffer_displaying(),
@@ -38,6 +52,10 @@ void test_minibuffer_echo() {
   buffer_update(&b, 100, 1, list, 0, &relline, &relcol);
   ASSERT(!minibuffer_displaying(),
          "A zero timeout echo should be cleared after first update");
+
+  frame_allocator_destroy(&alloc);
+  g_alloc = NULL;
+  destroy();
 }
 
 int32_t fake(struct command_ctx ctx, int argc, const char *argv[]) { return 0; }
@@ -64,6 +82,7 @@ void test_minibuffer_prompt() {
   minibuffer_abort_prompt();
   ASSERT(!minibuffer_focused(),
          "Minibuffer must not be focused after prompt has been aborted");
+  destroy();
 }
 
 void run_minibuffer_tests() {
diff --git a/test/test.h b/test/test.h
index f777916..4dab62e 100644
--- a/test/test.h
+++ b/test/test.h
@@ -12,6 +12,7 @@
 void run_buffer_tests();
 void run_utf8_tests();
 void run_text_tests();
+void run_undo_tests();
 void run_command_tests();
 void run_keyboard_tests();
 void run_allocator_tests();
diff --git a/test/text.c b/test/text.c
index 9c8d825..cb18df5 100644
--- a/test/text.c
+++ b/test/text.c
@@ -8,6 +8,10 @@
 #include <string.h>
 #include <wchar.h>
 
+void assert_line_eq(struct text_chunk line, const char *txt, const char *msg) {
+  ASSERT(strncmp((const char *)line.text, txt, line.nbytes) == 0, msg);
+}
+
 void assert_line_equal(struct text_chunk *line) {}
 
 void test_add_text() {
@@ -24,16 +28,16 @@ void test_add_text() {
 
   ASSERT(text_line_size(t, 0) == 14 && text_line_length(t, 0) == 14,
          "Expected line 1 to have 14 chars and 14 bytes");
-  ASSERT_STR_EQ((const char *)text_get_line(t, 0).text, "This is line 1",
-                "Expected line 1 to be line 1");
+  assert_line_eq(text_get_line(t, 0), "This is line 1",
+                 "Expected line 1 to be line 1");
 
   const char *txt2 = "This is line 2\n";
   text_insert_at(t, 1, 0, (uint8_t *)txt2, strlen(txt2), &lines_added,
                  &cols_added);
   ASSERT(text_num_lines(t) == 2,
          "Expected text to have two lines after second insertion");
-  ASSERT_STR_EQ((const char *)text_get_line(t, 1).text, "This is line 2",
-                "Expected line 2 to be line 2");
+  assert_line_eq(text_get_line(t, 1), "This is line 2",
+                 "Expected line 2 to be line 2");
 
   // simulate indentation
   const char *txt3 = "    ";
@@ -41,19 +45,18 @@ void test_add_text() {
                  &cols_added);
   ASSERT(text_num_lines(t) == 2,
          "Expected text to have two lines after second insertion");
-  ASSERT_STR_EQ((const char *)text_get_line(t, 0).text, "    This is line 1",
-                "Expected line 1 to be indented");
-  ASSERT_STR_EQ((const char *)text_get_line(t, 1).text, "This is line 2",
-                "Expected line 2 to be line 2 still");
+  assert_line_eq(text_get_line(t, 0), "    This is line 1",
+                 "Expected line 1 to be indented");
+  assert_line_eq(text_get_line(t, 1), "This is line 2",
+                 "Expected line 2 to be line 2 still");
 
   // insert newline in middle of line
   text_insert_at(t, 1, 4, (uint8_t *)"\n", 1, &lines_added, &cols_added);
   ASSERT(text_num_lines(t) == 3,
          "Expected text to have three lines after inserting a new line");
-  ASSERT_STR_EQ((const char *)text_get_line(t, 1).text, "This",
-                "Expected line 2 to be split");
-  ASSERT_STR_EQ((const char *)text_get_line(t, 2).text, " is line 2",
-                "Expected line 2 to be split");
+  assert_line_eq(text_get_line(t, 1), "This", "Expected line 2 to be split");
+  assert_line_eq(text_get_line(t, 2), " is line 2",
+                 "Expected line 2 to be split");
 
   // insert newline before line 1
   text_insert_at(t, 1, 0, (uint8_t *)"\n", 1, &lines_added, &cols_added);
@@ -61,10 +64,10 @@ void test_add_text() {
       text_num_lines(t) == 4,
       "Expected to have four lines after adding an empty line in the middle");
   ASSERT(text_line_length(t, 1) == 0, "Expected line 2 to be empty");
-  ASSERT_STR_EQ((const char *)text_get_line(t, 2).text, "This",
-                "Expected line 3 to be previous line 2");
-  ASSERT_STR_EQ((const char *)text_get_line(t, 3).text, " is line 2",
-                "Expected line 4 to be previous line 3");
+  assert_line_eq(text_get_line(t, 2), "This",
+                 "Expected line 3 to be previous line 2");
+  assert_line_eq(text_get_line(t, 3), " is line 2",
+                 "Expected line 4 to be previous line 3");
 
   text_destroy(t);
 }
@@ -151,6 +154,7 @@ void test_delete_text() {
   text_destroy(t);
   text_destroy(t2);
   text_destroy(t3);
+  text_destroy(t4);
 }
 
 void run_text_tests() {
diff --git a/test/undo.c b/test/undo.c
new file mode 100644
index 0000000..d0e2fdb
--- /dev/null
+++ b/test/undo.c
@@ -0,0 +1,104 @@
+#include "assert.h"
+#include "test.h"
+
+#include "undo.h"
+#include <stdlib.h>
+
+void test_undo_insert() {
+  struct undo_stack undo;
+
+  /* small capacity on purpose to force re-sizing */
+  undo_init(&undo, 1);
+
+  undo_push_boundary(&undo, (struct undo_boundary){.save_point = true});
+  ASSERT(undo_size(&undo) == 1,
+         "Expected undo stack to have one item after inserting a save point");
+
+  undo_push_boundary(&undo, (struct undo_boundary){});
+  ASSERT(undo_size(&undo) == 2,
+         "Expected undo stack to have two items after inserting a boundary");
+
+  undo_push_add(&undo, (struct undo_add){.begin = {.col = 0, .row = 0},
+                                         .end = {.col = 4, .row = 0}});
+  ASSERT(undo_size(&undo) == 3,
+         "Expected undo stack to have three items after inserting an add");
+
+  undo_push_delete(&undo, (struct undo_delete){.pos = {.row = 0, .col = 3},
+                                               .data = NULL,
+                                               .nbytes = 0});
+
+  ASSERT(undo_size(&undo) == 4,
+         "Expected undo stack to have four items after inserting a delete");
+
+  ASSERT(undo_current_position(&undo) == undo_size(&undo) - 1,
+         "Undo stack position should be at the top after inserting");
+
+  undo_destroy(&undo);
+}
+
+void test_undo() {
+  struct undo_stack undo;
+  undo_init(&undo, 10);
+
+  undo_push_boundary(&undo, (struct undo_boundary){.save_point = true});
+  undo_push_add(&undo, (struct undo_add){.begin = {.row = 0, .col = 10},
+                                         .end = {.row = 2, .col = 3}});
+
+  struct undo_record *records = NULL;
+  uint32_t nrecords = 0;
+
+  undo_next(&undo, &records, &nrecords);
+  ASSERT(nrecords == 2, "Expected to get back two records");
+  ASSERT(records[0].type == Undo_Add,
+         "Expected first returned record to be an add");
+  free(records);
+
+  ASSERT(undo_current_position(&undo) == INVALID_TOP,
+         "Expected undo stack position to have changed after undo");
+
+  // check that undo begin causes the top of the stack to not be reset
+  undo_begin(&undo);
+  undo_push_add(&undo, (struct undo_add){.begin = {.row = 0, .col = 10},
+                                         .end = {.row = 0, .col = 12}});
+  undo_end(&undo);
+
+  ASSERT(undo_current_position(&undo) == INVALID_TOP,
+         "Expected undo stack position to not have changed when undo "
+         "information was added as part of an undo");
+
+  // but now it should
+  undo_push_add(&undo, (struct undo_add){.begin = {.row = 0, .col = 10},
+                                         .end = {.row = 0, .col = 12}});
+
+  ASSERT(undo_current_position(&undo) == 3,
+         "Expected undo stack position to have changed when undo information "
+         "was added");
+
+  // test that it gets reset to top
+  undo_begin(&undo);
+  records = NULL;
+  undo_next(&undo, &records, &nrecords);
+  free(records);
+
+  undo_push_add(&undo, (struct undo_add){.begin = {.row = 0, .col = 10},
+                                         .end = {.row = 0, .col = 12}});
+  undo_push_boundary(&undo, (struct undo_boundary){.save_point = false});
+  undo_push_add(&undo, (struct undo_add){.begin = {.row = 0, .col = 10},
+                                         .end = {.row = 0, .col = 12}});
+
+  records = NULL;
+  undo_next(&undo, &records, &nrecords);
+  free(records);
+
+  undo_end(&undo);
+  ASSERT(
+      undo_current_position(&undo) == 4,
+      "Expected undo stack position to have been reset when it reached zero");
+
+  undo_destroy(&undo);
+}
+
+void run_undo_tests() {
+  run_test(test_undo_insert);
+  run_test(test_undo);
+}