Add keyword matching for drun searches.

There's starting to be a fair amount of duplicated code between the drun
and normal run modes. At some point in the future, it's likely to be
worth combining them, such that there's only a single
`struct search_item` or similar, and just handle the different modes at
the start and end of execution.

6 files changed, 124 insertions, 13 deletions

diff --git a/src/desktop_vec.c b/src/desktop_vec.c
index d02b2ac..f4363f8 100644
--- a/src/desktop_vec.c
+++ b/src/desktop_vec.c
@@ -24,6 +24,7 @@ void desktop_vec_destroy(struct desktop_vec *restrict vec)
 		free(vec->buf[i].id);
 		free(vec->buf[i].name);
 		free(vec->buf[i].path);
+		free(vec->buf[i].keywords);
 	}
 	free(vec->buf);
 }
@@ -32,7 +33,8 @@ void desktop_vec_add(
 		struct desktop_vec *restrict vec,
 		const char *restrict id,
 		const char *restrict name,
-		const char *restrict path)
+		const char *restrict path,
+		const char *restrict keywords)
 {
 	if (vec->count == vec->size) {
 		vec->size *= 2;
@@ -41,6 +43,9 @@ void desktop_vec_add(
 	vec->buf[vec->count].id = xstrdup(id);
 	vec->buf[vec->count].name = xstrdup(name);
 	vec->buf[vec->count].path = xstrdup(path);
+	vec->buf[vec->count].keywords = xstrdup(keywords);
+	vec->buf[vec->count].search_score = 0;
+	vec->buf[vec->count].history_score = 0;
 	vec->count++;
 }
 
@@ -65,6 +70,15 @@ void desktop_vec_add_file(struct desktop_vec *vec, const char *id, const char *p
 		goto cleanup_file;
 	}
 
+	/*
+	 * This is really a list rather than a string, but for the purposes of
+	 * matching against user input it's easier to just keep it as a string.
+	 */
+	char *keywords = g_key_file_get_locale_string(file, group, "Keywords", NULL, NULL);
+	if (keywords == NULL) {
+		keywords = "";
+	}
+
 	gsize length;
 	gchar **list = g_key_file_get_string_list(file, group, "OnlyShowIn", &length, NULL);
 	if (list) {
@@ -86,7 +100,7 @@ void desktop_vec_add_file(struct desktop_vec *vec, const char *id, const char *p
 		}
 	}
 
-	desktop_vec_add(vec, id, name, path);
+	desktop_vec_add(vec, id, name, path, keywords);
 
 cleanup_name:
 	free(name);
@@ -101,6 +115,16 @@ static int cmpdesktopp(const void *restrict a, const void *restrict b)
 	return strcmp(d1->name, d2->name);
 }
 
+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;
+}
+
 void desktop_vec_sort(struct desktop_vec *restrict vec)
 {
 	qsort(vec->buf, vec->count, sizeof(vec->buf[0]), cmpdesktopp);
@@ -116,6 +140,43 @@ struct desktop_entry *desktop_vec_find(struct desktop_vec *restrict vec, const c
 	return bsearch(&tmp, vec->buf, vec->count, sizeof(vec->buf[0]), cmpdesktopp);
 }
 
+struct string_vec desktop_vec_filter(
+		const struct desktop_vec *restrict vec,
+		const char *restrict substr)
+{
+	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) {
+			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].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) {
+				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].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;
+}
+
 struct desktop_vec desktop_vec_load(FILE *file)
 {
 	struct desktop_vec vec = desktop_vec_create();
@@ -135,7 +196,9 @@ struct desktop_vec desktop_vec_load(FILE *file)
 		char *name = &line[sublen + 1];
 		sublen = strlen(name);
 		char *path = &name[sublen + 1];
-		desktop_vec_add(&vec, id, name, path);
+		sublen = strlen(path);
+		char *keywords = &path[sublen + 1];
+		desktop_vec_add(&vec, id, name, path, keywords);
 	}
 	free(line);
 
@@ -154,6 +217,8 @@ void desktop_vec_save(struct desktop_vec *restrict vec, FILE *restrict file)
 		fputs(vec->buf[i].name, file);
 		fputc('\0', file);
 		fputs(vec->buf[i].path, file);
+		fputc('\0', file);
+		fputs(vec->buf[i].keywords, file);
 		fputc('\n', file);
 	}
 }
diff --git a/src/desktop_vec.h b/src/desktop_vec.h
index 9c15ad9..85c885e 100644
--- a/src/desktop_vec.h
+++ b/src/desktop_vec.h
@@ -3,11 +3,15 @@
 
 #include <stddef.h>
 #include <stdio.h>
+#include <stdint.h>
 
 struct desktop_entry {
 	char *id;
 	char *name;
 	char *path;
+	char *keywords;
+	uint32_t search_score;
+	uint32_t history_score;
 };
 
 struct desktop_vec {
@@ -23,11 +27,15 @@ void desktop_vec_add(
 		struct desktop_vec *restrict vec,
 		const char *restrict id,
 		const char *restrict name,
-		const char *restrict path);
+		const char *restrict path,
+		const char *restrict keywords);
 void desktop_vec_add_file(struct desktop_vec *desktop, const char *id, const char *path);
 
 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);
 
 struct desktop_vec desktop_vec_load(FILE *file);
 void desktop_vec_save(struct desktop_vec *restrict vec, FILE *restrict file);
