| 1 | //! Commit history: newest-first walks, paged with a cursor, optionally |
| 2 | //! filtered by path and message. |
| 3 | //! |
| 4 | //! Path filters follow git's default history simplification: at a merge |
| 5 | //! that kept one parent's version of the path, only that parent is |
| 6 | //! followed, so side branches whose changes didn't survive are left out |
| 7 | //! (`git log -- path`, not `--full-history`). |
| 8 | |
| 9 | use std::collections::{BinaryHeap, HashMap, HashSet, VecDeque}; |
| 10 | |
| 11 | use anyhow::Context; |
| 12 | use gix::bstr::ByteSlice; |
| 13 | use gix::revision::walk::Sorting; |
| 14 | use gix::traverse::commit::simple::CommitTimeOrder; |
| 15 | |
| 16 | use super::tree::{self, EntryKind}; |
| 17 | use super::{CommitInfo, ObjectId, commit_info}; |
| 18 | |
| 19 | #[derive(Debug, Clone, Default, PartialEq, Eq, Hash)] |
| 20 | pub struct LogQuery { |
| 21 | /// Only commits that change this path (empty: all commits). |
| 22 | pub path: Vec<u8>, |
| 23 | /// Case-insensitive match on the message, author name and email. |
| 24 | pub grep: Option<String>, |
| 25 | /// Start after this commit (the last one on the previous page). |
| 26 | pub after: Option<ObjectId>, |
| 27 | pub page: usize, |
| 28 | /// Commits a filtered walk may examine before giving up on this page. |
| 29 | pub scan_limit: usize, |
| 30 | } |
| 31 | |
| 32 | impl LogQuery { |
| 33 | fn filtered(&self) -> bool { |
| 34 | !self.path.is_empty() || self.grep.is_some() |
| 35 | } |
| 36 | } |
| 37 | |
| 38 | /// Where the "newer" link of a page goes. |
| 39 | #[derive(Debug, Clone, Copy, PartialEq, Eq)] |
| 40 | pub enum Newer { |
| 41 | /// This is the first page. |
| 42 | None, |
| 43 | /// Back to the first page (filtered logs can't step back exactly). |
| 44 | First, |
| 45 | After(ObjectId), |
| 46 | } |
| 47 | |
| 48 | #[derive(Debug, Clone)] |
| 49 | pub struct LogPage { |
| 50 | pub commits: Vec<CommitInfo>, |
| 51 | /// Cursor for the next (older) page. |
| 52 | pub older: Option<ObjectId>, |
| 53 | pub newer: Newer, |
| 54 | /// The filter gave up after `scan_limit` commits; `older` continues. |
| 55 | pub limit_reached: bool, |
| 56 | } |
| 57 | |
| 58 | impl LogPage { |
| 59 | pub fn weight(&self) -> usize { |
| 60 | 64 + self.commits.iter().map(CommitInfo::weight).sum::<usize>() |
| 61 | } |
| 62 | } |
| 63 | |
| 64 | #[derive(Debug, thiserror::Error)] |
| 65 | pub enum LogError { |
| 66 | #[error("the cursor commit is not in this history")] |
| 67 | UnknownCursor, |
| 68 | #[error(transparent)] |
| 69 | Git(#[from] anyhow::Error), |
| 70 | } |
| 71 | |
| 72 | /// One page of the history of `tip`, newest commit first. |
| 73 | pub fn page(repo: &gix::Repository, tip: ObjectId, query: &LogQuery) -> Result<LogPage, LogError> { |
| 74 | let filtered = query.filtered(); |
| 75 | let grep = query.grep.as_ref().map(|q| q.to_lowercase()); |
| 76 | let mut walk = if query.path.is_empty() { |
| 77 | Walk::All( |
| 78 | repo.rev_walk([tip]) |
| 79 | .sorting(Sorting::ByCommitTime(CommitTimeOrder::NewestFirst)) |
| 80 | .all() |
| 81 | .context("cannot walk history")?, |
| 82 | ) |
| 83 | } else { |
| 84 | Walk::Path(PathWalk::new(repo, tip, &query.path)?) |
| 85 | }; |
| 86 | |
| 87 | // Unfiltered: the commits up to and including the cursor, enough to |
| 88 | // find where the previous page started. |
| 89 | let mut recent: VecDeque<ObjectId> = VecDeque::new(); |
| 90 | let mut seeking = query.after; |
| 91 | let mut out = LogPage { |
| 92 | commits: Vec::new(), |
| 93 | older: None, |
| 94 | newer: Newer::None, |
| 95 | limit_reached: false, |
| 96 | }; |
| 97 | let mut scanned = 0; |
| 98 | let mut last_examined = None; |
| 99 | while let Some(step) = walk.next() { |
| 100 | let (id, touches) = step?; |
| 101 | if let Some(cursor) = seeking { |
| 102 | if !filtered { |
| 103 | recent.push_back(id); |
| 104 | if recent.len() > query.page + 1 { |
| 105 | recent.pop_front(); |
| 106 | } |
| 107 | } |
| 108 | if id == cursor { |
| 109 | seeking = None; |
| 110 | } |
| 111 | continue; |
| 112 | } |
| 113 | if filtered { |
| 114 | if scanned == query.scan_limit { |
| 115 | out.limit_reached = true; |
| 116 | out.older = last_examined; |
| 117 | break; |
| 118 | } |
| 119 | scanned += 1; |
| 120 | last_examined = Some(id); |
| 121 | } |
| 122 | if !touches { |
| 123 | continue; |
| 124 | } |
| 125 | let commit = commit_info(repo, id)?; |
| 126 | if let Some(grep) = &grep |
| 127 | && !message_matches(repo, &commit, grep)? |
| 128 | { |
| 129 | continue; |
| 130 | } |
| 131 | if out.commits.len() == query.page { |
| 132 | out.older = out.commits.last().map(|c| c.id); |
| 133 | break; |
| 134 | } |
| 135 | out.commits.push(commit); |
| 136 | } |
| 137 | if seeking.is_some() { |
| 138 | return Err(LogError::UnknownCursor); |
| 139 | } |
| 140 | if query.after.is_some() { |
| 141 | out.newer = if filtered || recent.len() <= query.page { |
| 142 | Newer::First |
| 143 | } else { |
| 144 | Newer::After(recent[0]) |
| 145 | }; |
| 146 | } |
| 147 | Ok(out) |
| 148 | } |
| 149 | |
| 150 | fn message_matches(repo: &gix::Repository, info: &CommitInfo, grep: &str) -> anyhow::Result<bool> { |
| 151 | if info.author_name.to_lowercase().contains(grep) |
| 152 | || info.author_email.to_lowercase().contains(grep) |
| 153 | { |
| 154 | return Ok(true); |
| 155 | } |
| 156 | let commit = repo.find_commit(info.id).context("commit not found")?; |
| 157 | let message = commit.message_raw_sloppy().to_str_lossy().to_lowercase(); |
| 158 | Ok(message.contains(grep)) |
| 159 | } |
| 160 | |
| 161 | enum Walk<'repo> { |
| 162 | All(gix::revision::Walk<'repo>), |
| 163 | Path(PathWalk<'repo>), |
| 164 | } |
| 165 | |
| 166 | impl Walk<'_> { |
| 167 | /// The next commit, and whether it passes the path filter. |
| 168 | fn next(&mut self) -> Option<anyhow::Result<(ObjectId, bool)>> { |
| 169 | match self { |
| 170 | Walk::All(walk) => Some( |
| 171 | walk.next()? |
| 172 | .map(|info| (info.id, true)) |
| 173 | .context("cannot walk history"), |
| 174 | ), |
| 175 | Walk::Path(walk) => walk.next().transpose(), |
| 176 | } |
| 177 | } |
| 178 | } |
| 179 | |
| 180 | /// Newest-first walk that simplifies history for `path`. |
| 181 | struct PathWalk<'repo> { |
| 182 | repo: &'repo gix::Repository, |
| 183 | path: Vec<u8>, |
| 184 | queue: BinaryHeap<(i64, ObjectId)>, |
| 185 | seen: HashSet<ObjectId>, |
| 186 | oids: PathOids, |
| 187 | } |
| 188 | |
| 189 | impl<'repo> PathWalk<'repo> { |
| 190 | fn new(repo: &'repo gix::Repository, tip: ObjectId, path: &[u8]) -> anyhow::Result<Self> { |
| 191 | let mut walk = PathWalk { |
| 192 | repo, |
| 193 | path: path.to_vec(), |
| 194 | queue: BinaryHeap::new(), |
| 195 | seen: HashSet::new(), |
| 196 | oids: PathOids::default(), |
| 197 | }; |
| 198 | walk.push(tip)?; |
| 199 | Ok(walk) |
| 200 | } |
| 201 | |
| 202 | fn push(&mut self, id: ObjectId) -> anyhow::Result<()> { |
| 203 | if !self.seen.insert(id) { |
| 204 | return Ok(()); |
| 205 | } |
| 206 | // Missing parents (shallow clones) end the walk there. |
| 207 | let Ok(commit) = self.repo.find_commit(id) else { |
| 208 | return Ok(()); |
| 209 | }; |
| 210 | let time = commit.time().context("malformed commit")?.seconds; |
| 211 | self.queue.push((time, id)); |
| 212 | Ok(()) |
| 213 | } |
| 214 | |
| 215 | fn next(&mut self) -> anyhow::Result<Option<(ObjectId, bool)>> { |
| 216 | let Some((_, id)) = self.queue.pop() else { |
| 217 | return Ok(None); |
| 218 | }; |
| 219 | let commit = self.repo.find_commit(id).context("commit not found")?; |
| 220 | let parents: Vec<ObjectId> = commit.parent_ids().map(|p| p.detach()).collect(); |
| 221 | let here = self.oids.get(self.repo, id, &self.path)?; |
| 222 | let mut same = None; |
| 223 | for parent in &parents { |
| 224 | if self.oids.get(self.repo, *parent, &self.path)? == here { |
| 225 | same = Some(*parent); |
| 226 | break; |
| 227 | } |
| 228 | } |
| 229 | let (touches, follow) = match same { |
| 230 | // Identical to a parent: not interesting, and only that |
| 231 | // parent's history explains the path's state. |
| 232 | Some(parent) => (false, vec![parent]), |
| 233 | None if parents.is_empty() => (here.is_some(), Vec::new()), |
| 234 | None => (true, parents), |
| 235 | }; |
| 236 | for parent in follow { |
| 237 | self.push(parent)?; |
| 238 | } |
| 239 | Ok(Some((id, touches))) |
| 240 | } |
| 241 | } |
| 242 | |
| 243 | /// What one path holds (id and mode), memoized per commit: each commit is |
| 244 | /// usually asked about again as the parent of the next one. |
| 245 | #[derive(Default)] |
| 246 | struct PathOids { |
| 247 | by_commit: HashMap<ObjectId, Option<(ObjectId, EntryKind)>>, |
| 248 | } |
| 249 | |
| 250 | impl PathOids { |
| 251 | fn get( |
| 252 | &mut self, |
| 253 | repo: &gix::Repository, |
| 254 | commit: ObjectId, |
| 255 | path: &[u8], |
| 256 | ) -> anyhow::Result<Option<(ObjectId, EntryKind)>> { |
| 257 | if let Some(found) = self.by_commit.get(&commit) { |
| 258 | return Ok(*found); |
| 259 | } |
| 260 | let found = tree::entry_at(repo, commit, path)?; |
| 261 | if self.by_commit.len() > 4096 { |
| 262 | self.by_commit.clear(); |
| 263 | } |
| 264 | self.by_commit.insert(commit, found); |
| 265 | Ok(found) |
| 266 | } |
| 267 | } |