1 /*
2 * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
3 * Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011 Apple Inc.
4 * All rights reserved.
5 *
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Library General Public
8 * License as published by the Free Software Foundation; either
9 * version 2 of the License, or (at your option) any later version.
10 *
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * Library General Public License for more details.
15 *
16 * You should have received a copy of the GNU Library General Public License
17 * along with this library; see the file COPYING.LIB. If not, write to
18 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
19 * Boston, MA 02110-1301, USA.
20 *
21 */
22
23 #ifndef THIRD_PARTY_BLINK_RENDERER_CORE_CSS_RULE_SET_H_
24 #define THIRD_PARTY_BLINK_RENDERER_CORE_CSS_RULE_SET_H_
25
26 #include "third_party/blink/renderer/core/core_export.h"
27 #include "third_party/blink/renderer/core/css/css_keyframes_rule.h"
28 #include "third_party/blink/renderer/core/css/media_query_evaluator.h"
29 #include "third_party/blink/renderer/core/css/resolver/media_query_result.h"
30 #include "third_party/blink/renderer/core/css/rule_feature_set.h"
31 #include "third_party/blink/renderer/core/css/style_rule.h"
32 #include "third_party/blink/renderer/platform/heap/collection_support/heap_linked_stack.h"
33 #include "third_party/blink/renderer/platform/wtf/forward.h"
34 #include "third_party/blink/renderer/platform/wtf/hash_map.h"
35 #include "third_party/blink/renderer/platform/wtf/size_assertions.h"
36
37 namespace blink {
38
39 using AddRuleFlags = unsigned;
40
41 enum AddRuleFlag {
42 kRuleHasNoSpecialState = 0,
43 kRuleHasDocumentSecurityOrigin = 1 << 0,
44 kRuleIsVisitedDependent = 1 << 1,
45 };
46
47 // Some CSS properties do not apply to certain pseudo-elements, and need to be
48 // ignored when resolving styles.
49 enum class ValidPropertyFilter : unsigned {
50 // All properties are valid. This is the common case.
51 kNoFilter,
52 // Defined in a ::cue pseudo-element scope. Only properties listed
53 // in https://w3c.github.io/webvtt/#the-cue-pseudo-element are valid.
54 kCue,
55 // Defined in a ::first-letter pseudo-element scope. Only properties listed in
56 // https://drafts.csswg.org/css-pseudo-4/#first-letter-styling are valid.
57 kFirstLetter,
58 // Defined in a ::marker pseudo-element scope. Only properties listed in
59 // https://drafts.csswg.org/css-pseudo-4/#marker-pseudo are valid.
60 kMarker,
61 // Defined in a highlight pseudo-element scope like ::selection and
62 // ::target-text. Only properties listed in
63 // https://drafts.csswg.org/css-pseudo-4/#highlight-styling are valid.
64 kHighlight,
65 };
66
67 class CSSSelector;
68 class MediaQueryEvaluator;
69 class StyleSheetContents;
70
71 class MinimalRuleData {
72 DISALLOW_NEW();
73
74 public:
MinimalRuleData(StyleRule * rule,unsigned selector_index,AddRuleFlags flags)75 MinimalRuleData(StyleRule* rule, unsigned selector_index, AddRuleFlags flags)
76 : rule_(rule), selector_index_(selector_index), flags_(flags) {}
77
78 void Trace(Visitor*) const;
79
80 Member<StyleRule> rule_;
81 unsigned selector_index_;
82 AddRuleFlags flags_;
83 };
84
85 } // namespace blink
86
WTF_ALLOW_MOVE_AND_INIT_WITH_MEM_FUNCTIONS(blink::MinimalRuleData)87 WTF_ALLOW_MOVE_AND_INIT_WITH_MEM_FUNCTIONS(blink::MinimalRuleData)
88
89 namespace blink {
90
91 // This is a wrapper around a StyleRule, pointing to one of the N complex
92 // selectors in the StyleRule. This allows us to treat each selector
93 // independently but still tie them back to the original StyleRule. If multiple
94 // selectors from a single rule match the same element we can see that as one
95 // match for the rule. It computes some information about the wrapped selector
96 // and makes it accessible cheaply.
97 class CORE_EXPORT RuleData : public GarbageCollected<RuleData> {
98 public:
99 static RuleData* MaybeCreate(StyleRule*,
100 unsigned selector_index,
101 unsigned position,
102 AddRuleFlags);
103
104 RuleData(StyleRule*,
105 unsigned selector_index,
106 unsigned position,
107 AddRuleFlags);
108
109 unsigned GetPosition() const { return position_; }
110 StyleRule* Rule() const { return rule_; }
111 const CSSSelector& Selector() const {
112 return rule_->SelectorList().SelectorAt(selector_index_);
113 }
114 unsigned SelectorIndex() const { return selector_index_; }
115
116 bool ContainsUncommonAttributeSelector() const {
117 return contains_uncommon_attribute_selector_;
118 }
119 unsigned Specificity() const { return specificity_; }
120 unsigned LinkMatchType() const { return link_match_type_; }
121 bool HasDocumentSecurityOrigin() const {
122 return has_document_security_origin_;
123 }
124 ValidPropertyFilter GetValidPropertyFilter(
125 bool is_matching_ua_rules = false) const {
126 return is_matching_ua_rules
127 ? ValidPropertyFilter::kNoFilter
128 : static_cast<ValidPropertyFilter>(valid_property_filter_);
129 }
130 // Try to balance between memory usage (there can be lots of RuleData objects)
131 // and good filtering performance.
132 static const unsigned kMaximumIdentifierCount = 4;
133 const unsigned* DescendantSelectorIdentifierHashes() const {
134 return descendant_selector_identifier_hashes_;
135 }
136
137 void Trace(Visitor*) const;
138
139 // This number is picked fairly arbitrary. If lowered, be aware that there
140 // might be sites and extensions using style rules with selector lists
141 // exceeding the number of simple selectors to fit in this bitfield.
142 // See https://crbug.com/312913 and https://crbug.com/704562
143 static constexpr size_t kSelectorIndexBits = 13;
144
145 // This number was picked fairly arbitrarily. We can probably lower it if we
146 // need to. Some simple testing showed <100,000 RuleData's on large sites.
147 static constexpr size_t kPositionBits = 18;
148
149 private:
150 Member<StyleRule> rule_;
151 unsigned selector_index_ : kSelectorIndexBits;
152 unsigned position_ : kPositionBits;
153 unsigned contains_uncommon_attribute_selector_ : 1;
154 // 32 bits above
155 unsigned specificity_ : 24;
156 unsigned link_match_type_ : 2;
157 unsigned has_document_security_origin_ : 1;
158 unsigned valid_property_filter_ : 3;
159 // 30 bits above
160 // Use plain array instead of a Vector to minimize memory overhead.
161 unsigned descendant_selector_identifier_hashes_[kMaximumIdentifierCount];
162 };
163
164 } // namespace blink
165
WTF_ALLOW_MOVE_AND_INIT_WITH_MEM_FUNCTIONS(blink::RuleData)166 WTF_ALLOW_MOVE_AND_INIT_WITH_MEM_FUNCTIONS(blink::RuleData)
167
168 namespace blink {
169
170 struct SameSizeAsRuleData {
171 DISALLOW_NEW();
172 Member<void*> a;
173 unsigned b;
174 unsigned c;
175 unsigned d[4];
176 };
177
178 ASSERT_SIZE(RuleData, SameSizeAsRuleData);
179
180 // Holds RuleData objects. It partitions them into various indexed groups,
181 // e.g. it stores separately rules that match against id, class, tag, shadow
182 // host, etc. It indexes these by some key where possible, e.g. rules that match
183 // against tag name are indexed by that tag. Rules that don't fall into a
184 // specific group are appended to the "universal" rules. The grouping is done to
185 // optimize finding what rules apply to an element under consideration by
186 // ElementRuleCollector::CollectMatchingRules.
187 class CORE_EXPORT RuleSet final : public GarbageCollected<RuleSet> {
188 public:
189 RuleSet() : rule_count_(0) {}
190 RuleSet(const RuleSet&) = delete;
191 RuleSet& operator=(const RuleSet&) = delete;
192
193 void AddRulesFromSheet(StyleSheetContents*,
194 const MediaQueryEvaluator&,
195 AddRuleFlags = kRuleHasNoSpecialState);
196 void AddStyleRule(StyleRule*, AddRuleFlags);
197 void AddRule(StyleRule*, unsigned selector_index, AddRuleFlags);
198
199 const RuleFeatureSet& Features() const { return features_; }
200
201 const HeapVector<Member<const RuleData>>* IdRules(
202 const AtomicString& key) const {
203 DCHECK(!pending_rules_);
204 return id_rules_.at(key);
205 }
206 const HeapVector<Member<const RuleData>>* ClassRules(
207 const AtomicString& key) const {
208 DCHECK(!pending_rules_);
209 return class_rules_.at(key);
210 }
211 const HeapVector<Member<const RuleData>>* TagRules(
212 const AtomicString& key) const {
213 DCHECK(!pending_rules_);
214 return tag_rules_.at(key);
215 }
216 const HeapVector<Member<const RuleData>>* ShadowPseudoElementRules(
217 const AtomicString& key) const {
218 DCHECK(!pending_rules_);
219 return shadow_pseudo_element_rules_.at(key);
220 }
221 const HeapVector<Member<const RuleData>>* LinkPseudoClassRules() const {
222 DCHECK(!pending_rules_);
223 return &link_pseudo_class_rules_;
224 }
225 const HeapVector<Member<const RuleData>>* CuePseudoRules() const {
226 DCHECK(!pending_rules_);
227 return &cue_pseudo_rules_;
228 }
229 const HeapVector<Member<const RuleData>>* FocusPseudoClassRules() const {
230 DCHECK(!pending_rules_);
231 return &focus_pseudo_class_rules_;
232 }
233 const HeapVector<Member<const RuleData>>*
234 SpatialNavigationInterestPseudoClassRules() const {
235 DCHECK(!pending_rules_);
236 return &spatial_navigation_interest_class_rules_;
237 }
238 const HeapVector<Member<const RuleData>>* UniversalRules() const {
239 DCHECK(!pending_rules_);
240 return &universal_rules_;
241 }
242 const HeapVector<Member<const RuleData>>* ShadowHostRules() const {
243 DCHECK(!pending_rules_);
244 return &shadow_host_rules_;
245 }
246 const HeapVector<Member<const RuleData>>* PartPseudoRules() const {
247 DCHECK(!pending_rules_);
248 return &part_pseudo_rules_;
249 }
250 const HeapVector<Member<const RuleData>>* VisitedDependentRules() const {
251 DCHECK(!pending_rules_);
252 return &visited_dependent_rules_;
253 }
254 const HeapVector<Member<StyleRulePage>>& PageRules() const {
255 DCHECK(!pending_rules_);
256 return page_rules_;
257 }
258 const HeapVector<Member<StyleRuleFontFace>>& FontFaceRules() const {
259 return font_face_rules_;
260 }
261 const HeapVector<Member<StyleRuleKeyframes>>& KeyframesRules() const {
262 return keyframes_rules_;
263 }
264 StyleRuleKeyframes* KeyframeStylesForAnimation(const AtomicString& name);
265 const HeapVector<Member<StyleRuleProperty>>& PropertyRules() const {
266 return property_rules_;
267 }
268 const HeapVector<Member<StyleRuleScrollTimeline>>& ScrollTimelineRules()
269 const {
270 return scroll_timeline_rules_;
271 }
272 const HeapVector<MinimalRuleData>& DeepCombinatorOrShadowPseudoRules() const {
273 return deep_combinator_or_shadow_pseudo_rules_;
274 }
275 const HeapVector<MinimalRuleData>& ContentPseudoElementRules() const {
276 return content_pseudo_element_rules_;
277 }
278 const HeapVector<MinimalRuleData>& SlottedPseudoElementRules() const {
279 return slotted_pseudo_element_rules_;
280 }
281
282 unsigned RuleCount() const { return rule_count_; }
283
284 void CompactRulesIfNeeded() {
285 if (!pending_rules_)
286 return;
287 CompactRules();
288 }
289
290 bool HasSlottedRules() const {
291 return !slotted_pseudo_element_rules_.IsEmpty();
292 }
293
294 bool HasV0BoundaryCrossingRules() const {
295 return !deep_combinator_or_shadow_pseudo_rules_.IsEmpty() ||
296 !content_pseudo_element_rules_.IsEmpty();
297 }
298
299 bool NeedsFullRecalcForRuleSetInvalidation() const {
300 return features_.NeedsFullRecalcForRuleSetInvalidation() ||
301 HasV0BoundaryCrossingRules();
302 }
303
304 bool DidMediaQueryResultsChange(const MediaQueryEvaluator& evaluator) const;
305
306 #ifndef NDEBUG
307 void Show() const;
308 #endif
309
310 void Trace(Visitor*) const;
311
312 private:
313 using PendingRuleMap =
314 HeapHashMap<AtomicString,
315 Member<HeapLinkedStack<Member<const RuleData>>>>;
316 using CompactRuleMap =
317 HeapHashMap<AtomicString, Member<HeapVector<Member<const RuleData>>>>;
318
319 void AddToRuleSet(const AtomicString& key, PendingRuleMap&, const RuleData*);
320 void AddPageRule(StyleRulePage*);
321 void AddViewportRule(StyleRuleViewport*);
322 void AddFontFaceRule(StyleRuleFontFace*);
323 void AddKeyframesRule(StyleRuleKeyframes*);
324 void AddPropertyRule(StyleRuleProperty*);
325 void AddScrollTimelineRule(StyleRuleScrollTimeline*);
326
327 bool MatchMediaForAddRules(const MediaQueryEvaluator& evaluator,
328 const MediaQuerySet* media_queries);
329 void AddChildRules(const HeapVector<Member<StyleRuleBase>>&,
330 const MediaQueryEvaluator& medium,
331 AddRuleFlags);
332 bool FindBestRuleSetAndAdd(const CSSSelector&, RuleData*);
333
334 void SortKeyframesRulesIfNeeded();
335
336 void CompactRules();
337 static void CompactPendingRules(PendingRuleMap&, CompactRuleMap&);
338
339 class PendingRuleMaps : public GarbageCollected<PendingRuleMaps> {
340 public:
341 PendingRuleMaps() = default;
342
343 PendingRuleMap id_rules;
344 PendingRuleMap class_rules;
345 PendingRuleMap tag_rules;
346 PendingRuleMap shadow_pseudo_element_rules;
347
348 void Trace(Visitor*) const;
349 };
350
351 PendingRuleMaps* EnsurePendingRules() {
352 if (!pending_rules_)
353 pending_rules_ = MakeGarbageCollected<PendingRuleMaps>();
354 return pending_rules_.Get();
355 }
356
357 CompactRuleMap id_rules_;
358 CompactRuleMap class_rules_;
359 CompactRuleMap tag_rules_;
360 CompactRuleMap shadow_pseudo_element_rules_;
361 HeapVector<Member<const RuleData>> link_pseudo_class_rules_;
362 HeapVector<Member<const RuleData>> cue_pseudo_rules_;
363 HeapVector<Member<const RuleData>> focus_pseudo_class_rules_;
364 HeapVector<Member<const RuleData>> spatial_navigation_interest_class_rules_;
365 HeapVector<Member<const RuleData>> universal_rules_;
366 HeapVector<Member<const RuleData>> shadow_host_rules_;
367 HeapVector<Member<const RuleData>> part_pseudo_rules_;
368 HeapVector<Member<const RuleData>> visited_dependent_rules_;
369 RuleFeatureSet features_;
370 HeapVector<Member<StyleRulePage>> page_rules_;
371 HeapVector<Member<StyleRuleFontFace>> font_face_rules_;
372 HeapVector<Member<StyleRuleKeyframes>> keyframes_rules_;
373 HeapVector<Member<StyleRuleProperty>> property_rules_;
374 HeapVector<Member<StyleRuleScrollTimeline>> scroll_timeline_rules_;
375 HeapVector<MinimalRuleData> deep_combinator_or_shadow_pseudo_rules_;
376 HeapVector<MinimalRuleData> content_pseudo_element_rules_;
377 HeapVector<MinimalRuleData> slotted_pseudo_element_rules_;
378 Vector<MediaQuerySetResult> media_query_set_results_;
379
380 bool keyframes_rules_sorted_ = true;
381
382 unsigned rule_count_;
383 Member<PendingRuleMaps> pending_rules_;
384
385 #ifndef NDEBUG
386 HeapVector<Member<const RuleData>> all_rules_;
387 #endif
388 };
389
390 } // namespace blink
391
392 #endif // THIRD_PARTY_BLINK_RENDERER_CORE_CSS_RULE_SET_H_
393