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