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

Source/core/events/TreeScopeEventContext.cpp

 /*
  * 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 10 matching lines @@
  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  *
  */
 
 #include "config.h"
 #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()
 {
     if (!m_touchEventContext)
         m_touchEventContext = TouchEventContext::create();
     return m_touchEventContext.get();
 }
 
 PassRefPtr<TreeScopeEventContext> TreeScopeEventContext::create(TreeScope& treeScope)
 {
     return adoptRef(new TreeScopeEventContext(treeScope));
 }
 
 TreeScopeEventContext::TreeScopeEventContext(TreeScope& treeScope)
     : m_treeScope(treeScope)
+    , m_preVisit(-1)
+    , m_postVisit(-1)
 {
 }
 
 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;
 }
+
+}