Make SVGResourcesCycleSolver check for cycles beyond one level (and more)
The SVGResourceCycleSolver checks for cycles from within the resources
a RenderObject references to the resources it references, or any resources
in the ancestor-chain of the starting RenderObject (including itself if
it is a resource container).
This suffers from a few issues. One is that a resource that is referenced
both by the starting RenderObject and another resource referenced from the
starting RenderObject will be flagged as a cycle because all the resources
are added to the resources set.
Another issue is that longer cycles may not be detected because only the
resources referenced by the starting RenderObject is checked, and
depending on how the render tree is built, some cycles could be missed.
Additionally, a resource defined within another resource can cause a
"false cycle" to be flagged when the inner resource references a resource
in the resource set - eventhough the inner resource itself is not reachable
from the starting RenderObject.
To fix the above, make the SVGResourcesCycleSolver traverse the entire
resource "graph", and verify that it is acyclic. The cycle-checking is
achieved by keeping track of the current "path" through the graph, and
checking any discovered references against that set. When traversing
a subtree looking for references, any resources discovered will be skipped
to avoid inject false dependencies that way.
Also keep a simple "cache" of sub-graphs that has been checked already
(and verified cycle-free) to avoid having to revisit them.
BUG=351713
Review URL: https://codereview.chromium.org/303693009
git-svn-id: svn://svn.chromium.org/blink/trunk@175129 bbb929c8-8fbe-4397-9dbb-9b2b20218538
18 files changed
