CSSStyleSelector.cpp 207 KB
Newer Older
darin@apple.com's avatar
darin@apple.com committed
1
/*
kocienda's avatar
kocienda committed
2
 * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
3
 *           (C) 2004-2005 Allan Sandfeld Jensen (kde@carewolf.com)
mitz@apple.com's avatar
mitz@apple.com committed
4
 * Copyright (C) 2006, 2007 Nicholas Shanks (webkit@nickshanks.com)
adele@apple.com's avatar
adele@apple.com committed
5
 * Copyright (C) 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.
ap's avatar
ap committed
6
 * Copyright (C) 2007 Alexey Proskuryakov <ap@webkit.org>
7
 * Copyright (C) 2007, 2008 Eric Seidel <eric@webkit.org>
kocienda's avatar
kocienda committed
8
9
10
11
12
13
14
15
16
17
18
19
20
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public License
 * along with this library; see the file COPYING.LIB.  If not, write to
ddkilzer's avatar
ddkilzer committed
21
22
 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
 * Boston, MA 02110-1301, USA.
kocienda's avatar
kocienda committed
23
 */
24

mjs's avatar
mjs committed
25
#include "config.h"
weinig's avatar
weinig committed
26
#include "CSSStyleSelector.h"
kocienda's avatar
kocienda committed
27

28
#include "CSSBorderImageValue.h"
rwlbuis's avatar
rwlbuis committed
29
#include "CSSCursorImageValue.h"
30
31
#include "CSSFontFace.h"
#include "CSSFontFaceRule.h"
32
#include "CSSFontFaceSource.h"
33
34
35
#include "CSSImageValue.h"
#include "CSSImportRule.h"
#include "CSSMediaRule.h"
ap's avatar
ap committed
36
#include "CSSPrimitiveValueMappings.h"
37
#include "CSSProperty.h"
darin's avatar
darin committed
38
#include "CSSPropertyNames.h"
39
#include "CSSRuleList.h"
40
#include "CSSSelector.h"
41
#include "CSSStyleRule.h"
42
#include "CSSStyleSheet.h"
43
#include "CSSTimingFunctionValue.h"
44
#include "CSSValueList.h"
darin's avatar
darin committed
45
#include "CachedImage.h"
weinig's avatar
weinig committed
46
#include "Counter.h"
47
48
49
#include "DashboardRegion.h"
#include "FontFamilyValue.h"
#include "FontValue.h"
darin's avatar
darin committed
50
#include "Frame.h"
darin's avatar
darin committed
51
#include "FrameView.h"
darin's avatar
darin committed
52
#include "HTMLDocument.h"
darin's avatar
darin committed
53
#include "HTMLElement.h"
adele's avatar
adele committed
54
#include "HTMLInputElement.h"
darin's avatar
darin committed
55
#include "HTMLNames.h"
56
#include "MediaList.h"
57
#include "MediaQueryEvaluator.h"
darin@apple.com's avatar
darin@apple.com committed
58
59
#include "Page.h"
#include "PageGroup.h"
60
#include "Pair.h"
weinig's avatar
weinig committed
61
#include "Rect.h"
darin's avatar
darin committed
62
#include "RenderTheme.h"
63
#include "SelectionController.h"
weinig's avatar
weinig committed
64
65
#include "Settings.h"
#include "ShadowValue.h"
66
#include "StyleSheetList.h"
hyatt@apple.com's avatar
hyatt@apple.com committed
67
#include "Text.h"
darin's avatar
darin committed
68
#include "UserAgentStyleSheets.h"
69
#include "XMLNames.h"
70
#include "loader.h"
weinig@apple.com's avatar
weinig@apple.com committed
71
#include <wtf/Vector.h>
kocienda's avatar
kocienda committed
72

mjs's avatar
mjs committed
73
#if ENABLE(SVG)
74
#include "XLinkNames.h"
75
#include "SVGNames.h"
76
77
#endif

darin's avatar
darin committed
78
79
using namespace std;

