better fuzzy matching + replace a bunch of space indentation junk

1 files changed, 154 insertions, 125 deletions

diff --git a/main.c b/main.c
index 3ecb921..71c7938 100644
--- a/main.c
+++ b/main.c
@@ -63,20 +63,20 @@ typedef struct {
 	EditMode mode;
 	u32 count;
 
-        /* these unfortunately have to be global so that draw() will know what
+	/* these unfortunately have to be global so that draw() will know what
 	 * to do when a window resizes during input
 	 */
-        Str msg;
-        Str input_line, input_prompt;
-        u32 optc, opti;
-        Str *optv;
+	Str msg;
+	Str input_line, input_prompt;
+	u32 optc, opti;
+	Str *optv;
 	u32 *optvi;
 
-        Str search;
-        int search_dir;
-        u32 search_char;
-        int search_char_dir;
-        int search_char_incl;
+	Str search;
+	int search_dir;
+	u32 search_char;
+	int search_char_dir;
+	int search_char_incl;
 
 	Str homedir;
 } Editor;
@@ -93,126 +93,126 @@ int ed_buf_open(Editor *e, const char *path) {
 		}
 	}
 
-        if (e->bufn == ED_BUF_MAX) return -1;
-        EditBuf b = { 0 };
-        b.arena = arena_init(1L << 30);
-        b.txt = FREELIST_NEW(&e->txt_free, &b.arena);
-        if (path) {
-                b.path = str_dup(paths, &b.arena);
-                b.type = ED_BUF_FILE;
-                txt_load(b.txt, path);
-        } else {
-                b.path = S("*scratch*");
-                b.type = ED_BUF_SCRATCH;
-                txt_load_empty(b.txt);
-        }
-        b.cur = txt_end(b.txt);
-        e->buf[e->bufn] = b;
-        return e->bufn++;
+	if (e->bufn == ED_BUF_MAX) return -1;
+	EditBuf b = { 0 };
+	b.arena = arena_init(1L << 30);
+	b.txt = FREELIST_NEW(&e->txt_free, &b.arena);
+	if (path) {
+		b.path = str_dup(paths, &b.arena);
+		b.type = ED_BUF_FILE;
+		txt_load(b.txt, path);
+	} else {
+		b.path = S("*scratch*");
+		b.type = ED_BUF_SCRATCH;
+		txt_load_empty(b.txt);
+	}
+	b.cur = txt_end(b.txt);
+	e->buf[e->bufn] = b;
+	return e->bufn++;
 }
 
 void ed_buf_free(EditBuf *b) {
-        txt_free(b->txt);
-        arena_free(&b->arena);
+	txt_free(b->txt);
+	arena_free(&b->arena);
 }
 
 void ed_buf_change_path(Editor *e, u32 i, Str s) {
-        EditBuf *eb = &e->buf[i];
-        eb->path = str_dup(s, &eb->arena);
-        eb->type = ED_BUF_FILE;
+	EditBuf *eb = &e->buf[i];
+	eb->path = str_dup(s, &eb->arena);
+	eb->type = ED_BUF_FILE;
 }
 
 void ed_init(Editor *e) {
-        memset(e, 0, sizeof(Editor));
-        e->scratch = arena_init(1L << 30);
-        e->bufi = ed_buf_open(e, NULL);
-        Str s = S("(Scratch buffer, type whatever)");
-        e->buf[e->bufi].cur = txt_insert(e->buf[e->bufi].cur, s.s, s.n);
+	memset(e, 0, sizeof(Editor));
+	e->scratch = arena_init(1L << 30);
+	e->bufi = ed_buf_open(e, NULL);
+	Str s = S("(Scratch buffer, type whatever)");
+	e->buf[e->bufi].cur = txt_insert(e->buf[e->bufi].cur, s.s, s.n);
 }
 
 void ed_fini(Editor *e) {
-        for (u32 i = 0; i < e->bufn; i++) {
-                ed_buf_free(&e->buf[i]);
-        }
-        if (e->search.s) free(e->search.s);
+	for (u32 i = 0; i < e->bufn; i++) {
+		ed_buf_free(&e->buf[i]);
+	}
+	if (e->search.s) free(e->search.s);
 }
 
 u32 ed_buf_close(Editor *e, u32 i) {
-        ed_buf_free(&e->buf[i]);
-        if (i + 1 < e->bufn) {
-                MOVE(&e->buf[i], &e->buf[i+1], e->bufn - (i + 1));
-        }
-        e->bufn--;
-        return i > 0 ? i - 1 : 0;
+	ed_buf_free(&e->buf[i]);
+	if (i + 1 < e->bufn) {
+		MOVE(&e->buf[i], &e->buf[i+1], e->bufn - (i + 1));
+	}
+	e->bufn--;
+	return i > 0 ? i - 1 : 0;
 }
 
 int ed_buf_save(Editor *e, u32 i) {
-        EditBuf *b = &e->buf[i];
-        if (b->type == ED_BUF_FILE) {
-                return txt_save(b->txt, str_to_cstr(b->path, &e->scratch));
-        } else {
-                return 0;
-        }
+	EditBuf *b = &e->buf[i];
+	if (b->type == ED_BUF_FILE) {
+		return txt_save(b->txt, str_to_cstr(b->path, &e->scratch));
+	} else {
+		return 0;
+	}
 }
 
 Str str_printf(Arena *a, const char *fmt, ...) {
-        va_list ap;
-        va_start(ap, fmt);
-        int n = vsnprintf(NULL, 0, fmt, ap);
-        va_end(ap);
-        va_start(ap, fmt);
-        char *buf = new_arr(a, char, n + 1);
-        vsnprintf(buf, n + 1, fmt, ap);
-        va_end(ap);
-        return (Str) { buf, n };
+	va_list ap;
+	va_start(ap, fmt);
+	int n = vsnprintf(NULL, 0, fmt, ap);
+	va_end(ap);
+	va_start(ap, fmt);
+	char *buf = new_arr(a, char, n + 1);
+	vsnprintf(buf, n + 1, fmt, ap);
+	va_end(ap);
+	return (Str) { buf, n };
 }
 
 static inline int is_space(u32 c) {
-        return c <= 0x20 && c != 0;
+	return c <= 0x20 && c != 0;
 }
 
 TxtLoc next_word(TxtLoc l) {
-        while (!at_end(l) && is_space(txt_chr(l))) l = cnext(l);
-        while (!at_end(l) && !is_space(txt_chr(l))) l = cnext(l);
-        return l;
+	while (!at_end(l) && is_space(txt_chr(l))) l = cnext(l);
+	while (!at_end(l) && !is_space(txt_chr(l))) l = cnext(l);
+	return l;
 }
 
 TxtLoc prev_word(TxtLoc l) {
-        while (!at_start(l)) {
-                TxtLoc n = bprev(l);
-                if (!is_space(txt_chr(n))) break;
-                l = n;
-        }
-        while (!at_start(l)) {
-                TxtLoc n = bprev(l);
-                if (is_space(txt_chr(n))) break;
-                l = n;
-        }
-        return l;
+	while (!at_start(l)) {
+		TxtLoc n = bprev(l);
+		if (!is_space(txt_chr(n))) break;
+		l = n;
+	}
+	while (!at_start(l)) {
+		TxtLoc n = bprev(l);
+		if (is_space(txt_chr(n))) break;
+		l = n;
+	}
+	return l;
 }
 
 static inline u32 bracket_opp(u32 c) {
-        switch (c) {
-        case '{': return '}';
-        case '}': return '{';
-        case '[': return ']';
-        case ']': return '[';
-        case '(': return ')';
-        case ')': return '(';
-        case '<': return '>';
-        case '>': return '<';
-        default:
-                return c;
-        }
+	switch (c) {
+	case '{': return '}';
+	case '}': return '{';
+	case '[': return ']';
+	case ']': return '[';
+	case '(': return ')';
+	case ')': return '(';
+	case '<': return '>';
+	case '>': return '<';
+	default:
+		return c;
+	}
 }
 
 static inline int bracket_dir(u32 c) {
-        switch (c) {
-        case '{': case '[': case '(': case '<': return 1;
-        case '}': case ']': case ')': case '>': return -1;
-        default:
-                return 0;
-        }
+	switch (c) {
+	case '{': case '[': case '(': case '<': return 1;
+	case '}': case ']': case ')': case '>': return -1;
+	default:
+		return 0;
+	}
 }
 
 int match_bracket(TxtLoc l, TxtLoc *out, u32 c) {
@@ -245,12 +245,12 @@ int match_bracket(TxtLoc l, TxtLoc *out, u32 c) {
 			}
 		}
 	}
