vis: implement jump list in terms of marks

11 files changed, 185 insertions, 177 deletions

diff --git a/Makefile b/Makefile
index 350d20c..d32e863 100644
--- a/Makefile
+++ b/Makefile
@@ -2,7 +2,7 @@
 
 REGEX_SRC ?= text-regex.c
 
-SRC = array.c buffer.c libutf.c main.c map.c ring-buffer.c \
+SRC = array.c buffer.c libutf.c main.c map.c \
 	sam.c text.c text-motions.c text-objects.c text-util.c \
 	ui-terminal.c view.c vis.c vis-lua.c vis-modes.c vis-motions.c \
 	vis-operators.c vis-registers.c vis-marks.c vis-prompt.c vis-text-objects.c $(REGEX_SRC)
diff --git a/config.def.h b/config.def.h
index b98eeab..b210ef3 100644
--- a/config.def.h
+++ b/config.def.h
@@ -156,6 +156,9 @@ static const KeyBinding bindings_selections[] = {
 	{ "_",                  ACTION(SELECTIONS_TRIM)                     },
 	{ "<S-Tab>",            ACTION(SELECTIONS_ALIGN_INDENT_RIGHT)       },
 	{ "<Tab>",              ACTION(SELECTIONS_ALIGN_INDENT_LEFT)        },
+	{ "g<",                 ACTION(JUMPLIST_PREV)                       },
+	{ "gs",                 ACTION(JUMPLIST_SAVE)                       },
+	{ "g>",                 ACTION(JUMPLIST_NEXT)                       },
 	{ 0 /* empty last element, array terminator */                      },
 };
 
