1//! Provide multiple traversal implementations with different performance envelopes.
2//!
3//! Use [`Simple`] for fast walks that maintain minimal state, or [`Topo`] for a more elaborate traversal.
4use gix_hash::ObjectId;
5use gix_object::FindExt;
6use gix_revwalk::{graph::IdMap, PriorityQueue};
7use smallvec::SmallVec;
89/// A fast iterator over the ancestors of one or more starting commits.
10pub struct Simple<Find, Predicate> {
11 objects: Find,
12 cache: Option<gix_commitgraph::Graph>,
13 predicate: Predicate,
14 state: simple::State,
15 parents: Parents,
16 sorting: simple::Sorting,
17}
1819/// Simple ancestors traversal, without the need to keep track of graph-state.
20pub mod simple;
2122/// A commit walker that walks in topographical order, like `git rev-list
23/// --topo-order` or `--date-order` depending on the chosen [`topo::Sorting`].
24///
25/// Instantiate with [`topo::Builder`].
26pub struct Topo<Find, Predicate> {
27 commit_graph: Option<gix_commitgraph::Graph>,
28 find: Find,
29 predicate: Predicate,
30 indegrees: IdMap<i32>,
31 states: IdMap<topo::WalkFlags>,
32 explore_queue: PriorityQueue<topo::iter::GenAndCommitTime, ObjectId>,
33 indegree_queue: PriorityQueue<topo::iter::GenAndCommitTime, ObjectId>,
34 topo_queue: topo::iter::Queue,
35 parents: Parents,
36 min_gen: u32,
37 buf: Vec<u8>,
38}
3940pub mod topo;
4142/// Specify how to handle commit parents during traversal.
43#[derive(Default, Copy, Clone)]
44pub enum Parents {
45/// Traverse all parents, useful for traversing the entire ancestry.
46#[default]
47All,
48/// Only traverse along the first parent, which commonly ignores all branches.
49First,
50}
5152/// The collection of parent ids we saw as part of the iteration.
53///
54/// Note that this list is truncated if [`Parents::First`] was used.
55pub type ParentIds = SmallVec<[gix_hash::ObjectId; 1]>;
5657/// Information about a commit that we obtained naturally as part of the iteration.
58#[derive(Debug, Clone, PartialEq, Eq, Ord, PartialOrd, Hash)]
59pub struct Info {
60/// The id of the commit.
61pub id: gix_hash::ObjectId,
62/// All parent ids we have encountered. Note that these will be at most one if [`Parents::First`] is enabled.
63pub parent_ids: ParentIds,
64/// The time at which the commit was created. It will only be `Some(_)` if the chosen traversal was
65 /// taking dates into consideration.
66pub commit_time: Option<gix_date::SecondsSinceUnixEpoch>,
67}
6869/// Information about a commit that can be obtained either from a [`gix_object::CommitRefIter`] or
70/// a [`gix_commitgraph::file::Commit`].
71#[derive(Clone, Copy)]
72pub enum Either<'buf, 'cache> {
73/// See [`gix_object::CommitRefIter`].
74CommitRefIter(gix_object::CommitRefIter<'buf>),
75/// See [`gix_commitgraph::file::Commit`].
76CachedCommit(gix_commitgraph::file::Commit<'cache>),
77}
7879impl Either<'_, '_> {
80/// Get a commit’s `tree_id` by either getting it from a [`gix_commitgraph::Graph`], if
81 /// present, or a [`gix_object::CommitRefIter`] otherwise.
82pub fn tree_id(self) -> Result<ObjectId, gix_object::decode::Error> {
83match self {
84Self::CommitRefIter(mut commit_ref_iter) => commit_ref_iter.tree_id(),
85Self::CachedCommit(commit) => Ok(commit.root_tree_id().into()),
86 }
87 }
8889/// Get a committer timestamp by either getting it from a [`gix_commitgraph::Graph`], if
90 /// present, or a [`gix_object::CommitRefIter`] otherwise.
91pub fn commit_time(self) -> Result<gix_date::SecondsSinceUnixEpoch, gix_object::decode::Error> {
92match self {
93Self::CommitRefIter(commit_ref_iter) => commit_ref_iter.committer().map(|c| c.seconds()),
94Self::CachedCommit(commit) => Ok(commit.committer_timestamp() as gix_date::SecondsSinceUnixEpoch),
95 }
96 }
97}
9899/// Find information about a commit by either getting it from a [`gix_commitgraph::Graph`], if
100/// present, or a [`gix_object::CommitRefIter`] otherwise.
101pub fn find<'cache, 'buf, Find>(
102 cache: Option<&'cache gix_commitgraph::Graph>,
103 objects: Find,
104 id: &gix_hash::oid,
105 buf: &'buf mut Vec<u8>,
106) -> Result<Either<'buf, 'cache>, gix_object::find::existing_iter::Error>
107where
108Find: gix_object::Find,
109{
110match cache.and_then(|cache| cache.commit_by_id(id).map(Either::CachedCommit)) {
111Some(c) => Ok(c),
112None => objects.find_commit_iter(id, buf).map(Either::CommitRefIter),
113 }
114}