summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/config.c2
-rw-r--r--src/desktop_vec.c43
-rw-r--r--src/desktop_vec.h4
-rw-r--r--src/fuzzy_match.c92
-rw-r--r--src/fuzzy_match.h8
-rw-r--r--src/main.c10
-rw-r--r--src/string_vec.c34
-rw-r--r--src/string_vec.h6
-rw-r--r--src/tofi.h1
9 files changed, 173 insertions, 27 deletions
diff --git a/src/config.c b/src/config.c
index 7ee29e8..801a5bf 100644
--- a/src/config.c
+++ b/src/config.c
@@ -321,6 +321,8 @@ bool parse_option(struct tofi *tofi, const char *filename, size_t lineno, const
tofi->hide_cursor = parse_bool(filename, lineno, value, &err);
} else if (strcasecmp(option, "history") == 0) {
tofi->use_history = parse_bool(filename, lineno, value, &err);
+ } else if (strcasecmp(option, "fuzzy-match") == 0) {
+ tofi->fuzzy_match = parse_bool(filename, lineno, value, &err);
} else if (strcasecmp(option, "drun-launch") == 0) {
tofi->drun_launch = parse_bool(filename, lineno, value, &err);
} else if (strcasecmp(option, "drun-print-exec") == 0) {
diff --git a/src/desktop_vec.c b/src/desktop_vec.c
index f4363f8..5d63390 100644
--- a/src/desktop_vec.c
+++ b/src/desktop_vec.c
@@ -1,6 +1,7 @@
#include <glib.h>
#include <stdbool.h>
#include "desktop_vec.h"
+#include "fuzzy_match.h"
#include "log.h"
#include "string_vec.h"
#include "xmalloc.h"
@@ -119,10 +120,10 @@ static int cmpscorep(const void *restrict a, const void *restrict b)
{
struct scored_string *restrict str1 = (struct scored_string *)a;
struct scored_string *restrict str2 = (struct scored_string *)b;
- if (str1->history_score != str2->history_score) {
- return str2->history_score - str1->history_score;
- }
- return str1->search_score - str2->search_score;
+
+ int hist_diff = str2->history_score - str1->history_score;
+ int search_diff = str2->search_score - str1->search_score;
+ return hist_diff + search_diff;
}
void desktop_vec_sort(struct desktop_vec *restrict vec)
@@ -142,29 +143,49 @@ struct desktop_entry *desktop_vec_find(struct desktop_vec *restrict vec, const c
struct string_vec desktop_vec_filter(
const struct desktop_vec *restrict vec,
- const char *restrict substr)
+ const char *restrict substr,
+ bool fuzzy)
{
struct string_vec filt = string_vec_create();
for (size_t i = 0; i < vec->count; i++) {
- char *c = strcasestr(vec->buf[i].name, substr);
- if (c != NULL) {
+ int32_t search_score;
+ if (fuzzy) {
+ search_score = fuzzy_match(substr, vec->buf[i].name);
+ } else {
+ char *c = strcasestr(vec->buf[i].name, substr);
+ if (c == NULL) {
+ search_score = INT32_MIN;
+ } else {
+ search_score = vec->buf[i].name - c;
+ }
+ }
+ if (search_score != INT32_MIN) {
string_vec_add(&filt, vec->buf[i].name);
/*
* Store the position of the match in the string as
* its search_score, for later sorting.
*/
- filt.buf[filt.count - 1].search_score = c - vec->buf[i].name;
+ filt.buf[filt.count - 1].search_score = search_score;
filt.buf[filt.count - 1].history_score = vec->buf[i].history_score;
} else {
/* If we didn't match the name, check the keywords. */
- c = strcasestr(vec->buf[i].keywords, substr);
- if (c != NULL) {
+ if (fuzzy) {
+ search_score = fuzzy_match(substr, vec->buf[i].keywords);
+ } else {
+ char *c = strcasestr(vec->buf[i].keywords, substr);
+ if (c == NULL) {
+ search_score = INT32_MIN;
+ } else {
+ search_score = vec->buf[i].keywords - c;
+ }
+ }
+ if (search_score != INT32_MIN) {
string_vec_add(&filt, vec->buf[i].name);
/*
* Arbitrary score addition to make name
* matches preferred over keyword matches.
*/
- filt.buf[filt.count - 1].search_score = 10 + c - vec->buf[i].keywords;
+ filt.buf[filt.count - 1].search_score = search_score - 20;
filt.buf[filt.count - 1].history_score = vec->buf[i].history_score;
}
}
diff --git a/src/desktop_vec.h b/src/desktop_vec.h
index 85c885e..a731566 100644
--- a/src/desktop_vec.h
+++ b/src/desktop_vec.h
@@ -1,6 +1,7 @@
#ifndef DESKTOP_VEC_H
#define DESKTOP_VEC_H
+#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#include <stdint.h>
@@ -35,7 +36,8 @@ void desktop_vec_sort(struct desktop_vec *restrict vec);
struct desktop_entry *desktop_vec_find(struct desktop_vec *restrict vec, const char *name);
struct string_vec desktop_vec_filter(
const struct desktop_vec *restrict vec,
- const char *restrict substr);
+ const char *restrict substr,
+ bool fuzzy);
struct desktop_vec desktop_vec_load(FILE *file);
void desktop_vec_save(struct desktop_vec *restrict vec, FILE *restrict file);
diff --git a/src/fuzzy_match.c b/src/fuzzy_match.c
new file mode 100644
index 0000000..1283151
--- /dev/null
+++ b/src/fuzzy_match.c
@@ -0,0 +1,92 @@
+#include <ctype.h>
+#include <stdbool.h>
+#include <stddef.h>
+#include <stdint.h>
+#include <string.h>
+
+#include "fuzzy_match.h"
+
+#undef MAX
+#define MAX(a, b) ((a) > (b) ? (a) : (b))
+
+/*
+ * Returns score if each character in pattern is found sequentially within str.
+ * Returns INT32_MIN otherwise.
+ *
+ * The scoring system is taken from fts_fuzzy_match v0.1.0 by Forrest Smith,
+ * which is licensed to the public domain.
+ *
+ * The factors affecting score are:
+ * - Bonuses:
+ * - If there are multiple adjacent matches.
+ * - If a match occurs after a separator character.
+ * - If a match is uppercase, and the previous character is lowercase.
+ *
+ * - Penalties:
+ * - If there are letters before the first match.
+ * - If there are superfluous characters in str.
+ */
+int32_t fuzzy_match(const char *restrict pattern, const char *restrict str)
+{
+ if (*pattern == '\0') {
+ return 0;
+ }
+ if (strlen(str) < strlen(pattern)) {
+ return INT32_MIN;
+ }
+
+ const int adjacency_bonus = 5;
+ const int separator_bonus = 10;
+ const int camel_bonus = 10;
+
+ const int leading_letter_penalty = -3;
+ const int max_leading_letter_penalty = -9;
+ const int unmatched_letter_penalty = -1;
+
+ int32_t score = 0;
+ const char *last_match = str;
+
+ /*
+ * Iterate through pattern, jumping to the next matching character in
+ * str. This will only ever find the first fuzzy match, not the best,
+ * but it's good enough and very quick.
+ */
+ for (size_t pidx = 0; pattern[pidx] != '\0'; pidx++) {
+ char search[2] = { pattern[pidx], '\0' };
+ char *match = strcasestr(last_match, search);
+ if (match == NULL) {
+ return INT32_MIN;
+ }
+
+ int32_t jump = match - last_match;
+
+ /* Apply bonuses. */
+ if (pidx > 0 && jump == 0) {
+ score += adjacency_bonus;
+ }
+ if (pidx > 0 || jump > 0) {
+ if (isupper(*match) && islower(*(match - 1))) {
+ score += camel_bonus;
+ }
+ if (isalnum(*match) && !isalnum(*(match - 1))) {
+ score += separator_bonus;
+ }
+ }
+ if (pidx == 0 && jump == 0) {
+ /* Match at start of string gets separator bonus. */
+ score += separator_bonus;
+ }
+
+ /* Apply penalties. */
+ if (pidx == 0) {
+ score += MAX(leading_letter_penalty * jump,
+ max_leading_letter_penalty);
+ }
+
+ last_match = match + 1;
+ }
+
+ score += unmatched_letter_penalty * (strlen(str) - strlen(pattern));
+
+ return score;
+}
diff --git a/src/fuzzy_match.h b/src/fuzzy_match.h
new file mode 100644
index 0000000..df4d298
--- /dev/null
+++ b/src/fuzzy_match.h
@@ -0,0 +1,8 @@
+#ifndef FUZZY_MATCH_H
+#define FUZZY_MATCH_H
+
+#include <stdint.h>
+
+int32_t fuzzy_match(const char *restrict pattern, const char *restrict str);
+
+#endif /* FUZZY_MATCH_H */
diff --git a/src/main.c b/src/main.c
index 32f6e15..8cc913d 100644
--- a/src/main.c
+++ b/src/main.c
@@ -168,12 +168,12 @@ static void handle_keypress(struct tofi *tofi, xkb_keycode_t keycode)
N_ELEM(buf));
entry->input_mb_length += len;
if (entry->drun) {
- struct string_vec results = desktop_vec_filter(&entry->apps, entry->input_mb);
+ struct string_vec results = desktop_vec_filter(&entry->apps, entry->input_mb, tofi->fuzzy_match);
string_vec_destroy(&entry->results);
entry->results = results;
} else {
struct string_vec tmp = entry->results;
- entry->results = string_vec_filter(&entry->results, entry->input_mb);
+ entry->results = string_vec_filter(&entry->results, entry->input_mb, tofi->fuzzy_match);
string_vec_destroy(&tmp);
}
}
@@ -189,9 +189,9 @@ static void handle_keypress(struct tofi *tofi, xkb_keycode_t keycode)
entry->input_mb_length = siz;
string_vec_destroy(&entry->results);
if (entry->drun) {
- entry->results = desktop_vec_filter(&entry->apps, entry->input_mb);
+ entry->results = desktop_vec_filter(&entry->apps, entry->input_mb, tofi->fuzzy_match);
} else {
- entry->results = string_vec_filter(&entry->commands, entry->input_mb);
+ entry->results = string_vec_filter(&entry->commands, entry->input_mb, tofi->fuzzy_match);
}
} else if (sym == XKB_KEY_Escape
|| (sym == XKB_KEY_c
@@ -775,6 +775,7 @@ static void usage()
" --hide-cursor <true|false> Hide the cursor.\n"
" --horizontal <true|false> List results horizontally.\n"
" --history <true|false> Sort results by number of usages.\n"
+" --fuzzy-match <true|false> Use fuzzy matching for searching.\n"
" --drun-launch <true|false> Launch apps directly in drun mode.\n"
" --drun-print-exec <true|false> Print a command line in drun mode.\n"
" This is now always the case,\n"
@@ -821,6 +822,7 @@ const struct option long_options[] = {
{"horizontal", required_argument, NULL, 0},
{"hide-cursor", required_argument, NULL, 0},
{"history", required_argument, NULL, 0},
+ {"fuzzy-match", required_argument, NULL, 0},
{"drun-launch", required_argument, NULL, 0},
{"drun-print-exec", required_argument, NULL, 0},
{"hint-font", required_argument, NULL, 0},
diff --git a/src/string_vec.c b/src/string_vec.c
index c337c61..464c450 100644
--- a/src/string_vec.c
+++ b/src/string_vec.c
@@ -1,8 +1,10 @@
+#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/mman.h>
+#include "fuzzy_match.h"
#include "string_vec.h"
#include "xmalloc.h"
@@ -31,10 +33,10 @@ static int cmpscorep(const void *restrict a, const void *restrict b)
{
struct scored_string *restrict str1 = (struct scored_string *)a;
struct scored_string *restrict str2 = (struct scored_string *)b;
- if (str1->history_score != str2->history_score) {
- return str2->history_score - str1->history_score;
- }
- return str1->search_score - str2->search_score;
+
+ int hist_diff = str2->history_score - str1->history_score;
+ int search_diff = str2->search_score - str1->search_score;
+ return hist_diff + search_diff;
}
struct string_vec string_vec_create(void)
@@ -55,7 +57,7 @@ void string_vec_destroy(struct string_vec *restrict vec)
free(vec->buf);
}
-struct string_vec string_vec_copy(struct string_vec *restrict vec)
+struct string_vec string_vec_copy(const struct string_vec *restrict vec)
{
struct string_vec copy = {
.count = vec->count,
@@ -110,18 +112,32 @@ char **string_vec_find(struct string_vec *restrict vec, const char * str)
struct string_vec string_vec_filter(
const struct string_vec *restrict vec,
- const char *restrict substr)
+ const char *restrict substr,
+ bool fuzzy)
{
+ if (substr[0] == '\0') {
+ return string_vec_copy(vec);
+ }
struct string_vec filt = string_vec_create();
for (size_t i = 0; i < vec->count; i++) {
- char *c = strcasestr(vec->buf[i].string, substr);
- if (c != NULL) {
+ int32_t search_score;
+ if (fuzzy) {
+ search_score = fuzzy_match(substr, vec->buf[i].string);
+ } else {
+ char *c = strcasestr(vec->buf[i].string, substr);
+ if (c == NULL) {
+ search_score = INT32_MIN;
+ } else {
+ search_score = vec->buf[i].string - c;
+ }
+ }
+ if (search_score != INT32_MIN) {
string_vec_add(&filt, vec->buf[i].string);
/*
* Store the position of the match in the string as
* its search_score, for later sorting.
*/
- filt.buf[filt.count - 1].search_score = c - vec->buf[i].string;
+ filt.buf[filt.count - 1].search_score = search_score;
filt.buf[filt.count - 1].history_score = vec->buf[i].history_score;
}
}
diff --git a/src/string_vec.h b/src/string_vec.h
index 7402052..f4e0bb9 100644
--- a/src/string_vec.h
+++ b/src/string_vec.h
@@ -1,6 +1,7 @@
#ifndef STRING_VEC_H
#define STRING_VEC_H
+#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
@@ -23,7 +24,7 @@ struct string_vec string_vec_create(void);
void string_vec_destroy(struct string_vec *restrict vec);
[[nodiscard("memory leaked")]]
-struct string_vec string_vec_copy(struct string_vec *restrict vec);
+struct string_vec string_vec_copy(const struct string_vec *restrict vec);
void string_vec_add(struct string_vec *restrict vec, const char *restrict str);
@@ -36,7 +37,8 @@ char **string_vec_find(struct string_vec *restrict vec, const char *str);
[[nodiscard("memory leaked")]]
struct string_vec string_vec_filter(
const struct string_vec *restrict vec,
- const char *restrict substr);
+ const char *restrict substr,
+ bool fuzzy);
[[nodiscard("memory leaked")]]
struct string_vec string_vec_load(FILE *file);
diff --git a/src/tofi.h b/src/tofi.h
index 1771ecd..1fcdf58 100644
--- a/src/tofi.h
+++ b/src/tofi.h
@@ -82,6 +82,7 @@ struct tofi {
bool late_keyboard_init;
bool drun_launch;
bool drun_print_exec;
+ bool fuzzy_match;
char target_output_name[MAX_OUTPUT_NAME_LEN];
};
generated by cgit v1.2.3 (git 2.39.1) at 2025-07-20 22:19:42 +0000