git_stack/graph/
mod.rs

1mod branch;
2mod commit;
3mod ops;
4
5pub use branch::*;
6pub use commit::*;
7pub use ops::*;
8
9use std::collections::BTreeMap;
10use std::collections::VecDeque;
11
12use crate::any::AnyId;
13use crate::any::BoxedEntry;
14use crate::any::BoxedResource;
15use crate::any::Resource;
16
17#[derive(Clone, Debug)]
18pub struct Graph {
19    graph: petgraph::graphmap::DiGraphMap<git2::Oid, usize>,
20    root_id: git2::Oid,
21    commits: BTreeMap<git2::Oid, BTreeMap<AnyId, BoxedResource>>,
22    pub branches: BranchSet,
23}
24
25impl Graph {
26    pub fn from_branches(
27        repo: &dyn crate::git::Repo,
28        branches: BranchSet,
29    ) -> crate::git::Result<Self> {
30        let mut root_id = None;
31        for branch_id in branches.oids() {
32            if let Some(old_root_id) = root_id {
33                root_id = repo.merge_base(old_root_id, branch_id);
34                if root_id.is_none() {
35                    return Err(git2::Error::new(
36                        git2::ErrorCode::NotFound,
37                        git2::ErrorClass::Reference,
38                        format!("no merge base between {old_root_id} and {branch_id}"),
39                    ));
40                }
41            } else {
42                root_id = Some(branch_id);
43            }
44        }
45        let root_id = root_id.ok_or_else(|| {
46            git2::Error::new(
47                git2::ErrorCode::NotFound,
48                git2::ErrorClass::Reference,
49                "at least one branch is required to make a graph",
50            )
51        })?;
52
53        let mut graph = Graph::with_base_id(root_id);
54        graph.branches = branches;
55        for branch_id in graph.branches.oids() {
56            for commit_id in crate::git::commit_range(repo, branch_id..root_id)? {
57                for (weight, parent_id) in repo.parent_ids(commit_id)?.into_iter().enumerate() {
58                    graph.graph.add_edge(commit_id, parent_id, weight);
59                }
60            }
61        }
62
63        Ok(graph)
64    }
65
66    pub fn insert(&mut self, node: Node, parent_id: git2::Oid) {
67        assert!(
68            self.contains_id(parent_id),
69            "expected to contain {parent_id}",
70        );
71        let Node {
72            id,
73            branches,
74            commit,
75        } = node;
76        self.graph.add_edge(id, parent_id, 0);
77        for branch in branches.into_iter().flatten() {
78            self.branches.insert(branch);
79        }
80        if let Some(commit) = commit {
81            self.commits.insert(id, commit);
82        }
83    }
84
85    pub fn rebase(&mut self, id: git2::Oid, from: git2::Oid, to: git2::Oid) {
86        assert!(self.contains_id(id), "expected to contain {id}");
87        assert!(self.contains_id(from), "expected to contain {from}");
88        assert!(self.contains_id(to), "expected to contain {to}");
89        assert_eq!(
90            self.parents_of(id).find(|parent| *parent == from),
91            Some(from)
92        );
93        assert_ne!(id, self.root_id, "Cannot rebase root ({id})");
94        let weight = self.graph.remove_edge(id, from).unwrap();
95        self.graph.add_edge(id, to, weight);
96    }
97
98    pub fn remove(&mut self, id: git2::Oid) -> Option<Node> {
99        assert_ne!(id, self.root_id, "Cannot remove root ({id})");
100        let children = self.children_of(id).collect::<Vec<_>>();
101        if !children.is_empty() {
102            let parents = self.parents_of(id).collect::<Vec<_>>();
103            for child_id in children.iter().copied() {
104                for (weight, parent_id) in parents.iter().copied().enumerate() {
105                    self.graph.add_edge(child_id, parent_id, weight);
106                }
107            }
108        }
109        self.graph.remove_node(id).then(|| {
110            let branches = self.branches.remove(id);
111            let commit = self.commits.remove(&id);
112            Node {
113                id,
114                commit,
115                branches,
116            }
117        })
118    }
119}
120
121impl Graph {
122    pub fn with_base_id(root_id: git2::Oid) -> Self {
123        let mut graph = petgraph::graphmap::DiGraphMap::new();
124        graph.add_node(root_id);
125        let commits = BTreeMap::new();
126        let branches = BranchSet::new();
127        Self {
128            graph,
129            root_id,
130            commits,
131            branches,
132        }
133    }
134
135    pub fn root_id(&self) -> git2::Oid {
136        self.root_id
137    }
138
139    pub fn contains_id(&self, id: git2::Oid) -> bool {
140        self.graph.contains_node(id)
141    }
142
143    pub fn primary_parent_of(&self, root_id: git2::Oid) -> Option<git2::Oid> {
144        self.graph
145            .edges_directed(root_id, petgraph::Direction::Outgoing)
146            .find_map(|(_child, parent, weight)| (*weight == 0).then_some(parent))
147    }
148
149    pub fn parents_of(
150        &self,
151        root_id: git2::Oid,
152    ) -> petgraph::graphmap::NeighborsDirected<'_, git2::Oid, petgraph::Directed> {
153        self.graph
154            .neighbors_directed(root_id, petgraph::Direction::Outgoing)
155    }
156
157    pub fn children_of(
158        &self,
159        root_id: git2::Oid,
160    ) -> petgraph::graphmap::NeighborsDirected<'_, git2::Oid, petgraph::Directed> {
161        self.graph
162            .neighbors_directed(root_id, petgraph::Direction::Incoming)
163    }
164
165    pub fn ancestors_of(&self, root_id: git2::Oid) -> AncestorsIter<'_> {
166        let cursor = AncestorsCursor::new(self, root_id);
167        AncestorsIter {
168            cursor,
169            graph: self,
170        }
171    }
172
173    pub fn descendants(&self) -> DescendantsIter<'_> {
174        self.descendants_of(self.root_id)
175    }
176
177    pub fn descendants_of(&self, root_id: git2::Oid) -> DescendantsIter<'_> {
178        let cursor = DescendantsCursor::new(self, root_id);
179        DescendantsIter {
180            cursor,
181            graph: self,
182        }
183    }
184
185    pub fn commit_get<R: Resource>(&self, id: git2::Oid) -> Option<&R> {
186        let commit = self.commits.get(&id)?;
187        let boxed_resource = commit.get(&AnyId::of::<R>())?;
188        let resource = boxed_resource.as_ref::<R>();
189        Some(resource)
190    }
191
192    pub fn commit_get_mut<R: Resource>(&mut self, id: git2::Oid) -> Option<&mut R> {
193        let commit = self.commits.get_mut(&id)?;
194        let boxed_resource = commit.get_mut(&AnyId::of::<R>())?;
195        let resource = boxed_resource.as_mut::<R>();
196        Some(resource)
197    }
198
199    pub fn commit_set<R: Into<BoxedEntry>>(&mut self, id: git2::Oid, r: R) -> bool {
200        let BoxedEntry { id: key, value } = r.into();
201        self.commits
202            .entry(id)
203            .or_default()
204            .insert(key, value)
205            .is_some()
206    }
207}
208
209#[derive(Debug)]
210pub struct Node {
211    id: git2::Oid,
212    commit: Option<BTreeMap<AnyId, BoxedResource>>,
213    branches: Option<Vec<Branch>>,
214}
215
216impl Node {
217    pub fn new(id: git2::Oid) -> Self {
218        Self {
219            id,
220            commit: None,
221            branches: None,
222        }
223    }
224}
225
226#[derive(Debug)]
227pub struct AncestorsIter<'g> {
228    cursor: AncestorsCursor,
229    graph: &'g Graph,
230}
231
232impl AncestorsIter<'_> {
233    pub fn into_cursor(self) -> AncestorsCursor {
234        self.cursor
235    }
236}
237
238impl Iterator for AncestorsIter<'_> {
239    type Item = git2::Oid;
240
241    fn next(&mut self) -> Option<Self::Item> {
242        self.cursor.next(self.graph)
243    }
244}
245
246#[derive(Debug)]
247pub struct AncestorsCursor {
248    node_queue: VecDeque<git2::Oid>,
249    primary_parents: bool,
250    prior: Option<git2::Oid>,
251    seen: std::collections::HashSet<git2::Oid>,
252}
253
254impl AncestorsCursor {
255    fn new(graph: &Graph, root_id: git2::Oid) -> Self {
256        let mut node_queue = VecDeque::new();
257        if graph.graph.contains_node(root_id) {
258            node_queue.push_back(root_id);
259        }
260        Self {
261            node_queue,
262            primary_parents: false,
263            prior: None,
264            seen: Default::default(),
265        }
266    }
267
268    pub fn primary_parents(mut self, yes: bool) -> Self {
269        self.primary_parents = yes;
270        self
271    }
272}
273
274impl AncestorsCursor {
275    pub fn next(&mut self, graph: &Graph) -> Option<git2::Oid> {
276        if let Some(prior) = self.prior {
277            if self.primary_parents {
278                // Single path, no chance for duplicating paths
279                self.node_queue.extend(graph.primary_parent_of(prior));
280            } else {
281                for parent_id in graph.parents_of(prior) {
282                    if self.seen.insert(parent_id) {
283                        self.node_queue.push_back(parent_id);
284                    }
285                }
286            }
287        }
288        let next = self.node_queue.pop_front()?;
289        self.prior = Some(next);
290        Some(next)
291    }
292
293    pub fn stop(&mut self) {
294        self.prior = None;
295    }
296}
297
298#[derive(Debug)]
299pub struct DescendantsIter<'g> {
300    cursor: DescendantsCursor,
301    graph: &'g Graph,
302}
303
304impl DescendantsIter<'_> {
305    pub fn into_cursor(self) -> DescendantsCursor {
306        self.cursor
307    }
308}
309
310impl Iterator for DescendantsIter<'_> {
311    type Item = git2::Oid;
312
313    fn next(&mut self) -> Option<Self::Item> {
314        self.cursor.next(self.graph)
315    }
316}
317
318#[derive(Debug)]
319pub struct DescendantsCursor {
320    node_queue: VecDeque<git2::Oid>,
321    prior: Option<git2::Oid>,
322}
323
324impl DescendantsCursor {
325    fn new(graph: &Graph, root_id: git2::Oid) -> Self {
326        let mut node_queue = VecDeque::new();
327        if graph.graph.contains_node(root_id) {
328            node_queue.push_back(root_id);
329        }
330        Self {
331            node_queue,
332            prior: None,
333        }
334    }
335}
336
337impl DescendantsCursor {
338    pub fn next(&mut self, graph: &Graph) -> Option<git2::Oid> {
339        if let Some(prior) = self.prior {
340            self.node_queue.extend(graph.children_of(prior));
341        }
342        let next = self.node_queue.pop_front()?;
343        self.prior = Some(next);
344        Some(next)
345    }
346
347    pub fn stop(&mut self) {
348        self.prior = None;
349    }
350}
git_stack/graph/mod.rs

git_stack/graph/
mod.rs
