/src/gitoxide/gix-traverse/src/commit/topo/iter.rs

Source
use gix_hash::{oid, ObjectId};
use gix_revwalk::PriorityQueue;
use smallvec::SmallVec;

use crate::commit::{
    find,
    topo::{Error, Sorting, WalkFlags},
    Either, Info, Parents, Topo,
};

pub(in crate::commit) type GenAndCommitTime = (u32, i64);

// Git's priority queue works as a LIFO stack if no compare function is set,
// which is the case for `--topo-order.` However, even in that case the initial
// items of the queue are sorted according to the commit time before beginning
// the walk.
#[derive(Debug)]
pub(in crate::commit) enum Queue {
    Date(PriorityQueue<i64, Info>),
    Topo(Vec<(i64, Info)>),
}

impl Queue {
    pub(super) fn new(s: Sorting) -> Self {
        match s {
            Sorting::DateOrder => Self::Date(PriorityQueue::new()),
            Sorting::TopoOrder => Self::Topo(vec![]),
        }
    }

    pub(super) fn push(&mut self, commit_time: i64, info: Info) {
        match self {
            Self::Date(q) => q.insert(commit_time, info),
            Self::Topo(q) => q.push((commit_time, info)),
        }
    }

    fn pop(&mut self) -> Option<Info> {
        match self {
            Self::Date(q) => q.pop().map(|(_, info)| info),
            Self::Topo(q) => q.pop().map(|(_, info)| info),
        }
    }

    pub(super) fn initial_sort(&mut self) {
        if let Self::Topo(ref mut inner_vec) = self {
            inner_vec.sort_by(|a, b| a.0.cmp(&b.0));
        }
    }
}

impl<Find, Predicate> Topo<Find, Predicate>
where
    Find: gix_object::Find,
{
    pub(super) fn compute_indegrees_to_depth(&mut self, gen_cutoff: u32) -> Result<(), Error> {
        while let Some(((gen, _), _)) = self.indegree_queue.peek() {
            if *gen >= gen_cutoff {
                self.indegree_walk_step()?;
            } else {
                break;
            }
        }

        Ok(())
    }

    fn indegree_walk_step(&mut self) -> Result<(), Error> {
        if let Some(((gen, _), id)) = self.indegree_queue.pop() {
            self.explore_to_depth(gen)?;

            let parents = self.collect_parents(&id)?;
            for (id, gen_time) in parents {
                self.indegrees.entry(id).and_modify(|e| *e += 1).or_insert(2);

                let state = self.states.get_mut(&id).ok_or(Error::MissingStateUnexpected)?;
                if !state.contains(WalkFlags::InDegree) {
                    *state |= WalkFlags::InDegree;
                    self.indegree_queue.insert(gen_time, id);
                }
            }
        }
        Ok(())
    }

    fn explore_to_depth(&mut self, gen_cutoff: u32) -> Result<(), Error> {
        while let Some(((gen, _), _)) = self.explore_queue.peek() {
            if *gen >= gen_cutoff {
                self.explore_walk_step()?;
            } else {
                break;
            }
        }
        Ok(())
    }

    fn explore_walk_step(&mut self) -> Result<(), Error> {
        if let Some((_, id)) = self.explore_queue.pop() {
            let parents = self.collect_parents(&id)?;
            self.process_parents(&id, &parents)?;

            for (id, gen_time) in parents {
                let state = self.states.get_mut(&id).ok_or(Error::MissingStateUnexpected)?;

                if !state.contains(WalkFlags::Explored) {
                    *state |= WalkFlags::Explored;
                    self.explore_queue.insert(gen_time, id);
                }
            }
        }
        Ok(())
    }

    fn expand_topo_walk(&mut self, id: &oid) -> Result<(), Error> {
        let parents = self.collect_parents(id)?;
        self.process_parents(id, &parents)?;

        for (pid, (parent_gen, parent_commit_time)) in parents {
            let parent_state = self.states.get(&pid).ok_or(Error::MissingStateUnexpected)?;
            if parent_state.contains(WalkFlags::Uninteresting) {
                continue;
            }

            if parent_gen < self.min_gen {
                self.min_gen = parent_gen;
                self.compute_indegrees_to_depth(self.min_gen)?;
            }

            let i = self.indegrees.get_mut(&pid).ok_or(Error::MissingIndegreeUnexpected)?;
            *i -= 1;
            if *i != 1 {
                continue;
            }

            let parent_ids = self.collect_all_parents(&pid)?.into_iter().map(|e| e.0).collect();
            self.topo_queue.push(
                parent_commit_time,
                Info {
                    id: pid,
                    parent_ids,
                    commit_time: Some(parent_commit_time),
                },
            );
        }

        Ok(())
    }

    fn process_parents(&mut self, id: &oid, parents: &[(ObjectId, GenAndCommitTime)]) -> Result<(), Error> {
        let state = self.states.get_mut(id).ok_or(Error::MissingStateUnexpected)?;
        if state.contains(WalkFlags::Added) {
            return Ok(());
        }

        *state |= WalkFlags::Added;

        // If the current commit is uninteresting we pass that on to ALL
        // parents, otherwise we set the Seen flag.
        let (pass, insert) = if state.contains(WalkFlags::Uninteresting) {
            let flags = WalkFlags::Uninteresting;
            for (id, _) in parents {
                let grand_parents = self.collect_all_parents(id)?;

                for (id, _) in &grand_parents {
                    self.states
                        .entry(*id)
                        .and_modify(|s| *s |= WalkFlags::Uninteresting)
                        .or_insert(WalkFlags::Uninteresting | WalkFlags::Seen);
                }
            }
            (flags, flags)
        } else {
            // NOTE: git sets SEEN like we do but keeps the SYMMETRIC_LEFT and
            // ANCENSTRY_PATH if they are set, but they have no purpose here.
            let flags = WalkFlags::empty();
            (flags, WalkFlags::Seen)
        };

        for (id, _) in parents {
            self.states.entry(*id).and_modify(|s| *s |= pass).or_insert(insert);
        }
        Ok(())
    }

    fn collect_parents(&mut self, id: &oid) -> Result<SmallVec<[(ObjectId, GenAndCommitTime); 1]>, Error> {
        collect_parents(
            &mut self.commit_graph,
            &self.find,
            id,
            matches!(self.parents, Parents::First),
            &mut self.buf,
        )
    }

    // Same as collect_parents but disregards the first_parent flag
    pub(super) fn collect_all_parents(
        &mut self,
        id: &oid,
    ) -> Result<SmallVec<[(ObjectId, GenAndCommitTime); 1]>, Error> {
        collect_parents(&mut self.commit_graph, &self.find, id, false, &mut self.buf)
    }

    fn pop_commit(&mut self) -> Option<Result<Info, Error>> {
        let commit = self.topo_queue.pop()?;
        let i = match self.indegrees.get_mut(&commit.id) {
            Some(i) => i,
            None => {
                return Some(Err(Error::MissingIndegreeUnexpected));
            }
        };

        *i = 0;
        if let Err(e) = self.expand_topo_walk(&commit.id) {
            return Some(Err(e));
        }

        Some(Ok(commit))
    }
}