darin's avatar
darin committed
80
namespace WebCore {
mjs's avatar
mjs committed
81

darin's avatar
darin committed
82
83
using namespace HTMLNames;

hyatt's avatar
hyatt committed
84
85
// #define STYLE_SHARING_STATS 1

86
#define HANDLE_INHERIT(prop, Prop) \
darin's avatar
darin committed
87
if (isInherit) { \
88
    m_style->set##Prop(m_parentStyle->prop()); \
darin's avatar
darin committed
89
    return; \
90
91
}

92
93
#define HANDLE_INHERIT_AND_INITIAL(prop, Prop) \
HANDLE_INHERIT(prop, Prop) \
darin's avatar
darin committed
94
if (isInitial) { \
95
    m_style->set##Prop(RenderStyle::initial##Prop()); \
darin's avatar
darin committed
96
    return; \
97
}
98
99
100

#define HANDLE_INHERIT_AND_INITIAL_WITH_VALUE(prop, Prop, Value) \
HANDLE_INHERIT(prop, Prop) \
darin's avatar
darin committed
101
if (isInitial) { \
102
    m_style->set##Prop(RenderStyle::initial##Value());\
103
104
    return;\
}
105

106
#define HANDLE_MULTILAYER_INHERIT_AND_INITIAL(layerType, LayerType, prop, Prop) \
107
if (isInherit) { \
108
    LayerType* currChild = m_style->access##LayerType##s(); \
109
    LayerType* prevChild = 0; \
110
    const LayerType* currParent = m_parentStyle->layerType##s(); \
111
112
113
    while (currParent && currParent->is##Prop##Set()) { \
        if (!currChild) { \
            /* Need to make a new layer.*/ \
114
            currChild = new LayerType(); \
115
116
117
118
119
120
121
122
123
124
125
126
127
            prevChild->setNext(currChild); \
        } \
        currChild->set##Prop(currParent->prop()); \
        prevChild = currChild; \
        currChild = prevChild->next(); \
        currParent = currParent->next(); \
    } \
    \
    while (currChild) { \
        /* Reset any remaining layers to not have the property set. */ \
        currChild->clear##Prop(); \
        currChild = currChild->next(); \
    } \
128
} else if (isInitial) { \
129
    LayerType* currChild = m_style->access##LayerType##s(); \
130
131
132
133
134
    currChild->set##Prop(RenderStyle::initial##Prop()); \
    for (currChild = currChild->next(); currChild; currChild = currChild->next()) \
        currChild->clear##Prop(); \
}

135
136
#define HANDLE_MULTILAYER_VALUE(layerType, LayerType, prop, Prop, value) { \
HANDLE_MULTILAYER_INHERIT_AND_INITIAL(layerType, LayerType, prop, Prop) \
137
138
if (isInherit || isInitial) \
    return; \
139
LayerType* currChild = m_style->access##LayerType##s(); \
140
LayerType* prevChild = 0; \
mitz@apple.com's avatar
mitz@apple.com committed
141
if (value->isValueList()) { \
142
    /* Walk each value and put it into a layer, creating new layers as needed. */ \
darin's avatar
darin committed
143
    CSSValueList* valueList = static_cast<CSSValueList*>(value); \
144
145
146
    for (unsigned int i = 0; i < valueList->length(); i++) { \
        if (!currChild) { \
            /* Need to make a new layer to hold this value */ \
147
            currChild = new LayerType(); \
148
149
            prevChild->setNext(currChild); \
        } \
bdakin@apple.com's avatar
bdakin@apple.com committed
150
        map##Prop(currChild, valueList->itemWithoutBoundsCheck(i)); \
151
152
153
        prevChild = currChild; \
        currChild = currChild->next(); \
    } \
mitz@apple.com's avatar
mitz@apple.com committed
154
155
156
} else { \
    map##Prop(currChild, value); \
    currChild = currChild->next(); \
157
158
159
160
161
162
163
} \
while (currChild) { \
    /* Reset all remaining layers to not have the property set. */ \
    currChild->clear##Prop(); \
    currChild = currChild->next(); \
} }

164
165
166
167
168
169
170
171
172
#define HANDLE_BACKGROUND_INHERIT_AND_INITIAL(prop, Prop) \
HANDLE_MULTILAYER_INHERIT_AND_INITIAL(backgroundLayer, BackgroundLayer, prop, Prop)

#define HANDLE_BACKGROUND_VALUE(prop, Prop, value) \
HANDLE_MULTILAYER_VALUE(backgroundLayer, BackgroundLayer, prop, Prop, value)

#define HANDLE_TRANSITION_VALUE(prop, Prop, value) \
HANDLE_MULTILAYER_VALUE(transition, Transition, prop, Prop, value)

173
#define HANDLE_INHERIT_COND(propID, prop, Prop) \
darin's avatar
darin committed
174
if (id == propID) { \
175
    m_style->set##Prop(m_parentStyle->prop()); \
darin's avatar
darin committed
176
    return; \
177
178
}

179
#define HANDLE_INITIAL_COND(propID, Prop) \
darin's avatar
darin committed
180
if (id == propID) { \
181
    m_style->set##Prop(RenderStyle::initial##Prop()); \
darin's avatar
darin committed
182
    return; \
183
184
185
}

#define HANDLE_INITIAL_COND_WITH_VALUE(propID, Prop, Value) \
darin's avatar
darin committed
186
if (id == propID) { \
187
    m_style->set##Prop(RenderStyle::initial##Value()); \
darin's avatar
darin committed
188
    return; \
189
190
}

darin@apple.com's avatar
darin@apple.com committed
191
class CSSRuleSet {
mjs's avatar
mjs committed
192
193
194
195
public:
    CSSRuleSet();
    ~CSSRuleSet();
    
mjs's avatar
mjs committed
196
    typedef HashMap<AtomicStringImpl*, CSSRuleDataList*> AtomRuleMap;
mjs's avatar
mjs committed
197
    
rwlbuis@webkit.org's avatar
rwlbuis@webkit.org committed
198
    void addRulesFromSheet(CSSStyleSheet*, const MediaQueryEvaluator&, CSSStyleSelector* = 0);
mjs's avatar
mjs committed
199
    
darin's avatar
darin committed
200
    void addRule(CSSStyleRule* rule, CSSSelector* sel);
mjs's avatar
mjs committed
201
    void addToRuleSet(AtomicStringImpl* key, AtomRuleMap& map,
darin's avatar
darin committed
202
                      CSSStyleRule* rule, CSSSelector* sel);
mjs's avatar
mjs committed
203
    
mjs's avatar
mjs committed
204
205
206
    CSSRuleDataList* getIDRules(AtomicStringImpl* key) { return m_idRules.get(key); }
    CSSRuleDataList* getClassRules(AtomicStringImpl* key) { return m_classRules.get(key); }
    CSSRuleDataList* getTagRules(AtomicStringImpl* key) { return m_tagRules.get(key); }
mjs's avatar
mjs committed
207
208
209
210
211
212
213
    CSSRuleDataList* getUniversalRules() { return m_universalRules; }
    
public:
    AtomRuleMap m_idRules;
    AtomRuleMap m_classRules;
    AtomRuleMap m_tagRules;
    CSSRuleDataList* m_universalRules;
darin's avatar
darin committed
214
    unsigned m_ruleCount;
mjs's avatar
mjs committed
215
216
};

