auto-completion of Q-Register names, goto labels and help topics

 * Using a common implementation in RBTreeString::auto_complete().
   This is very efficient even for very huge tables since only
   an O(log(n)) lookup is required and then all entries with a matching
   prefix are iterated. Worst-case complexity is still O(n), since all
   entries may be legitimate completions.
   If necessary, the number of matching entries could be restricted, though.
 * Auto completes short and long Q-Reg names.
   Short names are "case-insensitive" (since they are upper-cased).
   Long specs are terminated with a closing bracket.
 * Long spec completions may have problems with names containing
   funny characters since they may be misinterpreted as string building
   characters or contain braces. All the auto-completions suffered from
   this problem already (see TODO).
 * This greatly simplifies investigating the Q-Register name spaces
   interactively and e.g. calling macros with long names, inserting
   environment registers etc.
 * Goto labels are terminated with commas since they may be part
   of a computed goto.
 * Help topics are matched case insensitive (just like the topic
   lookup itself) and are terminated with the escape character.
   This greatly simplifies navigating womanpages and looking up
   topics with long names.

10 files changed, 251 insertions, 12 deletions

diff --git a/TODO b/TODO
index 2585efb..7708132 100644
--- a/TODO
+++ b/TODO
@@ -74,6 +74,17 @@ Known Bugs:
    window titles on exit using XTerm.
  * Glib (error) messages are not integrated with SciTECO's
    logging system.
+ * Auto-completions are prone to unexpected results when
+   the insertion contains string-building characters, braces
+   (for Q-Register auto-completions) or escape characters
+   (just consider autocompleting after @FG/...).
+   Insertions should thus be escaped.
+   A new string building command should consequently be
+   introduced to insert an ASCII character by digits,
+   e.g. ^E0XXX.
+   Also, auto-completions within string-building constructs
+   (except Q-Reg specs) should generally be disabled since
+   the result will be unpredictable.
 
 Features:
  * Auto-indention could be implemented via context-sensitive
@@ -167,7 +178,6 @@ Features:
    * ER command: read file into current buffer at dot
    * nEW to save a buffer by id
    * ^A and stdio in general
- * autocompletion of long Q-Reg names
  * Buffer ids should be "circular", i.e. interpreted modulo the
    number of buffers in the ring. This allows "%*" to wrap at the
    end of the buffer list.
@@ -305,3 +315,7 @@ Optimizations:
 
 Documentation:
  * Code docs (Doxygen). It's slowly getting better...
+ * The ? command could be extended to support looking
+   up help terms at dot in the current document (e.g. if called ?$).
+   Furthermore, womanpages could contain "hypertext" links
+   to help topics using special Troff markup and grosciteco support.
diff --git a/doc/sciteco.7.template b/doc/sciteco.7.template
index 9ce5bf8..c7dfc3e 100644
--- a/doc/sciteco.7.template
+++ b/doc/sciteco.7.template
@@ -350,6 +350,10 @@ TECO implementations.
 Most of these commands are control codes, so their control code
 mnemonics are given as well.
 .
+.\" FIXME: The auto-completion immediate editing commands
+.\" should probably be broken out of this table to keep it
+.\" small and moved into their own table in the AUTO COMPLETIONS
+.\" section.
 .SCITECO_TT 90n
 .TS
 expand,allbox,tab(;);
