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, MAX_OZ_LINE, MIN_OZ_LINE};
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        let col_line = child_style.grid_column();
73        let row_line = child_style.grid_row();
74
75        // Note: that the children reference the lines in between (and around) the tracks not tracks themselves,
76        // and thus we must subtract 1 to get an accurate estimate of the number of tracks
77        let (child_col_min, child_col_max, child_col_span) =
78            child_min_line_max_line_span::<S::CustomIdent>(col_line, explicit_col_count);
79        let (child_row_min, child_row_max, child_row_span) =
80            child_min_line_max_line_span::<S::CustomIdent>(row_line, explicit_row_count);
81
82        col_min = min(col_min, child_col_min);
83        col_max = max(col_max, child_col_max);
84        col_max_span = max(col_max_span, child_col_span);
85        row_min = min(row_min, child_row_min);
86        row_max = max(row_max, child_row_max);
87        row_max_span = max(row_max_span, child_row_span);
88    });
89
90    (col_min, col_max, col_max_span, row_min, row_max, row_max_span)
91}
92
93/// Helper function for `compute_grid_size_estimate`
94/// Produces a conservative estimate of the greatest and smallest grid lines used by a single grid item
95///
96/// Values are returned in origin-zero coordinates
97#[inline]
98fn child_min_line_max_line_span<S: CheapCloneStr>(
99    line: Line<GridPlacement<S>>,
100    explicit_track_count: u16,
101) -> (OriginZeroLine, OriginZeroLine, u16) {
102    use GenericGridPlacement::*;
103
104    // 8.3.1. Grid Placement Conflict Handling
105    // 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.
106    // B. If the start line is equal to the end line, remove the end line.
107    // C. If the placement contains two spans, remove the one contributed by the end grid-placement property.
108    // D. If the placement contains only a span for a named line, replace it with a span of 1.
109
110    // Convert line into origin-zero coordinates before attempting to analyze
111    // We ignore named lines here as they are accounted for separately
112    let oz_line = line.into_origin_zero_ignoring_named(explicit_track_count);
113
114    let min = match (oz_line.start, oz_line.end) {
115        // Both tracks specified
116        (Line(track1), Line(track2)) => {
117            // See rules A and B above
118            if track1 == track2 {
119                track1
120            } else {
121                min(track1, track2)
122            }
123        }
124
125        // Start track specified
126        (Line(track), Auto) => track,
127        (Line(track), Span(_)) => track,
128
129        // End track specified
130        (Auto, Line(track)) => track,
131        (Span(span), Line(track)) => track - span,
132
133        // Only spans or autos
134        // We ignore spans here by returning 0 which never effect the estimate as these are accounted for separately
135        (Auto | Span(_), Auto | Span(_)) => OriginZeroLine(0),
136    };
137
138    let max = match (oz_line.start, oz_line.end) {
139        // Both tracks specified
140        (Line(track1), Line(track2)) => {
141            // See rules A and B above
142            if track1 == track2 {
143                track1 + 1
144            } else {
145                max(track1, track2)
146            }
147        }
148
149        // Start track specified
150        (Line(track), Auto) => track + 1,
151        (Line(track), Span(span)) => track + span,
152
153        // End track specified
154        (Auto, Line(track)) => track,
155        (Span(_), Line(track)) => track,
156
157        // Only spans or autos
158        // We ignore spans here by returning 0 which never effect the estimate as these are accounted for separately
159        (Auto | Span(_), Auto | Span(_)) => OriginZeroLine(0),
160    };
161
162    // Calculate span only for indefinitely placed items as we don't need for other items (whose required space will
163    // be taken into account by min and max)
164    let span = match (oz_line.start, oz_line.end) {
165        (Auto | Span(_), Auto | Span(_)) => oz_line.indefinite_span(),
166        _ => 1,
167    };
168
169    // Clamp the min and max lines into the limited grid so that the estimated implicit track counts
170    // stay within the maximum track limit (https://www.w3.org/TR/css-grid-1/#overlarge-grids).
171    // This matches the clamping of the actual item placements performed during placement.
172    let clamped_min = OriginZeroLine(min.0.max(MIN_OZ_LINE));
173    let clamped_max = OriginZeroLine(max.0.min(MAX_OZ_LINE));
174
175    (clamped_min, clamped_max, span)
176}
177
178#[allow(clippy::bool_assert_comparison)]
179#[cfg(test)]
180mod tests {
181    mod test_child_min_max_line {
182        type S = String;
183        use super::super::child_min_line_max_line_span;
184        use super::super::OriginZeroLine;
185        use crate::geometry::Line;
186        use crate::style_helpers::*;
187
188        #[test]
189        fn child_min_max_line_auto() {
190            let (min_col, max_col, span) = child_min_line_max_line_span::<S>(Line { start: line(5), end: span(6) }, 6);
191            assert_eq!(min_col, OriginZeroLine(4));
192            assert_eq!(max_col, OriginZeroLine(10));
193            assert_eq!(span, 1);
194        }
195
196        #[test]
197        fn child_min_max_line_negative_track() {
198            let (min_col, max_col, span) = child_min_line_max_line_span::<S>(Line { start: line(-5), end: span(3) }, 6);
199            assert_eq!(min_col, OriginZeroLine(2));
200            assert_eq!(max_col, OriginZeroLine(5));
201            assert_eq!(span, 1);
202        }
203    }
204
205    mod test_initial_grid_sizing {
206        use super::super::compute_grid_size_estimate;
207        use crate::compute::grid::util::test_helpers::*;
208        use crate::style_helpers::*;
209
210        #[test]
211        fn explicit_grid_sizing_with_children() {
212            let explicit_col_count = 6;
213            let explicit_row_count = 8;
214            let child_styles = [
215                (line(1), span(2), line(2), auto()).into_grid_child(),
216                (line(-4), auto(), line(-2), auto()).into_grid_child(),
217            ];
218            let (inline, block) =
219                compute_grid_size_estimate(explicit_col_count, explicit_row_count, child_styles.iter());
220            assert_eq!(inline.negative_implicit, 0);
221            assert_eq!(inline.explicit, explicit_col_count);
222            assert_eq!(inline.positive_implicit, 0);
223            assert_eq!(block.negative_implicit, 0);
224            assert_eq!(block.explicit, explicit_row_count);
225            assert_eq!(block.positive_implicit, 0);
226        }
227
228        #[test]
229        fn negative_implicit_grid_sizing() {
230            let explicit_col_count = 4;
231            let explicit_row_count = 4;
232            let child_styles = [
233                (line(-6), span(2), line(-8), auto()).into_grid_child(),
234                (line(4), auto(), line(3), auto()).into_grid_child(),
235            ];
236            let (inline, block) =
237                compute_grid_size_estimate(explicit_col_count, explicit_row_count, child_styles.iter());
238            assert_eq!(inline.negative_implicit, 1);
239            assert_eq!(inline.explicit, explicit_col_count);
240            assert_eq!(inline.positive_implicit, 0);
241            assert_eq!(block.negative_implicit, 3);
242            assert_eq!(block.explicit, explicit_row_count);
243            assert_eq!(block.positive_implicit, 0);
244        }
245    }
246}
taffy/compute/grid/implicit_grid.rs

taffy/compute/grid/
implicit_grid.rs
