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