darin@apple.com's avatar
darin@apple.com committed
217
218
219
220
static CSSRuleSet* defaultStyle;
static CSSRuleSet* defaultQuirksStyle;
static CSSRuleSet* defaultPrintStyle;
static CSSRuleSet* defaultViewSourceStyle;
221

darin@apple.com's avatar
darin@apple.com committed
222
RenderStyle* CSSStyleSelector::s_styleNotYetAvailable;
kocienda's avatar
kocienda committed
223
224
225

static PseudoState pseudoState;

darin@apple.com's avatar
darin@apple.com committed
226
227
static void loadDefaultStyle();

rwlbuis@webkit.org's avatar
rwlbuis@webkit.org committed
228
229
230
231
232
233
234
235
236
237
238
239
static const MediaQueryEvaluator& screenEval()
{
    static const MediaQueryEvaluator staticScreenEval("screen");
    return staticScreenEval;
}

static const MediaQueryEvaluator& printEval()
{
    static const MediaQueryEvaluator staticPrintEval("print");
    return staticPrintEval;
}

darin@apple.com's avatar
darin@apple.com committed
240
241
CSSStyleSelector::CSSStyleSelector(Document* doc, const String& userStyleSheet, StyleSheetList* styleSheets, CSSStyleSheet* mappedElementSheet, bool strictParsing, bool matchAuthorAndUserStyles)
    : m_strictParsing(strictParsing)
kocienda's avatar
kocienda committed
242
{
darin's avatar
darin committed
243
    init();
ggaren's avatar
ggaren committed
244
245
    
    m_document = doc;
mitz@apple.com's avatar
mitz@apple.com committed
246
    m_fontSelector = new CSSFontSelector(doc);
darin's avatar
darin committed
247

timothy@apple.com's avatar
timothy@apple.com committed
248
249
    m_matchAuthorAndUserStyles = matchAuthorAndUserStyles;

darin@apple.com's avatar
darin@apple.com committed
250
251
    m_strictParsing = strictParsing;
    if (!defaultStyle)
eseidel's avatar
eseidel committed
252
        loadDefaultStyle();
kocienda's avatar
kocienda committed
253

254
    m_userStyle = 0;
darin's avatar
darin committed
255

256
257
258
259
260
261
    // construct document root element default style. this is needed
    // to evaluate media queries that contain relative constraints, like "screen and (max-width: 10em)"
    // This is here instead of constructor, because when constructor is run,
    // document doesn't have documentElement
    // NOTE: this assumes that element that gets passed to styleForElement -call
    // is always from the document that owns the style selector
ggaren's avatar
ggaren committed
262
    FrameView* view = m_document->view();
263
264
265
266
267
268
269
270
271
272
273
274
    if (view)
        m_medium = new MediaQueryEvaluator(view->mediaType());
    else
        m_medium = new MediaQueryEvaluator("all");

    Element* root = doc->documentElement();

    if (root)
        m_rootDefaultStyle = styleForElement(root, 0, false, true); // dont ref, because the RenderStyle is allocated from global heap

    if (m_rootDefaultStyle && view) {
        delete m_medium;
275
        m_medium = new MediaQueryEvaluator(view->mediaType(), view->frame(), m_rootDefaultStyle);
276
277
    }

278
    // FIXME: This sucks! The user sheet is reparsed every time!
279
    if (!userStyleSheet.isEmpty()) {
darin's avatar
darin committed
280
        m_userSheet = new CSSStyleSheet(doc);
281
        m_userSheet->parseString(userStyleSheet, strictParsing);
282

283
        m_userStyle = new CSSRuleSet();
rwlbuis@webkit.org's avatar
rwlbuis@webkit.org committed
284
        m_userStyle->addRulesFromSheet(m_userSheet.get(), *m_medium, this);
285
    }
kocienda's avatar
kocienda committed
286
287

    // add stylesheets from document
288
    m_authorStyle = new CSSRuleSet();
289
290
291
    
    // Add rules from elments like SVG's <font-face>
    if (mappedElementSheet)
rwlbuis@webkit.org's avatar
rwlbuis@webkit.org committed
292
        m_authorStyle->addRulesFromSheet(mappedElementSheet, *m_medium, this);
293

darin's avatar
darin committed
294
    DeprecatedPtrListIterator<StyleSheet> it(styleSheets->styleSheets);
295
    for (; it.current(); ++it)
296
        if (it.current()->isCSSStyleSheet() && !it.current()->disabled())
rwlbuis@webkit.org's avatar
rwlbuis@webkit.org committed
297
            m_authorStyle->addRulesFromSheet(static_cast<CSSStyleSheet*>(it.current()), *m_medium, this);
kocienda's avatar
kocienda committed
298
299
}

