Rewrite Shadow DOM distribution engine to support partial synchronous distribution for v1

third_party/WebKit/Source/core/dom/shadow/SlotAssignment.cpp

Index: third_party/WebKit/Source/core/dom/shadow/SlotAssignment.cpp
diff --git a/third_party/WebKit/Source/core/dom/shadow/SlotAssignment.cpp b/third_party/WebKit/Source/core/dom/shadow/SlotAssignment.cpp
index a13e9fb731cedae1bc806c0054377f6922f66da2..9c906804626b93e85e67a8852e2a4a585f6364cd 100644
--- a/third_party/WebKit/Source/core/dom/shadow/SlotAssignment.cpp
+++ b/third_party/WebKit/Source/core/dom/shadow/SlotAssignment.cpp
@@ -14,88 +14,165 @@
 
 namespace blink {
 
-HTMLSlotElement* SlotAssignment::assignedSlotFor(const Node& node) const
+void SlotEntry::add(HTMLSlotElement& slot)
 {
-    return m_assignment.get(const_cast<Node*>(&node));
+    // Relevant DOM Standard:
+    // https://dom.spec.whatwg.org/#concept-node-insert
+    // 6.4:  Run assign slotables for a tree with node's tree and a set containing each inclusive descendant of node that is a slot.
+    if (m_slots.isEmpty()) {
+        m_slots.add(&slot);
+        return;
+    }
+    HTMLSlotElement& first= *firstSlot();
+    DCHECK_NE(first, slot);
+    m_slots.add(&slot);
+    if (firstSlot() == &first)
+        return;
+    // |first| is no longer an active slot.
+    if (first.findHostChildWithSameSlotName())

[kochi, 2016/05/24 10:02:56]

Can this be simply "if (findHostChildBySlotName(first.name())"?
(ditto for line 47)

+        first.enqueueSlotChangeEvent();
+    // TODO(hayato): We should not eneueue a slotchange event for |first|
+    // if |first| was inserted together with |slot|.
+    // This could happen if |first| and |slot| are descendants of the inserted node, and
+    // |first| is preceding |slot|.

[kochi, 2016/05/23 06:08:42]

Maybe you can add a test case for this case, and now marking it failing, and add
TODO
in the test to fix this?

[hayato, 2016/05/24 13:23:38]

Yes, we should have a test. Let me add a test later.

There might be other false-positive cases. Thus, let me investigate further as
another task. I do not want to make this CL larger than the current one.

 }
 
-static void detachNotAssignedNode(Node& node)
+void SlotEntry::remove(HTMLSlotElement& slot)
 {
-    if (node.layoutObject())
-        node.lazyReattachIfAttached();
+    DCHECK(m_slots.contains(&slot));
+    m_slots.remove(&slot);
+    HTMLSlotElement* first = firstSlot();
+    if (first && first != &slot) {

[kochi, 2016/05/23 06:08:42]

Instead of |first != &slot|, you should check |oldFirst == slot|?

If there are 3 slots, if removed slot was second or third, no slotchange event
will occur, but if removed slot was oldFirst, then send slotchange event
to the second?

At this point, first can't be |slot| anyway because it is already removed
from |m_slots| on line 43.

[esprehn, 2016/05/23 06:41:00]

No need for the &, you can compare references and ptrs to nodes

[hayato, 2016/05/24 13:23:38]

Done

+        // |first| slot becomes an active slot.
+        if (first->findHostChildWithSameSlotName())
+            first->enqueueSlotChangeEvent();
+        // TODO(hayato): Prevent a false-positve slotchange.
+        // This could happen if more than one slots which have the same name are descendants of the removed node.
+    }
 }
 
-void SlotAssignment::resolveAssignment(ShadowRoot& shadowRoot)
+DEFINE_TRACE(SlotEntry)
 {
-    m_assignment.clear();
+    visitor->trace(m_slots);
+}
 
-    using Name2Slot = HeapHashMap<AtomicString, Member<HTMLSlotElement>>;
-    Name2Slot name2slot;
+HTMLSlotElement* SlotEntry::firstSlot() const
+{
+    return size() ? toHTMLSlotElement(*m_slots.begin()) : nullptr;

[esprehn, 2016/05/23 06:41:00]

You want .first()

[hayato, 2016/05/24 13:23:39]

Done

+}
 
-    const HeapVector<Member<HTMLSlotElement>>& slots = shadowRoot.descendantSlots();
+SlotEntry& SlotAssignment::entry(const AtomicString& name)
+{
+    auto addResult = m_slotEntryMap.add(name, nullptr);
+    if (addResult.isNewEntry)
+        addResult.storedValue->value = SlotEntry::create();
+    return *addResult.storedValue->value;
+}
 
-    for (Member<HTMLSlotElement> slot : slots) {
-        slot->willUpdateAssignment();
-        slot->willUpdateFallback();
-        name2slot.add(slot->name(), slot.get());
-    }
+void SlotAssignment::slotAdded(HTMLSlotElement& slot)
+{
+    ++m_slotCount;
+    entry(slot.name()).add(slot);

[esprehn, 2016/05/23 06:41:00]

findEntryByName ?

[hayato, 2016/05/24 13:23:39]

Done. Because this method creates and return a new entry if not found, I renamed
it |entryByName| rather than |findEntryByName|.

+    m_needsCollectSlots = true;
+}
 
-    for (Node& child : NodeTraversal::childrenOf(*shadowRoot.host())) {
-        if (child.isInsertionPoint()) {
-            // A re-distribution across v0 and v1 shadow trees is not supported.
-            detachNotAssignedNode(child);
+void SlotAssignment::slotRemoved(HTMLSlotElement& slot)
+{
+    DCHECK_GT(m_slotCount, 0u);
+    --m_slotCount;
+    entry(slot.name()).remove(slot);
+    m_needsCollectSlots = true;
+}
+
+bool SlotAssignment::findHostChildBySlotName(const AtomicString& slotName) const
+{
+    // TODO(hayato): Avoid traversing children every time.

[kochi, 2016/05/23 06:08:42]

Can we shortcut the traverse if any slot with |slotName| has already assigned
nodes?

[hayato, 2016/05/24 13:23:38]

No. Slot's assigned nodes are not updated at this timing.

[kochi, 2016/05/25 05:37:11]

Acknowledged.

+    for (Node& child : NodeTraversal::childrenOf(*m_owner->host())) {
+        if (!child.isSlotable())
             continue;
-        }
-        if (!child.slottable()) {
+        if (child.slotName() == slotName)
+            return true;
+    }
+    return false;
+}
+
+void SlotAssignment::slotRenamed(const AtomicString& oldSlotName, HTMLSlotElement& slot)
+{
+    // |slot| has already new name. Thus, we can not use slot.hasAssignedNodesSynchronously.
+    bool hasAssignedNodesBefore = (findSlotByName(oldSlotName) == &slot) && findHostChildBySlotName(oldSlotName);
+
+    entry(oldSlotName).remove(slot);

[kochi, 2016/05/23 06:08:42]

Shall we remove the entry from |m_slotEntryMap| when the entry becomes empty?

(if script makes random slot name and change it many times, SlotAssignment
gets a lot of garbage entries.)

[hayato, 2016/05/24 13:23:39]

We can. However, it is very rare. I am afraid that we might not justify the cost
of checking emptiness.

[kochi, 2016/05/25 05:37:11]

Even it's rare, do we (kind of) leak empty slot entries?
I don't think it's such heavy cost...

[kochi, 2016/05/25 06:40:26]

Ah, it is no longer necessary because now we use
DocumentOrderedMap and SlotEntry is no longer used.

+    entry(slot.name()).add(slot);
+
+    bool hasAssignedNodesAfter = slot.hasAssignedNodesSynchronously();
+
+    if (hasAssignedNodesBefore || hasAssignedNodesAfter)
+        slot.enqueueSlotChangeEvent();
+}
+
+void SlotAssignment::hostChildSlotNameChanged(const AtomicString& oldValue, const AtomicString& newValue)
+{
+    if (HTMLSlotElement* slot = findSlotByName(HTMLSlotElement::normalizeSlotName(oldValue))) {
+        slot->enqueueSlotChangeEvent();
+        m_owner->owner()->setNeedsDistributionRecalc();
+    }
+    if (HTMLSlotElement* slot = findSlotByName(HTMLSlotElement::normalizeSlotName(newValue))) {
+        slot->enqueueSlotChangeEvent();
+        m_owner->owner()->setNeedsDistributionRecalc();
+    }
+}
+
+SlotAssignment::SlotAssignment(ShadowRoot& owner)
+    : m_owner(&owner)
+{
+}
+
+static void detachNotAssignedNode(Node& node)
+{
+    if (node.layoutObject())
+        node.lazyReattachIfAttached();
+}
+
+void SlotAssignment::resolveAssignment()
+{
+    for (Member<HTMLSlotElement> slot : slots())
+        slot->clearDistribution();
+
+    for (Node& child : NodeTraversal::childrenOf(*m_owner->host())) {
+        if (!child.isSlotable()) {
             detachNotAssignedNode(child);
             continue;
         }
-        AtomicString slotName = child.slotName();
-        HTMLSlotElement* slot = name2slot.get(slotName);
+        HTMLSlotElement* slot = findSlotByName(child.slotName());
         if (slot)
-            assign(child, *slot);
+            assignTo(child, *slot);
         else
             detachNotAssignedNode(child);
     }
-
-    for (auto slot = slots.rbegin(); slot != slots.rend(); ++slot)
-        (*slot)->updateFallbackNodes();
-
-    // For each slot, check if assigned nodes have changed
-    // If so, call fireSlotchange function
-    for (const auto& slot : slots)
-        slot->didUpdateAssignment();
 }
 
-void SlotAssignment::resolveDistribution(ShadowRoot& shadowRoot)
+void SlotAssignment::resolveDistribution()
 {
-    const HeapVector<Member<HTMLSlotElement>>& slots = shadowRoot.descendantSlots();
-    for (Member<HTMLSlotElement> slot : slots) {
-        slot->willUpdateDistribution();
-    }
-
+    resolveAssignment();
+    const HeapVector<Member<HTMLSlotElement>>& slots = this->slots();
     for (auto slot : slots) {
         for (auto node : slot->assignedNodes())
-            distribute(*node, *slot);
+            distributeTo(*node, *slot);
     }
-
     // Update each slot's distribution in reverse tree order so that a child slot is visited before its parent slot.
     for (auto slot = slots.rbegin(); slot != slots.rend(); ++slot)
         (*slot)->updateDistributedNodesWithFallback();
-    for (const auto& slot : slots)
-        slot->didUpdateDistribution();
 }
 
-void SlotAssignment::assign(Node& hostChild, HTMLSlotElement& slot)
+void SlotAssignment::assignTo(Node& hostChild, HTMLSlotElement& slot)
 {
-    DCHECK(hostChild.isSlotAssignable());
-    m_assignment.add(&hostChild, &slot);
+    DCHECK(hostChild.isSlotable());
     slot.appendAssignedNode(hostChild);
 }
 
-void SlotAssignment::distribute(Node& hostChild, HTMLSlotElement& slot)
+void SlotAssignment::distributeTo(Node& hostChild, HTMLSlotElement& slot)
 {
-    DCHECK(hostChild.isSlotAssignable());
+    DCHECK(hostChild.isSlotable());
     if (isHTMLSlotElement(hostChild))
         slot.appendDistributedNodesFrom(toHTMLSlotElement(hostChild));
     else
@@ -105,10 +182,41 @@ void SlotAssignment::distribute(Node& hostChild, HTMLSlotElement& slot)
         slot.parentElementShadow()->setNeedsDistributionRecalc();
 }
 
+const HeapVector<Member<HTMLSlotElement>>& SlotAssignment::slots()
+{
+    if (m_needsCollectSlots)
+        collectSlots();
+    return m_slots;
+}
+
+HTMLSlotElement* SlotAssignment::findSlot(const Node& node)
+{
+    return node.isSlotable() ? findSlotByName(node.slotName()) : nullptr;
+}
+
+HTMLSlotElement* SlotAssignment::findSlotByName(const AtomicString& slotName)
+{
+    return entry(slotName).firstSlot();

[esprehn, 2016/05/23 06:41:00]

Hmm, we should just reuse the same map machinery we use for ids. As long as you
don't have conflicting names it's fast and there's no traversing. You want to
add getElementBySlotName to DocumentOrderedMap and use the add() version that
takes a string.

[hayato, 2016/05/24 13:23:39]

Ops. Thank you for letting me notice that. It looks I have almost re-invented
DocumentOrderedMap, with a different strategy for conflicting. :(

Done.
Since DocumentOrderedMap does now allow an access to its internal MayEntry, I
have to look up a map more than onc at several places, e.g.
SlotAssignment::slotAdded(). Let me optimize this with a fast access later.

+}
+
+void SlotAssignment::collectSlots()
+{
+    DCHECK(m_needsCollectSlots);
+    m_slots.clear();
+
+    m_slots.reserveCapacity(m_slotCount);
+    for (HTMLSlotElement& slot : Traversal<HTMLSlotElement>::descendantsOf(*m_owner)) {

[esprehn, 2016/05/23 06:41:00]

we can just use HTMLSlotElement::insertedInto and a check for duplicate slot
names that causes the slow traversal. We should just use the same collection
machinery we use for ids.

[hayato, 2016/05/24 13:23:38]

Yeah, but we need an ordered list of *all* slots, regardless of their name, in a
tree order, which is necessary to calculate fallback contents correctly.

e.g.
  <slot name=s1>
    <slot name=s2></slot>
  </slot>  

See SlotAssignment::resolveDistribution, where "for (auto slot = slots.rbegin();
slot != slots.rend(); ++slot)" is used.

+        m_slots.append(&slot);
+    }
+    m_needsCollectSlots = false;
+    DCHECK_EQ(m_slots.size(), m_slotCount);
+}
+
 DEFINE_TRACE(SlotAssignment)
 {
-    visitor->trace(m_descendantSlots);
-    visitor->trace(m_assignment);
+    visitor->trace(m_slots);
+    visitor->trace(m_slotEntryMap);
+    visitor->trace(m_owner);
 }
 
 } // namespace blink