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

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
Committed: https://src.chromium.org/viewvc/blink?view=rev&revision=175129

[fs, 2014-05-28 08:45:41]

This got more involved than had initially had hoped, but bugs with the old code
just kept popping up... I feel the the new code isn't terribly complicated
though so hopefully it's not too bad to review. Since more eyeballs make all
bugs shallow (I hear =)) I figured I'd add a whole bunch of reviewer to this
one, so PTAL and let me know of any issues you and any additional (corner)cases
you can dream up.

[krit, 2014-05-28 10:22:29]

Btw. does https://bugs.webkit.org/show_bug.cgi?id=130127 pass with the change?

https://codereview.chromium.org/303693009/diff/1/Source/core/rendering/svg/SV...
File Source/core/rendering/svg/SVGResourcesCycleSolver.cpp (right):

https://codereview.chromium.org/303693009/diff/1/Source/core/rendering/svg/SV...
Source/core/rendering/svg/SVGResourcesCycleSolver.cpp:50: class
SVGResourcesCycleSolver::ActiveFrame {
It seems like it could be a struct. The definition could even go into the
header.

https://codereview.chromium.org/303693009/diff/1/Source/core/rendering/svg/SV...
Source/core/rendering/svg/SVGResourcesCycleSolver.cpp:65:
RenderSVGResourceContainer* m_resource;
With activeSet, you mean visited resources? And m_resource is current resource?
We should use some clear terms here.

https://codereview.chromium.org/303693009/diff/1/Source/core/rendering/svg/SV...
Source/core/rendering/svg/SVGResourcesCycleSolver.cpp:70: // If we've traversed
this sub-graph before and no cycles were observed, then
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.

https://codereview.chromium.org/303693009/diff/1/Source/core/rendering/svg/SV...
Source/core/rendering/svg/SVGResourcesCycleSolver.cpp:114: do {
why not while() {}? parent is not checked here.

https://codereview.chromium.org/303693009/diff/1/Source/core/rendering/svg/SV...
File Source/core/rendering/svg/SVGResourcesCycleSolver.h (right):

https://codereview.chromium.org/303693009/diff/1/Source/core/rendering/svg/SV...
Source/core/rendering/svg/SVGResourcesCycleSolver.h:41: bool
resourceContainsCycles(RenderSVGResourceContainer*);
Are all renderers that we ever want to track are SVG ResourceContainers? I am
more thinking into the future here. At the moment this is probably correct. We
just have SVG gradients, patterns, filters, clip path, markers, masks.

https://codereview.chromium.org/303693009/diff/1/Source/core/rendering/svg/SV...
Source/core/rendering/svg/SVGResourcesCycleSolver.h:44: class ActiveFrame;
Does that need to be a class? If it is private, a simple struct seems to do it.

[fs, 2014-05-28 11:23:47]

Thanks for looking.

> Btw. does https://bugs.webkit.org/show_bug.cgi?id=130127 pass with the change?

I added it as a LayoutTest, so I hope it does =)

https://codereview.chromium.org/303693009/diff/1/Source/core/rendering/svg/SV...
File Source/core/rendering/svg/SVGResourcesCycleSolver.cpp (right):

https://codereview.chromium.org/303693009/diff/1/Source/core/rendering/svg/SV...
Source/core/rendering/svg/SVGResourcesCycleSolver.cpp:50: class
SVGResourcesCycleSolver::ActiveFrame {
On 2014/05/28 10:22:30, krit wrote:
> It seems like it could be a struct. The definition could even go into the
> header.

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.

https://codereview.chromium.org/303693009/diff/1/Source/core/rendering/svg/SV...
Source/core/rendering/svg/SVGResourcesCycleSolver.cpp:65:
RenderSVGResourceContainer* m_resource;
On 2014/05/28 10:22:30, krit wrote:
> With activeSet, you mean visited resources? And m_resource is current
resource?
> We should use some clear terms here.

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?

https://codereview.chromium.org/303693009/diff/1/Source/core/rendering/svg/SV...
Source/core/rendering/svg/SVGResourcesCycleSolver.cpp:70: // If we've traversed
this sub-graph before and no cycles were observed, then
On 2014/05/28 10:22:30, krit wrote:
> 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.

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.

https://codereview.chromium.org/303693009/diff/1/Source/core/rendering/svg/SV...
Source/core/rendering/svg/SVGResourcesCycleSolver.cpp:114: do {
On 2014/05/28 10:22:30, krit wrote:
> why not while() {}? parent is not checked here.

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

https://codereview.chromium.org/303693009/diff/1/Source/core/rendering/svg/SV...
File Source/core/rendering/svg/SVGResourcesCycleSolver.h (right):

https://codereview.chromium.org/303693009/diff/1/Source/core/rendering/svg/SV...
Source/core/rendering/svg/SVGResourcesCycleSolver.h:41: bool
resourceContainsCycles(RenderSVGResourceContainer*);
On 2014/05/28 10:22:30, krit wrote:
> Are all renderers that we ever want to track are SVG ResourceContainers? I am
> more thinking into the future here. At the moment this is probably correct. We
> just have SVG gradients, patterns, filters, clip path, markers, masks.

Did you have anything in particular predicted for the future? =)

I think this makes sense in the current scope and usage of things. Generalizing
wouldn't be hard though I think, but preferably that's something to do when it's
actually needed. (And after all, this is the SVG_Resource_CycleSolver ;-))

https://codereview.chromium.org/303693009/diff/1/Source/core/rendering/svg/SV...
Source/core/rendering/svg/SVGResourcesCycleSolver.h:44: class ActiveFrame;
On 2014/05/28 10:22:30, krit wrote:
> Does that need to be a class? If it is private, a simple struct seems to do
it.

I guess I instinctively make things class:es when nothing else needs to access
it's data members.

[krit, 2014-05-28 11:33:48]

On 2014/05/28 11:23:47, fs wrote:
>
https://codereview.chromium.org/303693009/diff/1/Source/core/rendering/svg/SV...
> Source/core/rendering/svg/SVGResourcesCycleSolver.cpp:65:
> RenderSVGResourceContainer* m_resource;
> On 2014/05/28 10:22:30, krit wrote:
> > With activeSet, you mean visited resources? And m_resource is current
> resource?
> > We should use some clear terms here.
> 
> 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?
> 

We are basically traversing a graph and looking for cycles. A graph consists of
nodes and edges. In graph theory we decide between three kind of nodes. The
unvisited nodes need to be checked still. The visited nodes are marked as cycle
free. So you are probably right to call the currently checked nodes active. I
think I can live with that.

I am find to add the definition of the struct to the cpp file. Both patterns are
used across core.

[f(malita), 2014-05-28 22:30:34]

Looks like a great cleanup, and should be a net improvement but I have some
SVGResourcesCycleSolver meta-questions.

How does this interact with other resource cycle detection mechanisms we have
sprinkled throughout the SVG code (RenderSVGResourceContainer::layout,
RenderSVGResourceFilter::applyResource, etc.)? I wonder whether those are in
place just because SVGResourcesCycleSolver was borked and can now be removed.

On one hand it's nice to have a catch-all place to break these cycles early, but
OTOH late detection may be significantly cheaper (we're traversing the graph
anyway for layout/paint/etc) and we could avoid building this expensive
transitive closure on every resource update (heck, looks like every client style
update even). Radical thought: what happens if we drop SVGResourcesCycleSolver
altogether and instead focus on detecting cycles at processing time (marking
resource nodes as active on the fly)? Seems like a PITA to prove
correctness/adequate coverage, but maybe there's some way to funnel resource
access through an API that enforces it?

Anyway, I like the patch and will take a closer look - these are somewhat
related ramblings :)

