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