Rebuild layout tree in flat tree order.

Rebuild layout tree in flat tree order.

Marking the DOM for layout tree rebuild and the actual rebuilding is
now contained in the lifecycle update at a point where the shadow dom
distribution is up-to-date. We can therefore safely mark the flat-tree
ancestor chain without risking that it's broken by a distribution.

The point of doing RebuildLayoutTree in flat tree order is that layout
boxes can then be re-attached in the layout tree order which makes it
simpler to handle whitespace reattachment. For shadow trees and slotted
elements, when using the shadow-including tree order, we could have
elements rebuild their layout boxes in an order arbitrarily decided by
the slot assignments and slot positions in the shadow tree.

Note that while the RebuildLayoutTree traversal used to happen in the
shadow-including order, the layout attachment already happens in the
flat tree order.

See [1] for a plan to fix correctness and performance of whitespace
re-attachment.

This CL is doing the following changes:

1. Modify MarkAncestorsWithChildNeedsReattachLayoutTree to mark flat
   tree ancestry.

2. Rebuild distributed children for InsertionPoint and HTMLSlotElement.
   These children were rebuilt after their host's shadow tree before
   this change.

3. Factored out RebuildLayoutTreeForChild() as common code for both
   walking light tree children in ContainerNode, and distributed
   children in InsertionPoint and HTMLSlotElement.

4. Made FinalDestinationSlot() a member of node instead of a static
   function as it is now needed in multiple files.

[1] http://bit.ly/2ozyBdx

Review-Url: https://codereview.chromium.org/2836753002
Cr-Commit-Position: refs/heads/master@{#471188}
Committed: https://chromium.googlesource.com/chromium/src/+/5e53c60ebe374282c8c2864a8e6d1d864afa221a

[rune, 2017-04-27 07:51:39]

The CQ bit was checked by rune@opera.com to run a CQ dry run

[commit-bot: I haz the power, 2017-04-27 07:51:56]

Dry run: CQ is trying da patch.

Follow status at:
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2017-04-27 09:34:54]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2017-04-27 09:34:55]

Dry run: This issue passed the CQ dry run.

[rune, 2017-04-27 11:06:07]

Description was changed from

==========
Rebuild layout tree in flat tree order.

*** NOT FOR LANDING ***

1. Modify MarkAncestorsWithChildNeedsReattachLayoutTree to mark flat
   tree ancestry.

2. Rebuild distributed children for InsertionPoint and HTMLSlotElement.
   These children were rebuilt after their host's shadow tree before
   this change.

3. Factored out RebuildLayoutTreeForChild() as common code for both
   walking light tree children in ContainerNode, and distributed
   children in InsertionPoint and HTMLSlotElement.
==========

to

==========
Rebuild layout tree in flat tree order.

Marking the DOM for layout tree rebuild and the actual rebuilding is
now contained in the lifecycle update at a point where the shadow dom
distribution is up-to-date. We can therefore safely mark the flat-tree
ancestor chain without risking that it's broken by a distribution.

The point of doing RebuildLayoutTree in flat tree order is that layout
boxes can then be re-attached in the layout tree order which makes it
simpler to handle whitespace reattachment. For shadow trees and slotted
elements, when using the shadow-including tree order, we could have
elements rebuild their layout boxes in an order arbitrarily decided by
the slot assignments and slot positions in the shadow tree.

Note that while the RebuildLayoutTree traversal used to happen in the
shadow-including order, the layout attachment already happens in the
flat tree order.

See [1] for a plan to fix correctness and performance of whitespace
re-attachment.

This CL is doing the following changes:

1. Modify MarkAncestorsWithChildNeedsReattachLayoutTree to mark flat
   tree ancestry.

2. Rebuild distributed children for InsertionPoint and HTMLSlotElement.
   These children were rebuilt after their host's shadow tree before
   this change.

3. Factored out RebuildLayoutTreeForChild() as common code for both
   walking light tree children in ContainerNode, and distributed
   children in InsertionPoint and HTMLSlotElement.

