//! ### Deviation//!//! Note that the algorithm implemented here is in many ways different from what `git` does.//!//! - it's less sophisticated than `git`, but prefers a candidate whose file name matches the//! destination's in identity matches, and uses that as a tie-breaker for similarity matches.//! - the set used for copy-detection is probably smaller by default.// TODO: Rewrite this based on what Git actually this, as long as there are test-cases for any 'complication'.// In practice, even this simplified version seems to have worked pretty well. use std::ops::Range; use bstr::{BStr, ByteSlice};use gix_object::tree::{EntryKind, EntryMode}; use crate::{ Rewrites, blob::{DiffLineStats, ResourceKind, platform::prepare_diff::Operation}, rewrites::{CopySource, Outcome, Tracker, tracker::visit::SourceKind}, tree::visit::{Action, ChangeId, Relation},}; /// The kind of a change.#[derive(Debug, Copy, Clone, Ord, PartialOrd, PartialEq, Eq)]pub enum ChangeKind { /// The change represents the *deletion* of an item. Deletion, /// The change represents the *modification* of an item. Modification, /// The change represents the *addition* of an item. Addition,} /// A trait providing all functionality to abstract over the concept of a change, as seen by the [`Tracker`].pub trait Change: Clone { /// Return the hash of the object behind this change for identification. /// /// Note that this is the id of the object as stored in `git`, i.e. it must have gone through workspace /// conversions. What matters is that the IDs are comparable. fn id(&self) -> &gix_hash::oid; /// Return the relation that this change may have with other changes. /// /// It allows to associate a directory with its children that are added or removed at the same moment. /// Note that this is ignored for modifications. /// /// If rename-tracking should always be on leaf-level, this should be set to `None` consistently. /// Note that trees will never be looked up by their `id` as their children are assumed to be passed in /// with the respective relationship. /// /// Also note that the tracker only sees what's given to it, it will not lookup trees or match paths itself. fn relation(&self) -> Option<Relation>; /// Return the kind of this change. fn kind(&self) -> ChangeKind; /// Return more information about the kind of entry affected by this change. fn entry_mode(&self) -> EntryMode; /// Return the id of the change along with its mode. fn id_and_entry_mode(&self) -> (&gix_hash::oid, EntryMode);} /// A set of tracked items allows to figure out their relations by figuring out their similarity.pub(crate) struct Item<T> { /// The underlying raw change change: T, /// That slice into the backing for paths. path: Range<usize>, /// If true, this item was already emitted, i.e. seen by the caller. emitted: bool,} impl<T: Change> Item<T> { fn location<'a>(&self, backing: &'a [u8]) -> &'a BStr { backing[self.path.clone()].as_ref() } fn entry_mode_compatible(&self, other: EntryMode) -> bool { use EntryKind::*; matches!( (other.kind(), self.change.entry_mode().kind()), (Blob | BlobExecutable, Blob | BlobExecutable) | (Link, Link) | (Tree, Tree) | (Commit, Commit) ) } fn is_source_for_destination_of(&self, kind: visit::SourceKind, dest_item_mode: EntryMode) -> bool { self.entry_mode_compatible(dest_item_mode) && match kind { visit::SourceKind::Rename => !self.emitted && matches!(self.change.kind(), ChangeKind::Deletion), visit::SourceKind::Copy => { matches!(self.change.kind(), ChangeKind::Modification) } } }} /// A module with types used in the user-callback in [Tracker::emit()](crate::rewrites::Tracker::emit()).pub mod visit { use bstr::BStr; use gix_object::tree::EntryMode; use crate::blob::DiffLineStats; /// The source of a rewrite, rename or copy. #[derive(Debug, Clone, PartialEq, PartialOrd)] pub struct Source<'a, T> { /// The kind of entry. pub entry_mode: EntryMode, /// The hash of the state of the source as seen in the object database. pub id: gix_hash::ObjectId, /// Further specify what kind of source this is. pub kind: SourceKind, /// The repository-relative location of this entry. pub location: &'a BStr, /// The change that was registered as source. pub change: &'a T, /// If this is a rewrite, indicate how many lines would need to change to turn this source into the destination. pub diff: Option<DiffLineStats>, } /// Further identify the kind of [Source]. #[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash)] pub enum SourceKind { /// This is the source of an entry that was renamed, as `source` was renamed to `destination`. Rename, /// This is the source of a copy, as `source` was copied into `destination`. Copy, } /// A change along with a location. #[derive(Debug, Clone)] pub struct Destination<'a, T: Clone> { /// The change at the given `location`. pub change: T, /// The repository-relative location of this destination. pub location: &'a BStr, }} ///pub mod emit { /// The error returned by [Tracker::emit()](super::Tracker::emit()). #[derive(Debug, thiserror::Error)] #[expect(missing_docs)] pub enum Error { #[error("Could not find blob for similarity checking")] FindExistingBlob(#[from] gix_object::find::existing_object::Error), #[error("Could not obtain exhaustive item set to use as possible sources for copy detection")] GetItemsForExhaustiveCopyDetection(#[source] Box<dyn std::error::Error + Send + Sync>), #[error(transparent)] SetResource(#[from] crate::blob::platform::set_resource::Error), #[error(transparent)] PrepareDiff(#[from] crate::blob::platform::prepare_diff::Error), }} /// Lifecycleimpl<T: Change> Tracker<T> { /// Create a new instance with `rewrites` configuration. pub fn new(rewrites: Rewrites) -> Self { Tracker { items: vec![], path_backing: vec![], rewrites, child_renames: Default::default(), } }} /// build state and find matches.impl<T: Change> Tracker<T> { /// We may refuse the push if that information isn't needed for what we have to track. pub fn try_push_change(&mut self, change: T, location: &BStr) -> Option<T> { let change_kind = change.kind(); if let (None, ChangeKind::Modification) = (self.rewrites.copies, change_kind) { return Some(change); } let entry_kind = change.entry_mode().kind(); let relation = change .relation() .filter(|_| matches!(change_kind, ChangeKind::Addition | ChangeKind::Deletion)); if let (None, EntryKind::Tree) = (relation, entry_kind) { return Some(change); } let start = self.path_backing.len(); self.path_backing.extend_from_slice(location); let path = start..self.path_backing.len(); self.items.push(Item { path, change, emitted: false, }); None } /// Can only be called once effectively as it alters its own state to assure each item is only emitted once. /// /// `cb(destination, source)` is called for each item, either with `Some(source)` if it's /// the destination of a copy or rename, or with `None` for source if no relation to other /// items in the tracked set exist, which is like saying 'no rename or rewrite or copy' happened. /// Note that directories with [relation](Relation) will be emitted if there is a match, along with all their matching /// child-items which are similarly bundled as rename. /// /// `objects` is used to access blob data for similarity checks if required and is taken directly from the object database. /// Worktree filters and text conversions will be applied afterwards automatically. Note that object-caching *should not* /// be enabled as caching is implemented by `diff_cache`, after all, the blob that's actually diffed is going /// through conversion steps. /// /// `diff_cache` is a way to retain a cache of resources that are prepared for rapid diffing, and it also controls /// the diff-algorithm (provided no user-algorithm is set). /// Note that we control a few options of `diff_cache` to assure it will ignore external commands. /// Note that we do not control how the `diff_cache` converts resources, it's left to the caller to decide /// if it should look at what's stored in `git`, or in the working tree, along with all diff-specific conversions. /// /// `push_source_tree(push_fn: push(change, location))` is a function that is called when the entire tree of the source /// should be added as modifications by calling `push` repeatedly to use for perfect copy tracking. Note that `push` /// will panic if `change` is not a modification, and it's valid to not call `push` at all. pub fn emit<PushSourceTreeFn, E>( &mut self, mut cb: impl FnMut(visit::Destination<'_, T>, Option<visit::Source<'_, T>>) -> Action, diff_cache: &mut crate::blob::Platform, objects: &impl gix_object::FindObjectOrHeader, mut push_source_tree: PushSourceTreeFn, ) -> Result<Outcome, emit::Error> where PushSourceTreeFn: FnMut(&mut dyn FnMut(T, &BStr)) -> Result<(), E>, E: std::error::Error + Send + Sync + 'static, { fn is_parent(change: &impl Change) -> bool { matches!(change.relation(), Some(Relation::Parent(_))) } diff_cache.options.skip_internal_diff_if_external_is_configured = false; // Early abort: if there is no pair, don't do anything. let has_work = { let (mut num_deletions, mut num_additions, mut num_modifications) = (0, 0, 0); let mut has_work = false; for change in &self.items { match change.change.kind() { ChangeKind::Deletion => { num_deletions += 1; } ChangeKind::Modification => { // This means we have copy-tracking enabled num_modifications += 1; } ChangeKind::Addition => num_additions += 1, } if (num_deletions != 0 && num_additions != 0) || (self.rewrites.copies.is_some() && num_modifications + num_additions > 1) { has_work = true; break; } } has_work }; let mut out = Outcome { options: self.rewrites, ..Default::default() }; if has_work { self.sort_items_by_id_and_location(); // Rewrites by directory (without local changes) can be pruned out quickly, // by finding only parents, their counterpart, and then all children can be matched by // relationship ID. self.match_pairs_of_kind( visit::SourceKind::Rename, &mut cb, None, /* by identity for parents */ &mut out, diff_cache, objects, Some(is_parent), )?; self.match_pairs_of_kind( visit::SourceKind::Rename, &mut cb, self.rewrites.percentage, &mut out, diff_cache, objects, None, )?; self.match_renamed_directories(&mut cb)?; if let Some(copies) = self.rewrites.copies { self.match_pairs_of_kind( visit::SourceKind::Copy, &mut cb, copies.percentage, &mut out, diff_cache, objects, None, )?; match copies.source { CopySource::FromSetOfModifiedFiles => {} CopySource::FromSetOfModifiedFilesAndAllSources => { push_source_tree(&mut |change, location| { if self.try_push_change(change, location).is_none() { // make sure these aren't viable to be emitted anymore. self.items.last_mut().expect("just pushed").emitted = true; } }) .map_err(|err| emit::Error::GetItemsForExhaustiveCopyDetection(Box::new(err)))?; self.sort_items_by_id_and_location(); self.match_pairs_of_kind( visit::SourceKind::Copy, &mut cb, copies.percentage, &mut out, diff_cache, objects, None, )?; } } } } self.items .sort_by(|a, b| a.location(&self.path_backing).cmp(b.location(&self.path_backing))); for item in self.items.drain(..).filter(|item| !item.emitted) { if cb( visit::Destination { location: item.location(&self.path_backing), change: item.change, }, None, ) .is_break() { break; } } Ok(out) }} impl<T: Change> Tracker<T> { /// Sort `items` primarily by their id, so identity-based lookups can be found quickly by /// partitioning (see `find_match`). Same-id items are then ordered by location, change-kind, /// relation and entry-mode - a total order over each item's observable identity - so that /// matching is deterministic and independent of the order in which changes were pushed, which /// the parallel dirwalk and index-traversal threads leave nondeterministic /// (see <https://github.com/GitoxideLabs/gitoxide/issues/1832>). Any items that still compare /// equal are identical in every observable field and are thus interchangeable for matching. fn sort_items_by_id_and_location(&mut self) { self.items.sort_by(|a, b| { a.change .id() .cmp(b.change.id()) .then_with(|| a.location(&self.path_backing).cmp(b.location(&self.path_backing))) .then_with(|| a.change.kind().cmp(&b.change.kind())) .then_with(|| a.change.relation().cmp(&b.change.relation())) .then_with(|| a.change.entry_mode().cmp(&b.change.entry_mode())) }); } #[expect(clippy::too_many_arguments)] fn match_pairs_of_kind( &mut self, kind: visit::SourceKind, cb: &mut impl FnMut(visit::Destination<'_, T>, Option<visit::Source<'_, T>>) -> Action, percentage: Option<f32>, out: &mut Outcome, diff_cache: &mut crate::blob::Platform, objects: &impl gix_object::FindObjectOrHeader, filter: Option<fn(&T) -> bool>, ) -> Result<(), emit::Error> { // we try to cheaply reduce the set of possibilities first, before possibly looking more exhaustively. let needs_second_pass = !needs_exact_match(percentage); // https://github.com/git/git/blob/cc01bad4a9f566cf4453c7edd6b433851b0835e2/diffcore-rename.c#L350-L369 // We would need a hashmap to be OK to not use the limit here, otherwise the performance is too bad. // This also means we don't find all renames if we hit the rename limit. if self .match_pairs(cb, None /* by identity */, kind, out, diff_cache, objects, filter)? .is_break() { return Ok(()); } if needs_second_pass { let is_limited = if self.rewrites.limit == 0 { false } else { let (num_src, num_dst) = estimate_involved_items(self.items.iter().map(|item| (item.emitted, item.change.kind())), kind); let permutations = num_src * num_dst; if permutations > self.rewrites.limit { match kind { visit::SourceKind::Rename => { out.num_similarity_checks_skipped_for_rename_tracking_due_to_limit = permutations; } visit::SourceKind::Copy => { out.num_similarity_checks_skipped_for_copy_tracking_due_to_limit = permutations; } } true } else { false } }; if !is_limited { let _ = self.match_pairs(cb, percentage, kind, out, diff_cache, objects, None)?; } } Ok(()) } #[expect(clippy::too_many_arguments)] fn match_pairs( &mut self, cb: &mut impl FnMut(visit::Destination<'_, T>, Option<visit::Source<'_, T>>) -> Action, percentage: Option<f32>, kind: visit::SourceKind, stats: &mut Outcome, diff_cache: &mut crate::blob::Platform, objects: &impl gix_object::FindObjectOrHeader, filter: Option<fn(&T) -> bool>, ) -> Result<Action, emit::Error> { let mut dest_ofs = 0; let mut num_checks = 0; let max_checks = { let limit = self.rewrites.limit.saturating_pow(2); // There can be trees with a lot of entries and pathological search behaviour, as they can be repeated // and then have a lot of similar hashes. This also means we have to search a lot of candidates which // can be too slow despite best attempts. So play it save and detect such cases 'roughly' by amount of items. if self.items.len() < 100_000 { 0 } else { limit } }; while let Some((mut dest_idx, dest)) = self.items[dest_ofs..].iter().enumerate().find_map(|(idx, item)| { (!item.emitted && matches!(item.change.kind(), ChangeKind::Addition) && filter.map_or_else( || { self.rewrites.track_empty // We always want to keep track of entries that are involved of a directory rename. // Note that this may still match them up arbitrarily if empty, but empty is empty. || matches!(item.change.relation(), Some(Relation::ChildOfParent(_))) || { let id = item.change.id(); id != gix_hash::ObjectId::empty_blob(id.kind()) } }, |f| f(&item.change), )) .then_some((idx, item)) }) { dest_idx += dest_ofs; dest_ofs = dest_idx + 1; self.items[dest_idx].location(&self.path_backing); let src = find_match( &self.items, dest, dest_idx, percentage, kind, stats, objects, diff_cache, &self.path_backing, &mut num_checks, )? .map(|(src_idx, src, diff)| { let (id, entry_mode) = src.change.id_and_entry_mode(); let id = id.to_owned(); let location = src.location(&self.path_backing); ( visit::Source { entry_mode, id, kind, location, change: &src.change, diff, }, src_idx, ) }); if max_checks != 0 && num_checks > max_checks { gix_trace::warn!( "Cancelled rename matching as there were too many iterations ({num_checks} > {max_checks})" ); return Ok(std::ops::ControlFlow::Break(())); } let Some((src, src_idx)) = src else { continue; }; let location = dest.location(&self.path_backing); let change = dest.change.clone(); let dest = visit::Destination { change, location }; let relations = if percentage.is_none() { src.change.relation().zip(dest.change.relation())Lines 1–500 of 887. Load more
//! ### Deviation //! //! Note that the algorithm implemented here is in many ways different from what `git` does. //! //! - it's less sophisticated than `git`, but prefers a candidate whose file name matches the //! destination's in identity matches, and uses that as a tie-breaker for similarity matches. //! - the set used for copy-detection is probably smaller by default. // TODO: Rewrite this based on what Git actually this, as long as there are test-cases for any 'complication'. // In practice, even this simplified version seems to have worked pretty well. use std::ops::Range; use bstr::{BStr, ByteSlice}; use gix_object::tree::{EntryKind, EntryMode}; use crate::{ Rewrites, blob::{DiffLineStats, ResourceKind, platform::prepare_diff::Operation}, rewrites::{CopySource, Outcome, Tracker, tracker::visit::SourceKind}, tree::visit::{Action, ChangeId, Relation}, }; /// The kind of a change. #[derive(Debug, Copy, Clone, Ord, PartialOrd, PartialEq, Eq)] pub enum ChangeKind { /// The change represents the *deletion* of an item. Deletion, /// The change represents the *modification* of an item. Modification, /// The change represents the *addition* of an item. Addition, } /// A trait providing all functionality to abstract over the concept of a change, as seen by the [`Tracker`]. pub trait Change: Clone { /// Return the hash of the object behind this change for identification. /// /// Note that this is the id of the object as stored in `git`, i.e. it must have gone through workspace /// conversions. What matters is that the IDs are comparable. fn id(&self) -> &gix_hash::oid; /// Return the relation that this change may have with other changes. /// /// It allows to associate a directory with its children that are added or removed at the same moment. /// Note that this is ignored for modifications. /// /// If rename-tracking should always be on leaf-level, this should be set to `None` consistently. /// Note that trees will never be looked up by their `id` as their children are assumed to be passed in /// with the respective relationship. /// /// Also note that the tracker only sees what's given to it, it will not lookup trees or match paths itself. fn relation(&self) -> Option<Relation>; /// Return the kind of this change. fn kind(&self) -> ChangeKind; /// Return more information about the kind of entry affected by this change. fn entry_mode(&self) -> EntryMode; /// Return the id of the change along with its mode. fn id_and_entry_mode(&self) -> (&gix_hash::oid, EntryMode); } /// A set of tracked items allows to figure out their relations by figuring out their similarity. pub(crate) struct Item<T> { /// The underlying raw change change: T, /// That slice into the backing for paths. path: Range<usize>, /// If true, this item was already emitted, i.e. seen by the caller. emitted: bool, } impl<T: Change> Item<T> { fn location<'a>(&self, backing: &'a [u8]) -> &'a BStr { backing[self.path.clone()].as_ref() } fn entry_mode_compatible(&self, other: EntryMode) -> bool { use EntryKind::*; matches!( (other.kind(), self.change.entry_mode().kind()), (Blob | BlobExecutable, Blob | BlobExecutable) | (Link, Link) | (Tree, Tree) | (Commit, Commit) ) } fn is_source_for_destination_of(&self, kind: visit::SourceKind, dest_item_mode: EntryMode) -> bool { self.entry_mode_compatible(dest_item_mode) && match kind { visit::SourceKind::Rename => !self.emitted && matches!(self.change.kind(), ChangeKind::Deletion), visit::SourceKind::Copy => { matches!(self.change.kind(), ChangeKind::Modification) } } } } /// A module with types used in the user-callback in [Tracker::emit()](crate::rewrites::Tracker::emit()). pub mod visit { use bstr::BStr; use gix_object::tree::EntryMode; use crate::blob::DiffLineStats; /// The source of a rewrite, rename or copy. #[derive(Debug, Clone, PartialEq, PartialOrd)] pub struct Source<'a, T> { /// The kind of entry. pub entry_mode: EntryMode, /// The hash of the state of the source as seen in the object database. pub id: gix_hash::ObjectId, /// Further specify what kind of source this is. pub kind: SourceKind, /// The repository-relative location of this entry. pub location: &'a BStr, /// The change that was registered as source. pub change: &'a T, /// If this is a rewrite, indicate how many lines would need to change to turn this source into the destination. pub diff: Option<DiffLineStats>, } /// Further identify the kind of [Source]. #[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash)] pub enum SourceKind { /// This is the source of an entry that was renamed, as `source` was renamed to `destination`. Rename, /// This is the source of a copy, as `source` was copied into `destination`. Copy, } /// A change along with a location. #[derive(Debug, Clone)] pub struct Destination<'a, T: Clone> { /// The change at the given `location`. pub change: T, /// The repository-relative location of this destination. pub location: &'a BStr, } } /// pub mod emit { /// The error returned by [Tracker::emit()](super::Tracker::emit()). #[derive(Debug, thiserror::Error)] #[expect(missing_docs)] pub enum Error { #[error("Could not find blob for similarity checking")] FindExistingBlob(#[from] gix_object::find::existing_object::Error), #[error("Could not obtain exhaustive item set to use as possible sources for copy detection")] GetItemsForExhaustiveCopyDetection(#[source] Box<dyn std::error::Error + Send + Sync>), #[error(transparent)] SetResource(#[from] crate::blob::platform::set_resource::Error), #[error(transparent)] PrepareDiff(#[from] crate::blob::platform::prepare_diff::Error), } } /// Lifecycle impl<T: Change> Tracker<T> { /// Create a new instance with `rewrites` configuration. pub fn new(rewrites: Rewrites) -> Self { Tracker { items: vec![], path_backing: vec![], rewrites, child_renames: Default::default(), } } } /// build state and find matches. impl<T: Change> Tracker<T> { /// We may refuse the push if that information isn't needed for what we have to track. pub fn try_push_change(&mut self, change: T, location: &BStr) -> Option<T> { let change_kind = change.kind(); if let (None, ChangeKind::Modification) = (self.rewrites.copies, change_kind) { return Some(change); } let entry_kind = change.entry_mode().kind(); let relation = change .relation() .filter(|_| matches!(change_kind, ChangeKind::Addition | ChangeKind::Deletion)); if let (None, EntryKind::Tree) = (relation, entry_kind) { return Some(change); } let start = self.path_backing.len(); self.path_backing.extend_from_slice(location); let path = start..self.path_backing.len(); self.items.push(Item { path, change, emitted: false, }); None } /// Can only be called once effectively as it alters its own state to assure each item is only emitted once. /// /// `cb(destination, source)` is called for each item, either with `Some(source)` if it's /// the destination of a copy or rename, or with `None` for source if no relation to other /// items in the tracked set exist, which is like saying 'no rename or rewrite or copy' happened. /// Note that directories with [relation](Relation) will be emitted if there is a match, along with all their matching /// child-items which are similarly bundled as rename. /// /// `objects` is used to access blob data for similarity checks if required and is taken directly from the object database. /// Worktree filters and text conversions will be applied afterwards automatically. Note that object-caching *should not* /// be enabled as caching is implemented by `diff_cache`, after all, the blob that's actually diffed is going /// through conversion steps. /// /// `diff_cache` is a way to retain a cache of resources that are prepared for rapid diffing, and it also controls /// the diff-algorithm (provided no user-algorithm is set). /// Note that we control a few options of `diff_cache` to assure it will ignore external commands. /// Note that we do not control how the `diff_cache` converts resources, it's left to the caller to decide /// if it should look at what's stored in `git`, or in the working tree, along with all diff-specific conversions. /// /// `push_source_tree(push_fn: push(change, location))` is a function that is called when the entire tree of the source /// should be added as modifications by calling `push` repeatedly to use for perfect copy tracking. Note that `push` /// will panic if `change` is not a modification, and it's valid to not call `push` at all. pub fn emit<PushSourceTreeFn, E>( &mut self, mut cb: impl FnMut(visit::Destination<'_, T>, Option<visit::Source<'_, T>>) -> Action, diff_cache: &mut crate::blob::Platform, objects: &impl gix_object::FindObjectOrHeader, mut push_source_tree: PushSourceTreeFn, ) -> Result<Outcome, emit::Error> where PushSourceTreeFn: FnMut(&mut dyn FnMut(T, &BStr)) -> Result<(), E>, E: std::error::Error + Send + Sync + 'static, { fn is_parent(change: &impl Change) -> bool { matches!(change.relation(), Some(Relation::Parent(_))) } diff_cache.options.skip_internal_diff_if_external_is_configured = false; // Early abort: if there is no pair, don't do anything. let has_work = { let (mut num_deletions, mut num_additions, mut num_modifications) = (0, 0, 0); let mut has_work = false; for change in &self.items { match change.change.kind() { ChangeKind::Deletion => { num_deletions += 1; } ChangeKind::Modification => { // This means we have copy-tracking enabled num_modifications += 1; } ChangeKind::Addition => num_additions += 1, } if (num_deletions != 0 && num_additions != 0) || (self.rewrites.copies.is_some() && num_modifications + num_additions > 1) { has_work = true; break; } } has_work }; let mut out = Outcome { options: self.rewrites, ..Default::default() }; if has_work { self.sort_items_by_id_and_location(); // Rewrites by directory (without local changes) can be pruned out quickly, // by finding only parents, their counterpart, and then all children can be matched by // relationship ID. self.match_pairs_of_kind( visit::SourceKind::Rename, &mut cb, None, /* by identity for parents */ &mut out, diff_cache, objects, Some(is_parent), )?; self.match_pairs_of_kind( visit::SourceKind::Rename, &mut cb, self.rewrites.percentage, &mut out, diff_cache, objects, None, )?; self.match_renamed_directories(&mut cb)?; if let Some(copies) = self.rewrites.copies { self.match_pairs_of_kind( visit::SourceKind::Copy, &mut cb, copies.percentage, &mut out, diff_cache, objects, None, )?; match copies.source { CopySource::FromSetOfModifiedFiles => {} CopySource::FromSetOfModifiedFilesAndAllSources => { push_source_tree(&mut |change, location| { if self.try_push_change(change, location).is_none() { // make sure these aren't viable to be emitted anymore. self.items.last_mut().expect("just pushed").emitted = true; } }) .map_err(|err| emit::Error::GetItemsForExhaustiveCopyDetection(Box::new(err)))?; self.sort_items_by_id_and_location(); self.match_pairs_of_kind( visit::SourceKind::Copy, &mut cb, copies.percentage, &mut out, diff_cache, objects, None, )?; } } } } self.items .sort_by(|a, b| a.location(&self.path_backing).cmp(b.location(&self.path_backing))); for item in self.items.drain(..).filter(|item| !item.emitted) { if cb( visit::Destination { location: item.location(&self.path_backing), change: item.change, }, None, ) .is_break() { break; } } Ok(out) } } impl<T: Change> Tracker<T> { /// Sort `items` primarily by their id, so identity-based lookups can be found quickly by /// partitioning (see `find_match`). Same-id items are then ordered by location, change-kind, /// relation and entry-mode - a total order over each item's observable identity - so that /// matching is deterministic and independent of the order in which changes were pushed, which /// the parallel dirwalk and index-traversal threads leave nondeterministic /// (see <https://github.com/GitoxideLabs/gitoxide/issues/1832>). Any items that still compare /// equal are identical in every observable field and are thus interchangeable for matching. fn sort_items_by_id_and_location(&mut self) { self.items.sort_by(|a, b| { a.change .id() .cmp(b.change.id()) .then_with(|| a.location(&self.path_backing).cmp(b.location(&self.path_backing))) .then_with(|| a.change.kind().cmp(&b.change.kind())) .then_with(|| a.change.relation().cmp(&b.change.relation())) .then_with(|| a.change.entry_mode().cmp(&b.change.entry_mode())) }); } #[expect(clippy::too_many_arguments)] fn match_pairs_of_kind( &mut self, kind: visit::SourceKind, cb: &mut impl FnMut(visit::Destination<'_, T>, Option<visit::Source<'_, T>>) -> Action, percentage: Option<f32>, out: &mut Outcome, diff_cache: &mut crate::blob::Platform, objects: &impl gix_object::FindObjectOrHeader, filter: Option<fn(&T) -> bool>, ) -> Result<(), emit::Error> { // we try to cheaply reduce the set of possibilities first, before possibly looking more exhaustively. let needs_second_pass = !needs_exact_match(percentage); // https://github.com/git/git/blob/cc01bad4a9f566cf4453c7edd6b433851b0835e2/diffcore-rename.c#L350-L369 // We would need a hashmap to be OK to not use the limit here, otherwise the performance is too bad. // This also means we don't find all renames if we hit the rename limit. if self .match_pairs(cb, None /* by identity */, kind, out, diff_cache, objects, filter)? .is_break() { return Ok(()); } if needs_second_pass { let is_limited = if self.rewrites.limit == 0 { false } else { let (num_src, num_dst) = estimate_involved_items(self.items.iter().map(|item| (item.emitted, item.change.kind())), kind); let permutations = num_src * num_dst; if permutations > self.rewrites.limit { match kind { visit::SourceKind::Rename => { out.num_similarity_checks_skipped_for_rename_tracking_due_to_limit = permutations; } visit::SourceKind::Copy => { out.num_similarity_checks_skipped_for_copy_tracking_due_to_limit = permutations; } } true } else { false } }; if !is_limited { let _ = self.match_pairs(cb, percentage, kind, out, diff_cache, objects, None)?; } } Ok(()) } #[expect(clippy::too_many_arguments)] fn match_pairs( &mut self, cb: &mut impl FnMut(visit::Destination<'_, T>, Option<visit::Source<'_, T>>) -> Action, percentage: Option<f32>, kind: visit::SourceKind, stats: &mut Outcome, diff_cache: &mut crate::blob::Platform, objects: &impl gix_object::FindObjectOrHeader, filter: Option<fn(&T) -> bool>, ) -> Result<Action, emit::Error> { let mut dest_ofs = 0; let mut num_checks = 0; let max_checks = { let limit = self.rewrites.limit.saturating_pow(2); // There can be trees with a lot of entries and pathological search behaviour, as they can be repeated // and then have a lot of similar hashes. This also means we have to search a lot of candidates which // can be too slow despite best attempts. So play it save and detect such cases 'roughly' by amount of items. if self.items.len() < 100_000 { 0 } else { limit } }; while let Some((mut dest_idx, dest)) = self.items[dest_ofs..].iter().enumerate().find_map(|(idx, item)| { (!item.emitted && matches!(item.change.kind(), ChangeKind::Addition) && filter.map_or_else( || { self.rewrites.track_empty // We always want to keep track of entries that are involved of a directory rename. // Note that this may still match them up arbitrarily if empty, but empty is empty. || matches!(item.change.relation(), Some(Relation::ChildOfParent(_))) || { let id = item.change.id(); id != gix_hash::ObjectId::empty_blob(id.kind()) } }, |f| f(&item.change), )) .then_some((idx, item)) }) { dest_idx += dest_ofs; dest_ofs = dest_idx + 1; self.items[dest_idx].location(&self.path_backing); let src = find_match( &self.items, dest, dest_idx, percentage, kind, stats, objects, diff_cache, &self.path_backing, &mut num_checks, )? .map(|(src_idx, src, diff)| { let (id, entry_mode) = src.change.id_and_entry_mode(); let id = id.to_owned(); let location = src.location(&self.path_backing); ( visit::Source { entry_mode, id, kind, location, change: &src.change, diff, }, src_idx, ) }); if max_checks != 0 && num_checks > max_checks { gix_trace::warn!( "Cancelled rename matching as there were too many iterations ({num_checks} > {max_checks})" ); return Ok(std::ops::ControlFlow::Break(())); } let Some((src, src_idx)) = src else { continue; }; let location = dest.location(&self.path_backing); let change = dest.change.clone(); let dest = visit::Destination { change, location }; let relations = if percentage.is_none() { src.change.relation().zip(dest.change.relation())