Grid: selectively rerun track sizing (#341)
1//! This module is a partial implementation of the CSS Grid Level 1 specification
2//! https://www.w3.org/TR/css-grid-1/
3use crate::axis::{AbsoluteAxis, AbstractAxis, InBothAbsAxis};
4use crate::geometry::{Line, Point, Rect, Size};
5use crate::layout::{Layout, RunMode, SizeAndBaselines, SizingMode};
6use crate::math::MaybeMath;
7use crate::node::Node;
8use crate::resolve::{MaybeResolve, ResolveOrZero};
9use crate::style::{AlignContent, AvailableSpace, Display, Position};
10use crate::style_helpers::*;
11use crate::sys::{GridTrackVec, Vec};
12use crate::tree::LayoutTree;
13use alignment::{align_and_position_item, align_tracks};
14use explicit_grid::{compute_explicit_grid_size_in_axis, initialize_grid_tracks};
15use implicit_grid::compute_grid_size_estimate;
16use placement::place_grid_items;
17use track_sizing::{
18 determine_if_item_crosses_flexible_or_intrinsic_tracks, resolve_item_track_indexes, track_sizing_algorithm,
19};
20use types::{CellOccupancyMatrix, GridTrack};
21
22pub(crate) use types::{GridCoordinate, GridLine, OriginZeroLine};
23
24#[cfg(feature = "debug")]
25use crate::debug::NODE_LOGGER;
26
27use super::{GenericAlgorithm, LayoutAlgorithm};
28
29mod alignment;
30mod explicit_grid;
31mod implicit_grid;
32mod placement;
33mod track_sizing;
34mod types;
35mod util;
36
37/// The public interface to Taffy's CSS Grid algorithm implementation
38pub(crate) struct CssGridAlgorithm;
39impl LayoutAlgorithm for CssGridAlgorithm {
40 const NAME: &'static str = "CSS GRID";
41
42 fn perform_layout(
43 tree: &mut impl LayoutTree,
44 node: Node,
45 known_dimensions: Size<Option<f32>>,
46 parent_size: Size<Option<f32>>,
47 available_space: Size<AvailableSpace>,
48 _sizing_mode: SizingMode,
49 ) -> SizeAndBaselines {
50 compute(tree, node, known_dimensions, parent_size, available_space, RunMode::PeformLayout)
51 }
52
53 fn measure_size(
54 tree: &mut impl LayoutTree,
55 node: Node,
56 known_dimensions: Size<Option<f32>>,
57 parent_size: Size<Option<f32>>,
58 available_space: Size<AvailableSpace>,
59 _sizing_mode: SizingMode,
60 ) -> Size<f32> {
61 compute(tree, node, known_dimensions, parent_size, available_space, RunMode::ComputeSize).size
62 }
63}
64
65/// Grid layout algorithm
66/// This consists of a few phases:
67/// - Resolving the explicit grid
68/// - Placing items (which also resolves the implicit grid)
69/// - Track (row/column) sizing
70/// - Alignment & Final item placement
71pub fn compute(
72 tree: &mut impl LayoutTree,
73 node: Node,
74 known_dimensions: Size<Option<f32>>,
75 parent_size: Size<Option<f32>>,
76 available_space: Size<AvailableSpace>,
77 run_mode: RunMode,
78) -> SizeAndBaselines {
79 let get_child_styles_iter = |node| tree.children(node).map(|child_node: &Node| tree.style(*child_node));
80 let style = tree.style(node).clone();
81 let child_styles_iter = get_child_styles_iter(node);
82
83 // 1. Resolve the explicit grid
84 // Exactly compute the number of rows and columns in the explicit grid.
85 let explicit_col_count = compute_explicit_grid_size_in_axis(&style, AbsoluteAxis::Horizontal);
86 let explicit_row_count = compute_explicit_grid_size_in_axis(&style, AbsoluteAxis::Vertical);
87
88 // 2. Implicit Grid: Estimate Track Counts
89 // Estimate the number of rows and columns in the implicit grid (= the entire grid)
90 // This is necessary as part of placement. Doing it early here is a perf optimisation to reduce allocations.
91 let (est_col_counts, est_row_counts) =
92 compute_grid_size_estimate(explicit_col_count, explicit_row_count, child_styles_iter);
93
94 // 2. Grid Item Placement
95 // Match items (children) to a definite grid position (row start/end and column start/end position)
96 let mut items = Vec::with_capacity(tree.child_count(node));
97 let mut cell_occupancy_matrix = CellOccupancyMatrix::with_track_counts(est_col_counts, est_row_counts);
98 let grid_auto_flow = style.grid_auto_flow;
99 let in_flow_children_iter = || {
100 tree.children(node)
101 .copied()
102 .enumerate()
103 .map(|(index, child_node)| (index, child_node, tree.style(child_node)))
104 .filter(|(_, _, style)| style.display != Display::None && style.position != Position::Absolute)
105 };
106 place_grid_items(&mut cell_occupancy_matrix, &mut items, in_flow_children_iter, grid_auto_flow);
107
108 // Extract track counts from previous step (auto-placement can expand the number of tracks)
109 let final_col_counts = *cell_occupancy_matrix.track_counts(AbsoluteAxis::Horizontal);
110 let final_row_counts = *cell_occupancy_matrix.track_counts(AbsoluteAxis::Vertical);
111
112 // 3. Initialize Tracks
113 // Initialize (explicit and implicit) grid tracks (and gutters)
114 // This resolves the min and max track sizing functions for all tracks and gutters
115 let mut columns = GridTrackVec::new();
116 let mut rows = GridTrackVec::new();
117 initialize_grid_tracks(
118 &mut columns,
119 final_col_counts,
120 &style.grid_template_columns,
121 &style.grid_auto_columns,
122 style.gap.width,
123 |column_index| cell_occupancy_matrix.column_is_occupied(column_index),
124 );
125 initialize_grid_tracks(
126 &mut rows,
127 final_row_counts,
128 &style.grid_template_rows,
129 &style.grid_auto_rows,
130 style.gap.height,
131 |row_index| cell_occupancy_matrix.row_is_occupied(row_index),
132 );
133
134 // 4. Compute "available grid space"
135 // https://www.w3.org/TR/css-grid-1/#available-grid-space
136 let padding = style.padding.resolve_or_zero(parent_size.width);
137 let border = style.border.resolve_or_zero(parent_size.width);
138 let margin = style.margin.resolve_or_zero(parent_size.width);
139 let aspect_ratio = style.aspect_ratio;
140 let min_size = style.min_size.maybe_resolve(parent_size).maybe_apply_aspect_ratio(aspect_ratio);
141 let max_size = style.max_size.maybe_resolve(parent_size).maybe_apply_aspect_ratio(aspect_ratio);
142 let size = style.size.maybe_resolve(parent_size).maybe_apply_aspect_ratio(aspect_ratio);
143
144 let constrained_available_space = size
145 .maybe_clamp(min_size, max_size)
146 .map(|size| size.map(AvailableSpace::Definite))
147 .unwrap_or(available_space.maybe_clamp(min_size, max_size));
148
149 let available_grid_space = Size {
150 width: constrained_available_space
151 .width
152 .map_definite_value(|space| space - padding.horizontal_axis_sum() - border.horizontal_axis_sum()),
153 height: constrained_available_space
154 .height
155 .map_definite_value(|space| space - padding.vertical_axis_sum() - border.vertical_axis_sum()),
156 };
157
158 let outer_node_size = size.maybe_clamp(min_size, max_size).or(parent_size.maybe_sub(margin.sum_axes()));
159 let mut inner_node_size = Size {
160 width: outer_node_size.width.map(|space| space - padding.horizontal_axis_sum() - border.horizontal_axis_sum()),
161 height: outer_node_size.height.map(|space| space - padding.vertical_axis_sum() - border.vertical_axis_sum()),
162 };
163
164 #[cfg(feature = "debug")]
165 NODE_LOGGER.labelled_debug_log("parent_size", parent_size);
166 #[cfg(feature = "debug")]
167 NODE_LOGGER.labelled_debug_log("outer_node_size", outer_node_size);
168 #[cfg(feature = "debug")]
169 NODE_LOGGER.labelled_debug_log("inner_node_size", inner_node_size);
170
171 // 5. Track Sizing
172
173 // Convert grid placements in origin-zero coordinates to indexes into the GridTrack (rows and columns) vectors
174 // This computation is relatively trivial, but it requires the final number of negative (implicit) tracks in
175 // each axis, and doing it up-front here means we don't have to keep repeating that calculation
176 resolve_item_track_indexes(&mut items, final_col_counts, final_row_counts);
177
178 // For each item, and in each axis, determine whether the item crosses any flexible (fr) tracks
179 // Record this as a boolean (per-axis) on each item for later use in the track-sizing algorithm
180 determine_if_item_crosses_flexible_or_intrinsic_tracks(&mut items, &columns, &rows);
181
182 // Run track sizing algorithm for Inline axis
183 track_sizing_algorithm(
184 tree,
185 AbstractAxis::Inline,
186 min_size.get(AbstractAxis::Inline),
187 max_size.get(AbstractAxis::Inline),
188 style.grid_align_content(AbstractAxis::Block),
189 available_grid_space,
190 inner_node_size,
191 &mut columns,
192 &mut rows,
193 &mut items,
194 |track: &GridTrack, parent_size: Option<f32>| track.max_track_sizing_function.definite_value(parent_size),
195 );
196 let initial_column_sum = columns.iter().map(|track| track.base_size).sum::<f32>();
197 inner_node_size.width = inner_node_size.width.or_else(|| initial_column_sum.into());
198
199 items.iter_mut().for_each(|item| item.known_dimensions_cache = None);
200
201 // Run track sizing algorithm for Block axis
202 track_sizing_algorithm(
203 tree,
204 AbstractAxis::Block,
205 min_size.get(AbstractAxis::Block),
206 max_size.get(AbstractAxis::Block),
207 style.grid_align_content(AbstractAxis::Inline),
208 available_grid_space,
209 inner_node_size,
210 &mut rows,
211 &mut columns,
212 &mut items,
213 |track: &GridTrack, _| Some(track.base_size),
214 );
215 let initial_row_sum = rows.iter().map(|track| track.base_size).sum::<f32>();
216 inner_node_size.height = inner_node_size.height.or_else(|| initial_row_sum.into());
217
218 // 6. Compute container size
219 let resolved_style_size = known_dimensions.or(style.size.maybe_resolve(parent_size));
220 let container_border_box = Size {
221 width: resolved_style_size
222 .get(AbstractAxis::Inline)
223 .unwrap_or_else(|| initial_column_sum + padding.horizontal_axis_sum() + border.horizontal_axis_sum()),
224 height: resolved_style_size
225 .get(AbstractAxis::Block)
226 .unwrap_or_else(|| initial_row_sum + padding.vertical_axis_sum() + border.vertical_axis_sum()),
227 };
228 let container_content_box = Size {
229 width: container_border_box.width - padding.horizontal_axis_sum() - border.horizontal_axis_sum(),
230 height: container_border_box.height - padding.vertical_axis_sum() - border.vertical_axis_sum(),
231 };
232
233 // If only the container's size has been requested
234 if run_mode == RunMode::ComputeSize {
235 return container_border_box.into();
236 }
237
238 // Column sizing must be re-run (once) if:
239 // - The grid container's width was initially indefinite and there are any columns with percentage track sizing functions
240 // - Any grid item crossing an intrinsically sized track's min content contribution width has changed
241 // TODO: Only rerun sizing for tracks that actually require it rather than for all tracks if any need it.
242 let mut rerun_column_sizing;
243
244 let has_percentage_column = columns.iter().any(|track| track.uses_percentage());
245 let parent_width_indefinite = !available_space.width.is_definite();
246 rerun_column_sizing = parent_width_indefinite && has_percentage_column;
247
248 if !rerun_column_sizing {
249 let min_content_contribution_changed = items
250 .iter_mut()
251 .filter(|item| item.crosses_intrinsic_column)
252 .map(|item| {
253 let known_dimensions = item.known_dimensions(
254 AbstractAxis::Inline,
255 &rows,
256 inner_node_size.height,
257 |track: &GridTrack, _| Some(track.base_size),
258 );
259 let new_min_content_contribution =
260 item.min_content_contribution(AbstractAxis::Inline, tree, known_dimensions, inner_node_size);
261
262 let has_changed = Some(new_min_content_contribution) != item.min_content_contribution_cache.width;
263
264 item.known_dimensions_cache = Some(known_dimensions);
265 item.min_content_contribution_cache.width = Some(new_min_content_contribution);
266 item.max_content_contribution_cache.width = None;
267 item.minimum_contribution_cache.width = None;
268
269 has_changed
270 })
271 .any(|has_changed| has_changed);
272 rerun_column_sizing = min_content_contribution_changed;
273 }
274
275 if rerun_column_sizing {
276 // Re-run track sizing algorithm for Inline axis
277 track_sizing_algorithm(
278 tree,
279 AbstractAxis::Inline,
280 min_size.get(AbstractAxis::Inline),
281 max_size.get(AbstractAxis::Inline),
282 style.grid_align_content(AbstractAxis::Block),
283 available_grid_space,
284 inner_node_size,
285 &mut columns,
286 &mut rows,
287 &mut items,
288 |track: &GridTrack, _| Some(track.base_size),
289 );
290
291 // Row sizing must be re-run (once) if:
292 // - The grid container's height was initially indefinite and there are any rows with percentage track sizing functions
293 // - Any grid item crossing an intrinsically sized track's min content contribution height has changed
294 // TODO: Only rerun sizing for tracks that actually require it rather than for all tracks if any need it.
295 let mut rerun_row_sizing;
296
297 let has_percentage_row = rows.iter().any(|track| track.uses_percentage());
298 let parent_height_indefinite = !available_space.height.is_definite();
299 rerun_row_sizing = parent_height_indefinite && has_percentage_row;
300
301 if !rerun_row_sizing {
302 let min_content_contribution_changed = items
303 .iter_mut()
304 .filter(|item| item.crosses_intrinsic_column)
305 .map(|item| {
306 let known_dimensions = item.known_dimensions(
307 AbstractAxis::Block,
308 &rows,
309 inner_node_size.width,
310 |track: &GridTrack, _| Some(track.base_size),
311 );
312 let new_min_content_contribution =
313 item.min_content_contribution(AbstractAxis::Block, tree, known_dimensions, inner_node_size);
314
315 let has_changed = Some(new_min_content_contribution) != item.min_content_contribution_cache.height;
316
317 item.known_dimensions_cache = Some(known_dimensions);
318 item.min_content_contribution_cache.height = Some(new_min_content_contribution);
319 item.max_content_contribution_cache.height = None;
320 item.minimum_contribution_cache.height = None;
321
322 has_changed
323 })
324 .any(|has_changed| has_changed);
325 rerun_row_sizing = min_content_contribution_changed;
326 }
327
328 if rerun_row_sizing {
329 // Re-run track sizing algorithm for Block axis
330 track_sizing_algorithm(
331 tree,
332 AbstractAxis::Block,
333 min_size.get(AbstractAxis::Block),
334 max_size.get(AbstractAxis::Block),
335 style.grid_align_content(AbstractAxis::Inline),
336 available_grid_space,
337 inner_node_size,
338 &mut rows,
339 &mut columns,
340 &mut items,
341 |track: &GridTrack, _| Some(track.base_size),
342 );
343 }
344 }
345
346 // 7. Resolve percentage track base sizes
347 // In the case of an indefinitely sized container these resolve to zero during the "Initialise Tracks" step
348 // and therefore need to be re-resolved here based on the content-sized content box of the container
349 if !available_grid_space.width.is_definite() {
350 for column in &mut columns {
351 let min: Option<f32> =
352 column.min_track_sizing_function.resolved_percentage_size(container_content_box.width);
353 let max: Option<f32> =
354 column.max_track_sizing_function.resolved_percentage_size(container_content_box.width);
355 column.base_size = column.base_size.maybe_clamp(min, max);
356 }
357 }
358 if !available_grid_space.height.is_definite() {
359 for row in &mut rows {
360 let min: Option<f32> = row.min_track_sizing_function.resolved_percentage_size(container_content_box.height);
361 let max: Option<f32> = row.max_track_sizing_function.resolved_percentage_size(container_content_box.height);
362 row.base_size = row.base_size.maybe_clamp(min, max);
363 }
364 }
365
366 // 8. Track Alignment
367
368 // Align columns
369 align_tracks(
370 container_content_box.get(AbstractAxis::Inline),
371 Line { start: padding.left, end: padding.right },
372 Line { start: border.left, end: border.right },
373 &mut columns,
374 style.justify_content.unwrap_or(AlignContent::Stretch),
375 );
376 // Align rows
377 align_tracks(
378 container_content_box.get(AbstractAxis::Block),
379 Line { start: padding.top, end: padding.bottom },
380 Line { start: border.top, end: border.bottom },
381 &mut rows,
382 style.align_content.unwrap_or(AlignContent::Stretch),
383 );
384
385 // 9. Size, Align, and Position Grid Items
386
387 // Sort items back into original order to allow them to be matched up with styles
388 items.sort_by_key(|item| item.source_order);
389
390 let container_alignment_styles = InBothAbsAxis { horizontal: style.justify_items, vertical: style.align_items };
391
392 // Position in-flow children (stored in items vector)
393 for (index, item) in items.iter().enumerate() {
394 let grid_area = Rect {
395 top: rows[item.row_indexes.start as usize + 1].offset,
396 bottom: rows[item.row_indexes.end as usize].offset,
397 left: columns[item.column_indexes.start as usize + 1].offset,
398 right: columns[item.column_indexes.end as usize].offset,
399 };
400 align_and_position_item(tree, item.node, index as u32, grid_area, container_alignment_styles);
401 }
402
403 // Position hidden and absolutely positioned children
404 let mut order = items.len() as u32;
405 (0..tree.child_count(node)).for_each(|index| {
406 let child = tree.child(node, index);
407 let child_style = tree.style(child);
408
409 // Position hidden child
410 if child_style.display == Display::None {
411 *tree.layout_mut(node) = Layout::with_order(order);
412 GenericAlgorithm::perform_layout(
413 tree,
414 child,
415 Size::NONE,
416 Size::NONE,
417 Size::MAX_CONTENT,
418 SizingMode::InherentSize,
419 );
420 order += 1;
421 return;
422 }
423
424 // Position absolutely positioned child
425 if child_style.position == Position::Absolute {
426 // Convert grid-col-{start/end} into Option's of indexes into the columns vector
427 // The Option is None if the style property is Auto and an unresolvable Span
428 let maybe_col_indexes = child_style
429 .grid_column
430 .into_origin_zero(final_col_counts.explicit)
431 .resolve_absolutely_positioned_grid_tracks()
432 .map(|maybe_grid_line| {
433 maybe_grid_line.map(|line: OriginZeroLine| line.into_track_vec_index(final_col_counts))
434 });
435 // Convert grid-row-{start/end} into Option's of indexes into the row vector
436 // The Option is None if the style property is Auto and an unresolvable Span
437 let maybe_row_indexes = child_style
438 .grid_row
439 .into_origin_zero(final_row_counts.explicit)
440 .resolve_absolutely_positioned_grid_tracks()
441 .map(|maybe_grid_line| {
442 maybe_grid_line.map(|line: OriginZeroLine| line.into_track_vec_index(final_row_counts))
443 });
444
445 let grid_area = Rect {
446 top: maybe_row_indexes.start.map(|index| rows[index].offset).unwrap_or(border.top),
447 bottom: maybe_row_indexes
448 .end
449 .map(|index| rows[index].offset)
450 .unwrap_or(container_border_box.height - border.bottom),
451 left: maybe_col_indexes.start.map(|index| columns[index].offset).unwrap_or(border.left),
452 right: maybe_col_indexes
453 .end
454 .map(|index| columns[index].offset)
455 .unwrap_or(container_border_box.width - border.right),
456 };
457 align_and_position_item(tree, child, order, grid_area, container_alignment_styles);
458 order += 1;
459 }
460 });
461
462 SizeAndBaselines { size: container_border_box, first_baselines: Point::NONE }
463}