#include "config.h"
#include "core/dom/SelectorQuery.h"
-#include "bindings/v8/ExceptionState.h"
-#include "core/css/parser/BisonCSSParser.h"
+#include "bindings/core/v8/ExceptionState.h"
#include "core/css/SelectorChecker.h"
-#include "core/css/SelectorCheckerFastPath.h"
#include "core/css/SiblingTraversalStrategies.h"
+#include "core/css/parser/CSSParser.h"
#include "core/dom/Document.h"
#include "core/dom/ElementTraversal.h"
#include "core/dom/Node.h"
#include "core/dom/StaticNodeList.h"
+#include "core/dom/shadow/ElementShadow.h"
+#include "core/dom/shadow/ShadowRoot.h"
-namespace WebCore {
+namespace blink {
struct SingleElementSelectorQueryTrait {
typedef Element* OutputType;
};
struct AllElementsSelectorQueryTrait {
- typedef Vector<RefPtr<Node> > OutputType;
+ typedef WillBeHeapVector<RefPtrWillBeMember<Element> > OutputType;
static const bool shouldOnlyMatchFirstElement = false;
- ALWAYS_INLINE static void appendElement(OutputType& output, Node& element)
+ ALWAYS_INLINE static void appendElement(OutputType& output, Element& element)
{
- output.append(RefPtr<Node>(element));
+ output.append(&element);
}
};
template <ClassElementListBehavior onlyRoots>
class ClassElementList {
+ STACK_ALLOCATED();
public:
ClassElementList(ContainerNode& rootNode, const AtomicString& className)
: m_className(className)
- , m_rootNode(rootNode)
+ , m_rootNode(&rootNode)
, m_currentElement(nextInternal(ElementTraversal::firstWithin(rootNode))) { }
bool isEmpty() const { return !m_currentElement; }
Element* current = m_currentElement;
ASSERT(current);
if (onlyRoots)
- m_currentElement = nextInternal(ElementTraversal::nextSkippingChildren(*m_currentElement, &m_rootNode));
+ m_currentElement = nextInternal(ElementTraversal::nextSkippingChildren(*m_currentElement, m_rootNode));
else
- m_currentElement = nextInternal(ElementTraversal::next(*m_currentElement, &m_rootNode));
+ m_currentElement = nextInternal(ElementTraversal::next(*m_currentElement, m_rootNode));
return current;
}
private:
Element* nextInternal(Element* element)
{
- for (; element; element = ElementTraversal::next(*element, &m_rootNode)) {
+ for (; element; element = ElementTraversal::next(*element, m_rootNode)) {
if (element->hasClass() && element->classNames().contains(m_className))
return element;
}
}
const AtomicString& m_className;
- ContainerNode& m_rootNode;
- Element* m_currentElement;
+ RawPtrWillBeMember<ContainerNode> m_rootNode;
+ RawPtrWillBeMember<Element> m_currentElement;
};
void SelectorDataList::initialize(const CSSSelectorList& selectorList)
for (const CSSSelector* selector = selectorList.first(); selector; selector = CSSSelectorList::next(*selector))
selectorCount++;
+ m_crossesTreeBoundary = false;
m_selectors.reserveInitialCapacity(selectorCount);
- for (const CSSSelector* selector = selectorList.first(); selector; selector = CSSSelectorList::next(*selector))
- m_selectors.uncheckedAppend(SelectorData(*selector, SelectorCheckerFastPath::canUse(*selector)));
+ unsigned index = 0;
+ for (const CSSSelector* selector = selectorList.first(); selector; selector = CSSSelectorList::next(*selector), ++index) {
+ m_selectors.uncheckedAppend(selector);
+ m_crossesTreeBoundary |= selectorList.selectorCrossesTreeScopes(index);
+ }
}
-inline bool SelectorDataList::selectorMatches(const SelectorData& selectorData, Element& element, const ContainerNode& rootNode) const
+inline bool SelectorDataList::selectorMatches(const CSSSelector& selector, Element& element, const ContainerNode& rootNode) const
{
- if (selectorData.isFastCheckable && !element.isSVGElement()) {
- SelectorCheckerFastPath selectorCheckerFastPath(selectorData.selector, element);
- if (!selectorCheckerFastPath.matchesRightmostSelector(SelectorChecker::VisitedMatchDisabled))
- return false;
- return selectorCheckerFastPath.matches();
- }
-
SelectorChecker selectorChecker(element.document(), SelectorChecker::QueryingRules);
- SelectorChecker::SelectorCheckingContext selectorCheckingContext(selectorData.selector, &element, SelectorChecker::VisitedMatchDisabled);
- selectorCheckingContext.behaviorAtBoundary = SelectorChecker::StaysWithinTreeScope;
+ SelectorChecker::SelectorCheckingContext selectorCheckingContext(selector, &element, SelectorChecker::VisitedMatchDisabled);
selectorCheckingContext.scope = !rootNode.isDocumentNode() ? &rootNode : 0;
+ if (selectorCheckingContext.scope)
+ selectorCheckingContext.contextFlags = SelectorChecker::ScopeContainsLastMatchedElement;
return selectorChecker.match(selectorCheckingContext, DOMSiblingTraversalStrategy()) == SelectorChecker::SelectorMatches;
}
{
unsigned selectorCount = m_selectors.size();
for (unsigned i = 0; i < selectorCount; ++i) {
- if (selectorMatches(m_selectors[i], targetElement, targetElement))
+ if (selectorMatches(*m_selectors[i], targetElement, targetElement))
return true;
}
return false;
}
-PassRefPtr<NodeList> SelectorDataList::queryAll(ContainerNode& rootNode) const
+PassRefPtrWillBeRawPtr<StaticElementList> SelectorDataList::queryAll(ContainerNode& rootNode) const
{
- Vector<RefPtr<Node> > result;
+ WillBeHeapVector<RefPtrWillBeMember<Element> > result;
execute<AllElementsSelectorQueryTrait>(rootNode, result);
- return StaticNodeList::adopt(result);
+ return StaticElementList::adopt(result);
}
-PassRefPtr<Element> SelectorDataList::queryFirst(ContainerNode& rootNode) const
+PassRefPtrWillBeRawPtr<Element> SelectorDataList::queryFirst(ContainerNode& rootNode) const
{
Element* matchedElement = 0;
execute<SingleElementSelectorQueryTrait>(rootNode, matchedElement);
inline bool SelectorDataList::canUseFastQuery(const ContainerNode& rootNode) const
{
- return m_selectors.size() == 1 && rootNode.inDocument() && !rootNode.document().inQuirksMode();
+ return m_selectors.size() == 1 && !m_crossesTreeBoundary && rootNode.inDocument() && !rootNode.document().inQuirksMode();
}
inline bool ancestorHasClassName(ContainerNode& rootNode, const AtomicString& className)
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())) {
+ 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)))
else if (!element || isRightmostSelector)
adjustedNode = 0;
if (isRightmostSelector) {
- executeForTraverseRoot<SelectorQueryTrait>(m_selectors[0], adjustedNode, MatchesTraverseRoots, rootNode, output);
+ 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);
+ 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->m_match == CSSSelector::Class) {
+ 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);
+ 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);
+ 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);
+ executeForTraverseRoots<SelectorQueryTrait>(*m_selectors[0], traverseRoots, DoesNotMatchTraverseRoots, rootNode, output);
return;
}
startFromParent = false;
}
- executeForTraverseRoot<SelectorQueryTrait>(m_selectors[0], &rootNode, DoesNotMatchTraverseRoots, rootNode, output);
+ executeForTraverseRoot<SelectorQueryTrait>(*m_selectors[0], &rootNode, DoesNotMatchTraverseRoots, rootNode, output);
}
template <typename SelectorQueryTrait>
-void SelectorDataList::executeForTraverseRoot(const SelectorData& selector, ContainerNode* traverseRoot, MatchTraverseRootState matchTraverseRoot, ContainerNode& rootNode, typename SelectorQueryTrait::OutputType& output) const
+void SelectorDataList::executeForTraverseRoot(const CSSSelector& selector, ContainerNode* traverseRoot, MatchTraverseRootState matchTraverseRoot, ContainerNode& rootNode, typename SelectorQueryTrait::OutputType& output) const
{
if (!traverseRoot)
return;
}
template <typename SelectorQueryTrait, typename SimpleElementListType>
-void SelectorDataList::executeForTraverseRoots(const SelectorData& selector, SimpleElementListType& traverseRoots, MatchTraverseRootState matchTraverseRoots, ContainerNode& rootNode, typename SelectorQueryTrait::OutputType& output) const
+void SelectorDataList::executeForTraverseRoots(const CSSSelector& selector, SimpleElementListType& traverseRoots, MatchTraverseRootState matchTraverseRoots, ContainerNode& rootNode, typename SelectorQueryTrait::OutputType& output) const
{
if (traverseRoots.isEmpty())
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::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 (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 0;
+
+ ElementShadow* shadow = toElement(node).shadow();
+ ASSERT(shadow);
+ for (ShadowRoot* shadowRoot = shadow->oldestShadowRoot(); shadowRoot; shadowRoot = shadowRoot->youngerShadowRoot()) {
+ if (shadowRoot->type() == ShadowRoot::AuthorShadowRoot)
+ return shadowRoot;
+ }
+ return 0;
+}
+
+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 0;
+
+ ShadowRoot* shadowRoot = current->containingShadowRoot();
+ if (shadowRoot == rootNode)
+ return 0;
+ if (ShadowRoot* youngerShadowRoot = shadowRoot->youngerShadowRoot()) {
+ // Should not obtain any elements in user-agent shadow root.
+ ASSERT(youngerShadowRoot->type() == ShadowRoot::AuthorShadowRoot);
+ return youngerShadowRoot;
}
+
+ current = shadowRoot->host();
+ }
+ return 0;
+}
+
+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->m_match == CSSSelector::Id)
+ if (selector->match() == CSSSelector::Id)
return selector;
if (selector->relation() != CSSSelector::SubSelector)
break;
void SelectorDataList::execute(ContainerNode& rootNode, typename SelectorQueryTrait::OutputType& output) const
{
if (!canUseFastQuery(rootNode)) {
- executeSlow<SelectorQueryTrait>(rootNode, output);
+ if (m_crossesTreeBoundary) {
+ rootNode.document().updateDistributionForNodeIfNeeded(&rootNode);
+ executeSlowTraversingShadowTree<SelectorQueryTrait>(rootNode, output);
+ } else {
+ executeSlow<SelectorQueryTrait>(rootNode, output);
+ }
return;
}
ASSERT(m_selectors.size() == 1);
- const SelectorData& selector = m_selectors[0];
- const CSSSelector& firstSelector = selector.selector;
+ 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 Vector<Element*>& elements = rootNode.treeScope().getAllElementsById(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 (!firstSelector.tagHistory()) {
// Fast path for querySelector*('.foo'), and querySelector*('div').
- switch (firstSelector.m_match) {
+ switch (firstSelector.match()) {
case CSSSelector::Class:
collectElementsByClassName<SelectorQueryTrait>(rootNode, firstSelector.value(), output);
return;
findTraverseRootsAndExecute<SelectorQueryTrait>(rootNode, output);
}
-SelectorQuery::SelectorQuery(const CSSSelectorList& selectorList)
- : m_selectorList(selectorList)
+PassOwnPtr<SelectorQuery> SelectorQuery::adopt(CSSSelectorList& selectorList)
+{
+ return adoptPtr(new SelectorQuery(selectorList));
+}
+
+SelectorQuery::SelectorQuery(CSSSelectorList& selectorList)
{
+ m_selectorList.adopt(selectorList);
m_selectors.initialize(m_selectorList);
}
return m_selectors.matches(element);
}
-PassRefPtr<NodeList> SelectorQuery::queryAll(ContainerNode& rootNode) const
+PassRefPtrWillBeRawPtr<StaticElementList> SelectorQuery::queryAll(ContainerNode& rootNode) const
{
return m_selectors.queryAll(rootNode);
}
-PassRefPtr<Element> SelectorQuery::queryFirst(ContainerNode& rootNode) const
+PassRefPtrWillBeRawPtr<Element> SelectorQuery::queryFirst(ContainerNode& rootNode) const
{
return m_selectors.queryFirst(rootNode);
}
if (it != m_entries.end())
return it->value.get();
- BisonCSSParser parser(CSSParserContext(document, 0));
+ CSSParser parser(CSSParserContext(document, 0));
CSSSelectorList selectorList;
parser.parseSelector(selectors, selectorList);
if (m_entries.size() == maximumSelectorQueryCacheSize)
m_entries.remove(m_entries.begin());
- OwnPtr<SelectorQuery> selectorQuery = adoptPtr(new SelectorQuery(selectorList));
- SelectorQuery* rawSelectorQuery = selectorQuery.get();
- m_entries.add(selectors, selectorQuery.release());
- return rawSelectorQuery;
+ return m_entries.add(selectors, SelectorQuery::adopt(selectorList)).storedValue->value.get();
}
void SelectorQueryCache::invalidate()