From e45499816eab8abadbdd5bb6dd79b526a4ed6648 Mon Sep 17 00:00:00 2001 From: Albert Cervin Date: Sat, 11 Feb 2023 23:03:39 +0100 Subject: Implement undo This also fixes a bunch of valgrind errors --- common.mk | 6 +- src/buffer.c | 196 +++++++++++++++++++++++++++++++++++++++++++++------- src/buffer.h | 22 ++++++ src/command.c | 3 +- src/display.c | 2 +- src/main.c | 10 +-- src/text.c | 37 ++++++++-- src/undo.c | 200 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/undo.h | 67 ++++++++++++++++++ targets.mk | 4 ++ test/buffer.c | 2 + test/command.c | 6 ++ test/keyboard.c | 1 + test/main.c | 3 + test/minibuffer.c | 21 +++++- test/test.h | 1 + test/text.c | 36 +++++----- test/undo.c | 104 ++++++++++++++++++++++++++++ 18 files changed, 667 insertions(+), 54 deletions(-) create mode 100644 src/undo.c create mode 100644 src/undo.h create mode 100644 test/undo.c 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 +#include + +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 +#include + +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 #include +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 + +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); +} -- cgit v1.2.3