taffy 0.10.1

//! Computes the position of floats in a block formatting context
//!
//! Here are the precise rules that govern the behavior of floats:
//!
//! 1. The left outer edge of a left-floating box may not be to the left of the left edge of its containing block. An analogous rule
//!    holds for right-floating elements.
//! 2. If the current box is left-floating, and there are any left-floating boxes generated by elements earlier in the source document,
//!    then for each such earlier box, either the left outer edge of the current box must be to the right of the right outer edge of the earlier box,
//!    or its top must be lower than the bottom of the earlier box. Analogous rules hold for right-floating boxes.
//! 3. The right outer edge of a left-floating box may not be to the right of the left outer edge of any right-floating box that is next to it.
//!    Analogous rules hold for right-floating elements.
//! 4. A floating box's outer top may not be higher than the top of its containing block. When the float occurs between two collapsing margins,
//!    the float is positioned as if it had an otherwise empty anonymous block parent taking part in the flow. The position of such a parent is defined
//!    by the rules in the section on margin collapsing.
//! 5. The outer top of a floating box may not be higher than the outer top of any block or floated box generated by an element earlier in the source document.
//! 6. The outer top of an element's floating box may not be higher than the top of any line-box containing a box generated by
//!    an element earlier in the source document.
//! 7. A left-floating box that has another left-floating box to its left may not have its right outer edge to the right of its containing block's
//!    right edge. (Loosely: a left float may not stick out at the right edge, unless it is already as far to the left as possible.) An analogous rule
//!    holds for right-floating elements.
//! 8. A floating box must be placed as high as possible.
//! 9. A left-floating box must be put as far to the left as possible, a right-floating box as far to the right as possible. A higher position is
//!    preferred over one that is further to the left/right.
//!
//! But in CSS 2.2, if, within the block formatting context, there is an in-flow negative vertical margin such that the float's position is above the position it would be at were all such negative margins set to zero, the position of the float is undefined.
//!
//! <https://www.w3.org/TR/CSS22/visuren.html#floats>

use core::ops::Range;

use crate::{debug::debug_log, sys::Vec, AvailableSpace, Clear, FloatDirection, Point, Size};

/// An empty "slot" that avoids floats that is suitable for non-floated content
/// to be laid out into
#[derive(Debug, Clone, Copy, Default)]
pub struct ContentSlot {
    /// The id of the segment that the slot starts in
    pub segment_id: Option<usize>,
    /// The x position of the start of the slot
    pub x: f32,
    /// The y position of the start of the slot
    pub y: f32,
    /// The width of the slot
    pub width: f32,
    /// The height of the slot
    pub height: f32,
}

/// A floated box
#[derive(Debug, Clone, Default)]
pub struct PlacedFloatedBox {
    /// A user defined ID for the box
    // id: u64,
    /// The width of the box
    pub width: f32,
    /// The height of the box
    pub height: f32,
    /// Horizontal distance from the edge of the container that the box is floated towards
    /// (distance from the left for left floats, from the right for right floats)
    pub x_inset: f32,
    /// Vertical distance from top edge of the container
    pub y: f32,
}

/// A non-overlapping horizontal segment of the Block Formatting Context container
#[derive(Debug, Clone)]
struct Segment {
    /// The vertical start and end points of the segment
    y: Range<f32>,
    /// Left inset in slot 0. Right inset in slot 1.
    insets: [f32; 2],
}

impl Segment {
    /// Whether the segment can fit the passed floated box (in the horizontal axis)
    fn fits_float_width(&self, floated_box: Size<f32>, direction: FloatDirection, bfc_width: f32) -> bool {
        let slot = direction as usize;
        self.insets[slot] == 0.0 || (bfc_width - floated_box.width - self.inset_sum()) >= 0.0
    }

    /// The total space taken up by both insets
    #[inline(always)]
    fn inset_sum(&self) -> f32 {
        self.insets[0] + self.insets[1]
    }
}

