weavatrix_git/
history.rs

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    let first = load_id(repository, start, 0)?;
135    let mut pending = BinaryHeap::from([first]);
136    let mut scheduled = HashSet::from([start]);
137    let mut result = Vec::with_capacity(options.max_commits.min(1024));
138    let mut sequence = 1;
139    while let Some(item) = pending.pop() {
140        if result.len() == options.max_commits {
141            break;
142        }
143        let parents = if options.first_parent {
144            item.parents.get(..1).unwrap_or(&[])
145        } else {
146            &item.parents
147        };
148        for parent in parents {
149            if scheduled.insert(*parent) {
150                pending.push(load_id(repository, *parent, sequence)?);
151                sequence += 1;
152            }
153        }
154        if options.since.is_none_or(|time| item.time >= time)
155            && options.until.is_none_or(|time| item.time <= time)
156        {
157            result.push(item.id);
158        }
159    }
160    Ok(result)
161}
162
163fn load_id(repository: &Repository, id: ObjectId, sequence: u64) -> Result<PendingId> {
164    let commit = repository.commit_metadata(id)?;
165    Ok(PendingId {
166        time: commit.committer_time,
167        sequence,
168        id: commit.id,
169        parents: commit.parents,
170    })
171}
172
173fn validate_limit(repository: &Repository, options: HistoryOptions) -> Result<()> {
174    if options.max_commits > repository.limits().max_history_commits {
175        return Err(GitError::LimitExceeded {
176            resource: "history commits",
177            limit: repository.limits().max_history_commits,
178        });
179    }
180    Ok(())
181}
182
183fn commit_time(commit: &Commit) -> i64 {
184    commit
185        .committer
186        .as_ref()
187        .or(commit.author.as_ref())
188        .map_or(0, |signature| signature.timestamp)
189}
weavatrix_git/history.rs

weavatrix_git/
history.rs
