⎇ bf3dfaec9e387a7e67408fc78ca869d7eaaa8e1f
src/compute/grid/track_sizing.rs
Ñawpa willay
Pi imata llamkarqan
ch'uya
Grid: Fixes for minmax, fr proportions and distributing space across multiple tracks (#349)
1//! Implements the track sizing algorithm
2//! https://www.w3.org/TR/css-grid-1/#layout-algorithm
3use super::types::{GridItem, GridTrack, TrackCounts};
4use crate::axis::AbstractAxis;
5use crate::compute::{GenericAlgorithm, LayoutAlgorithm};
6use crate::geometry::{Rect, Size};
7use crate::layout::SizingMode;
8use crate::math::MaybeMath;
9use crate::prelude::{LayoutTree, TaffyMinContent};
10use crate::resolve::ResolveOrZero;
11use crate::style::{
12 AlignContent, AlignSelf, AvailableSpace, LengthPercentage, MaxTrackSizingFunction, MinTrackSizingFunction,
13};
14use crate::sys::{f32_max, f32_min};
15use core::cmp::Ordering;
16
17/// Takes an axis, and a list of grid items sorted firstly by whether they cross a flex track
18/// in the specified axis (items that don't cross a flex track first) and then by the number
19/// of tracks they cross in specified axis (ascending order).
20struct ItemBatcher {
21 /// The axis in which the ItemBatcher is operating. Used when querying properties from items.
22 axis: AbstractAxis,
23 /// The starting index of the current batch
24 index_offset: usize,
25 /// The span of the items in the current batch
26 current_span: u16,
27 /// Whether the current batch of items cross a flexible track
28 current_is_flex: bool,
29}
30
31impl ItemBatcher {
32 /// Create a new ItemBatcher for the specified axis
33 #[inline(always)]
34 fn new(axis: AbstractAxis) -> Self {
35 ItemBatcher { index_offset: 0, axis, current_span: 1, current_is_flex: false }
36 }
37
38 /// This is basically a manual version of Iterator::next which passes `items`
39 /// in as a parameter on each iteration to work around borrow checker rules
40 #[inline]
41 fn next<'items>(&mut self, items: &'items mut [GridItem]) -> Option<(&'items mut [GridItem], bool)> {
42 if self.current_is_flex || self.index_offset >= items.len() {
43 return None;
44 }
45
46 let item = &items[self.index_offset];
47 self.current_span = item.span(self.axis);
48 self.current_is_flex = item.crosses_flexible_track(self.axis);
49
50 let next_index_offset = if self.current_is_flex {
51 items.len()
52 } else {
53 items
54 .iter()
55 .position(|item: &GridItem| {
56 item.crosses_flexible_track(self.axis) || item.span(self.axis) > self.current_span
57 })
58 .unwrap_or(items.len())
59 };
60
61 let batch_range = self.index_offset..next_index_offset;
62 self.index_offset = next_index_offset;
63
64 let batch = &mut items[batch_range];
65 Some((batch, self.current_is_flex))
66 }
67}
68
69/// This struct captures a bunch of variables which are used to compute the intrinsic sizes of children so that those variables
70/// don't have to be passed around all over the place below. It then has methods that implement the intrinsic sizing computations
71struct IntrisicSizeMeasurer<'tree, 'oat, Tree, EstimateFunction>
72where
73 Tree: LayoutTree,
74 EstimateFunction: Fn(&GridTrack, Option<f32>) -> Option<f32>,
75{
76 /// The layout tree
77 tree: &'tree mut Tree,
78 /// The tracks in the opposite axis to the one we are currently sizing
79 other_axis_tracks: &'oat [GridTrack],
80 /// A function that computes an estimate of an other-axis track's size which is passed to
81 /// the child size measurement functions
82 get_track_size_estimate: EstimateFunction,
83 /// The axis we are currently sizing
84 axis: AbstractAxis,
85 /// The available grid space
86 inner_node_size: Size<Option<f32>>,
87}
88
89impl<'tree, 'oat, Tree, EstimateFunction> IntrisicSizeMeasurer<'tree, 'oat, Tree, EstimateFunction>
90where
91 Tree: LayoutTree,
92 EstimateFunction: Fn(&GridTrack, Option<f32>) -> Option<f32>,
93{
94 /// Compute the known_dimensions to be passed to the child sizing functions
95 /// These are estimates based on either the max track sizing function or the provisional base size in the opposite
96 /// axis to the one currently being sized.
97 /// https://www.w3.org/TR/css-grid-1/#algo-overview
98 #[inline(always)]
99 fn known_dimensions(&self, item: &mut GridItem) -> Size<Option<f32>> {
100 item.known_dimensions_cached(
101 self.axis,
102 self.other_axis_tracks,
103 self.inner_node_size.get(self.axis.other()),
104 &self.get_track_size_estimate,
105 )
106 }
107
108 /// Compute the item's resolved margins for size contributions. Horizontal percentage margins always resolve
109 /// to zero if the container size is indefinite as otherwise this would introduce a cyclic dependency.
110 #[inline(always)]
111 fn margins_axis_sums_with_baseline_shims(&self, item: &mut GridItem) -> Size<f32> {
112 let parent_width = self.inner_node_size.width;
113 Rect {
114 left: item.margin.left.resolve_or_zero(Some(0.0)),
115 right: item.margin.right.resolve_or_zero(Some(0.0)),
116 top: item.margin.top.resolve_or_zero(parent_width) + item.baseline_shim,
117 bottom: item.margin.bottom.resolve_or_zero(parent_width),
118 }
119 .sum_axes()
120 }
121
122 /// Retrieve the item's min content contribution from the cache or compute it using the provided parameters
123 #[inline(always)]
124 fn min_content_contribution(&mut self, item: &mut GridItem) -> f32 {
125 let known_dimensions = self.known_dimensions(item);
126 let margin_axis_sums = self.margins_axis_sums_with_baseline_shims(item);
127 let contribution =
128 item.min_content_contribution_cached(self.axis, self.tree, known_dimensions, self.inner_node_size);
129 contribution + margin_axis_sums.get(self.axis)
130 }
131
132 /// Retrieve the item's max content contribution from the cache or compute it using the provided parameters
133 #[inline(always)]
134 fn max_content_contribution(&mut self, item: &mut GridItem) -> f32 {
135 let known_dimensions = self.known_dimensions(item);
136 let margin_axis_sums = self.margins_axis_sums_with_baseline_shims(item);
137 let contribution =
138 item.max_content_contribution_cached(self.axis, self.tree, known_dimensions, self.inner_node_size);
139 contribution + margin_axis_sums.get(self.axis)
140 }
141
142 /// The minimum contribution of an item is the smallest outer size it can have.
143 /// Specifically:
144 /// - If the item’s computed preferred size behaves as auto or depends on the size of its containing block in the relevant axis:
145 /// Its minimum contribution is the outer size that would result from assuming the item’s used minimum size as its preferred size;
146 /// - Else the item’s minimum contribution is its min-content contribution.
147 /// Because the minimum contribution often depends on the size of the item’s content, it is considered a type of intrinsic size contribution.
148 #[inline(always)]
149 fn minimum_contribution(&mut self, item: &mut GridItem, axis_tracks: &[GridTrack]) -> f32 {
150 let known_dimensions = self.known_dimensions(item);
151 let margin_axis_sums = self.margins_axis_sums_with_baseline_shims(item);
152 let contribution =
153 item.minimum_contribution_cached(self.tree, self.axis, axis_tracks, known_dimensions, self.inner_node_size);
154 contribution + margin_axis_sums.get(self.axis)
155 }
156}
157
158/// To make track sizing efficient we want to order tracks
159/// Here a placement is either a Line<i16> representing a row-start/row-end or a column-start/column-end
160#[inline(always)]
161pub(super) fn cmp_by_cross_flex_then_span_then_start(
162 axis: AbstractAxis,
163) -> impl FnMut(&GridItem, &GridItem) -> Ordering {
164 move |item_a: &GridItem, item_b: &GridItem| -> Ordering {
165 match (item_a.crosses_flexible_track(axis), item_b.crosses_flexible_track(axis)) {
166 (false, true) => Ordering::Less,
167 (true, false) => Ordering::Greater,
168 _ => {
169 let placement_a = item_a.placement(axis);
170 let placement_b = item_b.placement(axis);
171 match placement_a.span().cmp(&placement_b.span()) {
172 Ordering::Less => Ordering::Less,
173 Ordering::Greater => Ordering::Greater,
174 Ordering::Equal => placement_a.start.cmp(&placement_b.start),
175 }
176 }
177 }
178 }
179}
180
181/// When applying the track sizing algorithm and estimating the size in the other axis for content sizing items
182/// we should take into account align-content/justify-content if both the grid container and all items in the
183/// other axis have definite sizes. This function computes such a per-gutter additional size adjustment.
184#[inline(always)]
185pub(super) fn compute_alignment_gutter_adjustment(
186 alignment: AlignContent,
187 axis_inner_node_size: Option<f32>,
188 get_track_size_estimate: impl Fn(&GridTrack, Option<f32>) -> Option<f32>,
189 tracks: &[GridTrack],
190) -> f32 {
191 if tracks.len() <= 1 {
192 return 0.0;
193 }
194
195 // As items never cross the outermost gutters in a grid, we can simplify our calculations by treating
196 // AlignContent::Start and AlignContent::End the same
197 let outer_gutter_weight = match alignment {
198 AlignContent::Start => 1,
199 AlignContent::FlexStart => 1,
200 AlignContent::End => 1,
201 AlignContent::FlexEnd => 1,
202 AlignContent::Center => 1,
203 AlignContent::Stretch => 0,
204 AlignContent::SpaceBetween => 0,
205 AlignContent::SpaceAround => 1,
206 AlignContent::SpaceEvenly => 1,
207 };
208
209 let inner_gutter_weight = match alignment {
210 AlignContent::FlexStart => 0,
211 AlignContent::Start => 0,
212 AlignContent::FlexEnd => 0,
213 AlignContent::End => 0,
214 AlignContent::Center => 0,
215 AlignContent::Stretch => 0,
216 AlignContent::SpaceBetween => 1,
217 AlignContent::SpaceAround => 2,
218 AlignContent::SpaceEvenly => 1,
219 };
220
221 if inner_gutter_weight == 0 {
222 return 0.0;
223 }
224
225 if let Some(axis_inner_node_size) = axis_inner_node_size {
226 let free_space = tracks
227 .iter()
228 .map(|track| get_track_size_estimate(track, Some(axis_inner_node_size)))
229 .sum::<Option<f32>>()
230 .map(|track_size_sum| f32_max(0.0, axis_inner_node_size - track_size_sum))
231 .unwrap_or(0.0);
232
233 let weighted_track_count =
234 (((tracks.len() - 3) / 2) * inner_gutter_weight as usize) + (2 * outer_gutter_weight as usize);
235
236 return (free_space / weighted_track_count as f32) * inner_gutter_weight as f32;
237 }
238
239 0.0
240}
241
242/// Convert origin-zero coordinates track placement in grid track vector indexes
243#[inline(always)]
244pub(super) fn resolve_item_track_indexes(items: &mut [GridItem], column_counts: TrackCounts, row_counts: TrackCounts) {
245 for item in items {
246 item.column_indexes = item.column.map(|line| line.into_track_vec_index(column_counts) as u16);
247 item.row_indexes = item.row.map(|line| line.into_track_vec_index(row_counts) as u16);
248 }
249}
250
251/// Determine (in each axis) whether the item crosses any flexible tracks
252#[inline(always)]
253pub(super) fn determine_if_item_crosses_flexible_or_intrinsic_tracks(
254 items: &mut Vec<GridItem>,
255 columns: &[GridTrack],
256 rows: &[GridTrack],
257) {
258 for item in items {
259 item.crosses_flexible_column =
260 item.track_range_excluding_lines(AbstractAxis::Inline).any(|i| columns[i].is_flexible());
261 item.crosses_intrinsic_column =
262 item.track_range_excluding_lines(AbstractAxis::Inline).any(|i| columns[i].has_intrinsic_sizing_function());
263 item.crosses_flexible_row =
264 item.track_range_excluding_lines(AbstractAxis::Block).any(|i| rows[i].is_flexible());
265 item.crosses_intrinsic_row =
266 item.track_range_excluding_lines(AbstractAxis::Block).any(|i| rows[i].has_intrinsic_sizing_function());
267 }
268}
269
270/// Track sizing algorithm
271/// Note: Gutters are treated as empty fixed-size tracks for the purpose of the track sizing algorithm.
272#[allow(clippy::too_many_arguments)]
273#[inline(always)]
274pub(super) fn track_sizing_algorithm<Tree: LayoutTree>(
275 tree: &mut Tree,
276 axis: AbstractAxis,
277 axis_min_size: Option<f32>,
278 axis_max_size: Option<f32>,
279 other_axis_alignment: AlignContent,
280 available_grid_space: Size<AvailableSpace>,
281 inner_node_size: Size<Option<f32>>,
282 axis_tracks: &mut [GridTrack],
283 other_axis_tracks: &mut [GridTrack],
284 items: &mut [GridItem],
285 get_track_size_estimate: impl Fn(&GridTrack, Option<f32>) -> Option<f32>,
286 has_baseline_aligned_item: bool,
287) {
288 // 11.4 Initialise Track sizes
289 // Initialize each track’s base size and growth limit.
290 initialize_track_sizes(axis_tracks, inner_node_size.get(axis));
291
292 // 11.5.1 Shim item baselines
293 if has_baseline_aligned_item {
294 resolve_item_baselines(tree, axis, items, inner_node_size);
295 }
296
297 // If all tracks have base_size = growth_limit, then skip the rest of this function.
298 // Note: this can only happen both track sizing function have the same fixed track sizing function
299 if axis_tracks.iter().all(|track| track.base_size == track.growth_limit) {
300 return;
301 }
302
303 // Pre-computations for 11.5 Resolve Intrinsic Track Sizes
304
305 // Compute an additional amount to add to each spanned gutter when computing item's estimated size in the
306 // in the opposite axis based on the alignment, container size, and estimated track sizes in that axis
307 let gutter_alignment_adjustment = compute_alignment_gutter_adjustment(
308 other_axis_alignment,
309 inner_node_size.get(axis.other()),
310 &get_track_size_estimate,
311 other_axis_tracks,
312 );
313 if other_axis_tracks.len() > 3 {
314 let len = other_axis_tracks.len();
315 let inner_gutter_tracks = other_axis_tracks[2..len].iter_mut().step_by(2);
316 for track in inner_gutter_tracks {
317 track.content_alignment_adjustment = gutter_alignment_adjustment;
318 }
319 }
320
321 // 11.5 Resolve Intrinsic Track Sizes
322 resolve_intrinsic_track_sizes(
323 tree,
324 axis,
325 axis_tracks,
326 other_axis_tracks,
327 items,
328 available_grid_space.get(axis),
329 inner_node_size,
330 get_track_size_estimate,
331 );
332
333 // 11.6. Maximise Tracks
334 // Distributes free space (if any) to tracks with FINITE growth limits, up to their limits.
335 maximise_tracks(axis_tracks, inner_node_size.get(axis), available_grid_space.get(axis));
336
337 // 11.7. Expand Flexible Tracks
338 // This step sizes flexible tracks using the largest value it can assign to an fr without exceeding the available space.
339 expand_flexible_tracks(
340 tree,
341 axis,
342 axis_tracks,
343 items,
344 axis_min_size,
345 axis_max_size,
346 available_grid_space,
347 inner_node_size,
348 );
349
350 // 11.8. Stretch auto Tracks
351 // This step expands tracks that have an auto max track sizing function by dividing any remaining positive, definite free space equally amongst them.
352 stretch_auto_tracks(axis, axis_tracks, axis_min_size, available_grid_space);
353}
354
355/// Whether it is a minimum or maximum size's space being distributed
356/// This controls behaviour of the space distribution algorithm when distributing beyond limits
357/// See "distributing space beyond limits" at https://www.w3.org/TR/css-grid-1/#extra-space
358#[derive(Copy, Clone, Debug, PartialEq, Eq)]
359enum IntrinsicContributionType {
360 /// It's a minimum size's space being distributed
361 Minimum,
362 /// It's a maximum size's space being distributed
363 Maximum,
364}
365
366/// Add any planned base size increases to the base size after a round of distributing space to base sizes
367/// Reset the planed base size increase to zero ready for the next round.
368#[inline(always)]
369fn flush_planned_base_size_increases(tracks: &mut [GridTrack]) {
370 for track in tracks {
371 track.base_size += track.base_size_planned_increase;
372 track.base_size_planned_increase = 0.0;
373 }
374}
375
376/// Add any planned growth limit increases to the growth limit after a round of distributing space to growth limits
377/// Reset the planed growth limit increase to zero ready for the next round.
378#[inline(always)]
379fn flush_planned_growth_limit_increases(tracks: &mut [GridTrack], set_infinitely_growable: bool) {
380 for track in tracks {
381 if track.growth_limit_planned_increase > 0.0 {
382 track.growth_limit = if track.growth_limit == f32::INFINITY {
383 track.base_size + track.growth_limit_planned_increase
384 } else {
385 track.growth_limit + track.growth_limit_planned_increase
386 };
387 track.infinitely_growable = set_infinitely_growable;
388 } else {
389 track.infinitely_growable = false;
390 }
391 track.growth_limit_planned_increase = 0.0
392 }
393}
394
395/// 11.4 Initialise Track sizes
396/// Initialize each track’s base size and growth limit.
397#[inline(always)]
398fn initialize_track_sizes(axis_tracks: &mut [GridTrack], axis_inner_node_size: Option<f32>) {
399 let last_track_idx = axis_tracks.len() - 1;
400
401 // First and last grid lines are always zero-sized.
402 axis_tracks[0].base_size = 0.0;
403 axis_tracks[0].growth_limit = 0.0;
404 axis_tracks[last_track_idx].base_size = 0.0;
405 axis_tracks[last_track_idx].growth_limit = 0.0;
406
407 let all_but_first_and_last = 1..last_track_idx;
408 for track in axis_tracks[all_but_first_and_last].iter_mut() {
409 // For each track, if the track’s min track sizing function is:
410 // - A fixed sizing function
411 // Resolve to an absolute length and use that size as the track’s initial base size.
412 // Note: Indefinite lengths cannot occur, as they’re treated as auto.
413 // - An intrinsic sizing function
414 // Use an initial base size of zero.
415 track.base_size = track.min_track_sizing_function.definite_value(axis_inner_node_size).unwrap_or(0.0);
416
417 // For each track, if the track’s max track sizing function is:
418 // - A fixed sizing function
419 // Resolve to an absolute length and use that size as the track’s initial growth limit.
420 // - An intrinsic sizing function
421 // Use an initial growth limit of infinity.
422 // - A flexible sizing function
423 // Use an initial growth limit of infinity.
424 track.growth_limit =
425 track.max_track_sizing_function.definite_value(axis_inner_node_size).unwrap_or(f32::INFINITY);
426
427 // In all cases, if the growth limit is less than the base size, increase the growth limit to match the base size.
428 if track.growth_limit < track.base_size {
429 track.growth_limit = track.base_size;
430 }
431 }
432}
433
434/// 11.5.1 Shim baseline-aligned items so their intrinsic size contributions reflect their baseline alignment.
435fn resolve_item_baselines(
436 tree: &mut impl LayoutTree,
437 axis: AbstractAxis,
438 items: &mut [GridItem],
439 inner_node_size: Size<Option<f32>>,
440) {
441 // Sort items by track in the other axis (row) start position so that we can iterate items in groups which
442 // are in the same track in the other axis (row)
443 let other_axis = axis.other();
444 items.sort_by_key(|item| item.placement(other_axis).start);
445
446 // Iterate over grid rows
447 let mut remaining_items = &mut items[0..];
448 while !remaining_items.is_empty() {
449 // Get the row index of the current row
450 let current_row = remaining_items[0].placement(other_axis).start;
451
452 // Find the item index of the first item that is in a different row (or None if we've reached the end of the list)
453 let next_row_first_item =
454 remaining_items.iter().position(|item| item.placement(other_axis).start != current_row);
455
456 // Use this index to split the `remaining_items` slice in two slices:
457 // - A `row_items` slice containing the items (that start) in the current row
458 // - A new `remaining_items` consisting of the remainder of the `remaining_items` slice
459 // that hasn't been split off into `row_items
460 let row_items = if let Some(index) = next_row_first_item {
461 let (row_items, tail) = remaining_items.split_at_mut(index);
462 remaining_items = tail;
463 row_items
464 } else {
465 let row_items = remaining_items;
466 remaining_items = &mut [];
467 row_items
468 };
469
470 // Count how many items in *this row* are baseline aligned
471 // If a row has one or zero items participating in baseline alignment then baseline alignment is a no-op
472 // for those items and we skip further computations for that row
473 let row_baseline_item_count = row_items.iter().filter(|item| item.align_self == AlignSelf::Baseline).count();
474 if row_baseline_item_count <= 1 {
475 continue;
476 }
477
478 // Compute the baselines of all items in the row
479 for item in row_items.iter_mut() {
480 let measured_size_and_baselines = GenericAlgorithm::perform_layout(
481 tree,
482 item.node,
483 Size::NONE,
484 inner_node_size,
485 Size::MIN_CONTENT,
486 SizingMode::InherentSize,
487 );
488
489 let baseline = measured_size_and_baselines.first_baselines.y;
490 let height = measured_size_and_baselines.size.height;
491
492 item.baseline = Some(baseline.unwrap_or(height) + item.margin.top.resolve_or_zero(inner_node_size.width));
493 }
494
495 // Compute the max baseline of all items in the row
496 let row_max_baseline =
497 row_items.iter().map(|item| item.baseline.unwrap_or(0.0)).max_by(|a, b| a.total_cmp(b)).unwrap();
498
499 // Compute the baseline shim for each item in the row
500 for item in row_items.iter_mut() {
501 item.baseline_shim = row_max_baseline - item.baseline.unwrap_or(0.0);
502 }
503 }
504}
505
506/// 11.5 Resolve Intrinsic Track Sizes
507#[allow(clippy::too_many_arguments)]
508fn resolve_intrinsic_track_sizes(
509 tree: &mut impl LayoutTree,
510 axis: AbstractAxis,
511 axis_tracks: &mut [GridTrack],
512 other_axis_tracks: &mut [GridTrack],
513 items: &mut [GridItem],
514 axis_available_grid_space: AvailableSpace,
515 inner_node_size: Size<Option<f32>>,
516 get_track_size_estimate: impl Fn(&GridTrack, Option<f32>) -> Option<f32>,
517) {
518 // Step 1. Shim baseline-aligned items so their intrinsic size contributions reflect their baseline alignment.
519
520 // Already done at this point. See resolve_item_baselines function.
521
522 // Step 2.
523
524 // The track sizing algorithm requires us to iterate through the items in ascendeding order of the number of
525 // tracks they span (first items that span 1 track, then items that span 2 tracks, etc).
526 // To avoid having to do multiple iterations of the items, we pre-sort them into this order.
527 items.sort_by(cmp_by_cross_flex_then_span_then_start(axis));
528
529 // Step 2, Step 3 and Step 4
530 // 2 & 3. Iterate over items that don't cross a flex track. Items should have already been sorted in ascending order
531 // of the number of tracks they span. Step 2 is the 1 track case and has an optimised implementation
532 // 4. Next, repeat the previous step instead considering (together, rather than grouped by span size) all items
533 // that do span a track with a flexible sizing function while
534
535 // Compute item's intrinsic (content-based) sizes
536 // Note: For items with a specified minimum size of auto (the initial value), the minimum contribution is usually equivalent
537 // to the min-content contribution—but can differ in some cases, see §6.6 Automatic Minimum Size of Grid Items.
538 // Also, minimum contribution <= min-content contribution <= max-content contribution.
539
540 let axis_inner_node_size = inner_node_size.get(axis);
541 let flex_factor_sum = axis_tracks.iter().map(|track| track.flex_factor()).sum::<f32>();
542 let mut item_sizer =
543 IntrisicSizeMeasurer { tree, other_axis_tracks, axis, inner_node_size, get_track_size_estimate };
544
545 let mut batched_item_iterator = ItemBatcher::new(axis);
546 while let Some((batch, is_flex)) = batched_item_iterator.next(items) {
547 // 2. Size tracks to fit non-spanning items: For each track with an intrinsic track sizing function and not a flexible sizing function,
548 // consider the items in it with a span of 1:
549 let batch_span = batch[0].placement(axis).span();
550 if !is_flex && batch_span == 1 {
551 for item in batch.iter_mut() {
552 let track_index = item.placement_indexes(axis).start + 1;
553 let track = &axis_tracks[track_index as usize];
554
555 // Handle base sizes
556 let new_base_size = match track.min_track_sizing_function {
557 MinTrackSizingFunction::MinContent => {
558 f32_max(track.base_size, item_sizer.min_content_contribution(item))
559 }
560 // If the container size is indefinite and has not yet been resolved then percentage sized
561 // tracks should be treated as min-content (this matches Chrome's behaviour and seems sensible)
562 MinTrackSizingFunction::Fixed(LengthPercentage::Percent(_)) => {
563 if axis_inner_node_size.is_none() {
564 f32_max(track.base_size, item_sizer.min_content_contribution(item))
565 } else {
566 track.base_size
567 }
568 }
569 MinTrackSizingFunction::MaxContent => {
570 f32_max(track.base_size, item_sizer.max_content_contribution(item))
571 }
572 MinTrackSizingFunction::Auto => {
573 let space = match axis_available_grid_space {
574 AvailableSpace::MinContent | AvailableSpace::MaxContent => {
575 let axis_minimum_size = item_sizer.minimum_contribution(item, axis_tracks);
576 let axis_min_content_size = item_sizer.min_content_contribution(item);
577 let limit = track.max_track_sizing_function.definite_limit(axis_inner_node_size);
578 axis_min_content_size.maybe_min(limit).max(axis_minimum_size)
579 }
580 AvailableSpace::Definite(_) => item_sizer.minimum_contribution(item, axis_tracks),
581 };
582 f32_max(track.base_size, space)
583 }
584 MinTrackSizingFunction::Fixed(_) => {
585 // Do nothing as it's not an intrinsic track sizing function
586 track.base_size
587 }
588 };
589 let track = &mut axis_tracks[track_index as usize];
590 track.base_size = new_base_size;
591
592 // Handle growth limits
593 if let MaxTrackSizingFunction::FitContent(_) = track.max_track_sizing_function {
594 let fit_content_limit = track.fit_content_limit(axis_inner_node_size);
595 let min_content_contribution = item_sizer.min_content_contribution(item);
596 let max_content_contribution =
597 f32_min(item_sizer.max_content_contribution(item), fit_content_limit);
598 track.growth_limit_planned_increase =
599 f32_max(track.growth_limit_planned_increase, min_content_contribution);
600 track.growth_limit_planned_increase =
601 f32_max(track.growth_limit_planned_increase, max_content_contribution);
602 } else if track.max_track_sizing_function.is_max_content_alike()
603 || track.max_track_sizing_function.uses_percentage() && axis_inner_node_size.is_none()
604 {
605 // If the container size is indefinite and has not yet been resolved then percentage sized
606 // tracks should be treated as auto (this matches Chrome's behaviour and seems sensible)
607 track.growth_limit_planned_increase =
608 f32_max(track.growth_limit_planned_increase, item_sizer.max_content_contribution(item));
609 } else if track.max_track_sizing_function.is_intrinsic() {
610 track.growth_limit_planned_increase =
611 f32_max(track.growth_limit_planned_increase, item_sizer.min_content_contribution(item));
612 }
613 }
614
615 for track in axis_tracks.iter_mut() {
616 if track.growth_limit_planned_increase > 0.0 {
617 track.growth_limit = if track.growth_limit == f32::INFINITY {
618 track.growth_limit_planned_increase
619 } else {
620 f32_max(track.growth_limit, track.growth_limit_planned_increase)
621 };
622 }
623 track.infinitely_growable = false;
624 track.growth_limit_planned_increase = 0.0;
625 if track.growth_limit < track.base_size {
626 track.growth_limit = track.base_size;
627 }
628 }
629
630 continue;
631 }
632
633 let use_flex_factor_for_distribution = is_flex && flex_factor_sum != 0.0;
634
635 // 1. For intrinsic minimums:
636 // First increase the base size of tracks with an intrinsic min track sizing function
637 let has_intrinsic_min_track_sizing_function =
638 move |track: &GridTrack| track.min_track_sizing_function.definite_value(axis_inner_node_size).is_none();
639 for item in batch.iter_mut().filter(|item| item.crosses_intrinsic_track(axis)) {
640 // ...by distributing extra space as needed to accommodate these items’ minimum contributions.
641 // If the grid container is being sized under a min- or max-content constraint, use the items’ limited min-content contributions
642 // in place of their minimum contributions here.
643 let space = match axis_available_grid_space {
644 AvailableSpace::MinContent | AvailableSpace::MaxContent => {
645 let axis_minimum_size = item_sizer.minimum_contribution(item, axis_tracks);
646 let axis_min_content_size = item_sizer.min_content_contribution(item);
647 let limit = item.spanned_track_limit(axis, axis_tracks, axis_inner_node_size);
648 axis_min_content_size.maybe_min(limit).max(axis_minimum_size)
649 }
650 AvailableSpace::Definite(_) => item_sizer.minimum_contribution(item, axis_tracks),
651 };
652 let tracks = &mut axis_tracks[item.track_range_excluding_lines(axis)];
653 if space > 0.0 {
654 distribute_item_space_to_base_size(
655 is_flex,
656 use_flex_factor_for_distribution,
657 space,
658 tracks,
659 has_intrinsic_min_track_sizing_function,
660 |_| f32::INFINITY,
661 IntrinsicContributionType::Minimum,
662 );
663 }
664 }
665 flush_planned_base_size_increases(axis_tracks);
666
667 // 2. For content-based minimums:
668 // Next continue to increase the base size of tracks with a min track sizing function of min-content or max-content
669 // by distributing extra space as needed to account for these items' min-content contributions.
670 let has_min_or_max_content_min_track_sizing_function = move |track: &GridTrack| {
671 use MinTrackSizingFunction::{MaxContent, MinContent};
672 matches!(track.min_track_sizing_function, MinContent | MaxContent)
673 };
674 for item in batch.iter_mut() {
675 let space = item_sizer.min_content_contribution(item);
676 let tracks = &mut axis_tracks[item.track_range_excluding_lines(axis)];
677 if space > 0.0 {
678 distribute_item_space_to_base_size(
679 is_flex,
680 use_flex_factor_for_distribution,
681 space,
682 tracks,
683 has_min_or_max_content_min_track_sizing_function,
684 |_| f32::INFINITY,
685 IntrinsicContributionType::Minimum,
686 );
687 }
688 }
689 flush_planned_base_size_increases(axis_tracks);
690
691 // 3. For max-content minimums:
692
693 // If the grid container is being sized under a max-content constraint, continue to increase the base size of tracks with
694 // a min track sizing function of auto or max-content by distributing extra space as needed to account for these items'
695 // limited max-content contributions.
696
697 // Define fit_content_limited_growth_limit function. This is passed to the distribute_space_up_to_limits
698 // helper function, and is used to compute the limit to distribute up to for each track.
699 // Wrapping the method on GridTrack is necessary in order to resolve percentage fit-content arguments.
700 if axis_available_grid_space == AvailableSpace::MaxContent {
701 /// Whether a track:
702 /// - has an Auto MIN track sizing function
703 /// - Does not have a MinContent MAX track sizing function
704 ///
705 /// The latter condition was added in order to match Chrome. But I believe it is due to the provision
706 /// under minmax here https://www.w3.org/TR/css-grid-1/#track-sizes which states that:
707 ///
708 /// "If the max is less than the min, then the max will be floored by the min (essentially yielding minmax(min, min))"
709 #[inline(always)]
710 fn has_auto_min_track_sizing_function(track: &GridTrack) -> bool {
711 track.min_track_sizing_function == MinTrackSizingFunction::Auto
712 && track.max_track_sizing_function != MaxTrackSizingFunction::MinContent
713 }
714
715 /// Whether a track has a MaxContent min track sizing function
716 #[inline(always)]
717 fn has_max_content_min_track_sizing_function(track: &GridTrack) -> bool {
718 track.min_track_sizing_function == MinTrackSizingFunction::MaxContent
719 }
720
721 for item in batch.iter_mut() {
722 let axis_max_content_size = item_sizer.max_content_contribution(item);
723 let limit = item.spanned_track_limit(axis, axis_tracks, axis_inner_node_size);
724 let space = axis_max_content_size.maybe_min(limit);
725 let tracks = &mut axis_tracks[item.track_range_excluding_lines(axis)];
726 if space > 0.0 {
727 // If any of the tracks spanned by the item have a MaxContent min track sizing function then
728 // distribute space only to those tracks. Otherwise distribute space to tracks with an Auto min
729 // track sizing function.
730 //
731 // Note: this prioritisation of MaxContent over Auto is not mentioned in the spec (which suggests that
732 // we ought to distribute space evenly between MaxContent and Auto tracks). But it is implemented like
733 // this in both Chrome and Firefox (and it does have a certain logic to it), so we implement it too for
734 // compatibility.
735 //
736 // See: https://www.w3.org/TR/css-grid-1/#track-size-max-content-min
737 if tracks.iter().any(has_max_content_min_track_sizing_function) {
738 distribute_item_space_to_base_size(
739 is_flex,
740 use_flex_factor_for_distribution,
741 space,
742 tracks,
743 has_max_content_min_track_sizing_function,
744 |_| f32::INFINITY,
745 IntrinsicContributionType::Maximum,
746 );
747 } else {
748 let fit_content_limited_growth_limit =
749 move |track: &GridTrack| track.fit_content_limited_growth_limit(axis_inner_node_size);
750 distribute_item_space_to_base_size(
751 is_flex,
752 use_flex_factor_for_distribution,
753 space,
754 tracks,
755 has_auto_min_track_sizing_function,
756 fit_content_limited_growth_limit,
757 IntrinsicContributionType::Maximum,
758 );
759 }
760 }
761 }
762 flush_planned_base_size_increases(axis_tracks);
763 }
764
765 // In all cases, continue to increase the base size of tracks with a min track sizing function of max-content by distributing
766 // extra space as needed to account for these items' max-content contributions.
767 let has_max_content_min_track_sizing_function =
768 move |track: &GridTrack| matches!(track.min_track_sizing_function, MinTrackSizingFunction::MaxContent);
769 for item in batch.iter_mut() {
770 let axis_max_content_size = item_sizer.max_content_contribution(item);
771 let space = axis_max_content_size;
772 let tracks = &mut axis_tracks[item.track_range_excluding_lines(axis)];
773 if space > 0.0 {
774 distribute_item_space_to_base_size(
775 is_flex,
776 use_flex_factor_for_distribution,
777 space,
778 tracks,
779 has_max_content_min_track_sizing_function,
780 |_| f32::INFINITY,
781 IntrinsicContributionType::Maximum,
782 );
783 }
784 }
785 flush_planned_base_size_increases(axis_tracks);
786
787 // 4. If at this point any track’s growth limit is now less than its base size, increase its growth limit to match its base size.
788 for track in axis_tracks.iter_mut() {
789 if track.growth_limit < track.base_size {
790 track.growth_limit = track.base_size;
791 }
792 }
793
794 // If a track is a flexible track, then it has flexible max track sizing function
795 // It cannot also have an intrinsic max track sizing function, so these steps do not apply.
796 if !is_flex {
797 // 5. For intrinsic maximums: Next increase the growth limit of tracks with an intrinsic max track sizing function by
798 // distributing extra space as needed to account for these items' min-content contributions.
799 let has_intrinsic_max_track_sizing_function =
800 move |track: &GridTrack| track.max_track_sizing_function.definite_value(axis_inner_node_size).is_none();
801 for item in batch.iter_mut() {
802 let axis_min_content_size = item_sizer.min_content_contribution(item);
803 let space = axis_min_content_size;
804 let tracks = &mut axis_tracks[item.track_range_excluding_lines(axis)];
805 if space > 0.0 {
806 distribute_item_space_to_growth_limit(
807 space,
808 tracks,
809 has_intrinsic_max_track_sizing_function,
810 inner_node_size.get(axis),
811 );
812 }
813 }
814 // Mark any tracks whose growth limit changed from infinite to finite in this step as infinitely growable for the next step.
815 flush_planned_growth_limit_increases(axis_tracks, true);
816
817 // 6. For max-content maximums: Lastly continue to increase the growth limit of tracks with a max track sizing function of max-content
818 // by distributing extra space as needed to account for these items' max-content contributions. However, limit the growth of any
819 // fit-content() tracks by their fit-content() argument.
820 let has_max_content_max_track_sizing_function = |track: &GridTrack| {
821 track.max_track_sizing_function.is_max_content_alike()
822 || (track.max_track_sizing_function.uses_percentage() && axis_inner_node_size.is_none())
823 };
824 for item in batch.iter_mut() {
825 let axis_max_content_size = item_sizer.max_content_contribution(item);
826 let space = axis_max_content_size;
827 let tracks = &mut axis_tracks[item.track_range_excluding_lines(axis)];
828 if space > 0.0 {
829 distribute_item_space_to_growth_limit(
830 space,
831 tracks,
832 has_max_content_max_track_sizing_function,
833 inner_node_size.get(axis),
834 );
835 }
836 }
837 // Mark any tracks whose growth limit changed from infinite to finite in this step as infinitely growable for the next step.
838 flush_planned_growth_limit_increases(axis_tracks, false);
839 }
840 }
841
842 // Step 5. If any track still has an infinite growth limit (because, for example, it had no items placed
843 // in it or it is a flexible track), set its growth limit to its base size.
844 // NOTE: this step is super-important to ensure that the "Maximise Tracks" step doesn't affect flexible tracks
845 axis_tracks
846 .iter_mut()
847 .filter(|track| track.growth_limit == f32::INFINITY)
848 .for_each(|track| track.growth_limit = track.base_size);
849}
850
851/// 11.5.1. Distributing Extra Space Across Spanned Tracks
852/// https://www.w3.org/TR/css-grid-1/#extra-space
853#[inline(always)]
854fn distribute_item_space_to_base_size(
855 is_flex: bool,
856 use_flex_factor_for_distribution: bool,
857 space: f32,
858 tracks: &mut [GridTrack],
859 track_is_affected: impl Fn(&GridTrack) -> bool,
860 track_limit: impl Fn(&GridTrack) -> f32,
861 intrinsic_contribution_type: IntrinsicContributionType,
862) {
863 if is_flex {
864 let filter = |track: &GridTrack| track.is_flexible() && track_is_affected(track);
865 if use_flex_factor_for_distribution {
866 distribute_item_space_to_base_size_inner(
867 space,
868 tracks,
869 filter,
870 |track| track.flex_factor(),
871 track_limit,
872 intrinsic_contribution_type,
873 )
874 } else {
875 distribute_item_space_to_base_size_inner(
876 space,
877 tracks,
878 filter,
879 |_| 1.0,
880 track_limit,
881 intrinsic_contribution_type,
882 )
883 }
884 } else {
885 distribute_item_space_to_base_size_inner(
886 space,
887 tracks,
888 track_is_affected,
889 |_| 1.0,
890 track_limit,
891 intrinsic_contribution_type,
892 )
893 }
894
895 /// Inner function that doesn't account for differences due to distributing to flex items
896 /// This difference is handled by the closure passed in above
897 fn distribute_item_space_to_base_size_inner(
898 space: f32,
899 tracks: &mut [GridTrack],
900 track_is_affected: impl Fn(&GridTrack) -> bool,
901 track_distribution_proportion: impl Fn(&GridTrack) -> f32,
902 track_limit: impl Fn(&GridTrack) -> f32,
903 intrinsic_contribution_type: IntrinsicContributionType,
904 ) {
905 // Skip this distribution if there is either
906 // - no space to distribute
907 // - no affected tracks to distribute space to
908 if space == 0.0 || !tracks.iter().any(&track_is_affected) {
909 return;
910 }
911
912 // Define get_base_size function. This is passed to the distribute_space_up_to_limits helper function
913 // to indicate that it is the base size that is being distributed to.
914 let get_base_size = |track: &GridTrack| track.base_size;
915
916 // 1. Find the space to distribute
917 let track_sizes: f32 = tracks.iter().map(|track| track.base_size).sum();
918 let extra_space: f32 = f32_max(0.0, space - track_sizes);
919
920 // 2. Distribute space up to limits:
921 // Note: there are two exit conditions to this loop:
922 // - We run out of space to distribute (extra_space falls below THRESHOLD)
923 // - We run out of growable tracks to distribute to
924
925 /// Define a small constant to avoid infinite loops due to rounding errors. Rather than stopping distributing
926 /// extra space when it gets to exactly zero, we will stop when it falls below this amount
927 const THRESHOLD: f32 = 0.000001;
928
929 let extra_space = distribute_space_up_to_limits(
930 extra_space,
931 tracks,
932 &track_is_affected,
933 &track_distribution_proportion,
934 get_base_size,
935 &track_limit,
936 );
937
938 // 3. Distribute remaining span beyond limits (if any)
939 if extra_space > THRESHOLD {
940 // When accommodating minimum contributions or accommodating min-content contributions:
941 // - any affected track that happens to also have an intrinsic max track sizing function;
942 // When accommodating max-content contributions:
943 // - any affected track that happens to also have a max-content max track sizing function
944 let mut filter = match intrinsic_contribution_type {
945 IntrinsicContributionType::Minimum => {
946 (|track: &GridTrack| track.max_track_sizing_function.is_intrinsic()) as fn(&GridTrack) -> bool
947 }
948 IntrinsicContributionType::Maximum => {
949 use MaxTrackSizingFunction::{FitContent, MaxContent};
950 (|track: &GridTrack| {
951 matches!(track.max_track_sizing_function, MaxContent | FitContent(_))
952 || track.min_track_sizing_function == MinTrackSizingFunction::MaxContent
953 }) as fn(&GridTrack) -> bool
954 }
955 };
956
957 // If there are no such tracks (matching filter above), then use all affected tracks.
958 let number_of_tracks =
959 tracks.iter().filter(|track| track_is_affected(track)).filter(|track| filter(track)).count();
960 if number_of_tracks == 0 {
961 filter = (|_| true) as fn(&GridTrack) -> bool;
962 }
963
964 distribute_space_up_to_limits(
965 extra_space,
966 tracks,
967 filter,
968 &track_distribution_proportion,
969 get_base_size,
970 &track_limit, // Should apply only fit-content limit here?
971 );
972 }
973
974 // 4. For each affected track, if the track’s item-incurred increase is larger than the track’s planned increase
975 // set the track’s planned increase to that value.
976 for track in tracks.iter_mut() {
977 if track.item_incurred_increase > track.base_size_planned_increase {
978 track.base_size_planned_increase = track.item_incurred_increase;
979 }
980
981 // Reset the item_incurresed increase ready for the next space distribution
982 track.item_incurred_increase = 0.0;
983 }
984 }
985}
986
987/// 11.5.1. Distributing Extra Space Across Spanned Tracks
988/// This is simplified (and faster) version of the algorithm for growth limits
989/// https://www.w3.org/TR/css-grid-1/#extra-space
990fn distribute_item_space_to_growth_limit(
991 space: f32,
992 tracks: &mut [GridTrack],
993 track_is_affected: impl Fn(&GridTrack) -> bool,
994 axis_inner_node_size: Option<f32>,
995) {
996 // Skip this distribution if there is either
997 // - no space to distribute
998 // - no affected tracks to distribute space to
999 if space == 0.0 || tracks.iter().filter(|track| track_is_affected(track)).count() == 0 {
1000 return;
1001 }
1002
1003 // 1. Find the space to distribute
1004 let track_sizes: f32 = tracks
1005 .iter()
1006 .map(|track| if track.growth_limit == f32::INFINITY { track.base_size } else { track.growth_limit })
1007 .sum();
1008 let extra_space: f32 = f32_max(0.0, space - track_sizes);
1009
1010 // 2. Distribute space up to limits:
1011 // For growth limits the limit is either Infinity, or the growth limit itself. Which means that:
1012 // - If there are any tracks with infinite limits then all space will be distributed to those track(s).
1013 // - Otherwise no space will be distributed as part of this step
1014 let number_of_growable_tracks = tracks
1015 .iter()
1016 .filter(|track| track_is_affected(track))
1017 .filter(|track| {
1018 track.infinitely_growable || track.fit_content_limited_growth_limit(axis_inner_node_size) == f32::INFINITY
1019 })
1020 .count();
1021 if number_of_growable_tracks > 0 {
1022 let item_incurred_increase = extra_space / number_of_growable_tracks as f32;
1023 for track in tracks.iter_mut().filter(|track| track_is_affected(track)).filter(|track| {
1024 track.infinitely_growable || track.fit_content_limited_growth_limit(axis_inner_node_size) == f32::INFINITY
1025 }) {
1026 track.item_incurred_increase = item_incurred_increase;
1027 }
1028 } else {
1029 // 3. Distribute space beyond limits
1030 // If space remains after all tracks are frozen, unfreeze and continue to distribute space to the item-incurred increase
1031 // ...when handling any intrinsic growth limit: all affected tracks.
1032 distribute_space_up_to_limits(
1033 extra_space,
1034 tracks,
1035 track_is_affected,
1036 |_| 1.0,
1037 |track| if track.growth_limit == f32::INFINITY { track.base_size } else { track.growth_limit },
1038 move |track| track.fit_content_limit(axis_inner_node_size),
1039 );
1040 };
1041
1042 // 4. For each affected track, if the track’s item-incurred increase is larger than the track’s planned increase
1043 // set the track’s planned increase to that value.
1044 for track in tracks.iter_mut() {
1045 if track.item_incurred_increase > track.growth_limit_planned_increase {
1046 track.growth_limit_planned_increase = track.item_incurred_increase;
1047 }
1048
1049 // Reset the item_incurresed increase ready for the next space distribution
1050 track.item_incurred_increase = 0.0;
1051 }
1052}
1053
1054/// 11.6 Maximise Tracks
1055/// Distributes free space (if any) to tracks with FINITE growth limits, up to their limits.
1056#[inline(always)]
1057fn maximise_tracks(
1058 axis_tracks: &mut [GridTrack],
1059 axis_inner_node_size: Option<f32>,
1060 axis_available_grid_space: AvailableSpace,
1061) {
1062 let used_space: f32 = axis_tracks.iter().map(|track| track.base_size).sum();
1063 let free_space = axis_available_grid_space.compute_free_space(used_space);
1064 if free_space == f32::INFINITY {
1065 axis_tracks.iter_mut().for_each(|track| track.base_size = track.growth_limit);
1066 } else if free_space > 0.0 {
1067 distribute_space_up_to_limits(
1068 free_space,
1069 axis_tracks,
1070 |_| true,
1071 |_| 1.0,
1072 |track| track.base_size,
1073 move |track: &GridTrack| track.fit_content_limited_growth_limit(axis_inner_node_size),
1074 );
1075 for track in axis_tracks.iter_mut() {
1076 track.base_size += track.item_incurred_increase;
1077 track.item_incurred_increase = 0.0;
1078 }
1079 }
1080}
1081
1082/// 11.7. Expand Flexible Tracks
1083/// This step sizes flexible tracks using the largest value it can assign to an fr without exceeding the available space.
1084#[allow(clippy::too_many_arguments)]
1085#[inline(always)]
1086fn expand_flexible_tracks(
1087 tree: &mut impl LayoutTree,
1088 axis: AbstractAxis,
1089 axis_tracks: &mut [GridTrack],
1090 items: &mut [GridItem],
1091 axis_min_size: Option<f32>,
1092 axis_max_size: Option<f32>,
1093 available_grid_space: Size<AvailableSpace>,
1094 inner_node_size: Size<Option<f32>>,
1095) {
1096 // First, find the grid’s used flex fraction:
1097 let flex_fraction = match available_grid_space.get(axis) {
1098 // If the free space is zero:
1099 // The used flex fraction is zero.
1100 // Otherwise, if the free space is a definite length:
1101 // The used flex fraction is the result of finding the size of an fr using all of the grid tracks and
1102 // a space to fill of the available grid space.
1103 AvailableSpace::Definite(available_space) => {
1104 let used_space: f32 = axis_tracks.iter().map(|track| track.base_size).sum();
1105 let free_space = available_space - used_space;
1106 if free_space <= 0.0 {
1107 0.0
1108 } else {
1109 find_size_of_fr(axis_tracks, available_space)
1110 }
1111 }
1112 // If ... sizing the grid container under a min-content constraint the used flex fraction is zero.
1113 AvailableSpace::MinContent => 0.0,
1114 // Otherwise, if the free space is an indefinite length:
1115 AvailableSpace::MaxContent => {
1116 // The used flex fraction is the maximum of:
1117 let flex_fraction = f32_max(
1118 // For each flexible track, if the flexible track’s flex factor is greater than one,
1119 // the result of dividing the track’s base size by its flex factor; otherwise, the track’s base size.
1120 axis_tracks
1121 .iter()
1122 .filter(|track| track.max_track_sizing_function.is_flexible())
1123 .map(|track| {
1124 let flex_factor = track.flex_factor();
1125 if flex_factor > 1.0 {
1126 track.base_size / flex_factor
1127 } else {
1128 track.base_size
1129 }
1130 })
1131 .max_by(|a, b| a.total_cmp(b))
1132 .unwrap_or(0.0),
1133 // For each grid item that crosses a flexible track, the result of finding the size of an fr using all the grid tracks
1134 // that the item crosses and a space to fill of the item’s max-content contribution.
1135 items
1136 .iter_mut()
1137 .filter(|item| item.crosses_flexible_track(axis))
1138 .map(|item| {
1139 let tracks = &axis_tracks[item.track_range_excluding_lines(axis)];
1140 // TODO: plumb estimate of other axis size (known_dimensions) in here rather than just passing Size::NONE?
1141 let max_content_contribution =
1142 item.max_content_contribution_cached(axis, tree, Size::NONE, inner_node_size);
1143 find_size_of_fr(tracks, max_content_contribution)
1144 })
1145 .max_by(|a, b| a.total_cmp(b))
1146 .unwrap_or(0.0),
1147 );
1148
1149 // If using this flex fraction would cause the grid to be smaller than the grid container’s min-width/height (or larger than the
1150 // grid container’s max-width/height), then redo this step, treating the free space as definite and the available grid space as equal
1151 // to the grid container’s inner size when it’s sized to its min-width/height (max-width/height).
1152 // (Note: min_size takes precedence over max_size)
1153 let hypothetical_grid_size: f32 = axis_tracks
1154 .iter()
1155 .map(|track| match track.max_track_sizing_function {
1156 MaxTrackSizingFunction::Flex(track_flex_factor) => {
1157 f32_max(track.base_size, track_flex_factor * flex_fraction)
1158 }
1159 _ => track.base_size,
1160 })
1161 .sum();
1162 let axis_min_size = axis_min_size.unwrap_or(0.0);
1163 let axis_max_size = axis_max_size.unwrap_or(f32::INFINITY);
1164 if hypothetical_grid_size < axis_min_size {
1165 find_size_of_fr(axis_tracks, axis_min_size)
1166 } else if hypothetical_grid_size > axis_max_size {
1167 find_size_of_fr(axis_tracks, axis_max_size)
1168 } else {
1169 flex_fraction
1170 }
1171 }
1172 };
1173
1174 // For each flexible track, if the product of the used flex fraction and the track’s flex factor is greater
1175 // than the track’s base size, set its base size to that product.
1176 for track in axis_tracks.iter_mut() {
1177 if let MaxTrackSizingFunction::Flex(track_flex_factor) = track.max_track_sizing_function {
1178 track.base_size = f32_max(track.base_size, track_flex_factor * flex_fraction);
1179 }
1180 }
1181}
1182
1183/// 11.7.1. Find the Size of an fr
1184/// This algorithm finds the largest size that an fr unit can be without exceeding the target size.
1185/// It must be called with a set of grid tracks and some quantity of space to fill.
1186#[inline(always)]
1187fn find_size_of_fr(tracks: &[GridTrack], space_to_fill: f32) -> f32 {
1188 // Handle the trivial case where there is no space to fill
1189 // Do not remove as otherwise the loop below will loop infinitely
1190 if space_to_fill == 0.0 {
1191 return 0.0;
1192 }
1193
1194 // If the product of the hypothetical fr size (computed below) and any flexible track’s flex factor
1195 // is less than the track’s base size, then we must restart this algorithm treating all such tracks as inflexible.
1196 // We therefore wrap the entire algorithm in a loop, with an hypotherical_fr_size of INFINITY such that the above
1197 // condition can never be true for the first iteration.
1198 let mut hypothetical_fr_size = f32::INFINITY;
1199 let mut previous_iter_hypothetical_fr_size;
1200 loop {
1201 // Let leftover space be the space to fill minus the base sizes of the non-flexible grid tracks.
1202 // Let flex factor sum be the sum of the flex factors of the flexible tracks. If this value is less than 1, set it to 1 instead.
1203 // We compute both of these in a single loop to avoid iterating over the data twice
1204 let mut used_space = 0.0;
1205 let mut naive_flex_factor_sum = 0.0;
1206 for track in tracks.iter() {
1207 match track.max_track_sizing_function {
1208 // Tracks for which flex_factor * hypothetical_fr_size < track.base_size are treated as inflexible
1209 MaxTrackSizingFunction::Flex(flex_factor) if flex_factor * hypothetical_fr_size >= track.base_size => {
1210 naive_flex_factor_sum += flex_factor;
1211 }
1212 _ => used_space += track.base_size,
1213 };
1214 }
1215 let leftover_space = space_to_fill - used_space;
1216 let flex_factor = f32_max(naive_flex_factor_sum, 1.0);
1217
1218 // Let the hypothetical fr size be the leftover space divided by the flex factor sum.
1219 previous_iter_hypothetical_fr_size = hypothetical_fr_size;
1220 hypothetical_fr_size = leftover_space / flex_factor;
1221
1222 // If the product of the hypothetical fr size and a flexible track’s flex factor is less than the track’s base size,
1223 // restart this algorithm treating all such tracks as inflexible.
1224 // We keep track of the hypothetical_fr_size
1225 let hypotherical_fr_size_is_valid = tracks.iter().all(|track| match track.max_track_sizing_function {
1226 MaxTrackSizingFunction::Flex(flex_factor) => {
1227 flex_factor * hypothetical_fr_size >= track.base_size
1228 || flex_factor * previous_iter_hypothetical_fr_size < track.base_size
1229 }
1230 _ => true,
1231 });
1232 if hypotherical_fr_size_is_valid {
1233 break;
1234 }
1235 }
1236
1237 // Return the hypothetical fr size.
1238 hypothetical_fr_size
1239}
1240
1241/// 11.8. Stretch auto Tracks
1242/// This step expands tracks that have an auto max track sizing function by dividing any remaining positive, definite free space equally amongst them.
1243#[inline(always)]
1244fn stretch_auto_tracks(
1245 axis: AbstractAxis,
1246 axis_tracks: &mut [GridTrack],
1247 axis_min_size: Option<f32>,
1248 available_grid_space: Size<AvailableSpace>,
1249) {
1250 let num_auto_tracks =
1251 axis_tracks.iter().filter(|track| track.max_track_sizing_function == MaxTrackSizingFunction::Auto).count();
1252 if num_auto_tracks > 0 {
1253 let used_space: f32 = axis_tracks.iter().map(|track| track.base_size).sum();
1254
1255 // If the free space is indefinite, but the grid container has a definite min-width/height
1256 // use that size to calculate the free space for this step instead.
1257 let free_space = if available_grid_space.get(axis).is_definite() {
1258 available_grid_space.get(axis).compute_free_space(used_space)
1259 } else {
1260 match axis_min_size {
1261 Some(size) => size - used_space,
1262 None => 0.0,
1263 }
1264 };
1265 if free_space > 0.0 {
1266 let extra_space_per_auto_track = free_space / num_auto_tracks as f32;
1267 axis_tracks
1268 .iter_mut()
1269 .filter(|track| track.max_track_sizing_function == MaxTrackSizingFunction::Auto)
1270 .for_each(|track| track.base_size += extra_space_per_auto_track);
1271 }
1272 }
1273}
1274
1275/// Helper function for distributing space to tracks evenly
1276/// Used by both distribute_item_space_to_base_size and maximise_tracks steps
1277#[inline(always)]
1278fn distribute_space_up_to_limits(
1279 space_to_distribute: f32,
1280 tracks: &mut [GridTrack],
1281 track_is_affected: impl Fn(&GridTrack) -> bool,
1282 track_distribution_proportion: impl Fn(&GridTrack) -> f32,
1283 track_affected_property: impl Fn(&GridTrack) -> f32,
1284 track_limit: impl Fn(&GridTrack) -> f32,
1285) -> f32 {
1286 /// Define a small constant to avoid infinite loops due to rounding errors. Rather than stopping distributing
1287 /// extra space when it gets to exactly zero, we will stop when it falls below this amount
1288 const THRESHOLD: f32 = 0.000001;
1289
1290 let mut space_to_distribute = space_to_distribute;
1291 while space_to_distribute > THRESHOLD {
1292 let track_distribution_proportion_sum: f32 = tracks
1293 .iter()
1294 .filter(|track| track_affected_property(track) + track.item_incurred_increase < track_limit(track))
1295 .filter(|track| track_is_affected(track))
1296 .map(&track_distribution_proportion)
1297 .sum();
1298
1299 if track_distribution_proportion_sum == 0.0 {
1300 break;
1301 }
1302
1303 // Compute item-incurred increase for this iteration
1304 let min_increase_limit = tracks
1305 .iter()
1306 .filter(|track| track_affected_property(track) + track.item_incurred_increase < track_limit(track))
1307 .filter(|track| track_is_affected(track))
1308 .map(|track| (track_limit(track) - track_affected_property(track)) / track_distribution_proportion(track))
1309 .min_by(|a, b| a.total_cmp(b))
1310 .unwrap(); // We will never pass an empty track list to this function
1311 let iteration_item_incurred_increase =
1312 f32_min(min_increase_limit, space_to_distribute / track_distribution_proportion_sum);
1313
1314 for track in tracks.iter_mut().filter(|track| track_is_affected(track)) {
1315 let increase = iteration_item_incurred_increase * track_distribution_proportion(track);
1316 if increase > 0.0 && track_affected_property(track) + increase <= track_limit(track) {
1317 track.item_incurred_increase += increase;
1318 space_to_distribute -= increase;
1319 }
1320 }
1321 }
1322
1323 space_to_distribute
1324}