auto merge of #1700 : pcwalton/servo/deleafset, r=kmcallister

cc @pradeep90 — This removes leaf sets and should be enough to get you started.

This series of patches combines various layout passes to eliminate the overhead involved with bottom-up passes. It also makes assign-widths and flow construction run in parallel. No raw layout code was touched (except in trivial ways); rather this just changes the way methods are invoked. So the overall level of code cleanliness should remain the same. In fact, this is a (slight) net loss in LOC, and should be an improvement in safety due to not having to ensure that the nodes in the leaf sets stay alive!

This was quite a nice speedup; we're now 38% faster than Blink sequentially for style recalc on the rainbow page and 2.56x faster with 4 cores. (The relatively low speedup is because the LRU cache hits perfectly on that page sequentially.)

There is a data race somewhere in the unsafe code I added, so *do not merge yet*.

10 files changed, 386 insertions, 370 deletions

diff --git a/src/components/main/css/matching.rs b/src/components/main/css/matching.rs
index 687a08efdd4..0dd4299e5d4 100644
--- a/src/components/main/css/matching.rs
+++ b/src/components/main/css/matching.rs
@@ -5,12 +5,14 @@
 // High-level interface to CSS selector matching.
 
 use css::node_style::StyledNode;
+use layout::construct::FlowConstructor;
+use layout::context::LayoutContext;
 use layout::extra::LayoutAuxMethods;
 use layout::util::{LayoutDataAccess, LayoutDataWrapper};
-use layout::wrapper::{LayoutElement, LayoutNode};
+use layout::wrapper::{LayoutElement, LayoutNode, PostorderNodeMutTraversal, ThreadSafeLayoutNode};
 
 use extra::arc::Arc;
-use script::layout_interface::LayoutChan;
+use gfx::font_context::FontContext;
 use servo_util::cache::{Cache, LRUCache, SimpleHashCache};
 use servo_util::namespace::Null;
 use servo_util::smallvec::{SmallVec, SmallVec0, SmallVec16};
