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