@@ -488,6 +492,24 @@ rubbed-out part of the command line, stopping at the string's
 terminating character.
 T}
 T{
+Auto complete Q-Register name
+T};9;^I, Tab;T{
+Q-Register specifications
+T};T{
+In all Q-Register specifications \(em either after a command
+with a Q-Register argument like \fBM\fP or as part of a string building
+construct like \fB^EQ\fP (of course including string building
+constructs \fIwithin\fP Q-Register specifications) \(em
+auto complete the local or global register name beginning at
+the start of the specification.
+In the case of one or two-letter specifications (\fB#\fIxy\fR),
+only one or two-letter register names are considered for
+auto-completion.
+In the case of long specifications (\fB[\fIname\fB]\fR),
+fully completed names are terminated with a closing bracket,
+thus ending the specification.
+T}
+T{
 Auto complete filename
 T};9;^I, Tab;T{
 String arguments
@@ -528,6 +550,26 @@ commands), complete beginning with the symbol, terminating fully
 completed symbols with a comma.
 T}
 T{
+Auto complete Goto label
+T};9;^I, Tab;T{
+Goto command arguments
+T};T{
+In Goto label arguments (\fBO\fP command),
+complete beginning with the current label, terminating fully
+completed labels with a comma.
+T}
+T{
+Auto complete help topic
+T};9;^I, Tab;T{
+Help topic arguments
+T};T{
+In help topic arguments (\fB?\fP command),
+complete beginning at the start of the command.
+Fully completed topics terminate the string argument,
+effectively opening the corresponding \fIwomanpage\fP,
+except if the \(lq{\(rq terminator is used.
+T}
+T{
 Indent to next tab stop
 T};9;^I, Tab;T{
 Text insertion arguments
diff --git a/src/cmdline.cpp b/src/cmdline.cpp
index 042cd6f..10e4a6b 100644
--- a/src/cmdline.cpp
+++ b/src/cmdline.cpp
@@ -39,6 +39,7 @@
 #include "ring.h"
 #include "ioview.h"
 #include "goto.h"
+#include "help.h"
 #include "undo.h"
 #include "symbols.h"
 #include "spawn.h"
@@ -443,6 +444,34 @@ Cmdline::process_edit_cmd(gchar key)
 				interface.popup_clear();
 				insert(key);
 			}
+		} else if (States::is_qreg()) {
+			if (interface.popup_is_shown()) {
+				/* cycle through popup pages */
+				interface.popup_show();
+				break;
+			}
+
+			QRegSpecMachine &machine = ((StateExpectQReg *)States::current)->machine;
+			gchar *new_chars = machine.auto_complete();
+
+			if (new_chars)
+				insert(new_chars);
+			g_free(new_chars);
+		} else if (States::is_string() &&
+		           ((StateExpectString *)States::current)->machine.qregspec_machine) {
+			if (interface.popup_is_shown()) {
+				/* cycle through popup pages */
+				interface.popup_show();
+				break;
+			}
+
+			QRegSpecMachine *machine =
+				((StateExpectString *)States::current)->machine.qregspec_machine;
+			gchar *new_chars = machine->auto_complete();
+
+			if (new_chars)
+				insert(new_chars);
+			g_free(new_chars);
 		} else if (States::is_insertion() && !interface.ssm(SCI_GETUSETABS)) {
 			interface.popup_clear();
 
@@ -514,6 +543,32 @@ Cmdline::process_edit_cmd(gchar key)
 			if (new_chars)
 				insert(new_chars);
 			g_free(new_chars);
+		} else if (States::current == &States::gotocmd) {
+			if (interface.popup_is_shown()) {
+				/* cycle through popup pages */
+				interface.popup_show();
+				break;
+			}
+
+			const gchar *label = last_occurrence(strings[0], ",");
+			gchar *new_chars = Goto::table->auto_complete(label);
+
+			if (new_chars)
+				insert(new_chars);
+			g_free(new_chars);
+		} else if (States::current == &States::gethelp) {
+			if (interface.popup_is_shown()) {
+				/* cycle through popup pages */
+				interface.popup_show();
+				break;
+			}
+
+			gchar complete = escape_char == '{' ? '\0' : escape_char;
+			gchar *new_chars = help_index.auto_complete(strings[0], complete);
+
+			if (new_chars)
+				insert(new_chars);
+			g_free(new_chars);
 		} else {
 			interface.popup_clear();
 			insert(key);
diff --git a/src/goto.h b/src/goto.h
index 4fa5766..f2064d1 100644
--- a/src/goto.h
+++ b/src/goto.h
@@ -94,6 +94,12 @@ public:
 		RBTreeString::clear();
 	}
 
+	inline gchar *
+	auto_complete(const gchar *name, gchar completed = ',')
+	{
+		return RBTreeString::auto_complete(name, completed);
+	}
+
 #ifdef DEBUG
 	void dump(void);
 #endif
diff --git a/src/help.h b/src/help.h
index 7ce7ea2..92115ab 100644
--- a/src/help.h
+++ b/src/help.h
@@ -53,6 +53,12 @@ public:
 
 	void set(const gchar *name, const gchar *filename,
 	         tecoInt pos = 0);
+
+	inline gchar *
+	auto_complete(const gchar *name, gchar completed = '\0')
+	{
+		return RBTreeStringCase::auto_complete(name, completed);
+	}
 };
 
 extern HelpIndex help_index;
diff --git a/src/parser.h b/src/parser.h
index b18e13c..f5dcba5 100644
--- a/src/parser.h
+++ b/src/parser.h
@@ -120,8 +120,6 @@ public:
 class QRegSpecMachine;
 
 class StringBuildingMachine : public MicroStateMachine<gchar *> {
-	QRegSpecMachine *qregspec_machine;
-
 	enum Mode {
 		MODE_NORMAL,
 		MODE_UPPER,
@@ -131,9 +129,11 @@ class StringBuildingMachine : public MicroStateMachine<gchar *> {
 	bool toctl;
 
 public:
+	QRegSpecMachine *qregspec_machine;
+
 	StringBuildingMachine() : MicroStateMachine<gchar *>(),
-				  qregspec_machine(NULL),
-				  mode(MODE_NORMAL), toctl(false) {}
+				  mode(MODE_NORMAL), toctl(false),
+				  qregspec_machine(NULL) {}
 	~StringBuildingMachine();
 
 	void reset(void);
@@ -147,7 +147,6 @@ public:
  * string building commands and accumulation into a string
  */
 class StateExpectString : public State {
-	StringBuildingMachine machine;
 	gsize insert_len;
 
 	gint nesting;
@@ -156,6 +155,13 @@ class StateExpectString : public State {
 	bool last;
 
 public:
+	/*
+	 * FIXME: Only public as long as cmdline.cpp
+	 * needs to access it.
+	 * Can be avoided one process_edit_cmd() is in State.
+	 */
+	StringBuildingMachine machine;
+
 	StateExpectString(bool _building = true, bool _last = true)
 			 : insert_len(0), nesting(1),
 			   string_building(_building), last(_last) {}
diff --git a/src/qregisters.cpp b/src/qregisters.cpp
index 6ca7990..23d7fc4 100644
--- a/src/qregisters.cpp
+++ b/src/qregisters.cpp
@@ -990,9 +990,16 @@ QRegSpecMachine::input(gchar chr, QRegister *&result)
 
 MICROSTATE_START;
 	switch (chr) {
-	case '.': undo.push_var(is_local) = true; break;
-	case '#': set(&&StateFirstChar); break;
-	case '[': set(&&StateString); break;
+	case '.':
+		undo.push_var(is_local) = true;
+		break;
+	case '#':
+		set(&&StateFirstChar);
+		break;
+	case '[':
+		set(&&StateString);
+		undo.push_var(nesting)++;
+		break;
 	default:
 		undo.push_str(name) = String::chrdup(String::toupper(chr));
 		goto done;
@@ -1003,6 +1010,7 @@ MICROSTATE_START;
 StateFirstChar:
 	undo.push_str(name) = (gchar *)g_malloc(3);
 	name[0] = String::toupper(chr);
+	name[1] = '\0';
 	set(&&StateSecondChar);
 	return false;
 
@@ -1017,9 +1025,9 @@ StateString:
 		undo.push_var(nesting)++;
 		break;
 	case ']':
+		undo.push_var(nesting)--;
 		if (!nesting)
 			goto done;
-		undo.push_var(nesting)--;
 		break;
 	}
 
@@ -1071,6 +1079,28 @@ done:
 	return true;
 }
 
+gchar *
+QRegSpecMachine::auto_complete(void)
+{
+	gsize restrict_len = 0;
+
+	if (string_machine.qregspec_machine)
+		/* nested Q-Reg definition */
+		return string_machine.qregspec_machine->auto_complete();
+
+	if (state == StateStart)
+		/* single-letter Q-Reg */
+		restrict_len = 1;
+	else if (!nesting)
+		/* two-letter Q-Reg */
+		restrict_len = 2;
+
+	QRegisterTable &table = is_local ? *QRegisters::locals
+	                                 : QRegisters::globals;
+	return table.auto_complete(name, nesting == 1 ? ']' : '\0',
+	                           restrict_len);
+}
+
 /*
  * Command states
  */
diff --git a/src/qregisters.h b/src/qregisters.h
index 1ea47ee..1d0962c 100644
--- a/src/qregisters.h
+++ b/src/qregisters.h
@@ -374,6 +374,12 @@ public:
 	void update_environ(void);
 
 	void clear(void);
+
+	inline gchar *
+	auto_complete(const gchar *name, gchar completed = '\0', gsize max_len = 0)
+	{
+		return RBTreeString::auto_complete(name, completed, max_len);
+	}
 };
 
 class QRegisterStack {
@@ -471,6 +477,8 @@ public:
 	{
 		throw InvalidQRegError(name, is_local);
 	}
+
+	gchar *auto_complete(void);
 };
 
 /*
@@ -482,14 +490,19 @@ public:
  */
 class StateExpectQReg : public State {
 public:
+	/*
+	 * FIXME: Only public, so we can access it from
+	 * cmdline.cpp. Will not be necessary if process_edit_cmd()
+	 * is a State method.
+	 */
+	QRegSpecMachine machine;
+
 	StateExpectQReg(QRegSpecType type = QREG_REQUIRED);
 
 private:
 	State *custom(gchar chr);
 
 protected:
-	QRegSpecMachine machine;
-
 	virtual State *got_register(QRegister *reg) = 0;
 };
 
@@ -624,6 +637,12 @@ namespace States {
 	extern StateMacro		macro;
 	extern StateMacroFile		macro_file;
 	extern StateCopyToQReg		copytoqreg;
+
+	static inline bool
+	is_qreg()
+	{
+		return dynamic_cast<StateExpectQReg *>(current);
+	}
 }
 
 namespace QRegisters {
diff --git a/src/rbtree.cpp b/src/rbtree.cpp
index f1d870d..5b1a4e1 100644
--- a/src/rbtree.cpp
+++ b/src/rbtree.cpp
@@ -19,13 +19,71 @@
 #include "config.h"
 #endif
 
+#include <string.h>
+
 #include <glib.h>
 #include <glib/gprintf.h>
 
+#include "sciteco.h"
 #include "rbtree.h"
+#include "interface.h"
+#include "string-utils.h"
 
 namespace SciTECO {
 
+template <StringCmpFunc StringCmp, StringNCmpFunc StringNCmp>
+gchar *
+RBTreeStringT<StringCmp, StringNCmp>::
+auto_complete(const gchar *key, gchar completed, gsize restrict_len)
+{
+	gsize key_len;
+	RBEntryString *first = NULL;
+	gsize prefix_len = 0;
+	gint prefixed_entries = 0;
+	gchar *insert = NULL;
+
+	if (!key)
+		key = "";
+	key_len = strlen(key);
+
+	for (RBEntryString *cur = nfind(key);
+	     cur && !StringNCmp(cur->key, key, key_len);
+	     cur = (RBEntryString *)cur->next()) {
+		if (restrict_len && strlen(cur->key) != restrict_len)
+			continue;
+
+		if (!first)
+			first = cur;
+
+		gsize len = String::diff(first->key + key_len,
+					 cur->key + key_len);
+		if (!prefix_len || len < prefix_len)
+			prefix_len = len;
+
+		prefixed_entries++;
+	}
+	if (prefix_len > 0)
+		insert = g_strndup(first->key + key_len, prefix_len);
+
+	if (!insert && prefixed_entries > 1) {
+		for (RBEntryString *cur = first;
+		     cur && !StringNCmp(cur->key, key, key_len);
+		     cur = (RBEntryString *)cur->next()) {
+			if (restrict_len && strlen(cur->key) != restrict_len)
+				continue;
+
+			interface.popup_add(InterfaceCurrent::POPUP_PLAIN,
+					    cur->key);
+		}
+
+		interface.popup_show();
+	} else if (prefixed_entries == 1) {
+		String::append(insert, completed);
+	}
+
+	return insert;
+}
+
 template class RBTreeStringT<strcmp, strncmp>;
 template class RBTreeStringT<g_ascii_strcasecmp, g_ascii_strncasecmp>;
 
diff --git a/src/rbtree.h b/src/rbtree.h
index 4a4bbdb..76b2141 100644
--- a/src/rbtree.h
+++ b/src/rbtree.h
@@ -181,6 +181,9 @@ public:
 		RBEntryString entry((gchar *)str);
 		return RBTree<RBEntryString>::nfind(&entry);
 	}
+
+	gchar *auto_complete(const gchar *key, gchar completed = '\0',
+	                     gsize restrict_len = 0);
 };
 
 typedef RBTreeStringT<strcmp, strncmp> RBTreeString;