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

Source/core/events/EventPath.cpp

 /*
  * Copyright (C) 2013 Google Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions are
  * met:
  *
  *     * Redistributions of source code must retain the above copyright
  * notice, this list of conditions and the following disclaimer.
  *     * Neither the name of Google Inc. nor the names of its
@@ skipping 112 matching lines @@
 }
 
 void EventPath::resetWith(Node* node)
 {
     ASSERT(node);
     m_node = node;
     m_nodeEventContexts.clear();
     m_treeScopeEventContexts.clear();
     calculatePath();
     calculateAdjustedTargets();
-    calculateAdjustedEventPath();
+    if (RuntimeEnabledFeatures::shadowDOMEnabled() && !node->isSVGElement())
+        calculateTreeScopePrePostOrderNumbers();
 }
 
 void EventPath::addNodeEventContext(Node* node)
 {
     m_nodeEventContexts.append(NodeEventContext(node, eventTargetRespectingTargetRules(node)));
 }
 
 void EventPath::calculatePath()
 {
     ASSERT(m_node);
@@ skipping 27 matching lines @@
             current = current->shadowHost();
             addNodeEventContext(current);
         } else {
             current = current->parentNode();
             if (current)
                 addNodeEventContext(current);
         }
     }
 }
 
-void EventPath::calculateAdjustedEventPath()
+void EventPath::calculateTreeScopePrePostOrderNumbers()
 {
-    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);
     }
+    ASSERT(rootTree);
+    rootTree->calculatePrePostOrderNumber(0);
 }
 
 TreeScopeEventContext* EventPath::ensureTreeScopeEventContext(Node* currentTarget, TreeScope* treeScope, TreeScopeEventContextMap& treeScopeEventContextMap)
 {
     if (!treeScope)
         return 0;
     TreeScopeEventContextMap::AddResult addResult = treeScopeEventContextMap.add(treeScope, TreeScopeEventContext::create(*treeScope));
     TreeScopeEventContext* treeScopeEventContext = addResult.storedValue->value.get();
     if (addResult.isNewEntry) {
         TreeScopeEventContext* parentTreeScopeEventContext = ensureTreeScopeEventContext(0, treeScope->olderShadowRootOrParentTreeScope(), treeScopeEventContextMap);
@@ skipping 158 matching lines @@
 
 #ifndef NDEBUG
 void EventPath::checkReachability(TreeScope& treeScope, TouchList& touchList)
 {
     for (size_t i = 0; i < touchList.length(); ++i)
         ASSERT(touchList.item(i)->target()->toNode()->treeScope().isInclusiveOlderSiblingShadowRootOrAncestorTreeScopeOf(treeScope));
 }
 #endif
 
 } // namespace