1 From 94353eb52055927d9079f3d9e33da1c954abf386 Mon Sep 17 00:00:00 2001 2 From: aleks <aleks.stier@icloud.com> 3 Date: Wed, 26 Jun 2019 13:25:10 +0200 4 Subject: [PATCH] Add support for fuzzy-matching 5 6 --- 7 config.def.h | 1 + 8 config.mk | 2 +- 9 dmenu.c | 89 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 10 3 files changed, 91 insertions(+), 1 deletion(-) 11 12 diff --git a/config.def.h b/config.def.h 13 index 1edb647..51612b9 100644 14 --- a/config.def.h 15 +++ b/config.def.h 16 @@ -2,6 +2,7 @@ 17 /* Default settings; can be overriden by command line. */ 18 19 static int topbar = 1; /* -b option; if 0, dmenu appears at bottom */ 20 +static int fuzzy = 1; /* -F option; if 0, dmenu doesn't use fuzzy matching */ 21 /* -fn option overrides fonts[0]; default X11 font or font set */ 22 static const char *fonts[] = { 23 "monospace:size=10" 24 diff --git a/config.mk b/config.mk 25 index 0929b4a..d14309a 100644 26 --- a/config.mk 27 +++ b/config.mk 28 @@ -20,7 +20,7 @@ FREETYPEINC = /usr/include/freetype2 29 30 # includes and libs 31 INCS = -I$(X11INC) -I$(FREETYPEINC) 32 -LIBS = -L$(X11LIB) -lX11 $(XINERAMALIBS) $(FREETYPELIBS) 33 +LIBS = -L$(X11LIB) -lX11 $(XINERAMALIBS) $(FREETYPELIBS) -lm 34 35 # flags 36 CPPFLAGS = -D_DEFAULT_SOURCE -D_BSD_SOURCE -D_XOPEN_SOURCE=700 -D_POSIX_C_SOURCE=200809L -DVERSION=\"$(VERSION)\" $(XINERAMAFLAGS) 37 diff --git a/dmenu.c b/dmenu.c 38 index 6b8f51b..96ddc98 100644 39 --- a/dmenu.c 40 +++ b/dmenu.c 41 @@ -1,6 +1,7 @@ 42 /* See LICENSE file for copyright and license details. */ 43 #include <ctype.h> 44 #include <locale.h> 45 +#include <math.h> 46 #include <stdio.h> 47 #include <stdlib.h> 48 #include <string.h> 49 @@ -32,6 +33,7 @@ struct item { 50 char *text; 51 struct item *left, *right; 52 int out; 53 + double distance; 54 }; 55 56 static char text[BUFSIZ] = ""; 57 @@ -210,9 +212,94 @@ grabkeyboard(void) 58 die("cannot grab keyboard"); 59 } 60 61 +int 62 +compare_distance(const void *a, const void *b) 63 +{ 64 + struct item *da = *(struct item **) a; 65 + struct item *db = *(struct item **) b; 66 + 67 + if (!db) 68 + return 1; 69 + if (!da) 70 + return -1; 71 + 72 + return da->distance == db->distance ? 0 : da->distance < db->distance ? -1 : 1; 73 +} 74 + 75 +void 76 +fuzzymatch(void) 77 +{ 78 + /* bang - we have so much memory */ 79 + struct item *it; 80 + struct item **fuzzymatches = NULL; 81 + char c; 82 + int number_of_matches = 0, i, pidx, sidx, eidx; 83 + int text_len = strlen(text), itext_len; 84 + 85 + matches = matchend = NULL; 86 + 87 + /* walk through all items */ 88 + for (it = items; it && it->text; it++) { 89 + if (text_len) { 90 + itext_len = strlen(it->text); 91 + pidx = 0; /* pointer */ 92 + sidx = eidx = -1; /* start of match, end of match */ 93 + /* walk through item text */ 94 + for (i = 0; i < itext_len && (c = it->text[i]); i++) { 95 + /* fuzzy match pattern */ 96 + if (!fstrncmp(&text[pidx], &c, 1)) { 97 + if(sidx == -1) 98 + sidx = i; 99 + pidx++; 100 + if (pidx == text_len) { 101 + eidx = i; 102 + break; 103 + } 104 + } 105 + } 106 + /* build list of matches */ 107 + if (eidx != -1) { 108 + /* compute distance */ 109 + /* add penalty if match starts late (log(sidx+2)) 110 + * add penalty for long a match without many matching characters */ 111 + it->distance = log(sidx + 2) + (double)(eidx - sidx - text_len); 112 + /* fprintf(stderr, "distance %s %f\n", it->text, it->distance); */ 113 + appenditem(it, &matches, &matchend); 114 + number_of_matches++; 115 + } 116 + } else { 117 + appenditem(it, &matches, &matchend); 118 + } 119 + } 120 + 121 + if (number_of_matches) { 122 + /* initialize array with matches */ 123 + if (!(fuzzymatches = realloc(fuzzymatches, number_of_matches * sizeof(struct item*)))) 124 + die("cannot realloc %u bytes:", number_of_matches * sizeof(struct item*)); 125 + for (i = 0, it = matches; it && i < number_of_matches; i++, it = it->right) { 126 + fuzzymatches[i] = it; 127 + } 128 + /* sort matches according to distance */ 129 + qsort(fuzzymatches, number_of_matches, sizeof(struct item*), compare_distance); 130 + /* rebuild list of matches */ 131 + matches = matchend = NULL; 132 + for (i = 0, it = fuzzymatches[i]; i < number_of_matches && it && \ 133 + it->text; i++, it = fuzzymatches[i]) { 134 + appenditem(it, &matches, &matchend); 135 + } 136 + free(fuzzymatches); 137 + } 138 + curr = sel = matches; 139 + calcoffsets(); 140 +} 141 + 142 static void 143 match(void) 144 { 145 + if (fuzzy) { 146 + fuzzymatch(); 147 + return; 148 + } 149 static char **tokv = NULL; 150 static int tokn = 0; 151 152 @@ -702,6 +789,8 @@ main(int argc, char *argv[]) 153 topbar = 0; 154 else if (!strcmp(argv[i], "-f")) /* grabs keyboard before reading stdin */ 155 fast = 1; 156 + else if (!strcmp(argv[i], "-F")) /* grabs keyboard before reading stdin */ 157 + fuzzy = 0; 158 else if (!strcmp(argv[i], "-i")) { /* case-insensitive item matching */ 159 fstrncmp = strncasecmp; 160 fstrstr = cistrstr; 161 -- 162 2.22.0 163
