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