linenoise: Ctrl-R search

* linenoise/linenoise.c (next_hist_match, history_search): New
static function.
(edit): New Ctrl-R case added to early switch that also
handles Tab completion, and calls history_search.
(lino_free): Adding null check, so we can safely call
lino_free(0). history_search relies on this.

* txr.1: Documented search.

2 files changed, 180 insertions, 3 deletions

diff --git a/linenoise/linenoise.c b/linenoise/linenoise.c
index 404cf284..47d1754e 100644
--- a/linenoise/linenoise.c
+++ b/linenoise/linenoise.c
@@ -390,6 +390,133 @@ void lino_add_completion(lino_completions_t *lc, const char *str) {
     lc->cvec[lc->len++] = copy;
 }
 
+static int next_hist_match(lino_t *l, char *pat, int cur, size_t *offs)
+{
+    int i;
+
+    if (cur >= l->history_len)
+        cur = l->history_len - 1;
+
+    for (i = cur; i >= 0; i--) {
+        char *hline = l->history[i];
+        char *pmatch = strstr(hline, pat);
+        if (pmatch != 0) {
+            *offs = pmatch - hline;
+            return i;
+        }
+    }
+    return -1;
+}
+
+static int history_search(lino_t *l)
+{
+    char hpat[128] = "";
+    int hi = l->history_len - l->history_index - 2 + (l->history_index == 0);
+    int hp = hi, hl = 0, stop = 0;
+    size_t dp = l->dpos;
+    const char *fmt = "[%s]%s";
+    size_t ex = strlen(fmt) - 2*strlen("%s");
+    lino_t *lc = lino_copy(l), *ld = lino_copy(l);
+    int c = -1;
+
+    if (lc == 0 || ld == 0)
+        goto out;
+
+    lc->prompt = "search:";
+
+    while (!stop) {
+        size_t nw = snprintf(lc->data, sizeof lc->data, fmt, hpat, l->data);
+        int vb = 0;
+        lc->dlen = nw;
+        lc->dpos = dp + hl + ex;
+
+        if (lc->dpos > lc->dlen)
+            lc->dpos = lc->dlen;
+
+        refresh_line(lc);
+
+        for (;;) {
+            unsigned char byte;
+            int nread = read(lc->ifd, &byte, 1);
+
+            if (nread <= 0) {
+                c = nread;
+                stop = 1;
+            } else {
+                c = byte;
+
+                if (vb)
+                    goto verbatim;
+
+                switch (c) {
+                default:
+                    if (c < 32)
+                        continue;
+                verbatim:
+                    if (hl >= sizeof hpat)
+                        break;
+                    hpat[hl++] = c;
+                    /* fallthrough */
+                    if (0) {
+                case CTL('R'):
+                        if (hl == 0) {
+                            generate_beep(lc);
+                            break;
+                        }
+                        hp = hi - 1;
+                    }
+
+                    {
+                        int ni = next_hist_match(l, hpat, hp, &dp);
+
+                        if (ni < 0)
+                            break;
+
+                        hi = ni;
+                        strcpy(l->data, l->history[hi]);
+                        l->dpos = l->dlen = strlen(l->data);
+                    }
+                    break;
+                case BACKSPACE: case CTL('H'):
+                    if (hl == 0)
+                        break;
+
+                    hpat[--hl] = 0;
+                    break;
+                case ENTER:
+                    stop = 1;
+                    break;
+                case CTL('C'):
+                    strcpy(l->data, ld->data);
+                    l->dpos = ld->dpos;
+                    l->dlen = ld->dlen;
+                    stop = 1;
+                    c = 0;
+                    break;
+                case CTL('F'): case CTL('B'):
+                case CTL('N'): case CTL('P'):
+                case ESC:
+                    if (hi < l->history_len)
+                        l->history_index = l->history_len - hi - 1;
+                    l->dpos = dp;
+                    stop = 1;
+                    break;
+                case CTL('V'):
+                    vb = 1;
+                    continue;
+                }
+            }
+            break;
+        }
+    }
+
+out:
+    lino_free(lc);
+    lino_free(ld);
+    refresh_line(l);
+    return c;
+}
+
 /* =========================== Line editing ================================= */
 
 /* We define a very simple "append buffer" structure, that is an heap
@@ -786,6 +913,9 @@ static int edit(lino_t *l, const char *prompt)
             if (l->completion_callback != NULL)
                 c = complete_line(l);
             break;
+        case CTL('R'):
+            c = history_search(l);
+            break;
         }
 
         if (c < 0)
@@ -1048,9 +1178,11 @@ static void lino_cleanup(lino_t *ls)
 
 void lino_free(lino_t *ls)
 {
-    unlink_from_list(ls);
-    lino_cleanup(ls);
-    free(ls);
+    if (ls != 0) {
+        unlink_from_list(ls);
+        lino_cleanup(ls);
+        free(ls);
+    }
 }
 
 lino_error_t lino_get_error(lino_t *l)
diff --git a/txr.1 b/txr.1
index 5e054e83..3647102f 100644
--- a/txr.1
+++ b/txr.1
@@ -33535,6 +33535,51 @@ from the most recent line already in history. This is true whether it
 is a freshly composed line, a recalled history line, or an edited
 history line.
 
+.NP* History Search
+It is possible to search backwards through the history interactively
+for a line containing a substring. The Ctrl-R command is used to initiate
+search.  The command prompt is replaced with the prefix
+.code search:
+next to which a pair of empty square brackets appears, indicating
+that the listener is in search mode. The square brackets are the
+search box, enclosing the search text, which is initially empty.
+
+In search mode, characters may be typed. They accumulate inside the search
+box, and constitute the string to search for. The listener instantly
+navigates to the most recent line which contains a substring match for the
+search string, and places the cursor on the first character of the
+match. Control characters entered directly are ignored. The Ctrl-V command be
+used to add a character verbatim, as in edit mode.
+
+To remove characters from the search box, Backspace can be used. The
+search is not repeated with the shortened search text: the same line
+continues to show until a character is added, at which point
+a new search is issued.
+
+Search mode has a "home position": a starting point for searches.
+The initial home position is whatever line of history is selected
+when search mode is initiated. Searches work backward in history from
+that line. If search text is edited by deleting characters and then
+adding new ones, the new search proceeds from the home position.
+
+The Ctrl-R command can be used in search mode. It registers the currently
+showing line as the new home position, and then repeats the search using the
+existing search text backwards from the new position. If the search text
+is empty, Ctrl-R has no effect.
+
+The Ctrl-C command leaves search mode at any time and causes the
+listener to resume editing the original input at the original character
+position. The Enter key accepts the result of a search and submits it
+as if it were a newly composed line.
+
+Navigation keys may be used in search mode. A navigation key immediately
+cancels search mode, and is processed in edit mode, using whatever line was
+located by the search, at the matching character position.
+
+Navigating to a history line manually using the up and down arrow keys (or
+Ctrl-P/Ctrl-N) has the same net effect same as locating that line using
+Ctrl-R search.
+
 .NP* History Persistence
 
 The history is maintained in a text file called