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