Core undo tree changes

2 files changed, 132 insertions, 50 deletions

diff --git a/text.c b/text.c
index c30b973..1c569b6 100644
--- a/text.c
+++ b/text.c
@@ -85,15 +85,19 @@ struct Change {
 	Span new;               /* all pieces which are introduced/swapped in by the change */
 	size_t pos;             /* absolute position at which the change occured */
 	Change *next;           /* next change which is part of the same action */
+	Change *prev;           /* previous change which is part of the same action */
 };
 
 /* An Action is a list of Changes which are used to undo/redo all modifications
- * since the last snapshot operation. Actions are kept in an undo and a redo stack.
+ * since the last snapshot operation. Actions are stored in a directed graph structure.
  */
 typedef struct Action Action;
 struct Action {
 	Change *change;         /* the most recent change */
-	Action *next;           /* next action in the undo/redo stack */
+	Action *next;           /* the next (child) action in the undo tree */
+	Action *prev;           /* the previous (parent) operation in the undo tree */
+	Action *earlier;        /* the previous Action, chronologically */
+	Action *later;          /* the next Action, chronologically */
 	time_t time;            /* when the first change of this action was performed */
 };
 
@@ -106,16 +110,17 @@ typedef struct {
 struct Text {
 	Buffer buf;             /* original mmap(2)-ed file content at the time of load operation */
 	Buffer *buffers;        /* all buffers which have been allocated to hold insertion data */
-	Piece *pieces;		/* all pieces which have been allocated, used to free them */
+	Piece *pieces;          /* all pieces which have been allocated, used to free them */
 	Piece *cache;           /* most recently modified piece */
-	int piece_count;	/* number of pieces allocated, only used for debuging purposes */
+	int piece_count;        /* number of pieces allocated, only used for debuging purposes */
 	Piece begin, end;       /* sentinel nodes which always exists but don't hold any data */
-	Action *redo, *undo;    /* two stacks holding all actions performed to the file */
+	Action *history;        /* undo tree */
 	Action *current_action; /* action holding all file changes until a snapshot is performed */
+	Action *last_action;    /* the last action added to the tree, chronologically */
 	Action *saved_action;   /* the last action at the time of the save operation */
 	size_t size;            /* current file content size in bytes */
 	char *filename;         /* filename of which data was loaded */
-	struct stat info;	/* stat as proped on load time */
+	struct stat info;       /* stat as proped on load time */
 	int fd;                 /* the file descriptor of the original mmap-ed data */
 	LineCache lines;        /* mapping between absolute pos in bytes and logical line breaks */
 	enum TextNewLine newlines; /* which type of new lines does the file use */
@@ -149,8 +154,6 @@ static void change_free(Change *c);
 /* action management */
 static Action *action_alloc(Text *txt);
 static void action_free(Action *a);
-static void action_push(Action **stack, Action *action);
-static Action *action_pop(Action **stack);
 /* logical line counting cache */
 static void lineno_cache_invalidate(LineCache *cache);
 static size_t lines_skip_forward(Text *txt, size_t pos, size_t lines, size_t *lines_skiped);
@@ -331,30 +334,28 @@ static void span_swap(Text *txt, Span *old, Span *new) {
 	txt->size += new->len;
 }
 
-static void action_push(Action **stack, Action *action) {
-	action->next = *stack;
-	*stack = action;
-}
-
-static Action *action_pop(Action **stack) {
-	Action *action = *stack;
-	if (action)
-		*stack = action->next;
-	return action;
-}
-
-/* allocate a new action, empty the redo stack and push the new action onto
- * the undo stack. all further changes will be associated with this action. */
+/* allocate a new action, set its pointers to the other actions in the history,
+ * and set it as txt->history. All further changes will be associated with this action. */
 static Action *action_alloc(Text *txt) {
-	Action *old, *new = calloc(1, sizeof(Action));
+	Action *new = calloc(1, sizeof(Action));
 	if (!new)
 		return NULL;
 	new->time = time(NULL);
-	/* throw a away all old redo operations */
-	while ((old = action_pop(&txt->redo)))
-		action_free(old);
 	txt->current_action = new;
-	action_push(&txt->undo, new);
+	/* set earlier, later pointers */
+	if (txt->last_action)
+		txt->last_action->later = new;
+	new->earlier = txt->last_action;
+
+	if (!txt->history) {
+		txt->history = new;
+		return new;
+	}
+
+	/* set prev, next pointers */
+	new->prev = txt->history;
+	txt->history->next = new;
+	txt->history = new;
 	return new;
 }
 
@@ -459,6 +460,8 @@ static Change *change_alloc(Text *txt, size_t pos) {
 		return NULL;
 	c->pos = pos;
 	c->next = a->change;
+	if (a->change)
+		a->change->prev = c;
 	a->change = c;
 	return c;
 }
@@ -557,38 +560,103 @@ bool text_insert(Text *txt, size_t pos, const char *data, size_t len) {
 	return true;
 }
 
-size_t text_undo(Text *txt) {
+size_t action_undo(Text *txt, Action *a) {
 	size_t pos = EPOS;
-	/* taking a snapshot makes sure that txt->current_action is reset */
-	text_snapshot(txt);
-	Action *a = action_pop(&txt->undo);
-	if (!a)
-		return pos;
 	for (Change *c = a->change; c; c = c->next) {
 		span_swap(txt, &c->new, &c->old);
 		pos = c->pos;
 	}
+	return pos;
+}
 
-	action_push(&txt->redo, a);
+size_t action_redo(Text *txt, Action *a) {
+	size_t pos = EPOS;
+	Change *c = a->change;
+	while (c->next)
+		c = c->next;
+	for ( ; c; c = c->prev) {
+		span_swap(txt, &c->old, &c->new);
+		pos = c->pos;
+	}
+	return pos;
+}
+
+size_t text_undo(Text *txt) {
+	size_t pos = EPOS;
+	/* taking a snapshot makes sure that txt->current_action is reset */
+	text_snapshot(txt);
+	Action *a = txt->history->prev;
+	if (!a)
+		return pos;
+	pos = action_undo(txt, txt->history);
+	txt->history = a;
 	lineno_cache_invalidate(&txt->lines);
 	return pos;
 }
 
 size_t text_redo(Text *txt) {
 	size_t pos = EPOS;
-	Action *a = action_pop(&txt->redo);
+	/* taking a snapshot makes sure that txt->current_action is reset */
+	text_snapshot(txt);
+	Action *a = txt->history->next;
 	if (!a)
 		return pos;
-	for (Change *c = a->change; c; c = c->next) {
-		span_swap(txt, &c->old, &c->new);
-		pos = c->pos;
+	pos = action_redo(txt, a);
+	txt->history = a;
+	lineno_cache_invalidate(&txt->lines);
+	return pos;
+}
+
+bool history_change_branch(Action *a) {
+	bool changed = false;
+	while (a->prev) {
+		if (a->prev->next != a) {
+			a->prev->next = a;
+			changed = true;
+		}
+		a = a->prev;
 	}
+	return changed;
+}
 
-	action_push(&txt->undo, a);
-	lineno_cache_invalidate(&txt->lines);
+size_t history_traverse_to(Text *txt, Action *a) {
+	size_t pos = EPOS;
+	if (!a)
+		return pos;
+	bool changed = history_change_branch(a);
+	if (!changed) {
+		if (a->time == txt->history->time) {
+			return txt->lines.pos;
+		} else if (a->time > txt->history->time) {
+			while (txt->history != a)
+				pos = text_redo(txt);
+			return pos;
+		} else if (a->time < txt->history->time) {
+			while (txt->history != a)
+				pos = text_undo(txt);
+			return pos;
+		}
+	} else {
+		while (txt->history->prev && txt->history->prev->next == txt->history)
+			text_undo(txt);
+		pos = text_undo(txt);
+		while (txt->history != a)
+			pos = text_redo(txt);
+		return pos;
+	}
 	return pos;
 }
 
+size_t text_earlier(Text *txt) {
+	Action *earlier = txt->history->earlier;
+	return history_traverse_to(txt, earlier);
+}
+
+size_t text_later(Text *txt) {
+	Action *later = txt->history->later;
+	return history_traverse_to(txt, later);
+}
+
 bool text_save(Text *txt, const char *filename) {
 	Filerange r = (Filerange){ .start = 0, .end = text_size(txt) };
 	return text_range_save(txt, &r, filename);
@@ -646,7 +714,7 @@ bool text_range_save(Text *txt, Filerange *range, const char *filename) {
 	fd = -1;
 	if (rename(tmpname, filename) == -1)
 		goto err;
-	txt->saved_action = txt->undo;
+	txt->saved_action = txt->history;
 	text_snapshot(txt);
 	if (!txt->filename)
 		text_filename_set(txt, filename);
@@ -687,7 +755,7 @@ ssize_t text_range_write(Text *txt, Filerange *range, int fd) {
 		}
 	}
 out:
-	txt->saved_action = txt->undo;
+	txt->saved_action = txt->history;
 	text_snapshot(txt);
 	return size - rem;
 }
@@ -732,6 +800,11 @@ Text *text_load(const char *filename) {
 		piece_init(&txt->end, p, NULL, NULL, 0);
 		txt->size = txt->buf.size;
 	}
+	/* write an empty action */
+	change_alloc(txt, EPOS);
+	text_snapshot(txt);
+	txt->saved_action = txt->history;
+
 	return txt;
 out:
 	if (txt->fd > 2) {
@@ -749,7 +822,7 @@ Text *text_load_fd(int fd) {
 	char buf[1024];
 	for (ssize_t len = 0; (len = read(fd, buf, sizeof buf)) > 0;)
 		text_insert(txt, text_size(txt), buf, len);
-	txt->saved_action = txt->undo;
+	txt->saved_action = txt->history;
 	text_snapshot(txt);
 	txt->fd = fd;
 	return txt;
@@ -867,19 +940,26 @@ bool text_delete(Text *txt, size_t pos, size_t len) {
 /* preserve the current text content such that it can be restored by
  * means of undo/redo operations */
 void text_snapshot(Text *txt) {
+	if (txt->current_action)
+		txt->last_action = txt->current_action;
 	txt->current_action = NULL;
 	txt->cache = NULL;
 }
 
+
 void text_free(Text *txt) {
 	if (!txt)
 		return;
 
-	Action *a;
-	while ((a = action_pop(&txt->undo)))
-		action_free(a);
-	while ((a = action_pop(&txt->redo)))
-		action_free(a);
+	// free history
+	Action *hist = txt->history;
+	while (hist && hist->prev)
+		hist = hist->prev;
+	while (hist) {
+		Action *later = hist->later;
+		action_free(hist);
+		hist = later;
+	}
 
 	for (Piece *next, *p = txt->pieces; p; p = next) {
 		next = p->global_next;
@@ -899,7 +979,7 @@ void text_free(Text *txt) {
 }
 
 bool text_modified(Text *txt) {
-	return txt->saved_action != txt->undo;
+	return txt->saved_action != txt->history;
 }
 
 enum TextNewLine text_newline_type(Text *txt){
@@ -1165,7 +1245,7 @@ size_t text_mark_get(Text *txt, Mark mark) {
 }
 
 size_t text_history_get(Text *txt, size_t index) {
-	for (Action *a = txt->current_action ? txt->current_action : txt->undo; a; a = a->next) {
+	for (Action *a = txt->current_action ? txt->current_action : txt->history; a; a = a->prev) {
 		if (index-- == 0) {
 			Change *c = a->change;
 			while (c && c->next)
diff --git a/text.h b/text.h
index 099cbe4..f5091c5 100644
--- a/text.h
+++ b/text.h
@@ -49,6 +49,8 @@ void text_snapshot(Text*);
  * the change occured or EPOS if nothing could be undo/redo. */
 size_t text_undo(Text*);
 size_t text_redo(Text*);
+size_t text_earlier(Text*);
+size_t text_later(Text*);
 
 size_t text_pos_by_lineno(Text*, size_t lineno);
 size_t text_lineno_by_pos(Text*, size_t pos);