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

third_party/WebKit/Source/core/html/HTMLSlotElement.cpp

Index: third_party/WebKit/Source/core/html/HTMLSlotElement.cpp
diff --git a/third_party/WebKit/Source/core/html/HTMLSlotElement.cpp b/third_party/WebKit/Source/core/html/HTMLSlotElement.cpp
index 331437363377ec23e6146f20400e17cbe95f9bb0..4d08c0132fa96da1cba3b468992c32dec7841267 100644
--- a/third_party/WebKit/Source/core/html/HTMLSlotElement.cpp
+++ b/third_party/WebKit/Source/core/html/HTMLSlotElement.cpp
@@ -38,6 +38,7 @@
 #include "core/dom/StyleEngine.h"
 #include "core/dom/shadow/ElementShadow.h"
 #include "core/dom/shadow/InsertionPoint.h"
+#include "core/dom/shadow/SlotAssignment.h"
 #include "core/events/Event.h"
 #include "core/html/AssignedNodesOptions.h"
 
@@ -47,15 +48,27 @@ using namespace HTMLNames;
 
 inline HTMLSlotElement::HTMLSlotElement(Document& document)
     : HTMLElement(slotTag, document)
-    , m_distributionState(DistributionDone)
-    , m_assignmentState(AssignmentDone)
-    , m_slotchangeEventAdded(false)
 {
     setHasCustomStyleCallbacks();
 }
 
 DEFINE_NODE_FACTORY(HTMLSlotElement);
 
