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

Source/core/events/TreeScopeEventContext.h

Index: Source/core/events/TreeScopeEventContext.h
diff --git a/Source/core/events/TreeScopeEventContext.h b/Source/core/events/TreeScopeEventContext.h
index 639cf816572418858ecdec69291d333253bec6c0..914442505557c9496689011e15be2db0a808927a 100644
--- a/Source/core/events/TreeScopeEventContext.h
+++ b/Source/core/events/TreeScopeEventContext.h
@@ -37,6 +37,7 @@
 
 namespace WebCore {
 
+class EventPath;
 class EventTarget;
 class Node;
 class TouchEventContext;
@@ -58,8 +59,14 @@ public:
     TouchEventContext* touchEventContext() const { return m_touchEventContext.get(); }
     TouchEventContext* ensureTouchEventContext();
 
-    PassRefPtr<NodeList> eventPath() const { return m_eventPath; }
-    void adoptEventPath(Vector<RefPtr<Node> >&);
+    PassRefPtr<NodeList> ensureEventPath(EventPath&);
+
+    bool isInclusiveAncestorOf(const TreeScopeEventContext&);
+    void addChild(TreeScopeEventContext& child) { m_children.append(&child); }
+
+    // Number each TreeScope for ancestor-descendant relationship check in Q(1).
+    // Preprocessing takes O(N).
+    int numberByDepthFirstSearch(int number);

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

"number" is awkward here.

What's the right term for this number? Tree scope position?

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

Let me use more explicit name, pre-order number and post-order number.

 
 private:
     TreeScopeEventContext(TreeScope&);
@@ -73,6 +80,10 @@ private:
     RefPtr<EventTarget> m_relatedTarget;
     RefPtr<NodeList> m_eventPath;
     RefPtrWillBePersistent<TouchEventContext> m_touchEventContext;
+
+    Vector<TreeScopeEventContext*> m_children;
+    int m_preVisit;
+    int m_postVisit;
 };
 
 #ifndef NDEBUG
@@ -97,6 +108,12 @@ inline void TreeScopeEventContext::setRelatedTarget(PassRefPtr<EventTarget> rela
     m_relatedTarget = relatedTarget;
 }
 
+inline bool TreeScopeEventContext::isInclusiveAncestorOf(const TreeScopeEventContext& other)
+{
+    ASSERT(m_preVisit != -1 && m_postVisit != -1 && other.m_preVisit != -1 && other.m_postVisit != -1);
+    return m_preVisit <= other.m_preVisit && other.m_postVisit <= m_postVisit;
+}
+
 }
 
 #endif // TreeScopeEventContext_h