auto merge of #4310 : pcwalton/servo/lists, r=SimonSapin

The exact rendering is ill-spec'd. Some things are ugly (especially the
width and height of list style images) but they are infrequently used
and I believe this implementation matches the spec. Numeric lists are
not supported yet, since they will require a separate layout pass.

The implementation is a subclass of `BlockFlow`, on advice from Robert
O'Callahan.

r? @SimonSapin 

7 files changed, 312 insertions, 52 deletions

diff --git a/components/layout/block.rs b/components/layout/block.rs
index 61fff95ec09..079a1961073 100644
--- a/components/layout/block.rs
+++ b/components/layout/block.rs
@@ -30,7 +30,7 @@
 use construct::FlowConstructor;
 use context::LayoutContext;
 use css::node_style::StyledNode;
-use display_list_builder::{BlockFlowDisplayListBuilding, BlockLevel, FragmentDisplayListBuilding};
+use display_list_builder::{BlockFlowDisplayListBuilding, FragmentDisplayListBuilding};
 use floats::{ClearBoth, ClearLeft, ClearRight, FloatKind, FloatLeft, Floats, PlacementInfo};
 use flow::{AbsolutePositionInfo, BaseFlow, BlockFlowClass, FloatIfNecessary, FlowClass, Flow};
 use flow::{ForceNonfloated, ImmutableFlowUtils, MutableFlowUtils, PreorderFlowTraversal};
@@ -51,6 +51,7 @@ use table::ColumnComputedInlineSize;
 use wrapper::ThreadSafeLayoutNode;
 
 use geom::Size2D;
+use gfx::display_list::DisplayList;
 use serialize::{Encoder, Encodable};
 use servo_msg::compositor_msg::LayerId;
 use servo_util::geometry::{Au, MAX_AU, MAX_RECT, ZERO_POINT};
