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