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