add fuzzy matching, bump versionHEADmaster

3 files changed, 95 insertions, 3 deletions

diff --git a/src/Globals.h b/src/Globals.h
index 95a61ea..71592c9 100644
--- a/src/Globals.h
+++ b/src/Globals.h
@@ -15,6 +15,7 @@ typedef struct {
 typedef struct {
   char *prompt;
   int insensitive;
+  int fuzzy;
 } Options;
 
 extern Options opts;
diff --git a/src/Input.c b/src/Input.c
index 23a474d..2bb1889 100644
--- a/src/Input.c
+++ b/src/Input.c
@@ -8,8 +8,13 @@
 #include "Terminal.h"
 #include "Input.h"
 
+int fuzzy_score(const char *s);
+
 int matches(const char *s) {
   if (input_len == 0) return 1;
+  if (opts.fuzzy) {
+    return fuzzy_score(s) >= 0;
+  }
   const char *p = s;
   if (opts.insensitive) {
     while (*p) {
@@ -25,6 +30,82 @@ int matches(const char *s) {
   return 0;
 }
 
+static int is_separator(char c) {
+  return c == ' ' || c == '-' || c == '_' || c == '.' || c == '/' || c == '\\';
+}
+
+int fuzzy_score(const char *s) {
+  if (input_len == 0) return 0;
+  int score = 0;
+  int prev_pos = -1;
+  const char *input_lower = NULL;
+  const char *s_lower = NULL;
+  char s_lower_buf[1024];
+  char input_lower_buf[256];
+
+  if (opts.insensitive) {
+    for (size_t i = 0; i < input_len && i < 255; i++) {
+      input_lower_buf[i] = tolower(input[i]);
+    }
+    input_lower_buf[input_len] = '\0';
+    input_lower = input_lower_buf;
+
+    size_t slen = strlen(s);
+    if (slen < 1024) {
+      for (size_t i = 0; i <= slen; i++) {
+        s_lower_buf[i] = tolower(s[i]);
+      }
+      s_lower = s_lower_buf;
+    }
+  }
+
+  const char *search = input_lower ? input_lower : input;
+  const char *search_s = s_lower ? s_lower : s;
+
+  for (size_t i = 0; i < input_len; i++) {
+    const char *found = NULL;
+    int best_pos = -1;
+    int best_score = -1000;
+    const char *p = search_s;
+    int pos = 0;
+    while (*p) {
+      if (*p == search[i] && (i == 0 || pos > prev_pos)) {
+        int char_score;
+        if (i == 0) {
+          if (pos == 0) char_score = 25;
+          else if (is_separator(s[pos - 1])) char_score = 3;
+          else char_score = 1;
+        } else {
+          if (prev_pos + 1 == pos) char_score = 25;
+          else if (is_separator(s[pos - 1])) char_score = 1;
+          else char_score = 8 - (pos - prev_pos - 1) * 2;
+        }
+        if (char_score > best_score) {
+          best_score = char_score;
+          best_pos = pos;
+          found = p;
+        }
+      }
+      p++;
+      pos++;
+    }
+    if (!found) return -1;
+    score += best_score;
+    if (score < 1) score = 1;
+    prev_pos = best_pos;
+  }
+  score -= (int)(strlen(s) / 3);
+  return score;
+}
+
+static int compare_scores(const void *a, const void *b) {
+  char *const *sa = a;
+  char *const *sb = b;
+  int score_a = fuzzy_score(*sa);
+  int score_b = fuzzy_score(*sb);
+  return score_b - score_a;
+}
+
 void filter_items(void) {
   filtered.count = 0;
   for (size_t i = 0; i < all_items.count; i++) {
@@ -37,6 +118,9 @@ void filter_items(void) {
       filtered.items[filtered.count++] = all_items.items[i];
     }
   }
+  if (opts.fuzzy && filtered.count > 1) {
+    qsort(filtered.items, filtered.count, sizeof(char *), compare_scores);
+  }
   if ((size_t)cursor >= filtered.count) cursor = filtered.count > 0 ? (int)filtered.count - 1 : 0;
   if (scroll > cursor) scroll = cursor;
   if (scroll < cursor - DEFAULT_LINES + 1) scroll = cursor - DEFAULT_LINES + 1;
diff --git a/src/Main.c b/src/Main.c
index 4ecd4f3..e941921 100644
--- a/src/Main.c
+++ b/src/Main.c
@@ -11,7 +11,8 @@
 
 Options opts = {
   .prompt = "",
-  .insensitive = 0
+  .insensitive = 0,
+  .fuzzy = 0
 };
 
 ItemList all_items = {0};
@@ -45,7 +46,7 @@ void read_items(void) {
 }
 
 void version(void) {
-  puts("insel 1.0");
+  puts("insel 1.1");
   puts("'those who select their inputs'\n");
   puts("GNU GPL version 2 <https://gnu.org/licenses/old-licenses/gpl-2.0.html>.\n"
      "This is free software: you are free to change and redistribute it.\n"
@@ -54,12 +55,14 @@ void version(void) {
 }
 
 void help(void) {
-  puts("Usage: insel [-i] [-p prompt]"
+  puts("Usage: insel [-i] [-F] [-p prompt]"
           "\n"
           "Options:"
           "\n"
           "  -i          Case-insensitive matching"
           "\n"
+          "  -F          Fuzzy matching (implies -i)"
+          "\n"
           "  -v          Show version"
           "\n"
           "  -p prompt   Prompt to display"
@@ -76,6 +79,10 @@ int main(int argc, char *argv[]) {
     if (strcmp(argv[i], "-v") == 0) version();
     else if (strcmp(argv[i], "--help") == 0) help();
     else if (strcmp(argv[i], "-i") == 0) opts.insensitive = 1;
+    else if (strcmp(argv[i], "-F") == 0) {
+      opts.fuzzy = 1;
+      opts.insensitive = 1;
+    }
     else if (strcmp(argv[i], "-b") == 0 && i + 1 < argc) i++;
     else if (strcmp(argv[i], "-f") == 0 && i + 1 < argc) i++;
     else if (strcmp(argv[i], "-l") == 0 && i + 1 < argc) i++;