From ff40c3f3c8e71ce62afb3c14003a291a272fa7a8 Mon Sep 17 00:00:00 2001 From: PouleyKetchoupp Date: Fri, 9 Jul 2021 11:21:27 -0700 Subject: Optimize NodePath update when renaming or deleting nodes in the editor Now the process uses a Map to lookup node pointers instead of iterating over all modified node paths in a list and comparing them for each property to check. The process also avoids checking properties with empty node paths and does an early exit on deleted nodes to avoid checking the node and its descendants. Also made a minor change in NodePath::rel_path_to() to avoid resizing a Vector many times for long paths (with copy-on-write each time). Now it's down to 2 resize calls in any case. --- core/string/node_path.cpp | 17 ++-- editor/scene_tree_dock.cpp | 207 ++++++++++++++++++++------------------------- editor/scene_tree_dock.h | 10 +-- 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 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 e91a88ba7a..57157a5555 100644 --- a/editor/scene_tree_dock.cpp +++ b/editor/scene_tree_dock.cpp @@ -1367,30 +1367,25 @@ void SceneTreeDock::_set_owners(Node *p_owner, const Array &p_nodes) { } } -void SceneTreeDock::_fill_path_renames(Vector base_path, Vector new_base_path, Node *p_node, List> *p_renames) { +void SceneTreeDock::_fill_path_renames(Vector base_path, Vector new_base_path, Node *p_node, Map *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 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> *p_renames) { +void SceneTreeDock::fill_path_renames(Node *p_node, Node *p_new_parent, Map *p_renames) { Vector base_path; Node *n = p_node->get_parent(); while (n) { @@ -1413,50 +1408,41 @@ void SceneTreeDock::fill_path_renames(Node *p_node, Node *p_new_parent, List> *p_renames) { - NodePath root_path_new = p_root_path; - for (List>::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>::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 *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::Element *found_node_path = p_renames->find(target_node); + if (found_node_path) { + Map::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::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> *p_renames) { +bool SceneTreeDock::_check_node_path_recursive(Node *p_root_node, Variant &r_variant, Map *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; } @@ -1467,7 +1453,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; @@ -1486,7 +1472,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; @@ -1507,7 +1493,7 @@ bool SceneTreeDock::_check_node_path_recursive(const NodePath &p_root_path, Vari return false; } -void SceneTreeDock::perform_node_renames(Node *p_base, List> *p_renames, Map, Set> *r_rem_anims) { +void SceneTreeDock::perform_node_renames(Node *p_base, Map *p_renames, Map, Set> *r_rem_anims) { Map, Set> rem_anims; if (!r_rem_anims) { r_rem_anims = &rem_anims; @@ -1521,10 +1507,15 @@ void SceneTreeDock::perform_node_renames(Node *p_base, List::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 properties; p_base->get_property_list(&properties); - NodePath base_root_path = p_base->get_path(); for (List::Element *E = properties.front(); E; E = E->next()) { if (!(E->get().usage & (PROPERTY_USAGE_STORAGE | PROPERTY_USAGE_EDITOR))) { @@ -1533,7 +1524,7 @@ void SceneTreeDock::perform_node_renames(Node *p_base, Listget().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); @@ -1549,19 +1540,9 @@ void SceneTreeDock::perform_node_renames(Node *p_base, Listget_node(ap->get_root()); if (root) { - NodePath root_path = root->get_path(); - NodePath new_root_path = root_path; - - for (List>::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::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::Element *E = anims.front(); E; E = E->next()) { Ref anim = ap->get_animation(E->get()); if (!r_rem_anims->has(anim)) { @@ -1585,47 +1566,44 @@ void SceneTreeDock::perform_node_renames(Node *p_base, Listget_path(); - if (!ran.has(i)) { continue; //channel was removed } - for (List>::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::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::Element *found_path = p_renames->find(n); + if (found_path) { + if (found_path->get() == NodePath()) { + //will be erased + + int idx = 0; + Set::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); } } } @@ -1640,7 +1618,7 @@ void SceneTreeDock::perform_node_renames(Node *p_base, List> path_renames; + Map path_renames; Vector base_path; Node *n = p_node->get_parent(); @@ -1655,10 +1633,8 @@ void SceneTreeDock::_node_prerenamed(Node *p_node, const String &p_new_name) { new_base_path.push_back(p_new_name); - Pair 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); @@ -1763,7 +1739,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> path_renames; + Map path_renames; Vector former_names; int inc = 0; @@ -1800,21 +1776,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 unfixed_new_names = old_new_name.get_names(); - Vector fixed_new_names; + Map::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 unfixed_new_names = old_new_name.get_names(); + Vector 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); @@ -2025,7 +2004,7 @@ void SceneTreeDock::_delete_confirm(bool p_cut) { } else { remove_list.sort_custom(); //sort nodes to keep positions - List> path_renames; + Map path_renames; //delete from animation for (List::Element *E = remove_list.front(); E; E = E->next()) { diff --git a/editor/scene_tree_dock.h b/editor/scene_tree_dock.h index 08d992d465..7c89865b6f 100644 --- a/editor/scene_tree_dock.h +++ b/editor/scene_tree_dock.h @@ -211,7 +211,7 @@ class SceneTreeDock : public VBoxContainer { void _selection_changed(); void _update_script_button(); - void _fill_path_renames(Vector base_path, Vector new_base_path, Node *p_node, List> *p_renames); + void _fill_path_renames(Vector base_path, Vector new_base_path, Node *p_node, Map *p_renames); void _normalize_drop(Node *&to_node, int &to_pos, int p_type); @@ -247,8 +247,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> *p_renames); - static bool _check_node_path_recursive(const NodePath &p_root_path, Variant &r_variant, List> *p_renames); + bool _update_node_path(Node *p_root_node, NodePath &r_node_path, Map *p_renames) const; + bool _check_node_path_recursive(Node *p_root_node, Variant &r_variant, Map *p_renames) const; protected: void _notification(int p_what); @@ -266,8 +266,8 @@ public: void instantiate(const String &p_file); void instantiate_scenes(const Vector &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> *p_renames); - void perform_node_renames(Node *p_base, List> *p_renames, Map, Set> *r_rem_anims = nullptr); + void fill_path_renames(Node *p_node, Node *p_new_parent, Map *p_renames); + void perform_node_renames(Node *p_base, Map *p_renames, Map, Set> *r_rem_anims = nullptr); SceneTreeEditor *get_tree_editor() { return scene_tree; } EditorData *get_editor_data() { return editor_data; } -- cgit v1.2.3