Source/WebCore:
authorrniwa@webkit.org <rniwa@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 18 Sep 2015 00:47:09 +0000 (00:47 +0000)
committerrniwa@webkit.org <rniwa@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 18 Sep 2015 00:47:09 +0000 (00:47 +0000)
commit0f6f7b10295b73674ab15c955e02c0591787d289
treef6c1eb79a98d93f2e1e76ab0103e6726d764eca9
parentc3df164107904f9e7056786fc477fd2cefed824e
Source/WebCore:
Add HTMLSlotElement, Element.slot, and NonDocumentTypeChildNode.assignedSlot
https://bugs.webkit.org/show_bug.cgi?id=149241

Reviewed by Antti Koivisto.

Implement the slotting algorithm and related features: slot element, slot attribute, and assignedSlot
as specified by https://w3c.github.io/webcomponents/spec/shadow/#slotting-algorithm
as of 8bf56e8ea5521a7a911efd1cabeb2be0d5c3ca74.

The slotting algorithm is implemented by the newly introduced SlotAssignment class which is created on
demand by ShadowRoot when a HTMLSlotElement is inserted into the shadow root. SlotAssignment contains
a HashMap of a slot name to SlotInfo structure, which holds the number of slot elements of the said name,
the first element if it's known, and an ordered list of the assigned nodes.

When there is exactly one slot element of a given name, "element" returns the slot element in O(1).
When another slot of the same name is inserted into the same shadow tree, we increment "elementCount" and
set "element" to nullptr since we don't know which slot element comes first in the tree order without O(n)
tree traversal, which is lazily done in resolveAllSlotElements.

Observe that SlotInfo's "element" can be nullptr in two occasions: (1) when there is no slot element of
the given name (SlotAssignment::assignSlots may insert such an entry), and (2) when there are more than
one slot elements of the same name and we haven't run resolveAllSlotElements.

Resolving assigned nodes, on the other hand, is always O(n) unless all assignments are up to date, and
lazily computed by assignSlots. This is because inserting or removing a node doesn't tell us the relative
ordering of the node with respect to other nodes assigned to the same slot. For example, let's say we have
child nodes (A, B, C, D) and (A, D) are assigned to slot Alpha and (B, C) are assigned to slot Beta. If we
insert a new node E between nodes B and C and this node is assigned to slot Alpha, then we must create an
ordered list (A, E, D) for slot Alpha. Unfortunately, determining where to insert E in this list can cost
O(n) child traversal in the worst case.

Tests: fast/shadow-dom/HTMLSlotElement-interface.html
       fast/shadow-dom/NonDocumentTypeChildNode-interface-assignedSlot.html

* CMakeLists.txt:
* DerivedSources.cpp:
* DerivedSources.make:
* WebCore.vcxproj/WebCore.vcxproj:
* WebCore.vcxproj/WebCore.vcxproj.filters:
* WebCore.xcodeproj/project.pbxproj:
* dom/Element.cpp:
(WebCore::Element::attributeChanged): Invalidate the slot assignments when slot attribute is changed.
(WebCore::Element::childrenChanged): Ditto for when a child node is inserted or removed. We can avoid it
when there is no default slot and only text nodes are removed or added in the future.
* dom/Element.idl: Added slot attribute on Element.
* dom/Node.cpp:
(WebCore::Node::assignedSlot): Added. Returns the assigned slot if the slot is in an open shadow tree.
* dom/Node.h:
* dom/NonDocumentTypeChildNode.idl: Added assignedSlot. Only expose in JS for now to avoid generating
the binding code for HTMLSlotElement in other languages.
* dom/ShadowRoot.cpp:
(WebCore::ShadowRoot::findAssignedSlot): Added. Forwards it to the implementation in SlotAssignment.
(WebCore::ShadowRoot::addSlotElementByName): Ditto.
(WebCore::ShadowRoot::removeSlotElementByName): Ditto.
(WebCore::ShadowRoot::invalidateSlotAssignments): Ditto.
(WebCore::ShadowRoot::assignedNodesForSlot): Ditto.
* dom/ShadowRoot.h:
(WebCore::ShadowRoot): Added m_slotAssignments as a member.
* dom/SlotAssignment.cpp: Added.
(WebCore::treatNullAsEmpty): Added. See https://w3c.github.io/webcomponents/spec/shadow/#dfn-default-slot
(WebCore::SlotAssignment::findAssignedSlot): Find the slot element to which a given node is assigned.
Since there could be multiple slot elements of the same name (or lack thereof), call findFirstSlotElement
to find the first slot element.
(WebCore::SlotAssignment::addSlotElementByName): Added. Called when a new slot element is inserted into
the associated shadow tree. When a slot element's name is changed, removeSlotElementByName is called on
with the old name before addSlotElementByName is called with the new name.
(WebCore::SlotAssignment::removeSlotElementByName): Ditto for removal.
(WebCore::SlotAssignment::assignedNodesForSlot): Added. Finds the ordered list of assigned nodes for
a given slot element. When there are multiple slot elements of the same name, we return the list only if
SlotInfo::element matches the argument.
(WebCore::SlotAssignment::findFirstSlotElement): Added. Resolves SlotInfo::element if needed.
(WebCore::SlotAssignment::resolveAllSlotElements): Finds SlotInfo::element for all slots. We resolve all
slots simultaneously to avoid doing O(number of nodes) tree traversal for O(number of slots) to avoid
the worst case O(n^2) behavior when all nodes in the shadow tree are slot elements of the same name.
(WebCore::SlotAssignment::assignSlots): Added. Computes the slot assignments by traversing each child
of the shadow host and adding to the appropriate SlotInfo::assignedNodes, creating a new entry if needed.
* dom/SlotAssignment.h: Added.
(WebCore::SlotAssignment::SlotAssignment):
(WebCore::SlotAssignment::invalidate):
(WebCore::SlotAssignment::SlotInfo::SlotInfo):
(WebCore::SlotAssignment::SlotInfo::hasSlotElements):
(WebCore::SlotAssignment::SlotInfo::hasDuplicatedSlotElements):
(WebCore::SlotAssignment::SlotInfo::shouldResolveSlotElement):
* html/HTMLAttributeNames.in: Added slot attribute.
* html/HTMLSlotElement.cpp: Added.
(WebCore::HTMLSlotElement::create):
(WebCore::HTMLSlotElement::HTMLSlotElement):
(WebCore::HTMLSlotElement::insertedInto): Calls addSlotElementByName.
(WebCore::HTMLSlotElement::removedFrom): Calls removeSlotElementByName. Because the element had already
been removed from the shadow tree, we can't use containingShadowRoot() to find the ShadowRoot here.
(WebCore::HTMLSlotElement::attributeChanged): Calls removeSlotElementByName and addSlotElementByName.
(WebCore::HTMLSlotElement::getDistributedNodes): Returns an ordered list of the assigned nodes.
* html/HTMLSlotElement.h: Added.
* html/HTMLSlotElement.idl: Added.
* html/HTMLTagNames.in: Added slot element.

