use gix_hash::{ObjectId, oid};use gix_revwalk::PriorityQueue;use smallvec::SmallVec; use crate::commit::{ Either, Info, Parents, Topo, find, topo::{Error, Sorting, WalkFlags},}; 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(inner_vec) = self { inner_vec.sort_by_key(|a| a.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(((generation, _), _)) = self.indegree_queue.peek() { if *generation >= gen_cutoff { self.indegree_walk_step()?; } else { break; } } Ok(()) } fn indegree_walk_step(&mut self) -> Result<(), Error> { if let Some(((generation, _), id)) = self.indegree_queue.pop() { self.explore_to_depth(generation)?; 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(((generation, _), _)) = self.explore_queue.peek() { if *generation >= 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)), }}
use gix_hash::{ObjectId, oid};
use gix_revwalk::PriorityQueue;
use smallvec::SmallVec;
use crate::commit::{
Either, Info, Parents, Topo, find,
topo::{Error, Sorting, WalkFlags},
};
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(inner_vec) = self {
inner_vec.sort_by_key(|a| a.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(((generation, _), _)) = self.indegree_queue.peek() {
if *generation >= gen_cutoff {
self.indegree_walk_step()?;
} else {
break;
}
}
Ok(())
}
fn indegree_walk_step(&mut self) -> Result<(), Error> {
if let Some(((generation, _), id)) = self.indegree_queue.pop() {
self.explore_to_depth(generation)?;
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(((generation, _), _)) = self.explore_queue.peek() {
if *generation >= 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)),
}
}