fzy
terminal fuzzy finder picker
git clone https://9o.is/git/fzy.git
commit 6aca96f448681507fc3c707fdbf55b7a8b096104 parent b3e59a17ec5967b4d23825415c415d76bfad0e5f Author: John Hawthorn <john.hawthorn@gmail.com> Date: Sat, 21 May 2016 14:56:03 -0700 Move sources into src directory Diffstat:
| M | Makefile | | | 10 | +++++----- |
| D | fzy.c | | | 290 | ------------------------------------------------------------------------------- |
| D | match.c | | | 183 | ------------------------------------------------------------------------------- |
| R | choices.c -> src/choices.c | | | 0 | |
| R | choices.h -> src/choices.h | | | 0 | |
| R | config.def.h -> src/config.def.h | | | 0 | |
| A | src/fzy.c | | | 290 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| R | fzytest.c -> src/fzytest.c | | | 0 | |
| A | src/match.c | | | 183 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| R | match.h -> src/match.h | | | 0 | |
| R | tty.c -> src/tty.c | | | 0 | |
| R | tty.h -> src/tty.h | | | 0 |
12 files changed, 478 insertions(+), 478 deletions(-)
diff --git a/Makefile b/Makefile @@ -11,8 +11,8 @@ INSTALL=install INSTALL_PROGRAM=$(INSTALL) INSTALL_DATA=${INSTALL} -m 644 -OBJECTS=fzy.o match.o tty.o choices.o -TESTOBJECTS=fzytest.o match.o choices.o +OBJECTS=src/fzy.o src/match.o src/tty.o src/choices.o +TESTOBJECTS=src/fzytest.o src/match.o src/choices.o all: fzy @@ -30,7 +30,7 @@ fzy: $(OBJECTS) $(CC) $(CPPFLAGS) $(CFLAGS) -c -o $@ $< config.h: - cp config.def.h config.h + cp src/config.def.h config.h install: fzy mkdir -p $(DESTDIR)$(BINDIR) @@ -41,9 +41,9 @@ install: fzy chmod 644 ${DESTDIR}${MANDIR}/man1/fzy.1 fmt: - clang-format -i *.c *.h + clang-format -i src/*.c src/*.h clean: - rm -f fzy fzytest *.o + rm -f fzy fzytest src/*.o .PHONY: test check all clean install fmt diff --git a/fzy.c b/fzy.c @@ -1,290 +0,0 @@ -#include <stdio.h> -#include <string.h> -#include <stdlib.h> -#include <ctype.h> -#include <getopt.h> -#include <limits.h> - -#include "match.h" -#include "tty.h" -#include "choices.h" - -#include "config.h" - -static int flag_show_scores = 0; - -static size_t num_lines = 10; -static size_t scrolloff = 1; - -static const char *prompt = "> "; - -#define SEARCH_SIZE_MAX 4096 -static char search[SEARCH_SIZE_MAX + 1] = {0}; - -static void clear(tty_t *tty) { - tty_setcol(tty, 0); - size_t line = 0; - while (line++ < num_lines) { - tty_newline(tty); - } - tty_clearline(tty); - tty_moveup(tty, line - 1); - tty_flush(tty); -} - -static void draw_match(tty_t *tty, const char *choice, int selected) { - int n = strlen(search); - size_t positions[n + 1]; - for (int i = 0; i < n + 1; i++) - positions[i] = -1; - - double score = match_positions(search, choice, &positions[0]); - - size_t maxwidth = tty_getwidth(tty); - - if (flag_show_scores) - tty_printf(tty, "(%5.2f) ", score); - - if (selected) - tty_setinvert(tty); - - for (size_t i = 0, p = 0; choice[i] != '\0'; i++) { - if (i + 1 < maxwidth) { - if (positions[p] == i) { - tty_setfg(tty, TTY_COLOR_HIGHLIGHT); - p++; - } else { - tty_setfg(tty, TTY_COLOR_NORMAL); - } - tty_printf(tty, "%c", choice[i]); - } else { - tty_printf(tty, "$"); - break; - } - } - tty_setnormal(tty); -} - -static void draw(tty_t *tty, choices_t *choices) { - size_t start = 0; - size_t current_selection = choices->selection; - if (current_selection + scrolloff >= num_lines) { - start = current_selection + scrolloff - num_lines + 1; - if (start + num_lines >= choices_available(choices)) { - start = choices_available(choices) - num_lines; - } - } - tty_setcol(tty, 0); - tty_printf(tty, "%s%s", prompt, search); - tty_clearline(tty); - for (size_t i = start; i < start + num_lines; i++) { - tty_printf(tty, "\n"); - tty_clearline(tty); - const char *choice = choices_get(choices, i); - if (choice) { - draw_match(tty, choice, i == choices->selection); - } - } - tty_moveup(tty, num_lines); - tty_setcol(tty, strlen(prompt) + strlen(search)); - tty_flush(tty); -} - -static void emit(choices_t *choices) { - const char *selection = choices_get(choices, choices->selection); - if (selection) { - /* output the selected result */ - printf("%s\n", selection); - } else { - /* No match, output the query instead */ - printf("%s\n", search); - } -} - -#define KEY_CTRL(key) ((key) - ('@')) -#define KEY_DEL 127 -#define KEY_ESC 27 - -static void run(tty_t *tty, choices_t *choices) { - choices_search(choices, search); - char ch; - do { - draw(tty, choices); - ch = tty_getchar(tty); - size_t search_size = strlen(search); - if (isprint(ch)) { - if (search_size < SEARCH_SIZE_MAX) { - search[search_size++] = ch; - search[search_size] = '\0'; - choices_search(choices, search); - } - } else if (ch == KEY_DEL || ch == KEY_CTRL('H')) { /* DEL || Backspace (C-H) */ - if (search_size) - search[--search_size] = '\0'; - choices_search(choices, search); - } else if (ch == KEY_CTRL('U')) { /* C-U */ - search_size = 0; - search[0] = '\0'; - choices_search(choices, search); - } else if (ch == KEY_CTRL('W')) { /* C-W */ - if (search_size) - search[--search_size] = '\0'; - while (search_size && !isspace(search[--search_size])) - search[search_size] = '\0'; - choices_search(choices, search); - } else if (ch == KEY_CTRL('N')) { /* C-N */ - choices_next(choices); - } else if (ch == KEY_CTRL('P')) { /* C-P */ - choices_prev(choices); - } else if (ch == KEY_CTRL('I')) { /* TAB (C-I) */ - strncpy(search, choices_get(choices, choices->selection), SEARCH_SIZE_MAX); - choices_search(choices, search); - } else if (ch == KEY_CTRL('C') || ch == KEY_CTRL('D')) { /* ^C || ^D */ - clear(tty); - tty_close(tty); - exit(EXIT_FAILURE); - } else if (ch == KEY_CTRL('M')) { /* CR */ - clear(tty); - - /* ttyout should be flushed before outputting on stdout */ - tty_close(tty); - - emit(choices); - - /* Return to eventually exit successfully */ - return; - } else if (ch == KEY_ESC) { /* ESC */ - ch = tty_getchar(tty); - if (ch == '[' || ch == 'O') { - ch = tty_getchar(tty); - if (ch == 'A') { /* UP ARROW */ - choices_prev(choices); - } else if (ch == 'B') { /* DOWN ARROW */ - choices_next(choices); - } - } - } - } while (1); -} - -static const char *usage_str = - "" - "Usage: fzy [OPTION]...\n" - " -l, --lines=LINES Specify how many lines of results to show (default 10)\n" - " -p, --prompt=PROMPT Input prompt (default '> ')\n" - " -q, --query=QUERY Use QUERY as the initial search string\n" - " -e, --show-matches=QUERY Output the sorted matches of QUERY\n" - " -t, --tty=TTY Specify file to use as TTY device (default /dev/tty)\n" - " -s, --show-scores Show the scores of each match\n" - " -h, --help Display this help and exit\n" - " -v, --version Output version information and exit\n"; - -static void usage(const char *argv0) { - fprintf(stderr, usage_str, argv0); -} - -static struct option longopts[] = {{"show-matches", required_argument, NULL, 'e'}, - {"query", required_argument, NULL, 'q'}, - {"lines", required_argument, NULL, 'l'}, - {"tty", required_argument, NULL, 't'}, - {"prompt", required_argument, NULL, 'p'}, - {"show-scores", no_argument, NULL, 's'}, - {"version", no_argument, NULL, 'v'}, - {"benchmark", optional_argument, NULL, 'b'}, - {"help", no_argument, NULL, 'h'}, - {NULL, 0, NULL, 0}}; - -int main(int argc, char *argv[]) { - int benchmark = 0; - const char *filter = NULL; - const char *tty_filename = "/dev/tty"; - char c; - while ((c = getopt_long(argc, argv, "vhse:q:l:t:p:", longopts, NULL)) != -1) { - switch (c) { - case 'v': - printf("%s " VERSION " (c) 2014 John Hawthorn\n", argv[0]); - exit(EXIT_SUCCESS); - case 's': - flag_show_scores = 1; - break; - case 'q': - strncpy(search, optarg, SEARCH_SIZE_MAX); - break; - case 'e': - filter = optarg; - break; - case 'b': - if (optarg) { - if (sscanf(optarg, "%d", &benchmark) != 1) { - usage(argv[0]); - exit(EXIT_FAILURE); - } - } else { - benchmark = 100; - } - break; - case 't': - tty_filename = optarg; - break; - case 'p': - prompt = optarg; - break; - case 'l': { - int l; - if (!strcmp(optarg, "max")) { - l = INT_MAX; - } else if (sscanf(optarg, "%d", &l) != 1 || l < 3) { - fprintf(stderr, "Invalid format for --lines: %s\n", optarg); - fprintf(stderr, "Must be integer in range 3..\n"); - usage(argv[0]); - exit(EXIT_FAILURE); - } - num_lines = l; - } break; - case 'h': - default: - usage(argv[0]); - exit(EXIT_SUCCESS); - } - } - if (optind != argc) { - usage(argv[0]); - exit(EXIT_FAILURE); - } - - choices_t choices; - choices_init(&choices); - choices_fread(&choices, stdin); - - if (benchmark) { - if (!filter) { - fprintf(stderr, "Must specify -e/--show-matches with --benchmark\n"); - exit(EXIT_FAILURE); - } - for (int i = 0; i < benchmark; i++) - choices_search(&choices, filter); - } else if (filter) { - choices_search(&choices, filter); - for (size_t i = 0; i < choices_available(&choices); i++) { - if (flag_show_scores) - printf("%f\t", choices_getscore(&choices, i)); - printf("%s\n", choices_get(&choices, i)); - } - } else { - /* interactive */ - tty_t tty; - tty_init(&tty, tty_filename); - - if (num_lines > choices.size) - num_lines = choices.size; - - if (num_lines + 1 > tty_getheight(&tty)) - num_lines = tty_getheight(&tty) - 1; - - run(&tty, &choices); - } - - choices_destroy(&choices); - - return 0; -} diff --git a/match.c b/match.c @@ -1,183 +0,0 @@ -#include <ctype.h> -#include <string.h> -#include <strings.h> -#include <stdio.h> -#include <float.h> -#include <math.h> - -#include "match.h" - -#include "config.h" - -char *strcasechr(const char *s, char c) { - const char accept[3] = {c, toupper(c), 0}; - return strpbrk(s, accept); -} - -int has_match(const char *needle, const char *haystack) { - while (*needle) { - char nch = *needle++; - - if (!(haystack = strcasechr(haystack, nch))) { - return 0; - } - haystack++; - } - return 1; -} - -#define max(a, b) (((a) > (b)) ? (a) : (b)) - -#ifdef DEBUG_VERBOSE -/* print one of the internal matrices */ -void mat_print(score_t *mat, char name, const char *needle, const char *haystack) { - int n = strlen(needle); - int m = strlen(haystack); - int i, j; - fprintf(stderr, "%c ", name); - for (j = 0; j < m; j++) { - fprintf(stderr, " %c", haystack[j]); - } - fprintf(stderr, "\n"); - for (i = 0; i < n; i++) { - fprintf(stderr, " %c |", needle[i]); - for (j = 0; j < m; j++) { - score_t val = mat[i * m + j]; - if (val == SCORE_MIN) { - fprintf(stderr, " -\u221E"); - } else { - fprintf(stderr, " %.3f", val); - } - } - fprintf(stderr, "\n"); - } - fprintf(stderr, "\n\n"); -} -#endif - -score_t calculate_score(const char *needle, const char *haystack, size_t *positions) { - if (!*haystack || !*needle) - return SCORE_MIN; - - int n = strlen(needle); - int m = strlen(haystack); - - if (m > 1024) { - /* - * Unreasonably large candidate: return no score - * If it is a valid match it will still be returned, it will - * just be ranked below any reasonably sized candidates - */ - return SCORE_MIN; - } - - score_t match_bonus[m]; - score_t D[n][m], M[n][m]; - - /* - * D[][] Stores the best score for this position ending with a match. - * M[][] Stores the best possible score at this position. - */ - - /* Which positions are beginning of words */ - char last_ch = '\0'; - for (int i = 0; i < m; i++) { - char ch = haystack[i]; - - score_t score = 0; - if (isalnum(ch)) { - if (!last_ch || last_ch == '/') { - score = SCORE_MATCH_SLASH; - } else if (last_ch == '-' || last_ch == '_' || last_ch == ' ' || - (last_ch >= '0' && last_ch <= '9')) { - score = SCORE_MATCH_WORD; - } else if (last_ch >= 'a' && last_ch <= 'z' && ch >= 'A' && ch <= 'Z') { - /* CamelCase */ - score = SCORE_MATCH_CAPITAL; - } else if (last_ch == '.') { - score = SCORE_MATCH_DOT; - } - } - - match_bonus[i] = score; - last_ch = ch; - } - - for (int i = 0; i < n; i++) { - score_t prev_score = SCORE_MIN; - score_t gap_score = i == n - 1 ? SCORE_GAP_TRAILING : SCORE_GAP_INNER; - for (int j = 0; j < m; j++) { - score_t score = SCORE_MIN; - if (tolower(needle[i]) == tolower(haystack[j])) { - if (!i) { - score = (j * SCORE_GAP_LEADING) + match_bonus[j]; - } else if (j) { /* i > 0 && j > 0*/ - score = max( - M[i - 1][j - 1] + match_bonus[j], - - /* consecutive match, doesn't stack with match_bonus */ - D[i - 1][j - 1] + SCORE_MATCH_CONSECUTIVE); - } - } - D[i][j] = score; - M[i][j] = prev_score = max(score, prev_score + gap_score); - } - } - -#ifdef DEBUG_VERBOSE - fprintf(stderr, "\"%s\" =~ \"%s\"\n", needle, haystack); - mat_print(&D[0][0], 'D', needle, haystack); - mat_print(&M[0][0], 'M', needle, haystack); - fprintf(stderr, "\n"); -#endif - - /* backtrace to find the positions of optimal matching */ - if (positions) { - int match_required = 0; - for (int i = n - 1, j = m - 1; i >= 0; i--) { - for (; j >= 0; j--) { - /* - * There may be multiple paths which result in - * the optimal weight. - * - * For simplicity, we will pick the first one - * we encounter, the latest in the candidate - * string. - */ - if (D[i][j] != SCORE_MIN && - (match_required || D[i][j] == M[i][j])) { - /* If this score was determined using - * SCORE_MATCH_CONSECUTIVE, the - * previous character MUST be a match - */ - match_required = - i && j && - M[i][j] == D[i - 1][j - 1] + SCORE_MATCH_CONSECUTIVE; - positions[i] = j--; - break; - } - } - } - } - - return M[n - 1][m - 1]; -} - -score_t match_positions(const char *needle, const char *haystack, size_t *positions) { - if (!*needle) { - return SCORE_MAX; - } else if (!strcasecmp(needle, haystack)) { - if (positions) { - int n = strlen(needle); - for (int i = 0; i < n; i++) - positions[i] = i; - } - return SCORE_MAX; - } else { - return calculate_score(needle, haystack, positions); - } -} - -score_t match(const char *needle, const char *haystack) { - return match_positions(needle, haystack, NULL); -} diff --git a/choices.c b/src/choices.c diff --git a/choices.h b/src/choices.h diff --git a/config.def.h b/src/config.def.h diff --git a/src/fzy.c b/src/fzy.c @@ -0,0 +1,290 @@ +#include <stdio.h> +#include <string.h> +#include <stdlib.h> +#include <ctype.h> +#include <getopt.h> +#include <limits.h> + +#include "match.h" +#include "tty.h" +#include "choices.h" + +#include "../config.h" + +static int flag_show_scores = 0; + +static size_t num_lines = 10; +static size_t scrolloff = 1; + +static const char *prompt = "> "; + +#define SEARCH_SIZE_MAX 4096 +static char search[SEARCH_SIZE_MAX + 1] = {0}; + +static void clear(tty_t *tty) { + tty_setcol(tty, 0); + size_t line = 0; + while (line++ < num_lines) { + tty_newline(tty); + } + tty_clearline(tty); + tty_moveup(tty, line - 1); + tty_flush(tty); +} + +static void draw_match(tty_t *tty, const char *choice, int selected) { + int n = strlen(search); + size_t positions[n + 1]; + for (int i = 0; i < n + 1; i++) + positions[i] = -1; + + double score = match_positions(search, choice, &positions[0]); + + size_t maxwidth = tty_getwidth(tty); + + if (flag_show_scores) + tty_printf(tty, "(%5.2f) ", score); + + if (selected) + tty_setinvert(tty); + + for (size_t i = 0, p = 0; choice[i] != '\0'; i++) { + if (i + 1 < maxwidth) { + if (positions[p] == i) { + tty_setfg(tty, TTY_COLOR_HIGHLIGHT); + p++; + } else { + tty_setfg(tty, TTY_COLOR_NORMAL); + } + tty_printf(tty, "%c", choice[i]); + } else { + tty_printf(tty, "$"); + break; + } + } + tty_setnormal(tty); +} + +static void draw(tty_t *tty, choices_t *choices) { + size_t start = 0; + size_t current_selection = choices->selection; + if (current_selection + scrolloff >= num_lines) { + start = current_selection + scrolloff - num_lines + 1; + if (start + num_lines >= choices_available(choices)) { + start = choices_available(choices) - num_lines; + } + } + tty_setcol(tty, 0); + tty_printf(tty, "%s%s", prompt, search); + tty_clearline(tty); + for (size_t i = start; i < start + num_lines; i++) { + tty_printf(tty, "\n"); + tty_clearline(tty); + const char *choice = choices_get(choices, i); + if (choice) { + draw_match(tty, choice, i == choices->selection); + } + } + tty_moveup(tty, num_lines); + tty_setcol(tty, strlen(prompt) + strlen(search)); + tty_flush(tty); +} + +static void emit(choices_t *choices) { + const char *selection = choices_get(choices, choices->selection); + if (selection) { + /* output the selected result */ + printf("%s\n", selection); + } else { + /* No match, output the query instead */ + printf("%s\n", search); + } +} + +#define KEY_CTRL(key) ((key) - ('@')) +#define KEY_DEL 127 +#define KEY_ESC 27 + +static void run(tty_t *tty, choices_t *choices) { + choices_search(choices, search); + char ch; + do { + draw(tty, choices); + ch = tty_getchar(tty); + size_t search_size = strlen(search); + if (isprint(ch)) { + if (search_size < SEARCH_SIZE_MAX) { + search[search_size++] = ch; + search[search_size] = '\0'; + choices_search(choices, search); + } + } else if (ch == KEY_DEL || ch == KEY_CTRL('H')) { /* DEL || Backspace (C-H) */ + if (search_size) + search[--search_size] = '\0'; + choices_search(choices, search); + } else if (ch == KEY_CTRL('U')) { /* C-U */ + search_size = 0; + search[0] = '\0'; + choices_search(choices, search); + } else if (ch == KEY_CTRL('W')) { /* C-W */ + if (search_size) + search[--search_size] = '\0'; + while (search_size && !isspace(search[--search_size])) + search[search_size] = '\0'; + choices_search(choices, search); + } else if (ch == KEY_CTRL('N')) { /* C-N */ + choices_next(choices); + } else if (ch == KEY_CTRL('P')) { /* C-P */ + choices_prev(choices); + } else if (ch == KEY_CTRL('I')) { /* TAB (C-I) */ + strncpy(search, choices_get(choices, choices->selection), SEARCH_SIZE_MAX); + choices_search(choices, search); + } else if (ch == KEY_CTRL('C') || ch == KEY_CTRL('D')) { /* ^C || ^D */ + clear(tty); + tty_close(tty); + exit(EXIT_FAILURE); + } else if (ch == KEY_CTRL('M')) { /* CR */ + clear(tty); + + /* ttyout should be flushed before outputting on stdout */ + tty_close(tty); + + emit(choices); + + /* Return to eventually exit successfully */ + return; + } else if (ch == KEY_ESC) { /* ESC */ + ch = tty_getchar(tty); + if (ch == '[' || ch == 'O') { + ch = tty_getchar(tty); + if (ch == 'A') { /* UP ARROW */ + choices_prev(choices); + } else if (ch == 'B') { /* DOWN ARROW */ + choices_next(choices); + } + } + } + } while (1); +} + +static const char *usage_str = + "" + "Usage: fzy [OPTION]...\n" + " -l, --lines=LINES Specify how many lines of results to show (default 10)\n" + " -p, --prompt=PROMPT Input prompt (default '> ')\n" + " -q, --query=QUERY Use QUERY as the initial search string\n" + " -e, --show-matches=QUERY Output the sorted matches of QUERY\n" + " -t, --tty=TTY Specify file to use as TTY device (default /dev/tty)\n" + " -s, --show-scores Show the scores of each match\n" + " -h, --help Display this help and exit\n" + " -v, --version Output version information and exit\n"; + +static void usage(const char *argv0) { + fprintf(stderr, usage_str, argv0); +} + +static struct option longopts[] = {{"show-matches", required_argument, NULL, 'e'}, + {"query", required_argument, NULL, 'q'}, + {"lines", required_argument, NULL, 'l'}, + {"tty", required_argument, NULL, 't'}, + {"prompt", required_argument, NULL, 'p'}, + {"show-scores", no_argument, NULL, 's'}, + {"version", no_argument, NULL, 'v'}, + {"benchmark", optional_argument, NULL, 'b'}, + {"help", no_argument, NULL, 'h'}, + {NULL, 0, NULL, 0}}; + +int main(int argc, char *argv[]) { + int benchmark = 0; + const char *filter = NULL; + const char *tty_filename = "/dev/tty"; + char c; + while ((c = getopt_long(argc, argv, "vhse:q:l:t:p:", longopts, NULL)) != -1) { + switch (c) { + case 'v': + printf("%s " VERSION " (c) 2014 John Hawthorn\n", argv[0]); + exit(EXIT_SUCCESS); + case 's': + flag_show_scores = 1; + break; + case 'q': + strncpy(search, optarg, SEARCH_SIZE_MAX); + break; + case 'e': + filter = optarg; + break; + case 'b': + if (optarg) { + if (sscanf(optarg, "%d", &benchmark) != 1) { + usage(argv[0]); + exit(EXIT_FAILURE); + } + } else { + benchmark = 100; + } + break; + case 't': + tty_filename = optarg; + break; + case 'p': + prompt = optarg; + break; + case 'l': { + int l; + if (!strcmp(optarg, "max")) { + l = INT_MAX; + } else if (sscanf(optarg, "%d", &l) != 1 || l < 3) { + fprintf(stderr, "Invalid format for --lines: %s\n", optarg); + fprintf(stderr, "Must be integer in range 3..\n"); + usage(argv[0]); + exit(EXIT_FAILURE); + } + num_lines = l; + } break; + case 'h': + default: + usage(argv[0]); + exit(EXIT_SUCCESS); + } + } + if (optind != argc) { + usage(argv[0]); + exit(EXIT_FAILURE); + } + + choices_t choices; + choices_init(&choices); + choices_fread(&choices, stdin); + + if (benchmark) { + if (!filter) { + fprintf(stderr, "Must specify -e/--show-matches with --benchmark\n"); + exit(EXIT_FAILURE); + } + for (int i = 0; i < benchmark; i++) + choices_search(&choices, filter); + } else if (filter) { + choices_search(&choices, filter); + for (size_t i = 0; i < choices_available(&choices); i++) { + if (flag_show_scores) + printf("%f\t", choices_getscore(&choices, i)); + printf("%s\n", choices_get(&choices, i)); + } + } else { + /* interactive */ + tty_t tty; + tty_init(&tty, tty_filename); + + if (num_lines > choices.size) + num_lines = choices.size; + + if (num_lines + 1 > tty_getheight(&tty)) + num_lines = tty_getheight(&tty) - 1; + + run(&tty, &choices); + } + + choices_destroy(&choices); + + return 0; +} diff --git a/fzytest.c b/src/fzytest.c diff --git a/src/match.c b/src/match.c @@ -0,0 +1,183 @@ +#include <ctype.h> +#include <string.h> +#include <strings.h> +#include <stdio.h> +#include <float.h> +#include <math.h> + +#include "match.h" + +#include "../config.h" + +char *strcasechr(const char *s, char c) { + const char accept[3] = {c, toupper(c), 0}; + return strpbrk(s, accept); +} + +int has_match(const char *needle, const char *haystack) { + while (*needle) { + char nch = *needle++; + + if (!(haystack = strcasechr(haystack, nch))) { + return 0; + } + haystack++; + } + return 1; +} + +#define max(a, b) (((a) > (b)) ? (a) : (b)) + +#ifdef DEBUG_VERBOSE +/* print one of the internal matrices */ +void mat_print(score_t *mat, char name, const char *needle, const char *haystack) { + int n = strlen(needle); + int m = strlen(haystack); + int i, j; + fprintf(stderr, "%c ", name); + for (j = 0; j < m; j++) { + fprintf(stderr, " %c", haystack[j]); + } + fprintf(stderr, "\n"); + for (i = 0; i < n; i++) { + fprintf(stderr, " %c |", needle[i]); + for (j = 0; j < m; j++) { + score_t val = mat[i * m + j]; + if (val == SCORE_MIN) { + fprintf(stderr, " -\u221E"); + } else { + fprintf(stderr, " %.3f", val); + } + } + fprintf(stderr, "\n"); + } + fprintf(stderr, "\n\n"); +} +#endif + +score_t calculate_score(const char *needle, const char *haystack, size_t *positions) { + if (!*haystack || !*needle) + return SCORE_MIN; + + int n = strlen(needle); + int m = strlen(haystack); + + if (m > 1024) { + /* + * Unreasonably large candidate: return no score + * If it is a valid match it will still be returned, it will + * just be ranked below any reasonably sized candidates + */ + return SCORE_MIN; + } + + score_t match_bonus[m]; + score_t D[n][m], M[n][m]; + + /* + * D[][] Stores the best score for this position ending with a match. + * M[][] Stores the best possible score at this position. + */ + + /* Which positions are beginning of words */ + char last_ch = '\0'; + for (int i = 0; i < m; i++) { + char ch = haystack[i]; + + score_t score = 0; + if (isalnum(ch)) { + if (!last_ch || last_ch == '/') { + score = SCORE_MATCH_SLASH; + } else if (last_ch == '-' || last_ch == '_' || last_ch == ' ' || + (last_ch >= '0' && last_ch <= '9')) { + score = SCORE_MATCH_WORD; + } else if (last_ch >= 'a' && last_ch <= 'z' && ch >= 'A' && ch <= 'Z') { + /* CamelCase */ + score = SCORE_MATCH_CAPITAL; + } else if (last_ch == '.') { + score = SCORE_MATCH_DOT; + } + } + + match_bonus[i] = score; + last_ch = ch; + } + + for (int i = 0; i < n; i++) { + score_t prev_score = SCORE_MIN; + score_t gap_score = i == n - 1 ? SCORE_GAP_TRAILING : SCORE_GAP_INNER; + for (int j = 0; j < m; j++) { + score_t score = SCORE_MIN; + if (tolower(needle[i]) == tolower(haystack[j])) { + if (!i) { + score = (j * SCORE_GAP_LEADING) + match_bonus[j]; + } else if (j) { /* i > 0 && j > 0*/ + score = max( + M[i - 1][j - 1] + match_bonus[j], + + /* consecutive match, doesn't stack with match_bonus */ + D[i - 1][j - 1] + SCORE_MATCH_CONSECUTIVE); + } + } + D[i][j] = score; + M[i][j] = prev_score = max(score, prev_score + gap_score); + } + } + +#ifdef DEBUG_VERBOSE + fprintf(stderr, "\"%s\" =~ \"%s\"\n", needle, haystack); + mat_print(&D[0][0], 'D', needle, haystack); + mat_print(&M[0][0], 'M', needle, haystack); + fprintf(stderr, "\n"); +#endif + + /* backtrace to find the positions of optimal matching */ + if (positions) { + int match_required = 0; + for (int i = n - 1, j = m - 1; i >= 0; i--) { + for (; j >= 0; j--) { + /* + * There may be multiple paths which result in + * the optimal weight. + * + * For simplicity, we will pick the first one + * we encounter, the latest in the candidate + * string. + */ + if (D[i][j] != SCORE_MIN && + (match_required || D[i][j] == M[i][j])) { + /* If this score was determined using + * SCORE_MATCH_CONSECUTIVE, the + * previous character MUST be a match + */ + match_required = + i && j && + M[i][j] == D[i - 1][j - 1] + SCORE_MATCH_CONSECUTIVE; + positions[i] = j--; + break; + } + } + } + } + + return M[n - 1][m - 1]; +} + +score_t match_positions(const char *needle, const char *haystack, size_t *positions) { + if (!*needle) { + return SCORE_MAX; + } else if (!strcasecmp(needle, haystack)) { + if (positions) { + int n = strlen(needle); + for (int i = 0; i < n; i++) + positions[i] = i; + } + return SCORE_MAX; + } else { + return calculate_score(needle, haystack, positions); + } +} + +score_t match(const char *needle, const char *haystack) { + return match_positions(needle, haystack, NULL); +} diff --git a/match.h b/src/match.h diff --git a/tty.c b/src/tty.c diff --git a/tty.h b/src/tty.h