[SVG] Resources should be laid out in dependecy order.

[SVG] Resources should be laid out in dependecy order.

We're currently laying out resources in tree order, while they are
(conceptually) forming a DAG - and this disconnect results in
complicated logic and an extra layout pass attempting to re-validate
nodes that might have been invalidated by the resource layout. This is
broken in (at least) two ways:

  * two passes are not guaranteed to be enough, we could need an
    arbitrary number of passes to stabilize the tree.
  * the re-layout logic hangs off RenderSVGRoot, and falls apart when
    multiple root nodes are present (html doc with multiple svg fragments).

Recently introduced asserts are testing for render tree nodes which are
still marked for layout at paint time, and are catching several invariant
violations due to the above.

To address this problem, we should lay out resources in transitive
dependency order (where node A depends on resource B if it references
it directly: <rect id="a" filter="url(#b)"/>). Turns out this is not as
complicated as it sounds, and we can avoid building an explicit resources
DAG because we already have the sparse version: each node tracks the list
of resources it is referencing.

So before laying out a node, we should ensure that its resources are laid
out first. Applying this recursively, we are effectively traversing the
dependency DAG in the correct order.

(This relies on the assumption that a resource' layout does not depend on
its in-tree parent layout - which should be the case as resources only
make sense in the context of their clients).

The CL also removes the RenderSVGRoot re-layout logic added in
http://trac.webkit.org/changeset/111601 as it is no longer needed: a
resource is now guaranteed to be laid out before any of its clients.

BUG=282925, 294237, 294238
R=pdr@chromium.org,schenney@chromium.org,dschulze@chromium.org,ojan@chromium.org,eseidel@chromium.org

Committed: https://src.chromium.org/viewvc/blink?view=rev&revision=158480

[f(malita), 2013-09-18 22:34:58]

I don't think this fixes all the resource related issues, but it should at least
solve the layout order problem. Off the top of my head, a couple of other things
that bother me about resources:

* We have a one-to-many RenderSVGResourceContainer<->clients relationship, so
the layout of the resource container has to be truly independent of its clients
and its own container. That probably *should* be the case, but I suspect
RenderSVGResourceContainer is not properly sealed and some of its children might
be poking at the containing block chain at layout time (RenderSVGText?). If this
turns out to be a problem we may have to resort to instantiating one resource
renderer per client and lay it out in the appropriate context.
* Marking nodes for layout during layout seems like asking for trouble. The
invalidation logic (markForLayoutAndParentResourceInvalidation & friends) should
be triggered at attribute change time and not during layout.

I've also included all the current test diffs for review, but I'm still
investigating 3 of them so the rebaseline is not definitive:

- svg/text/text-layout-crash.html
- svg/custom/unicode-in-tspan-multi-svg-crash.html
^^ The new results for these are likely correct (the text should be visible).

- svg/W3C-SVG-1.1/masking-path-04-b.svg
- svg/custom/mask-with-default-value.svg
- svg/custom/masking-clipping-hidpi.svg
^^ Minor resource layout diff. This could be an unrelated issue that was
previously masked by multiple layout passes. Still investigating.

[pdr., 2013-09-18 22:47:35]

Really really really amazing Florin!

https://codereview.chromium.org/23785014/diff/1/LayoutTests/svg/text/text-lay...
File LayoutTests/svg/text/text-layout-crash-expected.txt (right):

https://codereview.chromium.org/23785014/diff/1/LayoutTests/svg/text/text-lay...
LayoutTests/svg/text/text-layout-crash-expected.txt:2: bc
These test failures look real (or need more investigation)

https://codereview.chromium.org/23785014/diff/1/Source/core/rendering/svg/Ren...
File Source/core/rendering/svg/RenderSVGRoot.cpp (right):

https://codereview.chromium.org/23785014/diff/1/Source/core/rendering/svg/Ren...
Source/core/rendering/svg/RenderSVGRoot.cpp:211: // Layout own resources.
Lets pull this out into a helper.

[f(malita), 2013-09-19 15:13:21]

https://codereview.chromium.org/23785014/diff/1/LayoutTests/svg/text/text-lay...
File LayoutTests/svg/text/text-layout-crash-expected.txt (right):

https://codereview.chromium.org/23785014/diff/1/LayoutTests/svg/text/text-lay...
LayoutTests/svg/text/text-layout-crash-expected.txt:2: bc
On 2013/09/18 22:47:35, pdr wrote:
> These test failures look real (or need more investigation)

