2c9aa9377988f3ce4c66d3d3af9eb176e6a2c645
[WebKit-https.git] / Source / WebCore / cssjit / SelectorCompiler.cpp
1 /*
2  * Copyright (C) 2013, 2014 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
14  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23  * THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 #include "config.h"
27 #include "SelectorCompiler.h"
28
29 #if ENABLE(CSS_SELECTOR_JIT)
30
31 #include "CSSSelector.h"
32 #include "Element.h"
33 #include "ElementData.h"
34 #include "FunctionCall.h"
35 #include "HTMLNames.h"
36 #include "NodeRenderStyle.h"
37 #include "QualifiedName.h"
38 #include "RegisterAllocator.h"
39 #include "RenderElement.h"
40 #include "RenderStyle.h"
41 #include "SVGElement.h"
42 #include "SelectorCheckerTestFunctions.h"
43 #include "StackAllocator.h"
44 #include "StyledElement.h"
45 #include <JavaScriptCore/LinkBuffer.h>
46 #include <JavaScriptCore/MacroAssembler.h>
47 #include <JavaScriptCore/VM.h>
48 #include <wtf/HashMap.h>
49 #include <wtf/HashSet.h>
50 #include <wtf/Vector.h>
51
52 namespace WebCore {
53 namespace SelectorCompiler {
54
55 #define CSS_SELECTOR_JIT_DEBUGGING 0
56
57 enum class BacktrackingAction {
58     NoBacktracking,
59     JumpToDescendantEntryPoint,
60     JumpToIndirectAdjacentEntryPoint,
61     JumpToDescendantTreeWalkerEntryPoint,
62     JumpToDescendantTail,
63     JumpToClearAdjacentDescendantTail,
64     JumpToDirectAdjacentTail
65 };
66
67 struct BacktrackingFlag {
68     enum {
69         DescendantEntryPoint = 1,
70         IndirectAdjacentEntryPoint = 1 << 1,
71         SaveDescendantBacktrackingStart = 1 << 2,
72         SaveAdjacentBacktrackingStart = 1 << 3,
73         DirectAdjacentTail = 1 << 4,
74         DescendantTail = 1 << 5,
75     };
76 };
77
78 enum class FragmentRelation {
79     Rightmost,
80     Descendant,
81     Child,
82     DirectAdjacent,
83     IndirectAdjacent
84 };
85
86 enum class FunctionType {
87     SimpleSelectorChecker,
88     SelectorCheckerWithCheckingContext,
89     CannotCompile
90 };
91
92 struct SelectorFragment {
93     SelectorFragment()
94         : traversalBacktrackingAction(BacktrackingAction::NoBacktracking)
95         , matchingBacktrackingAction(BacktrackingAction::NoBacktracking)
96         , backtrackingFlags(0)
97         , tagName(nullptr)
98         , id(nullptr)
99     {
100     }
101     FragmentRelation relationToLeftFragment;
102     FragmentRelation relationToRightFragment;
103
104     BacktrackingAction traversalBacktrackingAction;
105     BacktrackingAction matchingBacktrackingAction;
106     unsigned char backtrackingFlags;
107
108     const QualifiedName* tagName;
109     const AtomicString* id;
110     Vector<const AtomicStringImpl*, 1> classNames;
111     HashSet<unsigned> pseudoClasses;
112     Vector<JSC::FunctionPtr> unoptimizedPseudoClasses;
113     Vector<const CSSSelector*> attributes;
114 };
115
116 typedef JSC::MacroAssembler Assembler;
117 typedef Vector<SelectorFragment, 8> SelectorFragmentList;
118
119 class SelectorCodeGenerator {
120 public:
121     SelectorCodeGenerator(const CSSSelector*);
122     SelectorCompilationStatus compile(JSC::VM*, JSC::MacroAssemblerCodeRef&);
123
124 private:
125 #if CPU(X86_64)
126     static const Assembler::RegisterID returnRegister = JSC::X86Registers::eax;
127     static const Assembler::RegisterID elementAddressRegister = JSC::X86Registers::edi;
128     static const Assembler::RegisterID checkingContextRegister = JSC::X86Registers::esi;
129 #endif
130
131     void computeBacktrackingInformation();
132
133     // Element relations tree walker.
134     void generateWalkToParentElement(Assembler::JumpList& failureCases, Assembler::RegisterID targetRegister);
135     void generateParentElementTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment&);
136     void generateAncestorTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment&);
137
138     void generateWalkToPreviousAdjacent(Assembler::JumpList& failureCases, const SelectorFragment&);
139     void generateDirectAdjacentTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment&);
140     void generateIndirectAdjacentTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment&);
141     void markParentElementIfResolvingStyle(JSC::FunctionPtr);
142
143     void linkFailures(Assembler::JumpList& globalFailureCases, BacktrackingAction, Assembler::JumpList& localFailureCases);
144     void generateAdjacentBacktrackingTail(StackAllocator& adjacentTailStack);
145     void generateDescendantBacktrackingTail();
146     void generateBacktrackingTailsIfNeeded(const SelectorFragment&);
147
148     // Element properties matchers.
149     void generateElementMatching(Assembler::JumpList& failureCases, const SelectorFragment&);
150     void generateElementDataMatching(Assembler::JumpList& failureCases, const SelectorFragment&);
151     void generateElementFunctionCallTest(Assembler::JumpList& failureCases, JSC::FunctionPtr);
152     void generateSynchronizeStyleAttribute(Assembler::RegisterID elementDataArraySizeAndFlags);
153     void generateSynchronizeAllAnimatedSVGAttribute(Assembler::RegisterID elementDataArraySizeAndFlags);
154     void generateElementAttributesMatching(Assembler::JumpList& failureCases, const LocalRegister& elementDataAddress, const SelectorFragment&);
155     void generateElementAttributeMatching(Assembler::JumpList& failureCases, Assembler::RegisterID currentAttributeAddress, Assembler::RegisterID decIndexRegister, const CSSSelector* attributeSelector);
156     void generateElementHasTagName(Assembler::JumpList& failureCases, const QualifiedName& nameToMatch);
157     void generateElementHasId(Assembler::JumpList& failureCases, const LocalRegister& elementDataAddress, const AtomicString& idToMatch);
158     void generateElementHasClasses(Assembler::JumpList& failureCases, const LocalRegister& elementDataAddress, const Vector<const AtomicStringImpl*>& classNames);
159     void generateElementIsLink(Assembler::JumpList& failureCases);
160
161     Assembler m_assembler;
162     RegisterAllocator m_registerAllocator;
163     StackAllocator m_stackAllocator;
164     Vector<std::pair<Assembler::Call, JSC::FunctionPtr>> m_functionCalls;
165
166     FunctionType m_functionType;
167     SelectorFragmentList m_selectorFragments;
168     bool m_selectorCannotMatchAnything;
169
170     StackAllocator::StackReference m_checkingContextStackReference;
171
172     Assembler::Label m_descendantEntryPoint;
173     Assembler::Label m_indirectAdjacentEntryPoint;
174     Assembler::Label m_descendantTreeWalkerBacktrackingPoint;
175     Assembler::RegisterID m_descendantBacktrackingStart;
176     Assembler::JumpList m_descendantBacktrackingFailureCases;
177     StackAllocator::StackReference m_adjacentBacktrackingStart;
178     Assembler::JumpList m_adjacentBacktrackingFailureCases;
179     Assembler::JumpList m_clearAdjacentEntryPointDescendantFailureCases;
180
181 #if CSS_SELECTOR_JIT_DEBUGGING
182     const CSSSelector* m_originalSelector;
183 #endif
184 };
185
186 SelectorCompilationStatus compileSelector(const CSSSelector* lastSelector, JSC::VM* vm, JSC::MacroAssemblerCodeRef& codeRef)
187 {
188     if (!vm->canUseJIT())
189         return SelectorCompilationStatus::CannotCompile;
190     SelectorCodeGenerator codeGenerator(lastSelector);
191     return codeGenerator.compile(vm, codeRef);
192 }
193
194 static inline FragmentRelation fragmentRelationForSelectorRelation(CSSSelector::Relation relation)
195 {
196     switch (relation) {
197     case CSSSelector::Descendant:
198         return FragmentRelation::Descendant;
199     case CSSSelector::Child:
200         return FragmentRelation::Child;
201     case CSSSelector::DirectAdjacent:
202         return FragmentRelation::DirectAdjacent;
203     case CSSSelector::IndirectAdjacent:
204         return FragmentRelation::IndirectAdjacent;
205     case CSSSelector::SubSelector:
206     case CSSSelector::ShadowDescendant:
207         ASSERT_NOT_REACHED();
208     }
209     ASSERT_NOT_REACHED();
210     return FragmentRelation::Descendant;
211 }
212
213 static inline FunctionType mostRestrictiveFunctionType(FunctionType a, FunctionType b)
214 {
215     return std::max(a, b);
216 }
217
218 static inline FunctionType addPseudoType(CSSSelector::PseudoType type, SelectorFragment& pseudoClasses)
219 {
220     switch (type) {
221     // Unoptimized pseudo selector. They are just function call to a simple testing function.
222     case CSSSelector::PseudoAutofill:
223         pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isAutofilled));
224         return FunctionType::SimpleSelectorChecker;
225     case CSSSelector::PseudoChecked:
226         pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isChecked));
227         return FunctionType::SimpleSelectorChecker;
228     case CSSSelector::PseudoDefault:
229         pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isDefaultButtonForForm));
230         return FunctionType::SimpleSelectorChecker;
231     case CSSSelector::PseudoDisabled:
232         pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isDisabled));
233         return FunctionType::SimpleSelectorChecker;
234     case CSSSelector::PseudoEnabled:
235         pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isEnabled));
236         return FunctionType::SimpleSelectorChecker;
237     case CSSSelector::PseudoFocus:
238         pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(SelectorChecker::matchesFocusPseudoClass));
239         return FunctionType::SimpleSelectorChecker;
240     case CSSSelector::PseudoIndeterminate:
241         pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(shouldAppearIndeterminate));
242         return FunctionType::SimpleSelectorChecker;
243     case CSSSelector::PseudoInvalid:
244         pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isInvalid));
245         return FunctionType::SimpleSelectorChecker;
246     case CSSSelector::PseudoOptional:
247         pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isOptionalFormControl));
248         return FunctionType::SimpleSelectorChecker;
249     case CSSSelector::PseudoReadOnly:
250         pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesReadOnlyPseudoClass));
251         return FunctionType::SimpleSelectorChecker;
252     case CSSSelector::PseudoReadWrite:
253         pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesReadWritePseudoClass));
254         return FunctionType::SimpleSelectorChecker;
255     case CSSSelector::PseudoRequired:
256         pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isRequiredFormControl));
257         return FunctionType::SimpleSelectorChecker;
258     case CSSSelector::PseudoValid:
259         pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isValid));
260         return FunctionType::SimpleSelectorChecker;
261 #if ENABLE(FULLSCREEN_API)
262     case CSSSelector::PseudoFullScreen:
263         pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesFullScreenPseudoClass));
264         return FunctionType::SimpleSelectorChecker;
265 #endif
266 #if ENABLE(VIDEO_TRACK)
267     case CSSSelector::PseudoFutureCue:
268         pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesFutureCuePseudoClass));
269         return FunctionType::SimpleSelectorChecker;
270     case CSSSelector::PseudoPastCue:
271         pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesPastCuePseudoClass));
272         return FunctionType::SimpleSelectorChecker;
273 #endif
274
275     // Optimized pseudo selectors.
276     case CSSSelector::PseudoAnyLink:
277         pseudoClasses.pseudoClasses.add(CSSSelector::PseudoLink);
278         return FunctionType::SimpleSelectorChecker;
279
280     case CSSSelector::PseudoLink:
281         pseudoClasses.pseudoClasses.add(type);
282         return FunctionType::SimpleSelectorChecker;
283
284     default:
285         break;
286     }
287     return FunctionType::CannotCompile;
288 }
289
290 inline SelectorCodeGenerator::SelectorCodeGenerator(const CSSSelector* rootSelector)
291     : m_stackAllocator(m_assembler)
292     , m_functionType(FunctionType::SimpleSelectorChecker)
293     , m_selectorCannotMatchAnything(false)
294 #if CSS_SELECTOR_JIT_DEBUGGING
295     , m_originalSelector(rootSelector)
296 #endif
297 {
298 #if CSS_SELECTOR_JIT_DEBUGGING
299     dataLogF("Compiling \"%s\"\n", m_originalSelector->selectorText().utf8().data());
300 #endif
301
302     SelectorFragment fragment;
303     FragmentRelation relationToPreviousFragment = FragmentRelation::Rightmost;
304     for (const CSSSelector* selector = rootSelector; selector; selector = selector->tagHistory()) {
305         switch (selector->m_match) {
306         case CSSSelector::Tag:
307             ASSERT(!fragment.tagName);
308             fragment.tagName = &(selector->tagQName());
309             break;
310         case CSSSelector::Id: {
311             const AtomicString& id = selector->value();
312             if (fragment.id) {
313                 if (id != *fragment.id)
314                     goto InconsistentSelector;
315             } else
316                 fragment.id = &(selector->value());
317             break;
318         }
319         case CSSSelector::Class:
320             fragment.classNames.append(selector->value().impl());
321             break;
322         case CSSSelector::PseudoClass:
323             m_functionType = mostRestrictiveFunctionType(m_functionType, addPseudoType(selector->pseudoType(), fragment));
324             if (m_functionType == FunctionType::CannotCompile)
325                 goto CannotHandleSelector;
326             break;
327         case CSSSelector::Set:
328             fragment.attributes.append(selector);
329             break;
330         case CSSSelector::Unknown:
331         case CSSSelector::Exact:
332         case CSSSelector::List:
333         case CSSSelector::Hyphen:
334         case CSSSelector::PseudoElement:
335         case CSSSelector::Contain:
336         case CSSSelector::Begin:
337         case CSSSelector::End:
338         case CSSSelector::PagePseudoClass:
339             goto CannotHandleSelector;
340         }
341
342         CSSSelector::Relation relation = selector->relation();
343         if (relation == CSSSelector::SubSelector)
344             continue;
345
346         if (relation == CSSSelector::ShadowDescendant && !selector->isLastInTagHistory())
347             goto CannotHandleSelector;
348
349         if (relation == CSSSelector::DirectAdjacent || relation == CSSSelector::IndirectAdjacent)
350             m_functionType = std::max(m_functionType, FunctionType::SelectorCheckerWithCheckingContext);
351
352         fragment.relationToLeftFragment = fragmentRelationForSelectorRelation(relation);
353         fragment.relationToRightFragment = relationToPreviousFragment;
354         relationToPreviousFragment = fragment.relationToLeftFragment;
355
356         m_selectorFragments.append(fragment);
357         fragment = SelectorFragment();
358     }
359
360     computeBacktrackingInformation();
361
362     return;
363 InconsistentSelector:
364     m_functionType = FunctionType::SimpleSelectorChecker;
365     m_selectorCannotMatchAnything = true;
366 CannotHandleSelector:
367     m_selectorFragments.clear();
368 }
369
370 static inline unsigned minimumRegisterRequirements(const SelectorFragmentList& selectorFragments)
371 {
372     // Strict minimum to match anything interesting:
373     // Element + BacktrackingRegister + ElementData + a pointer to values + an index on that pointer + the value we expect;
374     unsigned minimum = 6;
375
376     // Attributes cause some register pressure.
377     for (unsigned selectorFragmentIndex = 0; selectorFragmentIndex < selectorFragments.size(); ++selectorFragmentIndex) {
378         const SelectorFragment& selectorFragment = selectorFragments[selectorFragmentIndex];
379         const Vector<const CSSSelector*>& attributes = selectorFragment.attributes;
380
381         for (unsigned attributeIndex = 0; attributeIndex < attributes.size(); ++attributeIndex) {
382             // Element + ElementData + scratchRegister + attributeArrayPointer + expectedLocalName + qualifiedNameImpl.
383             unsigned attributeMinimum = 6;
384             if (selectorFragment.traversalBacktrackingAction == BacktrackingAction::JumpToDescendantTail
385                 || selectorFragment.matchingBacktrackingAction == BacktrackingAction::JumpToDescendantTail)
386                 attributeMinimum += 1; // If there is a DescendantTail, there is a backtracking register.
387
388             if (attributes.size() != 1)
389                 attributeMinimum += 2; // For the local copy of the counter and attributeArrayPointer.
390
391             const CSSSelector* attributeSelector = attributes[attributeIndex];
392             if (attributeSelector->attribute().prefix() != starAtom && !attributeSelector->attribute().namespaceURI().isNull())
393                 attributeMinimum += 1; // Additional register for the expected namespace.
394
395             minimum = std::max(minimum, attributeMinimum);
396         }
397     }
398
399     return minimum;
400 }
401
402 inline SelectorCompilationStatus SelectorCodeGenerator::compile(JSC::VM* vm, JSC::MacroAssemblerCodeRef& codeRef)
403 {
404     if (m_selectorFragments.isEmpty() && !m_selectorCannotMatchAnything)
405         return SelectorCompilationStatus::CannotCompile;
406
407     bool reservedCalleeSavedRegisters = false;
408     unsigned availableRegisterCount = m_registerAllocator.availableRegisterCount();
409     unsigned minimumRegisterCountForAttributes = minimumRegisterRequirements(m_selectorFragments);
410     if (availableRegisterCount < minimumRegisterCountForAttributes) {
411         reservedCalleeSavedRegisters = true;
412         m_registerAllocator.reserveCalleeSavedRegisters(m_stackAllocator, minimumRegisterCountForAttributes - availableRegisterCount);
413     }
414
415     m_registerAllocator.allocateRegister(elementAddressRegister);
416
417     if (m_functionType == FunctionType::SelectorCheckerWithCheckingContext)
418         m_checkingContextStackReference = m_stackAllocator.push(checkingContextRegister);
419
420     Assembler::JumpList failureCases;
421
422     for (unsigned i = 0; i < m_selectorFragments.size(); ++i) {
423         const SelectorFragment& fragment = m_selectorFragments[i];
424         switch (fragment.relationToRightFragment) {
425         case FragmentRelation::Rightmost:
426             generateElementMatching(failureCases, fragment);
427             break;
428         case FragmentRelation::Descendant:
429             generateAncestorTreeWalker(failureCases, fragment);
430             break;
431         case FragmentRelation::Child:
432             generateParentElementTreeWalker(failureCases, fragment);
433             break;
434         case FragmentRelation::DirectAdjacent:
435             generateDirectAdjacentTreeWalker(failureCases, fragment);
436             break;
437         case FragmentRelation::IndirectAdjacent:
438             generateIndirectAdjacentTreeWalker(failureCases, fragment);
439             break;
440         }
441         generateBacktrackingTailsIfNeeded(fragment);
442     }
443
444     m_registerAllocator.deallocateRegister(elementAddressRegister);
445
446     if (m_functionType == FunctionType::SimpleSelectorChecker && m_selectorCannotMatchAnything) {
447         m_assembler.move(Assembler::TrustedImm32(0), returnRegister);
448         m_assembler.ret();
449     } else if (m_functionType == FunctionType::SimpleSelectorChecker) {
450         // Success.
451         m_assembler.move(Assembler::TrustedImm32(1), returnRegister);
452         if (!reservedCalleeSavedRegisters)
453             m_assembler.ret();
454
455         // Failure.
456         if (!failureCases.empty()) {
457             Assembler::Jump skipFailureCase;
458             if (reservedCalleeSavedRegisters)
459                 skipFailureCase = m_assembler.jump();
460
461             failureCases.link(&m_assembler);
462             m_assembler.move(Assembler::TrustedImm32(0), returnRegister);
463
464             if (!reservedCalleeSavedRegisters)
465                 m_assembler.ret();
466             else
467                 skipFailureCase.link(&m_assembler);
468         }
469         if (reservedCalleeSavedRegisters) {
470             m_registerAllocator.restoreCalleeSavedRegisters(m_stackAllocator);
471             m_assembler.ret();
472         }
473     } else {
474         ASSERT(m_functionType == FunctionType::SelectorCheckerWithCheckingContext);
475         ASSERT(!m_selectorCannotMatchAnything);
476
477         // Success.
478         m_assembler.move(Assembler::TrustedImm32(1), returnRegister);
479
480         StackAllocator successStack = m_stackAllocator;
481         StackAllocator failureStack = m_stackAllocator;
482
483         LocalRegister checkingContextRegister(m_registerAllocator);
484         successStack.pop(m_checkingContextStackReference, checkingContextRegister);
485
486         // Failure.
487         if (!failureCases.empty()) {
488             Assembler::Jump skipFailureCase = m_assembler.jump();
489
490             failureCases.link(&m_assembler);
491             failureStack.discard();
492             m_assembler.move(Assembler::TrustedImm32(0), returnRegister);
493
494             skipFailureCase.link(&m_assembler);
495         }
496
497         m_stackAllocator.merge(std::move(successStack), std::move(failureStack));
498         m_registerAllocator.restoreCalleeSavedRegisters(m_stackAllocator);
499         m_assembler.ret();
500     }
501
502     JSC::LinkBuffer linkBuffer(*vm, &m_assembler, CSS_CODE_ID);
503     for (unsigned i = 0; i < m_functionCalls.size(); i++)
504         linkBuffer.link(m_functionCalls[i].first, m_functionCalls[i].second);
505
506 #if CSS_SELECTOR_JIT_DEBUGGING && ASSERT_DISABLED
507     codeRef = linkBuffer.finalizeCodeWithDisassembly("CSS Selector JIT for \"%s\"", m_originalSelector->selectorText().utf8().data());
508 #else
509     codeRef = FINALIZE_CODE(linkBuffer, ("CSS Selector JIT"));
510 #endif
511
512     if (m_functionType == FunctionType::SimpleSelectorChecker)
513         return SelectorCompilationStatus::SimpleSelectorChecker;
514     return SelectorCompilationStatus::SelectorCheckerWithCheckingContext;
515 }
516
517
518 static inline void updateChainStates(const SelectorFragment& fragment, bool& hasDescendantRelationOnTheRight, unsigned& ancestorPositionSinceDescendantRelation, bool& hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain, unsigned& adjacentPositionSinceIndirectAdjacentTreeWalk)
519 {
520     switch (fragment.relationToRightFragment) {
521     case FragmentRelation::Rightmost:
522         break;
523     case FragmentRelation::Descendant:
524         hasDescendantRelationOnTheRight = true;
525         ancestorPositionSinceDescendantRelation = 0;
526         hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain = false;
527         break;
528     case FragmentRelation::Child:
529         ++ancestorPositionSinceDescendantRelation;
530         hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain = false;
531         break;
532     case FragmentRelation::DirectAdjacent:
533         if (hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain)
534             ++adjacentPositionSinceIndirectAdjacentTreeWalk;
535         break;
536     case FragmentRelation::IndirectAdjacent:
537         hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain = true;
538         break;
539     }
540 }
541
542 static inline bool isFirstAncestor(unsigned ancestorPositionSinceDescendantRelation)
543 {
544     return ancestorPositionSinceDescendantRelation == 1;
545 }
546
547 static inline bool isFirstAdjacent(unsigned ancestorPositionSinceDescendantRelation)
548 {
549     return ancestorPositionSinceDescendantRelation == 1;
550 }
551
552 static inline bool isAfterChildRelation(unsigned ancestorPositionSinceDescendantRelation)
553 {
554     return ancestorPositionSinceDescendantRelation > 0;
555 }
556
557 static inline void solveBacktrackingAction(SelectorFragment& fragment, bool hasDescendantRelationOnTheRight, unsigned ancestorPositionSinceDescendantRelation, bool hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain, unsigned adjacentPositionSinceIndirectAdjacentTreeWalk)
558 {
559     switch (fragment.relationToRightFragment) {
560     case FragmentRelation::Rightmost:
561     case FragmentRelation::Descendant:
562         break;
563     case FragmentRelation::Child:
564         // Failure to match the element should resume matching at the nearest ancestor/descendant entry point.
565         if (hasDescendantRelationOnTheRight) {
566             if (isFirstAncestor(ancestorPositionSinceDescendantRelation))
567                 fragment.matchingBacktrackingAction = BacktrackingAction::JumpToDescendantEntryPoint;
568             else
569                 fragment.matchingBacktrackingAction = BacktrackingAction::JumpToDescendantTail;
570         }
571         break;
572     case FragmentRelation::DirectAdjacent:
573         // Failure on traversal implies no other sibling traversal can match. Matching should resume at the
574         // nearest ancestor/descendant traversal.
575         if (hasDescendantRelationOnTheRight) {
576             if (!isAfterChildRelation(ancestorPositionSinceDescendantRelation))
577                 fragment.traversalBacktrackingAction = BacktrackingAction::JumpToDescendantTreeWalkerEntryPoint;
578             else {
579                 if (!hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain || isFirstAdjacent(adjacentPositionSinceIndirectAdjacentTreeWalk))
580                     fragment.traversalBacktrackingAction = BacktrackingAction::JumpToDescendantTail;
581                 else
582                     fragment.traversalBacktrackingAction = BacktrackingAction::JumpToClearAdjacentDescendantTail;
583             }
584         }
585
586         // If the rightmost relation is a indirect adjacent, matching sould resume from there.
587         // Otherwise, we resume from the latest ancestor/descendant if any.
588         if (hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain) {
589             if (isFirstAdjacent(adjacentPositionSinceIndirectAdjacentTreeWalk))
590                 fragment.matchingBacktrackingAction = BacktrackingAction::JumpToIndirectAdjacentEntryPoint;
591             else
592                 fragment.matchingBacktrackingAction = BacktrackingAction::JumpToDirectAdjacentTail;
593         } else if (hasDescendantRelationOnTheRight) {
594             if (isAfterChildRelation(ancestorPositionSinceDescendantRelation))
595                 fragment.matchingBacktrackingAction = BacktrackingAction::JumpToDescendantTail;
596             else if (hasDescendantRelationOnTheRight)
597                 fragment.matchingBacktrackingAction = BacktrackingAction::JumpToDescendantTreeWalkerEntryPoint;
598         }
599         break;
600     case FragmentRelation::IndirectAdjacent:
601         // Failure on traversal implies no other sibling matching will succeed. Matching can resume
602         // from the latest ancestor/descendant.
603         if (hasDescendantRelationOnTheRight) {
604             if (isAfterChildRelation(ancestorPositionSinceDescendantRelation))
605                 fragment.traversalBacktrackingAction = BacktrackingAction::JumpToDescendantTail;
606             else
607                 fragment.traversalBacktrackingAction = BacktrackingAction::JumpToDescendantTreeWalkerEntryPoint;
608         }
609         break;
610     }
611 }
612
613 static bool requiresAdjacentTail(const SelectorFragment& fragment)
614 {
615     ASSERT(fragment.traversalBacktrackingAction != BacktrackingAction::JumpToDirectAdjacentTail);
616     return fragment.matchingBacktrackingAction == BacktrackingAction::JumpToDirectAdjacentTail;
617 }
618
619 static bool requiresDescendantTail(const SelectorFragment& fragment)
620 {
621     return fragment.matchingBacktrackingAction == BacktrackingAction::JumpToDescendantTail || fragment.traversalBacktrackingAction == BacktrackingAction::JumpToDescendantTail;
622 }
623
624 void SelectorCodeGenerator::computeBacktrackingInformation()
625 {
626     bool hasDescendantRelationOnTheRight = false;
627     unsigned ancestorPositionSinceDescendantRelation = 0;
628     bool hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain = false;
629     unsigned adjacentPositionSinceIndirectAdjacentTreeWalk = 0;
630
631     bool needsAdjacentTail = false;
632     bool needsDescendantTail = false;
633
634     for (unsigned i = 0; i < m_selectorFragments.size(); ++i) {
635         SelectorFragment& fragment = m_selectorFragments[i];
636
637         updateChainStates(fragment, hasDescendantRelationOnTheRight, ancestorPositionSinceDescendantRelation, hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain, adjacentPositionSinceIndirectAdjacentTreeWalk);
638
639         solveBacktrackingAction(fragment, hasDescendantRelationOnTheRight, ancestorPositionSinceDescendantRelation, hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain, adjacentPositionSinceIndirectAdjacentTreeWalk);
640
641         needsAdjacentTail |= requiresAdjacentTail(fragment);
642         needsDescendantTail |= requiresDescendantTail(fragment);
643
644         // Add code generation flags.
645         if (fragment.relationToLeftFragment != FragmentRelation::Descendant && fragment.relationToRightFragment == FragmentRelation::Descendant)
646             fragment.backtrackingFlags |= BacktrackingFlag::DescendantEntryPoint;
647         if (fragment.relationToLeftFragment == FragmentRelation::DirectAdjacent && fragment.relationToRightFragment == FragmentRelation::IndirectAdjacent)
648             fragment.backtrackingFlags |= BacktrackingFlag::IndirectAdjacentEntryPoint;
649         if (fragment.relationToLeftFragment != FragmentRelation::Descendant && fragment.relationToRightFragment == FragmentRelation::Child && isFirstAncestor(ancestorPositionSinceDescendantRelation))
650             fragment.backtrackingFlags |= BacktrackingFlag::SaveDescendantBacktrackingStart;
651         if (fragment.relationToLeftFragment == FragmentRelation::DirectAdjacent && fragment.relationToRightFragment == FragmentRelation::DirectAdjacent && isFirstAdjacent(adjacentPositionSinceIndirectAdjacentTreeWalk))
652             fragment.backtrackingFlags |= BacktrackingFlag::SaveAdjacentBacktrackingStart;
653         if (fragment.relationToLeftFragment != FragmentRelation::DirectAdjacent && needsAdjacentTail) {
654             ASSERT(fragment.relationToRightFragment == FragmentRelation::DirectAdjacent);
655             fragment.backtrackingFlags |= BacktrackingFlag::DirectAdjacentTail;
656             needsAdjacentTail = false;
657         }
658         if (fragment.relationToLeftFragment == FragmentRelation::Descendant && needsDescendantTail) {
659             fragment.backtrackingFlags |= BacktrackingFlag::DescendantTail;
660             needsDescendantTail = false;
661         }
662     }
663 }
664
665 static inline Assembler::Jump testIsElementFlagOnNode(Assembler::ResultCondition condition, Assembler& assembler, Assembler::RegisterID nodeAddress)
666 {
667     return assembler.branchTest32(condition, Assembler::Address(nodeAddress, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagIsElement()));
668 }
669
670 void SelectorCodeGenerator::generateWalkToParentElement(Assembler::JumpList& failureCases, Assembler::RegisterID targetRegister)
671 {
672     //    ContainerNode* parent = parentNode()
673     //    if (!parent || !parent->isElementNode())
674     //         failure
675     m_assembler.loadPtr(Assembler::Address(elementAddressRegister, Node::parentNodeMemoryOffset()), targetRegister);
676     failureCases.append(m_assembler.branchTestPtr(Assembler::Zero, targetRegister));
677     failureCases.append(testIsElementFlagOnNode(Assembler::Zero, m_assembler, targetRegister));
678 }
679
680 void SelectorCodeGenerator::generateParentElementTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
681 {
682     Assembler::JumpList traversalFailureCases;
683     generateWalkToParentElement(traversalFailureCases, elementAddressRegister);
684     linkFailures(failureCases, fragment.traversalBacktrackingAction, traversalFailureCases);
685
686     Assembler::JumpList matchingFailureCases;
687     generateElementMatching(matchingFailureCases, fragment);
688     linkFailures(failureCases, fragment.matchingBacktrackingAction, matchingFailureCases);
689
690     if (fragment.backtrackingFlags & BacktrackingFlag::SaveDescendantBacktrackingStart) {
691         m_descendantBacktrackingStart = m_registerAllocator.allocateRegister();
692         m_assembler.move(elementAddressRegister, m_descendantBacktrackingStart);
693     }
694 }
695
696 void SelectorCodeGenerator::generateAncestorTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
697 {
698     // Loop over the ancestors until one of them matches the fragment.
699     Assembler::Label loopStart(m_assembler.label());
700
701     if (fragment.backtrackingFlags & BacktrackingFlag::DescendantEntryPoint)
702         m_descendantTreeWalkerBacktrackingPoint = m_assembler.label();
703
704     generateWalkToParentElement(failureCases, elementAddressRegister);
705
706     if (fragment.backtrackingFlags & BacktrackingFlag::DescendantEntryPoint)
707         m_descendantEntryPoint = m_assembler.label();
708
709     Assembler::JumpList tagMatchingLocalFailureCases;
710     generateElementMatching(tagMatchingLocalFailureCases, fragment);
711     tagMatchingLocalFailureCases.linkTo(loopStart, &m_assembler);
712 }
713
714 void SelectorCodeGenerator::generateWalkToPreviousAdjacent(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
715 {
716     //    do {
717     //        previousSibling = previousSibling->previousSibling();
718     //        if (!previousSibling)
719     //            failure!
720     //    while (!previousSibling->isElement());
721     Assembler::RegisterID previousSibling;
722     bool useTailOnTraversalFailure = fragment.traversalBacktrackingAction >= BacktrackingAction::JumpToDescendantTail;
723     if (!useTailOnTraversalFailure) {
724         // If the current fragment is not dependant on a previously saved elementAddressRegister, a fast recover
725         // from a failure would resume with elementAddressRegister.
726         // When walking to the previous sibling, the failure can be that previousSibling is null. We cannot backtrack
727         // with a null elementAddressRegister so we do the traversal on a copy.
728         previousSibling = m_registerAllocator.allocateRegister();
729         m_assembler.move(elementAddressRegister, previousSibling);
730     } else
731         previousSibling = elementAddressRegister;
732
733     Assembler::Label loopStart = m_assembler.label();
734     m_assembler.loadPtr(Assembler::Address(previousSibling, Node::previousSiblingMemoryOffset()), previousSibling);
735     failureCases.append(m_assembler.branchTestPtr(Assembler::Zero, previousSibling));
736     testIsElementFlagOnNode(Assembler::Zero, m_assembler, previousSibling).linkTo(loopStart, &m_assembler);
737
738     // On success, move previousSibling over to elementAddressRegister if we could not work on elementAddressRegister directly.
739     if (!useTailOnTraversalFailure) {
740         m_assembler.move(previousSibling, elementAddressRegister);
741         m_registerAllocator.deallocateRegister(previousSibling);
742     }
743 }
744
745 void SelectorCodeGenerator::generateDirectAdjacentTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
746 {
747     markParentElementIfResolvingStyle(Element::setChildrenAffectedByDirectAdjacentRules);
748
749     Assembler::JumpList traversalFailureCases;
750     generateWalkToPreviousAdjacent(traversalFailureCases, fragment);
751     linkFailures(failureCases, fragment.traversalBacktrackingAction, traversalFailureCases);
752
753     Assembler::JumpList matchingFailureCases;
754     generateElementMatching(matchingFailureCases, fragment);
755     linkFailures(failureCases, fragment.matchingBacktrackingAction, matchingFailureCases);
756
757     if (fragment.backtrackingFlags & BacktrackingFlag::SaveAdjacentBacktrackingStart)
758         m_adjacentBacktrackingStart = m_stackAllocator.push(elementAddressRegister);
759 }
760
761 void SelectorCodeGenerator::generateIndirectAdjacentTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
762 {
763     markParentElementIfResolvingStyle(Element::setChildrenAffectedByForwardPositionalRules);
764
765     Assembler::Label loopStart(m_assembler.label());
766
767     Assembler::JumpList traversalFailureCases;
768     generateWalkToPreviousAdjacent(traversalFailureCases, fragment);
769     linkFailures(failureCases, fragment.traversalBacktrackingAction, traversalFailureCases);
770
771     if (fragment.backtrackingFlags & BacktrackingFlag::IndirectAdjacentEntryPoint)
772         m_indirectAdjacentEntryPoint = m_assembler.label();
773
774     Assembler::JumpList localFailureCases;
775     generateElementMatching(localFailureCases, fragment);
776     localFailureCases.linkTo(loopStart, &m_assembler);
777 }
778
779 void SelectorCodeGenerator::markParentElementIfResolvingStyle(JSC::FunctionPtr markingFunction)
780 {
781     //     if (checkingContext.resolvingMode == ResolvingStyle) {
782     //         Element* parent = element->parentNode();
783     //         markingFunction(parent);
784     //     }
785     Assembler::JumpList failedToGetParent;
786     Assembler::Jump notResolvingStyle;
787     {
788         // Get the checking context.
789         unsigned offsetToCheckingContext = m_stackAllocator.offsetToStackReference(m_checkingContextStackReference);
790         LocalRegister checkingContext(m_registerAllocator);
791         m_assembler.loadPtr(Assembler::Address(Assembler::stackPointerRegister, offsetToCheckingContext), checkingContext);
792
793         // If we not resolving style, skip the whole marking.
794         notResolvingStyle = m_assembler.branch8(Assembler::NotEqual, Assembler::Address(checkingContext, OBJECT_OFFSETOF(CheckingContext, resolvingMode)), Assembler::TrustedImm32(SelectorChecker::ResolvingStyle));
795     }
796
797     // Get the parent element in a temporary register.
798     Assembler::RegisterID parentElement = m_registerAllocator.allocateRegister();
799     generateWalkToParentElement(failedToGetParent, parentElement);
800
801     // Return the register parentElement just before the function call since we don't need it to be preserved
802     // on the stack.
803     m_registerAllocator.deallocateRegister(parentElement);
804
805     // Invoke the marking function on the parent element.
806     FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
807     functionCall.setFunctionAddress(markingFunction);
808     functionCall.setFirstArgument(parentElement);
809     functionCall.call();
810
811     notResolvingStyle.link(&m_assembler);
812     failedToGetParent.link(&m_assembler);
813 }
814
815
816 void SelectorCodeGenerator::linkFailures(Assembler::JumpList& globalFailureCases, BacktrackingAction backtrackingAction, Assembler::JumpList& localFailureCases)
817 {
818     switch (backtrackingAction) {
819     case BacktrackingAction::NoBacktracking:
820         globalFailureCases.append(localFailureCases);
821         break;
822     case BacktrackingAction::JumpToDescendantEntryPoint:
823         localFailureCases.linkTo(m_descendantEntryPoint, &m_assembler);
824         break;
825     case BacktrackingAction::JumpToDescendantTreeWalkerEntryPoint:
826         localFailureCases.linkTo(m_descendantTreeWalkerBacktrackingPoint, &m_assembler);
827         break;
828     case BacktrackingAction::JumpToDescendantTail:
829         m_descendantBacktrackingFailureCases.append(localFailureCases);
830         break;
831     case BacktrackingAction::JumpToIndirectAdjacentEntryPoint:
832         localFailureCases.linkTo(m_indirectAdjacentEntryPoint, &m_assembler);
833         break;
834     case BacktrackingAction::JumpToDirectAdjacentTail:
835         m_adjacentBacktrackingFailureCases.append(localFailureCases);
836         break;
837     case BacktrackingAction::JumpToClearAdjacentDescendantTail:
838         m_clearAdjacentEntryPointDescendantFailureCases.append(localFailureCases);
839         break;
840     }
841 }
842
843 void SelectorCodeGenerator::generateAdjacentBacktrackingTail(StackAllocator& adjacentTailStack)
844 {
845     m_adjacentBacktrackingFailureCases.link(&m_assembler);
846     m_adjacentBacktrackingFailureCases.clear();
847     adjacentTailStack.pop(m_adjacentBacktrackingStart, elementAddressRegister);
848     m_assembler.jump(m_indirectAdjacentEntryPoint);
849 }
850
851 void SelectorCodeGenerator::generateDescendantBacktrackingTail()
852 {
853     m_descendantBacktrackingFailureCases.link(&m_assembler);
854     m_descendantBacktrackingFailureCases.clear();
855     m_assembler.move(m_descendantBacktrackingStart, elementAddressRegister);
856     m_registerAllocator.deallocateRegister(m_descendantBacktrackingStart);
857     m_assembler.jump(m_descendantEntryPoint);
858 }
859
860 void SelectorCodeGenerator::generateBacktrackingTailsIfNeeded(const SelectorFragment& fragment)
861 {
862     if (fragment.backtrackingFlags & BacktrackingFlag::DirectAdjacentTail && fragment.backtrackingFlags & BacktrackingFlag::DescendantTail) {
863         StackAllocator successStack = m_stackAllocator;
864         StackAllocator adjacentTailStack = m_stackAllocator;
865         StackAllocator descendantTailStack = m_stackAllocator;
866
867         successStack.popAndDiscard(m_adjacentBacktrackingStart);
868
869         Assembler::Jump normalCase = m_assembler.jump();
870
871         generateAdjacentBacktrackingTail(adjacentTailStack);
872
873         m_clearAdjacentEntryPointDescendantFailureCases.link(&m_assembler);
874         m_clearAdjacentEntryPointDescendantFailureCases.clear();
875         descendantTailStack.popAndDiscard(m_adjacentBacktrackingStart);
876
877         generateDescendantBacktrackingTail();
878
879         normalCase.link(&m_assembler);
880
881         m_stackAllocator.merge(std::move(successStack), std::move(adjacentTailStack), std::move(descendantTailStack));
882     } else if (fragment.backtrackingFlags & BacktrackingFlag::DirectAdjacentTail) {
883         StackAllocator successStack = m_stackAllocator;
884         StackAllocator adjacentTailStack = m_stackAllocator;
885
886         successStack.popAndDiscard(m_adjacentBacktrackingStart);
887
888         Assembler::Jump normalCase = m_assembler.jump();
889         generateAdjacentBacktrackingTail(adjacentTailStack);
890         normalCase.link(&m_assembler);
891
892         m_stackAllocator.merge(std::move(successStack), std::move(adjacentTailStack));
893     } else if (fragment.backtrackingFlags & BacktrackingFlag::DescendantTail) {
894         Assembler::Jump normalCase = m_assembler.jump();
895         generateDescendantBacktrackingTail();
896         normalCase.link(&m_assembler);
897     }
898 }
899
900 void SelectorCodeGenerator::generateElementMatching(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
901 {
902     if (fragment.pseudoClasses.contains(CSSSelector::PseudoLink))
903         generateElementIsLink(failureCases);
904
905     if (fragment.tagName)
906         generateElementHasTagName(failureCases, *(fragment.tagName));
907
908     for (unsigned i = 0; i < fragment.unoptimizedPseudoClasses.size(); ++i)
909         generateElementFunctionCallTest(failureCases, fragment.unoptimizedPseudoClasses[i]);
910
911     generateElementDataMatching(failureCases, fragment);
912 }
913
914 void SelectorCodeGenerator::generateElementDataMatching(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
915 {
916     if (!fragment.id && fragment.classNames.isEmpty() && fragment.attributes.isEmpty())
917         return;
918
919     //  Generate:
920     //     elementDataAddress = element->elementData();
921     //     if (!elementDataAddress)
922     //         failure!
923     LocalRegister elementDataAddress(m_registerAllocator);
924     m_assembler.loadPtr(Assembler::Address(elementAddressRegister, Element::elementDataMemoryOffset()), elementDataAddress);
925     failureCases.append(m_assembler.branchTestPtr(Assembler::Zero, elementDataAddress));
926
927     if (fragment.id)
928         generateElementHasId(failureCases, elementDataAddress, *fragment.id);
929     if (!fragment.classNames.isEmpty())
930         generateElementHasClasses(failureCases, elementDataAddress, fragment.classNames);
931     if (!fragment.attributes.isEmpty())
932     generateElementAttributesMatching(failureCases, elementDataAddress, fragment);
933 }
934
935 static inline Assembler::Jump testIsHTMLFlagOnNode(Assembler::ResultCondition condition, Assembler& assembler, Assembler::RegisterID nodeAddress)
936 {
937     return assembler.branchTest32(condition, Assembler::Address(nodeAddress, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagIsHTML()));
938 }
939
940 static inline bool canMatchStyleAttribute(const SelectorFragment& fragment)
941 {
942     for (unsigned i = 0; i < fragment.attributes.size(); ++i) {
943         const CSSSelector* attributeSelector = fragment.attributes[i];
944         const QualifiedName& attributeName = attributeSelector->attribute();
945         if (Attribute::nameMatchesFilter(HTMLNames::styleAttr, attributeName.prefix(), attributeName.localName(), attributeName.namespaceURI())
946             || Attribute::nameMatchesFilter(HTMLNames::styleAttr, attributeName.prefix(), attributeSelector->attributeCanonicalLocalName(), attributeName.namespaceURI())) {
947             return true;
948         }
949     }
950     return false;
951 }
952
953 void SelectorCodeGenerator::generateSynchronizeStyleAttribute(Assembler::RegisterID elementDataArraySizeAndFlags)
954 {
955     // The style attribute is updated lazily based on the flag styleAttributeIsDirty.
956     Assembler::Jump styleAttributeNotDirty = m_assembler.branchTest32(Assembler::Zero, elementDataArraySizeAndFlags, Assembler::TrustedImm32(ElementData::styleAttributeIsDirtyFlag()));
957
958     FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
959     functionCall.setFunctionAddress(StyledElement::synchronizeStyleAttributeInternal);
960     Assembler::RegisterID elementAddress = elementAddressRegister;
961     functionCall.setFirstArgument(elementAddress);
962     functionCall.call();
963
964     styleAttributeNotDirty.link(&m_assembler);
965 }
966
967 void SelectorCodeGenerator::generateSynchronizeAllAnimatedSVGAttribute(Assembler::RegisterID elementDataArraySizeAndFlags)
968 {
969     // SVG attributes can be updated lazily depending on the flag AnimatedSVGAttributesAreDirty. We need to check
970     // that first.
971     Assembler::Jump animatedSVGAttributesNotDirty = m_assembler.branchTest32(Assembler::Zero, elementDataArraySizeAndFlags, Assembler::TrustedImm32(ElementData::animatedSVGAttributesAreDirtyFlag()));
972
973     FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
974     functionCall.setFunctionAddress(SVGElement::synchronizeAllAnimatedSVGAttribute);
975     Assembler::RegisterID elementAddress = elementAddressRegister;
976     functionCall.setFirstArgument(elementAddress);
977     functionCall.call();
978
979     animatedSVGAttributesNotDirty.link(&m_assembler);
980 }
981
982 void SelectorCodeGenerator::generateElementAttributesMatching(Assembler::JumpList& failureCases, const LocalRegister& elementDataAddress, const SelectorFragment& fragment)
983 {
984     LocalRegister scratchRegister(m_registerAllocator);
985     Assembler::RegisterID elementDataArraySizeAndFlags = scratchRegister;
986     Assembler::RegisterID attributeArrayLength = scratchRegister;
987
988     m_assembler.load32(Assembler::Address(elementDataAddress, ElementData::arraySizeAndFlagsMemoryOffset()), elementDataArraySizeAndFlags);
989
990     if (canMatchStyleAttribute(fragment))
991         generateSynchronizeStyleAttribute(elementDataArraySizeAndFlags);
992
993     // FIXME: Systematically generating the function call for animatable SVG attributes causes a runtime penaltly. We should instead
994     // filter from the list of SVGElement::isAnimatableAttribute at runtime when compiling.
995     generateSynchronizeAllAnimatedSVGAttribute(elementDataArraySizeAndFlags);
996
997     // Attributes can be stored either in a separate vector for UniqueElementData, or after the elementData itself
998     // for ShareableElementData.
999     LocalRegister attributeArrayPointer(m_registerAllocator);
1000     Assembler::Jump isShareableElementData  = m_assembler.branchTest32(Assembler::Zero, elementDataArraySizeAndFlags, Assembler::TrustedImm32(ElementData::isUniqueFlag()));
1001     {
1002         ptrdiff_t attributeVectorOffset = UniqueElementData::attributeVectorMemoryOffset();
1003         m_assembler.loadPtr(Assembler::Address(elementDataAddress, attributeVectorOffset + UniqueElementData::AttributeVector::dataMemoryOffset()), attributeArrayPointer);
1004         m_assembler.load32(Assembler::Address(elementDataAddress, attributeVectorOffset + UniqueElementData::AttributeVector::sizeMemoryOffset()), attributeArrayLength);
1005     }
1006     Assembler::Jump skipShareable = m_assembler.jump();
1007
1008     {
1009         isShareableElementData.link(&m_assembler);
1010         m_assembler.urshift32(elementDataArraySizeAndFlags, Assembler::TrustedImm32(ElementData::arraySizeOffset()), attributeArrayLength);
1011         m_assembler.add64(Assembler::TrustedImm32(ShareableElementData::attributeArrayMemoryOffset()), elementDataAddress, attributeArrayPointer);
1012     }
1013
1014     skipShareable.link(&m_assembler);
1015
1016     // If there are no attributes, fail immediately.
1017     failureCases.append(m_assembler.branchTest32(Assembler::Zero, attributeArrayLength));
1018
1019     unsigned attributeCount = fragment.attributes.size();
1020     for (unsigned i = 0; i < attributeCount; ++i) {
1021         Assembler::RegisterID decIndexRegister;
1022         Assembler::RegisterID currentAttributeAddress;
1023
1024         bool isLastAttribute = i == (attributeCount - 1);
1025         if (!isLastAttribute) {
1026             // We need to make a copy to let the next iterations use the values.
1027             currentAttributeAddress = m_registerAllocator.allocateRegister();
1028             decIndexRegister = m_registerAllocator.allocateRegister();
1029             m_assembler.move(attributeArrayPointer, currentAttributeAddress);
1030             m_assembler.move(attributeArrayLength, decIndexRegister);
1031         } else {
1032             currentAttributeAddress = attributeArrayPointer;
1033             decIndexRegister = attributeArrayLength;
1034         }
1035
1036         generateElementAttributeMatching(failureCases, currentAttributeAddress, decIndexRegister, fragment.attributes[i]);
1037
1038         if (!isLastAttribute) {
1039             m_registerAllocator.deallocateRegister(decIndexRegister);
1040             m_registerAllocator.deallocateRegister(currentAttributeAddress);
1041         }
1042     }
1043 }
1044
1045 void SelectorCodeGenerator::generateElementAttributeMatching(Assembler::JumpList& failureCases, Assembler::RegisterID currentAttributeAddress, Assembler::RegisterID decIndexRegister, const CSSSelector* attributeSelector)
1046 {
1047     // Get the localName used for comparison. HTML elements use a lowercase local name known in selectors as canonicalLocalName.
1048     LocalRegister localNameToMatch(m_registerAllocator);
1049
1050     // In general, canonicalLocalName and localName are the same. When they differ, we have to check if the node is HTML to know
1051     // which one to use.
1052     const AtomicStringImpl* canonicalLocalName = attributeSelector->attributeCanonicalLocalName().impl();
1053     const AtomicStringImpl* localName = attributeSelector->attribute().localName().impl();
1054     if (canonicalLocalName == localName)
1055         m_assembler.move(Assembler::TrustedImmPtr(canonicalLocalName), localNameToMatch);
1056     else {
1057         m_assembler.move(Assembler::TrustedImmPtr(canonicalLocalName), localNameToMatch);
1058         Assembler::Jump elementIsHTML = testIsHTMLFlagOnNode(Assembler::NonZero, m_assembler, elementAddressRegister);
1059         m_assembler.move(Assembler::TrustedImmPtr(localName), localNameToMatch);
1060         elementIsHTML.link(&m_assembler);
1061     }
1062
1063     Assembler::JumpList successCases;
1064     Assembler::Label loopStart(m_assembler.label());
1065
1066     LocalRegister qualifiedNameImpl(m_registerAllocator);
1067     m_assembler.loadPtr(Assembler::Address(currentAttributeAddress, Attribute::nameMemoryOffset()), qualifiedNameImpl);
1068
1069     bool shouldCheckNamespace = attributeSelector->attribute().prefix() != starAtom;
1070     if (shouldCheckNamespace) {
1071         Assembler::Jump nameDoesNotMatch = m_assembler.branchPtr(Assembler::NotEqual, Assembler::Address(qualifiedNameImpl, QualifiedName::QualifiedNameImpl::localNameMemoryOffset()), localNameToMatch);
1072
1073         const AtomicStringImpl* namespaceURI = attributeSelector->attribute().namespaceURI().impl();
1074         if (namespaceURI) {
1075             LocalRegister namespaceToMatch(m_registerAllocator);
1076             m_assembler.move(Assembler::TrustedImmPtr(namespaceURI), namespaceToMatch);
1077             successCases.append(m_assembler.branchPtr(Assembler::Equal, Assembler::Address(qualifiedNameImpl, QualifiedName::QualifiedNameImpl::namespaceMemoryOffset()), namespaceToMatch));
1078         } else
1079             successCases.append(m_assembler.branchTestPtr(Assembler::Zero, Assembler::Address(qualifiedNameImpl, QualifiedName::QualifiedNameImpl::namespaceMemoryOffset())));
1080         nameDoesNotMatch.link(&m_assembler);
1081     } else
1082         successCases.append(m_assembler.branchPtr(Assembler::Equal, Assembler::Address(qualifiedNameImpl, QualifiedName::QualifiedNameImpl::localNameMemoryOffset()), localNameToMatch));
1083
1084     // If we reached the last element -> failure.
1085     failureCases.append(m_assembler.branchSub32(Assembler::Zero, Assembler::TrustedImm32(1), decIndexRegister));
1086
1087     // Otherwise just loop over.
1088     m_assembler.addPtr(Assembler::TrustedImm32(sizeof(Attribute)), currentAttributeAddress);
1089     m_assembler.jump().linkTo(loopStart, &m_assembler);
1090     successCases.link(&m_assembler);
1091 }
1092
1093 void SelectorCodeGenerator::generateElementFunctionCallTest(Assembler::JumpList& failureCases, JSC::FunctionPtr testFunction)
1094 {
1095     Assembler::RegisterID elementAddress = elementAddressRegister;
1096     FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
1097     functionCall.setFunctionAddress(testFunction);
1098     functionCall.setFirstArgument(elementAddress);
1099     failureCases.append(functionCall.callAndBranchOnCondition(Assembler::Zero));
1100 }
1101
1102 inline void SelectorCodeGenerator::generateElementHasTagName(Assembler::JumpList& failureCases, const QualifiedName& nameToMatch)
1103 {
1104     if (nameToMatch == anyQName())
1105         return;
1106
1107     // Load the QualifiedNameImpl from the input.
1108     LocalRegister qualifiedNameImpl(m_registerAllocator);
1109     m_assembler.loadPtr(Assembler::Address(elementAddressRegister, Element::tagQNameMemoryOffset() + QualifiedName::implMemoryOffset()), qualifiedNameImpl);
1110
1111     const AtomicString& selectorLocalName = nameToMatch.localName();
1112     if (selectorLocalName != starAtom) {
1113         // Generate localName == element->localName().
1114         LocalRegister constantRegister(m_registerAllocator);
1115         m_assembler.move(Assembler::TrustedImmPtr(selectorLocalName.impl()), constantRegister);
1116         failureCases.append(m_assembler.branchPtr(Assembler::NotEqual, Assembler::Address(qualifiedNameImpl, QualifiedName::QualifiedNameImpl::localNameMemoryOffset()), constantRegister));
1117     }
1118
1119     const AtomicString& selectorNamespaceURI = nameToMatch.namespaceURI();
1120     if (selectorNamespaceURI != starAtom) {
1121         // Generate namespaceURI == element->namespaceURI().
1122         LocalRegister constantRegister(m_registerAllocator);
1123         m_assembler.move(Assembler::TrustedImmPtr(selectorNamespaceURI.impl()), constantRegister);
1124         failureCases.append(m_assembler.branchPtr(Assembler::NotEqual, Assembler::Address(qualifiedNameImpl, QualifiedName::QualifiedNameImpl::namespaceMemoryOffset()), constantRegister));
1125     }
1126 }
1127
1128 void SelectorCodeGenerator::generateElementHasId(Assembler::JumpList& failureCases, const LocalRegister& elementDataAddress, const AtomicString& idToMatch)
1129 {
1130     // Compare the pointers of the AtomicStringImpl from idForStyleResolution with the reference idToMatch.
1131     LocalRegister idToMatchRegister(m_registerAllocator);
1132     m_assembler.move(Assembler::TrustedImmPtr(idToMatch.impl()), idToMatchRegister);
1133     failureCases.append(m_assembler.branchPtr(Assembler::NotEqual, Assembler::Address(elementDataAddress, ElementData::idForStyleResolutionMemoryOffset()), idToMatchRegister));
1134 }
1135
1136 void SelectorCodeGenerator::generateElementHasClasses(Assembler::JumpList& failureCases, const LocalRegister& elementDataAddress, const Vector<const AtomicStringImpl*>& classNames)
1137 {
1138     // Load m_classNames.
1139     LocalRegister spaceSplitStringData(m_registerAllocator);
1140     m_assembler.loadPtr(Assembler::Address(elementDataAddress, ElementData::classNamesMemoryOffset()), spaceSplitStringData);
1141
1142     // If SpaceSplitString does not have a SpaceSplitStringData pointer, it is empty -> failure case.
1143     failureCases.append(m_assembler.branchTestPtr(Assembler::Zero, spaceSplitStringData));
1144
1145     // We loop over the classes of SpaceSplitStringData for each class name we need to match.
1146     LocalRegister indexRegister(m_registerAllocator);
1147     for (unsigned i = 0; i < classNames.size(); ++i) {
1148         LocalRegister classNameToMatch(m_registerAllocator);
1149         m_assembler.move(Assembler::TrustedImmPtr(classNames[i]), classNameToMatch);
1150         m_assembler.move(Assembler::TrustedImm32(0), indexRegister);
1151
1152         // Beginning of a loop over all the class name of element to find the one we are looking for.
1153         Assembler::Label loopStart(m_assembler.label());
1154
1155         // If the pointers match, proceed to the next matcher.
1156         Assembler::Jump classFound = m_assembler.branchPtr(Assembler::Equal, Assembler::BaseIndex(spaceSplitStringData, indexRegister, Assembler::timesPtr(), SpaceSplitStringData::tokensMemoryOffset()), classNameToMatch);
1157
1158         // Increment the index.
1159         m_assembler.add32(Assembler::TrustedImm32(1), indexRegister);
1160
1161         // If we reached the last element -> failure.
1162         failureCases.append(m_assembler.branch32(Assembler::Equal, Assembler::Address(spaceSplitStringData, SpaceSplitStringData::sizeMemoryOffset()), indexRegister));
1163         // Otherwise just loop over.
1164         m_assembler.jump().linkTo(loopStart, &m_assembler);
1165
1166         // Success case.
1167         classFound.link(&m_assembler);
1168     }
1169 }
1170
1171 void SelectorCodeGenerator::generateElementIsLink(Assembler::JumpList& failureCases)
1172 {
1173     failureCases.append(m_assembler.branchTest32(Assembler::Zero, Assembler::Address(elementAddressRegister, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagIsLink())));
1174 }
1175
1176 }; // namespace SelectorCompiler.
1177 }; // namespace WebCore.
1178
1179 #endif // ENABLE(CSS_SELECTOR_JIT)