review_queue/
stacks.rs

1//! Groups tracked reviews into stacks, derived from each review's `ancestors` on every call
2//! rather than stored: membership changes as revisions land or get reordered, so a stored copy
3//! would just go stale.
4//!
5//! A stack is a root-to-leaf chain. A lone review is a stack of one. If a chain forks (two
6//! reviews share a parent), each leaf gets its own stack, and the shared ancestors belong to
7//! whichever leaf sorts first.
8
9use std::collections::{BTreeMap, BTreeSet};
10
11use crate::state::{ReviewEntry, ReviewKey};
12
13#[derive(Debug, Clone, PartialEq, Eq)]
14pub struct Stack {
15    /// The top-most member - the review a workspace for this stack is built from.
16    pub tip: ReviewKey,
17    /// The tracked members, bottom-most first. Ancestors that aren't tracked (you're not a
18    /// reviewer on them) don't appear here, though they're part of the stack's contents.
19    pub members: Vec<ReviewKey>,
20}
21
22/// Group `entries` into stacks. Resolved entries are ignored: a landed review is already part of
23/// its descendants' base, not of the stack.
24pub fn group<'a>(entries: impl IntoIterator<Item = &'a ReviewEntry>) -> Vec<Stack> {
25    let live: BTreeMap<&ReviewKey, &ReviewEntry> = entries
26        .into_iter()
27        .filter(|e| !e.resolved)
28        .map(|e| (&e.key, e))
29        .collect();
30
31    let ancestors_of_something: BTreeSet<&ReviewKey> =
32        live.values().flat_map(|e| e.ancestors.iter()).collect();
33
34    let mut assigned: BTreeSet<&ReviewKey> = BTreeSet::new();
35    let mut stacks = Vec::new();
36    // `live` is a BTreeMap, so leaves are visited in key order: deterministic.
37    for (key, entry) in &live {
38        if ancestors_of_something.contains(key) {
39            continue;
40        }
41        let members: Vec<ReviewKey> = entry
42            .ancestors
43            .iter()
44            .chain(std::iter::once(*key))
45            .filter(|k| live.contains_key(k) && assigned.insert(k))
46            .cloned()
47            .collect();
48        stacks.push(Stack {
49            tip: (*key).clone(),
50            members,
51        });
52    }
53
54    // Inconsistent data (an ancestor list that doesn't reach a member) shouldn't hide a review.
55    for key in live.keys() {
56        if assigned.insert(key) {
57            stacks.push(Stack {
58                tip: (*key).clone(),
59                members: vec![(*key).clone()],
60            });
61        }
62    }
63    stacks
64}
65
66/// The stack containing `key`, if it's tracked and unresolved.
67pub fn stack_containing<'a>(stacks: &'a [Stack], key: &ReviewKey) -> Option<&'a Stack> {
68    stacks.iter().find(|s| s.members.contains(key))
69}
70
71#[cfg(test)]
72mod tests {
73    use super::*;
74    use crate::source::{RepoRef, ReviewKind};
75
76    fn k(id: &str) -> ReviewKey {
77        ReviewKey::new("moz", id)
78    }
79
80    fn entry(id: &str, ancestors: &[&str]) -> ReviewEntry {
81        ReviewEntry {
82            key: k(id),
83            title: String::new(),
84            author: String::new(),
85            url: String::new(),
86            repo: RepoRef {
87                urls: vec![],
88                display_name: String::new(),
89            },
90            kind: ReviewKind::Direct,
91            version: "1".into(),
92            in_queue: true,
93            resolved: false,
94            last_synced: chrono::Utc::now(),
95            stack_id: None,
96            ancestors: ancestors.iter().map(|a| k(a)).collect(),
97            diff_stat: None,
98            description: None,
99        }
100    }
101
102    #[test]
103    fn lone_reviews_are_stacks_of_one() {
104        let entries = [entry("D1", &[]), entry("D2", &[])];
105        let stacks = group(&entries);
106        assert_eq!(stacks.len(), 2);
107        assert_eq!(stacks[0].members, vec![k("D1")]);
108    }
109
110    #[test]
111    fn chain_groups_bottom_to_top() {
112        let entries = [
113            entry("D3", &["D1", "D2"]),
114            entry("D1", &[]),
115            entry("D2", &["D1"]),
116        ];
117        let stacks = group(&entries);
118        assert_eq!(stacks.len(), 1);
119        assert_eq!(stacks[0].tip, k("D3"));
120        assert_eq!(stacks[0].members, vec![k("D1"), k("D2"), k("D3")]);
121    }
122
123    #[test]
124    fn untracked_ancestors_are_skipped_but_still_link_members() {
125        // D9 isn't tracked (not our review), yet D1 and D3 are still one stack through it.
126        let entries = [entry("D1", &[]), entry("D3", &["D1", "D9"])];
127        let stacks = group(&entries);
128        assert_eq!(stacks.len(), 1);
129        assert_eq!(stacks[0].members, vec![k("D1"), k("D3")]);
130    }
131
132    #[test]
133    fn a_fork_gives_each_leaf_its_own_stack_and_the_shared_parent_to_the_first() {
134        let entries = [entry("D1", &[]), entry("D2", &["D1"]), entry("D3", &["D1"])];
135        let stacks = group(&entries);
136        assert_eq!(stacks.len(), 2);
137        assert_eq!(stacks[0].members, vec![k("D1"), k("D2")]);
138        assert_eq!(stacks[1].members, vec![k("D3")]);
139    }
140
141    #[test]
142    fn resolved_entries_are_ignored() {
143        let mut d1 = entry("D1", &[]);
144        d1.resolved = true;
145        let entries = [d1, entry("D2", &[])];
146        let stacks = group(&entries);
147        assert_eq!(stacks.len(), 1);
148        assert_eq!(stacks[0].members, vec![k("D2")]);
149    }
150}
review_queue/stacks.rs

review_queue/
stacks.rs
