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