1use core::borrow::Borrow;
4
5use crate::geometry::{AbsoluteAxis, AbstractAxis, InBothAbsAxis};
6use crate::geometry::{Line, Point, Rect, Size};
7use crate::style::{AlignItems, AlignSelf, AvailableSpace, Overflow, Position};
8use crate::tree::{Layout, LayoutInput, LayoutOutput, LayoutPartialTreeExt, NodeId, RunMode, SizingMode};
9use crate::util::debug::debug_log;
10use crate::util::sys::{f32_max, GridTrackVec, Vec};
11use crate::util::MaybeMath;
12use crate::util::{MaybeResolve, ResolveOrZero};
13use crate::{
14 style_helpers::*, AlignContent, BoxGenerationMode, BoxSizing, CoreStyle, GridContainerStyle, GridItemStyle,
15 JustifyContent, LayoutGridContainer,
16};
17use alignment::{align_and_position_item, align_tracks};
18use explicit_grid::{compute_explicit_grid_size_in_axis, initialize_grid_tracks};
19use implicit_grid::compute_grid_size_estimate;
20use placement::place_grid_items;
21use track_sizing::{
22 determine_if_item_crosses_flexible_or_intrinsic_tracks, resolve_item_track_indexes, track_sizing_algorithm,
23};
24use types::{CellOccupancyMatrix, GridTrack};
25
26#[cfg(feature = "detailed_layout_info")]
27use types::{GridItem, GridTrackKind, TrackCounts};
28
29pub(crate) use types::{GridCoordinate, GridLine, OriginZeroLine};
30
31mod alignment;
32mod explicit_grid;
33mod implicit_grid;
34mod placement;
35mod track_sizing;
36mod types;
37mod util;
38
39pub fn compute_grid_layout(tree: &mut impl LayoutGridContainer, node: NodeId, inputs: LayoutInput) -> LayoutOutput {
46 let LayoutInput { known_dimensions, parent_size, available_space, run_mode, .. } = inputs;
47
48 let style = tree.get_grid_container_style(node);
49
50 let aspect_ratio = style.aspect_ratio();
53 let padding = style.padding().resolve_or_zero(parent_size.width);
54 let border = style.border().resolve_or_zero(parent_size.width);
55 let padding_border = padding + border;
56 let padding_border_size = padding_border.sum_axes();
57 let box_sizing_adjustment =
58 if style.box_sizing() == BoxSizing::ContentBox { padding_border_size } else { Size::ZERO };
59
60 let min_size = style
61 .min_size()
62 .maybe_resolve(parent_size)
63 .maybe_apply_aspect_ratio(aspect_ratio)
64 .maybe_add(box_sizing_adjustment);
65 let max_size = style
66 .max_size()
67 .maybe_resolve(parent_size)
68 .maybe_apply_aspect_ratio(aspect_ratio)
69 .maybe_add(box_sizing_adjustment);
70 let preferred_size = if inputs.sizing_mode == SizingMode::InherentSize {
71 style
72 .size()
73 .maybe_resolve(parent_size)
74 .maybe_apply_aspect_ratio(style.aspect_ratio())
75 .maybe_add(box_sizing_adjustment)
76 } else {
77 Size::NONE
78 };
79
80 let scrollbar_gutter = style.overflow().transpose().map(|overflow| match overflow {
84 Overflow::Scroll => style.scrollbar_width(),
85 _ => 0.0,
86 });
87 let mut content_box_inset = padding_border;
89 content_box_inset.right += scrollbar_gutter.x;
90 content_box_inset.bottom += scrollbar_gutter.y;
91
92 let align_content = style.align_content().unwrap_or(AlignContent::Stretch);
93 let justify_content = style.justify_content().unwrap_or(JustifyContent::Stretch);
94 let align_items = style.align_items();
95 let justify_items = style.justify_items();
96
97 let grid_template_columms = style.grid_template_columns();
100 let grid_template_rows = style.grid_template_rows();
101 let grid_auto_columms = style.grid_auto_columns();
102 let grid_auto_rows = style.grid_auto_rows();
103
104 let constrained_available_space = known_dimensions
105 .or(preferred_size)
106 .map(|size| size.map(AvailableSpace::Definite))
107 .unwrap_or(available_space)
108 .maybe_clamp(min_size, max_size)
109 .maybe_max(padding_border_size);
110
111 let available_grid_space = Size {
112 width: constrained_available_space
113 .width
114 .map_definite_value(|space| space - content_box_inset.horizontal_axis_sum()),
115 height: constrained_available_space
116 .height
117 .map_definite_value(|space| space - content_box_inset.vertical_axis_sum()),
118 };
119
120 let outer_node_size =
121 known_dimensions.or(preferred_size).maybe_clamp(min_size, max_size).maybe_max(padding_border_size);
122 let mut inner_node_size = Size {
123 width: outer_node_size.width.map(|space| space - content_box_inset.horizontal_axis_sum()),
124 height: outer_node_size.height.map(|space| space - content_box_inset.vertical_axis_sum()),
125 };
126
127 debug_log!("parent_size", dbg:parent_size);
128 debug_log!("outer_node_size", dbg:outer_node_size);
129 debug_log!("inner_node_size", dbg:inner_node_size);
130
131 if let (RunMode::ComputeSize, Some(width), Some(height)) = (run_mode, outer_node_size.width, outer_node_size.height)
132 {
133 return LayoutOutput::from_outer_size(Size { width, height });
134 }
135
136 let get_child_styles_iter =
137 |node| tree.child_ids(node).map(|child_node: NodeId| tree.get_grid_child_style(child_node));
138 let child_styles_iter = get_child_styles_iter(node);
139
140 let auto_fit_container_size = outer_node_size
145 .or(max_size)
146 .or(min_size)
147 .maybe_clamp(min_size, max_size)
148 .maybe_max(padding_border_size)
149 .maybe_sub(content_box_inset.sum_axes());
150
151 let explicit_col_count = compute_explicit_grid_size_in_axis(
153 &style,
154 grid_template_columms.borrow(),
155 auto_fit_container_size,
156 AbsoluteAxis::Horizontal,
157 );
158 let explicit_row_count = compute_explicit_grid_size_in_axis(
159 &style,
160 grid_template_rows.borrow(),
161 auto_fit_container_size,
162 AbsoluteAxis::Vertical,
163 );
164
165 let (est_col_counts, est_row_counts) =
169 compute_grid_size_estimate(explicit_col_count, explicit_row_count, child_styles_iter);
170
171 let mut items = Vec::with_capacity(tree.child_count(node));
174 let mut cell_occupancy_matrix = CellOccupancyMatrix::with_track_counts(est_col_counts, est_row_counts);
175 let in_flow_children_iter = || {
176 tree.child_ids(node)
177 .enumerate()
178 .map(|(index, child_node)| (index, child_node, tree.get_grid_child_style(child_node)))
179 .filter(|(_, _, style)| {
180 style.box_generation_mode() != BoxGenerationMode::None && style.position() != Position::Absolute
181 })
182 };
183 place_grid_items(
184 &mut cell_occupancy_matrix,
185 &mut items,
186 in_flow_children_iter,
187 style.grid_auto_flow(),
188 align_items.unwrap_or(AlignItems::Stretch),
189 justify_items.unwrap_or(AlignItems::Stretch),
190 );
191
192 let final_col_counts = *cell_occupancy_matrix.track_counts(AbsoluteAxis::Horizontal);
194 let final_row_counts = *cell_occupancy_matrix.track_counts(AbsoluteAxis::Vertical);
195
196 let mut columns = GridTrackVec::new();
200 let mut rows = GridTrackVec::new();
201 initialize_grid_tracks(
202 &mut columns,
203 final_col_counts,
204 grid_template_columms.borrow(),
205 grid_auto_columms.borrow(),
206 style.gap().width,
207 |column_index| cell_occupancy_matrix.column_is_occupied(column_index),
208 );
209 initialize_grid_tracks(
210 &mut rows,
211 final_row_counts,
212 grid_template_rows.borrow(),
213 grid_auto_rows.borrow(),
214 style.gap().height,
215 |row_index| cell_occupancy_matrix.row_is_occupied(row_index),
216 );
217
218 drop(grid_template_rows);
219 drop(grid_template_columms);
220 drop(grid_auto_rows);
221 drop(grid_auto_columms);
222 drop(style);
223
224 resolve_item_track_indexes(&mut items, final_col_counts, final_row_counts);
230
231 determine_if_item_crosses_flexible_or_intrinsic_tracks(&mut items, &columns, &rows);
234
235 let has_baseline_aligned_item = items.iter().any(|item| item.align_self == AlignSelf::Baseline);
237
238 track_sizing_algorithm(
240 tree,
241 AbstractAxis::Inline,
242 min_size.get(AbstractAxis::Inline),
243 max_size.get(AbstractAxis::Inline),
244 justify_content,
245 align_content,
246 available_grid_space,
247 inner_node_size,
248 &mut columns,
249 &mut rows,
250 &mut items,
251 |track: &GridTrack, parent_size: Option<f32>| track.max_track_sizing_function.definite_value(parent_size),
252 has_baseline_aligned_item,
253 );
254 let initial_column_sum = columns.iter().map(|track| track.base_size).sum::<f32>();
255 inner_node_size.width = inner_node_size.width.or_else(|| initial_column_sum.into());
256
257 items.iter_mut().for_each(|item| item.available_space_cache = None);
258
259 track_sizing_algorithm(
261 tree,
262 AbstractAxis::Block,
263 min_size.get(AbstractAxis::Block),
264 max_size.get(AbstractAxis::Block),
265 align_content,
266 justify_content,
267 available_grid_space,
268 inner_node_size,
269 &mut rows,
270 &mut columns,
271 &mut items,
272 |track: &GridTrack, _| Some(track.base_size),
273 false, );
275 let initial_row_sum = rows.iter().map(|track| track.base_size).sum::<f32>();
276 inner_node_size.height = inner_node_size.height.or_else(|| initial_row_sum.into());
277
278 debug_log!("initial_column_sum", dbg:initial_column_sum);
279 debug_log!(dbg: columns.iter().map(|track| track.base_size).collect::<Vec<_>>());
280 debug_log!("initial_row_sum", dbg:initial_row_sum);
281 debug_log!(dbg: rows.iter().map(|track| track.base_size).collect::<Vec<_>>());
282
283 let resolved_style_size = known_dimensions.or(preferred_size);
285 let container_border_box = Size {
286 width: resolved_style_size
287 .get(AbstractAxis::Inline)
288 .unwrap_or_else(|| initial_column_sum + content_box_inset.horizontal_axis_sum())
289 .maybe_clamp(min_size.width, max_size.width)
290 .max(padding_border_size.width),
291 height: resolved_style_size
292 .get(AbstractAxis::Block)
293 .unwrap_or_else(|| initial_row_sum + content_box_inset.vertical_axis_sum())
294 .maybe_clamp(min_size.height, max_size.height)
295 .max(padding_border_size.height),
296 };
297 let container_content_box = Size {
298 width: f32_max(0.0, container_border_box.width - content_box_inset.horizontal_axis_sum()),
299 height: f32_max(0.0, container_border_box.height - content_box_inset.vertical_axis_sum()),
300 };
301
302 if run_mode == RunMode::ComputeSize {
304 return LayoutOutput::from_outer_size(container_border_box);
305 }
306
307 if !available_grid_space.width.is_definite() {
311 for column in &mut columns {
312 let min: Option<f32> =
313 column.min_track_sizing_function.resolved_percentage_size(container_content_box.width);
314 let max: Option<f32> =
315 column.max_track_sizing_function.resolved_percentage_size(container_content_box.width);
316 column.base_size = column.base_size.maybe_clamp(min, max);
317 }
318 }
319 if !available_grid_space.height.is_definite() {
320 for row in &mut rows {
321 let min: Option<f32> = row.min_track_sizing_function.resolved_percentage_size(container_content_box.height);
322 let max: Option<f32> = row.max_track_sizing_function.resolved_percentage_size(container_content_box.height);
323 row.base_size = row.base_size.maybe_clamp(min, max);
324 }
325 }
326
327 let mut rerun_column_sizing;
332
333 let has_percentage_column = columns.iter().any(|track| track.uses_percentage());
334 let parent_width_indefinite = !available_space.width.is_definite();
335 rerun_column_sizing = parent_width_indefinite && has_percentage_column;
336
337 if !rerun_column_sizing {
338 let min_content_contribution_changed =
339 items.iter_mut().filter(|item| item.crosses_intrinsic_column).any(|item| {
340 let available_space = item.available_space(
341 AbstractAxis::Inline,
342 &rows,
343 inner_node_size.height,
344 |track: &GridTrack, _| Some(track.base_size),
345 );
346 let new_min_content_contribution =
347 item.min_content_contribution(AbstractAxis::Inline, tree, available_space, inner_node_size);
348
349 let has_changed = Some(new_min_content_contribution) != item.min_content_contribution_cache.width;
350
351 item.available_space_cache = Some(available_space);
352 item.min_content_contribution_cache.width = Some(new_min_content_contribution);
353 item.max_content_contribution_cache.width = None;
354 item.minimum_contribution_cache.width = None;
355
356 has_changed
357 });
358 rerun_column_sizing = min_content_contribution_changed;
359 } else {
360 items.iter_mut().for_each(|item| {
362 item.available_space_cache = None;
363 item.min_content_contribution_cache.width = None;
364 item.max_content_contribution_cache.width = None;
365 item.minimum_contribution_cache.width = None;
366 });
367 }
368
369 if rerun_column_sizing {
370 track_sizing_algorithm(
372 tree,
373 AbstractAxis::Inline,
374 min_size.get(AbstractAxis::Inline),
375 max_size.get(AbstractAxis::Inline),
376 justify_content,
377 align_content,
378 available_grid_space,
379 inner_node_size,
380 &mut columns,
381 &mut rows,
382 &mut items,
383 |track: &GridTrack, _| Some(track.base_size),
384 has_baseline_aligned_item,
385 );
386
387 let mut rerun_row_sizing;
392
393 let has_percentage_row = rows.iter().any(|track| track.uses_percentage());
394 let parent_height_indefinite = !available_space.height.is_definite();
395 rerun_row_sizing = parent_height_indefinite && has_percentage_row;
396
397 if !rerun_row_sizing {
398 let min_content_contribution_changed =
399 items.iter_mut().filter(|item| item.crosses_intrinsic_column).any(|item| {
400 let available_space = item.available_space(
401 AbstractAxis::Block,
402 &columns,
403 inner_node_size.width,
404 |track: &GridTrack, _| Some(track.base_size),
405 );
406 let new_min_content_contribution =
407 item.min_content_contribution(AbstractAxis::Block, tree, available_space, inner_node_size);
408
409 let has_changed = Some(new_min_content_contribution) != item.min_content_contribution_cache.height;
410
411 item.available_space_cache = Some(available_space);
412 item.min_content_contribution_cache.height = Some(new_min_content_contribution);
413 item.max_content_contribution_cache.height = None;
414 item.minimum_contribution_cache.height = None;
415
416 has_changed
417 });
418 rerun_row_sizing = min_content_contribution_changed;
419 } else {
420 items.iter_mut().for_each(|item| {
421 item.available_space_cache = None;
423 item.min_content_contribution_cache.height = None;
424 item.max_content_contribution_cache.height = None;
425 item.minimum_contribution_cache.height = None;
426 });
427 }
428
429 if rerun_row_sizing {
430 track_sizing_algorithm(
432 tree,
433 AbstractAxis::Block,
434 min_size.get(AbstractAxis::Block),
435 max_size.get(AbstractAxis::Block),
436 align_content,
437 justify_content,
438 available_grid_space,
439 inner_node_size,
440 &mut rows,
441 &mut columns,
442 &mut items,
443 |track: &GridTrack, _| Some(track.base_size),
444 false, );
446 }
447 }
448
449 align_tracks(
453 container_content_box.get(AbstractAxis::Inline),
454 Line { start: padding.left, end: padding.right },
455 Line { start: border.left, end: border.right },
456 &mut columns,
457 justify_content,
458 );
459 align_tracks(
461 container_content_box.get(AbstractAxis::Block),
462 Line { start: padding.top, end: padding.bottom },
463 Line { start: border.top, end: border.bottom },
464 &mut rows,
465 align_content,
466 );
467
468 #[cfg_attr(not(feature = "content_size"), allow(unused_mut))]
471 let mut item_content_size_contribution = Size::ZERO;
472
473 items.sort_by_key(|item| item.source_order);
475
476 let container_alignment_styles = InBothAbsAxis { horizontal: justify_items, vertical: align_items };
477
478 for (index, item) in items.iter_mut().enumerate() {
480 let grid_area = Rect {
481 top: rows[item.row_indexes.start as usize + 1].offset,
482 bottom: rows[item.row_indexes.end as usize].offset,
483 left: columns[item.column_indexes.start as usize + 1].offset,
484 right: columns[item.column_indexes.end as usize].offset,
485 };
486 #[cfg_attr(not(feature = "content_size"), allow(unused_variables))]
487 let (content_size_contribution, y_position, height) = align_and_position_item(
488 tree,
489 item.node,
490 index as u32,
491 grid_area,
492 container_alignment_styles,
493 item.baseline_shim,
494 );
495 item.y_position = y_position;
496 item.height = height;
497
498 #[cfg(feature = "content_size")]
499 {
500 item_content_size_contribution = item_content_size_contribution.f32_max(content_size_contribution);
501 }
502 }
503
504 let mut order = items.len() as u32;
506 (0..tree.child_count(node)).for_each(|index| {
507 let child = tree.get_child_id(node, index);
508 let child_style = tree.get_grid_child_style(child);
509
510 if child_style.box_generation_mode() == BoxGenerationMode::None {
512 drop(child_style);
513 tree.set_unrounded_layout(child, &Layout::with_order(order));
514 tree.perform_child_layout(
515 child,
516 Size::NONE,
517 Size::NONE,
518 Size::MAX_CONTENT,
519 SizingMode::InherentSize,
520 Line::FALSE,
521 );
522 order += 1;
523 return;
524 }
525
526 if child_style.position() == Position::Absolute {
528 let maybe_col_indexes = child_style
531 .grid_column()
532 .into_origin_zero(final_col_counts.explicit)
533 .resolve_absolutely_positioned_grid_tracks()
534 .map(|maybe_grid_line| {
535 maybe_grid_line.map(|line: OriginZeroLine| line.into_track_vec_index(final_col_counts))
536 });
537 let maybe_row_indexes = child_style
540 .grid_row()
541 .into_origin_zero(final_row_counts.explicit)
542 .resolve_absolutely_positioned_grid_tracks()
543 .map(|maybe_grid_line| {
544 maybe_grid_line.map(|line: OriginZeroLine| line.into_track_vec_index(final_row_counts))
545 });
546
547 let grid_area = Rect {
548 top: maybe_row_indexes.start.map(|index| rows[index].offset).unwrap_or(border.top),
549 bottom: maybe_row_indexes
550 .end
551 .map(|index| rows[index].offset)
552 .unwrap_or(container_border_box.height - border.bottom - scrollbar_gutter.y),
553 left: maybe_col_indexes.start.map(|index| columns[index].offset).unwrap_or(border.left),
554 right: maybe_col_indexes
555 .end
556 .map(|index| columns[index].offset)
557 .unwrap_or(container_border_box.width - border.right - scrollbar_gutter.x),
558 };
559 drop(child_style);
560
561 #[cfg_attr(not(feature = "content_size"), allow(unused_variables))]
563 let (content_size_contribution, _, _) =
564 align_and_position_item(tree, child, order, grid_area, container_alignment_styles, 0.0);
565 #[cfg(feature = "content_size")]
566 {
567 item_content_size_contribution = item_content_size_contribution.f32_max(content_size_contribution);
568 }
569
570 order += 1;
571 }
572 });
573
574 #[cfg(feature = "detailed_layout_info")]
576 tree.set_detailed_grid_info(
577 node,
578 DetailedGridInfo {
579 rows: DetailedGridTracksInfo::from_grid_tracks_and_track_count(final_row_counts, rows),
580 columns: DetailedGridTracksInfo::from_grid_tracks_and_track_count(final_col_counts, columns),
581 items: items.iter().map(DetailedGridItemsInfo::from_grid_item).collect(),
582 },
583 );
584
585 if items.is_empty() {
587 return LayoutOutput::from_outer_size(container_border_box);
588 }
589
590 let grid_container_baseline: f32 = {
592 items.sort_by_key(|item| item.row_indexes.start);
594
595 let first_row = items[0].row_indexes.start;
597
598 let first_row_items = &items[0..].split(|item| item.row_indexes.start != first_row).next().unwrap();
600
601 let row_has_baseline_item = first_row_items.iter().any(|item| item.align_self == AlignSelf::Baseline);
603
604 let item = if row_has_baseline_item {
605 first_row_items.iter().find(|item| item.align_self == AlignSelf::Baseline).unwrap()
606 } else {
607 &first_row_items[0]
608 };
609
610 item.y_position + item.baseline.unwrap_or(item.height)
611 };
612
613 LayoutOutput::from_sizes_and_baselines(
614 container_border_box,
615 item_content_size_contribution,
616 Point { x: None, y: Some(grid_container_baseline) },
617 )
618}
619
620#[derive(Debug, Clone, PartialEq)]
622#[cfg(feature = "detailed_layout_info")]
623pub struct DetailedGridInfo {
624 pub rows: DetailedGridTracksInfo,
626 pub columns: DetailedGridTracksInfo,
628 pub items: Vec<DetailedGridItemsInfo>,
630}
631
632#[derive(Debug, Clone, PartialEq)]
634#[cfg(feature = "detailed_layout_info")]
635pub struct DetailedGridTracksInfo {
636 pub negative_implicit_tracks: u16,
638 pub explicit_tracks: u16,
640 pub positive_implicit_tracks: u16,
642
643 pub gutters: Vec<f32>,
645 pub sizes: Vec<f32>,
647}
648
649#[cfg(feature = "detailed_layout_info")]
650impl DetailedGridTracksInfo {
651 #[inline(always)]
653 fn grid_track_base_size_of_kind(grid_tracks: &[GridTrack], kind: GridTrackKind) -> Vec<f32> {
654 grid_tracks
655 .iter()
656 .filter_map(|track| match track.kind == kind {
657 true => Some(track.base_size),
658 false => None,
659 })
660 .collect()
661 }
662
663 fn gutters_from_grid_track_layout(grid_tracks: &[GridTrack]) -> Vec<f32> {
665 DetailedGridTracksInfo::grid_track_base_size_of_kind(grid_tracks, GridTrackKind::Gutter)
666 }
667
668 fn sizes_from_grid_track_layout(grid_tracks: &[GridTrack]) -> Vec<f32> {
670 DetailedGridTracksInfo::grid_track_base_size_of_kind(grid_tracks, GridTrackKind::Track)
671 }
672
673 fn from_grid_tracks_and_track_count(track_count: TrackCounts, grid_tracks: Vec<GridTrack>) -> Self {
675 DetailedGridTracksInfo {
676 negative_implicit_tracks: track_count.negative_implicit,
677 explicit_tracks: track_count.explicit,
678 positive_implicit_tracks: track_count.positive_implicit,
679 gutters: DetailedGridTracksInfo::gutters_from_grid_track_layout(&grid_tracks),
680 sizes: DetailedGridTracksInfo::sizes_from_grid_track_layout(&grid_tracks),
681 }
682 }
683}
684
685#[derive(Debug, Clone, PartialEq)]
690#[cfg(feature = "detailed_layout_info")]
691pub struct DetailedGridItemsInfo {
692 pub row_start: u16,
694 pub row_end: u16,
696 pub column_start: u16,
698 pub column_end: u16,
700}
701
702#[cfg(feature = "detailed_layout_info")]
704impl DetailedGridItemsInfo {
705 #[inline(always)]
707 fn from_grid_item(grid_item: &GridItem) -> Self {
708 #[inline(always)]
710 fn to_one_indexed_grid_line(grid_track_index: u16) -> u16 {
711 grid_track_index / 2 + 1
712 }
713
714 DetailedGridItemsInfo {
715 row_start: to_one_indexed_grid_line(grid_item.row_indexes.start),
716 row_end: to_one_indexed_grid_line(grid_item.row_indexes.end),
717 column_start: to_one_indexed_grid_line(grid_item.column_indexes.start),
718 column_end: to_one_indexed_grid_line(grid_item.column_indexes.end),
719 }
720 }
721}