diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-06-19 09:26:03 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-06-19 09:26:03 +0000 |
commit | 9918693037dce8aa4bb6f08741b6812923486c18 (patch) | |
tree | 21d2b40bec7e6a7ea664acee056eb3d08e15a1cf /vendor/gix/src/object | |
parent | Releasing progress-linux version 1.75.0+dfsg1-5~progress7.99u1. (diff) | |
download | rustc-9918693037dce8aa4bb6f08741b6812923486c18.tar.xz rustc-9918693037dce8aa4bb6f08741b6812923486c18.zip |
Merging upstream version 1.76.0+dfsg1.
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'vendor/gix/src/object')
-rw-r--r-- | vendor/gix/src/object/blob.rs | 276 | ||||
-rw-r--r-- | vendor/gix/src/object/errors.rs | 6 | ||||
-rw-r--r-- | vendor/gix/src/object/tree/diff/change.rs | 47 | ||||
-rw-r--r-- | vendor/gix/src/object/tree/diff/for_each.rs | 155 | ||||
-rw-r--r-- | vendor/gix/src/object/tree/diff/mod.rs | 32 | ||||
-rw-r--r-- | vendor/gix/src/object/tree/diff/rewrites.rs | 108 | ||||
-rw-r--r-- | vendor/gix/src/object/tree/diff/tracked.rs | 490 | ||||
-rw-r--r-- | vendor/gix/src/object/tree/iter.rs | 2 | ||||
-rw-r--r-- | vendor/gix/src/object/tree/mod.rs | 5 | ||||
-rw-r--r-- | vendor/gix/src/object/tree/traverse.rs | 9 |
10 files changed, 345 insertions, 785 deletions
diff --git a/vendor/gix/src/object/blob.rs b/vendor/gix/src/object/blob.rs index ef19c302a..59629727f 100644 --- a/vendor/gix/src/object/blob.rs +++ b/vendor/gix/src/object/blob.rs @@ -5,61 +5,132 @@ use crate::{Blob, ObjectDetached}; pub mod diff { use std::ops::Range; - use crate::{bstr::ByteSlice, object::blob::diff::line::Change}; + use gix_diff::blob::{platform::prepare_diff::Operation, ResourceKind}; + + use crate::{ + bstr::ByteSlice, + object::{blob::diff::lines::Change, tree::diff::change::Event}, + }; /// A platform to keep temporary information to perform line diffs on modified blobs. /// - pub struct Platform<'old, 'new> { - /// The previous version of the blob. - pub old: crate::Object<'old>, - /// The new version of the blob. - pub new: crate::Object<'new>, - /// The algorithm to use when calling [imara_diff::diff()][gix_diff::blob::diff()]. - /// This value is determined by the `diff.algorithm` configuration. - pub algo: gix_diff::blob::Algorithm, + pub struct Platform<'a> { + /// The cache holding diffable data related to our blobs. + pub resource_cache: &'a mut gix_diff::blob::Platform, } /// pub mod init { - /// The error returned by [`Platform::from_ids()`][super::Platform::from_ids()]. - #[derive(Debug, thiserror::Error)] - #[allow(missing_docs)] - pub enum Error { - #[error("Could not find the previous blob or the new blob to diff against")] - FindExisting(#[from] crate::object::find::existing::Error), - #[error("Could not obtain diff algorithm from configuration")] - DiffAlgorithm(#[from] crate::config::diff::algorithm::Error), - } + /// The error returned by [`Platform::from_tree_change()`][super::Platform::from_tree_change()]. + pub type Error = gix_diff::blob::platform::set_resource::Error; } - impl<'old, 'new> Platform<'old, 'new> { - /// Produce a platform for performing various diffs after obtaining the object data of `previous_id` and `new_id`. - /// - /// Note that these objects are treated as raw data and are assumed to be blobs. - pub fn from_ids( - previous_id: &crate::Id<'old>, - new_id: &crate::Id<'new>, - ) -> Result<Platform<'old, 'new>, init::Error> { - match previous_id - .object() - .and_then(|old| new_id.object().map(|new| (old, new))) - { - Ok((old, new)) => { - let algo = match new_id.repo.config.diff_algorithm() { - Ok(algo) => algo, - Err(err) => return Err(err.into()), - }; - Ok(Platform { old, new, algo }) + impl<'a> Platform<'a> { + /// Produce a platform for performing various diffs after obtaining the data from a single `tree_change`. + pub fn from_tree_change( + tree_change: &crate::object::tree::diff::Change<'_, '_, '_>, + resource_cache: &'a mut gix_diff::blob::Platform, + ) -> Result<Platform<'a>, init::Error> { + match tree_change.event { + Event::Addition { entry_mode, id } => { + resource_cache.set_resource( + id.repo.object_hash().null(), + entry_mode.kind(), + tree_change.location, + ResourceKind::OldOrSource, + &id.repo.objects, + )?; + resource_cache.set_resource( + id.inner, + entry_mode.kind(), + tree_change.location, + ResourceKind::NewOrDestination, + &id.repo.objects, + )?; + } + Event::Deletion { entry_mode, id } => { + resource_cache.set_resource( + id.inner, + entry_mode.kind(), + tree_change.location, + ResourceKind::OldOrSource, + &id.repo.objects, + )?; + resource_cache.set_resource( + id.repo.object_hash().null(), + entry_mode.kind(), + tree_change.location, + ResourceKind::NewOrDestination, + &id.repo.objects, + )?; + } + Event::Modification { + previous_entry_mode, + previous_id, + entry_mode, + id, + } => { + resource_cache.set_resource( + previous_id.inner, + previous_entry_mode.kind(), + tree_change.location, + ResourceKind::OldOrSource, + &previous_id.repo.objects, + )?; + resource_cache.set_resource( + id.inner, + entry_mode.kind(), + tree_change.location, + ResourceKind::NewOrDestination, + &id.repo.objects, + )?; + } + Event::Rewrite { + source_location, + source_entry_mode, + source_id, + entry_mode, + id, + diff: _, + copy: _, + } => { + resource_cache.set_resource( + source_id.inner, + source_entry_mode.kind(), + source_location, + ResourceKind::OldOrSource, + &source_id.repo.objects, + )?; + resource_cache.set_resource( + id.inner, + entry_mode.kind(), + tree_change.location, + ResourceKind::NewOrDestination, + &id.repo.objects, + )?; } - Err(err) => Err(err.into()), } + Ok(Self { resource_cache }) } } /// - pub mod line { + pub mod lines { use crate::bstr::BStr; + /// The error returned by [Platform::lines()](super::Platform::lines()). + #[derive(Debug, thiserror::Error)] + #[allow(missing_docs)] + pub enum Error<E> + where + E: std::error::Error + Send + Sync + 'static, + { + #[error(transparent)] + ProcessHunk(E), + #[error(transparent)] + PrepareDiff(#[from] gix_diff::blob::platform::prepare_diff::Error), + } + /// A change to a hunk of lines. pub enum Change<'a, 'data> { /// Lines were added. @@ -82,70 +153,91 @@ pub mod diff { } } - impl<'old, 'new> Platform<'old, 'new> { + impl<'a> Platform<'a> { /// Perform a diff on lines between the old and the new version of a blob, passing each hunk of lines to `process_hunk`. - /// The diffing algorithm is determined by the `diff.algorithm` configuration. - /// - /// Note that you can invoke the diff more flexibly as well. + /// The diffing algorithm is determined by the `diff.algorithm` configuration, or individual diff drivers. + /// Note that `process_hunk` is not called if one of the involved resources are binary, but that can be determined + /// by introspecting the outcome. // TODO: more tests (only tested insertion right now) - pub fn lines<FnH, E>(&self, mut process_hunk: FnH) -> Result<(), E> + pub fn lines<FnH, E>( + &mut self, + mut process_hunk: FnH, + ) -> Result<gix_diff::blob::platform::prepare_diff::Outcome<'_>, lines::Error<E>> where - FnH: FnMut(line::Change<'_, '_>) -> Result<(), E>, - E: std::error::Error, + FnH: FnMut(lines::Change<'_, '_>) -> Result<(), E>, + E: std::error::Error + Send + Sync + 'static, { - let input = self.line_tokens(); - let mut err = None; - let mut lines = Vec::new(); - gix_diff::blob::diff(self.algo, &input, |before: Range<u32>, after: Range<u32>| { - if err.is_some() { - return; + self.resource_cache.options.skip_internal_diff_if_external_is_configured = false; + + let prep = self.resource_cache.prepare_diff()?; + match prep.operation { + Operation::InternalDiff { algorithm } => { + let input = prep.interned_input(); + let mut err = None; + let mut lines = Vec::new(); + + gix_diff::blob::diff(algorithm, &input, |before: Range<u32>, after: Range<u32>| { + if err.is_some() { + return; + } + lines.clear(); + lines.extend( + input.before[before.start as usize..before.end as usize] + .iter() + .map(|&line| input.interner[line].as_bstr()), + ); + let end_of_before = lines.len(); + lines.extend( + input.after[after.start as usize..after.end as usize] + .iter() + .map(|&line| input.interner[line].as_bstr()), + ); + let hunk_before = &lines[..end_of_before]; + let hunk_after = &lines[end_of_before..]; + if hunk_after.is_empty() { + err = process_hunk(Change::Deletion { lines: hunk_before }).err(); + } else if hunk_before.is_empty() { + err = process_hunk(Change::Addition { lines: hunk_after }).err(); + } else { + err = process_hunk(Change::Modification { + lines_before: hunk_before, + lines_after: hunk_after, + }) + .err(); + } + }); + + if let Some(err) = err { + return Err(lines::Error::ProcessHunk(err)); + } } - lines.clear(); - lines.extend( - input.before[before.start as usize..before.end as usize] - .iter() - .map(|&line| input.interner[line].as_bstr()), - ); - let end_of_before = lines.len(); - lines.extend( - input.after[after.start as usize..after.end as usize] - .iter() - .map(|&line| input.interner[line].as_bstr()), - ); - let hunk_before = &lines[..end_of_before]; - let hunk_after = &lines[end_of_before..]; - if hunk_after.is_empty() { - err = process_hunk(Change::Deletion { lines: hunk_before }).err(); - } else if hunk_before.is_empty() { - err = process_hunk(Change::Addition { lines: hunk_after }).err(); - } else { - err = process_hunk(Change::Modification { - lines_before: hunk_before, - lines_after: hunk_after, - }) - .err(); + Operation::ExternalCommand { .. } => { + unreachable!("we disabled that") } - }); - - match err { - Some(err) => Err(err), - None => Ok(()), - } + Operation::SourceOrDestinationIsBinary => {} + }; + Ok(prep) } /// Count the amount of removed and inserted lines efficiently. - pub fn line_counts(&self) -> gix_diff::blob::sink::Counter<()> { - let tokens = self.line_tokens(); - gix_diff::blob::diff(self.algo, &tokens, gix_diff::blob::sink::Counter::default()) - } + /// Note that nothing will happen if one of the inputs is binary, and `None` will be returned. + pub fn line_counts( + &mut self, + ) -> Result<Option<gix_diff::blob::sink::Counter<()>>, gix_diff::blob::platform::prepare_diff::Error> { + self.resource_cache.options.skip_internal_diff_if_external_is_configured = false; - /// Return a tokenizer which treats lines as smallest unit for use in a [diff operation][gix_diff::blob::diff()]. - /// - /// The line separator is determined according to normal git rules and filters. - pub fn line_tokens(&self) -> gix_diff::blob::intern::InternedInput<&[u8]> { - // TODO: make use of `core.eol` and/or filters to do line-counting correctly. It's probably - // OK to just know how these objects are saved to know what constitutes a line. - gix_diff::blob::intern::InternedInput::new(self.old.data.as_bytes(), self.new.data.as_bytes()) + let prep = self.resource_cache.prepare_diff()?; + match prep.operation { + Operation::InternalDiff { algorithm } => { + let tokens = prep.interned_input(); + let counter = gix_diff::blob::diff(algorithm, &tokens, gix_diff::blob::sink::Counter::default()); + Ok(Some(counter)) + } + Operation::ExternalCommand { .. } => { + unreachable!("we disabled that") + } + Operation::SourceOrDestinationIsBinary => Ok(None), + } } } } diff --git a/vendor/gix/src/object/errors.rs b/vendor/gix/src/object/errors.rs index 92789b6cb..db81daacb 100644 --- a/vendor/gix/src/object/errors.rs +++ b/vendor/gix/src/object/errors.rs @@ -20,12 +20,12 @@ pub mod find { /// Indicate that an error occurred when trying to find an object. #[derive(Debug, thiserror::Error)] #[error(transparent)] - pub struct Error(#[from] pub gix_odb::find::Error); + pub struct Error(#[from] pub gix_object::find::Error); /// pub mod existing { /// An object could not be found in the database, or an error occurred when trying to obtain it. - pub type Error = gix_odb::find::existing::Error; + pub type Error = gix_object::find::existing::Error; } } @@ -34,5 +34,5 @@ pub mod write { /// An error to indicate writing to the loose object store failed. #[derive(Debug, thiserror::Error)] #[error(transparent)] - pub struct Error(#[from] pub gix_odb::find::Error); + pub struct Error(#[from] pub gix_object::find::Error); } diff --git a/vendor/gix/src/object/tree/diff/change.rs b/vendor/gix/src/object/tree/diff/change.rs index e6826d6ed..e4eb5f3df 100644 --- a/vendor/gix/src/object/tree/diff/change.rs +++ b/vendor/gix/src/object/tree/diff/change.rs @@ -1,17 +1,4 @@ -use crate::{bstr::BStr, Id}; - -/// Information about the diff performed to detect similarity of a [Rewrite][Event::Rewrite]. -#[derive(Debug, Default, Clone, Copy, Eq, PartialEq)] -pub struct DiffLineStats { - /// The amount of lines to remove from the source to get to the destination. - pub removals: u32, - /// The amount of lines to add to the source to get to the destination. - pub insertions: u32, - /// The amount of lines of the previous state, in the source. - pub before: u32, - /// The amount of lines of the new state, in the destination. - pub after: u32, -} +use crate::{bstr::BStr, diff::blob::DiffLineStats, Id}; /// An event emitted when finding differences between two trees. #[derive(Debug, Clone, Copy)] @@ -80,25 +67,25 @@ pub enum Event<'a, 'old, 'new> { }, } -impl<'a, 'old, 'new> Event<'a, 'old, 'new> { - /// Produce a platform for performing a line-diff, or `None` if this is not a [`Modification`][Event::Modification] - /// or one of the entries to compare is not a blob. - pub fn diff( +impl<'a, 'old, 'new> super::Change<'a, 'old, 'new> { + /// Produce a platform for performing a line-diff no matter whether the underlying [Event] is an addition, modification, + /// deletion or rewrite. + /// Use `resource_cache` to store the diffable data and possibly reuse previously stored data. + /// Afterwards the platform, which holds on to `resource_cache`, can be used to perform ready-made operations on the + /// pre-set resources. + /// + /// ### Warning about Memory Consumption + /// + /// `resource_cache` only grows, so one should call [`gix_diff::blob::Platform::clear_resource_cache`] occasionally. + pub fn diff<'b>( &self, - ) -> Option<Result<crate::object::blob::diff::Platform<'old, 'new>, crate::object::blob::diff::init::Error>> { - match self { - Event::Modification { - previous_entry_mode, - previous_id, - entry_mode, - id, - } if entry_mode.is_blob() && previous_entry_mode.is_blob() => { - Some(crate::object::blob::diff::Platform::from_ids(previous_id, id)) - } - _ => None, - } + resource_cache: &'b mut gix_diff::blob::Platform, + ) -> Result<crate::object::blob::diff::Platform<'b>, crate::object::blob::diff::init::Error> { + crate::object::blob::diff::Platform::from_tree_change(self, resource_cache) } +} +impl<'a, 'old, 'new> Event<'a, 'old, 'new> { /// Return the current mode of this instance. pub fn entry_mode(&self) -> gix_object::tree::EntryMode { match self { diff --git a/vendor/gix/src/object/tree/diff/for_each.rs b/vendor/gix/src/object/tree/diff/for_each.rs index 3932f9027..c1b76fbe6 100644 --- a/vendor/gix/src/object/tree/diff/for_each.rs +++ b/vendor/gix/src/object/tree/diff/for_each.rs @@ -1,14 +1,11 @@ use gix_object::TreeRefIter; -use gix_odb::FindExt; use super::{change, Action, Change, Platform}; use crate::{ bstr::BStr, + diff::{rewrites, rewrites::tracker}, ext::ObjectIdExt, - object::tree::{ - diff, - diff::{rewrites, tracked}, - }, + object::tree::diff, Repository, Tree, }; @@ -20,12 +17,10 @@ pub enum Error { Diff(#[from] gix_diff::tree::changes::Error), #[error("The user-provided callback failed")] ForEach(#[source] Box<dyn std::error::Error + Send + Sync + 'static>), - #[error("Could not find blob for similarity checking")] - FindExistingBlob(#[from] crate::object::find::existing::Error), - #[error("Could not configure diff algorithm prior to checking similarity")] - ConfigureDiffAlgorithm(#[from] crate::config::diff::algorithm::Error), - #[error("Could not traverse tree to obtain possible sources for copies")] - TraverseTreeForExhaustiveCopyDetection(#[from] gix_traverse::tree::breadthfirst::Error), + #[error(transparent)] + ResourceCache(#[from] crate::repository::diff::resource_cache::Error), + #[error("Failure during rename tracking")] + RenameTracking(#[from] tracker::emit::Error), } /// @@ -49,24 +44,59 @@ impl<'a, 'old> Platform<'a, 'old> { where E: std::error::Error + Sync + Send + 'static, { + self.for_each_to_obtain_tree_inner(other, for_each, None) + } + + /// Like [`Self::for_each_to_obtain_tree()`], but with a reusable `resource_cache` which is used to perform + /// diffs fast. + /// + /// Reusing it between multiple invocations saves a lot of IOps as it avoids the creation + /// of a temporary `resource_cache` that triggers reading or checking for multiple gitattribute files. + /// Note that it's recommended to call [`gix_diff::blob::Platform::clear_resource_cache()`] between the calls + /// to avoid runaway memory usage, as the cache isn't limited. + /// + /// Note that to do rename tracking like `git` does, one has to configure the `resource_cache` with + /// a conversion pipeline that uses [`gix_diff::blob::pipeline::Mode::ToGit`]. + pub fn for_each_to_obtain_tree_with_cache<'new, E>( + &mut self, + other: &Tree<'new>, + resource_cache: &mut gix_diff::blob::Platform, + for_each: impl FnMut(Change<'_, 'old, 'new>) -> Result<Action, E>, + ) -> Result<Outcome, Error> + where + E: std::error::Error + Sync + Send + 'static, + { + self.for_each_to_obtain_tree_inner(other, for_each, Some(resource_cache)) + } + + fn for_each_to_obtain_tree_inner<'new, E>( + &mut self, + other: &Tree<'new>, + for_each: impl FnMut(Change<'_, 'old, 'new>) -> Result<Action, E>, + resource_cache: Option<&mut gix_diff::blob::Platform>, + ) -> Result<Outcome, Error> + where + E: std::error::Error + Sync + Send + 'static, + { let repo = self.lhs.repo; let mut delegate = Delegate { src_tree: self.lhs, other_repo: other.repo, recorder: gix_diff::tree::Recorder::default().track_location(self.tracking), visit: for_each, - tracked: self.rewrites.map(|r| tracked::State::new(r, self.tracking)), + location: self.tracking, + tracked: self.rewrites.map(rewrites::Tracker::new), err: None, }; match gix_diff::tree::Changes::from(TreeRefIter::from_bytes(&self.lhs.data)).needed_to_obtain( TreeRefIter::from_bytes(&other.data), &mut self.state, - |oid, buf| repo.objects.find_tree_iter(oid, buf), + &repo.objects, &mut delegate, ) { Ok(()) => { let outcome = Outcome { - rewrites: delegate.process_tracked_changes()?, + rewrites: delegate.process_tracked_changes(resource_cache)?, }; match delegate.err { Some(err) => Err(Error::ForEach(Box::new(err))), @@ -88,7 +118,8 @@ struct Delegate<'a, 'old, 'new, VisitFn, E> { other_repo: &'new Repository, recorder: gix_diff::tree::Recorder, visit: VisitFn, - tracked: Option<tracked::State>, + tracked: Option<rewrites::Tracker<gix_diff::tree::visit::Change>>, + location: Option<gix_diff::tree::recorder::Location>, err: Option<E>, } @@ -138,12 +169,25 @@ where } } - fn process_tracked_changes(&mut self) -> Result<Option<rewrites::Outcome>, Error> { + fn process_tracked_changes( + &mut self, + diff_cache: Option<&mut gix_diff::blob::Platform>, + ) -> Result<Option<rewrites::Outcome>, Error> { let tracked = match self.tracked.as_mut() { Some(t) => t, None => return Ok(None), }; + let repo = self.src_tree.repo; + let mut storage; + let diff_cache = match diff_cache { + Some(cache) => cache, + None => { + storage = repo.diff_resource_cache(gix_diff::blob::pipeline::Mode::ToGit, Default::default())?; + &mut storage + } + }; + let outcome = tracked.emit( |dest, source| match source { Some(source) => { @@ -152,14 +196,14 @@ where location: dest.location, event: diff::change::Event::Rewrite { source_location: source.location, - source_entry_mode: source.mode, + source_entry_mode: source.entry_mode, source_id: source.id.attach(self.src_tree.repo), entry_mode: mode, id: oid.to_owned().attach(self.other_repo), diff: source.diff, copy: match source.kind { - tracked::visit::Kind::RenameTarget => false, - tracked::visit::Kind::CopyDestination => true, + tracker::visit::SourceKind::Rename => false, + tracker::visit::SourceKind::Copy => true, }, }, }; @@ -181,7 +225,13 @@ where &mut self.err, ), }, - self.src_tree, + diff_cache, + &self.src_tree.repo.objects, + |push| { + self.src_tree + .traverse() + .breadthfirst(&mut tree_to_changes::Delegate::new(push, self.location)) + }, )?; Ok(Some(outcome)) } @@ -234,3 +284,68 @@ where } } } + +mod tree_to_changes { + use gix_diff::tree::visit::Change; + use gix_object::tree::EntryRef; + + use crate::bstr::BStr; + + pub struct Delegate<'a> { + push: &'a mut dyn FnMut(Change, &BStr), + recorder: gix_traverse::tree::Recorder, + } + + impl<'a> Delegate<'a> { + pub fn new( + push: &'a mut dyn FnMut(Change, &BStr), + location: Option<gix_diff::tree::recorder::Location>, + ) -> Self { + let location = location.map(|t| match t { + gix_diff::tree::recorder::Location::FileName => gix_traverse::tree::recorder::Location::FileName, + gix_diff::tree::recorder::Location::Path => gix_traverse::tree::recorder::Location::Path, + }); + Self { + push, + recorder: gix_traverse::tree::Recorder::default().track_location(location), + } + } + } + + impl gix_traverse::tree::Visit for Delegate<'_> { + fn pop_front_tracked_path_and_set_current(&mut self) { + self.recorder.pop_front_tracked_path_and_set_current() + } + + fn push_back_tracked_path_component(&mut self, component: &BStr) { + self.recorder.push_back_tracked_path_component(component) + } + + fn push_path_component(&mut self, component: &BStr) { + self.recorder.push_path_component(component) + } + + fn pop_path_component(&mut self) { + self.recorder.pop_path_component(); + } + + fn visit_tree(&mut self, _entry: &EntryRef<'_>) -> gix_traverse::tree::visit::Action { + gix_traverse::tree::visit::Action::Continue + } + + fn visit_nontree(&mut self, entry: &EntryRef<'_>) -> gix_traverse::tree::visit::Action { + if entry.mode.is_blob() { + (self.push)( + Change::Modification { + previous_entry_mode: entry.mode, + previous_oid: gix_hash::ObjectId::null(entry.oid.kind()), + entry_mode: entry.mode, + oid: entry.oid.to_owned(), + }, + self.recorder.path(), + ); + } + gix_traverse::tree::visit::Action::Continue + } + } +} diff --git a/vendor/gix/src/object/tree/diff/mod.rs b/vendor/gix/src/object/tree/diff/mod.rs index 5f7a041e4..858775610 100644 --- a/vendor/gix/src/object/tree/diff/mod.rs +++ b/vendor/gix/src/object/tree/diff/mod.rs @@ -1,6 +1,6 @@ use gix_diff::tree::recorder::Location; -use crate::{bstr::BStr, Tree}; +use crate::{bstr::BStr, diff::Rewrites, Tree}; /// Returned by the `for_each` function to control flow. #[derive(Default, Clone, Copy, PartialOrd, PartialEq, Ord, Eq, Hash)] @@ -39,7 +39,7 @@ impl<'repo> Tree<'repo> { /// try to access blobs to compute a similarity metric. Thus, it's more compatible to turn rewrite tracking off /// using [`Platform::track_rewrites()`]. #[allow(clippy::result_large_err)] - pub fn changes<'a>(&'a self) -> Result<Platform<'a, 'repo>, rewrites::Error> { + pub fn changes<'a>(&'a self) -> Result<Platform<'a, 'repo>, crate::diff::new_rewrites::Error> { Ok(Platform { state: Default::default(), lhs: self, @@ -58,34 +58,6 @@ pub struct Platform<'a, 'repo> { rewrites: Option<Rewrites>, } -/// A structure to capture how to perform rename and copy tracking -#[derive(Debug, Copy, Clone, PartialEq)] -pub struct Rewrites { - /// If `Some(…)`, do also find copies. `None` is the default which does not try to detect copies at all. - /// - /// Note that this is an even more expensive operation than detecting renames as files. - pub copies: Option<rewrites::Copies>, - /// The percentage of similarity needed for files to be considered renamed, defaulting to `Some(0.5)`. - /// This field is similar to `git diff -M50%`. - /// - /// If `None`, files are only considered equal if their content matches 100%. - /// Note that values greater than 1.0 have no different effect than 1.0. - pub percentage: Option<f32>, - /// The amount of files to consider for fuzzy rename or copy tracking. Defaults to 1000, meaning that only 1000*1000 - /// combinations can be tested for fuzzy matches, i.e. the ones that try to find matches by comparing similarity. - /// If 0, there is no limit. - /// - /// If the limit would not be enough to test the entire set of combinations, the algorithm will trade in precision and not - /// run the fuzzy version of identity tests at all. That way results are never partial. - pub limit: usize, -} - -/// -pub mod rewrites; - -/// types to actually perform rename tracking. -pub(crate) mod tracked; - /// Configuration impl<'a, 'repo> Platform<'a, 'repo> { /// Keep track of file-names, which makes the [`location`][Change::location] field usable with the filename of the changed item. diff --git a/vendor/gix/src/object/tree/diff/rewrites.rs b/vendor/gix/src/object/tree/diff/rewrites.rs deleted file mode 100644 index e434726d9..000000000 --- a/vendor/gix/src/object/tree/diff/rewrites.rs +++ /dev/null @@ -1,108 +0,0 @@ -use crate::{ - config::{cache::util::ApplyLeniency, tree::Diff}, - diff::rename::Tracking, - object::tree::diff::Rewrites, -}; - -/// From where to source copies -#[derive(Debug, Copy, Clone, Eq, PartialEq)] -pub enum CopySource { - /// Find copies from the set of modified files only. - FromSetOfModifiedFiles, - /// Find copies from the set of changed files, as well as all files known to the source (i.e. previous state) of the tree. - /// - /// This can be an expensive operation as it scales exponentially with the total amount of files in the tree. - FromSetOfModifiedFilesAndSourceTree, -} - -/// How to determine copied files. -#[derive(Debug, Copy, Clone, PartialEq)] -pub struct Copies { - /// The set of files to search when finding the source of copies. - pub source: CopySource, - /// Equivalent to [`Rewrites::percentage`], but used for copy tracking. - /// - /// Useful to have similarity-based rename tracking and cheaper copy tracking, which also is the default - /// as only identity plays a role. - pub percentage: Option<f32>, -} - -impl Default for Copies { - fn default() -> Self { - Copies { - source: CopySource::FromSetOfModifiedFiles, - percentage: Some(0.5), - } - } -} - -/// Information collected while handling rewrites of files which may be tracked. -#[derive(Default, Clone, Copy, Debug, PartialEq)] -pub struct Outcome { - /// The options used to guide the rewrite tracking. Either fully provided by the caller or retrieved from git configuration. - pub options: Rewrites, - /// The amount of similarity checks that have been conducted to find renamed files and potentially copies. - pub num_similarity_checks: usize, - /// Set to the amount of worst-case rename permutations we didn't search as our limit didn't allow it. - pub num_similarity_checks_skipped_for_rename_tracking_due_to_limit: usize, - /// Set to the amount of worst-case copy permutations we didn't search as our limit didn't allow it. - pub num_similarity_checks_skipped_for_copy_tracking_due_to_limit: usize, -} - -/// The error returned by [`Rewrites::try_from_config()`]. -#[derive(Debug, thiserror::Error)] -#[allow(missing_docs)] -pub enum Error { - #[error(transparent)] - ConfigDiffRenames(#[from] crate::config::key::GenericError), - #[error(transparent)] - ConfigDiffRenameLimit(#[from] crate::config::unsigned_integer::Error), -} - -/// The default settings for rewrites according to the git configuration defaults. -impl Default for Rewrites { - fn default() -> Self { - Rewrites { - copies: None, - percentage: Some(0.5), - limit: 1000, - } - } -} - -impl Rewrites { - /// Create an instance by reading all relevant information from the `config`uration, while being `lenient` or not. - /// Returns `Ok(None)` if nothing is configured. - /// - /// Note that missing values will be defaulted similar to what git does. - #[allow(clippy::result_large_err)] - pub fn try_from_config(config: &gix_config::File<'static>, lenient: bool) -> Result<Option<Self>, Error> { - let key = "diff.renames"; - let copies = match config - .boolean_by_key(key) - .map(|value| Diff::RENAMES.try_into_renames(value)) - .transpose() - .with_leniency(lenient)? - { - Some(renames) => match renames { - Tracking::Disabled => return Ok(None), - Tracking::Renames => None, - Tracking::RenamesAndCopies => Some(Copies::default()), - }, - None => return Ok(None), - }; - - let default = Self::default(); - Ok(Rewrites { - copies, - limit: config - .integer_by_key("diff.renameLimit") - .map(|value| Diff::RENAME_LIMIT.try_into_usize(value)) - .transpose() - .with_leniency(lenient)? - .unwrap_or(default.limit), - ..default - } - .into()) - } -} diff --git a/vendor/gix/src/object/tree/diff/tracked.rs b/vendor/gix/src/object/tree/diff/tracked.rs deleted file mode 100644 index d6042fcbc..000000000 --- a/vendor/gix/src/object/tree/diff/tracked.rs +++ /dev/null @@ -1,490 +0,0 @@ -use std::ops::Range; - -use gix_diff::tree::visit::Change; -use gix_object::tree::EntryMode; - -use crate::{ - bstr::BStr, - ext::ObjectIdExt, - object::tree::diff::{ - change::DiffLineStats, - rewrites::{CopySource, Outcome}, - Rewrites, - }, - Repository, Tree, -}; - -/// A set of tracked items allows to figure out their relations by figuring out their similarity. -pub struct Item { - /// The underlying raw change - change: Change, - /// That slice into the backing for paths. - location: Range<usize>, - /// If true, this item was already emitted, i.e. seen by the caller. - emitted: bool, -} - -impl Item { - fn location<'a>(&self, backing: &'a [u8]) -> &'a BStr { - backing[self.location.clone()].as_ref() - } - fn entry_mode_compatible(&self, mode: EntryMode) -> bool { - use EntryMode::*; - matches!( - (mode, self.change.entry_mode()), - (Blob | BlobExecutable, Blob | BlobExecutable) | (Link, Link) - ) - } - - fn is_source_for_destination_of(&self, kind: visit::Kind, dest_item_mode: EntryMode) -> bool { - self.entry_mode_compatible(dest_item_mode) - && match kind { - visit::Kind::RenameTarget => !self.emitted && matches!(self.change, Change::Deletion { .. }), - visit::Kind::CopyDestination => { - matches!(self.change, Change::Modification { .. }) - } - } - } -} - -pub struct State { - items: Vec<Item>, - path_backing: Vec<u8>, - rewrites: Rewrites, - tracking: Option<gix_diff::tree::recorder::Location>, -} - -pub mod visit { - use crate::{bstr::BStr, object::tree::diff::change::DiffLineStats}; - - pub struct Source<'a> { - pub mode: gix_object::tree::EntryMode, - pub id: gix_hash::ObjectId, - pub kind: Kind, - pub location: &'a BStr, - pub diff: Option<DiffLineStats>, - } - - #[derive(Debug, Copy, Clone, Eq, PartialEq)] - pub enum Kind { - RenameTarget, - CopyDestination, - } - - pub struct Destination<'a> { - pub change: gix_diff::tree::visit::Change, - pub location: &'a BStr, - } -} - -impl State { - pub(crate) fn new(renames: Rewrites, tracking: Option<gix_diff::tree::recorder::Location>) -> Self { - State { - items: vec![], - path_backing: vec![], - rewrites: renames, - tracking, - } - } -} - -/// build state and find matches. -impl State { - /// 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: Change, location: &BStr) -> Option<Change> { - if !change.entry_mode().is_blob_or_symlink() { - return Some(change); - } - let keep = match (self.rewrites.copies, &change) { - (Some(_find_copies), _) => true, - (None, Change::Modification { .. }) => false, - (None, _) => true, - }; - - if !keep { - return Some(change); - } - - let start = self.path_backing.len(); - self.path_backing.extend_from_slice(location); - self.items.push(Item { - location: start..self.path_backing.len(), - change, - emitted: false, - }); - None - } - - /// Can only be called once effectively as it alters its own state. - /// - /// `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. - pub fn emit( - &mut self, - mut cb: impl FnMut(visit::Destination<'_>, Option<visit::Source<'_>>) -> gix_diff::tree::visit::Action, - src_tree: &Tree<'_>, - ) -> Result<Outcome, crate::object::tree::diff::for_each::Error> { - fn by_id_and_location(a: &Item, b: &Item) -> std::cmp::Ordering { - a.change.oid().cmp(b.change.oid()).then_with(|| { - a.location - .start - .cmp(&b.location.start) - .then(a.location.end.cmp(&b.location.end)) - }) - } - self.items.sort_by(by_id_and_location); - - let mut out = Outcome { - options: self.rewrites, - ..Default::default() - }; - out = self.match_pairs_of_kind( - visit::Kind::RenameTarget, - &mut cb, - self.rewrites.percentage, - out, - src_tree.repo, - )?; - - if let Some(copies) = self.rewrites.copies { - out = self.match_pairs_of_kind( - visit::Kind::CopyDestination, - &mut cb, - copies.percentage, - out, - src_tree.repo, - )?; - - match copies.source { - CopySource::FromSetOfModifiedFiles => {} - CopySource::FromSetOfModifiedFilesAndSourceTree => { - src_tree - .traverse() - .breadthfirst(&mut tree_to_events::Delegate::new(self))?; - self.items.sort_by(by_id_and_location); - - out = self.match_pairs_of_kind( - visit::Kind::CopyDestination, - &mut cb, - copies.percentage, - out, - src_tree.repo, - )?; - } - } - } - - 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, - ) == gix_diff::tree::visit::Action::Cancel - { - break; - } - } - Ok(out) - } - - fn match_pairs_of_kind( - &mut self, - kind: visit::Kind, - cb: &mut impl FnMut(visit::Destination<'_>, Option<visit::Source<'_>>) -> gix_diff::tree::visit::Action, - percentage: Option<f32>, - mut out: Outcome, - repo: &Repository, - ) -> Result<Outcome, crate::object::tree::diff::for_each::Error> { - // we try to cheaply reduce the set of possibilities first, before possibly looking more exhaustively. - let needs_second_pass = !needs_exact_match(percentage); - if self.match_pairs(cb, None /* by identity */, kind, repo, &mut out)? == gix_diff::tree::visit::Action::Cancel - { - return Ok(out); - } - if needs_second_pass { - let is_limited = if self.rewrites.limit == 0 { - false - } else if let Some(permutations) = permutations_over_limit(&self.items, self.rewrites.limit, kind) { - match kind { - visit::Kind::RenameTarget => { - out.num_similarity_checks_skipped_for_rename_tracking_due_to_limit = permutations; - } - visit::Kind::CopyDestination => { - out.num_similarity_checks_skipped_for_copy_tracking_due_to_limit = permutations; - } - } - true - } else { - false - }; - if !is_limited { - self.match_pairs(cb, self.rewrites.percentage, kind, repo, &mut out)?; - } - } - Ok(out) - } - - fn match_pairs( - &mut self, - cb: &mut impl FnMut(visit::Destination<'_>, Option<visit::Source<'_>>) -> gix_diff::tree::visit::Action, - percentage: Option<f32>, - kind: visit::Kind, - repo: &Repository, - stats: &mut Outcome, - ) -> Result<gix_diff::tree::visit::Action, crate::object::tree::diff::for_each::Error> { - // TODO(perf): reuse object data and interner state and interned tokens, make these available to `find_match()` - let mut dest_ofs = 0; - while let Some((mut dest_idx, dest)) = self.items[dest_ofs..].iter().enumerate().find_map(|(idx, item)| { - (!item.emitted && matches!(item.change, Change::Addition { .. })).then_some((idx, item)) - }) { - dest_idx += dest_ofs; - dest_ofs = dest_idx + 1; - let src = - find_match(&self.items, dest, dest_idx, percentage, kind, repo, stats)?.map(|(src_idx, src, diff)| { - let (id, mode) = src.change.oid_and_entry_mode(); - let id = id.to_owned(); - let location = src.location(&self.path_backing); - ( - visit::Source { - mode, - id, - kind, - location, - diff, - }, - src_idx, - ) - }); - if src.is_none() { - continue; - } - let location = dest.location(&self.path_backing); - let change = dest.change.clone(); - let dest = visit::Destination { change, location }; - self.items[dest_idx].emitted = true; - if let Some(src_idx) = src.as_ref().map(|t| t.1) { - self.items[src_idx].emitted = true; - } - if cb(dest, src.map(|t| t.0)) == gix_diff::tree::visit::Action::Cancel { - return Ok(gix_diff::tree::visit::Action::Cancel); - } - } - Ok(gix_diff::tree::visit::Action::Continue) - } -} - -fn permutations_over_limit(items: &[Item], limit: usize, kind: visit::Kind) -> Option<usize> { - let (sources, destinations) = items - .iter() - .filter(|item| match kind { - visit::Kind::RenameTarget => !item.emitted, - visit::Kind::CopyDestination => true, - }) - .fold((0, 0), |(mut src, mut dest), item| { - match item.change { - Change::Addition { .. } => { - dest += 1; - } - Change::Deletion { .. } => { - if kind == visit::Kind::RenameTarget { - src += 1 - } - } - Change::Modification { .. } => { - if kind == visit::Kind::CopyDestination { - src += 1 - } - } - } - (src, dest) - }); - let permutations = sources * destinations; - (permutations > limit * limit).then_some(permutations) -} - -fn needs_exact_match(percentage: Option<f32>) -> bool { - percentage.map_or(true, |p| p >= 1.0) -} - -/// <`src_idx`, src, possibly diff stat> -type SourceTuple<'a> = (usize, &'a Item, Option<DiffLineStats>); - -/// Find `item` in our set of items ignoring `item_idx` to avoid finding ourselves, by similarity indicated by `percentage`. -/// The latter can be `None` or `Some(x)` where `x>=1` for identity, and anything else for similarity. -/// We also ignore emitted items entirely. -/// Use `kind` to indicate what kind of match we are looking for, which might be deletions matching an `item` addition, or -/// any non-deletion otherwise. -/// Note that we always try to find by identity first even if a percentage is given as it's much faster and may reduce the set -/// of items to be searched. -fn find_match<'a>( - items: &'a [Item], - item: &Item, - item_idx: usize, - percentage: Option<f32>, - kind: visit::Kind, - repo: &Repository, - stats: &mut Outcome, -) -> Result<Option<SourceTuple<'a>>, crate::object::tree::diff::for_each::Error> { - let (item_id, item_mode) = item.change.oid_and_entry_mode(); - if needs_exact_match(percentage) || item_mode == gix_object::tree::EntryMode::Link { - let first_idx = items.partition_point(|a| a.change.oid() < item_id); - let range = match items.get(first_idx..).map(|items| { - let end = items - .iter() - .position(|a| a.change.oid() != item_id) - .map_or(items.len(), |idx| first_idx + idx); - first_idx..end - }) { - Some(range) => range, - None => return Ok(None), - }; - if range.is_empty() { - return Ok(None); - } - let res = items[range.clone()].iter().enumerate().find_map(|(mut src_idx, src)| { - src_idx += range.start; - (src_idx != item_idx && src.is_source_for_destination_of(kind, item_mode)).then_some((src_idx, src, None)) - }); - if let Some(src) = res { - return Ok(Some(src)); - } - } else { - let new = item_id.to_owned().attach(repo).object()?; - let percentage = percentage.expect("it's set to something below 1.0 and we assured this"); - debug_assert!( - item.change.entry_mode().is_blob(), - "symlinks are matched exactly, and trees aren't used here" - ); - let algo = repo.config.diff_algorithm()?; - for (can_idx, src) in items - .iter() - .enumerate() - .filter(|(src_idx, src)| *src_idx != item_idx && src.is_source_for_destination_of(kind, item_mode)) - { - let old = src.change.oid().to_owned().attach(repo).object()?; - // TODO: make sure we get attribute handling and binary skips and filters right here. There is crate::object::blob::diff::Platform - // which should have facilities for that one day, but we don't use it because we need newlines in our tokens. - let tokens = gix_diff::blob::intern::InternedInput::new( - gix_diff::blob::sources::byte_lines_with_terminator(&old.data), - gix_diff::blob::sources::byte_lines_with_terminator(&new.data), - ); - let counts = gix_diff::blob::diff( - algo, - &tokens, - gix_diff::blob::sink::Counter::new(diff::Statistics { - removed_bytes: 0, - input: &tokens, - }), - ); - let similarity = (old.data.len() - counts.wrapped) as f32 / old.data.len().max(new.data.len()) as f32; - stats.num_similarity_checks += 1; - if similarity >= percentage { - return Ok(Some(( - can_idx, - src, - DiffLineStats { - removals: counts.removals, - insertions: counts.insertions, - before: tokens.before.len().try_into().expect("interner handles only u32"), - after: tokens.after.len().try_into().expect("interner handles only u32"), - } - .into(), - ))); - } - } - } - Ok(None) -} - -mod diff { - use std::ops::Range; - - pub struct Statistics<'a, 'data> { - pub removed_bytes: usize, - pub input: &'a gix_diff::blob::intern::InternedInput<&'data [u8]>, - } - - impl<'a, 'data> gix_diff::blob::Sink for Statistics<'a, 'data> { - type Out = usize; - - fn process_change(&mut self, before: Range<u32>, _after: Range<u32>) { - self.removed_bytes = self.input.before[before.start as usize..before.end as usize] - .iter() - .map(|token| self.input.interner[*token].len()) - .sum(); - } - - fn finish(self) -> Self::Out { - self.removed_bytes - } - } -} - -mod tree_to_events { - use gix_diff::tree::visit::Change; - use gix_object::tree::EntryRef; - - use crate::bstr::BStr; - - pub struct Delegate<'a> { - parent: &'a mut super::State, - recorder: gix_traverse::tree::Recorder, - } - - impl<'a> Delegate<'a> { - pub fn new(parent: &'a mut super::State) -> Self { - let tracking = parent.tracking.map(|t| match t { - gix_diff::tree::recorder::Location::FileName => gix_traverse::tree::recorder::Location::FileName, - gix_diff::tree::recorder::Location::Path => gix_traverse::tree::recorder::Location::Path, - }); - Self { - parent, - recorder: gix_traverse::tree::Recorder::default().track_location(tracking), - } - } - } - - impl gix_traverse::tree::Visit for Delegate<'_> { - fn pop_front_tracked_path_and_set_current(&mut self) { - self.recorder.pop_front_tracked_path_and_set_current() - } - - fn push_back_tracked_path_component(&mut self, component: &BStr) { - self.recorder.push_back_tracked_path_component(component) - } - - fn push_path_component(&mut self, component: &BStr) { - self.recorder.push_path_component(component) - } - - fn pop_path_component(&mut self) { - self.recorder.pop_path_component(); - } - - fn visit_tree(&mut self, _entry: &EntryRef<'_>) -> gix_traverse::tree::visit::Action { - gix_traverse::tree::visit::Action::Continue - } - - fn visit_nontree(&mut self, entry: &EntryRef<'_>) -> gix_traverse::tree::visit::Action { - if entry.mode.is_blob() { - self.parent.try_push_change( - Change::Modification { - previous_entry_mode: entry.mode, - previous_oid: gix_hash::ObjectId::null(entry.oid.kind()), - entry_mode: entry.mode, - oid: entry.oid.to_owned(), - }, - self.recorder.path(), - ); - // make sure these aren't viable to be emitted anymore. - self.parent.items.last_mut().expect("just pushed").emitted = true; - } - gix_traverse::tree::visit::Action::Continue - } - } -} diff --git a/vendor/gix/src/object/tree/iter.rs b/vendor/gix/src/object/tree/iter.rs index 848d9eeab..cc9c4bd28 100644 --- a/vendor/gix/src/object/tree/iter.rs +++ b/vendor/gix/src/object/tree/iter.rs @@ -51,7 +51,7 @@ impl<'repo, 'a> std::fmt::Display for EntryRef<'repo, 'a> { write!( f, "{:06o} {:>6} {}\t{}", - self.mode() as u32, + *self.mode(), self.mode().as_str(), self.id().shorten_or_id(), self.filename() diff --git a/vendor/gix/src/object/tree/mod.rs b/vendor/gix/src/object/tree/mod.rs index e4dac24f8..a8173fce4 100644 --- a/vendor/gix/src/object/tree/mod.rs +++ b/vendor/gix/src/object/tree/mod.rs @@ -1,8 +1,7 @@ use gix_hash::ObjectId; use gix_macros::momo; -pub use gix_object::tree::EntryMode; -use gix_object::{bstr::BStr, TreeRefIter}; -use gix_odb::FindExt; +pub use gix_object::tree::{EntryKind, EntryMode}; +use gix_object::{bstr::BStr, FindExt, TreeRefIter}; use crate::{object::find, Id, ObjectDetached, Tree}; diff --git a/vendor/gix/src/object/tree/traverse.rs b/vendor/gix/src/object/tree/traverse.rs index 974df6b0d..f2f3ff817 100644 --- a/vendor/gix/src/object/tree/traverse.rs +++ b/vendor/gix/src/object/tree/traverse.rs @@ -1,5 +1,3 @@ -use gix_odb::FindExt; - use crate::Tree; /// Traversal @@ -52,11 +50,6 @@ impl<'a, 'repo> Platform<'a, 'repo> { { let root = gix_object::TreeRefIter::from_bytes(&self.root.data); let state = gix_traverse::tree::breadthfirst::State::default(); - gix_traverse::tree::breadthfirst( - root, - state, - |oid, buf| self.root.repo.objects.find_tree_iter(oid, buf).ok(), - delegate, - ) + gix_traverse::tree::breadthfirst(root, state, &self.root.repo.objects, delegate) } } |