| 1 | //! What rules about commits look at, read from a pack: each commit's |
| 2 | //! message, addresses, parents and signature, and the files it adds, |
| 3 | //! changes or deletes with their sizes. A push's pack is read before it is |
| 4 | //! stored; a pull request's commits are fetched as a pack from its source |
| 5 | //! (`inspect_commits`), so both are read by the same code. |
| 6 | |
| 7 | use std::cell::Cell; |
| 8 | use std::collections::{HashMap, HashSet, VecDeque}; |
| 9 | |
| 10 | use futures_util::future::{join_all, try_join_all}; |
| 11 | use g1t_contracts::rules::{CommitFacts, FileChange, Signature}; |
| 12 | use g1t_scan::pack::{ObjectKind, Pack}; |
| 13 | use worker::Result; |
| 14 | |
| 15 | use crate::secret_scan::Objects; |
| 16 | use crate::store::GitRepo; |
| 17 | |
| 18 | /// Who registered each signing key (fingerprint to user id), and who |
| 19 | /// verified each address (to user id and username). |
| 20 | pub type Owners = (HashMap<String, String>, HashMap<String, (String, String)>); |
| 21 | |
| 22 | /// The most commits read for one ref. |
| 23 | pub const MAX_COMMITS: usize = 300; |
| 24 | /// The most files listed for one commit; more is not complete. |
| 25 | pub const MAX_FILES: usize = 1000; |
| 26 | /// The most of a message kept. |
| 27 | const MAX_MESSAGE: usize = 4096; |
| 28 | |
| 29 | /// A raw commit's headers and message. |
| 30 | #[derive(Debug, Default, PartialEq, Eq)] |
| 31 | pub struct CommitText { |
| 32 | pub tree: String, |
| 33 | pub parents: Vec<String>, |
| 34 | pub author_email: Option<String>, |
| 35 | pub committer_email: Option<String>, |
| 36 | pub message: String, |
| 37 | } |
| 38 | |
| 39 | fn email(value: &str) -> Option<String> { |
| 40 | let start = value.rfind('<')?; |
| 41 | let end = start + value[start..].find('>')?; |
| 42 | Some(value[start + 1..end].trim().to_owned()) |
| 43 | } |
| 44 | |
| 45 | /// Reads a raw commit object. |
| 46 | pub fn read_commit(data: &[u8]) -> CommitText { |
| 47 | let text = String::from_utf8_lossy(data); |
| 48 | let (headers, message) = text.split_once("\n\n").unwrap_or((&text, "")); |
| 49 | let mut commit = CommitText::default(); |
| 50 | for line in headers.split('\n') { |
| 51 | if let Some(tree) = line.strip_prefix("tree ") { |
| 52 | commit.tree = tree.trim().to_owned(); |
| 53 | } else if let Some(parent) = line.strip_prefix("parent ") { |
| 54 | commit.parents.push(parent.trim().to_owned()); |
| 55 | } else if let Some(author) = line.strip_prefix("author ") { |
| 56 | commit.author_email = email(author); |
| 57 | } else if let Some(committer) = line.strip_prefix("committer ") { |
| 58 | commit.committer_email = email(committer); |
| 59 | } |
| 60 | } |
| 61 | let mut end = message.len().min(MAX_MESSAGE); |
| 62 | while !message.is_char_boundary(end) { |
| 63 | end -= 1; |
| 64 | } |
| 65 | commit.message = message[..end].to_owned(); |
| 66 | commit |
| 67 | } |
| 68 | |
| 69 | /// The commits of the pack reachable from `tip` without leaving it, |
| 70 | /// newest first: what a push adds to a ref. `None` past `limit`. |
| 71 | pub fn added(pack: &Pack, tip: &str, limit: usize) -> Option<Vec<String>> { |
| 72 | let mut seen = HashSet::new(); |
| 73 | let mut queue = VecDeque::from([tip.to_owned()]); |
| 74 | let mut out = Vec::new(); |
| 75 | while let Some(id) = queue.pop_front() { |
| 76 | if !seen.insert(id.clone()) { |
| 77 | continue; |
| 78 | } |
| 79 | let Some((ObjectKind::Commit, data)) = pack.get(&id) else { |
| 80 | continue; |
| 81 | }; |
| 82 | out.push(id); |
| 83 | if out.len() > limit { |
| 84 | return None; |
| 85 | } |
| 86 | queue.extend(read_commit(data).parents); |
| 87 | } |
| 88 | Some(out) |
| 89 | } |
| 90 | |
| 91 | /// The files that differ between two trees, deletions included, with the |
| 92 | /// size of each new blob the pack holds. Whether the list is complete. |
| 93 | /// Each level of the trees is read at once. |
| 94 | async fn changed<R: GitRepo>(objects: &Objects<'_, R>, old_root: Option<String>, new_root: Option<String>) -> Result<(Vec<FileChange>, bool)> { |
| 95 | let mut files = Vec::new(); |
| 96 | let mut level: Vec<(String, Option<String>, Option<String>)> = vec![(String::new(), old_root, new_root)]; |
| 97 | while !level.is_empty() { |
| 98 | let read = try_join_all(level.iter().map(|(_, old, new)| async move { |
| 99 | let tree = async |id: &Option<String>| match id { |
| 100 | Some(id) => objects.tree(id).await, |
| 101 | None => Ok(Vec::new()), |
| 102 | }; |
| 103 | futures_util::future::try_join(tree(old), tree(new)).await |
| 104 | })) |
| 105 | .await?; |
| 106 | let mut next = Vec::new(); |
| 107 | for ((prefix, _, _), (old_items, new_items)) in level.into_iter().zip(read) { |
| 108 | for item in &new_items { |
| 109 | let before = old_items.iter().find(|entry| entry.name == item.name); |
| 110 | if before.is_some_and(|before| before.id == item.id && before.mode == item.mode) { |
| 111 | continue; |
| 112 | } |
| 113 | let path = format!("{prefix}{}", item.name); |
| 114 | if item.is_tree() { |
| 115 | next.push((format!("{path}/"), before.filter(|b| b.is_tree()).map(|b| b.id.clone()), Some(item.id.clone()))); |
| 116 | // A file replaced by a directory is deleted. |
| 117 | if before.is_some_and(|b| !b.is_tree()) { |
| 118 | files.push(FileChange { path: path.clone(), size: None, deleted: true }); |
| 119 | } |
| 120 | } else { |
| 121 | let size = match objects.pack.get(&item.id) { |
| 122 | Some((ObjectKind::Blob, data)) => Some(data.len() as u64), |
| 123 | _ => None, |
| 124 | }; |
| 125 | files.push(FileChange { path, size, deleted: false }); |
| 126 | if let Some(before) = before.filter(|b| b.is_tree()) { |
| 127 | next.push((format!("{prefix}{}/", item.name), Some(before.id.clone()), None)); |
| 128 | } |
| 129 | } |
| 130 | } |
| 131 | for item in &old_items { |
| 132 | if new_items.iter().any(|entry| entry.name == item.name) { |
| 133 | continue; |
| 134 | } |
| 135 | let path = format!("{prefix}{}", item.name); |
| 136 | if item.is_tree() { |
| 137 | next.push((format!("{path}/"), Some(item.id.clone()), None)); |
| 138 | } else { |
| 139 | files.push(FileChange { path, size: None, deleted: true }); |
| 140 | } |
| 141 | } |
| 142 | if files.len() > MAX_FILES { |
| 143 | files.truncate(MAX_FILES); |
| 144 | return Ok((files, false)); |
| 145 | } |
| 146 | } |
| 147 | level = next; |
| 148 | } |
| 149 | Ok((files, true)) |
| 150 | } |
| 151 | |
| 152 | /// One commit of the pack, read as rules look at it. `signature` is what |
| 153 | /// was made of its signature, when one was asked for. |
| 154 | pub async fn facts<R: GitRepo>(objects: &Objects<'_, R>, id: &str, signature: Option<Signature>) -> Result<Option<CommitFacts>> { |
| 155 | let Some((ObjectKind::Commit, data)) = objects.pack.get(id) else { |
| 156 | return Ok(None); |
| 157 | }; |
| 158 | let commit = read_commit(data); |
| 159 | let old_tree = match commit.parents.first() { |
| 160 | Some(parent) => objects.commit_tree(parent).await?, |
| 161 | None => None, |
| 162 | }; |
| 163 | let (files, files_complete) = changed(objects, old_tree, Some(commit.tree.clone())).await?; |
| 164 | Ok(Some(CommitFacts { |
| 165 | sha: id.to_owned(), |
| 166 | message: commit.message, |
| 167 | author_email: commit.author_email, |
| 168 | committer_email: commit.committer_email, |
| 169 | parents: commit.parents.len() as u32, |
| 170 | signature: signature.unwrap_or_default(), |
| 171 | files, |
| 172 | files_complete, |
| 173 | })) |
| 174 | } |
| 175 | |
| 176 | /// Whether `old` is in the history of `new`: a fast-forward. Walks the |
| 177 | /// pack's commits, then the repository's history from where it leaves it, |
| 178 | /// reading the histories from each place it leaves at once. |
| 179 | pub async fn contains<R: GitRepo>(pack: &Pack, repo: &R, new: &str, old: &str, depth: u32) -> Result<bool> { |
| 180 | if new == old { |
| 181 | return Ok(true); |
| 182 | } |
| 183 | let mut seen = HashSet::new(); |
| 184 | let mut queue = VecDeque::from([new.to_owned()]); |
| 185 | let mut boundary = Vec::new(); |
| 186 | while let Some(id) = queue.pop_front() { |
| 187 | if id == old { |
| 188 | return Ok(true); |
| 189 | } |
| 190 | if !seen.insert(id.clone()) || seen.len() > 5000 { |
| 191 | continue; |
| 192 | } |
| 193 | match pack.get(&id) { |
| 194 | Some((ObjectKind::Commit, data)) => queue.extend(read_commit(data).parents), |
| 195 | _ => boundary.push(id), |
| 196 | } |
| 197 | } |
| 198 | let histories = join_all(boundary.iter().take(20).map(|start| repo.log(start, depth))).await; |
| 199 | if found_in(&histories, old) { |
| 200 | return Ok(true); |
| 201 | } |
| 202 | // Merges: the history is first-parent only, so look along the second |
| 203 | // parents it names too. |
| 204 | let seconds: Vec<&String> = histories |
| 205 | .iter() |
| 206 | .flatten() |
| 207 | .flat_map(|history| history.iter().filter(|commit| commit.parents.len() > 1).take(10)) |
| 208 | .flat_map(|commit| commit.parents.iter().skip(1)) |
| 209 | .collect(); |
| 210 | if seconds.iter().any(|parent| *parent == old) { |
| 211 | return Ok(true); |
| 212 | } |
| 213 | let further = join_all(seconds.iter().map(|parent| repo.log(parent, depth))).await; |
| 214 | if found_in(&further, old) { |
| 215 | return Ok(true); |
| 216 | } |
| 217 | // Not found: a history that could not be read may have held it. |
| 218 | for history in histories.into_iter().chain(further) { |
| 219 | history?; |
| 220 | } |
| 221 | Ok(false) |
| 222 | } |
| 223 | |
| 224 | /// Whether any history read holds `old`. |
| 225 | fn found_in(histories: &[Result<Vec<g1t_contracts::repos::Commit>>], old: &str) -> bool { |
| 226 | histories.iter().flatten().any(|history| history.iter().any(|commit| commit.hash == old)) |
| 227 | } |
| 228 | |
| 229 | /// The signature fingerprints and committer addresses of commits, for |
| 230 | /// looking up who owns them. |
| 231 | pub fn signing_facts(pack: &Pack, ids: &[String]) -> (Vec<String>, Vec<String>) { |
| 232 | let mut fingerprints = Vec::new(); |
| 233 | let mut emails = Vec::new(); |
| 234 | for id in ids { |
| 235 | let Some((ObjectKind::Commit, data)) = pack.get(id) else { continue }; |
| 236 | if let Some(fingerprint) = crate::signatures::fingerprint(data) |
| 237 | && !fingerprints.contains(&fingerprint) |
| 238 | { |
| 239 | fingerprints.push(fingerprint); |
| 240 | if let Some(email) = read_commit(data).committer_email.map(|email| email.to_lowercase()) |
| 241 | && !emails.contains(&email) |
| 242 | { |
| 243 | emails.push(email); |
| 244 | } |
| 245 | } |
| 246 | } |
| 247 | (fingerprints, emails) |
| 248 | } |
| 249 | |
| 250 | /// Every commit of `ids` read, with its signature decided against who |
| 251 | /// owns the keys and addresses (`owners`, when signatures matter). The |
| 252 | /// commits are read at once. |
| 253 | pub async fn read_all<R: GitRepo>( |
| 254 | pack: &Pack, |
| 255 | repo: &R, |
| 256 | ids: &[String], |
| 257 | owners: Option<&Owners>, |
| 258 | ) -> Result<Vec<CommitFacts>> { |
| 259 | let objects = Objects { pack, repo, reads: Cell::new(0) }; |
| 260 | let objects = &objects; |
| 261 | let read = try_join_all(ids.iter().map(|id| async move { |
| 262 | let signature = owners.and_then(|(keys, emails)| { |
| 263 | let (_, data) = pack.get(id)?; |
| 264 | let committer = read_commit(data).committer_email; |
| 265 | Some(crate::signatures::decide(data, committer.as_deref(), keys, emails)) |
| 266 | }); |
| 267 | facts(objects, id, signature).await |
| 268 | })) |
| 269 | .await?; |
| 270 | Ok(read.into_iter().flatten().collect()) |
| 271 | } |
| 272 | |
| 273 | #[cfg(test)] |
| 274 | mod tests { |
| 275 | use super::*; |
| 276 | |
| 277 | #[test] |
| 278 | fn a_commit_reads_its_parents_addresses_and_message() { |
| 279 | let raw = b"tree aaaa\nparent bbbb\nparent cccc\nauthor Ada Lovelace <ada@acme.com> 1 +0000\ncommitter G <noreply@g1t.sh> 1 +0000\ngpgsig -----BEGIN SSH SIGNATURE-----\n abc\n -----END SSH SIGNATURE-----\n\nfeat: rules\n\nWith a body.\n"; |
| 280 | let commit = read_commit(raw); |
| 281 | assert_eq!(commit.tree, "aaaa"); |
| 282 | assert_eq!(commit.parents, vec!["bbbb", "cccc"]); |
| 283 | assert_eq!(commit.author_email.as_deref(), Some("ada@acme.com")); |
| 284 | assert_eq!(commit.committer_email.as_deref(), Some("noreply@g1t.sh")); |
| 285 | assert_eq!(commit.message, "feat: rules\n\nWith a body.\n"); |
| 286 | } |
| 287 | |
| 288 | #[test] |
| 289 | fn a_long_message_is_cut_on_a_character() { |
| 290 | let message = "é".repeat(5000); |
| 291 | let raw = format!("tree a\n\n{message}"); |
| 292 | assert!(read_commit(raw.as_bytes()).message.len() <= MAX_MESSAGE); |
| 293 | } |
| 294 | |
| 295 | #[test] |
| 296 | fn the_commits_a_push_adds_are_those_its_pack_holds() { |
| 297 | use g1t_scan::pack::write_pack; |
| 298 | let first = b"tree t\nauthor A <a@x> 1 +0000\ncommitter A <a@x> 1 +0000\n\none\n".to_vec(); |
| 299 | let first_id = g1t_scan::pack::object_id(ObjectKind::Commit, &first); |
| 300 | let second = format!("tree t\nparent {first_id}\nparent {}\nauthor A <a@x> 1 +0000\ncommitter A <a@x> 1 +0000\n\ntwo\n", "f".repeat(40)).into_bytes(); |
| 301 | let second_id = g1t_scan::pack::object_id(ObjectKind::Commit, &second); |
| 302 | let pack = Pack::parse(&write_pack(&[(ObjectKind::Commit, first), (ObjectKind::Commit, second)])).unwrap(); |
| 303 | assert_eq!(added(&pack, &second_id, 10), Some(vec![second_id.clone(), first_id.clone()])); |
| 304 | assert_eq!(added(&pack, &second_id, 1), None, "past the limit"); |
| 305 | assert_eq!(added(&pack, &"0".repeat(40), 10), Some(Vec::new()), "a tip the pack does not hold adds nothing"); |
| 306 | } |
| 307 | |
| 308 | /// Histories by where they start; a start missing from it fails. |
| 309 | struct Histories(HashMap<String, Vec<g1t_contracts::repos::Commit>>); |
| 310 | |
| 311 | impl GitRepo for Histories { |
| 312 | async fn access(&self, _scope: crate::store::Scope) -> Result<g1t_contracts::repos::GitAccess> { |
| 313 | unimplemented!() |
| 314 | } |
| 315 | async fn branches(&self) -> Result<Vec<g1t_contracts::repos::Branch>> { |
| 316 | Ok(Vec::new()) |
| 317 | } |
| 318 | async fn log(&self, git_ref: &str, _limit: u32) -> Result<Vec<g1t_contracts::repos::Commit>> { |
| 319 | self.0.get(git_ref).cloned().ok_or_else(|| worker::Error::RustError(format!("no history from {git_ref}"))) |
| 320 | } |
| 321 | async fn parents(&self, _commit_hash: &str) -> Result<Option<Vec<String>>> { |
| 322 | Ok(None) |
| 323 | } |
| 324 | async fn read_tree(&self, _tree_hash: &str) -> Result<Option<Vec<g1t_contracts::repos::TreeEntry>>> { |
| 325 | Ok(None) |
| 326 | } |
| 327 | async fn read_blob(&self, _blob_hash: &str) -> Result<Option<Vec<u8>>> { |
| 328 | Ok(None) |
| 329 | } |
| 330 | async fn read_file(&self, _git_ref: &str, _path: &str) -> Result<Option<Vec<u8>>> { |
| 331 | Ok(None) |
| 332 | } |
| 333 | async fn fork(&self, _target_key: &str) -> Result<()> { |
| 334 | Ok(()) |
| 335 | } |
| 336 | } |
| 337 | |
| 338 | fn run<F: std::future::Future>(future: F) -> F::Output { |
| 339 | let waker = std::task::Waker::noop(); |
| 340 | match std::pin::pin!(future).as_mut().poll(&mut std::task::Context::from_waker(waker)) { |
| 341 | std::task::Poll::Ready(output) => output, |
| 342 | std::task::Poll::Pending => panic!("the fake store never waits"), |
| 343 | } |
| 344 | } |
| 345 | |
| 346 | fn at(hash: &str, parents: &[&str]) -> g1t_contracts::repos::Commit { |
| 347 | g1t_contracts::repos::Commit { |
| 348 | hash: hash.to_owned(), |
| 349 | tree_hash: String::new(), |
| 350 | message: String::new(), |
| 351 | author: g1t_contracts::repos::Signature { name: "A".into(), email: "a@x".into() }, |
| 352 | parents: parents.iter().map(|parent| (*parent).to_owned()).collect(), |
| 353 | authored_at: String::new(), |
| 354 | } |
| 355 | } |
| 356 | |
| 357 | #[test] |
| 358 | fn a_fast_forward_is_found_along_the_history_and_its_merges() { |
| 359 | use g1t_scan::pack::write_pack; |
| 360 | // The push brings one commit on top of `base`; `base` merged `side`, |
| 361 | // whose history holds `old`. |
| 362 | let (base, side, old) = ("b".repeat(40), "5".repeat(40), "0".repeat(40)); |
| 363 | let tip = format!("tree t |
| 364 | parent {base} |
| 365 | author A <a@x> 1 +0000 |
| 366 | committer A <a@x> 1 +0000 |
| 367 | |
| 368 | tip |
| 369 | ").into_bytes(); |
| 370 | let tip_id = g1t_scan::pack::object_id(ObjectKind::Commit, &tip); |
| 371 | let pack = Pack::parse(&write_pack(&[(ObjectKind::Commit, tip)])).unwrap(); |
| 372 | let mut histories = HashMap::new(); |
| 373 | histories.insert(base.clone(), vec![at(&base, &["1".repeat(40).as_str(), side.as_str()])]); |
| 374 | histories.insert(side.clone(), vec![at(&side, &[]), at(&old, &[])]); |
| 375 | let repo = Histories(histories); |
| 376 | assert!(run(contains(&pack, &repo, &tip_id, &old, 100)).unwrap()); |
| 377 | assert!(run(contains(&pack, &repo, &tip_id, &side, 100)).unwrap(), "a second parent itself"); |
| 378 | assert!(!run(contains(&pack, &repo, &tip_id, &"9".repeat(40), 100)).unwrap()); |
| 379 | // A history that cannot be read does not hide one found elsewhere, |
| 380 | // and is an error only when nothing was found. |
| 381 | let mut histories = repo.0; |
| 382 | histories.remove(&side); |
| 383 | let repo = Histories(histories); |
| 384 | assert!(run(contains(&pack, &repo, &tip_id, &side, 100)).unwrap()); |
| 385 | assert!(run(contains(&pack, &repo, &tip_id, &old, 100)).is_err()); |
| 386 | } |
| 387 | } |