Add fast path for querySelector(All)

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 19 matching lines @@
 #include "core/css/CSSSelectorList.h"
 #include "core/css/SelectorChecker.h"
 #include "core/css/SelectorCheckerFastPath.h"
 #include "core/css/SiblingTraversalStrategies.h"
 #include "core/dom/Document.h"
 #include "core/dom/NodeTraversal.h"
 #include "core/dom/StaticNodeList.h"
 
 namespace WebCore {
 
+class SimpleNodeList {
+public:
+    virtual bool isEmpty() const = 0;
+    virtual Node* next() = 0;
+};
+
+class SingleNodeList : public SimpleNodeList {
+public:
+    SingleNodeList(Node* rootNode) : m_currentNode(rootNode) { }
+
+    bool isEmpty() const { return !m_currentNode; }
+
+    Node* next()
+    {
+        Node* current = m_currentNode;
+        m_currentNode = 0;
+        return current;
+    }
+
+private:
+    Node* m_currentNode;
+};
+
+class ClassRootNodeList : public SimpleNodeList {
+public:
+    ClassRootNodeList(Node* rootNode, const AtomicString& className)
+        : m_className(className)
+        , m_rootNode(rootNode)
+        , m_currentElement(nextInternal(ElementTraversal::firstWithin(rootNode))) { }
+
+    bool isEmpty() const { return !m_currentElement; }
+
+    Node* next()
+    {
+        Node* current = m_currentElement;
+        ASSERT(current);
+        m_currentElement = nextInternal(ElementTraversal::nextSkippingChildren(m_currentElement, m_rootNode));
+        return current;
+    }
+
+private:
+    Element* nextInternal(Element* element)
+    {
+        for (; element; element = ElementTraversal::next(element, m_rootNode)) {
+            if (element->hasClass() && element->classNames().contains(m_className))
+                return element;
+        }
+        return 0;
+    }
+
+    const AtomicString& m_className;
+    Node* m_rootNode;
+    Element* m_currentElement;
+};
+
+class ClassElementList : public SimpleNodeList {
+public:
+    ClassElementList(Node* rootNode, const AtomicString& className)
+        : m_className(className)
+        , m_rootNode(rootNode)
+        , m_currentElement(nextInternal(ElementTraversal::firstWithin(rootNode))) { }
+
+    bool isEmpty() const { return !m_currentElement; }
+
+    Node* next()
+    {
+        Node* current = m_currentElement;
+        ASSERT(current);
+        m_currentElement = nextInternal(ElementTraversal::next(m_currentElement, m_rootNode));
+        return current;
+    }
+
+private:
+    Element* nextInternal(Element* element)
+    {
+        for (; element; element = ElementTraversal::next(element, m_rootNode)) {
+            if (element->hasClass() && element->classNames().contains(m_className))
+                return element;
+        }
+        return 0;
+    }
+
+    const AtomicString& m_className;
+    Node* m_rootNode;
+    Element* m_currentElement;
+};
+
 void SelectorDataList::initialize(const CSSSelectorList& selectorList)
 {
     ASSERT(m_selectors.isEmpty());
 
     unsigned selectorCount = 0;
     for (const CSSSelector* selector = selectorList.first(); selector; selector = CSSSelectorList::next(selector))
         selectorCount++;
 
     m_selectors.reserveInitialCapacity(selectorCount);
     for (const CSSSelector* selector = selectorList.first(); selector; selector = CSSSelectorList::next(selector))
@@ skipping 26 matching lines @@
         if (selectorMatches(m_selectors[i], targetElement, targetElement))
             return true;
     }
 
     return false;
 }
 
 PassRefPtr<NodeList> SelectorDataList::queryAll(Node* rootNode) const
 {
     Vector<RefPtr<Node> > result;
-    execute<false>(rootNode, result);
+    executeQueryAll(rootNode, result);
     return StaticNodeList::adopt(result);
 }
 
 PassRefPtr<Element> SelectorDataList::queryFirst(Node* rootNode) const
 {
-    Vector<RefPtr<Node> > result;
-    execute<true>(rootNode, result);
-    if (result.isEmpty())
-        return 0;
-    ASSERT(result.size() == 1);
-    ASSERT(result.first()->isElementNode());
-    return toElement(result.first().get());
+    return executeQueryFirst(rootNode);
 }
 
 static inline bool isTreeScopeRoot(Node* node)
 {
     ASSERT(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.
-//
-// If the first value is false, the returned Node is the rootNode parameter or a descendant of rootNode representing
+void SelectorDataList::collectElementsByClassName(Node* rootNode, const AtomicString& className, Vector<RefPtr<Node> >& traversalRoots) const
+{
+    for (Element* element = ElementTraversal::firstWithin(rootNode); element; element = ElementTraversal::next(element, rootNode)) {
+        if (element->hasClass() && element->classNames().contains(className))
+            traversalRoots.append(element);
+    }
+}
+
+void SelectorDataList::collectElementsByTagName(Node* rootNode, const QualifiedName& tagName, Vector<RefPtr<Node> >& traversalRoots) const
+{
+    for (Element* element = ElementTraversal::firstWithin(rootNode); element; element = ElementTraversal::next(element, rootNode)) {
+        if (SelectorChecker::tagMatches(element, tagName))
+            traversalRoots.append(element);
+    }
+}
+
+Element* SelectorDataList::findElementByClassName(Node* rootNode, const AtomicString& className) const
+{
+    for (Element* element = ElementTraversal::firstWithin(rootNode); element; element = ElementTraversal::next(element, rootNode)) {
+        if (element->hasClass() && element->classNames().contains(className))
+            return element;
+    }
+    return 0;
+}
+
+Element* SelectorDataList::findElementByTagName(Node* rootNode, const QualifiedName& tagName) const
+{
+    for (Element* element = ElementTraversal::firstWithin(rootNode); element; element = ElementTraversal::next(element, rootNode)) {
+        if (SelectorChecker::tagMatches(element, tagName))
+            return element;
+    }
+    return 0;
+}
+
+inline bool SelectorDataList::canUseFastQuery(Node* rootNode) const
+{
+    return m_selectors.size() == 1 && rootNode->inDocument() && !rootNode->document()->inQuirksMode();
+}
+
+// If returns true, traversalRoots has the elements that may match the selector query.
+//
+// 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
+PassOwnPtr<SimpleNodeList> SelectorDataList::findTraverseRoots(Node* rootNode, bool& matchTraverseRoots) 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);
+    ASSERT(rootNode);
+    ASSERT(m_selectors.size() == 1);
+    ASSERT(m_selectors[0].selector);
+
+    bool isRightmostSelector = 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 || isRightmostSelector)
+                rootNode = 0;
+            if (isRightmostSelector) {
+                matchTraverseRoots = true;
+                return adoptPtr(new SingleNodeList(rootNode));
+            }
+            if (startFromParent && rootNode)
+                rootNode = rootNode->parentNode();
+
+            matchTraverseRoots = false;
+            return adoptPtr(new SingleNodeList(rootNode));
+        }
+
+        // If we have both CSSSelector::Id and CSSSelector::Class at the same time, we should use Id
+        // to find traverse root.
+        if (!startFromParent && selector->m_match == CSSSelector::Class) {
+            if (isRightmostSelector) {
+                matchTraverseRoots = true;
+                return adoptPtr(new ClassElementList(rootNode, selector->value()));
+            }
+            matchTraverseRoots = false;
+            return adoptPtr(new ClassRootNodeList(rootNode, selector->value()));
+        }
+
+        if (selector->relation() == CSSSelector::SubSelector)
+            continue;
+        isRightmostSelector = false;
+        if (selector->relation() == CSSSelector::DirectAdjacent || selector->relation() == CSSSelector::IndirectAdjacent)
+            startFromParent = true;
+        else
+            startFromParent = false;
+    }
+
+    matchTraverseRoots = false;
+    return adoptPtr(new SingleNodeList(rootNode));
+}
+
+void SelectorDataList::executeSlowQueryAll(Node* rootNode, Vector<RefPtr<Node> >& matchedElements) const
+{
+    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;
+            }
+        }
+    }
+}
+
+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;
+
+    if (!firstSelector->tagHistory()) {
+        // Fast path for querySelectorAll('#id'), 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;
+    }
+
+    while (!traverseRoots->isEmpty()) {
+        Node* traverseRoot = traverseRoots->next();
+        for (Element* element = ElementTraversal::firstWithin(traverseRoot); element; element = ElementTraversal::next(element, traverseRoot)) {
+            if (selectorMatches(selector, element, rootNode))
+                matchedElements.append(element);
+        }
+    }
+}
+
+// If matchTraverseRoot is true, the returned Node is the single Element that may match the selector query.
+//
+// If matchTraverseRoot is false, the returned Node is the rootNode parameter or a descendant of rootNode representing
+// the subtree for which we can limit the querySelector traversal.
+//
+// The returned Node may be 0, regardless of matchTraverseRoot, if this method finds that the selectors won't
+// match any element.
+Node* SelectorDataList::findTraverseRoot(Node* rootNode, bool& matchTraverseRoot) 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.
+    ASSERT(rootNode);
+    ASSERT(m_selectors.size() == 1);
+    ASSERT(m_selectors[0].selector);
 
     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 (matchSingleNode) {
+                matchTraverseRoot = true;
+                return rootNode;
+            }
             if (startFromParent && rootNode)
                 rootNode = rootNode->parentNode();
