layout: Make incremental reflow more fine-grained by introducing "reflow

out-of-flow" and "reconstruct flow" damage bits.

This is needed for good performance on the maze solver.

20 files changed, 628 insertions, 387 deletions

diff --git a/components/layout/block.rs b/components/layout/block.rs
index 295cb7883fd..b0ba90c2742 100644
--- a/components/layout/block.rs
+++ b/components/layout/block.rs
@@ -36,6 +36,7 @@ use flow::{BaseFlow, BlockFlowClass, FlowClass, Flow, ImmutableFlowUtils};
 use flow::{MutableFlowUtils, PreorderFlowTraversal, PostorderFlowTraversal, mut_base};
 use flow;
 use fragment::{Fragment, ImageFragment, InlineBlockFragment, ScannedTextFragment};
+use incremental::{Reflow, ReflowOutOfFlow};
 use layout_debug;
 use model::{Auto, IntrinsicISizes, MarginCollapseInfo, MarginsCollapse, MarginsCollapseThrough};
 use model::{MaybeAuto, NoCollapsibleMargins, Specified, specified, specified_or_none};
@@ -51,9 +52,11 @@ use servo_util::logical_geometry::{LogicalPoint, LogicalRect, LogicalSize};
 use servo_util::opts;
 use std::cmp::{max, min};
 use std::fmt;
+use style::ComputedValues;
 use style::computed_values::{LPA_Auto, LPA_Length, LPA_Percentage, LPN_Length, LPN_None};
 use style::computed_values::{LPN_Percentage, LP_Length, LP_Percentage, box_sizing, display, float};
 use style::computed_values::{overflow, position};
+use sync::Arc;
 
 /// Information specific to floated blocks.
 #[deriving(Clone, Encodable)]
@@ -436,6 +439,11 @@ impl<'a> PreorderFlowTraversal for AbsoluteAssignBSizesTraversal<'a> {
             return;
         }
 
+        assert!(block_flow.base.flags.is_absolutely_positioned());
+        if !block_flow.base.restyle_damage.intersects(ReflowOutOfFlow | Reflow) {
+            return
+        }
+
         let AbsoluteAssignBSizesTraversal(ref ctx) = *self;
         block_flow.calculate_absolute_block_size_and_margins(*ctx);
     }
