taffy/compute/grid/
placement.rs

1//! Implements placing items in the grid and resolving the implicit grid.
2//! <https://www.w3.org/TR/css-grid-1/#placement>
3use super::types::{CellOccupancyMatrix, CellOccupancyState, GridItem};
4use super::{NamedLineResolver, OriginZeroLine, MAX_OZ_LINE, MIN_OZ_LINE};
5use crate::geometry::Line;
6use crate::geometry::{AbsoluteAxis, InBothAbsAxis};
7use crate::style::{AlignItems, GridAutoFlow, OriginZeroGridPlacement};
8use crate::tree::NodeId;
9use crate::util::sys::Vec;
10use crate::{CoreStyle, GridItemStyle};
11
12#[inline]
13/// Advances the cursor by one track.
14fn advance_position(position: OriginZeroLine) -> OriginZeroLine {
15    OriginZeroLine(position.0.saturating_add(1))
16}
17
18#[inline]
19/// Resolves an indefinite span starting at `position`.
20fn resolve_indefinite_grid_span(position: OriginZeroLine, span: u16) -> Line<OriginZeroLine> {
21    let position = position.0 as i32;
22    let span = span as i32;
23    let line = |value: i32| OriginZeroLine(value.clamp(i16::MIN as i32, i16::MAX as i32) as i16);
24    Line { start: line(position), end: line(position + span) }
25}
26
27/// 8.5. Grid Item Placement Algorithm
28/// Place items into the grid, generating new rows/column into the implicit grid as required
29///
30/// [Specification](https://www.w3.org/TR/css-grid-2/#auto-placement-algo)
31#[allow(clippy::too_many_arguments)]
32pub(super) fn place_grid_items<'a, S, ChildIter>(
33    cell_occupancy_matrix: &mut CellOccupancyMatrix,
34    items: &mut Vec<GridItem>,
35    children_iter: impl Fn() -> ChildIter,
36    grid_auto_flow: GridAutoFlow,
37    align_items: AlignItems,
38    justify_items: AlignItems,
39    named_line_resolver: &NamedLineResolver<<S as CoreStyle>::CustomIdent>,
40) where
41    S: GridItemStyle + 'a,
42    ChildIter: Iterator<Item = (usize, NodeId, S)>,
43{
44    let primary_axis = grid_auto_flow.primary_axis();
45    let secondary_axis = primary_axis.other_axis();
46    let explicit_col_count = cell_occupancy_matrix.track_counts(AbsoluteAxis::Horizontal).explicit;
47
48    let map_child_style_to_origin_zero_placement = {
49        let explicit_row_count = cell_occupancy_matrix.track_counts(AbsoluteAxis::Vertical).explicit;
50        move |(index, node, style): (usize, NodeId, S)| -> (_, _, _, S) {
51            let origin_zero_placement = InBothAbsAxis {
52                horizontal: named_line_resolver
53                    .resolve_column_names(&style.grid_column())
54                    .map(|placement| placement.into_origin_zero_placement(explicit_col_count)),
55                vertical: named_line_resolver
56                    .resolve_row_names(&style.grid_row())
57                    .map(|placement| placement.into_origin_zero_placement(explicit_row_count)),
58            };
59            (index, node, origin_zero_placement, style)
60        }
61    };
62
63    // 1. Place children with definite positions
64    let mut idx = 0;
65    children_iter()
66        .map(map_child_style_to_origin_zero_placement)
67        .filter(|(_, _, placement, _)| placement.horizontal.is_definite() && placement.vertical.is_definite())
68        .for_each(|(index, child_node, child_placement, style)| {
69            idx += 1;
70            #[cfg(test)]
71            println!("Definite Item {idx}\n==============");
72
73            let (row_span, col_span) = place_definite_grid_item(child_placement, primary_axis);
74            record_grid_placement(
75                cell_occupancy_matrix,
76                items,
77                child_node,
78                index,
79                style,
80                align_items,
81                justify_items,
82                primary_axis,
83                row_span,
84                col_span,
85                CellOccupancyState::DefinitelyPlaced,
86            );
87        });
88
89    // 2. Place remaining children with definite secondary axis positions
90    let mut idx = 0;
91    children_iter()
92        .map(map_child_style_to_origin_zero_placement)
93        .filter(|(_, _, placement, _)| {
94            placement.get(secondary_axis).is_definite() && !placement.get(primary_axis).is_definite()
95        })
96        .for_each(|(index, child_node, child_placement, style)| {
97            idx += 1;
98            #[cfg(test)]
99            println!("Definite Secondary Item {idx}\n==============");
100
101            let (primary_span, secondary_span) =
102                place_definite_secondary_axis_item(&*cell_occupancy_matrix, child_placement, grid_auto_flow);
103
104            record_grid_placement(
105                cell_occupancy_matrix,
106                items,
107                child_node,
108                index,
109                style,
110                align_items,
111                justify_items,
112                primary_axis,
113                primary_span,
114                secondary_span,
115                CellOccupancyState::AutoPlaced,
116            );
117        });
118
119    // 3. Determine the number of columns in the implicit grid
120    // By the time we get to this point in the execution, this is actually already accounted for:
121    //
122    // 3.1 Start with the columns from the explicit grid
123    //        => Handled by grid size estimate which is used to pre-size the GridOccupancyMatrix
124    //
125    // 3.2 Among all the items with a definite column position (explicitly positioned items, items positioned in the previous step,
126    //     and items not yet positioned but with a definite column) add columns to the beginning and end of the implicit grid as necessary
127    //     to accommodate those items.
128    //        => Handled by expand_to_fit_range which expands the GridOccupancyMatrix as necessary
129    //            -> Called by mark_area_as
130    //            -> Called by record_grid_placement
131    //
132    // 3.3 If the largest column span among all the items without a definite column position is larger than the width of
133    //     the implicit grid, add columns to the end of the implicit grid to accommodate that column span.
134    //        => Handled by grid size estimate which is used to pre-size the GridOccupancyMatrix
135
136    // 4. Position the remaining grid items
137    // (which either have definite position only in the secondary axis or indefinite positions in both axis)
138    let primary_axis = grid_auto_flow.primary_axis();
139    let secondary_axis = primary_axis.other_axis();
140    let primary_axis_grid_start_line = cell_occupancy_matrix.track_counts(primary_axis).implicit_start_line();
141    let secondary_axis_grid_start_line = cell_occupancy_matrix.track_counts(secondary_axis).implicit_start_line();
142    let grid_start_position = (primary_axis_grid_start_line, secondary_axis_grid_start_line);
143    let mut grid_position = grid_start_position;
144    let mut idx = 0;
145    children_iter()
146        .map(map_child_style_to_origin_zero_placement)
147        .filter(|(_, _, placement, _)| !placement.get(secondary_axis).is_definite())
148        .for_each(|(index, child_node, child_placement, style)| {
149            idx += 1;
150            #[cfg(test)]
151            println!("\nAuto Item {idx}\n==============");
152
153            // Compute placement
154            let (primary_span, secondary_span) = place_indefinitely_positioned_item(
155                &*cell_occupancy_matrix,
156                child_placement,
157                grid_auto_flow,
158                grid_position,
159            );
160
161            // Record item
162            record_grid_placement(
163                cell_occupancy_matrix,
164                items,
165                child_node,
166                index,
167                style,
168                align_items,
169                justify_items,
170                primary_axis,
171                primary_span,
172                secondary_span,
173                CellOccupancyState::AutoPlaced,
174            );
175
176            // If using the "dense" placement algorithm then reset the grid position back to grid_start_position ready for the next item
177            // Otherwise set it to the position of the current item so that the next item it placed after it.
178            grid_position = match grid_auto_flow.is_dense() {
179                true => grid_start_position,
180                false => (primary_span.end, secondary_span.start),
181            };
182        });
183}
184
185/// 8.5. Grid Item Placement Algorithm
186/// Place a single definitely placed item into the grid
187fn place_definite_grid_item(
188    placement: InBothAbsAxis<Line<OriginZeroGridPlacement>>,
189    primary_axis: AbsoluteAxis,
190) -> (Line<OriginZeroLine>, Line<OriginZeroLine>) {
191    // Resolve spans to tracks
192    let primary_span = placement.get(primary_axis).resolve_definite_grid_lines();
193    let secondary_span = placement.get(primary_axis.other_axis()).resolve_definite_grid_lines();
194
195    (primary_span, secondary_span)
196}
197
198/// 8.5. Grid Item Placement Algorithm
199/// Step 2. Place remaining children with definite secondary axis positions
200fn place_definite_secondary_axis_item(
201    cell_occupancy_matrix: &CellOccupancyMatrix,
202    placement: InBothAbsAxis<Line<OriginZeroGridPlacement>>,
203    auto_flow: GridAutoFlow,
204) -> (Line<OriginZeroLine>, Line<OriginZeroLine>) {
205    let primary_axis = auto_flow.primary_axis();
206    let secondary_axis = primary_axis.other_axis();
207    let primary_axis_grid_start_line = cell_occupancy_matrix.track_counts(primary_axis).implicit_start_line();
208
209    let secondary_axis_placement = placement.get(secondary_axis).resolve_definite_grid_lines();
210    let starting_position = match auto_flow.is_dense() {
211        true => primary_axis_grid_start_line,
212        false => cell_occupancy_matrix
213            .last_of_type(primary_axis, secondary_axis_placement.start, CellOccupancyState::AutoPlaced)
214            .unwrap_or(primary_axis_grid_start_line),
215    };
216    let primary_axis_span = placement.get(primary_axis).indefinite_span();
217
218    let mut position: OriginZeroLine = starting_position;
219    loop {
220        let primary_axis_placement = resolve_indefinite_grid_span(position, primary_axis_span);
221
222        let collision = cell_occupancy_matrix.line_area_collision_jump(
223            primary_axis,
224            primary_axis_placement,
225            secondary_axis_placement,
226        );
227
228        match collision {
229            None => return (primary_axis_placement, secondary_axis_placement),
230            Some(next_position) => position = next_position,
231        }
232    }
233}
234
235/// 8.5. Grid Item Placement Algorithm
236/// Step 4. Position the remaining grid items.
237fn place_indefinitely_positioned_item(
238    cell_occupancy_matrix: &CellOccupancyMatrix,
239    placement: InBothAbsAxis<Line<OriginZeroGridPlacement>>,
240    auto_flow: GridAutoFlow,
241    grid_position: (OriginZeroLine, OriginZeroLine),
242) -> (Line<OriginZeroLine>, Line<OriginZeroLine>) {
243    let primary_axis = auto_flow.primary_axis();
244    let secondary_axis = primary_axis.other_axis();
245
246    let primary_placement_style = placement.get(primary_axis);
247    let secondary_placement_style = placement.get(secondary_axis);
248
249    let secondary_span = secondary_placement_style.indefinite_span();
250    let has_definite_primary_axis_position = primary_placement_style.is_definite();
251    let primary_axis_grid_start_line = cell_occupancy_matrix.track_counts(primary_axis).implicit_start_line();
252    let primary_axis_grid_end_line = cell_occupancy_matrix.track_counts(primary_axis).implicit_end_line();
253    let secondary_axis_grid_start_line = cell_occupancy_matrix.track_counts(secondary_axis).implicit_start_line();
254
255    let (mut primary_idx, mut secondary_idx) = grid_position;
256
257    if has_definite_primary_axis_position {
258        let primary_span = primary_placement_style.resolve_definite_grid_lines();
259
260        // Compute secondary axis starting position for search
261        secondary_idx = match auto_flow.is_dense() {
262            // If auto-flow is dense then we always search from the first track
263            true => secondary_axis_grid_start_line,
264            false => {
265                if primary_span.start < primary_idx {
266                    advance_position(secondary_idx)
267                } else {
268                    secondary_idx
269                }
270            }
271        };
272
273        // Item has fixed primary axis position: so we simply increment the secondary axis position
274        // until we find a space that the item fits in
275        loop {
276            let secondary_span = resolve_indefinite_grid_span(secondary_idx, secondary_span);
277
278            // If area is occupied, jump the index past the collision and try again
279            let collision =
280                cell_occupancy_matrix.line_area_collision_jump(secondary_axis, secondary_span, primary_span);
281            if let Some(next_position) = collision {
282                secondary_idx = next_position;
283                continue;
284            }
285
286            // Once we find a free space, return that position
287            return (primary_span, secondary_span);
288        }
289    } else {
290        let primary_span = primary_placement_style.indefinite_span();
291
292        // Whether the item spans every track in the primary axis. Such an item can only be
293        // placed at the primary axis grid start, in a stripe of entirely unoccupied tracks.
294        let spans_all_primary_tracks = primary_span as usize >= cell_occupancy_matrix.track_counts(primary_axis).len();
295
296        // Item does not have any fixed axis, so we search along the primary axis until we hit the end of the already
297        // existent tracks, and then we reset the primary axis back to zero and increment the secondary axis index.
298        // We continue in this vein until we find a space that the item fits in.
299        loop {
300            let primary_span = resolve_indefinite_grid_span(primary_idx, primary_span);
301            let secondary_span = resolve_indefinite_grid_span(secondary_idx, secondary_span);
302
303            // If the primary index is out of bounds, then increment the secondary index and reset the primary
304            // index back to the start of the grid
305            let primary_out_of_bounds = primary_span.end > primary_axis_grid_end_line;
306            if primary_out_of_bounds {
307                // If the span is out of bounds even at the search start position then it can never fit,
308                // as searching only ever moves the span further away from the start of the grid. Bail out
309                // and let `record_grid_placement` clamp the placement into the limited grid
310                if primary_idx == primary_axis_grid_start_line {
311                    return (primary_span, secondary_span);
312                }
313                secondary_idx = advance_position(secondary_idx);
314                primary_idx = primary_axis_grid_start_line;
315                continue;
316            }
317
318            // If the item spans every primary axis track, it fits if and only if all of the
319            // secondary axis tracks it spans are entirely unoccupied. Jump the secondary index
320            // past any non-empty tracks in the spanned stripe.
321            if spans_all_primary_tracks {
322                match cell_occupancy_matrix.occupied_track_jump(secondary_axis, secondary_span) {
323                    Some(next_position) => {
324                        secondary_idx = next_position;
325                        primary_idx = primary_axis_grid_start_line;
326                        continue;
327                    }
328                    None => return (primary_span, secondary_span),
329                }
330            }
331
332            // If area is occupied, jump the primary index past the collision and try again
333            let collision = cell_occupancy_matrix.line_area_collision_jump(primary_axis, primary_span, secondary_span);
334            if let Some(next_position) = collision {
335                primary_idx = next_position;
336                continue;
337            }
338
339            // Once we find a free space that's in bounds, return that position
340            return (primary_span, secondary_span);
341        }
342    }
343}
344
345/// Clamp a placement into the limited grid, preserving a span of at least 1 track.
346/// Items placed outside of the limited grid are clamped into it.
347///
348/// See: <https://www.w3.org/TR/css-grid-1/#overlarge-grids>
349fn clamp_span_to_limited_grid(span: Line<OriginZeroLine>) -> Line<OriginZeroLine> {
350    let start = span.start.0.clamp(MIN_OZ_LINE, MAX_OZ_LINE - 1);
351    let end = span.end.0.clamp(start + 1, MAX_OZ_LINE);
352    Line { start: OriginZeroLine(start), end: OriginZeroLine(end) }
353}
354
355/// Record the grid item in both CellOccupancyMatric and the GridItems list
356/// once a definite placement has been determined
357#[allow(clippy::too_many_arguments)]
358fn record_grid_placement<S: GridItemStyle>(
359    cell_occupancy_matrix: &mut CellOccupancyMatrix,
360    items: &mut Vec<GridItem>,
361    node: NodeId,
362    index: usize,
363    style: S,
364    parent_align_items: AlignItems,
365    parent_justify_items: AlignItems,
366    primary_axis: AbsoluteAxis,
367    primary_span: Line<OriginZeroLine>,
368    secondary_span: Line<OriginZeroLine>,
369    placement_type: CellOccupancyState,
370) {
371    #[cfg(test)]
372    println!("BEFORE placement:");
373    #[cfg(test)]
374    println!("{cell_occupancy_matrix:?}");
375
376    // Clamp placements into the limited grid to prevent arithmetic overflow when growing the
377    // implicit grid (https://www.w3.org/TR/css-grid-1/#overlarge-grids)
378    let primary_span = clamp_span_to_limited_grid(primary_span);
379    let secondary_span = clamp_span_to_limited_grid(secondary_span);
380
381    // Mark area of grid as occupied
382    cell_occupancy_matrix.mark_area_as(primary_axis, primary_span, secondary_span, placement_type);
383
384    // Create grid item
385    let (col_span, row_span) = match primary_axis {
386        AbsoluteAxis::Horizontal => (primary_span, secondary_span),
387        AbsoluteAxis::Vertical => (secondary_span, primary_span),
388    };
389    items.push(GridItem::new_with_placement_style_and_order(
390        node,
391        col_span,
392        row_span,
393        style,
394        parent_align_items,
395        parent_justify_items,
396        index as u16,
397    ));
398
399    #[cfg(test)]
400    println!("AFTER placement:");
401    #[cfg(test)]
402    println!("{cell_occupancy_matrix:?}");
403    #[cfg(test)]
404    println!("\n");
405}
406
407#[cfg(test)]
408mod tests {
409    use super::*;
410
411    mod test_placement_algorithm {
412        use crate::compute::grid::implicit_grid::compute_grid_size_estimate;
413        use crate::compute::grid::types::TrackCounts;
414        use crate::compute::grid::util::*;
415        use crate::compute::grid::CellOccupancyMatrix;
416        use crate::compute::grid::NamedLineResolver;
417        use crate::compute::grid::OriginZeroLine;
418        use crate::prelude::*;
419        use crate::style::GridAutoFlow;
420
421        use super::super::place_grid_items;
422
423        type ExpectedPlacement = (i16, i16, i16, i16);
424
425        fn placement_test_runner(
426            explicit_col_count: u16,
427            explicit_row_count: u16,
428            children: Vec<(usize, Style, ExpectedPlacement)>,
429            expected_col_counts: TrackCounts,
430            expected_row_counts: TrackCounts,
431            flow: GridAutoFlow,
432        ) {
433            // Setup test
434            let children_iter = || children.iter().map(|(index, style, _)| (*index, NodeId::from(*index), style));
435            let child_styles_iter = children.iter().map(|(_, style, _)| style);
436            let estimated_sizes = compute_grid_size_estimate(explicit_col_count, explicit_row_count, child_styles_iter);
437            let mut items = Vec::new();
438            let mut cell_occupancy_matrix =
439                CellOccupancyMatrix::with_track_counts(estimated_sizes.0, estimated_sizes.1);
440            let mut name_resolver = NamedLineResolver::new(&Style::DEFAULT, 0, 0);
441            name_resolver.set_explicit_column_count(explicit_col_count);
442            name_resolver.set_explicit_row_count(explicit_row_count);
443
444            // Run placement algorithm
445            place_grid_items(
446                &mut cell_occupancy_matrix,
447                &mut items,
448                children_iter,
449                flow,
450                AlignSelf::START,
451                AlignSelf::START,
452                // TODO: actually test named line resolution
453                &name_resolver,
454            );
455
456            // Assert that each item has been placed in the right location
457            let mut sorted_children = children.clone();
458            sorted_children.sort_by_key(|child| child.0);
459            for (idx, ((id, _style, expected_placement), item)) in sorted_children.iter().zip(items.iter()).enumerate()
460            {
461                assert_eq!(item.node, NodeId::from(*id));
462                let actual_placement = (item.column.start, item.column.end, item.row.start, item.row.end);
463                assert_eq!(actual_placement, (*expected_placement).into_oz(), "Item {idx} (0-indexed)");
464            }
465
466            // Assert that the correct number of implicit rows have been generated
467            let actual_row_counts = *cell_occupancy_matrix.track_counts(crate::compute::grid::AbsoluteAxis::Vertical);
468            assert_eq!(actual_row_counts, expected_row_counts, "row track counts");
469            let actual_col_counts = *cell_occupancy_matrix.track_counts(crate::compute::grid::AbsoluteAxis::Horizontal);
470            assert_eq!(actual_col_counts, expected_col_counts, "column track counts");
471        }
472
473        #[test]
474        fn test_only_fixed_placement() {
475            let flow = GridAutoFlow::Row;
476            let explicit_col_count = 2;
477            let explicit_row_count = 2;
478            let children = {
479                vec![
480                    // node, style (grid coords), expected_placement (oz coords)
481                    (1, (line(1), auto(), line(1), auto()).into_grid_child(), (0, 1, 0, 1)),
482                    (2, (line(-4), auto(), line(-3), auto()).into_grid_child(), (-1, 0, 0, 1)),
483                    (3, (line(-3), auto(), line(-4), auto()).into_grid_child(), (0, 1, -1, 0)),
484                    (4, (line(3), span(2), line(5), auto()).into_grid_child(), (2, 4, 4, 5)),
485                ]
486            };
487            let expected_cols = TrackCounts { negative_implicit: 1, explicit: 2, positive_implicit: 2 };
488            let expected_rows = TrackCounts { negative_implicit: 1, explicit: 2, positive_implicit: 3 };
489            placement_test_runner(explicit_col_count, explicit_row_count, children, expected_cols, expected_rows, flow);
490        }
491
492        #[test]
493        fn test_placement_spanning_origin() {
494            let flow = GridAutoFlow::Row;
495            let explicit_col_count = 2;
496            let explicit_row_count = 2;
497            let children = {
498                vec![
499                    // node, style (grid coords), expected_placement (oz coords)
500                    (1, (line(-1), line(-1), line(-1), line(-1)).into_grid_child(), (2, 3, 2, 3)),
501                    (2, (line(-1), span(2), line(-1), span(2)).into_grid_child(), (2, 4, 2, 4)),
502                    (3, (line(-4), line(-4), line(-4), line(-4)).into_grid_child(), (-1, 0, -1, 0)),
503                    (4, (line(-4), span(2), line(-4), span(2)).into_grid_child(), (-1, 1, -1, 1)),
504                ]
505            };
506            let expected_cols = TrackCounts { negative_implicit: 1, explicit: 2, positive_implicit: 2 };
507            let expected_rows = TrackCounts { negative_implicit: 1, explicit: 2, positive_implicit: 2 };
508            placement_test_runner(explicit_col_count, explicit_row_count, children, expected_cols, expected_rows, flow);
509        }
510
511        #[test]
512        fn test_only_auto_placement_row_flow() {
513            let flow = GridAutoFlow::Row;
514            let explicit_col_count = 2;
515            let explicit_row_count = 2;
516            let children = {
517                let auto_child = (auto(), auto(), auto(), auto()).into_grid_child();
518                vec![
519                    // output order, node, style (grid coords), expected_placement (oz coords)
520                    (1, auto_child.clone(), (0, 1, 0, 1)),
521                    (2, auto_child.clone(), (1, 2, 0, 1)),
522                    (3, auto_child.clone(), (0, 1, 1, 2)),
523                    (4, auto_child.clone(), (1, 2, 1, 2)),
524                    (5, auto_child.clone(), (0, 1, 2, 3)),
525                    (6, auto_child.clone(), (1, 2, 2, 3)),
526                    (7, auto_child.clone(), (0, 1, 3, 4)),
527                    (8, auto_child.clone(), (1, 2, 3, 4)),
528                ]
529            };
530            let expected_cols = TrackCounts { negative_implicit: 0, explicit: 2, positive_implicit: 0 };
531            let expected_rows = TrackCounts { negative_implicit: 0, explicit: 2, positive_implicit: 2 };
532            placement_test_runner(explicit_col_count, explicit_row_count, children, expected_cols, expected_rows, flow);
533        }
534
535        #[test]
536        fn test_only_auto_placement_column_flow() {
537            let flow = GridAutoFlow::Column;
538            let explicit_col_count = 2;
539            let explicit_row_count = 2;
540            let children = {
541                let auto_child = (auto(), auto(), auto(), auto()).into_grid_child();
542                vec![
543                    // output order, node, style (grid coords), expected_placement (oz coords)
544                    (1, auto_child.clone(), (0, 1, 0, 1)),
545                    (2, auto_child.clone(), (0, 1, 1, 2)),
546                    (3, auto_child.clone(), (1, 2, 0, 1)),
547                    (4, auto_child.clone(), (1, 2, 1, 2)),
548                    (5, auto_child.clone(), (2, 3, 0, 1)),
549                    (6, auto_child.clone(), (2, 3, 1, 2)),
550                    (7, auto_child.clone(), (3, 4, 0, 1)),
551                    (8, auto_child.clone(), (3, 4, 1, 2)),
552                ]
553            };
554            let expected_cols = TrackCounts { negative_implicit: 0, explicit: 2, positive_implicit: 2 };
555            let expected_rows = TrackCounts { negative_implicit: 0, explicit: 2, positive_implicit: 0 };
556            placement_test_runner(explicit_col_count, explicit_row_count, children, expected_cols, expected_rows, flow);
557        }
558
559        #[test]
560        fn test_oversized_item() {
561            let flow = GridAutoFlow::Row;
562            let explicit_col_count = 2;
563            let explicit_row_count = 2;
564            let children = {
565                vec![
566                    // output order, node, style (grid coords), expected_placement (oz coords)
567                    (1, (span(5), auto(), auto(), auto()).into_grid_child(), (0, 5, 0, 1)),
568                ]
569            };
570            let expected_cols = TrackCounts { negative_implicit: 0, explicit: 2, positive_implicit: 3 };
571            let expected_rows = TrackCounts { negative_implicit: 0, explicit: 2, positive_implicit: 0 };
572            placement_test_runner(explicit_col_count, explicit_row_count, children, expected_cols, expected_rows, flow);
573        }
574
575        #[test]
576        fn test_fixed_in_secondary_axis() {
577            let flow = GridAutoFlow::Row;
578            let explicit_col_count = 2;
579            let explicit_row_count = 2;
580            let children = {
581                vec![
582                    // output order, node, style (grid coords), expected_placement (oz coords)
583                    (1, (span(2), auto(), line(1), auto()).into_grid_child(), (0, 2, 0, 1)),
584                    (2, (auto(), auto(), line(2), auto()).into_grid_child(), (0, 1, 1, 2)),
585                    (3, (auto(), auto(), line(1), auto()).into_grid_child(), (2, 3, 0, 1)),
586                    (4, (auto(), auto(), line(4), auto()).into_grid_child(), (0, 1, 3, 4)),
587                ]
588            };
589            let expected_cols = TrackCounts { negative_implicit: 0, explicit: 2, positive_implicit: 1 };
590            let expected_rows = TrackCounts { negative_implicit: 0, explicit: 2, positive_implicit: 2 };
591            placement_test_runner(explicit_col_count, explicit_row_count, children, expected_cols, expected_rows, flow);
592        }
593
594        #[test]
595        fn test_definite_in_secondary_axis_with_fully_definite_negative() {
596            let flow = GridAutoFlow::Row;
597            let explicit_col_count = 2;
598            let explicit_row_count = 2;
599            let children = {
600                vec![
601                    // output order, node, style (grid coords), expected_placement (oz coords)
602                    (2, (auto(), auto(), line(2), auto()).into_grid_child(), (0, 1, 1, 2)),
603                    (1, (line(-4), auto(), line(2), auto()).into_grid_child(), (-1, 0, 1, 2)),
604                    (3, (auto(), auto(), line(1), auto()).into_grid_child(), (-1, 0, 0, 1)),
605                ]
606            };
607            let expected_cols = TrackCounts { negative_implicit: 1, explicit: 2, positive_implicit: 0 };
608            let expected_rows = TrackCounts { negative_implicit: 0, explicit: 2, positive_implicit: 0 };
609            placement_test_runner(explicit_col_count, explicit_row_count, children, expected_cols, expected_rows, flow);
610        }
611
612        #[test]
613        fn test_dense_packing_algorithm() {
614            let flow = GridAutoFlow::RowDense;
615            let explicit_col_count = 4;
616            let explicit_row_count = 4;
617            let children = {
618                vec![
619                    // output order, node, style (grid coords), expected_placement (oz coords)
620                    (1, (line(2), auto(), line(1), auto()).into_grid_child(), (1, 2, 0, 1)), // Definitely positioned in column 2
621                    (2, (span(2), auto(), auto(), auto()).into_grid_child(), (2, 4, 0, 1)), // Spans 2 columns, so positioned after item 1
622                    (3, (auto(), auto(), auto(), auto()).into_grid_child(), (0, 1, 0, 1)), // Spans 1 column, so should be positioned before item 1
623                ]
624            };
625            let expected_cols = TrackCounts { negative_implicit: 0, explicit: 4, positive_implicit: 0 };
626            let expected_rows = TrackCounts { negative_implicit: 0, explicit: 4, positive_implicit: 0 };
627            placement_test_runner(explicit_col_count, explicit_row_count, children, expected_cols, expected_rows, flow);
628        }
629
630        #[test]
631        fn test_sparse_packing_algorithm() {
632            let flow = GridAutoFlow::Row;
633            let explicit_col_count = 4;
634            let explicit_row_count = 4;
635            let children = {
636                vec![
637                    // output order, node, style (grid coords), expected_placement (oz coords)
638                    (1, (auto(), span(3), auto(), auto()).into_grid_child(), (0, 3, 0, 1)), // Width 3
639                    (2, (auto(), span(3), auto(), auto()).into_grid_child(), (0, 3, 1, 2)), // Width 3 (wraps to next row)
640                    (3, (auto(), span(1), auto(), auto()).into_grid_child(), (3, 4, 1, 2)), // Width 1 (uses second row as we're already on it)
641                ]
642            };
643            let expected_cols = TrackCounts { negative_implicit: 0, explicit: 4, positive_implicit: 0 };
644            let expected_rows = TrackCounts { negative_implicit: 0, explicit: 4, positive_implicit: 0 };
645            placement_test_runner(explicit_col_count, explicit_row_count, children, expected_cols, expected_rows, flow);
646        }
647
648        #[test]
649        fn test_auto_placement_in_negative_tracks() {
650            let flow = GridAutoFlow::RowDense;
651            let explicit_col_count = 2;
652            let explicit_row_count = 2;
653            let children = {
654                vec![
655                    // output order, node, style (grid coords), expected_placement (oz coords)
656                    (1, (line(-5), auto(), line(1), auto()).into_grid_child(), (-2, -1, 0, 1)), // Row 1. Definitely positioned in column -2
657                    (2, (auto(), auto(), line(2), auto()).into_grid_child(), (-2, -1, 1, 2)), // Row 2. Auto positioned in column -2
658                    (3, (auto(), auto(), auto(), auto()).into_grid_child(), (-1, 0, 0, 1)), // Row 1. Auto positioned in column -1
659                ]
660            };
661            let expected_cols = TrackCounts { negative_implicit: 2, explicit: 2, positive_implicit: 0 };
662            let expected_rows = TrackCounts { negative_implicit: 0, explicit: 2, positive_implicit: 0 };
663            placement_test_runner(explicit_col_count, explicit_row_count, children, expected_cols, expected_rows, flow);
664        }
665
666        #[test]
667        fn test_overlarge_placement_is_clamped() {
668            let explicit_col_count = 9_000;
669            let explicit_row_count = 0;
670            let style = (line(-19_005), auto(), auto(), auto()).into_grid_child();
671            let children = [(0, style)];
672            let estimated_sizes = compute_grid_size_estimate(
673                explicit_col_count,
674                explicit_row_count,
675                children.iter().map(|(_, style)| style),
676            );
677            let mut items = Vec::new();
678            let mut cell_occupancy_matrix =
679                CellOccupancyMatrix::with_track_counts(estimated_sizes.0, estimated_sizes.1);
680            let mut name_resolver = NamedLineResolver::new(&Style::DEFAULT, 0, 0);
681            name_resolver.set_explicit_column_count(explicit_col_count);
682            name_resolver.set_explicit_row_count(explicit_row_count);
683            place_grid_items(
684                &mut cell_occupancy_matrix,
685                &mut items,
686                || children.iter().map(|(index, style)| (*index, NodeId::from(*index), style)),
687                GridAutoFlow::Row,
688                AlignSelf::START,
689                AlignSelf::START,
690                &name_resolver,
691            );
692            assert_eq!(items[0].column, Line { start: OriginZeroLine(-10_000), end: OriginZeroLine(-9_999) });
693        }
694    }
695
696    #[test]
697    fn auto_placement_cursor_saturates_at_integer_bounds() {
698        assert_eq!(advance_position(OriginZeroLine(i16::MAX)), OriginZeroLine(i16::MAX));
699    }
700
701    #[test]
702    fn indefinite_spans_saturate_at_integer_bounds() {
703        assert_eq!(
704            resolve_indefinite_grid_span(OriginZeroLine(i16::MAX), 1),
705            Line { start: OriginZeroLine(i16::MAX), end: OriginZeroLine(i16::MAX) }
706        );
707    }
708}
taffy/compute/grid/placement.rs

taffy/compute/grid/
placement.rs
