Merge pull request #50319 from nekomatata/optimize-node-path-check

Optimize NodePath update when renaming or deleting nodes in the editor

3 files changed, 110 insertions, 124 deletions

diff --git a/core/string/node_path.cpp b/core/string/node_path.cpp
index d3afa7b4dd..5fae13779e 100644
--- a/core/string/node_path.cpp
+++ b/core/string/node_path.cpp
@@ -240,19 +240,26 @@ NodePath NodePath::rel_path_to(const NodePath &p_np) const {
 	common_parent--;
 
 	Vector<StringName> relpath;
+	relpath.resize(src_dirs.size() + dst_dirs.size() + 1);
 
-	for (int i = src_dirs.size() - 1; i > common_parent; i--) {
-		relpath.push_back("..");
+	StringName *relpath_ptr = relpath.ptrw();
+
+	int path_size = 0;
+	StringName back_str("..");
+	for (int i = common_parent + 1; i < src_dirs.size(); i++) {
+		relpath_ptr[path_size++] = back_str;
 	}
 
 	for (int i = common_parent + 1; i < dst_dirs.size(); i++) {
-		relpath.push_back(dst_dirs[i]);
+		relpath_ptr[path_size++] = dst_dirs[i];
 	}
 
-	if (relpath.size() == 0) {
-		relpath.push_back(".");
+	if (path_size == 0) {
+		relpath_ptr[path_size++] = ".";
 	}
 
+	relpath.resize(path_size);
+
 	return NodePath(relpath, p_np.get_subnames(), false);
 }
 
diff --git a/editor/scene_tree_dock.cpp b/editor/scene_tree_dock.cpp
index 6d1deb86c6..f453f4102d 100644
--- a/editor/scene_tree_dock.cpp
+++ b/editor/scene_tree_dock.cpp
@@ -1384,30 +1384,25 @@ void SceneTreeDock::_set_owners(Node *p_owner, const Array &p_nodes) {
 	}
 }
 
-void SceneTreeDock::_fill_path_renames(Vector<StringName> base_path, Vector<StringName> new_base_path, Node *p_node, List<Pair<NodePath, NodePath>> *p_renames) {
+void SceneTreeDock::_fill_path_renames(Vector<StringName> base_path, Vector<StringName> new_base_path, Node *p_node, Map<Node *, NodePath> *p_renames) {
 	base_path.push_back(p_node->get_name());
 	if (new_base_path.size()) {
 		new_base_path.push_back(p_node->get_name());
 	}
 
-	NodePath from(base_path, true);
-	NodePath to;
+	NodePath new_path;
 	if (new_base_path.size()) {
-		to = NodePath(new_base_path, true);
+		new_path = NodePath(new_base_path, true);
 	}
 
-	Pair<NodePath, NodePath> npp;
-	npp.first = from;
-	npp.second = to;
-
-	p_renames->push_back(npp);
+	p_renames->insert(p_node, new_path);
 
 	for (int i = 0; i < p_node->get_child_count(); i++) {
 		_fill_path_renames(base_path, new_base_path, p_node->get_child(i), p_renames);
 	}
 }
 
-void SceneTreeDock::fill_path_renames(Node *p_node, Node *p_new_parent, List<Pair<NodePath, NodePath>> *p_renames) {
+void SceneTreeDock::fill_path_renames(Node *p_node, Node *p_new_parent, Map<Node *, NodePath> *p_renames) {
 	Vector<StringName> base_path;
 	Node *n = p_node->get_parent();
 	while (n) {
@@ -1430,50 +1425,41 @@ void SceneTreeDock::fill_path_renames(Node *p_node, Node *p_new_parent, List<Pai
 	_fill_path_renames(base_path, new_base_path, p_node, p_renames);
 }
 
-bool SceneTreeDock::_update_node_path(const NodePath &p_root_path, NodePath &r_node_path, List<Pair<NodePath, NodePath>> *p_renames) {
-	NodePath root_path_new = p_root_path;
-	for (List<Pair<NodePath, NodePath>>::Element *F = p_renames->front(); F; F = F->next()) {
-		if (p_root_path == F->get().first) {
-			root_path_new = F->get().second;
-			break;
-		}
-	}
-
-	// Goes through all paths to check if it's matching.
-	for (List<Pair<NodePath, NodePath>>::Element *F = p_renames->front(); F; F = F->next()) {
-		NodePath rel_path_old = p_root_path.rel_path_to(F->get().first);
+bool SceneTreeDock::_update_node_path(Node *p_root_node, NodePath &r_node_path, Map<Node *, NodePath> *p_renames) const {
+	Node *target_node = p_root_node->get_node_or_null(r_node_path);
+	ERR_FAIL_NULL_V_MSG(target_node, false, "Found invalid node path '" + String(r_node_path) + "' on node '" + String(scene_root->get_path_to(p_root_node)) + "'");
 
-		// If old path detected, then it needs to be replaced with the new one.
-		if (r_node_path == rel_path_old) {
-			NodePath rel_path_new = F->get().second;
+	// Try to find the target node in modified node paths.
+	Map<Node *, NodePath>::Element *found_node_path = p_renames->find(target_node);
+	if (found_node_path) {
+		Map<Node *, NodePath>::Element *found_root_path = p_renames->find(p_root_node);
+		NodePath root_path_new = found_root_path ? found_root_path->get() : p_root_node->get_path();
+		r_node_path = root_path_new.rel_path_to(found_node_path->get());
 
-			// If not empty, get new relative path.
-			if (!rel_path_new.is_empty()) {
-				rel_path_new = root_path_new.rel_path_to(rel_path_new);
-			}
+		return true;
+	}
 
-			r_node_path = rel_path_new;
-			return true;
+	// Update the path if the base node has changed and has not been deleted.
+	Map<Node *, NodePath>::Element *found_root_path = p_renames->find(p_root_node);
+	if (found_root_path) {
+		NodePath root_path_new = found_root_path->get();
+		if (!root_path_new.is_empty()) {
+			NodePath old_abs_path = NodePath(String(p_root_node->get_path()).plus_file(r_node_path));
+			old_abs_path.simplify();
+			r_node_path = root_path_new.rel_path_to(old_abs_path);
 		}
 
-		// Update the node itself if it has a valid node path and has not been deleted.
-		if (p_root_path == F->get().first && r_node_path != NodePath() && F->get().second != NodePath()) {
-			NodePath abs_path = NodePath(String(root_path_new).plus_file(r_node_path)).simplified();
-			NodePath rel_path_new = F->get().second.rel_path_to(abs_path);
-
-			r_node_path = rel_path_new;
-			return true;
-		}
+		return true;
 	}
 
 	return false;
 }
 
-bool SceneTreeDock::_check_node_path_recursive(const NodePath &p_root_path, Variant &r_variant, List<Pair<NodePath, NodePath>> *p_renames) {
+bool SceneTreeDock::_check_node_path_recursive(Node *p_root_node, Variant &r_variant, Map<Node *, NodePath> *p_renames) const {
 	switch (r_variant.get_type()) {
 		case Variant::NODE_PATH: {
 			NodePath node_path = r_variant;
-			if (_update_node_path(p_root_path, node_path, p_renames)) {
+			if (!node_path.is_empty() && _update_node_path(p_root_node, node_path, p_renames)) {
 				r_variant = node_path;
 				return true;
 			}
@@ -1484,7 +1470,7 @@ bool SceneTreeDock::_check_node_path_recursive(const NodePath &p_root_path, Vari
 			bool updated = false;
 			for (int i = 0; i < a.size(); i++) {
 				Variant value = a[i];
-				if (_check_node_path_recursive(p_root_path, value, p_renames)) {
+				if (_check_node_path_recursive(p_root_node, value, p_renames)) {
 					if (!updated) {
 						a = a.duplicate(); // Need to duplicate for undo-redo to work.
 						updated = true;
@@ -1503,7 +1489,7 @@ bool SceneTreeDock::_check_node_path_recursive(const NodePath &p_root_path, Vari
 			bool updated = false;
 			for (int i = 0; i < d.size(); i++) {
 				Variant value = d.get_value_at_index(i);
-				if (_check_node_path_recursive(p_root_path, value, p_renames)) {
+				if (_check_node_path_recursive(p_root_node, value, p_renames)) {
 					if (!updated) {
 						d = d.duplicate(); // Need to duplicate for undo-redo to work.
 						updated = true;
@@ -1524,7 +1510,7 @@ bool SceneTreeDock::_check_node_path_recursive(const NodePath &p_root_path, Vari
 	return false;
 }
 
-void SceneTreeDock::perform_node_renames(Node *p_base, List<Pair<NodePath, NodePath>> *p_renames, Map<Ref<Animation>, Set<int>> *r_rem_anims) {
+void SceneTreeDock::perform_node_renames(Node *p_base, Map<Node *, NodePath> *p_renames, Map<Ref<Animation>, Set<int>> *r_rem_anims) {
 	Map<Ref<Animation>, Set<int>> rem_anims;
 	if (!r_rem_anims) {
 		r_rem_anims = &rem_anims;
@@ -1538,10 +1524,15 @@ void SceneTreeDock::perform_node_renames(Node *p_base, List<Pair<NodePath, NodeP
 		return;
 	}
 
+	// No renaming if base node is deleted.
+	Map<Node *, NodePath>::Element *found_base_path = p_renames->find(p_base);
+	if (found_base_path && found_base_path->get().is_empty()) {
+		return;
+	}
+
 	// Renaming node paths used in node properties.
 	List<PropertyInfo> properties;
 	p_base->get_property_list(&properties);
-	NodePath base_root_path = p_base->get_path();
 
 	for (List<PropertyInfo>::Element *E = properties.front(); E; E = E->next()) {
 		if (!(E->get().usage & (PROPERTY_USAGE_STORAGE | PROPERTY_USAGE_EDITOR))) {
@@ -1550,7 +1541,7 @@ void SceneTreeDock::perform_node_renames(Node *p_base, List<Pair<NodePath, NodeP
 		String propertyname = E->get().name;
 		Variant old_variant = p_base->get(propertyname);
 		Variant updated_variant = old_variant;
-		if (_check_node_path_recursive(base_root_path, updated_variant, p_renames)) {
+		if (_check_node_path_recursive(p_base, updated_variant, p_renames)) {
 			editor_data->get_undo_redo().add_do_property(p_base, propertyname, updated_variant);
 			editor_data->get_undo_redo().add_undo_property(p_base, propertyname, old_variant);
 			p_base->set(propertyname, updated_variant);
@@ -1566,19 +1557,9 @@ void SceneTreeDock::perform_node_renames(Node *p_base, List<Pair<NodePath, NodeP
 		Node *root = ap->get_node(ap->get_root());
 
 		if (root) {
-			NodePath root_path = root->get_path();
-			NodePath new_root_path = root_path;
-
-			for (List<Pair<NodePath, NodePath>>::Element *E = p_renames->front(); E; E = E->next()) {
-				if (E->get().first == root_path) {
-					new_root_path = E->get().second;
-					break;
-				}
-			}
-
-			if (new_root_path != NodePath()) {
-				//will not be erased
-
+			Map<Node *, NodePath>::Element *found_root_path = p_renames->find(root);
+			NodePath new_root_path = found_root_path ? found_root_path->get() : root->get_path();
+			if (!new_root_path.is_empty()) { // No renaming if root node is deleted.
 				for (List<StringName>::Element *E = anims.front(); E; E = E->next()) {
 					Ref<Animation> anim = ap->get_animation(E->get());
 					if (!r_rem_anims->has(anim)) {
@@ -1602,47 +1583,44 @@ void SceneTreeDock::perform_node_renames(Node *p_base, List<Pair<NodePath, NodeP
 							continue;
 						}
 
-						NodePath old_np = n->get_path();
-
 						if (!ran.has(i)) {
 							continue; //channel was removed
 						}
 
-						for (List<Pair<NodePath, NodePath>>::Element *F = p_renames->front(); F; F = F->next()) {
-							if (F->get().first == old_np) {
-								if (F->get().second == NodePath()) {
-									//will be erased
-
-									int idx = 0;
-									Set<int>::Element *EI = ran.front();
-									ERR_FAIL_COND(!EI); //bug
-									while (EI->get() != i) {
-										idx++;
-										EI = EI->next();
-										ERR_FAIL_COND(!EI); //another bug
-									}
-
-									editor_data->get_undo_redo().add_do_method(anim.ptr(), "remove_track", idx);
-									editor_data->get_undo_redo().add_undo_method(anim.ptr(), "add_track", anim->track_get_type(i), idx);
-									editor_data->get_undo_redo().add_undo_method(anim.ptr(), "track_set_path", idx, track_np);
-									editor_data->get_undo_redo().add_undo_method(anim.ptr(), "track_set_interpolation_type", idx, anim->track_get_interpolation_type(i));
-									for (int j = 0; j < anim->track_get_key_count(i); j++) {
-										editor_data->get_undo_redo().add_undo_method(anim.ptr(), "track_insert_key", idx, anim->track_get_key_time(i, j), anim->track_get_key_value(i, j), anim->track_get_key_transition(i, j));
-									}
-
-									ran.erase(i); //byebye channel
-
-								} else {
-									//will be renamed
-									NodePath rel_path = new_root_path.rel_path_to(F->get().second);
-
-									NodePath new_path = NodePath(rel_path.get_names(), track_np.get_subnames(), false);
-									if (new_path == track_np) {
-										continue; //bleh
-									}
-									editor_data->get_undo_redo().add_do_method(anim.ptr(), "track_set_path", i, new_path);
-									editor_data->get_undo_redo().add_undo_method(anim.ptr(), "track_set_path", i, track_np);
+						Map<Node *, NodePath>::Element *found_path = p_renames->find(n);
+						if (found_path) {
+							if (found_path->get() == NodePath()) {
+								//will be erased
+
+								int idx = 0;
+								Set<int>::Element *EI = ran.front();
+								ERR_FAIL_COND(!EI); //bug
+								while (EI->get() != i) {
+									idx++;
+									EI = EI->next();
+									ERR_FAIL_COND(!EI); //another bug
+								}
+
+								editor_data->get_undo_redo().add_do_method(anim.ptr(), "remove_track", idx);
+								editor_data->get_undo_redo().add_undo_method(anim.ptr(), "add_track", anim->track_get_type(i), idx);
+								editor_data->get_undo_redo().add_undo_method(anim.ptr(), "track_set_path", idx, track_np);
+								editor_data->get_undo_redo().add_undo_method(anim.ptr(), "track_set_interpolation_type", idx, anim->track_get_interpolation_type(i));
+								for (int j = 0; j < anim->track_get_key_count(i); j++) {
+									editor_data->get_undo_redo().add_undo_method(anim.ptr(), "track_insert_key", idx, anim->track_get_key_time(i, j), anim->track_get_key_value(i, j), anim->track_get_key_transition(i, j));
 								}
+
+								ran.erase(i); //byebye channel
+
+							} else {
+								//will be renamed
+								NodePath rel_path = new_root_path.rel_path_to(found_path->get());
+
+								NodePath new_path = NodePath(rel_path.get_names(), track_np.get_subnames(), false);
+								if (new_path == track_np) {
+									continue; //bleh
+								}
+								editor_data->get_undo_redo().add_do_method(anim.ptr(), "track_set_path", i, new_path);
+								editor_data->get_undo_redo().add_undo_method(anim.ptr(), "track_set_path", i, track_np);
 							}
 						}
 					}
@@ -1657,7 +1635,7 @@ void SceneTreeDock::perform_node_renames(Node *p_base, List<Pair<NodePath, NodeP
 }
 
 void SceneTreeDock::_node_prerenamed(Node *p_node, const String &p_new_name) {
-	List<Pair<NodePath, NodePath>> path_renames;
+	Map<Node *, NodePath> path_renames;
 
 	Vector<StringName> base_path;
 	Node *n = p_node->get_parent();
@@ -1672,10 +1650,8 @@ void SceneTreeDock::_node_prerenamed(Node *p_node, const String &p_new_name) {
 
 	new_base_path.push_back(p_new_name);
 
-	Pair<NodePath, NodePath> npp;
-	npp.first = NodePath(base_path, true);
-	npp.second = NodePath(new_base_path, true);
-	path_renames.push_back(npp);
+	NodePath new_path(new_base_path, true);
+	path_renames[p_node] = new_path;
 
 	for (int i = 0; i < p_node->get_child_count(); i++) {
 		_fill_path_renames(base_path, new_base_path, p_node->get_child(i), &path_renames);
@@ -1780,7 +1756,7 @@ void SceneTreeDock::_do_reparent(Node *p_new_parent, int p_position_in_parent, V
 
 	editor_data->get_undo_redo().create_action(TTR("Reparent Node"));
 
-	List<Pair<NodePath, NodePath>> path_renames;
+	Map<Node *, NodePath> path_renames;
 	Vector<StringName> former_names;
 
 	int inc = 0;
@@ -1817,21 +1793,24 @@ void SceneTreeDock::_do_reparent(Node *p_new_parent, int p_position_in_parent, V
 		// Name was modified, fix the path renames.
 		if (old_name.casecmp_to(new_name) != 0) {
 			// Fix the to name to have the new name.
-			NodePath old_new_name = path_renames[ni].second;
-			NodePath new_path;
-
-			Vector<StringName> unfixed_new_names = old_new_name.get_names();
-			Vector<StringName> fixed_new_names;
+			Map<Node *, NodePath>::Element *found_path = path_renames.find(node);
+			if (found_path) {
+				NodePath old_new_name = found_path->get();
 
-			// Get last name and replace with fixed new name.
-			for (int a = 0; a < (unfixed_new_names.size() - 1); a++) {
-				fixed_new_names.push_back(unfixed_new_names[a]);
-			}
-			fixed_new_names.push_back(new_name);
+				Vector<StringName> unfixed_new_names = old_new_name.get_names();
+				Vector<StringName> fixed_new_names;
 
-			NodePath fixed_node_path = NodePath(fixed_new_names, true);
+				// Get last name and replace with fixed new name.
+				for (int a = 0; a < (unfixed_new_names.size() - 1); a++) {
+					fixed_new_names.push_back(unfixed_new_names[a]);
+				}
+				fixed_new_names.push_back(new_name);
 
-			path_renames[ni].second = fixed_node_path;
+				NodePath fixed_node_path = NodePath(fixed_new_names, true);
+				path_renames[node] = fixed_node_path;
+			} else {
+				ERR_PRINT("Internal error. Can't find renamed path for node '" + node->get_path() + "'");
+			}
 		}
 
 		editor_data->get_undo_redo().add_do_method(ed, "live_debug_reparent_node", edited_scene->get_path_to(node), edited_scene->get_path_to(new_parent), new_name, p_position_in_parent + inc);
@@ -2042,7 +2021,7 @@ void SceneTreeDock::_delete_confirm(bool p_cut) {
 
 	} else {
 		remove_list.sort_custom<Node::Comparator>(); //sort nodes to keep positions
-		List<Pair<NodePath, NodePath>> path_renames;
+		Map<Node *, NodePath> path_renames;
 
 		//delete from animation
 		for (List<Node *>::Element *E = remove_list.front(); E; E = E->next()) {
diff --git a/editor/scene_tree_dock.h b/editor/scene_tree_dock.h
index fd9299fb2b..4952122cb7 100644
--- a/editor/scene_tree_dock.h
+++ b/editor/scene_tree_dock.h
@@ -217,7 +217,7 @@ class SceneTreeDock : public VBoxContainer {
 	void _selection_changed();
 	void _update_script_button();
 
-	void _fill_path_renames(Vector<StringName> base_path, Vector<StringName> new_base_path, Node *p_node, List<Pair<NodePath, NodePath>> *p_renames);
+	void _fill_path_renames(Vector<StringName> base_path, Vector<StringName> new_base_path, Node *p_node, Map<Node *, NodePath> *p_renames);
 
 	void _normalize_drop(Node *&to_node, int &to_pos, int p_type);
 
@@ -253,8 +253,8 @@ class SceneTreeDock : public VBoxContainer {
 	static SceneTreeDock *singleton;
 	static void _update_configuration_warning();
 
-	static bool _update_node_path(const NodePath &p_root_path, NodePath &r_node_path, List<Pair<NodePath, NodePath>> *p_renames);
-	static bool _check_node_path_recursive(const NodePath &p_root_path, Variant &r_variant, List<Pair<NodePath, NodePath>> *p_renames);
+	bool _update_node_path(Node *p_root_node, NodePath &r_node_path, Map<Node *, NodePath> *p_renames) const;
+	bool _check_node_path_recursive(Node *p_root_node, Variant &r_variant, Map<Node *, NodePath> *p_renames) const;
 
 protected:
 	void _notification(int p_what);
@@ -272,8 +272,8 @@ public:
 	void instantiate(const String &p_file);
 	void instantiate_scenes(const Vector<String> &p_files, Node *p_parent = nullptr);
 	void set_selected(Node *p_node, bool p_emit_selected = false);
-	void fill_path_renames(Node *p_node, Node *p_new_parent, List<Pair<NodePath, NodePath>> *p_renames);
-	void perform_node_renames(Node *p_base, List<Pair<NodePath, NodePath>> *p_renames, Map<Ref<Animation>, Set<int>> *r_rem_anims = nullptr);
+	void fill_path_renames(Node *p_node, Node *p_new_parent, Map<Node *, NodePath> *p_renames);
+	void perform_node_renames(Node *p_base, Map<Node *, NodePath> *p_renames, Map<Ref<Animation>, Set<int>> *r_rem_anims = nullptr);
 	SceneTreeEditor *get_tree_editor() { return scene_tree; }
 	EditorData *get_editor_data() { return editor_data; }