diff options
Diffstat (limited to 'source/blender/nodes/intern/node_tree_ref.cc')
| -rw-r--r-- | source/blender/nodes/intern/node_tree_ref.cc | 135 |
1 files changed, 86 insertions, 49 deletions
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<const NodeRef *> 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<ToposortNodeState> node_states, + NodeTreeRef::ToposortResult &result) { struct Item { const NodeRef *node; @@ -516,64 +520,97 @@ Vector<const NodeRef *> NodeTreeRef::toposort(const ToposortDirection direction) int link_index = 0; }; - Vector<const NodeRef *> toposort; - toposort.reserve(nodes_by_id_.size()); - Array<bool> node_is_done_by_id(nodes_by_id_.size(), false); - Stack<Item> nodes_to_check; + /* Do a depth-first search to sort nodes topologically. */ + Stack<Item, 64> 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<const SocketRef *> 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<const SocketRef *> 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<ToposortNodeState> 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<const SocketRef *> 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<const SocketRef *> 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 |