summaryrefslogtreecommitdiffstats
path: root/vendor/gix/src/object/tree
diff options
context:
space:
mode:
Diffstat (limited to 'vendor/gix/src/object/tree')
-rw-r--r--vendor/gix/src/object/tree/diff/change.rs111
-rw-r--r--vendor/gix/src/object/tree/diff/for_each.rs235
-rw-r--r--vendor/gix/src/object/tree/diff/mod.rs118
-rw-r--r--vendor/gix/src/object/tree/diff/rewrites.rs108
-rw-r--r--vendor/gix/src/object/tree/diff/tracked.rs491
-rw-r--r--vendor/gix/src/object/tree/iter.rs53
-rw-r--r--vendor/gix/src/object/tree/mod.rs158
-rw-r--r--vendor/gix/src/object/tree/traverse.rs62
8 files changed, 1336 insertions, 0 deletions
diff --git a/vendor/gix/src/object/tree/diff/change.rs b/vendor/gix/src/object/tree/diff/change.rs
new file mode 100644
index 000000000..e6826d6ed
--- /dev/null
+++ b/vendor/gix/src/object/tree/diff/change.rs
@@ -0,0 +1,111 @@
+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,
+}
+
+/// An event emitted when finding differences between two trees.
+#[derive(Debug, Clone, Copy)]
+pub enum Event<'a, 'old, 'new> {
+ /// An entry was added, like the addition of a file or directory.
+ Addition {
+ /// The mode of the added entry.
+ entry_mode: gix_object::tree::EntryMode,
+ /// The object id of the added entry.
+ id: Id<'new>,
+ },
+ /// An entry was deleted, like the deletion of a file or directory.
+ Deletion {
+ /// The mode of the deleted entry.
+ entry_mode: gix_object::tree::EntryMode,
+ /// The object id of the deleted entry.
+ id: Id<'old>,
+ },
+ /// An entry was modified, e.g. changing the contents of a file adjusts its object id and turning
+ /// a file into a symbolic link adjusts its mode.
+ Modification {
+ /// The mode of the entry before the modification.
+ previous_entry_mode: gix_object::tree::EntryMode,
+ /// The object id of the entry before the modification.
+ previous_id: Id<'old>,
+
+ /// The mode of the entry after the modification.
+ entry_mode: gix_object::tree::EntryMode,
+ /// The object id after the modification.
+ id: Id<'new>,
+ },
+ /// Entries are considered rewritten if they are not trees and they, according to some understanding of identity, were renamed
+ /// or copied.
+ /// In case of renames, this means they originally appeared as [`Deletion`][Event::Deletion] signalling their source as well as an
+ /// [`Addition`][Event::Addition] acting as destination.
+ ///
+ /// In case of copies, the `copy` flag is true and typically represents a perfect copy of a source was made.
+ ///
+ /// This variant can only be encountered if [rewrite tracking][super::Platform::track_rewrites()] is enabled.
+ ///
+ /// Note that mode changes may have occurred as well, i.e. changes from executable to non-executable or vice-versa.
+ Rewrite {
+ /// The location of the source of the rename operation.
+ ///
+ /// It may be empty if neither [file names][super::Platform::track_filename()] nor [file paths][super::Platform::track_path()]
+ /// are tracked.
+ source_location: &'a BStr,
+ /// The mode of the entry before the rename.
+ source_entry_mode: gix_object::tree::EntryMode,
+ /// The object id of the entry before the rename.
+ ///
+ /// Note that this is the same as `id` if we require the [similarity to be 100%][super::Rewrites::percentage], but may
+ /// be different otherwise.
+ source_id: Id<'old>,
+ /// Information about the diff we performed to detect similarity and match the `source_id` with the current state at `id`.
+ /// It's `None` if `source_id` is equal to `id`, as identity made an actual diff computation unnecessary.
+ diff: Option<DiffLineStats>,
+ /// The mode of the entry after the rename.
+ /// It could differ but still be considered a rename as we are concerned only about content.
+ entry_mode: gix_object::tree::EntryMode,
+ /// The object id after the rename.
+ id: Id<'new>,
+ /// If true, this rewrite is created by copy, and `source_id` is pointing to its source. Otherwise it's a rename, and `source_id`
+ /// points to a deleted object, as renames are tracked as deletions and additions of the same or similar content.
+ copy: bool,
+ },
+}
+
+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(
+ &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,
+ }
+ }
+
+ /// Return the current mode of this instance.
+ pub fn entry_mode(&self) -> gix_object::tree::EntryMode {
+ match self {
+ Event::Addition { entry_mode, .. }
+ | Event::Deletion { entry_mode, .. }
+ | Event::Modification { entry_mode, .. }
+ | Event::Rewrite { entry_mode, .. } => *entry_mode,
+ }
+ }
+}
diff --git a/vendor/gix/src/object/tree/diff/for_each.rs b/vendor/gix/src/object/tree/diff/for_each.rs
new file mode 100644
index 000000000..5cae4cf2f
--- /dev/null
+++ b/vendor/gix/src/object/tree/diff/for_each.rs
@@ -0,0 +1,235 @@
+use gix_object::TreeRefIter;
+use gix_odb::FindExt;
+
+use super::{change, Action, Change, Platform};
+use crate::{
+ bstr::BStr,
+ ext::ObjectIdExt,
+ object::tree::{
+ diff,
+ diff::{rewrites, tracked},
+ },
+ Repository, Tree,
+};
+
+/// The error return by methods on the [diff platform][Platform].
+#[derive(Debug, thiserror::Error)]
+#[allow(missing_docs)]
+pub enum Error {
+ #[error(transparent)]
+ 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),
+}
+
+///
+#[derive(Clone, Debug, Copy, PartialEq)]
+pub struct Outcome {
+ /// Available only if [rewrite-tracking was enabled][Platform::track_rewrites()].
+ pub rewrites: Option<rewrites::Outcome>,
+}
+
+/// Add the item to compare to.
+impl<'a, 'old> Platform<'a, 'old> {
+ /// Call `for_each` repeatedly with all changes that are needed to convert the source of the diff to the tree to `other`.
+ ///
+ /// `other` could also be created with the [`empty_tree()`][crate::Repository::empty_tree()] method to handle the first commit
+ /// in a repository - it doesn't have a parent, equivalent to compare 'nothing' to something.
+ pub fn for_each_to_obtain_tree<'new, E>(
+ &mut self,
+ other: &Tree<'new>,
+ for_each: impl FnMut(Change<'_, 'old, 'new>) -> Result<Action, E>,
+ ) -> 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)),
+ 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),
+ &mut delegate,
+ ) {
+ Ok(()) => {
+ let outcome = Outcome {
+ rewrites: delegate.process_tracked_changes()?,
+ };
+ match delegate.err {
+ Some(err) => Err(Error::ForEach(Box::new(err))),
+ None => Ok(outcome),
+ }
+ }
+ Err(gix_diff::tree::changes::Error::Cancelled) => delegate
+ .err
+ .map(|err| Err(Error::ForEach(Box::new(err))))
+ .unwrap_or(Err(Error::Diff(gix_diff::tree::changes::Error::Cancelled))),
+ Err(err) => Err(err.into()),
+ }
+ }
+}
+
+struct Delegate<'a, 'old, 'new, VisitFn, E> {
+ src_tree: &'a Tree<'old>,
+ other_repo: &'new Repository,
+ recorder: gix_diff::tree::Recorder,
+ visit: VisitFn,
+ tracked: Option<tracked::State>,
+ err: Option<E>,
+}
+
+impl<'a, 'old, 'new, VisitFn, E> Delegate<'a, 'old, 'new, VisitFn, E>
+where
+ VisitFn: for<'delegate> FnMut(Change<'delegate, 'old, 'new>) -> Result<Action, E>,
+ E: std::error::Error + Sync + Send + 'static,
+{
+ /// Call `visit` on an attached version of `change`.
+ fn emit_change(
+ change: gix_diff::tree::visit::Change,
+ location: &BStr,
+ visit: &mut VisitFn,
+ repo: &'old Repository,
+ other_repo: &'new Repository,
+ stored_err: &mut Option<E>,
+ ) -> gix_diff::tree::visit::Action {
+ use gix_diff::tree::visit::Change::*;
+ let event = match change {
+ Addition { entry_mode, oid } => change::Event::Addition {
+ entry_mode,
+ id: oid.attach(other_repo),
+ },
+ Deletion { entry_mode, oid } => change::Event::Deletion {
+ entry_mode,
+ id: oid.attach(repo),
+ },
+ Modification {
+ previous_entry_mode,
+ previous_oid,
+ entry_mode,
+ oid,
+ } => change::Event::Modification {
+ previous_entry_mode,
+ entry_mode,
+ previous_id: previous_oid.attach(repo),
+ id: oid.attach(other_repo),
+ },
+ };
+ match visit(Change { event, location }) {
+ Ok(Action::Cancel) => gix_diff::tree::visit::Action::Cancel,
+ Ok(Action::Continue) => gix_diff::tree::visit::Action::Continue,
+ Err(err) => {
+ *stored_err = Some(err);
+ gix_diff::tree::visit::Action::Cancel
+ }
+ }
+ }
+
+ fn process_tracked_changes(&mut self) -> Result<Option<rewrites::Outcome>, Error> {
+ let tracked = match self.tracked.as_mut() {
+ Some(t) => t,
+ None => return Ok(None),
+ };
+
+ let outcome = tracked.emit(
+ |dest, source| match source {
+ Some(source) => {
+ let (oid, mode) = dest.change.oid_and_entry_mode();
+ let change = diff::Change {
+ location: dest.location,
+ event: diff::change::Event::Rewrite {
+ source_location: source.location,
+ source_entry_mode: source.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,
+ },
+ },
+ };
+ match (self.visit)(change) {
+ Ok(Action::Cancel) => gix_diff::tree::visit::Action::Cancel,
+ Ok(Action::Continue) => gix_diff::tree::visit::Action::Continue,
+ Err(err) => {
+ self.err = Some(err);
+ gix_diff::tree::visit::Action::Cancel
+ }
+ }
+ }
+ None => Self::emit_change(
+ dest.change,
+ dest.location,
+ &mut self.visit,
+ self.src_tree.repo,
+ self.other_repo,
+ &mut self.err,
+ ),
+ },
+ self.src_tree,
+ )?;
+ Ok(Some(outcome))
+ }
+}
+
+impl<'a, 'old, 'new, VisitFn, E> gix_diff::tree::Visit for Delegate<'a, 'old, 'new, VisitFn, E>
+where
+ VisitFn: for<'delegate> FnMut(Change<'delegate, 'old, 'new>) -> Result<Action, E>,
+ E: std::error::Error + Sync + Send + 'static,
+{
+ 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(&mut self, change: gix_diff::tree::visit::Change) -> gix_diff::tree::visit::Action {
+ match self.tracked.as_mut() {
+ Some(tracked) => tracked
+ .try_push_change(change, self.recorder.path())
+ .map(|change| {
+ Self::emit_change(
+ change,
+ self.recorder.path(),
+ &mut self.visit,
+ self.src_tree.repo,
+ self.other_repo,
+ &mut self.err,
+ )
+ })
+ .unwrap_or(gix_diff::tree::visit::Action::Continue),
+ None => Self::emit_change(
+ change,
+ self.recorder.path(),
+ &mut self.visit,
+ self.src_tree.repo,
+ self.other_repo,
+ &mut self.err,
+ ),
+ }
+ }
+}
diff --git a/vendor/gix/src/object/tree/diff/mod.rs b/vendor/gix/src/object/tree/diff/mod.rs
new file mode 100644
index 000000000..5a3bf6ddf
--- /dev/null
+++ b/vendor/gix/src/object/tree/diff/mod.rs
@@ -0,0 +1,118 @@
+use gix_diff::tree::recorder::Location;
+
+use crate::{bstr::BStr, Tree};
+
+/// Returned by the `for_each` function to control flow.
+#[derive(Clone, Copy, PartialOrd, PartialEq, Ord, Eq, Hash)]
+pub enum Action {
+ /// Continue the traversal of changes.
+ Continue,
+ /// Stop the traversal of changes and stop calling this function.
+ Cancel,
+}
+
+impl Default for Action {
+ fn default() -> Self {
+ Action::Continue
+ }
+}
+
+/// Represents any possible change in order to turn one tree into another.
+#[derive(Debug, Clone, Copy)]
+pub struct Change<'a, 'old, 'new> {
+ /// The location of the file or directory described by `event`, if tracking was enabled.
+ ///
+ /// Otherwise this value is always an empty path.
+ pub location: &'a BStr,
+ /// The diff event itself to provide information about what would need to change.
+ pub event: change::Event<'a, 'old, 'new>,
+}
+
+///
+pub mod change;
+
+/// Diffing
+impl<'repo> Tree<'repo> {
+ /// Return a platform to see the changes needed to create other trees, for instance.
+ ///
+ /// # Performance
+ ///
+ /// It's highly recommended to set an object cache to avoid extracting the same object multiple times.
+ /// By default, similar to `git diff`, rename tracking will be enabled if it is not configured.
+ #[allow(clippy::result_large_err)]
+ pub fn changes<'a>(&'a self) -> Result<Platform<'a, 'repo>, rewrites::Error> {
+ Ok(Platform {
+ state: Default::default(),
+ lhs: self,
+ tracking: None,
+ rewrites: self.repo.config.diff_renames()?.unwrap_or_default().into(),
+ })
+ }
+}
+
+/// The diffing platform returned by [`Tree::changes()`].
+#[derive(Clone)]
+pub struct Platform<'a, 'repo> {
+ state: gix_diff::tree::State,
+ lhs: &'a Tree<'repo>,
+ tracking: Option<Location>,
+ 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.
+ pub fn track_filename(&mut self) -> &mut Self {
+ self.tracking = Some(Location::FileName);
+ self
+ }
+
+ /// Keep track of the entire path of a change, relative to the repository.
+ ///
+ /// This makes the [`location`][Change::location] field usable.
+ pub fn track_path(&mut self) -> &mut Self {
+ self.tracking = Some(Location::Path);
+ self
+ }
+
+ /// Provide `None` to disable rewrite tracking entirely, or pass `Some(<configuration>)` to control to
+ /// what extend rename and copy tracking is performed.
+ ///
+ /// Note that by default, the git configuration determines rewrite tracking and git defaults are used
+ /// if nothing is configured, which turns rename tracking with 50% similarity on, while not tracking copies at all.
+ pub fn track_rewrites(&mut self, renames: Option<Rewrites>) -> &mut Self {
+ self.rewrites = renames;
+ self
+ }
+}
+
+///
+pub mod for_each;
diff --git a/vendor/gix/src/object/tree/diff/rewrites.rs b/vendor/gix/src/object/tree/diff/rewrites.rs
new file mode 100644
index 000000000..304894d15
--- /dev/null
+++ b/vendor/gix/src/object/tree/diff/rewrites.rs
@@ -0,0 +1,108 @@
+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, || config.string_by_key(key)))
+ .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
new file mode 100644
index 000000000..3bbe01624
--- /dev/null
+++ b/vendor/gix/src/object/tree/diff/tracked.rs
@@ -0,0 +1,491 @@
+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(|idx| first_idx + idx)
+ .unwrap_or(items.len());
+ 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
new file mode 100644
index 000000000..c841e2574
--- /dev/null
+++ b/vendor/gix/src/object/tree/iter.rs
@@ -0,0 +1,53 @@
+use super::Tree;
+use crate::Repository;
+
+/// An entry within a tree
+pub struct EntryRef<'repo, 'a> {
+ /// The actual entry ref we are wrapping.
+ pub inner: gix_object::tree::EntryRef<'a>,
+
+ pub(crate) repo: &'repo Repository,
+}
+
+impl<'repo, 'a> EntryRef<'repo, 'a> {
+ /// The kind of object to which [`id()`][Self::id()] is pointing.
+ pub fn mode(&self) -> gix_object::tree::EntryMode {
+ self.inner.mode
+ }
+
+ /// The name of the file in the parent tree.
+ pub fn filename(&self) -> &gix_object::bstr::BStr {
+ self.inner.filename
+ }
+
+ /// Return the entries id, connected to the underlying repository.
+ pub fn id(&self) -> crate::Id<'repo> {
+ crate::Id::from_id(self.inner.oid, self.repo)
+ }
+
+ /// Return the entries id, without repository connection.
+ pub fn oid(&self) -> gix_hash::ObjectId {
+ self.inner.oid.to_owned()
+ }
+}
+
+impl<'repo, 'a> std::fmt::Display for EntryRef<'repo, 'a> {
+ fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+ write!(
+ f,
+ "{:06o} {:>6} {}\t{}",
+ self.mode() as u32,
+ self.mode().as_str(),
+ self.id().shorten_or_id(),
+ self.filename()
+ )
+ }
+}
+
+impl<'repo> Tree<'repo> {
+ /// Return an iterator over tree entries to obtain information about files and directories this tree contains.
+ pub fn iter(&self) -> impl Iterator<Item = Result<EntryRef<'repo, '_>, gix_object::decode::Error>> {
+ let repo = self.repo;
+ gix_object::TreeRefIter::from_bytes(&self.data).map(move |e| e.map(|entry| EntryRef { inner: entry, repo }))
+ }
+}
diff --git a/vendor/gix/src/object/tree/mod.rs b/vendor/gix/src/object/tree/mod.rs
new file mode 100644
index 000000000..db094bcb9
--- /dev/null
+++ b/vendor/gix/src/object/tree/mod.rs
@@ -0,0 +1,158 @@
+use gix_hash::ObjectId;
+use gix_object::{bstr::BStr, TreeRefIter};
+
+use crate::{object::find, Id, Tree};
+
+/// Initialization
+impl<'repo> Tree<'repo> {
+ /// Obtain a tree instance by handing in all components that it is made up of.
+ pub fn from_data(id: impl Into<ObjectId>, data: Vec<u8>, repo: &'repo crate::Repository) -> Self {
+ Tree {
+ id: id.into(),
+ data,
+ repo,
+ }
+ }
+}
+
+/// Access
+impl<'repo> Tree<'repo> {
+ /// Return this tree's identifier.
+ pub fn id(&self) -> Id<'repo> {
+ Id::from_id(self.id, self.repo)
+ }
+
+ // TODO: tests.
+ /// Follow a sequence of `path` components starting from this instance, and look them up one by one until the last component
+ /// is looked up and its tree entry is returned.
+ ///
+ /// # Performance Notes
+ ///
+ /// Searching tree entries is currently done in sequence, which allows to the search to be allocation free. It would be possible
+ /// to re-use a vector and use a binary search instead, which might be able to improve performance over all.
+ /// However, a benchmark should be created first to have some data and see which trade-off to choose here.
+ ///
+ /// # Why is this consuming?
+ ///
+ /// The borrow checker shows pathological behaviour in loops that mutate a buffer, but also want to return from it.
+ /// Workarounds include keeping an index and doing a separate access to the memory, which seems hard to do here without
+ /// re-parsing the entries.
+ pub fn lookup_entry<I, P>(mut self, path: I) -> Result<Option<Entry<'repo>>, find::existing::Error>
+ where
+ I: IntoIterator<Item = P>,
+ P: PartialEq<BStr>,
+ {
+ let mut path = path.into_iter().peekable();
+ while let Some(component) = path.next() {
+ match TreeRefIter::from_bytes(&self.data)
+ .filter_map(Result::ok)
+ .find(|entry| component.eq(entry.filename))
+ {
+ Some(entry) => {
+ if path.peek().is_none() {
+ return Ok(Some(Entry {
+ inner: entry.into(),
+ repo: self.repo,
+ }));
+ } else {
+ let next_id = entry.oid.to_owned();
+ let repo = self.repo;
+ drop(self);
+ self = match repo.find_object(next_id)?.try_into_tree() {
+ Ok(tree) => tree,
+ Err(_) => return Ok(None),
+ };
+ }
+ }
+ None => return Ok(None),
+ }
+ }
+ Ok(None)
+ }
+
+ /// Like [`lookup_entry()`][Self::lookup_entry()], but takes a `Path` directly via `relative_path`, a path relative to this tree.
+ ///
+ /// # Note
+ ///
+ /// If any path component contains illformed UTF-8 and thus can't be converted to bytes on platforms which can't do so natively,
+ /// the returned component will be empty which makes the lookup fail.
+ pub fn lookup_entry_by_path(
+ self,
+ relative_path: impl AsRef<std::path::Path>,
+ ) -> Result<Option<Entry<'repo>>, find::existing::Error> {
+ use crate::bstr::ByteSlice;
+ self.lookup_entry(relative_path.as_ref().components().map(|c: std::path::Component<'_>| {
+ gix_path::os_str_into_bstr(c.as_os_str())
+ .unwrap_or_else(|_| "".into())
+ .as_bytes()
+ }))
+ }
+}
+
+///
+pub mod diff;
+
+///
+pub mod traverse;
+
+///
+mod iter;
+pub use iter::EntryRef;
+
+impl<'r> std::fmt::Debug for Tree<'r> {
+ fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+ write!(f, "Tree({})", self.id)
+ }
+}
+
+/// An entry in a [`Tree`], similar to an entry in a directory.
+#[derive(PartialEq, Debug, Clone)]
+pub struct Entry<'repo> {
+ inner: gix_object::tree::Entry,
+ repo: &'repo crate::Repository,
+}
+
+mod entry {
+ use crate::{bstr::BStr, ext::ObjectIdExt, object::tree::Entry};
+
+ /// Access
+ impl<'repo> Entry<'repo> {
+ /// The kind of object to which `oid` is pointing to.
+ pub fn mode(&self) -> gix_object::tree::EntryMode {
+ self.inner.mode
+ }
+
+ /// The name of the file in the parent tree.
+ pub fn filename(&self) -> &BStr {
+ self.inner.filename.as_ref()
+ }
+
+ /// Return the object id of the entry.
+ pub fn id(&self) -> crate::Id<'repo> {
+ self.inner.oid.attach(self.repo)
+ }
+
+ /// Return the object this entry points to.
+ pub fn object(&self) -> Result<crate::Object<'repo>, crate::object::find::existing::Error> {
+ self.id().object()
+ }
+
+ /// Return the plain object id of this entry, without access to the repository.
+ pub fn oid(&self) -> &gix_hash::oid {
+ &self.inner.oid
+ }
+
+ /// Return the plain object id of this entry, without access to the repository.
+ pub fn object_id(&self) -> gix_hash::ObjectId {
+ self.inner.oid
+ }
+ }
+
+ /// Consuming
+ impl Entry<'_> {
+ /// Return the contained object.
+ pub fn detach(self) -> gix_object::tree::Entry {
+ self.inner
+ }
+ }
+}
diff --git a/vendor/gix/src/object/tree/traverse.rs b/vendor/gix/src/object/tree/traverse.rs
new file mode 100644
index 000000000..974df6b0d
--- /dev/null
+++ b/vendor/gix/src/object/tree/traverse.rs
@@ -0,0 +1,62 @@
+use gix_odb::FindExt;
+
+use crate::Tree;
+
+/// Traversal
+impl<'repo> Tree<'repo> {
+ /// Obtain a platform for initiating a variety of traversals.
+ pub fn traverse(&self) -> Platform<'_, 'repo> {
+ Platform {
+ root: self,
+ breadthfirst: BreadthFirstPresets { root: self },
+ }
+ }
+}
+
+/// An intermediate object to start traversing the parent tree from.
+pub struct Platform<'a, 'repo> {
+ root: &'a Tree<'repo>,
+ /// Provides easy access to presets for common breadth-first traversal.
+ pub breadthfirst: BreadthFirstPresets<'a, 'repo>,
+}
+
+/// Presets for common choices in breadth-first traversal.
+#[derive(Copy, Clone)]
+pub struct BreadthFirstPresets<'a, 'repo> {
+ root: &'a Tree<'repo>,
+}
+
+impl<'a, 'repo> BreadthFirstPresets<'a, 'repo> {
+ /// Returns all entries and their file paths, recursively, as reachable from this tree.
+ pub fn files(&self) -> Result<Vec<gix_traverse::tree::recorder::Entry>, gix_traverse::tree::breadthfirst::Error> {
+ let mut recorder = gix_traverse::tree::Recorder::default();
+ Platform {
+ root: self.root,
+ breadthfirst: *self,
+ }
+ .breadthfirst(&mut recorder)?;
+ Ok(recorder.records)
+ }
+}
+
+impl<'a, 'repo> Platform<'a, 'repo> {
+ /// Start a breadth-first, recursive traversal using `delegate`, for which a [`Recorder`][gix_traverse::tree::Recorder] can be used to get started.
+ ///
+ /// # Note
+ ///
+ /// - Results are returned in sort order according to tree-entry sorting rules, one level at a time.
+ /// - for obtaining the direct children of the tree, use [.iter()][crate::Tree::iter()] instead.
+ pub fn breadthfirst<V>(&self, delegate: &mut V) -> Result<(), gix_traverse::tree::breadthfirst::Error>
+ where
+ V: gix_traverse::tree::Visit,
+ {
+ 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,
+ )
+ }
+}