Sort results by match position.

Search results will now be sorted by history first, then by the position
of the match, such that a match at the start of a result will appear
before a match later in the result.

6 files changed, 50 insertions, 17 deletions

diff --git a/src/compgen.c b/src/compgen.c
index 84cd323..f656f32 100644
--- a/src/compgen.c
+++ b/src/compgen.c
@@ -188,6 +188,7 @@ void compgen_history_sort(struct string_vec *programs, struct history *history)
 		free(*res);
 		*res = NULL;
 		string_vec_add(&to_add, history->buf[i].name);
+		to_add.buf[to_add.count - 1].history_score = history->buf[i].run_count;
 	}
 
 	/* Sort the vector to push the removed entries to the end. */
@@ -205,7 +206,8 @@ void compgen_history_sort(struct string_vec *programs, struct history *history)
 
 	/* Add our history to the front in order. */
 	for (size_t i = 0; i < to_add.count; i++) {
-		programs->buf[i] = xstrdup(to_add.buf[i]);
+		programs->buf[i].string = xstrdup(to_add.buf[i].string);
+		programs->buf[i].history_score = to_add.buf[i].history_score;
 	}
 	string_vec_destroy(&to_add);
 }
diff --git a/src/entry_backend/harfbuzz.c b/src/entry_backend/harfbuzz.c
index fe4d7dc..bb4429c 100644
--- a/src/entry_backend/harfbuzz.c
+++ b/src/entry_backend/harfbuzz.c
@@ -228,7 +228,7 @@ void entry_backend_harfbuzz_update(struct entry *entry)
 
 		hb_buffer_clear_contents(buffer);
 		setup_hb_buffer(buffer);
-		hb_buffer_add_utf8(buffer, entry->results.buf[i], -1, 0, -1);
+		hb_buffer_add_utf8(buffer, entry->results.buf[i].string, -1, 0, -1);
 		hb_shape(entry->harfbuzz.hb_font, buffer, NULL, 0);
 		if (i == entry->selection) {
 			cairo_push_group(cr);
diff --git a/src/entry_backend/pango.c b/src/entry_backend/pango.c
index 8a0add7..34bb05e 100644
--- a/src/entry_backend/pango.c
+++ b/src/entry_backend/pango.c
@@ -80,7 +80,7 @@ void entry_backend_pango_update(struct entry *entry)
 		}
 		const char *str;
 		if (i < entry->results.count) {
-			str = entry->results.buf[i];
+			str = entry->results.buf[i].string;
 		} else {
 			str = "";
 		}
diff --git a/src/main.c b/src/main.c
index 307be0e..96140f5 100644
--- a/src/main.c
+++ b/src/main.c
@@ -1187,11 +1187,11 @@ int main(int argc, char *argv[])
 			tofi.submit = false;
 			if (tofi.window.entry.results.count > 0) {
 				uint32_t selection = tofi.window.entry.selection;
-				printf("%s\n", tofi.window.entry.results.buf[selection]);
+				printf("%s\n", tofi.window.entry.results.buf[selection].string);
 				if (tofi.use_history) {
 					history_add(
 							&tofi.window.entry.history,
-							tofi.window.entry.results.buf[selection]);
+							tofi.window.entry.results.buf[selection].string);
 					history_save(&tofi.window.entry.history);
 				}
 				break;
diff --git a/src/string_vec.c b/src/string_vec.c
index 8318df6..8806705 100644
--- a/src/string_vec.c
+++ b/src/string_vec.c
@@ -27,12 +27,22 @@ static int cmpstringp(const void *restrict a, const void *restrict b)
 	return strcmp(str1, str2);
 }
 
+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;
+}
+
 struct string_vec string_vec_create(void)
 {
 	struct string_vec vec = {
 		.count = 0,
 		.size = 128,
-		.buf = xcalloc(128, sizeof(char *))
+		.buf = xcalloc(128, sizeof(*vec.buf)),
 	};
 	return vec;
 }
