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