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