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/. */
5 //! Implements traversal over the DOM tree. The traversal starts in sequential
6 //! mode, and optionally parallelizes as it discovers work.
10 use crate::context::{PerThreadTraversalStatistics, StyleContext};
11 use crate::context::{ThreadLocalStyleContext, TraversalStatistics};
12 use crate::dom::{SendNode, TElement, TNode};
14 use crate::parallel::{DispatchMode, WORK_UNIT_MAX};
15 use crate::scoped_tls::ScopedTLS;
16 use crate::traversal::{DomTraversal, PerLevelTraversalData, PreTraverseToken};
18 use std::collections::VecDeque;
22 #[cfg(feature = "servo")]
23 fn should_report_statistics() -> bool {
27 #[cfg(feature = "gecko")]
28 fn should_report_statistics() -> bool {
29 unsafe { crate::gecko_bindings::structs::ServoTraversalStatistics_sActive }
32 #[cfg(feature = "servo")]
33 fn report_statistics(_stats: &PerThreadTraversalStatistics) {
34 unreachable!("Servo never report stats");
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() });
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;
51 /// Do a DOM traversal for top-down and (optionally) bottom-up processing,
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.
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>(
64 token: PreTraverseToken<E>,
65 pool: Option<&rayon::ThreadPool>,
73 .expect("Should've ensured we needed to traverse");
75 let report_stats = should_report_statistics();
76 let dump_stats = traversal.shared_context().options.dump_style_statistics;
77 let start_time = if dump_stats {
78 Some(time::precise_time_s())
83 // Declare the main-thread context, as well as the worker-thread contexts,
84 // which we may or may not instantiate. It's important to declare the worker-
85 // thread contexts first, so that they get dropped second. This matters because:
86 // * ThreadLocalContexts borrow AtomicRefCells in TLS.
87 // * Dropping a ThreadLocalContext can run SequentialTasks.
88 // * Sequential tasks may call into functions like
89 // Servo_StyleSet_GetBaseComputedValuesForElement, which instantiate a
90 // ThreadLocalStyleContext on the main thread. If the main thread
91 // ThreadLocalStyleContext has not released its TLS borrow by that point,
92 // we'll panic on double-borrow.
93 let mut tls_slots = None;
94 let mut tlc = ThreadLocalStyleContext::new(traversal.shared_context());
95 let mut context = StyleContext {
96 shared: traversal.shared_context(),
97 thread_local: &mut tlc,
100 // Process the nodes breadth-first, just like the parallel traversal does.
101 // This helps keep similar traversal characteristics for the style sharing
103 let mut discovered = VecDeque::<SendNode<E::ConcreteNode>>::with_capacity(WORK_UNIT_MAX * 2);
104 let mut depth = root.depth();
105 let mut nodes_remaining_at_current_depth = 1;
106 discovered.push_back(unsafe { SendNode::new(root.as_node()) });
107 while let Some(node) = discovered.pop_front() {
108 let mut children_to_process = 0isize;
109 let traversal_data = PerLevelTraversalData {
110 current_dom_depth: depth,
112 traversal.process_preorder(&traversal_data, &mut context, *node, |n| {
113 children_to_process += 1;
114 discovered.push_back(unsafe { SendNode::new(n) });
117 traversal.handle_postorder_traversal(
119 root.as_node().opaque(),
124 nodes_remaining_at_current_depth -= 1;
125 if nodes_remaining_at_current_depth == 0 {
127 // If there is enough work to parallelize over, and the caller allows
128 // parallelism, switch to the parallel driver. We do this only when
129 // moving to the next level in the dom so that we can pass the same
130 // depth for all the children.
131 if pool.is_some() && discovered.len() > WORK_UNIT_MAX {
132 let pool = pool.unwrap();
133 let tls = ScopedTLS::<ThreadLocalStyleContext<E>>::new(pool);
134 let root_opaque = root.as_node().opaque();
135 let drain = discovered.drain(..);
136 pool.scope_fifo(|scope| {
137 // Enable a breadth-first rayon traversal. This causes the work
138 // queue to be always FIFO, rather than FIFO for stealers and
139 // FILO for the owner (which is what rayon does by default). This
140 // ensures that we process all the elements at a given depth before
141 // proceeding to the next depth, which is important for style sharing.
142 gecko_profiler_label!(Layout, StyleComputation);
143 parallel::traverse_nodes(
145 DispatchMode::TailCall,
146 /* recursion_ok = */ true,
148 PerLevelTraversalData {
149 current_dom_depth: depth,
158 tls_slots = Some(tls.into_slots());
161 nodes_remaining_at_current_depth = discovered.len();
165 // Collect statistics from thread-locals if requested.
166 if dump_stats || report_stats {
167 let mut aggregate = mem::replace(&mut context.thread_local.statistics, Default::default());
168 let parallel = tls_slots.is_some();
169 if let Some(ref mut tls) = tls_slots {
170 for slot in tls.iter_mut() {
171 if let Some(cx) = slot.get_mut() {
172 aggregate += cx.statistics.clone();
178 report_statistics(&aggregate);
180 // dump statistics to stdout if requested
183 TraversalStatistics::new(aggregate, traversal, parallel, start_time.unwrap());
185 println!("{}", stats);