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