+// static
+AtomicString HTMLSlotElement::normalizeSlotName(const AtomicString& name)
+{
+    return (name.isNull() || name.isEmpty()) ? emptyAtom : name;

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

Why does your code care if the name is null or empty? This method should not be
needed. Just add the .isEmpty() checks to the right spots. In general your code
should avoid caring about null or empty strings

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

|name| here came from the result of Element::fastGetAttribute(), which can be
nullAtom (e.g. for <div></div>)  or emptyAtom (e.g. for <div slot=""></div>)

We have to treat both cases in the same way as per the Shadow DOM spec. I am
assuming that nullAtom != emptyAtom if they are used as a key of HashMap.

Normalizing a result of fastGetAttribute() in one place will eliminate several
manual checks for (isEmpty() || isNull()).

+}
+
+const HeapVector<Member<Node>>& HTMLSlotElement::assignedNodes()
+{
+#if DCHECK_IS_ON
+    DCHECK(!needsDistributionRecalc());
+#endif
+    DCHECK(isInShadowTree() || m_assignedNodes.isEmpty());
+    return m_assignedNodes;
+}
+
 const HeapVector<Member<Node>> HTMLSlotElement::assignedNodesForBinding(const AssignedNodesOptions& options)
 {
     updateDistribution();
@@ -66,7 +79,9 @@ const HeapVector<Member<Node>> HTMLSlotElement::assignedNodesForBinding(const As
 
 const HeapVector<Member<Node>>& HTMLSlotElement::getDistributedNodes()
 {
-    ASSERT(!needsDistributionRecalc());
+#if DCHECK_IS_ON

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

why is this needed now?

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

Done. Removed.

+    DCHECK(!needsDistributionRecalc());
+#endif
     if (isInShadowTree())
         return m_distributedNodes;
 
@@ -75,77 +90,51 @@ const HeapVector<Member<Node>>& HTMLSlotElement::getDistributedNodes()
     // TODO(hayato): If this path causes a performance issue, we should move
     // ShadowRootRaraDate::m_descendantSlots into TreeScopreRareData-ish and
     // update the distribution code so it considers a document tree too.
-    willUpdateDistribution();
+    clearDistribution();
     for (Node& child : NodeTraversal::childrenOf(*this)) {
-        if (!child.isSlotAssignable())
+        if (!child.isSlotable())
             continue;
         if (isHTMLSlotElement(child))
             m_distributedNodes.appendVector(toHTMLSlotElement(child).getDistributedNodes());

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

This code doesn't make sense, if the slot itself is not in a shadow tree then
none of the children of it can be in a shadow tree either. This is then
iterating every child and putting them into the vector in tree order, and then
it's putting every child of every <slot> that's a child of this slot in there
too. Why does the spec want us to put every descendant of the slot element into
a vector? That's very weird.

ex.

<slot>
  <slot>
    <div />
    <slot>
      <span />
    </slot>
  </slot>
  <section />
</slot>

This method walks that entire subtree and returns [div, span, section] but why??

If that's what the spec really wants then all of this recursion isn't needed,
just use descendantsOf() instead.

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

That's an expected behavior. A slot itself can be a fallback content of other
(parent) slot. We have to *flatten* a slot, recursively, even in a case of
fallback contents.

Maybe it might be easier to understand why we need this if each slot has a slot
name, and suppose they are used in a shadow tree

<slot name=s1>
  <slot name=s2>
    <div />
    <slot name=s3>
      <span />
    </slot>
  </slot>
  <section />
</slot>

1. If a host's children are [<div slot=s1>], slot s1's distributed nodes is
[<div slot=s1>] 
2. If a host's children are [<div slot=s2>], slot s1's distributed nodes is
[<div slot=s2>, <section>]
3. If a host's children are [<div slot=s3>], slot s1's distributed nodes is
[<div>, <div slot=s3> <section>, 
4. If a host's children are none, slot s1's distributed nodes is [<div>, <span>,
<section>], as you said. That's an expected behavior.
 
Yes.
We can not. 

e.g.

<slot name=s1>
  <slot name=s2>
    <div>
      <div id=foo>
         <slot name=s3>
           <span />
         </slot>
      </div>
  </slot>
  <section />
</slot>


Is this case, s1' distributed nodes will be [<div>, <section>] (where neither
<div id=foo> nor <span> are included), if the host does not have a child.

I think it is rare that slots are used in a document tree, thus, the support for
slots in a document tree is very limited in the current implementation. That's
one of TODO items.

[esprehn, 2016/05/25 05:45:02]

If you're not in a shadow tree then none of the elements you can reach through
NodeTraversal::childrenOf can be either, which means the recursive step of
toHTMLSlotElement(child).getDistributedNodes() on the child will go to:

if (isInShadowTree())
  return ...;

but it'll be false, so then you'll come down to this loop and start iterating
the kids of that child.

You can instead just use a loop over NodeTraversal::descendantsOf and not have
this be recursive at all.

[hayato, 2016/05/26 04:46:06]

I am afraid that it is not easy with NodeTraversal::descendantsOf. Let me re-use
the example:

<slot name=s1>
  <slot name=s2>
    <div>
      <div id=foo>
         <slot name=s3>
           <span />
         </slot>
      </div>
  </slot>
  <section />
</slot>

For s1.getDistributedNodes():

1. We have to pick up: [<div>, <section>]
2. We should not pick up: [<div id=foo>, <span>].


With NodeTraversal::descendantsOf, we need a `shouldPickup` function, like:

for (Node& node: NodeTraversal::descendantsOf(slot) {
   if (shouldPickup(node) {
      distributedNodes.append(node)
   }
}

I do not see how we can implement `shouldPickup` easily here without be
recursive.

- shoudPickup should return true for <div> and <section>
- shoudPickup should return false for <div id=foo> and <span>

         else
             m_distributedNodes.append(&child);
     }
-    didUpdateDistribution();
     return m_distributedNodes;
 }
 
 void HTMLSlotElement::appendAssignedNode(Node& node)
 {
-    ASSERT(m_assignmentState == AssignmentOnGoing);
     m_assignedNodes.append(&node);
 }
 
 void HTMLSlotElement::appendDistributedNode(Node& node)
 {
-    ASSERT(m_distributionState == DistributionOnGoing);
     size_t size = m_distributedNodes.size();
     m_distributedNodes.append(&node);
     m_distributedIndices.set(&node, size);
 }
 
-void HTMLSlotElement::appendFallbackNode(Node& node)
-{
-    ASSERT(m_assignmentState == AssignmentOnGoing);
-    m_fallbackNodes.append(&node);
-}
-
 void HTMLSlotElement::appendDistributedNodesFrom(const HTMLSlotElement& other)
 {
-    ASSERT(m_distributionState == DistributionOnGoing);
     size_t index = m_distributedNodes.size();
     m_distributedNodes.appendVector(other.m_distributedNodes);
     for (const auto& node : other.m_distributedNodes)
         m_distributedIndices.set(node.get(), index++);
 }
 
-void HTMLSlotElement::willUpdateAssignment()
+void HTMLSlotElement::clearDistribution()
 {
-    ASSERT(m_assignmentState != AssignmentOnGoing);
-    m_assignmentState = AssignmentOnGoing;
-    m_oldAssignedNodes.swap(m_assignedNodes);
     m_assignedNodes.clear();
-}
-
-void HTMLSlotElement::willUpdateDistribution()
-{
-    ASSERT(m_distributionState != DistributionOnGoing);
-    m_distributionState = DistributionOnGoing;
-    m_oldDistributedNodes.swap(m_distributedNodes);
     m_distributedNodes.clear();
     m_distributedIndices.clear();
 }
 
-void HTMLSlotElement::willUpdateFallback()
-{
-    m_oldFallbackNodes.swap(m_fallbackNodes);
-    m_fallbackNodes.clear();
-}
-
 void HTMLSlotElement::dispatchSlotChangeEvent()
 {
     Event* event = Event::create(EventTypeNames::slotchange);
     event->setTarget(this);
     dispatchScopedEvent(event);
-    m_slotchangeEventAdded = false;
+    m_slotchangeEventEnqueued = false;

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

you need to set this to false before you dispatch the event, otherwise a DOM
mutation inside the event listener will fail to cause another slot change event
to happen since it'll think the event is still pending.

 }
 
 Node* HTMLSlotElement::distributedNodeNextTo(const Node& node) const
@@ -197,24 +186,20 @@ void HTMLSlotElement::attributeChanged(const QualifiedName& name, const AtomicSt
 {
     if (name == nameAttr) {
         if (ShadowRoot* root = containingShadowRoot()) {
-            root->owner()->willAffectSelector();
             if (root->isV1() && oldValue != newValue)
-                root->assignV1();
+                root->ensureSlotAssignment().slotRenamed(normalizeSlotName(oldValue), *this);

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

slotRenamed shouldn't care if the string is empty or null

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

That should be cared because a slot with name of "empty or null" can be matched
to a host's child whose slot name is "empty or null".

         }
     }
     HTMLElement::attributeChanged(name, oldValue, newValue, reason);
 }
 
-void HTMLSlotElement::childrenChanged(const ChildrenChange& change)
+static bool wasInShadowTreeBeforeInserted(HTMLSlotElement& slot, ContainerNode& insertionPoint)
 {
-    HTMLElement::childrenChanged(change);
-    if (ShadowRoot* root = containingShadowRoot()) {
-        if (ElementShadow* rootOwner = root->owner()) {
-            rootOwner->setNeedsDistributionRecalc();
-        }
-        if (m_assignedNodes.isEmpty() && root->isV1())
-            root->assignV1();
-    }
+    ShadowRoot* root1 = slot.containingShadowRoot();
+    ShadowRoot* root2 = insertionPoint.containingShadowRoot();
+    if (root1 && root2 && root1 == root2)
+        return false;
+    return root1;

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

The caller of this is only insertedInto() below (as of now), and
this is called within context that slot.containingShadowRoot() exists -
so root1 should be always non-null, and only relevant check here seems

if (root1 == root2)
   return false;

which means "if insertion point is under the same shadow root, return false".
Then it sounds logically inverted from what the function name suggests to me.

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

No. It looks you are focusing on the node tree's *current* status, *after* the
node was inserted.

This is check for the status in the past, *before* the |slot| was inserted.

If root1 == root2, that means |slot| was in a *disconnected* tree. Does it make
sense?

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

Acknowledged.

 }
 
 Node::InsertionNotificationRequest HTMLSlotElement::insertedInto(ContainerNode* insertionPoint)
@@ -222,27 +207,36 @@ Node::InsertionNotificationRequest HTMLSlotElement::insertedInto(ContainerNode*
     HTMLElement::insertedInto(insertionPoint);
     ShadowRoot* root = containingShadowRoot();
     if (root) {
-        if (ElementShadow* rootOwner = root->owner())
-            rootOwner->setNeedsDistributionRecalc();
-        if (root == insertionPoint->treeScope().rootNode())
-            root->didAddSlot();
+        DCHECK(root->owner());
+        root->owner()->setNeedsDistributionRecalc();
+        // 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 (!wasInShadowTreeBeforeInserted(*this, *insertionPoint))
+            root->ensureSlotAssignment().slotAdded(*this);

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

I'm confused at following the logic here - could you explain the intention here?

     }
 
     // We could have been distributed into in a detached subtree, make sure to
     // clear the distribution when inserted again to avoid cycles.
     clearDistribution();
 
-    if (root && root->isV1())
-        root->assignV1();
-
     return InsertionDone;
 }
 
+static ShadowRoot* containingShadowRootBeforeRemoved(Node& removedDescendant, ContainerNode& insertionPoint)
+{
+    if (ShadowRoot* root = removedDescendant.containingShadowRoot())
+        return root;
+    return insertionPoint.containingShadowRoot();
+}
+
 void HTMLSlotElement::removedFrom(ContainerNode* insertionPoint)
 {
-    ShadowRoot* root = containingShadowRoot();
-    if (!root)
-        root = insertionPoint->containingShadowRoot();
+    // `removedFrom` is called after the node is removed from the tree.
+    // That means:
+    // 1. If this slot is still in a tree scope, it means the slot has been in a shadow tree. An inclusive inclusive shadow-including ancestor of the shadow host was originally removed from its parent.

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

nit: s/inclusive inclusive/inclusive/

+    // 2. Or (this slot is now not in a tree scope), this slot's inclusive ancestor was orginally removed from its parent (== insertion point). This slot and the originally removed node was in the same tree.
+
+    ShadowRoot* root = containingShadowRootBeforeRemoved(*this, *insertionPoint);
     if (root) {
         if (ElementShadow* rootOwner = root->owner())
             rootOwner->setNeedsDistributionRecalc();
@@ -251,14 +245,11 @@ void HTMLSlotElement::removedFrom(ContainerNode* insertionPoint)
     // Since this insertion point is no longer visible from the shadow subtree, it need to clean itself up.
     clearDistribution();
 
-    ContainerNode& rootNode = insertionPoint->treeScope().rootNode();
-    if (root == &rootNode)
-        root->didRemoveSlot();
-    else if (rootNode.isShadowRoot() && toShadowRoot(rootNode).isV1())
-        toShadowRoot(rootNode).assignV1();
+    if (root && root->isV1() && root == &insertionPoint->treeScope().rootNode()) {
+        // This slot was in a shadow tree and got disconnected from the shadow root.
+        root->ensureSlotAssignment().slotRemoved(*this);
+    }
 
-    if (root && root->isV1())
-        root->assignV1();
     HTMLElement::removedFrom(insertionPoint);
 }
 
@@ -271,93 +262,56 @@ void HTMLSlotElement::willRecalcStyle(StyleRecalcChange change)
         node->setNeedsStyleRecalc(LocalStyleChange, StyleChangeReasonForTracing::create(StyleChangeReason::PropagateInheritChangeToDistributedNodes));
 }
 
-void HTMLSlotElement::updateFallbackNodes()
-{
-    if (!m_fallbackNodes.isEmpty())
-        return;
-    for (auto& child : NodeTraversal::childrenOf(*this)) {
-        if (!child.isSlotAssignable())
-            continue;
-        // Insertion points are not supported as slots fallback
-        if (isActiveInsertionPoint(child))
-            continue;
-        appendFallbackNode(child);
-    }
-}
-
 void HTMLSlotElement::updateDistributedNodesWithFallback()
 {
     if (!m_distributedNodes.isEmpty())
         return;
-    for (auto node : m_fallbackNodes) {
-        if (isHTMLSlotElement(node))
-            appendDistributedNodesFrom(*toHTMLSlotElement(node));
+    for (auto& child : NodeTraversal::childrenOf(*this)) {
+        if (!child.isSlotable())
+            continue;
+        if (isHTMLSlotElement(child))
+            appendDistributedNodesFrom(toHTMLSlotElement(child));
         else
-            appendDistributedNode(*node);
+            appendDistributedNode(child);
     }
 }
 
-bool HTMLSlotElement::assignmentChanged()
-{
-    ASSERT(m_assignmentState != AssignmentOnGoing);
-    if (m_assignmentState == AssignmentDone)
-        m_assignmentState = m_oldAssignedNodes == m_assignedNodes ? AssignmentUnchanged : AssignmentChanged;
-    return m_assignmentState == AssignmentChanged;
-}
-
-bool HTMLSlotElement::distributionChanged()
+void HTMLSlotElement::enqueueSlotChangeEvent()
 {
-    ASSERT(m_distributionState != DistributionOnGoing);
-    if (m_distributionState == DistributionDone)
-        m_distributionState = m_oldDistributedNodes == m_distributedNodes ? DistributionUnchanged : DistributionChanged;
-    return m_distributionState == DistributionChanged;
-}
-
-bool HTMLSlotElement::fallbackChanged()
-{
-    return m_oldFallbackNodes == m_fallbackNodes;
-}
+    if (!m_slotchangeEventEnqueued) {
+        Microtask::enqueueMicrotask(WTF::bind(&HTMLSlotElement::dispatchSlotChangeEvent, this));

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

Does a Persistent<> get magically created for |this| here?

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

Good point! It looks it does not. 

Let me use Persistent<HTMLSlotElement>(this)) here. Is this okay here?

+        m_slotchangeEventEnqueued = true;
+    }
 
-void HTMLSlotElement::didUpdateAssignment()
-{
-    ASSERT(m_assignmentState == AssignmentOnGoing);
-    m_assignmentState = AssignmentDone;
-    if ((assignmentChanged() || fallbackChanged()) && !m_slotchangeEventAdded)
-        fireSlotChangeEvent();
-}
+    ShadowRoot* root = containingShadowRoot();
+    DCHECK(root);
+    DCHECK(root->isV1());
+    root->owner()->setNeedsDistributionRecalc();
 
-void HTMLSlotElement::didUpdateDistribution()
-{
-    ASSERT(m_distributionState == DistributionOnGoing);
-    m_distributionState = DistributionDone;
-    if (isChildOfV1ShadowHost()) {
-        ElementShadow* shadow = parentElementShadow();
-        ASSERT(shadow);
-        if (!shadow->needsDistributionRecalc() && distributionChanged())
-            shadow->setNeedsDistributionRecalc();
+    if (ShadowRoot* parentShadowRoot = v1ShadowRootOfParent()) {
+        if (HTMLSlotElement* next = parentShadowRoot->ensureSlotAssignment().findSlot(*this))
+            next->enqueueSlotChangeEvent();
     }
 }
 
-void HTMLSlotElement::fireSlotChangeEvent()
+bool HTMLSlotElement::hasAssignedNodesSynchronously() const
 {
-    ASSERT(!m_slotchangeEventAdded);
-    Microtask::enqueueMicrotask(WTF::bind(&HTMLSlotElement::dispatchSlotChangeEvent, this));
-    m_slotchangeEventAdded = true;
-
-    Element* shadowHost = isShadowHost(parentElement()) ? parentElement() : nullptr;
-    // If this slot is assigned to another slot, fire slot change event of that slot too.
-    if (shadowHost && shadowHost->shadowRootIfV1()) {
-        if (HTMLSlotElement* assigned = assignedSlot()) {
-            if (!assigned->m_slotchangeEventAdded)
-                assigned->fireSlotChangeEvent();
-        }
-    }
+    ShadowRoot* root = containingShadowRoot();
+    DCHECK(root);
+    DCHECK(root->isV1());
+    SlotAssignment& assignment = root->ensureSlotAssignment();
+    if (assignment.findSlot(*this) != this)
+        return false;
+    return assignment.findHostChildBySlotName(name());
 }
 
-void HTMLSlotElement::clearDistribution()
+bool HTMLSlotElement::findHostChildWithSameSlotName() const
 {
-    willUpdateDistribution();
-    didUpdateDistribution();
+    ShadowRoot* root = containingShadowRoot();
+    DCHECK(root);
+    DCHECK(root->isV1());
+    SlotAssignment& assignment = root->ensureSlotAssignment();
+    return assignment.findHostChildBySlotName(name());
 }
 
 short HTMLSlotElement::tabIndex() const
@@ -369,11 +323,7 @@ DEFINE_TRACE(HTMLSlotElement)
 {
     visitor->trace(m_assignedNodes);
     visitor->trace(m_distributedNodes);
-    visitor->trace(m_fallbackNodes);
     visitor->trace(m_distributedIndices);
-    visitor->trace(m_oldAssignedNodes);
-    visitor->trace(m_oldDistributedNodes);
-    visitor->trace(m_oldFallbackNodes);
     HTMLElement::trace(visitor);
 }