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