taffy/compute/grid/
implicit_grid.rs

1//! This module is not required for spec compliance, but is used as a performance optimisation
2//! to reduce the number of allocations required when creating a grid.
3use crate::geometry::Line;
4use crate::style::{GenericGridPlacement, GridPlacement};
5use crate::{CheapCloneStr, GridItemStyle};
6use core::cmp::{max, min};
7
8use super::types::TrackCounts;
9use super::OriginZeroLine;
10
11/// Estimate the number of rows and columns in the grid
12/// This is used as a performance optimisation to pre-size vectors and reduce allocations. It also forms a necessary step
13/// in the auto-placement
14///   - The estimates for the explicit and negative implicit track counts are exact.
15///   - However, the estimates for the positive explicit track count is a lower bound as auto-placement can affect this
16///     in ways which are impossible to predict until the auto-placement algorithm is run.
17///
18/// Note that this function internally mixes use of grid track numbers and grid line numbers
19pub(crate) fn compute_grid_size_estimate<'a, S: GridItemStyle + 'a>(
20    explicit_col_count: u16,
21    explicit_row_count: u16,
22    child_styles_iter: impl Iterator<Item = S>,
23) -> (TrackCounts, TrackCounts) {
24    // Iterate over children, producing an estimate of the min and max grid lines (in origin-zero coordinates where)
25    // along with the span of each item
26    let (col_min, col_max, col_max_span, row_min, row_max, row_max_span) =
27        get_known_child_positions(child_styles_iter, explicit_col_count, explicit_row_count);
28
29    // Compute *track* count estimates for each axis from:
30    //   - The explicit track counts
31    //   - The origin-zero coordinate min and max grid line variables
32    let negative_implicit_inline_tracks = col_min.implied_negative_implicit_tracks();
33    let explicit_inline_tracks = explicit_col_count;
34    let mut positive_implicit_inline_tracks = col_max.implied_positive_implicit_tracks(explicit_col_count);
35    let negative_implicit_block_tracks = row_min.implied_negative_implicit_tracks();
36    let explicit_block_tracks = explicit_row_count;
37    let mut positive_implicit_block_tracks = row_max.implied_positive_implicit_tracks(explicit_row_count);
38
39    // In each axis, adjust positive track estimate if any items have a span that does not fit within
40    // the total number of tracks in the estimate
41    let tot_inline_tracks = negative_implicit_inline_tracks + explicit_inline_tracks + positive_implicit_inline_tracks;
42    if tot_inline_tracks < col_max_span {
43        positive_implicit_inline_tracks = col_max_span - explicit_inline_tracks - negative_implicit_inline_tracks;
44    }
45
46    let tot_block_tracks = negative_implicit_block_tracks + explicit_block_tracks + positive_implicit_block_tracks;
47    if tot_block_tracks < row_max_span {
48        positive_implicit_block_tracks = row_max_span - explicit_block_tracks - negative_implicit_block_tracks;
49    }
50
51    let column_counts =
52        TrackCounts::from_raw(negative_implicit_inline_tracks, explicit_inline_tracks, positive_implicit_inline_tracks);
53
54    let row_counts =
55        TrackCounts::from_raw(negative_implicit_block_tracks, explicit_block_tracks, positive_implicit_block_tracks);
56
57    (column_counts, row_counts)
58}
59
60/// Iterate over children, producing an estimate of the min and max grid *lines* along with the span of each item
61///
62/// Min and max grid lines are returned in origin-zero coordinates)
63/// The span is measured in tracks spanned
64fn get_known_child_positions<'a, S: GridItemStyle + 'a>(
65    children_iter: impl Iterator<Item = S>,
66    explicit_col_count: u16,
67    explicit_row_count: u16,
68) -> (OriginZeroLine, OriginZeroLine, u16, OriginZeroLine, OriginZeroLine, u16) {
69    let (mut col_min, mut col_max, mut col_max_span) = (OriginZeroLine(0), OriginZeroLine(0), 0);
70    let (mut row_min, mut row_max, mut row_max_span) = (OriginZeroLine(0), OriginZeroLine(0), 0);
71    children_iter.for_each(|child_style| {
72        // Note: that the children reference the lines in between (and around) the tracks not tracks themselves,
73        // and thus we must subtract 1 to get an accurate estimate of the number of tracks
74        let (child_col_min, child_col_max, child_col_span) =
75            child_min_line_max_line_span::<S::CustomIdent>(child_style.grid_column(), explicit_col_count);
76        let (child_row_min, child_row_max, child_row_span) =
77            child_min_line_max_line_span::<S::CustomIdent>(child_style.grid_row(), explicit_row_count);
78        col_min = min(col_min, child_col_min);
79        col_max = max(col_max, child_col_max);
80        col_max_span = max(col_max_span, child_col_span);
81        row_min = min(row_min, child_row_min);
82        row_max = max(row_max, child_row_max);
83        row_max_span = max(row_max_span, child_row_span);
84    });
85
86    (col_min, col_max, col_max_span, row_min, row_max, row_max_span)
87}
88
89/// Helper function for `compute_grid_size_estimate`
90/// Produces a conservative estimate of the greatest and smallest grid lines used by a single grid item
91///
92/// Values are returned in origin-zero coordinates
93#[inline]
94fn child_min_line_max_line_span<S: CheapCloneStr>(
95    line: Line<GridPlacement<S>>,
96    explicit_track_count: u16,
97) -> (OriginZeroLine, OriginZeroLine, u16) {
98    use GenericGridPlacement::*;
99
100    // 8.3.1. Grid Placement Conflict Handling
101    // A. If the placement for a grid item contains two lines, and the start line is further end-ward than the end line, swap the two lines.
102    // B. If the start line is equal to the end line, remove the end line.
103    // C. If the placement contains two spans, remove the one contributed by the end grid-placement property.
104    // D. If the placement contains only a span for a named line, replace it with a span of 1.
105
106    // Convert line into origin-zero coordinates before attempting to analyze
107    // We ignore named lines here as they are accounted for separately
108    let oz_line = line.into_origin_zero_ignoring_named(explicit_track_count);
109
110    let min = match (oz_line.start, oz_line.end) {
111        // Both tracks specified
112        (Line(track1), Line(track2)) => {
113            // See rules A and B above
114            if track1 == track2 {
115                track1
116            } else {
117                min(track1, track2)
118            }
119        }
120
121        // Start track specified
122        (Line(track), Auto) => track,
123        (Line(track), Span(_)) => track,
124
125        // End track specified
126        (Auto, Line(track)) => track,
127        (Span(span), Line(track)) => track - span,
128
129        // Only spans or autos
130        // We ignore spans here by returning 0 which never effect the estimate as these are accounted for separately
131        (Auto | Span(_), Auto | Span(_)) => OriginZeroLine(0),
132    };
133
134    let max = match (oz_line.start, oz_line.end) {
135        // Both tracks specified
136        (Line(track1), Line(track2)) => {
137            // See rules A and B above
138            if track1 == track2 {
139                track1 + 1
140            } else {
141                max(track1, track2)
142            }
143        }
144
145        // Start track specified
146        (Line(track), Auto) => track + 1,
147        (Line(track), Span(span)) => track + span,
148
149        // End track specified
150        (Auto, Line(track)) => track,
151        (Span(_), Line(track)) => track,
152
153        // Only spans or autos
154        // We ignore spans here by returning 0 which never effect the estimate as these are accounted for separately
155        (Auto | Span(_), Auto | Span(_)) => OriginZeroLine(0),
156    };
157
158    // Calculate span only for indefinitely placed items as we don't need for other items (whose required space will
159    // be taken into account by min and max)
160    let span = match (oz_line.start, oz_line.end) {
161        (Auto | Span(_), Auto | Span(_)) => oz_line.indefinite_span(),
162        _ => 1,
163    };
164
165    (min, max, span)
166}
167
168#[allow(clippy::bool_assert_comparison)]
169#[cfg(test)]
170mod tests {
171    mod test_child_min_max_line {
172        type S = String;
173        use super::super::child_min_line_max_line_span;
174        use super::super::OriginZeroLine;
175        use crate::geometry::Line;
176        use crate::style_helpers::*;
177
178        #[test]
179        fn child_min_max_line_auto() {
180            let (min_col, max_col, span) = child_min_line_max_line_span::<S>(Line { start: line(5), end: span(6) }, 6);
181            assert_eq!(min_col, OriginZeroLine(4));
182            assert_eq!(max_col, OriginZeroLine(10));
183            assert_eq!(span, 1);
184        }
185
186        #[test]
187        fn child_min_max_line_negative_track() {
188            let (min_col, max_col, span) = child_min_line_max_line_span::<S>(Line { start: line(-5), end: span(3) }, 6);
189            assert_eq!(min_col, OriginZeroLine(2));
190            assert_eq!(max_col, OriginZeroLine(5));
191            assert_eq!(span, 1);
192        }
193    }
194
195    mod test_initial_grid_sizing {
196        use super::super::compute_grid_size_estimate;
197        use crate::compute::grid::util::test_helpers::*;
198        use crate::style_helpers::*;
199
200        #[test]
201        fn explicit_grid_sizing_with_children() {
202            let explicit_col_count = 6;
203            let explicit_row_count = 8;
204            let child_styles = vec![
205                (line(1), span(2), line(2), auto()).into_grid_child(),
206                (line(-4), auto(), line(-2), auto()).into_grid_child(),
207            ];
208            let (inline, block) =
209                compute_grid_size_estimate(explicit_col_count, explicit_row_count, child_styles.iter());
210            assert_eq!(inline.negative_implicit, 0);
211            assert_eq!(inline.explicit, explicit_col_count);
212            assert_eq!(inline.positive_implicit, 0);
213            assert_eq!(block.negative_implicit, 0);
214            assert_eq!(block.explicit, explicit_row_count);
215            assert_eq!(block.positive_implicit, 0);
216        }
217
218        #[test]
219        fn negative_implicit_grid_sizing() {
220            let explicit_col_count = 4;
221            let explicit_row_count = 4;
222            let child_styles = vec![
223                (line(-6), span(2), line(-8), auto()).into_grid_child(),
224                (line(4), auto(), line(3), auto()).into_grid_child(),
225            ];
226            let (inline, block) =
227                compute_grid_size_estimate(explicit_col_count, explicit_row_count, child_styles.iter());
228            assert_eq!(inline.negative_implicit, 1);
229            assert_eq!(inline.explicit, explicit_col_count);
230            assert_eq!(inline.positive_implicit, 0);
231            assert_eq!(block.negative_implicit, 3);
232            assert_eq!(block.explicit, explicit_row_count);
233            assert_eq!(block.positive_implicit, 0);
234        }
235    }
236}
taffy/compute/grid/implicit_grid.rs

taffy/compute/grid/
implicit_grid.rs
