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