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

Source/core/events/TreeScopeEventContext.cpp

Index: Source/core/events/TreeScopeEventContext.cpp
diff --git a/Source/core/events/TreeScopeEventContext.cpp b/Source/core/events/TreeScopeEventContext.cpp
index 98df539b1f45d4cbf24dee4ff8e935905a486396..a86922bff22cdaf2952c1bc8780d2b913e8602bf 100644
--- a/Source/core/events/TreeScopeEventContext.cpp
+++ b/Source/core/events/TreeScopeEventContext.cpp
@@ -28,13 +28,25 @@
 #include "core/events/TreeScopeEventContext.h"
 
 #include "core/dom/StaticNodeList.h"
+#include "core/dom/shadow/ShadowRoot.h"
+#include "core/events/EventPath.h"
 #include "core/events/TouchEventContext.h"
 
 namespace WebCore {
 
-void TreeScopeEventContext::adoptEventPath(Vector<RefPtr<Node> >& nodes)
+PassRefPtr<NodeList> TreeScopeEventContext::ensureEventPath(EventPath& path)
 {
+    if (m_eventPath)
+        return m_eventPath;
+
+    Vector<RefPtr<Node> > nodes;
+    nodes.reserveInitialCapacity(path.size());
+    for (size_t i = 0; i < path.size(); ++i) {
+        if (path[i].treeScopeEventContext()->isInclusiveAncestorOf(*this))
+            nodes.append(path[i].node());
+    }
     m_eventPath = StaticNodeList::adopt(nodes);
+    return m_eventPath;
 }
 
 TouchEventContext* TreeScopeEventContext::ensureTouchEventContext()
@@ -51,6 +63,8 @@ PassRefPtr<TreeScopeEventContext> TreeScopeEventContext::create(TreeScope& treeS
 
 TreeScopeEventContext::TreeScopeEventContext(TreeScope& treeScope)
     : m_treeScope(treeScope)
+    , m_preOrder(-1)
+    , m_postOrder(-1)
 {
 }
 
@@ -58,4 +72,13 @@ TreeScopeEventContext::~TreeScopeEventContext()
 {
 }
 
+int TreeScopeEventContext::calculatePrePostOrderNumber(int orderNumber)
+{
+    m_preOrder = orderNumber;
+    for (size_t i = 0; i < m_children.size(); ++i)
+        orderNumber = m_children[i]->calculatePrePostOrderNumber(orderNumber + 1);
+    m_postOrder = orderNumber + 1;
+    return orderNumber + 1;
+}
+
 }