Rewrite flow construction to be incrementalizable and parallelizable.

This replaces flow construction with a strict bottom-up tree traversal,
allowing for parallelism. Each step of the traversal creates a flow or
a `ConstructionItem`, similar to how Gecko works. {ib} splits are
handled by not creating `InlineFlow`s until the containing block is
reached.

This should be able to be incrementalized by storing the `Flow` from
layout to layout, and performing fixups during flow construction
and/or wiping containing blocks in a previous pass.

20 files changed, 1181 insertions, 888 deletions

diff --git a/src/components/main/css/matching.rs b/src/components/main/css/matching.rs
index c7f27b1a9ad..299147b01a2 100644
--- a/src/components/main/css/matching.rs
+++ b/src/components/main/css/matching.rs
@@ -6,13 +6,12 @@
 
 use std::cell::Cell;
 use std::comm;
-use std::rt::default_sched_threads;
+use std::rt;
 use std::task;
 use std::vec;
 use extra::arc::RWArc;
 
 use css::node_style::StyledNode;
-use css::node_util::NodeUtil;
 use layout::incremental;
 use layout::util::LayoutDataAccess;
 
@@ -38,10 +37,16 @@ impl MatchMethods for AbstractNode<LayoutView> {
             };
             stylist.get_applicable_declarations(self, style_attribute, None)
         };
