blender
/
blender
136
405
Fork 586
Code Issues 6.2k Pull Requests 758 Projects 19 Wiki Activity

Fix T92328: crash during field inferencing when there is a link cycle 

The toposort did not handle link cycles which it should.
This commit is contained in:
Jacques Lucke 2021-10-27 12:29:46 +02:00
parent d161b5d204
commit c06a86f99f
Notes: blender-bot 2023-12-22 20:14:11 +01:00 
Referenced by issue #92328, Blender hangs when making unintentional loops in geometry nodes
3 changed files with 101 additions and 54 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

8
source/blender/blenkernel/intern/node.cc
View File

@ -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;
}

12
source/blender/nodes/NOD_node_tree_ref.hh
View File

@ -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;

135
source/blender/nodes/intern/node_tree_ref.cc
View File

@ -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);
for (const NodeRef *start_node : nodes_by_id_) {
if (node_is_done_by_id[start_node->id()]) {
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;
}
/* 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);
toposort_from_start_node(direction, *node, node_states, result);
}
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;
}
/* 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