/// Helper type for placing a single floated box
///
/// Given a pinned starting y position, this type helps determine if there is any x position
/// such that there is sufficient horizontal space for the box accross it's entire height.
#[derive(Debug, Clone)]
struct FloatFitter {
    /// The overall width of the Block Formatting Context
    bfc_width: f32,
    /// The total height of the set of segments currently being considered
    slot_height: f64,
    /// The union of the insets of the set of segments currently being considered
    insets: [f32; 2],
}

impl FloatFitter {
    /// Create a new `FloatFitter`
    fn new(bfc_width: f32, slot_height: f32, insets: [f32; 2]) -> Self {
        Self { bfc_width, slot_height: slot_height as f64, insets }
    }

    // Horizontal fitting

    /// Union the insets of another segment. This is a "max" of the insets on each side.
    fn union_insets(&mut self, insets: [f32; 2]) {
        self.insets[0] = self.insets[0].max(insets[0]);
        self.insets[1] = self.insets[1].max(insets[1]);
    }

    /// Given the currently accounted for insets, check whether there is an x position
    /// such that the box fits horizontally
    fn fits_horiontally(&self, width: f32) -> bool {
        self.insets == [0.0, 0.0] || self.bfc_width - self.insets[0] - self.insets[1] - width >= 0.0
    }

    // Vertical fitting

    /// Add the height of another segment.
    fn add_height(&mut self, height: f32) {
        self.slot_height += height as f64;
    }

    /// Given the currently accounted for height, check whether the box fits vertically
    fn fits_vertically(&mut self, height: f32) -> bool {
        self.slot_height >= height as f64
    }
}

/// A context for placing floated boxes
#[derive(Debug, Clone)]
pub struct FloatContext {
    /// The available space constraint that applies to the root Block Formatting Context
    /// for which this `FloatContext` manages floats.
    available_width: f32,
    /// Whether the float context contains any floats
    has_floats: bool,
    /// A list of left-floated boxes within the context
    left_floats: Vec<PlacedFloatedBox>,
    /// A list of right-floated boxes within the context
    right_floats: Vec<PlacedFloatedBox>,
    /// A list of non-overlapping horizontal "segments" within the context.
    /// Each segment has the same available width for it's entire height.
    segments: Vec<Segment>,
    /// A closed-open range indicating which segment the last placed float
    /// was placed(on each side).
    last_placed_floats: [Range<usize>; 2],
    // Left hwm in slot 0. Right hwm in slot 1.
    // high_water_marks: [usize; 2],
    // left_float_high_water_mark: usize,
    // right_float_high_water_mark: usize,
}

impl Default for FloatContext {
    fn default() -> Self {
        Self {
            available_width: 0.0,
            has_floats: false,
            left_floats: Vec::new(),
            right_floats: Vec::new(),
            segments: Vec::new(),
            last_placed_floats: [0..0, 0..0], // high_water_marks: [0, 0],
        }
    }
}

impl FloatContext {
    /// Create a new empty `FloatContext`
    pub fn new() -> Self {
        Default::default()
    }

    /// Whether the float context contains any floats
    #[inline(always)]
    pub fn has_floats(&self) -> bool {
        self.has_floats
    }

    /// Whether the float context contains any floats that extend to or below min_y
    #[inline(always)]
    pub fn has_active_floats(&self, min_y: f32) -> bool {
        self.has_floats && self.segments.last().map(|seg| seg.y.end).unwrap_or(0.0) > min_y
    }

    /// Set the width of the `FloatContext`
    pub fn set_width(&mut self, available_width: f32) {
        self.available_width = available_width;
    }

    /// Returns a slice of placed left floats
    pub fn left_floats(&self) -> &[PlacedFloatedBox] {
        &self.left_floats
    }

    /// Returns a slice of placed right floats
    pub fn right_floats(&self) -> &[PlacedFloatedBox] {
        &self.right_floats
    }

