more undo

3 files changed, 321 insertions, 55 deletions

diff --git a/arr.c b/arr.c
new file mode 100644
index 0000000..b9b3387
--- /dev/null
+++ b/arr.c
@@ -0,0 +1,214 @@
+#ifndef ARR_C_
+#define ARR_C_
+/*
+This is free and unencumbered software released into the public domain.
+Anyone is free to copy, modify, publish, use, compile, sell, or
+distribute this software, either in source code form or as a compiled
+binary, for any purpose, commercial or non-commercial, and by any
+means.
+In jurisdictions that recognize copyright laws, the author or authors
+of this software dedicate any and all copyright interest in the
+software to the public domain. We make this dedication for the benefit
+of the public at large and to the detriment of our heirs and
+successors. We intend this dedication to be an overt act of
+relinquishment in perpetuity of all present and future rights to this
+software under copyright law.
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
+IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
+OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
+ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+OTHER DEALINGS IN THE SOFTWARE.
+For more information, please refer to <http://unlicense.org/>
+*/
+
+// functions in this file suffixed with _ are not meant to be used outside here, unless you
+// know what you're doing
+
+// IMPORTANT NOTE: If you are using this with structures containing `long double`s, do
+//  #define ARR_LONG_DOUBLE
+// before including this file
+
+#include <stddef.h>
+#if __STDC_VERSION__ >= 201112L
+typedef max_align_t ArrMaxAlign;
+#else
+typedef union {
+	long num;
+	void *ptr;
+	void (*fnptr)(void);
+#ifdef ARR_LONG_DOUBLE
+	long
+#endif
+	double flt;
+} ArrMaxAlign;
+#endif
+#if __STDC_VERSION__ < 199901L && !defined inline
+#define inline
+#endif
+
+
+typedef struct {
+	u32 len;
+	u32 cap;
+	ArrMaxAlign data[];
+} ArrHeader;
+
+// watch out! do not call this function if arr is NULL.
+static inline ArrHeader *arr_hdr_(void *arr) {
+	return (ArrHeader *)((char *)arr - offsetof(ArrHeader, data));
+}
+
+static inline u32 arr_len(void *arr) {
+	return arr ? arr_hdr_(arr)->len : 0;
+}
+
+static inline unsigned arr_lenu(void *arr) {
+	return (unsigned)arr_len(arr);
+}
+
+// grow array to fit one more member
+static void *arr_grow1_(void *arr, size_t member_size) {
+	if (arr) {
+		ArrHeader *hdr = arr_hdr_(arr);
+		if (hdr->len >= hdr->cap) {
+			u32 new_capacity = hdr->cap * 2;
+			ArrHeader *old_hdr = hdr;
+			hdr = (ArrHeader *)realloc(old_hdr, sizeof(ArrHeader) + new_capacity * member_size);
+			if (hdr) {
+				hdr->cap = new_capacity;
+			} else {
+				free(old_hdr);
+				return NULL;
+			}
+		}
+		return hdr->data;
+	} else {
+		// create a new array
+		u32 initial_capacity = 2; // allocate enough space for two members
+		ArrHeader *ret = (ArrHeader *)calloc(1, sizeof(ArrHeader) + initial_capacity * member_size);
+		if (ret) {
+			ret->cap = initial_capacity;
+			return ret->data;
+		} else {
+			return NULL;
+		}
+	}
+}
+
+static inline void *arr_add_ptr_(void **arr, size_t member_size) {
+	u8 *ret;
+	*arr = arr_grow1_(*arr, member_size);
+	if (*arr) {
+		ret = (u8 *)*arr + member_size * (arr_hdr_(*arr)->len++);
+		memset(ret, 0, member_size);
+	} else {
+		ret = NULL;
+	}
+	return ret;
+}
+
+#if 0
+// NOT TESTED
+static inline void arr_set_len_(void **arr, size_t member_size, size_t n) {
+	if (n >= U32_MAX-1) { 
+		// too big; free arr.
+		if (*arr) free(arr_hdr_(*arr));
+		*arr = NULL;
+	}
+
+	if (!*arr) {
+		// create a new array with capacity n+1
+		ArrHeader *hdr = calloc(1, sizeof(ArrHeader) + (n+1) * member_size);
+		if (hdr) {
+			hdr->cap = (u32)n+1;
+			hdr->len = (u32)n;
+			*arr = hdr->data;
+		}
+	} else {
+		// increase capacity of array
+		ArrHeader *hdr = arr_hdr_(*arr);
+		u32 curr_cap = hdr->cap;
+		if (n > curr_cap) {
+			ArrHeader *old_hdr = hdr;
+			while (n > curr_cap) {
+				if (curr_cap < U32_MAX/2)
+					curr_cap *= 2;
+				else
+					curr_cap = U32_MAX;
+			}
+			hdr = realloc(hdr, sizeof(ArrHeader) + curr_cap * member_size);
+			if (hdr) {
+				hdr->cap = curr_cap;
+			} else {
+				// growing failed
+				free(old_hdr);
+				*arr = NULL;
+				return;
+			}
+		}
+		if (n > hdr->len) {
+			// zero new elements
+			memset((char *)hdr->data + hdr->len, 0, (n - hdr->len) * member_size);
+		}
+		hdr->len = (u32)n;
+	}
+}
+#define arr_set_len(a, n) arr_set_len_((void **)&a, sizeof *(a), n)
+#endif
+
+#ifdef __cplusplus
+#define arr_cast_typeof(a) (decltype(a))
+#elif defined __GNUC__
+#define arr_cast_typeof(a) (__typeof__(a))
+#else
+#define arr_cast_typeof(a)
+#endif
+
+// if the array is not NULL, free it and set it to NULL
+#define arr_free(a) do { if (a) { free(arr_hdr_(a)); (a) = NULL; } } while (0)
+// add an item to the array - if allocation fails, the array will be freed and set to NULL.
+// (how this works: if we can successfully grow the array, increase the length and add the item.)
+#define arr_add(a, x) do { if (((a) = arr_cast_typeof(a) arr_grow1_((a), sizeof *(a)))) ((a)[arr_hdr_(a)->len++] = (x)); } while (0)
+// like arr_add, but instead of passing it the value, it returns a pointer to the value. returns NULL if allocation failed.
+// the added item will be zero-initialized.
+#define arr_addp(a) arr_cast_typeof(a) arr_add_ptr_((void **)&(a), sizeof *(a))
+// set the length of `a` to `n`, increasing the capacity if necessary.
+// the newly-added elements are zero-initialized.
+#define arr_qsort(a, cmp) qsort((a), arr_len(a), sizeof *(a), (cmp))
+#define arr_remove_last(a) do { assert(a); if (--arr_hdr_(a)->len == 0) arr_free(a); } while (0)
+#define arr_pop_last(a) ((a)[--arr_hdr_(a)->len])
+#define arr_size_in_bytes(a) (arr_len(a) * sizeof *(a))
+#define arr_lastp(a) ((a) ? &(a)[arr_len(a)-1] : NULL)
+#define arr_shrink(a, n) ((void)((a) && (arr_hdr_(a)->len -= (n))))
+#define arr_foreach_backwards(a, var) for (var = arr_lastp(a); var; var = var == (a) ? NULL : var-1)
+#define arr_reverse(a, type) do { \
+	u64 _i, _len = arr_len(a); \
+	for (_i = 0; 2*_i < _len; ++_i) { \
+		type *_x = &(a)[_i]; \
+		type *_y = &(a)[_len-1-_i]; \
+		type _tmp; \
+		_tmp = *_x; \
+		*_x = *_y; \
+		*_y = _tmp; \
+	} \
+	} while (0)
+
+static void arr_test(void) {
+	u32 *arr = NULL;
+	u32 i;
+	assert(arr_len(arr) == 0);
+	for (i = 0; i < 10000; ++i) {
+		arr_add(arr, i*i);
+	}
+	assert(arr_len(arr) == 10000);
+	arr_remove_last(arr);
+	assert(arr_len(arr) == 9999);
+	for (i = 0; i < arr_len(arr); ++i)
+		assert(arr[i] == i*i);
+	while (arr_len(arr))
+		arr_remove_last(arr);
+	assert(arr_len(arr) == 0);
+}
+#endif // ARR_C_
diff --git a/buffer.c b/buffer.c
index 39a25a5..7ede69d 100644
--- a/buffer.c
+++ b/buffer.c
@@ -4,6 +4,7 @@
 #include "util.c"
 #include "text.h"
 #include "string32.c"
