1/* 2 * Copyright (C) 2011, 2013, 2014 Apple Inc. All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions 6 * are met: 7 * 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 14 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY 15 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 16 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 17 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY 18 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 19 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 20 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 21 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 23 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 24 */ 25 26#include "config.h" 27#include "SelectorQuery.h" 28 29#include "CSSParser.h" 30#include "ElementDescendantIterator.h" 31#include "SelectorChecker.h" 32#include "SelectorCheckerFastPath.h" 33#include "StaticNodeList.h" 34#include "StyledElement.h" 35 36namespace WebCore { 37 38#if !ASSERT_DISABLED 39static bool isSingleTagNameSelector(const CSSSelector& selector) 40{ 41 return selector.isLastInTagHistory() && selector.m_match == CSSSelector::Tag; 42} 43 44static bool isSingleClassNameSelector(const CSSSelector& selector) 45{ 46 return selector.isLastInTagHistory() && selector.m_match == CSSSelector::Class; 47} 48#endif 49 50enum class IdMatchingType : uint8_t { 51 None, 52 Rightmost, 53 Filter 54}; 55 56static IdMatchingType findIdMatchingType(const CSSSelector& firstSelector) 57{ 58 bool inRightmost = true; 59 for (const CSSSelector* selector = &firstSelector; selector; selector = selector->tagHistory()) { 60 if (selector->m_match == CSSSelector::Id) { 61 if (inRightmost) 62 return IdMatchingType::Rightmost; 63 return IdMatchingType::Filter; 64 } 65 if (selector->relation() != CSSSelector::SubSelector) 66 inRightmost = false; 67 } 68 return IdMatchingType::None; 69} 70 71SelectorDataList::SelectorDataList(const CSSSelectorList& selectorList) 72{ 73 unsigned selectorCount = 0; 74 for (const CSSSelector* selector = selectorList.first(); selector; selector = CSSSelectorList::next(selector)) 75 selectorCount++; 76 77 m_selectors.reserveInitialCapacity(selectorCount); 78 for (const CSSSelector* selector = selectorList.first(); selector; selector = CSSSelectorList::next(selector)) 79 m_selectors.uncheckedAppend(SelectorData(selector, SelectorCheckerFastPath::canUse(selector))); 80 81 if (selectorCount == 1) { 82 const CSSSelector& selector = *m_selectors.first().selector; 83 if (selector.isLastInTagHistory()) { 84 switch (selector.m_match) { 85 case CSSSelector::Tag: 86 m_matchType = TagNameMatch; 87 break; 88 case CSSSelector::Class: 89 m_matchType = ClassNameMatch; 90 break; 91 case CSSSelector::Id: 92 m_matchType = RightMostWithIdMatch; 93 break; 94 default: 95 m_matchType = CompilableSingle; 96 break; 97 } 98 } else { 99 switch (findIdMatchingType(selector)) { 100 case IdMatchingType::None: 101 m_matchType = CompilableSingle; 102 break; 103 case IdMatchingType::Rightmost: 104 m_matchType = RightMostWithIdMatch; 105 break; 106 case IdMatchingType::Filter: 107 m_matchType = CompilableSingleWithRootFilter; 108 break; 109 } 110 } 111 } else 112 m_matchType = MultipleSelectorMatch; 113} 114 115inline bool SelectorDataList::selectorMatches(const SelectorData& selectorData, Element& element, const ContainerNode& rootNode) const 116{ 117 if (selectorData.isFastCheckable && !element.isSVGElement()) { 118 SelectorCheckerFastPath selectorCheckerFastPath(selectorData.selector, &element); 119 if (!selectorCheckerFastPath.matchesRightmostSelector(SelectorChecker::VisitedMatchDisabled)) 120 return false; 121 return selectorCheckerFastPath.matches(); 122 } 123 124 SelectorChecker selectorChecker(element.document(), SelectorChecker::Mode::QueryingRules); 125 SelectorChecker::SelectorCheckingContext selectorCheckingContext(selectorData.selector, &element, SelectorChecker::VisitedMatchDisabled); 126 selectorCheckingContext.scope = rootNode.isDocumentNode() ? nullptr : &rootNode; 127 return selectorChecker.match(selectorCheckingContext); 128} 129 130bool SelectorDataList::matches(Element& targetElement) const 131{ 132 unsigned selectorCount = m_selectors.size(); 133 for (unsigned i = 0; i < selectorCount; ++i) { 134 if (selectorMatches(m_selectors[i], targetElement, targetElement)) 135 return true; 136 } 137 return false; 138} 139 140struct AllElementExtractorSelectorQueryTrait { 141 typedef Vector<Ref<Element>> OutputType; 142 static const bool shouldOnlyMatchFirstElement = false; 143 ALWAYS_INLINE static void appendOutputForElement(OutputType& output, Element* element) { ASSERT(element); output.append(*element); } 144}; 145 146RefPtr<NodeList> SelectorDataList::queryAll(ContainerNode& rootNode) const 147{ 148 Vector<Ref<Element>> result; 149 execute<AllElementExtractorSelectorQueryTrait>(rootNode, result); 150 return StaticElementList::adopt(result); 151} 152 153struct SingleElementExtractorSelectorQueryTrait { 154 typedef Element* OutputType; 155 static const bool shouldOnlyMatchFirstElement = true; 156 ALWAYS_INLINE static void appendOutputForElement(OutputType& output, Element* element) 157 { 158 ASSERT(element); 159 ASSERT(!output); 160 output = element; 161 } 162}; 163 164Element* SelectorDataList::queryFirst(ContainerNode& rootNode) const 165{ 166 Element* result = nullptr; 167 execute<SingleElementExtractorSelectorQueryTrait>(rootNode, result); 168 return result; 169} 170 171static const CSSSelector* selectorForIdLookup(const ContainerNode& rootNode, const CSSSelector& firstSelector) 172{ 173 if (!rootNode.inDocument()) 174 return nullptr; 175 if (rootNode.document().inQuirksMode()) 176 return nullptr; 177 178 for (const CSSSelector* selector = &firstSelector; selector; selector = selector->tagHistory()) { 179 if (selector->m_match == CSSSelector::Id) 180 return selector; 181 if (selector->relation() != CSSSelector::SubSelector) 182 break; 183 } 184 185 return nullptr; 186} 187 188static inline bool isTreeScopeRoot(const ContainerNode& node) 189{ 190 return node.isDocumentNode() || node.isShadowRoot(); 191} 192 193template <typename SelectorQueryTrait> 194ALWAYS_INLINE void SelectorDataList::executeFastPathForIdSelector(const ContainerNode& rootNode, const SelectorData& selectorData, const CSSSelector* idSelector, typename SelectorQueryTrait::OutputType& output) const 195{ 196 ASSERT(m_selectors.size() == 1); 197 ASSERT(idSelector); 198 199 const AtomicString& idToMatch = idSelector->value(); 200 if (UNLIKELY(rootNode.treeScope().containsMultipleElementsWithId(idToMatch))) { 201 const Vector<Element*>* elements = rootNode.treeScope().getAllElementsById(idToMatch); 202 ASSERT(elements); 203 size_t count = elements->size(); 204 bool rootNodeIsTreeScopeRoot = isTreeScopeRoot(rootNode); 205 for (size_t i = 0; i < count; ++i) { 206 Element& element = *elements->at(i); 207 if ((rootNodeIsTreeScopeRoot || element.isDescendantOf(&rootNode)) && selectorMatches(selectorData, element, rootNode)) { 208 SelectorQueryTrait::appendOutputForElement(output, &element); 209 if (SelectorQueryTrait::shouldOnlyMatchFirstElement) 210 return; 211 } 212 } 213 return; 214 } 215 216 Element* element = rootNode.treeScope().getElementById(idToMatch); 217 if (!element || !(isTreeScopeRoot(rootNode) || element->isDescendantOf(&rootNode))) 218 return; 219 if (selectorMatches(selectorData, *element, rootNode)) 220 SelectorQueryTrait::appendOutputForElement(output, element); 221} 222 223#if ENABLE(CSS_SELECTOR_JIT) 224static ContainerNode& filterRootById(ContainerNode& rootNode, const CSSSelector& firstSelector) 225{ 226 if (!rootNode.inDocument()) 227 return rootNode; 228 if (rootNode.document().inQuirksMode()) 229 return rootNode; 230 231 // If there was an Id match in the rightmost Simple Selector, we should be in a RightMostWithIdMatch, not in filter. 232 // Thus we can skip the rightmost match. 233 const CSSSelector* selector = &firstSelector; 234 do { 235 ASSERT(selector->m_match != CSSSelector::Id); 236 if (selector->relation() != CSSSelector::SubSelector) 237 break; 238 selector = selector->tagHistory(); 239 } while (selector); 240 241 bool inAdjacentChain = false; 242 for (; selector; selector = selector->tagHistory()) { 243 if (selector->m_match == CSSSelector::Id) { 244 const AtomicString& idToMatch = selector->value(); 245 if (ContainerNode* searchRoot = rootNode.treeScope().getElementById(idToMatch)) { 246 if (LIKELY(!rootNode.treeScope().containsMultipleElementsWithId(idToMatch))) { 247 if (inAdjacentChain) 248 searchRoot = searchRoot->parentNode(); 249 if (searchRoot && (isTreeScopeRoot(rootNode) || searchRoot == &rootNode || searchRoot->isDescendantOf(&rootNode))) 250 return *searchRoot; 251 } 252 } 253 } 254 if (selector->relation() == CSSSelector::DirectAdjacent || selector->relation() == CSSSelector::IndirectAdjacent) 255 inAdjacentChain = true; 256 else 257 inAdjacentChain = false; 258 } 259 return rootNode; 260} 261#endif 262 263template <typename SelectorQueryTrait> 264static inline void elementsForLocalName(const ContainerNode& rootNode, const AtomicString& localName, typename SelectorQueryTrait::OutputType& output) 265{ 266 for (auto& element : elementDescendants(const_cast<ContainerNode&>(rootNode))) { 267 if (element.tagQName().localName() == localName) { 268 SelectorQueryTrait::appendOutputForElement(output, &element); 269 if (SelectorQueryTrait::shouldOnlyMatchFirstElement) 270 return; 271 } 272 } 273} 274 275template <typename SelectorQueryTrait> 276static inline void anyElement(const ContainerNode& rootNode, typename SelectorQueryTrait::OutputType& output) 277{ 278 for (auto& element : elementDescendants(const_cast<ContainerNode&>(rootNode))) { 279 SelectorQueryTrait::appendOutputForElement(output, &element); 280 if (SelectorQueryTrait::shouldOnlyMatchFirstElement) 281 return; 282 } 283} 284 285 286template <typename SelectorQueryTrait> 287ALWAYS_INLINE void SelectorDataList::executeSingleTagNameSelectorData(const ContainerNode& rootNode, const SelectorData& selectorData, typename SelectorQueryTrait::OutputType& output) const 288{ 289 ASSERT(m_selectors.size() == 1); 290 ASSERT(isSingleTagNameSelector(*selectorData.selector)); 291 292 const QualifiedName& tagQualifiedName = selectorData.selector->tagQName(); 293 const AtomicString& selectorLocalName = tagQualifiedName.localName(); 294 const AtomicString& selectorNamespaceURI = tagQualifiedName.namespaceURI(); 295 296 if (selectorNamespaceURI == starAtom) { 297 if (selectorLocalName != starAtom) { 298 // Common case: name defined, selectorNamespaceURI is a wildcard. 299 elementsForLocalName<SelectorQueryTrait>(rootNode, selectorLocalName, output); 300 } else { 301 // Other fairly common case: both are wildcards. 302 anyElement<SelectorQueryTrait>(rootNode, output); 303 } 304 } else { 305 // Fallback: NamespaceURI is set, selectorLocalName may be starAtom. 306 for (auto& element : elementDescendants(const_cast<ContainerNode&>(rootNode))) { 307 if (element.namespaceURI() == selectorNamespaceURI && (selectorLocalName == starAtom || element.tagQName().localName() == selectorLocalName)) { 308 SelectorQueryTrait::appendOutputForElement(output, &element); 309 if (SelectorQueryTrait::shouldOnlyMatchFirstElement) 310 return; 311 } 312 } 313 } 314} 315 316template <typename SelectorQueryTrait> 317ALWAYS_INLINE void SelectorDataList::executeSingleClassNameSelectorData(const ContainerNode& rootNode, const SelectorData& selectorData, typename SelectorQueryTrait::OutputType& output) const 318{ 319 ASSERT(m_selectors.size() == 1); 320 ASSERT(isSingleClassNameSelector(*selectorData.selector)); 321 322 const AtomicString& className = selectorData.selector->value(); 323 for (auto& element : elementDescendants(const_cast<ContainerNode&>(rootNode))) { 324 if (element.hasClass() && element.classNames().contains(className)) { 325 SelectorQueryTrait::appendOutputForElement(output, &element); 326 if (SelectorQueryTrait::shouldOnlyMatchFirstElement) 327 return; 328 } 329 } 330} 331 332template <typename SelectorQueryTrait> 333ALWAYS_INLINE void SelectorDataList::executeSingleSelectorData(const ContainerNode& rootNode, const SelectorData& selectorData, typename SelectorQueryTrait::OutputType& output) const 334{ 335 ASSERT(m_selectors.size() == 1); 336 337 for (auto& element : elementDescendants(const_cast<ContainerNode&>(rootNode))) { 338 if (selectorMatches(selectorData, element, rootNode)) { 339 SelectorQueryTrait::appendOutputForElement(output, &element); 340 if (SelectorQueryTrait::shouldOnlyMatchFirstElement) 341 return; 342 } 343 } 344} 345 346template <typename SelectorQueryTrait> 347ALWAYS_INLINE void SelectorDataList::executeSingleMultiSelectorData(const ContainerNode& rootNode, typename SelectorQueryTrait::OutputType& output) const 348{ 349 unsigned selectorCount = m_selectors.size(); 350 for (auto& element : elementDescendants(const_cast<ContainerNode&>(rootNode))) { 351 for (unsigned i = 0; i < selectorCount; ++i) { 352 if (selectorMatches(m_selectors[i], element, rootNode)) { 353 SelectorQueryTrait::appendOutputForElement(output, &element); 354 if (SelectorQueryTrait::shouldOnlyMatchFirstElement) 355 return; 356 break; 357 } 358 } 359 } 360} 361 362#if ENABLE(CSS_SELECTOR_JIT) 363template <typename SelectorQueryTrait> 364ALWAYS_INLINE void SelectorDataList::executeCompiledSimpleSelectorChecker(const ContainerNode& rootNode, SelectorCompiler::SimpleSelectorChecker selectorChecker, typename SelectorQueryTrait::OutputType& output, const SelectorData& selectorData) const 365{ 366 for (auto& element : elementDescendants(const_cast<ContainerNode&>(rootNode))) { 367#if CSS_SELECTOR_JIT_PROFILING 368 selectorData.compiledSelectorUsed(); 369#else 370 UNUSED_PARAM(selectorData); 371#endif 372 if (selectorChecker(&element)) { 373 SelectorQueryTrait::appendOutputForElement(output, &element); 374 if (SelectorQueryTrait::shouldOnlyMatchFirstElement) 375 return; 376 } 377 } 378} 379#endif // ENABLE(CSS_SELECTOR_JIT) 380 381template <typename SelectorQueryTrait> 382ALWAYS_INLINE void SelectorDataList::execute(ContainerNode& rootNode, typename SelectorQueryTrait::OutputType& output) const 383{ 384 ContainerNode* searchRootNode = &rootNode; 385 switch (m_matchType) { 386 case RightMostWithIdMatch: 387 { 388 const SelectorData& selectorData = m_selectors.first(); 389 if (const CSSSelector* idSelector = selectorForIdLookup(*searchRootNode, *selectorData.selector)) { 390 executeFastPathForIdSelector<SelectorQueryTrait>(*searchRootNode, m_selectors.first(), idSelector, output); 391 break; 392 } 393#if ENABLE(CSS_SELECTOR_JIT) 394 if (selectorData.compilationStatus == SelectorCompilationStatus::SimpleSelectorChecker) 395 goto CompiledSingleCase; 396#endif 397 } 398 FALLTHROUGH; 399 case CompilableSingleWithRootFilter: 400 case CompilableSingle: 401 { 402#if ENABLE(CSS_SELECTOR_JIT) 403 const SelectorData& selectorData = m_selectors.first(); 404 ASSERT(m_matchType == RightMostWithIdMatch || selectorData.compilationStatus == SelectorCompilationStatus::NotCompiled); 405 406 JSC::VM& vm = searchRootNode->document().scriptExecutionContext()->vm(); 407 selectorData.compilationStatus = SelectorCompiler::compileSelector(selectorData.selector, &vm, SelectorCompiler::SelectorContext::QuerySelector, selectorData.compiledSelectorCodeRef); 408 RELEASE_ASSERT(selectorData.compilationStatus != SelectorCompilationStatus::SelectorCheckerWithCheckingContext); 409 410 if (selectorData.compilationStatus == SelectorCompilationStatus::SimpleSelectorChecker) { 411 if (m_matchType == CompilableSingle) { 412 m_matchType = CompiledSingle; 413 goto CompiledSingleCase; 414 } 415 if (m_matchType == CompilableSingleWithRootFilter) { 416 m_matchType = CompiledSingleWithRootFilter; 417 goto CompiledSingleWithRootFilterCase; 418 } 419 goto CompiledSingleCase; 420 } 421 if (m_matchType != RightMostWithIdMatch) 422 m_matchType = SingleSelector; 423 goto SingleSelectorCase; 424 ASSERT_NOT_REACHED(); 425 break; 426#else 427 FALLTHROUGH; 428#endif // ENABLE(CSS_SELECTOR_JIT) 429 } 430 case CompiledSingleWithRootFilter: 431#if ENABLE(CSS_SELECTOR_JIT) 432 CompiledSingleWithRootFilterCase: 433 searchRootNode = &filterRootById(*searchRootNode, *m_selectors.first().selector); 434#endif // ENABLE(CSS_SELECTOR_JIT) 435 FALLTHROUGH; 436 case CompiledSingle: 437#if ENABLE(CSS_SELECTOR_JIT) 438 { 439 CompiledSingleCase: 440 const SelectorData& selectorData = m_selectors.first(); 441 void* compiledSelectorChecker = selectorData.compiledSelectorCodeRef.code().executableAddress(); 442 SelectorCompiler::SimpleSelectorChecker selectorChecker = SelectorCompiler::simpleSelectorCheckerFunction(compiledSelectorChecker, selectorData.compilationStatus); 443 executeCompiledSimpleSelectorChecker<SelectorQueryTrait>(*searchRootNode, selectorChecker, output, selectorData); 444 break; 445 } 446#else 447 FALLTHROUGH; 448#endif // ENABLE(CSS_SELECTOR_JIT) 449 case SingleSelector: 450#if ENABLE(CSS_SELECTOR_JIT) 451 SingleSelectorCase: 452#endif 453 executeSingleSelectorData<SelectorQueryTrait>(*searchRootNode, m_selectors.first(), output); 454 break; 455 case TagNameMatch: 456 executeSingleTagNameSelectorData<SelectorQueryTrait>(*searchRootNode, m_selectors.first(), output); 457 break; 458 case ClassNameMatch: 459 executeSingleClassNameSelectorData<SelectorQueryTrait>(*searchRootNode, m_selectors.first(), output); 460 break; 461 case MultipleSelectorMatch: 462 executeSingleMultiSelectorData<SelectorQueryTrait>(*searchRootNode, output); 463 break; 464 } 465} 466 467SelectorQuery::SelectorQuery(CSSSelectorList&& selectorList) 468 : m_selectorList(selectorList) 469 , m_selectors(m_selectorList) 470{ 471} 472 473SelectorQuery* SelectorQueryCache::add(const String& selectors, Document& document, ExceptionCode& ec) 474{ 475 auto it = m_entries.find(selectors); 476 if (it != m_entries.end()) 477 return it->value.get(); 478 479 CSSParser parser(document); 480 CSSSelectorList selectorList; 481 parser.parseSelector(selectors, selectorList); 482 483 if (!selectorList.first() || selectorList.hasInvalidSelector()) { 484 ec = SYNTAX_ERR; 485 return nullptr; 486 } 487 488 // Throw a NAMESPACE_ERR if the selector includes any namespace prefixes. 489 if (selectorList.selectorsNeedNamespaceResolution()) { 490 ec = NAMESPACE_ERR; 491 return nullptr; 492 } 493 494 const int maximumSelectorQueryCacheSize = 256; 495 if (m_entries.size() == maximumSelectorQueryCacheSize) 496 m_entries.remove(m_entries.begin()); 497 498 return m_entries.add(selectors, std::make_unique<SelectorQuery>(WTF::move(selectorList))).iterator->value.get(); 499} 500 501} 502