commit 0ac2d7b301f617b8c5ee26021e8d4566254f2a1c
parent 6bbdf4c79c38605575217f702c230be80a96046d
Author: Maxim Butov <mbutov@gmail.com>
Date: Fri, 13 Nov 2026 15:30:54 +0300
[dmenu][patches][typo] Add typo-tolerant matching
New patch for dmenu 5.4: every word of the input also matches ignoring
diacritics, and a single-word input also finds items containing it with
up to 1 or 2 errors (restricted Damerau-Levenshtein distance), listed
after the usual matches.
Diffstat:
2 files changed, 598 insertions(+), 0 deletions(-)
diff --git a/tools.suckless.org/dmenu/patches/typo/dmenu-typo-5.4.diff b/tools.suckless.org/dmenu/patches/typo/dmenu-typo-5.4.diff
@@ -0,0 +1,563 @@
+From 5943f87581e5dff643d335adaab6c716aac3fb86 Mon Sep 17 00:00:00 2001
+From: Maxim Butov <mbutov@gmail.com>
+Date: Fri, 13 Nov 2026 15:00:00 +0000
+Subject: [PATCH] typo: typo-tolerant matching
+MIME-Version: 1.0
+Content-Type: text/plain; charset=UTF-8
+Content-Transfer-Encoding: 8bit
+
+Every word of the input also matches ignoring diacritics, so "cafe" finds
+"café" and "елка" finds "ёлка"; case follows -i as usual. When the input
+is a single word, items that contain it with up to 1 or 2 errors
+(restricted Damerau-Levenshtein distance: an inserted, deleted or
+substituted character, or two adjacent characters swapped) are listed
+after the other matches, fewest errors first: "frefox" finds "firefox".
+
+1 error is allowed from 5 input characters, 2 from 8: typo_min_len_1 and
+typo_min_len_2 in config.h. Matching is UTF-8 aware.
+
+Upstream: https://github.com/mbutov/menu-typo
+---
+ config.def.h | 11 ++
+ dmenu.1 | 8 ++
+ dmenu.c | 59 +++++++-
+ typo.h | 394 +++++++++++++++++++++++++++++++++++++++++++++++++++
+ 4 files changed, 470 insertions(+), 2 deletions(-)
+ create mode 100644 typo.h
+
+diff --git a/config.def.h b/config.def.h
+index 1edb647..0e1f3aa 100644
+--- a/config.def.h
++++ b/config.def.h
+@@ -21,3 +21,14 @@ static unsigned int lines = 0;
+ * for example: " /?\"&[]"
+ */
+ static const char worddelimiters[] = " ";
++
++/*
++ * Typo-tolerant matching. Every word of the input also matches ignoring
++ * diacritics: "cafe" finds "café", "елка" finds "ёлка" (case is ignored
++ * with -i, as usual). When the input is a single word, items that contain
++ * it with up to 1 or 2 errors (Damerau-Levenshtein) are listed after the
++ * exact matches. The input length, in characters, from which 1 and 2
++ * errors are allowed; 0 disables.
++ */
++static unsigned int typo_min_len_1 = 5;
++static unsigned int typo_min_len_2 = 8;
+diff --git a/dmenu.1 b/dmenu.1
+index 323f93c..1b5282c 100644
+--- a/dmenu.1
++++ b/dmenu.1
+@@ -31,6 +31,14 @@ stdin. When the user selects an item and presses Return, their choice is printe
+ to stdout and dmenu terminates. Entering text will narrow the items to those
+ matching the tokens in the input.
+ .P
++Tokens also match ignoring diacritics, so "cafe" matches "caf\('e".
++When the input is a single word of at least 5 characters, items that contain
++it with one error, or two errors from 8 characters, are listed after the other
++matches, fewest errors first.
++An error is an inserted, deleted or substituted character, or two adjacent
++characters swapped.
++These lengths are set in config.h.
++.P
+ .B dmenu_run
+ is a script used by
+ .IR dwm (1)
+diff --git a/dmenu.c b/dmenu.c
+index fd49549..6d9ed88 100644
+--- a/dmenu.c
++++ b/dmenu.c
+@@ -53,6 +53,7 @@ static Drw *drw;
+ static Clr *scheme[SchemeLast];
+
+ #include "config.h"
++#include "typo.h"
+
+ static int (*fstrncmp)(const char *, const char *, size_t) = strncmp;
+ static char *(*fstrstr)(const char *, const char *) = strstr;
+@@ -226,9 +227,45 @@ grabkeyboard(void)
+ die("cannot grab keyboard");
+ }
+
++struct typo_item {
++ struct item *item;
++ int errors;
++ size_t order;
++};
++
++static struct typo_item *typos;
++static size_t ntypos, typocap;
++
++static int
++typo_item_cmp(const void *a, const void *b)
++{
++ const struct typo_item *x = a, *y = b;
++
++ if (x->errors != y->errors)
++ return x->errors - y->errors;
++ return x->order < y->order ? -1 : x->order > y->order;
++}
++
++static void
++addtypo(struct item *item, int errors)
++{
++ if (ntypos == typocap) {
++ typocap = typocap ? 2 * typocap : 64;
++ if (!(typos = realloc(typos, typocap * sizeof *typos)))
++ die("cannot realloc %zu bytes:",
++ typocap * sizeof *typos);
++ }
++ typos[ntypos].item = item;
++ typos[ntypos].errors = errors;
++ typos[ntypos].order = ntypos;
++ ntypos++;
++}
++
+ static void
+ match(void)
+ {
++ size_t t;
++ int maxerr, err;
+ static char **tokv = NULL;
+ static int tokn = 0;
+
+@@ -246,12 +283,26 @@ match(void)
+
+ matches = lprefix = lsubstr = matchend = prefixend = substrend = NULL;
+ textsize = strlen(text) + 1;
++ /* case as with or without -i; diacritics are always ignored */
++ typo_ignore_case = fstrstr == cistrstr;
++ /* a single word may also match with typos */
++ ntypos = 0;
++ maxerr = 0;
++ if (tokc == 1 && typo_min_len_1)
++ maxerr = typo_max_errors(typo_strlen(tokv[0]),
++ typo_min_len_1, typo_min_len_2 ? typo_min_len_2 : -1u);
+ for (item = items; item && item->text; item++) {
++ /* every word, as is or ignoring case and diacritics */
+ for (i = 0; i < tokc; i++)
+- if (!fstrstr(item->text, tokv[i]))
++ if (!fstrstr(item->text, tokv[i]) &&
++ !typo_contains(tokv[i], item->text))
+ break;
+- if (i != tokc) /* not all tokens match */
++ if (i != tokc) { /* not all tokens match */
++ if (maxerr && (err = typo_distance(tokv[0],
++ item->text, maxerr)) <= maxerr)
++ addtypo(item, err);
+ continue;
++ }
+ /* exact matches go first, then prefixes, then substrings */
+ if (!tokc || !fstrncmp(text, item->text, textsize))
+ appenditem(item, &matches, &matchend);
+@@ -276,6 +327,10 @@ match(void)
+ matches = lsubstr;
+ matchend = substrend;
+ }
++ /* then matches with typos, fewest errors first */
++ qsort(typos, ntypos, sizeof *typos, typo_item_cmp);
++ for (t = 0; t < ntypos; t++)
++ appenditem(typos[t].item, &matches, &matchend);
+ curr = sel = matches;
+ calcoffsets();
+ }
+diff --git a/typo.h b/typo.h
+new file mode 100644
+index 0000000..2523154
+--- /dev/null
++++ b/typo.h
+@@ -0,0 +1,394 @@
++/*
++ * typo.h - typo-tolerant matching for application menus.
++ *
++ * typo_distance() returns the restricted Damerau-Levenshtein distance
++ * (optimal string alignment) between a pattern and the best-matching
++ * substring of a text. The start and the end of the substring are free
++ * (Sellers' algorithm), so "frefox" matches "firefox" with one error and
++ * "vscod" matches "code-vscode" with none. An error is one inserted,
++ * deleted or substituted character, or two adjacent characters swapped.
++ *
++ * Both strings are UTF-8 and are compared character by character, case
++ * insensitively unless typo_ignore_case is 0 (towlower(), so case folding
++ * beyond ASCII needs a UTF-8 LC_CTYPE locale, which dmenu and rofi set up)
++ * and always ignoring diacritics: a
++ * letter with marks compares as its base letter (e-diaeresis as e, e-acute
++ * as e, alpha-tonos as alpha), and combining marks are skipped. Invalid
++ * bytes compare as themselves.
++ *
++ * typo_max_errors() is how many errors to allow for a pattern of a given
++ * length: with a short pattern, even one error matches almost anything.
++ *
++ * Single header, C99, no dependencies. Copyright (c) 2026 Maxim Butov,
++ * MIT license (see LICENSE).
++ */
++#ifndef TYPO_H
++#define TYPO_H
++
++#include <stddef.h>
++#include <stdint.h>
++#include <wctype.h>
++
++/* Longest pattern, in characters; longer ones never match with errors. */
++#define TYPO_PATTERN_MAX 64
++
++/* Whether to compare case insensitively (1, default) or not (0). */
++static int typo_ignore_case = 1;
++
++/* Default pattern lengths from which 1 and 2 errors are allowed. */
++#define TYPO_MIN_LEN_1 5
++#define TYPO_MIN_LEN_2 8
++
++/* BEGIN GENERATED by tools/gen-fold.py, Unicode 16.0.0, do not edit */
++static const uint16_t typo_fold_table[][2] = {
++ {0x00c0, 0x0041}, {0x00c1, 0x0041}, {0x00c2, 0x0041}, {0x00c3, 0x0041},
++ {0x00c4, 0x0041}, {0x00c5, 0x0041}, {0x00c7, 0x0043}, {0x00c8, 0x0045},
++ {0x00c9, 0x0045}, {0x00ca, 0x0045}, {0x00cb, 0x0045}, {0x00cc, 0x0049},
++ {0x00cd, 0x0049}, {0x00ce, 0x0049}, {0x00cf, 0x0049}, {0x00d1, 0x004e},
++ {0x00d2, 0x004f}, {0x00d3, 0x004f}, {0x00d4, 0x004f}, {0x00d5, 0x004f},
++ {0x00d6, 0x004f}, {0x00d9, 0x0055}, {0x00da, 0x0055}, {0x00db, 0x0055},
++ {0x00dc, 0x0055}, {0x00dd, 0x0059}, {0x00e0, 0x0061}, {0x00e1, 0x0061},
++ {0x00e2, 0x0061}, {0x00e3, 0x0061}, {0x00e4, 0x0061}, {0x00e5, 0x0061},
++ {0x00e7, 0x0063}, {0x00e8, 0x0065}, {0x00e9, 0x0065}, {0x00ea, 0x0065},
++ {0x00eb, 0x0065}, {0x00ec, 0x0069}, {0x00ed, 0x0069}, {0x00ee, 0x0069},
++ {0x00ef, 0x0069}, {0x00f1, 0x006e}, {0x00f2, 0x006f}, {0x00f3, 0x006f},
++ {0x00f4, 0x006f}, {0x00f5, 0x006f}, {0x00f6, 0x006f}, {0x00f9, 0x0075},
++ {0x00fa, 0x0075}, {0x00fb, 0x0075}, {0x00fc, 0x0075}, {0x00fd, 0x0079},
++ {0x00ff, 0x0079}, {0x0100, 0x0041}, {0x0101, 0x0061}, {0x0102, 0x0041},
++ {0x0103, 0x0061}, {0x0104, 0x0041}, {0x0105, 0x0061}, {0x0106, 0x0043},
++ {0x0107, 0x0063}, {0x0108, 0x0043}, {0x0109, 0x0063}, {0x010a, 0x0043},
++ {0x010b, 0x0063}, {0x010c, 0x0043}, {0x010d, 0x0063}, {0x010e, 0x0044},
++ {0x010f, 0x0064}, {0x0112, 0x0045}, {0x0113, 0x0065}, {0x0114, 0x0045},
++ {0x0115, 0x0065}, {0x0116, 0x0045}, {0x0117, 0x0065}, {0x0118, 0x0045},
++ {0x0119, 0x0065}, {0x011a, 0x0045}, {0x011b, 0x0065}, {0x011c, 0x0047},
++ {0x011d, 0x0067}, {0x011e, 0x0047}, {0x011f, 0x0067}, {0x0120, 0x0047},
++ {0x0121, 0x0067}, {0x0122, 0x0047}, {0x0123, 0x0067}, {0x0124, 0x0048},
++ {0x0125, 0x0068}, {0x0128, 0x0049}, {0x0129, 0x0069}, {0x012a, 0x0049},
++ {0x012b, 0x0069}, {0x012c, 0x0049}, {0x012d, 0x0069}, {0x012e, 0x0049},
++ {0x012f, 0x0069}, {0x0130, 0x0049}, {0x0134, 0x004a}, {0x0135, 0x006a},
++ {0x0136, 0x004b}, {0x0137, 0x006b}, {0x0139, 0x004c}, {0x013a, 0x006c},
++ {0x013b, 0x004c}, {0x013c, 0x006c}, {0x013d, 0x004c}, {0x013e, 0x006c},
++ {0x0143, 0x004e}, {0x0144, 0x006e}, {0x0145, 0x004e}, {0x0146, 0x006e},
++ {0x0147, 0x004e}, {0x0148, 0x006e}, {0x014c, 0x004f}, {0x014d, 0x006f},
++ {0x014e, 0x004f}, {0x014f, 0x006f}, {0x0150, 0x004f}, {0x0151, 0x006f},
++ {0x0154, 0x0052}, {0x0155, 0x0072}, {0x0156, 0x0052}, {0x0157, 0x0072},
++ {0x0158, 0x0052}, {0x0159, 0x0072}, {0x015a, 0x0053}, {0x015b, 0x0073},
++ {0x015c, 0x0053}, {0x015d, 0x0073}, {0x015e, 0x0053}, {0x015f, 0x0073},
++ {0x0160, 0x0053}, {0x0161, 0x0073}, {0x0162, 0x0054}, {0x0163, 0x0074},
++ {0x0164, 0x0054}, {0x0165, 0x0074}, {0x0168, 0x0055}, {0x0169, 0x0075},
++ {0x016a, 0x0055}, {0x016b, 0x0075}, {0x016c, 0x0055}, {0x016d, 0x0075},
++ {0x016e, 0x0055}, {0x016f, 0x0075}, {0x0170, 0x0055}, {0x0171, 0x0075},
++ {0x0172, 0x0055}, {0x0173, 0x0075}, {0x0174, 0x0057}, {0x0175, 0x0077},
++ {0x0176, 0x0059}, {0x0177, 0x0079}, {0x0178, 0x0059}, {0x0179, 0x005a},
++ {0x017a, 0x007a}, {0x017b, 0x005a}, {0x017c, 0x007a}, {0x017d, 0x005a},
++ {0x017e, 0x007a}, {0x01a0, 0x004f}, {0x01a1, 0x006f}, {0x01af, 0x0055},
++ {0x01b0, 0x0075}, {0x01cd, 0x0041}, {0x01ce, 0x0061}, {0x01cf, 0x0049},
++ {0x01d0, 0x0069}, {0x01d1, 0x004f}, {0x01d2, 0x006f}, {0x01d3, 0x0055},
++ {0x01d4, 0x0075}, {0x01d5, 0x0055}, {0x01d6, 0x0075}, {0x01d7, 0x0055},
++ {0x01d8, 0x0075}, {0x01d9, 0x0055}, {0x01da, 0x0075}, {0x01db, 0x0055},
++ {0x01dc, 0x0075}, {0x01de, 0x0041}, {0x01df, 0x0061}, {0x01e0, 0x0041},
++ {0x01e1, 0x0061}, {0x01e2, 0x00c6}, {0x01e3, 0x00e6}, {0x01e6, 0x0047},
++ {0x01e7, 0x0067}, {0x01e8, 0x004b}, {0x01e9, 0x006b}, {0x01ea, 0x004f},
++ {0x01eb, 0x006f}, {0x01ec, 0x004f}, {0x01ed, 0x006f}, {0x01ee, 0x01b7},
++ {0x01ef, 0x0292}, {0x01f0, 0x006a}, {0x01f4, 0x0047}, {0x01f5, 0x0067},
++ {0x01f8, 0x004e}, {0x01f9, 0x006e}, {0x01fa, 0x0041}, {0x01fb, 0x0061},
++ {0x01fc, 0x00c6}, {0x01fd, 0x00e6}, {0x01fe, 0x00d8}, {0x01ff, 0x00f8},
++ {0x0200, 0x0041}, {0x0201, 0x0061}, {0x0202, 0x0041}, {0x0203, 0x0061},
++ {0x0204, 0x0045}, {0x0205, 0x0065}, {0x0206, 0x0045}, {0x0207, 0x0065},
++ {0x0208, 0x0049}, {0x0209, 0x0069}, {0x020a, 0x0049}, {0x020b, 0x0069},
++ {0x020c, 0x004f}, {0x020d, 0x006f}, {0x020e, 0x004f}, {0x020f, 0x006f},
++ {0x0210, 0x0052}, {0x0211, 0x0072}, {0x0212, 0x0052}, {0x0213, 0x0072},
++ {0x0214, 0x0055}, {0x0215, 0x0075}, {0x0216, 0x0055}, {0x0217, 0x0075},
++ {0x0218, 0x0053}, {0x0219, 0x0073}, {0x021a, 0x0054}, {0x021b, 0x0074},
++ {0x021e, 0x0048}, {0x021f, 0x0068}, {0x0226, 0x0041}, {0x0227, 0x0061},
++ {0x0228, 0x0045}, {0x0229, 0x0065}, {0x022a, 0x004f}, {0x022b, 0x006f},
++ {0x022c, 0x004f}, {0x022d, 0x006f}, {0x022e, 0x004f}, {0x022f, 0x006f},
++ {0x0230, 0x004f}, {0x0231, 0x006f}, {0x0232, 0x0059}, {0x0233, 0x0079},
++ {0x0374, 0x02b9}, {0x0386, 0x0391}, {0x0388, 0x0395}, {0x0389, 0x0397},
++ {0x038a, 0x0399}, {0x038c, 0x039f}, {0x038e, 0x03a5}, {0x038f, 0x03a9},
++ {0x0390, 0x03b9}, {0x03aa, 0x0399}, {0x03ab, 0x03a5}, {0x03ac, 0x03b1},
++ {0x03ad, 0x03b5}, {0x03ae, 0x03b7}, {0x03af, 0x03b9}, {0x03b0, 0x03c5},
++ {0x03ca, 0x03b9}, {0x03cb, 0x03c5}, {0x03cc, 0x03bf}, {0x03cd, 0x03c5},
++ {0x03ce, 0x03c9}, {0x03d3, 0x03d2}, {0x03d4, 0x03d2}, {0x0400, 0x0415},
++ {0x0401, 0x0415}, {0x0403, 0x0413}, {0x0407, 0x0406}, {0x040c, 0x041a},
++ {0x040d, 0x0418}, {0x040e, 0x0423}, {0x0419, 0x0418}, {0x0439, 0x0438},
++ {0x0450, 0x0435}, {0x0451, 0x0435}, {0x0453, 0x0433}, {0x0457, 0x0456},
++ {0x045c, 0x043a}, {0x045d, 0x0438}, {0x045e, 0x0443}, {0x0476, 0x0474},
++ {0x0477, 0x0475}, {0x04c1, 0x0416}, {0x04c2, 0x0436}, {0x04d0, 0x0410},
++ {0x04d1, 0x0430}, {0x04d2, 0x0410}, {0x04d3, 0x0430}, {0x04d6, 0x0415},
++ {0x04d7, 0x0435}, {0x04da, 0x04d8}, {0x04db, 0x04d9}, {0x04dc, 0x0416},
++ {0x04dd, 0x0436}, {0x04de, 0x0417}, {0x04df, 0x0437}, {0x04e2, 0x0418},
++ {0x04e3, 0x0438}, {0x04e4, 0x0418}, {0x04e5, 0x0438}, {0x04e6, 0x041e},
++ {0x04e7, 0x043e}, {0x04ea, 0x04e8}, {0x04eb, 0x04e9}, {0x04ec, 0x042d},
++ {0x04ed, 0x044d}, {0x04ee, 0x0423}, {0x04ef, 0x0443}, {0x04f0, 0x0423},
++ {0x04f1, 0x0443}, {0x04f2, 0x0423}, {0x04f3, 0x0443}, {0x04f4, 0x0427},
++ {0x04f5, 0x0447}, {0x04f8, 0x042b}, {0x04f9, 0x044b}, {0x1e00, 0x0041},
++ {0x1e01, 0x0061}, {0x1e02, 0x0042}, {0x1e03, 0x0062}, {0x1e04, 0x0042},
++ {0x1e05, 0x0062}, {0x1e06, 0x0042}, {0x1e07, 0x0062}, {0x1e08, 0x0043},
++ {0x1e09, 0x0063}, {0x1e0a, 0x0044}, {0x1e0b, 0x0064}, {0x1e0c, 0x0044},
++ {0x1e0d, 0x0064}, {0x1e0e, 0x0044}, {0x1e0f, 0x0064}, {0x1e10, 0x0044},
++ {0x1e11, 0x0064}, {0x1e12, 0x0044}, {0x1e13, 0x0064}, {0x1e14, 0x0045},
++ {0x1e15, 0x0065}, {0x1e16, 0x0045}, {0x1e17, 0x0065}, {0x1e18, 0x0045},
++ {0x1e19, 0x0065}, {0x1e1a, 0x0045}, {0x1e1b, 0x0065}, {0x1e1c, 0x0045},
++ {0x1e1d, 0x0065}, {0x1e1e, 0x0046}, {0x1e1f, 0x0066}, {0x1e20, 0x0047},
++ {0x1e21, 0x0067}, {0x1e22, 0x0048}, {0x1e23, 0x0068}, {0x1e24, 0x0048},
++ {0x1e25, 0x0068}, {0x1e26, 0x0048}, {0x1e27, 0x0068}, {0x1e28, 0x0048},
++ {0x1e29, 0x0068}, {0x1e2a, 0x0048}, {0x1e2b, 0x0068}, {0x1e2c, 0x0049},
++ {0x1e2d, 0x0069}, {0x1e2e, 0x0049}, {0x1e2f, 0x0069}, {0x1e30, 0x004b},
++ {0x1e31, 0x006b}, {0x1e32, 0x004b}, {0x1e33, 0x006b}, {0x1e34, 0x004b},
++ {0x1e35, 0x006b}, {0x1e36, 0x004c}, {0x1e37, 0x006c}, {0x1e38, 0x004c},
++ {0x1e39, 0x006c}, {0x1e3a, 0x004c}, {0x1e3b, 0x006c}, {0x1e3c, 0x004c},
++ {0x1e3d, 0x006c}, {0x1e3e, 0x004d}, {0x1e3f, 0x006d}, {0x1e40, 0x004d},
++ {0x1e41, 0x006d}, {0x1e42, 0x004d}, {0x1e43, 0x006d}, {0x1e44, 0x004e},
++ {0x1e45, 0x006e}, {0x1e46, 0x004e}, {0x1e47, 0x006e}, {0x1e48, 0x004e},
++ {0x1e49, 0x006e}, {0x1e4a, 0x004e}, {0x1e4b, 0x006e}, {0x1e4c, 0x004f},
++ {0x1e4d, 0x006f}, {0x1e4e, 0x004f}, {0x1e4f, 0x006f}, {0x1e50, 0x004f},
++ {0x1e51, 0x006f}, {0x1e52, 0x004f}, {0x1e53, 0x006f}, {0x1e54, 0x0050},
++ {0x1e55, 0x0070}, {0x1e56, 0x0050}, {0x1e57, 0x0070}, {0x1e58, 0x0052},
++ {0x1e59, 0x0072}, {0x1e5a, 0x0052}, {0x1e5b, 0x0072}, {0x1e5c, 0x0052},
++ {0x1e5d, 0x0072}, {0x1e5e, 0x0052}, {0x1e5f, 0x0072}, {0x1e60, 0x0053},
++ {0x1e61, 0x0073}, {0x1e62, 0x0053}, {0x1e63, 0x0073}, {0x1e64, 0x0053},
++ {0x1e65, 0x0073}, {0x1e66, 0x0053}, {0x1e67, 0x0073}, {0x1e68, 0x0053},
++ {0x1e69, 0x0073}, {0x1e6a, 0x0054}, {0x1e6b, 0x0074}, {0x1e6c, 0x0054},
++ {0x1e6d, 0x0074}, {0x1e6e, 0x0054}, {0x1e6f, 0x0074}, {0x1e70, 0x0054},
++ {0x1e71, 0x0074}, {0x1e72, 0x0055}, {0x1e73, 0x0075}, {0x1e74, 0x0055},
++ {0x1e75, 0x0075}, {0x1e76, 0x0055}, {0x1e77, 0x0075}, {0x1e78, 0x0055},
++ {0x1e79, 0x0075}, {0x1e7a, 0x0055}, {0x1e7b, 0x0075}, {0x1e7c, 0x0056},
++ {0x1e7d, 0x0076}, {0x1e7e, 0x0056}, {0x1e7f, 0x0076}, {0x1e80, 0x0057},
++ {0x1e81, 0x0077}, {0x1e82, 0x0057}, {0x1e83, 0x0077}, {0x1e84, 0x0057},
++ {0x1e85, 0x0077}, {0x1e86, 0x0057}, {0x1e87, 0x0077}, {0x1e88, 0x0057},
++ {0x1e89, 0x0077}, {0x1e8a, 0x0058}, {0x1e8b, 0x0078}, {0x1e8c, 0x0058},
++ {0x1e8d, 0x0078}, {0x1e8e, 0x0059}, {0x1e8f, 0x0079}, {0x1e90, 0x005a},
++ {0x1e91, 0x007a}, {0x1e92, 0x005a}, {0x1e93, 0x007a}, {0x1e94, 0x005a},
++ {0x1e95, 0x007a}, {0x1e96, 0x0068}, {0x1e97, 0x0074}, {0x1e98, 0x0077},
++ {0x1e99, 0x0079}, {0x1e9b, 0x017f}, {0x1ea0, 0x0041}, {0x1ea1, 0x0061},
++ {0x1ea2, 0x0041}, {0x1ea3, 0x0061}, {0x1ea4, 0x0041}, {0x1ea5, 0x0061},
++ {0x1ea6, 0x0041}, {0x1ea7, 0x0061}, {0x1ea8, 0x0041}, {0x1ea9, 0x0061},
++ {0x1eaa, 0x0041}, {0x1eab, 0x0061}, {0x1eac, 0x0041}, {0x1ead, 0x0061},
++ {0x1eae, 0x0041}, {0x1eaf, 0x0061}, {0x1eb0, 0x0041}, {0x1eb1, 0x0061},
++ {0x1eb2, 0x0041}, {0x1eb3, 0x0061}, {0x1eb4, 0x0041}, {0x1eb5, 0x0061},
++ {0x1eb6, 0x0041}, {0x1eb7, 0x0061}, {0x1eb8, 0x0045}, {0x1eb9, 0x0065},
++ {0x1eba, 0x0045}, {0x1ebb, 0x0065}, {0x1ebc, 0x0045}, {0x1ebd, 0x0065},
++ {0x1ebe, 0x0045}, {0x1ebf, 0x0065}, {0x1ec0, 0x0045}, {0x1ec1, 0x0065},
++ {0x1ec2, 0x0045}, {0x1ec3, 0x0065}, {0x1ec4, 0x0045}, {0x1ec5, 0x0065},
++ {0x1ec6, 0x0045}, {0x1ec7, 0x0065}, {0x1ec8, 0x0049}, {0x1ec9, 0x0069},
++ {0x1eca, 0x0049}, {0x1ecb, 0x0069}, {0x1ecc, 0x004f}, {0x1ecd, 0x006f},
++ {0x1ece, 0x004f}, {0x1ecf, 0x006f}, {0x1ed0, 0x004f}, {0x1ed1, 0x006f},
++ {0x1ed2, 0x004f}, {0x1ed3, 0x006f}, {0x1ed4, 0x004f}, {0x1ed5, 0x006f},
++ {0x1ed6, 0x004f}, {0x1ed7, 0x006f}, {0x1ed8, 0x004f}, {0x1ed9, 0x006f},
++ {0x1eda, 0x004f}, {0x1edb, 0x006f}, {0x1edc, 0x004f}, {0x1edd, 0x006f},
++ {0x1ede, 0x004f}, {0x1edf, 0x006f}, {0x1ee0, 0x004f}, {0x1ee1, 0x006f},
++ {0x1ee2, 0x004f}, {0x1ee3, 0x006f}, {0x1ee4, 0x0055}, {0x1ee5, 0x0075},
++ {0x1ee6, 0x0055}, {0x1ee7, 0x0075}, {0x1ee8, 0x0055}, {0x1ee9, 0x0075},
++ {0x1eea, 0x0055}, {0x1eeb, 0x0075}, {0x1eec, 0x0055}, {0x1eed, 0x0075},
++ {0x1eee, 0x0055}, {0x1eef, 0x0075}, {0x1ef0, 0x0055}, {0x1ef1, 0x0075},
++ {0x1ef2, 0x0059}, {0x1ef3, 0x0079}, {0x1ef4, 0x0059}, {0x1ef5, 0x0079},
++ {0x1ef6, 0x0059}, {0x1ef7, 0x0079}, {0x1ef8, 0x0059}, {0x1ef9, 0x0079},
++ {0x1f00, 0x03b1}, {0x1f01, 0x03b1}, {0x1f02, 0x03b1}, {0x1f03, 0x03b1},
++ {0x1f04, 0x03b1}, {0x1f05, 0x03b1}, {0x1f06, 0x03b1}, {0x1f07, 0x03b1},
++ {0x1f08, 0x0391}, {0x1f09, 0x0391}, {0x1f0a, 0x0391}, {0x1f0b, 0x0391},
++ {0x1f0c, 0x0391}, {0x1f0d, 0x0391}, {0x1f0e, 0x0391}, {0x1f0f, 0x0391},
++ {0x1f10, 0x03b5}, {0x1f11, 0x03b5}, {0x1f12, 0x03b5}, {0x1f13, 0x03b5},
++ {0x1f14, 0x03b5}, {0x1f15, 0x03b5}, {0x1f18, 0x0395}, {0x1f19, 0x0395},
++ {0x1f1a, 0x0395}, {0x1f1b, 0x0395}, {0x1f1c, 0x0395}, {0x1f1d, 0x0395},
++ {0x1f20, 0x03b7}, {0x1f21, 0x03b7}, {0x1f22, 0x03b7}, {0x1f23, 0x03b7},
++ {0x1f24, 0x03b7}, {0x1f25, 0x03b7}, {0x1f26, 0x03b7}, {0x1f27, 0x03b7},
++ {0x1f28, 0x0397}, {0x1f29, 0x0397}, {0x1f2a, 0x0397}, {0x1f2b, 0x0397},
++ {0x1f2c, 0x0397}, {0x1f2d, 0x0397}, {0x1f2e, 0x0397}, {0x1f2f, 0x0397},
++ {0x1f30, 0x03b9}, {0x1f31, 0x03b9}, {0x1f32, 0x03b9}, {0x1f33, 0x03b9},
++ {0x1f34, 0x03b9}, {0x1f35, 0x03b9}, {0x1f36, 0x03b9}, {0x1f37, 0x03b9},
++ {0x1f38, 0x0399}, {0x1f39, 0x0399}, {0x1f3a, 0x0399}, {0x1f3b, 0x0399},
++ {0x1f3c, 0x0399}, {0x1f3d, 0x0399}, {0x1f3e, 0x0399}, {0x1f3f, 0x0399},
++ {0x1f40, 0x03bf}, {0x1f41, 0x03bf}, {0x1f42, 0x03bf}, {0x1f43, 0x03bf},
++ {0x1f44, 0x03bf}, {0x1f45, 0x03bf}, {0x1f48, 0x039f}, {0x1f49, 0x039f},
++ {0x1f4a, 0x039f}, {0x1f4b, 0x039f}, {0x1f4c, 0x039f}, {0x1f4d, 0x039f},
++ {0x1f50, 0x03c5}, {0x1f51, 0x03c5}, {0x1f52, 0x03c5}, {0x1f53, 0x03c5},
++ {0x1f54, 0x03c5}, {0x1f55, 0x03c5}, {0x1f56, 0x03c5}, {0x1f57, 0x03c5},
++ {0x1f59, 0x03a5}, {0x1f5b, 0x03a5}, {0x1f5d, 0x03a5}, {0x1f5f, 0x03a5},
++ {0x1f60, 0x03c9}, {0x1f61, 0x03c9}, {0x1f62, 0x03c9}, {0x1f63, 0x03c9},
++ {0x1f64, 0x03c9}, {0x1f65, 0x03c9}, {0x1f66, 0x03c9}, {0x1f67, 0x03c9},
++ {0x1f68, 0x03a9}, {0x1f69, 0x03a9}, {0x1f6a, 0x03a9}, {0x1f6b, 0x03a9},
++ {0x1f6c, 0x03a9}, {0x1f6d, 0x03a9}, {0x1f6e, 0x03a9}, {0x1f6f, 0x03a9},
++ {0x1f70, 0x03b1}, {0x1f71, 0x03b1}, {0x1f72, 0x03b5}, {0x1f73, 0x03b5},
++ {0x1f74, 0x03b7}, {0x1f75, 0x03b7}, {0x1f76, 0x03b9}, {0x1f77, 0x03b9},
++ {0x1f78, 0x03bf}, {0x1f79, 0x03bf}, {0x1f7a, 0x03c5}, {0x1f7b, 0x03c5},
++ {0x1f7c, 0x03c9}, {0x1f7d, 0x03c9}, {0x1f80, 0x03b1}, {0x1f81, 0x03b1},
++ {0x1f82, 0x03b1}, {0x1f83, 0x03b1}, {0x1f84, 0x03b1}, {0x1f85, 0x03b1},
++ {0x1f86, 0x03b1}, {0x1f87, 0x03b1}, {0x1f88, 0x0391}, {0x1f89, 0x0391},
++ {0x1f8a, 0x0391}, {0x1f8b, 0x0391}, {0x1f8c, 0x0391}, {0x1f8d, 0x0391},
++ {0x1f8e, 0x0391}, {0x1f8f, 0x0391}, {0x1f90, 0x03b7}, {0x1f91, 0x03b7},
++ {0x1f92, 0x03b7}, {0x1f93, 0x03b7}, {0x1f94, 0x03b7}, {0x1f95, 0x03b7},
++ {0x1f96, 0x03b7}, {0x1f97, 0x03b7}, {0x1f98, 0x0397}, {0x1f99, 0x0397},
++ {0x1f9a, 0x0397}, {0x1f9b, 0x0397}, {0x1f9c, 0x0397}, {0x1f9d, 0x0397},
++ {0x1f9e, 0x0397}, {0x1f9f, 0x0397}, {0x1fa0, 0x03c9}, {0x1fa1, 0x03c9},
++ {0x1fa2, 0x03c9}, {0x1fa3, 0x03c9}, {0x1fa4, 0x03c9}, {0x1fa5, 0x03c9},
++ {0x1fa6, 0x03c9}, {0x1fa7, 0x03c9}, {0x1fa8, 0x03a9}, {0x1fa9, 0x03a9},
++ {0x1faa, 0x03a9}, {0x1fab, 0x03a9}, {0x1fac, 0x03a9}, {0x1fad, 0x03a9},
++ {0x1fae, 0x03a9}, {0x1faf, 0x03a9}, {0x1fb0, 0x03b1}, {0x1fb1, 0x03b1},
++ {0x1fb2, 0x03b1}, {0x1fb3, 0x03b1}, {0x1fb4, 0x03b1}, {0x1fb6, 0x03b1},
++ {0x1fb7, 0x03b1}, {0x1fb8, 0x0391}, {0x1fb9, 0x0391}, {0x1fba, 0x0391},
++ {0x1fbb, 0x0391}, {0x1fbc, 0x0391}, {0x1fbe, 0x03b9}, {0x1fc2, 0x03b7},
++ {0x1fc3, 0x03b7}, {0x1fc4, 0x03b7}, {0x1fc6, 0x03b7}, {0x1fc7, 0x03b7},
++ {0x1fc8, 0x0395}, {0x1fc9, 0x0395}, {0x1fca, 0x0397}, {0x1fcb, 0x0397},
++ {0x1fcc, 0x0397}, {0x1fd0, 0x03b9}, {0x1fd1, 0x03b9}, {0x1fd2, 0x03b9},
++ {0x1fd3, 0x03b9}, {0x1fd6, 0x03b9}, {0x1fd7, 0x03b9}, {0x1fd8, 0x0399},
++ {0x1fd9, 0x0399}, {0x1fda, 0x0399}, {0x1fdb, 0x0399}, {0x1fe0, 0x03c5},
++ {0x1fe1, 0x03c5}, {0x1fe2, 0x03c5}, {0x1fe3, 0x03c5}, {0x1fe4, 0x03c1},
++ {0x1fe5, 0x03c1}, {0x1fe6, 0x03c5}, {0x1fe7, 0x03c5}, {0x1fe8, 0x03a5},
++ {0x1fe9, 0x03a5}, {0x1fea, 0x03a5}, {0x1feb, 0x03a5}, {0x1fec, 0x03a1},
++ {0x1ff2, 0x03c9}, {0x1ff3, 0x03c9}, {0x1ff4, 0x03c9}, {0x1ff6, 0x03c9},
++ {0x1ff7, 0x03c9}, {0x1ff8, 0x039f}, {0x1ff9, 0x039f}, {0x1ffa, 0x03a9},
++ {0x1ffb, 0x03a9}, {0x1ffc, 0x03a9},
++};
++/* END GENERATED */
++
++/* Base letter of a letter with diacritics, or c itself. */
++static inline uint32_t
++typo_fold(uint32_t c)
++{
++ size_t lo = 0, hi = sizeof typo_fold_table / sizeof typo_fold_table[0];
++
++ if (c < 0xc0 || c > 0xffff)
++ return c;
++ while (lo < hi) {
++ size_t mid = (lo + hi) / 2;
++
++ if (typo_fold_table[mid][0] == c)
++ return typo_fold_table[mid][1];
++ if (typo_fold_table[mid][0] < c)
++ lo = mid + 1;
++ else
++ hi = mid;
++ }
++ return c;
++}
++
++/* Combining marks, which are skipped. */
++static inline int
++typo_is_mark(uint32_t c)
++{
++ return (c >= 0x0300 && c <= 0x036f) || (c >= 0x1ab0 && c <= 0x1aff) ||
++ (c >= 0x1dc0 && c <= 0x1dff) || (c >= 0x20d0 && c <= 0x20ff) ||
++ (c >= 0xfe20 && c <= 0xfe2f);
++}
++
++/* Decodes one UTF-8 character at *s and advances *s. */
++static inline uint32_t
++typo_decode(const char **s)
++{
++ const unsigned char *p = (const unsigned char *)*s;
++ uint32_t c = p[0];
++ int n = 0, i;
++
++ if (c >= 0xf0 && c < 0xf8)
++ n = 3, c &= 0x07;
++ else if (c >= 0xe0)
++ n = 2, c &= 0x0f;
++ else if (c >= 0xc0)
++ n = 1, c &= 0x1f;
++ for (i = 1; i <= n; i++) {
++ /* broken sequence: take the first byte as it is */
++ if ((p[i] & 0xc0) != 0x80) {
++ c = p[0];
++ n = 0;
++ break;
++ }
++ c = (c << 6) | (p[i] & 0x3f);
++ }
++ *s += n + 1;
++ return c;
++}
++
++/*
++ * Next character to compare at *s: without diacritics, lowercased if
++ * typo_ignore_case; combining marks are skipped. Returns 0 at the end.
++ */
++static inline uint32_t
++typo_next_char(const char **s)
++{
++ uint32_t c;
++
++ do {
++ if (!**s)
++ return 0;
++ c = typo_decode(s);
++ } while (typo_is_mark(c));
++ c = typo_fold(c);
++ return typo_ignore_case ? (uint32_t)towlower((wint_t)c) : c;
++}
++
++/* Number of characters in a UTF-8 string. */
++static inline size_t
++typo_strlen(const char *s)
++{
++ size_t n = 0;
++
++ while (typo_next_char(&s))
++ n++;
++ return n;
++}
++
++/* Errors allowed for a pattern of len characters (0: exact matches only). */
++static inline int
++typo_max_errors(size_t len, unsigned int min_len_1, unsigned int min_len_2)
++{
++ return len >= min_len_2 ? 2 : len >= min_len_1 ? 1 : 0;
++}
++
++/*
++ * Distance from pattern to the closest substring of text; if it is greater
++ * than max, returns max + 1.
++ */
++static inline int
++typo_distance(const char *pattern, const char *text, int max)
++{
++ uint32_t pat[TYPO_PATTERN_MAX];
++ int prev2[TYPO_PATTERN_MAX + 1], prev[TYPO_PATTERN_MAX + 1];
++ int cur[TYPO_PATTERN_MAX + 1];
++ int m = 0, i, j, best, v;
++ uint32_t tc, tprev = 0;
++
++ while ((tc = typo_next_char(&pattern))) {
++ if (m == TYPO_PATTERN_MAX)
++ return max + 1;
++ pat[m++] = tc;
++ }
++ if (m == 0)
++ return 0;
++ for (i = 0; i <= m; i++)
++ prev[i] = prev2[i] = i;
++ best = m;
++ for (j = 0; (tc = typo_next_char(&text)); j++) {
++ cur[0] = 0; /* the substring may start anywhere */
++ for (i = 1; i <= m; i++) {
++ /* substitute, skip in text, skip in pattern */
++ v = prev[i - 1] + (pat[i - 1] != tc);
++ if (prev[i] + 1 < v)
++ v = prev[i] + 1;
++ if (cur[i - 1] + 1 < v)
++ v = cur[i - 1] + 1;
++ /* swap of two adjacent characters */
++ if (i > 1 && j > 0 && pat[i - 1] == tprev &&
++ pat[i - 2] == tc && prev2[i - 2] + 1 < v)
++ v = prev2[i - 2] + 1;
++ cur[i] = v;
++ }
++ if (cur[m] < best)
++ best = cur[m]; /* ... and end anywhere */
++ for (i = 0; i <= m; i++) {
++ prev2[i] = prev[i];
++ prev[i] = cur[i];
++ }
++ tprev = tc;
++ }
++ return best > max ? max + 1 : best;
++}
++
++/* Whether text contains pattern, ignoring diacritics (and case), no errors. */
++static inline int
++typo_contains(const char *pattern, const char *text)
++{
++ return typo_distance(pattern, text, 0) == 0;
++}
++
++#endif /* TYPO_H */
diff --git a/tools.suckless.org/dmenu/patches/typo/index.md b/tools.suckless.org/dmenu/patches/typo/index.md
@@ -0,0 +1,35 @@
+# typo
+
+## Description
+
+Typo-tolerant matching for dmenu.
+
+Every word of the input also matches ignoring diacritics, so `cafe` finds
+`café` and `елка` finds `ёлка`. When the input is a single word, items
+that contain it with up to one or two errors are listed after the exact,
+prefix and substring matches, fewest errors first.
+
+An error is an inserted, deleted or substituted character, or two adjacent
+characters swapped (restricted Damerau-Levenshtein distance), so `frefox`,
+`firefxo` and `fierfox` all find `firefox`. The input is compared with any
+part of an item, character by character in UTF-8.
+
+## Notes
+
+- One error is allowed from 5 input characters, two from 8: set
+ `typo_min_len_1` and `typo_min_len_2` in `config.h` (0 disables).
+- Case follows dmenu's `-i` switch; diacritics are always ignored.
+- Unlike [fuzzymatch](../fuzzymatch/), which forgives only missing letters,
+ this patch also forgives extra, wrong and swapped letters, and keeps the
+ usual order of exact matches.
+- The patch adds `typo.h`, a single-header implementation that can be
+ reused elsewhere. Upstream, with rofi modes using the same matching:
+ <https://github.com/mbutov/menu-typo>
+
+## Download
+
+- [dmenu-typo-5.4.diff](dmenu-typo-5.4.diff)
+
+## Authors
+
+- Maxim Butov - <mbutov@gmail.com>
