⎇ d2b2eb08a93c6088e89b14d630cc962d551b084e
src/compute/grid/mod.rs
Ñawpa willay
Pi imata llamkarqan
ch'uya
Fix implementation of SizingMode::ContentSize for Flexbox and Grid algorithms (#576)
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, AlignItems, AlignSelf, 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, sizing_mode)
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, sizing_mode).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 sizing_mode: SizingMode,
79) -> SizeAndBaselines {
80 let get_child_styles_iter = |node| tree.children(node).map(|child_node: &Node| tree.style(*child_node));
81 let style = tree.style(node).clone();
82 let child_styles_iter = get_child_styles_iter(node);
83
84 let preferred_size = if sizing_mode == SizingMode::InherentSize {
85 style.size.maybe_resolve(parent_size).maybe_apply_aspect_ratio(style.aspect_ratio)
86 } else {
87 Size::NONE
88 };
89
90 // 1. Resolve the explicit grid
91 // Exactly compute the number of rows and columns in the explicit grid.
92 let explicit_col_count = compute_explicit_grid_size_in_axis(&style, preferred_size, AbsoluteAxis::Horizontal);
93 let explicit_row_count = compute_explicit_grid_size_in_axis(&style, preferred_size, AbsoluteAxis::Vertical);
94
95 // 2. Implicit Grid: Estimate Track Counts
96 // Estimate the number of rows and columns in the implicit grid (= the entire grid)
97 // This is necessary as part of placement. Doing it early here is a perf optimisation to reduce allocations.
98 let (est_col_counts, est_row_counts) =
99 compute_grid_size_estimate(explicit_col_count, explicit_row_count, child_styles_iter);
100
101 // 2. Grid Item Placement
102 // Match items (children) to a definite grid position (row start/end and column start/end position)
103 let mut items = Vec::with_capacity(tree.child_count(node));
104 let mut cell_occupancy_matrix = CellOccupancyMatrix::with_track_counts(est_col_counts, est_row_counts);
105 let in_flow_children_iter = || {
106 tree.children(node)
107 .copied()
108 .enumerate()
109 .map(|(index, child_node)| (index, child_node, tree.style(child_node)))
110 .filter(|(_, _, style)| style.display != Display::None && style.position != Position::Absolute)
111 };
112 place_grid_items(
113 &mut cell_occupancy_matrix,
114 &mut items,
115 in_flow_children_iter,
116 style.grid_auto_flow,
117 style.align_items.unwrap_or(AlignItems::Stretch),
118 style.justify_items.unwrap_or(AlignItems::Stretch),
119 );
120
121 // Extract track counts from previous step (auto-placement can expand the number of tracks)
122 let final_col_counts = *cell_occupancy_matrix.track_counts(AbsoluteAxis::Horizontal);
123 let final_row_counts = *cell_occupancy_matrix.track_counts(AbsoluteAxis::Vertical);
124
125 // 3. Initialize Tracks
126 // Initialize (explicit and implicit) grid tracks (and gutters)
127 // This resolves the min and max track sizing functions for all tracks and gutters
128 let mut columns = GridTrackVec::new();
129 let mut rows = GridTrackVec::new();
130 initialize_grid_tracks(
131 &mut columns,
132 final_col_counts,
133 &style.grid_template_columns,
134 &style.grid_auto_columns,
135 style.gap.width,
136 |column_index| cell_occupancy_matrix.column_is_occupied(column_index),
137 );
138 initialize_grid_tracks(
139 &mut rows,
140 final_row_counts,
141 &style.grid_template_rows,
142 &style.grid_auto_rows,
143 style.gap.height,
144 |row_index| cell_occupancy_matrix.row_is_occupied(row_index),
145 );
146
147 // 4. Compute "available grid space"
148 // https://www.w3.org/TR/css-grid-1/#available-grid-space
149 let padding = style.padding.resolve_or_zero(parent_size.width);
150 let border = style.border.resolve_or_zero(parent_size.width);
151 let padding_border_size = (padding + border).sum_axes();
152 let aspect_ratio = style.aspect_ratio;
153 let min_size = style.min_size.maybe_resolve(parent_size).maybe_apply_aspect_ratio(aspect_ratio);
154 let max_size = style.max_size.maybe_resolve(parent_size).maybe_apply_aspect_ratio(aspect_ratio);
155 let size = preferred_size;
156
157 let constrained_available_space = known_dimensions
158 .or(size)
159 .map(|size| size.map(AvailableSpace::Definite))
160 .unwrap_or(available_space)
161 .maybe_clamp(min_size, max_size)
162 .maybe_max(padding_border_size);
163
164 let available_grid_space = Size {
165 width: constrained_available_space
166 .width
167 .map_definite_value(|space| space - padding.horizontal_axis_sum() - border.horizontal_axis_sum()),
168 height: constrained_available_space
169 .height
170 .map_definite_value(|space| space - padding.vertical_axis_sum() - border.vertical_axis_sum()),
171 };
172
173 let outer_node_size = known_dimensions.or(size).maybe_clamp(min_size, max_size).maybe_max(padding_border_size);
174 let mut inner_node_size = Size {
175 width: outer_node_size.width.map(|space| space - padding.horizontal_axis_sum() - border.horizontal_axis_sum()),
176 height: outer_node_size.height.map(|space| space - padding.vertical_axis_sum() - border.vertical_axis_sum()),
177 };
178
179 #[cfg(feature = "debug")]
180 NODE_LOGGER.labelled_debug_log("parent_size", parent_size);
181 #[cfg(feature = "debug")]
182 NODE_LOGGER.labelled_debug_log("outer_node_size", outer_node_size);
183 #[cfg(feature = "debug")]
184 NODE_LOGGER.labelled_debug_log("inner_node_size", inner_node_size);
185
186 // 5. Track Sizing
187
188 // Convert grid placements in origin-zero coordinates to indexes into the GridTrack (rows and columns) vectors
189 // This computation is relatively trivial, but it requires the final number of negative (implicit) tracks in
190 // each axis, and doing it up-front here means we don't have to keep repeating that calculation
191 resolve_item_track_indexes(&mut items, final_col_counts, final_row_counts);
192
193 // For each item, and in each axis, determine whether the item crosses any flexible (fr) tracks
194 // Record this as a boolean (per-axis) on each item for later use in the track-sizing algorithm
195 determine_if_item_crosses_flexible_or_intrinsic_tracks(&mut items, &columns, &rows);
196
197 // Determine if the grid has any baseline aligned items
198 let has_baseline_aligned_item = items.iter().any(|item| item.align_self == AlignSelf::Baseline);
199
200 // Run track sizing algorithm for Inline axis
201 track_sizing_algorithm(
202 tree,
203 AbstractAxis::Inline,
204 min_size.get(AbstractAxis::Inline),
205 max_size.get(AbstractAxis::Inline),
206 style.grid_align_content(AbstractAxis::Block),
207 available_grid_space,
208 inner_node_size,
209 &mut columns,
210 &mut rows,
211 &mut items,
212 |track: &GridTrack, parent_size: Option<f32>| track.max_track_sizing_function.definite_value(parent_size),
213 has_baseline_aligned_item,
214 );
215 let initial_column_sum = columns.iter().map(|track| track.base_size).sum::<f32>();
216 inner_node_size.width = inner_node_size.width.or_else(|| initial_column_sum.into());
217
218 items.iter_mut().for_each(|item| item.available_space_cache = None);
219
220 // Run track sizing algorithm for Block axis
221 track_sizing_algorithm(
222 tree,
223 AbstractAxis::Block,
224 min_size.get(AbstractAxis::Block),
225 max_size.get(AbstractAxis::Block),
226 style.grid_align_content(AbstractAxis::Inline),
227 available_grid_space,
228 inner_node_size,
229 &mut rows,
230 &mut columns,
231 &mut items,
232 |track: &GridTrack, _| Some(track.base_size),
233 false, // TODO: Support baseline alignment in the vertical axis
234 );
235 let initial_row_sum = rows.iter().map(|track| track.base_size).sum::<f32>();
236 inner_node_size.height = inner_node_size.height.or_else(|| initial_row_sum.into());
237
238 #[cfg(feature = "debug")]
239 NODE_LOGGER.labelled_debug_log("initial_column_sum", initial_column_sum);
240 #[cfg(feature = "debug")]
241 NODE_LOGGER.labelled_debug_log("initial_row_sum", initial_row_sum);
242
243 // 6. Compute container size
244 let resolved_style_size = known_dimensions.or(preferred_size);
245 let container_border_box = Size {
246 width: resolved_style_size
247 .get(AbstractAxis::Inline)
248 .unwrap_or_else(|| initial_column_sum + padding.horizontal_axis_sum() + border.horizontal_axis_sum())
249 .maybe_clamp(min_size.width, max_size.width)
250 .max(padding_border_size.width),
251 height: resolved_style_size
252 .get(AbstractAxis::Block)
253 .unwrap_or_else(|| initial_row_sum + padding.vertical_axis_sum() + border.vertical_axis_sum())
254 .maybe_clamp(min_size.height, max_size.height)
255 .max(padding_border_size.height),
256 };
257 let container_content_box = Size {
258 width: container_border_box.width - padding.horizontal_axis_sum() - border.horizontal_axis_sum(),
259 height: container_border_box.height - padding.vertical_axis_sum() - border.vertical_axis_sum(),
260 };
261
262 // If only the container's size has been requested
263 if run_mode == RunMode::ComputeSize {
264 return container_border_box.into();
265 }
266
267 // 7. Resolve percentage track base sizes
268 // In the case of an indefinitely sized container these resolve to zero during the "Initialise Tracks" step
269 // and therefore need to be re-resolved here based on the content-sized content box of the container
270 if !available_grid_space.width.is_definite() {
271 for column in &mut columns {
272 let min: Option<f32> =
273 column.min_track_sizing_function.resolved_percentage_size(container_content_box.width);
274 let max: Option<f32> =
275 column.max_track_sizing_function.resolved_percentage_size(container_content_box.width);
276 column.base_size = column.base_size.maybe_clamp(min, max);
277 }
278 }
279 if !available_grid_space.height.is_definite() {
280 for row in &mut rows {
281 let min: Option<f32> = row.min_track_sizing_function.resolved_percentage_size(container_content_box.height);
282 let max: Option<f32> = row.max_track_sizing_function.resolved_percentage_size(container_content_box.height);
283 row.base_size = row.base_size.maybe_clamp(min, max);
284 }
285 }
286
287 // Column sizing must be re-run (once) if:
288 // - The grid container's width was initially indefinite and there are any columns with percentage track sizing functions
289 // - Any grid item crossing an intrinsically sized track's min content contribution width has changed
290 // TODO: Only rerun sizing for tracks that actually require it rather than for all tracks if any need it.
291 let mut rerun_column_sizing;
292
293 let has_percentage_column = columns.iter().any(|track| track.uses_percentage());
294 let parent_width_indefinite = !available_space.width.is_definite();
295 rerun_column_sizing = parent_width_indefinite && has_percentage_column;
296
297 if !rerun_column_sizing {
298 let min_content_contribution_changed = items
299 .iter_mut()
300 .filter(|item| item.crosses_intrinsic_column)
301 .map(|item| {
302 let available_space = item.available_space(
303 AbstractAxis::Inline,
304 &rows,
305 inner_node_size.height,
306 |track: &GridTrack, _| Some(track.base_size),
307 );
308 let new_min_content_contribution =
309 item.min_content_contribution(AbstractAxis::Inline, tree, available_space, inner_node_size);
310
311 let has_changed = Some(new_min_content_contribution) != item.min_content_contribution_cache.width;
312
313 item.available_space_cache = Some(available_space);
314 item.min_content_contribution_cache.width = Some(new_min_content_contribution);
315 item.max_content_contribution_cache.width = None;
316 item.minimum_contribution_cache.width = None;
317
318 has_changed
319 })
320 .any(|has_changed| has_changed);
321 rerun_column_sizing = min_content_contribution_changed;
322 } else {
323 // Clear intrisic width caches
324 items.iter_mut().for_each(|item| {
325 item.available_space_cache = None;
326 item.min_content_contribution_cache.width = None;
327 item.max_content_contribution_cache.width = None;
328 item.minimum_contribution_cache.width = None;
329 });
330 }
331
332 if rerun_column_sizing {
333 // Re-run track sizing algorithm for Inline axis
334 track_sizing_algorithm(
335 tree,
336 AbstractAxis::Inline,
337 min_size.get(AbstractAxis::Inline),
338 max_size.get(AbstractAxis::Inline),
339 style.grid_align_content(AbstractAxis::Block),
340 available_grid_space,
341 inner_node_size,
342 &mut columns,
343 &mut rows,
344 &mut items,
345 |track: &GridTrack, _| Some(track.base_size),
346 has_baseline_aligned_item,
347 );
348
349 // Row sizing must be re-run (once) if:
350 // - The grid container's height was initially indefinite and there are any rows with percentage track sizing functions
351 // - Any grid item crossing an intrinsically sized track's min content contribution height has changed
352 // TODO: Only rerun sizing for tracks that actually require it rather than for all tracks if any need it.
353 let mut rerun_row_sizing;
354
355 let has_percentage_row = rows.iter().any(|track| track.uses_percentage());
356 let parent_height_indefinite = !available_space.height.is_definite();
357 rerun_row_sizing = parent_height_indefinite && has_percentage_row;
358
359 if !rerun_row_sizing {
360 let min_content_contribution_changed = items
361 .iter_mut()
362 .filter(|item| item.crosses_intrinsic_column)
363 .map(|item| {
364 let available_space = item.available_space(
365 AbstractAxis::Block,
366 &columns,
367 inner_node_size.width,
368 |track: &GridTrack, _| Some(track.base_size),
369 );
370 let new_min_content_contribution =
371 item.min_content_contribution(AbstractAxis::Block, tree, available_space, inner_node_size);
372
373 let has_changed = Some(new_min_content_contribution) != item.min_content_contribution_cache.height;
374
375 item.available_space_cache = Some(available_space);
376 item.min_content_contribution_cache.height = Some(new_min_content_contribution);
377 item.max_content_contribution_cache.height = None;
378 item.minimum_contribution_cache.height = None;
379
380 has_changed
381 })
382 .any(|has_changed| has_changed);
383 rerun_row_sizing = min_content_contribution_changed;
384 } else {
385 items.iter_mut().for_each(|item| {
386 // Clear intrisic height caches
387 item.available_space_cache = None;
388 item.min_content_contribution_cache.height = None;
389 item.max_content_contribution_cache.height = None;
390 item.minimum_contribution_cache.height = None;
391 });
392 }
393
394 if rerun_row_sizing {
395 // Re-run track sizing algorithm for Block axis
396 track_sizing_algorithm(
397 tree,
398 AbstractAxis::Block,
399 min_size.get(AbstractAxis::Block),
400 max_size.get(AbstractAxis::Block),
401 style.grid_align_content(AbstractAxis::Inline),
402 available_grid_space,
403 inner_node_size,
404 &mut rows,
405 &mut columns,
406 &mut items,
407 |track: &GridTrack, _| Some(track.base_size),
408 false, // TODO: Support baseline alignment in the vertical axis
409 );
410 }
411 }
412
413 // 8. Track Alignment
414
415 // Align columns
416 align_tracks(
417 container_content_box.get(AbstractAxis::Inline),
418 Line { start: padding.left, end: padding.right },
419 Line { start: border.left, end: border.right },
420 &mut columns,
421 style.justify_content.unwrap_or(AlignContent::Stretch),
422 );
423 // Align rows
424 align_tracks(
425 container_content_box.get(AbstractAxis::Block),
426 Line { start: padding.top, end: padding.bottom },
427 Line { start: border.top, end: border.bottom },
428 &mut rows,
429 style.align_content.unwrap_or(AlignContent::Stretch),
430 );
431
432 // 9. Size, Align, and Position Grid Items
433
434 // Sort items back into original order to allow them to be matched up with styles
435 items.sort_by_key(|item| item.source_order);
436
437 let container_alignment_styles = InBothAbsAxis { horizontal: style.justify_items, vertical: style.align_items };
438
439 // Position in-flow children (stored in items vector)
440 for (index, item) in items.iter().enumerate() {
441 let grid_area = Rect {
442 top: rows[item.row_indexes.start as usize + 1].offset,
443 bottom: rows[item.row_indexes.end as usize].offset,
444 left: columns[item.column_indexes.start as usize + 1].offset,
445 right: columns[item.column_indexes.end as usize].offset,
446 };
447 align_and_position_item(
448 tree,
449 item.node,
450 index as u32,
451 grid_area,
452 container_alignment_styles,
453 item.baseline_shim,
454 );
455 }
456
457 // Position hidden and absolutely positioned children
458 let mut order = items.len() as u32;
459 (0..tree.child_count(node)).for_each(|index| {
460 let child = tree.child(node, index);
461 let child_style = tree.style(child);
462
463 // Position hidden child
464 if child_style.display == Display::None {
465 *tree.layout_mut(child) = Layout::with_order(order);
466 GenericAlgorithm::perform_layout(
467 tree,
468 child,
469 Size::NONE,
470 Size::NONE,
471 Size::MAX_CONTENT,
472 SizingMode::InherentSize,
473 );
474 order += 1;
475 return;
476 }
477
478 // Position absolutely positioned child
479 if child_style.position == Position::Absolute {
480 // Convert grid-col-{start/end} into Option's of indexes into the columns vector
481 // The Option is None if the style property is Auto and an unresolvable Span
482 let maybe_col_indexes = child_style
483 .grid_column
484 .into_origin_zero(final_col_counts.explicit)
485 .resolve_absolutely_positioned_grid_tracks()
486 .map(|maybe_grid_line| {
487 maybe_grid_line.map(|line: OriginZeroLine| line.into_track_vec_index(final_col_counts))
488 });
489 // Convert grid-row-{start/end} into Option's of indexes into the row vector
490 // The Option is None if the style property is Auto and an unresolvable Span
491 let maybe_row_indexes = child_style
492 .grid_row
493 .into_origin_zero(final_row_counts.explicit)
494 .resolve_absolutely_positioned_grid_tracks()
495 .map(|maybe_grid_line| {
496 maybe_grid_line.map(|line: OriginZeroLine| line.into_track_vec_index(final_row_counts))
497 });
498
499 let grid_area = Rect {
500 top: maybe_row_indexes.start.map(|index| rows[index].offset).unwrap_or(border.top),
501 bottom: maybe_row_indexes
502 .end
503 .map(|index| rows[index].offset)
504 .unwrap_or(container_border_box.height - border.bottom),
505 left: maybe_col_indexes.start.map(|index| columns[index].offset).unwrap_or(border.left),
506 right: maybe_col_indexes
507 .end
508 .map(|index| columns[index].offset)
509 .unwrap_or(container_border_box.width - border.right),
510 };
511 // TODO: Baseline alignment support for absolutely positioned items (should check if is actuallty specified)
512 align_and_position_item(tree, child, order, grid_area, container_alignment_styles, 0.0);
513 order += 1;
514 }
515 });
516
517 // If there are not items then return just the container size (no baseline)
518 if items.is_empty() {
519 return SizeAndBaselines { size: container_border_box, first_baselines: Point::NONE };
520 }
521
522 // Determine the grid container baseline(s) (currently we only compute the first baseline)
523 let grid_container_baseline: f32 = {
524 // Sort items by row start position so that we can iterate items in groups which are in the same row
525 items.sort_by_key(|item| item.row_indexes.start);
526
527 // Get the row index of the first row containing items
528 let first_row = items[0].row_indexes.start;
529
530 // Create a slice of all of the items start in this row (taking advantage of the fact that we have just sorted the array)
531 let first_row_items = &items[0..].split(|item| item.row_indexes.start != first_row).next().unwrap();
532
533 // Check if any items in *this row* are baseline aligned
534 let row_has_baseline_item = first_row_items.iter().any(|item| item.align_self == AlignSelf::Baseline);
535
536 let item = if row_has_baseline_item {
537 first_row_items.iter().find(|item| item.align_self == AlignSelf::Baseline).unwrap()
538 } else {
539 &first_row_items[0]
540 };
541
542 let layout = tree.layout_mut(item.node);
543 layout.location.y + item.baseline.unwrap_or(layout.size.height)
544 };
545
546 SizeAndBaselines {
547 size: container_border_box,
548 first_baselines: Point { x: None, y: Some(grid_container_baseline) },
549 }
550}