Merging upstream version 1.70.0+dfsg2.

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

3 files changed, 315 insertions, 0 deletions

diff --git a/vendor/gix-traverse/src/tree/breadthfirst.rs b/vendor/gix-traverse/src/tree/breadthfirst.rs
new file mode 100644
index 000000000..b0c7ffdf5
--- /dev/null
+++ b/vendor/gix-traverse/src/tree/breadthfirst.rs
@@ -0,0 +1,107 @@
+use std::collections::VecDeque;
+
+use gix_hash::ObjectId;
+
+/// The error is part of the item returned by the [`traverse()`][impl_::traverse()] function.
+#[derive(Debug, thiserror::Error)]
+#[allow(missing_docs)]
+pub enum Error {
+    #[error("The tree {oid} could not be found")]
+    NotFound { oid: ObjectId },
+    #[error("The delegate cancelled the operation")]
+    Cancelled,
+    #[error(transparent)]
+    ObjectDecode(#[from] gix_object::decode::Error),
+}
+
+/// The state used and potentially shared by multiple tree traversals.
+#[derive(Default, Clone)]
+pub struct State {
+    next: VecDeque<ObjectId>,
+    buf: Vec<u8>,
+}
+
+impl State {
+    fn clear(&mut self) {
+        self.next.clear();
+        self.buf.clear();
+    }
+}
+
+pub(crate) mod impl_ {
+    use std::borrow::BorrowMut;
+
+    use gix_hash::oid;
+    use gix_object::{tree::EntryMode, TreeRefIter};
+
+    use super::{Error, State};
+    use crate::tree::Visit;
+
+    /// Start a breadth-first iteration over the `root` trees entries.
+    ///
+    /// * `root`
+    ///   * the tree to iterate in a nested fashion.
+    /// * `state` - all state used for the iteration. If multiple iterations are performed, allocations can be minimized by reusing
+    ///   this state.
+    /// * `find` - a way to lookup new object data during traversal by their ObjectId, writing their data into buffer and returning
+    ///    an iterator over entries if the object is present and is a tree. Caching should be implemented within this function
+    ///    as needed. The return value is `Option<TreeIter>` which degenerates all error information. Not finding a commit should also
+    ///    be considered an errors as all objects in the tree DAG should be present in the database. Hence [`Error::NotFound`] should
+    ///    be escalated into a more specific error if its encountered by the caller.
+    /// * `delegate` - A way to observe entries and control the iteration while allowing the optimizer to let you pay only for what you use.
+    pub fn traverse<StateMut, Find, V>(
+        root: TreeRefIter<'_>,
+        mut state: StateMut,
+        mut find: Find,
+        delegate: &mut V,
+    ) -> Result<(), Error>
+    where
+        Find: for<'a> FnMut(&oid, &'a mut Vec<u8>) -> Option<TreeRefIter<'a>>,
+        StateMut: BorrowMut<State>,
+        V: Visit,
+    {
+        let state = state.borrow_mut();
+        state.clear();
+        let mut tree = root;
+        loop {
+            for entry in tree {
+                let entry = entry?;
+                match entry.mode {
+                    EntryMode::Tree => {
+                        use crate::tree::visit::Action::*;
+                        delegate.push_path_component(entry.filename);
+                        let action = delegate.visit_tree(&entry);
+                        match action {
+                            Skip => {}
+                            Continue => {
+                                delegate.pop_path_component();
+                                delegate.push_back_tracked_path_component(entry.filename);
+                                state.next.push_back(entry.oid.to_owned())
+                            }
+                            Cancel => {
+                                return Err(Error::Cancelled);
+                            }
+                        }
+                    }
+                    _non_tree => {
+                        delegate.push_path_component(entry.filename);
+                        if delegate.visit_nontree(&entry).cancelled() {
+                            return Err(Error::Cancelled);
+                        }
+                    }
+                }
+                delegate.pop_path_component();
+            }
+            match state.next.pop_front() {
+                Some(oid) => {
+                    delegate.pop_front_tracked_path_and_set_current();
+                    match find(&oid, &mut state.buf) {
+                        Some(tree_iter) => tree = tree_iter,
+                        None => return Err(Error::NotFound { oid: oid.to_owned() }),
+                    }
+                }
+                None => break Ok(()),
+            }
+        }
+    }
+}
diff --git a/vendor/gix-traverse/src/tree/mod.rs b/vendor/gix-traverse/src/tree/mod.rs
new file mode 100644
index 000000000..5ae01736c
--- /dev/null
+++ b/vendor/gix-traverse/src/tree/mod.rs
@@ -0,0 +1,69 @@
+use std::collections::VecDeque;
+
+use gix_object::bstr::{BStr, BString};
+
+/// A trait to allow responding to a traversal designed to observe all entries in a tree, recursively while keeping track of
+/// paths if desired.
+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);
+
+    /// Observe a tree entry that is a tree and return an instruction whether to continue or not.
+    /// [`Action::Skip`][visit::Action::Skip] can be used to prevent traversing it, for example if it's known to the caller already.
+    ///
+    /// The implementation may use the current path to learn where in the tree the change is located.
+    fn visit_tree(&mut self, entry: &gix_object::tree::EntryRef<'_>) -> visit::Action;
+
+    /// Observe a tree entry that is NO tree and return an instruction whether to continue or not.
+    /// [`Action::Skip`][visit::Action::Skip] has no effect here.
+    ///
+    /// The implementation may use the current path to learn where in the tree the change is located.
+    fn visit_nontree(&mut self, entry: &gix_object::tree::EntryRef<'_>) -> visit::Action;
+}
+
+/// A [Visit][Visit] implementation to record every observed change and keep track of the changed paths.
+///
+/// Recorders can also be instructed to track the filename only, or no location at all.
+#[derive(Clone, Debug)]
+pub struct Recorder {
+    path_deque: VecDeque<BString>,
+    path: BString,
+    /// How to track the location.
+    location: Option<recorder::Location>,
+    /// The observed entries.
+    pub records: Vec<recorder::Entry>,
+}
+
+///
+pub mod visit {
+    /// What to do after an entry was [recorded][super::Visit::visit_tree()].
+    #[derive(Clone, Copy, PartialOrd, PartialEq, Ord, Eq, Hash)]
+    pub enum Action {
+        /// Continue the traversal of entries.
+        Continue,
+        /// Stop the traversal of entries, making this te last call to [`visit_(tree|nontree)(…)`][super::Visit::visit_nontree()].
+        Cancel,
+        /// Don't dive into the entry, skipping children effectively. Only useful in [`visit_tree(…)`][super::Visit::visit_tree()].
+        Skip,
+    }
+
+    impl Action {
+        /// Returns true if this action means to stop the traversal.
+        pub fn cancelled(&self) -> bool {
+            matches!(self, Action::Cancel)
+        }
+    }
+}
+
+///
+pub mod recorder;
+
+///
+pub mod breadthfirst;
+pub use breadthfirst::impl_::traverse as breadthfirst;
diff --git a/vendor/gix-traverse/src/tree/recorder.rs b/vendor/gix-traverse/src/tree/recorder.rs
new file mode 100644
index 000000000..d6144c9b9
--- /dev/null
+++ b/vendor/gix-traverse/src/tree/recorder.rs
@@ -0,0 +1,139 @@
+use gix_hash::ObjectId;
+use gix_object::{
+    bstr::{BStr, BString, ByteSlice, ByteVec},
+    tree,
+};
+
+use crate::tree::{visit::Action, Recorder, Visit};
+
+/// Describe how to track the location of an entry.
+#[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,
+}
+
+/// An owned entry as observed by a call to [`visit_(tree|nontree)(…)`][Visit::visit_tree()], enhanced with the full path to it.
+/// Otherwise similar to [`gix_object::tree::EntryRef`].
+#[derive(Clone, Debug, PartialEq, Eq)]
+pub struct Entry {
+    /// The kind of entry, similar to entries in a unix directory tree.
+    pub mode: tree::EntryMode,
+    /// The full path to the entry. A root entry would be `d`, and a file `a` within the directory would be `d/a`.
+    ///
+    /// This is independent of the platform and the path separators actually used there.
+    pub filepath: BString,
+    /// The id of the entry which can be used to locate it in an object database.
+    pub oid: ObjectId,
+}
+
+impl Entry {
+    fn new(entry: &tree::EntryRef<'_>, filepath: BString) -> Self {
+        Entry {
+            filepath,
+            oid: entry.oid.to_owned(),
+            mode: entry.mode,
+        }
+    }
+}
+
+impl Default for Recorder {
+    fn default() -> Self {
+        Recorder {
+            path_deque: Default::default(),
+            path: Default::default(),
+            location: Location::Path.into(),
+            records: vec![],
+        }
+    }
+}
+
+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);
+    }
+}
+
+/// 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 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 call is matched with push_tracked_path_component");
+        }
+    }
+
+    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_tree(&mut self, entry: &tree::EntryRef<'_>) -> Action {
+        self.records.push(Entry::new(entry, self.path_clone()));
+        Action::Continue
+    }
+
+    fn visit_nontree(&mut self, entry: &tree::EntryRef<'_>) -> Action {
+        self.records.push(Entry::new(entry, self.path_clone()));
+        Action::Continue
+    }
+}