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..0b533b5ded129bf8e4bb77a5151ec98985584452 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_preVisit(-1)
+    , m_postVisit(-1)
 {
 }
 
@@ -58,4 +72,14 @@ TreeScopeEventContext::~TreeScopeEventContext()
 {
 }
 
+int TreeScopeEventContext::numberByDepthFirstSearch(int number)
+{
+    m_preVisit = number;
+    for (size_t i = 0; i < m_children.size(); ++i) {

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

extra braces

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

Done.

+        number = m_children[i]->numberByDepthFirstSearch(number + 1);
+    }
+    m_postVisit = number + 1;

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

Why do you need postVisit? Can't you just do lastChild()->number() + 1 ? I don't
think you need to store that.

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

The reason is that the spec requires pre-calculation for event.path.
The event.path should not be affected by DOM mutations after event dispatching
starts.

+    return number + 1;
+}
+
 }