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