prov_views/
group.rs

1//! Turning a [`Selection`] into groups — a pure function, no I/O.
2//!
3//! A [`RowSet`] *borrows* its selection rather than copying it, which is the
4//! type saying what it is: a projection of a set of documents, not a second
5//! copy of them. One selection can be grouped several ways at once (the same
6//! query behind several lenses), and none of it goes back to disk.
7//!
8//! # Ordering
9//!
10//! Groups sort ascending by key, and rows within a group sort by path. Both are
11//! lexical and both are total, so grouping the same selection twice produces
12//! the identical row set.
13//!
14//! Ascending is the honest default rather than the convenient one: it is right
15//! for `people` and `tags`, and wrong for a date view, where a reader wants the
16//! newest first. There is deliberately no `sort:` axis yet — ordering, like
17//! formulas, is a place the format grows teeth, and a consumer that wants
18//! newest-first reverses a `Vec` it already has.
19
20use std::collections::BTreeMap;
21
22use crate::select::{Row, Selection};
23use crate::spec::Grouping;
24
25/// One group of a view's result.
26#[derive(Debug, Clone, PartialEq)]
27pub struct Group<'a> {
28    /// The group key — a field value, or a value cut at the view's grain.
29    pub key: String,
30    /// The documents under this key, ordered by path.
31    pub rows: Vec<&'a Row>,
32}
33
34/// A selection projected into groups.
35#[derive(Debug, Clone, PartialEq)]
36pub struct RowSet<'a> {
37    /// The name of the view that produced this.
38    pub view: String,
39    /// Groups, ascending by key.
40    pub groups: Vec<Group<'a>>,
41    /// Documents in scope that no field in the grouping chain gave a usable
42    /// value for.
43    ///
44    /// Reported rather than dropped: a view whose entries have all quietly
45    /// stopped grouping looks exactly like an empty archive, and the difference
46    /// is the whole diagnosis. A frontend labels this bucket ("Undated",
47    /// "Untagged"); which words to use is a presentation decision this crate
48    /// does not make.
49    pub ungrouped: Vec<&'a Row>,
50}
51
52impl RowSet<'_> {
53    /// How many **documents** this row set covers.
54    ///
55    /// Not the number of rows printed: a document under two of a multi-valued
56    /// field's groups is one document in two places, and counting it twice is
57    /// how a view comes to claim more entries than the workspace has. The
58    /// placements are [`placements`](Self::placements).
59    pub fn len(&self) -> usize {
60        let mut paths: Vec<_> = self
61            .groups
62            .iter()
63            .flat_map(|g| &g.rows)
64            .chain(&self.ungrouped)
65            .map(|r| &r.path)
66            .collect();
67        paths.sort();
68        paths.dedup();
69        paths.len()
70    }
71
72    /// Whether the view grouped nothing at all.
73    pub fn is_empty(&self) -> bool {
74        self.groups.is_empty() && self.ungrouped.is_empty()
75    }
76
77    /// How many rows a renderer will draw — one per document *per group it
78    /// falls into*, which is what makes it different from [`len`](Self::len).
79    pub fn placements(&self) -> usize {
80        self.groups.iter().map(|g| g.rows.len()).sum::<usize>() + self.ungrouped.len()
81    }
82}
83
84/// Group `selection` by `grouping`.
85///
86/// Pure, and total: every row of the selection lands in at least one group or
87/// in [`ungrouped`](RowSet::ungrouped), so nothing selected can go missing on
88/// the way to being displayed.
89pub fn group<'a>(selection: &'a Selection, grouping: &Grouping) -> RowSet<'a> {
90    let mut grouped: BTreeMap<String, Vec<&'a Row>> = BTreeMap::new();
91    let mut ungrouped: Vec<&'a Row> = Vec::new();
92
93    for row in &selection.rows {
94        let keys = grouping.keys_of(&row.meta);
95        if keys.is_empty() {
96            ungrouped.push(row);
97            continue;
98        }
99        for key in keys {
100            let bucket = grouped.entry(key).or_default();
101            // A field may repeat a value (`people: [Ada, Ada]`); one document
102            // belongs to a group once.
103            if !bucket.iter().any(|r| r.path == row.path) {
104                bucket.push(row);
105            }
106        }
107    }
108
109    // `BTreeMap` ordered the keys; the selection was already in path order, so
110    // each bucket is too.
111    let groups = grouped
112        .into_iter()
113        .map(|(key, rows)| Group { key, rows })
114        .collect();
115
116    RowSet {
117        view: selection.view.clone(),
118        groups,
119        ungrouped,
120    }
121}
122
123#[cfg(test)]
124mod tests {
125    use super::*;
126    use crate::spec::Grain;
127    use prov_graph::meta::{Mapping, Value};
128    use std::path::PathBuf;
129
130    /// The payoff of the split: a selection is a plain value, so every grouping
131    /// question is answered without a filesystem.
132    fn selection(rows: &[(&str, &[(&str, Value)])]) -> Selection {
133        Selection {
134            view: "v".into(),
135            rows: rows
136                .iter()
137                .map(|(path, fields)| {
138                    let mut meta = Mapping::new();
139                    for (k, v) in *fields {
140                        meta.insert((*k).into(), v.clone());
141                    }
142                    Row {
143                        path: PathBuf::from(path),
144                        meta: Value::Mapping(meta),
145                    }
146                })
147                .collect(),
148        }
149    }
150
151    fn text(s: &str) -> Value {
152        Value::String(s.to_string())
153    }
154
155    fn seq(items: &[&str]) -> Value {
156        Value::Sequence(items.iter().map(|s| text(s)).collect())
157    }
158
159    #[test]
160    fn groups_are_ascending_and_rows_stay_in_path_order() {
161        let sel = selection(&[
162            ("b.md", &[("created", text("2026-08-01"))]),
163            ("a.md", &[("created", text("2026-07-24"))]),
164            ("c.md", &[("created", text("2026-07-30"))]),
165        ]);
166        let rows = group(
167            &sel,
168            &Grouping {
169                keys: vec!["created".into()],
170                by: Some(Grain::Month),
171            },
172        );
173        assert_eq!(
174            rows.groups
175                .iter()
176                .map(|g| g.key.as_str())
177                .collect::<Vec<_>>(),
178            ["2026-07", "2026-08"]
179        );
180        assert_eq!(
181            rows.groups[0]
182                .rows
183                .iter()
184                .map(|r| r.path.to_str().unwrap())
185                .collect::<Vec<_>>(),
186            ["a.md", "c.md"]
187        );
188    }
189
190    /// The wart the split was for: a document under two groups is *one*
191    /// document, and `len` says so while `placements` counts the rows drawn.
192    #[test]
193    fn len_counts_documents_and_placements_counts_rows() {
194        let sel = selection(&[
195            ("letter.md", &[("people", seq(&["Ada", "Grace"]))]),
196            ("note.md", &[("people", seq(&["Ada"]))]),
197            ("bare.md", &[]),
198        ]);
199        let rows = group(&sel, &Grouping::field("people"));
200
201        assert_eq!(rows.len(), 3, "three documents");
202        assert_eq!(
203            rows.placements(),
204            4,
205            "Ada twice, Grace once, ungrouped once"
206        );
207        assert_eq!(rows.len(), sel.len(), "nothing selected went missing");
208    }
209
210    /// A repeated value is one membership, not two.
211    #[test]
212    fn a_repeated_value_does_not_double_a_row_within_its_group() {
213        let sel = selection(&[("letter.md", &[("people", seq(&["Ada", "Ada"]))])]);
214        let rows = group(&sel, &Grouping::field("people"));
215        assert_eq!(rows.groups.len(), 1);
216        assert_eq!(rows.groups[0].rows.len(), 1);
217    }
218
219    /// Grouping is total: every selected row is reachable afterwards.
220    #[test]
221    fn every_selected_row_lands_somewhere() {
222        let sel = selection(&[
223            ("a.md", &[("created", text("2026-07-24"))]),
224            ("b.md", &[("created", text("banana"))]),
225            ("c.md", &[]),
226        ]);
227        let rows = group(
228            &sel,
229            &Grouping {
230                keys: vec!["created".into()],
231                by: Some(Grain::Year),
232            },
233        );
234        assert_eq!(rows.len(), 3);
235        assert_eq!(rows.ungrouped.len(), 2, "the unparseable and the absent");
236    }
237
238    /// One selection, several lenses — what borrowing rather than copying is
239    /// for, and what a frontend offering a view switcher actually does.
240    #[test]
241    fn one_selection_groups_several_ways_at_once() {
242        let sel = selection(&[(
243            "letter.md",
244            &[("people", seq(&["Ada"])), ("created", text("2026-07-24"))],
245        )]);
246        let by_people = group(&sel, &Grouping::field("people"));
247        let by_year = group(
248            &sel,
249            &Grouping {
250                keys: vec!["created".into()],
251                by: Some(Grain::Year),
252            },
253        );
254        assert_eq!(by_people.groups[0].key, "Ada");
255        assert_eq!(by_year.groups[0].key, "2026");
256        assert_eq!(
257            by_people.groups[0].rows[0].path,
258            by_year.groups[0].rows[0].path
259        );
260    }
261}
prov_views/group.rs

prov_views/
group.rs