4. Made FinalDestinationSlot() a member of node instead of a static
   function as it is now needed in multiple files.

[1] http://bit.ly/2ozyBdx
==========

[rune, 2017-04-27 11:10:01]

rune@opera.com changed reviewers:
+ esprehn@chromium.org, meade@chromium.org, nainar@chromium.org

[rune, 2017-04-27 11:10:02]

While reviewing this, you should take a look at the design document if you
haven't already.

Re performance: I have run the blink_perf.shadow_dom tests locally without
seeing consistent regressions.

ptal.

[meade_UTC10, 2017-04-28 07:44:47]

This seems fine to me, but I'm not super familiar with this code - I imagine
nainar and esprehn can give a better review...

[esprehn, 2017-04-28 23:18:10]

I'm not sure I understand this change, you say:

"Rebuild distributed children for InsertionPoint and HTMLSlotElement.
   These children were rebuilt after their host's shadow tree before
   this change.
"

but we rebuild the distributed children inside InsertionPoint::AttachLayoutTree
today where we reattach all the distributed children. That looks the same as
what you're doing in this patch.

[rune, 2017-05-02 08:29:21]

On 2017/04/28 23:18:10, esprehn wrote:
> I'm not sure I understand this change, you say:
> 
> "Rebuild distributed children for InsertionPoint and HTMLSlotElement.
>    These children were rebuilt after their host's shadow tree before
>    this change.
> "
> 
> but we rebuild the distributed children inside
InsertionPoint::AttachLayoutTree
> today where we reattach all the distributed children. That looks the same as
> what you're doing in this patch.

During the rebuild-phase, we call RebuildLayoutTree and friends to walk down the
shadow-including tree until we reach a node which needs re-attachment. Then we
start AttachLayoutTree on that sub-tree in the flat tree order. This patch makes
the RebuildLayoutTree walk happen in the flat tree order as well. This is useful
because white-space re-attachment happens on siblings on the edge between
RebuildLayoutTree and AttachLayoutTree. We are tracking the next text node
sibling (walking backwards) in the RebuildLayoutTree machinery to figure out if
we need to add/remove a text layout object for white-space following re-attached
elements, but the need for a white-space layout object depends on flat tree
siblings, so the current code breaks down for shadow dom.

Example:

<div id="host">
  <:shadow-root>
    <div></div>
      <slot name="first"></slot>
      <span id="second"></span>
      <slot name="third"></slot>
    </div>
  </:shadow-root>
  <span slot="third"></span>
  <span slot="first"></span>
</div>

Say that all three spans need re-attachment. Without this patch, we would
re-attach them in the order: #second, #first, #third because the shadow-tree is
rebuilt before the light tree children of #host. This CL changes the
re-attachment to happen in this order: #third, #second, #first, which is the
reversed flat-tree order that we want for tracking white-space nodes.

[nainar, 2017-05-04 07:04:37]

Ran through the code and used your test case to step through the code. Makes
sense to me. LGTM.

[rune, 2017-05-04 08:35:54]

On 2017/05/04 07:04:37, nainar wrote:
> Ran through the code and used your test case to step through the code. Makes
> sense to me. LGTM.

I'll await a review from esprehn@

[rune, 2017-05-05 13:34:38]

On 2017/05/04 08:35:54, rune wrote:
> On 2017/05/04 07:04:37, nainar wrote:
> > Ran through the code and used your test case to step through the code. Makes
> > sense to me. LGTM.
> 
> I'll await a review from esprehn@

esprehn@: did my reply make it clearer?

[esprehn, 2017-05-11 22:28:41]

lgtm

[rune, 2017-05-11 22:50:50]

The CQ bit was checked by rune@opera.com

[rune, 2017-05-11 22:50:50]

The patchset sent to the CQ was uploaded after l-g-t-m from nainar@chromium.org,
esprehn@chromium.org
Link to the patchset: https://codereview.chromium.org/2836753002/#ps100001
(title: "Rebased")

