Use Traits in SelectorQuery to avoid a lot of code duplication

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 9334ca52f0f986e2c164c37396d4cebb1c56e24e..f3370cccffc118be04e35c9e8b292fa0f3e091c6 100644
--- a/Source/core/dom/SelectorQuery.cpp
+++ b/Source/core/dom/SelectorQuery.cpp
@@ -1,5 +1,6 @@
 /*
- * 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
@@ -38,76 +39,45 @@
 
 namespace WebCore {
 
-class SimpleNodeList {
-public:
-    virtual ~SimpleNodeList() { }
-    virtual bool isEmpty() const = 0;
-    virtual Node* next() = 0;
-};
-
-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 SingleElementSelectorQueryTrait {
+    typedef Element* OutputType;
+    static const bool shouldOnlyMatchFirstElement = true;
+    ALWAYS_INLINE static void appendElement(OutputType& output, Element& element)
     {
-        Node* current = m_currentNode;
-        m_currentNode = 0;
-        return current;
+        ASSERT(!output);
+        output = &element;
     }
-
-private:
-    Node* m_currentNode;
 };
 
-class ClassRootNodeList FINAL : public SimpleNodeList {
-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; }
-
-    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)
     {
-        Node* current = m_currentElement;
-        ASSERT(current);
-        m_currentElement = nextInternal(ElementTraversal::nextSkippingChildren(*m_currentElement, &m_rootNode));
-        return current;
+        output.append(RefPtr<Node>(element));
     }
-
-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 {
+enum ClassElementListBehavior { AllElements, OnlyRoots };
+
+template <ClassElementListBehavior onlyRoots>
+class ClassElementList {
 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));
+        if (onlyRoots)
+            m_currentElement = nextInternal(ElementTraversal::nextSkippingChildren(*m_currentElement, &m_rootNode));
+        else
+            m_currentElement = nextInternal(ElementTraversal::next(*m_currentElement, &m_rootNode));
         return current;
     }
 
@@ -169,47 +139,39 @@ bool SelectorDataList::matches(Element& targetElement) const
 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);
-}
-
-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* matchedElement = 0;
+    execute<SingleElementSelectorQueryTrait>(rootNode, matchedElement);
+    return matchedElement;
 }
 
-Element* SelectorDataList::findElementByClassName(Node& rootNode, const AtomicString& className) 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))
-            return element;
+        if (element->hasClass() && element->classNames().contains(className)) {
+            SelectorQueryTrait::appendElement(output, *element);
+            if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
+                return;
+        }
     }
-    return 0;
 }
 
-Element* SelectorDataList::findElementByTagName(Node& rootNode, const QualifiedName& tagName) 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))
-            return element;
+        if (SelectorChecker::tagMatches(*element, tagName)) {
+            SelectorQueryTrait::appendElement(output, *element);
+            if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
+                return;
+        }
     }
-    return 0;
 }
 
 inline bool SelectorDataList::canUseFastQuery(const Node& rootNode) const
@@ -237,7 +199,8 @@ inline bool ancestorHasClassName(Node& rootNode, const AtomicString& className)
 //
 // 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.
@@ -256,29 +219,34 @@ PassOwnPtr<SimpleNodeList> SelectorDataList::findTraverseRoots(Node& rootNode, b
             else if (!element || isRightmostSelector)
                 adjustedNode = 0;
             if (isRightmostSelector) {
-                matchTraverseRoots = true;
-                return adoptPtr(new SingleNodeList(adjustedNode));
+                executeForTraverseRoot<SelectorQueryTrait>(m_selectors[0], adjustedNode, MatchesTraverseRoots, rootNode, output);
+                return;
             }
+
             if (startFromParent && adjustedNode)
                 adjustedNode = adjustedNode->parentNode();
 
-            matchTraverseRoots = false;
-            return adoptPtr(new SingleNodeList(adjustedNode));
+            executeForTraverseRoot<SelectorQueryTrait>(m_selectors[0], adjustedNode, DoesNotMatchTraverseRoots, rootNode, output);
+            return;
         }
 
         // 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()));
+                ClassElementList<AllElements> traverseRoots(rootNode, selector->value());
+                executeForTraverseRoots<SelectorQueryTrait>(m_selectors[0], traverseRoots, MatchesTraverseRoots, rootNode, output);
+                return;
             }
-            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));
+            if (ancestorHasClassName(rootNode, selector->value())) {
+                executeForTraverseRoot<SelectorQueryTrait>(m_selectors[0], &rootNode, DoesNotMatchTraverseRoots, rootNode, output);
+                return;
+            }
 
-            return adoptPtr(new ClassRootNodeList(rootNode, selector->value()));
+            ClassElementList<OnlyRoots> traverseRoots(rootNode, selector->value());
+            executeForTraverseRoots<SelectorQueryTrait>(m_selectors[0], traverseRoots, DoesNotMatchTraverseRoots, rootNode, output);
+            return;
         }
 
         if (selector->relation() == CSSSelector::SubSelector)
@@ -290,165 +258,95 @@ PassOwnPtr<SimpleNodeList> SelectorDataList::findTraverseRoots(Node& rootNode, b
             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;
-            }
-        }
-    }
-}
-
-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 SelectorData& selector = m_selectors[0];
-    const CSSSelector* firstSelector = selector.selector;
+    if (!traverseRoot)
+        return;
 
-    // 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);
+    if (matchTraverseRoot) {
+        if (selectorMatches(selector, toElement(*traverseRoot), rootNode))
+            SelectorQueryTrait::appendElement(output, toElement(*traverseRoot));
         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.
+    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;
         }
     }
+}
 
-    bool matchTraverseRoots;
-    OwnPtr<SimpleNodeList> traverseRoots = findTraverseRoots(rootNode, matchTraverseRoots);
-    if (traverseRoots->isEmpty())
+template <typename SelectorQueryTrait, typename SimpleNodeListType>
+void SelectorDataList::executeForTraverseRoots(const SelectorData& selector, SimpleNodeListType& traverseRoots, MatchTraverseRootState matchTraverseRoots, Node& rootNode, typename SelectorQueryTrait::OutputType& output) const
+{
+    if (traverseRoots.isEmpty())
         return;
 
     if (matchTraverseRoots) {
-        while (!traverseRoots->isEmpty()) {
-            Node& node = *traverseRoots->next();
+        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();
+    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
+template <typename SelectorQueryTrait>
+void SelectorDataList::executeSlow(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 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;
+    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)) {
+                SelectorQueryTrait::appendElement(output, *element);
+                if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
+                    return;
+                break;
             }
-            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
+const CSSSelector* SelectorDataList::selectorForIdLookup(const CSSSelector* firstSelector) 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;
-        }
+    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);
+    if (!canUseFastQuery(rootNode)) {
+        executeSlow<SelectorQueryTrait>(rootNode, output);
+        return;
+    }
 
     ASSERT(m_selectors.size() == 1);
     ASSERT(m_selectors[0].selector);
@@ -456,56 +354,47 @@ Element* SelectorDataList::executeQueryFirst(Node& rootNode) const
     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)))
+                Element& element = *elements[i];
+                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());
+            collectElementsByClassName<SelectorQueryTrait>(rootNode, firstSelector->value(), output);
+            return;
         case CSSSelector::Tag:
-            return findElementByTagName(rootNode, firstSelector->tagQName());
+            collectElementsByTagName<SelectorQueryTrait>(rootNode, firstSelector->tagQName(), output);
+            return;
         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)