Add fast path for querySelector(All)

Source/core/dom/SelectorQuery.cpp

Index: Source/core/dom/SelectorQuery.cpp
diff --git a/Source/core/dom/SelectorQuery.cpp b/Source/core/dom/SelectorQuery.cpp
index 32ed0f30b0b86c7608837975df3f1f731ab591d6..be97d8f6b52014082cb66f02d769b37113a30cac 100644
--- a/Source/core/dom/SelectorQuery.cpp
+++ b/Source/core/dom/SelectorQuery.cpp
@@ -104,74 +104,142 @@ static inline bool isTreeScopeRoot(Node* node)
     return node->isDocumentNode() || node->isShadowRoot();
 }
 
-// If the first pair value is true, the returned Node is the single Element that may match the selector query.
+static bool hasNodeContains(DocumentOrderedList& rootNodes, Node* node)
+{
+    for (DocumentOrderedList::iterator it = rootNodes.begin(); it != rootNodes.end(); ++it) {
+        Node* rootNode = *it;
+        if (rootNode->contains(node))
+            return true;
+    }
+    return false;
+}
+
+static void addWithRemoveNodesContainedBy(DocumentOrderedList& rootNodes, Node* rootNode)
+{
+    rootNodes.add(rootNode);
+
+    // Remove nodes contained by a given rootNode, because rootNode is not given in document order.
+    DocumentOrderedList::iterator it = rootNodes.end();
+    do {
+        --it;
+        if (rootNode == *it)
+            break;
+        if (rootNode->contains(*it))
+            rootNodes.remove(*it);
+    } while (it != rootNodes.begin());
+}
+
+// If returns true, traversalRoots has the elements that may match the selector query.
 //
-// If the first value is false, the returned Node is the rootNode parameter or a descendant of rootNode representing
+// If returns false, traversalRoots has the rootNode parameter or descendants of rootNode representing
 // the subtree for which we can limit the querySelector traversal.
 //
-// The returned Node may be 0, regardless of the returned bool value, if this method finds that the selectors won't
+// The travseralRoots may be empty, regardless of the returned bool value, if this method finds that the selectors won't
 // match any element.
