gfx: Rewrite display list construction to make stacking-contexts more

first-class.

This implements the scheme described here:

    https://groups.google.com/forum/#!topic/mozilla.dev.servo/sZVPSfPVfkg

This commit changes Servo to generate one display list per stacking
context instead of one display list per layer. This is purely a
refactoring; there are no functional changes. Performance is essentially
the same as before. However, there should be numerous future benefits
that this is intended to allow for:

* It makes the code simpler to understand because the "new layer needed"
  vs. "no new layer needed" code paths are more consolidated.

* It makes it easy to support CSS properties that did not fit into our
  previous flat display list model (without unconditionally layerizing
  them):

  o `opacity` should be easy to support because the stacking context
    provides the higher-level grouping of display items to which opacity
    is to be applied.

  o `transform` can be easily supported because the stacking context
    provides a place to stash the transformation matrix. This has the side
    benefit of nicely separating the transformation matrix from the
    clipping regions.

* The `flatten` logic is now O(1) instead of O(n) and now only needs to
  be invoked for pseudo-stacking contexts (right now: just floats),
  instead of for every stacking context.

* Layers are now a proper tree instead of a flat list as far as layout
  is concerned, bringing us closer to a production-quality
  compositing/layers framework.

* This commit opens the door to incremental display list construction at
  the level of stacking contexts.

Future performance improvements could come from optimizing allocation of
display list items, and, of course, incremental display list
construction.

1 files changed, 37 insertions, 70 deletions

diff --git a/components/layout/layout_task.rs b/components/layout/layout_task.rs
index 15d9daccbc8..8fe2afb35ab 100644
--- a/components/layout/layout_task.rs
+++ b/components/layout/layout_task.rs
@@ -19,15 +19,13 @@ use sequential;
 use util::{LayoutDataAccess, LayoutDataWrapper, OpaqueNodeMethods, ToGfxColor};
 use wrapper::{LayoutNode, TLayoutNode, ThreadSafeLayoutNode};
 
-use collections::dlist::DList;
 use encoding::EncodingRef;
 use encoding::all::UTF_8;
 use geom::point::Point2D;
 use geom::rect::Rect;
 use geom::size::Size2D;
 use geom::scale_factor::ScaleFactor;
-use gfx::display_list::{ContentStackingLevel, DisplayItem, DisplayList};
-use gfx::display_list::{OpaqueNode};
+use gfx::display_list::{DisplayList, OpaqueNode, StackingContext};
 use gfx::render_task::{RenderInitMsg, RenderChan, RenderLayer};
 use gfx::{render_task, color};
 use layout_traits;
@@ -51,7 +49,6 @@ use gfx::font_cache_task::{FontCacheTask};
 use servo_net::local_image_cache::{ImageResponder, LocalImageCache};
 use servo_net::resource_task::{ResourceTask, load_bytes_iter};
 use servo_util::geometry::Au;
-use servo_util::geometry;
 use servo_util::logical_geometry::LogicalPoint;
 use servo_util::opts;
 use servo_util::smallvec::{SmallVec, SmallVec1, VecLike};
@@ -79,8 +76,8 @@ pub struct LayoutTaskData {
     /// The size of the viewport.
     pub screen_size: Size2D<Au>,
 
-    /// A cached display list.
-    pub display_list: Option<Arc<DisplayList>>,
+    /// The root stacking context.
+    pub stacking_context: Option<Arc<StackingContext>>,
 
     pub stylist: Box<Stylist>,
 
@@ -277,7 +274,7 @@ impl LayoutTask {
                 LayoutTaskData {
                     local_image_cache: local_image_cache,
                     screen_size: screen_size,
-                    display_list: None,
+                    stacking_context: None,
                     stylist: box Stylist::new(device),
                     parallel_traversal: parallel_traversal,
                     dirty: Rect::zero(),
@@ -621,7 +618,7 @@ impl LayoutTask {
             shared_layout_ctx.dirty =
                 flow::base(layout_root.deref()).position.to_physical(writing_mode,
                                                                      rw_data.screen_size);
-            flow::mut_base(layout_root.deref_mut()).abs_position =
+            flow::mut_base(layout_root.deref_mut()).stacking_relative_position =
                 LogicalPoint::zero(writing_mode).to_physical(writing_mode,
                                                              rw_data.screen_size);
 
@@ -643,13 +640,7 @@ impl LayoutTask {
                 }
             }
 
-            debug!("Done building display list. Display List = {}",
-                   flow::base(layout_root.deref()).display_list);
-
-            flow::mut_base(layout_root.deref_mut()).display_list.flatten(ContentStackingLevel);
-            let display_list =
-                Arc::new(mem::replace(&mut flow::mut_base(layout_root.deref_mut()).display_list,
-                                      DisplayList::new()));
+            debug!("Done building display list.");
 
             // FIXME(pcwalton): This is really ugly and can't handle overflow: scroll. Refactor
             // it with extreme prejudice.
@@ -678,31 +669,23 @@ impl LayoutTask {
                 let root_flow = flow::base(layout_root.deref());
                 root_flow.position.size.to_physical(root_flow.writing_mode)
             };
-            let root_size = Size2D(root_size.width.to_nearest_px() as uint,
-                                   root_size.height.to_nearest_px() as uint);
-            let render_layer = RenderLayer {
-                id: layout_root.layer_id(0),
-                display_list: display_list.clone(),
-                position: Rect(Point2D(0u, 0u), root_size),
-                background_color: color,
-                scroll_policy: Scrollable,
-            };
-
-            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
-            // reflow.
-            let mut layers = SmallVec1::new();
-            layers.push(render_layer);
-            for layer in mem::replace(&mut flow::mut_base(layout_root.deref_mut()).layers,
-                                      DList::new()).into_iter() {
-                layers.push(layer)
-            }
+            let mut display_list = box DisplayList::new();
+            flow::mut_base(layout_root.deref_mut()).display_list_building_result
+                                                   .add_to(&mut *display_list);
+            let render_layer = Arc::new(RenderLayer::new(layout_root.layer_id(0),
+                                                         color,
+                                                         Scrollable));
+            let origin = Rect(Point2D(Au(0), Au(0)), root_size);
+            let stacking_context = Arc::new(StackingContext::new(display_list,
+                                                                 origin,
+                                                                 0,
+                                                                 Some(render_layer)));
+
+            rw_data.stacking_context = Some(stacking_context.clone());
 
             debug!("Layout done!");
 
-            self.render_chan.send(RenderInitMsg(layers));
+            self.render_chan.send(RenderInitMsg(stacking_context));
         });
     }
 
