⎇ 0596475afda99229de96976e73b2d637c78fdb8b
src/compute/grid/track_sizing.rs
History
Who touched what
raw
Fix grid track sizing for `fit-content(percentage)` and for items spanning percentage gaps (#335)
1//! Implements the track sizing algorithm
2//! https://www.w3.org/TR/css-grid-1/#layout-algorithm
3use super::types::{GridItem, GridTrack, TrackCounts};
4use crate::axis::AbstractAxis;
5use crate::geometry::{Rect, Size};
6use crate::math::MaybeMath;
7use crate::prelude::LayoutTree;
8use crate::resolve::{MaybeResolve, ResolveOrZero};
9use crate::style::{AlignContent, AvailableSpace, MaxTrackSizingFunction, MinTrackSizingFunction, Style};
10use crate::sys::{f32_max, f32_min};
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 fn new(axis: AbstractAxis) -> Self {
30 ItemBatcher { index_offset: 0, axis, current_span: 1, current_is_flex: false }
31 }
32
33 /// This is basically a manual version of Iterator::next which passes `items`
34 /// in as a parameter on each iteration to work around borrow checker rules
35 fn next<'items>(&mut self, items: &'items mut [GridItem]) -> Option<(&'items mut [GridItem], bool)> {
36 if self.current_is_flex || self.index_offset >= items.len() {
37 return None;
38 }
39
40 let item = &items[self.index_offset];
41 self.current_span = item.span(self.axis);
42 self.current_is_flex = item.crosses_flexible_track(self.axis);
43
44 let next_index_offset = if self.current_is_flex {
45 items.len()
46 } else {
47 items
48 .iter()
49 .position(|item: &GridItem| {
50 item.crosses_flexible_track(self.axis) || item.span(self.axis) > self.current_span
51 })
52 .unwrap_or(items.len())
53 };
54
55 let batch_range = self.index_offset..next_index_offset;
56 self.index_offset = next_index_offset;
57
58 let batch = &mut items[batch_range];
59 Some((batch, self.current_is_flex))
60 }
61}
62
63/// To make track sizing efficient we want to order tracks
64/// Here a placement is either a Line<i16> representing a row-start/row-end or a column-start/column-end
65#[inline(always)]
66pub(super) fn cmp_by_cross_flex_then_span_then_start(
67 axis: AbstractAxis,
68) -> impl FnMut(&GridItem, &GridItem) -> Ordering {
69 move |item_a: &GridItem, item_b: &GridItem| -> Ordering {
70 match (item_a.crosses_flexible_track(axis), item_b.crosses_flexible_track(axis)) {
71 (false, true) => Ordering::Less,
72 (true, false) => Ordering::Greater,
73 _ => {
74 let placement_a = item_a.placement(axis);
75 let placement_b = item_b.placement(axis);
76 let a_span = placement_a.end - placement_a.start;
77 let b_span = placement_b.end - placement_b.start;
78 match a_span.cmp(&b_span) {
79 Ordering::Less => Ordering::Less,
80 Ordering::Greater => Ordering::Greater,
81 Ordering::Equal => placement_a.start.cmp(&placement_b.start),
82 }
83 }
84 }
85 }
86}
87
88/// When applying the track sizing algorithm and estimating the size in the other axis for content sizing items
89/// we should take into account align-content/justify-content if both the grid container and all items in the
90/// other axis have definite sizes. This function computes such a per-gutter additional size adjustment.
91pub(super) fn compute_alignment_gutter_adjustment(
92 alignment: AlignContent,
93 available_space: AvailableSpace,
94 get_track_size_estimate: impl Fn(&GridTrack, AvailableSpace) -> Option<f32>,
95 tracks: &[GridTrack],
96) -> f32 {
97 // As items never cross the outermost gutters in a grid, we can simplify our calculations by treating
98 // AlignContent::Start and AlignContent::End the same
99 let outer_gutter_weight = match alignment {
100 AlignContent::Start => 1,
101 AlignContent::FlexStart => 1,
102 AlignContent::End => 1,
103 AlignContent::FlexEnd => 1,
104 AlignContent::Center => 1,
105 AlignContent::Stretch => 0,
106 AlignContent::SpaceBetween => 0,
107 AlignContent::SpaceAround => 1,
108 AlignContent::SpaceEvenly => 1,
109 };
110
111 let inner_gutter_weight = match alignment {
112 AlignContent::FlexStart => 0,
113 AlignContent::Start => 0,
114 AlignContent::FlexEnd => 0,
115 AlignContent::End => 0,
116 AlignContent::Center => 0,
117 AlignContent::Stretch => 0,
118 AlignContent::SpaceBetween => 1,
119 AlignContent::SpaceAround => 2,
120 AlignContent::SpaceEvenly => 1,
121 };
122
123 if inner_gutter_weight > 0 && available_space.is_definite() && tracks.len() > 1 {
124 let inner_available_space = tracks
125 .iter()
126 .map(|track| get_track_size_estimate(track, available_space))
127 .sum::<Option<f32>>()
128 .map(|track_size_sum| f32_max(0.0, available_space.unwrap() - track_size_sum))
129 .unwrap_or(0.0);
130
131 let weighted_track_count =
132 (((tracks.len() - 3) / 2) * inner_gutter_weight as usize) + (2 * outer_gutter_weight as usize);
133
134 (inner_available_space / weighted_track_count as f32) * inner_gutter_weight as f32
135 } else {
136 0.0
137 }
138}
139
140/// Convert origin-zero coordinates track placement in grid track vector indexes
141pub(super) fn resolve_item_track_indexes(items: &mut [GridItem], column_counts: TrackCounts, row_counts: TrackCounts) {
142 for item in items {
143 item.column_indexes = item.column.map(|line| line.into_track_vec_index(column_counts) as u16);
144 item.row_indexes = item.row.map(|line| line.into_track_vec_index(row_counts) as u16);
145 }
146}
147
148/// Determine (in each axis) whether the item crosses any flexible tracks
149pub(super) fn determine_if_item_crosses_flexible_tracks(
150 items: &mut Vec<GridItem>,
151 columns: &[GridTrack],
152 rows: &[GridTrack],
153) {
154 for item in items {
155 item.crosses_flexible_column =
156 item.track_range_excluding_lines(AbstractAxis::Inline).any(|i| columns[i].is_flexible());
157 item.crosses_flexible_row =
158 item.track_range_excluding_lines(AbstractAxis::Block).any(|i| rows[i].is_flexible());
159 }
160}
161
162/// Track sizing algorithm
163/// Note: Gutters are treated as empty fixed-size tracks for the purpose of the track sizing algorithm.
164#[allow(clippy::too_many_arguments)]
165pub(super) fn track_sizing_algorithm<Tree: LayoutTree>(
166 tree: &mut Tree,
167 axis: AbstractAxis,
168 available_space: Size<AvailableSpace>,
169 available_grid_space: Size<AvailableSpace>,
170 inner_node_size: Size<Option<f32>>,
171 container_style: &Style,
172 axis_tracks: &mut [GridTrack],
173 other_axis_tracks: &mut [GridTrack],
174 items: &mut [GridItem],
175 get_track_size_estimate: impl Fn(&GridTrack, AvailableSpace) -> Option<f32>,
176) {
177 // 11.4 Initialise Track sizes
178 // Initialize each track’s base size and growth limit.
179 initialize_track_sizes(axis_tracks, inner_node_size.get(axis));
180
181 // If all tracks have base_size = growth_limit, then skip the rest of this function.
182 // Note: this can only happen both track sizing function have the same fixed track sizing function
183 if axis_tracks.iter().all(|track| track.base_size == track.growth_limit) {
184 return;
185 }
186
187 // Clear caches
188 // These caches are only valid for a single run of the track sizing algorithm, so ensure that they are clear.
189 items.iter_mut().for_each(|item| item.clear_contribution_caches());
190
191 // Pre-computations for 11.5 Resolve Intrinsic Track Sizes
192
193 // The track sizing algorithm requires us to iterate through the items in ascendeding order of the number of
194 // tracks they span (first items that span 1 track, then items that span 2 tracks, etc).
195 // To avoid having to do multiple iterations of the items, we pre-sort them into this order.
196 items.sort_by(cmp_by_cross_flex_then_span_then_start(axis));
197
198 // Compute an additional amount to add to each spanned gutter when computing item's estimated size in the
199 // in the opposite axis based on the alignment, container size, and estimated track sizes in that axis
200 let gutter_alignment_adjustment = compute_alignment_gutter_adjustment(
201 container_style.grid_align_content(axis.other()),
202 available_space.get(axis.other()),
203 &get_track_size_estimate,
204 other_axis_tracks,
205 );
206 if other_axis_tracks.len() > 3 {
207 let len = other_axis_tracks.len();
208 let inner_gutter_tracks = other_axis_tracks[2..len].iter_mut().step_by(2);
209 for track in inner_gutter_tracks {
210 track.content_alignment_adjustment = gutter_alignment_adjustment;
211 }
212 }
213
214 // 11.5 Resolve Intrinsic Track Sizes
215 resolve_intrinsic_track_sizes(
216 tree,
217 axis,
218 axis_tracks,
219 other_axis_tracks,
220 items,
221 available_grid_space,
222 inner_node_size,
223 get_track_size_estimate,
224 );
225
226 // 11.6. Maximise Tracks
227 // Distributes free space (if any) to tracks with FINITE growth limits, up to their limits.
228 maximise_tracks(axis, axis_tracks, available_grid_space);
229
230 // 11.7. Expand Flexible Tracks
231 // This step sizes flexible tracks using the largest value it can assign to an fr without exceeding the available space.
232 let axis_min_size = container_style.min_size.get(axis).into_option();
233 let axis_max_size = container_style.max_size.get(axis).into_option();
234 expand_flexible_tracks(
235 tree,
236 axis,
237 axis_tracks,
238 items,
239 axis_min_size,
240 axis_max_size,
241 available_grid_space,
242 inner_node_size,
243 );
244
245 // 11.8. Stretch auto Tracks
246 // This step expands tracks that have an auto max track sizing function by dividing any remaining positive, definite free space equally amongst them.
247 stretch_auto_tracks(axis, axis_tracks, container_style, available_space, available_grid_space);
248}
249
250/// Whether it is a minimum or maximum size's space being distributed
251/// This controls behaviour of the space distribution algorithm when distributing beyond limits
252/// See "distributing space beyond limits" at https://www.w3.org/TR/css-grid-1/#extra-space
253#[derive(Copy, Clone, Debug, PartialEq, Eq)]
254enum IntrinsicContributionType {
255 /// It's a minimum size's space being distributed
256 Minimum,
257 /// It's a maximum size's space being distributed
258 Maximum,
259}
260
261/// Add any planned base size increases to the base size after a round of distributing space to base sizes
262/// Reset the planed base size increase to zero ready for the next round.
263fn flush_planned_base_size_increases(tracks: &mut [GridTrack]) {
264 for track in tracks {
265 track.base_size += track.base_size_planned_increase;
266 track.base_size_planned_increase = 0.0;
267 }
268}
269
270/// Add any planned growth limit increases to the growth limit after a round of distributing space to growth limits
271/// Reset the planed growth limit increase to zero ready for the next round.
272fn flush_planned_growth_limit_increases(tracks: &mut [GridTrack], set_infinitely_growable: bool) {
273 for track in tracks {
274 if track.growth_limit_planned_increase > 0.0 {
275 track.growth_limit = if track.growth_limit == f32::INFINITY {
276 track.base_size + track.growth_limit_planned_increase
277 } else {
278 track.growth_limit + track.growth_limit_planned_increase
279 };
280 track.infinitely_growable = set_infinitely_growable;
281 } else {
282 track.infinitely_growable = false;
283 }
284 track.growth_limit_planned_increase = 0.0
285 }
286}
287
288/// 11.4 Initialise Track sizes
289/// Initialize each track’s base size and growth limit.
290fn initialize_track_sizes(axis_tracks: &mut [GridTrack], axis_inner_node_size: Option<f32>) {
291 let last_track_idx = axis_tracks.len() - 1;
292
293 // First and last grid lines are always zero-sized.
294 axis_tracks[0].base_size = 0.0;
295 axis_tracks[0].growth_limit = 0.0;
296 axis_tracks[last_track_idx].base_size = 0.0;
297 axis_tracks[last_track_idx].growth_limit = 0.0;
298
299 let all_but_first_and_last = 1..last_track_idx;
300 for track in axis_tracks[all_but_first_and_last].iter_mut() {
301 // For each track, if the track’s min track sizing function is:
302 // - A fixed sizing function
303 // Resolve to an absolute length and use that size as the track’s initial base size.
304 // Note: Indefinite lengths cannot occur, as they’re treated as auto.
305 // - An intrinsic sizing function
306 // Use an initial base size of zero.
307 track.base_size = track.min_track_sizing_function.definite_value(axis_inner_node_size.into()).unwrap_or(0.0);
308
309 // For each track, if the track’s max track sizing function is:
310 // - A fixed sizing function
311 // Resolve to an absolute length and use that size as the track’s initial growth limit.
312 // - An intrinsic sizing function
313 // Use an initial growth limit of infinity.
314 // - A flexible sizing function
315 // Use an initial growth limit of infinity.
316 track.growth_limit =
317 track.max_track_sizing_function.definite_value(axis_inner_node_size.into()).unwrap_or(f32::INFINITY);
318
319 // In all cases, if the growth limit is less than the base size, increase the growth limit to match the base size.
320 if track.growth_limit < track.base_size {
321 track.growth_limit = track.base_size;
322 }
323 }
324}
325
326/// 11.5 Resolve Intrinsic Track Sizes
327#[allow(clippy::too_many_arguments)]
328fn resolve_intrinsic_track_sizes(
329 tree: &mut impl LayoutTree,
330 axis: AbstractAxis,
331 axis_tracks: &mut [GridTrack],
332 other_axis_tracks: &mut [GridTrack],
333 items: &mut [GridItem],
334 available_grid_space: Size<AvailableSpace>,
335 inner_node_size: Size<Option<f32>>,
336 get_track_size_estimate: impl Fn(&GridTrack, AvailableSpace) -> Option<f32>,
337) {
338 // Step 1. Shim baseline-aligned items so their intrinsic size contributions reflect their baseline alignment.
339 // TODO: we do not yet support baseline alignment for CSS Grid
340
341 // Step 2. We skip Step 2 as it is noted that:
342 //
343 // This step is a simplification of the steps below for handling spanning items, and should yield
344 // the same behavior as running those instructions on items with a span of 1.
345 //
346 // We choose this alternative of running Step 3 on items with a span of 1 as we need to write the code for this anyway.
347
348 // Step 3 and Step 4
349 // 3. Iterate over items that don't cross a flex track. Items should have already been sorted in ascending order
350 // of the number of tracks they cross.
351 // 4. Next, repeat the previous step instead considering (together, rather than grouped by span size) all items
352 // that do span a track with a flexible sizing function while
353
354 // Compute item's intrinsic (content-based) sizes
355 // Note: For items with a specified minimum size of auto (the initial value), the minimum contribution is usually equivalent
356 // to the min-content contribution—but can differ in some cases, see §6.6 Automatic Minimum Size of Grid Items.
357 // Also, minimum contribution <= min-content contribution <= max-content contribution.
358 // TODO: be smarter about only computing these when they are required
359 let mut compute_item_sizes = |item: &mut GridItem, axis_tracks: &[GridTrack]| {
360 let known_dimensions = item.known_dimensions_cached(
361 axis,
362 other_axis_tracks,
363 available_grid_space.get(axis.other()),
364 &get_track_size_estimate,
365 );
366
367 let margin = Rect {
368 left: item.margin.left.resolve_or_zero(Some(0.0)),
369 right: item.margin.right.resolve_or_zero(Some(0.0)),
370 top: item.margin.top.resolve_or_zero(available_grid_space.width.into_option()),
371 bottom: item.margin.bottom.resolve_or_zero(available_grid_space.width.into_option()),
372 }
373 .sum_axes();
374
375 let min_content_size = item.min_content_contribution_cached(tree, known_dimensions, inner_node_size) + margin;
376 let max_content_size = item.max_content_contribution_cached(tree, known_dimensions, inner_node_size) + margin;
377 let axis_minimum_size = item.minimum_contribution_cached(
378 tree,
379 axis,
380 axis_tracks,
381 available_grid_space,
382 known_dimensions,
383 inner_node_size,
384 ) + margin.get(axis);
385
386 (axis_minimum_size, min_content_size.get(axis), max_content_size.get(axis))
387 };
388
389 let axis_available_grid_space = available_grid_space.get(axis);
390
391 let mut batched_item_iterator = ItemBatcher::new(axis);
392 while let Some((batch, is_flex)) = batched_item_iterator.next(items) {
393 // 1. For intrinsic minimums:
394 // First increase the base size of tracks with an intrinsic min track sizing function
395 let has_intrinsic_min_track_sizing_function = move |track: &GridTrack| {
396 track.min_track_sizing_function.definite_value(available_grid_space.get(axis)).is_none()
397 };
398 for item in batch.iter_mut() {
399 let (axis_minimum_size, axis_min_content_size, _) = compute_item_sizes(item, axis_tracks);
400
401 // ...by distributing extra space as needed to accommodate these items’ minimum contributions.
402 // If the grid container is being sized under a min- or max-content constraint, use the items’ limited min-content contributions
403 // in place of their minimum contributions here.
404 let space = match axis_available_grid_space {
405 AvailableSpace::MinContent | AvailableSpace::MaxContent => {
406 let limit = item.spanned_fixed_track_limit(axis, axis_tracks, inner_node_size.get(axis).into());
407 axis_min_content_size.maybe_min(limit).max(axis_minimum_size)
408 }
409 AvailableSpace::Definite(_) => axis_minimum_size,
410 };
411 let tracks = &mut axis_tracks[item.track_range_excluding_lines(axis)];
412 if space > 0.0 {
413 distribute_item_space_to_base_size(
414 is_flex,
415 space,
416 tracks,
417 has_intrinsic_min_track_sizing_function,
418 IntrinsicContributionType::Minimum,
419 available_grid_space.get(axis),
420 );
421 }
422 }
423 flush_planned_base_size_increases(axis_tracks);
424
425 // 2. For content-based minimums:
426 // Next continue to increase the base size of tracks with a min track sizing function of min-content or max-content
427 // by distributing extra space as needed to account for these items' min-content contributions.
428 let has_min_or_max_content_min_track_sizing_function = move |track: &GridTrack| {
429 use MinTrackSizingFunction::{MaxContent, MinContent};
430 matches!(track.min_track_sizing_function, MinContent | MaxContent)
431 };
432 for item in batch.iter_mut() {
433 let (_, axis_min_content_size, _) = compute_item_sizes(item, axis_tracks);
434 let tracks = &mut axis_tracks[item.track_range_excluding_lines(axis)];
435 let space = axis_min_content_size;
436 if space > 0.0 {
437 distribute_item_space_to_base_size(
438 is_flex,
439 space,
440 tracks,
441 has_min_or_max_content_min_track_sizing_function,
442 IntrinsicContributionType::Minimum,
443 available_grid_space.get(axis),
444 );
445 }
446 }
447 flush_planned_base_size_increases(axis_tracks);
448
449 // 3. For max-content minimums:
450
451 // If the grid container is being sized under a max-content constraint, continue to increase the base size of tracks with
452 // a min track sizing function of auto or max-content by distributing extra space as needed to account for these items'
453 // limited max-content contributions.
454 if axis_available_grid_space == AvailableSpace::MaxContent {
455 let has_auto_or_max_content_min_track_sizing_function = move |track: &GridTrack| {
456 use MinTrackSizingFunction::{Auto, MaxContent};
457 matches!(track.min_track_sizing_function, Auto | MaxContent)
458 };
459 for item in batch.iter_mut() {
460 let (_, _, axis_max_content_size) = compute_item_sizes(item, axis_tracks);
461 let limit = item.spanned_fixed_track_limit(axis, axis_tracks, inner_node_size.get(axis).into());
462 let space = axis_max_content_size.maybe_min(limit);
463 let tracks = &mut axis_tracks[item.track_range_excluding_lines(axis)];
464 if space > 0.0 {
465 distribute_item_space_to_base_size(
466 is_flex,
467 space,
468 tracks,
469 has_auto_or_max_content_min_track_sizing_function,
470 IntrinsicContributionType::Maximum,
471 available_grid_space.get(axis),
472 );
473 }
474 }
475 flush_planned_base_size_increases(axis_tracks);
476 }
477
478 // In all cases, continue to increase the base size of tracks with a min track sizing function of max-content by distributing
479 // extra space as needed to account for these items' max-content contributions.
480 let has_max_content_min_track_sizing_function =
481 move |track: &GridTrack| matches!(track.min_track_sizing_function, MinTrackSizingFunction::MaxContent);
482 for item in batch.iter_mut() {
483 let (_, _, axis_max_content_size) = compute_item_sizes(item, axis_tracks);
484 let space = axis_max_content_size;
485 let tracks = &mut axis_tracks[item.track_range_excluding_lines(axis)];
486 if space > 0.0 {
487 distribute_item_space_to_base_size(
488 is_flex,
489 space,
490 tracks,
491 has_max_content_min_track_sizing_function,
492 IntrinsicContributionType::Maximum,
493 available_grid_space.get(axis),
494 );
495 }
496 }
497 flush_planned_base_size_increases(axis_tracks);
498
499 // 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.
500 for track in axis_tracks.iter_mut() {
501 if track.growth_limit < track.base_size {
502 track.growth_limit = track.base_size;
503 }
504 }
505
506 // If a track is a flexible track, then it has flexible max track sizing function
507 // It cannot also have an intrinsic max track sizing function, so these steps do not apply.
508 if !is_flex {
509 // 5. For intrinsic maximums: Next increase the growth limit of tracks with an intrinsic max track sizing function by
510 // distributing extra space as needed to account for these items' min-content contributions.
511 let has_intrinsic_max_track_sizing_function = move |track: &GridTrack| {
512 track.max_track_sizing_function.definite_value(available_grid_space.get(axis)).is_none()
513 };
514 for item in batch.iter_mut() {
515 let (_, axis_min_content_size, _) = compute_item_sizes(item, axis_tracks);
516 let space = axis_min_content_size;
517 let tracks = &mut axis_tracks[item.track_range_excluding_lines(axis)];
518 if space > 0.0 {
519 distribute_item_space_to_growth_limit(
520 space,
521 tracks,
522 has_intrinsic_max_track_sizing_function,
523 inner_node_size.get(axis),
524 );
525 }
526 }
527 // Mark any tracks whose growth limit changed from infinite to finite in this step as infinitely growable for the next step.
528 flush_planned_growth_limit_increases(axis_tracks, true);
529
530 // 6. For max-content maximums: Lastly continue to increase the growth limit of tracks with a max track sizing function of max-content
531 // by distributing extra space as needed to account for these items' max-content contributions. However, limit the growth of any
532 // fit-content() tracks by their fit-content() argument.
533 let has_max_content_max_track_sizing_function =
534 |track: &GridTrack| track.max_track_sizing_function.is_max_content_alike();
535 for item in batch.iter_mut() {
536 let (_, _, axis_max_content_size) = compute_item_sizes(item, axis_tracks);
537 let space = axis_max_content_size;
538 let tracks = &mut axis_tracks[item.track_range_excluding_lines(axis)];
539 if space > 0.0 {
540 distribute_item_space_to_growth_limit(
541 space,
542 tracks,
543 has_max_content_max_track_sizing_function,
544 inner_node_size.get(axis),
545 );
546 }
547 }
548 // Mark any tracks whose growth limit changed from infinite to finite in this step as infinitely growable for the next step.
549 flush_planned_growth_limit_increases(axis_tracks, false);
550 }
551 }
552
553 // Step 5. If any track still has an infinite growth limit (because, for example, it had no items placed
554 // in it or it is a flexible track), set its growth limit to its base size.
555 // NOTE: this step is super-important to ensure that the "Maximise Tracks" step doesn't affect flexible tracks
556 axis_tracks
557 .iter_mut()
558 .filter(|track| track.growth_limit == f32::INFINITY)
559 .for_each(|track| track.growth_limit = track.base_size);
560}
561
562/// 11.5.1. Distributing Extra Space Across Spanned Tracks
563/// https://www.w3.org/TR/css-grid-1/#extra-space
564fn distribute_item_space_to_base_size(
565 is_flex: bool,
566 space: f32,
567 tracks: &mut [GridTrack],
568 track_is_affected: impl Fn(&GridTrack) -> bool,
569 intrinsic_contribution_type: IntrinsicContributionType,
570 axis_available_grid_space: AvailableSpace,
571) {
572 if is_flex {
573 let filter = |track: &GridTrack| track.is_flexible() && track_is_affected(track);
574 distribute_item_space_to_base_size_inner(
575 space,
576 tracks,
577 filter,
578 intrinsic_contribution_type,
579 axis_available_grid_space,
580 )
581 } else {
582 distribute_item_space_to_base_size_inner(
583 space,
584 tracks,
585 track_is_affected,
586 intrinsic_contribution_type,
587 axis_available_grid_space,
588 )
589 }
590
591 /// Inner function that doesn't account for differences due to distributing to flex items
592 /// This difference is handled by the closure passed in above
593 fn distribute_item_space_to_base_size_inner(
594 space: f32,
595 tracks: &mut [GridTrack],
596 track_is_affected: impl Fn(&GridTrack) -> bool,
597 intrinsic_contribution_type: IntrinsicContributionType,
598 axis_available_grid_space: AvailableSpace,
599 ) {
600 // Skip this distribution if there is either
601 // - no space to distribute
602 // - no affected tracks to distribute space to
603 if space == 0.0 || tracks.iter().filter(|track| track_is_affected(track)).count() == 0 {
604 return;
605 }
606
607 // Define get_base_size function. This is passed to the distribute_space_up_to_limits helper function
608 // to indicate that it is the base size that is being distributed to.
609 let get_base_size = |track: &GridTrack| track.base_size;
610
611 // Define fit_content_limited_growth_limit function. This is passed to the distribute_space_up_to_limits
612 // helper function, and is used to compute the limit to distribute up to for each track.
613 // Wrapping the method on GridTrack is necessary in order to resolve percentage fit-content arguments.
614 let axis_available_grid_space_opt = axis_available_grid_space.into_option();
615 let fit_content_limited_growth_limit =
616 move |track: &GridTrack| track.fit_content_limited_growth_limit(axis_available_grid_space_opt);
617
618 // 1. Find the space to distribute
619 let track_sizes: f32 = tracks.iter().map(|track| track.base_size).sum();
620 let extra_space: f32 = f32_max(0.0, space - track_sizes);
621
622 // 2. Distribute space up to limits:
623 // Note: there are two exit conditions to this loop:
624 // - We run out of space to distribute (extra_space falls below THRESHOLD)
625 // - We run out of growable tracks to distribute to
626
627 /// Define a small constant to avoid infinite loops due to rounding errors. Rather than stopping distributing
628 /// extra space when it gets to exactly zero, we will stop when it falls below this amount
629 const THRESHOLD: f32 = 0.000001;
630
631 let extra_space = distribute_space_up_to_limits(
632 extra_space,
633 tracks,
634 &track_is_affected,
635 get_base_size,
636 fit_content_limited_growth_limit,
637 );
638
639 // 3. Distribute remaining span beyond limits (if any)
640 if extra_space > THRESHOLD {
641 // When accommodating minimum contributions or accommodating min-content contributions:
642 // - any affected track that happens to also have an intrinsic max track sizing function;
643 // When accommodating max-content contributions:
644 // - any affected track that happens to also have a max-content max track sizing function
645 let mut filter = match intrinsic_contribution_type {
646 IntrinsicContributionType::Minimum => {
647 (|track: &GridTrack| track.max_track_sizing_function.is_intrinsic()) as fn(&GridTrack) -> bool
648 }
649 IntrinsicContributionType::Maximum => {
650 (|track: &GridTrack| track.max_track_sizing_function.is_max_content_alike())
651 as fn(&GridTrack) -> bool
652 }
653 };
654
655 // If there are no such tracks (matching filter above), then use all affected tracks.
656 let number_of_tracks =
657 tracks.iter().filter(|track| track_is_affected(track)).filter(|track| filter(track)).count();
658 if number_of_tracks == 0 {
659 filter = (|_| true) as fn(&GridTrack) -> bool;
660 }
661
662 // When distributing space beyond limits, the fit content limit applies to max-content sizes but not min-content sizes
663 let limit = match intrinsic_contribution_type {
664 IntrinsicContributionType::Minimum => &(|_: &GridTrack| f32::INFINITY) as &dyn Fn(&GridTrack) -> f32,
665 IntrinsicContributionType::Maximum => &fit_content_limited_growth_limit as &dyn Fn(&GridTrack) -> f32,
666 };
667
668 distribute_space_up_to_limits(extra_space, tracks, filter, get_base_size, limit);
669 }
670
671 // 4. For each affected track, if the track’s item-incurred increase is larger than the track’s planned increase
672 // set the track’s planned increase to that value.
673 for track in tracks.iter_mut() {
674 if track.item_incurred_increase > track.base_size_planned_increase {
675 track.base_size_planned_increase = track.item_incurred_increase;
676 }
677
678 // Reset the item_incurresed increase ready for the next space distribution
679 track.item_incurred_increase = 0.0;
680 }
681 }
682}
683
684/// 11.5.1. Distributing Extra Space Across Spanned Tracks
685/// This is simplified (and faster) version of the algorithm for growth limits
686/// https://www.w3.org/TR/css-grid-1/#extra-space
687fn distribute_item_space_to_growth_limit(
688 space: f32,
689 tracks: &mut [GridTrack],
690 track_is_affected: impl Fn(&GridTrack) -> bool,
691 axis_inner_node_size: Option<f32>,
692) {
693 // Skip this distribution if there is either
694 // - no space to distribute
695 // - no affected tracks to distribute space to
696 if space == 0.0 || tracks.iter().filter(|track| track_is_affected(track)).count() == 0 {
697 return;
698 }
699
700 // 1. Find the space to distribute
701 let track_sizes: f32 = tracks
702 .iter()
703 .map(|track| if track.growth_limit == f32::INFINITY { track.base_size } else { track.growth_limit })
704 .sum();
705 let extra_space: f32 = f32_max(0.0, space - track_sizes);
706
707 // 2. Distribute space up to limits:
708 // For growth limits the limit is either Infinity, or the growth limit itself. Which means that:
709 // - If there are any tracks with infinite limits then all space will be distributed to those track(s).
710 // - Otherwise no space will be distributed as part of this step
711 let number_of_growable_tracks = tracks
712 .iter()
713 .filter(|track| track_is_affected(track))
714 .filter(|track| {
715 track.infinitely_growable || track.fit_content_limited_growth_limit(axis_inner_node_size) == f32::INFINITY
716 })
717 .count();
718 if number_of_growable_tracks > 0 {
719 let item_incurred_increase = extra_space / number_of_growable_tracks as f32;
720 for track in tracks.iter_mut().filter(|track| track_is_affected(track)).filter(|track| {
721 track.infinitely_growable || track.fit_content_limited_growth_limit(axis_inner_node_size) == f32::INFINITY
722 }) {
723 track.item_incurred_increase = item_incurred_increase;
724 }
725 } else {
726 // 3. Distribute space beyond limits
727 // If space remains after all tracks are frozen, unfreeze and continue to distribute space to the item-incurred increase
728 // ...when handling any intrinsic growth limit: all affected tracks.
729 distribute_space_up_to_limits(
730 extra_space,
731 tracks,
732 track_is_affected,
733 |track| if track.growth_limit == f32::INFINITY { track.base_size } else { track.growth_limit },
734 move |track| track.fit_content_limit(axis_inner_node_size),
735 );
736 };
737
738 // 4. For each affected track, if the track’s item-incurred increase is larger than the track’s planned increase
739 // set the track’s planned increase to that value.
740 for track in tracks.iter_mut() {
741 if track.item_incurred_increase > track.growth_limit_planned_increase {
742 track.growth_limit_planned_increase = track.item_incurred_increase;
743 }
744
745 // Reset the item_incurresed increase ready for the next space distribution
746 track.item_incurred_increase = 0.0;
747 }
748}
749
750/// 11.6 Maximise Tracks
751/// Distributes free space (if any) to tracks with FINITE growth limits, up to their limits.
752fn maximise_tracks(axis: AbstractAxis, axis_tracks: &mut [GridTrack], available_grid_space: Size<AvailableSpace>) {
753 let used_space: f32 = axis_tracks.iter().map(|track| track.base_size).sum();
754 let free_space = available_grid_space.get(axis).compute_free_space(used_space);
755 if free_space == f32::INFINITY {
756 axis_tracks.iter_mut().for_each(|track| track.base_size = track.growth_limit);
757 } else if free_space > 0.0 {
758 let axis_available_grid_space = available_grid_space.get(axis).into_option();
759 distribute_space_up_to_limits(
760 free_space,
761 axis_tracks,
762 |_| true,
763 |track| track.base_size,
764 move |track: &GridTrack| track.fit_content_limited_growth_limit(axis_available_grid_space),
765 );
766 for track in axis_tracks.iter_mut() {
767 track.base_size += track.item_incurred_increase;
768 track.item_incurred_increase = 0.0;
769 }
770 }
771}
772
773/// 11.7. Expand Flexible Tracks
774/// This step sizes flexible tracks using the largest value it can assign to an fr without exceeding the available space.
775#[allow(clippy::too_many_arguments)]
776fn expand_flexible_tracks(
777 tree: &mut impl LayoutTree,
778 axis: AbstractAxis,
779 axis_tracks: &mut [GridTrack],
780 items: &mut [GridItem],
781 axis_min_size: Option<f32>,
782 axis_max_size: Option<f32>,
783 available_grid_space: Size<AvailableSpace>,
784 inner_node_size: Size<Option<f32>>,
785) {
786 // First, find the grid’s used flex fraction:
787 let flex_fraction = match available_grid_space.get(axis) {
788 // If the free space is zero:
789 // The used flex fraction is zero.
790 // Otherwise, if the free space is a definite length:
791 // The used flex fraction is the result of finding the size of an fr using all of the grid tracks and
792 // a space to fill of the available grid space.
793 AvailableSpace::Definite(available_space) => {
794 let used_space: f32 = axis_tracks.iter().map(|track| track.base_size).sum();
795 let free_space = available_space - used_space;
796 if free_space <= 0.0 {
797 0.0
798 } else {
799 find_size_of_fr(axis_tracks, available_space)
800 }
801 }
802 // If ... sizing the grid container under a min-content constraint the used flex fraction is zero.
803 AvailableSpace::MinContent => 0.0,
804 // Otherwise, if the free space is an indefinite length:
805 AvailableSpace::MaxContent => {
806 // The used flex fraction is the maximum of:
807 let flex_fraction = f32_max(
808 // For each flexible track, if the flexible track’s flex factor is greater than one,
809 // the result of dividing the track’s base size by its flex factor; otherwise, the track’s base size.
810 axis_tracks
811 .iter()
812 .filter(|track| track.max_track_sizing_function.is_flexible())
813 .map(|track| {
814 let flex_factor = track.flex_factor();
815 if flex_factor > 1.0 {
816 track.base_size * flex_factor
817 } else {
818 track.base_size
819 }
820 })
821 .max_by(|a, b| a.total_cmp(b))
822 .unwrap_or(0.0),
823 // For each grid item that crosses a flexible track, the result of finding the size of an fr using all the grid tracks
824 // that the item crosses and a space to fill of the item’s max-content contribution.
825 items
826 .iter_mut()
827 .filter(|item| item.crosses_flexible_track(axis))
828 .map(|item| {
829 let tracks = &axis_tracks[item.track_range_excluding_lines(axis)];
830 // TODO: plumb estimate of other axis size (known_dimensions) in here rather than just passing Size::NONE?
831 let max_content_contribution =
832 item.max_content_contribution_cached(tree, Size::NONE, inner_node_size);
833 find_size_of_fr(tracks, max_content_contribution.get(axis))
834 })
835 .max_by(|a, b| a.total_cmp(b))
836 .unwrap_or(0.0),
837 );
838
839 // If using this flex fraction would cause the grid to be smaller than the grid container’s min-width/height (or larger than the
840 // grid container’s max-width/height), then redo this step, treating the free space as definite and the available grid space as equal
841 // to the grid container’s inner size when it’s sized to its min-width/height (max-width/height).
842 // (Note: min_size takes precedence over max_size)
843 let hypothetical_grid_size: f32 = axis_tracks
844 .iter()
845 .map(|track| match track.max_track_sizing_function {
846 MaxTrackSizingFunction::Flex(track_flex_factor) => {
847 f32_max(track.base_size, track_flex_factor * flex_fraction)
848 }
849 _ => track.base_size,
850 })
851 .sum();
852 let axis_min_size = axis_min_size.unwrap_or(0.0);
853 let axis_max_size = axis_max_size.unwrap_or(f32::INFINITY);
854 if hypothetical_grid_size < axis_min_size {
855 find_size_of_fr(axis_tracks, axis_min_size)
856 } else if hypothetical_grid_size > axis_max_size {
857 find_size_of_fr(axis_tracks, axis_max_size)
858 } else {
859 flex_fraction
860 }
861 }
862 };
863
864 // For each flexible track, if the product of the used flex fraction and the track’s flex factor is greater
865 // than the track’s base size, set its base size to that product.
866 for track in axis_tracks.iter_mut() {
867 if let MaxTrackSizingFunction::Flex(track_flex_factor) = track.max_track_sizing_function {
868 track.base_size = f32_max(track.base_size, track_flex_factor * flex_fraction);
869 }
870 }
871}
872
873/// 11.7.1. Find the Size of an fr
874/// This algorithm finds the largest size that an fr unit can be without exceeding the target size.
875/// It must be called with a set of grid tracks and some quantity of space to fill.
876fn find_size_of_fr(tracks: &[GridTrack], space_to_fill: f32) -> f32 {
877 // Handle the trivial case where there is no space to fill
878 // Do not remove as otherwise the loop below will loop infinitely
879 if space_to_fill == 0.0 {
880 return 0.0;
881 }
882
883 // If the product of the hypothetical fr size (computed below) and any flexible track’s flex factor
884 // is less than the track’s base size, then we must restart this algorithm treating all such tracks as inflexible.
885 // We therefore wrap the entire algorithm in a loop, with an hypotherical_fr_size of INFINITY such that the above
886 // condition can never be true for the first iteration.
887 let mut hypothetical_fr_size = f32::INFINITY;
888 let mut previous_iter_hypothetical_fr_size;
889 loop {
890 // Let leftover space be the space to fill minus the base sizes of the non-flexible grid tracks.
891 // 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.
892 // We compute both of these in a single loop to avoid iterating over the data twice
893 let mut used_space = 0.0;
894 let mut naive_flex_factor_sum = 0.0;
895 for track in tracks.iter() {
896 match track.max_track_sizing_function {
897 // Tracks for which flex_factor * hypothetical_fr_size < track.base_size are treated as inflexible
898 MaxTrackSizingFunction::Flex(flex_factor) if flex_factor * hypothetical_fr_size >= track.base_size => {
899 naive_flex_factor_sum += flex_factor;
900 }
901 _ => used_space += track.base_size,
902 };
903 }
904 let leftover_space = space_to_fill - used_space;
905 let flex_factor = f32_max(naive_flex_factor_sum, 1.0);
906
907 // Let the hypothetical fr size be the leftover space divided by the flex factor sum.
908 previous_iter_hypothetical_fr_size = hypothetical_fr_size;
909 hypothetical_fr_size = leftover_space / flex_factor;
910
911 // If the product of the hypothetical fr size and a flexible track’s flex factor is less than the track’s base size,
912 // restart this algorithm treating all such tracks as inflexible.
913 // We keep track of the hypothetical_fr_size
914 let hypotherical_fr_size_is_valid = tracks.iter().all(|track| match track.max_track_sizing_function {
915 MaxTrackSizingFunction::Flex(flex_factor) => {
916 flex_factor * hypothetical_fr_size >= track.base_size
917 || flex_factor * previous_iter_hypothetical_fr_size < track.base_size
918 }
919 _ => true,
920 });
921 if hypotherical_fr_size_is_valid {
922 break;
923 }
924 }
925
926 // Return the hypothetical fr size.
927 hypothetical_fr_size
928}
929
930/// 11.8. Stretch auto Tracks
931/// This step expands tracks that have an auto max track sizing function by dividing any remaining positive, definite free space equally amongst them.
932fn stretch_auto_tracks(
933 axis: AbstractAxis,
934 axis_tracks: &mut [GridTrack],
935 container_style: &Style,
936 available_space: Size<AvailableSpace>,
937 available_grid_space: Size<AvailableSpace>,
938) {
939 let num_auto_tracks =
940 axis_tracks.iter().filter(|track| track.max_track_sizing_function == MaxTrackSizingFunction::Auto).count();
941 if num_auto_tracks > 0 {
942 let used_space: f32 = axis_tracks.iter().map(|track| track.base_size).sum();
943
944 // If the free space is indefinite, but the grid container has a definite min-width/height
945 // use that size to calculate the free space for this step instead.
946 let free_space = if available_grid_space.get(axis).is_definite() {
947 available_grid_space.get(axis).compute_free_space(used_space)
948 } else {
949 match container_style.min_size.maybe_resolve(available_space.into_options()).get(axis) {
950 Some(size) => size - used_space,
951 None => 0.0,
952 }
953 };
954 if free_space > 0.0 {
955 let extra_space_per_auto_track = free_space / num_auto_tracks as f32;
956 axis_tracks
957 .iter_mut()
958 .filter(|track| track.max_track_sizing_function == MaxTrackSizingFunction::Auto)
959 .for_each(|track| track.base_size += extra_space_per_auto_track);
960 }
961 }
962}
963
964/// Helper function for distributing space to tracks evenly
965/// Used by both distribute_item_space_to_base_size and maximise_tracks steps
966fn distribute_space_up_to_limits(
967 space_to_distribute: f32,
968 tracks: &mut [GridTrack],
969 track_is_affected: impl Fn(&GridTrack) -> bool,
970 track_affected_property: impl Fn(&GridTrack) -> f32,
971 track_limit: impl Fn(&GridTrack) -> f32,
972) -> f32 {
973 /// Define a small constant to avoid infinite loops due to rounding errors. Rather than stopping distributing
974 /// extra space when it gets to exactly zero, we will stop when it falls below this amount
975 const THRESHOLD: f32 = 0.000001;
976
977 let mut space_to_distribute = space_to_distribute;
978 while space_to_distribute > THRESHOLD {
979 let number_of_growable_tracks = tracks
980 .iter()
981 .filter(|track| track_affected_property(track) + track.item_incurred_increase < track_limit(track))
982 .filter(|track| track_is_affected(track))
983 .count();
984
985 if number_of_growable_tracks == 0 {
986 break;
987 }
988
989 // Compute item-incurred increase for this iteration
990 let min_increase_limit = tracks
991 .iter()
992 .filter(|track| track_affected_property(track) + track.item_incurred_increase < track_limit(track))
993 .filter(|track| track_is_affected(track))
994 .map(|track| track_limit(track) - track_affected_property(track))
995 .min_by(|a, b| a.total_cmp(b))
996 .unwrap(); // We will never pass an empty track list to this function
997 let iteration_item_incurred_increase =
998 f32_min(min_increase_limit, space_to_distribute / number_of_growable_tracks as f32);
999
1000 for track in tracks
1001 .iter_mut()
1002 .filter(|track| track_is_affected(track))
1003 .filter(|track| track_affected_property(track) + track.item_incurred_increase < track_limit(track))
1004 {
1005 track.item_incurred_increase += iteration_item_incurred_increase;
1006 }
1007
1008 space_to_distribute -= iteration_item_incurred_increase * number_of_growable_tracks as f32;
1009 }
1010
1011 space_to_distribute
1012}