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