Add WTF::move()
[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 "ElementDescendantIterator.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     return selectorChecker.match(selectorCheckingContext);
128 }
129
130 bool 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
140 struct 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
146 RefPtr<NodeList> SelectorDataList::queryAll(ContainerNode& rootNode) const
147 {
148     Vector<Ref<Element>> result;
149     execute<AllElementExtractorSelectorQueryTrait>(rootNode, result);
150     return StaticElementList::adopt(result);
151 }
152
153 struct 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
164 Element* SelectorDataList::queryFirst(ContainerNode& rootNode) const
165 {
166     Element* result = nullptr;
167     execute<SingleElementExtractorSelectorQueryTrait>(rootNode, result);
168     return result;
169 }
170
171 static 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
188 static inline bool isTreeScopeRoot(const ContainerNode& node)
189 {
190     return node.isDocumentNode() || node.isShadowRoot();
191 }
192
193 template <typename SelectorQueryTrait>
194 ALWAYS_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)
224 static 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
263 template <typename SelectorQueryTrait>
264 static 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
275 template <typename SelectorQueryTrait>
276 static 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
286 template <typename SelectorQueryTrait>
287 ALWAYS_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
316 template <typename SelectorQueryTrait>
317 ALWAYS_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
332 template <typename SelectorQueryTrait>
333 ALWAYS_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
346 template <typename SelectorQueryTrait>
347 ALWAYS_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)
363 template <typename SelectorQueryTrait>
364 ALWAYS_INLINE void SelectorDataList::executeCompiledSimpleSelectorChecker(const ContainerNode& rootNode, SelectorCompiler::SimpleSelectorChecker selectorChecker, typename SelectorQueryTrait::OutputType& output) const
365 {
366     for (auto& element : elementDescendants(const_cast<ContainerNode&>(rootNode))) {
367         if (selectorChecker(&element)) {
368             SelectorQueryTrait::appendOutputForElement(output, &element);
369             if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
370                 return;
371         }
372     }
373 }
374 #endif // ENABLE(CSS_SELECTOR_JIT)
375
376 template <typename SelectorQueryTrait>
377 ALWAYS_INLINE void SelectorDataList::execute(ContainerNode& rootNode, typename SelectorQueryTrait::OutputType& output) const
378 {
379     ContainerNode* searchRootNode = &rootNode;
380     switch (m_matchType) {
381     case RightMostWithIdMatch:
382         {
383         const SelectorData& selectorData = m_selectors.first();
384         if (const CSSSelector* idSelector = selectorForIdLookup(*searchRootNode, *selectorData.selector)) {
385             executeFastPathForIdSelector<SelectorQueryTrait>(*searchRootNode, m_selectors.first(), idSelector, output);
386             break;
387         }
388 #if ENABLE(CSS_SELECTOR_JIT)
389         if (selectorData.compilationStatus == SelectorCompilationStatus::SimpleSelectorChecker)
390             goto CompiledSingleCase;
391 #endif
392         }
393         FALLTHROUGH;
394     case CompilableSingleWithRootFilter:
395     case CompilableSingle:
396         {
397 #if ENABLE(CSS_SELECTOR_JIT)
398         const SelectorData& selectorData = m_selectors.first();
399         ASSERT(m_matchType == RightMostWithIdMatch || selectorData.compilationStatus == SelectorCompilationStatus::NotCompiled);
400
401         JSC::VM& vm = searchRootNode->document().scriptExecutionContext()->vm();
402         selectorData.compilationStatus = SelectorCompiler::compileSelector(selectorData.selector, &vm, SelectorCompiler::SelectorContext::QuerySelector, selectorData.compiledSelectorCodeRef);
403         RELEASE_ASSERT(selectorData.compilationStatus != SelectorCompilationStatus::SelectorCheckerWithCheckingContext);
404
405         if (selectorData.compilationStatus == SelectorCompilationStatus::SimpleSelectorChecker) {
406             if (m_matchType == CompilableSingle) {
407                 m_matchType = CompiledSingle;
408                 goto CompiledSingleCase;
409             }
410             if (m_matchType == CompilableSingleWithRootFilter) {
411                 m_matchType = CompiledSingleWithRootFilter;
412                 goto CompiledSingleWithRootFilterCase;
413             }
414             goto CompiledSingleCase;
415         }
416         if (m_matchType != RightMostWithIdMatch)
417             m_matchType = SingleSelector;
418         goto SingleSelectorCase;
419         ASSERT_NOT_REACHED();
420         break;
421 #else
422         FALLTHROUGH;
423 #endif // ENABLE(CSS_SELECTOR_JIT)
424         }
425     case CompiledSingleWithRootFilter:
426 #if ENABLE(CSS_SELECTOR_JIT)
427         CompiledSingleWithRootFilterCase:
428         searchRootNode = &filterRootById(*searchRootNode, *m_selectors.first().selector);
429 #endif // ENABLE(CSS_SELECTOR_JIT)
430         FALLTHROUGH;
431     case CompiledSingle:
432 #if ENABLE(CSS_SELECTOR_JIT)
433         {
434         CompiledSingleCase:
435         const SelectorData& selectorData = m_selectors.first();
436         void* compiledSelectorChecker = selectorData.compiledSelectorCodeRef.code().executableAddress();
437         SelectorCompiler::SimpleSelectorChecker selectorChecker = SelectorCompiler::simpleSelectorCheckerFunction(compiledSelectorChecker, selectorData.compilationStatus);
438         executeCompiledSimpleSelectorChecker<SelectorQueryTrait>(*searchRootNode, selectorChecker, output);
439         break;
440         }
441 #else
442         FALLTHROUGH;
443 #endif // ENABLE(CSS_SELECTOR_JIT)
444     case SingleSelector:
445 #if ENABLE(CSS_SELECTOR_JIT)
446         SingleSelectorCase:
447 #endif
448         executeSingleSelectorData<SelectorQueryTrait>(*searchRootNode, m_selectors.first(), output);
449         break;
450     case TagNameMatch:
451         executeSingleTagNameSelectorData<SelectorQueryTrait>(*searchRootNode, m_selectors.first(), output);
452         break;
453     case ClassNameMatch:
454         executeSingleClassNameSelectorData<SelectorQueryTrait>(*searchRootNode, m_selectors.first(), output);
455         break;
456     case MultipleSelectorMatch:
457         executeSingleMultiSelectorData<SelectorQueryTrait>(*searchRootNode, output);
458         break;
459     }
460 }
461
462 SelectorQuery::SelectorQuery(CSSSelectorList&& selectorList)
463     : m_selectorList(selectorList)
464     , m_selectors(m_selectorList)
465 {
466 }
467
468 SelectorQuery* SelectorQueryCache::add(const String& selectors, Document& document, ExceptionCode& ec)
469 {
470     auto it = m_entries.find(selectors);
471     if (it != m_entries.end())
472         return it->value.get();
473
474     CSSParser parser(document);
475     CSSSelectorList selectorList;
476     parser.parseSelector(selectors, selectorList);
477
478     if (!selectorList.first() || selectorList.hasInvalidSelector()) {
479         ec = SYNTAX_ERR;
480         return nullptr;
481     }
482
483     // Throw a NAMESPACE_ERR if the selector includes any namespace prefixes.
484     if (selectorList.selectorsNeedNamespaceResolution()) {
485         ec = NAMESPACE_ERR;
486         return nullptr;
487     }
488
489     const int maximumSelectorQueryCacheSize = 256;
490     if (m_entries.size() == maximumSelectorQueryCacheSize)
491         m_entries.remove(m_entries.begin());
492     
493     return m_entries.add(selectors, std::make_unique<SelectorQuery>(WTF::move(selectorList))).iterator->value.get();
494 }
495
496 }