Not sure about this one - it looks bad, but it's actually related/close to what
the test is doing:

<script>
  if (window.testRunner)
    testRunner.dumpAsText();

  onload = function() {
    document.body.offsetTop;
    document.body.style.zoom=0.9;

    document.designMode='on';
    window.getSelection().setBaseAndExtent(filterInFirstRoot, 0, 5);
    document.execCommand('ForwardDelete');
  }
</script>
This test passes if it does not crash.<br/>
<svg id="111">
  <text direction="rtl" id="filterInFirstRoot">
    <tspan id="tSpanInFirstRoot">abc<U+E47E></tspan>
  </text>
  <path filter="url(#filterInSecondRoot)"></path>
</svg>

I don't fully understand what the above is trying to do or what the expected
result is (CF generated?). But it seems plausible that
document.execCommand('ForwardDelete') is zapping the 'a' and the rest is left
alone (and should be visible in the text dump).

For unicode-in-tspan-multi-svg-crash.html OTOH, I think the new result is
correct: we were failing to correctly lay out cross-svgroot before, but now that
it's working the unicode chars are showing up. FF is also displaying them.

Still looking at the other test diffs.

[ojan, 2013-09-19 19:18:11]

> * Marking nodes for layout during layout seems like asking for trouble. The
> invalidation logic (markForLayoutAndParentResourceInvalidation & friends)
should
> be triggered at attribute change time and not during layout.

YES!

[f(malita), 2013-09-20 23:04:29]

