weavatrix_git/
revwalk.rs

1use std::{
2    cmp::Ordering,
3    collections::{BinaryHeap, HashSet},
4};
5
6use crate::{GitError, ObjectId, Repository, Result};
7
8#[derive(Clone, Debug, Eq, PartialEq)]
9struct Pending {
10    time: i64,
11    sequence: u64,
12    id: ObjectId,
13    parents: Vec<ObjectId>,
14}
15
16impl Ord for Pending {
17    fn cmp(&self, other: &Self) -> Ordering {
18        (self.time, self.sequence, self.id).cmp(&(other.time, other.sequence, other.id))
19    }
20}
21
22impl PartialOrd for Pending {
23    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
24        Some(self.cmp(other))
25    }
26}
27
28pub struct RevWalk<'repo> {
29    repository: &'repo Repository,
30    pending: BinaryHeap<Pending>,
31    scheduled: HashSet<ObjectId>,
32    hidden: HashSet<ObjectId>,
33    first_parent: bool,
34    sequence: u64,
35    emitted: usize,
36    failed: bool,
37}
38
39impl<'repo> RevWalk<'repo> {
40    pub(crate) fn new(repository: &'repo Repository) -> Self {
41        Self {
42            repository,
43            pending: BinaryHeap::new(),
44            scheduled: HashSet::new(),
45            hidden: HashSet::new(),
46            first_parent: false,
47            sequence: 0,
48            emitted: 0,
49            failed: false,
50        }
51    }
52
53    pub fn push(&mut self, id: ObjectId) -> Result<&mut Self> {
54        self.schedule(id)?;
55        Ok(self)
56    }
57
58    pub fn push_head(&mut self) -> Result<&mut Self> {
59        let id = self
60            .repository
61            .head()?
62            .target
63            .ok_or_else(|| crate::GitError::NotFound("unborn HEAD".to_owned()))?;
64        self.push(id)
65    }
66
67    pub fn push_ref(&mut self, name: &str) -> Result<&mut Self> {
68        self.push(self.repository.resolve(name)?)
69    }
70
71    pub fn hide(&mut self, id: ObjectId) -> Result<&mut Self> {
72        let mut stack = vec![id];
73        while let Some(id) = stack.pop() {
74            if !self.hidden.insert(id) {
75                continue;
76            }
77            if self.hidden.len() > self.repository.limits().max_history_commits {
78                return Err(GitError::LimitExceeded {
79                    resource: "revwalk hidden commits",
80                    limit: self.repository.limits().max_history_commits,
81                });
82            }
83            stack.extend(self.repository.commit_metadata(id)?.parents);
84        }
85        Ok(self)
86    }
87
88    pub fn hide_ref(&mut self, name: &str) -> Result<&mut Self> {
89        self.hide(self.repository.resolve(name)?)
90    }
91
92    pub const fn first_parent(&mut self, enabled: bool) -> &mut Self {
93        self.first_parent = enabled;
94        self
95    }
96
97    pub fn reset(&mut self) {
98        self.pending.clear();
99        self.scheduled.clear();
100        self.hidden.clear();
101        self.sequence = 0;
102        self.emitted = 0;
103        self.failed = false;
104    }
105
106    fn schedule(&mut self, id: ObjectId) -> Result<()> {
107        if !self.scheduled.insert(id) {
108            return Ok(());
109        }
110        if self.scheduled.len() > self.repository.limits().max_history_commits {
111            return Err(GitError::LimitExceeded {
112                resource: "revwalk commits",
113                limit: self.repository.limits().max_history_commits,
114            });
115        }
116        let commit = self.repository.commit_metadata(id)?;
117        self.pending.push(Pending {
118            time: commit.committer_time,
119            sequence: self.sequence,
120            id,
121            parents: commit.parents,
122        });
123        self.sequence = self.sequence.wrapping_add(1);
124        Ok(())
125    }
126}
127
128impl Iterator for RevWalk<'_> {
129    type Item = Result<ObjectId>;
130
131    fn next(&mut self) -> Option<Self::Item> {
132        if self.failed || self.emitted >= self.repository.limits().max_history_commits {
133            return None;
134        }
135        while let Some(item) = self.pending.pop() {
136            if self.hidden.contains(&item.id) {
137                continue;
138            }
139            let parents = if self.first_parent {
140                item.parents.get(..1).unwrap_or(&[])
141            } else {
142                &item.parents
143            };
144            for parent in parents {
145                if let Err(error) = self.schedule(*parent) {
146                    self.failed = true;
147                    return Some(Err(error));
148                }
149            }
150            self.emitted += 1;
151            return Some(Ok(item.id));
152        }
153        None
154    }
155}
156
157impl Repository {
158    #[must_use]
159    pub fn revwalk(&self) -> RevWalk<'_> {
160        RevWalk::new(self)
161    }
162}
weavatrix_git/revwalk.rs

weavatrix_git/
revwalk.rs