-        self.layout_data().applicable_declarations.set(applicable_declarations)
+
+        match *self.mutate_layout_data().ptr {
+            Some(ref mut layout_data) => {
+                layout_data.applicable_declarations = applicable_declarations
+            }
+            None => fail!("no layout data")
+        }
     }
     fn match_subtree(&self, stylist: RWArc<Stylist>) {
-        let num_tasks = default_sched_threads() * 2;
+        let num_tasks = rt::default_sched_threads() * 2;
         let mut node_count = 0;
         let mut nodes_per_task = vec::from_elem(num_tasks, ~[]);
 
@@ -83,18 +88,26 @@ impl MatchMethods for AbstractNode<LayoutView> {
             None => None
         };
 
-        let layout_data = self.layout_data();
-        let computed_values = cascade(*layout_data.applicable_declarations.borrow().ptr,
-                                      parent_style);
-        let style = layout_data.style.mutate();
-        match *style.ptr {
-            None => (),
-            Some(ref previous_style) => {
-                self.set_restyle_damage(incremental::compute_damage(previous_style,
-                                                                    &computed_values))
+        let computed_values = unsafe {
+            cascade(self.borrow_layout_data_unchecked().as_ref().unwrap().applicable_declarations,
+                    parent_style)
+        };
+
+        match *self.mutate_layout_data().ptr {
+            None => fail!("no layout data"),
+            Some(ref mut layout_data) => {
+                let style = &mut layout_data.style;
+                match *style {
+                    None => (),
+                    Some(ref previous_style) => {
+                        layout_data.restyle_damage =
+                            Some(incremental::compute_damage(previous_style,
+                                                             &computed_values).to_int())
+                    }
+                }
+                *style = Some(computed_values)
             }
         }
-        *style.ptr = Some(computed_values)
     }
 
     fn cascade_subtree(&self, parent: Option<AbstractNode<LayoutView>>) {
diff --git a/src/components/main/css/node_style.rs b/src/components/main/css/node_style.rs
index e4c40e1e3b4..33fdb8d43b2 100644
--- a/src/components/main/css/node_style.rs
+++ b/src/components/main/css/node_style.rs
@@ -17,6 +17,7 @@ pub trait StyledNode {
 }
 
 impl StyledNode for AbstractNode<LayoutView> {
+    #[inline]
     fn style(&self) -> &ComputedValues {
         // FIXME(pcwalton): Is this assertion needed for memory safety? It's slow.
         //assert!(self.is_element()); // Only elements can have styles
diff --git a/src/components/main/css/node_util.rs b/src/components/main/css/node_util.rs
index 104174b7b8c..5ca43c69243 100644
--- a/src/components/main/css/node_util.rs
+++ b/src/components/main/css/node_util.rs
@@ -27,22 +27,29 @@ impl<'self> NodeUtil<'self> for AbstractNode<LayoutView> {
      * FIXME: This isn't completely memory safe since the style is
      * stored in a box that can be overwritten
      */
+    #[inline]
     fn get_css_select_results(self) -> &'self ComputedValues {
-        let layout_data = self.layout_data();
-        match *layout_data.style.borrow().ptr {
-            None => fail!(~"style() called on node without a style!"),
-            Some(ref style) => unsafe { cast::transmute_region(style) }
+        unsafe {
+            cast::transmute_region(self.borrow_layout_data_unchecked()
+                                       .as_ref()
+                                       .unwrap()
+                                       .style
+                                       .as_ref()
+                                       .unwrap())
         }
     }
 
     /// Does this node have a computed style yet?
     fn have_css_select_results(self) -> bool {
-        self.layout_data().style.borrow().ptr.is_some()
+        self.borrow_layout_data().ptr.as_ref().unwrap().style.is_some()
     }
 
     /// Update the computed style of an HTML element with a style specified by CSS.
     fn set_css_select_results(self, decl: ComputedValues) {
-        *self.layout_data().style.mutate().ptr = Some(decl)
+        match *self.mutate_layout_data().ptr {
+            Some(ref mut data) => data.style = Some(decl),
+            _ => fail!("no layout data for this node"),
+        }
     }
 
     /// Get the description of how to account for recent style changes.
@@ -56,17 +63,21 @@ impl<'self> NodeUtil<'self> for AbstractNode<LayoutView> {
             RestyleDamage::none()
         };
 
-        self.layout_data()
-            .restyle_damage
-            .borrow()
+        self.borrow_layout_data()
             .ptr
+            .as_ref()
+            .unwrap()
+            .restyle_damage
             .map(|x| RestyleDamage::from_int(x))
             .unwrap_or(default)
     }
 
     /// Set the restyle damage field.
     fn set_restyle_damage(self, damage: RestyleDamage) {
-        *self.layout_data().restyle_damage.mutate().ptr = Some(damage.to_int())
+        match *self.mutate_layout_data().ptr {
+            Some(ref mut data) => data.restyle_damage = Some(damage.to_int()),
+            _ => fail!("no layout data for this node"),
+        }
     }
 }
 
diff --git a/src/components/main/layout/block.rs b/src/components/main/layout/block.rs
index 24565896ff7..bae5add6f09 100644
--- a/src/components/main/layout/block.rs
+++ b/src/components/main/layout/block.rs
@@ -40,6 +40,14 @@ impl BlockFlow {
         }
     }
 
+    pub fn from_box(base: FlowData, box: @RenderBox) -> BlockFlow {
+        BlockFlow {
+            base: base,
+            box: Some(box),
+            is_root: false
+        }
+    }
+
     pub fn new_root(base: FlowData) -> BlockFlow {
         BlockFlow {
             base: base,
@@ -499,6 +507,10 @@ impl FlowContext for BlockFlow {
         *first_in_flow = false;
     }
 
+    fn mark_as_root(&mut self) {
+        self.is_root = true
+    }
+
     fn debug_str(&self) -> ~str {
         if self.is_root {
             ~"BlockFlow(root)"
diff --git a/src/components/main/layout/box.rs b/src/components/main/layout/box.rs
index e2ca7b5d164..7f4514e3c4e 100644
--- a/src/components/main/layout/box.rs
+++ b/src/components/main/layout/box.rs
@@ -225,6 +225,7 @@ pub struct ImageRenderBox {
 }
 
 impl ImageRenderBox {
+    #[inline]
     pub fn new(base: RenderBoxBase, image_url: Url, local_image_cache: @mut LocalImageCache)
                -> ImageRenderBox {
         assert!(base.node.is_image_element());
@@ -523,6 +524,7 @@ pub struct UnscannedTextRenderBox {
 
 impl UnscannedTextRenderBox {
     /// Creates a new instance of `UnscannedTextRenderBox`.
+    #[inline(always)]
     pub fn new(base: RenderBoxBase) -> UnscannedTextRenderBox {
         assert!(base.node.is_text());
 
diff --git a/src/components/main/layout/box_builder.rs b/src/components/main/layout/box_builder.rs
deleted file mode 100644
index ee492c85304..00000000000
--- a/src/components/main/layout/box_builder.rs
+++ /dev/null
@@ -1,673 +0,0 @@
-/* This Source Code Form is subject to the terms of the Mozilla Public
- * License, v. 2.0. If a copy of the MPL was not distributed with this
- * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
-
-//! Creates CSS boxes from a DOM tree.
-
-use layout::block::BlockFlow;
-use layout::float::FloatFlow;
-use layout::box::{GenericRenderBox, GenericRenderBoxClass, ImageRenderBox, ImageRenderBoxClass};
-use layout::box::{RenderBox, RenderBoxBase, RenderBoxClass, RenderBoxUtils, TextRenderBoxClass};
-use layout::box::{UnscannedTextRenderBox, UnscannedTextRenderBoxClass};
-use layout::context::LayoutContext;
-use layout::float_context::FloatType;
-use layout::flow::{AbsoluteFlow, BlockFlowClass, FloatFlowClass, FlowContext, FlowData};
-use layout::flow::{ImmutableFlowUtils, InlineBlockFlow, InlineBlockFlowClass, InlineFlowClass};
-use layout::flow::{MutableFlowUtils, TableFlow};
-use layout::flow;
-use layout::inline::{InlineFlow};
-use layout::text::TextRunScanner;
-use css::node_style::StyledNode;
-
-use style::computed_values::display;
-use style::computed_values::float;
-use layout::float_context::{FloatLeft, FloatRight};
-use script::dom::node::{AbstractNode, CommentNodeTypeId, DoctypeNodeTypeId};
-use script::dom::node::{ElementNodeTypeId, LayoutView, TextNodeTypeId, DocumentNodeTypeId};
-use script::dom::node::DocumentFragmentNodeTypeId;
-use servo_util::range::Range;
-use servo_util::tree::{TreeNodeRef, TreeNode};
-use std::cast;
-use std::cell::Cell;
-
-enum FlowType {
-    AbsoluteFlowType,
-    BlockFlowType,
-    FloatFlowType(FloatType),
-    InlineBlockFlowType,
-    InlineFlowType,
-    RootFlowType,
-    TableFlowType,
-}
-
-pub struct LayoutTreeBuilder {
-    next_cid: int,
-    next_bid: int,
-}
-
-impl LayoutTreeBuilder {
-    pub fn new() -> LayoutTreeBuilder {
-        LayoutTreeBuilder {
-            next_cid: -1,
-            next_bid: -1,
-        }
-    }
-}
-
-// helper object for building the initial box list and making the
-// mapping between DOM nodes and boxes.
-struct BoxGenerator<'self> {
-    flow: &'self mut FlowContext,
-    range_stack: @mut ~[uint],
-}
-
-enum InlineSpacerSide {
-    LogicalBefore,
-    LogicalAfter,
-}
-
-impl<'self> BoxGenerator<'self> {
-    /* Debug ids only */
-
-    fn new(flow: &'self mut FlowContext) -> BoxGenerator<'self> {
-        debug!("Creating box generator for flow: {:s}", flow.debug_str());
-        BoxGenerator {
-            flow: flow,
-            range_stack: @mut ~[]
-        }
-    }
-
-    fn with_clone<R>(&mut self, cb: &fn(BoxGenerator<'self>) -> R) -> R {
-        // FIXME(pcwalton): This is a hack; it can be done safely with linearity.
-        unsafe {
-            let gen = BoxGenerator {
-                flow: cast::transmute_copy(&self.flow),
-                range_stack: self.range_stack
-            };
-            cb(gen)
-        }
-    }
-
-    /* Whether "spacer" boxes are needed to stand in for this DOM node */
-    fn inline_spacers_needed_for_node(_: AbstractNode<LayoutView>) -> bool {
-        return false;
-    }
-
-    // TODO: implement this, generating spacer 
-    fn make_inline_spacer_for_node_side(_: &LayoutContext,
-                                        _: AbstractNode<LayoutView>,
-                                        _: InlineSpacerSide)
-                                        -> Option<@RenderBox> {
-        None
-    }
-
-    pub fn push_node(&mut self,
-                     ctx: &LayoutContext,
-                     node: AbstractNode<LayoutView>,
-                     builder: &mut LayoutTreeBuilder) {
-        debug!("BoxGenerator[f{:d}]: pushing node: {:s}", flow::base(self.flow).id, node.debug_str());
-
-        // TODO: remove this once UA styles work
-        let box_type = self.decide_box_type(node);
-
-        debug!("BoxGenerator[f{:d}]: point a", flow::base(self.flow).id);
-
-        let range_stack = &mut self.range_stack;
-        // depending on flow, make a box for this node.
-        match self.flow.class() {
-            InlineFlowClass => {
-                let inline = self.flow.as_inline();
-                let node_range_start = inline.boxes.len();
-                range_stack.push(node_range_start);
-
-                // if a leaf, make a box.
-                if node.is_leaf() {
-                    let new_box = BoxGenerator::make_box(ctx, box_type, node, builder);
-                    inline.boxes.push(new_box);
-                } else if BoxGenerator::inline_spacers_needed_for_node(node) {
-                    // else, maybe make a spacer for "left" margin, border, padding
-                    let inline_spacer = BoxGenerator::make_inline_spacer_for_node_side(ctx, node, LogicalBefore);
-                    for spacer in inline_spacer.iter() {
-                        inline.boxes.push(*spacer);
-                    }
-                }
-                // TODO: cases for inline-block, etc.
-            },
-            BlockFlowClass => {
-                let block = self.flow.as_block();
-                debug!("BoxGenerator[f{:d}]: point b", block.base.id);
-                let new_box = BoxGenerator::make_box(ctx, box_type, node, builder);
-
-                debug!("BoxGenerator[f{:d}]: attaching box[b{:d}] to block flow (node: {:s})",
-                       block.base.id,
-                       new_box.base().id(),
-                       node.debug_str());
-
-                assert!(block.box.is_none());
-                block.box = Some(new_box);
-            }
-            FloatFlowClass => {
-                let float = self.flow.as_float();
-                debug!("BoxGenerator[f{:d}]: point b", float.base.id);
-
-                let new_box = BoxGenerator::make_box(ctx, box_type, node, builder);
-
-                debug!("BoxGenerator[f{:d}]: attaching box[b{:d}] to float flow (node: {:s})",
-                        float.base.id,
-                        new_box.base().id(),
-                        node.debug_str());
-
-                assert!(float.box.is_none() && float.index.is_none());
-                float.box = Some(new_box);
-            }
-            _ => warn!("push_node() not implemented for flow f{:d}", flow::base(self.flow).id),
-        }
-    }
-
-    pub fn pop_node(&mut self, ctx: &LayoutContext, node: AbstractNode<LayoutView>) {
-        debug!("BoxGenerator[f{:d}]: popping node: {:s}", flow::base(self.flow).id, node.debug_str());
-
-        match self.flow.class() {
-            InlineFlowClass => {
-                let inline = self.flow.as_inline();
-                let inline = &mut *inline;
-
-                if BoxGenerator::inline_spacers_needed_for_node(node) {
-                    // If this non-leaf box generates extra horizontal spacing, add a SpacerBox for
-                    // it.
-                    let result = BoxGenerator::make_inline_spacer_for_node_side(ctx, node, LogicalAfter);
-                    for spacer in result.iter() {
-                        let boxes = &mut inline.boxes;
-                        boxes.push(*spacer);
-                    }
-                }
-                let mut node_range: Range = Range::new(self.range_stack.pop(), 0);
-                node_range.extend_to(inline.boxes.len());
-
-                if node_range.length() == 0 {
-                    warn!("node range length is zero?!")
-                }
-
-                debug!("BoxGenerator: adding element range={}", node_range);
-                inline.elems.add_mapping(node, &node_range);
-            },
-            BlockFlowClass => assert!(self.range_stack.len() == 0),
-            FloatFlowClass => assert!(self.range_stack.len() == 0),
-            _ => warn!("pop_node() not implemented for flow {:?}", flow::base(self.flow).id),
-        }
-    }
-
-    /// Disambiguate between different methods here instead of inlining, since each case has very
-    /// different complexity.
-    fn make_box(layout_ctx: &LayoutContext,
-                ty: RenderBoxClass,
-                node: AbstractNode<LayoutView>,
-                builder: &mut LayoutTreeBuilder)
-                -> @RenderBox {
-        let base = RenderBoxBase::new(node, builder.next_box_id());
-        let result = match ty {
-            GenericRenderBoxClass => @GenericRenderBox::new(base) as @RenderBox,
-            TextRenderBoxClass | UnscannedTextRenderBoxClass => {
-                @UnscannedTextRenderBox::new(base) as @RenderBox
-            }
-            ImageRenderBoxClass => BoxGenerator::make_image_box(layout_ctx, node, base),
-        };
-        debug!("BoxGenerator: created box: {:s}", result.debug_str());
-        result
-    }
-
-    fn make_image_box(layout_ctx: &LayoutContext,
-                      node: AbstractNode<LayoutView>,
-                      base: RenderBoxBase)
-                      -> @RenderBox {
-        assert!(node.is_image_element());
-
-        do node.with_imm_image_element |image_element| {
-            if image_element.image.is_some() {
-                // FIXME(pcwalton): Don't copy URLs.
-                let url = (*image_element.image.get_ref()).clone();
-                @ImageRenderBox::new(base.clone(), url, layout_ctx.image_cache) as @RenderBox
-            } else {
-                info!("Tried to make image box, but couldn't find image. Made generic box \
-                       instead.");
-                @GenericRenderBox::new(base.clone()) as @RenderBox
-            }
-        }
-    }
-
-    fn decide_box_type(&self, node: AbstractNode<LayoutView>) -> RenderBoxClass {
-        if node.is_text() {
-            TextRenderBoxClass
-        } else if node.is_image_element() {
-            do node.with_imm_image_element |image_element| {
-                match image_element.image {
-                    Some(_) => ImageRenderBoxClass,
-                    None => GenericRenderBoxClass,
-                }
-            }
-        } else if node.is_element() {
-            GenericRenderBoxClass
-        } else {
-            fail!("Hey, doctypes and comments shouldn't get here! They are display:none!")
-        }
-    }
-
-}
-
-enum BoxGenResult<'self> {
-    NoGenerator,
-    ParentGenerator,
-    SiblingGenerator,
-    NewGenerator(BoxGenerator<'self>),
-    /// Start a new generator, but also switch the parent out for the
-    /// grandparent, ending the parent generator.
-    ReparentingGenerator(BoxGenerator<'self>),
-    Mixed(BoxGenerator<'self>, ~BoxGenResult<'self>),
-}
-
-/// Determines whether the result of child box construction needs to reparent
-/// or not. Reparenting is needed when a block flow is a child of an inline;
-/// in that case, we need to let the level up the stack no to end the parent
-/// genertor and continue with the grandparent.
-enum BoxConstructResult<'self> {
-    Normal(Option<BoxGenerator<'self>>),
-    Reparent(BoxGenerator<'self>),
-}
-
-impl LayoutTreeBuilder {
-    /* Debug-only ids */
-    pub fn next_flow_id(&mut self) -> int { self.next_cid += 1; self.next_cid }
-    pub fn next_box_id(&mut self) -> int { self.next_bid += 1; self.next_bid }
-
-    /// Creates necessary box(es) and flow context(s) for the current DOM node,
-    /// and recurses on its children.
-    pub fn construct_recursively<'a>(
-                                 &mut self,
-                                 layout_ctx: &LayoutContext,
-                                 cur_node: AbstractNode<LayoutView>,
-                                 mut grandparent_generator: Option<BoxGenerator<'a>>,
-                                 mut parent_generator: BoxGenerator<'a>,
-                                 mut prev_sibling_generator: Option<BoxGenerator<'a>>)
-                                 -> BoxConstructResult<'a> {
-        debug!("Considering node: {:s}", cur_node.debug_str());
-        let box_gen_result = {
-            let grandparent_gen_ref = match grandparent_generator {
-                Some(ref mut generator) => Some(generator),
-                None => None,
-            };
-            let sibling_gen_ref = match prev_sibling_generator {
-                Some(ref mut generator) => Some(generator),
-                None => None,
-            };
-            self.box_generator_for_node(cur_node, grandparent_gen_ref, &mut parent_generator, sibling_gen_ref)
-        };
-
-        let mut reparent = false;
-
-        debug!("result from generator_for_node: {:?}", &box_gen_result);
-        // Skip over nodes that don't belong in the flow tree
-        let (this_generator, next_generator) = match box_gen_result {
-            NoGenerator => return Normal(prev_sibling_generator),
-            ParentGenerator => {
-                do parent_generator.with_clone |clone| {
-                    (clone, None)
-                }
-            }
-            SiblingGenerator => (prev_sibling_generator.take_unwrap(), None),
-            NewGenerator(gen) => (gen, None),
-            ReparentingGenerator(gen) => {
-                reparent = true;
-                (gen, None)
-            }
-            Mixed(gen, next_gen) => (gen, Some(match *next_gen {
-                ParentGenerator => {
-                    do parent_generator.with_clone |clone| {
-                        clone
-                    }
-                }
-                SiblingGenerator => prev_sibling_generator.take_unwrap(),
-                _ => fail!("Unexpect BoxGenResult")
-            }))
-        };
-
-        let mut this_generator = this_generator;
-
-        debug!("point a: {:s}", cur_node.debug_str());
-        this_generator.push_node(layout_ctx, cur_node, self);
-        debug!("point b: {:s}", cur_node.debug_str());
-
-        // recurse on child nodes.
-        let prev_gen_cell = Cell::new(Normal(None));
-        for child_node in cur_node.children() {
-            do parent_generator.with_clone |grandparent_clone| {
-                let grandparent_clone_cell = Cell::new(Some(grandparent_clone));
-                do this_generator.with_clone |parent_clone| {
-                    match prev_gen_cell.take() {
-                        Normal(prev_gen) => {
-                            let prev_generator = self.construct_recursively(layout_ctx,
-                                                                            child_node,
-                                                                            grandparent_clone_cell.take(),
-                                                                            parent_clone,
-                                                                            prev_gen);
-                            prev_gen_cell.put_back(prev_generator);
-                        }
-                        Reparent(prev_gen) => {
-                            let prev_generator = self.construct_recursively(layout_ctx,
-                                                                            child_node,
-                                                                            None,
-                                                                            grandparent_clone_cell.take().unwrap(),
-                                                                            Some(prev_gen));
-                            prev_gen_cell.put_back(prev_generator);
-                        } 
-                    }
-                }
-            }
-        }
-
-        this_generator.pop_node(layout_ctx, cur_node);
-        self.simplify_children_of_flow(layout_ctx, this_generator.flow);
-
-        match next_generator {
-            Some(n_gen) => Normal(Some(n_gen)),
-            None => {
-                if reparent {
-                    Reparent(this_generator)
-                } else {
-                    Normal(Some(this_generator))
-                }
-            }
-        }
-    }
-
-    pub fn box_generator_for_node<'a>(&mut self,
-                                      node: AbstractNode<LayoutView>,
-                                      grandparent_generator: Option<&mut BoxGenerator<'a>>,
-                                      parent_generator: &mut BoxGenerator<'a>,
-                                      mut sibling_generator: Option<&mut BoxGenerator<'a>>)
-                                      -> BoxGenResult<'a> {
-        let display = match node.type_id() {
-            ElementNodeTypeId(_) => match node.style().Box.display {
-                display::none => return NoGenerator,
-                display::table | display::inline_table | display::table_row_group
-                    | display::table_header_group | display::table_footer_group
-                    | display::table_row | display::table_column_group
-                    | display::table_column | display::table_cell | display::table_caption
-                    | display::list_item
-                    => display::block,
-                display => display,
-            },
-            TextNodeTypeId => display::inline,
-            DocumentNodeTypeId(_) |
-            DoctypeNodeTypeId |
-            DocumentFragmentNodeTypeId |
-            CommentNodeTypeId => return NoGenerator,
-        };
-
-        // FIXME(pcwalton): Unsafe.
-        let sibling_flow: Option<&mut FlowContext> = sibling_generator.as_mut().map(|gen| {
-            unsafe {
-                cast::transmute_copy(&gen.flow)
-            }
-        });
-
-        let is_float = if (node.is_element()) {
-            match node.style().Box.float {
-                float::none => None,
-                float::left => Some(FloatLeft),
-                float::right => Some(FloatRight)
-            }
-        } else {
-            None
-        };
-
-        let sibling_flow_class = match sibling_flow {
-            None => None,
-            Some(flow) => Some(flow.class()),
-        };
-        
-        let new_generator = match (display, parent_generator.flow.class(), sibling_flow_class) {
-            // Floats
-            (display::block, BlockFlowClass, _) |
-            (display::block, FloatFlowClass, _) if is_float.is_some() => {
-                self.create_child_generator(node,
-                                            parent_generator,
-                                            FloatFlowType(is_float.unwrap()))
-            }
-            // If we're placing a float after an inline, append the float to the inline flow,
-            // then continue building from the inline flow in case there are more inlines
-            // afterward.
-            (display::block, _, Some(InlineFlowClass)) if is_float.is_some() => {
-                let float_type = FloatFlowType(is_float.unwrap());
-                let float_generator = self.create_child_generator(node,
-                                                                  sibling_generator.unwrap(),
-                                                                  float_type);
-                return Mixed(float_generator, ~SiblingGenerator);
-            }
-            // This is a catch-all case for when:
-            // a) sibling_flow is None
-            // b) sibling_flow is a BlockFlow
-            (display::block, InlineFlowClass, _) if is_float.is_some() => {
-                self.create_child_generator(node,
-                                            parent_generator,
-                                            FloatFlowType(is_float.unwrap()))
-            }
-
-            (display::block, BlockFlowClass, _) => {
-                match (parent_generator.flow.as_block().is_root, node.parent_node()) {
-                    // If this is the root node, then use the root flow's
-                    // context. Otherwise, make a child block context.
-                    (true, Some(parent)) if !parent.is_document() => {
-                        self.create_child_generator(node, parent_generator, BlockFlowType)
-                    }
-                    (true, None) | (true, Some(_)) => return ParentGenerator,
-                    (false, _) => {
-                        self.create_child_generator(node, parent_generator, BlockFlowType)
-                    }
-                }
-            }
-
-            (display::block, FloatFlowClass, _) => {
-                self.create_child_generator(node, parent_generator, BlockFlowType)
-            }
-
-            // Inlines that are children of inlines are part of the same flow
-            (display::inline, InlineFlowClass, _) => return ParentGenerator,
-            (display::inline_block, InlineFlowClass, _) => return ParentGenerator,
-
-            // Inlines that are children of blocks create new flows if their
-            // previous sibling was a block.
-            (display::inline, BlockFlowClass, Some(BlockFlowClass)) |
-            (display::inline_block, BlockFlowClass, Some(BlockFlowClass)) => {
-                self.create_child_generator(node, parent_generator, InlineFlowType)
-            }
-
-            // The first two cases should only be hit when a FloatFlow
-            // is the first child of a BlockFlow. Other times, we will
-            (display::inline, _, Some(FloatFlowClass)) |
-            (display::inline_block, _, Some(FloatFlowClass)) |
-            (display::inline, FloatFlowClass, _) |
-            (display::inline_block, FloatFlowClass, _) => {
-                self.create_child_generator(node, parent_generator, InlineFlowType)
-            }
-
-            // Inlines whose previous sibling was not a block try to use their
-            // sibling's flow context.
-            (display::inline, BlockFlowClass, _) |
-            (display::inline_block, BlockFlowClass, _) => {
-                return match sibling_generator {
-                    None => NewGenerator(self.create_child_generator(node, 
-                                                                     parent_generator, 
-                                                                     InlineFlowType)),
-                    Some(*) => SiblingGenerator
-                }
-            }
-
-            // blocks that are children of inlines need to split their parent
-            // flows.
-            (display::block, InlineFlowClass, _) => {
-                match grandparent_generator {
-                    None => fail!("expected to have a grandparent block flow"),
-                    Some(grandparent_gen) => {
-                        assert!(grandparent_gen.flow.is_block_like());
-
-                        let block_gen = self.create_child_generator(node,
-                                                                    grandparent_gen,
-                                                                    BlockFlowType);
-                        return ReparentingGenerator(block_gen);
-                    }
-                }
-            }
-
-            _ => return ParentGenerator
-        };
-
-        NewGenerator(new_generator)
-    }
-
-    pub fn create_child_generator<'a>(
-                                  &mut self,
-                                  node: AbstractNode<LayoutView>,
-                                  parent_generator: &mut BoxGenerator<'a>,
-                                  ty: FlowType)
-                                  -> BoxGenerator<'a> {
-        let new_flow = self.make_flow(ty, node);
-        parent_generator.flow.add_new_child(new_flow);
-        let flow_ref = flow::last_child(parent_generator.flow).unwrap();
-        BoxGenerator::new(*flow_ref)
-    }
-
-    /// Fix up any irregularities such as:
-    ///
-    /// * split inlines (CSS 2.1 Section 9.2.1.1)
-    /// * elide non-preformatted whitespace-only text boxes and their flows (CSS 2.1 Section
-    ///   9.2.2.1).
-    ///
-    /// The latter can only be done immediately adjacent to, or at the beginning or end of a block
-    /// flow. Otherwise, the whitespace might affect whitespace collapsing with adjacent text.
-    pub fn simplify_children_of_flow(&self, ctx: &LayoutContext, parent_flow: &mut FlowContext) {
-        match parent_flow.class() {
-            InlineFlowClass => {
-                let mut found_child_inline = false;
-                let mut found_child_block = false;
-
-                for child_ctx in flow::child_iter(parent_flow) {
-                    match child_ctx.class() {
-                        InlineFlowClass | InlineBlockFlowClass => found_child_inline = true,
-                        BlockFlowClass => found_child_block = true,
-                        _ => {}
-                    }
-                }
-
-                if found_child_block && found_child_inline {
-                    self.fixup_split_inline(parent_flow)
-                }
-            }
-            BlockFlowClass | FloatFlowClass => {
-                // check first/last child for whitespace-ness
-                let mut do_remove = false;
-                let p_id = flow::base(parent_flow).id;
-                do parent_flow.with_first_child |mut first_child| {
-                    for first_flow in first_child.mut_iter() {
-                        if first_flow.starts_inline_flow() {
-                            // FIXME: workaround for rust#6393
-                            {
-                                let first_inline_flow = first_flow.as_inline();
-                                let boxes = &first_inline_flow.boxes;
-                                if boxes.len() == 1 {
-                                    let first_box = boxes[0];   // FIXME(pcwalton): Rust bug
-                                    if first_box.is_whitespace_only() {
-                                        debug!("LayoutTreeBuilder: pruning whitespace-only first \
-                                                child flow f{:d} from parent f{:d}",
-                                               first_inline_flow.base.id,
-                                               p_id);
-                                        do_remove = true;
-                                    }
-                                }
-                            }
-                        }
-                    }
-                }
-                if (do_remove) { 
-                    parent_flow.remove_first();
-                }
-
-
-                do_remove = false;
-                let p_id = flow::base(parent_flow).id;
-                do parent_flow.with_last_child |mut last_child| {
-                    for last_flow in last_child.mut_iter() {
-                        if last_flow.starts_inline_flow() {
-                            // FIXME: workaround for rust#6393
-                            {
-                                let last_inline_flow = last_flow.as_inline();
-                                let boxes = &last_inline_flow.boxes;
-                                if boxes.len() == 1 && boxes.last().is_whitespace_only() {
-                                    let last_box = boxes.last();    // FIXME(pcwalton): Rust bug
-                                    if last_box.is_whitespace_only() {
-                                        debug!("LayoutTreeBuilder: pruning whitespace-only last \
-                                                child flow f{:d} from parent f{:d}",
-                                               last_inline_flow.base.id,
-                                               p_id);
-                                        do_remove = true;
-                                    }
-                                }
-                            }
-                        }
-                    }
-                }
-                if (do_remove) {
-                    parent_flow.remove_last();
-                }
-
-                // Issue 543: We only need to do this if there are inline child
-                // flows, but there's not a quick way to check at the moment.
-                for child_flow in flow::child_iter(parent_flow) {
-                    match child_flow.class() {
-                        InlineFlowClass | InlineBlockFlowClass => {
-                            let mut scanner = TextRunScanner::new();
-                            scanner.scan_for_runs(ctx, *child_flow);
-                        }
-                        _ => {}
-                    }
-                }
-            }
-            _ => {}
-        }
-    }
-
-    pub fn fixup_split_inline(&self, _: &mut FlowContext) {
-        // TODO: finish me. 
-        fail!(~"TODO: handle case where an inline is split by a block")
-    }
-
-    /// Entry point for box creation. Should only be called on the root DOM element.
-    pub fn construct_trees(&mut self, layout_ctx: &LayoutContext, root: AbstractNode<LayoutView>)
-                       -> Result<~FlowContext:, ()> {
-        debug!("Constructing flow tree for DOM: ");
-        debug!("{:?}", root.dump());
-
-        let mut new_flow = self.make_flow(RootFlowType, root);
-        {
-            let new_generator = BoxGenerator::new(new_flow);
-            self.construct_recursively(layout_ctx, root, None, new_generator, None);
-        }
-        return Ok(new_flow)
-    }
-
-    /// Creates a flow of the given type for the supplied node.
-    pub fn make_flow(&mut self, flow_type: FlowType, node: AbstractNode<LayoutView>)
-                     -> ~FlowContext: {
-        let info = FlowData::new(self.next_flow_id(), node);
-        let result = match flow_type {
-            AbsoluteFlowType        => ~AbsoluteFlow::new(info) as ~FlowContext:,
-            BlockFlowType           => ~BlockFlow::new(info) as ~FlowContext:,
-            FloatFlowType(f_type)   => ~FloatFlow::new(info, f_type) as ~FlowContext:,
-            InlineBlockFlowType     => ~InlineBlockFlow::new(info) as ~FlowContext:,
-            InlineFlowType          => ~InlineFlow::new(info) as ~FlowContext:,
-            RootFlowType            => ~BlockFlow::new_root(info) as ~FlowContext:,
-            TableFlowType           => ~TableFlow::new(info) as ~FlowContext:,
-        };
-        debug!("LayoutTreeBuilder: created flow: {:s}", result.debug_str());
-        result
-    }
-}
diff --git a/src/components/main/layout/construct.rs b/src/components/main/layout/construct.rs
new file mode 100644
index 00000000000..a190783f8d5
--- /dev/null
+++ b/src/components/main/layout/construct.rs
@@ -0,0 +1,614 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+//! Creates flows and boxes from a DOM tree via a bottom-up, incremental traversal of the DOM.
+//!
+//! Each step of the traversal considers the node and existing flow, if there is one. If a node is
+//! not dirty and an existing flow exists, then the traversal reuses that flow. Otherwise, it
+//! proceeds to construct either a flow or a `ConstructionItem`. A construction item is a piece of
+//! intermediate data that goes with a DOM node and hasn't found its "home" yet—maybe it's a render
+//! box, maybe it's an absolute or fixed position thing that hasn't found its containing block yet.
+//! Construction items bubble up the tree from children to parents until they find their homes.
+//!
+//! TODO(pcwalton): There is no incremental reflow yet. This scheme requires that nodes either have
+//! weak references to flows or that there be some mechanism to efficiently (O(1) time) "blow
+//! apart" a flow tree and have the flows migrate "home" to their respective DOM nodes while we
+//! perform flow tree construction. The precise mechanism for this will take some experimentation
+//! to get right.
+//!
+//! TODO(pcwalton): This scheme should be amenable to parallelization, but, of course, that's not
+//! yet implemented.
+
+use css::node_style::StyledNode;
+use layout::block::BlockFlow;
+use layout::box::{GenericRenderBox, ImageRenderBox, RenderBox, RenderBoxBase};
+use layout::box::{UnscannedTextRenderBox};
+use layout::context::LayoutContext;
+use layout::float::FloatFlow;
+use layout::float_context::FloatType;
+use layout::flow::{FlowContext, FlowData, MutableFlowUtils};
+use layout::inline::InlineFlow;
+use layout::text::TextRunScanner;
+use layout::util::LayoutDataAccess;
+
+use script::dom::element::HTMLImageElementTypeId;
+use script::dom::node::{AbstractNode, CommentNodeTypeId, DoctypeNodeTypeId};
+use script::dom::node::{DocumentFragmentNodeTypeId, DocumentNodeTypeId, ElementNodeTypeId};
+use script::dom::node::{LayoutView, PostorderNodeTraversal, TextNodeTypeId};
+use servo_util::slot::Slot;
+use servo_util::tree::TreeNodeRef;
+use std::util;
+use style::computed_values::{display, float};
+
+/// The results of flow construction for a DOM node.
+pub enum ConstructionResult {
+    /// This node contributes nothing at all (`display: none`). Alternately, this is what newly
+    /// created nodes have their `ConstructionResult` set to.
+    NoConstructionResult,
+
+    /// This node contributed a flow at the proper position in the tree. Nothing more needs to be
+    /// done for this node.
+    FlowConstructionResult(~FlowContext:),
+
+    /// This node contributed some object or objects that will be needed to construct a proper flow
+    /// later up the tree, but these objects have not yet found their home.
+    ConstructionItemConstructionResult(ConstructionItem),
+}
+
+/// Represents the output of flow construction for a DOM node that has not yet resulted in a
+/// complete flow. Construction items bubble up the tree until they find a `FlowContext` to be
+/// attached to.
+enum ConstructionItem {
+    /// Inline boxes and associated {ib} splits that have not yet found flows.
+    InlineBoxesConstructionItem(InlineBoxesConstructionResult),
+}
+
+/// Represents inline boxes and {ib} splits that are bubbling up from an inline.
+struct InlineBoxesConstructionResult {
+    /// Any {ib} splits that we're bubbling up.
+    ///
+    /// TODO(pcwalton): Small vector optimization.
+    splits: Option<~[InlineBlockSplit]>,
+
+    /// Any render boxes that succeed the {ib} splits.
+    boxes: ~[@RenderBox],
+}
+
+/// Represents an {ib} split that has not yet found the containing block that it belongs to. This
+/// is somewhat tricky. An example may be helpful. For this DOM fragment:
+///
+///     <span>
+///     A
+///     <div>B</div>
+///     C
+///     </span>
+///
+/// The resulting `ConstructionItem` for the outer `span` will be:
+///
+///     InlineBoxesConstructionItem(Some(~[
+///         InlineBlockSplit {
+///             predecessor_boxes: ~[
+///                 A
+///             ],
+///             block: ~BlockFlow {
+///                 B
+///             },
+///         }),~[
+///             C
+///         ])
+struct InlineBlockSplit {
+    /// The inline render boxes that precede the flow.
+    ///
+    /// TODO(pcwalton): Small vector optimization.
+    predecessor_boxes: ~[@RenderBox],
+
+    /// The flow that caused this {ib} split.
+    flow: ~FlowContext:,
+}
+
+/// Methods on optional vectors.
+///
+/// TODO(pcwalton): I think this will no longer be necessary once Rust #8981 lands.
+trait OptVector<T> {
+    /// Turns this optional vector into an owned one. If the optional vector is `None`, then this
+    /// simply returns an empty owned vector.
+    fn to_vec(self) -> ~[T];
+
+    /// Pushes a value onto this vector.
+    fn push(&mut self, value: T);
+
+    /// Pushes a vector onto this vector, consuming the original.
+    fn push_all_move(&mut self, values: ~[T]);
+
+    /// Pushes an optional vector onto this vector, consuming the original.
+    fn push_opt_vec_move(&mut self, values: Self);
+
+    /// Returns the length of this optional vector.
+    fn len(&self) -> uint;
+}
+
+impl<T> OptVector<T> for Option<~[T]> {
+    #[inline]
+    fn to_vec(self) -> ~[T] {
+        match self {
+            None => ~[],
+            Some(vector) => vector,
+        }
+    }
+
+    #[inline]
+    fn push(&mut self, value: T) {
+        match *self {
+            None => *self = Some(~[value]),
+            Some(ref mut vector) => vector.push(value),
+        }
+    }
+
+    #[inline]
+    fn push_all_move(&mut self, values: ~[T]) {
+        match *self {
+            None => *self = Some(values),
+            Some(ref mut vector) => vector.push_all_move(values),
+        }
+    }
+
+    #[inline]
+    fn push_opt_vec_move(&mut self, values: Option<~[T]>) {
+        match values {
+            None => {}
+            Some(values) => self.push_all_move(values),
+        }
+    }
+
+    #[inline]
+    fn len(&self) -> uint {
+        match *self {
+            None => 0,
+            Some(ref vector) => vector.len(),
+        }
+    }
+}
+
+/// An object that knows how to create flows.
+pub struct FlowConstructor<'self> {
+    /// The layout context.
+    ///
+    /// FIXME(pcwalton): Why does this contain `@`??? That destroys parallelism!!!
+    layout_context: &'self LayoutContext,
+
+    /// The next flow ID to assign.
+    ///
+    /// FIXME(pcwalton): This is going to have to be atomic; can't we do something better?
+    next_flow_id: Slot<int>,
+
+    /// The next box ID to assign.
+    ///
+    /// FIXME(pcwalton): This is going to have to be atomic; can't we do something better?
+    next_box_id: Slot<int>,
+}
+
+impl<'self> FlowConstructor<'self> {
+    /// Creates a new flow constructor.
+    pub fn init<'a>(layout_context: &'a LayoutContext) -> FlowConstructor<'a> {
+        FlowConstructor {
+            layout_context: layout_context,
+            next_flow_id: Slot::init(0),
+            next_box_id: Slot::init(0),
+        }
+    }
+
+    /// Returns the next flow ID and bumps the internal counter.
+    fn next_flow_id(&self) -> int {
+        let id = self.next_flow_id.get();
+        self.next_flow_id.set(id + 1);
+        id
+    }
+
+    /// Returns the next render box ID and bumps the internal counter.
+    fn next_box_id(&self) -> int {
+        let id = self.next_box_id.get();
+        self.next_box_id.set(id + 1);
+        id
+    }
+
+    /// Builds a `RenderBox` for the given image. This is out of line to guide inlining.
+    fn build_box_for_image(&self, base: RenderBoxBase, node: AbstractNode<LayoutView>)
+                           -> @RenderBox {
+        // FIXME(pcwalton): Don't copy URLs.
+        let url = node.with_imm_image_element(|image_element| {
+            image_element.image.as_ref().map(|url| (*url).clone())
+        });
+
+        match url {
+            None => @GenericRenderBox::new(base) as @RenderBox,
+            Some(url) => {
+                // FIXME(pcwalton): The fact that image render boxes store the cache in the
+                // box makes little sense to me.
+                @ImageRenderBox::new(base, url, self.layout_context.image_cache) as @RenderBox
+            }
+        }
+    }
+
+    /// Builds a `RenderBox` for the given node.
+    fn build_box_for_node(&self, node: AbstractNode<LayoutView>) -> @RenderBox {
+        let base = RenderBoxBase::new(node, self.next_box_id());
+        match node.type_id() {
+            ElementNodeTypeId(HTMLImageElementTypeId) => self.build_box_for_image(base, node),
+            TextNodeTypeId => @UnscannedTextRenderBox::new(base) as @RenderBox,
+            _ => @GenericRenderBox::new(base) as @RenderBox,
+        }
+    }
+
+    /// Creates an inline flow from a set of inline boxes and adds it as a child of the given flow.
+    ///
+    /// `#[inline(always)]` because this is performance critical and LLVM will not inline it
+    /// otherwise.
+    #[inline(always)]
+    fn flush_inline_boxes_to_flow(&self,
+                                  boxes: ~[@RenderBox],
+                                  flow: &mut ~FlowContext:,
+                                  node: AbstractNode<LayoutView>) {
+        if boxes.len() > 0 {
+            let inline_base = FlowData::new(self.next_flow_id(), node);
+            let mut inline_flow = ~InlineFlow::from_boxes(inline_base, boxes) as ~FlowContext:;
+            TextRunScanner::new().scan_for_runs(self.layout_context, inline_flow);
+            flow.add_new_child(inline_flow)
+        }
+    }
+
+    /// Creates an inline flow from a set of inline boxes, if present, and adds it as a child of
+    /// the given flow.
+    fn flush_inline_boxes_to_flow_if_necessary(&self,
+                                               opt_boxes: &mut Option<~[@RenderBox]>,
+                                               flow: &mut ~FlowContext:,
+                                               node: AbstractNode<LayoutView>) {
+        let opt_boxes = util::replace(opt_boxes, None);
+        if opt_boxes.len() > 0 {
+            self.flush_inline_boxes_to_flow(opt_boxes.to_vec(), flow, node)
+        }
+    }
+
+    /// Builds the children flows underneath a node with `display: block`. After this call,
+    /// other `BlockFlow`s or `InlineFlow`s will be populated underneath this node, depending on
+    /// whether {ib} splits needed to happen.
+    fn build_children_of_block_flow(&self,
+                                    flow: &mut ~FlowContext:,
+                                    node: AbstractNode<LayoutView>) {
+        // Gather up boxes for the inline flows we might need to create.
+        let mut opt_boxes_for_inline_flow = None;
+        let mut first_box = true;
+        for kid in node.children() {
+            match kid.swap_out_construction_result() {
+                NoConstructionResult => {}
+                FlowConstructionResult(kid_flow) => {
+                    // Strip ignorable whitespace from the start of this flow per CSS 2.1 §
+                    // 9.2.1.1.
+                    if first_box {
+                        strip_ignorable_whitespace_from_start(&mut opt_boxes_for_inline_flow);
+                        first_box = false
+                    }
+
+                    // Flush any inline boxes that we were gathering up. This allows us to handle
+                    // {ib} splits.
+                    self.flush_inline_boxes_to_flow_if_necessary(&mut opt_boxes_for_inline_flow,
+                                                                 flow,
+                                                                 node);
+                    flow.add_new_child(kid_flow);
+                }
+                ConstructionItemConstructionResult(InlineBoxesConstructionItem(
+                        InlineBoxesConstructionResult {
+                            splits: opt_splits,
+                            boxes: boxes
+                        })) => {
+                    // Add any {ib} splits.
+                    match opt_splits {
+                        None => {}
+                        Some(splits) => {
+                            for split in splits.move_iter() {
+                                // Pull apart the {ib} split object and push its predecessor boxes
+                                // onto the list.
+                                let InlineBlockSplit {
+                                    predecessor_boxes: predecessor_boxes,
+                                    flow: kid_flow
+                                } = split;
+                                opt_boxes_for_inline_flow.push_all_move(predecessor_boxes);
+
+                                // If this is the first box in flow, then strip ignorable
+                                // whitespace per CSS 2.1 § 9.2.1.1.
+                                if first_box {
+                                    strip_ignorable_whitespace_from_start(
+                                        &mut opt_boxes_for_inline_flow);
+                                    first_box = false
+                                }
+
+                                // Flush any inline boxes that we were gathering up.
+                                self.flush_inline_boxes_to_flow_if_necessary(
+                                        &mut opt_boxes_for_inline_flow,
+                                        flow,
+                                        node);
+
+                                // Push the flow generated by the {ib} split onto our list of
+                                // flows.
+                                flow.add_new_child(kid_flow);
+                            }
+                        }
+                    }
+
+                    // Add the boxes to the list we're maintaining.
+                    opt_boxes_for_inline_flow.push_all_move(boxes)
+                }
+            }
+        }
+
+        // Perform a final flush of any inline boxes that we were gathering up to handle {ib}
+        // splits, after stripping ignorable whitespace.
+        strip_ignorable_whitespace_from_end(&mut opt_boxes_for_inline_flow);
+        self.flush_inline_boxes_to_flow_if_necessary(&mut opt_boxes_for_inline_flow,
+                                                     flow,
+                                                     node);
+    }
+
+    /// Builds a flow for a node with `display: block`. This yields a `BlockFlow` with possibly
+    /// other `BlockFlow`s or `InlineFlow`s underneath it, depending on whether {ib} splits needed
+    /// to happen.
+    fn build_flow_for_block(&self, node: AbstractNode<LayoutView>) -> ~FlowContext: {
+        let base = FlowData::new(self.next_flow_id(), node);
+        let box = self.build_box_for_node(node);
+        let mut flow = ~BlockFlow::from_box(base, box) as ~FlowContext:;
+        self.build_children_of_block_flow(&mut flow, node);
+        flow
+    }
+
+    /// Builds the flow for a node with `float: {left|right}`. This yields a `FloatFlow` with a
+    /// `BlockFlow` underneath it.
+    fn build_flow_for_floated_block(&self, node: AbstractNode<LayoutView>, float_type: FloatType)
+                                    -> ~FlowContext: {
+        let base = FlowData::new(self.next_flow_id(), node);
+        let box = self.build_box_for_node(node);
+        let mut flow = ~FloatFlow::from_box(base, float_type, box) as ~FlowContext:;
+        self.build_children_of_block_flow(&mut flow, node);
+        flow
+    }
+
+    /// Concatenates the boxes of kids, adding in our own borders/padding/margins if necessary.
+    /// Returns the `InlineBoxesConstructionResult`, if any. There will be no
+    /// `InlineBoxesConstructionResult` if this node consisted entirely of ignorable whitespace.
+    fn build_boxes_for_nonreplaced_inline_content(&self, node: AbstractNode<LayoutView>)
+                                                  -> ConstructionResult {
+        let mut opt_inline_block_splits = None;
+        let mut opt_box_accumulator = None;
+
+        // Concatenate all the render boxes of our kids, creating {ib} splits as necessary.
+        for kid in node.children() {
+            match kid.swap_out_construction_result() {
+                NoConstructionResult => {}
+                FlowConstructionResult(flow) => {
+                    // {ib} split. Flush the accumulator to our new split and make a new
+                    // accumulator to hold any subsequent `RenderBox`es we come across.
+                    let split = InlineBlockSplit {
+                        predecessor_boxes: util::replace(&mut opt_box_accumulator, None).to_vec(),
+                        flow: flow,
+                    };
+                    opt_inline_block_splits.push(split)
+                }
+                ConstructionItemConstructionResult(InlineBoxesConstructionItem(
+                        InlineBoxesConstructionResult {
+                            splits: opt_splits,
+                            boxes: boxes
+                        })) => {
+                    // Bubble up {ib} splits.
+                    match opt_splits {
+                        None => {}
+                        Some(splits) => {
+                            for split in splits.move_iter() {
+                                let InlineBlockSplit {
+                                    predecessor_boxes: boxes,
+                                    flow: kid_flow
+                                } = split;
+                                opt_box_accumulator.push_all_move(boxes);
+
+                                let split = InlineBlockSplit {
+                                    predecessor_boxes: util::replace(&mut opt_box_accumulator,
+                                                                     None).to_vec(),
+                                    flow: kid_flow,
+                                };
+                                opt_inline_block_splits.push(split)
+                            }
+                        }
+                    }
+
+                    // Push residual boxes.
+                    opt_box_accumulator.push_all_move(boxes)
+                }
+            }
+        }
+
+        // TODO(pcwalton): Add in our own borders/padding/margins if necessary.
+
+        // Finally, make a new construction result.
+        if opt_inline_block_splits.len() > 0 || opt_box_accumulator.len() > 0 {
+            let construction_item = InlineBoxesConstructionItem(InlineBoxesConstructionResult {
+                splits: opt_inline_block_splits,
+                boxes: opt_box_accumulator.to_vec(),
+            });
+            ConstructionItemConstructionResult(construction_item)
+        } else {
+            NoConstructionResult
+        }
+    }
+
+    /// Creates an `InlineBoxesConstructionResult` for replaced content. Replaced content doesn't
+    /// render its children, so this just nukes a child's boxes and creates a `RenderBox`.
+    fn build_boxes_for_replaced_inline_content(&self, node: AbstractNode<LayoutView>)
+                                               -> ConstructionResult {
+        for kid in node.children() {
+            kid.set_flow_construction_result(NoConstructionResult)
+        }
+
+        let construction_item = InlineBoxesConstructionItem(InlineBoxesConstructionResult {
+            splits: None,
+            boxes: ~[
+                self.build_box_for_node(node)
+            ],
+        });
+        ConstructionItemConstructionResult(construction_item)
+    }
+
+    /// Builds one or more render boxes for a node with `display: inline`. This yields an
+    /// `InlineBoxesConstructionResult`.
+    fn build_boxes_for_inline(&self, node: AbstractNode<LayoutView>) -> ConstructionResult {
+        // Is this node replaced content?
+        if !node.is_replaced_content() {
+            // Go to a path that concatenates our kids' boxes.
+            self.build_boxes_for_nonreplaced_inline_content(node)
+        } else {
+            // Otherwise, just nuke our kids' boxes, create our `RenderBox` if any, and be done
+            // with it.
+            self.build_boxes_for_replaced_inline_content(node)
+        }
+    }
+}
+
+impl<'self> PostorderNodeTraversal for FlowConstructor<'self> {
+    // `#[inline(always)]` because this is always called from the traversal function and for some
+    // reason LLVM's inlining heuristics go awry here.
+    #[inline(always)]
+    fn process(&self, node: AbstractNode<LayoutView>) -> bool {
+        // Get the `display` property for this node, and determine whether this node is floated.
+        let (display, float) = match node.type_id() {
+            ElementNodeTypeId(_) => (node.style().Box.display, node.style().Box.float),
+            TextNodeTypeId => (display::inline, float::none),
+            CommentNodeTypeId |
+            DoctypeNodeTypeId |
+            DocumentFragmentNodeTypeId |
+            DocumentNodeTypeId(_) => (display::none, float::none),
+        };
+
+        // Switch on display and floatedness.
+        match (display, float) {
+            // `display: none` contributes no flow construction result. Nuke the flow construction
+            // results of children.
+            (display::none, _) => {
+                for child in node.children() {
+                    child.set_flow_construction_result(NoConstructionResult)
+                }
+            }
+
+            // Inline items contribute inline render box construction results.
+            (display::inline, float::none) => {
+                let construction_result = self.build_boxes_for_inline(node);
+                node.set_flow_construction_result(construction_result)
+            }
+
+            // Block flows that are not floated contribute block flow construction results.
+            //
+            // TODO(pcwalton): Make this only trigger for blocks and handle the other `display`
+            // properties separately.
+            (_, float::none) => {
+                let flow = self.build_flow_for_block(node);
+                node.set_flow_construction_result(FlowConstructionResult(flow))
+            }
+
+            // Floated flows contribute float flow construction results.
+            (_, float_value) => {
+                let float_type = FloatType::from_property(float_value);
+                let flow = self.build_flow_for_floated_block(node, float_type);
+                node.set_flow_construction_result(FlowConstructionResult(flow))
+            }
+        }
+
+        true
+    }
+}
+
+/// A utility trait with some useful methods for node queries.
+trait NodeUtils {
+    /// Returns true if this node doesn't render its kids and false otherwise.
+    fn is_replaced_content(self) -> bool;
+
+    /// Sets the construction result of a flow.
+    fn set_flow_construction_result(self, result: ConstructionResult);
+
+    /// Replaces the flow construction result in a node with `NoConstructionResult` and returns the
+    /// old value.
+    fn swap_out_construction_result(self) -> ConstructionResult;
+
+    /// Returns true if this node consists entirely of ignorable whitespace and false otherwise.
+    /// Ignorable whitespace is defined as whitespace that would be removed per CSS 2.1 § 16.6.1.
+    fn is_ignorable_whitespace(self) -> bool;
+}
+
+impl NodeUtils for AbstractNode<LayoutView> {
+    fn is_replaced_content(self) -> bool {
+        match self.type_id() {
+            TextNodeTypeId |
+            CommentNodeTypeId |
+            DoctypeNodeTypeId |
+            DocumentFragmentNodeTypeId |
+            DocumentNodeTypeId(_) |
+            ElementNodeTypeId(HTMLImageElementTypeId) => true,
+            ElementNodeTypeId(_) => false,
+        }
+    }
+
+    #[inline(always)]
+    fn set_flow_construction_result(self, result: ConstructionResult) {
+        match *self.mutate_layout_data().ptr {
+            Some(ref mut layout_data) => layout_data.flow_construction_result = result,
+            None => fail!("no layout data"),
+        }
+    }
+
+    #[inline(always)]
+    fn swap_out_construction_result(self) -> ConstructionResult {
+        match *self.mutate_layout_data().ptr {
+            Some(ref mut layout_data) => {
+                util::replace(&mut layout_data.flow_construction_result, NoConstructionResult)
+            }
+            None => fail!("no layout data"),
+        }
+    }
+
+    fn is_ignorable_whitespace(self) -> bool {
+        self.is_text() && self.with_imm_text(|text| text.element.data.is_whitespace())
+    }
+}
+
+/// Strips ignorable whitespace from the start of a list of boxes.
+fn strip_ignorable_whitespace_from_start(opt_boxes: &mut Option<~[@RenderBox]>) {
+    match util::replace(opt_boxes, None) {
+        None => return,
+        Some(boxes) => {
+            // FIXME(pcwalton): This is slow because vector shift is broken. :(
+            let mut found_nonwhitespace = false;
+            let mut result = ~[];
+            for box in boxes.move_iter() {
+                if !found_nonwhitespace && box.is_whitespace_only() {
+                    continue
+                }
+
+                found_nonwhitespace = true;
+                result.push(box)
+            }
+
+            *opt_boxes = Some(result)
+        }
+    }
+}
+
+/// Strips ignorable whitespace from the end of a list of boxes.
+fn strip_ignorable_whitespace_from_end(opt_boxes: &mut Option<~[@RenderBox]>) {
+    match *opt_boxes {
+        None => {}
+        Some(ref mut boxes) => {
+            while boxes.len() > 0 && boxes.last().is_whitespace_only() {
+                let _ = boxes.pop();
+            }
+        }
+    }
+    if opt_boxes.len() == 0 {
+        *opt_boxes = None
+    }
+}
+
diff --git a/src/components/main/layout/extra.rs b/src/components/main/layout/extra.rs
index 0bb1cbb4cd2..2683d8d0b34 100644
--- a/src/components/main/layout/extra.rs
+++ b/src/components/main/layout/extra.rs
@@ -8,7 +8,6 @@ use layout::util::{DisplayBoxes, LayoutData, LayoutDataAccess};
 
 use script::dom::node::{AbstractNode, LayoutView};
 use servo_util::tree::TreeNodeRef;
-use std::cast;
 
 /// Functionality useful for querying the layout-specific data on DOM nodes.
 pub trait LayoutAuxMethods {
@@ -18,20 +17,17 @@ pub trait LayoutAuxMethods {
 
 impl LayoutAuxMethods for AbstractNode<LayoutView> {
     /// Resets layout data and styles for the node.
-    ///
-    /// FIXME(pcwalton): Do this as part of box building instead of in a traversal.
     fn initialize_layout_data(self) {
-        unsafe {
-            let node = cast::transmute_mut(self.node());
-            if node.layout_data.is_none() {
-                node.layout_data = Some(~LayoutData::new() as ~Any)
-            } else {
-                self.layout_data().boxes.set(DisplayBoxes::init());
-            }
+        let layout_data_handle = self.mutate_layout_data();
+        match *layout_data_handle.ptr {
+            None => *layout_data_handle.ptr = Some(~LayoutData::new()),
+            Some(ref mut layout_data) => layout_data.boxes = DisplayBoxes::init(),
         }
     }
 
     /// Resets layout data and styles for a Node tree.
+    ///
+    /// FIXME(pcwalton): Do this as part of box building instead of in a traversal.
     fn initialize_style_for_subtree(self) {
         for n in self.traverse_preorder() {
             n.initialize_layout_data();
diff --git a/src/components/main/layout/float.rs b/src/components/main/layout/float.rs
index 3559ca4e842..be7ac50524b 100644
--- a/src/components/main/layout/float.rs
+++ b/src/components/main/layout/float.rs
@@ -53,6 +53,18 @@ impl FloatFlow {
         }
     }
 
+    pub fn from_box(base: FlowData, float_type: FloatType, box: @RenderBox) -> FloatFlow {
+        FloatFlow {
+            base: base,
+            containing_width: Au(0),
+            box: Some(box),
+            index: None,
+            float_type: float_type,
+            rel_pos: Point2D(Au(0), Au(0)),
+            floated_children: 0,
+        }
+    }
+
     pub fn teardown(&mut self) {
         for box in self.box.iter() {
             box.teardown();
@@ -252,7 +264,7 @@ impl FlowContext for FloatFlow {
     }
 
     fn assign_height(&mut self, ctx: &mut LayoutContext) {
-        debug!("assign_height_float: assigning height for float {}", self.base.id);
+        // Now that we've determined our height, propagate that out.
         let has_inorder_children = self.base.num_floats > 0;
         if has_inorder_children {
             let mut float_ctx = FloatContext::new(self.floated_children);
@@ -262,7 +274,7 @@ impl FlowContext for FloatFlow {
                 float_ctx = flow::mut_base(*kid).floats_out.clone();
             }
         }
-
+        debug!("assign_height_float: assigning height for float {}", self.base.id);
         let mut cur_y = Au(0);
         let mut top_offset = Au(0);
 
@@ -281,26 +293,25 @@ impl FlowContext for FloatFlow {
         let mut height = cur_y - top_offset;
 
         let mut noncontent_height;
-        for box in self.box.iter() {
-            let base = box.base();
-            let mut position_ref = base.position.mutate();
-            let position = &mut position_ref.ptr;
+        let box = self.box.as_ref().unwrap();
+        let base = box.base();
+        let mut position_ref = base.position.mutate();
+        let position = &mut position_ref.ptr;
 
-            // The associated box is the border box of this flow.
-            position.origin.y = base.margin.top;
+        // The associated box is the border box of this flow.
+        position.origin.y = base.margin.top;
 
-            noncontent_height = base.padding.top + base.padding.bottom + base.border.top +
-                base.border.bottom;
-        
-            //TODO(eatkinson): compute heights properly using the 'height' property.
-            let height_prop = MaybeAuto::from_style(base.style().Box.height,
-                                                    Au::new(0)).specified_or_zero();
+        noncontent_height = base.padding.top + base.padding.bottom + base.border.top +
+            base.border.bottom;
+    
+        //TODO(eatkinson): compute heights properly using the 'height' property.
+        let height_prop = MaybeAuto::from_style(base.style().Box.height,
+                                                Au::new(0)).specified_or_zero();
 
-            height = geometry::max(height, height_prop) + noncontent_height;
-            debug!("assign_height_float -- height: {}", height);
+        height = geometry::max(height, height_prop) + noncontent_height;
+        debug!("assign_height_float -- height: {}", height);
 
-            position.size.height = height;
-        }
+        position.size.height = height;
 
     }
 
@@ -314,6 +325,7 @@ impl FlowContext for FloatFlow {
         // Margins between a floated box and any other box do not collapse.
         *collapsing = Au::new(0);
     }
+
     fn debug_str(&self) -> ~str {
         ~"FloatFlow"
     }
diff --git a/src/components/main/layout/float_context.rs b/src/components/main/layout/float_context.rs
index 45e142b24b9..7a92554401c 100644
--- a/src/components/main/layout/float_context.rs
+++ b/src/components/main/layout/float_context.rs
@@ -3,12 +3,13 @@
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 use geom::point::Point2D;
-use geom::size::Size2D;
 use geom::rect::Rect;
+use geom::size::Size2D;
 use servo_util::geometry::{Au, max, min};
+use std::i32::max_value;
 use std::util::replace;
 use std::vec;
-use std::i32::max_value;
+use style::computed_values::float;
 
 #[deriving(Clone)]
 pub enum FloatType {
@@ -16,6 +17,16 @@ pub enum FloatType {
     FloatRight
 }
 
+impl FloatType {
+    pub fn from_property(property: float::T) -> FloatType {
+        match property {
+            float::none => fail!("can't create a float type from an unfloated property"),
+            float::left => FloatLeft,
+            float::right => FloatRight,
+        }
+    }
+}
+
 pub enum ClearType {
     ClearLeft,
     ClearRight,
@@ -31,13 +42,13 @@ struct FloatContextBase {
 }
 
 #[deriving(Clone)]
-struct FloatData{
+struct FloatData {
     bounds: Rect<Au>,
     f_type: FloatType
 }
 
 /// All information necessary to place a float
-pub struct PlacementInfo{
+pub struct PlacementInfo {
     width: Au,      // The dimensions of the float
     height: Au,
     ceiling: Au,    // The minimum top of the float, as determined by earlier elements
@@ -126,7 +137,7 @@ impl FloatContext {
     }
 }
 
-impl FloatContextBase{
+impl FloatContextBase {
     fn new(num_floats: uint) -> FloatContextBase {
         debug!("Creating float context of size {}", num_floats);
         FloatContextBase {
@@ -335,7 +346,7 @@ impl FloatContextBase{
             match maybe_location {
 
                 // If there are no floats blocking us, return the current location
-                // TODO(eatknson): integrate with overflow
+                // TODO(eatkinson): integrate with overflow
                 None => return match info.f_type { 
                     FloatLeft => Rect(Point2D(Au(0), float_y), 
                                       Size2D(info.max_width, Au(max_value))),
diff --git a/src/components/main/layout/flow.rs b/src/components/main/layout/flow.rs
index afa0f80b258..27d61f9dd84 100644
--- a/src/components/main/layout/flow.rs
+++ b/src/components/main/layout/flow.rs
@@ -111,6 +111,9 @@ pub trait FlowContext {
         fail!("collapse_margins not yet implemented")
     }
 
+    /// Marks this flow as the root flow. The default implementation is a no-op.
+    fn mark_as_root(&mut self) {}
+
     /// Returns a debugging string describing this flow.
     fn debug_str(&self) -> ~str {
         ~"???"
@@ -360,6 +363,7 @@ impl Iterator<@RenderBox> for BoxIterator {
 }
 
 impl FlowData {
+    #[inline]
     pub fn new(id: int, node: AbstractNode<LayoutView>) -> FlowData {
         FlowData {
             node: node,
diff --git a/src/components/main/layout/inline.rs b/src/components/main/layout/inline.rs
index 39fda3b7961..2a0c412fb32 100644
--- a/src/components/main/layout/inline.rs
+++ b/src/components/main/layout/inline.rs
@@ -196,14 +196,14 @@ impl LineboxScanner {
         debug!("LineboxScanner: Trying to place first box of line {}", self.lines.len());
 
         let first_box_size = first_box.base().position.get().size;
-        debug!("LineboxScanner: box size: {}", first_box_size);
-        let splitable = first_box.can_split();
+        let splittable = first_box.can_split();
+        debug!("LineboxScanner: box size: {}, splittable: {}", first_box_size, splittable);
         let line_is_empty: bool = self.pending_line.range.length() == 0;
 
-        // Initally, pretend a splitable box has 0 width.
+        // Initally, pretend a splittable box has 0 width.
         // We will move it later if it has nonzero width
         // and that causes problems.
-        let placement_width = if splitable {
+        let placement_width = if splittable {
             Au::new(0)
         } else {
             first_box_size.width
@@ -231,7 +231,7 @@ impl LineboxScanner {
 
         // If not, but we can't split the box, then we'll place
         // the line here and it will overflow.
-        if !splitable {
+        if !splittable {
             debug!("LineboxScanner: case=line doesn't fit, but is unsplittable");
             return (line_bounds, first_box_size.width);
         }
@@ -467,6 +467,15 @@ impl InlineFlow {
         }
     }
 
+    pub fn from_boxes(base: FlowData, boxes: ~[@RenderBox]) -> InlineFlow {
+        InlineFlow {
+            base: base,
+            boxes: boxes,
+            lines: ~[],
+            elems: ElementMapping::new(),
+        }
+    }
+
     pub fn teardown(&mut self) {
         for box in self.boxes.iter() {
             box.teardown();
diff --git a/src/components/main/layout/layout_task.rs b/src/components/main/layout/layout_task.rs
index f2bbfe55b04..4542b01323d 100644
--- a/src/components/main/layout/layout_task.rs
+++ b/src/components/main/layout/layout_task.rs
@@ -7,66 +7,87 @@
 
 use css::matching::MatchMethods;
 use css::select::new_stylist;
-use layout::extra::LayoutAuxMethods;
-use layout::box_builder::LayoutTreeBuilder;
+use layout::construct::{FlowConstructionResult, FlowConstructor, NoConstructionResult};
 use layout::context::LayoutContext;
 use layout::display_list_builder::{DisplayListBuilder};
+use layout::extra::LayoutAuxMethods;
 use layout::flow::{FlowContext, ImmutableFlowUtils, MutableFlowUtils, PreorderFlowTraversal};
 use layout::flow::{PostorderFlowTraversal};
 use layout::flow;
 use layout::incremental::{RestyleDamage, BubbleWidths};
-use layout::util::LayoutDataAccess;
+use layout::util::{LayoutData, LayoutDataAccess};
 
-use std::cast::transmute;
-use std::cell::Cell;
-use std::comm::Port;
-use std::task;
 use extra::arc::{Arc, RWArc};
 use geom::point::Point2D;
 use geom::rect::Rect;
 use geom::size::Size2D;
 use gfx::display_list::DisplayList;
 use gfx::font_context::FontContext;
-use servo_util::geometry::Au;
 use gfx::opts::Opts;
 use gfx::render_task::{RenderMsg, RenderChan, RenderLayer};
 use gfx::render_task;
-use style::Stylist;
-use style::Stylesheet;
-use style::AuthorOrigin;
 use script::dom::event::ReflowEvent;
-use script::dom::node::{AbstractNode, LayoutView};
+use script::dom::node::{AbstractNode, LayoutDataRef, LayoutView};
 use script::layout_interface::{AddStylesheetMsg, ContentBoxQuery};
+use script::layout_interface::{ContentBoxesQuery, ContentBoxesResponse, ExitNowMsg, LayoutQuery};
 use script::layout_interface::{HitTestQuery, ContentBoxResponse, HitTestResponse};
-use script::layout_interface::{ContentBoxesQuery, ContentBoxesResponse, ExitMsg, LayoutQuery};
-use script::layout_interface::{MatchSelectorsDocumentDamage, Msg};
-use script::layout_interface::{QueryMsg, Reflow, ReflowDocumentDamage};
+use script::layout_interface::{MatchSelectorsDocumentDamage, Msg, PrepareToExitMsg};
+use script::layout_interface::{QueryMsg, ReapLayoutDataMsg, Reflow, ReflowDocumentDamage};
 use script::layout_interface::{ReflowForDisplay, ReflowMsg};
 use script::script_task::{ReflowCompleteMsg, ScriptChan, SendEventMsg};
 use servo_msg::constellation_msg::{ConstellationChan, PipelineId};
 use servo_net::image_cache_task::{ImageCacheTask, ImageResponseMsg};
 use servo_net::local_image_cache::{ImageResponder, LocalImageCache};
-use servo_util::tree::TreeNodeRef;
+use servo_util::geometry::Au;
+use servo_util::range::Range;
 use servo_util::time::{ProfilerChan, profile};
 use servo_util::time;
-use servo_util::range::Range;
-use extra::url::Url;
+use servo_util::tree::TreeNodeRef;
+use std::cast::transmute;
+use std::cast;
+use std::cell::Cell;
+use std::comm::Port;
+use std::task;
+use std::util;
+use style::AuthorOrigin;
+use style::Stylesheet;
+use style::Stylist;
 
+/// Information needed by the layout task.
 struct LayoutTask {
+    /// The ID of the pipeline that we belong to.
     id: PipelineId,
+
+    /// The port on which we receive messages.
     port: Port<Msg>,
+
+    /// The channel on which messages can be sent to the constellation.
     constellation_chan: ConstellationChan,
+
+    /// The channel on which messages can be sent to the script task.
     script_chan: ScriptChan,
+
+    /// The channel on which messages can be sent to the painting task.
     render_chan: RenderChan<AbstractNode<()>>,
+
+    /// The channel on which messages can be sent to the image cache.
     image_cache_task: ImageCacheTask,
+
+    /// The local image cache.
     local_image_cache: @mut LocalImageCache,
+
+    /// The local font context.
     font_ctx: @mut FontContext,
-    doc_url: Option<Url>,
+
+    /// The size of the viewport.
     screen_size: Option<Size2D<Au>>,
 
+    /// A cached display list.
     display_list: Option<Arc<DisplayList<AbstractNode<()>>>>,
 
     stylist: RWArc<Stylist>,
+
+    /// The channel on which messages can be sent to the profiler.
     profiler_chan: ProfilerChan,
 }
 
@@ -195,6 +216,7 @@ impl ImageResponder for LayoutImageResponder {
 }
 
 impl LayoutTask {
+    /// Spawns a new layout task.
     pub fn create(id: PipelineId,
                   port: Port<Msg>,
                   constellation_chan: ConstellationChan,
@@ -217,6 +239,7 @@ impl LayoutTask {
         });
     }
 
+    /// Creates a new `LayoutTask` structure.
     fn new(id: PipelineId,
            port: Port<Msg>,
            constellation_chan: ConstellationChan,
@@ -237,7 +260,6 @@ impl LayoutTask {
             image_cache_task: image_cache_task.clone(),
             local_image_cache: @mut LocalImageCache(image_cache_task),
             font_ctx: fctx,
-            doc_url: None,
             screen_size: None,
 
             display_list: None,
@@ -247,6 +269,7 @@ impl LayoutTask {
         }
     }
 
+    /// Starts listening on the port.
     fn start(&mut self) {
         while self.handle_request() {
             // Loop indefinitely.
@@ -266,6 +289,7 @@ impl LayoutTask {
         }
     }
 
+    /// Receives and dispatches messages from the port.
     fn handle_request(&mut self) -> bool {
         match self.port.recv() {
             AddStylesheetMsg(sheet) => self.handle_add_stylesheet(sheet),
@@ -282,11 +306,17 @@ impl LayoutTask {
                     self.handle_query(query.take());
                 }
             }
-            ExitMsg => {
-                debug!("layout: ExitMsg received");
-                let (response_port, response_chan) = stream();
-                self.render_chan.send(render_task::ExitMsg(response_chan));
-                response_port.recv();
+            ReapLayoutDataMsg(dead_layout_data) => {
+                unsafe {
+                    self.handle_reap_layout_data(dead_layout_data)
+                }
+            }
+            PrepareToExitMsg(response_chan) => {
+                self.prepare_to_exit(response_chan)
+            }
+            ExitNowMsg => {
+                debug!("layout: ExitNowMsg received");
+                self.exit_now();
                 return false
             }
         }
@@ -294,6 +324,32 @@ impl LayoutTask {
         true
     }
 
+    /// Enters a quiescent state in which no new messages except for `ReapLayoutDataMsg` will be
+    /// processed until an `ExitNowMsg` is received. A pong is immediately sent on the given
+    /// response channel.
+    fn prepare_to_exit(&mut self, response_chan: Chan<()>) {
+        response_chan.send(());
+        match self.port.recv() {
+            ReapLayoutDataMsg(dead_layout_data) => {
+                unsafe {
+                    self.handle_reap_layout_data(dead_layout_data)
+                }
+            }
+            ExitNowMsg => self.exit_now(),
+            _ => {
+                fail!("layout: message that wasn't `ExitNowMsg` received after `PrepareToExitMsg`")
+            }
+        }
+    }
+
+    /// Shuts down the layout task now. If there are any DOM nodes left, layout will now (safely)
+    /// crash.
+    fn exit_now(&mut self) {
+        let (response_port, response_chan) = stream();
+        self.render_chan.send(render_task::ExitMsg(response_chan));
+        response_port.recv()
+    }
+
     fn handle_add_stylesheet(&mut self, sheet: Stylesheet) {
         let sheet = Cell::new(sheet);
         do self.stylist.write |stylist| {
@@ -301,6 +357,31 @@ impl LayoutTask {
         }
     }
 
+    /// 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: &LayoutContext, node: AbstractNode<LayoutView>)
+                           -> ~FlowContext: {
+        node.traverse_postorder(&FlowConstructor::init(layout_context));
+
+        let result = match *node.mutate_layout_data().ptr {
+            Some(ref mut layout_data) => {
+                util::replace(&mut layout_data.flow_construction_result, NoConstructionResult)
+            }
+            None => fail!("no layout data for root node"),
+        };
+        let mut flow = match result {
+            FlowConstructionResult(flow) => flow,
+            _ => fail!("Flow construction didn't result in a flow at the root of the tree!"),
+        };
+        flow.mark_as_root();
+        flow
+    }
+
     /// Performs layout constraint solving.
     ///
     /// This corresponds to `Reflow()` in Gecko and `layout()` in WebKit/Blink and should be
@@ -331,17 +412,14 @@ impl LayoutTask {
             transmute(&data.document_root)
         };
 
-        // FIXME: Bad copy!
-        let doc_url = data.url.clone();
-
-        debug!("layout: received layout request for: {:s}", doc_url.to_str());
+        debug!("layout: received layout request for: {:s}", data.url.to_str());
         debug!("layout: damage is {:?}", data.damage);
         debug!("layout: parsed Node tree");
         debug!("{:?}", node.dump());
+
         // Reset the image cache.
         self.local_image_cache.next_round(self.make_on_image_available_cb());
 
-        self.doc_url = Some(doc_url);
         let screen_size = Size2D(Au::from_px(data.window_size.width as int),
                                  Au::from_px(data.window_size.height as int));
         let resized = self.screen_size != Some(screen_size);
@@ -370,16 +448,9 @@ impl LayoutTask {
         }
 
         // Construct the flow tree.
-        let mut layout_root: ~FlowContext: = do profile(time::LayoutTreeBuilderCategory,
-                                                   self.profiler_chan.clone()) {
-            let mut builder = LayoutTreeBuilder::new();
-            let layout_root: ~FlowContext: = match builder.construct_trees(&layout_ctx, *node) {
-                Ok(root) => root,
-                Err(*) => fail!(~"Root flow should always exist")
-            };
-
-            layout_root
-        };
+        let mut layout_root = profile(time::LayoutTreeBuilderCategory,
+                                      self.profiler_chan.clone(),
+                                      || self.construct_flow_tree(&layout_ctx, *node));
 
         // Propagate damage.
         layout_root.traverse_preorder(&mut PropagateDamageTraversal {
@@ -421,22 +492,26 @@ impl LayoutTask {
                     };
 
                     // FIXME(pcwalton): Why are we cloning the display list here?!
-                    let layout_data = node.layout_data();
-                    let boxes = layout_data.boxes.mutate();
-                    boxes.ptr.display_list = Some(display_list.clone());
-
-                    if boxes.ptr.range.is_none() {
-                        debug!("Creating initial range for node");
-                        boxes.ptr.range = Some(Range::new(i,1));
-                    } else {
-                        debug!("Appending item to range");
-                        unsafe {
-                            let old_node: AbstractNode<()> = transmute(node);
-                            assert!(old_node == display_list.get().list[i-1].base().extra,
-                            "Non-contiguous arrangement of display items");
-                        }
+                    match *node.mutate_layout_data().ptr {
+                        Some(ref mut layout_data) => {
+                            let boxes = &mut layout_data.boxes;
+                            boxes.display_list = Some(display_list.clone());
+
+                            if boxes.range.is_none() {
+                                debug!("Creating initial range for node");
+                                boxes.range = Some(Range::new(i,1));
+                            } else {
+                                debug!("Appending item to range");
+                                unsafe {
+                                    let old_node: AbstractNode<()> = transmute(node);
+                                    assert!(old_node == display_list.get().list[i-1].base().extra,
+                                    "Non-contiguous arrangement of display items");
+                                }
 
-                        boxes.ptr.range.unwrap().extend_by(1);
+                                boxes.range.unwrap().extend_by(1);
+                            }
+                        }
+                        None => fail!("no layout data"),
                     }
                 }
 
@@ -472,8 +547,8 @@ impl LayoutTask {
 
                 fn box_for_node(node: AbstractNode<LayoutView>) -> Option<Rect<Au>> {
                     // FIXME(pcwalton): Why are we cloning the display list here?!
-                    let boxes = node.layout_data().boxes.borrow();
-                    let boxes = boxes.ptr;
+                    let layout_data = node.borrow_layout_data();
+                    let boxes = &layout_data.ptr.as_ref().unwrap().boxes;
                     match (boxes.display_list.clone(), boxes.range) {
                         (Some(display_list), Some(range)) => {
                             let mut rect: Option<Rect<Au>> = None;
@@ -516,8 +591,8 @@ impl LayoutTask {
 
                 fn boxes_for_node(node: AbstractNode<LayoutView>, mut box_accumulator: ~[Rect<Au>])
                                   -> ~[Rect<Au>] {
-                    let boxes = node.layout_data().boxes.borrow();
-                    let boxes = boxes.ptr;
+                    let layout_data = node.borrow_layout_data();
+                    let boxes = &layout_data.ptr.as_ref().unwrap().boxes;
                     match (boxes.display_list.clone(), boxes.range) {
                         (Some(display_list), Some(range)) => {
                             for i in range.eachi() {
@@ -589,5 +664,12 @@ impl LayoutTask {
             script_chan: self.script_chan.clone(),
         } as @ImageResponder
     }
+
+    /// Handles a message to destroy layout data. Layout data must be destroyed on *this* task
+    /// because it contains local managed pointers.
+    unsafe fn handle_reap_layout_data(&self, layout_data: LayoutDataRef) {
+        let ptr: &mut Option<~LayoutData> = cast::transmute(layout_data.borrow_unchecked());
+        *ptr = None
+    }
 }
 
diff --git a/src/components/main/layout/util.rs b/src/components/main/layout/util.rs
index eba5270489b..e6409bb6dbc 100644
--- a/src/components/main/layout/util.rs
+++ b/src/components/main/layout/util.rs
@@ -3,14 +3,15 @@
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 use layout::box::{RenderBox, RenderBoxUtils};
+use layout::construct::{ConstructionResult, NoConstructionResult};
 
 use extra::arc::Arc;
 use gfx::display_list::DisplayList;
 use script::dom::node::{AbstractNode, LayoutView};
 use servo_util::range::Range;
-use servo_util::slot::Slot;
+use servo_util::slot::{MutSlotRef, SlotRef};
 use servo_util::tree::TreeNodeRef;
-use std::any::AnyRefExt;
+use std::cast;
 use std::iter::Enumerate;
 use std::vec::VecIterator;
 use style::{ComputedValues, PropertyDeclaration};
@@ -140,47 +141,66 @@ impl ElementMapping {
 /// Data that layout associates with a node.
 pub struct LayoutData {
     /// The results of CSS matching for this node.
-    applicable_declarations: Slot<~[Arc<~[PropertyDeclaration]>]>,
+    applicable_declarations: ~[Arc<~[PropertyDeclaration]>],
 
     /// The results of CSS styling for this node.
-    style: Slot<Option<ComputedValues>>,
+    style: Option<ComputedValues>,
 
     /// Description of how to account for recent style changes.
-    restyle_damage: Slot<Option<int>>,
+    restyle_damage: Option<int>,
 
     /// The boxes assosiated with this flow.
     /// Used for getBoundingClientRect and friends.
-    boxes: Slot<DisplayBoxes>,
+    boxes: DisplayBoxes,
+
+    /// The current results of flow construction for this node. This is either a flow or a
+    /// `ConstructionItem`. See comments in `construct.rs` for more details.
+    flow_construction_result: ConstructionResult,
 }
 
 impl LayoutData {
     /// Creates new layout data.
     pub fn new() -> LayoutData {
         LayoutData {
-            applicable_declarations: Slot::init(~[]),
-            style: Slot::init(None),
-            restyle_damage: Slot::init(None),
-            boxes: Slot::init(DisplayBoxes::init()),
+            applicable_declarations: ~[],
+            style: None,
+            restyle_damage: None,
+            boxes: DisplayBoxes::init(),
+            flow_construction_result: NoConstructionResult,
         }
     }
 }
 
-// This serves as a static assertion that layout data remains sendable. If this is not done, then
-// we can have memory unsafety, which usually manifests as shutdown crashes.
-fn assert_is_sendable<T:Send>(_: T) {}
-fn assert_layout_data_is_sendable() {
-    assert_is_sendable(LayoutData::new())
-}
-
 /// A trait that allows access to the layout data of a DOM node.
 pub trait LayoutDataAccess {
-    fn layout_data<'a>(&'a self) -> &'a LayoutData;
+    /// Borrows the layout data without checks.
+    ///
+    /// FIXME(pcwalton): Make safe.
+    unsafe fn borrow_layout_data_unchecked<'a>(&'a self) -> &'a Option<~LayoutData>;
+    /// Borrows the layout data immutably. Fails on a conflicting borrow.
+    fn borrow_layout_data<'a>(&'a self) -> SlotRef<'a,Option<~LayoutData>>;
+    /// Borrows the layout data mutably. Fails on a conflicting borrow.
+    fn mutate_layout_data<'a>(&'a self) -> MutSlotRef<'a,Option<~LayoutData>>;
 }
 
 impl LayoutDataAccess for AbstractNode<LayoutView> {
     #[inline(always)]
-    fn layout_data<'a>(&'a self) -> &'a LayoutData {
-        self.node().layout_data.as_ref().unwrap().as_ref().unwrap()
+    unsafe fn borrow_layout_data_unchecked<'a>(&'a self) -> &'a Option<~LayoutData> {
+        cast::transmute(self.node().layout_data.borrow_unchecked())
+    }
+
+    #[inline(always)]
+    fn borrow_layout_data<'a>(&'a self) -> SlotRef<'a,Option<~LayoutData>> {
+        unsafe {
+            cast::transmute(self.node().layout_data.borrow())
+        }
+    }
+
+    #[inline(always)]
+    fn mutate_layout_data<'a>(&'a self) -> MutSlotRef<'a,Option<~LayoutData>> {
+        unsafe {
+            cast::transmute(self.node().layout_data.mutate())
+        }
     }
 }
 
diff --git a/src/components/main/servo.rc b/src/components/main/servo.rc
index 11e146f6008..dfe78f8c082 100755
--- a/src/components/main/servo.rc
+++ b/src/components/main/servo.rc
@@ -80,7 +80,7 @@ pub mod pipeline;
 pub mod layout {
     pub mod block;
     pub mod box;
-    pub mod box_builder;
+    pub mod construct;
     pub mod context;
     pub mod display_list_builder;
     pub mod float_context;
diff --git a/src/components/script/dom/bindings/utils.rs b/src/components/script/dom/bindings/utils.rs
index f79e8ae633a..b076810785a 100644
--- a/src/components/script/dom/bindings/utils.rs
+++ b/src/components/script/dom/bindings/utils.rs
@@ -863,26 +863,38 @@ pub fn CreateDOMGlobal(cx: *JSContext, class: *JSClass) -> *JSObject {
     }
 }
 
+/// Returns the global object of the realm that the given JS object was created in.
 #[fixed_stack_segment]
-fn cx_for_dom_reflector(obj: *JSObject) -> *JSContext {
+fn global_object_for_js_object(obj: *JSObject) -> *Box<window::Window> {
     unsafe {
         let global = GetGlobalForObjectCrossCompartment(obj);
         let clasp = JS_GetClass(global);
         assert!(((*clasp).flags & (JSCLASS_IS_DOMJSCLASS | JSCLASS_IS_GLOBAL)) != 0);
-        //XXXjdm either don't hardcode or sanity assert prototype stuff
-        let win = unwrap_object::<*Box<window::Window>>(global, PrototypeList::id::Window, 1);
-        match win {
-            Ok(win) => {
-                match (*win).data.page.js_info {
-                    Some(ref info) => info.js_context.ptr,
-                    None => fail!("no JS context for DOM global")
-                }
-            }
-            Err(_) => fail!("found DOM global that doesn't unwrap to Window")
+        // FIXME(jdm): Either don't hardcode or sanity assert prototype stuff.
+        match unwrap_object::<*Box<window::Window>>(global, PrototypeList::id::Window, 1) {
+            Ok(win) => win,
+            Err(_) => fail!("found DOM global that doesn't unwrap to Window"),
         }
     }
 }
 
+#[fixed_stack_segment]
+fn cx_for_dom_reflector(obj: *JSObject) -> *JSContext {
+    unsafe {
+        let win = global_object_for_js_object(obj);
+        match (*win).data.page.js_info {
+            Some(ref info) => info.js_context.ptr,
+            None => fail!("no JS context for DOM global")
+        }
+    }
+}
+
+/// Returns the global object of the realm that the given DOM object was created in.
+#[fixed_stack_segment]
+pub fn global_object_for_dom_object<T: Reflectable>(obj: &mut T) -> *Box<window::Window> {
+    global_object_for_js_object(obj.reflector().get_jsobject())
+}
+
 pub fn cx_for_dom_object<T: Reflectable>(obj: &mut T) -> *JSContext {
     cx_for_dom_reflector(obj.reflector().get_jsobject())
 }
diff --git a/src/components/script/dom/node.rs b/src/components/script/dom/node.rs
index 78533b2b48c..9709680300d 100644
--- a/src/components/script/dom/node.rs
+++ b/src/components/script/dom/node.rs
@@ -7,6 +7,7 @@
 use dom::bindings::utils::{Reflectable, Reflector, reflect_dom_object};
 use dom::bindings::utils::{DOMString, null_str_as_empty};
 use dom::bindings::utils::{ErrorResult, Fallible, NotFound, HierarchyRequest};
+use dom::bindings::utils;
 use dom::characterdata::CharacterData;
 use dom::document::{AbstractDocument, DocumentTypeId};
 use dom::documenttype::DocumentType;
@@ -18,11 +19,13 @@ use dom::htmlimageelement::HTMLImageElement;
 use dom::htmliframeelement::HTMLIFrameElement;
 use dom::text::Text;
 
-use std::cast;
-use std::cast::transmute;
-use std::unstable::raw::Box;
 use js::jsapi::{JSObject, JSContext};
+use servo_util::slot::{MutSlotRef, Slot, SlotRef};
 use servo_util::tree::{TreeNode, TreeNodeRef, TreeNodeRefAsElement};
+use std::cast::transmute;
+use std::cast;
+use std::unstable::raw::Box;
+use std::util;
 
 //
 // The basic Node structure
@@ -89,9 +92,87 @@ pub struct Node<View> {
     child_list: Option<@mut NodeList>,
 
     /// Layout information. Only the layout task may touch this data.
-    layout_data: Option<~Any>,
+    ///
+    /// FIXME(pcwalton): We need to send these back to the layout task to be destroyed when this
+    /// node is finalized.
+    layout_data: LayoutDataRef,
+}
+
+#[unsafe_destructor]
+impl<T> Drop for Node<T> {
+    fn drop(&mut self) {
+        unsafe {
+            let this: &mut Node<ScriptView> = cast::transmute(self);
+            this.reap_layout_data()
+        }
+    }
+}
+
+/// Encapsulates the abstract layout data.
+pub struct LayoutDataRef {
+    priv data: Slot<Option<*()>>,
+}
+
+impl LayoutDataRef {
+    #[inline]
+    pub fn init() -> LayoutDataRef {
+        LayoutDataRef {
+            data: Slot::init(None),
+        }
+    }
+
+    /// Creates a new piece of layout data from a value.
+    #[inline]
+    pub unsafe fn from_data<T>(data: ~T) -> LayoutDataRef {
+        LayoutDataRef {
+            data: Slot::init(Some(cast::transmute(data))),
+        }
+    }
+
+    /// Returns true if this layout data is present or false otherwise.
+    #[inline]
+    pub fn is_present(&self) -> bool {
+        self.data.get().is_some()
+    }
+
+    /// Borrows the layout data immutably, *asserting that there are no mutators*. Bad things will
+    /// happen if you try to mutate the layout data while this is held. This is the only thread-
+    /// safe layout data accessor.
+    ///
+    /// FIXME(pcwalton): Enforce this invariant via the type system. Will require traversal
+    /// functions to be trusted, but c'est la vie.
+    #[inline]
+    pub unsafe fn borrow_unchecked<'a>(&'a self) -> &'a () {
+        cast::transmute(self.data.borrow_unchecked())
+    }
+
+    /// Borrows the layout data immutably. This function is *not* thread-safe.
+    #[inline]
+    pub fn borrow<'a>(&'a self) -> SlotRef<'a,()> {
+        unsafe {
+            cast::transmute(self.data.borrow())
+        }
+    }
+
+    /// Borrows the layout data mutably. This function is *not* thread-safe.
+    ///
+    /// FIXME(pcwalton): We should really put this behind a `MutLayoutView` phantom type, to
+    /// prevent CSS selector matching from mutably accessing nodes it's not supposed to and racing
+    /// on it. This has already resulted in one bug!
+    #[inline]
+    pub fn mutate<'a>(&'a self) -> MutSlotRef<'a,()> {
+        unsafe {
+            cast::transmute(self.data.mutate())
+        }
+    }
 }
 
+/// A trait that represents abstract layout data.
+/// 
+/// FIXME(pcwalton): Very very unsafe!!! We need to send these back to the layout task to be
+/// destroyed when this node is finalized.
+pub trait TLayoutData {}
+
 /// The different types of nodes.
 #[deriving(Eq)]
 pub enum NodeTypeId {
@@ -319,12 +400,24 @@ impl<'self, View> AbstractNode<View> {
         self.transmute_mut(f)
     }
 
+    #[inline]
     pub fn is_comment(self) -> bool {
-        self.type_id() == CommentNodeTypeId
+        // FIXME(pcwalton): Temporary workaround for the lack of inlining of autogenerated `Eq`
+        // implementations in Rust.
+        match self.type_id() {
+            CommentNodeTypeId => true,
+            _ => false,
+        }
     }
 
+    #[inline]
     pub fn is_text(self) -> bool {
-        self.type_id() == TextNodeTypeId
+        // FIXME(pcwalton): Temporary workaround for the lack of inlining of autogenerated `Eq`
+        // implementations in Rust.
+        match self.type_id() {
+            TextNodeTypeId => true,
+            _ => false,
+        }
     }
 
     pub fn with_imm_text<R>(self, f: &fn(&Text) -> R) -> R {
@@ -364,8 +457,12 @@ impl<'self, View> AbstractNode<View> {
         self.transmute_mut(f)
     }
 
+    #[inline]
     pub fn is_image_element(self) -> bool {
-        self.type_id() == ElementNodeTypeId(HTMLImageElementTypeId)
+        match self.type_id() {
+            ElementNodeTypeId(HTMLImageElementTypeId) => true,
+            _ => false,
+        }
     }
 
     pub fn with_imm_image_element<R>(self, f: &fn(&HTMLImageElement) -> R) -> R {
@@ -543,7 +640,16 @@ impl Node<ScriptView> {
             owner_doc: doc,
             child_list: None,
 
-            layout_data: None,
+            layout_data: LayoutDataRef::init(),
+        }
+    }
+
+    /// Sends layout data, if any, back to the script task to be destroyed.
+    pub unsafe fn reap_layout_data(&mut self) {
+        if self.layout_data.is_present() {
+            let layout_data = util::replace(&mut self.layout_data, LayoutDataRef::init());
+            let js_window = utils::global_object_for_dom_object(self);
+            (*js_window).data.page.reap_dead_layout_data(layout_data)
         }
     }
 }
@@ -1095,12 +1201,12 @@ impl Reflectable for Node<ScriptView> {
 /// A bottom-up, parallelizable traversal.
 pub trait PostorderNodeTraversal {
     /// The operation to perform. Return true to continue or false to stop.
-    fn process(&mut self, node: AbstractNode<LayoutView>) -> bool;
+    fn process(&self, node: AbstractNode<LayoutView>) -> bool;
 
     /// Returns true if this node should be pruned. If this returns true, we skip the operation
     /// entirely and do not process any descendant nodes. This is called *before* child nodes are
     /// visited. The default implementation never prunes any nodes.
-    fn should_prune(&mut self, _node: AbstractNode<LayoutView>) -> bool {
+    fn should_prune(&self, _node: AbstractNode<LayoutView>) -> bool {
         false
     }
 }
@@ -1109,7 +1215,7 @@ impl AbstractNode<LayoutView> {
     /// Traverses the tree in postorder.
     ///
     /// TODO(pcwalton): Offer a parallel version with a compatible API.
-    pub fn traverse_postorder<T:PostorderNodeTraversal>(self, traversal: &mut T) -> bool {
+    pub fn traverse_postorder<T:PostorderNodeTraversal>(self, traversal: &T) -> bool {
         if traversal.should_prune(self) {
             return true
         }
diff --git a/src/components/script/layout_interface.rs b/src/components/script/layout_interface.rs
index 348594ca162..3d9cc5e96e2 100644
--- a/src/components/script/layout_interface.rs
+++ b/src/components/script/layout_interface.rs
@@ -6,15 +6,16 @@
 /// coupling between these two components, and enables the DOM to be placed in a separate crate
 /// from layout.
 
-use dom::node::{AbstractNode, ScriptView, LayoutView};
-use script_task::{ScriptChan};
-use std::comm::{Chan, SharedChan};
+use dom::node::{AbstractNode, LayoutDataRef, LayoutView, ScriptView};
+
+use extra::url::Url;
+use geom::point::Point2D;
 use geom::rect::Rect;
 use geom::size::Size2D;
-use geom::point::Point2D;
+use script_task::{ScriptChan};
 use servo_util::geometry::Au;
+use std::comm::{Chan, SharedChan};
 use style::Stylesheet;
-use extra::url::Url;
 
 /// Asynchronous messages that script can send to layout.
 ///
@@ -31,8 +32,19 @@ pub enum Msg {
     /// FIXME(pcwalton): As noted below, this isn't very type safe.
     QueryMsg(LayoutQuery),
 
-    /// Requests that the layout task shut down and exit.
-    ExitMsg,
+    /// Destroys layout data associated with a DOM node.
+    ///
+    /// TODO(pcwalton): Maybe think about batching to avoid message traffic.
+    ReapLayoutDataMsg(LayoutDataRef),
+
+    /// Requests that the layout task enter a quiescent state in which no more messages are
+    /// accepted except `ExitMsg`. A response message will be sent on the supplied channel when
+    /// this happens.
+    PrepareToExitMsg(Chan<()>),
+
+    /// Requests that the layout task immediately shut down. There must be no more nodes left after
+    /// this, or layout will crash.
+    ExitNowMsg,
 }
 
 /// Synchronous messages that script can send to layout.
diff --git a/src/components/script/script_task.rs b/src/components/script/script_task.rs
index 515dd1b0338..438f5429f06 100644
--- a/src/components/script/script_task.rs
+++ b/src/components/script/script_task.rs
@@ -2,11 +2,9 @@
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
-/// The script task is the task that owns the DOM in memory, runs JavaScript, and spawns parsing
-/// and layout tasks.
+//! The script task is the task that owns the DOM in memory, runs JavaScript, and spawns parsing
+//! and layout tasks.
 
-use servo_msg::compositor_msg::{ScriptListener, Loading, PerformingLayout};
-use servo_msg::compositor_msg::FinishedLoading;
 use dom::bindings::codegen::RegisterBindings;
 use dom::bindings::utils::{Reflectable, GlobalStaticData};
 use dom::document::AbstractDocument;
@@ -15,29 +13,20 @@ use dom::event::{Event_, ResizeEvent, ReflowEvent, ClickEvent, MouseDownEvent, M
 use dom::event::Event;
 use dom::eventtarget::AbstractEventTarget;
 use dom::htmldocument::HTMLDocument;
-use dom::window::Window;
+use dom::node::{AbstractNode, LayoutDataRef};
+use dom::window::{TimerData, Window};
+use html::hubbub_html_parser::HtmlParserResult;
+use html::hubbub_html_parser::{HtmlDiscoveredStyle, HtmlDiscoveredIFrame, HtmlDiscoveredScript};
+use html::hubbub_html_parser;
 use layout_interface::{AddStylesheetMsg, DocumentDamage};
 use layout_interface::{DocumentDamageLevel, HitTestQuery, HitTestResponse, LayoutQuery};
-use layout_interface::{LayoutChan, MatchSelectorsDocumentDamage, QueryMsg, Reflow};
-use layout_interface::{ReflowDocumentDamage, ReflowForDisplay, ReflowGoal};
-use layout_interface::ReflowMsg;
+use layout_interface::{LayoutChan, MatchSelectorsDocumentDamage, QueryMsg, ReapLayoutDataMsg};
+use layout_interface::{Reflow, ReflowDocumentDamage, ReflowForDisplay, ReflowGoal, ReflowMsg};
 use layout_interface;
-use servo_msg::constellation_msg::{ConstellationChan, LoadUrlMsg, NavigationDirection};
-use servo_msg::constellation_msg::{PipelineId, SubpageId};
-use servo_msg::constellation_msg::{LoadIframeUrlMsg, IFrameSandboxed, IFrameUnsandboxed};
-use servo_msg::constellation_msg;
 
-use std::cell::Cell;
-use std::comm;
-use std::comm::{Port, SharedChan};
-use std::ptr;
-use std::task::{spawn_sched, SingleThreaded};
-use std::util::replace;
-use dom::window::TimerData;
+use extra::future::Future;
+use extra::url::Url;
 use geom::size::Size2D;
-use html::hubbub_html_parser::HtmlParserResult;
-use html::hubbub_html_parser::{HtmlDiscoveredStyle, HtmlDiscoveredIFrame, HtmlDiscoveredScript};
-use html::hubbub_html_parser;
 use js::JSVAL_NULL;
 use js::global::debug_fns;
 use js::glue::RUST_JSVAL_TO_OBJECT;
@@ -45,12 +34,21 @@ use js::jsapi::{JSContext, JSObject};
 use js::jsapi::{JS_CallFunctionValue, JS_GetContextPrivate};
 use js::rust::{Compartment, Cx};
 use js;
+use servo_msg::compositor_msg::{FinishedLoading, Loading, PerformingLayout, ScriptListener};
+use servo_msg::constellation_msg::{ConstellationChan, IFrameSandboxed, IFrameUnsandboxed};
+use servo_msg::constellation_msg::{LoadIframeUrlMsg, LoadUrlMsg, NavigationDirection, PipelineId};
+use servo_msg::constellation_msg::{SubpageId};
+use servo_msg::constellation_msg;
 use servo_net::image_cache_task::ImageCacheTask;
 use servo_net::resource_task::ResourceTask;
-use servo_util::tree::{TreeNodeRef, ElementLike};
+use servo_util::tree::{TreeNode, TreeNodeRef, ElementLike};
 use servo_util::url::make_url;
-use extra::url::Url;
-use extra::future::Future;
+use std::cell::Cell;
+use std::comm::{Port, SharedChan};
+use std::comm;
+use std::ptr;
+use std::task::{spawn_sched, SingleThreaded};
+use std::util::replace;
 
 /// Messages used to control the script task.
 pub enum ScriptMsg {
@@ -86,6 +84,7 @@ pub struct NewLayoutInfo {
 /// Encapsulates external communication with the script task.
 #[deriving(Clone)]
 pub struct ScriptChan(SharedChan<ScriptMsg>);
+
 impl ScriptChan {
     /// Creates a new script chan.
     pub fn new(chan: Chan<ScriptMsg>) -> ScriptChan {
@@ -93,7 +92,7 @@ impl ScriptChan {
     }
 }
 
-/// Encapsulates a handle to a frame and its associate layout information
+/// Encapsulates a handle to a frame and its associated layout information.
 pub struct Page {
     /// Pipeline id associated with this page.
     id: PipelineId,
@@ -216,8 +215,7 @@ impl<'self> Iterator<@mut Page> for PageTreeIterator<'self> {
 impl Page {
     /// Adds the given damage.
     fn damage(&mut self, level: DocumentDamageLevel) {
-        let root = self.frame.get_ref().document.document().
-            GetDocumentElement();
+        let root = self.frame.get_ref().document.document().GetDocumentElement();
         match root {
             None => {},
             Some(root) => {
@@ -359,13 +357,18 @@ impl Page {
         });
     }
 
+    /// Sends the given layout data back to the layout task to be destroyed.
+    pub unsafe fn reap_dead_layout_data(&self, layout_data: LayoutDataRef) {
+        self.layout_chan.send(ReapLayoutDataMsg(layout_data))
+    }
 }
 
 /// Information for one frame in the browsing context.
 pub struct Frame {
+    /// The document for this frame.
     document: AbstractDocument,
+    /// The window object for this frame.
     window: @mut Window,
-
 }
 
 /// Encapsulation of the javascript information associated with each frame.
@@ -452,15 +455,16 @@ impl ScriptTask {
         }
     }
 
-    pub fn create<C: ScriptListener + Send>(id: PipelineId,
-                                            compositor: C,
-                                            layout_chan: LayoutChan,
-                                            port: Port<ScriptMsg>,
-                                            chan: ScriptChan,
-                                            constellation_chan: ConstellationChan,
-                                            resource_task: ResourceTask,
-                                            image_cache_task: ImageCacheTask,
-                                            initial_size: Future<Size2D<uint>>) {
+    pub fn create<C:ScriptListener + Send>(
+                  id: PipelineId,
+                  compositor: C,
+                  layout_chan: LayoutChan,
+                  port: Port<ScriptMsg>,
+                  chan: ScriptChan,
+                  constellation_chan: ConstellationChan,
+                  resource_task: ResourceTask,
+                  image_cache_task: ImageCacheTask,
+                  initial_size: Future<Size2D<uint>>) {
         let parms = Cell::new((compositor, layout_chan, port, chan, constellation_chan,
                                resource_task, image_cache_task, initial_size));
         // Since SpiderMonkey is blocking it needs to run in its own thread.
@@ -627,23 +631,23 @@ impl ScriptTask {
         true
     }
 
+
     /// Handles a request to exit the script task and shut down layout.
     /// Returns true if the script task should shut down and false otherwise.
     fn handle_exit_pipeline_msg(&mut self, id: PipelineId) -> bool {
         // If root is being exited, shut down all pages
         if self.page_tree.page.id == id {
             for page in self.page_tree.iter() {
-                page.join_layout();
-                page.layout_chan.send(layout_interface::ExitMsg);
+                shut_down_layout(page)
             }
             return true
         }
+
         // otherwise find just the matching page and exit all sub-pages
         match self.page_tree.remove(id) {
             Some(ref mut page_tree) => {
                 for page in page_tree.iter() {
-                    page.join_layout();
-                    page.layout_chan.send(layout_interface::ExitMsg);
+                    shut_down_layout(page)
                 }
                 false
             }
@@ -862,3 +866,34 @@ impl ScriptTask {
     }
 }
 
+/// Shuts down layout for the given page.
+fn shut_down_layout(page: @mut Page) {
+    page.join_layout();
+
+    // Tell the layout task to begin shutting down.
+    let (response_port, response_chan) = comm::stream();
+    page.layout_chan.send(layout_interface::PrepareToExitMsg(response_chan));
+    response_port.recv();
+
+    // Destroy all nodes.
+    //
+    // If there was a leak, the layout task will soon crash safely when it detects that local data
+    // is missing from its heap.
+    //
+    // FIXME(pcwalton): *But*, for now, because we use `@mut` boxes to hold onto Nodes, if this
+    // didn't destroy all the nodes there will be an *exploitable* security vulnerability as the
+    // nodes try to access the destroyed JS context. We need to change this so that the only actor
+    // who can judge a JS object dead (and thus run its drop glue) is the JS engine itself; thus it
+    // will be impossible (absent a serious flaw in the JS engine) for the JS context to be dead
+    // before nodes are.
+    unsafe {
+        let document_node = AbstractNode::from_document(page.frame.as_ref().unwrap().document);
+        for node in document_node.traverse_preorder() {
+            node.mut_node().reap_layout_data()
+        }
+    }
+
+    // Destroy the layout task. If there were node leaks, layout will now crash safely.
+    page.layout_chan.send(layout_interface::ExitNowMsg);
+}
+
diff --git a/src/components/util/slot.rs b/src/components/util/slot.rs
index 6c8eca9068f..34c12f2a0f5 100644
--- a/src/components/util/slot.rs
+++ b/src/components/util/slot.rs
@@ -6,6 +6,7 @@
 //! well, this type should be upstreamed to the Rust standard library.
 
 use std::cast;
+use std::util;
 
 #[unsafe_no_drop_flag]
 #[no_freeze]
@@ -74,6 +75,13 @@ impl<T> Slot<T> {
         }
     }
 
+    /// Borrows the data immutably. This function is thread-safe, but *bad things will happen if
+    /// you try to mutate the data while one of these pointers is held*.
+    #[inline]
+    pub unsafe fn borrow_unchecked<'a>(&'a self) -> &'a T {
+        &self.value
+    }
+
     #[inline]
     pub fn borrow<'a>(&'a self) -> SlotRef<'a,T> {
         unsafe {
@@ -109,8 +117,14 @@ impl<T> Slot<T> {
         *self.mutate().ptr = value
     }
 
+    /// Replaces the slot's value with the given value and returns the old value.
+    #[inline]
+    pub fn replace(&self, value: T) -> T {
+        util::replace(self.mutate().ptr, value)
+    }
+
     #[inline(never)]
-    pub fn fail(&self) {
+    pub fn fail(&self) -> ! {
         fail!("slot is borrowed")
     }
 }