help topics no longer need to be unique and can be toggled through with the `?$` command.

* This mirrors how the `FT$` command toggles through several results.
* Some non-unique .SCITECO_TOPICs have been added to sciteco(1) and sciteco(7).
* This works by inserting non-unique keys into the help topic RB tree - or rather
  by turning filename:pos also into keys since rb3ptr does not allow non-unique keys.
  When searching for a topic, we sort lower than any other entry with the same name.
  This way we can easily iterate all entries with the same name (search topic).
  The alternative would have been to maintain a linked list in each and every
  teco_help_topic_t.
* teco_rb3str_auto_complete() now filters out possible duplicate keys.
* Updated test case: check for non-unique topic names.

3 files changed, 118 insertions, 69 deletions

diff --git a/src/help.c b/src/help.c
index db8a974..e7e674c 100644
--- a/src/help.c
+++ b/src/help.c
@@ -40,8 +40,6 @@
 
 static void teco_help_set(const gchar *topic_name, const gchar *filename, gsize pos);
 
-static GStringChunk *teco_help_chunk = NULL;
-
 /** @extends teco_rb3str_head_t */
 typedef struct {
 	teco_rb3str_head_t head;
@@ -51,6 +49,21 @@ typedef struct {
 	gchar filename[];
 } teco_help_topic_t;
 
+static struct {
+	/**
+	 * Search tree for help topics.
+	 * Several topics with the same name (key) are allowed.
+	 */
+	teco_rb3str_tree_t tree;
+
+	/** first entry found for a given topic */
+	teco_help_topic_t *first;
+	/** last entry shown for a given topic */
+	teco_help_topic_t *current;
+
+	GStringChunk *chunk;
+} teco_help = {0};
+
 /** @static @memberof teco_help_topic_t */
 static teco_help_topic_t *
 teco_help_topic_new(const gchar *topic_name, const gchar *filename, gsize pos)
@@ -63,7 +76,7 @@ teco_help_topic_new(const gchar *topic_name, const gchar *filename, gsize pos)
 	 * It could be allocated via a stack allocator.
 	 */
 	teco_help_topic_t *topic = g_malloc0(sizeof(teco_help_topic_t) + strlen(filename) + 1);
-	teco_string_init_chunk(&topic->head.name, topic_name, strlen(topic_name), teco_help_chunk);
+	teco_string_init_chunk(&topic->head.name, topic_name, strlen(topic_name), teco_help.chunk);
 	topic->pos = pos;
 	strcpy(topic->filename, filename);
 	return topic;
@@ -80,17 +93,15 @@ teco_help_topic_free(teco_help_topic_t *ctx)
 	g_free(ctx);
 }
 
