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
//! Implements traversal over the DOM tree. The traversal starts in sequential
6
//! mode, and optionally parallelizes as it discovers work.
7
8
#![deny(missing_docs)]
9
10
use crate::context::{PerThreadTraversalStatistics, StyleContext};
11
use crate::context::{ThreadLocalStyleContext, TraversalStatistics};
12
use crate::dom::{SendNode, TElement, TNode};
13
use crate::parallel;
14
use crate::parallel::{DispatchMode, WORK_UNIT_MAX};
15
use crate::scoped_tls::ScopedTLS;
16
use crate::traversal::{DomTraversal, PerLevelTraversalData, PreTraverseToken};
17
use rayon;
18
use std::collections::VecDeque;
19
use std::mem;
20
use time;
21
22
#[cfg(feature = "servo")]
23
fn should_report_statistics() -> bool {
24
false
25
}
26
27
#[cfg(feature = "gecko")]
28
fn should_report_statistics() -> bool {
29
unsafe { crate::gecko_bindings::structs::ServoTraversalStatistics_sActive }
30
}
31
32
#[cfg(feature = "servo")]
33
fn report_statistics(_stats: &PerThreadTraversalStatistics) {
34
unreachable!("Servo never report stats");
35
}
36
37
#[cfg(feature = "gecko")]
38
fn report_statistics(stats: &PerThreadTraversalStatistics) {
39
// This should only be called in the main thread, or it may be racy
40
// to update the statistics in a global variable.
41
debug_assert!(unsafe { crate::gecko_bindings::bindings::Gecko_IsMainThread() });
42
let gecko_stats =
43
unsafe { &mut crate::gecko_bindings::structs::ServoTraversalStatistics_sSingleton };
44
gecko_stats.mElementsTraversed += stats.elements_traversed;
45
gecko_stats.mElementsStyled += stats.elements_styled;
46
gecko_stats.mElementsMatched += stats.elements_matched;
47
gecko_stats.mStylesShared += stats.styles_shared;
48
gecko_stats.mStylesReused += stats.styles_reused;
49
}
50
51
/// Do a DOM traversal for top-down and (optionally) bottom-up processing,
52
/// generic over `D`.
53
///
54
/// We use an adaptive traversal strategy. We start out with simple sequential
55
/// processing, until we arrive at a wide enough level in the DOM that the
56
/// parallel traversal would parallelize it. If a thread pool is provided, we
57
/// then transfer control over to the parallel traversal.
58
///
59
/// Returns true if the traversal was parallel, and also returns the statistics
60
/// object containing information on nodes traversed (on nightly only). Not
61
/// all of its fields will be initialized since we don't call finish().
62
pub fn traverse_dom<E, D>(
63
traversal: &D,
64
token: PreTraverseToken<E>,
65
pool: Option<&rayon::ThreadPool>,
66
) where
67
E: TElement,
68
D: DomTraversal<E>,
69
{
70
let root = token
71
.traversal_root()
72
.expect("Should've ensured we needed to traverse");
73
74
let report_stats = should_report_statistics();
75
let dump_stats = traversal.shared_context().options.dump_style_statistics;
76
let start_time = if dump_stats {
77
Some(time::precise_time_s())
78
} else {
79
None
80
};
81
82
// Declare the main-thread context, as well as the worker-thread contexts,
83
// which we may or may not instantiate. It's important to declare the worker-
84
// thread contexts first, so that they get dropped second. This matters because:
85
// * ThreadLocalContexts borrow AtomicRefCells in TLS.
86
// * Dropping a ThreadLocalContext can run SequentialTasks.
87
// * Sequential tasks may call into functions like
88
// Servo_StyleSet_GetBaseComputedValuesForElement, which instantiate a
89
// ThreadLocalStyleContext on the main thread. If the main thread
90
// ThreadLocalStyleContext has not released its TLS borrow by that point,
91
// we'll panic on double-borrow.
92
let mut maybe_tls: Option<ScopedTLS<ThreadLocalStyleContext<E>>> = None;
93
let mut tlc = ThreadLocalStyleContext::new(traversal.shared_context());
94
let mut context = StyleContext {
95
shared: traversal.shared_context(),
96
thread_local: &mut tlc,
97
};
98
99
// Process the nodes breadth-first, just like the parallel traversal does.
100
// This helps keep similar traversal characteristics for the style sharing
101
// cache.
102
let mut discovered = VecDeque::<SendNode<E::ConcreteNode>>::with_capacity(WORK_UNIT_MAX * 2);
103
let mut depth = root.depth();
104
let mut nodes_remaining_at_current_depth = 1;
105
discovered.push_back(unsafe { SendNode::new(root.as_node()) });
106
while let Some(node) = discovered.pop_front() {
107
let mut children_to_process = 0isize;
108
let traversal_data = PerLevelTraversalData {
109
current_dom_depth: depth,
110
};
111
traversal.process_preorder(&traversal_data, &mut context, *node, |n| {
112
children_to_process += 1;
113
discovered.push_back(unsafe { SendNode::new(n) });
114
});
115
116
traversal.handle_postorder_traversal(
117
&mut context,
118
root.as_node().opaque(),
119
*node,
120
children_to_process,
121
);
122
123
nodes_remaining_at_current_depth -= 1;
124
if nodes_remaining_at_current_depth == 0 {
125
depth += 1;
126
// If there is enough work to parallelize over, and the caller allows
127
// parallelism, switch to the parallel driver. We do this only when
128
// moving to the next level in the dom so that we can pass the same
129
// depth for all the children.
130
if pool.is_some() && discovered.len() > WORK_UNIT_MAX {
131
let pool = pool.unwrap();
132
maybe_tls = Some(ScopedTLS::<ThreadLocalStyleContext<E>>::new(pool));
133
let root_opaque = root.as_node().opaque();
134
let drain = discovered.drain(..);
135
pool.install(|| {
136
// Enable a breadth-first rayon traversal. This causes the work
137
// queue to be always FIFO, rather than FIFO for stealers and
138
// FILO for the owner (which is what rayon does by default). This
139
// ensures that we process all the elements at a given depth before
140
// proceeding to the next depth, which is important for style sharing.
141
rayon::scope_fifo(|scope| {
142
profiler_label!(Style);
143
parallel::traverse_nodes(
144
drain,
145
DispatchMode::TailCall,
146
/* recursion_ok = */ true,
147
root_opaque,
148
PerLevelTraversalData {
149
current_dom_depth: depth,
150
},
151
scope,
152
pool,
153
traversal,
154
maybe_tls.as_ref().unwrap(),
155
);
156
});
157
});
158
break;
159
}
160
nodes_remaining_at_current_depth = discovered.len();
161
}
162
}
163
164
// Collect statistics from thread-locals if requested.
165
if dump_stats || report_stats {
166
let mut aggregate = mem::replace(&mut context.thread_local.statistics, Default::default());
167
let parallel = maybe_tls.is_some();
168
if let Some(ref mut tls) = maybe_tls {
169
let slots = unsafe { tls.unsafe_get() };
170
for slot in slots {
171
if let Some(ref cx) = *slot.borrow() {
172
aggregate += cx.statistics.clone();
173
}
174
}
175
}
176
177
if report_stats {
178
report_statistics(&aggregate);
179
}
180
// dump statistics to stdout if requested
181
if dump_stats {
182
let stats =
183
TraversalStatistics::new(aggregate, traversal, parallel, start_time.unwrap());
184
if stats.is_large {
185
println!("{}", stats);
186
}
187
}
188
}
189
}