@@ -280,15 +282,17 @@ pub enum StyleSharingResult<'ln> {
 }
 
 pub trait MatchMethods {
-    /// Performs aux initialization, selector matching, and cascading sequentially.
-    fn match_and_cascade_subtree(&self,
-                                 stylist: &Stylist,
-                                 layout_chan: &LayoutChan,
-                                 applicable_declarations: &mut ApplicableDeclarations,
-                                 initial_values: &ComputedValues,
-                                 applicable_declarations_cache: &mut ApplicableDeclarationsCache,
-                                 style_sharing_candidate_cache: &mut StyleSharingCandidateCache,
-                                 parent: Option<LayoutNode>);
+    /// Performs aux initialization, selector matching, cascading, and flow construction
+    /// sequentially.
+    fn recalc_style_for_subtree(&self,
+                                stylist: &Stylist,
+                                layout_context: &mut LayoutContext,
+                                mut font_context: ~FontContext,
+                                applicable_declarations: &mut ApplicableDeclarations,
+                                applicable_declarations_cache: &mut ApplicableDeclarationsCache,
+                                style_sharing_candidate_cache: &mut StyleSharingCandidateCache,
+                                parent: Option<LayoutNode>)
+                                -> ~FontContext;
 
     fn match_node(&self,
                   stylist: &Stylist,
@@ -474,15 +478,16 @@ impl<'ln> MatchMethods for LayoutNode<'ln> {
         CannotShare(true)
     }
 
-    fn match_and_cascade_subtree(&self,
-                                 stylist: &Stylist,
-                                 layout_chan: &LayoutChan,
-                                 applicable_declarations: &mut ApplicableDeclarations,
-                                 initial_values: &ComputedValues,
-                                 applicable_declarations_cache: &mut ApplicableDeclarationsCache,
-                                 style_sharing_candidate_cache: &mut StyleSharingCandidateCache,
-                                 parent: Option<LayoutNode>) {
-        self.initialize_layout_data((*layout_chan).clone());
+    fn recalc_style_for_subtree(&self,
+                                stylist: &Stylist,
+                                layout_context: &mut LayoutContext,
+                                mut font_context: ~FontContext,
+                                applicable_declarations: &mut ApplicableDeclarations,
+                                applicable_declarations_cache: &mut ApplicableDeclarationsCache,
+                                style_sharing_candidate_cache: &mut StyleSharingCandidateCache,
+                                parent: Option<LayoutNode>)
+                                -> ~FontContext {
+        self.initialize_layout_data(layout_context.layout_chan.clone());
 
         // First, check to see whether we can share a style with someone.
         let sharing_result = unsafe {
@@ -497,6 +502,7 @@ impl<'ln> MatchMethods for LayoutNode<'ln> {
                 }
 
                 unsafe {
+                    let initial_values = layout_context.initial_css_values.get();
                     self.cascade_node(parent,
                                       initial_values,
                                       applicable_declarations,
@@ -514,14 +520,20 @@ impl<'ln> MatchMethods for LayoutNode<'ln> {
         }
 
         for kid in self.children() {
-            kid.match_and_cascade_subtree(stylist,
-                                          layout_chan,
-                                          applicable_declarations,
-                                          initial_values,
-                                          applicable_declarations_cache,
-                                          style_sharing_candidate_cache,
-                                          Some(self.clone()))
+            font_context = kid.recalc_style_for_subtree(stylist,
+                                                        layout_context,
+                                                        font_context,
+                                                        applicable_declarations,
+                                                        applicable_declarations_cache,
+                                                        style_sharing_candidate_cache,
+                                                        Some(self.clone()))
         }
+
+        // Construct flows.
+        let layout_node = ThreadSafeLayoutNode::new(self);
+        let mut flow_constructor = FlowConstructor::new(layout_context, Some(font_context));
+        flow_constructor.process(&layout_node);
+        flow_constructor.unwrap_font_context().unwrap()
     }
 
     unsafe fn cascade_node(&self,
diff --git a/src/components/main/layout/block.rs b/src/components/main/layout/block.rs
index 94c8d2c3947..079654658b9 100644
--- a/src/components/main/layout/block.rs
+++ b/src/components/main/layout/block.rs
@@ -71,7 +71,7 @@ impl BlockFlow {
     pub fn from_node(constructor: &mut FlowConstructor, node: &ThreadSafeLayoutNode, is_fixed: bool)
                      -> BlockFlow {
         BlockFlow {
-            base: BaseFlow::new(constructor.next_flow_id(), node),
+            base: BaseFlow::new((*node).clone()),
             box_: Some(Box::new(constructor, node)),
             is_root: false,
             is_fixed: is_fixed,
@@ -84,7 +84,7 @@ impl BlockFlow {
                            float_type: FloatType)
                            -> BlockFlow {
         BlockFlow {
-            base: BaseFlow::new(constructor.next_flow_id(), node),
+            base: BaseFlow::new((*node).clone()),
             box_: Some(Box::new(constructor, node)),
             is_root: false,
             is_fixed: false,
@@ -688,13 +688,12 @@ impl Flow for BlockFlow {
     /// Dual boxes consume some width first, and the remainder is assigned to all child (block)
     /// contexts.
     fn assign_widths(&mut self, ctx: &mut LayoutContext) {
-        debug!("assign_widths({}): assigning width for flow {}",
+        debug!("assign_widths({}): assigning width for flow",
                if self.is_float() {
                    "float"
                } else {
                    "block"
-               },
-               self.base.id);
+               });
 
         if self.is_root {
             debug!("Setting root position");
@@ -803,10 +802,10 @@ impl Flow for BlockFlow {
 
     fn assign_height_inorder(&mut self, ctx: &mut LayoutContext) {
         if self.is_float() {
-            debug!("assign_height_inorder_float: assigning height for float {}", self.base.id);
+            debug!("assign_height_inorder_float: assigning height for float");
             self.assign_height_float_inorder();
         } else {
-            debug!("assign_height_inorder: assigning height for block {}", self.base.id);
+            debug!("assign_height_inorder: assigning height for block");
             self.assign_height_block_base(ctx, true);
         }
     }
@@ -818,10 +817,10 @@ impl Flow for BlockFlow {
         }
 
         if self.is_float() {
-            debug!("assign_height_float: assigning height for float {}", self.base.id);
+            debug!("assign_height_float: assigning height for float");
             self.assign_height_float(ctx);
         } else {
-            debug!("assign_height: assigning height for block {}", self.base.id);
+            debug!("assign_height: assigning height for block");
             // This is the only case in which a block flow can start an inorder
             // subtraversal.
             if self.is_root && self.base.num_floats > 0 {
diff --git a/src/components/main/layout/construct.rs b/src/components/main/layout/construct.rs
index 66192647bcd..0b43884c01f 100644
--- a/src/components/main/layout/construct.rs
+++ b/src/components/main/layout/construct.rs
@@ -27,7 +27,7 @@ use layout::box_::{InlineInfo, InlineParentInfo, SpecificBoxInfo, UnscannedTextB
 use layout::box_::{UnscannedTextBoxInfo};
 use layout::context::LayoutContext;
 use layout::float_context::FloatType;
-use layout::flow::{Flow, FlowLeafSet, ImmutableFlowUtils, MutableOwnedFlowUtils};
+use layout::flow::{Flow, MutableOwnedFlowUtils};
 use layout::inline::InlineFlow;
 use layout::text::TextRunScanner;
 use layout::util::{LayoutDataAccess, OpaqueNode};
@@ -50,8 +50,6 @@ use servo_util::str::is_whitespace;
 
 use extra::url::Url;
 use extra::arc::Arc;
-
-use std::cell::RefCell;
 use std::util;
 use std::num::Zero;
 
@@ -71,11 +69,11 @@ pub enum ConstructionResult {
 }
 
 impl ConstructionResult {
-    fn destroy(&mut self, leaf_set: &FlowLeafSet) {
+    fn destroy(&mut self) {
         match *self {
             NoConstructionResult => {}
-            FlowConstructionResult(ref mut flow) => flow.destroy(leaf_set),
-            ConstructionItemConstructionResult(ref mut item) => item.destroy(leaf_set),
+            FlowConstructionResult(ref mut flow) => flow.destroy(),
+            ConstructionItemConstructionResult(ref mut item) => item.destroy(),
         }
     }
 }
@@ -91,12 +89,12 @@ enum ConstructionItem {
 }
 
 impl ConstructionItem {
-    fn destroy(&mut self, leaf_set: &FlowLeafSet) {
+    fn destroy(&mut self) {
         match *self {
             InlineBoxesConstructionItem(ref mut result) => {
                 for splits in result.splits.mut_iter() {
                     for split in splits.mut_iter() {
-                        split.destroy(leaf_set)
+                        split.destroy()
                     }
                 }
             }
@@ -149,8 +147,8 @@ struct InlineBlockSplit {
 }
 
 impl InlineBlockSplit {
-    fn destroy(&mut self, leaf_set: &FlowLeafSet) {
-        self.flow.destroy(leaf_set)
+    fn destroy(&mut self) {
+        self.flow.destroy()
     }
 }
 
@@ -222,35 +220,41 @@ pub struct FlowConstructor<'a> {
     /// The layout context.
     layout_context: &'a mut LayoutContext,
 
-    /// The next flow ID to assign.
+    /// An optional font context. If this is `None`, then we fetch the font context from the
+    /// layout context.
     ///
-    /// FIXME(pcwalton): This is going to have to be atomic; can't we do something better?
-    next_flow_id: RefCell<int>,
-
-    /// The font context.
-    font_context: ~FontContext,
-
-    /// The URL of the page.
-    url: &'a Url, 
+    /// FIXME(pcwalton): This is pretty bogus and is basically just a workaround for libgreen
+    /// having slow TLS.
+    font_context: Option<~FontContext>,
 }
 
-impl<'fc> FlowConstructor<'fc> {
+impl<'a> FlowConstructor<'a> {
     /// Creates a new flow constructor.
-    pub fn init<'a>(layout_context: &'a mut LayoutContext, url: &'a Url) -> FlowConstructor<'a> {
-        let font_context = ~FontContext::new(layout_context.font_context_info.clone());
+    pub fn new(layout_context: &'a mut LayoutContext, font_context: Option<~FontContext>)
+               -> FlowConstructor<'a> {
         FlowConstructor {
             layout_context: layout_context,
-            next_flow_id: RefCell::new(0),
             font_context: font_context,
-            url: url,
         }
     }
 
-    /// Returns the next flow ID and bumps the internal counter.
-    pub fn next_flow_id(&self) -> int {
-        let id = self.next_flow_id.get();
-        self.next_flow_id.set(id + 1);
-        id
+    fn font_context<'a>(&'a mut self) -> &'a mut FontContext {
+        match self.font_context {
+            Some(ref mut font_context) => {
+                let font_context: &mut FontContext = *font_context;
+                font_context
+            }
+            None => self.layout_context.font_context(),
+        }
+    }
+
+    /// Destroys this flow constructor and retrieves the font context.
+    pub fn unwrap_font_context(self) -> Option<~FontContext> {
+        let FlowConstructor {
+            font_context,
+            ..
+        } = self;
+        font_context
     }
 
     /// Builds the `ImageBoxInfo` for the given image. This is out of line to guide inlining.
@@ -272,7 +276,8 @@ impl<'fc> FlowConstructor<'fc> {
             ElementNodeTypeId(HTMLImageElementTypeId) => self.build_box_info_for_image(node, node.image_url()),
             ElementNodeTypeId(HTMLIframeElementTypeId) => IframeBox(IframeBoxInfo::new(node)),
             ElementNodeTypeId(HTMLObjectElementTypeId) => {
-                self.build_box_info_for_image(node, node.get_object_data(self.url))
+                let data = node.get_object_data(&self.layout_context.url);
+                self.build_box_info_for_image(node, data)
             }
             TextNodeTypeId => UnscannedTextBox(UnscannedTextBoxInfo::new(node)),
             _ => GenericBox,
@@ -292,9 +297,9 @@ impl<'fc> FlowConstructor<'fc> {
             return
         }
 
-        let mut inline_flow = ~InlineFlow::from_boxes(self.next_flow_id(), node, boxes) as ~Flow;
-        inline_flow.mark_as_leaf(self.layout_context.flow_leaf_set.get());
-        TextRunScanner::new().scan_for_runs(self.font_context, inline_flow);
+        let mut inline_flow = ~InlineFlow::from_boxes((*node).clone(), boxes) as ~Flow;
+        TextRunScanner::new().scan_for_runs(self.font_context(), inline_flow);
+        inline_flow.finish(self.layout_context);
 
         flow.add_new_child(inline_flow)
     }
@@ -399,11 +404,7 @@ impl<'fc> FlowConstructor<'fc> {
                                                      node);
 
         // The flow is done. If it ended up with no kids, add the flow to the leaf set.
-        if flow.child_count() == 0 {
-            flow.mark_as_leaf(self.layout_context.flow_leaf_set.get())
-        } else {
-            flow.mark_as_nonleaf()
-        }
+        flow.finish(self.layout_context)
     }
 
     /// Builds a flow for a node with `display: block`. This yields a `BlockFlow` with possibly
@@ -548,7 +549,7 @@ impl<'fc> FlowConstructor<'fc> {
                                         parent_node: &ThreadSafeLayoutNode) {
         let parent_box = Box::new(self, parent_node);
         let font_style = parent_box.font_style();
-        let font_group = self.font_context.get_resolved_font_for_style(&font_style);
+        let font_group = self.font_context().get_resolved_font_for_style(&font_style);
         let (font_ascent,font_descent) = font_group.borrow().with_mut( |fg| {
             fg.fonts[0].borrow().with_mut( |font| {
                 (font.metrics.ascent,font.metrics.descent)
@@ -657,7 +658,7 @@ impl<'a> PostorderNodeMutTraversal for FlowConstructor<'a> {
             (display::none, _, _) => {
                 for child in node.children() {
                     let mut old_result = child.swap_out_construction_result();
-                    old_result.destroy(self.layout_context.flow_leaf_set.get())
+                    old_result.destroy()
                 }
             }
 
diff --git a/src/components/main/layout/context.rs b/src/components/main/layout/context.rs
index 61b8c3e03e6..d2ce78bd3d8 100644
--- a/src/components/main/layout/context.rs
+++ b/src/components/main/layout/context.rs
@@ -5,11 +5,10 @@
 //! Data needed by the layout task.
 
 use css::matching::{ApplicableDeclarationsCache, StyleSharingCandidateCache};
-use layout::flow::FlowLeafSet;
 use layout::util::OpaqueNode;
-use layout::wrapper::DomLeafSet;
 
 use extra::arc::{Arc, MutexArc};
+use extra::url::Url;
 use geom::size::Size2D;
 use gfx::font_context::{FontContext, FontContextInfo};
 use green::task::GreenTask;
@@ -17,6 +16,7 @@ use script::layout_interface::LayoutChan;
 use servo_msg::constellation_msg::ConstellationChan;
 use servo_net::local_image_cache::LocalImageCache;
 use servo_util::geometry::Au;
+use servo_util::opts::Opts;
 use std::cast;
 use std::ptr;
 use std::rt::Runtime;
@@ -47,15 +47,9 @@ pub struct LayoutContext {
     /// A channel up to the constellation.
     constellation_chan: ConstellationChan,
 
-    /// The set of leaf DOM nodes.
-    dom_leaf_set: Arc<DomLeafSet>,
-
     /// A channel up to the layout task.
     layout_chan: LayoutChan,
 
-    /// The set of leaf flows.
-    flow_leaf_set: Arc<FlowLeafSet>,
-
     /// Information needed to construct a font context.
     font_context_info: FontContextInfo,
 
@@ -69,18 +63,26 @@ pub struct LayoutContext {
 
     /// The root node at which we're starting the layout.
     reflow_root: OpaqueNode,
+
+    /// The URL.
+    url: Url,
+
+    /// The command line options.
+    opts: Opts,
 }
 
 impl LayoutContext {
     pub fn font_context<'a>(&'a mut self) -> &'a mut FontContext {
         // Sanity check.
-        let mut task = Local::borrow(None::<Task>);
-        match task.get().maybe_take_runtime::<GreenTask>() {
-            Some(green) => {
-                task.get().put_runtime(green as ~Runtime);
-                fail!("can't call this on a green task!")
+        {
+            let mut task = Local::borrow(None::<Task>);
+            match task.get().maybe_take_runtime::<GreenTask>() {
+                Some(green) => {
+                    task.get().put_runtime(green as ~Runtime);
+                    fail!("can't call this on a green task!")
+                }
+                None => {}
             }
-            None => {}
         }
 
         unsafe {
diff --git a/src/components/main/layout/flow.rs b/src/components/main/layout/flow.rs
index 8f86bd9545c..b4a14a53ad9 100644
--- a/src/components/main/layout/flow.rs
+++ b/src/components/main/layout/flow.rs
@@ -33,7 +33,7 @@ use layout::display_list_builder::{DisplayListBuilder, ExtraDisplayListData};
 use layout::float_context::{FloatContext, Invalid};
 use layout::incremental::RestyleDamage;
 use layout::inline::InlineFlow;
-use layout::parallel::{FlowParallelInfo, UnsafeFlow};
+use layout::parallel::FlowParallelInfo;
 use layout::parallel;
 use layout::wrapper::ThreadSafeLayoutNode;
 use layout::flow_list::{FlowList, Link, Rawlink, FlowListIterator, MutFlowListIterator};
@@ -45,7 +45,6 @@ use geom::rect::Rect;
 use gfx::display_list::{ClipDisplayItemClass, DisplayListCollection, DisplayList};
 use layout::display_list_builder::ToGfxColor;
 use gfx::color::Color;
-use servo_util::concurrentmap::{ConcurrentHashMap, ConcurrentHashMapIterator};
 use servo_util::geometry::Au;
 use std::cast;
 use std::cell::RefCell;
@@ -215,7 +214,7 @@ pub trait MutableFlowUtils {
                           -> bool;
 
     /// Destroys the flow.
-    fn destroy(self, leaf_set: &FlowLeafSet);
+    fn destroy(self);
 }
 
 pub trait MutableOwnedFlowUtils {
@@ -223,15 +222,16 @@ pub trait MutableOwnedFlowUtils {
     /// it's present.
     fn add_new_child(&mut self, new_child: ~Flow);
 
-    /// Marks the flow as a leaf. The flow must not have children and must not be marked as a
-    /// nonleaf.
-    fn mark_as_leaf(&mut self, leaf_set: &FlowLeafSet);
-
-    /// Marks the flow as a nonleaf. The flow must not be marked as a leaf.
-    fn mark_as_nonleaf(&mut self);
+    /// Finishes a flow. Once a flow is finished, no more child flows or boxes may be added to it.
+    /// This will normally run the bubble-widths (minimum and preferred -- i.e. intrinsic -- width)
+    /// calculation, unless the global `bubble_widths_separately` flag is on.
+    ///
+    /// All flows must be finished at some point, or they will not have their intrinsic widths
+    /// properly computed. (This is not, however, a memory safety problem.)
+    fn finish(&mut self, context: &mut LayoutContext);
 
     /// Destroys the flow.
-    fn destroy(&mut self, leaf_set: &FlowLeafSet);
+    fn destroy(&mut self);
 }
 
 pub enum FlowClass {
@@ -455,13 +455,6 @@ bitfield!(FlowFlags, override_overline, set_override_overline, 0b0000_0100)
 // NB: If you update this, you need to update TEXT_DECORATION_OVERRIDE_BITMASK.
 bitfield!(FlowFlags, override_line_through, set_override_line_through, 0b0000_1000)
 
-// Whether this flow is marked as a leaf. Flows marked as leaves must not have any more kids added
-// to them.
-bitfield!(FlowFlags, is_leaf, set_is_leaf, 0b0100_0000)
-
-// Whether this flow is marked as a nonleaf. Flows marked as nonleaves must have children.
-bitfield!(FlowFlags, is_nonleaf, set_is_nonleaf, 0b1000_0000)
-
 // The text alignment for this flow.
 impl FlowFlags {
     #[inline]
@@ -499,9 +492,6 @@ pub struct BaseFlow {
     next_sibling: Link,
     prev_sibling: Rawlink,
 
-    /* TODO (Issue #87): debug only */
-    id: int,
-
     /* layout computations */
     // TODO: min/pref and position are used during disjoint phases of
     // layout; maybe combine into a single enum to save space.
@@ -563,7 +553,7 @@ impl Iterator<@Box> for BoxIterator {
 
 impl BaseFlow {
     #[inline]
-    pub fn new(id: int, node: &ThreadSafeLayoutNode) -> BaseFlow {
+    pub fn new(node: ThreadSafeLayoutNode) -> BaseFlow {
         let style = node.style();
         BaseFlow {
             restyle_damage: node.restyle_damage(),
@@ -572,8 +562,6 @@ impl BaseFlow {
             next_sibling: None,
             prev_sibling: Rawlink::none(),
 
-            id: id,
-
             min_width: Au::new(0),
             pref_width: Au::new(0),
             position: Au::zero_rect(),
@@ -740,7 +728,7 @@ impl<'a> MutableFlowUtils for &'a mut Flow {
                           mut index: uint,
                           lists: &RefCell<DisplayListCollection<E>>)
                           -> bool {
-        debug!("Flow: building display list for f{}", base(self).id);
+        debug!("Flow: building display list");
         index = match self.class() {
             BlockFlowClass => self.as_block().build_display_list_block(builder, container_block_size, dirty, index, lists),
             InlineFlowClass => self.as_inline().build_display_list_inline(builder, container_block_size, dirty, index, lists),
@@ -797,18 +785,9 @@ impl<'a> MutableFlowUtils for &'a mut Flow {
     }
 
     /// Destroys the flow.
-    fn destroy(self, leaf_set: &FlowLeafSet) {
-        let is_leaf = {
-            let base = mut_base(self);
-            base.children.len() == 0
-        };
-
-        if is_leaf {
-            leaf_set.remove(self);
-        } else {
-            for kid in child_iter(self) {
-                kid.destroy(leaf_set)
-            }
+    fn destroy(self) {
+        for kid in child_iter(self) {
+            kid.destroy()
         }
 
         mut_base(self).destroyed = true
@@ -824,84 +803,26 @@ impl MutableOwnedFlowUtils for ~Flow {
         }
 
         let base = mut_base(*self);
-        assert!(!base.flags_info.flags.is_leaf());
         base.children.push_back(new_child);
         let _ = base.parallel.children_count.fetch_add(1, Relaxed);
     }
 
-    /// Marks the flow as a leaf. The flow must not have children and must not be marked as a
-    /// nonleaf.
-    fn mark_as_leaf(&mut self, leaf_set: &FlowLeafSet) {
-        {
-            let base = mut_base(*self);
-            if base.flags_info.flags.is_nonleaf() {
-                fail!("attempted to mark a nonleaf flow as a leaf!")
-            }
-            if base.children.len() != 0 {
-                fail!("attempted to mark a flow with children as a leaf!")
-            }
-            base.flags_info.flags.set_is_leaf(true)
-        }
-        let self_borrowed: &Flow = *self;
-        leaf_set.insert(self_borrowed);
-    }
-
-    /// Marks the flow as a nonleaf. The flow must not be marked as a leaf.
-    fn mark_as_nonleaf(&mut self) {
-        let base = mut_base(*self);
-        if base.flags_info.flags.is_leaf() {
-            fail!("attempted to mark a leaf flow as a nonleaf!")
+    /// Finishes a flow. Once a flow is finished, no more child flows or boxes may be added to it.
+    /// This will normally run the bubble-widths (minimum and preferred -- i.e. intrinsic -- width)
+    /// calculation, unless the global `bubble_widths_separately` flag is on.
+    ///
+    /// All flows must be finished at some point, or they will not have their intrinsic widths
+    /// properly computed. (This is not, however, a memory safety problem.)
+    fn finish(&mut self, context: &mut LayoutContext) {
+        if !context.opts.bubble_widths_separately {
+            self.bubble_widths(context)
         }
-        base.flags_info.flags.set_is_nonleaf(true)
-        // We don't check to make sure there are no children as they might be added later.
     }
 
     /// Destroys the flow.
-    fn destroy(&mut self, leaf_set: &FlowLeafSet) {
+    fn destroy(&mut self) {
         let self_borrowed: &mut Flow = *self;
-        self_borrowed.destroy(leaf_set);
+        self_borrowed.destroy();
     }
 }
 
-/// Keeps track of the leaves of the flow tree. This is used to efficiently start bottom-up
-/// parallel traversals.
-pub struct FlowLeafSet {
-    priv set: ConcurrentHashMap<UnsafeFlow,()>,
-}
-
-impl FlowLeafSet {
-    /// Creates a new flow leaf set.
-    pub fn new() -> FlowLeafSet {
-        FlowLeafSet {
-            set: ConcurrentHashMap::with_locks_and_buckets(64, 256),
-        }
-    }
-
-    /// Inserts a newly-created flow into the leaf set.
-    fn insert(&self, flow: &Flow) {
-        self.set.insert(parallel::borrowed_flow_to_unsafe_flow(flow), ());
-    }
-
-    /// Removes a flow from the leaf set. Asserts that the flow was indeed in the leaf set. (This
-    /// invariant is needed for memory safety, as there must always be exactly one leaf set.)
-    fn remove(&self, flow: &Flow) {
-        if !self.contains(flow) {
-            fail!("attempted to remove a flow from the leaf set that wasn't in the set!")
-        }
-        let flow = parallel::borrowed_flow_to_unsafe_flow(flow);
-        self.set.remove(&flow);
-    }
-
-    pub fn contains(&self, flow: &Flow) -> bool {
-        let flow = parallel::borrowed_flow_to_unsafe_flow(flow);
-        self.set.contains_key(&flow)
-    }
-
-    pub fn clear(&self) {
-        self.set.clear()
-    }
-
-    pub fn iter<'a>(&'a self) -> ConcurrentHashMapIterator<'a,UnsafeFlow,()> {
-        self.set.iter()
-    }
-}
diff --git a/src/components/main/layout/inline.rs b/src/components/main/layout/inline.rs
index 9343804366c..e6a2643536f 100644
--- a/src/components/main/layout/inline.rs
+++ b/src/components/main/layout/inline.rs
@@ -84,8 +84,8 @@ impl LineboxScanner {
         self.floats.clone()
     }
 
-    fn reset_scanner(&mut self, flow: &mut InlineFlow) {
-        debug!("Resetting line box scanner's state for flow f{:d}.", flow.base.id);
+    fn reset_scanner(&mut self) {
+        debug!("Resetting line box scanner's state for flow.");
         self.lines = ~[];
         self.new_boxes = ~[];
         self.cur_y = Au::new(0);
@@ -99,7 +99,7 @@ impl LineboxScanner {
     }
 
     pub fn scan_for_lines(&mut self, flow: &mut InlineFlow) {
-        self.reset_scanner(flow);
+        self.reset_scanner();
 
         loop {
             // acquire the next box to lay out from work list or box list
@@ -142,9 +142,8 @@ impl LineboxScanner {
     }
 
     fn swap_out_results(&mut self, flow: &mut InlineFlow) {
-        debug!("LineboxScanner: Propagating scanned lines[n={:u}] to inline flow f{:d}",
-               self.lines.len(),
-               flow.base.id);
+        debug!("LineboxScanner: Propagating scanned lines[n={:u}] to inline flow",
+               self.lines.len());
 
         util::swap(&mut flow.boxes, &mut self.new_boxes);
         util::swap(&mut flow.lines, &mut self.lines);
@@ -466,9 +465,9 @@ pub struct InlineFlow {
 }
 
 impl InlineFlow {
-    pub fn from_boxes(id: int, node: &ThreadSafeLayoutNode, boxes: ~[Box]) -> InlineFlow {
+    pub fn from_boxes(node: ThreadSafeLayoutNode, boxes: ~[Box]) -> InlineFlow {
         InlineFlow {
-            base: BaseFlow::new(id, node),
+            base: BaseFlow::new(node),
             boxes: boxes,
             lines: ~[],
             elems: ElementMapping::new(),
@@ -497,9 +496,7 @@ impl InlineFlow {
 
         // TODO(#228): Once we form line boxes and have their cached bounds, we can be smarter and
         // not recurse on a line if nothing in it can intersect the dirty region.
-        debug!("Flow[{:d}]: building display list for {:u} inline boxes",
-               self.base.id,
-               self.boxes.len());
+        debug!("Flow: building display list for {:u} inline boxes", self.boxes.len());
 
         for box_ in self.boxes.iter() {
             let rel_offset: Point2D<Au> = box_.relative_position(container_block_size);
@@ -636,7 +633,7 @@ impl Flow for InlineFlow {
         let mut pref_width = Au::new(0);
 
         for box_ in self.boxes.iter() {
-            debug!("Flow[{:d}]: measuring {:s}", self.base.id, box_.debug_str());
+            debug!("Flow: measuring {:s}", box_.debug_str());
             box_.compute_borders(box_.style());
             let (this_minimum_width, this_preferred_width) =
                 box_.minimum_and_preferred_widths();
@@ -690,7 +687,7 @@ impl Flow for InlineFlow {
     }
 
     fn assign_height(&mut self, _: &mut LayoutContext) {
-        debug!("assign_height_inline: assigning height for flow {}", self.base.id);
+        debug!("assign_height_inline: assigning height for flow");
 
         // Divide the boxes into lines.
         //
diff --git a/src/components/main/layout/layout_task.rs b/src/components/main/layout/layout_task.rs
index 70abe34b82c..2f70d0ea499 100644
--- a/src/components/main/layout/layout_task.rs
+++ b/src/components/main/layout/layout_task.rs
@@ -9,18 +9,17 @@ use css::matching::{ApplicableDeclarations, ApplicableDeclarationsCache, MatchMe
 use css::matching::{StyleSharingCandidateCache};
 use css::select::new_stylist;
 use css::node_style::StyledNode;
-use layout::construct::{FlowConstructionResult, FlowConstructor, NoConstructionResult};
+use layout::construct::{FlowConstructionResult, NoConstructionResult};
 use layout::context::LayoutContext;
 use layout::display_list_builder::{DisplayListBuilder, ToGfxColor};
-use layout::flow::{Flow, FlowLeafSet, ImmutableFlowUtils, MutableFlowUtils, MutableOwnedFlowUtils};
+use layout::flow::{Flow, ImmutableFlowUtils, MutableFlowUtils, MutableOwnedFlowUtils};
 use layout::flow::{PreorderFlowTraversal, PostorderFlowTraversal};
 use layout::flow;
 use layout::incremental::RestyleDamage;
-use layout::parallel::{AssignHeightsAndStoreOverflowTraversalKind, BubbleWidthsTraversalKind};
-use layout::parallel::{PaddedUnsafeFlow};
+use layout::parallel::PaddedUnsafeFlow;
 use layout::parallel;
 use layout::util::{LayoutDataAccess, OpaqueNode, LayoutDataWrapper};
-use layout::wrapper::{DomLeafSet, LayoutNode, TLayoutNode, ThreadSafeLayoutNode};
+use layout::wrapper::{LayoutNode, TLayoutNode, ThreadSafeLayoutNode};
 
 use extra::url::Url;
 use extra::arc::{Arc, MutexArc};
@@ -28,7 +27,7 @@ use geom::rect::Rect;
 use geom::size::Size2D;
 use gfx::display_list::{ClipDisplayItemClass, DisplayItem, DisplayItemIterator};
 use gfx::display_list::{DisplayList, DisplayListCollection};
-use gfx::font_context::FontContextInfo;
+use gfx::font_context::{FontContext, FontContextInfo};
 use gfx::render_task::{RenderMsg, RenderChan, RenderLayer};
 use gfx::{render_task, color};
 use script::dom::bindings::js::JS;
@@ -39,7 +38,7 @@ use script::layout_interface::{AddStylesheetMsg, ContentBoxQuery};
 use script::layout_interface::{ContentBoxesQuery, ContentBoxesResponse, ExitNowMsg, LayoutQuery};
 use script::layout_interface::{HitTestQuery, ContentBoxResponse, HitTestResponse, MouseOverQuery, MouseOverResponse};
 use script::layout_interface::{ContentChangedDocumentDamage, LayoutChan, Msg, PrepareToExitMsg};
-use script::layout_interface::{QueryMsg, ReapLayoutDataMsg, Reflow, ReflowDocumentDamage, UntrustedNodeAddress};
+use script::layout_interface::{QueryMsg, ReapLayoutDataMsg, Reflow, UntrustedNodeAddress};
 use script::layout_interface::{ReflowForDisplay, ReflowMsg};
 use script::script_task::{ReflowCompleteMsg, ScriptChan, SendEventMsg};
 use servo_msg::constellation_msg::{ConstellationChan, PipelineId, Failure, FailureMsg};
@@ -87,12 +86,6 @@ pub struct LayoutTask {
     /// The local image cache.
     local_image_cache: MutexArc<LocalImageCache>,
 
-    /// The set of leaves in the DOM tree.
-    dom_leaf_set: Arc<DomLeafSet>,
-
-    /// The set of leaves in the flow tree.
-    flow_leaf_set: Arc<FlowLeafSet>,
-
     /// The size of the viewport.
     screen_size: Size2D<Au>,
 
@@ -195,12 +188,14 @@ impl<'a> PostorderFlowTraversal for BubbleWidthsTraversal<'a> {
 }
 
 /// The assign-widths traversal. In Gecko this corresponds to `Reflow`.
-struct AssignWidthsTraversal<'a>(&'a mut LayoutContext);
+pub struct AssignWidthsTraversal<'a> {
+    layout_context: &'a mut LayoutContext,
+}
 
 impl<'a> PreorderFlowTraversal for AssignWidthsTraversal<'a> {
     #[inline]
     fn process(&mut self, flow: &mut Flow) -> bool {
-        flow.assign_widths(**self);
+        flow.assign_widths(self.layout_context);
         true
     }
 }
@@ -304,8 +299,6 @@ impl LayoutTask {
             image_cache_task: image_cache_task.clone(),
             local_image_cache: local_image_cache,
             screen_size: screen_size,
-            dom_leaf_set: Arc::new(DomLeafSet::new()),
-            flow_leaf_set: Arc::new(FlowLeafSet::new()),
 
             display_list_collection: None,
             stylist: ~new_stylist(),
@@ -324,7 +317,7 @@ impl LayoutTask {
     }
 
     // Create a layout context for use in building display lists, hit testing, &c.
-    fn build_layout_context(&self, reflow_root: &LayoutNode) -> LayoutContext {
+    fn build_layout_context(&self, reflow_root: &LayoutNode, url: &Url) -> LayoutContext {
         let font_context_info = FontContextInfo {
             backend: self.opts.render_backend,
             needs_font_list: true,
@@ -335,13 +328,13 @@ impl LayoutTask {
             image_cache: self.local_image_cache.clone(),
             screen_size: self.screen_size.clone(),
             constellation_chan: self.constellation_chan.clone(),
-            dom_leaf_set: self.dom_leaf_set.clone(),
-            flow_leaf_set: self.flow_leaf_set.clone(),
             layout_chan: self.chan.clone(),
             font_context_info: font_context_info,
             stylist: &*self.stylist,
             initial_css_values: self.initial_css_values.clone(),
+            url: (*url).clone(),
             reflow_root: OpaqueNode::from_layout_node(reflow_root),
+            opts: self.opts.clone(),
         }
     }
 
@@ -423,17 +416,8 @@ impl LayoutTask {
         self.stylist.add_stylesheet(sheet, AuthorOrigin)
     }
 
-    /// Builds the flow tree.
-    ///
-    /// This corresponds to the various `nsCSSFrameConstructor` methods in Gecko or
-    /// `createRendererIfNeeded` in WebKit. Note, however that in WebKit `createRendererIfNeeded`
-    /// is intertwined with selector matching, making it difficult to compare directly. It is
-    /// marked `#[inline(never)]` to aid benchmarking in sampling profilers.
-    #[inline(never)]
-    fn construct_flow_tree(&self, layout_context: &mut LayoutContext, node: &mut LayoutNode, url: &Url) -> ~Flow {
-        let mut node = ThreadSafeLayoutNode::new(node);
-        node.traverse_postorder_mut(&mut FlowConstructor::init(layout_context, url));
-
+    /// Retrieves the flow tree root from the root node.
+    fn get_layout_root(&self, node: LayoutNode) -> ~Flow {
         let mut layout_data_ref = node.mutate_layout_data();
         let result = match *layout_data_ref.get() {
             Some(ref mut layout_data) => {
@@ -457,7 +441,7 @@ impl LayoutTask {
     fn solve_constraints(&mut self,
                          layout_root: &mut Flow,
                          layout_context: &mut LayoutContext) {
-        {
+        if layout_context.opts.bubble_widths_separately {
             let mut traversal = BubbleWidthsTraversal {
                 layout_context: layout_context,
             };
@@ -469,7 +453,12 @@ impl LayoutTask {
         // recompute them every time.
         // NOTE: this currently computes borders, so any pruning should separate that operation
         // out.
-        layout_root.traverse_preorder(&mut AssignWidthsTraversal(layout_context));
+        {
+            let mut traversal = AssignWidthsTraversal {
+                layout_context: layout_context,
+            };
+            layout_root.traverse_preorder(&mut traversal);
+        }
 
         // FIXME(pcwalton): Prune this pass as well.
         {
@@ -486,28 +475,24 @@ impl LayoutTask {
     /// benchmarked against those two. It is marked `#[inline(never)]` to aid profiling.
     #[inline(never)]
     fn solve_constraints_parallel(&mut self,
-                                  layout_root: &mut Flow,
+                                  layout_root: &mut ~Flow,
                                   layout_context: &mut LayoutContext) {
+        if layout_context.opts.bubble_widths_separately {
+            let mut traversal = BubbleWidthsTraversal {
+                layout_context: layout_context,
+            };
+            layout_root.traverse_postorder(&mut traversal);
+        }
+
         match self.parallel_traversal {
             None => fail!("solve_contraints_parallel() called with no parallel traversal ready"),
             Some(ref mut traversal) => {
-                parallel::traverse_flow_tree(BubbleWidthsTraversalKind,
-                                             &self.flow_leaf_set,
-                                             self.profiler_chan.clone(),
-                                             layout_context,
-                                             traversal);
-
                 // NOTE: this currently computes borders, so any pruning should separate that
                 // operation out.
-                // TODO(pcwalton): Run this in parallel as well. This will require a bit more work
-                // because this is a top-down traversal, unlike the others.
-                layout_root.traverse_preorder(&mut AssignWidthsTraversal(layout_context));
-
-                parallel::traverse_flow_tree(AssignHeightsAndStoreOverflowTraversalKind,
-                                             &self.flow_leaf_set,
-                                             self.profiler_chan.clone(),
-                                             layout_context,
-                                             traversal);
+                parallel::traverse_flow_tree_preorder(layout_root,
+                                                      self.profiler_chan.clone(),
+                                                      layout_context,
+                                                      traversal);
             }
         }
     }
@@ -560,45 +545,51 @@ impl LayoutTask {
         self.screen_size = current_screen_size;
 
         // Create a layout context for use throughout the following passes.
-        let mut layout_ctx = self.build_layout_context(node);
+        let mut layout_ctx = self.build_layout_context(node, &data.url);
+
+        // Create a font context, if this is sequential.
+        //
+        // FIXME(pcwalton): This is a pretty bogus thing to do. Essentially this is a workaround
+        // for libgreen having slow TLS.
+        let mut font_context_opt = if self.parallel_traversal.is_none() {
+            Some(~FontContext::new(layout_ctx.font_context_info.clone()))
+        } else {
+            None
+        };
+
+        // Create a font context, if this is sequential.
+        //
+        // FIXME(pcwalton): This is a pretty bogus thing to do. Essentially this is a workaround
+        // for libgreen having slow TLS.
+        let mut font_context_opt = if self.parallel_traversal.is_none() {
+            Some(~FontContext::new(layout_ctx.font_context_info.clone()))
+        } else {
+            None
+        };
 
         let mut layout_root = profile(time::LayoutStyleRecalcCategory,
                                       self.profiler_chan.clone(),
                                       || {
-            // Perform CSS selector matching if necessary.
-            match data.damage.level {
-                ReflowDocumentDamage => {}
-                _ => {
-                    profile(time::LayoutSelectorMatchCategory, self.profiler_chan.clone(), || {
-                        match self.parallel_traversal {
-                            None => {
-                                let mut applicable_declarations = ApplicableDeclarations::new();
-                                let mut applicable_declarations_cache =
-                                    ApplicableDeclarationsCache::new();
-                                let mut style_sharing_candidate_cache =
-                                    StyleSharingCandidateCache::new();
-                                node.match_and_cascade_subtree(self.stylist,
-                                                               &layout_ctx.layout_chan,
-                                                               &mut applicable_declarations,
-                                                               layout_ctx.initial_css_values.get(),
-                                                               &mut applicable_declarations_cache,
-                                                               &mut style_sharing_candidate_cache,
-                                                               None)
-                            }
-                            Some(ref mut traversal) => {
-                                parallel::match_and_cascade_subtree(node,
-                                                                    &mut layout_ctx,
-                                                                    traversal)
-                            }
-                        }
-                    })
+            // Perform CSS selector matching and flow construction.
+            match self.parallel_traversal {
+                None => {
+                    let mut applicable_declarations = ApplicableDeclarations::new();
+                    let mut applicable_declarations_cache = ApplicableDeclarationsCache::new();
+                    let mut style_sharing_candidate_cache = StyleSharingCandidateCache::new();
+                    drop(node.recalc_style_for_subtree(self.stylist,
+                                                       &mut layout_ctx,
+                                                       font_context_opt.take_unwrap(),
+                                                       &mut applicable_declarations,
+                                                       &mut applicable_declarations_cache,
+                                                       &mut style_sharing_candidate_cache,
+                                                       None))
+                }
+                Some(ref mut traversal) => {
+                    parallel::recalc_style_for_subtree(node, &mut layout_ctx, traversal)
                 }
             }
 
-            // Construct the flow tree.
-            profile(time::LayoutTreeBuilderCategory,
-                    self.profiler_chan.clone(),
-                    || self.construct_flow_tree(&mut layout_ctx, node, &data.url))
+            self.get_layout_root((*node).clone())
         });
 
         // Verification of the flow tree, which ensures that all nodes were either marked as leaves
@@ -624,7 +615,7 @@ impl LayoutTask {
                 }
                 Some(_) => {
                     // Parallel mode.
-                    self.solve_constraints_parallel(layout_root, &mut layout_ctx)
+                    self.solve_constraints_parallel(&mut layout_root, &mut layout_ctx)
                 }
             }
         });
@@ -685,7 +676,7 @@ impl LayoutTask {
             });
         }
 
-        layout_root.destroy(self.flow_leaf_set.get());
+        layout_root.destroy();
 
         // Tell script that we're done.
         //
diff --git a/src/components/main/layout/parallel.rs b/src/components/main/layout/parallel.rs
index f601c3a5dd7..5e4da051dbc 100644
--- a/src/components/main/layout/parallel.rs
+++ b/src/components/main/layout/parallel.rs
@@ -7,15 +7,17 @@
 //! This code is highly unsafe. Keep this file small and easy to audit.
 
 use css::matching::{ApplicableDeclarations, CannotShare, MatchMethods, StyleWasShared};
+use layout::construct::FlowConstructor;
 use layout::context::LayoutContext;
 use layout::extra::LayoutAuxMethods;
-use layout::flow::{Flow, FlowLeafSet, PostorderFlowTraversal};
+use layout::flow::{Flow, PreorderFlowTraversal, PostorderFlowTraversal};
 use layout::flow;
-use layout::layout_task::{AssignHeightsAndStoreOverflowTraversal, BubbleWidthsTraversal};
+use layout::layout_task::{AssignHeightsAndStoreOverflowTraversal, AssignWidthsTraversal};
+use layout::layout_task::{BubbleWidthsTraversal};
 use layout::util::{LayoutDataAccess, OpaqueNode};
-use layout::wrapper::{layout_node_to_unsafe_layout_node, LayoutNode, UnsafeLayoutNode};
+use layout::wrapper::{layout_node_to_unsafe_layout_node, LayoutNode, PostorderNodeMutTraversal};
+use layout::wrapper::{ThreadSafeLayoutNode, UnsafeLayoutNode};
 
-use extra::arc::Arc;
 use servo_util::time::{ProfilerChan, profile};
 use servo_util::time;
 use servo_util::workqueue::{WorkQueue, WorkUnit, WorkerProxy};
@@ -24,11 +26,6 @@ use std::ptr;
 use std::sync::atomics::{AtomicInt, Relaxed, SeqCst};
 use style::{Stylist, TNode};
 
-pub enum TraversalKind {
-    BubbleWidthsTraversalKind,
-    AssignHeightsAndStoreOverflowTraversalKind,
-}
-
 #[allow(dead_code)]
 fn static_assertion(node: UnsafeLayoutNode) {
     unsafe {
@@ -122,7 +119,9 @@ impl FlowParallelInfo {
 
 /// A parallel bottom-up flow traversal.
 trait ParallelPostorderFlowTraversal : PostorderFlowTraversal {
-    fn run_parallel(&mut self, mut unsafe_flow: UnsafeFlow) {
+    fn run_parallel(&mut self,
+                    mut unsafe_flow: UnsafeFlow,
+                    _: &mut WorkerProxy<*mut LayoutContext,PaddedUnsafeFlow>) {
         loop {
             unsafe {
                 // Get a real flow.
@@ -161,12 +160,64 @@ trait ParallelPostorderFlowTraversal : PostorderFlowTraversal {
     }
 }
 
+/// A parallel top-down flow traversal.
+trait ParallelPreorderFlowTraversal : PreorderFlowTraversal {
+    fn run_parallel(&mut self,
+                    unsafe_flow: UnsafeFlow,
+                    proxy: &mut WorkerProxy<*mut LayoutContext,PaddedUnsafeFlow>);
+
+    fn run_parallel_helper(&mut self,
+                           unsafe_flow: UnsafeFlow,
+                           proxy: &mut WorkerProxy<*mut LayoutContext,PaddedUnsafeFlow>,
+                           top_down_func: extern "Rust" fn(PaddedUnsafeFlow,
+                                                           &mut WorkerProxy<*mut LayoutContext,
+                                                                            PaddedUnsafeFlow>),
+                           bottom_up_func: extern "Rust" fn(PaddedUnsafeFlow,
+                                                            &mut WorkerProxy<*mut LayoutContext,
+                                                                             PaddedUnsafeFlow>)) {
+        let mut had_children = false;
+        unsafe {
+            // Get a real flow.
+            let flow: &mut ~Flow = cast::transmute(&unsafe_flow);
+
+            // Perform the appropriate traversal.
+            self.process(*flow);
+
+            // Possibly enqueue the children.
+            for kid in flow::child_iter(*flow) {
+                had_children = true;
+                proxy.push(WorkUnit {
+                    fun: top_down_func,
+                    data: UnsafeFlowConversions::from_flow(&borrowed_flow_to_unsafe_flow(kid)),
+                });
+            }
+
+        }
+
+        // If there were no more children, start assigning heights.
+        if !had_children {
+            bottom_up_func(UnsafeFlowConversions::from_flow(&unsafe_flow), proxy)
+        }
+    }
+}
+
 impl<'a> ParallelPostorderFlowTraversal for BubbleWidthsTraversal<'a> {}
 
+impl<'a> ParallelPreorderFlowTraversal for AssignWidthsTraversal<'a> {
+    fn run_parallel(&mut self,
+                    unsafe_flow: UnsafeFlow,
+                    proxy: &mut WorkerProxy<*mut LayoutContext,PaddedUnsafeFlow>) {
+        self.run_parallel_helper(unsafe_flow,
+                                 proxy,
+                                 assign_widths,
+                                 assign_heights_and_store_overflow)
+    }
+}
+
 impl<'a> ParallelPostorderFlowTraversal for AssignHeightsAndStoreOverflowTraversal<'a> {}
 
-fn match_and_cascade_node(unsafe_layout_node: UnsafeLayoutNode,
-                          proxy: &mut WorkerProxy<*mut LayoutContext,UnsafeLayoutNode>) {
+fn recalc_style_for_node(unsafe_layout_node: UnsafeLayoutNode,
+                         proxy: &mut WorkerProxy<*mut LayoutContext,UnsafeLayoutNode>) {
     unsafe {
         let layout_context: &mut LayoutContext = cast::transmute(*proxy.user_data());
 
@@ -216,24 +267,61 @@ fn match_and_cascade_node(unsafe_layout_node: UnsafeLayoutNode,
             StyleWasShared(index) => style_sharing_candidate_cache.touch(index),
         }
 
-        // Enqueue kids.
+        // Prepare for flow construction by counting the node's children and storing that count.
         let mut child_count = 0;
-        for kid in node.children() {
+        for _ in node.children() {
             child_count += 1;
+        }
+        if child_count != 0 {
+            let mut layout_data_ref = node.mutate_layout_data();
+            match *layout_data_ref.get() {
+                Some(ref mut layout_data) => {
+                    layout_data.data.parallel.children_count.store(child_count as int, Relaxed)
+                }
+                None => fail!("no layout data"),
+            }
 
-            proxy.push(WorkUnit {
-                fun: match_and_cascade_node,
-                data: layout_node_to_unsafe_layout_node(&kid),
-            });
+            // Enqueue kids.
+            for kid in node.children() {
+                proxy.push(WorkUnit {
+                    fun: recalc_style_for_node,
+                    data: layout_node_to_unsafe_layout_node(&kid),
+                });
+            }
+            return
         }
 
-        // Prepare for flow construction by adding this node to the leaf set or counting its
-        // children.
-        if child_count == 0 {
-            // We don't need set the `child_count` field here since that's only used by kids during
-            // bottom-up traversals, and since this node is a leaf it has no kids.
-            layout_context.dom_leaf_set.get().insert(&node);
-        } else {
+        // If we got here, we're a leaf. Start construction of flows for this node.
+        construct_flows(unsafe_layout_node, proxy)
+    }
+}
+
+fn construct_flows(mut unsafe_layout_node: UnsafeLayoutNode,
+                   proxy: &mut WorkerProxy<*mut LayoutContext,UnsafeLayoutNode>) {
+    loop {
+        let layout_context: &mut LayoutContext = unsafe {
+            cast::transmute(*proxy.user_data())
+        };
+
+        // Get a real layout node.
+        let node: LayoutNode = unsafe {
+            cast::transmute(unsafe_layout_node)
+        };
+
+        // Construct flows for this node.
+        {
+            let mut flow_constructor = FlowConstructor::new(layout_context, None);
+            flow_constructor.process(&ThreadSafeLayoutNode::new(&node));
+        }
+
+        // Reset the count of children for the next traversal.
+        //
+        // FIXME(pcwalton): Use children().len() when the implementation of that is efficient.
+        let mut child_count = 0;
+        for _ in node.children() {
+            child_count += 1
+        }
+        {
             let mut layout_data_ref = node.mutate_layout_data();
             match *layout_data_ref.get() {
                 Some(ref mut layout_data) => {
@@ -242,17 +330,52 @@ fn match_and_cascade_node(unsafe_layout_node: UnsafeLayoutNode,
                 None => fail!("no layout data"),
             }
         }
+
+        // If this is the reflow root, we're done.
+        if layout_context.reflow_root == OpaqueNode::from_layout_node(&node) {
+            break
+        }
+
+        // Otherwise, enqueue the parent.
+        match node.parent_node() {
+            Some(parent) => {
+
+                // No, we're not at the root yet. Then are we the last sibling of our parent?
+                // If so, we can continue on with our parent; otherwise, we've gotta wait.
+                unsafe {
+                    match *parent.borrow_layout_data_unchecked() {
+                        Some(ref parent_layout_data) => {
+                            let parent_layout_data = cast::transmute_mut(parent_layout_data);
+                            if parent_layout_data.data
+                                                 .parallel
+                                                 .children_count
+                                                 .fetch_sub(1, SeqCst) == 1 {
+                                // We were the last child of our parent. Construct flows for our
+                                // parent.
+                                unsafe_layout_node = layout_node_to_unsafe_layout_node(&parent)
+                            } else {
+                                // Get out of here and find another node to work on.
+                                break
+                            }
+                        }
+                        None => fail!("no layout data for parent?!"),
+                    }
+                }
+            }
+            None => fail!("no parent and weren't at reflow root?!"),
+        }
     }
 }
 
-fn bubble_widths(unsafe_flow: PaddedUnsafeFlow, proxy: &mut WorkerProxy<*mut LayoutContext,PaddedUnsafeFlow>) {
+fn assign_widths(unsafe_flow: PaddedUnsafeFlow,
+                 proxy: &mut WorkerProxy<*mut LayoutContext,PaddedUnsafeFlow>) {
     let layout_context: &mut LayoutContext = unsafe {
         cast::transmute(*proxy.user_data())
     };
-    let mut bubble_widths_traversal = BubbleWidthsTraversal {
+    let mut assign_widths_traversal = AssignWidthsTraversal {
         layout_context: layout_context,
     };
-    bubble_widths_traversal.run_parallel(unsafe_flow.to_flow())
+    assign_widths_traversal.run_parallel(unsafe_flow.to_flow(), proxy)
 }
 
 fn assign_heights_and_store_overflow(unsafe_flow: PaddedUnsafeFlow,
@@ -263,19 +386,19 @@ fn assign_heights_and_store_overflow(unsafe_flow: PaddedUnsafeFlow,
     let mut assign_heights_traversal = AssignHeightsAndStoreOverflowTraversal {
         layout_context: layout_context,
     };
-    assign_heights_traversal.run_parallel(unsafe_flow.to_flow())
+    assign_heights_traversal.run_parallel(unsafe_flow.to_flow(), proxy)
 }
 
-pub fn match_and_cascade_subtree(root_node: &LayoutNode,
-                                 layout_context: &mut LayoutContext,
-                                 queue: &mut WorkQueue<*mut LayoutContext,UnsafeLayoutNode>) {
+pub fn recalc_style_for_subtree(root_node: &LayoutNode,
+                                layout_context: &mut LayoutContext,
+                                queue: &mut WorkQueue<*mut LayoutContext,UnsafeLayoutNode>) {
     unsafe {
         queue.data = cast::transmute(layout_context)
     }
 
     // Enqueue the root node.
     queue.push(WorkUnit {
-        fun: match_and_cascade_node,
+        fun: recalc_style_for_node,
         data: layout_node_to_unsafe_layout_node(root_node),
     });
 
@@ -284,27 +407,19 @@ pub fn match_and_cascade_subtree(root_node: &LayoutNode,
     queue.data = ptr::mut_null()
 }
 
-pub fn traverse_flow_tree(kind: TraversalKind,
-                          leaf_set: &Arc<FlowLeafSet>,
-                          profiler_chan: ProfilerChan,
-                          layout_context: &mut LayoutContext,
-                          queue: &mut WorkQueue<*mut LayoutContext,PaddedUnsafeFlow>) {
+pub fn traverse_flow_tree_preorder(root: &mut ~Flow,
+                                   profiler_chan: ProfilerChan,
+                                   layout_context: &mut LayoutContext,
+                                   queue: &mut WorkQueue<*mut LayoutContext,PaddedUnsafeFlow>) {
     unsafe {
         queue.data = cast::transmute(layout_context)
     }
 
-    let fun = match kind {
-        BubbleWidthsTraversalKind => bubble_widths,
-        AssignHeightsAndStoreOverflowTraversalKind => assign_heights_and_store_overflow,
-    };
-
     profile(time::LayoutParallelWarmupCategory, profiler_chan, || {
-        for (flow, _) in leaf_set.get().iter() {
-            queue.push(WorkUnit {
-                fun: fun,
-                data: UnsafeFlowConversions::from_flow(flow),
-            })
-        }
+        queue.push(WorkUnit {
+            fun: assign_widths,
+            data: UnsafeFlowConversions::from_flow(&mut_owned_flow_to_unsafe_flow(root)),
+        })
     });
 
     queue.run();
diff --git a/src/components/main/layout/wrapper.rs b/src/components/main/layout/wrapper.rs
index 7fddf24f8e9..a5830b7f00c 100644
--- a/src/components/main/layout/wrapper.rs
+++ b/src/components/main/layout/wrapper.rs
@@ -25,7 +25,6 @@ use script::dom::htmlimageelement::HTMLImageElement;
 use script::dom::node::{DocumentNodeTypeId, ElementNodeTypeId, Node, NodeTypeId, NodeHelpers};
 use script::dom::text::Text;
 use servo_msg::constellation_msg::{PipelineId, SubpageId};
-use servo_util::concurrentmap::{ConcurrentHashMap, ConcurrentHashMapIterator};
 use servo_util::namespace;
 use servo_util::namespace::Namespace;
 use std::cast;
@@ -495,32 +494,3 @@ pub fn layout_node_to_unsafe_layout_node(node: &LayoutNode) -> UnsafeLayoutNode
     }
 }
 
-/// Keeps track of the leaves of the DOM. This is used to efficiently start bottom-up traversals.
-pub struct DomLeafSet {
-    priv set: ConcurrentHashMap<UnsafeLayoutNode,()>,
-}
-
-impl DomLeafSet {
-    /// Creates a new DOM leaf set.
-    pub fn new() -> DomLeafSet {
-        DomLeafSet {
-            set: ConcurrentHashMap::with_locks_and_buckets(64, 256),
-        }
-    }
-
-    /// Inserts a DOM node into the leaf set.
-    pub fn insert(&self, node: &LayoutNode) {
-        self.set.insert(layout_node_to_unsafe_layout_node(node), ());
-    }
-
-    /// Removes all DOM nodes from the set.
-    pub fn clear(&self) {
-        self.set.clear()
-    }
-
-    /// Iterates over the DOM nodes in the leaf set.
-    pub fn iter<'a>(&'a self) -> ConcurrentHashMapIterator<'a,UnsafeLayoutNode,()> {
-        self.set.iter()
-    }
-}
-
diff --git a/src/components/util/opts.rs b/src/components/util/opts.rs
index 04daf519c87..2f1d9777b8a 100644
--- a/src/components/util/opts.rs
+++ b/src/components/util/opts.rs
@@ -46,6 +46,12 @@ pub struct Opts {
     output_file: Option<~str>,
     headless: bool,
     hard_fail: bool,
+
+    /// True if we should bubble intrinsic widths sequentially (`-b`). If this is true, then
+    /// intrinsic widths are computed as a separate pass instead of during flow construction. You
+    /// may wish to turn this flag on in order to benchmark style recalculation against other
+    /// browser engines.
+    bubble_widths_separately: bool,
 }
 
 fn print_usage(app: &str, opts: &[groups::OptGroup]) {
@@ -68,6 +74,7 @@ pub fn from_cmdline_args(args: &[~str]) -> Opts {
         groups::optopt("y", "layout-threads", "Number of threads to use for layout", "1"),
         groups::optflag("z", "headless", "Headless mode"),
         groups::optflag("f", "hard-fail", "Exit on task failure instead of displaying about:failure"),
+        groups::optflag("b", "bubble-widths", "Bubble intrinsic widths separately like other engines"),
         groups::optflag("h", "help", "Print this message")
     ];
 
@@ -143,5 +150,6 @@ pub fn from_cmdline_args(args: &[~str]) -> Opts {
         output_file: opt_match.opt_str("o"),
         headless: opt_match.opt_present("z"),
         hard_fail: opt_match.opt_present("f"),
+        bubble_widths_separately: opt_match.opt_present("b"),
     }
 }