From c06a86f99f5bd59e2f1c37b18f5e668da245a206 Mon Sep 17 00:00:00 2001 From: Jacques Lucke Date: Wed, 27 Oct 2021 12:29:46 +0200 Subject: Fix T92328: crash during field inferencing when there is a link cycle The toposort did not handle link cycles which it should. --- source/blender/blenkernel/intern/node.cc | 8 +- source/blender/nodes/NOD_node_tree_ref.hh | 12 ++- source/blender/nodes/intern/node_tree_ref.cc | 135 +++++++++++++++++---------- 3 files changed, 101 insertions(+), 54 deletions(-) (limited to 'source/blender') diff --git a/source/blender/blenkernel/intern/node.cc b/source/blender/blenkernel/intern/node.cc index d6c4e1f21e4..95192003f9f 100644 --- a/source/blender/blenkernel/intern/node.cc +++ b/source/blender/blenkernel/intern/node.cc @@ -4717,10 +4717,10 @@ static OutputFieldDependency find_group_output_dependencies( static void propagate_data_requirements_from_right_to_left( const NodeTreeRef &tree, const MutableSpan field_state_by_socket_id) { - const Vector sorted_nodes = tree.toposort( + const NodeTreeRef::ToposortResult toposort_result = tree.toposort( NodeTreeRef::ToposortDirection::RightToLeft); - for (const NodeRef *node : sorted_nodes) { + for (const NodeRef *node : toposort_result.sorted_nodes) { const FieldInferencingInterface inferencing_interface = get_node_field_inferencing_interface( *node); @@ -4829,10 +4829,10 @@ static void determine_group_input_states( static void propagate_field_status_from_left_to_right( const NodeTreeRef &tree, const MutableSpan field_state_by_socket_id) { - Vector sorted_nodes = tree.toposort( + const NodeTreeRef::ToposortResult toposort_result = tree.toposort( NodeTreeRef::ToposortDirection::LeftToRight); - for (const NodeRef *node : sorted_nodes) { + for (const NodeRef *node : toposort_result.sorted_nodes) { if (node->is_group_input_node()) { continue; } diff --git a/source/blender/nodes/NOD_node_tree_ref.hh b/source/blender/nodes/NOD_node_tree_ref.hh index 9f9dcc69376..e04dd7f41bd 100644 --- a/source/blender/nodes/NOD_node_tree_ref.hh +++ b/source/blender/nodes/NOD_node_tree_ref.hh @@ -287,7 +287,17 @@ class NodeTreeRef : NonCopyable, NonMovable { RightToLeft, }; - Vector toposort(ToposortDirection direction) const; + struct ToposortResult { + Vector sorted_nodes; + /** + * There can't be a correct topologycal sort of the nodes when there is a cycle. The nodes will + * still be sorted to some degree. The caller has to decide whether it can handle non-perfect + * sorts or not. + */ + bool has_cycle = false; + }; + + ToposortResult toposort(ToposortDirection direction) const; bNodeTree *btree() const; StringRefNull name() const; diff --git a/source/blender/nodes/intern/node_tree_ref.cc b/source/blender/nodes/intern/node_tree_ref.cc index 2ca797009da..5481465aef6 100644 --- a/source/blender/nodes/intern/node_tree_ref.cc +++ b/source/blender/nodes/intern/node_tree_ref.cc @@ -502,11 +502,15 @@ bool NodeRef::any_socket_is_directly_linked(eNodeSocketInOut in_out) const return this->any_output_is_directly_linked(); } -/** - * Sort nodes topologically from left to right or right to left. - * In the future the result if this could be cached on #NodeTreeRef. - */ -Vector NodeTreeRef::toposort(const ToposortDirection direction) const +struct ToposortNodeState { + bool is_done = false; + bool is_in_stack = false; +}; + +static void toposort_from_start_node(const NodeTreeRef::ToposortDirection direction, + const NodeRef &start_node, + MutableSpan node_states, + NodeTreeRef::ToposortResult &result) { struct Item { const NodeRef *node; @@ -516,64 +520,97 @@ Vector NodeTreeRef::toposort(const ToposortDirection direction) int link_index = 0; }; - Vector toposort; - toposort.reserve(nodes_by_id_.size()); - Array node_is_done_by_id(nodes_by_id_.size(), false); - Stack nodes_to_check; + /* Do a depth-first search to sort nodes topologically. */ + Stack nodes_to_check; + nodes_to_check.push({&start_node}); + while (!nodes_to_check.is_empty()) { + Item &item = nodes_to_check.peek(); + const NodeRef &node = *item.node; + const Span sockets = node.sockets( + direction == NodeTreeRef::ToposortDirection::LeftToRight ? SOCK_IN : SOCK_OUT); + + while (true) { + if (item.socket_index == sockets.size()) { + /* All sockets have already been visited. */ + break; + } + const SocketRef &socket = *sockets[item.socket_index]; + const Span linked_sockets = socket.directly_linked_sockets(); + if (item.link_index == linked_sockets.size()) { + /* All links connected to this socket have already been visited. */ + item.socket_index++; + item.link_index = 0; + continue; + } + const SocketRef &linked_socket = *linked_sockets[item.link_index]; + const NodeRef &linked_node = linked_socket.node(); + ToposortNodeState &linked_node_state = node_states[linked_node.id()]; + if (linked_node_state.is_done) { + /* The linked node has already been visited. */ + item.link_index++; + continue; + } + if (linked_node_state.is_in_stack) { + result.has_cycle = true; + } + else { + nodes_to_check.push({&linked_node}); + linked_node_state.is_in_stack = true; + } + break; + } - for (const NodeRef *start_node : nodes_by_id_) { - if (node_is_done_by_id[start_node->id()]) { + /* If no other element has been pushed, the current node can be pushed to the sorted list. */ + if (&item == &nodes_to_check.peek()) { + ToposortNodeState &node_state = node_states[node.id()]; + node_state.is_done = true; + node_state.is_in_stack = false; + result.sorted_nodes.append(&node); + nodes_to_check.pop(); + } + } +} + +/** + * Sort nodes topologically from left to right or right to left. + * In the future the result if this could be cached on #NodeTreeRef. + */ +NodeTreeRef::ToposortResult NodeTreeRef::toposort(const ToposortDirection direction) const +{ + ToposortResult result; + result.sorted_nodes.reserve(nodes_by_id_.size()); + + Array node_states(nodes_by_id_.size()); + + for (const NodeRef *node : nodes_by_id_) { + if (node_states[node->id()].is_done) { /* Ignore nodes that are done already. */ continue; } - if (start_node->any_socket_is_directly_linked( + if (node->any_socket_is_directly_linked( direction == ToposortDirection::LeftToRight ? SOCK_OUT : SOCK_IN)) { /* Ignore non-start nodes. */ continue; } - /* Do a depth-first search to sort nodes topologically. */ - nodes_to_check.push({start_node}); - while (!nodes_to_check.is_empty()) { - Item &item = nodes_to_check.peek(); - const NodeRef &node = *item.node; - const Span sockets = node.sockets( - direction == ToposortDirection::LeftToRight ? SOCK_IN : SOCK_OUT); - - while (true) { - if (item.socket_index == sockets.size()) { - /* All sockets have already been visited. */ - break; - } - const SocketRef &socket = *sockets[item.socket_index]; - const Span linked_sockets = socket.directly_linked_sockets(); - if (item.link_index == linked_sockets.size()) { - /* All links connected to this socket have already been visited. */ - item.socket_index++; - item.link_index = 0; - continue; - } - const SocketRef &linked_socket = *linked_sockets[item.link_index]; - const NodeRef &linked_node = linked_socket.node(); - if (node_is_done_by_id[linked_node.id()]) { - /* The linked node has already been visited. */ - item.link_index++; - continue; - } - nodes_to_check.push({&linked_node}); - break; - } + toposort_from_start_node(direction, *node, node_states, result); + } - /* If no other element has been pushed, the current node can be pushed to the sorted list. */ - if (&item == &nodes_to_check.peek()) { - node_is_done_by_id[node.id()] = true; - toposort.append(&node); - nodes_to_check.pop(); + /* Check if the loop above forgot some nodes because there is a cycle. */ + if (result.sorted_nodes.size() < nodes_by_id_.size()) { + result.has_cycle = true; + for (const NodeRef *node : nodes_by_id_) { + if (node_states[node->id()].is_done) { + /* Ignore nodes that are done already. */ + continue; } + /* Start toposort at this node which is somewhere in the middle of a loop. */ + toposort_from_start_node(direction, *node, node_states, result); } } - return toposort; + BLI_assert(result.sorted_nodes.size() == nodes_by_id_.size()); + return result; } const NodeRef *NodeTreeRef::find_node(const bNode &bnode) const -- cgit v1.2.3