Do not attempt to synchronize attributes when no Simple Selector could match an anima...
[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             return true;
947
948         const AtomicString& canonicalLocalName = attributeSelector->attributeCanonicalLocalName();
949         if (attributeName.localName() != canonicalLocalName
950             && Attribute::nameMatchesFilter(HTMLNames::styleAttr, attributeName.prefix(), attributeSelector->attributeCanonicalLocalName(), attributeName.namespaceURI())) {
951             return true;
952         }
953     }
954     return false;
955 }
956
957 void SelectorCodeGenerator::generateSynchronizeStyleAttribute(Assembler::RegisterID elementDataArraySizeAndFlags)
958 {
959     // The style attribute is updated lazily based on the flag styleAttributeIsDirty.
960     Assembler::Jump styleAttributeNotDirty = m_assembler.branchTest32(Assembler::Zero, elementDataArraySizeAndFlags, Assembler::TrustedImm32(ElementData::styleAttributeIsDirtyFlag()));
961
962     FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
963     functionCall.setFunctionAddress(StyledElement::synchronizeStyleAttributeInternal);
964     Assembler::RegisterID elementAddress = elementAddressRegister;
965     functionCall.setFirstArgument(elementAddress);
966     functionCall.call();
967
968     styleAttributeNotDirty.link(&m_assembler);
969 }
970
971 static inline bool canMatchAnimatableSVGAttribute(const SelectorFragment& fragment)
972 {
973     for (unsigned i = 0; i < fragment.attributes.size(); ++i) {
974         const CSSSelector* attributeSelector = fragment.attributes[i];
975         const QualifiedName& selectorAttributeName = attributeSelector->attribute();
976
977         const QualifiedName& candidateForLocalName = SVGElement::animatableAttributeForName(selectorAttributeName.localName());
978         if (Attribute::nameMatchesFilter(candidateForLocalName, selectorAttributeName.prefix(), selectorAttributeName.localName(), selectorAttributeName.namespaceURI()))
979             return true;
980
981         const AtomicString& canonicalLocalName = attributeSelector->attributeCanonicalLocalName();
982         if (selectorAttributeName.localName() != canonicalLocalName) {
983             const QualifiedName& candidateForCanonicalLocalName = SVGElement::animatableAttributeForName(selectorAttributeName.localName());
984             if (Attribute::nameMatchesFilter(candidateForCanonicalLocalName, selectorAttributeName.prefix(), selectorAttributeName.localName(), selectorAttributeName.namespaceURI()))
985                 return true;
986         }
987     }
988     return false;
989 }
990
991 void SelectorCodeGenerator::generateSynchronizeAllAnimatedSVGAttribute(Assembler::RegisterID elementDataArraySizeAndFlags)
992 {
993     // SVG attributes can be updated lazily depending on the flag AnimatedSVGAttributesAreDirty. We need to check
994     // that first.
995     Assembler::Jump animatedSVGAttributesNotDirty = m_assembler.branchTest32(Assembler::Zero, elementDataArraySizeAndFlags, Assembler::TrustedImm32(ElementData::animatedSVGAttributesAreDirtyFlag()));
996
997     FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
998     functionCall.setFunctionAddress(SVGElement::synchronizeAllAnimatedSVGAttribute);
999     Assembler::RegisterID elementAddress = elementAddressRegister;
1000     functionCall.setFirstArgument(elementAddress);
1001     functionCall.call();
1002
1003     animatedSVGAttributesNotDirty.link(&m_assembler);
1004 }
1005
1006 void SelectorCodeGenerator::generateElementAttributesMatching(Assembler::JumpList& failureCases, const LocalRegister& elementDataAddress, const SelectorFragment& fragment)
1007 {
1008     LocalRegister scratchRegister(m_registerAllocator);
1009     Assembler::RegisterID elementDataArraySizeAndFlags = scratchRegister;
1010     Assembler::RegisterID attributeArrayLength = scratchRegister;
1011
1012     m_assembler.load32(Assembler::Address(elementDataAddress, ElementData::arraySizeAndFlagsMemoryOffset()), elementDataArraySizeAndFlags);
1013
1014     if (canMatchStyleAttribute(fragment))
1015         generateSynchronizeStyleAttribute(elementDataArraySizeAndFlags);
1016
1017     if (canMatchAnimatableSVGAttribute(fragment))
1018         generateSynchronizeAllAnimatedSVGAttribute(elementDataArraySizeAndFlags);
1019
1020     // Attributes can be stored either in a separate vector for UniqueElementData, or after the elementData itself
1021     // for ShareableElementData.
1022     LocalRegister attributeArrayPointer(m_registerAllocator);
1023     Assembler::Jump isShareableElementData  = m_assembler.branchTest32(Assembler::Zero, elementDataArraySizeAndFlags, Assembler::TrustedImm32(ElementData::isUniqueFlag()));
1024     {
1025         ptrdiff_t attributeVectorOffset = UniqueElementData::attributeVectorMemoryOffset();
1026         m_assembler.loadPtr(Assembler::Address(elementDataAddress, attributeVectorOffset + UniqueElementData::AttributeVector::dataMemoryOffset()), attributeArrayPointer);
1027         m_assembler.load32(Assembler::Address(elementDataAddress, attributeVectorOffset + UniqueElementData::AttributeVector::sizeMemoryOffset()), attributeArrayLength);
1028     }
1029     Assembler::Jump skipShareable = m_assembler.jump();
1030
1031     {
1032         isShareableElementData.link(&m_assembler);
1033         m_assembler.urshift32(elementDataArraySizeAndFlags, Assembler::TrustedImm32(ElementData::arraySizeOffset()), attributeArrayLength);
1034         m_assembler.add64(Assembler::TrustedImm32(ShareableElementData::attributeArrayMemoryOffset()), elementDataAddress, attributeArrayPointer);
1035     }
1036
1037     skipShareable.link(&m_assembler);
1038
1039     // If there are no attributes, fail immediately.
1040     failureCases.append(m_assembler.branchTest32(Assembler::Zero, attributeArrayLength));
1041
1042     unsigned attributeCount = fragment.attributes.size();
1043     for (unsigned i = 0; i < attributeCount; ++i) {
1044         Assembler::RegisterID decIndexRegister;
1045         Assembler::RegisterID currentAttributeAddress;
1046
1047         bool isLastAttribute = i == (attributeCount - 1);
1048         if (!isLastAttribute) {
1049             // We need to make a copy to let the next iterations use the values.
1050             currentAttributeAddress = m_registerAllocator.allocateRegister();
1051             decIndexRegister = m_registerAllocator.allocateRegister();
1052             m_assembler.move(attributeArrayPointer, currentAttributeAddress);
1053             m_assembler.move(attributeArrayLength, decIndexRegister);
1054         } else {
1055             currentAttributeAddress = attributeArrayPointer;
1056             decIndexRegister = attributeArrayLength;
1057         }
1058
1059         generateElementAttributeMatching(failureCases, currentAttributeAddress, decIndexRegister, fragment.attributes[i]);
1060
1061         if (!isLastAttribute) {
1062             m_registerAllocator.deallocateRegister(decIndexRegister);
1063             m_registerAllocator.deallocateRegister(currentAttributeAddress);
1064         }
1065     }
1066 }
1067
1068 void SelectorCodeGenerator::generateElementAttributeMatching(Assembler::JumpList& failureCases, Assembler::RegisterID currentAttributeAddress, Assembler::RegisterID decIndexRegister, const CSSSelector* attributeSelector)
1069 {
1070     // Get the localName used for comparison. HTML elements use a lowercase local name known in selectors as canonicalLocalName.
1071     LocalRegister localNameToMatch(m_registerAllocator);
1072
1073     // In general, canonicalLocalName and localName are the same. When they differ, we have to check if the node is HTML to know
1074     // which one to use.
1075     const AtomicStringImpl* canonicalLocalName = attributeSelector->attributeCanonicalLocalName().impl();
1076     const AtomicStringImpl* localName = attributeSelector->attribute().localName().impl();
1077     if (canonicalLocalName == localName)
1078         m_assembler.move(Assembler::TrustedImmPtr(canonicalLocalName), localNameToMatch);
1079     else {
1080         m_assembler.move(Assembler::TrustedImmPtr(canonicalLocalName), localNameToMatch);
1081         Assembler::Jump elementIsHTML = testIsHTMLFlagOnNode(Assembler::NonZero, m_assembler, elementAddressRegister);
1082         m_assembler.move(Assembler::TrustedImmPtr(localName), localNameToMatch);
1083         elementIsHTML.link(&m_assembler);
1084     }
1085
1086     Assembler::JumpList successCases;
1087     Assembler::Label loopStart(m_assembler.label());
1088
1089     LocalRegister qualifiedNameImpl(m_registerAllocator);
1090     m_assembler.loadPtr(Assembler::Address(currentAttributeAddress, Attribute::nameMemoryOffset()), qualifiedNameImpl);
1091
1092     bool shouldCheckNamespace = attributeSelector->attribute().prefix() != starAtom;
1093     if (shouldCheckNamespace) {
1094         Assembler::Jump nameDoesNotMatch = m_assembler.branchPtr(Assembler::NotEqual, Assembler::Address(qualifiedNameImpl, QualifiedName::QualifiedNameImpl::localNameMemoryOffset()), localNameToMatch);
1095
1096         const AtomicStringImpl* namespaceURI = attributeSelector->attribute().namespaceURI().impl();
1097         if (namespaceURI) {
1098             LocalRegister namespaceToMatch(m_registerAllocator);
1099             m_assembler.move(Assembler::TrustedImmPtr(namespaceURI), namespaceToMatch);
1100             successCases.append(m_assembler.branchPtr(Assembler::Equal, Assembler::Address(qualifiedNameImpl, QualifiedName::QualifiedNameImpl::namespaceMemoryOffset()), namespaceToMatch));
1101         } else
1102             successCases.append(m_assembler.branchTestPtr(Assembler::Zero, Assembler::Address(qualifiedNameImpl, QualifiedName::QualifiedNameImpl::namespaceMemoryOffset())));
1103         nameDoesNotMatch.link(&m_assembler);
1104     } else
1105         successCases.append(m_assembler.branchPtr(Assembler::Equal, Assembler::Address(qualifiedNameImpl, QualifiedName::QualifiedNameImpl::localNameMemoryOffset()), localNameToMatch));
1106
1107     // If we reached the last element -> failure.
1108     failureCases.append(m_assembler.branchSub32(Assembler::Zero, Assembler::TrustedImm32(1), decIndexRegister));
1109
1110     // Otherwise just loop over.
1111     m_assembler.addPtr(Assembler::TrustedImm32(sizeof(Attribute)), currentAttributeAddress);
1112     m_assembler.jump().linkTo(loopStart, &m_assembler);
1113     successCases.link(&m_assembler);
1114 }
1115
1116 void SelectorCodeGenerator::generateElementFunctionCallTest(Assembler::JumpList& failureCases, JSC::FunctionPtr testFunction)
1117 {
1118     Assembler::RegisterID elementAddress = elementAddressRegister;
1119     FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
1120     functionCall.setFunctionAddress(testFunction);
1121     functionCall.setFirstArgument(elementAddress);
1122     failureCases.append(functionCall.callAndBranchOnCondition(Assembler::Zero));
1123 }
1124
1125 inline void SelectorCodeGenerator::generateElementHasTagName(Assembler::JumpList& failureCases, const QualifiedName& nameToMatch)
1126 {
1127     if (nameToMatch == anyQName())
1128         return;
1129
1130     // Load the QualifiedNameImpl from the input.
1131     LocalRegister qualifiedNameImpl(m_registerAllocator);
1132     m_assembler.loadPtr(Assembler::Address(elementAddressRegister, Element::tagQNameMemoryOffset() + QualifiedName::implMemoryOffset()), qualifiedNameImpl);
1133
1134     const AtomicString& selectorLocalName = nameToMatch.localName();
1135     if (selectorLocalName != starAtom) {
1136         // Generate localName == element->localName().
1137         LocalRegister constantRegister(m_registerAllocator);
1138         m_assembler.move(Assembler::TrustedImmPtr(selectorLocalName.impl()), constantRegister);
1139         failureCases.append(m_assembler.branchPtr(Assembler::NotEqual, Assembler::Address(qualifiedNameImpl, QualifiedName::QualifiedNameImpl::localNameMemoryOffset()), constantRegister));
1140     }
1141
1142     const AtomicString& selectorNamespaceURI = nameToMatch.namespaceURI();
1143     if (selectorNamespaceURI != starAtom) {
1144         // Generate namespaceURI == element->namespaceURI().
1145         LocalRegister constantRegister(m_registerAllocator);
1146         m_assembler.move(Assembler::TrustedImmPtr(selectorNamespaceURI.impl()), constantRegister);
1147         failureCases.append(m_assembler.branchPtr(Assembler::NotEqual, Assembler::Address(qualifiedNameImpl, QualifiedName::QualifiedNameImpl::namespaceMemoryOffset()), constantRegister));
1148     }
1149 }
1150
1151 void SelectorCodeGenerator::generateElementHasId(Assembler::JumpList& failureCases, const LocalRegister& elementDataAddress, const AtomicString& idToMatch)
1152 {
1153     // Compare the pointers of the AtomicStringImpl from idForStyleResolution with the reference idToMatch.
1154     LocalRegister idToMatchRegister(m_registerAllocator);
1155     m_assembler.move(Assembler::TrustedImmPtr(idToMatch.impl()), idToMatchRegister);
1156     failureCases.append(m_assembler.branchPtr(Assembler::NotEqual, Assembler::Address(elementDataAddress, ElementData::idForStyleResolutionMemoryOffset()), idToMatchRegister));
1157 }
1158
1159 void SelectorCodeGenerator::generateElementHasClasses(Assembler::JumpList& failureCases, const LocalRegister& elementDataAddress, const Vector<const AtomicStringImpl*>& classNames)
1160 {
1161     // Load m_classNames.
1162     LocalRegister spaceSplitStringData(m_registerAllocator);
1163     m_assembler.loadPtr(Assembler::Address(elementDataAddress, ElementData::classNamesMemoryOffset()), spaceSplitStringData);
1164
1165     // If SpaceSplitString does not have a SpaceSplitStringData pointer, it is empty -> failure case.
1166     failureCases.append(m_assembler.branchTestPtr(Assembler::Zero, spaceSplitStringData));
1167
1168     // We loop over the classes of SpaceSplitStringData for each class name we need to match.
1169     LocalRegister indexRegister(m_registerAllocator);
1170     for (unsigned i = 0; i < classNames.size(); ++i) {
1171         LocalRegister classNameToMatch(m_registerAllocator);
1172         m_assembler.move(Assembler::TrustedImmPtr(classNames[i]), classNameToMatch);
1173         m_assembler.move(Assembler::TrustedImm32(0), indexRegister);
1174
1175         // Beginning of a loop over all the class name of element to find the one we are looking for.
1176         Assembler::Label loopStart(m_assembler.label());
1177
1178         // If the pointers match, proceed to the next matcher.
1179         Assembler::Jump classFound = m_assembler.branchPtr(Assembler::Equal, Assembler::BaseIndex(spaceSplitStringData, indexRegister, Assembler::timesPtr(), SpaceSplitStringData::tokensMemoryOffset()), classNameToMatch);
1180
1181         // Increment the index.
1182         m_assembler.add32(Assembler::TrustedImm32(1), indexRegister);
1183
1184         // If we reached the last element -> failure.
1185         failureCases.append(m_assembler.branch32(Assembler::Equal, Assembler::Address(spaceSplitStringData, SpaceSplitStringData::sizeMemoryOffset()), indexRegister));
1186         // Otherwise just loop over.
1187         m_assembler.jump().linkTo(loopStart, &m_assembler);
1188
1189         // Success case.
1190         classFound.link(&m_assembler);
1191     }
1192 }
1193
1194 void SelectorCodeGenerator::generateElementIsLink(Assembler::JumpList& failureCases)
1195 {
1196     failureCases.append(m_assembler.branchTest32(Assembler::Zero, Assembler::Address(elementAddressRegister, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagIsLink())));
1197 }
1198
1199 }; // namespace SelectorCompiler.
1200 }; // namespace WebCore.
1201
1202 #endif // ENABLE(CSS_SELECTOR_JIT)