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 65 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();
 }
 
+template<bool firstMatchOnly>
+void SelectorDataList::collectElementsByClassName(Node* rootNode, const SpaceSplitString& classNames, Vector<Node*>& traversalRoots) const
+{
+    for (Element* element = ElementTraversal::firstWithin(rootNode); element; element = ElementTraversal::next(element, rootNode)) {
+        if (element->hasClass() && element->classNames().containsAll(classNames)) {
+            traversalRoots.append(element);
+            if (firstMatchOnly)

[esprehn, 2013/07/12 07:17:17]

I'd rather you just created two methods.

Element* findElementByClassName(...);
void findElementsByClassName(..., Vector&);

[tasak, 2013/07/16 07:46:59]

I see.
Done.

+                return;
+        }
+    }
+}
+
+inline bool SelectorDataList::canUseFastQuery(Node* rootNode) const
+{
+    return m_selectors.size() == 1 && rootNode->inDocument() && !rootNode->document()->inQuirksMode();

[esprehn, 2013/07/12 07:17:17]

Why does the root need to be inDocument?

[tasak, 2013/07/16 07:46:59]

To use treeScope()->getElementById.

I guess, we have smaller nodes if rootNode is not in document.
So we could probably use slow path...

+}
+
+// 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 travseralRoots may be empty, regardless of the returned bool value, if this method finds that the selectors won't

[esprehn, 2013/07/12 07:17:17]

It seems like you're trying to do too much inside this one method.

[tasak, 2013/07/16 07:46:59]

I see. I moved the codes for finding elements with a given class name to
ClassElementList and ClassRootNodeList.
 

+// match any element.
+bool SelectorDataList::findTraverseRoots(Node* rootNode, Vector<Node*>& 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 (!canUseFastQuery(rootNode)) {
+        traversalRoots.append(rootNode);
+        return false;
+    }
+
+    bool matchTraverseRoots = true;
+    bool startFromParent = false;
+
+    for (const CSSSelector* selector = m_selectors[0].selector; selector; selector = selector->tagHistory()) {

[esprehn, 2013/07/12 07:17:17]

Do you need an ASSERT at the start of this method? [0] seems like out of bound
access :)

[tasak, 2013/07/16 07:46:59]

I see.
Done.

+        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 || matchTraverseRoots)
+                rootNode = 0;
+            if (matchTraverseRoots) {
+                if (rootNode)
+                    traversalRoots.append(rootNode);
+                return true;
+            }

[esprehn, 2013/07/12 07:17:17]

This loop is confusing, what is it doing?

[tasak, 2013/07/16 07:46:59]

This loop is:
- looking at each selector from right to left, e.g. if we have ".foo > div", we
will check firstly "> div". Next, we will check ".foo".

- if the rightmost selector (except subselectors) is "#id" or ".class",
matchTraverseRoots is true. This means, we can only see elements with the id or
with the class name.

- if we have "#id" or ".class" selector, but the selector is not rightmost one
(e.g. #id > div or .class > div), we don't need to check elements with the id or
with the class name. We need all descendants of the elements. matchTraverseRoots
is false.

- If we find "~" or "+", e.g. #id + div, we don't need to see all descendants of
#id element. Instead, we have to see all descendants of #id element's siblings.
In this case, startFromParent is true.

+            if (startFromParent && rootNode)
+                rootNode = rootNode->parentNode();
+            if (rootNode)
+                traversalRoots.append(rootNode);
+            return false;
+        }
+
+        // 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) {
+            SpaceSplitString classNames(selector->value(), rootNode->document()->inQuirksMode());
+            if (matchTraverseRoots) {
+                collectElementsByClassName<false>(rootNode, classNames, traversalRoots);
+            } else {
+                for (Element* element = ElementTraversal::firstWithin(rootNode); element; ) {
+                    if (element->hasClass() && element->classNames().containsAll(classNames)) {
+                        traversalRoots.append(element);
+                        element = ElementTraversal::nextSkippingChildren(element, rootNode);

[esprehn, 2013/07/12 07:17:17]

Why doesn't this need to be recursive? If this element is ".foo" and there's
another ".foo" inside it don't we need to find it?

[tasak, 2013/07/16 07:46:59]

Because this is for finding traversal roots (e.g. ".foo > div" is given.
Elements with ".foo" are traversal roots in executeQueryAll.
In executeQueryAll, we will use ElementTraversal::firstWithin and
ElementTraversal::next by using the element as root node.

So another ".foo" will be found.

+                    } else {
+                        element = ElementTraversal::next(element, rootNode);
+                    }
+                }
+            }
+            return matchTraverseRoots;
+        }
+
+        if (selector->relation() == CSSSelector::SubSelector)
+            continue;
+        matchTraverseRoots = false;
+        if (selector->relation() == CSSSelector::DirectAdjacent || selector->relation() == CSSSelector::IndirectAdjacent)
+            startFromParent = true;
+        else
+            startFromParent = false;
+    }
+    if (rootNode)
+        traversalRoots.append(rootNode);
+    return false;
+}
+
+void SelectorDataList::executeQueryAll(Node* rootNode, Vector<RefPtr<Node> >& matchedElements) const
+{
+    Vector<Node*> traverseRoots;
+    bool matchTraverseRoots = findTraverseRoots(rootNode, traverseRoots);
+
+    if (traverseRoots.isEmpty())
+        return;
+    if (matchTraverseRoots) {

[esprehn, 2013/07/12 07:17:17]

This is weird, even if matchTraverseRoots is false you still use traverseRoots
below. I think you need to break up findTraverseRoots in to several steps, the
algorithm inside is complicated and appears to be doing a lot of steps at the
same time.

[tasak, 2013/07/16 07:46:59]

The matchTraverseRoots means whether elements found by "findTraverseRoots" can
be results of querySelectorAll or not.

So if matchTraverseRoots is true, we can only check elements in traverseRoots.
Otherwise, we will see all descendants of elements in traverseRoots and check if
each descendant matches a given selector.

+        ASSERT(m_selectors.size() == 1);
+        for (unsigned i = 0; i < traverseRoots.size(); ++i) {
+            Element* element = toElement(traverseRoots.at(i));
+            if (selectorMatches(m_selectors[0], element, rootNode))
+                matchedElements.append(element);
+        }
+        return;
+    }
+
+    unsigned selectorCount = m_selectors.size();

[esprehn, 2013/07/12 07:17:17]

No need to cache this in a local

[tasak, 2013/07/16 07:46:59]

Done.

+    if (selectorCount == 1) {
+        const SelectorData& selector = m_selectors[0];
+        for (unsigned i = 0; i < traverseRoots.size(); ++i) {
+            Node* traverseRoot = traverseRoots.at(i);
+            for (Element* element = ElementTraversal::firstWithin(traverseRoot); element; element = ElementTraversal::next(element, traverseRoot)) {
+                if (selectorMatches(selector, element, rootNode))
+                    matchedElements.append(element);
+            }
+        }
+        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);
+                break;
+            }
+        }
+    }
+}
+
 // 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
 // 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
 // match any element.
 std::pair<bool, Node*> SelectorDataList::findTraverseRoot(Node* rootNode) 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;
     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
