1use std::{
2 cmp::Ordering,
3 collections::{BinaryHeap, HashSet},
4};
5
6use crate::{Commit, GitError, ObjectId, Repository, Result};
7
8#[derive(Clone, Copy, Debug)]
9pub struct HistoryOptions {
10 pub max_commits: usize,
11 pub first_parent: bool,
12 pub since: Option<i64>,
13 pub until: Option<i64>,
14}
15
16impl Default for HistoryOptions {
17 fn default() -> Self {
18 Self {
19 max_commits: 10_000,
20 first_parent: false,
21 since: None,
22 until: None,
23 }
24 }
25}
26
27#[derive(Clone, Debug)]
28pub struct HistoryRecord {
29 pub id: ObjectId,
30 pub commit: Commit,
31}
32
33#[derive(Clone, Debug, Eq, PartialEq)]
34struct Pending {
35 time: i64,
36 sequence: u64,
37 commit: Commit,
38}
39
40#[derive(Clone, Debug, Eq, PartialEq)]
41struct PendingId {
42 time: i64,
43 sequence: u64,
44 id: ObjectId,
45 parents: Vec<ObjectId>,
46}
47
48impl Ord for Pending {
49 fn cmp(&self, other: &Self) -> Ordering {
50 (self.time, self.sequence).cmp(&(other.time, other.sequence))
51 }
52}
53
54impl PartialOrd for Pending {
55 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
56 Some(self.cmp(other))
57 }
58}
59
60impl Ord for PendingId {
61 fn cmp(&self, other: &Self) -> Ordering {
62 (self.time, self.sequence).cmp(&(other.time, other.sequence))
63 }
64}
65
66impl PartialOrd for PendingId {
67 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
68 Some(self.cmp(other))
69 }
70}
71
72pub(crate) fn walk(
73 repository: &Repository,
74 start: ObjectId,
75 options: HistoryOptions,
76) -> Result<Vec<HistoryRecord>> {
77 let cap = options
78 .max_commits
79 .min(repository.limits().max_history_commits);
80 if options.max_commits > repository.limits().max_history_commits {
81 return Err(GitError::LimitExceeded {
82 resource: "history commits",
83 limit: repository.limits().max_history_commits,
84 });
85 }
86 let first = repository.commit(start)?;
87 let mut pending = BinaryHeap::from([Pending {
88 time: commit_time(&first),
89 sequence: 0,
90 commit: first,
91 }]);
92 let mut scheduled = HashSet::from([start]);
93 let mut result = Vec::with_capacity(cap.min(1024));
94 let mut sequence = 1;
95 while let Some(item) = pending.pop() {
96 if result.len() == cap {
97 break;
98 }
99 let commit = item.commit;
100 let parents = if options.first_parent {
101 commit.parents.get(..1).unwrap_or(&[])
102 } else {
103 &commit.parents
104 };
105 for parent in parents {
106 if scheduled.insert(*parent) {
107 let parent_commit = repository.commit(*parent)?;
108 pending.push(Pending {
109 time: commit_time(&parent_commit),
110 sequence,
111 commit: parent_commit,
112 });
113 sequence += 1;
114 }
115 }
116 let in_range = options.since.is_none_or(|time| item.time >= time)
117 && options.until.is_none_or(|time| item.time <= time);
118 if in_range {
119 result.push(HistoryRecord {
120 id: commit.id,
121 commit,
122 });
123 }
124 }
125 Ok(result)
126}
127
128pub(crate) fn walk_ids(
129 repository: &Repository,
130 start: ObjectId,
131 options: HistoryOptions,
132) -> Result<Vec<ObjectId>> {
133 validate_limit(repository, options)?;
134 if options.first_parent {
135 return walk_first_parent_ids(repository, start, options);
136 }
137 let first = load_id(repository, start, 0)?;
138 let mut pending = BinaryHeap::from([first]);
139 let mut scheduled = HashSet::from([start]);
140 let mut result = Vec::with_capacity(options.max_commits.min(1024));
141 let mut sequence = 1;
142 while let Some(item) = pending.pop() {
143 if result.len() == options.max_commits {
144 break;
145 }
146 let parents = if options.first_parent {
147 item.parents.get(..1).unwrap_or(&[])
148 } else {
149 &item.parents
150 };
151 for parent in parents {
152 if scheduled.insert(*parent) {
153 pending.push(load_id(repository, *parent, sequence)?);
154 sequence += 1;
155 }
156 }
157 if options.since.is_none_or(|time| item.time >= time)
158 && options.until.is_none_or(|time| item.time <= time)
159 {
160 result.push(item.id);
161 }
162 }
163 Ok(result)
164}
165
166fn walk_first_parent_ids(
167 repository: &Repository,
168 start: ObjectId,
169 options: HistoryOptions,
170) -> Result<Vec<ObjectId>> {
171 if let Some(ids) = repository.graph_first_parent_ids(start, options)? {
172 return Ok(ids);
173 }
174 let mut current = Some(start);
175 let mut result = Vec::with_capacity(options.max_commits.min(1024));
176 let mut traversed = 0;
177 while let Some(id) = current {
178 if result.len() == options.max_commits {
179 break;
180 }
181 if traversed == repository.limits().max_history_commits {
182 return Err(GitError::LimitExceeded {
183 resource: "history traversal",
184 limit: repository.limits().max_history_commits,
185 });
186 }
187 traversed += 1;
188 let commit = repository.commit_metadata(id)?;
189 current = commit.parents.first().copied();
190 if options
191 .since
192 .is_none_or(|time| commit.committer_time >= time)
193 && options
194 .until
195 .is_none_or(|time| commit.committer_time <= time)
196 {
197 result.push(commit.id);
198 }
199 }
200 Ok(result)
201}
202
203fn load_id(repository: &Repository, id: ObjectId, sequence: u64) -> Result<PendingId> {
204 let commit = repository.commit_metadata(id)?;
205 Ok(PendingId {
206 time: commit.committer_time,
207 sequence,
208 id: commit.id,
209 parents: commit.parents,
210 })
211}
212
213fn validate_limit(repository: &Repository, options: HistoryOptions) -> Result<()> {
214 if options.max_commits > repository.limits().max_history_commits {
215 return Err(GitError::LimitExceeded {
216 resource: "history commits",
217 limit: repository.limits().max_history_commits,
218 });
219 }
220 Ok(())
221}
222
223fn commit_time(commit: &Commit) -> i64 {
224 commit
225 .committer
226 .as_ref()
227 .or(commit.author.as_ref())
228 .map_or(0, |signature| signature.timestamp)
229}