Bug 149997 – Implement iterator for traversing composed DOM

• Status: RESOLVED
• Resolution: FIXED
• Component: DOM

[Antti Koivisto]

This is needed for example to get RenderTreePosition right.

[Antti Koivisto]

Created attachment 262910 [details]
patch

[Build Bot]

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

[Build Bot]

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

[Antti Koivisto]

Created attachment 262913 [details]
patch

[Ryosuke Niwa]

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?

[Antti Koivisto]

Created attachment 262914 [details]
patch

[Antti Koivisto]

> 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.

[Ryosuke Niwa]

(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?

[Antti Koivisto]

> > 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?

[Antti Koivisto]

shadowTreeDescendants -> composedTreeDescendants
shadowTreeChildren -> composedTreeChildren

[Ryosuke Niwa]

(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.

[Ryosuke Niwa]

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.

[Antti Koivisto]

> > 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.

[Antti Koivisto]

https://trac.webkit.org/r190983

[Brent Fulgham]

This introduced more Windows output changes. Can you please fix the Windows test expectations?

[Antti Koivisto]

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.

[Chris Dumez]

Seems to have regressed PLT on Mac by 1.2%.