darin's avatar
darin committed
300
301
void CSSStyleSelector::init()
{
302
    m_element = 0;
303
    m_matchedDecls.clear();
304
305
306
307
    m_ruleList = 0;
    m_collectRulesOnly = false;
    m_rootDefaultStyle = 0;
    m_medium = 0;
darin's avatar
darin committed
308
309
}

kocienda's avatar
kocienda committed
310
311
CSSStyleSelector::~CSSStyleSelector()
{
312
    delete m_medium;
313
    ::delete m_rootDefaultStyle;
314
315
    delete m_authorStyle;
    delete m_userStyle;
316
    deleteAllValues(m_viewportDependentMediaQueryResults);
kocienda's avatar
kocienda committed
317
318
}

darin's avatar
darin committed
319
static CSSStyleSheet* parseUASheet(const char* characters, unsigned size)
320
{
darin's avatar
darin committed
321
322
    CSSStyleSheet* const parent = 0;
    CSSStyleSheet* sheet = new CSSStyleSheet(parent);
darin@apple.com's avatar
darin@apple.com committed
323
    sheet->ref(); // leak the sheet on purpose
darin's avatar
darin committed
324
    sheet->parseString(String(characters, size));
325
326
327
    return sheet;
}

darin's avatar
darin committed
328
template<typename T> CSSStyleSheet* parseUASheet(const T& array)
darin's avatar
darin committed
329
{
darin's avatar
darin committed
330
    return parseUASheet(array, sizeof(array));
darin's avatar
darin committed
331
332
}

darin@apple.com's avatar
darin@apple.com committed
333
static void loadDefaultStyle()
kocienda's avatar
kocienda committed
334
{
darin@apple.com's avatar
darin@apple.com committed
335
    ASSERT(!defaultStyle);
kocienda's avatar
kocienda committed
336

darin@apple.com's avatar
darin@apple.com committed
337
338
339
340
    defaultStyle = new CSSRuleSet;
    defaultPrintStyle = new CSSRuleSet;
    defaultQuirksStyle = new CSSRuleSet;
    defaultViewSourceStyle = new CSSRuleSet;
341

darin's avatar
darin committed
342
    // Strict-mode rules.
darin@apple.com's avatar
darin@apple.com committed
343
344
345
    CSSStyleSheet* defaultSheet = parseUASheet(html4UserAgentStyleSheet);
    defaultStyle->addRulesFromSheet(defaultSheet, screenEval());
    defaultPrintStyle->addRulesFromSheet(defaultSheet, printEval());
eseidel's avatar
eseidel committed
346

darin's avatar
darin committed
347
    // Quirks-mode rules.
darin@apple.com's avatar
darin@apple.com committed
348
    defaultQuirksStyle->addRulesFromSheet(parseUASheet(quirksUserAgentStyleSheet), screenEval());
349
350
    
    // View source rules.
darin@apple.com's avatar
darin@apple.com committed
351
    defaultViewSourceStyle->addRulesFromSheet(parseUASheet(sourceUserAgentStyleSheet), screenEval());
kocienda's avatar
kocienda committed
352
353
}

354
355
void CSSStyleSelector::matchRules(CSSRuleSet* rules, int& firstRuleIndex, int& lastRuleIndex)
{
356
357
    m_matchedRules.clear();

358
    if (!rules || !m_element)
359
        return;
360
361
362
    
    // We need to collect the rules for id, class, tag, and everything else into a buffer and
    // then sort the buffer.
363
364
365
    if (m_element->hasID())
        matchRulesForList(rules->getIDRules(m_element->getIDAttribute().impl()), firstRuleIndex, lastRuleIndex);
    if (m_element->hasClass()) {
366
367
368
369
        ASSERT(m_styledElement);
        const ClassNames& classNames = m_styledElement->classNames();
        size_t size = classNames.size();
        for (size_t i = 0; i < size; ++i)
weinig@apple.com's avatar
weinig@apple.com committed
370
            matchRulesForList(rules->getClassRules(classNames[i].impl()), firstRuleIndex, lastRuleIndex);
371
    }
372
    matchRulesForList(rules->getTagRules(m_element->localName().impl()), firstRuleIndex, lastRuleIndex);
373
374
375
    matchRulesForList(rules->getUniversalRules(), firstRuleIndex, lastRuleIndex);
    
    // If we didn't match any rules, we're done.
376
377
    if (m_matchedRules.isEmpty())
        return;
378
379
    
    // Sort the set of matched rules.
380
    sortMatchedRules(0, m_matchedRules.size());
381
382
    
    // Now transfer the set of matched rules over to our list of decls.
383
    if (!m_collectRulesOnly) {
384
        for (unsigned i = 0; i < m_matchedRules.size(); i++)
385
386
            addMatchedDeclaration(m_matchedRules[i]->rule()->declaration());
    } else {
387
        for (unsigned i = 0; i < m_matchedRules.size(); i++) {
388
            if (!m_ruleList)
darin's avatar
darin committed
389
                m_ruleList = new CSSRuleList();
390
391
392
            m_ruleList->append(m_matchedRules[i]->rule());
        }
    }
393
394
}

