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