layout: Use the new `append_from` method to get rid of a bunch of moves

in display list construction.

These were showing up in the profile.

4 files changed, 96 insertions, 99 deletions

diff --git a/components/gfx/display_list/mod.rs b/components/gfx/display_list/mod.rs
index d219ab26cca..16b40d0b7d9 100644
--- a/components/gfx/display_list/mod.rs
+++ b/components/gfx/display_list/mod.rs
@@ -19,16 +19,16 @@ use render_context::RenderContext;
 use text::glyph::CharIndex;
 use text::TextRun;
 
-use collections::dlist::DList;
-use collections::dlist;
+use collections::Deque;
+use collections::dlist::{mod, DList};
 use geom::{Point2D, Rect, SideOffsets2D, Size2D, Matrix2D};
 use libc::uintptr_t;
 use servo_net::image::base::Image;
+use servo_util::dlist as servo_dlist;
 use servo_util::geometry::Au;
 use servo_util::opts;
 use servo_util::range::Range;
 use std::fmt;
-use std::mem;
 use std::slice::Items;
 use style::computed_values::border_style;
 use sync::Arc;
@@ -183,12 +183,8 @@ struct StackingContext {
 }
 
 impl StackingContext {
-    /// Creates a stacking context from a display list.
-    fn new(list: DisplayList) -> StackingContext {
-        let DisplayList {
-            list: list
-        } = list;
-
+    /// Creates a stacking context from a display list, consuming that display list in the process.
+    fn new(list: &mut DisplayList) -> StackingContext {
         let mut stacking_context = StackingContext {
             background_and_borders: DisplayList::new(),
             block_backgrounds_and_borders: DisplayList::new(),
@@ -197,30 +193,29 @@ impl StackingContext {
             positioned_descendants: Vec::new(),
         };
 
-        for item in list.into_iter() {
-            match item.base().level {
+        while !list.list.is_empty() {
+            let mut head = DisplayList::from_list(servo_dlist::split(&mut list.list));
+            match head.front().unwrap().base().level {
                 BackgroundAndBordersStackingLevel => {
-                    stacking_context.background_and_borders.push(item)
+                    stacking_context.background_and_borders.append_from(&mut head)
                 }
                 BlockBackgroundsAndBordersStackingLevel => {
-                    stacking_context.block_backgrounds_and_borders.push(item)
+                    stacking_context.block_backgrounds_and_borders.append_from(&mut head)
                 }
-                FloatStackingLevel => stacking_context.floats.push(item),
-                ContentStackingLevel => stacking_context.content.push(item),
+                FloatStackingLevel => stacking_context.floats.append_from(&mut head),
+                ContentStackingLevel => stacking_context.content.append_from(&mut head),
                 PositionedDescendantStackingLevel(z_index) => {
                     match stacking_context.positioned_descendants
                                           .iter_mut()
                                           .find(|& &(z, _)| z_index == z) {
                         Some(&(_, ref mut my_list)) => {
-                            my_list.push(item);
+                            my_list.append_from(&mut head);
                             continue
                         }
                         None => {}
                     }
 
-                    let mut new_list = DisplayList::new();
-                    new_list.list.push(item);
-                    stacking_context.positioned_descendants.push((z_index, new_list))
+                    stacking_context.positioned_descendants.push((z_index, head))
                 }
             }
         }
@@ -266,16 +261,29 @@ impl DisplayList {
         }
     }
 
+    /// Creates a new display list from the given list of display items.
+    fn from_list(list: DList<DisplayItem>) -> DisplayList {
+        DisplayList {
+            list: list,
+        }
+    }
+
     /// Appends the given item to the display list.
     #[inline]
     pub fn push(&mut self, item: DisplayItem) {
-        self.list.push(item)
+        self.list.push(item);
     }
 
-    /// Appends the given display list to this display list, consuming the other display list in
-    /// the process.
-    pub fn push_all_move(&mut self, other: DisplayList) {
-        self.list.append(other.list)
+    /// Appends the items in the given display list to this one, removing them in the process.
+    #[inline]
+    pub fn append_from(&mut self, other: &mut DisplayList) {
+        servo_dlist::append_from(&mut self.list, &mut other.list)
+    }
+
+    /// Returns the first display item in this list.
+    #[inline]
+    fn front(&self) -> Option<&DisplayItem> {
+        self.list.front()
     }
 
     pub fn debug(&self) {
@@ -309,20 +317,27 @@ impl DisplayList {
     /// steps in CSS 2.1 § E.2.
     ///
     /// This must be called before `draw_into_context()` is for correct results.
-    pub fn flatten(self, resulting_level: StackingLevel) -> DisplayList {
-        // TODO(pcwalton): Sort positioned children according to z-index.
+    pub fn flatten(&mut self, resulting_level: StackingLevel) {
+        // Fast paths:
+        if self.list.len() == 0 {
+            return
+        }
+        if self.list.len() == 1 {
+            self.set_stacking_level(resulting_level);
+            return
+        }
 
-        let mut result = DisplayList::new();
         let StackingContext {
-            background_and_borders,
-            block_backgrounds_and_borders,
-            floats,
-            content,
-            positioned_descendants: mut positioned_descendants
+            mut background_and_borders,
+            mut block_backgrounds_and_borders,
+            mut floats,
+            mut content,
+            mut positioned_descendants
         } = StackingContext::new(self);
+        debug_assert!(self.list.is_empty());
 
         // Steps 1 and 2: Borders and background for the root.
-        result.push_all_move(background_and_borders);
+        self.append_from(&mut background_and_borders);
 
         // Sort positioned children according to z-index.
         positioned_descendants.sort_by(|&(z_index_a, _), &(z_index_b, _)| {
@@ -332,32 +347,31 @@ impl DisplayList {
         // Step 3: Positioned descendants with negative z-indices.
         for &(ref mut z_index, ref mut list) in positioned_descendants.iter_mut() {
             if *z_index < 0 {
-                result.push_all_move(mem::replace(list, DisplayList::new()))
+                self.append_from(list)
             }
         }
 
         // Step 4: Block backgrounds and borders.
-        result.push_all_move(block_backgrounds_and_borders);
+        self.append_from(&mut block_backgrounds_and_borders);
 
         // Step 5: Floats.
-        result.push_all_move(floats);
+        self.append_from(&mut floats);
 
         // TODO(pcwalton): Step 6: Inlines that generate stacking contexts.
 
         // Step 7: Content.
-        result.push_all_move(content);
+        self.append_from(&mut content);
 
         // Steps 8 and 9: Positioned descendants with nonnegative z-indices.
         for &(ref mut z_index, ref mut list) in positioned_descendants.iter_mut() {
             if *z_index >= 0 {
-                result.push_all_move(mem::replace(list, DisplayList::new()))
+                self.append_from(list)
             }
         }
 
         // TODO(pcwalton): Step 10: Outlines.
 
-        result.set_stacking_level(resulting_level);
-        result
+        self.set_stacking_level(resulting_level);
     }
 
     /// Sets the stacking level for this display list and all its subitems.
diff --git a/components/layout/display_list_builder.rs b/components/layout/display_list_builder.rs
index 48d6f706fef..1bdfa00e95c 100644
--- a/components/layout/display_list_builder.rs
+++ b/components/layout/display_list_builder.rs
@@ -36,6 +36,7 @@ use gfx::render_task::RenderLayer;
 use servo_msg::compositor_msg::{FixedPosition, Scrollable};
 use servo_msg::constellation_msg::{ConstellationChan, FrameRectMsg};
 use servo_net::image::holder::ImageHolder;
+use servo_util::dlist;
 use servo_util::geometry::{mod, Au, ZERO_RECT};
 use servo_util::logical_geometry::{LogicalRect, WritingMode};
 use servo_util::opts;
@@ -117,12 +118,10 @@ impl FragmentDisplayListBuilding for Fragment {
         // doesn't have a fragment".
         let background_color = style.resolve_color(style.get_background().background_color);
         if !background_color.alpha.approx_eq(&0.0) {
-            let display_item = box SolidColorDisplayItem {
+            list.push(SolidColorDisplayItemClass(box SolidColorDisplayItem {
                 base: BaseDisplayItem::new(*absolute_bounds, self.node, level, *clip_rect),
                 color: background_color.to_gfx_color(),
-            };
-
-            list.push(SolidColorDisplayItemClass(display_item))
+            }));
         }
 
         // The background image is painted on top of the background color.
@@ -205,13 +204,12 @@ impl FragmentDisplayListBuilding for Fragment {
         };
 
         // Create the image display item.
-        let image_display_item = ImageDisplayItemClass(box ImageDisplayItem {
+        list.push(ImageDisplayItemClass(box ImageDisplayItem {
             base: BaseDisplayItem::new(bounds, self.node, level, clip_rect),
             image: image.clone(),
             stretch_size: Size2D(Au::from_px(image.width as int),
                                  Au::from_px(image.height as int)),
-        });
-        list.push(image_display_item)
+        }));
     }
 
     /// Adds the display items necessary to paint the borders of this fragment to a display list if
@@ -233,7 +231,7 @@ impl FragmentDisplayListBuilding for Fragment {
         let left_color = style.resolve_color(style.get_border().border_left_color);
 
         // Append the border to the display list.
-        let border_display_item = box BorderDisplayItem {
+        list.push(BorderDisplayItemClass(box BorderDisplayItem {
             base: BaseDisplayItem::new(*abs_bounds, self.node, level, *clip_rect),
             border: border.to_physical(style.writing_mode),
             color: SideOffsets2D::new(top_color.to_gfx_color(),
@@ -244,9 +242,7 @@ impl FragmentDisplayListBuilding for Fragment {
                                       style.get_border().border_right_style,
                                       style.get_border().border_bottom_style,
                                       style.get_border().border_left_style)
-        };
-
-        list.push(BorderDisplayItemClass(border_display_item))
+        }));
     }
 
     fn build_debug_borders_around_text_fragments(&self,
@@ -263,7 +259,7 @@ impl FragmentDisplayListBuilding for Fragment {
             fragment_bounds.size);
 
         // Compute the text fragment bounds and draw a border surrounding them.
-        let border_display_item = box BorderDisplayItem {
+        display_list.push(BorderDisplayItemClass(box BorderDisplayItem {
             base: BaseDisplayItem::new(absolute_fragment_bounds,
                                        self.node,
                                        ContentStackingLevel,
@@ -271,8 +267,7 @@ impl FragmentDisplayListBuilding for Fragment {
             border: SideOffsets2D::new_all_same(Au::from_px(1)),
             color: SideOffsets2D::new_all_same(color::rgb(0, 0, 200)),
             style: SideOffsets2D::new_all_same(border_style::solid)
-        };
-        display_list.push(BorderDisplayItemClass(border_display_item));
+        }));
 
         // Draw a rectangle representing the baselines.
         let ascent = text_fragment.run.ascent();
@@ -303,7 +298,7 @@ impl FragmentDisplayListBuilding for Fragment {
             fragment_bounds.size);
 
         // This prints a debug border around the border of this fragment.
-        let border_display_item = box BorderDisplayItem {
+        display_list.push(BorderDisplayItemClass(box BorderDisplayItem {
             base: BaseDisplayItem::new(absolute_fragment_bounds,
                                        self.node,
                                        ContentStackingLevel,
@@ -311,8 +306,7 @@ impl FragmentDisplayListBuilding for Fragment {
             border: SideOffsets2D::new_all_same(Au::from_px(1)),
             color: SideOffsets2D::new_all_same(color::rgb(0, 0, 200)),
             style: SideOffsets2D::new_all_same(border_style::solid)
-        };
-        display_list.push(BorderDisplayItemClass(border_display_item))
+        }));
     }
 
     fn build_display_list(&mut self,
@@ -442,7 +436,7 @@ impl FragmentDisplayListBuilding for Fragment {
                     tmp.to_physical(self.style.writing_mode, container_size) + flow_origin
                 };
 
-                let text_display_item = box TextDisplayItem {
+                display_list.push(TextDisplayItemClass(box TextDisplayItem {
                     base: BaseDisplayItem::new(absolute_content_box,
                                                self.node,
                                                ContentStackingLevel,
@@ -452,8 +446,7 @@ impl FragmentDisplayListBuilding for Fragment {
                     text_color: self.style().get_color().color.to_gfx_color(),
                     orientation: orientation,
                     baseline_origin: baseline_origin,
-                };
-                display_list.push(TextDisplayItemClass(text_display_item));
+                }));
 
                 // Create display items for text decoration
                 {
@@ -522,16 +515,14 @@ impl FragmentDisplayListBuilding for Fragment {
                         debug!("(building display list) building image fragment");
 
                         // Place the image into the display list.
-                        let image_display_item = box ImageDisplayItem {
+                        display_list.push(ImageDisplayItemClass(box ImageDisplayItem {
                             base: BaseDisplayItem::new(absolute_content_box,
                                                        self.node,
                                                        ContentStackingLevel,
                                                        *clip_rect),
                             image: image.clone(),
                             stretch_size: absolute_content_box.size,
-                        };
-
-                        display_list.push(ImageDisplayItemClass(image_display_item))
+                        }));
                     }
                     None => {
                         // No image data at all? Do nothing.
@@ -630,38 +621,35 @@ impl BlockFlowDisplayListBuilding for BlockFlow {
                                                  .relative_containing_block_size);
 
         // Add the box that starts the block context.
-        let mut display_list = DisplayList::new();
-        self.fragment.build_display_list(&mut display_list,
+        self.base.display_list = DisplayList::new();
+        let absolute_position =
+            self.base.abs_position.add_size(&relative_offset.to_physical(self.base.writing_mode));
+        self.fragment.build_display_list(&mut self.base.display_list,
                                          layout_context,
-                                         self.base.abs_position.add_size(
-                                             &relative_offset.to_physical(self.base.writing_mode)),
+                                         absolute_position,
                                          background_border_level,
                                          &self.base.clip_rect);
 
-        let mut child_layers = DList::new();
-        for kid in self.base.child_iter() {
+        self.base.layers = DList::new();
+        for kid in self.base.children.iter_mut() {
             if kid.is_absolutely_positioned() {
                 // All absolute flows will be handled by their containing block.
                 continue
             }
 
-            display_list.push_all_move(mem::replace(&mut flow::mut_base(kid).display_list,
-                                                    DisplayList::new()));
-            child_layers.append(mem::replace(&mut flow::mut_base(kid).layers, DList::new()))
+            self.base.display_list.append_from(&mut flow::mut_base(kid).display_list);
+            dlist::append_from(&mut self.base.layers, &mut flow::mut_base(kid).layers)
         }
 
         // Process absolute descendant links.
         for abs_descendant_link in self.base.abs_descendants.iter() {
             // TODO(pradeep): Send in our absolute position directly.
-            display_list.push_all_move(mem::replace(
-                    &mut flow::mut_base(abs_descendant_link).display_list,
-                    DisplayList::new()));
-            child_layers.append(mem::replace(&mut flow::mut_base(abs_descendant_link).layers,
-                                             DList::new()));
+            self.base
+                .display_list
+                .append_from(&mut flow::mut_base(abs_descendant_link).display_list);
+            dlist::append_from(&mut self.base.layers,
+                               &mut flow::mut_base(abs_descendant_link).layers)
         }
-
-        self.base.display_list = display_list;
-        self.base.layers = child_layers
     }
 
     fn build_display_list_for_absolutely_positioned_block(&mut self,
@@ -672,9 +660,7 @@ impl BlockFlowDisplayListBuilding for BlockFlow {
                 !self.base.flags.needs_layer() {
             // We didn't need a layer.
             let z_index = self.fragment.style().get_box().z_index.number_or_zero();
-            let level = PositionedDescendantStackingLevel(z_index);
-            self.base.display_list = mem::replace(&mut self.base.display_list,
-                                                  DisplayList::new()).flatten(level);
+            self.base.display_list.flatten(PositionedDescendantStackingLevel(z_index));
             return
         }
 
@@ -690,10 +676,10 @@ impl BlockFlowDisplayListBuilding for BlockFlow {
         } else {
             Scrollable
         };
-        let display_list = mem::replace(&mut self.base.display_list, DisplayList::new());
+        self.base.display_list.flatten(ContentStackingLevel);
         let new_layer = RenderLayer {
             id: self.layer_id(0),
-            display_list: Arc::new(display_list.flatten(ContentStackingLevel)),
+            display_list: Arc::new(mem::replace(&mut self.base.display_list, DisplayList::new())),
             position: Rect(origin, size),
             background_color: color::rgba(1.0, 1.0, 1.0, 0.0),
             scroll_policy: scroll_policy,
@@ -703,8 +689,6 @@ impl BlockFlowDisplayListBuilding for BlockFlow {
 
     fn build_display_list_for_floating_block(&mut self, layout_context: &LayoutContext) {
         self.build_display_list_for_block(layout_context, RootOfStackingContextLevel);
-        self.base.display_list = mem::replace(&mut self.base.display_list,
-                                              DisplayList::new()).flatten(FloatStackingLevel)
+        self.base.display_list.flatten(FloatStackingLevel)
     }
 }
-
diff --git a/components/layout/inline.rs b/components/layout/inline.rs
index 994695a5cc8..24264db6952 100644
--- a/components/layout/inline.rs
+++ b/components/layout/inline.rs
@@ -19,7 +19,7 @@ use wrapper::ThreadSafeLayoutNode;
 
 use collections::{Deque, RingBuf};
 use geom::{Rect, Size2D};
-use gfx::display_list::{ContentLevel, DisplayList};
+use gfx::display_list::ContentLevel;
 use gfx::font::FontMetrics;
 use gfx::font_context::FontContext;
 use gfx::text::glyph::CharIndex;
@@ -1199,9 +1199,9 @@ impl Flow for InlineFlow {
             match fragment.specific {
                 InlineBlockFragment(ref mut block_flow) => {
                     let block_flow = block_flow.flow_ref.deref_mut();
-                    self.base.display_list.push_all_move(
-                        mem::replace(&mut flow::mut_base(block_flow).display_list,
-                                     DisplayList::new()));
+                    self.base
+                        .display_list
+                        .append_from(&mut flow::mut_base(block_flow).display_list)
                 }
                 _ => {}
             }
diff --git a/components/layout/layout_task.rs b/components/layout/layout_task.rs
index d35aed10bcd..852ebe971f8 100644
--- a/components/layout/layout_task.rs
+++ b/components/layout/layout_task.rs
@@ -710,11 +710,10 @@ impl LayoutTask {
                 debug!("Done building display list. Display List = {}",
                        flow::base(layout_root.deref()).display_list);
 
-                let root_display_list =
-                    mem::replace(&mut flow::mut_base(layout_root.deref_mut()).display_list,
-                                 DisplayList::new());
-                root_display_list.debug();
-                let display_list = Arc::new(root_display_list.flatten(ContentStackingLevel));
+                flow::mut_base(&mut *layout_root).display_list.flatten(ContentStackingLevel);
+                let display_list =
+                    Arc::new(mem::replace(&mut flow::mut_base(&mut *layout_root).display_list,
+                                          DisplayList::new()));
 
                 // FIXME(pcwalton): This is really ugly and can't handle overflow: scroll. Refactor
                 // it with extreme prejudice.
@@ -754,7 +753,7 @@ impl LayoutTask {
                     scroll_policy: Scrollable,
                 };
 
-                rw_data.display_list = Some(display_list.clone());
+                rw_data.display_list = Some(display_list);
 
                 // TODO(pcwalton): Eventually, when we have incremental reflow, this will have to
                 // be smarter in order to handle retained layer contents properly from reflow to