395
void CSSStyleSelector::matchRulesForList(CSSRuleDataList* rules, int& firstRuleIndex, int& lastRuleIndex)
396
{
397
398
399
    if (!rules)
        return;

400
    for (CSSRuleData* d = rules->first(); d; d = d->next()) {
darin's avatar
darin committed
401
        CSSStyleRule* rule = d->rule();
402
        const AtomicString& localName = m_element->localName();
403
        const AtomicString& selectorLocalName = d->selector()->m_tag.localName();
404
        if ((localName == selectorLocalName || selectorLocalName == starAtom) && checkSelector(d->selector())) {
405
            // If the rule has no properties to apply, then ignore it.
darin's avatar
darin committed
406
            CSSMutableStyleDeclaration* decl = rule->declaration();
407
408
            if (!decl || !decl->length())
                continue;
409
410
411
            
            // If we're matching normal rules, set a pseudo bit if 
            // we really just matched a pseudo-element.
412
            if (dynamicPseudo != RenderStyle::NOPSEUDO && m_pseudoStyle == RenderStyle::NOPSEUDO) {
413
414
                if (m_collectRulesOnly)
                    return;
antti@apple.com's avatar
antti@apple.com committed
415
                if (dynamicPseudo < RenderStyle::FIRST_INTERNAL_PSEUDOID)
416
                    m_style->setHasPseudoStyle(dynamicPseudo);
417
            } else {
418
                // Update our first/last rule indices in the matched rules array.
419
420
421
                lastRuleIndex = m_matchedDecls.size() + m_matchedRules.size();
                if (firstRuleIndex == -1)
                    firstRuleIndex = lastRuleIndex;
422
423
424
425
426

                // Add this rule to our list of matched rules.
                addMatchedRule(d);
            }
        }
darin's avatar
darin committed
427
428
429
    }
}

430
431
432
433
434
435
436
437
438
439
440
bool operator >(CSSRuleData& r1, CSSRuleData& r2)
{
    int spec1 = r1.selector()->specificity();
    int spec2 = r2.selector()->specificity();
    return (spec1 == spec2) ? r1.position() > r2.position() : spec1 > spec2; 
}
bool operator <=(CSSRuleData& r1, CSSRuleData& r2)
{
    return !(r1 > r2);
}

darin's avatar
darin committed
441
void CSSStyleSelector::sortMatchedRules(unsigned start, unsigned end)
442
{
443
    if (start >= end || (end - start == 1))
444
        return; // Sanity check.
445

446
447
    if (end - start <= 6) {
        // Apply a bubble sort for smaller lists.
448
        for (unsigned i = end - 1; i > start; i--) {
449
            bool sorted = true;
darin's avatar
darin committed
450
            for (unsigned j = start; j < i; j++) {
451
                CSSRuleData* elt = m_matchedRules[j];
452
                CSSRuleData* elt2 = m_matchedRules[j + 1];
453
454
455
                if (*elt > *elt2) {
                    sorted = false;
                    m_matchedRules[j] = elt2;
456
                    m_matchedRules[j + 1] = elt;
457
458
459
460
461
                }
            }
            if (sorted)
                return;
        }
462
        return;
463
    }
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497

    // Peform a merge sort for larger lists.
    unsigned mid = (start + end) / 2;
    sortMatchedRules(start, mid);
    sortMatchedRules(mid, end);
    
    CSSRuleData* elt = m_matchedRules[mid - 1];
    CSSRuleData* elt2 = m_matchedRules[mid];
    
    // Handle the fast common case (of equal specificity).  The list may already
    // be completely sorted.
    if (*elt <= *elt2)
        return;
    
    // We have to merge sort.  Ensure our merge buffer is big enough to hold
    // all the items.
    Vector<CSSRuleData*> rulesMergeBuffer;
    rulesMergeBuffer.reserveCapacity(end - start); 

    unsigned i1 = start;
    unsigned i2 = mid;
    
    elt = m_matchedRules[i1];
    elt2 = m_matchedRules[i2];
    
    while (i1 < mid || i2 < end) {
        if (i1 < mid && (i2 == end || *elt <= *elt2)) {
            rulesMergeBuffer.append(elt);
            if (++i1 < mid)
                elt = m_matchedRules[i1];
        } else {
            rulesMergeBuffer.append(elt2);
            if (++i2 < end)
                elt2 = m_matchedRules[i2];
498
        }
499
500
501
502
    }
    
    for (unsigned i = start; i < end; i++)
        m_matchedRules[i] = rulesMergeBuffer[i - start];
503
504
}

darin's avatar
darin committed
505
void CSSStyleSelector::initElementAndPseudoState(Element* e)
kocienda's avatar
kocienda committed
506
{
507
508
509
    m_element = e;
    if (m_element && m_element->isStyledElement())
        m_styledElement = static_cast<StyledElement*>(m_element);
510
    else
511
        m_styledElement = 0;
512
513
514
    pseudoState = PseudoUnknown;
}

