Merge pull request #98278 from a-johnston/fuzzy-search-rebase

Add fuzzy string matching to quick open search

2 files changed, 102 insertions, 0 deletions

diff --git a/tests/core/string/test_fuzzy_search.h b/tests/core/string/test_fuzzy_search.h
new file mode 100644
index 0000000000..d647ebdd1a
--- /dev/null
+++ b/tests/core/string/test_fuzzy_search.h
@@ -0,0 +1,83 @@
+/**************************************************************************/
+/*  test_fuzzy_search.h                                                   */
+/**************************************************************************/
+/*                         This file is part of:                          */
+/*                             GODOT ENGINE                               */
+/*                        https://godotengine.org                         */
+/**************************************************************************/
+/* Copyright (c) 2014-present Godot Engine contributors (see AUTHORS.md). */
+/* Copyright (c) 2007-2014 Juan Linietsky, Ariel Manzur.                  */
+/*                                                                        */
+/* Permission is hereby granted, free of charge, to any person obtaining  */
+/* a copy of this software and associated documentation files (the        */
+/* "Software"), to deal in the Software without restriction, including    */
+/* without limitation the rights to use, copy, modify, merge, publish,    */
+/* distribute, sublicense, and/or sell copies of the Software, and to     */
+/* permit persons to whom the Software is furnished to do so, subject to  */
+/* the following conditions:                                              */
+/*                                                                        */
+/* The above copyright notice and this permission notice shall be         */
+/* included in all copies or substantial portions of the Software.        */
+/*                                                                        */
+/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,        */
+/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF     */
+/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. */
+/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY   */
+/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,   */
+/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE      */
+/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.                 */
+/**************************************************************************/
+
+#ifndef TEST_FUZZY_SEARCH_H
+#define TEST_FUZZY_SEARCH_H
+
+#include "core/string/fuzzy_search.h"
+#include "tests/test_macros.h"
+
+namespace TestFuzzySearch {
+
+struct FuzzySearchTestCase {
+	String query;
+	String expected;
+};
+
+// Ideally each of these test queries should represent a different aspect, and potentially bottleneck, of the search process.
+const FuzzySearchTestCase test_cases[] = {
+	// Short query, many matches, few adjacent characters
+	{ "///gd", "./menu/hud/hud.gd" },
+	// Filename match with typo
+	{ "sm.png", "./entity/blood_sword/sam.png" },
+	// Multipart filename word matches
+	{ "ham ", "./entity/game_trap/ha_missed_me.wav" },
+	// Single word token matches
+	{ "push background", "./entity/background_zone1/background/push.png" },
+	// Long token matches
+	{ "background_freighter background png", "./entity/background_freighter/background/background.png" },
+	// Many matches, many short tokens
+	{ "menu menu characters wav", "./menu/menu/characters/smoker/0.wav" },
+	// Maximize total matches
+	{ "entity gd", "./entity/entity_man.gd" }
+};
+
+Vector<String> load_test_data() {
+	Ref<FileAccess> fp = FileAccess::open(TestUtils::get_data_path("fuzzy_search/project_dir_tree.txt"), FileAccess::READ);
+	REQUIRE(fp.is_valid());
+	return fp->get_as_utf8_string().split("\n");
+}
+
+TEST_CASE("[FuzzySearch] Test fuzzy search results") {
+	FuzzySearch search;
+	Vector<FuzzySearchResult> results;
+	Vector<String> targets = load_test_data();
+
+	for (FuzzySearchTestCase test_case : test_cases) {
+		search.set_query(test_case.query);
+		search.search_all(targets, results);
+		CHECK_GT(results.size(), 0);
+		CHECK_EQ(results[0].target, test_case.expected);
+	}
+}
+
+} //namespace TestFuzzySearch
+
+#endif // TEST_FUZZY_SEARCH_H
diff --git a/tests/core/string/test_string.h b/tests/core/string/test_string.h
index 49afc55c64..9adc97e845 100644
--- a/tests/core/string/test_string.h
+++ b/tests/core/string/test_string.h
@@ -389,6 +389,19 @@ TEST_CASE("[String] Find") {
 	MULTICHECK_STRING_INT_EQ(s, rfind, "", 15, -1);
 }
 
+TEST_CASE("[String] Find character") {
+	String s = "racecar";
+	CHECK_EQ(s.find_char('r'), 0);
+	CHECK_EQ(s.find_char('r', 1), 6);
+	CHECK_EQ(s.find_char('e'), 3);
+	CHECK_EQ(s.find_char('e', 4), -1);
+
+	CHECK_EQ(s.rfind_char('r'), 6);
+	CHECK_EQ(s.rfind_char('r', 5), 0);
+	CHECK_EQ(s.rfind_char('e'), 3);
+	CHECK_EQ(s.rfind_char('e', 2), -1);
+}
+
 TEST_CASE("[String] Find case insensitive") {
 	String s = "Pretty Whale Whale";
 	MULTICHECK_STRING_EQ(s, findn, "WHA", 7);
@@ -1254,6 +1267,12 @@ TEST_CASE("[String] is_subsequence_of") {
 	CHECK(String("Sub").is_subsequence_ofn(a));
 }
 
+TEST_CASE("[String] is_lowercase") {
+	CHECK(String("abcd1234 !@#$%^&*()_-=+,.<>/\\|[]{};':\"`~").is_lowercase());
+	CHECK(String("").is_lowercase());
+	CHECK(!String("abc_ABC").is_lowercase());
+}
+
 TEST_CASE("[String] match") {
 	CHECK(String("img1.png").match("*.png"));
 	CHECK(!String("img1.jpeg").match("*.png"));