Source file track_sizing.ml

(* Grid track sizing algorithm implementation *)

open Geometry
open Style
open Tree

(* Types *)

type item_batcher = {
  axis : abstract_axis;
      (* The axis in which the ItemBatcher is operating. Used when querying
         properties from items. *)
  mutable index_offset : int; (* The starting index of the current batch *)
  mutable current_span : int; (* The span of the items in the current batch *)
  mutable current_is_flex : bool;
      (* Whether the current batch of items cross a flexible track *)
}
(* Takes an axis, and a list of grid items sorted firstly by whether they cross
   a flex track in the specified axis (items that don't cross a flex track
   first) and then by the number of tracks they cross in specified axis
   (ascending order). *)

(* Whether it is a minimum or maximum size's space being distributed This
   controls behaviour of the space distribution algorithm when distributing
   beyond limits *)
type intrinsic_contribution_type =
  | Minimum (* It's a minimum size's space being distributed *)
  | Maximum (* It's a maximum size's space being distributed *)

(* Intrinsic size measurer methods *)
module Intrinsic_size_measurer = struct
  type 'tree t = {
    tree : 'tree; (* The layout tree *)
    other_axis_tracks : Grid_track.t array;
        (* The tracks in the opposite axis to the one we are currently sizing *)
    get_track_size_estimate :
      Grid_track.t -> float option -> 'tree -> float option;
        (* A function that computes an estimate of an other-axis track's size *)
    axis : abstract_axis; (* The axis we are currently sizing *)
    inner_node_size : float option size; (* The available grid space *)
  }
  (* Struct that captures variables used to compute intrinsic sizes of
     children *)

  (* Compute the available_space to be passed to the child sizing functions *)
  let available_space (type tree) (measurer : tree t) (item : Grid_item.t) :
      float option size =
    (* These are estimates based on either the max track sizing function or the
       provisional base size in the opposite axis to the one currently being
       sized. https://www.w3.org/TR/css-grid-1/#algo-overview *)
    let item_other_axis_size =
      let track_range =
        Grid_item.track_range_excluding_lines item
          (Abstract_axis.other measurer.axis)
      in
      let start_idx = fst track_range in
      let end_idx = snd track_range in
      let tracks =
        Array.sub measurer.other_axis_tracks start_idx (end_idx - start_idx)
      in

      Array.fold_left
        (fun acc track ->
          match acc with
          | None -> None
          | Some sum -> (
              match
                measurer.get_track_size_estimate track
                  (Size.get
                     (Abstract_axis.other measurer.axis)
                     measurer.inner_node_size)
                  measurer.tree
              with
              | None -> None
              | Some size ->
                  Some
                    (sum +. size
                   +. track.Grid_track.content_alignment_adjustment)))
        (Some 0.0) tracks
    in

    let size = Size.none in
    match measurer.axis with
    | Abstract_axis.Inline -> { size with height = item_other_axis_size }
    | Abstract_axis.Block -> { size with width = item_other_axis_size }

  (* Compute the item's resolved margins for size contributions *)
  let margins_axis_sums_with_baseline_shims (type tree)
      (module Tree : LAYOUT_PARTIAL_TREE with type t = tree) (measurer : tree t)
      (item : Grid_item.t) : float size =
    (* Horizontal percentage margins always resolve to zero if the container
       size is indefinite as otherwise this would introduce a cyclic
       dependency. *)
    let calc = Tree.resolve_calc_value measurer.tree in
    let inner_node_width = measurer.inner_node_size.width in

    let margin_rect =
      Rect.
        {
          left =
            Length_percentage_auto.resolve_or_zero item.margin.left (Some 0.0)
              calc;
          right =
            Length_percentage_auto.resolve_or_zero item.margin.right (Some 0.0)
              calc;
          top =
            Length_percentage_auto.resolve_or_zero item.margin.top
              inner_node_width calc
            +. item.baseline_shim;
          bottom =
            Length_percentage_auto.resolve_or_zero item.margin.bottom
              inner_node_width calc;
        }
    in

    Rect.sum_axes margin_rect

  (* Retrieve the item's min content contribution from the cache or compute
     it *)
  let min_content_contribution (type tree)
      (module Tree : LAYOUT_PARTIAL_TREE with type t = tree) (measurer : tree t)
      (item : Grid_item.t) : float =
    let available_space = available_space measurer item in
    let margin_axis_sums =
      margins_axis_sums_with_baseline_shims (module Tree) measurer item
    in

    (* Check cache first *)
    match Size.get measurer.axis item.min_content_contribution_cache with
    | Some cached_value ->
        cached_value +. Size.get measurer.axis margin_axis_sums
    | None ->
        (* Compute known dimensions using the available space *)
        let known_dimensions =
          Grid_item.known_dimensions
            (module Tree)
            item measurer.tree measurer.inner_node_size available_space
        in

        (* Measure the child *)
        let layout_output =
          Tree.compute_child_layout measurer.tree item.node
            (Layout_input.make ~run_mode:Run_mode.Compute_size
               ~sizing_mode:Sizing_mode.Inherent_size
               ~axis:
                 (match measurer.axis with
                 | Abstract_axis.Inline -> Requested_axis.Horizontal
                 | Abstract_axis.Block -> Requested_axis.Vertical)
               ~known_dimensions ~parent_size:measurer.inner_node_size
               ~available_space:
                 (Size.map
                    (fun opt ->
                      match opt with
                      | Some size -> Available_space.Definite size
                      | None -> Available_space.Min_content)
                    available_space)
               ~vertical_margins_are_collapsible:Line.both_false)
        in
        let contribution =
          match measurer.axis with
          | Abstract_axis.Inline -> (Layout_output.size layout_output).width
          | Abstract_axis.Block -> (Layout_output.size layout_output).height
        in

        (* Update cache *)
        item.min_content_contribution_cache <-
          Size.set measurer.axis (Some contribution)
            item.min_content_contribution_cache;

        contribution +. Size.get measurer.axis margin_axis_sums

  (* Retrieve the item's max content contribution from the cache or compute
     it *)
  let max_content_contribution (type tree)
      (module Tree : LAYOUT_PARTIAL_TREE with type t = tree) (measurer : tree t)
      (item : Grid_item.t) : float =
    let available_space = available_space measurer item in
    let margin_axis_sums =
      margins_axis_sums_with_baseline_shims (module Tree) measurer item
    in

    (* Check cache first *)
    match Size.get measurer.axis item.max_content_contribution_cache with
    | Some cached_value ->
        cached_value +. Size.get measurer.axis margin_axis_sums
    | None ->
        (* Compute known dimensions using the available space *)
        let known_dimensions =
          Grid_item.known_dimensions
            (module Tree)
            item measurer.tree measurer.inner_node_size available_space
        in

        (* Measure the child *)
        let layout_output =
          Tree.compute_child_layout measurer.tree item.node
            (Layout_input.make ~run_mode:Run_mode.Compute_size
               ~sizing_mode:Sizing_mode.Inherent_size
               ~axis:
                 (match measurer.axis with
                 | Abstract_axis.Inline -> Requested_axis.Horizontal
                 | Abstract_axis.Block -> Requested_axis.Vertical)
               ~known_dimensions ~parent_size:measurer.inner_node_size
               ~available_space:
                 (Size.map
                    (fun opt ->
                      match opt with
                      | Some size -> Available_space.Definite size
                      | None -> Available_space.Max_content)
                    available_space)
               ~vertical_margins_are_collapsible:Line.both_false)
        in
        let contribution =
          match measurer.axis with
          | Abstract_axis.Inline -> (Layout_output.size layout_output).width
          | Abstract_axis.Block -> (Layout_output.size layout_output).height
        in

        (* Update cache *)
        item.max_content_contribution_cache <-
          Size.set measurer.axis (Some contribution)
            item.max_content_contribution_cache;

        contribution +. Size.get measurer.axis margin_axis_sums

  (* The minimum contribution of an item is the smallest outer size it can
     have *)
  let minimum_contribution (type tree)
      (module Tree : LAYOUT_PARTIAL_TREE with type t = tree) (measurer : tree t)
      (item : Grid_item.t) (axis_tracks : Grid_track.t array) : float =
    let calc = Tree.resolve_calc_value measurer.tree in
    let known_dimensions = available_space measurer item in
    let inner_node_size = measurer.inner_node_size in
    let margin_axis_sums =
      margins_axis_sums_with_baseline_shims (module Tree) measurer item
    in

    (* Check cache first *)
    match Size.get measurer.axis item.minimum_contribution_cache with
    | Some cached_value ->
        cached_value +. Size.get measurer.axis margin_axis_sums
    | None ->
        (* Resolve padding and border *)
        let padding =
          Rect.map
            (fun lp ->
              Length_percentage.resolve_or_zero lp inner_node_size.width calc)
            item.padding
        in
        let border =
          Rect.map
            (fun lp ->
              Length_percentage.resolve_or_zero lp inner_node_size.width calc)
            item.border
        in
        let padding_border_size = Rect.sum_axes (Rect.add padding border) in

        let box_sizing_adjustment =
          if item.box_sizing = Box_sizing.Content_box then padding_border_size
          else Size.zero
        in

        (* Helper to resolve dimension with optional value *)
        let maybe_min v_opt limit_opt =
          match (v_opt, limit_opt) with
          | None, _ -> None
          | Some v, None -> Some v
          | Some v, Some lim -> Some (min v lim)
        in

        let size =
          (* Try to get size from explicit size *)
          ( ( ( Dimension.maybe_resolve
                  (Size.get measurer.axis item.size)
                  (Size.get measurer.axis inner_node_size)
                  calc
              |> fun s_opt ->
                match s_opt with
                | Some s -> (
                    Size.apply_aspect_ratio item.aspect_ratio
                      (match measurer.axis with
                      | Abstract_axis.Inline ->
                          Size.{ width = Some s; height = None }
                      | Abstract_axis.Block ->
                          Size.{ width = None; height = Some s })
                    |> Size.get measurer.axis
                    |> fun v_opt ->
                    match v_opt with
                    | Some v ->
                        Some (v +. Size.get measurer.axis box_sizing_adjustment)
                    | None -> None)
                | None -> None )
            |> fun v_opt ->
              match v_opt with
              | Some _ -> v_opt
              | None -> (
                  (* Try min_size if size is not available *)
                  Dimension.maybe_resolve
                    (Size.get measurer.axis item.min_size)
                    (Size.get measurer.axis inner_node_size)
                    calc
                  |> fun s_opt ->
                  match s_opt with
                  | Some s -> (
                      Size.apply_aspect_ratio item.aspect_ratio
                        (match measurer.axis with
                        | Abstract_axis.Inline ->
                            Size.{ width = Some s; height = None }
                        | Abstract_axis.Block ->
                            Size.{ width = None; height = Some s })
                      |> Size.get measurer.axis
                      |> fun v_opt ->
                      match v_opt with
                      | Some v ->
                          Some
                            (v +. Size.get measurer.axis box_sizing_adjustment)
                      | None -> None)
                  | None -> None) )
          |> fun v_opt ->
            match v_opt with
            | Some _ -> v_opt
            | None ->
                (* Try automatic minimum size from overflow property *)
                let overflow_val =
                  match measurer.axis with
                  | Abstract_axis.Inline -> item.overflow.x
                  | Abstract_axis.Block -> item.overflow.y
                in
                Dimension.to_option
                  (Overflow.to_automatic_min_size overflow_val) )
          |> fun v_opt ->
          match v_opt with
          | Some v -> v
          | None ->
              (* Automatic minimum size. See
                 https://www.w3.org/TR/css-grid-1/#min-size-auto *)
              let start_idx, end_idx =
                Grid_item.track_range_excluding_lines item measurer.axis
              in
              let item_axis_tracks =
                Array.sub axis_tracks start_idx (end_idx - start_idx)
              in

              (* it spans at least one track in that axis whose min track sizing
                 function is auto *)
              let spans_auto_min_track =
                Array.exists
                  (fun track ->
                    Grid.Track_sizing_function.Min.is_auto
                      track.Grid_track.track_sizing_function)
                  item_axis_tracks
              in

              (* if it spans more than one track in that axis, none of those
                 tracks are flexible *)
              let only_span_one_track = Array.length item_axis_tracks = 1 in
              let spans_a_flexible_track =
                Array.exists
                  (fun track ->
                    Grid.Track_sizing_function.Max.is_fr
                      track.Grid_track.track_sizing_function)
                  item_axis_tracks
              in

              let use_content_based_minimum =
                spans_auto_min_track
                && (only_span_one_track || not spans_a_flexible_track)
              in

              (* Otherwise, the automatic minimum size is zero, as usual. *)
              if use_content_based_minimum then
                let minimum_contribution =
                  (* Pass known_dimensions to min_content_contribution_cached in
                     grid_item *)
                  let available_space_for_contribution = known_dimensions in
                  Grid_item.min_content_contribution_cached item measurer.axis
                    (module Tree)
                    measurer.tree available_space_for_contribution
                    inner_node_size
                in

                (* If the item is a compressible replaced element, and has a
                   definite preferred size or maximum size in the relevant axis,
                   the size suggestion is capped by those sizes; for this
                   purpose, any indefinite percentages in these sizes are
                   resolved against zero (and considered definite). *)
                if item.is_compressible_replaced then
                  let size_cap =
                    Dimension.maybe_resolve
                      (Size.get measurer.axis item.size)
                      (Some 0.0) calc
                  in
                  let max_size_cap =
                    Dimension.maybe_resolve
                      (Size.get measurer.axis item.max_size)
                      (Some 0.0) calc
                  in
                  maybe_min (Some minimum_contribution) size_cap
                  |> (fun v -> maybe_min v max_size_cap)
                  |> Option.value ~default:minimum_contribution
                else minimum_contribution
              else 0.0
        in

        (* In all cases, the size suggestion is additionally clamped by the
           maximum size in the affected axis, if it's definite. Note: The
           argument to fit-content() does not clamp the content-based minimum
           size in the same way as a fixed max track sizing function. *)
        let limit =
          Grid_item.spanned_fixed_track_limit item measurer.axis axis_tracks
            (Size.get measurer.axis inner_node_size)
            calc
        in
        let final_size =
          maybe_min (Some size) limit |> Option.value ~default:size
        in

        (* Update cache *)
        item.minimum_contribution_cache <-
          Size.set measurer.axis (Some final_size)
            item.minimum_contribution_cache;

        final_size +. Size.get measurer.axis margin_axis_sums
end

(* Helper functions *)

(* Create a new ItemBatcher for the specified axis *)
let new_item_batcher (axis : abstract_axis) : item_batcher =
  { axis; index_offset = 0; current_span = 1; current_is_flex = false }

(* This is basically a manual version of Iterator::next which passes `items` in
   as a parameter on each iteration to work around borrow checker rules *)
let item_batcher_next (batcher : item_batcher) (items : Grid_item.t array) :
    (Grid_item.t array * bool) option =
  if batcher.current_is_flex || batcher.index_offset >= Array.length items then
    None
  else
    let item = items.(batcher.index_offset) in
    batcher.current_span <- Grid_item.span item batcher.axis;
    batcher.current_is_flex <-
      Grid_item.crosses_flexible_track item batcher.axis;

    let next_index_offset =
      if batcher.current_is_flex then Array.length items
      else
        (* Find the first item after current offset that either crosses flexible
           track or has larger span *)
        let rec find_next idx =
          if idx >= Array.length items then Array.length items
          else
            let item = items.(idx) in
            if
              Grid_item.crosses_flexible_track item batcher.axis
              || Grid_item.span item batcher.axis > batcher.current_span
            then idx
            else find_next (idx + 1)
        in
        find_next (batcher.index_offset + 1)
    in

    let batch =
      Array.sub items batcher.index_offset
        (next_index_offset - batcher.index_offset)
    in
    batcher.index_offset <- next_index_offset;

    Some (batch, batcher.current_is_flex)

(* To make track sizing efficient we want to order tracks *)
let cmp_by_cross_flex_then_span_then_start (axis : abstract_axis)
    (item_a : Grid_item.t) (item_b : Grid_item.t) : int =
  match
    ( Grid_item.crosses_flexible_track item_a axis,
      Grid_item.crosses_flexible_track item_b axis )
  with
  | false, true -> -1
  | true, false -> 1
  | _ -> (
      let placement_a = Grid_item.placement item_a axis in
      let placement_b = Grid_item.placement item_b axis in
      let span_a = Grid_item.span item_a axis in
      let span_b = Grid_item.span item_b axis in
      match Int.compare span_a span_b with
      | 0 -> Int.compare placement_a.start placement_b.start
      | cmp -> cmp)

(* When applying the track sizing algorithm and estimating the size in the other
   axis for content sizing items we should take into account
   align-content/justify-content if both the grid container and all items in the
   other axis have definite sizes. *)
let compute_alignment_gutter_adjustment (alignment : align_content)
    (axis_inner_node_size : float option)
    (get_track_size_estimate : Grid_track.t -> float option -> float option)
    (tracks : Grid_track.t array) : float =
  if Array.length tracks <= 1 then 0.0
  else
    (* As items never cross the outermost gutters in a grid, we can simplify our
       calculations by treating AlignContent::Start and AlignContent::End the
       same *)
    let outer_gutter_weight =
      match alignment with
      | Start | Flex_start | End | Flex_end | Center -> 1
      | Stretch | Space_between -> 0
      | Space_around -> 1
      | Space_evenly -> 1
    in

    let inner_gutter_weight =
      match alignment with
      | Flex_start | Start | Flex_end | End | Center | Stretch -> 0
      | Space_between -> 1
      | Space_around -> 2
      | Space_evenly -> 1
    in

    if inner_gutter_weight = 0 then 0.0
    else
      match axis_inner_node_size with
      | None -> 0.0
      | Some axis_inner_node_size ->
          let track_size_sum_opt =
            Array.fold_left
              (fun acc track ->
                match
                  ( acc,
                    get_track_size_estimate track (Some axis_inner_node_size) )
                with
                | Some sum, Some size -> Some (sum +. size)
                | _ -> None)
              (Some 0.0) tracks
          in

          let free_space =
            match track_size_sum_opt with
            | Some track_size_sum ->
                max 0.0 (axis_inner_node_size -. track_size_sum)
            | None -> 0.0
          in

          let weighted_track_count =
            ((Array.length tracks - 3) / 2 * inner_gutter_weight)
            + (2 * outer_gutter_weight)
          in

          free_space
          /. float_of_int weighted_track_count
          *. float_of_int inner_gutter_weight

(* Convert origin-zero coordinates track placement in grid track vector
   indexes *)
let resolve_item_track_indexes (items : Grid_item.t array)
    (column_counts : Style.Grid.track_counts)
    (row_counts : Style.Grid.track_counts) : unit =
  Array.iter
    (fun item ->
      (* Convert origin-zero line coordinates to track vector indices *)
      let into_track_vec_index line track_counts =
        (* In origin-zero coordinates, negative lines are stored first in the
           track vector, followed by explicit tracks, then positive implicit
           tracks *)
        let negative_implicit = track_counts.Style.Grid.negative_implicit in
        if line < -negative_implicit then
          failwith
            "OriginZero grid line cannot be less than the number of negative \
             grid lines"
        else if line >= 0 then
          let explicit_and_pos_implicit =
            track_counts.Style.Grid.explicit
            + track_counts.Style.Grid.positive_implicit
          in
          if line > explicit_and_pos_implicit then
            failwith
              "OriginZero grid line cannot be more than the number of positive \
               grid lines"
          else
            (* Multiply by 2 to account for gutters - each line maps to an even
               index *)
            2 * (negative_implicit + line)
        else
          (* Multiply by 2 to account for gutters - each line maps to an even
             index *)
          2 * (negative_implicit + line)
      in
      item.Grid_item.column_indexes <-
        Line.map
          (fun line -> into_track_vec_index line column_counts)
          item.Grid_item.column;
      item.Grid_item.row_indexes <-
        Line.map
          (fun line -> into_track_vec_index line row_counts)
          item.Grid_item.row)
    items

(* Determine (in each axis) whether the item crosses any flexible tracks *)
let determine_if_item_crosses_flexible_or_intrinsic_tracks
    (items : Grid_item.t array) (columns : Grid_track.t array)
    (rows : Grid_track.t array) : unit =
  Array.iter
    (fun item ->
      (* Check if the item crosses any flexible or intrinsic columns *)
      let col_start_idx, col_end_idx =
        Grid_item.track_range_excluding_lines item Abstract_axis.Inline
      in
      let col_tracks =
        Array.sub columns col_start_idx (col_end_idx - col_start_idx)
      in
      item.crosses_flexible_column <-
        Array.exists Grid_track.is_flexible col_tracks;
      item.crosses_intrinsic_column <-
        Array.exists Grid_track.has_intrinsic_sizing_function col_tracks;

      (* Check if the item crosses any flexible or intrinsic rows *)
      let row_start_idx, row_end_idx =
        Grid_item.track_range_excluding_lines item Abstract_axis.Block
      in
      let row_tracks =
        Array.sub rows row_start_idx (row_end_idx - row_start_idx)
      in
      item.crosses_flexible_row <-
        Array.exists Grid_track.is_flexible row_tracks;
      item.crosses_intrinsic_row <-
        Array.exists Grid_track.has_intrinsic_sizing_function row_tracks)
    items

(* Add any planned base size increases to the base size after a round of
   distributing space to base sizes *)
let flush_planned_base_size_increases (tracks : Grid_track.t array) : unit =
  Array.iter
    (fun track ->
      track.Grid_track.base_size <-
        track.Grid_track.base_size
        +. track.Grid_track.base_size_planned_increase;
      track.Grid_track.base_size_planned_increase <- 0.0)
    tracks

(* Add any planned growth limit increases to the growth limit after a round of
   distributing space to growth limits *)
let flush_planned_growth_limit_increases (tracks : Grid_track.t array)
    (set_infinitely_growable : bool) : unit =
  Array.iter
    (fun track ->
      if track.Grid_track.growth_limit_planned_increase > 0.0 then (
        track.Grid_track.growth_limit <-
          (if track.Grid_track.growth_limit = Float.infinity then
             track.Grid_track.base_size
             +. track.Grid_track.growth_limit_planned_increase
           else
             track.Grid_track.growth_limit
             +. track.Grid_track.growth_limit_planned_increase);
        track.Grid_track.infinitely_growable <- set_infinitely_growable)
      else track.Grid_track.infinitely_growable <- false;
      track.Grid_track.growth_limit_planned_increase <- 0.0)
    tracks

(* 11.4 Initialise Track sizes Initialize each track's base size and growth
   limit. *)
let initialize_track_sizes (type t) (tree : t)
    (resolve_calc_value : t -> int -> float -> float)
    (axis_tracks : Grid_track.t array) (axis_inner_node_size : float option) :
    unit =
  Array.iter
    (fun track ->
      (* For each track, if the track's min track sizing function is: - A fixed
         sizing function Resolve to an absolute length and use that size as the
         track's initial base size. Note: Indefinite lengths cannot occur, as
         they're treated as auto. - An intrinsic sizing function Use an initial
         base size of zero. *)
      track.Grid_track.base_size <-
        (match
           Style.Grid.Track_sizing_function.Min.definite_value_with_calc
             track.Grid_track.track_sizing_function axis_inner_node_size
             (resolve_calc_value tree)
         with
        | Some value -> value
        | None -> 0.0);

      (* For each track, if the track's max track sizing function is: - A fixed
         sizing function Resolve to an absolute length and use that size as the
         track's initial growth limit. - An intrinsic sizing function Use an
         initial growth limit of infinity. - A flexible sizing function Use an
         initial growth limit of infinity. *)
      track.Grid_track.growth_limit <-
        (match
           Style.Grid.Track_sizing_function.Max.definite_value_with_calc
             track.Grid_track.track_sizing_function axis_inner_node_size
             (resolve_calc_value tree)
         with
        | Some value -> value
        | None -> Float.infinity);

      (* In all cases, if the growth limit is less than the base size, reconcile
         them. *)
      if track.Grid_track.growth_limit < track.Grid_track.base_size then
        if
          Style.Grid.Track_sizing_function.Max.is_fit_content
            track.Grid_track.track_sizing_function
        then
          (* Fit-content caps track growth; base size must not exceed the
             limit *)
          track.Grid_track.base_size <- track.Grid_track.growth_limit
        else track.Grid_track.growth_limit <- track.Grid_track.base_size)
    axis_tracks

(* 11.5.1 Shim baseline-aligned items so their intrinsic size contributions
   reflect their baseline alignment. *)
let resolve_item_baselines (type t)
    (module Tree : LAYOUT_PARTIAL_TREE with type t = t) (tree : t)
    (axis : abstract_axis) (items : Grid_item.t array)
    (inner_node_size : float option size) : unit =
  (* Sort items by track in the other axis (row) start position so that we can
     iterate items in groups which are in the same track in the other axis
     (row) *)
  let other_axis = Abstract_axis.other axis in
  Array.sort
    (fun a b ->
      let a_start = (Grid_item.placement a other_axis).start in
      let b_start = (Grid_item.placement b other_axis).start in
      Int.compare a_start b_start)
    items;

  (* Iterate over grid rows *)
  let rec process_rows start_idx =
    if start_idx >= Array.length items then ()
    else
      (* Get the row index of the current row *)
      let current_row =
        (Grid_item.placement items.(start_idx) other_axis).start
      in

      (* Find the end of the current row *)
      let rec find_row_end idx =
        if idx >= Array.length items then idx
        else if
          (Grid_item.placement items.(idx) other_axis).start <> current_row
        then idx
        else find_row_end (idx + 1)
      in
      let end_idx = find_row_end start_idx in
      let row_items = Array.sub items start_idx (end_idx - start_idx) in

      (* Count how many items in *this row* are baseline aligned If a row has
         one or zero items participating in baseline alignment then baseline
         alignment is a no-op for those items and we skip further computations
         for that row *)
      let row_baseline_item_count =
        Array.fold_left
          (fun count item ->
            if item.Grid_item.align_self = Align_items.Baseline then count + 1
            else count)
          0 row_items
      in

      if row_baseline_item_count > 1 then (
        (* Compute the baselines of all items in the row *)
        Array.iter
          (fun item ->
            let layout_output =
              Tree.compute_child_layout tree item.Grid_item.node
                (Layout_input.make ~known_dimensions:Size.none
                   ~parent_size:inner_node_size
                   ~available_space:
                     (Size.map (fun _ -> Available_space.Min_content) Size.none)
                   ~sizing_mode:Sizing_mode.Inherent_size
                   ~run_mode:Run_mode.Perform_layout ~axis:Requested_axis.Both
                   ~vertical_margins_are_collapsible:Line.both_false)
            in
            let baseline = (Layout_output.first_baselines layout_output).y in
            let height = (Layout_output.size layout_output).height in
            let calc = Tree.resolve_calc_value tree in

            item.Grid_item.baseline <-
              Some
                (Option.value baseline ~default:height
                +. Length_percentage_auto.resolve_or_zero
                     item.Grid_item.margin.top inner_node_size.width calc))
          row_items;

        (* Compute the max baseline of all items in the row *)
        let row_max_baseline =
          Array.fold_left
            (fun max_baseline item ->
              let baseline =
                Option.value item.Grid_item.baseline ~default:0.0
              in
              max max_baseline baseline)
            0.0 row_items
        in

        (* Compute the baseline shim for each item in the row *)
        Array.iter
          (fun item ->
            item.Grid_item.baseline_shim <-
              row_max_baseline
              -. Option.value item.Grid_item.baseline ~default:0.0)
          row_items);

      (* Process next row *)
      process_rows end_idx
  in
  process_rows 0

(* Helper function for distributing space to tracks evenly Used by both
   distribute_item_space_to_base_size and maximise_tracks steps *)
let distribute_space_up_to_limits (space_to_distribute : float)
    (tracks : Grid_track.t array) (track_is_affected : Grid_track.t -> bool)
    (track_distribution_proportion : Grid_track.t -> float)
    (track_affected_property : Grid_track.t -> float)
    (track_limit : Grid_track.t -> float) : float =
  (* Define a small constant to avoid infinite loops due to rounding errors *)
  let threshold = 0.01 in

  let space_to_distribute = ref space_to_distribute in
  while !space_to_distribute > threshold do
    (* Calculate the sum of distribution proportions for tracks that can still
       grow *)
    let track_distribution_proportion_sum =
      Array.fold_left
        (fun sum track ->
          if
            track_is_affected track
            && track_affected_property track
               +. track.Grid_track.item_incurred_increase
               < track_limit track
          then sum +. track_distribution_proportion track
          else sum)
        0.0 tracks
    in

    if track_distribution_proportion_sum = 0.0 then
      (* No more tracks can grow, stop distributing *)
      space_to_distribute := 0.0
    else
      (* Compute the minimum increase limit across all growable tracks *)
      let min_increase_limit =
        Array.fold_left
          (fun min_limit track ->
            if
              track_is_affected track
              && track_affected_property track
                 +. track.Grid_track.item_incurred_increase
                 < track_limit track
            then
              let limit =
                (track_limit track -. track_affected_property track)
                /. track_distribution_proportion track
              in
              if min_limit = Float.infinity then limit else min limit min_limit
            else min_limit)
          Float.infinity tracks
      in

      (* Compute the actual increase for this iteration *)
      let iteration_item_incurred_increase =
        min min_increase_limit
          (!space_to_distribute /. track_distribution_proportion_sum)
      in

      (* Apply the increase to each affected track *)
      Array.iter
        (fun track ->
          if track_is_affected track then
            let increase =
              iteration_item_incurred_increase
              *. track_distribution_proportion track
            in
            if
              increase > 0.0
              && track_affected_property track +. increase
                 <= track_limit track +. threshold
            then (
              track.Grid_track.item_incurred_increase <-
                track.Grid_track.item_incurred_increase +. increase;
              space_to_distribute := !space_to_distribute -. increase))
        tracks
  done;

  !space_to_distribute

(* 11.5.1. Distributing Extra Space Across Spanned Tracks This is simplified
   (and faster) version of the algorithm for growth limits *)
let distribute_item_space_to_growth_limit (space : float)
    (tracks : Grid_track.t array) (track_is_affected : Grid_track.t -> bool)
    (axis_inner_node_size : float option) : unit =
  (* Skip this distribution if there is either no space to distribute or no
     affected tracks *)
  if space = 0.0 || not (Array.exists track_is_affected tracks) then ()
  else
    (* 1. Find the space to distribute *)
    let track_sizes =
      Array.fold_left
        (fun sum track ->
          if track.Grid_track.growth_limit = Float.infinity then
            sum +. track.Grid_track.base_size
          else sum +. track.Grid_track.growth_limit)
        0.0 tracks
    in
    let extra_space = max 0.0 (space -. track_sizes) in

    (* 2. Distribute space up to limits *)
    (* For growth limits, the limit is either Infinity or the growth limit itself *)
    let number_of_growable_tracks =
      Array.fold_left
        (fun count track ->
          if
            track_is_affected track
            && (track.Grid_track.infinitely_growable
               || Grid_track.fit_content_limited_growth_limit track
                    axis_inner_node_size
                  = Float.infinity)
          then count + 1
          else count)
        0 tracks
    in

    if number_of_growable_tracks > 0 then
      (* Distribute space evenly to tracks with infinite limits *)
      let item_incurred_increase =
        extra_space /. float_of_int number_of_growable_tracks
      in
      Array.iter
        (fun track ->
          if
            track_is_affected track
            && (track.Grid_track.infinitely_growable
               || Grid_track.fit_content_limited_growth_limit track
                    axis_inner_node_size
                  = Float.infinity)
          then track.Grid_track.item_incurred_increase <- item_incurred_increase)
        tracks
    else
      (* 3. Distribute space beyond limits *)
      (* If space remains after all tracks are frozen, unfreeze and continue to distribute space *)
      distribute_space_up_to_limits extra_space tracks track_is_affected
        (fun _ -> 1.0) (* Equal distribution *)
        (fun track ->
          if track.Grid_track.growth_limit = Float.infinity then
            track.Grid_track.base_size
          else track.Grid_track.growth_limit)
        (fun track -> Grid_track.fit_content_limit track axis_inner_node_size)
      |> ignore;

    (* 4. Update planned increases *)
    Array.iter
      (fun track ->
        if
          track.Grid_track.item_incurred_increase
          > track.Grid_track.growth_limit_planned_increase
        then
          track.Grid_track.growth_limit_planned_increase <-
            track.Grid_track.item_incurred_increase;
        (* Reset item_incurred_increase for next distribution *)
        track.Grid_track.item_incurred_increase <- 0.0)
      tracks

(* 11.5.1. Distributing Extra Space Across Spanned Tracks *)
let distribute_item_space_to_base_size (is_flex : bool)
    (use_flex_factor_for_distribution : bool) (space : float)
    (tracks : Grid_track.t array) (track_is_affected : Grid_track.t -> bool)
    (track_limit : Grid_track.t -> float)
    (intrinsic_contribution_type : intrinsic_contribution_type) : unit =
  (* Skip this distribution if there is either no space to distribute or no
     affected tracks *)
  if space = 0.0 || not (Array.exists track_is_affected tracks) then ()
  else
    (* Choose the distribution proportion function based on whether we're
       distributing to flex tracks *)
    let track_distribution_proportion =
      if is_flex && use_flex_factor_for_distribution then fun track ->
        Grid_track.flex_factor track
      else fun _ -> 1.0
    in

    (* Filter affected tracks to only include flexible tracks when distributing
       to flex tracks *)
    let final_track_is_affected =
      if is_flex then fun track ->
        Grid_track.is_flexible track && track_is_affected track
      else track_is_affected
    in

    (* 1. Find the space to distribute *)
    let track_sizes =
      Array.fold_left
        (fun sum track -> sum +. track.Grid_track.base_size)
        0.0 tracks
    in
    let extra_space = max 0.0 (space -. track_sizes) in

    (* 2. Distribute space up to limits *)
    let threshold = 0.000001 in
    let remaining_space =
      distribute_space_up_to_limits extra_space tracks final_track_is_affected
        track_distribution_proportion
        (fun track -> track.Grid_track.base_size)
        track_limit
    in

    (* 3. Distribute remaining space beyond limits (if any) *)
    (if remaining_space > threshold then
       (* Determine filter for tracks that can receive space beyond limits *)
       let filter =
         match intrinsic_contribution_type with
         | Minimum ->
             (* For minimum contributions: tracks with intrinsic max sizing
                function *)
             fun track ->
               Style.Grid.Track_sizing_function.Max.is_intrinsic
                 track.Grid_track.track_sizing_function
         | Maximum ->
             (* For maximum contributions: tracks with max-content min or
                max/fit-content max *)
             fun track ->
               Style.Grid.Track_sizing_function.Min.is_max_content
                 track.Grid_track.track_sizing_function
               || Style.Grid.Track_sizing_function.Max.is_max_or_fit_content
                    track.Grid_track.track_sizing_function
       in

       (* If there are no tracks matching the filter, use all affected tracks *)
       let has_matching_tracks =
         Array.exists
           (fun track -> final_track_is_affected track && filter track)
           tracks
       in
       let combined_filter =
         if has_matching_tracks then fun track ->
           final_track_is_affected track && filter track
         else final_track_is_affected
       in

       distribute_space_up_to_limits remaining_space tracks combined_filter
         track_distribution_proportion
         (fun track -> track.Grid_track.base_size)
         track_limit
       |> ignore);

    (* 4. Update planned increases *)
    Array.iter
      (fun track ->
        if
          track.Grid_track.item_incurred_increase
          > track.Grid_track.base_size_planned_increase
        then
          track.Grid_track.base_size_planned_increase <-
            track.Grid_track.item_incurred_increase;
        (* Reset item_incurred_increase for next distribution *)
        track.Grid_track.item_incurred_increase <- 0.0)
      tracks

(* 11.5 Resolve Intrinsic Track Sizes *)
let resolve_intrinsic_track_sizes (type t)
    (module Tree : LAYOUT_PARTIAL_TREE with type t = t) (tree : t)
    (axis : abstract_axis) (axis_tracks : Grid_track.t array)
    (other_axis_tracks : Grid_track.t array) (items : Grid_item.t array)
    (axis_available_grid_space : Available_space.t)
    (inner_node_size : float option size)
    (get_track_size_estimate :
      Grid_track.t -> float option -> t -> float option) : unit =
  (* Step 1. Shim baseline-aligned items - already done in
     resolve_item_baselines *)

  (* Step 2. Sort items by span size and whether they cross flex tracks *)
  (* The track sizing algorithm requires us to iterate through the items in ascending order of the number of
     tracks they span (first items that span 1 track, then items that span 2 tracks, etc). *)
  Array.sort (cmp_by_cross_flex_then_span_then_start axis) items;

  (* Compute some shared values *)
  let axis_inner_node_size = Size.get axis inner_node_size in
  let flex_factor_sum =
    Array.fold_left
      (fun sum track -> sum +. Grid_track.flex_factor track)
      0.0 axis_tracks
  in

  (* Create intrinsic size measurer *)
  let item_sizer =
    Intrinsic_size_measurer.
      {
        tree;
        other_axis_tracks;
        get_track_size_estimate;
        axis;
        inner_node_size;
      }
  in

  (* Process items in batches *)
  let batcher = new_item_batcher axis in
  let rec process_batches () =
    match item_batcher_next batcher items with
    | None -> ()
    | Some (batch, is_flex) ->
        let batch_span = Grid_item.span batch.(0) axis in

        (* Special case for single-span items that don't cross flex tracks *)
        if (not is_flex) && batch_span = 1 then (
          (* Size tracks to fit non-spanning items *)
          Array.iter
            (fun item ->
              let track_index =
                (Grid_item.placement_indexes item axis).start + 1
              in
              let track = axis_tracks.(track_index) in

              (* Handle base sizes based on min track sizing function *)
              let new_base_size =
                if
                  Style.Grid.Track_sizing_function.Min.is_min_content
                    track.Grid_track.track_sizing_function
                then
                  max track.Grid_track.base_size
                    (Intrinsic_size_measurer.min_content_contribution
                       (module Tree)
                       item_sizer item)
                else if
                  Style.Grid.Track_sizing_function.Min.uses_percentage
                    track.Grid_track.track_sizing_function
                  && Option.is_none axis_inner_node_size
                then
                  (* If the container size is indefinite and has not yet been
                     resolved then percentage sized tracks should be treated as
                     min-content *)
                  max track.Grid_track.base_size
                    (Intrinsic_size_measurer.min_content_contribution
                       (module Tree)
                       item_sizer item)
                else if
                  Style.Grid.Track_sizing_function.Min.is_max_content
                    track.Grid_track.track_sizing_function
                then
                  max track.Grid_track.base_size
                    (Intrinsic_size_measurer.max_content_contribution
                       (module Tree)
                       item_sizer item)
                else if
                  Style.Grid.Track_sizing_function.Min.is_auto
                    track.Grid_track.track_sizing_function
                then
                  let space =
                    match axis_available_grid_space with
                    | (Available_space.Min_content | Available_space.Max_content)
                      when not
                             (Overflow.is_container
                                (Point.get axis item.overflow)) ->
                        let axis_minimum_size =
                          Intrinsic_size_measurer.minimum_contribution
                            (module Tree)
                            item_sizer item axis_tracks
                        in
                        let axis_min_content_size =
                          Intrinsic_size_measurer.min_content_contribution
                            (module Tree)
                            item_sizer item
                        in
                        let limit =
                          Style.Grid.Track_sizing_function.Max
                          .definite_limit_with_calc
                            track.Grid_track.track_sizing_function
                            axis_inner_node_size
                            (Tree.resolve_calc_value tree)
                        in
                        let limited_min_content =
                          match limit with
                          | Some lim -> min axis_min_content_size lim
                          | None -> axis_min_content_size
                        in
                        max limited_min_content axis_minimum_size
                    | _ ->
                        Intrinsic_size_measurer.minimum_contribution
                          (module Tree)
                          item_sizer item axis_tracks
                  in
                  max track.Grid_track.base_size space
                else track.Grid_track.base_size
              in
              axis_tracks.(track_index).Grid_track.base_size <- new_base_size;

              (* Handle growth limits *)
              let track = axis_tracks.(track_index) in
              if
                Style.Grid.Track_sizing_function.Max.is_fit_content
                  track.Grid_track.track_sizing_function
              then (
                (* If item is not a scroll container, then increase the growth
                   limit to at least the size of the min-content contribution *)
                if not (Overflow.is_container (Point.get axis item.overflow))
                then
                  track.Grid_track.growth_limit_planned_increase <-
                    max track.Grid_track.growth_limit_planned_increase
                      (Intrinsic_size_measurer.min_content_contribution
                         (module Tree)
                         item_sizer item);

                (* Always increase the growth limit to at least the size of the
                   "fit-content limited" max-content contribution *)
                let fit_content_limit =
                  Grid_track.fit_content_limit track axis_inner_node_size
                in
                let max_content_contribution =
                  min
                    (Intrinsic_size_measurer.max_content_contribution
                       (module Tree)
                       item_sizer item)
                    fit_content_limit
                in
                track.Grid_track.growth_limit_planned_increase <-
                  max track.Grid_track.growth_limit_planned_increase
                    max_content_contribution)
              else if
                Style.Grid.Track_sizing_function.Max.is_max_content_alike
                  track.Grid_track.track_sizing_function
                || Style.Grid.Track_sizing_function.Max.uses_percentage
                     track.Grid_track.track_sizing_function
                   && Option.is_none axis_inner_node_size
              then
                track.Grid_track.growth_limit_planned_increase <-
                  max track.Grid_track.growth_limit_planned_increase
                    (Intrinsic_size_measurer.max_content_contribution
                       (module Tree)
                       item_sizer item)
              else if
                Style.Grid.Track_sizing_function.Max.is_intrinsic
                  track.Grid_track.track_sizing_function
              then
                track.Grid_track.growth_limit_planned_increase <-
                  max track.Grid_track.growth_limit_planned_increase
                    (Intrinsic_size_measurer.min_content_contribution
                       (module Tree)
                       item_sizer item))
            batch;

          (* Apply growth limit increases and ensure growth_limit >=
             base_size *)
          Array.iter
            (fun track ->
              if track.Grid_track.growth_limit_planned_increase > 0.0 then
                track.Grid_track.growth_limit <-
                  (if track.Grid_track.growth_limit = Float.infinity then
                     track.Grid_track.growth_limit_planned_increase
                   else
                     max track.Grid_track.growth_limit
                       track.Grid_track.growth_limit_planned_increase);
              track.Grid_track.infinitely_growable <- false;
              track.Grid_track.growth_limit_planned_increase <- 0.0;
              if track.Grid_track.growth_limit < track.Grid_track.base_size then
                if
                  Style.Grid.Track_sizing_function.Max.is_fit_content
                    track.Grid_track.track_sizing_function
                then track.Grid_track.base_size <- track.Grid_track.growth_limit
                else track.Grid_track.growth_limit <- track.Grid_track.base_size)
            axis_tracks;

          process_batches ())
        else
          (* Handle multi-span items and items crossing flex tracks *)
          let use_flex_factor_for_distribution =
            is_flex && flex_factor_sum <> 0.0
          in

          (* Handle multi-span items and items crossing flex tracks *)
          (* This is a simplified implementation - the full algorithm has many more steps *)
          (* For now, we'll just ensure tracks are properly sized *)

          (* 1. For intrinsic minimums *)
          Array.iter
            (fun item ->
              if Grid_item.crosses_intrinsic_track item axis then
                (* QUIRK: The spec says that: If the grid container is being
                   sized under a min- or max-content constraint, use the items'
                   limited min-content contributions in place of their minimum
                   contributions here. However, in practice browsers only seem
                   to apply this rule if the item is not a scroll container,
                   giving the automatic minimum size of scroll containers (zero)
                   precedence over the min-content contributions. *)
                let space =
                  match axis_available_grid_space with
                  | (Available_space.Min_content | Available_space.Max_content)
                    when not
                           (Overflow.is_container
                              (Point.get axis item.overflow)) ->
                      let axis_minimum_size =
                        Intrinsic_size_measurer.minimum_contribution
                          (module Tree)
                          item_sizer item axis_tracks
                      in
                      let axis_min_content_size =
                        Intrinsic_size_measurer.min_content_contribution
                          (module Tree)
                          item_sizer item
                      in
                      let calc = Tree.resolve_calc_value tree in
                      let limit =
                        Grid_item.spanned_fixed_track_limit item axis
                          axis_tracks axis_inner_node_size calc
                      in
                      let limited_min_content =
                        match limit with
                        | Some lim -> min axis_min_content_size lim
                        | None -> axis_min_content_size
                      in
                      max limited_min_content axis_minimum_size
                  | _ ->
                      Intrinsic_size_measurer.minimum_contribution
                        (module Tree)
                        item_sizer item axis_tracks
                in
                let track_range =
                  Grid_item.track_range_excluding_lines item axis
                in
                let start_idx, end_idx = track_range in
                let tracks =
                  Array.sub axis_tracks start_idx (end_idx - start_idx)
                in
                if space > 0.0 then
                  let has_intrinsic_min_track_sizing_function track =
                    Style.Grid.Track_sizing_function.Min.is_intrinsic
                      track.Grid_track.track_sizing_function
                  in
                  if Overflow.is_container (Point.get axis item.overflow) then
                    let fit_content_limit track =
                      Grid_track.fit_content_limited_growth_limit track
                        axis_inner_node_size
                    in
                    distribute_item_space_to_base_size is_flex
                      use_flex_factor_for_distribution space tracks
                      has_intrinsic_min_track_sizing_function fit_content_limit
                      Minimum
                  else
                    distribute_item_space_to_base_size is_flex
                      use_flex_factor_for_distribution space tracks
                      has_intrinsic_min_track_sizing_function
                      (fun track -> track.Grid_track.growth_limit)
                      Minimum)
            batch;
          flush_planned_base_size_increases axis_tracks;

          (* 2. For content-based minimums *)
          Array.iter
            (fun item ->
              let space =
                Intrinsic_size_measurer.min_content_contribution
                  (module Tree)
                  item_sizer item
              in
              let track_range =
                Grid_item.track_range_excluding_lines item axis
              in
              let start_idx, end_idx = track_range in
              let tracks =
                Array.sub axis_tracks start_idx (end_idx - start_idx)
              in
              if space > 0.0 then
                let has_min_or_max_content_min_track_sizing_function track =
                  Style.Grid.Track_sizing_function.Min.is_min_or_max_content
                    track.Grid_track.track_sizing_function
                in
                if Overflow.is_container (Point.get axis item.overflow) then
                  let fit_content_limit track =
                    Grid_track.fit_content_limited_growth_limit track
                      axis_inner_node_size
                  in
                  distribute_item_space_to_base_size is_flex
                    use_flex_factor_for_distribution space tracks
                    has_min_or_max_content_min_track_sizing_function
                    fit_content_limit Minimum
                else
                  distribute_item_space_to_base_size is_flex
                    use_flex_factor_for_distribution space tracks
                    has_min_or_max_content_min_track_sizing_function
                    (fun track -> track.Grid_track.growth_limit)
                    Minimum)
            batch;
          flush_planned_base_size_increases axis_tracks;

          (* 3. For max-content minimums. The Rust implementation only runs this
             when sizing under a max-content constraint. However, with a
             definite available space we still need to account for max-content
             min tracks to match Taffy's behaviour in the generated tests. *)
          if
            axis_available_grid_space = Available_space.Max_content
            || Available_space.is_definite axis_available_grid_space
          then (
            (* Helper functions matching Rust implementation *)
            let has_auto_min_track_sizing_function track =
              Style.Grid.Track_sizing_function.Min.is_auto
                track.Grid_track.track_sizing_function
              && not
                   (Style.Grid.Track_sizing_function.Max.is_min_content
                      track.Grid_track.track_sizing_function)
            in
            let has_max_content_min_track_sizing_function track =
              Style.Grid.Track_sizing_function.Min.is_max_content
                track.Grid_track.track_sizing_function
            in

            Array.iter
              (fun item ->
                let axis_max_content_size =
                  Intrinsic_size_measurer.max_content_contribution
                    (module Tree)
                    item_sizer item
                in
                let calc = Tree.resolve_calc_value tree in
                let limit =
                  Grid_item.spanned_fixed_track_limit item axis axis_tracks
                    axis_inner_node_size calc
                in
                let space =
                  match limit with
                  | Some lim -> min axis_max_content_size lim
                  | None -> axis_max_content_size
                in
                let track_range =
                  Grid_item.track_range_excluding_lines item axis
                in
                let start_idx, end_idx = track_range in
                let tracks =
                  Array.sub axis_tracks start_idx (end_idx - start_idx)
                in
                if space > 0.0 then
                  (* If any of the tracks spanned by the item have a MaxContent
                     min track sizing function then distribute space only to
                     those tracks. Otherwise distribute space to tracks with an
                     Auto min track sizing function. *)
                  if
                    Array.exists has_max_content_min_track_sizing_function
                      tracks
                  then
                    distribute_item_space_to_base_size is_flex
                      use_flex_factor_for_distribution space tracks
                      has_max_content_min_track_sizing_function
                      (fun _ -> Float.infinity)
                      Maximum
                  else
                    let fit_content_limited_growth_limit track =
                      Grid_track.fit_content_limited_growth_limit track
                        axis_inner_node_size
                    in
                    distribute_item_space_to_base_size is_flex
                      use_flex_factor_for_distribution space tracks
                      has_auto_min_track_sizing_function
                      fit_content_limited_growth_limit Maximum)
              batch;
            flush_planned_base_size_increases axis_tracks);

          (* In all cases, continue to increase the base size of tracks with a
             max-content min track sizing function by distributing extra space
             as needed to account for these items' max-content contributions. *)
          let has_max_content_min_track_sizing_function track =
            Style.Grid.Track_sizing_function.Min.is_max_content
              track.Grid_track.track_sizing_function
          in

          Array.iter
            (fun item ->
              let space =
                Intrinsic_size_measurer.max_content_contribution
                  (module Tree)
                  item_sizer item
              in
              let track_range =
                Grid_item.track_range_excluding_lines item axis
              in
              let start_idx, end_idx = track_range in
              let tracks =
                Array.sub axis_tracks start_idx (end_idx - start_idx)
              in
              if space > 0.0 then
                distribute_item_space_to_base_size is_flex
                  use_flex_factor_for_distribution space tracks
                  has_max_content_min_track_sizing_function
                  (fun track -> track.Grid_track.growth_limit)
                  Maximum)
            batch;
          flush_planned_base_size_increases axis_tracks;

          (* 4. Ensure growth limit >= base size *)
          Array.iter
            (fun track ->
              if track.Grid_track.growth_limit < track.Grid_track.base_size then
                if
                  Style.Grid.Track_sizing_function.Max.is_fit_content
                    track.Grid_track.track_sizing_function
                then track.Grid_track.base_size <- track.Grid_track.growth_limit
                else track.Grid_track.growth_limit <- track.Grid_track.base_size)
            axis_tracks;

          (* 5. For intrinsic maximums (if not flex) *)
          if not is_flex then (
            Array.iter
              (fun item ->
                let space =
                  Intrinsic_size_measurer.min_content_contribution
                    (module Tree)
                    item_sizer item
                in
                let track_range =
                  Grid_item.track_range_excluding_lines item axis
                in
                let start_idx, end_idx = track_range in
                let tracks =
                  Array.sub axis_tracks start_idx (end_idx - start_idx)
                in
                if space > 0.0 then
                  distribute_item_space_to_growth_limit space tracks
                    (fun track ->
                      Style.Grid.Track_sizing_function.Max.is_intrinsic
                        track.Grid_track.track_sizing_function)
                    axis_inner_node_size)
              batch;
            flush_planned_growth_limit_increases axis_tracks true;

            (* 6. For max-content maximums *)
            Array.iter
              (fun item ->
                let space =
                  Intrinsic_size_measurer.max_content_contribution
                    (module Tree)
                    item_sizer item
                in
                let track_range =
                  Grid_item.track_range_excluding_lines item axis
                in
                let start_idx, end_idx = track_range in
                let tracks =
                  Array.sub axis_tracks start_idx (end_idx - start_idx)
                in
                if space > 0.0 then
                  distribute_item_space_to_growth_limit space tracks
                    (fun track ->
                      Style.Grid.Track_sizing_function.Max.is_max_content_alike
                        track.Grid_track.track_sizing_function
                      || Style.Grid.Track_sizing_function.Max.uses_percentage
                           track.Grid_track.track_sizing_function
                         && Option.is_none axis_inner_node_size)
                    axis_inner_node_size)
              batch;
            flush_planned_growth_limit_increases axis_tracks false);

          process_batches ()
  in
  process_batches ();

  (* Step 5. If any track still has an infinite growth limit, set its growth
     limit to its base size *)
  Array.iter
    (fun track ->
      if track.Grid_track.growth_limit = Float.infinity then
        track.Grid_track.growth_limit <- track.Grid_track.base_size)
    axis_tracks

(* 11.6 Maximise Tracks Distributes free space (if any) to tracks with FINITE
   growth limits, up to their limits. *)
let maximise_tracks (axis_tracks : Grid_track.t array)
    (axis_inner_node_size : float option)
    (axis_available_grid_space : Available_space.t) : unit =
  let used_space =
    Array.fold_left
      (fun sum track -> sum +. track.Grid_track.base_size)
      0.0 axis_tracks
  in
  let free_space =
    Available_space.compute_free_space axis_available_grid_space used_space
  in

  if free_space = Float.infinity then
    (* If free space is infinite, set all track base sizes to their growth
       limits *)
    Array.iter
      (fun track -> track.Grid_track.base_size <- track.Grid_track.growth_limit)
      axis_tracks
  else if free_space > 0.0 then (
    (* Distribute free space up to growth limits *)
    distribute_space_up_to_limits free_space axis_tracks
      (fun _ -> true) (* All tracks are affected *)
      (fun _ -> 1.0) (* Equal distribution *)
      (fun track -> track.Grid_track.base_size)
      (fun track ->
        Grid_track.fit_content_limited_growth_limit track axis_inner_node_size)
    |> ignore;

    (* Apply the incurred increases to base sizes *)
    Array.iter
      (fun track ->
        track.Grid_track.base_size <-
          track.Grid_track.base_size +. track.Grid_track.item_incurred_increase;
        track.Grid_track.item_incurred_increase <- 0.0)
      axis_tracks)

(* 11.7.1. Find the Size of an fr This algorithm finds the largest size that an
   fr unit can be without exceeding the target size. *)
let find_size_of_fr (tracks : Grid_track.t array) (space_to_fill : float) :
    float =
  (* Handle the trivial case where there is no space to fill *)
  if space_to_fill = 0.0 then 0.0
  else
    (* If the product of the hypothetical fr size and any flexible track's flex
       factor is less than the track's base size, then we must restart this
       algorithm treating all such tracks as inflexible. *)
    let rec find_fr_size hypothetical_fr_size =
      (* Calculate leftover space and flex factor sum *)
      let used_space = ref 0.0 in
      let naive_flex_factor_sum = ref 0.0 in

      Array.iter
        (fun track ->
          (* Tracks for which flex_factor * hypothetical_fr_size <
             track.base_size are treated as inflexible *)
          if
            Style.Grid.Track_sizing_function.Max.is_fr
              track.Grid_track.track_sizing_function
          then
            let flex_factor =
              Style.Grid.Track_sizing_function.Max.fr_value
                track.Grid_track.track_sizing_function
            in
            if flex_factor *. hypothetical_fr_size >= track.Grid_track.base_size
            then naive_flex_factor_sum := !naive_flex_factor_sum +. flex_factor
            else used_space := !used_space +. track.Grid_track.base_size
          else used_space := !used_space +. track.Grid_track.base_size)
        tracks;

      let leftover_space = space_to_fill -. !used_space in
      let flex_factor = max !naive_flex_factor_sum 1.0 in

      (* Calculate the new hypothetical fr size *)
      let new_hypothetical_fr_size = leftover_space /. flex_factor in

      (* Check if all flexible tracks are valid with this fr size *)
      let is_valid =
        Array.for_all
          (fun track ->
            if
              Style.Grid.Track_sizing_function.Max.is_fr
                track.Grid_track.track_sizing_function
            then
              let flex_factor =
                Style.Grid.Track_sizing_function.Max.fr_value
                  track.Grid_track.track_sizing_function
              in
              flex_factor *. new_hypothetical_fr_size
              >= track.Grid_track.base_size
              || flex_factor *. hypothetical_fr_size
                 < track.Grid_track.base_size
            else true)
          tracks
      in

      if is_valid then new_hypothetical_fr_size
      else find_fr_size new_hypothetical_fr_size
    in

    (* Start with infinity as the initial hypothetical fr size *)
    find_fr_size Float.infinity

(* 11.7. Expand Flexible Tracks This step sizes flexible tracks using the
   largest value it can assign to an fr without exceeding the available
   space. *)
let expand_flexible_tracks (type t)
    (module Tree : LAYOUT_PARTIAL_TREE with type t = t) (tree : t)
    (axis : abstract_axis) (axis_tracks : Grid_track.t array)
    (items : Grid_item.t array) (axis_min_size : float option)
    (axis_max_size : float option)
    (axis_available_space_for_expansion : Available_space.t)
    (inner_node_size : float option size) : unit =
  (* First, find the grid's used flex fraction *)
  let flex_fraction =
    match axis_available_space_for_expansion with
    (* If the free space is zero: The used flex fraction is zero. Otherwise, if
       the free space is a definite length: The used flex fraction is the result
       of finding the size of an fr using all of the grid tracks and a space to
       fill of the available grid space. *)
    | Available_space.Definite available_space ->
        let used_space =
          Array.fold_left
            (fun sum track -> sum +. track.Grid_track.base_size)
            0.0 axis_tracks
        in
        let free_space = available_space -. used_space in
        if free_space <= 0.0 then 0.0
        else find_size_of_fr axis_tracks available_space
    (* If ... sizing the grid container under a min-content constraint the used
       flex fraction is zero. *)
    | Available_space.Min_content -> 0.0
    (* Otherwise, if the free space is an indefinite length: *)
    | Available_space.Max_content ->
        (* The used flex fraction is the maximum of: *)
        let flex_fraction =
          max
            (* For each flexible track, if the flexible track's flex factor is
               greater than one, the result of dividing the track's base size by
               its flex factor; otherwise, the track's base size. *)
            (let max_track_factor =
               Array.fold_left
                 (fun curr_max track ->
                   if
                     Style.Grid.Track_sizing_function.Max.is_fr
                       track.Grid_track.track_sizing_function
                   then
                     let flex_factor =
                       Style.Grid.Track_sizing_function.Max.fr_value
                         track.Grid_track.track_sizing_function
                     in
                     let value =
                       if flex_factor > 1.0 then
                         track.Grid_track.base_size /. flex_factor
                       else track.Grid_track.base_size
                     in
                     max curr_max value
                   else curr_max)
                 0.0 axis_tracks
             in
             max_track_factor)
            (* For each grid item that crosses a flexible track, the result of
               finding the size of an fr using all the grid tracks that the item
               crosses and a space to fill of the item's max-content
               contribution. *)
            (let max_item_factor =
               Array.fold_left
                 (fun curr_max item ->
                   if Grid_item.crosses_flexible_track item axis then
                     let start_idx, end_idx =
                       Grid_item.track_range_excluding_lines item axis
                     in
                     let tracks =
                       Array.sub axis_tracks start_idx (end_idx - start_idx)
                     in
                     (* TODO: plumb estimate of other axis size
                        (known_dimensions) in here rather than just passing
                        (Size.none)? *)
                     let max_content_contribution =
                       Grid_item.max_content_contribution
                         (module Tree)
                         item axis tree Size.none inner_node_size
                     in
                     let value =
                       find_size_of_fr tracks max_content_contribution
                     in
                     max curr_max value
                   else curr_max)
                 0.0 items
             in
             max_item_factor)
        in

        (* If using this flex fraction would cause the grid to be smaller than
           the grid container's min-width/height (or larger than the grid
           container's max-width/height), then redo this step, treating the free
           space as definite and the available grid space as equal to the grid
           container's inner size when it's sized to its min-width/height
           (max-width/height). (Note: min_size takes precedence over
           max_size) *)
        let hypothetical_grid_size =
          Array.fold_left
            (fun sum track ->
              if
                Style.Grid.Track_sizing_function.Max.is_fr
                  track.Grid_track.track_sizing_function
              then
                let track_flex_factor =
                  Style.Grid.Track_sizing_function.Max.fr_value
                    track.Grid_track.track_sizing_function
                in
                sum
                +. max track.Grid_track.base_size
                     (track_flex_factor *. flex_fraction)
              else sum +. track.Grid_track.base_size)
            0.0 axis_tracks
        in
        let axis_min_size = Option.value axis_min_size ~default:0.0 in
        let axis_max_size =
          Option.value axis_max_size ~default:Float.infinity
        in
        if hypothetical_grid_size < axis_min_size then
          find_size_of_fr axis_tracks axis_min_size
        else if hypothetical_grid_size > axis_max_size then
          find_size_of_fr axis_tracks axis_max_size
        else flex_fraction
  in

  (* For each flexible track, if the product of the used flex fraction and the
     track's flex factor is greater than the track's base size, set its base
     size to that product. *)
  Array.iter
    (fun track ->
      if
        Style.Grid.Track_sizing_function.Max.is_fr
          track.Grid_track.track_sizing_function
      then
        let track_flex_factor =
          Style.Grid.Track_sizing_function.Max.fr_value
            track.Grid_track.track_sizing_function
        in
        track.Grid_track.base_size <-
          max track.Grid_track.base_size (track_flex_factor *. flex_fraction))
    axis_tracks

(* 11.8. Stretch auto Tracks This step expands tracks that have an auto max
   track sizing function by dividing any remaining positive, definite free space
   equally amongst them. *)
let stretch_auto_tracks (axis_tracks : Grid_track.t array)
    (axis_min_size : float option)
    (axis_available_space_for_expansion : Available_space.t) : unit =
  let num_auto_tracks =
    Array.fold_left
      (fun count track ->
        if
          Style.Grid.Track_sizing_function.Max.is_auto
            track.Grid_track.track_sizing_function
        then count + 1
        else count)
      0 axis_tracks
  in

  if num_auto_tracks > 0 then
    let used_space =
      Array.fold_left
        (fun sum track -> sum +. track.Grid_track.base_size)
        0.0 axis_tracks
    in

    (* If the free space is indefinite, but the grid container has a definite
       min-width/height use that size to calculate the free space for this step
       instead. *)
    let free_space =
      if Available_space.is_definite axis_available_space_for_expansion then
        Available_space.compute_free_space axis_available_space_for_expansion
          used_space
      else
        match axis_min_size with Some size -> size -. used_space | None -> 0.0
    in

    if free_space > 0.0 then
      let extra_space_per_auto_track =
        free_space /. float_of_int num_auto_tracks
      in
      Array.iter
        (fun track ->
          if
            Style.Grid.Track_sizing_function.Max.is_auto
              track.Grid_track.track_sizing_function
          then
            track.Grid_track.base_size <-
              track.Grid_track.base_size +. extra_space_per_auto_track)
        axis_tracks

(* Track sizing algorithm Note: Gutters are treated as empty fixed-size tracks
   for the purpose of the track sizing algorithm. *)
let track_sizing_algorithm (type t)
    (module Tree : LAYOUT_PARTIAL_TREE with type t = t) (tree : t)
    (axis : abstract_axis) (axis_min_size : float option)
    (axis_max_size : float option) (axis_alignment : align_content)
    (other_axis_alignment : align_content)
    (available_grid_space : Available_space.t size)
    (inner_node_size : float option size) (axis_tracks : Grid_track.t array)
    (other_axis_tracks : Grid_track.t array) (items : Grid_item.t array)
    (get_track_size_estimate :
      Grid_track.t -> float option -> t -> float option)
    (has_baseline_aligned_item : bool) : unit =
  (* 11.4 Initialise Track sizes Initialize each track's base size and growth
     limit. *)
  let percentage_basis =
    match Size.get axis inner_node_size with
    | Some value -> Some value
    | None -> axis_min_size
  in
  initialize_track_sizes tree
    (fun _ -> Tree.resolve_calc_value tree)
    axis_tracks percentage_basis;

  (* 11.5.1 Shim item baselines *)
  if has_baseline_aligned_item then
    resolve_item_baselines (module Tree) tree axis items inner_node_size;

  (* If all tracks have base_size = growth_limit, then skip the rest of this
     function. Note: this can only happen both track sizing function have the
     same fixed track sizing function *)
  if
    Array.for_all
      (fun track -> track.Grid_track.base_size = track.Grid_track.growth_limit)
      axis_tracks
  then ()
  else (* Pre-computations for 11.5 Resolve Intrinsic Track Sizes *)
    (* Compute an additional amount to add to each spanned gutter when computing
       item's estimated size in the in the opposite axis based on the alignment,
       container size, and estimated track sizes in that axis *)
    let gutter_alignment_adjustment =
      compute_alignment_gutter_adjustment other_axis_alignment
        (Size.get (Abstract_axis.other axis) inner_node_size)
        (fun track basis -> get_track_size_estimate track basis tree)
        other_axis_tracks
    in

    (* Set content_alignment_adjustment for inner gutter tracks *)
    (if Array.length other_axis_tracks > 3 then
       let len = Array.length other_axis_tracks in
       (* Inner gutter tracks are at indices 2, 4, 6, ... (step by 2) *)
       let i = ref 2 in
       while !i < len do
         other_axis_tracks.(!i).Grid_track.content_alignment_adjustment <-
           gutter_alignment_adjustment;
         i := !i + 2
       done);

    (* 11.5 Resolve Intrinsic Track Sizes *)
    resolve_intrinsic_track_sizes
      (module Tree)
      tree axis axis_tracks other_axis_tracks items
      (Size.get axis available_grid_space)
      inner_node_size get_track_size_estimate;

    (* 11.6. Maximise Tracks Distributes free space (if any) to tracks with
       FINITE growth limits, up to their limits. *)
    maximise_tracks axis_tracks
      (Size.get axis inner_node_size)
      (Size.get axis available_grid_space);

    (* For the purpose of the final two expansion steps ("Expand Flexible
       Tracks" and "Stretch auto Tracks"), we only want to expand into space
       generated by the grid container's size (as defined by either it's
       preferred size style or by it's parent node through something like
       stretch alignment), not just any available space. To do this we map
       definite available space to AvailableSpace::MaxContent in the case that
       inner_node_size is None *)
    let axis_available_space_for_expansion =
      match Size.get axis inner_node_size with
      | Some available_space -> Available_space.Definite available_space
      | None -> (
          match Size.get axis available_grid_space with
          | Available_space.Min_content -> Available_space.Min_content
          | Available_space.Max_content | Available_space.Definite _ ->
              Available_space.Max_content)
    in

    (* 11.7. Expand Flexible Tracks This step sizes flexible tracks using the
       largest value it can assign to an fr without exceeding the available
       space. *)
    expand_flexible_tracks
      (module Tree)
      tree axis axis_tracks items axis_min_size axis_max_size
      axis_available_space_for_expansion inner_node_size;

    (* 11.8. Stretch auto Tracks This step expands tracks that have an auto max
       track sizing function by dividing any remaining positive, definite free
       space equally amongst them. *)
    if axis_alignment = Align_content.Stretch then
      stretch_auto_tracks axis_tracks axis_min_size
        axis_available_space_for_expansion