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

Source/core/events/TreeScopeEventContext.h

 /*
  * Copyright (C) 2014 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:
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
  * 2. Redistributions in binary form must reproduce the above copyright
  *    notice, this list of conditions and the following disclaimer in the
@@ skipping 19 matching lines @@
 #include "core/dom/Node.h"
 #include "core/dom/NodeList.h"
 #include "core/dom/TreeScope.h"
 #include "core/events/EventTarget.h"
 #include "wtf/PassRefPtr.h"
 #include "wtf/RefPtr.h"
 #include "wtf/Vector.h"
 
 namespace WebCore {
 
+class EventPath;
 class EventTarget;
 class Node;
 class TouchEventContext;
 class TreeScope;
 
 class TreeScopeEventContext : public RefCounted<TreeScopeEventContext> {
 public:
     static PassRefPtr<TreeScopeEventContext> create(TreeScope&);
     ~TreeScopeEventContext();
 
     TreeScope& treeScope() const { return m_treeScope; }
 
     EventTarget* target() const { return m_target.get(); }
     void setTarget(PassRefPtr<EventTarget>);
 
     EventTarget* relatedTarget() const { return m_relatedTarget.get(); }
     void setRelatedTarget(PassRefPtr<EventTarget>);
 
     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&);
 
 #ifndef NDEBUG
     bool isUnreachableNode(EventTarget&);
 #endif
 
     TreeScope& m_treeScope;
     RefPtr<EventTarget> m_target;
     RefPtr<EventTarget> m_relatedTarget;
     RefPtr<NodeList> m_eventPath;
     RefPtrWillBePersistent<TouchEventContext> m_touchEventContext;
+
+    Vector<TreeScopeEventContext*> m_children;
+    int m_preVisit;
+    int m_postVisit;
 };
 
 #ifndef NDEBUG
 inline bool TreeScopeEventContext::isUnreachableNode(EventTarget& target)
 {
     // FIXME: Checks also for SVG elements.
     return target.toNode() && !target.toNode()->isSVGElement() && !target.toNode()->treeScope().isInclusiveOlderSiblingShadowRootOrAncestorTreeScopeOf(m_treeScope);
 }
 #endif
 
 inline void TreeScopeEventContext::setTarget(PassRefPtr<EventTarget> target)
 {
     ASSERT(target);
     ASSERT(!isUnreachableNode(*target));
     m_target = target;
 }
 
 inline void TreeScopeEventContext::setRelatedTarget(PassRefPtr<EventTarget> relatedTarget)
 {
     ASSERT(relatedTarget);
     ASSERT(!isUnreachableNode(*relatedTarget));
     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