auto merge of #1605 : pcwalton/servo/harden-layout-more, r=metajack

Closes #1584.

r? @metajack

8 files changed, 317 insertions, 226 deletions

diff --git a/src/components/main/css/node_style.rs b/src/components/main/css/node_style.rs
index f9b561425bb..beceacf3255 100644
--- a/src/components/main/css/node_style.rs
+++ b/src/components/main/css/node_style.rs
@@ -6,7 +6,7 @@
 
 use css::node_util::NodeUtil;
 use layout::incremental::RestyleDamage;
-use layout::wrapper::LayoutNode;
+use layout::wrapper::ThreadSafeLayoutNode;
 
 use extra::arc::Arc;
 use style::ComputedValues;
@@ -17,7 +17,7 @@ pub trait StyledNode {
     fn restyle_damage(&self) -> RestyleDamage;
 }
 
-impl<'ln> StyledNode for LayoutNode<'ln> {
+impl<'ln> StyledNode for ThreadSafeLayoutNode<'ln> {
     #[inline]
     fn style<'a>(&'a self) -> &'a Arc<ComputedValues> {
         self.get_css_select_results()
@@ -27,3 +27,4 @@ impl<'ln> StyledNode for LayoutNode<'ln> {
         self.get_restyle_damage()
     }
 }
+
diff --git a/src/components/main/css/node_util.rs b/src/components/main/css/node_util.rs
index 3a2b83ccab3..7493281d5cc 100644
--- a/src/components/main/css/node_util.rs
+++ b/src/components/main/css/node_util.rs
@@ -4,11 +4,11 @@
 
 use layout::incremental::RestyleDamage;
 use layout::util::LayoutDataAccess;
-use layout::wrapper::LayoutNode;
+use layout::wrapper::{TLayoutNode, ThreadSafeLayoutNode};
 
 use extra::arc::Arc;
 use std::cast;
-use style::{ComputedValues, TNode};
+use style::ComputedValues;
 
 pub trait NodeUtil {
     fn get_css_select_results<'a>(&'a self) -> &'a Arc<ComputedValues>;
@@ -18,17 +18,20 @@ pub trait NodeUtil {
     fn set_restyle_damage(self, damage: RestyleDamage);
 }
 
-impl<'ln> NodeUtil for LayoutNode<'ln> {
-    /** 
-     * Provides the computed style for the given node. If CSS selector
-     * Returns the style results for the given node. If CSS selector
-     * matching has not yet been performed, fails.
-     */
+impl<'ln> NodeUtil for ThreadSafeLayoutNode<'ln> {
+    /// Returns the style results for the given node. If CSS selector
+    /// matching has not yet been performed, fails.
     #[inline]
     fn get_css_select_results<'a>(&'a self) -> &'a Arc<ComputedValues> {
         unsafe {
             let layout_data_ref = self.borrow_layout_data();
-            cast::transmute_region(layout_data_ref.get().as_ref().unwrap().data.style.as_ref().unwrap())
+            cast::transmute_region(layout_data_ref.get()
+                                                  .as_ref()
+                                                  .unwrap()
+                                                  .data
+                                                  .style
+                                                  .as_ref()
+                                                  .unwrap())
         }
     }
 