[commit-bot: I haz the power, 2017-05-11 22:51:40]

CQ is trying da patch.

Follow status at:
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2017-05-12 02:27:11]

CQ is committing da patch.

Bot data: {"patchset_id": 100001, "attempt_start_ts": 1494543050388040,
"parent_rev": "e7e36ccdaa3fcf63b330bc956eeeb73abf7c39ea", "commit_rev":
"5e53c60ebe374282c8c2864a8e6d1d864afa221a"}

[commit-bot: I haz the power, 2017-05-12 02:27:23]

Description was changed from

==========
Rebuild layout tree in flat tree order.

Marking the DOM for layout tree rebuild and the actual rebuilding is
now contained in the lifecycle update at a point where the shadow dom
distribution is up-to-date. We can therefore safely mark the flat-tree
ancestor chain without risking that it's broken by a distribution.

The point of doing RebuildLayoutTree in flat tree order is that layout
boxes can then be re-attached in the layout tree order which makes it
simpler to handle whitespace reattachment. For shadow trees and slotted
elements, when using the shadow-including tree order, we could have
elements rebuild their layout boxes in an order arbitrarily decided by
the slot assignments and slot positions in the shadow tree.

Note that while the RebuildLayoutTree traversal used to happen in the
shadow-including order, the layout attachment already happens in the
flat tree order.

See [1] for a plan to fix correctness and performance of whitespace
re-attachment.

This CL is doing the following changes:

1. Modify MarkAncestorsWithChildNeedsReattachLayoutTree to mark flat
   tree ancestry.

2. Rebuild distributed children for InsertionPoint and HTMLSlotElement.
   These children were rebuilt after their host's shadow tree before
   this change.

3. Factored out RebuildLayoutTreeForChild() as common code for both
   walking light tree children in ContainerNode, and distributed
   children in InsertionPoint and HTMLSlotElement.

4. Made FinalDestinationSlot() a member of node instead of a static
   function as it is now needed in multiple files.

[1] http://bit.ly/2ozyBdx
==========

to

==========
Rebuild layout tree in flat tree order.

Marking the DOM for layout tree rebuild and the actual rebuilding is
now contained in the lifecycle update at a point where the shadow dom
distribution is up-to-date. We can therefore safely mark the flat-tree
ancestor chain without risking that it's broken by a distribution.

The point of doing RebuildLayoutTree in flat tree order is that layout
boxes can then be re-attached in the layout tree order which makes it
simpler to handle whitespace reattachment. For shadow trees and slotted
elements, when using the shadow-including tree order, we could have
elements rebuild their layout boxes in an order arbitrarily decided by
the slot assignments and slot positions in the shadow tree.

Note that while the RebuildLayoutTree traversal used to happen in the
shadow-including order, the layout attachment already happens in the
flat tree order.

See [1] for a plan to fix correctness and performance of whitespace
re-attachment.

This CL is doing the following changes:

1. Modify MarkAncestorsWithChildNeedsReattachLayoutTree to mark flat
   tree ancestry.

2. Rebuild distributed children for InsertionPoint and HTMLSlotElement.
   These children were rebuilt after their host's shadow tree before
   this change.

3. Factored out RebuildLayoutTreeForChild() as common code for both
   walking light tree children in ContainerNode, and distributed
   children in InsertionPoint and HTMLSlotElement.

4. Made FinalDestinationSlot() a member of node instead of a static
   function as it is now needed in multiple files.

[1] http://bit.ly/2ozyBdx

Review-Url: https://codereview.chromium.org/2836753002
Cr-Commit-Position: refs/heads/master@{#471188}
Committed:
https://chromium.googlesource.com/chromium/src/+/5e53c60ebe374282c8c2864a8e6d...
==========

[commit-bot: I haz the power, 2017-05-12 02:27:24]

Committed patchset #6 (id:100001) as
https://chromium.googlesource.com/chromium/src/+/5e53c60ebe374282c8c2864a8e6d...