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