1/*
2 * Copyright (C) 2013, 2014 Apple Inc. All rights reserved.
3 * Copyright (C) 2014 Yusuke Suzuki <utatane.tea@gmail.com>
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 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 INC. AND ITS CONTRIBUTORS ``AS IS''
15 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
16 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
17 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
18 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
19 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
20 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
21 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
22 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
23 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
24 * THE POSSIBILITY OF SUCH DAMAGE.
25 */
26
27#include "config.h"
28#include "SelectorCompiler.h"
29
30#if ENABLE(CSS_SELECTOR_JIT)
31
32#include "CSSSelector.h"
33#include "CSSSelectorList.h"
34#include "Element.h"
35#include "ElementData.h"
36#include "ElementRareData.h"
37#include "FunctionCall.h"
38#include "HTMLDocument.h"
39#include "HTMLNames.h"
40#include "InspectorInstrumentation.h"
41#include "NodeRenderStyle.h"
42#include "QualifiedName.h"
43#include "RegisterAllocator.h"
44#include "RenderElement.h"
45#include "RenderStyle.h"
46#include "SVGElement.h"
47#include "SelectorCheckerTestFunctions.h"
48#include "StackAllocator.h"
49#include "StyledElement.h"
50#include <JavaScriptCore/GPRInfo.h>
51#include <JavaScriptCore/LinkBuffer.h>
52#include <JavaScriptCore/MacroAssembler.h>
53#include <JavaScriptCore/VM.h>
54#include <limits>
55#include <wtf/HashMap.h>
56#include <wtf/HashSet.h>
57#include <wtf/Vector.h>
58#include <wtf/text/CString.h>
59
60namespace WebCore {
61namespace SelectorCompiler {
62
63#define CSS_SELECTOR_JIT_DEBUGGING 0
64
65enum class BacktrackingAction {
66    NoBacktracking,
67    JumpToDescendantEntryPoint,
68    JumpToIndirectAdjacentEntryPoint,
69    JumpToDescendantTreeWalkerEntryPoint,
70    JumpToIndirectAdjacentTreeWalkerEntryPoint,
71    JumpToDescendantTail,
72    JumpToDirectAdjacentTail
73};
74
75struct BacktrackingFlag {
76    enum {
77        DescendantEntryPoint = 1,
78        IndirectAdjacentEntryPoint = 1 << 1,
79        SaveDescendantBacktrackingStart = 1 << 2,
80        SaveAdjacentBacktrackingStart = 1 << 3,
81        DirectAdjacentTail = 1 << 4,
82        DescendantTail = 1 << 5,
83        InChainWithDescendantTail = 1 << 6
84    };
85};
86
87enum class FragmentRelation {
88    Rightmost,
89    Descendant,
90    Child,
91    DirectAdjacent,
92    IndirectAdjacent
93};
94
95enum class FunctionType {
96    SimpleSelectorChecker,
97    SelectorCheckerWithCheckingContext,
98    CannotMatchAnything,
99    CannotCompile
100};
101
102enum class FragmentPositionInRootFragments {
103    Rightmost,
104    NotRightmost
105};
106
107class AttributeMatchingInfo {
108public:
109    AttributeMatchingInfo(const CSSSelector* selector, bool canDefaultToCaseSensitiveValueMatch)
110        : m_selector(selector)
111        , m_canDefaultToCaseSensitiveValueMatch(canDefaultToCaseSensitiveValueMatch)
112    {
113    }
114
115    bool canDefaultToCaseSensitiveValueMatch() const { return m_canDefaultToCaseSensitiveValueMatch; }
116    const CSSSelector& selector() const { return *m_selector; }
117
118private:
119    const CSSSelector* m_selector;
120    bool m_canDefaultToCaseSensitiveValueMatch;
121};
122
123static const unsigned invalidHeight = std::numeric_limits<unsigned>::max();
124static const unsigned invalidWidth = std::numeric_limits<unsigned>::max();
125
126struct SelectorFragment {
127    SelectorFragment()
128        : traversalBacktrackingAction(BacktrackingAction::NoBacktracking)
129        , matchingTagNameBacktrackingAction(BacktrackingAction::NoBacktracking)
130        , matchingPostTagNameBacktrackingAction(BacktrackingAction::NoBacktracking)
131        , backtrackingFlags(0)
132        , tagNameMatchedBacktrackingStartHeightFromDescendant(invalidHeight)
133        , tagNameNotMatchedBacktrackingStartHeightFromDescendant(invalidHeight)
134        , heightFromDescendant(0)
135        , tagNameMatchedBacktrackingStartWidthFromIndirectAdjacent(invalidWidth)
136        , tagNameNotMatchedBacktrackingStartWidthFromIndirectAdjacent(invalidWidth)
137        , widthFromIndirectAdjacent(0)
138        , tagName(nullptr)
139        , id(nullptr)
140        , langFilter(nullptr)
141        , onlyMatchesLinksInQuirksMode(true)
142    {
143    }
144    FragmentRelation relationToLeftFragment;
145    FragmentRelation relationToRightFragment;
146    FragmentPositionInRootFragments positionInRootFragments;
147
148    BacktrackingAction traversalBacktrackingAction;
149    BacktrackingAction matchingTagNameBacktrackingAction;
150    BacktrackingAction matchingPostTagNameBacktrackingAction;
151    unsigned char backtrackingFlags;
152    unsigned tagNameMatchedBacktrackingStartHeightFromDescendant;
153    unsigned tagNameNotMatchedBacktrackingStartHeightFromDescendant;
154    unsigned heightFromDescendant;
155    unsigned tagNameMatchedBacktrackingStartWidthFromIndirectAdjacent;
156    unsigned tagNameNotMatchedBacktrackingStartWidthFromIndirectAdjacent;
157    unsigned widthFromIndirectAdjacent;
158
159    const QualifiedName* tagName;
160    const AtomicString* id;
161    const AtomicString* langFilter;
162    Vector<const AtomicStringImpl*, 32> classNames;
163    HashSet<unsigned> pseudoClasses;
164    Vector<JSC::FunctionPtr, 32> unoptimizedPseudoClasses;
165    Vector<AttributeMatchingInfo, 32> attributes;
166    Vector<std::pair<int, int>, 32> nthChildFilters;
167    Vector<SelectorFragment> notFilters;
168    Vector<Vector<SelectorFragment>> anyFilters;
169
170    // For quirks mode, follow this: http://quirks.spec.whatwg.org/#the-:active-and-:hover-quirk
171    // In quirks mode, a compound selector 'selector' that matches the following conditions must not match elements that would not also match the ':any-link' selector.
172    //
173    //    selector uses the ':active' or ':hover' pseudo-classes.
174    //    selector does not use a type selector.
175    //    selector does not use an attribute selector.
176    //    selector does not use an ID selector.
177    //    selector does not use a class selector.
178    //    selector does not use a pseudo-class selector other than ':active' and ':hover'.
179    //    selector does not use a pseudo-element selector.
180    //    selector is not part of an argument to a functional pseudo-class or pseudo-element.
181    bool onlyMatchesLinksInQuirksMode;
182};
183
184struct TagNamePattern {
185    TagNamePattern()
186        : tagName(nullptr)
187        , inverted(false)
188    {
189    }
190    const QualifiedName* tagName;
191    bool inverted;
192};
193
194typedef JSC::MacroAssembler Assembler;
195typedef Vector<SelectorFragment, 32> SelectorFragmentList;
196typedef Vector<TagNamePattern, 32> TagNameList;
197
198class SelectorCodeGenerator {
199public:
200    SelectorCodeGenerator(const CSSSelector*, SelectorContext);
201    SelectorCompilationStatus compile(JSC::VM*, JSC::MacroAssemblerCodeRef&);
202
203private:
204    static const Assembler::RegisterID returnRegister;
205    static const Assembler::RegisterID elementAddressRegister;
206    static const Assembler::RegisterID checkingContextRegister;
207    static const Assembler::RegisterID callFrameRegister;
208
209    void generateSelectorChecker();
210
211    // Element relations tree walker.
212    void generateWalkToParentNode(Assembler::RegisterID targetRegister);
213    void generateWalkToParentElement(Assembler::JumpList& failureCases, Assembler::RegisterID targetRegister);
214    void generateParentElementTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment&);
215    void generateAncestorTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment&);
216
217    void generateWalkToNextAdjacentElement(Assembler::JumpList& failureCases, Assembler::RegisterID);
218    void generateWalkToPreviousAdjacentElement(Assembler::JumpList& failureCases, Assembler::RegisterID);
219    void generateWalkToPreviousAdjacent(Assembler::JumpList& failureCases, const SelectorFragment&);
220    void generateDirectAdjacentTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment&);
221    void generateIndirectAdjacentTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment&);
222    void markParentElementIfResolvingStyle(int32_t);
223    void markParentElementIfResolvingStyle(JSC::FunctionPtr);
224
225    void linkFailures(Assembler::JumpList& globalFailureCases, BacktrackingAction, Assembler::JumpList& localFailureCases);
226    void generateAdjacentBacktrackingTail();
227    void generateDescendantBacktrackingTail();
228    void generateBacktrackingTailsIfNeeded(Assembler::JumpList& failureCases, const SelectorFragment&);
229
230    // Element properties matchers.
231    void generateElementMatching(Assembler::JumpList& matchingTagNameFailureCases, Assembler::JumpList& matchingPostTagNameFailureCases, const SelectorFragment&);
232    void generateElementDataMatching(Assembler::JumpList& failureCases, const SelectorFragment&);
233    void generateElementFunctionCallTest(Assembler::JumpList& failureCases, JSC::FunctionPtr);
234    void generateElementIsActive(Assembler::JumpList& failureCases, const SelectorFragment&);
235    void generateElementIsFirstChild(Assembler::JumpList& failureCases, const SelectorFragment&);
236    void generateElementIsHovered(Assembler::JumpList& failureCases, const SelectorFragment&);
237    void generateElementIsInLanguage(Assembler::JumpList& failureCases, const AtomicString&);
238    void generateElementIsLastChild(Assembler::JumpList& failureCases, const SelectorFragment&);
239    void generateElementIsOnlyChild(Assembler::JumpList& failureCases, const SelectorFragment&);
240    void generateSynchronizeStyleAttribute(Assembler::RegisterID elementDataArraySizeAndFlags);
241    void generateSynchronizeAllAnimatedSVGAttribute(Assembler::RegisterID elementDataArraySizeAndFlags);
242    void generateElementAttributesMatching(Assembler::JumpList& failureCases, const LocalRegister& elementDataAddress, const SelectorFragment&);
243    void generateElementAttributeMatching(Assembler::JumpList& failureCases, Assembler::RegisterID currentAttributeAddress, Assembler::RegisterID decIndexRegister, const AttributeMatchingInfo& attributeInfo);
244    void generateElementAttributeValueMatching(Assembler::JumpList& failureCases, Assembler::RegisterID currentAttributeAddress, const AttributeMatchingInfo& attributeInfo);
245    void generateElementAttributeValueExactMatching(Assembler::JumpList& failureCases, Assembler::RegisterID currentAttributeAddress, const AtomicString& expectedValue, bool caseSensitive);
246    void generateElementAttributeFunctionCallValueMatching(Assembler::JumpList& failureCases, Assembler::RegisterID currentAttributeAddress, const AtomicString& expectedValue, bool caseSensitive, JSC::FunctionPtr caseSensitiveTest, JSC::FunctionPtr caseInsensitiveTest);
247    void generateElementHasTagName(Assembler::JumpList& failureCases, const QualifiedName& nameToMatch);
248    void generateElementHasId(Assembler::JumpList& failureCases, const LocalRegister& elementDataAddress, const AtomicString& idToMatch);
249    void generateElementHasClasses(Assembler::JumpList& failureCases, const LocalRegister& elementDataAddress, const Vector<const AtomicStringImpl*>& classNames);
250    void generateElementIsLink(Assembler::JumpList& failureCases);
251    void generateElementIsNthChild(Assembler::JumpList& failureCases, const SelectorFragment&);
252    void generateElementMatchesNotPseudoClass(Assembler::JumpList& failureCases, const SelectorFragment&);
253    void generateElementMatchesAnyPseudoClass(Assembler::JumpList& failureCases, const SelectorFragment&);
254    void generateElementIsRoot(Assembler::JumpList& failureCases);
255    void generateElementIsTarget(Assembler::JumpList& failureCases);
256
257    // Helpers.
258    void addFlagsToElementStyleFromContext(Assembler::RegisterID checkingContext, int64_t);
259    Assembler::JumpList jumpIfNoPreviousAdjacentElement();
260    Assembler::JumpList jumpIfNoNextAdjacentElement();
261    Assembler::Jump jumpIfNotResolvingStyle(Assembler::RegisterID checkingContextRegister);
262    void generateSpecialFailureInQuirksModeForActiveAndHoverIfNeeded(Assembler::JumpList& failureCases, const SelectorFragment&);
263    Assembler::Jump modulo(JSC::MacroAssembler::ResultCondition, Assembler::RegisterID inputDividend, int divisor);
264    void moduloIsZero(Assembler::JumpList& failureCases, Assembler::RegisterID inputDividend, int divisor);
265
266    bool generatePrologue();
267    void generateEpilogue();
268    StackAllocator::StackReferenceVector m_prologueStackReferences;
269
270    Assembler m_assembler;
271    RegisterAllocator m_registerAllocator;
272    StackAllocator m_stackAllocator;
273    Vector<std::pair<Assembler::Call, JSC::FunctionPtr>, 32> m_functionCalls;
274
275    SelectorContext m_selectorContext;
276    FunctionType m_functionType;
277    SelectorFragmentList m_selectorFragments;
278    bool m_needsAdjacentBacktrackingStart;
279
280    StackAllocator::StackReference m_checkingContextStackReference;
281
282    Assembler::Label m_descendantEntryPoint;
283    Assembler::Label m_indirectAdjacentEntryPoint;
284    Assembler::Label m_descendantTreeWalkerBacktrackingPoint;
285    Assembler::Label m_indirectAdjacentTreeWalkerBacktrackingPoint;
286    Assembler::RegisterID m_descendantBacktrackingStart;
287    Assembler::JumpList m_descendantBacktrackingFailureCases;
288    StackAllocator::StackReference m_adjacentBacktrackingStart;
289    Assembler::JumpList m_adjacentBacktrackingFailureCases;
290
291#if CSS_SELECTOR_JIT_DEBUGGING
292    const CSSSelector* m_originalSelector;
293#endif
294};
295
296const Assembler::RegisterID SelectorCodeGenerator::returnRegister = JSC::GPRInfo::returnValueGPR;
297const Assembler::RegisterID SelectorCodeGenerator::elementAddressRegister = JSC::GPRInfo::argumentGPR0;
298const Assembler::RegisterID SelectorCodeGenerator::checkingContextRegister = JSC::GPRInfo::argumentGPR1;
299const Assembler::RegisterID SelectorCodeGenerator::callFrameRegister = JSC::GPRInfo::callFrameRegister;
300
301enum class FragmentsLevel {
302    Root = 0,
303    InFunctionalPseudoType = 1
304};
305
306static FunctionType constructFragments(const CSSSelector* rootSelector, SelectorContext, SelectorFragmentList& selectorFragments, FragmentsLevel, FragmentPositionInRootFragments);
307
308static void computeBacktrackingInformation(SelectorFragmentList& selectorFragments, bool& needsAdjacentBacktrackingStart);
309
310SelectorCompilationStatus compileSelector(const CSSSelector* lastSelector, JSC::VM* vm, SelectorContext selectorContext, JSC::MacroAssemblerCodeRef& codeRef)
311{
312    if (!vm->canUseJIT())
313        return SelectorCompilationStatus::CannotCompile;
314    SelectorCodeGenerator codeGenerator(lastSelector, selectorContext);
315    return codeGenerator.compile(vm, codeRef);
316}
317
318static inline FragmentRelation fragmentRelationForSelectorRelation(CSSSelector::Relation relation)
319{
320    switch (relation) {
321    case CSSSelector::Descendant:
322        return FragmentRelation::Descendant;
323    case CSSSelector::Child:
324        return FragmentRelation::Child;
325    case CSSSelector::DirectAdjacent:
326        return FragmentRelation::DirectAdjacent;
327    case CSSSelector::IndirectAdjacent:
328        return FragmentRelation::IndirectAdjacent;
329    case CSSSelector::SubSelector:
330    case CSSSelector::ShadowDescendant:
331        ASSERT_NOT_REACHED();
332    }
333    ASSERT_NOT_REACHED();
334    return FragmentRelation::Descendant;
335}
336
337static inline FunctionType mostRestrictiveFunctionType(FunctionType a, FunctionType b)
338{
339    return std::max(a, b);
340}
341
342static inline bool shouldUseRenderStyleFromCheckingContext(const SelectorFragment& fragment)
343{
344    // Return true if the position of this fragment is Rightmost in the root fragments.
345    // In this case, we should use the RenderStyle stored in the CheckingContext.
346    return fragment.relationToRightFragment == FragmentRelation::Rightmost && fragment.positionInRootFragments == FragmentPositionInRootFragments::Rightmost;
347}
348
349static inline FunctionType addPseudoClassType(const CSSSelector& selector, SelectorFragment& fragment, SelectorContext selectorContext, FragmentPositionInRootFragments positionInRootFragments)
350{
351    CSSSelector::PseudoClassType type = selector.pseudoClassType();
352    switch (type) {
353    // Unoptimized pseudo selector. They are just function call to a simple testing function.
354    case CSSSelector::PseudoClassAutofill:
355        fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isAutofilled));
356        return FunctionType::SimpleSelectorChecker;
357    case CSSSelector::PseudoClassChecked:
358        fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isChecked));
359        return FunctionType::SimpleSelectorChecker;
360    case CSSSelector::PseudoClassDefault:
361        fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isDefaultButtonForForm));
362        return FunctionType::SimpleSelectorChecker;
363    case CSSSelector::PseudoClassDisabled:
364        fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isDisabled));
365        return FunctionType::SimpleSelectorChecker;
366    case CSSSelector::PseudoClassEnabled:
367        fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isEnabled));
368        return FunctionType::SimpleSelectorChecker;
369    case CSSSelector::PseudoClassFocus:
370        fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(SelectorChecker::matchesFocusPseudoClass));
371        return FunctionType::SimpleSelectorChecker;
372    case CSSSelector::PseudoClassInRange:
373        fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isInRange));
374        return FunctionType::SimpleSelectorChecker;
375    case CSSSelector::PseudoClassIndeterminate:
376        fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(shouldAppearIndeterminate));
377        return FunctionType::SimpleSelectorChecker;
378    case CSSSelector::PseudoClassInvalid:
379        fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isInvalid));
380        return FunctionType::SimpleSelectorChecker;
381    case CSSSelector::PseudoClassOptional:
382        fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isOptionalFormControl));
383        return FunctionType::SimpleSelectorChecker;
384    case CSSSelector::PseudoClassOutOfRange:
385        fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isOutOfRange));
386        return FunctionType::SimpleSelectorChecker;
387    case CSSSelector::PseudoClassReadOnly:
388        fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesReadOnlyPseudoClass));
389        return FunctionType::SimpleSelectorChecker;
390    case CSSSelector::PseudoClassReadWrite:
391        fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesReadWritePseudoClass));
392        return FunctionType::SimpleSelectorChecker;
393    case CSSSelector::PseudoClassRequired:
394        fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isRequiredFormControl));
395        return FunctionType::SimpleSelectorChecker;
396    case CSSSelector::PseudoClassValid:
397        fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isValid));
398        return FunctionType::SimpleSelectorChecker;
399#if ENABLE(FULLSCREEN_API)
400    case CSSSelector::PseudoClassFullScreen:
401        fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesFullScreenPseudoClass));
402        return FunctionType::SimpleSelectorChecker;
403#endif
404#if ENABLE(VIDEO_TRACK)
405    case CSSSelector::PseudoClassFuture:
406        fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesFutureCuePseudoClass));
407        return FunctionType::SimpleSelectorChecker;
408    case CSSSelector::PseudoClassPast:
409        fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesPastCuePseudoClass));
410        return FunctionType::SimpleSelectorChecker;
411#endif
412
413    // Optimized pseudo selectors.
414    case CSSSelector::PseudoClassAnyLink:
415        fragment.pseudoClasses.add(CSSSelector::PseudoClassLink);
416        return FunctionType::SimpleSelectorChecker;
417
418    case CSSSelector::PseudoClassLink:
419    case CSSSelector::PseudoClassRoot:
420    case CSSSelector::PseudoClassTarget:
421        fragment.pseudoClasses.add(type);
422        return FunctionType::SimpleSelectorChecker;
423
424    case CSSSelector::PseudoClassActive:
425    case CSSSelector::PseudoClassFirstChild:
426    case CSSSelector::PseudoClassHover:
427    case CSSSelector::PseudoClassLastChild:
428    case CSSSelector::PseudoClassOnlyChild:
429        fragment.pseudoClasses.add(type);
430        if (selectorContext == SelectorContext::QuerySelector)
431            return FunctionType::SimpleSelectorChecker;
432        return FunctionType::SelectorCheckerWithCheckingContext;
433
434    case CSSSelector::PseudoClassNthChild:
435        {
436            if (!selector.parseNth())
437                return FunctionType::CannotMatchAnything;
438
439            int a = selector.nthA();
440            int b = selector.nthB();
441
442            // The element count is always positive.
443            if (a <= 0 && b < 1)
444                return FunctionType::CannotMatchAnything;
445
446            fragment.nthChildFilters.append(std::pair<int, int>(a, b));
447            if (selectorContext == SelectorContext::QuerySelector)
448                return FunctionType::SimpleSelectorChecker;
449            return FunctionType::SelectorCheckerWithCheckingContext;
450        }
451
452    case CSSSelector::PseudoClassNot:
453        {
454            const CSSSelectorList* selectorList = selector.selectorList();
455
456            if (!selectorList)
457                return FunctionType::CannotMatchAnything;
458
459            SelectorFragmentList notFragments;
460            FunctionType functionType = constructFragments(selectorList->first(), selectorContext, notFragments, FragmentsLevel::InFunctionalPseudoType, positionInRootFragments);
461
462            // Since this is not pseudo class filter, CannotMatchAnything implies this filter always passes.
463            if (functionType == FunctionType::CannotMatchAnything)
464                return FunctionType::SimpleSelectorChecker;
465
466            if (functionType == FunctionType::CannotCompile)
467                return functionType;
468
469            ASSERT(notFragments.size() == 1);
470            if (notFragments.size() != 1)
471                return FunctionType::CannotCompile;
472
473            const SelectorFragment& subFragment = notFragments.first();
474
475            // FIXME: Currently we don't support visitedMatchType.
476            if (subFragment.pseudoClasses.contains(CSSSelector::PseudoClassLink))
477                return FunctionType::CannotCompile;
478
479            fragment.notFilters.append(subFragment);
480            return functionType;
481        }
482
483    case CSSSelector::PseudoClassAny:
484        {
485            Vector<SelectorFragment, 32> anyFragments;
486            FunctionType functionType = FunctionType::SimpleSelectorChecker;
487            for (const CSSSelector* rootSelector = selector.selectorList()->first(); rootSelector; rootSelector = CSSSelectorList::next(rootSelector)) {
488                SelectorFragmentList fragmentList;
489                FunctionType subFunctionType = constructFragments(rootSelector, selectorContext, fragmentList, FragmentsLevel::InFunctionalPseudoType, positionInRootFragments);
490
491                // Since this fragment always unmatch against the element, don't insert it to anyFragments.
492                if (subFunctionType == FunctionType::CannotMatchAnything)
493                    continue;
494
495                if (subFunctionType == FunctionType::CannotCompile)
496                    return FunctionType::CannotCompile;
497
498                // :any() may not contain complex selectors which have combinators.
499                ASSERT(fragmentList.size() == 1);
500                if (fragmentList.size() != 1)
501                    return FunctionType::CannotCompile;
502
503                const SelectorFragment& subFragment = fragmentList.first();
504                anyFragments.append(subFragment);
505                functionType = mostRestrictiveFunctionType(functionType, subFunctionType);
506            }
507
508            // Since all fragments in :any() cannot match anything, this :any() filter cannot match anything.
509            if (anyFragments.isEmpty())
510                return FunctionType::CannotMatchAnything;
511
512            ASSERT(!anyFragments.isEmpty());
513            fragment.anyFilters.append(anyFragments);
514
515            return functionType;
516        }
517    case CSSSelector::PseudoClassLang:
518        {
519            const AtomicString& argument = selector.argument();
520            if (argument.isEmpty())
521                return FunctionType::CannotMatchAnything;
522
523            if (!fragment.langFilter)
524                fragment.langFilter = &argument;
525            else if (*fragment.langFilter != argument) {
526                // If there are multiple definition, we only care about the most restrictive one.
527                if (argument.startsWith(*fragment.langFilter, false))
528                    fragment.langFilter = &argument;
529                else if (fragment.langFilter->startsWith(argument, false))
530                    { } // The existing filter is more restrictive.
531                else
532                    return FunctionType::CannotMatchAnything;
533            }
534            return FunctionType::SimpleSelectorChecker;
535        }
536
537    default:
538        break;
539    }
540    return FunctionType::CannotCompile;
541}
542
543inline SelectorCodeGenerator::SelectorCodeGenerator(const CSSSelector* rootSelector, SelectorContext selectorContext)
544    : m_stackAllocator(m_assembler)
545    , m_selectorContext(selectorContext)
546    , m_functionType(FunctionType::SimpleSelectorChecker)
547    , m_needsAdjacentBacktrackingStart(false)
548#if CSS_SELECTOR_JIT_DEBUGGING
549    , m_originalSelector(rootSelector)
550#endif
551{
552#if CSS_SELECTOR_JIT_DEBUGGING
553    dataLogF("Compiling \"%s\"\n", m_originalSelector->selectorText().utf8().data());
554#endif
555
556    m_functionType = constructFragments(rootSelector, m_selectorContext, m_selectorFragments, FragmentsLevel::Root, FragmentPositionInRootFragments::Rightmost);
557    if (m_functionType != FunctionType::CannotCompile && m_functionType != FunctionType::CannotMatchAnything)
558        computeBacktrackingInformation(m_selectorFragments, m_needsAdjacentBacktrackingStart);
559}
560
561static bool pseudoClassOnlyMatchesLinksInQuirksMode(const CSSSelector& selector)
562{
563    CSSSelector::PseudoClassType pseudoClassType = selector.pseudoClassType();
564    return pseudoClassType == CSSSelector::PseudoClassHover || pseudoClassType == CSSSelector::PseudoClassActive;
565}
566
567static FunctionType constructFragments(const CSSSelector* rootSelector, SelectorContext selectorContext, SelectorFragmentList& selectorFragments, FragmentsLevel fragmentLevel, FragmentPositionInRootFragments positionInRootFragments)
568{
569    SelectorFragment fragment;
570    FragmentRelation relationToPreviousFragment = FragmentRelation::Rightmost;
571    FunctionType functionType = FunctionType::SimpleSelectorChecker;
572    for (const CSSSelector* selector = rootSelector; selector; selector = selector->tagHistory()) {
573        switch (selector->m_match) {
574        case CSSSelector::Tag:
575            ASSERT(!fragment.tagName);
576            fragment.tagName = &(selector->tagQName());
577            if (*fragment.tagName != anyQName())
578                fragment.onlyMatchesLinksInQuirksMode = false;
579            break;
580        case CSSSelector::Id: {
581            const AtomicString& id = selector->value();
582            if (fragment.id) {
583                if (id != *fragment.id)
584                    return FunctionType::CannotMatchAnything;
585            } else
586                fragment.id = &(selector->value());
587            fragment.onlyMatchesLinksInQuirksMode = false;
588            break;
589        }
590        case CSSSelector::Class:
591            fragment.classNames.append(selector->value().impl());
592            fragment.onlyMatchesLinksInQuirksMode = false;
593            break;
594        case CSSSelector::PseudoClass: {
595            FragmentPositionInRootFragments subPosition = positionInRootFragments;
596            if (relationToPreviousFragment != FragmentRelation::Rightmost)
597                subPosition = FragmentPositionInRootFragments::NotRightmost;
598
599            functionType = mostRestrictiveFunctionType(functionType, addPseudoClassType(*selector, fragment, selectorContext, subPosition));
600            if (!pseudoClassOnlyMatchesLinksInQuirksMode(*selector))
601                fragment.onlyMatchesLinksInQuirksMode = false;
602            if (functionType == FunctionType::CannotCompile || functionType == FunctionType::CannotMatchAnything)
603                return functionType;
604            break;
605        }
606
607        case CSSSelector::List:
608            if (selector->value().contains(' '))
609                return FunctionType::CannotMatchAnything;
610            FALLTHROUGH;
611        case CSSSelector::Begin:
612        case CSSSelector::End:
613        case CSSSelector::Contain:
614            if (selector->value().isEmpty())
615                return FunctionType::CannotMatchAnything;
616            FALLTHROUGH;
617        case CSSSelector::Exact:
618        case CSSSelector::Hyphen:
619            fragment.onlyMatchesLinksInQuirksMode = false;
620            fragment.attributes.append(AttributeMatchingInfo(selector, HTMLDocument::isCaseSensitiveAttribute(selector->attribute())));
621            break;
622
623        case CSSSelector::Set:
624            fragment.onlyMatchesLinksInQuirksMode = false;
625            fragment.attributes.append(AttributeMatchingInfo(selector, true));
626            break;
627        case CSSSelector::PagePseudoClass:
628            fragment.onlyMatchesLinksInQuirksMode = false;
629            // Pseudo page class are only relevant for style resolution, they are ignored for matching.
630            break;
631        case CSSSelector::Unknown:
632            ASSERT_NOT_REACHED();
633            return FunctionType::CannotMatchAnything;
634        case CSSSelector::PseudoElement:
635            fragment.onlyMatchesLinksInQuirksMode = false;
636            return FunctionType::CannotCompile;
637        }
638
639        CSSSelector::Relation relation = selector->relation();
640        if (relation == CSSSelector::SubSelector)
641            continue;
642
643        if (relation == CSSSelector::ShadowDescendant && !selector->isLastInTagHistory())
644            return FunctionType::CannotCompile;
645
646        if (relation == CSSSelector::DirectAdjacent || relation == CSSSelector::IndirectAdjacent) {
647            FunctionType relationFunctionType = FunctionType::SelectorCheckerWithCheckingContext;
648            if (selectorContext == SelectorContext::QuerySelector)
649                relationFunctionType = FunctionType::SimpleSelectorChecker;
650            functionType = mostRestrictiveFunctionType(functionType, relationFunctionType);
651        }
652
653        fragment.relationToLeftFragment = fragmentRelationForSelectorRelation(relation);
654        fragment.relationToRightFragment = relationToPreviousFragment;
655        fragment.positionInRootFragments = positionInRootFragments;
656        relationToPreviousFragment = fragment.relationToLeftFragment;
657
658        if (fragmentLevel == FragmentsLevel::InFunctionalPseudoType)
659            fragment.onlyMatchesLinksInQuirksMode = false;
660        selectorFragments.append(fragment);
661        fragment = SelectorFragment();
662    }
663    return functionType;
664}
665
666static inline bool attributeNameTestingRequiresNamespaceRegister(const CSSSelector& attributeSelector)
667{
668    return attributeSelector.attribute().prefix() != starAtom && !attributeSelector.attribute().namespaceURI().isNull();
669}
670
671static inline bool attributeValueTestingRequiresCaseFoldingRegister(const AttributeMatchingInfo& attributeInfo)
672{
673    return !attributeInfo.canDefaultToCaseSensitiveValueMatch();
674}
675
676// Strict minimum to match anything interesting:
677// Element + BacktrackingRegister + ElementData + a pointer to values + an index on that pointer + the value we expect;
678static const unsigned minimumRequiredRegisterCount = 6;
679// Element + ElementData + scratchRegister + attributeArrayPointer + expectedLocalName + (qualifiedNameImpl && expectedValue).
680static const unsigned minimumRequiredRegisterCountForAttributeFilter = 6;
681
682static inline unsigned minimumRegisterRequirements(const SelectorFragment& selectorFragment)
683{
684    unsigned minimum = minimumRequiredRegisterCount;
685    const Vector<AttributeMatchingInfo>& attributes = selectorFragment.attributes;
686
687    unsigned backtrackingRegisterRequirements = 0;
688    if (selectorFragment.backtrackingFlags & BacktrackingFlag::InChainWithDescendantTail)
689        backtrackingRegisterRequirements = 1; // If there is a DescendantTail, there is a backtracking register.
690
691    // Attributes cause some register pressure.
692    unsigned attributeCount = attributes.size();
693    for (unsigned attributeIndex = 0; attributeIndex < attributeCount; ++attributeIndex) {
694        unsigned attributeMinimum = minimumRequiredRegisterCountForAttributeFilter + backtrackingRegisterRequirements;
695
696        if (attributeIndex + 1 < attributeCount)
697            attributeMinimum += 2; // For the local copy of the counter and attributeArrayPointer.
698
699        const AttributeMatchingInfo& attributeInfo = attributes[attributeIndex];
700        const CSSSelector& attributeSelector = attributeInfo.selector();
701        if (attributeNameTestingRequiresNamespaceRegister(attributeSelector)
702            || attributeValueTestingRequiresCaseFoldingRegister(attributeInfo))
703            attributeMinimum += 1;
704
705        minimum = std::max(minimum, attributeMinimum);
706    }
707
708    // :not pseudo class filters cause some register pressure.
709    for (const SelectorFragment& subFragment : selectorFragment.notFilters) {
710        unsigned notFilterMinimum = minimumRegisterRequirements(subFragment) + backtrackingRegisterRequirements;
711        minimum = std::max(minimum, notFilterMinimum);
712    }
713
714    // :any pseudo class filters cause some register pressure.
715    for (const auto& subFragments : selectorFragment.anyFilters) {
716        for (const SelectorFragment& subFragment : subFragments) {
717            unsigned anyFilterMinimum = minimumRegisterRequirements(subFragment) + backtrackingRegisterRequirements;
718            minimum = std::max(minimum, anyFilterMinimum);
719        }
720    }
721
722    return minimum;
723}
724
725static inline unsigned minimumRegisterRequirements(const SelectorFragmentList& selectorFragments)
726{
727    unsigned minimum = minimumRequiredRegisterCount;
728
729    for (unsigned selectorFragmentIndex = 0; selectorFragmentIndex < selectorFragments.size(); ++selectorFragmentIndex) {
730        const SelectorFragment& selectorFragment = selectorFragments[selectorFragmentIndex];
731        minimum = std::max(minimum, minimumRegisterRequirements(selectorFragment));
732    }
733
734    return minimum;
735}
736
737inline SelectorCompilationStatus SelectorCodeGenerator::compile(JSC::VM* vm, JSC::MacroAssemblerCodeRef& codeRef)
738{
739    switch (m_functionType) {
740    case FunctionType::SimpleSelectorChecker:
741    case FunctionType::SelectorCheckerWithCheckingContext:
742        generateSelectorChecker();
743        break;
744    case FunctionType::CannotMatchAnything:
745        m_assembler.move(Assembler::TrustedImm32(0), returnRegister);
746        m_assembler.ret();
747        break;
748    case FunctionType::CannotCompile:
749        return SelectorCompilationStatus::CannotCompile;
750    }
751
752    JSC::LinkBuffer linkBuffer(*vm, m_assembler, CSS_CODE_ID);
753    for (unsigned i = 0; i < m_functionCalls.size(); i++)
754        linkBuffer.link(m_functionCalls[i].first, m_functionCalls[i].second);
755
756#if CSS_SELECTOR_JIT_DEBUGGING
757    codeRef = linkBuffer.finalizeCodeWithDisassembly("CSS Selector JIT for \"%s\"", m_originalSelector->selectorText().utf8().data());
758#else
759    codeRef = FINALIZE_CODE(linkBuffer, ("CSS Selector JIT"));
760#endif
761
762    if (m_functionType == FunctionType::SimpleSelectorChecker || m_functionType == FunctionType::CannotMatchAnything)
763        return SelectorCompilationStatus::SimpleSelectorChecker;
764    return SelectorCompilationStatus::SelectorCheckerWithCheckingContext;
765}
766
767
768static inline void updateChainStates(const SelectorFragment& fragment, bool& hasDescendantRelationOnTheRight, unsigned& ancestorPositionSinceDescendantRelation, bool& hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain, unsigned& adjacentPositionSinceIndirectAdjacentTreeWalk)
769{
770    switch (fragment.relationToRightFragment) {
771    case FragmentRelation::Rightmost:
772        break;
773    case FragmentRelation::Descendant:
774        hasDescendantRelationOnTheRight = true;
775        ancestorPositionSinceDescendantRelation = 0;
776        hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain = false;
777        break;
778    case FragmentRelation::Child:
779        if (hasDescendantRelationOnTheRight)
780            ++ancestorPositionSinceDescendantRelation;
781        hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain = false;
782        break;
783    case FragmentRelation::DirectAdjacent:
784        if (hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain)
785            ++adjacentPositionSinceIndirectAdjacentTreeWalk;
786        break;
787    case FragmentRelation::IndirectAdjacent:
788        hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain = true;
789        adjacentPositionSinceIndirectAdjacentTreeWalk = 0;
790        break;
791    }
792}
793
794static inline bool isFirstAncestor(unsigned ancestorPositionSinceDescendantRelation)
795{
796    return ancestorPositionSinceDescendantRelation == 1;
797}
798
799static inline bool isFirstAdjacent(unsigned adjacentPositionSinceIndirectAdjacentTreeWalk)
800{
801    return adjacentPositionSinceIndirectAdjacentTreeWalk == 1;
802}
803
804static inline BacktrackingAction solveDescendantBacktrackingActionForChild(const SelectorFragment& fragment, unsigned backtrackingStartHeightFromDescendant)
805{
806    // If height is invalid (e.g. There's no tag name).
807    if (backtrackingStartHeightFromDescendant == invalidHeight)
808        return BacktrackingAction::NoBacktracking;
809
810    // Start backtracking from the current element.
811    if (backtrackingStartHeightFromDescendant == fragment.heightFromDescendant)
812        return BacktrackingAction::JumpToDescendantEntryPoint;
813
814    // Start backtracking from the parent of current element.
815    if (backtrackingStartHeightFromDescendant == (fragment.heightFromDescendant + 1))
816        return BacktrackingAction::JumpToDescendantTreeWalkerEntryPoint;
817
818    return BacktrackingAction::JumpToDescendantTail;
819}
820
821static inline BacktrackingAction solveAdjacentBacktrackingActionForDirectAdjacent(const SelectorFragment& fragment, unsigned backtrackingStartWidthFromIndirectAdjacent)
822{
823    // If width is invalid (e.g. There's no tag name).
824    if (backtrackingStartWidthFromIndirectAdjacent == invalidWidth)
825        return BacktrackingAction::NoBacktracking;
826
827    // Start backtracking from the current element.
828    if (backtrackingStartWidthFromIndirectAdjacent == fragment.widthFromIndirectAdjacent)
829        return BacktrackingAction::JumpToIndirectAdjacentEntryPoint;
830
831    // Start backtracking from the previous adjacent of current element.
832    if (backtrackingStartWidthFromIndirectAdjacent == (fragment.widthFromIndirectAdjacent + 1))
833        return BacktrackingAction::JumpToIndirectAdjacentTreeWalkerEntryPoint;
834
835    return BacktrackingAction::JumpToDirectAdjacentTail;
836}
837
838static inline BacktrackingAction solveAdjacentTraversalBacktrackingAction(const SelectorFragment& fragment, bool hasDescendantRelationOnTheRight)
839{
840    if (!hasDescendantRelationOnTheRight)
841        return BacktrackingAction::NoBacktracking;
842
843    if (fragment.tagNameMatchedBacktrackingStartHeightFromDescendant == (fragment.heightFromDescendant + 1))
844        return BacktrackingAction::JumpToDescendantTreeWalkerEntryPoint;
845
846    return BacktrackingAction::JumpToDescendantTail;
847}
848
849static inline void solveBacktrackingAction(SelectorFragment& fragment, bool hasDescendantRelationOnTheRight, bool hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain)
850{
851    switch (fragment.relationToRightFragment) {
852    case FragmentRelation::Rightmost:
853    case FragmentRelation::Descendant:
854        break;
855    case FragmentRelation::Child:
856        // Failure to match the element should resume matching at the nearest ancestor/descendant entry point.
857        if (hasDescendantRelationOnTheRight) {
858            fragment.matchingTagNameBacktrackingAction = solveDescendantBacktrackingActionForChild(fragment, fragment.tagNameNotMatchedBacktrackingStartHeightFromDescendant);
859            fragment.matchingPostTagNameBacktrackingAction = solveDescendantBacktrackingActionForChild(fragment, fragment.tagNameMatchedBacktrackingStartHeightFromDescendant);
860        }
861        break;
862    case FragmentRelation::DirectAdjacent:
863        // Failure on traversal implies no other sibling traversal can match. Matching should resume at the
864        // nearest ancestor/descendant traversal.
865        fragment.traversalBacktrackingAction = solveAdjacentTraversalBacktrackingAction(fragment, hasDescendantRelationOnTheRight);
866
867        // If the rightmost relation is a indirect adjacent, matching sould resume from there.
868        // Otherwise, we resume from the latest ancestor/descendant if any.
869        if (hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain) {
870            fragment.matchingTagNameBacktrackingAction = solveAdjacentBacktrackingActionForDirectAdjacent(fragment, fragment.tagNameNotMatchedBacktrackingStartWidthFromIndirectAdjacent);
871            fragment.matchingPostTagNameBacktrackingAction = solveAdjacentBacktrackingActionForDirectAdjacent(fragment, fragment.tagNameMatchedBacktrackingStartWidthFromIndirectAdjacent);
872        } else if (hasDescendantRelationOnTheRight) {
873            // Since we resume from the latest ancestor/descendant, the action is the same as the traversal action.
874            fragment.matchingTagNameBacktrackingAction = fragment.traversalBacktrackingAction;
875            fragment.matchingPostTagNameBacktrackingAction = fragment.traversalBacktrackingAction;
876        }
877        break;
878    case FragmentRelation::IndirectAdjacent:
879        // Failure on traversal implies no other sibling matching will succeed. Matching can resume
880        // from the latest ancestor/descendant.
881        fragment.traversalBacktrackingAction = solveAdjacentTraversalBacktrackingAction(fragment, hasDescendantRelationOnTheRight);
882        break;
883    }
884}
885
886enum class TagNameEquality {
887    StrictlyNotEqual,
888    MaybeEqual,
889    StrictlyEqual
890};
891
892static inline TagNameEquality equalTagNames(const QualifiedName* lhs, const QualifiedName* rhs)
893{
894    if (!lhs || *lhs == anyQName())
895        return TagNameEquality::MaybeEqual;
896
897    if (!rhs || *rhs == anyQName())
898        return TagNameEquality::MaybeEqual;
899
900    ASSERT(lhs && rhs);
901
902    const AtomicString& lhsLocalName = lhs->localName();
903    const AtomicString& rhsLocalName = rhs->localName();
904    if (lhsLocalName != starAtom && rhsLocalName != starAtom) {
905        if (lhsLocalName != rhsLocalName)
906            return TagNameEquality::StrictlyNotEqual;
907        return TagNameEquality::StrictlyEqual;
908    }
909
910    const AtomicString& lhsNamespaceURI = lhs->namespaceURI();
911    const AtomicString& rhsNamespaceURI = rhs->namespaceURI();
912    if (lhsNamespaceURI != starAtom && rhsNamespaceURI != starAtom) {
913        if (lhsNamespaceURI != rhsNamespaceURI)
914            return TagNameEquality::StrictlyNotEqual;
915        return TagNameEquality::StrictlyEqual;
916    }
917
918    return TagNameEquality::MaybeEqual;
919}
920
921static inline bool equalTagNamePatterns(const TagNamePattern& lhs, const QualifiedName* rhs)
922{
923    TagNameEquality result = equalTagNames(lhs.tagName, rhs);
924    if (result == TagNameEquality::MaybeEqual)
925        return true;
926
927    // If both rhs & lhs have actual localName (or NamespaceURI),
928    // TagNameEquality result becomes StrictlyEqual or StrictlyNotEqual Since inverted lhs never matches on rhs.
929    bool equal = result == TagNameEquality::StrictlyEqual;
930    if (lhs.inverted)
931        return !equal;
932    return equal;
933}
934
935// Find the largest matching prefix from already known tagNames.
936// And by using this, compute an appropriate height of backtracking start element from the closest base element in the chain.
937static inline unsigned computeBacktrackingStartOffsetInChain(const TagNameList& tagNames, unsigned maxPrefixSize)
938{
939    RELEASE_ASSERT(!tagNames.isEmpty());
940    RELEASE_ASSERT(maxPrefixSize < tagNames.size());
941
942    for (unsigned largestPrefixSize = maxPrefixSize; largestPrefixSize > 0; --largestPrefixSize) {
943        unsigned offsetToLargestPrefix = tagNames.size() - largestPrefixSize;
944        bool matched = true;
945        // Since TagNamePatterns are pushed to a tagNames, check tagNames with reverse order.
946        for (unsigned i = 0; i < largestPrefixSize; ++i) {
947            unsigned lastIndex = tagNames.size() - 1;
948            unsigned currentIndex = lastIndex - i;
949            if (!equalTagNamePatterns(tagNames[currentIndex], tagNames[currentIndex - offsetToLargestPrefix].tagName)) {
950                matched = false;
951                break;
952            }
953        }
954        if (matched)
955            return offsetToLargestPrefix;
956    }
957    return tagNames.size();
958}
959
960static inline void computeBacktrackingHeightFromDescendant(SelectorFragment& fragment, TagNameList& tagNamesForChildChain, bool hasDescendantRelationOnTheRight, const SelectorFragment*& previousChildFragmentInChildChain)
961{
962    if (!hasDescendantRelationOnTheRight)
963        return;
964
965    if (fragment.relationToRightFragment == FragmentRelation::Descendant) {
966        tagNamesForChildChain.clear();
967
968        TagNamePattern pattern;
969        pattern.tagName = fragment.tagName;
970        tagNamesForChildChain.append(pattern);
971        fragment.heightFromDescendant = 0;
972        previousChildFragmentInChildChain = nullptr;
973    } else if (fragment.relationToRightFragment == FragmentRelation::Child) {
974        TagNamePattern pattern;
975        pattern.tagName = fragment.tagName;
976        tagNamesForChildChain.append(pattern);
977
978        unsigned maxPrefixSize = tagNamesForChildChain.size() - 1;
979        if (previousChildFragmentInChildChain) {
980            RELEASE_ASSERT(tagNamesForChildChain.size() >= previousChildFragmentInChildChain->tagNameMatchedBacktrackingStartHeightFromDescendant);
981            maxPrefixSize = tagNamesForChildChain.size() - previousChildFragmentInChildChain->tagNameMatchedBacktrackingStartHeightFromDescendant;
982        }
983
984        if (pattern.tagName) {
985            // Compute height from descendant in the case that tagName is not matched.
986            tagNamesForChildChain.last().inverted = true;
987            fragment.tagNameNotMatchedBacktrackingStartHeightFromDescendant = computeBacktrackingStartOffsetInChain(tagNamesForChildChain, maxPrefixSize);
988        }
989
990        // Compute height from descendant in the case that tagName is matched.
991        tagNamesForChildChain.last().inverted = false;
992        fragment.tagNameMatchedBacktrackingStartHeightFromDescendant = computeBacktrackingStartOffsetInChain(tagNamesForChildChain, maxPrefixSize);
993        fragment.heightFromDescendant = tagNamesForChildChain.size() - 1;
994        previousChildFragmentInChildChain = &fragment;
995    } else {
996        if (previousChildFragmentInChildChain) {
997            fragment.tagNameNotMatchedBacktrackingStartHeightFromDescendant = previousChildFragmentInChildChain->tagNameNotMatchedBacktrackingStartHeightFromDescendant;
998            fragment.tagNameMatchedBacktrackingStartHeightFromDescendant = previousChildFragmentInChildChain->tagNameMatchedBacktrackingStartHeightFromDescendant;
999            fragment.heightFromDescendant = previousChildFragmentInChildChain->heightFromDescendant;
1000        } else {
1001            fragment.tagNameNotMatchedBacktrackingStartHeightFromDescendant = tagNamesForChildChain.size();
1002            fragment.tagNameMatchedBacktrackingStartHeightFromDescendant = tagNamesForChildChain.size();
1003            fragment.heightFromDescendant = 0;
1004        }
1005    }
1006}
1007
1008static inline void computeBacktrackingWidthFromIndirectAdjacent(SelectorFragment& fragment, TagNameList& tagNamesForDirectAdjacentChain, bool hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain, const SelectorFragment*& previousDirectAdjacentFragmentInDirectAdjacentChain)
1009{
1010    if (!hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain)
1011        return;
1012
1013    if (fragment.relationToRightFragment == FragmentRelation::IndirectAdjacent) {
1014        tagNamesForDirectAdjacentChain.clear();
1015
1016        TagNamePattern pattern;
1017        pattern.tagName = fragment.tagName;
1018        tagNamesForDirectAdjacentChain.append(pattern);
1019        fragment.widthFromIndirectAdjacent = 0;
1020        previousDirectAdjacentFragmentInDirectAdjacentChain = nullptr;
1021    } else if (fragment.relationToRightFragment == FragmentRelation::DirectAdjacent) {
1022        TagNamePattern pattern;
1023        pattern.tagName = fragment.tagName;
1024        tagNamesForDirectAdjacentChain.append(pattern);
1025
1026        unsigned maxPrefixSize = tagNamesForDirectAdjacentChain.size() - 1;
1027        if (previousDirectAdjacentFragmentInDirectAdjacentChain) {
1028            RELEASE_ASSERT(tagNamesForDirectAdjacentChain.size() >= previousDirectAdjacentFragmentInDirectAdjacentChain->tagNameMatchedBacktrackingStartWidthFromIndirectAdjacent);
1029            maxPrefixSize = tagNamesForDirectAdjacentChain.size() - previousDirectAdjacentFragmentInDirectAdjacentChain->tagNameMatchedBacktrackingStartWidthFromIndirectAdjacent;
1030        }
1031
1032        if (pattern.tagName) {
1033            // Compute height from descendant in the case that tagName is not matched.
1034            tagNamesForDirectAdjacentChain.last().inverted = true;
1035            fragment.tagNameNotMatchedBacktrackingStartWidthFromIndirectAdjacent = computeBacktrackingStartOffsetInChain(tagNamesForDirectAdjacentChain, maxPrefixSize);
1036        }
1037
1038        // Compute height from descendant in the case that tagName is matched.
1039        tagNamesForDirectAdjacentChain.last().inverted = false;
1040        fragment.tagNameMatchedBacktrackingStartWidthFromIndirectAdjacent = computeBacktrackingStartOffsetInChain(tagNamesForDirectAdjacentChain, maxPrefixSize);
1041        fragment.widthFromIndirectAdjacent = tagNamesForDirectAdjacentChain.size() - 1;
1042        previousDirectAdjacentFragmentInDirectAdjacentChain = &fragment;
1043    }
1044}
1045
1046static bool requiresAdjacentTail(const SelectorFragment& fragment)
1047{
1048    ASSERT(fragment.traversalBacktrackingAction != BacktrackingAction::JumpToDirectAdjacentTail);
1049    return fragment.matchingTagNameBacktrackingAction == BacktrackingAction::JumpToDirectAdjacentTail || fragment.matchingPostTagNameBacktrackingAction == BacktrackingAction::JumpToDirectAdjacentTail;
1050}
1051
1052static bool requiresDescendantTail(const SelectorFragment& fragment)
1053{
1054    return fragment.matchingTagNameBacktrackingAction == BacktrackingAction::JumpToDescendantTail || fragment.matchingPostTagNameBacktrackingAction == BacktrackingAction::JumpToDescendantTail || fragment.traversalBacktrackingAction == BacktrackingAction::JumpToDescendantTail;
1055}
1056
1057void computeBacktrackingInformation(SelectorFragmentList& selectorFragments, bool& needsAdjacentBacktrackingStart)
1058{
1059    bool hasDescendantRelationOnTheRight = false;
1060    unsigned ancestorPositionSinceDescendantRelation = 0;
1061    bool hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain = false;
1062    unsigned adjacentPositionSinceIndirectAdjacentTreeWalk = 0;
1063
1064    bool needsAdjacentTail = false;
1065    bool needsDescendantTail = false;
1066    unsigned saveDescendantBacktrackingStartFragmentIndex = std::numeric_limits<unsigned>::max();
1067    unsigned saveIndirectAdjacentBacktrackingStartFragmentIndex = std::numeric_limits<unsigned>::max();
1068
1069    TagNameList tagNamesForChildChain;
1070    TagNameList tagNamesForDirectAdjacentChain;
1071    const SelectorFragment* previousChildFragmentInChildChain = nullptr;
1072    const SelectorFragment* previousDirectAdjacentFragmentInDirectAdjacentChain = nullptr;
1073
1074    for (unsigned i = 0; i < selectorFragments.size(); ++i) {
1075        SelectorFragment& fragment = selectorFragments[i];
1076
1077        updateChainStates(fragment, hasDescendantRelationOnTheRight, ancestorPositionSinceDescendantRelation, hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain, adjacentPositionSinceIndirectAdjacentTreeWalk);
1078
1079        computeBacktrackingHeightFromDescendant(fragment, tagNamesForChildChain, hasDescendantRelationOnTheRight, previousChildFragmentInChildChain);
1080
1081        computeBacktrackingWidthFromIndirectAdjacent(fragment, tagNamesForDirectAdjacentChain, hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain, previousDirectAdjacentFragmentInDirectAdjacentChain);
1082
1083#if CSS_SELECTOR_JIT_DEBUGGING
1084        dataLogF("Computing fragment[%d] backtracking height %u. NotMatched %u / Matched %u | width %u. NotMatched %u / Matched %u\n", i, fragment.heightFromDescendant, fragment.tagNameNotMatchedBacktrackingStartHeightFromDescendant, fragment.tagNameMatchedBacktrackingStartHeightFromDescendant, fragment.widthFromIndirectAdjacent, fragment.tagNameNotMatchedBacktrackingStartWidthFromIndirectAdjacent, fragment.tagNameMatchedBacktrackingStartWidthFromIndirectAdjacent);
1085#endif
1086
1087        solveBacktrackingAction(fragment, hasDescendantRelationOnTheRight, hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain);
1088
1089        needsAdjacentTail |= requiresAdjacentTail(fragment);
1090        needsDescendantTail |= requiresDescendantTail(fragment);
1091
1092        // Add code generation flags.
1093        if (fragment.relationToLeftFragment != FragmentRelation::Descendant && fragment.relationToRightFragment == FragmentRelation::Descendant)
1094            fragment.backtrackingFlags |= BacktrackingFlag::DescendantEntryPoint;
1095        if (fragment.relationToLeftFragment == FragmentRelation::DirectAdjacent && fragment.relationToRightFragment == FragmentRelation::IndirectAdjacent)
1096            fragment.backtrackingFlags |= BacktrackingFlag::IndirectAdjacentEntryPoint;
1097        if (fragment.relationToLeftFragment != FragmentRelation::Descendant && fragment.relationToRightFragment == FragmentRelation::Child && isFirstAncestor(ancestorPositionSinceDescendantRelation)) {
1098            ASSERT(saveDescendantBacktrackingStartFragmentIndex == std::numeric_limits<unsigned>::max());
1099            saveDescendantBacktrackingStartFragmentIndex = i;
1100        }
1101        if (fragment.relationToLeftFragment == FragmentRelation::DirectAdjacent && fragment.relationToRightFragment == FragmentRelation::DirectAdjacent && isFirstAdjacent(adjacentPositionSinceIndirectAdjacentTreeWalk)) {
1102            ASSERT(saveIndirectAdjacentBacktrackingStartFragmentIndex == std::numeric_limits<unsigned>::max());
1103            saveIndirectAdjacentBacktrackingStartFragmentIndex = i;
1104        }
1105        if (fragment.relationToLeftFragment != FragmentRelation::DirectAdjacent) {
1106            if (needsAdjacentTail) {
1107                ASSERT(fragment.relationToRightFragment == FragmentRelation::DirectAdjacent);
1108                ASSERT(saveIndirectAdjacentBacktrackingStartFragmentIndex != std::numeric_limits<unsigned>::max());
1109                fragment.backtrackingFlags |= BacktrackingFlag::DirectAdjacentTail;
1110                selectorFragments[saveIndirectAdjacentBacktrackingStartFragmentIndex].backtrackingFlags |= BacktrackingFlag::SaveAdjacentBacktrackingStart;
1111                needsAdjacentBacktrackingStart = true;
1112                needsAdjacentTail = false;
1113            }
1114            saveIndirectAdjacentBacktrackingStartFragmentIndex = std::numeric_limits<unsigned>::max();
1115        }
1116        if (fragment.relationToLeftFragment == FragmentRelation::Descendant) {
1117            if (needsDescendantTail) {
1118                ASSERT(saveDescendantBacktrackingStartFragmentIndex != std::numeric_limits<unsigned>::max());
1119                fragment.backtrackingFlags |= BacktrackingFlag::DescendantTail;
1120                selectorFragments[saveDescendantBacktrackingStartFragmentIndex].backtrackingFlags |= BacktrackingFlag::SaveDescendantBacktrackingStart;
1121                needsDescendantTail = false;
1122                for (unsigned j = saveDescendantBacktrackingStartFragmentIndex; j <= i; ++j)
1123                    selectorFragments[j].backtrackingFlags |= BacktrackingFlag::InChainWithDescendantTail;
1124            }
1125            saveDescendantBacktrackingStartFragmentIndex = std::numeric_limits<unsigned>::max();
1126        }
1127    }
1128}
1129
1130inline bool SelectorCodeGenerator::generatePrologue()
1131{
1132#if CPU(ARM64)
1133    Vector<JSC::MacroAssembler::RegisterID, 2> prologueRegisters;
1134    prologueRegisters.append(JSC::ARM64Registers::lr);
1135    prologueRegisters.append(JSC::ARM64Registers::fp);
1136    m_prologueStackReferences = m_stackAllocator.push(prologueRegisters);
1137    return true;
1138#elif CPU(ARM_THUMB2)
1139    Vector<JSC::MacroAssembler::RegisterID, 2> prologueRegisters;
1140    prologueRegisters.append(JSC::ARMRegisters::lr);
1141    // r6 is tempRegister in RegisterAllocator.h and addressTempRegister in MacroAssemblerARMv7.h and must be preserved by the callee.
1142    prologueRegisters.append(JSC::ARMRegisters::r6);
1143    m_prologueStackReferences = m_stackAllocator.push(prologueRegisters);
1144    return true;
1145#elif CPU(X86_64) && CSS_SELECTOR_JIT_DEBUGGING
1146    Vector<JSC::MacroAssembler::RegisterID, 1> prologueRegister;
1147    prologueRegister.append(callFrameRegister);
1148    m_prologueStackReferences = m_stackAllocator.push(prologueRegister);
1149    return true;
1150#endif
1151    return false;
1152}
1153
1154inline void SelectorCodeGenerator::generateEpilogue()
1155{
1156#if CPU(ARM64)
1157    Vector<JSC::MacroAssembler::RegisterID, 2> prologueRegisters;
1158    prologueRegisters.append(JSC::ARM64Registers::lr);
1159    prologueRegisters.append(JSC::ARM64Registers::fp);
1160    m_stackAllocator.pop(m_prologueStackReferences, prologueRegisters);
1161#elif CPU(ARM_THUMB2)
1162    Vector<JSC::MacroAssembler::RegisterID, 2> prologueRegisters;
1163    prologueRegisters.append(JSC::ARMRegisters::lr);
1164    prologueRegisters.append(JSC::ARMRegisters::r6);
1165    m_stackAllocator.pop(m_prologueStackReferences, prologueRegisters);
1166#elif CPU(X86_64) && CSS_SELECTOR_JIT_DEBUGGING
1167    Vector<JSC::MacroAssembler::RegisterID, 1> prologueRegister;
1168    prologueRegister.append(callFrameRegister);
1169    m_stackAllocator.pop(m_prologueStackReferences, prologueRegister);
1170#endif
1171}
1172
1173void SelectorCodeGenerator::generateSelectorChecker()
1174{
1175    StackAllocator::StackReferenceVector calleeSavedRegisterStackReferences;
1176    bool reservedCalleeSavedRegisters = false;
1177    unsigned availableRegisterCount = m_registerAllocator.availableRegisterCount();
1178    unsigned minimumRegisterCountForAttributes = minimumRegisterRequirements(m_selectorFragments);
1179#if CSS_SELECTOR_JIT_DEBUGGING
1180    dataLogF("Compiling with minimum required register count %u\n", minimumRegisterCountForAttributes);
1181#endif
1182
1183    bool needsEpilogue = generatePrologue();
1184
1185    ASSERT(minimumRegisterCountForAttributes <= maximumRegisterCount);
1186    if (availableRegisterCount < minimumRegisterCountForAttributes) {
1187        reservedCalleeSavedRegisters = true;
1188        calleeSavedRegisterStackReferences = m_stackAllocator.push(m_registerAllocator.reserveCalleeSavedRegisters(minimumRegisterCountForAttributes - availableRegisterCount));
1189    }
1190
1191    m_registerAllocator.allocateRegister(elementAddressRegister);
1192
1193    if (m_functionType == FunctionType::SelectorCheckerWithCheckingContext)
1194        m_checkingContextStackReference = m_stackAllocator.push(checkingContextRegister);
1195
1196    if (m_needsAdjacentBacktrackingStart)
1197        m_adjacentBacktrackingStart = m_stackAllocator.allocateUninitialized();
1198
1199    Assembler::JumpList failureCases;
1200
1201    for (unsigned i = 0; i < m_selectorFragments.size(); ++i) {
1202        const SelectorFragment& fragment = m_selectorFragments[i];
1203        switch (fragment.relationToRightFragment) {
1204        case FragmentRelation::Rightmost:
1205            generateElementMatching(failureCases, failureCases, fragment);
1206            break;
1207        case FragmentRelation::Descendant:
1208            generateAncestorTreeWalker(failureCases, fragment);
1209            break;
1210        case FragmentRelation::Child:
1211            generateParentElementTreeWalker(failureCases, fragment);
1212            break;
1213        case FragmentRelation::DirectAdjacent:
1214            generateDirectAdjacentTreeWalker(failureCases, fragment);
1215            break;
1216        case FragmentRelation::IndirectAdjacent:
1217            generateIndirectAdjacentTreeWalker(failureCases, fragment);
1218            break;
1219        }
1220        generateBacktrackingTailsIfNeeded(failureCases, fragment);
1221    }
1222
1223    m_registerAllocator.deallocateRegister(elementAddressRegister);
1224
1225    if (m_functionType == FunctionType::SimpleSelectorChecker) {
1226        if (!m_needsAdjacentBacktrackingStart && !reservedCalleeSavedRegisters && !needsEpilogue) {
1227            // Success.
1228            m_assembler.move(Assembler::TrustedImm32(1), returnRegister);
1229            m_assembler.ret();
1230
1231            // Failure.
1232            if (!failureCases.empty()) {
1233                failureCases.link(&m_assembler);
1234                m_assembler.move(Assembler::TrustedImm32(0), returnRegister);
1235                m_assembler.ret();
1236            }
1237        } else {
1238            // Success.
1239            m_assembler.move(Assembler::TrustedImm32(1), returnRegister);
1240
1241            // Failure.
1242            if (!failureCases.empty()) {
1243                Assembler::Jump skipFailureCase = m_assembler.jump();
1244                failureCases.link(&m_assembler);
1245                m_assembler.move(Assembler::TrustedImm32(0), returnRegister);
1246                skipFailureCase.link(&m_assembler);
1247            }
1248
1249            if (m_needsAdjacentBacktrackingStart)
1250                m_stackAllocator.popAndDiscardUpTo(m_adjacentBacktrackingStart);
1251            if (reservedCalleeSavedRegisters)
1252                m_stackAllocator.pop(calleeSavedRegisterStackReferences, m_registerAllocator.restoreCalleeSavedRegisters());
1253            if (needsEpilogue)
1254                generateEpilogue();
1255            m_assembler.ret();
1256        }
1257    } else {
1258        ASSERT(m_functionType == FunctionType::SelectorCheckerWithCheckingContext);
1259
1260        // Success.
1261        m_assembler.move(Assembler::TrustedImm32(1), returnRegister);
1262
1263        // Failure.
1264        if (!failureCases.empty()) {
1265            Assembler::Jump skipFailureCase = m_assembler.jump();
1266            failureCases.link(&m_assembler);
1267            m_assembler.move(Assembler::TrustedImm32(0), returnRegister);
1268            skipFailureCase.link(&m_assembler);
1269        }
1270
1271        m_stackAllocator.popAndDiscardUpTo(m_checkingContextStackReference);
1272        if (reservedCalleeSavedRegisters)
1273            m_stackAllocator.pop(calleeSavedRegisterStackReferences, m_registerAllocator.restoreCalleeSavedRegisters());
1274        if (needsEpilogue)
1275            generateEpilogue();
1276        m_assembler.ret();
1277    }
1278}
1279
1280static inline Assembler::Jump testIsElementFlagOnNode(Assembler::ResultCondition condition, Assembler& assembler, Assembler::RegisterID nodeAddress)
1281{
1282    return assembler.branchTest32(condition, Assembler::Address(nodeAddress, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagIsElement()));
1283}
1284
1285void SelectorCodeGenerator::generateWalkToParentNode(Assembler::RegisterID targetRegister)
1286{
1287    m_assembler.loadPtr(Assembler::Address(elementAddressRegister, Node::parentNodeMemoryOffset()), targetRegister);
1288}
1289
1290void SelectorCodeGenerator::generateWalkToParentElement(Assembler::JumpList& failureCases, Assembler::RegisterID targetRegister)
1291{
1292    //    ContainerNode* parent = parentNode()
1293    //    if (!parent || !parent->isElementNode())
1294    //         failure
1295    generateWalkToParentNode(targetRegister);
1296    failureCases.append(m_assembler.branchTestPtr(Assembler::Zero, targetRegister));
1297    failureCases.append(testIsElementFlagOnNode(Assembler::Zero, m_assembler, targetRegister));
1298}
1299
1300void SelectorCodeGenerator::generateParentElementTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
1301{
1302    Assembler::JumpList traversalFailureCases;
1303    generateWalkToParentElement(traversalFailureCases, elementAddressRegister);
1304    linkFailures(failureCases, fragment.traversalBacktrackingAction, traversalFailureCases);
1305
1306    Assembler::JumpList matchingTagNameFailureCases;
1307    Assembler::JumpList matchingPostTagNameFailureCases;
1308    generateElementMatching(matchingTagNameFailureCases, matchingPostTagNameFailureCases, fragment);
1309    linkFailures(failureCases, fragment.matchingTagNameBacktrackingAction, matchingTagNameFailureCases);
1310    linkFailures(failureCases, fragment.matchingPostTagNameBacktrackingAction, matchingPostTagNameFailureCases);
1311
1312    if (fragment.backtrackingFlags & BacktrackingFlag::SaveDescendantBacktrackingStart) {
1313        m_descendantBacktrackingStart = m_registerAllocator.allocateRegister();
1314        m_assembler.move(elementAddressRegister, m_descendantBacktrackingStart);
1315    }
1316}
1317
1318void SelectorCodeGenerator::generateAncestorTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
1319{
1320    // Loop over the ancestors until one of them matches the fragment.
1321    Assembler::Label loopStart(m_assembler.label());
1322
1323    if (fragment.backtrackingFlags & BacktrackingFlag::DescendantEntryPoint)
1324        m_descendantTreeWalkerBacktrackingPoint = m_assembler.label();
1325
1326    generateWalkToParentElement(failureCases, elementAddressRegister);
1327
1328    if (fragment.backtrackingFlags & BacktrackingFlag::DescendantEntryPoint)
1329        m_descendantEntryPoint = m_assembler.label();
1330
1331    Assembler::JumpList matchingFailureCases;
1332    generateElementMatching(matchingFailureCases, matchingFailureCases, fragment);
1333    matchingFailureCases.linkTo(loopStart, &m_assembler);
1334}
1335
1336inline void SelectorCodeGenerator::generateWalkToNextAdjacentElement(Assembler::JumpList& failureCases, Assembler::RegisterID workRegister)
1337{
1338    Assembler::Label loopStart = m_assembler.label();
1339    m_assembler.loadPtr(Assembler::Address(workRegister, Node::nextSiblingMemoryOffset()), workRegister);
1340    failureCases.append(m_assembler.branchTestPtr(Assembler::Zero, workRegister));
1341    testIsElementFlagOnNode(Assembler::Zero, m_assembler, workRegister).linkTo(loopStart, &m_assembler);
1342}
1343
1344inline void SelectorCodeGenerator::generateWalkToPreviousAdjacentElement(Assembler::JumpList& failureCases, Assembler::RegisterID workRegister)
1345{
1346    Assembler::Label loopStart = m_assembler.label();
1347    m_assembler.loadPtr(Assembler::Address(workRegister, Node::previousSiblingMemoryOffset()), workRegister);
1348    failureCases.append(m_assembler.branchTestPtr(Assembler::Zero, workRegister));
1349    testIsElementFlagOnNode(Assembler::Zero, m_assembler, workRegister).linkTo(loopStart, &m_assembler);
1350}
1351
1352void SelectorCodeGenerator::generateWalkToPreviousAdjacent(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
1353{
1354    //    do {
1355    //        previousSibling = previousSibling->previousSibling();
1356    //        if (!previousSibling)
1357    //            failure!
1358    //    while (!previousSibling->isElement());
1359    Assembler::RegisterID previousSibling;
1360    bool useTailOnTraversalFailure = fragment.traversalBacktrackingAction >= BacktrackingAction::JumpToDescendantTail;
1361    if (!useTailOnTraversalFailure) {
1362        // If the current fragment is not dependant on a previously saved elementAddressRegister, a fast recover
1363        // from a failure would resume with elementAddressRegister.
1364        // When walking to the previous sibling, the failure can be that previousSibling is null. We cannot backtrack
1365        // with a null elementAddressRegister so we do the traversal on a copy.
1366        previousSibling = m_registerAllocator.allocateRegister();
1367        m_assembler.move(elementAddressRegister, previousSibling);
1368    } else
1369        previousSibling = elementAddressRegister;
1370
1371    Assembler::JumpList traversalFailureCases;
1372    generateWalkToPreviousAdjacentElement(traversalFailureCases, previousSibling);
1373    linkFailures(failureCases, fragment.traversalBacktrackingAction, traversalFailureCases);
1374
1375    // On success, move previousSibling over to elementAddressRegister if we could not work on elementAddressRegister directly.
1376    if (!useTailOnTraversalFailure) {
1377        m_assembler.move(previousSibling, elementAddressRegister);
1378        m_registerAllocator.deallocateRegister(previousSibling);
1379    }
1380}
1381
1382void SelectorCodeGenerator::generateDirectAdjacentTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
1383{
1384    markParentElementIfResolvingStyle(Node::flagChildrenAffectedByDirectAdjacentRulesFlag());
1385
1386    generateWalkToPreviousAdjacent(failureCases, fragment);
1387
1388    Assembler::JumpList matchingTagNameFailureCases;
1389    Assembler::JumpList matchingPostTagNameFailureCases;
1390    generateElementMatching(matchingTagNameFailureCases, matchingPostTagNameFailureCases, fragment);
1391    linkFailures(failureCases, fragment.matchingTagNameBacktrackingAction, matchingTagNameFailureCases);
1392    linkFailures(failureCases, fragment.matchingPostTagNameBacktrackingAction, matchingPostTagNameFailureCases);
1393
1394    if (fragment.backtrackingFlags & BacktrackingFlag::SaveAdjacentBacktrackingStart) {
1395        unsigned offsetToAdjacentBacktrackingStart = m_stackAllocator.offsetToStackReference(m_adjacentBacktrackingStart);
1396        m_assembler.storePtr(elementAddressRegister, Assembler::Address(Assembler::stackPointerRegister, offsetToAdjacentBacktrackingStart));
1397    }
1398}
1399
1400void SelectorCodeGenerator::generateIndirectAdjacentTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
1401{
1402    markParentElementIfResolvingStyle(Element::setChildrenAffectedByForwardPositionalRules);
1403
1404    Assembler::Label loopStart(m_assembler.label());
1405
1406    if (fragment.backtrackingFlags & BacktrackingFlag::IndirectAdjacentEntryPoint)
1407        m_indirectAdjacentTreeWalkerBacktrackingPoint = m_assembler.label();
1408
1409    generateWalkToPreviousAdjacent(failureCases, fragment);
1410
1411    if (fragment.backtrackingFlags & BacktrackingFlag::IndirectAdjacentEntryPoint)
1412        m_indirectAdjacentEntryPoint = m_assembler.label();
1413
1414    Assembler::JumpList localFailureCases;
1415    generateElementMatching(localFailureCases, localFailureCases, fragment);
1416    localFailureCases.linkTo(loopStart, &m_assembler);
1417}
1418
1419
1420void SelectorCodeGenerator::addFlagsToElementStyleFromContext(Assembler::RegisterID checkingContext, int64_t newFlag)
1421{
1422    LocalRegister childStyle(m_registerAllocator);
1423    m_assembler.loadPtr(Assembler::Address(checkingContext, OBJECT_OFFSETOF(CheckingContext, elementStyle)), childStyle);
1424
1425    // FIXME: We should look into doing something smart in MacroAssembler instead.
1426    Assembler::Address flagAddress(childStyle, RenderStyle::noninheritedFlagsMemoryOffset() + RenderStyle::NonInheritedFlags::flagsMemoryOffset());
1427#if CPU(ARM_THUMB2)
1428    int32_t flagLowBits = newFlag & 0xffffffff;
1429    int32_t flagHighBits = newFlag >> 32;
1430    if (flagLowBits)
1431        m_assembler.or32(Assembler::TrustedImm32(flagLowBits), flagAddress);
1432    if (flagHighBits) {
1433        Assembler::Address flagHighAddress = flagAddress.withOffset(4);
1434        m_assembler.or32(Assembler::TrustedImm32(flagHighBits), flagHighAddress);
1435    }
1436#elif CPU(X86_64) || CPU(ARM64)
1437    LocalRegister flags(m_registerAllocator);
1438    m_assembler.load64(flagAddress, flags);
1439    LocalRegister isFirstChildStateFlagImmediate(m_registerAllocator);
1440    m_assembler.move(Assembler::TrustedImm64(newFlag), isFirstChildStateFlagImmediate);
1441    m_assembler.or64(isFirstChildStateFlagImmediate, flags);
1442    m_assembler.store64(flags, flagAddress);
1443#else
1444#error SelectorCodeGenerator::addFlagsToElementStyleFromContext not implemented for this architecture.
1445#endif
1446}
1447
1448Assembler::JumpList SelectorCodeGenerator::jumpIfNoPreviousAdjacentElement()
1449{
1450    Assembler::JumpList successCase;
1451    LocalRegister previousSibling(m_registerAllocator);
1452    m_assembler.move(elementAddressRegister, previousSibling);
1453    generateWalkToPreviousAdjacentElement(successCase, previousSibling);
1454    return successCase;
1455}
1456
1457Assembler::JumpList SelectorCodeGenerator::jumpIfNoNextAdjacentElement()
1458{
1459    Assembler::JumpList successCase;
1460    LocalRegister nextSibling(m_registerAllocator);
1461    m_assembler.move(elementAddressRegister, nextSibling);
1462    generateWalkToNextAdjacentElement(successCase, nextSibling);
1463    return successCase;
1464}
1465
1466Assembler::Jump SelectorCodeGenerator::jumpIfNotResolvingStyle(Assembler::RegisterID checkingContext)
1467{
1468    RELEASE_ASSERT(m_selectorContext == SelectorContext::RuleCollector);
1469
1470    // Get the checking context.
1471    unsigned offsetToCheckingContext = m_stackAllocator.offsetToStackReference(m_checkingContextStackReference);
1472    m_assembler.loadPtr(Assembler::Address(Assembler::stackPointerRegister, offsetToCheckingContext), checkingContext);
1473
1474    // If we not resolving style, skip the whole marking.
1475    static_assert(sizeof(SelectorChecker::Mode) == 1, "We generate a byte load/test for the SelectorChecker::Mode.");
1476    return m_assembler.branch8(Assembler::NotEqual, Assembler::Address(checkingContext, OBJECT_OFFSETOF(CheckingContext, resolvingMode)), Assembler::TrustedImm32(static_cast<std::underlying_type<SelectorChecker::Mode>::type>(SelectorChecker::Mode::ResolvingStyle)));
1477}
1478
1479static void getDocument(Assembler& assembler, Assembler::RegisterID element, Assembler::RegisterID output)
1480{
1481    assembler.loadPtr(Assembler::Address(element, Node::treeScopeMemoryOffset()), output);
1482    assembler.loadPtr(Assembler::Address(output, TreeScope::documentScopeMemoryOffset()), output);
1483}
1484
1485void SelectorCodeGenerator::generateSpecialFailureInQuirksModeForActiveAndHoverIfNeeded(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
1486{
1487    if (fragment.onlyMatchesLinksInQuirksMode) {
1488        // If the element is a link, it can always match :hover or :active.
1489        Assembler::Jump isLink = m_assembler.branchTest32(Assembler::NonZero, Assembler::Address(elementAddressRegister, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagIsLink()));
1490
1491        // Only quirks mode restrict :hover and :active.
1492        static_assert(sizeof(DocumentCompatibilityMode) == 1, "We generate a byte load/test for the compatibility mode.");
1493        LocalRegister documentAddress(m_registerAllocator);
1494        getDocument(m_assembler, elementAddressRegister, documentAddress);
1495        failureCases.append(m_assembler.branchTest8(Assembler::NonZero, Assembler::Address(documentAddress, Document::compatibilityModeMemoryOffset()), Assembler::TrustedImm32(static_cast<std::underlying_type<DocumentCompatibilityMode>::type>(DocumentCompatibilityMode::QuirksMode))));
1496
1497        isLink.link(&m_assembler);
1498    }
1499}
1500
1501#if CPU(ARM_THUMB2) && !CPU(APPLE_ARMV7S)
1502// FIXME: This could be implemented in assembly to avoid a function call, and we know the divisor at jit-compile time.
1503static int moduloHelper(int dividend, int divisor)
1504{
1505    return dividend % divisor;
1506}
1507#endif
1508
1509// The value in inputDividend is destroyed by the modulo operation.
1510Assembler::Jump SelectorCodeGenerator::modulo(Assembler::ResultCondition condition, Assembler::RegisterID inputDividend, int divisor)
1511{
1512    RELEASE_ASSERT(divisor);
1513#if CPU(ARM64) || CPU(APPLE_ARMV7S)
1514    LocalRegister divisorRegister(m_registerAllocator);
1515    m_assembler.move(Assembler::TrustedImm32(divisor), divisorRegister);
1516
1517    LocalRegister resultRegister(m_registerAllocator);
1518    m_assembler.m_assembler.sdiv<32>(resultRegister, inputDividend, divisorRegister);
1519    m_assembler.mul32(divisorRegister, resultRegister);
1520    return m_assembler.branchSub32(condition, inputDividend, resultRegister, resultRegister);
1521#elif CPU(ARM_THUMB2) && !CPU(APPLE_ARMV7S)
1522    LocalRegisterWithPreference divisorRegister(m_registerAllocator, JSC::GPRInfo::argumentGPR1);
1523    m_assembler.move(Assembler::TrustedImm32(divisor), divisorRegister);
1524    FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
1525    functionCall.setFunctionAddress(moduloHelper);
1526    functionCall.setTwoArguments(inputDividend, divisorRegister);
1527    return functionCall.callAndBranchOnBooleanReturnValue(condition);
1528#elif CPU(X86_64)
1529    // idiv takes RAX + an arbitrary register, and return RAX + RDX. Most of this code is about doing
1530    // an efficient allocation of those registers. If a register is already in use and is not the inputDividend,
1531    // we first try to copy it to a temporary register, it that is not possible we fall back to the stack.
1532    enum class RegisterAllocationType {
1533        External,
1534        AllocatedLocally,
1535        CopiedToTemporary,
1536        PushedToStack
1537    };
1538
1539    // 1) Get RAX and RDX.
1540    // If they are already used, push them to the stack.
1541    Assembler::RegisterID dividend = JSC::X86Registers::eax;
1542    RegisterAllocationType dividendAllocation = RegisterAllocationType::External;
1543    StackAllocator::StackReference temporaryDividendStackReference;
1544    Assembler::RegisterID temporaryDividendCopy = InvalidGPRReg;
1545    if (inputDividend != dividend) {
1546        bool registerIsInUse = m_registerAllocator.allocatedRegisters().contains(dividend);
1547        if (registerIsInUse) {
1548            if (m_registerAllocator.availableRegisterCount()) {
1549                temporaryDividendCopy = m_registerAllocator.allocateRegister();
1550                m_assembler.move(dividend, temporaryDividendCopy);
1551                dividendAllocation = RegisterAllocationType::CopiedToTemporary;
1552            } else {
1553                temporaryDividendStackReference = m_stackAllocator.push(dividend);
1554                dividendAllocation = RegisterAllocationType::PushedToStack;
1555            }
1556        } else {
1557            m_registerAllocator.allocateRegister(dividend);
1558            dividendAllocation = RegisterAllocationType::AllocatedLocally;
1559        }
1560        m_assembler.move(inputDividend, dividend);
1561    }
1562
1563    Assembler::RegisterID remainder = JSC::X86Registers::edx;
1564    RegisterAllocationType remainderAllocation = RegisterAllocationType::External;
1565    StackAllocator::StackReference temporaryRemainderStackReference;
1566    Assembler::RegisterID temporaryRemainderCopy = InvalidGPRReg;
1567    if (inputDividend != remainder) {
1568        bool registerIsInUse = m_registerAllocator.allocatedRegisters().contains(remainder);
1569        if (registerIsInUse) {
1570            if (m_registerAllocator.availableRegisterCount()) {
1571                temporaryRemainderCopy = m_registerAllocator.allocateRegister();
1572                m_assembler.move(remainder, temporaryRemainderCopy);
1573                remainderAllocation = RegisterAllocationType::CopiedToTemporary;
1574            } else {
1575                temporaryRemainderStackReference = m_stackAllocator.push(remainder);
1576                remainderAllocation = RegisterAllocationType::PushedToStack;
1577            }
1578        } else {
1579            m_registerAllocator.allocateRegister(remainder);
1580            remainderAllocation = RegisterAllocationType::AllocatedLocally;
1581        }
1582    }
1583    m_assembler.m_assembler.cdq();
1584
1585    // 2) Perform the division with idiv.
1586    {
1587        LocalRegister divisorRegister(m_registerAllocator);
1588        m_assembler.move(Assembler::TrustedImm64(divisor), divisorRegister);
1589        m_assembler.m_assembler.idivl_r(divisorRegister);
1590        m_assembler.test32(condition, remainder);
1591    }
1592
1593    // 3) Return RAX and RDX.
1594    if (remainderAllocation == RegisterAllocationType::AllocatedLocally)
1595        m_registerAllocator.deallocateRegister(remainder);
1596    else if (remainderAllocation == RegisterAllocationType::CopiedToTemporary) {
1597        m_assembler.move(temporaryRemainderCopy, remainder);
1598        m_registerAllocator.deallocateRegister(temporaryRemainderCopy);
1599    } else if (remainderAllocation == RegisterAllocationType::PushedToStack)
1600        m_stackAllocator.pop(temporaryRemainderStackReference, remainder);
1601
1602    if (dividendAllocation == RegisterAllocationType::AllocatedLocally)
1603        m_registerAllocator.deallocateRegister(dividend);
1604    else if (dividendAllocation == RegisterAllocationType::CopiedToTemporary) {
1605        m_assembler.move(temporaryDividendCopy, dividend);
1606        m_registerAllocator.deallocateRegister(temporaryDividendCopy);
1607    } else if (dividendAllocation == RegisterAllocationType::PushedToStack)
1608        m_stackAllocator.pop(temporaryDividendStackReference, dividend);
1609
1610    // 4) Branch on the test.
1611    return m_assembler.branch(condition);
1612#else
1613#error Modulo is not implemented for this architecture.
1614#endif
1615}
1616
1617void SelectorCodeGenerator::moduloIsZero(Assembler::JumpList& failureCases, Assembler::RegisterID inputDividend, int divisor)
1618{
1619    if (divisor == 1 || divisor == -1)
1620        return;
1621    if (divisor == 2 || divisor == -2) {
1622        failureCases.append(m_assembler.branchTest32(Assembler::NonZero, inputDividend, Assembler::TrustedImm32(1)));
1623        return;
1624    }
1625
1626    failureCases.append(modulo(Assembler::NonZero, inputDividend, divisor));
1627}
1628
1629static void setNodeFlag(Assembler& assembler, Assembler::RegisterID elementAddress, int32_t flag)
1630{
1631    assembler.or32(Assembler::TrustedImm32(flag), Assembler::Address(elementAddress, Node::nodeFlagsMemoryOffset()));
1632}
1633
1634void SelectorCodeGenerator::markParentElementIfResolvingStyle(int32_t nodeFlag)
1635{
1636    if (m_selectorContext == SelectorContext::QuerySelector)
1637        return;
1638
1639    Assembler::JumpList skipMarking;
1640    {
1641        LocalRegister checkingContext(m_registerAllocator);
1642        skipMarking.append(jumpIfNotResolvingStyle(checkingContext));
1643    }
1644
1645    LocalRegister parentElement(m_registerAllocator);
1646    generateWalkToParentElement(skipMarking, parentElement);
1647
1648    setNodeFlag(m_assembler, parentElement, nodeFlag);
1649
1650    skipMarking.link(&m_assembler);
1651}
1652
1653void SelectorCodeGenerator::markParentElementIfResolvingStyle(JSC::FunctionPtr markingFunction)
1654{
1655    if (m_selectorContext == SelectorContext::QuerySelector)
1656        return;
1657
1658    //     if (checkingContext.resolvingMode == ResolvingStyle) {
1659    //         Element* parent = element->parentNode();
1660    //         markingFunction(parent);
1661    //     }
1662
1663    Assembler::JumpList skipMarking;
1664    {
1665        LocalRegister checkingContext(m_registerAllocator);
1666        skipMarking.append(jumpIfNotResolvingStyle(checkingContext));
1667    }
1668
1669    // Get the parent element in a temporary register.
1670    Assembler::RegisterID parentElement = m_registerAllocator.allocateRegister();
1671    generateWalkToParentElement(skipMarking, parentElement);
1672
1673    // Return the register parentElement just before the function call since we don't need it to be preserved
1674    // on the stack.
1675    m_registerAllocator.deallocateRegister(parentElement);
1676
1677    // Invoke the marking function on the parent element.
1678    FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
1679    functionCall.setFunctionAddress(markingFunction);
1680    functionCall.setOneArgument(parentElement);
1681    functionCall.call();
1682
1683    skipMarking.link(&m_assembler);
1684}
1685
1686
1687void SelectorCodeGenerator::linkFailures(Assembler::JumpList& globalFailureCases, BacktrackingAction backtrackingAction, Assembler::JumpList& localFailureCases)
1688{
1689    switch (backtrackingAction) {
1690    case BacktrackingAction::NoBacktracking:
1691        globalFailureCases.append(localFailureCases);
1692        break;
1693    case BacktrackingAction::JumpToDescendantEntryPoint:
1694        localFailureCases.linkTo(m_descendantEntryPoint, &m_assembler);
1695        break;
1696    case BacktrackingAction::JumpToDescendantTreeWalkerEntryPoint:
1697        localFailureCases.linkTo(m_descendantTreeWalkerBacktrackingPoint, &m_assembler);
1698        break;
1699    case BacktrackingAction::JumpToDescendantTail:
1700        m_descendantBacktrackingFailureCases.append(localFailureCases);
1701        break;
1702    case BacktrackingAction::JumpToIndirectAdjacentEntryPoint:
1703        localFailureCases.linkTo(m_indirectAdjacentEntryPoint, &m_assembler);
1704        break;
1705    case BacktrackingAction::JumpToIndirectAdjacentTreeWalkerEntryPoint:
1706        localFailureCases.linkTo(m_indirectAdjacentTreeWalkerBacktrackingPoint, &m_assembler);
1707        break;
1708    case BacktrackingAction::JumpToDirectAdjacentTail:
1709        m_adjacentBacktrackingFailureCases.append(localFailureCases);
1710        break;
1711    }
1712}
1713
1714void SelectorCodeGenerator::generateAdjacentBacktrackingTail()
1715{
1716    // Recovering tail.
1717    m_adjacentBacktrackingFailureCases.link(&m_assembler);
1718    m_adjacentBacktrackingFailureCases.clear();
1719    unsigned offsetToAdjacentBacktrackingStart = m_stackAllocator.offsetToStackReference(m_adjacentBacktrackingStart);
1720    m_assembler.loadPtr(Assembler::Address(Assembler::stackPointerRegister, offsetToAdjacentBacktrackingStart), elementAddressRegister);
1721    m_assembler.jump(m_indirectAdjacentEntryPoint);
1722}
1723
1724void SelectorCodeGenerator::generateDescendantBacktrackingTail()
1725{
1726    m_descendantBacktrackingFailureCases.link(&m_assembler);
1727    m_descendantBacktrackingFailureCases.clear();
1728    m_assembler.move(m_descendantBacktrackingStart, elementAddressRegister);
1729    m_registerAllocator.deallocateRegister(m_descendantBacktrackingStart);
1730    m_assembler.jump(m_descendantEntryPoint);
1731}
1732
1733void SelectorCodeGenerator::generateBacktrackingTailsIfNeeded(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
1734{
1735    if (fragment.backtrackingFlags & BacktrackingFlag::DirectAdjacentTail && fragment.backtrackingFlags & BacktrackingFlag::DescendantTail) {
1736        Assembler::Jump normalCase = m_assembler.jump();
1737        generateAdjacentBacktrackingTail();
1738        generateDescendantBacktrackingTail();
1739        normalCase.link(&m_assembler);
1740    } else if (fragment.backtrackingFlags & BacktrackingFlag::DirectAdjacentTail) {
1741        Assembler::Jump normalCase = m_assembler.jump();
1742        generateAdjacentBacktrackingTail();
1743        failureCases.append(m_assembler.jump());
1744        normalCase.link(&m_assembler);
1745    } else if (fragment.backtrackingFlags & BacktrackingFlag::DescendantTail) {
1746        Assembler::Jump normalCase = m_assembler.jump();
1747        generateDescendantBacktrackingTail();
1748        normalCase.link(&m_assembler);
1749    }
1750}
1751
1752void SelectorCodeGenerator::generateElementMatching(Assembler::JumpList& matchingTagNameFailureCases, Assembler::JumpList& matchingPostTagNameFailureCases, const SelectorFragment& fragment)
1753{
1754    if (fragment.tagName)
1755        generateElementHasTagName(matchingTagNameFailureCases, *(fragment.tagName));
1756
1757    if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassLink))
1758        generateElementIsLink(matchingPostTagNameFailureCases);
1759
1760    if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassRoot))
1761        generateElementIsRoot(matchingPostTagNameFailureCases);
1762
1763    if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassTarget))
1764        generateElementIsTarget(matchingPostTagNameFailureCases);
1765
1766    for (unsigned i = 0; i < fragment.unoptimizedPseudoClasses.size(); ++i)
1767        generateElementFunctionCallTest(matchingPostTagNameFailureCases, fragment.unoptimizedPseudoClasses[i]);
1768
1769    generateElementDataMatching(matchingPostTagNameFailureCases, fragment);
1770
1771    if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassActive))
1772        generateElementIsActive(matchingPostTagNameFailureCases, fragment);
1773    if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassHover))
1774        generateElementIsHovered(matchingPostTagNameFailureCases, fragment);
1775    if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassOnlyChild))
1776        generateElementIsOnlyChild(matchingPostTagNameFailureCases, fragment);
1777    if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassFirstChild))
1778        generateElementIsFirstChild(matchingPostTagNameFailureCases, fragment);
1779    if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassLastChild))
1780        generateElementIsLastChild(matchingPostTagNameFailureCases, fragment);
1781    if (!fragment.nthChildFilters.isEmpty())
1782        generateElementIsNthChild(matchingPostTagNameFailureCases, fragment);
1783    if (!fragment.notFilters.isEmpty())
1784        generateElementMatchesNotPseudoClass(matchingPostTagNameFailureCases, fragment);
1785    if (!fragment.anyFilters.isEmpty())
1786        generateElementMatchesAnyPseudoClass(matchingPostTagNameFailureCases, fragment);
1787    if (fragment.langFilter)
1788        generateElementIsInLanguage(matchingPostTagNameFailureCases, *fragment.langFilter);
1789}
1790
1791void SelectorCodeGenerator::generateElementDataMatching(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
1792{
1793    if (!fragment.id && fragment.classNames.isEmpty() && fragment.attributes.isEmpty())
1794        return;
1795
1796    //  Generate:
1797    //     elementDataAddress = element->elementData();
1798    //     if (!elementDataAddress)
1799    //         failure!
1800    LocalRegister elementDataAddress(m_registerAllocator);
1801    m_assembler.loadPtr(Assembler::Address(elementAddressRegister, Element::elementDataMemoryOffset()), elementDataAddress);
1802    failureCases.append(m_assembler.branchTestPtr(Assembler::Zero, elementDataAddress));
1803
1804    if (fragment.id)
1805        generateElementHasId(failureCases, elementDataAddress, *fragment.id);
1806    if (!fragment.classNames.isEmpty())
1807        generateElementHasClasses(failureCases, elementDataAddress, fragment.classNames);
1808    if (!fragment.attributes.isEmpty())
1809        generateElementAttributesMatching(failureCases, elementDataAddress, fragment);
1810}
1811
1812static inline Assembler::Jump testIsHTMLFlagOnNode(Assembler::ResultCondition condition, Assembler& assembler, Assembler::RegisterID nodeAddress)
1813{
1814    return assembler.branchTest32(condition, Assembler::Address(nodeAddress, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagIsHTML()));
1815}
1816
1817static inline bool canMatchStyleAttribute(const SelectorFragment& fragment)
1818{
1819    for (unsigned i = 0; i < fragment.attributes.size(); ++i) {
1820        const CSSSelector& attributeSelector = fragment.attributes[i].selector();
1821        const QualifiedName& attributeName = attributeSelector.attribute();
1822        if (Attribute::nameMatchesFilter(HTMLNames::styleAttr, attributeName.prefix(), attributeName.localName(), attributeName.namespaceURI()))
1823            return true;
1824
1825        const AtomicString& canonicalLocalName = attributeSelector.attributeCanonicalLocalName();
1826        if (attributeName.localName() != canonicalLocalName
1827            && Attribute::nameMatchesFilter(HTMLNames::styleAttr, attributeName.prefix(), attributeSelector.attributeCanonicalLocalName(), attributeName.namespaceURI())) {
1828            return true;
1829        }
1830    }
1831    return false;
1832}
1833
1834void SelectorCodeGenerator::generateSynchronizeStyleAttribute(Assembler::RegisterID elementDataArraySizeAndFlags)
1835{
1836    // The style attribute is updated lazily based on the flag styleAttributeIsDirty.
1837    Assembler::Jump styleAttributeNotDirty = m_assembler.branchTest32(Assembler::Zero, elementDataArraySizeAndFlags, Assembler::TrustedImm32(ElementData::styleAttributeIsDirtyFlag()));
1838
1839    FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
1840    functionCall.setFunctionAddress(StyledElement::synchronizeStyleAttributeInternal);
1841    Assembler::RegisterID elementAddress = elementAddressRegister;
1842    functionCall.setOneArgument(elementAddress);
1843    functionCall.call();
1844
1845    styleAttributeNotDirty.link(&m_assembler);
1846}
1847
1848static inline bool canMatchAnimatableSVGAttribute(const SelectorFragment& fragment)
1849{
1850    for (unsigned i = 0; i < fragment.attributes.size(); ++i) {
1851        const CSSSelector& attributeSelector = fragment.attributes[i].selector();
1852        const QualifiedName& selectorAttributeName = attributeSelector.attribute();
1853
1854        const QualifiedName& candidateForLocalName = SVGElement::animatableAttributeForName(selectorAttributeName.localName());
1855        if (Attribute::nameMatchesFilter(candidateForLocalName, selectorAttributeName.prefix(), selectorAttributeName.localName(), selectorAttributeName.namespaceURI()))
1856            return true;
1857
1858        const AtomicString& canonicalLocalName = attributeSelector.attributeCanonicalLocalName();
1859        if (selectorAttributeName.localName() != canonicalLocalName) {
1860            const QualifiedName& candidateForCanonicalLocalName = SVGElement::animatableAttributeForName(selectorAttributeName.localName());
1861            if (Attribute::nameMatchesFilter(candidateForCanonicalLocalName, selectorAttributeName.prefix(), selectorAttributeName.localName(), selectorAttributeName.namespaceURI()))
1862                return true;
1863        }
1864    }
1865    return false;
1866}
1867
1868void SelectorCodeGenerator::generateSynchronizeAllAnimatedSVGAttribute(Assembler::RegisterID elementDataArraySizeAndFlags)
1869{
1870    // SVG attributes can be updated lazily depending on the flag AnimatedSVGAttributesAreDirty. We need to check
1871    // that first.
1872    Assembler::Jump animatedSVGAttributesNotDirty = m_assembler.branchTest32(Assembler::Zero, elementDataArraySizeAndFlags, Assembler::TrustedImm32(ElementData::animatedSVGAttributesAreDirtyFlag()));
1873
1874    FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
1875    functionCall.setFunctionAddress(SVGElement::synchronizeAllAnimatedSVGAttribute);
1876    Assembler::RegisterID elementAddress = elementAddressRegister;
1877    functionCall.setOneArgument(elementAddress);
1878    functionCall.call();
1879
1880    animatedSVGAttributesNotDirty.link(&m_assembler);
1881}
1882
1883void SelectorCodeGenerator::generateElementAttributesMatching(Assembler::JumpList& failureCases, const LocalRegister& elementDataAddress, const SelectorFragment& fragment)
1884{
1885    LocalRegister scratchRegister(m_registerAllocator);
1886    Assembler::RegisterID elementDataArraySizeAndFlags = scratchRegister;
1887    Assembler::RegisterID attributeArrayLength = scratchRegister;
1888
1889    m_assembler.load32(Assembler::Address(elementDataAddress, ElementData::arraySizeAndFlagsMemoryOffset()), elementDataArraySizeAndFlags);
1890
1891    if (canMatchStyleAttribute(fragment))
1892        generateSynchronizeStyleAttribute(elementDataArraySizeAndFlags);
1893
1894    if (canMatchAnimatableSVGAttribute(fragment))
1895        generateSynchronizeAllAnimatedSVGAttribute(elementDataArraySizeAndFlags);
1896
1897    // Attributes can be stored either in a separate vector for UniqueElementData, or after the elementData itself
1898    // for ShareableElementData.
1899    LocalRegister attributeArrayPointer(m_registerAllocator);
1900    Assembler::Jump isShareableElementData  = m_assembler.branchTest32(Assembler::Zero, elementDataArraySizeAndFlags, Assembler::TrustedImm32(ElementData::isUniqueFlag()));
1901    {
1902        ptrdiff_t attributeVectorOffset = UniqueElementData::attributeVectorMemoryOffset();
1903        m_assembler.loadPtr(Assembler::Address(elementDataAddress, attributeVectorOffset + UniqueElementData::AttributeVector::dataMemoryOffset()), attributeArrayPointer);
1904        m_assembler.load32(Assembler::Address(elementDataAddress, attributeVectorOffset + UniqueElementData::AttributeVector::sizeMemoryOffset()), attributeArrayLength);
1905    }
1906    Assembler::Jump skipShareable = m_assembler.jump();
1907
1908    {
1909        isShareableElementData.link(&m_assembler);
1910        m_assembler.urshift32(elementDataArraySizeAndFlags, Assembler::TrustedImm32(ElementData::arraySizeOffset()), attributeArrayLength);
1911        m_assembler.addPtr(Assembler::TrustedImm32(ShareableElementData::attributeArrayMemoryOffset()), elementDataAddress, attributeArrayPointer);
1912    }
1913
1914    skipShareable.link(&m_assembler);
1915
1916    // If there are no attributes, fail immediately.
1917    failureCases.append(m_assembler.branchTest32(Assembler::Zero, attributeArrayLength));
1918
1919    unsigned attributeCount = fragment.attributes.size();
1920    for (unsigned i = 0; i < attributeCount; ++i) {
1921        Assembler::RegisterID decIndexRegister;
1922        Assembler::RegisterID currentAttributeAddress;
1923
1924        bool isLastAttribute = i == (attributeCount - 1);
1925        if (!isLastAttribute) {
1926            // We need to make a copy to let the next iterations use the values.
1927            currentAttributeAddress = m_registerAllocator.allocateRegister();
1928            decIndexRegister = m_registerAllocator.allocateRegister();
1929            m_assembler.move(attributeArrayPointer, currentAttributeAddress);
1930            m_assembler.move(attributeArrayLength, decIndexRegister);
1931        } else {
1932            currentAttributeAddress = attributeArrayPointer;
1933            decIndexRegister = attributeArrayLength;
1934        }
1935
1936        generateElementAttributeMatching(failureCases, currentAttributeAddress, decIndexRegister, fragment.attributes[i]);
1937
1938        if (!isLastAttribute) {
1939            m_registerAllocator.deallocateRegister(decIndexRegister);
1940            m_registerAllocator.deallocateRegister(currentAttributeAddress);
1941        }
1942    }
1943}
1944
1945void SelectorCodeGenerator::generateElementAttributeMatching(Assembler::JumpList& failureCases, Assembler::RegisterID currentAttributeAddress, Assembler::RegisterID decIndexRegister, const AttributeMatchingInfo& attributeInfo)
1946{
1947    // Get the localName used for comparison. HTML elements use a lowercase local name known in selectors as canonicalLocalName.
1948    LocalRegister localNameToMatch(m_registerAllocator);
1949
1950    // In general, canonicalLocalName and localName are the same. When they differ, we have to check if the node is HTML to know
1951    // which one to use.
1952    const CSSSelector& attributeSelector = attributeInfo.selector();
1953    const AtomicStringImpl* canonicalLocalName = attributeSelector.attributeCanonicalLocalName().impl();
1954    const AtomicStringImpl* localName = attributeSelector.attribute().localName().impl();
1955    if (canonicalLocalName == localName)
1956        m_assembler.move(Assembler::TrustedImmPtr(canonicalLocalName), localNameToMatch);
1957    else {
1958        m_assembler.move(Assembler::TrustedImmPtr(canonicalLocalName), localNameToMatch);
1959        Assembler::Jump elementIsHTML = testIsHTMLFlagOnNode(Assembler::NonZero, m_assembler, elementAddressRegister);
1960        m_assembler.move(Assembler::TrustedImmPtr(localName), localNameToMatch);
1961        elementIsHTML.link(&m_assembler);
1962    }
1963
1964    Assembler::JumpList successCases;
1965    Assembler::Label loopStart(m_assembler.label());
1966
1967    {
1968        LocalRegister qualifiedNameImpl(m_registerAllocator);
1969        m_assembler.loadPtr(Assembler::Address(currentAttributeAddress, Attribute::nameMemoryOffset()), qualifiedNameImpl);
1970
1971        bool shouldCheckNamespace = attributeSelector.attribute().prefix() != starAtom;
1972        if (shouldCheckNamespace) {
1973            Assembler::Jump nameDoesNotMatch = m_assembler.branchPtr(Assembler::NotEqual, Assembler::Address(qualifiedNameImpl, QualifiedName::QualifiedNameImpl::localNameMemoryOffset()), localNameToMatch);
1974
1975            const AtomicStringImpl* namespaceURI = attributeSelector.attribute().namespaceURI().impl();
1976            if (namespaceURI) {
1977                LocalRegister namespaceToMatch(m_registerAllocator);
1978                m_assembler.move(Assembler::TrustedImmPtr(namespaceURI), namespaceToMatch);
1979                successCases.append(m_assembler.branchPtr(Assembler::Equal, Assembler::Address(qualifiedNameImpl, QualifiedName::QualifiedNameImpl::namespaceMemoryOffset()), namespaceToMatch));
1980            } else
1981                successCases.append(m_assembler.branchTestPtr(Assembler::Zero, Assembler::Address(qualifiedNameImpl, QualifiedName::QualifiedNameImpl::namespaceMemoryOffset())));
1982            nameDoesNotMatch.link(&m_assembler);
1983        } else
1984            successCases.append(m_assembler.branchPtr(Assembler::Equal, Assembler::Address(qualifiedNameImpl, QualifiedName::QualifiedNameImpl::localNameMemoryOffset()), localNameToMatch));
1985    }
1986
1987    Assembler::Label loopReEntry(m_assembler.label());
1988
1989    // If we reached the last element -> failure.
1990    failureCases.append(m_assembler.branchSub32(Assembler::Zero, Assembler::TrustedImm32(1), decIndexRegister));
1991
1992    // Otherwise just loop over.
1993    m_assembler.addPtr(Assembler::TrustedImm32(sizeof(Attribute)), currentAttributeAddress);
1994    m_assembler.jump().linkTo(loopStart, &m_assembler);
1995
1996    successCases.link(&m_assembler);
1997
1998    if (attributeSelector.m_match != CSSSelector::Set) {
1999        // We make the assumption that name matching fails in most cases and we keep value matching outside
2000        // of the loop. We re-enter the loop if needed.
2001        // FIXME: exact case sensitive value matching is so simple that it should be done in the loop.
2002        Assembler::JumpList localFailureCases;
2003        generateElementAttributeValueMatching(localFailureCases, currentAttributeAddress, attributeInfo);
2004        localFailureCases.linkTo(loopReEntry, &m_assembler);
2005    }
2006}
2007
2008enum CaseSensitivity {
2009    CaseSensitive,
2010    CaseInsensitive
2011};
2012
2013template<CaseSensitivity caseSensitivity>
2014static bool attributeValueBeginsWith(const Attribute* attribute, AtomicStringImpl* expectedString)
2015{
2016    AtomicStringImpl& valueImpl = *attribute->value().impl();
2017    if (caseSensitivity == CaseSensitive)
2018        return valueImpl.startsWith(expectedString);
2019    return valueImpl.startsWith(expectedString, false);
2020}
2021
2022template<CaseSensitivity caseSensitivity>
2023static bool attributeValueContains(const Attribute* attribute, AtomicStringImpl* expectedString)
2024{
2025    AtomicStringImpl& valueImpl = *attribute->value().impl();
2026    if (caseSensitivity == CaseSensitive)
2027        return valueImpl.find(expectedString) != notFound;
2028    return valueImpl.findIgnoringCase(expectedString) != notFound;
2029}
2030
2031template<CaseSensitivity caseSensitivity>
2032static bool attributeValueEndsWith(const Attribute* attribute, AtomicStringImpl* expectedString)
2033{
2034    AtomicStringImpl& valueImpl = *attribute->value().impl();
2035    if (caseSensitivity == CaseSensitive)
2036        return valueImpl.endsWith(expectedString);
2037    return valueImpl.endsWith(expectedString, false);
2038}
2039
2040template<CaseSensitivity caseSensitivity>
2041static bool attributeValueMatchHyphenRule(const Attribute* attribute, AtomicStringImpl* expectedString)
2042{
2043    AtomicStringImpl& valueImpl = *attribute->value().impl();
2044    if (valueImpl.length() < expectedString->length())
2045        return false;
2046
2047    bool valueStartsWithExpectedString;
2048    if (caseSensitivity == CaseSensitive)
2049        valueStartsWithExpectedString = valueImpl.startsWith(expectedString);
2050    else
2051        valueStartsWithExpectedString = valueImpl.startsWith(expectedString, false);
2052
2053    if (!valueStartsWithExpectedString)
2054        return false;
2055
2056    return valueImpl.length() == expectedString->length() || valueImpl[expectedString->length()] == '-';
2057}
2058
2059template<CaseSensitivity caseSensitivity>
2060static bool attributeValueSpaceSeparetedListContains(const Attribute* attribute, AtomicStringImpl* expectedString)
2061{
2062    AtomicStringImpl& value = *attribute->value().impl();
2063
2064    unsigned startSearchAt = 0;
2065    while (true) {
2066        size_t foundPos;
2067        if (caseSensitivity == CaseSensitive)
2068            foundPos = value.find(expectedString, startSearchAt);
2069        else
2070            foundPos = value.findIgnoringCase(expectedString, startSearchAt);
2071        if (foundPos == notFound)
2072            return false;
2073        if (!foundPos || value[foundPos - 1] == ' ') {
2074            unsigned endStr = foundPos + expectedString->length();
2075            if (endStr == value.length() || value[endStr] == ' ')
2076                return true;
2077        }
2078        startSearchAt = foundPos + 1;
2079    }
2080    return false;
2081}
2082
2083void SelectorCodeGenerator::generateElementAttributeValueMatching(Assembler::JumpList& failureCases, Assembler::RegisterID currentAttributeAddress, const AttributeMatchingInfo& attributeInfo)
2084{
2085    const CSSSelector& attributeSelector = attributeInfo.selector();
2086    const AtomicString& expectedValue = attributeSelector.value();
2087    ASSERT(!expectedValue.isNull());
2088    bool defaultToCaseSensitiveValueMatch = attributeInfo.canDefaultToCaseSensitiveValueMatch();
2089
2090    switch (attributeSelector.m_match) {
2091    case CSSSelector::Begin:
2092        generateElementAttributeFunctionCallValueMatching(failureCases, currentAttributeAddress, expectedValue, defaultToCaseSensitiveValueMatch, attributeValueBeginsWith<CaseSensitive>, attributeValueBeginsWith<CaseInsensitive>);
2093        break;
2094    case CSSSelector::Contain:
2095        generateElementAttributeFunctionCallValueMatching(failureCases, currentAttributeAddress, expectedValue, defaultToCaseSensitiveValueMatch, attributeValueContains<CaseSensitive>, attributeValueContains<CaseInsensitive>);
2096        break;
2097    case CSSSelector::End:
2098        generateElementAttributeFunctionCallValueMatching(failureCases, currentAttributeAddress, expectedValue, defaultToCaseSensitiveValueMatch, attributeValueEndsWith<CaseSensitive>, attributeValueEndsWith<CaseInsensitive>);
2099        break;
2100    case CSSSelector::Exact:
2101        generateElementAttributeValueExactMatching(failureCases, currentAttributeAddress, expectedValue, defaultToCaseSensitiveValueMatch);
2102        break;
2103    case CSSSelector::Hyphen:
2104        generateElementAttributeFunctionCallValueMatching(failureCases, currentAttributeAddress, expectedValue, defaultToCaseSensitiveValueMatch, attributeValueMatchHyphenRule<CaseSensitive>, attributeValueMatchHyphenRule<CaseInsensitive>);
2105        break;
2106    case CSSSelector::List:
2107        generateElementAttributeFunctionCallValueMatching(failureCases, currentAttributeAddress, expectedValue, defaultToCaseSensitiveValueMatch, attributeValueSpaceSeparetedListContains<CaseSensitive>, attributeValueSpaceSeparetedListContains<CaseInsensitive>);
2108        break;
2109    default:
2110        ASSERT_NOT_REACHED();
2111    }
2112}
2113
2114static inline Assembler::Jump testIsHTMLClassOnDocument(Assembler::ResultCondition condition, Assembler& assembler, Assembler::RegisterID documentAddress)
2115{
2116    return assembler.branchTest32(condition, Assembler::Address(documentAddress, Document::documentClassesMemoryOffset()), Assembler::TrustedImm32(Document::isHTMLDocumentClassFlag()));
2117}
2118
2119void SelectorCodeGenerator::generateElementAttributeValueExactMatching(Assembler::JumpList& failureCases, Assembler::RegisterID currentAttributeAddress, const AtomicString& expectedValue, bool canDefaultToCaseSensitiveValueMatch)
2120{
2121    LocalRegisterWithPreference expectedValueRegister(m_registerAllocator, JSC::GPRInfo::argumentGPR1);
2122    m_assembler.move(Assembler::TrustedImmPtr(expectedValue.impl()), expectedValueRegister);
2123
2124    if (canDefaultToCaseSensitiveValueMatch)
2125        failureCases.append(m_assembler.branchPtr(Assembler::NotEqual, Assembler::Address(currentAttributeAddress, Attribute::valueMemoryOffset()), expectedValueRegister));
2126    else {
2127        Assembler::Jump skipCaseInsensitiveComparison = m_assembler.branchPtr(Assembler::Equal, Assembler::Address(currentAttributeAddress, Attribute::valueMemoryOffset()), expectedValueRegister);
2128
2129        // If the element is an HTML element, in a HTML dcoument (not including XHTML), value matching is case insensitive.
2130        // Taking the contrapositive, if we find the element is not HTML or is not in a HTML document, the condition above
2131        // sould be sufficient and we can fail early.
2132        failureCases.append(testIsHTMLFlagOnNode(Assembler::Zero, m_assembler, elementAddressRegister));
2133
2134        {
2135            LocalRegister document(m_registerAllocator);
2136            getDocument(m_assembler, elementAddressRegister, document);
2137            failureCases.append(testIsHTMLClassOnDocument(Assembler::Zero, m_assembler, document));
2138        }
2139
2140        LocalRegister valueStringImpl(m_registerAllocator);
2141        m_assembler.loadPtr(Assembler::Address(currentAttributeAddress, Attribute::valueMemoryOffset()), valueStringImpl);
2142
2143        FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2144        functionCall.setFunctionAddress(WTF::equalIgnoringCaseNonNull);
2145        functionCall.setTwoArguments(valueStringImpl, expectedValueRegister);
2146        failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
2147
2148        skipCaseInsensitiveComparison.link(&m_assembler);
2149    }
2150}
2151
2152void SelectorCodeGenerator::generateElementAttributeFunctionCallValueMatching(Assembler::JumpList& failureCases, Assembler::RegisterID currentAttributeAddress, const AtomicString& expectedValue, bool canDefaultToCaseSensitiveValueMatch, JSC::FunctionPtr caseSensitiveTest, JSC::FunctionPtr caseInsensitiveTest)
2153{
2154    LocalRegisterWithPreference expectedValueRegister(m_registerAllocator, JSC::GPRInfo::argumentGPR1);
2155    m_assembler.move(Assembler::TrustedImmPtr(expectedValue.impl()), expectedValueRegister);
2156
2157    if (canDefaultToCaseSensitiveValueMatch) {
2158        FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2159        functionCall.setFunctionAddress(caseSensitiveTest);
2160        functionCall.setTwoArguments(currentAttributeAddress, expectedValueRegister);
2161        failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
2162    } else {
2163        Assembler::JumpList shouldUseCaseSensitiveComparison;
2164        shouldUseCaseSensitiveComparison.append(testIsHTMLFlagOnNode(Assembler::Zero, m_assembler, elementAddressRegister));
2165        {
2166            LocalRegister scratchRegister(m_registerAllocator);
2167            // scratchRegister = pointer to treeScope.
2168            m_assembler.loadPtr(Assembler::Address(elementAddressRegister, Node::treeScopeMemoryOffset()), scratchRegister);
2169            // scratchRegister = pointer to document.
2170            m_assembler.loadPtr(Assembler::Address(scratchRegister, TreeScope::documentScopeMemoryOffset()), scratchRegister);
2171            shouldUseCaseSensitiveComparison.append(testIsHTMLClassOnDocument(Assembler::Zero, m_assembler, scratchRegister));
2172        }
2173
2174        {
2175            FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2176            functionCall.setFunctionAddress(caseInsensitiveTest);
2177            functionCall.setTwoArguments(currentAttributeAddress, expectedValueRegister);
2178            failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
2179        }
2180
2181        Assembler::Jump skipCaseSensitiveCase = m_assembler.jump();
2182
2183        {
2184            shouldUseCaseSensitiveComparison.link(&m_assembler);
2185            FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2186            functionCall.setFunctionAddress(caseSensitiveTest);
2187            functionCall.setTwoArguments(currentAttributeAddress, expectedValueRegister);
2188            failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
2189        }
2190
2191        skipCaseSensitiveCase.link(&m_assembler);
2192    }
2193}
2194
2195void SelectorCodeGenerator::generateElementFunctionCallTest(Assembler::JumpList& failureCases, JSC::FunctionPtr testFunction)
2196{
2197    Assembler::RegisterID elementAddress = elementAddressRegister;
2198    FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2199    functionCall.setFunctionAddress(testFunction);
2200    functionCall.setOneArgument(elementAddress);
2201    failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
2202}
2203
2204static void setFirstChildState(Element* element)
2205{
2206    if (RenderStyle* style = element->renderStyle())
2207        style->setFirstChildState();
2208}
2209
2210static bool elementIsActive(Element* element)
2211{
2212    return element->active() || InspectorInstrumentation::forcePseudoState(element, CSSSelector::PseudoClassActive);
2213}
2214
2215static bool elementIsActiveForStyleResolution(Element* element, const CheckingContext* checkingContext)
2216{
2217    if (checkingContext->resolvingMode == SelectorChecker::Mode::ResolvingStyle)
2218        element->setChildrenAffectedByActive();
2219    return element->active() || InspectorInstrumentation::forcePseudoState(element, CSSSelector::PseudoClassActive);
2220}
2221
2222void SelectorCodeGenerator::generateElementIsActive(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
2223{
2224    generateSpecialFailureInQuirksModeForActiveAndHoverIfNeeded(failureCases, fragment);
2225    if (m_selectorContext == SelectorContext::QuerySelector) {
2226        FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2227        functionCall.setFunctionAddress(elementIsActive);
2228        functionCall.setOneArgument(elementAddressRegister);
2229        failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
2230    } else {
2231        if (shouldUseRenderStyleFromCheckingContext(fragment)) {
2232            LocalRegister checkingContext(m_registerAllocator);
2233            Assembler::Jump notResolvingStyle = jumpIfNotResolvingStyle(checkingContext);
2234            addFlagsToElementStyleFromContext(checkingContext, RenderStyle::NonInheritedFlags::flagIsaffectedByActive());
2235            notResolvingStyle.link(&m_assembler);
2236
2237            FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2238            functionCall.setFunctionAddress(elementIsActive);
2239            functionCall.setOneArgument(elementAddressRegister);
2240            failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
2241        } else {
2242            unsigned offsetToCheckingContext = m_stackAllocator.offsetToStackReference(m_checkingContextStackReference);
2243            Assembler::RegisterID checkingContext = m_registerAllocator.allocateRegisterWithPreference(JSC::GPRInfo::argumentGPR1);
2244            m_assembler.loadPtr(Assembler::Address(Assembler::stackPointerRegister, offsetToCheckingContext), checkingContext);
2245            m_registerAllocator.deallocateRegister(checkingContext);
2246
2247            FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2248            functionCall.setFunctionAddress(elementIsActiveForStyleResolution);
2249            functionCall.setTwoArguments(elementAddressRegister, checkingContext);
2250            failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
2251        }
2252    }
2253}
2254
2255void SelectorCodeGenerator::generateElementIsFirstChild(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
2256{
2257    if (m_selectorContext == SelectorContext::QuerySelector) {
2258        Assembler::JumpList successCase = jumpIfNoPreviousAdjacentElement();
2259        failureCases.append(m_assembler.jump());
2260        successCase.link(&m_assembler);
2261        LocalRegister parent(m_registerAllocator);
2262        generateWalkToParentElement(failureCases, parent);
2263        return;
2264    }
2265
2266    Assembler::RegisterID parentElement = m_registerAllocator.allocateRegister();
2267    generateWalkToParentElement(failureCases, parentElement);
2268
2269    // Zero in isFirstChildRegister is the success case. The register is set to non-zero if a sibling if found.
2270    LocalRegister isFirstChildRegister(m_registerAllocator);
2271    m_assembler.move(Assembler::TrustedImm32(0), isFirstChildRegister);
2272
2273    {
2274        Assembler::JumpList successCase = jumpIfNoPreviousAdjacentElement();
2275
2276        // If there was a sibling element, the element was not the first child -> failure case.
2277        m_assembler.move(Assembler::TrustedImm32(1), isFirstChildRegister);
2278
2279        successCase.link(&m_assembler);
2280    }
2281
2282    LocalRegister checkingContext(m_registerAllocator);
2283    Assembler::Jump notResolvingStyle = jumpIfNotResolvingStyle(checkingContext);
2284
2285    setNodeFlag(m_assembler, parentElement, Node::flagChildrenAffectedByFirstChildRulesFlag());
2286    m_registerAllocator.deallocateRegister(parentElement);
2287
2288    // The parent marking is unconditional. If the matching is not a success, we can now fail.
2289    // Otherwise we need to apply setFirstChildState() on the RenderStyle.
2290    failureCases.append(m_assembler.branchTest32(Assembler::NonZero, isFirstChildRegister));
2291
2292    if (shouldUseRenderStyleFromCheckingContext(fragment))
2293        addFlagsToElementStyleFromContext(checkingContext, RenderStyle::NonInheritedFlags::setFirstChildStateFlags());
2294    else {
2295        FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2296        functionCall.setFunctionAddress(setFirstChildState);
2297        Assembler::RegisterID elementAddress = elementAddressRegister;
2298        functionCall.setOneArgument(elementAddress);
2299        functionCall.call();
2300    }
2301
2302    notResolvingStyle.link(&m_assembler);
2303    failureCases.append(m_assembler.branchTest32(Assembler::NonZero, isFirstChildRegister));
2304}
2305
2306static bool elementIsHovered(Element* element)
2307{
2308    return element->hovered() || InspectorInstrumentation::forcePseudoState(element, CSSSelector::PseudoClassHover);
2309}
2310
2311static bool elementIsHoveredForStyleResolution(Element* element, const CheckingContext* checkingContext)
2312{
2313    if (checkingContext->resolvingMode == SelectorChecker::Mode::ResolvingStyle)
2314        element->setChildrenAffectedByHover();
2315    return element->hovered() || InspectorInstrumentation::forcePseudoState(element, CSSSelector::PseudoClassHover);
2316}
2317
2318void SelectorCodeGenerator::generateElementIsHovered(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
2319{
2320    generateSpecialFailureInQuirksModeForActiveAndHoverIfNeeded(failureCases, fragment);
2321    if (m_selectorContext == SelectorContext::QuerySelector) {
2322        FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2323        functionCall.setFunctionAddress(elementIsHovered);
2324        functionCall.setOneArgument(elementAddressRegister);
2325        failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
2326    } else {
2327        if (shouldUseRenderStyleFromCheckingContext(fragment)) {
2328            LocalRegisterWithPreference checkingContext(m_registerAllocator, JSC::GPRInfo::argumentGPR1);
2329            Assembler::Jump notResolvingStyle = jumpIfNotResolvingStyle(checkingContext);
2330            addFlagsToElementStyleFromContext(checkingContext, RenderStyle::NonInheritedFlags::flagIsaffectedByHover());
2331            notResolvingStyle.link(&m_assembler);
2332
2333            FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2334            functionCall.setFunctionAddress(elementIsHovered);
2335            functionCall.setOneArgument(elementAddressRegister);
2336            failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
2337        } else {
2338            unsigned offsetToCheckingContext = m_stackAllocator.offsetToStackReference(m_checkingContextStackReference);
2339            Assembler::RegisterID checkingContext = m_registerAllocator.allocateRegisterWithPreference(JSC::GPRInfo::argumentGPR1);
2340            m_assembler.loadPtr(Assembler::Address(Assembler::stackPointerRegister, offsetToCheckingContext), checkingContext);
2341            m_registerAllocator.deallocateRegister(checkingContext);
2342
2343            FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2344            functionCall.setFunctionAddress(elementIsHoveredForStyleResolution);
2345            functionCall.setTwoArguments(elementAddressRegister, checkingContext);
2346            failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
2347        }
2348    }
2349}
2350
2351void SelectorCodeGenerator::generateElementIsInLanguage(Assembler::JumpList& failureCases, const AtomicString& langFilter)
2352{
2353    LocalRegisterWithPreference langFilterRegister(m_registerAllocator, JSC::GPRInfo::argumentGPR1);
2354    m_assembler.move(Assembler::TrustedImmPtr(langFilter.impl()), langFilterRegister);
2355
2356    Assembler::RegisterID elementAddress = elementAddressRegister;
2357    FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2358    functionCall.setFunctionAddress(matchesLangPseudoClass);
2359    functionCall.setTwoArguments(elementAddress, langFilterRegister);
2360    failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
2361}
2362
2363static void setLastChildState(Element* element)
2364{
2365    if (RenderStyle* style = element->renderStyle())
2366        style->setLastChildState();
2367}
2368
2369void SelectorCodeGenerator::generateElementIsLastChild(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
2370{
2371    if (m_selectorContext == SelectorContext::QuerySelector) {
2372        Assembler::JumpList successCase = jumpIfNoNextAdjacentElement();
2373        failureCases.append(m_assembler.jump());
2374
2375        successCase.link(&m_assembler);
2376        LocalRegister parent(m_registerAllocator);
2377        generateWalkToParentElement(failureCases, parent);
2378
2379        failureCases.append(m_assembler.branchTest32(Assembler::Zero, Assembler::Address(parent, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagIsParsingChildrenFinished())));
2380
2381        return;
2382    }
2383
2384    Assembler::RegisterID parentElement = m_registerAllocator.allocateRegister();
2385    generateWalkToParentElement(failureCases, parentElement);
2386
2387    // Zero in isLastChildRegister is the success case. The register is set to non-zero if a sibling if found.
2388    LocalRegister isLastChildRegister(m_registerAllocator);
2389    m_assembler.move(Assembler::TrustedImm32(0), isLastChildRegister);
2390
2391    {
2392        Assembler::Jump notFinishedParsingChildren = m_assembler.branchTest32(Assembler::Zero, Assembler::Address(parentElement, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagIsParsingChildrenFinished()));
2393
2394        Assembler::JumpList successCase = jumpIfNoNextAdjacentElement();
2395
2396        notFinishedParsingChildren.link(&m_assembler);
2397        m_assembler.move(Assembler::TrustedImm32(1), isLastChildRegister);
2398
2399        successCase.link(&m_assembler);
2400    }
2401
2402    LocalRegister checkingContext(m_registerAllocator);
2403    Assembler::Jump notResolvingStyle = jumpIfNotResolvingStyle(checkingContext);
2404
2405    setNodeFlag(m_assembler, parentElement, Node::flagChildrenAffectedByLastChildRulesFlag());
2406    m_registerAllocator.deallocateRegister(parentElement);
2407
2408    // The parent marking is unconditional. If the matching is not a success, we can now fail.
2409    // Otherwise we need to apply setLastChildState() on the RenderStyle.
2410    failureCases.append(m_assembler.branchTest32(Assembler::NonZero, isLastChildRegister));
2411
2412    if (shouldUseRenderStyleFromCheckingContext(fragment))
2413        addFlagsToElementStyleFromContext(checkingContext, RenderStyle::NonInheritedFlags::setLastChildStateFlags());
2414    else {
2415        FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2416        functionCall.setFunctionAddress(setLastChildState);
2417        Assembler::RegisterID elementAddress = elementAddressRegister;
2418        functionCall.setOneArgument(elementAddress);
2419        functionCall.call();
2420    }
2421
2422    notResolvingStyle.link(&m_assembler);
2423    failureCases.append(m_assembler.branchTest32(Assembler::NonZero, isLastChildRegister));
2424}
2425
2426static void setOnlyChildState(Element* element)
2427{
2428    if (RenderStyle* style = element->renderStyle()) {
2429        style->setFirstChildState();
2430        style->setLastChildState();
2431    }
2432}
2433
2434void SelectorCodeGenerator::generateElementIsOnlyChild(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
2435{
2436    // Is Only child is pretty much a combination of isFirstChild + isLastChild. The main difference is that tree marking is combined.
2437    if (m_selectorContext == SelectorContext::QuerySelector) {
2438        Assembler::JumpList previousSuccessCase = jumpIfNoPreviousAdjacentElement();
2439        failureCases.append(m_assembler.jump());
2440        previousSuccessCase.link(&m_assembler);
2441
2442        Assembler::JumpList nextSuccessCase = jumpIfNoNextAdjacentElement();
2443        failureCases.append(m_assembler.jump());
2444        nextSuccessCase.link(&m_assembler);
2445
2446        LocalRegister parent(m_registerAllocator);
2447        generateWalkToParentElement(failureCases, parent);
2448
2449        failureCases.append(m_assembler.branchTest32(Assembler::Zero, Assembler::Address(parent, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagIsParsingChildrenFinished())));
2450
2451        return;
2452    }
2453
2454    Assembler::RegisterID parentElement = m_registerAllocator.allocateRegister();
2455    generateWalkToParentElement(failureCases, parentElement);
2456
2457    // Zero in isOnlyChildRegister is the success case. The register is set to non-zero if a sibling if found.
2458    LocalRegister isOnlyChildRegister(m_registerAllocator);
2459    m_assembler.move(Assembler::TrustedImm32(0), isOnlyChildRegister);
2460
2461    {
2462        Assembler::JumpList localFailureCases;
2463        {
2464            Assembler::JumpList successCase = jumpIfNoPreviousAdjacentElement();
2465            localFailureCases.append(m_assembler.jump());
2466            successCase.link(&m_assembler);
2467        }
2468        localFailureCases.append(m_assembler.branchTest32(Assembler::Zero, Assembler::Address(parentElement, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagIsParsingChildrenFinished())));
2469        Assembler::JumpList successCase = jumpIfNoNextAdjacentElement();
2470
2471        localFailureCases.link(&m_assembler);
2472        m_assembler.move(Assembler::TrustedImm32(1), isOnlyChildRegister);
2473
2474        successCase.link(&m_assembler);
2475    }
2476
2477    LocalRegister checkingContext(m_registerAllocator);
2478    Assembler::Jump notResolvingStyle = jumpIfNotResolvingStyle(checkingContext);
2479
2480    setNodeFlag(m_assembler, parentElement, Node::flagChildrenAffectedByFirstChildRulesFlag() | Node::flagChildrenAffectedByLastChildRulesFlag());
2481    m_registerAllocator.deallocateRegister(parentElement);
2482
2483    // The parent marking is unconditional. If the matching is not a success, we can now fail.
2484    // Otherwise we need to apply setLastChildState() on the RenderStyle.
2485    failureCases.append(m_assembler.branchTest32(Assembler::NonZero, isOnlyChildRegister));
2486
2487    if (shouldUseRenderStyleFromCheckingContext(fragment))
2488        addFlagsToElementStyleFromContext(checkingContext, RenderStyle::NonInheritedFlags::setFirstChildStateFlags() | RenderStyle::NonInheritedFlags::setLastChildStateFlags());
2489    else {
2490        FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2491        functionCall.setFunctionAddress(setOnlyChildState);
2492        Assembler::RegisterID elementAddress = elementAddressRegister;
2493        functionCall.setOneArgument(elementAddress);
2494        functionCall.call();
2495    }
2496
2497    notResolvingStyle.link(&m_assembler);
2498    failureCases.append(m_assembler.branchTest32(Assembler::NonZero, isOnlyChildRegister));
2499}
2500
2501inline void SelectorCodeGenerator::generateElementHasTagName(Assembler::JumpList& failureCases, const QualifiedName& nameToMatch)
2502{
2503    if (nameToMatch == anyQName())
2504        return;
2505
2506    // Load the QualifiedNameImpl from the input.
2507    LocalRegister qualifiedNameImpl(m_registerAllocator);
2508    m_assembler.loadPtr(Assembler::Address(elementAddressRegister, Element::tagQNameMemoryOffset() + QualifiedName::implMemoryOffset()), qualifiedNameImpl);
2509
2510    const AtomicString& selectorLocalName = nameToMatch.localName();
2511    if (selectorLocalName != starAtom) {
2512        // Generate localName == element->localName().
2513        LocalRegister constantRegister(m_registerAllocator);
2514        m_assembler.move(Assembler::TrustedImmPtr(selectorLocalName.impl()), constantRegister);
2515        failureCases.append(m_assembler.branchPtr(Assembler::NotEqual, Assembler::Address(qualifiedNameImpl, QualifiedName::QualifiedNameImpl::localNameMemoryOffset()), constantRegister));
2516    }
2517
2518    const AtomicString& selectorNamespaceURI = nameToMatch.namespaceURI();
2519    if (selectorNamespaceURI != starAtom) {
2520        // Generate namespaceURI == element->namespaceURI().
2521        LocalRegister constantRegister(m_registerAllocator);
2522        m_assembler.move(Assembler::TrustedImmPtr(selectorNamespaceURI.impl()), constantRegister);
2523        failureCases.append(m_assembler.branchPtr(Assembler::NotEqual, Assembler::Address(qualifiedNameImpl, QualifiedName::QualifiedNameImpl::namespaceMemoryOffset()), constantRegister));
2524    }
2525}
2526
2527void SelectorCodeGenerator::generateElementHasId(Assembler::JumpList& failureCases, const LocalRegister& elementDataAddress, const AtomicString& idToMatch)
2528{
2529    // Compare the pointers of the AtomicStringImpl from idForStyleResolution with the reference idToMatch.
2530    LocalRegister idToMatchRegister(m_registerAllocator);
2531    m_assembler.move(Assembler::TrustedImmPtr(idToMatch.impl()), idToMatchRegister);
2532    failureCases.append(m_assembler.branchPtr(Assembler::NotEqual, Assembler::Address(elementDataAddress, ElementData::idForStyleResolutionMemoryOffset()), idToMatchRegister));
2533}
2534
2535void SelectorCodeGenerator::generateElementHasClasses(Assembler::JumpList& failureCases, const LocalRegister& elementDataAddress, const Vector<const AtomicStringImpl*>& classNames)
2536{
2537    // Load m_classNames.
2538    LocalRegister spaceSplitStringData(m_registerAllocator);
2539    m_assembler.loadPtr(Assembler::Address(elementDataAddress, ElementData::classNamesMemoryOffset()), spaceSplitStringData);
2540
2541    // If SpaceSplitString does not have a SpaceSplitStringData pointer, it is empty -> failure case.
2542    failureCases.append(m_assembler.branchTestPtr(Assembler::Zero, spaceSplitStringData));
2543
2544    // We loop over the classes of SpaceSplitStringData for each class name we need to match.
2545    LocalRegister indexRegister(m_registerAllocator);
2546    for (unsigned i = 0; i < classNames.size(); ++i) {
2547        LocalRegister classNameToMatch(m_registerAllocator);
2548        m_assembler.move(Assembler::TrustedImmPtr(classNames[i]), classNameToMatch);
2549        m_assembler.move(Assembler::TrustedImm32(0), indexRegister);
2550
2551        // Beginning of a loop over all the class name of element to find the one we are looking for.
2552        Assembler::Label loopStart(m_assembler.label());
2553
2554        // If the pointers match, proceed to the next matcher.
2555        Assembler::Jump classFound = m_assembler.branchPtr(Assembler::Equal, Assembler::BaseIndex(spaceSplitStringData, indexRegister, Assembler::timesPtr(), SpaceSplitStringData::tokensMemoryOffset()), classNameToMatch);
2556
2557        // Increment the index.
2558        m_assembler.add32(Assembler::TrustedImm32(1), indexRegister);
2559
2560        // If we reached the last element -> failure.
2561        failureCases.append(m_assembler.branch32(Assembler::Equal, Assembler::Address(spaceSplitStringData, SpaceSplitStringData::sizeMemoryOffset()), indexRegister));
2562        // Otherwise just loop over.
2563        m_assembler.jump().linkTo(loopStart, &m_assembler);
2564
2565        // Success case.
2566        classFound.link(&m_assembler);
2567    }
2568}
2569
2570void SelectorCodeGenerator::generateElementIsLink(Assembler::JumpList& failureCases)
2571{
2572    failureCases.append(m_assembler.branchTest32(Assembler::Zero, Assembler::Address(elementAddressRegister, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagIsLink())));
2573}
2574
2575static void setElementChildIndex(Element* element, int index)
2576{
2577    element->setChildIndex(index);
2578}
2579
2580static void setElementChildIndexAndUpdateStyle(Element* element, int index)
2581{
2582    element->setChildIndex(index);
2583    if (RenderStyle* childStyle = element->renderStyle())
2584        childStyle->setUnique();
2585}
2586
2587void SelectorCodeGenerator::generateElementIsNthChild(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
2588{
2589    Assembler::RegisterID parentElement = m_registerAllocator.allocateRegister();
2590    generateWalkToParentElement(failureCases, parentElement);
2591
2592    Vector<std::pair<int, int>, 32> validSubsetFilters;
2593    validSubsetFilters.reserveInitialCapacity(fragment.nthChildFilters.size());
2594    for (const auto& slot : fragment.nthChildFilters) {
2595        int a = slot.first;
2596        int b = slot.second;
2597
2598        // Anything modulo 1 is zero. Unless b restricts the range, this does not filter anything out.
2599        if (a == 1 && (!b || (b == 1)))
2600            continue;
2601        validSubsetFilters.uncheckedAppend(slot);
2602    }
2603    if (validSubsetFilters.isEmpty()) {
2604        m_registerAllocator.deallocateRegister(parentElement);
2605        return;
2606    }
2607    if (m_selectorContext == SelectorContext::QuerySelector)
2608        m_registerAllocator.deallocateRegister(parentElement);
2609
2610    // Setup the counter at 1.
2611    LocalRegisterWithPreference elementCounter(m_registerAllocator, JSC::GPRInfo::argumentGPR1);
2612    m_assembler.move(Assembler::TrustedImm32(1), elementCounter);
2613
2614    // Loop over the previous adjacent elements and increment the counter.
2615    {
2616        LocalRegister previousSibling(m_registerAllocator);
2617        m_assembler.move(elementAddressRegister, previousSibling);
2618
2619        // Getting the child index is very efficient when it works. When there is no child index,
2620        // querying at every iteration is very inefficient. We solve this by only testing the child
2621        // index on the first direct adjacent.
2622        Assembler::JumpList noMoreSiblingsCases;
2623
2624        Assembler::JumpList noCachedChildIndexCases;
2625        generateWalkToPreviousAdjacentElement(noMoreSiblingsCases, previousSibling);
2626        noCachedChildIndexCases.append(m_assembler.branchTest32(Assembler::Zero, Assembler::Address(previousSibling, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagHasRareData())));
2627        {
2628            LocalRegister elementRareData(m_registerAllocator);
2629            m_assembler.loadPtr(Assembler::Address(previousSibling, Node::rareDataMemoryOffset()), elementRareData);
2630            LocalRegister cachedChildIndex(m_registerAllocator);
2631            m_assembler.load16(Assembler::Address(elementRareData, ElementRareData::childIndexMemoryOffset()), cachedChildIndex);
2632            noCachedChildIndexCases.append(m_assembler.branchTest32(Assembler::Zero, cachedChildIndex));
2633            m_assembler.add32(cachedChildIndex, elementCounter);
2634            noMoreSiblingsCases.append(m_assembler.jump());
2635        }
2636        noCachedChildIndexCases.link(&m_assembler);
2637        m_assembler.add32(Assembler::TrustedImm32(1), elementCounter);
2638
2639        Assembler::Label loopStart = m_assembler.label();
2640        generateWalkToPreviousAdjacentElement(noMoreSiblingsCases, previousSibling);
2641        m_assembler.add32(Assembler::TrustedImm32(1), elementCounter);
2642        m_assembler.jump().linkTo(loopStart, &m_assembler);
2643        noMoreSiblingsCases.link(&m_assembler);
2644    }
2645
2646    // Tree marking when doing style resolution.
2647    if (m_selectorContext != SelectorContext::QuerySelector) {
2648        LocalRegister checkingContext(m_registerAllocator);
2649        Assembler::Jump notResolvingStyle = jumpIfNotResolvingStyle(checkingContext);
2650
2651        m_registerAllocator.deallocateRegister(parentElement);
2652        FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2653        functionCall.setFunctionAddress(Element::setChildrenAffectedByForwardPositionalRules);
2654        functionCall.setOneArgument(parentElement);
2655        functionCall.call();
2656
2657        if (shouldUseRenderStyleFromCheckingContext(fragment)) {
2658            addFlagsToElementStyleFromContext(checkingContext, RenderStyle::NonInheritedFlags::flagIsUnique());
2659
2660            Assembler::RegisterID elementAddress = elementAddressRegister;
2661            FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2662            functionCall.setFunctionAddress(setElementChildIndex);
2663            functionCall.setTwoArguments(elementAddress, elementCounter);
2664            functionCall.call();
2665        } else {
2666            Assembler::RegisterID elementAddress = elementAddressRegister;
2667            FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2668            functionCall.setFunctionAddress(setElementChildIndexAndUpdateStyle);
2669            functionCall.setTwoArguments(elementAddress, elementCounter);
2670            functionCall.call();
2671        }
2672
2673        notResolvingStyle.link(&m_assembler);
2674    }
2675
2676    // Test every the nth-child filter.
2677    for (const auto& slot : validSubsetFilters) {
2678        int a = slot.first;
2679        int b = slot.second;
2680
2681        if (!a)
2682            failureCases.append(m_assembler.branch32(Assembler::NotEqual, Assembler::TrustedImm32(b), elementCounter));
2683        else if (a > 0) {
2684            if (a == 2 && b == 1) {
2685                // This is the common case 2n+1 (or "odd"), we can test for odd values without doing the arithmetic.
2686                failureCases.append(m_assembler.branchTest32(Assembler::Zero, elementCounter, Assembler::TrustedImm32(1)));
2687            } else {
2688                if (b)
2689                    failureCases.append(m_assembler.branchSub32(Assembler::Signed, Assembler::TrustedImm32(b), elementCounter));
2690                moduloIsZero(failureCases, elementCounter, a);
2691            }
2692        } else {
2693            LocalRegister bRegister(m_registerAllocator);
2694            m_assembler.move(Assembler::TrustedImm32(b), bRegister);
2695
2696            failureCases.append(m_assembler.branchSub32(Assembler::Signed, elementCounter, bRegister));
2697            moduloIsZero(failureCases, bRegister, a);
2698        }
2699    }
2700}
2701
2702void SelectorCodeGenerator::generateElementMatchesNotPseudoClass(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
2703{
2704    for (const auto& subFragment : fragment.notFilters) {
2705        Assembler::JumpList localFailureCases;
2706        generateElementMatching(localFailureCases, localFailureCases, subFragment);
2707        // Since this is a not pseudo class filter, reaching here is a failure.
2708        failureCases.append(m_assembler.jump());
2709        localFailureCases.link(&m_assembler);
2710    }
2711}
2712
2713void SelectorCodeGenerator::generateElementMatchesAnyPseudoClass(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
2714{
2715    for (const auto& subFragments : fragment.anyFilters) {
2716        RELEASE_ASSERT(!subFragments.isEmpty());
2717
2718        // Don't handle the last fragment in this loop.
2719        Assembler::JumpList successCases;
2720        for (unsigned i = 0; i < subFragments.size() - 1; ++i) {
2721            Assembler::JumpList localFailureCases;
2722            generateElementMatching(localFailureCases, localFailureCases, subFragments[i]);
2723            successCases.append(m_assembler.jump());
2724            localFailureCases.link(&m_assembler);
2725        }
2726
2727        // At the last fragment, optimize the failure jump to jump to the non-local failure directly.
2728        generateElementMatching(failureCases, failureCases, subFragments.last());
2729        successCases.link(&m_assembler);
2730    }
2731}
2732
2733void SelectorCodeGenerator::generateElementIsRoot(Assembler::JumpList& failureCases)
2734{
2735    LocalRegister document(m_registerAllocator);
2736    getDocument(m_assembler, elementAddressRegister, document);
2737    failureCases.append(m_assembler.branchPtr(Assembler::NotEqual, Assembler::Address(document, Document::documentElementMemoryOffset()), elementAddressRegister));
2738}
2739
2740void SelectorCodeGenerator::generateElementIsTarget(Assembler::JumpList& failureCases)
2741{
2742    LocalRegister document(m_registerAllocator);
2743    getDocument(m_assembler, elementAddressRegister, document);
2744    failureCases.append(m_assembler.branchPtr(Assembler::NotEqual, Assembler::Address(document, Document::cssTargetMemoryOffset()), elementAddressRegister));
2745}
2746
2747}; // namespace SelectorCompiler.
2748}; // namespace WebCore.
2749
2750#endif // ENABLE(CSS_SELECTOR_JIT)
2751