@@ -1853,16 +1854,7 @@ impl Flow for BlockFlow {
     }
 
     fn build_display_list(&mut self, layout_context: &LayoutContext) {
-        if self.base.flags.is_float() {
-            // TODO(#2009, pcwalton): This is a pseudo-stacking context. We need to merge `z-index:
-            // auto` kids into the parent stacking context, when that is supported.
-            self.build_display_list_for_floating_block(layout_context)
-        } else if self.base.flags.contains(IS_ABSOLUTELY_POSITIONED) {
-            self.build_display_list_for_absolutely_positioned_block(layout_context)
-        } else {
-            self.build_display_list_for_block(layout_context, BlockLevel)
-        }
-
+        self.build_display_list_for_block(box DisplayList::new(), layout_context);
         if opts::get().validate_display_list_geometry {
             self.base.validate_display_list_geometry();
         }
diff --git a/components/layout/construct.rs b/components/layout/construct.rs
index 21a24af7efb..ec8533058cd 100644
--- a/components/layout/construct.rs
+++ b/components/layout/construct.rs
@@ -30,6 +30,7 @@ use fragment::{TableColumnFragment, TableColumnFragmentInfo, TableFragment, Tabl
 use fragment::{TableWrapperFragment, UnscannedTextFragment, UnscannedTextFragmentInfo};
 use incremental::{RECONSTRUCT_FLOW, RestyleDamage};
 use inline::InlineFlow;
+use list_item::{mod, ListItemFlow};
 use parallel;
 use table_wrapper::TableWrapperFlow;
 use table::TableFlow;
@@ -59,7 +60,7 @@ use std::collections::DList;
 use std::mem;
 use std::sync::atomic::Relaxed;
 use style::ComputedValues;
-use style::computed_values::{display, position, float};
+use style::computed_values::{display, position, float, list_style_position};
 use sync::Arc;
 use url::Url;
 
@@ -471,38 +472,25 @@ impl<'a> FlowConstructor<'a> {
         }
     }
 
-    /// Build block flow for current node using information from children nodes.
-    ///
-    /// Consume results from children and combine them, handling {ib} splits.
-    /// Block flows and inline flows thus created will become the children of
-    /// this block flow.
-    /// Also, deal with the absolute and fixed descendants bubbled up by
-    /// children nodes.
-    fn build_flow_for_block(&mut self, mut flow: FlowRef, node: &ThreadSafeLayoutNode)
-                            -> ConstructionResult {
+    /// Constructs a block flow, beginning with the given `initial_fragment` if present and then
+    /// appending the construction results of children to the child list of the block flow. {ib}
+    /// splits and absolutely-positioned descendants are handled correctly.
+    fn build_flow_for_block_starting_with_fragment(&mut self,
+                                                   mut flow: FlowRef,
+                                                   node: &ThreadSafeLayoutNode,
+                                                   initial_fragment: Option<Fragment>)
+                                                   -> ConstructionResult {
         // Gather up fragments for the inline flows we might need to create.
         let mut inline_fragment_accumulator = InlineFragmentsAccumulator::new();
         let mut consecutive_siblings = vec!();
-        let mut first_fragment = true;
 
-        // Special case: If this is generated content, then we need to initialize the accumulator
-        // with the fragment corresponding to that content.
-        if node.get_pseudo_element_type() != Normal ||
-           node.type_id() == Some(ElementNodeTypeId(HTMLInputElementTypeId)) ||
-           node.type_id() == Some(ElementNodeTypeId(HTMLTextAreaElementTypeId)) {
-            // A TextArea's text contents are displayed through the input text
-            // box, so don't construct them.
-            // TODO Maybe this belongs somewhere else?
-            if node.type_id() == Some(ElementNodeTypeId(HTMLTextAreaElementTypeId)) {
-                for kid in node.children() {
-                    kid.set_flow_construction_result(NoConstructionResult)
-                }
+        let mut first_fragment = match initial_fragment {
+            None => true,
+            Some(initial_fragment) => {
+                inline_fragment_accumulator.fragments.push_back(initial_fragment);
+                false
             }
-            let fragment_info = UnscannedTextFragment(UnscannedTextFragmentInfo::new(node));
-            let fragment = Fragment::new_from_specific_info(node, fragment_info);
-            inline_fragment_accumulator.fragments.push_back(fragment);
-            first_fragment = false;
-        }
+        };
 
         // List of absolute descendants, in tree order.
         let mut abs_descendants = Descendants::new();
@@ -552,6 +540,39 @@ impl<'a> FlowConstructor<'a> {
         FlowConstructionResult(flow, abs_descendants)
     }
 
+    /// Constructs a flow for the given block node and its children. This method creates an
+    /// initial fragment as appropriate and then dispatches to
+    /// `build_flow_for_block_starting_with_fragment`. Currently the following kinds of flows get
+    /// initial content:
+    ///
+    /// * Generated content gets the initial content specified by the `content` attribute of the
+    ///   CSS.
+    /// * `<input>` and `<textarea>` elements get their content.
+    ///
+    /// FIXME(pcwalton): It is not clear to me that there isn't a cleaner way to handle
+    /// `<textarea>`.
+    fn build_flow_for_block(&mut self, flow: FlowRef, node: &ThreadSafeLayoutNode)
+                            -> ConstructionResult {
+        let initial_fragment = if node.get_pseudo_element_type() != Normal ||
+           node.type_id() == Some(ElementNodeTypeId(HTMLInputElementTypeId)) ||
+           node.type_id() == Some(ElementNodeTypeId(HTMLTextAreaElementTypeId)) {
+            // A TextArea's text contents are displayed through the input text
+            // box, so don't construct them.
+            if node.type_id() == Some(ElementNodeTypeId(HTMLTextAreaElementTypeId)) {
+                for kid in node.children() {
+                    kid.set_flow_construction_result(NoConstructionResult)
+                }
+            }
+            Some(Fragment::new_from_specific_info(
+                    node,
+                    UnscannedTextFragment(UnscannedTextFragmentInfo::new(node))))
+        } else {
+            None
+        };
+
+        self.build_flow_for_block_starting_with_fragment(flow, node, initial_fragment)
+    }
+
     /// 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.
@@ -905,6 +926,59 @@ impl<'a> FlowConstructor<'a> {
         self.build_flow_for_block(FlowRef::new(flow), node)
     }
 
+    /// Builds a flow for a node with `display: list-item`. This yields a `ListItemFlow` with
+    /// possibly other `BlockFlow`s or `InlineFlow`s underneath it.
+    fn build_flow_for_list_item(&mut self, node: &ThreadSafeLayoutNode) -> ConstructionResult {
+        let marker_fragment = match node.style().get_list().list_style_image {
+            Some(ref url) => {
+                Some(Fragment::new_from_specific_info(
+                    node,
+                    self.build_fragment_info_for_image(node, Some((*url).clone()))))
+            }
+            None => {
+                match list_item::static_text_for_list_style_type(node.style()
+                                                                     .get_list()
+                                                                     .list_style_type) {
+                    None => None,
+                    Some(text) => {
+                        let text = text.to_string();
+                        let mut unscanned_marker_fragments = DList::new();
+                        unscanned_marker_fragments.push_back(Fragment::new_from_specific_info(
+                            node,
+                            UnscannedTextFragment(UnscannedTextFragmentInfo::from_text(text))));
+                        let marker_fragments = TextRunScanner::new().scan_for_runs(
+                            self.layout_context.font_context(),
+                            unscanned_marker_fragments);
+                        debug_assert!(marker_fragments.len() == 1);
+                        marker_fragments.fragments.into_iter().next()
+                    }
+                }
+            }
+        };
+
+        // If the list marker is outside, it becomes the special "outside fragment" that list item
+        // flows have. If it's inside, it's just a plain old fragment. Note that this means that
+        // we adopt Gecko's behavior rather than WebKit's when the marker causes an {ib} split,
+        // which has caused some malaise (Bugzilla #36854) but CSS 2.1 § 12.5.1 lets me do it, so
+        // there.
+        let flow;
+        let initial_fragment;
+        match node.style().get_list().list_style_position {
+            list_style_position::outside => {
+                flow = box ListItemFlow::from_node_and_marker(self, node, marker_fragment);
+                initial_fragment = None;
+            }
+            list_style_position::inside => {
+                flow = box ListItemFlow::from_node_and_marker(self, node, None);
+                initial_fragment = marker_fragment;
+            }
+        }
+
+        self.build_flow_for_block_starting_with_fragment(FlowRef::new(flow as Box<Flow>),
+                                                         node,
+                                                         initial_fragment)
+    }
+
     /// Creates a fragment for a node with `display: table-column`.
     fn build_fragments_for_table_column(&mut self, node: &ThreadSafeLayoutNode)
                                         -> ConstructionResult {
@@ -1058,6 +1132,11 @@ impl<'a> PostorderNodeMutTraversal for FlowConstructor<'a> {
                 node.set_flow_construction_result(self.build_flow_for_nonfloated_block(node))
             }
 
+            // List items contribute their own special flows.
+            (display::list_item, _, _) => {
+                node.set_flow_construction_result(self.build_flow_for_list_item(node))
+            }
+
             // Inline items that are absolutely-positioned contribute inline fragment construction
             // results with a hypothetical fragment.
             (display::inline, _, position::absolute) => {
diff --git a/components/layout/display_list_builder.rs b/components/layout/display_list_builder.rs
index b11a14033c0..c8db1d4f992 100644
--- a/components/layout/display_list_builder.rs
+++ b/components/layout/display_list_builder.rs
@@ -12,12 +12,13 @@
 
 use block::BlockFlow;
 use context::LayoutContext;
-use flow::{mod, Flow, NEEDS_LAYER};
+use flow::{mod, Flow, IS_ABSOLUTELY_POSITIONED, NEEDS_LAYER};
 use fragment::{Fragment, GenericFragment, IframeFragment, IframeFragmentInfo, ImageFragment};
 use fragment::{ImageFragmentInfo, InlineAbsoluteHypotheticalFragment, InlineBlockFragment};
 use fragment::{ScannedTextFragment, ScannedTextFragmentInfo, TableFragment};
 use fragment::{TableCellFragment, TableColumnFragment, TableRowFragment, TableWrapperFragment};
 use fragment::{UnscannedTextFragment};
+use list_item::ListItemFlow;
 use model;
 use util::{OpaqueNodeMethods, ToGfxColor};
 
@@ -914,12 +915,19 @@ pub trait BlockFlowDisplayListBuilding {
                                          display_list: &mut DisplayList,
                                          layout_context: &LayoutContext,
                                          background_border_level: BackgroundAndBorderLevel);
-    fn build_display_list_for_block(&mut self,
-                                    layout_context: &LayoutContext,
-                                    background_border_level: BackgroundAndBorderLevel);
+    fn build_display_list_for_static_block(&mut self,
+                                           display_list: Box<DisplayList>,
+                                           layout_context: &LayoutContext,
+                                           background_border_level: BackgroundAndBorderLevel);
     fn build_display_list_for_absolutely_positioned_block(&mut self,
+                                                          display_list: Box<DisplayList>,
                                                           layout_context: &LayoutContext);
-    fn build_display_list_for_floating_block(&mut self, layout_context: &LayoutContext);
+    fn build_display_list_for_floating_block(&mut self,
+                                             display_list: Box<DisplayList>,
+                                             layout_context: &LayoutContext);
+    fn build_display_list_for_block(&mut self,
+                                    display_list: Box<DisplayList>,
+                                    layout_context: &LayoutContext);
     fn create_stacking_context(&self,
                                display_list: Box<DisplayList>,
                                layer: Option<Arc<PaintLayer>>)
@@ -945,10 +953,10 @@ impl BlockFlowDisplayListBuilding for BlockFlow {
         }
     }
 
-    fn build_display_list_for_block(&mut self,
-                                    layout_context: &LayoutContext,
-                                    background_border_level: BackgroundAndBorderLevel) {
-        let mut display_list = box DisplayList::new();
+    fn build_display_list_for_static_block(&mut self,
+                                           mut display_list: Box<DisplayList>,
+                                           layout_context: &LayoutContext,
+                                           background_border_level: BackgroundAndBorderLevel) {
         self.build_display_list_for_block_base(&mut *display_list,
                                                layout_context,
                                                background_border_level);
@@ -961,8 +969,8 @@ impl BlockFlowDisplayListBuilding for BlockFlow {
     }
 
     fn build_display_list_for_absolutely_positioned_block(&mut self,
+                                                          mut display_list: Box<DisplayList>,
                                                           layout_context: &LayoutContext) {
-        let mut display_list = box DisplayList::new();
         self.build_display_list_for_block_base(&mut *display_list,
                                                layout_context,
                                                RootOfStackingContextLevel);
@@ -991,8 +999,9 @@ impl BlockFlowDisplayListBuilding for BlockFlow {
         self.base.display_list_building_result = StackingContextResult(stacking_context)
     }
 
-    fn build_display_list_for_floating_block(&mut self, layout_context: &LayoutContext) {
-        let mut display_list = box DisplayList::new();
+    fn build_display_list_for_floating_block(&mut self,
+                                             mut display_list: Box<DisplayList>,
+                                             layout_context: &LayoutContext) {
         self.build_display_list_for_block_base(&mut *display_list,
                                                layout_context,
                                                RootOfStackingContextLevel);
@@ -1005,6 +1014,20 @@ impl BlockFlowDisplayListBuilding for BlockFlow {
         }
     }
 
+    fn build_display_list_for_block(&mut self,
+                                    display_list: Box<DisplayList>,
+                                    layout_context: &LayoutContext) {
+        if self.base.flags.is_float() {
+            // TODO(#2009, pcwalton): This is a pseudo-stacking context. We need to merge `z-index:
+            // auto` kids into the parent stacking context, when that is supported.
+            self.build_display_list_for_floating_block(display_list, layout_context)
+        } else if self.base.flags.contains(IS_ABSOLUTELY_POSITIONED) {
+            self.build_display_list_for_absolutely_positioned_block(display_list, layout_context)
+        } else {
+            self.build_display_list_for_static_block(display_list, layout_context, BlockLevel)
+        }
+    }
+
     fn create_stacking_context(&self,
                                display_list: Box<DisplayList>,
                                layer: Option<Arc<PaintLayer>>)
@@ -1017,6 +1040,35 @@ impl BlockFlowDisplayListBuilding for BlockFlow {
     }
 }
 
+pub trait ListItemFlowDisplayListBuilding {
+    fn build_display_list_for_list_item(&mut self,
+                                        display_list: Box<DisplayList>,
+                                        layout_context: &LayoutContext);
+}
+
+impl ListItemFlowDisplayListBuilding for ListItemFlow {
+    fn build_display_list_for_list_item(&mut self,
+                                        mut display_list: Box<DisplayList>,
+                                        layout_context: &LayoutContext) {
+        // Draw the marker, if applicable.
+        match self.marker {
+            None => {}
+            Some(ref mut marker) => {
+                let stacking_relative_fragment_origin =
+                    self.block_flow.base.stacking_relative_position_of_child_fragment(marker);
+                marker.build_display_list(&mut *display_list,
+                                          layout_context,
+                                          stacking_relative_fragment_origin,
+                                          ContentLevel,
+                                          &self.block_flow.base.clip_rect);
+            }
+        }
+
+        // Draw the rest of the block.
+        self.block_flow.build_display_list_for_block(display_list, layout_context)
+    }
+}
+
 // A helper data structure for gradients.
 struct StopRun {
     start_offset: f32,
diff --git a/components/layout/flow.rs b/components/layout/flow.rs
index bfca9c6168c..20645e70123 100644
--- a/components/layout/flow.rs
+++ b/components/layout/flow.rs
@@ -430,6 +430,7 @@ pub trait MutableOwnedFlowUtils {
 pub enum FlowClass {
     BlockFlowClass,
     InlineFlowClass,
+    ListItemFlowClass,
     TableWrapperFlowClass,
     TableFlowClass,
     TableColGroupFlowClass,
diff --git a/components/layout/lib.rs b/components/layout/lib.rs
index 2d045508088..1fa21311373 100644
--- a/components/layout/lib.rs
+++ b/components/layout/lib.rs
@@ -52,6 +52,7 @@ pub mod flow_ref;
 pub mod fragment;
 pub mod layout_task;
 pub mod inline;
+pub mod list_item;
 pub mod model;
 pub mod parallel;
 pub mod sequential;
diff --git a/components/layout/list_item.rs b/components/layout/list_item.rs
new file mode 100644
index 00000000000..fbf40c7747c
--- /dev/null
+++ b/components/layout/list_item.rs
@@ -0,0 +1,135 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+//! Layout for elements with a CSS `display` property of `list-item`. These elements consist of a
+//! block and an extra inline fragment for the marker.
+
+#![deny(unsafe_blocks)]
+
+use block::BlockFlow;
+use construct::FlowConstructor;
+use context::LayoutContext;
+use display_list_builder::ListItemFlowDisplayListBuilding;
+use flow::{Flow, FlowClass, ListItemFlowClass};
+use fragment::{Fragment, FragmentBoundsIterator};
+use wrapper::ThreadSafeLayoutNode;
+
+use gfx::display_list::DisplayList;
+use servo_util::geometry::Au;
+use servo_util::opts;
+use style::ComputedValues;
+use style::computed_values::list_style_type;
+use sync::Arc;
+
+/// A block with the CSS `display` property equal to `list-item`.
+#[deriving(Show)]
+pub struct ListItemFlow {
+    /// Data common to all block flows.
+    pub block_flow: BlockFlow,
+    /// The marker, if outside. (Markers that are inside are instead just fragments on the interior
+    /// `InlineFlow`.)
+    pub marker: Option<Fragment>,
+}
+
+impl ListItemFlow {
+    pub fn from_node_and_marker(constructor: &mut FlowConstructor,
+                                node: &ThreadSafeLayoutNode,
+                                marker_fragment: Option<Fragment>)
+                                -> ListItemFlow {
+        ListItemFlow {
+            block_flow: BlockFlow::from_node(constructor, node),
+            marker: marker_fragment,
+        }
+    }
+}
+
+impl Flow for ListItemFlow {
+    fn class(&self) -> FlowClass {
+        ListItemFlowClass
+    }
+
+    fn as_block<'a>(&'a mut self) -> &'a mut BlockFlow {
+        &mut self.block_flow
+    }
+
+    fn bubble_inline_sizes(&mut self) {
+        // The marker contributes no intrinsic inline-size, so…
+        self.block_flow.bubble_inline_sizes()
+    }
+
+    fn assign_inline_sizes(&mut self, layout_context: &LayoutContext) {
+        self.block_flow.assign_inline_sizes(layout_context);
+
+        match self.marker {
+            None => {}
+            Some(ref mut marker) => {
+                // Do this now. There's no need to do this in bubble-widths, since markers do not
+                // contribute to the inline size of this flow.
+                let intrinsic_inline_sizes = marker.compute_intrinsic_inline_sizes();
+
+                marker.border_box.size.inline =
+                    intrinsic_inline_sizes.content_intrinsic_sizes.preferred_inline_size;
+                marker.border_box.start.i = self.block_flow.fragment.border_box.start.i -
+                    marker.border_box.size.inline;
+            }
+        }
+    }
+
+    fn assign_block_size<'a>(&mut self, layout_context: &'a LayoutContext<'a>) {
+        self.block_flow.assign_block_size(layout_context);
+
+        match self.marker {
+            None => {}
+            Some(ref mut marker) => {
+                marker.border_box.start.b = Au(0);
+                marker.border_box.size.block = marker.calculate_line_height(layout_context);
+            }
+        }
+    }
+
+    fn compute_absolute_position(&mut self) {
+        self.block_flow.compute_absolute_position()
+    }
+
+    fn update_late_computed_inline_position_if_necessary(&mut self, inline_position: Au) {
+        self.block_flow.update_late_computed_inline_position_if_necessary(inline_position)
+    }
+
+    fn update_late_computed_block_position_if_necessary(&mut self, block_position: Au) {
+        self.block_flow.update_late_computed_block_position_if_necessary(block_position)
+    }
+
+    fn build_display_list(&mut self, layout_context: &LayoutContext) {
+        self.build_display_list_for_list_item(box DisplayList::new(), layout_context);
+        if opts::get().validate_display_list_geometry {
+            self.block_flow.base.validate_display_list_geometry();
+        }
+    }
+
+    fn repair_style(&mut self, new_style: &Arc<ComputedValues>) {
+        self.block_flow.repair_style(new_style)
+    }
+
+    fn iterate_through_fragment_bounds(&self, iterator: &mut FragmentBoundsIterator) {
+        self.block_flow.iterate_through_fragment_bounds(iterator);
+    }
+}
+
+/// Returns the static text to be used for the given value of the `list-style-type` property.
+///
+/// TODO(pcwalton): Return either a string or a counter descriptor, once we support counters.
+pub fn static_text_for_list_style_type(list_style_type: list_style_type::T)
+                                       -> Option<&'static str> {
+    // Just to keep things simple, use a nonbreaking space (Unicode 0xa0) to provide the marker
+    // separation.
+    match list_style_type {
+        list_style_type::none => None,
+        list_style_type::disc => Some("•\u00a0"),
+        list_style_type::circle => Some("◦\u00a0"),
+        list_style_type::square => Some("▪\u00a0"),
+        list_style_type::disclosure_open => Some("▾\u00a0"),
+        list_style_type::disclosure_closed => Some("‣\u00a0"),
+    }
+}
+
diff --git a/components/layout/table_cell.rs b/components/layout/table_cell.rs
index 8dd0817b6da..280e86408cb 100644
--- a/components/layout/table_cell.rs
+++ b/components/layout/table_cell.rs
@@ -23,7 +23,7 @@ use sync::Arc;
 /// A table formatting context.
 #[deriving(Encodable)]
 pub struct TableCellFlow {
-    /// Data common to all flows.
+    /// Data common to all block flows.
     pub block_flow: BlockFlow,
 }