Added tokenized search support to Quick Open dialog and FileSystem filter.

4 files changed, 76 insertions, 39 deletions

diff --git a/editor/editor_quick_open.cpp b/editor/editor_quick_open.cpp
index 6fd1fd687b..f8df0f9fa8 100644
--- a/editor/editor_quick_open.cpp
+++ b/editor/editor_quick_open.cpp
@@ -91,17 +91,21 @@ void EditorQuickOpen::_build_search_cache(EditorFileSystemDirectory *p_efsd) {
 }
 
 void EditorQuickOpen::_update_search() {
-	const String search_text = search_box->get_text();
-	const bool empty_search = search_text.is_empty();
+	const PackedStringArray search_tokens = search_box->get_text().to_lower().replace("/", " ").split(" ", false);
+	const bool empty_search = search_tokens.is_empty();
 
 	// Filter possible candidates.
 	Vector<Entry> entries;
 	for (int i = 0; i < files.size(); i++) {
-		if (empty_search || search_text.is_subsequence_ofn(files[i])) {
-			Entry r;
-			r.path = files[i];
-			r.score = empty_search ? 0 : _score_path(search_text, files[i].to_lower());
+		Entry r;
+		r.path = files[i];
+		if (empty_search) {
 			entries.push_back(r);
+		} else {
+			r.score = _score_search_result(search_tokens, r.path.to_lower());
+			if (r.score > 0) {
+				entries.push_back(r);
+			}
 		}
 	}
 
@@ -135,23 +139,42 @@ void EditorQuickOpen::_update_search() {
 	}
 }
 
-float EditorQuickOpen::_score_path(const String &p_search, const String &p_path) {
-	float score = 0.9f + .1f * (p_search.length() / (float)p_path.length());
+float EditorQuickOpen::_score_search_result(const PackedStringArray &p_search_tokens, const String &p_path) {
+	float score = 0.0f;
+	int prev_min_match_idx = -1;
 
-	// Exact match.
-	if (p_search == p_path) {
-		return 1.2f;
-	}
+	for (const String &s : p_search_tokens) {
+		int min_match_idx = p_path.find(s);
+
+		if (min_match_idx == -1) {
+			return 0.0f;
+		}
+
+		float token_score = s.length();
+
+		int max_match_idx = p_path.rfind(s);
+
+		// Prioritize the actual file name over folder.
+		if (max_match_idx > p_path.rfind("/")) {
+			token_score *= 2.0f;
+		}
+
+		// Prioritize matches at the front of the path token.
+		if (min_match_idx == 0 || p_path.find("/" + s) != -1) {
+			token_score += 1.0f;
+		}
+
+		score += token_score;
+
+		// Prioritize tokens which appear in order.
+		if (prev_min_match_idx != -1 && max_match_idx > prev_min_match_idx) {
+			score += 1.0f;
+		}
 
-	// Positive bias for matches close to the beginning of the file name.
-	String file = p_path.get_file();
-	int pos = file.findn(p_search);
-	if (pos != -1) {
-		return score * (1.0f - 0.1f * (float(pos) / file.length()));
+		prev_min_match_idx = min_match_idx;
 	}
 
-	// Similarity
-	return p_path.to_lower().similarity(p_search.to_lower());
+	return score;
 }
 
 void EditorQuickOpen::_confirmed() {
diff --git a/editor/editor_quick_open.h b/editor/editor_quick_open.h
index ec8ce0175e..bbc689040a 100644
--- a/editor/editor_quick_open.h
+++ b/editor/editor_quick_open.h
@@ -63,7 +63,7 @@ class EditorQuickOpen : public ConfirmationDialog {
 
 	void _update_search();
 	void _build_search_cache(EditorFileSystemDirectory *p_efsd);
-	float _score_path(const String &p_search, const String &p_path);
+	float _score_search_result(const PackedStringArray &p_search_tokens, const String &p_path);
 
 	void _confirmed();
 	virtual void cancel_pressed() override;
diff --git a/editor/filesystem_dock.cpp b/editor/filesystem_dock.cpp
index 2ed547a970..026df27819 100644
--- a/editor/filesystem_dock.cpp
+++ b/editor/filesystem_dock.cpp
@@ -267,7 +267,7 @@ bool FileSystemDock::_create_tree(TreeItem *p_parent, EditorFileSystemDirectory
 	} else {
 		subdirectory_item->set_collapsed(uncollapsed_paths.find(lpath) < 0);
 	}
-	if (searched_string.length() > 0 && dname.to_lower().find(searched_string) >= 0) {
+	if (!searched_tokens.is_empty() && _matches_all_search_tokens(dname)) {
 		parent_should_expand = true;
 	}
 
@@ -293,8 +293,8 @@ bool FileSystemDock::_create_tree(TreeItem *p_parent, EditorFileSystemDirectory
 			}
 
 			String file_name = p_dir->get_file(i);
-			if (searched_string.length() > 0) {
-				if (file_name.to_lower().find(searched_string) < 0) {
+			if (!searched_tokens.is_empty()) {
+				if (!_matches_all_search_tokens(file_name)) {
 					// The searched string is not in the file name, we skip it.
 					continue;
 				} else {
@@ -352,7 +352,7 @@ bool FileSystemDock::_create_tree(TreeItem *p_parent, EditorFileSystemDirectory
 		}
 	}
 
-	if (searched_string.length() > 0) {
+	if (!searched_tokens.is_empty()) {
 		if (parent_should_expand) {
 			subdirectory_item->set_collapsed(false);
 		} else if (dname != "res://") {
@@ -460,7 +460,7 @@ void FileSystemDock::_update_tree(const Vector<String> &p_uncollapsed_paths, boo
 			color = Color(1, 1, 1);
 		}
 
-		if (searched_string.length() == 0 || text.to_lower().find(searched_string) >= 0) {
+		if (searched_tokens.is_empty() || _matches_all_search_tokens(text)) {
 			TreeItem *ti = tree->create_item(favorites_item);
 			ti->set_text(0, text);
 			ti->set_icon(0, icon);
@@ -857,7 +857,7 @@ void FileSystemDock::_search(EditorFileSystemDirectory *p_path, List<FileInfo> *
 	for (int i = 0; i < p_path->get_file_count(); i++) {
 		String file = p_path->get_file(i);
 
-		if (file.to_lower().contains(searched_string)) {
+		if (_matches_all_search_tokens(file)) {
 			FileInfo fi;
 			fi.name = file;
 			fi.type = p_path->get_file_type(i);
@@ -984,14 +984,14 @@ void FileSystemDock::_update_file_list(bool p_keep_selection) {
 			if (favorite == "res://") {
 				text = "/";
 				icon = folder_icon;
-				if (searched_string.length() == 0 || text.to_lower().find(searched_string) >= 0) {
+				if (searched_tokens.is_empty() || _matches_all_search_tokens(text)) {
 					files->add_item(text, icon, true);
 					files->set_item_metadata(-1, favorite);
 				}
 			} else if (favorite.ends_with("/")) {
 				text = favorite.substr(0, favorite.length() - 1).get_file();
 				icon = folder_icon;
-				if (searched_string.length() == 0 || text.to_lower().find(searched_string) >= 0) {
+				if (searched_tokens.is_empty() || _matches_all_search_tokens(text)) {
 					files->add_item(text, icon, true);
 					files->set_item_metadata(-1, favorite);
 				}
@@ -1013,7 +1013,7 @@ void FileSystemDock::_update_file_list(bool p_keep_selection) {
 					fi.modified_time = 0;
 				}
 
-				if (searched_string.length() == 0 || fi.name.to_lower().find(searched_string) >= 0) {
+				if (searched_tokens.is_empty() || _matches_all_search_tokens(fi.name)) {
 					file_list.push_back(fi);
 				}
 			}
@@ -1036,7 +1036,7 @@ void FileSystemDock::_update_file_list(bool p_keep_selection) {
 			return;
 		}
 
-		if (searched_string.length() > 0) {
+		if (!searched_tokens.is_empty()) {
 			// Display the search results.
 			// Limit the number of results displayed to avoid an infinite loop.
 			_search(EditorFileSystem::get_singleton()->get_filesystem(), &file_list, 10000);
@@ -1272,7 +1272,7 @@ void FileSystemDock::_file_list_activate_file(int p_idx) {
 }
 
 void FileSystemDock::_preview_invalidated(const String &p_path) {
-	if (file_list_display_mode == FILE_LIST_DISPLAY_THUMBNAILS && p_path.get_base_dir() == current_path && searched_string.length() == 0 && file_list_vb->is_visible_in_tree()) {
+	if (file_list_display_mode == FILE_LIST_DISPLAY_THUMBNAILS && p_path.get_base_dir() == current_path && searched_tokens.is_empty() && file_list_vb->is_visible_in_tree()) {
 		for (int i = 0; i < files->get_item_count(); i++) {
 			if (files->get_item_metadata(i) == p_path) {
 				// Re-request preview.
@@ -2603,12 +2603,13 @@ void FileSystemDock::_resource_created() {
 }
 
 void FileSystemDock::_search_changed(const String &p_text, const Control *p_from) {
-	if (searched_string.length() == 0) {
+	if (searched_tokens.is_empty()) {
 		// Register the uncollapsed paths before they change.
 		uncollapsed_paths_before_search = get_uncollapsed_paths();
 	}
 
-	searched_string = p_text.to_lower();
+	const String searched_string = p_text.to_lower();
+	searched_tokens = searched_string.split(" ", false);
 
 	if (p_from == tree_search_box) {
 		file_list_search_box->set_text(searched_string);
@@ -2619,16 +2620,29 @@ void FileSystemDock::_search_changed(const String &p_text, const Control *p_from
 	bool unfold_path = (p_text.is_empty() && !current_path.is_empty());
 	switch (display_mode) {
 		case DISPLAY_MODE_TREE_ONLY: {
-			_update_tree(searched_string.length() == 0 ? uncollapsed_paths_before_search : Vector<String>(), false, false, unfold_path);
+			_update_tree(searched_tokens.is_empty() ? uncollapsed_paths_before_search : Vector<String>(), false, false, unfold_path);
 		} break;
 		case DISPLAY_MODE_HSPLIT:
 		case DISPLAY_MODE_VSPLIT: {
 			_update_file_list(false);
-			_update_tree(searched_string.length() == 0 ? uncollapsed_paths_before_search : Vector<String>(), false, false, unfold_path);
+			_update_tree(searched_tokens.is_empty() ? uncollapsed_paths_before_search : Vector<String>(), false, false, unfold_path);
 		} break;
 	}
 }
 
+bool FileSystemDock::_matches_all_search_tokens(const String &p_text) {
+	if (searched_tokens.is_empty()) {
+		return false;
+	}
+	const String s = p_text.to_lower();
+	for (const String &t : searched_tokens) {
+		if (!s.contains(t)) {
+			return false;
+		}
+	}
+	return true;
+}
+
 void FileSystemDock::_rescan() {
 	_set_scanning_mode();
 	EditorFileSystem::get_singleton()->scan();
@@ -3354,7 +3368,7 @@ void FileSystemDock::_file_list_item_clicked(int p_item, const Vector2 &p_pos, M
 	// Popup.
 	if (!paths.is_empty()) {
 		file_list_popup->clear();
-		_file_and_folders_fill_popup(file_list_popup, paths, searched_string.length() == 0);
+		_file_and_folders_fill_popup(file_list_popup, paths, searched_tokens.is_empty());
 		file_list_popup->set_position(files->get_screen_position() + p_pos);
 		file_list_popup->reset_size();
 		file_list_popup->popup();
@@ -3367,7 +3381,7 @@ void FileSystemDock::_file_list_empty_clicked(const Vector2 &p_pos, MouseButton
 	}
 
 	// Right click on empty space for file list.
-	if (searched_string.length() > 0) {
+	if (!searched_tokens.is_empty()) {
 		return;
 	}
 
@@ -4113,7 +4127,6 @@ FileSystemDock::FileSystemDock() {
 	new_resource_dialog->set_base_type("Resource");
 	new_resource_dialog->connect("create", callable_mp(this, &FileSystemDock::_resource_created));
 
-	searched_string = String();
 	uncollapsed_paths_before_search = Vector<String>();
 
 	tree_update_id = 0;
diff --git a/editor/filesystem_dock.h b/editor/filesystem_dock.h
index 8830f31d2d..6dbf25cf73 100644
--- a/editor/filesystem_dock.h
+++ b/editor/filesystem_dock.h
@@ -172,7 +172,7 @@ private:
 	LineEdit *file_list_search_box = nullptr;
 	MenuButton *file_list_button_sort = nullptr;
 
-	String searched_string;
+	PackedStringArray searched_tokens;
 	Vector<String> uncollapsed_paths_before_search;
 
 	TextureRect *search_icon = nullptr;
@@ -311,6 +311,7 @@ private:
 	void _split_dragged(int p_offset);
 
 	void _search_changed(const String &p_text, const Control *p_from);
+	bool _matches_all_search_tokens(const String &p_text);
 
 	MenuButton *_create_file_menu_button();
 	void _file_sort_popup(int p_id);