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