    /// Divide a segment into two segments so that a new float can be placed and have it's
    /// vertical start and end at exact segment boundaries
    fn subdivide_segment(&mut self, idx: usize, divide_at_y: f32) {
        let old_segment = &mut self.segments[idx];
        let new_segment = Segment { insets: old_segment.insets, y: divide_at_y..old_segment.y.end };
        if !old_segment.y.contains(&divide_at_y) || old_segment.y.start == divide_at_y {
            debug_log!("old_segment", dbg:&mut *old_segment);
            debug_log!("divide_at_y", dbg:divide_at_y);
            assert!(old_segment.y.contains(&divide_at_y) && old_segment.y.start != divide_at_y);
        }
        old_segment.y.end = divide_at_y;

        self.segments.splice((idx + 1)..(idx + 1), core::iter::once(new_segment));
    }

    /// Update the last placed float start and end values
    fn update_last_placed_float(&mut self, direction: FloatDirection, placement: Range<usize>) {
        let slot = direction as usize;
        self.last_placed_floats[slot].start = self.last_placed_floats[slot].start.max(placement.start);
        self.last_placed_floats[slot].end = self.last_placed_floats[slot].end.max(placement.end);
    }

    /// Position a floated box with the context, returning the (x, y) coordinates
    pub fn place_floated_box(
        &mut self,
        floated_box: Size<f32>,
        min_y: f32,
        containing_block_insets: [f32; 2],
        direction: FloatDirection,
        clear: Clear,
    ) -> Point<f32> {
        self.has_floats = true;

        let placed_floated_box =
            self.place_floated_box_inner(floated_box, min_y, containing_block_insets, direction, clear);

        let x_inset = placed_floated_box.x_inset;
        let y = placed_floated_box.y;
        match direction {
            FloatDirection::Left => {
                self.left_floats.push(placed_floated_box);
                Point { x: x_inset, y }
            }
            FloatDirection::Right => {
                self.right_floats.push(placed_floated_box);
                Point { x: self.available_width - x_inset - floated_box.width, y }
            }
        }
    }

    /// Inner implementation of float placement, split into a separate function so that it can early-return
    fn place_floated_box_inner(
        &mut self,
        floated_box: Size<f32>,
        min_y: f32,
        containing_block_insets: [f32; 2],
        direction: FloatDirection,
        clear: Clear,
    ) -> PlacedFloatedBox {
        let slot = direction as usize;

        // Ensure that float:
        //    - Starts at or after the last placed float that was floated in the same direction as it
        //    - Respects "clear"
        let hwm = match clear {
            Clear::Left => {
                let float_dir_start = self.last_placed_floats[slot].start;
                let left_end = self.last_placed_floats[0].end;
                float_dir_start.max(left_end + 1)
            }
            Clear::Right => {
                let float_dir_start = self.last_placed_floats[slot].start;
                let right_end = self.last_placed_floats[1].end;
                float_dir_start.max(right_end + 1)
            }
            Clear::Both => {
                let left_end = self.last_placed_floats[0].end;
                let right_end = self.last_placed_floats[1].end;
                left_end.max(right_end) + 1
            }
            Clear::None => {
                // float_dir_start
                self.last_placed_floats[slot].start
            }
        };

        // Ensure that float is placed in a segment at or below "min_y"
        // (ensuring that it is placed at or below min_y within it's segment happens below)
        let start_idx = self
            .segments
            .get(hwm..)
            .and_then(|segments| segments.iter().position(|segment| segment.y.end > min_y).map(|idx| idx + hwm));

        let mut start_idx = start_idx.unwrap_or(self.segments.len());
        let mut start_y = min_y;
        let mut end_idx = start_idx;
        // let mut end_y = min_y;

        // Loop over remaining segments, trying to place the float in a position
        // that has space to accomodate it.
        let (start, mut end, placed_inset) = 'outer: loop {
            // Start segment does not exist:
            //
            // This means no existing segment can accomodate the float so we must create a new
            // segment below all existing segments. A new segment will always have space for
            // the float, so we can exit the loop at this point.
            let Some(start_segment) = self.segments.get(start_idx) else {
                break (None, None, containing_block_insets[slot]);
            };

            // Candidate start segment doesn't have (horizontal) space for the float:
            // => retry with the next segment
            if !start_segment.fits_float_width(floated_box, direction, self.available_width) {
                start_idx += 1;
                end_idx = end_idx.max(start_idx);
                continue;
            }

            start_y = start_y.max(start_segment.y.start);
            let available_height = start_segment.y.end - start_y;
            let mut fitter = FloatFitter::new(self.available_width, available_height, containing_block_insets);
            fitter.union_insets(start_segment.insets);

            // Pinning the start segment, loop over segments starting with the start segment
            // to find the end segment:
            //   - The selected segment range must have enough height to contain the float
            //   - All of the segments in the range must have enough horizontal width to contain the float
            //     TODO: must ensure that width is in the correct place.
            loop {
                // End segment does not exist:
                //
                // This means no existing segment can accomodate the float so we must create a new
                // segment below all existing segments
                let Some(end_segment) = self.segments.get(end_idx) else {
                    let inset = fitter.insets[slot];
                    break 'outer (Some(start_idx), None, inset);
                };

                // Check horizontal fit
                //
                // If it does not fit horizontally then it will never fit in this position, so
                // continue the outer loop to find and check a new position
                fitter.union_insets(end_segment.insets);
                if !fitter.fits_horiontally(floated_box.width) {
                    start_idx += 1;
                    end_idx = end_idx.max(start_idx);
                    continue 'outer;
                }

                // Check vertical fit
                //
                // If it does not (yet) fit vertically then continue the inner loop to add another
                // segment to the range of segments we are placing the float in
                if end_idx != start_idx {
                    fitter.add_height(end_segment.y.end - end_segment.y.start);
                }
                if !fitter.fits_vertically(floated_box.height) {
                    end_idx += 1;
                    continue;
                }

                let inset = fitter.insets[slot];
                break 'outer (Some(start_idx), Some(end_idx), inset);
            }
        };

