tawasuyu/taffy

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::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(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(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(
95    line: Line<GridPlacement>,
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    let oz_line = line.into_origin_zero(explicit_track_count);
108
109    let min = match (oz_line.start, oz_line.end) {
110        // Both tracks specified
111        (Line(track1), Line(track2)) => {
112            // See rules A and B above
113            if track1 == track2 {
114                track1
115            } else {
116                min(track1, track2)
117            }
118        }
119
120        // Start track specified
121        (Line(track), Auto) => track,
122        (Line(track), Span(_)) => track,
123
124        // End track specified
125        (Auto, Line(track)) => track,
126        (Span(span), Line(track)) => track - span,
127
128        // Only spans or autos
129        // We ignore spans here by returning 0 which never effect the estimate as these are accounted for separately
130        (Auto | Span(_), Auto | Span(_)) => OriginZeroLine(0),
131    };
132
133    let max = match (oz_line.start, oz_line.end) {
134        // Both tracks specified
135        (Line(track1), Line(track2)) => {
136            // See rules A and B above
137            if track1 == track2 {
138                track1 + 1
139            } else {
140                max(track1, track2)
141            }
142        }
143
144        // Start track specified
145        (Line(track), Auto) => track + 1,
146        (Line(track), Span(span)) => track + span,
147
148        // End track specified
149        (Auto, Line(track)) => track,
150        (Span(_), Line(track)) => track,
151
152        // Only spans or autos
153        // We ignore spans here by returning 0 which never effect the estimate as these are accounted for separately
154        (Auto | Span(_), Auto | Span(_)) => OriginZeroLine(0),
155    };
156
157    // Calculate span only for indefinitely placed items as we don't need for other items (whose required space will
158    // be taken into account by min and max)
159    let span = match (line.start, line.end) {
160        (Auto | Span(_), Auto | Span(_)) => line.indefinite_span(),
161        _ => 1,
162    };
163
164    (min, max, span)
165}
166
167#[allow(clippy::bool_assert_comparison)]
168#[cfg(test)]
169mod tests {
170    mod test_child_min_max_line {
171        use super::super::child_min_line_max_line_span;
172        use super::super::OriginZeroLine;
173        use crate::geometry::Line;
174        use crate::style_helpers::*;
175
176        #[test]
177        fn child_min_max_line_auto() {
178            let (min_col, max_col, span) = child_min_line_max_line_span(Line { start: line(5), end: span(6) }, 6);
179            assert_eq!(min_col, OriginZeroLine(4));
180            assert_eq!(max_col, OriginZeroLine(10));
181            assert_eq!(span, 1);
182        }
183
184        #[test]
185        fn child_min_max_line_negative_track() {
186            let (min_col, max_col, span) = child_min_line_max_line_span(Line { start: line(-5), end: span(3) }, 6);
187            assert_eq!(min_col, OriginZeroLine(2));
188            assert_eq!(max_col, OriginZeroLine(5));
189            assert_eq!(span, 1);
190        }
191    }
192
193    mod test_initial_grid_sizing {
194        use super::super::compute_grid_size_estimate;
195        use crate::compute::grid::util::test_helpers::*;
196        use crate::style_helpers::*;
197
198        #[test]
199        fn explicit_grid_sizing_with_children() {
200            let explicit_col_count = 6;
201            let explicit_row_count = 8;
202            let child_styles = vec![
203                (line(1), span(2), line(2), auto()).into_grid_child(),
204                (line(-4), auto(), line(-2), auto()).into_grid_child(),
205            ];
206            let (inline, block) =
207                compute_grid_size_estimate(explicit_col_count, explicit_row_count, child_styles.iter());
208            assert_eq!(inline.negative_implicit, 0);
209            assert_eq!(inline.explicit, explicit_col_count);
210            assert_eq!(inline.positive_implicit, 0);
211            assert_eq!(block.negative_implicit, 0);
212            assert_eq!(block.explicit, explicit_row_count);
213            assert_eq!(block.positive_implicit, 0);
214        }
215
216        #[test]
217        fn negative_implicit_grid_sizing() {
218            let explicit_col_count = 4;
219            let explicit_row_count = 4;
220            let child_styles = vec![
221                (line(-6), span(2), line(-8), auto()).into_grid_child(),
222                (line(4), auto(), line(3), auto()).into_grid_child(),
223            ];
224            let (inline, block) =
225                compute_grid_size_estimate(explicit_col_count, explicit_row_count, child_styles.iter());
226            assert_eq!(inline.negative_implicit, 1);
227            assert_eq!(inline.explicit, explicit_col_count);
228            assert_eq!(inline.positive_implicit, 0);
229            assert_eq!(block.negative_implicit, 3);
230            assert_eq!(block.explicit, explicit_row_count);
231            assert_eq!(block.positive_implicit, 0);
232        }
233    }
234}