Use Traits in SelectorQuery to avoid a lot of code duplication

Source/core/dom/SelectorQuery.cpp

 /*
- * Copyright (C) 2011 Apple Inc. All rights reserved.
+ * Copyright (C) 2011, 2013 Apple Inc. All rights reserved.
+ * Copyright (C) 2014 Samsung Electronics. 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
  *     notice, this list of conditions and the following disclaimer in the
  *     documentation and/or other materials provided with the distribution.
@@ skipping 18 matching lines @@
 #include "core/css/SelectorChecker.h"
 #include "core/css/SelectorCheckerFastPath.h"
 #include "core/css/SiblingTraversalStrategies.h"
 #include "core/dom/Document.h"
 #include "core/dom/ElementTraversal.h"
 #include "core/dom/Node.h"
 #include "core/dom/StaticNodeList.h"
 
 namespace WebCore {
 
-class SimpleNodeList {
-public:
-    virtual ~SimpleNodeList() { }
-    virtual bool isEmpty() const = 0;
-    virtual Node* next() = 0;
+struct SingleElementSelectorQueryTrait {
+    typedef Element* OutputType;
+    static const bool shouldOnlyMatchFirstElement = true;
+    ALWAYS_INLINE static void appendElement(OutputType& output, Element* element)

[esprehn, 2014/01/23 18:26:34]

reference.

[Inactive, 2014/01/23 21:07:52]

Ok, I will update and reupload.

+    {
+        ASSERT(element);
+        ASSERT(!output);
+        output = element;
+    }
 };
 
-class SingleNodeList FINAL : public SimpleNodeList {
-public:
-    explicit SingleNodeList(Node* rootNode) : m_currentNode(rootNode) { }
-
-    virtual bool isEmpty() const OVERRIDE { return !m_currentNode; }
-
-    virtual Node* next() OVERRIDE
+struct AllElementsSelectorQueryTrait {
+    typedef Vector<RefPtr<Node> > OutputType;
+    static const bool shouldOnlyMatchFirstElement = false;
+    ALWAYS_INLINE static void appendElement(OutputType& output, Node* element)

[esprehn, 2014/01/23 18:26:34]

Same

     {
-        Node* current = m_currentNode;
-        m_currentNode = 0;
-        return current;
+        ASSERT(element);
+        output.append(element);
     }
-
-private:
-    Node* m_currentNode;
 };
 
-class ClassRootNodeList FINAL : public SimpleNodeList {
+class ClassRootNodeList {
 public:
     ClassRootNodeList(Node& rootNode, const AtomicString& className)
         : m_className(className)
         , m_rootNode(rootNode)
         , m_currentElement(nextInternal(ElementTraversal::firstWithin(m_rootNode))) { }
 
-    virtual bool isEmpty() const OVERRIDE { return !m_currentElement; }
+    bool isEmpty() const { return !m_currentElement; }
 
-    virtual Node* next() OVERRIDE
+    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 FINAL : public SimpleNodeList {
+class ClassElementList {

[adamk, 2014/01/23 21:16:13]

This and the above are nearly the same, so I'm tempted to say that there's even
more that could be done here, but I'm happy to leave that thought for later.

[Inactive, 2014/01/23 21:22:10]

I had the same thinking but was planning to do this in a follow-up patch because
this one is already big.

 public:
     ClassElementList(Node& rootNode, const AtomicString& className)
         : m_className(className)
         , m_rootNode(rootNode)
         , m_currentElement(nextInternal(ElementTraversal::firstWithin(rootNode))) { }
 
-    virtual bool isEmpty() const OVERRIDE { return !m_currentElement; }
+    bool isEmpty() const { return !m_currentElement; }
 
-    virtual Node* next() OVERRIDE
+    Node* next()
     {
         Node* current = m_currentElement;
         ASSERT(current);
         m_currentElement = nextInternal(ElementTraversal::next(*m_currentElement, &m_rootNode));
         return current;
     }
 
 private:
     Element* nextInternal(Element* element)
     {
@@ skipping 45 matching lines @@
         if (selectorMatches(m_selectors[i], targetElement, targetElement))
             return true;
     }
 
     return false;
 }
 
 PassRefPtr<NodeList> SelectorDataList::queryAll(Node& rootNode) const
 {
     Vector<RefPtr<Node> > result;
-    executeQueryAll(rootNode, result);
+    execute<AllElementsSelectorQueryTrait>(rootNode, result);
     return StaticNodeList::adopt(result);
 }
 
 PassRefPtr<Element> SelectorDataList::queryFirst(Node& rootNode) const
 {
-    return executeQueryFirst(rootNode);
+    Element* matchedElement = 0;
+    execute<SingleElementSelectorQueryTrait>(rootNode, matchedElement);
+    return matchedElement;
 }
 
-void SelectorDataList::collectElementsByClassName(Node& rootNode, const AtomicString& className, Vector<RefPtr<Node> >& traversalRoots) const
+template <typename SelectorQueryTrait>
+void SelectorDataList::collectElementsByClassName(Node& rootNode, const AtomicString& className,  typename SelectorQueryTrait::OutputType& output) const
 {
     for (Element* element = ElementTraversal::firstWithin(rootNode); element; element = ElementTraversal::next(*element, &rootNode)) {
-        if (element->hasClass() && element->classNames().contains(className))
-            traversalRoots.append(element);
+        if (element->hasClass() && element->classNames().contains(className)) {
+            SelectorQueryTrait::appendElement(output, element);
+            if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
+                return;
+        }
     }
 }
 
-void SelectorDataList::collectElementsByTagName(Node& rootNode, const QualifiedName& tagName, Vector<RefPtr<Node> >& traversalRoots) const
+template <typename SelectorQueryTrait>
+void SelectorDataList::collectElementsByTagName(Node& rootNode, const QualifiedName& tagName,  typename SelectorQueryTrait::OutputType& output) const
 {
     for (Element* element = ElementTraversal::firstWithin(rootNode); element; element = ElementTraversal::next(*element, &rootNode)) {
-        if (SelectorChecker::tagMatches(*element, tagName))
-            traversalRoots.append(element);
+        if (SelectorChecker::tagMatches(*element, tagName)) {
+            SelectorQueryTrait::appendElement(output, element);
+            if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
+                return;
+        }
     }
 }
 
-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(const Node& rootNode) const
 {
     return m_selectors.size() == 1 && rootNode.inDocument() && !rootNode.document().inQuirksMode();
 }
 
 inline bool ancestorHasClassName(Node& rootNode, const AtomicString& className)
 {
     if (!rootNode.isElementNode())
         return false;
 
     for (Element* element = &toElement(rootNode); element; element = element->parentElement()) {
         if (element->hasClass() && element->classNames().contains(className))
             return true;
     }
     return false;
 }
 
 
 // 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
 // match any element.
-PassOwnPtr<SimpleNodeList> SelectorDataList::findTraverseRoots(Node& rootNode, bool& matchTraverseRoots) const
+template <typename SelectorQueryTrait>
+void SelectorDataList::findTraverseRootsAndExecute(Node& rootNode, typename SelectorQueryTrait::OutputType& output) 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(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());
             Node* adjustedNode = &rootNode;
             if (element && (isTreeScopeRoot(rootNode) || element->isDescendantOf(&rootNode)))
                 adjustedNode = element;
             else if (!element || isRightmostSelector)
                 adjustedNode = 0;
-            if (isRightmostSelector) {
-                matchTraverseRoots = true;
-                return adoptPtr(new SingleNodeList(adjustedNode));
-            }
+            if (isRightmostSelector)
+                return executeForTraverseRoot<SelectorQueryTrait>(m_selectors[0], adjustedNode, MatchesTraverseRoots, rootNode, output);

[adamk, 2014/01/23 21:16:13]

returning a void function is a bit odd looking to my eyes, how would you feel
about making this and the other cases in this file into two statements?

[Inactive, 2014/01/23 21:22:10]

I tend to agree. The pattern was already used in this file (e.g. return
collectElementsByClassName(...)) so I followed. I will split in 2 statements, I
think it is clearer.

+
             if (startFromParent && adjustedNode)
                 adjustedNode = adjustedNode->parentNode();
 
-            matchTraverseRoots = false;
-            return adoptPtr(new SingleNodeList(adjustedNode));
+            return executeForTraverseRoot<SelectorQueryTrait>(m_selectors[0], adjustedNode, DoesNotMatchTraverseRoots, rootNode, output);
         }
 
         // 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 (!SelectorQueryTrait::shouldOnlyMatchFirstElement && !startFromParent && selector->m_match == CSSSelector::Class) {
             if (isRightmostSelector) {
-                matchTraverseRoots = true;
-                return adoptPtr(new ClassElementList(rootNode, selector->value()));
+                OwnPtr<ClassElementList> traverseRoots = adoptPtr(new ClassElementList(rootNode, selector->value()));

[adamk, 2014/01/23 21:16:13]

Why is this and the ClassRootNodeList heap-allocated? Seems like it would be
simpler to just stack-allocate them (either in a separate statement like this or
just as a temporary passed to executeForTraverseRoots()...

[Inactive, 2014/01/23 21:22:10]

Historical reasons. This is a good point, I will change this.

+                return executeForTraverseRoots<SelectorQueryTrait>(m_selectors[0], traverseRoots.get(), MatchesTraverseRoots, rootNode, output);
             }
-            matchTraverseRoots = false;
             // Since there exists some ancestor element which has the class name, we need to see all children of rootNode.
             if (ancestorHasClassName(rootNode, selector->value()))
-                return adoptPtr(new SingleNodeList(&rootNode));
+                return executeForTraverseRoot<SelectorQueryTrait>(m_selectors[0], &rootNode, DoesNotMatchTraverseRoots, rootNode, output);
 
-            return adoptPtr(new ClassRootNodeList(rootNode, selector->value()));
+            OwnPtr<ClassRootNodeList> traverseRoots = adoptPtr(new ClassRootNodeList(rootNode, selector->value()));
+            return executeForTraverseRoots<SelectorQueryTrait>(m_selectors[0], traverseRoots.get(), DoesNotMatchTraverseRoots, rootNode, output);
         }
 
         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));
+    executeForTraverseRoot<SelectorQueryTrait>(m_selectors[0], &rootNode, DoesNotMatchTraverseRoots, rootNode, output);
 }
 
-void SelectorDataList::executeSlowQueryAll(Node& rootNode, Vector<RefPtr<Node> >& matchedElements) const
+template <typename SelectorQueryTrait>
+void SelectorDataList::executeForTraverseRoot(const SelectorData& selector, Node* traverseRoot, MatchTraverseRootState matchTraverseRoot, Node& rootNode, typename SelectorQueryTrait::OutputType& output) 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;
-            }
+    if (!traverseRoot)
+        return;
+
+    if (matchTraverseRoot) {
+        if (selectorMatches(selector, toElement(*traverseRoot), rootNode))
+            SelectorQueryTrait::appendElement(output, toElement(traverseRoot));
+        return;
+    }
+
+    for (Element* element = ElementTraversal::firstWithin(*traverseRoot); element; element = ElementTraversal::next(*element, traverseRoot)) {
+        if (selectorMatches(selector, *element, rootNode)) {
+            SelectorQueryTrait::appendElement(output, element);
+            if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
+                return;
         }
     }
 }
 
-const CSSSelector* SelectorDataList::selectorForIdLookup(const CSSSelector* firstSelector) const
+template <typename SelectorQueryTrait, typename SimpleNodeListType>
+void SelectorDataList::executeForTraverseRoots(const SelectorData& selector, SimpleNodeListType* traverseRoots, MatchTraverseRootState matchTraverseRoots, Node& rootNode, typename SelectorQueryTrait::OutputType& output) const

[adamk, 2014/01/23 21:16:13]

...and make the |traverseRoots| argument a SimpleNodeListType&

[Inactive, 2014/01/23 21:22:10]

ok

 {
-    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 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 (rootNode.treeScope().containsMultipleElementsWithId(idToMatch)) {
-            const Vector<Element*>& elements = rootNode.treeScope().getAllElementsById(idToMatch);
-            size_t count = elements.size();
-            for (size_t i = 0; i < count; ++i) {
-                Element* element = elements[i];
-                ASSERT(element);
-                if (!(isTreeScopeRoot(rootNode) || element->isDescendantOf(&rootNode)))
-                    continue;
-                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 querySelectorAl('.foo'), and querySelectorAll('div').
-        switch (firstSelector->m_match) {
-        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;
 
     if (matchTraverseRoots) {
         while (!traverseRoots->isEmpty()) {
             Node& node = *traverseRoots->next();
             Element& element = toElement(node);
-            if (selectorMatches(selector, element, rootNode))
-                matchedElements.append(&element);
+            if (selectorMatches(selector, element, rootNode)) {
+                SelectorQueryTrait::appendElement(output, &element);
+                if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
+                    return;
+            }
         }
         return;
     }
 
     while (!traverseRoots->isEmpty()) {
         Node* traverseRoot = traverseRoots->next();
         ASSERT(traverseRoot);
         for (Element* element = ElementTraversal::firstWithin(*traverseRoot); element; element = ElementTraversal::next(*element, traverseRoot)) {
-            if (selectorMatches(selector, *element, rootNode))
-                matchedElements.append(element);
+            if (selectorMatches(selector, *element, rootNode)) {
+                SelectorQueryTrait::appendElement(output, element);
+                if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
+                    return;
+            }
         }
     }
 }
 
-// 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(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());
-            Node* adjustedRootNode = &rootNode;
-            if (element && (isTreeScopeRoot(rootNode) || element->isDescendantOf(&rootNode)))
-                adjustedRootNode = element;
-            else if (!element || matchSingleNode)
-                adjustedRootNode = 0;
-            if (matchSingleNode) {
-                matchTraverseRoot = true;
-                return adjustedRootNode;
-            }
-            if (startFromParent && adjustedRootNode)
-                adjustedRootNode = adjustedRootNode->parentNode();
-            matchTraverseRoot = false;
-            return adjustedRootNode;
-        }
-        if (selector->relation() == CSSSelector::SubSelector)
-            continue;
-        matchSingleNode = false;
-        if (selector->relation() == CSSSelector::DirectAdjacent || selector->relation() == CSSSelector::IndirectAdjacent)
-            startFromParent = true;
-        else
-            startFromParent = false;
-    }
-    matchTraverseRoot = false;
-    return &rootNode;
-}
-
-Element* SelectorDataList::executeSlowQueryFirst(Node& rootNode) const
+template <typename SelectorQueryTrait>
+void SelectorDataList::executeSlow(Node& rootNode, typename SelectorQueryTrait::OutputType& output) 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;
+            if (selectorMatches(m_selectors[i], *element, rootNode)) {
+                SelectorQueryTrait::appendElement(output, element);
+                if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
+                    return;
+                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;
 }
 
-Element* SelectorDataList::executeQueryFirst(Node& rootNode) const
+template <typename SelectorQueryTrait>
+void SelectorDataList::execute(Node& rootNode, typename SelectorQueryTrait::OutputType& output) const
 {
     if (!canUseFastQuery(rootNode))
-        return executeSlowQueryFirst(rootNode);
+        return executeSlow<SelectorQueryTrait>(rootNode, output);
 
     ASSERT(m_selectors.size() == 1);
     ASSERT(m_selectors[0].selector);
 
     const SelectorData& selector = m_selectors[0];
     const CSSSelector* firstSelector = selector.selector;
 
-    // Fast path for querySelectorAll('#id'), querySelectorAll('tag#id').
+    // Fast path for querySelector*('#id'), querySelector*('tag#id').
     if (const CSSSelector* idSelector = selectorForIdLookup(firstSelector)) {
         const AtomicString& idToMatch = idSelector->value();
         if (rootNode.treeScope().containsMultipleElementsWithId(idToMatch)) {
             const Vector<Element*>& elements = rootNode.treeScope().getAllElementsById(idToMatch);
             size_t count = elements.size();
             for (size_t i = 0; i < count; ++i) {
                 Element* element = elements[i];
                 ASSERT(element);
                 if (!(isTreeScopeRoot(rootNode) || element->isDescendantOf(&rootNode)))
                     continue;
-                if (selectorMatches(selector, *element, rootNode))
-                    return element;
+                if (selectorMatches(selector, *element, rootNode)) {
+                    SelectorQueryTrait::appendElement(output, element);
+                    if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
+                        return;
+                }
             }
-            return 0;
+            return;
         }
         Element* element = rootNode.treeScope().getElementById(idToMatch);
         if (!element || !(isTreeScopeRoot(rootNode) || element->isDescendantOf(&rootNode)))
-            return 0;
-        return selectorMatches(selector, *element, rootNode) ? element : 0;
+            return;
+        if (selectorMatches(selector, *element, rootNode))
+            SelectorQueryTrait::appendElement(output, element);
+        return;
     }
 
     if (!firstSelector->tagHistory()) {
-        // Fast path for querySelector('.foo'), and querySelector('div').
-        // Many web developers uses querySelector with these simple selectors.
+        // Fast path for querySelector*('.foo'), and querySelector*('div').
         switch (firstSelector->m_match) {
         case CSSSelector::Class:
-            return findElementByClassName(rootNode, firstSelector->value());
+            return collectElementsByClassName<SelectorQueryTrait>(rootNode, firstSelector->value(), output);
         case CSSSelector::Tag:
-            return findElementByTagName(rootNode, firstSelector->tagQName());
+            return collectElementsByTagName<SelectorQueryTrait>(rootNode, firstSelector->tagQName(), output);
         default:
             break; // If we need another fast path, add here.
         }
     }
 
-    bool matchTraverseRoot;
-    Node* traverseRootNode = findTraverseRoot(rootNode, matchTraverseRoot);
-    if (!traverseRootNode)
-        return 0;
-    if (matchTraverseRoot) {
-        ASSERT(traverseRootNode->isElementNode());
-        Element& element = toElement(*traverseRootNode);
-        return selectorMatches(selector, element, rootNode) ? &element : 0;
-    }
-
-    for (Element* element = ElementTraversal::firstWithin(*traverseRootNode); element; element = ElementTraversal::next(*element, traverseRootNode)) {
-        if (selectorMatches(selector, *element, rootNode))
-            return element;
-    }
-    return 0;
+    findTraverseRootsAndExecute<SelectorQueryTrait>(rootNode, output);
 }
 
 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();
 }
 
 }