[gegl] graph: avoid visiting nodes multiple times in gegl_node_has_source()

[N/A <ell src gnome org>]

commit ed8af9caeed516d4f39d3ff2c7337d6959425293
Author: Ell <ell_se yahoo com>
Date:   Thu Nov 9 14:53:28 2017 -0500

    graph: avoid visiting nodes multiple times in gegl_node_has_source()
    
    Port gegl_node_has_source() to GeglVisitor-based graph traversal.
    
    The current implementation doesn't keep track of which nodes have
    already been visited, which can lead to an exponentially-increasing
    number of visitations, w.r.t. number of nodes in the graph.
    
    In particular, in a graph of the form
        ___   ___   ___
       /   v /   v /   v
      A     B     C     D
       \___^ \___^ \___^
    
    calling 'gegl_node_has_source (A, E)', would arrive from A to B
    twice, once along each edge; each of these times, C will be arrived
    from B twice, once along each edge, for a total of 4 times;
    likewise, D will be arrived a total of 8 times, etc.  Note that
    gegl_node_has_source() is used for verifying that a node *doesn't*
    have another node as a source while building the graph, so
    traversal normally never breaks early, making this particularly
    problematic.
    
    A situation like this arises in GIMP, when a layer stack contains
    multiple pass-through groups.

 gegl/graph/gegl-node.c |   31 ++++++++++++++-----------------
 1 files changed, 14 insertions(+), 17 deletions(-)
---
diff --git a/gegl/graph/gegl-node.c b/gegl/graph/gegl-node.c
index 58df4a9..ecc240f 100644
--- a/gegl/graph/gegl-node.c
+++ b/gegl/graph/gegl-node.c
@@ -36,6 +36,7 @@
 #include "gegl-config.h"
 
 #include "graph/gegl-visitor.h"
+#include "graph/gegl-callback-visitor.h"
 
 #include "operation/gegl-operation.h"
 #include "operation/gegl-operations.h"
@@ -635,30 +636,26 @@ gegl_node_source_invalidated (GeglNode            *source,
   gegl_node_invalidated (destination, &dirty_rect, FALSE);
 }
 
-static GSList *
-gegl_node_get_depends_on (GeglNode *self);
+static gboolean
+gegl_node_has_source_callback (GeglNode *node,
+                               gpointer  potential_source)
+{
+  return node == potential_source;
+}
 
 static gboolean
 gegl_node_has_source (GeglNode *self,
                       GeglNode *potential_source)
 {
-  GSList *producers, *p;
-  gboolean found = FALSE;
+  GeglVisitor *visitor;
+  gboolean     found;
 
-  if (self == potential_source)
-    return TRUE;
+  visitor = gegl_callback_visitor_new (gegl_node_has_source_callback,
+                                       potential_source);
 
-  producers = gegl_node_get_depends_on (self);
-  for (p = producers; p; p = p->next)
-    {
-      if (p->data == potential_source)
-        found = TRUE;
-      else
-        found = gegl_node_has_source (p->data, potential_source);
-      if (found)
-        break;
-    }
-  g_slist_free (producers);
+  found = gegl_visitor_traverse (visitor, GEGL_VISITABLE (self));
+
+  g_object_unref (visitor);
 
   return found;
 }