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-2014 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 * Copyright (C) 2012 Google Inc. All rights reserved.
12 *
13 * This library is free software; you can redistribute it and/or
14 * modify it under the terms of the GNU Library General Public
15 * License as published by the Free Software Foundation; either
16 * version 2 of the License, or (at your option) any later version.
17 *
18 * This library is distributed in the hope that it will be useful,
19 * but WITHOUT ANY WARRANTY; without even the implied warranty of
20 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
21 * Library General Public License for more details.
22 *
23 * You should have received a copy of the GNU Library General Public License
24 * along with this library; see the file COPYING.LIB.  If not, write to
25 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
26 * Boston, MA 02110-1301, USA.
27 */
28
29#include "config.h"
30#include "RuleSet.h"
31
32#include "CSSFontSelector.h"
33#include "CSSSelector.h"
34#include "CSSSelectorList.h"
35#include "HTMLNames.h"
36#include "MediaQueryEvaluator.h"
37#include "SecurityOrigin.h"
38#include "SelectorChecker.h"
39#include "SelectorFilter.h"
40#include "StyleResolver.h"
41#include "StyleRule.h"
42#include "StyleRuleImport.h"
43#include "StyleSheetContents.h"
44#include "WebKitCSSKeyframesRule.h"
45
46#if ENABLE(VIDEO_TRACK)
47#include "TextTrackCue.h"
48#endif
49
50namespace WebCore {
51
52using namespace HTMLNames;
53
54// -----------------------------------------------------------------
55
56static inline bool isSelectorMatchingHTMLBasedOnRuleHash(const CSSSelector& selector)
57{
58    if (selector.tagHistory())
59        return false;
60
61    if (selector.m_match == CSSSelector::Tag) {
62        const AtomicString& selectorNamespace = selector.tagQName().namespaceURI();
63        return selectorNamespace == starAtom || selectorNamespace == xhtmlNamespaceURI;
64    }
65    if (SelectorChecker::isCommonPseudoClassSelector(&selector))
66        return true;
67    return selector.m_match == CSSSelector::Id || selector.m_match == CSSSelector::Class;
68}
69
70static bool selectorCanMatchPseudoElement(const CSSSelector& rootSelector)
71{
72    const CSSSelector* selector = &rootSelector;
73    do {
74        if (selector->matchesPseudoElement())
75            return true;
76
77        if (const CSSSelectorList* selectorList = selector->selectorList()) {
78            for (const CSSSelector* subSelector = selectorList->first(); subSelector; subSelector = CSSSelectorList::next(subSelector)) {
79                if (selectorCanMatchPseudoElement(*subSelector))
80                    return true;
81            }
82        }
83
84        selector = selector->tagHistory();
85    } while (selector);
86    return false;
87}
88
89static inline bool selectorListContainsAttributeSelector(const CSSSelector* selector)
90{
91    const CSSSelectorList* selectorList = selector->selectorList();
92    if (!selectorList)
93        return false;
94    for (const CSSSelector* selector = selectorList->first(); selector; selector = CSSSelectorList::next(selector)) {
95        for (const CSSSelector* component = selector; component; component = component->tagHistory()) {
96            if (component->isAttributeSelector())
97                return true;
98        }
99    }
100    return false;
101}
102
103static inline bool isCommonAttributeSelectorAttribute(const QualifiedName& attribute)
104{
105    // These are explicitly tested for equality in canShareStyleWithElement.
106    return attribute == typeAttr || attribute == readonlyAttr;
107}
108
109static inline bool containsUncommonAttributeSelector(const CSSSelector* selector)
110{
111    for (; selector; selector = selector->tagHistory()) {
112        // Allow certain common attributes (used in the default style) in the selectors that match the current element.
113        if (selector->isAttributeSelector() && !isCommonAttributeSelectorAttribute(selector->attribute()))
114            return true;
115        if (selectorListContainsAttributeSelector(selector))
116            return true;
117        if (selector->relation() != CSSSelector::SubSelector) {
118            selector = selector->tagHistory();
119            break;
120        }
121    }
122
123    for (; selector; selector = selector->tagHistory()) {
124        if (selector->isAttributeSelector())
125            return true;
126        if (selectorListContainsAttributeSelector(selector))
127            return true;
128    }
129    return false;
130}
131
132static inline PropertyWhitelistType determinePropertyWhitelistType(const AddRuleFlags addRuleFlags, const CSSSelector* selector)
133{
134    if (addRuleFlags & RuleIsInRegionRule)
135        return PropertyWhitelistRegion;
136#if ENABLE(VIDEO_TRACK)
137    for (const CSSSelector* component = selector; component; component = component->tagHistory()) {
138        if (component->m_match == CSSSelector::PseudoElement && (component->pseudoElementType() == CSSSelector::PseudoElementCue || component->value() == TextTrackCue::cueShadowPseudoId()))
139            return PropertyWhitelistCue;
140    }
141#else
142    UNUSED_PARAM(selector);
143#endif
144    return PropertyWhitelistNone;
145}
146
147RuleData::RuleData(StyleRule* rule, unsigned selectorIndex, unsigned position, AddRuleFlags addRuleFlags)
148    : m_rule(rule)
149    , m_selectorIndex(selectorIndex)
150    , m_hasDocumentSecurityOrigin(addRuleFlags & RuleHasDocumentSecurityOrigin)
151    , m_position(position)
152    , m_specificity(selector()->specificity())
153    , m_hasRightmostSelectorMatchingHTMLBasedOnRuleHash(isSelectorMatchingHTMLBasedOnRuleHash(*selector()))
154    , m_canMatchPseudoElement(selectorCanMatchPseudoElement(*selector()))
155    , m_containsUncommonAttributeSelector(WebCore::containsUncommonAttributeSelector(selector()))
156    , m_linkMatchType(SelectorChecker::determineLinkMatchType(selector()))
157    , m_propertyWhitelistType(determinePropertyWhitelistType(addRuleFlags, selector()))
158#if ENABLE(CSS_SELECTOR_JIT) && CSS_SELECTOR_JIT_PROFILING
159    , m_compiledSelectorUseCount(0)
160#endif
161{
162    ASSERT(m_position == position);
163    ASSERT(m_selectorIndex == selectorIndex);
164    SelectorFilter::collectIdentifierHashes(selector(), m_descendantSelectorIdentifierHashes, maximumIdentifierCount);
165}
166
167static void collectFeaturesFromRuleData(RuleFeatureSet& features, const RuleData& ruleData)
168{
169    bool foundSiblingSelector = false;
170    for (const CSSSelector* selector = ruleData.selector(); selector; selector = selector->tagHistory()) {
171        features.collectFeaturesFromSelector(selector);
172
173        if (const CSSSelectorList* selectorList = selector->selectorList()) {
174            for (const CSSSelector* subSelector = selectorList->first(); subSelector; subSelector = CSSSelectorList::next(subSelector)) {
175                if (!foundSiblingSelector && selector->isSiblingSelector())
176                    foundSiblingSelector = true;
177                features.collectFeaturesFromSelector(subSelector);
178            }
179        } else if (!foundSiblingSelector && selector->isSiblingSelector())
180            foundSiblingSelector = true;
181    }
182    if (foundSiblingSelector)
183        features.siblingRules.append(RuleFeature(ruleData.rule(), ruleData.selectorIndex(), ruleData.hasDocumentSecurityOrigin()));
184    if (ruleData.containsUncommonAttributeSelector())
185        features.uncommonAttributeRules.append(RuleFeature(ruleData.rule(), ruleData.selectorIndex(), ruleData.hasDocumentSecurityOrigin()));
186}
187
188void RuleSet::addToRuleSet(AtomicStringImpl* key, AtomRuleMap& map, const RuleData& ruleData)
189{
190    if (!key)
191        return;
192    std::unique_ptr<Vector<RuleData>>& rules = map.add(key, nullptr).iterator->value;
193    if (!rules)
194        rules = std::make_unique<Vector<RuleData>>();
195    rules->append(ruleData);
196}
197
198static unsigned rulesCountForName(const RuleSet::AtomRuleMap& map, AtomicStringImpl* name)
199{
200    if (const Vector<RuleData>* rules = map.get(name))
201        return rules->size();
202    return 0;
203}
204
205void RuleSet::addRule(StyleRule* rule, unsigned selectorIndex, AddRuleFlags addRuleFlags)
206{
207    RuleData ruleData(rule, selectorIndex, m_ruleCount++, addRuleFlags);
208    collectFeaturesFromRuleData(m_features, ruleData);
209
210    unsigned classBucketSize = 0;
211    const CSSSelector* tagSelector = nullptr;
212    const CSSSelector* classSelector = nullptr;
213    const CSSSelector* linkSelector = nullptr;
214    const CSSSelector* focusSelector = nullptr;
215    const CSSSelector* selector = ruleData.selector();
216    do {
217        if (selector->m_match == CSSSelector::Id) {
218            addToRuleSet(selector->value().impl(), m_idRules, ruleData);
219            return;
220        }
221
222#if ENABLE(VIDEO_TRACK)
223        if (selector->m_match == CSSSelector::PseudoElement && selector->pseudoElementType() == CSSSelector::PseudoElementCue) {
224            m_cuePseudoRules.append(ruleData);
225            return;
226        }
227#endif
228
229        if (selector->isCustomPseudoElement()) {
230            addToRuleSet(selector->value().impl(), m_shadowPseudoElementRules, ruleData);
231            return;
232        }
233
234        if (selector->m_match == CSSSelector::Class) {
235            AtomicStringImpl* className = selector->value().impl();
236            if (!classSelector) {
237                classSelector = selector;
238                classBucketSize = rulesCountForName(m_classRules, className);
239            } else if (classBucketSize) {
240                unsigned newClassBucketSize = rulesCountForName(m_classRules, className);
241                if (newClassBucketSize < classBucketSize) {
242                    classSelector = selector;
243                    classBucketSize = newClassBucketSize;
244                }
245            }
246        }
247
248        if (selector->m_match == CSSSelector::Tag && selector->tagQName().localName() != starAtom)
249            tagSelector = selector;
250
251        if (SelectorChecker::isCommonPseudoClassSelector(selector)) {
252            switch (selector->pseudoClassType()) {
253            case CSSSelector::PseudoClassLink:
254            case CSSSelector::PseudoClassVisited:
255            case CSSSelector::PseudoClassAnyLink:
256                linkSelector = selector;
257                break;
258            case CSSSelector::PseudoClassFocus:
259                focusSelector = selector;
260                break;
261            default:
262                ASSERT_NOT_REACHED();
263            }
264        }
265
266        if (selector->relation() != CSSSelector::SubSelector)
267            break;
268        selector = selector->tagHistory();
269    } while (selector);
270
271    if (classSelector) {
272        addToRuleSet(classSelector->value().impl(), m_classRules, ruleData);
273        return;
274    }
275
276    if (linkSelector) {
277        m_linkPseudoClassRules.append(ruleData);
278        return;
279    }
280
281    if (focusSelector) {
282        m_focusPseudoClassRules.append(ruleData);
283        return;
284    }
285
286    if (tagSelector) {
287        addToRuleSet(tagSelector->tagQName().localName().impl(), m_tagRules, ruleData);
288        return;
289    }
290
291    // If we didn't find a specialized map to stick it in, file under universal rules.
292    m_universalRules.append(ruleData);
293}
294
295void RuleSet::addPageRule(StyleRulePage* rule)
296{
297    m_pageRules.append(rule);
298}
299
300void RuleSet::addRegionRule(StyleRuleRegion* regionRule, bool hasDocumentSecurityOrigin)
301{
302    auto regionRuleSet = std::make_unique<RuleSet>();
303    // The region rule set should take into account the position inside the parent rule set.
304    // Otherwise, the rules inside region block might be incorrectly positioned before other similar rules from
305    // the stylesheet that contains the region block.
306    regionRuleSet->m_ruleCount = m_ruleCount;
307
308    // Collect the region rules into a rule set
309    // FIXME: Should this add other types of rules? (i.e. use addChildRules() directly?)
310    const Vector<RefPtr<StyleRuleBase>>& childRules = regionRule->childRules();
311    AddRuleFlags addRuleFlags = hasDocumentSecurityOrigin ? RuleHasDocumentSecurityOrigin : RuleHasNoSpecialState;
312    addRuleFlags = static_cast<AddRuleFlags>(addRuleFlags | RuleIsInRegionRule);
313    for (unsigned i = 0; i < childRules.size(); ++i) {
314        StyleRuleBase* regionStylingRule = childRules[i].get();
315        if (regionStylingRule->isStyleRule())
316            regionRuleSet->addStyleRule(static_cast<StyleRule*>(regionStylingRule), addRuleFlags);
317    }
318    // Update the "global" rule count so that proper order is maintained
319    m_ruleCount = regionRuleSet->m_ruleCount;
320
321    m_regionSelectorsAndRuleSets.append(RuleSetSelectorPair(regionRule->selectorList().first(), WTF::move(regionRuleSet)));
322}
323
324void RuleSet::addChildRules(const Vector<RefPtr<StyleRuleBase>>& rules, const MediaQueryEvaluator& medium, StyleResolver* resolver, bool hasDocumentSecurityOrigin, AddRuleFlags addRuleFlags)
325{
326    for (unsigned i = 0; i < rules.size(); ++i) {
327        StyleRuleBase* rule = rules[i].get();
328
329        if (rule->isStyleRule()) {
330            StyleRule* styleRule = static_cast<StyleRule*>(rule);
331            addStyleRule(styleRule, addRuleFlags);
332        } else if (rule->isPageRule())
333            addPageRule(static_cast<StyleRulePage*>(rule));
334        else if (rule->isMediaRule()) {
335            StyleRuleMedia* mediaRule = static_cast<StyleRuleMedia*>(rule);
336            if ((!mediaRule->mediaQueries() || medium.eval(mediaRule->mediaQueries(), resolver)))
337                addChildRules(mediaRule->childRules(), medium, resolver, hasDocumentSecurityOrigin, addRuleFlags);
338        } else if (rule->isFontFaceRule() && resolver) {
339            // Add this font face to our set.
340            const StyleRuleFontFace* fontFaceRule = static_cast<StyleRuleFontFace*>(rule);
341            resolver->fontSelector()->addFontFaceRule(fontFaceRule);
342            resolver->invalidateMatchedPropertiesCache();
343        } else if (rule->isKeyframesRule() && resolver) {
344            resolver->addKeyframeStyle(static_cast<StyleRuleKeyframes*>(rule));
345        }
346#if ENABLE(CSS_REGIONS)
347        else if (rule->isRegionRule() && resolver) {
348            addRegionRule(static_cast<StyleRuleRegion*>(rule), hasDocumentSecurityOrigin);
349        }
350#endif
351#if ENABLE(CSS_DEVICE_ADAPTATION)
352        else if (rule->isViewportRule() && resolver) {
353            resolver->viewportStyleResolver()->addViewportRule(static_cast<StyleRuleViewport*>(rule));
354        }
355#endif
356#if ENABLE(CSS3_CONDITIONAL_RULES)
357        else if (rule->isSupportsRule() && static_cast<StyleRuleSupports*>(rule)->conditionIsSupported())
358            addChildRules(static_cast<StyleRuleSupports*>(rule)->childRules(), medium, resolver, hasDocumentSecurityOrigin, addRuleFlags);
359#endif
360    }
361}
362
363void RuleSet::addRulesFromSheet(StyleSheetContents* sheet, const MediaQueryEvaluator& medium, StyleResolver* resolver)
364{
365    ASSERT(sheet);
366
367    const Vector<RefPtr<StyleRuleImport>>& importRules = sheet->importRules();
368    for (unsigned i = 0; i < importRules.size(); ++i) {
369        StyleRuleImport* importRule = importRules[i].get();
370        if (importRule->styleSheet() && (!importRule->mediaQueries() || medium.eval(importRule->mediaQueries(), resolver)))
371            addRulesFromSheet(importRule->styleSheet(), medium, resolver);
372    }
373
374    bool hasDocumentSecurityOrigin = resolver && resolver->document().securityOrigin()->canRequest(sheet->baseURL());
375    AddRuleFlags addRuleFlags = static_cast<AddRuleFlags>((hasDocumentSecurityOrigin ? RuleHasDocumentSecurityOrigin : 0));
376
377    addChildRules(sheet->childRules(), medium, resolver, hasDocumentSecurityOrigin, addRuleFlags);
378
379    if (m_autoShrinkToFitEnabled)
380        shrinkToFit();
381}
382
383void RuleSet::addStyleRule(StyleRule* rule, AddRuleFlags addRuleFlags)
384{
385    for (size_t selectorIndex = 0; selectorIndex != notFound; selectorIndex = rule->selectorList().indexOfNextSelectorAfter(selectorIndex))
386        addRule(rule, selectorIndex, addRuleFlags);
387}
388
389static inline void shrinkMapVectorsToFit(RuleSet::AtomRuleMap& map)
390{
391    RuleSet::AtomRuleMap::iterator end = map.end();
392    for (RuleSet::AtomRuleMap::iterator it = map.begin(); it != end; ++it)
393        it->value->shrinkToFit();
394}
395
396void RuleSet::shrinkToFit()
397{
398    shrinkMapVectorsToFit(m_idRules);
399    shrinkMapVectorsToFit(m_classRules);
400    shrinkMapVectorsToFit(m_tagRules);
401    shrinkMapVectorsToFit(m_shadowPseudoElementRules);
402    m_linkPseudoClassRules.shrinkToFit();
403#if ENABLE(VIDEO_TRACK)
404    m_cuePseudoRules.shrinkToFit();
405#endif
406    m_focusPseudoClassRules.shrinkToFit();
407    m_universalRules.shrinkToFit();
408    m_pageRules.shrinkToFit();
409}
410
411} // namespace WebCore
412