Lazy evaluation of event.path by numbering TreeScopes in DFS order for later O(1) queries

Source/core/events/EventPath.cpp

Index: Source/core/events/EventPath.cpp
diff --git a/Source/core/events/EventPath.cpp b/Source/core/events/EventPath.cpp
index 11c9d97b099f68613b534a3fed924f1e1af4601b..47157c05d21261bc012a2516a2b36cf8bd0fe662 100644
--- a/Source/core/events/EventPath.cpp
+++ b/Source/core/events/EventPath.cpp
@@ -130,7 +130,8 @@ void EventPath::resetWith(Node* node)
     m_treeScopeEventContexts.clear();
     calculatePath();
     calculateAdjustedTargets();
-    calculateAdjustedEventPath();
+    if (RuntimeEnabledFeatures::shadowDOMEnabled() && !node->isSVGElement())
+        numberTreeScopeEventContexts();
 }
 
 void EventPath::addNodeEventContext(Node* node)
@@ -178,25 +179,30 @@ void EventPath::calculatePath()
     }
 }
 
-void EventPath::calculateAdjustedEventPath()
+void EventPath::numberTreeScopeEventContexts()

[dglazkov, 2014/03/10 16:34:53]

calculateTreeScopePositions? These are just suggestions. It seems like there's a
really good term for this "number" thing that's just out of my grasp.

[hayato, 2014/03/11 05:54:04]

To make it more explicit, I'd like to use "preorder number" and "postorder
number".

How about calculateTreeScopePreOrderAndPostOrderNumbers?

 {
-    if (!RuntimeEnabledFeatures::shadowDOMEnabled())
-        return;
+    // Precondition:
+    //   - TreeScopes in m_treeScopeEventContexts must be *connected* in the same tree of trees.
+    //   - The root tree must be included.
+    HashMap<const TreeScope*, TreeScopeEventContext*> treeScopeEventContextMap;
+    for (size_t i = 0; i < m_treeScopeEventContexts.size(); ++i)
+        treeScopeEventContextMap.add(&m_treeScopeEventContexts[i]->treeScope(), m_treeScopeEventContexts[i].get());
+    TreeScopeEventContext* rootTree = 0;
     for (size_t i = 0; i < m_treeScopeEventContexts.size(); ++i) {
         TreeScopeEventContext* treeScopeEventContext = m_treeScopeEventContexts[i].get();
-        Vector<RefPtr<Node> > nodes;
-        nodes.reserveInitialCapacity(size());
-        for (size_t i = 0; i < size(); ++i) {
-            if (at(i).node()->treeScope().isInclusiveOlderSiblingShadowRootOrAncestorTreeScopeOf(treeScopeEventContext->treeScope())) {
-                ASSERT(!at(i).node()->containingShadowRoot()
-                    || at(i).node()->treeScope() == treeScopeEventContext->treeScope()
-                    || toShadowRoot(treeScopeEventContext->treeScope().rootNode()).type() == ShadowRoot::UserAgentShadowRoot
-                    || at(i).node()->containingShadowRoot()->type() != ShadowRoot::UserAgentShadowRoot);
-                nodes.append(at(i).node());
-            }
+        // Use olderShadowRootOrParentTreeScope here for parent-child relationships.
+        // See the definition of trees of trees in the Shado DOM spec: http://w3c.github.io/webcomponents/spec/shadow/
+        TreeScope* parent = treeScopeEventContext->treeScope().olderShadowRootOrParentTreeScope();
+        if (!parent) {
+            ASSERT(!rootTree);
+            rootTree = treeScopeEventContext;
+            continue;
         }
-        treeScopeEventContext->adoptEventPath(nodes);
+        ASSERT(treeScopeEventContextMap.find(parent) != treeScopeEventContextMap.end());
+        treeScopeEventContextMap.find(parent)->value->addChild(*treeScopeEventContext);

[esprehn, 2014/03/11 01:23:11]

Why do you need the hash map? Aren't we traversing them in order?

[hayato, 2014/03/11 05:54:04]

We don't have any assumption about the order of m_treeScopeEventContexts here.

To traverse each treeScope in DFS order, we need:
1. Pointers from parent to its children because TreeScope doesn't have pointers
to its children in a tree of trees.
   We store such children list in TreeScopeEventContext.
   In *for* loop, each TreeScope has to ask the parent to add me to the parent's
children list. We need hashmap here to lookup TreeScopeEventContext by
TreeScope.

     }
+    ASSERT(rootTree);
+    rootTree->numberByDepthFirstSearch(0);
 }
 
 TreeScopeEventContext* EventPath::ensureTreeScopeEventContext(Node* currentTarget, TreeScope* treeScope, TreeScopeEventContextMap& treeScopeEventContextMap)