aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--components/layout/traversal.rs2
-rw-r--r--components/layout_thread/lib.rs3
-rw-r--r--components/style/bloom.rs26
-rw-r--r--components/style/dom.rs12
-rw-r--r--components/style/gecko/traversal.rs2
-rw-r--r--components/style/parallel.rs10
-rw-r--r--components/style/sequential.rs58
-rw-r--r--components/style/traversal.rs22
-rw-r--r--ports/geckolib/glue.rs3
9 files changed, 63 insertions, 75 deletions
diff --git a/components/layout/traversal.rs b/components/layout/traversal.rs
index 3c0c1763d0c..844a61527b6 100644
--- a/components/layout/traversal.rs
+++ b/components/layout/traversal.rs
@@ -56,7 +56,7 @@ impl<'a, E> DomTraversal<E> for RecalcStyleAndConstructFlows<'a>
{
type ThreadLocalContext = ScopedThreadLocalLayoutContext<E>;
- fn process_preorder(&self, traversal_data: &mut PerLevelTraversalData,
+ fn process_preorder(&self, traversal_data: &PerLevelTraversalData,
thread_local: &mut Self::ThreadLocalContext, node: E::ConcreteNode) {
// FIXME(pcwalton): Stop allocating here. Ideally this should just be
// done by the HTML parser.
diff --git a/components/layout_thread/lib.rs b/components/layout_thread/lib.rs
index 2d9b921391f..9822d7eef0b 100644
--- a/components/layout_thread/lib.rs
+++ b/components/layout_thread/lib.rs
@@ -1146,7 +1146,6 @@ impl LayoutThread {
};
let traversal = RecalcStyleAndConstructFlows::new(layout_context, traversal_driver);
- let dom_depth = Some(0); // This is always the root node.
let token = {
let stylist = &<RecalcStyleAndConstructFlows as
DomTraversal<ServoLayoutElement>>::shared_context(&traversal).stylist;
@@ -1165,7 +1164,7 @@ impl LayoutThread {
let pool = self.parallel_traversal.as_mut().unwrap();
// Parallel mode
parallel::traverse_dom::<ServoLayoutElement, RecalcStyleAndConstructFlows>(
- &traversal, element, dom_depth, token, pool);
+ &traversal, element, token, pool);
} else {
// Sequential mode
sequential::traverse_dom::<ServoLayoutElement, RecalcStyleAndConstructFlows>(
diff --git a/components/style/bloom.rs b/components/style/bloom.rs
index aba2d9fa5b8..e8ba95aeb94 100644
--- a/components/style/bloom.rs
+++ b/components/style/bloom.rs
@@ -99,7 +99,7 @@ impl<E: TElement> StyleBloom<E> {
}
/// Rebuilds the bloom filter up to the parent of the given element.
- pub fn rebuild(&mut self, mut element: E) -> usize {
+ pub fn rebuild(&mut self, mut element: E) {
self.clear();
while let Some(parent) = element.parent_element() {
@@ -110,7 +110,6 @@ impl<E: TElement> StyleBloom<E> {
// Put them in the order we expect, from root to `element`'s parent.
self.elements.reverse();
- return self.elements.len();
}
/// In debug builds, asserts that all the parents of `element` are in the
@@ -139,12 +138,12 @@ impl<E: TElement> StyleBloom<E> {
/// responsible to keep around if it wants to get an effective filter.
pub fn insert_parents_recovering(&mut self,
element: E,
- element_depth: Option<usize>)
- -> usize
+ element_depth: usize)
{
// Easy case, we're in a different restyle, or we're empty.
if self.elements.is_empty() {
- return self.rebuild(element);
+ self.rebuild(element);
+ return;
}
let parent_element = match element.parent_element() {
@@ -152,23 +151,19 @@ impl<E: TElement> StyleBloom<E> {
None => {
// Yay, another easy case.
self.clear();
- return 0;
+ return;
}
};
if self.elements.last().map(|el| **el) == Some(parent_element) {
// Ta da, cache hit, we're all done.
- return self.elements.len();
+ return;
}
- let element_depth = match element_depth {
- Some(depth) => depth,
- // If we don't know the depth of `element`, we'd rather don't try
- // fixing up the bloom filter, since it's quadratic.
- None => {
- return self.rebuild(element);
- }
- };
+ if element_depth == 0 {
+ self.clear();
+ return;
+ }
// We should've early exited above.
debug_assert!(element_depth != 0,
@@ -250,6 +245,5 @@ impl<E: TElement> StyleBloom<E> {
debug_assert_eq!(self.elements.len(), element_depth);
// We're done! Easy.
- return self.elements.len();
}
}
diff --git a/components/style/dom.rs b/components/style/dom.rs
index 602401530ca..bd201683afe 100644
--- a/components/style/dom.rs
+++ b/components/style/dom.rs
@@ -281,6 +281,18 @@ pub trait TElement : PartialEq + Debug + Sized + Copy + Clone + ElementExt + Pre
/// Get this element as a node.
fn as_node(&self) -> Self::ConcreteNode;
+ /// Returns the depth of this element in the DOM.
+ fn depth(&self) -> usize {
+ let mut depth = 0;
+ let mut curr = *self;
+ while let Some(parent) = curr.parent_element() {
+ depth += 1;
+ curr = parent;
+ }
+
+ depth
+ }
+
/// While doing a reflow, the element at the root has no parent, as far as we're
/// concerned. This method returns `None` at the reflow root.
fn layout_parent_element(self, reflow_root: OpaqueNode) -> Option<Self> {
diff --git a/components/style/gecko/traversal.rs b/components/style/gecko/traversal.rs
index 7a68f66c75f..eb7f52ad269 100644
--- a/components/style/gecko/traversal.rs
+++ b/components/style/gecko/traversal.rs
@@ -32,7 +32,7 @@ impl<'recalc, 'le> DomTraversal<GeckoElement<'le>> for RecalcStyleOnly<'recalc>
type ThreadLocalContext = ThreadLocalStyleContext<GeckoElement<'le>>;
fn process_preorder(&self,
- traversal_data: &mut PerLevelTraversalData,
+ traversal_data: &PerLevelTraversalData,
thread_local: &mut Self::ThreadLocalContext,
node: GeckoNode<'le>)
{
diff --git a/components/style/parallel.rs b/components/style/parallel.rs
index ebc08429d09..2b39eb461d0 100644
--- a/components/style/parallel.rs
+++ b/components/style/parallel.rs
@@ -39,7 +39,6 @@ pub const CHUNK_SIZE: usize = 64;
#[allow(unsafe_code)]
pub fn traverse_dom<E, D>(traversal: &D,
root: E,
- known_root_dom_depth: Option<usize>,
token: PreTraverseToken,
queue: &rayon::ThreadPool)
where E: TElement,
@@ -60,9 +59,9 @@ pub fn traverse_dom<E, D>(traversal: &D,
children.push(unsafe { SendNode::new(kid) });
}
}
- (children, known_root_dom_depth.map(|x| x + 1))
+ (children, root.depth() + 1)
} else {
- (vec![unsafe { SendNode::new(root.as_node()) }], known_root_dom_depth)
+ (vec![unsafe { SendNode::new(root.as_node()) }], root.depth())
};
let traversal_data = PerLevelTraversalData {
@@ -126,10 +125,7 @@ fn top_down_dom<'a, 'scope, E, D>(nodes: &'a [SendNode<E::ConcreteNode>],
}
}
- if let Some(ref mut depth) = traversal_data.current_dom_depth {
- *depth += 1;
- }
-
+ traversal_data.current_dom_depth += 1;
traverse_nodes(discovered_child_nodes, root, traversal_data, scope, traversal, tls);
}
diff --git a/components/style/sequential.rs b/components/style/sequential.rs
index 0cb068e6f03..38ea519e474 100644
--- a/components/style/sequential.rs
+++ b/components/style/sequential.rs
@@ -9,9 +9,12 @@
use context::TraversalStatistics;
use dom::{TElement, TNode};
use std::borrow::BorrowMut;
+use std::collections::VecDeque;
use time;
use traversal::{DomTraversal, PerLevelTraversalData, PreTraverseToken};
+struct WorkItem<N: TNode>(N, usize);
+
/// Do a sequential DOM traversal for layout or styling, generic over `D`.
pub fn traverse_dom<E, D>(traversal: &D,
root: E,
@@ -25,44 +28,37 @@ pub fn traverse_dom<E, D>(traversal: &D,
debug_assert!(!traversal.is_parallel());
debug_assert!(token.should_traverse());
- fn doit<E, D>(traversal: &D, traversal_data: &mut PerLevelTraversalData,
- thread_local: &mut D::ThreadLocalContext, node: E::ConcreteNode)
- where E: TElement,
- D: DomTraversal<E>
- {
- traversal.process_preorder(traversal_data, thread_local, node);
- if let Some(el) = node.as_element() {
- if let Some(ref mut depth) = traversal_data.current_dom_depth {
- *depth += 1;
- }
-
- traversal.traverse_children(thread_local, el, |tlc, kid| {
- doit(traversal, traversal_data, tlc, kid)
- });
-
- if let Some(ref mut depth) = traversal_data.current_dom_depth {
- *depth -= 1;
- }
- }
-
- if D::needs_postorder_traversal() {
- traversal.process_postorder(thread_local, node);
- }
- }
-
- let mut traversal_data = PerLevelTraversalData {
- current_dom_depth: None,
- };
-
+ let mut discovered = VecDeque::<WorkItem<E::ConcreteNode>>::with_capacity(16);
let mut tlc = traversal.create_thread_local_context();
+ let root_depth = root.depth();
+
if token.traverse_unstyled_children_only() {
for kid in root.as_node().children() {
if kid.as_element().map_or(false, |el| el.get_data().is_none()) {
- doit(traversal, &mut traversal_data, &mut tlc, kid);
+ discovered.push_back(WorkItem(kid, root_depth + 1));
}
}
} else {
- doit(traversal, &mut traversal_data, &mut tlc, root.as_node());
+ discovered.push_back(WorkItem(root.as_node(), root_depth));
+ }
+
+ // Process the nodes breadth-first, just like the parallel traversal does.
+ // This helps keep similar traversal characteristics for the style sharing
+ // cache.
+ while let Some(WorkItem(node, depth)) = discovered.pop_front() {
+ let mut children_to_process = 0isize;
+ let traversal_data = PerLevelTraversalData { current_dom_depth: depth };
+ traversal.process_preorder(&traversal_data, &mut tlc, node);
+
+ if let Some(el) = node.as_element() {
+ traversal.traverse_children(&mut tlc, el, |_tlc, kid| {
+ children_to_process += 1;
+ discovered.push_back(WorkItem(kid, depth + 1))
+ });
+ }
+
+ traversal.handle_postorder_traversal(&mut tlc, root.as_node().opaque(),
+ node, children_to_process);
}
// Dump statistics to stdout if requested.
diff --git a/components/style/traversal.rs b/components/style/traversal.rs
index 2e35c37904e..f5be141cb66 100644
--- a/components/style/traversal.rs
+++ b/components/style/traversal.rs
@@ -23,11 +23,11 @@ use stylist::Stylist;
/// NB: Keep this as small as possible, please!
#[derive(Clone, Debug)]
pub struct PerLevelTraversalData {
- /// The current dom depth, if known, or `None` otherwise.
+ /// The current dom depth.
///
/// This is kept with cooperation from the traversal code and the bloom
/// filter.
- pub current_dom_depth: Option<usize>,
+ pub current_dom_depth: usize,
}
bitflags! {
@@ -119,7 +119,7 @@ pub trait DomTraversal<E: TElement> : Sync {
type ThreadLocalContext: Send + BorrowMut<ThreadLocalStyleContext<E>>;
/// Process `node` on the way down, before its children have been processed.
- fn process_preorder(&self, data: &mut PerLevelTraversalData,
+ fn process_preorder(&self, data: &PerLevelTraversalData,
thread_local: &mut Self::ThreadLocalContext,
node: E::ConcreteNode);
@@ -521,7 +521,7 @@ pub fn resolve_style<E, F, G, H>(context: &mut StyleContext<E>, element: E,
#[inline]
#[allow(unsafe_code)]
pub fn recalc_style_at<E, D>(traversal: &D,
- traversal_data: &mut PerLevelTraversalData,
+ traversal_data: &PerLevelTraversalData,
context: &mut StyleContext<E>,
element: E,
mut data: &mut AtomicRefMut<ElementData>)
@@ -619,7 +619,7 @@ pub fn recalc_style_at<E, D>(traversal: &D,
}
fn compute_style<E, D>(_traversal: &D,
- traversal_data: &mut PerLevelTraversalData,
+ traversal_data: &PerLevelTraversalData,
context: &mut StyleContext<E>,
element: E,
mut data: &mut AtomicRefMut<ElementData>)
@@ -650,16 +650,8 @@ fn compute_style<E, D>(_traversal: &D,
match kind {
MatchAndCascade => {
// Ensure the bloom filter is up to date.
- let dom_depth =
- context.thread_local.bloom_filter
- .insert_parents_recovering(element,
- traversal_data.current_dom_depth);
-
- // Update the dom depth with the up-to-date dom depth.
- //
- // Note that this is always the same than the pre-existing depth,
- // but it can change from unknown to known at this step.
- traversal_data.current_dom_depth = Some(dom_depth);
+ context.thread_local.bloom_filter
+ .insert_parents_recovering(element, traversal_data.current_dom_depth);
context.thread_local.bloom_filter.assert_complete(element);
context.thread_local.statistics.elements_matched += 1;
diff --git a/ports/geckolib/glue.rs b/ports/geckolib/glue.rs
index 94f03ebbb4e..62c0294f202 100644
--- a/ports/geckolib/glue.rs
+++ b/ports/geckolib/glue.rs
@@ -193,9 +193,8 @@ fn traverse_subtree(element: GeckoElement, raw_data: RawServoStyleSetBorrowed,
};
let traversal = RecalcStyleOnly::new(shared_style_context, traversal_driver);
- let known_depth = None;
if traversal_driver.is_parallel() {
- parallel::traverse_dom(&traversal, element, known_depth, token,
+ parallel::traverse_dom(&traversal, element, token,
global_style_data.style_thread_pool.as_ref().unwrap());
} else {
sequential::traverse_dom(&traversal, element, token);
generated by cgit v1.2.3 (git 2.25.1) at 2025-05-29 20:09:47 +0000