[Bf-blender-cvs] [c06a86f99f5] master: Fix T92328: crash during field inferencing when there is a link cycle
Jacques Lucke
noreply at git.blender.org
Wed Oct 27 12:31:40 CEST 2021
Commit: c06a86f99f5bd59e2f1c37b18f5e668da245a206
Author: Jacques Lucke
Date: Wed Oct 27 12:29:46 2021 +0200
Branches: master
https://developer.blender.org/rBc06a86f99f5bd59e2f1c37b18f5e668da245a206
Fix T92328: crash during field inferencing when there is a link cycle
The toposort did not handle link cycles which it should.
===================================================================
M source/blender/blenkernel/intern/node.cc
M source/blender/nodes/NOD_node_tree_ref.hh
M source/blender/nodes/intern/node_tree_ref.cc
===================================================================
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<SocketFieldState> field_state_by_socket_id)
{
- const Vector<const NodeRef *> 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<SocketFieldState> field_state_by_socket_id)
{
- Vector<const NodeRef *> 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<const NodeRef *> toposort(ToposortDirection direction) const;
+ struct ToposortResult {
+ Vector<const NodeRef *> 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<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
More information about the Bf-blender-cvs
mailing list