96a74affabbeb52f035f27d711564d56dfdfd01d
[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     const AtomicString& pseudoId = m_element->shadowPseudoId();
712     if (!pseudoId.isEmpty()) {
713         ASSERT(m_styledElement);
714         matchRulesForList(rules->getPseudoRules(pseudoId.impl()), firstRuleIndex, lastRuleIndex, includeEmptyRules);
715     }
716     matchRulesForList(rules->getTagRules(m_element->localName().impl()), firstRuleIndex, lastRuleIndex, includeEmptyRules);
717     matchRulesForList(rules->getUniversalRules(), firstRuleIndex, lastRuleIndex, includeEmptyRules);
718     
719     // If we didn't match any rules, we're done.
720     if (m_matchedRules.isEmpty())
721         return;
722     
723     // Sort the set of matched rules.
724     sortMatchedRules();
725     
726     // Now transfer the set of matched rules over to our list of decls.
727     if (!m_checker.m_collectRulesOnly) {
728         for (unsigned i = 0; i < m_matchedRules.size(); i++)
729             addMatchedDeclaration(m_matchedRules[i]->rule()->declaration());
730     } else {
731         for (unsigned i = 0; i < m_matchedRules.size(); i++) {
732             if (!m_ruleList)
733                 m_ruleList = CSSRuleList::create();
734             m_ruleList->append(m_matchedRules[i]->rule());
735         }
736     }
737 }
738
739 inline bool CSSStyleSelector::fastRejectSelector(const RuleData& ruleData) const
740 {
741     ASSERT(m_ancestorIdentifierFilter);
742     const unsigned* descendantSelectorIdentifierHashes = ruleData.descendantSelectorIdentifierHashes();
743     for (unsigned n = 0; n < RuleData::maximumIdentifierCount && descendantSelectorIdentifierHashes[n]; ++n) {
744         if (!m_ancestorIdentifierFilter->mayContain(descendantSelectorIdentifierHashes[n]))
745             return true;
746     }
747     return false;
748 }
749
750 class MatchingUARulesScope {
751 public:
752     MatchingUARulesScope();
753     ~MatchingUARulesScope();
754
755     static bool isMatchingUARules();
756
757 private:
758     static bool m_matchingUARules;
759 };
760
761 MatchingUARulesScope::MatchingUARulesScope()
762 {
763     ASSERT(!m_matchingUARules);
764     m_matchingUARules = true;
765 }
766
767 MatchingUARulesScope::~MatchingUARulesScope()
768 {
769     m_matchingUARules = false;
770 }
771
772 inline bool MatchingUARulesScope::isMatchingUARules()
773 {
774     return m_matchingUARules;
775 }
776
777 bool MatchingUARulesScope::m_matchingUARules = false;
778
779 inline static bool matchesInTreeScope(TreeScope* treeScope, bool ruleReachesIntoShadowDOM)
780 {
781     return MatchingUARulesScope::isMatchingUARules() || treeScope->applyAuthorSheets() || ruleReachesIntoShadowDOM;
782 }
783
784 void CSSStyleSelector::matchRulesForList(const Vector<RuleData>* rules, int& firstRuleIndex, int& lastRuleIndex, bool includeEmptyRules)
785 {
786     if (!rules)
787         return;
788     // In some cases we may end up looking up style for random elements in the middle of a recursive tree resolve.
789     // Ancestor identifier filter won't be up-to-date in that case and we can't use the fast path.
790     bool canUseFastReject = !m_parentStack.isEmpty() && m_parentStack.last().element == m_parentNode;
791
792     unsigned size = rules->size();
793     for (unsigned i = 0; i < size; ++i) {
794         const RuleData& ruleData = rules->at(i);
795         if (canUseFastReject && fastRejectSelector(ruleData))
796             continue;
797         if (checkSelector(ruleData)) {
798             if (!matchesInTreeScope(m_element->treeScope(), m_checker.m_hasUnknownPseudoElements))
799                 continue;
800             // If the rule has no properties to apply, then ignore it in the non-debug mode.
801             CSSStyleRule* rule = ruleData.rule();
802             CSSMutableStyleDeclaration* decl = rule->declaration();
803             if (!decl || (!decl->length() && !includeEmptyRules))
804                 continue;
805             if (m_checker.m_sameOriginOnly && !m_checker.m_document->securityOrigin()->canRequest(rule->baseURL()))
806                 continue; 
807             // If we're matching normal rules, set a pseudo bit if 
808             // we really just matched a pseudo-element.
809             if (m_dynamicPseudo != NOPSEUDO && m_checker.m_pseudoStyle == NOPSEUDO) {
810                 if (m_checker.m_collectRulesOnly)
811                     continue;
812                 if (m_dynamicPseudo < FIRST_INTERNAL_PSEUDOID)
813                     m_style->setHasPseudoStyle(m_dynamicPseudo);
814             } else {
815                 // Update our first/last rule indices in the matched rules array.
816                 lastRuleIndex = m_matchedDecls.size() + m_matchedRules.size();
817                 if (firstRuleIndex == -1)
818                     firstRuleIndex = lastRuleIndex;
819
820                 // Add this rule to our list of matched rules.
821                 addMatchedRule(&ruleData);
822             }
823         }
824     }
825 }
826
827 static inline bool compareRules(const RuleData* r1, const RuleData* r2)
828 {
829     unsigned specificity1 = r1->specificity();
830     unsigned specificity2 = r2->specificity();
831     return (specificity1 == specificity2) ? r1->position() < r2->position() : specificity1 < specificity2; 
832 }
833
834 void CSSStyleSelector::sortMatchedRules()
835 {
836     std::sort(m_matchedRules.begin(), m_matchedRules.end(), compareRules);
837 }
838
839 inline EInsideLink CSSStyleSelector::SelectorChecker::determineLinkState(Element* element) const
840 {
841     if (!element || !element->isLink())
842         return NotInsideLink;
843     return determineLinkStateSlowCase(element);
844 }
845     
846 inline void CSSStyleSelector::initElement(Element* e)
847 {
848     if (m_element != e) {
849         m_element = e;
850         m_styledElement = m_element && m_element->isStyledElement() ? static_cast<StyledElement*>(m_element) : 0;
851         m_elementLinkState = m_checker.determineLinkState(m_element);
852         if (e && e == e->document()->documentElement()) {
853             e->document()->setDirectionSetOnDocumentElement(false);
854             e->document()->setWritingModeSetOnDocumentElement(false);
855         }
856     }
857 }
858
859 inline void CSSStyleSelector::initForStyleResolve(Element* e, RenderStyle* parentStyle, PseudoId pseudoID)
860 {
861     m_checker.m_pseudoStyle = pseudoID;
862
863     m_parentNode = e ? e->parentNodeForRenderingAndStyle() : 0;
864
865     if (parentStyle)
866         m_parentStyle = parentStyle;
867     else
868         m_parentStyle = m_parentNode ? m_parentNode->renderStyle() : 0;
869
870     Node* docElement = e ? e->document()->documentElement() : 0;
871     RenderStyle* docStyle = m_checker.m_document->renderStyle();
872     m_rootElementStyle = docElement && e != docElement ? docElement->renderStyle() : docStyle;
873
874     m_style = 0;
875
876     m_matchedDecls.clear();
877
878     m_pendingImageProperties.clear();
879
880     m_ruleList = 0;
881
882     m_fontDirty = false;
883 }
884
885 static inline const AtomicString* linkAttribute(Node* node)
886 {
887     if (!node->isLink())
888         return 0;
889
890     ASSERT(node->isElementNode());
891     Element* element = static_cast<Element*>(node);
892     if (element->isHTMLElement())
893         return &element->fastGetAttribute(hrefAttr);
894
895 #if ENABLE(SVG)
896     if (element->isSVGElement())
897         return &element->fastGetAttribute(XLinkNames::hrefAttr);
898 #endif
899
900     return 0;
901 }
902
903 CSSStyleSelector::SelectorChecker::SelectorChecker(Document* document, bool strictParsing)
904     : m_document(document)
905     , m_strictParsing(strictParsing)
906     , m_collectRulesOnly(false)
907     , m_sameOriginOnly(false)
908     , m_pseudoStyle(NOPSEUDO)
909     , m_documentIsHTML(document->isHTMLDocument())
910     , m_hasUnknownPseudoElements(false)
911     , m_matchVisitedPseudoClass(false)
912 {
913 }
914
915 EInsideLink CSSStyleSelector::SelectorChecker::determineLinkStateSlowCase(Element* element) const
916 {
917     ASSERT(element->isLink());
918     
919     const AtomicString* attr = linkAttribute(element);
920     if (!attr || attr->isNull())
921         return NotInsideLink;
922
923 #if PLATFORM(QT)
924     Vector<UChar, 512> url;
925     visitedURL(m_document->baseURL(), *attr, url);
926     if (url.isEmpty())
927         return InsideUnvisitedLink;
928
929     // If the Qt4.4 interface for the history is used, we will have to fallback
930     // to the old global history.
931     QWebHistoryInterface* iface = QWebHistoryInterface::defaultInterface();
932     if (iface)
933         return iface->historyContains(QString(reinterpret_cast<QChar*>(url.data()), url.size())) ? InsideVisitedLink : InsideUnvisitedLink;
934
935     LinkHash hash = visitedLinkHash(url.data(), url.size());
936     if (!hash)
937         return InsideUnvisitedLink;
938 #else
939     LinkHash hash = visitedLinkHash(m_document->baseURL(), *attr);
940     if (!hash)
941         return InsideUnvisitedLink;
942 #endif
943
944     Frame* frame = m_document->frame();
945     if (!frame)
946         return InsideUnvisitedLink;
947
948     Page* page = frame->page();
949     if (!page)
950         return InsideUnvisitedLink;
951
952     m_linksCheckedForVisitedState.add(hash);
953
954 #if USE(PLATFORM_STRATEGIES)
955     return platformStrategies()->visitedLinkStrategy()->isLinkVisited(page, hash) ? InsideVisitedLink : InsideUnvisitedLink;
956 #else
957     return page->group().isLinkVisited(hash) ? InsideVisitedLink : InsideUnvisitedLink;
958 #endif
959 }
960
961 bool CSSStyleSelector::SelectorChecker::checkSelector(CSSSelector* sel, Element* element) const
962 {
963     PseudoId dynamicPseudo = NOPSEUDO;
964     return checkSelector(sel, element, dynamicPseudo, false, false) == SelectorMatches;
965 }
966
967 static const unsigned cStyleSearchThreshold = 10;
968 static const unsigned cStyleSearchLevelThreshold = 10;
969
970 Node* CSSStyleSelector::locateCousinList(Element* parent, unsigned& visitedNodeCount) const
971 {
972     if (visitedNodeCount >= cStyleSearchThreshold * cStyleSearchLevelThreshold)
973         return 0;
974     if (!parent || !parent->isStyledElement())
975         return 0;
976     StyledElement* p = static_cast<StyledElement*>(parent);
977     if (p->inlineStyleDecl())
978         return 0;
979     if (p->hasID() && m_features.idsInRules.contains(p->idForStyleResolution().impl()))
980         return 0;
981
982     RenderStyle* parentStyle = p->renderStyle();
983     unsigned subcount = 0;
984     Node* thisCousin = p;
985     Node* currentNode = p->previousSibling();
986
987     // Reserve the tries for this level. This effectively makes sure that the algorithm
988     // will never go deeper than cStyleSearchLevelThreshold levels into recursion.
989     visitedNodeCount += cStyleSearchThreshold;
990     while (thisCousin) {
991         while (currentNode) {
992             ++subcount;
993             if (currentNode->renderStyle() == parentStyle && currentNode->lastChild()) {
994                 // Adjust for unused reserved tries.
995                 visitedNodeCount -= cStyleSearchThreshold - subcount;
996                 return currentNode->lastChild();
997             }
998             if (subcount >= cStyleSearchThreshold)
999                 return 0;
1000             currentNode = currentNode->previousSibling();
1001         }
1002         currentNode = locateCousinList(thisCousin->parentElement(), visitedNodeCount);
1003         thisCousin = currentNode;
1004     }
1005
1006     return 0;
1007 }
1008
1009 bool CSSStyleSelector::matchesSiblingRules()
1010 {
1011     int firstSiblingRule = -1, lastSiblingRule = -1;
1012     matchRules(m_features.siblingRules.get(), firstSiblingRule, lastSiblingRule, false);
1013     if (m_matchedDecls.isEmpty())
1014         return false;
1015     m_matchedDecls.clear();
1016     return true;
1017 }
1018
1019 bool CSSStyleSelector::canShareStyleWithElement(Node* node) const
1020 {
1021     if (!node->isStyledElement())
1022         return false;
1023
1024     StyledElement* element = static_cast<StyledElement*>(node);
1025     RenderStyle* style = element->renderStyle();
1026
1027     if (!style)
1028         return false;
1029     if (style->unique())
1030         return false;
1031     if (element->tagQName() != m_element->tagQName())
1032         return false;
1033     if (element->hasClass() != m_element->hasClass())
1034         return false;
1035     if (element->inlineStyleDecl())
1036         return false;
1037     if (element->hasMappedAttributes() != m_styledElement->hasMappedAttributes())
1038         return false;
1039     if (element->isLink() != m_element->isLink())
1040         return false;
1041     if (style->affectedByAttributeSelectors())
1042         return false;
1043     if (element->hovered() != m_element->hovered())
1044         return false;
1045     if (element->active() != m_element->active())
1046         return false;
1047     if (element->focused() != m_element->focused())
1048         return false;
1049     if (element->shadowPseudoId() != m_element->shadowPseudoId())
1050         return false;
1051     if (element == element->document()->cssTarget())
1052         return false;
1053     if (m_element == m_element->document()->cssTarget())
1054         return false;
1055     if (element->fastGetAttribute(typeAttr) != m_element->fastGetAttribute(typeAttr))
1056         return false;
1057     if (element->fastGetAttribute(XMLNames::langAttr) != m_element->fastGetAttribute(XMLNames::langAttr))
1058         return false;
1059     if (element->fastGetAttribute(langAttr) != m_element->fastGetAttribute(langAttr))
1060         return false;
1061     if (element->fastGetAttribute(readonlyAttr) != m_element->fastGetAttribute(readonlyAttr))
1062         return false;
1063     if (element->fastGetAttribute(cellpaddingAttr) != m_element->fastGetAttribute(cellpaddingAttr))
1064         return false;
1065
1066     if (element->hasID() && m_features.idsInRules.contains(element->idForStyleResolution().impl()))
1067         return false;
1068
1069     bool isControl = element->isFormControlElement();
1070
1071     if (isControl != m_element->isFormControlElement())
1072         return false;
1073
1074     if (isControl) {
1075         HTMLInputElement* thisInputElement = element->toInputElement();
1076         HTMLInputElement* otherInputElement = m_element->toInputElement();
1077
1078         if (!thisInputElement || !otherInputElement)
1079             return false;
1080
1081         if (thisInputElement->isAutofilled() != otherInputElement->isAutofilled())
1082             return false;
1083         if (thisInputElement->isChecked() != otherInputElement->isChecked())
1084             return false;
1085         if (thisInputElement->isIndeterminate() != otherInputElement->isIndeterminate())
1086             return false;
1087
1088         if (element->isEnabledFormControl() != m_element->isEnabledFormControl())
1089             return false;
1090
1091         if (element->isDefaultButtonForForm() != m_element->isDefaultButtonForForm())
1092             return false;
1093
1094         if (!m_element->document()->containsValidityStyleRules())
1095             return false;
1096
1097         bool willValidate = element->willValidate();
1098
1099         if (willValidate != m_element->willValidate())
1100             return false;
1101
1102         if (willValidate && (element->isValidFormControlElement() != m_element->isValidFormControlElement()))
1103             return false;
1104
1105         if (element->isInRange() != m_element->isInRange())
1106             return false;
1107
1108         if (element->isOutOfRange() != m_element->isOutOfRange())
1109             return false;
1110     }
1111
1112     if (style->transitions() || style->animations())
1113         return false;
1114
1115 #if USE(ACCELERATED_COMPOSITING)
1116     // Turn off style sharing for elements that can gain layers for reasons outside of the style system.
1117     // See comments in RenderObject::setStyle().
1118     if (element->hasTagName(iframeTag) || element->hasTagName(frameTag) || element->hasTagName(embedTag) || element->hasTagName(objectTag) || element->hasTagName(appletTag))
1119         return false;
1120 #endif
1121
1122     if (equalIgnoringCase(element->fastGetAttribute(dirAttr), "auto") || equalIgnoringCase(m_element->fastGetAttribute(dirAttr), "auto"))
1123         return false;
1124
1125     if (element->hasClass() && m_element->fastGetAttribute(classAttr) != element->fastGetAttribute(classAttr))
1126         return false;
1127
1128     if (element->hasMappedAttributes() && !element->attributeMap()->mappedMapsEquivalent(m_styledElement->attributeMap()))
1129         return false;
1130
1131     if (element->isLink() && m_elementLinkState != style->insideLink())
1132         return false;
1133
1134     return true;
1135 }
1136     
1137 inline Node* CSSStyleSelector::findSiblingForStyleSharing(Node* node, unsigned& count) const
1138 {
1139     for (; node; node = node->previousSibling()) {
1140         if (!node->isElementNode())
1141             continue;
1142         if (canShareStyleWithElement(node))
1143             break;
1144         if (count++ == cStyleSearchThreshold)
1145             return 0;
1146     }
1147     return node;
1148 }
1149
1150 static inline bool parentStylePreventsSharing(const RenderStyle* parentStyle)
1151 {
1152     return parentStyle->childrenAffectedByPositionalRules() 
1153         || parentStyle->childrenAffectedByFirstChildRules()
1154         || parentStyle->childrenAffectedByLastChildRules() 
1155         || parentStyle->childrenAffectedByDirectAdjacentRules();
1156 }
1157
1158 ALWAYS_INLINE RenderStyle* CSSStyleSelector::locateSharedStyle()
1159 {
1160     if (!m_styledElement || !m_parentStyle)
1161         return 0;
1162     // If the element has inline style it is probably unique.
1163     if (m_styledElement->inlineStyleDecl())
1164         return 0;
1165     // Ids stop style sharing if they show up in the stylesheets.
1166     if (m_styledElement->hasID() && m_features.idsInRules.contains(m_styledElement->idForStyleResolution().impl()))
1167         return 0;
1168     if (parentStylePreventsSharing(m_parentStyle))
1169         return 0;
1170
1171     // Check previous siblings and their cousins.
1172     unsigned count = 0;
1173     unsigned visitedNodeCount = 0;
1174     Node* shareNode = 0;
1175     Node* cousinList = m_styledElement->previousSibling();
1176     while (cousinList) {
1177         shareNode = findSiblingForStyleSharing(cousinList, count);
1178         if (shareNode)
1179             break;
1180         cousinList = locateCousinList(cousinList->parentElement(), visitedNodeCount);
1181     }
1182
1183     // If we have exhausted all our budget or our cousins.
1184     if (!shareNode)
1185         return 0;
1186
1187     // Can't share if sibling rules apply. This is checked at the end as it should rarely fail.
1188     if (matchesSiblingRules())
1189         return 0;
1190     // Tracking child index requires unique style for each node. This may get set by the sibling rule match above.
1191     if (parentStylePreventsSharing(m_parentStyle))
1192         return 0;
1193     return shareNode->renderStyle();
1194 }
1195
1196 void CSSStyleSelector::matchUARules(int& firstUARule, int& lastUARule)
1197 {
1198     MatchingUARulesScope scope;
1199
1200     // First we match rules from the user agent sheet.
1201     RuleSet* userAgentStyleSheet = m_medium->mediaTypeMatchSpecific("print")
1202         ? defaultPrintStyle : defaultStyle;
1203     matchRules(userAgentStyleSheet, firstUARule, lastUARule, false);
1204
1205     // In quirks mode, we match rules from the quirks user agent sheet.
1206     if (!m_checker.m_strictParsing)
1207         matchRules(defaultQuirksStyle, firstUARule, lastUARule, false);
1208         
1209     // 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.
1210     if (m_checker.m_document->isViewSource()) {
1211         if (!defaultViewSourceStyle)
1212             loadViewSourceStyle();
1213         matchRules(defaultViewSourceStyle, firstUARule, lastUARule, false);
1214     }
1215 }
1216
1217 PassRefPtr<RenderStyle> CSSStyleSelector::styleForDocument(Document* document)
1218 {
1219     Frame* frame = document->frame();
1220
1221     RefPtr<RenderStyle> documentStyle = RenderStyle::create();
1222     documentStyle->setDisplay(BLOCK);
1223     documentStyle->setVisuallyOrdered(document->visuallyOrdered());
1224     documentStyle->setZoom(frame ? frame->pageZoomFactor() : 1);
1225     documentStyle->setPageScaleTransform(frame ? frame->pageScaleFactor() : 1);
1226     documentStyle->setUserModify(document->inDesignMode() ? READ_WRITE : READ_ONLY);
1227
1228     Element* docElement = document->documentElement();
1229     RenderObject* docElementRenderer = docElement ? docElement->renderer() : 0;
1230     if (docElementRenderer) {
1231         // Use the direction and writing-mode of the body to set the
1232         // viewport's direction and writing-mode unless the property is set on the document element.
1233         // If there is no body, then use the document element.
1234         RenderObject* bodyRenderer = document->body() ? document->body()->renderer() : 0;
1235         if (bodyRenderer && !document->writingModeSetOnDocumentElement())
1236             documentStyle->setWritingMode(bodyRenderer->style()->writingMode());
1237         else
1238             documentStyle->setWritingMode(docElementRenderer->style()->writingMode());
1239         if (bodyRenderer && !document->directionSetOnDocumentElement())
1240             documentStyle->setDirection(bodyRenderer->style()->direction());
1241         else
1242             documentStyle->setDirection(docElementRenderer->style()->direction());
1243     }
1244
1245     FontDescription fontDescription;
1246     fontDescription.setUsePrinterFont(document->printing());
1247     if (Settings* settings = document->settings()) {
1248         fontDescription.setRenderingMode(settings->fontRenderingMode());
1249         if (document->printing() && !settings->shouldPrintBackgrounds())
1250             documentStyle->setForceBackgroundsToWhite(true);
1251         const AtomicString& stdfont = settings->standardFontFamily();
1252         if (!stdfont.isEmpty()) {
1253             fontDescription.firstFamily().setFamily(stdfont);
1254             fontDescription.firstFamily().appendFamily(0);
1255         }
1256         fontDescription.setKeywordSize(CSSValueMedium - CSSValueXxSmall + 1);
1257         int size = CSSStyleSelector::fontSizeForKeyword(document, CSSValueMedium, false);
1258         fontDescription.setSpecifiedSize(size);
1259         bool useSVGZoomRules = document->isSVGDocument();
1260         fontDescription.setComputedSize(CSSStyleSelector::getComputedSizeFromSpecifiedSize(document, documentStyle.get(), fontDescription.isAbsoluteSize(), size, useSVGZoomRules));
1261     }
1262
1263     documentStyle->setFontDescription(fontDescription);
1264     documentStyle->font().update(0);
1265         
1266     return documentStyle.release();
1267 }
1268
1269 // If resolveForRootDefault is true, style based on user agent style sheet only. This is used in media queries, where
1270 // relative units are interpreted according to document root element style, styled only with UA stylesheet
1271
1272 PassRefPtr<RenderStyle> CSSStyleSelector::styleForElement(Element* e, RenderStyle* defaultParent, bool allowSharing, bool resolveForRootDefault, bool matchVisitedPseudoClass)
1273 {
1274     // Once an element has a renderer, we don't try to destroy it, since otherwise the renderer
1275     // will vanish if a style recalc happens during loading.
1276     if (allowSharing && !e->document()->haveStylesheetsLoaded() && !e->renderer()) {
1277         if (!s_styleNotYetAvailable) {
1278             s_styleNotYetAvailable = RenderStyle::create().releaseRef();
1279             s_styleNotYetAvailable->ref();
1280             s_styleNotYetAvailable->setDisplay(NONE);
1281             s_styleNotYetAvailable->font().update(m_fontSelector);
1282         }
1283         s_styleNotYetAvailable->ref();
1284         e->document()->setHasNodesWithPlaceholderStyle();
1285         return s_styleNotYetAvailable;
1286     }
1287
1288     initElement(e);
1289     initForStyleResolve(e, defaultParent);
1290     if (allowSharing) {
1291         RenderStyle* sharedStyle = locateSharedStyle();
1292         if (sharedStyle)
1293             return sharedStyle;
1294     }
1295
1296     // Compute our style allowing :visited to match first.
1297     RefPtr<RenderStyle> visitedStyle;
1298     if (!matchVisitedPseudoClass && m_parentStyle && (m_parentStyle->insideLink() || e->isLink()) && e->document()->usesLinkRules()) {
1299         // Fetch our parent style.
1300         RenderStyle* parentStyle = m_parentStyle;
1301         if (!e->isLink()) {
1302             // Use the parent's visited style if one exists.
1303             RenderStyle* parentVisitedStyle = m_parentStyle->getCachedPseudoStyle(VISITED_LINK);
1304             if (parentVisitedStyle)
1305                 parentStyle = parentVisitedStyle;
1306         }
1307         visitedStyle = styleForElement(e, parentStyle, false, false, true);
1308         initForStyleResolve(e, defaultParent);
1309     }
1310
1311     m_checker.m_matchVisitedPseudoClass = matchVisitedPseudoClass;
1312
1313     m_style = RenderStyle::create();
1314
1315     if (m_parentStyle)
1316         m_style->inheritFrom(m_parentStyle);
1317     else
1318         m_parentStyle = style();
1319
1320     if (e->isLink()) {
1321         m_style->setIsLink(true);
1322         m_style->setInsideLink(m_elementLinkState);
1323     }
1324     
1325     if (visitedStyle) {
1326         // Copy any pseudo bits that the visited style has to the primary style so that
1327         // pseudo element styles will continue to work for pseudo elements inside :visited
1328         // links.
1329         for (unsigned pseudo = FIRST_PUBLIC_PSEUDOID; pseudo < FIRST_INTERNAL_PSEUDOID; ++pseudo) {
1330             if (visitedStyle->hasPseudoStyle(static_cast<PseudoId>(pseudo)))
1331                 m_style->setHasPseudoStyle(static_cast<PseudoId>(pseudo));
1332         }
1333         if (m_elementLinkState == InsideUnvisitedLink)
1334             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.
1335         else
1336             visitedStyle->setStyleType(VISITED_LINK);
1337     }
1338
1339     if (simpleDefaultStyleSheet && !elementCanUseSimpleDefaultStyle(e)) {
1340         loadFullDefaultStyle();
1341         assertNoSiblingRulesInDefaultStyle();
1342     }
1343
1344 #if ENABLE(SVG)
1345     static bool loadedSVGUserAgentSheet;
1346     if (e->isSVGElement() && !loadedSVGUserAgentSheet) {
1347         // SVG rules.
1348         loadedSVGUserAgentSheet = true;
1349         CSSStyleSheet* svgSheet = parseUASheet(svgUserAgentStyleSheet, sizeof(svgUserAgentStyleSheet));
1350         defaultStyle->addRulesFromSheet(svgSheet, screenEval());
1351         defaultPrintStyle->addRulesFromSheet(svgSheet, printEval());
1352         assertNoSiblingRulesInDefaultStyle();
1353     }
1354 #endif
1355
1356 #if ENABLE(MATHML)
1357     static bool loadedMathMLUserAgentSheet;
1358     if (e->isMathMLElement() && !loadedMathMLUserAgentSheet) {
1359         // MathML rules.
1360         loadedMathMLUserAgentSheet = true;
1361         CSSStyleSheet* mathMLSheet = parseUASheet(mathmlUserAgentStyleSheet, sizeof(mathmlUserAgentStyleSheet));
1362         defaultStyle->addRulesFromSheet(mathMLSheet, screenEval());
1363         defaultPrintStyle->addRulesFromSheet(mathMLSheet, printEval());
1364         // There are some sibling rules here.
1365         collectSiblingRulesInDefaultStyle();
1366     }
1367 #endif
1368
1369 #if ENABLE(VIDEO)
1370     static bool loadedMediaStyleSheet;
1371     if (!loadedMediaStyleSheet && (e->hasTagName(videoTag) || e->hasTagName(audioTag))) {
1372         loadedMediaStyleSheet = true;
1373         String mediaRules = String(mediaControlsUserAgentStyleSheet, sizeof(mediaControlsUserAgentStyleSheet)) + RenderTheme::themeForPage(e->document()->page())->extraMediaControlsStyleSheet();
1374         CSSStyleSheet* mediaControlsSheet = parseUASheet(mediaRules);
1375         defaultStyle->addRulesFromSheet(mediaControlsSheet, screenEval());
1376         defaultPrintStyle->addRulesFromSheet(mediaControlsSheet, printEval());
1377         assertNoSiblingRulesInDefaultStyle();
1378     }
1379 #endif
1380
1381 #if ENABLE(FULLSCREEN_API)
1382     static bool loadedFullScreenStyleSheet;
1383     if (!loadedFullScreenStyleSheet && e->document()->webkitIsFullScreen()) {
1384         loadedFullScreenStyleSheet = true;
1385         String fullscreenRules = String(fullscreenUserAgentStyleSheet, sizeof(fullscreenUserAgentStyleSheet)) + RenderTheme::defaultTheme()->extraFullScreenStyleSheet();
1386         CSSStyleSheet* fullscreenSheet = parseUASheet(fullscreenRules);
1387         defaultStyle->addRulesFromSheet(fullscreenSheet, screenEval());
1388         defaultQuirksStyle->addRulesFromSheet(fullscreenSheet, screenEval());
1389     }
1390 #endif
1391
1392     int firstUARule = -1, lastUARule = -1;
1393     int firstUserRule = -1, lastUserRule = -1;
1394     int firstAuthorRule = -1, lastAuthorRule = -1;
1395     matchUARules(firstUARule, lastUARule);
1396
1397     if (!resolveForRootDefault) {
1398         // 4. Now we check user sheet rules.
1399         if (m_matchAuthorAndUserStyles)
1400             matchRules(m_userStyle.get(), firstUserRule, lastUserRule, false);
1401
1402         // 5. Now check author rules, beginning first with presentational attributes
1403         // mapped from HTML.
1404         if (m_styledElement) {
1405             // Ask if the HTML element has mapped attributes.
1406             if (m_styledElement->hasMappedAttributes()) {
1407                 // Walk our attribute list and add in each decl.
1408                 const NamedNodeMap* map = m_styledElement->attributeMap();
1409                 for (unsigned i = 0; i < map->length(); i++) {
1410                     Attribute* attr = map->attributeItem(i);
1411                     if (attr->isMappedAttribute() && attr->decl()) {
1412                         lastAuthorRule = m_matchedDecls.size();
1413                         if (firstAuthorRule == -1)
1414                             firstAuthorRule = lastAuthorRule;
1415                         addMatchedDeclaration(attr->decl());
1416                     }
1417                 }
1418             }
1419
1420             // Now we check additional mapped declarations.
1421             // Tables and table cells share an additional mapped rule that must be applied
1422             // after all attributes, since their mapped style depends on the values of multiple attributes.
1423             if (m_styledElement->canHaveAdditionalAttributeStyleDecls()) {
1424                 m_additionalAttributeStyleDecls.clear();
1425                 m_styledElement->additionalAttributeStyleDecls(m_additionalAttributeStyleDecls);
1426                 if (!m_additionalAttributeStyleDecls.isEmpty()) {
1427                     unsigned additionalDeclsSize = m_additionalAttributeStyleDecls.size();
1428                     if (firstAuthorRule == -1)
1429                         firstAuthorRule = m_matchedDecls.size();
1430                     lastAuthorRule = m_matchedDecls.size() + additionalDeclsSize - 1;
1431                     for (unsigned i = 0; i < additionalDeclsSize; i++)
1432                         addMatchedDeclaration(m_additionalAttributeStyleDecls[i]);
1433                 }
1434             }
1435             if (m_styledElement->isHTMLElement()) {
1436                 bool isAuto;
1437                 TextDirection textDirection = toHTMLElement(m_styledElement)->directionalityIfhasDirAutoAttribute(isAuto);
1438                 if (isAuto)
1439                     addMatchedDeclaration(textDirection == LTR ? leftToRightDeclaration() : rightToLeftDeclaration());
1440             }
1441         }
1442     
1443         // 6. Check the rules in author sheets next.
1444         if (m_matchAuthorAndUserStyles)
1445             matchRules(m_authorStyle.get(), firstAuthorRule, lastAuthorRule, false);
1446
1447         // 7. Now check our inline style attribute.
1448         if (m_matchAuthorAndUserStyles && m_styledElement) {
1449             CSSMutableStyleDeclaration* inlineDecl = m_styledElement->inlineStyleDecl();
1450             if (inlineDecl) {
1451                 lastAuthorRule = m_matchedDecls.size();
1452                 if (firstAuthorRule == -1)
1453                     firstAuthorRule = lastAuthorRule;
1454                 addMatchedDeclaration(inlineDecl);
1455             }
1456         }
1457     }
1458
1459     // Reset the value back before applying properties, so that -webkit-link knows what color to use.
1460     m_checker.m_matchVisitedPseudoClass = matchVisitedPseudoClass;
1461     
1462     // Now we have all of the matched rules in the appropriate order.  Walk the rules and apply
1463     // high-priority properties first, i.e., those properties that other properties depend on.
1464     // The order is (1) high-priority not important, (2) high-priority important, (3) normal not important
1465     // and (4) normal important.
1466     m_lineHeightValue = 0;
1467     applyDeclarations<true>(false, 0, m_matchedDecls.size() - 1);
1468     if (!resolveForRootDefault) {
1469         applyDeclarations<true>(true, firstAuthorRule, lastAuthorRule);
1470         applyDeclarations<true>(true, firstUserRule, lastUserRule);
1471     }
1472     applyDeclarations<true>(true, firstUARule, lastUARule);
1473     
1474     // If our font got dirtied, go ahead and update it now.
1475     if (m_fontDirty)
1476         updateFont();
1477
1478     // Line-height is set when we are sure we decided on the font-size
1479     if (m_lineHeightValue)
1480         applyProperty(CSSPropertyLineHeight, m_lineHeightValue);
1481
1482     // Now do the normal priority UA properties.
1483     applyDeclarations<false>(false, firstUARule, lastUARule);
1484     
1485     // Cache our border and background so that we can examine them later.
1486     cacheBorderAndBackground();
1487     
1488     // Now do the author and user normal priority properties and all the !important properties.
1489     if (!resolveForRootDefault) {
1490         applyDeclarations<false>(false, lastUARule + 1, m_matchedDecls.size() - 1);
1491         applyDeclarations<false>(true, firstAuthorRule, lastAuthorRule);
1492         applyDeclarations<false>(true, firstUserRule, lastUserRule);
1493     }
1494     applyDeclarations<false>(true, firstUARule, lastUARule);
1495
1496     ASSERT(!m_fontDirty);
1497     // If our font got dirtied by one of the non-essential font props, 
1498     // go ahead and update it a second time.
1499     if (m_fontDirty)
1500         updateFont();
1501     
1502     // Clean up our style object's display and text decorations (among other fixups).
1503     adjustRenderStyle(style(), m_parentStyle, e);
1504
1505     // Start loading images referenced by this style.
1506     loadPendingImages();
1507
1508     // If we have first-letter pseudo style, do not share this style
1509     if (m_style->hasPseudoStyle(FIRST_LETTER))
1510         m_style->setUnique();
1511
1512     if (visitedStyle) {
1513         // Add the visited style off the main style.
1514         m_style->addCachedPseudoStyle(visitedStyle.release());
1515     }
1516
1517     if (!matchVisitedPseudoClass)
1518         initElement(0); // Clear out for the next resolve.
1519
1520     // Now return the style.
1521     return m_style.release();
1522 }
1523
1524 PassRefPtr<RenderStyle> CSSStyleSelector::styleForKeyframe(const RenderStyle* elementStyle, const WebKitCSSKeyframeRule* keyframeRule, KeyframeValue& keyframe)
1525 {
1526     if (keyframeRule->style())
1527         addMatchedDeclaration(keyframeRule->style());
1528
1529     ASSERT(!m_style);
1530
1531     // Create the style
1532     m_style = RenderStyle::clone(elementStyle);
1533
1534     m_lineHeightValue = 0;
1535
1536     // We don't need to bother with !important. Since there is only ever one
1537     // decl, there's nothing to override. So just add the first properties.
1538     if (keyframeRule->style())
1539         applyDeclarations<true>(false, 0, m_matchedDecls.size() - 1);
1540
1541     // If our font got dirtied, go ahead and update it now.
1542     if (m_fontDirty)
1543         updateFont();
1544
1545     // Line-height is set when we are sure we decided on the font-size
1546     if (m_lineHeightValue)
1547         applyProperty(CSSPropertyLineHeight, m_lineHeightValue);
1548
1549     // Now do rest of the properties.
1550     if (keyframeRule->style())
1551         applyDeclarations<false>(false, 0, m_matchedDecls.size() - 1);
1552
1553     // If our font got dirtied by one of the non-essential font props,
1554     // go ahead and update it a second time.
1555     if (m_fontDirty)
1556         updateFont();
1557
1558     // Start loading images referenced by this style.
1559     loadPendingImages();
1560
1561     // Add all the animating properties to the keyframe.
1562     if (keyframeRule->style()) {
1563         CSSMutableStyleDeclaration::const_iterator end = keyframeRule->style()->end();
1564         for (CSSMutableStyleDeclaration::const_iterator it = keyframeRule->style()->begin(); it != end; ++it) {
1565             int property = (*it).id();
1566             // Timing-function within keyframes is special, because it is not animated; it just
1567             // describes the timing function between this keyframe and the next.
1568             if (property != CSSPropertyWebkitAnimationTimingFunction)
1569                 keyframe.addProperty(property);
1570         }
1571     }
1572
1573     return m_style.release();
1574 }
1575
1576 void CSSStyleSelector::keyframeStylesForAnimation(Element* e, const RenderStyle* elementStyle, KeyframeList& list)
1577 {
1578     list.clear();
1579     
1580     // Get the keyframesRule for this name
1581     if (!e || list.animationName().isEmpty())
1582         return;
1583
1584     m_keyframesRuleMap.checkConsistency();
1585    
1586     if (!m_keyframesRuleMap.contains(list.animationName().impl()))
1587         return;
1588         
1589     const WebKitCSSKeyframesRule* rule = m_keyframesRuleMap.find(list.animationName().impl()).get()->second.get();
1590     
1591     // Construct and populate the style for each keyframe
1592     for (unsigned i = 0; i < rule->length(); ++i) {
1593         // Apply the declaration to the style. This is a simplified version of the logic in styleForElement
1594         initElement(e);
1595         initForStyleResolve(e);
1596         
1597         const WebKitCSSKeyframeRule* keyframeRule = rule->item(i);
1598
1599         KeyframeValue keyframe(0, 0);
1600         keyframe.setStyle(styleForKeyframe(elementStyle, keyframeRule, keyframe));
1601
1602         // Add this keyframe style to all the indicated key times
1603         Vector<float> keys;
1604         keyframeRule->getKeys(keys);
1605         for (size_t keyIndex = 0; keyIndex < keys.size(); ++keyIndex) {
1606             keyframe.setKey(keys[keyIndex]);
1607             list.insert(keyframe);
1608         }
1609     }
1610     
1611     // If the 0% keyframe is missing, create it (but only if there is at least one other keyframe)
1612     int initialListSize = list.size();
1613     if (initialListSize > 0 && list[0].key() != 0) {
1614         RefPtr<WebKitCSSKeyframeRule> keyframeRule = WebKitCSSKeyframeRule::create();
1615         keyframeRule->setKeyText("0%");
1616         KeyframeValue keyframe(0, 0);
1617         keyframe.setStyle(styleForKeyframe(elementStyle, keyframeRule.get(), keyframe));
1618         list.insert(keyframe);
1619     }
1620
1621     // If the 100% keyframe is missing, create it (but only if there is at least one other keyframe)
1622     if (initialListSize > 0 && (list[list.size() - 1].key() != 1)) {
1623         RefPtr<WebKitCSSKeyframeRule> keyframeRule = WebKitCSSKeyframeRule::create();
1624         keyframeRule->setKeyText("100%");
1625         KeyframeValue keyframe(1, 0);
1626         keyframe.setStyle(styleForKeyframe(elementStyle, keyframeRule.get(), keyframe));
1627         list.insert(keyframe);
1628     }
1629 }
1630
1631 PassRefPtr<RenderStyle> CSSStyleSelector::pseudoStyleForElement(PseudoId pseudo, Element* e, RenderStyle* parentStyle, bool matchVisitedPseudoClass)
1632 {
1633     if (!e)
1634         return 0;
1635
1636     initElement(e);
1637
1638     // Compute our :visited style first, so that we know whether or not we'll need to create a normal style just to hang it
1639     // off of.
1640     RefPtr<RenderStyle> visitedStyle;
1641     if (!matchVisitedPseudoClass && parentStyle && parentStyle->insideLink()) {
1642         // Fetch our parent style with :visited in effect.
1643         RenderStyle* parentVisitedStyle = parentStyle->getCachedPseudoStyle(VISITED_LINK);
1644         visitedStyle = pseudoStyleForElement(pseudo, e, parentVisitedStyle ? parentVisitedStyle : parentStyle, true);
1645         if (visitedStyle)
1646             visitedStyle->setStyleType(VISITED_LINK);
1647     }
1648
1649     initForStyleResolve(e, parentStyle, pseudo);
1650     m_style = RenderStyle::create();
1651     if (parentStyle)
1652         m_style->inheritFrom(parentStyle);
1653
1654     m_checker.m_matchVisitedPseudoClass = matchVisitedPseudoClass;
1655
1656     // Since we don't use pseudo-elements in any of our quirk/print user agent rules, don't waste time walking
1657     // those rules.
1658     
1659     // Check UA, user and author rules.
1660     int firstUARule = -1, lastUARule = -1, firstUserRule = -1, lastUserRule = -1, firstAuthorRule = -1, lastAuthorRule = -1;
1661     matchUARules(firstUARule, lastUARule);
1662
1663     if (m_matchAuthorAndUserStyles) {
1664         matchRules(m_userStyle.get(), firstUserRule, lastUserRule, false);
1665         matchRules(m_authorStyle.get(), firstAuthorRule, lastAuthorRule, false);
1666     }
1667
1668     if (m_matchedDecls.isEmpty() && !visitedStyle)
1669         return 0;
1670
1671     m_style->setStyleType(pseudo);
1672     
1673     m_lineHeightValue = 0;
1674     
1675     // Reset the value back before applying properties, so that -webkit-link knows what color to use.
1676     m_checker.m_matchVisitedPseudoClass = matchVisitedPseudoClass;
1677
1678     // High-priority properties.
1679     applyDeclarations<true>(false, 0, m_matchedDecls.size() - 1);
1680     applyDeclarations<true>(true, firstAuthorRule, lastAuthorRule);
1681     applyDeclarations<true>(true, firstUserRule, lastUserRule);
1682     applyDeclarations<true>(true, firstUARule, lastUARule);
1683     
1684     // If our font got dirtied, go ahead and update it now.
1685     if (m_fontDirty)
1686         updateFont();
1687
1688     // Line-height is set when we are sure we decided on the font-size
1689     if (m_lineHeightValue)
1690         applyProperty(CSSPropertyLineHeight, m_lineHeightValue);
1691     
1692     // Now do the normal priority properties.
1693     applyDeclarations<false>(false, firstUARule, lastUARule);
1694     
1695     // Cache our border and background so that we can examine them later.
1696     cacheBorderAndBackground();
1697     
1698     applyDeclarations<false>(false, lastUARule + 1, m_matchedDecls.size() - 1);
1699     applyDeclarations<false>(true, firstAuthorRule, lastAuthorRule);
1700     applyDeclarations<false>(true, firstUserRule, lastUserRule);
1701     applyDeclarations<false>(true, firstUARule, lastUARule);
1702     
1703     // If our font got dirtied by one of the non-essential font props, 
1704     // go ahead and update it a second time.
1705     if (m_fontDirty)
1706         updateFont();
1707
1708     // Clean up our style object's display and text decorations (among other fixups).
1709     adjustRenderStyle(style(), parentStyle, 0);
1710
1711     // Start loading images referenced by this style.
1712     loadPendingImages();
1713
1714     // Hang our visited style off m_style.
1715     if (visitedStyle)
1716         m_style->addCachedPseudoStyle(visitedStyle.release());
1717         
1718     // Now return the style.
1719     return m_style.release();
1720 }
1721
1722 PassRefPtr<RenderStyle> CSSStyleSelector::styleForPage(int pageIndex)
1723 {
1724     initForStyleResolve(m_checker.m_document->documentElement()); // m_rootElementStyle will be set to the document style.
1725
1726     m_style = RenderStyle::create();
1727     m_style->inheritFrom(m_rootElementStyle);
1728
1729     const bool isLeft = isLeftPage(pageIndex);
1730     const bool isFirst = isFirstPage(pageIndex);
1731     const String page = pageName(pageIndex);
1732     matchPageRules(defaultPrintStyle, isLeft, isFirst, page);
1733     matchPageRules(m_userStyle.get(), isLeft, isFirst, page);
1734     matchPageRules(m_authorStyle.get(), isLeft, isFirst, page);
1735     m_lineHeightValue = 0;
1736     applyDeclarations<true>(false, 0, m_matchedDecls.size() - 1);
1737
1738     // If our font got dirtied, go ahead and update it now.
1739     if (m_fontDirty)
1740         updateFont();
1741
1742     // Line-height is set when we are sure we decided on the font-size
1743     if (m_lineHeightValue)
1744         applyProperty(CSSPropertyLineHeight, m_lineHeightValue);
1745
1746     applyDeclarations<false>(false, 0, m_matchedDecls.size() - 1);
1747
1748     // Start loading images referenced by this style.
1749     loadPendingImages();
1750
1751     // Now return the style.
1752     return m_style.release();
1753 }
1754
1755 static void addIntrinsicMargins(RenderStyle* style)
1756 {
1757     // Intrinsic margin value.
1758     const int intrinsicMargin = 2 * style->effectiveZoom();
1759     
1760     // FIXME: Using width/height alone and not also dealing with min-width/max-width is flawed.
1761     // FIXME: Using "quirk" to decide the margin wasn't set is kind of lame.
1762     if (style->width().isIntrinsicOrAuto()) {
1763         if (style->marginLeft().quirk())
1764             style->setMarginLeft(Length(intrinsicMargin, Fixed));
1765         if (style->marginRight().quirk())
1766             style->setMarginRight(Length(intrinsicMargin, Fixed));
1767     }
1768
1769     if (style->height().isAuto()) {
1770         if (style->marginTop().quirk())
1771             style->setMarginTop(Length(intrinsicMargin, Fixed));
1772         if (style->marginBottom().quirk())
1773             style->setMarginBottom(Length(intrinsicMargin, Fixed));
1774     }
1775 }
1776
1777 static inline bool isAtShadowBoundary(Element* element)
1778 {
1779     if (!element)
1780         return false;
1781
1782     ContainerNode* parentNode = element->parentNode();
1783     return parentNode && parentNode->isShadowBoundary();
1784 }
1785
1786 void CSSStyleSelector::adjustRenderStyle(RenderStyle* style, RenderStyle* parentStyle, Element *e)
1787 {
1788     // Cache our original display.
1789     style->setOriginalDisplay(style->display());
1790
1791     if (style->display() != NONE) {
1792         // If we have a <td> that specifies a float property, in quirks mode we just drop the float
1793         // property.
1794         // Sites also commonly use display:inline/block on <td>s and <table>s.  In quirks mode we force
1795         // these tags to retain their display types.
1796         if (!m_checker.m_strictParsing && e) {
1797             if (e->hasTagName(tdTag)) {
1798                 style->setDisplay(TABLE_CELL);
1799                 style->setFloating(FNONE);
1800             }
1801             else if (e->hasTagName(tableTag))
1802                 style->setDisplay(style->isDisplayInlineType() ? INLINE_TABLE : TABLE);
1803         }
1804
1805         if (e && (e->hasTagName(tdTag) || e->hasTagName(thTag))) {
1806             if (style->whiteSpace() == KHTML_NOWRAP) {
1807                 // Figure out if we are really nowrapping or if we should just
1808                 // use normal instead.  If the width of the cell is fixed, then
1809                 // we don't actually use NOWRAP.
1810                 if (style->width().isFixed())
1811                     style->setWhiteSpace(NORMAL);
1812                 else
1813                     style->setWhiteSpace(NOWRAP);
1814             }
1815         }
1816
1817         // Tables never support the -webkit-* values for text-align and will reset back to the default.
1818         if (e && e->hasTagName(tableTag) && (style->textAlign() == WEBKIT_LEFT || style->textAlign() == WEBKIT_CENTER || style->textAlign() == WEBKIT_RIGHT))
1819             style->setTextAlign(TAAUTO);
1820
1821         // Frames and framesets never honor position:relative or position:absolute.  This is necessary to
1822         // fix a crash where a site tries to position these objects.  They also never honor display.
1823         if (e && (e->hasTagName(frameTag) || e->hasTagName(framesetTag))) {
1824             style->setPosition(StaticPosition);
1825             style->setDisplay(BLOCK);
1826         }
1827
1828         // Table headers with a text-align of auto will change the text-align to center.
1829         if (e && e->hasTagName(thTag) && style->textAlign() == TAAUTO)
1830             style->setTextAlign(CENTER);
1831
1832         if (e && e->hasTagName(legendTag))
1833             style->setDisplay(BLOCK);
1834
1835         // Mutate the display to BLOCK or TABLE for certain cases, e.g., if someone attempts to
1836         // position or float an inline, compact, or run-in.  Cache the original display, since it
1837         // may be needed for positioned elements that have to compute their static normal flow
1838         // positions.  We also force inline-level roots to be block-level.
1839         if (style->display() != BLOCK && style->display() != TABLE && style->display() != BOX &&
1840             (style->position() == AbsolutePosition || style->position() == FixedPosition || style->floating() != FNONE ||
1841              (e && e->document()->documentElement() == e))) {
1842             if (style->display() == INLINE_TABLE)
1843                 style->setDisplay(TABLE);
1844             else if (style->display() == INLINE_BOX)
1845                 style->setDisplay(BOX);
1846             else if (style->display() == LIST_ITEM) {
1847                 // It is a WinIE bug that floated list items lose their bullets, so we'll emulate the quirk,
1848                 // but only in quirks mode.
1849                 if (!m_checker.m_strictParsing && style->floating() != FNONE)
1850                     style->setDisplay(BLOCK);
1851             }
1852             else
1853                 style->setDisplay(BLOCK);
1854         }
1855         
1856         // FIXME: Don't support this mutation for pseudo styles like first-letter or first-line, since it's not completely
1857         // clear how that should work.
1858         if (style->display() == INLINE && style->styleType() == NOPSEUDO && parentStyle && style->writingMode() != parentStyle->writingMode())
1859             style->setDisplay(INLINE_BLOCK);
1860         
1861         // After performing the display mutation, check table rows.  We do not honor position:relative on
1862         // table rows or cells.  This has been established in CSS2.1 (and caused a crash in containingBlock()
1863         // on some sites).
1864         if ((style->display() == TABLE_HEADER_GROUP || style->display() == TABLE_ROW_GROUP
1865              || style->display() == TABLE_FOOTER_GROUP || style->display() == TABLE_ROW) &&
1866              style->position() == RelativePosition)
1867             style->setPosition(StaticPosition);
1868
1869         // writing-mode does not apply to table row groups, table column groups, table rows, and table columns.
1870         // FIXME: Table cells should be allowed to be perpendicular or flipped with respect to the table, though.
1871         if (style->display() == TABLE_COLUMN || style->display() == TABLE_COLUMN_GROUP || style->display() == TABLE_FOOTER_GROUP
1872             || style->display() == TABLE_HEADER_GROUP || style->display() == TABLE_ROW || style->display() == TABLE_ROW_GROUP
1873             || style->display() == TABLE_CELL)
1874             style->setWritingMode(parentStyle->writingMode());
1875
1876         // FIXME: Since we don't support block-flow on flexible boxes yet, disallow setting
1877         // of block-flow to anything other than TopToBottomWritingMode.
1878         // https://bugs.webkit.org/show_bug.cgi?id=46418 - Flexible box support.
1879         if (style->writingMode() != TopToBottomWritingMode && (style->display() == BOX || style->display() == INLINE_BOX))
1880             style->setWritingMode(TopToBottomWritingMode);
1881     }
1882
1883     // Make sure our z-index value is only applied if the object is positioned.
1884     if (style->position() == StaticPosition)
1885         style->setHasAutoZIndex();
1886
1887     // Auto z-index becomes 0 for the root element and transparent objects.  This prevents
1888     // cases where objects that should be blended as a single unit end up with a non-transparent
1889     // object wedged in between them.  Auto z-index also becomes 0 for objects that specify transforms/masks/reflections.
1890     if (style->hasAutoZIndex() && ((e && e->document()->documentElement() == e) || style->opacity() < 1.0f || 
1891         style->hasTransformRelatedProperty() || style->hasMask() || style->boxReflect()))
1892         style->setZIndex(0);
1893
1894     // Textarea considers overflow visible as auto.
1895     if (e && e->hasTagName(textareaTag)) {
1896         style->setOverflowX(style->overflowX() == OVISIBLE ? OAUTO : style->overflowX());
1897         style->setOverflowY(style->overflowY() == OVISIBLE ? OAUTO : style->overflowY());
1898     }
1899
1900     // Finally update our text decorations in effect, but don't allow text-decoration to percolate through
1901     // tables, inline blocks, inline tables, run-ins, or shadow DOM.
1902     if (style->display() == TABLE || style->display() == INLINE_TABLE || style->display() == RUN_IN
1903         || style->display() == INLINE_BLOCK || style->display() == INLINE_BOX || isAtShadowBoundary(e))
1904         style->setTextDecorationsInEffect(style->textDecoration());
1905     else
1906         style->addToTextDecorationsInEffect(style->textDecoration());
1907     
1908     // If either overflow value is not visible, change to auto.
1909     if (style->overflowX() == OMARQUEE && style->overflowY() != OMARQUEE)
1910         style->setOverflowY(OMARQUEE);
1911     else if (style->overflowY() == OMARQUEE && style->overflowX() != OMARQUEE)
1912         style->setOverflowX(OMARQUEE);
1913     else if (style->overflowX() == OVISIBLE && style->overflowY() != OVISIBLE)
1914         style->setOverflowX(OAUTO);
1915     else if (style->overflowY() == OVISIBLE && style->overflowX() != OVISIBLE)
1916         style->setOverflowY(OAUTO);
1917
1918     // Table rows, sections and the table itself will support overflow:hidden and will ignore scroll/auto.
1919     // FIXME: Eventually table sections will support auto and scroll.
1920     if (style->display() == TABLE || style->display() == INLINE_TABLE ||
1921         style->display() == TABLE_ROW_GROUP || style->display() == TABLE_ROW) {
1922         if (style->overflowX() != OVISIBLE && style->overflowX() != OHIDDEN) 
1923             style->setOverflowX(OVISIBLE);
1924         if (style->overflowY() != OVISIBLE && style->overflowY() != OHIDDEN) 
1925             style->setOverflowY(OVISIBLE);
1926     }
1927
1928     // Menulists should have visible overflow
1929     if (style->appearance() == MenulistPart) {
1930         style->setOverflowX(OVISIBLE);
1931         style->setOverflowY(OVISIBLE);
1932     }
1933
1934     // Cull out any useless layers and also repeat patterns into additional layers.
1935     style->adjustBackgroundLayers();
1936     style->adjustMaskLayers();
1937
1938     // Do the same for animations and transitions.
1939     style->adjustAnimations();
1940     style->adjustTransitions();
1941
1942     // Important: Intrinsic margins get added to controls before the theme has adjusted the style, since the theme will
1943     // alter fonts and heights/widths.
1944     if (e && e->isFormControlElement() && style->fontSize() >= 11) {
1945         // Don't apply intrinsic margins to image buttons.  The designer knows how big the images are,
1946         // so we have to treat all image buttons as though they were explicitly sized.
1947         if (!e->hasTagName(inputTag) || !static_cast<HTMLInputElement*>(e)->isImageButton())
1948             addIntrinsicMargins(style);
1949     }
1950
1951     // Let the theme also have a crack at adjusting the style.
1952     if (style->hasAppearance())
1953         RenderTheme::defaultTheme()->adjustStyle(this, style, e, m_hasUAAppearance, m_borderData, m_backgroundData, m_backgroundColor);
1954
1955 #if ENABLE(SVG)
1956     if (e && e->isSVGElement()) {
1957         // Spec: http://www.w3.org/TR/SVG/masking.html#OverflowProperty
1958         if (style->overflowY() == OSCROLL)
1959             style->setOverflowY(OHIDDEN);
1960         else if (style->overflowY() == OAUTO)
1961             style->setOverflowY(OVISIBLE);
1962
1963         if (style->overflowX() == OSCROLL)
1964             style->setOverflowX(OHIDDEN);
1965         else if (style->overflowX() == OAUTO)
1966             style->setOverflowX(OVISIBLE);
1967
1968         // Only the root <svg> element in an SVG document fragment tree honors css position
1969         if (!(e->hasTagName(SVGNames::svgTag) && e->parentNode() && !e->parentNode()->isSVGElement()))
1970             style->setPosition(RenderStyle::initialPosition());
1971     }
1972 #endif
1973 }
1974
1975 void CSSStyleSelector::updateFont()
1976 {
1977     checkForTextSizeAdjust();
1978     checkForGenericFamilyChange(style(), m_parentStyle);
1979     checkForZoomChange(style(), m_parentStyle);
1980     m_style->font().update(m_fontSelector);
1981     m_fontDirty = false;
1982 }
1983
1984 void CSSStyleSelector::cacheBorderAndBackground()
1985 {
1986     m_hasUAAppearance = m_style->hasAppearance();
1987     if (m_hasUAAppearance) {
1988         m_borderData = m_style->border();
1989         m_backgroundData = *m_style->backgroundLayers();
1990         m_backgroundColor = m_style->backgroundColor();
1991     }
1992 }
1993
1994 PassRefPtr<CSSRuleList> CSSStyleSelector::styleRulesForElement(Element* e, unsigned rulesToInclude)
1995 {
1996     return pseudoStyleRulesForElement(e, NOPSEUDO, rulesToInclude);
1997 }
1998
1999 PassRefPtr<CSSRuleList> CSSStyleSelector::pseudoStyleRulesForElement(Element* e, PseudoId pseudoId, unsigned rulesToInclude)
2000 {
2001     if (!e || !e->document()->haveStylesheetsLoaded())
2002         return 0;
2003
2004     m_checker.m_collectRulesOnly = true;
2005
2006     initElement(e);
2007     initForStyleResolve(e, 0, pseudoId);
2008
2009     if (rulesToInclude & UAAndUserCSSRules) {
2010         int firstUARule = -1, lastUARule = -1;
2011         // First we match rules from the user agent sheet.
2012         matchUARules(firstUARule, lastUARule);
2013
2014         // Now we check user sheet rules.
2015         if (m_matchAuthorAndUserStyles) {
2016             int firstUserRule = -1, lastUserRule = -1;
2017             matchRules(m_userStyle.get(), firstUserRule, lastUserRule, rulesToInclude & EmptyCSSRules);
2018         }
2019     }
2020
2021     if (m_matchAuthorAndUserStyles) {
2022         m_checker.m_sameOriginOnly = !(rulesToInclude & CrossOriginCSSRules);
2023
2024         // Check the rules in author sheets.
2025         int firstAuthorRule = -1, lastAuthorRule = -1;
2026         matchRules(m_authorStyle.get(), firstAuthorRule, lastAuthorRule, rulesToInclude & EmptyCSSRules);
2027
2028         m_checker.m_sameOriginOnly = false;
2029     }
2030
2031     m_checker.m_collectRulesOnly = false;
2032    
2033     return m_ruleList.release();
2034 }
2035
2036 inline bool CSSStyleSelector::checkSelector(const RuleData& ruleData)
2037 {
2038     m_dynamicPseudo = NOPSEUDO;
2039     m_checker.m_hasUnknownPseudoElements = false;
2040
2041     // Let the slow path handle SVG as it has some additional rules regarding shadow trees.
2042     if (ruleData.hasFastCheckableSelector() && !m_element->isSVGElement()) {
2043         // We know this selector does not include any pseudo selectors.
2044         if (m_checker.m_pseudoStyle != NOPSEUDO)
2045             return false;
2046         // We know a sufficiently simple single part selector matches simply because we found it from the rule hash.
2047         // This is limited to HTML only so we don't need to check the namespace.
2048         if (ruleData.hasTopSelectorMatchingHTMLBasedOnRuleHash() && !ruleData.hasMultipartSelector() && m_element->isHTMLElement())
2049             return true;
2050         return SelectorChecker::fastCheckSelector(ruleData.selector(), m_element);
2051     }
2052
2053     // Slow path.
2054     SelectorMatch match = m_checker.checkSelector(ruleData.selector(), m_element, m_dynamicPseudo, false, false, style(), m_parentNode ? m_parentNode->renderStyle() : 0);
2055     if (match != SelectorMatches)
2056         return false;
2057     if (m_checker.m_pseudoStyle != NOPSEUDO && m_checker.m_pseudoStyle != m_dynamicPseudo)
2058         return false;
2059     return true;
2060 }
2061     
2062 namespace {
2063
2064 inline bool selectorTagMatches(const Element* element, const CSSSelector* selector)
2065 {
2066     if (!selector->hasTag())
2067         return true;
2068     const AtomicString& localName = selector->tag().localName();
2069     if (localName != starAtom && localName != element->localName())
2070         return false;
2071     const AtomicString& namespaceURI = selector->tag().namespaceURI();
2072     return namespaceURI == starAtom || namespaceURI == element->namespaceURI();
2073 }
2074
2075 inline bool isFastCheckableSelector(const CSSSelector* selector)
2076 {
2077     for (; selector; selector = selector->tagHistory()) {
2078         if (selector->relation() != CSSSelector::Descendant && selector->relation() != CSSSelector::Child && selector->relation() != CSSSelector::SubSelector)
2079             return false;
2080         if (selector->m_match != CSSSelector::None && selector->m_match != CSSSelector::Id && selector->m_match != CSSSelector::Class)
2081             return false;
2082     }
2083     return true;
2084 }
2085     
2086 template <bool checkValue(const Element*, AtomicStringImpl*)>
2087 inline bool fastCheckSingleSelector(const CSSSelector*& selector, const Element*& element, const CSSSelector*& topChildOrSubselector, const Element*& topChildOrSubselectorMatchElement)
2088 {
2089     AtomicStringImpl* value = selector->value().impl();
2090     for (; element; element = element->parentElement()) {
2091         if (checkValue(element, value) && selectorTagMatches(element, selector)) {
2092             if (selector->relation() == CSSSelector::Descendant)
2093                 topChildOrSubselector = 0;
2094             else if (!topChildOrSubselector) {
2095                 ASSERT(selector->relation() == CSSSelector::Child || selector->relation() == CSSSelector::SubSelector);
2096                 topChildOrSubselector = selector;
2097                 topChildOrSubselectorMatchElement = element;
2098             }
2099             if (selector->relation() != CSSSelector::SubSelector)
2100                 element = element->parentElement();
2101             selector = selector->tagHistory();
2102             return true;
2103         }
2104         if (topChildOrSubselector) {
2105             // Child or subselector check failed.
2106             // If the match element is null, topChildOrSubselector was also the very topmost selector and had to match 
2107             // the original element we were checking.
2108             if (!topChildOrSubselectorMatchElement)
2109                 return false;
2110             // There may be other matches down the ancestor chain.
2111             // Rewind to the topmost child or subselector and the element it matched, continue checking ancestors.
2112             selector = topChildOrSubselector;
2113             element = topChildOrSubselectorMatchElement->parentElement();
2114             topChildOrSubselector = 0;
2115             return true;
2116         }
2117     }
2118     return false;
2119 }
2120
2121 inline bool checkClassValue(const Element* element, AtomicStringImpl* value) 
2122 {
2123     return element->hasClass() && static_cast<const StyledElement*>(element)->classNames().contains(value);
2124 }
2125
2126 inline bool checkIDValue(const Element* element, AtomicStringImpl* value) 
2127 {
2128     return element->hasID() && element->idForStyleResolution().impl() == value;
2129 }
2130
2131 inline bool checkTagValue(const Element*, AtomicStringImpl*)
2132 {
2133     return true;
2134 }
2135
2136 }
2137
2138 bool CSSStyleSelector::SelectorChecker::fastCheckSelector(const CSSSelector* selector, const Element* element)
2139 {
2140     ASSERT(isFastCheckableSelector(selector));
2141
2142     // The top selector requires tag check only as rule hashes have already handled id and class matches.
2143     if (!selectorTagMatches(element, selector))
2144         return false;
2145
2146     const CSSSelector* topChildOrSubselector = 0;
2147     const Element* topChildOrSubselectorMatchElement = 0;
2148     if (selector->relation() == CSSSelector::Child || selector->relation() == CSSSelector::SubSelector)
2149         topChildOrSubselector = selector;
2150
2151     if (selector->relation() != CSSSelector::SubSelector)
2152         element = element->parentElement();
2153
2154     selector = selector->tagHistory();
2155
2156     // We know this compound selector has descendant, child and subselector combinators only and all components are simple.
2157     while (selector) {
2158         switch (selector->m_match) {
2159         case CSSSelector::Class:
2160             if (!fastCheckSingleSelector<checkClassValue>(selector, element, topChildOrSubselector, topChildOrSubselectorMatchElement))
2161                 return false;
2162             break;
2163         case CSSSelector::Id:
2164             if (!fastCheckSingleSelector<checkIDValue>(selector, element, topChildOrSubselector, topChildOrSubselectorMatchElement))
2165                 return false;
2166             break;
2167         case CSSSelector::None:
2168             if (!fastCheckSingleSelector<checkTagValue>(selector, element, topChildOrSubselector, topChildOrSubselectorMatchElement))
2169                 return false;
2170             break;
2171         default:
2172             ASSERT_NOT_REACHED();
2173         }
2174     }
2175     return true;
2176 }
2177
2178 // Recursive check of selectors and combinators
2179 // It can return 3 different values:
2180 // * SelectorMatches         - the selector matches the element e
2181 // * SelectorFailsLocally    - the selector fails for the element e
2182 // * SelectorFailsCompletely - the selector fails for e and any sibling or ancestor of e
2183 CSSStyleSelector::SelectorMatch CSSStyleSelector::SelectorChecker::checkSelector(CSSSelector* sel, Element* e, PseudoId& dynamicPseudo, bool isSubSelector, bool encounteredLink, RenderStyle* elementStyle, RenderStyle* elementParentStyle) const
2184 {
2185 #if ENABLE(SVG)
2186     // Spec: CSS2 selectors cannot be applied to the (conceptually) cloned DOM tree
2187     // because its contents are not part of the formal document structure.
2188     if (e->isSVGShadowRoot())
2189         return SelectorFailsCompletely;
2190 #endif
2191
2192     // first selector has to match
2193     if (!checkOneSelector(sel, e, dynamicPseudo, isSubSelector, encounteredLink, elementStyle, elementParentStyle))
2194         return SelectorFailsLocally;
2195
2196     // The rest of the selectors has to match
2197     CSSSelector::Relation relation = sel->relation();
2198
2199     // Prepare next sel
2200     sel = sel->tagHistory();
2201     if (!sel)
2202         return SelectorMatches;
2203
2204     if (relation != CSSSelector::SubSelector)
2205         // Bail-out if this selector is irrelevant for the pseudoStyle
2206         if (m_pseudoStyle != NOPSEUDO && m_pseudoStyle != dynamicPseudo)
2207             return SelectorFailsCompletely;
2208
2209     // Check for nested links.
2210     if (m_matchVisitedPseudoClass && !isSubSelector) {
2211         RenderStyle* currentStyle = elementStyle ? elementStyle : e->renderStyle();
2212         if (currentStyle && currentStyle->insideLink() && e->isLink()) {
2213             if (encounteredLink)
2214                 m_matchVisitedPseudoClass = false; // This link is not relevant to the style being resolved, so disable matching.
2215             else
2216                 encounteredLink = true;
2217         }
2218     }
2219
2220     switch (relation) {
2221         case CSSSelector::Descendant:
2222             while (true) {
2223                 ContainerNode* n = e->parentNode();
2224                 if (!n || !n->isElementNode())
2225                     return SelectorFailsCompletely;
2226                 e = static_cast<Element*>(n);
2227                 SelectorMatch match = checkSelector(sel, e, dynamicPseudo, false, encounteredLink);
2228                 if (match != SelectorFailsLocally)
2229                     return match;
2230             }
2231             break;
2232         case CSSSelector::Child:
2233         {
2234             ContainerNode* n = e->parentNode();
2235             if (!n || !n->isElementNode())
2236                 return SelectorFailsCompletely;
2237             e = static_cast<Element*>(n);
2238             return checkSelector(sel, e, dynamicPseudo, false, encounteredLink);
2239         }
2240         case CSSSelector::DirectAdjacent:
2241         {
2242             if (!m_collectRulesOnly && e->parentNode() && e->parentNode()->isElementNode()) {
2243                 RenderStyle* parentStyle = elementStyle ? elementParentStyle : e->parentNode()->renderStyle();
2244                 if (parentStyle)
2245                     parentStyle->setChildrenAffectedByDirectAdjacentRules();
2246             }
2247             Node* n = e->previousSibling();
2248             while (n && !n->isElementNode())
2249                 n = n->previousSibling();
2250             if (!n)
2251                 return SelectorFailsLocally;
2252             e = static_cast<Element*>(n);
2253             m_matchVisitedPseudoClass = false;
2254             return checkSelector(sel, e, dynamicPseudo, false, encounteredLink);
2255         }
2256         case CSSSelector::IndirectAdjacent:
2257             if (!m_collectRulesOnly && e->parentNode() && e->parentNode()->isElementNode()) {
2258                 RenderStyle* parentStyle = elementStyle ? elementParentStyle : e->parentNode()->renderStyle();
2259                 if (parentStyle)
2260                     parentStyle->setChildrenAffectedByForwardPositionalRules();
2261             }
2262             while (true) {
2263                 Node* n = e->previousSibling();
2264                 while (n && !n->isElementNode())
2265                     n = n->previousSibling();
2266                 if (!n)
2267                     return SelectorFailsLocally;
2268                 e = static_cast<Element*>(n);
2269                 m_matchVisitedPseudoClass = false;
2270                 SelectorMatch match = checkSelector(sel, e, dynamicPseudo, false, encounteredLink);
2271                 if (match != SelectorFailsLocally)
2272                     return match;
2273             };
2274             break;
2275         case CSSSelector::SubSelector:
2276             // a selector is invalid if something follows a pseudo-element
2277             // We make an exception for scrollbar pseudo elements and allow a set of pseudo classes (but nothing else)
2278             // to follow the pseudo elements.
2279             if ((elementStyle || m_collectRulesOnly) && dynamicPseudo != NOPSEUDO && dynamicPseudo != SELECTION &&
2280                 !((RenderScrollbar::scrollbarForStyleResolve() || dynamicPseudo == SCROLLBAR_CORNER || dynamicPseudo == RESIZER) && sel->m_match == CSSSelector::PseudoClass))
2281                 return SelectorFailsCompletely;
2282             return checkSelector(sel, e, dynamicPseudo, true, encounteredLink, elementStyle, elementParentStyle);
2283         case CSSSelector::ShadowDescendant:
2284         {
2285             Node* shadowHostNode = e->shadowAncestorNode();
2286             if (shadowHostNode == e || !shadowHostNode->isElementNode())
2287                 return SelectorFailsCompletely;
2288             e = static_cast<Element*>(shadowHostNode);
2289             return checkSelector(sel, e, dynamicPseudo, false, encounteredLink);
2290         }
2291     }
2292
2293     return SelectorFailsCompletely;
2294 }
2295
2296 static void addLocalNameToSet(HashSet<AtomicStringImpl*>* set, const QualifiedName& qName)
2297 {
2298     set->add(qName.localName().impl());
2299 }
2300
2301 static HashSet<AtomicStringImpl*>* createHtmlCaseInsensitiveAttributesSet()
2302 {
2303     // This is the list of attributes in HTML 4.01 with values marked as "[CI]" or case-insensitive
2304     // Mozilla treats all other values as case-sensitive, thus so do we.
2305     HashSet<AtomicStringImpl*>* attrSet = new HashSet<AtomicStringImpl*>;
2306
2307     addLocalNameToSet(attrSet, accept_charsetAttr);
2308     addLocalNameToSet(attrSet, acceptAttr);
2309     addLocalNameToSet(attrSet, alignAttr);
2310     addLocalNameToSet(attrSet, alinkAttr);
2311     addLocalNameToSet(attrSet, axisAttr);
2312     addLocalNameToSet(attrSet, bgcolorAttr);
2313     addLocalNameToSet(attrSet, charsetAttr);
2314     addLocalNameToSet(attrSet, checkedAttr);
2315     addLocalNameToSet(attrSet, clearAttr);
2316     addLocalNameToSet(attrSet, codetypeAttr);
2317     addLocalNameToSet(attrSet, colorAttr);
2318     addLocalNameToSet(attrSet, compactAttr);
2319     addLocalNameToSet(attrSet, declareAttr);
2320     addLocalNameToSet(attrSet, deferAttr);
2321     addLocalNameToSet(attrSet, dirAttr);
2322     addLocalNameToSet(attrSet, disabledAttr);
2323     addLocalNameToSet(attrSet, enctypeAttr);
2324     addLocalNameToSet(attrSet, faceAttr);
2325     addLocalNameToSet(attrSet, frameAttr);
2326     addLocalNameToSet(attrSet, hreflangAttr);
2327     addLocalNameToSet(attrSet, http_equivAttr);
2328     addLocalNameToSet(attrSet, langAttr);
2329     addLocalNameToSet(attrSet, languageAttr);
2330     addLocalNameToSet(attrSet, linkAttr);
2331     addLocalNameToSet(attrSet, mediaAttr);
2332     addLocalNameToSet(attrSet, methodAttr);
2333     addLocalNameToSet(attrSet, multipleAttr);
2334     addLocalNameToSet(attrSet, nohrefAttr);
2335     addLocalNameToSet(attrSet, noresizeAttr);
2336     addLocalNameToSet(attrSet, noshadeAttr);
2337     addLocalNameToSet(attrSet, nowrapAttr);
2338     addLocalNameToSet(attrSet, readonlyAttr);
2339     addLocalNameToSet(attrSet, relAttr);
2340     addLocalNameToSet(attrSet, revAttr);
2341     addLocalNameToSet(attrSet, rulesAttr);
2342     addLocalNameToSet(attrSet, scopeAttr);
2343     addLocalNameToSet(attrSet, scrollingAttr);
2344     addLocalNameToSet(attrSet, selectedAttr);
2345     addLocalNameToSet(attrSet, shapeAttr);
2346     addLocalNameToSet(attrSet, targetAttr);
2347     addLocalNameToSet(attrSet, textAttr);
2348     addLocalNameToSet(attrSet, typeAttr);
2349     addLocalNameToSet(attrSet, valignAttr);
2350     addLocalNameToSet(attrSet, valuetypeAttr);
2351     addLocalNameToSet(attrSet, vlinkAttr);
2352
2353     return attrSet;
2354 }
2355
2356 static bool htmlAttributeHasCaseInsensitiveValue(const QualifiedName& attr)
2357 {
2358     static HashSet<AtomicStringImpl*>* htmlCaseInsensitiveAttributesSet = createHtmlCaseInsensitiveAttributesSet();
2359     bool isPossibleHTMLAttr = !attr.hasPrefix() && (attr.namespaceURI() == nullAtom);
2360     return isPossibleHTMLAttr && htmlCaseInsensitiveAttributesSet->contains(attr.localName().impl());
2361 }
2362
2363 bool CSSStyleSelector::SelectorChecker::checkOneSelector(CSSSelector* sel, Element* e, PseudoId& dynamicPseudo, bool isSubSelector, bool encounteredLink, RenderStyle* elementStyle, RenderStyle* elementParentStyle) const
2364 {
2365     ASSERT(e);
2366     if (!e)
2367         return false;
2368
2369     if (!selectorTagMatches(e, sel))
2370         return false;
2371
2372     if (sel->hasAttribute()) {
2373         if (sel->m_match == CSSSelector::Class)
2374             return e->hasClass() && static_cast<StyledElement*>(e)->classNames().contains(sel->value());
2375
2376         if (sel->m_match == CSSSelector::Id)
2377             return e->hasID() && e->idForStyleResolution() == sel->value();
2378         
2379         const QualifiedName& attr = sel->attribute();
2380
2381         // FIXME: Handle the case were elementStyle is 0.
2382         if (elementStyle && (!e->isStyledElement() || (!static_cast<StyledElement*>(e)->isMappedAttribute(attr) && attr != typeAttr && attr != readonlyAttr))) {
2383             elementStyle->setAffectedByAttributeSelectors(); // Special-case the "type" and "readonly" attributes so input form controls can share style.
2384         }
2385
2386         const AtomicString& value = e->getAttribute(attr);
2387         if (value.isNull())
2388             return false; // attribute is not set
2389
2390         bool caseSensitive = !m_documentIsHTML || !htmlAttributeHasCaseInsensitiveValue(attr);
2391
2392         switch (sel->m_match) {
2393         case CSSSelector::Exact:
2394             if (caseSensitive ? sel->value() != value : !equalIgnoringCase(sel->value(), value))
2395                 return false;
2396             break;
2397         case CSSSelector::List:
2398         {
2399             // Ignore empty selectors or selectors containing spaces
2400             if (sel->value().contains(' ') || sel->value().isEmpty())
2401                 return false;
2402
2403             unsigned startSearchAt = 0;
2404             while (true) {
2405                 size_t foundPos = value.find(sel->value(), startSearchAt, caseSensitive);
2406                 if (foundPos == notFound)
2407                     return false;
2408                 if (foundPos == 0 || value[foundPos - 1] == ' ') {
2409                     unsigned endStr = foundPos + sel->value().length();
2410                     if (endStr == value.length() || value[endStr] == ' ')
2411                         break; // We found a match.
2412                 }
2413                 
2414                 // No match. Keep looking.
2415                 startSearchAt = foundPos + 1;
2416             }
2417             break;
2418         }
2419         case CSSSelector::Contain:
2420             if (!value.contains(sel->value(), caseSensitive) || sel->value().isEmpty())
2421                 return false;
2422             break;
2423         case CSSSelector::Begin:
2424             if (!value.startsWith(sel->value(), caseSensitive) || sel->value().isEmpty())
2425                 return false;
2426             break;
2427         case CSSSelector::End:
2428             if (!value.endsWith(sel->value(), caseSensitive) || sel->value().isEmpty())
2429                 return false;
2430             break;
2431         case CSSSelector::Hyphen:
2432             if (value.length() < sel->value().length())
2433                 return false;
2434             if (!value.startsWith(sel->value(), caseSensitive))
2435                 return false;
2436             // It they start the same, check for exact match or following '-':
2437             if (value.length() != sel->value().length() && value[sel->value().length()] != '-')
2438                 return false;
2439             break;
2440         case CSSSelector::PseudoClass:
2441         case CSSSelector::PseudoElement:
2442         default:
2443             break;
2444         }
2445     }
2446     
2447     if (sel->m_match == CSSSelector::PseudoClass) {
2448         // Handle :not up front.
2449         if (sel->pseudoType() == CSSSelector::PseudoNot) {
2450             ASSERT(sel->selectorList());
2451             for (CSSSelector* subSel = sel->selectorList()->first(); subSel; subSel = subSel->tagHistory()) {
2452                 // :not cannot nest. I don't really know why this is a
2453                 // restriction in CSS3, but it is, so let's honor it.
2454                 // the parser enforces that this never occurs
2455                 ASSERT(subSel->pseudoType() != CSSSelector::PseudoNot);
2456
2457                 if (!checkOneSelector(subSel, e, dynamicPseudo, true, encounteredLink, elementStyle, elementParentStyle))
2458                     return true;
2459             }
2460         } else if (dynamicPseudo != NOPSEUDO && (RenderScrollbar::scrollbarForStyleResolve() || dynamicPseudo == SCROLLBAR_CORNER || dynamicPseudo == RESIZER)) {
2461             // CSS scrollbars match a specific subset of pseudo classes, and they have specialized rules for each
2462             // (since there are no elements involved).
2463             return checkScrollbarPseudoClass(sel, dynamicPseudo);
2464         } else if (dynamicPseudo == SELECTION) {
2465             if (sel->pseudoType() == CSSSelector::PseudoWindowInactive)
2466                 return !m_document->page()->focusController()->isActive();
2467         }
2468         
2469         // Normal element pseudo class checking.
2470         switch (sel->pseudoType()) {
2471             // Pseudo classes:
2472             case CSSSelector::PseudoNot:
2473                 break; // Already handled up above.
2474             case CSSSelector::PseudoEmpty: {
2475                 bool result = true;
2476                 for (Node* n = e->firstChild(); n; n = n->nextSibling()) {
2477                     if (n->isElementNode()) {
2478                         result = false;
2479                         break;
2480                     } else if (n->isTextNode()) {
2481                         Text* textNode = static_cast<Text*>(n);
2482                         if (!textNode->data().isEmpty()) {
2483                             result = false;
2484                             break;
2485                         }
2486                     }
2487                 }
2488                 if (!m_collectRulesOnly) {
2489                     if (elementStyle)
2490                         elementStyle->setEmptyState(result);
2491                     else if (e->renderStyle() && (e->document()->usesSiblingRules() || e->renderStyle()->unique()))
2492                         e->renderStyle()->setEmptyState(result);
2493                 }
2494                 return result;
2495             }
2496             case CSSSelector::PseudoFirstChild: {
2497                 // first-child matches the first child that is an element
2498                 if (e->parentNode() && e->parentNode()->isElementNode()) {
2499                     bool result = false;
2500                     Node* n = e->previousSibling();
2501                     while (n && !n->isElementNode())
2502                         n = n->previousSibling();
2503                     if (!n)
2504                         result = true;
2505                     if (!m_collectRulesOnly) {
2506                         RenderStyle* childStyle = elementStyle ? elementStyle : e->renderStyle();
2507                         RenderStyle* parentStyle = elementStyle ? elementParentStyle : e->parentNode()->renderStyle();
2508                         if (parentStyle)
2509                             parentStyle->setChildrenAffectedByFirstChildRules();
2510                         if (result && childStyle)
2511                             childStyle->setFirstChildState();
2512                     }
2513                     return result;
2514                 }
2515                 break;
2516             }
2517             case CSSSelector::PseudoFirstOfType: {
2518                 // first-of-type matches the first element of its type
2519                 if (e->parentNode() && e->parentNode()->isElementNode()) {
2520                     bool result = false;
2521                     const QualifiedName& type = e->tagQName();
2522                     Node* n = e->previousSibling();
2523                     while (n) {
2524                         if (n->isElementNode() && static_cast<Element*>(n)->hasTagName(type))
2525                             break;
2526                         n = n->previousSibling();
2527                     }
2528                     if (!n)
2529                         result = true;
2530                     if (!m_collectRulesOnly) {
2531                         RenderStyle* parentStyle = elementStyle ? elementParentStyle : e->parentNode()->renderStyle();
2532                         if (parentStyle)
2533                             parentStyle->setChildrenAffectedByForwardPositionalRules();
2534                     }
2535                     return result;
2536                 }
2537                 break;
2538             }
2539             case CSSSelector::PseudoLastChild: {
2540                 // last-child matches the last child that is an element
2541                 if (Element* parentElement = e->parentElement()) {
2542                     bool result = false;
2543                     if (parentElement->isFinishedParsingChildren()) {
2544                         Node* n = e->nextSibling();
2545                         while (n && !n->isElementNode())
2546                             n = n->nextSibling();
2547                         if (!n)
2548                             result = true;
2549                     }
2550                     if (!m_collectRulesOnly) {
2551                         RenderStyle* childStyle = elementStyle ? elementStyle : e->renderStyle();
2552                         RenderStyle* parentStyle = elementStyle ? elementParentStyle : parentElement->renderStyle();
2553                         if (parentStyle)
2554                             parentStyle->setChildrenAffectedByLastChildRules();
2555                         if (result && childStyle)
2556                             childStyle->setLastChildState();
2557                     }
2558                     return result;
2559                 }
2560                 break;
2561             }
2562             case CSSSelector::PseudoLastOfType: {
2563                 // last-of-type matches the last element of its type
2564                 if (Element* parentElement = e->parentElement()) {
2565                     if (!m_collectRulesOnly) {
2566                         RenderStyle* parentStyle = elementStyle ? elementParentStyle : parentElement->renderStyle();
2567                         if (parentStyle)
2568                             parentStyle->setChildrenAffectedByBackwardPositionalRules();
2569                     }
2570                     if (!parentElement->isFinishedParsingChildren())
2571                         return false;
2572                     bool result = false;
2573                     const QualifiedName& type = e->tagQName();
2574                     Node* n = e->nextSibling();
2575                     while (n) {
2576                         if (n->isElementNode() && static_cast<Element*>(n)->hasTagName(type))
2577                             break;
2578                         n = n->nextSibling();
2579                     }
2580                     if (!n)
2581                         result = true;
2582                     return result;
2583                 }
2584                 break;
2585             }
2586             case CSSSelector::PseudoOnlyChild: {
2587                 if (Element* parentElement = e->parentElement()) {
2588                     bool firstChild = false;
2589                     bool lastChild = false;
2590                     
2591                     Node* n = e->previousSibling();
2592                     while (n && !n->isElementNode())
2593                         n = n->previousSibling();
2594                     if (!n)
2595                         firstChild = true;
2596                     if (firstChild && parentElement->isFinishedParsingChildren()) {
2597                         n = e->nextSibling();
2598                         while (n && !n->isElementNode())
2599                             n = n->nextSibling();
2600                         if (!n)
2601                             lastChild = true;
2602                     }
2603                     if (!m_collectRulesOnly) {
2604                         RenderStyle* childStyle = elementStyle ? elementStyle : e->renderStyle();
2605                         RenderStyle* parentStyle = elementStyle ? elementParentStyle : parentElement->renderStyle();
2606                         if (parentStyle) {
2607                             parentStyle->setChildrenAffectedByFirstChildRules();
2608                             parentStyle->setChildrenAffectedByLastChildRules();
2609                         }
2610                         if (firstChild && childStyle)
2611                             childStyle->setFirstChildState();
2612                         if (lastChild && childStyle)
2613                             childStyle->setLastChildState();
2614                     }
2615                     return firstChild && lastChild;
2616                 }
2617                 break;
2618             }
2619             case CSSSelector::PseudoOnlyOfType: {
2620                 // FIXME: This selector is very slow.
2621                 if (Element* parentElement = e->parentElement()) {
2622                     if (!m_collectRulesOnly) {
2623                         RenderStyle* parentStyle = elementStyle ? elementParentStyle : parentElement->renderStyle();
2624                         if (parentStyle) {
2625                             parentStyle->setChildrenAffectedByForwardPositionalRules();
2626                             parentStyle->setChildrenAffectedByBackwardPositionalRules();
2627                         }
2628                     }
2629                     if (!parentElement->isFinishedParsingChildren())
2630                         return false;
2631                     bool firstChild = false;
2632                     bool lastChild = false;
2633                     const QualifiedName& type = e->tagQName();
2634                     Node* n = e->previousSibling();
2635                     while (n) {
2636                         if (n->isElementNode() && static_cast<Element*>(n)->hasTagName(type))
2637                             break;
2638                         n = n->previousSibling();
2639                     }
2640                     if (!n)
2641                         firstChild = true;
2642                     if (firstChild) {
2643                         n = e->nextSibling();
2644                         while (n) {
2645                             if (n->isElementNode() && static_cast<Element*>(n)->hasTagName(type))
2646                                 break;
2647                             n = n->nextSibling();
2648                         }
2649                         if (!n)
2650                             lastChild = true;
2651                     }
2652                     return firstChild && lastChild;
2653                 }
2654                 break;
2655             }
2656             case CSSSelector::PseudoNthChild: {
2657                 if (!sel->parseNth())
2658                     break;
2659                 if (Element* parentElement = e->parentElement()) {
2660                     int count = 1;
2661                     Node* n = e->previousSibling();
2662                     while (n) {
2663                         if (n->isElementNode()) {
2664                             RenderStyle* s = n->renderStyle();
2665                             unsigned index = s ? s->childIndex() : 0;
2666                             if (index) {
2667                                 count += index;
2668                                 break;
2669                             }
2670                             count++;
2671                         }
2672                         n = n->previousSibling();
2673                     }
2674                     
2675                     if (!m_collectRulesOnly) {
2676                         RenderStyle* childStyle = elementStyle ? elementStyle : e->renderStyle();
2677                         RenderStyle* parentStyle = elementStyle ? elementParentStyle : parentElement->renderStyle();
2678                         if (childStyle)
2679                             childStyle->setChildIndex(count);
2680                         if (parentStyle)
2681                             parentStyle->setChildrenAffectedByForwardPositionalRules();
2682                     }
2683                     
2684                     if (sel->matchNth(count))
2685                         return true;
2686                 }
2687                 break;
2688             }
2689             case CSSSelector::PseudoNthOfType: {
2690                 if (!sel->parseNth())
2691                     break;
2692                 if (Element* parentElement = e->parentElement()) {
2693                     int count = 1;
2694                     const QualifiedName& type = e->tagQName();
2695                     Node* n = e->previousSibling();
2696                     while (n) {
2697                         if (n->isElementNode() && static_cast<Element*>(n)->hasTagName(type))
2698                             count++;
2699                         n = n->previousSibling();
2700                     }
2701                     
2702                     if (!m_collectRulesOnly) {
2703                         RenderStyle* parentStyle = elementStyle ? elementParentStyle : parentElement->renderStyle();
2704                         if (parentStyle)
2705                             parentStyle->setChildrenAffectedByForwardPositionalRules();
2706                     }
2707
2708                     if (sel->matchNth(count))
2709                         return true;
2710                 }
2711                 break;
2712             }
2713             case CSSSelector::PseudoNthLastChild: {
2714                 if (!sel->parseNth())
2715                     break;
2716                 if (Element* parentElement = e->parentElement()) {
2717                     if (!m_collectRulesOnly) {
2718                         RenderStyle* parentStyle = elementStyle ? elementParentStyle : parentElement->renderStyle();
2719                         if (parentStyle)
2720                             parentStyle->setChildrenAffectedByBackwardPositionalRules();
2721                     }
2722                     if (!parentElement->isFinishedParsingChildren())
2723                         return false;
2724                     int count = 1;
2725                     Node* n = e->nextSibling();
2726                     while (n) {
2727                         if (n->isElementNode())
2728                             count++;
2729                         n = n->nextSibling();
2730                     }
2731                     if (sel->matchNth(count))
2732                         return true;
2733                 }
2734                 break;
2735             }
2736             case CSSSelector::PseudoNthLastOfType: {
2737                 if (!sel->parseNth())
2738                     break;
2739                 if (Element* parentElement = e->parentElement()) {
2740                     if (!m_collectRulesOnly) {
2741                         RenderStyle* parentStyle = elementStyle ? elementParentStyle : parentElement->renderStyle();
2742                         if (parentStyle)
2743                             parentStyle->setChildrenAffectedByBackwardPositionalRules();
2744                     }
2745                     if (!parentElement->isFinishedParsingChildren())
2746                         return false;
2747                     int count = 1;
2748                     const QualifiedName& type = e->tagQName();
2749                     Node* n = e->nextSibling();
2750                     while (n) {
2751                         if (n->isElementNode() && static_cast<Element*>(n)->hasTagName(type))
2752                             count++;
2753                         n = n->nextSibling();
2754                     }
2755                     if (sel->matchNth(count))
2756                         return true;
2757                 }
2758                 break;
2759             }
2760             case CSSSelector::PseudoTarget:
2761                 if (e == e->document()->cssTarget())
2762                     return true;
2763                 break;
2764             case CSSSelector::PseudoAny:
2765                 for (CSSSelector* selector = sel->selectorList()->first(); selector; selector = CSSSelectorList::next(selector)) {
2766                     if (checkSelector(selector, e, dynamicPseudo, true, encounteredLink, elementStyle, elementParentStyle) == SelectorMatches)
2767                         return true;
2768                 }
2769                 break;
2770             case CSSSelector::PseudoAnyLink:
2771                 if (e && e->isLink())
2772                     return true;
2773                 break;
2774             case CSSSelector::PseudoAutofill: {
2775                 if (!e || !e->isFormControlElement())
2776                     break;
2777                 if (HTMLInputElement* inputElement = e->toInputElement())
2778                     return inputElement->isAutofilled();
2779                 break;
2780             }
2781             case CSSSelector::PseudoLink:
2782                 if (e && e->isLink())
2783                     return !m_matchVisitedPseudoClass;
2784                 break;
2785             case CSSSelector::PseudoVisited:
2786                 if (e && e->isLink())
2787                     return m_matchVisitedPseudoClass;
2788                 break;
2789             case CSSSelector::PseudoDrag: {
2790                 if (elementStyle)
2791                     elementStyle->setAffectedByDragRules(true);
2792                 else if (e->renderStyle())
2793                     e->renderStyle()->setAffectedByDragRules(true);
2794                 if (e->renderer() && e->renderer()->isDragging())
2795                     return true;
2796                 break;
2797             }
2798             case CSSSelector::PseudoFocus:
2799                 if (e && e->focused() && e->document()->frame() && e->document()->frame()->selection()->isFocusedAndActive())
2800                     return true;
2801                 break;
2802             case CSSSelector::PseudoHover: {
2803                 // If we're in quirks mode, then hover should never match anchors with no
2804                 // href and *:hover should not match anything.  This is important for sites like wsj.com.
2805                 if (m_strictParsing || isSubSelector || (sel->hasTag() && !e->hasTagName(aTag)) || e->isLink()) {
2806                     if (elementStyle)
2807                         elementStyle->setAffectedByHoverRules(true);
2808                     else if (e->renderStyle())
2809                         e->renderStyle()->setAffectedByHoverRules(true);
2810                     if (e->hovered())
2811                         return true;
2812                 }
2813                 break;
2814             }
2815             case CSSSelector::PseudoActive:
2816                 // If we're in quirks mode, then :active should never match anchors with no
2817                 // href and *:active should not match anything. 
2818                 if (m_strictParsing || isSubSelector || (sel->hasTag() && !e->hasTagName(aTag)) || e->isLink()) {
2819                     if (elementStyle)
2820                         elementStyle->setAffectedByActiveRules(true);
2821                     else if (e->renderStyle())
2822                         e->renderStyle()->setAffectedByActiveRules(true);
2823                     if (e->active())
2824                         return true;
2825                 }
2826                 break;
2827             case CSSSelector::PseudoEnabled:
2828                 if (e && e->isFormControlElement())
2829                     return e->isEnabledFormControl();
2830                 break;
2831             case CSSSelector::PseudoFullPageMedia:
2832                 return e && e->document() && e->document()->isMediaDocument();
2833                 break;
2834             case CSSSelector::PseudoDefault:
2835                 return e && e->isDefaultButtonForForm();
2836             case CSSSelector::PseudoDisabled:
2837                 if (e && e->isFormControlElement())
2838                     return !e->isEnabledFormControl();
2839                 break;
2840             case CSSSelector::PseudoReadOnly: {
2841                 if (!e || !e->isFormControlElement())
2842                     return false;
2843                 return e->isTextFormControl() && e->isReadOnlyFormControl();
2844             }
2845             case CSSSelector::PseudoReadWrite: {
2846                 if (!e || !e->isFormControlElement())
2847                     return false;
2848                 return e->isTextFormControl() && !e->isReadOnlyFormControl();
2849             }
2850             case CSSSelector::PseudoOptional:
2851                 return e && e->isOptionalFormControl();
2852             case CSSSelector::PseudoRequired:
2853                 return e && e->isRequiredFormControl();
2854             case CSSSelector::PseudoValid: {
2855                 if (!e)
2856                     return false;
2857                 e->document()->setContainsValidityStyleRules();
2858                 return e->willValidate() && e->isValidFormControlElement();
2859             } case CSSSelector::PseudoInvalid: {
2860                 if (!e)
2861                     return false;
2862                 e->document()->setContainsValidityStyleRules();
2863                 return (e->willValidate() && !e->isValidFormControlElement()) || e->hasUnacceptableValue();
2864             } case CSSSelector::PseudoChecked: {
2865                 if (!e || !e->isFormControlElement())
2866                     break;
2867                 // Even though WinIE allows checked and indeterminate to co-exist, the CSS selector spec says that
2868                 // you can't be both checked and indeterminate.  We will behave like WinIE behind the scenes and just
2869                 // obey the CSS spec here in the test for matching the pseudo.
2870                 HTMLInputElement* inputElement = e->toInputElement();
2871                 if (inputElement && inputElement->isChecked() && !inputElement->isIndeterminate())
2872                     return true;
2873                 break;
2874             }
2875             case CSSSelector::PseudoIndeterminate: {
2876                 if (!e || !e->isFormControlElement())
2877                     break;
2878                 HTMLInputElement* inputElement = e->toInputElement();
2879                 if (inputElement && inputElement->isIndeterminate())
2880                     return true;
2881                 break;
2882             }
2883             case CSSSelector::PseudoRoot:
2884                 if (e == e->document()->documentElement())
2885                     return true;
2886                 break;
2887             case CSSSelector::PseudoLang: {
2888                 AtomicString value = e->computeInheritedLanguage();
2889                 const AtomicString& argument = sel->argument();
2890                 if (value.isEmpty() || !value.startsWith(argument, false))
2891                     break;
2892                 if (value.length() != argument.length() && value[argument.length()] != '-')
2893                     break;
2894                 return true;
2895             }
2896 #if ENABLE(FULLSCREEN_API)
2897             case CSSSelector::PseudoFullScreen:
2898                 // While a Document is in the fullscreen state, and the document's current fullscreen 
2899                 // element is an element in the document, the 'full-screen' pseudoclass applies to 
2900                 // that element. Also, an <iframe>, <object> or <embed> element whose child browsing 
2901                 // context's Document is in the fullscreen state has the 'full-screen' pseudoclass applied.
2902                 if (e->isFrameElementBase() && static_cast<HTMLFrameElementBase*>(e)->containsFullScreenElement())
2903                     return true;
2904                 if (!e->document()->webkitIsFullScreen())
2905                     return false;
2906                 return e == e->document()->webkitCurrentFullScreenElement();
2907             case CSSSelector::PseudoAnimatingFullScreenTransition:
2908                 if (e != e->document()->webkitCurrentFullScreenElement())
2909                     return false;
2910                 return e->document()->isAnimatingFullScreen();
2911             case CSSSelector::PseudoFullScreenAncestor:
2912                 return e->containsFullScreenElement();
2913             case CSSSelector::PseudoFullScreenDocument:
2914                 // While a Document is in the fullscreen state, the 'full-screen-document' pseudoclass applies 
2915                 // to all elements of that Document.
2916                 if (!e->document()->webkitIsFullScreen())
2917                     return false;
2918                 return true;
2919 #endif
2920             case CSSSelector::PseudoInRange:
2921                 if (!e)
2922                     return false;
2923                 e->document()->setContainsValidityStyleRules();
2924                 return e->isInRange();
2925             case CSSSelector::PseudoOutOfRange:
2926                 if (!e)
2927                     return false;
2928                 e->document()->setContainsValidityStyleRules();
2929                 return e->isOutOfRange();
2930             case CSSSelector::PseudoUnknown:
2931             case CSSSelector::PseudoNotParsed:
2932             default:
2933                 ASSERT_NOT_REACHED();
2934                 break;
2935         }
2936         return false;
2937     }
2938     if (sel->m_match == CSSSelector::PseudoElement) {
2939         if (!elementStyle && !m_collectRulesOnly)
2940             return false;
2941
2942         if (sel->isUnknownPseudoElement()) {
2943             m_hasUnknownPseudoElements = true;
2944             return e->shadowPseudoId() == sel->value();
2945         }
2946
2947         PseudoId pseudoId = CSSSelector::pseudoId(sel->pseudoType());
2948         if (pseudoId == FIRST_LETTER) {
2949             if (Document* document = e->document())
2950                 document->setUsesFirstLetterRules(true);
2951         }
2952         if (pseudoId != NOPSEUDO)
2953             dynamicPseudo = pseudoId;
2954     }
2955     // ### add the rest of the checks...
2956     return true;
2957 }
2958
2959 bool CSSStyleSelector::SelectorChecker::checkScrollbarPseudoClass(CSSSelector* sel, PseudoId&) const
2960 {
2961     RenderScrollbar* scrollbar = RenderScrollbar::scrollbarForStyleResolve();
2962     ScrollbarPart part = RenderScrollbar::partForStyleResolve();
2963
2964     // FIXME: This is a temporary hack for resizers and scrollbar corners.  Eventually :window-inactive should become a real
2965     // pseudo class and just apply to everything.
2966     if (sel->pseudoType() == CSSSelector::PseudoWindowInactive)
2967         return !m_document->page()->focusController()->isActive();
2968     
2969     if (!scrollbar)
2970         return false;
2971         
2972     ASSERT(sel->m_match == CSSSelector::PseudoClass);
2973     switch (sel->pseudoType()) {
2974         case CSSSelector::PseudoEnabled:
2975             return scrollbar->enabled();
2976         case CSSSelector::PseudoDisabled:
2977             return !scrollbar->enabled();
2978         case CSSSelector::PseudoHover: {
2979             ScrollbarPart hoveredPart = scrollbar->hoveredPart();
2980             if (part == ScrollbarBGPart)
2981                 return hoveredPart != NoPart;
2982             if (part == TrackBGPart)
2983                 return hoveredPart == BackTrackPart || hoveredPart == ForwardTrackPart || hoveredPart == ThumbPart;
2984             return part == hoveredPart;
2985         }
2986         case CSSSelector::PseudoActive: {
2987             ScrollbarPart pressedPart = scrollbar->pressedPart();
2988             if (part == ScrollbarBGPart)
2989                 return pressedPart != NoPart;
2990             if (part == TrackBGPart)
2991                 return pressedPart == BackTrackPart || pressedPart == ForwardTrackPart || pressedPart == ThumbPart;
2992             return part == pressedPart;
2993         }
2994         case CSSSelector::PseudoHorizontal:
2995             return scrollbar->orientation() == HorizontalScrollbar;
2996         case CSSSelector::PseudoVertical:
2997             return scrollbar->orientation() == VerticalScrollbar;
2998         case CSSSelector::PseudoDecrement:
2999             return part == BackButtonStartPart || part == BackButtonEndPart || part == BackTrackPart;
3000         case CSSSelector::PseudoIncrement:
3001             return part == ForwardButtonStartPart || part == ForwardButtonEndPart || part == ForwardTrackPart;
3002         case CSSSelector::PseudoStart:
3003             return part == BackButtonStartPart || part == ForwardButtonStartPart || part == BackTrackPart;
3004         case CSSSelector::PseudoEnd:
3005             return part == BackButtonEndPart || part == ForwardButtonEndPart || part == ForwardTrackPart;
3006         case CSSSelector::PseudoDoubleButton: {
3007             ScrollbarButtonsPlacement buttonsPlacement = scrollbar->theme()->buttonsPlacement();
3008             if (part == BackButtonStartPart || part == ForwardButtonStartPart || part == BackTrackPart)
3009                 return buttonsPlacement == ScrollbarButtonsDoubleStart || buttonsPlacement == ScrollbarButtonsDoubleBoth;
3010             if (part == BackButtonEndPart || part == ForwardButtonEndPart || part == ForwardTrackPart)
3011                 return buttonsPlacement == ScrollbarButtonsDoubleEnd || buttonsPlacement == ScrollbarButtonsDoubleBoth;
3012             return false;
3013         } 
3014         case CSSSelector::PseudoSingleButton: {
3015             ScrollbarButtonsPlacement buttonsPlacement = scrollbar->theme()->buttonsPlacement();
3016             if (part == BackButtonStartPart || part == ForwardButtonEndPart || part == BackTrackPart || part == ForwardTrackPart)
3017                 return buttonsPlacement == ScrollbarButtonsSingle;
3018             return false;
3019         }
3020         case CSSSelector::PseudoNoButton: {
3021             ScrollbarButtonsPlacement buttonsPlacement = scrollbar->theme()->buttonsPlacement();
3022             if (part == BackTrackPart)
3023                 return buttonsPlacement == ScrollbarButtonsNone || buttonsPlacement == ScrollbarButtonsDoubleEnd;
3024             if (part == ForwardTrackPart)
3025                 return buttonsPlacement == ScrollbarButtonsNone || buttonsPlacement == ScrollbarButtonsDoubleStart;
3026             return false;
3027         }
3028         case CSSSelector::PseudoCornerPresent:
3029             return scrollbar->scrollableArea()->isScrollCornerVisible();
3030         default:
3031             return false;
3032     }
3033 }
3034
3035 // -----------------------------------------------------------------
3036
3037 static inline bool isSelectorMatchingHTMLBasedOnRuleHash(const CSSSelector* selector)
3038 {
3039     const AtomicString& selectorNamespace = selector->tag().namespaceURI();
3040     if (selectorNamespace != starAtom && selectorNamespace != xhtmlNamespaceURI)
3041         return false;
3042     if (selector->m_match == CSSSelector::None)
3043         return true;
3044     if (selector->m_match != CSSSelector::Id && selector->m_match != CSSSelector::Class)
3045         return false;
3046     return selector->tag() == starAtom;
3047 }
3048
3049 RuleData::RuleData(CSSStyleRule* rule, CSSSelector* selector, unsigned position)
3050     : m_rule(rule)
3051     , m_selector(selector)
3052     , m_specificity(selector->specificity())
3053     , m_position(position)
3054     , m_hasFastCheckableSelector(isFastCheckableSelector(selector))
3055     , m_hasMultipartSelector(selector->tagHistory())
3056     , m_hasTopSelectorMatchingHTMLBasedOnRuleHash(isSelectorMatchingHTMLBasedOnRuleHash(selector))
3057 {
3058     collectDescendantSelectorIdentifierHashes();
3059 }
3060
3061 inline void RuleData::collectIdentifierHashes(const CSSSelector* selector, unsigned& identifierCount)
3062 {
3063     if ((selector->m_match == CSSSelector::Id || selector->m_match == CSSSelector::Class) && !selector->value().isEmpty())
3064         m_descendantSelectorIdentifierHashes[identifierCount++] = selector->value().impl()->existingHash();
3065     if (identifierCount == maximumIdentifierCount)
3066         return;
3067     const AtomicString& localName = selector->tag().localName();
3068     if (localName != starAtom)
3069         m_descendantSelectorIdentifierHashes[identifierCount++] = localName.impl()->existingHash();
3070 }
3071
3072 inline void RuleData::collectDescendantSelectorIdentifierHashes()
3073 {
3074     unsigned identifierCount = 0;
3075     CSSSelector::Relation relation = m_selector->relation();
3076     
3077     // Skip the topmost selector. It is handled quickly by the rule hashes.    
3078     bool skipOverSubselectors = true;
3079     for (const CSSSelector* selector = m_selector->tagHistory(); selector; selector = selector->tagHistory()) {
3080         // Only collect identifiers that match ancestors.
3081         switch (relation) {
3082         case CSSSelector::SubSelector:
3083             if (!skipOverSubselectors)
3084                 collectIdentifierHashes(selector, identifierCount);
3085             break;
3086         case CSSSelector::DirectAdjacent:
3087         case CSSSelector::IndirectAdjacent:
3088         case CSSSelector::ShadowDescendant:
3089             skipOverSubselectors = true;
3090             break;
3091         case CSSSelector::Descendant:
3092         case CSSSelector::Child:
3093             skipOverSubselectors = false;
3094             collectIdentifierHashes(selector, identifierCount);
3095             break;
3096         }
3097         if (identifierCount == maximumIdentifierCount)
3098             return;
3099         relation = selector->relation();
3100     }
3101     m_descendantSelectorIdentifierHashes[identifierCount] = 0;
3102 }
3103
3104 RuleSet::RuleSet()
3105     : m_ruleCount(0)
3106     , m_autoShrinkToFitEnabled(true)
3107 {
3108 }
3109
3110 RuleSet::~RuleSet()
3111
3112     deleteAllValues(m_idRules);
3113     deleteAllValues(m_classRules);
3114     deleteAllValues(m_pseudoRules);
3115     deleteAllValues(m_tagRules);
3116 }
3117
3118
3119 void RuleSet::addToRuleSet(AtomicStringImpl* key, AtomRuleMap& map,
3120                               CSSStyleRule* rule, CSSSelector* sel)
3121 {
3122     if (!key) return;
3123     Vector<RuleData>* rules = map.get(key);
3124     if (!rules) {
3125         rules = new Vector<RuleData>;
3126         map.set(key, rules);
3127     }
3128     rules->append(RuleData(rule, sel, m_ruleCount++));
3129 }
3130
3131 void RuleSet::addRule(CSSStyleRule* rule, CSSSelector* sel)
3132 {
3133     if (sel->m_match == CSSSelector::Id) {
3134         addToRuleSet(sel->value().impl(), m_idRules, rule, sel);
3135         return;
3136     }
3137     if (sel->m_match == CSSSelector::Class) {
3138         addToRuleSet(sel->value().impl(), m_classRules, rule, sel);
3139         return;
3140     }
3141      
3142     if (sel->isUnknownPseudoElement()) {
3143         addToRuleSet(sel->value().impl(), m_pseudoRules, rule, sel);
3144         return;
3145     }
3146
3147     const AtomicString& localName = sel->tag().localName();
3148     if (localName != starAtom) {
3149         addToRuleSet(localName.impl(), m_tagRules, rule, sel);
3150         return;
3151     }
3152
3153     m_universalRules.append(RuleData(rule, sel, m_ruleCount++));
3154 }
3155
3156 void RuleSet::addPageRule(CSSStyleRule* rule, CSSSelector* sel)
3157 {
3158     m_pageRules.append(RuleData(rule, sel, m_pageRules.size()));
3159 }
3160
3161 void RuleSet::addRulesFromSheet(CSSStyleSheet* sheet, const MediaQueryEvaluator& medium, CSSStyleSelector* styleSelector)
3162 {
3163     if (!sheet)
3164         return;
3165
3166     // No media implies "all", but if a media list exists it must
3167     // contain our current medium
3168     if (sheet->media() && !medium.eval(sheet->media(), styleSelector))
3169         return; // the style sheet doesn't apply
3170
3171     int len = sheet->length();
3172
3173     for (int i = 0; i < len; i++) {
3174         StyleBase* item = sheet->item(i);
3175         if (item->isStyleRule())
3176             addStyleRule(static_cast<CSSStyleRule*>(item));
3177         else if (item->isImportRule()) {
3178             CSSImportRule* import = static_cast<CSSImportRule*>(item);
3179             if (!import->media() || medium.eval(import->media(), styleSelector))
3180                 addRulesFromSheet(import->styleSheet(), medium, styleSelector);
3181         }
3182         else if (item->isMediaRule()) {
3183             CSSMediaRule* r = static_cast<CSSMediaRule*>(item);
3184             CSSRuleList* rules = r->cssRules();
3185
3186             if ((!r->media() || medium.eval(r->media(), styleSelector)) && rules) {
3187                 // Traverse child elements of the @media rule.
3188                 for (unsigned j = 0; j < rules->length(); j++) {
3189                     CSSRule *childItem = rules->item(j);
3190                     if (childItem->isStyleRule()) {
3191                         // It is a StyleRule, so append it to our list
3192                         addStyleRule(static_cast<CSSStyleRule*>(childItem));
3193                     } else if (childItem->isFontFaceRule() && styleSelector) {
3194                         // Add this font face to our set.
3195                         const CSSFontFaceRule* fontFaceRule = static_cast<CSSFontFaceRule*>(childItem);
3196                         styleSelector->fontSelector()->addFontFaceRule(fontFaceRule);
3197                     } else if (childItem->isKeyframesRule() && styleSelector) {
3198                         // Add this keyframe rule to our set.
3199                         styleSelector->addKeyframeStyle(static_cast<WebKitCSSKeyframesRule*>(childItem));
3200                     }
3201                 }   // for rules
3202             }   // if rules
3203         } else if (item->isFontFaceRule() && styleSelector) {
3204             // Add this font face to our set.
3205             const CSSFontFaceRule* fontFaceRule = static_cast<CSSFontFaceRule*>(item);
3206             styleSelector->fontSelector()->addFontFaceRule(fontFaceRule);
3207         } else if (item->isKeyframesRule())
3208             styleSelector->addKeyframeStyle(static_cast<WebKitCSSKeyframesRule*>(item));
3209     }
3210     if (m_autoShrinkToFitEnabled)
3211         shrinkToFit();
3212 }
3213
3214 void RuleSet::addStyleRule(CSSStyleRule* rule)
3215 {
3216     if (rule->isPageRule()) {
3217         CSSPageRule* pageRule = static_cast<CSSPageRule*>(rule);
3218         addPageRule(pageRule, pageRule->selectorList().first());
3219     } else {
3220         for (CSSSelector* s = rule->selectorList().first(); s; s = CSSSelectorList::next(s))
3221             addRule(rule, s);
3222     }
3223 }
3224     
3225 static inline void collectFeaturesFromSelector(CSSStyleSelector::Features& features, const CSSSelector* selector)
3226 {
3227     if (selector->m_match == CSSSelector::Id && !selector->value().isEmpty())
3228         features.idsInRules.add(selector->value().impl());
3229     if (selector->hasAttribute()) {
3230         switch (selector->m_match) {
3231         case CSSSelector::Exact:
3232         case CSSSelector::Set:
3233         case CSSSelector::List:
3234         case CSSSelector::Hyphen:
3235         case CSSSelector::Contain:
3236         case CSSSelector::Begin:
3237         case CSSSelector::End:
3238             features.attrsInRules.add(selector->attribute().localName().impl());
3239             break;
3240         default:
3241             break;
3242         }
3243     }
3244     switch (selector->pseudoType()) {
3245     case CSSSelector::PseudoFirstLine:
3246         features.usesFirstLineRules = true;
3247         break;
3248     case CSSSelector::PseudoBefore:
3249     case CSSSelector::PseudoAfter:
3250         features.usesBeforeAfterRules = true;
3251         break;
3252     case CSSSelector::PseudoLink:
3253     case CSSSelector::PseudoVisited:
3254         features.usesLinkRules = true;
3255         break;
3256     default:
3257         break;
3258     }
3259 }
3260
3261 static void collectFeaturesFromList(CSSStyleSelector::Features& features, const Vector<RuleData>& rules)
3262 {
3263     unsigned size = rules.size();
3264     for (unsigned i = 0; i < size; ++i) {
3265         const RuleData& ruleData = rules[i];
3266         bool foundSiblingSelector = false;
3267         for (CSSSelector* selector = ruleData.selector(); selector; selector = selector->tagHistory()) {
3268             collectFeaturesFromSelector(features, selector);
3269
3270             if (CSSSelectorList* selectorList = selector->selectorList()) {
3271                 for (CSSSelector* subSelector = selectorList->first(); subSelector; subSelector = CSSSelectorList::next(subSelector)) {
3272                     if (selector->isSiblingSelector())
3273                         foundSiblingSelector = true;
3274                     collectFeaturesFromSelector(features, subSelector);
3275                 }
3276             } else if (selector->isSiblingSelector())
3277                 foundSiblingSelector = true;
3278         }
3279         if (foundSiblingSelector) {
3280             if (!features.siblingRules)
3281                 features.siblingRules = adoptPtr(new RuleSet);
3282             features.siblingRules->addRule(ruleData.rule(), ruleData.selector());   
3283         }
3284     }
3285 }
3286
3287 void RuleSet::collectFeatures(CSSStyleSelector::Features& features) const
3288 {
3289     AtomRuleMap::const_iterator end = m_idRules.end();
3290     for (AtomRuleMap::const_iterator it = m_idRules.begin(); it != end; ++it)
3291         collectFeaturesFromList(features, *it->second);
3292     end = m_classRules.end();
3293     for (AtomRuleMap::const_iterator it = m_classRules.begin(); it != end; ++it)
3294         collectFeaturesFromList(features, *it->second);
3295     end = m_tagRules.end();
3296     for (AtomRuleMap::const_iterator it = m_tagRules.begin(); it != end; ++it)
3297         collectFeaturesFromList(features, *it->second);
3298     end = m_pseudoRules.end();
3299     for (AtomRuleMap::const_iterator it = m_pseudoRules.begin(); it != end; ++it)
3300         collectFeaturesFromList(features, *it->second);
3301     collectFeaturesFromList(features, m_universalRules);
3302 }
3303     
3304 static inline void shrinkMapVectorsToFit(RuleSet::AtomRuleMap& map)
3305 {
3306     RuleSet::AtomRuleMap::iterator end = map.end();
3307     for (RuleSet::AtomRuleMap::iterator it = map.begin(); it != end; ++it)
3308         it->second->shrinkToFit();
3309 }
3310     
3311 void RuleSet::shrinkToFit()
3312 {
3313     shrinkMapVectorsToFit(m_idRules);
3314     shrinkMapVectorsToFit(m_classRules);
3315     shrinkMapVectorsToFit(m_tagRules);
3316     shrinkMapVectorsToFit(m_pseudoRules);
3317     m_universalRules.shrinkToFit();
3318     m_pageRules.shrinkToFit();
3319 }
3320
3321 // -------------------------------------------------------------------------------------
3322 // this is mostly boring stuff on how to apply a certain rule to the renderstyle...
3323
3324 static Length convertToLength(CSSPrimitiveValue* primitiveValue, RenderStyle* style, RenderStyle* rootStyle, bool toFloat, double multiplier = 1, bool *ok = 0)
3325 {
3326     // This function is tolerant of a null style value. The only place style is used is in
3327     // length measurements, like 'ems' and 'px'. And in those cases style is only used
3328     // when the units are EMS or EXS. So we will just fail in those cases.
3329     Length l;
3330     if (!primitiveValue) {
3331         if (ok)
3332             *ok = false;
3333     } else {
3334         int type = primitiveValue->primitiveType();
3335         
3336         if (!style && (type == CSSPrimitiveValue::CSS_EMS || type == CSSPrimitiveValue::CSS_EXS || type == CSSPrimitiveValue::CSS_REMS)) {
3337             if (ok)
3338                 *ok = false;
3339         } else if (CSSPrimitiveValue::isUnitTypeLength(type)) {
3340             if (toFloat)
3341                 l = Length(primitiveValue->computeLengthDouble(style, rootStyle, multiplier), Fixed);
3342             else
3343                 l = Length(primitiveValue->computeLengthIntForLength(style, rootStyle, multiplier), Fixed);
3344         }
3345         else if (type == CSSPrimitiveValue::CSS_PERCENTAGE)
3346             l = Length(primitiveValue->getDoubleValue(), Percent);
3347         else if (type == CSSPrimitiveValue::CSS_NUMBER)
3348             l = Length(primitiveValue->getDoubleValue() * 100.0, Percent);
3349         else if (ok)
3350             *ok = false;
3351     }
3352     return l;
3353 }
3354     
3355 static Length convertToIntLength(CSSPrimitiveValue* primitiveValue, RenderStyle* style, RenderStyle* rootStyle, double multiplier = 1, bool *ok = 0)
3356 {
3357     return convertToLength(primitiveValue, style, rootStyle, false, multiplier, ok);
3358 }
3359
3360 static Length convertToFloatLength(CSSPrimitiveValue* primitiveValue, RenderStyle* style, RenderStyle* rootStyle, double multiplier = 1, bool *ok = 0)
3361 {
3362     return convertToLength(primitiveValue, style, rootStyle, true, multiplier, ok);
3363 }
3364
3365 template <bool applyFirst>
3366 void CSSStyleSelector::applyDeclarations(bool isImportant, int startIndex, int endIndex)
3367 {
3368     if (startIndex == -1)
3369         return;
3370
3371     for (int i = startIndex; i <= endIndex; i++) {
3372         CSSMutableStyleDeclaration* decl = m_matchedDecls[i];
3373         CSSMutableStyleDeclaration::const_iterator end = decl->end();
3374         for (CSSMutableStyleDeclaration::const_iterator it = decl->begin(); it != end; ++it) {
3375             const CSSProperty& current = *it;
3376             if (isImportant == current.isImportant()) {
3377                 int property = current.id();
3378
3379                 if (applyFirst) {
3380                     COMPILE_ASSERT(firstCSSProperty == CSSPropertyColor, CSS_color_is_first_property);
3381                     COMPILE_ASSERT(CSSPropertyZoom == CSSPropertyColor + 14, CSS_zoom_is_end_of_first_prop_range);
3382                     COMPILE_ASSERT(CSSPropertyLineHeight == CSSPropertyZoom + 1, CSS_line_height_is_after_zoom);
3383
3384                     // give special priority to font-xxx, color properties, etc
3385                     if (property <= CSSPropertyLineHeight) {
3386                         // we apply line-height later
3387                         if (property == CSSPropertyLineHeight)
3388                             m_lineHeightValue = current.value(); 
3389                         else 
3390                             applyProperty(current.id(), current.value());
3391                     }
3392                 } else {
3393                     if (property > CSSPropertyLineHeight)
3394                         applyProperty(current.id(), current.value());
3395                 }
3396             }
3397         }
3398     }
3399 }
3400
3401 void CSSStyleSelector::matchPageRules(RuleSet* rules, bool isLeftPage, bool isFirstPage, const String& pageName)
3402 {
3403     m_matchedRules.clear();
3404
3405     if (!rules)
3406         return;
3407
3408     matchPageRulesForList(rules->getPageRules(), isLeftPage, isFirstPage, pageName);
3409
3410     // If we didn't match any rules, we're done.
3411     if (m_matchedRules.isEmpty())
3412         return;
3413
3414     // Sort the set of matched rules.
3415     sortMatchedRules();
3416
3417     // Now transfer the set of matched rules over to our list of decls.
3418     for (unsigned i = 0; i < m_matchedRules.size(); i++)
3419         addMatchedDeclaration(m_matchedRules[i]->rule()->declaration());
3420 }
3421
3422 void CSSStyleSelector::matchPageRulesForList(const Vector<RuleData>* rules, bool isLeftPage, bool isFirstPage, const String& pageName)
3423 {
3424     if (!rules)
3425         return;
3426
3427     unsigned size = rules->size();
3428     for (unsigned i = 0; i < size; ++i) {
3429         const RuleData& ruleData = rules->at(i);
3430         CSSStyleRule* rule = ruleData.rule();
3431         const AtomicString& selectorLocalName = ruleData.selector()->tag().localName();
3432         if (selectorLocalName != starAtom && selectorLocalName != pageName)
3433             continue;
3434         CSSSelector::PseudoType pseudoType = ruleData.selector()->pseudoType();
3435         if ((pseudoType == CSSSelector::PseudoLeftPage && !isLeftPage)
3436             || (pseudoType == CSSSelector::PseudoRightPage && isLeftPage)
3437             || (pseudoType == CSSSelector::PseudoFirstPage && !isFirstPage))
3438             continue;
3439
3440         // If the rule has no properties to apply, then ignore it.
3441         CSSMutableStyleDeclaration* decl = rule->declaration();
3442         if (!decl || !decl->length())
3443             continue;
3444
3445         // Add this rule to our list of matched rules.
3446         addMatchedRule(&ruleData);
3447     }
3448 }
3449
3450 bool CSSStyleSelector::isLeftPage(int pageIndex) const
3451 {
3452     bool isFirstPageLeft = false;
3453     if (!m_rootElementStyle->isLeftToRightDirection())
3454         isFirstPageLeft = true;
3455
3456     return (pageIndex + (isFirstPageLeft ? 1 : 0)) % 2;
3457 }
3458
3459 bool CSSStyleSelector::isFirstPage(int pageIndex) const
3460 {
3461     // FIXME: In case of forced left/right page, page at index 1 (not 0) can be the first page.
3462     return (!pageIndex);
3463 }
3464
3465 String CSSStyleSelector::pageName(int /* pageIndex */) const
3466 {
3467     // FIXME: Implement page index to page name mapping.
3468     return "";
3469 }
3470
3471 static void applyCounterList(RenderStyle* style, CSSValueList* list, bool isReset)
3472 {
3473     CounterDirectiveMap& map = style->accessCounterDirectives();
3474     typedef CounterDirectiveMap::iterator Iterator;
3475
3476     Iterator end = map.end();
3477     for (Iterator it = map.begin(); it != end; ++it)
3478         if (isReset)
3479             it->second.m_reset = false;
3480         else
3481             it->second.m_increment = false;
3482
3483     int length = list ? list->length() : 0;
3484     for (int i = 0; i < length; ++i) {
3485         CSSValue* currValue = list->itemWithoutBoundsCheck(i);
3486         if (!currValue->isPrimitiveValue())
3487             continue;
3488
3489         Pair* pair = static_cast<CSSPrimitiveValue*>(currValue)->getPairValue();
3490         if (!pair || !pair->first() || !pair->second())
3491             continue;
3492
3493         AtomicString identifier = static_cast<CSSPrimitiveValue*>(pair->first())->getStringValue();
3494         // FIXME: What about overflow?
3495         int value = static_cast<CSSPrimitiveValue*>(pair->second())->getIntValue();
3496         CounterDirectives& directives = map.add(identifier.impl(), CounterDirectives()).first->second;
3497         if (isReset) {
3498             directives.m_reset = true;
3499             directives.m_resetValue = value;
3500         } else {
3501             if (directives.m_increment)
3502                 directives.m_incrementValue += value;
3503             else {
3504                 directives.m_increment = true;
3505                 directives.m_incrementValue = value;
3506             }
3507         }
3508     }
3509 }
3510
3511 void CSSStyleSelector::applyPropertyToStyle(int id, CSSValue *value, RenderStyle* style)
3512 {
3513     initElement(0);
3514     initForStyleResolve(0, style);
3515     m_style = style;
3516     if (value)
3517         applyProperty(id, value);
3518 }
3519
3520 inline bool isValidVisitedLinkProperty(int id)
3521 {
3522     switch(static_cast<CSSPropertyID>(id)) {
3523         case CSSPropertyBackgroundColor:
3524         case CSSPropertyBorderLeftColor:
3525         case CSSPropertyBorderRightColor:
3526         case CSSPropertyBorderTopColor:
3527         case CSSPropertyBorderBottomColor:
3528         case CSSPropertyColor:
3529         case CSSPropertyOutlineColor:
3530         case CSSPropertyWebkitColumnRuleColor:
3531         case CSSPropertyWebkitTextEmphasisColor:
3532         case CSSPropertyWebkitTextFillColor:
3533         case CSSPropertyWebkitTextStrokeColor:
3534         // Also allow shorthands so that inherit/initial still work.
3535         case CSSPropertyBackground:
3536         case CSSPropertyBorderLeft:
3537         case CSSPropertyBorderRight:
3538         case CSSPropertyBorderTop:
3539         case CSSPropertyBorderBottom:
3540         case CSSPropertyOutline:
3541         case CSSPropertyWebkitColumnRule:
3542 #if ENABLE(SVG)
3543         case CSSPropertyFill:
3544         case CSSPropertyStroke:
3545 #endif
3546             return true;
3547         default:
3548             break;
3549     }
3550
3551     return false;
3552 }
3553
3554 class SVGDisplayPropertyGuard {
3555     WTF_MAKE_NONCOPYABLE(SVGDisplayPropertyGuard);
3556 public:
3557     SVGDisplayPropertyGuard(Element*, RenderStyle*);
3558     ~SVGDisplayPropertyGuard();
3559 private:
3560 #if ENABLE(SVG)
3561     RenderStyle* m_style;
3562     EDisplay m_originalDisplayPropertyValue;
3563 #endif
3564 };
3565
3566 #if !ENABLE(SVG)
3567 inline SVGDisplayPropertyGuard::SVGDisplayPropertyGuard(Element*, RenderStyle*)
3568 {
3569 }
3570
3571 inline SVGDisplayPropertyGuard::~SVGDisplayPropertyGuard()
3572 {
3573 }
3574 #else
3575 static inline bool isAcceptableForSVGElement(EDisplay displayPropertyValue)
3576 {
3577     return displayPropertyValue == INLINE || displayPropertyValue == BLOCK || displayPropertyValue == NONE;
3578 }
3579
3580 inline SVGDisplayPropertyGuard::SVGDisplayPropertyGuard(Element* element, RenderStyle* style)
3581 {
3582     if (!(element && element->isSVGElement() && style->styleType() == NOPSEUDO)) {
3583         m_originalDisplayPropertyValue = NONE;
3584         m_style = 0;
3585         return;
3586     }
3587     m_style = style;
3588     m_originalDisplayPropertyValue = style->display();
3589     ASSERT(isAcceptableForSVGElement(m_originalDisplayPropertyValue));
3590 }
3591
3592 inline SVGDisplayPropertyGuard::~SVGDisplayPropertyGuard()
3593 {
3594     if (!m_style || isAcceptableForSVGElement(m_style->display()))
3595         return;
3596     m_style->setDisplay(m_originalDisplayPropertyValue);
3597 }
3598 #endif
3599
3600
3601 // SVG handles zooming in a different way compared to CSS. The whole document is scaled instead
3602 // of each individual length value in the render style / tree. CSSPrimitiveValue::computeLength*()
3603 // multiplies each resolved length with the zoom multiplier - so for SVG we need to disable that.
3604 // Though all CSS values that can be applied to outermost <svg> elements (width/height/border/padding...)
3605 // need to respect the scaling. RenderBox (the parent class of RenderSVGRoot) grabs values like
3606 // width/height/border/padding/... from the RenderStyle -> for SVG these values would never scale,
3607 // if we'd pass a 1.0 zoom factor everyhwere. So we only pass a zoom factor of 1.0 for specific
3608 // properties that are NOT allowed to scale within a zoomed SVG document (letter/word-spacing/font-size).
3609 static inline bool useSVGZoomRules(const Element* e)
3610 {
3611     return e && e->isSVGElement();
3612 }
3613
3614 void CSSStyleSelector::applyProperty(int id, CSSValue *value)
3615 {
3616     CSSPrimitiveValue* primitiveValue = 0;
3617     if (value->isPrimitiveValue())
3618         primitiveValue = static_cast<CSSPrimitiveValue*>(value);
3619
3620     float zoomFactor = m_style->effectiveZoom();
3621
3622     Length l;
3623
3624     unsigned short valueType = value->cssValueType();
3625
3626     bool isInherit = m_parentNode && valueType == CSSValue::CSS_INHERIT;
3627     bool isInitial = valueType == CSSValue::CSS_INITIAL || (!m_parentNode && valueType == CSSValue::CSS_INHERIT);
3628     
3629     id = CSSProperty::resolveDirectionAwareProperty(id, m_style->direction(), m_style->writingMode());
3630
3631     if (m_checker.m_matchVisitedPseudoClass && !isValidVisitedLinkProperty(id)) {
3632         // Limit the properties that can be applied to only the ones honored by :visited.
3633         return;
3634     }
3635     
3636     CSSPropertyID property = static_cast<CSSPropertyID>(id);
3637
3638     // check lookup table for implementations and use when available
3639     if (m_applyProperty.implements(property)) {
3640         if (isInherit)
3641             m_applyProperty.applyInheritValue(property, this);
3642         else if (isInitial)
3643             m_applyProperty.applyInitialValue(property, this);
3644         else
3645             m_applyProperty.applyValue(property, this, value);
3646         return;
3647     }
3648
3649     // What follows is a list that maps the CSS properties into their corresponding front-end
3650     // RenderStyle values.  Shorthands (e.g. border, background) occur in this list as well and
3651     // are only hit when mapping "inherit" or "initial" into front-end values.
3652     switch (property) {
3653 // ident only properties
3654     case CSSPropertyBorderCollapse:
3655         HANDLE_INHERIT_AND_INITIAL_AND_PRIMITIVE(borderCollapse, BorderCollapse)
3656         return;
3657     case CSSPropertyOutlineStyle:
3658         HANDLE_INHERIT_AND_INITIAL_WITH_VALUE(outlineStyle, OutlineStyle, BorderStyle)
3659         if (primitiveValue) {
3660             if (primitiveValue->getIdent() == CSSValueAuto)
3661                 m_style->setOutlineStyle(DOTTED, true);
3662             else
3663                 m_style->setOutlineStyle(*primitiveValue);
3664         }
3665         return;
3666     case CSSPropertyCaptionSide:
3667         HANDLE_INHERIT_AND_INITIAL_AND_PRIMITIVE(captionSide, CaptionSide)
3668         return;
3669     case CSSPropertyClear:
3670         HANDLE_INHERIT_AND_INITIAL_AND_PRIMITIVE(clear, Clear)
3671         return;
3672     case CSSPropertyDisplay: {
3673         SVGDisplayPropertyGuard guard(m_element, m_style.get());
3674         HANDLE_INHERIT_AND_INITIAL_AND_PRIMITIVE(display, Display)
3675 #if ENABLE(WCSS)
3676         if (primitiveValue && primitiveValue->getIdent() == CSSValueWapMarquee) {
3677             // Initialize WAP Marquee style
3678             m_style->setOverflowX(OMARQUEE);
3679             m_style->setOverflowY(OMARQUEE);
3680             m_style->setWhiteSpace(NOWRAP);
3681             m_style->setMarqueeDirection(MLEFT);
3682             m_style->setMarqueeSpeed(85); // Normal speed
3683             m_style->setMarqueeLoopCount(1);
3684             m_style->setMarqueeBehavior(MSCROLL);
3685
3686             if (m_parentStyle)
3687                 m_style->setDisplay(m_parentStyle->display());
3688         }
3689 #endif
3690         return;
3691     }
3692     case CSSPropertyEmptyCells:
3693         HANDLE_INHERIT_AND_INITIAL_AND_PRIMITIVE(emptyCells, EmptyCells)
3694         return;
3695     case CSSPropertyFloat:
3696         HANDLE_INHERIT_AND_INITIAL_AND_PRIMITIVE(floating, Floating)
3697         return;
3698     case CSSPropertyListStylePosition:
3699         HANDLE_INHERIT_AND_INITIAL_AND_PRIMITIVE(listStylePosition, ListStylePosition)
3700         return;
3701     case CSSPropertyListStyleType:
3702         HANDLE_INHERIT_AND_INITIAL_AND_PRIMITIVE(listStyleType, ListStyleType)
3703         return;
3704     case CSSPropertyPageBreakBefore:
3705         HANDLE_INHERIT_AND_INITIAL_AND_PRIMITIVE_WITH_VALUE(pageBreakBefore, PageBreakBefore, PageBreak)
3706         return;
3707     case CSSPropertyPageBreakAfter:
3708         HANDLE_INHERIT_AND_INITIAL_AND_PRIMITIVE_WITH_VALUE(pageBreakAfter, PageBreakAfter, PageBreak)
3709         return;
3710     case CSSPropertyPageBreakInside:
3711         HANDLE_INHERIT_AND_INITIAL_AND_PRIMITIVE_WITH_VALUE(pageBreakInside, PageBreakInside, PageBreak)
3712         return;
3713     case CSSPropertyPosition:
3714         HANDLE_INHERIT_AND_INITIAL_AND_PRIMITIVE(position, Position)
3715         return;
3716     case CSSPropertyTableLayout:
3717         HANDLE_INHERIT_AND_INITIAL_AND_PRIMITIVE(tableLayout, TableLayout)
3718         return;
3719     case CSSPropertyUnicodeBidi: 
3720         HANDLE_INHERIT_AND_INITIAL_AND_PRIMITIVE(unicodeBidi, UnicodeBidi)
3721         return;
3722     case CSSPropertyTextTransform: 
3723         HANDLE_INHERIT_AND_INITIAL_AND_PRIMITIVE(textTransform, TextTransform)
3724         return;
3725     case CSSPropertyVisibility:
3726         HANDLE_INHERIT_AND_INITIAL_AND_PRIMITIVE(visibility, Visibility)
3727         return;
3728     case CSSPropertyWhiteSpace:
3729         HANDLE_INHERIT_AND_INITIAL_AND_PRIMITIVE(whiteSpace, WhiteSpace)
3730         return;
3731     case CSSPropertyBorderSpacing: {
3732         if (isInherit) {
3733             m_style->setHorizontalBorderSpacing(m_parentStyle->horizontalBorderSpacing());
3734             m_style->setVerticalBorderSpacing(m_parentStyle->verticalBorderSpacing());
3735         }
3736         else if (isInitial) {
3737             m_style->setHorizontalBorderSpacing(0);
3738             m_style->setVerticalBorderSpacing(0);
3739         }
3740         return;
3741     }
3742     case CSSPropertyWebkitBorderHorizontalSpacing: {
3743         HANDLE_INHERIT_AND_INITIAL(horizontalBorderSpacing, HorizontalBorderSpacing)
3744         if (!primitiveValue)
3745             return;
3746         short spacing = primitiveValue->computeLengthShort(style(), m_rootElementStyle, zoomFactor);
3747         m_style->setHorizontalBorderSpacing(spacing);
3748         return;
3749     }
3750     case CSSPropertyWebkitBorderVerticalSpacing: {
3751         HANDLE_INHERIT_AND_INITIAL(verticalBorderSpacing, VerticalBorderSpacing)
3752         if (!primitiveValue)
3753             return;
3754         short spacing = primitiveValue->computeLengthShort(style(), m_rootElementStyle, zoomFactor);
3755         m_style->setVerticalBorderSpacing(spacing);
3756         return;
3757     }
3758     case CSSPropertyCursor:
3759         if (isInherit) {
3760             m_style->setCursor(m_parentStyle->cursor());
3761             m_style->setCursorList(m_parentStyle->cursors());
3762             return;
3763         }
3764         m_style->clearCursorList();
3765         if (isInitial) {