auto merge of #646 : kmcallister/servo/incremental-layout, r=metajack

This is a first attempt at incremental layout.  When recomputing styles, we compare old and new CSS properties to determine which layout steps can be skipped.

Since I'm new to Servo I'm not sure that my code matches the idioms of the project.  Please don't hold back with review comments :)

19 files changed, 384 insertions, 78 deletions

diff --git a/src/components/gfx/font_context.rs b/src/components/gfx/font_context.rs
index 1eff76495cd..60f58d9571f 100644
--- a/src/components/gfx/font_context.rs
+++ b/src/components/gfx/font_context.rs
@@ -134,11 +134,8 @@ impl<'self> FontContext {
             let transformed_family_name = self.transform_family(family_name);
             debug!("(create font group) transformed family is `%s`", transformed_family_name);
 
-            let result = match self.font_list {
-                Some(ref fl) => {
-                    fl.find_font_in_family(transformed_family_name, style)
-                },
-                None => None,
+            let result = do self.font_list.chain_ref |fl| {
+                fl.find_font_in_family(transformed_family_name, style)
             };
 
             let mut found = false;
@@ -162,11 +159,8 @@ impl<'self> FontContext {
         let last_resort = FontList::get_last_resort_font_families();
 
         for last_resort.iter().advance |family| {
-            let result = match self.font_list {
-                Some(ref fl) => {
-                    fl.find_font_in_family(*family, style)
-                },
-                None => None,
+            let result = do self.font_list.chain_ref |fl| {
+                fl.find_font_in_family(*family, style)
             };
 
             for result.iter().advance |font_entry| {
diff --git a/src/components/gfx/opts.rs b/src/components/gfx/opts.rs
index 456d37869c9..e1b46027cc1 100644
--- a/src/components/gfx/opts.rs
+++ b/src/components/gfx/opts.rs
@@ -78,11 +78,9 @@ pub fn from_cmdline_args(args: &[~str]) -> Opts {
         None => 1,      // FIXME: Number of cores.
     };
 
-    let profiler_period: Option<float> =
-        // if only flag is present, default to 5 second period
-        match getopts::opt_default(&opt_match, "p", "5") {
-        Some(period) => Some(float::from_str(period).get()),
-        None => None,
+    // if only flag is present, default to 5 second period
+    let profiler_period = do getopts::opt_default(&opt_match, "p", "5").map |period| {
+        float::from_str(*period).get()
     };
 
     let exit_after_load = getopts::opt_present(&opt_match, "x");
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/css/select_handler.rs b/src/components/main/css/select_handler.rs
index be7b21b3924..4a294aa2426 100644
--- a/src/components/main/css/select_handler.rs
+++ b/src/components/main/css/select_handler.rs
@@ -30,17 +30,14 @@ impl SelectHandler<AbstractNode<LayoutView>> for NodeSelectHandler {
 
     fn named_parent_node(&self, node: &AbstractNode<LayoutView>, name: &str)
                          -> Option<AbstractNode<LayoutView>> {
-        match node.parent_node() {
-            Some(parent) => {
-                do with_node_name(parent) |node_name| {
-                    if eq_slice(name, node_name) {
-                        Some(parent)
-                    } else {
-                        None
-                    }
+        do node.parent_node().chain |parent| {
+            do with_node_name(parent) |node_name| {
+                if eq_slice(name, node_name) {
+                    Some(parent)
+                } else {
+                    None
                 }
             }
-            None => None
         }
     }
 
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/box_builder.rs b/src/components/main/layout/box_builder.rs
index 717bfd61a49..fd5dfd5bbc1 100644
--- a/src/components/main/layout/box_builder.rs
+++ b/src/components/main/layout/box_builder.rs
@@ -356,14 +356,8 @@ impl LayoutTreeBuilder {
                               sibling_generator: Option<@mut BoxGenerator>)
                               -> Option<(@mut BoxGenerator, @mut BoxGenerator)> {
 
-        fn is_root(node: AbstractNode<LayoutView>) -> bool {
-            match node.parent_node() {
-                None => true,
-                Some(_) => false
-            }
-        }
         let display = if node.is_element() {
-            match node.style().display(is_root(node)) {
+            match node.style().display(node.is_root()) {
                 CSSDisplayNone => return None, // tree ends here if 'display: none'
                 // TODO(eatkinson) these are hacks so that the code doesn't crash
                 // when unsupported display values are used. They should be deleted
@@ -390,11 +384,8 @@ impl LayoutTreeBuilder {
             }
         };
 
-        let sibling_flow: Option<FlowContext> = match sibling_generator {
-            None => None,
-            Some(gen) => Some(gen.flow)
-        };
-        
+        let sibling_flow: Option<FlowContext> = sibling_generator.map(|gen| gen.flow);
+
         // TODO(eatkinson): use the value of the float property to
         // determine whether to float left or right.
         let is_float = if (node.is_element()) {
diff --git a/src/components/main/layout/float_context.rs b/src/components/main/layout/float_context.rs
index 6ccef10939e..04c7040acc0 100644
--- a/src/components/main/layout/float_context.rs
+++ b/src/components/main/layout/float_context.rs
@@ -291,10 +291,7 @@ impl FloatContextBase{
             }
         }
 
-        match max_height {
-            None => None,
-            Some(h) => Some(h + self.offset.y)
-        }
+        max_height.map(|h| h + self.offset.y)
     }
 
     /// Given necessary info, finds the closest place a box can be positioned
diff --git a/src/components/main/layout/flow.rs b/src/components/main/layout/flow.rs
index 38fd16974b3..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;
@@ -45,6 +47,7 @@ use servo_util::tree::{TreeNode, TreeNodeRef, TreeUtils};
 
 /// The type of the formatting context and data specific to each context, such as line box
 /// structures or float lists.
+#[deriving(Clone)]
 pub enum FlowContext {
     AbsoluteFlow(@mut FlowData), 
     BlockFlow(@mut BlockFlowData),
@@ -64,12 +67,6 @@ pub enum FlowContextType {
     Flow_Table
 }
 
-impl Clone for FlowContext {
-    fn clone(&self) -> FlowContext {
-        *self
-    }
-}
-
 impl FlowContext {
     pub fn teardown(&self) {
         match *self {
@@ -84,6 +81,9 @@ impl FlowContext {
 
     /// Like traverse_preorder, but don't end the whole traversal if the callback
     /// returns false.
+    //
+    // FIXME: Unify this with traverse_preorder_prune, which takes a separate
+    // 'prune' function.
     fn partially_traverse_preorder(&self, callback: &fn(FlowContext) -> bool) {
         if !callback((*self).clone()) {
             return;
@@ -157,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>,
@@ -225,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,
@@ -264,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,
@@ -448,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 68ba371d110..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());
+        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);
         }
 
@@ -272,8 +314,6 @@ impl LayoutTask {
             } // time(layout: display list building)
         }
 
-        debug!("%?", layout_root.dump());
-
         // Tell script that we're done.
         //
         // FIXME(pcwalton): This should probably be *one* channel, but we can't fix this without
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;
 }
 
diff --git a/src/components/net/image/holder.rs b/src/components/net/image/holder.rs
index 61173703c45..bf56b6413e3 100644
--- a/src/components/net/image/holder.rs
+++ b/src/components/net/image/holder.rs
@@ -57,14 +57,11 @@ impl ImageHolder {
     /// Query and update the current image size.
     pub fn get_size(&mut self) -> Option<Size2D<int>> {
         debug!("get_size() %?", self.url);
-        match self.get_image() {
-            Some(img) => { 
-                let img_ref = img.get();
-                self.cached_size = Size2D(img_ref.width as int,
-                                          img_ref.height as int);
-                Some(copy self.cached_size)
-            },
-            None => None
+        do self.get_image().map |img| {
+            let img_ref = img.get();
+            self.cached_size = Size2D(img_ref.width as int,
+                                      img_ref.height as int);
+            self.cached_size.clone()
         }
     }
 
@@ -89,12 +86,7 @@ impl ImageHolder {
 
         // Clone isn't pure so we have to swap out the mutable image option
         let image = replace(&mut self.image, None);
-
-        let result = match image {
-            Some(ref image) => Some(image.clone()),
-            None => None
-        };
-
+        let result = image.clone();
         replace(&mut self.image, image);
 
         return result;
diff --git a/src/components/script/dom/node.rs b/src/components/script/dom/node.rs
index d9ee80edaa1..edd108e6881 100644
--- a/src/components/script/dom/node.rs
+++ b/src/components/script/dom/node.rs
@@ -264,6 +264,11 @@ impl<'self, View> AbstractNode<View> {
         self.with_base(|b| b.next_sibling)
     }
 
+    /// Is this node a root?
+    pub fn is_root(self) -> bool {
+        self.parent_node().is_none()
+    }
+
     //
     // Downcasting borrows
     //
@@ -415,10 +420,7 @@ impl<'self, View> AbstractNode<View> {
 impl<View> Iterator<AbstractNode<View>> for AbstractNodeChildrenIterator<View> {
     pub fn next(&mut self) -> Option<AbstractNode<View>> {
         let node = self.current_node;
-        self.current_node = match self.current_node {
-            None => None,
-            Some(node) => node.next_sibling(),
-        };
+        self.current_node = self.current_node.chain(|node| node.next_sibling());
         node
     }
 }
diff --git a/src/components/util/tree.rs b/src/components/util/tree.rs
index 94ceb5e1b36..eebf91fa10f 100644
--- a/src/components/util/tree.rs
+++ b/src/components/util/tree.rs
@@ -69,6 +69,20 @@ pub trait TreeUtils {
 
     /// Iterates over this node and all its descendants, in postorder.
     fn traverse_postorder(&self, callback: &fn(Self) -> bool) -> bool;
+
+    /// Like traverse_preorder but calls 'prune' first on each node.  If it returns true then we
+    /// skip the whole subtree but continue iterating.
+    ///
+    /// 'prune' is a separate function a) for compatibility with the 'for' protocol,
+    /// b) so that the postorder version can still prune before traversing.
+    fn traverse_preorder_prune(&self, prune: &fn(&Self) -> bool, callback: &fn(Self) -> bool) -> bool;
+
+    /// Like traverse_postorder but calls 'prune' first on each node.  If it returns true then we
+    /// skip the whole subtree but continue iterating.
+    ///
+    /// NB: 'prune' is called *before* traversing children, even though this is a
+    /// postorder traversal.
+    fn traverse_postorder_prune(&self, prune: &fn(&Self) -> bool, callback: &fn(Self) -> bool) -> bool;
 }
 
 impl<NR:TreeNodeRef<N>,N:TreeNode<NR>> TreeUtils for NR {
@@ -146,14 +160,19 @@ impl<NR:TreeNodeRef<N>,N:TreeNode<NR>> TreeUtils for NR {
         true
     }
 
-    fn traverse_preorder(&self, callback: &fn(NR) -> bool) -> bool {
+    fn traverse_preorder_prune(&self, prune: &fn(&NR) -> bool, callback: &fn(NR) -> bool) -> bool {
+        // prune shouldn't mutate, so don't clone
+        if prune(self) {
+            return true;
+        }
+
         if !callback((*self).clone()) {
             return false;
         }
 
         for self.each_child |kid| {
             // FIXME: Work around rust#2202. We should be able to pass the callback directly.
-            if !kid.traverse_preorder(|a| callback(a)) {
+            if !kid.traverse_preorder_prune(|a| prune(a), |a| callback(a)) {
                 return false;
             }
         }
@@ -161,15 +180,28 @@ impl<NR:TreeNodeRef<N>,N:TreeNode<NR>> TreeUtils for NR {
         true
     }
 
-    fn traverse_postorder(&self, callback: &fn(NR) -> bool) -> bool {
+    fn traverse_postorder_prune(&self, prune: &fn(&NR) -> bool, callback: &fn(NR) -> bool) -> bool {
+        // prune shouldn't mutate, so don't clone
+        if prune(self) {
+            return true;
+        }
+
         for self.each_child |kid| {
             // FIXME: Work around rust#2202. We should be able to pass the callback directly.
-            if !kid.traverse_postorder(|a| callback(a)) {
+            if !kid.traverse_postorder_prune(|a| prune(a), |a| callback(a)) {
                 return false;
             }
         }
 
         callback((*self).clone())
     }
+
+    fn traverse_preorder(&self, callback: &fn(NR) -> bool) -> bool {
+        self.traverse_preorder_prune(|_| false, callback)
+    }
+
+    fn traverse_postorder(&self, callback: &fn(NR) -> bool) -> bool {
+        self.traverse_postorder_prune(|_| false, callback)
+    }
 }
 
diff --git a/src/components/util/vec.rs b/src/components/util/vec.rs
index dab59bfa1da..fa34c52a350 100644
--- a/src/components/util/vec.rs
+++ b/src/components/util/vec.rs
@@ -11,10 +11,7 @@ pub trait BinarySearchMethods<'self, T: Ord + Eq> {
 
 impl<'self, T: Ord + Eq> BinarySearchMethods<'self, T> for &'self [T] {
     fn binary_search(&self, key: &T) -> Option<&'self T> {
-        match self.binary_search_index(key) {
-            None => None,
-            Some(i) => Some(&self[i])
-        }
+        self.binary_search_index(key).map(|i| &self[*i])
     }
 
     fn binary_search_index(&self, key: &T) -> Option<uint> {
diff --git a/src/support/css/rust-css b/src/support/css/rust-css
-Subproject 8b9cf93fb03027d0f125afbd84cf758bd8d2d67
+Subproject b45dd830488d4ea345c0e84a1da081bd69c6fc7
diff --git a/src/test/html/color-change-text.js b/src/test/html/color-change-text.js
index c0c47837b04..41b9e3881cf 100644
--- a/src/test/html/color-change-text.js
+++ b/src/test/html/color-change-text.js
@@ -1,3 +1,3 @@
 window.setTimeout(function () {
-    document.getElementsByTagName('div')[0].setAttribute('class', 'blue');
+    window.document.getElementsByTagName('div')[0].setAttribute('class', 'blue');
 }, 1000);