Rewrite flow construction to be incrementalizable and parallelizable.

This replaces flow construction with a strict bottom-up tree traversal,
allowing for parallelism. Each step of the traversal creates a flow or
a `ConstructionItem`, similar to how Gecko works. {ib} splits are
handled by not creating `InlineFlow`s until the containing block is
reached.

This should be able to be incrementalized by storing the `Flow` from
layout to layout, and performing fixups during flow construction
and/or wiping containing blocks in a previous pass.

2 files changed, 140 insertions, 22 deletions

diff --git a/src/components/script/dom/bindings/utils.rs b/src/components/script/dom/bindings/utils.rs
index f79e8ae633a..b076810785a 100644
--- a/src/components/script/dom/bindings/utils.rs
+++ b/src/components/script/dom/bindings/utils.rs
@@ -863,26 +863,38 @@ pub fn CreateDOMGlobal(cx: *JSContext, class: *JSClass) -> *JSObject {
     }
 }
 
+/// Returns the global object of the realm that the given JS object was created in.
 #[fixed_stack_segment]
-fn cx_for_dom_reflector(obj: *JSObject) -> *JSContext {
+fn global_object_for_js_object(obj: *JSObject) -> *Box<window::Window> {
     unsafe {
         let global = GetGlobalForObjectCrossCompartment(obj);
         let clasp = JS_GetClass(global);
         assert!(((*clasp).flags & (JSCLASS_IS_DOMJSCLASS | JSCLASS_IS_GLOBAL)) != 0);
-        //XXXjdm either don't hardcode or sanity assert prototype stuff
-        let win = unwrap_object::<*Box<window::Window>>(global, PrototypeList::id::Window, 1);
-        match win {
-            Ok(win) => {
-                match (*win).data.page.js_info {
-                    Some(ref info) => info.js_context.ptr,
-                    None => fail!("no JS context for DOM global")
-                }
-            }
-            Err(_) => fail!("found DOM global that doesn't unwrap to Window")
+        // FIXME(jdm): Either don't hardcode or sanity assert prototype stuff.
+        match unwrap_object::<*Box<window::Window>>(global, PrototypeList::id::Window, 1) {
+            Ok(win) => win,
+            Err(_) => fail!("found DOM global that doesn't unwrap to Window"),
         }
     }
 }
 
+#[fixed_stack_segment]
+fn cx_for_dom_reflector(obj: *JSObject) -> *JSContext {
+    unsafe {
+        let win = global_object_for_js_object(obj);
+        match (*win).data.page.js_info {
+            Some(ref info) => info.js_context.ptr,
+            None => fail!("no JS context for DOM global")
+        }
+    }
+}
+
+/// Returns the global object of the realm that the given DOM object was created in.
+#[fixed_stack_segment]
+pub fn global_object_for_dom_object<T: Reflectable>(obj: &mut T) -> *Box<window::Window> {
+    global_object_for_js_object(obj.reflector().get_jsobject())
+}
+
 pub fn cx_for_dom_object<T: Reflectable>(obj: &mut T) -> *JSContext {
     cx_for_dom_reflector(obj.reflector().get_jsobject())
 }
diff --git a/src/components/script/dom/node.rs b/src/components/script/dom/node.rs
index 78533b2b48c..9709680300d 100644
--- a/src/components/script/dom/node.rs
+++ b/src/components/script/dom/node.rs
@@ -7,6 +7,7 @@
 use dom::bindings::utils::{Reflectable, Reflector, reflect_dom_object};
 use dom::bindings::utils::{DOMString, null_str_as_empty};
 use dom::bindings::utils::{ErrorResult, Fallible, NotFound, HierarchyRequest};
+use dom::bindings::utils;
 use dom::characterdata::CharacterData;
 use dom::document::{AbstractDocument, DocumentTypeId};
 use dom::documenttype::DocumentType;
@@ -18,11 +19,13 @@ use dom::htmlimageelement::HTMLImageElement;
 use dom::htmliframeelement::HTMLIFrameElement;
 use dom::text::Text;
 
-use std::cast;
-use std::cast::transmute;
-use std::unstable::raw::Box;
 use js::jsapi::{JSObject, JSContext};
+use servo_util::slot::{MutSlotRef, Slot, SlotRef};
 use servo_util::tree::{TreeNode, TreeNodeRef, TreeNodeRefAsElement};
+use std::cast::transmute;
+use std::cast;
+use std::unstable::raw::Box;
+use std::util;
 
 //
 // The basic Node structure
@@ -89,9 +92,87 @@ pub struct Node<View> {
     child_list: Option<@mut NodeList>,
 
     /// Layout information. Only the layout task may touch this data.
-    layout_data: Option<~Any>,
+    ///
+    /// FIXME(pcwalton): We need to send these back to the layout task to be destroyed when this
+    /// node is finalized.
+    layout_data: LayoutDataRef,
+}
+
+#[unsafe_destructor]
+impl<T> Drop for Node<T> {
+    fn drop(&mut self) {
+        unsafe {
+            let this: &mut Node<ScriptView> = cast::transmute(self);
+            this.reap_layout_data()
+        }
+    }
+}
+
+/// Encapsulates the abstract layout data.
+pub struct LayoutDataRef {
+    priv data: Slot<Option<*()>>,
+}
+
+impl LayoutDataRef {
+    #[inline]
+    pub fn init() -> LayoutDataRef {
+        LayoutDataRef {
+            data: Slot::init(None),
+        }
+    }
+
+    /// Creates a new piece of layout data from a value.
+    #[inline]
+    pub unsafe fn from_data<T>(data: ~T) -> LayoutDataRef {
+        LayoutDataRef {
+            data: Slot::init(Some(cast::transmute(data))),
+        }
+    }
+
+    /// Returns true if this layout data is present or false otherwise.
+    #[inline]
+    pub fn is_present(&self) -> bool {
+        self.data.get().is_some()
+    }
+
+    /// Borrows the layout data immutably, *asserting that there are no mutators*. Bad things will
+    /// happen if you try to mutate the layout data while this is held. This is the only thread-
+    /// safe layout data accessor.
+    ///
+    /// FIXME(pcwalton): Enforce this invariant via the type system. Will require traversal
+    /// functions to be trusted, but c'est la vie.
+    #[inline]
+    pub unsafe fn borrow_unchecked<'a>(&'a self) -> &'a () {
+        cast::transmute(self.data.borrow_unchecked())
+    }
+
+    /// Borrows the layout data immutably. This function is *not* thread-safe.
+    #[inline]
+    pub fn borrow<'a>(&'a self) -> SlotRef<'a,()> {
+        unsafe {
+            cast::transmute(self.data.borrow())
+        }
+    }
+
+    /// Borrows the layout data mutably. This function is *not* thread-safe.
+    ///
+    /// FIXME(pcwalton): We should really put this behind a `MutLayoutView` phantom type, to
+    /// prevent CSS selector matching from mutably accessing nodes it's not supposed to and racing
+    /// on it. This has already resulted in one bug!
+    #[inline]
+    pub fn mutate<'a>(&'a self) -> MutSlotRef<'a,()> {
+        unsafe {
+            cast::transmute(self.data.mutate())
+        }
+    }
 }
 
