Start using the new :not() and :matches() in the Web Inspector
[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