803d82503fc423ed4acef526ff7387a2d8a31d52
[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 AtomicString* id = nullptr;
201     Vector<const Vector<AtomicString>*> languageArgumentsList;
202     Vector<const AtomicStringImpl*, 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<AtomicString>*);
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 AtomicString& expectedValue, AttributeCaseSensitivity valueCaseSensitivity);
313     void generateElementAttributeFunctionCallValueMatching(Assembler::JumpList& failureCases, Assembler::RegisterID currentAttributeAddress, const AtomicString& 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 AtomicString& idToMatch);
316     void generateElementHasClasses(Assembler::JumpList& failureCases, const LocalRegister& elementDataAddress, const Vector<const AtomicStringImpl*, 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, std::optional<Assembler::RegisterID> value = { });
333     void generateAddStyleRelation(Assembler::RegisterID checkingContext, Assembler::RegisterID element, Style::Relation::Type, std::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     // These pseudo-classes only have meaning with scrollbars.
623     case CSSSelector::PseudoClassHorizontal:
624     case CSSSelector::PseudoClassVertical:
625     case CSSSelector::PseudoClassDecrement:
626     case CSSSelector::PseudoClassIncrement:
627     case CSSSelector::PseudoClassStart:
628     case CSSSelector::PseudoClassEnd:
629     case CSSSelector::PseudoClassDoubleButton:
630     case CSSSelector::PseudoClassSingleButton:
631     case CSSSelector::PseudoClassNoButton:
632     case CSSSelector::PseudoClassCornerPresent:
633         return FunctionType::CannotMatchAnything;
634
635     // FIXME: Compile these pseudoclasses, too!
636     case CSSSelector::PseudoClassFirstOfType:
637     case CSSSelector::PseudoClassLastOfType:
638     case CSSSelector::PseudoClassOnlyOfType:
639     case CSSSelector::PseudoClassNthOfType:
640     case CSSSelector::PseudoClassNthLastOfType:
641     case CSSSelector::PseudoClassDrag:
642 #if ENABLE(CSS_SELECTORS_LEVEL4)
643     case CSSSelector::PseudoClassDir:
644     case CSSSelector::PseudoClassRole:
645 #endif
646         return FunctionType::CannotCompile;
647
648     // Optimized pseudo selectors.
649     case CSSSelector::PseudoClassAnyLink:
650     case CSSSelector::PseudoClassLink:
651     case CSSSelector::PseudoClassRoot:
652     case CSSSelector::PseudoClassTarget:
653         fragment.pseudoClasses.add(type);
654         return FunctionType::SimpleSelectorChecker;
655     case CSSSelector::PseudoClassAnyLinkDeprecated:
656         fragment.pseudoClasses.add(CSSSelector::PseudoClassAnyLink);
657         return FunctionType::SimpleSelectorChecker;
658
659     case CSSSelector::PseudoClassVisited:
660         // Determine this :visited cannot match anything statically.
661         if (!visitedMatchEnabled)
662             return FunctionType::CannotMatchAnything;
663
664         // Inside functional pseudo class except for :not, :visited never matches.
665         // And in the case inside :not, returning CannotMatchAnything indicates that :not(:visited) can match over anything.
666         if (fragmentLevel == FragmentsLevel::InFunctionalPseudoType)
667             return FunctionType::CannotMatchAnything;
668
669         fragment.pseudoClasses.add(type);
670         visitedMode = VisitedMode::Visited;
671         return FunctionType::SimpleSelectorChecker;
672
673     case CSSSelector::PseudoClassScope:
674         if (selectorContext != SelectorContext::QuerySelector) {
675             fragment.pseudoClasses.add(CSSSelector::PseudoClassRoot);
676             return FunctionType::SimpleSelectorChecker;
677         }
678         fragment.pseudoClasses.add(CSSSelector::PseudoClassScope);
679         return FunctionType::SelectorCheckerWithCheckingContext;
680
681     case CSSSelector::PseudoClassActive:
682     case CSSSelector::PseudoClassEmpty:
683     case CSSSelector::PseudoClassFirstChild:
684     case CSSSelector::PseudoClassHover:
685     case CSSSelector::PseudoClassLastChild:
686     case CSSSelector::PseudoClassOnlyChild:
687     case CSSSelector::PseudoClassPlaceholderShown:
688     case CSSSelector::PseudoClassFocusWithin:
689         fragment.pseudoClasses.add(type);
690         if (selectorContext == SelectorContext::QuerySelector)
691             return FunctionType::SimpleSelectorChecker;
692         return FunctionType::SelectorCheckerWithCheckingContext;
693
694     case CSSSelector::PseudoClassNthChild:
695         return addNthChildType(selector, selectorContext, positionInRootFragments, CSSSelector::PseudoClassFirstChild, visitedMatchEnabled, fragment.nthChildFilters, fragment.nthChildOfFilters, fragment.pseudoClasses, internalSpecificity);
696
697     case CSSSelector::PseudoClassNthLastChild:
698         return addNthChildType(selector, selectorContext, positionInRootFragments, CSSSelector::PseudoClassLastChild, visitedMatchEnabled, fragment.nthLastChildFilters, fragment.nthLastChildOfFilters, fragment.pseudoClasses, internalSpecificity);
699
700     case CSSSelector::PseudoClassNot:
701         {
702             const CSSSelectorList* selectorList = selector.selectorList();
703
704             ASSERT_WITH_MESSAGE(selectorList, "The CSS Parser should never produce valid :not() CSSSelector with an empty selectorList.");
705             if (!selectorList)
706                 return FunctionType::CannotMatchAnything;
707
708             FunctionType functionType = FunctionType::SimpleSelectorChecker;
709             SelectorFragmentList* selectorFragments = nullptr;
710             for (const CSSSelector* subselector = selectorList->first(); subselector; subselector = CSSSelectorList::next(subselector)) {
711                 if (!selectorFragments) {
712                     fragment.notFilters.append(SelectorFragmentList());
713                     selectorFragments = &fragment.notFilters.last();
714                 }
715
716                 VisitedMode ignoreVisitedMode = VisitedMode::None;
717                 FunctionType localFunctionType = constructFragments(subselector, selectorContext, *selectorFragments, FragmentsLevel::InFunctionalPseudoType, positionInRootFragments, visitedMatchEnabled, ignoreVisitedMode, PseudoElementMatchingBehavior::NeverMatch);
718                 ASSERT_WITH_MESSAGE(ignoreVisitedMode == VisitedMode::None, ":visited is disabled in the functional pseudo classes");
719
720                 // Since this is not pseudo class filter, CannotMatchAnything implies this filter always passes.
721                 if (localFunctionType == FunctionType::CannotMatchAnything)
722                     continue;
723
724                 if (localFunctionType == FunctionType::CannotCompile)
725                     return FunctionType::CannotCompile;
726
727                 functionType = mostRestrictiveFunctionType(functionType, localFunctionType);
728                 selectorFragments = nullptr;
729             }
730
731             // If there is still a SelectorFragmentList open, the last Fragment(s) cannot match anything,
732             // we have one FragmentList too many in our selector list.
733             if (selectorFragments)
734                 fragment.notFilters.removeLast();
735
736             return functionType;
737         }
738
739     case CSSSelector::PseudoClassAny:
740         {
741             Vector<SelectorFragment, 32> anyFragments;
742             FunctionType functionType = FunctionType::SimpleSelectorChecker;
743             for (const CSSSelector* rootSelector = selector.selectorList()->first(); rootSelector; rootSelector = CSSSelectorList::next(rootSelector)) {
744                 SelectorFragmentList fragmentList;
745                 VisitedMode ignoreVisitedMode = VisitedMode::None;
746                 FunctionType subFunctionType = constructFragments(rootSelector, selectorContext, fragmentList, FragmentsLevel::InFunctionalPseudoType, positionInRootFragments, visitedMatchEnabled, ignoreVisitedMode, PseudoElementMatchingBehavior::NeverMatch);
747                 ASSERT_WITH_MESSAGE(ignoreVisitedMode == VisitedMode::None, ":visited is disabled in the functional pseudo classes");
748
749                 // Since this fragment always unmatch against the element, don't insert it to anyFragments.
750                 if (subFunctionType == FunctionType::CannotMatchAnything)
751                     continue;
752
753                 if (subFunctionType == FunctionType::CannotCompile)
754                     return FunctionType::CannotCompile;
755
756                 // :any() may not contain complex selectors which have combinators.
757                 ASSERT(fragmentList.size() == 1);
758                 if (fragmentList.size() != 1)
759                     return FunctionType::CannotCompile;
760
761                 const SelectorFragment& subFragment = fragmentList.first();
762                 anyFragments.append(subFragment);
763                 functionType = mostRestrictiveFunctionType(functionType, subFunctionType);
764             }
765
766             // Since all fragments in :any() cannot match anything, this :any() filter cannot match anything.
767             if (anyFragments.isEmpty())
768                 return FunctionType::CannotMatchAnything;
769
770             ASSERT(!anyFragments.isEmpty());
771             fragment.anyFilters.append(anyFragments);
772
773             return functionType;
774         }
775
776     case CSSSelector::PseudoClassLang:
777         {
778             const Vector<AtomicString>* selectorLangArgumentList = selector.langArgumentList();
779             ASSERT(selectorLangArgumentList && !selectorLangArgumentList->isEmpty());
780             fragment.languageArgumentsList.append(selectorLangArgumentList);
781             return FunctionType::SimpleSelectorChecker;
782         }
783
784     case CSSSelector::PseudoClassMatches:
785         {
786             SelectorList matchesList;
787             const CSSSelectorList* selectorList = selector.selectorList();
788             FunctionType functionType = FunctionType::SimpleSelectorChecker;
789             unsigned firstFragmentListSpecificity = 0;
790             bool firstFragmentListSpecificitySet = false;
791             SelectorFragmentList* selectorFragments = nullptr;
792             for (const CSSSelector* subselector = selectorList->first(); subselector; subselector = CSSSelectorList::next(subselector)) {
793                 if (!selectorFragments) {
794                     matchesList.append(SelectorFragmentList());
795                     selectorFragments = &matchesList.last();
796                 }
797
798                 VisitedMode ignoreVisitedMode = VisitedMode::None;
799                 FunctionType localFunctionType = constructFragments(subselector, selectorContext, *selectorFragments, FragmentsLevel::InFunctionalPseudoType, positionInRootFragments, visitedMatchEnabled, ignoreVisitedMode, pseudoElementMatchingBehavior);
800                 ASSERT_WITH_MESSAGE(ignoreVisitedMode == VisitedMode::None, ":visited is disabled in the functional pseudo classes");
801
802                 // Since this fragment never matches against the element, don't insert it to matchesList.
803                 if (localFunctionType == FunctionType::CannotMatchAnything)
804                     continue;
805
806                 if (localFunctionType == FunctionType::CannotCompile)
807                     return FunctionType::CannotCompile;
808
809                 // FIXME: Currently pseudo elements inside :matches are supported in non-JIT code.
810                 if (selectorFragments->first().pseudoElementSelector)
811                     return FunctionType::CannotCompile;
812
813                 if (firstFragmentListSpecificitySet) {
814                     // The CSS JIT does not handle dynamic specificity yet.
815                     if (selectorContext == SelectorContext::RuleCollector && selectorFragments->staticSpecificity != firstFragmentListSpecificity)
816                         return FunctionType::CannotCompile;
817                 } else {
818                     firstFragmentListSpecificitySet = true;
819                     firstFragmentListSpecificity = selectorFragments->staticSpecificity;
820                 }
821
822                 functionType = mostRestrictiveFunctionType(functionType, localFunctionType);
823                 selectorFragments = nullptr;
824             }
825
826             // If there is still a SelectorFragmentList open, the last Fragment(s) cannot match anything,
827             // we have one FragmentList too many in our selector list.
828             if (selectorFragments)
829                 matchesList.removeLast();
830
831             // Since all selector list in :matches() cannot match anything, the whole :matches() filter cannot match anything.
832             if (matchesList.isEmpty())
833                 return FunctionType::CannotMatchAnything;
834
835             internalSpecificity = firstFragmentListSpecificity;
836
837             fragment.matchesFilters.append(matchesList);
838
839             return functionType;
840         }
841     case CSSSelector::PseudoClassHost:
842         return FunctionType::CannotCompile;
843     case CSSSelector::PseudoClassUnknown:
844         ASSERT_NOT_REACHED();
845         return FunctionType::CannotMatchAnything;
846     }
847
848     ASSERT_NOT_REACHED();
849     return FunctionType::CannotCompile;
850 }
851
852 inline SelectorCodeGenerator::SelectorCodeGenerator(const CSSSelector* rootSelector, SelectorContext selectorContext)
853     : m_stackAllocator(m_assembler)
854     , m_selectorContext(selectorContext)
855     , m_functionType(FunctionType::SimpleSelectorChecker)
856     , m_visitedMode(VisitedMode::None)
857     , m_descendantBacktrackingStartInUse(false)
858 #if CSS_SELECTOR_JIT_DEBUGGING
859     , m_originalSelector(rootSelector)
860 #endif
861 {
862 #if CSS_SELECTOR_JIT_DEBUGGING
863     dataLogF("Compiling \"%s\"\n", m_originalSelector->selectorText().utf8().data());
864 #endif
865
866     // In QuerySelector context, :visited always has no effect due to security issues.
867     bool visitedMatchEnabled = selectorContext != SelectorContext::QuerySelector;
868
869     m_functionType = constructFragments(rootSelector, m_selectorContext, m_selectorFragments, FragmentsLevel::Root, FragmentPositionInRootFragments::Rightmost, visitedMatchEnabled, m_visitedMode, PseudoElementMatchingBehavior::CanMatch);
870     if (m_functionType != FunctionType::CannotCompile && m_functionType != FunctionType::CannotMatchAnything)
871         computeBacktrackingInformation(m_selectorFragments);
872 }
873
874 static bool pseudoClassOnlyMatchesLinksInQuirksMode(const CSSSelector& selector)
875 {
876     CSSSelector::PseudoClassType pseudoClassType = selector.pseudoClassType();
877     return pseudoClassType == CSSSelector::PseudoClassHover || pseudoClassType == CSSSelector::PseudoClassActive;
878 }
879
880 static bool isScrollbarPseudoElement(CSSSelector::PseudoElementType type)
881 {
882     return type >= CSSSelector::PseudoElementScrollbar && type <= CSSSelector::PseudoElementScrollbarTrackPiece;
883 }
884
885 static FunctionType constructFragmentsInternal(const CSSSelector* rootSelector, SelectorContext selectorContext, SelectorFragmentList& selectorFragments, FragmentsLevel fragmentLevel, FragmentPositionInRootFragments positionInRootFragments, bool visitedMatchEnabled, VisitedMode& visitedMode, PseudoElementMatchingBehavior pseudoElementMatchingBehavior)
886 {
887     FragmentRelation relationToPreviousFragment = FragmentRelation::Rightmost;
888     bool isRightmostOrAdjacent = positionInRootFragments != FragmentPositionInRootFragments::Other;
889     FunctionType functionType = FunctionType::SimpleSelectorChecker;
890     SelectorFragment* fragment = nullptr;
891     unsigned specificity = 0;
892     for (const CSSSelector* selector = rootSelector; selector; selector = selector->tagHistory()) {
893         if (!fragment) {
894             selectorFragments.append(SelectorFragment());
895             fragment = &selectorFragments.last();
896         }
897
898         specificity = CSSSelector::addSpecificities(specificity, selector->simpleSelectorSpecificity());
899
900         // A selector is invalid if something follows a pseudo-element.
901         // We make an exception for scrollbar pseudo elements and allow a set of pseudo classes (but nothing else)
902         // to follow the pseudo elements.
903         if (fragment->pseudoElementSelector && !isScrollbarPseudoElement(fragment->pseudoElementSelector->pseudoElementType()))
904             return FunctionType::CannotMatchAnything;
905
906         switch (selector->match()) {
907         case CSSSelector::Tag:
908             ASSERT(!fragment->tagNameSelector);
909             fragment->tagNameSelector = selector;
910             if (fragment->tagNameSelector->tagQName() != anyQName())
911                 fragment->onlyMatchesLinksInQuirksMode = false;
912             break;
913         case CSSSelector::Id: {
914             const AtomicString& id = selector->value();
915             if (fragment->id) {
916                 if (id != *fragment->id)
917                     return FunctionType::CannotMatchAnything;
918             } else
919                 fragment->id = &(selector->value());
920             fragment->onlyMatchesLinksInQuirksMode = false;
921             break;
922         }
923         case CSSSelector::Class:
924             fragment->classNames.append(selector->value().impl());
925             fragment->onlyMatchesLinksInQuirksMode = false;
926             break;
927         case CSSSelector::PseudoClass: {
928             FragmentPositionInRootFragments subPosition = positionInRootFragments;
929             if (relationToPreviousFragment != FragmentRelation::Rightmost)
930                 subPosition = isRightmostOrAdjacent ? FragmentPositionInRootFragments::AdjacentToRightmost : FragmentPositionInRootFragments::Other;
931             if (fragment->pseudoElementSelector && isScrollbarPseudoElement(fragment->pseudoElementSelector->pseudoElementType()))
932                 functionType = mostRestrictiveFunctionType(functionType, addScrollbarPseudoClassType(*selector, *fragment));
933             else {
934                 unsigned internalSpecificity = 0;
935                 functionType = mostRestrictiveFunctionType(functionType, addPseudoClassType(*selector, *fragment, internalSpecificity, selectorContext, fragmentLevel, subPosition, visitedMatchEnabled, visitedMode, pseudoElementMatchingBehavior));
936                 specificity = CSSSelector::addSpecificities(specificity, internalSpecificity);
937             }
938             if (!pseudoClassOnlyMatchesLinksInQuirksMode(*selector))
939                 fragment->onlyMatchesLinksInQuirksMode = false;
940             if (functionType == FunctionType::CannotCompile || functionType == FunctionType::CannotMatchAnything)
941                 return functionType;
942             break;
943         }
944         case CSSSelector::PseudoElement: {
945             fragment->onlyMatchesLinksInQuirksMode = false;
946
947             // In the QuerySelector context, PseudoElement selectors always fail.
948             if (selectorContext == SelectorContext::QuerySelector)
949                 return FunctionType::CannotMatchAnything;
950
951             switch (selector->pseudoElementType()) {
952             case CSSSelector::PseudoElementAfter:
953             case CSSSelector::PseudoElementBefore:
954             case CSSSelector::PseudoElementFirstLetter:
955             case CSSSelector::PseudoElementFirstLine:
956             case CSSSelector::PseudoElementScrollbar:
957             case CSSSelector::PseudoElementScrollbarButton:
958             case CSSSelector::PseudoElementScrollbarCorner:
959             case CSSSelector::PseudoElementScrollbarThumb:
960             case CSSSelector::PseudoElementScrollbarTrack:
961             case CSSSelector::PseudoElementScrollbarTrackPiece:
962                 ASSERT(!fragment->pseudoElementSelector);
963                 fragment->pseudoElementSelector = selector;
964                 break;
965             case CSSSelector::PseudoElementUnknown:
966                 ASSERT_NOT_REACHED();
967                 return FunctionType::CannotMatchAnything;
968             // FIXME: Support PseudoId::Resizer, PseudoId::Selection etc.
969             default:
970                 // This branch includes custom pseudo elements.
971                 return FunctionType::CannotCompile;
972             }
973
974             if (pseudoElementMatchingBehavior == PseudoElementMatchingBehavior::NeverMatch)
975                 return FunctionType::CannotMatchAnything;
976
977             functionType = FunctionType::SelectorCheckerWithCheckingContext;
978             break;
979         }
980         case CSSSelector::List:
981             if (selector->value().find(isHTMLSpace<UChar>) != notFound)
982                 return FunctionType::CannotMatchAnything;
983             FALLTHROUGH;
984         case CSSSelector::Begin:
985         case CSSSelector::End:
986         case CSSSelector::Contain:
987             if (selector->value().isEmpty())
988                 return FunctionType::CannotMatchAnything;
989             FALLTHROUGH;
990         case CSSSelector::Exact:
991         case CSSSelector::Hyphen:
992             fragment->onlyMatchesLinksInQuirksMode = false;
993             fragment->attributes.append(AttributeMatchingInfo(*selector));
994             break;
995
996         case CSSSelector::Set:
997             fragment->onlyMatchesLinksInQuirksMode = false;
998             fragment->attributes.append(AttributeMatchingInfo(*selector));
999             break;
1000         case CSSSelector::PagePseudoClass:
1001             fragment->onlyMatchesLinksInQuirksMode = false;
1002             // Pseudo page class are only relevant for style resolution, they are ignored for matching.
1003             break;
1004         case CSSSelector::Unknown:
1005             ASSERT_NOT_REACHED();
1006             return FunctionType::CannotMatchAnything;
1007         }
1008
1009         auto relation = selector->relation();
1010         if (relation == CSSSelector::Subselector)
1011             continue;
1012
1013         if (relation == CSSSelector::ShadowDescendant && !selector->isLastInTagHistory())
1014             return FunctionType::CannotCompile;
1015
1016         if (relation == CSSSelector::DirectAdjacent || relation == CSSSelector::IndirectAdjacent) {
1017             FunctionType relationFunctionType = FunctionType::SelectorCheckerWithCheckingContext;
1018             if (selectorContext == SelectorContext::QuerySelector)
1019                 relationFunctionType = FunctionType::SimpleSelectorChecker;
1020             functionType = mostRestrictiveFunctionType(functionType, relationFunctionType);
1021
1022             // When the relation is adjacent, disable :visited match.
1023             visitedMatchEnabled = false;
1024         }
1025
1026         // Virtual pseudo element is only effective in the rightmost fragment.
1027         pseudoElementMatchingBehavior = PseudoElementMatchingBehavior::NeverMatch;
1028
1029         fragment->relationToLeftFragment = fragmentRelationForSelectorRelation(relation);
1030         fragment->relationToRightFragment = relationToPreviousFragment;
1031         fragment->positionInRootFragments = positionInRootFragments;
1032         fragment->isRightmostOrAdjacent = isRightmostOrAdjacent;
1033         relationToPreviousFragment = fragment->relationToLeftFragment;
1034         if (relationToPreviousFragment != FragmentRelation::Rightmost && relationToPreviousFragment != FragmentRelation::DirectAdjacent && relationToPreviousFragment != FragmentRelation::IndirectAdjacent)
1035             isRightmostOrAdjacent = false;
1036
1037         if (fragmentLevel != FragmentsLevel::Root)
1038             fragment->onlyMatchesLinksInQuirksMode = false;
1039
1040         fragment = nullptr;
1041     }
1042
1043     ASSERT(!fragment);
1044
1045     selectorFragments.staticSpecificity = specificity;
1046
1047     return functionType;
1048 }
1049
1050 static FunctionType constructFragments(const CSSSelector* rootSelector, SelectorContext selectorContext, SelectorFragmentList& selectorFragments, FragmentsLevel fragmentLevel, FragmentPositionInRootFragments positionInRootFragments, bool visitedMatchEnabled, VisitedMode& visitedMode, PseudoElementMatchingBehavior pseudoElementMatchingBehavior)
1051 {
1052     ASSERT(selectorFragments.isEmpty());
1053
1054     FunctionType functionType = constructFragmentsInternal(rootSelector, selectorContext, selectorFragments, fragmentLevel, positionInRootFragments, visitedMatchEnabled, visitedMode, pseudoElementMatchingBehavior);
1055     if (functionType != FunctionType::SimpleSelectorChecker && functionType != FunctionType::SelectorCheckerWithCheckingContext)
1056         selectorFragments.clear();
1057     return functionType;
1058 }
1059
1060 static inline bool attributeNameTestingRequiresNamespaceRegister(const CSSSelector& attributeSelector)
1061 {
1062     return attributeSelector.attribute().prefix() != starAtom() && !attributeSelector.attribute().namespaceURI().isNull();
1063 }
1064
1065 static inline bool attributeValueTestingRequiresExtraRegister(const AttributeMatchingInfo& attributeInfo)
1066 {
1067     switch (attributeInfo.attributeCaseSensitivity()) {
1068     case AttributeCaseSensitivity::CaseSensitive:
1069         return false;
1070     case AttributeCaseSensitivity::HTMLLegacyCaseInsensitive:
1071         return true;
1072     case AttributeCaseSensitivity::CaseInsensitive:
1073         return attributeInfo.selector().match() == CSSSelector::Exact;
1074     }
1075     return true;
1076 }
1077
1078 // Element + ElementData + a pointer to values + an index on that pointer + the value we expect;
1079 static const unsigned minimumRequiredRegisterCount = 5;
1080 // Element + ElementData + scratchRegister + attributeArrayPointer + expectedLocalName + (qualifiedNameImpl && expectedValue).
1081 static const unsigned minimumRequiredRegisterCountForAttributeFilter = 6;
1082 // On x86, we always need 6 registers: Element + SiblingCounter + SiblingCounterCopy + divisor + dividend + remainder.
1083 // On other architectures, we need 6 registers for style resolution:
1084 //     Element + elementCounter + previousSibling + checkingContext + lastRelation + nextSiblingElement.
1085 static const unsigned minimumRequiredRegisterCountForNthChildFilter = 6;
1086
1087 static unsigned minimumRegisterRequirements(const SelectorFragment& selectorFragment)
1088 {
1089     unsigned minimum = minimumRequiredRegisterCount;
1090     const auto& attributes = selectorFragment.attributes;
1091
1092     // Attributes cause some register pressure.
1093     unsigned attributeCount = attributes.size();
1094     for (unsigned attributeIndex = 0; attributeIndex < attributeCount; ++attributeIndex) {
1095         unsigned attributeMinimum = minimumRequiredRegisterCountForAttributeFilter;
1096
1097         if (attributeIndex + 1 < attributeCount)
1098             attributeMinimum += 2; // For the local copy of the counter and attributeArrayPointer.
1099
1100         const AttributeMatchingInfo& attributeInfo = attributes[attributeIndex];
1101         const CSSSelector& attributeSelector = attributeInfo.selector();
1102         if (attributeNameTestingRequiresNamespaceRegister(attributeSelector)
1103             || attributeValueTestingRequiresExtraRegister(attributeInfo))
1104             attributeMinimum += 1;
1105
1106         minimum = std::max(minimum, attributeMinimum);
1107     }
1108
1109     if (!selectorFragment.nthChildFilters.isEmpty() || !selectorFragment.nthChildOfFilters.isEmpty() || !selectorFragment.nthLastChildFilters.isEmpty() || !selectorFragment.nthLastChildOfFilters.isEmpty())
1110         minimum = std::max(minimum, minimumRequiredRegisterCountForNthChildFilter);
1111
1112     // :any pseudo class filters cause some register pressure.
1113     for (const auto& subFragments : selectorFragment.anyFilters) {
1114         for (const SelectorFragment& subFragment : subFragments) {
1115             unsigned anyFilterMinimum = minimumRegisterRequirements(subFragment);
1116             minimum = std::max(minimum, anyFilterMinimum);
1117         }
1118     }
1119
1120     return minimum;
1121 }
1122
1123 bool hasAnyCombinators(const Vector<SelectorFragmentList>& selectorList);
1124 template <size_t inlineCapacity>
1125 bool hasAnyCombinators(const Vector<SelectorFragment, inlineCapacity>& selectorFragmentList);
1126
1127 bool hasAnyCombinators(const Vector<SelectorFragmentList>& selectorList)
1128 {
1129     for (const SelectorFragmentList& selectorFragmentList : selectorList) {
1130         if (hasAnyCombinators(selectorFragmentList))
1131             return true;
1132     }
1133     return false;
1134 }
1135
1136 template <size_t inlineCapacity>
1137 bool hasAnyCombinators(const Vector<SelectorFragment, inlineCapacity>& selectorFragmentList)
1138 {
1139     if (selectorFragmentList.isEmpty())
1140         return false;
1141     if (selectorFragmentList.size() != 1)
1142         return true;
1143     if (hasAnyCombinators(selectorFragmentList.first().notFilters))
1144         return true;
1145     for (const SelectorList& matchesList : selectorFragmentList.first().matchesFilters) {
1146         if (hasAnyCombinators(matchesList))
1147             return true;
1148     }
1149     for (const NthChildOfSelectorInfo& nthChildOfSelectorInfo : selectorFragmentList.first().nthChildOfFilters) {
1150         if (hasAnyCombinators(nthChildOfSelectorInfo.selectorList))
1151             return true;
1152     }
1153     for (const NthChildOfSelectorInfo& nthLastChildOfSelectorInfo : selectorFragmentList.first().nthLastChildOfFilters) {
1154         if (hasAnyCombinators(nthLastChildOfSelectorInfo.selectorList))
1155             return true;
1156     }
1157     return false;
1158 }
1159
1160 // The CSS JIT has only been validated with a strict minimum of 6 allocated registers.
1161 const unsigned minimumRegisterRequirement = 6;
1162
1163 void computeBacktrackingMemoryRequirements(SelectorFragmentList& selectorFragments, bool backtrackingRegisterReserved = false);
1164
1165 static void computeBacktrackingMemoryRequirements(SelectorList& selectorList, unsigned& totalRegisterRequirements, unsigned& totalStackRequirements, bool backtrackingRegisterReservedForFragment = false)
1166 {
1167     unsigned selectorListRegisterRequirements = 0;
1168     unsigned selectorListStackRequirements = 0;
1169     bool clobberElementAddressRegister = false;
1170
1171     for (SelectorFragmentList& selectorFragmentList : selectorList) {
1172         computeBacktrackingMemoryRequirements(selectorFragmentList, backtrackingRegisterReservedForFragment);
1173
1174         selectorListRegisterRequirements = std::max(selectorListRegisterRequirements, selectorFragmentList.registerRequirements);
1175         selectorListStackRequirements = std::max(selectorListStackRequirements, selectorFragmentList.stackRequirements);
1176         clobberElementAddressRegister = clobberElementAddressRegister || selectorFragmentList.clobberElementAddressRegister;
1177     }
1178
1179     totalRegisterRequirements = std::max(totalRegisterRequirements, selectorListRegisterRequirements);
1180     totalStackRequirements = std::max(totalStackRequirements, selectorListStackRequirements);
1181
1182     selectorList.registerRequirements = std::max(selectorListRegisterRequirements, minimumRegisterRequirement);
1183     selectorList.stackRequirements = selectorListStackRequirements;
1184     selectorList.clobberElementAddressRegister = clobberElementAddressRegister;
1185 }
1186
1187 void computeBacktrackingMemoryRequirements(SelectorFragmentList& selectorFragments, bool backtrackingRegisterReserved)
1188 {
1189     selectorFragments.registerRequirements = minimumRegisterRequirement;
1190     selectorFragments.stackRequirements = 0;
1191     selectorFragments.clobberElementAddressRegister = hasAnyCombinators(selectorFragments);
1192
1193     for (SelectorFragment& selectorFragment : selectorFragments) {
1194         unsigned fragmentRegisterRequirements = minimumRegisterRequirements(selectorFragment);
1195         unsigned fragmentStackRequirements = 0;
1196
1197         bool backtrackingRegisterReservedForFragment = backtrackingRegisterReserved || selectorFragment.backtrackingFlags & BacktrackingFlag::InChainWithDescendantTail;
1198
1199         computeBacktrackingMemoryRequirements(selectorFragment.notFilters, fragmentRegisterRequirements, fragmentStackRequirements, backtrackingRegisterReservedForFragment);
1200
1201         for (SelectorList& matchesList : selectorFragment.matchesFilters)
1202             computeBacktrackingMemoryRequirements(matchesList, fragmentRegisterRequirements, fragmentStackRequirements, backtrackingRegisterReservedForFragment);
1203
1204         for (NthChildOfSelectorInfo& nthChildOfSelectorInfo : selectorFragment.nthChildOfFilters)
1205             computeBacktrackingMemoryRequirements(nthChildOfSelectorInfo.selectorList, fragmentRegisterRequirements, fragmentStackRequirements, backtrackingRegisterReservedForFragment);
1206
1207         for (NthChildOfSelectorInfo& nthLastChildOfSelectorInfo : selectorFragment.nthLastChildOfFilters)
1208             computeBacktrackingMemoryRequirements(nthLastChildOfSelectorInfo.selectorList, fragmentRegisterRequirements, fragmentStackRequirements, backtrackingRegisterReservedForFragment);
1209
1210         if (selectorFragment.backtrackingFlags & BacktrackingFlag::InChainWithDescendantTail) {
1211             if (!backtrackingRegisterReserved)
1212                 ++fragmentRegisterRequirements;
1213             else
1214                 ++fragmentStackRequirements;
1215         }
1216         if (selectorFragment.backtrackingFlags & BacktrackingFlag::InChainWithAdjacentTail)
1217             ++fragmentStackRequirements;
1218
1219         selectorFragments.registerRequirements = std::max(selectorFragments.registerRequirements, fragmentRegisterRequirements);
1220         selectorFragments.stackRequirements = std::max(selectorFragments.stackRequirements, fragmentStackRequirements);
1221     }
1222 }
1223
1224 inline SelectorCompilationStatus SelectorCodeGenerator::compile(JSC::MacroAssemblerCodeRef<CSSSelectorPtrTag>& codeRef)
1225 {
1226     switch (m_functionType) {
1227     case FunctionType::SimpleSelectorChecker:
1228     case FunctionType::SelectorCheckerWithCheckingContext:
1229         generateSelectorChecker();
1230         break;
1231     case FunctionType::CannotMatchAnything:
1232         m_assembler.tagReturnAddress();
1233         m_assembler.move(Assembler::TrustedImm32(0), returnRegister);
1234         m_assembler.ret();
1235         break;
1236     case FunctionType::CannotCompile:
1237         return SelectorCompilationStatus::CannotCompile;
1238     }
1239
1240     JSC::LinkBuffer linkBuffer(m_assembler, CSS_CODE_ID, JSC::JITCompilationCanFail);
1241     if (!linkBuffer.isValid()) {
1242         // This could be SelectorCompilationStatus::NotCompiled but that would cause us to re-enter
1243         // the CSS JIT every time we evaluate that selector.
1244         // If we failed to allocate the buffer, we have bigger problems than CSS performance, it is fine
1245         // to be slower.
1246         return SelectorCompilationStatus::CannotCompile;
1247     }
1248
1249     for (unsigned i = 0; i < m_functionCalls.size(); i++)
1250         linkBuffer.link(m_functionCalls[i].first, m_functionCalls[i].second);
1251
1252 #if CSS_SELECTOR_JIT_DEBUGGING
1253     codeRef = linkBuffer.finalizeCodeWithDisassembly(CSSSelectorPtrTag, "CSS Selector JIT for \"%s\"", m_originalSelector->selectorText().utf8().data());
1254 #else
1255     codeRef = FINALIZE_CODE(linkBuffer, CSSSelectorPtrTag, "CSS Selector JIT");
1256 #endif
1257
1258     if (m_functionType == FunctionType::SimpleSelectorChecker || m_functionType == FunctionType::CannotMatchAnything)
1259         return SelectorCompilationStatus::SimpleSelectorChecker;
1260     return SelectorCompilationStatus::SelectorCheckerWithCheckingContext;
1261 }
1262
1263
1264 static inline void updateChainStates(const SelectorFragment& fragment, bool& hasDescendantRelationOnTheRight, unsigned& ancestorPositionSinceDescendantRelation, bool& hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain, unsigned& adjacentPositionSinceIndirectAdjacentTreeWalk)
1265 {
1266     switch (fragment.relationToRightFragment) {
1267     case FragmentRelation::Rightmost:
1268         break;
1269     case FragmentRelation::Descendant:
1270         hasDescendantRelationOnTheRight = true;
1271         ancestorPositionSinceDescendantRelation = 0;
1272         hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain = false;
1273         break;
1274     case FragmentRelation::Child:
1275         if (hasDescendantRelationOnTheRight)
1276             ++ancestorPositionSinceDescendantRelation;
1277         hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain = false;
1278         break;
1279     case FragmentRelation::DirectAdjacent:
1280         if (hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain)
1281             ++adjacentPositionSinceIndirectAdjacentTreeWalk;
1282         break;
1283     case FragmentRelation::IndirectAdjacent:
1284         hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain = true;
1285         adjacentPositionSinceIndirectAdjacentTreeWalk = 0;
1286         break;
1287     }
1288 }
1289
1290 static inline bool isFirstAncestor(unsigned ancestorPositionSinceDescendantRelation)
1291 {
1292     return ancestorPositionSinceDescendantRelation == 1;
1293 }
1294
1295 static inline bool isFirstAdjacent(unsigned adjacentPositionSinceIndirectAdjacentTreeWalk)
1296 {
1297     return adjacentPositionSinceIndirectAdjacentTreeWalk == 1;
1298 }
1299
1300 static inline BacktrackingAction solveDescendantBacktrackingActionForChild(const SelectorFragment& fragment, unsigned backtrackingStartHeightFromDescendant)
1301 {
1302     // If height is invalid (e.g. There's no tag name).
1303     if (backtrackingStartHeightFromDescendant == invalidHeight)
1304         return BacktrackingAction::NoBacktracking;
1305
1306     // Start backtracking from the current element.
1307     if (backtrackingStartHeightFromDescendant == fragment.heightFromDescendant)
1308         return BacktrackingAction::JumpToDescendantEntryPoint;
1309
1310     // Start backtracking from the parent of current element.
1311     if (backtrackingStartHeightFromDescendant == (fragment.heightFromDescendant + 1))
1312         return BacktrackingAction::JumpToDescendantTreeWalkerEntryPoint;
1313
1314     return BacktrackingAction::JumpToDescendantTail;
1315 }
1316
1317 static inline BacktrackingAction solveAdjacentBacktrackingActionForDirectAdjacent(const SelectorFragment& fragment, unsigned backtrackingStartWidthFromIndirectAdjacent)
1318 {
1319     // If width is invalid (e.g. There's no tag name).
1320     if (backtrackingStartWidthFromIndirectAdjacent == invalidWidth)
1321         return BacktrackingAction::NoBacktracking;
1322
1323     // Start backtracking from the current element.
1324     if (backtrackingStartWidthFromIndirectAdjacent == fragment.widthFromIndirectAdjacent)
1325         return BacktrackingAction::JumpToIndirectAdjacentEntryPoint;
1326
1327     // Start backtracking from the previous adjacent of current element.
1328     if (backtrackingStartWidthFromIndirectAdjacent == (fragment.widthFromIndirectAdjacent + 1))
1329         return BacktrackingAction::JumpToIndirectAdjacentTreeWalkerEntryPoint;
1330
1331     return BacktrackingAction::JumpToDirectAdjacentTail;
1332 }
1333
1334 static inline BacktrackingAction solveAdjacentTraversalBacktrackingAction(const SelectorFragment& fragment, bool hasDescendantRelationOnTheRight)
1335 {
1336     if (!hasDescendantRelationOnTheRight)
1337         return BacktrackingAction::NoBacktracking;
1338
1339     if (fragment.tagNameMatchedBacktrackingStartHeightFromDescendant == (fragment.heightFromDescendant + 1))
1340         return BacktrackingAction::JumpToDescendantTreeWalkerEntryPoint;
1341
1342     return BacktrackingAction::JumpToDescendantTail;
1343 }
1344
1345 static inline void solveBacktrackingAction(SelectorFragment& fragment, bool hasDescendantRelationOnTheRight, bool hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain)
1346 {
1347     switch (fragment.relationToRightFragment) {
1348     case FragmentRelation::Rightmost:
1349     case FragmentRelation::Descendant:
1350         break;
1351     case FragmentRelation::Child:
1352         // Failure to match the element should resume matching at the nearest ancestor/descendant entry point.
1353         if (hasDescendantRelationOnTheRight) {
1354             fragment.matchingTagNameBacktrackingAction = solveDescendantBacktrackingActionForChild(fragment, fragment.tagNameNotMatchedBacktrackingStartHeightFromDescendant);
1355             fragment.matchingPostTagNameBacktrackingAction = solveDescendantBacktrackingActionForChild(fragment, fragment.tagNameMatchedBacktrackingStartHeightFromDescendant);
1356         }
1357         break;
1358     case FragmentRelation::DirectAdjacent:
1359         // Failure on traversal implies no other sibling traversal can match. Matching should resume at the
1360         // nearest ancestor/descendant traversal.
1361         fragment.traversalBacktrackingAction = solveAdjacentTraversalBacktrackingAction(fragment, hasDescendantRelationOnTheRight);
1362
1363         // If the rightmost relation is a indirect adjacent, matching sould resume from there.
1364         // Otherwise, we resume from the latest ancestor/descendant if any.
1365         if (hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain) {
1366             fragment.matchingTagNameBacktrackingAction = solveAdjacentBacktrackingActionForDirectAdjacent(fragment, fragment.tagNameNotMatchedBacktrackingStartWidthFromIndirectAdjacent);
1367             fragment.matchingPostTagNameBacktrackingAction = solveAdjacentBacktrackingActionForDirectAdjacent(fragment, fragment.tagNameMatchedBacktrackingStartWidthFromIndirectAdjacent);
1368         } else if (hasDescendantRelationOnTheRight) {
1369             // Since we resume from the latest ancestor/descendant, the action is the same as the traversal action.
1370             fragment.matchingTagNameBacktrackingAction = fragment.traversalBacktrackingAction;
1371             fragment.matchingPostTagNameBacktrackingAction = fragment.traversalBacktrackingAction;
1372         }
1373         break;
1374     case FragmentRelation::IndirectAdjacent:
1375         // Failure on traversal implies no other sibling matching will succeed. Matching can resume
1376         // from the latest ancestor/descendant.
1377         fragment.traversalBacktrackingAction = solveAdjacentTraversalBacktrackingAction(fragment, hasDescendantRelationOnTheRight);
1378         break;
1379     }
1380 }
1381
1382 enum class TagNameEquality {
1383     StrictlyNotEqual,
1384     MaybeEqual,
1385     StrictlyEqual
1386 };
1387
1388 static inline TagNameEquality equalTagNames(const CSSSelector* lhs, const CSSSelector* rhs)
1389 {
1390     if (!lhs || !rhs)
1391         return TagNameEquality::MaybeEqual;
1392
1393     const QualifiedName& lhsQualifiedName = lhs->tagQName();
1394     if (lhsQualifiedName == anyQName())
1395         return TagNameEquality::MaybeEqual;
1396
1397     const QualifiedName& rhsQualifiedName = rhs->tagQName();
1398     if (rhsQualifiedName == anyQName())
1399         return TagNameEquality::MaybeEqual;
1400
1401     const AtomicString& lhsLocalName = lhsQualifiedName.localName();
1402     const AtomicString& rhsLocalName = rhsQualifiedName.localName();
1403     if (lhsLocalName != starAtom() && rhsLocalName != starAtom()) {
1404         const AtomicString& lhsLowercaseLocalName = lhs->tagLowercaseLocalName();
1405         const AtomicString& rhsLowercaseLocalName = rhs->tagLowercaseLocalName();
1406
1407         if (lhsLowercaseLocalName != rhsLowercaseLocalName)
1408             return TagNameEquality::StrictlyNotEqual;
1409
1410         if (lhsLocalName == lhsLowercaseLocalName && rhsLocalName == rhsLowercaseLocalName)
1411             return TagNameEquality::StrictlyEqual;
1412         return TagNameEquality::MaybeEqual;
1413     }
1414
1415     const AtomicString& lhsNamespaceURI = lhsQualifiedName.namespaceURI();
1416     const AtomicString& rhsNamespaceURI = rhsQualifiedName.namespaceURI();
1417     if (lhsNamespaceURI != starAtom() && rhsNamespaceURI != starAtom()) {
1418         if (lhsNamespaceURI != rhsNamespaceURI)
1419             return TagNameEquality::StrictlyNotEqual;
1420         return TagNameEquality::StrictlyEqual;
1421     }
1422
1423     return TagNameEquality::MaybeEqual;
1424 }
1425
1426 static inline bool equalTagNamePatterns(const TagNamePattern& lhs, const TagNamePattern& rhs)
1427 {
1428     TagNameEquality result = equalTagNames(lhs.tagNameSelector, rhs.tagNameSelector);
1429     if (result == TagNameEquality::MaybeEqual)
1430         return true;
1431
1432     // If both rhs & lhs have actual localName (or NamespaceURI),
1433     // TagNameEquality result becomes StrictlyEqual or StrictlyNotEqual Since inverted lhs never matches on rhs.
1434     bool equal = result == TagNameEquality::StrictlyEqual;
1435     if (lhs.inverted)
1436         return !equal;
1437     return equal;
1438 }
1439
1440 // Find the largest matching prefix from already known tagNames.
1441 // And by using this, compute an appropriate height of backtracking start element from the closest base element in the chain.
1442 static inline unsigned computeBacktrackingStartOffsetInChain(const TagNameList& tagNames, unsigned maxPrefixSize)
1443 {
1444     RELEASE_ASSERT(!tagNames.isEmpty());
1445     RELEASE_ASSERT(maxPrefixSize < tagNames.size());
1446
1447     for (unsigned largestPrefixSize = maxPrefixSize; largestPrefixSize > 0; --largestPrefixSize) {
1448         unsigned offsetToLargestPrefix = tagNames.size() - largestPrefixSize;
1449         bool matched = true;
1450         // Since TagNamePatterns are pushed to a tagNames, check tagNames with reverse order.
1451         for (unsigned i = 0; i < largestPrefixSize; ++i) {
1452             unsigned lastIndex = tagNames.size() - 1;
1453             unsigned currentIndex = lastIndex - i;
1454             if (!equalTagNamePatterns(tagNames[currentIndex], tagNames[currentIndex - offsetToLargestPrefix])) {
1455                 matched = false;
1456                 break;
1457             }
1458         }
1459         if (matched)
1460             return offsetToLargestPrefix;
1461     }
1462     return tagNames.size();
1463 }
1464
1465 static inline void computeBacktrackingHeightFromDescendant(SelectorFragment& fragment, TagNameList& tagNamesForChildChain, bool hasDescendantRelationOnTheRight, const SelectorFragment*& previousChildFragmentInChildChain)
1466 {
1467     if (!hasDescendantRelationOnTheRight)
1468         return;
1469
1470     if (fragment.relationToRightFragment == FragmentRelation::Descendant) {
1471         tagNamesForChildChain.clear();
1472
1473         TagNamePattern pattern;
1474         pattern.tagNameSelector = fragment.tagNameSelector;
1475         tagNamesForChildChain.append(pattern);
1476         fragment.heightFromDescendant = 0;
1477         previousChildFragmentInChildChain = nullptr;
1478     } else if (fragment.relationToRightFragment == FragmentRelation::Child) {
1479         TagNamePattern pattern;
1480         pattern.tagNameSelector = fragment.tagNameSelector;
1481         tagNamesForChildChain.append(pattern);
1482
1483         unsigned maxPrefixSize = tagNamesForChildChain.size() - 1;
1484         if (previousChildFragmentInChildChain) {
1485             RELEASE_ASSERT(tagNamesForChildChain.size() >= previousChildFragmentInChildChain->tagNameMatchedBacktrackingStartHeightFromDescendant);
1486             maxPrefixSize = tagNamesForChildChain.size() - previousChildFragmentInChildChain->tagNameMatchedBacktrackingStartHeightFromDescendant;
1487         }
1488
1489         if (pattern.tagNameSelector) {
1490             // Compute height from descendant in the case that tagName is not matched.
1491             tagNamesForChildChain.last().inverted = true;
1492             fragment.tagNameNotMatchedBacktrackingStartHeightFromDescendant = computeBacktrackingStartOffsetInChain(tagNamesForChildChain, maxPrefixSize);
1493         }
1494
1495         // Compute height from descendant in the case that tagName is matched.
1496         tagNamesForChildChain.last().inverted = false;
1497         fragment.tagNameMatchedBacktrackingStartHeightFromDescendant = computeBacktrackingStartOffsetInChain(tagNamesForChildChain, maxPrefixSize);
1498         fragment.heightFromDescendant = tagNamesForChildChain.size() - 1;
1499         previousChildFragmentInChildChain = &fragment;
1500     } else {
1501         if (previousChildFragmentInChildChain) {
1502             fragment.tagNameNotMatchedBacktrackingStartHeightFromDescendant = previousChildFragmentInChildChain->tagNameNotMatchedBacktrackingStartHeightFromDescendant;
1503             fragment.tagNameMatchedBacktrackingStartHeightFromDescendant = previousChildFragmentInChildChain->tagNameMatchedBacktrackingStartHeightFromDescendant;
1504             fragment.heightFromDescendant = previousChildFragmentInChildChain->heightFromDescendant;
1505         } else {
1506             fragment.tagNameNotMatchedBacktrackingStartHeightFromDescendant = tagNamesForChildChain.size();
1507             fragment.tagNameMatchedBacktrackingStartHeightFromDescendant = tagNamesForChildChain.size();
1508             fragment.heightFromDescendant = 0;
1509         }
1510     }
1511 }
1512
1513 static inline void computeBacktrackingWidthFromIndirectAdjacent(SelectorFragment& fragment, TagNameList& tagNamesForDirectAdjacentChain, bool hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain, const SelectorFragment*& previousDirectAdjacentFragmentInDirectAdjacentChain)
1514 {
1515     if (!hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain)
1516         return;
1517
1518     if (fragment.relationToRightFragment == FragmentRelation::IndirectAdjacent) {
1519         tagNamesForDirectAdjacentChain.clear();
1520
1521         TagNamePattern pattern;
1522         pattern.tagNameSelector = fragment.tagNameSelector;
1523         tagNamesForDirectAdjacentChain.append(pattern);
1524         fragment.widthFromIndirectAdjacent = 0;
1525         previousDirectAdjacentFragmentInDirectAdjacentChain = nullptr;
1526     } else if (fragment.relationToRightFragment == FragmentRelation::DirectAdjacent) {
1527         TagNamePattern pattern;
1528         pattern.tagNameSelector = fragment.tagNameSelector;
1529         tagNamesForDirectAdjacentChain.append(pattern);
1530
1531         unsigned maxPrefixSize = tagNamesForDirectAdjacentChain.size() - 1;
1532         if (previousDirectAdjacentFragmentInDirectAdjacentChain) {
1533             RELEASE_ASSERT(tagNamesForDirectAdjacentChain.size() >= previousDirectAdjacentFragmentInDirectAdjacentChain->tagNameMatchedBacktrackingStartWidthFromIndirectAdjacent);
1534             maxPrefixSize = tagNamesForDirectAdjacentChain.size() - previousDirectAdjacentFragmentInDirectAdjacentChain->tagNameMatchedBacktrackingStartWidthFromIndirectAdjacent;
1535         }
1536
1537         if (pattern.tagNameSelector) {
1538             // Compute height from descendant in the case that tagName is not matched.
1539             tagNamesForDirectAdjacentChain.last().inverted = true;
1540             fragment.tagNameNotMatchedBacktrackingStartWidthFromIndirectAdjacent = computeBacktrackingStartOffsetInChain(tagNamesForDirectAdjacentChain, maxPrefixSize);
1541         }
1542
1543         // Compute height from descendant in the case that tagName is matched.
1544         tagNamesForDirectAdjacentChain.last().inverted = false;
1545         fragment.tagNameMatchedBacktrackingStartWidthFromIndirectAdjacent = computeBacktrackingStartOffsetInChain(tagNamesForDirectAdjacentChain, maxPrefixSize);
1546         fragment.widthFromIndirectAdjacent = tagNamesForDirectAdjacentChain.size() - 1;
1547         previousDirectAdjacentFragmentInDirectAdjacentChain = &fragment;
1548     }
1549 }
1550
1551 static bool requiresAdjacentTail(const SelectorFragment& fragment)
1552 {
1553     ASSERT(fragment.traversalBacktrackingAction != BacktrackingAction::JumpToDirectAdjacentTail);
1554     return fragment.matchingTagNameBacktrackingAction == BacktrackingAction::JumpToDirectAdjacentTail || fragment.matchingPostTagNameBacktrackingAction == BacktrackingAction::JumpToDirectAdjacentTail;
1555 }
1556
1557 static bool requiresDescendantTail(const SelectorFragment& fragment)
1558 {
1559     return fragment.matchingTagNameBacktrackingAction == BacktrackingAction::JumpToDescendantTail || fragment.matchingPostTagNameBacktrackingAction == BacktrackingAction::JumpToDescendantTail || fragment.traversalBacktrackingAction == BacktrackingAction::JumpToDescendantTail;
1560 }
1561
1562 void computeBacktrackingInformation(SelectorFragmentList& selectorFragments, unsigned level)
1563 {
1564     bool hasDescendantRelationOnTheRight = false;
1565     unsigned ancestorPositionSinceDescendantRelation = 0;
1566     bool hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain = false;
1567     unsigned adjacentPositionSinceIndirectAdjacentTreeWalk = 0;
1568
1569     bool needsAdjacentTail = false;
1570     bool needsDescendantTail = false;
1571     unsigned saveDescendantBacktrackingStartFragmentIndex = std::numeric_limits<unsigned>::max();
1572     unsigned saveIndirectAdjacentBacktrackingStartFragmentIndex = std::numeric_limits<unsigned>::max();
1573
1574     TagNameList tagNamesForChildChain;
1575     TagNameList tagNamesForDirectAdjacentChain;
1576     const SelectorFragment* previousChildFragmentInChildChain = nullptr;
1577     const SelectorFragment* previousDirectAdjacentFragmentInDirectAdjacentChain = nullptr;
1578
1579     for (unsigned i = 0; i < selectorFragments.size(); ++i) {
1580         SelectorFragment& fragment = selectorFragments[i];
1581
1582         updateChainStates(fragment, hasDescendantRelationOnTheRight, ancestorPositionSinceDescendantRelation, hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain, adjacentPositionSinceIndirectAdjacentTreeWalk);
1583
1584         computeBacktrackingHeightFromDescendant(fragment, tagNamesForChildChain, hasDescendantRelationOnTheRight, previousChildFragmentInChildChain);
1585
1586         computeBacktrackingWidthFromIndirectAdjacent(fragment, tagNamesForDirectAdjacentChain, hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain, previousDirectAdjacentFragmentInDirectAdjacentChain);
1587
1588 #if CSS_SELECTOR_JIT_DEBUGGING
1589         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);
1590 #endif
1591
1592         solveBacktrackingAction(fragment, hasDescendantRelationOnTheRight, hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain);
1593
1594         needsAdjacentTail |= requiresAdjacentTail(fragment);
1595         needsDescendantTail |= requiresDescendantTail(fragment);
1596
1597         // Add code generation flags.
1598         if (fragment.relationToLeftFragment != FragmentRelation::Descendant && fragment.relationToRightFragment == FragmentRelation::Descendant)
1599             fragment.backtrackingFlags |= BacktrackingFlag::DescendantEntryPoint;
1600         if (fragment.relationToLeftFragment == FragmentRelation::DirectAdjacent && fragment.relationToRightFragment == FragmentRelation::IndirectAdjacent)
1601             fragment.backtrackingFlags |= BacktrackingFlag::IndirectAdjacentEntryPoint;
1602         if (fragment.relationToLeftFragment != FragmentRelation::Descendant && fragment.relationToRightFragment == FragmentRelation::Child && isFirstAncestor(ancestorPositionSinceDescendantRelation)) {
1603             ASSERT(saveDescendantBacktrackingStartFragmentIndex == std::numeric_limits<unsigned>::max());
1604             saveDescendantBacktrackingStartFragmentIndex = i;
1605         }
1606         if (fragment.relationToLeftFragment == FragmentRelation::DirectAdjacent && fragment.relationToRightFragment == FragmentRelation::DirectAdjacent && isFirstAdjacent(adjacentPositionSinceIndirectAdjacentTreeWalk)) {
1607             ASSERT(saveIndirectAdjacentBacktrackingStartFragmentIndex == std::numeric_limits<unsigned>::max());
1608             saveIndirectAdjacentBacktrackingStartFragmentIndex = i;
1609         }
1610         if (fragment.relationToLeftFragment != FragmentRelation::DirectAdjacent) {
1611             if (needsAdjacentTail) {
1612                 ASSERT(fragment.relationToRightFragment == FragmentRelation::DirectAdjacent);
1613                 ASSERT(saveIndirectAdjacentBacktrackingStartFragmentIndex != std::numeric_limits<unsigned>::max());
1614                 fragment.backtrackingFlags |= BacktrackingFlag::DirectAdjacentTail;
1615                 selectorFragments[saveIndirectAdjacentBacktrackingStartFragmentIndex].backtrackingFlags |= BacktrackingFlag::SaveAdjacentBacktrackingStart;
1616                 needsAdjacentTail = false;
1617                 for (unsigned j = saveIndirectAdjacentBacktrackingStartFragmentIndex; j <= i; ++j)
1618                     selectorFragments[j].backtrackingFlags |= BacktrackingFlag::InChainWithAdjacentTail;
1619             }
1620             saveIndirectAdjacentBacktrackingStartFragmentIndex = std::numeric_limits<unsigned>::max();
1621         }
1622         if (fragment.relationToLeftFragment == FragmentRelation::Descendant) {
1623             if (needsDescendantTail) {
1624                 ASSERT(saveDescendantBacktrackingStartFragmentIndex != std::numeric_limits<unsigned>::max());
1625                 fragment.backtrackingFlags |= BacktrackingFlag::DescendantTail;
1626                 selectorFragments[saveDescendantBacktrackingStartFragmentIndex].backtrackingFlags |= BacktrackingFlag::SaveDescendantBacktrackingStart;
1627                 needsDescendantTail = false;
1628                 for (unsigned j = saveDescendantBacktrackingStartFragmentIndex; j <= i; ++j)
1629                     selectorFragments[j].backtrackingFlags |= BacktrackingFlag::InChainWithDescendantTail;
1630             }
1631             saveDescendantBacktrackingStartFragmentIndex = std::numeric_limits<unsigned>::max();
1632         }
1633     }
1634
1635     for (SelectorFragment& fragment : selectorFragments) {
1636         if (!fragment.notFilters.isEmpty()) {
1637 #if CSS_SELECTOR_JIT_DEBUGGING
1638             dataLogF("%*s  Subselectors for :not():\n", level * 4, "");
1639 #endif
1640
1641             for (SelectorFragmentList& selectorList : fragment.notFilters)
1642                 computeBacktrackingInformation(selectorList, level + 1);
1643         }
1644
1645         if (!fragment.matchesFilters.isEmpty()) {
1646             for (SelectorList& matchesList : fragment.matchesFilters) {
1647 #if CSS_SELECTOR_JIT_DEBUGGING
1648                 dataLogF("%*s  Subselectors for :matches():\n", level * 4, "");
1649 #endif
1650
1651                 for (SelectorFragmentList& selectorList : matchesList)
1652                     computeBacktrackingInformation(selectorList, level + 1);
1653             }
1654         }
1655
1656         for (NthChildOfSelectorInfo& nthChildOfSelectorInfo : fragment.nthChildOfFilters) {
1657 #if CSS_SELECTOR_JIT_DEBUGGING
1658             dataLogF("%*s  Subselectors for %dn+%d:\n", level * 4, "", nthChildOfSelectorInfo.a, nthChildOfSelectorInfo.b);
1659 #endif
1660
1661             for (SelectorFragmentList& selectorList : nthChildOfSelectorInfo.selectorList)
1662                 computeBacktrackingInformation(selectorList, level + 1);
1663         }
1664
1665         for (NthChildOfSelectorInfo& nthLastChildOfSelectorInfo : fragment.nthLastChildOfFilters) {
1666 #if CSS_SELECTOR_JIT_DEBUGGING
1667             dataLogF("%*s  Subselectors for %dn+%d:\n", level * 4, "", nthLastChildOfSelectorInfo.a, nthLastChildOfSelectorInfo.b);
1668 #endif
1669
1670             for (SelectorFragmentList& selectorList : nthLastChildOfSelectorInfo.selectorList)
1671                 computeBacktrackingInformation(selectorList, level + 1);
1672         }
1673     }
1674 }
1675
1676 inline void SelectorCodeGenerator::pushMacroAssemblerRegisters()
1677 {
1678 #if CPU(ARM_THUMB2)
1679     // r6 is tempRegister in RegisterAllocator.h and addressTempRegister in MacroAssemblerARMv7.h and must be preserved by the callee.
1680     Vector<JSC::MacroAssembler::RegisterID, 1> macroAssemblerRegisters({ JSC::ARMRegisters::r6 });
1681     m_macroAssemblerRegistersStackReferences = m_stackAllocator.push(macroAssemblerRegisters);
1682 #endif
1683 }
1684
1685 inline void SelectorCodeGenerator::popMacroAssemblerRegisters(StackAllocator& stackAllocator)
1686 {
1687 #if CPU(ARM_THUMB2)
1688     Vector<JSC::MacroAssembler::RegisterID, 1> macroAssemblerRegisters({ JSC::ARMRegisters::r6 });
1689     stackAllocator.pop(m_macroAssemblerRegistersStackReferences, macroAssemblerRegisters);
1690 #else
1691     UNUSED_PARAM(stackAllocator);
1692 #endif
1693 }
1694
1695 inline bool SelectorCodeGenerator::generatePrologue()
1696 {
1697 #if CPU(ARM64)
1698     Vector<JSC::MacroAssembler::RegisterID, 2> prologueRegisters;
1699     prologueRegisters.append(JSC::ARM64Registers::lr);
1700     prologueRegisters.append(JSC::ARM64Registers::fp);
1701     m_prologueStackReferences = m_stackAllocator.push(prologueRegisters);
1702     return true;
1703 #elif CPU(ARM_THUMB2)
1704     Vector<JSC::MacroAssembler::RegisterID, 1> prologueRegisters;
1705     prologueRegisters.append(JSC::ARMRegisters::lr);
1706     m_prologueStackReferences = m_stackAllocator.push(prologueRegisters);
1707     return true;
1708 #elif CPU(X86_64) && CSS_SELECTOR_JIT_DEBUGGING
1709     Vector<JSC::MacroAssembler::RegisterID, 1> prologueRegister;
1710     prologueRegister.append(callFrameRegister);
1711     m_prologueStackReferences = m_stackAllocator.push(prologueRegister);
1712     return true;
1713 #endif
1714     return false;
1715 }
1716
1717 inline void SelectorCodeGenerator::generateEpilogue(StackAllocator& stackAllocator)
1718 {
1719 #if CPU(ARM64)
1720     Vector<JSC::MacroAssembler::RegisterID, 2> prologueRegisters({ JSC::ARM64Registers::lr, JSC::ARM64Registers::fp });
1721     stackAllocator.pop(m_prologueStackReferences, prologueRegisters);
1722 #elif CPU(ARM_THUMB2)
1723     Vector<JSC::MacroAssembler::RegisterID, 1> prologueRegister({ JSC::ARMRegisters::lr });
1724     stackAllocator.pop(m_prologueStackReferences, prologueRegister);
1725 #elif CPU(X86_64) && CSS_SELECTOR_JIT_DEBUGGING
1726     Vector<JSC::MacroAssembler::RegisterID, 1> prologueRegister({ callFrameRegister });
1727     stackAllocator.pop(m_prologueStackReferences, prologueRegister);
1728 #else
1729     UNUSED_PARAM(stackAllocator);
1730 #endif
1731 }
1732
1733 static bool isAdjacentRelation(FragmentRelation relation)
1734 {
1735     return relation == FragmentRelation::DirectAdjacent || relation == FragmentRelation::IndirectAdjacent;
1736 }
1737
1738 static bool shouldMarkStyleIsAffectedByPreviousSibling(const SelectorFragment& fragment)
1739 {
1740     return isAdjacentRelation(fragment.relationToLeftFragment) && !isAdjacentRelation(fragment.relationToRightFragment);
1741 }
1742
1743 void SelectorCodeGenerator::generateSelectorChecker()
1744 {
1745     m_assembler.tagReturnAddress();
1746     pushMacroAssemblerRegisters();
1747     StackAllocator earlyFailureStack = m_stackAllocator;
1748
1749     Assembler::JumpList failureOnFunctionEntry;
1750     // Test selector's pseudo element equals to requested PseudoId.
1751     if (m_selectorContext != SelectorContext::QuerySelector && m_functionType == FunctionType::SelectorCheckerWithCheckingContext) {
1752         ASSERT_WITH_MESSAGE(fragmentMatchesTheRightmostElement(m_selectorFragments.first()), "Matching pseudo elements only make sense for the rightmost fragment.");
1753         generateRequestedPseudoElementEqualsToSelectorPseudoElement(failureOnFunctionEntry, m_selectorFragments.first(), checkingContextRegister);
1754     }
1755
1756     if (m_selectorContext == SelectorContext::RuleCollector) {
1757         unsigned specificity = m_selectorFragments.staticSpecificity;
1758         if (m_functionType == FunctionType::SelectorCheckerWithCheckingContext)
1759             m_assembler.store32(Assembler::TrustedImm32(specificity), JSC::GPRInfo::argumentGPR2);
1760         else
1761             m_assembler.store32(Assembler::TrustedImm32(specificity), JSC::GPRInfo::argumentGPR1);
1762     }
1763
1764     computeBacktrackingMemoryRequirements(m_selectorFragments);
1765     unsigned availableRegisterCount = m_registerAllocator.reserveCallerSavedRegisters(m_selectorFragments.registerRequirements);
1766
1767 #if CSS_SELECTOR_JIT_DEBUGGING
1768     dataLogF("Compiling with minimum required register count %u, minimum stack space %u\n", m_selectorFragments.registerRequirements, m_selectorFragments.stackRequirements);
1769 #endif
1770
1771     // We do not want unbounded stack allocation for backtracking. Going down 8 enry points would already be incredibly inefficient.
1772     unsigned maximumBacktrackingAllocations = 8;
1773     if (m_selectorFragments.stackRequirements > maximumBacktrackingAllocations) {
1774         m_assembler.move(Assembler::TrustedImm32(0), returnRegister);
1775         popMacroAssemblerRegisters(m_stackAllocator);
1776         m_assembler.ret();
1777         return;
1778     }
1779
1780     bool needsEpilogue = generatePrologue();
1781
1782     StackAllocator::StackReferenceVector calleeSavedRegisterStackReferences;
1783     bool reservedCalleeSavedRegisters = false;
1784     ASSERT(m_selectorFragments.registerRequirements <= maximumRegisterCount);
1785     if (availableRegisterCount < m_selectorFragments.registerRequirements) {
1786         reservedCalleeSavedRegisters = true;
1787         calleeSavedRegisterStackReferences = m_stackAllocator.push(m_registerAllocator.reserveCalleeSavedRegisters(m_selectorFragments.registerRequirements - availableRegisterCount));
1788     }
1789
1790     m_registerAllocator.allocateRegister(elementAddressRegister);
1791
1792     StackAllocator::StackReference temporaryStackBase = m_stackAllocator.stackTop();
1793
1794     if (m_functionType == FunctionType::SelectorCheckerWithCheckingContext)
1795         m_checkingContextStackReference = m_stackAllocator.push(checkingContextRegister);
1796
1797     unsigned stackRequirementCount = m_selectorFragments.stackRequirements;
1798     if (m_visitedMode == VisitedMode::Visited)
1799         stackRequirementCount += 2;
1800
1801     StackAllocator::StackReferenceVector temporaryStack;
1802     if (stackRequirementCount)
1803         temporaryStack = m_stackAllocator.allocateUninitialized(stackRequirementCount);
1804
1805     if (m_visitedMode == VisitedMode::Visited) {
1806         m_lastVisitedElement = temporaryStack.takeLast();
1807         m_startElement = temporaryStack.takeLast();
1808         m_assembler.storePtr(elementAddressRegister, m_stackAllocator.addressOf(m_startElement));
1809         m_assembler.storePtr(Assembler::TrustedImmPtr(nullptr), m_stackAllocator.addressOf(m_lastVisitedElement));
1810     }
1811
1812     m_backtrackingStack = temporaryStack;
1813
1814     Assembler::JumpList failureCases;
1815     generateSelectorCheckerExcludingPseudoElements(failureCases, m_selectorFragments);
1816
1817     if (m_selectorContext != SelectorContext::QuerySelector && m_functionType == FunctionType::SelectorCheckerWithCheckingContext) {
1818         ASSERT(!m_selectorFragments.isEmpty());
1819         generateMarkPseudoStyleForPseudoElement(failureCases, m_selectorFragments.first());
1820     }
1821
1822     if (m_visitedMode == VisitedMode::Visited) {
1823         LocalRegister lastVisitedElement(m_registerAllocator);
1824         m_assembler.loadPtr(m_stackAllocator.addressOf(m_lastVisitedElement), lastVisitedElement);
1825         Assembler::Jump noLastVisitedElement = m_assembler.branchTestPtr(Assembler::Zero, lastVisitedElement);
1826         generateElementIsFirstLink(failureCases, lastVisitedElement);
1827         noLastVisitedElement.link(&m_assembler);
1828     }
1829
1830     m_registerAllocator.deallocateRegister(elementAddressRegister);
1831
1832     if (m_functionType == FunctionType::SimpleSelectorChecker) {
1833         if (temporaryStackBase == m_stackAllocator.stackTop() && !reservedCalleeSavedRegisters && !needsEpilogue) {
1834             StackAllocator successStack = m_stackAllocator;
1835             StackAllocator failureStack = m_stackAllocator;
1836
1837             ASSERT(!m_selectorFragments.stackRequirements);
1838             // Success.
1839             m_assembler.move(Assembler::TrustedImm32(1), returnRegister);
1840             popMacroAssemblerRegisters(successStack);
1841             m_assembler.ret();
1842
1843             // Failure.
1844             ASSERT_WITH_MESSAGE(failureOnFunctionEntry.empty(), "Early failure on function entry is used for pseudo element. When early failure is used, function type is SelectorCheckerWithCheckingContext.");
1845             if (!failureCases.empty()) {
1846                 failureCases.link(&m_assembler);
1847                 m_assembler.move(Assembler::TrustedImm32(0), returnRegister);
1848                 popMacroAssemblerRegisters(failureStack);
1849                 m_assembler.ret();
1850             } else
1851                 failureStack = successStack;
1852
1853             m_stackAllocator.merge(WTFMove(successStack), WTFMove(failureStack));
1854             return;
1855         }
1856     }
1857
1858     // Success.
1859     m_assembler.move(Assembler::TrustedImm32(1), returnRegister);
1860
1861     // Failure.
1862     if (!failureCases.empty()) {
1863         Assembler::Jump skipFailureCase = m_assembler.jump();
1864         failureCases.link(&m_assembler);
1865         m_assembler.move(Assembler::TrustedImm32(0), returnRegister);
1866         skipFailureCase.link(&m_assembler);
1867     }
1868
1869     if (temporaryStackBase != m_stackAllocator.stackTop())
1870         m_stackAllocator.popAndDiscardUpTo(temporaryStackBase);
1871     if (reservedCalleeSavedRegisters)
1872         m_stackAllocator.pop(calleeSavedRegisterStackReferences, m_registerAllocator.restoreCalleeSavedRegisters());
1873
1874     StackAllocator successStack = m_stackAllocator;
1875     if (needsEpilogue)
1876         generateEpilogue(successStack);
1877     popMacroAssemblerRegisters(successStack);
1878     m_assembler.ret();
1879
1880     // Early failure on function entry case.
1881     if (!failureOnFunctionEntry.empty()) {
1882         failureOnFunctionEntry.link(&m_assembler);
1883         m_assembler.move(Assembler::TrustedImm32(0), returnRegister);
1884         popMacroAssemblerRegisters(earlyFailureStack);
1885         m_assembler.ret();
1886     } else
1887         earlyFailureStack = successStack;
1888     m_stackAllocator.merge(WTFMove(successStack), WTFMove(earlyFailureStack));
1889 }
1890
1891 void SelectorCodeGenerator::generateSelectorCheckerExcludingPseudoElements(Assembler::JumpList& failureCases, const SelectorFragmentList& selectorFragmentList)
1892 {
1893     m_backtrackingLevels.append(BacktrackingLevel());
1894
1895     for (const SelectorFragment& fragment : selectorFragmentList) {
1896         switch (fragment.relationToRightFragment) {
1897         case FragmentRelation::Rightmost:
1898             generateRightmostTreeWalker(failureCases, fragment);
1899             break;
1900         case FragmentRelation::Descendant:
1901             generateAncestorTreeWalker(failureCases, fragment);
1902             break;
1903         case FragmentRelation::Child:
1904             generateParentElementTreeWalker(failureCases, fragment);
1905             break;
1906         case FragmentRelation::DirectAdjacent:
1907             generateDirectAdjacentTreeWalker(failureCases, fragment);
1908             break;
1909         case FragmentRelation::IndirectAdjacent:
1910             generateIndirectAdjacentTreeWalker(failureCases, fragment);
1911             break;
1912         }
1913         if (shouldMarkStyleIsAffectedByPreviousSibling(fragment)) {
1914             if (fragmentMatchesTheRightmostElement(fragment))
1915                 generateAddStyleRelationIfResolvingStyle(elementAddressRegister, Style::Relation::AffectedByPreviousSibling);
1916             else
1917                 generateAddStyleRelationIfResolvingStyle(elementAddressRegister, Style::Relation::DescendantsAffectedByPreviousSibling);
1918         }
1919         generateBacktrackingTailsIfNeeded(failureCases, fragment);
1920     }
1921
1922     ASSERT(!m_backtrackingLevels.last().descendantBacktrackingStart.isValid());
1923     ASSERT(!m_backtrackingLevels.last().adjacentBacktrackingStart.isValid());
1924     m_backtrackingLevels.takeLast();
1925 }
1926
1927 void SelectorCodeGenerator::generateElementMatchesSelectorList(Assembler::JumpList& failingCases, Assembler::RegisterID elementToMatch, const SelectorList& selectorList)
1928 {
1929     ASSERT(!selectorList.isEmpty());
1930
1931     RegisterVector registersToSave;
1932
1933     // The contract is that existing registers are preserved. Two special cases are elementToMatch and elementAddressRegister
1934     // because they are used by the matcher itself.
1935     // To simplify things for now, we just always preserve them on the stack.
1936     unsigned elementToTestIndex = std::numeric_limits<unsigned>::max();
1937     bool isElementToMatchOnStack = false;
1938     if (selectorList.clobberElementAddressRegister) {
1939         if (elementToMatch != elementAddressRegister) {
1940             registersToSave.append(elementAddressRegister);
1941             registersToSave.append(elementToMatch);
1942             elementToTestIndex = 1;
1943             isElementToMatchOnStack = true;
1944         } else {
1945             registersToSave.append(elementAddressRegister);
1946             elementToTestIndex = 0;
1947         }
1948     } else if (elementToMatch != elementAddressRegister)
1949         registersToSave.append(elementAddressRegister);
1950
1951     // Next, we need to free as many registers as needed by the nested selector list.
1952     unsigned availableRegisterCount = m_registerAllocator.availableRegisterCount();
1953
1954     // Do not count elementAddressRegister, it will remain allocated.
1955     ++availableRegisterCount;
1956
1957     if (isElementToMatchOnStack)
1958         ++availableRegisterCount;
1959
1960     if (selectorList.registerRequirements > availableRegisterCount) {
1961         unsigned registerToPushCount = selectorList.registerRequirements - availableRegisterCount;
1962         for (Assembler::RegisterID registerId : m_registerAllocator.allocatedRegisters()) {
1963             if (registerId == elementAddressRegister)
1964                 continue; // Handled separately above.
1965             if (isElementToMatchOnStack && registerId == elementToMatch)
1966                 continue; // Do not push the element twice to the stack!
1967
1968             registersToSave.append(registerId);
1969
1970             --registerToPushCount;
1971             if (!registerToPushCount)
1972                 break;
1973         }
1974     }
1975
1976     StackAllocator::StackReferenceVector allocatedRegistersOnStack = m_stackAllocator.push(registersToSave);
1977     for (Assembler::RegisterID registerID : registersToSave) {
1978         if (registerID != elementAddressRegister)
1979             m_registerAllocator.deallocateRegister(registerID);
1980     }
1981
1982
1983     if (elementToMatch != elementAddressRegister)
1984         m_assembler.move(elementToMatch, elementAddressRegister);
1985
1986     Assembler::JumpList localFailureCases;
1987     if (selectorList.size() == 1) {
1988         const SelectorFragmentList& nestedSelectorFragmentList = selectorList.first();
1989         generateSelectorCheckerExcludingPseudoElements(localFailureCases, nestedSelectorFragmentList);
1990     } else {
1991         Assembler::JumpList matchFragmentList;
1992
1993         unsigned selectorListSize = selectorList.size();
1994         unsigned selectorListLastIndex = selectorListSize - 1;
1995         for (unsigned i = 0; i < selectorList.size(); ++i) {
1996             const SelectorFragmentList& nestedSelectorFragmentList = selectorList[i];
1997             Assembler::JumpList localSelectorFailureCases;
1998             generateSelectorCheckerExcludingPseudoElements(localSelectorFailureCases, nestedSelectorFragmentList);
1999             if (i != selectorListLastIndex) {
2000                 matchFragmentList.append(m_assembler.jump());
2001                 localSelectorFailureCases.link(&m_assembler);
2002
2003                 if (nestedSelectorFragmentList.clobberElementAddressRegister) {
2004                     RELEASE_ASSERT(elementToTestIndex != std::numeric_limits<unsigned>::max());
2005                     m_assembler.loadPtr(m_stackAllocator.addressOf(allocatedRegistersOnStack[elementToTestIndex]), elementAddressRegister);
2006                 }
2007             } else
2008                 localFailureCases.append(localSelectorFailureCases);
2009         }
2010         matchFragmentList.link(&m_assembler);
2011     }
2012
2013     // Finally, restore all the registers in the state they were before this selector checker.
2014     for (Assembler::RegisterID registerID : registersToSave) {
2015         if (registerID != elementAddressRegister)
2016             m_registerAllocator.allocateRegister(registerID);
2017     }
2018
2019     if (allocatedRegistersOnStack.isEmpty()) {
2020         failingCases.append(localFailureCases);
2021         return;
2022     }
2023
2024     if (localFailureCases.empty())
2025         m_stackAllocator.pop(allocatedRegistersOnStack, registersToSave);
2026     else {
2027         StackAllocator successStack = m_stackAllocator;
2028         StackAllocator failureStack = m_stackAllocator;
2029
2030         successStack.pop(allocatedRegistersOnStack, registersToSave);
2031
2032         Assembler::Jump skipFailureCase = m_assembler.jump();
2033         localFailureCases.link(&m_assembler);
2034         failureStack.pop(allocatedRegistersOnStack, registersToSave);
2035         failingCases.append(m_assembler.jump());
2036
2037         skipFailureCase.link(&m_assembler);
2038
2039         m_stackAllocator.merge(WTFMove(successStack), WTFMove(failureStack));
2040     }
2041 }
2042
2043 void SelectorCodeGenerator::generateRightmostTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
2044 {
2045     generateElementMatching(failureCases, failureCases, fragment);
2046 }
2047
2048 void SelectorCodeGenerator::generateWalkToParentNode(Assembler::RegisterID targetRegister)
2049 {
2050     m_assembler.loadPtr(Assembler::Address(elementAddressRegister, Node::parentNodeMemoryOffset()), targetRegister);
2051 }
2052
2053 void SelectorCodeGenerator::generateWalkToParentElement(Assembler::JumpList& failureCases, Assembler::RegisterID targetRegister)
2054 {
2055     //    ContainerNode* parent = parentNode()
2056     //    if (!parent || !parent->isElementNode())
2057     //         failure
2058     generateWalkToParentNode(targetRegister);
2059     failureCases.append(m_assembler.branchTestPtr(Assembler::Zero, targetRegister));
2060     failureCases.append(DOMJIT::branchTestIsElementFlagOnNode(m_assembler, Assembler::Zero, targetRegister));
2061 }
2062
2063 void SelectorCodeGenerator::generateWalkToParentElementOrShadowRoot(Assembler::JumpList& failureCases, Assembler::RegisterID targetRegister)
2064 {
2065     //    ContainerNode* parent = parentNode()
2066     //    if (!parent || !(parent->isElementNode() || parent->isShadowRoot()))
2067     //         failure
2068     generateWalkToParentNode(targetRegister);
2069     failureCases.append(m_assembler.branchTestPtr(Assembler::Zero, targetRegister));
2070     failureCases.append(DOMJIT::branchTestIsElementOrShadowRootFlagOnNode(m_assembler, Assembler::Zero, targetRegister));
2071 }
2072
2073 void SelectorCodeGenerator::generateParentElementTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
2074 {
2075     Assembler::JumpList traversalFailureCases;
2076     generateWalkToParentElement(traversalFailureCases, elementAddressRegister);
2077     linkFailures(failureCases, fragment.traversalBacktrackingAction, traversalFailureCases);
2078
2079     Assembler::JumpList matchingTagNameFailureCases;
2080     Assembler::JumpList matchingPostTagNameFailureCases;
2081     generateElementMatching(matchingTagNameFailureCases, matchingPostTagNameFailureCases, fragment);
2082     linkFailures(failureCases, fragment.matchingTagNameBacktrackingAction, matchingTagNameFailureCases);
2083     linkFailures(failureCases, fragment.matchingPostTagNameBacktrackingAction, matchingPostTagNameFailureCases);
2084
2085     if (fragment.backtrackingFlags & BacktrackingFlag::SaveDescendantBacktrackingStart) {
2086         if (!m_descendantBacktrackingStartInUse) {
2087             m_descendantBacktrackingStart = m_registerAllocator.allocateRegister();
2088             m_assembler.move(elementAddressRegister, m_descendantBacktrackingStart);
2089             m_descendantBacktrackingStartInUse = true;
2090         } else {
2091             BacktrackingLevel& currentBacktrackingLevel = m_backtrackingLevels.last();
2092             ASSERT(!currentBacktrackingLevel.descendantBacktrackingStart.isValid());
2093             currentBacktrackingLevel.descendantBacktrackingStart = m_backtrackingStack.takeLast();
2094
2095             m_assembler.storePtr(elementAddressRegister, m_stackAllocator.addressOf(currentBacktrackingLevel.descendantBacktrackingStart));
2096         }
2097     }
2098 }
2099
2100 void SelectorCodeGenerator::generateAncestorTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
2101 {
2102     // Loop over the ancestors until one of them matches the fragment.
2103     Assembler::Label loopStart(m_assembler.label());
2104
2105     if (fragment.backtrackingFlags & BacktrackingFlag::DescendantEntryPoint)
2106         m_backtrackingLevels.last().descendantTreeWalkerBacktrackingPoint = m_assembler.label();
2107
2108     generateWalkToParentElement(failureCases, elementAddressRegister);
2109
2110     if (fragment.backtrackingFlags & BacktrackingFlag::DescendantEntryPoint)
2111         m_backtrackingLevels.last().descendantEntryPoint = m_assembler.label();
2112
2113     Assembler::JumpList matchingFailureCases;
2114     generateElementMatching(matchingFailureCases, matchingFailureCases, fragment);
2115     matchingFailureCases.linkTo(loopStart, &m_assembler);
2116 }
2117
2118 inline void SelectorCodeGenerator::generateWalkToNextAdjacentElement(Assembler::JumpList& failureCases, Assembler::RegisterID workRegister)
2119 {
2120     Assembler::Label loopStart = m_assembler.label();
2121     m_assembler.loadPtr(Assembler::Address(workRegister, Node::nextSiblingMemoryOffset()), workRegister);
2122     failureCases.append(m_assembler.branchTestPtr(Assembler::Zero, workRegister));
2123     DOMJIT::branchTestIsElementFlagOnNode(m_assembler, Assembler::Zero, workRegister).linkTo(loopStart, &m_assembler);
2124 }
2125
2126 inline void SelectorCodeGenerator::generateWalkToPreviousAdjacentElement(Assembler::JumpList& failureCases, Assembler::RegisterID workRegister)
2127 {
2128     Assembler::Label loopStart = m_assembler.label();
2129     m_assembler.loadPtr(Assembler::Address(workRegister, Node::previousSiblingMemoryOffset()), workRegister);
2130     failureCases.append(m_assembler.branchTestPtr(Assembler::Zero, workRegister));
2131     DOMJIT::branchTestIsElementFlagOnNode(m_assembler, Assembler::Zero, workRegister).linkTo(loopStart, &m_assembler);
2132 }
2133
2134 void SelectorCodeGenerator::generateWalkToPreviousAdjacent(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
2135 {
2136     //    do {
2137     //        previousSibling = previousSibling->previousSibling();
2138     //        if (!previousSibling)
2139     //            failure!
2140     //    while (!previousSibling->isElement());
2141     Assembler::RegisterID previousSibling;
2142     bool useTailOnTraversalFailure = fragment.traversalBacktrackingAction >= BacktrackingAction::JumpToDescendantTail;
2143     if (!useTailOnTraversalFailure) {
2144         // If the current fragment is not dependant on a previously saved elementAddressRegister, a fast recover
2145         // from a failure would resume with elementAddressRegister.
2146         // When walking to the previous sibling, the failure can be that previousSibling is null. We cannot backtrack
2147         // with a null elementAddressRegister so we do the traversal on a copy.
2148         previousSibling = m_registerAllocator.allocateRegister();
2149         m_assembler.move(elementAddressRegister, previousSibling);
2150     } else
2151         previousSibling = elementAddressRegister;
2152
2153     Assembler::JumpList traversalFailureCases;
2154     generateWalkToPreviousAdjacentElement(traversalFailureCases, previousSibling);
2155     linkFailures(failureCases, fragment.traversalBacktrackingAction, traversalFailureCases);
2156
2157     // On success, move previousSibling over to elementAddressRegister if we could not work on elementAddressRegister directly.
2158     if (!useTailOnTraversalFailure) {
2159         m_assembler.move(previousSibling, elementAddressRegister);
2160         m_registerAllocator.deallocateRegister(previousSibling);
2161     }
2162 }
2163
2164 void SelectorCodeGenerator::generateDirectAdjacentTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
2165 {
2166     generateWalkToPreviousAdjacent(failureCases, fragment);
2167     generateAddStyleRelationIfResolvingStyle(elementAddressRegister, Style::Relation::AffectsNextSibling);
2168
2169     Assembler::JumpList matchingTagNameFailureCases;
2170     Assembler::JumpList matchingPostTagNameFailureCases;
2171     generateElementMatching(matchingTagNameFailureCases, matchingPostTagNameFailureCases, fragment);
2172     linkFailures(failureCases, fragment.matchingTagNameBacktrackingAction, matchingTagNameFailureCases);
2173     linkFailures(failureCases, fragment.matchingPostTagNameBacktrackingAction, matchingPostTagNameFailureCases);
2174
2175     if (fragment.backtrackingFlags & BacktrackingFlag::SaveAdjacentBacktrackingStart) {
2176         BacktrackingLevel& currentBacktrackingLevel = m_backtrackingLevels.last();
2177         ASSERT(!currentBacktrackingLevel.adjacentBacktrackingStart.isValid());
2178         currentBacktrackingLevel.adjacentBacktrackingStart = m_backtrackingStack.takeLast();
2179
2180         m_assembler.storePtr(elementAddressRegister, m_stackAllocator.addressOf(currentBacktrackingLevel.adjacentBacktrackingStart));
2181     }
2182 }
2183
2184 void SelectorCodeGenerator::generateIndirectAdjacentTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
2185 {
2186     Assembler::Label loopStart(m_assembler.label());
2187
2188     if (fragment.backtrackingFlags & BacktrackingFlag::IndirectAdjacentEntryPoint)
2189         m_backtrackingLevels.last().indirectAdjacentTreeWalkerBacktrackingPoint = m_assembler.label();
2190
2191     generateWalkToPreviousAdjacent(failureCases, fragment);
2192     generateAddStyleRelationIfResolvingStyle(elementAddressRegister, Style::Relation::AffectsNextSibling);
2193
2194     if (fragment.backtrackingFlags & BacktrackingFlag::IndirectAdjacentEntryPoint)
2195         m_backtrackingLevels.last().indirectAdjacentEntryPoint = m_assembler.label();
2196
2197     Assembler::JumpList localFailureCases;
2198     generateElementMatching(localFailureCases, localFailureCases, fragment);
2199     localFailureCases.linkTo(loopStart, &m_assembler);
2200 }
2201
2202 void SelectorCodeGenerator::generateAddStyleRelationIfResolvingStyle(Assembler::RegisterID element, Style::Relation::Type relationType, std::optional<Assembler::RegisterID> value)
2203 {
2204     if (m_selectorContext == SelectorContext::QuerySelector)
2205         return;
2206
2207     LocalRegister checkingContext(m_registerAllocator);
2208     Assembler::Jump notResolvingStyle = jumpIfNotResolvingStyle(checkingContext);
2209
2210     generateAddStyleRelation(checkingContext, element, relationType, value);
2211
2212     notResolvingStyle.link(&m_assembler);
2213 }
2214
2215 static void addStyleRelationFunction(SelectorChecker::CheckingContext* checkingContext, const Element* element)
2216 {
2217     checkingContext->styleRelations.append({ *element, Style::Relation::AffectedByActive, 1 });
2218 }
2219
2220 void SelectorCodeGenerator::generateAddStyleRelation(Assembler::RegisterID checkingContext, Assembler::RegisterID element, Style::Relation::Type relationType, std::optional<Assembler::RegisterID> value)
2221 {
2222     ASSERT(m_selectorContext != SelectorContext::QuerySelector);
2223
2224     Assembler::Address vectorAddress(checkingContext, OBJECT_OFFSETOF(SelectorChecker::CheckingContext, styleRelations));
2225     auto dataAddress = vectorAddress.withOffset(Style::Relations::dataMemoryOffset());
2226     auto sizeAddress = vectorAddress.withOffset(Style::Relations::sizeMemoryOffset());
2227
2228     auto getLastRelationPointer = [&] (Assembler::RegisterID sizeAndTarget) {
2229         m_assembler.sub32(Assembler::TrustedImm32(1), sizeAndTarget);
2230 #if CPU(ADDRESS64)
2231         static_assert(sizeof(Style::Relation) == 16, "");
2232         static_assert(1 << 4 == 16, "");
2233         m_assembler.lshiftPtr(Assembler::TrustedImm32(4), sizeAndTarget);
2234 #else
2235         m_assembler.mul32(Assembler::TrustedImm32(sizeof(Style::Relation)), sizeAndTarget, sizeAndTarget);
2236 #endif
2237         m_assembler.addPtr(dataAddress, sizeAndTarget);
2238     };
2239
2240     // For AffectsNextSibling we just increment the count if the previous added relation was in the same sibling chain.
2241     Assembler::JumpList mergeSuccess;
2242     if (relationType == Style::Relation::AffectsNextSibling) {
2243         Assembler::JumpList mergeFailure;
2244
2245         LocalRegister lastRelation(m_registerAllocator);
2246         m_assembler.load32(sizeAddress, lastRelation);
2247
2248         // if (!checkingContext.styleRelations.isEmpty())
2249         mergeFailure.append(m_assembler.branchTest32(Assembler::Zero, lastRelation));
2250
2251         // Style::Relation& lastRelation = checkingContext.styleRelations.last();
2252         getLastRelationPointer(lastRelation);
2253
2254         // if (lastRelation.type == Style::Relation::AffectsNextSibling)
2255         Assembler::Address typeAddress(lastRelation, OBJECT_OFFSETOF(Style::Relation, type));
2256         mergeFailure.append(m_assembler.branch32(Assembler::NotEqual, typeAddress, Assembler::TrustedImm32(Style::Relation::AffectsNextSibling)));
2257
2258         Assembler::Address elementAddress(lastRelation, OBJECT_OFFSETOF(Style::Relation, element));
2259         {
2260             // if (element.nextSiblingElement() == lastRelation.element)
2261             LocalRegister nextSiblingElement(m_registerAllocator);
2262             m_assembler.move(element, nextSiblingElement);
2263             generateWalkToNextAdjacentElement(mergeFailure, nextSiblingElement);
2264             mergeFailure.append(m_assembler.branchPtr(Assembler::NotEqual, nextSiblingElement, elementAddress));
2265         }
2266
2267         // ++lastRelation.value;
2268         Assembler::Address valueAddress(lastRelation, OBJECT_OFFSETOF(Style::Relation, value));
2269         m_assembler.add32(Assembler::TrustedImm32(1), valueAddress);
2270
2271         // lastRelation.element = &element;
2272         m_assembler.storePtr(element, elementAddress);
2273
2274         mergeSuccess.append(m_assembler.jump());
2275         mergeFailure.link(&m_assembler);
2276     }
2277
2278     // FIXME: Append to vector without a function call at least when there is sufficient capacity.
2279     FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2280     functionCall.setFunctionAddress(addStyleRelationFunction);
2281     functionCall.setTwoArguments(checkingContext, element);
2282     functionCall.call();
2283
2284     LocalRegister relationPointer(m_registerAllocator);
2285     m_assembler.load32(sizeAddress, relationPointer);
2286     getLastRelationPointer(relationPointer);
2287
2288     Assembler::Address typeAddress(relationPointer, OBJECT_OFFSETOF(Style::Relation, type));
2289     m_assembler.store32(Assembler::TrustedImm32(relationType), typeAddress);
2290
2291     if (value) {
2292         Assembler::Address valueAddress(relationPointer, OBJECT_OFFSETOF(Style::Relation, value));
2293         m_assembler.store32(*value, valueAddress);
2294     }
2295
2296     mergeSuccess.link(&m_assembler);
2297 }
2298
2299 Assembler::JumpList SelectorCodeGenerator::jumpIfNoPreviousAdjacentElement()
2300 {
2301     Assembler::JumpList successCase;
2302     LocalRegister previousSibling(m_registerAllocator);
2303     m_assembler.move(elementAddressRegister, previousSibling);
2304     generateWalkToPreviousAdjacentElement(successCase, previousSibling);
2305     return successCase;
2306 }
2307
2308 Assembler::JumpList SelectorCodeGenerator::jumpIfNoNextAdjacentElement()
2309 {
2310     Assembler::JumpList successCase;
2311     LocalRegister nextSibling(m_registerAllocator);
2312     m_assembler.move(elementAddressRegister, nextSibling);
2313     generateWalkToNextAdjacentElement(successCase, nextSibling);
2314     return successCase;
2315 }
2316
2317
2318 void SelectorCodeGenerator::loadCheckingContext(Assembler::RegisterID checkingContext)
2319 {
2320     // Get the checking context.
2321     RELEASE_ASSERT(m_functionType == FunctionType::SelectorCheckerWithCheckingContext);
2322     m_assembler.loadPtr(m_stackAllocator.addressOf(m_checkingContextStackReference), checkingContext);
2323 }
2324
2325 Assembler::Jump SelectorCodeGenerator::branchOnResolvingModeWithCheckingContext(Assembler::RelationalCondition condition, SelectorChecker::Mode mode, Assembler::RegisterID checkingContext)
2326 {
2327     // Depend on the specified resolving mode and our current mode, branch.
2328     static_assert(sizeof(SelectorChecker::Mode) == 1, "We generate a byte load/test for the SelectorChecker::Mode.");
2329     return m_assembler.branch8(condition, Assembler::Address(checkingContext, OBJECT_OFFSETOF(SelectorChecker::CheckingContext, resolvingMode)), Assembler::TrustedImm32(static_cast<std::underlying_type<SelectorChecker::Mode>::type>(mode)));
2330
2331 }
2332
2333 Assembler::Jump SelectorCodeGenerator::branchOnResolvingMode(Assembler::RelationalCondition condition, SelectorChecker::Mode mode, Assembler::RegisterID checkingContext)
2334 {
2335     loadCheckingContext(checkingContext);
2336     return branchOnResolvingModeWithCheckingContext(condition, mode, checkingContext);
2337 }
2338
2339 Assembler::Jump SelectorCodeGenerator::jumpIfNotResolvingStyle(Assembler::RegisterID checkingContext)
2340 {
2341     return branchOnResolvingMode(Assembler::NotEqual, SelectorChecker::Mode::ResolvingStyle, checkingContext);
2342 }
2343
2344 void SelectorCodeGenerator::generateSpecialFailureInQuirksModeForActiveAndHoverIfNeeded(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
2345 {
2346     if (fragment.onlyMatchesLinksInQuirksMode) {
2347         // If the element is a link, it can always match :hover or :active.
2348         Assembler::Jump isLink = m_assembler.branchTest32(Assembler::NonZero, Assembler::Address(elementAddressRegister, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagIsLink()));
2349
2350         // Only quirks mode restrict :hover and :active.
2351         static_assert(sizeof(DocumentCompatibilityMode) == 1, "We generate a byte load/test for the compatibility mode.");
2352         LocalRegister documentAddress(m_registerAllocator);
2353         DOMJIT::loadDocument(m_assembler, elementAddressRegister, documentAddress);
2354         failureCases.append(m_assembler.branchTest8(Assembler::NonZero, Assembler::Address(documentAddress, Document::compatibilityModeMemoryOffset()), Assembler::TrustedImm32(static_cast<std::underlying_type<DocumentCompatibilityMode>::type>(DocumentCompatibilityMode::QuirksMode))));
2355
2356         isLink.link(&m_assembler);
2357     }
2358 }
2359
2360 #if CPU(ARM_THUMB2) && !CPU(APPLE_ARMV7S)
2361 // FIXME: This could be implemented in assembly to avoid a function call, and we know the divisor at jit-compile time.
2362 static int moduloHelper(int dividend, int divisor)
2363 {
2364     return dividend % divisor;
2365 }
2366 #endif
2367
2368 // The value in inputDividend is destroyed by the modulo operation.
2369 Assembler::Jump SelectorCodeGenerator::modulo(Assembler::ResultCondition condition, Assembler::RegisterID inputDividend, int divisor)
2370 {
2371     RELEASE_ASSERT(divisor);
2372 #if CPU(ARM64) || CPU(APPLE_ARMV7S)
2373     LocalRegister divisorRegister(m_registerAllocator);
2374     m_assembler.move(Assembler::TrustedImm32(divisor), divisorRegister);
2375
2376     LocalRegister resultRegister(m_registerAllocator);
2377     m_assembler.m_assembler.sdiv<32>(resultRegister, inputDividend, divisorRegister);
2378     m_assembler.mul32(divisorRegister, resultRegister);
2379     return m_assembler.branchSub32(condition, inputDividend, resultRegister, resultRegister);
2380 #elif CPU(ARM_THUMB2) && !CPU(APPLE_ARMV7S)
2381     LocalRegisterWithPreference divisorRegister(m_registerAllocator, JSC::GPRInfo::argumentGPR1);
2382     m_assembler.move(Assembler::TrustedImm32(divisor), divisorRegister);
2383     FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2384     functionCall.setFunctionAddress(moduloHelper);
2385     functionCall.setTwoArguments(inputDividend, divisorRegister);
2386     return functionCall.callAndBranchOnBooleanReturnValue(condition);
2387 #elif CPU(X86_64)
2388     // idiv takes RAX + an arbitrary register, and return RAX + RDX. Most of this code is about doing
2389     // an efficient allocation of those registers. If a register is already in use and is not the inputDividend,
2390     // we first try to copy it to a temporary register, it that is not possible we fall back to the stack.
2391     enum class RegisterAllocationType {
2392         External,
2393         AllocatedLocally,
2394         CopiedToTemporary,
2395         PushedToStack
2396     };
2397
2398     // 1) Get RAX and RDX.
2399     // If they are already used, push them to the stack.
2400     Assembler::RegisterID dividend = JSC::X86Registers::eax;
2401     RegisterAllocationType dividendAllocation = RegisterAllocationType::External;
2402     StackAllocator::StackReference temporaryDividendStackReference;
2403     Assembler::RegisterID temporaryDividendCopy = JSC::InvalidGPRReg;
2404     if (inputDividend != dividend) {
2405         bool registerIsInUse = m_registerAllocator.allocatedRegisters().contains(dividend);
2406         if (registerIsInUse) {
2407             if (m_registerAllocator.availableRegisterCount() > 1) {
2408                 temporaryDividendCopy = m_registerAllocator.allocateRegister();
2409                 m_assembler.move(dividend, temporaryDividendCopy);
2410                 dividendAllocation = RegisterAllocationType::CopiedToTemporary;
2411             } else {
2412                 temporaryDividendStackReference = m_stackAllocator.push(dividend);
2413                 dividendAllocation = RegisterAllocationType::PushedToStack;
2414             }
2415         } else {
2416             m_registerAllocator.allocateRegister(dividend);
2417             dividendAllocation = RegisterAllocationType::AllocatedLocally;
2418         }
2419         m_assembler.move(inputDividend, dividend);
2420     }
2421
2422     Assembler::RegisterID remainder = JSC::X86Registers::edx;
2423     RegisterAllocationType remainderAllocation = RegisterAllocationType::External;
2424     StackAllocator::StackReference temporaryRemainderStackReference;
2425     Assembler::RegisterID temporaryRemainderCopy = JSC::InvalidGPRReg;
2426     if (inputDividend != remainder) {
2427         bool registerIsInUse = m_registerAllocator.allocatedRegisters().contains(remainder);
2428         if (registerIsInUse) {
2429             if (m_registerAllocator.availableRegisterCount() > 1) {
2430                 temporaryRemainderCopy = m_registerAllocator.allocateRegister();
2431                 m_assembler.move(remainder, temporaryRemainderCopy);
2432                 remainderAllocation = RegisterAllocationType::CopiedToTemporary;
2433             } else {
2434                 temporaryRemainderStackReference = m_stackAllocator.push(remainder);
2435                 remainderAllocation = RegisterAllocationType::PushedToStack;
2436             }
2437         } else {
2438             m_registerAllocator.allocateRegister(remainder);
2439             remainderAllocation = RegisterAllocationType::AllocatedLocally;
2440         }
2441     }
2442
2443     // If the input register is used by idiv, save its value to restore it after the operation.
2444     Assembler::RegisterID inputDividendCopy;
2445     StackAllocator::StackReference pushedInputDividendStackReference;
2446     RegisterAllocationType savedInputDividendAllocationType = RegisterAllocationType::External;
2447     if (inputDividend == dividend || inputDividend == remainder) {
2448         if (m_registerAllocator.availableRegisterCount() > 1) {
2449             inputDividendCopy = m_registerAllocator.allocateRegister();
2450             m_assembler.move(inputDividend, inputDividendCopy);
2451             savedInputDividendAllocationType = RegisterAllocationType::CopiedToTemporary;
2452         } else {
2453             pushedInputDividendStackReference = m_stackAllocator.push(inputDividend);
2454             savedInputDividendAllocationType = RegisterAllocationType::PushedToStack;
2455         }
2456     }
2457
2458     m_assembler.m_assembler.cdq();
2459
2460     // 2) Perform the division with idiv.
2461     {
2462         LocalRegister divisorRegister(m_registerAllocator);
2463         m_assembler.move(Assembler::TrustedImm64(divisor), divisorRegister);
2464         m_assembler.m_assembler.idivl_r(divisorRegister);
2465         m_assembler.test32(remainder);
2466     }
2467
2468     // 3) Return RAX and RDX.
2469     if (remainderAllocation == RegisterAllocationType::AllocatedLocally)
2470         m_registerAllocator.deallocateRegister(remainder);
2471     else if (remainderAllocation == RegisterAllocationType::CopiedToTemporary) {
2472         m_assembler.move(temporaryRemainderCopy, remainder);
2473         m_registerAllocator.deallocateRegister(temporaryRemainderCopy);
2474     } else if (remainderAllocation == RegisterAllocationType::PushedToStack)
2475         m_stackAllocator.pop(temporaryRemainderStackReference, remainder);
2476
2477     if (dividendAllocation == RegisterAllocationType::AllocatedLocally)
2478         m_registerAllocator.deallocateRegister(dividend);
2479     else if (dividendAllocation == RegisterAllocationType::CopiedToTemporary) {
2480         m_assembler.move(temporaryDividendCopy, dividend);
2481         m_registerAllocator.deallocateRegister(temporaryDividendCopy);
2482     } else if (dividendAllocation == RegisterAllocationType::PushedToStack)
2483         m_stackAllocator.pop(temporaryDividendStackReference, dividend);
2484
2485     if (savedInputDividendAllocationType != RegisterAllocationType::External) {
2486         if (savedInputDividendAllocationType == RegisterAllocationType::CopiedToTemporary) {
2487             m_assembler.move(inputDividendCopy, inputDividend);
2488             m_registerAllocator.deallocateRegister(inputDividendCopy);
2489         } else if (savedInputDividendAllocationType == RegisterAllocationType::PushedToStack)
2490             m_stackAllocator.pop(pushedInputDividendStackReference, inputDividend);
2491     }
2492
2493     // 4) Branch on the test.
2494     return m_assembler.branch(condition);
2495 #else
2496 #error Modulo is not implemented for this architecture.
2497 #endif
2498 }
2499
2500 void SelectorCodeGenerator::moduloIsZero(Assembler::JumpList& failureCases, Assembler::RegisterID inputDividend, int divisor)
2501 {
2502     if (divisor == 1 || divisor == -1)
2503         return;
2504     if (divisor == 2 || divisor == -2) {
2505         failureCases.append(m_assembler.branchTest32(Assembler::NonZero, inputDividend, Assembler::TrustedImm32(1)));
2506         return;
2507     }
2508
2509     failureCases.append(modulo(Assembler::NonZero, inputDividend, divisor));
2510 }
2511
2512 void SelectorCodeGenerator::linkFailures(Assembler::JumpList& globalFailureCases, BacktrackingAction backtrackingAction, Assembler::JumpList& localFailureCases)
2513 {
2514     switch (backtrackingAction) {
2515     case BacktrackingAction::NoBacktracking:
2516         globalFailureCases.append(localFailureCases);
2517         break;
2518     case BacktrackingAction::JumpToDescendantEntryPoint:
2519         localFailureCases.linkTo(m_backtrackingLevels.last().descendantEntryPoint, &m_assembler);
2520         break;
2521     case BacktrackingAction::JumpToDescendantTreeWalkerEntryPoint:
2522         localFailureCases.linkTo(m_backtrackingLevels.last().descendantTreeWalkerBacktrackingPoint, &m_assembler);
2523         break;
2524     case BacktrackingAction::JumpToDescendantTail:
2525         m_backtrackingLevels.last().descendantBacktrackingFailureCases.append(localFailureCases);
2526         break;
2527     case BacktrackingAction::JumpToIndirectAdjacentEntryPoint:
2528         localFailureCases.linkTo(m_backtrackingLevels.last().indirectAdjacentEntryPoint, &m_assembler);
2529         break;
2530     case BacktrackingAction::JumpToIndirectAdjacentTreeWalkerEntryPoint:
2531         localFailureCases.linkTo(m_backtrackingLevels.last().indirectAdjacentTreeWalkerBacktrackingPoint, &m_assembler);
2532         break;
2533     case BacktrackingAction::JumpToDirectAdjacentTail:
2534         m_backtrackingLevels.last().adjacentBacktrackingFailureCases.append(localFailureCases);
2535         break;
2536     }
2537 }
2538
2539 void SelectorCodeGenerator::generateAdjacentBacktrackingTail()
2540 {
2541     // Recovering tail.
2542     m_backtrackingLevels.last().adjacentBacktrackingFailureCases.link(&m_assembler);
2543     m_backtrackingLevels.last().adjacentBacktrackingFailureCases.clear();
2544
2545     BacktrackingLevel& currentBacktrackingLevel = m_backtrackingLevels.last();
2546     m_assembler.loadPtr(m_stackAllocator.addressOf(currentBacktrackingLevel.adjacentBacktrackingStart), elementAddressRegister);
2547     m_backtrackingStack.append(currentBacktrackingLevel.adjacentBacktrackingStart);
2548     currentBacktrackingLevel.adjacentBacktrackingStart = StackAllocator::StackReference();
2549
2550     m_assembler.jump(m_backtrackingLevels.last().indirectAdjacentEntryPoint);
2551 }
2552
2553 void SelectorCodeGenerator::generateDescendantBacktrackingTail()
2554 {
2555     m_backtrackingLevels.last().descendantBacktrackingFailureCases.link(&m_assembler);
2556     m_backtrackingLevels.last().descendantBacktrackingFailureCases.clear();
2557
2558     BacktrackingLevel& currentBacktrackingLevel = m_backtrackingLevels.last();
2559     if (!currentBacktrackingLevel.descendantBacktrackingStart.isValid()) {
2560         m_assembler.move(m_descendantBacktrackingStart, elementAddressRegister);
2561         m_registerAllocator.deallocateRegister(m_descendantBacktrackingStart);
2562         m_descendantBacktrackingStartInUse = false;
2563     } else {
2564         m_assembler.loadPtr(m_stackAllocator.addressOf(currentBacktrackingLevel.descendantBacktrackingStart), elementAddressRegister);
2565         m_backtrackingStack.append(currentBacktrackingLevel.descendantBacktrackingStart);
2566         currentBacktrackingLevel.descendantBacktrackingStart = StackAllocator::StackReference();
2567     }
2568
2569     m_assembler.jump(m_backtrackingLevels.last().descendantEntryPoint);
2570 }
2571
2572 void SelectorCodeGenerator::generateBacktrackingTailsIfNeeded(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
2573 {
2574     if (fragment.backtrackingFlags & BacktrackingFlag::DirectAdjacentTail && fragment.backtrackingFlags & BacktrackingFlag::DescendantTail) {
2575         Assembler::Jump normalCase = m_assembler.jump();
2576         generateAdjacentBacktrackingTail();
2577         generateDescendantBacktrackingTail();
2578         normalCase.link(&m_assembler);
2579     } else if (fragment.backtrackingFlags & BacktrackingFlag::DirectAdjacentTail) {
2580         Assembler::Jump normalCase = m_assembler.jump();
2581         generateAdjacentBacktrackingTail();
2582         failureCases.append(m_assembler.jump());
2583         normalCase.link(&m_assembler);
2584     } else if (fragment.backtrackingFlags & BacktrackingFlag::DescendantTail) {
2585         Assembler::Jump normalCase = m_assembler.jump();
2586         generateDescendantBacktrackingTail();
2587         normalCase.link(&m_assembler);
2588     }
2589 }
2590
2591 void SelectorCodeGenerator::generateElementMatching(Assembler::JumpList& matchingTagNameFailureCases, Assembler::JumpList& matchingPostTagNameFailureCases, const SelectorFragment& fragment)
2592 {
2593     if (fragment.tagNameSelector)
2594         generateElementHasTagName(matchingTagNameFailureCases, *(fragment.tagNameSelector));
2595
2596     generateElementLinkMatching(matchingPostTagNameFailureCases, fragment);
2597
2598     if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassRoot))
2599         generateElementIsRoot(matchingPostTagNameFailureCases);
2600
2601     if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassScope))
2602         generateElementIsScopeRoot(matchingPostTagNameFailureCases);
2603
2604     if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassTarget))
2605         generateElementIsTarget(matchingPostTagNameFailureCases);
2606
2607     if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassFocusWithin))
2608         generateElementHasFocusWithin(matchingPostTagNameFailureCases);
2609
2610     for (unsigned i = 0; i < fragment.unoptimizedPseudoClasses.size(); ++i)
2611         generateElementFunctionCallTest(matchingPostTagNameFailureCases, fragment.unoptimizedPseudoClasses[i]);
2612
2613     for (unsigned i = 0; i < fragment.unoptimizedPseudoClassesWithContext.size(); ++i)
2614         generateContextFunctionCallTest(matchingPostTagNameFailureCases, fragment.unoptimizedPseudoClassesWithContext[i]);
2615
2616     generateElementDataMatching(matchingPostTagNameFailureCases, fragment);
2617
2618     if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassActive))
2619         generateElementIsActive(matchingPostTagNameFailureCases, fragment);
2620     if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassEmpty))
2621         generateElementIsEmpty(matchingPostTagNameFailureCases);
2622     if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassHover))
2623         generateElementIsHovered(matchingPostTagNameFailureCases, fragment);
2624     if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassOnlyChild))
2625         generateElementIsOnlyChild(matchingPostTagNameFailureCases);
2626     if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassPlaceholderShown))
2627         generateElementHasPlaceholderShown(matchingPostTagNameFailureCases);
2628     if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassFirstChild))
2629         generateElementIsFirstChild(matchingPostTagNameFailureCases);
2630     if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassLastChild))
2631         generateElementIsLastChild(matchingPostTagNameFailureCases);
2632     if (!fragment.nthChildFilters.isEmpty())
2633         generateElementIsNthChild(matchingPostTagNameFailureCases, fragment);
2634     if (!fragment.nthLastChildFilters.isEmpty())
2635         generateElementIsNthLastChild(matchingPostTagNameFailureCases, fragment);
2636     if (!fragment.notFilters.isEmpty())
2637         generateElementMatchesNotPseudoClass(matchingPostTagNameFailureCases, fragment);
2638     if (!fragment.anyFilters.isEmpty())
2639         generateElementMatchesAnyPseudoClass(matchingPostTagNameFailureCases, fragment);
2640     if (!fragment.matchesFilters.isEmpty())
2641         generateElementMatchesMatchesPseudoClass(matchingPostTagNameFailureCases, fragment);
2642     if (!fragment.languageArgumentsList.isEmpty())
2643         generateElementIsInLanguage(matchingPostTagNameFailureCases, fragment);
2644     if (!fragment.nthChildOfFilters.isEmpty())
2645         generateElementIsNthChildOf(matchingPostTagNameFailureCases, fragment);
2646     if (!fragment.nthLastChildOfFilters.isEmpty())
2647         generateElementIsNthLastChildOf(matchingPostTagNameFailureCases, fragment);
2648     if (fragment.pseudoElementSelector)
2649         generateElementHasPseudoElement(matchingPostTagNameFailureCases, fragment);
2650
2651     // Reach here when the generateElementMatching matching succeeded.
2652     // Only when the matching succeeeded, the last visited element should be stored and checked at the end of the whole matching.
2653     if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassVisited))
2654         generateStoreLastVisitedElement(elementAddressRegister);
2655 }
2656
2657 void SelectorCodeGenerator::generateElementDataMatching(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
2658 {
2659     if (!fragment.id && fragment.classNames.isEmpty() && fragment.attributes.isEmpty())
2660         return;
2661
2662     //  Generate:
2663     //     elementDataAddress = element->elementData();
2664     //     if (!elementDataAddress)
2665     //         failure!
2666     LocalRegister elementDataAddress(m_registerAllocator);
2667     m_assembler.loadPtr(Assembler::Address(elementAddressRegister, Element::elementDataMemoryOffset()), elementDataAddress);
2668     failureCases.append(m_assembler.branchTestPtr(Assembler::Zero, elementDataAddress));
2669
2670     if (fragment.id)
2671         generateElementHasId(failureCases, elementDataAddress, *fragment.id);
2672     if (!fragment.classNames.isEmpty())
2673         generateElementHasClasses(failureCases, elementDataAddress, fragment.classNames);
2674     if (!fragment.attributes.isEmpty())
2675         generateElementAttributesMatching(failureCases, elementDataAddress, fragment);
2676 }
2677
2678 void SelectorCodeGenerator::generateElementLinkMatching(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
2679 {
2680     if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassLink)
2681         || fragment.pseudoClasses.contains(CSSSelector::PseudoClassAnyLink)
2682         || fragment.pseudoClasses.contains(CSSSelector::PseudoClassVisited))
2683         generateElementIsLink(failureCases);
2684 }
2685
2686 static inline bool canMatchStyleAttribute(const SelectorFragment& fragment)
2687 {
2688     for (unsigned i = 0; i < fragment.attributes.size(); ++i) {
2689         const CSSSelector& attributeSelector = fragment.attributes[i].selector();
2690         const QualifiedName& attributeName = attributeSelector.attribute();
2691         if (Attribute::nameMatchesFilter(HTMLNames::styleAttr, attributeName.prefix(), attributeName.localName(), attributeName.namespaceURI()))
2692             return true;
2693
2694         const AtomicString& canonicalLocalName = attributeSelector.attributeCanonicalLocalName();
2695         if (attributeName.localName() != canonicalLocalName
2696             && Attribute::nameMatchesFilter(HTMLNames::styleAttr, attributeName.prefix(), attributeSelector.attributeCanonicalLocalName(), attributeName.namespaceURI())) {
2697             return true;
2698         }
2699     }
2700     return false;
2701 }
2702
2703 void SelectorCodeGenerator::generateSynchronizeStyleAttribute(Assembler::RegisterID elementDataArraySizeAndFlags)
2704 {
2705     // The style attribute is updated lazily based on the flag styleAttributeIsDirty.
2706     Assembler::Jump styleAttributeNotDirty = m_assembler.branchTest32(Assembler::Zero, elementDataArraySizeAndFlags, Assembler::TrustedImm32(ElementData::styleAttributeIsDirtyFlag()));
2707
2708     FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2709     functionCall.setFunctionAddress(StyledElement::synchronizeStyleAttributeInternal);
2710     Assembler::RegisterID elementAddress = elementAddressRegister;
2711     functionCall.setOneArgument(elementAddress);
2712     functionCall.call();
2713
2714     styleAttributeNotDirty.link(&m_assembler);
2715 }
2716
2717 static inline bool canMatchAnimatableSVGAttribute(const SelectorFragment& fragment)
2718 {
2719     for (unsigned i = 0; i < fragment.attributes.size(); ++i) {
2720         const CSSSelector& attributeSelector = fragment.attributes[i].selector();
2721         const QualifiedName& selectorAttributeName = attributeSelector.attribute();
2722
2723         const QualifiedName& candidateForLocalName = SVGElement::animatableAttributeForName(selectorAttributeName.localName());
2724         if (Attribute::nameMatchesFilter(candidateForLocalName, selectorAttributeName.prefix(), selectorAttributeName.localName(), selectorAttributeName.namespaceURI()))
2725             return true;
2726
2727         const AtomicString& canonicalLocalName = attributeSelector.attributeCanonicalLocalName();
2728         if (selectorAttributeName.localName() != canonicalLocalName) {
2729             const QualifiedName& candidateForCanonicalLocalName = SVGElement::animatableAttributeForName(selectorAttributeName.localName());
2730             if (Attribute::nameMatchesFilter(candidateForCanonicalLocalName, selectorAttributeName.prefix(), selectorAttributeName.localName(), selectorAttributeName.namespaceURI()))
2731                 return true;
2732         }
2733     }
2734     return false;
2735 }
2736
2737 void SelectorCodeGenerator::generateSynchronizeAllAnimatedSVGAttribute(Assembler::RegisterID elementDataArraySizeAndFlags)
2738 {
2739     // SVG attributes can be updated lazily depending on the flag AnimatedSVGAttributesAreDirty. We need to check
2740     // that first.
2741     Assembler::Jump animatedSVGAttributesNotDirty = m_assembler.branchTest32(Assembler::Zero, elementDataArraySizeAndFlags, Assembler::TrustedImm32(ElementData::animatedSVGAttributesAreDirtyFlag()));
2742
2743     FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2744     functionCall.setFunctionAddress(SVGElement::synchronizeAllAnimatedSVGAttribute);
2745     Assembler::RegisterID elementAddress = elementAddressRegister;
2746     functionCall.setOneArgument(elementAddress);
2747     functionCall.call();
2748
2749     animatedSVGAttributesNotDirty.link(&m_assembler);
2750 }
2751
2752 void SelectorCodeGenerator::generateElementAttributesMatching(Assembler::JumpList& failureCases, const LocalRegister& elementDataAddress, const SelectorFragment& fragment)
2753 {
2754     LocalRegister scratchRegister(m_registerAllocator);
2755     Assembler::RegisterID elementDataArraySizeAndFlags = scratchRegister;
2756     Assembler::RegisterID attributeArrayLength = scratchRegister;
2757
2758     m_assembler.load32(Assembler::Address(elementDataAddress, ElementData::arraySizeAndFlagsMemoryOffset()), elementDataArraySizeAndFlags);
2759
2760     if (canMatchStyleAttribute(fragment))
2761         generateSynchronizeStyleAttribute(elementDataArraySizeAndFlags);
2762
2763     if (canMatchAnimatableSVGAttribute(fragment))
2764         generateSynchronizeAllAnimatedSVGAttribute(elementDataArraySizeAndFlags);
2765
2766     // Attributes can be stored either in a separate vector for UniqueElementData, or after the elementData itself
2767     // for ShareableElementData.
2768     LocalRegister attributeArrayPointer(m_registerAllocator);
2769     Assembler::Jump isShareableElementData  = m_assembler.branchTest32(Assembler::Zero, elementDataArraySizeAndFlags, Assembler::TrustedImm32(ElementData::isUniqueFlag()));
2770     {
2771         ptrdiff_t attributeVectorOffset = UniqueElementData::attributeVectorMemoryOffset();
2772         m_assembler.loadPtr(Assembler::Address(elementDataAddress, attributeVectorOffset + UniqueElementData::AttributeVector::dataMemoryOffset()), attributeArrayPointer);
2773         m_assembler.load32(Assembler::Address(elementDataAddress, attributeVectorOffset + UniqueElementData::AttributeVector::sizeMemoryOffset()), attributeArrayLength);
2774     }
2775     Assembler::Jump skipShareable = m_assembler.jump();
2776
2777     {
2778         isShareableElementData.link(&m_assembler);
2779         m_assembler.urshift32(elementDataArraySizeAndFlags, Assembler::TrustedImm32(ElementData::arraySizeOffset()), attributeArrayLength);
2780         m_assembler.addPtr(Assembler::TrustedImm32(ShareableElementData::attributeArrayMemoryOffset()), elementDataAddress, attributeArrayPointer);
2781     }
2782
2783     skipShareable.link(&m_assembler);
2784
2785     // If there are no attributes, fail immediately.
2786     failureCases.append(m_assembler.branchTest32(Assembler::Zero, attributeArrayLength));
2787
2788     unsigned attributeCount = fragment.attributes.size();
2789     for (unsigned i = 0; i < attributeCount; ++i) {
2790         Assembler::RegisterID decIndexRegister;
2791         Assembler::RegisterID currentAttributeAddress;
2792
2793         bool isLastAttribute = i == (attributeCount - 1);
2794         if (!isLastAttribute) {
2795             // We need to make a copy to let the next iterations use the values.
2796             currentAttributeAddress = m_registerAllocator.allocateRegister();
2797             decIndexRegister = m_registerAllocator.allocateRegister();
2798             m_assembler.move(attributeArrayPointer, currentAttributeAddress);
2799             m_assembler.move(attributeArrayLength, decIndexRegister);
2800         } else {
2801             currentAttributeAddress = attributeArrayPointer;
2802             decIndexRegister = attributeArrayLength;
2803         }
2804
2805         generateElementAttributeMatching(failureCases, currentAttributeAddress, decIndexRegister, fragment.attributes[i]);
2806
2807         if (!isLastAttribute) {
2808             m_registerAllocator.deallocateRegister(decIndexRegister);
2809             m_registerAllocator.deallocateRegister(currentAttributeAddress);
2810         }
2811     }
2812 }
2813
2814 void SelectorCodeGenerator::generateElementAttributeMatching(Assembler::JumpList& failureCases, Assembler::RegisterID currentAttributeAddress, Assembler::RegisterID decIndexRegister, const AttributeMatchingInfo& attributeInfo)
2815 {
2816     // Get the localName used for comparison. HTML elements use a lowercase local name known in selectors as canonicalLocalName.
2817     LocalRegister localNameToMatch(m_registerAllocator);
2818
2819     // In general, canonicalLocalName and localName are the same. When they differ, we have to check if the node is HTML to know
2820     // which one to use.
2821     const CSSSelector& attributeSelector = attributeInfo.selector();
2822     const AtomicStringImpl* canonicalLocalName = attributeSelector.attributeCanonicalLocalName().impl();
2823     const AtomicStringImpl* localName = attributeSelector.attribute().localName().impl();
2824     if (canonicalLocalName == localName)
2825         m_assembler.move(Assembler::TrustedImmPtr(canonicalLocalName), localNameToMatch);
2826     else {
2827         m_assembler.move(Assembler::TrustedImmPtr(canonicalLocalName), localNameToMatch);
2828         Assembler::Jump elementIsHTML = DOMJIT::branchTestIsHTMLFlagOnNode(m_assembler, Assembler::NonZero, elementAddressRegister);
2829         m_assembler.move(Assembler::TrustedImmPtr(localName), localNameToMatch);
2830         elementIsHTML.link(&m_assembler);
2831     }
2832
2833     Assembler::JumpList successCases;
2834     Assembler::Label loopStart(m_assembler.label());
2835
2836     {
2837         LocalRegister qualifiedNameImpl(m_registerAllocator);
2838         m_assembler.loadPtr(Assembler::Address(currentAttributeAddress, Attribute::nameMemoryOffset()), qualifiedNameImpl);
2839
2840         bool shouldCheckNamespace = attributeSelector.attribute().prefix() != starAtom();
2841         if (shouldCheckNamespace) {
2842             Assembler::Jump nameDoesNotMatch = m_assembler.branchPtr(Assembler::NotEqual, Assembler::Address(qualifiedNameImpl, QualifiedName::QualifiedNameImpl::localNameMemoryOffset()), localNameToMatch);
2843
2844             const AtomicStringImpl* namespaceURI = attributeSelector.attribute().namespaceURI().impl();
2845             if (namespaceURI) {
2846                 LocalRegister namespaceToMatch(m_registerAllocator);
2847                 m_assembler.move(Assembler::TrustedImmPtr(namespaceURI), namespaceToMatch);
2848                 successCases.append(m_assembler.branchPtr(Assembler::Equal, Assembler::Address(qualifiedNameImpl, QualifiedName::QualifiedNameImpl::namespaceMemoryOffset()), namespaceToMatch));
2849             } else
2850                 successCases.append(m_assembler.branchTestPtr(Assembler::Zero, Assembler::Address(qualifiedNameImpl, QualifiedName::QualifiedNameImpl::namespaceMemoryOffset())));
2851             nameDoesNotMatch.link(&m_assembler);
2852         } else
2853             successCases.append(m_assembler.branchPtr(Assembler::Equal, Assembler::Address(qualifiedNameImpl, QualifiedName::QualifiedNameImpl::localNameMemoryOffset()), localNameToMatch));
2854     }
2855
2856     Assembler::Label loopReEntry(m_assembler.label());
2857
2858     // If we reached the last element -> failure.
2859     failureCases.append(m_assembler.branchSub32(Assembler::Zero, Assembler::TrustedImm32(1), decIndexRegister));
2860
2861     // Otherwise just loop over.
2862     m_assembler.addPtr(Assembler::TrustedImm32(sizeof(Attribute)), currentAttributeAddress);
2863     m_assembler.jump().linkTo(loopStart, &m_assembler);
2864
2865     successCases.link(&m_assembler);
2866
2867     if (attributeSelector.match() != CSSSelector::Set) {
2868         // We make the assumption that name matching fails in most cases and we keep value matching outside
2869         // of the loop. We re-enter the loop if needed.
2870         // FIXME: exact case sensitive value matching is so simple that it should be done in the loop.
2871         Assembler::JumpList localFailureCases;
2872         generateElementAttributeValueMatching(localFailureCases, currentAttributeAddress, attributeInfo);
2873         localFailureCases.linkTo(loopReEntry, &m_assembler);
2874     }
2875 }
2876
2877 enum CaseSensitivity {
2878     CaseSensitive,
2879     CaseInsensitive
2880 };
2881
2882 template<CaseSensitivity caseSensitivity>
2883 static bool attributeValueBeginsWith(const Attribute* attribute, AtomicStringImpl* expectedString)
2884 {
2885     ASSERT(expectedString);
2886
2887     AtomicStringImpl& valueImpl = *attribute->value().impl();
2888     if (caseSensitivity == CaseSensitive)
2889         return valueImpl.startsWith(*expectedString);
2890     return valueImpl.startsWithIgnoringASCIICase(*expectedString);
2891 }
2892
2893 template<CaseSensitivity caseSensitivity>
2894 static bool attributeValueContains(const Attribute* attribute, AtomicStringImpl* expectedString)
2895 {
2896     AtomicStringImpl& valueImpl = *attribute->value().impl();
2897     if (caseSensitivity == CaseSensitive)
2898         return valueImpl.find(expectedString) != notFound;
2899     return valueImpl.findIgnoringASCIICase(expectedString) != notFound;
2900 }
2901
2902 template<CaseSensitivity caseSensitivity>
2903 static bool attributeValueEndsWith(const Attribute* attribute, AtomicStringImpl* expectedString)
2904 {
2905     ASSERT(expectedString);
2906
2907     AtomicStringImpl& valueImpl = *attribute->value().impl();
2908     if (caseSensitivity == CaseSensitive)
2909         return valueImpl.endsWith(*expectedString);
2910     return valueImpl.endsWithIgnoringASCIICase(*expectedString);
2911 }
2912
2913 template<CaseSensitivity caseSensitivity>
2914 static bool attributeValueMatchHyphenRule(const Attribute* attribute, AtomicStringImpl* expectedString)
2915 {
2916     ASSERT(expectedString);
2917
2918     AtomicStringImpl& valueImpl = *attribute->value().impl();
2919     if (valueImpl.length() < expectedString->length())
2920         return false;
2921
2922     bool valueStartsWithExpectedString;
2923     if (caseSensitivity == CaseSensitive)
2924         valueStartsWithExpectedString = valueImpl.startsWith(*expectedString);
2925     else
2926         valueStartsWithExpectedString = valueImpl.startsWithIgnoringASCIICase(*expectedString);
2927
2928     if (!valueStartsWithExpectedString)
2929         return false;
2930
2931     return valueImpl.length() == expectedString->length() || valueImpl[expectedString->length()] == '-';
2932 }
2933
2934 template<CaseSensitivity caseSensitivity>
2935 static bool attributeValueSpaceSeparetedListContains(const Attribute* attribute, AtomicStringImpl* expectedString)
2936 {
2937     AtomicStringImpl& value = *attribute->value().impl();
2938
2939     unsigned startSearchAt = 0;
2940     while (true) {
2941         size_t foundPos;
2942         if (caseSensitivity == CaseSensitive)
2943             foundPos = value.find(expectedString, startSearchAt);
2944         else
2945             foundPos = value.findIgnoringASCIICase(expectedString, startSearchAt);
2946         if (foundPos == notFound)
2947             return false;
2948         if (!foundPos || isHTMLSpace(value[foundPos - 1])) {
2949             unsigned endStr = foundPos + expectedString->length();
2950             if (endStr == value.length() || isHTMLSpace(value[endStr]))
2951                 return true;
2952         }
2953         startSearchAt = foundPos + 1;
2954     }
2955     return false;
2956 }
2957
2958 void SelectorCodeGenerator::generateElementAttributeValueMatching(Assembler::JumpList& failureCases, Assembler::RegisterID currentAttributeAddress, const AttributeMatchingInfo& attributeInfo)
2959 {
2960     const CSSSelector& attributeSelector = attributeInfo.selector();
2961     const AtomicString& expectedValue = attributeSelector.value();
2962     ASSERT(!expectedValue.isNull());
2963     AttributeCaseSensitivity valueCaseSensitivity = attributeInfo.attributeCaseSensitivity();
2964
2965     switch (attributeSelector.match()) {
2966     case CSSSelector::Begin:
2967         generateElementAttributeFunctionCallValueMatching(failureCases, currentAttributeAddress, expectedValue, valueCaseSensitivity, attributeValueBeginsWith<CaseSensitive>, attributeValueBeginsWith<CaseInsensitive>);
2968         break;
2969     case CSSSelector::Contain:
2970         generateElementAttributeFunctionCallValueMatching(failureCases, currentAttributeAddress, expectedValue, valueCaseSensitivity, attributeValueContains<CaseSensitive>, attributeValueContains<CaseInsensitive>);
2971         break;
2972     case CSSSelector::End:
2973         generateElementAttributeFunctionCallValueMatching(failureCases, currentAttributeAddress, expectedValue, valueCaseSensitivity, attributeValueEndsWith<CaseSensitive>, attributeValueEndsWith<CaseInsensitive>);
2974         break;
2975     case CSSSelector::Exact:
2976         generateElementAttributeValueExactMatching(failureCases, currentAttributeAddress, expectedValue, valueCaseSensitivity);
2977         break;
2978     case CSSSelector::Hyphen:
2979         generateElementAttributeFunctionCallValueMatching(failureCases, currentAttributeAddress, expectedValue, valueCaseSensitivity, attributeValueMatchHyphenRule<CaseSensitive>, attributeValueMatchHyphenRule<CaseInsensitive>);
2980         break;
2981     case CSSSelector::List:
2982         generateElementAttributeFunctionCallValueMatching(failureCases, currentAttributeAddress, expectedValue, valueCaseSensitivity, attributeValueSpaceSeparetedListContains<CaseSensitive>, attributeValueSpaceSeparetedListContains<CaseInsensitive>);
2983         break;
2984     default:
2985         ASSERT_NOT_REACHED();
2986     }
2987 }
2988
2989 static inline Assembler::Jump testIsHTMLClassOnDocument(Assembler::ResultCondition condition, Assembler& assembler, Assembler::RegisterID documentAddress)
2990 {
2991     return assembler.branchTest32(condition, Assembler::Address(documentAddress, Document::documentClassesMemoryOffset()), Assembler::TrustedImm32(Document::isHTMLDocumentClassFlag()));
2992 }
2993
2994 void SelectorCodeGenerator::generateElementAttributeValueExactMatching(Assembler::JumpList& failureCases, Assembler::RegisterID currentAttributeAddress, const AtomicString& expectedValue, AttributeCaseSensitivity valueCaseSensitivity)
2995 {
2996     LocalRegisterWithPreference expectedValueRegister(m_registerAllocator, JSC::GPRInfo::argumentGPR1);
2997     m_assembler.move(Assembler::TrustedImmPtr(expectedValue.impl()), expectedValueRegister);
2998
2999     switch (valueCaseSensitivity) {
3000     case AttributeCaseSensitivity::CaseSensitive: {
3001         failureCases.append(m_assembler.branchPtr(Assembler::NotEqual, Assembler::Address(currentAttributeAddress, Attribute::valueMemoryOffset()), expectedValueRegister));
3002         break;
3003     }
3004     case AttributeCaseSensitivity::HTMLLegacyCaseInsensitive: {
3005         Assembler::Jump skipCaseInsensitiveComparison = m_assembler.branchPtr(Assembler::Equal, Assembler::Address(currentAttributeAddress, Attribute::valueMemoryOffset()), expectedValueRegister);
3006
3007         // If the element is an HTML element, in a HTML dcoument (not including XHTML), value matching is case insensitive.
3008         // Taking the contrapositive, if we find the element is not HTML or is not in a HTML document, the condition above
3009         // sould be sufficient and we can fail early.
3010         failureCases.append(DOMJIT::branchTestIsHTMLFlagOnNode(m_assembler, Assembler::Zero, elementAddressRegister));
3011
3012         {
3013             LocalRegister document(m_registerAllocator);
3014             DOMJIT::loadDocument(m_assembler, elementAddressRegister, document);
3015             failureCases.append(testIsHTMLClassOnDocument(Assembler::Zero, m_assembler, document));
3016         }
3017
3018         LocalRegister valueStringImpl(m_registerAllocator);
3019         m_assembler.loadPtr(Assembler::Address(currentAttributeAddress, Attribute::valueMemoryOffset()), valueStringImpl);
3020
3021         FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
3022         functionCall.setFunctionAddress(WTF::equalIgnoringASCIICaseNonNull);
3023         functionCall.setTwoArguments(valueStringImpl, expectedValueRegister);
3024         failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
3025
3026         skipCaseInsensitiveComparison.link(&m_assembler);
3027         break;
3028     }
3029     case AttributeCaseSensitivity::CaseInsensitive: {
3030         LocalRegister valueStringImpl(m_registerAllocator);
3031         m_assembler.loadPtr(Assembler::Address(currentAttributeAddress, Attribute::valueMemoryOffset()), valueStringImpl);
3032
3033         Assembler::Jump skipCaseInsensitiveComparison = m_assembler.branchPtr(Assembler::Equal, valueStringImpl, expectedValueRegister);
3034         FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
3035         functionCall.setFunctionAddress(WTF::equalIgnoringASCIICaseNonNull);
3036         functionCall.setTwoArguments(valueStringImpl, expectedValueRegister);
3037         failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
3038         skipCaseInsensitiveComparison.link(&m_assembler);
3039         break;
3040     }
3041     }
3042 }
3043
3044 void SelectorCodeGenerator::generateElementAttributeFunctionCallValueMatching(Assembler::JumpList& failureCases, Assembler::RegisterID currentAttributeAddress, const AtomicString& expectedValue, AttributeCaseSensitivity valueCaseSensitivity, JSC::FunctionPtr<CSSOperationPtrTag> caseSensitiveTest, JSC::FunctionPtr<CSSOperationPtrTag> caseInsensitiveTest)
3045 {
3046     LocalRegisterWithPreference expectedValueRegister(m_registerAllocator, JSC::GPRInfo::argumentGPR1);
3047     m_assembler.move(Assembler::TrustedImmPtr(expectedValue.impl()), expectedValueRegister);
3048
3049
3050     switch (valueCaseSensitivity) {
3051     case AttributeCaseSensitivity::CaseSensitive: {
3052         FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
3053         functionCall.setFunctionAddress(caseSensitiveTest);
3054         functionCall.setTwoArguments(currentAttributeAddress, expectedValueRegister);
3055         failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
3056         break;
3057     }
3058     case AttributeCaseSensitivity::HTMLLegacyCaseInsensitive: {
3059         Assembler::JumpList shouldUseCaseSensitiveComparison;
3060         shouldUseCaseSensitiveComparison.append(DOMJIT::branchTestIsHTMLFlagOnNode(m_assembler, Assembler::Zero, elementAddressRegister));
3061         {
3062             LocalRegister scratchRegister(m_registerAllocator);
3063             // scratchRegister = pointer to treeScope.
3064             m_assembler.loadPtr(Assembler::Address(elementAddressRegister, Node::treeScopeMemoryOffset()), scratchRegister);
3065             // scratchRegister = pointer to document.
3066             m_assembler.loadPtr(Assembler::Address(scratchRegister, TreeScope::documentScopeMemoryOffset()), scratchRegister);
3067             shouldUseCaseSensitiveComparison.append(testIsHTMLClassOnDocument(Assembler::Zero, m_assembler, scratchRegister));
3068         }
3069
3070         {
3071             FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
3072             functionCall.setFunctionAddress(caseInsensitiveTest);
3073             functionCall.setTwoArguments(currentAttributeAddress, expectedValueRegister);
3074             failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
3075         }
3076
3077         Assembler::Jump skipCaseSensitiveCase = m_assembler.jump();
3078
3079         {
3080             shouldUseCaseSensitiveComparison.link(&m_assembler);
3081             FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
3082             functionCall.setFunctionAddress(caseSensitiveTest);
3083             functionCall.setTwoArguments(currentAttributeAddress, expectedValueRegister);
3084             failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
3085         }
3086
3087         skipCaseSensitiveCase.link(&m_assembler);
3088         break;
3089     }
3090     case AttributeCaseSensitivity::CaseInsensitive: {
3091         FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
3092         functionCall.setFunctionAddress(caseInsensitiveTest);
3093         functionCall.setTwoArguments(currentAttributeAddress, expectedValueRegister);
3094         failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
3095         break;
3096     }
3097     }
3098 }
3099
3100 void SelectorCodeGenerator::generateElementFunctionCallTest(Assembler::JumpList& failureCases, JSC::FunctionPtr<CSSOperationPtrTag> testFunction)
3101 {
3102     Assembler::RegisterID elementAddress = elementAddressRegister;
3103     FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
3104     functionCall.setFunctionAddress(testFunction);
3105     functionCall.setOneArgument(elementAddress);
3106     failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
3107 }
3108
3109 void SelectorCodeGenerator::generateContextFunctionCallTest(Assembler::JumpList& failureCases, JSC::FunctionPtr<CSSOperationPtrTag> testFunction)
3110 {
3111     Assembler::RegisterID checkingContext = m_registerAllocator.allocateRegister();
3112     loadCheckingContext(checkingContext);
3113     m_registerAllocator.deallocateRegister(checkingContext);
3114
3115     FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
3116     functionCall.setFunctionAddress(testFunction);
3117     functionCall.setOneArgument(checkingContext);
3118     failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
3119 }
3120
3121 static bool elementIsActive(const Element* element)
3122 {
3123     return element->active() || InspectorInstrumentation::forcePseudoState(*element, CSSSelector::PseudoClassActive);
3124 }
3125
3126 void SelectorCodeGenerator::generateElementIsActive(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
3127 {
3128     generateSpecialFailureInQuirksModeForActiveAndHoverIfNeeded(failureCases, fragment);
3129
3130     generateAddStyleRelationIfResolvingStyle(elementAddressRegister, Style::Relation::AffectedByActive);
3131
3132     FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
3133     functionCall.setFunctionAddress(elementIsActive);
3134     functionCall.setOneArgument(elementAddressRegister);
3135     failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
3136 }
3137
3138 static void jumpIfElementIsNotEmpty(Assembler& assembler, RegisterAllocator& registerAllocator, Assembler::JumpList& notEmptyCases, Assembler::RegisterID element)
3139 {
3140     LocalRegister currentChild(registerAllocator);
3141     assembler.loadPtr(Assembler::Address(element, ContainerNode::firstChildMemoryOffset()), currentChild);
3142
3143     Assembler::Label loopStart(assembler.label());
3144     Assembler::Jump noMoreChildren = assembler.branchTestPtr(Assembler::Zero, currentChild);
3145
3146     notEmptyCases.append(DOMJIT::branchTestIsElementFlagOnNode(assembler, Assembler::NonZero, currentChild));
3147
3148     {
3149         Assembler::Jump skipTextNodeCheck = assembler.branchTest32(Assembler::Zero, Assembler::Address(currentChild, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagIsText()));
3150
3151         LocalRegister textStringImpl(registerAllocator);
3152         assembler.loadPtr(Assembler::Address(currentChild, CharacterData::dataMemoryOffset()), textStringImpl);
3153         notEmptyCases.append(assembler.branchTest32(Assembler::NonZero, Assembler::Address(textStringImpl, StringImpl::lengthMemoryOffset())));
3154
3155         skipTextNodeCheck.link(&assembler);
3156     }
3157
3158     assembler.loadPtr(Assembler::Address(currentChild, Node::nextSiblingMemoryOffset()), currentChild);
3159     assembler.jump().linkTo(loopStart, &assembler);
3160
3161     noMoreChildren.link(&assembler);
3162 }
3163
3164 void SelectorCodeGenerator::generateElementIsEmpty(Assembler::JumpList& failureCases)
3165 {
3166     if (m_selectorContext == SelectorContext::QuerySelector) {
3167         jumpIfElementIsNotEmpty(m_assembler, m_registerAllocator, failureCases, elementAddressRegister);
3168         return;
3169     }
3170
3171     LocalRegisterWithPreference isEmptyResults(m_registerAllocator, JSC::GPRInfo::argumentGPR1);
3172     m_assembler.move(Assembler::TrustedImm32(0), isEmptyResults);
3173
3174     Assembler::JumpList notEmpty;
3175     jumpIfElementIsNotEmpty(m_assembler, m_registerAllocator, notEmpty, elementAddressRegister);
3176     m_assembler.move(Assembler::TrustedImm32(1), isEmptyResults);
3177     notEmpty.link(&m_assembler);
3178
3179     generateAddStyleRelationIfResolvingStyle(elementAddressRegister, Style::Relation::AffectedByEmpty, Assembler::RegisterID(isEmptyResults));
3180
3181     failureCases.append(m_assembler.branchTest32(Assembler::Zero, isEmptyResults));
3182 }
3183
3184 void SelectorCodeGenerator::generateElementIsFirstChild(Assembler::JumpList& failureCases)
3185 {
3186     if (m_selectorContext == SelectorContext::QuerySelector) {
3187         Assembler::JumpList successCase = jumpIfNoPreviousAdjacentElement();
3188         failureCases.append(m_assembler.jump());
3189         successCase.link(&m_assembler);
3190         LocalRegister parent(m_registerAllocator);
3191         generateWalkToParentElementOrShadowRoot(failureCases, parent);
3192         return;
3193     }
3194
3195     // Zero in isFirstChildRegister is the success case. The register is set to non-zero if a sibling if found.
3196     LocalRegister isFirstChildRegister(m_registerAllocator);
3197     m_assembler.move(Assembler::TrustedImm32(0), isFirstChildRegister);
3198
3199     {
3200         Assembler::JumpList successCase = jumpIfNoPreviousAdjacentElement();
3201
3202         // If there was a sibling element, the element was not the first child -> failure case.
3203         m_assembler.move(Assembler::TrustedImm32(1), isFirstChildRegister);
3204
3205         successCase.link(&m_assembler);
3206     }
3207
3208     LocalRegister parentNode(m_registerAllocator);
3209     generateWalkToParentNode(parentNode);
3210     failureCases.append(m_assembler.branchTestPtr(Assembler::Zero, parentNode));
3211     Assembler::Jump notElement = DOMJIT::branchTestIsElementFlagOnNode(m_assembler, Assembler::Zero, parentNode);
3212
3213     LocalRegister checkingContext(m_registerAllocator);
3214     Assembler::Jump notResolvingStyle = jumpIfNotResolvingStyle(checkingContext);
3215
3216     generateAddStyleRelation(checkingContext, parentNode, Style::Relation::ChildrenAffectedByFirstChildRules);
3217     // The parent marking is unconditional. If the matching is not a success, we can now fail.
3218     // Otherwise we need to apply setFirstChildState() on the RenderStyle.
3219     Assembler::Label checkWithRelation(m_assembler.label());
3220     failureCases.append(m_assembler.branchTest32(Assembler::NonZero, isFirstChildRegister));
3221     generateAddStyleRelation(checkingContext, elementAddressRegister, Style::Relation::FirstChild);
3222     Assembler::Jump successCase = m_assembler.jump();
3223
3224     notElement.link(&m_assembler);
3225     failureCases.append(DOMJIT::branchTestIsShadowRootFlagOnNode(m_assembler, Assembler::Zero, parentNode));
3226     jumpIfNotResolvingStyle(checkingContext).linkTo(checkWithRelation, &m_assembler);
3227
3228     notResolvingStyle.link(&m_assembler);
3229     failureCases.append(m_assembler.branchTest32(Assembler::NonZero, isFirstChildRegister));
3230
3231     successCase.link(&m_assembler);
3232 }
3233
3234 static bool elementIsHovered(const Element* element)
3235 {
3236     return element->hovered() || InspectorInstrumentation::forcePseudoState(*element, CSSSelector::PseudoClassHover);
3237 }
3238
3239 void SelectorCodeGenerator::generateElementIsHovered(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
3240 {
3241     generateSpecialFailureInQuirksModeForActiveAndHoverIfNeeded(failureCases, fragment);
3242
3243     generateAddStyleRelationIfResolvingStyle(elementAddressRegister, Style::Relation::AffectedByHover);
3244
3245     Assembler::JumpList successCases;
3246     if (m_selectorContext != SelectorContext::QuerySelector && fragment.relationToRightFragment != FragmentRelation::Rightmost) {
3247         // :hover always matches when not in rightmost position when collecting rules for descendant style invalidation optimization.
3248         // Resolving style for a matching descendant will set parent childrenAffectedByHover bit even when the element is not currently hovered.
3249         // This bit has to be set for the event based :hover invalidation to work.
3250         // FIXME: We should just collect style relation bits and apply them as needed when computing style invalidation optimization.
3251         LocalRegister checkingContext(m_registerAllocator);
3252         successCases.append(branchOnResolvingMode(Assembler::Equal, SelectorChecker::Mode::CollectingRulesIgnoringVirtualPseudoElements, checkingContext));
3253     }
3254
3255     FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
3256     functionCall.setFunctionAddress(elementIsHovered);
3257     functionCall.setOneArgument(elementAddressRegister);
3258     failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
3259
3260     successCases.link(&m_assembler);
3261 }
3262
3263 void SelectorCodeGenerator::generateElementIsInLanguage(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
3264 {
3265     for (const Vector<AtomicString>* languageArguments : fragment.languageArgumentsList)
3266         generateElementIsInLanguage(failureCases, languageArguments);
3267 }
3268
3269 void SelectorCodeGenerator::generateElementIsInLanguage(Assembler::JumpList& failureCases, const Vector<AtomicString>* languageArguments)
3270 {
3271     LocalRegisterWithPreference langRangeRegister(m_registerAllocator, JSC::GPRInfo::argumentGPR1);
3272     m_assembler.move(Assembler::TrustedImmPtr(languageArguments), langRangeRegister);
3273
3274     Assembler::RegisterID elementAddress = elementAddressRegister;
3275     FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
3276     functionCall.setFunctionAddress(matchesLangPseudoClass);
3277     functionCall.setTwoArguments(elementAddress, langRangeRegister);
3278     failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
3279 }
3280
3281 void SelectorCodeGenerator::generateElementIsLastChild(Assembler::JumpList& failureCases)
3282 {
3283     if (m_selectorContext == SelectorContext::QuerySelector) {
3284         Assembler::JumpList successCase = jumpIfNoNextAdjacentElement();
3285         failureCases.append(m_assembler.jump());
3286
3287         successCase.link(&m_assembler);
3288         LocalRegister parent(m_registerAllocator);
3289         generateWalkToParentElementOrShadowRoot(failureCases, parent);
3290
3291         failureCases.append(m_assembler.branchTest32(Assembler::Zero, Assembler::Address(parent, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagIsParsingChildrenFinished())));
3292
3293         return;
3294     }
3295
3296     LocalRegister parentNode(m_registerAllocator);
3297     generateWalkToParentNode(parentNode);
3298     failureCases.append(m_assembler.branchTestPtr(Assembler::Zero, parentNode));
3299
3300     // Zero in isLastChildRegister is the success case. The register is set to non-zero if a sibling if found.
3301     LocalRegister isLastChildRegister(m_registerAllocator);
3302     m_assembler.move(Assembler::TrustedImm32(0), isLastChildRegister);
3303
3304     {
3305         Assembler::Jump notFinishedParsingChildren = m_assembler.branchTest32(Assembler::Zero, Assembler::Address(parentNode, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagIsParsingChildrenFinished()));
3306
3307         Assembler::JumpList successCase = jumpIfNoNextAdjacentElement();
3308
3309         notFinishedParsingChildren.link(&m_assembler);
3310         m_assembler.move(Assembler::TrustedImm32(1), isLastChildRegister);
3311
3312         successCase.link(&m_assembler);
3313     }
3314
3315     Assembler::Jump notElement = DOMJIT::branchTestIsElementFlagOnNode(m_assembler, Assembler::Zero, parentNode);
3316
3317     LocalRegister checkingContext(m_registerAllocator);
3318     Assembler::Jump notResolvingStyle = jumpIfNotResolvingStyle(checkingContext);
3319
3320     generateAddStyleRelation(checkingContext, parentNode, Style::Relation::ChildrenAffectedByLastChildRules);
3321     // The parent marking is unconditional. If the matching is not a success, we can now fail.
3322     // Otherwise we need to apply setLastChildState() on the RenderStyle.
3323     Assembler::Label checkWithRelation(m_assembler.label());
3324     failureCases.append(m_assembler.branchTest32(Assembler::NonZero, isLastChildRegister));
3325     generateAddStyleRelation(checkingContext, elementAddressRegister, Style::Relation::LastChild);
3326     Assembler::Jump successCase = m_assembler.jump();
3327
3328     notElement.link(&m_assembler);
3329     failureCases.append(DOMJIT::branchTestIsShadowRootFlagOnNode(m_assembler, Assembler::Zero, parentNode));
3330     jumpIfNotResolvingStyle(checkingContext).linkTo(checkWithRelation, &m_assembler);
3331
3332     notResolvingStyle.link(&m_assembler);
3333     failureCases.append(m_assembler.branchTest32(Assembler::NonZero, isLastChildRegister));
3334
3335     successCase.link(&m_assembler);
3336 }
3337
3338 void SelectorCodeGenerator::generateElementIsOnlyChild(Assembler::JumpList& failureCases)
3339 {
3340     // Is Only child is pretty much a combination of isFirstChild + isLastChild. The main difference is that tree marking is combined.
3341     if (m_selectorContext == SelectorContext::QuerySelector) {
3342         Assembler::JumpList previousSuccessCase = jumpIfNoPreviousAdjacentElement();
3343         failureCases.append(m_assembler.jump());
3344         previousSuccessCase.link(&m_assembler);
3345
3346         Assembler::JumpList nextSuccessCase = jumpIfNoNextAdjacentElement();
3347         failureCases.append(m_assembler.jump());
3348         nextSuccessCase.link(&m_assembler);
3349
3350         LocalRegister parent(m_registerAllocator);
3351         generateWalkToParentElementOrShadowRoot(failureCases, parent);
3352
3353         failureCases.append(m_assembler.branchTest32(Assembler::Zero, Assembler::Address(parent, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagIsParsingChildrenFinished())));
3354
3355         return;
3356     }
3357
3358     LocalRegister parentNode(m_registerAllocator);
3359     generateWalkToParentNode(parentNode);
3360     failureCases.append(m_assembler.branchTestPtr(Assembler::Zero, parentNode));
3361
3362     // Zero in isOnlyChildRegister is the success case. The register is set to non-zero if a sibling if found.
3363     LocalRegister isOnlyChildRegister(m_registerAllocator);
3364     m_assembler.move(Assembler::TrustedImm32(0), isOnlyChildRegister);
3365
3366     {
3367         Assembler::JumpList localFailureCases;
3368         {
3369             Assembler::JumpList successCase = jumpIfNoPreviousAdjacentElement();
3370             localFailureCases.append(m_assembler.jump());
3371             successCase.link(&m_assembler);
3372         }
3373         localFailureCases.append(m_assembler.branchTest32(Assembler::Zero, Assembler::Address(parentNode, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagIsParsingChildrenFinished())));
3374         Assembler::JumpList successCase = jumpIfNoNextAdjacentElement();
3375
3376         localFailureCases.link(&m_assembler);
3377         m_assembler.move(Assembler::TrustedImm32(1), isOnlyChildRegister);
3378
3379         successCase.link(&m_assembler);
3380     }
3381
3382     Assembler::Jump notElement = DOMJIT::branchTestIsElementFlagOnNode(m_assembler, Assembler::Zero, parentNode);
3383
3384     LocalRegister checkingContext(m_registerAllocator);
3385     Assembler::Jump notResolvingStyle = jumpIfNotResolvingStyle(checkingContext);
3386
3387     generateAddStyleRelation(checkingContext, parentNode, Style::Relation::ChildrenAffectedByFirstChildRules);
3388     generateAddStyleRelation(checkingContext, parentNode, Style::Relation::ChildrenAffectedByLastChildRules);
3389     // The parent marking is unconditional. If the matching is not a success, we can now fail.
3390     // Otherwise we need to apply setLastChildState() on the RenderStyle.
3391     Assembler::Label checkWithRelation(m_assembler.label());
3392     failureCases.append(m_assembler.branchTest32(Assembler::NonZero, isOnlyChildRegister));
3393     generateAddStyleRelation(checkingContext, elementAddressRegister, Style::Relation::FirstChild);
3394     generateAddStyleRelation(checkingContext, elementAddressRegister, Style::Relation::LastChild);
3395     Assembler::Jump successCase = m_assembler.jump();
3396
3397     notElement.link(&m_assembler);
3398     failureCases.append(DOMJIT::branchTestIsShadowRootFlagOnNode(m_assembler, Assembler::Zero, parentNode));
3399     jumpIfNotResolvingStyle(checkingContext).linkTo(checkWithRelation, &m_assembler);
3400
3401     notResolvingStyle.link(&m_assembler);
3402     failureCases.append(m_assembler.branchTest32(Assembler::NonZero, isOnlyChildRegister));
3403
3404     successCase.link(&m_assembler);
3405 }
3406
3407 static bool makeContextStyleUniqueIfNecessaryAndTestIsPlaceholderShown(const Element* element, SelectorChecker::CheckingContext* checkingContext)
3408 {
3409     if (is<HTMLTextFormControlElement>(*element) && element->isTextField()) {
3410         if (checkingContext->resolvingMode == SelectorChecker::Mode::ResolvingStyle)
3411             checkingContext->styleRelations.append({ *element, Style::Relation::Unique, 1 });
3412         return downcast<HTMLTextFormControlElement>(*element).isPlaceholderVisible();
3413     }
3414     return false;
3415 }
3416
3417 static bool isPlaceholderShown(const Element* element)
3418 {
3419     return is<HTMLTextFormControlElement>(*element) && downcast<HTMLTextFormControlElement>(*element).isPlaceholderVisible();
3420 }
3421
3422 void SelectorCodeGenerator::generateElementHasPlaceholderShown(Assembler::JumpList& failureCases)
3423 {
3424     if (m_selectorContext == SelectorContext::QuerySelector) {
3425         FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
3426         functionCall.setFunctionAddress(isPlaceholderShown);
3427         functionCall.setOneArgument(elementAddressRegister);
3428         failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
3429         return;
3430     }
3431
3432     Assembler::RegisterID checkingContext = m_registerAllocator.allocateRegisterWithPreference(JSC::GPRInfo::argumentGPR1);
3433     loadCheckingContext(checkingContext);
3434     m_registerAllocator.deallocateRegister(checkingContext);
3435
3436     FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
3437     functionCall.setFunctionAddress(makeContextStyleUniqueIfNecessaryAndTestIsPlaceholderShown);
3438     functionCall.setTwoArguments(elementAddressRegister, checkingContext);
3439     failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
3440 }
3441
3442 inline void SelectorCodeGenerator::generateElementHasTagName(Assembler::JumpList& failureCases, const CSSSelector& tagMatchingSelector)
3443 {
3444     const QualifiedName& nameToMatch = tagMatchingSelector.tagQName();
3445     if (nameToMatch == anyQName())
3446         return;
3447
3448     // Load the QualifiedNameImpl from the input.
3449     LocalRegister qualifiedNameImpl(m_registerAllocator);
3450     m_assembler.loadPtr(Assembler::Address(elementAddressRegister, Element::tagQNameMemoryOffset() + QualifiedName::implMemoryOffset()), qualifiedNameImpl);
3451
3452     const AtomicString& selectorLocalName = nameToMatch.localName();
3453     if (selectorLocalName != starAtom()) {
3454         const AtomicString& lowercaseLocalName = tagMatchingSelector.tagLowercaseLocalName();
3455
3456         if (selectorLocalName == lowercaseLocalName) {
3457             // Generate localName == element->localName().
3458             LocalRegister constantRegister(m_registerAllocator);
3459             m_assembler.move(Assembler::TrustedImmPtr(selectorLocalName.impl()), constantRegister);
3460             failureCases.append(m_assembler.branchPtr(Assembler::NotEqual, Assembler::Address(qualifiedNameImpl, QualifiedName::QualifiedNameImpl::localNameMemoryOffset()), constantRegister));
3461         } else {
3462             Assembler::JumpList caseSensitiveCases;
3463             caseSensitiveCases.append(DOMJIT::branchTestIsHTMLFlagOnNode(m_assembler, Assembler::Zero, elementAddressRegister));
3464             {
3465                 LocalRegister document(m_registerAllocator);
3466                 DOMJIT::loadDocument(m_assembler, elementAddressRegister, document);
3467                 caseSensitiveCases.append(testIsHTMLClassOnDocument(Assembler::Zero, m_assembler, document));
3468             }
3469
3470             LocalRegister constantRegister(m_registerAllocator);
3471             m_assembler.move(Assembler::TrustedImmPtr(lowercaseLocalName.impl()), constantRegister);
3472             Assembler::Jump skipCaseSensitiveCase = m_assembler.jump();
3473
3474             caseSensitiveCases.link(&m_assembler);
3475             m_assembler.move(Assembler::TrustedImmPtr(selectorLocalName.impl()), constantRegister);
3476             skipCaseSensitiveCase.link(&m_assembler);
3477
3478             failureCases.append(m_assembler.branchPtr(Assembler::NotEqual, Assembler::Address(qualifiedNameImpl, QualifiedName::QualifiedNameImpl::localNameMemoryOffset()), constantRegister));
3479         }
3480     }
3481
3482     const AtomicString& selectorNamespaceURI = nameToMatch.namespaceURI();
3483     if (selectorNamespaceURI != starAtom()) {
3484         // Generate namespaceURI == element->namespaceURI().
3485         LocalRegister constantRegister(m_registerAllocator);
3486         m_assembler.move(Assembler::TrustedImmPtr(selectorNamespaceURI.impl()), constantRegister);
3487         failureCases.append(m_assembler.branchPtr(Assembler::NotEqual, Assembler::Address(qualifiedNameImpl, QualifiedName::QualifiedNameImpl::namespaceMemoryOffset()), constantRegister));
3488     }
3489 }
3490
3491 void SelectorCodeGenerator::generateElementHasId(Assembler::JumpList& failureCases, const LocalRegister& elementDataAddress, const AtomicString& idToMatch)
3492 {
3493     // Compare the pointers of the AtomicStringImpl from idForStyleResolution with the reference idToMatch.
3494     LocalRegister idToMatchRegister(m_registerAllocator);
3495     m_assembler.move(Assembler::TrustedImmPtr(idToMatch.impl()), idToMatchRegister);
3496     failureCases.append(m_assembler.branchPtr(Assembler::NotEqual, Assembler::Address(elementDataAddress, ElementData::idForStyleResolutionMemoryOffset()), idToMatchRegister));
3497 }
3498
3499 void SelectorCodeGenerator::generateElementHasClasses(Assembler::JumpList& failureCases, const LocalRegister& elementDataAddress, const Vector<const AtomicStringImpl*, 8>& classNames)
3500 {
3501     // Load m_classNames.
3502     LocalRegister spaceSplitStringData(m_registerAllocator);
3503     m_assembler.loadPtr(Assembler::Address(elementDataAddress, ElementData::classNamesMemoryOffset()), spaceSplitStringData);
3504
3505     // If SpaceSplitString does not have a SpaceSplitStringData pointer, it is empty -> failure case.
3506     failureCases.append(m_assembler.branchTestPtr(Assembler::Zero, spaceSplitStringData));
3507
3508     // We loop over the classes of SpaceSplitStringData for each class name we need to match.
3509     LocalRegister indexRegister(m_registerAllocator);
3510     for (unsigned i = 0; i < classNames.size(); ++i) {
3511         LocalRegister classNameToMatch(m_registerAllocator);
3512         m_assembler.move(Assembler::TrustedImmPtr(classNames[i]), classNameToMatch);
3513         m_assembler.move(Assembler::TrustedImm32(0), indexRegister);
3514
3515         // Beginning of a loop over all the class name of element to find the one we are looking for.
3516         Assembler::Label loopStart(m_assembler.label());
3517
3518         // If the pointers match, proceed to the next matcher.
3519         Assembler::Jump classFound = m_assembler.branchPtr(Assembler::Equal, Assembler::BaseIndex(spaceSplitStringData, indexRegister, Assembler::timesPtr(), SpaceSplitStringData::tokensMemoryOffset()), classNameToMatch);
3520
3521         // Increment the index.
3522         m_assembler.add32(Assembler::TrustedImm32(1), indexRegister);
3523
3524         // If we reached the last element -> failure.
3525         failureCases.append(m_assembler.branch32(Assembler::Equal, Assembler::Address(spaceSplitStringData, SpaceSplitStringData::sizeMemoryOffset()), indexRegister));
3526         // Otherwise just loop over.
3527         m_assembler.jump().linkTo(loopStart, &m_assembler);
3528
3529         // Success case.
3530         classFound.link(&m_assembler);
3531     }
3532 }
3533
3534 void SelectorCodeGenerator::generateElementIsLink(Assembler::JumpList& failureCases)
3535 {
3536     failureCases.append(m_assembler.branchTest32(Assembler::Zero, Assembler::Address(elementAddressRegister, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagIsLink())));
3537 }
3538
3539 static bool nthFilterIsAlwaysSatisified(int a, int b)
3540 {
3541     // Anything modulo 1 is zero. Unless b restricts the range, this does not filter anything out.
3542     if (a == 1 && (!b || (b == 1)))
3543         return true;
3544     return false;
3545 }
3546
3547 void SelectorCodeGenerator::generateNthChildParentCheckAndRelationUpdate(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
3548 {
3549     LocalRegister parentNode(m_registerAllocator);
3550     generateWalkToParentNode(parentNode);
3551     failureCases.append(m_assembler.branchTestPtr(Assembler::Zero, parentNode));
3552     Assembler::Jump notElement = DOMJIT::branchTestIsElementFlagOnNode(m_assembler, Assembler::Zero, parentNode);
3553
3554     auto relation = fragmentMatchesRightmostOrAdjacentElement(fragment)
3555         ? Style::Relation::ChildrenAffectedByForwardPositionalRules
3556         : Style::Relation::DescendantsAffectedByForwardPositionalRules;
3557     generateAddStyleRelationIfResolvingStyle(parentNode, relation);
3558     Assembler::Jump parentNodeCheckEnd = m_assembler.jump();
3559
3560     notElement.link(&m_assembler);
3561     failureCases.append(DOMJIT::branchTestIsShadowRootFlagOnNode(m_assembler, Assembler::Zero, parentNode));
3562
3563     parentNodeCheckEnd.link(&m_assembler);
3564 }
3565
3566 void SelectorCodeGenerator::generateElementIsNthChild(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
3567 {
3568     generateNthChildParentCheckAndRelationUpdate(failureCases, fragment);
3569
3570     Vector<std::pair<int, int>, 32> validSubsetFilters;
3571     validSubsetFilters.reserveInitialCapacity(fragment.nthChildFilters.size());
3572     for (const auto& slot : fragment.nthChildFilters) {
3573         if (nthFilterIsAlwaysSatisified(slot.first, slot.second))
3574             continue;
3575         validSubsetFilters.uncheckedAppend(slot);
3576     }
3577     if (validSubsetFilters.isEmpty())
3578         return;
3579
3580     // Setup the counter at 1.
3581     LocalRegisterWithPreference elementCounter(m_registerAllocator, JSC::GPRInfo::argumentGPR1);
3582     m_assembler.move(Assembler::TrustedImm32(1), elementCounter);
3583
3584     // Loop over the previous adjacent elements and increment the counter.
3585     {
3586         LocalRegister previousSibling(m_registerAllocator);
3587         m_assembler.move(elementAddressRegister, previousSibling);
3588
3589         // Getting the child index is very efficient when it works. When there is no child index,
3590         // querying at every iteration is very inefficient. We solve this by only testing the child
3591         // index on the first direct adjacent.
3592         Assembler::JumpList noMoreSiblingsCases;
3593
3594         Assembler::JumpList noCachedChildIndexCases;
3595         generateWalkToPreviousAdjacentElement(noMoreSiblingsCases, previousSibling);
3596         noCachedChildIndexCases.append(m_assembler.branchTest32(Assembler::Zero, Assembler::Address(previousSibling, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagHasRareData())));
3597         {
3598             LocalRegister elementRareData(m_registerAllocator);
3599             m_assembler.loadPtr(Assembler::Address(previousSibling, Node::rareDataMemoryOffset()), elementRareData);
3600             LocalRegister cachedChildIndex(m_registerAllocator);
3601             m_assembler.load16(Assembler::Address(elementRareData, ElementRareData::childIndexMemoryOffset()), cachedChildIndex);
3602             noCachedChildIndexCases.append(m_assembler.branchTest32(Assembler::Zero, cachedChildIndex));
3603             m_assembler.add32(cachedChildIndex, elementCounter);
3604             noMoreSiblingsCases.append(m_assembler.jump());
3605         }
3606         noCachedChildIndexCases.link(&m_assembler);
3607         m_assembler.add32(Assembler::TrustedImm32(1), elementCounter);
3608
3609         Assembler::Label loopStart = m_assembler.label();
3610         generateWalkToPreviousAdjacentElement(noMoreSiblingsCases, previousSibling);
3611         m_assembler.add32(Assembler::TrustedImm32(1), elementCounter);
3612         m_assembler.jump().linkTo(loopStart, &m_assembler);
3613         noMoreSiblingsCases.link(&m_assembler);
3614     }
3615
3616     generateAddStyleRelationIfResolvingStyle(elementAddressRegister, Style::Relation::NthChildIndex, Assembler::RegisterID(elementCounter));
3617
3618     for (const auto& slot : validSubsetFilters)
3619         generateNthFilterTest(failureCases, elementCounter, slot.first, slot.second);
3620 }
3621
3622 void SelectorCodeGenerator::generateElementIsNthChildOf(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
3623 {
3624     generateNthChildParentCheckAndRelationUpdate(failureCases, fragment);
3625
3626     // The initial element must match the selector list.
3627     for (const NthChildOfSelectorInfo& nthChildOfSelectorInfo : fragment.nthChildOfFilters)
3628         generateElementMatchesSelectorList(failureCases, elementAddressRegister, nthChildOfSelectorInfo.selectorList);
3629
3630     Vector<const NthChildOfSelectorInfo*> validSubsetFilters;
3631     for (const NthChildOfSelectorInfo& nthChildOfSelectorInfo : fragment.nthChildOfFilters) {
3632         if (nthFilterIsAlwaysSatisified(nthChildOfSelectorInfo.a, nthChildOfSelectorInfo.b))
3633             continue;
3634         validSubsetFilters.append(&nthChildOfSelectorInfo);
3635     }
3636     if (validSubsetFilters.isEmpty())
3637         return;
3638
3639     for (const NthChildOfSelectorInfo* nthChildOfSelectorInfo : validSubsetFilters) {
3640         // Setup the counter at 1.
3641         LocalRegisterWithPreference elementCounter(m_registerAllocator, JSC::GPRInfo::argumentGPR1);
3642         m_assembler.move(Assembler::TrustedImm32(1), elementCounter);
3643
3644         // Loop over the previous adjacent elements and increment the counter.
3645         {
3646             LocalRegister previousSibling(m_registerAllocator);
3647             m_assembler.move(elementAddressRegister, previousSibling);
3648
3649             Assembler::JumpList noMoreSiblingsCases;
3650
3651             Assembler::Label loopStart = m_assembler.label();
3652
3653             generateWalkToPreviousAdjacentElement(noMoreSiblingsCases, previousSibling);
3654
3655             Assembler::JumpList localFailureCases;
3656             generateElementMatchesSelectorList(localFailureCases, previousSibling, nthChildOfSelectorInfo->selectorList);
3657             localFailureCases.linkTo(loopStart, &m_assembler);
3658             m_assembler.add32(Assembler::TrustedImm32(1), elementCounter);
3659             m_assembler.jump().linkTo(loopStart, &m_assembler);
3660
3661             noMoreSiblingsCases.link(&m_assembler);
3662         }
3663
3664         generateNthFilterTest(failureCases, elementCounter, nthChildOfSelectorInfo->a, nthChildOfSelectorInfo->b);
3665     }
3666 }
3667
3668 void SelectorCodeGenerator::generateNthLastChildParentCheckAndRelationUpdate(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
3669 {
3670     LocalRegister parentNode(m_registerAllocator);
3671     generateWalkToParentNode(parentNode);
3672     failureCases.append(m_assembler.branchTestPtr(Assembler::Zero, parentNode));
3673     Assembler::Jump notElement = DOMJIT::branchTestIsElementFlagOnNode(m_assembler, Assembler::Zero, parentNode);
3674
3675     auto relation = fragmentMatchesRightmostOrAdjacentElement(fragment)
3676         ? Style::Relation::ChildrenAffectedByBackwardPositionalRules
3677         : Style::Relation::DescendantsAffectedByBackwardPositionalRules;
3678     generateAddStyleRelationIfResolvingStyle(parentNode, relation);
3679     failureCases.append(m_assembler.branchTest32(Assembler::Zero, Assembler::Address(parentNode, Node::nodeFlagsMemoryOffset()),
3680         Assembler::TrustedImm32(Node::flagIsParsingChildrenFinished())));
3681     Assembler::Jump parentNodeCheckEnd = m_assembler.jump();
3682
3683     notElement.link(&m_assembler);
3684     failureCases.append(DOMJIT::branchTestIsShadowRootFlagOnNode(m_assembler, Assembler::Zero, parentNode));
3685
3686     parentNodeCheckEnd.link(&m_assembler);
3687 }
3688
3689 void SelectorCodeGenerator::generateElementIsNthLastChild(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
3690 {
3691     generateNthLastChildParentCheckAndRelationUpdate(failureCases, fragment);
3692
3693     Vector<std::pair<int, int>, 32> validSubsetFilters;
3694     validSubsetFilters.reserveInitialCapacity(fragment.nthLastChildFilters.size());
3695     for (const auto& slot : fragment.nthLastChildFilters) {
3696         if (nthFilterIsAlwaysSatisified(slot.first, slot.second))
3697             continue;
3698         validSubsetFilters.uncheckedAppend(slot);
3699     }
3700     if (validSubsetFilters.isEmpty())
3701         return;
3702
3703     LocalRegister elementCounter(m_registerAllocator);
3704     { // Loop over the following sibling elements and increment the counter.
3705         LocalRegister nextSibling(m_registerAllocator);
3706         m_assembler.move(elementAddressRegister, nextSibling);
3707         // Setup the counter at 1.
3708         m_assembler.move(Assembler::TrustedImm32(1), elementCounter);
3709
3710         Assembler::JumpList noMoreSiblingsCases;
3711
3712         generateWalkToNextAdjacentElement(noMoreSiblingsCases, nextSibling);
3713
3714         Assembler::Label loopStart = m_assembler.label();
3715         m_assembler.add32(Assembler::TrustedImm32(1), elementCounter);
3716         generateWalkToNextAdjacentElement(noMoreSiblingsCases, nextSibling);
3717         m_assembler.jump().linkTo(loopStart, &m_assembler);
3718         noMoreSiblingsCases.link(&m_assembler);
3719     }
3720
3721     for (const auto& slot : validSubsetFilters)
3722         generateNthFilterTest(failureCases, elementCounter, slot.first, slot.second);
3723 }
3724
3725 void SelectorCodeGenerator::generateElementIsNthLastChildOf(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
3726 {
3727     generateNthLastChildParentCheckAndRelationUpdate(failureCases, fragment);
3728
3729     Vector<const NthChildOfSelectorInfo*> validSubsetFilters;
3730     validSubsetFilters.reserveInitialCapacity(fragment.nthLastChildOfFilters.size());
3731
3732     // The initial element must match the selector list.
3733     for (const NthChildOfSelectorInfo& nthLastChildOfSelectorInfo : fragment.nthLastChildOfFilters)
3734         generateElementMatchesSelectorList(failureCases, elementAddressRegister, nthLastChildOfSelectorInfo.selectorList);
3735     
3736     for (const NthChildOfSelectorInfo& nthLastChildOfSelectorInfo : fragment.nthLastChildOfFilters) {
3737         if (nthFilterIsAlwaysSatisified(nthLastChildOfSelectorInfo.a, nthLastChildOfSelectorInfo.b))
3738             continue;
3739         validSubsetFilters.uncheckedAppend(&nthLastChildOfSelectorInfo);
3740     }
3741     if (validSubsetFilters.isEmpty())
3742         return;
3743
3744     for (const NthChildOfSelectorInfo* nthLastChildOfSelectorInfo : validSubsetFilters) {
3745         // Setup the counter at 1.
3746         LocalRegisterWithPreference elementCounter(m_registerAllocator, JSC::GPRInfo::argumentGPR1);
3747         m_assembler.move(Assembler::TrustedImm32(1), elementCounter);
3748
3749         // Loop over the following adjacent elements and increment the counter.
3750         {
3751             LocalRegister nextSibling(m_registerAllocator);
3752             m_assembler.move(elementAddressRegister, nextSibling);
3753
3754             Assembler::JumpList noMoreSiblingsCases;
3755
3756             Assembler::Label loopStart = m_assembler.label();
3757
3758             generateWalkToNextAdjacentElement(noMoreSiblingsCases, nextSibling);
3759
3760             Assembler::JumpList localFailureCases;
3761             generateElementMatchesSelectorList(localFailureCases, nextSibling, nthLastChildOfSelectorInfo->selectorList);
3762             localFailureCases.linkTo(loopStart, &m_assembler);
3763             m_assembler.add32(Assembler::TrustedImm32(1), elementCounter);
3764             m_assembler.jump().linkTo(loopStart, &m_assembler);
3765
3766             noMoreSiblingsCases.link(&m_assembler);
3767         }