+#include "arr.c"
 
 // a position in the buffer
 typedef struct {
@@ -19,16 +20,15 @@ typedef struct {
 
 typedef enum {
 	BUFFER_EDIT_DELETE_TEXT, // text = deleted text, text_len = length of text deleted, pos = where text was deleted (first character)
-	BUFFER_EDIT_INSERT_TEXT // text unused, text_len = length of text inserted, pos = where text was inserted (first character)
+	BUFFER_EDIT_INSERT_TEXT // text = NULL, text_len = length of text inserted, pos = where text was inserted (first character)
 	// (we don't need to know what text was inserted for BUFFER_EDIT_INSERT_TEXT, since it'll be right there)
 } BufferEditType;
 
 typedef struct BufferEdit {
-	struct BufferEdit *next;
 	BufferEditType type;
 	BufferPos pos;
-	u32 text_len;
-	char32_t text[];
+	size_t text_len;
+	char32_t *text;
 } BufferEdit;
 
 typedef struct {
@@ -42,8 +42,8 @@ typedef struct {
 	u32 lines_capacity;
 	Line *lines;
 	char error[128];
-	BufferEdit *undo_history;
-	BufferEdit *redo_history;
+	BufferEdit *undo_history; // dynamic array of undo history
+	BufferEdit *redo_history; // dynamic array of redo history
 } TextBuffer;
 
 
@@ -91,15 +91,15 @@ static void buffer_out_of_mem(TextBuffer *buffer) {
 }
 
 // add this edit to the undo history
-static void buffer_append_edit(TextBuffer *buffer, BufferEdit *edit) {
-	edit->next = buffer->undo_history;
-	buffer->undo_history = edit;
+static void buffer_append_edit(TextBuffer *buffer, BufferEdit const *edit) {
+	arr_add(buffer->undo_history, *edit);
+	if (!buffer->undo_history) buffer_out_of_mem(buffer);
 }
 
 // add this edit to the redo history
-static void buffer_append_redo(TextBuffer *buffer, BufferEdit *edit) {
-	edit->next = buffer->redo_history;
-	buffer->redo_history = edit;
+static void buffer_append_redo(TextBuffer *buffer, BufferEdit const *edit) {
+	arr_add(buffer->redo_history, *edit);
+	if (!buffer->redo_history) buffer_out_of_mem(buffer);
 }
 
 
@@ -130,12 +130,12 @@ static bool buffer_pos_valid(TextBuffer *buffer, BufferPos p) {
 
 
 // get some number of characters of text from the given position in the buffer.
-static Status buffer_get_text_at_pos(TextBuffer *buffer, BufferPos pos, char32_t *text, u32 nchars) {
+static Status buffer_get_text_at_pos(TextBuffer *buffer, BufferPos pos, char32_t *text, size_t nchars) {
 	if (!buffer_pos_valid(buffer, pos)) {
 		return false;
 	}
 	char32_t *p = text;
-	u32 chars_left = nchars;
+	size_t chars_left = nchars;
 	Line *line = &buffer->lines[pos.line], *end = buffer->lines + buffer->nlines;
 	u32 index = pos.index;
 	while (chars_left) {
@@ -154,7 +154,7 @@ static Status buffer_get_text_at_pos(TextBuffer *buffer, BufferPos pos, char32_t
 		++line;
 		if (chars_left && line == end) {
 			// reached end of file before getting full text... this isn't good
-			buffer_seterr(buffer, "Failed to fetch " U32_FMT " characters at " U32_FMT ":" U32_FMT ".", nchars, pos.line+1, pos.index+1);
+			buffer_seterr(buffer, "Failed to fetch %zu characters at " U32_FMT ":" U32_FMT ".", nchars, pos.line+1, pos.index+1);
 			return false;
 		}
 	}
@@ -163,32 +163,44 @@ static Status buffer_get_text_at_pos(TextBuffer *buffer, BufferPos pos, char32_t
 
 // functions for creating buffer edits:
 // call these before you make an edit to create an undo event
-static WarnUnusedResult BufferEdit *buffer_create_edit_delete_text(TextBuffer *buffer, BufferPos start, u32 len) {
-	BufferEdit *e = buffer_calloc(buffer, 1, sizeof *e + len * sizeof *e->text);
-	if (e) {
-		e->type = BUFFER_EDIT_DELETE_TEXT;
-		e->pos = start;
-		e->text_len = len;
-		if (!buffer_get_text_at_pos(buffer, start, e->text, len)) {
-			free(e);
-			e = NULL;
+static Status buffer_create_edit_delete_text(TextBuffer *buffer, BufferEdit *edit, BufferPos start, size_t len) {
+	edit->text = calloc(1, len * sizeof *edit->text);
+	if (edit->text) {
+		edit->type = BUFFER_EDIT_DELETE_TEXT;
+		edit->pos = start;
+		edit->text_len = len;
+		if (!buffer_get_text_at_pos(buffer, start, edit->text, len)) {
+			free(edit->text);
+			return false;
 		}
+		return true;
+	} else {
+		return false;
 	}
-	return e;
 }
 
-static WarnUnusedResult BufferEdit *buffer_create_edit_insert_text(TextBuffer *buffer, BufferPos start, u32 len) {
-	if (!buffer_pos_valid(buffer, start)) return NULL;
-	BufferEdit *e = buffer_calloc(buffer, 1, sizeof *e);
-	if (e) {
-		e->type = BUFFER_EDIT_INSERT_TEXT;
-		e->pos = start;
-		e->text_len = len;
-	}
-	return e;
+static Status buffer_create_edit_insert_text(TextBuffer *buffer, BufferEdit *edit, BufferPos start, size_t len) {
+	if (!buffer_pos_valid(buffer, start)) return false;
+	edit->type = BUFFER_EDIT_INSERT_TEXT;
+	edit->pos = start;
+	edit->text_len = len;
+	edit->text = NULL;
+	return true;
 }
 
+static void buffer_edit_delete_text(TextBuffer *buffer, BufferPos start, size_t len) {
+	BufferEdit edit = {0};
+	if (buffer_create_edit_delete_text(buffer, &edit, start, len)) {
+		buffer_append_edit(buffer, &edit);
+	}
+}
 
+static void buffer_edit_insert_text(TextBuffer *buffer, BufferPos start, size_t len) {
+	BufferEdit edit = {0};
+	if (buffer_create_edit_insert_text(buffer, &edit, start, len)) {
+		buffer_append_edit(buffer, &edit);
+	}
+}
 
 // grow capacity of line to at least minimum_capacity
 // returns true if allocation was succesful
@@ -251,6 +263,9 @@ void buffer_free(TextBuffer *buffer) {
 	}
 	free(lines);
 
+	arr_free(buffer->undo_history);
+	arr_free(buffer->redo_history);
+
 	// zero buffer, except for error
 	char error[sizeof buffer->error];
 	memcpy(error, buffer->error, sizeof error);
@@ -913,6 +928,8 @@ static void buffer_insert_lines(TextBuffer *buffer, u32 where, u32 number) {
 
 // inserts the given text, returning the position of the end of the text
 BufferPos buffer_insert_text_at_pos(TextBuffer *buffer, BufferPos pos, String32 str) {
+	buffer_edit_insert_text(buffer, pos, str.len);
+
 	u32 line_idx = pos.line;
 	u32 index = pos.index;
 	Line *line = &buffer->lines[line_idx];
@@ -1012,6 +1029,11 @@ void buffer_delete_lines(TextBuffer *buffer, u32 first_line_idx, u32 nlines) {
 }
 
 void buffer_delete_chars_at_pos(TextBuffer *buffer, BufferPos pos, i64 nchars) {
+	assert(nchars >= 0);
+	if (nchars <= 0) return;
+
+	buffer_edit_delete_text(buffer, pos, (size_t)nchars);
+
 	u32 line_idx = pos.line;
 	u32 index = pos.index;
 	Line *line = &buffer->lines[line_idx], *lines_end = &buffer->lines[buffer->nlines];
@@ -1099,31 +1121,51 @@ void buffer_backspace_words_at_cursor(TextBuffer *buffer, i64 nwords) {
 	buffer_backspace_words_at_pos(buffer, &buffer->cursor_pos, nwords);
 }
 
+// returns the inverse edit
+static Status buffer_undo_edit(TextBuffer *buffer, BufferEdit const *edit, BufferEdit *inverse) {
+	switch (edit->type) {
+	case BUFFER_EDIT_INSERT_TEXT:
+		// the inverse edit is the deletion of this text
+		if (!buffer_create_edit_delete_text(buffer, inverse, edit->pos, edit->text_len))
+			return false;
+		// delete the text
+		buffer_delete_chars_at_pos(buffer, edit->pos, (i64)edit->text_len);
+		break;
+	case BUFFER_EDIT_DELETE_TEXT: {
+		// the inverse edit is the insertion of this text
+		if (!buffer_create_edit_insert_text(buffer, inverse, edit->pos, edit->text_len))
+			return false;
+		// insert the text
+		String32 str = {edit->text_len, edit->text};
+		buffer_insert_text_at_pos(buffer, edit->pos, str);
+	} break;
+	}
+
+	return true;
+}
+
 void buffer_undo(TextBuffer *buffer, i64 ntimes) {
 	for (i64 i = 0; i < ntimes; ++i) {
-		BufferEdit *edit = buffer->undo_history;
-		BufferEdit *inverse = NULL;
-		
-		switch (edit->type) {
-		case BUFFER_EDIT_INSERT_TEXT:
-			// the inverse edit is the deletion of this text
-			inverse = buffer_create_edit_delete_text(buffer, edit->pos, edit->text_len);
-			// delete the text
-			buffer_delete_chars_at_pos(buffer, edit->pos, edit->text_len);
-			break;
-		case BUFFER_EDIT_DELETE_TEXT: {
-			// the inverse edit is the insertion of this text
-			inverse = buffer_create_edit_insert_text(buffer, edit->pos, edit->text_len);
-			// insert the text
-			String32 str = {edit->text_len, edit->text};
-			buffer_insert_text_at_pos(buffer, edit->pos, str);
-		} break;
+		BufferEdit *edit = arr_lastp(buffer->undo_history);
+		if (edit) {
+			BufferEdit inverse = {0};
+			if (buffer_undo_edit(buffer, edit, &inverse)) {
+				buffer_append_redo(buffer, &inverse);
+				arr_remove_last(buffer->undo_history);
+			}
 		}
+	}
+}
 
-		if (inverse) {
-			buffer_append_redo(buffer, inverse);
+void buffer_redo(TextBuffer *buffer, i64 ntimes) {
+	for (i64 i = 0; i < ntimes; ++i) {
+		BufferEdit *edit = arr_lastp(buffer->redo_history);
+		if (edit) {
+			BufferEdit inverse = {0};
+			if (buffer_undo_edit(buffer, edit, &inverse)) {
+				buffer_append_edit(buffer, &inverse);
+				arr_remove_last(buffer->redo_history);
+			}
 		}
-
-		free(edit);
 	}
 }
diff --git a/main.c b/main.c
index 93bac8a..31dd849 100644
--- a/main.c
+++ b/main.c
@@ -78,6 +78,7 @@ int main(void) {
 		SDL_Event event;
 		Uint8 const *keyboard_state = SDL_GetKeyboardState(NULL);
 		bool ctrl = keyboard_state[SDL_SCANCODE_LCTRL] || keyboard_state[SDL_SCANCODE_RCTRL];
+		bool shift = keyboard_state[SDL_SCANCODE_LSHIFT] || keyboard_state[SDL_SCANCODE_RSHIFT];
 
 		while (SDL_PollEvent(&event)) {
 			// @TODO: make a function to handle text buffer events
@@ -142,6 +143,15 @@ int main(void) {
 						}
 					}
 					break;
+				case SDLK_z:
+					if (ctrl) {
+						if (shift) {
+							buffer_undo(&text_buffer, 1);
+						} else {
+							buffer_redo(&text_buffer, 1);
+						}
+					}
+					break;
 				}
 			} break;
 			case SDL_TEXTINPUT: {