diff --git a/src/drun.c b/src/drun.c
index 8e1e0b4..482db92 100644
--- a/src/drun.c
+++ b/src/drun.c
@@ -290,3 +290,23 @@ void drun_launch(const char *filename)
 	g_object_unref(context);
 	g_object_unref(info);
 }
+
+static int cmpscorep(const void *restrict a, const void *restrict b)
+{
+	struct desktop_entry *restrict app1 = (struct desktop_entry *)a;
+	struct desktop_entry *restrict app2 = (struct desktop_entry *)b;
+	return app2->history_score - app1->history_score;
+}
+
+void drun_history_sort(struct desktop_vec *apps, struct history *history)
+{
+	log_debug("Moving already known apps to the front.\n");
+	for (size_t i = 0; i < history->count; i++) {
+		struct desktop_entry *res = desktop_vec_find(apps, history->buf[i].name);
+		if (res == NULL) {
+			continue;
+		}
+		res->history_score = history->buf[i].run_count;
+	}
+	qsort(apps->buf, apps->count, sizeof(apps->buf[0]), cmpscorep);
+}
diff --git a/src/drun.h b/src/drun.h
index 2e14599..8650ae6 100644
--- a/src/drun.h
+++ b/src/drun.h
@@ -2,10 +2,12 @@
 #define DRUN_H
 
 #include "desktop_vec.h"
+#include "history.h"
 #include "string_vec.h"
 
 struct desktop_vec drun_generate(void);
 struct desktop_vec drun_generate_cached(void);
+void drun_history_sort(struct desktop_vec *apps, struct history *history);
 void drun_launch(const char *filename);
 
 #endif /* DRUN_H */
diff --git a/src/main.c b/src/main.c
index 9429408..cb49c4a 100644
--- a/src/main.c
+++ b/src/main.c
@@ -170,9 +170,15 @@ static void wl_keyboard_key(
 					buf,
 					N_ELEM(buf));
 			entry->input_mb_length += len;
-			struct string_vec tmp = entry->results;
-			entry->results = string_vec_filter(&entry->results, entry->input_mb);
-			string_vec_destroy(&tmp);
+			if (tofi->window.entry.drun) {
+				struct string_vec results = desktop_vec_filter(&entry->apps, entry->input_mb);
+				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);
+				string_vec_destroy(&tmp);
+			}
 		}
 	} else if (entry->input_length > 0 && sym == XKB_KEY_BackSpace) {
 		entry->input_length--;
@@ -185,7 +191,11 @@ static void wl_keyboard_key(
 				NULL);
 		entry->input_mb_length = siz;
 		string_vec_destroy(&entry->results);
-		entry->results = string_vec_filter(&entry->commands, entry->input_mb);
+		if (tofi->window.entry.drun) {
+			entry->results = desktop_vec_filter(&entry->apps, entry->input_mb);
+		} else {
+			entry->results = string_vec_filter(&entry->commands, entry->input_mb);
+		}
 	} else if (sym == XKB_KEY_Escape
 			|| (sym == XKB_KEY_c
 				&& xkb_state_mod_name_is_active(
@@ -1046,6 +1056,10 @@ int main(int argc, char *argv[])
 		log_debug("Generating command list.\n");
 		log_indent();
 		tofi.window.entry.commands = compgen_cached();
+		if (tofi.use_history) {
+			tofi.window.entry.history = history_load(tofi.window.entry.drun);
+			compgen_history_sort(&tofi.window.entry.commands, &tofi.window.entry.history);
+		}
 		log_unindent();
 		log_debug("Command list generated.\n");
 	} else if (strstr(argv[0], "-drun")) {
@@ -1053,6 +1067,12 @@ int main(int argc, char *argv[])
 		log_indent();
 		tofi.window.entry.drun = true;
 		struct desktop_vec apps = drun_generate_cached();
+		if (tofi.use_history) {
+			tofi.window.entry.history = history_load(tofi.window.entry.drun);
+			if (tofi.window.entry.drun) {
+				drun_history_sort(&apps, &tofi.window.entry.history);
+			}
+		}
 		struct string_vec commands = string_vec_create();
 		for (size_t i = 0; i < apps.count; i++) {
 			string_vec_add(&commands, apps.buf[i].name);
@@ -1075,10 +1095,6 @@ int main(int argc, char *argv[])
 		free(line);
 		tofi.use_history = false;
 	}
-	if (tofi.use_history) {
-		tofi.window.entry.history = history_load(tofi.window.entry.drun);
-		compgen_history_sort(&tofi.window.entry.commands, &tofi.window.entry.history);
-	}
 	tofi.window.entry.results = string_vec_copy(&tofi.window.entry.commands);
 
 	/*
diff --git a/src/string_vec.h b/src/string_vec.h
index 7fce96e..64b3d46 100644
--- a/src/string_vec.h
+++ b/src/string_vec.h
@@ -7,7 +7,7 @@
 
 struct scored_string {
 	char *string;
-	int8_t search_score;
+	int32_t search_score;
 	int32_t history_score;
 };