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