Implement a simple version of SelectorQuery.

third_party/WebKit/Source/core/dom/query/SelectorCheckerMatcher.cpp

Index: third_party/WebKit/Source/core/dom/query/SelectorCheckerMatcher.cpp
diff --git a/third_party/WebKit/Source/core/dom/query/SelectorCheckerMatcher.cpp b/third_party/WebKit/Source/core/dom/query/SelectorCheckerMatcher.cpp
new file mode 100644
index 0000000000000000000000000000000000000000..58d12c03c6ca0279602f3029caa2fe92fa0d5d2d
--- /dev/null
+++ b/third_party/WebKit/Source/core/dom/query/SelectorCheckerMatcher.cpp
@@ -0,0 +1,115 @@
+// Copyright 2015 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "config.h"
+#include "core/dom/query/SelectorCheckerMatcher.h"
+
+#include "core/css/SelectorChecker.h"
+#include "core/dom/ContainerNode.h"
+#include "core/dom/Element.h"
+#include "core/dom/ElementTraversal.h"
+#include "core/dom/shadow/ElementShadow.h"
+#include "core/dom/shadow/ShadowRoot.h"
+
+namespace blink {
+
+SelectorCheckerMatcher::SelectorCheckerMatcher(CSSSelectorList& selectorList)
+    : m_selectorList(selectorList)
+    , m_usesDeepCombinatorOrShadowPseudo(false)
+    , m_needsUpdatedDistribution(false)
+{
+    unsigned index = 0;
+    for (const CSSSelector* selector = selectorList.first(); selector; selector = CSSSelectorList::next(*selector), ++index) {
+        m_usesDeepCombinatorOrShadowPseudo |= selectorList.selectorUsesDeepCombinatorOrShadowPseudo(index);
+        m_needsUpdatedDistribution |= selectorList.selectorNeedsUpdatedDistribution(index);
+    }
+}
+
+SelectorCheckerMatcher::~SelectorCheckerMatcher()
+{
+}
+
+static ShadowRoot* oldestOpenShadowRoot(const ContainerNode& node)
+{
+    if (!node.isElementNode())
+        return nullptr;
+    ElementShadow* shadow = toElement(node).shadow();
+    if (!shadow)
+        return nullptr;
+    for (ShadowRoot* root = shadow->oldestShadowRoot(); root; root = root->youngerShadowRoot()) {
+        if (root->type() == ShadowRootType::V0 || root->type() == ShadowRootType::Open)
+            return root;
+    }
+    return nullptr;
+}
+
+static Element* nextTraversingShadowTree(const ContainerNode& node, const ContainerNode* rootNode)
+{
+    if (ShadowRoot* shadowRoot = oldestOpenShadowRoot(node)) {
+        if (Element* next = ElementTraversal::firstWithin(*shadowRoot))
+            return next;
+    }
+
+    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);
+            current = youngerShadowRoot;
+        } else {
+            current = shadowRoot->host();
+        }
+    }
+
+    return nullptr;
+}
+
+Element* SelectorCheckerMatcher::findFirst(ContainerNode& rootNode) const
+{
+    if (m_usesDeepCombinatorOrShadowPseudo) {
+        for (Element* element = nextTraversingShadowTree(rootNode, &rootNode); element; element = nextTraversingShadowTree(*element, &rootNode)) {
+            if (match(*element, rootNode))
+                return element;
+        }
+        return nullptr;
+    }
+    return SelectorMatcher::findFirst(rootNode);
+}
+
+void SelectorCheckerMatcher::findAll(ContainerNode& rootNode, WillBeHeapVector<RefPtrWillBeMember<Element>>& result) const
+{
+    if (m_usesDeepCombinatorOrShadowPseudo) {
+        for (Element* element = nextTraversingShadowTree(rootNode, &rootNode); element; element = nextTraversingShadowTree(*element, &rootNode)) {
+            if (match(*element, rootNode))
+                result.append(element);
+        }
+        return;
+    }
+    return SelectorMatcher::findAll(rootNode, result);
+}
+
+bool SelectorCheckerMatcher::match(Element& element, ContainerNode& rootNode) const
+{
+    // XXX: Add a fast path here, this does ancestor walking repeatedly.
+    if (m_needsUpdatedDistribution)
+        rootNode.updateDistribution();
+    SelectorChecker checker(SelectorChecker::QueryingRules);
+    SelectorChecker::SelectorCheckingContext context(&element, SelectorChecker::VisitedMatchDisabled);
+    context.scope = &rootNode;
+    for (const CSSSelector* selector = m_selectorList.first(); selector; selector = CSSSelectorList::next(*selector)) {
+        context.selector = selector;
+        if (checker.match(context))
+            return true;
+    }
+    return false;
+}
+
+}