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