auto merge of #3640 : cgaebel/servo/incremental-flow-construction, r=pcwalton

This also hides the not-yet-working parts of incremental reflow behind a runtime
flag. As I get the failing reftests passing, I'll send pull requests for them one
by one.

7 files changed, 237 insertions, 62 deletions

diff --git a/components/layout/construct.rs b/components/layout/construct.rs
index 7d4b6d24b81..58747ca13e9 100644
--- a/components/layout/construct.rs
+++ b/components/layout/construct.rs
@@ -43,7 +43,7 @@ use table_rowgroup::TableRowGroupFlow;
 use table_row::TableRowFlow;
 use table_cell::TableCellFlow;
 use text::TextRunScanner;
-use util::{LayoutDataAccess, OpaqueNodeMethods};
+use util::{LayoutDataAccess, OpaqueNodeMethods, LayoutDataWrapper};
 use wrapper::{PostorderNodeMutTraversal, TLayoutNode, ThreadSafeLayoutNode};
 use wrapper::{Before, After, Normal};
 
@@ -80,6 +80,22 @@ pub enum ConstructionResult {
     ConstructionItemConstructionResult(ConstructionItem),
 }
 
+impl ConstructionResult {
+    pub fn swap_out(&mut self, layout_context: &LayoutContext) -> ConstructionResult {
+        if layout_context.shared.opts.incremental_layout {
+            match *self {
+                NoConstructionResult =>
+                    return NoConstructionResult,
+                FlowConstructionResult(ref flow_ref, ref abs_descendants) =>
+                    return FlowConstructionResult((*flow_ref).clone(), (*abs_descendants).clone()),
+                ConstructionItemConstructionResult(_) => {},
+            }
+        }
+
+        mem::replace(self, NoConstructionResult)
+    }
+}
+
 /// 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 `Flow` to be attached
 /// to.
