ephemeris_release/proposal/
groups.rs

1//! Release units grouped and ordered for one commit each.
2
3use std::collections::{BTreeMap, BTreeSet};
4
5use super::ProposalError;
6use crate::unit::Unit;
7use crate::version::Proposed;
8
9/// Units that move to one version in one commit.
10#[derive(Clone, Debug, Eq, PartialEq)]
11pub(super) struct ReleaseGroup {
12    units: BTreeSet<String>,
13}
14
15impl ReleaseGroup {
16    /// Group the proposed units, each shared group as one and every other
17    /// unit alone, so that a group follows the groups it depends on. Ties
18    /// go by unit name.
19    pub(super) fn ordered(
20        units: &[Unit],
21        proposed: &BTreeMap<String, Proposed>,
22        shared: &[BTreeSet<String>],
23    ) -> Result<Vec<Self>, ProposalError> {
24        let mut groups: BTreeMap<String, BTreeSet<String>> = BTreeMap::new();
25        let mut leaders: BTreeMap<&str, String> = BTreeMap::new();
26        for name in proposed.keys() {
27            if leaders.contains_key(name.as_str()) {
28                continue;
29            }
30            let group: BTreeSet<String> = shared
31                .iter()
32                .find(|group| group.contains(name))
33                .map_or_else(
34                    || BTreeSet::from([name.clone()]),
35                    |group| {
36                        group
37                            .iter()
38                            .filter(|member| proposed.contains_key(*member))
39                            .cloned()
40                            .collect()
41                    },
42                );
43            let leader = group.first().unwrap_or(name).clone();
44            for member in proposed.keys().filter(|member| group.contains(*member)) {
45                leaders.insert(member, leader.clone());
46            }
47            groups.insert(leader, group);
48        }
49        let mut waiting: BTreeMap<String, BTreeSet<String>> = groups
50            .iter()
51            .map(|(leader, group)| {
52                let dependencies = units
53                    .iter()
54                    .filter(|unit| group.contains(&unit.name))
55                    .flat_map(|unit| &unit.dependencies)
56                    .filter_map(|dependency| leaders.get(dependency.as_str()))
57                    .filter(|other| *other != leader)
58                    .cloned()
59                    .collect();
60                (leader.clone(), dependencies)
61            })
62            .collect();
63        let mut ordered = Vec::new();
64        while let Some(leader) = waiting
65            .iter()
66            .find_map(|(leader, pending)| pending.is_empty().then(|| leader.clone()))
67        {
68            waiting.remove(&leader);
69            for pending in waiting.values_mut() {
70                pending.remove(&leader);
71            }
72            if let Some(members) = groups.remove(&leader) {
73                ordered.push(Self { units: members });
74            }
75        }
76        if waiting.is_empty() {
77            Ok(ordered)
78        } else {
79            Err(ProposalError::DependencyCycle {
80                units: groups.into_values().flatten().collect(),
81            })
82        }
83    }
84
85    /// The unit names in name order.
86    pub(super) fn units(&self) -> impl Iterator<Item = &str> {
87        self.units.iter().map(String::as_str)
88    }
89
90    /// Whether `name` belongs to the group.
91    pub(super) fn contains(&self, name: &str) -> bool {
92        self.units.contains(name)
93    }
94}
95
96#[cfg(test)]
97mod tests {
98    use std::collections::{BTreeMap, BTreeSet};
99
100    use super::ReleaseGroup;
101    use crate::proposal::ProposalError;
102    use crate::state::ReleaseUnitState;
103    use crate::unit::Unit;
104    use crate::version::Proposed;
105
106    fn unit(name: &str, dependencies: &[&str]) -> Unit {
107        let state: ReleaseUnitState = facet_json::from_str(
108            r#"{"target":{"ecosystem":"version-file","version_file":"VERSION"},"source":["."],"changelog":"CHANGELOG.md","dependencies":[],"pins":{},"tag_prefix":"v","kind":"library","application_bump":"none","revision_file":null}"#,
109        )
110        .unwrap();
111        let mut unit = Unit::configured(name, None, "1.0.0".parse().unwrap(), &state);
112        unit.dependencies = dependencies
113            .iter()
114            .map(|dependency| (*dependency).to_owned())
115            .collect();
116        unit
117    }
118
119    fn proposed(names: &[&str]) -> BTreeMap<String, Proposed> {
120        names
121            .iter()
122            .map(|name| ((*name).to_owned(), Proposed::Bump("2.0.0".parse().unwrap())))
123            .collect()
124    }
125
126    fn names(groups: &[ReleaseGroup]) -> Vec<Vec<&str>> {
127        groups.iter().map(|group| group.units().collect()).collect()
128    }
129
130    #[test]
131    fn dependencies_come_first_and_ties_go_by_name() {
132        let units = [
133            unit("a", &["z"]),
134            unit("b", &[]),
135            unit("z", &[]),
136            unit("y", &["b"]),
137        ];
138        let groups = ReleaseGroup::ordered(&units, &proposed(&["a", "b", "y", "z"]), &[]).unwrap();
139        assert_eq!(names(&groups), [["b"], ["y"], ["z"], ["a"]]);
140    }
141
142    #[test]
143    fn a_shared_group_is_one_group() {
144        let units = [unit("a", &["c"]), unit("b", &[]), unit("c", &[])];
145        let shared = [BTreeSet::from(["a".to_owned(), "b".to_owned()])];
146        let groups = ReleaseGroup::ordered(&units, &proposed(&["a", "b", "c"]), &shared).unwrap();
147        assert_eq!(names(&groups), [vec!["c"], vec!["a", "b"]]);
148    }
149
150    #[test]
151    fn a_cycle_is_an_error() {
152        let units = [unit("a", &["b"]), unit("b", &["a"])];
153        assert!(matches!(
154            ReleaseGroup::ordered(&units, &proposed(&["a", "b"]), &[]),
155            Err(ProposalError::DependencyCycle { units }) if units == ["a", "b"]
156        ));
157    }
158}
ephemeris_release/proposal/groups.rs

ephemeris_release/proposal/
groups.rs
