Incorrect UA style when printing a simple document
[WebKit-https.git] / Source / WebCore / css / CSSStyleSelector.cpp
1 /*
2  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
3  *           (C) 2004-2005 Allan Sandfeld Jensen (kde@carewolf.com)
4  * Copyright (C) 2006, 2007 Nicholas Shanks (webkit@nickshanks.com)
5  * Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011 Apple Inc. All rights reserved.
6  * Copyright (C) 2007 Alexey Proskuryakov <ap@webkit.org>
7  * Copyright (C) 2007, 2008 Eric Seidel <eric@webkit.org>
8  * Copyright (C) 2008, 2009 Torch Mobile Inc. All rights reserved. (http://www.torchmobile.com/)
9  * Copyright (c) 2011, Code Aurora Forum. All rights reserved.
10  * Copyright (C) Research In Motion Limited 2011. All rights reserved.
11  *
12  * This library is free software; you can redistribute it and/or
13  * modify it under the terms of the GNU Library General Public
14  * License as published by the Free Software Foundation; either
15  * version 2 of the License, or (at your option) any later version.
16  *
17  * This library is distributed in the hope that it will be useful,
18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
20  * Library General Public License for more details.
21  *
22  * You should have received a copy of the GNU Library General Public License
23  * along with this library; see the file COPYING.LIB.  If not, write to
24  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
25  * Boston, MA 02110-1301, USA.
26  */
27
28 #include "config.h"
29 #include "CSSStyleSelector.h"
30
31 #include "Attribute.h"
32 #include "ContentData.h"
33 #include "CounterContent.h"
34 #include "CursorList.h"
35 #include "CSSBorderImageValue.h"
36 #include "CSSCursorImageValue.h"
37 #include "CSSFontFaceRule.h"
38 #include "CSSFontSelector.h"
39 #include "CSSImportRule.h"
40 #include "CSSLineBoxContainValue.h"
41 #include "CSSMediaRule.h"
42 #include "CSSPageRule.h"
43 #include "CSSParser.h"
44 #include "CSSPrimitiveValueMappings.h"
45 #include "CSSPropertyNames.h"
46 #include "CSSReflectValue.h"
47 #include "CSSRuleList.h"
48 #include "CSSSelector.h"
49 #include "CSSSelectorList.h"
50 #include "CSSStyleApplyProperty.h"
51 #include "CSSStyleRule.h"
52 #include "CSSStyleSheet.h"
53 #include "CSSTimingFunctionValue.h"
54 #include "CSSValueList.h"
55 #include "CachedImage.h"
56 #include "Counter.h"
57 #include "FocusController.h"
58 #include "FontFamilyValue.h"
59 #include "FontValue.h"
60 #include "Frame.h"
61 #include "FrameSelection.h"
62 #include "FrameView.h"
63 #include "HTMLDocument.h"
64 #include "HTMLElement.h"
65 #include "HTMLFrameElementBase.h"
66 #include "HTMLInputElement.h"
67 #include "HTMLNames.h"
68 #include "HTMLTextAreaElement.h"
69 #include "KeyframeList.h"
70 #include "LinkHash.h"
71 #include "Matrix3DTransformOperation.h"
72 #include "MatrixTransformOperation.h"
73 #include "MediaList.h"
74 #include "MediaQueryEvaluator.h"
75 #include "NodeRenderStyle.h"
76 #include "Page.h"
77 #include "PageGroup.h"
78 #include "Pair.h"
79 #include "PerspectiveTransformOperation.h"
80 #include "QuotesData.h"
81 #include "Rect.h"
82 #include "RenderScrollbar.h"
83 #include "RenderScrollbarTheme.h"
84 #include "RenderStyleConstants.h"
85 #include "RenderTheme.h"
86 #include "RotateTransformOperation.h"
87 #include "ScaleTransformOperation.h"
88 #include "SecurityOrigin.h"
89 #include "Settings.h"
90 #include "ShadowData.h"
91 #include "ShadowValue.h"
92 #include "SkewTransformOperation.h"
93 #include "StyleCachedImage.h"
94 #include "StylePendingImage.h"
95 #include "StyleGeneratedImage.h"
96 #include "StyleSheetList.h"
97 #include "Text.h"
98 #include "TransformationMatrix.h"
99 #include "TranslateTransformOperation.h"
100 #include "UserAgentStyleSheets.h"
101 #include "WebKitCSSKeyframeRule.h"
102 #include "WebKitCSSKeyframesRule.h"
103 #include "WebKitCSSTransformValue.h"
104 #include "XMLNames.h"
105 #include <wtf/StdLibExtras.h>
106 #include <wtf/Vector.h>
107
108 #if USE(PLATFORM_STRATEGIES)
109 #include "PlatformStrategies.h"
110 #include "VisitedLinkStrategy.h"
111 #endif
112
113 #if ENABLE(DASHBOARD_SUPPORT)
114 #include "DashboardRegion.h"
115 #endif
116
117 #if ENABLE(SVG)
118 #include "XLinkNames.h"
119 #include "SVGNames.h"
120 #endif
121
122 #if PLATFORM(QT)
123 #include <qwebhistoryinterface.h>
124 #endif
125
126 using namespace std;
127
128 namespace WebCore {
129
130 using namespace HTMLNames;
131
132 #define HANDLE_INHERIT(prop, Prop) \
133 if (isInherit) { \
134     m_style->set##Prop(m_parentStyle->prop()); \
135     return; \
136 }
137
138 #define HANDLE_INHERIT_AND_INITIAL(prop, Prop) \
139 HANDLE_INHERIT(prop, Prop) \
140 if (isInitial) { \
141     m_style->set##Prop(RenderStyle::initial##Prop()); \
142     return; \
143 }
144
145 #define HANDLE_INHERIT_AND_INITIAL_WITH_VALUE(prop, Prop, Value) \
146 HANDLE_INHERIT(prop, Prop) \
147 if (isInitial) { \
148     m_style->set##Prop(RenderStyle::initial##Value());\
149     return;\
150 }
151
152 #define HANDLE_INHERIT_AND_INITIAL_AND_PRIMITIVE(prop, Prop) \
153 HANDLE_INHERIT_AND_INITIAL(prop, Prop) \
154 if (primitiveValue) \
155     m_style->set##Prop(*primitiveValue);
156
157 #define HANDLE_INHERIT_AND_INITIAL_AND_PRIMITIVE_WITH_VALUE(prop, Prop, Value) \
158 HANDLE_INHERIT_AND_INITIAL_WITH_VALUE(prop, Prop, Value) \
159 if (primitiveValue) \
160     m_style->set##Prop(*primitiveValue);
161
162 #define HANDLE_ANIMATION_INHERIT_AND_INITIAL(prop, Prop) \
163 if (isInherit) { \
164     AnimationList* list = m_style->accessAnimations(); \
165     const AnimationList* parentList = m_parentStyle->animations(); \
166     size_t i = 0, parentSize = parentList ? parentList->size() : 0; \
167     for ( ; i < parentSize && parentList->animation(i)->is##Prop##Set(); ++i) { \
168         if (list->size() <= i) \
169             list->append(Animation::create()); \
170         list->animation(i)->set##Prop(parentList->animation(i)->prop()); \
171     } \
172     \
173     /* Reset any remaining animations to not have the property set. */ \
174     for ( ; i < list->size(); ++i) \
175         list->animation(i)->clear##Prop(); \
176 } else if (isInitial) { \
177     AnimationList* list = m_style->accessAnimations(); \
178     if (list->isEmpty()) \
179         list->append(Animation::create()); \
180     list->animation(0)->set##Prop(Animation::initialAnimation##Prop()); \
181     for (size_t i = 1; i < list->size(); ++i) \
182         list->animation(0)->clear##Prop(); \
183 }
184
185 #define HANDLE_ANIMATION_VALUE(prop, Prop, value) { \
186 HANDLE_ANIMATION_INHERIT_AND_INITIAL(prop, Prop) \
187 if (isInherit || isInitial) \
188     return; \
189 AnimationList* list = m_style->accessAnimations(); \
190 size_t childIndex = 0; \
191 if (value->isValueList()) { \
192     /* Walk each value and put it into an animation, creating new animations as needed. */ \
193     CSSValueList* valueList = static_cast<CSSValueList*>(value); \
194     for (unsigned int i = 0; i < valueList->length(); i++) { \
195         if (childIndex <= list->size()) \
196             list->append(Animation::create()); \
197         mapAnimation##Prop(list->animation(childIndex), valueList->itemWithoutBoundsCheck(i)); \
198         ++childIndex; \
199     } \
200 } else { \
201     if (list->isEmpty()) \
202         list->append(Animation::create()); \
203     mapAnimation##Prop(list->animation(childIndex), value); \
204     childIndex = 1; \
205 } \
206 for ( ; childIndex < list->size(); ++childIndex) { \
207     /* Reset all remaining animations to not have the property set. */ \
208     list->animation(childIndex)->clear##Prop(); \
209 } \
210 }
211
212 #define HANDLE_TRANSITION_INHERIT_AND_INITIAL(prop, Prop) \
213 if (isInherit) { \
214     AnimationList* list = m_style->accessTransitions(); \
215     const AnimationList* parentList = m_parentStyle->transitions(); \
216     size_t i = 0, parentSize = parentList ? parentList->size() : 0; \
217     for ( ; i < parentSize && parentList->animation(i)->is##Prop##Set(); ++i) { \
218         if (list->size() <= i) \
219             list->append(Animation::create()); \
220         list->animation(i)->set##Prop(parentList->animation(i)->prop()); \
221     } \
222     \
223     /* Reset any remaining transitions to not have the property set. */ \
224     for ( ; i < list->size(); ++i) \
225         list->animation(i)->clear##Prop(); \
226 } else if (isInitial) { \
227     AnimationList* list = m_style->accessTransitions(); \
228     if (list->isEmpty()) \
229         list->append(Animation::create()); \
230     list->animation(0)->set##Prop(Animation::initialAnimation##Prop()); \
231     for (size_t i = 1; i < list->size(); ++i) \
232         list->animation(0)->clear##Prop(); \
233 }
234
235 #define HANDLE_TRANSITION_VALUE(prop, Prop, value) { \
236 HANDLE_TRANSITION_INHERIT_AND_INITIAL(prop, Prop) \
237 if (isInherit || isInitial) \
238     return; \
239 AnimationList* list = m_style->accessTransitions(); \
240 size_t childIndex = 0; \
241 if (value->isValueList()) { \
242     /* Walk each value and put it into a transition, creating new animations as needed. */ \
243     CSSValueList* valueList = static_cast<CSSValueList*>(value); \
244     for (unsigned int i = 0; i < valueList->length(); i++) { \
245         if (childIndex <= list->size()) \
246             list->append(Animation::create()); \
247         mapAnimation##Prop(list->animation(childIndex), valueList->itemWithoutBoundsCheck(i)); \
248         ++childIndex; \
249     } \
250 } else { \
251     if (list->isEmpty()) \
252         list->append(Animation::create()); \
253     mapAnimation##Prop(list->animation(childIndex), value); \
254     childIndex = 1; \
255 } \
256 for ( ; childIndex < list->size(); ++childIndex) { \
257     /* Reset all remaining transitions to not have the property set. */ \
258     list->animation(childIndex)->clear##Prop(); \
259 } \
260 }
261
262 #define HANDLE_INHERIT_COND(propID, prop, Prop) \
263 if (id == propID) { \
264     m_style->set##Prop(m_parentStyle->prop()); \
265     return; \
266 }
267     
268 #define HANDLE_INHERIT_COND_WITH_BACKUP(propID, prop, propAlt, Prop) \
269 if (id == propID) { \
270     if (m_parentStyle->prop().isValid()) \
271         m_style->set##Prop(m_parentStyle->prop()); \
272     else \
273         m_style->set##Prop(m_parentStyle->propAlt()); \
274     return; \
275 }
276
277 #define HANDLE_INITIAL_COND(propID, Prop) \
278 if (id == propID) { \
279     m_style->set##Prop(RenderStyle::initial##Prop()); \
280     return; \
281 }
282
283 #define HANDLE_INITIAL_COND_WITH_VALUE(propID, Prop, Value) \
284 if (id == propID) { \
285     m_style->set##Prop(RenderStyle::initial##Value()); \
286     return; \
287 }
288
289 class RuleData {
290 public:
291     RuleData(CSSStyleRule*, CSSSelector*, unsigned position);
292
293     unsigned position() const { return m_position; }
294     CSSStyleRule* rule() const { return m_rule; }
295     CSSSelector* selector() const { return m_selector; }
296     
297     bool hasFastCheckableSelector() const { return m_hasFastCheckableSelector; }
298     bool hasMultipartSelector() const { return m_hasMultipartSelector; }
299     bool hasTopSelectorMatchingHTMLBasedOnRuleHash() const { return m_hasTopSelectorMatchingHTMLBasedOnRuleHash; }
300     unsigned specificity() const { return m_specificity; }
301     
302     // Try to balance between memory usage (there can be lots of RuleData objects) and good filtering performance.
303     static const unsigned maximumIdentifierCount = 4;
304     const unsigned* descendantSelectorIdentifierHashes() const { return m_descendantSelectorIdentifierHashes; }
305
306 private:
307     void collectDescendantSelectorIdentifierHashes();
308     void collectIdentifierHashes(const CSSSelector*, unsigned& identifierCount);
309     
310     CSSStyleRule* m_rule;
311     CSSSelector* m_selector;
312     unsigned m_specificity;
313     unsigned m_position : 29;
314     bool m_hasFastCheckableSelector : 1;
315     bool m_hasMultipartSelector : 1;
316     bool m_hasTopSelectorMatchingHTMLBasedOnRuleHash : 1;
317     // Use plain array instead of a Vector to minimize memory overhead.
318     unsigned m_descendantSelectorIdentifierHashes[maximumIdentifierCount];
319 };
320
321 class RuleSet {
322     WTF_MAKE_NONCOPYABLE(RuleSet);
323 public:
324     RuleSet();
325     ~RuleSet();
326     
327     typedef HashMap<AtomicStringImpl*, Vector<RuleData>*> AtomRuleMap;
328     
329     void addRulesFromSheet(CSSStyleSheet*, const MediaQueryEvaluator&, CSSStyleSelector* = 0);
330
331     void addStyleRule(CSSStyleRule* item);
332     void addRule(CSSStyleRule* rule, CSSSelector* sel);
333     void addPageRule(CSSStyleRule* rule, CSSSelector* sel);
334     void addToRuleSet(AtomicStringImpl* key, AtomRuleMap& map,
335                       CSSStyleRule* rule, CSSSelector* sel);
336     void shrinkToFit();
337     void disableAutoShrinkToFit() { m_autoShrinkToFitEnabled = false; }
338
339     void collectFeatures(CSSStyleSelector::Features&) const;
340     
341     const Vector<RuleData>* getIDRules(AtomicStringImpl* key) const { return m_idRules.get(key); }
342     const Vector<RuleData>* getClassRules(AtomicStringImpl* key) const { return m_classRules.get(key); }
343     const Vector<RuleData>* getTagRules(AtomicStringImpl* key) const { return m_tagRules.get(key); }
344     const Vector<RuleData>* getPseudoRules(AtomicStringImpl* key) const { return m_pseudoRules.get(key); }
345     const Vector<RuleData>* getUniversalRules() const { return &m_universalRules; }
346     const Vector<RuleData>* getPageRules() const { return &m_pageRules; }
347     
348 public:
349     AtomRuleMap m_idRules;
350     AtomRuleMap m_classRules;
351     AtomRuleMap m_tagRules;
352     AtomRuleMap m_pseudoRules;
353     Vector<RuleData> m_universalRules;
354     Vector<RuleData> m_pageRules;
355     unsigned m_ruleCount;
356     bool m_autoShrinkToFitEnabled;
357 };
358
359 static RuleSet* defaultStyle;
360 static RuleSet* defaultQuirksStyle;
361 static RuleSet* defaultPrintStyle;
362 static RuleSet* defaultViewSourceStyle;
363 static CSSStyleSheet* simpleDefaultStyleSheet;
364     
365 static RuleSet* siblingRulesInDefaultStyle;
366
367 RenderStyle* CSSStyleSelector::s_styleNotYetAvailable;
368
369 static void loadFullDefaultStyle();
370 static void loadSimpleDefaultStyle();
371 // FIXME: It would be nice to use some mechanism that guarantees this is in sync with the real UA stylesheet.
372 static const char* simpleUserAgentStyleSheet = "html,body,div{display:block}head{display:none}body{margin:8px}div:focus,span:focus{outline:auto 5px -webkit-focus-ring-color}a:-webkit-any-link{color:-webkit-link;text-decoration:underline}a:-webkit-any-link:active{color:-webkit-activelink}";
373
374 static inline bool elementCanUseSimpleDefaultStyle(Element* e)
375 {
376     return e->hasTagName(htmlTag) || e->hasTagName(headTag) || e->hasTagName(bodyTag) || e->hasTagName(divTag) || e->hasTagName(spanTag) || e->hasTagName(brTag) || e->hasTagName(aTag);
377 }
378
379 static inline void collectSiblingRulesInDefaultStyle()
380 {
381     CSSStyleSelector::Features features;
382     defaultStyle->collectFeatures(features);
383     ASSERT(features.idsInRules.isEmpty());
384     delete siblingRulesInDefaultStyle;
385     siblingRulesInDefaultStyle = features.siblingRules.leakPtr();
386 }
387
388 static inline void assertNoSiblingRulesInDefaultStyle()
389 {
390 #ifndef NDEBUG
391     if (siblingRulesInDefaultStyle)
392         return;
393     collectSiblingRulesInDefaultStyle();
394     ASSERT(!siblingRulesInDefaultStyle);
395 #endif
396 }
397     
398 static const MediaQueryEvaluator& screenEval()
399 {
400     DEFINE_STATIC_LOCAL(const MediaQueryEvaluator, staticScreenEval, ("screen"));
401     return staticScreenEval;
402 }
403
404 static const MediaQueryEvaluator& printEval()
405 {
406     DEFINE_STATIC_LOCAL(const MediaQueryEvaluator, staticPrintEval, ("print"));
407     return staticPrintEval;
408 }
409
410 static CSSMutableStyleDeclaration* leftToRightDeclaration()
411 {
412     DEFINE_STATIC_LOCAL(RefPtr<CSSMutableStyleDeclaration>, leftToRightDecl, (CSSMutableStyleDeclaration::create()));
413     if (!leftToRightDecl->length()) {
414         leftToRightDecl->setProperty(CSSPropertyDirection, "ltr", false, false);
415         leftToRightDecl->setStrictParsing(false);
416     }
417     return leftToRightDecl.get();
418 }
419
420 static CSSMutableStyleDeclaration* rightToLeftDeclaration()
421 {
422     DEFINE_STATIC_LOCAL(RefPtr<CSSMutableStyleDeclaration>, rightToLeftDecl, (CSSMutableStyleDeclaration::create()));
423     if (!rightToLeftDecl->length()) {
424         rightToLeftDecl->setProperty(CSSPropertyDirection, "rtl", false, false);
425         rightToLeftDecl->setStrictParsing(false);
426     }
427     return rightToLeftDecl.get();
428 }
429
430 CSSStyleSelector::CSSStyleSelector(Document* document, StyleSheetList* styleSheets, CSSStyleSheet* mappedElementSheet,
431                                    CSSStyleSheet* pageUserSheet, const Vector<RefPtr<CSSStyleSheet> >* pageGroupUserSheets,
432                                    bool strictParsing, bool matchAuthorAndUserStyles)
433     : m_backgroundData(BackgroundFillLayer)
434     , m_checker(document, strictParsing)
435     , m_element(0)
436     , m_styledElement(0)
437     , m_elementLinkState(NotInsideLink)
438     , m_fontSelector(CSSFontSelector::create(document))
439     , m_applyProperty(CSSStyleApplyProperty::sharedCSSStyleApplyProperty())
440 {
441     m_matchAuthorAndUserStyles = matchAuthorAndUserStyles;
442     
443     Element* root = document->documentElement();
444
445     if (!defaultStyle) {
446         if (!root || elementCanUseSimpleDefaultStyle(root))
447             loadSimpleDefaultStyle();
448         else {
449             loadFullDefaultStyle();
450         }
451     }
452
453     // construct document root element default style. this is needed
454     // to evaluate media queries that contain relative constraints, like "screen and (max-width: 10em)"
455     // This is here instead of constructor, because when constructor is run,
456     // document doesn't have documentElement
457     // NOTE: this assumes that element that gets passed to styleForElement -call
458     // is always from the document that owns the style selector
459     FrameView* view = document->view();
460     if (view)
461         m_medium = adoptPtr(new MediaQueryEvaluator(view->mediaType()));
462     else
463         m_medium = adoptPtr(new MediaQueryEvaluator("all"));
464
465     if (root)
466         m_rootDefaultStyle = styleForElement(root, 0, false, true); // don't ref, because the RenderStyle is allocated from global heap
467
468     if (m_rootDefaultStyle && view)
469         m_medium = adoptPtr(new MediaQueryEvaluator(view->mediaType(), view->frame(), m_rootDefaultStyle.get()));
470
471     m_authorStyle = adoptPtr(new RuleSet);
472     // Adding rules from multiple sheets, shrink at the end.
473     m_authorStyle->disableAutoShrinkToFit();
474
475     // FIXME: This sucks! The user sheet is reparsed every time!
476     OwnPtr<RuleSet> tempUserStyle = adoptPtr(new RuleSet);
477     if (pageUserSheet)
478         tempUserStyle->addRulesFromSheet(pageUserSheet, *m_medium, this);
479     if (pageGroupUserSheets) {
480         unsigned length = pageGroupUserSheets->size();
481         for (unsigned i = 0; i < length; i++) {
482             if (pageGroupUserSheets->at(i)->isUserStyleSheet())
483                 tempUserStyle->addRulesFromSheet(pageGroupUserSheets->at(i).get(), *m_medium, this);
484             else
485                 m_authorStyle->addRulesFromSheet(pageGroupUserSheets->at(i).get(), *m_medium, this);
486         }
487     }
488
489     if (tempUserStyle->m_ruleCount > 0 || tempUserStyle->m_pageRules.size() > 0)
490         m_userStyle = tempUserStyle.release();
491
492     // Add rules from elements like SVG's <font-face>
493     if (mappedElementSheet)
494         m_authorStyle->addRulesFromSheet(mappedElementSheet, *m_medium, this);
495
496     // add stylesheets from document
497     unsigned length = styleSheets->length();
498     for (unsigned i = 0; i < length; i++) {
499         StyleSheet* sheet = styleSheets->item(i);
500         if (sheet->isCSSStyleSheet() && !sheet->disabled())
501             m_authorStyle->addRulesFromSheet(static_cast<CSSStyleSheet*>(sheet), *m_medium, this);
502     }    
503     // Collect all ids and rules using sibling selectors (:first-child and similar)
504     // in the current set of stylesheets. Style sharing code uses this information to reject
505     // sharing candidates.
506     // Usually there are no sibling rules in the default style but the MathML sheet has some.
507     if (siblingRulesInDefaultStyle)
508         siblingRulesInDefaultStyle->collectFeatures(m_features);
509     m_authorStyle->collectFeatures(m_features);
510     if (m_userStyle)
511         m_userStyle->collectFeatures(m_features);
512
513     m_authorStyle->shrinkToFit();
514     if (m_features.siblingRules)
515         m_features.siblingRules->shrinkToFit();
516
517     if (document->renderer() && document->renderer()->style())
518         document->renderer()->style()->font().update(fontSelector());
519 }
520
521 // This is a simplified style setting function for keyframe styles
522 void CSSStyleSelector::addKeyframeStyle(PassRefPtr<WebKitCSSKeyframesRule> rule)
523 {
524     AtomicString s(rule->name());
525     m_keyframesRuleMap.add(s.impl(), rule);
526 }
527
528 CSSStyleSelector::~CSSStyleSelector()
529 {
530     m_fontSelector->clearDocument();
531     deleteAllValues(m_viewportDependentMediaQueryResults);
532 }
533     
534 CSSStyleSelector::Features::Features() 
535     : usesFirstLineRules(false)
536     , usesBeforeAfterRules(false)
537     , usesLinkRules(false)
538 {
539 }
540
541 CSSStyleSelector::Features::~Features()
542 {
543 }
544
545 static CSSStyleSheet* parseUASheet(const String& str)
546 {
547     CSSStyleSheet* sheet = CSSStyleSheet::create().releaseRef(); // leak the sheet on purpose
548     sheet->parseString(str);
549     return sheet;
550 }
551
552 static CSSStyleSheet* parseUASheet(const char* characters, unsigned size)
553 {
554     return parseUASheet(String(characters, size));
555 }
556
557 static void loadFullDefaultStyle()
558 {
559     if (simpleDefaultStyleSheet) {
560         ASSERT(defaultStyle);
561         ASSERT(defaultPrintStyle == defaultStyle);
562         delete defaultStyle;
563         simpleDefaultStyleSheet->deref();
564         defaultStyle = new RuleSet;
565         defaultPrintStyle = new RuleSet;
566         simpleDefaultStyleSheet = 0;
567     } else {
568         ASSERT(!defaultStyle);
569         defaultStyle = new RuleSet;
570         defaultPrintStyle = new RuleSet;
571         defaultQuirksStyle = new RuleSet;
572     }
573
574     // Strict-mode rules.
575     String defaultRules = String(htmlUserAgentStyleSheet, sizeof(htmlUserAgentStyleSheet)) + RenderTheme::defaultTheme()->extraDefaultStyleSheet();
576     CSSStyleSheet* defaultSheet = parseUASheet(defaultRules);
577     defaultStyle->addRulesFromSheet(defaultSheet, screenEval());
578     defaultPrintStyle->addRulesFromSheet(defaultSheet, printEval());
579
580     // Quirks-mode rules.
581     String quirksRules = String(quirksUserAgentStyleSheet, sizeof(quirksUserAgentStyleSheet)) + RenderTheme::defaultTheme()->extraQuirksStyleSheet();
582     CSSStyleSheet* quirksSheet = parseUASheet(quirksRules);
583     defaultQuirksStyle->addRulesFromSheet(quirksSheet, screenEval());
584 }
585
586 static void loadSimpleDefaultStyle()
587 {
588     ASSERT(!defaultStyle);
589     ASSERT(!simpleDefaultStyleSheet);
590     
591     defaultStyle = new RuleSet;
592     // There are no media-specific rules in the simple default style.
593     defaultPrintStyle = defaultStyle;
594     defaultQuirksStyle = new RuleSet;
595
596     simpleDefaultStyleSheet = parseUASheet(simpleUserAgentStyleSheet, strlen(simpleUserAgentStyleSheet));
597     defaultStyle->addRulesFromSheet(simpleDefaultStyleSheet, screenEval());
598     
599     // No need to initialize quirks sheet yet as there are no quirk rules for elements allowed in simple default style.
600 }
601     
602 static void loadViewSourceStyle()
603 {
604     ASSERT(!defaultViewSourceStyle);
605     defaultViewSourceStyle = new RuleSet;
606     defaultViewSourceStyle->addRulesFromSheet(parseUASheet(sourceUserAgentStyleSheet, sizeof(sourceUserAgentStyleSheet)), screenEval());
607 }
608     
609 static inline void collectElementIdentifierHashes(const Element* element, Vector<unsigned, 4>& identifierHashes)
610 {
611     identifierHashes.append(element->localName().impl()->existingHash());
612     if (element->hasID())
613         identifierHashes.append(element->idForStyleResolution().impl()->existingHash());
614     const StyledElement* styledElement = element->isStyledElement() ? static_cast<const StyledElement*>(element) : 0;
615     if (styledElement && styledElement->hasClass()) {
616         const SpaceSplitString& classNames = styledElement->classNames();
617         size_t count = classNames.size();
618         for (size_t i = 0; i < count; ++i)
619             identifierHashes.append(classNames[i].impl()->existingHash());
620     }
621 }
622
623 void CSSStyleSelector::pushParentStackFrame(Element* parent)
624 {
625     ASSERT(m_ancestorIdentifierFilter);
626     ASSERT(m_parentStack.isEmpty() || m_parentStack.last().element == parent->parentElement());
627     ASSERT(!m_parentStack.isEmpty() || !parent->parentElement());
628     m_parentStack.append(ParentStackFrame(parent));
629     ParentStackFrame& parentFrame = m_parentStack.last();
630     // Mix tags, class names and ids into some sort of weird bouillabaisse.
631     // The filter is used for fast rejection of child and descendant selectors.
632     collectElementIdentifierHashes(parent, parentFrame.identifierHashes);
633     size_t count = parentFrame.identifierHashes.size();
634     for (size_t i = 0; i < count; ++i)
635         m_ancestorIdentifierFilter->add(parentFrame.identifierHashes[i]);
636 }
637
638 void CSSStyleSelector::popParentStackFrame()
639 {
640     ASSERT(!m_parentStack.isEmpty());
641     ASSERT(m_ancestorIdentifierFilter);
642     const ParentStackFrame& parentFrame = m_parentStack.last();
643     size_t count = parentFrame.identifierHashes.size();
644     for (size_t i = 0; i < count; ++i)
645         m_ancestorIdentifierFilter->remove(parentFrame.identifierHashes[i]);
646     m_parentStack.removeLast();
647     if (m_parentStack.isEmpty()) {
648         ASSERT(m_ancestorIdentifierFilter->likelyEmpty());
649         m_ancestorIdentifierFilter.clear();
650     }
651 }
652
653 void CSSStyleSelector::pushParent(Element* parent)
654 {
655     if (m_parentStack.isEmpty()) {
656         ASSERT(!m_ancestorIdentifierFilter);
657         m_ancestorIdentifierFilter = adoptPtr(new BloomFilter<bloomFilterKeyBits>);
658         // If the element is not the root itself, build the stack starting from the root.
659         if (parent->parentElement()) {
660             Vector<Element*, 30> ancestors;
661             for (Element* ancestor = parent; ancestor; ancestor = ancestor->parentElement())
662                 ancestors.append(ancestor);
663             int count = ancestors.size();
664             for (int n = count - 1; n >= 0; --n)
665                 pushParentStackFrame(ancestors[n]);
666             return;
667         }
668     } else if (!parent->parentElement()) {
669         // We are not always invoked consistently. For example, script execution can cause us to enter
670         // style recalc in the middle of tree building. Reset the stack if we see a new root element.
671         ASSERT(m_ancestorIdentifierFilter);
672         m_ancestorIdentifierFilter->clear();
673         m_parentStack.resize(0);
674     } else {
675         ASSERT(m_ancestorIdentifierFilter);
676         // We may get invoked for some random elements in some wacky cases during style resolve.
677         // Pause maintaining the stack in this case.
678         if (m_parentStack.last().element != parent->parentElement())
679             return;
680     }
681     pushParentStackFrame(parent);
682 }
683
684 void CSSStyleSelector::popParent(Element* parent)
685 {
686     if (m_parentStack.isEmpty() || m_parentStack.last().element != parent)
687         return;
688     popParentStackFrame();
689 }
690
691 void CSSStyleSelector::addMatchedDeclaration(CSSMutableStyleDeclaration* decl)
692 {
693     m_matchedDecls.append(decl);
694 }
695
696 void CSSStyleSelector::matchRules(RuleSet* rules, int& firstRuleIndex, int& lastRuleIndex, bool includeEmptyRules)
697 {
698     m_matchedRules.clear();
699
700     if (!rules || !m_element)
701         return;
702     
703     // We need to collect the rules for id, class, tag, and everything else into a buffer and
704     // then sort the buffer.
705     if (m_element->hasID())
706         matchRulesForList(rules->getIDRules(m_element->idForStyleResolution().impl()), firstRuleIndex, lastRuleIndex, includeEmptyRules);
707     if (m_element->hasClass()) {
708         ASSERT(m_styledElement);
709         const SpaceSplitString& classNames = m_styledElement->classNames();
710         size_t size = classNames.size();
711         for (size_t i = 0; i < size; ++i)
712             matchRulesForList(rules->getClassRules(classNames[i].impl()), firstRuleIndex, lastRuleIndex, includeEmptyRules);
713     }
714     const AtomicString& pseudoId = m_element->shadowPseudoId();
715     if (!pseudoId.isEmpty()) {
716         ASSERT(m_styledElement);
717         matchRulesForList(rules->getPseudoRules(pseudoId.impl()), firstRuleIndex, lastRuleIndex, includeEmptyRules);
718     }
719     matchRulesForList(rules->getTagRules(m_element->localName().impl()), firstRuleIndex, lastRuleIndex, includeEmptyRules);
720     matchRulesForList(rules->getUniversalRules(), firstRuleIndex, lastRuleIndex, includeEmptyRules);
721     
722     // If we didn't match any rules, we're done.
723     if (m_matchedRules.isEmpty())
724         return;
725     
726     // Sort the set of matched rules.
727     sortMatchedRules();
728     
729     // Now transfer the set of matched rules over to our list of decls.
730     if (!m_checker.m_collectRulesOnly) {
731         for (unsigned i = 0; i < m_matchedRules.size(); i++)
732             addMatchedDeclaration(m_matchedRules[i]->rule()->declaration());
733     } else {
734         for (unsigned i = 0; i < m_matchedRules.size(); i++) {
735             if (!m_ruleList)
736                 m_ruleList = CSSRuleList::create();
737             m_ruleList->append(m_matchedRules[i]->rule());
738         }
739     }
740 }
741
742 inline bool CSSStyleSelector::fastRejectSelector(const RuleData& ruleData) const
743 {
744     ASSERT(m_ancestorIdentifierFilter);
745     const unsigned* descendantSelectorIdentifierHashes = ruleData.descendantSelectorIdentifierHashes();
746     for (unsigned n = 0; n < RuleData::maximumIdentifierCount && descendantSelectorIdentifierHashes[n]; ++n) {
747         if (!m_ancestorIdentifierFilter->mayContain(descendantSelectorIdentifierHashes[n]))
748             return true;
749     }
750     return false;
751 }
752
753 class MatchingUARulesScope {
754 public:
755     MatchingUARulesScope();
756     ~MatchingUARulesScope();
757
758     static bool isMatchingUARules();
759
760 private:
761     static bool m_matchingUARules;
762 };
763
764 MatchingUARulesScope::MatchingUARulesScope()
765 {
766     ASSERT(!m_matchingUARules);
767     m_matchingUARules = true;
768 }
769
770 MatchingUARulesScope::~MatchingUARulesScope()
771 {
772     m_matchingUARules = false;
773 }
774
775 inline bool MatchingUARulesScope::isMatchingUARules()
776 {
777     return m_matchingUARules;
778 }
779
780 bool MatchingUARulesScope::m_matchingUARules = false;
781
782 inline static bool matchesInTreeScope(TreeScope* treeScope, bool ruleReachesIntoShadowDOM)
783 {
784     return MatchingUARulesScope::isMatchingUARules() || treeScope->applyAuthorSheets() || ruleReachesIntoShadowDOM;
785 }
786
787 void CSSStyleSelector::matchRulesForList(const Vector<RuleData>* rules, int& firstRuleIndex, int& lastRuleIndex, bool includeEmptyRules)
788 {
789     if (!rules)
790         return;
791     // In some cases we may end up looking up style for random elements in the middle of a recursive tree resolve.
792     // Ancestor identifier filter won't be up-to-date in that case and we can't use the fast path.
793     bool canUseFastReject = !m_parentStack.isEmpty() && m_parentStack.last().element == m_parentNode;
794
795     unsigned size = rules->size();
796     for (unsigned i = 0; i < size; ++i) {
797         const RuleData& ruleData = rules->at(i);
798         if (canUseFastReject && fastRejectSelector(ruleData))
799             continue;
800         if (checkSelector(ruleData)) {
801             if (!matchesInTreeScope(m_element->treeScope(), m_checker.m_hasUnknownPseudoElements))
802                 continue;
803             // If the rule has no properties to apply, then ignore it in the non-debug mode.
804             CSSStyleRule* rule = ruleData.rule();
805             CSSMutableStyleDeclaration* decl = rule->declaration();
806             if (!decl || (!decl->length() && !includeEmptyRules))
807                 continue;
808             if (m_checker.m_sameOriginOnly && !m_checker.m_document->securityOrigin()->canRequest(rule->baseURL()))
809                 continue; 
810             // If we're matching normal rules, set a pseudo bit if 
811             // we really just matched a pseudo-element.
812             if (m_dynamicPseudo != NOPSEUDO && m_checker.m_pseudoStyle == NOPSEUDO) {
813                 if (m_checker.m_collectRulesOnly)
814                     continue;
815                 if (m_dynamicPseudo < FIRST_INTERNAL_PSEUDOID)
816                     m_style->setHasPseudoStyle(m_dynamicPseudo);
817             } else {
818                 // Update our first/last rule indices in the matched rules array.
819                 lastRuleIndex = m_matchedDecls.size() + m_matchedRules.size();
820                 if (firstRuleIndex == -1)
821                     firstRuleIndex = lastRuleIndex;
822
823                 // Add this rule to our list of matched rules.
824                 addMatchedRule(&ruleData);
825             }
826         }
827     }
828 }
829
830 static inline bool compareRules(const RuleData* r1, const RuleData* r2)
831 {
832     unsigned specificity1 = r1->specificity();
833     unsigned specificity2 = r2->specificity();
834     return (specificity1 == specificity2) ? r1->position() < r2->position() : specificity1 < specificity2; 
835 }
836
837 void CSSStyleSelector::sortMatchedRules()
838 {
839     std::sort(m_matchedRules.begin(), m_matchedRules.end(), compareRules);
840 }
841
842 inline EInsideLink CSSStyleSelector::SelectorChecker::determineLinkState(Element* element) const
843 {
844     if (!element || !element->isLink())
845         return NotInsideLink;
846     return determineLinkStateSlowCase(element);
847 }
848     
849 inline void CSSStyleSelector::initElement(Element* e)
850 {
851     if (m_element != e) {
852         m_element = e;
853         m_styledElement = m_element && m_element->isStyledElement() ? static_cast<StyledElement*>(m_element) : 0;
854         m_elementLinkState = m_checker.determineLinkState(m_element);
855         if (e && e == e->document()->documentElement()) {
856             e->document()->setDirectionSetOnDocumentElement(false);
857             e->document()->setWritingModeSetOnDocumentElement(false);
858         }
859     }
860 }
861
862 inline void CSSStyleSelector::initForStyleResolve(Element* e, RenderStyle* parentStyle, PseudoId pseudoID)
863 {
864     m_checker.m_pseudoStyle = pseudoID;
865
866     m_parentNode = e ? e->parentNodeForRenderingAndStyle() : 0;
867
868     if (parentStyle)
869         m_parentStyle = parentStyle;
870     else
871         m_parentStyle = m_parentNode ? m_parentNode->renderStyle() : 0;
872
873     Node* docElement = e ? e->document()->documentElement() : 0;
874     RenderStyle* docStyle = m_checker.m_document->renderStyle();
875     m_rootElementStyle = docElement && e != docElement ? docElement->renderStyle() : docStyle;
876
877     m_style = 0;
878
879     m_matchedDecls.clear();
880
881     m_pendingImageProperties.clear();
882
883     m_ruleList = 0;
884
885     m_fontDirty = false;
886 }
887
888 static inline const AtomicString* linkAttribute(Node* node)
889 {
890     if (!node->isLink())
891         return 0;
892
893     ASSERT(node->isElementNode());
894     Element* element = static_cast<Element*>(node);
895     if (element->isHTMLElement())
896         return &element->fastGetAttribute(hrefAttr);
897
898 #if ENABLE(SVG)
899     if (element->isSVGElement())
900         return &element->fastGetAttribute(XLinkNames::hrefAttr);
901 #endif
902
903     return 0;
904 }
905
906 CSSStyleSelector::SelectorChecker::SelectorChecker(Document* document, bool strictParsing)
907     : m_document(document)
908     , m_strictParsing(strictParsing)
909     , m_collectRulesOnly(false)
910     , m_sameOriginOnly(false)
911     , m_pseudoStyle(NOPSEUDO)
912     , m_documentIsHTML(document->isHTMLDocument())
913     , m_hasUnknownPseudoElements(false)
914     , m_matchVisitedPseudoClass(false)
915 {
916 }
917
918 EInsideLink CSSStyleSelector::SelectorChecker::determineLinkStateSlowCase(Element* element) const
919 {
920     ASSERT(element->isLink());
921     
922     const AtomicString* attr = linkAttribute(element);
923     if (!attr || attr->isNull())
924         return NotInsideLink;
925
926 #if PLATFORM(QT)
927     Vector<UChar, 512> url;
928     visitedURL(m_document->baseURL(), *attr, url);
929     if (url.isEmpty())
930         return InsideUnvisitedLink;
931
932     // If the Qt4.4 interface for the history is used, we will have to fallback
933     // to the old global history.
934     QWebHistoryInterface* iface = QWebHistoryInterface::defaultInterface();
935     if (iface)
936         return iface->historyContains(QString(reinterpret_cast<QChar*>(url.data()), url.size())) ? InsideVisitedLink : InsideUnvisitedLink;
937
938     LinkHash hash = visitedLinkHash(url.data(), url.size());
939     if (!hash)
940         return InsideUnvisitedLink;
941 #else
942     LinkHash hash = visitedLinkHash(m_document->baseURL(), *attr);
943     if (!hash)
944         return InsideUnvisitedLink;
945 #endif
946
947     Frame* frame = m_document->frame();
948     if (!frame)
949         return InsideUnvisitedLink;
950
951     Page* page = frame->page();
952     if (!page)
953         return InsideUnvisitedLink;
954
955     m_linksCheckedForVisitedState.add(hash);
956
957 #if USE(PLATFORM_STRATEGIES)
958     return platformStrategies()->visitedLinkStrategy()->isLinkVisited(page, hash) ? InsideVisitedLink : InsideUnvisitedLink;
959 #else
960     return page->group().isLinkVisited(hash) ? InsideVisitedLink : InsideUnvisitedLink;
961 #endif
962 }
963
964 bool CSSStyleSelector::SelectorChecker::checkSelector(CSSSelector* sel, Element* element) const
965 {
966     PseudoId dynamicPseudo = NOPSEUDO;
967     return checkSelector(sel, element, dynamicPseudo, false, false) == SelectorMatches;
968 }
969
970 static const unsigned cStyleSearchThreshold = 10;
971 static const unsigned cStyleSearchLevelThreshold = 10;
972
973 Node* CSSStyleSelector::locateCousinList(Element* parent, unsigned& visitedNodeCount) const
974 {
975     if (visitedNodeCount >= cStyleSearchThreshold * cStyleSearchLevelThreshold)
976         return 0;
977     if (!parent || !parent->isStyledElement())
978         return 0;
979     StyledElement* p = static_cast<StyledElement*>(parent);
980     if (p->inlineStyleDecl())
981         return 0;
982     if (p->hasID() && m_features.idsInRules.contains(p->idForStyleResolution().impl()))
983         return 0;
984
985     RenderStyle* parentStyle = p->renderStyle();
986     unsigned subcount = 0;
987     Node* thisCousin = p;
988     Node* currentNode = p->previousSibling();
989
990     // Reserve the tries for this level. This effectively makes sure that the algorithm
991     // will never go deeper than cStyleSearchLevelThreshold levels into recursion.
992     visitedNodeCount += cStyleSearchThreshold;
993     while (thisCousin) {
994         while (currentNode) {
995             ++subcount;
996             if (currentNode->renderStyle() == parentStyle && currentNode->lastChild()) {
997                 // Adjust for unused reserved tries.
998                 visitedNodeCount -= cStyleSearchThreshold - subcount;
999                 return currentNode->lastChild();
1000             }
1001             if (subcount >= cStyleSearchThreshold)
1002                 return 0;
1003             currentNode = currentNode->previousSibling();
1004         }
1005         currentNode = locateCousinList(thisCousin->parentElement(), visitedNodeCount);
1006         thisCousin = currentNode;
1007     }
1008
1009     return 0;
1010 }
1011
1012 bool CSSStyleSelector::matchesSiblingRules()
1013 {
1014     int firstSiblingRule = -1, lastSiblingRule = -1;
1015     matchRules(m_features.siblingRules.get(), firstSiblingRule, lastSiblingRule, false);
1016     if (m_matchedDecls.isEmpty())
1017         return false;
1018     m_matchedDecls.clear();
1019     return true;
1020 }
1021
1022 bool CSSStyleSelector::canShareStyleWithElement(Node* node) const
1023 {
1024     if (!node->isStyledElement())
1025         return false;
1026
1027     StyledElement* element = static_cast<StyledElement*>(node);
1028     RenderStyle* style = element->renderStyle();
1029
1030     if (!style)
1031         return false;
1032     if (style->unique())
1033         return false;
1034     if (element->tagQName() != m_element->tagQName())
1035         return false;
1036     if (element->hasClass() != m_element->hasClass())
1037         return false;
1038     if (element->inlineStyleDecl())
1039         return false;
1040     if (element->hasMappedAttributes() != m_styledElement->hasMappedAttributes())
1041         return false;
1042     if (element->isLink() != m_element->isLink())
1043         return false;
1044     if (style->affectedByAttributeSelectors())
1045         return false;
1046     if (element->hovered() != m_element->hovered())
1047         return false;
1048     if (element->active() != m_element->active())
1049         return false;
1050     if (element->focused() != m_element->focused())
1051         return false;
1052     if (element->shadowPseudoId() != m_element->shadowPseudoId())
1053         return false;
1054     if (element == element->document()->cssTarget())
1055         return false;
1056     if (m_element == m_element->document()->cssTarget())
1057         return false;
1058     if (element->fastGetAttribute(typeAttr) != m_element->fastGetAttribute(typeAttr))
1059         return false;
1060     if (element->fastGetAttribute(XMLNames::langAttr) != m_element->fastGetAttribute(XMLNames::langAttr))
1061         return false;
1062     if (element->fastGetAttribute(langAttr) != m_element->fastGetAttribute(langAttr))
1063         return false;
1064     if (element->fastGetAttribute(readonlyAttr) != m_element->fastGetAttribute(readonlyAttr))
1065         return false;
1066     if (element->fastGetAttribute(cellpaddingAttr) != m_element->fastGetAttribute(cellpaddingAttr))
1067         return false;
1068
1069     if (element->hasID() && m_features.idsInRules.contains(element->idForStyleResolution().impl()))
1070         return false;
1071
1072     bool isControl = element->isFormControlElement();
1073
1074     if (isControl != m_element->isFormControlElement())
1075         return false;
1076
1077     if (isControl) {
1078         HTMLInputElement* thisInputElement = element->toInputElement();
1079         HTMLInputElement* otherInputElement = m_element->toInputElement();
1080
1081         if (!thisInputElement || !otherInputElement)
1082             return false;
1083
1084         if (thisInputElement->isAutofilled() != otherInputElement->isAutofilled())
1085             return false;
1086         if (thisInputElement->isChecked() != otherInputElement->isChecked())
1087             return false;
1088         if (thisInputElement->isIndeterminate() != otherInputElement->isIndeterminate())
1089             return false;
1090
1091         if (element->isEnabledFormControl() != m_element->isEnabledFormControl())
1092             return false;
1093
1094         if (element->isDefaultButtonForForm() != m_element->isDefaultButtonForForm())
1095             return false;
1096
1097         if (!m_element->document()->containsValidityStyleRules())
1098             return false;
1099
1100         bool willValidate = element->willValidate();
1101
1102         if (willValidate != m_element->willValidate())
1103             return false;
1104
1105         if (willValidate && (element->isValidFormControlElement() != m_element->isValidFormControlElement()))
1106             return false;
1107
1108         if (element->isInRange() != m_element->isInRange())
1109             return false;
1110
1111         if (element->isOutOfRange() != m_element->isOutOfRange())
1112             return false;
1113     }
1114
1115     if (style->transitions() || style->animations())
1116         return false;
1117
1118 #if USE(ACCELERATED_COMPOSITING)
1119     // Turn off style sharing for elements that can gain layers for reasons outside of the style system.
1120     // See comments in RenderObject::setStyle().
1121     if (element->hasTagName(iframeTag) || element->hasTagName(frameTag) || element->hasTagName(embedTag) || element->hasTagName(objectTag) || element->hasTagName(appletTag))
1122         return false;
1123 #endif
1124
1125     if (equalIgnoringCase(element->fastGetAttribute(dirAttr), "auto") || equalIgnoringCase(m_element->fastGetAttribute(dirAttr), "auto"))
1126         return false;
1127
1128     if (element->hasClass() && m_element->fastGetAttribute(classAttr) != element->fastGetAttribute(classAttr))
1129         return false;
1130
1131     if (element->hasMappedAttributes() && !element->attributeMap()->mappedMapsEquivalent(m_styledElement->attributeMap()))
1132         return false;
1133
1134     if (element->isLink() && m_elementLinkState != style->insideLink())
1135         return false;
1136
1137     return true;
1138 }
1139     
1140 inline Node* CSSStyleSelector::findSiblingForStyleSharing(Node* node, unsigned& count) const
1141 {
1142     for (; node; node = node->previousSibling()) {
1143         if (!node->isElementNode())
1144             continue;
1145         if (canShareStyleWithElement(node))
1146             break;
1147         if (count++ == cStyleSearchThreshold)
1148             return 0;
1149     }
1150     return node;
1151 }
1152
1153 static inline bool parentStylePreventsSharing(const RenderStyle* parentStyle)
1154 {
1155     return parentStyle->childrenAffectedByPositionalRules() 
1156         || parentStyle->childrenAffectedByFirstChildRules()
1157         || parentStyle->childrenAffectedByLastChildRules() 
1158         || parentStyle->childrenAffectedByDirectAdjacentRules();
1159 }
1160
1161 ALWAYS_INLINE RenderStyle* CSSStyleSelector::locateSharedStyle()
1162 {
1163     if (!m_styledElement || !m_parentStyle)
1164         return 0;
1165     // If the element has inline style it is probably unique.
1166     if (m_styledElement->inlineStyleDecl())
1167         return 0;
1168     // Ids stop style sharing if they show up in the stylesheets.
1169     if (m_styledElement->hasID() && m_features.idsInRules.contains(m_styledElement->idForStyleResolution().impl()))
1170         return 0;
1171     if (parentStylePreventsSharing(m_parentStyle))
1172         return 0;
1173
1174     // Check previous siblings and their cousins.
1175     unsigned count = 0;
1176     unsigned visitedNodeCount = 0;
1177     Node* shareNode = 0;
1178     Node* cousinList = m_styledElement->previousSibling();
1179     while (cousinList) {
1180         shareNode = findSiblingForStyleSharing(cousinList, count);
1181         if (shareNode)
1182             break;
1183         cousinList = locateCousinList(cousinList->parentElement(), visitedNodeCount);
1184     }
1185
1186     // If we have exhausted all our budget or our cousins.
1187     if (!shareNode)
1188         return 0;
1189
1190     // Can't share if sibling rules apply. This is checked at the end as it should rarely fail.
1191     if (matchesSiblingRules())
1192         return 0;
1193     // Tracking child index requires unique style for each node. This may get set by the sibling rule match above.
1194     if (parentStylePreventsSharing(m_parentStyle))
1195         return 0;
1196     return shareNode->renderStyle();
1197 }
1198
1199 void CSSStyleSelector::matchUARules(int& firstUARule, int& lastUARule)
1200 {
1201     MatchingUARulesScope scope;
1202
1203     // First we match rules from the user agent sheet.
1204     RuleSet* userAgentStyleSheet = m_medium->mediaTypeMatchSpecific("print")
1205         ? defaultPrintStyle : defaultStyle;
1206     matchRules(userAgentStyleSheet, firstUARule, lastUARule, false);
1207
1208     // In quirks mode, we match rules from the quirks user agent sheet.
1209     if (!m_checker.m_strictParsing)
1210         matchRules(defaultQuirksStyle, firstUARule, lastUARule, false);
1211         
1212     // If document uses view source styles (in view source mode or in xml viewer mode), then we match rules from the view source style sheet.
1213     if (m_checker.m_document->isViewSource()) {
1214         if (!defaultViewSourceStyle)
1215             loadViewSourceStyle();
1216         matchRules(defaultViewSourceStyle, firstUARule, lastUARule, false);
1217     }
1218 }
1219
1220 PassRefPtr<RenderStyle> CSSStyleSelector::styleForDocument(Document* document)
1221 {
1222     Frame* frame = document->frame();
1223
1224     RefPtr<RenderStyle> documentStyle = RenderStyle::create();
1225     documentStyle->setDisplay(BLOCK);
1226     documentStyle->setVisuallyOrdered(document->visuallyOrdered());
1227     documentStyle->setZoom(frame ? frame->pageZoomFactor() : 1);
1228     documentStyle->setPageScaleTransform(frame ? frame->pageScaleFactor() : 1);
1229     documentStyle->setUserModify(document->inDesignMode() ? READ_WRITE : READ_ONLY);
1230
1231     Element* docElement = document->documentElement();
1232     RenderObject* docElementRenderer = docElement ? docElement->renderer() : 0;
1233     if (docElementRenderer) {
1234         // Use the direction and writing-mode of the body to set the
1235         // viewport's direction and writing-mode unless the property is set on the document element.
1236         // If there is no body, then use the document element.
1237         RenderObject* bodyRenderer = document->body() ? document->body()->renderer() : 0;
1238         if (bodyRenderer && !document->writingModeSetOnDocumentElement())
1239             documentStyle->setWritingMode(bodyRenderer->style()->writingMode());
1240         else
1241             documentStyle->setWritingMode(docElementRenderer->style()->writingMode());
1242         if (bodyRenderer && !document->directionSetOnDocumentElement())
1243             documentStyle->setDirection(bodyRenderer->style()->direction());
1244         else
1245             documentStyle->setDirection(docElementRenderer->style()->direction());
1246     }
1247
1248     FontDescription fontDescription;
1249     fontDescription.setUsePrinterFont(document->printing());
1250     if (Settings* settings = document->settings()) {
1251         fontDescription.setRenderingMode(settings->fontRenderingMode());
1252         if (document->printing() && !settings->shouldPrintBackgrounds())
1253             documentStyle->setForceBackgroundsToWhite(true);
1254         const AtomicString& stdfont = settings->standardFontFamily();
1255         if (!stdfont.isEmpty()) {
1256             fontDescription.firstFamily().setFamily(stdfont);
1257             fontDescription.firstFamily().appendFamily(0);
1258         }
1259         fontDescription.setKeywordSize(CSSValueMedium - CSSValueXxSmall + 1);
1260         int size = CSSStyleSelector::fontSizeForKeyword(document, CSSValueMedium, false);
1261         fontDescription.setSpecifiedSize(size);
1262         bool useSVGZoomRules = document->isSVGDocument();
1263         fontDescription.setComputedSize(CSSStyleSelector::getComputedSizeFromSpecifiedSize(document, documentStyle.get(), fontDescription.isAbsoluteSize(), size, useSVGZoomRules));
1264     }
1265
1266     documentStyle->setFontDescription(fontDescription);
1267     documentStyle->font().update(0);
1268         
1269     return documentStyle.release();
1270 }
1271
1272 // If resolveForRootDefault is true, style based on user agent style sheet only. This is used in media queries, where
1273 // relative units are interpreted according to document root element style, styled only with UA stylesheet
1274
1275 PassRefPtr<RenderStyle> CSSStyleSelector::styleForElement(Element* e, RenderStyle* defaultParent, bool allowSharing, bool resolveForRootDefault, bool matchVisitedPseudoClass)
1276 {
1277     // Once an element has a renderer, we don't try to destroy it, since otherwise the renderer
1278     // will vanish if a style recalc happens during loading.
1279     if (allowSharing && !e->document()->haveStylesheetsLoaded() && !e->renderer()) {
1280         if (!s_styleNotYetAvailable) {
1281             s_styleNotYetAvailable = RenderStyle::create().releaseRef();
1282             s_styleNotYetAvailable->ref();
1283             s_styleNotYetAvailable->setDisplay(NONE);
1284             s_styleNotYetAvailable->font().update(m_fontSelector);
1285         }
1286         s_styleNotYetAvailable->ref();
1287         e->document()->setHasNodesWithPlaceholderStyle();
1288         return s_styleNotYetAvailable;
1289     }
1290
1291     initElement(e);
1292     initForStyleResolve(e, defaultParent);
1293     if (allowSharing) {
1294         RenderStyle* sharedStyle = locateSharedStyle();
1295         if (sharedStyle)
1296             return sharedStyle;
1297     }
1298
1299     // Compute our style allowing :visited to match first.
1300     RefPtr<RenderStyle> visitedStyle;
1301     if (!matchVisitedPseudoClass && m_parentStyle && (m_parentStyle->insideLink() || e->isLink()) && e->document()->usesLinkRules()) {
1302         // Fetch our parent style.
1303         RenderStyle* parentStyle = m_parentStyle;
1304         if (!e->isLink()) {
1305             // Use the parent's visited style if one exists.
1306             RenderStyle* parentVisitedStyle = m_parentStyle->getCachedPseudoStyle(VISITED_LINK);
1307             if (parentVisitedStyle)
1308                 parentStyle = parentVisitedStyle;
1309         }
1310         visitedStyle = styleForElement(e, parentStyle, false, false, true);
1311         initForStyleResolve(e, defaultParent);
1312     }
1313
1314     m_checker.m_matchVisitedPseudoClass = matchVisitedPseudoClass;
1315
1316     m_style = RenderStyle::create();
1317
1318     if (m_parentStyle)
1319         m_style->inheritFrom(m_parentStyle);
1320     else
1321         m_parentStyle = style();
1322
1323     if (e->isLink()) {
1324         m_style->setIsLink(true);
1325         m_style->setInsideLink(m_elementLinkState);
1326     }
1327     
1328     if (visitedStyle) {
1329         // Copy any pseudo bits that the visited style has to the primary style so that
1330         // pseudo element styles will continue to work for pseudo elements inside :visited
1331         // links.
1332         for (unsigned pseudo = FIRST_PUBLIC_PSEUDOID; pseudo < FIRST_INTERNAL_PSEUDOID; ++pseudo) {
1333             if (visitedStyle->hasPseudoStyle(static_cast<PseudoId>(pseudo)))
1334                 m_style->setHasPseudoStyle(static_cast<PseudoId>(pseudo));
1335         }
1336         if (m_elementLinkState == InsideUnvisitedLink)
1337             visitedStyle = 0;  // We made the style to avoid timing attacks. Just throw it away now that we did that, since we don't need it.
1338         else
1339             visitedStyle->setStyleType(VISITED_LINK);
1340     }
1341
1342     if (simpleDefaultStyleSheet && !elementCanUseSimpleDefaultStyle(e)) {
1343         loadFullDefaultStyle();
1344         assertNoSiblingRulesInDefaultStyle();
1345     }
1346
1347 #if ENABLE(SVG)
1348     static bool loadedSVGUserAgentSheet;
1349     if (e->isSVGElement() && !loadedSVGUserAgentSheet) {
1350         // SVG rules.
1351         loadedSVGUserAgentSheet = true;
1352         CSSStyleSheet* svgSheet = parseUASheet(svgUserAgentStyleSheet, sizeof(svgUserAgentStyleSheet));
1353         defaultStyle->addRulesFromSheet(svgSheet, screenEval());
1354         defaultPrintStyle->addRulesFromSheet(svgSheet, printEval());
1355         assertNoSiblingRulesInDefaultStyle();
1356     }
1357 #endif
1358
1359 #if ENABLE(MATHML)
1360     static bool loadedMathMLUserAgentSheet;
1361     if (e->isMathMLElement() && !loadedMathMLUserAgentSheet) {
1362         // MathML rules.
1363         loadedMathMLUserAgentSheet = true;
1364         CSSStyleSheet* mathMLSheet = parseUASheet(mathmlUserAgentStyleSheet, sizeof(mathmlUserAgentStyleSheet));
1365         defaultStyle->addRulesFromSheet(mathMLSheet, screenEval());
1366         defaultPrintStyle->addRulesFromSheet(mathMLSheet, printEval());
1367         // There are some sibling rules here.
1368         collectSiblingRulesInDefaultStyle();
1369     }
1370 #endif
1371
1372 #if ENABLE(VIDEO)
1373     static bool loadedMediaStyleSheet;
1374     if (!loadedMediaStyleSheet && (e->hasTagName(videoTag) || e->hasTagName(audioTag))) {
1375         loadedMediaStyleSheet = true;
1376         String mediaRules = String(mediaControlsUserAgentStyleSheet, sizeof(mediaControlsUserAgentStyleSheet)) + RenderTheme::themeForPage(e->document()->page())->extraMediaControlsStyleSheet();
1377         CSSStyleSheet* mediaControlsSheet = parseUASheet(mediaRules);
1378         defaultStyle->addRulesFromSheet(mediaControlsSheet, screenEval());
1379         defaultPrintStyle->addRulesFromSheet(mediaControlsSheet, printEval());
1380         assertNoSiblingRulesInDefaultStyle();
1381     }
1382 #endif
1383
1384 #if ENABLE(FULLSCREEN_API)
1385     static bool loadedFullScreenStyleSheet;
1386     if (!loadedFullScreenStyleSheet && e->document()->webkitIsFullScreen()) {
1387         loadedFullScreenStyleSheet = true;
1388         String fullscreenRules = String(fullscreenUserAgentStyleSheet, sizeof(fullscreenUserAgentStyleSheet)) + RenderTheme::defaultTheme()->extraFullScreenStyleSheet();
1389         CSSStyleSheet* fullscreenSheet = parseUASheet(fullscreenRules);
1390         defaultStyle->addRulesFromSheet(fullscreenSheet, screenEval());
1391         defaultQuirksStyle->addRulesFromSheet(fullscreenSheet, screenEval());
1392     }
1393 #endif
1394
1395     int firstUARule = -1, lastUARule = -1;
1396     int firstUserRule = -1, lastUserRule = -1;
1397     int firstAuthorRule = -1, lastAuthorRule = -1;
1398     matchUARules(firstUARule, lastUARule);
1399
1400     if (!resolveForRootDefault) {
1401         // 4. Now we check user sheet rules.
1402         if (m_matchAuthorAndUserStyles)
1403             matchRules(m_userStyle.get(), firstUserRule, lastUserRule, false);
1404
1405         // 5. Now check author rules, beginning first with presentational attributes
1406         // mapped from HTML.
1407         if (m_styledElement) {
1408             // Ask if the HTML element has mapped attributes.
1409             if (m_styledElement->hasMappedAttributes()) {
1410                 // Walk our attribute list and add in each decl.
1411                 const NamedNodeMap* map = m_styledElement->attributeMap();
1412                 for (unsigned i = 0; i < map->length(); i++) {
1413                     Attribute* attr = map->attributeItem(i);
1414                     if (attr->isMappedAttribute() && attr->decl()) {
1415                         lastAuthorRule = m_matchedDecls.size();
1416                         if (firstAuthorRule == -1)
1417                             firstAuthorRule = lastAuthorRule;
1418                         addMatchedDeclaration(attr->decl());
1419                     }
1420                 }
1421             }
1422
1423             // Now we check additional mapped declarations.
1424             // Tables and table cells share an additional mapped rule that must be applied
1425             // after all attributes, since their mapped style depends on the values of multiple attributes.
1426             if (m_styledElement->canHaveAdditionalAttributeStyleDecls()) {
1427                 m_additionalAttributeStyleDecls.clear();
1428                 m_styledElement->additionalAttributeStyleDecls(m_additionalAttributeStyleDecls);
1429                 if (!m_additionalAttributeStyleDecls.isEmpty()) {
1430                     unsigned additionalDeclsSize = m_additionalAttributeStyleDecls.size();
1431                     if (firstAuthorRule == -1)
1432                         firstAuthorRule = m_matchedDecls.size();
1433                     lastAuthorRule = m_matchedDecls.size() + additionalDeclsSize - 1;
1434                     for (unsigned i = 0; i < additionalDeclsSize; i++)
1435                         addMatchedDeclaration(m_additionalAttributeStyleDecls[i]);
1436                 }
1437             }
1438             if (m_styledElement->isHTMLElement()) {
1439                 bool isAuto;
1440                 TextDirection textDirection = toHTMLElement(m_styledElement)->directionalityIfhasDirAutoAttribute(isAuto);
1441                 if (isAuto)
1442                     addMatchedDeclaration(textDirection == LTR ? leftToRightDeclaration() : rightToLeftDeclaration());
1443             }
1444         }
1445     
1446         // 6. Check the rules in author sheets next.
1447         if (m_matchAuthorAndUserStyles)
1448             matchRules(m_authorStyle.get(), firstAuthorRule, lastAuthorRule, false);
1449
1450         // 7. Now check our inline style attribute.
1451         if (m_matchAuthorAndUserStyles && m_styledElement) {
1452             CSSMutableStyleDeclaration* inlineDecl = m_styledElement->inlineStyleDecl();
1453             if (inlineDecl) {
1454                 lastAuthorRule = m_matchedDecls.size();
1455                 if (firstAuthorRule == -1)
1456                     firstAuthorRule = lastAuthorRule;
1457                 addMatchedDeclaration(inlineDecl);
1458             }
1459         }
1460     }
1461
1462     // Reset the value back before applying properties, so that -webkit-link knows what color to use.
1463     m_checker.m_matchVisitedPseudoClass = matchVisitedPseudoClass;
1464     
1465     // Now we have all of the matched rules in the appropriate order.  Walk the rules and apply
1466     // high-priority properties first, i.e., those properties that other properties depend on.
1467     // The order is (1) high-priority not important, (2) high-priority important, (3) normal not important
1468     // and (4) normal important.
1469     m_lineHeightValue = 0;
1470     applyDeclarations<true>(false, 0, m_matchedDecls.size() - 1);
1471     if (!resolveForRootDefault) {
1472         applyDeclarations<true>(true, firstAuthorRule, lastAuthorRule);
1473         applyDeclarations<true>(true, firstUserRule, lastUserRule);
1474     }
1475     applyDeclarations<true>(true, firstUARule, lastUARule);
1476     
1477     // If our font got dirtied, go ahead and update it now.
1478     if (m_fontDirty)
1479         updateFont();
1480
1481     // Line-height is set when we are sure we decided on the font-size
1482     if (m_lineHeightValue)
1483         applyProperty(CSSPropertyLineHeight, m_lineHeightValue);
1484
1485     // Now do the normal priority UA properties.
1486     applyDeclarations<false>(false, firstUARule, lastUARule);
1487     
1488     // Cache our border and background so that we can examine them later.
1489     cacheBorderAndBackground();
1490     
1491     // Now do the author and user normal priority properties and all the !important properties.
1492     if (!resolveForRootDefault) {
1493         applyDeclarations<false>(false, lastUARule + 1, m_matchedDecls.size() - 1);
1494         applyDeclarations<false>(true, firstAuthorRule, lastAuthorRule);
1495         applyDeclarations<false>(true, firstUserRule, lastUserRule);
1496     }
1497     applyDeclarations<false>(true, firstUARule, lastUARule);
1498
1499     ASSERT(!m_fontDirty);
1500     // If our font got dirtied by one of the non-essential font props, 
1501     // go ahead and update it a second time.
1502     if (m_fontDirty)
1503         updateFont();
1504     
1505     // Clean up our style object's display and text decorations (among other fixups).
1506     adjustRenderStyle(style(), m_parentStyle, e);
1507
1508     // Start loading images referenced by this style.
1509     loadPendingImages();
1510
1511     // If we have first-letter pseudo style, do not share this style
1512     if (m_style->hasPseudoStyle(FIRST_LETTER))
1513         m_style->setUnique();
1514
1515     if (visitedStyle) {
1516         // Add the visited style off the main style.
1517         m_style->addCachedPseudoStyle(visitedStyle.release());
1518     }
1519
1520     if (!matchVisitedPseudoClass)
1521         initElement(0); // Clear out for the next resolve.
1522
1523     // Now return the style.
1524     return m_style.release();
1525 }
1526
1527 PassRefPtr<RenderStyle> CSSStyleSelector::styleForKeyframe(const RenderStyle* elementStyle, const WebKitCSSKeyframeRule* keyframeRule, KeyframeValue& keyframe)
1528 {
1529     if (keyframeRule->style())
1530         addMatchedDeclaration(keyframeRule->style());
1531
1532     ASSERT(!m_style);
1533
1534     // Create the style
1535     m_style = RenderStyle::clone(elementStyle);
1536
1537     m_lineHeightValue = 0;
1538
1539     // We don't need to bother with !important. Since there is only ever one
1540     // decl, there's nothing to override. So just add the first properties.
1541     if (keyframeRule->style())
1542         applyDeclarations<true>(false, 0, m_matchedDecls.size() - 1);
1543
1544     // If our font got dirtied, go ahead and update it now.
1545     if (m_fontDirty)
1546         updateFont();
1547
1548     // Line-height is set when we are sure we decided on the font-size
1549     if (m_lineHeightValue)
1550         applyProperty(CSSPropertyLineHeight, m_lineHeightValue);
1551
1552     // Now do rest of the properties.
1553     if (keyframeRule->style())
1554         applyDeclarations<false>(false, 0, m_matchedDecls.size() - 1);
1555
1556     // If our font got dirtied by one of the non-essential font props,
1557     // go ahead and update it a second time.
1558     if (m_fontDirty)
1559         updateFont();
1560
1561     // Start loading images referenced by this style.
1562     loadPendingImages();
1563
1564     // Add all the animating properties to the keyframe.
1565     if (keyframeRule->style()) {
1566         CSSMutableStyleDeclaration::const_iterator end = keyframeRule->style()->end();
1567         for (CSSMutableStyleDeclaration::const_iterator it = keyframeRule->style()->begin(); it != end; ++it) {
1568             int property = (*it).id();
1569             // Timing-function within keyframes is special, because it is not animated; it just
1570             // describes the timing function between this keyframe and the next.
1571             if (property != CSSPropertyWebkitAnimationTimingFunction)
1572                 keyframe.addProperty(property);
1573         }
1574     }
1575
1576     return m_style.release();
1577 }
1578
1579 void CSSStyleSelector::keyframeStylesForAnimation(Element* e, const RenderStyle* elementStyle, KeyframeList& list)
1580 {
1581     list.clear();
1582     
1583     // Get the keyframesRule for this name
1584     if (!e || list.animationName().isEmpty())
1585         return;
1586
1587     m_keyframesRuleMap.checkConsistency();
1588    
1589     if (!m_keyframesRuleMap.contains(list.animationName().impl()))
1590         return;
1591         
1592     const WebKitCSSKeyframesRule* rule = m_keyframesRuleMap.find(list.animationName().impl()).get()->second.get();
1593     
1594     // Construct and populate the style for each keyframe
1595     for (unsigned i = 0; i < rule->length(); ++i) {
1596         // Apply the declaration to the style. This is a simplified version of the logic in styleForElement
1597         initElement(e);
1598         initForStyleResolve(e);
1599         
1600         const WebKitCSSKeyframeRule* keyframeRule = rule->item(i);
1601
1602         KeyframeValue keyframe(0, 0);
1603         keyframe.setStyle(styleForKeyframe(elementStyle, keyframeRule, keyframe));
1604
1605         // Add this keyframe style to all the indicated key times
1606         Vector<float> keys;
1607         keyframeRule->getKeys(keys);
1608         for (size_t keyIndex = 0; keyIndex < keys.size(); ++keyIndex) {
1609             keyframe.setKey(keys[keyIndex]);
1610             list.insert(keyframe);
1611         }
1612     }
1613     
1614     // If the 0% keyframe is missing, create it (but only if there is at least one other keyframe)
1615     int initialListSize = list.size();
1616     if (initialListSize > 0 && list[0].key() != 0) {
1617         RefPtr<WebKitCSSKeyframeRule> keyframeRule = WebKitCSSKeyframeRule::create();
1618         keyframeRule->setKeyText("0%");
1619         KeyframeValue keyframe(0, 0);
1620         keyframe.setStyle(styleForKeyframe(elementStyle, keyframeRule.get(), keyframe));
1621         list.insert(keyframe);
1622     }
1623
1624     // If the 100% keyframe is missing, create it (but only if there is at least one other keyframe)
1625     if (initialListSize > 0 && (list[list.size() - 1].key() != 1)) {
1626         RefPtr<WebKitCSSKeyframeRule> keyframeRule = WebKitCSSKeyframeRule::create();
1627         keyframeRule->setKeyText("100%");
1628         KeyframeValue keyframe(1, 0);
1629         keyframe.setStyle(styleForKeyframe(elementStyle, keyframeRule.get(), keyframe));
1630         list.insert(keyframe);
1631     }
1632 }
1633
1634 PassRefPtr<RenderStyle> CSSStyleSelector::pseudoStyleForElement(PseudoId pseudo, Element* e, RenderStyle* parentStyle, bool matchVisitedPseudoClass)
1635 {
1636     if (!e)
1637         return 0;
1638
1639     initElement(e);
1640
1641     // Compute our :visited style first, so that we know whether or not we'll need to create a normal style just to hang it
1642     // off of.
1643     RefPtr<RenderStyle> visitedStyle;
1644     if (!matchVisitedPseudoClass && parentStyle && parentStyle->insideLink()) {
1645         // Fetch our parent style with :visited in effect.
1646         RenderStyle* parentVisitedStyle = parentStyle->getCachedPseudoStyle(VISITED_LINK);
1647         visitedStyle = pseudoStyleForElement(pseudo, e, parentVisitedStyle ? parentVisitedStyle : parentStyle, true);
1648         if (visitedStyle)
1649             visitedStyle->setStyleType(VISITED_LINK);
1650     }
1651
1652     initForStyleResolve(e, parentStyle, pseudo);
1653     m_style = RenderStyle::create();
1654     if (parentStyle)
1655         m_style->inheritFrom(parentStyle);
1656
1657     m_checker.m_matchVisitedPseudoClass = matchVisitedPseudoClass;
1658
1659     // Since we don't use pseudo-elements in any of our quirk/print user agent rules, don't waste time walking
1660     // those rules.
1661     
1662     // Check UA, user and author rules.
1663     int firstUARule = -1, lastUARule = -1, firstUserRule = -1, lastUserRule = -1, firstAuthorRule = -1, lastAuthorRule = -1;
1664     matchUARules(firstUARule, lastUARule);
1665
1666     if (m_matchAuthorAndUserStyles) {
1667         matchRules(m_userStyle.get(), firstUserRule, lastUserRule, false);
1668         matchRules(m_authorStyle.get(), firstAuthorRule, lastAuthorRule, false);
1669     }
1670
1671     if (m_matchedDecls.isEmpty() && !visitedStyle)
1672         return 0;
1673
1674     m_style->setStyleType(pseudo);
1675     
1676     m_lineHeightValue = 0;
1677     
1678     // Reset the value back before applying properties, so that -webkit-link knows what color to use.
1679     m_checker.m_matchVisitedPseudoClass = matchVisitedPseudoClass;
1680
1681     // High-priority properties.
1682     applyDeclarations<true>(false, 0, m_matchedDecls.size() - 1);
1683     applyDeclarations<true>(true, firstAuthorRule, lastAuthorRule);
1684     applyDeclarations<true>(true, firstUserRule, lastUserRule);
1685     applyDeclarations<true>(true, firstUARule, lastUARule);
1686     
1687     // If our font got dirtied, go ahead and update it now.
1688     if (m_fontDirty)
1689         updateFont();
1690
1691     // Line-height is set when we are sure we decided on the font-size
1692     if (m_lineHeightValue)
1693         applyProperty(CSSPropertyLineHeight, m_lineHeightValue);
1694     
1695     // Now do the normal priority properties.
1696     applyDeclarations<false>(false, firstUARule, lastUARule);
1697     
1698     // Cache our border and background so that we can examine them later.
1699     cacheBorderAndBackground();
1700     
1701     applyDeclarations<false>(false, lastUARule + 1, m_matchedDecls.size() - 1);
1702     applyDeclarations<false>(true, firstAuthorRule, lastAuthorRule);
1703     applyDeclarations<false>(true, firstUserRule, lastUserRule);
1704     applyDeclarations<false>(true, firstUARule, lastUARule);
1705     
1706     // If our font got dirtied by one of the non-essential font props, 
1707     // go ahead and update it a second time.
1708     if (m_fontDirty)
1709         updateFont();
1710
1711     // Clean up our style object's display and text decorations (among other fixups).
1712     adjustRenderStyle(style(), parentStyle, 0);
1713
1714     // Start loading images referenced by this style.
1715     loadPendingImages();
1716
1717     // Hang our visited style off m_style.
1718     if (visitedStyle)
1719         m_style->addCachedPseudoStyle(visitedStyle.release());
1720         
1721     // Now return the style.
1722     return m_style.release();
1723 }
1724
1725 PassRefPtr<RenderStyle> CSSStyleSelector::styleForPage(int pageIndex)
1726 {
1727     initForStyleResolve(m_checker.m_document->documentElement()); // m_rootElementStyle will be set to the document style.
1728
1729     m_style = RenderStyle::create();
1730     m_style->inheritFrom(m_rootElementStyle);
1731
1732     const bool isLeft = isLeftPage(pageIndex);
1733     const bool isFirst = isFirstPage(pageIndex);
1734     const String page = pageName(pageIndex);
1735     matchPageRules(defaultPrintStyle, isLeft, isFirst, page);
1736     matchPageRules(m_userStyle.get(), isLeft, isFirst, page);
1737     matchPageRules(m_authorStyle.get(), isLeft, isFirst, page);
1738     m_lineHeightValue = 0;
1739     applyDeclarations<true>(false, 0, m_matchedDecls.size() - 1);
1740
1741     // If our font got dirtied, go ahead and update it now.
1742     if (m_fontDirty)
1743         updateFont();
1744
1745     // Line-height is set when we are sure we decided on the font-size
1746     if (m_lineHeightValue)
1747         applyProperty(CSSPropertyLineHeight, m_lineHeightValue);
1748
1749     applyDeclarations<false>(false, 0, m_matchedDecls.size() - 1);
1750
1751     // Start loading images referenced by this style.
1752     loadPendingImages();
1753
1754     // Now return the style.
1755     return m_style.release();
1756 }
1757
1758 static void addIntrinsicMargins(RenderStyle* style)
1759 {
1760     // Intrinsic margin value.
1761     const int intrinsicMargin = 2 * style->effectiveZoom();
1762     
1763     // FIXME: Using width/height alone and not also dealing with min-width/max-width is flawed.
1764     // FIXME: Using "quirk" to decide the margin wasn't set is kind of lame.
1765     if (style->width().isIntrinsicOrAuto()) {
1766         if (style->marginLeft().quirk())
1767             style->setMarginLeft(Length(intrinsicMargin, Fixed));
1768         if (style->marginRight().quirk())
1769             style->setMarginRight(Length(intrinsicMargin, Fixed));
1770     }
1771
1772     if (style->height().isAuto()) {
1773         if (style->marginTop().quirk())
1774             style->setMarginTop(Length(intrinsicMargin, Fixed));
1775         if (style->marginBottom().quirk())
1776             style->setMarginBottom(Length(intrinsicMargin, Fixed));
1777     }
1778 }
1779
1780 static inline bool isAtShadowBoundary(Element* element)
1781 {
1782     if (!element)
1783         return false;
1784
1785     ContainerNode* parentNode = element->parentNode();
1786     return parentNode && parentNode->isShadowBoundary();
1787 }
1788
1789 void CSSStyleSelector::adjustRenderStyle(RenderStyle* style, RenderStyle* parentStyle, Element *e)
1790 {
1791     // Cache our original display.
1792     style->setOriginalDisplay(style->display());
1793
1794     if (style->display() != NONE) {
1795         // If we have a <td> that specifies a float property, in quirks mode we just drop the float
1796         // property.
1797         // Sites also commonly use display:inline/block on <td>s and <table>s.  In quirks mode we force
1798         // these tags to retain their display types.
1799         if (!m_checker.m_strictParsing && e) {
1800             if (e->hasTagName(tdTag)) {
1801                 style->setDisplay(TABLE_CELL);
1802                 style->setFloating(FNONE);
1803             }
1804             else if (e->hasTagName(tableTag))
1805                 style->setDisplay(style->isDisplayInlineType() ? INLINE_TABLE : TABLE);
1806         }
1807
1808         if (e && (e->hasTagName(tdTag) || e->hasTagName(thTag))) {
1809             if (style->whiteSpace() == KHTML_NOWRAP) {
1810                 // Figure out if we are really nowrapping or if we should just
1811                 // use normal instead.  If the width of the cell is fixed, then
1812                 // we don't actually use NOWRAP.
1813                 if (style->width().isFixed())
1814                     style->setWhiteSpace(NORMAL);
1815                 else
1816                     style->setWhiteSpace(NOWRAP);
1817             }
1818         }
1819
1820         // Tables never support the -webkit-* values for text-align and will reset back to the default.
1821         if (e && e->hasTagName(tableTag) && (style->textAlign() == WEBKIT_LEFT || style->textAlign() == WEBKIT_CENTER || style->textAlign() == WEBKIT_RIGHT))
1822             style->setTextAlign(TAAUTO);
1823
1824         // Frames and framesets never honor position:relative or position:absolute.  This is necessary to
1825         // fix a crash where a site tries to position these objects.  They also never honor display.
1826         if (e && (e->hasTagName(frameTag) || e->hasTagName(framesetTag))) {
1827             style->setPosition(StaticPosition);
1828             style->setDisplay(BLOCK);
1829         }
1830
1831         // Table headers with a text-align of auto will change the text-align to center.
1832         if (e && e->hasTagName(thTag) && style->textAlign() == TAAUTO)
1833             style->setTextAlign(CENTER);
1834
1835         if (e && e->hasTagName(legendTag))
1836             style->setDisplay(BLOCK);
1837
1838         // Mutate the display to BLOCK or TABLE for certain cases, e.g., if someone attempts to
1839         // position or float an inline, compact, or run-in.  Cache the original display, since it
1840         // may be needed for positioned elements that have to compute their static normal flow
1841         // positions.  We also force inline-level roots to be block-level.
1842         if (style->display() != BLOCK && style->display() != TABLE && style->display() != BOX &&
1843             (style->position() == AbsolutePosition || style->position() == FixedPosition || style->floating() != FNONE ||
1844              (e && e->document()->documentElement() == e))) {
1845             if (style->display() == INLINE_TABLE)
1846                 style->setDisplay(TABLE);
1847             else if (style->display() == INLINE_BOX)
1848                 style->setDisplay(BOX);
1849             else if (style->display() == LIST_ITEM) {
1850                 // It is a WinIE bug that floated list items lose their bullets, so we'll emulate the quirk,
1851                 // but only in quirks mode.
1852                 if (!m_checker.m_strictParsing && style->floating() != FNONE)
1853                     style->setDisplay(BLOCK);
1854             }
1855             else
1856                 style->setDisplay(BLOCK);
1857         }
1858         
1859         // FIXME: Don't support this mutation for pseudo styles like first-letter or first-line, since it's not completely
1860         // clear how that should work.
1861         if (style->display() == INLINE && style->styleType() == NOPSEUDO && parentStyle && style->writingMode() != parentStyle->writingMode())
1862             style->setDisplay(INLINE_BLOCK);
1863         
1864         // After performing the display mutation, check table rows.  We do not honor position:relative on
1865         // table rows or cells.  This has been established in CSS2.1 (and caused a crash in containingBlock()
1866         // on some sites).
1867         if ((style->display() == TABLE_HEADER_GROUP || style->display() == TABLE_ROW_GROUP
1868              || style->display() == TABLE_FOOTER_GROUP || style->display() == TABLE_ROW) &&
1869              style->position() == RelativePosition)
1870             style->setPosition(StaticPosition);
1871
1872         // writing-mode does not apply to table row groups, table column groups, table rows, and table columns.
1873         // FIXME: Table cells should be allowed to be perpendicular or flipped with respect to the table, though.
1874         if (style->display() == TABLE_COLUMN || style->display() == TABLE_COLUMN_GROUP || style->display() == TABLE_FOOTER_GROUP
1875             || style->display() == TABLE_HEADER_GROUP || style->display() == TABLE_ROW || style->display() == TABLE_ROW_GROUP
1876             || style->display() == TABLE_CELL)
1877             style->setWritingMode(parentStyle->writingMode());
1878
1879         // FIXME: Since we don't support block-flow on flexible boxes yet, disallow setting
1880         // of block-flow to anything other than TopToBottomWritingMode.
1881         // https://bugs.webkit.org/show_bug.cgi?id=46418 - Flexible box support.
1882         if (style->writingMode() != TopToBottomWritingMode && (style->display() == BOX || style->display() == INLINE_BOX))
1883             style->setWritingMode(TopToBottomWritingMode);
1884     }
1885
1886     // Make sure our z-index value is only applied if the object is positioned.
1887     if (style->position() == StaticPosition)
1888         style->setHasAutoZIndex();
1889
1890     // Auto z-index becomes 0 for the root element and transparent objects.  This prevents
1891     // cases where objects that should be blended as a single unit end up with a non-transparent
1892     // object wedged in between them.  Auto z-index also becomes 0 for objects that specify transforms/masks/reflections.
1893     if (style->hasAutoZIndex() && ((e && e->document()->documentElement() == e) || style->opacity() < 1.0f || 
1894         style->hasTransformRelatedProperty() || style->hasMask() || style->boxReflect()))
1895         style->setZIndex(0);
1896
1897     // Textarea considers overflow visible as auto.
1898     if (e && e->hasTagName(textareaTag)) {
1899         style->setOverflowX(style->overflowX() == OVISIBLE ? OAUTO : style->overflowX());
1900         style->setOverflowY(style->overflowY() == OVISIBLE ? OAUTO : style->overflowY());
1901     }
1902
1903     // Finally update our text decorations in effect, but don't allow text-decoration to percolate through
1904     // tables, inline blocks, inline tables, run-ins, or shadow DOM.
1905     if (style->display() == TABLE || style->display() == INLINE_TABLE || style->display() == RUN_IN
1906         || style->display() == INLINE_BLOCK || style->display() == INLINE_BOX || isAtShadowBoundary(e))
1907         style->setTextDecorationsInEffect(style->textDecoration());
1908     else
1909         style->addToTextDecorationsInEffect(style->textDecoration());
1910     
1911     // If either overflow value is not visible, change to auto.
1912     if (style->overflowX() == OMARQUEE && style->overflowY() != OMARQUEE)
1913         style->setOverflowY(OMARQUEE);
1914     else if (style->overflowY() == OMARQUEE && style->overflowX() != OMARQUEE)
1915         style->setOverflowX(OMARQUEE);
1916     else if (style->overflowX() == OVISIBLE && style->overflowY() != OVISIBLE)
1917         style->setOverflowX(OAUTO);
1918     else if (style->overflowY() == OVISIBLE && style->overflowX() != OVISIBLE)
1919         style->setOverflowY(OAUTO);
1920
1921     // Table rows, sections and the table itself will support overflow:hidden and will ignore scroll/auto.
1922     // FIXME: Eventually table sections will support auto and scroll.
1923     if (style->display() == TABLE || style->display() == INLINE_TABLE ||
1924         style->display() == TABLE_ROW_GROUP || style->display() == TABLE_ROW) {
1925         if (style->overflowX() != OVISIBLE && style->overflowX() != OHIDDEN) 
1926             style->setOverflowX(OVISIBLE);
1927         if (style->overflowY() != OVISIBLE && style->overflowY() != OHIDDEN) 
1928             style->setOverflowY(OVISIBLE);
1929     }
1930
1931     // Menulists should have visible overflow
1932     if (style->appearance() == MenulistPart) {
1933         style->setOverflowX(OVISIBLE);
1934         style->setOverflowY(OVISIBLE);
1935     }
1936
1937     // Cull out any useless layers and also repeat patterns into additional layers.
1938     style->adjustBackgroundLayers();
1939     style->adjustMaskLayers();
1940
1941     // Do the same for animations and transitions.
1942     style->adjustAnimations();
1943     style->adjustTransitions();
1944
1945     // Important: Intrinsic margins get added to controls before the theme has adjusted the style, since the theme will
1946     // alter fonts and heights/widths.
1947     if (e && e->isFormControlElement() && style->fontSize() >= 11) {
1948         // Don't apply intrinsic margins to image buttons.  The designer knows how big the images are,
1949         // so we have to treat all image buttons as though they were explicitly sized.
1950         if (!e->hasTagName(inputTag) || !static_cast<HTMLInputElement*>(e)->isImageButton())
1951             addIntrinsicMargins(style);
1952     }
1953
1954     // Let the theme also have a crack at adjusting the style.
1955     if (style->hasAppearance())
1956         RenderTheme::defaultTheme()->adjustStyle(this, style, e, m_hasUAAppearance, m_borderData, m_backgroundData, m_backgroundColor);
1957
1958 #if ENABLE(SVG)
1959     if (e && e->isSVGElement()) {
1960         // Spec: http://www.w3.org/TR/SVG/masking.html#OverflowProperty
1961         if (style->overflowY() == OSCROLL)
1962             style->setOverflowY(OHIDDEN);
1963         else if (style->overflowY() == OAUTO)
1964             style->setOverflowY(OVISIBLE);
1965
1966         if (style->overflowX() == OSCROLL)
1967             style->setOverflowX(OHIDDEN);
1968         else if (style->overflowX() == OAUTO)
1969             style->setOverflowX(OVISIBLE);
1970
1971         // Only the root <svg> element in an SVG document fragment tree honors css position
1972         if (!(e->hasTagName(SVGNames::svgTag) && e->parentNode() && !e->parentNode()->isSVGElement()))
1973             style->setPosition(RenderStyle::initialPosition());
1974     }
1975 #endif
1976 }
1977
1978 void CSSStyleSelector::updateFont()
1979 {
1980     checkForTextSizeAdjust();
1981     checkForGenericFamilyChange(style(), m_parentStyle);
1982     checkForZoomChange(style(), m_parentStyle);
1983     m_style->font().update(m_fontSelector);
1984     m_fontDirty = false;
1985 }
1986
1987 void CSSStyleSelector::cacheBorderAndBackground()
1988 {
1989     m_hasUAAppearance = m_style->hasAppearance();
1990     if (m_hasUAAppearance) {
1991         m_borderData = m_style->border();
1992         m_backgroundData = *m_style->backgroundLayers();
1993         m_backgroundColor = m_style->backgroundColor();
1994     }
1995 }
1996
1997 PassRefPtr<CSSRuleList> CSSStyleSelector::styleRulesForElement(Element* e, unsigned rulesToInclude)
1998 {
1999     return pseudoStyleRulesForElement(e, NOPSEUDO, rulesToInclude);
2000 }
2001
2002 PassRefPtr<CSSRuleList> CSSStyleSelector::pseudoStyleRulesForElement(Element* e, PseudoId pseudoId, unsigned rulesToInclude)
2003 {
2004     if (!e || !e->document()->haveStylesheetsLoaded())
2005         return 0;
2006
2007     m_checker.m_collectRulesOnly = true;
2008
2009     initElement(e);
2010     initForStyleResolve(e, 0, pseudoId);
2011
2012     if (rulesToInclude & UAAndUserCSSRules) {
2013         int firstUARule = -1, lastUARule = -1;
2014         // First we match rules from the user agent sheet.
2015         matchUARules(firstUARule, lastUARule);
2016
2017         // Now we check user sheet rules.
2018         if (m_matchAuthorAndUserStyles) {
2019             int firstUserRule = -1, lastUserRule = -1;
2020             matchRules(m_userStyle.get(), firstUserRule, lastUserRule, rulesToInclude & EmptyCSSRules);
2021         }
2022     }
2023
2024     if (m_matchAuthorAndUserStyles) {
2025         m_checker.m_sameOriginOnly = !(rulesToInclude & CrossOriginCSSRules);
2026
2027         // Check the rules in author sheets.
2028         int firstAuthorRule = -1, lastAuthorRule = -1;
2029         matchRules(m_authorStyle.get(), firstAuthorRule, lastAuthorRule, rulesToInclude & EmptyCSSRules);
2030
2031         m_checker.m_sameOriginOnly = false;
2032     }
2033
2034     m_checker.m_collectRulesOnly = false;
2035    
2036     return m_ruleList.release();
2037 }
2038
2039 inline bool CSSStyleSelector::checkSelector(const RuleData& ruleData)
2040 {
2041     m_dynamicPseudo = NOPSEUDO;
2042     m_checker.m_hasUnknownPseudoElements = false;
2043
2044     // Let the slow path handle SVG as it has some additional rules regarding shadow trees.
2045     if (ruleData.hasFastCheckableSelector() && !m_element->isSVGElement()) {
2046         // We know this selector does not include any pseudo selectors.
2047         if (m_checker.m_pseudoStyle != NOPSEUDO)
2048             return false;
2049         // We know a sufficiently simple single part selector matches simply because we found it from the rule hash.
2050         // This is limited to HTML only so we don't need to check the namespace.
2051         if (ruleData.hasTopSelectorMatchingHTMLBasedOnRuleHash() && !ruleData.hasMultipartSelector() && m_element->isHTMLElement())
2052             return true;
2053         return SelectorChecker::fastCheckSelector(ruleData.selector(), m_element);
2054     }
2055
2056     // Slow path.
2057     SelectorMatch match = m_checker.checkSelector(ruleData.selector(), m_element, m_dynamicPseudo, false, false, style(), m_parentNode ? m_parentNode->renderStyle() : 0);
2058     if (match != SelectorMatches)
2059         return false;
2060     if (m_checker.m_pseudoStyle != NOPSEUDO && m_checker.m_pseudoStyle != m_dynamicPseudo)
2061         return false;
2062     return true;
2063 }
2064     
2065 namespace {
2066
2067 inline bool selectorTagMatches(const Element* element, const CSSSelector* selector)
2068 {
2069     if (!selector->hasTag())
2070         return true;
2071     const AtomicString& localName = selector->tag().localName();
2072     if (localName != starAtom && localName != element->localName())
2073         return false;
2074     const AtomicString& namespaceURI = selector->tag().namespaceURI();
2075     return namespaceURI == starAtom || namespaceURI == element->namespaceURI();
2076 }
2077
2078 inline bool isFastCheckableSelector(const CSSSelector* selector)
2079 {
2080     for (; selector; selector = selector->tagHistory()) {
2081         if (selector->relation() != CSSSelector::Descendant && selector->relation() != CSSSelector::Child && selector->relation() != CSSSelector::SubSelector)
2082             return false;
2083         if (selector->m_match != CSSSelector::None && selector->m_match != CSSSelector::Id && selector->m_match != CSSSelector::Class)
2084             return false;
2085     }
2086     return true;
2087 }
2088     
2089 template <bool checkValue(const Element*, AtomicStringImpl*)>
2090 inline bool fastCheckSingleSelector(const CSSSelector*& selector, const Element*& element, const CSSSelector*& topChildOrSubselector, const Element*& topChildOrSubselectorMatchElement)
2091 {
2092     AtomicStringImpl* value = selector->value().impl();
2093     for (; element; element = element->parentElement()) {
2094         if (checkValue(element, value) && selectorTagMatches(element, selector)) {
2095             if (selector->relation() == CSSSelector::Descendant)
2096                 topChildOrSubselector = 0;
2097             else if (!topChildOrSubselector) {
2098                 ASSERT(selector->relation() == CSSSelector::Child || selector->relation() == CSSSelector::SubSelector);
2099                 topChildOrSubselector = selector;
2100                 topChildOrSubselectorMatchElement = element;
2101             }
2102             if (selector->relation() != CSSSelector::SubSelector)
2103                 element = element->parentElement();
2104             selector = selector->tagHistory();
2105             return true;
2106         }
2107         if (topChildOrSubselector) {
2108             // Child or subselector check failed.
2109             // If the match element is null, topChildOrSubselector was also the very topmost selector and had to match 
2110             // the original element we were checking.
2111             if (!topChildOrSubselectorMatchElement)
2112                 return false;
2113             // There may be other matches down the ancestor chain.
2114             // Rewind to the topmost child or subselector and the element it matched, continue checking ancestors.
2115             selector = topChildOrSubselector;
2116             element = topChildOrSubselectorMatchElement->parentElement();
2117             topChildOrSubselector = 0;
2118             return true;
2119         }
2120     }
2121     return false;
2122 }
2123
2124 inline bool checkClassValue(const Element* element, AtomicStringImpl* value) 
2125 {
2126     return element->hasClass() && static_cast<const StyledElement*>(element)->classNames().contains(value);
2127 }
2128
2129 inline bool checkIDValue(const Element* element, AtomicStringImpl* value) 
2130 {
2131     return element->hasID() && element->idForStyleResolution().impl() == value;
2132 }
2133
2134 inline bool checkTagValue(const Element*, AtomicStringImpl*)
2135 {
2136     return true;
2137 }
2138
2139 }
2140
2141 bool CSSStyleSelector::SelectorChecker::fastCheckSelector(const CSSSelector* selector, const Element* element)
2142 {
2143     ASSERT(isFastCheckableSelector(selector));
2144
2145     // The top selector requires tag check only as rule hashes have already handled id and class matches.
2146     if (!selectorTagMatches(element, selector))
2147         return false;
2148
2149     const CSSSelector* topChildOrSubselector = 0;
2150     const Element* topChildOrSubselectorMatchElement = 0;
2151     if (selector->relation() == CSSSelector::Child || selector->relation() == CSSSelector::SubSelector)
2152         topChildOrSubselector = selector;
2153
2154     if (selector->relation() != CSSSelector::SubSelector)
2155         element = element->parentElement();
2156
2157     selector = selector->tagHistory();
2158
2159     // We know this compound selector has descendant, child and subselector combinators only and all components are simple.
2160     while (selector) {
2161         switch (selector->m_match) {
2162         case CSSSelector::Class:
2163             if (!fastCheckSingleSelector<checkClassValue>(selector, element, topChildOrSubselector, topChildOrSubselectorMatchElement))
2164                 return false;
2165             break;
2166         case CSSSelector::Id:
2167             if (!fastCheckSingleSelector<checkIDValue>(selector, element, topChildOrSubselector, topChildOrSubselectorMatchElement))
2168                 return false;
2169             break;
2170         case CSSSelector::None:
2171             if (!fastCheckSingleSelector<checkTagValue>(selector, element, topChildOrSubselector, topChildOrSubselectorMatchElement))
2172                 return false;
2173             break;
2174         default:
2175             ASSERT_NOT_REACHED();
2176         }
2177     }
2178     return true;
2179 }
2180
2181 // Recursive check of selectors and combinators
2182 // It can return 3 different values:
2183 // * SelectorMatches         - the selector matches the element e
2184 // * SelectorFailsLocally    - the selector fails for the element e
2185 // * SelectorFailsCompletely - the selector fails for e and any sibling or ancestor of e
2186 CSSStyleSelector::SelectorMatch CSSStyleSelector::SelectorChecker::checkSelector(CSSSelector* sel, Element* e, PseudoId& dynamicPseudo, bool isSubSelector, bool encounteredLink, RenderStyle* elementStyle, RenderStyle* elementParentStyle) const
2187 {
2188 #if ENABLE(SVG)
2189     // Spec: CSS2 selectors cannot be applied to the (conceptually) cloned DOM tree
2190     // because its contents are not part of the formal document structure.
2191     if (e->isSVGShadowRoot())
2192         return SelectorFailsCompletely;
2193 #endif
2194
2195     // first selector has to match
2196     if (!checkOneSelector(sel, e, dynamicPseudo, isSubSelector, encounteredLink, elementStyle, elementParentStyle))
2197         return SelectorFailsLocally;
2198
2199     // The rest of the selectors has to match
2200     CSSSelector::Relation relation = sel->relation();
2201
2202     // Prepare next sel
2203     sel = sel->tagHistory();
2204     if (!sel)
2205         return SelectorMatches;
2206
2207     if (relation != CSSSelector::SubSelector)
2208         // Bail-out if this selector is irrelevant for the pseudoStyle
2209         if (m_pseudoStyle != NOPSEUDO && m_pseudoStyle != dynamicPseudo)
2210             return SelectorFailsCompletely;
2211
2212     // Check for nested links.
2213     if (m_matchVisitedPseudoClass && !isSubSelector) {
2214         RenderStyle* currentStyle = elementStyle ? elementStyle : e->renderStyle();
2215         if (currentStyle && currentStyle->insideLink() && e->isLink()) {
2216             if (encounteredLink)
2217                 m_matchVisitedPseudoClass = false; // This link is not relevant to the style being resolved, so disable matching.
2218             else
2219                 encounteredLink = true;
2220         }
2221     }
2222
2223     switch (relation) {
2224         case CSSSelector::Descendant:
2225             while (true) {
2226                 ContainerNode* n = e->parentNode();
2227                 if (!n || !n->isElementNode())
2228                     return SelectorFailsCompletely;
2229                 e = static_cast<Element*>(n);
2230                 SelectorMatch match = checkSelector(sel, e, dynamicPseudo, false, encounteredLink);
2231                 if (match != SelectorFailsLocally)
2232                     return match;
2233             }
2234             break;
2235         case CSSSelector::Child:
2236         {
2237             ContainerNode* n = e->parentNode();
2238             if (!n || !n->isElementNode())
2239                 return SelectorFailsCompletely;
2240             e = static_cast<Element*>(n);
2241             return checkSelector(sel, e, dynamicPseudo, false, encounteredLink);
2242         }
2243         case CSSSelector::DirectAdjacent:
2244         {
2245             if (!m_collectRulesOnly && e->parentNode() && e->parentNode()->isElementNode()) {
2246                 RenderStyle* parentStyle = elementStyle ? elementParentStyle : e->parentNode()->renderStyle();
2247                 if (parentStyle)
2248                     parentStyle->setChildrenAffectedByDirectAdjacentRules();
2249             }
2250             Node* n = e->previousSibling();
2251             while (n && !n->isElementNode())
2252                 n = n->previousSibling();
2253             if (!n)
2254                 return SelectorFailsLocally;
2255             e = static_cast<Element*>(n);
2256             m_matchVisitedPseudoClass = false;
2257             return checkSelector(sel, e, dynamicPseudo, false, encounteredLink);
2258         }
2259         case CSSSelector::IndirectAdjacent:
2260             if (!m_collectRulesOnly && e->parentNode() && e->parentNode()->isElementNode()) {
2261                 RenderStyle* parentStyle = elementStyle ? elementParentStyle : e->parentNode()->renderStyle();
2262                 if (parentStyle)
2263                     parentStyle->setChildrenAffectedByForwardPositionalRules();
2264             }
2265             while (true) {
2266                 Node* n = e->previousSibling();
2267                 while (n && !n->isElementNode())
2268                     n = n->previousSibling();
2269                 if (!n)
2270                     return SelectorFailsLocally;
2271                 e = static_cast<Element*>(n);
2272                 m_matchVisitedPseudoClass = false;
2273                 SelectorMatch match = checkSelector(sel, e, dynamicPseudo, false, encounteredLink);
2274                 if (match != SelectorFailsLocally)
2275                     return match;
2276             };
2277             break;
2278         case CSSSelector::SubSelector:
2279             // a selector is invalid if something follows a pseudo-element
2280             // We make an exception for scrollbar pseudo elements and allow a set of pseudo classes (but nothing else)
2281             // to follow the pseudo elements.
2282             if ((elementStyle || m_collectRulesOnly) && dynamicPseudo != NOPSEUDO && dynamicPseudo != SELECTION &&
2283                 !((RenderScrollbar::scrollbarForStyleResolve() || dynamicPseudo == SCROLLBAR_CORNER || dynamicPseudo == RESIZER) && sel->m_match == CSSSelector::PseudoClass))
2284                 return SelectorFailsCompletely;
2285             return checkSelector(sel, e, dynamicPseudo, true, encounteredLink, elementStyle, elementParentStyle);
2286         case CSSSelector::ShadowDescendant:
2287         {
2288             Node* shadowHostNode = e->shadowAncestorNode();
2289             if (shadowHostNode == e || !shadowHostNode->isElementNode())
2290                 return SelectorFailsCompletely;
2291             e = static_cast<Element*>(shadowHostNode);
2292             return checkSelector(sel, e, dynamicPseudo, false, encounteredLink);
2293         }
2294     }
2295
2296     return SelectorFailsCompletely;
2297 }
2298
2299 static void addLocalNameToSet(HashSet<AtomicStringImpl*>* set, const QualifiedName& qName)
2300 {
2301     set->add(qName.localName().impl());
2302 }
2303
2304 static HashSet<AtomicStringImpl*>* createHtmlCaseInsensitiveAttributesSet()
2305 {
2306     // This is the list of attributes in HTML 4.01 with values marked as "[CI]" or case-insensitive
2307     // Mozilla treats all other values as case-sensitive, thus so do we.
2308     HashSet<AtomicStringImpl*>* attrSet = new HashSet<AtomicStringImpl*>;
2309
2310     addLocalNameToSet(attrSet, accept_charsetAttr);
2311     addLocalNameToSet(attrSet, acceptAttr);
2312     addLocalNameToSet(attrSet, alignAttr);
2313     addLocalNameToSet(attrSet, alinkAttr);
2314     addLocalNameToSet(attrSet, axisAttr);
2315     addLocalNameToSet(attrSet, bgcolorAttr);
2316     addLocalNameToSet(attrSet, charsetAttr);
2317     addLocalNameToSet(attrSet, checkedAttr);
2318     addLocalNameToSet(attrSet, clearAttr);
2319     addLocalNameToSet(attrSet, codetypeAttr);
2320     addLocalNameToSet(attrSet, colorAttr);
2321     addLocalNameToSet(attrSet, compactAttr);
2322     addLocalNameToSet(attrSet, declareAttr);
2323     addLocalNameToSet(attrSet, deferAttr);
2324     addLocalNameToSet(attrSet, dirAttr);
2325     addLocalNameToSet(attrSet, disabledAttr);
2326     addLocalNameToSet(attrSet, enctypeAttr);
2327     addLocalNameToSet(attrSet, faceAttr);
2328     addLocalNameToSet(attrSet, frameAttr);
2329     addLocalNameToSet(attrSet, hreflangAttr);
2330     addLocalNameToSet(attrSet, http_equivAttr);
2331     addLocalNameToSet(attrSet, langAttr);
2332     addLocalNameToSet(attrSet, languageAttr);
2333     addLocalNameToSet(attrSet, linkAttr);
2334     addLocalNameToSet(attrSet, mediaAttr);
2335     addLocalNameToSet(attrSet, methodAttr);
2336     addLocalNameToSet(attrSet, multipleAttr);
2337     addLocalNameToSet(attrSet, nohrefAttr);
2338     addLocalNameToSet(attrSet, noresizeAttr);
2339     addLocalNameToSet(attrSet, noshadeAttr);
2340     addLocalNameToSet(attrSet, nowrapAttr);
2341     addLocalNameToSet(attrSet, readonlyAttr);
2342     addLocalNameToSet(attrSet, relAttr);
2343     addLocalNameToSet(attrSet, revAttr);
2344     addLocalNameToSet(attrSet, rulesAttr);
2345     addLocalNameToSet(attrSet, scopeAttr);
2346     addLocalNameToSet(attrSet, scrollingAttr);
2347     addLocalNameToSet(attrSet, selectedAttr);
2348     addLocalNameToSet(attrSet, shapeAttr);
2349     addLocalNameToSet(attrSet, targetAttr);
2350     addLocalNameToSet(attrSet, textAttr);
2351     addLocalNameToSet(attrSet, typeAttr);
2352     addLocalNameToSet(attrSet, valignAttr);
2353     addLocalNameToSet(attrSet, valuetypeAttr);
2354     addLocalNameToSet(attrSet, vlinkAttr);
2355
2356     return attrSet;
2357 }
2358
2359 static bool htmlAttributeHasCaseInsensitiveValue(const QualifiedName& attr)
2360 {
2361     static HashSet<AtomicStringImpl*>* htmlCaseInsensitiveAttributesSet = createHtmlCaseInsensitiveAttributesSet();
2362     bool isPossibleHTMLAttr = !attr.hasPrefix() && (attr.namespaceURI() == nullAtom);
2363     return isPossibleHTMLAttr && htmlCaseInsensitiveAttributesSet->contains(attr.localName().impl());
2364 }
2365
2366 bool CSSStyleSelector::SelectorChecker::checkOneSelector(CSSSelector* sel, Element* e, PseudoId& dynamicPseudo, bool isSubSelector, bool encounteredLink, RenderStyle* elementStyle, RenderStyle* elementParentStyle) const
2367 {
2368     ASSERT(e);
2369     if (!e)
2370         return false;
2371
2372     if (!selectorTagMatches(e, sel))
2373         return false;
2374
2375     if (sel->hasAttribute()) {
2376         if (sel->m_match == CSSSelector::Class)
2377             return e->hasClass() && static_cast<StyledElement*>(e)->classNames().contains(sel->value());
2378
2379         if (sel->m_match == CSSSelector::Id)
2380             return e->hasID() && e->idForStyleResolution() == sel->value();
2381         
2382         const QualifiedName& attr = sel->attribute();
2383
2384         // FIXME: Handle the case were elementStyle is 0.
2385         if (elementStyle && (!e->isStyledElement() || (!static_cast<StyledElement*>(e)->isMappedAttribute(attr) && attr != typeAttr && attr != readonlyAttr))) {
2386             elementStyle->setAffectedByAttributeSelectors(); // Special-case the "type" and "readonly" attributes so input form controls can share style.
2387         }
2388
2389         const AtomicString& value = e->getAttribute(attr);
2390         if (value.isNull())
2391             return false; // attribute is not set
2392
2393         bool caseSensitive = !m_documentIsHTML || !htmlAttributeHasCaseInsensitiveValue(attr);
2394
2395         switch (sel->m_match) {
2396         case CSSSelector::Exact:
2397             if (caseSensitive ? sel->value() != value : !equalIgnoringCase(sel->value(), value))
2398                 return false;
2399             break;
2400         case CSSSelector::List:
2401         {
2402             // Ignore empty selectors or selectors containing spaces
2403             if (sel->value().contains(' ') || sel->value().isEmpty())
2404                 return false;
2405
2406             unsigned startSearchAt = 0;
2407             while (true) {
2408                 size_t foundPos = value.find(sel->value(), startSearchAt, caseSensitive);
2409                 if (foundPos == notFound)
2410                     return false;
2411                 if (foundPos == 0 || value[foundPos - 1] == ' ') {
2412                     unsigned endStr = foundPos + sel->value().length();
2413                     if (endStr == value.length() || value[endStr] == ' ')
2414                         break; // We found a match.
2415                 }
2416                 
2417                 // No match. Keep looking.
2418                 startSearchAt = foundPos + 1;
2419             }
2420             break;
2421         }
2422         case CSSSelector::Contain:
2423             if (!value.contains(sel->value(), caseSensitive) || sel->value().isEmpty())
2424                 return false;
2425             break;
2426         case CSSSelector::Begin:
2427             if (!value.startsWith(sel->value(), caseSensitive) || sel->value().isEmpty())
2428                 return false;
2429             break;
2430         case CSSSelector::End:
2431             if (!value.endsWith(sel->value(), caseSensitive) || sel->value().isEmpty())
2432                 return false;
2433             break;
2434         case CSSSelector::Hyphen:
2435             if (value.length() < sel->value().length())
2436                 return false;
2437             if (!value.startsWith(sel->value(), caseSensitive))
2438                 return false;
2439             // It they start the same, check for exact match or following '-':
2440             if (value.length() != sel->value().length() && value[sel->value().length()] != '-')
2441                 return false;
2442             break;
2443         case CSSSelector::PseudoClass:
2444         case CSSSelector::PseudoElement:
2445         default:
2446             break;
2447         }
2448     }
2449     
2450     if (sel->m_match == CSSSelector::PseudoClass) {
2451         // Handle :not up front.
2452         if (sel->pseudoType() == CSSSelector::PseudoNot) {
2453             ASSERT(sel->selectorList());
2454             for (CSSSelector* subSel = sel->selectorList()->first(); subSel; subSel = subSel->tagHistory()) {
2455                 // :not cannot nest. I don't really know why this is a
2456                 // restriction in CSS3, but it is, so let's honor it.
2457                 // the parser enforces that this never occurs
2458                 ASSERT(subSel->pseudoType() != CSSSelector::PseudoNot);
2459
2460                 if (!checkOneSelector(subSel, e, dynamicPseudo, true, encounteredLink, elementStyle, elementParentStyle))
2461                     return true;
2462             }
2463         } else if (dynamicPseudo != NOPSEUDO && (RenderScrollbar::scrollbarForStyleResolve() || dynamicPseudo == SCROLLBAR_CORNER || dynamicPseudo == RESIZER)) {
2464             // CSS scrollbars match a specific subset of pseudo classes, and they have specialized rules for each
2465             // (since there are no elements involved).
2466             return checkScrollbarPseudoClass(sel, dynamicPseudo);
2467         } else if (dynamicPseudo == SELECTION) {
2468             if (sel->pseudoType() == CSSSelector::PseudoWindowInactive)
2469                 return !m_document->page()->focusController()->isActive();
2470         }
2471         
2472         // Normal element pseudo class checking.
2473         switch (sel->pseudoType()) {
2474             // Pseudo classes:
2475             case CSSSelector::PseudoNot:
2476                 break; // Already handled up above.
2477             case CSSSelector::PseudoEmpty: {
2478                 bool result = true;
2479                 for (Node* n = e->firstChild(); n; n = n->nextSibling()) {
2480                     if (n->isElementNode()) {
2481                         result = false;
2482                         break;
2483                     } else if (n->isTextNode()) {
2484                         Text* textNode = static_cast<Text*>(n);
2485                         if (!textNode->data().isEmpty()) {
2486                             result = false;
2487                             break;
2488                         }
2489                     }
2490                 }
2491                 if (!m_collectRulesOnly) {
2492                     if (elementStyle)
2493                         elementStyle->setEmptyState(result);
2494                     else if (e->renderStyle() && (e->document()->usesSiblingRules() || e->renderStyle()->unique()))
2495                         e->renderStyle()->setEmptyState(result);
2496                 }
2497                 return result;
2498             }
2499             case CSSSelector::PseudoFirstChild: {
2500                 // first-child matches the first child that is an element
2501                 if (e->parentNode() && e->parentNode()->isElementNode()) {
2502                     bool result = false;
2503                     Node* n = e->previousSibling();
2504                     while (n && !n->isElementNode())
2505                         n = n->previousSibling();
2506                     if (!n)
2507                         result = true;
2508                     if (!m_collectRulesOnly) {
2509                         RenderStyle* childStyle = elementStyle ? elementStyle : e->renderStyle();
2510                         RenderStyle* parentStyle = elementStyle ? elementParentStyle : e->parentNode()->renderStyle();
2511                         if (parentStyle)
2512                             parentStyle->setChildrenAffectedByFirstChildRules();
2513                         if (result && childStyle)
2514                             childStyle->setFirstChildState();
2515                     }
2516                     return result;
2517                 }
2518                 break;
2519             }
2520             case CSSSelector::PseudoFirstOfType: {
2521                 // first-of-type matches the first element of its type
2522                 if (e->parentNode() && e->parentNode()->isElementNode()) {
2523                     bool result = false;
2524                     const QualifiedName& type = e->tagQName();
2525                     Node* n = e->previousSibling();
2526                     while (n) {
2527                         if (n->isElementNode() && static_cast<Element*>(n)->hasTagName(type))
2528                             break;
2529                         n = n->previousSibling();
2530                     }
2531                     if (!n)
2532                         result = true;
2533                     if (!m_collectRulesOnly) {
2534                         RenderStyle* parentStyle = elementStyle ? elementParentStyle : e->parentNode()->renderStyle();
2535                         if (parentStyle)
2536                             parentStyle->setChildrenAffectedByForwardPositionalRules();
2537                     }
2538                     return result;
2539                 }
2540                 break;
2541             }
2542             case CSSSelector::PseudoLastChild: {
2543                 // last-child matches the last child that is an element
2544                 if (Element* parentElement = e->parentElement()) {
2545                     bool result = false;
2546                     if (parentElement->isFinishedParsingChildren()) {
2547                         Node* n = e->nextSibling();
2548                         while (n && !n->isElementNode())
2549                             n = n->nextSibling();
2550                         if (!n)
2551                             result = true;
2552                     }
2553                     if (!m_collectRulesOnly) {
2554                         RenderStyle* childStyle = elementStyle ? elementStyle : e->renderStyle();
2555                         RenderStyle* parentStyle = elementStyle ? elementParentStyle : parentElement->renderStyle();
2556                         if (parentStyle)
2557                             parentStyle->setChildrenAffectedByLastChildRules();
2558                         if (result && childStyle)
2559                             childStyle->setLastChildState();
2560                     }
2561                     return result;
2562                 }
2563                 break;
2564             }
2565             case CSSSelector::PseudoLastOfType: {
2566                 // last-of-type matches the last element of its type
2567                 if (Element* parentElement = e->parentElement()) {
2568                     if (!m_collectRulesOnly) {
2569                         RenderStyle* parentStyle = elementStyle ? elementParentStyle : parentElement->renderStyle();
2570                         if (parentStyle)
2571                             parentStyle->setChildrenAffectedByBackwardPositionalRules();
2572                     }
2573                     if (!parentElement->isFinishedParsingChildren())
2574                         return false;
2575                     bool result = false;
2576                     const QualifiedName& type = e->tagQName();
2577                     Node* n = e->nextSibling();
2578                     while (n) {
2579                         if (n->isElementNode() && static_cast<Element*>(n)->hasTagName(type))
2580                             break;
2581                         n = n->nextSibling();
2582                     }
2583                     if (!n)
2584                         result = true;
2585                     return result;
2586                 }
2587                 break;
2588             }
2589             case CSSSelector::PseudoOnlyChild: {
2590                 if (Element* parentElement = e->parentElement()) {
2591                     bool firstChild = false;
2592                     bool lastChild = false;
2593                     
2594                     Node* n = e->previousSibling();
2595                     while (n && !n->isElementNode())
2596                         n = n->previousSibling();
2597                     if (!n)
2598                         firstChild = true;
2599                     if (firstChild && parentElement->isFinishedParsingChildren()) {
2600                         n = e->nextSibling();
2601                         while (n && !n->isElementNode())
2602                             n = n->nextSibling();
2603                         if (!n)
2604                             lastChild = true;
2605                     }
2606                     if (!m_collectRulesOnly) {
2607                         RenderStyle* childStyle = elementStyle ? elementStyle : e->renderStyle();
2608                         RenderStyle* parentStyle = elementStyle ? elementParentStyle : parentElement->renderStyle();
2609                         if (parentStyle) {
2610                             parentStyle->setChildrenAffectedByFirstChildRules();
2611                             parentStyle->setChildrenAffectedByLastChildRules();
2612                         }
2613                         if (firstChild && childStyle)
2614                             childStyle->setFirstChildState();
2615                         if (lastChild && childStyle)
2616                             childStyle->setLastChildState();
2617                     }
2618                     return firstChild && lastChild;
2619                 }
2620                 break;
2621             }
2622             case CSSSelector::PseudoOnlyOfType: {
2623                 // FIXME: This selector is very slow.
2624                 if (Element* parentElement = e->parentElement()) {
2625                     if (!m_collectRulesOnly) {
2626                         RenderStyle* parentStyle = elementStyle ? elementParentStyle : parentElement->renderStyle();
2627                         if (parentStyle) {
2628                             parentStyle->setChildrenAffectedByForwardPositionalRules();
2629                             parentStyle->setChildrenAffectedByBackwardPositionalRules();
2630                         }
2631                     }
2632                     if (!parentElement->isFinishedParsingChildren())
2633                         return false;
2634                     bool firstChild = false;
2635                     bool lastChild = false;
2636                     const QualifiedName& type = e->tagQName();
2637                     Node* n = e->previousSibling();
2638                     while (n) {
2639                         if (n->isElementNode() && static_cast<Element*>(n)->hasTagName(type))
2640                             break;
2641                         n = n->previousSibling();
2642                     }
2643                     if (!n)
2644                         firstChild = true;
2645                     if (firstChild) {
2646                         n = e->nextSibling();
2647                         while (n) {
2648                             if (n->isElementNode() && static_cast<Element*>(n)->hasTagName(type))
2649                                 break;
2650                             n = n->nextSibling();
2651                         }
2652                         if (!n)
2653                             lastChild = true;
2654                     }
2655                     return firstChild && lastChild;
2656                 }
2657                 break;
2658             }
2659             case CSSSelector::PseudoNthChild: {
2660                 if (!sel->parseNth())
2661                     break;
2662                 if (Element* parentElement = e->parentElement()) {
2663                     int count = 1;
2664                     Node* n = e->previousSibling();
2665                     while (n) {
2666                         if (n->isElementNode()) {
2667                             RenderStyle* s = n->renderStyle();
2668                             unsigned index = s ? s->childIndex() : 0;
2669                             if (index) {
2670                                 count += index;
2671                                 break;
2672                             }
2673                             count++;
2674                         }
2675                         n = n->previousSibling();
2676                     }
2677                     
2678                     if (!m_collectRulesOnly) {
2679                         RenderStyle* childStyle = elementStyle ? elementStyle : e->renderStyle();
2680                         RenderStyle* parentStyle = elementStyle ? elementParentStyle : parentElement->renderStyle();
2681                         if (childStyle)
2682                             childStyle->setChildIndex(count);
2683                         if (parentStyle)
2684                             parentStyle->setChildrenAffectedByForwardPositionalRules();
2685                     }
2686                     
2687                     if (sel->matchNth(count))
2688                         return true;
2689                 }
2690                 break;
2691             }
2692             case CSSSelector::PseudoNthOfType: {
2693                 if (!sel->parseNth())
2694                     break;
2695                 if (Element* parentElement = e->parentElement()) {
2696                     int count = 1;
2697                     const QualifiedName& type = e->tagQName();
2698                     Node* n = e->previousSibling();
2699                     while (n) {
2700                         if (n->isElementNode() && static_cast<Element*>(n)->hasTagName(type))
2701                             count++;
2702                         n = n->previousSibling();
2703                     }
2704                     
2705                     if (!m_collectRulesOnly) {
2706                         RenderStyle* parentStyle = elementStyle ? elementParentStyle : parentElement->renderStyle();
2707                         if (parentStyle)
2708                             parentStyle->setChildrenAffectedByForwardPositionalRules();
2709                     }
2710
2711                     if (sel->matchNth(count))
2712                         return true;
2713                 }
2714                 break;
2715             }
2716             case CSSSelector::PseudoNthLastChild: {
2717                 if (!sel->parseNth())
2718                     break;
2719                 if (Element* parentElement = e->parentElement()) {
2720                     if (!m_collectRulesOnly) {
2721                         RenderStyle* parentStyle = elementStyle ? elementParentStyle : parentElement->renderStyle();
2722                         if (parentStyle)
2723                             parentStyle->setChildrenAffectedByBackwardPositionalRules();
2724                     }
2725                     if (!parentElement->isFinishedParsingChildren())
2726                         return false;
2727                     int count = 1;
2728                     Node* n = e->nextSibling();
2729                     while (n) {
2730                         if (n->isElementNode())
2731                             count++;
2732                         n = n->nextSibling();
2733                     }
2734                     if (sel->matchNth(count))
2735                         return true;
2736                 }
2737                 break;
2738             }
2739             case CSSSelector::PseudoNthLastOfType: {
2740                 if (!sel->parseNth())
2741                     break;
2742                 if (Element* parentElement = e->parentElement()) {
2743                     if (!m_collectRulesOnly) {
2744                         RenderStyle* parentStyle = elementStyle ? elementParentStyle : parentElement->renderStyle();
2745                         if (parentStyle)
2746                             parentStyle->setChildrenAffectedByBackwardPositionalRules();
2747                     }
2748                     if (!parentElement->isFinishedParsingChildren())
2749                         return false;
2750                     int count = 1;
2751                     const QualifiedName& type = e->tagQName();
2752                     Node* n = e->nextSibling();
2753                     while (n) {
2754                         if (n->isElementNode() && static_cast<Element*>(n)->hasTagName(type))
2755                             count++;
2756                         n = n->nextSibling();
2757                     }
2758                     if (sel->matchNth(count))
2759                         return true;
2760                 }
2761                 break;
2762             }
2763             case CSSSelector::PseudoTarget:
2764                 if (e == e->document()->cssTarget())
2765                     return true;
2766                 break;
2767             case CSSSelector::PseudoAny:
2768                 for (CSSSelector* selector = sel->selectorList()->first(); selector; selector = CSSSelectorList::next(selector)) {
2769                     if (checkSelector(selector, e, dynamicPseudo, true, encounteredLink, elementStyle, elementParentStyle) == SelectorMatches)
2770                         return true;
2771                 }
2772                 break;
2773             case CSSSelector::PseudoAnyLink:
2774                 if (e && e->isLink())
2775                     return true;
2776                 break;
2777             case CSSSelector::PseudoAutofill: {
2778                 if (!e || !e->isFormControlElement())
2779                     break;
2780                 if (HTMLInputElement* inputElement = e->toInputElement())
2781                     return inputElement->isAutofilled();
2782                 break;
2783             }
2784             case CSSSelector::PseudoLink:
2785                 if (e && e->isLink())
2786                     return !m_matchVisitedPseudoClass;
2787                 break;
2788             case CSSSelector::PseudoVisited:
2789                 if (e && e->isLink())
2790                     return m_matchVisitedPseudoClass;
2791                 break;
2792             case CSSSelector::PseudoDrag: {
2793                 if (elementStyle)
2794                     elementStyle->setAffectedByDragRules(true);
2795                 else if (e->renderStyle())
2796                     e->renderStyle()->setAffectedByDragRules(true);
2797                 if (e->renderer() && e->renderer()->isDragging())
2798                     return true;
2799                 break;
2800             }
2801             case CSSSelector::PseudoFocus:
2802                 if (e && e->focused() && e->document()->frame() && e->document()->frame()->selection()->isFocusedAndActive())
2803                     return true;
2804                 break;
2805             case CSSSelector::PseudoHover: {
2806                 // If we're in quirks mode, then hover should never match anchors with no
2807                 // href and *:hover should not match anything.  This is important for sites like wsj.com.
2808                 if (m_strictParsing || isSubSelector || (sel->hasTag() && !e->hasTagName(aTag)) || e->isLink()) {
2809                     if (elementStyle)
2810                         elementStyle->setAffectedByHoverRules(true);
2811                     else if (e->renderStyle())
2812                         e->renderStyle()->setAffectedByHoverRules(true);
2813                     if (e->hovered())
2814                         return true;
2815                 }
2816                 break;
2817             }
2818             case CSSSelector::PseudoActive:
2819                 // If we're in quirks mode, then :active should never match anchors with no
2820                 // href and *:active should not match anything. 
2821                 if (m_strictParsing || isSubSelector || (sel->hasTag() && !e->hasTagName(aTag)) || e->isLink()) {
2822                     if (elementStyle)
2823                         elementStyle->setAffectedByActiveRules(true);
2824                     else if (e->renderStyle())
2825                         e->renderStyle()->setAffectedByActiveRules(true);
2826                     if (e->active())
2827                         return true;
2828                 }
2829                 break;
2830             case CSSSelector::PseudoEnabled:
2831                 if (e && e->isFormControlElement())
2832                     return e->isEnabledFormControl();
2833                 break;
2834             case CSSSelector::PseudoFullPageMedia:
2835                 return e && e->document() && e->document()->isMediaDocument();
2836                 break;
2837             case CSSSelector::PseudoDefault:
2838                 return e && e->isDefaultButtonForForm();
2839             case CSSSelector::PseudoDisabled:
2840                 if (e && e->isFormControlElement())
2841                     return !e->isEnabledFormControl();
2842                 break;
2843             case CSSSelector::PseudoReadOnly: {
2844                 if (!e || !e->isFormControlElement())
2845                     return false;
2846                 return e->isTextFormControl() && e->isReadOnlyFormControl();
2847             }
2848             case CSSSelector::PseudoReadWrite: {
2849                 if (!e || !e->isFormControlElement())
2850                     return false;
2851                 return e->isTextFormControl() && !e->isReadOnlyFormControl();
2852             }
2853             case CSSSelector::PseudoOptional:
2854                 return e && e->isOptionalFormControl();
2855             case CSSSelector::PseudoRequired:
2856                 return e && e->isRequiredFormControl();
2857             case CSSSelector::PseudoValid: {
2858                 if (!e)
2859                     return false;
2860                 e->document()->setContainsValidityStyleRules();
2861                 return e->willValidate() && e->isValidFormControlElement();
2862             } case CSSSelector::PseudoInvalid: {
2863                 if (!e)
2864                     return false;
2865                 e->document()->setContainsValidityStyleRules();
2866                 return (e->willValidate() && !e->isValidFormControlElement()) || e->hasUnacceptableValue();
2867             } case CSSSelector::PseudoChecked: {
2868                 if (!e || !e->isFormControlElement())
2869                     break;
2870                 // Even though WinIE allows checked and indeterminate to co-exist, the CSS selector spec says that
2871                 // you can't be both checked and indeterminate.  We will behave like WinIE behind the scenes and just
2872                 // obey the CSS spec here in the test for matching the pseudo.
2873                 HTMLInputElement* inputElement = e->toInputElement();
2874                 if (inputElement && inputElement->isChecked() && !inputElement->isIndeterminate())
2875                     return true;
2876                 break;
2877             }
2878             case CSSSelector::PseudoIndeterminate: {
2879                 if (!e || !e->isFormControlElement())
2880                     break;
2881                 HTMLInputElement* inputElement = e->toInputElement();
2882                 if (inputElement && inputElement->isIndeterminate())
2883                     return true;
2884                 break;
2885             }
2886             case CSSSelector::PseudoRoot:
2887                 if (e == e->document()->documentElement())
2888                     return true;
2889                 break;
2890             case CSSSelector::PseudoLang: {
2891                 AtomicString value = e->computeInheritedLanguage();
2892                 const AtomicString& argument = sel->argument();
2893                 if (value.isEmpty() || !value.startsWith(argument, false))
2894                     break;
2895                 if (value.length() != argument.length() && value[argument.length()] != '-')
2896                     break;
2897                 return true;
2898             }
2899 #if ENABLE(FULLSCREEN_API)
2900             case CSSSelector::PseudoFullScreen:
2901                 // While a Document is in the fullscreen state, and the document's current fullscreen 
2902                 // element is an element in the document, the 'full-screen' pseudoclass applies to 
2903                 // that element. Also, an <iframe>, <object> or <embed> element whose child browsing 
2904                 // context's Document is in the fullscreen state has the 'full-screen' pseudoclass applied.
2905                 if (e->isFrameElementBase() && static_cast<HTMLFrameElementBase*>(e)->containsFullScreenElement())
2906                     return true;
2907                 if (!e->document()->webkitIsFullScreen())
2908                     return false;
2909                 return e == e->document()->webkitCurrentFullScreenElement();
2910             case CSSSelector::PseudoAnimatingFullScreenTransition:
2911                 if (e != e->document()->webkitCurrentFullScreenElement())
2912                     return false;
2913                 return e->document()->isAnimatingFullScreen();
2914             case CSSSelector::PseudoFullScreenAncestor:
2915                 return e->containsFullScreenElement();
2916             case CSSSelector::PseudoFullScreenDocument:
2917                 // While a Document is in the fullscreen state, the 'full-screen-document' pseudoclass applies 
2918                 // to all elements of that Document.
2919                 if (!e->document()->webkitIsFullScreen())
2920                     return false;
2921                 return true;
2922 #endif
2923             case CSSSelector::PseudoInRange:
2924                 if (!e)
2925                     return false;
2926                 e->document()->setContainsValidityStyleRules();
2927                 return e->isInRange();
2928             case CSSSelector::PseudoOutOfRange:
2929                 if (!e)
2930                     return false;
2931                 e->document()->setContainsValidityStyleRules();
2932                 return e->isOutOfRange();
2933             case CSSSelector::PseudoUnknown:
2934             case CSSSelector::PseudoNotParsed:
2935             default:
2936                 ASSERT_NOT_REACHED();
2937                 break;
2938         }
2939         return false;
2940     }
2941     if (sel->m_match == CSSSelector::PseudoElement) {
2942         if (!elementStyle && !m_collectRulesOnly)
2943             return false;
2944
2945         if (sel->isUnknownPseudoElement()) {
2946             m_hasUnknownPseudoElements = true;
2947             return e->shadowPseudoId() == sel->value();
2948         }
2949
2950         PseudoId pseudoId = CSSSelector::pseudoId(sel->pseudoType());
2951         if (pseudoId == FIRST_LETTER) {
2952             if (Document* document = e->document())
2953                 document->setUsesFirstLetterRules(true);
2954         }
2955         if (pseudoId != NOPSEUDO)
2956             dynamicPseudo = pseudoId;
2957     }
2958     // ### add the rest of the checks...
2959     return true;
2960 }
2961
2962 bool CSSStyleSelector::SelectorChecker::checkScrollbarPseudoClass(CSSSelector* sel, PseudoId&) const
2963 {
2964     RenderScrollbar* scrollbar = RenderScrollbar::scrollbarForStyleResolve();
2965     ScrollbarPart part = RenderScrollbar::partForStyleResolve();
2966
2967     // FIXME: This is a temporary hack for resizers and scrollbar corners.  Eventually :window-inactive should become a real
2968     // pseudo class and just apply to everything.
2969     if (sel->pseudoType() == CSSSelector::PseudoWindowInactive)
2970         return !m_document->page()->focusController()->isActive();
2971     
2972     if (!scrollbar)
2973         return false;
2974         
2975     ASSERT(sel->m_match == CSSSelector::PseudoClass);
2976     switch (sel->pseudoType()) {
2977         case CSSSelector::PseudoEnabled:
2978             return scrollbar->enabled();
2979         case CSSSelector::PseudoDisabled:
2980             return !scrollbar->enabled();
2981         case CSSSelector::PseudoHover: {
2982             ScrollbarPart hoveredPart = scrollbar->hoveredPart();
2983             if (part == ScrollbarBGPart)
2984                 return hoveredPart != NoPart;
2985             if (part == TrackBGPart)
2986                 return hoveredPart == BackTrackPart || hoveredPart == ForwardTrackPart || hoveredPart == ThumbPart;
2987             return part == hoveredPart;
2988         }
2989         case CSSSelector::PseudoActive: {
2990             ScrollbarPart pressedPart = scrollbar->pressedPart();
2991             if (part == ScrollbarBGPart)
2992                 return pressedPart != NoPart;
2993             if (part == TrackBGPart)
2994                 return pressedPart == BackTrackPart || pressedPart == ForwardTrackPart || pressedPart == ThumbPart;
2995             return part == pressedPart;
2996         }
2997         case CSSSelector::PseudoHorizontal:
2998             return scrollbar->orientation() == HorizontalScrollbar;
2999         case CSSSelector::PseudoVertical:
3000             return scrollbar->orientation() == VerticalScrollbar;
3001         case CSSSelector::PseudoDecrement:
3002             return part == BackButtonStartPart || part == BackButtonEndPart || part == BackTrackPart;
3003         case CSSSelector::PseudoIncrement:
3004             return part == ForwardButtonStartPart || part == ForwardButtonEndPart || part == ForwardTrackPart;
3005         case CSSSelector::PseudoStart:
3006             return part == BackButtonStartPart || part == ForwardButtonStartPart || part == BackTrackPart;
3007         case CSSSelector::PseudoEnd:
3008             return part == BackButtonEndPart || part == ForwardButtonEndPart || part == ForwardTrackPart;
3009         case CSSSelector::PseudoDoubleButton: {
3010             ScrollbarButtonsPlacement buttonsPlacement = scrollbar->theme()->buttonsPlacement();
3011             if (part == BackButtonStartPart || part == ForwardButtonStartPart || part == BackTrackPart)
3012                 return buttonsPlacement == ScrollbarButtonsDoubleStart || buttonsPlacement == ScrollbarButtonsDoubleBoth;
3013             if (part == BackButtonEndPart || part == ForwardButtonEndPart || part == ForwardTrackPart)
3014                 return buttonsPlacement == ScrollbarButtonsDoubleEnd || buttonsPlacement == ScrollbarButtonsDoubleBoth;
3015             return false;
3016         } 
3017         case CSSSelector::PseudoSingleButton: {
3018             ScrollbarButtonsPlacement buttonsPlacement = scrollbar->theme()->buttonsPlacement();
3019             if (part == BackButtonStartPart || part == ForwardButtonEndPart || part == BackTrackPart || part == ForwardTrackPart)
3020                 return buttonsPlacement == ScrollbarButtonsSingle;
3021             return false;
3022         }
3023         case CSSSelector::PseudoNoButton: {
3024             ScrollbarButtonsPlacement buttonsPlacement = scrollbar->theme()->buttonsPlacement();
3025             if (part == BackTrackPart)
3026                 return buttonsPlacement == ScrollbarButtonsNone || buttonsPlacement == ScrollbarButtonsDoubleEnd;
3027             if (part == ForwardTrackPart)
3028                 return buttonsPlacement == ScrollbarButtonsNone || buttonsPlacement == ScrollbarButtonsDoubleStart;
3029             return false;
3030         }
3031         case CSSSelector::PseudoCornerPresent:
3032             return scrollbar->scrollableArea()->isScrollCornerVisible();
3033         default:
3034             return false;
3035     }
3036 }
3037
3038 // -----------------------------------------------------------------
3039
3040 static inline bool isSelectorMatchingHTMLBasedOnRuleHash(const CSSSelector* selector)
3041 {
3042     const AtomicString& selectorNamespace = selector->tag().namespaceURI();
3043     if (selectorNamespace != starAtom && selectorNamespace != xhtmlNamespaceURI)
3044         return false;
3045     if (selector->m_match == CSSSelector::None)
3046         return true;
3047     if (selector->m_match != CSSSelector::Id && selector->m_match != CSSSelector::Class)
3048         return false;
3049     return selector->tag() == starAtom;
3050 }
3051
3052 RuleData::RuleData(CSSStyleRule* rule, CSSSelector* selector, unsigned position)
3053     : m_rule(rule)
3054     , m_selector(selector)
3055     , m_specificity(selector->specificity())
3056     , m_position(position)
3057     , m_hasFastCheckableSelector(isFastCheckableSelector(selector))
3058     , m_hasMultipartSelector(selector->tagHistory())
3059     , m_hasTopSelectorMatchingHTMLBasedOnRuleHash(isSelectorMatchingHTMLBasedOnRuleHash(selector))
3060 {
3061     collectDescendantSelectorIdentifierHashes();
3062 }
3063
3064 inline void RuleData::collectIdentifierHashes(const CSSSelector* selector, unsigned& identifierCount)
3065 {
3066     if ((selector->m_match == CSSSelector::Id || selector->m_match == CSSSelector::Class) && !selector->value().isEmpty())
3067         m_descendantSelectorIdentifierHashes[identifierCount++] = selector->value().impl()->existingHash();
3068     if (identifierCount == maximumIdentifierCount)
3069         return;
3070     const AtomicString& localName = selector->tag().localName();
3071     if (localName != starAtom)
3072         m_descendantSelectorIdentifierHashes[identifierCount++] = localName.impl()->existingHash();
3073 }
3074
3075 inline void RuleData::collectDescendantSelectorIdentifierHashes()
3076 {
3077     unsigned identifierCount = 0;
3078     CSSSelector::Relation relation = m_selector->relation();
3079     
3080     // Skip the topmost selector. It is handled quickly by the rule hashes.    
3081     bool skipOverSubselectors = true;
3082     for (const CSSSelector* selector = m_selector->tagHistory(); selector; selector = selector->tagHistory()) {
3083         // Only collect identifiers that match ancestors.
3084         switch (relation) {
3085         case CSSSelector::SubSelector:
3086             if (!skipOverSubselectors)
3087                 collectIdentifierHashes(selector, identifierCount);
3088             break;
3089         case CSSSelector::DirectAdjacent:
3090         case CSSSelector::IndirectAdjacent:
3091         case CSSSelector::ShadowDescendant:
3092             skipOverSubselectors = true;
3093             break;
3094         case CSSSelector::Descendant:
3095         case CSSSelector::Child:
3096             skipOverSubselectors = false;
3097             collectIdentifierHashes(selector, identifierCount);
3098             break;
3099         }
3100         if (identifierCount == maximumIdentifierCount)
3101             return;
3102         relation = selector->relation();
3103     }
3104     m_descendantSelectorIdentifierHashes[identifierCount] = 0;
3105 }
3106
3107 RuleSet::RuleSet()
3108     : m_ruleCount(0)
3109     , m_autoShrinkToFitEnabled(true)
3110 {
3111 }
3112
3113 RuleSet::~RuleSet()
3114
3115     deleteAllValues(m_idRules);
3116     deleteAllValues(m_classRules);
3117     deleteAllValues(m_pseudoRules);
3118     deleteAllValues(m_tagRules);
3119 }
3120
3121
3122 void RuleSet::addToRuleSet(AtomicStringImpl* key, AtomRuleMap& map,
3123                               CSSStyleRule* rule, CSSSelector* sel)
3124 {
3125     if (!key) return;
3126     Vector<RuleData>* rules = map.get(key);
3127     if (!rules) {
3128         rules = new Vector<RuleData>;
3129         map.set(key, rules);
3130     }
3131     rules->append(RuleData(rule, sel, m_ruleCount++));
3132 }
3133
3134 void RuleSet::addRule(CSSStyleRule* rule, CSSSelector* sel)
3135 {
3136     if (sel->m_match == CSSSelector::Id) {
3137         addToRuleSet(sel->value().impl(), m_idRules, rule, sel);
3138         return;
3139     }
3140     if (sel->m_match == CSSSelector::Class) {
3141         addToRuleSet(sel->value().impl(), m_classRules, rule, sel);
3142         return;
3143     }
3144      
3145     if (sel->isUnknownPseudoElement()) {
3146         addToRuleSet(sel->value().impl(), m_pseudoRules, rule, sel);
3147         return;
3148     }
3149
3150     const AtomicString& localName = sel->tag().localName();
3151     if (localName != starAtom) {
3152         addToRuleSet(localName.impl(), m_tagRules, rule, sel);
3153         return;
3154     }
3155
3156     m_universalRules.append(RuleData(rule, sel, m_ruleCount++));
3157 }
3158
3159 void RuleSet::addPageRule(CSSStyleRule* rule, CSSSelector* sel)
3160 {
3161     m_pageRules.append(RuleData(rule, sel, m_pageRules.size()));
3162 }
3163
3164 void RuleSet::addRulesFromSheet(CSSStyleSheet* sheet, const MediaQueryEvaluator& medium, CSSStyleSelector* styleSelector)
3165 {
3166     if (!sheet)
3167         return;
3168
3169     // No media implies "all", but if a media list exists it must
3170     // contain our current medium
3171     if (sheet->media() && !medium.eval(sheet->media(), styleSelector))
3172         return; // the style sheet doesn't apply
3173
3174     int len = sheet->length();
3175
3176     for (int i = 0; i < len; i++) {
3177         StyleBase* item = sheet->item(i);
3178         if (item->isStyleRule())
3179             addStyleRule(static_cast<CSSStyleRule*>(item));
3180         else if (item->isImportRule()) {
3181             CSSImportRule* import = static_cast<CSSImportRule*>(item);
3182             if (!import->media() || medium.eval(import->media(), styleSelector))
3183                 addRulesFromSheet(import->styleSheet(), medium, styleSelector);
3184         }
3185         else if (item->isMediaRule()) {
3186             CSSMediaRule* r = static_cast<CSSMediaRule*>(item);
3187             CSSRuleList* rules = r->cssRules();
3188
3189             if ((!r->media() || medium.eval(r->media(), styleSelector)) && rules) {
3190                 // Traverse child elements of the @media rule.
3191                 for (unsigned j = 0; j < rules->length(); j++) {
3192                     CSSRule *childItem = rules->item(j);
3193                     if (childItem->isStyleRule()) {
3194                         // It is a StyleRule, so append it to our list
3195                         addStyleRule(static_cast<CSSStyleRule*>(childItem));
3196                     } else if (childItem->isFontFaceRule() && styleSelector) {
3197                         // Add this font face to our set.
3198                         const CSSFontFaceRule* fontFaceRule = static_cast<CSSFontFaceRule*>(childItem);
3199                         styleSelector->fontSelector()->addFontFaceRule(fontFaceRule);
3200                     } else if (childItem->isKeyframesRule() && styleSelector) {
3201                         // Add this keyframe rule to our set.
3202                         styleSelector->addKeyframeStyle(static_cast<WebKitCSSKeyframesRule*>(childItem));
3203                     }
3204                 }   // for rules
3205             }   // if rules
3206         } else if (item->isFontFaceRule() && styleSelector) {
3207             // Add this font face to our set.
3208             const CSSFontFaceRule* fontFaceRule = static_cast<CSSFontFaceRule*>(item);
3209             styleSelector->fontSelector()->addFontFaceRule(fontFaceRule);
3210         } else if (item->isKeyframesRule())
3211             styleSelector->addKeyframeStyle(static_cast<WebKitCSSKeyframesRule*>(item));
3212     }
3213     if (m_autoShrinkToFitEnabled)
3214         shrinkToFit();
3215 }
3216
3217 void RuleSet::addStyleRule(CSSStyleRule* rule)
3218 {
3219     if (rule->isPageRule()) {
3220         CSSPageRule* pageRule = static_cast<CSSPageRule*>(rule);
3221         addPageRule(pageRule, pageRule->selectorList().first());
3222     } else {
3223         for (CSSSelector* s = rule->selectorList().first(); s; s = CSSSelectorList::next(s))
3224             addRule(rule, s);
3225     }
3226 }
3227     
3228 static inline void