add fuzzy matching, bump versionHEADmaster

1 files changed, 84 insertions, 0 deletions

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;