Bug 149997 - Implement iterator for traversing composed DOM
Summary: Implement iterator for traversing composed DOM
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: DOM (show other bugs)
Version: WebKit Nightly Build
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Nobody
URL:
Keywords:
Depends on: 150004
Blocks: 148695
  Show dependency treegraph
 
Reported: 2015-10-10 03:33 PDT by Antti Koivisto
Modified: 2016-06-13 13:09 PDT (History)
4 users (show)

See Also:


Attachments
patch (30.74 KB, patch)
2015-10-12 12:06 PDT, Antti Koivisto
buildbot: commit-queue-
Details | Formatted Diff | Diff
Archive of layout-test-results from ews104 for mac-mavericks-wk2 (712.54 KB, application/zip)
2015-10-12 12:44 PDT, Build Bot
no flags Details
patch (35.82 KB, patch)
2015-10-12 12:59 PDT, Antti Koivisto
no flags Details | Formatted Diff | Diff
patch (39.16 KB, patch)
2015-10-12 13:06 PDT, Antti Koivisto
rniwa: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Antti Koivisto 2015-10-10 03:33:51 PDT
This is needed for example to get RenderTreePosition right.
Comment 1 Antti Koivisto 2015-10-12 12:06:48 PDT
Created attachment 262910 [details]
patch
Comment 2 Build Bot 2015-10-12 12:44:44 PDT
Comment on attachment 262910 [details]
patch

Attachment 262910 [details] did not pass mac-wk2-ews (mac-wk2):
Output: http://webkit-queues.webkit.org/results/272342

New failing tests:
fullscreen/full-screen-fixed-pos-parent.html
fast/html/details-open2.html
fast/forms/select-listbox-focus-displaynone.html
fast/repaint/text-in-relative-positioned-inline.html
fast/html/details-add-child-2.html
Comment 3 Build Bot 2015-10-12 12:44:46 PDT
Created attachment 262912 [details]
Archive of layout-test-results from ews104 for mac-mavericks-wk2

The attached test failures were seen while running run-webkit-tests on the mac-wk2-ews.
Bot: ews104  Port: mac-mavericks-wk2  Platform: Mac OS X 10.9.5
Comment 4 Antti Koivisto 2015-10-12 12:59:24 PDT
Created attachment 262913 [details]
patch
Comment 5 Ryosuke Niwa 2015-10-12 13:05:23 PDT
Comment on attachment 262913 [details]
patch

View in context: https://bugs.webkit.org/attachment.cgi?id=262913&action=review

