layout: Introduce a DOM leaf set as a prerequisite for parallel flow

construction.

This will be very slow until we have the concurrent hash table, but we
might as well get it in.

7 files changed, 125 insertions, 50 deletions

diff --git a/src/components/main/layout/construct.rs b/src/components/main/layout/construct.rs
index dbb0f9d9b5b..cbd03bb50c2 100644
--- a/src/components/main/layout/construct.rs
+++ b/src/components/main/layout/construct.rs
@@ -26,7 +26,7 @@ use layout::box_::{Box, GenericBox, IframeBox, IframeBoxInfo, ImageBox, ImageBox
 use layout::box_::{UnscannedTextBox, UnscannedTextBoxInfo, InlineInfo, InlineParentInfo};
 use layout::context::LayoutContext;
 use layout::float_context::FloatType;
-use layout::flow::{BaseFlow, Flow, ImmutableFlowUtils, LeafSet, MutableOwnedFlowUtils};
+use layout::flow::{BaseFlow, Flow, FlowLeafSet, ImmutableFlowUtils, MutableOwnedFlowUtils};
 use layout::inline::InlineFlow;
 use layout::text::TextRunScanner;
 use layout::util::{LayoutDataAccess, OpaqueNode};
@@ -58,7 +58,7 @@ pub enum ConstructionResult {
 }
 
 impl ConstructionResult {
-    fn destroy(&mut self, leaf_set: &mut LeafSet) {
+    fn destroy(&mut self, leaf_set: &mut FlowLeafSet) {
         match *self {
             NoConstructionResult => {}
             FlowConstructionResult(ref mut flow) => flow.destroy(leaf_set),
@@ -76,7 +76,7 @@ enum ConstructionItem {
 }
 
 impl ConstructionItem {
-    fn destroy(&mut self, leaf_set: &mut LeafSet) {
+    fn destroy(&mut self, leaf_set: &mut FlowLeafSet) {
         match *self {
             InlineBoxesConstructionItem(ref mut result) => {
                 for splits in result.splits.mut_iter() {
@@ -133,7 +133,7 @@ struct InlineBlockSplit {
 }
 
 impl InlineBlockSplit {
-    fn destroy(&mut self, leaf_set: &mut LeafSet) {
+    fn destroy(&mut self, leaf_set: &mut FlowLeafSet) {
         self.flow.destroy(leaf_set)
     }
 }
@@ -274,7 +274,7 @@ impl<'fc> FlowConstructor<'fc> {
 
         let inline_base = BaseFlow::new(self.next_flow_id(), node);
         let mut inline_flow = ~InlineFlow::from_boxes(inline_base, boxes) as ~Flow;
-        self.layout_context.leaf_set.access(|leaf_set| inline_flow.mark_as_leaf(leaf_set));
+        self.layout_context.flow_leaf_set.access(|leaf_set| inline_flow.mark_as_leaf(leaf_set));
         TextRunScanner::new().scan_for_runs(self.font_context, inline_flow);
 
         flow.add_new_child(inline_flow)
@@ -380,7 +380,7 @@ impl<'fc> FlowConstructor<'fc> {
 
         // The flow is done. If it ended up with no kids, add the flow to the leaf set.
         if flow.child_count() == 0 {
-            self.layout_context.leaf_set.access(|leaf_set| flow.mark_as_leaf(leaf_set))
+            self.layout_context.flow_leaf_set.access(|leaf_set| flow.mark_as_leaf(leaf_set))
         } else {
             flow.mark_as_nonleaf()
         }
@@ -619,7 +619,7 @@ impl<'a> PostorderNodeMutTraversal for FlowConstructor<'a> {
             // `display: none` contributes no flow construction result. Nuke the flow construction
             // results of children.
             (display::none, _, _) => {
-                self.layout_context.leaf_set.access(|leaf_set| {
+                self.layout_context.flow_leaf_set.access(|leaf_set| {
                     for child in node.children() {
                         let mut old_result = child.swap_out_construction_result();
                         old_result.destroy(leaf_set)
diff --git a/src/components/main/layout/context.rs b/src/components/main/layout/context.rs
index 93613a54a19..801b474c824 100644
--- a/src/components/main/layout/context.rs
+++ b/src/components/main/layout/context.rs
@@ -6,8 +6,9 @@
 
 use extra::arc::MutexArc;
 use green::task::GreenTask;
-use layout::flow::LeafSet;
+use layout::flow::FlowLeafSet;
 use layout::util::OpaqueNode;
+use layout::wrapper::DomLeafSet;
 use std::cast;
 use std::ptr;
 use std::rt::Runtime;
@@ -36,8 +37,11 @@ pub struct LayoutContext {
     /// A channel up to the constellation.
     constellation_chan: ConstellationChan,
 
+    /// The set of leaf DOM nodes.
+    dom_leaf_set: MutexArc<DomLeafSet>,
+
     /// The set of leaf flows.
-    leaf_set: MutexArc<LeafSet>,
+    flow_leaf_set: MutexArc<FlowLeafSet>,
 
     /// Information needed to construct a font context.
     font_context_info: FontContextInfo,
diff --git a/src/components/main/layout/flow.rs b/src/components/main/layout/flow.rs
index 56d81fc78ea..d47743fa897 100644
--- a/src/components/main/layout/flow.rs
+++ b/src/components/main/layout/flow.rs
@@ -216,13 +216,13 @@ pub trait MutableOwnedFlowUtils {
 
     /// Marks the flow as a leaf. The flow must not have children and must not be marked as a
     /// nonleaf.
-    fn mark_as_leaf(&mut self, leaf_set: &mut LeafSet);
+    fn mark_as_leaf(&mut self, leaf_set: &mut FlowLeafSet);
 
     /// Marks the flow as a nonleaf. The flow must not be marked as a leaf.
     fn mark_as_nonleaf(&mut self);
 
     /// Destroys the flow.
-    fn destroy(&mut self, leaf_set: &mut LeafSet);
+    fn destroy(&mut self, leaf_set: &mut FlowLeafSet);
 }
 
 pub enum FlowClass {
@@ -756,7 +756,7 @@ impl MutableOwnedFlowUtils for ~Flow {
 
     /// Marks the flow as a leaf. The flow must not have children and must not be marked as a
     /// nonleaf.
-    fn mark_as_leaf(&mut self, leaf_set: &mut LeafSet) {
+    fn mark_as_leaf(&mut self, leaf_set: &mut FlowLeafSet) {
         {
             let base = mut_base(*self);
             if base.flags_info.flags.is_nonleaf() {
@@ -781,7 +781,7 @@ impl MutableOwnedFlowUtils for ~Flow {
     }
 
     /// Destroys the flow.
-    fn destroy(&mut self, leaf_set: &mut LeafSet) {
+    fn destroy(&mut self, leaf_set: &mut FlowLeafSet) {
         let is_leaf = {
             let base = mut_base(*self);
             base.children.len() == 0
@@ -803,14 +803,14 @@ impl MutableOwnedFlowUtils for ~Flow {
 /// Keeps track of the leaves of the flow tree. This is used to efficiently start bottom-up
 /// parallel traversals.
 #[deriving(Clone)]
-pub struct LeafSet {
+pub struct FlowLeafSet {
     priv set: HashSet<UnsafeFlow>,
 }
 
-impl LeafSet {
-    /// Creates a new leaf set.
-    pub fn new() -> LeafSet {
-        LeafSet {
+impl FlowLeafSet {
+    /// Creates a new flow leaf set.
+    pub fn new() -> FlowLeafSet {
+        FlowLeafSet {
             set: HashSet::new(),
         }
     }
diff --git a/src/components/main/layout/layout_task.rs b/src/components/main/layout/layout_task.rs
index 12b2c9af7ed..c8b9c435f14 100644
--- a/src/components/main/layout/layout_task.rs
+++ b/src/components/main/layout/layout_task.rs
@@ -12,7 +12,7 @@ use layout::construct::{FlowConstructionResult, FlowConstructor, NoConstructionR
 use layout::context::LayoutContext;
 use layout::display_list_builder::{DisplayListBuilder, ToGfxColor};
 use layout::extra::LayoutAuxMethods;
-use layout::flow::{Flow, ImmutableFlowUtils, LeafSet, MutableFlowUtils, MutableOwnedFlowUtils};
+use layout::flow::{Flow, FlowLeafSet, ImmutableFlowUtils, MutableFlowUtils, MutableOwnedFlowUtils};
 use layout::flow::{PreorderFlowTraversal, PostorderFlowTraversal};
 use layout::flow;
 use layout::incremental::RestyleDamage;
@@ -20,7 +20,7 @@ use layout::parallel::{AssignHeightsAndStoreOverflowTraversalKind, BubbleWidthsT
 use layout::parallel::{UnsafeFlow};
 use layout::parallel;
 use layout::util::{LayoutDataAccess, OpaqueNode, LayoutDataWrapper};
-use layout::wrapper::LayoutNode;
+use layout::wrapper::{DomLeafSet, LayoutNode};
 
 use extra::arc::{Arc, MutexArc};
 use geom::rect::Rect;
@@ -82,8 +82,11 @@ pub struct LayoutTask {
     /// The local image cache.
     local_image_cache: MutexArc<LocalImageCache>,
 
+    /// The set of leaves in the DOM tree.
+    dom_leaf_set: MutexArc<DomLeafSet>,
+
     /// The set of leaves in the flow tree.
-    leaf_set: MutexArc<LeafSet>,
+    flow_leaf_set: MutexArc<FlowLeafSet>,
 
     /// The size of the viewport.
     screen_size: Size2D<Au>,
@@ -289,7 +292,8 @@ impl LayoutTask {
             image_cache_task: image_cache_task.clone(),
             local_image_cache: local_image_cache,
             screen_size: screen_size,
-            leaf_set: MutexArc::new(LeafSet::new()),
+            dom_leaf_set: MutexArc::new(DomLeafSet::new()),
+            flow_leaf_set: MutexArc::new(FlowLeafSet::new()),
 
             display_list: None,
             stylist: ~new_stylist(),
@@ -318,7 +322,8 @@ impl LayoutTask {
             image_cache: self.local_image_cache.clone(),
             screen_size: self.screen_size.clone(),
             constellation_chan: self.constellation_chan.clone(),
-            leaf_set: self.leaf_set.clone(),
+            dom_leaf_set: self.dom_leaf_set.clone(),
+            flow_leaf_set: self.flow_leaf_set.clone(),
             font_context_info: font_context_info,
             stylist: &*self.stylist,
             reflow_root: OpaqueNode::from_layout_node(reflow_root),
@@ -470,7 +475,7 @@ impl LayoutTask {
             None => fail!("solve_contraints_parallel() called with no parallel traversal ready"),
             Some(ref mut traversal) => {
                 parallel::traverse_flow_tree(BubbleWidthsTraversalKind,
-                                             &self.leaf_set,
+                                             &self.flow_leaf_set,
                                              self.profiler_chan.clone(),
                                              layout_context,
                                              traversal);
@@ -482,7 +487,7 @@ impl LayoutTask {
                 layout_root.traverse_preorder(&mut AssignWidthsTraversal(layout_context));
 
                 parallel::traverse_flow_tree(AssignHeightsAndStoreOverflowTraversalKind,
-                                             &self.leaf_set,
+                                             &self.flow_leaf_set,
                                              self.profiler_chan.clone(),
                                              layout_context,
                                              traversal);
@@ -657,7 +662,7 @@ impl LayoutTask {
             });
         }
 
-        self.leaf_set.access(|leaf_set| layout_root.destroy(leaf_set));
+        self.flow_leaf_set.access(|leaf_set| layout_root.destroy(leaf_set));
 
         // Tell script that we're done.
         //
diff --git a/src/components/main/layout/parallel.rs b/src/components/main/layout/parallel.rs
index fa93708053b..674c4a5e423 100644
--- a/src/components/main/layout/parallel.rs
+++ b/src/components/main/layout/parallel.rs
@@ -8,11 +8,11 @@
 
 use css::matching::MatchMethods;
 use layout::context::LayoutContext;
-use layout::flow::{Flow, LeafSet, PostorderFlowTraversal};
+use layout::flow::{Flow, FlowLeafSet, PostorderFlowTraversal};
 use layout::flow;
 use layout::layout_task::{AssignHeightsAndStoreOverflowTraversal, BubbleWidthsTraversal};
-use layout::util::OpaqueNode;
-use layout::wrapper::LayoutNode;
+use layout::util::{LayoutDataAccess, OpaqueNode};
+use layout::wrapper::{layout_node_to_unsafe_layout_node, LayoutNode, UnsafeLayoutNode};
 
 use extra::arc::MutexArc;
 use servo_util::time::{ProfilerChan, profile};
@@ -46,11 +46,17 @@ pub fn mut_owned_flow_to_unsafe_flow(flow: *mut ~Flow) -> UnsafeFlow {
     }
 }
 
-pub type UnsafeLayoutNode = (uint, uint);
+/// Information that we need stored in each DOM node.
+pub struct DomParallelInfo {
+    /// The number of children that still need work done.
+    children_count: AtomicInt,
+}
 
-fn layout_node_to_unsafe_layout_node(node: &LayoutNode) -> UnsafeLayoutNode {
-    unsafe {
-        cast::transmute_copy(node)
+impl DomParallelInfo {
+    pub fn new() -> DomParallelInfo {
+        DomParallelInfo {
+            children_count: AtomicInt::new(0),
+        }
     }
 }
 
@@ -124,25 +130,42 @@ fn match_and_cascade_node(unsafe_layout_node: UnsafeLayoutNode,
         // Get a real layout node.
         let node: LayoutNode = cast::transmute(unsafe_layout_node);
 
-        // Perform the CSS selector matching.
-        let stylist: &Stylist = cast::transmute(layout_context.stylist);
-        node.match_node(stylist);
-
-        // Perform the CSS cascade.
-        let parent_opt = if OpaqueNode::from_layout_node(&node) == layout_context.reflow_root {
-            None
-        } else {
-            node.parent_node()
-        };
-        node.cascade_node(parent_opt);
+        if node.is_element() {
+            // Perform the CSS selector matching.
+            let stylist: &Stylist = cast::transmute(layout_context.stylist);
+            node.match_node(stylist);
+
+            // Perform the CSS cascade.
+            let parent_opt = if OpaqueNode::from_layout_node(&node) == layout_context.reflow_root {
+                None
+            } else {
+                node.parent_node()
+            };
+            node.cascade_node(parent_opt);
+        }
 
         // Enqueue kids.
+        let mut child_count = 0;
         for kid in node.children() {
-            if kid.is_element() {
-                proxy.push(WorkUnit {
-                    fun: match_and_cascade_node,
-                    data: layout_node_to_unsafe_layout_node(&kid),
-                });
+            child_count += 1;
+
+            proxy.push(WorkUnit {
+                fun: match_and_cascade_node,
+                data: layout_node_to_unsafe_layout_node(&kid),
+            });
+        }
+
+        // Prepare for flow construction by adding this node to the leaf set or counting its
+        // children.
+        if child_count == 0 {
+            layout_context.dom_leaf_set.access(|dom_leaf_set| dom_leaf_set.insert(&node));
+        } else {
+            let mut layout_data_ref = node.mutate_layout_data();
+            match *layout_data_ref.get() {
+                Some(ref mut layout_data) => {
+                    layout_data.data.parallel.children_count.store(child_count as int, Relaxed)
+                }
+                None => fail!("no layout data"),
             }
         }
     }
@@ -188,7 +211,7 @@ pub fn match_and_cascade_subtree(root_node: &LayoutNode,
 }
 
 pub fn traverse_flow_tree(kind: TraversalKind,
-                          leaf_set: &MutexArc<LeafSet>,
+                          leaf_set: &MutexArc<FlowLeafSet>,
                           profiler_chan: ProfilerChan,
                           layout_context: &mut LayoutContext,
                           queue: &mut WorkQueue<*mut LayoutContext,UnsafeFlow>) {
diff --git a/src/components/main/layout/util.rs b/src/components/main/layout/util.rs
index 43853e67f80..f77e74fb10b 100644
--- a/src/components/main/layout/util.rs
+++ b/src/components/main/layout/util.rs
@@ -4,6 +4,7 @@
 
 use layout::box_::Box;
 use layout::construct::{ConstructionResult, NoConstructionResult};
+use layout::parallel::DomParallelInfo;
 use layout::wrapper::LayoutNode;
 
 use extra::arc::Arc;
@@ -148,6 +149,9 @@ pub struct PrivateLayoutData {
     /// The current results of flow construction for this node. This is either a flow or a
     /// `ConstructionItem`. See comments in `construct.rs` for more details.
     flow_construction_result: ConstructionResult,
+
+    /// Information needed during parallel traversals.
+    parallel: DomParallelInfo,
 }
 
 impl PrivateLayoutData {
@@ -162,6 +166,7 @@ impl PrivateLayoutData {
             after_style: None,
             restyle_damage: None,
             flow_construction_result: NoConstructionResult,
+            parallel: DomParallelInfo::new(),
         }
     }
 }
diff --git a/src/components/main/layout/wrapper.rs b/src/components/main/layout/wrapper.rs
index 75bc94e5b85..f6ebb1b2898 100644
--- a/src/components/main/layout/wrapper.rs
+++ b/src/components/main/layout/wrapper.rs
@@ -25,6 +25,7 @@ use servo_msg::constellation_msg::{PipelineId, SubpageId};
 use servo_util::namespace;
 use servo_util::namespace::Namespace;
 use std::cast;
+use std::hashmap::{HashMap, HashMapIterator};
 use style::{PropertyDeclarationBlock, TElement, TNode, AttrSelector};
 
 /// A wrapper so that layout can access only the methods that it should have access to. Layout must
@@ -428,3 +429,40 @@ impl<'le> TElement for LayoutElement<'le> {
     }
 }
 
+pub type UnsafeLayoutNode = (uint, uint);
+
+pub fn layout_node_to_unsafe_layout_node(node: &LayoutNode) -> UnsafeLayoutNode {
+    unsafe {
+        cast::transmute_copy(node)
+    }
+}
+
+/// Keeps track of the leaves of the DOM. This is used to efficiently start bottom-up traversals.
+pub struct DomLeafSet {
+    priv set: HashMap<UnsafeLayoutNode,()>,
+}
+
+impl DomLeafSet {
+    /// Creates a new DOM leaf set.
+    pub fn new() -> DomLeafSet {
+        DomLeafSet {
+            set: HashMap::new(),
+        }
+    }
+
+    /// Inserts a DOM node into the leaf set.
+    pub fn insert(&mut self, node: &LayoutNode) {
+        self.set.insert(layout_node_to_unsafe_layout_node(node), ());
+    }
+
+    /// Removes all DOM nodes from the set.
+    pub fn clear(&mut self) {
+        self.set.clear()
+    }
+
+    /// Iterates over the DOM nodes in the leaf set.
+    pub fn iter<'a>(&'a self) -> HashMapIterator<'a,UnsafeLayoutNode,()> {
+        self.set.iter()
+    }
+}
+