@@ -43,7 +46,7 @@ impl<'ln> NodeUtil for LayoutNode<'ln> {
     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() {
+        let default = if self.node_is_element() {
             RestyleDamage::all()
         } else {
             RestyleDamage::none()
diff --git a/src/components/main/layout/box_.rs b/src/components/main/layout/box_.rs
index 807f950faf9..7604c95e5b5 100644
--- a/src/components/main/layout/box_.rs
+++ b/src/components/main/layout/box_.rs
@@ -40,7 +40,7 @@ use layout::flow::{Flow, FlowFlagsInfo};
 use layout::flow;
 use layout::model::{MaybeAuto, specified, Auto, Specified};
 use layout::util::OpaqueNode;
-use layout::wrapper::LayoutNode;
+use layout::wrapper::{TLayoutNode, ThreadSafeLayoutNode};
 
 /// Boxes (`struct Box`) are the leaves of the layout tree. They cannot position themselves. In
 /// general, boxes do not have a simple correspondence with CSS boxes in the specification:
@@ -123,10 +123,11 @@ impl ImageBoxInfo {
     ///
     /// FIXME(pcwalton): The fact that image boxes store the cache in the box makes little sense to
     /// me.
-    pub fn new(node: &LayoutNode, image_url: Url, local_image_cache: MutexArc<LocalImageCache>)
+    pub fn new(node: &ThreadSafeLayoutNode,
+               image_url: Url,
+               local_image_cache: MutexArc<LocalImageCache>)
                -> ImageBoxInfo {
-
-        fn convert_length(node: &LayoutNode, name: &str) -> Option<Au> {
+        fn convert_length(node: &ThreadSafeLayoutNode, name: &str) -> Option<Au> {
             node.with_element(|element| {
                 element.get_attr(&namespace::Null, name).and_then(|string| {
                     let n: Option<int> = FromStr::from_str(string);
@@ -207,7 +208,7 @@ pub struct IframeBoxInfo {
 
 impl IframeBoxInfo {
     /// Creates the information specific to an iframe box.
-    pub fn new(node: &LayoutNode) -> IframeBoxInfo {
+    pub fn new(node: &ThreadSafeLayoutNode) -> IframeBoxInfo {
         let (pipeline_id, subpage_id) = node.iframe_pipeline_and_subpage_ids();
         IframeBoxInfo {
             pipeline_id: pipeline_id,
@@ -249,7 +250,7 @@ pub struct UnscannedTextBoxInfo {
 
 impl UnscannedTextBoxInfo {
     /// Creates a new instance of `UnscannedTextBoxInfo` from the given DOM node.
-    pub fn new(node: &LayoutNode) -> UnscannedTextBoxInfo {
+    pub fn new(node: &ThreadSafeLayoutNode) -> UnscannedTextBoxInfo {
         // FIXME(pcwalton): Don't copy text; atomically reference count it instead.
         UnscannedTextBoxInfo {
             text: node.text(),
@@ -297,9 +298,9 @@ pub struct InlineParentInfo {
 
 impl Box {
     /// Constructs a new `Box` instance.
-    pub fn new(node: LayoutNode, specific: SpecificBoxInfo) -> Box {
+    pub fn new(node: ThreadSafeLayoutNode, specific: SpecificBoxInfo) -> Box {
         Box {
-            node: OpaqueNode::from_layout_node(&node),
+            node: OpaqueNode::from_thread_safe_layout_node(&node),
             style: node.style().clone(),
             position: RefCell::new(Au::zero_rect()),
             border: RefCell::new(Zero::zero()),
diff --git a/src/components/main/layout/construct.rs b/src/components/main/layout/construct.rs
index 1cb7b419c3d..b5f9cf21046 100644
--- a/src/components/main/layout/construct.rs
+++ b/src/components/main/layout/construct.rs
@@ -30,7 +30,7 @@ use layout::flow::{BaseFlow, Flow, FlowLeafSet, ImmutableFlowUtils, MutableOwned
 use layout::inline::InlineFlow;
 use layout::text::TextRunScanner;
 use layout::util::{LayoutDataAccess, OpaqueNode};
-use layout::wrapper::{LayoutNode, PostorderNodeMutTraversal};
+use layout::wrapper::{PostorderNodeMutTraversal, TLayoutNode, ThreadSafeLayoutNode};
 
 use gfx::font_context::FontContext;
 use script::dom::element::{HTMLIframeElementTypeId, HTMLImageElementTypeId};
@@ -234,7 +234,7 @@ impl<'fc> FlowConstructor<'fc> {
     }
 
     /// Builds the `ImageBoxInfo` for the given image. This is out of line to guide inlining.
-    fn build_box_info_for_image(&mut self, node: LayoutNode) -> Option<ImageBoxInfo> {
+    fn build_box_info_for_image(&mut self, node: ThreadSafeLayoutNode) -> Option<ImageBoxInfo> {
         // FIXME(pcwalton): Don't copy URLs.
         match node.image_url() {
             None => None,
@@ -247,7 +247,7 @@ impl<'fc> FlowConstructor<'fc> {
     }
 
     /// Builds a `Box` for the given node.
-    fn build_box_for_node(&mut self, node: LayoutNode) -> Box {
+    fn build_box_for_node(&mut self, node: ThreadSafeLayoutNode) -> Box {
         let specific = match node.type_id() {
             ElementNodeTypeId(HTMLImageElementTypeId) => {
                 match self.build_box_info_for_image(node) {
@@ -267,7 +267,10 @@ impl<'fc> FlowConstructor<'fc> {
     /// `#[inline(always)]` because this is performance critical and LLVM will not inline it
     /// otherwise.
     #[inline(always)]
-    fn flush_inline_boxes_to_flow(&mut self, boxes: ~[Box], flow: &mut ~Flow, node: LayoutNode) {
+    fn flush_inline_boxes_to_flow(&mut self,
+                                  boxes: ~[Box],
+                                  flow: &mut ~Flow,
+                                  node: ThreadSafeLayoutNode) {
         if boxes.len() == 0 {
             return
         }
@@ -285,7 +288,7 @@ impl<'fc> FlowConstructor<'fc> {
     fn flush_inline_boxes_to_flow_if_necessary(&mut self,
                                                opt_boxes: &mut Option<~[Box]>,
                                                flow: &mut ~Flow,
-                                               node: LayoutNode) {
+                                               node: ThreadSafeLayoutNode) {
         let opt_boxes = util::replace(opt_boxes, None);
         if opt_boxes.len() > 0 {
             self.flush_inline_boxes_to_flow(opt_boxes.to_vec(), flow, node)
@@ -295,9 +298,7 @@ impl<'fc> FlowConstructor<'fc> {
     /// Builds the children flows underneath a node with `display: block`. After this call,
     /// other `BlockFlow`s or `InlineFlow`s will be populated underneath this node, depending on
     /// whether {ib} splits needed to happen.
-    fn build_children_of_block_flow(&mut self,
-                                    flow: &mut ~Flow,
-                                    node: LayoutNode) {
+    fn build_children_of_block_flow(&mut self, flow: &mut ~Flow, node: ThreadSafeLayoutNode) {
         // Gather up boxes for the inline flows we might need to create.
         let mut opt_boxes_for_inline_flow = None;
         let mut first_box = true;
@@ -389,7 +390,7 @@ impl<'fc> FlowConstructor<'fc> {
     /// Builds a flow for a node with `display: block`. This yields a `BlockFlow` with possibly
     /// other `BlockFlow`s or `InlineFlow`s underneath it, depending on whether {ib} splits needed
     /// to happen.
-    fn build_flow_for_block(&mut self, node: LayoutNode, is_fixed: bool) -> ~Flow {
+    fn build_flow_for_block(&mut self, node: ThreadSafeLayoutNode, is_fixed: bool) -> ~Flow {
         let base = BaseFlow::new(self.next_flow_id(), node);
         let box_ = self.build_box_for_node(node);
         let mut flow = ~BlockFlow::from_box(base, box_, is_fixed) as ~Flow;
@@ -399,7 +400,7 @@ impl<'fc> FlowConstructor<'fc> {
 
     /// Builds the flow for a node with `float: {left|right}`. This yields a float `BlockFlow` with
     /// a `BlockFlow` underneath it.
-    fn build_flow_for_floated_block(&mut self, node: LayoutNode, float_type: FloatType)
+    fn build_flow_for_floated_block(&mut self, node: ThreadSafeLayoutNode, float_type: FloatType)
                                     -> ~Flow {
         let base = BaseFlow::new(self.next_flow_id(), node);
         let box_ = self.build_box_for_node(node);
@@ -413,7 +414,7 @@ impl<'fc> FlowConstructor<'fc> {
     /// Concatenates the boxes of kids, adding in our own borders/padding/margins if necessary.
     /// Returns the `InlineBoxesConstructionResult`, if any. There will be no
     /// `InlineBoxesConstructionResult` if this node consisted entirely of ignorable whitespace.
-    fn build_boxes_for_nonreplaced_inline_content(&mut self, node: LayoutNode)
+    fn build_boxes_for_nonreplaced_inline_content(&mut self, node: ThreadSafeLayoutNode)
                                                   -> ConstructionResult {
         let mut opt_inline_block_splits = None;
         let mut opt_box_accumulator = None;
@@ -519,7 +520,9 @@ impl<'fc> FlowConstructor<'fc> {
         }
     }
 
-    fn set_inline_info_for_inline_child(&mut self, boxes: &~[&Box], parent_node: LayoutNode) {
+    fn set_inline_info_for_inline_child(&mut self,
+                                        boxes: &~[&Box],
+                                        parent_node: ThreadSafeLayoutNode) {
         let parent_box = self.build_box_for_node(parent_node);
         let font_style = parent_box.font_style();
         let font_group = self.font_context.get_resolved_font_for_style(&font_style);
@@ -557,7 +560,7 @@ impl<'fc> FlowConstructor<'fc> {
                             style: parent_box.style.clone(),
                             font_ascent: font_ascent,
                             font_descent: font_descent,
-                            node: OpaqueNode::from_layout_node(&parent_node),
+                            node: OpaqueNode::from_thread_safe_layout_node(&parent_node),
                         });
                 },
                 &None => {}
@@ -566,7 +569,8 @@ impl<'fc> FlowConstructor<'fc> {
     }
     /// Creates an `InlineBoxesConstructionResult` for replaced content. Replaced content doesn't
     /// render its children, so this just nukes a child's boxes and creates a `Box`.
-    fn build_boxes_for_replaced_inline_content(&mut self, node: LayoutNode) -> ConstructionResult {
+    fn build_boxes_for_replaced_inline_content(&mut self, node: ThreadSafeLayoutNode)
+                                               -> ConstructionResult {
         for kid in node.children() {
             kid.set_flow_construction_result(NoConstructionResult)
         }
@@ -582,7 +586,7 @@ impl<'fc> FlowConstructor<'fc> {
 
     /// Builds one or more boxes for a node with `display: inline`. This yields an
     /// `InlineBoxesConstructionResult`.
-    fn build_boxes_for_inline(&mut self, node: LayoutNode) -> ConstructionResult {
+    fn build_boxes_for_inline(&mut self, node: ThreadSafeLayoutNode) -> ConstructionResult {
         // Is this node replaced content?
         if !node.is_replaced_content() {
             // Go to a path that concatenates our kids' boxes.
@@ -598,7 +602,7 @@ impl<'a> PostorderNodeMutTraversal for FlowConstructor<'a> {
     // `#[inline(always)]` because this is always called from the traversal function and for some
     // reason LLVM's inlining heuristics go awry here.
     #[inline(always)]
-    fn process(&mut self, node: LayoutNode) -> bool {
+    fn process(&mut self, node: ThreadSafeLayoutNode) -> bool {
         // Get the `display` property for this node, and determine whether this node is floated.
         let (display, float, position) = match node.type_id() {
             ElementNodeTypeId(_) => {
@@ -671,7 +675,7 @@ trait NodeUtils {
     fn swap_out_construction_result(self) -> ConstructionResult;
 }
 
-impl<'ln> NodeUtils for LayoutNode<'ln> {
+impl<'ln> NodeUtils for ThreadSafeLayoutNode<'ln> {
     fn is_replaced_content(self) -> bool {
         match self.type_id() {
             TextNodeTypeId |
diff --git a/src/components/main/layout/flow.rs b/src/components/main/layout/flow.rs
index 2373a47df87..9abd29ab934 100644
--- a/src/components/main/layout/flow.rs
+++ b/src/components/main/layout/flow.rs
@@ -35,7 +35,7 @@ use layout::incremental::RestyleDamage;
 use layout::inline::InlineFlow;
 use layout::parallel::{FlowParallelInfo, UnsafeFlow};
 use layout::parallel;
-use layout::wrapper::LayoutNode;
+use layout::wrapper::ThreadSafeLayoutNode;
 
 use extra::dlist::{DList, DListIterator, MutDListIterator};
 use extra::container::Deque;
@@ -553,7 +553,7 @@ impl Iterator<@Box> for BoxIterator {
 
 impl BaseFlow {
     #[inline]
-    pub fn new(id: int, node: LayoutNode) -> BaseFlow {
+    pub fn new(id: int, node: ThreadSafeLayoutNode) -> BaseFlow {
         let style = node.style();
         BaseFlow {
             restyle_damage: node.restyle_damage(),
diff --git a/src/components/main/layout/layout_task.rs b/src/components/main/layout/layout_task.rs
index 468ef2297b1..f5572208218 100644
--- a/src/components/main/layout/layout_task.rs
+++ b/src/components/main/layout/layout_task.rs
@@ -19,7 +19,7 @@ use layout::parallel::{AssignHeightsAndStoreOverflowTraversalKind, BubbleWidthsT
 use layout::parallel::{UnsafeFlow};
 use layout::parallel;
 use layout::util::{LayoutDataAccess, OpaqueNode, LayoutDataWrapper};
-use layout::wrapper::{DomLeafSet, LayoutNode};
+use layout::wrapper::{DomLeafSet, LayoutNode, TLayoutNode, ThreadSafeLayoutNode};
 
 use extra::arc::{Arc, MutexArc};
 use geom::rect::Rect;
@@ -416,6 +416,7 @@ impl LayoutTask {
     /// marked `#[inline(never)]` to aid benchmarking in sampling profilers.
     #[inline(never)]
     fn construct_flow_tree(&self, layout_context: &mut LayoutContext, node: LayoutNode) -> ~Flow {
+        let node = ThreadSafeLayoutNode::new(node);
         node.traverse_postorder_mut(&mut FlowConstructor::init(layout_context));
 
         let mut layout_data_ref = node.mutate_layout_data();
@@ -623,13 +624,16 @@ impl LayoutTask {
                 for child in node.traverse_preorder() {
                     if child.type_id() == ElementNodeTypeId(HTMLHtmlElementTypeId) || 
                             child.type_id() == ElementNodeTypeId(HTMLBodyElementTypeId) {
-                        let element_bg_color = child.style()
-                                                    .get()
-                                                    .resolve_color(child.style()
-                                                                        .get()
-                                                                        .Background
-                                                                        .background_color)
-                                                    .to_gfx_color();
+                        let element_bg_color = {
+                            let thread_safe_child = ThreadSafeLayoutNode::new(child);
+                            thread_safe_child.style()
+                                             .get()
+                                             .resolve_color(thread_safe_child.style()
+                                                                             .get()
+                                                                             .Background
+                                                                             .background_color)
+                                             .to_gfx_color()
+                        };
                         match element_bg_color {
                             color::rgba(0., 0., 0., 0.) => {}
                             _ => {
diff --git a/src/components/main/layout/util.rs b/src/components/main/layout/util.rs
index e93cc0674ae..08596646f55 100644
--- a/src/components/main/layout/util.rs
+++ b/src/components/main/layout/util.rs
@@ -5,7 +5,7 @@
 use layout::box_::Box;
 use layout::construct::{ConstructionResult, NoConstructionResult};
 use layout::parallel::DomParallelInfo;
-use layout::wrapper::LayoutNode;
+use layout::wrapper::{LayoutNode, TLayoutNode, ThreadSafeLayoutNode};
 
 use extra::arc::Arc;
 use script::dom::bindings::utils::Reflectable;
@@ -227,6 +227,15 @@ impl OpaqueNode {
         }
     }
 
+    /// Converts a thread-safe DOM node (layout view) to an `OpaqueNode`.
+    pub fn from_thread_safe_layout_node(node: &ThreadSafeLayoutNode) -> OpaqueNode {
+        unsafe {
+            let abstract_node = node.get_abstract();
+            let ptr: uintptr_t = cast::transmute(abstract_node.reflector().get_jsobject());
+            OpaqueNode(ptr)
+        }
+    }
+
     /// Converts a DOM node (script view) to an `OpaqueNode`.
     pub fn from_script_node(node: &AbstractNode) -> OpaqueNode {
         unsafe {
diff --git a/src/components/main/layout/wrapper.rs b/src/components/main/layout/wrapper.rs
index b9863b3db5f..f1af40c8888 100644
--- a/src/components/main/layout/wrapper.rs
+++ b/src/components/main/layout/wrapper.rs
@@ -26,88 +26,48 @@ use servo_util::concurrentmap::{ConcurrentHashMap, ConcurrentHashMapIterator};
 use servo_util::namespace;
 use servo_util::namespace::Namespace;
 use std::cast;
+use std::cell::{Ref, RefMut};
 use style::{PropertyDeclarationBlock, TElement, TNode, AttrSelector};
 
-/// A wrapper so that layout can access only the methods that it should have access to. Layout must
-/// only ever see these and must never see instances of `AbstractNode`.
-#[deriving(Clone, Eq)]
-pub struct LayoutNode<'a> {
-    /// The wrapped node.
-    priv node: AbstractNode,
-
-    /// Being chained to a value prevents `LayoutNode`s from escaping.
-    priv chain: &'a (),
-}
-
-impl<'ln> LayoutNode<'ln> {
-    /// Creates a new layout node, scoped to the given closure.
-    pub unsafe fn with_layout_node<R>(node: AbstractNode, f: <'a> |LayoutNode<'a>| -> R) -> R {
-        let heavy_iron_ball = ();
-        f(LayoutNode {
-            node: node,
-            chain: &heavy_iron_ball,
-        })
-    }
+use layout::util::LayoutDataWrapper;
 
+/// Allows some convenience methods on generic layout nodes.
+pub trait TLayoutNode {
     /// Creates a new layout node with the same lifetime as this layout node.
-    unsafe fn new_with_this_lifetime(&self, node: AbstractNode) -> LayoutNode<'ln> {
-        LayoutNode {
-            node: node,
-            chain: self.chain,
-        }
-    }
+    unsafe fn new_with_this_lifetime(&self, node: AbstractNode) -> Self;
 
-    /// Returns the interior of this node as a `Node`. This is highly unsafe for layout to call
-    /// and as such is marked `unsafe`.
-    pub unsafe fn get<'a>(&'a self) -> &'a Node {
-        cast::transmute(self.node.node())
-    }
+    /// Returns the type ID of this node. Fails if this node is borrowed mutably.
+    fn type_id(&self) -> NodeTypeId;
 
     /// Returns the interior of this node as an `AbstractNode`. This is highly unsafe for layout to
     /// call and as such is marked `unsafe`.
-    pub unsafe fn get_abstract(&self) -> AbstractNode {
-        self.node
-    }
+    unsafe fn get_abstract(&self) -> AbstractNode;
 
-    /// Returns the first child of this node.
-    pub fn first_child(&self) -> Option<LayoutNode<'ln>> {
-        unsafe {
-            self.node.first_child().map(|node| self.new_with_this_lifetime(node))
-        }
+    /// Returns the interior of this node as a `Node`. This is highly unsafe for layout to call
+    /// and as such is marked `unsafe`.
+    unsafe fn get<'a>(&'a self) -> &'a Node {
+        let node = self.get_abstract();
+        cast::transmute(node.node())
     }
 
-    /// Returns the first child of this node.
-    pub fn last_child(&self) -> Option<LayoutNode<'ln>> {
-        unsafe {
-            self.node.last_child().map(|node| self.new_with_this_lifetime(node))
+    fn node_is_element(&self) -> bool {
+        match self.type_id() {
+            ElementNodeTypeId(..) => true,
+            _ => false
         }
     }
 
-    /// Iterates over this node and all its descendants, in preorder.
-    ///
-    /// FIXME(pcwalton): Terribly inefficient. We should use parallelism.
-    pub fn traverse_preorder(&self) -> LayoutTreeIterator<'ln> {
-        let mut nodes = ~[];
-        gather_layout_nodes(self, &mut nodes, false);
-        LayoutTreeIterator::new(nodes)
-    }
-
-    /// Returns an iterator over this node's children.
-    pub fn children(&self) -> LayoutNodeChildrenIterator<'ln> {
-        LayoutNodeChildrenIterator {
-            current_node: self.first_child(),
+    fn node_is_document(&self) -> bool {
+        match self.type_id() {
+            DocumentNodeTypeId(..) => true,
+            _ => false
         }
     }
 
-    /// Returns the type ID of this node. Fails if this node is borrowed mutably.
-    pub fn type_id(&self) -> NodeTypeId {
-        self.node.type_id()
-    }
-
     /// If this is an image element, returns its URL. If this is not an image element, fails.
     ///
     /// FIXME(pcwalton): Don't copy URLs.
-    pub fn image_url(&self) -> Option<Url> {
+    fn image_url(&self) -> Option<Url> {
         unsafe {
             self.with_image_element(|image_element| {
                 image_element.image.as_ref().map(|url| (*url).clone())
@@ -115,19 +75,29 @@ impl<'ln> LayoutNode<'ln> {
         }
     }
 
+    /// Downcasts this node to an iframe element and calls the given closure.
+    ///
+    /// FIXME(pcwalton): RAII.
+    unsafe fn with_iframe_element<R>(&self, f: |&HTMLIFrameElement| -> R) -> R {
+        if !self.get_abstract().is_iframe_element() {
+            fail!(~"node is not an iframe element");
+        }
+        self.get_abstract().transmute(f)
+    }
+
     /// Downcasts this node to an image element and calls the given closure.
     ///
     /// FIXME(pcwalton): RAII.
-    unsafe fn with_image_element<R>(self, f: |&HTMLImageElement| -> R) -> R {
-        if !self.node.is_image_element() {
+    unsafe fn with_image_element<R>(&self, f: |&HTMLImageElement| -> R) -> R {
+        if !self.get_abstract().is_image_element() {
             fail!(~"node is not an image element");
         }
-        self.node.transmute(f)
+        self.get_abstract().transmute(f)
     }
 
     /// If this node is an iframe element, returns its pipeline and subpage IDs. If this node is
     /// not an iframe element, fails.
-    pub fn iframe_pipeline_and_subpage_ids(&self) -> (PipelineId, SubpageId) {
+    fn iframe_pipeline_and_subpage_ids(&self) -> (PipelineId, SubpageId) {
         unsafe {
             self.with_iframe_element(|iframe_element| {
                 let size = iframe_element.size.unwrap();
@@ -136,34 +106,10 @@ impl<'ln> LayoutNode<'ln> {
         }
     }
 
-    /// Downcasts this node to an iframe element and calls the given closure.
-    ///
-    /// FIXME(pcwalton): RAII.
-    unsafe fn with_iframe_element<R>(self, f: |&HTMLIFrameElement| -> R) -> R {
-        if !self.node.is_iframe_element() {
-            fail!(~"node is not an iframe element");
-        }
-        self.node.transmute(f)
-    }
-
-    /// Returns true if this node is a text node or false otherwise.
-    #[inline]
-    pub fn is_text(self) -> bool {
-        self.node.is_text()
-    }
-
-    /// Returns true if this node consists entirely of ignorable whitespace and false otherwise.
-    /// Ignorable whitespace is defined as whitespace that would be removed per CSS 2.1 § 16.6.1.
-    pub fn is_ignorable_whitespace(&self) -> bool {
-        unsafe {
-            self.is_text() && self.with_text(|text| text.element.data.is_whitespace())
-        }
-    }
-
     /// If this is a text node, copies out the text. If this is not a text node, fails.
     ///
     /// FIXME(pcwalton): Don't copy text. Atomically reference count instead.
-    pub fn text(&self) -> ~str {
+    fn text(&self) -> ~str {
         unsafe {
             self.with_text(|text| text.element.data.to_str())
         }
@@ -172,67 +118,75 @@ impl<'ln> LayoutNode<'ln> {
     /// Downcasts this node to a text node and calls the given closure.
     ///
     /// FIXME(pcwalton): RAII.
-    unsafe fn with_text<R>(self, f: |&Text| -> R) -> R {
-        self.node.with_imm_text(f)
+    unsafe fn with_text<R>(&self, f: |&Text| -> R) -> R {
+        self.get_abstract().with_imm_text(f)
     }
 
-    /// Dumps this node tree, for debugging.
-    pub fn dump(&self) {
-        self.node.dump()
+    /// Returns the first child of this node.
+    fn first_child(&self) -> Option<Self> {
+        unsafe {
+            self.get_abstract().first_child().map(|node| self.new_with_this_lifetime(node))
+        }
     }
 
-    /// Returns a string that describes this node, for debugging.
-    pub fn debug_str(&self) -> ~str {
-        self.node.debug_str()
+    /// Dumps this node tree, for debugging.
+    fn dump(&self) {
+        unsafe {
+            self.get_abstract().dump()
+        }
     }
+}
 
-    /// Traverses the tree in postorder.
-    ///
-    /// TODO(pcwalton): Offer a parallel version with a compatible API.
-    pub fn traverse_postorder<T:PostorderNodeTraversal>(self, traversal: &T) -> bool {
-        if traversal.should_prune(self) {
-            return true
-        }
+/// A wrapper so that layout can access only the methods that it should have access to. Layout must
+/// only ever see these and must never see instances of `AbstractNode`.
+#[deriving(Clone, Eq)]
+pub struct LayoutNode<'a> {
+    /// The wrapped node.
+    priv node: AbstractNode,
 
-        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()
-                }
-            }
+    /// Being chained to a value prevents `LayoutNode`s from escaping.
+    priv chain: &'a (),
+}
+
+impl<'ln> TLayoutNode for LayoutNode<'ln> {
+    unsafe fn new_with_this_lifetime(&self, node: AbstractNode) -> LayoutNode<'ln> {
+        LayoutNode {
+            node: node,
+            chain: self.chain,
         }
+    }
+    fn type_id(&self) -> NodeTypeId {
+        self.node.type_id()
+    }
+    unsafe fn get_abstract(&self) -> AbstractNode {
+        self.node
+    }
+}
 
-        traversal.process(self)
+impl<'ln> LayoutNode<'ln> {
+    /// Creates a new layout node, scoped to the given closure.
+    pub unsafe fn with_layout_node<R>(node: AbstractNode, f: <'a> |LayoutNode<'a>| -> R) -> R {
+        let heavy_iron_ball = ();
+        f(LayoutNode {
+            node: node,
+            chain: &heavy_iron_ball,
+        })
     }
 
-    /// Traverses the tree in postorder.
+    /// Iterates over this node and all its descendants, in preorder.
     ///
-    /// TODO(pcwalton): Offer a parallel version with a compatible API.
-    pub fn traverse_postorder_mut<T:PostorderNodeMutTraversal>(mut self, traversal: &mut T)
-                                  -> bool {
-        if traversal.should_prune(self) {
-            return true
-        }
+    /// FIXME(pcwalton): Terribly inefficient. We should use parallelism.
+    pub fn traverse_preorder(&self) -> LayoutTreeIterator<'ln> {
+        let mut nodes = ~[];
+        gather_layout_nodes(self, &mut nodes, false);
+        LayoutTreeIterator::new(nodes)
+    }
 
-        let mut opt_kid = self.first_child();
-        loop {
-            match opt_kid {
-                None => break,
-                Some(kid) => {
-                    if !kid.traverse_postorder_mut(traversal) {
-                        return false
-                    }
-                    opt_kid = kid.next_sibling()
-                }
-            }
+    /// Returns an iterator over this node's children.
+    pub fn children(&self) -> LayoutNodeChildrenIterator<'ln> {
+        LayoutNodeChildrenIterator {
+            current_node: self.first_child(),
         }
-
-        traversal.process(self)
     }
 }
 
@@ -255,20 +209,6 @@ impl<'ln> TNode<LayoutElement<'ln>> for LayoutNode<'ln> {
         }
     }
 
-    fn is_element(&self) -> bool {
-        match self.node.type_id() {
-            ElementNodeTypeId(..) => true,
-            _ => false
-        }
-    }
-
-    fn is_document(&self) -> bool {
-        match self.node.type_id() {
-            DocumentNodeTypeId(..) => true,
-            _ => false
-        }
-    }
-
     /// If this is an element, accesses the element data. Fails if this is not an element node.
     #[inline]
     fn with_element<R>(&self, f: |&LayoutElement<'ln>| -> R) -> R {
@@ -283,6 +223,14 @@ impl<'ln> TNode<LayoutElement<'ln>> for LayoutNode<'ln> {
         })
     }
 
+    fn is_element(&self) -> bool {
+        self.node_is_element()
+    }
+
+    fn is_document(&self) -> bool {
+        self.node_is_document()
+    }
+
     fn match_attr(&self, attr: &AttrSelector, test: |&str| -> bool) -> bool {
         self.with_element(|element| {
             let name = if element.element.html_element_in_html_document() {
@@ -361,32 +309,6 @@ fn gather_layout_nodes<'a>(cur: &LayoutNode<'a>, refs: &mut ~[LayoutNode<'a>], p
     }
 }
 
-/// A bottom-up, parallelizable traversal.
-pub trait PostorderNodeTraversal {
-    /// The operation to perform. Return true to continue or false to stop.
-    fn process<'a>(&'a self, node: LayoutNode<'a>) -> bool;
-
-    /// 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<'a>(&'a self, _node: LayoutNode<'a>) -> bool {
-        false
-    }
-}
-
-/// A bottom-up, parallelizable traversal.
-pub trait PostorderNodeMutTraversal {
-    /// The operation to perform. Return true to continue or false to stop.
-    fn process<'a>(&'a mut self, node: LayoutNode<'a>) -> bool;
-
-    /// 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<'a>(&'a self, _node: LayoutNode<'a>) -> bool {
-        false
-    }
-}
-
 /// A wrapper around elements that ensures layout can only ever access safe properties.
 pub struct LayoutElement<'le> {
     priv element: &'le Element,
@@ -429,6 +351,153 @@ impl<'le> TElement for LayoutElement<'le> {
     }
 }
 
+/// A thread-safe version of `LayoutNode`, used during flow construction. This type of layout
+/// node does not allow any parents or siblings of nodes to be accessed, to avoid races.
+pub struct ThreadSafeLayoutNode<'ln> {
+    /// The wrapped node.
+    priv node: AbstractNode,
+
+    /// Being chained to a value prevents `ThreadSafeLayoutNode`s from escaping.
+    priv chain: &'ln (),
+}
+
+impl<'ln> TLayoutNode for ThreadSafeLayoutNode<'ln> {
+    /// Creates a new layout node with the same lifetime as this layout node.
+    unsafe fn new_with_this_lifetime(&self, node: AbstractNode) -> ThreadSafeLayoutNode<'ln> {
+        ThreadSafeLayoutNode {
+            node: node,
+            chain: self.chain,
+        }
+    }
+    fn type_id(&self) -> NodeTypeId {
+        self.node.type_id()
+    }
+    unsafe fn get_abstract(&self) -> AbstractNode {
+        self.node
+    }
+}
+
+impl<'ln> ThreadSafeLayoutNode<'ln> {
+    /// Creates a new `ThreadSafeLayoutNode` from the given `LayoutNode`.
+    pub fn new<'a>(node: LayoutNode<'a>) -> ThreadSafeLayoutNode<'a> {
+        ThreadSafeLayoutNode {
+            node: node.node,
+            chain: node.chain,
+        }
+    }
+
+    /// Returns the next sibling of this node. Unsafe and private because this can lead to races.
+    unsafe fn next_sibling(&self) -> Option<ThreadSafeLayoutNode<'ln>> {
+        self.node.node().next_sibling.map(|node| self.new_with_this_lifetime(node))
+    }
+
+    /// Returns an iterator over this node's children.
+    pub fn children(&self) -> ThreadSafeLayoutNodeChildrenIterator<'ln> {
+        ThreadSafeLayoutNodeChildrenIterator {
+            current_node: self.first_child(),
+        }
+    }
+
+    /// If this is an element, accesses the element data. Fails if this is not an element node.
+    #[inline]
+    pub fn with_element<R>(&self, f: |&ThreadSafeLayoutElement| -> R) -> R {
+        unsafe {
+            self.get_abstract().with_imm_element(|element| {
+                // FIXME(pcwalton): Workaround until Rust gets multiple lifetime parameters on
+                // implementations.
+                f(&ThreadSafeLayoutElement {
+                    element: cast::transmute_region(element),
+                })
+            })
+        }
+    }
+
+    /// Borrows the layout data immutably. Fails on a conflicting borrow.
+    #[inline(always)]
+    pub fn borrow_layout_data<'a>(&'a self) -> Ref<'a,Option<LayoutDataWrapper>> {
+        unsafe {
+            cast::transmute(self.get().layout_data.borrow())
+        }
+    }
+
+    /// Borrows the layout data mutably. Fails on a conflicting borrow.
+    #[inline(always)]
+    pub fn mutate_layout_data<'a>(&'a self) -> RefMut<'a,Option<LayoutDataWrapper>> {
+        unsafe {
+            cast::transmute(self.get().layout_data.borrow_mut())
+        }
+    }
+
+    /// Traverses the tree in postorder.
+    ///
+    /// TODO(pcwalton): Offer a parallel version with a compatible API.
+    pub fn traverse_postorder_mut<T:PostorderNodeMutTraversal>(mut 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_mut(traversal) {
+                        return false
+                    }
+                    unsafe {
+                        opt_kid = kid.next_sibling()
+                    }
+                }
+            }
+        }
+
+        traversal.process(self)
+    }
+}
+
+pub struct ThreadSafeLayoutNodeChildrenIterator<'a> {
+    priv current_node: Option<ThreadSafeLayoutNode<'a>>,
+}
+
+impl<'a> Iterator<ThreadSafeLayoutNode<'a>> for ThreadSafeLayoutNodeChildrenIterator<'a> {
+    fn next(&mut self) -> Option<ThreadSafeLayoutNode<'a>> {
+        let node = self.current_node;
+        self.current_node = self.current_node.and_then(|node| {
+            unsafe {
+                node.next_sibling()
+            }
+        });
+        node
+    }
+}
+
+/// A wrapper around elements that ensures layout can only ever access safe properties and cannot
+/// race on elements.
+pub struct ThreadSafeLayoutElement<'le> {
+    priv element: &'le Element,
+}
+
+impl<'le> ThreadSafeLayoutElement<'le> {
+    #[inline]
+    pub fn get_attr(&self, namespace: &Namespace, name: &str) -> Option<&'static str> {
+        unsafe { self.element.get_attr_val_for_layout(namespace, name) }
+    }
+}
+
+/// A bottom-up, parallelizable traversal.
+pub trait PostorderNodeMutTraversal {
+    /// The operation to perform. Return true to continue or false to stop.
+    fn process<'a>(&'a mut self, node: ThreadSafeLayoutNode<'a>) -> bool;
+
+    /// 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<'a>(&'a self, _node: ThreadSafeLayoutNode<'a>) -> bool {
+        false
+    }
+}
+
 pub type UnsafeLayoutNode = (uint, uint);
 
 pub fn layout_node_to_unsafe_layout_node(node: &LayoutNode) -> UnsafeLayoutNode {