Build a `rel_path → introducing_sha` index in one history walk. Replies are append-only, so the "introducing" commit is the unique add. Replaces an O(N paths × full diff walk) per-path search with one walk.
(
root: &Path,
rel_paths: I,
)
| 345 | /// Replies are append-only, so the "introducing" commit is the unique add. |
| 346 | /// Replaces an O(N paths × full diff walk) per-path search with one walk. |
| 347 | pub fn introducing_commits<'a, I: IntoIterator<Item = &'a str>>( |
| 348 | root: &Path, |
| 349 | rel_paths: I, |
| 350 | ) -> Result<std::collections::HashMap<String, String>> { |
| 351 | use std::collections::{HashMap, HashSet}; |
| 352 | let repo = open(root)?; |
| 353 | // Translate caller's trace-relative paths to repo-relative, and keep a |
| 354 | // reverse mapping so the returned keys read back in trace-relative form. |
| 355 | let pairs: Vec<(String, String)> = rel_paths |
| 356 | .into_iter() |
| 357 | .map(|r| (translate(&repo, root, r), r.to_string())) |
| 358 | .collect(); |
| 359 | let wanted: HashSet<String> = pairs.iter().map(|(k, _)| k.clone()).collect(); |
| 360 | let back: HashMap<String, String> = pairs.into_iter().collect(); |
| 361 | let mut hits: HashMap<String, String> = HashMap::with_capacity(wanted.len()); |
| 362 | if wanted.is_empty() { |
| 363 | return Ok(hits); |
| 364 | } |
| 365 | let mut walk = repo.revwalk()?; |
| 366 | walk.push_head()?; |
| 367 | walk.set_sorting(git2::Sort::TIME)?; |
| 368 | |
| 369 | for oid in walk { |
| 370 | let oid = oid?; |
| 371 | let commit = repo.find_commit(oid)?; |
| 372 | let commit_tree = commit.tree()?; |
| 373 | let parents: Vec<git2::Tree> = (0..commit.parent_count()) |
| 374 | .filter_map(|i| commit.parent(i).ok().and_then(|p| p.tree().ok())) |
| 375 | .collect(); |
| 376 | |
| 377 | let record = |path: Option<&Path>, hits: &mut HashMap<String, String>| { |
| 378 | let Some(p) = path else { return }; |
| 379 | let Some(s) = p.to_str() else { return }; |
| 380 | if wanted.contains(s) && !hits.contains_key(s) { |
| 381 | hits.insert(s.to_string(), oid.to_string()); |
| 382 | } |
| 383 | }; |
| 384 | |
| 385 | if parents.is_empty() { |
| 386 | commit_tree.walk(git2::TreeWalkMode::PreOrder, |dir, entry| { |
| 387 | let mut p = PathBuf::from(dir); |
| 388 | if let Some(name) = entry.name() { |
| 389 | p.push(name); |
| 390 | } |
| 391 | record(Some(p.as_path()), &mut hits); |
| 392 | git2::TreeWalkResult::Ok |
| 393 | })?; |
| 394 | } else { |
| 395 | for parent_tree in &parents { |
| 396 | if let Ok(diff) = repo.diff_tree_to_tree(Some(parent_tree), Some(&commit_tree), None) { |
| 397 | for delta in diff.deltas() { |
| 398 | record(delta.new_file().path(), &mut hits); |
| 399 | record(delta.old_file().path(), &mut hits); |
| 400 | } |
| 401 | } |
| 402 | } |
| 403 | } |
| 404 | if hits.len() == wanted.len() { |
searching dependent graphs…