@@ -818,214 +826,224 @@ impl BlockFlow {
                                             margins_may_collapse: MarginsMayCollapseFlag) {
         let _scope = layout_debug_scope!("assign_block_size_block_base {:x}", self.base.debug_id());
 
-        // Our current border-box position.
-        let mut cur_b = Au(0);
+        if self.base.restyle_damage.contains(Reflow) {
+            // Our current border-box position.
+            let mut cur_b = Au(0);
 
-        // Absolute positioning establishes a block formatting context. Don't propagate floats
-        // in or out. (But do propagate them between kids.)
-        if self.base.flags.is_absolutely_positioned() ||
-                margins_may_collapse != MarginsMayCollapse {
-            self.base.floats = Floats::new(self.fragment.style.writing_mode);
-        }
+            // Absolute positioning establishes a block formatting context. Don't propagate floats
+            // in or out. (But do propagate them between kids.)
+            if self.base.flags.is_absolutely_positioned() ||
+                    margins_may_collapse != MarginsMayCollapse {
+                self.base.floats = Floats::new(self.fragment.style.writing_mode);
+            }
 
-        let mut margin_collapse_info = MarginCollapseInfo::new();
-        self.base.floats.translate(LogicalSize::new(
-            self.fragment.style.writing_mode, -self.fragment.inline_start_offset(), Au(0)));
-
-        // The sum of our block-start border and block-start padding.
-        let block_start_offset = self.fragment.border_padding.block_start;
-        translate_including_floats(&mut cur_b, block_start_offset, &mut self.base.floats);
-
-        let can_collapse_block_start_margin_with_kids =
-            margins_may_collapse == MarginsMayCollapse &&
-            !self.base.flags.is_absolutely_positioned() &&
-            self.fragment.border_padding.block_start == Au(0);
-        margin_collapse_info.initialize_block_start_margin(
-            &self.fragment,
-            can_collapse_block_start_margin_with_kids);
-
-        // At this point, `cur_b` is at the content edge of our box. Now iterate over children.
-        let mut floats = self.base.floats.clone();
-        let mut layers_needed_for_descendants = false;
-        for kid in self.base.child_iter() {
-            if flow::base(kid).flags.is_absolutely_positioned() {
-                // Assume that the *hypothetical box* for an absolute flow starts immediately
-                // after the block-end border edge of the previous flow.
-                kid.as_block().hypothetical_position.b = cur_b;
-                kid.assign_block_size_for_inorder_child_if_necessary(layout_context);
-                propagate_layer_flag_from_child(&mut layers_needed_for_descendants, kid);
+            let mut margin_collapse_info = MarginCollapseInfo::new();
+            self.base.floats.translate(LogicalSize::new(
+                self.fragment.style.writing_mode, -self.fragment.inline_start_offset(), Au(0)));
 
-                // Skip the collapsing and float processing for absolute flow kids and continue
-                // with the next flow.
-                continue
-            }
+            // The sum of our block-start border and block-start padding.
+            let block_start_offset = self.fragment.border_padding.block_start;
+            translate_including_floats(&mut cur_b, block_start_offset, &mut self.base.floats);
 
-            // Assign block-size now for the child if it was impacted by floats and we couldn't
-            // before.
-            flow::mut_base(kid).floats = floats.clone();
-            if kid.is_float() {
-                flow::mut_base(kid).position.start.b = cur_b;
-                {
-                    let kid_block = kid.as_block();
-                    kid_block.float.as_mut().unwrap().float_ceiling =
-                        margin_collapse_info.current_float_ceiling();
-                }
-                propagate_layer_flag_from_child(&mut layers_needed_for_descendants, kid);
+            let can_collapse_block_start_margin_with_kids =
+                margins_may_collapse == MarginsMayCollapse &&
+                !self.base.flags.is_absolutely_positioned() &&
+                self.fragment.border_padding.block_start == Au(0);
+            margin_collapse_info.initialize_block_start_margin(
+                &self.fragment,
+                can_collapse_block_start_margin_with_kids);
 
-                let need_to_process_child_floats =
+            // At this point, `cur_b` is at the content edge of our box. Now iterate over children.
+            let mut floats = self.base.floats.clone();
+            let mut layers_needed_for_descendants = false;
+            for kid in self.base.child_iter() {
+                if flow::base(kid).flags.is_absolutely_positioned() {
+                    // Assume that the *hypothetical box* for an absolute flow starts immediately
+                    // after the block-end border edge of the previous flow.
+                    kid.as_block().hypothetical_position.b = cur_b;
                     kid.assign_block_size_for_inorder_child_if_necessary(layout_context);
-                assert!(need_to_process_child_floats);  // As it was a float itself...
+                    propagate_layer_flag_from_child(&mut layers_needed_for_descendants, kid);
 
-                let kid_base = flow::mut_base(kid);
-                floats = kid_base.floats.clone();
-                continue
-            }
+                    // Skip the collapsing and float processing for absolute flow kids and continue
+                    // with the next flow.
+                    continue
+                }
 
-            // If we have clearance, assume there are no floats in.
-            //
-            // FIXME(#2008, pcwalton): This could be wrong if we have `clear: left` or `clear:
-            // right` and there are still floats to impact, of course. But this gets complicated
-            // with margin collapse. Possibly the right thing to do is to lay out the block again
-            // in this rare case. (Note that WebKit can lay blocks out twice; this may be related,
-            // although I haven't looked into it closely.)
-            if flow::base(kid).flags.clears_floats() {
-                flow::mut_base(kid).floats = Floats::new(self.fragment.style.writing_mode)
-            }
+                // Assign block-size now for the child if it was impacted by floats and we couldn't
+                // before.
+                flow::mut_base(kid).floats = floats.clone();
+                if kid.is_float() {
+                    flow::mut_base(kid).position.start.b = cur_b;
+                    {
+                        let kid_block = kid.as_block();
+                        kid_block.float.as_mut().unwrap().float_ceiling =
+                            margin_collapse_info.current_float_ceiling();
+                    }
+                    propagate_layer_flag_from_child(&mut layers_needed_for_descendants, kid);
 
-            // Lay the child out if this was an in-order traversal.
-            let need_to_process_child_floats =
-                kid.assign_block_size_for_inorder_child_if_necessary(layout_context);
+                    let need_to_process_child_floats =
+                        kid.assign_block_size_for_inorder_child_if_necessary(layout_context);
+                    assert!(need_to_process_child_floats);  // As it was a float itself...
 
-            // Mark flows for layerization if necessary to handle painting order correctly.
-            propagate_layer_flag_from_child(&mut layers_needed_for_descendants, kid);
+                    let kid_base = flow::mut_base(kid);
+                    floats = kid_base.floats.clone();
+                    continue
+                }
 
-            // Handle any (possibly collapsed) top margin.
-            let delta = margin_collapse_info.advance_block_start_margin(
-                &flow::base(kid).collapsible_margins);
-            translate_including_floats(&mut cur_b, delta, &mut floats);
+                // If we have clearance, assume there are no floats in.
+                //
+                // FIXME(#2008, pcwalton): This could be wrong if we have `clear: left` or `clear:
+                // right` and there are still floats to impact, of course. But this gets
+                // complicated with margin collapse. Possibly the right thing to do is to lay out
+                // the block again in this rare case. (Note that WebKit can lay blocks out twice;
+                // this may be related, although I haven't looked into it closely.)
+                if flow::base(kid).flags.clears_floats() {
+                    flow::mut_base(kid).floats = Floats::new(self.fragment.style.writing_mode)
+                }
 
-            // Clear past the floats that came in, if necessary.
-            let clearance = match (flow::base(kid).flags.clears_left(),
-                                   flow::base(kid).flags.clears_right()) {
-                (false, false) => Au(0),
-                (true, false) => floats.clearance(ClearLeft),
-                (false, true) => floats.clearance(ClearRight),
-                (true, true) => floats.clearance(ClearBoth),
-            };
-            translate_including_floats(&mut cur_b, clearance, &mut floats);
+                // Lay the child out if this was an in-order traversal.
+                let need_to_process_child_floats =
+                    kid.assign_block_size_for_inorder_child_if_necessary(layout_context);
 
-            // At this point, `cur_b` is at the border edge of the child.
-            flow::mut_base(kid).position.start.b = cur_b;
+                // Mark flows for layerization if necessary to handle painting order correctly.
+                propagate_layer_flag_from_child(&mut layers_needed_for_descendants, kid);
 
-            // Now pull out the child's outgoing floats. We didn't do this immediately after the
-            // `assign_block_size_for_inorder_child_if_necessary` call because clearance on a block
-            // operates on the floats that come *in*, not the floats that go *out*.
-            if need_to_process_child_floats {
-                floats = flow::mut_base(kid).floats.clone()
-            }
+                // Handle any (possibly collapsed) top margin.
+                let delta = margin_collapse_info.advance_block_start_margin(
+                    &flow::base(kid).collapsible_margins);
+                translate_including_floats(&mut cur_b, delta, &mut floats);
+
+                // Clear past the floats that came in, if necessary.
+                let clearance = match (flow::base(kid).flags.clears_left(),
+                                       flow::base(kid).flags.clears_right()) {
+                    (false, false) => Au(0),
+                    (true, false) => floats.clearance(ClearLeft),
+                    (false, true) => floats.clearance(ClearRight),
+                    (true, true) => floats.clearance(ClearBoth),
+                };
+                translate_including_floats(&mut cur_b, clearance, &mut floats);
 
-            // Move past the child's border box. Do not use the `translate_including_floats`
-            // function here because the child has already translated floats past its border box.
-            let kid_base = flow::mut_base(kid);
-            cur_b = cur_b + kid_base.position.size.block;
+                // At this point, `cur_b` is at the border edge of the child.
+                flow::mut_base(kid).position.start.b = cur_b;
 
-            // Handle any (possibly collapsed) block-end margin.
-            let delta =
-                margin_collapse_info.advance_block_end_margin(&kid_base.collapsible_margins);
-            translate_including_floats(&mut cur_b, delta, &mut floats);
-        }
+                // Now pull out the child's outgoing floats. We didn't do this immediately after
+                // the `assign_block_size_for_inorder_child_if_necessary` call because clearance on
+                // a block operates on the floats that come *in*, not the floats that go *out*.
+                if need_to_process_child_floats {
+                    floats = flow::mut_base(kid).floats.clone()
+                }
 
-        // Mark ourselves for layerization if that will be necessary to paint in the proper order
-        // (CSS 2.1, Appendix E).
-        self.base.flags.set_layers_needed_for_descendants(layers_needed_for_descendants);
-
-        // Collect various offsets needed by absolutely positioned descendants.
-        (&mut *self as &mut Flow).collect_static_block_offsets_from_children();
-
-        // Add in our block-end margin and compute our collapsible margins.
-        let can_collapse_block_end_margin_with_kids =
-            margins_may_collapse == MarginsMayCollapse &&
-            !self.base.flags.is_absolutely_positioned() &&
-            self.fragment.border_padding.block_end == Au(0);
-        let (collapsible_margins, delta) =
-            margin_collapse_info.finish_and_compute_collapsible_margins(
-            &self.fragment,
-            can_collapse_block_end_margin_with_kids);
-        self.base.collapsible_margins = collapsible_margins;
-        translate_including_floats(&mut cur_b, delta, &mut floats);
-
-        // FIXME(#2003, pcwalton): The max is taken here so that you can scroll the page, but this
-        // is not correct behavior according to CSS 2.1 § 10.5. Instead I think we should treat the
-        // root element as having `overflow: scroll` and use the layers-based scrolling
-        // infrastructure to make it scrollable.
-        let mut block_size = cur_b - block_start_offset;
-        let is_root = self.is_root();
-        if is_root {
-            let screen_size = LogicalSize::from_physical(
-                self.fragment.style.writing_mode, layout_context.shared.screen_size);
-            block_size = Au::max(screen_size.block, block_size)
-        }
+                // Move past the child's border box. Do not use the `translate_including_floats`
+                // function here because the child has already translated floats past its border
+                // box.
+                let kid_base = flow::mut_base(kid);
+                cur_b = cur_b + kid_base.position.size.block;
+
+                // Handle any (possibly collapsed) block-end margin.
+                let delta =
+                    margin_collapse_info.advance_block_end_margin(&kid_base.collapsible_margins);
+                translate_including_floats(&mut cur_b, delta, &mut floats);
+            }
+
+            // Mark ourselves for layerization if that will be necessary to paint in the proper
+            // order (CSS 2.1, Appendix E).
+            self.base.flags.set_layers_needed_for_descendants(layers_needed_for_descendants);
+
+            // Collect various offsets needed by absolutely positioned descendants.
+            (&mut *self as &mut Flow).collect_static_block_offsets_from_children();
+
+            // Add in our block-end margin and compute our collapsible margins.
+            let can_collapse_block_end_margin_with_kids =
+                margins_may_collapse == MarginsMayCollapse &&
+                !self.base.flags.is_absolutely_positioned() &&
+                self.fragment.border_padding.block_end == Au(0);
+            let (collapsible_margins, delta) =
+                margin_collapse_info.finish_and_compute_collapsible_margins(
+                &self.fragment,
+                can_collapse_block_end_margin_with_kids);
+            self.base.collapsible_margins = collapsible_margins;
+            translate_including_floats(&mut cur_b, delta, &mut floats);
 
-        if is_root || self.formatting_context_type() != NonformattingContext ||
-                self.base.flags.is_absolutely_positioned() {
-            // The content block-size includes all the floats per CSS 2.1 § 10.6.7. The easiest way
-            // to handle this is to just treat this as clearance.
-            block_size = block_size + floats.clearance(ClearBoth);
-        }
+            // FIXME(#2003, pcwalton): The max is taken here so that you can scroll the page, but
+            // this is not correct behavior according to CSS 2.1 § 10.5. Instead I think we should
+            // treat the root element as having `overflow: scroll` and use the layers-based
+            // scrolling infrastructure to make it scrollable.
+            let mut block_size = cur_b - block_start_offset;
+            let is_root = self.is_root();
+            if is_root {
+                let screen_size = LogicalSize::from_physical(self.fragment.style.writing_mode,
+                                                             layout_context.shared.screen_size);
+                block_size = Au::max(screen_size.block, block_size)
+            }
 
-        if self.base.flags.is_absolutely_positioned() {
-            // Fixed position layers get layers.
-            if self.is_fixed() {
-                self.base.flags.set_needs_layer(true)
+            if is_root || self.formatting_context_type() != NonformattingContext ||
+                    self.base.flags.is_absolutely_positioned() {
+                // The content block-size includes all the floats per CSS 2.1 § 10.6.7. The easiest
+                // way to handle this is to just treat it as clearance.
+                block_size = block_size + floats.clearance(ClearBoth);
             }
 
-            // Store the content block-size for use in calculating the absolute flow's dimensions
-            // later.
-            //
-            // FIXME(pcwalton): This looks not idempotent. Is it?
-            self.fragment.border_box.size.block = block_size;
-            return
-        }
+            if self.base.flags.is_absolutely_positioned() {
+                // Fixed position layers get layers.
+                if self.is_fixed() {
+                    self.base.flags.set_needs_layer(true)
+                }
 
-        // Compute any explicitly-specified block size.
-        // Can't use `for` because we assign to `candidate_block_size_iterator.candidate_value`.
-        let mut candidate_block_size_iterator = CandidateBSizeIterator::new(
-            &self.fragment,
-            self.base.block_container_explicit_block_size);
-        loop {
-            match candidate_block_size_iterator.next() {
-                Some(candidate_block_size) => {
-                    candidate_block_size_iterator.candidate_value = match candidate_block_size {
-                        Auto => block_size,
-                        Specified(value) => value
+                // Store the content block-size for use in calculating the absolute flow's
+                // dimensions later.
+                //
+                // FIXME(pcwalton): This looks not idempotent. Is it?
+                self.fragment.border_box.size.block = block_size;
+                return
+            }
+
+            // Compute any explicitly-specified block size.
+            // Can't use `for` because we assign to `candidate_block_size_iterator.candidate_value`.
+            let mut candidate_block_size_iterator = CandidateBSizeIterator::new(
+                &self.fragment,
+                self.base.block_container_explicit_block_size);
+            loop {
+                match candidate_block_size_iterator.next() {
+                    Some(candidate_block_size) => {
+                        candidate_block_size_iterator.candidate_value =
+                            match candidate_block_size {
+                                Auto => block_size,
+                                Specified(value) => value
+                            }
                     }
+                    None => break,
                 }
-                None => break,
             }
-        }
 
-        // Adjust `cur_b` as necessary to account for the explicitly-specified block-size.
-        block_size = candidate_block_size_iterator.candidate_value;
-        let delta = block_size - (cur_b - block_start_offset);
-        translate_including_floats(&mut cur_b, delta, &mut floats);
+            // Adjust `cur_b` as necessary to account for the explicitly-specified block-size.
+            block_size = candidate_block_size_iterator.candidate_value;
+            let delta = block_size - (cur_b - block_start_offset);
+            translate_including_floats(&mut cur_b, delta, &mut floats);
 
-        // Take border and padding into account.
-        let block_end_offset = self.fragment.border_padding.block_end;
-        translate_including_floats(&mut cur_b, block_end_offset, &mut floats);
+            // Take border and padding into account.
+            let block_end_offset = self.fragment.border_padding.block_end;
+            translate_including_floats(&mut cur_b, block_end_offset, &mut floats);
 
-        // Now that `cur_b` is at the block-end of the border box, compute the final border box
-        // position.
-        self.fragment.border_box.size.block = cur_b;
-        self.fragment.border_box.start.b = Au(0);
+            // Now that `cur_b` is at the block-end of the border box, compute the final border box
+            // position.
+            self.fragment.border_box.size.block = cur_b;
+            self.fragment.border_box.start.b = Au(0);
 
-        if !self.base.flags.is_absolutely_positioned() {
-            self.base.position.size.block = cur_b;
-        }
+            if !self.base.flags.is_absolutely_positioned() {
+                self.base.position.size.block = cur_b;
+            }
 
-        // Store the current set of floats in the flow so that flows that come later in the
-        // document can access them.
-        self.base.floats = floats.clone();
-        self.adjust_fragments_for_collapsed_margins_if_root();
+            // Store the current set of floats in the flow so that flows that come later in the
+            // document can access them.
+            self.base.floats = floats.clone();
+            self.adjust_fragments_for_collapsed_margins_if_root();
+        } else {
+            // We don't need to reflow, but we still need to perform in-order traversals if
+            // necessary.
+            for kid in self.base.child_iter() {
+                kid.assign_block_size_for_inorder_child_if_necessary(layout_context);
+            }
+        }
 
         if self.is_root_of_absolute_flow_tree() {
             // Assign block-sizes for all flows in this absolute flow tree.
@@ -1038,6 +1056,15 @@ impl BlockFlow {
                 layout_context: layout_context,
             });
         }
+
+        // Don't remove the dirty bits yet if we're absolutely-positioned, since our final size
+        // has not been calculated yet. (See `calculate_absolute_block_size_and_margins` for that.)
+        // Also don't remove the dirty bits if we're a block formatting context since our inline
+        // size has not yet been computed. (See `assign_inline_position_for_formatting_context()`.)
+        if !self.base.flags.is_absolutely_positioned() &&
+                self.formatting_context_type() == NonformattingContext {
+            self.base.restyle_damage.remove(ReflowOutOfFlow | Reflow);
+        }
     }
 
     /// Add placement information about current float flow for use by the parent.
@@ -1184,6 +1211,8 @@ impl BlockFlow {
         let block_size = solution.block_size + self.fragment.border_padding.block_start_end();
         self.fragment.border_box.size.block = block_size;
         self.base.position.size.block = block_size;
+
+        self.base.restyle_damage.remove(ReflowOutOfFlow | Reflow);
     }
 
     // Our inline-size was set to the inline-size of the containing block by the flow's parent.
@@ -1375,6 +1404,10 @@ impl BlockFlow {
     fn assign_inline_position_for_formatting_context(&mut self) {
         debug_assert!(self.formatting_context_type() != NonformattingContext);
 
+        if !self.base.restyle_damage.intersects(ReflowOutOfFlow | Reflow) {
+            return
+        }
+
         let info = PlacementInfo {
             size: LogicalSize::new(
                 self.fragment.style.writing_mode,
@@ -1504,6 +1537,10 @@ impl Flow for BlockFlow {
     fn assign_inline_sizes(&mut self, layout_context: &LayoutContext) {
         let _scope = layout_debug_scope!("block::assign_inline_sizes {:x}", self.base.debug_id());
 
+        if !self.base.restyle_damage.intersects(ReflowOutOfFlow | Reflow) {
+            return
+        }
+
         debug!("assign_inline_sizes({}): assigning inline_size for flow",
                if self.is_float() {
                    "float"
@@ -1576,12 +1613,16 @@ impl Flow for BlockFlow {
         }
 
         let is_formatting_context = self.formatting_context_type() != NonformattingContext;
-        if is_formatting_context {
+        if !self.base.flags.is_absolutely_positioned() && is_formatting_context {
             self.assign_inline_position_for_formatting_context();
         }
 
         if self.base.flags.impacted_by_floats() {
-            self.assign_block_size(layout_context);
+            if self.base.restyle_damage.intersects(ReflowOutOfFlow | Reflow) {
+                self.assign_block_size(layout_context);
+                // Don't remove the restyle damage; `assign_block_size` decides whether that is
+                // appropriate (which in the case of e.g. absolutely-positioned flows, it is not).
+            }
             return true
         }
 
@@ -1771,6 +1812,10 @@ impl Flow for BlockFlow {
             self.base.validate_display_list_geometry();
         }
     }
+
+    fn repair_style(&mut self, new_style: &Arc<ComputedValues>) {
+        self.fragment.repair_style(new_style)
+    }
 }
 
 impl fmt::Show for BlockFlow {
diff --git a/components/layout/construct.rs b/components/layout/construct.rs
index 4910a9c01b5..71b199af179 100644
--- a/components/layout/construct.rs
+++ b/components/layout/construct.rs
@@ -27,7 +27,7 @@ use fragment::{InlineAbsoluteHypotheticalFragmentInfo, InlineBlockFragment};
 use fragment::{InlineBlockFragmentInfo, InputFragment, SpecificFragmentInfo, TableCellFragment};
 use fragment::{TableColumnFragment, TableColumnFragmentInfo, TableFragment, TableRowFragment};
 use fragment::{TableWrapperFragment, UnscannedTextFragment, UnscannedTextFragmentInfo};
-use incremental::RestyleDamage;
+use incremental::{ReconstructFlow, RestyleDamage};
 use inline::InlineFlow;
 use parallel;
 use table_wrapper::TableWrapperFlow;
@@ -38,7 +38,7 @@ use table_rowgroup::TableRowGroupFlow;
 use table_row::TableRowFlow;
 use table_cell::TableCellFlow;
 use text::TextRunScanner;
-use util::{LayoutDataAccess, OpaqueNodeMethods, LayoutDataWrapper};
+use util::{HasNewlyConstructedFlow, LayoutDataAccess, OpaqueNodeMethods, LayoutDataWrapper};
 use wrapper::{PostorderNodeMutTraversal, TLayoutNode, ThreadSafeLayoutNode};
 use wrapper::{Before, After, Normal};
 
@@ -942,6 +942,44 @@ impl<'a> FlowConstructor<'a> {
 
         FlowConstructionResult(flow, Descendants::new())
     }
+
+    /// Attempts to perform incremental repair to account for recent changes to this node. This
+    /// can fail and return false, indicating that flows will need to be reconstructed.
+    ///
+    /// TODO(pcwalton): Add some more fast paths, like toggling `display: none`, adding block kids
+    /// to block parents with no {ib} splits, adding out-of-flow kids, etc.
+    pub fn repair_if_possible(&mut self, node: &ThreadSafeLayoutNode) -> bool {
+        // We can skip reconstructing the flow if we don't have to reconstruct and none of our kids
+        // did either.
+        if node.restyle_damage().contains(ReconstructFlow) {
+            return false
+        }
+
+        let mut need_to_reconstruct = false;
+        for kid in node.children() {
+            if kid.flags().contains(HasNewlyConstructedFlow) {
+                kid.remove_flags(HasNewlyConstructedFlow);
+                need_to_reconstruct = true
+            }
+        }
+        if need_to_reconstruct {
+            return false
+        }
+
+        match node.swap_out_construction_result() {
+            NoConstructionResult => true,
+            FlowConstructionResult(mut flow, _) => {
+                // The node's flow is of the same type and has the same set of children and can
+                // therefore be repaired by simply propagating damage and style to the flow.
+                flow::mut_base(&mut *flow).restyle_damage.insert(node.restyle_damage());
+                flow.repair_style(node.style());
+                true
+            }
+            ConstructionItemConstructionResult(_) => {
+                false
+            }
+        }
+    }
 }
 
 impl<'a> PostorderNodeMutTraversal for FlowConstructor<'a> {
@@ -1088,6 +1126,7 @@ impl<'a> PostorderNodeMutTraversal for FlowConstructor<'a> {
             }
         }
 
+        node.insert_flags(HasNewlyConstructedFlow);
         true
     }
 }
diff --git a/components/layout/css/matching.rs b/components/layout/css/matching.rs
index 29c4f5208f4..62374477181 100644
--- a/components/layout/css/matching.rs
+++ b/components/layout/css/matching.rs
@@ -5,11 +5,9 @@
 //! High-level interface to CSS selector matching.
 
 use css::node_style::StyledNode;
-use incremental;
-use incremental::RestyleDamage;
+use incremental::{mod, RestyleDamage};
 use util::{LayoutDataAccess, LayoutDataWrapper};
-use wrapper::{LayoutElement, LayoutNode, ThreadSafeLayoutNode};
-use wrapper::{TLayoutNode};
+use wrapper::{LayoutElement, LayoutNode, TLayoutNode};
 
 use script::dom::node::{TextNodeTypeId};
 use servo_util::bloom::BloomFilter;
@@ -339,8 +337,8 @@ pub enum StyleSharingResult<'ln> {
     /// is shareable at all.
     CannotShare(bool),
     /// The node's style can be shared. The integer specifies the index in the LRU cache that was
-    /// hit.
-    StyleWasShared(uint),
+    /// hit and the damage that was done.
+    StyleWasShared(uint, RestyleDamage),
 }
 
 pub trait MatchMethods {
@@ -385,7 +383,8 @@ trait PrivateMatchMethods {
                                    style: &mut Option<Arc<ComputedValues>>,
                                    applicable_declarations_cache: &mut
                                    ApplicableDeclarationsCache,
-                                   shareable: bool) -> RestyleDamage;
+                                   shareable: bool)
+                                   -> RestyleDamage;
 
     fn share_style_with_candidate_if_possible(&self,
                                               parent_node: Option<LayoutNode>,
@@ -400,7 +399,8 @@ impl<'ln> PrivateMatchMethods for LayoutNode<'ln> {
                                    style: &mut Option<Arc<ComputedValues>>,
                                    applicable_declarations_cache: &mut
                                    ApplicableDeclarationsCache,
-                                   shareable: bool) -> RestyleDamage {
+                                   shareable: bool)
+                                   -> RestyleDamage {
         let this_style;
         let cacheable;
         match parent_style {
@@ -432,9 +432,10 @@ impl<'ln> PrivateMatchMethods for LayoutNode<'ln> {
             applicable_declarations_cache.insert(applicable_declarations, this_style.clone());
         }
 
-        let ret = incremental::compute_damage(&*style, this_style.deref());
+        // Calculate style difference and write.
+        let damage = incremental::compute_damage(style, &*this_style);
         *style = Some(this_style);
-        ret
+        damage
     }
 
 
@@ -526,12 +527,11 @@ impl<'ln> MatchMethods for LayoutNode<'ln> {
                 Some(shared_style) => {
                     // Yay, cache hit. Share the style.
                     let mut layout_data_ref = self.mutate_layout_data();
-                    let layout_data = layout_data_ref.as_mut().unwrap();
-                    let style = &mut layout_data.shared_data.style;
-                    layout_data.data.restyle_damage.insert(
-                        incremental::compute_damage(&*style, &*shared_style));
+                    let shared_data = &mut layout_data_ref.as_mut().unwrap().shared_data;
+                    let style = &mut shared_data.style;
+                    let damage = incremental::compute_damage(style, &*shared_style);
                     *style = Some(shared_style);
-                    return StyleWasShared(i)
+                    return StyleWasShared(i, damage)
                 }
                 None => {}
             }
@@ -585,8 +585,6 @@ impl<'ln> MatchMethods for LayoutNode<'ln> {
                            parent: Option<LayoutNode>,
                            applicable_declarations: &ApplicableDeclarations,
                            applicable_declarations_cache: &mut ApplicableDeclarationsCache) {
-        let mut restyle_damage = ThreadSafeLayoutNode::new(self).restyle_damage();
-
         // Get our parent's style. This must be unsafe so that we don't touch the parent's
         // borrow flags.
         //
@@ -602,51 +600,46 @@ impl<'ln> MatchMethods for LayoutNode<'ln> {
             }
         };
 
-
-        {
-            let mut layout_data_ref = self.mutate_layout_data();
-            let layout_data = layout_data_ref.as_mut().expect("no layout_data");
-            match self.type_id() {
-                Some(TextNodeTypeId) => {
-                    // Text nodes get a copy of the parent style. This ensures
-                    // that during fragment construction any non-inherited
-                    // CSS properties (such as vertical-align) are correctly
-                    // set on the fragment(s).
-                    let cloned_parent_style = parent_style.unwrap().clone();
-                    restyle_damage.insert(
-                        incremental::compute_damage(&layout_data.shared_data.style, &*cloned_parent_style));
-                    layout_data.shared_data.style = Some(cloned_parent_style);
-                }
-                _ => {
-                    restyle_damage.insert(
-                        self.cascade_node_pseudo_element(
+        let mut layout_data_ref = self.mutate_layout_data();
+        match &mut *layout_data_ref {
+            &None => fail!("no layout data"),
+            &Some(ref mut layout_data) => {
+                match self.type_id() {
+                    Some(TextNodeTypeId) => {
+                        // Text nodes get a copy of the parent style. This ensures
+                        // that during fragment construction any non-inherited
+                        // CSS properties (such as vertical-align) are correctly
+                        // set on the fragment(s).
+                        let cloned_parent_style = parent_style.unwrap().clone();
+                        layout_data.shared_data.style = Some(cloned_parent_style);
+                    }
+                    _ => {
+                        let mut damage = self.cascade_node_pseudo_element(
                             parent_style,
                             applicable_declarations.normal.as_slice(),
                             &mut layout_data.shared_data.style,
                             applicable_declarations_cache,
-                            applicable_declarations.normal_shareable));
-                    if applicable_declarations.before.len() > 0 {
-                        restyle_damage.insert(
-                            self.cascade_node_pseudo_element(
-                                Some(layout_data.shared_data.style.as_ref().unwrap()),
-                                applicable_declarations.before.as_slice(),
-                                &mut layout_data.data.before_style,
-                                applicable_declarations_cache,
-                                false));
-                    }
-                    if applicable_declarations.after.len() > 0 {
-                        restyle_damage.insert(
-                           self.cascade_node_pseudo_element(
+                            applicable_declarations.normal_shareable);
+                        if applicable_declarations.before.len() > 0 {
+                           damage = damage | self.cascade_node_pseudo_element(
+                               Some(layout_data.shared_data.style.as_ref().unwrap()),
+                               applicable_declarations.before.as_slice(),
+                               &mut layout_data.data.before_style,
+                               applicable_declarations_cache,
+                               false);
+                        }
+                        if applicable_declarations.after.len() > 0 {
+                           damage = damage | self.cascade_node_pseudo_element(
                                Some(layout_data.shared_data.style.as_ref().unwrap()),
                                applicable_declarations.after.as_slice(),
                                &mut layout_data.data.after_style,
                                applicable_declarations_cache,
-                               false));
+                               false);
+                        }
+                        layout_data.data.restyle_damage = damage;
                     }
                 }
             }
         }
-
-        ThreadSafeLayoutNode::new(self).set_restyle_damage(restyle_damage);
     }
 }
diff --git a/components/layout/css/node_style.rs b/components/layout/css/node_style.rs
index 35bb1b1a8fa..ecfb3383453 100644
--- a/components/layout/css/node_style.rs
+++ b/components/layout/css/node_style.rs
@@ -5,7 +5,6 @@
 // Style retrieval from DOM elements.
 
 use css::node_util::NodeUtil;
-use incremental::RestyleDamage;
 use wrapper::ThreadSafeLayoutNode;
 
 use style::ComputedValues;
@@ -15,8 +14,6 @@ use sync::Arc;
 pub trait StyledNode {
     fn style<'a>(&'a self) -> &'a Arc<ComputedValues>;
     fn unstyle(self);
-    fn restyle_damage(self) -> RestyleDamage;
-    fn set_restyle_damage(self, damage: RestyleDamage);
 }
 
 impl<'ln> StyledNode for ThreadSafeLayoutNode<'ln> {
@@ -28,15 +25,4 @@ impl<'ln> StyledNode for ThreadSafeLayoutNode<'ln> {
     fn unstyle(self) {
         self.remove_css_select_results()
     }
-
-    fn restyle_damage(self) -> RestyleDamage {
-        self.get_restyle_damage()
-    }
-
-    fn set_restyle_damage(self, damage: RestyleDamage) {
-        fn doit<N: NodeUtil>(n: N, damage: RestyleDamage) {
-            n.set_restyle_damage(damage);
-        }
-        doit(self, damage);
-    }
 }
diff --git a/components/layout/css/node_util.rs b/components/layout/css/node_util.rs
index 80144d50022..eb447b0cf6b 100644
--- a/components/layout/css/node_util.rs
+++ b/components/layout/css/node_util.rs
@@ -2,7 +2,6 @@
  * 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/. */
 
-use incremental::RestyleDamage;
 use util::LayoutDataAccess;
 use wrapper::ThreadSafeLayoutNode;
 use wrapper::{After, Before, Normal};
@@ -15,9 +14,6 @@ pub trait NodeUtil {
     fn get_css_select_results<'a>(&'a self) -> &'a Arc<ComputedValues>;
     fn have_css_select_results(&self) -> bool;
     fn remove_css_select_results(self);
-
-    fn get_restyle_damage(self) -> RestyleDamage;
-    fn set_restyle_damage(self, damage: RestyleDamage);
 }
 
 impl<'ln> NodeUtil for ThreadSafeLayoutNode<'ln> {
@@ -75,23 +71,5 @@ impl<'ln> NodeUtil for ThreadSafeLayoutNode<'ln> {
 
         *style = None;
     }
-
-    /// Get the description of how to account for recent style changes.
-    /// This is a simple bitfield and fine to copy by value.
-    fn get_restyle_damage(self) -> RestyleDamage {
-        let layout_data_ref = self.borrow_layout_data();
-        layout_data_ref
-            .as_ref().unwrap()
-            .data
-            .restyle_damage
-    }
-
-    /// Set the restyle damage field.
-    fn set_restyle_damage(self, damage: RestyleDamage) {
-        let mut layout_data_ref = self.mutate_layout_data();
-        match &mut *layout_data_ref {
-            &Some(ref mut layout_data) => layout_data.data.restyle_damage = damage,
-            _ => fail!("no layout data for this node"),
-        }
-    }
 }
+
diff --git a/components/layout/flow.rs b/components/layout/flow.rs
index 92ac60e190b..2479dc14c9d 100644
--- a/components/layout/flow.rs
+++ b/components/layout/flow.rs
@@ -32,7 +32,7 @@ use floats::Floats;
 use flow_list::{FlowList, FlowListIterator, MutFlowListIterator};
 use flow_ref::FlowRef;
 use fragment::{Fragment, TableRowFragment, TableCellFragment};
-use incremental::RestyleDamage;
+use incremental::{ReconstructFlow, Reflow, ReflowOutOfFlow, RestyleDamage};
 use inline::InlineFlow;
 use model::{CollapsibleMargins, IntrinsicISizes, MarginCollapseInfo};
 use parallel::FlowParallelInfo;
@@ -62,6 +62,8 @@ use std::raw;
 use std::sync::atomics::{AtomicUint, SeqCst};
 use std::slice::MutItems;
 use style::computed_values::{clear, float, position, text_align};
+use style::ComputedValues;
+use sync::Arc;
 
 /// Virtual methods that make up a float context.
 ///
@@ -199,6 +201,7 @@ pub trait Flow: fmt::Show + ToString + Sync {
         let impacted = base(&*self).flags.impacted_by_floats();
         if impacted {
             self.assign_block_size(layout_context);
+            mut_base(&mut *self).restyle_damage.remove(ReflowOutOfFlow | Reflow);
         }
         impacted
     }
@@ -289,6 +292,10 @@ pub trait Flow: fmt::Show + ToString + Sync {
             LayerId(pointer, fragment_id)
         }
     }
+
+    /// Attempts to perform incremental fixup of this flow by replacing its fragment's style with
+    /// the new style. This can only succeed if the flow has exactly one fragment.
+    fn repair_style(&mut self, new_style: &Arc<ComputedValues>);
 }
 
 impl<'a, E, S: Encoder<E>> Encodable<S, E> for &'a Flow + 'a {
@@ -420,8 +427,6 @@ pub trait MutableFlowUtils {
     /// So, kids have their flow origin already set. In the case of absolute flow kids, they have
     /// their hypothetical box position already set.
     fn collect_static_block_offsets_from_children(self);
-
-    fn propagate_restyle_damage(self);
 }
 
 pub trait MutableOwnedFlowUtils {
@@ -874,9 +879,13 @@ impl BaseFlow {
             }
         }
 
+        // New flows start out as fully damaged.
+        let mut damage = RestyleDamage::all();
+        damage.remove(ReconstructFlow);
+
         BaseFlow {
             ref_count: AtomicUint::new(1),
-            restyle_damage: RestyleDamage::all(),
+            restyle_damage: damage,
             children: FlowList::new(),
             intrinsic_inline_sizes: IntrinsicISizes::new(),
             position: LogicalRect::zero(writing_mode),
@@ -1209,47 +1218,6 @@ impl<'a> MutableFlowUtils for &'a mut Flow + 'a {
         }
         mut_base(self).abs_descendants.static_block_offsets = absolute_descendant_block_offsets
     }
-
-    fn propagate_restyle_damage(self) {
-        struct DirtyFloats {
-            left:  bool,
-            right: bool,
-        }
-
-        fn doit(flow: &mut Flow, down: RestyleDamage, dirty_floats: &mut DirtyFloats) -> RestyleDamage {
-            if base(flow).flags.clears_left() {
-                dirty_floats.left  = false;
-            }
-            if base(flow).flags.clears_right() {
-                dirty_floats.right = false;
-            }
-
-            if base(flow).flags.floats_left() {
-                (*dirty_floats).left  = true;
-            } else if base(flow).flags.floats_right() {
-                (*dirty_floats).right = true;
-            }
-
-            let mut my_damage = mut_base(flow).restyle_damage;
-            my_damage.insert(down);
-
-            if (*dirty_floats).left || (*dirty_floats).right {
-                my_damage = RestyleDamage::all();
-            }
-
-            let down_damage = my_damage.propagate_down();
-
-            for kid in child_iter(flow) {
-                my_damage.insert(doit(kid, down_damage, dirty_floats));
-            }
-
-            mut_base(flow).restyle_damage = my_damage;
-
-            my_damage.propagate_up()
-        }
-
-        doit(self, RestyleDamage::empty(), &mut DirtyFloats { left: false, right: false });
-    }
 }
 
 impl MutableOwnedFlowUtils for FlowRef {
diff --git a/components/layout/fragment.rs b/components/layout/fragment.rs
index 965f2a990c0..2844495bb23 100644
--- a/components/layout/fragment.rs
+++ b/components/layout/fragment.rs
@@ -1479,6 +1479,9 @@ impl Fragment {
         }
     }
 
+    pub fn repair_style(&mut self, new_style: &Arc<ComputedValues>) {
+        self.style = (*new_style).clone()
+    }
 }
 
 impl fmt::Show for Fragment {
diff --git a/components/layout/incremental.rs b/components/layout/incremental.rs
index 6f23756442f..6d340991b6c 100644
--- a/components/layout/incremental.rs
+++ b/components/layout/incremental.rs
@@ -2,8 +2,11 @@
  * 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/. */
 
+use flow::{mod, Flow};
+
 use std::fmt;
 use std::sync::Arc;
+use style::computed_values::float;
 use style::ComputedValues;
 
 bitflags! {
@@ -18,22 +21,67 @@ bitflags! {
         #[doc = "bottom-up."]
         static BubbleISizes = 0x02,
 
+        #[doc = "Recompute actual inline-sizes and block-sizes, only taking out-of-flow children \
+                 into account. \
+                 Propagates up the flow tree because the computation is top-down."]
+        static ReflowOutOfFlow = 0x04,
+
         #[doc = "Recompute actual inline_sizes and block_sizes."]
         #[doc = "Propagates up the flow tree because the computation is"]
         #[doc = "top-down."]
-        static Reflow = 0x04
+        static Reflow = 0x08,
+
+        #[doc = "The entire flow needs to be reconstructed."]
+        static ReconstructFlow = 0x10
+    }
+}
+
+bitflags! {
+    flags SpecialRestyleDamage: u8 {
+        #[doc="If this flag is set, we need to reflow the entire document. This is more or less a \
+               temporary hack to deal with cases that we don't handle incrementally yet."]
+        static ReflowEntireDocument = 0x01,
     }
 }
 
 impl RestyleDamage {
-    /// Elements of self which should also get set on any ancestor flow.
-    pub fn propagate_up(self) -> RestyleDamage {
-        self & Reflow
+    /// Supposing a flow has the given `position` property and this damage, returns the damage that
+    /// we should add to the *parent* of this flow.
+    pub fn damage_for_parent(self, child_is_absolutely_positioned: bool) -> RestyleDamage {
+        if child_is_absolutely_positioned {
+            self & (Repaint | ReflowOutOfFlow)
+        } else {
+            self & (Repaint | Reflow | ReflowOutOfFlow)
+        }
     }
 
-    /// Elements of self which should also get set on any child flows.
-    pub fn propagate_down(self) -> RestyleDamage {
-        self & BubbleISizes
+    /// Supposing the *parent* of a flow with the given `position` property has this damage,
+    /// returns the damage that we should add to this flow.
+    pub fn damage_for_child(self,
+                            parent_is_absolutely_positioned: bool,
+                            child_is_absolutely_positioned: bool)
+                            -> RestyleDamage {
+        match (parent_is_absolutely_positioned, child_is_absolutely_positioned) {
+            (false, true) => {
+                // Absolute children are out-of-flow and therefore insulated from changes.
+                //
+                // FIXME(pcwalton): Au contraire, if the containing block dimensions change!
+                self & Repaint
+            }
+            (true, false) => {
+                // Changing the position of an absolutely-positioned block requires us to reflow
+                // its kids.
+                if self.contains(ReflowOutOfFlow) {
+                    self | Reflow
+                } else {
+                    self
+                }
+            }
+            _ => {
+                // TODO(pcwalton): Take floatedness into account.
+                self & (Repaint | Reflow)
+            }
+        }
     }
 }
 
@@ -42,9 +90,11 @@ impl fmt::Show for RestyleDamage {
         let mut first_elem = true;
 
         let to_iter =
-            [ (Repaint,      "Repaint")
-            , (BubbleISizes, "BubbleISizes")
-            , (Reflow,       "Reflow")
+            [ (Repaint,         "Repaint")
+            , (BubbleISizes,    "BubbleISizes")
+            , (ReflowOutOfFlow, "ReflowOutOfFlow")
+            , (Reflow,          "Reflow")
+            , (ReconstructFlow, "ReconstructFlow")
             ];
 
         for &(damage, damage_str) in to_iter.iter() {
@@ -78,7 +128,7 @@ macro_rules! add_if_not_equal(
 pub fn compute_damage(old: &Option<Arc<ComputedValues>>, new: &ComputedValues) -> RestyleDamage {
     let old: &ComputedValues =
         match old.as_ref() {
-            None => return Repaint | BubbleISizes | Reflow,
+            None => return RestyleDamage::all(),
             Some(cv) => &**cv,
         };
 
@@ -90,23 +140,83 @@ pub fn compute_damage(old: &Option<Arc<ComputedValues>>, new: &ComputedValues) -
 
     // FIXME: We can short-circuit more of this.
 
-    add_if_not_equal!(old, new, damage, [ Repaint ],
-        [ get_color.color, get_background.background_color,
-          get_border.border_top_color, get_border.border_right_color,
-          get_border.border_bottom_color, get_border.border_left_color ]);
-
-    add_if_not_equal!(old, new, damage, [ Repaint, BubbleISizes, Reflow ],
-        [ get_border.border_top_width, get_border.border_right_width,
-          get_border.border_bottom_width, get_border.border_left_width,
-          get_margin.margin_top, get_margin.margin_right,
-          get_margin.margin_bottom, get_margin.margin_left,
-          get_padding.padding_top, get_padding.padding_right,
-          get_padding.padding_bottom, get_padding.padding_left,
-          get_box.position, get_box.width, get_box.height, get_box.float, get_box.display,
-          get_font.font_family, get_font.font_size, get_font.font_style, get_font.font_weight,
-          get_inheritedtext.text_align, get_text.text_decoration, get_inheritedbox.line_height ]);
+    add_if_not_equal!(old, new, damage,
+                      [ Repaint ], [
+        get_color.color, get_background.background_color,
+        get_border.border_top_color, get_border.border_right_color,
+        get_border.border_bottom_color, get_border.border_left_color
+    ]);
+
+    add_if_not_equal!(old, new, damage,
+                      [ Repaint, ReflowOutOfFlow ], [
+        get_positionoffsets.top, get_positionoffsets.left,
+        get_positionoffsets.right, get_positionoffsets.bottom
+    ]);
+
+    add_if_not_equal!(old, new, damage,
+                      [ Repaint, BubbleISizes, ReflowOutOfFlow, Reflow ], [
+        get_border.border_top_width, get_border.border_right_width,
+        get_border.border_bottom_width, get_border.border_left_width,
+        get_margin.margin_top, get_margin.margin_right,
+        get_margin.margin_bottom, get_margin.margin_left,
+        get_padding.padding_top, get_padding.padding_right,
+        get_padding.padding_bottom, get_padding.padding_left,
+        get_box.width, get_box.height,
+        get_font.font_family, get_font.font_size, get_font.font_style, get_font.font_weight,
+        get_inheritedtext.text_align, get_text.text_decoration, get_inheritedbox.line_height
+    ]);
+
+    add_if_not_equal!(old, new, damage,
+                      [ Repaint, BubbleISizes, ReflowOutOfFlow, Reflow, ReconstructFlow ],
+                      [ get_box.float, get_box.display, get_box.position ]);
 
     // FIXME: test somehow that we checked every CSS property
 
     damage
 }
+
+pub trait LayoutDamageComputation {
+    fn compute_layout_damage(self) -> SpecialRestyleDamage;
+    fn reflow_entire_document(self);
+}
+
+impl<'a> LayoutDamageComputation for &'a mut Flow+'a {
+    fn compute_layout_damage(self) -> SpecialRestyleDamage {
+        let mut special_damage = SpecialRestyleDamage::empty();
+        let is_absolutely_positioned = flow::base(self).flags.is_absolutely_positioned();
+
+        {
+            let self_base = flow::mut_base(self);
+            for kid in self_base.children.iter_mut() {
+                let child_is_absolutely_positioned =
+                    flow::base(kid).flags.is_absolutely_positioned();
+                flow::mut_base(kid).restyle_damage
+                                   .insert(self_base.restyle_damage.damage_for_child(
+                                            is_absolutely_positioned,
+                                            child_is_absolutely_positioned));
+                special_damage.insert(kid.compute_layout_damage());
+                self_base.restyle_damage
+                         .insert(flow::base(kid).restyle_damage.damage_for_parent(
+                                 child_is_absolutely_positioned));
+            }
+        }
+
+        let self_base = flow::base(self);
+        if self_base.flags.float_kind() != float::none &&
+                self_base.restyle_damage.intersects(Reflow) {
+            special_damage.insert(ReflowEntireDocument);
+        }
+
+        special_damage
+    }
+
+    fn reflow_entire_document(self) {
+        let self_base = flow::mut_base(self);
+        self_base.restyle_damage.insert(RestyleDamage::all());
+        self_base.restyle_damage.remove(ReconstructFlow);
+        for kid in self_base.children.iter_mut() {
+            kid.reflow_entire_document();
+        }
+    }
+}
+
diff --git a/components/layout/inline.rs b/components/layout/inline.rs
index 771e275dee1..83e18ac3668 100644
--- a/components/layout/inline.rs
+++ b/components/layout/inline.rs
@@ -12,6 +12,7 @@ use flow::{BaseFlow, FlowClass, Flow, InlineFlowClass, MutableFlowUtils};
 use flow;
 use fragment::{Fragment, InlineAbsoluteHypotheticalFragment, InlineBlockFragment};
 use fragment::{ScannedTextFragment, ScannedTextFragmentInfo, SplitInfo};
+use incremental::{Reflow, ReflowOutOfFlow};
 use layout_debug;
 use model::IntrinsicISizesContribution;
 use text;
@@ -1111,6 +1112,14 @@ impl Flow for InlineFlow {
                 line.bounds.size.block;
         } // End of `lines.each` loop.
 
+        // Assign block sizes for any inline-block descendants.
+        for kid in self.base.child_iter() {
+            if flow::base(kid).flags.is_absolutely_positioned() || kid.is_float() {
+                continue
+            }
+            kid.assign_block_size_for_inorder_child_if_necessary(layout_context);
+        }
+
         self.base.position.size.block = match self.lines.as_slice().last() {
             Some(ref last_line) => last_line.bounds.start.b + last_line.bounds.size.block,
             None => Au(0),
@@ -1120,6 +1129,8 @@ impl Flow for InlineFlow {
         self.base.floats.translate(LogicalSize::new(self.base.writing_mode,
                                                     Au(0),
                                                     -self.base.position.size.block));
+
+        self.base.restyle_damage.remove(ReflowOutOfFlow | Reflow);
     }
 
     fn compute_absolute_position(&mut self) {
@@ -1210,6 +1221,8 @@ impl Flow for InlineFlow {
             self.base.validate_display_list_geometry();
         }
     }
+
+    fn repair_style(&mut self, _: &Arc<ComputedValues>) {}
 }
 
 impl fmt::Show for InlineFlow {
diff --git a/components/layout/layout_task.rs b/components/layout/layout_task.rs
index 16264b247e5..9a433003bf9 100644
--- a/components/layout/layout_task.rs
+++ b/components/layout/layout_task.rs
@@ -8,10 +8,9 @@
 use css::node_style::StyledNode;
 use construct::FlowConstructionResult;
 use context::SharedLayoutContext;
-use flow::{Flow, ImmutableFlowUtils, MutableFlowUtils, MutableOwnedFlowUtils};
-use flow;
+use flow::{mod, Flow, ImmutableFlowUtils, MutableFlowUtils, MutableOwnedFlowUtils};
 use flow_ref::FlowRef;
-use incremental::{Reflow, Repaint};
+use incremental::{LayoutDamageComputation, Reflow, ReflowEntireDocument, Repaint};
 use layout_debug;
 use parallel::UnsafeFlow;
 use parallel;
@@ -675,7 +674,10 @@ impl LayoutTask {
                 Some((&data.url, data.iframe, self.first_reflow.get())),
                 self.time_profiler_chan.clone(),
                 || {
-            layout_root.propagate_restyle_damage();
+            if opts::get().nonincremental_layout ||
+                    layout_root.compute_layout_damage().contains(ReflowEntireDocument) {
+                layout_root.reflow_entire_document()
+            }
         });
 
         // Verification of the flow tree, which ensures that all nodes were either marked as leaves
diff --git a/components/layout/table.rs b/components/layout/table.rs
index f90f291bf22..cb41e887747 100644
--- a/components/layout/table.rs
+++ b/components/layout/table.rs
@@ -22,8 +22,9 @@ use servo_util::geometry::Au;
 use servo_util::logical_geometry::LogicalRect;
 use std::cmp::max;
 use std::fmt;
+use style::{ComputedValues, CSSFloat};
 use style::computed_values::{LPA_Auto, LPA_Length, LPA_Percentage, table_layout};
-use style::CSSFloat;
+use sync::Arc;
 
 /// A table flow corresponded to the table's internal table fragment under a table wrapper flow.
 /// The properties `position`, `float`, and `margin-*` are used on the table wrapper fragment,
@@ -322,6 +323,10 @@ impl Flow for TableFlow {
     fn build_display_list(&mut self, layout_context: &LayoutContext) {
         self.block_flow.build_display_list(layout_context);
     }
+
+    fn repair_style(&mut self, new_style: &Arc<ComputedValues>) {
+        self.block_flow.repair_style(new_style)
+    }
 }
 
 impl fmt::Show for TableFlow {
diff --git a/components/layout/table_caption.rs b/components/layout/table_caption.rs
index 96e50747dc9..b27a8260f7c 100644
--- a/components/layout/table_caption.rs
+++ b/components/layout/table_caption.rs
@@ -14,6 +14,8 @@ use wrapper::ThreadSafeLayoutNode;
 
 use servo_util::geometry::Au;
 use std::fmt;
+use style::ComputedValues;
+use sync::Arc;
 
 /// A table formatting context.
 pub struct TableCaptionFlow {
@@ -73,6 +75,10 @@ impl Flow for TableCaptionFlow {
         debug!("build_display_list_table_caption: same process as block flow");
         self.block_flow.build_display_list(layout_context)
     }
+
+    fn repair_style(&mut self, new_style: &Arc<ComputedValues>) {
+        self.block_flow.repair_style(new_style)
+    }
 }
 
 impl fmt::Show for TableCaptionFlow {
diff --git a/components/layout/table_cell.rs b/components/layout/table_cell.rs
index 02c0c4445ef..c31454b162f 100644
--- a/components/layout/table_cell.rs
+++ b/components/layout/table_cell.rs
@@ -17,6 +17,8 @@ use wrapper::ThreadSafeLayoutNode;
 
 use servo_util::geometry::Au;
 use std::fmt;
+use style::ComputedValues;
+use sync::Arc;
 
 /// A table formatting context.
 #[deriving(Encodable)]
@@ -142,6 +144,10 @@ impl Flow for TableCellFlow {
     fn build_display_list(&mut self, layout_context: &LayoutContext) {
         self.block_flow.build_display_list(layout_context)
     }
+
+    fn repair_style(&mut self, new_style: &Arc<ComputedValues>) {
+        self.block_flow.repair_style(new_style)
+    }
 }
 
 impl fmt::Show for TableCellFlow {
diff --git a/components/layout/table_colgroup.rs b/components/layout/table_colgroup.rs
index 75df377778f..f726d6a3270 100644
--- a/components/layout/table_colgroup.rs
+++ b/components/layout/table_colgroup.rs
@@ -17,6 +17,8 @@ use servo_util::geometry::Au;
 use std::cmp::max;
 use std::fmt;
 use style::computed_values::LengthOrPercentageOrAuto;
+use style::ComputedValues;
+use sync::Arc;
 
 /// A table formatting context.
 pub struct TableColGroupFlow {
@@ -91,6 +93,8 @@ impl Flow for TableColGroupFlow {
 
     // Table columns are invisible.
     fn build_display_list(&mut self, _: &LayoutContext) {}
+
+    fn repair_style(&mut self, _: &Arc<ComputedValues>) {}
 }
 
 impl fmt::Show for TableColGroupFlow {
diff --git a/components/layout/table_row.rs b/components/layout/table_row.rs
index c4c26281e20..ff7eaa9a0ab 100644
--- a/components/layout/table_row.rs
+++ b/components/layout/table_row.rs
@@ -21,7 +21,9 @@ use wrapper::ThreadSafeLayoutNode;
 use servo_util::geometry::Au;
 use std::cmp::max;
 use std::fmt;
+use style::ComputedValues;
 use style::computed_values::{LPA_Auto, LPA_Length, LPA_Percentage};
+use sync::Arc;
 
 /// A single row of a table.
 #[deriving(Encodable)]
@@ -245,6 +247,10 @@ impl Flow for TableRowFlow {
     fn build_display_list(&mut self, layout_context: &LayoutContext) {
         self.block_flow.build_display_list(layout_context)
     }
+
+    fn repair_style(&mut self, new_style: &Arc<ComputedValues>) {
+        self.block_flow.repair_style(new_style)
+    }
 }
 
 impl fmt::Show for TableRowFlow {
diff --git a/components/layout/table_rowgroup.rs b/components/layout/table_rowgroup.rs
index e21aedfc5ab..10eb65f6c84 100644
--- a/components/layout/table_rowgroup.rs
+++ b/components/layout/table_rowgroup.rs
@@ -20,6 +20,8 @@ use wrapper::ThreadSafeLayoutNode;
 
 use servo_util::geometry::Au;
 use std::fmt;
+use style::ComputedValues;
+use sync::Arc;
 
 /// A table formatting context.
 #[deriving(Encodable)]
@@ -205,6 +207,10 @@ impl Flow for TableRowGroupFlow {
         debug!("build_display_list_table_rowgroup: same process as block flow");
         self.block_flow.build_display_list(layout_context)
     }
+
+    fn repair_style(&mut self, new_style: &Arc<ComputedValues>) {
+        self.block_flow.repair_style(new_style)
+    }
 }
 
 impl fmt::Show for TableRowGroupFlow {
diff --git a/components/layout/table_wrapper.rs b/components/layout/table_wrapper.rs
index 60d65b91570..b4494b129f0 100644
--- a/components/layout/table_wrapper.rs
+++ b/components/layout/table_wrapper.rs
@@ -26,8 +26,9 @@ use wrapper::ThreadSafeLayoutNode;
 use servo_util::geometry::Au;
 use std::cmp::{max, min};
 use std::fmt;
-use style::CSSFloat;
+use style::{ComputedValues, CSSFloat};
 use style::computed_values::table_layout;
+use sync::Arc;
 
 #[deriving(Encodable)]
 pub enum TableLayout {
@@ -329,6 +330,10 @@ impl Flow for TableWrapperFlow {
     fn build_display_list(&mut self, layout_context: &LayoutContext) {
         self.block_flow.build_display_list(layout_context)
     }
+
+    fn repair_style(&mut self, new_style: &Arc<ComputedValues>) {
+        self.block_flow.repair_style(new_style)
+    }
 }
 
 impl fmt::Show for TableWrapperFlow {
diff --git a/components/layout/traversal.rs b/components/layout/traversal.rs
index 439c31f28fa..b4909d3b99a 100644
--- a/components/layout/traversal.rs
+++ b/components/layout/traversal.rs
@@ -8,10 +8,10 @@ use css::node_style::StyledNode;
 use css::matching::{ApplicableDeclarations, CannotShare, MatchMethods, StyleWasShared};
 use construct::FlowConstructor;
 use context::LayoutContext;
-use flow::{Flow, ImmutableFlowUtils, MutableFlowUtils};
+use flow::{Flow, MutableFlowUtils};
 use flow::{PreorderFlowTraversal, PostorderFlowTraversal};
 use flow;
-use incremental::{RestyleDamage, BubbleISizes, Reflow};
+use incremental::{RestyleDamage, BubbleISizes, Reflow, ReflowOutOfFlow};
 use wrapper::{layout_node_to_unsafe_layout_node, LayoutNode};
 use wrapper::{PostorderNodeMutTraversal, ThreadSafeLayoutNode, UnsafeLayoutNode};
 use wrapper::{PreorderDomTraversal, PostorderDomTraversal};
@@ -134,9 +134,10 @@ impl<'a> PreorderDomTraversal for RecalcStyleForNode<'a> {
         // Just needs to be wrapped in an option for `match_node`.
         let some_bf = Some(bf);
 
-        if node.is_dirty() || node.has_dirty_siblings() {
-            // Remove existing CSS styles from changed nodes, to force
-            // non-incremental reflow.
+        let nonincremental_layout = opts::get().nonincremental_layout;
+        if nonincremental_layout || node.is_dirty() {
+            // Remove existing CSS styles from nodes whose content has changed (e.g. text changed),
+            // to force non-incremental reflow.
             if node.has_changed() {
                 let node = ThreadSafeLayoutNode::new(&node);
                 node.unstyle();
@@ -161,7 +162,9 @@ impl<'a> PreorderDomTraversal for RecalcStyleForNode<'a> {
                                         &some_bf,
                                         &mut applicable_declarations,
                                         &mut shareable);
-                   }
+                    } else {
+                        ThreadSafeLayoutNode::new(&node).set_restyle_damage(RestyleDamage::all())
+                    }
 
                     // Perform the CSS cascade.
                     unsafe {
@@ -175,7 +178,10 @@ impl<'a> PreorderDomTraversal for RecalcStyleForNode<'a> {
                         style_sharing_candidate_cache.insert_if_possible(&node);
                     }
                 }
-                StyleWasShared(index) => style_sharing_candidate_cache.touch(index),
+                StyleWasShared(index, damage) => {
+                    style_sharing_candidate_cache.touch(index);
+                    ThreadSafeLayoutNode::new(&node).set_restyle_damage(damage);
+                }
             }
         }
 
@@ -205,18 +211,16 @@ impl<'a> PostorderDomTraversal for ConstructFlows<'a> {
         {
             let tnode = ThreadSafeLayoutNode::new(&node);
 
-            // Always re-construct if incremental layout is turned off.
-            if opts::get().nonincremental_layout {
-                unsafe {
-                    node.set_dirty_descendants(true);
-                }
-            }
-
-            if node.has_dirty_descendants() {
-                tnode.set_restyle_damage(RestyleDamage::all());
+            // Always reconstruct if incremental layout is turned off.
+            let nonincremental_layout = opts::get().nonincremental_layout;
+            if nonincremental_layout || node.has_dirty_descendants() {
                 let mut flow_constructor = FlowConstructor::new(self.layout_context);
-                flow_constructor.process(&tnode);
-                debug!("Constructed flow for {:x}: {:x}", tnode.debug_id(), tnode.flow_debug_id());
+                if nonincremental_layout || !flow_constructor.repair_if_possible(&tnode) {
+                    flow_constructor.process(&tnode);
+                    debug!("Constructed flow for {:x}: {:x}",
+                           tnode.debug_id(),
+                           tnode.flow_debug_id());
+                }
             }
 
             // Reset the layout damage in this node. It's been propagated to the
@@ -300,18 +304,12 @@ pub struct AssignISizes<'a> {
 impl<'a> PreorderFlowTraversal for AssignISizes<'a> {
     #[inline]
     fn process(&self, flow: &mut Flow) {
-        if flow::base(flow).restyle_damage.contains(Reflow) {
-            flow.assign_inline_sizes(self.layout_context);
-        } else if flow.is_block_like() {
-            let block = flow.as_block();
-            block.propagate_and_compute_used_inline_size(self.layout_context);
-        }
+        flow.assign_inline_sizes(self.layout_context);
     }
 
     #[inline]
     fn should_process(&self, flow: &mut Flow) -> bool {
-        // TODO(cgaebel): Incremental inline size assignment.
-        flow::base(flow).restyle_damage.contains(Reflow) || true
+        flow::base(flow).restyle_damage.intersects(ReflowOutOfFlow | Reflow)
     }
 }
 
@@ -326,26 +324,25 @@ pub struct AssignBSizesAndStoreOverflow<'a> {
 impl<'a> PostorderFlowTraversal for AssignBSizesAndStoreOverflow<'a> {
     #[inline]
     fn process(&self, flow: &mut Flow) {
-        if !flow::base(flow).flags.impacted_by_floats() {
-            flow.assign_block_size(self.layout_context);
+        // Can't do anything with flows impacted by floats until we reach their inorder parent.
+        // NB: We must return without resetting the restyle bits for these, as we haven't actually
+        // reflowed anything!
+        if flow::base(flow).flags.impacted_by_floats() {
+            return
+        }
 
-            // Skip store-overflow for absolutely positioned flows. That will be
-            // done in a separate traversal.
+        flow.assign_block_size(self.layout_context);
 
-            if flow::base(flow).restyle_damage.contains(Reflow) {
-                if !flow.is_store_overflow_delayed() {
-                    flow.store_overflow(self.layout_context);
-                }
-            }
+        // Skip store-overflow for absolutely positioned flows. That will be
+        // done in a separate traversal.
+        if !flow.is_store_overflow_delayed() {
+            flow.store_overflow(self.layout_context);
         }
-
-        flow::mut_base(flow).restyle_damage.remove(Reflow);
     }
 
     #[inline]
     fn should_process(&self, flow: &mut Flow) -> bool {
-        // TODO(cgaebel): Incremental block size assignment.
-        flow::base(flow).restyle_damage.contains(Reflow) || true
+        flow::base(flow).restyle_damage.intersects(ReflowOutOfFlow | Reflow)
     }
 }
 
diff --git a/components/layout/util.rs b/components/layout/util.rs
index 9bb1a3ffa1f..c7ddbc0c596 100644
--- a/components/layout/util.rs
+++ b/components/layout/util.rs
@@ -42,6 +42,9 @@ pub struct PrivateLayoutData {
 
     /// Information needed during parallel traversals.
     pub parallel: DomParallelInfo,
+
+    /// Various flags.
+    pub flags: LayoutDataFlags,
 }
 
 impl PrivateLayoutData {
@@ -55,10 +58,18 @@ impl PrivateLayoutData {
             before_flow_construction_result: NoConstructionResult,
             after_flow_construction_result: NoConstructionResult,
             parallel: DomParallelInfo::new(),
+            flags: LayoutDataFlags::empty(),
         }
     }
 }
 
+bitflags! {
+    flags LayoutDataFlags: u8 {
+        #[doc="Whether a flow has been newly constructed."]
+        static HasNewlyConstructedFlow = 0x01
+    }
+}
+
 pub struct LayoutDataWrapper {
     pub chan: Option<LayoutChan>,
     pub shared_data: SharedLayoutData,
diff --git a/components/layout/wrapper.rs b/components/layout/wrapper.rs
index b204cb141d4..865c7c861be 100644
--- a/components/layout/wrapper.rs
+++ b/components/layout/wrapper.rs
@@ -32,7 +32,9 @@
 
 use context::SharedLayoutContext;
 use css::node_style::StyledNode;
-use util::{LayoutDataAccess, LayoutDataWrapper, PrivateLayoutData, OpaqueNodeMethods};
+use incremental::RestyleDamage;
+use util::{LayoutDataAccess, LayoutDataFlags, LayoutDataWrapper, OpaqueNodeMethods};
+use util::{PrivateLayoutData};
 
 use gfx::display_list::OpaqueNode;
 use script::dom::bindings::cell::{Ref, RefMut};
@@ -803,7 +805,17 @@ impl<'ln> ThreadSafeLayoutNode<'ln> {
         layout_data_wrapper_ref.data.after_style.is_some()
     }
 
+    /// Borrows the layout data without checking. Fails on a conflicting borrow.
+    #[inline(always)]
+    fn borrow_layout_data_unchecked<'a>(&'a self) -> *const Option<LayoutDataWrapper> {
+        unsafe {
+            mem::transmute(self.get().layout_data_unchecked())
+        }
+    }
+
     /// Borrows the layout data immutably. Fails on a conflicting borrow.
+    ///
+    /// TODO(pcwalton): Make this private. It will let us avoid borrow flag checks in some cases.
     #[inline(always)]
     pub fn borrow_layout_data<'a>(&'a self) -> Ref<'a,Option<LayoutDataWrapper>> {
         unsafe {
@@ -812,6 +824,8 @@ impl<'ln> ThreadSafeLayoutNode<'ln> {
     }
 
     /// Borrows the layout data mutably. Fails on a conflicting borrow.
+    ///
+    /// TODO(pcwalton): Make this private. It will let us avoid borrow flag checks in some cases.
     #[inline(always)]
     pub fn mutate_layout_data<'a>(&'a self) -> RefMut<'a,Option<LayoutDataWrapper>> {
         unsafe {
@@ -887,6 +901,50 @@ impl<'ln> ThreadSafeLayoutNode<'ln> {
             }
         }
     }
+
+    /// Get the description of how to account for recent style changes.
+    /// This is a simple bitfield and fine to copy by value.
+    pub fn restyle_damage(self) -> RestyleDamage {
+        let layout_data_ref = self.borrow_layout_data();
+        layout_data_ref.as_ref().unwrap().data.restyle_damage
+    }
+
+    /// Set the restyle damage field.
+    pub fn set_restyle_damage(self, damage: RestyleDamage) {
+        let mut layout_data_ref = self.mutate_layout_data();
+        match &mut *layout_data_ref {
+            &Some(ref mut layout_data) => layout_data.data.restyle_damage = damage,
+            _ => fail!("no layout data for this node"),
+        }
+    }
+
+    /// Returns the layout data flags for this node.
+    pub fn flags(self) -> LayoutDataFlags {
+        unsafe {
+            match *self.borrow_layout_data_unchecked() {
+                None => fail!(),
+                Some(ref layout_data) => layout_data.data.flags,
+            }
+        }
+    }
+
+    /// Adds the given flags to this node.
+    pub fn insert_flags(self, new_flags: LayoutDataFlags) {
+        let mut layout_data_ref = self.mutate_layout_data();
+        match &mut *layout_data_ref {
+            &Some(ref mut layout_data) => layout_data.data.flags.insert(new_flags),
+            _ => fail!("no layout data for this node"),
+        }
+    }
+
+    /// Removes the given flags from this node.
+    pub fn remove_flags(self, flags: LayoutDataFlags) {
+        let mut layout_data_ref = self.mutate_layout_data();
+        match &mut *layout_data_ref {
+            &Some(ref mut layout_data) => layout_data.data.flags.remove(flags),
+            _ => fail!("no layout data for this node"),
+        }
+    }
 }
 
 pub struct ThreadSafeLayoutNodeChildrenIterator<'a> {