Implement a simple version of SelectorQuery.

third_party/WebKit/Source/core/dom/SelectorQuery.cpp

 /*
  * 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.
@@ skipping 10 matching lines @@
  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */
 
 #include "config.h"
 #include "core/dom/SelectorQuery.h"
 
 #include "bindings/core/v8/ExceptionState.h"
-#include "core/css/SelectorChecker.h"
 #include "core/css/parser/CSSParser.h"
+#include "core/dom/ContainerNode.h"
 #include "core/dom/Document.h"
-#include "core/dom/ElementTraversal.h"
+#include "core/dom/Element.h"
 #include "core/dom/ExceptionCode.h"
-#include "core/dom/Node.h"
 #include "core/dom/StaticNodeList.h"
-#include "core/dom/shadow/ElementShadow.h"
-#include "core/dom/shadow/ShadowRoot.h"
+#include "core/dom/query/SelectorAnyMatcher.h"
+#include "core/dom/query/SelectorCheckerMatcher.h"
+#include "core/dom/query/SelectorClassMatcher.h"
+#include "core/dom/query/SelectorIdMatcher.h"
+#include "core/dom/query/SelectorMatcher.h"
+#include "core/dom/query/SelectorTagMatcher.h"
 
 namespace blink {
 
-struct SingleElementSelectorQueryTrait {
-    typedef Element* OutputType;
-    static const bool shouldOnlyMatchFirstElement = true;
-    ALWAYS_INLINE static void appendElement(OutputType& output, Element& element)
-    {
-        ASSERT(!output);
-        output = &element;
-    }
-};
-
-struct AllElementsSelectorQueryTrait {
-    typedef WillBeHeapVector<RefPtrWillBeMember<Element>> OutputType;
-    static const bool shouldOnlyMatchFirstElement = false;
-    ALWAYS_INLINE static void appendElement(OutputType& output, Element& element)
-    {
-        output.append(&element);
-    }
-};
-
-enum ClassElementListBehavior { AllElements, OnlyRoots };
-
-template <ClassElementListBehavior onlyRoots>
-class ClassElementList {
-    STACK_ALLOCATED();
-public:
-    ClassElementList(ContainerNode& rootNode, const AtomicString& className)
-        : m_className(className)
-        , m_rootNode(&rootNode)
-        , m_currentElement(nextInternal(ElementTraversal::firstWithin(rootNode))) { }
-
-    bool isEmpty() const { return !m_currentElement; }
-
-    Element* next()
-    {
-        Element* current = m_currentElement;
-        ASSERT(current);
-        if (onlyRoots)
-            m_currentElement = nextInternal(ElementTraversal::nextSkippingChildren(*m_currentElement, m_rootNode));
-        else
-            m_currentElement = nextInternal(ElementTraversal::next(*m_currentElement, m_rootNode));
-        return current;
-    }
-
-private:
-    Element* nextInternal(Element* element)
-    {
-        for (; element; element = ElementTraversal::next(*element, m_rootNode)) {
-            if (element->hasClass() && element->classNames().contains(m_className))
-                return element;
-        }
-        return nullptr;
-    }
-
-    const AtomicString& m_className;
-    RawPtrWillBeMember<ContainerNode> m_rootNode;
-    RawPtrWillBeMember<Element> m_currentElement;
-};
-
-void SelectorDataList::initialize(const CSSSelectorList& selectorList)
-{
-    ASSERT(m_selectors.isEmpty());
-
-    unsigned selectorCount = 0;
-    for (const CSSSelector* selector = selectorList.first(); selector; selector = CSSSelectorList::next(*selector))
-        selectorCount++;
-
-    m_usesDeepCombinatorOrShadowPseudo = false;
-    m_needsUpdatedDistribution = false;
-    m_selectors.reserveInitialCapacity(selectorCount);
-    unsigned index = 0;
-    for (const CSSSelector* selector = selectorList.first(); selector; selector = CSSSelectorList::next(*selector), ++index) {
-        m_selectors.uncheckedAppend(selector);
-        m_usesDeepCombinatorOrShadowPseudo |= selectorList.selectorUsesDeepCombinatorOrShadowPseudo(index);
-        m_needsUpdatedDistribution |= selectorList.selectorNeedsUpdatedDistribution(index);
-    }
-}
-
-inline bool SelectorDataList::selectorMatches(const CSSSelector& selector, Element& element, const ContainerNode& rootNode) const
-{
-    SelectorChecker selectorChecker(SelectorChecker::QueryingRules);
-    SelectorChecker::SelectorCheckingContext selectorCheckingContext(&element, SelectorChecker::VisitedMatchDisabled);
-    selectorCheckingContext.selector = &selector;
-    selectorCheckingContext.scope = &rootNode;
-    return selectorChecker.match(selectorCheckingContext);
-}
-
-bool SelectorDataList::matches(Element& targetElement) const
-{
-    if (m_needsUpdatedDistribution)
-        targetElement.updateDistribution();
-
-    unsigned selectorCount = m_selectors.size();
-    for (unsigned i = 0; i < selectorCount; ++i) {
-        if (selectorMatches(*m_selectors[i], targetElement, targetElement))
-            return true;
-    }
-
-    return false;
-}
-
-Element* SelectorDataList::closest(Element& targetElement) const
-{
-    if (m_needsUpdatedDistribution)
-        targetElement.updateDistribution();
-
-    unsigned selectorCount = m_selectors.size();
-    for (Element* currentElement = &targetElement; currentElement; currentElement = currentElement->parentElement()) {
-        for (unsigned i = 0; i < selectorCount; ++i) {
-            if (selectorMatches(*m_selectors[i], *currentElement, targetElement))
-                return currentElement;
-        }
-    }
-    return nullptr;
-}
-
-PassRefPtrWillBeRawPtr<StaticElementList> SelectorDataList::queryAll(ContainerNode& rootNode) const
-{
-    WillBeHeapVector<RefPtrWillBeMember<Element>> result;
-    execute<AllElementsSelectorQueryTrait>(rootNode, result);
-    return StaticElementList::adopt(result);
-}
-
-PassRefPtrWillBeRawPtr<Element> SelectorDataList::queryFirst(ContainerNode& rootNode) const
-{
-    Element* matchedElement = nullptr;
-    execute<SingleElementSelectorQueryTrait>(rootNode, matchedElement);
-    return matchedElement;
-}
-
-template <typename SelectorQueryTrait>
-void SelectorDataList::collectElementsByClassName(ContainerNode& rootNode, const AtomicString& className,  typename SelectorQueryTrait::OutputType& output) const
-{
-    for (Element& element : ElementTraversal::descendantsOf(rootNode)) {
-        if (element.hasClass() && element.classNames().contains(className)) {
-            SelectorQueryTrait::appendElement(output, element);
-            if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
-                return;
-        }
-    }
-}
-
-inline bool matchesTagName(const QualifiedName& tagName, const Element& element)
-{
-    if (tagName == anyQName())
-        return true;
-    if (element.hasLocalName(tagName.localName()))
-        return true;
-    // Non-html elements in html documents are normalized to their camel-cased
-    // version during parsing if applicable. Yet, type selectors are lower-cased
-    // for selectors in html documents. Compare the upper case converted names
-    // instead to allow matching SVG elements like foreignObject.
-    if (!element.isHTMLElement() && element.document().isHTMLDocument())
-        return element.tagQName().localNameUpper() == tagName.localNameUpper();
-    return false;
-}
-
-template <typename SelectorQueryTrait>
-void SelectorDataList::collectElementsByTagName(ContainerNode& rootNode, const QualifiedName& tagName,  typename SelectorQueryTrait::OutputType& output) const
-{
-    for (Element& element : ElementTraversal::descendantsOf(rootNode)) {
-        // querySelector*() doesn't allow namespaces and throws before it gets
-        // here so we can ignore them.
-        ASSERT(tagName.namespaceURI() == starAtom);
-        if (matchesTagName(tagName, element)) {
-            SelectorQueryTrait::appendElement(output, element);
-            if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
-                return;
-        }
-    }
-}
-
-inline bool SelectorDataList::canUseFastQuery(const ContainerNode& rootNode) const
-{
-    if (m_usesDeepCombinatorOrShadowPseudo)
-        return false;
-    if (m_needsUpdatedDistribution)
-        return false;
-    if (rootNode.document().inQuirksMode())
-        return false;
-    if (!rootNode.inDocument())
-        return false;
-    return m_selectors.size() == 1;
-}
-
-inline bool ancestorHasClassName(ContainerNode& 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.
-template <typename SelectorQueryTrait>
-void SelectorDataList::findTraverseRootsAndExecute(ContainerNode& 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);
-
-    bool isRightmostSelector = true;
-    bool startFromParent = false;
-
-    for (const CSSSelector* selector = m_selectors[0]; selector; selector = selector->tagHistory()) {
-        if (selector->match() == CSSSelector::Id && !rootNode.document().containsMultipleElementsWithId(selector->value())) {
-            Element* element = rootNode.treeScope().getElementById(selector->value());
-            ContainerNode* adjustedNode = &rootNode;
-            if (element && (isTreeScopeRoot(rootNode) || element->isDescendantOf(&rootNode)))
-                adjustedNode = element;
-            else if (!element || isRightmostSelector)
-                adjustedNode = nullptr;
-            if (isRightmostSelector) {
-                executeForTraverseRoot<SelectorQueryTrait>(*m_selectors[0], adjustedNode, MatchesTraverseRoots, rootNode, output);
-                return;
-            }
-
-            if (startFromParent && adjustedNode)
-                adjustedNode = adjustedNode->parentNode();
-
-            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 (!SelectorQueryTrait::shouldOnlyMatchFirstElement && !startFromParent && selector->match() == CSSSelector::Class) {
-            if (isRightmostSelector) {
-                ClassElementList<AllElements> traverseRoots(rootNode, selector->value());
-                executeForTraverseRoots<SelectorQueryTrait>(*m_selectors[0], traverseRoots, MatchesTraverseRoots, rootNode, output);
-                return;
-            }
-            // Since there exists some ancestor element which has the class name, we need to see all children of rootNode.
-            if (ancestorHasClassName(rootNode, selector->value())) {
-                executeForTraverseRoot<SelectorQueryTrait>(*m_selectors[0], &rootNode, DoesNotMatchTraverseRoots, rootNode, output);
-                return;
-            }
-
-            ClassElementList<OnlyRoots> traverseRoots(rootNode, selector->value());
-            executeForTraverseRoots<SelectorQueryTrait>(*m_selectors[0], traverseRoots, DoesNotMatchTraverseRoots, rootNode, output);
-            return;
-        }
-
-        if (selector->relation() == CSSSelector::SubSelector)
-            continue;
-        isRightmostSelector = false;
-        if (selector->relation() == CSSSelector::DirectAdjacent || selector->relation() == CSSSelector::IndirectAdjacent)
-            startFromParent = true;
-        else
-            startFromParent = false;
-    }
-
-    executeForTraverseRoot<SelectorQueryTrait>(*m_selectors[0], &rootNode, DoesNotMatchTraverseRoots, rootNode, output);
-}
-
-template <typename SelectorQueryTrait>
-void SelectorDataList::executeForTraverseRoot(const CSSSelector& selector, ContainerNode* traverseRoot, MatchTraverseRootState matchTraverseRoot, ContainerNode& rootNode, typename SelectorQueryTrait::OutputType& output) const
-{
-    if (!traverseRoot)
-        return;
-
-    if (matchTraverseRoot) {
-        if (selectorMatches(selector, toElement(*traverseRoot), rootNode))
-            SelectorQueryTrait::appendElement(output, toElement(*traverseRoot));
-        return;
-    }
-
-    for (Element& element : ElementTraversal::descendantsOf(*traverseRoot)) {
-        if (selectorMatches(selector, element, rootNode)) {
-            SelectorQueryTrait::appendElement(output, element);
-            if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
-                return;
-        }
-    }
-}
-
-template <typename SelectorQueryTrait, typename SimpleElementListType>
-void SelectorDataList::executeForTraverseRoots(const CSSSelector& selector, SimpleElementListType& traverseRoots, MatchTraverseRootState matchTraverseRoots, ContainerNode& rootNode, typename SelectorQueryTrait::OutputType& output) const
-{
-    if (traverseRoots.isEmpty())
-        return;
-
-    if (matchTraverseRoots) {
-        while (!traverseRoots.isEmpty()) {
-            Element& element = *traverseRoots.next();
-            if (selectorMatches(selector, element, rootNode)) {
-                SelectorQueryTrait::appendElement(output, element);
-                if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
-                    return;
-            }
-        }
-        return;
-    }
-
-    while (!traverseRoots.isEmpty()) {
-        for (Element& element : ElementTraversal::descendantsOf(*traverseRoots.next())) {
-            if (selectorMatches(selector, element, rootNode)) {
-                SelectorQueryTrait::appendElement(output, element);
-                if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
-                    return;
-            }
-        }
-    }
-}
-
-template <typename SelectorQueryTrait>
-bool SelectorDataList::selectorListMatches(ContainerNode& rootNode, Element& element, typename SelectorQueryTrait::OutputType& output) const
-{
-    for (unsigned i = 0; i < m_selectors.size(); ++i) {
-        if (selectorMatches(*m_selectors[i], element, rootNode)) {
-            SelectorQueryTrait::appendElement(output, element);
-            return true;
-        }
-    }
-    return false;
-}
-
-template <typename SelectorQueryTrait>
-void SelectorDataList::executeSlow(ContainerNode& rootNode, typename SelectorQueryTrait::OutputType& output) const
-{
-    for (Element& element : ElementTraversal::descendantsOf(rootNode)) {
-        if (selectorListMatches<SelectorQueryTrait>(rootNode, element, output) && SelectorQueryTrait::shouldOnlyMatchFirstElement)
-            return;
-    }
-}
-
-// FIXME: Move the following helper functions, authorShadowRootOf, firstWithinTraversingShadowTree,
-// nextTraversingShadowTree to the best place, e.g. NodeTraversal.
-static ShadowRoot* authorShadowRootOf(const ContainerNode& node)
-{
-    if (!node.isElementNode() || !isShadowHost(&node))
-        return nullptr;
-
-    ElementShadow* shadow = toElement(node).shadow();
-    ASSERT(shadow);
-    for (ShadowRoot* shadowRoot = shadow->oldestShadowRoot(); shadowRoot; shadowRoot = shadowRoot->youngerShadowRoot()) {
-        if (shadowRoot->type() == ShadowRootType::V0 || shadowRoot->type() == ShadowRootType::Open)
-            return shadowRoot;
-    }
-    return nullptr;
-}
-
-static ContainerNode* firstWithinTraversingShadowTree(const ContainerNode& rootNode)
-{
-    if (ShadowRoot* shadowRoot = authorShadowRootOf(rootNode))
-        return shadowRoot;
-    return ElementTraversal::firstWithin(rootNode);
-}
-
-static ContainerNode* nextTraversingShadowTree(const ContainerNode& node, const ContainerNode* rootNode)
-{
-    if (ShadowRoot* shadowRoot = authorShadowRootOf(node))
-        return shadowRoot;
-
-    const ContainerNode* current = &node;
-    while (current) {
-        if (Element* next = ElementTraversal::next(*current, rootNode))
-            return next;
-
-        if (!current->isInShadowTree())
-            return nullptr;
-
-        ShadowRoot* shadowRoot = current->containingShadowRoot();
-        if (shadowRoot == rootNode)
-            return nullptr;
-        if (ShadowRoot* youngerShadowRoot = shadowRoot->youngerShadowRoot()) {
-            // Should not obtain any elements in closed or user-agent shadow root.
-            ASSERT(youngerShadowRoot->type() == ShadowRootType::V0 || youngerShadowRoot->type() == ShadowRootType::Open);
-            return youngerShadowRoot;
-        }
-
-        current = shadowRoot->host();
-    }
-    return nullptr;
-}
-
-template <typename SelectorQueryTrait>
-void SelectorDataList::executeSlowTraversingShadowTree(ContainerNode& rootNode, typename SelectorQueryTrait::OutputType& output) const
-{
-    for (ContainerNode* node = firstWithinTraversingShadowTree(rootNode); node; node = nextTraversingShadowTree(*node, &rootNode)) {
-        if (!node->isElementNode())
-            continue;
-        Element* element = toElement(node);
-        if (selectorListMatches<SelectorQueryTrait>(rootNode, *element, output) && SelectorQueryTrait::shouldOnlyMatchFirstElement)
-            return;
-    }
-}
-
-const CSSSelector* SelectorDataList::selectorForIdLookup(const CSSSelector& firstSelector) const
-{
-    for (const CSSSelector* selector = &firstSelector; selector; selector = selector->tagHistory()) {
-        if (selector->match() == CSSSelector::Id)
-            return selector;
-        if (selector->relation() != CSSSelector::SubSelector)
-            break;
-    }
-    return nullptr;
-}
-
-template <typename SelectorQueryTrait>
-void SelectorDataList::execute(ContainerNode& rootNode, typename SelectorQueryTrait::OutputType& output) const
-{
-    if (!canUseFastQuery(rootNode)) {
-        if (m_needsUpdatedDistribution)
-            rootNode.updateDistribution();
-        if (m_usesDeepCombinatorOrShadowPseudo) {
-            executeSlowTraversingShadowTree<SelectorQueryTrait>(rootNode, output);
-        } else {
-            executeSlow<SelectorQueryTrait>(rootNode, output);
-        }
-        return;
-    }
-
-    ASSERT(m_selectors.size() == 1);
-
-    const CSSSelector& selector = *m_selectors[0];
-    const CSSSelector& firstSelector = selector;
-
-    // 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 WillBeHeapVector<RawPtrWillBeMember<Element>>& elements = rootNode.treeScope().getAllElementsById(idToMatch);
-            size_t count = elements.size();
-            for (size_t i = 0; i < count; ++i) {
-                Element& element = *elements[i];
-                if (!(isTreeScopeRoot(rootNode) || element.isDescendantOf(&rootNode)))
-                    continue;
-                if (selectorMatches(selector, element, rootNode)) {
-                    SelectorQueryTrait::appendElement(output, element);
-                    if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
-                        return;
-                }
-            }
-            return;
-        }
-        Element* element = rootNode.treeScope().getElementById(idToMatch);
-        if (!element || !(isTreeScopeRoot(rootNode) || element->isDescendantOf(&rootNode)))
-            return;
-        if (selectorMatches(selector, *element, rootNode))
-            SelectorQueryTrait::appendElement(output, *element);
-        return;
-    }
-
-    if (!firstSelector.tagHistory()) {
-        // Fast path for querySelector*('.foo'), and querySelector*('div').
-        switch (firstSelector.match()) {
-        case CSSSelector::Class:
-            collectElementsByClassName<SelectorQueryTrait>(rootNode, firstSelector.value(), output);
-            return;
-        case CSSSelector::Tag:
-            collectElementsByTagName<SelectorQueryTrait>(rootNode, firstSelector.tagQName(), output);
-            return;
-        default:
-            break; // If we need another fast path, add here.
-        }
-    }
-
-    findTraverseRootsAndExecute<SelectorQueryTrait>(rootNode, output);
-}
-
 PassOwnPtr<SelectorQuery> SelectorQuery::adopt(CSSSelectorList& selectorList)
 {
     return adoptPtr(new SelectorQuery(selectorList));
 }
 
