Skip to main content

sui_layout/
grid.rs

1use sui_core::{Point, Rect, Size};
2
3use crate::{Alignment, Constraints};
4
5#[derive(Debug, Clone, Copy, PartialEq)]
6pub enum GridTrackMax {
7    Auto,
8    Points(f32),
9    Fraction(f32),
10}
11
12#[derive(Debug, Clone, Copy, PartialEq)]
13pub enum GridTrack {
14    Fixed(f32),
15    Auto,
16    Fraction(f32),
17    MinMax { min: f32, max: GridTrackMax },
18}
19
20impl GridTrack {
21    pub const fn fixed(points: f32) -> Self {
22        Self::Fixed(points)
23    }
24
25    pub const fn auto() -> Self {
26        Self::Auto
27    }
28
29    pub const fn fraction(weight: f32) -> Self {
30        Self::Fraction(weight)
31    }
32
33    pub const fn minmax(min: f32, max: GridTrackMax) -> Self {
34        Self::MinMax { min, max }
35    }
36}
37
38#[derive(Debug, Clone, Copy, PartialEq, Eq)]
39pub struct GridPlacement {
40    pub row: usize,
41    pub column: usize,
42    pub row_span: usize,
43    pub column_span: usize,
44}
45
46impl GridPlacement {
47    pub const fn new(row: usize, column: usize) -> Self {
48        Self {
49            row,
50            column,
51            row_span: 1,
52            column_span: 1,
53        }
54    }
55
56    pub const fn span(mut self, rows: usize, columns: usize) -> Self {
57        self.row_span = if rows == 0 { 1 } else { rows };
58        self.column_span = if columns == 0 { 1 } else { columns };
59        self
60    }
61}
62
63impl Default for GridPlacement {
64    fn default() -> Self {
65        Self::new(0, 0)
66    }
67}
68
69#[derive(Debug, Clone, Copy, PartialEq)]
70pub struct GridItem {
71    pub placement: GridPlacement,
72    pub minimum_size: Size,
73    pub natural_size: Size,
74    pub horizontal_alignment: Alignment,
75    pub vertical_alignment: Alignment,
76}
77
78impl GridItem {
79    pub fn new(placement: GridPlacement, natural_size: Size) -> Self {
80        let natural_size = sanitize_size(natural_size);
81        Self {
82            placement,
83            minimum_size: natural_size,
84            natural_size,
85            horizontal_alignment: Alignment::Stretch,
86            vertical_alignment: Alignment::Stretch,
87        }
88    }
89
90    pub fn minimum_size(mut self, minimum_size: Size) -> Self {
91        self.minimum_size = sanitize_size(minimum_size);
92        self
93    }
94
95    pub const fn align(mut self, horizontal: Alignment, vertical: Alignment) -> Self {
96        self.horizontal_alignment = horizontal;
97        self.vertical_alignment = vertical;
98        self
99    }
100}
101
102#[derive(Debug, Clone, PartialEq)]
103pub struct GridStyle {
104    pub columns: Vec<GridTrack>,
105    pub rows: Vec<GridTrack>,
106    pub column_gap: f32,
107    pub row_gap: f32,
108}
109
110impl GridStyle {
111    pub fn new(columns: impl IntoIterator<Item = GridTrack>) -> Self {
112        Self {
113            columns: columns.into_iter().collect(),
114            rows: Vec::new(),
115            column_gap: 0.0,
116            row_gap: 0.0,
117        }
118    }
119
120    pub fn rows(mut self, rows: impl IntoIterator<Item = GridTrack>) -> Self {
121        self.rows = rows.into_iter().collect();
122        self
123    }
124
125    pub fn gap(mut self, gap: f32) -> Self {
126        let gap = finite_non_negative(gap);
127        self.column_gap = gap;
128        self.row_gap = gap;
129        self
130    }
131
132    pub fn column_gap(mut self, gap: f32) -> Self {
133        self.column_gap = finite_non_negative(gap);
134        self
135    }
136
137    pub fn row_gap(mut self, gap: f32) -> Self {
138        self.row_gap = finite_non_negative(gap);
139        self
140    }
141}
142
143impl Default for GridStyle {
144    fn default() -> Self {
145        Self::new([GridTrack::Auto])
146    }
147}
148
149#[derive(Debug, Clone, Copy, PartialEq)]
150pub struct GridItemLayout {
151    pub cell: Rect,
152    pub rect: Rect,
153}
154
155#[derive(Debug, Clone, PartialEq)]
156pub struct GridLayout {
157    pub size: Size,
158    pub column_offsets: Vec<f32>,
159    pub column_widths: Vec<f32>,
160    pub row_offsets: Vec<f32>,
161    pub row_heights: Vec<f32>,
162    pub items: Vec<GridItemLayout>,
163}
164
165/// Lay out `items` on `style`'s tracks, adding auto tracks for items placed
166/// past them, up to [`MAX_GRID_TRACKS`] rows and columns.
167pub fn grid_layout(style: &GridStyle, items: &[GridItem], constraints: Constraints) -> GridLayout {
168    let placements = items
169        .iter()
170        .map(|item| within_track_limit(item.placement))
171        .collect::<Vec<_>>();
172    let column_count = placements
173        .iter()
174        .map(|placement| placement.column + placement.column_span)
175        .max()
176        .unwrap_or(0)
177        .max(style.columns.len())
178        .max(1);
179    let row_count = placements
180        .iter()
181        .map(|placement| placement.row + placement.row_span)
182        .max()
183        .unwrap_or(0)
184        .max(style.rows.len())
185        .max(1);
186
187    let columns = padded_tracks(&style.columns, column_count);
188    let rows = padded_tracks(&style.rows, row_count);
189    let (column_widths, width) = resolve_tracks(
190        &columns,
191        style.column_gap,
192        constraints.min.width,
193        constraints.max.width,
194        items
195            .iter()
196            .zip(&placements)
197            .map(|(item, placement)| AxisItem {
198                start: placement.column,
199                span: placement.column_span,
200                minimum: item.minimum_size.width,
201                natural: item.natural_size.width,
202            }),
203    );
204    let (row_heights, height) = resolve_tracks(
205        &rows,
206        style.row_gap,
207        constraints.min.height,
208        constraints.max.height,
209        items
210            .iter()
211            .zip(&placements)
212            .map(|(item, placement)| AxisItem {
213                start: placement.row,
214                span: placement.row_span,
215                minimum: item.minimum_size.height,
216                natural: item.natural_size.height,
217            }),
218    );
219    let column_offsets = track_offsets(&column_widths, style.column_gap);
220    let row_offsets = track_offsets(&row_heights, style.row_gap);
221    let item_layouts = items
222        .iter()
223        .zip(&placements)
224        .map(|(item, placement)| {
225            let cell = span_rect(
226                *placement,
227                &column_offsets,
228                &column_widths,
229                &row_offsets,
230                &row_heights,
231                style.column_gap,
232                style.row_gap,
233            );
234            let child_size = Size::new(
235                aligned_extent(
236                    item.horizontal_alignment,
237                    cell.width(),
238                    item.natural_size.width,
239                ),
240                aligned_extent(
241                    item.vertical_alignment,
242                    cell.height(),
243                    item.natural_size.height,
244                ),
245            );
246            let origin = Point::new(
247                aligned_origin(
248                    item.horizontal_alignment,
249                    cell.x(),
250                    cell.width(),
251                    child_size.width,
252                ),
253                aligned_origin(
254                    item.vertical_alignment,
255                    cell.y(),
256                    cell.height(),
257                    child_size.height,
258                ),
259            );
260            GridItemLayout {
261                cell,
262                rect: Rect::from_origin_size(origin, child_size),
263            }
264        })
265        .collect();
266
267    GridLayout {
268        size: constraints.clamp(Size::new(width, height)),
269        column_offsets,
270        column_widths,
271        row_offsets,
272        row_heights,
273        items: item_layouts,
274    }
275}
276
277/// The most rows or columns [`grid_layout`] adds for placed items.
278pub const MAX_GRID_TRACKS: usize = 1 << 16;
279
280/// `placement` pulled back within [`MAX_GRID_TRACKS`], with spans of at least
281/// one track, so a stray index can't allocate tracks without end or overflow.
282fn within_track_limit(placement: GridPlacement) -> GridPlacement {
283    let row = placement.row.min(MAX_GRID_TRACKS - 1);
284    let column = placement.column.min(MAX_GRID_TRACKS - 1);
285    GridPlacement {
286        row,
287        column,
288        row_span: placement.row_span.clamp(1, MAX_GRID_TRACKS - row),
289        column_span: placement.column_span.clamp(1, MAX_GRID_TRACKS - column),
290    }
291}
292
293#[derive(Clone, Copy)]
294struct AxisItem {
295    start: usize,
296    span: usize,
297    minimum: f32,
298    natural: f32,
299}
300
301fn padded_tracks(tracks: &[GridTrack], count: usize) -> Vec<GridTrack> {
302    let mut result = tracks.to_vec();
303    result.resize(count, GridTrack::Auto);
304    result
305}
306
307fn resolve_tracks(
308    tracks: &[GridTrack],
309    gap: f32,
310    minimum_container: f32,
311    maximum_container: f32,
312    items: impl Iterator<Item = AxisItem> + Clone,
313) -> (Vec<f32>, f32) {
314    let gap = finite_non_negative(gap);
315    let gap_total = gap * tracks.len().saturating_sub(1) as f32;
316    let mut minimums = tracks.iter().map(track_minimum).collect::<Vec<_>>();
317    let mut sizes = minimums.clone();
318
319    for item in items.clone().filter(|item| item.span == 1) {
320        if let Some(track) = tracks.get(item.start) {
321            let minimum = finite_non_negative(item.minimum);
322            let natural = finite_non_negative(item.natural).max(minimum);
323            if !matches!(track, GridTrack::Fixed(_)) {
324                minimums[item.start] = minimums[item.start].max(minimum);
325                sizes[item.start] = sizes[item.start].max(track_natural_target(*track, natural));
326            }
327        }
328    }
329    for item in items.filter(|item| item.span > 1) {
330        distribute_span_shortfall(
331            tracks,
332            &mut minimums,
333            item.start,
334            item.span,
335            finite_non_negative(item.minimum),
336            gap,
337        );
338        distribute_span_shortfall(
339            tracks,
340            &mut sizes,
341            item.start,
342            item.span,
343            finite_non_negative(item.natural).max(finite_non_negative(item.minimum)),
344            gap,
345        );
346    }
347    for (size, minimum) in sizes.iter_mut().zip(&minimums) {
348        *size = size.max(*minimum);
349    }
350    for ((track, minimum), size) in tracks.iter().zip(&mut minimums).zip(&mut sizes) {
351        let cap = track_maximum(*track);
352        *minimum = minimum.min(cap);
353        *size = size.min(cap).max(*minimum);
354    }
355
356    let target = if maximum_container.is_finite() {
357        maximum_container.max(0.0)
358    } else {
359        finite_non_negative(minimum_container).max(sum_tracks(&sizes, gap_total))
360    };
361    let available_tracks = (target - gap_total).max(0.0);
362    let current_tracks = sizes.iter().sum::<f32>();
363    if current_tracks < available_tracks {
364        distribute_fractional_space(tracks, &mut sizes, available_tracks - current_tracks);
365    } else if current_tracks > available_tracks {
366        shrink_to_fit(&mut sizes, &minimums, current_tracks - available_tracks);
367    }
368
369    let natural = sum_tracks(&sizes, gap_total);
370    let resolved =
371        natural
372            .max(finite_non_negative(minimum_container))
373            .min(if maximum_container.is_finite() {
374                maximum_container.max(0.0)
375            } else {
376                f32::INFINITY
377            });
378    (sizes, resolved)
379}
380
381fn track_minimum(track: &GridTrack) -> f32 {
382    match *track {
383        GridTrack::Fixed(points) => finite_non_negative(points),
384        GridTrack::MinMax { min, .. } => finite_non_negative(min),
385        GridTrack::Auto | GridTrack::Fraction(_) => 0.0,
386    }
387}
388
389fn track_natural_target(track: GridTrack, natural: f32) -> f32 {
390    match track {
391        GridTrack::Fixed(points) => finite_non_negative(points),
392        GridTrack::Auto | GridTrack::Fraction(_) => natural,
393        GridTrack::MinMax { min, max } => match max {
394            GridTrackMax::Auto | GridTrackMax::Fraction(_) => natural.max(min),
395            GridTrackMax::Points(max) => natural.clamp(min.max(0.0), max.max(min).max(0.0)),
396        },
397    }
398}
399
400fn track_maximum(track: GridTrack) -> f32 {
401    match track {
402        GridTrack::Fixed(points) => finite_non_negative(points),
403        GridTrack::MinMax {
404            min,
405            max: GridTrackMax::Points(max),
406        } => finite_non_negative(max).max(finite_non_negative(min)),
407        GridTrack::Auto
408        | GridTrack::Fraction(_)
409        | GridTrack::MinMax {
410            max: GridTrackMax::Auto | GridTrackMax::Fraction(_),
411            ..
412        } => f32::INFINITY,
413    }
414}
415
416fn fractional_weight(track: GridTrack) -> f32 {
417    match track {
418        GridTrack::Fraction(weight) => finite_non_negative(weight),
419        GridTrack::MinMax {
420            max: GridTrackMax::Fraction(weight),
421            ..
422        } => finite_non_negative(weight),
423        _ => 0.0,
424    }
425}
426
427fn distribute_fractional_space(tracks: &[GridTrack], sizes: &mut [f32], extra: f32) {
428    let weight = tracks.iter().copied().map(fractional_weight).sum::<f32>();
429    if weight <= 0.0 || extra <= 0.0 {
430        return;
431    }
432    for (track, size) in tracks.iter().copied().zip(sizes) {
433        let track_weight = fractional_weight(track);
434        if track_weight > 0.0 {
435            *size += extra * track_weight / weight;
436        }
437    }
438}
439
440fn shrink_to_fit(sizes: &mut [f32], minimums: &[f32], mut overflow: f32) {
441    while overflow > 0.001 {
442        let shrinkable = sizes
443            .iter()
444            .zip(minimums)
445            .filter(|(size, minimum)| **size > **minimum + 0.001)
446            .count();
447        if shrinkable == 0 {
448            break;
449        }
450        let share = overflow / shrinkable as f32;
451        let mut consumed = 0.0;
452        for (size, minimum) in sizes.iter_mut().zip(minimums) {
453            let amount = (*size - *minimum).max(0.0).min(share);
454            *size -= amount;
455            consumed += amount;
456        }
457        if consumed <= 0.001 {
458            break;
459        }
460        overflow -= consumed;
461    }
462}
463
464fn distribute_span_shortfall(
465    tracks: &[GridTrack],
466    sizes: &mut [f32],
467    start: usize,
468    span: usize,
469    target: f32,
470    gap: f32,
471) {
472    let end = (start + span).min(sizes.len());
473    if start >= end {
474        return;
475    }
476    let current = sizes[start..end].iter().sum::<f32>() + gap * (end - start - 1) as f32;
477    let shortfall = (target - current).max(0.0);
478    if shortfall <= 0.0 {
479        return;
480    }
481    let eligible = (start..end)
482        .filter(|index| !matches!(tracks[*index], GridTrack::Fixed(_)))
483        .collect::<Vec<_>>();
484    if eligible.is_empty() {
485        return;
486    }
487    let share = shortfall / eligible.len() as f32;
488    for index in eligible {
489        sizes[index] += share;
490    }
491}
492
493fn track_offsets(sizes: &[f32], gap: f32) -> Vec<f32> {
494    let mut offset = 0.0;
495    sizes
496        .iter()
497        .map(|size| {
498            let current = offset;
499            offset += *size + gap;
500            current
501        })
502        .collect()
503}
504
505#[allow(clippy::too_many_arguments)]
506fn span_rect(
507    placement: GridPlacement,
508    column_offsets: &[f32],
509    column_widths: &[f32],
510    row_offsets: &[f32],
511    row_heights: &[f32],
512    column_gap: f32,
513    row_gap: f32,
514) -> Rect {
515    let column = placement.column.min(column_widths.len().saturating_sub(1));
516    let row = placement.row.min(row_heights.len().saturating_sub(1));
517    let column_end = (column + placement.column_span.max(1)).min(column_widths.len());
518    let row_end = (row + placement.row_span.max(1)).min(row_heights.len());
519    let width = column_widths[column..column_end].iter().sum::<f32>()
520        + column_gap * column_end.saturating_sub(column + 1) as f32;
521    let height = row_heights[row..row_end].iter().sum::<f32>()
522        + row_gap * row_end.saturating_sub(row + 1) as f32;
523    Rect::new(column_offsets[column], row_offsets[row], width, height)
524}
525
526fn aligned_extent(alignment: Alignment, available: f32, natural: f32) -> f32 {
527    if alignment == Alignment::Stretch {
528        available
529    } else {
530        finite_non_negative(natural).min(available)
531    }
532}
533
534fn aligned_origin(alignment: Alignment, start: f32, available: f32, child_extent: f32) -> f32 {
535    match alignment {
536        Alignment::Start | Alignment::Stretch => start,
537        Alignment::Center => start + (available - child_extent).max(0.0) * 0.5,
538        Alignment::End => start + (available - child_extent).max(0.0),
539    }
540}
541
542fn sum_tracks(sizes: &[f32], gap_total: f32) -> f32 {
543    sizes.iter().sum::<f32>() + gap_total
544}
545
546fn finite_non_negative(value: f32) -> f32 {
547    if value.is_finite() {
548        value.max(0.0)
549    } else {
550        0.0
551    }
552}
553
554fn sanitize_size(size: Size) -> Size {
555    Size::new(
556        finite_non_negative(size.width),
557        finite_non_negative(size.height),
558    )
559}
560
561#[cfg(test)]
562mod tests {
563    use super::*;
564
565    #[test]
566    fn far_out_placements_stay_within_the_track_limit() {
567        let style = GridStyle::new([GridTrack::Auto]);
568        let items = [
569            GridItem::new(GridPlacement::new(1_000_000_000, 3), Size::new(10.0, 10.0)),
570            GridItem::new(
571                GridPlacement::new(usize::MAX, usize::MAX).span(usize::MAX, usize::MAX),
572                Size::new(10.0, 10.0),
573            ),
574        ];
575        let layout = grid_layout(
576            &style,
577            &items,
578            Constraints::new(Size::ZERO, Size::new(400.0, 400.0)),
579        );
580        assert!(layout.column_widths.len() <= MAX_GRID_TRACKS);
581        assert!(layout.row_heights.len() <= MAX_GRID_TRACKS);
582        assert_eq!(layout.items.len(), 2);
583    }
584
585    #[test]
586    fn fraction_tracks_share_remaining_width_after_auto_content() {
587        let style = GridStyle::new([
588            GridTrack::Auto,
589            GridTrack::Fraction(1.0),
590            GridTrack::Fraction(2.0),
591        ])
592        .column_gap(10.0);
593        let items = [GridItem::new(
594            GridPlacement::new(0, 0),
595            Size::new(80.0, 20.0),
596        )];
597        let layout = grid_layout(&style, &items, Constraints::tight(Size::new(380.0, 40.0)));
598
599        assert_eq!(layout.column_widths[0], 80.0);
600        assert!((layout.column_widths[1] - 93.333_336).abs() < 0.001);
601        assert!((layout.column_widths[2] - 186.666_67).abs() < 0.001);
602    }
603
604    #[test]
605    fn spanning_item_grows_auto_tracks_and_alignment_uses_cell() {
606        let style = GridStyle::new([GridTrack::Auto, GridTrack::Auto]).gap(8.0);
607        let item = GridItem::new(GridPlacement::new(0, 0).span(1, 2), Size::new(208.0, 24.0))
608            .minimum_size(Size::new(120.0, 20.0))
609            .align(Alignment::Center, Alignment::Center);
610        let layout = grid_layout(
611            &style,
612            &[item],
613            Constraints::new(Size::ZERO, Size::new(240.0, 80.0)),
614        );
615
616        assert_eq!(layout.column_widths, vec![100.0, 100.0]);
617        assert_eq!(layout.items[0].cell.width(), 208.0);
618        assert_eq!(layout.items[0].rect.width(), 208.0);
619    }
620}