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