Improve Create Dialog search ranking and refactor calculation.

Code changes:
 - Improved search ranking with various features (position in type string, string length proportion, in favorite list, in recent list).
 - Recent items are now stored in an ItemList (no visual change).
 - Removed results that had a parent that matched the search term to improve clarity.

Performance:
 - Reduce types to process upon opening the dialog (instead of every search change), reduces number of types by 4~5.
 - Clear arrays after closing dialog instead of keeping them.
 - Various other optimizations.

2 files changed, 359 insertions, 459 deletions

diff --git a/editor/create_dialog.cpp b/editor/create_dialog.cpp
index 310de9dd90..a1bc7a9522 100644
--- a/editor/create_dialog.cpp
+++ b/editor/create_dialog.cpp
@@ -32,60 +32,38 @@
 
 #include "core/class_db.h"
 #include "core/os/keyboard.h"
-#include "core/print_string.h"
 #include "editor_feature_profile.h"
-#include "editor_help.h"
 #include "editor_node.h"
 #include "editor_scale.h"
 #include "editor_settings.h"
-#include "scene/gui/box_container.h"
 
 void CreateDialog::popup_create(bool p_dont_clear, bool p_replace_mode, const String &p_select_type) {
-	type_list.clear();
-	ClassDB::get_class_list(&type_list);
-	ScriptServer::get_global_class_list(&type_list);
-	type_list.sort_custom<StringName::AlphCompare>();
-
-	recent->clear();
-
-	FileAccess *f = FileAccess::open(EditorSettings::get_singleton()->get_project_settings_dir().plus_file("create_recent." + base_type), FileAccess::READ);
+	_fill_type_list();
 
-	if (f) {
-		TreeItem *root = recent->create_item();
+	icon_fallback = search_options->has_theme_icon(base_type, "EditorIcons") ? base_type : "Object";
 
-		String icon_fallback = search_options->has_theme_icon(base_type, "EditorIcons") ? base_type : "Object";
-
-		while (!f->eof_reached()) {
-			String l = f->get_line().strip_edges();
-			String name = l.split(" ")[0];
-			if ((ClassDB::class_exists(name) || ScriptServer::is_global_class(name)) && !_is_class_disabled_by_feature_profile(name)) {
-				TreeItem *ti = recent->create_item(root);
-				ti->set_text(0, l);
-				ti->set_icon(0, EditorNode::get_singleton()->get_class_icon(name, icon_fallback));
-			}
-		}
-
-		memdelete(f);
+	if (p_dont_clear) {
+		search_box->select_all();
+	} else {
+		search_box->clear();
 	}
 
-	favorites->clear();
-
-	f = FileAccess::open(EditorSettings::get_singleton()->get_project_settings_dir().plus_file("favorites." + base_type), FileAccess::READ);
-
-	favorite_list.clear();
-
-	if (f) {
-		while (!f->eof_reached()) {
-			String l = f->get_line().strip_edges();
+	if (p_replace_mode) {
+		search_box->set_text(p_select_type);
+	}
 
-			if (l != String()) {
-				favorite_list.push_back(l);
-			}
-		}
+	search_box->grab_focus();
+	_update_search();
 
-		memdelete(f);
+	if (p_replace_mode) {
+		set_title(vformat(TTR("Change %s Type"), base_type));
+		get_ok()->set_text(TTR("Change"));
+	} else {
+		set_title(vformat(TTR("Create New %s"), base_type));
+		get_ok()->set_text(TTR("Create"));
 	}
 
+	_load_favorites_and_history();
 	_save_and_update_favorite_list();
 
 	// Restore valid window bounds or pop up at default size.
@@ -95,357 +73,263 @@ void CreateDialog::popup_create(bool p_dont_clear, bool p_replace_mode, const St
 	} else {
 		popup_centered_clamped(Size2(900, 700) * EDSCALE, 0.8);
 	}
+}
 
-	if (p_dont_clear) {
-		search_box->select_all();
-	} else {
-		search_box->clear();
-	}
+void CreateDialog::_fill_type_list() {
+	List<StringName> complete_type_list;
+	ClassDB::get_class_list(&complete_type_list);
+	ScriptServer::get_global_class_list(&complete_type_list);
 
-	search_box->grab_focus();
+	EditorData &ed = EditorNode::get_editor_data();
 
-	_update_search();
+	for (List<StringName>::Element *I = complete_type_list.front(); I; I = I->next()) {
+		String type = I->get();
+		if (!_should_hide_type(type)) {
+			type_list.push_back(type);
 
-	is_replace_mode = p_replace_mode;
+			if (!ed.get_custom_types().has(type)) {
+				continue;
+			}
 
-	if (p_replace_mode) {
-		select_type(p_select_type);
-		set_title(vformat(TTR("Change %s Type"), base_type));
-		get_ok()->set_text(TTR("Change"));
-	} else {
-		set_title(vformat(TTR("Create New %s"), base_type));
-		get_ok()->set_text(TTR("Create"));
+			const Vector<EditorData::CustomType> &ct = ed.get_custom_types()[type];
+			for (int i = 0; i < ct.size(); i++) {
+				custom_type_parents[ct[i].name] = type;
+				custom_type_indices[ct[i].name] = i;
+				type_list.push_back(ct[i].name);
+			}
+		}
 	}
+	type_list.sort_custom<StringName::AlphCompare>();
 }
 
-void CreateDialog::_text_changed(const String &p_newtext) {
-	_update_search();
+bool CreateDialog::_is_type_preferred(const String &p_type) const {
+	if (ClassDB::class_exists(p_type)) {
+		return ClassDB::is_parent_class(p_type, preferred_search_result_type);
+	}
+
+	return EditorNode::get_editor_data().script_class_is_parent(p_type, preferred_search_result_type);
 }
 
-void CreateDialog::_sbox_input(const Ref<InputEvent> &p_ie) {
-	Ref<InputEventKey> k = p_ie;
-	if (k.is_valid() && (k->get_keycode() == KEY_UP ||
-								k->get_keycode() == KEY_DOWN ||
-								k->get_keycode() == KEY_PAGEUP ||
-								k->get_keycode() == KEY_PAGEDOWN)) {
-		search_options->call("_gui_input", k);
-		search_box->accept_event();
-	}
+bool CreateDialog::_is_class_disabled_by_feature_profile(const StringName &p_class) const {
+	Ref<EditorFeatureProfile> profile = EditorFeatureProfileManager::get_singleton()->get_current_profile();
+
+	return !profile.is_null() && profile->is_class_disabled(p_class);
 }
 
-void CreateDialog::add_type(const String &p_type, HashMap<String, TreeItem *> &p_types, TreeItem *p_root, TreeItem **to_select) {
-	if (p_types.has(p_type)) {
-		return;
+bool CreateDialog::_should_hide_type(const String &p_type) const {
+	if (_is_class_disabled_by_feature_profile(p_type)) {
+		return true;
 	}
 
-	bool cpp_type = ClassDB::class_exists(p_type);
-	EditorData &ed = EditorNode::get_editor_data();
+	if (base_type == "Node" && p_type.begins_with("Editor")) {
+		return true; // Do not show editor nodes.
+	}
 
 	if (p_type == base_type) {
-		return;
+		return true; // Root is already added.
 	}
 
-	if (cpp_type) {
+	if (ClassDB::class_exists(p_type)) {
+		if (!ClassDB::can_instance(p_type)) {
+			return true; // Can't create abstract class.
+		}
+
 		if (!ClassDB::is_parent_class(p_type, base_type)) {
-			return;
+			return true; // Wrong inheritance.
+		}
+
+		for (Set<StringName>::Element *E = type_blacklist.front(); E; E = E->next()) {
+			if (ClassDB::is_parent_class(p_type, E->get())) {
+				return true; // Parent type is blacklisted.
+			}
 		}
 	} else {
-		if (!search_loaded_scripts.has(p_type)) {
-			search_loaded_scripts[p_type] = ed.script_class_load_script(p_type);
+		if (!EditorNode::get_editor_data().script_class_is_parent(p_type, base_type)) {
+			return true; // Wrong inheritance.
 		}
-
-		if (!ScriptServer::is_global_class(p_type) || !ed.script_class_is_parent(p_type, base_type)) {
-			return;
+		if (!ScriptServer::is_global_class(p_type)) {
+			return true;
 		}
 
 		String script_path = ScriptServer::get_global_class_path(p_type);
-		if (script_path.find("res://addons/", 0) != -1) {
+		if (script_path.begins_with("res://addons/")) {
 			if (!EditorNode::get_singleton()->is_addon_plugin_enabled(script_path.get_slicec('/', 3))) {
-				return;
+				return true; // Plugin is not enabled.
 			}
 		}
 	}
 
-	String inherits = cpp_type ? ClassDB::get_parent_class(p_type) : ed.script_class_get_base(p_type);
-
-	TreeItem *parent = p_root;
+	return false;
+}
 
-	if (inherits.length()) {
-		if (!p_types.has(inherits)) {
-			add_type(inherits, p_types, p_root, to_select);
-		}
+void CreateDialog::_update_search() {
+	search_options->clear();
+	search_options_types.clear();
 
-		if (p_types.has(inherits)) {
-			parent = p_types[inherits];
-		} else if (ScriptServer::is_global_class(inherits)) {
-			return;
-		}
-	}
+	TreeItem *root = search_options->create_item();
+	root->set_text(0, base_type);
+	root->set_icon(0, search_options->get_theme_icon(icon_fallback, "EditorIcons"));
+	search_options_types[base_type] = root;
 
-	bool can_instance = (cpp_type && ClassDB::can_instance(p_type)) || ScriptServer::is_global_class(p_type);
+	const String search_text = search_box->get_text();
+	bool empty_search = search_text == "";
 
-	TreeItem *item = search_options->create_item(parent);
-	if (cpp_type) {
-		item->set_text(0, p_type);
-	} else {
-		item->set_metadata(0, p_type);
-		item->set_text(0, p_type + " (" + ScriptServer::get_global_class_path(p_type).get_file() + ")");
+	// Filter all candidate results.
+	Vector<String> candidates;
+	for (List<StringName>::Element *I = type_list.front(); I; I = I->next()) {
+		if (empty_search || search_text.is_subsequence_ofi(I->get())) {
+			candidates.push_back(I->get());
+		}
 	}
-	if (!can_instance) {
-		item->set_custom_color(0, search_options->get_theme_color("disabled_font_color", "Editor"));
-		item->set_selectable(0, false);
-	} else if (!(*to_select && (*to_select)->get_text(0) == search_box->get_text())) {
-		String search_term = search_box->get_text().to_lower();
-
-		// if the node name matches exactly as the search, the node should be selected.
-		// this also fixes when the user clicks on recent nodes.
-		if (p_type.to_lower() == search_term) {
-			*to_select = item;
-		} else {
-			bool current_type_prefered = _is_type_prefered(p_type);
-			bool selected_type_prefered = *to_select ? _is_type_prefered((*to_select)->get_text(0).split(" ")[0]) : false;
-
-			bool is_subsequence_of_type = search_box->get_text().is_subsequence_ofi(p_type);
-			bool is_substring_of_type = p_type.to_lower().find(search_term) >= 0;
-			bool is_substring_of_selected = false;
-			bool is_subsequence_of_selected = false;
-			bool is_selected_equal = false;
-
-			if (*to_select) {
-				String name = (*to_select)->get_text(0).split(" ")[0].to_lower();
-				is_substring_of_selected = name.find(search_term) >= 0;
-				is_subsequence_of_selected = search_term.is_subsequence_of(name);
-				is_selected_equal = name == search_term;
-			}
 
-			if (is_subsequence_of_type && !is_selected_equal) {
-				if (is_substring_of_type) {
-					if (!is_substring_of_selected || (current_type_prefered && !selected_type_prefered)) {
-						*to_select = item;
-					}
-				} else {
-					// substring results weigh more than subsequences, so let's make sure we don't override them
-					if (!is_substring_of_selected) {
-						if (!is_subsequence_of_selected || (current_type_prefered && !selected_type_prefered)) {
-							*to_select = item;
-						}
-					}
-				}
-			}
-		}
+	// Build the type tree.
+	for (int i = 0; i < candidates.size(); i++) {
+		_add_type(candidates[i], ClassDB::class_exists(candidates[i]));
 	}
 
-	if (bool(EditorSettings::get_singleton()->get("docks/scene_tree/start_create_dialog_fully_expanded"))) {
-		item->set_collapsed(false);
+	// Select the best result.
+	if (empty_search) {
+		select_type(base_type);
+	} else if (candidates.size() > 0) {
+		select_type(_top_result(candidates, search_text));
 	} else {
-		// don't collapse search results
-		bool collapse = (search_box->get_text() == "");
-		// don't collapse the root node
-		collapse &= (item != p_root);
-		// don't collapse abstract nodes on the first tree level
-		collapse &= ((parent != p_root) || (can_instance));
-		item->set_collapsed(collapse);
+		favorite->set_disabled(true);
+		help_bit->set_text("");
+		get_ok()->set_disabled(true);
+		search_options->deselect_all();
 	}
-
-	const String &description = DTR(EditorHelp::get_doc_data()->class_list[p_type].brief_description);
-	item->set_tooltip(0, description);
-
-	String icon_fallback = search_options->has_theme_icon(base_type, "EditorIcons") ? base_type : "Object";
-	item->set_icon(0, EditorNode::get_singleton()->get_class_icon(p_type, icon_fallback));
-
-	p_types[p_type] = item;
 }
 
-bool CreateDialog::_is_type_prefered(const String &type) {
-	bool cpp_type = ClassDB::class_exists(type);
-	EditorData &ed = EditorNode::get_editor_data();
-
-	if (cpp_type) {
-		return ClassDB::is_parent_class(type, preferred_search_result_type);
+void CreateDialog::_add_type(const String &p_type, bool p_cpp_type) {
+	if (search_options_types.has(p_type)) {
+		return;
 	}
-	return ed.script_class_is_parent(type, preferred_search_result_type);
-}
 
-bool CreateDialog::_is_class_disabled_by_feature_profile(const StringName &p_class) {
-	Ref<EditorFeatureProfile> profile = EditorFeatureProfileManager::get_singleton()->get_current_profile();
-	if (profile.is_null()) {
-		return false;
+	String inherits;
+	if (p_cpp_type) {
+		inherits = ClassDB::get_parent_class(p_type);
+	} else if (ScriptServer::is_global_class(p_type)) {
+		inherits = EditorNode::get_editor_data().script_class_get_base(p_type);
+	} else {
+		inherits = custom_type_parents[p_type];
 	}
 
-	return profile->is_class_disabled(p_class);
+	_add_type(inherits, p_cpp_type || ClassDB::class_exists(inherits));
+
+	TreeItem *item = search_options->create_item(search_options_types[inherits]);
+	search_options_types[p_type] = item;
+	_configure_search_option_item(item, p_type, p_cpp_type);
 }
 
-void CreateDialog::select_type(const String &p_type) {
-	TreeItem *to_select;
-	if (search_options_types.has(p_type)) {
-		to_select = search_options_types[p_type];
+void CreateDialog::_configure_search_option_item(TreeItem *r_item, const String &p_type, const bool p_cpp_type) {
+	bool script_type = ScriptServer::is_global_class(p_type);
+	if (p_cpp_type) {
+		r_item->set_text(0, p_type);
+	} else if (script_type) {
+		r_item->set_metadata(0, p_type);
+		r_item->set_text(0, p_type + " (" + ScriptServer::get_global_class_path(p_type).get_file() + ")");
 	} else {
-		to_select = search_options->get_root();
+		r_item->set_metadata(0, custom_type_parents[p_type]);
+		r_item->set_text(0, p_type);
 	}
 
-	// uncollapse from selected type to top level
-	// TODO: should this be in tree?
-	TreeItem *cur = to_select;
-	while (cur) {
-		cur->set_collapsed(false);
-		cur = cur->get_parent();
+	bool can_instance = (p_cpp_type && ClassDB::can_instance(p_type)) || !p_cpp_type;
+	if (!can_instance) {
+		r_item->set_custom_color(0, search_options->get_theme_color("disabled_font_color", "Editor"));
+		r_item->set_selectable(0, false);
 	}
 
-	to_select->select(0);
-
-	search_options->scroll_to_item(to_select);
-}
-
-void CreateDialog::_update_search() {
-	search_options->clear();
-	favorite->set_disabled(true);
-
-	help_bit->set_text("");
-
-	search_options_types.clear();
-
-	TreeItem *root = search_options->create_item();
-	EditorData &ed = EditorNode::get_editor_data();
-
-	root->set_text(0, base_type);
-	String base_icon = search_options->has_theme_icon(base_type, "EditorIcons") ? base_type : "Object";
-	root->set_icon(0, search_options->get_theme_icon(base_icon, "EditorIcons"));
-
-	TreeItem *to_select = search_box->get_text() == base_type ? root : nullptr;
-
-	for (List<StringName>::Element *I = type_list.front(); I; I = I->next()) {
-		String type = I->get();
+	if (search_box->get_text() != "") {
+		r_item->set_collapsed(false);
+	} else {
+		// Don't collapse the root node or an abstract node on the first tree level.
+		bool should_collapse = p_type != base_type && (r_item->get_parent()->get_text(0) != base_type || can_instance);
 
-		if (_is_class_disabled_by_feature_profile(type)) {
-			continue;
+		if (should_collapse && bool(EditorSettings::get_singleton()->get("docks/scene_tree/start_create_dialog_fully_expanded"))) {
+			should_collapse = false; // Collapse all nodes anyway.
 		}
-		bool cpp_type = ClassDB::class_exists(type);
+		r_item->set_collapsed(should_collapse);
+	}
 
-		if (base_type == "Node" && type.begins_with("Editor")) {
-			continue; // do not show editor nodes
-		}
+	const String &description = DTR(EditorHelp::get_doc_data()->class_list[p_type].brief_description);
+	r_item->set_tooltip(0, description);
+	r_item->set_icon(0, EditorNode::get_singleton()->get_class_icon(p_type, icon_fallback));
 
-		if (cpp_type && !ClassDB::can_instance(type)) {
-			continue; // can't create what can't be instanced
+	if (!p_cpp_type && !script_type) {
+		Ref<Texture2D> icon = EditorNode::get_editor_data().get_custom_types()[custom_type_parents[p_type]][custom_type_indices[p_type]].icon;
+		if (icon.is_valid()) {
+			r_item->set_icon(0, icon);
 		}
+	}
+}
 
-		if (cpp_type) {
-			bool skip = false;
-
-			for (Set<StringName>::Element *E = type_blacklist.front(); E && !skip; E = E->next()) {
-				if (ClassDB::is_parent_class(type, E->get())) {
-					skip = true;
-				}
-			}
-			if (skip) {
-				continue;
-			}
+String CreateDialog::_top_result(const Vector<String> p_candidates, const String &p_search_text) const {
+	float highest_score = 0;
+	int highest_index = 0;
+	for (int i = 0; i < p_candidates.size(); i++) {
+		float score = _score_type(p_candidates[i].get_slicec(' ', 0), p_search_text);
+		if (score > highest_score) {
+			highest_score = score;
+			highest_index = i;
 		}
+	}
 
-		if (search_box->get_text() == "") {
-			add_type(type, search_options_types, root, &to_select);
-		} else {
-			bool found = false;
-			String type2 = type;
-			bool cpp_type2 = cpp_type;
-
-			if (!cpp_type && !search_loaded_scripts.has(type)) {
-				search_loaded_scripts[type] = ed.script_class_load_script(type);
-			}
+	return p_candidates[highest_index];
+}
 
-			while (type2 != "" && (cpp_type2 ? ClassDB::is_parent_class(type2, base_type) : ed.script_class_is_parent(type2, base_type)) && type2 != base_type) {
-				if (search_box->get_text().is_subsequence_ofi(type2)) {
-					found = true;
-					break;
-				}
+float CreateDialog::_score_type(const String &p_type, const String &p_search) const {
+	float inverse_length = 1.f / float(p_type.length());
 
-				type2 = cpp_type2 ? ClassDB::get_parent_class(type2) : ed.script_class_get_base(type2);
-				cpp_type2 = cpp_type2 || ClassDB::class_exists(type2); // Built-in class can't inherit from custom type, so we can skip the check if it's already true.
+	// Favor types where search term is a substring close to the start of the type.
+	float w = 0.5f;
+	int pos = p_type.findn(p_search);
+	float score = (pos > -1) ? 1.0f - w * MIN(1, 3 * pos * inverse_length) : MAX(0.f, .9f - w);
 
-				if (!cpp_type2 && !search_loaded_scripts.has(type2)) {
-					search_loaded_scripts[type2] = ed.script_class_load_script(type2);
-				}
-			}
+	// Favor shorter items: they resemble the search term more.
+	w = 0.1f;
+	score *= (1 - w) + w * (p_search.length() * inverse_length);
 
-			if (found) {
-				add_type(type, search_options_types, root, &to_select);
-			}
-		}
+	score *= _is_type_preferred(p_type) ? 1.0f : 0.8f;
 
-		if (EditorNode::get_editor_data().get_custom_types().has(type) && ClassDB::is_parent_class(type, base_type)) {
-			//there are custom types based on this... cool.
+	// Add score for being a favorite type.
+	score *= (favorite_list.find(p_type) > -1) ? 1.0f : 0.7f;
 
-			const Vector<EditorData::CustomType> &ct = EditorNode::get_editor_data().get_custom_types()[type];
-			for (int i = 0; i < ct.size(); i++) {
-				bool show = search_box->get_text().is_subsequence_ofi(ct[i].name);
-
-				if (!show) {
-					continue;
-				}
-
-				if (!search_options_types.has(type)) {
-					add_type(type, search_options_types, root, &to_select);
-				}
-
-				TreeItem *ti;
-				if (search_options_types.has(type)) {
-					ti = search_options_types[type];
-				} else {
-					ti = search_options->get_root();
-				}
-
-				TreeItem *item = search_options->create_item(ti);
-				item->set_metadata(0, type);
-				item->set_text(0, ct[i].name);
-				item->set_icon(0, ct[i].icon.is_valid() ? ct[i].icon : search_options->get_theme_icon(base_icon, "EditorIcons"));
-
-				if (!to_select || ct[i].name == search_box->get_text()) {
-					to_select = item;
-				}
-			}
+	// Look through at most 5 recent items
+	bool in_recent = false;
+	for (int i = 0; i < MIN(5, recent->get_item_count()); i++) {
+		if (recent->get_item_text(i) == p_type) {
+			in_recent = true;
+			break;
 		}
 	}
+	score *= in_recent ? 1.0f : 0.8f;
 
-	if (search_box->get_text() == "") {
-		to_select = root;
-	}
-
-	if (to_select) {
-		to_select->select(0);
-		search_options->scroll_to_item(to_select);
-		favorite->set_disabled(false);
-		favorite->set_pressed(favorite_list.find(to_select->get_text(0)) != -1);
-	}
+	return score;
+}
 
-	get_ok()->set_disabled(root->get_children() == nullptr);
+void CreateDialog::_cleanup() {
+	type_list.clear();
+	favorite_list.clear();
+	favorites->clear();
+	recent->clear();
+	custom_type_parents.clear();
+	custom_type_indices.clear();
 }
 
 void CreateDialog::_confirmed() {
-	TreeItem *ti = search_options->get_selected();
-	if (!ti) {
+	String selected_item = get_selected_type();
+	if (selected_item == String()) {
 		return;
 	}
 
 	FileAccess *f = FileAccess::open(EditorSettings::get_singleton()->get_project_settings_dir().plus_file("create_recent." + base_type), FileAccess::WRITE);
-
 	if (f) {
-		f->store_line(get_selected_type());
-		TreeItem *t = recent->get_root();
-		if (t) {
-			t = t->get_children();
-		}
-		int count = 0;
-		while (t) {
-			if (t->get_text(0) != get_selected_type()) {
-				f->store_line(t->get_text(0));
-			}
+		f->store_line(selected_item);
 
-			if (count > 32) {
-				//limit it to 32 entries..
-				break;
+		for (int i = 0; i < MIN(32, recent->get_item_count()); i++) {
+			if (recent->get_item_text(i) != selected_item) {
+				f->store_line(recent->get_item_text(i));
 			}
-			t = t->get_next();
-			count++;
 		}
 
 		memdelete(f);
@@ -453,6 +337,26 @@ void CreateDialog::_confirmed() {
 
 	emit_signal("create");
 	hide();
+	_cleanup();
+}
+
+void CreateDialog::_text_changed(const String &p_newtext) {
+	_update_search();
+}
+
+void CreateDialog::_sbox_input(const Ref<InputEvent> &p_ie) {
+	Ref<InputEventKey> k = p_ie;
+	if (k.is_valid()) {
+		switch (k->get_keycode()) {
+			case KEY_UP:
+			case KEY_DOWN:
+			case KEY_PAGEUP:
+			case KEY_PAGEDOWN: {
+				search_options->call("_gui_input", k);
+				search_box->accept_event();
+			} break;
+		}
+	}
 }
 
 void CreateDialog::_notification(int p_what) {
@@ -472,42 +376,36 @@ void CreateDialog::_notification(int p_what) {
 				search_box->select_all();
 			} else {
 				EditorSettings::get_singleton()->get_project_metadata("dialog_bounds", "create_new_node", Rect2(get_position(), get_size()));
-				search_loaded_scripts.clear();
 			}
 		} break;
 	}
 }
 
-void CreateDialog::set_base_type(const String &p_base) {
-	base_type = p_base;
-	if (is_replace_mode) {
-		set_title(vformat(TTR("Change %s Type"), p_base));
-	} else {
-		set_title(vformat(TTR("Create New %s"), p_base));
+void CreateDialog::select_type(const String &p_type) {
+	if (!search_options_types.has(p_type)) {
+		return;
 	}
 
-	_update_search();
-}
-
-String CreateDialog::get_base_type() const {
-	return base_type;
-}
+	TreeItem *to_select = search_options_types[p_type];
+	to_select->select(0);
+	search_options->scroll_to_item(to_select);
 
-void CreateDialog::set_preferred_search_result_type(const String &p_preferred_type) {
-	preferred_search_result_type = p_preferred_type;
-}
+	if (EditorHelp::get_doc_data()->class_list.has(p_type)) {
+		help_bit->set_text(DTR(EditorHelp::get_doc_data()->class_list[p_type].brief_description));
+	}
 
-String CreateDialog::get_preferred_search_result_type() {
-	return preferred_search_result_type;
+	favorite->set_disabled(false);
+	favorite->set_pressed(favorite_list.find(p_type) != -1);
+	get_ok()->set_disabled(false);
 }
 
 String CreateDialog::get_selected_type() {
 	TreeItem *selected = search_options->get_selected();
-	if (selected) {
-		return selected->get_text(0);
-	} else {
+	if (!selected) {
 		return String();
 	}
+
+	return selected->get_text(0);
 }
 
 Object *CreateDialog::instance_selected() {
@@ -518,14 +416,9 @@ Object *CreateDialog::instance_selected() {
 	}
 
 	Variant md = selected->get_metadata(0);
-	String custom;
-	if (md.get_type() != Variant::NIL) {
-		custom = md;
-	}
-
 	Object *obj = nullptr;
-
-	if (!custom.empty()) {
+	if (md.get_type() != Variant::NIL) {
+		String custom = md;
 		if (ScriptServer::is_global_class(custom)) {
 			obj = EditorNode::get_editor_data().script_class_instance(custom);
 			Node *n = Object::cast_to<Node>(obj);
@@ -545,9 +438,10 @@ Object *CreateDialog::instance_selected() {
 	obj->get_property_list(&pinfo);
 
 	for (List<PropertyInfo>::Element *E = pinfo.front(); E; E = E->next()) {
-		if (E->get().type == Variant::OBJECT && E->get().usage & PROPERTY_USAGE_EDITOR_INSTANTIATE_OBJECT) {
-			Object *prop = ClassDB::instance(E->get().class_name);
-			obj->set(E->get().name, prop);
+		PropertyInfo pi = E->get();
+		if (pi.type == Variant::OBJECT && pi.usage & PROPERTY_USAGE_EDITOR_INSTANTIATE_OBJECT) {
+			Object *prop = ClassDB::instance(pi.class_name);
+			obj->set(pi.name, prop);
 		}
 	}
 
@@ -555,29 +449,18 @@ Object *CreateDialog::instance_selected() {
 }
 
 void CreateDialog::_item_selected() {
-	TreeItem *item = search_options->get_selected();
-	if (!item) {
-		return;
-	}
-
-	String name = item->get_text(0);
-
-	favorite->set_disabled(false);
-	favorite->set_pressed(favorite_list.find(name) != -1);
-
-	if (!EditorHelp::get_doc_data()->class_list.has(name)) {
-		return;
-	}
-
-	help_bit->set_text(DTR(EditorHelp::get_doc_data()->class_list[name].brief_description));
-
-	get_ok()->set_disabled(false);
+	String name = get_selected_type();
+	select_type(name);
 }
 
 void CreateDialog::_hide_requested() {
 	_cancel_pressed(); // From AcceptDialog.
 }
 
+void CreateDialog::cancel_pressed() {
+	_cleanup();
+}
+
 void CreateDialog::_favorite_toggled() {
 	TreeItem *item = search_options->get_selected();
 	if (!item) {
@@ -597,50 +480,8 @@ void CreateDialog::_favorite_toggled() {
 	_save_and_update_favorite_list();
 }
 
-void CreateDialog::_save_favorite_list() {
-	FileAccess *f = FileAccess::open(EditorSettings::get_singleton()->get_project_settings_dir().plus_file("favorites." + base_type), FileAccess::WRITE);
-
-	if (f) {
-		for (int i = 0; i < favorite_list.size(); i++) {
-			String l = favorite_list[i];
-			String name = l.split(" ")[0];
-			if (!(ClassDB::class_exists(name) || ScriptServer::is_global_class(name))) {
-				continue;
-			}
-			f->store_line(l);
-		}
-		memdelete(f);
-	}
-}
-
-void CreateDialog::_update_favorite_list() {
-	favorites->clear();
-
-	TreeItem *root = favorites->create_item();
-
-	String icon_fallback = search_options->has_theme_icon(base_type, "EditorIcons") ? base_type : "Object";
-
-	for (int i = 0; i < favorite_list.size(); i++) {
-		String l = favorite_list[i];
-		String name = l.split(" ")[0];
-		if (!((ClassDB::class_exists(name) || ScriptServer::is_global_class(name)) && !_is_class_disabled_by_feature_profile(name))) {
-			continue;
-		}
-
-		TreeItem *ti = favorites->create_item(root);
-		ti->set_text(0, l);
-		ti->set_icon(0, EditorNode::get_singleton()->get_class_icon(name, icon_fallback));
-	}
-	emit_signal("favorites_updated");
-}
-
-void CreateDialog::_history_selected() {
-	TreeItem *item = recent->get_selected();
-	if (!item) {
-		return;
-	}
-
-	search_box->set_text(item->get_text(0).get_slicec(' ', 0));
+void CreateDialog::_history_selected(int p_idx) {
+	search_box->set_text(recent->get_item_text(p_idx).get_slicec(' ', 0));
 	favorites->deselect_all();
 	_update_search();
 }
@@ -652,12 +493,12 @@ void CreateDialog::_favorite_selected() {
 	}
 
 	search_box->set_text(item->get_text(0).get_slicec(' ', 0));
-	recent->deselect_all();
+	recent->unselect_all();
 	_update_search();
 }
 
-void CreateDialog::_history_activated() {
-	_history_selected();
+void CreateDialog::_history_activated(int p_idx) {
+	_history_selected(p_idx);
 	_confirmed();
 }
 
@@ -740,8 +581,61 @@ void CreateDialog::drop_data_fw(const Point2 &p_point, const Variant &p_data, Co
 }
 
 void CreateDialog::_save_and_update_favorite_list() {
-	_save_favorite_list();
-	_update_favorite_list();
+	favorites->clear();
+	TreeItem *root = favorites->create_item();
+
+	FileAccess *f = FileAccess::open(EditorSettings::get_singleton()->get_project_settings_dir().plus_file("favorites." + base_type), FileAccess::WRITE);
+	if (f) {
+		for (int i = 0; i < favorite_list.size(); i++) {
+			String l = favorite_list[i];
+			String name = l.get_slicec(' ', 0);
+			if (!(ClassDB::class_exists(name) || ScriptServer::is_global_class(name))) {
+				continue;
+			}
+			f->store_line(l);
+
+			if (_is_class_disabled_by_feature_profile(name)) {
+				continue;
+			}
+
+			TreeItem *ti = favorites->create_item(root);
+			ti->set_text(0, l);
+			ti->set_icon(0, EditorNode::get_singleton()->get_class_icon(name, icon_fallback));
+		}
+		memdelete(f);
+	}
+
+	emit_signal("favorites_updated");
+}
+
+void CreateDialog::_load_favorites_and_history() {
+	String dir = EditorSettings::get_singleton()->get_project_settings_dir();
+	FileAccess *f = FileAccess::open(dir.plus_file("create_recent." + base_type), FileAccess::READ);
+	if (f) {
+		while (!f->eof_reached()) {
+			String l = f->get_line().strip_edges();
+			String name = l.get_slicec(' ', 0);
+
+			if ((ClassDB::class_exists(name) || ScriptServer::is_global_class(name)) && !_is_class_disabled_by_feature_profile(name)) {
+				recent->add_item(l, EditorNode::get_singleton()->get_class_icon(name, icon_fallback));
+			}
+		}
+
+		memdelete(f);
+	}
+
+	f = FileAccess::open(dir.plus_file("favorites." + base_type), FileAccess::READ);
+	if (f) {
+		while (!f->eof_reached()) {
+			String l = f->get_line().strip_edges();
+
+			if (l != String()) {
+				favorite_list.push_back(l);
+			}
+		}
+
+		memdelete(f);
+	}
 }
 
 void CreateDialog::_bind_methods() {
@@ -756,7 +650,11 @@ void CreateDialog::_bind_methods() {
 }
 
 CreateDialog::CreateDialog() {
-	is_replace_mode = false;
+	base_type = "Object";
+	preferred_search_result_type = "";
+
+	type_blacklist.insert("PluginScript"); // PluginScript must be initialized before use, which is not possible here.
+	type_blacklist.insert("ScriptCreateDialog"); // This is an exposed editor Node that doesn't have an Editor prefix.
 
 	HSplitContainer *hsc = memnew(HSplitContainer);
 	add_child(hsc);
@@ -765,67 +663,64 @@ CreateDialog::CreateDialog() {
 	hsc->add_child(vsc);
 
 	VBoxContainer *fav_vb = memnew(VBoxContainer);
-	vsc->add_child(fav_vb);
 	fav_vb->set_custom_minimum_size(Size2(150, 100) * EDSCALE);
 	fav_vb->set_v_size_flags(Control::SIZE_EXPAND_FILL);
+	vsc->add_child(fav_vb);
 
 	favorites = memnew(Tree);
-	fav_vb->add_margin_child(TTR("Favorites:"), favorites, true);
 	favorites->set_hide_root(true);
 	favorites->set_hide_folding(true);
 	favorites->set_allow_reselect(true);
 	favorites->connect("cell_selected", callable_mp(this, &CreateDialog::_favorite_selected));
 	favorites->connect("item_activated", callable_mp(this, &CreateDialog::_favorite_activated));
+	favorites->add_theme_constant_override("draw_guides", 1);
 #ifndef _MSC_VER
 #warning cant forward drag data to a non control, must be fixed
 #endif
 	//favorites->set_drag_forwarding(this);
-	favorites->add_theme_constant_override("draw_guides", 1);
+	fav_vb->add_margin_child(TTR("Favorites:"), favorites, true);
 
 	VBoxContainer *rec_vb = memnew(VBoxContainer);
 	vsc->add_child(rec_vb);
 	rec_vb->set_custom_minimum_size(Size2(150, 100) * EDSCALE);
 	rec_vb->set_v_size_flags(Control::SIZE_EXPAND_FILL);
 
-	recent = memnew(Tree);
+	recent = memnew(ItemList);
 	rec_vb->add_margin_child(TTR("Recent:"), recent, true);
-	recent->set_hide_root(true);
-	recent->set_hide_folding(true);
 	recent->set_allow_reselect(true);
-	recent->connect("cell_selected", callable_mp(this, &CreateDialog::_history_selected));
+	recent->connect("item_selected", callable_mp(this, &CreateDialog::_history_selected));
 	recent->connect("item_activated", callable_mp(this, &CreateDialog::_history_activated));
 	recent->add_theme_constant_override("draw_guides", 1);
 
 	VBoxContainer *vbc = memnew(VBoxContainer);
-	hsc->add_child(vbc);
 	vbc->set_custom_minimum_size(Size2(300, 0) * EDSCALE);
 	vbc->set_h_size_flags(Control::SIZE_EXPAND_FILL);
-	HBoxContainer *search_hb = memnew(HBoxContainer);
+	hsc->add_child(vbc);
+
 	search_box = memnew(LineEdit);
 	search_box->set_h_size_flags(Control::SIZE_EXPAND_FILL);
+	search_box->connect("text_changed", callable_mp(this, &CreateDialog::_text_changed));
+	search_box->connect("gui_input", callable_mp(this, &CreateDialog::_sbox_input));
+
+	HBoxContainer *search_hb = memnew(HBoxContainer);
 	search_hb->add_child(search_box);
+
 	favorite = memnew(Button);
 	favorite->set_flat(true);
 	favorite->set_toggle_mode(true);
-	search_hb->add_child(favorite);
 	favorite->connect("pressed", callable_mp(this, &CreateDialog::_favorite_toggled));
+	search_hb->add_child(favorite);
 	vbc->add_margin_child(TTR("Search:"), search_hb);
-	search_box->connect("text_changed", callable_mp(this, &CreateDialog::_text_changed));
-	search_box->connect("gui_input", callable_mp(this, &CreateDialog::_sbox_input));
+
 	search_options = memnew(Tree);
-	vbc->add_margin_child(TTR("Matches:"), search_options, true);
-	get_ok()->set_disabled(true);
-	register_text_enter(search_box);
-	set_hide_on_ok(false);
 	search_options->connect("item_activated", callable_mp(this, &CreateDialog::_confirmed));
 	search_options->connect("cell_selected", callable_mp(this, &CreateDialog::_item_selected));
-	base_type = "Object";
-	preferred_search_result_type = "";
+	vbc->add_margin_child(TTR("Matches:"), search_options, true);
 
 	help_bit = memnew(EditorHelpBit);
-	vbc->add_margin_child(TTR("Description:"), help_bit);
 	help_bit->connect("request_hide", callable_mp(this, &CreateDialog::_hide_requested));
+	vbc->add_margin_child(TTR("Description:"), help_bit);
 
-	type_blacklist.insert("PluginScript"); // PluginScript must be initialized before use, which is not possible here
-	type_blacklist.insert("ScriptCreateDialog"); // This is an exposed editor Node that doesn't have an Editor prefix.
+	register_text_enter(search_box);
+	set_hide_on_ok(false);
 }
diff --git a/editor/create_dialog.h b/editor/create_dialog.h
index cdc91ae535..52eb9945af 100644
--- a/editor/create_dialog.h
+++ b/editor/create_dialog.h
@@ -35,60 +35,65 @@
 #include "scene/gui/button.h"
 #include "scene/gui/dialogs.h"
 #include "scene/gui/item_list.h"
-#include "scene/gui/label.h"
 #include "scene/gui/line_edit.h"
 #include "scene/gui/tree.h"
 
 class CreateDialog : public ConfirmationDialog {
 	GDCLASS(CreateDialog, ConfirmationDialog);
 
-	Vector<String> favorite_list;
-	Tree *favorites;
-	Tree *recent;
-
-	Button *favorite;
 	LineEdit *search_box;
 	Tree *search_options;
-	HashMap<String, TreeItem *> search_options_types;
-	HashMap<String, RES> search_loaded_scripts;
-	bool is_replace_mode;
+
 	String base_type;
+	String icon_fallback;
 	String preferred_search_result_type;
+
+	Button *favorite;
+	Vector<String> favorite_list;
+	Tree *favorites;
+	ItemList *recent;
 	EditorHelpBit *help_bit;
+
+	HashMap<String, TreeItem *> search_options_types;
+	HashMap<String, String> custom_type_parents;
+	HashMap<String, int> custom_type_indices;
 	List<StringName> type_list;
 	Set<StringName> type_blacklist;
 
-	void _item_selected();
-	void _hide_requested();
-
 	void _update_search();
-	void _update_favorite_list();
-	void _save_favorite_list();
-	void _favorite_toggled();
+	bool _should_hide_type(const String &p_type) const;
+	void _add_type(const String &p_current, bool p_cpp_type);
+	void _configure_search_option_item(TreeItem *r_item, const String &p_type, const bool p_cpp_type);
+	String _top_result(const Vector<String> p_candidates, const String &p_search_text) const;
+	float _score_type(const String &p_type, const String &p_search) const;
+	bool _is_type_preferred(const String &p_type) const;
 
-	void _history_selected();
-	void _favorite_selected();
-
-	void _history_activated();
-	void _favorite_activated();
+	void _fill_type_list();
+	void _cleanup();
 
 	void _sbox_input(const Ref<InputEvent> &p_ie);
+	void _text_changed(const String &p_newtext);
+	void select_type(const String &p_type);
+	void _item_selected();
+	void _hide_requested();
 
 	void _confirmed();
-	void _text_changed(const String &p_newtext);
+	virtual void cancel_pressed();
 
-	Ref<Texture2D> _get_editor_icon(const String &p_type) const;
+	void _favorite_toggled();
 
-	void add_type(const String &p_type, HashMap<String, TreeItem *> &p_types, TreeItem *p_root, TreeItem **to_select);
+	void _history_selected(int p_idx);
+	void _favorite_selected();
 
-	void select_type(const String &p_type);
+	void _history_activated(int p_idx);
+	void _favorite_activated();
 
 	Variant get_drag_data_fw(const Point2 &p_point, Control *p_from);
 	bool can_drop_data_fw(const Point2 &p_point, const Variant &p_data, Control *p_from) const;
 	void drop_data_fw(const Point2 &p_point, const Variant &p_data, Control *p_from);
 
-	bool _is_class_disabled_by_feature_profile(const StringName &p_class);
-	bool _is_type_prefered(const String &type);
+	bool _is_class_disabled_by_feature_profile(const StringName &p_class) const;
+	void _load_favorites_and_history();
 
 protected:
 	void _notification(int p_what);
@@ -100,11 +105,11 @@ public:
 	Object *instance_selected();
 	String get_selected_type();
 
-	void set_base_type(const String &p_base);
-	String get_base_type() const;
+	void set_base_type(const String &p_base) { base_type = p_base; }
+	String get_base_type() const { return base_type; }
 
-	void set_preferred_search_result_type(const String &p_preferred_type);
-	String get_preferred_search_result_type();
+	void set_preferred_search_result_type(const String &p_preferred_type) { preferred_search_result_type = p_preferred_type; }
+	String get_preferred_search_result_type() { return preferred_search_result_type; }
 
 	void popup_create(bool p_dont_clear, bool p_replace_mode = false, const String &p_select_type = "Node");