Optimized querySelector(All) when selector contains #id
[WebKit-https.git] / Source / WebCore / dom / SelectorQuery.cpp
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 "ElementIterator.h"
31 #include "SelectorChecker.h"
32 #include "SelectorCheckerFastPath.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.m_match == CSSSelector::Tag;
42 }
43
44 static bool isSingleClassNameSelector(const CSSSelector& selector)
45 {
46     return selector.isLastInTagHistory() && selector.m_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->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
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, 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
115 inline 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::QueryingRules);
125     SelectorChecker::SelectorCheckingContext selectorCheckingContext(selectorData.selector, &element, SelectorChecker::VisitedMatchDisabled);
126     selectorCheckingContext.scope = rootNode.isDocumentNode() ? nullptr : &rootNode;
127     PseudoId ignoreDynamicPseudo = NOPSEUDO;
128     return selectorChecker.match(selectorCheckingContext, ignoreDynamicPseudo);
129 }
130
131 bool SelectorDataList::matches(Element& targetElement) const
132 {
133     unsigned selectorCount = m_selectors.size();
134     for (unsigned i = 0; i < selectorCount; ++i) {
135         if (selectorMatches(m_selectors[i], targetElement, targetElement))
136             return true;
137     }
138     return false;
139 }
140
141 struct AllElementExtractorSelectorQueryTrait {
142     typedef Vector<Ref<Element>> OutputType;
143     static const bool shouldOnlyMatchFirstElement = false;
144     ALWAYS_INLINE static void appendOutputForElement(OutputType& output, Element* element) { ASSERT(element); output.append(*element); }
145 };
146
147 RefPtr<NodeList> SelectorDataList::queryAll(ContainerNode& rootNode) const
148 {
149     Vector<Ref<Element>> result;
150     execute<AllElementExtractorSelectorQueryTrait>(rootNode, result);
151     return StaticElementList::adopt(result);
152 }
153
154 struct SingleElementExtractorSelectorQueryTrait {
155     typedef Element* OutputType;
156     static const bool shouldOnlyMatchFirstElement = true;
157     ALWAYS_INLINE static void appendOutputForElement(OutputType& output, Element* element)
158     {
159         ASSERT(element);
160         ASSERT(!output);
161         output = element;
162     }
163 };
164
165 Element* SelectorDataList::queryFirst(ContainerNode& rootNode) const
166 {
167     Element* result = nullptr;
168     execute<SingleElementExtractorSelectorQueryTrait>(rootNode, result);
169     return result;
170 }
171
172 static const CSSSelector* selectorForIdLookup(const ContainerNode& rootNode, const CSSSelector& firstSelector)
173 {
174     if (!rootNode.inDocument())
175         return nullptr;
176     if (rootNode.document().inQuirksMode())
177         return nullptr;
178
179     for (const CSSSelector* selector = &firstSelector; selector; selector = selector->tagHistory()) {
180         if (selector->m_match == CSSSelector::Id)
181             return selector;
182         if (selector->relation() != CSSSelector::SubSelector)
183             break;
184     }
185
186     return nullptr;
187 }
188
189 static inline bool isTreeScopeRoot(const ContainerNode& node)
190 {
191     return node.isDocumentNode() || node.isShadowRoot();
192 }
193
194 template <typename SelectorQueryTrait>
195 ALWAYS_INLINE void SelectorDataList::executeFastPathForIdSelector(const ContainerNode& rootNode, const SelectorData& selectorData, const CSSSelector* idSelector, typename SelectorQueryTrait::OutputType& output) const
196 {
197     ASSERT(m_selectors.size() == 1);
198     ASSERT(idSelector);
199
200     const AtomicString& idToMatch = idSelector->value();
201     if (UNLIKELY(rootNode.treeScope().containsMultipleElementsWithId(idToMatch))) {
202         const Vector<Element*>* elements = rootNode.treeScope().getAllElementsById(idToMatch);
203         ASSERT(elements);
204         size_t count = elements->size();
205         bool rootNodeIsTreeScopeRoot = isTreeScopeRoot(rootNode);
206         for (size_t i = 0; i < count; ++i) {
207             Element& element = *elements->at(i);
208             if ((rootNodeIsTreeScopeRoot || element.isDescendantOf(&rootNode)) && selectorMatches(selectorData, element, rootNode)) {
209                 SelectorQueryTrait::appendOutputForElement(output, &element);
210                 if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
211                     return;
212             }
213         }
214         return;
215     }
216
217     Element* element = rootNode.treeScope().getElementById(idToMatch);
218     if (!element || !(isTreeScopeRoot(rootNode) || element->isDescendantOf(&rootNode)))
219         return;
220     if (selectorMatches(selectorData, *element, rootNode))
221         SelectorQueryTrait::appendOutputForElement(output, element);
222 }
223
224 #if ENABLE(CSS_SELECTOR_JIT)
225 static ContainerNode& filterRootById(ContainerNode& rootNode, const CSSSelector& firstSelector)
226 {
227     if (!rootNode.inDocument())
228         return rootNode;
229     if (rootNode.document().inQuirksMode())
230         return rootNode;
231
232     // If there was an Id match in the rightmost Simple Selector, we should be in a RightMostWithIdMatch, not in filter.
233     // Thus we can skip the rightmost match.
234     const CSSSelector* selector = &firstSelector;
235     do {
236         ASSERT(selector->m_match != CSSSelector::Id);
237         if (selector->relation() != CSSSelector::SubSelector)
238             break;
239         selector = selector->tagHistory();
240     } while (selector);
241
242     bool inAdjacentChain = false;
243     for (; selector; selector = selector->tagHistory()) {
244         if (selector->m_match == CSSSelector::Id) {
245             const AtomicString& idToMatch = selector->value();
246             if (ContainerNode* searchRoot = rootNode.treeScope().getElementById(idToMatch)) {
247                 if (LIKELY(!rootNode.treeScope().containsMultipleElementsWithId(idToMatch))) {
248                     if (inAdjacentChain)
249                         searchRoot = searchRoot->parentNode();
250                     if (searchRoot && (isTreeScopeRoot(rootNode) || searchRoot == &rootNode || searchRoot->isDescendantOf(&rootNode)))
251                         return *searchRoot;
252                 }
253             }
254         }
255         if (selector->relation() == CSSSelector::DirectAdjacent || selector->relation() == CSSSelector::IndirectAdjacent)
256             inAdjacentChain = true;
257         else
258             inAdjacentChain = false;
259     }
260     return rootNode;
261 }
262 #endif
263
264 template <typename SelectorQueryTrait>
265 static inline void elementsForLocalName(const ContainerNode& rootNode, const AtomicString& localName, typename SelectorQueryTrait::OutputType& output)
266 {
267     for (auto& element : descendantsOfType<Element>(const_cast<ContainerNode&>(rootNode))) {
268         if (element.tagQName().localName() == localName) {
269             SelectorQueryTrait::appendOutputForElement(output, &element);
270             if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
271                 return;
272         }
273     }
274 }
275
276 template <typename SelectorQueryTrait>
277 static inline void anyElement(const ContainerNode& rootNode, typename SelectorQueryTrait::OutputType& output)
278 {
279     for (auto& element : descendantsOfType<Element>(const_cast<ContainerNode&>(rootNode))) {
280         SelectorQueryTrait::appendOutputForElement(output, &element);
281         if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
282             return;
283     }
284 }
285
286
287 template <typename SelectorQueryTrait>
288 ALWAYS_INLINE void SelectorDataList::executeSingleTagNameSelectorData(const ContainerNode& rootNode, const SelectorData& selectorData, typename SelectorQueryTrait::OutputType& output) const
289 {
290     ASSERT(m_selectors.size() == 1);
291     ASSERT(isSingleTagNameSelector(*selectorData.selector));
292
293     const QualifiedName& tagQualifiedName = selectorData.selector->tagQName();
294     const AtomicString& selectorLocalName = tagQualifiedName.localName();
295     const AtomicString& selectorNamespaceURI = tagQualifiedName.namespaceURI();
296
297     if (selectorNamespaceURI == starAtom) {
298         if (selectorLocalName != starAtom) {
299             // Common case: name defined, selectorNamespaceURI is a wildcard.
300             elementsForLocalName<SelectorQueryTrait>(rootNode, selectorLocalName, output);
301         } else {
302             // Other fairly common case: both are wildcards.
303             anyElement<SelectorQueryTrait>(rootNode, output);
304         }
305     } else {
306         // Fallback: NamespaceURI is set, selectorLocalName may be starAtom.
307         for (auto& element : descendantsOfType<Element>(const_cast<ContainerNode&>(rootNode))) {
308             if (element.namespaceURI() == selectorNamespaceURI && (selectorLocalName == starAtom || element.tagQName().localName() == selectorLocalName)) {
309                 SelectorQueryTrait::appendOutputForElement(output, &element);
310                 if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
311                     return;
312             }
313         }
314     }
315 }
316
317 template <typename SelectorQueryTrait>
318 ALWAYS_INLINE void SelectorDataList::executeSingleClassNameSelectorData(const ContainerNode& rootNode, const SelectorData& selectorData, typename SelectorQueryTrait::OutputType& output) const
319 {
320     ASSERT(m_selectors.size() == 1);
321     ASSERT(isSingleClassNameSelector(*selectorData.selector));
322
323     const AtomicString& className = selectorData.selector->value();
324     for (auto& element : descendantsOfType<Element>(const_cast<ContainerNode&>(rootNode))) {
325         if (element.hasClass() && element.classNames().contains(className)) {
326             SelectorQueryTrait::appendOutputForElement(output, &element);
327             if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
328                 return;
329         }
330     }
331 }
332
333 template <typename SelectorQueryTrait>
334 ALWAYS_INLINE void SelectorDataList::executeSingleSelectorData(const ContainerNode& rootNode, const SelectorData& selectorData, typename SelectorQueryTrait::OutputType& output) const
335 {
336     ASSERT(m_selectors.size() == 1);
337
338     for (auto& element : descendantsOfType<Element>(const_cast<ContainerNode&>(rootNode))) {
339         if (selectorMatches(selectorData, element, rootNode)) {
340             SelectorQueryTrait::appendOutputForElement(output, &element);
341             if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
342                 return;
343         }
344     }
345 }
346
347 template <typename SelectorQueryTrait>
348 ALWAYS_INLINE void SelectorDataList::executeSingleMultiSelectorData(const ContainerNode& rootNode, typename SelectorQueryTrait::OutputType& output) const
349 {
350     unsigned selectorCount = m_selectors.size();
351     for (auto& element : descendantsOfType<Element>(const_cast<ContainerNode&>(rootNode))) {
352         for (unsigned i = 0; i < selectorCount; ++i) {
353             if (selectorMatches(m_selectors[i], element, rootNode)) {
354                 SelectorQueryTrait::appendOutputForElement(output, &element);
355                 if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
356                     return;
357                 break;
358             }
359         }
360     }
361 }
362
363 #if ENABLE(CSS_SELECTOR_JIT)
364 template <typename SelectorQueryTrait>
365 ALWAYS_INLINE void SelectorDataList::executeCompiledSimpleSelectorChecker(const ContainerNode& rootNode, SelectorCompiler::SimpleSelectorChecker selectorChecker, typename SelectorQueryTrait::OutputType& output) const
366 {
367     for (auto& element : descendantsOfType<Element>(const_cast<ContainerNode&>(rootNode))) {
368         if (selectorChecker(&element)) {
369             SelectorQueryTrait::appendOutputForElement(output, &element);
370             if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
371                 return;
372         }
373     }
374 }
375 #endif // ENABLE(CSS_SELECTOR_JIT)
376
377 template <typename SelectorQueryTrait>
378 ALWAYS_INLINE void SelectorDataList::execute(ContainerNode& rootNode, typename SelectorQueryTrait::OutputType& output) const
379 {
380     ContainerNode* searchRootNode = &rootNode;
381     switch (m_matchType) {
382     case RightMostWithIdMatch:
383         if (const CSSSelector* idSelector = selectorForIdLookup(*searchRootNode, *m_selectors.first().selector)) {
384             executeFastPathForIdSelector<SelectorQueryTrait>(*searchRootNode, m_selectors.first(), idSelector, output);
385             break;
386         }
387         FALLTHROUGH;
388     case CompilableSingleWithRootFilter:
389     case CompilableSingle:
390         {
391 #if ENABLE(CSS_SELECTOR_JIT)
392         const SelectorData& selectorData = m_selectors.first();
393         ASSERT(m_matchType == RightMostWithIdMatch || selectorData.compilationStatus == SelectorCompilationStatus::NotCompiled);
394
395         JSC::VM* vm = searchRootNode->document().scriptExecutionContext()->vm();
396         selectorData.compilationStatus = SelectorCompiler::compileSelector(selectorData.selector, vm, SelectorCompiler::SelectorContext::QuerySelector, selectorData.compiledSelectorCodeRef);
397         RELEASE_ASSERT(selectorData.compilationStatus != SelectorCompilationStatus::SelectorCheckerWithCheckingContext);
398
399         if (selectorData.compilationStatus == SelectorCompilationStatus::SimpleSelectorChecker) {
400             if (m_matchType == CompilableSingle) {
401                 m_matchType = CompiledSingle;
402                 goto CompiledSingleCase;
403             }
404             if (m_matchType == CompilableSingleWithRootFilter) {
405                 m_matchType = CompiledSingleWithRootFilter;
406                 goto CompiledSingleWithRootFilterCase;
407             }
408             goto CompiledSingleCase;
409         }
410         if (m_matchType != RightMostWithIdMatch)
411             m_matchType = SingleSelector;
412         goto SingleSelectorCase;
413         ASSERT_NOT_REACHED();
414         break;
415 #else
416         FALLTHROUGH;
417 #endif // ENABLE(CSS_SELECTOR_JIT)
418         }
419     case CompiledSingleWithRootFilter:
420 #if ENABLE(CSS_SELECTOR_JIT)
421         CompiledSingleWithRootFilterCase:
422         searchRootNode = &filterRootById(*searchRootNode, *m_selectors.first().selector);
423 #endif // ENABLE(CSS_SELECTOR_JIT)
424         FALLTHROUGH;
425     case CompiledSingle:
426 #if ENABLE(CSS_SELECTOR_JIT)
427         {
428         CompiledSingleCase:
429         const SelectorData& selectorData = m_selectors.first();
430         void* compiledSelectorChecker = selectorData.compiledSelectorCodeRef.code().executableAddress();
431         SelectorCompiler::SimpleSelectorChecker selectorChecker = SelectorCompiler::simpleSelectorCheckerFunction(compiledSelectorChecker, selectorData.compilationStatus);
432         executeCompiledSimpleSelectorChecker<SelectorQueryTrait>(*searchRootNode, selectorChecker, output);
433         break;
434         }
435 #else
436         FALLTHROUGH;
437 #endif // ENABLE(CSS_SELECTOR_JIT)
438     case SingleSelector:
439 #if ENABLE(CSS_SELECTOR_JIT)
440         SingleSelectorCase:
441 #endif
442         executeSingleSelectorData<SelectorQueryTrait>(*searchRootNode, m_selectors.first(), output);
443         break;
444     case TagNameMatch:
445         executeSingleTagNameSelectorData<SelectorQueryTrait>(*searchRootNode, m_selectors.first(), output);
446         break;
447     case ClassNameMatch:
448         executeSingleClassNameSelectorData<SelectorQueryTrait>(*searchRootNode, m_selectors.first(), output);
449         break;
450     case MultipleSelectorMatch:
451         executeSingleMultiSelectorData<SelectorQueryTrait>(*searchRootNode, output);
452         break;
453     }
454 }
455
456 SelectorQuery::SelectorQuery(CSSSelectorList&& selectorList)
457     : m_selectorList(selectorList)
458     , m_selectors(m_selectorList)
459 {
460 }
461
462 SelectorQuery* SelectorQueryCache::add(const String& selectors, Document& document, ExceptionCode& ec)
463 {
464     auto it = m_entries.find(selectors);
465     if (it != m_entries.end())
466         return it->value.get();
467
468     CSSParser parser(document);
469     CSSSelectorList selectorList;
470     parser.parseSelector(selectors, selectorList);
471
472     if (!selectorList.first() || selectorList.hasInvalidSelector()) {
473         ec = SYNTAX_ERR;
474         return nullptr;
475     }
476
477     // Throw a NAMESPACE_ERR if the selector includes any namespace prefixes.
478     if (selectorList.selectorsNeedNamespaceResolution()) {
479         ec = NAMESPACE_ERR;
480         return nullptr;
481     }
482
483     const int maximumSelectorQueryCacheSize = 256;
484     if (m_entries.size() == maximumSelectorQueryCacheSize)
485         m_entries.remove(m_entries.begin());
486     
487     return m_entries.add(selectors, std::make_unique<SelectorQuery>(std::move(selectorList))).iterator->value.get();
488 }
489
490 void SelectorQueryCache::invalidate()
491 {
492     m_entries.clear();
493 }
494
495 }