From 574eff0df1aff9bdc6d32939a03312cc08803de3 Mon Sep 17 00:00:00 2001 From: Phil Jones Date: Mon, 17 Apr 2023 23:43:05 +0100 Subject: Add --matching-algorithm option. This replaces the --fuzzy-match algorithm. Available choices are normal, prefix and fuzzy. Levenshtein distance was investigated, but it seems pretty rubbish for tofi's use case, where you normally want a good match when you've only typed a small portion of the target string. --- src/config.c | 30 +++++- src/desktop_vec.c | 21 +--- src/desktop_vec.h | 3 +- src/fuzzy_match.c | 238 ------------------------------------------ src/fuzzy_match.h | 10 -- src/input.c | 8 +- src/main.c | 2 +- src/matching.c | 301 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/matching.h | 14 +++ src/string_vec.c | 10 +- src/string_vec.h | 3 +- src/tofi.h | 3 +- 12 files changed, 363 insertions(+), 280 deletions(-) delete mode 100644 src/fuzzy_match.c delete mode 100644 src/fuzzy_match.h create mode 100644 src/matching.c create mode 100644 src/matching.h (limited to 'src') diff --git a/src/config.c b/src/config.c index b78e3af..2b85028 100644 --- a/src/config.c +++ b/src/config.c @@ -79,6 +79,8 @@ static uint32_t fixup_percentage(uint32_t value, uint32_t base, bool is_percent) static uint32_t parse_anchor(const char *filename, size_t lineno, const char *str, bool *err); static enum cursor_style parse_cursor_style(const char *filename, size_t lineno, const char *str, bool *err); +static enum matching_algorithm parse_matching_algorithm(const char *filename, size_t lineno, const char *str, bool *err); + static bool parse_bool(const char *filename, size_t lineno, const char *str, bool *err); static uint32_t parse_char(const char *filename, size_t lineno, const char *str, bool *err); static struct color parse_color(const char *filename, size_t lineno, const char *str, bool *err); @@ -683,10 +685,18 @@ bool parse_option(struct tofi *tofi, const char *filename, size_t lineno, const } } else if (strcasecmp(option, "history-file") == 0) { snprintf(tofi->history_file, N_ELEM(tofi->history_file), "%s", value); + } else if (strcasecmp(option, "matching-algorithm") == 0) { + enum matching_algorithm val = parse_matching_algorithm(filename, lineno, value, &err); + if (!err) { + tofi->matching_algorithm= val; + } } else if (strcasecmp(option, "fuzzy-match") == 0) { + log_warning("The \"fuzzy-match\" option is deprecated, and may be removed in future. Please switch to \"matching-algorithm\".\n"); bool val = parse_bool(filename, lineno, value, &err); if (!err) { - tofi->fuzzy_match = val; + if (val) { + tofi->matching_algorithm = MATCHING_ALGORITHM_FUZZY; + } } } else if (strcasecmp(option, "require-match") == 0) { bool val = parse_bool(filename, lineno, value, &err); @@ -983,6 +993,24 @@ enum cursor_style parse_cursor_style(const char *filename, size_t lineno, const return 0; } +enum matching_algorithm parse_matching_algorithm(const char *filename, size_t lineno, const char *str, bool *err) +{ + if(strcasecmp(str, "normal") == 0) { + return MATCHING_ALGORITHM_NORMAL; + } + if(strcasecmp(str, "fuzzy") == 0) { + return MATCHING_ALGORITHM_FUZZY; + } + if(strcasecmp(str, "prefix") == 0) { + return MATCHING_ALGORITHM_PREFIX; + } + PARSE_ERROR(filename, lineno, "Invalid matching algorithm \"%s\".\n", str); + if (err) { + *err = true; + } + return 0; +} + struct color parse_color(const char *filename, size_t lineno, const char *str, bool *err) { struct color color = hex_to_color(str); diff --git a/src/desktop_vec.c b/src/desktop_vec.c index c9a0b86..1fd0b41 100644 --- a/src/desktop_vec.c +++ b/src/desktop_vec.c @@ -1,7 +1,7 @@ #include #include #include "desktop_vec.h" -#include "fuzzy_match.h" +#include "matching.h" #include "log.h" #include "string_vec.h" #include "unicode.h" @@ -150,31 +150,20 @@ struct desktop_entry *desktop_vec_find_sorted(struct desktop_vec *restrict vec, struct string_ref_vec desktop_vec_filter( const struct desktop_vec *restrict vec, const char *restrict substr, - bool fuzzy) + enum matching_algorithm algorithm) { struct string_ref_vec filt = string_ref_vec_create(); for (size_t i = 0; i < vec->count; i++) { int32_t search_score; - if (fuzzy) { - search_score = fuzzy_match_words(substr, vec->buf[i].name); - } else { - search_score = fuzzy_match_simple_words(substr, vec->buf[i].name); - } + search_score = match_words(algorithm, substr, vec->buf[i].name); if (search_score != INT32_MIN) { string_ref_vec_add(&filt, vec->buf[i].name); - /* - * Store the position of the match in the string as - * its search_score, for later sorting. - */ + /* Store the score of the match for later sorting. */ 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. */ - if (fuzzy) { - search_score = fuzzy_match_words(substr, vec->buf[i].keywords); - } else { - search_score = fuzzy_match_simple_words(substr, vec->buf[i].keywords); - } + search_score = match_words(algorithm, substr, vec->buf[i].keywords); if (search_score != INT32_MIN) { string_ref_vec_add(&filt, vec->buf[i].name); /* diff --git a/src/desktop_vec.h b/src/desktop_vec.h index f8d0b79..cdc0d6c 100644 --- a/src/desktop_vec.h +++ b/src/desktop_vec.h @@ -5,6 +5,7 @@ #include #include #include +#include "matching.h" struct desktop_entry { char *id; @@ -37,7 +38,7 @@ struct desktop_entry *desktop_vec_find_sorted(struct desktop_vec *restrict vec, struct string_ref_vec desktop_vec_filter( const struct desktop_vec *restrict vec, const char *restrict substr, - bool fuzzy); + enum matching_algorithm algorithm); 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 deleted file mode 100644 index e9f1dcb..0000000 --- a/src/fuzzy_match.c +++ /dev/null @@ -1,238 +0,0 @@ -#include -#include -#include -#include -#include - -#include "fuzzy_match.h" -#include "unicode.h" -#include "xmalloc.h" - -#undef MAX -#define MAX(a, b) ((a) > (b) ? (a) : (b)) - -static int32_t compute_score( - int32_t jump, - bool first_char, - const char *restrict match); - -static int32_t fuzzy_match_recurse( - const char *restrict pattern, - const char *restrict str, - int32_t score, - bool first_match_only, - bool first_char); - -/* - * Split patterns into words, and perform simple matching against str for each. - * Returns the sum of substring distances from the start of str. - * If a word is not found, returns INT32_MIN. - */ -int32_t fuzzy_match_simple_words(const char *restrict patterns, const char *restrict str) -{ - int32_t score = 0; - char *saveptr = NULL; - char *tmp = utf8_normalize(patterns); - char *pattern = strtok_r(tmp, " ", &saveptr); - while (pattern != NULL) { - char *c = utf8_strcasestr(str, pattern); - if (c == NULL) { - score = INT32_MIN; - break; - } else { - score += str - c; - } - pattern = strtok_r(NULL, " ", &saveptr); - } - free(tmp); - return score; -} - - -/* - * Split patterns into words, and return the sum of fuzzy_match(word, str). - * If a word is not found, returns INT32_MIN. - */ -int32_t fuzzy_match_words(const char *restrict patterns, const char *restrict str) -{ - int32_t score = 0; - char *saveptr = NULL; - char *tmp = utf8_normalize(patterns); - char *pattern = strtok_r(tmp, " ", &saveptr); - while (pattern != NULL) { - int32_t word_score = fuzzy_match(pattern, str); - if (word_score == INT32_MIN) { - score = INT32_MIN; - break; - } else { - score += word_score; - } - pattern = strtok_r(NULL, " ", &saveptr); - } - free(tmp); - return score; -} - -/* - * Returns score if each character in pattern is found sequentially within str. - * Returns INT32_MIN otherwise. - */ -int32_t fuzzy_match(const char *restrict pattern, const char *restrict str) -{ - const int unmatched_letter_penalty = -1; - const size_t slen = utf8_strlen(str); - const size_t plen = utf8_strlen(pattern); - int32_t score = 0; - - if (*pattern == '\0') { - return score; - } - if (slen < plen) { - return INT32_MIN; - } - - /* We can already penalise any unused letters. */ - score += unmatched_letter_penalty * (int32_t)(slen - plen); - - /* - * If the string is more than 100 characters, just find the first fuzzy - * match rather than the best. - * - * This is required as the number of possible matches (for patterns and - * strings all consisting of one letter) scales something like: - * - * slen! / (plen! (slen - plen)!) ~ slen^plen for plen << slen - * - * This quickly grinds everything to a halt. 100 is chosen fairly - * arbitrarily from the following logic: - * - * - e is the most common character in English, at around 13% of - * letters. Depending on the context, let's say this be up to 20%. - * - 100 * 0.20 = 20 repeats of the same character. - * - In the worst case here, 20! / (10! 10!) ~200,000 possible matches, - * which is "slow but not frozen" for my machine. - * - * In reality, this worst case shouldn't be hit, and finding the "best" - * fuzzy match in lines of text > 100 characters isn't really in scope - * for a dmenu clone. - */ - bool first_match_only = slen > 100; - - /* Perform the match. */ - score = fuzzy_match_recurse(pattern, str, score, first_match_only, true); - - return score; -} - -/* - * Recursively match the whole of pattern against str. - * The score parameter is the score of the previously matched character. - * - * This reaches a maximum recursion depth of strlen(pattern) + 1. However, the - * stack usage is small (the maximum I've seen on x86_64 is 144 bytes with - * gcc -O3), so this shouldn't matter unless pattern contains thousands of - * characters. - */ -int32_t fuzzy_match_recurse( - const char *restrict pattern, - const char *restrict str, - int32_t score, - bool first_match_only, - bool first_char) -{ - if (*pattern == '\0') { - /* We've matched the full pattern. */ - return score; - } - - const char *match = str; - uint32_t search = utf8_to_utf32(pattern); - - int32_t best_score = INT32_MIN; - - /* - * Find all occurrences of the next pattern character in str, and - * recurse on them. - */ - while ((match = utf8_strcasechr(match, search)) != NULL) { - int32_t jump = 0; - for (const char *tmp = str; tmp != match; tmp = utf8_next_char(tmp)) { - jump++; - } - int32_t subscore = fuzzy_match_recurse( - utf8_next_char(pattern), - utf8_next_char(match), - compute_score(jump, first_char, match), - first_match_only, - false); - best_score = MAX(best_score, subscore); - match = utf8_next_char(match); - - if (first_match_only) { - break; - } - } - - if (best_score == INT32_MIN) { - /* We couldn't match the rest of the pattern. */ - return INT32_MIN; - } else { - return score + best_score; - } -} - -/* - * Calculate the score for a single matching letter. - * The scoring system is taken from fts_fuzzy_match v0.2.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 (already accounted for). - */ -int32_t compute_score(int32_t jump, bool first_char, const char *restrict match) -{ - const int adjacency_bonus = 15; - const int separator_bonus = 30; - const int camel_bonus = 30; - const int first_letter_bonus = 15; - - const int leading_letter_penalty = -5; - const int max_leading_letter_penalty = -15; - - int32_t score = 0; - - const uint32_t cur = utf8_to_utf32(match); - - /* Apply bonuses. */ - if (!first_char && jump == 0) { - score += adjacency_bonus; - } - if (!first_char || jump > 0) { - const uint32_t prev = utf8_to_utf32(utf8_prev_char(match)); - if (utf32_isupper(cur) && utf32_islower(prev)) { - score += camel_bonus; - } - if (utf32_isalnum(cur) && !utf32_isalnum(prev)) { - score += separator_bonus; - } - } - if (first_char && jump == 0) { - /* Match at start of string gets separator bonus. */ - score += first_letter_bonus; - } - - /* Apply penalties. */ - if (first_char) { - score += MAX(leading_letter_penalty * jump, - max_leading_letter_penalty); - } - - return score; -} diff --git a/src/fuzzy_match.h b/src/fuzzy_match.h deleted file mode 100644 index d427bc6..0000000 --- a/src/fuzzy_match.h +++ /dev/null @@ -1,10 +0,0 @@ -#ifndef FUZZY_MATCH_H -#define FUZZY_MATCH_H - -#include - -int32_t fuzzy_match_simple_words(const char *restrict patterns, const char *restrict str); -int32_t fuzzy_match_words(const char *restrict patterns, const char *restrict str); -int32_t fuzzy_match(const char *restrict pattern, const char *restrict str); - -#endif /* FUZZY_MATCH_H */ diff --git a/src/input.c b/src/input.c index 1049fa9..ad89dbd 100644 --- a/src/input.c +++ b/src/input.c @@ -148,12 +148,12 @@ void add_character(struct tofi *tofi, xkb_keycode_t keycode) entry->input_utf8_length += len; if (entry->drun) { - struct string_ref_vec results = desktop_vec_filter(&entry->apps, entry->input_utf8, tofi->fuzzy_match); + struct string_ref_vec results = desktop_vec_filter(&entry->apps, entry->input_utf8, tofi->matching_algorithm); string_ref_vec_destroy(&entry->results); entry->results = results; } else { struct string_ref_vec tmp = entry->results; - entry->results = string_ref_vec_filter(&entry->results, entry->input_utf8, tofi->fuzzy_match); + entry->results = string_ref_vec_filter(&entry->results, entry->input_utf8, tofi->matching_algorithm); string_ref_vec_destroy(&tmp); } @@ -186,9 +186,9 @@ void input_refresh_results(struct tofi *tofi) entry->input_utf8_length = bytes_written; string_ref_vec_destroy(&entry->results); if (entry->drun) { - entry->results = desktop_vec_filter(&entry->apps, entry->input_utf8, tofi->fuzzy_match); + entry->results = desktop_vec_filter(&entry->apps, entry->input_utf8, tofi->matching_algorithm); } else { - entry->results = string_ref_vec_filter(&entry->commands, entry->input_utf8, tofi->fuzzy_match); + entry->results = string_ref_vec_filter(&entry->commands, entry->input_utf8, tofi->matching_algorithm); } reset_selection(tofi); diff --git a/src/main.c b/src/main.c index a59ac78..76df63d 100644 --- a/src/main.c +++ b/src/main.c @@ -834,7 +834,6 @@ static void usage(bool err) " --output Name of output to display window on.\n" " --anchor Location on screen to anchor window.\n" " --horizontal List results horizontally.\n" -" --fuzzy-match Use fuzzy matching for searching.\n" "\n" "All options listed in \"man 5 tofi\" are also accpted in the form \"--key=value\".\n" ); @@ -912,6 +911,7 @@ const struct option long_options[] = { {"history", required_argument, NULL, 0}, {"history-file", required_argument, NULL, 0}, {"fuzzy-match", required_argument, NULL, 0}, + {"matching-algorithm", required_argument, NULL, 0}, {"require-match", required_argument, NULL, 0}, {"auto-accept-single", required_argument, NULL, 0}, {"hide-input", required_argument, NULL, 0}, diff --git a/src/matching.c b/src/matching.c new file mode 100644 index 0000000..b0d184f --- /dev/null +++ b/src/matching.c @@ -0,0 +1,301 @@ +#include +#include +#include +#include +#include + +#include "matching.h" +#include "unicode.h" +#include "xmalloc.h" + +#undef MAX +#define MAX(a, b) ((a) > (b) ? (a) : (b)) + +static int32_t simple_match_words( + const char *restrict patterns, + const char *restrict str); + +static int32_t prefix_match_words( + const char *restrict patterns, + const char *restrict str); + +static int32_t fuzzy_match_words( + const char *restrict patterns, + const char *restrict str); + +static int32_t fuzzy_match( + const char *restrict pattern, + const char *restrict str); + +static int32_t fuzzy_match_recurse( + const char *restrict pattern, + const char *restrict str, + int32_t score, + bool first_match_only, + bool first_char); + +static int32_t compute_score( + int32_t jump, + bool first_char, + const char *restrict match); + +/* + * Select the appropriate algorithm, and return its score. + * Each algorithm returns larger scores for better matches, + * and returns INT32_MIN if a word is not found. + */ +int32_t match_words( + enum matching_algorithm algorithm, + const char *restrict patterns, + const char *restrict str) +{ + switch (algorithm) { + case MATCHING_ALGORITHM_NORMAL: + return simple_match_words(patterns, str); + case MATCHING_ALGORITHM_PREFIX: + return prefix_match_words(patterns, str); + case MATCHING_ALGORITHM_FUZZY: + return fuzzy_match_words(patterns, str); + default: + return INT32_MIN; + } +} + +/* + * Split patterns into words, and perform simple matching against str for each. + * Returns the negative sum of substring distances from the start of str. + * If a word is not found, returns INT32_MIN. + */ +int32_t simple_match_words(const char *restrict patterns, const char *restrict str) +{ + int32_t score = 0; + char *saveptr = NULL; + char *tmp = utf8_normalize(patterns); + char *pattern = strtok_r(tmp, " ", &saveptr); + while (pattern != NULL) { + char *c = utf8_strcasestr(str, pattern); + if (c == NULL) { + score = INT32_MIN; + break; + } else { + score -= c - str; + } + pattern = strtok_r(NULL, " ", &saveptr); + } + free(tmp); + return score; +} + +/* + * Split patterns into words, and perform prefix matching against str for each. + * Returns the negative sum of remaining string suffix lengths. + * If a word is not found, returns INT32_MIN. + */ +int32_t prefix_match_words(const char *restrict patterns, const char *restrict str) +{ + int32_t score = 0; + char *saveptr = NULL; + char *tmp = utf8_normalize(patterns); + char *pattern = strtok_r(tmp, " ", &saveptr); + while (pattern != NULL) { + char *c = utf8_strcasestr(str, pattern); + if (c != str) { + score = INT32_MIN; + break; + } else { + score -= utf8_strlen(str) - utf8_strlen(pattern); + } + pattern = strtok_r(NULL, " ", &saveptr); + } + free(tmp); + return score; +} + + +/* + * Split patterns into words, and return the sum of fuzzy_match(word, str). + * If a word is not found, returns INT32_MIN. + */ +int32_t fuzzy_match_words(const char *restrict patterns, const char *restrict str) +{ + int32_t score = 0; + char *saveptr = NULL; + char *tmp = utf8_normalize(patterns); + char *pattern = strtok_r(tmp, " ", &saveptr); + while (pattern != NULL) { + int32_t word_score = fuzzy_match(pattern, str); + if (word_score == INT32_MIN) { + score = INT32_MIN; + break; + } else { + score += word_score; + } + pattern = strtok_r(NULL, " ", &saveptr); + } + free(tmp); + return score; +} + +/* + * Returns score if each character in pattern is found sequentially within str. + * Returns INT32_MIN otherwise. + */ +int32_t fuzzy_match(const char *restrict pattern, const char *restrict str) +{ + const int unmatched_letter_penalty = -1; + const size_t slen = utf8_strlen(str); + const size_t plen = utf8_strlen(pattern); + int32_t score = 0; + + if (*pattern == '\0') { + return score; + } + if (slen < plen) { + return INT32_MIN; + } + + /* We can already penalise any unused letters. */ + score += unmatched_letter_penalty * (int32_t)(slen - plen); + + /* + * If the string is more than 100 characters, just find the first fuzzy + * match rather than the best. + * + * This is required as the number of possible matches (for patterns and + * strings all consisting of one letter) scales something like: + * + * slen! / (plen! (slen - plen)!) ~ slen^plen for plen << slen + * + * This quickly grinds everything to a halt. 100 is chosen fairly + * arbitrarily from the following logic: + * + * - e is the most common character in English, at around 13% of + * letters. Depending on the context, let's say this be up to 20%. + * - 100 * 0.20 = 20 repeats of the same character. + * - In the worst case here, 20! / (10! 10!) ~200,000 possible matches, + * which is "slow but not frozen" for my machine. + * + * In reality, this worst case shouldn't be hit, and finding the "best" + * fuzzy match in lines of text > 100 characters isn't really in scope + * for a dmenu clone. + */ + bool first_match_only = slen > 100; + + /* Perform the match. */ + score = fuzzy_match_recurse(pattern, str, score, first_match_only, true); + + return score; +} + +/* + * Recursively match the whole of pattern against str. + * The score parameter is the score of the previously matched character. + * + * This reaches a maximum recursion depth of strlen(pattern) + 1. However, the + * stack usage is small (the maximum I've seen on x86_64 is 144 bytes with + * gcc -O3), so this shouldn't matter unless pattern contains thousands of + * characters. + */ +int32_t fuzzy_match_recurse( + const char *restrict pattern, + const char *restrict str, + int32_t score, + bool first_match_only, + bool first_char) +{ + if (*pattern == '\0') { + /* We've matched the full pattern. */ + return score; + } + + const char *match = str; + uint32_t search = utf8_to_utf32(pattern); + + int32_t best_score = INT32_MIN; + + /* + * Find all occurrences of the next pattern character in str, and + * recurse on them. + */ + while ((match = utf8_strcasechr(match, search)) != NULL) { + int32_t jump = 0; + for (const char *tmp = str; tmp != match; tmp = utf8_next_char(tmp)) { + jump++; + } + int32_t subscore = fuzzy_match_recurse( + utf8_next_char(pattern), + utf8_next_char(match), + compute_score(jump, first_char, match), + first_match_only, + false); + best_score = MAX(best_score, subscore); + match = utf8_next_char(match); + + if (first_match_only) { + break; + } + } + + if (best_score == INT32_MIN) { + /* We couldn't match the rest of the pattern. */ + return INT32_MIN; + } else { + return score + best_score; + } +} + +/* + * Calculate the score for a single matching letter. + * The scoring system is taken from fts_fuzzy_match v0.2.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 (already accounted for). + */ +int32_t compute_score(int32_t jump, bool first_char, const char *restrict match) +{ + const int adjacency_bonus = 15; + const int separator_bonus = 30; + const int camel_bonus = 30; + const int first_letter_bonus = 15; + + const int leading_letter_penalty = -5; + const int max_leading_letter_penalty = -15; + + int32_t score = 0; + + const uint32_t cur = utf8_to_utf32(match); + + /* Apply bonuses. */ + if (!first_char && jump == 0) { + score += adjacency_bonus; + } + if (!first_char || jump > 0) { + const uint32_t prev = utf8_to_utf32(utf8_prev_char(match)); + if (utf32_isupper(cur) && utf32_islower(prev)) { + score += camel_bonus; + } + if (utf32_isalnum(cur) && !utf32_isalnum(prev)) { + score += separator_bonus; + } + } + if (first_char && jump == 0) { + /* Match at start of string gets separator bonus. */ + score += first_letter_bonus; + } + + /* Apply penalties. */ + if (first_char) { + score += MAX(leading_letter_penalty * jump, + max_leading_letter_penalty); + } + + return score; +} diff --git a/src/matching.h b/src/matching.h new file mode 100644 index 0000000..f619804 --- /dev/null +++ b/src/matching.h @@ -0,0 +1,14 @@ +#ifndef MATCHING_H +#define MATCHING_H + +#include + +enum matching_algorithm { + MATCHING_ALGORITHM_NORMAL, + MATCHING_ALGORITHM_PREFIX, + MATCHING_ALGORITHM_FUZZY +}; + +int32_t match_words(enum matching_algorithm algorithm, const char *restrict patterns, const char *restrict str); + +#endif /* MATCHING_H */ diff --git a/src/string_vec.c b/src/string_vec.c index 039d191..7a8493f 100644 --- a/src/string_vec.c +++ b/src/string_vec.c @@ -5,8 +5,8 @@ #include #include #include -#include "fuzzy_match.h" #include "history.h" +#include "matching.h" #include "string_vec.h" #include "unicode.h" #include "xmalloc.h" @@ -181,7 +181,7 @@ struct scored_string_ref *string_ref_vec_find_sorted(struct string_ref_vec *rest struct string_ref_vec string_ref_vec_filter( const struct string_ref_vec *restrict vec, const char *restrict substr, - bool fuzzy) + enum matching_algorithm algorithm) { if (substr[0] == '\0') { return string_ref_vec_copy(vec); @@ -189,11 +189,7 @@ struct string_ref_vec string_ref_vec_filter( struct string_ref_vec filt = string_ref_vec_create(); for (size_t i = 0; i < vec->count; i++) { int32_t search_score; - if (fuzzy) { - search_score = fuzzy_match_words(substr, vec->buf[i].string); - } else { - search_score = fuzzy_match_simple_words(substr, vec->buf[i].string); - } + search_score = match_words(algorithm, substr, vec->buf[i].string); if (search_score != INT32_MIN) { string_ref_vec_add(&filt, vec->buf[i].string); filt.buf[filt.count - 1].search_score = search_score; diff --git a/src/string_vec.h b/src/string_vec.h index 6f54d56..4d77ad3 100644 --- a/src/string_vec.h +++ b/src/string_vec.h @@ -6,6 +6,7 @@ #include #include #include "history.h" +#include "matching.h" struct scored_string { char *string; @@ -73,7 +74,7 @@ struct scored_string_ref *string_ref_vec_find_sorted(struct string_ref_vec *rest struct string_ref_vec string_ref_vec_filter( const struct string_ref_vec *restrict vec, const char *restrict substr, - bool fuzzy); + enum matching_algorithm algorithm); [[nodiscard("memory leaked")]] struct string_ref_vec string_ref_vec_from_buffer(char *buffer); diff --git a/src/tofi.h b/src/tofi.h index 571eab8..048f9c9 100644 --- a/src/tofi.h +++ b/src/tofi.h @@ -8,6 +8,7 @@ #include "clipboard.h" #include "color.h" #include "entry.h" +#include "matching.h" #include "surface.h" #include "wlr-layer-shell-unstable-v1.h" #include "fractional-scale-v1.h" @@ -90,6 +91,7 @@ struct tofi { /* Options */ uint32_t anchor; + enum matching_algorithm matching_algorithm; bool ascii_input; bool hide_cursor; bool use_history; @@ -97,7 +99,6 @@ struct tofi { bool late_keyboard_init; bool drun_launch; bool drun_print_exec; - bool fuzzy_match; bool require_match; bool auto_accept_single; bool multiple_instance; -- cgit v1.2.3