impl<Find, Predicate> Iterator for Topo<Find, Predicate>
where
    Find: gix_object::Find,
    Predicate: FnMut(&oid) -> bool,
{
    type Item = Result<Info, Error>;

    fn next(&mut self) -> Option<Self::Item> {
        loop {
            match self.pop_commit()? {
                Ok(id) => {
                    if (self.predicate)(&id.id) {
                        return Some(Ok(id));
                    }
                }
                Err(e) => return Some(Err(e)),
            }
        }
    }
}

fn collect_parents<Find>(
    cache: &mut Option<gix_commitgraph::Graph>,
    f: Find,
    id: &oid,
    first_only: bool,
    buf: &mut Vec<u8>,
) -> Result<SmallVec<[(ObjectId, GenAndCommitTime); 1]>, Error>
where
    Find: gix_object::Find,
{
    let mut parents = SmallVec::<[(ObjectId, GenAndCommitTime); 1]>::new();
    match find(cache.as_ref(), &f, id, buf)? {
        Either::CommitRefIter(c) => {
            for token in c {
                use gix_object::commit::ref_iter::Token as T;
                match token {
                    Ok(T::Tree { .. }) => continue,
                    Ok(T::Parent { id }) => {
                        parents.push((id, (0, 0))); // Dummy numbers to be filled in
                        if first_only {
                            break;
                        }
                    }
                    Ok(_past_parents) => break,
                    Err(err) => return Err(err.into()),
                }
            }
            // Need to check the cache again. That a commit is not in the cache
            // doesn't mean a parent is not.
            for (id, gen_time) in parents.iter_mut() {
                let commit = find(cache.as_ref(), &f, id, buf)?;
                *gen_time = gen_and_commit_time(commit)?;
            }
        }
        Either::CachedCommit(c) => {
            for pos in c.iter_parents() {
                let Ok(pos) = pos else {
                    // drop corrupt cache and use ODB from now on.
                    *cache = None;
                    return collect_parents(cache, f, id, first_only, buf);
                };
                let parent_commit = cache
                    .as_ref()
                    .expect("cache exists if CachedCommit was returned")
                    .commit_at(pos);
                parents.push((
                    parent_commit.id().into(),
                    (parent_commit.generation(), parent_commit.committer_timestamp() as i64),
                ));
                if first_only {
                    break;
                }
            }
        }
    }
    Ok(parents)
}

