gpui_kit_grid/engine/
group.rs

1//! Grouping: the levels of a view, the order of sibling groups, group
2//! footers and the grouped rebuild. No GPUI types.
3
4use std::{array, cmp::Ordering, fmt, iter, mem, ops::Range, sync::Arc};
5
6use super::{
7    AggregateRow, FadingIds, GroupInfo, GroupPath, Parallelism, Projection, Rebuild, SortDirection,
8    Structure, ViewSpec,
9    aggregate::{GroupValues, KeyedGroup, ViewAggregates, aggregate_groups},
10    directed,
11    display::{AggregateValues, Group, GroupData, GroupId},
12    sorted_rows,
13};
14use crate::{
15    model::{CellValue, ColumnId, ColumnIx, ColumnSet, GridColumns, GridRow, OwnedValue},
16    store::{RowId, StoreSnapshot},
17};
18
19/// The key function of a [`GroupKey`].
20type KeyFn<R> = Arc<dyn Fn(&R) -> CellValue<'_> + Send + Sync>;
21
22/// Grouping by a function of the row rather than a column: a bucket of
23/// prices, the first letter of a name.
24pub struct GroupKey<R: GridRow> {
25    id: &'static str,
26    title: Arc<str>,
27    depends_on: ColumnSet,
28    key: KeyFn<R>,
29}
30
31impl<R: GridRow> Clone for GroupKey<R> {
32    fn clone(&self) -> Self {
33        Self {
34            id: self.id,
35            title: self.title.clone(),
36            depends_on: self.depends_on,
37            key: self.key.clone(),
38        }
39    }
40}
41
42impl<R: GridRow> fmt::Debug for GroupKey<R> {
43    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
44        f.debug_struct("GroupKey")
45            .field("id", &self.id)
46            .field("title", &self.title)
47            .field("depends_on", &self.depends_on)
48            .finish_non_exhaustive()
49    }
50}
51
52impl<R: GridRow> GroupKey<R> {
53    /// A level keyed by `key`.
54    ///
55    /// `id` names the level in group paths and must differ from every
56    /// column id of the schema. `depends_on` lists the columns `key` reads;
57    /// pass every column when unsure. `key` runs in the background, from
58    /// several threads of a large rebuild, once or twice per row: it must
59    /// not allocate, so it returns text borrowed from the row.
60    pub fn new(
61        id: &'static str,
62        depends_on: ColumnSet,
63        key: impl Fn(&R) -> CellValue<'_> + Send + Sync + 'static,
64    ) -> Self {
65        Self {
66            id,
67            title: id.into(),
68            depends_on,
69            key: Arc::new(key),
70        }
71    }
72
73    /// The level's title in captions and the group panel; the id by
74    /// default.
75    pub fn with_title(mut self, title: impl Into<Arc<str>>) -> Self {
76        self.title = title.into();
77        self
78    }
79
80    /// The level's id.
81    pub fn id(&self) -> &'static str {
82        self.id
83    }
84
85    /// The level's title.
86    pub fn title(&self) -> &str {
87        &self.title
88    }
89
90    /// The columns the key reads.
91    pub fn depends_on(&self) -> ColumnSet {
92        self.depends_on
93    }
94
95    /// The key of a row.
96    pub(crate) fn value<'r>(&self, row: &'r R) -> CellValue<'r> {
97        (self.key)(row)
98    }
99}
100
101/// What a level groups by.
102enum GroupLevel<R: GridRow> {
103    Column(R::Column),
104    Key(GroupKey<R>),
105}
106
107impl<R: GridRow> Clone for GroupLevel<R> {
108    fn clone(&self) -> Self {
109        match self {
110            Self::Column(column) => Self::Column(*column),
111            Self::Key(key) => Self::Key(key.clone()),
112        }
113    }
114}
115
116/// One level of a grouping: a column or a [`GroupKey`], and the order of
117/// its groups by key.
118pub struct GroupBy<R: GridRow> {
119    level: GroupLevel<R>,
120    direction: SortDirection,
121}
122
123impl<R: GridRow> Clone for GroupBy<R> {
124    fn clone(&self) -> Self {
125        Self {
126            level: self.level.clone(),
127            direction: self.direction,
128        }
129    }
130}
131
132impl<R: GridRow> fmt::Debug for GroupBy<R> {
133    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
134        let mut debug = f.debug_struct("GroupBy");
135        match &self.level {
136            GroupLevel::Column(column) => debug.field("column", column),
137            GroupLevel::Key(key) => debug.field("key", key),
138        };
139        debug.field("direction", &self.direction).finish()
140    }
141}
142
143impl<R: GridRow> GroupBy<R> {
144    /// Groups by a column's value, ascending.
145    pub fn column(column: R::Column) -> Self {
146        Self {
147            level: GroupLevel::Column(column),
148            direction: SortDirection::Ascending,
149        }
150    }
151
152    /// Groups by a function of the row, ascending.
153    pub fn key(key: GroupKey<R>) -> Self {
154        Self {
155            level: GroupLevel::Key(key),
156            direction: SortDirection::Ascending,
157        }
158    }
159
160    /// The order of this level's groups by key.
161    pub fn with_direction(mut self, direction: SortDirection) -> Self {
162        self.direction = direction;
163        self
164    }
165
166    /// The order of this level's groups by key.
167    pub fn direction(&self) -> SortDirection {
168        self.direction
169    }
170
171    /// The column, for a column level.
172    pub fn as_column(&self) -> Option<R::Column> {
173        match &self.level {
174            GroupLevel::Column(column) => Some(*column),
175            GroupLevel::Key(_) => None,
176        }
177    }
178
179    /// The key, for a level by a function of the row.
180    pub fn as_key(&self) -> Option<&GroupKey<R>> {
181        match &self.level {
182            GroupLevel::Column(_) => None,
183            GroupLevel::Key(key) => Some(key),
184        }
185    }
186
187    /// The level's id in a [`GroupPath`]: the column's id, or the key's.
188    pub fn id(&self) -> ColumnId {
189        match &self.level {
190            GroupLevel::Column(column) => column.column_id(),
191            GroupLevel::Key(key) => ColumnId::new_static(key.id),
192        }
193    }
194
195    /// The level's key of a row.
196    pub(crate) fn value<'r>(&self, row: &'r R) -> CellValue<'r> {
197        match &self.level {
198            GroupLevel::Column(column) => row.value(*column),
199            GroupLevel::Key(key) => key.value(row),
200        }
201    }
202}
203
204/// The grouping of a view: its levels, the top one first.
205pub(crate) struct GroupSpec<R: GridRow> {
206    levels: Arc<[GroupBy<R>]>,
207}
208
209impl<R: GridRow> Clone for GroupSpec<R> {
210    fn clone(&self) -> Self {
211        Self {
212            levels: self.levels.clone(),
213        }
214    }
215}
216
217impl<R: GridRow> GroupSpec<R> {
218    /// The levels, the top one first.
219    pub(crate) fn levels(&self) -> &[GroupBy<R>] {
220        &self.levels
221    }
222}
223
224/// What [`GroupOrder`] knows about a group when it orders siblings.
225pub struct GroupOrderContext<'a> {
226    path: &'a GroupPath,
227    row_count: usize,
228    aggregates: AggregateRow<'a>,
229}
230
231impl<'a> GroupOrderContext<'a> {
232    /// The group at `path`, with its live rows and aggregates.
233    pub(crate) fn new(path: &'a GroupPath, row_count: usize, aggregates: AggregateRow<'a>) -> Self {
234        Self {
235            path,
236            row_count,
237            aggregates,
238        }
239    }
240
241    /// The group's identity.
242    pub fn path(&self) -> &'a GroupPath {
243        self.path
244    }
245
246    /// The group's key value.
247    pub fn value(&self) -> &'a OwnedValue {
248        self.path
249            .value(self.path.depth())
250            .expect("a group's path is not the root")
251    }
252
253    /// The group's depth: 0 for a top-level group.
254    pub fn depth(&self) -> u16 {
255        self.path.depth()
256    }
257
258    /// The group's live rows.
259    pub fn row_count(&self) -> usize {
260        self.row_count
261    }
262
263    /// The group's aggregate of a column, if the view aggregates it.
264    pub fn aggregate(&self, column: ColumnIx) -> Option<&'a OwnedValue> {
265        self.aggregates.get(column)
266    }
267}
268
269/// The order of sibling groups. Groups are first in the order of their
270/// keys, each level in its direction; `compare` sorts siblings stably from
271/// there, so `Equal` keeps the key order.
272///
273/// Called in the background, from several threads of a large rebuild, once
274/// per comparison of two groups.
275pub trait GroupOrder<R: GridRow>: Send + Sync + 'static {
276    /// Compares two sibling groups.
277    fn compare(&self, a: &GroupOrderContext<'_>, b: &GroupOrderContext<'_>) -> Ordering;
278
279    /// The columns whose changes can reorder groups: the order's
280    /// aggregates. Empty for an order that reads keys alone.
281    fn depends_on(&self) -> ColumnSet {
282        ColumnSet::EMPTY
283    }
284}
285
286/// Groups in the order of their keys, each level in its direction: the default.
287#[derive(Clone, Copy, Debug, Default)]
288pub struct KeyOrder;
289
290impl<R: GridRow> GroupOrder<R> for KeyOrder {
291    fn compare(&self, _: &GroupOrderContext<'_>, _: &GroupOrderContext<'_>) -> Ordering {
292        Ordering::Equal
293    }
294}
295
296/// Groups by the aggregate of a column: the column needs an aggregate in
297/// the view. Ties, and groups without the aggregate, keep the key order.
298#[derive(Clone, Copy, Debug)]
299pub struct AggregateOrder {
300    column: ColumnIx,
301    direction: SortDirection,
302}
303
304impl AggregateOrder {
305    /// Orders groups by their aggregate of `column`.
306    pub fn new(column: impl GridColumns, direction: SortDirection) -> Self {
307        Self {
308            column: column.ix(),
309            direction,
310        }
311    }
312
313    /// The column whose aggregate orders the groups.
314    pub fn column(&self) -> ColumnIx {
315        self.column
316    }
317
318    /// The direction.
319    pub fn direction(&self) -> SortDirection {
320        self.direction
321    }
322}
323
324impl<R: GridRow> GroupOrder<R> for AggregateOrder {
325    fn compare(&self, a: &GroupOrderContext<'_>, b: &GroupOrderContext<'_>) -> Ordering {
326        match (a.aggregate(self.column), b.aggregate(self.column)) {
327            (Some(a), Some(b)) => directed(a.cmp_total(b), self.direction),
328            _ => Ordering::Equal,
329        }
330    }
331
332    fn depends_on(&self) -> ColumnSet {
333        let mut columns = ColumnSet::EMPTY;
334        columns.insert(self.column);
335        columns
336    }
337}
338
339/// Which groups have a footer row under their rows. Called in the
340/// background, once per group.
341pub trait GroupFooter: Send + Sync + 'static {
342    /// Returns true if `group` has a footer.
343    fn has_footer(&self, group: &GroupInfo<'_>) -> bool;
344}
345
346/// No group has a footer: the default.
347#[derive(Clone, Copy, Debug, Default)]
348pub struct NoGroupFooter;
349
350impl GroupFooter for NoGroupFooter {
351    fn has_footer(&self, _: &GroupInfo<'_>) -> bool {
352        false
353    }
354}
355
356/// Every group has a footer.
357#[derive(Clone, Copy, Debug, Default)]
358pub struct EveryGroupFooter;
359
360impl GroupFooter for EveryGroupFooter {
361    fn has_footer(&self, _: &GroupInfo<'_>) -> bool {
362        true
363    }
364}
365
366impl<R: GridRow> ViewSpec<R> {
367    /// Groups the rows by these levels, the first one outermost. Repeated
368    /// level ids are dropped, the first one stays; an empty list turns
369    /// grouping off. Replaces a tree, as in AG Grid and DevExpress: the last
370    /// of `with_group_by` and [`Self::with_tree`] wins.
371    pub fn with_group_by(mut self, levels: impl IntoIterator<Item = GroupBy<R>>) -> Self {
372        let mut unique: Vec<GroupBy<R>> = Vec::new();
373        for level in levels {
374            debug_assert!(
375                level
376                    .as_key()
377                    .is_none_or(|key| R::Column::all().iter().all(|column| column.id() != key.id)),
378                "the group key id {:?} is a column id",
379                level.id()
380            );
381            if !unique.iter().any(|kept| kept.id() == level.id()) {
382                unique.push(level);
383            }
384        }
385        self.structure = if unique.is_empty() {
386            Structure::Flat
387        } else {
388            Structure::Groups(GroupSpec {
389                levels: unique.into(),
390            })
391        };
392        self
393    }
394
395    /// The grouping levels, the top one first; empty without grouping.
396    pub fn group_by(&self) -> &[GroupBy<R>] {
397        match self.structure() {
398            Structure::Groups(groups) => groups.levels(),
399            Structure::Flat | Structure::Tree(_) => &[],
400        }
401    }
402
403    /// Sets the order of sibling groups (default [`KeyOrder`]).
404    pub fn with_group_order(mut self, order: impl GroupOrder<R>) -> Self {
405        self.group_order = Some(Arc::new(order));
406        self
407    }
408
409    /// The order of sibling groups.
410    pub fn group_order(&self) -> &dyn GroupOrder<R> {
411        match &self.group_order {
412            Some(order) => &**order,
413            None => &KeyOrder,
414        }
415    }
416
417    /// Sets which groups have a footer (default [`NoGroupFooter`]).
418    pub fn with_group_footer(mut self, footer: impl GroupFooter) -> Self {
419        self.group_footer = Some(Arc::new(footer));
420        self
421    }
422
423    /// Which groups have a footer.
424    pub(crate) fn group_footer(&self) -> &dyn GroupFooter {
425        match &self.group_footer {
426            Some(footer) => &**footer,
427            None => &NoGroupFooter,
428        }
429    }
430}
431
432/// Builds a grouped view, splitting the sort across threads as a flat
433/// rebuild does.
434pub(super) fn rebuild<R: GridRow>(
435    engine: &Rebuild,
436    snapshot: &StoreSnapshot<R>,
437    spec: &ViewSpec<R>,
438    grouping: &GroupSpec<R>,
439) -> Projection {
440    let parallelism = Parallelism::for_rows(snapshot.len(), engine.max_threads());
441    rebuild_with(snapshot, spec, grouping, parallelism)
442}
443
444/// [`rebuild`] with the work split as given.
445///
446/// 1. Filter and sort, as a flat rebuild: by the levels' keys, each in its
447///    direction, then the view's sort, then insertion. Fading rows take
448///    their places by their last values; those of a group of the last level
449///    without a live row go, as a fading row makes no group.
450/// 2. Find the groups in one pass over the sorted entries, by the keys
451///    they cache: a group ends where a key of its level or above changes.
452/// 3. Aggregate the live rows from the bottom up, in key order, and total.
453/// 4. Sort the siblings of each level by the group order, stably, and lay
454///    the rows out again so each group's rows follow each other.
455/// 5. Ask the group footer about each group; lay the lines out by the
456///    expansion.
457///
458/// Allocates per group and per job, not per row: keys are borrowed from
459/// the snapshot's rows.
460pub(super) fn rebuild_with<R: GridRow>(
461    snapshot: &StoreSnapshot<R>,
462    spec: &ViewSpec<R>,
463    grouping: &GroupSpec<R>,
464    parallelism: Parallelism,
465) -> Projection {
466    let levels = grouping.levels();
467    let keys = sort_keys(spec, levels);
468    // As many keys cached as the view has, up to `MAX_CACHED_KEYS`; never
469    // fewer than two, so small views share one instance.
470    match keys.len() {
471        0..=2 => build::<R, 2>(snapshot, spec, levels, &keys, parallelism),
472        3 => build::<R, 3>(snapshot, spec, levels, &keys, parallelism),
473        _ => build::<R, MAX_CACHED_KEYS>(snapshot, spec, levels, &keys, parallelism),
474    }
475}
476
477/// [`rebuild_with`] with `N` keys cached in each sort entry.
478fn build<R: GridRow, const N: usize>(
479    snapshot: &StoreSnapshot<R>,
480    spec: &ViewSpec<R>,
481    levels: &[GroupBy<R>],
482    keys: &[SortKey<'_, R>],
483    parallelism: Parallelism,
484) -> Projection {
485    let level_count = levels.len() as u16;
486    let (mut sorted, fading) = sort_rows::<R, N>(snapshot, spec, keys, parallelism);
487    let fading = if fading > 0 {
488        FadingIds::new(snapshot)
489    } else {
490        FadingIds::default()
491    };
492    let mut table = find_groups(levels, &sorted);
493    if !fading.is_empty() && drop_fading_groups(&mut sorted, &table, level_count, &fading) {
494        table = find_groups(levels, &sorted);
495    }
496
497    let aggregates = ViewAggregates::new(spec);
498    #[cfg(debug_assertions)]
499    warn_unaggregated_order(spec, aggregates.columns());
500    let mut computed =
501        aggregate_groups(&aggregates, &table.groups, level_count, &sorted, |entry| {
502            (!fading.contains(entry.2)).then_some(&**entry.3)
503        });
504    let columns = aggregates.columns();
505    let width = columns.len();
506    let order = order_groups(spec.group_order(), &table, &computed, columns);
507
508    // The groups in caption order. A group's rows start where the rows laid
509    // out so far end: its first descendant of the last level comes next.
510    let expansion = spec.expansion();
511    let mut caption_ids = vec![0u32; order.len()];
512    let mut groups = Vec::with_capacity(order.len());
513    let mut values = Vec::with_capacity(order.len() * width);
514    let mut rows = Vec::with_capacity(sorted.len());
515    for (id, &key_ix) in order.iter().enumerate() {
516        let key_ix = key_ix as usize;
517        caption_ids[key_ix] = id as u32;
518        let keyed = &table.groups[key_ix];
519        let start = rows.len() as u32;
520        let len = keyed.rows.end - keyed.rows.start;
521        if usize::from(keyed.depth) + 1 == levels.len() {
522            rows.extend(
523                sorted[keyed.rows.start as usize..keyed.rows.end as usize]
524                    .iter()
525                    .map(|entry| entry.2),
526            );
527        }
528        let path = mem::take(&mut table.paths[key_ix]);
529        let expanded = expansion.is_group_expanded(&path, levels.len());
530        groups.push(Group {
531            parent: table.parents[key_ix].map(|parent| GroupId::new(caption_ids[parent] as usize)),
532            // A subtree keeps its size when siblings move.
533            end: (id + keyed.end as usize - key_ix) as u32,
534            key_ix: key_ix as u32,
535            rows: start..start + len,
536            live: computed.live[key_ix],
537            line: u32::MAX,
538            expanded,
539            footer: false,
540            path,
541        });
542        values.extend(
543            computed.values[key_ix * width..(key_ix + 1) * width]
544                .iter_mut()
545                .map(|value| mem::replace(value, OwnedValue::Empty)),
546        );
547    }
548
549    let mut groups = GroupData::new(level_count, groups, AggregateValues::new(columns, values));
550    let footer = spec.group_footer();
551    let footers: Vec<bool> = groups
552        .table(&rows)
553        .iter()
554        .map(|group| footer.has_footer(&group))
555        .collect();
556    for (group, footer) in groups.groups.iter_mut().zip(footers) {
557        group.footer = footer;
558    }
559    Projection::with_groups(snapshot, rows, groups)
560        .with_row_count(computed.total_live)
561        .with_totals(AggregateValues::new(columns, computed.totals))
562}
563
564/// The most keys a sort entry caches: the levels' keys first, then the
565/// view's sort keys. The rest are read only when the cached ones tie, as
566/// later sort keys of a flat rebuild are; reading one takes a row from
567/// memory, which costs more than the larger entry (S16b of `spike_bench`:
568/// two levels and a sort key).
569const MAX_CACHED_KEYS: usize = 4;
570
571/// A key of the grouped sort.
572struct SortKey<'s, R: GridRow> {
573    source: KeySource<'s, R>,
574    direction: SortDirection,
575}
576
577enum KeySource<'s, R: GridRow> {
578    Level(&'s GroupBy<R>),
579    Column(R::Column),
580}
581
582impl<R: GridRow> SortKey<'_, R> {
583    #[inline]
584    fn value<'r>(&self, row: &'r R) -> CellValue<'r> {
585        match &self.source {
586            KeySource::Level(level) => level.value(row),
587            KeySource::Column(column) => row.value(*column),
588        }
589    }
590}
591
592/// The keys of a grouped sort: the levels' keys, each in its direction,
593/// then the view's sort.
594fn sort_keys<'s, R: GridRow>(
595    spec: &'s ViewSpec<R>,
596    levels: &'s [GroupBy<R>],
597) -> Vec<SortKey<'s, R>> {
598    levels
599        .iter()
600        .map(|level| SortKey {
601            source: KeySource::Level(level),
602            direction: level.direction(),
603        })
604        .chain(spec.sort().iter().map(|&(column, direction)| SortKey {
605            source: KeySource::Column(column),
606            direction,
607        }))
608        .collect()
609}
610
611/// A row of the grouped sort: its first `N` keys (`Empty` past the last
612/// key), insertion sequence, id and row. The levels' keys come first, so
613/// the groups are found from the entries without reading the rows again.
614type GroupEntry<'a, R, const N: usize> = ([CellValue<'a>; N], u64, RowId, &'a Arc<R>);
615
616/// Compares by the keys, then by insertion; see [`super::compare_sorted`].
617#[inline(always)]
618fn compare_grouped<R: GridRow, const N: usize>(
619    a: &GroupEntry<'_, R, N>,
620    b: &GroupEntry<'_, R, N>,
621    cached: &[SortDirection; N],
622    rest: &[SortKey<'_, R>],
623) -> Ordering {
624    for ix in 0..N {
625        let ordering = directed(a.0[ix].cmp_total(&b.0[ix]), cached[ix]);
626        if ordering.is_ne() {
627            return ordering;
628        }
629    }
630    rest.iter()
631        .map(|key| directed(key.value(a.3).cmp_total(&key.value(b.3)), key.direction))
632        .find(|ordering| ordering.is_ne())
633        .unwrap_or(Ordering::Equal)
634        .then_with(|| a.1.cmp(&b.1))
635}
636
637/// The visible rows of `snapshot` in key order, by `keys` and insertion,
638/// with the number of fading rows among them.
639fn sort_rows<'a, R: GridRow, const N: usize>(
640    snapshot: &'a StoreSnapshot<R>,
641    spec: &ViewSpec<R>,
642    keys: &[SortKey<'_, R>],
643    parallelism: Parallelism,
644) -> (Vec<GroupEntry<'a, R, N>>, usize) {
645    let cached: [SortDirection; N] = array::from_fn(|ix| {
646        keys.get(ix)
647            .map_or(SortDirection::Ascending, |key| key.direction)
648    });
649    let rest = keys.get(N..).unwrap_or_default();
650    sorted_rows(
651        snapshot,
652        spec,
653        parallelism,
654        // A missing key is `Empty` in every row: it ties.
655        |id, row, seq| {
656            let keys =
657                array::from_fn(|ix| keys.get(ix).map_or(CellValue::Empty, |key| key.value(row)));
658            (keys, seq, id, row)
659        },
660        |a, b| compare_grouped(a, b, &cached, rest),
661        |entry| *entry,
662    )
663}
664
665/// Drops the fading rows of the groups of the last level in `table` that
666/// have no live row, keeping the order: a fading row makes no group, or it
667/// would go at once. Returns true if it dropped any: the groups are to be
668/// found again. Usually the first row of a group is live, so this is O(groups).
669fn drop_fading_groups<R: GridRow, const N: usize>(
670    sorted: &mut Vec<GroupEntry<'_, R, N>>,
671    table: &KeyTable,
672    levels: u16,
673    fading: &FadingIds,
674) -> bool {
675    let is_fading = |group: &KeyedGroup| {
676        usize::from(group.depth) + 1 == usize::from(levels)
677            && sorted[group.rows.start as usize..group.rows.end as usize]
678                .iter()
679                .all(|entry| fading.contains(entry.2))
680    };
681    if !table.groups.iter().any(is_fading) {
682        return false;
683    }
684    // The groups of the last level cover the rows in order.
685    let dropped: Vec<Range<usize>> = table
686        .groups
687        .iter()
688        .filter(|group| is_fading(group))
689        .map(|group| group.rows.start as usize..group.rows.end as usize)
690        .collect();
691    let mut kept = 0;
692    let mut next = 0;
693    for range in dropped.into_iter().chain([sorted.len()..sorted.len()]) {
694        sorted.copy_within(next..range.start, kept);
695        kept += range.start - next;
696        next = range.end;
697    }
698    sorted.truncate(kept);
699    true
700}
701
702/// The groups of sorted rows, in key order: a group, then its subgroups,
703/// siblings in the order of their keys.
704#[derive(Default)]
705struct KeyTable {
706    groups: Vec<KeyedGroup>,
707    paths: Vec<GroupPath>,
708    /// The enclosing group, by place in `groups`.
709    parents: Vec<Option<usize>>,
710}
711
712/// Finds the groups of `sorted` in one pass: on each row, the first level
713/// whose key differs from the previous row's (by `cmp_total`) closes the
714/// groups of that level and below and opens new ones. A group's key is its
715/// first row's: `Int(1)` and `Float(1.0)` are one group.
716fn find_groups<'a, R: GridRow, const N: usize>(
717    levels: &[GroupBy<R>],
718    sorted: &[GroupEntry<'a, R, N>],
719) -> KeyTable {
720    let ids: Vec<ColumnId> = levels.iter().map(GroupBy::id).collect();
721    let mut table = KeyTable::default();
722    let mut previous: Vec<CellValue<'a>> = Vec::with_capacity(levels.len());
723    let mut keys: Vec<CellValue<'a>> = Vec::with_capacity(levels.len());
724    // The open group of each level down to the current row's.
725    let mut open: Vec<usize> = Vec::with_capacity(levels.len());
726    let close = |table: &mut KeyTable, open: &mut Vec<usize>, depth: usize, row_ix: usize| {
727        while open.len() > depth {
728            let group = open.pop().expect("open groups");
729            table.groups[group].end = table.groups.len() as u32;
730            table.groups[group].rows.end = row_ix as u32;
731        }
732    };
733    for (row_ix, entry) in sorted.iter().enumerate() {
734        // The first levels' keys are cached in the entry.
735        keys.clear();
736        keys.extend(
737            levels
738                .iter()
739                .enumerate()
740                .map(|(depth, level)| match entry.0.get(depth) {
741                    Some(&key) => key,
742                    None => level.value(entry.3),
743                }),
744        );
745        let changed = if row_ix == 0 {
746            0
747        } else {
748            keys.iter()
749                .zip(&previous)
750                .position(|(key, previous)| key.cmp_total(previous).is_ne())
751                .unwrap_or(levels.len())
752        };
753        close(&mut table, &mut open, changed, row_ix);
754        for depth in changed..levels.len() {
755            let parent = open.last().copied();
756            let level = (ids[depth].clone(), OwnedValue::from_cell(keys[depth]));
757            let path = match parent {
758                Some(parent) => GroupPath::new(
759                    table.paths[parent]
760                        .levels()
761                        .iter()
762                        .cloned()
763                        .chain(iter::once(level)),
764                ),
765                None => GroupPath::new([level]),
766            };
767            open.push(table.groups.len());
768            table.groups.push(KeyedGroup {
769                depth: depth as u16,
770                end: 0,
771                rows: row_ix as u32..row_ix as u32,
772            });
773            table.paths.push(path);
774            table.parents.push(parent);
775        }
776        mem::swap(&mut previous, &mut keys);
777    }
778    close(&mut table, &mut open, 0, sorted.len());
779    table
780}
781
782/// The groups in caption order, as places in `table`: the siblings of each
783/// level sorted by `order`, stably, so ties keep the key order.
784fn order_groups<R: GridRow>(
785    order: &dyn GroupOrder<R>,
786    table: &KeyTable,
787    computed: &GroupValues,
788    columns: ColumnSet,
789) -> Vec<u32> {
790    let width = columns.len();
791    let context = |ix: u32| {
792        let ix = ix as usize;
793        let live = computed.live[ix] as usize;
794        GroupOrderContext::new(
795            &table.paths[ix],
796            live,
797            AggregateRow::new(
798                columns,
799                &computed.values[ix * width..(ix + 1) * width],
800                live,
801            ),
802        )
803    };
804    let compare = |a: u32, b: u32| order.compare(&context(a), &context(b));
805    let mut ordered = Vec::with_capacity(table.groups.len());
806    let mut siblings = Vec::new();
807    order_siblings(
808        &table.groups,
809        0..table.groups.len(),
810        0,
811        &compare,
812        &mut siblings,
813        &mut ordered,
814    );
815    ordered
816}
817
818/// Appends the groups of `span` to `ordered` in caption order: the top ones
819/// of the span sorted by `compare`, each followed by its subgroups.
820/// `siblings` keeps a buffer per depth across calls.
821fn order_siblings(
822    groups: &[KeyedGroup],
823    span: Range<usize>,
824    depth: usize,
825    compare: &impl Fn(u32, u32) -> Ordering,
826    siblings: &mut Vec<Vec<u32>>,
827    ordered: &mut Vec<u32>,
828) {
829    if siblings.len() <= depth {
830        siblings.resize_with(depth + 1, Vec::new);
831    }
832    let mut level = mem::take(&mut siblings[depth]);
833    level.clear();
834    let mut next = span.start;
835    while next < span.end {
836        level.push(next as u32);
837        next = groups[next].end as usize;
838    }
839    level.sort_by(|&a, &b| compare(a, b));
840    for &group in &level {
841        ordered.push(group);
842        let group = group as usize;
843        let subgroups = group + 1..groups[group].end as usize;
844        if !subgroups.is_empty() {
845            order_siblings(groups, subgroups, depth + 1, compare, siblings, ordered);
846        }
847    }
848    siblings[depth] = level;
849}
850
851/// Warns once per rebuild of a debug build when the group order reads a
852/// column the view does not aggregate: such groups keep the key order.
853#[cfg(debug_assertions)]
854fn warn_unaggregated_order<R: GridRow>(spec: &ViewSpec<R>, aggregated: ColumnSet) {
855    let order_columns = spec.group_order().depends_on();
856    if let Some(column) = R::Column::all()
857        .iter()
858        .find(|column| order_columns.contains(column.ix()) && !aggregated.contains(column.ix()))
859    {
860        log::warn!(
861            "the group order reads column {:?}, which the view does not aggregate: groups keep the key order",
862            column.id()
863        );
864    }
865}
gpui_kit_grid/engine/group.rs

gpui_kit_grid/engine/
group.rs