https://codereview.chromium.org/303693009/diff/20001/Source/core/rendering/sv...
File Source/core/rendering/svg/SVGResourcesCycleSolver.cpp (right):

https://codereview.chromium.org/303693009/diff/20001/Source/core/rendering/sv...
Source/core/rendering/svg/SVGResourcesCycleSolver.cpp:78: while (child) {
Nit: I think expressing this as a for loop makes the intent clearer upfront.

[f(malita), 2014-05-29 20:49:28]

Please add a couple of dynamic tests where we construct an un-attached subtree
(which contains either full resource cycles or back-edges into the existing
tree), then append it to the DOM atomically.

https://codereview.chromium.org/303693009/diff/20001/Source/core/rendering/sv...
File Source/core/rendering/svg/SVGResourcesCycleSolver.cpp (right):

https://codereview.chromium.org/303693009/diff/20001/Source/core/rendering/sv...
Source/core/rendering/svg/SVGResourcesCycleSolver.cpp:77: RenderObject* child =
resource;
"child" (for me at least) has a direct-descendant connotation. Maybe we should
rename it to "descendent" or "node" (plus a "current" prefix to reflect the
iterator role)?

https://codereview.chromium.org/303693009/diff/20001/Source/core/rendering/sv...
Source/core/rendering/svg/SVGResourcesCycleSolver.cpp:78: while (child) {
On 2014/05/28 22:30:34, Florin Malita wrote:
> Nit: I think expressing this as a for loop makes the intent clearer upfront.

Never mind, I see that it wouldn't work well given the current skip semantics.

https://codereview.chromium.org/303693009/diff/20001/Source/core/rendering/sv...
Source/core/rendering/svg/SVGResourcesCycleSolver.cpp:112: // "initiating"
resource.)
Not sure this is worth the effort: for the most common case (when the renderer
is not under a resource container) this will just create extra work by crawling
all the way to the root, no?

[fs, 2014-05-30 11:13:53]

> Looks like a great cleanup, and should be a net improvement but I have some
> SVGResourcesCycleSolver meta-questions.

Thanks, that's indeed some interesting notes.

> How does this interact with other resource cycle detection mechanisms we have
> sprinkled throughout the SVG code (RenderSVGResourceContainer::layout,
> RenderSVGResourceFilter::applyResource, etc.)? I wonder whether those are in
> place just because SVGResourcesCycleSolver was borked and can now be removed.

I'll see if I can work that out (hopefully there some form of regression tests
for those.)