darin's avatar
darin committed
515
void CSSStyleSelector::initForStyleResolve(Element* e, RenderStyle* defaultParent)
516
517
{
    // set some variables we will need
518
    m_pseudoStyle = RenderStyle::NOPSEUDO;
519

520
    m_parentNode = e->parentNode();
521

mjs's avatar
mjs committed
522
#if ENABLE(SVG)
523
524
    if (!m_parentNode && e->isSVGElement() && e->isShadowNode())
        m_parentNode = e->shadowParentNode();
525
526
#endif

527
    if (defaultParent)
528
        m_parentStyle = defaultParent;
529
    else
530
531
        m_parentStyle = m_parentNode ? m_parentNode->renderStyle() : 0;
    m_isXMLDoc = !m_element->document()->isHTMLDocument();
532

533
    m_style = 0;
534
    
535
536
    m_matchedDecls.clear();

537
538
    m_ruleList = 0;

539
    m_fontDirty = false;
540
541
}

darin@apple.com's avatar
darin@apple.com committed
542
static inline const AtomicString* linkAttribute(Node* node)
543
{
darin@apple.com's avatar
darin@apple.com committed
544
545
    if (!node->isLink())
        return 0;
darin@apple.com's avatar
darin@apple.com committed
546

darin@apple.com's avatar
darin@apple.com committed
547
548
549
550
    ASSERT(node->isElementNode());
    Element* element = static_cast<Element*>(node);
    if (element->isHTMLElement())
        return &element->getAttribute(hrefAttr);
mjs's avatar
mjs committed
551
#if ENABLE(SVG)
darin@apple.com's avatar
darin@apple.com committed
552
553
    if (element->isSVGElement())
        return &element->getAttribute(XLinkNames::hrefAttr);
554
#endif
darin@apple.com's avatar
darin@apple.com committed
555
556
    return 0;
}
darin@apple.com's avatar
darin@apple.com committed
557

darin@apple.com's avatar
darin@apple.com committed
558
559
560
561
562
PseudoState CSSStyleSelector::checkPseudoState(Element* element, bool checkVisited)
{
    const AtomicString* attr = linkAttribute(element);
    if (!attr || attr->isNull())
        return PseudoNone;
darin@apple.com's avatar
darin@apple.com committed
563

darin@apple.com's avatar
darin@apple.com committed
564
565
    if (!checkVisited)
        return PseudoAnyLink;
darin@apple.com's avatar
darin@apple.com committed
566

darin@apple.com's avatar
darin@apple.com committed
567
568
569
    unsigned hash = m_document->visitedLinkHash(*attr);
    if (!hash)
        return PseudoLink;
darin@apple.com's avatar
darin@apple.com committed
570

darin@apple.com's avatar
darin@apple.com committed
571
572
573
    Frame* frame = m_document->frame();
    if (!frame)
        return PseudoLink;
darin@apple.com's avatar
darin@apple.com committed
574

darin@apple.com's avatar
darin@apple.com committed
575
    Page* page = frame->page();
darin@apple.com's avatar
darin@apple.com committed
576
577
    if (!page)
        return PseudoLink;
darin@apple.com's avatar
darin@apple.com committed
578

darin@apple.com's avatar
darin@apple.com committed
579
580
    m_linksCheckedForVisitedState.add(hash);
    return page->group().isLinkVisited(hash) ? PseudoVisited : PseudoLink;
581
582
}

583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
// a helper function for parsing nth-arguments
static bool parseNth(const String& nth, int &a, int &b)
{
    if (nth.isEmpty())
        return false;
    a = 0;
    b = 0;
    if (nth == "odd") {
        a = 2;
        b = 1;
    } else if (nth == "even") {
        a = 2;
        b = 0;
    } else {
        int n = nth.find('n');
        if (n != -1) {
            if (nth[0] == '-') {
                if (n == 1)
                    a = -1; // -n == -1n
                else
hyatt@apple.com's avatar
hyatt@apple.com committed
603
                    a = nth.substring(0, n).toInt();
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
            } else if (!n)
                a = 1; // n == 1n
            else
                a = nth.substring(0, n).toInt();

            int p = nth.find('+', n);
            if (p != -1)
                b = nth.substring(p + 1, nth.length() - p - 1).toInt();
            else {
                p = nth.find('-', n);
                b = -nth.substring(p + 1, nth.length() - p - 1).toInt();
            }
        } else
            b = nth.toInt();
    }
    return true;
}

// a helper function for checking nth-arguments
static bool matchNth(int count, int a, int b)
{
    if (!a)
        return count == b;
    else if (a > 0) {
        if (count < b)
            return false;
        return (count - b) % a == 0;
    } else {
        if (count > b)
            return false;
        return (b - count) % (-a) == 0;
    }
}


639
640
641
642
643
#ifdef STYLE_SHARING_STATS
static int fraction = 0;
static int total = 0;
#endif

644
static const unsigned cStyleSearchThreshold = 10;
645

