apps: better fuzzy search algorithm

3 files changed, 84 insertions, 42 deletions

diff --git a/lib/apps/application.vala b/lib/apps/application.vala
index 5748fc6..75ff6b2 100644
--- a/lib/apps/application.vala
+++ b/lib/apps/application.vala
@@ -32,13 +32,13 @@ public class Application : Object {
     public Score fuzzy_match(string term) {
         var score = Score();
         if (name != null)
-            score.name = levenshtein(term, name);
+            score.name = fuzzy_match_string(term, name);
         if (entry != null)
-            score.entry = levenshtein(term, entry);
+            score.entry = fuzzy_match_string(term, entry);
         if (executable != null)
-            score.executable = levenshtein(term, executable);
+            score.executable = fuzzy_match_string(term, executable);
         if (description != null)
-            score.description = levenshtein(term, description);
+            score.description = fuzzy_match_string(term, description);
 
         return score;
     }
@@ -75,44 +75,10 @@ int min3(int a, int b, int c) {
     return (a < b) ? ((a < c) ? a : c) : ((b < c) ? b : c);
 }
 
-double levenshtein(string s1, string s2) {
-    int len1 = s1.length;
-    int len2 = s2.length;
-
-    int[, ] d = new int[len1 + 1, len2 + 1];
-
-    for (int i = 0; i <= len1; i++) {
-        d[i, 0] = i;
-    }
-    for (int j = 0; j <= len2; j++) {
-        d[0, j] = j;
-    }
-
-    for (int i = 1; i <= len1; i++) {
-        for (int j = 1; j <= len2; j++) {
-            int cost = (s1[i - 1] == s2[j - 1]) ? 0 : 1;
-            d[i, j] = min3(
-                d[i - 1, j] + 1,       // deletion
-                d[i, j - 1] + 1,       // insertion
-                d[i - 1, j - 1] + cost // substitution
-            );
-        }
-    }
-
-    var distance = d[len1, len2];
-    int max_len = len1 > len2 ? len1 : len2;
-
-    if (max_len == 0) {
-        return 1.0;
-    }
-
-    return 1.0 - ((double)distance / max_len);
-}
-
 public struct Score {
-    double name;
-    double entry;
-    double executable;
-    double description;
+    int name;
+    int entry;
+    int executable;
+    int description;
 }
 }
diff --git a/lib/apps/fuzzy.vala b/lib/apps/fuzzy.vala
new file mode 100644
index 0000000..d6dac3d
--- /dev/null
+++ b/lib/apps/fuzzy.vala
@@ -0,0 +1,75 @@
+
+namespace AstalApps {
+
+    private int max(int a, int b) {
+      return a > b ? a : b;
+    }
+
+    public int fuzzy_match_string(string pattern, string str) {
+        const int unmatched_letter_penalty = -1;
+        int score = 100;
+
+        if (pattern.length == 0) return score;
+        if (str.length < pattern.length) return int.MIN;
+
+        score += unmatched_letter_penalty * (str.length - pattern.length);
+        score = fuzzy_match_recurse(pattern, str, score, true);
+
+        return score;
+    }
+
+    private int fuzzy_match_recurse(string pattern, string str, int score, bool first_char) {
+        if (pattern.length == 0) return score;
+
+        int match_idx = 0;
+        int offset = 0;
+        unichar search = pattern.casefold().get_char(0);
+        int best_score = int.MIN;
+
+        while ((match_idx = str.casefold().substring(offset).index_of_char(search)) >= 0) {
+            offset += match_idx;
+            int subscore = fuzzy_match_recurse(
+                pattern.substring(1),
+                str.substring(offset + 1),
+                compute_score(offset, first_char, str, offset), false);
+            best_score = max(best_score, subscore);
+            offset++;
+        }
+
+
+        if (best_score == int.MIN) return int.MIN;
+        return score + best_score;
+    }
+
+    private int compute_score(int jump, bool first_char, string match, int idx) {
+        const int adjacency_bonus = 15;
+        const int separator_bonus = 30;
+        const int camel_bonus = 30;
+        const int first_letter_bonus = 15;
+        const int leading_letter_penalty = -5;
+        const int max_leading_letter_penalty = -15;
+
+        int score = 0;
+
+        if (!first_char && jump == 0) {
+            score += adjacency_bonus;
+        }
+        if (!first_char || jump > 0) {
+            if (match[idx].isupper() && match[idx-1].islower()) {
+                score += camel_bonus;
+            }
+            if (match[idx].isalnum() && !match[idx-1].isalnum()) {
+                score += separator_bonus;
+            }
+        }
+        if (first_char && jump == 0) {
+            score += first_letter_bonus;
+        }
+        if (first_char) {
+            score += max(leading_letter_penalty * jump, max_leading_letter_penalty);
+        }
+
+        return score;
+    }
+
+}
diff --git a/lib/apps/meson.build b/lib/apps/meson.build
index fb87e22..b83b216 100644
--- a/lib/apps/meson.build
+++ b/lib/apps/meson.build
@@ -44,6 +44,7 @@ sources = [
   'apps.vala',
   'application.vala',
   'cli.vala',
+  'fuzzy.vala',
 ]
 
 if get_option('lib')