-std::pair<bool, Node*> SelectorDataList::findTraverseRoot(Node* rootNode) const
+bool SelectorDataList::findTraverseRoot(Node* rootNode, DocumentOrderedList& traversalRoots) const
 {
     // We need to return the matches in document order. To use id lookup while there is possiblity of multiple matches
     // we would need to sort the results. For now, just traverse the document in that case.
-    if (m_selectors.size() != 1)
-        return std::make_pair(false, rootNode);
-    if (!rootNode->inDocument())
-        return std::make_pair(false, rootNode);
-    if (rootNode->document()->inQuirksMode())
-        return std::make_pair(false, rootNode);
-
-    bool matchSingleNode = true;
+    if (m_selectors.size() != 1 || !rootNode->inDocument() || rootNode->document()->inQuirksMode()) {
+        traversalRoots.parserAdd(rootNode);
+        return false;
+    }
+
+    bool matchTraverseRoots = true;
     bool startFromParent = false;
     for (const CSSSelector* selector = m_selectors[0].selector; selector; selector = selector->tagHistory()) {
         if (selector->m_match == CSSSelector::Id && !rootNode->document()->containsMultipleElementsWithId(selector->value())) {
             Element* element = rootNode->treeScope()->getElementById(selector->value());
             if (element && (isTreeScopeRoot(rootNode) || element->isDescendantOf(rootNode)))
                 rootNode = element;
-            else if (!element || matchSingleNode)
+            else if (!element || matchTraverseRoots)
                 rootNode = 0;
-            if (matchSingleNode)
-                return std::make_pair(true, rootNode);
+            if (matchTraverseRoots) {
+                if (rootNode)
+                    traversalRoots.parserAdd(rootNode);
+                return true;
+            }
             if (startFromParent && rootNode)
                 rootNode = rootNode->parentNode();
-            return std::make_pair(false, rootNode);
+            if (rootNode)
+                traversalRoots.parserAdd(rootNode);
+            return false;
+        }
+        if (selector->m_match == CSSSelector::Class) {
+            RefPtr<NodeList> nodeList = rootNode->getElementsByClassName(selector->value());

[haraken, 2013/07/08 11:33:47]

oh, this will create unexpected NodeList cache in NodeRareData and increase
memory. See this discussion for more details:
https://bugs.webkit.org/show_bug.cgi?id=88322

+            if (startFromParent) {
+                // Looking at parent nodes, we need to sort in document order.
+                for (unsigned i = 0; i < nodeList->length(); ++i)  {
+                    Node* node = nodeList->item(i);
+                    if (!node || (!isTreeScopeRoot(rootNode) && !node->isDescendantOf(rootNode)))
+                        continue;
+                    if (Node* parent = node->parentNode()) {
+                        if (!hasNodeContains(traversalRoots, parent))
+                            addWithRemoveNodesContainedBy(traversalRoots, parent);
+                    }
+                }
+            } else if (matchTraverseRoots) {
+                for (unsigned i = 0; i < nodeList->length(); ++i) {
+                    Node* node = nodeList->item(i);
+                    if (node && (isTreeScopeRoot(rootNode) || node->isDescendantOf(rootNode)))
+                        traversalRoots.parserAdd(node);
+                }
+                return true;
+            } else {
+                for (unsigned i = 0; i < nodeList->length(); ++i) {
+                    Node* node = nodeList->item(i);
+                    if (!node || (!isTreeScopeRoot(rootNode) && !node->isDescendantOf(rootNode)))
+                        continue;
+                    // Need to check whether the new node is contained by other nodes.
+                    if (!hasNodeContains(traversalRoots, node))
+                        traversalRoots.add(node);
+                }
+            }
+            return false;
         }
+
         if (selector->relation() == CSSSelector::SubSelector)
             continue;
-        matchSingleNode = false;
+        matchTraverseRoots = false;
         if (selector->relation() == CSSSelector::DirectAdjacent || selector->relation() == CSSSelector::IndirectAdjacent)
             startFromParent = true;
         else
             startFromParent = false;
     }
-    return std::make_pair(false, rootNode);
+    if (rootNode)
+        traversalRoots.parserAdd(rootNode);
+    return false;
 }
 
 template <bool firstMatchOnly>
 void SelectorDataList::execute(Node* rootNode, Vector<RefPtr<Node> >& matchedElements) const
 {
-    std::pair<bool, Node*> traverseRoot = findTraverseRoot(rootNode);
-    if (!traverseRoot.second)
+    DocumentOrderedList traverseRoots;
+    bool matchTraverseRoots = findTraverseRoot(rootNode, traverseRoots);
+
+    if (traverseRoots.isEmpty())
         return;
-    Node* traverseRootNode = traverseRoot.second;
-    if (traverseRoot.first) {
+    if (matchTraverseRoots) {
         ASSERT(m_selectors.size() == 1);
-        ASSERT(traverseRootNode->isElementNode());
-        Element* element = toElement(traverseRootNode);
-        if (selectorMatches(m_selectors[0], element, rootNode))
-            matchedElements.append(element);
+        for (DocumentOrderedList::iterator it = traverseRoots.begin(); it != traverseRoots.end(); ++it) {
+            Element* element = toElement(*it);
+            if (selectorMatches(m_selectors[0], element, rootNode))
+                matchedElements.append(element);
+        }
         return;
     }
 
     unsigned selectorCount = m_selectors.size();
     if (selectorCount == 1) {
         const SelectorData& selector = m_selectors[0];
-        for (Element* element = ElementTraversal::firstWithin(rootNode); element; element = ElementTraversal::next(element, rootNode)) {
-            if (selectorMatches(selector, element, rootNode)) {
-                matchedElements.append(element);
-                if (firstMatchOnly)
-                    return;
+        for (DocumentOrderedList::iterator it = traverseRoots.begin(); it != traverseRoots.end(); ++it) {
+            Node* traverseRoot = *it;
+            for (Element* element = ElementTraversal::firstWithin(traverseRoot); element; element = ElementTraversal::next(element, traverseRoot)) {
+                if (selectorMatches(selector, element, rootNode)) {
+                    matchedElements.append(element);
+                    if (firstMatchOnly)
+                        return;
+                }
             }
         }
         return;