@@ -40,7 +50,7 @@ struct string_vec string_vec_create(void)
 void string_vec_destroy(struct string_vec *restrict vec)
 {
 	for (size_t i = 0; i < vec->count; i++) {
-		free(vec->buf[i]);
+		free(vec->buf[i].string);
 	}
 	free(vec->buf);
 }
@@ -50,11 +60,13 @@ struct string_vec string_vec_copy(struct string_vec *restrict vec)
 	struct string_vec copy = {
 		.count = vec->count,
 		.size = vec->size,
-		.buf = xcalloc(vec->size, sizeof(char *))
+		.buf = xcalloc(vec->size, sizeof(*copy.buf)),
 	};
 
 	for (size_t i = 0; i < vec->count; i++) {
-		copy.buf[i] = xstrdup(vec->buf[i]);
+		copy.buf[i].string = xstrdup(vec->buf[i].string);
+		copy.buf[i].search_score = vec->buf[i].search_score;
+		copy.buf[i].history_score = vec->buf[i].history_score;
 	}
 
 	return copy;
@@ -66,7 +78,7 @@ void string_vec_add(struct string_vec *restrict vec, const char *restrict str)
 		vec->size *= 2;
 		vec->buf = xrealloc(vec->buf, vec->size * sizeof(vec->buf[0]));
 	}
-	vec->buf[vec->count] = xstrdup(str);
+	vec->buf[vec->count].string = xstrdup(str);
 	vec->count++;
 }
 
@@ -79,9 +91,9 @@ void string_vec_uniq(struct string_vec *restrict vec)
 {
 	size_t count = vec->count;
 	for (size_t i = 1; i < vec->count; i++) {
-		if (!strcmp(vec->buf[i], vec->buf[i-1])) {
-			free(vec->buf[i-1]);
-			vec->buf[i-1] = NULL;
+		if (!strcmp(vec->buf[i].string, vec->buf[i-1].string)) {
+			free(vec->buf[i-1].string);
+			vec->buf[i-1].string = NULL;
 			count--;
 		}
 	}
@@ -100,10 +112,22 @@ struct string_vec string_vec_filter(
 {
 	struct string_vec filt = string_vec_create();
 	for (size_t i = 0; i < vec->count; i++) {
-		if (strcasestr(vec->buf[i], substr) != NULL) {
-			string_vec_add(&filt, vec->buf[i]);
+		char *c = strcasestr(vec->buf[i].string, substr);
+		if (c != NULL) {
+			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].history_score = vec->buf[i].history_score;
 		}
 	}
+	/*
+	 * Sort the results by this search_score. This moves matches at the beginnings
+	 * of words to the front of the result list.
+	 */
+	qsort(filt.buf, filt.count, sizeof(filt.buf[0]), cmpscorep);
 	return filt;
 }
 
@@ -131,7 +155,7 @@ struct string_vec string_vec_load(FILE *file)
 void string_vec_save(struct string_vec *restrict vec, FILE *restrict file)
 {
 	for (size_t i = 0; i < vec->count; i++) {
-		fputs(vec->buf[i], file);
+		fputs(vec->buf[i].string, file);
 		fputc('\n', file);
 	}
 }
diff --git a/src/string_vec.h b/src/string_vec.h
index 44fd5fe..2a106a2 100644
--- a/src/string_vec.h
+++ b/src/string_vec.h
@@ -2,12 +2,19 @@
 #define STRING_VEC_H
 
 #include <stddef.h>
+#include <stdint.h>
 #include <stdio.h>
 
+struct scored_string {
+	char *string;
+	int8_t search_score;
+	int8_t history_score;
+};
+
 struct string_vec {
 	size_t count;
 	size_t size;
-	char **buf;
+	struct scored_string *buf;
 };
 
 [[nodiscard("memory leaked")]]