f188ae0996c53385457c0e8420b6dbc766b06f45
[WebKit-https.git] / Source / WebCore / css / RuleSet.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-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 "CSSKeyframesRule.h"
34 #include "CSSSelector.h"
35 #include "CSSSelectorList.h"
36 #include "HTMLNames.h"
37 #include "MediaQueryEvaluator.h"
38 #include "SecurityOrigin.h"
39 #include "SelectorChecker.h"
40 #include "SelectorFilter.h"
41 #include "StyleResolver.h"
42 #include "StyleRule.h"
43 #include "StyleRuleImport.h"
44 #include "StyleSheetContents.h"
45 #include "ViewportStyleResolver.h"
46
47 #if ENABLE(VIDEO_TRACK)
48 #include "TextTrackCue.h"
49 #endif
50
51 namespace WebCore {
52
53 using namespace HTMLNames;
54
55 // -----------------------------------------------------------------
56
57 static inline MatchBasedOnRuleHash computeMatchBasedOnRuleHash(const CSSSelector& selector)
58 {
59     if (selector.tagHistory())
60         return MatchBasedOnRuleHash::None;
61
62     if (selector.match() == CSSSelector::Tag) {
63         const QualifiedName& tagQualifiedName = selector.tagQName();
64         const AtomicString& selectorNamespace = tagQualifiedName.namespaceURI();
65         if (selectorNamespace == starAtom() || selectorNamespace == xhtmlNamespaceURI) {
66             if (tagQualifiedName == anyQName())
67                 return MatchBasedOnRuleHash::Universal;
68             return MatchBasedOnRuleHash::ClassC;
69         }
70         return MatchBasedOnRuleHash::None;
71     }
72     if (SelectorChecker::isCommonPseudoClassSelector(&selector))
73         return MatchBasedOnRuleHash::ClassB;
74     if (selector.match() == CSSSelector::Id)
75         return MatchBasedOnRuleHash::ClassA;
76     if (selector.match() == CSSSelector::Class)
77         return MatchBasedOnRuleHash::ClassB;
78     return MatchBasedOnRuleHash::None;
79 }
80
81 static bool selectorCanMatchPseudoElement(const CSSSelector& rootSelector)
82 {
83     const CSSSelector* selector = &rootSelector;
84     do {
85         if (selector->matchesPseudoElement())
86             return true;
87
88         if (const CSSSelectorList* selectorList = selector->selectorList()) {
89             for (const CSSSelector* subSelector = selectorList->first(); subSelector; subSelector = CSSSelectorList::next(subSelector)) {
90                 if (selectorCanMatchPseudoElement(*subSelector))
91                     return true;
92             }
93         }
94
95         selector = selector->tagHistory();
96     } while (selector);
97     return false;
98 }
99
100 static inline bool isCommonAttributeSelectorAttribute(const QualifiedName& attribute)
101 {
102     // These are explicitly tested for equality in canShareStyleWithElement.
103     return attribute == typeAttr || attribute == readonlyAttr;
104 }
105
106 static bool containsUncommonAttributeSelector(const CSSSelector& rootSelector, bool matchesRightmostElement)
107 {
108     const CSSSelector* selector = &rootSelector;
109     do {
110         if (selector->isAttributeSelector()) {
111             // FIXME: considering non-rightmost simple selectors is necessary because of the style sharing of cousins.
112             // It is a primitive solution which disable a lot of style sharing on pages that rely on attributes for styling.
113             // We should investigate better ways of doing this.
114             if (!isCommonAttributeSelectorAttribute(selector->attribute()) || !matchesRightmostElement)
115                 return true;
116         }
117
118         if (const CSSSelectorList* selectorList = selector->selectorList()) {
119             for (const CSSSelector* subSelector = selectorList->first(); subSelector; subSelector = CSSSelectorList::next(subSelector)) {
120                 if (containsUncommonAttributeSelector(*subSelector, matchesRightmostElement))
121                     return true;
122             }
123         }
124
125         if (selector->relation() != CSSSelector::Subselector)
126             matchesRightmostElement = false;
127
128         selector = selector->tagHistory();
129     } while (selector);
130     return false;
131 }
132
133 static inline bool containsUncommonAttributeSelector(const CSSSelector& rootSelector)
134 {
135     return containsUncommonAttributeSelector(rootSelector, true);
136 }
137
138 static inline PropertyWhitelistType determinePropertyWhitelistType(const CSSSelector* selector)
139 {
140     for (const CSSSelector* component = selector; component; component = component->tagHistory()) {
141 #if ENABLE(VIDEO_TRACK)
142         if (component->match() == CSSSelector::PseudoElement && (component->pseudoElementType() == CSSSelector::PseudoElementCue || component->value() == TextTrackCue::cueShadowPseudoId()))
143             return PropertyWhitelistCue;
144 #endif
145         if (component->match() == CSSSelector::PseudoElement && component->pseudoElementType() == CSSSelector::PseudoElementMarker)
146             return PropertyWhitelistMarker;
147     }
148     return PropertyWhitelistNone;
149 }
150
151 RuleData::RuleData(StyleRule* rule, unsigned selectorIndex, unsigned position, AddRuleFlags addRuleFlags)
152     : m_rule(rule)
153     , m_selectorIndex(selectorIndex)
154     , m_hasDocumentSecurityOrigin(addRuleFlags & RuleHasDocumentSecurityOrigin)
155     , m_position(position)
156     , m_matchBasedOnRuleHash(static_cast<unsigned>(computeMatchBasedOnRuleHash(*selector())))
157     , m_canMatchPseudoElement(selectorCanMatchPseudoElement(*selector()))
158     , m_containsUncommonAttributeSelector(WebCore::containsUncommonAttributeSelector(*selector()))
159     , m_linkMatchType(SelectorChecker::determineLinkMatchType(selector()))
160     , m_propertyWhitelistType(determinePropertyWhitelistType(selector()))
161     , m_descendantSelectorIdentifierHashes(SelectorFilter::collectHashes(*selector()))
162 #if ENABLE(CSS_SELECTOR_JIT) && CSS_SELECTOR_JIT_PROFILING
163     , m_compiledSelectorUseCount(0)
164 #endif
165 {
166     ASSERT(m_position == position);
167     ASSERT(m_selectorIndex == selectorIndex);
168 }
169
170 RuleSet::RuleSet() = default;
171
172 RuleSet::~RuleSet() = default;
173
174 void RuleSet::addToRuleSet(const AtomicString& key, AtomRuleMap& map, const RuleData& ruleData)
175 {
176     if (key.isNull())
177         return;
178     auto& rules = map.add(key, nullptr).iterator->value;
179     if (!rules)
180         rules = std::make_unique<RuleDataVector>();
181     rules->append(ruleData);
182 }
183
184 static unsigned rulesCountForName(const RuleSet::AtomRuleMap& map, const AtomicString& name)
185 {
186     if (const auto* rules = map.get(name))
187         return rules->size();
188     return 0;
189 }
190
191 static bool isHostSelectorMatchingInShadowTree(const CSSSelector& startSelector)
192 {
193     auto* leftmostSelector = &startSelector;
194     bool hasDescendantOrChildRelation = false;
195     while (auto* previous = leftmostSelector->tagHistory()) {
196         hasDescendantOrChildRelation = leftmostSelector->hasDescendantOrChildRelation();
197         leftmostSelector = previous;
198     }
199     if (!hasDescendantOrChildRelation)
200         return false;
201
202     return leftmostSelector->match() == CSSSelector::PseudoClass && leftmostSelector->pseudoClassType() == CSSSelector::PseudoClassHost;
203 }
204
205 void RuleSet::addRule(StyleRule* rule, unsigned selectorIndex, AddRuleFlags addRuleFlags)
206 {
207     RuleData ruleData(rule, selectorIndex, m_ruleCount++, addRuleFlags);
208     m_features.collectFeatures(ruleData);
209
210     unsigned classBucketSize = 0;
211     const CSSSelector* idSelector = nullptr;
212     const CSSSelector* tagSelector = nullptr;
213     const CSSSelector* classSelector = nullptr;
214     const CSSSelector* linkSelector = nullptr;
215     const CSSSelector* focusSelector = nullptr;
216     const CSSSelector* hostPseudoClassSelector = nullptr;
217     const CSSSelector* customPseudoElementSelector = nullptr;
218     const CSSSelector* slottedPseudoElementSelector = nullptr;
219 #if ENABLE(VIDEO_TRACK)
220     const CSSSelector* cuePseudoElementSelector = nullptr;
221 #endif
222     const CSSSelector* selector = ruleData.selector();
223     do {
224         switch (selector->match()) {
225         case CSSSelector::Id:
226             idSelector = selector;
227             break;
228         case CSSSelector::Class: {
229             auto& className = selector->value();
230             if (!classSelector) {
231                 classSelector = selector;
232                 classBucketSize = rulesCountForName(m_classRules, className);
233             } else if (classBucketSize) {
234                 unsigned newClassBucketSize = rulesCountForName(m_classRules, className);
235                 if (newClassBucketSize < classBucketSize) {
236                     classSelector = selector;
237                     classBucketSize = newClassBucketSize;
238                 }
239             }
240             break;
241         }
242         case CSSSelector::Tag:
243             if (selector->tagQName().localName() != starAtom())
244                 tagSelector = selector;
245             break;
246         case CSSSelector::PseudoElement:
247             switch (selector->pseudoElementType()) {
248             case CSSSelector::PseudoElementUserAgentCustom:
249             case CSSSelector::PseudoElementWebKitCustom:
250             case CSSSelector::PseudoElementWebKitCustomLegacyPrefixed:
251                 customPseudoElementSelector = selector;
252                 break;
253             case CSSSelector::PseudoElementSlotted:
254                 slottedPseudoElementSelector = selector;
255                 break;
256 #if ENABLE(VIDEO_TRACK)
257             case CSSSelector::PseudoElementCue:
258                 cuePseudoElementSelector = selector;
259                 break;
260 #endif
261             default:
262                 break;
263             }
264             break;
265         case CSSSelector::PseudoClass:
266             switch (selector->pseudoClassType()) {
267             case CSSSelector::PseudoClassLink:
268             case CSSSelector::PseudoClassVisited:
269             case CSSSelector::PseudoClassAnyLink:
270             case CSSSelector::PseudoClassAnyLinkDeprecated:
271                 linkSelector = selector;
272                 break;
273             case CSSSelector::PseudoClassFocus:
274                 focusSelector = selector;
275                 break;
276             case CSSSelector::PseudoClassHost:
277                 hostPseudoClassSelector = selector;
278                 break;
279             default:
280                 break;
281             }
282             break;
283         case CSSSelector::Unknown:
284         case CSSSelector::Exact:
285         case CSSSelector::Set:
286         case CSSSelector::List:
287         case CSSSelector::Hyphen:
288         case CSSSelector::Contain:
289         case CSSSelector::Begin:
290         case CSSSelector::End:
291         case CSSSelector::PagePseudoClass:
292             break;
293         }
294         if (selector->relation() != CSSSelector::Subselector)
295             break;
296         selector = selector->tagHistory();
297     } while (selector);
298
299 #if ENABLE(VIDEO_TRACK)
300     if (cuePseudoElementSelector) {
301         m_cuePseudoRules.append(ruleData);
302         return;
303     }
304 #endif
305
306     if (slottedPseudoElementSelector) {
307         // ::slotted pseudo elements work accross shadow boundary making filtering difficult.
308         ruleData.disableSelectorFiltering();
309         m_slottedPseudoElementRules.append(ruleData);
310         return;
311     }
312
313     if (customPseudoElementSelector) {
314         // FIXME: Custom pseudo elements are handled by the shadow tree's selector filter. It doesn't know about the main DOM.
315         ruleData.disableSelectorFiltering();
316         addToRuleSet(customPseudoElementSelector->value(), m_shadowPseudoElementRules, ruleData);
317         return;
318     }
319
320     if (!m_hasHostPseudoClassRulesMatchingInShadowTree)
321         m_hasHostPseudoClassRulesMatchingInShadowTree = isHostSelectorMatchingInShadowTree(*ruleData.selector());
322
323     if (hostPseudoClassSelector) {
324         m_hostPseudoClassRules.append(ruleData);
325         return;
326     }
327
328     if (idSelector) {
329         addToRuleSet(idSelector->value(), m_idRules, ruleData);
330         return;
331     }
332
333     if (classSelector) {
334         addToRuleSet(classSelector->value(), m_classRules, ruleData);
335         return;
336     }
337
338     if (linkSelector) {
339         m_linkPseudoClassRules.append(ruleData);
340         return;
341     }
342
343     if (focusSelector) {
344         m_focusPseudoClassRules.append(ruleData);
345         return;
346     }
347
348     if (tagSelector) {
349         addToRuleSet(tagSelector->tagQName().localName(), m_tagLocalNameRules, ruleData);
350         addToRuleSet(tagSelector->tagLowercaseLocalName(), m_tagLowercaseLocalNameRules, ruleData);
351         return;
352     }
353
354     // If we didn't find a specialized map to stick it in, file under universal rules.
355     m_universalRules.append(ruleData);
356 }
357
358 void RuleSet::addPageRule(StyleRulePage* rule)
359 {
360     m_pageRules.append(rule);
361 }
362
363 void RuleSet::addChildRules(const Vector<RefPtr<StyleRuleBase>>& rules, const MediaQueryEvaluator& medium, StyleResolver* resolver, bool hasDocumentSecurityOrigin, bool isInitiatingElementInUserAgentShadowTree, AddRuleFlags addRuleFlags)
364 {
365     for (auto& rule : rules) {
366         if (is<StyleRule>(*rule))
367             addStyleRule(downcast<StyleRule>(rule.get()), addRuleFlags);
368         else if (is<StyleRulePage>(*rule))
369             addPageRule(downcast<StyleRulePage>(rule.get()));
370         else if (is<StyleRuleMedia>(*rule)) {
371             auto& mediaRule = downcast<StyleRuleMedia>(*rule);
372             if ((!mediaRule.mediaQueries() || medium.evaluate(*mediaRule.mediaQueries(), resolver)))
373                 addChildRules(mediaRule.childRules(), medium, resolver, hasDocumentSecurityOrigin, isInitiatingElementInUserAgentShadowTree, addRuleFlags);
374         } else if (is<StyleRuleFontFace>(*rule) && resolver) {
375             // Add this font face to our set.
376             resolver->document().fontSelector().addFontFaceRule(downcast<StyleRuleFontFace>(*rule.get()), isInitiatingElementInUserAgentShadowTree);
377             resolver->invalidateMatchedPropertiesCache();
378         } else if (is<StyleRuleKeyframes>(*rule) && resolver)
379             resolver->addKeyframeStyle(downcast<StyleRuleKeyframes>(*rule));
380         else if (is<StyleRuleSupports>(*rule) && downcast<StyleRuleSupports>(*rule).conditionIsSupported())
381             addChildRules(downcast<StyleRuleSupports>(*rule).childRules(), medium, resolver, hasDocumentSecurityOrigin, isInitiatingElementInUserAgentShadowTree, addRuleFlags);
382 #if ENABLE(CSS_DEVICE_ADAPTATION)
383         else if (is<StyleRuleViewport>(*rule) && resolver) {
384             resolver->viewportStyleResolver()->addViewportRule(downcast<StyleRuleViewport>(rule.get()));
385         }
386 #endif
387     }
388 }
389
390 void RuleSet::addRulesFromSheet(StyleSheetContents& sheet, const MediaQueryEvaluator& medium, StyleResolver* resolver)
391 {
392     for (auto& rule : sheet.importRules()) {
393         if (rule->styleSheet() && (!rule->mediaQueries() || medium.evaluate(*rule->mediaQueries(), resolver)))
394             addRulesFromSheet(*rule->styleSheet(), medium, resolver);
395     }
396
397     bool hasDocumentSecurityOrigin = resolver && resolver->document().securityOrigin().canRequest(sheet.baseURL());
398     AddRuleFlags addRuleFlags = static_cast<AddRuleFlags>((hasDocumentSecurityOrigin ? RuleHasDocumentSecurityOrigin : 0));
399
400     // FIXME: Skip Content Security Policy check when stylesheet is in a user agent shadow tree.
401     // See <https://bugs.webkit.org/show_bug.cgi?id=146663>.
402     bool isInitiatingElementInUserAgentShadowTree = false;
403     addChildRules(sheet.childRules(), medium, resolver, hasDocumentSecurityOrigin, isInitiatingElementInUserAgentShadowTree, addRuleFlags);
404
405     if (m_autoShrinkToFitEnabled)
406         shrinkToFit();
407 }
408
409 void RuleSet::addStyleRule(StyleRule* rule, AddRuleFlags addRuleFlags)
410 {
411     for (size_t selectorIndex = 0; selectorIndex != notFound; selectorIndex = rule->selectorList().indexOfNextSelectorAfter(selectorIndex))
412         addRule(rule, selectorIndex, addRuleFlags);
413 }
414
415 bool RuleSet::hasShadowPseudoElementRules() const
416 {
417     if (!m_shadowPseudoElementRules.isEmpty())
418         return true;
419 #if ENABLE(VIDEO_TRACK)
420     if (!m_cuePseudoRules.isEmpty())
421         return true;
422 #endif
423     return false;
424 }
425
426 static inline void shrinkMapVectorsToFit(RuleSet::AtomRuleMap& map)
427 {
428     for (auto& vector : map.values())
429         vector->shrinkToFit();
430 }
431
432 void RuleSet::shrinkToFit()
433 {
434     shrinkMapVectorsToFit(m_idRules);
435     shrinkMapVectorsToFit(m_classRules);
436     shrinkMapVectorsToFit(m_tagLocalNameRules);
437     shrinkMapVectorsToFit(m_tagLowercaseLocalNameRules);
438     shrinkMapVectorsToFit(m_shadowPseudoElementRules);
439     m_linkPseudoClassRules.shrinkToFit();
440 #if ENABLE(VIDEO_TRACK)
441     m_cuePseudoRules.shrinkToFit();
442 #endif
443     m_hostPseudoClassRules.shrinkToFit();
444     m_slottedPseudoElementRules.shrinkToFit();
445     m_focusPseudoClassRules.shrinkToFit();
446     m_universalRules.shrinkToFit();
447     m_pageRules.shrinkToFit();
448     m_features.shrinkToFit();
449 }
450
451 } // namespace WebCore