@@ -209,12 +212,10 @@ static const KeyBinding bindings_normal[] = {
 	{ "<C-d>",              ACTION(SELECTIONS_NEXT)                     },
 	{ "<C-e>",              ACTION(WINDOW_SLIDE_UP)                     },
 	{ "<C-f>",              ALIAS("<PageDown>")                         },
-	{ "<C-i>",              ACTION(JUMPLIST_NEXT)                       },
 	{ "<C-j>",              ACTION(SELECTIONS_NEW_LINE_BELOW)           },
 	{ "<C-k>",              ACTION(SELECTIONS_NEW_LINE_ABOVE)           },
 	{ "<C-l>",              ACTION(SELECTIONS_REMOVE_COLUMN_EXCEPT)     },
 	{ "<C-n>",              ACTION(SELECTIONS_MATCH_WORD)               },
-	{ "<C-o>",              ACTION(JUMPLIST_PREV)                       },
 	{ "<C-p>",              ACTION(SELECTIONS_REMOVE_LAST)              },
 	{ "<C-r>",              ACTION(REDO)                                },
 	{ "<C-u>",              ACTION(SELECTIONS_PREV)                     },
diff --git a/main.c b/main.c
index 8be58cd..8db470d 100644
--- a/main.c
+++ b/main.c
@@ -145,6 +145,8 @@ static const char *window(Vis*, const char *keys, const Arg *arg);
 static const char *unicode_info(Vis*, const char *keys, const Arg *arg);
 /* either go to count % of ile or to matching item */
 static const char *percent(Vis*, const char *keys, const Arg *arg);
+/* navigate jumplist next (arg->i > 0), prev (arg->i < 0), save (arg->i = 0) */
+static const char *jumplist(Vis*, const char *keys, const Arg *arg);
 
 enum {
 	VIS_ACTION_EDITOR_SUSPEND,
@@ -212,6 +214,7 @@ enum {
 	VIS_ACTION_DELETE_WORD_PREV,
 	VIS_ACTION_JUMPLIST_PREV,
 	VIS_ACTION_JUMPLIST_NEXT,
+	VIS_ACTION_JUMPLIST_SAVE,
 	VIS_ACTION_CHANGELIST_PREV,
 	VIS_ACTION_CHANGELIST_NEXT,
 	VIS_ACTION_UNDO,
@@ -654,12 +657,17 @@ static const KeyAction vis_action[] = {
 	[VIS_ACTION_JUMPLIST_PREV] = {
 		"vis-jumplist-prev",
 		VIS_HELP("Go to older cursor position in jump list")
-		movement, { .i = VIS_MOVE_JUMPLIST_PREV }
+		jumplist, { .i = -1 }
 	},
 	[VIS_ACTION_JUMPLIST_NEXT] = {
 		"vis-jumplist-next",
 		VIS_HELP("Go to newer cursor position in jump list")
-		movement, { .i = VIS_MOVE_JUMPLIST_NEXT }
+		jumplist, { .i = +1 }
+	},
+	[VIS_ACTION_JUMPLIST_SAVE] = {
+		"vis-jumplist-save",
+		VIS_HELP("Save current selections in jump list")
+		jumplist, { .i = 0 }
 	},
 	[VIS_ACTION_CHANGELIST_PREV] = {
 		"vis-changelist-prev",
@@ -2308,6 +2316,16 @@ static const char *percent(Vis *vis, const char *keys, const Arg *arg) {
 	return keys;
 }
 
+static const char *jumplist(Vis *vis, const char *keys, const Arg *arg) {
+	if (arg->i < 0)
+		vis_jumplist_prev(vis);
+	else if (arg->i > 0)
+		vis_jumplist_next(vis);
+	else
+		vis_jumplist_save(vis);
+	return keys;
+}
+
 static Vis *vis;
 
 static void signal_handler(int signum, siginfo_t *siginfo, void *context) {
diff --git a/ring-buffer.c b/ring-buffer.c
deleted file mode 100644
index 537fb90..0000000
--- a/ring-buffer.c
+++ /dev/null
@@ -1,85 +0,0 @@
-#include "ring-buffer.h"
-#include <stdlib.h>
-
-struct RingBuffer {
-	int cur;            /* index of current element, last added etc. */
-	int start;          /* index of first/oldest element */
-	int end;            /* index of reserved/empty slot */
-	size_t size;        /* buffer capacity / number of slots */
-	bool iterating;     /* whether we are in a sequence of prev/next calls */
-	const void *data[]; /* user supplied buffer content */
-};
-
-static int ringbuf_index_prev(RingBuffer *buf, int i) {
-	return (i-1+buf->size) % buf->size;
-}
-
-static int ringbuf_index_next(RingBuffer *buf, int i) {
-	return (i+1) % buf->size;
-}
-
-static bool ringbuf_isfull(RingBuffer *buf) {
-	return ringbuf_index_next(buf, buf->end) == buf->start;
-}
-
-static bool ringbuf_isempty(RingBuffer *buf) {
-	return buf->start == buf->end;
-}
-
-static bool ringbuf_isfirst(RingBuffer *buf) {
-	return buf->cur == buf->start;
-}
-
-static bool ringbuf_islast(RingBuffer *buf) {
-	return ringbuf_index_next(buf, buf->cur) == buf->end;
-}
-
-const void *ringbuf_prev(RingBuffer *buf) {
-	if (ringbuf_isempty(buf) || (ringbuf_isfirst(buf) && buf->iterating))
-		return NULL;
-	if (buf->iterating)
-		buf->cur = ringbuf_index_prev(buf, buf->cur);
-	buf->iterating = true;
-	return buf->data[buf->cur];
-}
-
-const void *ringbuf_next(RingBuffer *buf) {
-	if (ringbuf_isempty(buf) || ringbuf_islast(buf))
-		return NULL;
-	buf->cur = ringbuf_index_next(buf, buf->cur);
-	buf->iterating = true;
-	return buf->data[buf->cur];
-}
-
-void ringbuf_add(RingBuffer *buf, const void *value) {
-	if (ringbuf_isempty(buf)) {
-		buf->end = ringbuf_index_next(buf, buf->end);
-	} else if (!ringbuf_islast(buf)) {
-		buf->cur = ringbuf_index_next(buf, buf->cur);
-		buf->end = ringbuf_index_next(buf, buf->cur);
-	} else if (ringbuf_isfull(buf)) {
-		buf->start = ringbuf_index_next(buf, buf->start);
-		buf->cur = ringbuf_index_next(buf, buf->cur);
-		buf->end = ringbuf_index_next(buf, buf->end);
-	} else {
-		buf->cur = ringbuf_index_next(buf, buf->cur);
-		buf->end = ringbuf_index_next(buf, buf->end);
-	}
-	buf->data[buf->cur] = value;
-	buf->iterating = false;
-}
-
-void ringbuf_invalidate(RingBuffer *buf) {
-	buf->iterating = false;
-}
-
-RingBuffer *ringbuf_alloc(size_t size) {
-	RingBuffer *buf;
-	if ((buf = calloc(1, sizeof(*buf) + (++size)*sizeof(buf->data[0]))))
-		buf->size = size;
-	return buf;
-}
-
-void ringbuf_free(RingBuffer *buf) {
-	free(buf);
-}
diff --git a/ring-buffer.h b/ring-buffer.h
deleted file mode 100644
index cfd70e0..0000000
--- a/ring-buffer.h
+++ /dev/null
@@ -1,21 +0,0 @@
-#ifndef RING_BUFFER_H
-#define RING_BUFFER_H
-
-#include <stdbool.h>
-#include <stddef.h>
-
-/*
- * Circular buffer with functions for accessing elements in order.
- * One slot always remains unused to distinguish between the empty/full case.
- */
-
-typedef struct RingBuffer RingBuffer;
-
-RingBuffer *ringbuf_alloc(size_t size);
-void ringbuf_free(RingBuffer*);
-void ringbuf_add(RingBuffer*, const void *value);
-const void *ringbuf_prev(RingBuffer*);
-const void *ringbuf_next(RingBuffer*);
-void ringbuf_invalidate(RingBuffer*);
-
-#endif
diff --git a/sam.c b/sam.c
index d5b7bf5..7bd4c5e 100644
--- a/sam.c
+++ b/sam.c
@@ -1248,6 +1248,7 @@ enum SamError sam_cmd(Vis *vis, const char *s) {
 		if (primary_pos != EPOS && view_selection_disposed(vis->win->view))
 			view_cursor_to(vis->win->view, primary_pos);
 		view_selections_primary_set(view_selections(vis->win->view));
+		vis_jumplist_save(vis);
 		bool completed = true;
 		for (Selection *s = view_selections(vis->win->view); s; s = view_selections_next(s)) {
 			if (view_selections_anchored(s)) {
diff --git a/vis-core.h b/vis-core.h
index 024261c..9c6a635 100644
--- a/vis-core.h
+++ b/vis-core.h
@@ -8,7 +8,6 @@
 #include "text.h"
 #include "text-util.h"
 #include "map.h"
-#include "ring-buffer.h"
 #include "array.h"
 #include "buffer.h"
 #include "util.h"
@@ -134,6 +133,12 @@ typedef struct {
 	enum SamError error;  /* non-zero in case something went wrong */
 } Transcript;
 
+typedef struct {
+	Array prev;
+	Array next;
+	size_t max;
+} MarkList;
+
 struct File { /* shared state among windows displaying the same file */
 	Text *text;                      /* data structure holding the file content */
 	const char *name;                /* file name used when loading/saving */
@@ -159,7 +164,7 @@ struct Win {
 	UiWin *ui;              /* ui object handling visual appearance of this window */
 	File *file;             /* file being displayed in this window */
 	View *view;             /* currently displayed part of underlying text */
-	RingBuffer *jumplist;   /* LRU jump management */
+	MarkList jumplist;      /* LRU jump management */
 	ChangeList changelist;  /* state for iterating through least recently changes */
 	Array saved_selections; /* register used to store selections */
 	Mode modes[VIS_MODE_INVALID]; /* overlay mods used for per window key bindings */
@@ -276,9 +281,12 @@ void file_name_set(File*, const char *name);
 bool register_init(Register*);
 void register_release(Register*);
 
-void marks_init(Array*);
+void mark_init(Array*);
 void mark_release(Array*);
 
+void marklist_init(MarkList*, size_t max);
+void marklist_release(MarkList*);
+
 const char *register_get(Vis*, Register*, size_t *len);
 const char *register_slot_get(Vis*, Register*, size_t slot, size_t *len);
 
diff --git a/vis-marks.c b/vis-marks.c
index 26dfd71..e04f6b0 100644
--- a/vis-marks.c
+++ b/vis-marks.c
@@ -25,7 +25,19 @@ void vis_mark_normalize(Array *a) {
 	}
 }
 
-void marks_init(Array *arr) {
+bool vis_mark_equal(Array *a, Array *b) {
+	size_t len = array_length(a);
+	if (len != array_length(b))
+		return false;
+	for (size_t i = 0; i < len; i++) {
+		if (!text_range_equal(array_get(a, i), array_get(b, i)))
+			return false;
+	}
+
+	return true;
+}
+
+void mark_init(Array *arr) {
 	array_init_sized(arr, sizeof(SelectionRegion));
 }
 
@@ -35,7 +47,6 @@ void mark_release(Array *arr) {
 	array_release(arr);
 }
 
-
 static Array *mark_from(Vis *vis, enum VisMark id) {
 	if (id == VIS_MARK_SELECTION && vis->win)
 		return &vis->win->saved_selections;
@@ -54,13 +65,12 @@ void vis_mark(Vis *vis, enum VisMark mark) {
 		vis->action.mark = mark;
 }
 
-Array vis_mark_get(Vis *vis, enum VisMark id) {
+static Array mark_get(Win *win, Array *mark) {
 	Array sel;
 	array_init_sized(&sel, sizeof(Filerange));
-	Array *mark = mark_from(vis, id);
 	if (!mark)
 		return sel;
-	View *view = vis->win->view;
+	View *view = win->view;
 	size_t len = array_length(mark);
 	array_reserve(&sel, len);
 	for (size_t i = 0; i < len; i++) {
@@ -73,12 +83,15 @@ Array vis_mark_get(Vis *vis, enum VisMark id) {
 	return sel;
 }
 
-void vis_mark_set(Vis *vis, enum VisMark id, Array *sel) {
-	Array *mark = mark_from(vis, id);
+Array vis_mark_get(Vis *vis, enum VisMark id) {
+	return mark_get(vis->win, mark_from(vis, id));
+}
+
+static void mark_set(Win *win, Array *mark, Array *sel) {
 	if (!mark)
 		return;
 	array_clear(mark);
-	View *view = vis->win->view;
+	View *view = win->view;
 	for (size_t i = 0, len = array_length(sel); i < len; i++) {
 		SelectionRegion ss;
 		Filerange *r = array_get(sel, i);
@@ -87,6 +100,121 @@ void vis_mark_set(Vis *vis, enum VisMark id, Array *sel) {
 	}
 }
 
+void vis_mark_set(Vis *vis, enum VisMark id, Array *sel) {
+	mark_set(vis->win, mark_from(vis, id), sel);
+}
+
+void marklist_init(MarkList *list, size_t max) {
+	array_init_sized(&list->prev, sizeof(Array));
+	array_reserve(&list->prev, max);
+	array_init_sized(&list->next, sizeof(Array));
+	array_reserve(&list->next, max);
+}
+
+void marklist_release(MarkList *list) {
+	for (size_t i = 0, len = array_length(&list->prev); i < len; i++)
+		array_release(array_get(&list->prev, i));
+	array_release(&list->prev);
+	for (size_t i = 0, len = array_length(&list->next); i < len; i++)
+		array_release(array_get(&list->next, i));
+	array_release(&list->next);
+}
+
+static bool marklist_push(Win *win, MarkList *list, Array *sel) {
+	Array *top = array_peek(&list->prev);
+	if (top) {
+		Array top_sel = mark_get(win, top);
+		bool eq = vis_mark_equal(&top_sel, sel);
+		array_release(&top_sel);
+		if (eq)
+			return true;
+	}
+
+	for (size_t i = 0, len = array_length(&list->next); i < len; i++)
+		array_release(array_get(&list->next, i));
+	array_clear(&list->next);
+	Array arr;
+	mark_init(&arr);
+	if (array_length(&list->prev) >= array_capacity(&list->prev)) {
+		Array *tmp = array_get(&list->prev, 0);
+		arr = *tmp;
+		array_remove(&list->prev, 0);
+	}
+	mark_set(win, &arr, sel);
+	return array_push(&list->prev, &arr);
+}
+
+bool vis_jumplist_save(Vis *vis) {
+	View *view = vis->win->view;
+	Array sel = view_selections_get_all(view);
+	bool ret = marklist_push(vis->win, &vis->win->jumplist, &sel);
+	array_release(&sel);
+	return ret;
+}
+
+static bool marklist_prev(Win *win, MarkList *list) {
+	View *view = win->view;
+	bool restore = false;
+	Array cur = view_selections_get_all(view);
+	bool anchored = view_selections_anchored(view_selections_primary_get(view));
+	Array *top = array_peek(&list->prev);
+	if (!top)
+		goto out;
+	Array top_sel = mark_get(win, top);
+	restore = !vis_mark_equal(&top_sel, &cur);
+	if (restore)
+		view_selections_set_all(view, &top_sel, anchored);
+	array_release(&top_sel);
+	if (restore)
+		goto out;
+
+	for (;;) {
+		Array *prev = array_pop(&list->prev);
+		if (!prev)
+			goto out;
+		array_push(&list->next, prev);
+		prev = array_peek(&list->prev);
+		if (!prev)
+			goto out;
+		Array sel = mark_get(win, prev);
+		restore = array_length(&sel) > 0;
+		if (restore)
+			view_selections_set_all(view, &sel, anchored);
+		array_release(&sel);
+		if (restore)
+			goto out;
+	}
+out:
+	array_release(&cur);
+	return restore;
+}
+
+static bool marklist_next(Win *win, MarkList *list) {
+	View *view = win->view;
+	bool anchored = view_selections_anchored(view_selections_primary_get(view));
+	for (;;) {
+		Array *next = array_pop(&list->next);
+		if (!next)
+			return false;
+		Array sel = mark_get(win, next);
+		if (array_length(&sel) > 0) {
+			view_selections_set_all(view, &sel, anchored);
+			array_release(&sel);
+			array_push(&list->prev, next);
+			return true;
+		}
+		array_release(next);
+	}
+}
+
+bool vis_jumplist_prev(Vis *vis) {
+	return marklist_prev(vis->win, &vis->win->jumplist);
+}
+
+bool vis_jumplist_next(Vis *vis) {
+	return marklist_next(vis->win, &vis->win->jumplist);
+}
+
 enum VisMark vis_mark_from(Vis *vis, char mark) {
 	if (mark >= 'a' && mark <= 'z')
 		return VIS_MARK_a + mark - 'a';
diff --git a/vis-motions.c b/vis-motions.c
index 5b55288..6a668c5 100644
--- a/vis-motions.c
+++ b/vis-motions.c
@@ -205,30 +205,6 @@ static size_t window_changelist_prev(Vis *vis, Win *win, size_t pos) {
 	return cl->pos;
 }
 
-static size_t window_jumplist_next(Vis *vis, Win *win, size_t cur) {
-	while (win->jumplist) {
-		Mark mark = (Mark)ringbuf_next(win->jumplist);
-		if (!mark)
-			return cur;
-		size_t pos = text_mark_get(win->file->text, mark);
-		if (pos != EPOS && pos != cur)
-			return pos;
-	}
-	return cur;
-}
-
-static size_t window_jumplist_prev(Vis *vis, Win *win, size_t cur) {
-	while (win->jumplist) {
-		Mark mark = (Mark)ringbuf_prev(win->jumplist);
-		if (!mark)
-			return cur;
-		size_t pos = text_mark_get(win->file->text, mark);
-		if (pos != EPOS && pos != cur)
-			return pos;
-	}
-	return cur;
-}
-
 static size_t window_nop(Vis *vis, Win *win, size_t pos) {
 	return pos;
 }
@@ -618,14 +594,6 @@ const Movement vis_motions[] = {
 		.win = window_changelist_prev,
 		.type = INCLUSIVE,
 	},
-	[VIS_MOVE_JUMPLIST_NEXT] = {
-		.win = window_jumplist_next,
-		.type = INCLUSIVE,
-	},
-	[VIS_MOVE_JUMPLIST_PREV] = {
-		.win = window_jumplist_prev,
-		.type = INCLUSIVE,
-	},
 	[VIS_MOVE_NOP] = {
 		.win = window_nop,
 		.type = IDEMPOTENT,
diff --git a/vis.c b/vis.c
index cc09455..375e73a 100644
--- a/vis.c
+++ b/vis.c
@@ -136,7 +136,7 @@ static File *file_new_text(Vis *vis, Text *text) {
 	file->text = text;
 	file->stat = text_stat(text);
 	for (size_t i = 0; i < LENGTH(file->marks); i++)
-		marks_init(&file->marks[i]);
+		mark_init(&file->marks[i]);
 	if (vis->files)
 		vis->files->prev = file;
 	file->next = vis->files;
@@ -264,7 +264,7 @@ static void window_free(Win *win) {
 	view_free(win->view);
 	for (size_t i = 0; i < LENGTH(win->modes); i++)
 		map_free(win->modes[i].bindings);
-	ringbuf_free(win->jumplist);
+	marklist_release(&win->jumplist);
 	mark_release(&win->saved_selections);
 	free(win);
 }
@@ -456,14 +456,14 @@ Win *window_new_file(Vis *vis, File *file, enum UiOption options) {
 		return NULL;
 	win->vis = vis;
 	win->file = file;
-	win->jumplist = ringbuf_alloc(31);
 	win->view = view_new(file->text);
 	win->ui = vis->ui->window_new(vis->ui, win, options);
-	if (!win->jumplist || !win->view || !win->ui) {
+	if (!win->view || !win->ui) {
 		window_free(win);
 		return NULL;
 	}
-	marks_init(&win->saved_selections);
+	marklist_init(&win->jumplist, 32);
+	mark_init(&win->saved_selections);
 	file->refcount++;
 	view_options_set(win->view, view_options_get(win->view));
 	view_tabwidth_set(win->view, vis->tabwidth);
@@ -795,17 +795,6 @@ void vis_keymap_disable(Vis *vis) {
 	vis->keymap_disabled = true;
 }
 
-static void window_jumplist_add(Win *win, size_t pos) {
-	Mark mark = text_mark_set(win->file->text, pos);
-	if (mark && win->jumplist)
-		ringbuf_add(win->jumplist, (void*)mark);
-}
-
-static void window_jumplist_invalidate(Win *win) {
-	if (win->jumplist)
-		ringbuf_invalidate(win->jumplist);
-}
-
 void vis_interrupt(Vis *vis) {
 	vis->interrupted = true;
 }
@@ -918,10 +907,6 @@ void vis_do(Vis *vis) {
 					view_cursors_to(sel, pos);
 				if (vis->mode->visual)
 					c.range = view_selections_get(sel);
-				if (a->movement->type & JUMP)
-					window_jumplist_add(win, pos);
-				else
-					window_jumplist_invalidate(win);
 			} else if (a->movement->type & INCLUSIVE && c.range.end > start) {
 				c.range.end = text_char_next(txt, c.range.end);
 			} else if (linewise && (a->movement->type & LINEWISE_INCLUSIVE)) {
@@ -989,6 +974,8 @@ void vis_do(Vis *vis) {
 	}
 
 	view_selections_normalize(view);
+	if (a->movement && (a->movement->type & JUMP))
+		vis_jumplist_save(vis);
 
 	if (a->op) {
 
diff --git a/vis.h b/vis.h
index ab81e02..87349e1 100644
--- a/vis.h
+++ b/vis.h
@@ -510,8 +510,6 @@ enum VisMotion {
 	VIS_MOVE_WINDOW_LINE_BOTTOM,
 	VIS_MOVE_CHANGELIST_NEXT,
 	VIS_MOVE_CHANGELIST_PREV,
-	VIS_MOVE_JUMPLIST_NEXT,
-	VIS_MOVE_JUMPLIST_PREV,
 	VIS_MOVE_NOP,
 	VIS_MOVE_PERCENT,
 	VIS_MOVE_BYTE,
@@ -714,7 +712,12 @@ Array vis_mark_get(Vis*, enum VisMark id);
  * according to the start position.
  */
 void vis_mark_normalize(Array*);
-
+/** Add selections of focused window to jump list. */
+bool vis_jumplist_save(Vis*);
+/** Navigate jump list backwards. */
+bool vis_jumplist_prev(Vis*);
+/** Navigate jump list forwards. */
+bool vis_jumplist_next(Vis*);
 /** @} */
 /** Register specifiers. */
 enum VisRegister {