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