Cleanup: Nodes: Use const arguments, avoid recursive iteration

Use the node topology cache and avoid modifying the node tree
in a non-threadsafe way to improve the predictability of using
the helper function. Replaces the implementation from
e0d40471364aafca967b6ebd52.

6 files changed, 28 insertions, 40 deletions

diff --git a/source/blender/blenkernel/BKE_node.h b/source/blender/blenkernel/BKE_node.h
index 21d421cfb6a..4d883f9e31e 100644
--- a/source/blender/blenkernel/BKE_node.h
+++ b/source/blender/blenkernel/BKE_node.h
@@ -1005,7 +1005,7 @@ void node_type_storage(struct bNodeType *ntype,
 /** \name Node Generic Functions
  * \{ */
 
-bool BKE_node_is_connected_to_output(struct bNodeTree *ntree, struct bNode *node);
+bool BKE_node_is_connected_to_output(const struct bNodeTree *ntree, const struct bNode *node);
 
 /* ************** COMMON NODES *************** */
 
diff --git a/source/blender/draw/engines/workbench/workbench_materials.c b/source/blender/draw/engines/workbench/workbench_materials.c
index 4744c0db6ce..7c5e8313532 100644
--- a/source/blender/draw/engines/workbench/workbench_materials.c
+++ b/source/blender/draw/engines/workbench/workbench_materials.c
@@ -88,14 +88,14 @@ BLI_INLINE Material *workbench_object_material_get(Object *ob, int mat_nr)
 BLI_INLINE void workbench_material_get_image(
     Object *ob, int mat_nr, Image **r_image, ImageUser **r_iuser, eGPUSamplerState *r_sampler)
 {
-  bNode *node;
+  const bNode *node;
   *r_sampler = 0;
 
   ED_object_get_active_image(ob, mat_nr, r_image, r_iuser, &node, NULL);
   if (node && *r_image) {
     switch (node->type) {
       case SH_NODE_TEX_IMAGE: {
-        NodeTexImage *storage = node->storage;
+        const NodeTexImage *storage = node->storage;
         const bool use_filter = (storage->interpolation != SHD_INTERP_CLOSEST);
         const bool use_repeat = (storage->extension == SHD_IMAGE_EXTENSION_REPEAT);
         const bool use_clip = (storage->extension == SHD_IMAGE_EXTENSION_CLIP);
@@ -105,7 +105,7 @@ BLI_INLINE void workbench_material_get_image(
         break;
       }
       case SH_NODE_TEX_ENVIRONMENT: {
-        NodeTexEnvironment *storage = node->storage;
+        const NodeTexEnvironment *storage = node->storage;
         const bool use_filter = (storage->interpolation != SHD_INTERP_CLOSEST);
         SET_FLAG_FROM_TEST(*r_sampler, use_filter, GPU_SAMPLER_FILTER);
         break;
diff --git a/source/blender/editors/include/ED_uvedit.h b/source/blender/editors/include/ED_uvedit.h
index b97cd6a9099..5fea8711a84 100644
--- a/source/blender/editors/include/ED_uvedit.h
+++ b/source/blender/editors/include/ED_uvedit.h
@@ -73,8 +73,8 @@ bool ED_object_get_active_image(struct Object *ob,
                                 int mat_nr,
                                 struct Image **r_ima,
                                 struct ImageUser **r_iuser,
-                                struct bNode **r_node,
-                                struct bNodeTree **r_ntree);
+                                const struct bNode **r_node,
+                                const struct bNodeTree **r_ntree);
 void ED_object_assign_active_image(struct Main *bmain,
                                    struct Object *ob,
                                    int mat_nr,
diff --git a/source/blender/editors/object/object_bake_api.c b/source/blender/editors/object/object_bake_api.c
index 260d65fc5dc..d647578dc50 100644
--- a/source/blender/editors/object/object_bake_api.c
+++ b/source/blender/editors/object/object_bake_api.c
@@ -467,8 +467,8 @@ static bool bake_object_check(const Scene *scene,
     }
 
     for (int i = 0; i < ob->totcol; i++) {
-      bNodeTree *ntree = NULL;
-      bNode *node = NULL;
+      const bNodeTree *ntree = NULL;
+      const bNode *node = NULL;
       const int mat_nr = i + 1;
       Image *image;
       ED_object_get_active_image(ob, mat_nr, &image, NULL, &node, &ntree);
diff --git a/source/blender/editors/uvedit/uvedit_ops.c b/source/blender/editors/uvedit/uvedit_ops.c
index b65f4889347..0e77a8ba4ad 100644
--- a/source/blender/editors/uvedit/uvedit_ops.c
+++ b/source/blender/editors/uvedit/uvedit_ops.c
@@ -111,8 +111,8 @@ bool ED_object_get_active_image(Object *ob,
                                 int mat_nr,
                                 Image **r_ima,
                                 ImageUser **r_iuser,
-                                bNode **r_node,
-                                bNodeTree **r_ntree)
+                                const bNode **r_node,
+                                const bNodeTree **r_ntree)
 {
   Material *ma = DEG_is_evaluated_object(ob) ? BKE_object_material_get_eval(ob, mat_nr) :
                                                BKE_object_material_get(ob, mat_nr);
diff --git a/source/blender/nodes/intern/node_common.cc b/source/blender/nodes/intern/node_common.cc
index 69631fa5213..975bf0c01ca 100644
--- a/source/blender/nodes/intern/node_common.cc
+++ b/source/blender/nodes/intern/node_common.cc
@@ -22,6 +22,7 @@
 #include "BLT_translation.h"
 
 #include "BKE_node.h"
+#include "BKE_node_runtime.hh"
 #include "BKE_node_tree_update.h"
 
 #include "RNA_types.h"
@@ -378,42 +379,29 @@ void ntree_update_reroute_nodes(bNodeTree *ntree)
   }
 }
 
-static bool node_is_connected_to_output_recursive(bNodeTree *ntree, bNode *node)
+bool BKE_node_is_connected_to_output(const bNodeTree *ntree, const bNode *node)
 {
-  bNodeLink *link;
-
-  /* avoid redundant checks, and infinite loops in case of cyclic node links */
-  if (node->done) {
-    return false;
-  }
-  node->done = 1;
-
-  /* main test, done before child loop so it catches output nodes themselves as well */
-  if (node->typeinfo->nclass == NODE_CLASS_OUTPUT && node->flag & NODE_DO_OUTPUT) {
-    return true;
+  ntree->ensure_topology_cache();
+  Stack<const bNode *> nodes_to_check;
+  for (const bNodeSocket *socket : node->output_sockets()) {
+    for (const bNodeLink *link : socket->directly_linked_links()) {
+      nodes_to_check.push(link->tonode);
+    }
   }
-
-  /* test all connected nodes, first positive find is sufficient to return true */
-  for (link = (bNodeLink *)ntree->links.first; link; link = link->next) {
-    if (link->fromnode == node) {
-      if (node_is_connected_to_output_recursive(ntree, link->tonode)) {
-        return true;
+  while (!nodes_to_check.is_empty()) {
+    const bNode *next_node = nodes_to_check.pop();
+    for (const bNodeSocket *socket : next_node->output_sockets()) {
+      for (const bNodeLink *link : socket->directly_linked_links()) {
+        if (link->tonode->typeinfo->nclass == NODE_CLASS_OUTPUT &&
+            link->tonode->flag & NODE_DO_OUTPUT) {
+          return true;
+        }
+        nodes_to_check.push(link->tonode);
       }
     }
   }
-  return false;
-}
-
-bool BKE_node_is_connected_to_output(bNodeTree *ntree, bNode *node)
-{
-  bNode *tnode;
-
-  /* clear flags */
-  for (tnode = (bNode *)ntree->nodes.first; tnode; tnode = tnode->next) {
-    tnode->done = 0;
-  }
 
-  return node_is_connected_to_output_recursive(ntree, node);
+  return false;
 }
 
 /** \} */