CustomElementUpgradeSorter puts elements in shadow-including tree order.

CustomElementUpgradeSorter puts elements in shadow-including tree order.

This is part of "element definition", step 21.
https://html.spec.whatwg.org/multipage/scripting.html#dom-customelementsregistry-define

BUG=594918
Committed: https://crrev.com/be6415b2a676083838cb45ef84772819834a5b5e
Cr-Commit-Position: refs/heads/master@{#395014}

[dominicc (has gone to gerrit), 2016-05-20 00:56:18]

dominicc@chromium.org changed reviewers:
+ kojii@chromium.org

[dominicc (has gone to gerrit), 2016-05-20 00:56:19]

PTAL

I realize there are lots of approaches to this, and you can construct examples
that perform well or poorly for each.

In the worst case this is O(nodes in document) when each leaf node is one kind
of custom element. It temporarily uses a lot of additional space to build its
model of the document. In a pathological case like that a tree walk would be
better.

However documents probably use heterogeneous sets of elements, and towards the
leaves there are probably built-in elements, not custom elements. This probably
performs well in situations like that. It will walk over the elements of
interest; their ancestors; and at a given level any siblings up to the second
last ancestor of interest. (The "second last" bit comes from the early
termination when there's just one node remaining to explore. Which means that
singletons--which you'd expect to be common with deep chains of
ancestors--should still be acceptably fast.)

It might be better to make this non-recursive, but we can work on that later. I
wanted to keep it simple at first.

[kojii, 2016-05-20 05:02:46]

lgtm, agree to start simple.

[dominicc (has gone to gerrit), 2016-05-20 05:04:34]

The CQ bit was checked by dominicc@chromium.org

[commit-bot: I haz the power, 2016-05-20 05:04:49]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1995933005/1
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1995933005/1

[commit-bot: I haz the power, 2016-05-20 06:12:21]

Committed patchset #1 (id:1)

[commit-bot: I haz the power, 2016-05-20 06:14:47]

Description was changed from

==========
CustomElementUpgradeSorter puts elements in shadow-including tree order.

This is part of "element definition", step 21.
https://html.spec.whatwg.org/multipage/scripting.html#dom-customelementsregis...

BUG=594918
==========

to

==========
CustomElementUpgradeSorter puts elements in shadow-including tree order.

This is part of "element definition", step 21.
https://html.spec.whatwg.org/multipage/scripting.html#dom-customelementsregis...

BUG=594918

Committed: https://crrev.com/be6415b2a676083838cb45ef84772819834a5b5e
Cr-Commit-Position: refs/heads/master@{#395014}
==========

[commit-bot: I haz the power, 2016-05-20 06:14:48]

Patchset 1 (id:??) landed as
https://crrev.com/be6415b2a676083838cb45ef84772819834a5b5e
Cr-Commit-Position: refs/heads/master@{#395014}