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