        // Short-circuit for zero-sized boxes
        if floated_box.width == 0.0 || floated_box.height == 0.0 {
            // TODO: need to update last_placed_float?

            return PlacedFloatedBox {
                width: floated_box.width,
                height: floated_box.height,
                y: start_y,
                x_inset: placed_inset,
            };
        }

        // Handle case where floated box is placed after all existing segments
        if start.is_none() {
            let last_y_end = self.segments.last().map(|seg| seg.y.end).unwrap_or(0.0);
            if start_y > last_y_end {
                self.segments.push(Segment { y: last_y_end..start_y, insets: [0.0, 0.0] });
            }

            let start_y = last_y_end.max(start_y);

            let mut insets = containing_block_insets;
            insets[slot] += floated_box.width;
            self.segments.push(Segment { y: start_y..(start_y + floated_box.height), insets });

            // Update last_placed_float
            let start_idx = self.segments.len() - 1;
            let end_idx = start_idx + 1;
            self.update_last_placed_float(direction, start_idx..end_idx);

            return PlacedFloatedBox {
                width: floated_box.width,
                height: floated_box.height,
                y: start_y,
                x_inset: containing_block_insets[slot],
            };
        }

        // Else unwrap the index of the segment that the start of the floating box is placed in
        let mut start_idx = start.unwrap();

        // If the floated box doesn't start at the exact same y-offset as the segment it starts in, then
        // subdivide that segment into two segments at the y-offset that the floated box starts at, and increment
        // `start_idx` so that the floating box is placed in the second of the two segments.
        if start_y != self.segments[start_idx].y.start {
            self.subdivide_segment(start_idx, start_y);
            start_idx += 1;
            if let Some(end_idx) = end.as_mut() {
                *end_idx += 1;
            }
        }

        let end_idx = match end {
            None => {
                let last_y_end = self.segments.last().map(|seg| seg.y.end).unwrap_or(0.0);
                if min_y > last_y_end {
                    self.segments.push(Segment { y: last_y_end..min_y, insets: [0.0, 0.0] });
                }
                self.segments.len() - 1
            }
            Some(end_idx) => {
                let end_y = start_y + floated_box.height;
                if end_y != self.segments[end_idx].y.end {
                    self.subdivide_segment(end_idx, end_y);
                }

                end_idx
            }
        };

