dmenu-typo-5.4.diff (25547B)
1 From 5943f87581e5dff643d335adaab6c716aac3fb86 Mon Sep 17 00:00:00 2001 2 From: Maxim Butov <mbutov@gmail.com> 3 Date: Fri, 13 Nov 2026 15:00:00 +0000 4 Subject: [PATCH] typo: typo-tolerant matching 5 MIME-Version: 1.0 6 Content-Type: text/plain; charset=UTF-8 7 Content-Transfer-Encoding: 8bit 8 9 Every word of the input also matches ignoring diacritics, so "cafe" finds 10 "café" and "елка" finds "ёлка"; case follows -i as usual. When the input 11 is a single word, items that contain it with up to 1 or 2 errors 12 (restricted Damerau-Levenshtein distance: an inserted, deleted or 13 substituted character, or two adjacent characters swapped) are listed 14 after the other matches, fewest errors first: "frefox" finds "firefox". 15 16 1 error is allowed from 5 input characters, 2 from 8: typo_min_len_1 and 17 typo_min_len_2 in config.h. Matching is UTF-8 aware. 18 19 Upstream: https://github.com/mbutov/menu-typo 20 --- 21 config.def.h | 11 ++ 22 dmenu.1 | 8 ++ 23 dmenu.c | 59 +++++++- 24 typo.h | 394 +++++++++++++++++++++++++++++++++++++++++++++++++++ 25 4 files changed, 470 insertions(+), 2 deletions(-) 26 create mode 100644 typo.h 27 28 diff --git a/config.def.h b/config.def.h 29 index 1edb647..0e1f3aa 100644 30 --- a/config.def.h 31 +++ b/config.def.h 32 @@ -21,3 +21,14 @@ static unsigned int lines = 0; 33 * for example: " /?\"&[]" 34 */ 35 static const char worddelimiters[] = " "; 36 + 37 +/* 38 + * Typo-tolerant matching. Every word of the input also matches ignoring 39 + * diacritics: "cafe" finds "café", "елка" finds "ёлка" (case is ignored 40 + * with -i, as usual). When the input is a single word, items that contain 41 + * it with up to 1 or 2 errors (Damerau-Levenshtein) are listed after the 42 + * exact matches. The input length, in characters, from which 1 and 2 43 + * errors are allowed; 0 disables. 44 + */ 45 +static unsigned int typo_min_len_1 = 5; 46 +static unsigned int typo_min_len_2 = 8; 47 diff --git a/dmenu.1 b/dmenu.1 48 index 323f93c..1b5282c 100644 49 --- a/dmenu.1 50 +++ b/dmenu.1 51 @@ -31,6 +31,14 @@ stdin. When the user selects an item and presses Return, their choice is printe 52 to stdout and dmenu terminates. Entering text will narrow the items to those 53 matching the tokens in the input. 54 .P 55 +Tokens also match ignoring diacritics, so "cafe" matches "caf\('e". 56 +When the input is a single word of at least 5 characters, items that contain 57 +it with one error, or two errors from 8 characters, are listed after the other 58 +matches, fewest errors first. 59 +An error is an inserted, deleted or substituted character, or two adjacent 60 +characters swapped. 61 +These lengths are set in config.h. 62 +.P 63 .B dmenu_run 64 is a script used by 65 .IR dwm (1) 66 diff --git a/dmenu.c b/dmenu.c 67 index fd49549..6d9ed88 100644 68 --- a/dmenu.c 69 +++ b/dmenu.c 70 @@ -53,6 +53,7 @@ static Drw *drw; 71 static Clr *scheme[SchemeLast]; 72 73 #include "config.h" 74 +#include "typo.h" 75 76 static int (*fstrncmp)(const char *, const char *, size_t) = strncmp; 77 static char *(*fstrstr)(const char *, const char *) = strstr; 78 @@ -226,9 +227,45 @@ grabkeyboard(void) 79 die("cannot grab keyboard"); 80 } 81 82 +struct typo_item { 83 + struct item *item; 84 + int errors; 85 + size_t order; 86 +}; 87 + 88 +static struct typo_item *typos; 89 +static size_t ntypos, typocap; 90 + 91 +static int 92 +typo_item_cmp(const void *a, const void *b) 93 +{ 94 + const struct typo_item *x = a, *y = b; 95 + 96 + if (x->errors != y->errors) 97 + return x->errors - y->errors; 98 + return x->order < y->order ? -1 : x->order > y->order; 99 +} 100 + 101 +static void 102 +addtypo(struct item *item, int errors) 103 +{ 104 + if (ntypos == typocap) { 105 + typocap = typocap ? 2 * typocap : 64; 106 + if (!(typos = realloc(typos, typocap * sizeof *typos))) 107 + die("cannot realloc %zu bytes:", 108 + typocap * sizeof *typos); 109 + } 110 + typos[ntypos].item = item; 111 + typos[ntypos].errors = errors; 112 + typos[ntypos].order = ntypos; 113 + ntypos++; 114 +} 115 + 116 static void 117 match(void) 118 { 119 + size_t t; 120 + int maxerr, err; 121 static char **tokv = NULL; 122 static int tokn = 0; 123 124 @@ -246,12 +283,26 @@ match(void) 125 126 matches = lprefix = lsubstr = matchend = prefixend = substrend = NULL; 127 textsize = strlen(text) + 1; 128 + /* case as with or without -i; diacritics are always ignored */ 129 + typo_ignore_case = fstrstr == cistrstr; 130 + /* a single word may also match with typos */ 131 + ntypos = 0; 132 + maxerr = 0; 133 + if (tokc == 1 && typo_min_len_1) 134 + maxerr = typo_max_errors(typo_strlen(tokv[0]), 135 + typo_min_len_1, typo_min_len_2 ? typo_min_len_2 : -1u); 136 for (item = items; item && item->text; item++) { 137 + /* every word, as is or ignoring case and diacritics */ 138 for (i = 0; i < tokc; i++) 139 - if (!fstrstr(item->text, tokv[i])) 140 + if (!fstrstr(item->text, tokv[i]) && 141 + !typo_contains(tokv[i], item->text)) 142 break; 143 - if (i != tokc) /* not all tokens match */ 144 + if (i != tokc) { /* not all tokens match */ 145 + if (maxerr && (err = typo_distance(tokv[0], 146 + item->text, maxerr)) <= maxerr) 147 + addtypo(item, err); 148 continue; 149 + } 150 /* exact matches go first, then prefixes, then substrings */ 151 if (!tokc || !fstrncmp(text, item->text, textsize)) 152 appenditem(item, &matches, &matchend); 153 @@ -276,6 +327,10 @@ match(void) 154 matches = lsubstr; 155 matchend = substrend; 156 } 157 + /* then matches with typos, fewest errors first */ 158 + qsort(typos, ntypos, sizeof *typos, typo_item_cmp); 159 + for (t = 0; t < ntypos; t++) 160 + appenditem(typos[t].item, &matches, &matchend); 161 curr = sel = matches; 162 calcoffsets(); 163 } 164 diff --git a/typo.h b/typo.h 165 new file mode 100644 166 index 0000000..2523154 167 --- /dev/null 168 +++ b/typo.h 169 @@ -0,0 +1,394 @@ 170 +/* 171 + * typo.h - typo-tolerant matching for application menus. 172 + * 173 + * typo_distance() returns the restricted Damerau-Levenshtein distance 174 + * (optimal string alignment) between a pattern and the best-matching 175 + * substring of a text. The start and the end of the substring are free 176 + * (Sellers' algorithm), so "frefox" matches "firefox" with one error and 177 + * "vscod" matches "code-vscode" with none. An error is one inserted, 178 + * deleted or substituted character, or two adjacent characters swapped. 179 + * 180 + * Both strings are UTF-8 and are compared character by character, case 181 + * insensitively unless typo_ignore_case is 0 (towlower(), so case folding 182 + * beyond ASCII needs a UTF-8 LC_CTYPE locale, which dmenu and rofi set up) 183 + * and always ignoring diacritics: a 184 + * letter with marks compares as its base letter (e-diaeresis as e, e-acute 185 + * as e, alpha-tonos as alpha), and combining marks are skipped. Invalid 186 + * bytes compare as themselves. 187 + * 188 + * typo_max_errors() is how many errors to allow for a pattern of a given 189 + * length: with a short pattern, even one error matches almost anything. 190 + * 191 + * Single header, C99, no dependencies. Copyright (c) 2026 Maxim Butov, 192 + * MIT license (see LICENSE). 193 + */ 194 +#ifndef TYPO_H 195 +#define TYPO_H 196 + 197 +#include <stddef.h> 198 +#include <stdint.h> 199 +#include <wctype.h> 200 + 201 +/* Longest pattern, in characters; longer ones never match with errors. */ 202 +#define TYPO_PATTERN_MAX 64 203 + 204 +/* Whether to compare case insensitively (1, default) or not (0). */ 205 +static int typo_ignore_case = 1; 206 + 207 +/* Default pattern lengths from which 1 and 2 errors are allowed. */ 208 +#define TYPO_MIN_LEN_1 5 209 +#define TYPO_MIN_LEN_2 8 210 + 211 +/* BEGIN GENERATED by tools/gen-fold.py, Unicode 16.0.0, do not edit */ 212 +static const uint16_t typo_fold_table[][2] = { 213 + {0x00c0, 0x0041}, {0x00c1, 0x0041}, {0x00c2, 0x0041}, {0x00c3, 0x0041}, 214 + {0x00c4, 0x0041}, {0x00c5, 0x0041}, {0x00c7, 0x0043}, {0x00c8, 0x0045}, 215 + {0x00c9, 0x0045}, {0x00ca, 0x0045}, {0x00cb, 0x0045}, {0x00cc, 0x0049}, 216 + {0x00cd, 0x0049}, {0x00ce, 0x0049}, {0x00cf, 0x0049}, {0x00d1, 0x004e}, 217 + {0x00d2, 0x004f}, {0x00d3, 0x004f}, {0x00d4, 0x004f}, {0x00d5, 0x004f}, 218 + {0x00d6, 0x004f}, {0x00d9, 0x0055}, {0x00da, 0x0055}, {0x00db, 0x0055}, 219 + {0x00dc, 0x0055}, {0x00dd, 0x0059}, {0x00e0, 0x0061}, {0x00e1, 0x0061}, 220 + {0x00e2, 0x0061}, {0x00e3, 0x0061}, {0x00e4, 0x0061}, {0x00e5, 0x0061}, 221 + {0x00e7, 0x0063}, {0x00e8, 0x0065}, {0x00e9, 0x0065}, {0x00ea, 0x0065}, 222 + {0x00eb, 0x0065}, {0x00ec, 0x0069}, {0x00ed, 0x0069}, {0x00ee, 0x0069}, 223 + {0x00ef, 0x0069}, {0x00f1, 0x006e}, {0x00f2, 0x006f}, {0x00f3, 0x006f}, 224 + {0x00f4, 0x006f}, {0x00f5, 0x006f}, {0x00f6, 0x006f}, {0x00f9, 0x0075}, 225 + {0x00fa, 0x0075}, {0x00fb, 0x0075}, {0x00fc, 0x0075}, {0x00fd, 0x0079}, 226 + {0x00ff, 0x0079}, {0x0100, 0x0041}, {0x0101, 0x0061}, {0x0102, 0x0041}, 227 + {0x0103, 0x0061}, {0x0104, 0x0041}, {0x0105, 0x0061}, {0x0106, 0x0043}, 228 + {0x0107, 0x0063}, {0x0108, 0x0043}, {0x0109, 0x0063}, {0x010a, 0x0043}, 229 + {0x010b, 0x0063}, {0x010c, 0x0043}, {0x010d, 0x0063}, {0x010e, 0x0044}, 230 + {0x010f, 0x0064}, {0x0112, 0x0045}, {0x0113, 0x0065}, {0x0114, 0x0045}, 231 + {0x0115, 0x0065}, {0x0116, 0x0045}, {0x0117, 0x0065}, {0x0118, 0x0045}, 232 + {0x0119, 0x0065}, {0x011a, 0x0045}, {0x011b, 0x0065}, {0x011c, 0x0047}, 233 + {0x011d, 0x0067}, {0x011e, 0x0047}, {0x011f, 0x0067}, {0x0120, 0x0047}, 234 + {0x0121, 0x0067}, {0x0122, 0x0047}, {0x0123, 0x0067}, {0x0124, 0x0048}, 235 + {0x0125, 0x0068}, {0x0128, 0x0049}, {0x0129, 0x0069}, {0x012a, 0x0049}, 236 + {0x012b, 0x0069}, {0x012c, 0x0049}, {0x012d, 0x0069}, {0x012e, 0x0049}, 237 + {0x012f, 0x0069}, {0x0130, 0x0049}, {0x0134, 0x004a}, {0x0135, 0x006a}, 238 + {0x0136, 0x004b}, {0x0137, 0x006b}, {0x0139, 0x004c}, {0x013a, 0x006c}, 239 + {0x013b, 0x004c}, {0x013c, 0x006c}, {0x013d, 0x004c}, {0x013e, 0x006c}, 240 + {0x0143, 0x004e}, {0x0144, 0x006e}, {0x0145, 0x004e}, {0x0146, 0x006e}, 241 + {0x0147, 0x004e}, {0x0148, 0x006e}, {0x014c, 0x004f}, {0x014d, 0x006f}, 242 + {0x014e, 0x004f}, {0x014f, 0x006f}, {0x0150, 0x004f}, {0x0151, 0x006f}, 243 + {0x0154, 0x0052}, {0x0155, 0x0072}, {0x0156, 0x0052}, {0x0157, 0x0072}, 244 + {0x0158, 0x0052}, {0x0159, 0x0072}, {0x015a, 0x0053}, {0x015b, 0x0073}, 245 + {0x015c, 0x0053}, {0x015d, 0x0073}, {0x015e, 0x0053}, {0x015f, 0x0073}, 246 + {0x0160, 0x0053}, {0x0161, 0x0073}, {0x0162, 0x0054}, {0x0163, 0x0074}, 247 + {0x0164, 0x0054}, {0x0165, 0x0074}, {0x0168, 0x0055}, {0x0169, 0x0075}, 248 + {0x016a, 0x0055}, {0x016b, 0x0075}, {0x016c, 0x0055}, {0x016d, 0x0075}, 249 + {0x016e, 0x0055}, {0x016f, 0x0075}, {0x0170, 0x0055}, {0x0171, 0x0075}, 250 + {0x0172, 0x0055}, {0x0173, 0x0075}, {0x0174, 0x0057}, {0x0175, 0x0077}, 251 + {0x0176, 0x0059}, {0x0177, 0x0079}, {0x0178, 0x0059}, {0x0179, 0x005a}, 252 + {0x017a, 0x007a}, {0x017b, 0x005a}, {0x017c, 0x007a}, {0x017d, 0x005a}, 253 + {0x017e, 0x007a}, {0x01a0, 0x004f}, {0x01a1, 0x006f}, {0x01af, 0x0055}, 254 + {0x01b0, 0x0075}, {0x01cd, 0x0041}, {0x01ce, 0x0061}, {0x01cf, 0x0049}, 255 + {0x01d0, 0x0069}, {0x01d1, 0x004f}, {0x01d2, 0x006f}, {0x01d3, 0x0055}, 256 + {0x01d4, 0x0075}, {0x01d5, 0x0055}, {0x01d6, 0x0075}, {0x01d7, 0x0055}, 257 + {0x01d8, 0x0075}, {0x01d9, 0x0055}, {0x01da, 0x0075}, {0x01db, 0x0055}, 258 + {0x01dc, 0x0075}, {0x01de, 0x0041}, {0x01df, 0x0061}, {0x01e0, 0x0041}, 259 + {0x01e1, 0x0061}, {0x01e2, 0x00c6}, {0x01e3, 0x00e6}, {0x01e6, 0x0047}, 260 + {0x01e7, 0x0067}, {0x01e8, 0x004b}, {0x01e9, 0x006b}, {0x01ea, 0x004f}, 261 + {0x01eb, 0x006f}, {0x01ec, 0x004f}, {0x01ed, 0x006f}, {0x01ee, 0x01b7}, 262 + {0x01ef, 0x0292}, {0x01f0, 0x006a}, {0x01f4, 0x0047}, {0x01f5, 0x0067}, 263 + {0x01f8, 0x004e}, {0x01f9, 0x006e}, {0x01fa, 0x0041}, {0x01fb, 0x0061}, 264 + {0x01fc, 0x00c6}, {0x01fd, 0x00e6}, {0x01fe, 0x00d8}, {0x01ff, 0x00f8}, 265 + {0x0200, 0x0041}, {0x0201, 0x0061}, {0x0202, 0x0041}, {0x0203, 0x0061}, 266 + {0x0204, 0x0045}, {0x0205, 0x0065}, {0x0206, 0x0045}, {0x0207, 0x0065}, 267 + {0x0208, 0x0049}, {0x0209, 0x0069}, {0x020a, 0x0049}, {0x020b, 0x0069}, 268 + {0x020c, 0x004f}, {0x020d, 0x006f}, {0x020e, 0x004f}, {0x020f, 0x006f}, 269 + {0x0210, 0x0052}, {0x0211, 0x0072}, {0x0212, 0x0052}, {0x0213, 0x0072}, 270 + {0x0214, 0x0055}, {0x0215, 0x0075}, {0x0216, 0x0055}, {0x0217, 0x0075}, 271 + {0x0218, 0x0053}, {0x0219, 0x0073}, {0x021a, 0x0054}, {0x021b, 0x0074}, 272 + {0x021e, 0x0048}, {0x021f, 0x0068}, {0x0226, 0x0041}, {0x0227, 0x0061}, 273 + {0x0228, 0x0045}, {0x0229, 0x0065}, {0x022a, 0x004f}, {0x022b, 0x006f}, 274 + {0x022c, 0x004f}, {0x022d, 0x006f}, {0x022e, 0x004f}, {0x022f, 0x006f}, 275 + {0x0230, 0x004f}, {0x0231, 0x006f}, {0x0232, 0x0059}, {0x0233, 0x0079}, 276 + {0x0374, 0x02b9}, {0x0386, 0x0391}, {0x0388, 0x0395}, {0x0389, 0x0397}, 277 + {0x038a, 0x0399}, {0x038c, 0x039f}, {0x038e, 0x03a5}, {0x038f, 0x03a9}, 278 + {0x0390, 0x03b9}, {0x03aa, 0x0399}, {0x03ab, 0x03a5}, {0x03ac, 0x03b1}, 279 + {0x03ad, 0x03b5}, {0x03ae, 0x03b7}, {0x03af, 0x03b9}, {0x03b0, 0x03c5}, 280 + {0x03ca, 0x03b9}, {0x03cb, 0x03c5}, {0x03cc, 0x03bf}, {0x03cd, 0x03c5}, 281 + {0x03ce, 0x03c9}, {0x03d3, 0x03d2}, {0x03d4, 0x03d2}, {0x0400, 0x0415}, 282 + {0x0401, 0x0415}, {0x0403, 0x0413}, {0x0407, 0x0406}, {0x040c, 0x041a}, 283 + {0x040d, 0x0418}, {0x040e, 0x0423}, {0x0419, 0x0418}, {0x0439, 0x0438}, 284 + {0x0450, 0x0435}, {0x0451, 0x0435}, {0x0453, 0x0433}, {0x0457, 0x0456}, 285 + {0x045c, 0x043a}, {0x045d, 0x0438}, {0x045e, 0x0443}, {0x0476, 0x0474}, 286 + {0x0477, 0x0475}, {0x04c1, 0x0416}, {0x04c2, 0x0436}, {0x04d0, 0x0410}, 287 + {0x04d1, 0x0430}, {0x04d2, 0x0410}, {0x04d3, 0x0430}, {0x04d6, 0x0415}, 288 + {0x04d7, 0x0435}, {0x04da, 0x04d8}, {0x04db, 0x04d9}, {0x04dc, 0x0416}, 289 + {0x04dd, 0x0436}, {0x04de, 0x0417}, {0x04df, 0x0437}, {0x04e2, 0x0418}, 290 + {0x04e3, 0x0438}, {0x04e4, 0x0418}, {0x04e5, 0x0438}, {0x04e6, 0x041e}, 291 + {0x04e7, 0x043e}, {0x04ea, 0x04e8}, {0x04eb, 0x04e9}, {0x04ec, 0x042d}, 292 + {0x04ed, 0x044d}, {0x04ee, 0x0423}, {0x04ef, 0x0443}, {0x04f0, 0x0423}, 293 + {0x04f1, 0x0443}, {0x04f2, 0x0423}, {0x04f3, 0x0443}, {0x04f4, 0x0427}, 294 + {0x04f5, 0x0447}, {0x04f8, 0x042b}, {0x04f9, 0x044b}, {0x1e00, 0x0041}, 295 + {0x1e01, 0x0061}, {0x1e02, 0x0042}, {0x1e03, 0x0062}, {0x1e04, 0x0042}, 296 + {0x1e05, 0x0062}, {0x1e06, 0x0042}, {0x1e07, 0x0062}, {0x1e08, 0x0043}, 297 + {0x1e09, 0x0063}, {0x1e0a, 0x0044}, {0x1e0b, 0x0064}, {0x1e0c, 0x0044}, 298 + {0x1e0d, 0x0064}, {0x1e0e, 0x0044}, {0x1e0f, 0x0064}, {0x1e10, 0x0044}, 299 + {0x1e11, 0x0064}, {0x1e12, 0x0044}, {0x1e13, 0x0064}, {0x1e14, 0x0045}, 300 + {0x1e15, 0x0065}, {0x1e16, 0x0045}, {0x1e17, 0x0065}, {0x1e18, 0x0045}, 301 + {0x1e19, 0x0065}, {0x1e1a, 0x0045}, {0x1e1b, 0x0065}, {0x1e1c, 0x0045}, 302 + {0x1e1d, 0x0065}, {0x1e1e, 0x0046}, {0x1e1f, 0x0066}, {0x1e20, 0x0047}, 303 + {0x1e21, 0x0067}, {0x1e22, 0x0048}, {0x1e23, 0x0068}, {0x1e24, 0x0048}, 304 + {0x1e25, 0x0068}, {0x1e26, 0x0048}, {0x1e27, 0x0068}, {0x1e28, 0x0048}, 305 + {0x1e29, 0x0068}, {0x1e2a, 0x0048}, {0x1e2b, 0x0068}, {0x1e2c, 0x0049}, 306 + {0x1e2d, 0x0069}, {0x1e2e, 0x0049}, {0x1e2f, 0x0069}, {0x1e30, 0x004b}, 307 + {0x1e31, 0x006b}, {0x1e32, 0x004b}, {0x1e33, 0x006b}, {0x1e34, 0x004b}, 308 + {0x1e35, 0x006b}, {0x1e36, 0x004c}, {0x1e37, 0x006c}, {0x1e38, 0x004c}, 309 + {0x1e39, 0x006c}, {0x1e3a, 0x004c}, {0x1e3b, 0x006c}, {0x1e3c, 0x004c}, 310 + {0x1e3d, 0x006c}, {0x1e3e, 0x004d}, {0x1e3f, 0x006d}, {0x1e40, 0x004d}, 311 + {0x1e41, 0x006d}, {0x1e42, 0x004d}, {0x1e43, 0x006d}, {0x1e44, 0x004e}, 312 + {0x1e45, 0x006e}, {0x1e46, 0x004e}, {0x1e47, 0x006e}, {0x1e48, 0x004e}, 313 + {0x1e49, 0x006e}, {0x1e4a, 0x004e}, {0x1e4b, 0x006e}, {0x1e4c, 0x004f}, 314 + {0x1e4d, 0x006f}, {0x1e4e, 0x004f}, {0x1e4f, 0x006f}, {0x1e50, 0x004f}, 315 + {0x1e51, 0x006f}, {0x1e52, 0x004f}, {0x1e53, 0x006f}, {0x1e54, 0x0050}, 316 + {0x1e55, 0x0070}, {0x1e56, 0x0050}, {0x1e57, 0x0070}, {0x1e58, 0x0052}, 317 + {0x1e59, 0x0072}, {0x1e5a, 0x0052}, {0x1e5b, 0x0072}, {0x1e5c, 0x0052}, 318 + {0x1e5d, 0x0072}, {0x1e5e, 0x0052}, {0x1e5f, 0x0072}, {0x1e60, 0x0053}, 319 + {0x1e61, 0x0073}, {0x1e62, 0x0053}, {0x1e63, 0x0073}, {0x1e64, 0x0053}, 320 + {0x1e65, 0x0073}, {0x1e66, 0x0053}, {0x1e67, 0x0073}, {0x1e68, 0x0053}, 321 + {0x1e69, 0x0073}, {0x1e6a, 0x0054}, {0x1e6b, 0x0074}, {0x1e6c, 0x0054}, 322 + {0x1e6d, 0x0074}, {0x1e6e, 0x0054}, {0x1e6f, 0x0074}, {0x1e70, 0x0054}, 323 + {0x1e71, 0x0074}, {0x1e72, 0x0055}, {0x1e73, 0x0075}, {0x1e74, 0x0055}, 324 + {0x1e75, 0x0075}, {0x1e76, 0x0055}, {0x1e77, 0x0075}, {0x1e78, 0x0055}, 325 + {0x1e79, 0x0075}, {0x1e7a, 0x0055}, {0x1e7b, 0x0075}, {0x1e7c, 0x0056}, 326 + {0x1e7d, 0x0076}, {0x1e7e, 0x0056}, {0x1e7f, 0x0076}, {0x1e80, 0x0057}, 327 + {0x1e81, 0x0077}, {0x1e82, 0x0057}, {0x1e83, 0x0077}, {0x1e84, 0x0057}, 328 + {0x1e85, 0x0077}, {0x1e86, 0x0057}, {0x1e87, 0x0077}, {0x1e88, 0x0057}, 329 + {0x1e89, 0x0077}, {0x1e8a, 0x0058}, {0x1e8b, 0x0078}, {0x1e8c, 0x0058}, 330 + {0x1e8d, 0x0078}, {0x1e8e, 0x0059}, {0x1e8f, 0x0079}, {0x1e90, 0x005a}, 331 + {0x1e91, 0x007a}, {0x1e92, 0x005a}, {0x1e93, 0x007a}, {0x1e94, 0x005a}, 332 + {0x1e95, 0x007a}, {0x1e96, 0x0068}, {0x1e97, 0x0074}, {0x1e98, 0x0077}, 333 + {0x1e99, 0x0079}, {0x1e9b, 0x017f}, {0x1ea0, 0x0041}, {0x1ea1, 0x0061}, 334 + {0x1ea2, 0x0041}, {0x1ea3, 0x0061}, {0x1ea4, 0x0041}, {0x1ea5, 0x0061}, 335 + {0x1ea6, 0x0041}, {0x1ea7, 0x0061}, {0x1ea8, 0x0041}, {0x1ea9, 0x0061}, 336 + {0x1eaa, 0x0041}, {0x1eab, 0x0061}, {0x1eac, 0x0041}, {0x1ead, 0x0061}, 337 + {0x1eae, 0x0041}, {0x1eaf, 0x0061}, {0x1eb0, 0x0041}, {0x1eb1, 0x0061}, 338 + {0x1eb2, 0x0041}, {0x1eb3, 0x0061}, {0x1eb4, 0x0041}, {0x1eb5, 0x0061}, 339 + {0x1eb6, 0x0041}, {0x1eb7, 0x0061}, {0x1eb8, 0x0045}, {0x1eb9, 0x0065}, 340 + {0x1eba, 0x0045}, {0x1ebb, 0x0065}, {0x1ebc, 0x0045}, {0x1ebd, 0x0065}, 341 + {0x1ebe, 0x0045}, {0x1ebf, 0x0065}, {0x1ec0, 0x0045}, {0x1ec1, 0x0065}, 342 + {0x1ec2, 0x0045}, {0x1ec3, 0x0065}, {0x1ec4, 0x0045}, {0x1ec5, 0x0065}, 343 + {0x1ec6, 0x0045}, {0x1ec7, 0x0065}, {0x1ec8, 0x0049}, {0x1ec9, 0x0069}, 344 + {0x1eca, 0x0049}, {0x1ecb, 0x0069}, {0x1ecc, 0x004f}, {0x1ecd, 0x006f}, 345 + {0x1ece, 0x004f}, {0x1ecf, 0x006f}, {0x1ed0, 0x004f}, {0x1ed1, 0x006f}, 346 + {0x1ed2, 0x004f}, {0x1ed3, 0x006f}, {0x1ed4, 0x004f}, {0x1ed5, 0x006f}, 347 + {0x1ed6, 0x004f}, {0x1ed7, 0x006f}, {0x1ed8, 0x004f}, {0x1ed9, 0x006f}, 348 + {0x1eda, 0x004f}, {0x1edb, 0x006f}, {0x1edc, 0x004f}, {0x1edd, 0x006f}, 349 + {0x1ede, 0x004f}, {0x1edf, 0x006f}, {0x1ee0, 0x004f}, {0x1ee1, 0x006f}, 350 + {0x1ee2, 0x004f}, {0x1ee3, 0x006f}, {0x1ee4, 0x0055}, {0x1ee5, 0x0075}, 351 + {0x1ee6, 0x0055}, {0x1ee7, 0x0075}, {0x1ee8, 0x0055}, {0x1ee9, 0x0075}, 352 + {0x1eea, 0x0055}, {0x1eeb, 0x0075}, {0x1eec, 0x0055}, {0x1eed, 0x0075}, 353 + {0x1eee, 0x0055}, {0x1eef, 0x0075}, {0x1ef0, 0x0055}, {0x1ef1, 0x0075}, 354 + {0x1ef2, 0x0059}, {0x1ef3, 0x0079}, {0x1ef4, 0x0059}, {0x1ef5, 0x0079}, 355 + {0x1ef6, 0x0059}, {0x1ef7, 0x0079}, {0x1ef8, 0x0059}, {0x1ef9, 0x0079}, 356 + {0x1f00, 0x03b1}, {0x1f01, 0x03b1}, {0x1f02, 0x03b1}, {0x1f03, 0x03b1}, 357 + {0x1f04, 0x03b1}, {0x1f05, 0x03b1}, {0x1f06, 0x03b1}, {0x1f07, 0x03b1}, 358 + {0x1f08, 0x0391}, {0x1f09, 0x0391}, {0x1f0a, 0x0391}, {0x1f0b, 0x0391}, 359 + {0x1f0c, 0x0391}, {0x1f0d, 0x0391}, {0x1f0e, 0x0391}, {0x1f0f, 0x0391}, 360 + {0x1f10, 0x03b5}, {0x1f11, 0x03b5}, {0x1f12, 0x03b5}, {0x1f13, 0x03b5}, 361 + {0x1f14, 0x03b5}, {0x1f15, 0x03b5}, {0x1f18, 0x0395}, {0x1f19, 0x0395}, 362 + {0x1f1a, 0x0395}, {0x1f1b, 0x0395}, {0x1f1c, 0x0395}, {0x1f1d, 0x0395}, 363 + {0x1f20, 0x03b7}, {0x1f21, 0x03b7}, {0x1f22, 0x03b7}, {0x1f23, 0x03b7}, 364 + {0x1f24, 0x03b7}, {0x1f25, 0x03b7}, {0x1f26, 0x03b7}, {0x1f27, 0x03b7}, 365 + {0x1f28, 0x0397}, {0x1f29, 0x0397}, {0x1f2a, 0x0397}, {0x1f2b, 0x0397}, 366 + {0x1f2c, 0x0397}, {0x1f2d, 0x0397}, {0x1f2e, 0x0397}, {0x1f2f, 0x0397}, 367 + {0x1f30, 0x03b9}, {0x1f31, 0x03b9}, {0x1f32, 0x03b9}, {0x1f33, 0x03b9}, 368 + {0x1f34, 0x03b9}, {0x1f35, 0x03b9}, {0x1f36, 0x03b9}, {0x1f37, 0x03b9}, 369 + {0x1f38, 0x0399}, {0x1f39, 0x0399}, {0x1f3a, 0x0399}, {0x1f3b, 0x0399}, 370 + {0x1f3c, 0x0399}, {0x1f3d, 0x0399}, {0x1f3e, 0x0399}, {0x1f3f, 0x0399}, 371 + {0x1f40, 0x03bf}, {0x1f41, 0x03bf}, {0x1f42, 0x03bf}, {0x1f43, 0x03bf}, 372 + {0x1f44, 0x03bf}, {0x1f45, 0x03bf}, {0x1f48, 0x039f}, {0x1f49, 0x039f}, 373 + {0x1f4a, 0x039f}, {0x1f4b, 0x039f}, {0x1f4c, 0x039f}, {0x1f4d, 0x039f}, 374 + {0x1f50, 0x03c5}, {0x1f51, 0x03c5}, {0x1f52, 0x03c5}, {0x1f53, 0x03c5}, 375 + {0x1f54, 0x03c5}, {0x1f55, 0x03c5}, {0x1f56, 0x03c5}, {0x1f57, 0x03c5}, 376 + {0x1f59, 0x03a5}, {0x1f5b, 0x03a5}, {0x1f5d, 0x03a5}, {0x1f5f, 0x03a5}, 377 + {0x1f60, 0x03c9}, {0x1f61, 0x03c9}, {0x1f62, 0x03c9}, {0x1f63, 0x03c9}, 378 + {0x1f64, 0x03c9}, {0x1f65, 0x03c9}, {0x1f66, 0x03c9}, {0x1f67, 0x03c9}, 379 + {0x1f68, 0x03a9}, {0x1f69, 0x03a9}, {0x1f6a, 0x03a9}, {0x1f6b, 0x03a9}, 380 + {0x1f6c, 0x03a9}, {0x1f6d, 0x03a9}, {0x1f6e, 0x03a9}, {0x1f6f, 0x03a9}, 381 + {0x1f70, 0x03b1}, {0x1f71, 0x03b1}, {0x1f72, 0x03b5}, {0x1f73, 0x03b5}, 382 + {0x1f74, 0x03b7}, {0x1f75, 0x03b7}, {0x1f76, 0x03b9}, {0x1f77, 0x03b9}, 383 + {0x1f78, 0x03bf}, {0x1f79, 0x03bf}, {0x1f7a, 0x03c5}, {0x1f7b, 0x03c5}, 384 + {0x1f7c, 0x03c9}, {0x1f7d, 0x03c9}, {0x1f80, 0x03b1}, {0x1f81, 0x03b1}, 385 + {0x1f82, 0x03b1}, {0x1f83, 0x03b1}, {0x1f84, 0x03b1}, {0x1f85, 0x03b1}, 386 + {0x1f86, 0x03b1}, {0x1f87, 0x03b1}, {0x1f88, 0x0391}, {0x1f89, 0x0391}, 387 + {0x1f8a, 0x0391}, {0x1f8b, 0x0391}, {0x1f8c, 0x0391}, {0x1f8d, 0x0391}, 388 + {0x1f8e, 0x0391}, {0x1f8f, 0x0391}, {0x1f90, 0x03b7}, {0x1f91, 0x03b7}, 389 + {0x1f92, 0x03b7}, {0x1f93, 0x03b7}, {0x1f94, 0x03b7}, {0x1f95, 0x03b7}, 390 + {0x1f96, 0x03b7}, {0x1f97, 0x03b7}, {0x1f98, 0x0397}, {0x1f99, 0x0397}, 391 + {0x1f9a, 0x0397}, {0x1f9b, 0x0397}, {0x1f9c, 0x0397}, {0x1f9d, 0x0397}, 392 + {0x1f9e, 0x0397}, {0x1f9f, 0x0397}, {0x1fa0, 0x03c9}, {0x1fa1, 0x03c9}, 393 + {0x1fa2, 0x03c9}, {0x1fa3, 0x03c9}, {0x1fa4, 0x03c9}, {0x1fa5, 0x03c9}, 394 + {0x1fa6, 0x03c9}, {0x1fa7, 0x03c9}, {0x1fa8, 0x03a9}, {0x1fa9, 0x03a9}, 395 + {0x1faa, 0x03a9}, {0x1fab, 0x03a9}, {0x1fac, 0x03a9}, {0x1fad, 0x03a9}, 396 + {0x1fae, 0x03a9}, {0x1faf, 0x03a9}, {0x1fb0, 0x03b1}, {0x1fb1, 0x03b1}, 397 + {0x1fb2, 0x03b1}, {0x1fb3, 0x03b1}, {0x1fb4, 0x03b1}, {0x1fb6, 0x03b1}, 398 + {0x1fb7, 0x03b1}, {0x1fb8, 0x0391}, {0x1fb9, 0x0391}, {0x1fba, 0x0391}, 399 + {0x1fbb, 0x0391}, {0x1fbc, 0x0391}, {0x1fbe, 0x03b9}, {0x1fc2, 0x03b7}, 400 + {0x1fc3, 0x03b7}, {0x1fc4, 0x03b7}, {0x1fc6, 0x03b7}, {0x1fc7, 0x03b7}, 401 + {0x1fc8, 0x0395}, {0x1fc9, 0x0395}, {0x1fca, 0x0397}, {0x1fcb, 0x0397}, 402 + {0x1fcc, 0x0397}, {0x1fd0, 0x03b9}, {0x1fd1, 0x03b9}, {0x1fd2, 0x03b9}, 403 + {0x1fd3, 0x03b9}, {0x1fd6, 0x03b9}, {0x1fd7, 0x03b9}, {0x1fd8, 0x0399}, 404 + {0x1fd9, 0x0399}, {0x1fda, 0x0399}, {0x1fdb, 0x0399}, {0x1fe0, 0x03c5}, 405 + {0x1fe1, 0x03c5}, {0x1fe2, 0x03c5}, {0x1fe3, 0x03c5}, {0x1fe4, 0x03c1}, 406 + {0x1fe5, 0x03c1}, {0x1fe6, 0x03c5}, {0x1fe7, 0x03c5}, {0x1fe8, 0x03a5}, 407 + {0x1fe9, 0x03a5}, {0x1fea, 0x03a5}, {0x1feb, 0x03a5}, {0x1fec, 0x03a1}, 408 + {0x1ff2, 0x03c9}, {0x1ff3, 0x03c9}, {0x1ff4, 0x03c9}, {0x1ff6, 0x03c9}, 409 + {0x1ff7, 0x03c9}, {0x1ff8, 0x039f}, {0x1ff9, 0x039f}, {0x1ffa, 0x03a9}, 410 + {0x1ffb, 0x03a9}, {0x1ffc, 0x03a9}, 411 +}; 412 +/* END GENERATED */ 413 + 414 +/* Base letter of a letter with diacritics, or c itself. */ 415 +static inline uint32_t 416 +typo_fold(uint32_t c) 417 +{ 418 + size_t lo = 0, hi = sizeof typo_fold_table / sizeof typo_fold_table[0]; 419 + 420 + if (c < 0xc0 || c > 0xffff) 421 + return c; 422 + while (lo < hi) { 423 + size_t mid = (lo + hi) / 2; 424 + 425 + if (typo_fold_table[mid][0] == c) 426 + return typo_fold_table[mid][1]; 427 + if (typo_fold_table[mid][0] < c) 428 + lo = mid + 1; 429 + else 430 + hi = mid; 431 + } 432 + return c; 433 +} 434 + 435 +/* Combining marks, which are skipped. */ 436 +static inline int 437 +typo_is_mark(uint32_t c) 438 +{ 439 + return (c >= 0x0300 && c <= 0x036f) || (c >= 0x1ab0 && c <= 0x1aff) || 440 + (c >= 0x1dc0 && c <= 0x1dff) || (c >= 0x20d0 && c <= 0x20ff) || 441 + (c >= 0xfe20 && c <= 0xfe2f); 442 +} 443 + 444 +/* Decodes one UTF-8 character at *s and advances *s. */ 445 +static inline uint32_t 446 +typo_decode(const char **s) 447 +{ 448 + const unsigned char *p = (const unsigned char *)*s; 449 + uint32_t c = p[0]; 450 + int n = 0, i; 451 + 452 + if (c >= 0xf0 && c < 0xf8) 453 + n = 3, c &= 0x07; 454 + else if (c >= 0xe0) 455 + n = 2, c &= 0x0f; 456 + else if (c >= 0xc0) 457 + n = 1, c &= 0x1f; 458 + for (i = 1; i <= n; i++) { 459 + /* broken sequence: take the first byte as it is */ 460 + if ((p[i] & 0xc0) != 0x80) { 461 + c = p[0]; 462 + n = 0; 463 + break; 464 + } 465 + c = (c << 6) | (p[i] & 0x3f); 466 + } 467 + *s += n + 1; 468 + return c; 469 +} 470 + 471 +/* 472 + * Next character to compare at *s: without diacritics, lowercased if 473 + * typo_ignore_case; combining marks are skipped. Returns 0 at the end. 474 + */ 475 +static inline uint32_t 476 +typo_next_char(const char **s) 477 +{ 478 + uint32_t c; 479 + 480 + do { 481 + if (!**s) 482 + return 0; 483 + c = typo_decode(s); 484 + } while (typo_is_mark(c)); 485 + c = typo_fold(c); 486 + return typo_ignore_case ? (uint32_t)towlower((wint_t)c) : c; 487 +} 488 + 489 +/* Number of characters in a UTF-8 string. */ 490 +static inline size_t 491 +typo_strlen(const char *s) 492 +{ 493 + size_t n = 0; 494 + 495 + while (typo_next_char(&s)) 496 + n++; 497 + return n; 498 +} 499 + 500 +/* Errors allowed for a pattern of len characters (0: exact matches only). */ 501 +static inline int 502 +typo_max_errors(size_t len, unsigned int min_len_1, unsigned int min_len_2) 503 +{ 504 + return len >= min_len_2 ? 2 : len >= min_len_1 ? 1 : 0; 505 +} 506 + 507 +/* 508 + * Distance from pattern to the closest substring of text; if it is greater 509 + * than max, returns max + 1. 510 + */ 511 +static inline int 512 +typo_distance(const char *pattern, const char *text, int max) 513 +{ 514 + uint32_t pat[TYPO_PATTERN_MAX]; 515 + int prev2[TYPO_PATTERN_MAX + 1], prev[TYPO_PATTERN_MAX + 1]; 516 + int cur[TYPO_PATTERN_MAX + 1]; 517 + int m = 0, i, j, best, v; 518 + uint32_t tc, tprev = 0; 519 + 520 + while ((tc = typo_next_char(&pattern))) { 521 + if (m == TYPO_PATTERN_MAX) 522 + return max + 1; 523 + pat[m++] = tc; 524 + } 525 + if (m == 0) 526 + return 0; 527 + for (i = 0; i <= m; i++) 528 + prev[i] = prev2[i] = i; 529 + best = m; 530 + for (j = 0; (tc = typo_next_char(&text)); j++) { 531 + cur[0] = 0; /* the substring may start anywhere */ 532 + for (i = 1; i <= m; i++) { 533 + /* substitute, skip in text, skip in pattern */ 534 + v = prev[i - 1] + (pat[i - 1] != tc); 535 + if (prev[i] + 1 < v) 536 + v = prev[i] + 1; 537 + if (cur[i - 1] + 1 < v) 538 + v = cur[i - 1] + 1; 539 + /* swap of two adjacent characters */ 540 + if (i > 1 && j > 0 && pat[i - 1] == tprev && 541 + pat[i - 2] == tc && prev2[i - 2] + 1 < v) 542 + v = prev2[i - 2] + 1; 543 + cur[i] = v; 544 + } 545 + if (cur[m] < best) 546 + best = cur[m]; /* ... and end anywhere */ 547 + for (i = 0; i <= m; i++) { 548 + prev2[i] = prev[i]; 549 + prev[i] = cur[i]; 550 + } 551 + tprev = tc; 552 + } 553 + return best > max ? max + 1 : best; 554 +} 555 + 556 +/* Whether text contains pattern, ignoring diacritics (and case), no errors. */ 557 +static inline int 558 +typo_contains(const char *pattern, const char *text) 559 +{ 560 + return typo_distance(pattern, text, 0) == 0; 561 +} 562 + 563 +#endif /* TYPO_H */