Do the sequential traversal breadth-first.

While we're at it, we also eliminate the 'unknown' dom depth for the
bloom filter. Computing depth has negligible cost relative to the
amount of work we do setting up the bloom filter at a given depth.
Doing it once per traversal should be totally fine.

I originally separated the elimination of unknown dom depth from the
traversal changes, but I got bloom filter crashes on the intermediate
patch, presumably because I didn't properly fix the sequential traversal
for this case. Given that the final state is green, I just decided to
squash and move on.

8 files changed, 62 insertions, 73 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;