auto merge of #1208 : pcwalton/servo/any-layout-data, r=metajack

Breaks the dependency between `gfx` and `script`, which is nice.

This exposed some performance issues with Rust's `Any` type, which I've filed:

https://github.com/mozilla/rust/issues/10382

7 files changed, 202 insertions, 149 deletions

diff --git a/src/components/main/css/matching.rs b/src/components/main/css/matching.rs
index f7da616f19e..c7f27b1a9ad 100644
--- a/src/components/main/css/matching.rs
+++ b/src/components/main/css/matching.rs
@@ -14,6 +14,7 @@ use extra::arc::RWArc;
 use css::node_style::StyledNode;
 use css::node_util::NodeUtil;
 use layout::incremental;
+use layout::util::LayoutDataAccess;
 
 use script::dom::node::{AbstractNode, LayoutView};
 use style::Stylist;
@@ -37,10 +38,7 @@ impl MatchMethods for AbstractNode<LayoutView> {
             };
             stylist.get_applicable_declarations(self, style_attribute, None)
         };
-        let cell = Cell::new(applicable_declarations);
-        do self.write_layout_data |data| {
-            data.applicable_declarations = cell.take();
-        }
+        self.layout_data().applicable_declarations.set(applicable_declarations)
     }
     fn match_subtree(&self, stylist: RWArc<Stylist>) {
         let num_tasks = default_sched_threads() * 2;
@@ -84,22 +82,21 @@ impl MatchMethods for AbstractNode<LayoutView> {
             Some(parent) => Some(parent.style()),
             None => None
         };
-        let computed_values = do self.read_layout_data |data| {
-            cascade(data.applicable_declarations, parent_style)
-        };
-        let cell = Cell::new(computed_values);
-        do self.write_layout_data |data| {
-            let style = cell.take();
-            // If there was an existing style, compute the damage that
-            // incremental layout will need to fix.
-            match data.style {
-                None => (),
-                Some(ref previous_style) => self.set_restyle_damage(
-                    incremental::compute_damage(previous_style, &style))
+
+        let layout_data = self.layout_data();
+        let computed_values = cascade(*layout_data.applicable_declarations.borrow().ptr,
+                                      parent_style);
+        let style = layout_data.style.mutate();
+        match *style.ptr {
+            None => (),
+            Some(ref previous_style) => {
+                self.set_restyle_damage(incremental::compute_damage(previous_style,
+                                                                    &computed_values))
             }
-            data.style = Some(style);
         }
+        *style.ptr = Some(computed_values)
     }
+
     fn cascade_subtree(&self, parent: Option<AbstractNode<LayoutView>>) {
         self.cascade_node(parent);
 
diff --git a/src/components/main/css/node_util.rs b/src/components/main/css/node_util.rs
index 2d670129b8f..104174b7b8c 100644
--- a/src/components/main/css/node_util.rs
+++ b/src/components/main/css/node_util.rs
@@ -3,14 +3,13 @@
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 use layout::incremental::RestyleDamage;
+use layout::util::LayoutDataAccess;
 
 use std::cast;
-use std::cell::Cell;
 use style::ComputedValues;
 use script::dom::node::{AbstractNode, LayoutView};
 use servo_util::tree::TreeNodeRef;
 
-
 pub trait NodeUtil<'self> {
     fn get_css_select_results(self) -> &'self ComputedValues;
     fn set_css_select_results(self, decl: ComputedValues);
@@ -29,23 +28,21 @@ impl<'self> NodeUtil<'self> for AbstractNode<LayoutView> {
      * stored in a box that can be overwritten
      */
     fn get_css_select_results(self) -> &'self ComputedValues {
-        do self.read_layout_data |layout_data| {
-            match layout_data.style {
-                None => fail!(~"style() called on node without a style!"),
-                Some(ref style) => unsafe { cast::transmute_region(style) }
-            }
+        let layout_data = self.layout_data();
+        match *layout_data.style.borrow().ptr {
+            None => fail!(~"style() called on node without a style!"),
+            Some(ref style) => unsafe { cast::transmute_region(style) }
         }
     }
 
     /// Does this node have a computed style yet?
     fn have_css_select_results(self) -> bool {
-        self.read_layout_data(|data| data.style.is_some())
+        self.layout_data().style.borrow().ptr.is_some()
     }
 
     /// Update the computed style of an HTML element with a style specified by CSS.
     fn set_css_select_results(self, decl: ComputedValues) {
-        let cell = Cell::new(decl);
-        self.write_layout_data(|data| data.style = Some(cell.take()));
+        *self.layout_data().style.mutate().ptr = Some(decl)
     }
 
     /// Get the description of how to account for recent style changes.
@@ -59,15 +56,17 @@ impl<'self> NodeUtil<'self> for AbstractNode<LayoutView> {
             RestyleDamage::none()
         };
 
-        do self.read_layout_data |layout_data| {
-            layout_data.restyle_damage
-                .map(|x| RestyleDamage::from_int(x))
-                .unwrap_or(default)
-        }
+        self.layout_data()
+            .restyle_damage
+            .borrow()
+            .ptr
+            .map(|x| RestyleDamage::from_int(x))
+            .unwrap_or(default)
     }
 
     /// Set the restyle damage field.
     fn set_restyle_damage(self, damage: RestyleDamage) {
-        self.write_layout_data(|data| data.restyle_damage = Some(damage.to_int()));
+        *self.layout_data().restyle_damage.mutate().ptr = Some(damage.to_int())
     }
 }
+
diff --git a/src/components/main/layout/aux.rs b/src/components/main/layout/aux.rs
index 98406c802df..0bb1cbb4cd2 100644
--- a/src/components/main/layout/aux.rs
+++ b/src/components/main/layout/aux.rs
@@ -4,8 +4,11 @@
 
 //! Code for managing the layout data in the DOM.
 
+use layout::util::{DisplayBoxes, LayoutData, LayoutDataAccess};
+
 use script::dom::node::{AbstractNode, LayoutView};
 use servo_util::tree::TreeNodeRef;
+use std::cast;
 
 /// Functionality useful for querying the layout-specific data on DOM nodes.
 pub trait LayoutAuxMethods {
@@ -15,10 +18,16 @@ pub trait LayoutAuxMethods {
 
 impl LayoutAuxMethods for AbstractNode<LayoutView> {
     /// Resets layout data and styles for the node.
+    ///
+    /// FIXME(pcwalton): Do this as part of box building instead of in a traversal.
     fn initialize_layout_data(self) {
-        do self.write_layout_data |data| {
-            data.boxes.display_list = None;
-            data.boxes.range = None;
+        unsafe {
+            let node = cast::transmute_mut(self.node());
+            if node.layout_data.is_none() {
+                node.layout_data = Some(~LayoutData::new() as ~Any)
+            } else {
+                self.layout_data().boxes.set(DisplayBoxes::init());
+            }
         }
     }
 
diff --git a/src/components/main/layout/layout_task.rs b/src/components/main/layout/layout_task.rs
index 819cfffcf72..14f9235ad9c 100644
--- a/src/components/main/layout/layout_task.rs
+++ b/src/components/main/layout/layout_task.rs
@@ -15,10 +15,11 @@ use layout::flow::{FlowContext, ImmutableFlowUtils, MutableFlowUtils, PreorderFl
 use layout::flow::{PostorderFlowTraversal};
 use layout::flow;
 use layout::incremental::{RestyleDamage, BubbleWidths};
+use layout::util::LayoutDataAccess;
 
 use std::cast::transmute;
 use std::cell::Cell;
-use std::comm::{Port};
+use std::comm::Port;
 use std::task;
 use extra::arc::{Arc, RWArc};
 use geom::point::Point2D;
@@ -419,22 +420,23 @@ impl LayoutTask {
                         transmute(display_list.get().list[i].base().extra)
                     };
 
-                    do node.write_layout_data |layout_data| {
-                        layout_data.boxes.display_list = Some(display_list.clone());
-
-                        if layout_data.boxes.range.is_none() {
-                            debug!("Creating initial range for node");
-                            layout_data.boxes.range = Some(Range::new(i,1));
-                        } else {
-                            debug!("Appending item to range");
-                            unsafe {
-                                let old_node: AbstractNode<()> = transmute(node);
-                                assert!(old_node == display_list.get().list[i-1].base().extra,
-                                "Non-contiguous arrangement of display items");
-                            }
-
-                            layout_data.boxes.range.unwrap().extend_by(1);
+                    // FIXME(pcwalton): Why are we cloning the display list here?!
+                    let layout_data = node.layout_data();
+                    let boxes = layout_data.boxes.mutate();
+                    boxes.ptr.display_list = Some(display_list.clone());
+
+                    if boxes.ptr.range.is_none() {
+                        debug!("Creating initial range for node");
+                        boxes.ptr.range = Some(Range::new(i,1));
+                    } else {
+                        debug!("Appending item to range");
+                        unsafe {
+                            let old_node: AbstractNode<()> = transmute(node);
+                            assert!(old_node == display_list.get().list[i-1].base().extra,
+                            "Non-contiguous arrangement of display items");
                         }
+
+                        boxes.ptr.range.unwrap().extend_by(1);
                     }
                 }
 
@@ -469,34 +471,35 @@ impl LayoutTask {
                 };
 
                 fn box_for_node(node: AbstractNode<LayoutView>) -> Option<Rect<Au>> {
-                    do node.read_layout_data |layout_data| {
-                        match (layout_data.boxes.display_list.clone(), layout_data.boxes.range) {
-                            (Some(display_list), Some(range)) => {
-                                let mut rect: Option<Rect<Au>> = None;
-                                for i in range.eachi() {
-                                    rect = match rect {
-                                        Some(acc) => {
-                                            Some(acc.union(&display_list.get().list[i].bounds()))
-                                        }
-                                        None => Some(display_list.get().list[i].bounds())
+                    // FIXME(pcwalton): Why are we cloning the display list here?!
+                    let boxes = node.layout_data().boxes.borrow();
+                    let boxes = boxes.ptr;
+                    match (boxes.display_list.clone(), boxes.range) {
+                        (Some(display_list), Some(range)) => {
+                            let mut rect: Option<Rect<Au>> = None;
+                            for i in range.eachi() {
+                                rect = match rect {
+                                    Some(acc) => {
+                                        Some(acc.union(&display_list.get().list[i].bounds()))
                                     }
+                                    None => Some(display_list.get().list[i].bounds())
                                 }
-                                rect
                             }
-                            _ => {
-                                let mut acc: Option<Rect<Au>> = None;
-                                for child in node.children() {
-                                    let rect = box_for_node(child);
-                                    match rect {
-                                        None => continue,
-                                        Some(rect) => acc = match acc {
-                                            Some(acc) =>  Some(acc.union(&rect)),
-                                            None => Some(rect)
-                                        }
+                            rect
+                        }
+                        _ => {
+                            let mut acc: Option<Rect<Au>> = None;
+                            for child in node.children() {
+                                let rect = box_for_node(child);
+                                match rect {
+                                    None => continue,
+                                    Some(rect) => acc = match acc {
+                                        Some(acc) =>  Some(acc.union(&rect)),
+                                        None => Some(rect)
                                     }
                                 }
-                                acc
                             }
+                            acc
                         }
                     }
                 }
@@ -511,25 +514,23 @@ impl LayoutTask {
                     transmute(node)
                 };
 
-                fn boxes_for_node(node: AbstractNode<LayoutView>,
-                                  boxes: ~[Rect<Au>]) -> ~[Rect<Au>] {
-                    let boxes = Cell::new(boxes);
-                    do node.read_layout_data |layout_data| {
-                        let mut boxes = boxes.take();
-                        match (layout_data.boxes.display_list.clone(), layout_data.boxes.range) {
-                            (Some(display_list), Some(range)) => {
-                                for i in range.eachi() {
-                                    boxes.push(display_list.get().list[i].bounds());
-                                }
+                fn boxes_for_node(node: AbstractNode<LayoutView>, mut box_accumulator: ~[Rect<Au>])
+                                  -> ~[Rect<Au>] {
+                    let boxes = node.layout_data().boxes.borrow();
+                    let boxes = boxes.ptr;
+                    match (boxes.display_list.clone(), boxes.range) {
+                        (Some(display_list), Some(range)) => {
+                            for i in range.eachi() {
+                                box_accumulator.push(display_list.get().list[i].bounds());
                             }
-                            _ => {
-                                for child in node.children() {
-                                    boxes = boxes_for_node(child, boxes);
-                                }
+                        }
+                        _ => {
+                            for child in node.children() {
+                                box_accumulator = boxes_for_node(child, box_accumulator);
                             }
                         }
-                        boxes
                     }
+                    box_accumulator
                 }
 
                 let mut boxes = ~[];
diff --git a/src/components/main/layout/util.rs b/src/components/main/layout/util.rs
index cf6d38ee7a0..eba5270489b 100644
--- a/src/components/main/layout/util.rs
+++ b/src/components/main/layout/util.rs
@@ -3,12 +3,34 @@
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 use layout::box::{RenderBox, RenderBoxUtils};
+
+use extra::arc::Arc;
+use gfx::display_list::DisplayList;
 use script::dom::node::{AbstractNode, LayoutView};
 use servo_util::range::Range;
-
+use servo_util::slot::Slot;
+use servo_util::tree::TreeNodeRef;
+use std::any::AnyRefExt;
 use std::iter::Enumerate;
 use std::vec::VecIterator;
+use style::{ComputedValues, PropertyDeclaration};
+
+/// The boxes associated with a node.
+pub struct DisplayBoxes {
+    display_list: Option<Arc<DisplayList<AbstractNode<()>>>>,
+    range: Option<Range>,
+}
 
+impl DisplayBoxes {
+    pub fn init() -> DisplayBoxes {
+        DisplayBoxes {
+            display_list: None,
+            range: None,
+        }
+    }
+}
+
+/// A range of nodes.
 pub struct NodeRange {
     node: AbstractNode<LayoutView>,
     range: Range,
@@ -16,7 +38,10 @@ pub struct NodeRange {
 
 impl NodeRange {
     pub fn new(node: AbstractNode<LayoutView>, range: &Range) -> NodeRange {
-        NodeRange { node: node, range: (*range).clone() }
+        NodeRange {
+            node: node,
+            range: (*range).clone()
+        }
     }
 }
 
@@ -111,3 +136,51 @@ impl ElementMapping {
         debug!("----------------------------------");
     }
 }
+
+/// Data that layout associates with a node.
+pub struct LayoutData {
+    /// The results of CSS matching for this node.
+    applicable_declarations: Slot<~[Arc<~[PropertyDeclaration]>]>,
+
+    /// The results of CSS styling for this node.
+    style: Slot<Option<ComputedValues>>,
+
+    /// Description of how to account for recent style changes.
+    restyle_damage: Slot<Option<int>>,
+
+    /// The boxes assosiated with this flow.
+    /// Used for getBoundingClientRect and friends.
+    boxes: Slot<DisplayBoxes>,
+}
+
+impl LayoutData {
+    /// Creates new layout data.
+    pub fn new() -> LayoutData {
+        LayoutData {
+            applicable_declarations: Slot::init(~[]),
+            style: Slot::init(None),
+            restyle_damage: Slot::init(None),
+            boxes: Slot::init(DisplayBoxes::init()),
+        }
+    }
+}
+
+// This serves as a static assertion that layout data remains sendable. If this is not done, then
+// we can have memory unsafety, which usually manifests as shutdown crashes.
+fn assert_is_sendable<T:Send>(_: T) {}
+fn assert_layout_data_is_sendable() {
+    assert_is_sendable(LayoutData::new())
+}
+
+/// A trait that allows access to the layout data of a DOM node.
+pub trait LayoutDataAccess {
+    fn layout_data<'a>(&'a self) -> &'a LayoutData;
+}
+
+impl LayoutDataAccess for AbstractNode<LayoutView> {
+    #[inline(always)]
+    fn layout_data<'a>(&'a self) -> &'a LayoutData {
+        self.node().layout_data.as_ref().unwrap().as_ref().unwrap()
+    }
+}
+
diff --git a/src/components/script/dom/node.rs b/src/components/script/dom/node.rs
index c6ce48ed395..f08c91c817b 100644
--- a/src/components/script/dom/node.rs
+++ b/src/components/script/dom/node.rs
@@ -21,12 +21,8 @@ use dom::text::Text;
 use std::cast;
 use std::cast::transmute;
 use std::unstable::raw::Box;
-use extra::arc::Arc;
 use js::jsapi::{JSObject, JSContext};
-use style::{ComputedValues, PropertyDeclaration};
 use servo_util::tree::{TreeNode, TreeNodeRef, TreeNodeRefAsElement};
-use servo_util::range::Range;
-use gfx::display_list::DisplayList;
 
 //
 // The basic Node structure
@@ -93,7 +89,7 @@ pub struct Node<View> {
     child_list: Option<@mut NodeList>,
 
     /// Layout information. Only the layout task may touch this data.
-    priv layout_data: LayoutData,
+    layout_data: Option<~Any>,
 }
 
 /// The different types of nodes.
@@ -543,7 +539,7 @@ impl Node<ScriptView> {
             owner_doc: doc,
             child_list: None,
 
-            layout_data: LayoutData::new(),
+            layout_data: None,
         }
     }
 }
@@ -1092,62 +1088,41 @@ impl Reflectable for Node<ScriptView> {
     }
 }
 
-// This stuff is notionally private to layout, but we put it here because it needs
-// to be stored in a Node, and we can't have cross-crate cyclic dependencies.
+/// A bottom-up, parallelizable traversal.
+pub trait PostorderNodeTraversal {
+    /// The operation to perform. Return true to continue or false to stop.
+    fn process(&mut self, node: AbstractNode<LayoutView>) -> bool;
 
-pub struct DisplayBoxes {
-    display_list: Option<Arc<DisplayList<AbstractNode<()>>>>,
-    range: Option<Range>,
-}
-
-/// Data that layout associates with a node.
-pub struct LayoutData {
-    /// The results of CSS matching for this node.
-    applicable_declarations: ~[Arc<~[PropertyDeclaration]>],
-
-    /// The results of CSS styling for this node.
-    style: Option<ComputedValues>,
-
-    /// Description of how to account for recent style changes.
-    restyle_damage: Option<int>,
-
-    /// The boxes assosiated with this flow.
-    /// Used for getBoundingClientRect and friends.
-    boxes: DisplayBoxes,
-}
-
-impl LayoutData {
-    /// Creates new layout data.
-    pub fn new() -> LayoutData {
-        LayoutData {
-            applicable_declarations: ~[],
-            style: None,
-            restyle_damage: None,
-            boxes: DisplayBoxes {
-                display_list: None,
-                range: None,
-            },
-        }
+    /// Returns true if this node should be pruned. If this returns true, we skip the operation
+    /// entirely and do not process any descendant nodes. This is called *before* child nodes are
+    /// visited. The default implementation never prunes any nodes.
+    fn should_prune(&mut self, _node: AbstractNode<LayoutView>) -> bool {
+        false
     }
 }
 
-// This serves as a static assertion that layout data remains sendable. If this is not done, then
-// we can have memory unsafety, which usually manifests as shutdown crashes.
-fn assert_is_sendable<T:Send>(_: T) {}
-fn assert_layout_data_is_sendable() {
-    assert_is_sendable(LayoutData::new())
-}
-
 impl AbstractNode<LayoutView> {
-    // These accessors take a continuation rather than returning a reference, because
-    // an AbstractNode doesn't have a lifetime parameter relating to the underlying
-    // Node.  Also this makes it easier to switch to RWArc if we decide that is
-    // necessary.
-    pub fn read_layout_data<R>(self, blk: &fn(data: &LayoutData) -> R) -> R {
-        blk(&self.node().layout_data)
-    }
+    /// Traverses the tree in postorder.
+    ///
+    /// TODO(pcwalton): Offer a parallel version with a compatible API.
+    pub fn traverse_postorder<T:PostorderNodeTraversal>(self, traversal: &mut T) -> bool {
+        if traversal.should_prune(self) {
+            return true
+        }
+
+        let mut opt_kid = self.first_child();
+        loop {
+            match opt_kid {
+                None => break,
+                Some(kid) => {
+                    if !kid.traverse_postorder(traversal) {
+                        return false
+                    }
+                    opt_kid = kid.next_sibling()
+                }
+            }
+        }
 
-    pub fn write_layout_data<R>(self, blk: &fn(data: &mut LayoutData) -> R) -> R {
-        blk(&mut self.mut_node().layout_data)
+        traversal.process(self)
     }
 }
diff --git a/src/components/script/script.rc b/src/components/script/script.rc
index 8c24cc5a995..a2dee9a6943 100644
--- a/src/components/script/script.rc
+++ b/src/components/script/script.rc
@@ -14,7 +14,6 @@
 #[feature(globs, macro_rules, struct_variant, managed_boxes)];
 
 extern mod geom;
-extern mod gfx (name = "gfx");
 extern mod hubbub;
 extern mod js;
 extern mod servo_net (name = "net");