Replace WTF::move with WTFMove
[WebKit-https.git] / Source / WebCore / cssjit / SelectorCompiler.cpp
1 /*
2  * Copyright (C) 2013-2015 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 "HTMLParserIdioms.h"
41 #include "InspectorInstrumentation.h"
42 #include "NodeRenderStyle.h"
43 #include "QualifiedName.h"
44 #include "RegisterAllocator.h"
45 #include "RenderElement.h"
46 #include "RenderStyle.h"
47 #include "SVGElement.h"
48 #include "SelectorCheckerTestFunctions.h"
49 #include "StackAllocator.h"
50 #include "StyledElement.h"
51 #include <JavaScriptCore/GPRInfo.h>
52 #include <JavaScriptCore/LinkBuffer.h>
53 #include <JavaScriptCore/MacroAssembler.h>
54 #include <JavaScriptCore/VM.h>
55 #include <limits>
56 #include <wtf/Deque.h>
57 #include <wtf/HashMap.h>
58 #include <wtf/HashSet.h>
59 #include <wtf/Vector.h>
60 #include <wtf/text/CString.h>
61
62 namespace WebCore {
63 namespace SelectorCompiler {
64
65 #define CSS_SELECTOR_JIT_DEBUGGING 0
66
67 enum class BacktrackingAction {
68     NoBacktracking,
69     JumpToDescendantEntryPoint,
70     JumpToIndirectAdjacentEntryPoint,
71     JumpToDescendantTreeWalkerEntryPoint,
72     JumpToIndirectAdjacentTreeWalkerEntryPoint,
73     JumpToDescendantTail,
74     JumpToDirectAdjacentTail
75 };
76
77 struct BacktrackingFlag {
78     enum {
79         DescendantEntryPoint = 1,
80         IndirectAdjacentEntryPoint = 1 << 1,
81         SaveDescendantBacktrackingStart = 1 << 2,
82         SaveAdjacentBacktrackingStart = 1 << 3,
83         DirectAdjacentTail = 1 << 4,
84         DescendantTail = 1 << 5,
85         InChainWithDescendantTail = 1 << 6,
86         InChainWithAdjacentTail = 1 << 7
87     };
88 };
89
90 enum class FragmentRelation {
91     Rightmost,
92     Descendant,
93     Child,
94     DirectAdjacent,
95     IndirectAdjacent
96 };
97
98 enum class FunctionType {
99     SimpleSelectorChecker,
100     SelectorCheckerWithCheckingContext,
101     CannotMatchAnything,
102     CannotCompile
103 };
104
105 enum class FragmentPositionInRootFragments {
106     Rightmost,
107     NotRightmost
108 };
109
110 enum class VisitedMode {
111     None,
112     Visited
113 };
114
115 enum class AttributeCaseSensitivity {
116     CaseSensitive,
117     // Some values are matched case-insensitively for HTML elements.
118     // That is a legacy behavior decided by HTMLDocument::isCaseSensitiveAttribute().
119     HTMLLegacyCaseInsensitive,
120     CaseInsensitive
121 };
122
123 static AttributeCaseSensitivity attributeSelectorCaseSensitivity(const CSSSelector& selector)
124 {
125     ASSERT(selector.isAttributeSelector());
126
127     // This is by convention, the case is irrelevant for Set.
128     if (selector.match() == CSSSelector::Set)
129         return AttributeCaseSensitivity::CaseSensitive;
130
131     if (selector.attributeValueMatchingIsCaseInsensitive())
132         return AttributeCaseSensitivity::CaseInsensitive;
133     if (HTMLDocument::isCaseSensitiveAttribute(selector.attribute()))
134         return AttributeCaseSensitivity::CaseSensitive;
135     return AttributeCaseSensitivity::HTMLLegacyCaseInsensitive;
136 }
137
138 class AttributeMatchingInfo {
139 public:
140     explicit AttributeMatchingInfo(const CSSSelector& selector)
141         : m_selector(&selector)
142         , m_attributeCaseSensitivity(attributeSelectorCaseSensitivity(selector))
143     {
144         ASSERT(!(m_attributeCaseSensitivity == AttributeCaseSensitivity::CaseInsensitive && !selector.attributeValueMatchingIsCaseInsensitive()));
145         ASSERT(!(selector.match() == CSSSelector::Set && m_attributeCaseSensitivity != AttributeCaseSensitivity::CaseSensitive));
146     }
147
148     AttributeCaseSensitivity attributeCaseSensitivity() const { return m_attributeCaseSensitivity; }
149     const CSSSelector& selector() const { return *m_selector; }
150
151 private:
152     const CSSSelector* m_selector;
153     AttributeCaseSensitivity m_attributeCaseSensitivity;
154 };
155
156 static const unsigned invalidHeight = std::numeric_limits<unsigned>::max();
157 static const unsigned invalidWidth = std::numeric_limits<unsigned>::max();
158
159 struct SelectorFragment;
160 class SelectorFragmentList;
161
162 class SelectorList : public Vector<SelectorFragmentList> {
163 public:
164     unsigned registerRequirements = std::numeric_limits<unsigned>::max();
165     unsigned stackRequirements = std::numeric_limits<unsigned>::max();
166     bool clobberElementAddressRegister = true;
167 };
168
169 struct NthChildOfSelectorInfo {
170     int a;
171     int b;
172     SelectorList selectorList;
173 };
174
175 struct SelectorFragment {
176     FragmentRelation relationToLeftFragment;
177     FragmentRelation relationToRightFragment;
178     FragmentPositionInRootFragments positionInRootFragments;
179
180     BacktrackingAction traversalBacktrackingAction = BacktrackingAction::NoBacktracking;
181     BacktrackingAction matchingTagNameBacktrackingAction = BacktrackingAction::NoBacktracking;
182     BacktrackingAction matchingPostTagNameBacktrackingAction = BacktrackingAction::NoBacktracking;
183     unsigned char backtrackingFlags = 0;
184     unsigned tagNameMatchedBacktrackingStartHeightFromDescendant = invalidHeight;
185     unsigned tagNameNotMatchedBacktrackingStartHeightFromDescendant = invalidHeight;
186     unsigned heightFromDescendant = 0;
187     unsigned tagNameMatchedBacktrackingStartWidthFromIndirectAdjacent = invalidWidth;
188     unsigned tagNameNotMatchedBacktrackingStartWidthFromIndirectAdjacent = invalidWidth;
189     unsigned widthFromIndirectAdjacent = 0;
190
191     FunctionType appendUnoptimizedPseudoClassWithContext(bool (*matcher)(const SelectorChecker::CheckingContext&));
192
193     // FIXME: the large stack allocation caused by the inline capacity causes memory inefficiency. We should dump
194     // the min/max/average of the vectors and pick better inline capacity.
195     const CSSSelector* tagNameSelector = nullptr;
196     const AtomicString* id = nullptr;
197     Vector<const Vector<AtomicString>*> languageArgumentsList;
198     Vector<const AtomicStringImpl*, 8> classNames;
199     HashSet<unsigned> pseudoClasses;
200     Vector<JSC::FunctionPtr, 4> unoptimizedPseudoClasses;
201     Vector<JSC::FunctionPtr, 4> unoptimizedPseudoClassesWithContext;
202     Vector<AttributeMatchingInfo, 4> attributes;
203     Vector<std::pair<int, int>, 2> nthChildFilters;
204     Vector<NthChildOfSelectorInfo> nthChildOfFilters;
205     Vector<std::pair<int, int>, 2> nthLastChildFilters;
206     Vector<NthChildOfSelectorInfo> nthLastChildOfFilters;
207     SelectorList notFilters;
208     Vector<SelectorList> matchesFilters;
209     Vector<Vector<SelectorFragment>> anyFilters;
210     const CSSSelector* pseudoElementSelector = nullptr;
211
212     // For quirks mode, follow this: http://quirks.spec.whatwg.org/#the-:active-and-:hover-quirk
213     // 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.
214     //
215     //    selector uses the ':active' or ':hover' pseudo-classes.
216     //    selector does not use a type selector.
217     //    selector does not use an attribute selector.
218     //    selector does not use an ID selector.
219     //    selector does not use a class selector.
220     //    selector does not use a pseudo-class selector other than ':active' and ':hover'.
221     //    selector does not use a pseudo-element selector.
222     //    selector is not part of an argument to a functional pseudo-class or pseudo-element.
223     bool onlyMatchesLinksInQuirksMode = true;
224 };
225
226 class SelectorFragmentList : public Vector<SelectorFragment, 4> {
227 public:
228     unsigned registerRequirements = std::numeric_limits<unsigned>::max();
229     unsigned stackRequirements = std::numeric_limits<unsigned>::max();
230     unsigned staticSpecificity = 0;
231     bool clobberElementAddressRegister = true;
232 };
233
234 struct TagNamePattern {
235     const CSSSelector* tagNameSelector = nullptr;
236     bool inverted = false;
237 };
238
239 typedef JSC::MacroAssembler Assembler;
240 typedef Vector<TagNamePattern, 32> TagNameList;
241
242 struct BacktrackingLevel {
243     Assembler::Label descendantEntryPoint;
244     Assembler::Label indirectAdjacentEntryPoint;
245     Assembler::Label descendantTreeWalkerBacktrackingPoint;
246     Assembler::Label indirectAdjacentTreeWalkerBacktrackingPoint;
247
248     StackAllocator::StackReference descendantBacktrackingStart;
249     Assembler::JumpList descendantBacktrackingFailureCases;
250     StackAllocator::StackReference adjacentBacktrackingStart;
251     Assembler::JumpList adjacentBacktrackingFailureCases;
252 };
253
254 class SelectorCodeGenerator {
255 public:
256     SelectorCodeGenerator(const CSSSelector*, SelectorContext);
257     SelectorCompilationStatus compile(JSC::VM*, JSC::MacroAssemblerCodeRef&);
258
259 private:
260     static const Assembler::RegisterID returnRegister;
261     static const Assembler::RegisterID elementAddressRegister;
262     static const Assembler::RegisterID checkingContextRegister;
263     static const Assembler::RegisterID callFrameRegister;
264
265     void generateSelectorChecker();
266     void generateSelectorCheckerExcludingPseudoElements(Assembler::JumpList& failureCases, const SelectorFragmentList&);
267     void generateElementMatchesSelectorList(Assembler::JumpList& failureCases, Assembler::RegisterID elementToMatch, const SelectorList&);
268
269     // Element relations tree walker.
270     void generateRightmostTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment&);
271     void generateWalkToParentNode(Assembler::RegisterID targetRegister);
272     void generateWalkToParentElement(Assembler::JumpList& failureCases, Assembler::RegisterID targetRegister);
273     void generateParentElementTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment&);
274     void generateAncestorTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment&);
275
276     void generateWalkToNextAdjacentElement(Assembler::JumpList& failureCases, Assembler::RegisterID);
277     void generateWalkToPreviousAdjacentElement(Assembler::JumpList& failureCases, Assembler::RegisterID);
278     void generateWalkToPreviousAdjacent(Assembler::JumpList& failureCases, const SelectorFragment&);
279     void generateDirectAdjacentTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment&);
280     void generateIndirectAdjacentTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment&);
281
282     void linkFailures(Assembler::JumpList& globalFailureCases, BacktrackingAction, Assembler::JumpList& localFailureCases);
283     void generateAdjacentBacktrackingTail();
284     void generateDescendantBacktrackingTail();
285     void generateBacktrackingTailsIfNeeded(Assembler::JumpList& failureCases, const SelectorFragment&);
286
287     // Element properties matchers.
288     void generateElementMatching(Assembler::JumpList& matchingTagNameFailureCases, Assembler::JumpList& matchingPostTagNameFailureCases, const SelectorFragment&);
289     void generateElementDataMatching(Assembler::JumpList& failureCases, const SelectorFragment&);
290     void generateElementLinkMatching(Assembler::JumpList& failureCases, const SelectorFragment&);
291     void generateElementFunctionCallTest(Assembler::JumpList& failureCases, JSC::FunctionPtr);
292     void generateContextFunctionCallTest(Assembler::JumpList& failureCases, JSC::FunctionPtr);
293     void generateElementIsActive(Assembler::JumpList& failureCases, const SelectorFragment&);
294     void generateElementIsEmpty(Assembler::JumpList& failureCases, const SelectorFragment&);
295     void generateElementIsFirstChild(Assembler::JumpList& failureCases, const SelectorFragment&);
296     void generateElementIsHovered(Assembler::JumpList& failureCases, const SelectorFragment&);
297     void generateElementIsInLanguage(Assembler::JumpList& failureCases, const SelectorFragment&);
298     void generateElementIsInLanguage(Assembler::JumpList& failureCases, const Vector<AtomicString>*);
299     void generateElementIsLastChild(Assembler::JumpList& failureCases, const SelectorFragment&);
300     void generateElementIsOnlyChild(Assembler::JumpList& failureCases, const SelectorFragment&);
301     void generateElementHasPlaceholderShown(Assembler::JumpList& failureCases, const SelectorFragment&);
302     void generateSynchronizeStyleAttribute(Assembler::RegisterID elementDataArraySizeAndFlags);
303     void generateSynchronizeAllAnimatedSVGAttribute(Assembler::RegisterID elementDataArraySizeAndFlags);
304     void generateElementAttributesMatching(Assembler::JumpList& failureCases, const LocalRegister& elementDataAddress, const SelectorFragment&);
305     void generateElementAttributeMatching(Assembler::JumpList& failureCases, Assembler::RegisterID currentAttributeAddress, Assembler::RegisterID decIndexRegister, const AttributeMatchingInfo& attributeInfo);
306     void generateElementAttributeValueMatching(Assembler::JumpList& failureCases, Assembler::RegisterID currentAttributeAddress, const AttributeMatchingInfo& attributeInfo);
307     void generateElementAttributeValueExactMatching(Assembler::JumpList& failureCases, Assembler::RegisterID currentAttributeAddress, const AtomicString& expectedValue, AttributeCaseSensitivity valueCaseSensitivity);
308     void generateElementAttributeFunctionCallValueMatching(Assembler::JumpList& failureCases, Assembler::RegisterID currentAttributeAddress, const AtomicString& expectedValue, AttributeCaseSensitivity valueCaseSensitivity, JSC::FunctionPtr caseSensitiveTest, JSC::FunctionPtr caseInsensitiveTest);
309     void generateElementHasTagName(Assembler::JumpList& failureCases, const CSSSelector& tagMatchingSelector);
310     void generateElementHasId(Assembler::JumpList& failureCases, const LocalRegister& elementDataAddress, const AtomicString& idToMatch);
311     void generateElementHasClasses(Assembler::JumpList& failureCases, const LocalRegister& elementDataAddress, const Vector<const AtomicStringImpl*, 8>& classNames);
312     void generateElementIsLink(Assembler::JumpList& failureCases);
313     void generateElementIsNthChild(Assembler::JumpList& failureCases, const SelectorFragment&);
314     void generateElementIsNthChildOf(Assembler::JumpList& failureCases, const SelectorFragment&);
315     void generateElementIsNthLastChild(Assembler::JumpList& failureCases, const SelectorFragment&);
316     void generateElementIsNthLastChildOf(Assembler::JumpList& failureCases, const SelectorFragment&);
317     void generateElementMatchesNotPseudoClass(Assembler::JumpList& failureCases, const SelectorFragment&);
318     void generateElementMatchesAnyPseudoClass(Assembler::JumpList& failureCases, const SelectorFragment&);
319     void generateElementMatchesMatchesPseudoClass(Assembler::JumpList& failureCases, const SelectorFragment&);
320     void generateElementHasPseudoElement(Assembler::JumpList& failureCases, const SelectorFragment&);
321     void generateElementIsRoot(Assembler::JumpList& failureCases);
322     void generateElementIsScopeRoot(Assembler::JumpList& failureCases);
323     void generateElementIsTarget(Assembler::JumpList& failureCases);
324
325     // Helpers.
326     void addFlagsToElementStyleFromContext(Assembler::RegisterID checkingContext, int64_t);
327     Assembler::Jump branchOnResolvingModeWithCheckingContext(Assembler::RelationalCondition, SelectorChecker::Mode, Assembler::RegisterID checkingContext);
328     Assembler::Jump branchOnResolvingMode(Assembler::RelationalCondition, SelectorChecker::Mode, Assembler::RegisterID checkingContext);
329     void generateElementIsFirstLink(Assembler::JumpList& failureCases, Assembler::RegisterID element);
330     void generateStoreLastVisitedElement(Assembler::RegisterID element);
331     void generateMarkPseudoStyleForPseudoElement(Assembler::JumpList& failureCases, const SelectorFragment&);
332     void generateNthFilterTest(Assembler::JumpList& failureCases, Assembler::RegisterID counter, int a, int b);
333     void generateRequestedPseudoElementEqualsToSelectorPseudoElement(Assembler::JumpList& failureCases, const SelectorFragment&, Assembler::RegisterID checkingContext);
334     void generateSpecialFailureInQuirksModeForActiveAndHoverIfNeeded(Assembler::JumpList& failureCases, const SelectorFragment&);
335     void markElementIfResolvingStyle(Assembler::RegisterID, int32_t);
336     Assembler::JumpList jumpIfNoPreviousAdjacentElement();
337     Assembler::JumpList jumpIfNoNextAdjacentElement();
338     Assembler::Jump jumpIfNotResolvingStyle(Assembler::RegisterID checkingContextRegister);
339     void loadCheckingContext(Assembler::RegisterID checkingContext);
340     Assembler::Jump modulo(JSC::MacroAssembler::ResultCondition, Assembler::RegisterID inputDividend, int divisor);
341     void moduloIsZero(Assembler::JumpList& failureCases, Assembler::RegisterID inputDividend, int divisor);
342
343     void pushMacroAssemblerRegisters();
344     void popMacroAssemblerRegisters(StackAllocator&);
345     bool generatePrologue();
346     void generateEpilogue(StackAllocator&);
347     StackAllocator::StackReferenceVector m_macroAssemblerRegistersStackReferences;
348     StackAllocator::StackReferenceVector m_prologueStackReferences;
349
350     Assembler m_assembler;
351     RegisterAllocator m_registerAllocator;
352     StackAllocator m_stackAllocator;
353     Vector<std::pair<Assembler::Call, JSC::FunctionPtr>, 32> m_functionCalls;
354
355     SelectorContext m_selectorContext;
356     FunctionType m_functionType;
357     SelectorFragmentList m_selectorFragments;
358     VisitedMode m_visitedMode;
359
360     StackAllocator::StackReference m_checkingContextStackReference;
361
362     bool m_descendantBacktrackingStartInUse;
363     Assembler::RegisterID m_descendantBacktrackingStart;
364     StackAllocator::StackReferenceVector m_backtrackingStack;
365     Deque<BacktrackingLevel, 32> m_backtrackingLevels;
366     StackAllocator::StackReference m_lastVisitedElement;
367     StackAllocator::StackReference m_startElement;
368
369 #if CSS_SELECTOR_JIT_DEBUGGING
370     const CSSSelector* m_originalSelector;
371 #endif
372 };
373
374 const Assembler::RegisterID SelectorCodeGenerator::returnRegister = JSC::GPRInfo::returnValueGPR;
375 const Assembler::RegisterID SelectorCodeGenerator::elementAddressRegister = JSC::GPRInfo::argumentGPR0;
376 const Assembler::RegisterID SelectorCodeGenerator::checkingContextRegister = JSC::GPRInfo::argumentGPR1;
377 const Assembler::RegisterID SelectorCodeGenerator::callFrameRegister = JSC::GPRInfo::callFrameRegister;
378
379 enum class FragmentsLevel {
380     Root = 0,
381     InFunctionalPseudoType = 1
382 };
383
384 enum class PseudoElementMatchingBehavior { CanMatch, NeverMatch };
385
386 static FunctionType constructFragments(const CSSSelector* rootSelector, SelectorContext, SelectorFragmentList& selectorFragments, FragmentsLevel, FragmentPositionInRootFragments, bool visitedMatchEnabled, VisitedMode&, PseudoElementMatchingBehavior);
387
388 static void computeBacktrackingInformation(SelectorFragmentList& selectorFragments, unsigned level = 0);
389
390 SelectorCompilationStatus compileSelector(const CSSSelector* lastSelector, JSC::VM* vm, SelectorContext selectorContext, JSC::MacroAssemblerCodeRef& codeRef)
391 {
392     if (!vm->canUseJIT())
393         return SelectorCompilationStatus::CannotCompile;
394     SelectorCodeGenerator codeGenerator(lastSelector, selectorContext);
395     return codeGenerator.compile(vm, codeRef);
396 }
397
398 static inline FragmentRelation fragmentRelationForSelectorRelation(CSSSelector::Relation relation)
399 {
400     switch (relation) {
401     case CSSSelector::Descendant:
402         return FragmentRelation::Descendant;
403     case CSSSelector::Child:
404         return FragmentRelation::Child;
405     case CSSSelector::DirectAdjacent:
406         return FragmentRelation::DirectAdjacent;
407     case CSSSelector::IndirectAdjacent:
408         return FragmentRelation::IndirectAdjacent;
409     case CSSSelector::SubSelector:
410     case CSSSelector::ShadowDescendant:
411         ASSERT_NOT_REACHED();
412     }
413     ASSERT_NOT_REACHED();
414     return FragmentRelation::Descendant;
415 }
416
417 static inline FunctionType mostRestrictiveFunctionType(FunctionType a, FunctionType b)
418 {
419     return std::max(a, b);
420 }
421
422 static inline bool fragmentMatchesTheRightmostElement(SelectorContext selectorContext, const SelectorFragment& fragment)
423 {
424     // Return true if the position of this fragment is Rightmost in the root fragments.
425     // In this case, we should use the RenderStyle stored in the CheckingContext.
426     ASSERT_UNUSED(selectorContext, selectorContext != SelectorContext::QuerySelector);
427     return fragment.relationToRightFragment == FragmentRelation::Rightmost && fragment.positionInRootFragments == FragmentPositionInRootFragments::Rightmost;
428 }
429
430 FunctionType SelectorFragment::appendUnoptimizedPseudoClassWithContext(bool (*matcher)(const SelectorChecker::CheckingContext&))
431 {
432     unoptimizedPseudoClassesWithContext.append(JSC::FunctionPtr(matcher));
433     return FunctionType::SelectorCheckerWithCheckingContext;
434 }
435
436 static inline FunctionType addScrollbarPseudoClassType(const CSSSelector&, SelectorFragment&)
437 {
438     // FIXME: scrollbar pseudoclass interaction with :not doesn't behave correctly.
439     // Compile them when they are fixed and tested.
440     // https://bugs.webkit.org/show_bug.cgi?id=146221
441     return FunctionType::CannotCompile;
442 }
443
444 // Handle the forward :nth-child() and backward :nth-last-child().
445 static FunctionType addNthChildType(const CSSSelector& selector, SelectorContext selectorContext, FragmentPositionInRootFragments positionInRootFragments, CSSSelector::PseudoClassType firstMatchAlternative, bool visitedMatchEnabled, Vector<std::pair<int, int>, 2>& simpleCases, Vector<NthChildOfSelectorInfo>& filteredCases, HashSet<unsigned>& pseudoClasses, unsigned& internalSpecificity)
446 {
447     if (!selector.parseNth())
448         return FunctionType::CannotMatchAnything;
449
450     int a = selector.nthA();
451     int b = selector.nthB();
452
453     // The element count is always positive.
454     if (a <= 0 && b < 1)
455         return FunctionType::CannotMatchAnything;
456
457     if (const CSSSelectorList* selectorList = selector.selectorList()) {
458         NthChildOfSelectorInfo nthChildOfSelectorInfo;
459         nthChildOfSelectorInfo.a = a;
460         nthChildOfSelectorInfo.b = b;
461
462         FunctionType globalFunctionType = FunctionType::SimpleSelectorChecker;
463         if (selectorContext != SelectorContext::QuerySelector)
464             globalFunctionType = FunctionType::SelectorCheckerWithCheckingContext;
465
466         unsigned firstFragmentListSpecificity = 0;
467         bool firstFragmentListSpecificitySet = false;
468
469         SelectorFragmentList* selectorFragments = nullptr;
470         for (const CSSSelector* subselector = selectorList->first(); subselector; subselector = CSSSelectorList::next(subselector)) {
471             if (!selectorFragments) {
472                 nthChildOfSelectorInfo.selectorList.append(SelectorFragmentList());
473                 selectorFragments = &nthChildOfSelectorInfo.selectorList.last();
474             }
475
476             VisitedMode ignoreVisitedMode = VisitedMode::None;
477             FunctionType functionType = constructFragments(subselector, selectorContext, *selectorFragments, FragmentsLevel::InFunctionalPseudoType, positionInRootFragments, visitedMatchEnabled, ignoreVisitedMode, PseudoElementMatchingBehavior::NeverMatch);
478             ASSERT_WITH_MESSAGE(ignoreVisitedMode == VisitedMode::None, ":visited is disabled in the functional pseudo classes");
479             switch (functionType) {
480             case FunctionType::SimpleSelectorChecker:
481             case FunctionType::SelectorCheckerWithCheckingContext:
482                 break;
483             case FunctionType::CannotMatchAnything:
484                 continue;
485             case FunctionType::CannotCompile:
486                 return FunctionType::CannotCompile;
487             }
488
489             if (firstFragmentListSpecificitySet) {
490                 // The CSS JIT does not handle dynamic specificity yet.
491                 if (selectorContext == SelectorContext::RuleCollector && selectorFragments->staticSpecificity != firstFragmentListSpecificity)
492                     return FunctionType::CannotCompile;
493             } else {
494                 firstFragmentListSpecificitySet = true;
495                 firstFragmentListSpecificity = selectorFragments->staticSpecificity;
496             }
497
498             globalFunctionType = mostRestrictiveFunctionType(globalFunctionType, functionType);
499             selectorFragments = nullptr;
500         }
501
502         // If there is still a SelectorFragmentList open, the last Fragment(s) cannot match anything,
503         // we have one FragmentList too many in our selector list.
504         if (selectorFragments)
505             nthChildOfSelectorInfo.selectorList.removeLast();
506
507         if (nthChildOfSelectorInfo.selectorList.isEmpty())
508             return FunctionType::CannotMatchAnything;
509
510         internalSpecificity = firstFragmentListSpecificity;
511         filteredCases.append(nthChildOfSelectorInfo);
512         return globalFunctionType;
513     }
514
515     if (b == 1 && a <= 0)
516         pseudoClasses.add(firstMatchAlternative);
517     else
518         simpleCases.append(std::pair<int, int>(a, b));
519     if (selectorContext == SelectorContext::QuerySelector)
520         return FunctionType::SimpleSelectorChecker;
521     return FunctionType::SelectorCheckerWithCheckingContext;
522 }
523
524 static inline FunctionType addPseudoClassType(const CSSSelector& selector, SelectorFragment& fragment, unsigned& internalSpecificity, SelectorContext selectorContext, FragmentsLevel fragmentLevel, FragmentPositionInRootFragments positionInRootFragments, bool visitedMatchEnabled, VisitedMode& visitedMode, PseudoElementMatchingBehavior pseudoElementMatchingBehavior)
525 {
526     CSSSelector::PseudoClassType type = selector.pseudoClassType();
527     switch (type) {
528     // Unoptimized pseudo selector. They are just function call to a simple testing function.
529     case CSSSelector::PseudoClassAutofill:
530         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isAutofilled));
531         return FunctionType::SimpleSelectorChecker;
532     case CSSSelector::PseudoClassChecked:
533         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isChecked));
534         return FunctionType::SimpleSelectorChecker;
535     case CSSSelector::PseudoClassDefault:
536         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isDefaultButtonForForm));
537         return FunctionType::SimpleSelectorChecker;
538     case CSSSelector::PseudoClassDisabled:
539         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isDisabled));
540         return FunctionType::SimpleSelectorChecker;
541     case CSSSelector::PseudoClassEnabled:
542         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isEnabled));
543         return FunctionType::SimpleSelectorChecker;
544     case CSSSelector::PseudoClassFocus:
545         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(SelectorChecker::matchesFocusPseudoClass));
546         return FunctionType::SimpleSelectorChecker;
547     case CSSSelector::PseudoClassFullPageMedia:
548         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isMediaDocument));
549         return FunctionType::SimpleSelectorChecker;
550     case CSSSelector::PseudoClassInRange:
551         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isInRange));
552         return FunctionType::SimpleSelectorChecker;
553     case CSSSelector::PseudoClassIndeterminate:
554         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(shouldAppearIndeterminate));
555         return FunctionType::SimpleSelectorChecker;
556     case CSSSelector::PseudoClassInvalid:
557         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isInvalid));
558         return FunctionType::SimpleSelectorChecker;
559     case CSSSelector::PseudoClassOptional:
560         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isOptionalFormControl));
561         return FunctionType::SimpleSelectorChecker;
562     case CSSSelector::PseudoClassOutOfRange:
563         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isOutOfRange));
564         return FunctionType::SimpleSelectorChecker;
565     case CSSSelector::PseudoClassReadOnly:
566         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesReadOnlyPseudoClass));
567         return FunctionType::SimpleSelectorChecker;
568     case CSSSelector::PseudoClassReadWrite:
569         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesReadWritePseudoClass));
570         return FunctionType::SimpleSelectorChecker;
571     case CSSSelector::PseudoClassRequired:
572         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isRequiredFormControl));
573         return FunctionType::SimpleSelectorChecker;
574     case CSSSelector::PseudoClassValid:
575         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isValid));
576         return FunctionType::SimpleSelectorChecker;
577     case CSSSelector::PseudoClassWindowInactive:
578         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isWindowInactive));
579         return FunctionType::SimpleSelectorChecker;
580
581 #if ENABLE(FULLSCREEN_API)
582     case CSSSelector::PseudoClassFullScreen:
583         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesFullScreenPseudoClass));
584         return FunctionType::SimpleSelectorChecker;
585     case CSSSelector::PseudoClassFullScreenDocument:
586         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesFullScreenDocumentPseudoClass));
587         return FunctionType::SimpleSelectorChecker;
588     case CSSSelector::PseudoClassFullScreenAncestor:
589         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesFullScreenAncestorPseudoClass));
590         return FunctionType::SimpleSelectorChecker;
591     case CSSSelector::PseudoClassAnimatingFullScreenTransition:
592         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesFullScreenAnimatingFullScreenTransitionPseudoClass));
593         return FunctionType::SimpleSelectorChecker;
594 #endif
595 #if ENABLE(VIDEO_TRACK)
596     case CSSSelector::PseudoClassFuture:
597         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesFutureCuePseudoClass));
598         return FunctionType::SimpleSelectorChecker;
599     case CSSSelector::PseudoClassPast:
600         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesPastCuePseudoClass));
601         return FunctionType::SimpleSelectorChecker;
602 #endif
603
604     // These pseudo-classes only have meaning with scrollbars.
605     case CSSSelector::PseudoClassHorizontal:
606     case CSSSelector::PseudoClassVertical:
607     case CSSSelector::PseudoClassDecrement:
608     case CSSSelector::PseudoClassIncrement:
609     case CSSSelector::PseudoClassStart:
610     case CSSSelector::PseudoClassEnd:
611     case CSSSelector::PseudoClassDoubleButton:
612     case CSSSelector::PseudoClassSingleButton:
613     case CSSSelector::PseudoClassNoButton:
614     case CSSSelector::PseudoClassCornerPresent:
615         return FunctionType::CannotMatchAnything;
616
617     // FIXME: Compile these pseudoclasses, too!
618     case CSSSelector::PseudoClassFirstOfType:
619     case CSSSelector::PseudoClassLastOfType:
620     case CSSSelector::PseudoClassOnlyOfType:
621     case CSSSelector::PseudoClassNthOfType:
622     case CSSSelector::PseudoClassNthLastOfType:
623     case CSSSelector::PseudoClassDrag:
624 #if ENABLE(CSS_SELECTORS_LEVEL4)
625     case CSSSelector::PseudoClassDir:
626     case CSSSelector::PseudoClassRole:
627 #endif
628         return FunctionType::CannotCompile;
629
630     // Optimized pseudo selectors.
631     case CSSSelector::PseudoClassAnyLink:
632     case CSSSelector::PseudoClassLink:
633     case CSSSelector::PseudoClassRoot:
634     case CSSSelector::PseudoClassTarget:
635         fragment.pseudoClasses.add(type);
636         return FunctionType::SimpleSelectorChecker;
637     case CSSSelector::PseudoClassAnyLinkDeprecated:
638         fragment.pseudoClasses.add(CSSSelector::PseudoClassAnyLink);
639         return FunctionType::SimpleSelectorChecker;
640
641     case CSSSelector::PseudoClassVisited:
642         // Determine this :visited cannot match anything statically.
643         if (!visitedMatchEnabled)
644             return FunctionType::CannotMatchAnything;
645
646         // Inside functional pseudo class except for :not, :visited never matches.
647         // And in the case inside :not, returning CannotMatchAnything indicates that :not(:visited) can match over anything.
648         if (fragmentLevel == FragmentsLevel::InFunctionalPseudoType)
649             return FunctionType::CannotMatchAnything;
650
651         fragment.pseudoClasses.add(type);
652         visitedMode = VisitedMode::Visited;
653         return FunctionType::SimpleSelectorChecker;
654
655     case CSSSelector::PseudoClassScope:
656         if (selectorContext != SelectorContext::QuerySelector) {
657             fragment.pseudoClasses.add(CSSSelector::PseudoClassRoot);
658             return FunctionType::SimpleSelectorChecker;
659         }
660         fragment.pseudoClasses.add(CSSSelector::PseudoClassScope);
661         return FunctionType::SelectorCheckerWithCheckingContext;
662
663     case CSSSelector::PseudoClassActive:
664     case CSSSelector::PseudoClassEmpty:
665     case CSSSelector::PseudoClassFirstChild:
666     case CSSSelector::PseudoClassHover:
667     case CSSSelector::PseudoClassLastChild:
668     case CSSSelector::PseudoClassOnlyChild:
669     case CSSSelector::PseudoClassPlaceholderShown:
670         fragment.pseudoClasses.add(type);
671         if (selectorContext == SelectorContext::QuerySelector)
672             return FunctionType::SimpleSelectorChecker;
673         return FunctionType::SelectorCheckerWithCheckingContext;
674
675     case CSSSelector::PseudoClassNthChild:
676         return addNthChildType(selector, selectorContext, positionInRootFragments, CSSSelector::PseudoClassFirstChild, visitedMatchEnabled, fragment.nthChildFilters, fragment.nthChildOfFilters, fragment.pseudoClasses, internalSpecificity);
677
678     case CSSSelector::PseudoClassNthLastChild:
679         return addNthChildType(selector, selectorContext, positionInRootFragments, CSSSelector::PseudoClassLastChild, visitedMatchEnabled, fragment.nthLastChildFilters, fragment.nthLastChildOfFilters, fragment.pseudoClasses, internalSpecificity);
680
681     case CSSSelector::PseudoClassNot:
682         {
683             const CSSSelectorList* selectorList = selector.selectorList();
684
685             ASSERT_WITH_MESSAGE(selectorList, "The CSS Parser should never produce valid :not() CSSSelector with an empty selectorList.");
686             if (!selectorList)
687                 return FunctionType::CannotMatchAnything;
688
689             FunctionType functionType = FunctionType::SimpleSelectorChecker;
690             SelectorFragmentList* selectorFragments = nullptr;
691             for (const CSSSelector* subselector = selectorList->first(); subselector; subselector = CSSSelectorList::next(subselector)) {
692                 if (!selectorFragments) {
693                     fragment.notFilters.append(SelectorFragmentList());
694                     selectorFragments = &fragment.notFilters.last();
695                 }
696
697                 VisitedMode ignoreVisitedMode = VisitedMode::None;
698                 FunctionType localFunctionType = constructFragments(subselector, selectorContext, *selectorFragments, FragmentsLevel::InFunctionalPseudoType, positionInRootFragments, visitedMatchEnabled, ignoreVisitedMode, PseudoElementMatchingBehavior::NeverMatch);
699                 ASSERT_WITH_MESSAGE(ignoreVisitedMode == VisitedMode::None, ":visited is disabled in the functional pseudo classes");
700
701                 // Since this is not pseudo class filter, CannotMatchAnything implies this filter always passes.
702                 if (localFunctionType == FunctionType::CannotMatchAnything)
703                     continue;
704
705                 if (localFunctionType == FunctionType::CannotCompile)
706                     return FunctionType::CannotCompile;
707
708                 functionType = mostRestrictiveFunctionType(functionType, localFunctionType);
709                 selectorFragments = nullptr;
710             }
711
712             // If there is still a SelectorFragmentList open, the last Fragment(s) cannot match anything,
713             // we have one FragmentList too many in our selector list.
714             if (selectorFragments)
715                 fragment.notFilters.removeLast();
716
717             return functionType;
718         }
719
720     case CSSSelector::PseudoClassAny:
721         {
722             Vector<SelectorFragment, 32> anyFragments;
723             FunctionType functionType = FunctionType::SimpleSelectorChecker;
724             for (const CSSSelector* rootSelector = selector.selectorList()->first(); rootSelector; rootSelector = CSSSelectorList::next(rootSelector)) {
725                 SelectorFragmentList fragmentList;
726                 VisitedMode ignoreVisitedMode = VisitedMode::None;
727                 FunctionType subFunctionType = constructFragments(rootSelector, selectorContext, fragmentList, FragmentsLevel::InFunctionalPseudoType, positionInRootFragments, visitedMatchEnabled, ignoreVisitedMode, PseudoElementMatchingBehavior::NeverMatch);
728                 ASSERT_WITH_MESSAGE(ignoreVisitedMode == VisitedMode::None, ":visited is disabled in the functional pseudo classes");
729
730                 // Since this fragment always unmatch against the element, don't insert it to anyFragments.
731                 if (subFunctionType == FunctionType::CannotMatchAnything)
732                     continue;
733
734                 if (subFunctionType == FunctionType::CannotCompile)
735                     return FunctionType::CannotCompile;
736
737                 // :any() may not contain complex selectors which have combinators.
738                 ASSERT(fragmentList.size() == 1);
739                 if (fragmentList.size() != 1)
740                     return FunctionType::CannotCompile;
741
742                 const SelectorFragment& subFragment = fragmentList.first();
743                 anyFragments.append(subFragment);
744                 functionType = mostRestrictiveFunctionType(functionType, subFunctionType);
745             }
746
747             // Since all fragments in :any() cannot match anything, this :any() filter cannot match anything.
748             if (anyFragments.isEmpty())
749                 return FunctionType::CannotMatchAnything;
750
751             ASSERT(!anyFragments.isEmpty());
752             fragment.anyFilters.append(anyFragments);
753
754             return functionType;
755         }
756
757     case CSSSelector::PseudoClassLang:
758         {
759             const Vector<AtomicString>* selectorLangArgumentList = selector.langArgumentList();
760             ASSERT(selectorLangArgumentList && !selectorLangArgumentList->isEmpty());
761             fragment.languageArgumentsList.append(selectorLangArgumentList);
762             return FunctionType::SimpleSelectorChecker;
763         }
764
765     case CSSSelector::PseudoClassMatches:
766         {
767             SelectorList matchesList;
768             const CSSSelectorList* selectorList = selector.selectorList();
769             FunctionType functionType = FunctionType::SimpleSelectorChecker;
770             unsigned firstFragmentListSpecificity = 0;
771             bool firstFragmentListSpecificitySet = false;
772             SelectorFragmentList* selectorFragments = nullptr;
773             for (const CSSSelector* subselector = selectorList->first(); subselector; subselector = CSSSelectorList::next(subselector)) {
774                 if (!selectorFragments) {
775                     matchesList.append(SelectorFragmentList());
776                     selectorFragments = &matchesList.last();
777                 }
778
779                 VisitedMode ignoreVisitedMode = VisitedMode::None;
780                 FunctionType localFunctionType = constructFragments(subselector, selectorContext, *selectorFragments, FragmentsLevel::InFunctionalPseudoType, positionInRootFragments, visitedMatchEnabled, ignoreVisitedMode, pseudoElementMatchingBehavior);
781                 ASSERT_WITH_MESSAGE(ignoreVisitedMode == VisitedMode::None, ":visited is disabled in the functional pseudo classes");
782
783                 // Since this fragment never matches against the element, don't insert it to matchesList.
784                 if (localFunctionType == FunctionType::CannotMatchAnything)
785                     continue;
786
787                 if (localFunctionType == FunctionType::CannotCompile)
788                     return FunctionType::CannotCompile;
789
790                 // FIXME: Currently pseudo elements inside :matches are supported in non-JIT code.
791                 if (selectorFragments->first().pseudoElementSelector)
792                     return FunctionType::CannotCompile;
793
794                 if (firstFragmentListSpecificitySet) {
795                     // The CSS JIT does not handle dynamic specificity yet.
796                     if (selectorContext == SelectorContext::RuleCollector && selectorFragments->staticSpecificity != firstFragmentListSpecificity)
797                         return FunctionType::CannotCompile;
798                 } else {
799                     firstFragmentListSpecificitySet = true;
800                     firstFragmentListSpecificity = selectorFragments->staticSpecificity;
801                 }
802
803                 functionType = mostRestrictiveFunctionType(functionType, localFunctionType);
804                 selectorFragments = nullptr;
805             }
806
807             // If there is still a SelectorFragmentList open, the last Fragment(s) cannot match anything,
808             // we have one FragmentList too many in our selector list.
809             if (selectorFragments)
810                 matchesList.removeLast();
811
812             // Since all selector list in :matches() cannot match anything, the whole :matches() filter cannot match anything.
813             if (matchesList.isEmpty())
814                 return FunctionType::CannotMatchAnything;
815
816             internalSpecificity = firstFragmentListSpecificity;
817
818             fragment.matchesFilters.append(matchesList);
819
820             return functionType;
821         }
822 #if ENABLE(SHADOW_DOM)
823     case CSSSelector::PseudoClassHost:
824         // :host matches based on context. Cases that reach selector checker don't match.
825         return FunctionType::CannotMatchAnything;
826 #endif
827     case CSSSelector::PseudoClassUnknown:
828         ASSERT_NOT_REACHED();
829         return FunctionType::CannotMatchAnything;
830     }
831
832     ASSERT_NOT_REACHED();
833     return FunctionType::CannotCompile;
834 }
835
836 inline SelectorCodeGenerator::SelectorCodeGenerator(const CSSSelector* rootSelector, SelectorContext selectorContext)
837     : m_stackAllocator(m_assembler)
838     , m_selectorContext(selectorContext)
839     , m_functionType(FunctionType::SimpleSelectorChecker)
840     , m_visitedMode(VisitedMode::None)
841     , m_descendantBacktrackingStartInUse(false)
842 #if CSS_SELECTOR_JIT_DEBUGGING
843     , m_originalSelector(rootSelector)
844 #endif
845 {
846 #if CSS_SELECTOR_JIT_DEBUGGING
847     dataLogF("Compiling \"%s\"\n", m_originalSelector->selectorText().utf8().data());
848 #endif
849
850     // In QuerySelector context, :visited always has no effect due to security issues.
851     bool visitedMatchEnabled = selectorContext != SelectorContext::QuerySelector;
852
853     m_functionType = constructFragments(rootSelector, m_selectorContext, m_selectorFragments, FragmentsLevel::Root, FragmentPositionInRootFragments::Rightmost, visitedMatchEnabled, m_visitedMode, PseudoElementMatchingBehavior::CanMatch);
854     if (m_functionType != FunctionType::CannotCompile && m_functionType != FunctionType::CannotMatchAnything)
855         computeBacktrackingInformation(m_selectorFragments);
856 }
857
858 static bool pseudoClassOnlyMatchesLinksInQuirksMode(const CSSSelector& selector)
859 {
860     CSSSelector::PseudoClassType pseudoClassType = selector.pseudoClassType();
861     return pseudoClassType == CSSSelector::PseudoClassHover || pseudoClassType == CSSSelector::PseudoClassActive;
862 }
863
864 static bool isScrollbarPseudoElement(CSSSelector::PseudoElementType type)
865 {
866     return type >= CSSSelector::PseudoElementScrollbar && type <= CSSSelector::PseudoElementScrollbarTrackPiece;
867 }
868
869 static FunctionType constructFragmentsInternal(const CSSSelector* rootSelector, SelectorContext selectorContext, SelectorFragmentList& selectorFragments, FragmentsLevel fragmentLevel, FragmentPositionInRootFragments positionInRootFragments, bool visitedMatchEnabled, VisitedMode& visitedMode, PseudoElementMatchingBehavior pseudoElementMatchingBehavior)
870 {
871     FragmentRelation relationToPreviousFragment = FragmentRelation::Rightmost;
872     FunctionType functionType = FunctionType::SimpleSelectorChecker;
873     SelectorFragment* fragment = nullptr;
874     unsigned specificity = 0;
875     for (const CSSSelector* selector = rootSelector; selector; selector = selector->tagHistory()) {
876         if (!fragment) {
877             selectorFragments.append(SelectorFragment());
878             fragment = &selectorFragments.last();
879         }
880
881         specificity = CSSSelector::addSpecificities(specificity, selector->simpleSelectorSpecificity());
882
883         // A selector is invalid if something follows a pseudo-element.
884         // We make an exception for scrollbar pseudo elements and allow a set of pseudo classes (but nothing else)
885         // to follow the pseudo elements.
886         if (fragment->pseudoElementSelector && !isScrollbarPseudoElement(fragment->pseudoElementSelector->pseudoElementType()))
887             return FunctionType::CannotMatchAnything;
888
889         switch (selector->match()) {
890         case CSSSelector::Tag:
891             ASSERT(!fragment->tagNameSelector);
892             fragment->tagNameSelector = selector;
893             if (fragment->tagNameSelector->tagQName() != anyQName())
894                 fragment->onlyMatchesLinksInQuirksMode = false;
895             break;
896         case CSSSelector::Id: {
897             const AtomicString& id = selector->value();
898             if (fragment->id) {
899                 if (id != *fragment->id)
900                     return FunctionType::CannotMatchAnything;
901             } else
902                 fragment->id = &(selector->value());
903             fragment->onlyMatchesLinksInQuirksMode = false;
904             break;
905         }
906         case CSSSelector::Class:
907             fragment->classNames.append(selector->value().impl());
908             fragment->onlyMatchesLinksInQuirksMode = false;
909             break;
910         case CSSSelector::PseudoClass: {
911             FragmentPositionInRootFragments subPosition = positionInRootFragments;
912             if (relationToPreviousFragment != FragmentRelation::Rightmost)
913                 subPosition = FragmentPositionInRootFragments::NotRightmost;
914             if (fragment->pseudoElementSelector && isScrollbarPseudoElement(fragment->pseudoElementSelector->pseudoElementType()))
915                 functionType = mostRestrictiveFunctionType(functionType, addScrollbarPseudoClassType(*selector, *fragment));
916             else {
917                 unsigned internalSpecificity = 0;
918                 functionType = mostRestrictiveFunctionType(functionType, addPseudoClassType(*selector, *fragment, internalSpecificity, selectorContext, fragmentLevel, subPosition, visitedMatchEnabled, visitedMode, pseudoElementMatchingBehavior));
919                 specificity = CSSSelector::addSpecificities(specificity, internalSpecificity);
920             }
921             if (!pseudoClassOnlyMatchesLinksInQuirksMode(*selector))
922                 fragment->onlyMatchesLinksInQuirksMode = false;
923             if (functionType == FunctionType::CannotCompile || functionType == FunctionType::CannotMatchAnything)
924                 return functionType;
925             break;
926         }
927         case CSSSelector::PseudoElement: {
928             fragment->onlyMatchesLinksInQuirksMode = false;
929
930             // In the QuerySelector context, PseudoElement selectors always fail.
931             if (selectorContext == SelectorContext::QuerySelector)
932                 return FunctionType::CannotMatchAnything;
933
934             switch (selector->pseudoElementType()) {
935             case CSSSelector::PseudoElementAfter:
936             case CSSSelector::PseudoElementBefore:
937             case CSSSelector::PseudoElementFirstLetter:
938             case CSSSelector::PseudoElementFirstLine:
939             case CSSSelector::PseudoElementScrollbar:
940             case CSSSelector::PseudoElementScrollbarButton:
941             case CSSSelector::PseudoElementScrollbarCorner:
942             case CSSSelector::PseudoElementScrollbarThumb:
943             case CSSSelector::PseudoElementScrollbarTrack:
944             case CSSSelector::PseudoElementScrollbarTrackPiece:
945                 ASSERT(!fragment->pseudoElementSelector);
946                 fragment->pseudoElementSelector = selector;
947                 break;
948             case CSSSelector::PseudoElementUnknown:
949                 ASSERT_NOT_REACHED();
950                 return FunctionType::CannotMatchAnything;
951             // FIXME: Support RESIZER, SELECTION etc.
952             default:
953                 // This branch includes custom pseudo elements.
954                 return FunctionType::CannotCompile;
955             }
956
957             if (pseudoElementMatchingBehavior == PseudoElementMatchingBehavior::NeverMatch)
958                 return FunctionType::CannotMatchAnything;
959
960             functionType = FunctionType::SelectorCheckerWithCheckingContext;
961             break;
962         }
963         case CSSSelector::List:
964             if (selector->value().find(isHTMLSpace<UChar>) != notFound)
965                 return FunctionType::CannotMatchAnything;
966             FALLTHROUGH;
967         case CSSSelector::Begin:
968         case CSSSelector::End:
969         case CSSSelector::Contain:
970             if (selector->value().isEmpty())
971                 return FunctionType::CannotMatchAnything;
972             FALLTHROUGH;
973         case CSSSelector::Exact:
974         case CSSSelector::Hyphen:
975             fragment->onlyMatchesLinksInQuirksMode = false;
976             fragment->attributes.append(AttributeMatchingInfo(*selector));
977             break;
978
979         case CSSSelector::Set:
980             fragment->onlyMatchesLinksInQuirksMode = false;
981             fragment->attributes.append(AttributeMatchingInfo(*selector));
982             break;
983         case CSSSelector::PagePseudoClass:
984             fragment->onlyMatchesLinksInQuirksMode = false;
985             // Pseudo page class are only relevant for style resolution, they are ignored for matching.
986             break;
987         case CSSSelector::Unknown:
988             ASSERT_NOT_REACHED();
989             return FunctionType::CannotMatchAnything;
990         }
991
992         CSSSelector::Relation relation = selector->relation();
993         if (relation == CSSSelector::SubSelector)
994             continue;
995
996         if (relation == CSSSelector::ShadowDescendant && !selector->isLastInTagHistory())
997             return FunctionType::CannotCompile;
998
999         if (relation == CSSSelector::DirectAdjacent || relation == CSSSelector::IndirectAdjacent) {
1000             FunctionType relationFunctionType = FunctionType::SelectorCheckerWithCheckingContext;
1001             if (selectorContext == SelectorContext::QuerySelector)
1002                 relationFunctionType = FunctionType::SimpleSelectorChecker;
1003             functionType = mostRestrictiveFunctionType(functionType, relationFunctionType);
1004
1005             // When the relation is adjacent, disable :visited match.
1006             visitedMatchEnabled = false;
1007         }
1008
1009         // Virtual pseudo element is only effective in the rightmost fragment.
1010         pseudoElementMatchingBehavior = PseudoElementMatchingBehavior::NeverMatch;
1011
1012         fragment->relationToLeftFragment = fragmentRelationForSelectorRelation(relation);
1013         fragment->relationToRightFragment = relationToPreviousFragment;
1014         fragment->positionInRootFragments = positionInRootFragments;
1015         relationToPreviousFragment = fragment->relationToLeftFragment;
1016
1017         if (fragmentLevel != FragmentsLevel::Root)
1018             fragment->onlyMatchesLinksInQuirksMode = false;
1019
1020         fragment = nullptr;
1021     }
1022
1023     ASSERT(!fragment);
1024
1025     selectorFragments.staticSpecificity = specificity;
1026
1027     return functionType;
1028 }
1029
1030 static FunctionType constructFragments(const CSSSelector* rootSelector, SelectorContext selectorContext, SelectorFragmentList& selectorFragments, FragmentsLevel fragmentLevel, FragmentPositionInRootFragments positionInRootFragments, bool visitedMatchEnabled, VisitedMode& visitedMode, PseudoElementMatchingBehavior pseudoElementMatchingBehavior)
1031 {
1032     ASSERT(selectorFragments.isEmpty());
1033
1034     FunctionType functionType = constructFragmentsInternal(rootSelector, selectorContext, selectorFragments, fragmentLevel, positionInRootFragments, visitedMatchEnabled, visitedMode, pseudoElementMatchingBehavior);
1035     if (functionType != FunctionType::SimpleSelectorChecker && functionType != FunctionType::SelectorCheckerWithCheckingContext)
1036         selectorFragments.clear();
1037     return functionType;
1038 }
1039
1040 static inline bool attributeNameTestingRequiresNamespaceRegister(const CSSSelector& attributeSelector)
1041 {
1042     return attributeSelector.attribute().prefix() != starAtom && !attributeSelector.attribute().namespaceURI().isNull();
1043 }
1044
1045 static inline bool attributeValueTestingRequiresExtraRegister(const AttributeMatchingInfo& attributeInfo)
1046 {
1047     switch (attributeInfo.attributeCaseSensitivity()) {
1048     case AttributeCaseSensitivity::CaseSensitive:
1049         return false;
1050     case AttributeCaseSensitivity::HTMLLegacyCaseInsensitive:
1051         return true;
1052     case AttributeCaseSensitivity::CaseInsensitive:
1053         return attributeInfo.selector().match() == CSSSelector::Exact;
1054     }
1055     return true;
1056 }
1057
1058 // Element + ElementData + a pointer to values + an index on that pointer + the value we expect;
1059 static const unsigned minimumRequiredRegisterCount = 5;
1060 // Element + ElementData + scratchRegister + attributeArrayPointer + expectedLocalName + (qualifiedNameImpl && expectedValue).
1061 static const unsigned minimumRequiredRegisterCountForAttributeFilter = 6;
1062 #if CPU(X86_64)
1063 // Element + SiblingCounter + SiblingCounterCopy + divisor + dividend + remainder.
1064 static const unsigned minimumRequiredRegisterCountForNthChildFilter = 6;
1065 #endif
1066
1067 static unsigned minimumRegisterRequirements(const SelectorFragment& selectorFragment)
1068 {
1069     unsigned minimum = minimumRequiredRegisterCount;
1070     const auto& attributes = selectorFragment.attributes;
1071
1072     // Attributes cause some register pressure.
1073     unsigned attributeCount = attributes.size();
1074     for (unsigned attributeIndex = 0; attributeIndex < attributeCount; ++attributeIndex) {
1075         unsigned attributeMinimum = minimumRequiredRegisterCountForAttributeFilter;
1076
1077         if (attributeIndex + 1 < attributeCount)
1078             attributeMinimum += 2; // For the local copy of the counter and attributeArrayPointer.
1079
1080         const AttributeMatchingInfo& attributeInfo = attributes[attributeIndex];
1081         const CSSSelector& attributeSelector = attributeInfo.selector();
1082         if (attributeNameTestingRequiresNamespaceRegister(attributeSelector)
1083             || attributeValueTestingRequiresExtraRegister(attributeInfo))
1084             attributeMinimum += 1;
1085
1086         minimum = std::max(minimum, attributeMinimum);
1087     }
1088
1089 #if CPU(X86_64)
1090     if (!selectorFragment.nthChildFilters.isEmpty() || !selectorFragment.nthChildOfFilters.isEmpty() || !selectorFragment.nthLastChildFilters.isEmpty() || !selectorFragment.nthLastChildOfFilters.isEmpty())
1091         minimum = std::max(minimum, minimumRequiredRegisterCountForNthChildFilter);
1092 #endif
1093
1094     // :any pseudo class filters cause some register pressure.
1095     for (const auto& subFragments : selectorFragment.anyFilters) {
1096         for (const SelectorFragment& subFragment : subFragments) {
1097             unsigned anyFilterMinimum = minimumRegisterRequirements(subFragment);
1098             minimum = std::max(minimum, anyFilterMinimum);
1099         }
1100     }
1101
1102     return minimum;
1103 }
1104
1105 bool hasAnyCombinators(const Vector<SelectorFragmentList>& selectorList);
1106 template <size_t inlineCapacity>
1107 bool hasAnyCombinators(const Vector<SelectorFragment, inlineCapacity>& selectorFragmentList);
1108
1109 bool hasAnyCombinators(const Vector<SelectorFragmentList>& selectorList)
1110 {
1111     for (const SelectorFragmentList& selectorFragmentList : selectorList) {
1112         if (hasAnyCombinators(selectorFragmentList))
1113             return true;
1114     }
1115     return false;
1116 }
1117
1118 template <size_t inlineCapacity>
1119 bool hasAnyCombinators(const Vector<SelectorFragment, inlineCapacity>& selectorFragmentList)
1120 {
1121     if (selectorFragmentList.isEmpty())
1122         return false;
1123     if (selectorFragmentList.size() != 1)
1124         return true;
1125     if (hasAnyCombinators(selectorFragmentList.first().notFilters))
1126         return true;
1127     for (const SelectorList& matchesList : selectorFragmentList.first().matchesFilters) {
1128         if (hasAnyCombinators(matchesList))
1129             return true;
1130     }
1131     for (const NthChildOfSelectorInfo& nthChildOfSelectorInfo : selectorFragmentList.first().nthChildOfFilters) {
1132         if (hasAnyCombinators(nthChildOfSelectorInfo.selectorList))
1133             return true;
1134     }
1135     for (const NthChildOfSelectorInfo& nthLastChildOfSelectorInfo : selectorFragmentList.first().nthLastChildOfFilters) {
1136         if (hasAnyCombinators(nthLastChildOfSelectorInfo.selectorList))
1137             return true;
1138     }
1139     return false;
1140 }
1141
1142 // The CSS JIT has only been validated with a strict minimum of 6 allocated registers.
1143 const unsigned minimumRegisterRequirement = 6;
1144
1145 void computeBacktrackingMemoryRequirements(SelectorFragmentList& selectorFragments, bool backtrackingRegisterReserved = false);
1146
1147 static void computeBacktrackingMemoryRequirements(SelectorList& selectorList, unsigned& totalRegisterRequirements, unsigned& totalStackRequirements, bool backtrackingRegisterReservedForFragment = false)
1148 {
1149     unsigned selectorListRegisterRequirements = 0;
1150     unsigned selectorListStackRequirements = 0;
1151     bool clobberElementAddressRegister = false;
1152
1153     for (SelectorFragmentList& selectorFragmentList : selectorList) {
1154         computeBacktrackingMemoryRequirements(selectorFragmentList, backtrackingRegisterReservedForFragment);
1155
1156         selectorListRegisterRequirements = std::max(selectorListRegisterRequirements, selectorFragmentList.registerRequirements);
1157         selectorListStackRequirements = std::max(selectorListStackRequirements, selectorFragmentList.stackRequirements);
1158         clobberElementAddressRegister = clobberElementAddressRegister || selectorFragmentList.clobberElementAddressRegister;
1159     }
1160
1161     totalRegisterRequirements = std::max(totalRegisterRequirements, selectorListRegisterRequirements);
1162     totalStackRequirements = std::max(totalStackRequirements, selectorListStackRequirements);
1163
1164     selectorList.registerRequirements = std::max(selectorListRegisterRequirements, minimumRegisterRequirement);
1165     selectorList.stackRequirements = selectorListStackRequirements;
1166     selectorList.clobberElementAddressRegister = clobberElementAddressRegister;
1167 }
1168
1169 void computeBacktrackingMemoryRequirements(SelectorFragmentList& selectorFragments, bool backtrackingRegisterReserved)
1170 {
1171     selectorFragments.registerRequirements = minimumRegisterRequirement;
1172     selectorFragments.stackRequirements = 0;
1173     selectorFragments.clobberElementAddressRegister = hasAnyCombinators(selectorFragments);
1174
1175     for (SelectorFragment& selectorFragment : selectorFragments) {
1176         unsigned fragmentRegisterRequirements = minimumRegisterRequirements(selectorFragment);
1177         unsigned fragmentStackRequirements = 0;
1178
1179         bool backtrackingRegisterReservedForFragment = backtrackingRegisterReserved || selectorFragment.backtrackingFlags & BacktrackingFlag::InChainWithDescendantTail;
1180
1181         computeBacktrackingMemoryRequirements(selectorFragment.notFilters, fragmentRegisterRequirements, fragmentStackRequirements, backtrackingRegisterReservedForFragment);
1182
1183         for (SelectorList& matchesList : selectorFragment.matchesFilters)
1184             computeBacktrackingMemoryRequirements(matchesList, fragmentRegisterRequirements, fragmentStackRequirements, backtrackingRegisterReservedForFragment);
1185
1186         for (NthChildOfSelectorInfo& nthChildOfSelectorInfo : selectorFragment.nthChildOfFilters)
1187             computeBacktrackingMemoryRequirements(nthChildOfSelectorInfo.selectorList, fragmentRegisterRequirements, fragmentStackRequirements, backtrackingRegisterReservedForFragment);
1188
1189         for (NthChildOfSelectorInfo& nthLastChildOfSelectorInfo : selectorFragment.nthLastChildOfFilters)
1190             computeBacktrackingMemoryRequirements(nthLastChildOfSelectorInfo.selectorList, fragmentRegisterRequirements, fragmentStackRequirements, backtrackingRegisterReservedForFragment);
1191
1192         if (selectorFragment.backtrackingFlags & BacktrackingFlag::InChainWithDescendantTail) {
1193             if (!backtrackingRegisterReserved)
1194                 ++fragmentRegisterRequirements;
1195             else
1196                 ++fragmentStackRequirements;
1197         }
1198         if (selectorFragment.backtrackingFlags & BacktrackingFlag::InChainWithAdjacentTail)
1199             ++fragmentStackRequirements;
1200
1201         selectorFragments.registerRequirements = std::max(selectorFragments.registerRequirements, fragmentRegisterRequirements);
1202         selectorFragments.stackRequirements = std::max(selectorFragments.stackRequirements, fragmentStackRequirements);
1203     }
1204 }
1205
1206 inline SelectorCompilationStatus SelectorCodeGenerator::compile(JSC::VM* vm, JSC::MacroAssemblerCodeRef& codeRef)
1207 {
1208     switch (m_functionType) {
1209     case FunctionType::SimpleSelectorChecker:
1210     case FunctionType::SelectorCheckerWithCheckingContext:
1211         generateSelectorChecker();
1212         break;
1213     case FunctionType::CannotMatchAnything:
1214         m_assembler.move(Assembler::TrustedImm32(0), returnRegister);
1215         m_assembler.ret();
1216         break;
1217     case FunctionType::CannotCompile:
1218         return SelectorCompilationStatus::CannotCompile;
1219     }
1220
1221     JSC::LinkBuffer linkBuffer(*vm, m_assembler, CSS_CODE_ID, JSC::JITCompilationCanFail);
1222     if (!linkBuffer.isValid()) {
1223         // This could be SelectorCompilationStatus::NotCompiled but that would cause us to re-enter
1224         // the CSS JIT every time we evaluate that selector.
1225         // If we failed to allocate the buffer, we have bigger problems than CSS performance, it is fine
1226         // to be slower.
1227         return SelectorCompilationStatus::CannotCompile;
1228     }
1229
1230     for (unsigned i = 0; i < m_functionCalls.size(); i++)
1231         linkBuffer.link(m_functionCalls[i].first, m_functionCalls[i].second);
1232
1233 #if CSS_SELECTOR_JIT_DEBUGGING
1234     codeRef = linkBuffer.finalizeCodeWithDisassembly("CSS Selector JIT for \"%s\"", m_originalSelector->selectorText().utf8().data());
1235 #else
1236     codeRef = FINALIZE_CODE(linkBuffer, ("CSS Selector JIT"));
1237 #endif
1238
1239     if (m_functionType == FunctionType::SimpleSelectorChecker || m_functionType == FunctionType::CannotMatchAnything)
1240         return SelectorCompilationStatus::SimpleSelectorChecker;
1241     return SelectorCompilationStatus::SelectorCheckerWithCheckingContext;
1242 }
1243
1244
1245 static inline void updateChainStates(const SelectorFragment& fragment, bool& hasDescendantRelationOnTheRight, unsigned& ancestorPositionSinceDescendantRelation, bool& hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain, unsigned& adjacentPositionSinceIndirectAdjacentTreeWalk)
1246 {
1247     switch (fragment.relationToRightFragment) {
1248     case FragmentRelation::Rightmost:
1249         break;
1250     case FragmentRelation::Descendant:
1251         hasDescendantRelationOnTheRight = true;
1252         ancestorPositionSinceDescendantRelation = 0;
1253         hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain = false;
1254         break;
1255     case FragmentRelation::Child:
1256         if (hasDescendantRelationOnTheRight)
1257             ++ancestorPositionSinceDescendantRelation;
1258         hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain = false;
1259         break;
1260     case FragmentRelation::DirectAdjacent:
1261         if (hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain)
1262             ++adjacentPositionSinceIndirectAdjacentTreeWalk;
1263         break;
1264     case FragmentRelation::IndirectAdjacent:
1265         hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain = true;
1266         adjacentPositionSinceIndirectAdjacentTreeWalk = 0;
1267         break;
1268     }
1269 }
1270
1271 static inline bool isFirstAncestor(unsigned ancestorPositionSinceDescendantRelation)
1272 {
1273     return ancestorPositionSinceDescendantRelation == 1;
1274 }
1275
1276 static inline bool isFirstAdjacent(unsigned adjacentPositionSinceIndirectAdjacentTreeWalk)
1277 {
1278     return adjacentPositionSinceIndirectAdjacentTreeWalk == 1;
1279 }
1280
1281 static inline BacktrackingAction solveDescendantBacktrackingActionForChild(const SelectorFragment& fragment, unsigned backtrackingStartHeightFromDescendant)
1282 {
1283     // If height is invalid (e.g. There's no tag name).
1284     if (backtrackingStartHeightFromDescendant == invalidHeight)
1285         return BacktrackingAction::NoBacktracking;
1286
1287     // Start backtracking from the current element.
1288     if (backtrackingStartHeightFromDescendant == fragment.heightFromDescendant)
1289         return BacktrackingAction::JumpToDescendantEntryPoint;
1290
1291     // Start backtracking from the parent of current element.
1292     if (backtrackingStartHeightFromDescendant == (fragment.heightFromDescendant + 1))
1293         return BacktrackingAction::JumpToDescendantTreeWalkerEntryPoint;
1294
1295     return BacktrackingAction::JumpToDescendantTail;
1296 }
1297
1298 static inline BacktrackingAction solveAdjacentBacktrackingActionForDirectAdjacent(const SelectorFragment& fragment, unsigned backtrackingStartWidthFromIndirectAdjacent)
1299 {
1300     // If width is invalid (e.g. There's no tag name).
1301     if (backtrackingStartWidthFromIndirectAdjacent == invalidWidth)
1302         return BacktrackingAction::NoBacktracking;
1303
1304     // Start backtracking from the current element.
1305     if (backtrackingStartWidthFromIndirectAdjacent == fragment.widthFromIndirectAdjacent)
1306         return BacktrackingAction::JumpToIndirectAdjacentEntryPoint;
1307
1308     // Start backtracking from the previous adjacent of current element.
1309     if (backtrackingStartWidthFromIndirectAdjacent == (fragment.widthFromIndirectAdjacent + 1))
1310         return BacktrackingAction::JumpToIndirectAdjacentTreeWalkerEntryPoint;
1311
1312     return BacktrackingAction::JumpToDirectAdjacentTail;
1313 }
1314
1315 static inline BacktrackingAction solveAdjacentTraversalBacktrackingAction(const SelectorFragment& fragment, bool hasDescendantRelationOnTheRight)
1316 {
1317     if (!hasDescendantRelationOnTheRight)
1318         return BacktrackingAction::NoBacktracking;
1319
1320     if (fragment.tagNameMatchedBacktrackingStartHeightFromDescendant == (fragment.heightFromDescendant + 1))
1321         return BacktrackingAction::JumpToDescendantTreeWalkerEntryPoint;
1322
1323     return BacktrackingAction::JumpToDescendantTail;
1324 }
1325
1326 static inline void solveBacktrackingAction(SelectorFragment& fragment, bool hasDescendantRelationOnTheRight, bool hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain)
1327 {
1328     switch (fragment.relationToRightFragment) {
1329     case FragmentRelation::Rightmost:
1330     case FragmentRelation::Descendant:
1331         break;
1332     case FragmentRelation::Child:
1333         // Failure to match the element should resume matching at the nearest ancestor/descendant entry point.
1334         if (hasDescendantRelationOnTheRight) {
1335             fragment.matchingTagNameBacktrackingAction = solveDescendantBacktrackingActionForChild(fragment, fragment.tagNameNotMatchedBacktrackingStartHeightFromDescendant);
1336             fragment.matchingPostTagNameBacktrackingAction = solveDescendantBacktrackingActionForChild(fragment, fragment.tagNameMatchedBacktrackingStartHeightFromDescendant);
1337         }
1338         break;
1339     case FragmentRelation::DirectAdjacent:
1340         // Failure on traversal implies no other sibling traversal can match. Matching should resume at the
1341         // nearest ancestor/descendant traversal.
1342         fragment.traversalBacktrackingAction = solveAdjacentTraversalBacktrackingAction(fragment, hasDescendantRelationOnTheRight);
1343
1344         // If the rightmost relation is a indirect adjacent, matching sould resume from there.
1345         // Otherwise, we resume from the latest ancestor/descendant if any.
1346         if (hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain) {
1347             fragment.matchingTagNameBacktrackingAction = solveAdjacentBacktrackingActionForDirectAdjacent(fragment, fragment.tagNameNotMatchedBacktrackingStartWidthFromIndirectAdjacent);
1348             fragment.matchingPostTagNameBacktrackingAction = solveAdjacentBacktrackingActionForDirectAdjacent(fragment, fragment.tagNameMatchedBacktrackingStartWidthFromIndirectAdjacent);
1349         } else if (hasDescendantRelationOnTheRight) {
1350             // Since we resume from the latest ancestor/descendant, the action is the same as the traversal action.
1351             fragment.matchingTagNameBacktrackingAction = fragment.traversalBacktrackingAction;
1352             fragment.matchingPostTagNameBacktrackingAction = fragment.traversalBacktrackingAction;
1353         }
1354         break;
1355     case FragmentRelation::IndirectAdjacent:
1356         // Failure on traversal implies no other sibling matching will succeed. Matching can resume
1357         // from the latest ancestor/descendant.
1358         fragment.traversalBacktrackingAction = solveAdjacentTraversalBacktrackingAction(fragment, hasDescendantRelationOnTheRight);
1359         break;
1360     }
1361 }
1362
1363 enum class TagNameEquality {
1364     StrictlyNotEqual,
1365     MaybeEqual,
1366     StrictlyEqual
1367 };
1368
1369 static inline TagNameEquality equalTagNames(const CSSSelector* lhs, const CSSSelector* rhs)
1370 {
1371     if (!lhs || !rhs)
1372         return TagNameEquality::MaybeEqual;
1373
1374     const QualifiedName& lhsQualifiedName = lhs->tagQName();
1375     if (lhsQualifiedName == anyQName())
1376         return TagNameEquality::MaybeEqual;
1377
1378     const QualifiedName& rhsQualifiedName = rhs->tagQName();
1379     if (rhsQualifiedName == anyQName())
1380         return TagNameEquality::MaybeEqual;
1381
1382     const AtomicString& lhsLocalName = lhsQualifiedName.localName();
1383     const AtomicString& rhsLocalName = rhsQualifiedName.localName();
1384     if (lhsLocalName != starAtom && rhsLocalName != starAtom) {
1385         const AtomicString& lhsLowercaseLocalName = lhs->tagLowercaseLocalName();
1386         const AtomicString& rhsLowercaseLocalName = rhs->tagLowercaseLocalName();
1387
1388         if (lhsLowercaseLocalName != rhsLowercaseLocalName)
1389             return TagNameEquality::StrictlyNotEqual;
1390
1391         if (lhsLocalName == lhsLowercaseLocalName && rhsLocalName == rhsLowercaseLocalName)
1392             return TagNameEquality::StrictlyEqual;
1393         return TagNameEquality::MaybeEqual;
1394     }
1395
1396     const AtomicString& lhsNamespaceURI = lhsQualifiedName.namespaceURI();
1397     const AtomicString& rhsNamespaceURI = rhsQualifiedName.namespaceURI();
1398     if (lhsNamespaceURI != starAtom && rhsNamespaceURI != starAtom) {
1399         if (lhsNamespaceURI != rhsNamespaceURI)
1400             return TagNameEquality::StrictlyNotEqual;
1401         return TagNameEquality::StrictlyEqual;
1402     }
1403
1404     return TagNameEquality::MaybeEqual;
1405 }
1406
1407 static inline bool equalTagNamePatterns(const TagNamePattern& lhs, const TagNamePattern& rhs)
1408 {
1409     TagNameEquality result = equalTagNames(lhs.tagNameSelector, rhs.tagNameSelector);
1410     if (result == TagNameEquality::MaybeEqual)
1411         return true;
1412
1413     // If both rhs & lhs have actual localName (or NamespaceURI),
1414     // TagNameEquality result becomes StrictlyEqual or StrictlyNotEqual Since inverted lhs never matches on rhs.
1415     bool equal = result == TagNameEquality::StrictlyEqual;
1416     if (lhs.inverted)
1417         return !equal;
1418     return equal;
1419 }
1420
1421 // Find the largest matching prefix from already known tagNames.
1422 // And by using this, compute an appropriate height of backtracking start element from the closest base element in the chain.
1423 static inline unsigned computeBacktrackingStartOffsetInChain(const TagNameList& tagNames, unsigned maxPrefixSize)
1424 {
1425     RELEASE_ASSERT(!tagNames.isEmpty());
1426     RELEASE_ASSERT(maxPrefixSize < tagNames.size());
1427
1428     for (unsigned largestPrefixSize = maxPrefixSize; largestPrefixSize > 0; --largestPrefixSize) {
1429         unsigned offsetToLargestPrefix = tagNames.size() - largestPrefixSize;
1430         bool matched = true;
1431         // Since TagNamePatterns are pushed to a tagNames, check tagNames with reverse order.
1432         for (unsigned i = 0; i < largestPrefixSize; ++i) {
1433             unsigned lastIndex = tagNames.size() - 1;
1434             unsigned currentIndex = lastIndex - i;
1435             if (!equalTagNamePatterns(tagNames[currentIndex], tagNames[currentIndex - offsetToLargestPrefix])) {
1436                 matched = false;
1437                 break;
1438             }
1439         }
1440         if (matched)
1441             return offsetToLargestPrefix;
1442     }
1443     return tagNames.size();
1444 }
1445
1446 static inline void computeBacktrackingHeightFromDescendant(SelectorFragment& fragment, TagNameList& tagNamesForChildChain, bool hasDescendantRelationOnTheRight, const SelectorFragment*& previousChildFragmentInChildChain)
1447 {
1448     if (!hasDescendantRelationOnTheRight)
1449         return;
1450
1451     if (fragment.relationToRightFragment == FragmentRelation::Descendant) {
1452         tagNamesForChildChain.clear();
1453
1454         TagNamePattern pattern;
1455         pattern.tagNameSelector = fragment.tagNameSelector;
1456         tagNamesForChildChain.append(pattern);
1457         fragment.heightFromDescendant = 0;
1458         previousChildFragmentInChildChain = nullptr;
1459     } else if (fragment.relationToRightFragment == FragmentRelation::Child) {
1460         TagNamePattern pattern;
1461         pattern.tagNameSelector = fragment.tagNameSelector;
1462         tagNamesForChildChain.append(pattern);
1463
1464         unsigned maxPrefixSize = tagNamesForChildChain.size() - 1;
1465         if (previousChildFragmentInChildChain) {
1466             RELEASE_ASSERT(tagNamesForChildChain.size() >= previousChildFragmentInChildChain->tagNameMatchedBacktrackingStartHeightFromDescendant);
1467             maxPrefixSize = tagNamesForChildChain.size() - previousChildFragmentInChildChain->tagNameMatchedBacktrackingStartHeightFromDescendant;
1468         }
1469
1470         if (pattern.tagNameSelector) {
1471             // Compute height from descendant in the case that tagName is not matched.
1472             tagNamesForChildChain.last().inverted = true;
1473             fragment.tagNameNotMatchedBacktrackingStartHeightFromDescendant = computeBacktrackingStartOffsetInChain(tagNamesForChildChain, maxPrefixSize);
1474         }
1475
1476         // Compute height from descendant in the case that tagName is matched.
1477         tagNamesForChildChain.last().inverted = false;
1478         fragment.tagNameMatchedBacktrackingStartHeightFromDescendant = computeBacktrackingStartOffsetInChain(tagNamesForChildChain, maxPrefixSize);
1479         fragment.heightFromDescendant = tagNamesForChildChain.size() - 1;
1480         previousChildFragmentInChildChain = &fragment;
1481     } else {
1482         if (previousChildFragmentInChildChain) {
1483             fragment.tagNameNotMatchedBacktrackingStartHeightFromDescendant = previousChildFragmentInChildChain->tagNameNotMatchedBacktrackingStartHeightFromDescendant;
1484             fragment.tagNameMatchedBacktrackingStartHeightFromDescendant = previousChildFragmentInChildChain->tagNameMatchedBacktrackingStartHeightFromDescendant;
1485             fragment.heightFromDescendant = previousChildFragmentInChildChain->heightFromDescendant;
1486         } else {
1487             fragment.tagNameNotMatchedBacktrackingStartHeightFromDescendant = tagNamesForChildChain.size();
1488             fragment.tagNameMatchedBacktrackingStartHeightFromDescendant = tagNamesForChildChain.size();
1489             fragment.heightFromDescendant = 0;
1490         }
1491     }
1492 }
1493
1494 static inline void computeBacktrackingWidthFromIndirectAdjacent(SelectorFragment& fragment, TagNameList& tagNamesForDirectAdjacentChain, bool hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain, const SelectorFragment*& previousDirectAdjacentFragmentInDirectAdjacentChain)
1495 {
1496     if (!hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain)
1497         return;
1498
1499     if (fragment.relationToRightFragment == FragmentRelation::IndirectAdjacent) {
1500         tagNamesForDirectAdjacentChain.clear();
1501
1502         TagNamePattern pattern;
1503         pattern.tagNameSelector = fragment.tagNameSelector;
1504         tagNamesForDirectAdjacentChain.append(pattern);
1505         fragment.widthFromIndirectAdjacent = 0;
1506         previousDirectAdjacentFragmentInDirectAdjacentChain = nullptr;
1507     } else if (fragment.relationToRightFragment == FragmentRelation::DirectAdjacent) {
1508         TagNamePattern pattern;
1509         pattern.tagNameSelector = fragment.tagNameSelector;
1510         tagNamesForDirectAdjacentChain.append(pattern);
1511
1512         unsigned maxPrefixSize = tagNamesForDirectAdjacentChain.size() - 1;
1513         if (previousDirectAdjacentFragmentInDirectAdjacentChain) {
1514             RELEASE_ASSERT(tagNamesForDirectAdjacentChain.size() >= previousDirectAdjacentFragmentInDirectAdjacentChain->tagNameMatchedBacktrackingStartWidthFromIndirectAdjacent);
1515             maxPrefixSize = tagNamesForDirectAdjacentChain.size() - previousDirectAdjacentFragmentInDirectAdjacentChain->tagNameMatchedBacktrackingStartWidthFromIndirectAdjacent;
1516         }
1517
1518         if (pattern.tagNameSelector) {
1519             // Compute height from descendant in the case that tagName is not matched.
1520             tagNamesForDirectAdjacentChain.last().inverted = true;
1521             fragment.tagNameNotMatchedBacktrackingStartWidthFromIndirectAdjacent = computeBacktrackingStartOffsetInChain(tagNamesForDirectAdjacentChain, maxPrefixSize);
1522         }
1523
1524         // Compute height from descendant in the case that tagName is matched.
1525         tagNamesForDirectAdjacentChain.last().inverted = false;
1526         fragment.tagNameMatchedBacktrackingStartWidthFromIndirectAdjacent = computeBacktrackingStartOffsetInChain(tagNamesForDirectAdjacentChain, maxPrefixSize);
1527         fragment.widthFromIndirectAdjacent = tagNamesForDirectAdjacentChain.size() - 1;
1528         previousDirectAdjacentFragmentInDirectAdjacentChain = &fragment;
1529     }
1530 }
1531
1532 static bool requiresAdjacentTail(const SelectorFragment& fragment)
1533 {
1534     ASSERT(fragment.traversalBacktrackingAction != BacktrackingAction::JumpToDirectAdjacentTail);
1535     return fragment.matchingTagNameBacktrackingAction == BacktrackingAction::JumpToDirectAdjacentTail || fragment.matchingPostTagNameBacktrackingAction == BacktrackingAction::JumpToDirectAdjacentTail;
1536 }
1537
1538 static bool requiresDescendantTail(const SelectorFragment& fragment)
1539 {
1540     return fragment.matchingTagNameBacktrackingAction == BacktrackingAction::JumpToDescendantTail || fragment.matchingPostTagNameBacktrackingAction == BacktrackingAction::JumpToDescendantTail || fragment.traversalBacktrackingAction == BacktrackingAction::JumpToDescendantTail;
1541 }
1542
1543 void computeBacktrackingInformation(SelectorFragmentList& selectorFragments, unsigned level)
1544 {
1545     bool hasDescendantRelationOnTheRight = false;
1546     unsigned ancestorPositionSinceDescendantRelation = 0;
1547     bool hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain = false;
1548     unsigned adjacentPositionSinceIndirectAdjacentTreeWalk = 0;
1549
1550     bool needsAdjacentTail = false;
1551     bool needsDescendantTail = false;
1552     unsigned saveDescendantBacktrackingStartFragmentIndex = std::numeric_limits<unsigned>::max();
1553     unsigned saveIndirectAdjacentBacktrackingStartFragmentIndex = std::numeric_limits<unsigned>::max();
1554
1555     TagNameList tagNamesForChildChain;
1556     TagNameList tagNamesForDirectAdjacentChain;
1557     const SelectorFragment* previousChildFragmentInChildChain = nullptr;
1558     const SelectorFragment* previousDirectAdjacentFragmentInDirectAdjacentChain = nullptr;
1559
1560     for (unsigned i = 0; i < selectorFragments.size(); ++i) {
1561         SelectorFragment& fragment = selectorFragments[i];
1562
1563         updateChainStates(fragment, hasDescendantRelationOnTheRight, ancestorPositionSinceDescendantRelation, hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain, adjacentPositionSinceIndirectAdjacentTreeWalk);
1564
1565         computeBacktrackingHeightFromDescendant(fragment, tagNamesForChildChain, hasDescendantRelationOnTheRight, previousChildFragmentInChildChain);
1566
1567         computeBacktrackingWidthFromIndirectAdjacent(fragment, tagNamesForDirectAdjacentChain, hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain, previousDirectAdjacentFragmentInDirectAdjacentChain);
1568
1569 #if CSS_SELECTOR_JIT_DEBUGGING
1570         dataLogF("%*sComputing fragment[%d] backtracking height %u. NotMatched %u / Matched %u | width %u. NotMatched %u / Matched %u\n", level * 4, "", i, fragment.heightFromDescendant, fragment.tagNameNotMatchedBacktrackingStartHeightFromDescendant, fragment.tagNameMatchedBacktrackingStartHeightFromDescendant, fragment.widthFromIndirectAdjacent, fragment.tagNameNotMatchedBacktrackingStartWidthFromIndirectAdjacent, fragment.tagNameMatchedBacktrackingStartWidthFromIndirectAdjacent);
1571 #endif
1572
1573         solveBacktrackingAction(fragment, hasDescendantRelationOnTheRight, hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain);
1574
1575         needsAdjacentTail |= requiresAdjacentTail(fragment);
1576         needsDescendantTail |= requiresDescendantTail(fragment);
1577
1578         // Add code generation flags.
1579         if (fragment.relationToLeftFragment != FragmentRelation::Descendant && fragment.relationToRightFragment == FragmentRelation::Descendant)
1580             fragment.backtrackingFlags |= BacktrackingFlag::DescendantEntryPoint;
1581         if (fragment.relationToLeftFragment == FragmentRelation::DirectAdjacent && fragment.relationToRightFragment == FragmentRelation::IndirectAdjacent)
1582             fragment.backtrackingFlags |= BacktrackingFlag::IndirectAdjacentEntryPoint;
1583         if (fragment.relationToLeftFragment != FragmentRelation::Descendant && fragment.relationToRightFragment == FragmentRelation::Child && isFirstAncestor(ancestorPositionSinceDescendantRelation)) {
1584             ASSERT(saveDescendantBacktrackingStartFragmentIndex == std::numeric_limits<unsigned>::max());
1585             saveDescendantBacktrackingStartFragmentIndex = i;
1586         }
1587         if (fragment.relationToLeftFragment == FragmentRelation::DirectAdjacent && fragment.relationToRightFragment == FragmentRelation::DirectAdjacent && isFirstAdjacent(adjacentPositionSinceIndirectAdjacentTreeWalk)) {
1588             ASSERT(saveIndirectAdjacentBacktrackingStartFragmentIndex == std::numeric_limits<unsigned>::max());
1589             saveIndirectAdjacentBacktrackingStartFragmentIndex = i;
1590         }
1591         if (fragment.relationToLeftFragment != FragmentRelation::DirectAdjacent) {
1592             if (needsAdjacentTail) {
1593                 ASSERT(fragment.relationToRightFragment == FragmentRelation::DirectAdjacent);
1594                 ASSERT(saveIndirectAdjacentBacktrackingStartFragmentIndex != std::numeric_limits<unsigned>::max());
1595                 fragment.backtrackingFlags |= BacktrackingFlag::DirectAdjacentTail;
1596                 selectorFragments[saveIndirectAdjacentBacktrackingStartFragmentIndex].backtrackingFlags |= BacktrackingFlag::SaveAdjacentBacktrackingStart;
1597                 needsAdjacentTail = false;
1598                 for (unsigned j = saveIndirectAdjacentBacktrackingStartFragmentIndex; j <= i; ++j)
1599                     selectorFragments[j].backtrackingFlags |= BacktrackingFlag::InChainWithAdjacentTail;
1600             }
1601             saveIndirectAdjacentBacktrackingStartFragmentIndex = std::numeric_limits<unsigned>::max();
1602         }
1603         if (fragment.relationToLeftFragment == FragmentRelation::Descendant) {
1604             if (needsDescendantTail) {
1605                 ASSERT(saveDescendantBacktrackingStartFragmentIndex != std::numeric_limits<unsigned>::max());
1606                 fragment.backtrackingFlags |= BacktrackingFlag::DescendantTail;
1607                 selectorFragments[saveDescendantBacktrackingStartFragmentIndex].backtrackingFlags |= BacktrackingFlag::SaveDescendantBacktrackingStart;
1608                 needsDescendantTail = false;
1609                 for (unsigned j = saveDescendantBacktrackingStartFragmentIndex; j <= i; ++j)
1610                     selectorFragments[j].backtrackingFlags |= BacktrackingFlag::InChainWithDescendantTail;
1611             }
1612             saveDescendantBacktrackingStartFragmentIndex = std::numeric_limits<unsigned>::max();
1613         }
1614     }
1615
1616     for (SelectorFragment& fragment : selectorFragments) {
1617         if (!fragment.notFilters.isEmpty()) {
1618 #if CSS_SELECTOR_JIT_DEBUGGING
1619             dataLogF("%*s  Subselectors for :not():\n", level * 4, "");
1620 #endif
1621
1622             for (SelectorFragmentList& selectorList : fragment.notFilters)
1623                 computeBacktrackingInformation(selectorList, level + 1);
1624         }
1625
1626         if (!fragment.matchesFilters.isEmpty()) {
1627             for (SelectorList& matchesList : fragment.matchesFilters) {
1628 #if CSS_SELECTOR_JIT_DEBUGGING
1629                 dataLogF("%*s  Subselectors for :matches():\n", level * 4, "");
1630 #endif
1631
1632                 for (SelectorFragmentList& selectorList : matchesList)
1633                     computeBacktrackingInformation(selectorList, level + 1);
1634             }
1635         }
1636
1637         for (NthChildOfSelectorInfo& nthChildOfSelectorInfo : fragment.nthChildOfFilters) {
1638 #if CSS_SELECTOR_JIT_DEBUGGING
1639             dataLogF("%*s  Subselectors for %dn+%d:\n", level * 4, "", nthChildOfSelectorInfo.a, nthChildOfSelectorInfo.b);
1640 #endif
1641
1642             for (SelectorFragmentList& selectorList : nthChildOfSelectorInfo.selectorList)
1643                 computeBacktrackingInformation(selectorList, level + 1);
1644         }
1645
1646         for (NthChildOfSelectorInfo& nthLastChildOfSelectorInfo : fragment.nthLastChildOfFilters) {
1647 #if CSS_SELECTOR_JIT_DEBUGGING
1648             dataLogF("%*s  Subselectors for %dn+%d:\n", level * 4, "", nthLastChildOfSelectorInfo.a, nthLastChildOfSelectorInfo.b);
1649 #endif
1650
1651             for (SelectorFragmentList& selectorList : nthLastChildOfSelectorInfo.selectorList)
1652                 computeBacktrackingInformation(selectorList, level + 1);
1653         }
1654     }
1655 }
1656
1657 inline void SelectorCodeGenerator::pushMacroAssemblerRegisters()
1658 {
1659 #if CPU(ARM_THUMB2)
1660     // r6 is tempRegister in RegisterAllocator.h and addressTempRegister in MacroAssemblerARMv7.h and must be preserved by the callee.
1661     Vector<JSC::MacroAssembler::RegisterID, 1> macroAssemblerRegisters({ JSC::ARMRegisters::r6 });
1662     m_macroAssemblerRegistersStackReferences = m_stackAllocator.push(macroAssemblerRegisters);
1663 #endif
1664 }
1665
1666 inline void SelectorCodeGenerator::popMacroAssemblerRegisters(StackAllocator& stackAllocator)
1667 {
1668 #if CPU(ARM_THUMB2)
1669     Vector<JSC::MacroAssembler::RegisterID, 1> macroAssemblerRegisters({ JSC::ARMRegisters::r6 });
1670     stackAllocator.pop(m_macroAssemblerRegistersStackReferences, macroAssemblerRegisters);
1671 #else
1672     UNUSED_PARAM(stackAllocator);
1673 #endif
1674 }
1675
1676 inline bool SelectorCodeGenerator::generatePrologue()
1677 {
1678 #if CPU(ARM64)
1679     Vector<JSC::MacroAssembler::RegisterID, 2> prologueRegisters;
1680     prologueRegisters.append(JSC::ARM64Registers::lr);
1681     prologueRegisters.append(JSC::ARM64Registers::fp);
1682     m_prologueStackReferences = m_stackAllocator.push(prologueRegisters);
1683     return true;
1684 #elif CPU(ARM_THUMB2)
1685     Vector<JSC::MacroAssembler::RegisterID, 1> prologueRegisters;
1686     prologueRegisters.append(JSC::ARMRegisters::lr);
1687     m_prologueStackReferences = m_stackAllocator.push(prologueRegisters);
1688     return true;
1689 #elif CPU(X86_64) && CSS_SELECTOR_JIT_DEBUGGING
1690     Vector<JSC::MacroAssembler::RegisterID, 1> prologueRegister;
1691     prologueRegister.append(callFrameRegister);
1692     m_prologueStackReferences = m_stackAllocator.push(prologueRegister);
1693     return true;
1694 #endif
1695     return false;
1696 }
1697
1698 inline void SelectorCodeGenerator::generateEpilogue(StackAllocator& stackAllocator)
1699 {
1700 #if CPU(ARM64)
1701     Vector<JSC::MacroAssembler::RegisterID, 2> prologueRegisters({ JSC::ARM64Registers::lr, JSC::ARM64Registers::fp });
1702     stackAllocator.pop(m_prologueStackReferences, prologueRegisters);
1703 #elif CPU(ARM_THUMB2)
1704     Vector<JSC::MacroAssembler::RegisterID, 1> prologueRegister({ JSC::ARMRegisters::lr });
1705     stackAllocator.pop(m_prologueStackReferences, prologueRegister);
1706 #elif CPU(X86_64) && CSS_SELECTOR_JIT_DEBUGGING
1707     Vector<JSC::MacroAssembler::RegisterID, 1> prologueRegister({ callFrameRegister });
1708     stackAllocator.pop(m_prologueStackReferences, prologueRegister);
1709 #else
1710     UNUSED_PARAM(stackAllocator);
1711 #endif
1712 }
1713
1714 static bool isAdjacentRelation(FragmentRelation relation)
1715 {
1716     return relation == FragmentRelation::DirectAdjacent || relation == FragmentRelation::IndirectAdjacent;
1717 }
1718
1719 static bool shouldMarkStyleIsAffectedByPreviousSibling(const SelectorFragment& fragment)
1720 {
1721     return isAdjacentRelation(fragment.relationToLeftFragment) && !isAdjacentRelation(fragment.relationToRightFragment);
1722 }
1723
1724 void SelectorCodeGenerator::generateSelectorChecker()
1725 {
1726     pushMacroAssemblerRegisters();
1727     StackAllocator earlyFailureStack = m_stackAllocator;
1728
1729     Assembler::JumpList failureOnFunctionEntry;
1730     // Test selector's pseudo element equals to requested PseudoId.
1731     if (m_selectorContext != SelectorContext::QuerySelector && m_functionType == FunctionType::SelectorCheckerWithCheckingContext) {
1732         ASSERT_WITH_MESSAGE(fragmentMatchesTheRightmostElement(m_selectorContext, m_selectorFragments.first()), "Matching pseudo elements only make sense for the rightmost fragment.");
1733         generateRequestedPseudoElementEqualsToSelectorPseudoElement(failureOnFunctionEntry, m_selectorFragments.first(), checkingContextRegister);
1734     }
1735
1736     if (m_selectorContext == SelectorContext::RuleCollector) {
1737         unsigned specificity = m_selectorFragments.staticSpecificity;
1738         if (m_functionType == FunctionType::SelectorCheckerWithCheckingContext)
1739             m_assembler.store32(Assembler::TrustedImm32(specificity), JSC::GPRInfo::argumentGPR2);
1740         else
1741             m_assembler.store32(Assembler::TrustedImm32(specificity), JSC::GPRInfo::argumentGPR1);
1742     }
1743
1744     computeBacktrackingMemoryRequirements(m_selectorFragments);
1745     unsigned availableRegisterCount = m_registerAllocator.reserveCallerSavedRegisters(m_selectorFragments.registerRequirements);
1746
1747 #if CSS_SELECTOR_JIT_DEBUGGING
1748     dataLogF("Compiling with minimum required register count %u, minimum stack space %u\n", m_selectorFragments.registerRequirements, m_selectorFragments.stackRequirements);
1749 #endif
1750
1751     // We do not want unbounded stack allocation for backtracking. Going down 8 enry points would already be incredibly inefficient.
1752     unsigned maximumBacktrackingAllocations = 8;
1753     if (m_selectorFragments.stackRequirements > maximumBacktrackingAllocations) {
1754         m_assembler.move(Assembler::TrustedImm32(0), returnRegister);
1755         popMacroAssemblerRegisters(m_stackAllocator);
1756         m_assembler.ret();
1757         return;
1758     }
1759
1760     bool needsEpilogue = generatePrologue();
1761
1762     StackAllocator::StackReferenceVector calleeSavedRegisterStackReferences;
1763     bool reservedCalleeSavedRegisters = false;
1764     ASSERT(m_selectorFragments.registerRequirements <= maximumRegisterCount);
1765     if (availableRegisterCount < m_selectorFragments.registerRequirements) {
1766         reservedCalleeSavedRegisters = true;
1767         calleeSavedRegisterStackReferences = m_stackAllocator.push(m_registerAllocator.reserveCalleeSavedRegisters(m_selectorFragments.registerRequirements - availableRegisterCount));
1768     }
1769
1770     m_registerAllocator.allocateRegister(elementAddressRegister);
1771
1772     StackAllocator::StackReference temporaryStackBase = m_stackAllocator.stackTop();
1773
1774     if (m_functionType == FunctionType::SelectorCheckerWithCheckingContext)
1775         m_checkingContextStackReference = m_stackAllocator.push(checkingContextRegister);
1776
1777     unsigned stackRequirementCount = m_selectorFragments.stackRequirements;
1778     if (m_visitedMode == VisitedMode::Visited)
1779         stackRequirementCount += 2;
1780
1781     StackAllocator::StackReferenceVector temporaryStack;
1782     if (stackRequirementCount)
1783         temporaryStack = m_stackAllocator.allocateUninitialized(stackRequirementCount);
1784
1785     if (m_visitedMode == VisitedMode::Visited) {
1786         m_lastVisitedElement = temporaryStack.takeLast();
1787         m_startElement = temporaryStack.takeLast();
1788         m_assembler.storePtr(elementAddressRegister, m_stackAllocator.addressOf(m_startElement));
1789         m_assembler.storePtr(Assembler::TrustedImmPtr(nullptr), m_stackAllocator.addressOf(m_lastVisitedElement));
1790     }
1791
1792     m_backtrackingStack = temporaryStack;
1793
1794     Assembler::JumpList failureCases;
1795     generateSelectorCheckerExcludingPseudoElements(failureCases, m_selectorFragments);
1796
1797     if (m_selectorContext != SelectorContext::QuerySelector && m_functionType == FunctionType::SelectorCheckerWithCheckingContext) {
1798         ASSERT(!m_selectorFragments.isEmpty());
1799         generateMarkPseudoStyleForPseudoElement(failureCases, m_selectorFragments.first());
1800     }
1801
1802     if (m_visitedMode == VisitedMode::Visited) {
1803         LocalRegister lastVisitedElement(m_registerAllocator);
1804         m_assembler.loadPtr(m_stackAllocator.addressOf(m_lastVisitedElement), lastVisitedElement);
1805         Assembler::Jump noLastVisitedElement = m_assembler.branchTestPtr(Assembler::Zero, lastVisitedElement);
1806         generateElementIsFirstLink(failureCases, lastVisitedElement);
1807         noLastVisitedElement.link(&m_assembler);
1808     }
1809
1810     m_registerAllocator.deallocateRegister(elementAddressRegister);
1811
1812     if (m_functionType == FunctionType::SimpleSelectorChecker) {
1813         if (temporaryStackBase == m_stackAllocator.stackTop() && !reservedCalleeSavedRegisters && !needsEpilogue) {
1814             StackAllocator successStack = m_stackAllocator;
1815             StackAllocator failureStack = m_stackAllocator;
1816
1817             ASSERT(!m_selectorFragments.stackRequirements);
1818             // Success.
1819             m_assembler.move(Assembler::TrustedImm32(1), returnRegister);
1820             popMacroAssemblerRegisters(successStack);
1821             m_assembler.ret();
1822
1823             // Failure.
1824             ASSERT_WITH_MESSAGE(failureOnFunctionEntry.empty(), "Early failure on function entry is used for pseudo element. When early failure is used, function type is SelectorCheckerWithCheckingContext.");
1825             if (!failureCases.empty()) {
1826                 failureCases.link(&m_assembler);
1827                 m_assembler.move(Assembler::TrustedImm32(0), returnRegister);
1828                 popMacroAssemblerRegisters(failureStack);
1829                 m_assembler.ret();
1830             } else
1831                 failureStack = successStack;
1832
1833             m_stackAllocator.merge(WTFMove(successStack), WTFMove(failureStack));
1834             return;
1835         }
1836     }
1837
1838     // Success.
1839     m_assembler.move(Assembler::TrustedImm32(1), returnRegister);
1840
1841     // Failure.
1842     if (!failureCases.empty()) {
1843         Assembler::Jump skipFailureCase = m_assembler.jump();
1844         failureCases.link(&m_assembler);
1845         m_assembler.move(Assembler::TrustedImm32(0), returnRegister);
1846         skipFailureCase.link(&m_assembler);
1847     }
1848
1849     if (temporaryStackBase != m_stackAllocator.stackTop())
1850         m_stackAllocator.popAndDiscardUpTo(temporaryStackBase);
1851     if (reservedCalleeSavedRegisters)
1852         m_stackAllocator.pop(calleeSavedRegisterStackReferences, m_registerAllocator.restoreCalleeSavedRegisters());
1853
1854     StackAllocator successStack = m_stackAllocator;
1855     if (needsEpilogue)
1856         generateEpilogue(successStack);
1857     popMacroAssemblerRegisters(successStack);
1858     m_assembler.ret();
1859
1860     // Early failure on function entry case.
1861     if (!failureOnFunctionEntry.empty()) {
1862         failureOnFunctionEntry.link(&m_assembler);
1863         m_assembler.move(Assembler::TrustedImm32(0), returnRegister);
1864         popMacroAssemblerRegisters(earlyFailureStack);
1865         m_assembler.ret();
1866     } else
1867         earlyFailureStack = successStack;
1868     m_stackAllocator.merge(WTFMove(successStack), WTFMove(earlyFailureStack));
1869 }
1870
1871 void SelectorCodeGenerator::generateSelectorCheckerExcludingPseudoElements(Assembler::JumpList& failureCases, const SelectorFragmentList& selectorFragmentList)
1872 {
1873     m_backtrackingLevels.append(BacktrackingLevel());
1874
1875     for (const SelectorFragment& fragment : selectorFragmentList) {
1876         switch (fragment.relationToRightFragment) {
1877         case FragmentRelation::Rightmost:
1878             generateRightmostTreeWalker(failureCases, fragment);
1879             break;
1880         case FragmentRelation::Descendant:
1881             generateAncestorTreeWalker(failureCases, fragment);
1882             break;
1883         case FragmentRelation::Child:
1884             generateParentElementTreeWalker(failureCases, fragment);
1885             break;
1886         case FragmentRelation::DirectAdjacent:
1887             generateDirectAdjacentTreeWalker(failureCases, fragment);
1888             break;
1889         case FragmentRelation::IndirectAdjacent:
1890             generateIndirectAdjacentTreeWalker(failureCases, fragment);
1891             break;
1892         }
1893         if (shouldMarkStyleIsAffectedByPreviousSibling(fragment))
1894             markElementIfResolvingStyle(elementAddressRegister, Node::flagStyleIsAffectedByPreviousSibling());
1895         generateBacktrackingTailsIfNeeded(failureCases, fragment);
1896     }
1897
1898     ASSERT(!m_backtrackingLevels.last().descendantBacktrackingStart.isValid());
1899     ASSERT(!m_backtrackingLevels.last().adjacentBacktrackingStart.isValid());
1900     m_backtrackingLevels.takeLast();
1901 }
1902
1903 void SelectorCodeGenerator::generateElementMatchesSelectorList(Assembler::JumpList& failingCases, Assembler::RegisterID elementToMatch, const SelectorList& selectorList)
1904 {
1905     ASSERT(!selectorList.isEmpty());
1906
1907     RegisterVector registersToSave;
1908
1909     // The contract is that existing registers are preserved. Two special cases are elementToMatch and elementAddressRegister
1910     // because they are used by the matcher itself.
1911     // To simplify things for now, we just always preserve them on the stack.
1912     unsigned elementToTestIndex = std::numeric_limits<unsigned>::max();
1913     bool isElementToMatchOnStack = false;
1914     if (selectorList.clobberElementAddressRegister) {
1915         if (elementToMatch != elementAddressRegister) {
1916             registersToSave.append(elementAddressRegister);
1917             registersToSave.append(elementToMatch);
1918             elementToTestIndex = 1;
1919             isElementToMatchOnStack = true;
1920         } else {
1921             registersToSave.append(elementAddressRegister);
1922             elementToTestIndex = 0;
1923         }
1924     } else if (elementToMatch != elementAddressRegister)
1925         registersToSave.append(elementAddressRegister);
1926
1927     // Next, we need to free as many registers as needed by the nested selector list.
1928     unsigned availableRegisterCount = m_registerAllocator.availableRegisterCount();
1929
1930     // Do not count elementAddressRegister, it will remain allocated.
1931     ++availableRegisterCount;
1932
1933     if (isElementToMatchOnStack)
1934         ++availableRegisterCount;
1935
1936     if (selectorList.registerRequirements > availableRegisterCount) {
1937         unsigned registerToPushCount = selectorList.registerRequirements - availableRegisterCount;
1938         for (Assembler::RegisterID registerId : m_registerAllocator.allocatedRegisters()) {
1939             if (registerId == elementAddressRegister)
1940                 continue; // Handled separately above.
1941             if (isElementToMatchOnStack && registerId == elementToMatch)
1942                 continue; // Do not push the element twice to the stack!
1943
1944             registersToSave.append(registerId);
1945
1946             --registerToPushCount;
1947             if (!registerToPushCount)
1948                 break;
1949         }
1950     }
1951
1952     StackAllocator::StackReferenceVector allocatedRegistersOnStack = m_stackAllocator.push(registersToSave);
1953     for (Assembler::RegisterID registerID : registersToSave) {
1954         if (registerID != elementAddressRegister)
1955             m_registerAllocator.deallocateRegister(registerID);
1956     }
1957
1958
1959     if (elementToMatch != elementAddressRegister)
1960         m_assembler.move(elementToMatch, elementAddressRegister);
1961
1962     Assembler::JumpList localFailureCases;
1963     if (selectorList.size() == 1) {
1964         const SelectorFragmentList& nestedSelectorFragmentList = selectorList.first();
1965         generateSelectorCheckerExcludingPseudoElements(localFailureCases, nestedSelectorFragmentList);
1966     } else {
1967         Assembler::JumpList matchFragmentList;
1968
1969         unsigned selectorListSize = selectorList.size();
1970         unsigned selectorListLastIndex = selectorListSize - 1;
1971         for (unsigned i = 0; i < selectorList.size(); ++i) {
1972             const SelectorFragmentList& nestedSelectorFragmentList = selectorList[i];
1973             Assembler::JumpList localSelectorFailureCases;
1974             generateSelectorCheckerExcludingPseudoElements(localSelectorFailureCases, nestedSelectorFragmentList);
1975             if (i != selectorListLastIndex) {
1976                 matchFragmentList.append(m_assembler.jump());
1977                 localSelectorFailureCases.link(&m_assembler);
1978
1979                 if (nestedSelectorFragmentList.clobberElementAddressRegister) {
1980                     RELEASE_ASSERT(elementToTestIndex != std::numeric_limits<unsigned>::max());
1981                     m_assembler.loadPtr(m_stackAllocator.addressOf(allocatedRegistersOnStack[elementToTestIndex]), elementAddressRegister);
1982                 }
1983             } else
1984                 localFailureCases.append(localSelectorFailureCases);
1985         }
1986         matchFragmentList.link(&m_assembler);
1987     }
1988
1989     // Finally, restore all the registers in the state they were before this selector checker.
1990     for (Assembler::RegisterID registerID : registersToSave) {
1991         if (registerID != elementAddressRegister)
1992             m_registerAllocator.allocateRegister(registerID);
1993     }
1994
1995     if (allocatedRegistersOnStack.isEmpty()) {
1996         failingCases.append(localFailureCases);
1997         return;
1998     }
1999
2000     if (localFailureCases.empty())
2001         m_stackAllocator.pop(allocatedRegistersOnStack, registersToSave);
2002     else {
2003         StackAllocator successStack = m_stackAllocator;
2004         StackAllocator failureStack = m_stackAllocator;
2005
2006         successStack.pop(allocatedRegistersOnStack, registersToSave);
2007
2008         Assembler::Jump skipFailureCase = m_assembler.jump();
2009         localFailureCases.link(&m_assembler);
2010         failureStack.pop(allocatedRegistersOnStack, registersToSave);
2011         failingCases.append(m_assembler.jump());
2012
2013         skipFailureCase.link(&m_assembler);
2014
2015         m_stackAllocator.merge(WTFMove(successStack), WTFMove(failureStack));
2016     }
2017 }
2018
2019 static inline Assembler::Jump testIsElementFlagOnNode(Assembler::ResultCondition condition, Assembler& assembler, Assembler::RegisterID nodeAddress)
2020 {
2021     return assembler.branchTest32(condition, Assembler::Address(nodeAddress, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagIsElement()));
2022 }
2023
2024 void SelectorCodeGenerator::generateRightmostTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
2025 {
2026     generateElementMatching(failureCases, failureCases, fragment);
2027 }
2028
2029 void SelectorCodeGenerator::generateWalkToParentNode(Assembler::RegisterID targetRegister)
2030 {
2031     m_assembler.loadPtr(Assembler::Address(elementAddressRegister, Node::parentNodeMemoryOffset()), targetRegister);
2032 }
2033
2034 void SelectorCodeGenerator::generateWalkToParentElement(Assembler::JumpList& failureCases, Assembler::RegisterID targetRegister)
2035 {
2036     //    ContainerNode* parent = parentNode()
2037     //    if (!parent || !parent->isElementNode())
2038     //         failure
2039     generateWalkToParentNode(targetRegister);
2040     failureCases.append(m_assembler.branchTestPtr(Assembler::Zero, targetRegister));
2041     failureCases.append(testIsElementFlagOnNode(Assembler::Zero, m_assembler, targetRegister));
2042 }
2043
2044 void SelectorCodeGenerator::generateParentElementTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
2045 {
2046     Assembler::JumpList traversalFailureCases;
2047     generateWalkToParentElement(traversalFailureCases, elementAddressRegister);
2048     linkFailures(failureCases, fragment.traversalBacktrackingAction, traversalFailureCases);
2049
2050     Assembler::JumpList matchingTagNameFailureCases;
2051     Assembler::JumpList matchingPostTagNameFailureCases;
2052     generateElementMatching(matchingTagNameFailureCases, matchingPostTagNameFailureCases, fragment);
2053     linkFailures(failureCases, fragment.matchingTagNameBacktrackingAction, matchingTagNameFailureCases);
2054     linkFailures(failureCases, fragment.matchingPostTagNameBacktrackingAction, matchingPostTagNameFailureCases);
2055
2056     if (fragment.backtrackingFlags & BacktrackingFlag::SaveDescendantBacktrackingStart) {
2057         if (!m_descendantBacktrackingStartInUse) {
2058             m_descendantBacktrackingStart = m_registerAllocator.allocateRegister();
2059             m_assembler.move(elementAddressRegister, m_descendantBacktrackingStart);
2060             m_descendantBacktrackingStartInUse = true;
2061         } else {
2062             BacktrackingLevel& currentBacktrackingLevel = m_backtrackingLevels.last();
2063             ASSERT(!currentBacktrackingLevel.descendantBacktrackingStart.isValid());
2064             currentBacktrackingLevel.descendantBacktrackingStart = m_backtrackingStack.takeLast();
2065
2066             m_assembler.storePtr(elementAddressRegister, m_stackAllocator.addressOf(currentBacktrackingLevel.descendantBacktrackingStart));
2067         }
2068     }
2069 }
2070
2071 void SelectorCodeGenerator::generateAncestorTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
2072 {
2073     // Loop over the ancestors until one of them matches the fragment.
2074     Assembler::Label loopStart(m_assembler.label());
2075
2076     if (fragment.backtrackingFlags & BacktrackingFlag::DescendantEntryPoint)
2077         m_backtrackingLevels.last().descendantTreeWalkerBacktrackingPoint = m_assembler.label();
2078
2079     generateWalkToParentElement(failureCases, elementAddressRegister);
2080
2081     if (fragment.backtrackingFlags & BacktrackingFlag::DescendantEntryPoint)
2082         m_backtrackingLevels.last().descendantEntryPoint = m_assembler.label();
2083
2084     Assembler::JumpList matchingFailureCases;
2085     generateElementMatching(matchingFailureCases, matchingFailureCases, fragment);
2086     matchingFailureCases.linkTo(loopStart, &m_assembler);
2087 }
2088
2089 inline void SelectorCodeGenerator::generateWalkToNextAdjacentElement(Assembler::JumpList& failureCases, Assembler::RegisterID workRegister)
2090 {
2091     Assembler::Label loopStart = m_assembler.label();
2092     m_assembler.loadPtr(Assembler::Address(workRegister, Node::nextSiblingMemoryOffset()), workRegister);
2093     failureCases.append(m_assembler.branchTestPtr(Assembler::Zero, workRegister));
2094     testIsElementFlagOnNode(Assembler::Zero, m_assembler, workRegister).linkTo(loopStart, &m_assembler);
2095 }
2096
2097 inline void SelectorCodeGenerator::generateWalkToPreviousAdjacentElement(Assembler::JumpList& failureCases, Assembler::RegisterID workRegister)
2098 {
2099     Assembler::Label loopStart = m_assembler.label();
2100     m_assembler.loadPtr(Assembler::Address(workRegister, Node::previousSiblingMemoryOffset()), workRegister);
2101     failureCases.append(m_assembler.branchTestPtr(Assembler::Zero, workRegister));
2102     testIsElementFlagOnNode(Assembler::Zero, m_assembler, workRegister).linkTo(loopStart, &m_assembler);
2103 }
2104
2105 void SelectorCodeGenerator::generateWalkToPreviousAdjacent(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
2106 {
2107     //    do {
2108     //        previousSibling = previousSibling->previousSibling();
2109     //        if (!previousSibling)
2110     //            failure!
2111     //    while (!previousSibling->isElement());
2112     Assembler::RegisterID previousSibling;
2113     bool useTailOnTraversalFailure = fragment.traversalBacktrackingAction >= BacktrackingAction::JumpToDescendantTail;
2114     if (!useTailOnTraversalFailure) {
2115         // If the current fragment is not dependant on a previously saved elementAddressRegister, a fast recover
2116         // from a failure would resume with elementAddressRegister.
2117         // When walking to the previous sibling, the failure can be that previousSibling is null. We cannot backtrack
2118         // with a null elementAddressRegister so we do the traversal on a copy.
2119         previousSibling = m_registerAllocator.allocateRegister();
2120         m_assembler.move(elementAddressRegister, previousSibling);
2121     } else
2122         previousSibling = elementAddressRegister;
2123
2124     Assembler::JumpList traversalFailureCases;
2125     generateWalkToPreviousAdjacentElement(traversalFailureCases, previousSibling);
2126     linkFailures(failureCases, fragment.traversalBacktrackingAction, traversalFailureCases);
2127
2128     // On success, move previousSibling over to elementAddressRegister if we could not work on elementAddressRegister directly.
2129     if (!useTailOnTraversalFailure) {
2130         m_assembler.move(previousSibling, elementAddressRegister);
2131         m_registerAllocator.deallocateRegister(previousSibling);
2132     }
2133 }
2134
2135 void SelectorCodeGenerator::generateDirectAdjacentTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
2136 {
2137     generateWalkToPreviousAdjacent(failureCases, fragment);
2138     markElementIfResolvingStyle(elementAddressRegister, Node::flagAffectsNextSiblingElementStyle());
2139
2140     Assembler::JumpList matchingTagNameFailureCases;
2141     Assembler::JumpList matchingPostTagNameFailureCases;
2142     generateElementMatching(matchingTagNameFailureCases, matchingPostTagNameFailureCases, fragment);
2143     linkFailures(failureCases, fragment.matchingTagNameBacktrackingAction, matchingTagNameFailureCases);
2144     linkFailures(failureCases, fragment.matchingPostTagNameBacktrackingAction, matchingPostTagNameFailureCases);
2145
2146     if (fragment.backtrackingFlags & BacktrackingFlag::SaveAdjacentBacktrackingStart) {
2147         BacktrackingLevel& currentBacktrackingLevel = m_backtrackingLevels.last();
2148         ASSERT(!currentBacktrackingLevel.adjacentBacktrackingStart.isValid());
2149         currentBacktrackingLevel.adjacentBacktrackingStart = m_backtrackingStack.takeLast();
2150
2151         m_assembler.storePtr(elementAddressRegister, m_stackAllocator.addressOf(currentBacktrackingLevel.adjacentBacktrackingStart));
2152     }
2153 }
2154
2155 void SelectorCodeGenerator::generateIndirectAdjacentTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
2156 {
2157     Assembler::Label loopStart(m_assembler.label());
2158
2159     if (fragment.backtrackingFlags & BacktrackingFlag::IndirectAdjacentEntryPoint)
2160         m_backtrackingLevels.last().indirectAdjacentTreeWalkerBacktrackingPoint = m_assembler.label();
2161
2162     generateWalkToPreviousAdjacent(failureCases, fragment);
2163     markElementIfResolvingStyle(elementAddressRegister, Node::flagAffectsNextSiblingElementStyle());
2164
2165     if (fragment.backtrackingFlags & BacktrackingFlag::IndirectAdjacentEntryPoint)
2166         m_backtrackingLevels.last().indirectAdjacentEntryPoint = m_assembler.label();
2167
2168     Assembler::JumpList localFailureCases;
2169     generateElementMatching(localFailureCases, localFailureCases, fragment);
2170     localFailureCases.linkTo(loopStart, &m_assembler);
2171 }
2172
2173
2174 void SelectorCodeGenerator::addFlagsToElementStyleFromContext(Assembler::RegisterID checkingContext, int64_t newFlag)
2175 {
2176     ASSERT(m_selectorContext != SelectorContext::QuerySelector);
2177
2178     LocalRegister childStyle(m_registerAllocator);
2179     m_assembler.loadPtr(Assembler::Address(checkingContext, OBJECT_OFFSETOF(SelectorChecker::CheckingContext, elementStyle)), childStyle);
2180
2181     // FIXME: We should look into doing something smart in MacroAssembler instead.
2182     Assembler::Address flagAddress(childStyle, RenderStyle::noninheritedFlagsMemoryOffset() + RenderStyle::NonInheritedFlags::flagsMemoryOffset());
2183 #if CPU(ARM_THUMB2)
2184     int32_t flagLowBits = newFlag & 0xffffffff;
2185     int32_t flagHighBits = newFlag >> 32;
2186     if (flagLowBits)
2187         m_assembler.or32(Assembler::TrustedImm32(flagLowBits), flagAddress);
2188     if (flagHighBits) {
2189         Assembler::Address flagHighAddress = flagAddress.withOffset(4);
2190         m_assembler.or32(Assembler::TrustedImm32(flagHighBits), flagHighAddress);
2191     }
2192 #elif CPU(X86_64) || CPU(ARM64)
2193     LocalRegister flags(m_registerAllocator);
2194     m_assembler.load64(flagAddress, flags);
2195     LocalRegister isFirstChildStateFlagImmediate(m_registerAllocator);
2196     m_assembler.move(Assembler::TrustedImm64(newFlag), isFirstChildStateFlagImmediate);
2197     m_assembler.or64(isFirstChildStateFlagImmediate, flags);
2198     m_assembler.store64(flags, flagAddress);
2199 #else
2200 #error SelectorCodeGenerator::addFlagsToElementStyleFromContext not implemented for this architecture.
2201 #endif
2202 }
2203
2204 Assembler::JumpList SelectorCodeGenerator::jumpIfNoPreviousAdjacentElement()
2205 {
2206     Assembler::JumpList successCase;
2207     LocalRegister previousSibling(m_registerAllocator);
2208     m_assembler.move(elementAddressRegister, previousSibling);
2209     generateWalkToPreviousAdjacentElement(successCase, previousSibling);
2210     return successCase;
2211 }
2212
2213 Assembler::JumpList SelectorCodeGenerator::jumpIfNoNextAdjacentElement()
2214 {
2215     Assembler::JumpList successCase;
2216     LocalRegister nextSibling(m_registerAllocator);
2217     m_assembler.move(elementAddressRegister, nextSibling);
2218     generateWalkToNextAdjacentElement(successCase, nextSibling);
2219     return successCase;
2220 }
2221
2222
2223 void SelectorCodeGenerator::loadCheckingContext(Assembler::RegisterID checkingContext)
2224 {
2225     // Get the checking context.
2226     RELEASE_ASSERT(m_functionType == FunctionType::SelectorCheckerWithCheckingContext);
2227     m_assembler.loadPtr(m_stackAllocator.addressOf(m_checkingContextStackReference), checkingContext);
2228 }
2229
2230 Assembler::Jump SelectorCodeGenerator::branchOnResolvingModeWithCheckingContext(Assembler::RelationalCondition condition, SelectorChecker::Mode mode, Assembler::RegisterID checkingContext)
2231 {
2232     // Depend on the specified resolving mode and our current mode, branch.
2233     static_assert(sizeof(SelectorChecker::Mode) == 1, "We generate a byte load/test for the SelectorChecker::Mode.");
2234     return m_assembler.branch8(condition, Assembler::Address(checkingContext, OBJECT_OFFSETOF(SelectorChecker::CheckingContext, resolvingMode)), Assembler::TrustedImm32(static_cast<std::underlying_type<SelectorChecker::Mode>::type>(mode)));
2235
2236 }
2237
2238 Assembler::Jump SelectorCodeGenerator::branchOnResolvingMode(Assembler::RelationalCondition condition, SelectorChecker::Mode mode, Assembler::RegisterID checkingContext)
2239 {
2240     loadCheckingContext(checkingContext);
2241     return branchOnResolvingModeWithCheckingContext(condition, mode, checkingContext);
2242 }
2243
2244 Assembler::Jump SelectorCodeGenerator::jumpIfNotResolvingStyle(Assembler::RegisterID checkingContext)
2245 {
2246     return branchOnResolvingMode(Assembler::NotEqual, SelectorChecker::Mode::ResolvingStyle, checkingContext);
2247 }
2248
2249 static void getDocument(Assembler& assembler, Assembler::RegisterID element, Assembler::RegisterID output)
2250 {
2251     assembler.loadPtr(Assembler::Address(element, Node::treeScopeMemoryOffset()), output);
2252     assembler.loadPtr(Assembler::Address(output, TreeScope::documentScopeMemoryOffset()), output);
2253 }
2254
2255 void SelectorCodeGenerator::generateSpecialFailureInQuirksModeForActiveAndHoverIfNeeded(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
2256 {
2257     if (fragment.onlyMatchesLinksInQuirksMode) {
2258         // If the element is a link, it can always match :hover or :active.
2259         Assembler::Jump isLink = m_assembler.branchTest32(Assembler::NonZero, Assembler::Address(elementAddressRegister, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagIsLink()));
2260
2261         // Only quirks mode restrict :hover and :active.
2262         static_assert(sizeof(DocumentCompatibilityMode) == 1, "We generate a byte load/test for the compatibility mode.");
2263         LocalRegister documentAddress(m_registerAllocator);
2264         getDocument(m_assembler, elementAddressRegister, documentAddress);
2265         failureCases.append(m_assembler.branchTest8(Assembler::NonZero, Assembler::Address(documentAddress, Document::compatibilityModeMemoryOffset()), Assembler::TrustedImm32(static_cast<std::underlying_type<DocumentCompatibilityMode>::type>(DocumentCompatibilityMode::QuirksMode))));
2266
2267         isLink.link(&m_assembler);
2268     }
2269 }
2270
2271 #if CPU(ARM_THUMB2) && !CPU(APPLE_ARMV7S)
2272 // FIXME: This could be implemented in assembly to avoid a function call, and we know the divisor at jit-compile time.
2273 static int moduloHelper(int dividend, int divisor)
2274 {
2275     return dividend % divisor;
2276 }
2277 #endif
2278
2279 // The value in inputDividend is destroyed by the modulo operation.
2280 Assembler::Jump SelectorCodeGenerator::modulo(Assembler::ResultCondition condition, Assembler::RegisterID inputDividend, int divisor)
2281 {
2282     RELEASE_ASSERT(divisor);
2283 #if CPU(ARM64) || CPU(APPLE_ARMV7S)
2284     LocalRegister divisorRegister(m_registerAllocator);
2285     m_assembler.move(Assembler::TrustedImm32(divisor), divisorRegister);
2286
2287     LocalRegister resultRegister(m_registerAllocator);
2288     m_assembler.m_assembler.sdiv<32>(resultRegister, inputDividend, divisorRegister);
2289     m_assembler.mul32(divisorRegister, resultRegister);
2290     return m_assembler.branchSub32(condition, inputDividend, resultRegister, resultRegister);
2291 #elif CPU(ARM_THUMB2) && !CPU(APPLE_ARMV7S)
2292     LocalRegisterWithPreference divisorRegister(m_registerAllocator, JSC::GPRInfo::argumentGPR1);
2293     m_assembler.move(Assembler::TrustedImm32(divisor), divisorRegister);
2294     FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2295     functionCall.setFunctionAddress(moduloHelper);
2296     functionCall.setTwoArguments(inputDividend, divisorRegister);
2297     return functionCall.callAndBranchOnBooleanReturnValue(condition);
2298 #elif CPU(X86_64)
2299     // idiv takes RAX + an arbitrary register, and return RAX + RDX. Most of this code is about doing
2300     // an efficient allocation of those registers. If a register is already in use and is not the inputDividend,
2301     // we first try to copy it to a temporary register, it that is not possible we fall back to the stack.
2302     enum class RegisterAllocationType {
2303         External,
2304         AllocatedLocally,
2305         CopiedToTemporary,
2306         PushedToStack
2307     };
2308
2309     // 1) Get RAX and RDX.
2310     // If they are already used, push them to the stack.
2311     Assembler::RegisterID dividend = JSC::X86Registers::eax;
2312     RegisterAllocationType dividendAllocation = RegisterAllocationType::External;
2313     StackAllocator::StackReference temporaryDividendStackReference;
2314     Assembler::RegisterID temporaryDividendCopy = InvalidGPRReg;
2315     if (inputDividend != dividend) {
2316         bool registerIsInUse = m_registerAllocator.allocatedRegisters().contains(dividend);
2317         if (registerIsInUse) {
2318             if (m_registerAllocator.availableRegisterCount() > 1) {
2319                 temporaryDividendCopy = m_registerAllocator.allocateRegister();
2320                 m_assembler.move(dividend, temporaryDividendCopy);
2321                 dividendAllocation = RegisterAllocationType::CopiedToTemporary;
2322             } else {
2323                 temporaryDividendStackReference = m_stackAllocator.push(dividend);
2324                 dividendAllocation = RegisterAllocationType::PushedToStack;
2325             }
2326         } else {
2327             m_registerAllocator.allocateRegister(dividend);
2328             dividendAllocation = RegisterAllocationType::AllocatedLocally;
2329         }
2330         m_assembler.move(inputDividend, dividend);
2331     }
2332
2333     Assembler::RegisterID remainder = JSC::X86Registers::edx;
2334     RegisterAllocationType remainderAllocation = RegisterAllocationType::External;
2335     StackAllocator::StackReference temporaryRemainderStackReference;
2336     Assembler::RegisterID temporaryRemainderCopy = InvalidGPRReg;
2337     if (inputDividend != remainder) {
2338         bool registerIsInUse = m_registerAllocator.allocatedRegisters().contains(remainder);
2339         if (registerIsInUse) {
2340             if (m_registerAllocator.availableRegisterCount() > 1) {
2341                 temporaryRemainderCopy = m_registerAllocator.allocateRegister();
2342                 m_assembler.move(remainder, temporaryRemainderCopy);
2343                 remainderAllocation = RegisterAllocationType::CopiedToTemporary;
2344             } else {
2345                 temporaryRemainderStackReference = m_stackAllocator.push(remainder);
2346                 remainderAllocation = RegisterAllocationType::PushedToStack;
2347             }
2348         } else {
2349             m_registerAllocator.allocateRegister(remainder);
2350             remainderAllocation = RegisterAllocationType::AllocatedLocally;
2351         }
2352     }
2353
2354     // If the input register is used by idiv, save its value to restore it after the operation.
2355     Assembler::RegisterID inputDividendCopy;
2356     StackAllocator::StackReference pushedInputDividendStackReference;
2357     RegisterAllocationType savedInputDividendAllocationType = RegisterAllocationType::External;
2358     if (inputDividend == dividend || inputDividend == remainder) {
2359         if (m_registerAllocator.availableRegisterCount() > 1) {
2360             inputDividendCopy = m_registerAllocator.allocateRegister();
2361             m_assembler.move(inputDividend, inputDividendCopy);
2362             savedInputDividendAllocationType = RegisterAllocationType::CopiedToTemporary;
2363         } else {
2364             pushedInputDividendStackReference = m_stackAllocator.push(inputDividend);
2365             savedInputDividendAllocationType = RegisterAllocationType::PushedToStack;
2366         }
2367     }
2368
2369     m_assembler.m_assembler.cdq();
2370
2371     // 2) Perform the division with idiv.
2372     {
2373         LocalRegister divisorRegister(m_registerAllocator);
2374         m_assembler.move(Assembler::TrustedImm64(divisor), divisorRegister);
2375         m_assembler.m_assembler.idivl_r(divisorRegister);
2376         m_assembler.test32(condition, remainder);
2377     }
2378
2379     // 3) Return RAX and RDX.
2380     if (remainderAllocation == RegisterAllocationType::AllocatedLocally)
2381         m_registerAllocator.deallocateRegister(remainder);
2382     else if (remainderAllocation == RegisterAllocationType::CopiedToTemporary) {
2383         m_assembler.move(temporaryRemainderCopy, remainder);
2384         m_registerAllocator.deallocateRegister(temporaryRemainderCopy);
2385     } else if (remainderAllocation == RegisterAllocationType::PushedToStack)
2386         m_stackAllocator.pop(temporaryRemainderStackReference, remainder);
2387
2388     if (dividendAllocation == RegisterAllocationType::AllocatedLocally)
2389         m_registerAllocator.deallocateRegister(dividend);
2390     else if (dividendAllocation == RegisterAllocationType::CopiedToTemporary) {
2391         m_assembler.move(temporaryDividendCopy, dividend);
2392         m_registerAllocator.deallocateRegister(temporaryDividendCopy);
2393     } else if (dividendAllocation == RegisterAllocationType::PushedToStack)
2394         m_stackAllocator.pop(temporaryDividendStackReference, dividend);
2395
2396     if (savedInputDividendAllocationType != RegisterAllocationType::External) {
2397         if (savedInputDividendAllocationType == RegisterAllocationType::CopiedToTemporary) {
2398             m_assembler.move(inputDividendCopy, inputDividend);
2399             m_registerAllocator.deallocateRegister(inputDividendCopy);
2400         } else if (savedInputDividendAllocationType == RegisterAllocationType::PushedToStack)
2401             m_stackAllocator.pop(pushedInputDividendStackReference, inputDividend);
2402     }
2403
2404     // 4) Branch on the test.
2405     return m_assembler.branch(condition);
2406 #else
2407 #error Modulo is not implemented for this architecture.
2408 #endif
2409 }
2410
2411 void SelectorCodeGenerator::moduloIsZero(Assembler::JumpList& failureCases, Assembler::RegisterID inputDividend, int divisor)
2412 {
2413     if (divisor == 1 || divisor == -1)
2414         return;
2415     if (divisor == 2 || divisor == -2) {
2416         failureCases.append(m_assembler.branchTest32(Assembler::NonZero, inputDividend, Assembler::TrustedImm32(1)));
2417         return;
2418     }
2419
2420     failureCases.append(modulo(Assembler::NonZero, inputDividend, divisor));
2421 }
2422
2423 static void setNodeFlag(Assembler& assembler, Assembler::RegisterID elementAddress, int32_t flag)
2424 {
2425     assembler.or32(Assembler::TrustedImm32(flag), Assembler::Address(elementAddress, Node::nodeFlagsMemoryOffset()));
2426 }
2427
2428 void SelectorCodeGenerator::markElementIfResolvingStyle(Assembler::RegisterID element, int32_t nodeFlag)
2429 {
2430     if (m_selectorContext == SelectorContext::QuerySelector)
2431         return;
2432
2433     Assembler::JumpList skipMarking;
2434     {
2435         LocalRegister checkingContext(m_registerAllocator);
2436         skipMarking.append(jumpIfNotResolvingStyle(checkingContext));
2437     }
2438
2439     setNodeFlag(m_assembler, element, nodeFlag);
2440
2441     skipMarking.link(&m_assembler);
2442 }
2443
2444 void SelectorCodeGenerator::linkFailures(Assembler::JumpList& globalFailureCases, BacktrackingAction backtrackingAction, Assembler::JumpList& localFailureCases)
2445 {
2446     switch (backtrackingAction) {
2447     case BacktrackingAction::NoBacktracking:
2448         globalFailureCases.append(localFailureCases);
2449         break;
2450     case BacktrackingAction::JumpToDescendantEntryPoint:
2451         localFailureCases.linkTo(m_backtrackingLevels.last().descendantEntryPoint, &m_assembler);
2452         break;
2453     case BacktrackingAction::JumpToDescendantTreeWalkerEntryPoint:
2454         localFailureCases.linkTo(m_backtrackingLevels.last().descendantTreeWalkerBacktrackingPoint, &m_assembler);
2455         break;
2456     case BacktrackingAction::JumpToDescendantTail:
2457         m_backtrackingLevels.last().descendantBacktrackingFailureCases.append(localFailureCases);
2458         break;
2459     case BacktrackingAction::JumpToIndirectAdjacentEntryPoint:
2460         localFailureCases.linkTo(m_backtrackingLevels.last().indirectAdjacentEntryPoint, &m_assembler);
2461         break;
2462     case BacktrackingAction::JumpToIndirectAdjacentTreeWalkerEntryPoint:
2463         localFailureCases.linkTo(m_backtrackingLevels.last().indirectAdjacentTreeWalkerBacktrackingPoint, &m_assembler);
2464         break;
2465     case BacktrackingAction::JumpToDirectAdjacentTail:
2466         m_backtrackingLevels.last().adjacentBacktrackingFailureCases.append(localFailureCases);
2467         break;
2468     }
2469 }
2470
2471 void SelectorCodeGenerator::generateAdjacentBacktrackingTail()
2472 {
2473     // Recovering tail.
2474     m_backtrackingLevels.last().adjacentBacktrackingFailureCases.link(&m_assembler);
2475     m_backtrackingLevels.last().adjacentBacktrackingFailureCases.clear();
2476
2477     BacktrackingLevel& currentBacktrackingLevel = m_backtrackingLevels.last();
2478     m_assembler.loadPtr(m_stackAllocator.addressOf(currentBacktrackingLevel.adjacentBacktrackingStart), elementAddressRegister);
2479     m_backtrackingStack.append(currentBacktrackingLevel.adjacentBacktrackingStart);
2480     currentBacktrackingLevel.adjacentBacktrackingStart = StackAllocator::StackReference();
2481
2482     m_assembler.jump(m_backtrackingLevels.last().indirectAdjacentEntryPoint);
2483 }
2484
2485 void SelectorCodeGenerator::generateDescendantBacktrackingTail()
2486 {
2487     m_backtrackingLevels.last().descendantBacktrackingFailureCases.link(&m_assembler);
2488     m_backtrackingLevels.last().descendantBacktrackingFailureCases.clear();
2489
2490     BacktrackingLevel& currentBacktrackingLevel = m_backtrackingLevels.last();
2491     if (!currentBacktrackingLevel.descendantBacktrackingStart.isValid()) {
2492         m_assembler.move(m_descendantBacktrackingStart, elementAddressRegister);
2493         m_registerAllocator.deallocateRegister(m_descendantBacktrackingStart);
2494         m_descendantBacktrackingStartInUse = false;
2495     } else {
2496         m_assembler.loadPtr(m_stackAllocator.addressOf(currentBacktrackingLevel.descendantBacktrackingStart), elementAddressRegister);
2497         m_backtrackingStack.append(currentBacktrackingLevel.descendantBacktrackingStart);
2498         currentBacktrackingLevel.descendantBacktrackingStart = StackAllocator::StackReference();
2499     }
2500
2501     m_assembler.jump(m_backtrackingLevels.last().descendantEntryPoint);
2502 }
2503
2504 void SelectorCodeGenerator::generateBacktrackingTailsIfNeeded(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
2505 {
2506     if (fragment.backtrackingFlags & BacktrackingFlag::DirectAdjacentTail && fragment.backtrackingFlags & BacktrackingFlag::DescendantTail) {
2507         Assembler::Jump normalCase = m_assembler.jump();
2508         generateAdjacentBacktrackingTail();
2509         generateDescendantBacktrackingTail();
2510         normalCase.link(&m_assembler);
2511     } else if (fragment.backtrackingFlags & BacktrackingFlag::DirectAdjacentTail) {
2512         Assembler::Jump normalCase = m_assembler.jump();
2513         generateAdjacentBacktrackingTail();
2514         failureCases.append(m_assembler.jump());
2515         normalCase.link(&m_assembler);
2516     } else if (fragment.backtrackingFlags & BacktrackingFlag::DescendantTail) {
2517         Assembler::Jump normalCase = m_assembler.jump();
2518         generateDescendantBacktrackingTail();
2519         normalCase.link(&m_assembler);
2520     }
2521 }
2522
2523 void SelectorCodeGenerator::generateElementMatching(Assembler::JumpList& matchingTagNameFailureCases, Assembler::JumpList& matchingPostTagNameFailureCases, const SelectorFragment& fragment)
2524 {
2525     if (fragment.tagNameSelector)
2526         generateElementHasTagName(matchingTagNameFailureCases, *(fragment.tagNameSelector));
2527
2528     generateElementLinkMatching(matchingPostTagNameFailureCases, fragment);
2529
2530     if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassRoot))
2531         generateElementIsRoot(matchingPostTagNameFailureCases);
2532
2533     if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassScope))
2534         generateElementIsScopeRoot(matchingPostTagNameFailureCases);
2535
2536     if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassTarget))
2537         generateElementIsTarget(matchingPostTagNameFailureCases);
2538
2539     for (unsigned i = 0; i < fragment.unoptimizedPseudoClasses.size(); ++i)
2540         generateElementFunctionCallTest(matchingPostTagNameFailureCases, fragment.unoptimizedPseudoClasses[i]);
2541
2542     for (unsigned i = 0; i < fragment.unoptimizedPseudoClassesWithContext.size(); ++i)
2543         generateContextFunctionCallTest(matchingPostTagNameFailureCases, fragment.unoptimizedPseudoClassesWithContext[i]);
2544
2545     generateElementDataMatching(matchingPostTagNameFailureCases, fragment);
2546
2547     if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassActive))
2548         generateElementIsActive(matchingPostTagNameFailureCases, fragment);
2549     if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassEmpty))
2550         generateElementIsEmpty(matchingPostTagNameFailureCases, fragment);
2551     if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassHover))
2552         generateElementIsHovered(matchingPostTagNameFailureCases, fragment);
2553     if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassOnlyChild))
2554         generateElementIsOnlyChild(matchingPostTagNameFailureCases, fragment);
2555     if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassPlaceholderShown))
2556         generateElementHasPlaceholderShown(matchingPostTagNameFailureCases, fragment);
2557     if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassFirstChild))
2558         generateElementIsFirstChild(matchingPostTagNameFailureCases, fragment);
2559     if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassLastChild))
2560         generateElementIsLastChild(matchingPostTagNameFailureCases, fragment);
2561     if (!fragment.nthChildFilters.isEmpty())
2562         generateElementIsNthChild(matchingPostTagNameFailureCases, fragment);
2563     if (!fragment.nthLastChildFilters.isEmpty())
2564         generateElementIsNthLastChild(matchingPostTagNameFailureCases, fragment);
2565     if (!fragment.notFilters.isEmpty())
2566         generateElementMatchesNotPseudoClass(matchingPostTagNameFailureCases, fragment);
2567     if (!fragment.anyFilters.isEmpty())
2568         generateElementMatchesAnyPseudoClass(matchingPostTagNameFailureCases, fragment);
2569     if (!fragment.matchesFilters.isEmpty())
2570         generateElementMatchesMatchesPseudoClass(matchingPostTagNameFailureCases, fragment);
2571     if (!fragment.languageArgumentsList.isEmpty())
2572         generateElementIsInLanguage(matchingPostTagNameFailureCases, fragment);
2573     if (!fragment.nthChildOfFilters.isEmpty())
2574         generateElementIsNthChildOf(matchingPostTagNameFailureCases, fragment);
2575     if (!fragment.nthLastChildOfFilters.isEmpty())
2576         generateElementIsNthLastChildOf(matchingPostTagNameFailureCases, fragment);
2577     if (fragment.pseudoElementSelector)
2578         generateElementHasPseudoElement(matchingPostTagNameFailureCases, fragment);
2579
2580     // Reach here when the generateElementMatching matching succeeded.
2581     // Only when the matching succeeeded, the last visited element should be stored and checked at the end of the whole matching.
2582     if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassVisited))
2583         generateStoreLastVisitedElement(elementAddressRegister);
2584 }
2585
2586 void SelectorCodeGenerator::generateElementDataMatching(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
2587 {
2588     if (!fragment.id && fragment.classNames.isEmpty() && fragment.attributes.isEmpty())
2589         return;
2590
2591     //  Generate:
2592     //     elementDataAddress = element->elementData();
2593     //     if (!elementDataAddress)
2594     //         failure!
2595     LocalRegister elementDataAddress(m_registerAllocator);
2596     m_assembler.loadPtr(Assembler::Address(elementAddressRegister, Element::elementDataMemoryOffset()), elementDataAddress);
2597     failureCases.append(m_assembler.branchTestPtr(Assembler::Zero, elementDataAddress));
2598
2599     if (fragment.id)
2600         generateElementHasId(failureCases, elementDataAddress, *fragment.id);
2601     if (!fragment.classNames.isEmpty())
2602         generateElementHasClasses(failureCases, elementDataAddress, fragment.classNames);
2603     if (!fragment.attributes.isEmpty())
2604         generateElementAttributesMatching(failureCases, elementDataAddress, fragment);
2605 }
2606
2607 void SelectorCodeGenerator::generateElementLinkMatching(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
2608 {
2609     if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassLink)
2610         || fragment.pseudoClasses.contains(CSSSelector::PseudoClassAnyLink)
2611         || fragment.pseudoClasses.contains(CSSSelector::PseudoClassVisited))
2612         generateElementIsLink(failureCases);
2613 }
2614
2615 static inline Assembler::Jump testIsHTMLFlagOnNode(Assembler::ResultCondition condition, Assembler& assembler, Assembler::RegisterID nodeAddress)
2616 {
2617     return assembler.branchTest32(condition, Assembler::Address(nodeAddress, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagIsHTML()));
2618 }
2619
2620 static inline bool canMatchStyleAttribute(const SelectorFragment& fragment)
2621 {
2622     for (unsigned i = 0; i < fragment.attributes.size(); ++i) {
2623         const CSSSelector& attributeSelector = fragment.attributes[i].selector();
2624         const QualifiedName& attributeName = attributeSelector.attribute();
2625         if (Attribute::nameMatchesFilter(HTMLNames::styleAttr, attributeName.prefix(), attributeName.localName(), attributeName.namespaceURI()))
2626             return true;
2627
2628         const AtomicString& canonicalLocalName = attributeSelector.attributeCanonicalLocalName();
2629         if (attributeName.localName() != canonicalLocalName
2630             && Attribute::nameMatchesFilter(HTMLNames::styleAttr, attributeName.prefix(), attributeSelector.attributeCanonicalLocalName(), attributeName.namespaceURI())) {
2631             return true;
2632         }
2633     }
2634     return false;
2635 }
2636
2637 void SelectorCodeGenerator::generateSynchronizeStyleAttribute(Assembler::RegisterID elementDataArraySizeAndFlags)
2638 {
2639     // The style attribute is updated lazily based on the flag styleAttributeIsDirty.
2640     Assembler::Jump styleAttributeNotDirty = m_assembler.branchTest32(Assembler::Zero, elementDataArraySizeAndFlags, Assembler::TrustedImm32(ElementData::styleAttributeIsDirtyFlag()));
2641
2642     FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2643     functionCall.setFunctionAddress(StyledElement::synchronizeStyleAttributeInternal);
2644     Assembler::RegisterID elementAddress = elementAddressRegister;
2645     functionCall.setOneArgument(elementAddress);
2646     functionCall.call();
2647
2648     styleAttributeNotDirty.link(&m_assembler);
2649 }
2650
2651 static inline bool canMatchAnimatableSVGAttribute(const SelectorFragment& fragment)
2652 {
2653     for (unsigned i = 0; i < fragment.attributes.size(); ++i) {
2654         const CSSSelector& attributeSelector = fragment.attributes[i].selector();
2655         const QualifiedName& selectorAttributeName = attributeSelector.attribute();
2656
2657         const QualifiedName& candidateForLocalName = SVGElement::animatableAttributeForName(selectorAttributeName.localName());
2658         if (Attribute::nameMatchesFilter(candidateForLocalName, selectorAttributeName.prefix(), selectorAttributeName.localName(), selectorAttributeName.namespaceURI()))
2659             return true;
2660
2661         const AtomicString& canonicalLocalName = attributeSelector.attributeCanonicalLocalName();
2662         if (selectorAttributeName.localName() != canonicalLocalName) {
2663             const QualifiedName& candidateForCanonicalLocalName = SVGElement::animatableAttributeForName(selectorAttributeName.localName());
2664             if (Attribute::nameMatchesFilter(candidateForCanonicalLocalName, selectorAttributeName.prefix(), selectorAttributeName.localName(), selectorAttributeName.namespaceURI()))
2665                 return true;
2666         }
2667     }
2668     return false;
2669 }
2670
2671 void SelectorCodeGenerator::generateSynchronizeAllAnimatedSVGAttribute(Assembler::RegisterID elementDataArraySizeAndFlags)
2672 {
2673     // SVG attributes can be updated lazily depending on the flag AnimatedSVGAttributesAreDirty. We need to check
2674     // that first.
2675     Assembler::Jump animatedSVGAttributesNotDirty = m_assembler.branchTest32(Assembler::Zero, elementDataArraySizeAndFlags, Assembler::TrustedImm32(ElementData::animatedSVGAttributesAreDirtyFlag()));
2676
2677     FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2678     functionCall.setFunctionAddress(SVGElement::synchronizeAllAnimatedSVGAttribute);
2679     Assembler::RegisterID elementAddress = elementAddressRegister;
2680     functionCall.setOneArgument(elementAddress);
2681     functionCall.call();
2682
2683     animatedSVGAttributesNotDirty.link(&m_assembler);
2684 }
2685
2686 void SelectorCodeGenerator::generateElementAttributesMatching(Assembler::JumpList& failureCases, const LocalRegister& elementDataAddress, const SelectorFragment& fragment)
2687 {
2688     LocalRegister scratchRegister(m_registerAllocator);
2689     Assembler::RegisterID elementDataArraySizeAndFlags = scratchRegister;
2690     Assembler::RegisterID attributeArrayLength = scratchRegister;
2691
2692     m_assembler.load32(Assembler::Address(elementDataAddress, ElementData::arraySizeAndFlagsMemoryOffset()), elementDataArraySizeAndFlags);
2693
2694     if (canMatchStyleAttribute(fragment))
2695         generateSynchronizeStyleAttribute(elementDataArraySizeAndFlags);
2696
2697     if (canMatchAnimatableSVGAttribute(fragment))
2698         generateSynchronizeAllAnimatedSVGAttribute(elementDataArraySizeAndFlags);
2699
2700     // Attributes can be stored either in a separate vector for UniqueElementData, or after the elementData itself
2701     // for ShareableElementData.
2702     LocalRegister attributeArrayPointer(m_registerAllocator);
2703     Assembler::Jump isShareableElementData  = m_assembler.branchTest32(Assembler::Zero, elementDataArraySizeAndFlags, Assembler::TrustedImm32(ElementData::isUniqueFlag()));
2704     {
2705         ptrdiff_t attributeVectorOffset = UniqueElementData::attributeVectorMemoryOffset();
2706         m_assembler.loadPtr(Assembler::Address(elementDataAddress, attributeVectorOffset + UniqueElementData::AttributeVector::dataMemoryOffset()), attributeArrayPointer);
2707         m_assembler.load32(Assembler::Address(elementDataAddress, attributeVectorOffset + UniqueElementData::AttributeVector::sizeMemoryOffset()), attributeArrayLength);
2708     }
2709     Assembler::Jump skipShareable = m_assembler.jump();
2710
2711     {
2712         isShareableElementData.link(&m_assembler);
2713         m_assembler.urshift32(elementDataArraySizeAndFlags, Assembler::TrustedImm32(ElementData::arraySizeOffset()), attributeArrayLength);
2714         m_assembler.addPtr(Assembler::TrustedImm32(ShareableElementData::attributeArrayMemoryOffset()), elementDataAddress, attributeArrayPointer);
2715     }
2716
2717     skipShareable.link(&m_assembler);
2718
2719     // If there are no attributes, fail immediately.
2720     failureCases.append(m_assembler.branchTest32(Assembler::Zero, attributeArrayLength));
2721
2722     unsigned attributeCount = fragment.attributes.size();
2723     for (unsigned i = 0; i < attributeCount; ++i) {
2724         Assembler::RegisterID decIndexRegister;
2725         Assembler::RegisterID currentAttributeAddress;
2726
2727         bool isLastAttribute = i == (attributeCount - 1);
2728         if (!isLastAttribute) {
2729             // We need to make a copy to let the next iterations use the values.
2730             currentAttributeAddress = m_registerAllocator.allocateRegister();
2731             decIndexRegister = m_registerAllocator.allocateRegister();
2732             m_assembler.move(attributeArrayPointer, currentAttributeAddress);
2733             m_assembler.move(attributeArrayLength, decIndexRegister);
2734         } else {
2735             currentAttributeAddress = attributeArrayPointer;
2736             decIndexRegister = attributeArrayLength;
2737         }
2738
2739         generateElementAttributeMatching(failureCases, currentAttributeAddress, decIndexRegister, fragment.attributes[i]);
2740
2741         if (!isLastAttribute) {
2742             m_registerAllocator.deallocateRegister(decIndexRegister);
2743             m_registerAllocator.deallocateRegister(currentAttributeAddress);
2744         }
2745     }
2746 }
2747
2748 void SelectorCodeGenerator::generateElementAttributeMatching(Assembler::JumpList& failureCases, Assembler::RegisterID currentAttributeAddress, Assembler::RegisterID decIndexRegister, const AttributeMatchingInfo& attributeInfo)
2749 {
2750     // Get the localName used for comparison. HTML elements use a lowercase local name known in selectors as canonicalLocalName.
2751     LocalRegister localNameToMatch(m_registerAllocator);
2752
2753     // In general, canonicalLocalName and localName are the same. When they differ, we have to check if the node is HTML to know
2754     // which one to use.
2755     const CSSSelector& attributeSelector = attributeInfo.selector();
2756     const AtomicStringImpl* canonicalLocalName = attributeSelector.attributeCanonicalLocalName().impl();
2757     const AtomicStringImpl* localName = attributeSelector.attribute().localName().impl();
2758     if (canonicalLocalName == localName)
2759         m_assembler.move(Assembler::TrustedImmPtr(canonicalLocalName), localNameToMatch);
2760     else {
2761         m_assembler.move(Assembler::TrustedImmPtr(canonicalLocalName), localNameToMatch);
2762         Assembler::Jump elementIsHTML = testIsHTMLFlagOnNode(Assembler::NonZero, m_assembler, elementAddressRegister);
2763         m_assembler.move(Assembler::TrustedImmPtr(localName), localNameToMatch);
2764         elementIsHTML.link(&m_assembler);
2765     }
2766
2767     Assembler::JumpList successCases;
2768     Assembler::Label loopStart(m_assembler.label());
2769
2770     {
2771         LocalRegister qualifiedNameImpl(m_registerAllocator);
2772         m_assembler.loadPtr(Assembler::Address(currentAttributeAddress, Attribute::nameMemoryOffset()), qualifiedNameImpl);
2773
2774         bool shouldCheckNamespace = attributeSelector.attribute().prefix() != starAtom;
2775         if (shouldCheckNamespace) {
2776             Assembler::Jump nameDoesNotMatch = m_assembler.branchPtr(Assembler::NotEqual, Assembler::Address(qualifiedNameImpl, QualifiedName::QualifiedNameImpl::localNameMemoryOffset()), localNameToMatch);
2777
2778             const AtomicStringImpl* namespaceURI = attributeSelector.attribute().namespaceURI().impl();
2779             if (namespaceURI) {
2780                 LocalRegister namespaceToMatch(m_registerAllocator);
2781                 m_assembler.move(Assembler::TrustedImmPtr(namespaceURI), namespaceToMatch);
2782                 successCases.append(m_assembler.branchPtr(Assembler::Equal, Assembler::Address(qualifiedNameImpl, QualifiedName::QualifiedNameImpl::namespaceMemoryOffset()), namespaceToMatch));
2783             } else
2784                 successCases.append(m_assembler.branchTestPtr(Assembler::Zero, Assembler::Address(qualifiedNameImpl, QualifiedName::QualifiedNameImpl::namespaceMemoryOffset())));
2785             nameDoesNotMatch.link(&m_assembler);
2786         } else
2787             successCases.append(m_assembler.branchPtr(Assembler::Equal, Assembler::Address(qualifiedNameImpl, QualifiedName::QualifiedNameImpl::localNameMemoryOffset()), localNameToMatch));
2788     }
2789
2790     Assembler::Label loopReEntry(m_assembler.label());
2791
2792     // If we reached the last element -> failure.
2793     failureCases.append(m_assembler.branchSub32(Assembler::Zero, Assembler::TrustedImm32(1), decIndexRegister));
2794
2795     // Otherwise just loop over.
2796     m_assembler.addPtr(Assembler::TrustedImm32(sizeof(Attribute)), currentAttributeAddress);
2797     m_assembler.jump().linkTo(loopStart, &m_assembler);
2798
2799     successCases.link(&m_assembler);
2800
2801     if (attributeSelector.match() != CSSSelector::Set) {
2802         // We make the assumption that name matching fails in most cases and we keep value matching outside
2803         // of the loop. We re-enter the loop if needed.
2804         // FIXME: exact case sensitive value matching is so simple that it should be done in the loop.
2805         Assembler::JumpList localFailureCases;
2806         generateElementAttributeValueMatching(localFailureCases, currentAttributeAddress, attributeInfo);
2807         localFailureCases.linkTo(loopReEntry, &m_assembler);
2808     }
2809 }
2810
2811 enum CaseSensitivity {
2812     CaseSensitive,
2813     CaseInsensitive
2814 };
2815
2816 template<CaseSensitivity caseSensitivity>
2817 static bool attributeValueBeginsWith(const Attribute* attribute, AtomicStringImpl* expectedString)
2818 {
2819     ASSERT(expectedString);
2820
2821     AtomicStringImpl& valueImpl = *attribute->value().impl();
2822     if (caseSensitivity == CaseSensitive)
2823         return valueImpl.startsWith(*expectedString);
2824     return valueImpl.startsWithIgnoringASCIICase(*expectedString);
2825 }
2826
2827 template<CaseSensitivity caseSensitivity>
2828 static bool attributeValueContains(const Attribute* attribute, AtomicStringImpl* expectedString)
2829 {
2830     AtomicStringImpl& valueImpl = *attribute->value().impl();
2831     if (caseSensitivity == CaseSensitive)
2832         return valueImpl.find(expectedString) != notFound;
2833     return valueImpl.findIgnoringASCIICase(expectedString) != notFound;
2834 }
2835
2836 template<CaseSensitivity caseSensitivity>
2837 static bool attributeValueEndsWith(const Attribute* attribute, AtomicStringImpl* expectedString)
2838 {
2839     ASSERT(expectedString);
2840
2841     AtomicStringImpl& valueImpl = *attribute->value().impl();
2842     if (caseSensitivity == CaseSensitive)
2843         return valueImpl.endsWith(*expectedString);
2844     return valueImpl.endsWithIgnoringASCIICase(*expectedString);
2845 }
2846
2847 template<CaseSensitivity caseSensitivity>
2848 static bool attributeValueMatchHyphenRule(const Attribute* attribute, AtomicStringImpl* expectedString)
2849 {
2850     ASSERT(expectedString);
2851
2852     AtomicStringImpl& valueImpl = *attribute->value().impl();
2853     if (valueImpl.length() < expectedString->length())
2854         return false;
2855
2856     bool valueStartsWithExpectedString;
2857     if (caseSensitivity == CaseSensitive)
2858         valueStartsWithExpectedString = valueImpl.startsWith(*expectedString);
2859     else
2860         valueStartsWithExpectedString = valueImpl.startsWithIgnoringASCIICase(*expectedString);
2861
2862     if (!valueStartsWithExpectedString)
2863         return false;
2864
2865     return valueImpl.length() == expectedString->length() || valueImpl[expectedString->length()] == '-';
2866 }
2867
2868 template<CaseSensitivity caseSensitivity>
2869 static bool attributeValueSpaceSeparetedListContains(const Attribute* attribute, AtomicStringImpl* expectedString)
2870 {
2871     AtomicStringImpl& value = *attribute->value().impl();
2872
2873     unsigned startSearchAt = 0;
2874     while (true) {
2875         size_t foundPos;
2876         if (caseSensitivity == CaseSensitive)
2877             foundPos = value.find(expectedString, startSearchAt);
2878         else
2879             foundPos = value.findIgnoringASCIICase(expectedString, startSearchAt);
2880         if (foundPos == notFound)
2881             return false;
2882         if (!foundPos || isHTMLSpace(value[foundPos - 1])) {
2883             unsigned endStr = foundPos + expectedString->length();
2884             if (endStr == value.length() || isHTMLSpace(value[endStr]))
2885                 return true;
2886         }
2887         startSearchAt = foundPos + 1;
2888     }
2889     return false;
2890 }
2891
2892 void SelectorCodeGenerator::generateElementAttributeValueMatching(Assembler::JumpList& failureCases, Assembler::RegisterID currentAttributeAddress, const AttributeMatchingInfo& attributeInfo)
2893 {
2894     const CSSSelector& attributeSelector = attributeInfo.selector();
2895     const AtomicString& expectedValue = attributeSelector.value();
2896     ASSERT(!expectedValue.isNull());
2897     AttributeCaseSensitivity valueCaseSensitivity = attributeInfo.attributeCaseSensitivity();
2898
2899     switch (attributeSelector.match()) {
2900     case CSSSelector::Begin:
2901         generateElementAttributeFunctionCallValueMatching(failureCases, currentAttributeAddress, expectedValue, valueCaseSensitivity, attributeValueBeginsWith<CaseSensitive>, attributeValueBeginsWith<CaseInsensitive>);
2902         break;
2903     case CSSSelector::Contain:
2904         generateElementAttributeFunctionCallValueMatching(failureCases, currentAttributeAddress, expectedValue, valueCaseSensitivity, attributeValueContains<CaseSensitive>, attributeValueContains<CaseInsensitive>);
2905         break;
2906     case CSSSelector::End:
2907         generateElementAttributeFunctionCallValueMatching(failureCases, currentAttributeAddress, expectedValue, valueCaseSensitivity, attributeValueEndsWith<CaseSensitive>, attributeValueEndsWith<CaseInsensitive>);
2908         break;
2909     case CSSSelector::Exact:
2910         generateElementAttributeValueExactMatching(failureCases, currentAttributeAddress, expectedValue, valueCaseSensitivity);
2911         break;
2912     case CSSSelector::Hyphen:
2913         generateElementAttributeFunctionCallValueMatching(failureCases, currentAttributeAddress, expectedValue, valueCaseSensitivity, attributeValueMatchHyphenRule<CaseSensitive>, attributeValueMatchHyphenRule<CaseInsensitive>);
2914         break;
2915     case CSSSelector::List:
2916         generateElementAttributeFunctionCallValueMatching(failureCases, currentAttributeAddress, expectedValue, valueCaseSensitivity, attributeValueSpaceSeparetedListContains<CaseSensitive>, attributeValueSpaceSeparetedListContains<CaseInsensitive>);
2917         break;
2918     default:
2919         ASSERT_NOT_REACHED();
2920     }
2921 }
2922
2923 static inline Assembler::Jump testIsHTMLClassOnDocument(Assembler::ResultCondition condition, Assembler& assembler, Assembler::RegisterID documentAddress)
2924 {
2925     return assembler.branchTest32(condition, Assembler::Address(documentAddress, Document::documentClassesMemoryOffset()), Assembler::TrustedImm32(Document::isHTMLDocumentClassFlag()));
2926 }
2927
2928 void SelectorCodeGenerator::generateElementAttributeValueExactMatching(Assembler::JumpList& failureCases, Assembler::RegisterID currentAttributeAddress, const AtomicString& expectedValue, AttributeCaseSensitivity valueCaseSensitivity)
2929 {
2930     LocalRegisterWithPreference expectedValueRegister(m_registerAllocator, JSC::GPRInfo::argumentGPR1);
2931     m_assembler.move(Assembler::TrustedImmPtr(expectedValue.impl()), expectedValueRegister);
2932
2933     switch (valueCaseSensitivity) {
2934     case AttributeCaseSensitivity::CaseSensitive: {
2935         failureCases.append(m_assembler.branchPtr(Assembler::NotEqual, Assembler::Address(currentAttributeAddress, Attribute::valueMemoryOffset()), expectedValueRegister));
2936         break;
2937     }
2938     case AttributeCaseSensitivity::HTMLLegacyCaseInsensitive: {
2939         Assembler::Jump skipCaseInsensitiveComparison = m_assembler.branchPtr(Assembler::Equal, Assembler::Address(currentAttributeAddress, Attribute::valueMemoryOffset()), expectedValueRegister);
2940
2941         // If the element is an HTML element, in a HTML dcoument (not including XHTML), value matching is case insensitive.
2942         // Taking the contrapositive, if we find the element is not HTML or is not in a HTML document, the condition above
2943         // sould be sufficient and we can fail early.
2944         failureCases.append(testIsHTMLFlagOnNode(Assembler::Zero, m_assembler, elementAddressRegister));
2945
2946         {
2947             LocalRegister document(m_registerAllocator);
2948             getDocument(m_assembler, elementAddressRegister, document);
2949             failureCases.append(testIsHTMLClassOnDocument(Assembler::Zero, m_assembler, document));
2950         }
2951
2952         LocalRegister valueStringImpl(m_registerAllocator);
2953         m_assembler.loadPtr(Assembler::Address(currentAttributeAddress, Attribute::valueMemoryOffset()), valueStringImpl);
2954
2955         FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2956         functionCall.setFunctionAddress(WTF::equalIgnoringASCIICaseNonNull);
2957         functionCall.setTwoArguments(valueStringImpl, expectedValueRegister);
2958         failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
2959
2960         skipCaseInsensitiveComparison.link(&m_assembler);
2961         break;
2962     }
2963     case AttributeCaseSensitivity::CaseInsensitive: {
2964         LocalRegister valueStringImpl(m_registerAllocator);
2965         m_assembler.loadPtr(Assembler::Address(currentAttributeAddress, Attribute::valueMemoryOffset()), valueStringImpl);
2966
2967         Assembler::Jump skipCaseInsensitiveComparison = m_assembler.branchPtr(Assembler::Equal, valueStringImpl, expectedValueRegister);
2968         FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2969         functionCall.setFunctionAddress(WTF::equalIgnoringASCIICaseNonNull);
2970         functionCall.setTwoArguments(valueStringImpl, expectedValueRegister);
2971         failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
2972         skipCaseInsensitiveComparison.link(&m_assembler);
2973         break;
2974     }
2975     }
2976 }
2977
2978 void SelectorCodeGenerator::generateElementAttributeFunctionCallValueMatching(Assembler::JumpList& failureCases, Assembler::RegisterID currentAttributeAddress, const AtomicString& expectedValue, AttributeCaseSensitivity valueCaseSensitivity, JSC::FunctionPtr caseSensitiveTest, JSC::FunctionPtr caseInsensitiveTest)
2979 {
2980     LocalRegisterWithPreference expectedValueRegister(m_registerAllocator, JSC::GPRInfo::argumentGPR1);
2981     m_assembler.move(Assembler::TrustedImmPtr(expectedValue.impl()), expectedValueRegister);
2982
2983
2984     switch (valueCaseSensitivity) {
2985     case AttributeCaseSensitivity::CaseSensitive: {
2986         FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2987         functionCall.setFunctionAddress(caseSensitiveTest);
2988         functionCall.setTwoArguments(currentAttributeAddress, expectedValueRegister);
2989         failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
2990         break;
2991     }
2992     case AttributeCaseSensitivity::HTMLLegacyCaseInsensitive: {
2993         Assembler::JumpList shouldUseCaseSensitiveComparison;
2994         shouldUseCaseSensitiveComparison.append(testIsHTMLFlagOnNode(Assembler::Zero, m_assembler, elementAddressRegister));
2995         {
2996             LocalRegister scratchRegister(m_registerAllocator);
2997             // scratchRegister = pointer to treeScope.
2998             m_assembler.loadPtr(Assembler::Address(elementAddressRegister, Node::treeScopeMemoryOffset()), scratchRegister);
2999             // scratchRegister = pointer to document.
3000             m_assembler.loadPtr(Assembler::Address(scratchRegister, TreeScope::documentScopeMemoryOffset()), scratchRegister);
3001             shouldUseCaseSensitiveComparison.append(testIsHTMLClassOnDocument(Assembler::Zero, m_assembler, scratchRegister));
3002         }
3003
3004         {
3005             FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
3006             functionCall.setFunctionAddress(caseInsensitiveTest);
3007             functionCall.setTwoArguments(currentAttributeAddress, expectedValueRegister);
3008             failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
3009         }
3010
3011         Assembler::Jump skipCaseSensitiveCase = m_assembler.jump();
3012
3013         {
3014             shouldUseCaseSensitiveComparison.link(&m_assembler);
3015             FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
3016             functionCall.setFunctionAddress(caseSensitiveTest);
3017             functionCall.setTwoArguments(currentAttributeAddress, expectedValueRegister);
3018             failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
3019         }
3020
3021         skipCaseSensitiveCase.link(&m_assembler);
3022         break;
3023     }
3024     case AttributeCaseSensitivity::CaseInsensitive: {
3025         FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
3026         functionCall.setFunctionAddress(caseInsensitiveTest);
3027         functionCall.setTwoArguments(currentAttributeAddress, expectedValueRegister);
3028         failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
3029         break;
3030     }
3031     }
3032 }
3033
3034 void SelectorCodeGenerator::generateElementFunctionCallTest(Assembler::JumpList& failureCases, JSC::FunctionPtr testFunction)
3035 {
3036     Assembler::RegisterID elementAddress = elementAddressRegister;
3037     FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
3038     functionCall.setFunctionAddress(testFunction);
3039     functionCall.setOneArgument(elementAddress);
3040     failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
3041 }
3042
3043 void SelectorCodeGenerator::generateContextFunctionCallTest(Assembler::JumpList& failureCases, JSC::FunctionPtr testFunction)
3044 {
3045     Assembler::RegisterID checkingContext = m_registerAllocator.allocateRegister();
3046     loadCheckingContext(checkingContext);
3047     m_registerAllocator.deallocateRegister(checkingContext);
3048
3049     FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
3050     functionCall.setFunctionAddress(testFunction);
3051     functionCall.setOneArgument(checkingContext);
3052     failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
3053 }
3054
3055 static void setFirstChildState(Element* element)
3056 {
3057     if (RenderStyle* style = element->renderStyle())
3058         style->setFirstChildState();
3059 }
3060
3061 static bool elementIsActive(Element* element)
3062 {
3063     return element->active() || InspectorInstrumentation::forcePseudoState(*element, CSSSelector::PseudoClassActive);
3064 }
3065
3066 static bool elementIsActiveForStyleResolution(Element* element, const SelectorChecker::CheckingContext* checkingContext)
3067 {
3068     if (checkingContext->resolvingMode == SelectorChecker::Mode::ResolvingStyle)
3069         element->setChildrenAffectedByActive();
3070     return element->active() || InspectorInstrumentation::forcePseudoState(*element, CSSSelector::PseudoClassActive);
3071 }
3072
3073 void SelectorCodeGenerator::generateElementIsActive(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
3074 {
3075     generateSpecialFailureInQuirksModeForActiveAndHoverIfNeeded(failureCases, fragment);
3076     if (m_selectorContext == SelectorContext::QuerySelector) {
3077         FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
3078         functionCall.setFunctionAddress(elementIsActive);
3079         functionCall.setOneArgument(elementAddressRegister);
3080         failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
3081         return;
3082     }
3083
3084     if (fragmentMatchesTheRightmostElement(m_selectorContext, fragment)) {
3085         LocalRegister checkingContext(m_registerAllocator);
3086         Assembler::Jump notResolvingStyle = jumpIfNotResolvingStyle(checkingContext);
3087         addFlagsToElementStyleFromContext(checkingContext, RenderStyle::NonInheritedFlags::flagIsaffectedByActive());
3088         notResolvingStyle.link(&m_assembler);
3089
3090         FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
3091         functionCall.setFunctionAddress(elementIsActive);
3092         functionCall.setOneArgument(elementAddressRegister);
3093         failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
3094     } else {
3095         Assembler::RegisterID checkingContext = m_registerAllocator.allocateRegisterWithPreference(JSC::GPRInfo::argumentGPR1);
3096         loadCheckingContext(checkingContext);
3097         m_registerAllocator.deallocateRegister(checkingContext);
3098
3099         FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
3100         functionCall.setFunctionAddress(elementIsActiveForStyleResolution);
3101         functionCall.setTwoArguments(elementAddressRegister, checkingContext);
3102         failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
3103     }
3104 }
3105
3106 static void jumpIfElementIsNotEmpty(Assembler& assembler, RegisterAllocator& registerAllocator, Assembler::JumpList& notEmptyCases, Assembler::RegisterID element)
3107 {
3108     LocalRegister currentChild(registerAllocator);
3109     assembler.loadPtr(Assembler::Address(element, ContainerNode::firstChildMemoryOffset()), currentChild);
3110
3111     Assembler::Label loopStart(assembler.label());
3112     Assembler::Jump noMoreChildren = assembler.branchTestPtr(Assembler::Zero, currentChild);
3113
3114     notEmptyCases.append(testIsElementFlagOnNode(Assembler::NonZero, assembler, currentChild));
3115
3116     {
3117         Assembler::Jump skipTextNodeCheck = assembler.branchTest32(Assembler::Zero, Assembler::Address(currentChild, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagIsText()));
3118
3119         LocalRegister textStringImpl(registerAllocator);
3120         assembler.loadPtr(Assembler::Address(currentChild, CharacterData::dataMemoryOffset()), textStringImpl);
3121         notEmptyCases.append(assembler.branchTest32(Assembler::NonZero, Assembler::Address(textStringImpl, StringImpl::lengthMemoryOffset())));
3122
3123         skipTextNodeCheck.link(&assembler);
3124     }
3125
3126     assembler.loadPtr(Assembler::Address(currentChild, Node::nextSiblingMemoryOffset()), currentChild);
3127     assembler.jump().linkTo(loopStart, &assembler);
3128
3129     noMoreChildren.link(&assembler);
3130 }
3131
3132 static void setElementStyleIsAffectedByEmpty(Element* element)
3133 {
3134     element->setStyleAffectedByEmpty();
3135 }
3136
3137 static void setElementStyleFromContextIsAffectedByEmptyAndUpdateRenderStyleIfNecessary(SelectorChecker::CheckingContext* context, bool isEmpty)
3138 {
3139     ASSERT(context->elementStyle);
3140     context->elementStyle->setEmptyState(isEmpty);
3141 }
3142
3143 void SelectorCodeGenerator::generateElementIsEmpty(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
3144 {
3145     if (m_selectorContext == SelectorContext::QuerySelector) {
3146         jumpIfElementIsNotEmpty(m_assembler, m_registerAllocator, failureCases, elementAddressRegister);
3147         return;
3148     }
3149
3150     LocalRegisterWithPreference isEmptyResults(m_registerAllocator, JSC::GPRInfo::argumentGPR1);
3151     m_assembler.move(Assembler::TrustedImm32(0), isEmptyResults);
3152
3153     Assembler::JumpList notEmpty;
3154     jumpIfElementIsNotEmpty(m_assembler, m_registerAllocator, notEmpty, elementAddressRegister);
3155     m_assembler.move(Assembler::TrustedImm32(1), isEmptyResults);
3156     notEmpty.link(&m_assembler);
3157
3158     Assembler::Jump skipMarking;
3159     if (fragmentMatchesTheRightmostElement(m_selectorContext, fragment)) {
3160         {
3161             LocalRegister checkingContext(m_registerAllocator);
3162             skipMarking = jumpIfNotResolvingStyle(checkingContext);
3163
3164             FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
3165             functionCall.setFunctionAddress(setElementStyleFromContextIsAffectedByEmptyAndUpdateRenderStyleIfNecessary);
3166             functionCall.setTwoArguments(checkingContext, isEmptyResults);
3167             functionCall.call();
3168         }
3169
3170         FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
3171         functionCall.setFunctionAddress(setElementStyleIsAffectedByEmpty);
3172         functionCall.setOneArgument(elementAddressRegister);
3173         functionCall.call();
3174     } else {
3175         {
3176             LocalRegister checkingContext(m_registerAllocator);
3177             skipMarking = jumpIfNotResolvingStyle(checkingContext);
3178         }
3179         FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
3180         functionCall.setFunctionAddress(setElementStyleIsAffectedByEmpty);
3181         functionCall.setOneArgument(elementAddressRegister);
3182         functionCall.call();
3183     }
3184     skipMarking.link(&m_assembler);
3185
3186     failureCases.append(m_assembler.branchTest32(Assembler::Zero, isEmptyResults));
3187 }
3188
3189 void SelectorCodeGenerator::generateElementIsFirstChild(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
3190 {
3191     if (m_selectorContext == SelectorContext::QuerySelector) {
3192         Assembler::JumpList successCase = jumpIfNoPreviousAdjacentElement();
3193         failureCases.append(m_assembler.jump());
3194         successCase.link(&m_assembler);
3195         LocalRegister parent(m_registerAllocator);
3196         generateWalkToParentElement(failureCases, parent);
3197         return;
3198     }
3199
3200     Assembler::RegisterID parentElement = m_registerAllocator.allocateRegister();
3201     generateWalkToParentElement(failureCases, parentElement);
3202
3203     // Zero in isFirstChildRegister is the success case. The register is set to non-zero if a sibling if found.
3204     LocalRegister isFirstChildRegister(m_registerAllocator);
3205     m_assembler.move(Assembler::TrustedImm32(0), isFirstChildRegister);
3206
3207     {
3208         Assembler::JumpList successCase = jumpIfNoPreviousAdjacentElement();
3209
3210         // If there was a sibling element, the element was not the first child -> failure case.
3211         m_assembler.move(Assembler::TrustedImm32(1), isFirstChildRegister);
3212
3213         successCase.link(&m_assembler);
3214     }
3215
3216     LocalRegister checkingContext(m_registerAllocator);
3217     Assembler::Jump notResolvingStyle = jumpIfNotResolvingStyle(checkingContext);
3218
3219     setNodeFlag(m_assembler, parentElement, Node::flagChildrenAffectedByFirstChildRulesFlag());
3220     m_registerAllocator.deallocateRegister(parentElement);
3221
3222     // The parent marking is unconditional. If the matching is not a success, we can now fail.
3223     // Otherwise we need to apply setFirstChildState() on the RenderStyle.
3224     failureCases.append(m_assembler.branchTest32(Assembler::NonZero, isFirstChildRegister));
3225
3226     if (fragmentMatchesTheRightmostElement(m_selectorContext, fragment))
3227         addFlagsToElementStyleFromContext(checkingContext, RenderStyle::NonInheritedFlags::setFirstChildStateFlags());
3228     else {
3229         FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
3230         functionCall.setFunctionAddress(setFirstChildState);
3231         Assembler::RegisterID elementAddress = elementAddressRegister;
3232         functionCall.setOneArgument(elementAddress);
3233         functionCall.call();
3234     }
3235
3236     notResolvingStyle.link(&m_assembler);
3237     failureCases.append(m_assembler.branchTest32(Assembler::NonZero, isFirstChildRegister));
3238 }
3239
3240 static bool elementIsHovered(Element* element)
3241 {
3242     return element->hovered() || InspectorInstrumentation::forcePseudoState(*element, CSSSelector::PseudoClassHover);
3243 }
3244
3245 static bool elementIsHoveredForStyleResolution(Element* element, const SelectorChecker::CheckingContext* checkingContext)
3246 {
3247     if (checkingContext->resolvingMode == SelectorChecker::Mode::ResolvingStyle)
3248         element->setChildrenAffectedByHover();
3249     return element->hovered() || InspectorInstrumentation::forcePseudoState(*element, CSSSelector::PseudoClassHover);
3250 }
3251
3252 void SelectorCodeGenerator::generateElementIsHovered(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
3253 {