Source code

Revision control

Other Tools

1
/* This Source Code Form is subject to the terms of the Mozilla Public
2
* License, v. 2.0. If a copy of the MPL was not distributed with this
3
* file, You can obtain one at https://mozilla.org/MPL/2.0/. */
4
5
//! A data structure to efficiently index structs containing selectors by local
6
//! name, ids and hash.
7
8
use crate::applicable_declarations::ApplicableDeclarationList;
9
use crate::context::QuirksMode;
10
use crate::dom::TElement;
11
use crate::hash::map as hash_map;
12
use crate::hash::{HashMap, HashSet};
13
use crate::rule_tree::CascadeLevel;
14
use crate::selector_parser::SelectorImpl;
15
use crate::stylist::Rule;
16
use crate::{Atom, LocalName, Namespace, WeakAtom};
17
use fallible::FallibleVec;
18
use hashglobe::FailedAllocationError;
19
use precomputed_hash::PrecomputedHash;
20
use selectors::matching::{matches_selector, ElementSelectorFlags, MatchingContext};
21
use selectors::parser::{Combinator, Component, SelectorIter};
22
use smallvec::SmallVec;
23
use std::hash::{BuildHasherDefault, Hash, Hasher};
24
25
/// A hasher implementation that doesn't hash anything, because it expects its
26
/// input to be a suitable u32 hash.
27
pub struct PrecomputedHasher {
28
hash: Option<u32>,
29
}
30
31
impl Default for PrecomputedHasher {
32
fn default() -> Self {
33
Self { hash: None }
34
}
35
}
36
37
/// A simple alias for a hashmap using PrecomputedHasher.
38
pub type PrecomputedHashMap<K, V> = HashMap<K, V, BuildHasherDefault<PrecomputedHasher>>;
39
40
/// A simple alias for a hashset using PrecomputedHasher.
41
pub type PrecomputedHashSet<K> = HashSet<K, BuildHasherDefault<PrecomputedHasher>>;
42
43
impl Hasher for PrecomputedHasher {
44
#[inline]
45
fn write(&mut self, _: &[u8]) {
46
unreachable!(
47
"Called into PrecomputedHasher with something that isn't \
48
a u32"
49
)
50
}
51
52
#[inline]
53
fn write_u32(&mut self, i: u32) {
54
debug_assert!(self.hash.is_none());
55
self.hash = Some(i);
56
}
57
58
#[inline]
59
fn finish(&self) -> u64 {
60
self.hash.expect("PrecomputedHasher wasn't fed?") as u64
61
}
62
}
63
64
/// A trait to abstract over a given selector map entry.
65
pub trait SelectorMapEntry: Sized + Clone {
66
/// Gets the selector we should use to index in the selector map.
67
fn selector(&self) -> SelectorIter<SelectorImpl>;
68
}
69
70
/// Map element data to selector-providing objects for which the last simple
71
/// selector starts with them.
72
///
73
/// e.g.,
74
/// "p > img" would go into the set of selectors corresponding to the
75
/// element "img"
76
/// "a .foo .bar.baz" would go into the set of selectors corresponding to
77
/// the class "bar"
78
///
79
/// Because we match selectors right-to-left (i.e., moving up the tree
80
/// from an element), we need to compare the last simple selector in the
81
/// selector with the element.
82
///
83
/// So, if an element has ID "id1" and classes "foo" and "bar", then all
84
/// the rules it matches will have their last simple selector starting
85
/// either with "#id1" or with ".foo" or with ".bar".
86
///
87
/// Hence, the union of the rules keyed on each of element's classes, ID,
88
/// element name, etc. will contain the Selectors that actually match that
89
/// element.
90
///
91
/// We use a 1-entry SmallVec to avoid a separate heap allocation in the case
92
/// where we only have one entry, which is quite common. See measurements in:
95
///
96
/// TODO: Tune the initial capacity of the HashMap
97
#[derive(Debug, MallocSizeOf)]
98
pub struct SelectorMap<T: 'static> {
99
/// Rules that have `:root` selectors.
100
pub root: SmallVec<[T; 1]>,
101
/// A hash from an ID to rules which contain that ID selector.
102
pub id_hash: MaybeCaseInsensitiveHashMap<Atom, SmallVec<[T; 1]>>,
103
/// A hash from a class name to rules which contain that class selector.
104
pub class_hash: MaybeCaseInsensitiveHashMap<Atom, SmallVec<[T; 1]>>,
105
/// A hash from local name to rules which contain that local name selector.
106
pub local_name_hash: PrecomputedHashMap<LocalName, SmallVec<[T; 1]>>,
107
/// A hash from namespace to rules which contain that namespace selector.
108
pub namespace_hash: PrecomputedHashMap<Namespace, SmallVec<[T; 1]>>,
109
/// All other rules.
110
pub other: SmallVec<[T; 1]>,
111
/// The number of entries in this map.
112
pub count: usize,
113
}
114
115
impl<T: 'static> Default for SelectorMap<T> {
116
#[inline]
117
fn default() -> Self {
118
Self::new()
119
}
120
}
121
122
// FIXME(Manishearth) the 'static bound can be removed when
123
// our HashMap fork (hashglobe) is able to use NonZero,
124
// or when stdlib gets fallible collections
125
impl<T: 'static> SelectorMap<T> {
126
/// Trivially constructs an empty `SelectorMap`.
127
pub fn new() -> Self {
128
SelectorMap {
129
root: SmallVec::new(),
130
id_hash: MaybeCaseInsensitiveHashMap::new(),
131
class_hash: MaybeCaseInsensitiveHashMap::new(),
132
local_name_hash: HashMap::default(),
133
namespace_hash: HashMap::default(),
134
other: SmallVec::new(),
135
count: 0,
136
}
137
}
138
139
/// Clears the hashmap retaining storage.
140
pub fn clear(&mut self) {
141
self.root.clear();
142
self.id_hash.clear();
143
self.class_hash.clear();
144
self.local_name_hash.clear();
145
self.namespace_hash.clear();
146
self.other.clear();
147
self.count = 0;
148
}
149
150
/// Returns whether there are any entries in the map.
151
pub fn is_empty(&self) -> bool {
152
self.count == 0
153
}
154
155
/// Returns the number of entries.
156
pub fn len(&self) -> usize {
157
self.count
158
}
159
}
160
161
impl SelectorMap<Rule> {
162
/// Append to `rule_list` all Rules in `self` that match element.
163
///
164
/// Extract matching rules as per element's ID, classes, tag name, etc..
165
/// Sort the Rules at the end to maintain cascading order.
166
pub fn get_all_matching_rules<E, F>(
167
&self,
168
element: E,
169
rule_hash_target: E,
170
matching_rules_list: &mut ApplicableDeclarationList,
171
context: &mut MatchingContext<E::Impl>,
172
flags_setter: &mut F,
173
cascade_level: CascadeLevel,
174
) where
175
E: TElement,
176
F: FnMut(&E, ElementSelectorFlags),
177
{
178
if self.is_empty() {
179
return;
180
}
181
182
let quirks_mode = context.quirks_mode();
183
184
if rule_hash_target.is_root() {
185
SelectorMap::get_matching_rules(
186
element,
187
&self.root,
188
matching_rules_list,
189
context,
190
flags_setter,
191
cascade_level,
192
);
193
}
194
195
if let Some(id) = rule_hash_target.id() {
196
if let Some(rules) = self.id_hash.get(id, quirks_mode) {
197
SelectorMap::get_matching_rules(
198
element,
199
rules,
200
matching_rules_list,
201
context,
202
flags_setter,
203
cascade_level,
204
)
205
}
206
}
207
208
rule_hash_target.each_class(|class| {
209
if let Some(rules) = self.class_hash.get(&class, quirks_mode) {
210
SelectorMap::get_matching_rules(
211
element,
212
rules,
213
matching_rules_list,
214
context,
215
flags_setter,
216
cascade_level,
217
)
218
}
219
});
220
221
if let Some(rules) = self.local_name_hash.get(rule_hash_target.local_name()) {
222
SelectorMap::get_matching_rules(
223
element,
224
rules,
225
matching_rules_list,
226
context,
227
flags_setter,
228
cascade_level,
229
)
230
}
231
232
if let Some(rules) = self.namespace_hash.get(rule_hash_target.namespace()) {
233
SelectorMap::get_matching_rules(
234
element,
235
rules,
236
matching_rules_list,
237
context,
238
flags_setter,
239
cascade_level,
240
)
241
}
242
243
SelectorMap::get_matching_rules(
244
element,
245
&self.other,
246
matching_rules_list,
247
context,
248
flags_setter,
249
cascade_level,
250
);
251
}
252
253
/// Adds rules in `rules` that match `element` to the `matching_rules` list.
254
pub(crate) fn get_matching_rules<E, F>(
255
element: E,
256
rules: &[Rule],
257
matching_rules: &mut ApplicableDeclarationList,
258
context: &mut MatchingContext<E::Impl>,
259
flags_setter: &mut F,
260
cascade_level: CascadeLevel,
261
) where
262
E: TElement,
263
F: FnMut(&E, ElementSelectorFlags),
264
{
265
for rule in rules {
266
if matches_selector(
267
&rule.selector,
268
0,
269
Some(&rule.hashes),
270
&element,
271
context,
272
flags_setter,
273
) {
274
matching_rules.push(
275
rule.to_applicable_declaration_block(cascade_level),
276
);
277
}
278
}
279
}
280
}
281
282
impl<T: SelectorMapEntry> SelectorMap<T> {
283
/// Inserts into the correct hash, trying id, class, localname and
284
/// namespace.
285
pub fn insert(
286
&mut self,
287
entry: T,
288
quirks_mode: QuirksMode,
289
) -> Result<(), FailedAllocationError> {
290
self.count += 1;
291
292
let vector = match find_bucket(entry.selector()) {
293
Bucket::Root => &mut self.root,
294
Bucket::ID(id) => self
295
.id_hash
296
.try_entry(id.clone(), quirks_mode)?
297
.or_insert_with(SmallVec::new),
298
Bucket::Class(class) => self
299
.class_hash
300
.try_entry(class.clone(), quirks_mode)?
301
.or_insert_with(SmallVec::new),
302
Bucket::LocalName { name, lower_name } => {
303
// If the local name in the selector isn't lowercase, insert it
304
// into the rule hash twice. This means that, during lookup, we
305
// can always find the rules based on the local name of the
306
// element, regardless of whether it's an html element in an
307
// html document (in which case we match against lower_name) or
308
// not (in which case we match against name).
309
//
310
// In the case of a non-html-element-in-html-document with a
311
// lowercase localname and a non-lowercase selector, the
312
// rulehash lookup may produce superfluous selectors, but the
313
// subsequent selector matching work will filter them out.
314
if name != lower_name {
315
self.local_name_hash
316
.try_entry(lower_name.clone())?
317
.or_insert_with(SmallVec::new)
318
.try_push(entry.clone())?;
319
}
320
self.local_name_hash
321
.try_entry(name.clone())?
322
.or_insert_with(SmallVec::new)
323
},
324
Bucket::Namespace(url) => self
325
.namespace_hash
326
.try_entry(url.clone())?
327
.or_insert_with(SmallVec::new),
328
Bucket::Universal => &mut self.other,
329
};
330
331
vector.try_push(entry)
332
}
333
334
/// Looks up entries by id, class, local name, namespace, and other (in
335
/// order).
336
///
337
/// Each entry is passed to the callback, which returns true to continue
338
/// iterating entries, or false to terminate the lookup.
339
///
340
/// Returns false if the callback ever returns false.
341
///
342
/// FIXME(bholley) This overlaps with SelectorMap<Rule>::get_all_matching_rules,
343
/// but that function is extremely hot and I'd rather not rearrange it.
344
#[inline]
345
pub fn lookup<'a, E, F>(&'a self, element: E, quirks_mode: QuirksMode, mut f: F) -> bool
346
where
347
E: TElement,
348
F: FnMut(&'a T) -> bool,
349
{
350
if element.is_root() {
351
for entry in self.root.iter() {
352
if !f(&entry) {
353
return false;
354
}
355
}
356
}
357
358
if let Some(id) = element.id() {
359
if let Some(v) = self.id_hash.get(id, quirks_mode) {
360
for entry in v.iter() {
361
if !f(&entry) {
362
return false;
363
}
364
}
365
}
366
}
367
368
let mut done = false;
369
element.each_class(|class| {
370
if !done {
371
if let Some(v) = self.class_hash.get(class, quirks_mode) {
372
for entry in v.iter() {
373
if !f(&entry) {
374
done = true;
375
return;
376
}
377
}
378
}
379
}
380
});
381
if done {
382
return false;
383
}
384
385
if let Some(v) = self.local_name_hash.get(element.local_name()) {
386
for entry in v.iter() {
387
if !f(&entry) {
388
return false;
389
}
390
}
391
}
392
393
if let Some(v) = self.namespace_hash.get(element.namespace()) {
394
for entry in v.iter() {
395
if !f(&entry) {
396
return false;
397
}
398
}
399
}
400
401
for entry in self.other.iter() {
402
if !f(&entry) {
403
return false;
404
}
405
}
406
407
true
408
}
409
410
/// Performs a normal lookup, and also looks up entries for the passed-in
411
/// id and classes.
412
///
413
/// Each entry is passed to the callback, which returns true to continue
414
/// iterating entries, or false to terminate the lookup.
415
///
416
/// Returns false if the callback ever returns false.
417
#[inline]
418
pub fn lookup_with_additional<'a, E, F>(
419
&'a self,
420
element: E,
421
quirks_mode: QuirksMode,
422
additional_id: Option<&WeakAtom>,
423
additional_classes: &[Atom],
424
mut f: F,
425
) -> bool
426
where
427
E: TElement,
428
F: FnMut(&'a T) -> bool,
429
{
430
// Do the normal lookup.
431
if !self.lookup(element, quirks_mode, |entry| f(entry)) {
432
return false;
433
}
434
435
// Check the additional id.
436
if let Some(id) = additional_id {
437
if let Some(v) = self.id_hash.get(id, quirks_mode) {
438
for entry in v.iter() {
439
if !f(&entry) {
440
return false;
441
}
442
}
443
}
444
}
445
446
// Check the additional classes.
447
for class in additional_classes {
448
if let Some(v) = self.class_hash.get(class, quirks_mode) {
449
for entry in v.iter() {
450
if !f(&entry) {
451
return false;
452
}
453
}
454
}
455
}
456
457
true
458
}
459
}
460
461
enum Bucket<'a> {
462
Root,
463
ID(&'a Atom),
464
Class(&'a Atom),
465
LocalName {
466
name: &'a LocalName,
467
lower_name: &'a LocalName,
468
},
469
Namespace(&'a Namespace),
470
Universal,
471
}
472
473
fn specific_bucket_for<'a>(component: &'a Component<SelectorImpl>) -> Bucket<'a> {
474
match *component {
475
Component::Root => Bucket::Root,
476
Component::ID(ref id) => Bucket::ID(id),
477
Component::Class(ref class) => Bucket::Class(class),
478
Component::LocalName(ref selector) => Bucket::LocalName {
479
name: &selector.name,
480
lower_name: &selector.lower_name,
481
},
482
Component::Namespace(_, ref url) | Component::DefaultNamespace(ref url) => {
483
Bucket::Namespace(url)
484
},
485
// ::slotted(..) isn't a normal pseudo-element, so we can insert it on
486
// the rule hash normally without much problem. For example, in a
487
// selector like:
488
//
489
// div::slotted(span)::before
490
//
491
// It looks like:
492
//
493
// [
494
// LocalName(div),
495
// Combinator(SlotAssignment),
496
// Slotted(span),
497
// Combinator::PseudoElement,
498
// PseudoElement(::before),
499
// ]
500
//
501
// So inserting `span` in the rule hash makes sense since we want to
502
// match the slotted <span>.
503
Component::Slotted(ref selector) => find_bucket(selector.iter()),
504
Component::Host(Some(ref selector)) => find_bucket(selector.iter()),
505
_ => Bucket::Universal,
506
}
507
}
508
509
/// Searches a compound selector from left to right, and returns the appropriate
510
/// bucket for it.
511
#[inline(always)]
512
fn find_bucket<'a>(mut iter: SelectorIter<'a, SelectorImpl>) -> Bucket<'a> {
513
let mut current_bucket = Bucket::Universal;
514
515
loop {
516
// We basically want to find the most specific bucket,
517
// where:
518
//
519
// root > id > class > local name > namespace > universal.
520
//
521
for ss in &mut iter {
522
let new_bucket = specific_bucket_for(ss);
523
match new_bucket {
524
Bucket::Root => return new_bucket,
525
Bucket::ID(..) => {
526
current_bucket = new_bucket;
527
},
528
Bucket::Class(..) => {
529
if !matches!(current_bucket, Bucket::ID(..)) {
530
current_bucket = new_bucket;
531
}
532
},
533
Bucket::LocalName { .. } => {
534
if matches!(current_bucket, Bucket::Universal | Bucket::Namespace(..)) {
535
current_bucket = new_bucket;
536
}
537
},
538
Bucket::Namespace(..) => {
539
if matches!(current_bucket, Bucket::Universal) {
540
current_bucket = new_bucket;
541
}
542
},
543
Bucket::Universal => {},
544
}
545
}
546
547
// Effectively, pseudo-elements are ignored, given only state
548
// pseudo-classes may appear before them.
549
if iter.next_sequence() != Some(Combinator::PseudoElement) {
550
break;
551
}
552
}
553
554
return current_bucket;
555
}
556
557
/// Wrapper for PrecomputedHashMap that does ASCII-case-insensitive lookup in quirks mode.
558
#[derive(Debug, MallocSizeOf)]
559
pub struct MaybeCaseInsensitiveHashMap<K: PrecomputedHash + Hash + Eq, V: 'static>(
560
PrecomputedHashMap<K, V>,
561
);
562
563
// FIXME(Manishearth) the 'static bound can be removed when
564
// our HashMap fork (hashglobe) is able to use NonZero,
565
// or when stdlib gets fallible collections
566
impl<V: 'static> MaybeCaseInsensitiveHashMap<Atom, V> {
567
/// Empty map
568
pub fn new() -> Self {
569
MaybeCaseInsensitiveHashMap(PrecomputedHashMap::default())
570
}
571
572
/// HashMap::try_entry
573
pub fn try_entry(
574
&mut self,
575
mut key: Atom,
576
quirks_mode: QuirksMode,
577
) -> Result<hash_map::Entry<Atom, V>, FailedAllocationError> {
578
if quirks_mode == QuirksMode::Quirks {
579
key = key.to_ascii_lowercase()
580
}
581
self.0.try_entry(key)
582
}
583
584
/// HashMap::iter
585
pub fn iter(&self) -> hash_map::Iter<Atom, V> {
586
self.0.iter()
587
}
588
589
/// HashMap::clear
590
pub fn clear(&mut self) {
591
self.0.clear()
592
}
593
594
/// HashMap::get
595
pub fn get(&self, key: &WeakAtom, quirks_mode: QuirksMode) -> Option<&V> {
596
if quirks_mode == QuirksMode::Quirks {
597
self.0.get(&key.to_ascii_lowercase())
598
} else {
599
self.0.get(key)
600
}
601
}
602
}