/
driver.rs
136 lines (125 loc) · 5.73 KB
/
driver.rs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
/* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
//! Implements traversal over the DOM tree. The traversal starts in sequential
//! mode, and optionally parallelizes as it discovers work.
#![deny(missing_docs)]
use context::{StyleContext, ThreadLocalStyleContext};
use dom::{SendNode, TElement, TNode};
use parallel;
use parallel::{DispatchMode, WORK_UNIT_MAX};
use rayon;
use scoped_tls::ScopedTLS;
use std::collections::VecDeque;
use std::mem;
use time;
use traversal::{DomTraversal, PerLevelTraversalData, PreTraverseToken};
/// Do a DOM traversal for top-down and (optionally) bottom-up processing,
/// generic over `D`.
///
/// We use an adaptive traversal strategy. We start out with simple sequential
/// processing, until we arrive at a wide enough level in the DOM that the
/// parallel traversal would parallelize it. If a thread pool is provided, we
/// then transfer control over to the parallel traversal.
///
/// Returns true if the traversal was parallel, and also returns the statistics
/// object containing information on nodes traversed (on nightly only). Not
/// all of its fields will be initialized since we don't call finish().
pub fn traverse_dom<E, D>(
traversal: &D,
token: PreTraverseToken<E>,
pool: Option<&rayon::ThreadPool>
)
where
E: TElement,
D: DomTraversal<E>,
{
let root =
token.traversal_root().expect("Should've ensured we needed to traverse");
let dump_stats = traversal.shared_context().options.dump_style_statistics;
let start_time = if dump_stats { Some(time::precise_time_s()) } else { None };
// Declare the main-thread context, as well as the worker-thread contexts,
// which we may or may not instantiate. It's important to declare the worker-
// thread contexts first, so that they get dropped second. This matters because:
// * ThreadLocalContexts borrow AtomicRefCells in TLS.
// * Dropping a ThreadLocalContext can run SequentialTasks.
// * Sequential tasks may call into functions like
// Servo_StyleSet_GetBaseComputedValuesForElement, which instantiate a
// ThreadLocalStyleContext on the main thread. If the main thread
// ThreadLocalStyleContext has not released its TLS borrow by that point,
// we'll panic on double-borrow.
let mut maybe_tls: Option<ScopedTLS<ThreadLocalStyleContext<E>>> = None;
let mut tlc = ThreadLocalStyleContext::new(traversal.shared_context());
let mut context = StyleContext {
shared: traversal.shared_context(),
thread_local: &mut tlc,
};
// Process the nodes breadth-first, just like the parallel traversal does.
// This helps keep similar traversal characteristics for the style sharing
// cache.
let mut discovered =
VecDeque::<SendNode<E::ConcreteNode>>::with_capacity(WORK_UNIT_MAX * 2);
let mut depth = root.depth();
let mut nodes_remaining_at_current_depth = 1;
discovered.push_back(unsafe { SendNode::new(root.as_node()) });
while let Some(node) = discovered.pop_front() {
let mut children_to_process = 0isize;
let traversal_data = PerLevelTraversalData { current_dom_depth: depth };
traversal.process_preorder(&traversal_data, &mut context, *node, |n| {
children_to_process += 1;
discovered.push_back(unsafe { SendNode::new(n) });
});
traversal.handle_postorder_traversal(&mut context, root.as_node().opaque(),
*node, children_to_process);
nodes_remaining_at_current_depth -= 1;
if nodes_remaining_at_current_depth == 0 {
depth += 1;
// If there is enough work to parallelize over, and the caller allows
// parallelism, switch to the parallel driver. We do this only when
// moving to the next level in the dom so that we can pass the same
// depth for all the children.
if pool.is_some() && discovered.len() > WORK_UNIT_MAX {
let pool = pool.unwrap();
maybe_tls = Some(ScopedTLS::<ThreadLocalStyleContext<E>>::new(pool));
let root_opaque = root.as_node().opaque();
let drain = discovered.drain(..);
pool.install(|| {
rayon::scope(|scope| {
parallel::traverse_nodes(
drain,
DispatchMode::TailCall,
/* recursion_ok = */ true,
root_opaque,
PerLevelTraversalData { current_dom_depth: depth },
scope,
pool,
traversal,
maybe_tls.as_ref().unwrap()
);
});
});
break;
}
nodes_remaining_at_current_depth = discovered.len();
}
}
// dump statistics to stdout if requested
if dump_stats {
let mut aggregate =
mem::replace(&mut context.thread_local.statistics, Default::default());
let parallel = maybe_tls.is_some();
if let Some(ref mut tls) = maybe_tls {
let slots = unsafe { tls.unsafe_get() };
aggregate = slots.iter().fold(aggregate, |acc, t| {
match *t.borrow() {
None => acc,
Some(ref cx) => &cx.statistics + &acc,
}
});
}
aggregate.finish(traversal, parallel, start_time.unwrap());
if aggregate.is_large_traversal() {
println!("{}", aggregate);
}
}
}