LayoutTests:
Add HTMLSlotElement and NonDocumentTypeChildNode.assignedSlot
https://bugs.webkit.org/show_bug.cgi?id=149241

Reviewed by Antti Koivisto.

Added new conformance tests and rebaselined tests as needed.

In particular, inspector/model/remote-object.html was rebaselined since "assignedSlot" now appears as one of the first five
properties on Comment node that this test outputs.

* fast/shadow-dom/HTMLSlotElement-interface-expected.txt: Added.
* fast/shadow-dom/HTMLSlotElement-interface.html: Added.
* fast/shadow-dom/NonDocumentTypeChildNode-interface-assignedSlot-expected.txt: Added.
* fast/shadow-dom/NonDocumentTypeChildNode-interface-assignedSlot.html: Added.
* js/dom/dom-static-property-for-in-iteration-expected.txt:
* platform/mac-mavericks/js/dom/global-constructors-attributes-expected.txt:
* platform/mac-yosemite/js/dom/global-constructors-attributes-expected.txt:
* platform/mac/inspector/model: Added.
* platform/mac/inspector/model/remote-object-expected.txt: Copied from LayoutTests/inspector/model/remote-object-expected.txt.
* platform/mac/js/dom/global-constructors-attributes-expected.txt:

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@189950 268f45cc-cd09-0410-ab3c-d52691b4dbfc
31 files changed:
LayoutTests/ChangeLog
LayoutTests/fast/shadow-dom/HTMLSlotElement-interface-expected.txt [new file with mode: 0644]
LayoutTests/fast/shadow-dom/HTMLSlotElement-interface.html [new file with mode: 0644]
LayoutTests/fast/shadow-dom/NonDocumentTypeChildNode-interface-assignedSlot-expected.txt [new file with mode: 0644]
LayoutTests/fast/shadow-dom/NonDocumentTypeChildNode-interface-assignedSlot.html [new file with mode: 0644]
LayoutTests/js/dom/dom-static-property-for-in-iteration-expected.txt
LayoutTests/platform/mac-mavericks/js/dom/global-constructors-attributes-expected.txt
LayoutTests/platform/mac-yosemite/js/dom/global-constructors-attributes-expected.txt
LayoutTests/platform/mac/inspector/model/remote-object-expected.txt [new file with mode: 0644]
LayoutTests/platform/mac/js/dom/global-constructors-attributes-expected.txt
Source/WebCore/CMakeLists.txt
Source/WebCore/ChangeLog
Source/WebCore/DerivedSources.cpp
Source/WebCore/DerivedSources.make
Source/WebCore/WebCore.vcxproj/WebCore.vcxproj
Source/WebCore/WebCore.vcxproj/WebCore.vcxproj.filters
Source/WebCore/WebCore.xcodeproj/project.pbxproj
Source/WebCore/dom/Element.cpp
Source/WebCore/dom/Element.idl
Source/WebCore/dom/Node.cpp
Source/WebCore/dom/Node.h
Source/WebCore/dom/NonDocumentTypeChildNode.idl
Source/WebCore/dom/ShadowRoot.cpp
Source/WebCore/dom/ShadowRoot.h
Source/WebCore/dom/SlotAssignment.cpp [new file with mode: 0644]
Source/WebCore/dom/SlotAssignment.h [new file with mode: 0644]
Source/WebCore/html/HTMLAttributeNames.in
Source/WebCore/html/HTMLSlotElement.cpp [new file with mode: 0644]
Source/WebCore/html/HTMLSlotElement.h [new file with mode: 0644]
Source/WebCore/html/HTMLSlotElement.idl [new file with mode: 0644]
Source/WebCore/html/HTMLTagNames.in