From 2734e126aaff3d08cefac9d9b9c7701ab6f32668 Mon Sep 17 00:00:00 2001
From: auric <104602845+ihateamongus@users.noreply.github.com>
Date: Thu, 11 Sep 2025 20:38:12 -0500
Subject: Rank dmenu matches by query similarity

---
 core/dmenu/dmenu.c | 76 +++++++++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 61 insertions(+), 15 deletions(-)

(limited to 'core/dmenu')

diff --git a/core/dmenu/dmenu.c b/core/dmenu/dmenu.c
index 6ca6db6..5769e19 100644
--- a/core/dmenu/dmenu.c
+++ b/core/dmenu/dmenu.c
@@ -33,9 +33,10 @@
 enum { SchemeNorm, SchemeSel, SchemeOut, SchemeLast }; /* color schemes */
 
 struct item {
-	char *text;
-	struct item *left, *right;
-	int out;
+        char *text;
+        struct item *left, *right;
+        int out;
+        int distance;
 };
 
 static char text[BUFSIZ] = "";
@@ -85,17 +86,57 @@ fuzzy(const char *text, const char *pattern)
         return 1;
 }
 
+static int
+levenshtein(const char *s1, const char *s2)
+{
+        size_t len1 = strlen(s1), len2 = strlen(s2);
+        size_t i, j;
+        int *v0 = ecalloc(len2 + 1, sizeof *v0);
+        int *v1 = ecalloc(len2 + 1, sizeof *v1);
+
+        for (j = 0; j <= len2; j++)
+                v0[j] = j;
+        for (i = 0; i < len1; i++) {
+                v1[0] = i + 1;
+                for (j = 0; j < len2; j++) {
+                        int cost = tolower((unsigned char)s1[i]) == tolower((unsigned char)s2[j]) ? 0 : 1;
+                        v1[j + 1] = MIN(MIN(v1[j] + 1, v0[j + 1] + 1), v0[j] + cost);
+                }
+                memcpy(v0, v1, (len2 + 1) * sizeof *v0);
+        }
+        i = v0[len2];
+        free(v0);
+        free(v1);
+        return i;
+}
+
 static void
 appenditem(struct item *item, struct item **list, struct item **last)
 {
-	if (*last)
-		(*last)->right = item;
-	else
-		*list = item;
+        struct item *i;
 
-	item->left = *last;
-	item->right = NULL;
-	*last = item;
+        if (!*list) {
+                item->left = item->right = NULL;
+                *list = *last = item;
+                return;
+        }
+
+        for (i = *list; i && item->distance >= i->distance; i = i->right)
+                ;
+        if (!i) {
+                (*last)->right = item;
+                item->left = *last;
+                item->right = NULL;
+                *last = item;
+        } else {
+                item->right = i;
+                item->left = i->left;
+                if (i->left)
+                        i->left->right = item;
+                else
+                        *list = item;
+                i->left = item;
+        }
 }
 
 static void
@@ -261,11 +302,15 @@ match(void)
 
         matches = matchend = NULL;
         for (item = items; item && item->text; item++) {
-                for (i = 0; i < tokc; i++)
+                int distance = 0;
+                for (i = 0; i < tokc; i++) {
                         if (!fuzzy(item->text, tokv[i]))
                                 break;
+                        distance += levenshtein(item->text, tokv[i]);
+                }
                 if (i != tokc)
                         continue;
+                item->distance = distance;
                 appenditem(item, &matches, &matchend);
         }
         curr = sel = matches;
@@ -553,11 +598,12 @@ readstdin(void)
 		}
 		if (line[len - 1] == '\n')
 			line[len - 1] = '\0';
-		if (!(items[i].text = strdup(line)))
-			die("strdup:");
+                if (!(items[i].text = strdup(line)))
+                        die("strdup:");
 
-		items[i].out = 0;
-	}
+                items[i].out = 0;
+                items[i].distance = 0;
+        }
 	free(line);
 	if (items)
 		items[i].text = NULL;
-- 
cgit v1.2.3