taffy 0.13.0

//! 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, Direction, 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,
}

/// An empty "slot" that avoids floats that is suitable for a box that establishes
/// an independent formatting context (and therefore must not overlap floats) to be
/// laid out into. Unlike [`ContentSlot`], this accounts for the box's own margins,
/// which are resolved against the containing block's edges (not float edges) and
/// may therefore overlap floats.
#[derive(Debug, Clone, Copy, Default)]
pub struct BfcSlot {
    /// The id of the segment that the slot starts in
    pub segment_id: Option<usize>,
    /// The x position of the start of the slot (border box edge)
    pub x: f32,
    /// The y position of the start of the slot
    pub y: f32,
    /// The space available for the box's border box: the space between float edges
    /// and the margin-inset containing block edges. The box fits in the slot if its
    /// border box width does not exceed this.
    pub border_width: f32,
    /// The width that an auto width resolves to (before applying min/max constraints and
    /// the negative-margin lower bound). This differs from `border_width` in that the
    /// trailing margin is subtracted (except for any part of it that overlaps a float).
    pub stretch_width: 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],
    /// Whether a float actually occupies the left (slot 0) / right (slot 1) inset.
    /// The insets of a segment created for a float are seeded with the float's containing
    /// block insets on both sides, so a non-zero inset alone does not imply a float.
    has_float: [bool; 2],
}

impl Segment {
    /// Whether the segment can fit the passed floated box (in the horizontal axis)
    ///
    /// See [`float_fits_horizontally`] for the details of the fit rules.
    fn fits_float_width(
        &self,
        floated_box: Size<f32>,
        direction: FloatDirection,
        bfc_width: f32,
        cb_insets: [f32; 2],
    ) -> bool {
        float_fits_horizontally(floated_box.width, direction, bfc_width, self.insets, cb_insets)
    }
}

/// Whether a floated box of the given width fits horizontally given the float insets
/// (`float_insets`) and containing block insets (`cb_insets`) that apply to it.
///
/// A float is normally placed at the further-in of the float edge and the containing block
/// edge on the side it is floated towards (its "lead" side). From that position it must:
///
///   - not overlap any float on the opposite ("trail") side (CSS2 §9.5.1 rule 3), and
///   - not extend past the containing block's trail edge if there is a float on its lead
///     side (CSS2 §9.5.1 rule 7: a float may only stick out of its containing block if it
///     is already as far towards its float direction as possible).
///
/// Note that a float which is not constrained by other floats *may* overflow its
/// containing block's trail edge (rules 1 and 7).
fn float_fits_horizontally(
    width: f32,
    direction: FloatDirection,
    bfc_width: f32,
    float_insets: [f32; 2],
    cb_insets: [f32; 2],
) -> bool {
    let lead = direction as usize;
    let trail = 1 - lead;
    let x_inset = float_insets[lead].max(cb_insets[lead]);
    let fits_opposite_floats = float_insets[trail] == 0.0 || x_inset + width <= bfc_width - float_insets[trail];
    let fits_containing_block = float_insets[lead] == 0.0 || x_inset + width <= bfc_width - cb_insets[trail];
    fits_opposite_floats && fits_containing_block
}

/// 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 float insets of the set of segments currently being considered
    float_insets: [f32; 2],
    /// The insets of the box's containing block from the edges of the Block Formatting Context
    cb_insets: [f32; 2],
}