+/// A trait that represents abstract layout data.
+/// 
+/// FIXME(pcwalton): Very very unsafe!!! We need to send these back to the layout task to be
+/// destroyed when this node is finalized.
+pub trait TLayoutData {}
+
 /// The different types of nodes.
 #[deriving(Eq)]
 pub enum NodeTypeId {
@@ -319,12 +400,24 @@ impl<'self, View> AbstractNode<View> {
         self.transmute_mut(f)
     }
 
+    #[inline]
     pub fn is_comment(self) -> bool {
-        self.type_id() == CommentNodeTypeId
+        // FIXME(pcwalton): Temporary workaround for the lack of inlining of autogenerated `Eq`
+        // implementations in Rust.
+        match self.type_id() {
+            CommentNodeTypeId => true,
+            _ => false,
+        }
     }
 
+    #[inline]
     pub fn is_text(self) -> bool {
-        self.type_id() == TextNodeTypeId
+        // FIXME(pcwalton): Temporary workaround for the lack of inlining of autogenerated `Eq`
+        // implementations in Rust.
+        match self.type_id() {
+            TextNodeTypeId => true,
+            _ => false,
+        }
     }
 
     pub fn with_imm_text<R>(self, f: &fn(&Text) -> R) -> R {
@@ -364,8 +457,12 @@ impl<'self, View> AbstractNode<View> {
         self.transmute_mut(f)
     }
 
+    #[inline]
     pub fn is_image_element(self) -> bool {
-        self.type_id() == ElementNodeTypeId(HTMLImageElementTypeId)
+        match self.type_id() {
+            ElementNodeTypeId(HTMLImageElementTypeId) => true,
+            _ => false,
+        }
     }
 
     pub fn with_imm_image_element<R>(self, f: &fn(&HTMLImageElement) -> R) -> R {
@@ -543,7 +640,16 @@ impl Node<ScriptView> {
             owner_doc: doc,
             child_list: None,
 
-            layout_data: None,
+            layout_data: LayoutDataRef::init(),
+        }
+    }
+
+    /// Sends layout data, if any, back to the script task to be destroyed.
+    pub unsafe fn reap_layout_data(&mut self) {
+        if self.layout_data.is_present() {
+            let layout_data = util::replace(&mut self.layout_data, LayoutDataRef::init());
+            let js_window = utils::global_object_for_dom_object(self);
+            (*js_window).data.page.reap_dead_layout_data(layout_data)
         }
     }
 }
@@ -1095,12 +1201,12 @@ impl Reflectable for Node<ScriptView> {
 /// 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;
+    fn process(&self, node: AbstractNode<LayoutView>) -> 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(&mut self, _node: AbstractNode<LayoutView>) -> bool {
+    fn should_prune(&self, _node: AbstractNode<LayoutView>) -> bool {
         false
     }
 }
@@ -1109,7 +1215,7 @@ impl AbstractNode<LayoutView> {
     /// 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 {
+    pub fn traverse_postorder<T:PostorderNodeTraversal>(self, traversal: &T) -> bool {
         if traversal.should_prune(self) {
             return true
         }