Optimized querySelector(All) when selector contains #id.

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 589a0f27c6d275aab90b9610a4abe3db6071bfe8..3c43113df5c09615c96ae09102a822d298ab8b95 100644
--- a/Source/core/dom/SelectorQuery.cpp
+++ b/Source/core/dom/SelectorQuery.cpp
@@ -98,38 +98,62 @@ PassRefPtr<Element> SelectorDataList::queryFirst(Node* rootNode) const
     return toElement(result.first().get());
 }
 
-bool SelectorDataList::canUseIdLookup(Node* rootNode) const
+static inline bool isTreeScopeRoot(Node* node)
+{
+    ASSERT(node);
+    return node->isDocumentNode() || node->isShadowRoot();
+}
+
+std::pair<bool, Node*> SelectorDataList::findTraverseRoot(Node* rootNode) const

[haraken, 2013/05/14 12:50:33]

Let's add a comment about what the return values mean.

 {
     // 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 false;
-    if (m_selectors[0].selector->m_match != CSSSelector::Id)
-        return false;
+        return std::make_pair(false, rootNode);
     if (!rootNode->inDocument())
-        return false;
+        return std::make_pair(false, rootNode);
     if (rootNode->document()->inQuirksMode())
-        return false;
-    if (rootNode->document()->containsMultipleElementsWithId(m_selectors[0].selector->value()))
-        return false;
-    return true;
-}
-
-static inline bool isTreeScopeRoot(Node* node)
-{
-    ASSERT(node);
-    return node->isDocumentNode() || node->isShadowRoot();
+        return std::make_pair(false, rootNode);
+
+    bool matchSingleNode = 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)
+                rootNode = 0;
+            if (matchSingleNode)
+                return std::make_pair(true, rootNode);
+            if (startFromParent && rootNode)
+                rootNode = rootNode->parentNode();
+            return std::make_pair(false, rootNode);
+        }
+        if (selector->relation() == CSSSelector::SubSelector)
+            continue;
+        matchSingleNode = false;
+        if (selector->relation() == CSSSelector::DirectAdjacent || selector->relation() == CSSSelector::IndirectAdjacent)
+            startFromParent = true;
+        else
+            startFromParent = false;
+    }
+    return std::make_pair(false, rootNode);
 }
 
 template <bool firstMatchOnly>
 void SelectorDataList::execute(Node* rootNode, Vector<RefPtr<Node> >& matchedElements) const
 {
-    if (canUseIdLookup(rootNode)) {
+    std::pair<bool, Node*> traverseRoot = findTraverseRoot(rootNode);
+    if (!traverseRoot.second)
+        return;
+    Node* traverseRootNode = traverseRoot.second;
+    if (traverseRoot.first) {
         ASSERT(m_selectors.size() == 1);
-        const CSSSelector* selector = m_selectors[0].selector;
-        Element* element = rootNode->treeScope()->getElementById(selector->value());
-        if (!element || !(isTreeScopeRoot(rootNode) || element->isDescendantOf(rootNode)))
+        ASSERT(traverseRootNode->isElementNode());
+        if (!traverseRootNode->isElementNode())

[haraken, 2013/05/14 12:50:33]

You can remove this if statement, because it shouldn't happen.

             return;
+        Element* element = toElement(traverseRootNode);
         if (selectorMatches(m_selectors[0], element, rootNode))
             matchedElements.append(element);
         return;
@@ -137,7 +161,7 @@ void SelectorDataList::execute(Node* rootNode, Vector<RefPtr<Node> >& matchedEle
 
     unsigned selectorCount = m_selectors.size();
 
-    Node* n = rootNode->firstChild();
+    Node* n = traverseRootNode->firstChild();
     while (n) {
         if (n->isElementNode()) {
             Element* element = toElement(n);
@@ -156,7 +180,7 @@ void SelectorDataList::execute(Node* rootNode, Vector<RefPtr<Node> >& matchedEle
         }
         while (!n->nextSibling()) {
             n = n->parentNode();
-            if (n == rootNode)
+            if (n == traverseRootNode)
                 return;
         }
         n = n->nextSibling();