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