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