Add fast path for tag#id selector queries

Source/core/dom/SelectorQuery.cpp

 /*
  * Copyright (C) 2011 Apple 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
@@ skipping 290 matching lines @@
     for (Element* element = ElementTraversal::firstWithin(rootNode); element; element = ElementTraversal::next(*element, &rootNode)) {
         for (unsigned i = 0; i < m_selectors.size(); ++i) {
             if (selectorMatches(m_selectors[i], *element, rootNode)) {
                 matchedElements.append(element);
                 break;
             }
         }
     }
 }
 
+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))
         return executeSlowQueryAll(rootNode, matchedElements);
 
     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:
             return collectElementsByTagName(rootNode, firstSelector->tagQName(), matchedElements);
         default:
             break; // If we need another fast path, add here.
         }
     }
 
     bool matchTraverseRoots;
     OwnPtr<SimpleNodeList> traverseRoots = findTraverseRoots(rootNode, matchTraverseRoots);
     if (traverseRoots->isEmpty())
         return;
 
-    const SelectorData& selector = m_selectors[0];
     if (matchTraverseRoots) {
         while (!traverseRoots->isEmpty()) {
             Node& node = *traverseRoots->next();
             Element& element = toElement(node);
             if (selectorMatches(selector, element, rootNode))
                 matchedElements.append(&element);
         }
         return;
     }
 
@@ skipping 61 matching lines @@
         }
     }
     return 0;
 }
 
 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;
 
-    if (!selector->tagHistory()) {
-        // Fast path for querySelector('#id'), querySelector('.foo'), and querySelector('div').
+    // 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 (!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.
         }
     }
 
     bool matchTraverseRoot;
     Node* traverseRootNode = findTraverseRoot(rootNode, matchTraverseRoot);
     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;
 }
 
 SelectorQuery::SelectorQuery(const CSSSelectorList& selectorList)
     : m_selectorList(selectorList)
 {
     m_selectors.initialize(m_selectorList);
 }
@@ skipping 43 matching lines @@
     m_entries.add(selectors, selectorQuery.release());
     return rawSelectorQuery;
 }
 
 void SelectorQueryCache::invalidate()
 {
     m_entries.clear();
 }
 
 }