a27227026b790821681f715c8c546e10345af0e6
[WebKit-https.git] / Source / WebCore / dom / SelectorQuery.cpp
1 /*
2  * Copyright (C) 2011, 2013, 2014 Apple Inc. All rights reserved.
3  * Copyright (C) 2014 Yusuke Suzuki <utatane.tea@gmail.com>
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 "SelectorQuery.h"
29
30 #include "CSSParser.h"
31 #include "ElementDescendantIterator.h"
32 #include "SelectorChecker.h"
33 #include "StaticNodeList.h"
34 #include "StyledElement.h"
35
36 namespace WebCore {
37
38 #if !ASSERT_DISABLED
39 static bool isSingleTagNameSelector(const CSSSelector& selector)
40 {
41     return selector.isLastInTagHistory() && selector.match() == CSSSelector::Tag;
42 }
43
44 static bool isSingleClassNameSelector(const CSSSelector& selector)
45 {
46     return selector.isLastInTagHistory() && selector.match() == CSSSelector::Class;
47 }
48 #endif
49
50 enum class IdMatchingType : uint8_t {
51     None,
52     Rightmost,
53     Filter
54 };
55
56 static IdMatchingType findIdMatchingType(const CSSSelector& firstSelector)
57 {
58     bool inRightmost = true;
59     for (const CSSSelector* selector = &firstSelector; selector; selector = selector->tagHistory()) {
60         if (selector->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
71 SelectorDataList::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));
80
81     if (selectorCount == 1) {
82         const CSSSelector& selector = *m_selectors.first().selector;
83         if (selector.isLastInTagHistory()) {
84             switch (selector.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 = CompilableMultipleSelectorMatch;
113 }
114
115 inline bool SelectorDataList::selectorMatches(const SelectorData& selectorData, Element& element, const ContainerNode& rootNode) const
116 {
117     SelectorChecker selectorChecker(element.document());
118     SelectorChecker::CheckingContext selectorCheckingContext(SelectorChecker::Mode::QueryingRules);
119     selectorCheckingContext.scope = rootNode.isDocumentNode() ? nullptr : &rootNode;
120     unsigned ignoredSpecificity;
121     return selectorChecker.match(selectorData.selector, &element, selectorCheckingContext, ignoredSpecificity);
122 }
123
124 inline Element* SelectorDataList::selectorClosest(const SelectorData& selectorData, Element& element, const ContainerNode& rootNode) const
125 {
126     SelectorChecker selectorChecker(element.document());
127     SelectorChecker::CheckingContext selectorCheckingContext(SelectorChecker::Mode::QueryingRules);
128     selectorCheckingContext.scope = rootNode.isDocumentNode() ? nullptr : &rootNode;
129     Element* currentNode = &element;
130     unsigned ignoredSpecificity;
131     if (!selectorChecker.match(selectorData.selector, currentNode, selectorCheckingContext, ignoredSpecificity))
132         return nullptr;
133     return currentNode;
134 }
135
136 bool SelectorDataList::matches(Element& targetElement) const
137 {
138     unsigned selectorCount = m_selectors.size();
139     for (unsigned i = 0; i < selectorCount; ++i) {
140         if (selectorMatches(m_selectors[i], targetElement, targetElement))
141             return true;
142     }
143     return false;
144 }
145
146 Element* SelectorDataList::closest(Element& targetElement) const
147 {
148     Element* currentNode = &targetElement;
149     do {
150         for (auto& selector : m_selectors) {
151             Element* candidateElement = selectorClosest(selector, *currentNode, targetElement);
152             if (candidateElement)
153                 return candidateElement;
154         }
155         currentNode = currentNode->parentElement();
156     } while (currentNode);
157     return nullptr;
158 }
159
160 struct AllElementExtractorSelectorQueryTrait {
161     typedef Vector<Ref<Element>> OutputType;
162     static const bool shouldOnlyMatchFirstElement = false;
163     ALWAYS_INLINE static void appendOutputForElement(OutputType& output, Element* element) { ASSERT(element); output.append(*element); }
164 };
165
166 RefPtr<NodeList> SelectorDataList::queryAll(ContainerNode& rootNode) const
167 {
168     Vector<Ref<Element>> result;
169     execute<AllElementExtractorSelectorQueryTrait>(rootNode, result);
170     return StaticElementList::adopt(result);
171 }
172
173 struct SingleElementExtractorSelectorQueryTrait {
174     typedef Element* OutputType;
175     static const bool shouldOnlyMatchFirstElement = true;
176     ALWAYS_INLINE static void appendOutputForElement(OutputType& output, Element* element)
177     {
178         ASSERT(element);
179         ASSERT(!output);
180         output = element;
181     }
182 };
183
184 Element* SelectorDataList::queryFirst(ContainerNode& rootNode) const
185 {
186     Element* result = nullptr;
187     execute<SingleElementExtractorSelectorQueryTrait>(rootNode, result);
188     return result;
189 }
190
191 static const CSSSelector* selectorForIdLookup(const ContainerNode& rootNode, const CSSSelector& firstSelector)
192 {
193     if (!rootNode.inDocument())
194         return nullptr;
195     if (rootNode.document().inQuirksMode())
196         return nullptr;
197
198     for (const CSSSelector* selector = &firstSelector; selector; selector = selector->tagHistory()) {
199         if (selector->match() == CSSSelector::Id)
200             return selector;
201         if (selector->relation() != CSSSelector::SubSelector)
202             break;
203     }
204
205     return nullptr;
206 }
207
208 static inline bool isTreeScopeRoot(const ContainerNode& node)
209 {
210     return node.isDocumentNode() || node.isShadowRoot();
211 }
212
213 template <typename SelectorQueryTrait>
214 ALWAYS_INLINE void SelectorDataList::executeFastPathForIdSelector(const ContainerNode& rootNode, const SelectorData& selectorData, const CSSSelector* idSelector, typename SelectorQueryTrait::OutputType& output) const
215 {
216     ASSERT(m_selectors.size() == 1);
217     ASSERT(idSelector);
218
219     const AtomicString& idToMatch = idSelector->value();
220     if (UNLIKELY(rootNode.treeScope().containsMultipleElementsWithId(idToMatch))) {
221         const Vector<Element*>* elements = rootNode.treeScope().getAllElementsById(idToMatch);
222         ASSERT(elements);
223         size_t count = elements->size();
224         bool rootNodeIsTreeScopeRoot = isTreeScopeRoot(rootNode);
225         for (size_t i = 0; i < count; ++i) {
226             Element& element = *elements->at(i);
227             if ((rootNodeIsTreeScopeRoot || element.isDescendantOf(&rootNode)) && selectorMatches(selectorData, element, rootNode)) {
228                 SelectorQueryTrait::appendOutputForElement(output, &element);
229                 if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
230                     return;
231             }
232         }
233         return;
234     }
235
236     Element* element = rootNode.treeScope().getElementById(idToMatch);
237     if (!element || !(isTreeScopeRoot(rootNode) || element->isDescendantOf(&rootNode)))
238         return;
239     if (selectorMatches(selectorData, *element, rootNode))
240         SelectorQueryTrait::appendOutputForElement(output, element);
241 }
242
243 static ContainerNode& filterRootById(ContainerNode& rootNode, const CSSSelector& firstSelector)
244 {
245     if (!rootNode.inDocument())
246         return rootNode;
247     if (rootNode.document().inQuirksMode())
248         return rootNode;
249
250     // If there was an Id match in the rightmost Simple Selector, we should be in a RightMostWithIdMatch, not in filter.
251     // Thus we can skip the rightmost match.
252     const CSSSelector* selector = &firstSelector;
253     do {
254         ASSERT(selector->match() != CSSSelector::Id);
255         if (selector->relation() != CSSSelector::SubSelector)
256             break;
257         selector = selector->tagHistory();
258     } while (selector);
259
260     bool inAdjacentChain = false;
261     for (; selector; selector = selector->tagHistory()) {
262         if (selector->match() == CSSSelector::Id) {
263             const AtomicString& idToMatch = selector->value();
264             if (ContainerNode* searchRoot = rootNode.treeScope().getElementById(idToMatch)) {
265                 if (LIKELY(!rootNode.treeScope().containsMultipleElementsWithId(idToMatch))) {
266                     if (inAdjacentChain)
267                         searchRoot = searchRoot->parentNode();
268                     if (searchRoot && (isTreeScopeRoot(rootNode) || searchRoot == &rootNode || searchRoot->isDescendantOf(&rootNode)))
269                         return *searchRoot;
270                 }
271             }
272         }
273         if (selector->relation() == CSSSelector::SubSelector)
274             continue;
275         if (selector->relation() == CSSSelector::DirectAdjacent || selector->relation() == CSSSelector::IndirectAdjacent)
276             inAdjacentChain = true;
277         else
278             inAdjacentChain = false;
279     }
280     return rootNode;
281 }
282
283 static ALWAYS_INLINE bool localNameMatches(const Element& element, const AtomicString& localName, const AtomicString& lowercaseLocalName)
284 {
285     if (element.isHTMLElement() && element.document().isHTMLDocument())
286         return element.localName() == lowercaseLocalName;
287     return element.localName() == localName;
288
289 }
290
291 template <typename SelectorQueryTrait>
292 static inline void elementsForLocalName(const ContainerNode& rootNode, const AtomicString& localName, const AtomicString& lowercaseLocalName, typename SelectorQueryTrait::OutputType& output)
293 {
294     if (localName == lowercaseLocalName) {
295         for (auto& element : elementDescendants(const_cast<ContainerNode&>(rootNode))) {
296             if (element.tagQName().localName() == localName) {
297                 SelectorQueryTrait::appendOutputForElement(output, &element);
298                 if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
299                 return;
300             }
301         }
302     } else {
303         for (auto& element : elementDescendants(const_cast<ContainerNode&>(rootNode))) {
304             if (localNameMatches(element, localName, lowercaseLocalName)) {
305                 SelectorQueryTrait::appendOutputForElement(output, &element);
306                 if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
307                 return;
308             }
309         }
310     }
311 }
312
313 template <typename SelectorQueryTrait>
314 static inline void anyElement(const ContainerNode& rootNode, typename SelectorQueryTrait::OutputType& output)
315 {
316     for (auto& element : elementDescendants(const_cast<ContainerNode&>(rootNode))) {
317         SelectorQueryTrait::appendOutputForElement(output, &element);
318         if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
319             return;
320     }
321 }
322
323
324 template <typename SelectorQueryTrait>
325 ALWAYS_INLINE void SelectorDataList::executeSingleTagNameSelectorData(const ContainerNode& rootNode, const SelectorData& selectorData, typename SelectorQueryTrait::OutputType& output) const
326 {
327     ASSERT(m_selectors.size() == 1);
328     ASSERT(isSingleTagNameSelector(*selectorData.selector));
329
330     const QualifiedName& tagQualifiedName = selectorData.selector->tagQName();
331     const AtomicString& selectorLocalName = tagQualifiedName.localName();
332     const AtomicString& selectorLowercaseLocalName = selectorData.selector->tagLowercaseLocalName();
333     const AtomicString& selectorNamespaceURI = tagQualifiedName.namespaceURI();
334
335     if (selectorNamespaceURI == starAtom) {
336         if (selectorLocalName != starAtom) {
337             // Common case: name defined, selectorNamespaceURI is a wildcard.
338             elementsForLocalName<SelectorQueryTrait>(rootNode, selectorLocalName, selectorLowercaseLocalName, output);
339         } else {
340             // Other fairly common case: both are wildcards.
341             anyElement<SelectorQueryTrait>(rootNode, output);
342         }
343     } else {
344         // Fallback: NamespaceURI is set, selectorLocalName may be starAtom.
345         for (auto& element : elementDescendants(const_cast<ContainerNode&>(rootNode))) {
346             if (element.namespaceURI() == selectorNamespaceURI && localNameMatches(element, selectorLocalName, selectorLowercaseLocalName)) {
347                 SelectorQueryTrait::appendOutputForElement(output, &element);
348                 if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
349                     return;
350             }
351         }
352     }
353 }
354
355 template <typename SelectorQueryTrait>
356 ALWAYS_INLINE void SelectorDataList::executeSingleClassNameSelectorData(const ContainerNode& rootNode, const SelectorData& selectorData, typename SelectorQueryTrait::OutputType& output) const
357 {
358     ASSERT(m_selectors.size() == 1);
359     ASSERT(isSingleClassNameSelector(*selectorData.selector));
360
361     const AtomicString& className = selectorData.selector->value();
362     for (auto& element : elementDescendants(const_cast<ContainerNode&>(rootNode))) {
363         if (element.hasClass() && element.classNames().contains(className)) {
364             SelectorQueryTrait::appendOutputForElement(output, &element);
365             if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
366                 return;
367         }
368     }
369 }
370
371 template <typename SelectorQueryTrait>
372 ALWAYS_INLINE void SelectorDataList::executeSingleSelectorData(const ContainerNode& rootNode, const ContainerNode& searchRootNode, const SelectorData& selectorData, typename SelectorQueryTrait::OutputType& output) const
373 {
374     ASSERT(m_selectors.size() == 1);
375
376     for (auto& element : elementDescendants(const_cast<ContainerNode&>(searchRootNode))) {
377         if (selectorMatches(selectorData, element, rootNode)) {
378             SelectorQueryTrait::appendOutputForElement(output, &element);
379             if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
380                 return;
381         }
382     }
383 }
384
385 template <typename SelectorQueryTrait>
386 ALWAYS_INLINE void SelectorDataList::executeSingleMultiSelectorData(const ContainerNode& rootNode, typename SelectorQueryTrait::OutputType& output) const
387 {
388     unsigned selectorCount = m_selectors.size();
389     for (auto& element : elementDescendants(const_cast<ContainerNode&>(rootNode))) {
390         for (unsigned i = 0; i < selectorCount; ++i) {
391             if (selectorMatches(m_selectors[i], element, rootNode)) {
392                 SelectorQueryTrait::appendOutputForElement(output, &element);
393                 if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
394                     return;
395                 break;
396             }
397         }
398     }
399 }
400
401 #if ENABLE(CSS_SELECTOR_JIT)
402 template <typename SelectorQueryTrait>
403 ALWAYS_INLINE void SelectorDataList::executeCompiledSimpleSelectorChecker(const ContainerNode& searchRootNode, SelectorCompiler::QuerySelectorSimpleSelectorChecker selectorChecker, typename SelectorQueryTrait::OutputType& output, const SelectorData& selectorData) const
404 {
405     for (auto& element : elementDescendants(const_cast<ContainerNode&>(searchRootNode))) {
406 #if CSS_SELECTOR_JIT_PROFILING
407         selectorData.compiledSelectorUsed();
408 #else
409         UNUSED_PARAM(selectorData);
410 #endif
411         if (selectorChecker(&element)) {
412             SelectorQueryTrait::appendOutputForElement(output, &element);
413             if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
414                 return;
415         }
416     }
417 }
418
419 template <typename SelectorQueryTrait>
420 ALWAYS_INLINE void SelectorDataList::executeCompiledSelectorCheckerWithCheckingContext(const ContainerNode& rootNode, const ContainerNode& searchRootNode, SelectorCompiler::QuerySelectorSelectorCheckerWithCheckingContext selectorChecker, typename SelectorQueryTrait::OutputType& output, const SelectorData& selectorData) const
421 {
422     SelectorChecker::CheckingContext checkingContext(SelectorChecker::Mode::QueryingRules);
423     checkingContext.scope = rootNode.isDocumentNode() ? nullptr : &rootNode;
424
425     for (auto& element : elementDescendants(const_cast<ContainerNode&>(searchRootNode))) {
426 #if CSS_SELECTOR_JIT_PROFILING
427         selectorData.compiledSelectorUsed();
428 #else
429         UNUSED_PARAM(selectorData);
430 #endif
431         if (selectorChecker(&element, &checkingContext)) {
432             SelectorQueryTrait::appendOutputForElement(output, &element);
433             if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
434                 return;
435         }
436     }
437 }
438
439 template <typename SelectorQueryTrait>
440 ALWAYS_INLINE void SelectorDataList::executeCompiledSingleMultiSelectorData(const ContainerNode& rootNode, typename SelectorQueryTrait::OutputType& output) const
441 {
442     SelectorChecker::CheckingContext checkingContext(SelectorChecker::Mode::QueryingRules);
443     checkingContext.scope = rootNode.isDocumentNode() ? nullptr : &rootNode;
444     unsigned selectorCount = m_selectors.size();
445     for (auto& element : elementDescendants(const_cast<ContainerNode&>(rootNode))) {
446         for (unsigned i = 0; i < selectorCount; ++i) {
447 #if CSS_SELECTOR_JIT_PROFILING
448             m_selectors[i].compiledSelectorUsed();
449 #endif
450             bool matched = false;
451             void* compiledSelectorChecker = m_selectors[i].compiledSelectorCodeRef.code().executableAddress();
452             if (m_selectors[i].compilationStatus == SelectorCompilationStatus::SimpleSelectorChecker) {
453                 SelectorCompiler::QuerySelectorSimpleSelectorChecker selectorChecker = SelectorCompiler::querySelectorSimpleSelectorCheckerFunction(compiledSelectorChecker, m_selectors[i].compilationStatus);
454                 matched = selectorChecker(&element);
455             } else {
456                 ASSERT(m_selectors[i].compilationStatus == SelectorCompilationStatus::SelectorCheckerWithCheckingContext);
457                 SelectorCompiler::QuerySelectorSelectorCheckerWithCheckingContext selectorChecker = SelectorCompiler::querySelectorSelectorCheckerFunctionWithCheckingContext(compiledSelectorChecker, m_selectors[i].compilationStatus);
458                 matched = selectorChecker(&element, &checkingContext);
459             }
460             if (matched) {
461                 SelectorQueryTrait::appendOutputForElement(output, &element);
462                 if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
463                     return;
464                 break;
465             }
466         }
467     }
468 }
469
470 static bool isCompiledSelector(SelectorCompilationStatus compilationStatus)
471 {
472     return compilationStatus == SelectorCompilationStatus::SimpleSelectorChecker || compilationStatus == SelectorCompilationStatus::SelectorCheckerWithCheckingContext;
473 }
474
475 bool SelectorDataList::compileSelector(const SelectorData& selectorData, const ContainerNode& rootNode)
476 {
477     if (selectorData.compilationStatus != SelectorCompilationStatus::NotCompiled)
478         return isCompiledSelector(selectorData.compilationStatus);
479
480     JSC::VM& vm = rootNode.document().scriptExecutionContext()->vm();
481     selectorData.compilationStatus = SelectorCompiler::compileSelector(selectorData.selector, &vm, SelectorCompiler::SelectorContext::QuerySelector, selectorData.compiledSelectorCodeRef);
482     return isCompiledSelector(selectorData.compilationStatus);
483 }
484
485
486 #endif // ENABLE(CSS_SELECTOR_JIT)
487
488 template <typename SelectorQueryTrait>
489 ALWAYS_INLINE void SelectorDataList::execute(ContainerNode& rootNode, typename SelectorQueryTrait::OutputType& output) const
490 {
491     ContainerNode* searchRootNode = &rootNode;
492     switch (m_matchType) {
493     case RightMostWithIdMatch:
494         {
495         const SelectorData& selectorData = m_selectors.first();
496         if (const CSSSelector* idSelector = selectorForIdLookup(*searchRootNode, *selectorData.selector)) {
497             executeFastPathForIdSelector<SelectorQueryTrait>(*searchRootNode, m_selectors.first(), idSelector, output);
498             break;
499         }
500 #if ENABLE(CSS_SELECTOR_JIT)
501         if (compileSelector(selectorData, *searchRootNode))
502             goto CompiledSingleCase;
503 #endif // ENABLE(CSS_SELECTOR_JIT)
504         goto SingleSelectorCase;
505         ASSERT_NOT_REACHED();
506         }
507
508     case CompilableSingleWithRootFilter:
509     case CompilableSingle:
510         {
511 #if ENABLE(CSS_SELECTOR_JIT)
512         const SelectorData& selectorData = m_selectors.first();
513         ASSERT(selectorData.compilationStatus == SelectorCompilationStatus::NotCompiled);
514         ASSERT(m_matchType == CompilableSingle || m_matchType == CompilableSingleWithRootFilter);
515         if (compileSelector(selectorData, *searchRootNode)) {
516             if (m_matchType == CompilableSingle) {
517                 m_matchType = CompiledSingle;
518                 goto CompiledSingleCase;
519             }
520             ASSERT(m_matchType == CompilableSingleWithRootFilter);
521             m_matchType = CompiledSingleWithRootFilter;
522             goto CompiledSingleWithRootFilterCase;
523         }
524 #endif // ENABLE(CSS_SELECTOR_JIT)
525         if (m_matchType == CompilableSingle) {
526             m_matchType = SingleSelector;
527             goto SingleSelectorCase;
528         }
529         ASSERT(m_matchType == CompilableSingleWithRootFilter);
530         m_matchType = SingleSelectorWithRootFilter;
531         goto SingleSelectorWithRootFilterCase;
532         ASSERT_NOT_REACHED();
533         }
534
535 #if ENABLE(CSS_SELECTOR_JIT)
536     case CompiledSingleWithRootFilter:
537         CompiledSingleWithRootFilterCase:
538         searchRootNode = &filterRootById(*searchRootNode, *m_selectors.first().selector);
539         FALLTHROUGH;
540     case CompiledSingle:
541         {
542         CompiledSingleCase:
543         const SelectorData& selectorData = m_selectors.first();
544         void* compiledSelectorChecker = selectorData.compiledSelectorCodeRef.code().executableAddress();
545         if (selectorData.compilationStatus == SelectorCompilationStatus::SimpleSelectorChecker) {
546             SelectorCompiler::QuerySelectorSimpleSelectorChecker selectorChecker = SelectorCompiler::querySelectorSimpleSelectorCheckerFunction(compiledSelectorChecker, selectorData.compilationStatus);
547             executeCompiledSimpleSelectorChecker<SelectorQueryTrait>(*searchRootNode, selectorChecker, output, selectorData);
548         } else {
549             ASSERT(selectorData.compilationStatus == SelectorCompilationStatus::SelectorCheckerWithCheckingContext);
550             SelectorCompiler::QuerySelectorSelectorCheckerWithCheckingContext selectorChecker = SelectorCompiler::querySelectorSelectorCheckerFunctionWithCheckingContext(compiledSelectorChecker, selectorData.compilationStatus);
551             executeCompiledSelectorCheckerWithCheckingContext<SelectorQueryTrait>(rootNode, *searchRootNode, selectorChecker, output, selectorData);
552         }
553         break;
554         }
555 #else
556     case CompiledSingleWithRootFilter:
557     case CompiledSingle:
558         ASSERT_NOT_REACHED();
559         FALLTHROUGH;
560 #endif // ENABLE(CSS_SELECTOR_JIT)
561
562     case SingleSelectorWithRootFilter:
563         SingleSelectorWithRootFilterCase:
564         searchRootNode = &filterRootById(*searchRootNode, *m_selectors.first().selector);
565         FALLTHROUGH;
566     case SingleSelector:
567         SingleSelectorCase:
568         executeSingleSelectorData<SelectorQueryTrait>(rootNode, *searchRootNode, m_selectors.first(), output);
569         break;
570
571     case TagNameMatch:
572         executeSingleTagNameSelectorData<SelectorQueryTrait>(*searchRootNode, m_selectors.first(), output);
573         break;
574     case ClassNameMatch:
575         executeSingleClassNameSelectorData<SelectorQueryTrait>(*searchRootNode, m_selectors.first(), output);
576         break;
577     case CompilableMultipleSelectorMatch:
578 #if ENABLE(CSS_SELECTOR_JIT)
579         {
580         unsigned selectorCount = m_selectors.size();
581         for (unsigned i = 0; i < selectorCount; ++i) {
582             if (!compileSelector(m_selectors[i], *searchRootNode)) {
583                 m_matchType = MultipleSelectorMatch;
584                 goto MultipleSelectorMatch;
585             }
586         }
587         m_matchType = CompiledMultipleSelectorMatch;
588         goto CompiledMultipleSelectorMatch;
589         }
590 #else
591         FALLTHROUGH;
592 #endif // ENABLE(CSS_SELECTOR_JIT)
593     case CompiledMultipleSelectorMatch:
594 #if ENABLE(CSS_SELECTOR_JIT)
595         CompiledMultipleSelectorMatch:
596         executeCompiledSingleMultiSelectorData<SelectorQueryTrait>(*searchRootNode, output);
597         break;
598 #else
599         FALLTHROUGH;
600 #endif // ENABLE(CSS_SELECTOR_JIT)
601     case MultipleSelectorMatch:
602 #if ENABLE(CSS_SELECTOR_JIT)
603         MultipleSelectorMatch:
604 #endif
605         executeSingleMultiSelectorData<SelectorQueryTrait>(*searchRootNode, output);
606         break;
607     }
608 }
609
610 SelectorQuery::SelectorQuery(CSSSelectorList&& selectorList)
611     : m_selectorList(WTF::move(selectorList))
612     , m_selectors(m_selectorList)
613 {
614 }
615
616 SelectorQuery* SelectorQueryCache::add(const String& selectors, Document& document, ExceptionCode& ec)
617 {
618     auto it = m_entries.find(selectors);
619     if (it != m_entries.end())
620         return it->value.get();
621
622     CSSParser parser(document);
623     CSSSelectorList selectorList;
624     parser.parseSelector(selectors, selectorList);
625
626     if (!selectorList.first() || selectorList.hasInvalidSelector()) {
627         ec = SYNTAX_ERR;
628         return nullptr;
629     }
630
631     // Throw a NAMESPACE_ERR if the selector includes any namespace prefixes.
632     if (selectorList.selectorsNeedNamespaceResolution()) {
633         ec = NAMESPACE_ERR;
634         return nullptr;
635     }
636
637     const int maximumSelectorQueryCacheSize = 256;
638     if (m_entries.size() == maximumSelectorQueryCacheSize)
639         m_entries.remove(m_entries.begin());
640
641     return m_entries.add(selectors, std::make_unique<SelectorQuery>(WTF::move(selectorList))).iterator->value.get();
642 }
643
644 }