Make low-level layout algorithm functions public (#434)
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::axis::{AbsoluteAxis, AbstractAxis, InBothAbsAxis};
4use crate::geometry::{Line, Point, Rect, Size};
5use crate::layout::{Layout, RunMode, SizeAndBaselines, SizingMode};
6use crate::math::MaybeMath;
7use crate::resolve::{MaybeResolve, ResolveOrZero};
8use crate::style::{AlignContent, AlignItems, AlignSelf, AvailableSpace, Display, Position};
9use crate::style_helpers::*;
10use crate::sys::{GridTrackVec, Vec};
11use crate::tree::{LayoutTree, NodeId};
12use alignment::{align_and_position_item, align_tracks};
13use explicit_grid::{compute_explicit_grid_size_in_axis, initialize_grid_tracks};
14use implicit_grid::compute_grid_size_estimate;
15use placement::place_grid_items;
16use track_sizing::{
17 determine_if_item_crosses_flexible_or_intrinsic_tracks, resolve_item_track_indexes, track_sizing_algorithm,
18};
19use types::{CellOccupancyMatrix, GridTrack};
20
21pub(crate) use types::{GridCoordinate, GridLine, OriginZeroLine};
22
23#[cfg(feature = "debug")]
24use crate::debug::NODE_LOGGER;
25
26use super::LayoutAlgorithm;
27
28mod alignment;
29mod explicit_grid;
30mod implicit_grid;
31mod placement;
32mod track_sizing;
33mod types;
34mod util;
35
36/// The public interface to Taffy's CSS Grid algorithm implementation
37pub struct CssGridAlgorithm;
38impl LayoutAlgorithm for CssGridAlgorithm {
39 const NAME: &'static str = "CSS GRID";
40
41 fn perform_layout(
42 tree: &mut impl LayoutTree,
43 node: NodeId,
44 known_dimensions: Size<Option<f32>>,
45 parent_size: Size<Option<f32>>,
46 available_space: Size<AvailableSpace>,
47 _sizing_mode: SizingMode,
48 ) -> SizeAndBaselines {
49 compute(tree, node, known_dimensions, parent_size, available_space, RunMode::PeformLayout)
50 }
51
52 fn measure_size(
53 tree: &mut impl LayoutTree,
54 node: NodeId,
55 known_dimensions: Size<Option<f32>>,
56 parent_size: Size<Option<f32>>,
57 available_space: Size<AvailableSpace>,
58 _sizing_mode: SizingMode,
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) -> SizeAndBaselines {
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_size = (padding + border).sum_axes();
143 let aspect_ratio = style.aspect_ratio;
144 let min_size = style.min_size.maybe_resolve(parent_size).maybe_apply_aspect_ratio(aspect_ratio);
145 let max_size = style.max_size.maybe_resolve(parent_size).maybe_apply_aspect_ratio(aspect_ratio);
146 let size = style.size.maybe_resolve(parent_size).maybe_apply_aspect_ratio(aspect_ratio);
147
148 let constrained_available_space = known_dimensions
149 .or(size)
150 .maybe_clamp(min_size, max_size)
151 .map(|size| size.map(AvailableSpace::Definite))
152 .unwrap_or(available_space.map(|space| match space {
153 // Available grid space should not depend on Definite available space as a grid is allowed
154 // to expand beyond it's available space
155 AvailableSpace::Definite(_) => AvailableSpace::MaxContent,
156 _ => space,
157 }));
158
159 let available_grid_space = Size {
160 width: constrained_available_space
161 .width
162 .map_definite_value(|space| space - padding.horizontal_axis_sum() - border.horizontal_axis_sum()),
163 height: constrained_available_space
164 .height
165 .map_definite_value(|space| space - padding.vertical_axis_sum() - border.vertical_axis_sum()),
166 };
167
168 let outer_node_size = known_dimensions.or(size.maybe_clamp(min_size, max_size).or(min_size));
169 let mut inner_node_size = Size {
170 width: outer_node_size.width.map(|space| space - padding.horizontal_axis_sum() - border.horizontal_axis_sum()),
171 height: outer_node_size.height.map(|space| space - padding.vertical_axis_sum() - border.vertical_axis_sum()),
172 };
173
174 #[cfg(feature = "debug")]
175 NODE_LOGGER.labelled_debug_log("parent_size", parent_size);
176 #[cfg(feature = "debug")]
177 NODE_LOGGER.labelled_debug_log("outer_node_size", outer_node_size);
178 #[cfg(feature = "debug")]
179 NODE_LOGGER.labelled_debug_log("inner_node_size", inner_node_size);
180
181 // 5. Track Sizing
182
183 // Convert grid placements in origin-zero coordinates to indexes into the GridTrack (rows and columns) vectors
184 // This computation is relatively trivial, but it requires the final number of negative (implicit) tracks in
185 // each axis, and doing it up-front here means we don't have to keep repeating that calculation
186 resolve_item_track_indexes(&mut items, final_col_counts, final_row_counts);
187
188 // For each item, and in each axis, determine whether the item crosses any flexible (fr) tracks
189 // Record this as a boolean (per-axis) on each item for later use in the track-sizing algorithm
190 determine_if_item_crosses_flexible_or_intrinsic_tracks(&mut items, &columns, &rows);
191
192 // Determine if the grid has any baseline aligned items
193 let has_baseline_aligned_item = items.iter().any(|item| item.align_self == AlignSelf::Baseline);
194
195 // Run track sizing algorithm for Inline axis
196 track_sizing_algorithm(
197 tree,
198 AbstractAxis::Inline,
199 min_size.get(AbstractAxis::Inline),
200 max_size.get(AbstractAxis::Inline),
201 style.grid_align_content(AbstractAxis::Block),
202 available_grid_space,
203 inner_node_size,
204 &mut columns,
205 &mut rows,
206 &mut items,
207 |track: &GridTrack, parent_size: Option<f32>| track.max_track_sizing_function.definite_value(parent_size),
208 has_baseline_aligned_item,
209 );
210 let initial_column_sum = columns.iter().map(|track| track.base_size).sum::<f32>();
211 inner_node_size.width = inner_node_size.width.or_else(|| initial_column_sum.into());
212
213 items.iter_mut().for_each(|item| item.available_space_cache = None);
214
215 // Run track sizing algorithm for Block axis
216 track_sizing_algorithm(
217 tree,
218 AbstractAxis::Block,
219 min_size.get(AbstractAxis::Block),
220 max_size.get(AbstractAxis::Block),
221 style.grid_align_content(AbstractAxis::Inline),
222 available_grid_space,
223 inner_node_size,
224 &mut rows,
225 &mut columns,
226 &mut items,
227 |track: &GridTrack, _| Some(track.base_size),
228 false, // TODO: Support baseline alignment in the vertical axis
229 );
230 let initial_row_sum = rows.iter().map(|track| track.base_size).sum::<f32>();
231 inner_node_size.height = inner_node_size.height.or_else(|| initial_row_sum.into());
232
233 // 6. Compute container size
234 let resolved_style_size = known_dimensions.or(style.size.maybe_resolve(parent_size));
235 let container_border_box = Size {
236 width: resolved_style_size
237 .get(AbstractAxis::Inline)
238 .unwrap_or_else(|| initial_column_sum + padding.horizontal_axis_sum() + border.horizontal_axis_sum())
239 .max(padding_border_size.width),
240 height: resolved_style_size
241 .get(AbstractAxis::Block)
242 .unwrap_or_else(|| initial_row_sum + padding.vertical_axis_sum() + border.vertical_axis_sum())
243 .max(padding_border_size.height),
244 };
245 let container_content_box = Size {
246 width: container_border_box.width - padding.horizontal_axis_sum() - border.horizontal_axis_sum(),
247 height: container_border_box.height - padding.vertical_axis_sum() - border.vertical_axis_sum(),
248 };
249
250 // If only the container's size has been requested
251 if run_mode == RunMode::ComputeSize {
252 return container_border_box.into();
253 }
254
255 // 7. Resolve percentage track base sizes
256 // In the case of an indefinitely sized container these resolve to zero during the "Initialise Tracks" step
257 // and therefore need to be re-resolved here based on the content-sized content box of the container
258 if !available_grid_space.width.is_definite() {
259 for column in &mut columns {
260 let min: Option<f32> =
261 column.min_track_sizing_function.resolved_percentage_size(container_content_box.width);
262 let max: Option<f32> =
263 column.max_track_sizing_function.resolved_percentage_size(container_content_box.width);
264 column.base_size = column.base_size.maybe_clamp(min, max);
265 }
266 }
267 if !available_grid_space.height.is_definite() {
268 for row in &mut rows {
269 let min: Option<f32> = row.min_track_sizing_function.resolved_percentage_size(container_content_box.height);
270 let max: Option<f32> = row.max_track_sizing_function.resolved_percentage_size(container_content_box.height);
271 row.base_size = row.base_size.maybe_clamp(min, max);
272 }
273 }
274
275 // Column sizing must be re-run (once) if:
276 // - The grid container's width was initially indefinite and there are any columns with percentage track sizing functions
277 // - Any grid item crossing an intrinsically sized track's min content contribution width has changed
278 // TODO: Only rerun sizing for tracks that actually require it rather than for all tracks if any need it.
279 let mut rerun_column_sizing;
280
281 let has_percentage_column = columns.iter().any(|track| track.uses_percentage());
282 let parent_width_indefinite = !available_space.width.is_definite();
283 rerun_column_sizing = parent_width_indefinite && has_percentage_column;
284
285 if !rerun_column_sizing {
286 let min_content_contribution_changed = items
287 .iter_mut()
288 .filter(|item| item.crosses_intrinsic_column)
289 .map(|item| {
290 let available_space = item.available_space(
291 AbstractAxis::Inline,
292 &rows,
293 inner_node_size.height,
294 |track: &GridTrack, _| Some(track.base_size),
295 );
296 let new_min_content_contribution =
297 item.min_content_contribution(AbstractAxis::Inline, tree, available_space, inner_node_size);
298
299 let has_changed = Some(new_min_content_contribution) != item.min_content_contribution_cache.width;
300
301 item.available_space_cache = Some(available_space);
302 item.min_content_contribution_cache.width = Some(new_min_content_contribution);
303 item.max_content_contribution_cache.width = None;
304 item.minimum_contribution_cache.width = None;
305
306 has_changed
307 })
308 .any(|has_changed| has_changed);
309 rerun_column_sizing = min_content_contribution_changed;
310 } else {
311 // Clear intrisic width caches
312 items.iter_mut().for_each(|item| {
313 item.available_space_cache = None;
314 item.min_content_contribution_cache.width = None;
315 item.max_content_contribution_cache.width = None;
316 item.minimum_contribution_cache.width = None;
317 });
318 }
319
320 if rerun_column_sizing {
321 // Re-run track sizing algorithm for Inline axis
322 track_sizing_algorithm(
323 tree,
324 AbstractAxis::Inline,
325 min_size.get(AbstractAxis::Inline),
326 max_size.get(AbstractAxis::Inline),
327 style.grid_align_content(AbstractAxis::Block),
328 available_grid_space,
329 inner_node_size,
330 &mut columns,
331 &mut rows,
332 &mut items,
333 |track: &GridTrack, _| Some(track.base_size),
334 has_baseline_aligned_item,
335 );
336
337 // Row sizing must be re-run (once) if:
338 // - The grid container's height was initially indefinite and there are any rows with percentage track sizing functions
339 // - Any grid item crossing an intrinsically sized track's min content contribution height has changed
340 // TODO: Only rerun sizing for tracks that actually require it rather than for all tracks if any need it.
341 let mut rerun_row_sizing;
342
343 let has_percentage_row = rows.iter().any(|track| track.uses_percentage());
344 let parent_height_indefinite = !available_space.height.is_definite();
345 rerun_row_sizing = parent_height_indefinite && has_percentage_row;
346
347 if !rerun_row_sizing {
348 let min_content_contribution_changed = items
349 .iter_mut()
350 .filter(|item| item.crosses_intrinsic_column)
351 .map(|item| {
352 let available_space = item.available_space(
353 AbstractAxis::Block,
354 &columns,
355 inner_node_size.width,
356 |track: &GridTrack, _| Some(track.base_size),
357 );
358 let new_min_content_contribution =
359 item.min_content_contribution(AbstractAxis::Block, tree, available_space, inner_node_size);
360
361 let has_changed = Some(new_min_content_contribution) != item.min_content_contribution_cache.height;
362
363 item.available_space_cache = Some(available_space);
364 item.min_content_contribution_cache.height = Some(new_min_content_contribution);
365 item.max_content_contribution_cache.height = None;
366 item.minimum_contribution_cache.height = None;
367
368 has_changed
369 })
370 .any(|has_changed| has_changed);
371 rerun_row_sizing = min_content_contribution_changed;
372 } else {
373 items.iter_mut().for_each(|item| {
374 // Clear intrisic height caches
375 item.available_space_cache = None;
376 item.min_content_contribution_cache.height = None;
377 item.max_content_contribution_cache.height = None;
378 item.minimum_contribution_cache.height = None;
379 });
380 }
381
382 if rerun_row_sizing {
383 // Re-run track sizing algorithm for Block axis
384 track_sizing_algorithm(
385 tree,
386 AbstractAxis::Block,
387 min_size.get(AbstractAxis::Block),
388 max_size.get(AbstractAxis::Block),
389 style.grid_align_content(AbstractAxis::Inline),
390 available_grid_space,
391 inner_node_size,
392 &mut rows,
393 &mut columns,
394 &mut items,
395 |track: &GridTrack, _| Some(track.base_size),
396 false, // TODO: Support baseline alignment in the vertical axis
397 );
398 }
399 }
400
401 // 8. Track Alignment
402
403 // Align columns
404 align_tracks(
405 container_content_box.get(AbstractAxis::Inline),
406 Line { start: padding.left, end: padding.right },
407 Line { start: border.left, end: border.right },
408 &mut columns,
409 style.justify_content.unwrap_or(AlignContent::Stretch),
410 );
411 // Align rows
412 align_tracks(
413 container_content_box.get(AbstractAxis::Block),
414 Line { start: padding.top, end: padding.bottom },
415 Line { start: border.top, end: border.bottom },
416 &mut rows,
417 style.align_content.unwrap_or(AlignContent::Stretch),
418 );
419
420 // 9. Size, Align, and Position Grid Items
421
422 // Sort items back into original order to allow them to be matched up with styles
423 items.sort_by_key(|item| item.source_order);
424
425 let container_alignment_styles = InBothAbsAxis { horizontal: style.justify_items, vertical: style.align_items };
426
427 // Position in-flow children (stored in items vector)
428 for (index, item) in items.iter().enumerate() {
429 let grid_area = Rect {
430 top: rows[item.row_indexes.start as usize + 1].offset,
431 bottom: rows[item.row_indexes.end as usize].offset,
432 left: columns[item.column_indexes.start as usize + 1].offset,
433 right: columns[item.column_indexes.end as usize].offset,
434 };
435 align_and_position_item(
436 tree,
437 item.node,
438 index as u32,
439 grid_area,
440 container_alignment_styles,
441 item.baseline_shim,
442 );
443 }
444
445 // Position hidden and absolutely positioned children
446 let mut order = items.len() as u32;
447 (0..tree.child_count(node)).for_each(|index| {
448 let child = tree.child(node, index);
449 let child_style = tree.style(child);
450
451 // Position hidden child
452 if child_style.display == Display::None {
453 *tree.layout_mut(child) = Layout::with_order(order);
454 tree.perform_child_layout(child, Size::NONE, Size::NONE, Size::MAX_CONTENT, SizingMode::InherentSize);
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),
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),
491 };
492 // TODO: Baseline alignment support for absolutely positioned items (should check if is actuallty specified)
493 align_and_position_item(tree, child, order, grid_area, container_alignment_styles, 0.0);
494 order += 1;
495 }
496 });
497
498 // If there are not items then return just the container size (no baseline)
499 if items.is_empty() {
500 return SizeAndBaselines { size: container_border_box, first_baselines: Point::NONE };
501 }
502
503 // Determine the grid container baseline(s) (currently we only compute the first baseline)
504 let grid_container_baseline: f32 = {
505 // Sort items by row start position so that we can iterate items in groups which are in the same row
506 items.sort_by_key(|item| item.row_indexes.start);
507
508 // Get the row index of the first row containing items
509 let first_row = items[0].row_indexes.start;
510
511 // Create a slice of all of the items start in this row (taking advantage of the fact that we have just sorted the array)
512 let first_row_items = &items[0..].split(|item| item.row_indexes.start != first_row).next().unwrap();
513
514 // Check if any items in *this row* are baseline aligned
515 let row_has_baseline_item = first_row_items.iter().any(|item| item.align_self == AlignSelf::Baseline);
516
517 let item = if row_has_baseline_item {
518 first_row_items.iter().find(|item| item.align_self == AlignSelf::Baseline).unwrap()
519 } else {
520 &first_row_items[0]
521 };
522
523 let layout = tree.layout_mut(item.node);
524 layout.location.y + item.baseline.unwrap_or(layout.size.height)
525 };
526
527 SizeAndBaselines {
528 size: container_border_box,
529 first_baselines: Point { x: None, y: Some(grid_container_baseline) },
530 }
531}