dmenu-fuzzymatch-5.3.diff (5690B)
1 From d166c2c90f777f5a80f628d493cdcf7bf03034b8 Mon Sep 17 00:00:00 2001 2 From: Justinas Grigas <dev@jstnas.com> 3 Date: Mon, 17 Jun 2024 02:52:15 +0100 4 Subject: [PATCH] fuzzymatch: Add support for fuzzy-matching 5 6 This version of the patch updates the manpage. 7 --- 8 config.def.h | 1 + 9 config.mk | 2 +- 10 dmenu.1 | 5 ++- 11 dmenu.c | 90 +++++++++++++++++++++++++++++++++++++++++++++++++++- 12 4 files changed, 95 insertions(+), 3 deletions(-) 13 14 diff --git a/config.def.h b/config.def.h 15 index 1edb647..a4e6174 100644 16 --- a/config.def.h 17 +++ b/config.def.h 18 @@ -2,6 +2,7 @@ 19 /* Default settings; can be overriden by command line. */ 20 21 static int topbar = 1; /* -b option; if 0, dmenu appears at bottom */ 22 +static int fuzzy = 1; /* -F option; if 0, dmenu doesn't use fuzzy matching */ 23 /* -fn option overrides fonts[0]; default X11 font or font set */ 24 static const char *fonts[] = { 25 "monospace:size=10" 26 diff --git a/config.mk b/config.mk 27 index 137f7c8..6a19175 100644 28 --- a/config.mk 29 +++ b/config.mk 30 @@ -21,7 +21,7 @@ FREETYPEINC = /usr/include/freetype2 31 32 # includes and libs 33 INCS = -I$(X11INC) -I$(FREETYPEINC) 34 -LIBS = -L$(X11LIB) -lX11 $(XINERAMALIBS) $(FREETYPELIBS) 35 +LIBS = -L$(X11LIB) -lX11 $(XINERAMALIBS) $(FREETYPELIBS) -lm 36 37 # flags 38 CPPFLAGS = -D_DEFAULT_SOURCE -D_BSD_SOURCE -D_XOPEN_SOURCE=700 -D_POSIX_C_SOURCE=200809L -DVERSION=\"$(VERSION)\" $(XINERAMAFLAGS) 39 diff --git a/dmenu.1 b/dmenu.1 40 index 323f93c..e2c5ef4 100644 41 --- a/dmenu.1 42 +++ b/dmenu.1 43 @@ -3,7 +3,7 @@ 44 dmenu \- dynamic menu 45 .SH SYNOPSIS 46 .B dmenu 47 -.RB [ \-bfiv ] 48 +.RB [ \-bFfiv ] 49 .RB [ \-l 50 .IR lines ] 51 .RB [ \-m 52 @@ -40,6 +40,9 @@ which lists programs in the user's $PATH and runs the result in their $SHELL. 53 .B \-b 54 dmenu appears at the bottom of the screen. 55 .TP 56 +.B \-F 57 +disables fuzzy matching. 58 +.TP 59 .B \-f 60 dmenu grabs the keyboard before reading stdin if not reading from a tty. This 61 is faster, but will lock up X until stdin reaches end\-of\-file. 62 diff --git a/dmenu.c b/dmenu.c 63 index 40f93e0..03e1f45 100644 64 --- a/dmenu.c 65 +++ b/dmenu.c 66 @@ -1,6 +1,7 @@ 67 /* See LICENSE file for copyright and license details. */ 68 #include <ctype.h> 69 #include <locale.h> 70 +#include <math.h> 71 #include <stdio.h> 72 #include <stdlib.h> 73 #include <string.h> 74 @@ -31,6 +32,7 @@ struct item { 75 char *text; 76 struct item *left, *right; 77 int out; 78 + double distance; 79 }; 80 81 static char text[BUFSIZ] = ""; 82 @@ -226,9 +228,93 @@ grabkeyboard(void) 83 die("cannot grab keyboard"); 84 } 85 86 +int 87 +compare_distance(const void *a, const void *b) 88 +{ 89 + struct item *da = *(struct item **) a; 90 + struct item *db = *(struct item **) b; 91 + 92 + if (!db) 93 + return 1; 94 + if (!da) 95 + return -1; 96 + 97 + return da->distance == db->distance ? 0 : da->distance < db->distance ? -1 : 1; 98 +} 99 + 100 +void 101 +fuzzymatch(void) 102 +{ 103 + /* bang - we have so much memory */ 104 + struct item *it; 105 + struct item **fuzzymatches = NULL; 106 + char c; 107 + int number_of_matches = 0, i, pidx, sidx, eidx; 108 + int text_len = strlen(text), itext_len; 109 + 110 + matches = matchend = NULL; 111 + 112 + /* walk through all items */ 113 + for (it = items; it && it->text; ++it) { 114 + if (text_len) { 115 + itext_len = strlen(it->text); 116 + pidx = 0; /* pointer */ 117 + sidx = eidx = -1; /* start of match, end of match */ 118 + /* walk through item text */ 119 + for (i = 0; i < itext_len && (c = it->text[i]); ++i) { 120 + /* fuzzy match pattern */ 121 + if (!fstrncmp(&text[pidx], &c, 1)) { 122 + if(sidx == -1) 123 + sidx = i; 124 + ++pidx; 125 + if (pidx == text_len) { 126 + eidx = i; 127 + break; 128 + } 129 + } 130 + } 131 + /* build list of matches */ 132 + if (eidx != -1) { 133 + /* compute distance */ 134 + /* add penalty if match starts late (log(sidx+2)) 135 + * add penalty for long a match without many matching characters */ 136 + it->distance = log(sidx + 2) + (double)(eidx - sidx - text_len); 137 + /* fprintf(stderr, "distance %s %f\n", it->text, it->distance); */ 138 + appenditem(it, &matches, &matchend); 139 + ++number_of_matches; 140 + } 141 + } else { 142 + appenditem(it, &matches, &matchend); 143 + } 144 + } 145 + 146 + if (number_of_matches) { 147 + /* initialize array with matches */ 148 + if (!(fuzzymatches = realloc(fuzzymatches, 149 + number_of_matches * sizeof(struct item *)))) 150 + die("cannot realloc %u bytes:", number_of_matches * sizeof(struct item *)); 151 + for (i = 0, it = matches; it && i < number_of_matches; ++i, it = it->right) 152 + fuzzymatches[i] = it; 153 + /* sort matches according to distance */ 154 + qsort(fuzzymatches, number_of_matches, sizeof(struct item*), compare_distance); 155 + /* rebuild list of matches */ 156 + matches = matchend = NULL; 157 + for (i = 0, it = fuzzymatches[i]; i < number_of_matches && it && 158 + it->text; ++i, it = fuzzymatches[i]) 159 + appenditem(it, &matches, &matchend); 160 + free(fuzzymatches); 161 + } 162 + curr = sel = matches; 163 + calcoffsets(); 164 +} 165 + 166 static void 167 match(void) 168 { 169 + if (fuzzy) { 170 + fuzzymatch(); 171 + return; 172 + } 173 static char **tokv = NULL; 174 static int tokn = 0; 175 176 @@ -715,7 +801,7 @@ setup(void) 177 static void 178 usage(void) 179 { 180 - die("usage: dmenu [-bfiv] [-l lines] [-p prompt] [-fn font] [-m monitor]\n" 181 + die("usage: dmenu [-bFfiv] [-l lines] [-p prompt] [-fn font] [-m monitor]\n" 182 " [-nb color] [-nf color] [-sb color] [-sf color] [-w windowid]"); 183 } 184 185 @@ -732,6 +818,8 @@ main(int argc, char *argv[]) 186 exit(0); 187 } else if (!strcmp(argv[i], "-b")) /* appears at the bottom of the screen */ 188 topbar = 0; 189 + else if (!strcmp(argv[i], "-F")) /* disables fuzzy matching */ 190 + fuzzy = 0; 191 else if (!strcmp(argv[i], "-f")) /* grabs keyboard before reading stdin */ 192 fast = 1; 193 else if (!strcmp(argv[i], "-i")) { /* case-insensitive item matching */ 194 -- 195 2.45.2 196