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