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