impl FloatFitter {
    /// Create a new `FloatFitter`
    fn new(bfc_width: f32, slot_height: f32, cb_insets: [f32; 2]) -> Self {
        Self { bfc_width, slot_height: slot_height as f64, float_insets: [0.0, 0.0], cb_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.float_insets[0] = self.float_insets[0].max(insets[0]);
        self.float_insets[1] = self.float_insets[1].max(insets[1]);
    }

    /// The inset from the edge of the BFC (on the side the box is floated towards) that the
    /// box would be placed at given the currently accounted for insets
    fn placed_inset(&self, direction: FloatDirection) -> f32 {
        let lead = direction as usize;
        self.float_insets[lead].max(self.cb_insets[lead])
    }

    /// Given the currently accounted for insets, check whether there is an x position
    /// such that the box fits horizontally.
    ///
    /// See [`float_fits_horizontally`] for the details of the fit rules.
    fn fits_horiontally(&self, width: f32, direction: FloatDirection) -> bool {
        float_fits_horizontally(width, direction, self.bfc_width, self.float_insets, self.cb_insets)
    }

    // 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],
    /// The bottom (y + height) of the lowest float placed on each side, including
    /// zero-sized floats (which occupy no segment). Left in slot 0, right in slot 1.
    clear_bottoms: [Option<f32>; 2],
    /// The topmost y position allowed for a new float (CSS2 float rule 5), including
    /// the tops of zero-sized floats (which occupy no segment)
    float_ceiling: Option<f32>,
    // 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],
            clear_bottoms: [None, None],
            float_ceiling: None,
        }
    }
}

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, has_float: old_segment.has_float, 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 slot = direction as usize;
        let bottom = placed_floated_box.y + placed_floated_box.height;
        self.clear_bottoms[slot] = Some(self.clear_bottoms[slot].map_or(bottom, |b| b.max(bottom)));
        let y = placed_floated_box.y;
        self.float_ceiling = Some(self.float_ceiling.map_or(y, |ceiling| ceiling.max(y)));

        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;

        // Floats (including zero-sized floats) that occupy no segment still constrain the
        // position of later boxes: rule 5 (a float may not be higher than the top of any
        // earlier float) and `clear` (which clears past the bottom of floats on the
        // relevant side, regardless of their width)
        let min_y = min_y
            .max(self.float_ceiling.unwrap_or(f32::NEG_INFINITY))
            .max(self.cleared_threshold(clear).unwrap_or(f32::NEG_INFINITY));

        // Ensure that float:
        //    - Starts at or after the last placed float in either direction (CSS2 float rule 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")
        //    - Respects "clear"
        let float_start = self.last_placed_floats[0].start.max(self.last_placed_floats[1].start);
        let hwm = match clear {
            Clear::Left => {
                let left_end = self.last_placed_floats[0].end;
                float_start.max(left_end + 1)
            }
            Clear::Right => {
                let right_end = self.last_placed_floats[1].end;
                float_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_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, containing_block_insets) {
                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.placed_inset(direction);
                    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, direction) {
                    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.placed_inset(direction);
                break 'outer (Some(start_idx), Some(end_idx), inset);
            }
        };

        // Short-circuit for zero-height boxes. Zero-width boxes are still recorded in segments:
        // their edge acts as an obstacle that boxes establishing an independent formatting
        // context may not be placed to the outside of (e.g. via a negative margin).
        if 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], has_float: [false; 2] });
            }

            let start_y = last_y_end.max(start_y);

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

            // 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], has_float: [false; 2] });
                }
                self.segments.len() - 1
            }
            Some(mut end_idx) => {
                let end_y = start_y + floated_box.height;

                // Due to floating point imprecision, `end_y` may coincide with (or fall before)
                // the start of the end segment even though the sum of the candidate segment
                // heights was computed as sufficient. In that case the float effectively ends at
                // the boundary of the previous segment, so walk back to the segment that actually
                // contains `end_y`.
                while end_idx > start_idx && end_y <= self.segments[end_idx].y.start {
                    end_idx -= 1;
                }

                // Only subdivide if `end_y` falls strictly within the segment. If it lands on
                // (or, due to floating point imprecision, beyond) a segment boundary then no
                // subdivision is needed.
                if self.segments[end_idx].y.start < end_y && 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;
            segment.has_float[slot] = true;
        }

        // 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)
    ///
    /// Returns `None` if no float has been placed on the relevant side(s)
    fn cleared_segment(&self, clear: Clear) -> Option<usize> {
        let left_end = self.last_placed_floats[0].end;
        let right_end = self.last_placed_floats[1].end;
        match clear {
            Clear::Left if left_end > 0 => Some(left_end),
            Clear::Right if right_end > 0 => Some(right_end),
            Clear::Both if left_end > 0 || right_end > 0 => Some(left_end.max(right_end)),
            _ => None,
        }
    }

    /// Get the bottom of lowest relevant float for the specific clear property
    pub fn cleared_threshold(&self, clear: Clear) -> Option<f32> {
        match clear {
            Clear::Left => self.clear_bottoms[0],
            Clear::Right => self.clear_bottoms[1],
            Clear::Both => match self.clear_bottoms {
                [Some(l), Some(r)] => Some(l.max(r)),
                [l, r] => l.or(r),
            },
            Clear::None => None,
        }
    }

    /// 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,
            };
        }

        // Clearance clears past the bottom of floats on the relevant side, including
        // zero-sized floats which occupy no segment
        let min_y = min_y.max(self.cleared_threshold(clear).unwrap_or(f32::NEG_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,
            },
        }
    }

    /// Search for a space suitable for laying out a box that establishes an independent
    /// formatting context (whose border box must not overlap floats).
    ///
    /// The box's margins are resolved against the containing block's content edges. When there
    /// are floats beside the box:
    ///
    ///   - The leading margin (in flow direction) positions the border box's leading edge, but
    ///     may be partially or fully "absorbed" by a float on the leading side (the border edge
    ///     is the further-in of the float edge and the margin-inset containing block edge), and
    ///     a negative leading margin does not move the border edge past the float edge. When no
    ///     float intrudes on the leading side the margin applies as usual, and a negative margin
    ///     may move the border edge outside the containing block.
    ///   - The trailing margin is subtracted from the width an auto width resolves to (except
    ///     for any part of it that overlaps a float on the trailing side). When a float intrudes
    ///     on the trailing side, the trailing margin does not affect whether a box of a given
    ///     width fits in the slot: the trailing margin may overflow the containing block edge.
    ///     When no float intrudes on the trailing side the margin applies as usual, and a
    ///     negative margin lets the border box extend outside the containing block.
    ///
    /// When there are no floats beside the box, its (possibly negative) margins apply as usual.
    pub fn find_bfc_slot(
        &self,
        min_y: f32,
        containing_block_insets: [f32; 2],
        margins: [f32; 2],
        direction: Direction,
        clear: Clear,
        after: Option<usize>,
    ) -> BfcSlot {
        let margin_insets = [containing_block_insets[0] + margins[0], containing_block_insets[1] + margins[1]];
        let no_float_width = self.available_width - margin_insets[0] - margin_insets[1];
        let no_float_slot = BfcSlot {
            segment_id: None,
            x: margin_insets[0],
            y: min_y,
            border_width: no_float_width,
            stretch_width: no_float_width,
        };

        if !self.has_active_floats(min_y) {
            return no_float_slot;
        }

        // Clearance clears past the bottom of floats on the relevant side, including
        // zero-sized floats which occupy no segment
        let min_y = min_y.max(self.cleared_threshold(clear).unwrap_or(f32::NEG_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());
        match self.segments.get(start_idx) {
            Some(segment) => {
                let lead = match direction {
                    Direction::Ltr => 0,
                    Direction::Rtl => 1,
                };
                let trail = 1 - lead;
                let has_lead_float = segment.has_float[lead];
                let has_trail_float = segment.has_float[trail];
                let mut fit_insets = [0.0; 2];
                let mut stretch_insets = [0.0; 2];
                fit_insets[lead] =
                    if has_lead_float { segment.insets[lead].max(margin_insets[lead]) } else { margin_insets[lead] };
                stretch_insets[lead] = fit_insets[lead];
                fit_insets[trail] = if has_trail_float {
                    segment.insets[trail].max(containing_block_insets[trail])
                } else {
                    // A positive trailing margin may overflow the containing block edge (it does
                    // not affect fit), but a negative one widens the space for the border box
                    margin_insets[trail].min(containing_block_insets[trail])
                };
                stretch_insets[trail] = if has_trail_float {
                    segment.insets[trail].max(margin_insets[trail])
                } else {
                    margin_insets[trail]
                };
                BfcSlot {
                    segment_id: Some(start_idx),
                    x: fit_insets[0],
                    y: segment.y.start.max(min_y),
                    border_width: self.available_width - fit_insets[0] - fit_insets[1],
                    stretch_width: self.available_width - stretch_insets[0] - stretch_insets[1],
                }
            }
            // Below all floats
            None => BfcSlot {
                y: self.segments.last().map(|segment| segment.y.end).unwrap_or(min_y).max(min_y),
                ..no_float_slot
            },
        }
    }
}

/// 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,
    /// The widest single float (the floats' min-content contribution)
    widest: f32,
}

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

    /// Add a float to the computation
    pub fn add_float(&mut self, width: f32, _direction: FloatDirection, _clear: Clear) {
        match self.available_width {
            // Definite available width means the container is being fit-content sized
            // (e.g. it is itself a float being shrink-to-fit sized). The floats' max-content
            // contribution (widths summed) is clamped by the available width in `result`.
            AvailableSpace::Definite(_) | AvailableSpace::MaxContent => self.contribution += width,
            AvailableSpace::MinContent => self.contribution = self.contribution.max(width),
        };
        self.widest = self.widest.max(width);
    }

    /// Get the computed float contribution to intrinsic width
    pub fn result(&self) -> f32 {
        match self.available_width {
            // Fit-content sizing: clamp the max-content contribution between the available
            // width and the min-content contribution (floats narrow by wrapping onto new
            // bands, but never below the widest single float).
            AvailableSpace::Definite(available_width) => self.contribution.min(available_width).max(self.widest),
            _ => self.contribution,
        }
    }
}