+Element* SelectorDataList::executeQueryFirst(Node* rootNode) const
 {
-    std::pair<bool, Node*> traverseRoot = findTraverseRoot(rootNode);
-    if (!traverseRoot.second)
-        return;
-    Node* traverseRootNode = traverseRoot.second;
-    if (traverseRoot.first) {
-        ASSERT(m_selectors.size() == 1);
-        ASSERT(traverseRootNode->isElementNode());
-        Element* element = toElement(traverseRootNode);
-        if (selectorMatches(m_selectors[0], element, rootNode))
-            matchedElements.append(element);
-        return;
+    // fast path
+    if (canUseFastQuery(rootNode)) {
+        if (m_selectors[0].selector && !m_selectors[0].selector->tagHistory()) {
+            const CSSSelector* selector = m_selectors[0].selector;
+            if (selector->m_match == CSSSelector::Id && !rootNode->document()->containsMultipleElementsWithId(selector->value())) {
+                // just getElementById
+                Element* element = rootNode->treeScope()->getElementById(selector->value());
+                return element && (isTreeScopeRoot(rootNode) || element->isDescendantOf(rootNode)) ? element : 0;

[esprehn, 2013/07/12 07:17:17]

Remove the isTreeScopeRoot checks, isDescendantOf already knows how to handle
that with a fast path.

[tasak, 2013/07/16 07:46:59]

We need this check, because this doesn't use findTraverseRoot.
This is a fast path for querySelector('#id') or querySelector('.class').

The reason why I added the code is that I found performance regression of
PerformanceTests/Parser/query-selector-first.

Now findTraverseRoot code is a fast path for querySelector('div > #id') or
querySelector('#id > div') or ...

+            }
+            if (selector->m_match == CSSSelector::Class) {
+                Vector<Node*> nodes;
+                SpaceSplitString classNames(selector->value(), rootNode->document()->inQuirksMode());
+                collectElementsByClassName<true>(rootNode, classNames, nodes);
+                return nodes.size() > 0 ? toElement(nodes.at(0)) : 0;

[esprehn, 2013/07/12 07:17:17]

nodes.isEmpty() ? 0 : nodes.first();

[tasak, 2013/07/16 07:46:59]

I added findElementByClassName and removed this code.

+            }
+        }
+
+        std::pair<bool, Node*> traverseRoot = findTraverseRoot(rootNode);

[esprehn, 2013/07/12 07:17:17]

I think you want to return a Node* and have an out param you pass in. What's
this boolean here?

[tasak, 2013/07/16 07:46:59]

Done.

+        if (!traverseRoot.second)
+            return 0;
+        Node* traverseRootNode = traverseRoot.second;
+        if (traverseRoot.first) {
+            ASSERT(m_selectors.size() == 1);
+            ASSERT(traverseRootNode->isElementNode());
+            Element* element = toElement(traverseRootNode);
+            return selectorMatches(m_selectors[0], element, rootNode) ? element : 0;
+        }
+        rootNode = traverseRootNode;
     }
 
     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;
-            }
+            if (selectorMatches(selector, element, rootNode))
+                return element;
         }
-        return;
+        return 0;
     }
+
     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;
-            }
+            if (selectorMatches(m_selectors[i], element, rootNode))
+                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();
 }
 
 }