646
Node* CSSStyleSelector::locateCousinList(Element* parent, unsigned depth)
647
{
eseidel's avatar
eseidel committed
648
    if (parent && parent->isStyledElement()) {
649
        StyledElement* p = static_cast<StyledElement*>(parent);
adele's avatar
adele committed
650
        if (!p->inlineStyleDecl() && !p->hasID()) {
darin's avatar
darin committed
651
            Node* r = p->previousSibling();
652
            unsigned subcount = 0;
adele's avatar
adele committed
653
            RenderStyle* st = p->renderStyle();
hyatt's avatar
hyatt committed
654
            while (r) {
adele's avatar
adele committed
655
                if (r->renderStyle() == st)
hyatt's avatar
hyatt committed
656
                    return r->lastChild();
657
                if (subcount++ == cStyleSearchThreshold)
hyatt's avatar
hyatt committed
658
659
660
                    return 0;
                r = r->previousSibling();
            }
661
662
            if (!r && depth < cStyleSearchThreshold)
                r = locateCousinList(static_cast<Element*>(parent->parentNode()), depth + 1);
hyatt's avatar
hyatt committed
663
            while (r) {
adele's avatar
adele committed
664
                if (r->renderStyle() == st)
hyatt's avatar
hyatt committed
665
                    return r->lastChild();
666
                if (subcount++ == cStyleSearchThreshold)
hyatt's avatar
hyatt committed
667
668
669
                    return 0;
                r = r->previousSibling();
            }
670
671
672
673
674
        }
    }
    return 0;
}

darin's avatar
darin committed
675
bool CSSStyleSelector::canShareStyleWithElement(Node* n)
676
{
677
    if (n->isStyledElement()) {
darin's avatar
darin committed
678
        StyledElement* s = static_cast<StyledElement*>(n);
adele's avatar
adele committed
679
680
        RenderStyle* style = s->renderStyle();
        if (style && !style->unique() &&
681
682
683
684
            (s->tagQName() == m_element->tagQName()) && !s->hasID() &&
            (s->hasClass() == m_element->hasClass()) && !s->inlineStyleDecl() &&
            (s->hasMappedAttributes() == m_styledElement->hasMappedAttributes()) &&
            (s->isLink() == m_element->isLink()) && 
adele's avatar
adele committed
685
            !style->affectedByAttributeSelectors() &&
686
687
688
689
690
            (s->hovered() == m_element->hovered()) &&
            (s->active() == m_element->active()) &&
            (s->focused() == m_element->focused()) &&
            (s != s->document()->getCSSTarget() && m_element != m_element->document()->getCSSTarget()) &&
            (s->getAttribute(typeAttr) == m_element->getAttribute(typeAttr)) &&
691
692
            (s->getAttribute(XMLNames::langAttr) == m_element->getAttribute(XMLNames::langAttr)) &&
            (s->getAttribute(langAttr) == m_element->getAttribute(langAttr)) &&
hyatt@apple.com's avatar
hyatt@apple.com committed
693
694
            (s->getAttribute(readonlyAttr) == m_element->getAttribute(readonlyAttr)) &&
            (s->getAttribute(cellpaddingAttr) == m_element->getAttribute(cellpaddingAttr))) {
695
            bool isControl = s->isControl();
696
            if (isControl != m_element->isControl())
697
                return false;
698
699
700
            if (isControl && (s->isEnabled() != m_element->isEnabled()) ||
                             (s->isIndeterminate() != m_element->isIndeterminate()) ||
                             (s->isChecked() != m_element->isChecked()))
701
702
                return false;
            
703
704
705
            if (style->transitions())
                return false;

hyatt's avatar
hyatt committed
706
707
            bool classesMatch = true;
            if (s->hasClass()) {
708
                const AtomicString& class1 = m_element->getAttribute(classAttr);
709
                const AtomicString& class2 = s->getAttribute(classAttr);
hyatt's avatar
hyatt committed
710
711
712
713
714
715
                classesMatch = (class1 == class2);
            }
            
            if (classesMatch) {
                bool mappedAttrsMatch = true;
                if (s->hasMappedAttributes())
716
                    mappedAttrsMatch = s->mappedAttributes()->mapsEquivalent(m_styledElement->mappedAttributes());
hyatt's avatar
hyatt committed
717
                if (mappedAttrsMatch) {
mjs's avatar
mjs committed
718
                    bool linksMatch = true;
darin@apple.com's avatar
darin@apple.com committed
719

mjs's avatar
mjs committed
720
                    if (s->isLink()) {
hyatt's avatar
hyatt committed
721
                        // We need to check to see if the visited state matches.
darin@apple.com's avatar
darin@apple.com committed
722
723
724
                        if (pseudoState == PseudoUnknown) {
                            const Color& linkColor = m_element->document()->linkColor();
                            const Color& visitedColor = m_element->document()->visitedLinkColor();
darin@apple.com's avatar
darin@apple.com committed
725
                            pseudoState = checkPseudoState(m_element, style->pseudoState() != PseudoAnyLink || linkColor != visitedColor);
darin@apple.com's avatar
darin@apple.com committed
726
                        }
adele's avatar
adele committed
727
                        linksMatch = (pseudoState == style->pseudoState());
hyatt's avatar
hyatt committed
728
729
                    }
                    
mjs's avatar
mjs committed
730
                    if (linksMatch)
hyatt's avatar
hyatt committed
731
                        return true;
732
                }
733
734
735
736
737
738
739
740
            }
        }
    }
    return false;
}

