/* 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 app_units::{Au, MAX_AU};
use block::FormattingContextType;
use flow::{Flow, FlowFlags, GetBaseFlow, ImmutableFlowUtils};
use persistent_list::PersistentList;
use std::cmp::{max, min};
use std::fmt;
use style::computed_values::float::T as StyleFloat;
use style::logical_geometry::{LogicalRect, LogicalSize, WritingMode};
use style::values::computed::LengthOrPercentageOrAuto;
/// The kind of float: left or right.
#[derive(Clone, Copy, Debug, Serialize)]
pub enum FloatKind {
Left,
Right
}
impl FloatKind {
pub fn from_property(property: StyleFloat) -> Option<FloatKind> {
match property {
StyleFloat::None => None,
StyleFloat::Left => Some(FloatKind::Left),
StyleFloat::Right => Some(FloatKind::Right),
}
}
}
/// The kind of clearance: left, right, or both.
#[derive(Clone, Copy)]
pub enum ClearType {
Left,
Right,
Both,
}
/// Information about a single float.
#[derive(Clone, Copy)]
struct Float {
/// The boundaries of this float.
bounds: LogicalRect<Au>,
/// The kind of float: left or right.
kind: FloatKind,
}
impl fmt::Debug for Float {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "bounds={:?} kind={:?}", self.bounds, self.kind)
}
}
/// Information about the floats next to a flow.
#[derive(Clone)]
struct FloatList {
/// Information about each of the floats here.
floats: PersistentList<Float>,
/// Cached copy of the maximum block-start offset of the float.
max_block_start: Option<Au>,
}
impl FloatList {
fn new() -> FloatList {
FloatList {
floats: PersistentList::new(),
max_block_start: 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.floats.len() > 0
}
}
impl fmt::Debug for FloatList {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "max_block_start={:?} floats={}", self.max_block_start, self.floats.len())?;
for float in self.floats.iter() {
write!(f, " {:?}", float)?;
}
Ok(())
}
}
/// All the information necessary to place a float.
pub struct PlacementInfo {
/// The dimensions of the float.
pub size: LogicalSize<Au>,
/// The minimum block-start of the float, as determined by earlier elements.
pub ceiling: Au,
/// The maximum inline-end position of the float, generally determined by the containing block.
pub max_inline_size: Au,
/// The kind of float.
pub kind: FloatKind
}
impl fmt::Debug for PlacementInfo {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f,
"size={:?} ceiling={:?} max_inline_size={:?} kind={:?}",
self.size,
self.ceiling,
self.max_inline_size,
self.kind)
}
}
fn range_intersect(block_start_1: Au, block_end_1: Au, block_start_2: Au, block_end_2: Au) -> (Au, Au) {
(max(block_start_1, block_start_2), min(block_end_1, block_end_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.
#[derive(Clone)]
pub struct Floats {
/// The list of floats.
list: FloatList,
/// The offset of the flow relative to the first float.
offset: LogicalSize<Au>,
/// The writing mode of these floats.
pub writing_mode: WritingMode,
}
impl fmt::Debug for Floats {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
if !self.list.is_present() {
write!(f, "[empty]")
} else {
write!(f, "offset={:?} floats={:?}", self.offset, self.list)
}
}
}
impl Floats {
/// Creates a new `Floats` object.
pub fn new(writing_mode: WritingMode) -> Floats {
Floats {
list: FloatList::new(),
offset: LogicalSize::zero(writing_mode),
writing_mode: writing_mode,
}
}
/// Adjusts the recorded offset of the flow relative to the first float.
pub fn translate(&mut self, delta: LogicalSize<Au>) {
self.offset = self.offset + delta
}
/// Returns the position of the last float in flow coordinates.
pub fn last_float_pos(&self) -> Option<LogicalRect<Au>> {
match self.list.floats.front() {
None => None,
Some(float) => Some(float.bounds.translate_by_size(self.offset)),
}
}
/// Returns a rectangle that encloses the region from block-start to block-start + block-size,
/// with inline-size small enough that it doesn't collide with any floats. max_x is the
/// inline-size beyond which floats have no effect. (Generally this is the containing block
/// inline-size.)
pub fn available_rect(&self, block_start: Au, block_size: Au, max_x: Au)
-> Option<LogicalRect<Au>> {
let list = &self.list;
let block_start = block_start - self.offset.block;
debug!("available_rect: trying to find space at {:?}", block_start);
// Relevant dimensions for the inline-end-most inline-start float
let mut max_inline_start = Au(0) - self.offset.inline;
let mut l_block_start = None;
let mut l_block_end = None;
// Relevant dimensions for the inline-start-most inline-end float
let mut min_inline_end = max_x - self.offset.inline;
let mut r_block_start = None;
let mut r_block_end = None;
// Find the float collisions for the given range in the block direction.
for float in list.floats.iter() {
debug!("available_rect: Checking for collision against float");
let float_pos = float.bounds.start;
let float_size = float.bounds.size;
debug!("float_pos: {:?}, float_size: {:?}", float_pos, float_size);
match float.kind {
FloatKind::Left if float_pos.i + float_size.inline > max_inline_start &&
float_pos.b + float_size.block > block_start &&
float_pos.b < block_start + block_size => {
max_inline_start = float_pos.i + float_size.inline;
l_block_start = Some(float_pos.b);
l_block_end = Some(float_pos.b + float_size.block);
debug!("available_rect: collision with inline_start float: new \
max_inline_start is {:?}",
max_inline_start);
}
FloatKind::Right if float_pos.i < min_inline_end &&
float_pos.b + float_size.block > block_start &&
float_pos.b < block_start + block_size => {
min_inline_end = float_pos.i;
r_block_start = Some(float_pos.b);
r_block_end = Some(float_pos.b + float_size.block);
debug!("available_rect: collision with inline_end float: new min_inline_end \
is {:?}",
min_inline_end);
}
FloatKind::Left | FloatKind::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 block-start smaller than the
// given upper bound.
let (block_start, block_end) = match (r_block_start,
r_block_end,
l_block_start,
l_block_end) {
(Some(r_block_start), Some(r_block_end), Some(l_block_start), Some(l_block_end)) => {
range_intersect(max(block_start, r_block_start),
r_block_end,
max(block_start, l_block_start),
l_block_end)
}
(None, None, Some(l_block_start), Some(l_block_end)) => {
(max(block_start, l_block_start), l_block_end)
}
(Some(r_block_start), Some(r_block_end), None, None) => {
(max(block_start, r_block_start), r_block_end)
}
(None, None, None, None) => return None,
_ => panic!("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 inline-sizes since we check against that inline-end away, but we should
// still understand why they occur and add a stronger assertion here.
// assert!(max_inline-start < min_inline-end);
assert!(block_start <= block_end, "Float position error");
Some(LogicalRect::new(self.writing_mode,
max_inline_start + self.offset.inline,
block_start + self.offset.block,
min_inline_end - max_inline_start,
block_end - block_start))
}
/// Adds a new float to the list.
pub fn add_float(&mut self, info: &PlacementInfo) {
let new_info = PlacementInfo {
size: info.size,
ceiling: match self.list.max_block_start {
None => info.ceiling,
Some(max_block_start) => max(info.ceiling, max_block_start + self.offset.block),
},
max_inline_size: info.max_inline_size,
kind: info.kind
};
debug!("add_float: added float with info {:?}", new_info);
let new_float = Float {
bounds: LogicalRect::from_point_size(
self.writing_mode,
self.place_between_floats(&new_info).start - self.offset,
info.size,
),
kind: info.kind
};
self.list.floats = self.list.floats.prepend_elem(new_float);
self.list.max_block_start = match self.list.max_block_start {
None => Some(new_float.bounds.start.b),
Some(max_block_start) => Some(max(max_block_start, new_float.bounds.start.b)),
}
}
/// Given the three sides of the bounding rectangle in the block-start direction, finds the
/// largest block-size that will result in the rectangle not colliding with any floats. Returns
/// `None` if that block-size is infinite.
fn max_block_size_for_bounds(&self, inline_start: Au, block_start: Au, inline_size: Au)
-> Option<Au> {
let list = &self.list;
let block_start = block_start - self.offset.block;
let inline_start = inline_start - self.offset.inline;
let mut max_block_size = None;
for float in list.floats.iter() {
if float.bounds.start.b + float.bounds.size.block > block_start &&
float.bounds.start.i + float.bounds.size.inline > inline_start &&
float.bounds.start.i < inline_start + inline_size {
let new_y = float.bounds.start.b;
max_block_size = Some(min(max_block_size.unwrap_or(new_y), new_y));
}
}
max_block_size.map(|h| h + self.offset.block)
}
/// Given placement information, finds the closest place a fragment can be positioned without
/// colliding with any floats.
pub fn place_between_floats(&self, info: &PlacementInfo) -> LogicalRect<Au> {
debug!("place_between_floats: Placing object with {:?}", info.size);
// If no floats, use this fast path.
if !self.list.is_present() {
match info.kind {
FloatKind::Left => {
return LogicalRect::new(
self.writing_mode,
Au(0),
info.ceiling,
info.max_inline_size,
MAX_AU)
}
FloatKind::Right => {
return LogicalRect::new(
self.writing_mode,
info.max_inline_size - info.size.inline,
info.ceiling,
info.max_inline_size,
MAX_AU)
}
}
}
// Can't go any higher than previous floats or previous elements in the document.
let mut float_b = info.ceiling;
loop {
let maybe_location = self.available_rect(float_b,
info.size.block,
info.max_inline_size);
debug!("place_float: got available rect: {:?} for block-pos: {:?}",
maybe_location,
float_b);
match maybe_location {
// If there are no floats blocking us, return the current location
// TODO(eatkinson): integrate with overflow
None => {
return match info.kind {
FloatKind::Left => {
LogicalRect::new(
self.writing_mode,
Au(0),
float_b,
info.max_inline_size,
MAX_AU)
}
FloatKind::Right => {
LogicalRect::new(
self.writing_mode,
info.max_inline_size - info.size.inline,
float_b,
info.max_inline_size,
MAX_AU)
}
}
}
Some(rect) => {
assert_ne!(rect.start.b + rect.size.block, float_b,
"Non-terminating float placement");
// Place here if there is enough room
if rect.size.inline >= info.size.inline {
let block_size = self.max_block_size_for_bounds(rect.start.i,
rect.start.b,
rect.size.inline);
let block_size = block_size.unwrap_or(MAX_AU);
return match info.kind {
FloatKind::Left => {
LogicalRect::new(
self.writing_mode,
rect.start.i,
float_b,
rect.size.inline,
block_size)
}
FloatKind::Right => {
LogicalRect::new(
self.writing_mode,
rect.start.i + rect.size.inline - info.size.inline,
float_b,
rect.size.inline,
block_size)
}
}
}
// Try to place at the next-lowest location.
// Need to be careful of fencepost errors.
float_b = rect.start.b + rect.size.block;
}
}
}
}
pub fn clearance(&self, clear: ClearType) -> Au {
let list = &self.list;
let mut clearance = Au(0);
for float in list.floats.iter() {
match (clear, float.kind) {
(ClearType::Left, FloatKind::Left) |
(ClearType::Right, FloatKind::Right) |
(ClearType::Both, _) => {
let b = self.offset.block + float.bounds.start.b + float.bounds.size.block;
clearance = max(clearance, b);
}
_ => {}
}
}
clearance
}
pub fn is_present(&self) -> bool {
self.list.is_present()
}
}
/// The speculated inline sizes of floats flowing through or around a flow (depending on whether
/// the flow is a block formatting context). These speculations are always *upper bounds*; the
/// actual inline sizes might be less. Note that this implies that a speculated value of zero is a
/// guarantee that there will be no floats on that side.
///
/// This is used for two purposes: (a) determining whether we can lay out blocks in parallel; (b)
/// guessing the inline-sizes of block formatting contexts in an effort to lay them out in
/// parallel.
#[derive(Clone, Copy)]
pub struct SpeculatedFloatPlacement {
/// The estimated inline size (an upper bound) of the left floats flowing through this flow.
pub left: Au,
/// The estimated inline size (an upper bound) of the right floats flowing through this flow.
pub right: Au,
}
impl fmt::Debug for SpeculatedFloatPlacement {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "L {:?} R {:?}", self.left, self.right)
}
}
impl SpeculatedFloatPlacement {
/// Returns a `SpeculatedFloatPlacement` objects with both left and right speculated inline
/// sizes initialized to zero.
pub fn zero() -> SpeculatedFloatPlacement {
SpeculatedFloatPlacement {
left: Au(0),
right: Au(0),
}
}
/// Given the speculated inline size of the floats out for the inorder predecessor of this
/// flow, computes the speculated inline size of the floats flowing in.
pub fn compute_floats_in(&mut self, flow: &mut Flow) {
let base_flow = flow.base();
if base_flow.flags.contains(FlowFlags::CLEARS_LEFT) {
self.left = Au(0)
}
if base_flow.flags.contains(FlowFlags::CLEARS_RIGHT) {
self.right = Au(0)
}
}
/// Given the speculated inline size of the floats out for this flow's last child, computes the
/// speculated inline size of the floats out for this flow.
pub fn compute_floats_out(&mut self, flow: &mut Flow) {
if flow.is_block_like() {
let block_flow = flow.as_block();
if block_flow.formatting_context_type() != FormattingContextType::None {
*self = block_flow.base.speculated_float_placement_in;
} else {
if self.left > Au(0) || self.right > Au(0) {
let speculated_inline_content_edge_offsets =
block_flow.fragment.guess_inline_content_edge_offsets();
if self.left > Au(0) && speculated_inline_content_edge_offsets.start > Au(0) {
self.left = self.left + speculated_inline_content_edge_offsets.start
}
if self.right > Au(0) && speculated_inline_content_edge_offsets.end > Au(0) {
self.right = self.right + speculated_inline_content_edge_offsets.end
}
}
self.left = max(self.left, block_flow.base.speculated_float_placement_in.left);
self.right = max(self.right, block_flow.base.speculated_float_placement_in.right);
}
}
let base_flow = flow.base();
if !base_flow.flags.is_float() {
return
}
let mut float_inline_size = base_flow.intrinsic_inline_sizes.preferred_inline_size;
if float_inline_size == Au(0) {
if flow.is_block_like() {
// Hack: If the size of the float is a percentage, then there's no way we can guess
// at its size now. So just pick an arbitrary nonzero value (in this case, 1px) so
// that the layout traversal logic will know that objects later in the document
// might flow around this float.
if let LengthOrPercentageOrAuto::Percentage(percentage) =
flow.as_block().fragment.style.content_inline_size() {
if percentage.0 > 0.0 {
float_inline_size = Au::from_px(1)
}
}
}
}
match base_flow.flags.float_kind() {
StyleFloat::None => {}
StyleFloat::Left => self.left = self.left + float_inline_size,
StyleFloat::Right => self.right = self.right + float_inline_size,
}
}
/// Given a flow, computes the speculated inline size of the floats in of its first child.
pub fn compute_floats_in_for_first_child(parent_flow: &mut Flow) -> SpeculatedFloatPlacement {
if !parent_flow.is_block_like() {
return parent_flow.base().speculated_float_placement_in
}
let parent_block_flow = parent_flow.as_block();
if parent_block_flow.formatting_context_type() != FormattingContextType::None {
return SpeculatedFloatPlacement::zero()
}
let mut placement = parent_block_flow.base.speculated_float_placement_in;
let speculated_inline_content_edge_offsets =
parent_block_flow.fragment.guess_inline_content_edge_offsets();
if speculated_inline_content_edge_offsets.start > Au(0) {
placement.left = if placement.left > speculated_inline_content_edge_offsets.start {
placement.left - speculated_inline_content_edge_offsets.start
} else {
Au(0)
}
}
if speculated_inline_content_edge_offsets.end > Au(0) {
placement.right = if placement.right > speculated_inline_content_edge_offsets.end {
placement.right - speculated_inline_content_edge_offsets.end
} else {
Au(0)
}
}
placement
}
}