Merging upstream version 1.72.1+dfsg1.

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

5 files changed, 112 insertions, 182 deletions

diff --git a/vendor/gix-revision/src/describe.rs b/vendor/gix-revision/src/describe.rs
index 55cc3deef..2c1636477 100644
--- a/vendor/gix-revision/src/describe.rs
+++ b/vendor/gix-revision/src/describe.rs
@@ -94,7 +94,8 @@ impl<'a> Display for Format<'a> {
     }
 }
 
-type Flags = u32;
+/// A bit-field which keeps track of which commit is reachable by one of 32 candidates names.
+pub type Flags = u32;
 const MAX_CANDIDATES: usize = std::mem::size_of::<Flags>() * 8;
 
 /// The options required to call [`describe()`][function::describe()].
@@ -129,14 +130,11 @@ impl<'name> Default for Options<'name> {
 /// The error returned by the [`describe()`][function::describe()] function.
 #[derive(Debug, thiserror::Error)]
 #[allow(missing_docs)]
-pub enum Error<E>
-where
-    E: std::error::Error + Send + Sync + 'static,
-{
-    #[error("Commit {} could not be found during graph traversal", .oid.to_hex())]
-    Find {
+pub enum Error {
+    #[error("The parents of commit {} could not be added to graph during traversal", oid.to_hex())]
+    InsertParentsToGraph {
         #[source]
-        err: Option<E>,
+        err: crate::graph::insert_parents::Error,
         oid: gix_hash::ObjectId,
     },
     #[error("A commit could not be decoded during traversal")]
@@ -144,35 +142,32 @@ where
 }
 
 pub(crate) mod function {
-    use std::{borrow::Cow, cmp::Ordering, collections::VecDeque, iter::FromIterator};
+    use std::{borrow::Cow, cmp::Ordering};
 
     use bstr::BStr;
     use gix_hash::oid;
-    use gix_hashtable::{hash_map, HashMap};
-    use gix_object::CommitRefIter;
 
     use super::{Error, Outcome};
-    use crate::describe::{Flags, Options, MAX_CANDIDATES};
+    use crate::{
+        describe::{CommitTime, Flags, Options, MAX_CANDIDATES},
+        Graph, PriorityQueue,
+    };
 
-    /// Given a `commit` id, traverse the commit graph and collect candidate names from the `name_by_oid` mapping to produce
+    /// Given a `commit` id, traverse the commit `graph` and collect candidate names from the `name_by_oid` mapping to produce
     /// an `Outcome`, which converted [`into_format()`][Outcome::into_format()] will produce a typical `git describe` string.
     ///
     /// Note that the `name_by_oid` map is returned in the [`Outcome`], which can be forcefully returned even if there was no matching
     /// candidate by setting `fallback_to_oid` to true.
-    pub fn describe<'name, Find, E>(
+    pub fn describe<'name>(
         commit: &oid,
-        mut find: Find,
+        graph: &mut Graph<'_, Flags>,
         Options {
             name_by_oid,
             mut max_candidates,
             fallback_to_oid,
             first_parent,
         }: Options<'name>,
-    ) -> Result<Option<Outcome<'name>>, Error<E>>
-    where
-        Find: for<'b> FnMut(&oid, &'b mut Vec<u8>) -> Result<Option<CommitRefIter<'b>>, E>,
-        E: std::error::Error + Send + Sync + 'static,
-    {
+    ) -> Result<Option<Outcome<'name>>, Error> {
         max_candidates = max_candidates.min(MAX_CANDIDATES);
         if let Some(name) = name_by_oid.get(commit) {
             return Ok(Some(Outcome {
@@ -198,19 +193,16 @@ pub(crate) mod function {
             };
         }
 
-        let mut buf = Vec::new();
-        let mut parent_buf = Vec::new();
-
-        let mut queue = VecDeque::from_iter(Some((commit.to_owned(), u32::MAX)));
+        let mut queue = PriorityQueue::from_iter(Some((u32::MAX, commit.to_owned())));
         let mut candidates = Vec::new();
         let mut commits_seen = 0;
         let mut gave_up_on_commit = None;
-        let mut seen = HashMap::<gix_hash::ObjectId, Flags>::default();
-        seen.insert(commit.to_owned(), 0u32);
+        graph.clear();
+        graph.insert(commit.to_owned(), 0u32);
 
-        while let Some((commit, _commit_time)) = queue.pop_front() {
+        while let Some(commit) = queue.pop_value() {
             commits_seen += 1;
-            if let Some(name) = name_by_oid.get(&commit) {
+            let flags = if let Some(name) = name_by_oid.get(&commit) {
                 if candidates.len() < max_candidates {
                     let identity_bit = 1 << candidates.len();
                     candidates.push(Candidate {
@@ -219,14 +211,17 @@ pub(crate) mod function {
                         identity_bit,
                         order: candidates.len(),
                     });
-                    *seen.get_mut(&commit).expect("inserted") |= identity_bit;
+                    let flags = graph.get_mut(&commit).expect("inserted");
+                    *flags |= identity_bit;
+                    *flags
                 } else {
                     gave_up_on_commit = Some(commit);
                     break;
                 }
-            }
+            } else {
+                graph[&commit]
+            };
 
-            let flags = seen[&commit];
             for candidate in candidates
                 .iter_mut()
                 .filter(|c| (flags & c.identity_bit) != c.identity_bit)
@@ -257,16 +252,7 @@ pub(crate) mod function {
                 }
             }
 
-            parents_by_date_onto_queue_and_track_names(
-                &mut find,
-                &mut buf,
-                &mut parent_buf,
-                &mut queue,
-                &mut seen,
-                &commit,
-                flags,
-                first_parent,
-            )?;
+            parents_by_date_onto_queue_and_track_names(graph, &mut queue, commit, flags, first_parent)?;
         }
 
         if candidates.is_empty() {
@@ -290,17 +276,14 @@ pub(crate) mod function {
         });
 
         if let Some(commit_id) = gave_up_on_commit {
-            queue.push_front((commit_id, u32::MAX));
+            queue.insert(u32::MAX, commit_id);
             commits_seen -= 1;
         }
 
         commits_seen += finish_depth_computation(
             queue,
-            find,
+            graph,
             candidates.first_mut().expect("at least one candidate"),
-            seen,
-            buf,
-            parent_buf,
             first_parent,
         )?;
 
@@ -313,91 +296,41 @@ pub(crate) mod function {
         }))
     }
 
-    #[allow(clippy::too_many_arguments)]
-    fn parents_by_date_onto_queue_and_track_names<Find, E>(
-        find: &mut Find,
-        buf: &mut Vec<u8>,
-        parent_buf: &mut Vec<u8>,
-        queue: &mut VecDeque<(gix_hash::ObjectId, u32)>,
-        seen: &mut HashMap<gix_hash::ObjectId, Flags>,
-        commit: &gix_hash::oid,
+    fn parents_by_date_onto_queue_and_track_names(
+        graph: &mut Graph<'_, Flags>,
+        queue: &mut PriorityQueue<CommitTime, gix_hash::ObjectId>,
+        commit: gix_hash::ObjectId,
         commit_flags: Flags,
         first_parent: bool,
-    ) -> Result<(), Error<E>>
-    where
-        Find: for<'b> FnMut(&oid, &'b mut Vec<u8>) -> Result<Option<CommitRefIter<'b>>, E>,
-        E: std::error::Error + Send + Sync + 'static,
-    {
-        let commit_iter = find(commit, buf)
-            .map_err(|err| Error::Find {
-                err: Some(err),
-                oid: commit.to_owned(),
-            })?
-            .ok_or_else(|| Error::Find {
-                err: None,
-                oid: commit.to_owned(),
-            })?;
-        for token in commit_iter {
-            match token {
-                Ok(gix_object::commit::ref_iter::Token::Tree { .. }) => continue,
-                Ok(gix_object::commit::ref_iter::Token::Parent { id: parent_id }) => match seen.entry(parent_id) {
-                    hash_map::Entry::Vacant(entry) => {
-                        let parent = match find(&parent_id, parent_buf).map_err(|err| Error::Find {
-                            err: Some(err),
-                            oid: commit.to_owned(),
-                        })? {
-                            Some(p) => p,
-                            None => continue, // skip missing objects, they don't exist.
-                        };
-
-                        let parent_commit_date = parent
-                            .committer()
-                            .map(|committer| committer.time.seconds_since_unix_epoch)
-                            .unwrap_or_default();
-
-                        entry.insert(commit_flags);
-                        match queue.binary_search_by(|c| c.1.cmp(&parent_commit_date).reverse()) {
-                            Ok(_) => queue.push_back((parent_id, parent_commit_date)),
-                            Err(pos) => queue.insert(pos, (parent_id, parent_commit_date)),
-                        };
-                    }
-                    hash_map::Entry::Occupied(mut entry) => {
-                        *entry.get_mut() |= commit_flags;
-                    }
+    ) -> Result<(), Error> {
+        graph
+            .insert_parents(
+                &commit,
+                |parent_id, parent_commit_date| {
+                    queue.insert(parent_commit_date as u32, parent_id);
+                    commit_flags
                 },
-                Ok(_unused_token) => break,
-                Err(err) => return Err(err.into()),
-            }
-            if first_parent {
-                break;
-            }
-        }
-
+                |_parent_id, flags| *flags |= commit_flags,
+                first_parent,
+            )
+            .map_err(|err| Error::InsertParentsToGraph { err, oid: commit })?;
         Ok(())
     }
 
-    #[allow(clippy::too_many_arguments)]
-    fn finish_depth_computation<'name, Find, E>(
-        mut queue: VecDeque<(gix_hash::ObjectId, u32)>,
-        mut find: Find,
-        best_candidate: &mut Candidate<'name>,
-        mut seen: HashMap<gix_hash::ObjectId, Flags>,
-        mut buf: Vec<u8>,
-        mut parent_buf: Vec<u8>,
+    fn finish_depth_computation(
+        mut queue: PriorityQueue<CommitTime, gix_hash::ObjectId>,
+        graph: &mut Graph<'_, Flags>,
+        best_candidate: &mut Candidate<'_>,
         first_parent: bool,
-    ) -> Result<u32, Error<E>>
-    where
-        Find: for<'b> FnMut(&oid, &'b mut Vec<u8>) -> Result<Option<CommitRefIter<'b>>, E>,
-        E: std::error::Error + Send + Sync + 'static,
-    {
+    ) -> Result<u32, Error> {
         let mut commits_seen = 0;
-        while let Some((commit, _commit_time)) = queue.pop_front() {
+        while let Some(commit) = queue.pop_value() {
             commits_seen += 1;
-            let flags = seen[&commit];
+            let flags = graph[&commit];
             if (flags & best_candidate.identity_bit) == best_candidate.identity_bit {
                 if queue
-                    .iter()
-                    .all(|(id, _)| (seen[id] & best_candidate.identity_bit) == best_candidate.identity_bit)
+                    .iter_unordered()
+                    .all(|id| (graph[id] & best_candidate.identity_bit) == best_candidate.identity_bit)
                 {
                     break;
                 }
@@ -405,16 +338,7 @@ pub(crate) mod function {
                 best_candidate.commits_in_its_future += 1;
             }
 
-            parents_by_date_onto_queue_and_track_names(
-                &mut find,
-                &mut buf,
-                &mut parent_buf,
-                &mut queue,
-                &mut seen,
-                &commit,
-                flags,
-                first_parent,
-            )?;
+            parents_by_date_onto_queue_and_track_names(graph, &mut queue, commit, flags, first_parent)?;
         }
         Ok(commits_seen)
     }
@@ -429,3 +353,6 @@ pub(crate) mod function {
         order: usize,
     }
 }
+
+/// The timestamp for the creation date of a commit in seconds since unix epoch.
+type CommitTime = u32;
diff --git a/vendor/gix-revision/src/lib.rs b/vendor/gix-revision/src/lib.rs
index ef273b5ae..31d22768c 100644
--- a/vendor/gix-revision/src/lib.rs
+++ b/vendor/gix-revision/src/lib.rs
@@ -14,6 +14,6 @@ pub use describe::function::describe;
 
 ///
 pub mod spec;
+pub use spec::types::Spec;
 
-mod types;
-pub use types::Spec;
+pub use gix_revwalk::{graph, Graph, PriorityQueue};
diff --git a/vendor/gix-revision/src/spec/mod.rs b/vendor/gix-revision/src/spec/mod.rs
index c2df7bc1e..616ad3a26 100644
--- a/vendor/gix-revision/src/spec/mod.rs
+++ b/vendor/gix-revision/src/spec/mod.rs
@@ -53,6 +53,57 @@ mod _impls {
     }
 }
 
+pub(crate) mod types {
+    /// A revision specification without any bindings to a repository, useful for serialization or movement over thread boundaries.
+    ///
+    /// Note that all [object ids][gix_hash::ObjectId] should be a committish, but don't have to be.
+    /// Unless the field name contains `_exclusive`, the respective objects are included in the set.
+    #[derive(Copy, Clone, Debug, Ord, PartialOrd, Eq, PartialEq, Hash)]
+    #[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
+    pub enum Spec {
+        /// Include commits reachable from this revision, i.e. `a` and its ancestors.
+        ///
+        /// The equivalent to [crate::spec::Kind::IncludeReachable], but with data.
+        Include(gix_hash::ObjectId),
+        /// Exclude commits reachable from this revision, i.e. `a` and its ancestors. Example: `^a`.
+        ///
+        /// The equivalent to [crate::spec::Kind::ExcludeReachable], but with data.
+        Exclude(gix_hash::ObjectId),
+        /// Every commit that is reachable from `from` to `to`, but not any ancestors of `from`. Example: `from..to`.
+        ///
+        /// The equivalent to [crate::spec::Kind::RangeBetween], but with data.
+        Range {
+            /// The starting point of the range, which is included in the set.
+            from: gix_hash::ObjectId,
+            /// The end point of the range, which is included in the set.
+            to: gix_hash::ObjectId,
+        },
+        /// Every commit reachable through either `theirs` or `ours`, but no commit that is reachable by both. Example: `theirs...ours`.
+        ///
+        /// The equivalent to [crate::spec::Kind::ReachableToMergeBase], but with data.
+        Merge {
+            /// Their side of the merge, which is included in the set.
+            theirs: gix_hash::ObjectId,
+            /// Our side of the merge, which is included in the set.
+            ours: gix_hash::ObjectId,
+        },
+        /// Include every commit of all parents of `a`, but not `a` itself. Example: `a^@`.
+        ///
+        /// The equivalent to [crate::spec::Kind::IncludeReachableFromParents], but with data.
+        IncludeOnlyParents(
+            /// Include only the parents of this object, but not the object itself.
+            gix_hash::ObjectId,
+        ),
+        /// Exclude every commit of all parents of `a`, but not `a` itself. Example: `a^!`.
+        ///
+        /// The equivalent to [crate::spec::Kind::ExcludeReachableFromParents], but with data.
+        ExcludeParents(
+            /// Exclude the parents of this object, but not the object itself.
+            gix_hash::ObjectId,
+        ),
+    }
+}
+
 ///
 pub mod parse;
 pub use parse::function::parse;
diff --git a/vendor/gix-revision/src/spec/parse/function.rs b/vendor/gix-revision/src/spec/parse/function.rs
index 94fb4ee5d..8a89f8f68 100644
--- a/vendor/gix-revision/src/spec/parse/function.rs
+++ b/vendor/gix-revision/src/spec/parse/function.rs
@@ -213,7 +213,7 @@ fn long_describe_prefix(name: &BStr) -> Option<(&BStr, delegate::PrefixHint<'_>)
         .and_then(|generation| {
             iter.next().map(|token| {
                 let last_token_len = token.len();
-                let first_token_ptr = iter.last().map(|token| token.as_ptr()).unwrap_or(token.as_ptr());
+                let first_token_ptr = iter.last().map_or(token.as_ptr(), |token| token.as_ptr());
                 // SAFETY: both pointers are definitely part of the same object
                 #[allow(unsafe_code)]
                 let prior_tokens_len: usize = unsafe { token.as_ptr().offset_from(first_token_ptr) }
@@ -413,7 +413,7 @@ where
 
     input = {
         if let Some(b'@') = sep {
-            let past_sep = input[sep_pos.map(|pos| pos + 1).unwrap_or(input.len())..].as_bstr();
+            let past_sep = input[sep_pos.map_or(input.len(), |pos| pos + 1)..].as_bstr();
             let (nav, rest, _consumed) = parens(past_sep)?.ok_or_else(|| Error::AtNeedsCurlyBrackets {
                 input: input[sep_pos.unwrap_or(input.len())..].into(),
             })?;
diff --git a/vendor/gix-revision/src/types.rs b/vendor/gix-revision/src/types.rs
deleted file mode 100644
index 374d43e20..000000000
--- a/vendor/gix-revision/src/types.rs
+++ /dev/null
@@ -1,48 +0,0 @@
-/// A revision specification without any bindings to a repository, useful for serialization or movement over thread boundaries.
-///
-/// Note that all [object ids][gix_hash::ObjectId] should be a committish, but don't have to be.
-/// Unless the field name contains `_exclusive`, the respective objects are included in the set.
-#[derive(Copy, Clone, Debug, Ord, PartialOrd, Eq, PartialEq, Hash)]
-#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
-pub enum Spec {
-    /// Include commits reachable from this revision, i.e. `a` and its ancestors.
-    ///
-    /// The equivalent to [crate::spec::Kind::IncludeReachable], but with data.
-    Include(gix_hash::ObjectId),
-    /// Exclude commits reachable from this revision, i.e. `a` and its ancestors. Example: `^a`.
-    ///
-    /// The equivalent to [crate::spec::Kind::ExcludeReachable], but with data.
-    Exclude(gix_hash::ObjectId),
-    /// Every commit that is reachable from `from` to `to`, but not any ancestors of `from`. Example: `from..to`.
-    ///
-    /// The equivalent to [crate::spec::Kind::RangeBetween], but with data.
-    Range {
-        /// The starting point of the range, which is included in the set.
-        from: gix_hash::ObjectId,
-        /// The end point of the range, which is included in the set.
-        to: gix_hash::ObjectId,
-    },
-    /// Every commit reachable through either `theirs` or `ours`, but no commit that is reachable by both. Example: `theirs...ours`.
-    ///
-    /// The equivalent to [crate::spec::Kind::ReachableToMergeBase], but with data.
-    Merge {
-        /// Their side of the merge, which is included in the set.
-        theirs: gix_hash::ObjectId,
-        /// Our side of the merge, which is included in the set.
-        ours: gix_hash::ObjectId,
-    },
-    /// Include every commit of all parents of `a`, but not `a` itself. Example: `a^@`.
-    ///
-    /// The equivalent to [crate::spec::Kind::IncludeReachableFromParents], but with data.
-    IncludeOnlyParents(
-        /// Include only the parents of this object, but not the object itself.
-        gix_hash::ObjectId,
-    ),
-    /// Exclude every commit of all parents of `a`, but not `a` itself. Example: `a^!`.
-    ///
-    /// The equivalent to [crate::spec::Kind::ExcludeReachableFromParents], but with data.
-    ExcludeParents(
-        /// Exclude the parents of this object, but not the object itself.
-        gix_hash::ObjectId,
-    ),
-}