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..9291c11b70bd8c80831f9f67efdf3bfac3dcb91e 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,40 +39,37 @@
 
 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);
@@ -94,16 +92,16 @@ private:
     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);
@@ -169,47 +167,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);
+    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);
-    }
-}
-
-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;
+        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 +227,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.
@@ -255,30 +246,28 @@ PassOwnPtr<SimpleNodeList> SelectorDataList::findTraverseRoots(Node& rootNode, b
                 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)
@@ -290,82 +279,33 @@ 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);
+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

+{
     if (traverseRoots->isEmpty())
         return;
 
@@ -373,8 +313,11 @@ void SelectorDataList::executeQueryAll(Node& rootNode, Vector<RefPtr<Node> >& ma
         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;
     }
@@ -383,72 +326,46 @@ void SelectorDataList::executeQueryAll(Node& rootNode, Vector<RefPtr<Node> >& ma
         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);
+        return executeSlow<SelectorQueryTrait>(rootNode, output);
 
     ASSERT(m_selectors.size() == 1);
     ASSERT(m_selectors[0].selector);
@@ -456,7 +373,7 @@ 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)) {
@@ -467,45 +384,35 @@ Element* SelectorDataList::executeQueryFirst(Node& rootNode) const
                 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)