Improved cycling with ctrl-p/ctrl-n and better rendering of highlighted

partial matches (with grouping to greedily maximize longest highlighted
substrings)

1 files changed, 86 insertions, 51 deletions

diff --git a/ask.c b/ask.c
index 1768a8b..f09b701 100644
--- a/ask.c
+++ b/ask.c
@@ -23,7 +23,7 @@
 #define EQ(a, b) (case_sensitive ? (a) == (b) : LOWERCASE(a) == LOWERCASE(b))
 #define PASSWORD "-\\|/"
 
-static int password = 0, quickpick = 0, case_sensitive = 0, to_skip = 0;
+static int password = 0, quickpick = 0, case_sensitive = 0;
 
 static inline void *memcheck(void *p)
 {
@@ -34,44 +34,72 @@ static inline void *memcheck(void *p)
     return p;
 }
 
-static int score(const char *str, const char *patt)
+/* Return length of the longest substring of patt[p:] that occurs within
+ * str[s:], while still leaving enough space for the rest of `patt` to occur
+ * within the rest of `str`. If there is no valid solution, return -1.
+ */
+static int lcs(const char *str, const char *patt, int slen, int plen, int s, int p, int *cache)
 {
-    if (!patt[0]) return 0;
-    int score = 0;
-    const char *s = str, *p = patt;
-    while (*s && !EQ(*s, *p)) ++s;
-    while (*s && *p && EQ(*s, *p)) {
-        ++score;
-        ++s;
-        ++p;
+    if (!patt[p]) return 0;
+    if (!str[s]) return -1;
+    if (cache[s*plen + p]) return cache[s*plen + p];
+    if (!EQ(str[s], patt[p])) return lcs(str, patt, slen, plen, s+1, p, cache);
+    // Run starting here
+    int run = 1;
+    while (str[s+run] && patt[p+run] && EQ(str[s+run], patt[p+run])
+           && lcs(str, patt, slen, plen, s+run, p+run, cache) >= 0) {
+        ++run;
     }
-    for (; *p; ++s, ++p) {
-        while (*s && !EQ(*s, *p)) ++s;
-        if (!*s) return 0;
+    if (run == 0) run = -1;
+    cache[s*plen + p] = run;
+    return run;
+}
+
+static int matches(const char *str, const char *patt)
+{
+    while (*patt) {
+        while (!EQ(*str, *patt)) {
+            if (!*str) return 0;
+            ++str;
+        }
+        ++str;
+        ++patt;
     }
-    if (*p && !*s) return 0;
-    return score;
+    return 1;
 }
 
-static void draw_line(FILE *out, const char *line, const char *hl, const char *cur)
+static void draw_line(FILE *out, const char *line, const char *patt, int cursor)
 {
-    int dim = 0, backtrack = 0;
-    for (const char *pl = line, *phl = hl; *pl; pl++) {
-        if (phl >= cur) ++backtrack;
-        if (case_sensitive ? *pl == *phl : LOWERCASE(*pl) == LOWERCASE(*phl)) {
-            ++phl;
+    size_t linelen = strlen(line), patlen = strlen(patt);
+    int dim = 0;
+    int p = 0;
+    int run = 0;
+    int *cache = calloc((linelen+1)*(patlen+1), sizeof(int));
+    if (cursor >= (int)patlen)
+        fputs("\0337", out);
+    for (int i = 0; i < (int)linelen; i++) {
+        if (EQ(patt[p], line[i]) &&
+            run + lcs(line,patt,(int)linelen,(int)patlen,i,p,cache)
+            >= lcs(line,patt,(int)linelen,(int)patlen,i+1,p,cache)) {
             if (dim) {
                 fputs("\033[22m", out);
                 dim = 0;
             }
-        } else if (!dim) {
-            fputs("\033[2m", out);
-            dim = 1;
+            fputc(patt[p], out);
+            ++run;
+            ++p;
+            if (cursor == p)
+                fputs("\0337", out);
+        } else {
+            run = 0;
+            if (!dim) {
+                fputs("\033[2m", out);
+                dim = 1;
+            }
+            fputc(line[i], out);
         }
-        fputc(*pl, out);
     }
-    if (backtrack)
-        fprintf(out, "\033[%dD", backtrack);
+    fputs("\0338", out);
 }
 
 /*
@@ -90,6 +118,7 @@ static char *get_input(FILE *in, FILE *out, const char *prompt, const char *init
         fputs(initial, out);
     }
 
+    int start = 0;
     // Show cursor and set to blinking line:
     while (1) {
         fputs("\033[G\033[K\033[0m", out);
@@ -98,43 +127,35 @@ static char *get_input(FILE *in, FILE *out, const char *prompt, const char *init
             fputs(prompt, out);
             fputs("\033[0m", out);
         }
-        picked = NULL;
         case_sensitive = 0;
         for (const char *p = buf; *p; ++p)
             case_sensitive |= ('A' <= *p && *p <= 'Z');
 
         int ncandidates = 0;
-        for (int i = 0; i < nopts; i++)
-            ncandidates += score(opts[i], buf) > 0;
-
-        int bestscore = 0;
-        char *best = NULL;
-        int skipped = 0;
+        picked = NULL;
         for (int i = 0; i < nopts; i++) {
-            int s = score(opts[i], buf);
-            if (s && skipped < to_skip) {
-                ++skipped;
-                continue;
-            }
-            if (s > bestscore) {
-                best = opts[i];
-                bestscore = s;
+            int j = (start + i) % nopts;
+            if (matches(opts[j], buf)) {
+                ++ncandidates;
+                if (!picked) {
+                    picked = opts[j];
+                    start = j;
+                }
             }
         }
 
-        picked = best;
-        if (quickpick && ncandidates == 1 && best)
+        if (quickpick && ncandidates == 1 && picked)
             goto finished;
 
         if (password) {
-            if (best) fputs("\033[0;32m", out);
+            if (picked) fputs("\033[0;32m", out);
             else if (nopts > 0) fputs("\033[0;31m", out);
             else fputs("\033[0;2m", out);
             fputc((PASSWORD)[strlen(buf) % strlen(PASSWORD)], out);
             fputs("\033[0m", out);
         } else {
-            if (best) {
-                draw_line(out, best, buf, &buf[b]);
+            if (picked) {
+                draw_line(out, picked, buf, b);
             } else {
                 if (nopts > 0)
                     fprintf(out, "\033[0;31m%s\033[0m", buf);
@@ -178,12 +199,26 @@ static char *get_input(FILE *in, FILE *out, const char *prompt, const char *init
                     buf[len = b] = 0;
                 break;
             case KEY_CTRL_N:
-                if (ncandidates)
-                    to_skip = (to_skip + 1) % ncandidates;
+                if (picked) {
+                    for (int i = 1; i < nopts; i++) {
+                        int j = (start + i) % nopts;
+                        if (matches(opts[j], buf)) {
+                            start = j;
+                            break;
+                        }
+                    }
+                }
                 break;
             case KEY_CTRL_P:
-                if (ncandidates)
-                    to_skip = (to_skip + ncandidates - 1) % ncandidates;
+                if (picked) {
+                    for (int i = nopts-1; i > 0; i--) {
+                        int j = (start + i) % nopts;
+                        if (matches(opts[j], buf)) {
+                            start = j;
+                            break;
+                        }
+                    }
+                }
                 break;
             case KEY_BACKSPACE: case KEY_BACKSPACE2:
                 if (b > 0) {