        // Update inset for the range of segments that the float is placed in
        let placed_inset_plus_width = placed_inset + floated_box.width;
        for segment in &mut self.segments[start_idx..=end_idx] {
            segment.insets[slot] = placed_inset_plus_width;
        }

        // Update last_placed_float
        self.update_last_placed_float(direction, start_idx..(end_idx + 1));

        PlacedFloatedBox { width: floated_box.width, height: floated_box.height, y: start_y, x_inset: placed_inset }
    }

    /// Get the end segment of the last float on side(s) specified by the clear parameter (if any)
    fn cleared_segment(&self, clear: Clear) -> Option<usize> {
        match clear {
            Clear::Left => Some(self.last_placed_floats[0].end),
            Clear::Right => Some(self.last_placed_floats[1].end),
            Clear::Both => {
                let left_end = self.last_placed_floats[0].end;
                let right_end = self.last_placed_floats[1].end;
                Some(left_end.max(right_end))
            }
            Clear::None => None,
        }
    }

    /// Get the bottom of lowest relevant float for the specific clear property
    pub fn cleared_threshold(&self, clear: Clear) -> Option<f32> {
        self.cleared_segment(clear).and_then(|idx| self.segments.get(idx.max(1) - 1)).map(|seg| seg.y.end)
    }

    /// Search for a space suitable for laying out non-floated content into
    pub fn find_content_slot(
        &self,
        min_y: f32,
        containing_block_insets: [f32; 2],
        clear: Clear,
        after: Option<usize>,
    ) -> ContentSlot {
        if !self.has_active_floats(min_y) {
            return ContentSlot {
                segment_id: None,
                x: containing_block_insets[0],
                y: min_y,
                width: self.available_width - containing_block_insets[0] - containing_block_insets[1],
                height: f32::INFINITY,
            };
        }

        // The min starting segment index
        let at_least = after.map(|idx| idx + 1).unwrap_or(0);
        let hwm = at_least.max(self.cleared_segment(clear).map(|idx| idx + 1).unwrap_or(0));

        let start_idx = self
            .segments
            .get(hwm..)
            .and_then(|segments| segments.iter().position(|segment| segment.y.end > min_y).map(|idx| idx + hwm));
        let start_idx = start_idx.unwrap_or(self.segments.len());
        let segment = self.segments.get(start_idx);
        match segment {
            Some(segment) => {
                let inset_left = segment.insets[0].max(containing_block_insets[0]);
                let inset_right = segment.insets[1].max(containing_block_insets[1]);
                ContentSlot {
                    segment_id: Some(start_idx),
                    x: inset_left,
                    y: segment.y.start.max(min_y),
                    width: self.available_width - inset_left - inset_right,
                    height: f32::INFINITY,
                }
            }
            None => ContentSlot {
                segment_id: None,
                x: containing_block_insets[0],
                y: min_y,
                width: self.available_width - containing_block_insets[0] - containing_block_insets[1],
                height: f32::INFINITY,
            },
        }
    }
}

/// Context for computing the intrinsic width contribution of a set of floats
pub struct FloatIntrinsicWidthCalculator {
    /// The available width of the container
    available_width: AvailableSpace,
    /// The running total intrinsic width contribution
    contribution: f32,
}

impl FloatIntrinsicWidthCalculator {
    /// Create a new `FloatIntrinsicWidthCalculator`
    pub fn new(available_width: AvailableSpace) -> Self {
        Self { available_width, contribution: 0.0 }
    }

    /// Add a float to the computation
    pub fn add_float(&mut self, width: f32, _direction: FloatDirection, _clear: Clear) {
        match self.available_width {
            AvailableSpace::Definite(_) => {
                // We will never hit this code path with definite available space
            }
            AvailableSpace::MinContent => self.contribution = self.contribution.max(width),
            AvailableSpace::MaxContent => self.contribution += width,
        };
    }

    /// Get the computed float contribution to intrinsic width
    pub fn result(&self) -> f32 {
        self.contribution
    }
}