> Source/WebCore/dom/ComposedTreeIterator.cpp:36
> +    auto* node = m_current;
> +    while (node != &m_root) {

Walking up the tree each time seems unnecessary / inefficient
since we may never get out of the current shadow DOM.

It's probably better to figure out the counting shadow root instead
since node->treeScope->root() will just get you that in O(1).

> Source/WebCore/dom/ComposedTreeIterator.cpp:79
> +    if (is<HTMLSlotElement>(*m_current) && !m_shadowStack.last().currentSlot) {

I would put this into a small helper function like findCurrentSlotPosition or something.

> Source/WebCore/dom/ComposedTreeIterator.cpp:95
> +            if (++m_shadowStack.last().currentSlotNodeIndex < slot->assignedNodes()->size()) {

I think it's helpful to have a local boolean like
bool nextNodeIsStilInSameSlot = ++m_shadowStack.last().currentSlotNodeIndex < slot->assignedNodes()->size()

> Source/WebCore/dom/ComposedTreeIterator.h:195
> +// FIXME: We should have const versions too.
> +inline ComposedTreeDescendantAdapter composedTreeDescendants(ContainerNode& parent)
> +{
> +    return ComposedTreeDescendantAdapter(parent);
> +}

It looks like this function isn't used anywhere.  Why don't we add it when we need it?
Comment 6 Antti Koivisto 2015-10-12 13:06:32 PDT
Created attachment 262914 [details]
patch
Comment 7 Antti Koivisto 2015-10-12 13:17:15 PDT
> Walking up the tree each time seems unnecessary / inefficient
> since we may never get out of the current shadow DOM.

Stack setup code is there mostly for completeness sake (that is, it allows starting from any node within any root). In normal use the stack build as you traverse.

> It's probably better to figure out the counting shadow root instead
> since node->treeScope->root() will just get you that in O(1).

Not sure what you mean. In general case there is no way to know if there is a trip to shadow tree between a node and its ancestor without walking the parent chain.

> It looks like this function isn't used anywhere.  Why don't we add it when
> we need it?

For future use. I plan to add some tests that dump the composed tree.
Comment 8 Ryosuke Niwa 2015-10-12 15:03:42 PDT
(In reply to comment #7)
> > Walking up the tree each time seems unnecessary / inefficient
> > since we may never get out of the current shadow DOM.
> 
> Stack setup code is there mostly for completeness sake (that is, it allows
> starting from any node within any root). In normal use the stack build as
> you traverse.
> 
> > It's probably better to figure out the counting shadow root instead
> > since node->treeScope->root() will just get you that in O(1).
> 
> Not sure what you mean. In general case there is no way to know if there is
> a trip to shadow tree between a node and its ancestor without walking the
> parent chain.

You do. If you only move into a slot if the slot is the next node, or if the next node is assigned into a slot. Since a node can only be assigned into a slot inside shadow DOM of its parent node, you just need to do:
if (auto parent = node->parentElement()) {
  if (auto shadowRoot = parent->shadowRoot()) {
    slot = shadowRoot->findAssignedSlot(this)
  }
}
to find the slot into which we're moving into. This is O(1). Once you found the slot, you can figure out whether we're moving in ("this" is the first assigned node), still in the middle of the slot, or we're moving out of the slot ("this" is the last assigned node).

If "this" is a slot element, we just need to recursively find the first assigned node as long as the current assigned node is also a slot.

For moving out of a slot, you find the assigned slot in O(1) as shown above, and check whether you're the last one in the assigned nodes list or not.  If you're the last assigned node, then just move to the next node from the slot. If the slot from which you're moving out is assigned to another slot, then you into that slot's next assigned node. If we're the last slot assigned to another slot, then we recursively move out of slot as long as the slot we just moved out is the last assigned node in the containing slot.

Does that make sense?
Comment 9 Antti Koivisto 2015-10-13 00:16:34 PDT
> > Not sure what you mean. In general case there is no way to know if there is
> > a trip to shadow tree between a node and its ancestor without walking the
> > parent chain.
> 
> You do. If you only move into a slot if the slot is the next node, or if the
> next node is assigned into a slot. Since a node can only be assigned into a
> slot inside shadow DOM of its parent node, you just need to do:
> if (auto parent = node->parentElement()) {
>   if (auto shadowRoot = parent->shadowRoot()) {
>     slot = shadowRoot->findAssignedSlot(this)
>   }
> }

Right. And if you have a node and an ancestor you need to walk the parent chain between them to see if this condition happens to know if there are trip to a shadow tree there. That's what I meant.

> For moving out of a slot, you find the assigned slot in O(1) as shown above,
> and check whether you're the last one in the assigned nodes list or not.  If

Yeah. That's what the patch does.

> you're the last assigned node, then just move to the next node from the
> slot. If the slot from which you're moving out is assigned to another slot,
> then you into that slot's next assigned node. If we're the last slot

I'm maintaining the shadow stack to cache the assigned node index within the current slot. This allows moving to the slot's next assigned node in O(1).

A way to sort-of do this stacklessly (though I'm not sure if that is what you are arguing for) would be to walk the real siblings of the current slot assignee and find the next one in the same slot. This is much slower since we are doing hash lookups vs indexing to array. It also has bad worst case if nodes are assigned to mixed slots (like ABCABCABC.

If we are maintaining a stack and want to support arbitrary starting state for the iterator then we need to have function to synthesize the stack without traversing the tree. That's what initializeShadowStack() is about.

Note that it doesn't get called at all if you use shadowTreeDescendants() and is almost never called for shadowTreeChildren() (since there is a fast path that avoids it).

> assigned to another slot, then we recursively move out of slot as long as
> the slot we just moved out is the last assigned node in the containing slot.
> 
> Does that make sense?
Comment 10 Antti Koivisto 2015-10-13 00:18:48 PDT
shadowTreeDescendants -> composedTreeDescendants
shadowTreeChildren -> composedTreeChildren
Comment 11 Ryosuke Niwa 2015-10-13 01:17:06 PDT
(In reply to comment #9)
>
> > For moving out of a slot, you find the assigned slot in O(1) as shown above,
> > and check whether you're the last one in the assigned nodes list or not.  If
> 
> Yeah. That's what the patch does.
> 
> > you're the last assigned node, then just move to the next node from the
> > slot. If the slot from which you're moving out is assigned to another slot,
> > then you into that slot's next assigned node. If we're the last slot
> 
> I'm maintaining the shadow stack to cache the assigned node index within the
> current slot. This allows moving to the slot's next assigned node in O(1).
> 
> A way to sort-of do this stacklessly (though I'm not sure if that is what
> you are arguing for) would be to walk the real siblings of the current slot
> assignee and find the next one in the same slot. This is much slower since
> we are doing hash lookups vs indexing to array. It also has bad worst case
> if nodes are assigned to mixed slots (like ABCABCABC.

Oh I see. Thanks for the clarification.

> If we are maintaining a stack and want to support arbitrary starting state
> for the iterator then we need to have function to synthesize the stack
> without traversing the tree. That's what initializeShadowStack() is about.
> 
> Note that it doesn't get called at all if you use shadowTreeDescendants()
> and is almost never called for shadowTreeChildren() (since there is a fast
> path that avoids it).

Okay. Can we avoid traversing up the shadow ancestors when the current shadow DOM doesn't have any slots? I'm mainly concerned about the performance implication of function invocations on builtin shadow DOMs (for input elements, etc...) without slots since they're a lot more common than shadow DOM with slots.
Comment 12 Ryosuke Niwa 2015-10-13 01:47:40 PDT
Comment on attachment 262914 [details]
patch

View in context: https://bugs.webkit.org/attachment.cgi?id=262914&action=review

> Source/WebCore/dom/ComposedTreeIterator.cpp:35
> +    auto* node = m_current;

Please add a change log note saying this code doesn't run in most cases.

> Source/WebCore/dom/ComposedTreeIterator.cpp:79
> +    if (is<HTMLSlotElement>(*m_current) && !m_shadowStack.last().currentSlot) {

shadowStack.last() appears many times in this function.
Can we store that in a local variable?

> Source/WebCore/dom/ComposedTreeIterator.cpp:83
> +            m_shadowStack.last().currentSlot = &slot;
> +            m_shadowStack.last().currentSlotNodeIndex = 0;

Should we add a helper function to set slot + offset?

> Source/WebCore/dom/ComposedTreeIterator.cpp:95
> +            if (++m_shadowStack.last().currentSlotNodeIndex < slot->assignedNodes()->size()) {

Can we add a descriptive local variable like:
bool nextNodeIsInSameSlot = ++m_shadowStack.last().currentSlotNodeIndex < slot->assignedNodes()->size()
?

> Source/WebCore/dom/ComposedTreeIterator.cpp:121
> +        ASSERT(m_shadowStack.last().host == downcast<ShadowRoot>(*parent).host());

Ditto about storing m_shadowStack.last() in a local variable.

> Source/WebCore/dom/ComposedTreeIterator.cpp:151
> +    ASSERT(m_shadowStack.last().host == m_current->parentNode());
> +    if (!m_shadowStack.last().currentSlot) {

Can we put a blank line after all these assertions?
It's hard to read it.
Also, can we store m_shadowStack.last() in a local variable?

> Source/WebCore/dom/ComposedTreeIterator.cpp:157
> +    if (++m_shadowStack.last().currentSlotNodeIndex < slotNodes->size())

Ditto about defining a descriptive local variable.

> Source/WebCore/dom/ComposedTreeIterator.cpp:168
> +    ASSERT(m_shadowStack.last().host == m_current->parentNode());
> +    if (!m_shadowStack.last().currentSlot) {

Ditto about adding a blank line here.

> Source/WebCore/dom/ComposedTreeIterator.cpp:175
> +    auto* slotNodes = m_shadowStack.last().currentSlot->assignedNodes();
> +    ASSERT(slotNodes->at(m_shadowStack.last().currentSlotNodeIndex) == m_current);
> +    if (m_shadowStack.last().currentSlotNodeIndex > 0)
> +        m_current = slotNodes->at(--m_shadowStack.last().currentSlotNodeIndex);

Same comments about defining a local variable for m_shadowStack.last()
and defining a descriptive local variable like previousNodeIsInSameSlot.

> Source/WebCore/dom/ComposedTreeIterator.h:75
> +        HTMLSlotElement* currentSlot { nullptr };
> +        unsigned currentSlotNodeIndex { 0 };

It seems useful to have a helper method that sets both of these variables.
Comment 13 Antti Koivisto 2015-10-13 05:56:44 PDT
> > Source/WebCore/dom/ComposedTreeIterator.h:75
> > +        HTMLSlotElement* currentSlot { nullptr };
> > +        unsigned currentSlotNodeIndex { 0 };
> 
> It seems useful to have a helper method that sets both of these variables.

Didn't do this as I felt it reduced readability overall. Did the rest.
Comment 14 Antti Koivisto 2015-10-13 06:13:23 PDT
https://trac.webkit.org/r190983
Comment 15 Brent Fulgham 2015-10-13 10:48:59 PDT
This introduced more Windows output changes. Can you please fix the Windows test expectations?
Comment 16 Antti Koivisto 2015-10-13 15:45:36 PDT
There was an actual bug with enabling DETAILS_ELEMENT without enabling SHADOW_DOM. This was fixed in https://trac.webkit.org/r190995 and fixed most of the failing details tests on windows. There are still a few rebases left.
Comment 17 Chris Dumez 2016-06-13 13:09:18 PDT
Seems to have regressed PLT on Mac by 1.2%.