+SelectorQuery::~SelectorQuery()
+{
+}
+
+static PassOwnPtr<SelectorMatcher> createMatcher(CSSSelectorList& selectorList)
+{
+    if (selectorList.hasOneSelector() && !selectorList.first()->tagHistory()) {
+        const CSSSelector* selector = selectorList.first();
+        switch (selector->match()) {
+        case CSSSelector::Id:
+            return adoptPtr(new SelectorIdMatcher(selector->value()));
+        case CSSSelector::Class:
+            return adoptPtr(new SelectorClassMatcher(selector->value()));
+        case CSSSelector::Tag:
+            if (selector->tagQName() == anyQName())
+                return adoptPtr(new SelectorAnyMatcher());
+            return adoptPtr(new SelectorTagMatcher(selector->tagQName()));
+        default:
+            break;
+        }
+    }
+    return adoptPtr(new SelectorCheckerMatcher(selectorList));
+}
+
 SelectorQuery::SelectorQuery(CSSSelectorList& selectorList)
+    : m_matcher(createMatcher(selectorList))
 {
-    m_selectorList.adopt(selectorList);
-    m_selectors.initialize(m_selectorList);
+    ASSERT(m_matcher);
 }
 
 bool SelectorQuery::matches(Element& element) const
 {
-    return m_selectors.matches(element);
+    return m_matcher->match(element, element);
 }
 
 Element* SelectorQuery::closest(Element& element) const
 {
-    return m_selectors.closest(element);
+    for (Element* current = &element; current; current = current->parentElement()) {
+        if (m_matcher->match(*current, element))
+            return current;
+    }
+    return nullptr;
 }
 
 PassRefPtrWillBeRawPtr<StaticElementList> SelectorQuery::queryAll(ContainerNode& rootNode) const
 {
-    return m_selectors.queryAll(rootNode);
+    WillBeHeapVector<RefPtrWillBeMember<Element>> result;
+    m_matcher->findAll(rootNode, result);
+    return StaticElementList::adopt(result);
 }
 
-PassRefPtrWillBeRawPtr<Element> SelectorQuery::queryFirst(ContainerNode& rootNode) const
+Element* SelectorQuery::queryFirst(ContainerNode& rootNode) const
 {
-    return m_selectors.queryFirst(rootNode);
+    return m_matcher->findFirst(rootNode);
 }
 
 SelectorQuery* SelectorQueryCache::add(const AtomicString& selectors, const Document& document, ExceptionState& exceptionState)
 {
     HashMap<AtomicString, OwnPtr<SelectorQuery>>::iterator it = m_entries.find(selectors);
     if (it != m_entries.end())
         return it->value.get();
 
     CSSSelectorList selectorList;
     CSSParser::parseSelector(CSSParserContext(document, nullptr), selectors, selectorList);
@@ skipping 15 matching lines @@
 
     return m_entries.add(selectors, SelectorQuery::adopt(selectorList)).storedValue->value.get();
 }
 
 void SelectorQueryCache::invalidate()
 {
     m_entries.clear();
 }
 
 }