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