RenderStyle* CSSStyleSelector::locateSharedStyle()
{
hyatt@apple.com's avatar
hyatt@apple.com committed
741
    if (m_styledElement && !m_styledElement->inlineStyleDecl() && !m_styledElement->hasID() && !m_styledElement->document()->usesSiblingRules()) {
742
        // Check previous siblings.
743
        unsigned count = 0;
darin's avatar
darin committed
744
        Node* n;
745
        for (n = m_element->previousSibling(); n && !n->isElementNode(); n = n->previousSibling()) { }
746
        while (n) {
hyatt's avatar
hyatt committed
747
            if (canShareStyleWithElement(n))
adele's avatar
adele committed
748
                return n->renderStyle();
749
            if (count++ == cStyleSearchThreshold)
750
                return 0;
751
            for (n = n->previousSibling(); n && !n->isElementNode(); n = n->previousSibling()) { }
752
        }
hyatt's avatar
hyatt committed
753
        if (!n) 
754
            n = locateCousinList(static_cast<Element*>(m_element->parentNode()));
755
        while (n) {
hyatt's avatar
hyatt committed
756
            if (canShareStyleWithElement(n))
adele's avatar
adele committed
757
                return n->renderStyle();
758
            if (count++ == cStyleSearchThreshold)
759
                return 0;
760
            for (n = n->previousSibling(); n && !n->isElementNode(); n = n->previousSibling()) { }
761
762
763
764
765
        }        
    }
    return 0;
}

766
767
void CSSStyleSelector::matchUARules(int& firstUARule, int& lastUARule)
{
bdakin's avatar
bdakin committed
768
    // First we match rules from the user agent sheet.
darin's avatar
darin committed
769
    CSSRuleSet* userAgentStyleSheet = m_medium->mediaTypeMatchSpecific("print")
darin@apple.com's avatar
darin@apple.com committed
770
        ? defaultPrintStyle : defaultStyle;
bdakin's avatar
bdakin committed
771
    matchRules(userAgentStyleSheet, firstUARule, lastUARule);
772

bdakin's avatar
bdakin committed
773
    // In quirks mode, we match rules from the quirks user agent sheet.
darin@apple.com's avatar
darin@apple.com committed
774
775
    if (!m_strictParsing)
        matchRules(defaultQuirksStyle, firstUARule, lastUARule);
776
        
bdakin's avatar
bdakin committed
777
    // If we're in view source mode, then we match rules from the view source style sheet.
ggaren's avatar
ggaren committed
778
    if (m_document->frame() && m_document->frame()->inViewSourceMode())
darin@apple.com's avatar
darin@apple.com committed
779
        matchRules(defaultViewSourceStyle, firstUARule, lastUARule);
780
781
782
783
}

// If resolveForRootDefault is true, style based on user agent style sheet only. This is used in media queries, where
// relative units are interpreted according to document root element style, styled only with UA stylesheet
hyatt's avatar
hyatt committed
784

785
RenderStyle* CSSStyleSelector::styleForElement(Element* e, RenderStyle* defaultParent, bool allowSharing, bool resolveForRootDefault)
786
{
787
788
789
    // Once an element has a renderer, we don't try to destroy it, since otherwise the renderer
    // will vanish if a style recalc happens during loading.
    if (allowSharing && !e->document()->haveStylesheetsLoaded() && !e->renderer()) {
darin@apple.com's avatar
darin@apple.com committed
790
791
792
793
794
        if (!s_styleNotYetAvailable) {
            s_styleNotYetAvailable = ::new RenderStyle;
            s_styleNotYetAvailable->ref();
            s_styleNotYetAvailable->setDisplay(NONE);
            s_styleNotYetAvailable->font().update(m_fontSelector);
795
        }
darin@apple.com's avatar
darin@apple.com committed
796
        s_styleNotYetAvailable->ref();
antti's avatar
antti committed
797
        e->document()->setHasNodesWithPlaceholderStyle();
darin@apple.com's avatar
darin@apple.com committed
798
        return s_styleNotYetAvailable;
799
800
    }
    
801
    initElementAndPseudoState(e);
802
    if (allowSharing) {
803
        m_style = locateSharedStyle();
804
#ifdef STYLE_SHARING_STATS
805
        fraction += m_style != 0;
806
807
808
        total++;
        printf("Sharing %d out of %d\n", fraction, total);
#endif
809
810
811
        if (m_style) {
            m_style->ref();
            return m_style;
812
        }
813
    }
814
    initForStyleResolve(e, defaultParent);
kocienda's avatar
kocienda committed
815

816
    if (resolveForRootDefault) {
817
        m_style = ::new RenderStyle();
818
819
        // don't ref, because we want to delete this, but we cannot unref it
    } else {
820
821
        m_style = new (e->document()->renderArena()) RenderStyle();
        m_style->ref();
822
    }
823
824
    if (m_parentStyle)
        m_style->inheritFrom(m_parentStyle);
825
    else
826
        m_parentStyle = m_style;
hyatt's avatar
hyatt committed
827

rwlbuis@webkit.org's avatar
rwlbuis@webkit.org committed
828
#if ENABLE(SVG)
darin@apple.com's avatar
darin@apple.com committed
829
830
    static bool loadedSVGUserAgentSheet;
    if (e->isSVGElement() && !loadedSVGUserAgentSheet) {