CSS JIT cleanup: move two utility functions out of the properties-matcher section
[WebKit-https.git] / Source / WebCore / cssjit / SelectorCompiler.cpp
1 /*
2  * Copyright (C) 2013, 2014 Apple Inc. All rights reserved.
3  * Copyright (C) 2014 Yusuke Suzuki <utatane.tea@gmail.com>
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  *    notice, this list of conditions and the following disclaimer in the
12  *    documentation and/or other materials provided with the distribution.
13  *
14  * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
15  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
16  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
17  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
18  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
19  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
20  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
21  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
22  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
23  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
24  * THE POSSIBILITY OF SUCH DAMAGE.
25  */
26
27 #include "config.h"
28 #include "SelectorCompiler.h"
29
30 #if ENABLE(CSS_SELECTOR_JIT)
31
32 #include "CSSSelector.h"
33 #include "Element.h"
34 #include "ElementData.h"
35 #include "ElementRareData.h"
36 #include "FunctionCall.h"
37 #include "HTMLDocument.h"
38 #include "HTMLNames.h"
39 #include "InspectorInstrumentation.h"
40 #include "NodeRenderStyle.h"
41 #include "QualifiedName.h"
42 #include "RegisterAllocator.h"
43 #include "RenderElement.h"
44 #include "RenderStyle.h"
45 #include "SVGElement.h"
46 #include "SelectorCheckerTestFunctions.h"
47 #include "StackAllocator.h"
48 #include "StyledElement.h"
49 #include <JavaScriptCore/GPRInfo.h>
50 #include <JavaScriptCore/LinkBuffer.h>
51 #include <JavaScriptCore/MacroAssembler.h>
52 #include <JavaScriptCore/VM.h>
53 #include <limits>
54 #include <wtf/HashMap.h>
55 #include <wtf/HashSet.h>
56 #include <wtf/Vector.h>
57 #include <wtf/text/CString.h>
58
59 namespace WebCore {
60 namespace SelectorCompiler {
61
62 #define CSS_SELECTOR_JIT_DEBUGGING 0
63
64 enum class BacktrackingAction {
65     NoBacktracking,
66     JumpToDescendantEntryPoint,
67     JumpToIndirectAdjacentEntryPoint,
68     JumpToDescendantTreeWalkerEntryPoint,
69     JumpToIndirectAdjacentTreeWalkerEntryPoint,
70     JumpToDescendantTail,
71     JumpToDirectAdjacentTail
72 };
73
74 struct BacktrackingFlag {
75     enum {
76         DescendantEntryPoint = 1,
77         IndirectAdjacentEntryPoint = 1 << 1,
78         SaveDescendantBacktrackingStart = 1 << 2,
79         SaveAdjacentBacktrackingStart = 1 << 3,
80         DirectAdjacentTail = 1 << 4,
81         DescendantTail = 1 << 5,
82         InChainWithDescendantTail = 1 << 6
83     };
84 };
85
86 enum class FragmentRelation {
87     Rightmost,
88     Descendant,
89     Child,
90     DirectAdjacent,
91     IndirectAdjacent
92 };
93
94 enum class FunctionType {
95     SimpleSelectorChecker,
96     SelectorCheckerWithCheckingContext,
97     CannotMatchAnything,
98     CannotCompile
99 };
100
101 class AttributeMatchingInfo {
102 public:
103     AttributeMatchingInfo(const CSSSelector* selector, bool canDefaultToCaseSensitiveValueMatch)
104         : m_selector(selector)
105         , m_canDefaultToCaseSensitiveValueMatch(canDefaultToCaseSensitiveValueMatch)
106     {
107     }
108
109     bool canDefaultToCaseSensitiveValueMatch() const { return m_canDefaultToCaseSensitiveValueMatch; }
110     const CSSSelector& selector() const { return *m_selector; }
111
112 private:
113     const CSSSelector* m_selector;
114     bool m_canDefaultToCaseSensitiveValueMatch;
115 };
116
117 static const unsigned invalidHeight = std::numeric_limits<unsigned>::max();
118 static const unsigned invalidWidth = std::numeric_limits<unsigned>::max();
119
120 struct SelectorFragment {
121     SelectorFragment()
122         : traversalBacktrackingAction(BacktrackingAction::NoBacktracking)
123         , matchingTagNameBacktrackingAction(BacktrackingAction::NoBacktracking)
124         , matchingPostTagNameBacktrackingAction(BacktrackingAction::NoBacktracking)
125         , backtrackingFlags(0)
126         , tagNameMatchedBacktrackingStartHeightFromDescendant(invalidHeight)
127         , tagNameNotMatchedBacktrackingStartHeightFromDescendant(invalidHeight)
128         , heightFromDescendant(0)
129         , tagNameMatchedBacktrackingStartWidthFromIndirectAdjacent(invalidWidth)
130         , tagNameNotMatchedBacktrackingStartWidthFromIndirectAdjacent(invalidWidth)
131         , widthFromIndirectAdjacent(0)
132         , tagName(nullptr)
133         , id(nullptr)
134         , inFunctionalPseudoClass(false)
135     {
136     }
137     FragmentRelation relationToLeftFragment;
138     FragmentRelation relationToRightFragment;
139
140     BacktrackingAction traversalBacktrackingAction;
141     BacktrackingAction matchingTagNameBacktrackingAction;
142     BacktrackingAction matchingPostTagNameBacktrackingAction;
143     unsigned char backtrackingFlags;
144     unsigned tagNameMatchedBacktrackingStartHeightFromDescendant;
145     unsigned tagNameNotMatchedBacktrackingStartHeightFromDescendant;
146     unsigned heightFromDescendant;
147     unsigned tagNameMatchedBacktrackingStartWidthFromIndirectAdjacent;
148     unsigned tagNameNotMatchedBacktrackingStartWidthFromIndirectAdjacent;
149     unsigned widthFromIndirectAdjacent;
150
151     const QualifiedName* tagName;
152     const AtomicString* id;
153     Vector<const AtomicStringImpl*, 1> classNames;
154     HashSet<unsigned> pseudoClasses;
155     Vector<JSC::FunctionPtr> unoptimizedPseudoClasses;
156     Vector<AttributeMatchingInfo> attributes;
157     Vector<std::pair<int, int>> nthChildfilters;
158
159     bool inFunctionalPseudoClass;
160 };
161
162 struct TagNamePattern {
163     TagNamePattern()
164         : tagName(nullptr)
165         , inverted(false)
166     {
167     }
168     const QualifiedName* tagName;
169     bool inverted;
170 };
171
172 typedef JSC::MacroAssembler Assembler;
173 typedef Vector<SelectorFragment, 8> SelectorFragmentList;
174 typedef Vector<TagNamePattern, 8> TagNameList;
175
176 class SelectorCodeGenerator {
177 public:
178     SelectorCodeGenerator(const CSSSelector*, SelectorContext);
179     SelectorCompilationStatus compile(JSC::VM*, JSC::MacroAssemblerCodeRef&);
180
181 private:
182     static const Assembler::RegisterID returnRegister;
183     static const Assembler::RegisterID elementAddressRegister;
184     static const Assembler::RegisterID checkingContextRegister;
185     static const Assembler::RegisterID callFrameRegister;
186
187     void computeBacktrackingInformation();
188     void generateSelectorChecker();
189
190     // Element relations tree walker.
191     void generateWalkToParentNode(Assembler::RegisterID targetRegister);
192     void generateWalkToParentElement(Assembler::JumpList& failureCases, Assembler::RegisterID targetRegister);
193     void generateParentElementTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment&);
194     void generateAncestorTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment&);
195
196     void generateWalkToNextAdjacentElement(Assembler::JumpList& failureCases, Assembler::RegisterID);
197     void generateWalkToPreviousAdjacentElement(Assembler::JumpList& failureCases, Assembler::RegisterID);
198     void generateWalkToPreviousAdjacent(Assembler::JumpList& failureCases, const SelectorFragment&);
199     void generateDirectAdjacentTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment&);
200     void generateIndirectAdjacentTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment&);
201     void markParentElementIfResolvingStyle(int32_t);
202     void markParentElementIfResolvingStyle(JSC::FunctionPtr);
203
204     void linkFailures(Assembler::JumpList& globalFailureCases, BacktrackingAction, Assembler::JumpList& localFailureCases);
205     void generateAdjacentBacktrackingTail();
206     void generateDescendantBacktrackingTail();
207     void generateBacktrackingTailsIfNeeded(Assembler::JumpList& failureCases, const SelectorFragment&);
208
209     // Element properties matchers.
210     void generateElementMatching(Assembler::JumpList& matchingTagNameFailureCases, Assembler::JumpList& matchingPostTagNameFailureCases, const SelectorFragment&);
211     void generateElementDataMatching(Assembler::JumpList& failureCases, const SelectorFragment&);
212     void generateElementFunctionCallTest(Assembler::JumpList& failureCases, JSC::FunctionPtr);
213     void generateElementIsActive(Assembler::JumpList& failureCases, const SelectorFragment&);
214     void generateElementIsFirstChild(Assembler::JumpList& failureCases, const SelectorFragment&);
215     void generateElementIsHovered(Assembler::JumpList& failureCases, const SelectorFragment&);
216     void generateElementIsLastChild(Assembler::JumpList& failureCases, const SelectorFragment&);
217     void generateElementIsOnlyChild(Assembler::JumpList& failureCases, const SelectorFragment&);
218     void generateSynchronizeStyleAttribute(Assembler::RegisterID elementDataArraySizeAndFlags);
219     void generateSynchronizeAllAnimatedSVGAttribute(Assembler::RegisterID elementDataArraySizeAndFlags);
220     void generateElementAttributesMatching(Assembler::JumpList& failureCases, const LocalRegister& elementDataAddress, const SelectorFragment&);
221     void generateElementAttributeMatching(Assembler::JumpList& failureCases, Assembler::RegisterID currentAttributeAddress, Assembler::RegisterID decIndexRegister, const AttributeMatchingInfo& attributeInfo);
222     void generateElementAttributeValueMatching(Assembler::JumpList& failureCases, Assembler::RegisterID currentAttributeAddress, const AttributeMatchingInfo& attributeInfo);
223     void generateElementAttributeValueExactMatching(Assembler::JumpList& failureCases, Assembler::RegisterID currentAttributeAddress, const AtomicString& expectedValue, bool caseSensitive);
224     void generateElementAttributeFunctionCallValueMatching(Assembler::JumpList& failureCases, Assembler::RegisterID currentAttributeAddress, const AtomicString& expectedValue, bool caseSensitive, JSC::FunctionPtr caseSensitiveTest, JSC::FunctionPtr caseInsensitiveTest);
225     void generateElementHasTagName(Assembler::JumpList& failureCases, const QualifiedName& nameToMatch);
226     void generateElementHasId(Assembler::JumpList& failureCases, const LocalRegister& elementDataAddress, const AtomicString& idToMatch);
227     void generateElementHasClasses(Assembler::JumpList& failureCases, const LocalRegister& elementDataAddress, const Vector<const AtomicStringImpl*>& classNames);
228     void generateElementIsLink(Assembler::JumpList& failureCases);
229     void generateElementIsNthChild(Assembler::JumpList& failureCases, const SelectorFragment&);
230     void generateElementIsRoot(Assembler::JumpList& failureCases);
231     void generateElementIsTarget(Assembler::JumpList& failureCases);
232
233     // Helpers.
234     void addFlagsToElementStyleFromContext(Assembler::RegisterID checkingContext, int64_t);
235     Assembler::JumpList jumpIfNoPreviousAdjacentElement();
236     Assembler::JumpList jumpIfNoNextAdjacentElement();
237     Assembler::Jump jumpIfNotResolvingStyle(Assembler::RegisterID checkingContextRegister);
238     void generateSpecialFailureInQuirksModeForActiveAndHoverIfNeeded(Assembler::JumpList& failureCases, const SelectorFragment&);
239     Assembler::Jump modulo(JSC::MacroAssembler::ResultCondition, Assembler::RegisterID inputDividend, int divisor);
240     void moduloIsZero(Assembler::JumpList& failureCases, Assembler::RegisterID inputDividend, int divisor);
241
242     bool generatePrologue();
243     void generateEpilogue();
244     Vector<StackAllocator::StackReference> m_prologueStackReferences;
245     
246     Assembler m_assembler;
247     RegisterAllocator m_registerAllocator;
248     StackAllocator m_stackAllocator;
249     Vector<std::pair<Assembler::Call, JSC::FunctionPtr>> m_functionCalls;
250
251     SelectorContext m_selectorContext;
252     FunctionType m_functionType;
253     SelectorFragmentList m_selectorFragments;
254     bool m_needsAdjacentBacktrackingStart;
255
256     StackAllocator::StackReference m_checkingContextStackReference;
257
258     Assembler::Label m_descendantEntryPoint;
259     Assembler::Label m_indirectAdjacentEntryPoint;
260     Assembler::Label m_descendantTreeWalkerBacktrackingPoint;
261     Assembler::Label m_indirectAdjacentTreeWalkerBacktrackingPoint;
262     Assembler::RegisterID m_descendantBacktrackingStart;
263     Assembler::JumpList m_descendantBacktrackingFailureCases;
264     StackAllocator::StackReference m_adjacentBacktrackingStart;
265     Assembler::JumpList m_adjacentBacktrackingFailureCases;
266
267 #if CSS_SELECTOR_JIT_DEBUGGING
268     const CSSSelector* m_originalSelector;
269 #endif
270 };
271
272 const Assembler::RegisterID SelectorCodeGenerator::returnRegister = JSC::GPRInfo::returnValueGPR;
273 const Assembler::RegisterID SelectorCodeGenerator::elementAddressRegister = JSC::GPRInfo::argumentGPR0;
274 const Assembler::RegisterID SelectorCodeGenerator::checkingContextRegister = JSC::GPRInfo::argumentGPR1;
275 const Assembler::RegisterID SelectorCodeGenerator::callFrameRegister = JSC::GPRInfo::callFrameRegister;
276
277 SelectorCompilationStatus compileSelector(const CSSSelector* lastSelector, JSC::VM* vm, SelectorContext selectorContext, JSC::MacroAssemblerCodeRef& codeRef)
278 {
279     if (!vm->canUseJIT())
280         return SelectorCompilationStatus::CannotCompile;
281     SelectorCodeGenerator codeGenerator(lastSelector, selectorContext);
282     return codeGenerator.compile(vm, codeRef);
283 }
284
285 static inline FragmentRelation fragmentRelationForSelectorRelation(CSSSelector::Relation relation)
286 {
287     switch (relation) {
288     case CSSSelector::Descendant:
289         return FragmentRelation::Descendant;
290     case CSSSelector::Child:
291         return FragmentRelation::Child;
292     case CSSSelector::DirectAdjacent:
293         return FragmentRelation::DirectAdjacent;
294     case CSSSelector::IndirectAdjacent:
295         return FragmentRelation::IndirectAdjacent;
296     case CSSSelector::SubSelector:
297     case CSSSelector::ShadowDescendant:
298         ASSERT_NOT_REACHED();
299     }
300     ASSERT_NOT_REACHED();
301     return FragmentRelation::Descendant;
302 }
303
304 static inline FunctionType mostRestrictiveFunctionType(FunctionType a, FunctionType b)
305 {
306     return std::max(a, b);
307 }
308
309 static inline FunctionType addPseudoClassType(const CSSSelector& selector, SelectorFragment& fragment, SelectorContext selectorContext)
310 {
311     CSSSelector::PseudoClassType type = selector.pseudoClassType();
312     switch (type) {
313     // Unoptimized pseudo selector. They are just function call to a simple testing function.
314     case CSSSelector::PseudoClassAutofill:
315         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isAutofilled));
316         return FunctionType::SimpleSelectorChecker;
317     case CSSSelector::PseudoClassChecked:
318         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isChecked));
319         return FunctionType::SimpleSelectorChecker;
320     case CSSSelector::PseudoClassDefault:
321         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isDefaultButtonForForm));
322         return FunctionType::SimpleSelectorChecker;
323     case CSSSelector::PseudoClassDisabled:
324         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isDisabled));
325         return FunctionType::SimpleSelectorChecker;
326     case CSSSelector::PseudoClassEnabled:
327         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isEnabled));
328         return FunctionType::SimpleSelectorChecker;
329     case CSSSelector::PseudoClassFocus:
330         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(SelectorChecker::matchesFocusPseudoClass));
331         return FunctionType::SimpleSelectorChecker;
332     case CSSSelector::PseudoClassIndeterminate:
333         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(shouldAppearIndeterminate));
334         return FunctionType::SimpleSelectorChecker;
335     case CSSSelector::PseudoClassInvalid:
336         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isInvalid));
337         return FunctionType::SimpleSelectorChecker;
338     case CSSSelector::PseudoClassOptional:
339         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isOptionalFormControl));
340         return FunctionType::SimpleSelectorChecker;
341     case CSSSelector::PseudoClassReadOnly:
342         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesReadOnlyPseudoClass));
343         return FunctionType::SimpleSelectorChecker;
344     case CSSSelector::PseudoClassReadWrite:
345         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesReadWritePseudoClass));
346         return FunctionType::SimpleSelectorChecker;
347     case CSSSelector::PseudoClassRequired:
348         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isRequiredFormControl));
349         return FunctionType::SimpleSelectorChecker;
350     case CSSSelector::PseudoClassValid:
351         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isValid));
352         return FunctionType::SimpleSelectorChecker;
353 #if ENABLE(FULLSCREEN_API)
354     case CSSSelector::PseudoClassFullScreen:
355         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesFullScreenPseudoClass));
356         return FunctionType::SimpleSelectorChecker;
357 #endif
358 #if ENABLE(VIDEO_TRACK)
359     case CSSSelector::PseudoClassFuture:
360         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesFutureCuePseudoClass));
361         return FunctionType::SimpleSelectorChecker;
362     case CSSSelector::PseudoClassPast:
363         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesPastCuePseudoClass));
364         return FunctionType::SimpleSelectorChecker;
365 #endif
366
367     // Optimized pseudo selectors.
368     case CSSSelector::PseudoClassAnyLink:
369         fragment.pseudoClasses.add(CSSSelector::PseudoClassLink);
370         return FunctionType::SimpleSelectorChecker;
371
372     case CSSSelector::PseudoClassLink:
373     case CSSSelector::PseudoClassRoot:
374     case CSSSelector::PseudoClassTarget:
375         fragment.pseudoClasses.add(type);
376         return FunctionType::SimpleSelectorChecker;
377
378     case CSSSelector::PseudoClassActive:
379     case CSSSelector::PseudoClassFirstChild:
380     case CSSSelector::PseudoClassHover:
381     case CSSSelector::PseudoClassLastChild:
382     case CSSSelector::PseudoClassOnlyChild:
383         fragment.pseudoClasses.add(type);
384         if (selectorContext == SelectorContext::QuerySelector)
385             return FunctionType::SimpleSelectorChecker;
386         return FunctionType::SelectorCheckerWithCheckingContext;
387
388     case CSSSelector::PseudoClassNthChild:
389         {
390             if (!selector.parseNth())
391                 return FunctionType::CannotMatchAnything;
392
393             int a = selector.nthA();
394             int b = selector.nthB();
395
396             // The element count is always positive.
397             if (a <= 0 && b < 1)
398                 return FunctionType::CannotMatchAnything;
399
400             fragment.nthChildfilters.append(std::pair<int, int>(a, b));
401             if (selectorContext == SelectorContext::QuerySelector)
402                 return FunctionType::SimpleSelectorChecker;
403             return FunctionType::SelectorCheckerWithCheckingContext;
404         }
405     default:
406         break;
407     }
408     return FunctionType::CannotCompile;
409 }
410
411 inline SelectorCodeGenerator::SelectorCodeGenerator(const CSSSelector* rootSelector, SelectorContext selectorContext)
412     : m_stackAllocator(m_assembler)
413     , m_selectorContext(selectorContext)
414     , m_functionType(FunctionType::SimpleSelectorChecker)
415     , m_needsAdjacentBacktrackingStart(false)
416 #if CSS_SELECTOR_JIT_DEBUGGING
417     , m_originalSelector(rootSelector)
418 #endif
419 {
420 #if CSS_SELECTOR_JIT_DEBUGGING
421     dataLogF("Compiling \"%s\"\n", m_originalSelector->selectorText().utf8().data());
422 #endif
423
424     SelectorFragment fragment;
425     FragmentRelation relationToPreviousFragment = FragmentRelation::Rightmost;
426     for (const CSSSelector* selector = rootSelector; selector; selector = selector->tagHistory()) {
427         switch (selector->m_match) {
428         case CSSSelector::Tag:
429             ASSERT(!fragment.tagName);
430             fragment.tagName = &(selector->tagQName());
431             break;
432         case CSSSelector::Id: {
433             const AtomicString& id = selector->value();
434             if (fragment.id) {
435                 if (id != *fragment.id) {
436                     m_functionType = FunctionType::CannotMatchAnything;
437                     return;
438                 }
439             } else
440                 fragment.id = &(selector->value());
441             break;
442         }
443         case CSSSelector::Class:
444             fragment.classNames.append(selector->value().impl());
445             break;
446         case CSSSelector::PseudoClass:
447             m_functionType = mostRestrictiveFunctionType(m_functionType, addPseudoClassType(*selector, fragment, m_selectorContext));
448             if (m_functionType == FunctionType::CannotCompile || m_functionType == FunctionType::CannotMatchAnything)
449                 return;
450             break;
451         case CSSSelector::List:
452             if (selector->value().contains(' ')) {
453                 m_functionType = FunctionType::CannotMatchAnything;
454                 return;
455             }
456             FALLTHROUGH;
457         case CSSSelector::Begin:
458         case CSSSelector::End:
459         case CSSSelector::Contain:
460             if (selector->value().isEmpty()) {
461                 m_functionType = FunctionType::CannotMatchAnything;
462                 return;
463             }
464             FALLTHROUGH;
465         case CSSSelector::Exact:
466         case CSSSelector::Hyphen:
467             fragment.attributes.append(AttributeMatchingInfo(selector, HTMLDocument::isCaseSensitiveAttribute(selector->attribute())));
468             break;
469         case CSSSelector::Set:
470             fragment.attributes.append(AttributeMatchingInfo(selector, true));
471             break;
472         case CSSSelector::PagePseudoClass:
473             // Pseudo page class are only relevant for style resolution, they are ignored for matching.
474             break;
475         case CSSSelector::Unknown:
476             ASSERT_NOT_REACHED();
477             m_functionType = FunctionType::CannotMatchAnything;
478             return;
479         case CSSSelector::PseudoElement:
480             goto CannotHandleSelector;
481         }
482
483         CSSSelector::Relation relation = selector->relation();
484         if (relation == CSSSelector::SubSelector)
485             continue;
486
487         if (relation == CSSSelector::ShadowDescendant && !selector->isLastInTagHistory())
488             goto CannotHandleSelector;
489
490         if (relation == CSSSelector::DirectAdjacent || relation == CSSSelector::IndirectAdjacent) {
491             FunctionType relationFunctionType = FunctionType::SelectorCheckerWithCheckingContext;
492             if (m_selectorContext == SelectorContext::QuerySelector)
493                 relationFunctionType = FunctionType::SimpleSelectorChecker;
494             m_functionType = std::max(m_functionType, relationFunctionType);
495         }
496
497         fragment.relationToLeftFragment = fragmentRelationForSelectorRelation(relation);
498         fragment.relationToRightFragment = relationToPreviousFragment;
499         relationToPreviousFragment = fragment.relationToLeftFragment;
500
501         m_selectorFragments.append(fragment);
502         fragment = SelectorFragment();
503     }
504
505     computeBacktrackingInformation();
506
507     return;
508 CannotHandleSelector:
509     m_functionType = FunctionType::CannotCompile;
510 }
511
512 static inline bool attributeNameTestingRequiresNamespaceRegister(const CSSSelector& attributeSelector)
513 {
514     return attributeSelector.attribute().prefix() != starAtom && !attributeSelector.attribute().namespaceURI().isNull();
515 }
516
517 static inline bool attributeValueTestingRequiresCaseFoldingRegister(const AttributeMatchingInfo& attributeInfo)
518 {
519     return !attributeInfo.canDefaultToCaseSensitiveValueMatch();
520 }
521
522 static inline unsigned minimumRegisterRequirements(const SelectorFragmentList& selectorFragments)
523 {
524     // Strict minimum to match anything interesting:
525     // Element + BacktrackingRegister + ElementData + a pointer to values + an index on that pointer + the value we expect;
526     unsigned minimum = 6;
527
528     // Attributes cause some register pressure.
529     for (unsigned selectorFragmentIndex = 0; selectorFragmentIndex < selectorFragments.size(); ++selectorFragmentIndex) {
530         const SelectorFragment& selectorFragment = selectorFragments[selectorFragmentIndex];
531         const Vector<AttributeMatchingInfo>& attributes = selectorFragment.attributes;
532
533         unsigned attributeCount = attributes.size();
534         for (unsigned attributeIndex = 0; attributeIndex < attributeCount; ++attributeIndex) {
535             // Element + ElementData + scratchRegister + attributeArrayPointer + expectedLocalName + (qualifiedNameImpl && expectedValue).
536             unsigned attributeMinimum = 6;
537             if (selectorFragment.backtrackingFlags & BacktrackingFlag::InChainWithDescendantTail)
538                 attributeMinimum += 1; // If there is a DescendantTail, there is a backtracking register.
539
540             if (attributeIndex + 1 < attributeCount)
541                 attributeMinimum += 2; // For the local copy of the counter and attributeArrayPointer.
542
543             const AttributeMatchingInfo& attributeInfo = attributes[attributeIndex];
544             const CSSSelector& attributeSelector = attributeInfo.selector();
545             if (attributeNameTestingRequiresNamespaceRegister(attributeSelector)
546                 || attributeValueTestingRequiresCaseFoldingRegister(attributeInfo))
547                 attributeMinimum += 1;
548
549             minimum = std::max(minimum, attributeMinimum);
550         }
551     }
552
553     return minimum;
554 }
555
556 inline SelectorCompilationStatus SelectorCodeGenerator::compile(JSC::VM* vm, JSC::MacroAssemblerCodeRef& codeRef)
557 {
558     switch (m_functionType) {
559     case FunctionType::SimpleSelectorChecker:
560     case FunctionType::SelectorCheckerWithCheckingContext:
561         generateSelectorChecker();
562         break;
563     case FunctionType::CannotMatchAnything:
564         m_assembler.move(Assembler::TrustedImm32(0), returnRegister);
565         m_assembler.ret();
566         break;
567     case FunctionType::CannotCompile:
568         return SelectorCompilationStatus::CannotCompile;
569     }
570
571     JSC::LinkBuffer linkBuffer(*vm, &m_assembler, CSS_CODE_ID);
572     for (unsigned i = 0; i < m_functionCalls.size(); i++)
573         linkBuffer.link(m_functionCalls[i].first, m_functionCalls[i].second);
574
575 #if CSS_SELECTOR_JIT_DEBUGGING
576     codeRef = linkBuffer.finalizeCodeWithDisassembly("CSS Selector JIT for \"%s\"", m_originalSelector->selectorText().utf8().data());
577 #else
578     codeRef = FINALIZE_CODE(linkBuffer, ("CSS Selector JIT"));
579 #endif
580
581     if (m_functionType == FunctionType::SimpleSelectorChecker || m_functionType == FunctionType::CannotMatchAnything)
582         return SelectorCompilationStatus::SimpleSelectorChecker;
583     return SelectorCompilationStatus::SelectorCheckerWithCheckingContext;
584 }
585
586
587 static inline void updateChainStates(const SelectorFragment& fragment, bool& hasDescendantRelationOnTheRight, unsigned& ancestorPositionSinceDescendantRelation, bool& hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain, unsigned& adjacentPositionSinceIndirectAdjacentTreeWalk)
588 {
589     switch (fragment.relationToRightFragment) {
590     case FragmentRelation::Rightmost:
591         break;
592     case FragmentRelation::Descendant:
593         hasDescendantRelationOnTheRight = true;
594         ancestorPositionSinceDescendantRelation = 0;
595         hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain = false;
596         break;
597     case FragmentRelation::Child:
598         if (hasDescendantRelationOnTheRight)
599             ++ancestorPositionSinceDescendantRelation;
600         hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain = false;
601         break;
602     case FragmentRelation::DirectAdjacent:
603         if (hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain)
604             ++adjacentPositionSinceIndirectAdjacentTreeWalk;
605         break;
606     case FragmentRelation::IndirectAdjacent:
607         hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain = true;
608         adjacentPositionSinceIndirectAdjacentTreeWalk = 0;
609         break;
610     }
611 }
612
613 static inline bool isFirstAncestor(unsigned ancestorPositionSinceDescendantRelation)
614 {
615     return ancestorPositionSinceDescendantRelation == 1;
616 }
617
618 static inline bool isFirstAdjacent(unsigned adjacentPositionSinceIndirectAdjacentTreeWalk)
619 {
620     return adjacentPositionSinceIndirectAdjacentTreeWalk == 1;
621 }
622
623 static inline BacktrackingAction solveDescendantBacktrackingActionForChild(const SelectorFragment& fragment, unsigned backtrackingStartHeightFromDescendant)
624 {
625     // If height is invalid (e.g. There's no tag name).
626     if (backtrackingStartHeightFromDescendant == invalidHeight)
627         return BacktrackingAction::NoBacktracking;
628
629     // Start backtracking from the current element.
630     if (backtrackingStartHeightFromDescendant == fragment.heightFromDescendant)
631         return BacktrackingAction::JumpToDescendantEntryPoint;
632
633     // Start backtracking from the parent of current element.
634     if (backtrackingStartHeightFromDescendant == (fragment.heightFromDescendant + 1))
635         return BacktrackingAction::JumpToDescendantTreeWalkerEntryPoint;
636
637     return BacktrackingAction::JumpToDescendantTail;
638 }
639
640 static inline BacktrackingAction solveAdjacentBacktrackingActionForDirectAdjacent(const SelectorFragment& fragment, unsigned backtrackingStartWidthFromIndirectAdjacent)
641 {
642     // If width is invalid (e.g. There's no tag name).
643     if (backtrackingStartWidthFromIndirectAdjacent == invalidWidth)
644         return BacktrackingAction::NoBacktracking;
645
646     // Start backtracking from the current element.
647     if (backtrackingStartWidthFromIndirectAdjacent == fragment.widthFromIndirectAdjacent)
648         return BacktrackingAction::JumpToIndirectAdjacentEntryPoint;
649
650     // Start backtracking from the previous adjacent of current element.
651     if (backtrackingStartWidthFromIndirectAdjacent == (fragment.widthFromIndirectAdjacent + 1))
652         return BacktrackingAction::JumpToIndirectAdjacentTreeWalkerEntryPoint;
653
654     return BacktrackingAction::JumpToDirectAdjacentTail;
655 }
656
657 static inline BacktrackingAction solveAdjacentTraversalBacktrackingAction(const SelectorFragment& fragment, bool hasDescendantRelationOnTheRight)
658 {
659     if (!hasDescendantRelationOnTheRight)
660         return BacktrackingAction::NoBacktracking;
661
662     if (fragment.tagNameMatchedBacktrackingStartHeightFromDescendant == (fragment.heightFromDescendant + 1))
663         return BacktrackingAction::JumpToDescendantTreeWalkerEntryPoint;
664
665     return BacktrackingAction::JumpToDescendantTail;
666 }
667
668 static inline void solveBacktrackingAction(SelectorFragment& fragment, bool hasDescendantRelationOnTheRight, bool hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain)
669 {
670     switch (fragment.relationToRightFragment) {
671     case FragmentRelation::Rightmost:
672     case FragmentRelation::Descendant:
673         break;
674     case FragmentRelation::Child:
675         // Failure to match the element should resume matching at the nearest ancestor/descendant entry point.
676         if (hasDescendantRelationOnTheRight) {
677             fragment.matchingTagNameBacktrackingAction = solveDescendantBacktrackingActionForChild(fragment, fragment.tagNameNotMatchedBacktrackingStartHeightFromDescendant);
678             fragment.matchingPostTagNameBacktrackingAction = solveDescendantBacktrackingActionForChild(fragment, fragment.tagNameMatchedBacktrackingStartHeightFromDescendant);
679         }
680         break;
681     case FragmentRelation::DirectAdjacent:
682         // Failure on traversal implies no other sibling traversal can match. Matching should resume at the
683         // nearest ancestor/descendant traversal.
684         fragment.traversalBacktrackingAction = solveAdjacentTraversalBacktrackingAction(fragment, hasDescendantRelationOnTheRight);
685
686         // If the rightmost relation is a indirect adjacent, matching sould resume from there.
687         // Otherwise, we resume from the latest ancestor/descendant if any.
688         if (hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain) {
689             fragment.matchingTagNameBacktrackingAction = solveAdjacentBacktrackingActionForDirectAdjacent(fragment, fragment.tagNameNotMatchedBacktrackingStartWidthFromIndirectAdjacent);
690             fragment.matchingPostTagNameBacktrackingAction = solveAdjacentBacktrackingActionForDirectAdjacent(fragment, fragment.tagNameMatchedBacktrackingStartWidthFromIndirectAdjacent);
691         } else if (hasDescendantRelationOnTheRight) {
692             // Since we resume from the latest ancestor/descendant, the action is the same as the traversal action.
693             fragment.matchingTagNameBacktrackingAction = fragment.traversalBacktrackingAction;
694             fragment.matchingPostTagNameBacktrackingAction = fragment.traversalBacktrackingAction;
695         }
696         break;
697     case FragmentRelation::IndirectAdjacent:
698         // Failure on traversal implies no other sibling matching will succeed. Matching can resume
699         // from the latest ancestor/descendant.
700         fragment.traversalBacktrackingAction = solveAdjacentTraversalBacktrackingAction(fragment, hasDescendantRelationOnTheRight);
701         break;
702     }
703 }
704
705 enum class TagNameEquality {
706     StrictlyNotEqual,
707     MaybeEqual,
708     StrictlyEqual
709 };
710
711 static inline TagNameEquality equalTagNames(const QualifiedName* lhs, const QualifiedName* rhs)
712 {
713     if (!lhs || *lhs == anyQName())
714         return TagNameEquality::MaybeEqual;
715
716     if (!rhs || *rhs == anyQName())
717         return TagNameEquality::MaybeEqual;
718
719     ASSERT(lhs && rhs);
720
721     const AtomicString& lhsLocalName = lhs->localName();
722     const AtomicString& rhsLocalName = rhs->localName();
723     if (lhsLocalName != starAtom && rhsLocalName != starAtom) {
724         if (lhsLocalName != rhsLocalName)
725             return TagNameEquality::StrictlyNotEqual;
726         return TagNameEquality::StrictlyEqual;
727     }
728
729     const AtomicString& lhsNamespaceURI = lhs->namespaceURI();
730     const AtomicString& rhsNamespaceURI = rhs->namespaceURI();
731     if (lhsNamespaceURI != starAtom && rhsNamespaceURI != starAtom) {
732         if (lhsNamespaceURI != rhsNamespaceURI)
733             return TagNameEquality::StrictlyNotEqual;
734         return TagNameEquality::StrictlyEqual;
735     }
736
737     return TagNameEquality::MaybeEqual;
738 }
739
740 static inline bool equalTagNamePatterns(const TagNamePattern& lhs, const QualifiedName* rhs)
741 {
742     TagNameEquality result = equalTagNames(lhs.tagName, rhs);
743     if (result == TagNameEquality::MaybeEqual)
744         return true;
745
746     // If both rhs & lhs have actual localName (or NamespaceURI),
747     // TagNameEquality result becomes StrictlyEqual or StrictlyNotEqual Since inverted lhs never matches on rhs.
748     bool equal = result == TagNameEquality::StrictlyEqual;
749     if (lhs.inverted)
750         return !equal;
751     return equal;
752 }
753
754 // Find the largest matching prefix from already known tagNames.
755 // And by using this, compute an appropriate height of backtracking start element from the closest base element in the chain.
756 static inline unsigned computeBacktrackingStartOffsetInChain(const TagNameList& tagNames, unsigned maxPrefixSize)
757 {
758     RELEASE_ASSERT(!tagNames.isEmpty());
759     RELEASE_ASSERT(maxPrefixSize < tagNames.size());
760
761     for (unsigned largestPrefixSize = maxPrefixSize; largestPrefixSize > 0; --largestPrefixSize) {
762         unsigned offsetToLargestPrefix = tagNames.size() - largestPrefixSize;
763         bool matched = true;
764         // Since TagNamePatterns are pushed to a tagNames, check tagNames with reverse order.
765         for (unsigned i = 0; i < largestPrefixSize; ++i) {
766             unsigned lastIndex = tagNames.size() - 1;
767             unsigned currentIndex = lastIndex - i;
768             if (!equalTagNamePatterns(tagNames[currentIndex], tagNames[currentIndex - offsetToLargestPrefix].tagName)) {
769                 matched = false;
770                 break;
771             }
772         }
773         if (matched)
774             return offsetToLargestPrefix;
775     }
776     return tagNames.size();
777 }
778
779 static inline void computeBacktrackingHeightFromDescendant(SelectorFragment& fragment, TagNameList& tagNamesForChildChain, bool hasDescendantRelationOnTheRight, const SelectorFragment*& previousChildFragmentInChildChain)
780 {
781     if (!hasDescendantRelationOnTheRight)
782         return;
783
784     if (fragment.relationToRightFragment == FragmentRelation::Descendant) {
785         tagNamesForChildChain.clear();
786
787         TagNamePattern pattern;
788         pattern.tagName = fragment.tagName;
789         tagNamesForChildChain.append(pattern);
790         fragment.heightFromDescendant = 0;
791         previousChildFragmentInChildChain = nullptr;
792     } else if (fragment.relationToRightFragment == FragmentRelation::Child) {
793         TagNamePattern pattern;
794         pattern.tagName = fragment.tagName;
795         tagNamesForChildChain.append(pattern);
796
797         unsigned maxPrefixSize = tagNamesForChildChain.size() - 1;
798         if (previousChildFragmentInChildChain) {
799             RELEASE_ASSERT(tagNamesForChildChain.size() >= previousChildFragmentInChildChain->tagNameMatchedBacktrackingStartHeightFromDescendant);
800             maxPrefixSize = tagNamesForChildChain.size() - previousChildFragmentInChildChain->tagNameMatchedBacktrackingStartHeightFromDescendant;
801         }
802
803         if (pattern.tagName) {
804             // Compute height from descendant in the case that tagName is not matched.
805             tagNamesForChildChain.last().inverted = true;
806             fragment.tagNameNotMatchedBacktrackingStartHeightFromDescendant = computeBacktrackingStartOffsetInChain(tagNamesForChildChain, maxPrefixSize);
807         }
808
809         // Compute height from descendant in the case that tagName is matched.
810         tagNamesForChildChain.last().inverted = false;
811         fragment.tagNameMatchedBacktrackingStartHeightFromDescendant = computeBacktrackingStartOffsetInChain(tagNamesForChildChain, maxPrefixSize);
812         fragment.heightFromDescendant = tagNamesForChildChain.size() - 1;
813         previousChildFragmentInChildChain = &fragment;
814     } else {
815         if (previousChildFragmentInChildChain) {
816             fragment.tagNameNotMatchedBacktrackingStartHeightFromDescendant = previousChildFragmentInChildChain->tagNameNotMatchedBacktrackingStartHeightFromDescendant;
817             fragment.tagNameMatchedBacktrackingStartHeightFromDescendant = previousChildFragmentInChildChain->tagNameMatchedBacktrackingStartHeightFromDescendant;
818             fragment.heightFromDescendant = previousChildFragmentInChildChain->heightFromDescendant;
819         } else {
820             fragment.tagNameNotMatchedBacktrackingStartHeightFromDescendant = tagNamesForChildChain.size();
821             fragment.tagNameMatchedBacktrackingStartHeightFromDescendant = tagNamesForChildChain.size();
822             fragment.heightFromDescendant = 0;
823         }
824     }
825 }
826
827 static inline void computeBacktrackingWidthFromIndirectAdjacent(SelectorFragment& fragment, TagNameList& tagNamesForDirectAdjacentChain, bool hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain, const SelectorFragment*& previousDirectAdjacentFragmentInDirectAdjacentChain)
828 {
829     if (!hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain)
830         return;
831
832     if (fragment.relationToRightFragment == FragmentRelation::IndirectAdjacent) {
833         tagNamesForDirectAdjacentChain.clear();
834
835         TagNamePattern pattern;
836         pattern.tagName = fragment.tagName;
837         tagNamesForDirectAdjacentChain.append(pattern);
838         fragment.widthFromIndirectAdjacent = 0;
839         previousDirectAdjacentFragmentInDirectAdjacentChain = nullptr;
840     } else if (fragment.relationToRightFragment == FragmentRelation::DirectAdjacent) {
841         TagNamePattern pattern;
842         pattern.tagName = fragment.tagName;
843         tagNamesForDirectAdjacentChain.append(pattern);
844
845         unsigned maxPrefixSize = tagNamesForDirectAdjacentChain.size() - 1;
846         if (previousDirectAdjacentFragmentInDirectAdjacentChain) {
847             RELEASE_ASSERT(tagNamesForDirectAdjacentChain.size() >= previousDirectAdjacentFragmentInDirectAdjacentChain->tagNameMatchedBacktrackingStartWidthFromIndirectAdjacent);
848             maxPrefixSize = tagNamesForDirectAdjacentChain.size() - previousDirectAdjacentFragmentInDirectAdjacentChain->tagNameMatchedBacktrackingStartWidthFromIndirectAdjacent;
849         }
850
851         if (pattern.tagName) {
852             // Compute height from descendant in the case that tagName is not matched.
853             tagNamesForDirectAdjacentChain.last().inverted = true;
854             fragment.tagNameNotMatchedBacktrackingStartWidthFromIndirectAdjacent = computeBacktrackingStartOffsetInChain(tagNamesForDirectAdjacentChain, maxPrefixSize);
855         }
856
857         // Compute height from descendant in the case that tagName is matched.
858         tagNamesForDirectAdjacentChain.last().inverted = false;
859         fragment.tagNameMatchedBacktrackingStartWidthFromIndirectAdjacent = computeBacktrackingStartOffsetInChain(tagNamesForDirectAdjacentChain, maxPrefixSize);
860         fragment.widthFromIndirectAdjacent = tagNamesForDirectAdjacentChain.size() - 1;
861         previousDirectAdjacentFragmentInDirectAdjacentChain = &fragment;
862     }
863 }
864
865 static bool requiresAdjacentTail(const SelectorFragment& fragment)
866 {
867     ASSERT(fragment.traversalBacktrackingAction != BacktrackingAction::JumpToDirectAdjacentTail);
868     return fragment.matchingTagNameBacktrackingAction == BacktrackingAction::JumpToDirectAdjacentTail || fragment.matchingPostTagNameBacktrackingAction == BacktrackingAction::JumpToDirectAdjacentTail;
869 }
870
871 static bool requiresDescendantTail(const SelectorFragment& fragment)
872 {
873     return fragment.matchingTagNameBacktrackingAction == BacktrackingAction::JumpToDescendantTail || fragment.matchingPostTagNameBacktrackingAction == BacktrackingAction::JumpToDescendantTail || fragment.traversalBacktrackingAction == BacktrackingAction::JumpToDescendantTail;
874 }
875
876 void SelectorCodeGenerator::computeBacktrackingInformation()
877 {
878     bool hasDescendantRelationOnTheRight = false;
879     unsigned ancestorPositionSinceDescendantRelation = 0;
880     bool hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain = false;
881     unsigned adjacentPositionSinceIndirectAdjacentTreeWalk = 0;
882
883     bool needsAdjacentTail = false;
884     bool needsDescendantTail = false;
885     unsigned saveDescendantBacktrackingStartFragmentIndex = std::numeric_limits<unsigned>::max();
886     unsigned saveIndirectAdjacentBacktrackingStartFragmentIndex = std::numeric_limits<unsigned>::max();
887
888     TagNameList tagNamesForChildChain;
889     TagNameList tagNamesForDirectAdjacentChain;
890     const SelectorFragment* previousChildFragmentInChildChain = nullptr;
891     const SelectorFragment* previousDirectAdjacentFragmentInDirectAdjacentChain = nullptr;
892
893     for (unsigned i = 0; i < m_selectorFragments.size(); ++i) {
894         SelectorFragment& fragment = m_selectorFragments[i];
895
896         updateChainStates(fragment, hasDescendantRelationOnTheRight, ancestorPositionSinceDescendantRelation, hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain, adjacentPositionSinceIndirectAdjacentTreeWalk);
897
898         computeBacktrackingHeightFromDescendant(fragment, tagNamesForChildChain, hasDescendantRelationOnTheRight, previousChildFragmentInChildChain);
899
900         computeBacktrackingWidthFromIndirectAdjacent(fragment, tagNamesForDirectAdjacentChain, hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain, previousDirectAdjacentFragmentInDirectAdjacentChain);
901
902 #if CSS_SELECTOR_JIT_DEBUGGING
903         dataLogF("Computing fragment[%d] backtracking height %u. NotMatched %u / Matched %u | width %u. NotMatched %u / Matched %u\n", i, fragment.heightFromDescendant, fragment.tagNameNotMatchedBacktrackingStartHeightFromDescendant, fragment.tagNameMatchedBacktrackingStartHeightFromDescendant, fragment.widthFromIndirectAdjacent, fragment.tagNameNotMatchedBacktrackingStartWidthFromIndirectAdjacent, fragment.tagNameMatchedBacktrackingStartWidthFromIndirectAdjacent);
904 #endif
905
906         solveBacktrackingAction(fragment, hasDescendantRelationOnTheRight, hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain);
907
908         needsAdjacentTail |= requiresAdjacentTail(fragment);
909         needsDescendantTail |= requiresDescendantTail(fragment);
910
911         // Add code generation flags.
912         if (fragment.relationToLeftFragment != FragmentRelation::Descendant && fragment.relationToRightFragment == FragmentRelation::Descendant)
913             fragment.backtrackingFlags |= BacktrackingFlag::DescendantEntryPoint;
914         if (fragment.relationToLeftFragment == FragmentRelation::DirectAdjacent && fragment.relationToRightFragment == FragmentRelation::IndirectAdjacent)
915             fragment.backtrackingFlags |= BacktrackingFlag::IndirectAdjacentEntryPoint;
916         if (fragment.relationToLeftFragment != FragmentRelation::Descendant && fragment.relationToRightFragment == FragmentRelation::Child && isFirstAncestor(ancestorPositionSinceDescendantRelation)) {
917             ASSERT(saveDescendantBacktrackingStartFragmentIndex == std::numeric_limits<unsigned>::max());
918             saveDescendantBacktrackingStartFragmentIndex = i;
919         }
920         if (fragment.relationToLeftFragment == FragmentRelation::DirectAdjacent && fragment.relationToRightFragment == FragmentRelation::DirectAdjacent && isFirstAdjacent(adjacentPositionSinceIndirectAdjacentTreeWalk)) {
921             ASSERT(saveIndirectAdjacentBacktrackingStartFragmentIndex == std::numeric_limits<unsigned>::max());
922             saveIndirectAdjacentBacktrackingStartFragmentIndex = i;
923         }
924         if (fragment.relationToLeftFragment != FragmentRelation::DirectAdjacent) {
925             if (needsAdjacentTail) {
926                 ASSERT(fragment.relationToRightFragment == FragmentRelation::DirectAdjacent);
927                 ASSERT(saveIndirectAdjacentBacktrackingStartFragmentIndex != std::numeric_limits<unsigned>::max());
928                 fragment.backtrackingFlags |= BacktrackingFlag::DirectAdjacentTail;
929                 m_selectorFragments[saveIndirectAdjacentBacktrackingStartFragmentIndex].backtrackingFlags |= BacktrackingFlag::SaveAdjacentBacktrackingStart;
930                 m_needsAdjacentBacktrackingStart = true;
931                 needsAdjacentTail = false;
932             }
933             saveIndirectAdjacentBacktrackingStartFragmentIndex = std::numeric_limits<unsigned>::max();
934         }
935         if (fragment.relationToLeftFragment == FragmentRelation::Descendant) {
936             if (needsDescendantTail) {
937                 ASSERT(saveDescendantBacktrackingStartFragmentIndex != std::numeric_limits<unsigned>::max());
938                 fragment.backtrackingFlags |= BacktrackingFlag::DescendantTail;
939                 m_selectorFragments[saveDescendantBacktrackingStartFragmentIndex].backtrackingFlags |= BacktrackingFlag::SaveDescendantBacktrackingStart;
940                 needsDescendantTail = false;
941                 for (unsigned j = saveDescendantBacktrackingStartFragmentIndex; j <= i; ++j)
942                     m_selectorFragments[j].backtrackingFlags |= BacktrackingFlag::InChainWithDescendantTail;
943             }
944             saveDescendantBacktrackingStartFragmentIndex = std::numeric_limits<unsigned>::max();
945         }
946     }
947 }
948
949 inline bool SelectorCodeGenerator::generatePrologue()
950 {
951 #if CPU(ARM64)
952     Vector<JSC::MacroAssembler::RegisterID, 2> prologueRegisters;
953     prologueRegisters.append(JSC::ARM64Registers::lr);
954     prologueRegisters.append(JSC::ARM64Registers::fp);
955     m_prologueStackReferences = m_stackAllocator.push(prologueRegisters);
956     return true;
957 #elif CPU(X86_64) && CSS_SELECTOR_JIT_DEBUGGING
958     Vector<JSC::MacroAssembler::RegisterID, 1> prologueRegister;
959     prologueRegister.append(callFrameRegister);
960     m_prologueStackReferences = m_stackAllocator.push(prologueRegister);
961     return true;
962 #endif
963     return false;
964 }
965     
966 inline void SelectorCodeGenerator::generateEpilogue()
967 {
968 #if CPU(ARM64)
969     Vector<JSC::MacroAssembler::RegisterID, 2> prologueRegisters;
970     prologueRegisters.append(JSC::ARM64Registers::lr);
971     prologueRegisters.append(JSC::ARM64Registers::fp);
972     m_stackAllocator.pop(m_prologueStackReferences, prologueRegisters);
973 #elif CPU(X86_64) && CSS_SELECTOR_JIT_DEBUGGING
974     Vector<JSC::MacroAssembler::RegisterID, 1> prologueRegister;
975     prologueRegister.append(callFrameRegister);
976     m_stackAllocator.pop(m_prologueStackReferences, prologueRegister);
977 #endif
978 }
979     
980 void SelectorCodeGenerator::generateSelectorChecker()
981 {
982     bool needsEpilogue = generatePrologue();
983     
984     Vector<StackAllocator::StackReference> calleeSavedRegisterStackReferences;
985     bool reservedCalleeSavedRegisters = false;
986     unsigned availableRegisterCount = m_registerAllocator.availableRegisterCount();
987     unsigned minimumRegisterCountForAttributes = minimumRegisterRequirements(m_selectorFragments);
988     ASSERT(minimumRegisterCountForAttributes <= registerCount);
989     if (availableRegisterCount < minimumRegisterCountForAttributes) {
990         reservedCalleeSavedRegisters = true;
991         calleeSavedRegisterStackReferences = m_stackAllocator.push(m_registerAllocator.reserveCalleeSavedRegisters(minimumRegisterCountForAttributes - availableRegisterCount));
992     }
993
994     m_registerAllocator.allocateRegister(elementAddressRegister);
995
996     if (m_functionType == FunctionType::SelectorCheckerWithCheckingContext)
997         m_checkingContextStackReference = m_stackAllocator.push(checkingContextRegister);
998
999     if (m_needsAdjacentBacktrackingStart)
1000         m_adjacentBacktrackingStart = m_stackAllocator.allocateUninitialized();
1001
1002     Assembler::JumpList failureCases;
1003
1004     for (unsigned i = 0; i < m_selectorFragments.size(); ++i) {
1005         const SelectorFragment& fragment = m_selectorFragments[i];
1006         switch (fragment.relationToRightFragment) {
1007         case FragmentRelation::Rightmost:
1008             generateElementMatching(failureCases, failureCases, fragment);
1009             break;
1010         case FragmentRelation::Descendant:
1011             generateAncestorTreeWalker(failureCases, fragment);
1012             break;
1013         case FragmentRelation::Child:
1014             generateParentElementTreeWalker(failureCases, fragment);
1015             break;
1016         case FragmentRelation::DirectAdjacent:
1017             generateDirectAdjacentTreeWalker(failureCases, fragment);
1018             break;
1019         case FragmentRelation::IndirectAdjacent:
1020             generateIndirectAdjacentTreeWalker(failureCases, fragment);
1021             break;
1022         }
1023         generateBacktrackingTailsIfNeeded(failureCases, fragment);
1024     }
1025
1026     m_registerAllocator.deallocateRegister(elementAddressRegister);
1027
1028     if (m_functionType == FunctionType::SimpleSelectorChecker) {
1029         if (!m_needsAdjacentBacktrackingStart && !reservedCalleeSavedRegisters && !needsEpilogue) {
1030             // Success.
1031             m_assembler.move(Assembler::TrustedImm32(1), returnRegister);
1032             m_assembler.ret();
1033
1034             // Failure.
1035             if (!failureCases.empty()) {
1036                 failureCases.link(&m_assembler);
1037                 m_assembler.move(Assembler::TrustedImm32(0), returnRegister);
1038                 m_assembler.ret();
1039             }
1040         } else {
1041             // Success.
1042             m_assembler.move(Assembler::TrustedImm32(1), returnRegister);
1043
1044             // Failure.
1045             if (!failureCases.empty()) {
1046                 Assembler::Jump skipFailureCase = m_assembler.jump();
1047                 failureCases.link(&m_assembler);
1048                 m_assembler.move(Assembler::TrustedImm32(0), returnRegister);
1049                 skipFailureCase.link(&m_assembler);
1050             }
1051
1052             if (m_needsAdjacentBacktrackingStart)
1053                 m_stackAllocator.popAndDiscardUpTo(m_adjacentBacktrackingStart);
1054             if (reservedCalleeSavedRegisters)
1055                 m_stackAllocator.pop(calleeSavedRegisterStackReferences, m_registerAllocator.restoreCalleeSavedRegisters());
1056             if (needsEpilogue)
1057                 generateEpilogue();
1058             m_assembler.ret();
1059         }
1060     } else {
1061         ASSERT(m_functionType == FunctionType::SelectorCheckerWithCheckingContext);
1062
1063         // Success.
1064         m_assembler.move(Assembler::TrustedImm32(1), returnRegister);
1065
1066         // Failure.
1067         if (!failureCases.empty()) {
1068             Assembler::Jump skipFailureCase = m_assembler.jump();
1069             failureCases.link(&m_assembler);
1070             m_assembler.move(Assembler::TrustedImm32(0), returnRegister);
1071             skipFailureCase.link(&m_assembler);
1072         }
1073
1074         m_stackAllocator.popAndDiscardUpTo(m_checkingContextStackReference);
1075         if (reservedCalleeSavedRegisters)
1076             m_stackAllocator.pop(calleeSavedRegisterStackReferences, m_registerAllocator.restoreCalleeSavedRegisters());
1077         if (needsEpilogue)
1078             generateEpilogue();
1079         m_assembler.ret();
1080     }
1081 }
1082
1083 static inline Assembler::Jump testIsElementFlagOnNode(Assembler::ResultCondition condition, Assembler& assembler, Assembler::RegisterID nodeAddress)
1084 {
1085     return assembler.branchTest32(condition, Assembler::Address(nodeAddress, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagIsElement()));
1086 }
1087
1088 void SelectorCodeGenerator::generateWalkToParentNode(Assembler::RegisterID targetRegister)
1089 {
1090     m_assembler.loadPtr(Assembler::Address(elementAddressRegister, Node::parentNodeMemoryOffset()), targetRegister);
1091 }
1092
1093 void SelectorCodeGenerator::generateWalkToParentElement(Assembler::JumpList& failureCases, Assembler::RegisterID targetRegister)
1094 {
1095     //    ContainerNode* parent = parentNode()
1096     //    if (!parent || !parent->isElementNode())
1097     //         failure
1098     generateWalkToParentNode(targetRegister);
1099     failureCases.append(m_assembler.branchTestPtr(Assembler::Zero, targetRegister));
1100     failureCases.append(testIsElementFlagOnNode(Assembler::Zero, m_assembler, targetRegister));
1101 }
1102
1103 void SelectorCodeGenerator::generateParentElementTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
1104 {
1105     Assembler::JumpList traversalFailureCases;
1106     generateWalkToParentElement(traversalFailureCases, elementAddressRegister);
1107     linkFailures(failureCases, fragment.traversalBacktrackingAction, traversalFailureCases);
1108
1109     Assembler::JumpList matchingTagNameFailureCases;
1110     Assembler::JumpList matchingPostTagNameFailureCases;
1111     generateElementMatching(matchingTagNameFailureCases, matchingPostTagNameFailureCases, fragment);
1112     linkFailures(failureCases, fragment.matchingTagNameBacktrackingAction, matchingTagNameFailureCases);
1113     linkFailures(failureCases, fragment.matchingPostTagNameBacktrackingAction, matchingPostTagNameFailureCases);
1114
1115     if (fragment.backtrackingFlags & BacktrackingFlag::SaveDescendantBacktrackingStart) {
1116         m_descendantBacktrackingStart = m_registerAllocator.allocateRegister();
1117         m_assembler.move(elementAddressRegister, m_descendantBacktrackingStart);
1118     }
1119 }
1120
1121 void SelectorCodeGenerator::generateAncestorTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
1122 {
1123     // Loop over the ancestors until one of them matches the fragment.
1124     Assembler::Label loopStart(m_assembler.label());
1125
1126     if (fragment.backtrackingFlags & BacktrackingFlag::DescendantEntryPoint)
1127         m_descendantTreeWalkerBacktrackingPoint = m_assembler.label();
1128
1129     generateWalkToParentElement(failureCases, elementAddressRegister);
1130
1131     if (fragment.backtrackingFlags & BacktrackingFlag::DescendantEntryPoint)
1132         m_descendantEntryPoint = m_assembler.label();
1133
1134     Assembler::JumpList matchingFailureCases;
1135     generateElementMatching(matchingFailureCases, matchingFailureCases, fragment);
1136     matchingFailureCases.linkTo(loopStart, &m_assembler);
1137 }
1138
1139 inline void SelectorCodeGenerator::generateWalkToNextAdjacentElement(Assembler::JumpList& failureCases, Assembler::RegisterID workRegister)
1140 {
1141     Assembler::Label loopStart = m_assembler.label();
1142     m_assembler.loadPtr(Assembler::Address(workRegister, Node::nextSiblingMemoryOffset()), workRegister);
1143     failureCases.append(m_assembler.branchTestPtr(Assembler::Zero, workRegister));
1144     testIsElementFlagOnNode(Assembler::Zero, m_assembler, workRegister).linkTo(loopStart, &m_assembler);
1145 }
1146
1147 inline void SelectorCodeGenerator::generateWalkToPreviousAdjacentElement(Assembler::JumpList& failureCases, Assembler::RegisterID workRegister)
1148 {
1149     Assembler::Label loopStart = m_assembler.label();
1150     m_assembler.loadPtr(Assembler::Address(workRegister, Node::previousSiblingMemoryOffset()), workRegister);
1151     failureCases.append(m_assembler.branchTestPtr(Assembler::Zero, workRegister));
1152     testIsElementFlagOnNode(Assembler::Zero, m_assembler, workRegister).linkTo(loopStart, &m_assembler);
1153 }
1154
1155 void SelectorCodeGenerator::generateWalkToPreviousAdjacent(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
1156 {
1157     //    do {
1158     //        previousSibling = previousSibling->previousSibling();
1159     //        if (!previousSibling)
1160     //            failure!
1161     //    while (!previousSibling->isElement());
1162     Assembler::RegisterID previousSibling;
1163     bool useTailOnTraversalFailure = fragment.traversalBacktrackingAction >= BacktrackingAction::JumpToDescendantTail;
1164     if (!useTailOnTraversalFailure) {
1165         // If the current fragment is not dependant on a previously saved elementAddressRegister, a fast recover
1166         // from a failure would resume with elementAddressRegister.
1167         // When walking to the previous sibling, the failure can be that previousSibling is null. We cannot backtrack
1168         // with a null elementAddressRegister so we do the traversal on a copy.
1169         previousSibling = m_registerAllocator.allocateRegister();
1170         m_assembler.move(elementAddressRegister, previousSibling);
1171     } else
1172         previousSibling = elementAddressRegister;
1173
1174     Assembler::JumpList traversalFailureCases;
1175     generateWalkToPreviousAdjacentElement(traversalFailureCases, previousSibling);
1176     linkFailures(failureCases, fragment.traversalBacktrackingAction, traversalFailureCases);
1177
1178     // On success, move previousSibling over to elementAddressRegister if we could not work on elementAddressRegister directly.
1179     if (!useTailOnTraversalFailure) {
1180         m_assembler.move(previousSibling, elementAddressRegister);
1181         m_registerAllocator.deallocateRegister(previousSibling);
1182     }
1183 }
1184
1185 void SelectorCodeGenerator::generateDirectAdjacentTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
1186 {
1187     markParentElementIfResolvingStyle(Node::flagChildrenAffectedByDirectAdjacentRulesFlag());
1188
1189     generateWalkToPreviousAdjacent(failureCases, fragment);
1190
1191     Assembler::JumpList matchingTagNameFailureCases;
1192     Assembler::JumpList matchingPostTagNameFailureCases;
1193     generateElementMatching(matchingTagNameFailureCases, matchingPostTagNameFailureCases, fragment);
1194     linkFailures(failureCases, fragment.matchingTagNameBacktrackingAction, matchingTagNameFailureCases);
1195     linkFailures(failureCases, fragment.matchingPostTagNameBacktrackingAction, matchingPostTagNameFailureCases);
1196
1197     if (fragment.backtrackingFlags & BacktrackingFlag::SaveAdjacentBacktrackingStart) {
1198         unsigned offsetToAdjacentBacktrackingStart = m_stackAllocator.offsetToStackReference(m_adjacentBacktrackingStart);
1199         m_assembler.storePtr(elementAddressRegister, Assembler::Address(Assembler::stackPointerRegister, offsetToAdjacentBacktrackingStart));
1200     }
1201 }
1202
1203 void SelectorCodeGenerator::generateIndirectAdjacentTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
1204 {
1205     markParentElementIfResolvingStyle(Element::setChildrenAffectedByForwardPositionalRules);
1206
1207     Assembler::Label loopStart(m_assembler.label());
1208
1209     if (fragment.backtrackingFlags & BacktrackingFlag::IndirectAdjacentEntryPoint)
1210         m_indirectAdjacentTreeWalkerBacktrackingPoint = m_assembler.label();
1211
1212     generateWalkToPreviousAdjacent(failureCases, fragment);
1213
1214     if (fragment.backtrackingFlags & BacktrackingFlag::IndirectAdjacentEntryPoint)
1215         m_indirectAdjacentEntryPoint = m_assembler.label();
1216
1217     Assembler::JumpList localFailureCases;
1218     generateElementMatching(localFailureCases, localFailureCases, fragment);
1219     localFailureCases.linkTo(loopStart, &m_assembler);
1220 }
1221
1222
1223 void SelectorCodeGenerator::addFlagsToElementStyleFromContext(Assembler::RegisterID checkingContext, int64_t newFlag)
1224 {
1225     LocalRegister childStyle(m_registerAllocator);
1226     m_assembler.loadPtr(Assembler::Address(checkingContext, OBJECT_OFFSETOF(CheckingContext, elementStyle)), childStyle);
1227
1228     // FIXME: We should look into doing something smart in MacroAssembler instead.
1229     LocalRegister flags(m_registerAllocator);
1230     Assembler::Address flagAddress(childStyle, RenderStyle::noninheritedFlagsMemoryOffset() + RenderStyle::NonInheritedFlags::flagsMemoryOffset());
1231     m_assembler.load64(flagAddress, flags);
1232     LocalRegister isFirstChildStateFlagImmediate(m_registerAllocator);
1233     m_assembler.move(Assembler::TrustedImm64(newFlag), isFirstChildStateFlagImmediate);
1234     m_assembler.or64(isFirstChildStateFlagImmediate, flags);
1235     m_assembler.store64(flags, flagAddress);
1236 }
1237
1238 Assembler::JumpList SelectorCodeGenerator::jumpIfNoPreviousAdjacentElement()
1239 {
1240     Assembler::JumpList successCase;
1241     LocalRegister previousSibling(m_registerAllocator);
1242     m_assembler.move(elementAddressRegister, previousSibling);
1243     generateWalkToPreviousAdjacentElement(successCase, previousSibling);
1244     return successCase;
1245 }
1246
1247 Assembler::JumpList SelectorCodeGenerator::jumpIfNoNextAdjacentElement()
1248 {
1249     Assembler::JumpList successCase;
1250     LocalRegister nextSibling(m_registerAllocator);
1251     m_assembler.move(elementAddressRegister, nextSibling);
1252     generateWalkToNextAdjacentElement(successCase, nextSibling);
1253     return successCase;
1254 }
1255
1256 Assembler::Jump SelectorCodeGenerator::jumpIfNotResolvingStyle(Assembler::RegisterID checkingContext)
1257 {
1258     RELEASE_ASSERT(m_selectorContext == SelectorContext::RuleCollector);
1259
1260     // Get the checking context.
1261     unsigned offsetToCheckingContext = m_stackAllocator.offsetToStackReference(m_checkingContextStackReference);
1262     m_assembler.loadPtr(Assembler::Address(Assembler::stackPointerRegister, offsetToCheckingContext), checkingContext);
1263
1264     // If we not resolving style, skip the whole marking.
1265     return m_assembler.branch8(Assembler::NotEqual, Assembler::Address(checkingContext, OBJECT_OFFSETOF(CheckingContext, resolvingMode)), Assembler::TrustedImm32(SelectorChecker::ResolvingStyle));
1266 }
1267
1268 static bool fragmentOnlyMatchesLinksInQuirksMode(const SelectorFragment& fragment)
1269 {
1270     // For quirks mode, follow this: http://quirks.spec.whatwg.org/#the-:active-and-:hover-quirk
1271     // 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.
1272     //
1273     //    selector uses the ':active' or ':hover' pseudo-classes.
1274     //    selector does not use a type selector.
1275     //    selector does not use an attribute selector.
1276     //    selector does not use an ID selector.
1277     //    selector does not use a class selector.
1278     //    selector does not use a pseudo-class selector other than ':active' and ':hover'.
1279     //    selector does not use a pseudo-element selector.
1280     //    selector is not part of an argument to a functional pseudo-class or pseudo-element.
1281     if (fragment.tagName && *fragment.tagName != anyQName())
1282         return false;
1283
1284     if (!fragment.attributes.isEmpty())
1285         return false;
1286
1287     if (fragment.id)
1288         return false;
1289
1290     if (!fragment.classNames.isEmpty())
1291         return false;
1292
1293     if (!fragment.unoptimizedPseudoClasses.isEmpty() || !fragment.nthChildfilters.isEmpty())
1294         return false;
1295
1296     for (unsigned pseudoClassType : fragment.pseudoClasses) {
1297         if (pseudoClassType != CSSSelector::PseudoClassHover && pseudoClassType != CSSSelector::PseudoClassActive)
1298             return false;
1299     }
1300
1301     if (fragment.inFunctionalPseudoClass)
1302         return false;
1303
1304     return true;
1305 }
1306
1307 static void getDocument(Assembler& assembler, Assembler::RegisterID element, Assembler::RegisterID output)
1308 {
1309     assembler.loadPtr(Assembler::Address(element, Node::treeScopeMemoryOffset()), output);
1310     assembler.loadPtr(Assembler::Address(output, TreeScope::documentScopeMemoryOffset()), output);
1311 }
1312
1313 void SelectorCodeGenerator::generateSpecialFailureInQuirksModeForActiveAndHoverIfNeeded(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
1314 {
1315     if (fragmentOnlyMatchesLinksInQuirksMode(fragment)) {
1316         // If the element is a link, it can always match :hover or :active.
1317         Assembler::Jump isLink = m_assembler.branchTest32(Assembler::NonZero, Assembler::Address(elementAddressRegister, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagIsLink()));
1318
1319         // Only quirks mode restrict :hover and :active.
1320         static_assert(sizeof(DocumentCompatibilityMode) == 1, "We generate a byte load/test for the compatibility mode.");
1321         LocalRegister documentAddress(m_registerAllocator);
1322         getDocument(m_assembler, elementAddressRegister, documentAddress);
1323         failureCases.append(m_assembler.branchTest8(Assembler::NonZero, Assembler::Address(documentAddress, Document::compatibilityModeMemoryOffset()), Assembler::TrustedImm32(static_cast<std::underlying_type<DocumentCompatibilityMode>::type>(DocumentCompatibilityMode::QuirksMode))));
1324
1325         isLink.link(&m_assembler);
1326     }
1327 }
1328
1329 // The value in inputDividend is destroyed by the modulo operation.
1330 Assembler::Jump SelectorCodeGenerator::modulo(Assembler::ResultCondition condition, Assembler::RegisterID inputDividend, int divisor)
1331 {
1332     RELEASE_ASSERT(divisor);
1333 #if CPU(ARM64)
1334     LocalRegister divisorRegister(m_registerAllocator);
1335     m_assembler.move(Assembler::TrustedImm32(divisor), divisorRegister);
1336
1337     LocalRegister resultRegister(m_registerAllocator);
1338     m_assembler.m_assembler.sdiv<32>(resultRegister, inputDividend, divisorRegister);
1339     m_assembler.mul32(divisorRegister, resultRegister);
1340     return m_assembler.branchSub32(condition, inputDividend, resultRegister, resultRegister);
1341 #elif CPU(X86_64)
1342     // idiv takes RAX + an arbitrary register, and return RAX + RDX. Most of this code is about doing
1343     // an efficient allocation of those registers. If a register is already in use and is not the inputDividend,
1344     // we first try to copy it to a temporary register, it that is not possible we fall back to the stack.
1345     enum class RegisterAllocationType {
1346         External,
1347         AllocatedLocally,
1348         CopiedToTemporary,
1349         PushedToStack
1350     };
1351
1352     // 1) Get RAX and RDX.
1353     // If they are already used, push them to the stack.
1354     Assembler::RegisterID dividend = JSC::X86Registers::eax;
1355     RegisterAllocationType dividendAllocation = RegisterAllocationType::External;
1356     StackAllocator::StackReference temporaryDividendStackReference;
1357     Assembler::RegisterID temporaryDividendCopy = InvalidGPRReg;
1358     if (inputDividend != dividend) {
1359         bool registerIsInUse = m_registerAllocator.allocatedRegisters().contains(dividend);
1360         if (registerIsInUse) {
1361             if (m_registerAllocator.availableRegisterCount()) {
1362                 temporaryDividendCopy = m_registerAllocator.allocateRegister();
1363                 m_assembler.move(dividend, temporaryDividendCopy);
1364                 dividendAllocation = RegisterAllocationType::CopiedToTemporary;
1365             } else {
1366                 temporaryDividendStackReference = m_stackAllocator.push(dividend);
1367                 dividendAllocation = RegisterAllocationType::PushedToStack;
1368             }
1369         } else {
1370             m_registerAllocator.allocateRegister(dividend);
1371             dividendAllocation = RegisterAllocationType::AllocatedLocally;
1372         }
1373         m_assembler.move(inputDividend, dividend);
1374     }
1375
1376     Assembler::RegisterID remainder = JSC::X86Registers::edx;
1377     RegisterAllocationType remainderAllocation = RegisterAllocationType::External;
1378     StackAllocator::StackReference temporaryRemainderStackReference;
1379     Assembler::RegisterID temporaryRemainderCopy = InvalidGPRReg;
1380     if (inputDividend != remainder) {
1381         bool registerIsInUse = m_registerAllocator.allocatedRegisters().contains(remainder);
1382         if (registerIsInUse) {
1383             if (m_registerAllocator.availableRegisterCount()) {
1384                 temporaryRemainderCopy = m_registerAllocator.allocateRegister();
1385                 m_assembler.move(remainder, temporaryRemainderCopy);
1386                 remainderAllocation = RegisterAllocationType::CopiedToTemporary;
1387             } else {
1388                 temporaryRemainderStackReference = m_stackAllocator.push(remainder);
1389                 remainderAllocation = RegisterAllocationType::PushedToStack;
1390             }
1391         } else {
1392             m_registerAllocator.allocateRegister(remainder);
1393             remainderAllocation = RegisterAllocationType::AllocatedLocally;
1394         }
1395     }
1396     m_assembler.m_assembler.cdq();
1397
1398     // 2) Perform the division with idiv.
1399     {
1400         LocalRegister divisorRegister(m_registerAllocator);
1401         m_assembler.move(Assembler::TrustedImm64(divisor), divisorRegister);
1402         m_assembler.m_assembler.idivl_r(divisorRegister);
1403         m_assembler.test32(condition, remainder);
1404     }
1405
1406     // 3) Return RAX and RDX.
1407     if (remainderAllocation == RegisterAllocationType::AllocatedLocally)
1408         m_registerAllocator.deallocateRegister(remainder);
1409     else if (remainderAllocation == RegisterAllocationType::CopiedToTemporary) {
1410         m_assembler.move(temporaryRemainderCopy, remainder);
1411         m_registerAllocator.deallocateRegister(temporaryRemainderCopy);
1412     } else if (remainderAllocation == RegisterAllocationType::PushedToStack)
1413         m_stackAllocator.pop(temporaryRemainderStackReference, remainder);
1414
1415     if (dividendAllocation == RegisterAllocationType::AllocatedLocally)
1416         m_registerAllocator.deallocateRegister(dividend);
1417     else if (dividendAllocation == RegisterAllocationType::CopiedToTemporary) {
1418         m_assembler.move(temporaryDividendCopy, dividend);
1419         m_registerAllocator.deallocateRegister(temporaryDividendCopy);
1420     } else if (dividendAllocation == RegisterAllocationType::PushedToStack)
1421         m_stackAllocator.pop(temporaryDividendStackReference, dividend);
1422
1423     // 4) Branch on the test.
1424     return m_assembler.branch(condition);
1425 #else
1426 #error Modulo is not implemented for this architecture.
1427 #endif
1428 }
1429
1430 void SelectorCodeGenerator::moduloIsZero(Assembler::JumpList& failureCases, Assembler::RegisterID inputDividend, int divisor)
1431 {
1432     if (divisor == 1 || divisor == -1)
1433         return;
1434     if (divisor == 2 || divisor == -2) {
1435         failureCases.append(m_assembler.branchTest32(Assembler::NonZero, inputDividend, Assembler::TrustedImm32(1)));
1436         return;
1437     }
1438
1439     failureCases.append(modulo(Assembler::NonZero, inputDividend, divisor));
1440 }
1441
1442 static void setNodeFlag(Assembler& assembler, Assembler::RegisterID elementAddress, int32_t flag)
1443 {
1444     assembler.or32(Assembler::TrustedImm32(flag), Assembler::Address(elementAddress, Node::nodeFlagsMemoryOffset()));
1445 }
1446
1447 void SelectorCodeGenerator::markParentElementIfResolvingStyle(int32_t nodeFlag)
1448 {
1449     if (m_selectorContext == SelectorContext::QuerySelector)
1450         return;
1451
1452     Assembler::JumpList skipMarking;
1453     {
1454         LocalRegister checkingContext(m_registerAllocator);
1455         skipMarking.append(jumpIfNotResolvingStyle(checkingContext));
1456     }
1457
1458     LocalRegister parentElement(m_registerAllocator);
1459     generateWalkToParentElement(skipMarking, parentElement);
1460
1461     setNodeFlag(m_assembler, parentElement, nodeFlag);
1462
1463     skipMarking.link(&m_assembler);
1464 }
1465
1466 void SelectorCodeGenerator::markParentElementIfResolvingStyle(JSC::FunctionPtr markingFunction)
1467 {
1468     if (m_selectorContext == SelectorContext::QuerySelector)
1469         return;
1470
1471     //     if (checkingContext.resolvingMode == ResolvingStyle) {
1472     //         Element* parent = element->parentNode();
1473     //         markingFunction(parent);
1474     //     }
1475
1476     Assembler::JumpList skipMarking;
1477     {
1478         LocalRegister checkingContext(m_registerAllocator);
1479         skipMarking.append(jumpIfNotResolvingStyle(checkingContext));
1480     }
1481
1482     // Get the parent element in a temporary register.
1483     Assembler::RegisterID parentElement = m_registerAllocator.allocateRegister();
1484     generateWalkToParentElement(skipMarking, parentElement);
1485
1486     // Return the register parentElement just before the function call since we don't need it to be preserved
1487     // on the stack.
1488     m_registerAllocator.deallocateRegister(parentElement);
1489
1490     // Invoke the marking function on the parent element.
1491     FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
1492     functionCall.setFunctionAddress(markingFunction);
1493     functionCall.setOneArgument(parentElement);
1494     functionCall.call();
1495
1496     skipMarking.link(&m_assembler);
1497 }
1498
1499
1500 void SelectorCodeGenerator::linkFailures(Assembler::JumpList& globalFailureCases, BacktrackingAction backtrackingAction, Assembler::JumpList& localFailureCases)
1501 {
1502     switch (backtrackingAction) {
1503     case BacktrackingAction::NoBacktracking:
1504         globalFailureCases.append(localFailureCases);
1505         break;
1506     case BacktrackingAction::JumpToDescendantEntryPoint:
1507         localFailureCases.linkTo(m_descendantEntryPoint, &m_assembler);
1508         break;
1509     case BacktrackingAction::JumpToDescendantTreeWalkerEntryPoint:
1510         localFailureCases.linkTo(m_descendantTreeWalkerBacktrackingPoint, &m_assembler);
1511         break;
1512     case BacktrackingAction::JumpToDescendantTail:
1513         m_descendantBacktrackingFailureCases.append(localFailureCases);
1514         break;
1515     case BacktrackingAction::JumpToIndirectAdjacentEntryPoint:
1516         localFailureCases.linkTo(m_indirectAdjacentEntryPoint, &m_assembler);
1517         break;
1518     case BacktrackingAction::JumpToIndirectAdjacentTreeWalkerEntryPoint:
1519         localFailureCases.linkTo(m_indirectAdjacentTreeWalkerBacktrackingPoint, &m_assembler);
1520         break;
1521     case BacktrackingAction::JumpToDirectAdjacentTail:
1522         m_adjacentBacktrackingFailureCases.append(localFailureCases);
1523         break;
1524     }
1525 }
1526
1527 void SelectorCodeGenerator::generateAdjacentBacktrackingTail()
1528 {
1529     // Recovering tail.
1530     m_adjacentBacktrackingFailureCases.link(&m_assembler);
1531     m_adjacentBacktrackingFailureCases.clear();
1532     unsigned offsetToAdjacentBacktrackingStart = m_stackAllocator.offsetToStackReference(m_adjacentBacktrackingStart);
1533     m_assembler.loadPtr(Assembler::Address(Assembler::stackPointerRegister, offsetToAdjacentBacktrackingStart), elementAddressRegister);
1534     m_assembler.jump(m_indirectAdjacentEntryPoint);
1535 }
1536
1537 void SelectorCodeGenerator::generateDescendantBacktrackingTail()
1538 {
1539     m_descendantBacktrackingFailureCases.link(&m_assembler);
1540     m_descendantBacktrackingFailureCases.clear();
1541     m_assembler.move(m_descendantBacktrackingStart, elementAddressRegister);
1542     m_registerAllocator.deallocateRegister(m_descendantBacktrackingStart);
1543     m_assembler.jump(m_descendantEntryPoint);
1544 }
1545
1546 void SelectorCodeGenerator::generateBacktrackingTailsIfNeeded(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
1547 {
1548     if (fragment.backtrackingFlags & BacktrackingFlag::DirectAdjacentTail && fragment.backtrackingFlags & BacktrackingFlag::DescendantTail) {
1549         Assembler::Jump normalCase = m_assembler.jump();
1550         generateAdjacentBacktrackingTail();
1551         generateDescendantBacktrackingTail();
1552         normalCase.link(&m_assembler);
1553     } else if (fragment.backtrackingFlags & BacktrackingFlag::DirectAdjacentTail) {
1554         Assembler::Jump normalCase = m_assembler.jump();
1555         generateAdjacentBacktrackingTail();
1556         failureCases.append(m_assembler.jump());
1557         normalCase.link(&m_assembler);
1558     } else if (fragment.backtrackingFlags & BacktrackingFlag::DescendantTail) {
1559         Assembler::Jump normalCase = m_assembler.jump();
1560         generateDescendantBacktrackingTail();
1561         normalCase.link(&m_assembler);
1562     }
1563 }
1564
1565 void SelectorCodeGenerator::generateElementMatching(Assembler::JumpList& matchingTagNameFailureCases, Assembler::JumpList& matchingPostTagNameFailureCases, const SelectorFragment& fragment)
1566 {
1567     if (fragment.tagName)
1568         generateElementHasTagName(matchingTagNameFailureCases, *(fragment.tagName));
1569
1570     if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassLink))
1571         generateElementIsLink(matchingPostTagNameFailureCases);
1572
1573     if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassRoot))
1574         generateElementIsRoot(matchingPostTagNameFailureCases);
1575
1576     if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassTarget))
1577         generateElementIsTarget(matchingPostTagNameFailureCases);
1578
1579     for (unsigned i = 0; i < fragment.unoptimizedPseudoClasses.size(); ++i)
1580         generateElementFunctionCallTest(matchingPostTagNameFailureCases, fragment.unoptimizedPseudoClasses[i]);
1581
1582     generateElementDataMatching(matchingPostTagNameFailureCases, fragment);
1583
1584     if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassActive))
1585         generateElementIsActive(matchingPostTagNameFailureCases, fragment);
1586     if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassHover))
1587         generateElementIsHovered(matchingPostTagNameFailureCases, fragment);
1588     if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassOnlyChild))
1589         generateElementIsOnlyChild(matchingPostTagNameFailureCases, fragment);
1590     if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassFirstChild))
1591         generateElementIsFirstChild(matchingPostTagNameFailureCases, fragment);
1592     if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassLastChild))
1593         generateElementIsLastChild(matchingPostTagNameFailureCases, fragment);
1594     if (!fragment.nthChildfilters.isEmpty())
1595         generateElementIsNthChild(matchingPostTagNameFailureCases, fragment);
1596 }
1597
1598 void SelectorCodeGenerator::generateElementDataMatching(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
1599 {
1600     if (!fragment.id && fragment.classNames.isEmpty() && fragment.attributes.isEmpty())
1601         return;
1602
1603     //  Generate:
1604     //     elementDataAddress = element->elementData();
1605     //     if (!elementDataAddress)
1606     //         failure!
1607     LocalRegister elementDataAddress(m_registerAllocator);
1608     m_assembler.loadPtr(Assembler::Address(elementAddressRegister, Element::elementDataMemoryOffset()), elementDataAddress);
1609     failureCases.append(m_assembler.branchTestPtr(Assembler::Zero, elementDataAddress));
1610
1611     if (fragment.id)
1612         generateElementHasId(failureCases, elementDataAddress, *fragment.id);
1613     if (!fragment.classNames.isEmpty())
1614         generateElementHasClasses(failureCases, elementDataAddress, fragment.classNames);
1615     if (!fragment.attributes.isEmpty())
1616     generateElementAttributesMatching(failureCases, elementDataAddress, fragment);
1617 }
1618
1619 static inline Assembler::Jump testIsHTMLFlagOnNode(Assembler::ResultCondition condition, Assembler& assembler, Assembler::RegisterID nodeAddress)
1620 {
1621     return assembler.branchTest32(condition, Assembler::Address(nodeAddress, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagIsHTML()));
1622 }
1623
1624 static inline bool canMatchStyleAttribute(const SelectorFragment& fragment)
1625 {
1626     for (unsigned i = 0; i < fragment.attributes.size(); ++i) {
1627         const CSSSelector& attributeSelector = fragment.attributes[i].selector();
1628         const QualifiedName& attributeName = attributeSelector.attribute();
1629         if (Attribute::nameMatchesFilter(HTMLNames::styleAttr, attributeName.prefix(), attributeName.localName(), attributeName.namespaceURI()))
1630             return true;
1631
1632         const AtomicString& canonicalLocalName = attributeSelector.attributeCanonicalLocalName();
1633         if (attributeName.localName() != canonicalLocalName
1634             && Attribute::nameMatchesFilter(HTMLNames::styleAttr, attributeName.prefix(), attributeSelector.attributeCanonicalLocalName(), attributeName.namespaceURI())) {
1635             return true;
1636         }
1637     }
1638     return false;
1639 }
1640
1641 void SelectorCodeGenerator::generateSynchronizeStyleAttribute(Assembler::RegisterID elementDataArraySizeAndFlags)
1642 {
1643     // The style attribute is updated lazily based on the flag styleAttributeIsDirty.
1644     Assembler::Jump styleAttributeNotDirty = m_assembler.branchTest32(Assembler::Zero, elementDataArraySizeAndFlags, Assembler::TrustedImm32(ElementData::styleAttributeIsDirtyFlag()));
1645
1646     FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
1647     functionCall.setFunctionAddress(StyledElement::synchronizeStyleAttributeInternal);
1648     Assembler::RegisterID elementAddress = elementAddressRegister;
1649     functionCall.setOneArgument(elementAddress);
1650     functionCall.call();
1651
1652     styleAttributeNotDirty.link(&m_assembler);
1653 }
1654
1655 static inline bool canMatchAnimatableSVGAttribute(const SelectorFragment& fragment)
1656 {
1657     for (unsigned i = 0; i < fragment.attributes.size(); ++i) {
1658         const CSSSelector& attributeSelector = fragment.attributes[i].selector();
1659         const QualifiedName& selectorAttributeName = attributeSelector.attribute();
1660
1661         const QualifiedName& candidateForLocalName = SVGElement::animatableAttributeForName(selectorAttributeName.localName());
1662         if (Attribute::nameMatchesFilter(candidateForLocalName, selectorAttributeName.prefix(), selectorAttributeName.localName(), selectorAttributeName.namespaceURI()))
1663             return true;
1664
1665         const AtomicString& canonicalLocalName = attributeSelector.attributeCanonicalLocalName();
1666         if (selectorAttributeName.localName() != canonicalLocalName) {
1667             const QualifiedName& candidateForCanonicalLocalName = SVGElement::animatableAttributeForName(selectorAttributeName.localName());
1668             if (Attribute::nameMatchesFilter(candidateForCanonicalLocalName, selectorAttributeName.prefix(), selectorAttributeName.localName(), selectorAttributeName.namespaceURI()))
1669                 return true;
1670         }
1671     }
1672     return false;
1673 }
1674
1675 void SelectorCodeGenerator::generateSynchronizeAllAnimatedSVGAttribute(Assembler::RegisterID elementDataArraySizeAndFlags)
1676 {
1677     // SVG attributes can be updated lazily depending on the flag AnimatedSVGAttributesAreDirty. We need to check
1678     // that first.
1679     Assembler::Jump animatedSVGAttributesNotDirty = m_assembler.branchTest32(Assembler::Zero, elementDataArraySizeAndFlags, Assembler::TrustedImm32(ElementData::animatedSVGAttributesAreDirtyFlag()));
1680
1681     FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
1682     functionCall.setFunctionAddress(SVGElement::synchronizeAllAnimatedSVGAttribute);
1683     Assembler::RegisterID elementAddress = elementAddressRegister;
1684     functionCall.setOneArgument(elementAddress);
1685     functionCall.call();
1686
1687     animatedSVGAttributesNotDirty.link(&m_assembler);
1688 }
1689
1690 void SelectorCodeGenerator::generateElementAttributesMatching(Assembler::JumpList& failureCases, const LocalRegister& elementDataAddress, const SelectorFragment& fragment)
1691 {
1692     LocalRegister scratchRegister(m_registerAllocator);
1693     Assembler::RegisterID elementDataArraySizeAndFlags = scratchRegister;
1694     Assembler::RegisterID attributeArrayLength = scratchRegister;
1695
1696     m_assembler.load32(Assembler::Address(elementDataAddress, ElementData::arraySizeAndFlagsMemoryOffset()), elementDataArraySizeAndFlags);
1697
1698     if (canMatchStyleAttribute(fragment))
1699         generateSynchronizeStyleAttribute(elementDataArraySizeAndFlags);
1700
1701     if (canMatchAnimatableSVGAttribute(fragment))
1702         generateSynchronizeAllAnimatedSVGAttribute(elementDataArraySizeAndFlags);
1703
1704     // Attributes can be stored either in a separate vector for UniqueElementData, or after the elementData itself
1705     // for ShareableElementData.
1706     LocalRegister attributeArrayPointer(m_registerAllocator);
1707     Assembler::Jump isShareableElementData  = m_assembler.branchTest32(Assembler::Zero, elementDataArraySizeAndFlags, Assembler::TrustedImm32(ElementData::isUniqueFlag()));
1708     {
1709         ptrdiff_t attributeVectorOffset = UniqueElementData::attributeVectorMemoryOffset();
1710         m_assembler.loadPtr(Assembler::Address(elementDataAddress, attributeVectorOffset + UniqueElementData::AttributeVector::dataMemoryOffset()), attributeArrayPointer);
1711         m_assembler.load32(Assembler::Address(elementDataAddress, attributeVectorOffset + UniqueElementData::AttributeVector::sizeMemoryOffset()), attributeArrayLength);
1712     }
1713     Assembler::Jump skipShareable = m_assembler.jump();
1714
1715     {
1716         isShareableElementData.link(&m_assembler);
1717         m_assembler.urshift32(elementDataArraySizeAndFlags, Assembler::TrustedImm32(ElementData::arraySizeOffset()), attributeArrayLength);
1718         m_assembler.add64(Assembler::TrustedImm32(ShareableElementData::attributeArrayMemoryOffset()), elementDataAddress, attributeArrayPointer);
1719     }
1720
1721     skipShareable.link(&m_assembler);
1722
1723     // If there are no attributes, fail immediately.
1724     failureCases.append(m_assembler.branchTest32(Assembler::Zero, attributeArrayLength));
1725
1726     unsigned attributeCount = fragment.attributes.size();
1727     for (unsigned i = 0; i < attributeCount; ++i) {
1728         Assembler::RegisterID decIndexRegister;
1729         Assembler::RegisterID currentAttributeAddress;
1730
1731         bool isLastAttribute = i == (attributeCount - 1);
1732         if (!isLastAttribute) {
1733             // We need to make a copy to let the next iterations use the values.
1734             currentAttributeAddress = m_registerAllocator.allocateRegister();
1735             decIndexRegister = m_registerAllocator.allocateRegister();
1736             m_assembler.move(attributeArrayPointer, currentAttributeAddress);
1737             m_assembler.move(attributeArrayLength, decIndexRegister);
1738         } else {
1739             currentAttributeAddress = attributeArrayPointer;
1740             decIndexRegister = attributeArrayLength;
1741         }
1742
1743         generateElementAttributeMatching(failureCases, currentAttributeAddress, decIndexRegister, fragment.attributes[i]);
1744
1745         if (!isLastAttribute) {
1746             m_registerAllocator.deallocateRegister(decIndexRegister);
1747             m_registerAllocator.deallocateRegister(currentAttributeAddress);
1748         }
1749     }
1750 }
1751
1752 void SelectorCodeGenerator::generateElementAttributeMatching(Assembler::JumpList& failureCases, Assembler::RegisterID currentAttributeAddress, Assembler::RegisterID decIndexRegister, const AttributeMatchingInfo& attributeInfo)
1753 {
1754     // Get the localName used for comparison. HTML elements use a lowercase local name known in selectors as canonicalLocalName.
1755     LocalRegister localNameToMatch(m_registerAllocator);
1756
1757     // In general, canonicalLocalName and localName are the same. When they differ, we have to check if the node is HTML to know
1758     // which one to use.
1759     const CSSSelector& attributeSelector = attributeInfo.selector();
1760     const AtomicStringImpl* canonicalLocalName = attributeSelector.attributeCanonicalLocalName().impl();
1761     const AtomicStringImpl* localName = attributeSelector.attribute().localName().impl();
1762     if (canonicalLocalName == localName)
1763         m_assembler.move(Assembler::TrustedImmPtr(canonicalLocalName), localNameToMatch);
1764     else {
1765         m_assembler.move(Assembler::TrustedImmPtr(canonicalLocalName), localNameToMatch);
1766         Assembler::Jump elementIsHTML = testIsHTMLFlagOnNode(Assembler::NonZero, m_assembler, elementAddressRegister);
1767         m_assembler.move(Assembler::TrustedImmPtr(localName), localNameToMatch);
1768         elementIsHTML.link(&m_assembler);
1769     }
1770
1771     Assembler::JumpList successCases;
1772     Assembler::Label loopStart(m_assembler.label());
1773
1774     {
1775         LocalRegister qualifiedNameImpl(m_registerAllocator);
1776         m_assembler.loadPtr(Assembler::Address(currentAttributeAddress, Attribute::nameMemoryOffset()), qualifiedNameImpl);
1777
1778         bool shouldCheckNamespace = attributeSelector.attribute().prefix() != starAtom;
1779         if (shouldCheckNamespace) {
1780             Assembler::Jump nameDoesNotMatch = m_assembler.branchPtr(Assembler::NotEqual, Assembler::Address(qualifiedNameImpl, QualifiedName::QualifiedNameImpl::localNameMemoryOffset()), localNameToMatch);
1781
1782             const AtomicStringImpl* namespaceURI = attributeSelector.attribute().namespaceURI().impl();
1783             if (namespaceURI) {
1784                 LocalRegister namespaceToMatch(m_registerAllocator);
1785                 m_assembler.move(Assembler::TrustedImmPtr(namespaceURI), namespaceToMatch);
1786                 successCases.append(m_assembler.branchPtr(Assembler::Equal, Assembler::Address(qualifiedNameImpl, QualifiedName::QualifiedNameImpl::namespaceMemoryOffset()), namespaceToMatch));
1787             } else
1788                 successCases.append(m_assembler.branchTestPtr(Assembler::Zero, Assembler::Address(qualifiedNameImpl, QualifiedName::QualifiedNameImpl::namespaceMemoryOffset())));
1789             nameDoesNotMatch.link(&m_assembler);
1790         } else
1791             successCases.append(m_assembler.branchPtr(Assembler::Equal, Assembler::Address(qualifiedNameImpl, QualifiedName::QualifiedNameImpl::localNameMemoryOffset()), localNameToMatch));
1792     }
1793
1794     Assembler::Label loopReEntry(m_assembler.label());
1795
1796     // If we reached the last element -> failure.
1797     failureCases.append(m_assembler.branchSub32(Assembler::Zero, Assembler::TrustedImm32(1), decIndexRegister));
1798
1799     // Otherwise just loop over.
1800     m_assembler.addPtr(Assembler::TrustedImm32(sizeof(Attribute)), currentAttributeAddress);
1801     m_assembler.jump().linkTo(loopStart, &m_assembler);
1802
1803     successCases.link(&m_assembler);
1804
1805     if (attributeSelector.m_match != CSSSelector::Set) {
1806         // We make the assumption that name matching fails in most cases and we keep value matching outside
1807         // of the loop. We re-enter the loop if needed.
1808         // FIXME: exact case sensitive value matching is so simple that it should be done in the loop.
1809         Assembler::JumpList localFailureCases;
1810         generateElementAttributeValueMatching(localFailureCases, currentAttributeAddress, attributeInfo);
1811         localFailureCases.linkTo(loopReEntry, &m_assembler);
1812     }
1813 }
1814
1815 enum CaseSensitivity {
1816     CaseSensitive,
1817     CaseInsensitive
1818 };
1819
1820 template<CaseSensitivity caseSensitivity>
1821 static bool attributeValueBeginsWith(const Attribute* attribute, AtomicStringImpl* expectedString)
1822 {
1823     AtomicStringImpl& valueImpl = *attribute->value().impl();
1824     if (caseSensitivity == CaseSensitive)
1825         return valueImpl.startsWith(expectedString);
1826     return valueImpl.startsWith(expectedString, false);
1827 }
1828
1829 template<CaseSensitivity caseSensitivity>
1830 static bool attributeValueContains(const Attribute* attribute, AtomicStringImpl* expectedString)
1831 {
1832     AtomicStringImpl& valueImpl = *attribute->value().impl();
1833     if (caseSensitivity == CaseSensitive)
1834         return valueImpl.find(expectedString) != notFound;
1835     return valueImpl.findIgnoringCase(expectedString) != notFound;
1836 }
1837
1838 template<CaseSensitivity caseSensitivity>
1839 static bool attributeValueEndsWith(const Attribute* attribute, AtomicStringImpl* expectedString)
1840 {
1841     AtomicStringImpl& valueImpl = *attribute->value().impl();
1842     if (caseSensitivity == CaseSensitive)
1843         return valueImpl.endsWith(expectedString);
1844     return valueImpl.endsWith(expectedString, false);
1845 }
1846
1847 template<CaseSensitivity caseSensitivity>
1848 static bool attributeValueMatchHyphenRule(const Attribute* attribute, AtomicStringImpl* expectedString)
1849 {
1850     AtomicStringImpl& valueImpl = *attribute->value().impl();
1851     if (valueImpl.length() < expectedString->length())
1852         return false;
1853
1854     bool valueStartsWithExpectedString;
1855     if (caseSensitivity == CaseSensitive)
1856         valueStartsWithExpectedString = valueImpl.startsWith(expectedString);
1857     else
1858         valueStartsWithExpectedString = valueImpl.startsWith(expectedString, false);
1859
1860     if (!valueStartsWithExpectedString)
1861         return false;
1862
1863     return valueImpl.length() == expectedString->length() || valueImpl[expectedString->length()] == '-';
1864 }
1865
1866 template<CaseSensitivity caseSensitivity>
1867 static bool attributeValueSpaceSeparetedListContains(const Attribute* attribute, AtomicStringImpl* expectedString)
1868 {
1869     AtomicStringImpl& value = *attribute->value().impl();
1870
1871     unsigned startSearchAt = 0;
1872     while (true) {
1873         size_t foundPos;
1874         if (caseSensitivity == CaseSensitive)
1875             foundPos = value.find(expectedString, startSearchAt);
1876         else
1877             foundPos = value.findIgnoringCase(expectedString, startSearchAt);
1878         if (foundPos == notFound)
1879             return false;
1880         if (!foundPos || value[foundPos - 1] == ' ') {
1881             unsigned endStr = foundPos + expectedString->length();
1882             if (endStr == value.length() || value[endStr] == ' ')
1883                 return true;
1884         }
1885         startSearchAt = foundPos + 1;
1886     }
1887     return false;
1888 }
1889
1890 void SelectorCodeGenerator::generateElementAttributeValueMatching(Assembler::JumpList& failureCases, Assembler::RegisterID currentAttributeAddress, const AttributeMatchingInfo& attributeInfo)
1891 {
1892     const CSSSelector& attributeSelector = attributeInfo.selector();
1893     const AtomicString& expectedValue = attributeSelector.value();
1894     ASSERT(!expectedValue.isNull());
1895     bool defaultToCaseSensitiveValueMatch = attributeInfo.canDefaultToCaseSensitiveValueMatch();
1896
1897     switch (attributeSelector.m_match) {
1898     case CSSSelector::Begin:
1899         generateElementAttributeFunctionCallValueMatching(failureCases, currentAttributeAddress, expectedValue, defaultToCaseSensitiveValueMatch, attributeValueBeginsWith<CaseSensitive>, attributeValueBeginsWith<CaseInsensitive>);
1900         break;
1901     case CSSSelector::Contain:
1902         generateElementAttributeFunctionCallValueMatching(failureCases, currentAttributeAddress, expectedValue, defaultToCaseSensitiveValueMatch, attributeValueContains<CaseSensitive>, attributeValueContains<CaseInsensitive>);
1903         break;
1904     case CSSSelector::End:
1905         generateElementAttributeFunctionCallValueMatching(failureCases, currentAttributeAddress, expectedValue, defaultToCaseSensitiveValueMatch, attributeValueEndsWith<CaseSensitive>, attributeValueEndsWith<CaseInsensitive>);
1906         break;
1907     case CSSSelector::Exact:
1908         generateElementAttributeValueExactMatching(failureCases, currentAttributeAddress, expectedValue, defaultToCaseSensitiveValueMatch);
1909         break;
1910     case CSSSelector::Hyphen:
1911         generateElementAttributeFunctionCallValueMatching(failureCases, currentAttributeAddress, expectedValue, defaultToCaseSensitiveValueMatch, attributeValueMatchHyphenRule<CaseSensitive>, attributeValueMatchHyphenRule<CaseInsensitive>);
1912         break;
1913     case CSSSelector::List:
1914         generateElementAttributeFunctionCallValueMatching(failureCases, currentAttributeAddress, expectedValue, defaultToCaseSensitiveValueMatch, attributeValueSpaceSeparetedListContains<CaseSensitive>, attributeValueSpaceSeparetedListContains<CaseInsensitive>);
1915         break;
1916     default:
1917         ASSERT_NOT_REACHED();
1918     }
1919 }
1920
1921 static inline Assembler::Jump testIsHTMLClassOnDocument(Assembler::ResultCondition condition, Assembler& assembler, Assembler::RegisterID documentAddress)
1922 {
1923     return assembler.branchTest32(condition, Assembler::Address(documentAddress, Document::documentClassesMemoryOffset()), Assembler::TrustedImm32(Document::isHTMLDocumentClassFlag()));
1924 }
1925
1926 void SelectorCodeGenerator::generateElementAttributeValueExactMatching(Assembler::JumpList& failureCases, Assembler::RegisterID currentAttributeAddress, const AtomicString& expectedValue, bool canDefaultToCaseSensitiveValueMatch)
1927 {
1928     LocalRegister expectedValueRegister(m_registerAllocator);
1929     m_assembler.move(Assembler::TrustedImmPtr(expectedValue.impl()), expectedValueRegister);
1930
1931     if (canDefaultToCaseSensitiveValueMatch)
1932         failureCases.append(m_assembler.branchPtr(Assembler::NotEqual, Assembler::Address(currentAttributeAddress, Attribute::valueMemoryOffset()), expectedValueRegister));
1933     else {
1934         Assembler::Jump skipCaseInsensitiveComparison = m_assembler.branchPtr(Assembler::Equal, Assembler::Address(currentAttributeAddress, Attribute::valueMemoryOffset()), expectedValueRegister);
1935
1936         // If the element is an HTML element, in a HTML dcoument (not including XHTML), value matching is case insensitive.
1937         // Taking the contrapositive, if we find the element is not HTML or is not in a HTML document, the condition above
1938         // sould be sufficient and we can fail early.
1939         failureCases.append(testIsHTMLFlagOnNode(Assembler::Zero, m_assembler, elementAddressRegister));
1940
1941         {
1942             LocalRegister document(m_registerAllocator);
1943             getDocument(m_assembler, elementAddressRegister, document);
1944             failureCases.append(testIsHTMLClassOnDocument(Assembler::Zero, m_assembler, document));
1945         }
1946
1947         LocalRegister valueStringImpl(m_registerAllocator);
1948         m_assembler.loadPtr(Assembler::Address(currentAttributeAddress, Attribute::valueMemoryOffset()), valueStringImpl);
1949
1950         FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
1951         functionCall.setFunctionAddress(WTF::equalIgnoringCaseNonNull);
1952         functionCall.setTwoArguments(expectedValueRegister, valueStringImpl);
1953         failureCases.append(functionCall.callAndBranchOnCondition(Assembler::Zero));
1954
1955         skipCaseInsensitiveComparison.link(&m_assembler);
1956     }
1957 }
1958
1959 void SelectorCodeGenerator::generateElementAttributeFunctionCallValueMatching(Assembler::JumpList& failureCases, Assembler::RegisterID currentAttributeAddress, const AtomicString& expectedValue, bool canDefaultToCaseSensitiveValueMatch, JSC::FunctionPtr caseSensitiveTest, JSC::FunctionPtr caseInsensitiveTest)
1960 {
1961     LocalRegister expectedValueRegister(m_registerAllocator);
1962     m_assembler.move(Assembler::TrustedImmPtr(expectedValue.impl()), expectedValueRegister);
1963
1964     if (canDefaultToCaseSensitiveValueMatch) {
1965         FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
1966         functionCall.setFunctionAddress(caseSensitiveTest);
1967         functionCall.setTwoArguments(currentAttributeAddress, expectedValueRegister);
1968         failureCases.append(functionCall.callAndBranchOnCondition(Assembler::Zero));
1969     } else {
1970         Assembler::JumpList shouldUseCaseSensitiveComparison;
1971         shouldUseCaseSensitiveComparison.append(testIsHTMLFlagOnNode(Assembler::Zero, m_assembler, elementAddressRegister));
1972         {
1973             LocalRegister scratchRegister(m_registerAllocator);
1974             // scratchRegister = pointer to treeScope.
1975             m_assembler.loadPtr(Assembler::Address(elementAddressRegister, Node::treeScopeMemoryOffset()), scratchRegister);
1976             // scratchRegister = pointer to document.
1977             m_assembler.loadPtr(Assembler::Address(scratchRegister, TreeScope::documentScopeMemoryOffset()), scratchRegister);
1978             shouldUseCaseSensitiveComparison.append(testIsHTMLClassOnDocument(Assembler::Zero, m_assembler, scratchRegister));
1979         }
1980
1981         {
1982             FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
1983             functionCall.setFunctionAddress(caseInsensitiveTest);
1984             functionCall.setTwoArguments(currentAttributeAddress, expectedValueRegister);
1985             failureCases.append(functionCall.callAndBranchOnCondition(Assembler::Zero));
1986         }
1987
1988         Assembler::Jump skipCaseSensitiveCase = m_assembler.jump();
1989
1990         {
1991             shouldUseCaseSensitiveComparison.link(&m_assembler);
1992             FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
1993             functionCall.setFunctionAddress(caseSensitiveTest);
1994             functionCall.setTwoArguments(currentAttributeAddress, expectedValueRegister);
1995             failureCases.append(functionCall.callAndBranchOnCondition(Assembler::Zero));
1996         }
1997
1998         skipCaseSensitiveCase.link(&m_assembler);
1999     }
2000 }
2001
2002 void SelectorCodeGenerator::generateElementFunctionCallTest(Assembler::JumpList& failureCases, JSC::FunctionPtr testFunction)
2003 {
2004     Assembler::RegisterID elementAddress = elementAddressRegister;
2005     FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2006     functionCall.setFunctionAddress(testFunction);
2007     functionCall.setOneArgument(elementAddress);
2008     failureCases.append(functionCall.callAndBranchOnCondition(Assembler::Zero));
2009 }
2010
2011 static void setFirstChildState(Element* element)
2012 {
2013     if (RenderStyle* style = element->renderStyle())
2014         style->setFirstChildState();
2015 }
2016
2017 static bool elementIsActive(Element* element)
2018 {
2019     return element->active() || InspectorInstrumentation::forcePseudoState(element, CSSSelector::PseudoClassActive);
2020 }
2021
2022 static bool elementIsActiveForStyleResolution(Element* element, const CheckingContext* checkingContext)
2023 {
2024     if (checkingContext->resolvingMode == SelectorChecker::ResolvingStyle)
2025         element->setChildrenAffectedByActive();
2026     return element->active() || InspectorInstrumentation::forcePseudoState(element, CSSSelector::PseudoClassActive);
2027 }
2028
2029 void SelectorCodeGenerator::generateElementIsActive(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
2030 {
2031     generateSpecialFailureInQuirksModeForActiveAndHoverIfNeeded(failureCases, fragment);
2032     if (m_selectorContext == SelectorContext::QuerySelector) {
2033         FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2034         functionCall.setFunctionAddress(elementIsActive);
2035         functionCall.setOneArgument(elementAddressRegister);
2036         failureCases.append(functionCall.callAndBranchOnCondition(Assembler::Zero));
2037     } else {
2038         if (fragment.relationToRightFragment == FragmentRelation::Rightmost) {
2039             LocalRegister checkingContext(m_registerAllocator);
2040             Assembler::Jump notResolvingStyle = jumpIfNotResolvingStyle(checkingContext);
2041             addFlagsToElementStyleFromContext(checkingContext, RenderStyle::NonInheritedFlags::flagIsaffectedByActive());
2042             notResolvingStyle.link(&m_assembler);
2043
2044             FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2045             functionCall.setFunctionAddress(elementIsActive);
2046             functionCall.setOneArgument(elementAddressRegister);
2047             failureCases.append(functionCall.callAndBranchOnCondition(Assembler::Zero));
2048         } else {
2049             unsigned offsetToCheckingContext = m_stackAllocator.offsetToStackReference(m_checkingContextStackReference);
2050             Assembler::RegisterID checkingContext = m_registerAllocator.allocateRegister();
2051             m_assembler.loadPtr(Assembler::Address(Assembler::stackPointerRegister, offsetToCheckingContext), checkingContext);
2052             m_registerAllocator.deallocateRegister(checkingContext);
2053
2054             FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2055             functionCall.setFunctionAddress(elementIsActiveForStyleResolution);
2056             functionCall.setTwoArguments(elementAddressRegister, checkingContext);
2057             failureCases.append(functionCall.callAndBranchOnCondition(Assembler::Zero));
2058         }
2059     }
2060 }
2061
2062 void SelectorCodeGenerator::generateElementIsFirstChild(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
2063 {
2064     if (m_selectorContext == SelectorContext::QuerySelector) {
2065         Assembler::JumpList successCase = jumpIfNoPreviousAdjacentElement();
2066         failureCases.append(m_assembler.jump());
2067         successCase.link(&m_assembler);
2068         LocalRegister parent(m_registerAllocator);
2069         generateWalkToParentElement(failureCases, parent);
2070         return;
2071     }
2072
2073     Assembler::RegisterID parentElement = m_registerAllocator.allocateRegister();
2074     generateWalkToParentElement(failureCases, parentElement);
2075
2076     // Zero in isFirstChildRegister is the success case. The register is set to non-zero if a sibling if found.
2077     LocalRegister isFirstChildRegister(m_registerAllocator);
2078     m_assembler.move(Assembler::TrustedImm32(0), isFirstChildRegister);
2079
2080     {
2081         Assembler::JumpList successCase = jumpIfNoPreviousAdjacentElement();
2082
2083         // If there was a sibling element, the element was not the first child -> failure case.
2084         m_assembler.move(Assembler::TrustedImm32(1), isFirstChildRegister);
2085
2086         successCase.link(&m_assembler);
2087     }
2088
2089     LocalRegister checkingContext(m_registerAllocator);
2090     Assembler::Jump notResolvingStyle = jumpIfNotResolvingStyle(checkingContext);
2091
2092     setNodeFlag(m_assembler, parentElement, Node::flagChildrenAffectedByFirstChildRulesFlag());
2093     m_registerAllocator.deallocateRegister(parentElement);
2094
2095     // The parent marking is unconditional. If the matching is not a success, we can now fail.
2096     // Otherwise we need to apply setFirstChildState() on the RenderStyle.
2097     failureCases.append(m_assembler.branchTest32(Assembler::NonZero, isFirstChildRegister));
2098
2099     if (fragment.relationToRightFragment == FragmentRelation::Rightmost)
2100         addFlagsToElementStyleFromContext(checkingContext, RenderStyle::NonInheritedFlags::setFirstChildStateFlags());
2101     else {
2102         FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2103         functionCall.setFunctionAddress(setFirstChildState);
2104         Assembler::RegisterID elementAddress = elementAddressRegister;
2105         functionCall.setOneArgument(elementAddress);
2106         functionCall.call();
2107     }
2108
2109     notResolvingStyle.link(&m_assembler);
2110     failureCases.append(m_assembler.branchTest32(Assembler::NonZero, isFirstChildRegister));
2111 }
2112
2113 static bool elementIsHovered(Element* element)
2114 {
2115     return element->hovered() || InspectorInstrumentation::forcePseudoState(element, CSSSelector::PseudoClassHover);
2116 }
2117
2118 static bool elementIsHoveredForStyleResolution(Element* element, const CheckingContext* checkingContext)
2119 {
2120     if (checkingContext->resolvingMode == SelectorChecker::ResolvingStyle)
2121         element->setChildrenAffectedByHover();
2122     return element->hovered() || InspectorInstrumentation::forcePseudoState(element, CSSSelector::PseudoClassHover);
2123 }
2124
2125 void SelectorCodeGenerator::generateElementIsHovered(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
2126 {
2127     generateSpecialFailureInQuirksModeForActiveAndHoverIfNeeded(failureCases, fragment);
2128     if (m_selectorContext == SelectorContext::QuerySelector) {
2129         FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2130         functionCall.setFunctionAddress(elementIsHovered);
2131         functionCall.setOneArgument(elementAddressRegister);
2132         failureCases.append(functionCall.callAndBranchOnCondition(Assembler::Zero));
2133     } else {
2134         if (fragment.relationToRightFragment == FragmentRelation::Rightmost) {
2135             LocalRegister checkingContext(m_registerAllocator);
2136             Assembler::Jump notResolvingStyle = jumpIfNotResolvingStyle(checkingContext);
2137             addFlagsToElementStyleFromContext(checkingContext, RenderStyle::NonInheritedFlags::flagIsaffectedByHover());
2138             notResolvingStyle.link(&m_assembler);
2139
2140             FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2141             functionCall.setFunctionAddress(elementIsHovered);
2142             functionCall.setOneArgument(elementAddressRegister);
2143             failureCases.append(functionCall.callAndBranchOnCondition(Assembler::Zero));
2144         } else {
2145             unsigned offsetToCheckingContext = m_stackAllocator.offsetToStackReference(m_checkingContextStackReference);
2146             Assembler::RegisterID checkingContext = m_registerAllocator.allocateRegister();
2147             m_assembler.loadPtr(Assembler::Address(Assembler::stackPointerRegister, offsetToCheckingContext), checkingContext);
2148             m_registerAllocator.deallocateRegister(checkingContext);
2149
2150             FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2151             functionCall.setFunctionAddress(elementIsHoveredForStyleResolution);
2152             functionCall.setTwoArguments(elementAddressRegister, checkingContext);
2153             failureCases.append(functionCall.callAndBranchOnCondition(Assembler::Zero));
2154         }
2155     }
2156 }
2157
2158 static void setLastChildState(Element* element)
2159 {
2160     if (RenderStyle* style = element->renderStyle())
2161         style->setLastChildState();
2162 }
2163
2164 void SelectorCodeGenerator::generateElementIsLastChild(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
2165 {
2166     if (m_selectorContext == SelectorContext::QuerySelector) {
2167         Assembler::JumpList successCase = jumpIfNoNextAdjacentElement();
2168         failureCases.append(m_assembler.jump());
2169
2170         successCase.link(&m_assembler);
2171         LocalRegister parent(m_registerAllocator);
2172         generateWalkToParentElement(failureCases, parent);
2173
2174         failureCases.append(m_assembler.branchTest32(Assembler::Zero, Assembler::Address(parent, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagIsParsingChildrenFinished())));
2175
2176         return;
2177     }
2178
2179     Assembler::RegisterID parentElement = m_registerAllocator.allocateRegister();
2180     generateWalkToParentElement(failureCases, parentElement);
2181
2182     // Zero in isLastChildRegister is the success case. The register is set to non-zero if a sibling if found.
2183     LocalRegister isLastChildRegister(m_registerAllocator);
2184     m_assembler.move(Assembler::TrustedImm32(0), isLastChildRegister);
2185
2186     {
2187         Assembler::Jump notFinishedParsingChildren = m_assembler.branchTest32(Assembler::Zero, Assembler::Address(parentElement, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagIsParsingChildrenFinished()));
2188
2189         Assembler::JumpList successCase = jumpIfNoNextAdjacentElement();
2190
2191         notFinishedParsingChildren.link(&m_assembler);
2192         m_assembler.move(Assembler::TrustedImm32(1), isLastChildRegister);
2193
2194         successCase.link(&m_assembler);
2195     }
2196
2197     LocalRegister checkingContext(m_registerAllocator);
2198     Assembler::Jump notResolvingStyle = jumpIfNotResolvingStyle(checkingContext);
2199
2200     setNodeFlag(m_assembler, parentElement, Node::flagChildrenAffectedByLastChildRulesFlag());
2201     m_registerAllocator.deallocateRegister(parentElement);
2202
2203     // The parent marking is unconditional. If the matching is not a success, we can now fail.
2204     // Otherwise we need to apply setLastChildState() on the RenderStyle.
2205     failureCases.append(m_assembler.branchTest32(Assembler::NonZero, isLastChildRegister));
2206
2207     if (fragment.relationToRightFragment == FragmentRelation::Rightmost)
2208         addFlagsToElementStyleFromContext(checkingContext, RenderStyle::NonInheritedFlags::setLastChildStateFlags());
2209     else {
2210         FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2211         functionCall.setFunctionAddress(setLastChildState);
2212         Assembler::RegisterID elementAddress = elementAddressRegister;
2213         functionCall.setOneArgument(elementAddress);
2214         functionCall.call();
2215     }
2216
2217     notResolvingStyle.link(&m_assembler);
2218     failureCases.append(m_assembler.branchTest32(Assembler::NonZero, isLastChildRegister));
2219 }
2220
2221 static void setOnlyChildState(Element* element)
2222 {
2223     if (RenderStyle* style = element->renderStyle()) {
2224         style->setFirstChildState();
2225         style->setLastChildState();
2226     }
2227 }
2228
2229 void SelectorCodeGenerator::generateElementIsOnlyChild(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
2230 {
2231     // Is Only child is pretty much a combination of isFirstChild + isLastChild. The main difference is that tree marking is combined.
2232     if (m_selectorContext == SelectorContext::QuerySelector) {
2233         Assembler::JumpList previousSuccessCase = jumpIfNoPreviousAdjacentElement();
2234         failureCases.append(m_assembler.jump());
2235         previousSuccessCase.link(&m_assembler);
2236
2237         Assembler::JumpList nextSuccessCase = jumpIfNoNextAdjacentElement();
2238         failureCases.append(m_assembler.jump());
2239         nextSuccessCase.link(&m_assembler);
2240
2241         LocalRegister parent(m_registerAllocator);
2242         generateWalkToParentElement(failureCases, parent);
2243
2244         failureCases.append(m_assembler.branchTest32(Assembler::Zero, Assembler::Address(parent, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagIsParsingChildrenFinished())));
2245
2246         return;
2247     }
2248
2249     Assembler::RegisterID parentElement = m_registerAllocator.allocateRegister();
2250     generateWalkToParentElement(failureCases, parentElement);
2251
2252     // Zero in isOnlyChildRegister is the success case. The register is set to non-zero if a sibling if found.
2253     LocalRegister isOnlyChildRegister(m_registerAllocator);
2254     m_assembler.move(Assembler::TrustedImm32(0), isOnlyChildRegister);
2255
2256     {
2257         Assembler::JumpList localFailureCases;
2258         {
2259             Assembler::JumpList successCase = jumpIfNoPreviousAdjacentElement();
2260             localFailureCases.append(m_assembler.jump());
2261             successCase.link(&m_assembler);
2262         }
2263         localFailureCases.append(m_assembler.branchTest32(Assembler::Zero, Assembler::Address(parentElement, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagIsParsingChildrenFinished())));
2264         Assembler::JumpList successCase = jumpIfNoNextAdjacentElement();
2265
2266         localFailureCases.link(&m_assembler);
2267         m_assembler.move(Assembler::TrustedImm32(1), isOnlyChildRegister);
2268
2269         successCase.link(&m_assembler);
2270     }
2271
2272     LocalRegister checkingContext(m_registerAllocator);
2273     Assembler::Jump notResolvingStyle = jumpIfNotResolvingStyle(checkingContext);
2274
2275     setNodeFlag(m_assembler, parentElement, Node::flagChildrenAffectedByFirstChildRulesFlag() | Node::flagChildrenAffectedByLastChildRulesFlag());
2276     m_registerAllocator.deallocateRegister(parentElement);
2277
2278     // The parent marking is unconditional. If the matching is not a success, we can now fail.
2279     // Otherwise we need to apply setLastChildState() on the RenderStyle.
2280     failureCases.append(m_assembler.branchTest32(Assembler::NonZero, isOnlyChildRegister));
2281
2282     if (fragment.relationToRightFragment == FragmentRelation::Rightmost)
2283         addFlagsToElementStyleFromContext(checkingContext, RenderStyle::NonInheritedFlags::setFirstChildStateFlags() | RenderStyle::NonInheritedFlags::setLastChildStateFlags());
2284     else {
2285         FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2286         functionCall.setFunctionAddress(setOnlyChildState);
2287         Assembler::RegisterID elementAddress = elementAddressRegister;
2288         functionCall.setOneArgument(elementAddress);
2289         functionCall.call();
2290     }
2291
2292     notResolvingStyle.link(&m_assembler);
2293     failureCases.append(m_assembler.branchTest32(Assembler::NonZero, isOnlyChildRegister));
2294 }
2295
2296 inline void SelectorCodeGenerator::generateElementHasTagName(Assembler::JumpList& failureCases, const QualifiedName& nameToMatch)
2297 {
2298     if (nameToMatch == anyQName())
2299         return;
2300
2301     // Load the QualifiedNameImpl from the input.
2302     LocalRegister qualifiedNameImpl(m_registerAllocator);
2303     m_assembler.loadPtr(Assembler::Address(elementAddressRegister, Element::tagQNameMemoryOffset() + QualifiedName::implMemoryOffset()), qualifiedNameImpl);
2304
2305     const AtomicString& selectorLocalName = nameToMatch.localName();
2306     if (selectorLocalName != starAtom) {
2307         // Generate localName == element->localName().
2308         LocalRegister constantRegister(m_registerAllocator);
2309         m_assembler.move(Assembler::TrustedImmPtr(selectorLocalName.impl()), constantRegister);
2310         failureCases.append(m_assembler.branchPtr(Assembler::NotEqual, Assembler::Address(qualifiedNameImpl, QualifiedName::QualifiedNameImpl::localNameMemoryOffset()), constantRegister));
2311     }
2312
2313     const AtomicString& selectorNamespaceURI = nameToMatch.namespaceURI();
2314     if (selectorNamespaceURI != starAtom) {
2315         // Generate namespaceURI == element->namespaceURI().
2316         LocalRegister constantRegister(m_registerAllocator);
2317         m_assembler.move(Assembler::TrustedImmPtr(selectorNamespaceURI.impl()), constantRegister);
2318         failureCases.append(m_assembler.branchPtr(Assembler::NotEqual, Assembler::Address(qualifiedNameImpl, QualifiedName::QualifiedNameImpl::namespaceMemoryOffset()), constantRegister));
2319     }
2320 }
2321
2322 void SelectorCodeGenerator::generateElementHasId(Assembler::JumpList& failureCases, const LocalRegister& elementDataAddress, const AtomicString& idToMatch)
2323 {
2324     // Compare the pointers of the AtomicStringImpl from idForStyleResolution with the reference idToMatch.
2325     LocalRegister idToMatchRegister(m_registerAllocator);
2326     m_assembler.move(Assembler::TrustedImmPtr(idToMatch.impl()), idToMatchRegister);
2327     failureCases.append(m_assembler.branchPtr(Assembler::NotEqual, Assembler::Address(elementDataAddress, ElementData::idForStyleResolutionMemoryOffset()), idToMatchRegister));
2328 }
2329
2330 void SelectorCodeGenerator::generateElementHasClasses(Assembler::JumpList& failureCases, const LocalRegister& elementDataAddress, const Vector<const AtomicStringImpl*>& classNames)
2331 {
2332     // Load m_classNames.
2333     LocalRegister spaceSplitStringData(m_registerAllocator);
2334     m_assembler.loadPtr(Assembler::Address(elementDataAddress, ElementData::classNamesMemoryOffset()), spaceSplitStringData);
2335
2336     // If SpaceSplitString does not have a SpaceSplitStringData pointer, it is empty -> failure case.
2337     failureCases.append(m_assembler.branchTestPtr(Assembler::Zero, spaceSplitStringData));
2338
2339     // We loop over the classes of SpaceSplitStringData for each class name we need to match.
2340     LocalRegister indexRegister(m_registerAllocator);
2341     for (unsigned i = 0; i < classNames.size(); ++i) {
2342         LocalRegister classNameToMatch(m_registerAllocator);
2343         m_assembler.move(Assembler::TrustedImmPtr(classNames[i]), classNameToMatch);
2344         m_assembler.move(Assembler::TrustedImm32(0), indexRegister);
2345
2346         // Beginning of a loop over all the class name of element to find the one we are looking for.
2347         Assembler::Label loopStart(m_assembler.label());
2348
2349         // If the pointers match, proceed to the next matcher.
2350         Assembler::Jump classFound = m_assembler.branchPtr(Assembler::Equal, Assembler::BaseIndex(spaceSplitStringData, indexRegister, Assembler::timesPtr(), SpaceSplitStringData::tokensMemoryOffset()), classNameToMatch);
2351
2352         // Increment the index.
2353         m_assembler.add32(Assembler::TrustedImm32(1), indexRegister);
2354
2355         // If we reached the last element -> failure.
2356         failureCases.append(m_assembler.branch32(Assembler::Equal, Assembler::Address(spaceSplitStringData, SpaceSplitStringData::sizeMemoryOffset()), indexRegister));
2357         // Otherwise just loop over.
2358         m_assembler.jump().linkTo(loopStart, &m_assembler);
2359
2360         // Success case.
2361         classFound.link(&m_assembler);
2362     }
2363 }
2364
2365 void SelectorCodeGenerator::generateElementIsLink(Assembler::JumpList& failureCases)
2366 {
2367     failureCases.append(m_assembler.branchTest32(Assembler::Zero, Assembler::Address(elementAddressRegister, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagIsLink())));
2368 }
2369
2370 static void setElementChildIndex(Element* element, int index)
2371 {
2372     element->setChildIndex(index);
2373 }
2374
2375 static void setElementChildIndexAndUpdateStyle(Element* element, int index)
2376 {
2377     element->setChildIndex(index);
2378     if (RenderStyle* childStyle = element->renderStyle())
2379         childStyle->setUnique();
2380 }
2381
2382 void SelectorCodeGenerator::generateElementIsNthChild(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
2383 {
2384     Assembler::RegisterID parentElement = m_registerAllocator.allocateRegister();
2385     generateWalkToParentElement(failureCases, parentElement);
2386
2387     Vector<std::pair<int, int>> validSubsetFilters;
2388     validSubsetFilters.reserveInitialCapacity(fragment.nthChildfilters.size());
2389     for (const auto& slot : fragment.nthChildfilters) {
2390         int a = slot.first;
2391         int b = slot.second;
2392
2393         // Anything modulo 1 is zero. Unless b restricts the range, this does not filter anything out.
2394         if (a == 1 && (!b || (b == 1)))
2395             continue;
2396         validSubsetFilters.uncheckedAppend(slot);
2397     }
2398     if (validSubsetFilters.isEmpty()) {
2399         m_registerAllocator.deallocateRegister(parentElement);
2400         return;
2401     }
2402     if (m_selectorContext == SelectorContext::QuerySelector)
2403         m_registerAllocator.deallocateRegister(parentElement);
2404
2405     // Setup the counter at 1.
2406     LocalRegister elementCounter(m_registerAllocator);
2407     m_assembler.move(Assembler::TrustedImm32(1), elementCounter);
2408
2409     // Loop over the previous adjacent elements and increment the counter.
2410     {
2411         LocalRegister previousSibling(m_registerAllocator);
2412         m_assembler.move(elementAddressRegister, previousSibling);
2413
2414         // Getting the child index is very efficient when it works. When there is no child index,
2415         // querying at every iteration is very inefficient. We solve this by only testing the child
2416         // index on the first direct adjacent.
2417         Assembler::JumpList noMoreSiblingsCases;
2418
2419         Assembler::JumpList noCachedChildIndexCases;
2420         generateWalkToPreviousAdjacentElement(noMoreSiblingsCases, previousSibling);
2421         noCachedChildIndexCases.append(m_assembler.branchTest32(Assembler::Zero, Assembler::Address(previousSibling, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagHasRareData())));
2422         {
2423             LocalRegister elementRareData(m_registerAllocator);
2424             m_assembler.loadPtr(Assembler::Address(previousSibling, Node::rareDataMemoryOffset()), elementRareData);
2425             LocalRegister cachedChildIndex(m_registerAllocator);
2426             m_assembler.load16(Assembler::Address(elementRareData, ElementRareData::childIndexMemoryOffset()), cachedChildIndex);
2427             noCachedChildIndexCases.append(m_assembler.branchTest32(Assembler::Zero, cachedChildIndex));
2428             m_assembler.add32(cachedChildIndex, elementCounter);
2429             noMoreSiblingsCases.append(m_assembler.jump());
2430         }
2431         noCachedChildIndexCases.link(&m_assembler);
2432         m_assembler.add32(Assembler::TrustedImm32(1), elementCounter);
2433
2434         Assembler::Label loopStart = m_assembler.label();
2435         generateWalkToPreviousAdjacentElement(noMoreSiblingsCases, previousSibling);
2436         m_assembler.add32(Assembler::TrustedImm32(1), elementCounter);
2437         m_assembler.jump().linkTo(loopStart, &m_assembler);
2438         noMoreSiblingsCases.link(&m_assembler);
2439     }
2440
2441     // Tree marking when doing style resolution.
2442     if (m_selectorContext != SelectorContext::QuerySelector) {
2443         LocalRegister checkingContext(m_registerAllocator);
2444         Assembler::Jump notResolvingStyle = jumpIfNotResolvingStyle(checkingContext);
2445
2446         m_registerAllocator.deallocateRegister(parentElement);
2447         FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2448         functionCall.setFunctionAddress(Element::setChildrenAffectedByForwardPositionalRules);
2449         functionCall.setOneArgument(parentElement);
2450         functionCall.call();
2451
2452         if (fragment.relationToRightFragment == FragmentRelation::Rightmost) {
2453             addFlagsToElementStyleFromContext(checkingContext, RenderStyle::NonInheritedFlags::flagIsUnique());
2454
2455             Assembler::RegisterID elementAddress = elementAddressRegister;
2456             FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2457             functionCall.setFunctionAddress(setElementChildIndex);
2458             functionCall.setTwoArguments(elementAddress, elementCounter);
2459             functionCall.call();
2460         } else {
2461             Assembler::RegisterID elementAddress = elementAddressRegister;
2462             FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2463             functionCall.setFunctionAddress(setElementChildIndexAndUpdateStyle);
2464             functionCall.setTwoArguments(elementAddress, elementCounter);
2465             functionCall.call();
2466         }
2467
2468         notResolvingStyle.link(&m_assembler);
2469     }
2470
2471     // Test every the nth-child filter.
2472     for (const auto& slot : validSubsetFilters) {
2473         int a = slot.first;
2474         int b = slot.second;
2475
2476         if (!a)
2477             failureCases.append(m_assembler.branch32(Assembler::NotEqual, Assembler::TrustedImm32(b), elementCounter));
2478         else if (a > 0) {
2479             if (a == 2 && b == 1) {
2480                 // This is the common case 2n+1 (or "odd"), we can test for odd values without doing the arithmetic.
2481                 failureCases.append(m_assembler.branchTest32(Assembler::Zero, elementCounter, Assembler::TrustedImm32(1)));
2482             } else {
2483                 if (b)
2484                     failureCases.append(m_assembler.branchSub32(Assembler::Signed, Assembler::TrustedImm32(b), elementCounter));
2485                 moduloIsZero(failureCases, elementCounter, a);
2486             }
2487         } else {
2488             LocalRegister bRegister(m_registerAllocator);
2489             m_assembler.move(Assembler::TrustedImm32(b), bRegister);
2490
2491             failureCases.append(m_assembler.branchSub32(Assembler::Signed, elementCounter, bRegister));
2492             moduloIsZero(failureCases, bRegister, a);
2493         }
2494     }
2495 }
2496
2497 void SelectorCodeGenerator::generateElementIsRoot(Assembler::JumpList& failureCases)
2498 {
2499     LocalRegister document(m_registerAllocator);
2500     getDocument(m_assembler, elementAddressRegister, document);
2501     failureCases.append(m_assembler.branchPtr(Assembler::NotEqual, Assembler::Address(document, Document::documentElementMemoryOffset()), elementAddressRegister));
2502 }
2503
2504 void SelectorCodeGenerator::generateElementIsTarget(Assembler::JumpList& failureCases)
2505 {
2506     LocalRegister document(m_registerAllocator);
2507     getDocument(m_assembler, elementAddressRegister, document);
2508     failureCases.append(m_assembler.branchPtr(Assembler::NotEqual, Assembler::Address(document, Document::cssTargetMemoryOffset()), elementAddressRegister));
2509 }
2510
2511 }; // namespace SelectorCompiler.
2512 }; // namespace WebCore.
2513
2514 #endif // ENABLE(CSS_SELECTOR_JIT)