@@ -933,27 +916,23 @@ impl LayoutRPC for LayoutRPCImpl {
         ContentBoxesResponse(rw_data.content_boxes_response.clone())
     }
 
-    /// Requests the node containing the point of interest
+    /// Requests the node containing the point of interest.
     fn hit_test(&self, _: TrustedNodeAddress, point: Point2D<f32>) -> Result<HitTestResponse, ()> {
-        fn hit_test<'a,I>(point: Point2D<Au>, mut iterator: I)
-                          -> Option<HitTestResponse>
-                          where I: Iterator<&'a DisplayItem> {
-            for item in iterator {
-                // TODO(tikue): This check should really be performed by a method of `DisplayItem`.
-                if geometry::rect_contains_point(item.base().clip_rect, point) &&
-                        geometry::rect_contains_point(item.bounds(), point) {
-                    return Some(HitTestResponse(item.base().node.to_untrusted_node_address()))
-                }
-            }
-            None
-        }
         let point = Point2D(Au::from_frac_px(point.x as f64), Au::from_frac_px(point.y as f64));
         let resp = {
             let &LayoutRPCImpl(ref rw_data) = self;
             let rw_data = rw_data.lock();
-            match rw_data.display_list {
-                None => panic!("no display list!"),
-                Some(ref display_list) => hit_test(point, display_list.list.iter().rev()),
+            match rw_data.stacking_context {
+                None => panic!("no root stacking context!"),
+                Some(ref stacking_context) => {
+                    let mut result = Vec::new();
+                    stacking_context.hit_test(point, &mut result, true);
+                    if !result.is_empty() {
+                        Some(HitTestResponse(result[0]))
+                    } else {
+                        None
+                    }
+                }
             }
         };
 
@@ -965,29 +944,17 @@ impl LayoutRPC for LayoutRPCImpl {
 
     fn mouse_over(&self, _: TrustedNodeAddress, point: Point2D<f32>)
                   -> Result<MouseOverResponse, ()> {
-        fn mouse_over_test<'a,I>(point: Point2D<Au>,
-                                 mut iterator: I,
-                                 result: &mut Vec<UntrustedNodeAddress>)
-                                 where I: Iterator<&'a DisplayItem> {
-            for item in iterator {
-                // TODO(tikue): This check should really be performed by a method of `DisplayItem`.
-                if geometry::rect_contains_point(item.bounds(), point) {
-                    result.push(item.base().node.to_untrusted_node_address())
-                }
-            }
-        }
-
         let mut mouse_over_list: Vec<UntrustedNodeAddress> = vec!();
         let point = Point2D(Au::from_frac_px(point.x as f64), Au::from_frac_px(point.y as f64));
         {
             let &LayoutRPCImpl(ref rw_data) = self;
             let rw_data = rw_data.lock();
-            match rw_data.display_list {
-                None => panic!("no display list!"),
-                Some(ref display_list) => {
-                    mouse_over_test(point, display_list.list.iter().rev(), &mut mouse_over_list);
+            match rw_data.stacking_context {
+                None => panic!("no root stacking context!"),
+                Some(ref stacking_context) => {
+                    stacking_context.hit_test(point, &mut mouse_over_list, false);
                 }
-            };
+            }
         }
 
         if mouse_over_list.is_empty() {