Add fast path for tag#id selector queries

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 50113c5420ca37fa8a619847b9ccc86adb2773a5..72a3708da24c88f947ba1138d292f35ad4df2697 100644
--- a/Source/core/dom/SelectorQuery.cpp
+++ b/Source/core/dom/SelectorQuery.cpp
@@ -308,6 +308,17 @@ void SelectorDataList::executeSlowQueryAll(Node& rootNode, Vector<RefPtr<Node> >
     }
 }
 
+const CSSSelector* SelectorDataList::selectorForIdLookup(const CSSSelector* firstSelector) const
+{
+    for (const CSSSelector* selector = firstSelector; selector; selector = selector->tagHistory()) {
+        if (selector->m_match == CSSSelector::Id)
+            return selector;
+        if (selector->relation() != CSSSelector::SubSelector)
+            break;
+    }
+    return 0;
+}
+
 void SelectorDataList::executeQueryAll(Node& rootNode, Vector<RefPtr<Node> >& matchedElements) const
 {
     if (!canUseFastQuery(rootNode))
@@ -316,22 +327,35 @@ void SelectorDataList::executeQueryAll(Node& rootNode, Vector<RefPtr<Node> >& ma
     ASSERT(m_selectors.size() == 1);
     ASSERT(m_selectors[0].selector);
 
-    const CSSSelector* firstSelector = m_selectors[0].selector;
+    const SelectorData& selector = m_selectors[0];
+    const CSSSelector* firstSelector = selector.selector;
+
+    // Fast path for querySelectorAll('#id'), querySelectorAll('tag#id').
+    if (const CSSSelector* idSelector = selectorForIdLookup(firstSelector)) {
+        const AtomicString& idToMatch = idSelector->value();
+        if (UNLIKELY(rootNode.treeScope().containsMultipleElementsWithId(idToMatch))) {
+            const Vector<Element*>* elements = rootNode.treeScope().getAllElementsById(idToMatch);
+            ASSERT(elements);
+            size_t count = elements->size();
+            for (size_t i = 0; i < count; ++i) {
+                Element* element = elements->at(i);
+                ASSERT(element);
+                if (selectorMatches(selector, *element, rootNode))
+                    matchedElements.append(element);
+            }
+            return;
+        }
+        Element* element = rootNode.treeScope().getElementById(idToMatch);
+        if (!element || !(isTreeScopeRoot(rootNode) || element->isDescendantOf(&rootNode)))
+            return;
+        if (selectorMatches(selector, *element, rootNode))
+            matchedElements.append(element);
+        return;
+    }
 
     if (!firstSelector->tagHistory()) {
-        // Fast path for querySelectorAll('#id'), querySelectorAl('.foo'), and querySelectorAll('div').
+        // Fast path for querySelectorAl('.foo'), and querySelectorAll('div').
         switch (firstSelector->m_match) {
-        case CSSSelector::Id:
-            {
-                if (rootNode.document().containsMultipleElementsWithId(firstSelector->value()))
-                    break;
-
-                // Just the same as getElementById.
-                Element* element = rootNode.treeScope().getElementById(firstSelector->value());
-                if (element && (isTreeScopeRoot(rootNode) || element->isDescendantOf(&rootNode)))
-                    matchedElements.append(element);
-                return;
-            }
         case CSSSelector::Class:
             return collectElementsByClassName(rootNode, firstSelector->value(), matchedElements);
         case CSSSelector::Tag:
@@ -346,7 +370,6 @@ void SelectorDataList::executeQueryAll(Node& rootNode, Vector<RefPtr<Node> >& ma
     if (traverseRoots->isEmpty())
         return;
 
-    const SelectorData& selector = m_selectors[0];
     if (matchTraverseRoots) {
         while (!traverseRoots->isEmpty()) {
             Node& node = *traverseRoots->next();
@@ -428,25 +451,41 @@ Element* SelectorDataList::executeQueryFirst(Node& rootNode) const
     if (!canUseFastQuery(rootNode))
         return executeSlowQueryFirst(rootNode);
 
+    ASSERT(m_selectors.size() == 1);
+    ASSERT(m_selectors[0].selector);
 
-    const CSSSelector* selector = m_selectors[0].selector;
-    ASSERT(selector);
+    const SelectorData& selector = m_selectors[0];
+    const CSSSelector* firstSelector = selector.selector;
+
+    // Fast path for querySelectorAll('#id'), querySelectorAll('tag#id').
+    if (const CSSSelector* idSelector = selectorForIdLookup(firstSelector)) {
+        const AtomicString& idToMatch = idSelector->value();
+        if (UNLIKELY(rootNode.treeScope().containsMultipleElementsWithId(idToMatch))) {
+            const Vector<Element*>* elements = rootNode.treeScope().getAllElementsById(idToMatch);
+            ASSERT(elements);
+            size_t count = elements->size();
+            for (size_t i = 0; i < count; ++i) {
+                Element* element = elements->at(i);
+                ASSERT(element);
+                if (selectorMatches(selector, *element, rootNode))
+                    return element;
+            }
+            return 0;
+        }
+        Element* element = rootNode.treeScope().getElementById(idToMatch);
+        if (!element || !(isTreeScopeRoot(rootNode) || element->isDescendantOf(&rootNode)))
+            return 0;
+        return selectorMatches(selector, *element, rootNode) ? element : 0;

[esprehn, 2013/12/02 20:38:04]

Woah looks like copy pasta?

[Inactive, 2013/12/02 20:47:26]

Yes, SelectorDataList::executeQueryFirst() and
SelectorDataList::executeQueryAll() are currently mostly (except the former
returns as soon as a match is found and the latter appends matches to a vector)
duplicated because they are really hot.

This was done by this earlier optimization:
https://chromiumcodereview.appspot.com/18732004

I will see what I can do about this.

+    }
 
-    if (!selector->tagHistory()) {
-        // Fast path for querySelector('#id'), querySelector('.foo'), and querySelector('div').
+    if (!firstSelector->tagHistory()) {
+        // Fast path for querySelector('.foo'), and querySelector('div').
         // Many web developers uses querySelector with these simple selectors.
-        switch (selector->m_match) {
-        case CSSSelector::Id:
-            {
-                if (rootNode.document().containsMultipleElementsWithId(selector->value()))
-                    break;
-                Element* element = rootNode.treeScope().getElementById(selector->value());
-                return element && (isTreeScopeRoot(rootNode) || element->isDescendantOf(&rootNode)) ? element : 0;
-            }
+        switch (firstSelector->m_match) {
         case CSSSelector::Class:
-            return findElementByClassName(rootNode, selector->value());
+            return findElementByClassName(rootNode, firstSelector->value());
         case CSSSelector::Tag:
-            return findElementByTagName(rootNode, selector->tagQName());
+            return findElementByTagName(rootNode, firstSelector->tagQName());
         default:
             break; // If we need another fast path, add here.
         }
@@ -457,14 +496,13 @@ Element* SelectorDataList::executeQueryFirst(Node& rootNode) const
     if (!traverseRootNode)
         return 0;
     if (matchTraverseRoot) {
-        ASSERT(m_selectors.size() == 1);
         ASSERT(traverseRootNode->isElementNode());
         Element& element = toElement(*traverseRootNode);
-        return selectorMatches(m_selectors[0], element, rootNode) ? &element : 0;
+        return selectorMatches(selector, element, rootNode) ? &element : 0;
     }
 
     for (Element* element = ElementTraversal::firstWithin(*traverseRootNode); element; element = ElementTraversal::next(*element, traverseRootNode)) {
-        if (selectorMatches(m_selectors[0], *element, rootNode))
+        if (selectorMatches(selector, *element, rootNode))
             return element;
     }
     return 0;