First attempt at incremental layout

For now we only prune the bubble_widths traversal, because of inability to
reuse FloatContexts.  Other limitations are likewise marked with FIXME
comments.

8 files changed, 312 insertions, 2 deletions

diff --git a/src/components/main/css/matching.rs b/src/components/main/css/matching.rs
index 50de881b0b6..4801979bcc8 100644
--- a/src/components/main/css/matching.rs
+++ b/src/components/main/css/matching.rs
@@ -6,6 +6,7 @@
 
 use css::node_util::NodeUtil;
 use css::select_handler::NodeSelectHandler;
+use layout::incremental;
 
 use script::dom::node::{AbstractNode, LayoutView};
 use newcss::complete::CompleteSelectResults;
@@ -31,6 +32,13 @@ impl MatchMethods for AbstractNode<LayoutView> {
             let incomplete_results = select_ctx.select_style(self, &select_handler);
             // Combine this node's results with its parent's to resolve all inherited values
             let complete_results = compose_results(*self, incomplete_results);
+
+            // If there was an existing style, compute the damage that
+            // incremental layout will need to fix.
+            if self.have_css_select_results() {
+                let damage = incremental::compute_damage(self, self.get_css_select_results(), &complete_results);
+                self.set_restyle_damage(damage);
+            }
             self.set_css_select_results(complete_results);
         }
 
diff --git a/src/components/main/css/node_style.rs b/src/components/main/css/node_style.rs
index 689b62f93e0..d64e59134c4 100644
--- a/src/components/main/css/node_style.rs
+++ b/src/components/main/css/node_style.rs
@@ -5,6 +5,7 @@
 // Style retrieval from DOM elements.
 
 use css::node_util::NodeUtil;
+use layout::incremental::RestyleDamage;
 
 use newcss::complete::CompleteStyle;
 use script::dom::node::{AbstractNode, LayoutView};
@@ -12,6 +13,7 @@ use script::dom::node::{AbstractNode, LayoutView};
 /// Node mixin providing `style` method that returns a `NodeStyle`
 pub trait StyledNode {
     fn style(&self) -> CompleteStyle;
+    fn restyle_damage(&self) -> RestyleDamage;
 }
 
 impl StyledNode for AbstractNode<LayoutView> {
@@ -20,4 +22,8 @@ impl StyledNode for AbstractNode<LayoutView> {
         let results = self.get_css_select_results();
         results.computed_style()
     }
+
+    fn restyle_damage(&self) -> RestyleDamage {
+        self.get_restyle_damage()
+    }
 }
diff --git a/src/components/main/css/node_util.rs b/src/components/main/css/node_util.rs
index 0342d8e2dc7..a63ee695af5 100644
--- a/src/components/main/css/node_util.rs
+++ b/src/components/main/css/node_util.rs
@@ -3,6 +3,7 @@
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 use layout::aux::LayoutAuxMethods;
+use layout::incremental::RestyleDamage;
 
 use std::cast::transmute;
 use newcss::complete::CompleteSelectResults;
@@ -11,6 +12,10 @@ use script::dom::node::{AbstractNode, LayoutView};
 pub trait NodeUtil<'self> {
     fn get_css_select_results(self) -> &'self CompleteSelectResults;
     fn set_css_select_results(self, decl: CompleteSelectResults);
+    fn have_css_select_results(self) -> bool;
+
+    fn get_restyle_damage(self) -> RestyleDamage;
+    fn set_restyle_damage(self, damage: RestyleDamage);
 }
 
 impl<'self> NodeUtil<'self> for AbstractNode<LayoutView> {
@@ -32,6 +37,11 @@ impl<'self> NodeUtil<'self> for AbstractNode<LayoutView> {
         }
     }
 
+    /// Does this node have a computed style yet?
+    fn have_css_select_results(self) -> bool {
+        self.has_layout_data() && self.layout_data().style.is_some()
+    }
+
     /// Update the computed style of an HTML element with a style specified by CSS.
     fn set_css_select_results(self, decl: CompleteSelectResults) {
         if !self.has_layout_data() {
@@ -40,4 +50,30 @@ impl<'self> NodeUtil<'self> for AbstractNode<LayoutView> {
 
         self.layout_data().style = Some(decl);
     }
+
+    /// 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 {
+        // For DOM elements, if we haven't computed damage yet, assume the worst.
+        // Other nodes don't have styles.
+        let default = if self.is_element() {
+            RestyleDamage::all()
+        } else {
+            RestyleDamage::none()
+        };
+
+        if !self.has_layout_data() {
+            return default;
+        }
+        self.layout_data().restyle_damage.get_or_default(default)
+    }
+
+    /// Set the restyle damage field.
+    fn set_restyle_damage(self, damage: RestyleDamage) {
+        if !self.has_layout_data() {
+            fail!(~"set_restyle_damage() called on a node without aux data!");
+        }
+
+        self.layout_data().restyle_damage = Some(damage);
+    }
 }