> On one hand it's nice to have a catch-all place to break these cycles early,
but
> OTOH late detection may be significantly cheaper (we're traversing the graph
> anyway for layout/paint/etc) and we could avoid building this expensive
> transitive closure on every resource update (heck, looks like every client
style
> update even). Radical thought: what happens if we drop SVGResourcesCycleSolver
> altogether and instead focus on detecting cycles at processing time (marking
> resource nodes as active on the fly)? Seems like a PITA to prove
> correctness/adequate coverage, but maybe there's some way to funnel resource
> access through an API that enforces it?

That's certainly a model I'd be willing to explore/support. In Presto we did it
that way: In the (rough) equivalent of layout() we would track the set of active
resources, and then every time a resource reference needed to be "followed" the
active set was consulted. It's quite possible that a lot/most of the logic could
be hidden in some reasonable place - a good/nice place to store the "active set"
might be trickier (but maybe not.)

> Please add a couple of dynamic tests where we construct an un-attached subtree
> (which contains either full resource cycles or back-edges into the existing
> tree), then append it to the DOM atomically.

I'll try to cook some up.

https://codereview.chromium.org/303693009/diff/20001/Source/core/rendering/sv...
File Source/core/rendering/svg/SVGResourcesCycleSolver.cpp (right):

https://codereview.chromium.org/303693009/diff/20001/Source/core/rendering/sv...
Source/core/rendering/svg/SVGResourcesCycleSolver.cpp:112: // "initiating"
resource.)
On 2014/05/29 20:49:28, Florin Malita wrote:
> Not sure this is worth the effort: for the most common case (when the renderer
> is not under a resource container) this will just create extra work by
crawling
> all the way to the root, no?

Yeah, I'm not really convinced this is such a grand optimization either... Not
that I think a the depth is usually that high either, but it certainly is
questionable for the cases _with_ cycles. Dropping the ancestor-walk (keeping
m_renderer if it's a resource container since that's still required I believe).

[fs, 2014-05-30 12:06:36]

On 2014/05/30 11:13:53, fs wrote:
> > Please add a couple of dynamic tests where we construct an un-attached
subtree
> > (which contains either full resource cycles or back-edges into the existing
> > tree), then append it to the DOM atomically.
> 
> I'll try to cook some up.
 
Dish completed.

[f(malita), 2014-05-30 13:06:21]

On 2014/05/30 12:06:36, fs wrote:
> On 2014/05/30 11:13:53, fs wrote:
> > > Please add a couple of dynamic tests where we construct an un-attached
> subtree
> > > (which contains either full resource cycles or back-edges into the
existing
> > > tree), then append it to the DOM atomically.
> > 
> > I'll try to cook some up.
>  
> Dish completed.

Thanks, LGTM.

[fs, 2014-05-30 13:30:42]

The CQ bit was checked by fs@opera.com

[commit-bot: I haz the power, 2014-05-30 13:31:17]

CQ is trying da patch. Follow status at
 https://chromium-status.appspot.com/cq/fs@opera.com/303693009/60001

[commit-bot: I haz the power, 2014-05-30 13:55:57]

Change committed as 175129