Figured where some of the minor test layout diffs are coming from, and it's not
pretty: we *are* resolving resource containers relative lengths against their
in-tree/parent viewport (instead of the client viewport), violating the CL
assumptions. This is plain wrong (see
https://code.google.com/p/chromium/issues/detail?id=294900), but given the
current one-resource-container-for-multiple-clients model there's no easy way
around it.

Since the CL suppresses resource container invalidations during parent layout,
we end up missing viewport resize events:

         SubtreeLayoutScope layoutScope(child);
-        if (needsLayout)
+        if (needsLayout && !child->isSVGResourceContainer())
             layoutScope.setNeedsLayout(child);

Unfortunately we can't just switch that back, because invalidating the resources
at this point may and up invalidating random clients outside of the current
SubtreeLayoutScope - and we're back to square one.

One way to solve this is to make sure resource containers are invalidated at a
higher level, in a SubtreeLayoutScope that includes all their possible clients.
I have a version of the CL that uses existing
SVGElement::m_elementsWithRelativeLengths maps and hooks into
RenderView::layout() &  SVGSVGElement::svgAttributeChanged() to accomplish this.
Not sure how I feel about it: it seems a bit too dirty even for an interim fix,
while we're working on refactoring resources from ground up. Maybe we should
just hack something in place that disallows cross-SVGRoot resource references?
I'll post it anyway, let me know what you think.

[pdr., 2013-09-23 22:26:00]

I think we should get this in sooner rather than later. It solves a bunch of
critical security issues in our layout system.

https://codereview.chromium.org/23785014/diff/12001/Source/core/rendering/Ren...
File Source/core/rendering/RenderView.cpp (right):

https://codereview.chromium.org/23785014/diff/12001/Source/core/rendering/Ren...
Source/core/rendering/RenderView.cpp:278: // SVG resource containers need to be
invalidated outside any particular SVG root layout scope.
This comment isn't actually helpful. Can you expand on why?

https://codereview.chromium.org/23785014/diff/12001/Source/core/rendering/svg...
File Source/core/rendering/svg/RenderSVGResourceContainer.cpp (right):

https://codereview.chromium.org/23785014/diff/12001/Source/core/rendering/svg...
Source/core/rendering/svg/RenderSVGResourceContainer.cpp:57: if (!needsLayout()
|| m_isInLayout)
Should these be asserts?

https://codereview.chromium.org/23785014/diff/12001/Source/core/rendering/svg...
File Source/core/rendering/svg/RenderSVGResourceContainer.h (right):

https://codereview.chromium.org/23785014/diff/12001/Source/core/rendering/svg...
Source/core/rendering/svg/RenderSVGResourceContainer.h:63: bool m_isInLayout;
Can you use ": 1" to save some bits?

https://codereview.chromium.org/23785014/diff/12001/Source/core/rendering/svg...
File Source/core/rendering/svg/RenderSVGResourceMarker.cpp (right):

https://codereview.chromium.org/23785014/diff/12001/Source/core/rendering/svg...
Source/core/rendering/svg/RenderSVGResourceMarker.cpp:49: if (!needsLayout() ||
m_isInLayout)
Ditto on asserts

https://codereview.chromium.org/23785014/diff/12001/Source/core/svg/SVGElemen...
File Source/core/svg/SVGElement.cpp (right):

https://codereview.chromium.org/23785014/diff/12001/Source/core/svg/SVGElemen...
Source/core/svg/SVGElement.cpp:472: for (HashSet<SVGElement*>::iterator it =
m_elementsWithRelativeLengths.begin(); it != end; ++it) {
This always scares me. Are we sure nothing in this loop can modify
m_elementsWithRelativeLengths? Can we assert it?

[f(malita), 2013-09-23 23:20:33]

https://codereview.chromium.org/23785014/diff/12001/Source/core/rendering/Ren...
File Source/core/rendering/RenderView.cpp (right):

https://codereview.chromium.org/23785014/diff/12001/Source/core/rendering/Ren...
Source/core/rendering/RenderView.cpp:278: // SVG resource containers need to be
invalidated outside any particular SVG root layout scope.
On 2013/09/23 22:26:02, pdr wrote:
> This comment isn't actually helpful. Can you expand on why?

Didn't want to just duplicate the info in SVGRenderSupport::layoutChildren, but
I guess it should make sense on its own. Will do.

https://codereview.chromium.org/23785014/diff/12001/Source/core/rendering/svg...
File Source/core/rendering/svg/RenderSVGResourceContainer.cpp (right):

https://codereview.chromium.org/23785014/diff/12001/Source/core/rendering/svg...
Source/core/rendering/svg/RenderSVGResourceContainer.cpp:57: if (!needsLayout()
|| m_isInLayout)
On 2013/09/23 22:26:02, pdr wrote:
> Should these be asserts?

m_isInLayout is used for runtime layout cycle detection, so it cannot be
asserted.

We can probably turn the needsLayout() check into an assert though - we're only
calling layout() if needed.

https://codereview.chromium.org/23785014/diff/12001/Source/core/rendering/svg...
File Source/core/rendering/svg/RenderSVGResourceContainer.h (right):

https://codereview.chromium.org/23785014/diff/12001/Source/core/rendering/svg...
Source/core/rendering/svg/RenderSVGResourceContainer.h:63: bool m_isInLayout;
On 2013/09/23 22:26:02, pdr wrote:
> Can you use ": 1" to save some bits?

Tried that, but TemporaryChange<bool> barfed on it :(. Maybe we can fix the
template, but OTOH there are no adjacent bitfields so alignment will likely wipe
whatever we'd be saving.

https://codereview.chromium.org/23785014/diff/12001/Source/core/svg/SVGElemen...
File Source/core/svg/SVGElement.cpp (right):

https://codereview.chromium.org/23785014/diff/12001/Source/core/svg/SVGElemen...
Source/core/svg/SVGElement.cpp:472: for (HashSet<SVGElement*>::iterator it =
m_elementsWithRelativeLengths.begin(); it != end; ++it) {
On 2013/09/23 22:26:02, pdr wrote:
> This always scares me. Are we sure nothing in this loop can modify
> m_elementsWithRelativeLengths? Can we assert it?

Pretty sure:

* the only way to modify m_elementsWithRelativeLengths is via
updateRelativeLengthsInformation, which is only called on node
insertions/removal + svgAttributeChanged().
* the only call in the loop is setNeedsLayout, which should not trigger any of
the above.

I'll see if I can come up with a way to assert this.

[Stephen Chennney, 2013-09-25 19:31:36]

While this leaves me feeling embarassed, I'm not convinced this solves the
problem. I'm concerned about the case where the resource is deep in a tree and
gets marked as invalidated after a large portion of its subtree has already been
laid out. This causes all of the previously laid out subtree to be marked as
needing layout, all the way up to an ancestor that is still laying out.

Now that resource itself will be laid out before getting used again, but what
about the rest of the subtree? Do we not care about non-resource-nodes needing
layout? Does layoutIfNeeded take care of this problem for us? What am I missing,
if anything?

This issue with the rest of the subtree is why I didn't consider this approach
way back when. I didn't think laying out just the resources was enough. All of
the hardening of text run handling has masked most of the bugs with other nodes
not getting layout.

I'm also late to the party so missed the patch that added checks for things
being correctly laid out. Is that equivalent to jamesr's old patch that asserts
that nothing needs layout after layout?

[Stephen Chennney, 2013-09-25 19:33:32]

Sorry, not quite right about marking something deep in a subtree for layout
during layout. It marks all the ancestors up to the currently laying-out node as
needing layout, but not their children IIRC.

[f(malita), 2013-09-25 21:13:44]

On 2013/09/25 19:31:36, Stephen Chenney wrote:
> I'm concerned about the case where the resource is deep in a tree and
> gets marked as invalidated after a large portion of its subtree has already
been
> laid out. This causes all of the previously laid out subtree to be marked as
> needing layout, all the way up to an ancestor that is still laying out.

I *think* I understand your concern, but just to be sure can you maybe come up
with a specific example to discuss?

One significant change that the CL introduces is that we are no longer
invalidating resource containers *during* layout
(SVGRenderSupport::layoutChildren):

         SubtreeLayoutScope layoutScope(child);
-        if (needsLayout)
+        if (needsLayout && !child->isSVGResourceContainer())
             layoutScope.setNeedsLayout(child);

Since the only external (non-descendant) change that affects resource containers
is a viewport change (which causes relative length recalc), we are now
invalidating resource containers either outside layout (at SVGSVGElement
attribute change time), or at a higher level during layout (RenderView::layout).


So basically if a resource container needs invalidation, that should happen
before we even enter the SVG root layout scope. Once we enter that scope we
should no longer invalidate resource containers. Elements referencing resource
containers will trigger their layout; during resource container layout we do
invalidate all the clients, but OTOH this is guaranteed to happen before we
layout any of the clients (first client to be laid out triggers the resource
layout) - so it should be fine.

[Stephen Chennney, 2013-09-25 21:33:35]

On 2013/09/25 21:13:44, Florin Malita wrote:
> On 2013/09/25 19:31:36, Stephen Chenney wrote:
> > I'm concerned about the case where the resource is deep in a tree and
> > gets marked as invalidated after a large portion of its subtree has already
> been
> > laid out. This causes all of the previously laid out subtree to be marked as
> > needing layout, all the way up to an ancestor that is still laying out.
> 
> I *think* I understand your concern, but just to be sure can you maybe come up
> with a specific example to discuss?
> 
> One significant change that the CL introduces is that we are no longer
> invalidating resource containers *during* layout
> (SVGRenderSupport::layoutChildren):
> 
>          SubtreeLayoutScope layoutScope(child);
> -        if (needsLayout)
> +        if (needsLayout && !child->isSVGResourceContainer())
>              layoutScope.setNeedsLayout(child);
> 
> Since the only external (non-descendant) change that affects resource
containers
> is a viewport change (which causes relative length recalc), we are now
> invalidating resource containers either outside layout (at SVGSVGElement
> attribute change time), or at a higher level during layout
(RenderView::layout).
> 
> 
> So basically if a resource container needs invalidation, that should happen
> before we even enter the SVG root layout scope. Once we enter that scope we
> should no longer invalidate resource containers. Elements referencing resource
> containers will trigger their layout; during resource container layout we do
> invalidate all the clients, but OTOH this is guaranteed to happen before we
> layout any of the clients (first client to be laid out triggers the resource
> layout) - so it should be fine.

Yeah, I see. I don't think we can cause the problem for the resources case so I
am fine with submitting this, pdr has put more time into it, so I will defer to
him for final.

I wonder how many existing bugs this will fix, particularly those related to
resources appearing after their client in the DOM. There is one I remember about
horizontal and vertical lines not appearing due to a clip problem.

[pdr., 2013-09-25 22:35:39]

On 2013/09/25 21:33:35, Stephen Chenney wrote:
> On 2013/09/25 21:13:44, Florin Malita wrote:
> > On 2013/09/25 19:31:36, Stephen Chenney wrote:
> > > I'm concerned about the case where the resource is deep in a tree and
> > > gets marked as invalidated after a large portion of its subtree has
already
> > been
> > > laid out. This causes all of the previously laid out subtree to be marked
as
> > > needing layout, all the way up to an ancestor that is still laying out.
> > 
> > I *think* I understand your concern, but just to be sure can you maybe come
up
> > with a specific example to discuss?
> > 
> > One significant change that the CL introduces is that we are no longer
> > invalidating resource containers *during* layout
> > (SVGRenderSupport::layoutChildren):
> > 
> >          SubtreeLayoutScope layoutScope(child);
> > -        if (needsLayout)
> > +        if (needsLayout && !child->isSVGResourceContainer())
> >              layoutScope.setNeedsLayout(child);
> > 
> > Since the only external (non-descendant) change that affects resource
> containers
> > is a viewport change (which causes relative length recalc), we are now
> > invalidating resource containers either outside layout (at SVGSVGElement
> > attribute change time), or at a higher level during layout
> (RenderView::layout).
> > 
> > 
> > So basically if a resource container needs invalidation, that should happen
> > before we even enter the SVG root layout scope. Once we enter that scope we
> > should no longer invalidate resource containers. Elements referencing
resource
> > containers will trigger their layout; during resource container layout we do
> > invalidate all the clients, but OTOH this is guaranteed to happen before we
> > layout any of the clients (first client to be laid out triggers the resource
> > layout) - so it should be fine.
> 
> Yeah, I see. I don't think we can cause the problem for the resources case so
I
> am fine with submitting this, pdr has put more time into it, so I will defer
to
> him for final.
> 
> I wonder how many existing bugs this will fix, particularly those related to
> resources appearing after their client in the DOM. There is one I remember
about
> horizontal and vertical lines not appearing due to a clip problem.

Florin and I were sitting next to eachother which is why it may seem like we're
rushing this through. If you're available tomorrow at 10:30PST / 1:30EST, can we
discuss it during the svg sync? We could definitely use your input here :)

[pdr., 2013-09-28 00:15:51]

On 2013/09/25 22:35:39, pdr wrote:
> On 2013/09/25 21:33:35, Stephen Chenney wrote:
> > On 2013/09/25 21:13:44, Florin Malita wrote:
> > > On 2013/09/25 19:31:36, Stephen Chenney wrote:
> > > > I'm concerned about the case where the resource is deep in a tree and
> > > > gets marked as invalidated after a large portion of its subtree has
> already
> > > been
> > > > laid out. This causes all of the previously laid out subtree to be
marked
> as
> > > > needing layout, all the way up to an ancestor that is still laying out.
> > > 
> > > I *think* I understand your concern, but just to be sure can you maybe
come
> up
> > > with a specific example to discuss?
> > > 
> > > One significant change that the CL introduces is that we are no longer
> > > invalidating resource containers *during* layout
> > > (SVGRenderSupport::layoutChildren):
> > > 
> > >          SubtreeLayoutScope layoutScope(child);
> > > -        if (needsLayout)
> > > +        if (needsLayout && !child->isSVGResourceContainer())
> > >              layoutScope.setNeedsLayout(child);
> > > 
> > > Since the only external (non-descendant) change that affects resource
> > containers
> > > is a viewport change (which causes relative length recalc), we are now
> > > invalidating resource containers either outside layout (at SVGSVGElement
> > > attribute change time), or at a higher level during layout
> > (RenderView::layout).
> > > 
> > > 
> > > So basically if a resource container needs invalidation, that should
happen
> > > before we even enter the SVG root layout scope. Once we enter that scope
we
> > > should no longer invalidate resource containers. Elements referencing
> resource
> > > containers will trigger their layout; during resource container layout we
do
> > > invalidate all the clients, but OTOH this is guaranteed to happen before
we
> > > layout any of the clients (first client to be laid out triggers the
resource
> > > layout) - so it should be fine.
> > 
> > Yeah, I see. I don't think we can cause the problem for the resources case
so
> I
> > am fine with submitting this, pdr has put more time into it, so I will defer
> to
> > him for final.
> > 
> > I wonder how many existing bugs this will fix, particularly those related to
> > resources appearing after their client in the DOM. There is one I remember
> about
> > horizontal and vertical lines not appearing due to a clip problem.
> 
> Florin and I were sitting next to eachother which is why it may seem like
we're
> rushing this through. If you're available tomorrow at 10:30PST / 1:30EST, can
we
> discuss it during the svg sync? We could definitely use your input here :)

Sadly I was out sick and Florin was traveling so this sync never materialized.
Lets discuss this on Tuesday for sure.

LGTM to commit because this fixes a huge number of security issues in SVG.

[commit-bot: I haz the power, 2013-09-28 00:40:22]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/fmalita@chromium.org/23785014/48001

[commit-bot: I haz the power, 2013-09-28 04:17:29]

Change committed as 158480