diff --git a/src/components/main/layout/aux.rs b/src/components/main/layout/aux.rs
index 486effad90b..d63df74c53d 100644
--- a/src/components/main/layout/aux.rs
+++ b/src/components/main/layout/aux.rs
@@ -5,6 +5,7 @@
 //! Code for managing the layout data in the DOM.
 
 use layout::flow::FlowContext;
+use layout::incremental::RestyleDamage;
 
 use newcss::complete::CompleteSelectResults;
 use script::dom::node::{AbstractNode, LayoutView};
@@ -15,6 +16,9 @@ pub struct LayoutData {
     /// The results of CSS styling for this node.
     style: Option<CompleteSelectResults>,
 
+    /// Description of how to account for recent style changes.
+    restyle_damage: Option<RestyleDamage>,
+
     /// The CSS flow that this node is associated with.
     flow: Option<FlowContext>,
 }
@@ -24,6 +28,7 @@ impl LayoutData {
     pub fn new() -> LayoutData {
         LayoutData {
             style: None,
+            restyle_damage: None,
             flow: None,
         }
     }
diff --git a/src/components/main/layout/flow.rs b/src/components/main/layout/flow.rs
index 752e83b0dc1..6dd1654e746 100644
--- a/src/components/main/layout/flow.rs
+++ b/src/components/main/layout/flow.rs
@@ -32,6 +32,8 @@ use layout::context::LayoutContext;
 use layout::display_list_builder::{DisplayListBuilder, ExtraDisplayListData};
 use layout::inline::{InlineFlowData};
 use layout::float_context::{FloatContext, Invalid, FloatType};
+use layout::incremental::RestyleDamage;
+use css::node_style::StyledNode;
 
 use std::cell::Cell;
 use std::uint;
@@ -155,6 +157,7 @@ impl TreeNodeRef<FlowData> for FlowContext {
 /// `CommonFlowInfo`?
 pub struct FlowData {
     node: AbstractNode<LayoutView>,
+    restyle_damage: RestyleDamage,
 
     parent: Option<FlowContext>,
     first_child: Option<FlowContext>,
@@ -223,6 +226,7 @@ impl FlowData {
     pub fn new(id: int, node: AbstractNode<LayoutView>) -> FlowData {
         FlowData {
             node: node,
+            restyle_damage: node.restyle_damage(),
 
             parent: None,
             first_child: None,
@@ -262,6 +266,15 @@ impl<'self> FlowContext {
         }
     }
 
+    /// A convenience method to return the restyle damage of this flow. Fails if the flow is
+    /// currently being borrowed mutably.
+    #[inline(always)]
+    pub fn restyle_damage(&self) -> RestyleDamage {
+        do self.with_base |info| {
+            info.restyle_damage
+        }
+    }
+
     pub fn inline(&self) -> @mut InlineFlowData {
         match *self {
             InlineFlow(info) => info,
@@ -446,7 +459,8 @@ impl<'self> FlowContext {
         };
 
         do self.with_base |base| {
-            fmt!("f%? %? floats %? size %?", base.id, repr, base.num_floats, base.position)
+            fmt!("f%? %? floats %? size %? damage %?", base.id, repr, base.num_floats,
+                 base.position, base.restyle_damage)
         }
     }
 }
diff --git a/src/components/main/layout/incremental.rs b/src/components/main/layout/incremental.rs
new file mode 100644
index 00000000000..da26ddcfc2e
--- /dev/null
+++ b/src/components/main/layout/incremental.rs
@@ -0,0 +1,198 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+use newcss::complete::CompleteSelectResults;
+
+use script::dom::node::{AbstractNode, LayoutView};
+
+/// Individual layout actions that may be necessary after restyling.
+///
+/// If you add to this enum, also add the value to RestyleDamage::all below.
+/// (FIXME: do this automatically)
+pub enum RestyleEffect {
+    /// Repaint the node itself.
+    /// Currently unused; need to decide how this propagates.
+    Repaint = 0x01,
+
+    /// Recompute intrinsic widths (minimum and preferred).
+    /// Propagates down the flow tree because the computation is
+    /// bottom-up.
+    BubbleWidths = 0x02,
+
+    /// Recompute actual widths and heights.
+    /// Propagates up the flow tree because the computation is
+    /// top-down.
+    Reflow = 0x04,
+}
+
+/// A set of RestyleEffects.
+// FIXME: Switch to librustc/util/enum_set.rs if that gets moved into
+// libextra (Rust #8054)
+pub struct RestyleDamage {
+    priv bits: int
+}
+
+// Provide literal syntax of the form restyle_damage!(Repaint, Reflow)
+macro_rules! restyle_damage(
+    ( $($damage:ident),* ) => (
+        RestyleDamage::none() $( .add($damage) )*
+    )
+)
+
+impl RestyleDamage {
+    pub fn none() -> RestyleDamage {
+        RestyleDamage { bits: 0 }
+    }
+
+    pub fn all() -> RestyleDamage {
+        restyle_damage!(Repaint, BubbleWidths, Reflow)
+    }
+
+    /// Effects of resizing the window.
+    pub fn for_resize() -> RestyleDamage {
+        RestyleDamage::all()
+    }
+
+    pub fn is_empty(self) -> bool {
+        self.bits == 0
+    }
+
+    pub fn is_nonempty(self) -> bool {
+        self.bits != 0
+    }
+
+    pub fn add(self, effect: RestyleEffect) -> RestyleDamage {
+        RestyleDamage { bits: self.bits | (effect as int) }
+    }
+
+    pub fn has(self, effect: RestyleEffect) -> bool {
+        (self.bits & (effect as int)) != 0
+    }
+
+    pub fn lacks(self, effect: RestyleEffect) -> bool {
+        (self.bits & (effect as int)) == 0
+    }
+
+    pub fn union(self, other: RestyleDamage) -> RestyleDamage {
+        RestyleDamage { bits: self.bits | other.bits }
+    }
+
+    pub fn union_in_place(&mut self, other: RestyleDamage) {
+        self.bits = self.bits | other.bits;
+    }
+
+    pub fn intersect(self, other: RestyleDamage) -> RestyleDamage {
+        RestyleDamage { bits: self.bits & other.bits }
+    }
+
+    /// Elements of self which should also get set on any ancestor flow.
+    pub fn propagate_up(self) -> RestyleDamage {
+        self.intersect(restyle_damage!(Reflow))
+    }
+
+    /// Elements of self which should also get set on any child flows.
+    pub fn propagate_down(self) -> RestyleDamage {
+        self.intersect(restyle_damage!(BubbleWidths))
+    }
+}
+
+// NB: We need the braces inside the RHS due to Rust #8012.  This particular
+// version of this macro might be safe anyway, but we want to avoid silent
+// breakage on modifications.
+macro_rules! add_if_not_equal(
+    ([ $($effect:ident),* ], [ $($getter:ident),* ]) => ({
+        if $( (old.$getter() != new.$getter()) )||* {
+            damage.union_in_place( restyle_damage!( $($effect),* ) );
+        }
+    })
+)
+
+pub fn compute_damage(node: &AbstractNode<LayoutView>,
+                      old_results: &CompleteSelectResults, new_results: &CompleteSelectResults)
+                      -> RestyleDamage {
+    let old = old_results.computed_style();
+    let new = new_results.computed_style();
+    let mut damage = RestyleDamage::none();
+
+    // This checks every CSS property, as enumerated in
+    // impl<'self> CssComputedStyle<'self>
+    // in src/support/netsurfcss/rust-netsurfcss/netsurfcss.rc.
+
+    // FIXME: We can short-circuit more of this.
+
+    add_if_not_equal!([ Repaint ],
+        [ color, background_color, border_top_color, border_right_color,
+          border_bottom_color, border_left_color ]);
+
+    add_if_not_equal!([ Repaint, BubbleWidths, Reflow ],
+        [ border_top_width, border_right_width, border_bottom_width,
+          border_left_width, margin_top, margin_right, margin_bottom, margin_left,
+          padding_top, padding_right, padding_bottom, padding_left, position,
+          width, height, float, font_family, font_size, font_style, font_weight,
+          text_align, text_decoration, line_height ]);
+
+    // Handle 'display' specially because it has this 'is_root' parameter.
+    let is_root = node.is_root();
+    if old.display(is_root) != new.display(is_root) {
+        damage.union_in_place(restyle_damage!(Repaint, BubbleWidths, Reflow));
+    }
+
+    // FIXME: test somehow that we checked every CSS property
+
+    damage
+}
+
+
+#[cfg(test)]
+mod restyle_damage_tests {
+    use super::*;
+
+    #[test]
+    fn none_is_empty() {
+        let d = RestyleDamage::none();
+        assert!(!d.has(Repaint));
+        assert!(!d.has(BubbleWidths));
+        assert!(d.lacks(Repaint));
+        assert!(d.lacks(BubbleWidths));
+    }
+
+    #[test]
+    fn all_is_full() {
+        let d = RestyleDamage::all();
+        assert!(d.has(Repaint));
+        assert!(d.has(BubbleWidths));
+        assert!(!d.lacks(Repaint));
+        assert!(!d.lacks(BubbleWidths));
+    }
+
+    #[test]
+    fn can_add() {
+        assert!(RestyleDamage::none().add(BubbleWidths).has(BubbleWidths));
+    }
+
+    #[test]
+    fn can_union() {
+        let d = restyle_damage!(Repaint).union(restyle_damage!(BubbleWidths));
+        assert!(d.has(Repaint));
+        assert!(d.has(BubbleWidths));
+    }
+
+    #[test]
+    fn can_union_in_place() {
+        let mut d = restyle_damage!(Repaint);
+        d.union_in_place(restyle_damage!(BubbleWidths));
+        assert!(d.has(Repaint));
+        assert!(d.has(BubbleWidths));
+    }
+
+    #[test]
+    fn can_intersect() {
+        let x = restyle_damage!(Repaint, BubbleWidths);
+        let y = restyle_damage!(Repaint, Reflow);
+        let d = x.intersect(y);
+        assert!(d.has(Repaint));
+        assert!(d.lacks(BubbleWidths));
+        assert!(d.lacks(Reflow));
+    }
+}
diff --git a/src/components/main/layout/layout_task.rs b/src/components/main/layout/layout_task.rs
index ac1cacdc9b4..1581ba5f2e8 100644
--- a/src/components/main/layout/layout_task.rs
+++ b/src/components/main/layout/layout_task.rs
@@ -13,6 +13,7 @@ use layout::box_builder::LayoutTreeBuilder;
 use layout::context::LayoutContext;
 use layout::display_list_builder::{DisplayListBuilder};
 use layout::flow::FlowContext;
+use layout::incremental::{RestyleDamage, BubbleWidths};
 
 use std::cast::transmute;
 use std::cell::Cell;
@@ -193,6 +194,8 @@ impl LayoutTask {
         self.doc_url = Some(doc_url);
         let screen_size = Size2D(Au::from_px(data.window_size.width as int),
                                  Au::from_px(data.window_size.height as int));
+        let resized = self.screen_size != Some(screen_size);
+        debug!("resized: %?", resized);
         self.screen_size = Some(screen_size);
 
         // Create a layout context for use throughout the following passes.
@@ -227,20 +230,59 @@ impl LayoutTask {
             layout_root
         };
 
+        // Propagate restyle damage up and down the tree, as appropriate.
+        // FIXME: Merge this with flow tree building and/or the other traversals.
+        for layout_root.traverse_preorder |flow| {
+            // Also set any damage implied by resize.
+            if resized {
+                do flow.with_mut_base |base| {
+                    base.restyle_damage.union_in_place(RestyleDamage::for_resize());
+                }
+            }
+
+            let prop = flow.with_base(|base| base.restyle_damage.propagate_down());
+            if prop.is_nonempty() {
+                for flow.each_child |kid_ctx| {
+                    do kid_ctx.with_mut_base |kid| {
+                        kid.restyle_damage.union_in_place(prop);
+                    }
+                }
+            }
+        }
+
+        for layout_root.traverse_postorder |flow| {
+            do flow.with_base |base| {
+                match base.parent {
+                    None => {},
+                    Some(parent_ctx) => {
+                        let prop = base.restyle_damage.propagate_up();
+                        do parent_ctx.with_mut_base |parent| {
+                            parent.restyle_damage.union_in_place(prop);
+                        }
+                    }
+                }
+            }
+        }
+
         debug!("layout: constructed Flow tree");
         debug!("%?", layout_root.dump());
 
         // Perform the primary layout passes over the flow tree to compute the locations of all
         // the boxes.
         do profile(time::LayoutMainCategory, self.profiler_chan.clone()) {
-            for layout_root.traverse_postorder |flow| {
+            for layout_root.traverse_postorder_prune(|f| f.restyle_damage().lacks(BubbleWidths)) |flow| {
                 flow.bubble_widths(&mut layout_ctx);
             };
+
+            // FIXME: We want to do
+            //     for layout_root.traverse_preorder_prune(|f| f.restyle_damage().lacks(Reflow)) |flow| {
+            // but FloatContext values can't be reused, so we need to recompute them every time.
             for layout_root.traverse_preorder |flow| {
                 flow.assign_widths(&mut layout_ctx);
             };
 
             // For now, this is an inorder traversal
+            // FIXME: prune this traversal as well
             layout_root.assign_height(&mut layout_ctx);
         }
 
diff --git a/src/components/main/servo.rc b/src/components/main/servo.rc
index 5aac6b1b013..826b04f6d12 100755
--- a/src/components/main/servo.rc
+++ b/src/components/main/servo.rc
@@ -82,6 +82,7 @@ pub mod layout {
     pub mod model;
     pub mod text;
     pub mod util;
+    pub mod incremental;
     mod aux;
 }