gix_traverse/commit/
mod.rs

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

gix_traverse/commit/
mod.rs
