Bug 149997

Created attachment 262910 [details] patch

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

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

Created attachment 262913 [details] patch

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?

Created attachment 262914 [details] patch

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

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

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

shadowTreeDescendants -> composedTreeDescendants shadowTreeChildren -> composedTreeChildren

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

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

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

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.

Seems to have regressed PLT on Mac by 1.2%.