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
e0d4047136.

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 *************** */
 

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;

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,

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

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

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,44 +379,31 @@ 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;
+  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);
+    }
   }
-  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;
-  }
-
-  /* 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);
-}
-
 /** \} */
 
 /* -------------------------------------------------------------------- */