Merging upstream version 1.70.0+dfsg2.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

6 files changed, 732 insertions, 0 deletions

diff --git a/vendor/gix-diff/src/blob.rs b/vendor/gix-diff/src/blob.rs
new file mode 100644
index 000000000..27c1a1317
--- /dev/null
+++ b/vendor/gix-diff/src/blob.rs
@@ -0,0 +1,3 @@
+//! For using text diffs, please have a look at the [`imara-diff` documentation](https://docs.rs/imara-diff),
+//! maintained by [Pascal Kuthe](https://github.com/pascalkuthe).
+pub use imara_diff::*;
diff --git a/vendor/gix-diff/src/lib.rs b/vendor/gix-diff/src/lib.rs
new file mode 100644
index 000000000..a60f7bc04
--- /dev/null
+++ b/vendor/gix-diff/src/lib.rs
@@ -0,0 +1,9 @@
+//! Algorithms for diffing various git object types and for generating patches, highly optimized for performance.
+#![deny(missing_docs, rust_2018_idioms)]
+#![forbid(unsafe_code)]
+
+///
+pub mod tree;
+
+///
+pub mod blob;
diff --git a/vendor/gix-diff/src/tree/changes.rs b/vendor/gix-diff/src/tree/changes.rs
new file mode 100644
index 000000000..f0b3e82ab
--- /dev/null
+++ b/vendor/gix-diff/src/tree/changes.rs
@@ -0,0 +1,396 @@
+use std::{borrow::BorrowMut, collections::VecDeque};
+
+use gix_hash::{oid, ObjectId};
+use gix_object::tree::EntryRef;
+
+use crate::{
+    tree,
+    tree::{visit::Change, TreeInfoPair},
+};
+
+/// The error returned by [tree::Changes::needed_to_obtain()].
+#[derive(Debug, thiserror::Error)]
+#[allow(missing_docs)]
+pub enum Error {
+    #[error("The object {oid} referenced by the tree or the tree itself was not found in the database")]
+    FindExisting {
+        oid: ObjectId,
+        source: Box<dyn std::error::Error + Send + Sync + 'static>,
+    },
+    #[error("The delegate cancelled the operation")]
+    Cancelled,
+    #[error(transparent)]
+    EntriesDecode(#[from] gix_object::decode::Error),
+}
+
+impl<'a> tree::Changes<'a> {
+    /// Calculate the changes that would need to be applied to `self` to get `other`.
+    ///
+    /// * The `state` maybe owned or mutably borrowed to allow reuses allocated data structures through multiple runs.
+    /// * `locate` is a function `f(object_id, &mut buffer) -> Option<TreeIter>` to return a `TreeIter` for the given object id backing
+    ///   its data in the given buffer. Returning `None` is unexpected as these trees are obtained during iteration, and in a typical
+    ///   database errors are not expected either which is why the error case is omitted. To allow proper error reporting, [`Error::FindExisting`]
+    ///   should be converted into a more telling error.
+    /// * `delegate` will receive the computed changes, see the [`Visit`][`tree::Visit`] trait for more information on what to expect.
+    ///
+    /// # Notes
+    ///
+    /// * To obtain progress, implement it within the `delegate`.
+    /// * Tree entries are expected to be ordered using [`tree-entry-comparison`][git_cmp_c] (the same [in Rust][git_cmp_rs])
+    /// * it does a breadth first iteration as buffer space only fits two trees, the current one on the one we compare with.
+    /// * does not do rename tracking but attempts to reduce allocations to zero (so performance is mostly determined
+    ///   by the delegate implementation which should be as specific as possible. Rename tracking can be computed on top of the changes
+    ///   received by the `delegate`.
+    /// * cycle checking is not performed, but can be performed in the delegate which can return [`tree::visit::Action::Cancel`] to stop the traversal.
+    /// * [std::mem::ManuallyDrop] is used because `Peekable` is needed. When using it as wrapper around our no-drop iterators, all of the sudden
+    ///   borrowcheck complains as Drop is present (even though it's not)
+    ///
+    /// [git_cmp_c]: https://github.com/git/git/blob/311531c9de557d25ac087c1637818bd2aad6eb3a/tree-diff.c#L49:L65
+    /// [git_cmp_rs]: https://github.com/Byron/gitoxide/blob/a4d5f99c8dc99bf814790928a3bf9649cd99486b/gix-object/src/mutable/tree.rs#L52-L55
+    pub fn needed_to_obtain<FindFn, R, StateMut, E>(
+        mut self,
+        other: gix_object::TreeRefIter<'_>,
+        mut state: StateMut,
+        mut find: FindFn,
+        delegate: &mut R,
+    ) -> Result<(), Error>
+    where
+        FindFn: for<'b> FnMut(&oid, &'b mut Vec<u8>) -> Result<gix_object::TreeRefIter<'b>, E>,
+        E: std::error::Error + Send + Sync + 'static,
+        R: tree::Visit,
+        StateMut: BorrowMut<tree::State>,
+    {
+        let state = state.borrow_mut();
+        state.clear();
+        let mut lhs_entries = peekable(self.0.take().unwrap_or_default());
+        let mut rhs_entries = peekable(other);
+        let mut pop_path = false;
+
+        loop {
+            if pop_path {
+                delegate.pop_path_component();
+            }
+            pop_path = true;
+
+            match (lhs_entries.next(), rhs_entries.next()) {
+                (None, None) => {
+                    match state.trees.pop_front() {
+                        Some((None, Some(rhs))) => {
+                            delegate.pop_front_tracked_path_and_set_current();
+                            rhs_entries = peekable(find(&rhs, &mut state.buf2).map_err(|err| Error::FindExisting {
+                                oid: rhs,
+                                source: err.into(),
+                            })?);
+                        }
+                        Some((Some(lhs), Some(rhs))) => {
+                            delegate.pop_front_tracked_path_and_set_current();
+                            lhs_entries = peekable(find(&lhs, &mut state.buf1).map_err(|err| Error::FindExisting {
+                                oid: lhs,
+                                source: err.into(),
+                            })?);
+                            rhs_entries = peekable(find(&rhs, &mut state.buf2).map_err(|err| Error::FindExisting {
+                                oid: rhs,
+                                source: err.into(),
+                            })?);
+                        }
+                        Some((Some(lhs), None)) => {
+                            delegate.pop_front_tracked_path_and_set_current();
+                            lhs_entries = peekable(find(&lhs, &mut state.buf1).map_err(|err| Error::FindExisting {
+                                oid: lhs,
+                                source: err.into(),
+                            })?);
+                        }
+                        Some((None, None)) => unreachable!("BUG: it makes no sense to fill the stack with empties"),
+                        None => return Ok(()),
+                    };
+                    pop_path = false;
+                }
+                (Some(lhs), Some(rhs)) => {
+                    use std::cmp::Ordering::*;
+                    let (lhs, rhs) = (lhs?, rhs?);
+                    match compare(&lhs, &rhs) {
+                        Equal => handle_lhs_and_rhs_with_equal_filenames(lhs, rhs, &mut state.trees, delegate)?,
+                        Less => catchup_lhs_with_rhs(&mut lhs_entries, lhs, rhs, &mut state.trees, delegate)?,
+                        Greater => catchup_rhs_with_lhs(&mut rhs_entries, lhs, rhs, &mut state.trees, delegate)?,
+                    }
+                }
+                (Some(lhs), None) => {
+                    let lhs = lhs?;
+                    delete_entry_schedule_recursion(lhs, &mut state.trees, delegate)?;
+                }
+                (None, Some(rhs)) => {
+                    let rhs = rhs?;
+                    add_entry_schedule_recursion(rhs, &mut state.trees, delegate)?;
+                }
+            }
+        }
+    }
+}
+
+fn compare(a: &EntryRef<'_>, b: &EntryRef<'_>) -> std::cmp::Ordering {
+    let common = a.filename.len().min(b.filename.len());
+    a.filename[..common].cmp(&b.filename[..common]).then_with(|| {
+        let a = a.filename.get(common).or_else(|| a.mode.is_tree().then_some(&b'/'));
+        let b = b.filename.get(common).or_else(|| b.mode.is_tree().then_some(&b'/'));
+        a.cmp(&b)
+    })
+}
+
+fn delete_entry_schedule_recursion<R: tree::Visit>(
+    entry: EntryRef<'_>,
+    queue: &mut VecDeque<TreeInfoPair>,
+    delegate: &mut R,
+) -> Result<(), Error> {
+    delegate.push_path_component(entry.filename);
+    if delegate
+        .visit(Change::Deletion {
+            entry_mode: entry.mode,
+            oid: entry.oid.to_owned(),
+        })
+        .cancelled()
+    {
+        return Err(Error::Cancelled);
+    }
+    if entry.mode.is_tree() {
+        delegate.pop_path_component();
+        delegate.push_back_tracked_path_component(entry.filename);
+        queue.push_back((Some(entry.oid.to_owned()), None));
+    }
+    Ok(())
+}
+
+fn add_entry_schedule_recursion<R: tree::Visit>(
+    entry: EntryRef<'_>,
+    queue: &mut VecDeque<TreeInfoPair>,
+    delegate: &mut R,
+) -> Result<(), Error> {
+    delegate.push_path_component(entry.filename);
+    if delegate
+        .visit(Change::Addition {
+            entry_mode: entry.mode,
+            oid: entry.oid.to_owned(),
+        })
+        .cancelled()
+    {
+        return Err(Error::Cancelled);
+    }
+    if entry.mode.is_tree() {
+        delegate.pop_path_component();
+        delegate.push_back_tracked_path_component(entry.filename);
+        queue.push_back((None, Some(entry.oid.to_owned())))
+    }
+    Ok(())
+}
+fn catchup_rhs_with_lhs<R: tree::Visit>(
+    rhs_entries: &mut IteratorType<gix_object::TreeRefIter<'_>>,
+    lhs: EntryRef<'_>,
+    rhs: EntryRef<'_>,
+    queue: &mut VecDeque<TreeInfoPair>,
+    delegate: &mut R,
+) -> Result<(), Error> {
+    use std::cmp::Ordering::*;
+    add_entry_schedule_recursion(rhs, queue, delegate)?;
+    loop {
+        match rhs_entries.peek() {
+            Some(Ok(rhs)) => match compare(&lhs, rhs) {
+                Equal => {
+                    let rhs = rhs_entries.next().transpose()?.expect("the peeked item to be present");
+                    delegate.pop_path_component();
+                    handle_lhs_and_rhs_with_equal_filenames(lhs, rhs, queue, delegate)?;
+                    break;
+                }
+                Greater => {
+                    let rhs = rhs_entries.next().transpose()?.expect("the peeked item to be present");
+                    delegate.pop_path_component();
+                    add_entry_schedule_recursion(rhs, queue, delegate)?;
+                }
+                Less => {
+                    delegate.pop_path_component();
+                    delete_entry_schedule_recursion(lhs, queue, delegate)?;
+                    break;
+                }
+            },
+            Some(Err(err)) => return Err(Error::EntriesDecode(err.to_owned())),
+            None => {
+                delegate.pop_path_component();
+                delete_entry_schedule_recursion(lhs, queue, delegate)?;
+                break;
+            }
+        }
+    }
+    Ok(())
+}
+
+fn catchup_lhs_with_rhs<R: tree::Visit>(
+    lhs_entries: &mut IteratorType<gix_object::TreeRefIter<'_>>,
+    lhs: EntryRef<'_>,
+    rhs: EntryRef<'_>,
+    queue: &mut VecDeque<TreeInfoPair>,
+    delegate: &mut R,
+) -> Result<(), Error> {
+    use std::cmp::Ordering::*;
+    delete_entry_schedule_recursion(lhs, queue, delegate)?;
+    loop {
+        match lhs_entries.peek() {
+            Some(Ok(lhs)) => match compare(lhs, &rhs) {
+                Equal => {
+                    let lhs = lhs_entries.next().expect("the peeked item to be present")?;
+                    delegate.pop_path_component();
+                    handle_lhs_and_rhs_with_equal_filenames(lhs, rhs, queue, delegate)?;
+                    break;
+                }
+                Less => {
+                    let lhs = lhs_entries.next().expect("the peeked item to be present")?;
+                    delegate.pop_path_component();
+                    delete_entry_schedule_recursion(lhs, queue, delegate)?;
+                }
+                Greater => {
+                    delegate.pop_path_component();
+                    add_entry_schedule_recursion(rhs, queue, delegate)?;
+                    break;
+                }
+            },
+            Some(Err(err)) => return Err(Error::EntriesDecode(err.to_owned())),
+            None => {
+                delegate.pop_path_component();
+                add_entry_schedule_recursion(rhs, queue, delegate)?;
+                break;
+            }
+        }
+    }
+    Ok(())
+}
+
+fn handle_lhs_and_rhs_with_equal_filenames<R: tree::Visit>(
+    lhs: EntryRef<'_>,
+    rhs: EntryRef<'_>,
+    queue: &mut VecDeque<TreeInfoPair>,
+    delegate: &mut R,
+) -> Result<(), Error> {
+    use gix_object::tree::EntryMode::*;
+    match (lhs.mode, rhs.mode) {
+        (Tree, Tree) => {
+            delegate.push_back_tracked_path_component(lhs.filename);
+            if lhs.oid != rhs.oid
+                && delegate
+                    .visit(Change::Modification {
+                        previous_entry_mode: lhs.mode,
+                        previous_oid: lhs.oid.to_owned(),
+                        entry_mode: rhs.mode,
+                        oid: rhs.oid.to_owned(),
+                    })
+                    .cancelled()
+            {
+                return Err(Error::Cancelled);
+            }
+            queue.push_back((Some(lhs.oid.to_owned()), Some(rhs.oid.to_owned())));
+        }
+        (_, Tree) => {
+            delegate.push_back_tracked_path_component(lhs.filename);
+            if delegate
+                .visit(Change::Deletion {
+                    entry_mode: lhs.mode,
+                    oid: lhs.oid.to_owned(),
+                })
+                .cancelled()
+            {
+                return Err(Error::Cancelled);
+            };
+            if delegate
+                .visit(Change::Addition {
+                    entry_mode: rhs.mode,
+                    oid: rhs.oid.to_owned(),
+                })
+                .cancelled()
+            {
+                return Err(Error::Cancelled);
+            };
+            queue.push_back((None, Some(rhs.oid.to_owned())));
+        }
+        (Tree, _) => {
+            delegate.push_back_tracked_path_component(lhs.filename);
+            if delegate
+                .visit(Change::Deletion {
+                    entry_mode: lhs.mode,
+                    oid: lhs.oid.to_owned(),
+                })
+                .cancelled()
+            {
+                return Err(Error::Cancelled);
+            }
+            if delegate
+                .visit(Change::Addition {
+                    entry_mode: rhs.mode,
+                    oid: rhs.oid.to_owned(),
+                })
+                .cancelled()
+            {
+                return Err(Error::Cancelled);
+            };
+            queue.push_back((Some(lhs.oid.to_owned()), None));
+        }
+        (lhs_non_tree, rhs_non_tree) => {
+            delegate.push_path_component(lhs.filename);
+            debug_assert!(lhs_non_tree.is_no_tree() && rhs_non_tree.is_no_tree());
+            if lhs.oid != rhs.oid
+                && delegate
+                    .visit(Change::Modification {
+                        previous_entry_mode: lhs.mode,
+                        previous_oid: lhs.oid.to_owned(),
+                        entry_mode: rhs.mode,
+                        oid: rhs.oid.to_owned(),
+                    })
+                    .cancelled()
+            {
+                return Err(Error::Cancelled);
+            }
+        }
+    };
+    Ok(())
+}
+
+type IteratorType<I> = std::mem::ManuallyDrop<std::iter::Peekable<I>>;
+
+fn peekable<I: Iterator>(iter: I) -> IteratorType<I> {
+    std::mem::ManuallyDrop::new(iter.peekable())
+}
+
+#[cfg(test)]
+mod tests {
+    use std::cmp::Ordering;
+
+    use gix_object::tree::EntryMode;
+
+    use super::*;
+
+    #[test]
+    fn compare_select_samples() {
+        let null = gix_hash::ObjectId::null(gix_hash::Kind::Sha1);
+        let actual = compare(
+            &EntryRef {
+                mode: EntryMode::Blob,
+                filename: "plumbing-cli.rs".into(),
+                oid: &null,
+            },
+            &EntryRef {
+                mode: EntryMode::Tree,
+                filename: "plumbing".into(),
+                oid: &null,
+            },
+        );
+        assert_eq!(actual, Ordering::Less);
+        let actual = compare(
+            &EntryRef {
+                mode: EntryMode::Tree,
+                filename: "plumbing-cli.rs".into(),
+                oid: &null,
+            },
+            &EntryRef {
+                mode: EntryMode::Blob,
+                filename: "plumbing".into(),
+                oid: &null,
+            },
+        );
+        assert_eq!(actual, Ordering::Greater);
+    }
+}
diff --git a/vendor/gix-diff/src/tree/mod.rs b/vendor/gix-diff/src/tree/mod.rs
new file mode 100644
index 000000000..fea4550f6
--- /dev/null
+++ b/vendor/gix-diff/src/tree/mod.rs
@@ -0,0 +1,55 @@
+use std::collections::VecDeque;
+
+use gix_hash::ObjectId;
+use gix_object::{bstr::BString, TreeRefIter};
+
+/// The state required to visit [Changes] to be instantiated with `State::default()`.
+#[derive(Default, Clone)]
+pub struct State {
+    buf1: Vec<u8>,
+    buf2: Vec<u8>,
+    trees: VecDeque<TreeInfoPair>,
+}
+
+type TreeInfoPair = (Option<ObjectId>, Option<ObjectId>);
+
+impl State {
+    fn clear(&mut self) {
+        self.trees.clear();
+        self.buf1.clear();
+        self.buf2.clear();
+    }
+}
+
+/// An iterator over changes of a tree, instantiated using `Changes::from(…)`.
+pub struct Changes<'a>(Option<TreeRefIter<'a>>);
+
+impl<'a, T> From<T> for Changes<'a>
+where
+    T: Into<Option<TreeRefIter<'a>>>,
+{
+    fn from(v: T) -> Self {
+        Changes(v.into())
+    }
+}
+
+///
+pub mod changes;
+
+///
+pub mod visit;
+#[doc(inline)]
+pub use visit::Visit;
+
+/// A [Visit][visit::Visit] implementation to record every observed change and keep track of the changed paths.
+#[derive(Clone, Debug)]
+pub struct Recorder {
+    path_deque: VecDeque<BString>,
+    path: BString,
+    location: Option<recorder::Location>,
+    /// The observed changes.
+    pub records: Vec<recorder::Change>,
+}
+
+/// Useful for use as delegate implementing [`Visit`] to keep track of all seen changes. Useful for debugging or printing primarily.
+pub mod recorder;
diff --git a/vendor/gix-diff/src/tree/recorder.rs b/vendor/gix-diff/src/tree/recorder.rs
new file mode 100644
index 000000000..dc92c3aca
--- /dev/null
+++ b/vendor/gix-diff/src/tree/recorder.rs
@@ -0,0 +1,157 @@
+use gix_hash::ObjectId;
+use gix_object::{
+    bstr::{BStr, BString, ByteSlice, ByteVec},
+    tree,
+};
+
+use crate::tree::{visit, Recorder};
+
+/// Describe how to track the location of a change.
+#[derive(Debug, Clone, Copy, Eq, PartialEq)]
+pub enum Location {
+    /// Track the entire path, relative to the repository.
+    Path,
+    /// Keep only the file-name as location, which may be enough for some calculations.
+    ///
+    /// This is less expensive than tracking the entire `Path`.
+    FileName,
+}
+
+/// A Change as observed by a call to [`visit(…)`][visit::Visit::visit()], enhanced with the path affected by the change.
+/// Its similar to [visit::Change] but includes the path that changed.
+#[derive(Clone, Debug, PartialEq, Eq)]
+#[allow(missing_docs)]
+pub enum Change {
+    Addition {
+        entry_mode: tree::EntryMode,
+        oid: ObjectId,
+        path: BString,
+    },
+    Deletion {
+        entry_mode: tree::EntryMode,
+        oid: ObjectId,
+        path: BString,
+    },
+    Modification {
+        previous_entry_mode: tree::EntryMode,
+        previous_oid: ObjectId,
+
+        entry_mode: tree::EntryMode,
+        oid: ObjectId,
+
+        path: BString,
+    },
+}
+
+impl Default for Recorder {
+    fn default() -> Self {
+        Recorder {
+            path_deque: Default::default(),
+            path: Default::default(),
+            location: Some(Location::Path),
+            records: vec![],
+        }
+    }
+}
+
+/// Builder
+impl Recorder {
+    /// Obtain a copy of the currently tracked, full path of the entry.
+    pub fn track_location(mut self, location: Option<Location>) -> Self {
+        self.location = location;
+        self
+    }
+}
+
+/// Access
+impl Recorder {
+    /// Obtain a copy of the currently tracked, full path of the entry.
+    pub fn path_clone(&self) -> BString {
+        self.path.clone()
+    }
+
+    /// Return the currently set path.
+    pub fn path(&self) -> &BStr {
+        self.path.as_ref()
+    }
+}
+
+impl Recorder {
+    fn pop_element(&mut self) {
+        if let Some(pos) = self.path.rfind_byte(b'/') {
+            self.path.resize(pos, 0);
+        } else {
+            self.path.clear();
+        }
+    }
+
+    fn push_element(&mut self, name: &BStr) {
+        if !self.path.is_empty() {
+            self.path.push(b'/');
+        }
+        self.path.push_str(name);
+    }
+}
+
+impl visit::Visit for Recorder {
+    fn pop_front_tracked_path_and_set_current(&mut self) {
+        if let Some(Location::Path) = self.location {
+            self.path = self.path_deque.pop_front().expect("every parent is set only once");
+        }
+    }
+
+    fn push_back_tracked_path_component(&mut self, component: &BStr) {
+        if let Some(Location::Path) = self.location {
+            self.push_element(component);
+            self.path_deque.push_back(self.path.clone());
+        }
+    }
+
+    fn push_path_component(&mut self, component: &BStr) {
+        match self.location {
+            None => {}
+            Some(Location::Path) => {
+                self.push_element(component);
+            }
+            Some(Location::FileName) => {
+                self.path.clear();
+                self.path.extend_from_slice(component);
+            }
+        }
+    }
+
+    fn pop_path_component(&mut self) {
+        if let Some(Location::Path) = self.location {
+            self.pop_element();
+        }
+    }
+
+    fn visit(&mut self, change: visit::Change) -> visit::Action {
+        use visit::Change::*;
+        self.records.push(match change {
+            Deletion { entry_mode, oid } => Change::Deletion {
+                entry_mode,
+                oid,
+                path: self.path_clone(),
+            },
+            Addition { entry_mode, oid } => Change::Addition {
+                entry_mode,
+                oid,
+                path: self.path_clone(),
+            },
+            Modification {
+                previous_entry_mode,
+                previous_oid,
+                entry_mode,
+                oid,
+            } => Change::Modification {
+                previous_entry_mode,
+                previous_oid,
+                entry_mode,
+                oid,
+                path: self.path_clone(),
+            },
+        });
+        visit::Action::Continue
+    }
+}
diff --git a/vendor/gix-diff/src/tree/visit.rs b/vendor/gix-diff/src/tree/visit.rs
new file mode 100644
index 000000000..e94c432ae
--- /dev/null
+++ b/vendor/gix-diff/src/tree/visit.rs
@@ -0,0 +1,112 @@
+use gix_hash::ObjectId;
+use gix_object::{bstr::BStr, tree, tree::EntryMode};
+
+/// Represents any possible change in order to turn one tree into another.
+#[derive(Debug, Clone, PartialOrd, PartialEq, Ord, Eq, Hash)]
+pub enum Change {
+    /// An entry was added, like the addition of a file or directory.
+    Addition {
+        /// The mode of the added entry.
+        entry_mode: tree::EntryMode,
+        /// The object id of the added entry.
+        oid: ObjectId,
+    },
+    /// An entry was deleted, like the deletion of a file or directory.
+    Deletion {
+        /// The mode of the deleted entry.
+        entry_mode: tree::EntryMode,
+        /// The object id of the deleted entry.
+        oid: ObjectId,
+    },
+    /// 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: tree::EntryMode,
+        /// The object id of the entry before the modification.
+        previous_oid: ObjectId,
+
+        /// The mode of the entry after the modification.
+        entry_mode: tree::EntryMode,
+        /// The object id after the modification.
+        oid: ObjectId,
+    },
+}
+
+impl Change {
+    /// Return the current object id.
+    pub fn oid(&self) -> &gix_hash::oid {
+        match self {
+            Change::Addition { oid, .. } | Change::Deletion { oid, .. } | Change::Modification { oid, .. } => oid,
+        }
+    }
+    /// Return the current tree entry mode.
+    pub fn entry_mode(&self) -> EntryMode {
+        match self {
+            Change::Addition { entry_mode, .. }
+            | Change::Deletion { entry_mode, .. }
+            | Change::Modification { entry_mode, .. } => *entry_mode,
+        }
+    }
+    /// Return the current object id and tree entry mode of a change.
+    pub fn oid_and_entry_mode(&self) -> (&gix_hash::oid, EntryMode) {
+        match self {
+            Change::Addition { oid, entry_mode }
+            | Change::Deletion { oid, entry_mode }
+            | Change::Modification { oid, entry_mode, .. } => (oid, *entry_mode),
+        }
+    }
+}
+
+/// What to do after a [Change] was [recorded][Visit::visit()].
+#[derive(Clone, Copy, PartialOrd, PartialEq, Ord, Eq, Hash)]
+pub enum Action {
+    /// Continue the traversal of changes.
+    Continue,
+    /// Stop the traversal of changes, making this the last call to [visit(…)][Visit::visit()].
+    Cancel,
+}
+
+impl Default for Action {
+    fn default() -> Self {
+        Action::Continue
+    }
+}
+
+impl Action {
+    /// Returns true if this action means to stop the traversal.
+    pub fn cancelled(&self) -> bool {
+        matches!(self, Action::Cancel)
+    }
+}
+
+/// A trait to allow responding to a traversal designed to figure out the [changes][Change]
+/// to turn tree A into tree B.
+pub trait Visit {
+    /// Sets the full path path in front of the queue so future calls to push and pop components affect it instead.
+    fn pop_front_tracked_path_and_set_current(&mut self);
+    /// Append a `component` to the end of a path, which may be empty.
+    fn push_back_tracked_path_component(&mut self, component: &BStr);
+    /// Append a `component` to the end of a path, which may be empty.
+    fn push_path_component(&mut self, component: &BStr);
+    /// Removes the last component from the path, which may leave it empty.
+    fn pop_path_component(&mut self);
+    /// Record a `change` and return an instruction whether to continue or not.
+    ///
+    /// The implementation may use the current path to lean where in the tree the change is located.
+    fn visit(&mut self, change: Change) -> Action;
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn size_of_change() {
+        let actual = std::mem::size_of::<Change>();
+        assert!(
+            actual <= 46,
+            "{actual} <= 46: this type shouldn't grow without us knowing"
+        )
+    }
+}