-static teco_rb3str_tree_t teco_help_tree;
-
 static gboolean
 teco_help_init(GError **error)
 {
-	if (G_LIKELY(teco_help_chunk != NULL))
+	if (G_LIKELY(teco_help.chunk != NULL))
 		/* already loaded */
 		return TRUE;
 
-	teco_help_chunk = g_string_chunk_new(32);
-	rb3_reset_tree(&teco_help_tree);
+	teco_help.chunk = g_string_chunk_new(32);
+	rb3_reset_tree(&teco_help.tree);
 
 	g_auto(teco_string_t) lib_path = {NULL, 0};
 	if (!teco_qreg_table_get_string(&teco_qreg_table_globals, "$SCITECOPATH",
@@ -180,6 +191,16 @@ teco_help_init(GError **error)
 	return TRUE;
 }
 
+/*
+ * Compare only for the key name (search term), but we are lower than
+ * all of the existing entries.
+ */
+static gint
+teco_help_casecmp_plain(const teco_rb3str_head_t *head, const teco_string_t *data)
+{
+	return teco_string_casecmp(head->key, data->data, data->len) ? : 1;
+}
+
 static inline teco_help_topic_t *
 teco_help_find(const gchar *topic_name)
 {
@@ -192,60 +213,54 @@ teco_help_find(const gchar *topic_name)
 	 * look-up string to their printable forms.
 	 */
 	g_autofree gchar *term = teco_string_echo(topic_name, strlen(topic_name));
-	return (teco_help_topic_t *)teco_rb3str_find(&teco_help_tree, FALSE, term, strlen(term));
+	teco_string_t data = {(gchar *)term, strlen(term)};
+	teco_help_topic_t *topic = (teco_help_topic_t *)rb3_nfind(&teco_help.tree,
+	                                                          (rb3_cmp *)teco_help_casecmp_plain, &data);
+	return topic && !teco_string_casecmp(topic->head.key, data.data, data.len) ? topic : NULL;
 }
 
-static void
-teco_help_set(const gchar *topic_name, const gchar *filename, gsize pos)
+/*
+ * By turning the filename and position into secondary keys, we can insert
+ * several topics with the same search term and they will be sorted.
+ * Alternatively, we'd have to keep lists in each teco_help_topic_t.
+ */
+static gint
+teco_help_casecmp(const teco_help_topic_t *topic, const teco_help_topic_t *data)
 {
-	teco_help_topic_t *topic;
-	teco_help_topic_t *existing = teco_help_find(topic_name);
-	if (existing) {
-		if (!strcmp(existing->filename, filename)) {
-			/*
-			 * A topic with the same name already exists
-			 * in the same file.
-			 * For the time being, we simply overwrite the
-			 * last topic.
-			 * FIXME: Perhaps make it unique again!?
-			 */
-			existing->pos = pos;
-			return;
-		}
-
-		/* in another file -> make name unique */
-		teco_interface_msg(TECO_MSG_WARNING,
-		                   "Topic collision: \"%s\" defined in \"%s\" and \"%s\"",
-		                   topic_name, existing->filename, filename);
-
-		g_autofree gchar *basename = g_path_get_basename(filename);
-		g_autofree gchar *unique_name = g_strconcat(topic_name, ":", basename, NULL);
-		topic = teco_help_topic_new(unique_name, filename, pos);
-	} else {
-		topic = teco_help_topic_new(topic_name, filename, pos);
-	}
+	return teco_string_casecmp(topic->head.key, data->head.key.data, data->head.key.len)
+		? : strcasecmp(topic->filename, data->filename)
+		? : (gssize)topic->pos - data->pos;
+}
 
-	teco_rb3str_insert(&teco_help_tree, FALSE, &topic->head);
+/*
+ * If the topic is already present in the tree, we will still
+ * insert the given topic.
+ */
+static inline void
+teco_help_set(const gchar *topic_name, const gchar *filename, gsize pos)
+{
+	teco_help_topic_t *topic = teco_help_topic_new(topic_name, filename, pos);
+	rb3_insert(&teco_help.tree, &topic->head.head, (rb3_cmp *)teco_help_casecmp, topic);
 }
 
 gboolean
 teco_help_auto_complete(const gchar *topic_name, teco_string_t *insert)
 {
-	return teco_rb3str_auto_complete(&teco_help_tree, FALSE, topic_name,
+	return teco_rb3str_auto_complete(&teco_help.tree, FALSE, topic_name,
 	                                 topic_name ? strlen(topic_name) : 0, 0, insert);
 }
 
 static void TECO_DEBUG_CLEANUP
 teco_help_cleanup(void)
 {
-	if (!teco_help_chunk)
+	if (!teco_help.chunk)
 		/* not initialized */
 		return;
-	g_string_chunk_free(teco_help_chunk);
+	g_string_chunk_free(teco_help.chunk);
 
 	struct rb3_head *cur;
 
-	while ((cur = rb3_get_root(&teco_help_tree))) {
+	while ((cur = rb3_get_root(&teco_help.tree))) {
 		rb3_unlink_and_rebalance(cur);
 		teco_help_topic_free((teco_help_topic_t *)cur);
 	}
@@ -282,15 +297,34 @@ teco_state_help_done(teco_machine_main_t *ctx, teco_string_t str, GError **error
 		return NULL;
 	}
 
-	/*
-	 * FIXME: Perhaps ?$ could toggle through all topics with the
-	 * same name.
-	 */
-	const gchar *topic_name = str.data ? : "";
-	teco_help_topic_t *topic = teco_help_find(topic_name);
-	if (!topic) {
+	if (str.len) {
+		teco_help_topic_t *next = teco_help_find(str.data);
+		if (!next) {
+			g_set_error(error, TECO_ERROR, TECO_ERROR_FAILED,
+			            "Topic \"%s\" not found", str.data);
+			return NULL;
+		}
+		teco_undo_ptr(teco_help.current) = next;
+		teco_undo_ptr(teco_help.first) = next;
+
+		guint results = 0;
+		for (teco_help_topic_t *cur = teco_help.first;
+		     cur && !teco_string_cmp(cur->head.name, teco_help.first->head.name.data,
+		                             teco_help.first->head.name.len);
+		     cur = (teco_help_topic_t *)teco_rb3str_get_next(&cur->head))
+			results++;
+		if (results > 1)
+			teco_interface_msg(TECO_MSG_INFO, "Found %u help entries", results);
+	} else if (teco_help.current) {
+		/* toggle through topics with the same name */
+		teco_help_topic_t *next = (teco_help_topic_t *)teco_rb3str_get_next(&teco_help.current->head);
+		if (!next || teco_string_cmp(next->head.name, teco_help.first->head.name.data,
+		                             teco_help.first->head.name.len) != 0)
+			next = teco_help.first;
+		teco_undo_ptr(teco_help.current) = next;
+	} else {
 		g_set_error(error, TECO_ERROR, TECO_ERROR_FAILED,
-		            "Topic \"%s\" not found", topic_name);
+		            "No help topic found");
 		return NULL;
 	}
 
@@ -300,10 +334,10 @@ teco_state_help_done(teco_machine_main_t *ctx, teco_string_t str, GError **error
 	 * when editing the buffer for the first time.
 	 */
 	if (!teco_current_doc_undo_edit(error) ||
-	    !teco_ring_edit(topic->filename, error))
+	    !teco_ring_edit(teco_help.current->filename, error))
 		return NULL;
 
-	teco_current_doc_set_dot(teco_interface_bytes2glyphs_absdot(topic->pos));
+	teco_current_doc_set_dot(teco_interface_bytes2glyphs_absdot(teco_help.current->pos));
 
 	/*
 	 * Make sure the topic is visible.
@@ -315,7 +349,7 @@ teco_state_help_done(teco_machine_main_t *ctx, teco_string_t str, GError **error
 	 */
 	undo__teco_interface_ssm(SCI_GOTOPOS,
 	                         teco_interface_ssm(SCI_GETCURRENTPOS, 0, 0), 0);
-	teco_interface_ssm(SCI_GOTOPOS, topic->pos, 0);
+	teco_interface_ssm(SCI_GOTOPOS, teco_help.current->pos, 0);
 
 	return &teco_state_start;
 }
@@ -332,6 +366,9 @@ gboolean teco_state_help_insert_completion(teco_machine_main_t *ctx, teco_string
  * Look up <topic> in the help index, opening
  * the corresponding womanpage as a buffer and scrolling
  * to the topic's position.
+ * If a <topic> is defined in several places, you can
+ * call \(lq?\fB$\fP\(rq to toggle through all of them.
+ *
  * The help index is built when this command is first
  * executed, so the help system does not consume resources
  * when not used (e.g. in a batch-mode script).
diff --git a/src/rb3str.c b/src/rb3str.c
index f4c16fa..367ff83 100644
--- a/src/rb3str.c
+++ b/src/rb3str.c
@@ -60,32 +60,37 @@ teco_rb3str_find(teco_rb3str_tree_t *tree, gboolean case_sensitive, const gchar
 	return (teco_rb3str_head_t *)rb3_find(tree, cmp, &data);
 }
 
-/** @memberof teco_rb3str_tree_t */
-teco_rb3str_head_t *
-teco_rb3str_nfind(teco_rb3str_tree_t *tree, gboolean case_sensitive, const gchar *str, gsize len)
+/*
+ * This is based on rb3_INLINE_find() in rb3ptr.h.
+ * FIXME: Should perhaps be in rb3ptr.c.
+ */
+struct rb3_head *
+rb3_nfind(struct rb3_tree *tree, rb3_cmp cmp, void *data)
 {
-	rb3_cmp *cmp = case_sensitive ? (rb3_cmp *)teco_rb3str_cmp : (rb3_cmp *)teco_rb3str_casecmp;
-	teco_string_t data = {(gchar *)str, len};
-
-	/*
-	 * This is based on rb3_INLINE_find() in rb3ptr.h.
-	 * Alternatively, we might adapt/wrap teco_rb3str_cmp() in order to store
-	 * the last element > data.
-	 */
 	struct rb3_head *parent = rb3_get_base(tree);
 	struct rb3_head *res = NULL;
 	int dir = RB3_LEFT;
+
         while (rb3_has_child(parent, dir)) {
                 parent = rb3_get_child(parent, dir);
-                int r = cmp(parent, &data);
+                int r = cmp(parent, data);
                 if (r == 0)
-                        return (teco_rb3str_head_t *)parent;
-                dir = (r < 0) ? RB3_RIGHT : RB3_LEFT;
+                        return parent;
+                dir = r < 0 ? RB3_RIGHT : RB3_LEFT;
 		if (dir == RB3_LEFT)
 			res = parent;
         }
 
-	return (teco_rb3str_head_t *)res;
+	return res;
+}
+
+/** @memberof teco_rb3str_tree_t */
+teco_rb3str_head_t *
+teco_rb3str_nfind(teco_rb3str_tree_t *tree, gboolean case_sensitive, const gchar *str, gsize len)
+{
+	rb3_cmp *cmp = case_sensitive ? (rb3_cmp *)teco_rb3str_cmp : (rb3_cmp *)teco_rb3str_casecmp;
+	teco_string_t data = {(gchar *)str, len};
+	return (teco_rb3str_head_t *)rb3_nfind(tree, cmp, &data);
 }
 
 /**
@@ -133,9 +138,14 @@ teco_rb3str_auto_complete(teco_rb3str_tree_t *tree, gboolean case_sensitive,
 	if (prefix_len > 0) {
 		teco_string_init(insert, first->key.data + str_len, prefix_len);
 	} else if (prefixed_entries > 1) {
+		teco_rb3str_head_t *next;
 		for (teco_rb3str_head_t *cur = first;
 		     cur && cur->key.len >= str_len && diff(cur->key, str, str_len) == str_len;
-		     cur = teco_rb3str_get_next(cur)) {
+		     cur = next) {
+			next = teco_rb3str_get_next(cur);
+			if (next && !teco_string_cmp(next->key, cur->key.data, cur->key.len))
+				/* filter out duplicates */
+				continue;
 			if (restrict_len && g_utf8_strlen(cur->key.data, cur->key.len) != restrict_len)
 				continue;
 
diff --git a/src/rb3str.h b/src/rb3str.h
index 00d1791..7fd7007 100644
--- a/src/rb3str.h
+++ b/src/rb3str.h
@@ -23,6 +23,8 @@
 #include "sciteco.h"
 #include "string-utils.h"
 
+struct rb3_head *rb3_nfind(struct rb3_tree *tree, rb3_cmp cmp, void *data);
+
 /**
  * A RB-tree with teco_string_t keys.
  *