1 /* 2 * Copyright (C) 2011, 2013 Apple Inc. All rights reserved. 3 * Copyright (C) 2014 Samsung Electronics. All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 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. 14 * 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. 25 */ 26 27 #include "config.h" 28 #include "core/dom/SelectorQuery.h" 29 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" 40 41 namespace WebCore { 42 43 struct SingleElementSelectorQueryTrait { 44 typedef Element* OutputType; 45 static const bool shouldOnlyMatchFirstElement = true; 46 ALWAYS_INLINE static void appendElement(OutputType& output, Element& element) 47 { 48 ASSERT(!output); 49 output = &element; 50 } 51 }; 52 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) 57 { 58 output.append(&element); 59 } 60 }; 61 62 enum ClassElementListBehavior { AllElements, OnlyRoots }; 63 64 template <ClassElementListBehavior onlyRoots> 65 class ClassElementList { 66 STACK_ALLOCATED(); 67 public: 68 ClassElementList(ContainerNode& rootNode, const AtomicString& className) 69 : m_className(className) 70 , m_rootNode(&rootNode) 71 , m_currentElement(nextInternal(ElementTraversal::firstWithin(rootNode))) { } 72 73 bool isEmpty() const { return !m_currentElement; } 74 75 Element* next() 76 { 77 Element* current = m_currentElement; 78 ASSERT(current); 79 if (onlyRoots) 80 m_currentElement = nextInternal(ElementTraversal::nextSkippingChildren(*m_currentElement, m_rootNode)); 81 else 82 m_currentElement = nextInternal(ElementTraversal::next(*m_currentElement, m_rootNode)); 83 return current; 84 } 85 86 private: 87 Element* nextInternal(Element* element) 88 { 89 for (; element; element = ElementTraversal::next(*element, m_rootNode)) { 90 if (element->hasClass() && element->classNames().contains(m_className)) 91 return element; 92 } 93 return 0; 94 } 95 96 const AtomicString& m_className; 97 RawPtrWillBeMember<ContainerNode> m_rootNode; 98 RawPtrWillBeMember<Element> m_currentElement; 99 }; 100 101 void SelectorDataList::initialize(const CSSSelectorList& selectorList) 102 { 103 ASSERT(m_selectors.isEmpty()); 104 105 unsigned selectorCount = 0; 106 for (const CSSSelector* selector = selectorList.first(); selector; selector = CSSSelectorList::next(*selector)) 107 selectorCount++; 108 109 m_crossesTreeBoundary = false; 110 m_selectors.reserveInitialCapacity(selectorCount); 111 unsigned index = 0; 112 for (const CSSSelector* selector = selectorList.first(); selector; selector = CSSSelectorList::next(*selector), ++index) { 113 m_selectors.uncheckedAppend(selector); 114 m_crossesTreeBoundary |= selectorList.selectorCrossesTreeScopes(index); 115 } 116 } 117 118 inline bool SelectorDataList::selectorMatches(const CSSSelector& selector, Element& element, const ContainerNode& rootNode) const 119 { 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 if (selectorCheckingContext.scope) 125 selectorCheckingContext.behaviorAtBoundary = static_cast<SelectorChecker::BehaviorAtBoundary>(SelectorChecker::StaysWithinTreeScope | SelectorChecker::ScopeContainsLastMatchedElement); 126 return selectorChecker.match(selectorCheckingContext, DOMSiblingTraversalStrategy()) == SelectorChecker::SelectorMatches; 127 } 128 129 bool SelectorDataList::matches(Element& targetElement) const 130 { 131 unsigned selectorCount = m_selectors.size(); 132 for (unsigned i = 0; i < selectorCount; ++i) { 133 if (selectorMatches(*m_selectors[i], targetElement, targetElement)) 134 return true; 135 } 136 137 return false; 138 } 139 140 PassRefPtrWillBeRawPtr<StaticNodeList> SelectorDataList::queryAll(ContainerNode& rootNode) const 141 { 142 WillBeHeapVector<RefPtrWillBeMember<Node> > result; 143 execute<AllElementsSelectorQueryTrait>(rootNode, result); 144 return StaticNodeList::adopt(result); 145 } 146 147 PassRefPtrWillBeRawPtr<Element> SelectorDataList::queryFirst(ContainerNode& rootNode) const 148 { 149 Element* matchedElement = 0; 150 execute<SingleElementSelectorQueryTrait>(rootNode, matchedElement); 151 return matchedElement; 152 } 153 154 template <typename SelectorQueryTrait> 155 void SelectorDataList::collectElementsByClassName(ContainerNode& rootNode, const AtomicString& className, typename SelectorQueryTrait::OutputType& output) const 156 { 157 for (Element* element = ElementTraversal::firstWithin(rootNode); element; element = ElementTraversal::next(*element, &rootNode)) { 158 if (element->hasClass() && element->classNames().contains(className)) { 159 SelectorQueryTrait::appendElement(output, *element); 160 if (SelectorQueryTrait::shouldOnlyMatchFirstElement) 161 return; 162 } 163 } 164 } 165 166 template <typename SelectorQueryTrait> 167 void SelectorDataList::collectElementsByTagName(ContainerNode& rootNode, const QualifiedName& tagName, typename SelectorQueryTrait::OutputType& output) const 168 { 169 for (Element* element = ElementTraversal::firstWithin(rootNode); element; element = ElementTraversal::next(*element, &rootNode)) { 170 if (SelectorChecker::tagMatches(*element, tagName)) { 171 SelectorQueryTrait::appendElement(output, *element); 172 if (SelectorQueryTrait::shouldOnlyMatchFirstElement) 173 return; 174 } 175 } 176 } 177 178 inline bool SelectorDataList::canUseFastQuery(const ContainerNode& rootNode) const 179 { 180 return m_selectors.size() == 1 && !m_crossesTreeBoundary && rootNode.inDocument() && !rootNode.document().inQuirksMode(); 181 } 182 183 inline bool ancestorHasClassName(ContainerNode& rootNode, const AtomicString& className) 184 { 185 if (!rootNode.isElementNode()) 186 return false; 187 188 for (Element* element = &toElement(rootNode); element; element = element->parentElement()) { 189 if (element->hasClass() && element->classNames().contains(className)) 190 return true; 191 } 192 return false; 193 } 194 195 196 // If returns true, traversalRoots has the elements that may match the selector query. 197 // 198 // If returns false, traversalRoots has the rootNode parameter or descendants of rootNode representing 199 // the subtree for which we can limit the querySelector traversal. 200 // 201 // The travseralRoots may be empty, regardless of the returned bool value, if this method finds that the selectors won't 202 // match any element. 203 template <typename SelectorQueryTrait> 204 void SelectorDataList::findTraverseRootsAndExecute(ContainerNode& rootNode, typename SelectorQueryTrait::OutputType& output) const 205 { 206 // We need to return the matches in document order. To use id lookup while there is possiblity of multiple matches 207 // we would need to sort the results. For now, just traverse the document in that case. 208 ASSERT(m_selectors.size() == 1); 209 210 bool isRightmostSelector = true; 211 bool startFromParent = false; 212 213 for (const CSSSelector* selector = m_selectors[0]; selector; selector = selector->tagHistory()) { 214 if (selector->match() == CSSSelector::Id && !rootNode.document().containsMultipleElementsWithId(selector->value())) { 215 Element* element = rootNode.treeScope().getElementById(selector->value()); 216 ContainerNode* adjustedNode = &rootNode; 217 if (element && (isTreeScopeRoot(rootNode) || element->isDescendantOf(&rootNode))) 218 adjustedNode = element; 219 else if (!element || isRightmostSelector) 220 adjustedNode = 0; 221 if (isRightmostSelector) { 222 executeForTraverseRoot<SelectorQueryTrait>(*m_selectors[0], adjustedNode, MatchesTraverseRoots, rootNode, output); 223 return; 224 } 225 226 if (startFromParent && adjustedNode) 227 adjustedNode = adjustedNode->parentNode(); 228 229 executeForTraverseRoot<SelectorQueryTrait>(*m_selectors[0], adjustedNode, DoesNotMatchTraverseRoots, rootNode, output); 230 return; 231 } 232 233 // If we have both CSSSelector::Id and CSSSelector::Class at the same time, we should use Id 234 // to find traverse root. 235 if (!SelectorQueryTrait::shouldOnlyMatchFirstElement && !startFromParent && selector->match() == CSSSelector::Class) { 236 if (isRightmostSelector) { 237 ClassElementList<AllElements> traverseRoots(rootNode, selector->value()); 238 executeForTraverseRoots<SelectorQueryTrait>(*m_selectors[0], traverseRoots, MatchesTraverseRoots, rootNode, output); 239 return; 240 } 241 // Since there exists some ancestor element which has the class name, we need to see all children of rootNode. 242 if (ancestorHasClassName(rootNode, selector->value())) { 243 executeForTraverseRoot<SelectorQueryTrait>(*m_selectors[0], &rootNode, DoesNotMatchTraverseRoots, rootNode, output); 244 return; 245 } 246 247 ClassElementList<OnlyRoots> traverseRoots(rootNode, selector->value()); 248 executeForTraverseRoots<SelectorQueryTrait>(*m_selectors[0], traverseRoots, DoesNotMatchTraverseRoots, rootNode, output); 249 return; 250 } 251 252 if (selector->relation() == CSSSelector::SubSelector) 253 continue; 254 isRightmostSelector = false; 255 if (selector->relation() == CSSSelector::DirectAdjacent || selector->relation() == CSSSelector::IndirectAdjacent) 256 startFromParent = true; 257 else 258 startFromParent = false; 259 } 260 261 executeForTraverseRoot<SelectorQueryTrait>(*m_selectors[0], &rootNode, DoesNotMatchTraverseRoots, rootNode, output); 262 } 263 264 template <typename SelectorQueryTrait> 265 void SelectorDataList::executeForTraverseRoot(const CSSSelector& selector, ContainerNode* traverseRoot, MatchTraverseRootState matchTraverseRoot, ContainerNode& rootNode, typename SelectorQueryTrait::OutputType& output) const 266 { 267 if (!traverseRoot) 268 return; 269 270 if (matchTraverseRoot) { 271 if (selectorMatches(selector, toElement(*traverseRoot), rootNode)) 272 SelectorQueryTrait::appendElement(output, toElement(*traverseRoot)); 273 return; 274 } 275 276 for (Element* element = ElementTraversal::firstWithin(*traverseRoot); element; element = ElementTraversal::next(*element, traverseRoot)) { 277 if (selectorMatches(selector, *element, rootNode)) { 278 SelectorQueryTrait::appendElement(output, *element); 279 if (SelectorQueryTrait::shouldOnlyMatchFirstElement) 280 return; 281 } 282 } 283 } 284 285 template <typename SelectorQueryTrait, typename SimpleElementListType> 286 void SelectorDataList::executeForTraverseRoots(const CSSSelector& selector, SimpleElementListType& traverseRoots, MatchTraverseRootState matchTraverseRoots, ContainerNode& rootNode, typename SelectorQueryTrait::OutputType& output) const 287 { 288 if (traverseRoots.isEmpty()) 289 return; 290 291 if (matchTraverseRoots) { 292 while (!traverseRoots.isEmpty()) { 293 Element& element = *traverseRoots.next(); 294 if (selectorMatches(selector, element, rootNode)) { 295 SelectorQueryTrait::appendElement(output, element); 296 if (SelectorQueryTrait::shouldOnlyMatchFirstElement) 297 return; 298 } 299 } 300 return; 301 } 302 303 while (!traverseRoots.isEmpty()) { 304 Element& traverseRoot = *traverseRoots.next(); 305 for (Element* element = ElementTraversal::firstWithin(traverseRoot); element; element = ElementTraversal::next(*element, &traverseRoot)) { 306 if (selectorMatches(selector, *element, rootNode)) { 307 SelectorQueryTrait::appendElement(output, *element); 308 if (SelectorQueryTrait::shouldOnlyMatchFirstElement) 309 return; 310 } 311 } 312 } 313 } 314 315 template <typename SelectorQueryTrait> 316 bool SelectorDataList::selectorListMatches(ContainerNode& rootNode, Element& element, typename SelectorQueryTrait::OutputType& output) const 317 { 318 for (unsigned i = 0; i < m_selectors.size(); ++i) { 319 if (selectorMatches(*m_selectors[i], element, rootNode)) { 320 SelectorQueryTrait::appendElement(output, element); 321 return true; 322 } 323 } 324 return false; 325 } 326 327 template <typename SelectorQueryTrait> 328 void SelectorDataList::executeSlow(ContainerNode& rootNode, typename SelectorQueryTrait::OutputType& output) const 329 { 330 for (Element* element = ElementTraversal::firstWithin(rootNode); element; element = ElementTraversal::next(*element, &rootNode)) { 331 if (selectorListMatches<SelectorQueryTrait>(rootNode, *element, output) && SelectorQueryTrait::shouldOnlyMatchFirstElement) 332 return; 333 } 334 } 335 336 // FIXME: Move the following helper functions, authorShadowRootOf, firstWithinTraversingShadowTree, 337 // nextTraversingShadowTree to the best place, e.g. NodeTraversal. 338 static ShadowRoot* authorShadowRootOf(const ContainerNode& node) 339 { 340 if (!node.isElementNode() || !isShadowHost(&node)) 341 return 0; 342 343 ElementShadow* shadow = toElement(node).shadow(); 344 ASSERT(shadow); 345 for (ShadowRoot* shadowRoot = shadow->oldestShadowRoot(); shadowRoot; shadowRoot = shadowRoot->youngerShadowRoot()) { 346 if (shadowRoot->type() == ShadowRoot::AuthorShadowRoot) 347 return shadowRoot; 348 } 349 return 0; 350 } 351 352 static ContainerNode* firstWithinTraversingShadowTree(const ContainerNode& rootNode) 353 { 354 if (ShadowRoot* shadowRoot = authorShadowRootOf(rootNode)) 355 return shadowRoot; 356 return ElementTraversal::firstWithin(rootNode); 357 } 358 359 static ContainerNode* nextTraversingShadowTree(const ContainerNode& node, const ContainerNode* rootNode) 360 { 361 if (ShadowRoot* shadowRoot = authorShadowRootOf(node)) 362 return shadowRoot; 363 364 const ContainerNode* current = &node; 365 while (current) { 366 if (Element* next = ElementTraversal::next(*current, rootNode)) 367 return next; 368 369 if (!current->isInShadowTree()) 370 return 0; 371 372 ShadowRoot* shadowRoot = current->containingShadowRoot(); 373 if (shadowRoot == rootNode) 374 return 0; 375 if (ShadowRoot* youngerShadowRoot = shadowRoot->youngerShadowRoot()) { 376 // Should not obtain any elements in user-agent shadow root. 377 ASSERT(youngerShadowRoot->type() == ShadowRoot::AuthorShadowRoot); 378 return youngerShadowRoot; 379 } 380 381 current = shadowRoot->host(); 382 } 383 return 0; 384 } 385 386 template <typename SelectorQueryTrait> 387 void SelectorDataList::executeSlowTraversingShadowTree(ContainerNode& rootNode, typename SelectorQueryTrait::OutputType& output) const 388 { 389 for (ContainerNode* node = firstWithinTraversingShadowTree(rootNode); node; node = nextTraversingShadowTree(*node, &rootNode)) { 390 if (!node->isElementNode()) 391 continue; 392 Element* element = toElement(node); 393 if (selectorListMatches<SelectorQueryTrait>(rootNode, *element, output) && SelectorQueryTrait::shouldOnlyMatchFirstElement) 394 return; 395 } 396 } 397 398 const CSSSelector* SelectorDataList::selectorForIdLookup(const CSSSelector& firstSelector) const 399 { 400 for (const CSSSelector* selector = &firstSelector; selector; selector = selector->tagHistory()) { 401 if (selector->match() == CSSSelector::Id) 402 return selector; 403 if (selector->relation() != CSSSelector::SubSelector) 404 break; 405 } 406 return 0; 407 } 408 409 template <typename SelectorQueryTrait> 410 void SelectorDataList::execute(ContainerNode& rootNode, typename SelectorQueryTrait::OutputType& output) const 411 { 412 if (!canUseFastQuery(rootNode)) { 413 if (m_crossesTreeBoundary) { 414 rootNode.document().updateDistributionForNodeIfNeeded(&rootNode); 415 executeSlowTraversingShadowTree<SelectorQueryTrait>(rootNode, output); 416 } else { 417 executeSlow<SelectorQueryTrait>(rootNode, output); 418 } 419 return; 420 } 421 422 ASSERT(m_selectors.size() == 1); 423 424 const CSSSelector& selector = *m_selectors[0]; 425 const CSSSelector& firstSelector = selector; 426 427 // Fast path for querySelector*('#id'), querySelector*('tag#id'). 428 if (const CSSSelector* idSelector = selectorForIdLookup(firstSelector)) { 429 const AtomicString& idToMatch = idSelector->value(); 430 if (rootNode.treeScope().containsMultipleElementsWithId(idToMatch)) { 431 const Vector<Element*>& elements = rootNode.treeScope().getAllElementsById(idToMatch); 432 size_t count = elements.size(); 433 for (size_t i = 0; i < count; ++i) { 434 Element& element = *elements[i]; 435 if (!(isTreeScopeRoot(rootNode) || element.isDescendantOf(&rootNode))) 436 continue; 437 if (selectorMatches(selector, element, rootNode)) { 438 SelectorQueryTrait::appendElement(output, element); 439 if (SelectorQueryTrait::shouldOnlyMatchFirstElement) 440 return; 441 } 442 } 443 return; 444 } 445 Element* element = rootNode.treeScope().getElementById(idToMatch); 446 if (!element || !(isTreeScopeRoot(rootNode) || element->isDescendantOf(&rootNode))) 447 return; 448 if (selectorMatches(selector, *element, rootNode)) 449 SelectorQueryTrait::appendElement(output, *element); 450 return; 451 } 452 453 if (!firstSelector.tagHistory()) { 454 // Fast path for querySelector*('.foo'), and querySelector*('div'). 455 switch (firstSelector.match()) { 456 case CSSSelector::Class: 457 collectElementsByClassName<SelectorQueryTrait>(rootNode, firstSelector.value(), output); 458 return; 459 case CSSSelector::Tag: 460 collectElementsByTagName<SelectorQueryTrait>(rootNode, firstSelector.tagQName(), output); 461 return; 462 default: 463 break; // If we need another fast path, add here. 464 } 465 } 466 467 findTraverseRootsAndExecute<SelectorQueryTrait>(rootNode, output); 468 } 469 470 PassOwnPtr<SelectorQuery> SelectorQuery::adopt(CSSSelectorList& selectorList) 471 { 472 return adoptPtr(new SelectorQuery(selectorList)); 473 } 474 475 SelectorQuery::SelectorQuery(CSSSelectorList& selectorList) 476 { 477 m_selectorList.adopt(selectorList); 478 m_selectors.initialize(m_selectorList); 479 } 480 481 bool SelectorQuery::matches(Element& element) const 482 { 483 return m_selectors.matches(element); 484 } 485 486 PassRefPtrWillBeRawPtr<StaticNodeList> SelectorQuery::queryAll(ContainerNode& rootNode) const 487 { 488 return m_selectors.queryAll(rootNode); 489 } 490 491 PassRefPtrWillBeRawPtr<Element> SelectorQuery::queryFirst(ContainerNode& rootNode) const 492 { 493 return m_selectors.queryFirst(rootNode); 494 } 495 496 SelectorQuery* SelectorQueryCache::add(const AtomicString& selectors, const Document& document, ExceptionState& exceptionState) 497 { 498 HashMap<AtomicString, OwnPtr<SelectorQuery> >::iterator it = m_entries.find(selectors); 499 if (it != m_entries.end()) 500 return it->value.get(); 501 502 BisonCSSParser parser(CSSParserContext(document, 0)); 503 CSSSelectorList selectorList; 504 parser.parseSelector(selectors, selectorList); 505 506 if (!selectorList.first()) { 507 exceptionState.throwDOMException(SyntaxError, "'" + selectors + "' is not a valid selector."); 508 return 0; 509 } 510 511 // throw a NamespaceError if the selector includes any namespace prefixes. 512 if (selectorList.selectorsNeedNamespaceResolution()) { 513 exceptionState.throwDOMException(NamespaceError, "'" + selectors + "' contains namespaces, which are not supported."); 514 return 0; 515 } 516 517 const unsigned maximumSelectorQueryCacheSize = 256; 518 if (m_entries.size() == maximumSelectorQueryCacheSize) 519 m_entries.remove(m_entries.begin()); 520 521 return m_entries.add(selectors, SelectorQuery::adopt(selectorList)).storedValue->value.get(); 522 } 523 524 void SelectorQueryCache::invalidate() 525 { 526 m_entries.clear(); 527 } 528 529 } 530