pub(super) fn gen_and_commit_time(c: Either<'_, '_>) -> Result<GenAndCommitTime, Error> {
    match c {
        Either::CommitRefIter(c) => {
            let mut commit_time = 0;
            for token in c {
                use gix_object::commit::ref_iter::Token as T;
                match token {
                    Ok(T::Tree { .. }) => continue,
                    Ok(T::Parent { .. }) => continue,
                    Ok(T::Author { .. }) => continue,
                    Ok(T::Committer { signature }) => {
                        commit_time = signature.seconds();
                        break;
                    }
                    Ok(_unused_token) => break,
                    Err(err) => return Err(err.into()),
                }
            }
            Ok((gix_commitgraph::GENERATION_NUMBER_INFINITY, commit_time))
        }
        Either::CachedCommit(c) => Ok((c.generation(), c.committer_timestamp() as i64)),
    }
}

Coverage Report

Created: 2025-11-16 07:09

Line	Count	Source
1		use gix_hash::{oid, ObjectId};
2		use gix_revwalk::PriorityQueue;
3		use smallvec::SmallVec;
4
5		use crate::commit::{
6		find,
7		topo::{Error, Sorting, WalkFlags},
8		Either, Info, Parents, Topo,
9		};
10
11		pub(in crate::commit) type GenAndCommitTime = (u32, i64);
12
13		// Git's priority queue works as a LIFO stack if no compare function is set,
14		// which is the case for `--topo-order.` However, even in that case the initial
15		// items of the queue are sorted according to the commit time before beginning
16		// the walk.
17		#[derive(Debug)]
18		pub(in crate::commit) enum Queue {
19		Date(PriorityQueue<i64, Info>),
20		Topo(Vec<(i64, Info)>),
21		}
22
23		impl Queue {
24	0	pub(super) fn new(s: Sorting) -> Self {
25	0	match s {
26	0	Sorting::DateOrder => Self::Date(PriorityQueue::new()),
27	0	Sorting::TopoOrder => Self::Topo(vec![]),
28		}
29	0	}
30
31	0	pub(super) fn push(&mut self, commit_time: i64, info: Info) {
32	0	match self {
33	0	Self::Date(q) => q.insert(commit_time, info),
34	0	Self::Topo(q) => q.push((commit_time, info)),
35		}
36	0	}
37
38	0	fn pop(&mut self) -> Option<Info> {
39	0	match self {
40	0	Self::Date(q) => q.pop().map(\|(_, info)\| info),
41	0	Self::Topo(q) => q.pop().map(\|(_, info)\| info),
42		}
43	0	}
44
45	0	pub(super) fn initial_sort(&mut self) {
46	0	if let Self::Topo(ref mut inner_vec) = self {
47	0	inner_vec.sort_by(\|a, b\| a.0.cmp(&b.0));
48	0	}
49	0	}
50		}
51
52		impl<Find, Predicate> Topo<Find, Predicate>
53		where
54		Find: gix_object::Find,
55		{
56	0	pub(super) fn compute_indegrees_to_depth(&mut self, gen_cutoff: u32) -> Result<(), Error> {
57	0	while let Some(((gen, _), _)) = self.indegree_queue.peek() {
58	0	if *gen >= gen_cutoff {
59	0	self.indegree_walk_step()?;
60		} else {
61	0	break;
62		}
63		}
64
65	0	Ok(())
66	0	}
67
68	0	fn indegree_walk_step(&mut self) -> Result<(), Error> {
69	0	if let Some(((gen, _), id)) = self.indegree_queue.pop() {
70	0	self.explore_to_depth(gen)?;
71
72	0	let parents = self.collect_parents(&id)?;
73	0	for (id, gen_time) in parents {
74	0	self.indegrees.entry(id).and_modify(\|e\| *e += 1).or_insert(2);
75
76	0	let state = self.states.get_mut(&id).ok_or(Error::MissingStateUnexpected)?;
77	0	if !state.contains(WalkFlags::InDegree) {
78	0	*state \|= WalkFlags::InDegree;
79	0	self.indegree_queue.insert(gen_time, id);
80	0	}
81		}
82	0	}
83	0	Ok(())
84	0	}
85
86	0	fn explore_to_depth(&mut self, gen_cutoff: u32) -> Result<(), Error> {
87	0	while let Some(((gen, _), _)) = self.explore_queue.peek() {
88	0	if *gen >= gen_cutoff {
89	0	self.explore_walk_step()?;
90		} else {
91	0	break;
92		}
93		}
94	0	Ok(())
95	0	}
96
97	0	fn explore_walk_step(&mut self) -> Result<(), Error> {
98	0	if let Some((_, id)) = self.explore_queue.pop() {
99	0	let parents = self.collect_parents(&id)?;
100	0	self.process_parents(&id, &parents)?;
101
102	0	for (id, gen_time) in parents {
103	0	let state = self.states.get_mut(&id).ok_or(Error::MissingStateUnexpected)?;
104
105	0	if !state.contains(WalkFlags::Explored) {
106	0	*state \|= WalkFlags::Explored;
107	0	self.explore_queue.insert(gen_time, id);
108	0	}
109		}
110	0	}
111	0	Ok(())
112	0	}
113
114	0	fn expand_topo_walk(&mut self, id: &oid) -> Result<(), Error> {
115	0	let parents = self.collect_parents(id)?;
116	0	self.process_parents(id, &parents)?;
117
118	0	for (pid, (parent_gen, parent_commit_time)) in parents {
119	0	let parent_state = self.states.get(&pid).ok_or(Error::MissingStateUnexpected)?;
120	0	if parent_state.contains(WalkFlags::Uninteresting) {
121	0	continue;
122	0	}
123
124	0	if parent_gen < self.min_gen {
125	0	self.min_gen = parent_gen;
126	0	self.compute_indegrees_to_depth(self.min_gen)?;
127	0	}
128
129	0	let i = self.indegrees.get_mut(&pid).ok_or(Error::MissingIndegreeUnexpected)?;
130	0	*i -= 1;
131	0	if *i != 1 {
132	0	continue;
133	0	}
134
135	0	let parent_ids = self.collect_all_parents(&pid)?.into_iter().map(\|e\| e.0).collect();
136	0	self.topo_queue.push(
137	0	parent_commit_time,
138	0	Info {
139	0	id: pid,
140	0	parent_ids,
141	0	commit_time: Some(parent_commit_time),
142	0	},
143		);
144		}
145
146	0	Ok(())
147	0	}
148
149	0	fn process_parents(&mut self, id: &oid, parents: &[(ObjectId, GenAndCommitTime)]) -> Result<(), Error> {
150	0	let state = self.states.get_mut(id).ok_or(Error::MissingStateUnexpected)?;
151	0	if state.contains(WalkFlags::Added) {
152	0	return Ok(());
153	0	}
154
155	0	*state \|= WalkFlags::Added;
156
157		// If the current commit is uninteresting we pass that on to ALL
158		// parents, otherwise we set the Seen flag.
159	0	let (pass, insert) = if state.contains(WalkFlags::Uninteresting) {
160	0	let flags = WalkFlags::Uninteresting;
161	0	for (id, _) in parents {
162	0	let grand_parents = self.collect_all_parents(id)?;
163
164	0	for (id, _) in &grand_parents {
165	0	self.states
166	0	.entry(*id)
167	0	.and_modify(\|s\| *s \|= WalkFlags::Uninteresting)
168	0	.or_insert(WalkFlags::Uninteresting \| WalkFlags::Seen);
169		}
170		}
171	0	(flags, flags)
172		} else {
173		// NOTE: git sets SEEN like we do but keeps the SYMMETRIC_LEFT and
174		// ANCENSTRY_PATH if they are set, but they have no purpose here.
175	0	let flags = WalkFlags::empty();
176	0	(flags, WalkFlags::Seen)
177		};
178
179	0	for (id, _) in parents {
180	0	self.states.entry(id).and_modify(\|s\| s \|= pass).or_insert(insert);
181		}
182	0	Ok(())
183	0	}
184
185	0	fn collect_parents(&mut self, id: &oid) -> Result<SmallVec<[(ObjectId, GenAndCommitTime); 1]>, Error> {
186	0	collect_parents(
187	0	&mut self.commit_graph,
188	0	&self.find,
189	0	id,
190	0	matches!(self.parents, Parents::First),
191	0	&mut self.buf,
192		)
193	0	}
194
195		// Same as collect_parents but disregards the first_parent flag
196	0	pub(super) fn collect_all_parents(
197	0	&mut self,
198	0	id: &oid,
199	0	) -> Result<SmallVec<[(ObjectId, GenAndCommitTime); 1]>, Error> {
200	0	collect_parents(&mut self.commit_graph, &self.find, id, false, &mut self.buf)
201	0	}
202
203	0	fn pop_commit(&mut self) -> Option<Result<Info, Error>> {
204	0	let commit = self.topo_queue.pop()?;
205	0	let i = match self.indegrees.get_mut(&commit.id) {
206	0	Some(i) => i,
207		None => {
208	0	return Some(Err(Error::MissingIndegreeUnexpected));
209		}
210		};
211
212	0	*i = 0;
213	0	if let Err(e) = self.expand_topo_walk(&commit.id) {
214	0	return Some(Err(e));
215	0	}
216
217	0	Some(Ok(commit))
218	0	}
219		}
220
221		impl<Find, Predicate> Iterator for Topo<Find, Predicate>
222		where
223		Find: gix_object::Find,
224		Predicate: FnMut(&oid) -> bool,
225		{
226		type Item = Result<Info, Error>;
227
228	0	fn next(&mut self) -> Option<Self::Item> {
229		loop {
230	0	match self.pop_commit()? {
231	0	Ok(id) => {
232	0	if (self.predicate)(&id.id) {
233	0	return Some(Ok(id));
234	0	}
235		}
236	0	Err(e) => return Some(Err(e)),
237		}
238		}
239	0	}
240		}
241
242	0	fn collect_parents<Find>(
243	0	cache: &mut Option<gix_commitgraph::Graph>,
244	0	f: Find,
245	0	id: &oid,
246	0	first_only: bool,
247	0	buf: &mut Vec<u8>,
248	0	) -> Result<SmallVec<[(ObjectId, GenAndCommitTime); 1]>, Error>
249	0	where
250	0	Find: gix_object::Find,
251		{
252	0	let mut parents = SmallVec::<[(ObjectId, GenAndCommitTime); 1]>::new();
253	0	match find(cache.as_ref(), &f, id, buf)? {
254	0	Either::CommitRefIter(c) => {
255	0	for token in c {
256		use gix_object::commit::ref_iter::Token as T;
257	0	match token {
258	0	Ok(T::Tree { .. }) => continue,
259	0	Ok(T::Parent { id }) => {
260	0	parents.push((id, (0, 0))); // Dummy numbers to be filled in
261	0	if first_only {
262	0	break;
263	0	}
264		}
265	0	Ok(_past_parents) => break,
266	0	Err(err) => return Err(err.into()),
267		}
268		}
269		// Need to check the cache again. That a commit is not in the cache
270		// doesn't mean a parent is not.
271	0	for (id, gen_time) in parents.iter_mut() {
272	0	let commit = find(cache.as_ref(), &f, id, buf)?;
273	0	*gen_time = gen_and_commit_time(commit)?;
274		}
275		}
276	0	Either::CachedCommit(c) => {
277	0	for pos in c.iter_parents() {
278	0	let Ok(pos) = pos else {
279		// drop corrupt cache and use ODB from now on.
280	0	*cache = None;
281	0	return collect_parents(cache, f, id, first_only, buf);
282		};
283	0	let parent_commit = cache
284	0	.as_ref()
285	0	.expect("cache exists if CachedCommit was returned")
286	0	.commit_at(pos);
287	0	parents.push((
288	0	parent_commit.id().into(),
289	0	(parent_commit.generation(), parent_commit.committer_timestamp() as i64),
290	0	));
291	0	if first_only {
292	0	break;
293	0	}
294		}
295		}
296		}
297	0	Ok(parents)
298	0	}
299
300	0	pub(super) fn gen_and_commit_time(c: Either<'_, '_>) -> Result<GenAndCommitTime, Error> {
301	0	match c {
302	0	Either::CommitRefIter(c) => {
303	0	let mut commit_time = 0;
304	0	for token in c {
305		use gix_object::commit::ref_iter::Token as T;
306	0	match token {
307	0	Ok(T::Tree { .. }) => continue,
308	0	Ok(T::Parent { .. }) => continue,
309	0	Ok(T::Author { .. }) => continue,
310	0	Ok(T::Committer { signature }) => {
311	0	commit_time = signature.seconds();
312	0	break;
313		}
314	0	Ok(_unused_token) => break,
315	0	Err(err) => return Err(err.into()),
316		}
317		}
318	0	Ok((gix_commitgraph::GENERATION_NUMBER_INFINITY, commit_time))
319		}
320	0	Either::CachedCommit(c) => Ok((c.generation(), c.committer_timestamp() as i64)),
321		}
322	0	}