-            return std::make_pair(false, rootNode);
+            matchTraverseRoot = false;
+            return 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
-{
-    std::pair<bool, Node*> traverseRoot = findTraverseRoot(rootNode);
-    if (!traverseRoot.second)
-        return;
-    Node* traverseRootNode = traverseRoot.second;
-    if (traverseRoot.first) {
+    matchTraverseRoot = false;
+    return rootNode;
+}
+
+Element* SelectorDataList::executeSlowQueryFirst(Node* rootNode) const
+{
+    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))
+                return element;
+        }
+    }
+    return 0;
+}
+
+Element* SelectorDataList::executeQueryFirst(Node* rootNode) const
+{
+    if (!canUseFastQuery(rootNode))
+        return executeSlowQueryFirst(rootNode);
+
+
+    const CSSSelector* selector = m_selectors[0].selector;
+    ASSERT(selector);
+
+    if (!selector->tagHistory()) {
+        // Fast path for querySelector('#id'), 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;
+            }
+        case CSSSelector::Class:
+            return findElementByClassName(rootNode, selector->value());
+        case CSSSelector::Tag:
+            return findElementByTagName(rootNode, selector->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;
+    }
+
+    for (Element* element = ElementTraversal::firstWithin(traverseRootNode); element; element = ElementTraversal::next(element, traverseRootNode)) {
         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;
-            }
-        }
-        return;
-    }
-    for (Element* element = ElementTraversal::firstWithin(rootNode); element; element = ElementTraversal::next(element, rootNode)) {
-        for (unsigned i = 0; i < selectorCount; ++i) {
-            if (selectorMatches(m_selectors[i], element, rootNode)) {
-                matchedElements.append(element);
-                if (firstMatchOnly)
-                    return;
-                break;
-            }
-        }
-    }
+            return element;
+    }
+    return 0;
 }
 
 SelectorQuery::SelectorQuery(const CSSSelectorList& selectorList)
     : m_selectorList(selectorList)
 {
     m_selectors.initialize(m_selectorList);
 }
 
 bool SelectorQuery::matches(Element* element) const
 {
@@ skipping 40 matching lines @@
     m_entries.add(selectors, selectorQuery.release());
     return rawSelectorQuery;
 }
 
 void SelectorQueryCache::invalidate()
 {
     m_entries.clear();
 }
 
 }