layout: Rewrite the float context.

This rewrites the float context to avoid dynamic failures resulting from
`.clone()` misuse. It also renames the float context to the simpler
`Floats`. The new version is modeled on WebKit's `FloatingObjects`.

8 files changed, 448 insertions, 451 deletions

diff --git a/src/components/main/layout/block.rs b/src/components/main/layout/block.rs
index 079654658b9..ccaf15b456b 100644
--- a/src/components/main/layout/block.rs
+++ b/src/components/main/layout/block.rs
@@ -8,7 +8,7 @@ use layout::box_::Box;
 use layout::construct::FlowConstructor;
 use layout::context::LayoutContext;
 use layout::display_list_builder::{DisplayListBuilder, ExtraDisplayListData};
-use layout::float_context::{FloatContext, PlacementInfo, Invalid, FloatType};
+use layout::floats::{FloatKind, Floats, PlacementInfo};
 use layout::flow::{BaseFlow, BlockFlowClass, FlowClass, Flow, ImmutableFlowUtils};
 use layout::flow;
 use layout::model::{MaybeAuto, Specified, Auto, specified_or_none, specified};
@@ -34,17 +34,17 @@ pub struct FloatedBlockInfo {
     floated_children: uint,
 
     /// Left or right?
-    float_type: FloatType
+    float_kind: FloatKind,
 }
 
 impl FloatedBlockInfo {
-    pub fn new(float_type: FloatType) -> FloatedBlockInfo {
+    pub fn new(float_kind: FloatKind) -> FloatedBlockInfo {
         FloatedBlockInfo {
             containing_width: Au(0),
             rel_pos: Point2D(Au(0), Au(0)),
             index: None,
             floated_children: 0,
-            float_type: float_type
+            float_kind: float_kind,
         }
     }
 }
@@ -68,7 +68,9 @@ pub struct BlockFlow {
 }
 
 impl BlockFlow {
-    pub fn from_node(constructor: &mut FlowConstructor, node: &ThreadSafeLayoutNode, is_fixed: bool)
+    pub fn from_node(constructor: &mut FlowConstructor,
+                     node: &ThreadSafeLayoutNode,
+                     is_fixed: bool)
                      -> BlockFlow {
         BlockFlow {
             base: BaseFlow::new((*node).clone()),
@@ -81,14 +83,14 @@ impl BlockFlow {
 
     pub fn float_from_node(constructor: &mut FlowConstructor,
                            node: &ThreadSafeLayoutNode,
-                           float_type: FloatType)
+                           float_kind: FloatKind)
                            -> BlockFlow {
         BlockFlow {
             base: BaseFlow::new((*node).clone()),
             box_: Some(Box::new(constructor, node)),
             is_root: false,
             is_fixed: false,
-            float: Some(~FloatedBlockInfo::new(float_type))
+            float: Some(~FloatedBlockInfo::new(float_kind))
         }
     }
 
@@ -102,13 +104,13 @@ impl BlockFlow {
         }
     }
 
-    pub fn new_float(base: BaseFlow, float_type: FloatType) -> BlockFlow {
+    pub fn new_float(base: BaseFlow, float_kind: FloatKind) -> BlockFlow {
         BlockFlow {
             base: base,
             box_: None,
             is_root: false,
             is_fixed: false,
-            float: Some(~FloatedBlockInfo::new(float_type))
+            float: Some(~FloatedBlockInfo::new(float_kind))
         }
     }
 
@@ -257,13 +259,12 @@ impl BlockFlow {
         let mut top_offset = Au::new(0);
         let mut bottom_offset = Au::new(0);
         let mut left_offset = Au::new(0);
-        let mut float_ctx = Invalid;
 
         for box_ in self.box_.iter() {
             clearance = match box_.clear() {
                 None => Au::new(0),
                 Some(clear) => {
-                    self.base.floats_in.clearance(clear)
+                    self.base.floats.clearance(clear)
                 }
             };
 
@@ -277,18 +278,20 @@ impl BlockFlow {
 
         if inorder {
             // Floats for blocks work like this:
-            // self.floats_in -> child[0].floats_in
+            // self.floats -> child[0].floats
             // visit child[0]
-            // child[i-1].floats_out -> child[i].floats_in
+            // child[i-1].floats -> child[i].floats
             // visit child[i]
             // repeat until all children are visited.
-            // last_child.floats_out -> self.floats_out (done at the end of this method)
-            float_ctx = self.base.floats_in.translate(Point2D(-left_offset, -top_offset));
+            // last_child.floats -> self.floats (done at the end of this method)
+            self.base.floats.translate(Point2D(-left_offset, -top_offset));
+            let mut floats = self.base.floats.clone();
             for kid in self.base.child_iter() {
-                flow::mut_base(kid).floats_in = float_ctx.clone();
+                flow::mut_base(kid).floats = floats;
                 kid.assign_height_inorder(ctx);
-                float_ctx = flow::mut_base(kid).floats_out.clone();
+                floats = flow::mut_base(kid).floats.clone();
             }
+            self.base.floats = floats;
         }
 
         // The amount of margin that we can potentially collapse with
@@ -434,9 +437,7 @@ impl BlockFlow {
 
         if inorder {
             let extra_height = height - (cur_y - top_offset) + bottom_offset;
-            self.base.floats_out = float_ctx.translate(Point2D(left_offset, -extra_height));
-        } else {
-            self.base.floats_out = self.base.floats_in.clone();
+            self.base.floats.translate(Point2D(left_offset, -extra_height));
         }
     }
 
@@ -453,7 +454,7 @@ impl BlockFlow {
             height = box_.border_box.get().size.height;
             clearance = match box_.clear() {
                 None => Au(0),
-                Some(clear) => self.base.floats_in.clearance(clear),
+                Some(clear) => self.base.floats.clearance(clear),
             };
 
             let noncontent_width = box_.padding.get().left + box_.padding.get().right +
@@ -465,29 +466,33 @@ impl BlockFlow {
         }
 
         let info = PlacementInfo {
-            width: self.base.position.size.width + full_noncontent_width,
-            height: height + margin_height,
+            size: Size2D(self.base.position.size.width + full_noncontent_width,
+                         height + margin_height),
             ceiling: clearance,
             max_width: self.float.get_ref().containing_width,
-            f_type: self.float.get_ref().float_type,
+            kind: self.float.get_ref().float_kind,
         };
 
-        // Place the float and return the FloatContext back to the parent flow.
+        // Place the float and return the `Floats` back to the parent flow.
         // After, grab the position and use that to set our position.
-        self.base.floats_out = self.base.floats_in.add_float(&info);
-        self.float.get_mut_ref().rel_pos = self.base.floats_out.last_float_pos();
+        self.base.floats.add_float(&info);
+
+        self.float.get_mut_ref().rel_pos = self.base.floats.last_float_pos().unwrap();
     }
 
     fn assign_height_float(&mut self, ctx: &mut LayoutContext) {
         // Now that we've determined our height, propagate that out.
         let has_inorder_children = self.base.num_floats > 0;
         if has_inorder_children {
-            let mut float_ctx = FloatContext::new(self.float.get_ref().floated_children);
+            let mut floats = Floats::new();
             for kid in self.base.child_iter() {
-                flow::mut_base(kid).floats_in = float_ctx.clone();
+                flow::mut_base(kid).floats = floats;
                 kid.assign_height_inorder(ctx);
-                float_ctx = flow::mut_base(kid).floats_out.clone();
+                floats = flow::mut_base(kid).floats.clone();
             }
+
+            // Floats establish a block formatting context, so we discard the output floats here.
+            drop(floats);
         }
         let mut cur_y = Au(0);
         let mut top_offset = Au(0);
@@ -699,7 +704,7 @@ impl Flow for BlockFlow {
             debug!("Setting root position");
             self.base.position.origin = Au::zero_point();
             self.base.position.size.width = ctx.screen_size.width;
-            self.base.floats_in = FloatContext::new(self.base.num_floats);
+            self.base.floats = Floats::new();
             self.base.flags_info.flags.set_inorder(false);
         }
 
@@ -788,7 +793,7 @@ impl Flow for BlockFlow {
             child_base.flags_info.flags.set_inorder(has_inorder_children);
 
             if !child_base.flags_info.flags.inorder() {
-                child_base.floats_in = FloatContext::new(0);
+                child_base.floats = Floats::new();
             }
 
             // Per CSS 2.1 § 16.3.1, text decoration propagates to all children in flow.
diff --git a/src/components/main/layout/box_.rs b/src/components/main/layout/box_.rs
index ff6ccaf93b6..7a230bf09c1 100644
--- a/src/components/main/layout/box_.rs
+++ b/src/components/main/layout/box_.rs
@@ -38,7 +38,7 @@ use css::node_style::StyledNode;
 use layout::construct::FlowConstructor;
 use layout::context::LayoutContext;
 use layout::display_list_builder::{DisplayListBuilder, ExtraDisplayListData, ToGfxColor};
-use layout::float_context::{ClearType, ClearLeft, ClearRight, ClearBoth};
+use layout::floats::{ClearBoth, ClearLeft, ClearRight, ClearType};
 use layout::flow::{Flow, FlowFlagsInfo};
 use layout::flow;
 use layout::model::{MaybeAuto, specified, Auto, Specified};
diff --git a/src/components/main/layout/construct.rs b/src/components/main/layout/construct.rs
index 0b43884c01f..35cba8458bb 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_::{InlineInfo, InlineParentInfo, SpecificBoxInfo, UnscannedTextBox};
 use layout::box_::{UnscannedTextBoxInfo};
 use layout::context::LayoutContext;
-use layout::float_context::FloatType;
+use layout::floats::FloatKind;
 use layout::flow::{Flow, MutableOwnedFlowUtils};
 use layout::inline::InlineFlow;
 use layout::text::TextRunScanner;
@@ -418,9 +418,9 @@ impl<'a> FlowConstructor<'a> {
 
     /// Builds the flow for a node with `float: {left|right}`. This yields a float `BlockFlow` with
     /// a `BlockFlow` underneath it.
-    fn build_flow_for_floated_block(&mut self, node: &ThreadSafeLayoutNode, float_type: FloatType)
+    fn build_flow_for_floated_block(&mut self, node: &ThreadSafeLayoutNode, float_kind: FloatKind)
                                     -> ~Flow {
-        let mut flow = ~BlockFlow::float_from_node(self, node, float_type) as ~Flow;
+        let mut flow = ~BlockFlow::float_from_node(self, node, float_kind) as ~Flow;
         self.build_children_of_block_flow(&mut flow, node);
         flow
     }
@@ -684,8 +684,8 @@ impl<'a> PostorderNodeMutTraversal for FlowConstructor<'a> {
 
             // Floated flows contribute float flow construction results.
             (_, float_value, _) => {
-                let float_type = FloatType::from_property(float_value);
-                let flow = self.build_flow_for_floated_block(node, float_type);
+                let float_kind = FloatKind::from_property(float_value);
+                let flow = self.build_flow_for_floated_block(node, float_kind);
                 node.set_flow_construction_result(FlowConstructionResult(flow))
             }
         }
diff --git a/src/components/main/layout/float_context.rs b/src/components/main/layout/float_context.rs
deleted file mode 100644
index e61d3eb11c7..00000000000
--- a/src/components/main/layout/float_context.rs
+++ /dev/null
@@ -1,392 +0,0 @@
-/* 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/. */
-
-use geom::point::Point2D;
-use geom::rect::Rect;
-use geom::size::Size2D;
-use servo_util::geometry::{Au, max, min};
-use std::i32::max_value;
-use std::util::replace;
-use std::vec;
-use style::computed_values::float;
-
-#[deriving(Clone)]
-pub enum FloatType {
-    FloatLeft,
-    FloatRight
-}
-
-impl FloatType {
-    pub fn from_property(property: float::T) -> FloatType {
-        match property {
-            float::none => fail!("can't create a float type from an unfloated property"),
-            float::left => FloatLeft,
-            float::right => FloatRight,
-        }
-    }
-}
-
-pub enum ClearType {
-    ClearLeft,
-    ClearRight,
-    ClearBoth
-}
-
-struct FloatContextBase {
-    /// This is an option of a vector to avoid allocation in the fast path (no floats).
-    float_data: Option<~[Option<FloatData>]>,
-    floats_used: uint,
-    max_y: Au,
-    offset: Point2D<Au>,
-}
-
-#[deriving(Clone)]
-struct FloatData {
-    bounds: Rect<Au>,
-    f_type: FloatType
-}
-
-/// All information necessary to place a float
-pub struct PlacementInfo {
-    width: Au,      // The dimensions of the float
-    height: Au,
-    ceiling: Au,    // The minimum top of the float, as determined by earlier elements
-    max_width: Au,  // The maximum right of the float, generally determined by the contining block
-    f_type: FloatType // left or right
-}
-
-/// Wrappers around float methods. To avoid allocating data we'll never use,
-/// destroy the context on modification.
-pub enum FloatContext {
-    Invalid,
-    Valid(FloatContextBase)
-}
-
-impl FloatContext {
-    pub fn new(num_floats: uint) -> FloatContext {
-        Valid(FloatContextBase::new(num_floats))
-    }
-
-    #[inline(always)]
-    pub fn clone(&mut self) -> FloatContext {
-        match *self {
-            Invalid => fail!("Can't clone an invalid float context"),
-            Valid(_) => replace(self, Invalid)
-        }
-    }
-
-    #[inline(always)]
-    fn with_mut_base<R>(&mut self, callback: |&mut FloatContextBase| -> R) -> R {
-        match *self {
-            Invalid => fail!("Float context no longer available"),
-            Valid(ref mut base) => callback(&mut *base)
-        }
-    }
-
-    #[inline(always)]
-    pub fn with_base<R>(&self, callback: |&FloatContextBase| -> R) -> R {
-        match *self {
-            Invalid => fail!("Float context no longer available"),
-            Valid(ref base) => callback(&*base)
-        }
-    }
-
-    #[inline(always)]
-    pub fn translate(&mut self, trans: Point2D<Au>) -> FloatContext {
-        self.with_mut_base(|base| {
-            base.translate(trans);
-        });
-        replace(self, Invalid)
-    }
-
-    #[inline(always)]
-    pub fn available_rect(&mut self, top: Au, height: Au, max_x: Au) -> Option<Rect<Au>> {
-        self.with_base(|base| {
-            base.available_rect(top, height, max_x)
-        })
-    }
-
-    #[inline(always)]
-    pub fn add_float(&mut self, info: &PlacementInfo) -> FloatContext{
-        self.with_mut_base(|base| {
-            base.add_float(info);
-        });
-        replace(self, Invalid)
-    }
-
-    #[inline(always)]
-    pub fn place_between_floats(&self, info: &PlacementInfo) -> Rect<Au> {
-        self.with_base(|base| {
-            base.place_between_floats(info)
-        })
-    }
-
-    #[inline(always)]
-    pub fn last_float_pos(&mut self) -> Point2D<Au> {
-        self.with_base(|base| {
-            base.last_float_pos()
-        })
-    }
-
-    #[inline(always)]
-    pub fn clearance(&self, clear: ClearType) -> Au {
-        self.with_base(|base| {
-            base.clearance(clear)
-        })
-    }
-}
-
-impl FloatContextBase {
-    fn new(num_floats: uint) -> FloatContextBase {
-        debug!("Creating float context of size {}", num_floats);
-        FloatContextBase {
-            float_data: if num_floats == 0 {
-                None
-            } else {
-                Some(vec::from_elem(num_floats, None))
-            },
-            floats_used: 0,
-            max_y: Au(0),
-            offset: Point2D(Au(0), Au(0))
-        }
-    }
-
-    fn translate(&mut self, trans: Point2D<Au>) {
-        self.offset = self.offset + trans;
-    }
-
-    fn last_float_pos(&self) -> Point2D<Au> {
-        assert!(self.floats_used > 0, "Error: tried to access FloatContext with no floats in it");
-
-        match self.float_data.get_ref()[self.floats_used - 1] {
-            None => fail!("FloatContext error: floats should never be None here"),
-            Some(float) => {
-                debug!("Returning float position: {}", float.bounds.origin + self.offset);
-                float.bounds.origin + self.offset
-            }
-        }
-    }
-
-    /// Returns a rectangle that encloses the region from top to top + height,
-    /// with width small enough that it doesn't collide with any floats. max_x
-    /// is the x-coordinate beyond which floats have no effect (generally 
-    /// this is the containing block width).
-    fn available_rect(&self, top: Au, height: Au, max_x: Au) -> Option<Rect<Au>> {
-        fn range_intersect(top_1: Au, bottom_1: Au, top_2: Au, bottom_2: Au) -> (Au, Au) {
-            (max(top_1, top_2), min(bottom_1, bottom_2))
-        }
-
-        let top = top - self.offset.y;
-
-        debug!("available_rect: trying to find space at {}", top);
-
-        // Relevant dimensions for the right-most left float
-        let mut max_left = Au(0) - self.offset.x;
-        let mut l_top = None;
-        let mut l_bottom = None;
-        // Relevant dimensions for the left-most right float
-        let mut min_right = max_x - self.offset.x;
-        let mut r_top = None;
-        let mut r_bottom = None;
-
-        // Find the float collisions for the given vertical range.
-        for floats in self.float_data.iter() {
-            for float in floats.iter() {
-                debug!("available_rect: Checking for collision against float");
-                match *float {
-                    None => (),
-                    Some(data) => {
-                        let float_pos = data.bounds.origin;
-                        let float_size = data.bounds.size;
-                        debug!("float_pos: {}, float_size: {}", float_pos, float_size);
-                        match data.f_type {
-                            FloatLeft => {
-                                if(float_pos.x + float_size.width > max_left && 
-                                   float_pos.y + float_size.height > top && float_pos.y < top + height) {
-                                    max_left = float_pos.x + float_size.width;
-                                
-                                    l_top = Some(float_pos.y);
-                                    l_bottom = Some(float_pos.y + float_size.height);
-
-                                    debug!("available_rect: collision with left float: new max_left is {}",
-                                            max_left);
-                                }
-                            }
-                            FloatRight => {
-                                if(float_pos.x < min_right && 
-                                   float_pos.y + float_size.height > top && float_pos.y < top + height) {
-                                    min_right = float_pos.x;
-
-                                    r_top = Some(float_pos.y);
-                                    r_bottom = Some(float_pos.y + float_size.height);
-                                    debug!("available_rect: collision with right float: new min_right is {}",
-                                            min_right);
-                                }
-                            }
-                        }
-                    }
-                }
-            };
-        }
-
-        // Extend the vertical range of the rectangle to the closest floats.
-        // If there are floats on both sides, take the intersection of the
-        // two areas. Also make sure we never return a top smaller than the
-        // given upper bound.
-        let (top, bottom) = match (r_top, r_bottom, l_top, l_bottom) {
-            (Some(r_top), Some(r_bottom), Some(l_top), Some(l_bottom)) => 
-                range_intersect(max(top, r_top), r_bottom, max(top, l_top), l_bottom),
-
-            (None, None, Some(l_top), Some(l_bottom)) => (max(top, l_top), l_bottom),
-            (Some(r_top), Some(r_bottom), None, None) => (max(top, r_top), r_bottom),
-            (None, None, None, None) => return None,
-            _ => fail!("Reached unreachable state when computing float area")
-        };
-
-        // This assertion is too strong and fails in some cases. It is OK to
-        // return negative widths since we check against that right away, but
-        // we should still undersrtand why they occur and add a stronger
-        // assertion here.
-        //assert!(max_left < min_right); 
-        
-        assert!(top <= bottom, "Float position error");
-
-        Some(Rect{
-            origin: Point2D(max_left, top) + self.offset,
-            size: Size2D(min_right - max_left, bottom - top)
-        })
-    }
-
-    fn add_float(&mut self, info: &PlacementInfo) {
-        assert!(self.float_data.is_some());
-        debug!("Floats_used: {}, Floats available: {}",
-               self.floats_used,
-               self.float_data.get_ref().len());
-        assert!(self.floats_used < self.float_data.get_ref().len() && 
-                self.float_data.get_ref()[self.floats_used].is_none());
-
-        let new_info = PlacementInfo {
-            width: info.width,
-            height: info.height,
-            ceiling: max(info.ceiling, self.max_y + self.offset.y),
-            max_width: info.max_width,
-            f_type: info.f_type
-        };
-
-        debug!("add_float: added float with info {:?}", new_info);
-
-        let new_float = FloatData {    
-            bounds: Rect {
-                origin: self.place_between_floats(&new_info).origin - self.offset,
-                size: Size2D(info.width, info.height)
-            },
-            f_type: info.f_type
-        };
-        self.float_data.get_mut_ref()[self.floats_used] = Some(new_float);
-        self.max_y = max(self.max_y, new_float.bounds.origin.y);
-        self.floats_used += 1;
-    }
-
-    /// Given the top 3 sides of the rectange, finds the largest height that
-    /// will result in the rectange not colliding with any floats. Returns
-    /// None if that height is infinite.
-    fn max_height_for_bounds(&self, left: Au, top: Au, width: Au) -> Option<Au> {
-        let top = top - self.offset.y;
-        let left = left - self.offset.x;
-        let mut max_height = None;
-
-        for floats in self.float_data.iter() {
-            for float in floats.iter() {
-                match *float {
-                    None => (),
-                    Some(f_data) => {
-                        if f_data.bounds.origin.y + f_data.bounds.size.height > top &&
-                           f_data.bounds.origin.x + f_data.bounds.size.width > left &&
-                           f_data.bounds.origin.x < left + width {
-                               let new_y = f_data.bounds.origin.y;
-                               max_height = Some(min(max_height.unwrap_or(new_y), new_y));
-                           }
-                    }
-                }
-            }
-        }
-
-        max_height.map(|h| h + self.offset.y)
-    }
-
-    /// Given necessary info, finds the closest place a box can be positioned
-    /// without colliding with any floats.
-    fn place_between_floats(&self, info: &PlacementInfo) -> Rect<Au>{
-        debug!("place_float: Placing float with width {} and height {}", info.width, info.height);
-        // Can't go any higher than previous floats or
-        // previous elements in the document.
-        let mut float_y = info.ceiling;
-        loop {
-            let maybe_location = self.available_rect(float_y, info.height, info.max_width);
-            debug!("place_float: Got available rect: {:?} for y-pos: {}", maybe_location, float_y);
-            match maybe_location {
-
-                // If there are no floats blocking us, return the current location
-                // TODO(eatkinson): integrate with overflow
-                None => return match info.f_type { 
-                    FloatLeft => Rect(Point2D(Au(0), float_y), 
-                                      Size2D(info.max_width, Au(max_value))),
-
-                    FloatRight => Rect(Point2D(info.max_width - info.width, float_y), 
-                                       Size2D(info.max_width, Au(max_value)))
-                },
-
-                Some(rect) => {
-                    assert!(rect.origin.y + rect.size.height != float_y, 
-                            "Non-terminating float placement");
-                    
-                    // Place here if there is enough room
-                    if (rect.size.width >= info.width) {
-                        let height = self.max_height_for_bounds(rect.origin.x, 
-                                                                rect.origin.y, 
-                                                                rect.size.width);
-                        let height = height.unwrap_or(Au(max_value));
-                        return match info.f_type {
-                            FloatLeft => Rect(Point2D(rect.origin.x, float_y),
-                                              Size2D(rect.size.width, height)),
-                            FloatRight => {
-                                Rect(Point2D(rect.origin.x + rect.size.width - info.width, float_y),
-                                     Size2D(rect.size.width, height))
-                            }
-                        };
-                    }
-
-                    // Try to place at the next-lowest location.
-                    // Need to be careful of fencepost errors.
-                    float_y = rect.origin.y + rect.size.height;
-                }
-            }
-        }
-    }
-
-    fn clearance(&self, clear: ClearType) -> Au {
-        let mut clearance = Au(0);
-        for floats in self.float_data.iter() {
-            for float in floats.iter() {
-                match *float {
-                    None => (),
-                    Some(f_data) => {
-                        match (clear, f_data.f_type) {
-                            (ClearLeft, FloatLeft) |
-                            (ClearRight, FloatRight) |
-                            (ClearBoth, _) => {
-                                clearance = max(
-                                    clearance,
-                                    self.offset.y + f_data.bounds.origin.y + f_data.bounds.size.height);
-                            }
-                            _ => ()
-                        }
-                    }
-                }
-            }
-        }
-        clearance
-    }
-}
-
diff --git a/src/components/main/layout/floats.rs b/src/components/main/layout/floats.rs
new file mode 100644
index 00000000000..7e42928770a
--- /dev/null
+++ b/src/components/main/layout/floats.rs
@@ -0,0 +1,383 @@
+/* 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/. */
+
+use geom::point::Point2D;
+use geom::rect::Rect;
+use geom::size::Size2D;
+use servo_util::cowarc::CowArc;
+use servo_util::geometry::{Au, max, min};
+use std::i32;
+use style::computed_values::float;
+
+/// The kind of float: left or right.
+#[deriving(Clone)]
+pub enum FloatKind {
+    FloatLeft,
+    FloatRight
+}
+
+impl FloatKind {
+    pub fn from_property(property: float::T) -> FloatKind {
+        match property {
+            float::none => fail!("can't create a float type from an unfloated property"),
+            float::left => FloatLeft,
+            float::right => FloatRight,
+        }
+    }
+}
+
+/// The kind of clearance: left, right, or both.
+pub enum ClearType {
+    ClearLeft,
+    ClearRight,
+    ClearBoth,
+}
+
+/// Information about a single float.
+#[deriving(Clone)]
+struct Float {
+    /// The boundaries of this float.
+    bounds: Rect<Au>,
+    /// The kind of float: left or right.
+    kind: FloatKind,
+}
+
+/// Information about the floats next to a flow.
+///
+/// FIXME(pcwalton): When we have fast `MutexArc`s, try removing `#[deriving(Clone)]` and wrap in a
+/// mutex.
+#[deriving(Clone)]
+struct FloatList {
+    /// Information about each of the floats here.
+    floats: ~[Float],
+    /// Cached copy of the maximum top offset of the float.
+    max_top: Au,
+}
+
+impl FloatList {
+    fn new() -> FloatList {
+        FloatList {
+            floats: ~[],
+            max_top: Au(0),
+        }
+    }
+}
+
+/// Wraps a `FloatList` to avoid allocation in the common case of no floats.
+///
+/// FIXME(pcwalton): When we have fast `MutexArc`s, try removing `CowArc` and use a mutex instead.
+#[deriving(Clone)]
+struct FloatListRef {
+    list: Option<CowArc<FloatList>>,
+}
+
+impl FloatListRef {
+    fn new() -> FloatListRef {
+        FloatListRef {
+            list: None,
+        }
+    }
+
+    /// Returns true if the list is allocated and false otherwise. If false, there are guaranteed
+    /// not to be any floats.
+    fn is_present(&self) -> bool {
+        self.list.is_some()
+    }
+
+    #[inline]
+    fn get<'a>(&'a self) -> Option<&'a FloatList> {
+        match self.list {
+            None => None,
+            Some(ref list) => Some(list.get()),
+        }
+    }
+
+    #[inline]
+    fn get_mut<'a>(&'a mut self) -> &'a mut FloatList {
+        if self.list.is_none() {
+            self.list = Some(CowArc::new(FloatList::new()))
+        }
+        self.list.as_mut().unwrap().get_mut()
+    }
+}
+
+/// All the information necessary to place a float.
+pub struct PlacementInfo {
+    /// The dimensions of the float.
+    size: Size2D<Au>,
+    /// The minimum top of the float, as determined by earlier elements.
+    ceiling: Au,
+    /// The maximum right position of the float, generally determined by the containing block.
+    max_width: Au,
+    /// The kind of float.
+    kind: FloatKind
+}
+
+fn range_intersect(top_1: Au, bottom_1: Au, top_2: Au, bottom_2: Au) -> (Au, Au) {
+    (max(top_1, top_2), min(bottom_1, bottom_2))
+}
+
+/// Encapsulates information about floats. This is optimized to avoid allocation if there are
+/// no floats, and to avoid copying when translating the list of floats downward.
+#[deriving(Clone)]
+pub struct Floats {
+    /// The list of floats.
+    priv list: FloatListRef,
+    /// The offset of the flow relative to the first float.
+    priv offset: Point2D<Au>,
+}
+
+impl Floats {
+    /// Creates a new `Floats` object.
+    pub fn new() -> Floats {
+        Floats {
+            list: FloatListRef::new(),
+            offset: Point2D(Au(0), Au(0)),
+        }
+    }
+
+    /// Adjusts the recorded offset of the flow relative to the first float.
+    pub fn translate(&mut self, delta: Point2D<Au>) {
+        self.offset = self.offset + delta
+    }
+
+    /// Returns the position of the last float in flow coordinates.
+    pub fn last_float_pos(&self) -> Option<Point2D<Au>> {
+        match self.list.get() {
+            None => None,
+            Some(list) => {
+                match list.floats.last_opt() {
+                    None => None,
+                    Some(float) => Some(float.bounds.origin + self.offset),
+                }
+            }
+        }
+    }
+
+    /// Returns a rectangle that encloses the region from top to top + height, with width small
+    /// enough that it doesn't collide with any floats. max_x is the x-coordinate beyond which
+    /// floats have no effect. (Generally this is the containing block width.)
+    pub fn available_rect(&self, top: Au, height: Au, max_x: Au) -> Option<Rect<Au>> {
+        let list = match self.list.get() {
+            None => return None,
+            Some(list) => list,
+        };
+
+        let top = top - self.offset.y;
+
+        debug!("available_rect: trying to find space at {}", top);
+
+        // Relevant dimensions for the right-most left float
+        let mut max_left = Au(0) - self.offset.x;
+        let mut l_top = None;
+        let mut l_bottom = None;
+        // Relevant dimensions for the left-most right float
+        let mut min_right = max_x - self.offset.x;
+        let mut r_top = None;
+        let mut r_bottom = None;
+
+        // Find the float collisions for the given vertical range.
+        for float in list.floats.iter() {
+            debug!("available_rect: Checking for collision against float");
+            let float_pos = float.bounds.origin;
+            let float_size = float.bounds.size;
+
+            debug!("float_pos: {}, float_size: {}", float_pos, float_size);
+            match float.kind {
+                FloatLeft if float_pos.x + float_size.width > max_left && 
+                        float_pos.y + float_size.height > top && float_pos.y < top + height => {
+                    max_left = float_pos.x + float_size.width;
+                
+                    l_top = Some(float_pos.y);
+                    l_bottom = Some(float_pos.y + float_size.height);
+
+                    debug!("available_rect: collision with left float: new max_left is {}",
+                            max_left);
+                }
+                FloatRight if float_pos.x < min_right && 
+                       float_pos.y + float_size.height > top && float_pos.y < top + height => {
+                    min_right = float_pos.x;
+
+                    r_top = Some(float_pos.y);
+                    r_bottom = Some(float_pos.y + float_size.height);
+                    debug!("available_rect: collision with right float: new min_right is {}",
+                            min_right);
+                }
+                FloatLeft | FloatRight => {}
+            }
+        }
+
+        // Extend the vertical range of the rectangle to the closest floats.
+        // If there are floats on both sides, take the intersection of the
+        // two areas. Also make sure we never return a top smaller than the
+        // given upper bound.
+        let (top, bottom) = match (r_top, r_bottom, l_top, l_bottom) {
+            (Some(r_top), Some(r_bottom), Some(l_top), Some(l_bottom)) => 
+                range_intersect(max(top, r_top), r_bottom, max(top, l_top), l_bottom),
+
+            (None, None, Some(l_top), Some(l_bottom)) => (max(top, l_top), l_bottom),
+            (Some(r_top), Some(r_bottom), None, None) => (max(top, r_top), r_bottom),
+            (None, None, None, None) => return None,
+            _ => fail!("Reached unreachable state when computing float area")
+        };
+
+        // FIXME(eatkinson): This assertion is too strong and fails in some cases. It is OK to
+        // return negative widths since we check against that right away, but we should still
+        // undersrtand why they occur and add a stronger assertion here.
+        // assert!(max_left < min_right); 
+        
+        assert!(top <= bottom, "Float position error");
+
+        Some(Rect {
+            origin: Point2D(max_left, top) + self.offset,
+            size: Size2D(min_right - max_left, bottom - top)
+        })
+    }
+
+    /// Adds a new float to the list.
+    pub fn add_float(&mut self, info: &PlacementInfo) {
+        let new_info;
+        {
+            let list = self.list.get_mut();
+            new_info = PlacementInfo {
+                size: info.size,
+                ceiling: max(info.ceiling, list.max_top + self.offset.y),
+                max_width: info.max_width,
+                kind: info.kind
+            }
+        }
+
+        debug!("add_float: added float with info {:?}", new_info);
+
+        let new_float = Float {
+            bounds: Rect {
+                origin: self.place_between_floats(&new_info).origin - self.offset,
+                size: info.size,
+            },
+            kind: info.kind
+        };
+
+        let list = self.list.get_mut();
+        list.floats.push(new_float);
+        list.max_top = max(list.max_top, new_float.bounds.origin.y);
+    }
+
+    /// Given the top 3 sides of the rectangle, finds the largest height that will result in the
+    /// rectangle not colliding with any floats. Returns None if that height is infinite.
+    fn max_height_for_bounds(&self, left: Au, top: Au, width: Au) -> Option<Au> {
+        let list = match self.list.get() {
+            None => return None,
+            Some(list) => list,
+        };
+
+        let top = top - self.offset.y;
+        let left = left - self.offset.x;
+        let mut max_height = None;
+
+        for float in list.floats.iter() {
+            if float.bounds.origin.y + float.bounds.size.height > top &&
+                   float.bounds.origin.x + float.bounds.size.width > left &&
+                   float.bounds.origin.x < left + width {
+               let new_y = float.bounds.origin.y;
+               max_height = Some(min(max_height.unwrap_or(new_y), new_y));
+            }
+        }
+
+        max_height.map(|h| h + self.offset.y)
+    }
+
+    /// Given placement information, finds the closest place a box can be positioned without
+    /// colliding with any floats.
+    pub fn place_between_floats(&self, info: &PlacementInfo) -> Rect<Au> {
+        debug!("place_between_floats: Placing object with width {} and height {}",
+               info.size.width,
+               info.size.height);
+
+        // If no floats, use this fast path.
+        if !self.list.is_present() {
+            match info.kind {
+                FloatLeft => {
+                    return Rect(Point2D(Au(0), info.ceiling),
+                                Size2D(info.max_width, Au(i32::max_value)))
+                }
+                FloatRight => {
+                    return Rect(Point2D(info.max_width - info.size.width, info.ceiling),
+                                Size2D(info.max_width, Au(i32::max_value)))
+                }
+            }
+        }
+
+        // Can't go any higher than previous floats or previous elements in the document.
+        let mut float_y = info.ceiling;
+        loop {
+            let maybe_location = self.available_rect(float_y, info.size.height, info.max_width);
+            debug!("place_float: Got available rect: {:?} for y-pos: {}", maybe_location, float_y);
+            match maybe_location {
+                // If there are no floats blocking us, return the current location
+                // TODO(eatkinson): integrate with overflow
+                None => {
+                    return match info.kind { 
+                        FloatLeft => {
+                            Rect(Point2D(Au(0), float_y),
+                                 Size2D(info.max_width, Au(i32::max_value)))
+                        }
+                        FloatRight => {
+                            Rect(Point2D(info.max_width - info.size.width, float_y), 
+                                         Size2D(info.max_width, Au(i32::max_value)))
+                        }
+                    }
+                }
+                Some(rect) => {
+                    assert!(rect.origin.y + rect.size.height != float_y, 
+                            "Non-terminating float placement");
+                    
+                    // Place here if there is enough room
+                    if rect.size.width >= info.size.width {
+                        let height = self.max_height_for_bounds(rect.origin.x, 
+                                                                rect.origin.y, 
+                                                                rect.size.width);
+                        let height = height.unwrap_or(Au(i32::max_value));
+                        return match info.kind {
+                            FloatLeft => {
+                                Rect(Point2D(rect.origin.x, float_y),
+                                             Size2D(rect.size.width, height))
+                            }
+                            FloatRight => {
+                                Rect(Point2D(rect.origin.x + rect.size.width - info.size.width,
+                                             float_y),
+                                     Size2D(rect.size.width, height))
+                            }
+                        }
+                    }
+
+                    // Try to place at the next-lowest location.
+                    // Need to be careful of fencepost errors.
+                    float_y = rect.origin.y + rect.size.height;
+                }
+            }
+        }
+    }
+
+    pub fn clearance(&self, clear: ClearType) -> Au {
+        let list = match self.list.get() {
+            None => return Au(0),
+            Some(list) => list,
+        };
+
+        let mut clearance = Au(0);
+        for float in list.floats.iter() {
+            match (clear, float.kind) {
+                (ClearLeft, FloatLeft) |
+                (ClearRight, FloatRight) |
+                (ClearBoth, _) => {
+                    let y = self.offset.y + float.bounds.origin.y + float.bounds.size.height;
+                    clearance = max(clearance, y);
+                }
+                _ => {}
+            }
+        }
+        clearance
+    }
+}
+
diff --git a/src/components/main/layout/flow.rs b/src/components/main/layout/flow.rs
index b4a14a53ad9..b476e8b07b7 100644
--- a/src/components/main/layout/flow.rs
+++ b/src/components/main/layout/flow.rs
@@ -30,7 +30,7 @@ use layout::block::BlockFlow;
 use layout::box_::Box;
 use layout::context::LayoutContext;
 use layout::display_list_builder::{DisplayListBuilder, ExtraDisplayListData};
-use layout::float_context::{FloatContext, Invalid};
+use layout::floats::Floats;
 use layout::incremental::RestyleDamage;
 use layout::inline::InlineFlow;
 use layout::parallel::FlowParallelInfo;
@@ -511,9 +511,13 @@ pub struct BaseFlow {
     /// TODO(pcwalton): Group with other transient data to save space.
     parallel: FlowParallelInfo,
 
-    floats_in: FloatContext,
-    floats_out: FloatContext,
+    /// The floats next to this flow.
+    floats: Floats,
+
+    /// The number of floated descendants of this flow (including this flow, if it's floated).
     num_floats: uint,
+
+    /// The position of this flow in page coordinates, computed during display list construction.
     abs_position: Point2D<Au>,
 
     /// Whether this flow has been destroyed.
@@ -569,8 +573,7 @@ impl BaseFlow {
 
             parallel: FlowParallelInfo::new(),
 
-            floats_in: Invalid,
-            floats_out: Invalid,
+            floats: Floats::new(),
             num_floats: 0,
             abs_position: Point2D(Au::new(0), Au::new(0)),
 
diff --git a/src/components/main/layout/inline.rs b/src/components/main/layout/inline.rs
index e6a2643536f..4292ab32274 100644
--- a/src/components/main/layout/inline.rs
+++ b/src/components/main/layout/inline.rs
@@ -7,9 +7,9 @@ use layout::box_::{Box, CannotSplit, GenericBox, IframeBox, ImageBox, ScannedTex
 use layout::box_::{SplitDidNotFit, UnscannedTextBox, InlineInfo};
 use layout::context::LayoutContext;
 use layout::display_list_builder::{DisplayListBuilder, ExtraDisplayListData};
+use layout::floats::{FloatLeft, Floats, PlacementInfo};
 use layout::flow::{BaseFlow, FlowClass, Flow, InlineFlowClass};
 use layout::flow;
-use layout::float_context::{FloatContext, FloatLeft, PlacementInfo};
 use layout::util::ElementMapping;
 use layout::wrapper::ThreadSafeLayoutNode;
 
@@ -56,7 +56,7 @@ struct LineBox {
 }
 
 struct LineboxScanner {
-    floats: FloatContext,
+    floats: Floats,
     new_boxes: ~[Box],
     work_list: RingBuf<Box>,
     pending_line: LineBox,
@@ -65,7 +65,7 @@ struct LineboxScanner {
 }
 
 impl LineboxScanner {
-    pub fn new(float_ctx: FloatContext) -> LineboxScanner {
+    pub fn new(float_ctx: Floats) -> LineboxScanner {
         LineboxScanner {
             floats: float_ctx,
             new_boxes: ~[],
@@ -80,7 +80,7 @@ impl LineboxScanner {
         }
     }
 
-    pub fn floats_out(&mut self) -> FloatContext {
+    pub fn floats(&mut self) -> Floats {
         self.floats.clone()
     }
 
@@ -193,11 +193,10 @@ impl LineboxScanner {
         };
 
         let mut info = PlacementInfo {
-            width: placement_width,
-            height: first_box_size.height,
+            size: Size2D(placement_width, first_box_size.height),
             ceiling: ceiling,
             max_width: flow.base.position.size.width,
-            f_type: FloatLeft
+            kind: FloatLeft,
         };
 
         let line_bounds = self.floats.place_between_floats(&info);
@@ -253,7 +252,7 @@ impl LineboxScanner {
                     (None, None)            => fail!("This case makes no sense.")
                 };
 
-                info.width = actual_box_width;
+                info.size.width = actual_box_width;
                 let new_bounds = self.floats.place_between_floats(&info);
 
                 debug!("LineboxScanner: case=new line position: {}", new_bounds);
@@ -626,7 +625,7 @@ impl Flow for InlineFlow {
         for kid in self.base.child_iter() {
             let child_base = flow::mut_base(kid);
             num_floats += child_base.num_floats;
-            child_base.floats_in = FloatContext::new(child_base.num_floats);
+            child_base.floats = Floats::new();
         }
 
         let mut min_width = Au::new(0);
@@ -653,7 +652,7 @@ impl Flow for InlineFlow {
         //
         // TODO: Combine this with `LineboxScanner`'s walk in the box list, or put this into `Box`.
 
-        debug!("InlineFlow::assign_widths: floats_in: {:?}", self.base.floats_in);
+        debug!("InlineFlow::assign_widths: floats in: {:?}", self.base.floats);
 
         {
             let this = &mut *self;
@@ -698,12 +697,12 @@ impl Flow for InlineFlow {
         // determine its height for computing linebox height.
         //
         // TODO(pcwalton): Cache the linebox scanner?
-        debug!("assign_height_inline: floats_in: {:?}", self.base.floats_in);
+        debug!("assign_height_inline: floats in: {:?}", self.base.floats);
         // assign height for inline boxes
         for box_ in self.boxes.iter() {
             box_.assign_height();
         }
-        let scanner_floats = self.base.floats_in.clone();
+        let scanner_floats = self.base.floats.clone();
         let mut scanner = LineboxScanner::new(scanner_floats);
 
         // Access the linebox scanner.
@@ -880,9 +879,8 @@ impl Flow for InlineFlow {
                 Au::new(0)
             };
 
-        self.base.floats_out = scanner.floats_out()
-                                      .translate(Point2D(Au::new(0),
-                                                         -self.base.position.size.height));
+        self.base.floats = scanner.floats();
+        self.base.floats.translate(Point2D(Au::new(0), -self.base.position.size.height));
     }
 
     fn collapse_margins(&mut self,
diff --git a/src/components/main/servo.rs b/src/components/main/servo.rs
index 53071519273..48e29f2a975 100755
--- a/src/components/main/servo.rs
+++ b/src/components/main/servo.rs
@@ -90,7 +90,7 @@ pub mod layout {
     pub mod construct;
     pub mod context;
     pub mod display_list_builder;
-    pub mod float_context;
+    pub mod floats;
     pub mod flow;
     pub mod flow_list;
     pub mod layout_task;