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