Make SVGResourcesCycleSolver check for cycles beyond one level (and more)

Source/core/rendering/svg/SVGResourcesCycleSolver.cpp

Index: Source/core/rendering/svg/SVGResourcesCycleSolver.cpp
diff --git a/Source/core/rendering/svg/SVGResourcesCycleSolver.cpp b/Source/core/rendering/svg/SVGResourcesCycleSolver.cpp
index 8c48d7bd3d4ab6a29c95655d68df5200e991c3ed..5c9b3d2f20e40cb8a57b9675007727264675ad12 100644
--- a/Source/core/rendering/svg/SVGResourcesCycleSolver.cpp
+++ b/Source/core/rendering/svg/SVGResourcesCycleSolver.cpp
@@ -47,101 +47,88 @@ SVGResourcesCycleSolver::~SVGResourcesCycleSolver()
 {
 }
 
-bool SVGResourcesCycleSolver::resourceContainsCycles(RenderObject* renderer) const
-{
-    ASSERT(renderer);
-
-    // First (first loop iteration) operate on the resources of the given
-    // renderer.
-    // <marker id="a"> <path marker-start="url(#b)"/> ...
-    // <marker id="b" marker-start="url(#a)"/>
-    // Then operate on the child resources of the given renderer.
-    // <marker id="a"> <path marker-start="url(#b)"/> ...
-    // <marker id="b"> <path marker-start="url(#a)"/> ...
-    for (RenderObject* child = renderer; child; child = child->nextInPreOrder(renderer)) {
-        SVGResources* childResources = SVGResourcesCache::cachedResourcesForRenderObject(child);
-        if (!childResources)
-            continue;
+class SVGResourcesCycleSolver::ActiveFrame {

[krit, 2014/05/28 10:22:30]

It seems like it could be a struct. The definition could even go into the
header.

[fs, 2014/05/28 11:23:48]

I can make it a struct I suppose (see reply to comment in the header-file). I'd
prefer to not litter the header-file with it, even if it's "simple" though. It
could even be made local to the CU - if the ResourceSet typedef had suitable
access - maybe that's preferable then.

+public:
+    ActiveFrame(ResourceSet& activeSet, RenderSVGResourceContainer* resource)
+        : m_activeSet(activeSet)
+        , m_resource(resource)
+    {
+        m_activeSet.add(m_resource);
+    }
+    ~ActiveFrame()
+    {
+        m_activeSet.remove(m_resource);
+    }
 
-        // A child of the given 'resource' contains resources.
-        HashSet<RenderSVGResourceContainer*> childSet;
-        childResources->buildSetOfResources(childSet);
+private:
+    ResourceSet& m_activeSet;
+    RenderSVGResourceContainer* m_resource;

[krit, 2014/05/28 10:22:30]

With activeSet, you mean visited resources? And m_resource is current resource?
We should use some clear terms here.

[fs, 2014/05/28 11:23:48]

Heh, this was called m_visitedResources in earlier drafts - it's strictly not a
"visited set" though I think - more like a "visited path" (and before
m_visitedResources it was called m_resourcePath...). Any of those two that you
find better?

+};
 
-        // Walk all child resources and check whether they reference any resource contained in the resources set.
-        HashSet<RenderSVGResourceContainer*>::iterator end = childSet.end();
-        for (HashSet<RenderSVGResourceContainer*>::iterator it = childSet.begin(); it != end; ++it) {
-            if (m_allResources.contains(*it))
-                return true;
+bool SVGResourcesCycleSolver::resourceContainsCycles(RenderSVGResourceContainer* resource)
+{
+    // If we've traversed this sub-graph before and no cycles were observed, then

[krit, 2014/05/28 10:22:30]

Is that algorithm using any of the known traversal patterns? I would be great if
the code just follows one of the known cycle detection algorithms from graph
theory.

[fs, 2014/05/28 11:23:48]

It's essentially a (recursive) depth-first traversal/search looking for a
back-edge. Don't know if that has better name. Various SCC-partitioning algos
are similar, but we don't really care for SCCs here.

+    // reuse that result.
+    if (m_dagCache.contains(resource))
+        return false;
+
+    ActiveFrame frame(m_activeResources, resource);
+
+    RenderObject* child = resource;
+    while (child) {
+        // Skip subtrees which are themselves resources. (They will be
+        // processed - if needed - when they are actually referenced.)
+        if (child != resource && child->isSVGResourceContainer()) {
+            child = child->nextInPreOrderAfterChildren(resource);
+            continue;
+        }
+        if (SVGResources* childResources = SVGResourcesCache::cachedResourcesForRenderObject(child)) {
+            // Fetch all the resources referenced by |child|.
+            ResourceSet childSet;
+            childResources->buildSetOfResources(childSet);
+
+            // Iterate resources referenced by |child|.
+            ResourceSet::iterator end = childSet.end();
+            for (ResourceSet::iterator it = childSet.begin(); it != end; ++it) {
+                if (m_activeResources.contains(*it) || resourceContainsCycles(*it))
+                    return true;
+            }
         }
+        child = child->nextInPreOrder(resource);
     }
+
+    // No cycles found in (or from) this resource. Add it to the "DAG cache".
+    m_dagCache.add(resource);
     return false;
 }
 
 void SVGResourcesCycleSolver::resolveCycles()
 {
-    ASSERT(m_allResources.isEmpty());
-
-#if DEBUG_CYCLE_DETECTION > 0
-    fprintf(stderr, "\nBefore cycle detection:\n");
-    m_resources->dump(m_renderer);
-#endif
+    ASSERT(m_activeResources.isEmpty());
+
+    // Add the first resource container from the ancestor-chain (including the
+    // renderer itself) to the resource path. (This is an optimization that
+    // will reduce the number of steps by one for cycles back onto the
+    // "initiating" resource.)
+    RenderObject* parent = m_renderer;
+    do {

[krit, 2014/05/28 10:22:30]

why not while() {}? parent is not checked here.

[fs, 2014/05/28 11:23:48]

m_renderer is assumed non-null (asserted in constructor), so we know that the
initial parent (== m_renderer) is not null.

+        if (parent->isSVGResourceContainer()) {
+            m_activeResources.add(toRenderSVGResourceContainer(parent));
+            break;
+        }
+        parent = parent->parent();
+    } while (parent);
 
-    // Stash all resources into a HashSet for the ease of traversing.
-    HashSet<RenderSVGResourceContainer*> localResources;
+    ResourceSet localResources;
     m_resources->buildSetOfResources(localResources);
-    ASSERT(!localResources.isEmpty());
-
-    // Add all parent resource containers to the HashSet.
-    HashSet<RenderSVGResourceContainer*> parentResources;
-    RenderObject* parent = m_renderer->parent();
-    while (parent) {
-        if (parent->isSVGResourceContainer())
-            parentResources.add(toRenderSVGResourceContainer(parent));
-        parent = parent->parent();
-    }
 
-#if DEBUG_CYCLE_DETECTION > 0
-    fprintf(stderr, "\nDetecting wheter any resources references any of following objects:\n");
-    {
-        fprintf(stderr, "Local resources:\n");
-        HashSet<RenderSVGResourceContainer*>::iterator end = localResources.end();
-        for (HashSet<RenderSVGResourceContainer*>::iterator it = localResources.begin(); it != end; ++it)
-            fprintf(stderr, "|> %s: object=%p (node=%p)\n", (*it)->renderName(), *it, (*it)->node());
-
-        fprintf(stderr, "Parent resources:\n");
-        end = parentResources.end();
-        for (HashSet<RenderSVGResourceContainer*>::iterator it = parentResources.begin(); it != end; ++it)
-            fprintf(stderr, "|> %s: object=%p (node=%p)\n", (*it)->renderName(), *it, (*it)->node());
+    ResourceSet::iterator end = localResources.end();
+    for (ResourceSet::iterator it = localResources.begin(); it != end; ++it) {
+        if (m_activeResources.contains(*it) || resourceContainsCycles(*it))
+            breakCycle(*it);
     }
-#endif
-
-    // Build combined set of local and parent resources.
-    m_allResources = localResources;
-    HashSet<RenderSVGResourceContainer*>::iterator end = parentResources.end();
-    for (HashSet<RenderSVGResourceContainer*>::iterator it = parentResources.begin(); it != end; ++it)
-        m_allResources.add(*it);
-
-    // If we're a resource, add ourselves to the HashSet.
-    if (m_renderer->isSVGResourceContainer())
-        m_allResources.add(toRenderSVGResourceContainer(m_renderer));
-
-    ASSERT(!m_allResources.isEmpty());
-
-    // The job of this function is to determine wheter any of the 'resources' associated with the given 'renderer'
-    // references us (or wheter any of its kids references us) -> that's a cycle, we need to find and break it.
-    end = localResources.end();
-    for (HashSet<RenderSVGResourceContainer*>::iterator it = localResources.begin(); it != end; ++it) {
-        RenderSVGResourceContainer* resource = *it;
-        if (parentResources.contains(resource) || resourceContainsCycles(resource))
-            breakCycle(resource);
-    }
-
-#if DEBUG_CYCLE_DETECTION > 0
-    fprintf(stderr, "\nAfter cycle detection:\n");
-    m_resources->dump(m_renderer);
-#endif
 
-    m_allResources.clear();
+    m_activeResources.clear();
 }
 
 void SVGResourcesCycleSolver::breakCycle(RenderSVGResourceContainer* resourceLeadingToCycle)