-        if (depth == 0) {
-                *out = l;
-                return 1;
-        } else {
-                return 0;
-        }
+	if (depth == 0) {
+		*out = l;
+		return 1;
+	} else {
+		return 0;
+	}
 }
 
 static inline int is_func_end(TxtLoc l) {
@@ -260,41 +260,41 @@ static inline int is_func_end(TxtLoc l) {
 
 int next_func_end(TxtLoc l, TxtLoc *out) {
 	l = cnext(l);
-        for (;;) {
-                TxtLoc n = next_line_start(l);
+	for (;;) {
+		TxtLoc n = next_line_start(l);
 		if (!txt_before(l, n)) break;
-                if (is_func_end(l)) {
+		if (is_func_end(l)) {
 			*out = l;
 			return 1;
 		}
 		l = n;
-        }
+	}
 	return 0;
 }
 
 int prev_func_end(TxtLoc l, TxtLoc *out) {
 	l = cprev(l);
-        while (!at_start(l)) {
-                l = prev_line_start(l);
-                if (is_func_end(l)) {
+	while (!at_start(l)) {
+		l = prev_line_start(l);
+		if (is_func_end(l)) {
 			*out = l;
 			return 1;
 		}
-        }
-        return 0;
+	}
+	return 0;
 }
 
 int empty_line(TxtLoc l) {
-        u8 b = txt_byte(start_of_line(l));
-        return b == '\n' || b == 0 /* last line of buffer */
-        ;
+	u8 b = txt_byte(start_of_line(l));
+	return b == '\n' || b == 0 /* last line of buffer */
+	;
 }
 
 int prev_func(TxtLoc start, TxtLoc *out) {
 	TxtLoc l;
 	if (prev_func_end(start, &l) && match_bracket(l, &l, '}')) {
 		*out = l;
-                return 1;
+		return 1;
 	}
 	return 0;
 }
@@ -1117,7 +1117,7 @@ static inline char to_lower(char c) {
 	return c;
 }
 
-int fz_score(Str s, Str p) {
+static inline int fz_start_score(Str s, Str p) {
 	if (!p.n || str_eql(s, p)) return 0;
 	int n = 1;
 	u32 pi = 0, si = 0;
@@ -1138,19 +1138,48 @@ int fz_score(Str s, Str p) {
 	}
 }
 
-void qsort_opt(u32 *dest, int *scr, int n) {
+typedef struct {
+	u16 score, start;
+} FuzzyScore;
+
+static inline FuzzyScore fz_score(Str s, Str p) {
+	if (!p.n) return (FuzzyScore) { 0, 0 };
+	int score = -1;
+	int score_start = 0;
+	for (u32 i = 0; i < s.n; i++) {
+		const char *m = memchr(s.s + i, p.s[0], s.n - i);
+		if (m) i = m - s.s;
+		else break;
+		int f = fz_start_score(str_skip(s, i), p);
+		if (f == -1) continue;
+		if (score == -1 || f < score) {
+			score = f;
+			score_start = i;
+		}
+	}
+	if (score == -1) return (FuzzyScore) { 0xffff, 0 };
+	return (FuzzyScore) { score, score_start };
+}
+
+static inline int fz_score_cmp(FuzzyScore a, FuzzyScore b) {
+	if (a.score < b.score) return -1;
+	if (b.score < a.score) return 1;
+	return (b.start < a.start) - (a.start < b.start);
+}
+
+void qsort_opt(u32 *dest, FuzzyScore *scr, int n) {
 	int i = 0, j = n - 1;
-	int x = scr[n / 2];
+	FuzzyScore x = scr[n / 2];
 	do {
-		while (scr[i] < x) i++;
-		while (x < scr[j]) j--;
+		while (fz_score_cmp(scr[i], x) < 0) i++;
+		while (fz_score_cmp(x, scr[j]) < 0) j--;
 		if (i <= j) {
-			int t = dest[i];
+			int t0 = dest[i];
 			dest[i] = dest[j];
-			dest[j] = t;
-			t = scr[i];
+			dest[j] = t0;
+			FuzzyScore t1 = scr[i];
 			scr[i] = scr[j];
-			scr[j] = t;
+			scr[j] = t1;
 			i++;
 			j--;
 		}
@@ -1160,11 +1189,11 @@ void qsort_opt(u32 *dest, int *scr, int n) {
 }
 
 u32 sort_opt_idx(u32 *dest, Str *src, u32 n, Str pat, Arena *scratch) {
-	int *scr = new_arr(scratch, int, n);
+	FuzzyScore *scr = new_arr(scratch, FuzzyScore, n);
 	u32 scrn = 0;
 	for (u32 i = 0; i < n; i++) {
-		int s = fz_score(src[i], pat);
-		if (s != -1) {
+		FuzzyScore s = fz_score(src[i], pat);
+		if (s.score != 0xffff) {
 			scr[scrn] = s;
 			dest[scrn] = i;
 			scrn++;