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::node::Node;
8use crate::resolve::{MaybeResolve, ResolveOrZero};
9use crate::style::{AlignContent, AvailableSpace, Display, Position};
10use crate::style_helpers::*;
11use crate::sys::{GridTrackVec, Vec};
12use crate::tree::LayoutTree;
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::{determine_if_item_crosses_flexible_tracks, resolve_item_track_indexes, track_sizing_algorithm};
18use types::{CellOccupancyMatrix, GridTrack};
19
20pub(crate) use types::{GridCoordinate, GridLine, OriginZeroLine};
21
22#[cfg(feature = "debug")]
23use crate::debug::NODE_LOGGER;
24
25use super::{GenericAlgorithm, LayoutAlgorithm};
26
27mod alignment;
28mod explicit_grid;
29mod implicit_grid;
30mod placement;
31mod track_sizing;
32mod types;
33mod util;
34
35/// The public interface to Taffy's CSS Grid algorithm implementation
36pub(crate) struct CssGridAlgorithm;
37impl LayoutAlgorithm for CssGridAlgorithm {
38 const NAME: &'static str = "CSS GRID";
39
40 fn perform_layout(
41 tree: &mut impl LayoutTree,
42 node: Node,
43 known_dimensions: Size<Option<f32>>,
44 parent_size: Size<Option<f32>>,
45 available_space: Size<AvailableSpace>,
46 _sizing_mode: SizingMode,
47 ) -> SizeAndBaselines {
48 compute(tree, node, known_dimensions, parent_size, available_space, RunMode::PeformLayout)
49 }
50
51 fn measure_size(
52 tree: &mut impl LayoutTree,
53 node: Node,
54 known_dimensions: Size<Option<f32>>,
55 parent_size: Size<Option<f32>>,
56 available_space: Size<AvailableSpace>,
57 _sizing_mode: SizingMode,
58 ) -> Size<f32> {
59 compute(tree, node, known_dimensions, parent_size, available_space, RunMode::ComputeSize).size
60 }
61}
62
63/// Grid layout algorithm
64/// This consists of a few phases:
65/// - Resolving the explicit grid
66/// - Placing items (which also resolves the implicit grid)
67/// - Track (row/column) sizing
68/// - Alignment & Final item placement
69pub fn compute(
70 tree: &mut impl LayoutTree,
71 node: Node,
72 known_dimensions: Size<Option<f32>>,
73 parent_size: Size<Option<f32>>,
74 available_space: Size<AvailableSpace>,
75 run_mode: RunMode,
76) -> SizeAndBaselines {
77 let get_child_styles_iter = |node| tree.children(node).map(|child_node: &Node| tree.style(*child_node));
78 let style = tree.style(node).clone();
79 let child_styles_iter = get_child_styles_iter(node);
80
81 // 1. Resolve the explicit grid
82 // Exactly compute the number of rows and columns in the explicit grid.
83 let explicit_col_count = compute_explicit_grid_size_in_axis(&style, AbsoluteAxis::Horizontal);
84 let explicit_row_count = compute_explicit_grid_size_in_axis(&style, AbsoluteAxis::Vertical);
85
86 // 2. Implicit Grid: Estimate Track Counts
87 // Estimate the number of rows and columns in the implicit grid (= the entire grid)
88 // This is necessary as part of placement. Doing it early here is a perf optimisation to reduce allocations.
89 let (est_col_counts, est_row_counts) =
90 compute_grid_size_estimate(explicit_col_count, explicit_row_count, child_styles_iter);
91
92 // 2. Grid Item Placement
93 // Match items (children) to a definite grid position (row start/end and column start/end position)
94 let mut items = Vec::with_capacity(tree.child_count(node));
95 let mut cell_occupancy_matrix = CellOccupancyMatrix::with_track_counts(est_col_counts, est_row_counts);
96 let grid_auto_flow = style.grid_auto_flow;
97 let in_flow_children_iter = || {
98 tree.children(node)
99 .copied()
100 .enumerate()
101 .map(|(index, child_node)| (index, child_node, tree.style(child_node)))
102 .filter(|(_, _, style)| style.display != Display::None && style.position != Position::Absolute)
103 };
104 place_grid_items(&mut cell_occupancy_matrix, &mut items, in_flow_children_iter, grid_auto_flow);
105
106 // Extract track counts from previous step (auto-placement can expand the number of tracks)
107 let final_col_counts = *cell_occupancy_matrix.track_counts(AbsoluteAxis::Horizontal);
108 let final_row_counts = *cell_occupancy_matrix.track_counts(AbsoluteAxis::Vertical);
109
110 // 3. Initialize Tracks
111 // Initialize (explicit and implicit) grid tracks (and gutters)
112 // This resolves the min and max track sizing functions for all tracks and gutters
113 let mut columns = GridTrackVec::new();
114 let mut rows = GridTrackVec::new();
115 initialize_grid_tracks(
116 &mut columns,
117 final_col_counts,
118 &style.grid_template_columns,
119 &style.grid_auto_columns,
120 style.gap.width,
121 |column_index| cell_occupancy_matrix.column_is_occupied(column_index),
122 );
123 initialize_grid_tracks(
124 &mut rows,
125 final_row_counts,
126 &style.grid_template_rows,
127 &style.grid_auto_rows,
128 style.gap.height,
129 |row_index| cell_occupancy_matrix.row_is_occupied(row_index),
130 );
131
132 // 4. Compute "available grid space"
133 // https://www.w3.org/TR/css-grid-1/#available-grid-space
134 let padding = style.padding.resolve_or_zero(parent_size.width);
135 let border = style.border.resolve_or_zero(parent_size.width);
136 let margin = style.margin.resolve_or_zero(parent_size.width);
137 let aspect_ratio = style.aspect_ratio;
138 let min_size = style.min_size.maybe_resolve(parent_size).maybe_apply_aspect_ratio(aspect_ratio);
139 let max_size = style.max_size.maybe_resolve(parent_size).maybe_apply_aspect_ratio(aspect_ratio);
140 let size = style.size.maybe_resolve(parent_size).maybe_apply_aspect_ratio(aspect_ratio);
141
142 let constrained_available_space = size
143 .maybe_clamp(min_size, max_size)
144 .map(|size| size.map(AvailableSpace::Definite))
145 .unwrap_or(available_space.maybe_clamp(min_size, max_size));
146
147 let available_grid_space = Size {
148 width: constrained_available_space
149 .width
150 .map_definite_value(|space| space - padding.horizontal_axis_sum() - border.horizontal_axis_sum()),
151 height: constrained_available_space
152 .height
153 .map_definite_value(|space| space - padding.vertical_axis_sum() - border.vertical_axis_sum()),
154 };
155
156 let outer_node_size = size.maybe_clamp(min_size, max_size).or(parent_size.maybe_sub(margin.sum_axes()));
157 let mut inner_node_size = Size {
158 width: outer_node_size.width.map(|space| space - padding.horizontal_axis_sum() - border.horizontal_axis_sum()),
159 height: outer_node_size.height.map(|space| space - padding.vertical_axis_sum() - border.vertical_axis_sum()),
160 };
161
162 #[cfg(feature = "debug")]
163 NODE_LOGGER.labelled_debug_log("parent_size", parent_size);
164 #[cfg(feature = "debug")]
165 NODE_LOGGER.labelled_debug_log("outer_node_size", outer_node_size);
166 #[cfg(feature = "debug")]
167 NODE_LOGGER.labelled_debug_log("inner_node_size", inner_node_size);
168
169 // 5. Track Sizing
170
171 // Convert grid placements in origin-zero coordinates to indexes into the GridTrack (rows and columns) vectors
172 // This computation is relatively trivial, but it requires the final number of negative (implicit) tracks in
173 // each axis, and doing it up-front here means we don't have to keep repeating that calculation
174 resolve_item_track_indexes(&mut items, final_col_counts, final_row_counts);
175
176 // For each item, and in each axis, determine whether the item crosses any flexible (fr) tracks
177 // Record this as a boolean (per-axis) on each item for later use in the track-sizing algorithm
178 determine_if_item_crosses_flexible_tracks(&mut items, &columns, &rows);
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 style.grid_align_content(AbstractAxis::Block),
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 );
194 let initial_column_sum = columns.iter().map(|track| track.base_size).sum::<f32>();
195 inner_node_size.width = inner_node_size.width.or_else(|| initial_column_sum.into());
196
197 // Run track sizing algorithm for Block axis
198 track_sizing_algorithm(
199 tree,
200 AbstractAxis::Block,
201 min_size.get(AbstractAxis::Block),
202 max_size.get(AbstractAxis::Block),
203 style.grid_align_content(AbstractAxis::Inline),
204 available_grid_space,
205 inner_node_size,
206 &mut rows,
207 &mut columns,
208 &mut items,
209 |track: &GridTrack, _| Some(track.base_size),
210 );
211 let initial_row_sum = rows.iter().map(|track| track.base_size).sum::<f32>();
212 inner_node_size.height = inner_node_size.height.or_else(|| initial_row_sum.into());
213
214 // 6. Compute container size
215 let resolved_style_size = known_dimensions.or(style.size.maybe_resolve(parent_size));
216 let container_border_box = Size {
217 width: resolved_style_size
218 .get(AbstractAxis::Inline)
219 .unwrap_or_else(|| initial_column_sum + padding.horizontal_axis_sum() + border.horizontal_axis_sum()),
220 height: resolved_style_size
221 .get(AbstractAxis::Block)
222 .unwrap_or_else(|| initial_row_sum + padding.vertical_axis_sum() + border.vertical_axis_sum()),
223 };
224 let container_content_box = Size {
225 width: container_border_box.width - padding.horizontal_axis_sum() - border.horizontal_axis_sum(),
226 height: container_border_box.height - padding.vertical_axis_sum() - border.vertical_axis_sum(),
227 };
228
229 // If only the container's size has been requested
230 if run_mode == RunMode::ComputeSize {
231 return container_border_box.into();
232 }
233
234 // Re-run track sizing algorithm for Inline axis
235 track_sizing_algorithm(
236 tree,
237 AbstractAxis::Inline,
238 min_size.get(AbstractAxis::Inline),
239 max_size.get(AbstractAxis::Inline),
240 style.grid_align_content(AbstractAxis::Block),
241 available_grid_space,
242 inner_node_size,
243 &mut columns,
244 &mut rows,
245 &mut items,
246 |track: &GridTrack, _| Some(track.base_size),
247 );
248
249 // Re-run track sizing algorithm for Block axis
250 track_sizing_algorithm(
251 tree,
252 AbstractAxis::Block,
253 min_size.get(AbstractAxis::Block),
254 max_size.get(AbstractAxis::Block),
255 style.grid_align_content(AbstractAxis::Inline),
256 available_grid_space,
257 inner_node_size,
258 &mut rows,
259 &mut columns,
260 &mut items,
261 |track: &GridTrack, _| Some(track.base_size),
262 );
263
264 // 7. Resolve percentage track base sizes
265 // In the case of an indefinitely sized container these resolve to zero during the "Initialise Tracks" step
266 // and therefore need to be re-resolved here based on the content-sized content box of the container
267 if !available_grid_space.width.is_definite() {
268 for column in &mut columns {
269 let min: Option<f32> =
270 column.min_track_sizing_function.resolved_percentage_size(container_content_box.width);
271 let max: Option<f32> =
272 column.max_track_sizing_function.resolved_percentage_size(container_content_box.width);
273 column.base_size = column.base_size.maybe_clamp(min, max);
274 }
275 }
276 if !available_grid_space.height.is_definite() {
277 for row in &mut rows {
278 let min: Option<f32> = row.min_track_sizing_function.resolved_percentage_size(container_content_box.height);
279 let max: Option<f32> = row.max_track_sizing_function.resolved_percentage_size(container_content_box.height);
280 row.base_size = row.base_size.maybe_clamp(min, max);
281 }
282 }
283
284 // 8. Track Alignment
285
286 // Align columns
287 align_tracks(
288 container_content_box.get(AbstractAxis::Inline),
289 Line { start: padding.left, end: padding.right },
290 Line { start: border.left, end: border.right },
291 &mut columns,
292 style.justify_content.unwrap_or(AlignContent::Stretch),
293 );
294 // Align rows
295 align_tracks(
296 container_content_box.get(AbstractAxis::Block),
297 Line { start: padding.top, end: padding.bottom },
298 Line { start: border.top, end: border.bottom },
299 &mut rows,
300 style.align_content.unwrap_or(AlignContent::Stretch),
301 );
302
303 // 9. Size, Align, and Position Grid Items
304
305 // Sort items back into original order to allow them to be matched up with styles
306 items.sort_by_key(|item| item.source_order);
307
308 let container_alignment_styles = InBothAbsAxis { horizontal: style.justify_items, vertical: style.align_items };
309
310 // Position in-flow children (stored in items vector)
311 for (index, item) in items.iter().enumerate() {
312 let grid_area = Rect {
313 top: rows[item.row_indexes.start as usize + 1].offset,
314 bottom: rows[item.row_indexes.end as usize].offset,
315 left: columns[item.column_indexes.start as usize + 1].offset,
316 right: columns[item.column_indexes.end as usize].offset,
317 };
318 align_and_position_item(tree, item.node, index as u32, grid_area, container_alignment_styles);
319 }
320
321 // Position hidden and absolutely positioned children
322 let mut order = items.len() as u32;
323 (0..tree.child_count(node)).for_each(|index| {
324 let child = tree.child(node, index);
325 let child_style = tree.style(child);
326
327 // Position hidden child
328 if child_style.display == Display::None {
329 *tree.layout_mut(node) = Layout::with_order(order);
330 GenericAlgorithm::perform_layout(
331 tree,
332 child,
333 Size::NONE,
334 Size::NONE,
335 Size::MAX_CONTENT,
336 SizingMode::InherentSize,
337 );
338 order += 1;
339 return;
340 }
341
342 // Position absolutely positioned child
343 if child_style.position == Position::Absolute {
344 // Convert grid-col-{start/end} into Option's of indexes into the columns vector
345 // The Option is None if the style property is Auto and an unresolvable Span
346 let maybe_col_indexes = child_style
347 .grid_column
348 .into_origin_zero(final_col_counts.explicit)
349 .resolve_absolutely_positioned_grid_tracks()
350 .map(|maybe_grid_line| {
351 maybe_grid_line.map(|line: OriginZeroLine| line.into_track_vec_index(final_col_counts))
352 });
353 // Convert grid-row-{start/end} into Option's of indexes into the row vector
354 // The Option is None if the style property is Auto and an unresolvable Span
355 let maybe_row_indexes = child_style
356 .grid_row
357 .into_origin_zero(final_row_counts.explicit)
358 .resolve_absolutely_positioned_grid_tracks()
359 .map(|maybe_grid_line| {
360 maybe_grid_line.map(|line: OriginZeroLine| line.into_track_vec_index(final_row_counts))
361 });
362
363 let grid_area = Rect {
364 top: maybe_row_indexes.start.map(|index| rows[index].offset).unwrap_or(border.top),
365 bottom: maybe_row_indexes
366 .end
367 .map(|index| rows[index].offset)
368 .unwrap_or(container_border_box.height - border.bottom),
369 left: maybe_col_indexes.start.map(|index| columns[index].offset).unwrap_or(border.left),
370 right: maybe_col_indexes
371 .end
372 .map(|index| columns[index].offset)
373 .unwrap_or(container_border_box.width - border.right),
374 };
375 align_and_position_item(tree, child, order, grid_area, container_alignment_styles);
376 order += 1;
377 }
378 });
379
380 SizeAndBaselines { size: container_border_box, first_baselines: Point::NONE }
381}