1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
use gix_hash::{oid, ObjectId};
use gix_revwalk::{graph::IdMap, PriorityQueue};
use crate::commit::{
find,
topo::{iter::gen_and_commit_time, Error, Sorting, WalkFlags},
Info, Parents, Topo,
};
/// Builder for [`Topo`].
pub struct Builder<Find, Predicate> {
commit_graph: Option<gix_commitgraph::Graph>,
find: Find,
predicate: Predicate,
sorting: Sorting,
parents: Parents,
tips: Vec<ObjectId>,
ends: Vec<ObjectId>,
}
impl<Find> Builder<Find, fn(&oid) -> bool>
where
Find: gix_object::Find,
{
/// Create a new `Builder` for a [`Topo`] that reads commits from a repository with `find`.
/// starting at the `tips` and ending at the `ends`. Like `git rev-list
/// --topo-order ^ends tips`.
pub fn from_iters(
find: Find,
tips: impl IntoIterator<Item = impl Into<ObjectId>>,
ends: Option<impl IntoIterator<Item = impl Into<ObjectId>>>,
) -> Self {
Self::new(find).with_tips(tips).with_ends(ends.into_iter().flatten())
}
/// Create a new `Builder` for a [`Topo`] that reads commits from a
/// repository with `find`.
pub fn new(find: Find) -> Self {
Self {
commit_graph: Default::default(),
find,
sorting: Default::default(),
parents: Default::default(),
tips: Default::default(),
ends: Default::default(),
predicate: |_| true,
}
}
/// Set a `predicate` to filter out revisions from the walk. Can be used to
/// implement e.g. filtering on paths or time. This does *not* exclude the
/// parent(s) of a revision that is excluded. Specify a revision as an 'end'
/// if you want that behavior.
pub fn with_predicate<Predicate>(self, predicate: Predicate) -> Builder<Find, Predicate>
where
Predicate: FnMut(&oid) -> bool,
{
Builder {
commit_graph: self.commit_graph,
find: self.find,
sorting: self.sorting,
parents: self.parents,
tips: self.tips,
ends: self.ends,
predicate,
}
}
}
impl<Find, Predicate> Builder<Find, Predicate>
where
Find: gix_object::Find,
Predicate: FnMut(&oid) -> bool,
{
/// Add commits to start reading from.
///
/// The behavior is similar to specifying additional `ends` in `git rev-list --topo-order ^ends tips`.
pub fn with_tips(mut self, tips: impl IntoIterator<Item = impl Into<ObjectId>>) -> Self {
self.tips.extend(tips.into_iter().map(Into::into));
self
}
/// Add commits ending the traversal.
///
/// These commits themselves will not be read, i.e. the behavior is similar to specifying additional
/// `ends` in `git rev-list --topo-order ^ends tips`.
pub fn with_ends(mut self, ends: impl IntoIterator<Item = impl Into<ObjectId>>) -> Self {
self.ends.extend(ends.into_iter().map(Into::into));
self
}
/// Set the `sorting` to use for the topological walk.
pub fn sorting(mut self, sorting: Sorting) -> Self {
self.sorting = sorting;
self
}
/// Specify how to handle commit `parents` during traversal.
pub fn parents(mut self, parents: Parents) -> Self {
self.parents = parents;
self
}
/// Set or unset the `commit_graph` to use for the iteration.
pub fn with_commit_graph(mut self, commit_graph: Option<gix_commitgraph::Graph>) -> Self {
self.commit_graph = commit_graph;
self
}
/// Build a new [`Topo`] instance.
///
/// Note that merely building an instance is currently expensive.
pub fn build(self) -> Result<Topo<Find, Predicate>, Error> {
let mut w = Topo {
commit_graph: self.commit_graph,
find: self.find,
predicate: self.predicate,
indegrees: IdMap::default(),
states: IdMap::default(),
explore_queue: PriorityQueue::new(),
indegree_queue: PriorityQueue::new(),
topo_queue: super::iter::Queue::new(self.sorting),
parents: self.parents,
min_gen: gix_commitgraph::GENERATION_NUMBER_INFINITY,
buf: vec![],
};
// Initial flags for the states of the tips and ends. All of them are
// seen and added to the explore and indegree queues. The ends are by
// definition (?) uninteresting and bottom.
let tip_flags = WalkFlags::Seen | WalkFlags::Explored | WalkFlags::InDegree;
let end_flags = tip_flags | WalkFlags::Uninteresting | WalkFlags::Bottom;
for (id, flags) in self
.tips
.iter()
.map(|id| (id, tip_flags))
.chain(self.ends.iter().map(|id| (id, end_flags)))
{
*w.indegrees.entry(*id).or_default() = 1;
let commit = find(w.commit_graph.as_ref(), &w.find, id, &mut w.buf)?;
let (gen, time) = gen_and_commit_time(commit)?;
if gen < w.min_gen {
w.min_gen = gen;
}
w.states.insert(*id, flags);
w.explore_queue.insert((gen, time), *id);
w.indegree_queue.insert((gen, time), *id);
}
// NOTE: Parents of the ends must also be marked uninteresting for some
// reason. See handle_commit()
for id in &self.ends {
let parents = w.collect_all_parents(id)?;
for (id, _) in parents {
w.states
.entry(id)
.and_modify(|s| *s |= WalkFlags::Uninteresting)
.or_insert(WalkFlags::Uninteresting | WalkFlags::Seen);
}
}
w.compute_indegrees_to_depth(w.min_gen)?;
// NOTE: in Git the ends are also added to the topo_queue in addition to
// the tips, but then in simplify_commit() Git is told to ignore it. For
// now the tests pass.
for id in self.tips.iter() {
let i = w.indegrees.get(id).ok_or(Error::MissingIndegreeUnexpected)?;
if *i != 1 {
continue;
}
let commit = find(w.commit_graph.as_ref(), &w.find, id, &mut w.buf)?;
let (_, time) = gen_and_commit_time(commit)?;
let parent_ids = w.collect_all_parents(id)?.into_iter().map(|e| e.0).collect();
w.topo_queue.push(
time,
Info {
id: *id,
parent_ids,
commit_time: Some(time),
},
);
}
w.topo_queue.initial_sort();
Ok(w)
}
}