2 * Copyright (C) 2011, 2013 Apple Inc. All rights reserved.
3 * Copyright (C) 2014 Samsung Electronics. All rights reserved.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
15 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
16 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
17 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
18 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
19 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
20 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
21 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
22 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
24 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 #include "core/dom/SelectorQuery.h"
30 #include "bindings/v8/ExceptionState.h"
31 #include "core/css/parser/BisonCSSParser.h"
32 #include "core/css/SelectorChecker.h"
33 #include "core/css/SiblingTraversalStrategies.h"
34 #include "core/dom/Document.h"
35 #include "core/dom/ElementTraversal.h"
36 #include "core/dom/Node.h"
37 #include "core/dom/StaticNodeList.h"
38 #include "core/dom/shadow/ElementShadow.h"
39 #include "core/dom/shadow/ShadowRoot.h"
43 struct SingleElementSelectorQueryTrait {
44 typedef Element* OutputType;
45 static const bool shouldOnlyMatchFirstElement = true;
46 ALWAYS_INLINE static void appendElement(OutputType& output, Element& element)
53 struct AllElementsSelectorQueryTrait {
54 typedef WillBeHeapVector<RefPtrWillBeMember<Node> > OutputType;
55 static const bool shouldOnlyMatchFirstElement = false;
56 ALWAYS_INLINE static void appendElement(OutputType& output, Node& element)
58 output.append(&element);
62 enum ClassElementListBehavior { AllElements, OnlyRoots };
64 template <ClassElementListBehavior onlyRoots>
65 class ClassElementList {
68 ClassElementList(ContainerNode& rootNode, const AtomicString& className)
69 : m_className(className)
70 , m_rootNode(&rootNode)
71 , m_currentElement(nextInternal(ElementTraversal::firstWithin(rootNode))) { }
73 bool isEmpty() const { return !m_currentElement; }
77 Element* current = m_currentElement;
80 m_currentElement = nextInternal(ElementTraversal::nextSkippingChildren(*m_currentElement, m_rootNode));
82 m_currentElement = nextInternal(ElementTraversal::next(*m_currentElement, m_rootNode));
87 Element* nextInternal(Element* element)
89 for (; element; element = ElementTraversal::next(*element, m_rootNode)) {
90 if (element->hasClass() && element->classNames().contains(m_className))
96 const AtomicString& m_className;
97 RawPtrWillBeMember<ContainerNode> m_rootNode;
98 RawPtrWillBeMember<Element> m_currentElement;
101 void SelectorDataList::initialize(const CSSSelectorList& selectorList)
103 ASSERT(m_selectors.isEmpty());
105 unsigned selectorCount = 0;
106 for (const CSSSelector* selector = selectorList.first(); selector; selector = CSSSelectorList::next(*selector))
109 m_crossesTreeBoundary = false;
110 m_selectors.reserveInitialCapacity(selectorCount);
112 for (const CSSSelector* selector = selectorList.first(); selector; selector = CSSSelectorList::next(*selector), ++index) {
113 m_selectors.uncheckedAppend(selector);
114 m_crossesTreeBoundary |= selectorList.selectorCrossesTreeScopes(index);
118 inline bool SelectorDataList::selectorMatches(const CSSSelector& selector, Element& element, const ContainerNode& rootNode) const
120 SelectorChecker selectorChecker(element.document(), SelectorChecker::QueryingRules);
121 SelectorChecker::SelectorCheckingContext selectorCheckingContext(selector, &element, SelectorChecker::VisitedMatchDisabled);
122 selectorCheckingContext.behaviorAtBoundary = SelectorChecker::StaysWithinTreeScope;
123 selectorCheckingContext.scope = !rootNode.isDocumentNode() ? &rootNode : 0;
124 return selectorChecker.match(selectorCheckingContext, DOMSiblingTraversalStrategy()) == SelectorChecker::SelectorMatches;
127 bool SelectorDataList::matches(Element& targetElement) const
129 unsigned selectorCount = m_selectors.size();
130 for (unsigned i = 0; i < selectorCount; ++i) {
131 if (selectorMatches(*m_selectors[i], targetElement, targetElement))
138 PassRefPtrWillBeRawPtr<StaticNodeList> SelectorDataList::queryAll(ContainerNode& rootNode) const
140 WillBeHeapVector<RefPtrWillBeMember<Node> > result;
141 execute<AllElementsSelectorQueryTrait>(rootNode, result);
142 return StaticNodeList::adopt(result);
145 PassRefPtrWillBeRawPtr<Element> SelectorDataList::queryFirst(ContainerNode& rootNode) const
147 Element* matchedElement = 0;
148 execute<SingleElementSelectorQueryTrait>(rootNode, matchedElement);
149 return matchedElement;
152 template <typename SelectorQueryTrait>
153 void SelectorDataList::collectElementsByClassName(ContainerNode& rootNode, const AtomicString& className, typename SelectorQueryTrait::OutputType& output) const
155 for (Element* element = ElementTraversal::firstWithin(rootNode); element; element = ElementTraversal::next(*element, &rootNode)) {
156 if (element->hasClass() && element->classNames().contains(className)) {
157 SelectorQueryTrait::appendElement(output, *element);
158 if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
164 template <typename SelectorQueryTrait>
165 void SelectorDataList::collectElementsByTagName(ContainerNode& rootNode, const QualifiedName& tagName, typename SelectorQueryTrait::OutputType& output) const
167 for (Element* element = ElementTraversal::firstWithin(rootNode); element; element = ElementTraversal::next(*element, &rootNode)) {
168 if (SelectorChecker::tagMatches(*element, tagName)) {
169 SelectorQueryTrait::appendElement(output, *element);
170 if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
176 inline bool SelectorDataList::canUseFastQuery(const ContainerNode& rootNode) const
178 return m_selectors.size() == 1 && !m_crossesTreeBoundary && rootNode.inDocument() && !rootNode.document().inQuirksMode();
181 inline bool ancestorHasClassName(ContainerNode& rootNode, const AtomicString& className)
183 if (!rootNode.isElementNode())
186 for (Element* element = &toElement(rootNode); element; element = element->parentElement()) {
187 if (element->hasClass() && element->classNames().contains(className))
194 // If returns true, traversalRoots has the elements that may match the selector query.
196 // If returns false, traversalRoots has the rootNode parameter or descendants of rootNode representing
197 // the subtree for which we can limit the querySelector traversal.
199 // The travseralRoots may be empty, regardless of the returned bool value, if this method finds that the selectors won't
200 // match any element.
201 template <typename SelectorQueryTrait>
202 void SelectorDataList::findTraverseRootsAndExecute(ContainerNode& rootNode, typename SelectorQueryTrait::OutputType& output) const
204 // We need to return the matches in document order. To use id lookup while there is possiblity of multiple matches
205 // we would need to sort the results. For now, just traverse the document in that case.
206 ASSERT(m_selectors.size() == 1);
208 bool isRightmostSelector = true;
209 bool startFromParent = false;
211 for (const CSSSelector* selector = m_selectors[0]; selector; selector = selector->tagHistory()) {
212 if (selector->match() == CSSSelector::Id && !rootNode.document().containsMultipleElementsWithId(selector->value())) {
213 Element* element = rootNode.treeScope().getElementById(selector->value());
214 ContainerNode* adjustedNode = &rootNode;
215 if (element && (isTreeScopeRoot(rootNode) || element->isDescendantOf(&rootNode)))
216 adjustedNode = element;
217 else if (!element || isRightmostSelector)
219 if (isRightmostSelector) {
220 executeForTraverseRoot<SelectorQueryTrait>(*m_selectors[0], adjustedNode, MatchesTraverseRoots, rootNode, output);
224 if (startFromParent && adjustedNode)
225 adjustedNode = adjustedNode->parentNode();
227 executeForTraverseRoot<SelectorQueryTrait>(*m_selectors[0], adjustedNode, DoesNotMatchTraverseRoots, rootNode, output);
231 // If we have both CSSSelector::Id and CSSSelector::Class at the same time, we should use Id
232 // to find traverse root.
233 if (!SelectorQueryTrait::shouldOnlyMatchFirstElement && !startFromParent && selector->match() == CSSSelector::Class) {
234 if (isRightmostSelector) {
235 ClassElementList<AllElements> traverseRoots(rootNode, selector->value());
236 executeForTraverseRoots<SelectorQueryTrait>(*m_selectors[0], traverseRoots, MatchesTraverseRoots, rootNode, output);
239 // Since there exists some ancestor element which has the class name, we need to see all children of rootNode.
240 if (ancestorHasClassName(rootNode, selector->value())) {
241 executeForTraverseRoot<SelectorQueryTrait>(*m_selectors[0], &rootNode, DoesNotMatchTraverseRoots, rootNode, output);
245 ClassElementList<OnlyRoots> traverseRoots(rootNode, selector->value());
246 executeForTraverseRoots<SelectorQueryTrait>(*m_selectors[0], traverseRoots, DoesNotMatchTraverseRoots, rootNode, output);
250 if (selector->relation() == CSSSelector::SubSelector)
252 isRightmostSelector = false;
253 if (selector->relation() == CSSSelector::DirectAdjacent || selector->relation() == CSSSelector::IndirectAdjacent)
254 startFromParent = true;
256 startFromParent = false;
259 executeForTraverseRoot<SelectorQueryTrait>(*m_selectors[0], &rootNode, DoesNotMatchTraverseRoots, rootNode, output);
262 template <typename SelectorQueryTrait>
263 void SelectorDataList::executeForTraverseRoot(const CSSSelector& selector, ContainerNode* traverseRoot, MatchTraverseRootState matchTraverseRoot, ContainerNode& rootNode, typename SelectorQueryTrait::OutputType& output) const
268 if (matchTraverseRoot) {
269 if (selectorMatches(selector, toElement(*traverseRoot), rootNode))
270 SelectorQueryTrait::appendElement(output, toElement(*traverseRoot));
274 for (Element* element = ElementTraversal::firstWithin(*traverseRoot); element; element = ElementTraversal::next(*element, traverseRoot)) {
275 if (selectorMatches(selector, *element, rootNode)) {
276 SelectorQueryTrait::appendElement(output, *element);
277 if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
283 template <typename SelectorQueryTrait, typename SimpleElementListType>
284 void SelectorDataList::executeForTraverseRoots(const CSSSelector& selector, SimpleElementListType& traverseRoots, MatchTraverseRootState matchTraverseRoots, ContainerNode& rootNode, typename SelectorQueryTrait::OutputType& output) const
286 if (traverseRoots.isEmpty())
289 if (matchTraverseRoots) {
290 while (!traverseRoots.isEmpty()) {
291 Element& element = *traverseRoots.next();
292 if (selectorMatches(selector, element, rootNode)) {
293 SelectorQueryTrait::appendElement(output, element);
294 if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
301 while (!traverseRoots.isEmpty()) {
302 Element& traverseRoot = *traverseRoots.next();
303 for (Element* element = ElementTraversal::firstWithin(traverseRoot); element; element = ElementTraversal::next(*element, &traverseRoot)) {
304 if (selectorMatches(selector, *element, rootNode)) {
305 SelectorQueryTrait::appendElement(output, *element);
306 if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
313 template <typename SelectorQueryTrait>
314 bool SelectorDataList::selectorListMatches(ContainerNode& rootNode, Element& element, typename SelectorQueryTrait::OutputType& output) const
316 for (unsigned i = 0; i < m_selectors.size(); ++i) {
317 if (selectorMatches(*m_selectors[i], element, rootNode)) {
318 SelectorQueryTrait::appendElement(output, element);
325 template <typename SelectorQueryTrait>
326 void SelectorDataList::executeSlow(ContainerNode& rootNode, typename SelectorQueryTrait::OutputType& output) const
328 for (Element* element = ElementTraversal::firstWithin(rootNode); element; element = ElementTraversal::next(*element, &rootNode)) {
329 if (selectorListMatches<SelectorQueryTrait>(rootNode, *element, output) && SelectorQueryTrait::shouldOnlyMatchFirstElement)
334 // FIXME: Move the following helper functions, authorShadowRootOf, firstWithinTraversingShadowTree,
335 // nextTraversingShadowTree to the best place, e.g. NodeTraversal.
336 static ShadowRoot* authorShadowRootOf(const ContainerNode& node)
338 if (!node.isElementNode() || !isShadowHost(&node))
341 ElementShadow* shadow = toElement(node).shadow();
343 for (ShadowRoot* shadowRoot = shadow->oldestShadowRoot(); shadowRoot; shadowRoot = shadowRoot->youngerShadowRoot()) {
344 if (shadowRoot->type() == ShadowRoot::AuthorShadowRoot)
350 static ContainerNode* firstWithinTraversingShadowTree(const ContainerNode& rootNode)
352 if (ShadowRoot* shadowRoot = authorShadowRootOf(rootNode))
354 return ElementTraversal::firstWithin(rootNode);
357 static ContainerNode* nextTraversingShadowTree(const ContainerNode& node, const ContainerNode* rootNode)
359 if (ShadowRoot* shadowRoot = authorShadowRootOf(node))
362 const ContainerNode* current = &node;
364 if (Element* next = ElementTraversal::next(*current, rootNode))
367 if (!current->isInShadowTree())
370 ShadowRoot* shadowRoot = current->containingShadowRoot();
371 if (shadowRoot == rootNode)
373 if (ShadowRoot* youngerShadowRoot = shadowRoot->youngerShadowRoot()) {
374 // Should not obtain any elements in user-agent shadow root.
375 ASSERT(youngerShadowRoot->type() == ShadowRoot::AuthorShadowRoot);
376 return youngerShadowRoot;
379 current = shadowRoot->host();
384 template <typename SelectorQueryTrait>
385 void SelectorDataList::executeSlowTraversingShadowTree(ContainerNode& rootNode, typename SelectorQueryTrait::OutputType& output) const
387 for (ContainerNode* node = firstWithinTraversingShadowTree(rootNode); node; node = nextTraversingShadowTree(*node, &rootNode)) {
388 if (!node->isElementNode())
390 Element* element = toElement(node);
391 if (selectorListMatches<SelectorQueryTrait>(rootNode, *element, output) && SelectorQueryTrait::shouldOnlyMatchFirstElement)
396 const CSSSelector* SelectorDataList::selectorForIdLookup(const CSSSelector& firstSelector) const
398 for (const CSSSelector* selector = &firstSelector; selector; selector = selector->tagHistory()) {
399 if (selector->match() == CSSSelector::Id)
401 if (selector->relation() != CSSSelector::SubSelector)
407 template <typename SelectorQueryTrait>
408 void SelectorDataList::execute(ContainerNode& rootNode, typename SelectorQueryTrait::OutputType& output) const
410 if (!canUseFastQuery(rootNode)) {
411 if (m_crossesTreeBoundary) {
412 rootNode.document().updateDistributionForNodeIfNeeded(&rootNode);
413 executeSlowTraversingShadowTree<SelectorQueryTrait>(rootNode, output);
415 executeSlow<SelectorQueryTrait>(rootNode, output);
420 ASSERT(m_selectors.size() == 1);
422 const CSSSelector& selector = *m_selectors[0];
423 const CSSSelector& firstSelector = selector;
425 // Fast path for querySelector*('#id'), querySelector*('tag#id').
426 if (const CSSSelector* idSelector = selectorForIdLookup(firstSelector)) {
427 const AtomicString& idToMatch = idSelector->value();
428 if (rootNode.treeScope().containsMultipleElementsWithId(idToMatch)) {
429 const Vector<Element*>& elements = rootNode.treeScope().getAllElementsById(idToMatch);
430 size_t count = elements.size();
431 for (size_t i = 0; i < count; ++i) {
432 Element& element = *elements[i];
433 if (!(isTreeScopeRoot(rootNode) || element.isDescendantOf(&rootNode)))
435 if (selectorMatches(selector, element, rootNode)) {
436 SelectorQueryTrait::appendElement(output, element);
437 if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
443 Element* element = rootNode.treeScope().getElementById(idToMatch);
444 if (!element || !(isTreeScopeRoot(rootNode) || element->isDescendantOf(&rootNode)))
446 if (selectorMatches(selector, *element, rootNode))
447 SelectorQueryTrait::appendElement(output, *element);
451 if (!firstSelector.tagHistory()) {
452 // Fast path for querySelector*('.foo'), and querySelector*('div').
453 switch (firstSelector.match()) {
454 case CSSSelector::Class:
455 collectElementsByClassName<SelectorQueryTrait>(rootNode, firstSelector.value(), output);
457 case CSSSelector::Tag:
458 collectElementsByTagName<SelectorQueryTrait>(rootNode, firstSelector.tagQName(), output);
461 break; // If we need another fast path, add here.
465 findTraverseRootsAndExecute<SelectorQueryTrait>(rootNode, output);
468 PassOwnPtr<SelectorQuery> SelectorQuery::adopt(CSSSelectorList& selectorList)
470 return adoptPtr(new SelectorQuery(selectorList));
473 SelectorQuery::SelectorQuery(CSSSelectorList& selectorList)
475 m_selectorList.adopt(selectorList);
476 m_selectors.initialize(m_selectorList);
479 bool SelectorQuery::matches(Element& element) const
481 return m_selectors.matches(element);
484 PassRefPtrWillBeRawPtr<StaticNodeList> SelectorQuery::queryAll(ContainerNode& rootNode) const
486 return m_selectors.queryAll(rootNode);
489 PassRefPtrWillBeRawPtr<Element> SelectorQuery::queryFirst(ContainerNode& rootNode) const
491 return m_selectors.queryFirst(rootNode);
494 SelectorQuery* SelectorQueryCache::add(const AtomicString& selectors, const Document& document, ExceptionState& exceptionState)
496 HashMap<AtomicString, OwnPtr<SelectorQuery> >::iterator it = m_entries.find(selectors);
497 if (it != m_entries.end())
498 return it->value.get();
500 BisonCSSParser parser(CSSParserContext(document, 0));
501 CSSSelectorList selectorList;
502 parser.parseSelector(selectors, selectorList);
504 if (!selectorList.first()) {
505 exceptionState.throwDOMException(SyntaxError, "'" + selectors + "' is not a valid selector.");
509 // throw a NamespaceError if the selector includes any namespace prefixes.
510 if (selectorList.selectorsNeedNamespaceResolution()) {
511 exceptionState.throwDOMException(NamespaceError, "'" + selectors + "' contains namespaces, which are not supported.");
515 const unsigned maximumSelectorQueryCacheSize = 256;
516 if (m_entries.size() == maximumSelectorQueryCacheSize)
517 m_entries.remove(m_entries.begin());
519 return m_entries.add(selectors, SelectorQuery::adopt(selectorList)).storedValue->value.get();
522 void SelectorQueryCache::invalidate()