@@ -345,7 +361,7 @@ impl<'a> FlowConstructor<'a> {
                                                            &mut InlineFragmentsAccumulator,
                                                            abs_descendants: &mut Descendants,
                                                            first_fragment: &mut bool) {
-        match kid.swap_out_construction_result() {
+        match kid.swap_out_construction_result(self.layout_context) {
             NoConstructionResult => {}
             FlowConstructionResult(kid_flow, kid_abs_descendants) => {
                 // If kid_flow is TableCaptionFlow, kid_flow should be added under
@@ -546,7 +562,7 @@ impl<'a> FlowConstructor<'a> {
             if kid.get_pseudo_element_type() != Normal {
                 self.process(&kid);
             }
-            match kid.swap_out_construction_result() {
+            match kid.swap_out_construction_result(self.layout_context) {
                 NoConstructionResult => {}
                 FlowConstructionResult(flow, kid_abs_descendants) => {
                     // {ib} split. Flush the accumulator to our new split and make a new
@@ -727,12 +743,13 @@ impl<'a> FlowConstructor<'a> {
                                                table_wrapper_flow: &mut FlowRef,
                                                node: &ThreadSafeLayoutNode) {
         for kid in node.children() {
-            match kid.swap_out_construction_result() {
+            match kid.swap_out_construction_result(self.layout_context) {
                 NoConstructionResult | ConstructionItemConstructionResult(_) => {}
                 FlowConstructionResult(kid_flow, _) => {
                     // Only kid flows with table-caption are matched here.
-                    assert!(kid_flow.get().is_table_caption());
-                    table_wrapper_flow.add_new_child(kid_flow);
+                    if kid_flow.get().is_table_caption() {
+                        table_wrapper_flow.add_new_child(kid_flow);
+                    }
                 }
             }
         }
@@ -889,7 +906,7 @@ impl<'a> FlowConstructor<'a> {
         for kid in node.children() {
             // CSS 2.1 § 17.2.1. Treat all non-column child fragments of `table-column-group`
             // as `display: none`.
-            match kid.swap_out_construction_result() {
+            match kid.swap_out_construction_result(self.layout_context) {
                 ConstructionItemConstructionResult(TableColumnFragmentConstructionItem(
                         fragment)) => {
                     col_fragments.push(fragment);
@@ -958,7 +975,7 @@ impl<'a> PostorderNodeMutTraversal for FlowConstructor<'a> {
             // results of children.
             (display::none, _, _) => {
                 for child in node.children() {
-                    drop(child.swap_out_construction_result())
+                    drop(child.swap_out_construction_result(self.layout_context))
                 }
             }
 
@@ -1063,12 +1080,14 @@ trait NodeUtils {
     /// Returns true if this node doesn't render its kids and false otherwise.
     fn is_replaced_content(&self) -> bool;
 
+    fn get_construction_result<'a>(self, layout_data: &'a mut LayoutDataWrapper) -> &'a mut ConstructionResult;
+
     /// Sets the construction result of a flow.
-    fn set_flow_construction_result(&self, result: ConstructionResult);
+    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;
+    fn swap_out_construction_result(self, layout_context: &LayoutContext) -> ConstructionResult;
 }
 
 impl<'ln> NodeUtils for ThreadSafeLayoutNode<'ln> {
@@ -1087,43 +1106,30 @@ impl<'ln> NodeUtils for ThreadSafeLayoutNode<'ln> {
         }
     }
 
+    fn get_construction_result<'a>(self, layout_data: &'a mut LayoutDataWrapper) -> &'a mut ConstructionResult {
+        match self.get_pseudo_element_type() {
+            Before(_) => &mut layout_data.data.before_flow_construction_result,
+            After (_) => &mut layout_data.data.after_flow_construction_result,
+            Normal    => &mut layout_data.data.flow_construction_result,
+        }
+    }
+
     #[inline(always)]
-    fn set_flow_construction_result(&self, result: ConstructionResult) {
+    fn set_flow_construction_result(self, result: ConstructionResult) {
         let mut layout_data_ref = self.mutate_layout_data();
-        match &mut *layout_data_ref {
-            &Some(ref mut layout_data) =>{
-                match self.get_pseudo_element_type() {
-                    Before(_) => layout_data.data.before_flow_construction_result = result,
-                    After(_) => layout_data.data.after_flow_construction_result = result,
-                    Normal => layout_data.data.flow_construction_result = result,
-                }
-            },
-            &None => fail!("no layout data"),
-        }
+        let layout_data = layout_data_ref.as_mut().expect("no layout data");
+
+        let dst = self.get_construction_result(layout_data);
+
+        *dst = result;
     }
 
     #[inline(always)]
-    fn swap_out_construction_result(&self) -> ConstructionResult {
+    fn swap_out_construction_result(self, layout_context: &LayoutContext) -> ConstructionResult {
         let mut layout_data_ref = self.mutate_layout_data();
-        match &mut *layout_data_ref {
-            &Some(ref mut layout_data) => {
-                match self.get_pseudo_element_type() {
-                    Before(_) => {
-                        mem::replace(&mut layout_data.data.before_flow_construction_result,
-                                     NoConstructionResult)
-                    }
-                    After(_) => {
-                        mem::replace(&mut layout_data.data.after_flow_construction_result,
-                                     NoConstructionResult)
-                    }
-                    Normal => {
-                        mem::replace(&mut layout_data.data.flow_construction_result,
-                                     NoConstructionResult)
-                    }
-                }
-            }
-            &None => fail!("no layout data"),
-        }
+        let layout_data = layout_data_ref.as_mut().expect("no layout data");
+
+        self.get_construction_result(layout_data).swap_out(layout_context)
     }
 }
 
diff --git a/components/layout/css/node_style.rs b/components/layout/css/node_style.rs
index 8512429442a..35bb1b1a8fa 100644
--- a/components/layout/css/node_style.rs
+++ b/components/layout/css/node_style.rs
@@ -14,6 +14,7 @@ use sync::Arc;
 /// Node mixin providing `style` method that returns a `NodeStyle`
 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);
 }
@@ -24,6 +25,10 @@ impl<'ln> StyledNode for ThreadSafeLayoutNode<'ln> {
         self.get_css_select_results()
     }
 
+    fn unstyle(self) {
+        self.remove_css_select_results()
+    }
+
     fn restyle_damage(self) -> RestyleDamage {
         self.get_restyle_damage()
     }
diff --git a/components/layout/css/node_util.rs b/components/layout/css/node_util.rs
index 17d181b9937..c5268abf169 100644
--- a/components/layout/css/node_util.rs
+++ b/components/layout/css/node_util.rs
@@ -13,6 +13,7 @@ use sync::Arc;
 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);
@@ -60,6 +61,20 @@ impl<'ln> NodeUtil for ThreadSafeLayoutNode<'ln> {
         layout_data_ref.as_ref().unwrap().shared_data.style.is_some()
     }
 
+    fn remove_css_select_results(self) {
+        let mut layout_data_ref = self.mutate_layout_data();
+        let layout_data = layout_data_ref.as_mut().expect("no layout data");
+
+        let style =
+            match self.get_pseudo_element_type() {
+                Before(_) => &mut layout_data.data.before_style,
+                After (_) => &mut layout_data.data.after_style,
+                Normal    => &mut layout_data.shared_data.style,
+            };
+
+        *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 {
diff --git a/components/layout/flow.rs b/components/layout/flow.rs
index 8c75cb27eec..5aca4c11bb3 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::{RestyleDamage, Reflow};
 use inline::InlineFlow;
 use model::{CollapsibleMargins, IntrinsicISizes, MarginCollapseInfo};
 use parallel::FlowParallelInfo;
@@ -432,7 +432,13 @@ pub trait MutableFlowUtils {
     /// This is called in a bottom-up traversal (specifically, the assign-block-size traversal).
     /// 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(&mut self);
+    fn collect_static_block_offsets_from_children(self);
+
+    fn propagate_restyle_damage(self);
+
+    /// At the moment, reflow isn't idempotent. This function resets this flow
+    /// (and all its descendants, recursively), and marks them as needing reflow.
+    fn nonincremental_reset(self);
 }
 
 pub trait MutableOwnedFlowUtils {
@@ -589,6 +595,7 @@ impl FlowFlags {
 /// The Descendants of a flow.
 ///
 /// Also, details about their position wrt this flow.
+#[deriving(Clone)]
 pub struct Descendants {
     /// Links to every descendant. This must be private because it is unsafe to leak `FlowRef`s to
     /// layout.
@@ -1155,9 +1162,9 @@ impl<'a> MutableFlowUtils for &'a mut Flow + 'a {
     /// assign-block-size traversal). 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(&mut self) {
+    fn collect_static_block_offsets_from_children(self) {
         let mut absolute_descendant_block_offsets = Vec::new();
-        for kid in mut_base(*self).child_iter() {
+        for kid in mut_base(self).child_iter() {
             let mut gives_absolute_offsets = true;
             if kid.is_block_like() {
                 let kid_block = kid.as_block();
@@ -1189,7 +1196,88 @@ impl<'a> MutableFlowUtils for &'a mut Flow + 'a {
                 }
             }
         }
-        mut_base(*self).abs_descendants.static_block_offsets = absolute_descendant_block_offsets
+        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 {
+            match flow.float_clearance() {
+                clear::none  => {}
+                clear::left  => {
+                    (*dirty_floats).left  = false;
+                }
+                clear::right => {
+                    (*dirty_floats).right = false;
+                }
+                clear::both  => {
+                    (*dirty_floats).left  = false;
+                    (*dirty_floats).right = false;
+                }
+            }
+
+            match flow.float_kind() {
+                float::none  => {}
+                float::left  => {
+                    (*dirty_floats).left  = true;
+                }
+                float::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 });
+    }
+
+
+    fn nonincremental_reset(self) {
+        fn reset_flow(flow: &mut Flow) {
+            let base = mut_base(flow);
+
+            if !base.restyle_damage.contains(Reflow) {
+                return
+            }
+
+            let writing_mode = base.writing_mode;
+
+            base.position               = LogicalRect::zero(writing_mode);
+            base.overflow               = LogicalRect::zero(writing_mode);
+            base.floats                 = Floats::new(writing_mode);
+            base.collapsible_margins    = CollapsibleMargins::new();
+            base.abs_position           = Zero::zero();
+            base.block_container_explicit_block_size = None;
+            base.display_list           = DisplayList::new();
+            base.layers                 = DList::new();
+            base.absolute_position_info = AbsolutePositionInfo::new(writing_mode);
+        }
+
+        reset_flow(self);
+
+        for child in child_iter(self) {
+            child.nonincremental_reset();
+        }
     }
 }
 
diff --git a/components/layout/layout_task.rs b/components/layout/layout_task.rs
index 0eb0f739c69..2ff6d921490 100644
--- a/components/layout/layout_task.rs
+++ b/components/layout/layout_task.rs
@@ -7,7 +7,7 @@
 
 use css::matching::{ApplicableDeclarations, MatchMethods};
 use css::node_style::StyledNode;
-use construct::{FlowConstructionResult, NoConstructionResult};
+use construct::FlowConstructionResult;
 use context::{LayoutContext, SharedLayoutContext};
 use flow::{Flow, ImmutableFlowUtils, MutableFlowUtils, MutableOwnedFlowUtils};
 use flow::{PreorderFlowTraversal, PostorderFlowTraversal};
@@ -479,14 +479,12 @@ impl LayoutTask {
     }
 
     /// Retrieves the flow tree root from the root node.
-    fn get_layout_root(&self, node: LayoutNode) -> FlowRef {
+    fn get_layout_root(&self, node: LayoutNode, layout_context: &LayoutContext) -> FlowRef {
         let mut layout_data_ref = node.mutate_layout_data();
-        let result = match &mut *layout_data_ref {
-            &Some(ref mut layout_data) => {
-                mem::replace(&mut layout_data.data.flow_construction_result, NoConstructionResult)
-            }
-            &None => fail!("no layout data for root node"),
-        };
+        let layout_data = layout_data_ref.as_mut().expect("no layout data for root node");
+
+        let result = layout_data.data.flow_construction_result.swap_out(layout_context);
+
         let mut flow = match result {
             FlowConstructionResult(mut flow, abs_descendants) => {
                 // Note: Assuming that the root has display 'static' (as per
@@ -499,6 +497,7 @@ impl LayoutTask {
             }
             _ => fail!("Flow construction didn't result in a flow at the root of the tree!"),
         };
+
         flow.get_mut().mark_as_root();
         flow
     }
@@ -657,7 +656,23 @@ impl LayoutTask {
                 }
             }
 
-            self.get_layout_root((*node).clone())
+            self.get_layout_root((*node).clone(), &LayoutContext::new(&shared_layout_ctx))
+        });
+
+        profile(time::LayoutRestyleDamagePropagation,
+                Some((&data.url, data.iframe, self.first_reflow.get())),
+                self.time_profiler_chan.clone(),
+                || {
+            layout_root.get_mut().propagate_restyle_damage();
+        });
+
+        profile(time::LayoutNonIncrementalReset,
+                Some((&data.url, data.iframe, self.first_reflow.get())),
+                self.time_profiler_chan.clone(),
+                || {
+            if shared_layout_ctx.opts.incremental_layout {
+                layout_root.get_mut().nonincremental_reset();
+            }
         });
 
         // Verification of the flow tree, which ensures that all nodes were either marked as leaves
diff --git a/components/layout/traversal.rs b/components/layout/traversal.rs
index 41896ba1fad..b9686e84276 100644
--- a/components/layout/traversal.rs
+++ b/components/layout/traversal.rs
@@ -132,8 +132,15 @@ 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() {
-            // First, check to see whether we can share a style with someone.
+        if node.is_dirty() || node.has_dirty_siblings() {
+            // Remove existing CSS styles from changed nodes, to force
+            // non-incremental reflow.
+            if node.has_changed() {
+                let node = ThreadSafeLayoutNode::new(&node);
+                node.unstyle();
+            }
+
+            // Check to see whether we can share a style with someone.
             let style_sharing_candidate_cache =
                 self.layout_context.style_sharing_candidate_cache();
             let sharing_result = unsafe {
@@ -194,17 +201,31 @@ impl<'a> PostorderDomTraversal for ConstructFlows<'a> {
     fn process(&self, node: LayoutNode) {
         // Construct flows for this node.
         {
-            let node = ThreadSafeLayoutNode::new(&node);
-            let mut flow_constructor = FlowConstructor::new(self.layout_context);
-            flow_constructor.process(&node);
+            let tnode = ThreadSafeLayoutNode::new(&node);
+
+            // Always re-construct if incremental layout is turned off.
+            if !self.layout_context.shared.opts.incremental_layout {
+                unsafe {
+                    node.set_dirty_descendants(true);
+                }
+            }
+
+            if node.has_dirty_descendants() {
+                tnode.set_restyle_damage(RestyleDamage::all());
+                debug!("Constructing flow for {}", tnode.debug_id());
+                let mut flow_constructor = FlowConstructor::new(self.layout_context);
+                flow_constructor.process(&tnode);
+            }
 
             // Reset the layout damage in this node. It's been propagated to the
             // flow by the flow constructor.
-            node.set_restyle_damage(RestyleDamage::empty());
+            tnode.set_restyle_damage(RestyleDamage::empty());
         }
 
         unsafe {
+            node.set_changed(false);
             node.set_dirty(false);
+            node.set_dirty_siblings(false);
             node.set_dirty_descendants(false);
         }
 
diff --git a/components/layout/wrapper.rs b/components/layout/wrapper.rs
index 706d8b8d04e..6f1d01dcbf2 100644
--- a/components/layout/wrapper.rs
+++ b/components/layout/wrapper.rs
@@ -49,7 +49,7 @@ use script::dom::htmlimageelement::{HTMLImageElement, LayoutHTMLImageElementHelp
 use script::dom::htmlinputelement::{HTMLInputElement, LayoutHTMLInputElementHelpers};
 use script::dom::node::{DocumentNodeTypeId, ElementNodeTypeId, Node, NodeTypeId};
 use script::dom::node::{LayoutNodeHelpers, RawLayoutNodeHelpers, SharedLayoutData, TextNodeTypeId};
-use script::dom::node::{IsDirty, HasDirtyDescendants};
+use script::dom::node::{HasChanged, IsDirty, HasDirtySiblings, HasDirtyDescendants};
 use script::dom::text::Text;
 use script::layout_interface::LayoutChan;
 use servo_msg::constellation_msg::{PipelineId, SubpageId};
@@ -267,6 +267,11 @@ impl<'ln> LayoutNode<'ln> {
             self.parent_node()
         }
     }
+
+    pub fn debug_id(self) -> uint {
+        let opaque: OpaqueNode = OpaqueNodeMethods::from_layout_node(&self);
+        opaque.to_untrusted_node_address() as uint
+    }
 }
 
 impl<'ln> TNode<'ln, LayoutElement<'ln>> for LayoutNode<'ln> {
@@ -343,6 +348,14 @@ impl<'ln> TNode<'ln, LayoutElement<'ln>> for LayoutNode<'ln> {
         }
     }
 
+    fn has_changed(self) -> bool {
+        unsafe { self.node.get_flag(HasChanged) }
+    }
+
+    unsafe fn set_changed(self, value: bool) {
+        self.node.set_flag(HasChanged, value)
+    }
+
     fn is_dirty(self) -> bool {
         unsafe { self.node.get_flag(IsDirty) }
     }
@@ -351,6 +364,14 @@ impl<'ln> TNode<'ln, LayoutElement<'ln>> for LayoutNode<'ln> {
         self.node.set_flag(IsDirty, value)
     }
 
+    fn has_dirty_siblings(self) -> bool {
+        unsafe { self.node.get_flag(HasDirtySiblings) }
+    }
+
+    unsafe fn set_dirty_siblings(self, value: bool) {
+        self.node.set_flag(HasDirtySiblings, value);
+    }
+
     fn has_dirty_descendants(self) -> bool {
         unsafe { self.node.get_flag(HasDirtyDescendants) }
     }
@@ -668,6 +689,10 @@ impl<'ln> ThreadSafeLayoutNode<'ln> {
         }
     }
 
+    pub fn debug_id(self) -> uint {
+        self.node.debug_id()
+    }
+
     /// Returns the next sibling of this node. Unsafe and private because this can lead to races.
     unsafe fn next_sibling(&self) -> Option<ThreadSafeLayoutNode<'ln>> {
         if self.pseudo.is_before() {