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
//! The style bloom filter is used as an optimization when matching deep
6
//! descendant selectors.
7
8
#![deny(missing_docs)]
9
10
use crate::dom::{SendElement, TElement};
11
use atomic_refcell::{AtomicRefCell, AtomicRefMut};
12
use owning_ref::OwningHandle;
13
use selectors::bloom::BloomFilter;
14
use servo_arc::Arc;
15
use smallvec::SmallVec;
16
use std::mem::ManuallyDrop;
17
18
thread_local! {
19
/// Bloom filters are large allocations, so we store them in thread-local storage
20
/// such that they can be reused across style traversals. StyleBloom is responsible
21
/// for ensuring that the bloom filter is zeroed when it is dropped.
22
///
23
/// We intentionally leak this from TLS because we don't have the guarantee
24
/// of TLS destructors to run in worker threads.
25
///
26
/// We could change this once https://github.com/rayon-rs/rayon/issues/688
27
/// is fixed, hopefully.
28
static BLOOM_KEY: ManuallyDrop<Arc<AtomicRefCell<BloomFilter>>> =
29
ManuallyDrop::new(Arc::new_leaked(Default::default()));
30
}
31
32
/// A struct that allows us to fast-reject deep descendant selectors avoiding
33
/// selector-matching.
34
///
35
/// This is implemented using a counting bloom filter, and it's a standard
36
/// optimization. See Gecko's `AncestorFilter`, and Blink's and WebKit's
37
/// `SelectorFilter`.
38
///
39
/// The constraints for Servo's style system are a bit different compared to
40
/// traditional style systems given Servo does a parallel breadth-first
41
/// traversal instead of a sequential depth-first traversal.
42
///
43
/// This implies that we need to track a bit more state than other browsers to
44
/// ensure we're doing the correct thing during the traversal, and being able to
45
/// apply this optimization effectively.
46
///
47
/// Concretely, we have a bloom filter instance per worker thread, and we track
48
/// the current DOM depth in order to find a common ancestor when it doesn't
49
/// match the previous element we've styled.
50
///
51
/// This is usually a pretty fast operation (we use to be one level deeper than
52
/// the previous one), but in the case of work-stealing, we may needed to push
53
/// and pop multiple elements.
54
///
55
/// See the `insert_parents_recovering`, where most of the magic happens.
56
///
57
/// Regarding thread-safety, this struct is safe because:
58
///
59
/// * We clear this after a restyle.
60
/// * The DOM shape and attributes (and every other thing we access here) are
61
/// immutable during a restyle.
62
///
63
pub struct StyleBloom<E: TElement> {
64
/// A handle to the bloom filter from the thread upon which this StyleBloom
65
/// was created. We use AtomicRefCell so that this is all |Send|, which allows
66
/// StyleBloom to live in ThreadLocalStyleContext, which is dropped from the
67
/// parent thread.
68
filter: OwningHandle<Arc<AtomicRefCell<BloomFilter>>, AtomicRefMut<'static, BloomFilter>>,
69
70
/// The stack of elements that this bloom filter contains, along with the
71
/// number of hashes pushed for each element.
72
elements: SmallVec<[PushedElement<E>; 16]>,
73
74
/// Stack of hashes that have been pushed onto this filter.
75
pushed_hashes: SmallVec<[u32; 64]>,
76
}
77
78
/// The very rough benchmarks in the selectors crate show clear()
79
/// costing about 25 times more than remove_hash(). We use this to implement
80
/// clear() more efficiently when only a small number of hashes have been
81
/// pushed.
82
///
83
/// One subtly to note is that remove_hash() will not touch the value
84
/// if the filter overflowed. However, overflow can only occur if we
85
/// get 255 collisions on the same hash value, and 25 < 255.
86
const MEMSET_CLEAR_THRESHOLD: usize = 25;
87
88
struct PushedElement<E: TElement> {
89
/// The element that was pushed.
90
element: SendElement<E>,
91
92
/// The number of hashes pushed for the element.
93
num_hashes: usize,
94
}
95
96
impl<E: TElement> PushedElement<E> {
97
fn new(el: E, num_hashes: usize) -> Self {
98
PushedElement {
99
element: unsafe { SendElement::new(el) },
100
num_hashes,
101
}
102
}
103
}
104
105
fn each_relevant_element_hash<E, F>(element: E, mut f: F)
106
where
107
E: TElement,
108
F: FnMut(u32),
109
{
110
f(element.local_name().get_hash());
111
f(element.namespace().get_hash());
112
113
if let Some(id) = element.id() {
114
f(id.get_hash());
115
}
116
117
element.each_class(|class| f(class.get_hash()));
118
}
119
120
impl<E: TElement> Drop for StyleBloom<E> {
121
fn drop(&mut self) {
122
// Leave the reusable bloom filter in a zeroed state.
123
self.clear();
124
}
125
}
126
127
impl<E: TElement> StyleBloom<E> {
128
/// Create an empty `StyleBloom`. Because StyleBloom acquires the thread-
129
/// local filter buffer, creating multiple live StyleBloom instances at
130
/// the same time on the same thread will panic.
131
132
// Forced out of line to limit stack frame sizes after extra inlining from
134
//
136
#[inline(never)]
137
pub fn new() -> Self {
138
let bloom_arc = BLOOM_KEY.with(|b| Arc::clone(&*b));
139
let filter =
140
OwningHandle::new_with_fn(bloom_arc, |x| unsafe { x.as_ref() }.unwrap().borrow_mut());
141
debug_assert!(
142
filter.is_zeroed(),
143
"Forgot to zero the bloom filter last time"
144
);
145
StyleBloom {
146
filter,
147
elements: Default::default(),
148
pushed_hashes: Default::default(),
149
}
150
}
151
152
/// Return the bloom filter used properly by the `selectors` crate.
153
pub fn filter(&self) -> &BloomFilter {
154
&*self.filter
155
}
156
157
/// Push an element to the bloom filter, knowing that it's a child of the
158
/// last element parent.
159
pub fn push(&mut self, element: E) {
160
if cfg!(debug_assertions) {
161
if self.elements.is_empty() {
162
assert!(element.traversal_parent().is_none());
163
}
164
}
165
self.push_internal(element);
166
}
167
168
/// Same as `push`, but without asserting, in order to use it from
169
/// `rebuild`.
170
fn push_internal(&mut self, element: E) {
171
let mut count = 0;
172
each_relevant_element_hash(element, |hash| {
173
count += 1;
174
self.filter.insert_hash(hash);
175
self.pushed_hashes.push(hash);
176
});
177
self.elements.push(PushedElement::new(element, count));
178
}
179
180
/// Pop the last element in the bloom filter and return it.
181
#[inline]
182
fn pop(&mut self) -> Option<E> {
183
let PushedElement {
184
element,
185
num_hashes,
186
} = self.elements.pop()?;
187
let popped_element = *element;
188
189
// Verify that the pushed hashes match the ones we'd get from the element.
190
let mut expected_hashes = vec![];
191
if cfg!(debug_assertions) {
192
each_relevant_element_hash(popped_element, |hash| expected_hashes.push(hash));
193
}
194
195
for _ in 0..num_hashes {
196
let hash = self.pushed_hashes.pop().unwrap();
197
debug_assert_eq!(expected_hashes.pop().unwrap(), hash);
198
self.filter.remove_hash(hash);
199
}
200
201
Some(popped_element)
202
}
203
204
/// Returns the DOM depth of elements that can be correctly
205
/// matched against the bloom filter (that is, the number of
206
/// elements in our list).
207
pub fn matching_depth(&self) -> usize {
208
self.elements.len()
209
}
210
211
/// Clears the bloom filter.
212
pub fn clear(&mut self) {
213
self.elements.clear();
214
215
if self.pushed_hashes.len() > MEMSET_CLEAR_THRESHOLD {
216
self.filter.clear();
217
self.pushed_hashes.clear();
218
} else {
219
for hash in self.pushed_hashes.drain() {
220
self.filter.remove_hash(hash);
221
}
222
debug_assert!(self.filter.is_zeroed());
223
}
224
}
225
226
/// Rebuilds the bloom filter up to the parent of the given element.
227
pub fn rebuild(&mut self, mut element: E) {
228
self.clear();
229
230
let mut parents_to_insert = SmallVec::<[E; 16]>::new();
231
while let Some(parent) = element.traversal_parent() {
232
parents_to_insert.push(parent);
233
element = parent;
234
}
235
236
for parent in parents_to_insert.drain().rev() {
237
self.push(parent);
238
}
239
}
240
241
/// In debug builds, asserts that all the parents of `element` are in the
242
/// bloom filter.
243
///
244
/// Goes away in release builds.
245
pub fn assert_complete(&self, mut element: E) {
246
if cfg!(debug_assertions) {
247
let mut checked = 0;
248
while let Some(parent) = element.traversal_parent() {
249
assert_eq!(
250
parent,
251
*(self.elements[self.elements.len() - 1 - checked].element)
252
);
253
element = parent;
254
checked += 1;
255
}
256
assert_eq!(checked, self.elements.len());
257
}
258
}
259
260
/// Get the element that represents the chain of things inserted
261
/// into the filter right now. That chain is the given element
262
/// (if any) and its ancestors.
263
#[inline]
264
pub fn current_parent(&self) -> Option<E> {
265
self.elements.last().map(|ref el| *el.element)
266
}
267
268
/// Insert the parents of an element in the bloom filter, trying to recover
269
/// the filter if the last element inserted doesn't match.
270
///
271
/// Gets the element depth in the dom, to make it efficient, or if not
272
/// provided always rebuilds the filter from scratch.
273
///
274
/// Returns the new bloom filter depth, that the traversal code is
275
/// responsible to keep around if it wants to get an effective filter.
276
pub fn insert_parents_recovering(&mut self, element: E, element_depth: usize) {
277
// Easy case, we're in a different restyle, or we're empty.
278
if self.elements.is_empty() {
279
self.rebuild(element);
280
return;
281
}
282
283
let traversal_parent = match element.traversal_parent() {
284
Some(parent) => parent,
285
None => {
286
// Yay, another easy case.
287
self.clear();
288
return;
289
},
290
};
291
292
if self.current_parent() == Some(traversal_parent) {
293
// Ta da, cache hit, we're all done.
294
return;
295
}
296
297
if element_depth == 0 {
298
self.clear();
299
return;
300
}
301
302
// We should've early exited above.
303
debug_assert!(
304
element_depth != 0,
305
"We should have already cleared the bloom filter"
306
);
307
debug_assert!(!self.elements.is_empty(), "How! We should've just rebuilt!");
308
309
// Now the fun begins: We have the depth of the dom and the depth of the
310
// last element inserted in the filter, let's try to find a common
311
// parent.
312
//
313
// The current depth, that is, the depth of the last element inserted in
314
// the bloom filter, is the number of elements _minus one_, that is: if
315
// there's one element, it must be the root -> depth zero.
316
let mut current_depth = self.elements.len() - 1;
317
318
// If the filter represents an element too deep in the dom, we need to
319
// pop ancestors.
320
while current_depth > element_depth - 1 {
321
self.pop().expect("Emilio is bad at math");
322
current_depth -= 1;
323
}
324
325
// Now let's try to find a common parent in the bloom filter chain,
326
// starting with traversal_parent.
327
let mut common_parent = traversal_parent;
328
let mut common_parent_depth = element_depth - 1;
329
330
// Let's collect the parents we are going to need to insert once we've
331
// found the common one.
332
let mut parents_to_insert = SmallVec::<[E; 16]>::new();
333
334
// If the bloom filter still doesn't have enough elements, the common
335
// parent is up in the dom.
336
while common_parent_depth > current_depth {
337
// TODO(emilio): Seems like we could insert parents here, then
338
// reverse the slice.
339
parents_to_insert.push(common_parent);
340
common_parent = common_parent.traversal_parent().expect("We were lied to");
341
common_parent_depth -= 1;
342
}
343
344
// Now the two depths are the same.
345
debug_assert_eq!(common_parent_depth, current_depth);
346
347
// Happy case: The parents match, we only need to push the ancestors
348
// we've collected and we'll never enter in this loop.
349
//
350
// Not-so-happy case: Parent's don't match, so we need to keep going up
351
// until we find a common ancestor.
352
//
353
// Gecko currently models native anonymous content that conceptually
354
// hangs off the document (such as scrollbars) as a separate subtree
355
// from the document root.
356
//
357
// Thus it's possible with Gecko that we do not find any common
358
// ancestor.
359
while *(self.elements.last().unwrap().element) != common_parent {
360
parents_to_insert.push(common_parent);
361
self.pop().unwrap();
362
common_parent = match common_parent.traversal_parent() {
363
Some(parent) => parent,
364
None => {
365
debug_assert!(self.elements.is_empty());
366
if cfg!(feature = "gecko") {
367
break;
368
} else {
369
panic!("should have found a common ancestor");
370
}
371
},
372
}
373
}
374
375
// Now the parents match, so insert the stack of elements we have been
376
// collecting so far.
377
for parent in parents_to_insert.drain().rev() {
378
self.push(parent);
379
}
380
381
debug_assert_eq!(self.elements.len(), element_depth);
382
383
// We're done! Easy.
384
}
385
}