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