Merging upstream version 1.72.1+dfsg1.

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

10 files changed, 985 insertions, 0 deletions

diff --git a/vendor/gix-revwalk/.cargo-checksum.json b/vendor/gix-revwalk/.cargo-checksum.json
new file mode 100644
index 000000000..cf283fcff
--- /dev/null
+++ b/vendor/gix-revwalk/.cargo-checksum.json
@@ -0,0 +1 @@
+{"files":{"CHANGELOG.md":"3c1a2e0f720b671163182b18d7e1b32f07f5e64c42f5b140b8b94f3a7748f1d9","Cargo.toml":"f59b4689046d339936e9a18c24ad7542598ef4da69a9870682ada2f93a2734fe","LICENSE-APACHE":"cb4780590812826851ba250f90bed0ed19506ec98f6865a0e2e20bbf62391ff9","LICENSE-MIT":"49df47913ab2beafe8dc45607877ae64198bf0eee64aaad3e82ed9e4d27424e8","src/graph/commit.rs":"6ede08a41a98f9d590633ed2a7ef9d391676e93509994d85b8ef9056b46cf887","src/graph/errors.rs":"5b76551bae0cea85ca3d21fd1a1c86453d96cd49692159b822f403e92eb1a2b4","src/graph/mod.rs":"b642c705befec29b9fb128bb576e01eb5595ff7d146866f49ff7e15b4728c7f1","src/lib.rs":"d776108c321ffb0d218ebc410f1afd4c05bdf851205283ba726c4b6d17af5eae","src/queue.rs":"82cecd24646e25732342e950f00f28c16521d82d45562dc0aa558cf07a269885"},"package":"bc2623ba8747914f151f5e12b65adac576ab459dbed5f50a36c7a3e9cbf2d3ca"}
\ No newline at end of file
diff --git a/vendor/gix-revwalk/CHANGELOG.md b/vendor/gix-revwalk/CHANGELOG.md
new file mode 100644
index 000000000..8939887c3
--- /dev/null
+++ b/vendor/gix-revwalk/CHANGELOG.md
@@ -0,0 +1,35 @@
+# Changelog
+
+All notable changes to this project will be documented in this file.
+
+The format is based on [Keep a Changelog](https://keepachangelog.com/en/1.0.0/),
+and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0.html).
+
+## 0.1.0 (2023-06-10)
+
+### Bug Fixes (BREAKING)
+
+ - <csr-id-e9205679ab017699fd2605d4211d7ac2528dbc4b/> rename `PriorityQueue::pop()` to `::pop_value()` and add `::pop()` that also pops the key.
+   This aligns the method name with `peek()`, which also pops the key.
+
+### Commit Statistics
+
+<csr-read-only-do-not-edit/>
+
+ - 4 commits contributed to the release.
+ - 1 commit was understood as [conventional](https://www.conventionalcommits.org).
+ - 0 issues like '(#ID)' were seen in commit messages
+
+### Commit Details
+
+<csr-read-only-do-not-edit/>
+
+<details><summary>view details</summary>
+
+ * **Uncategorized**
+    - Prepare changelogs prior to release ([`298f3d7`](https://github.com/Byron/gitoxide/commit/298f3d7359c5b183314d8c584e45dcdd559d88b3))
+    - Merge branch 'walk-with-commitgraph' ([`fdee9a2`](https://github.com/Byron/gitoxide/commit/fdee9a22873a13ae644d3dc92f8fe93f8f0266c0))
+    - Rename `PriorityQueue::pop()` to `::pop_value()` and add `::pop()` that also pops the key. ([`e920567`](https://github.com/Byron/gitoxide/commit/e9205679ab017699fd2605d4211d7ac2528dbc4b))
+    - Add new `gix-revwalk` crate for support types related to revision walking. ([`13ce887`](https://github.com/Byron/gitoxide/commit/13ce887682f5c31d1f78a63613ca97b811e4ffba))
+</details>
+
diff --git a/vendor/gix-revwalk/Cargo.toml b/vendor/gix-revwalk/Cargo.toml
new file mode 100644
index 000000000..aa131055f
--- /dev/null
+++ b/vendor/gix-revwalk/Cargo.toml
@@ -0,0 +1,46 @@
+# THIS FILE IS AUTOMATICALLY GENERATED BY CARGO
+#
+# When uploading crates to the registry Cargo will automatically
+# "normalize" Cargo.toml files for maximal compatibility
+# with all versions of Cargo and also rewrite `path` dependencies
+# to registry (e.g., crates.io) dependencies.
+#
+# If you are reading this file be aware that the original Cargo.toml
+# will likely look very different (and much more reasonable).
+# See Cargo.toml.orig for the original contents.
+
+[package]
+edition = "2021"
+rust-version = "1.64"
+name = "gix-revwalk"
+version = "0.1.0"
+authors = ["Sebastian Thiel <sebastian.thiel@icloud.com>"]
+include = [
+    "src/**/*",
+    "LICENSE-*",
+    "CHANGELOG.md",
+]
+description = "A crate providing utilities for walking the revision graph"
+license = "MIT/Apache-2.0"
+repository = "https://github.com/Byron/gitoxide"
+
+[lib]
+doctest = false
+
+[dependencies.gix-commitgraph]
+version = "^0.16.0"
+
+[dependencies.gix-hash]
+version = "^0.11.2"
+
+[dependencies.gix-hashtable]
+version = "^0.2.1"
+
+[dependencies.gix-object]
+version = "^0.30.0"
+
+[dependencies.smallvec]
+version = "1.10.0"
+
+[dependencies.thiserror]
+version = "1.0.26"
diff --git a/vendor/gix-revwalk/LICENSE-APACHE b/vendor/gix-revwalk/LICENSE-APACHE
new file mode 100644
index 000000000..a51f59a06
--- /dev/null
+++ b/vendor/gix-revwalk/LICENSE-APACHE
@@ -0,0 +1,191 @@
+
+                                 Apache License
+                           Version 2.0, January 2004
+                        http://www.apache.org/licenses/
+
+   TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION
+
+   1. Definitions.
+
+      "License" shall mean the terms and conditions for use, reproduction,
+      and distribution as defined by Sections 1 through 9 of this document.
+
+      "Licensor" shall mean the copyright owner or entity authorized by
+      the copyright owner that is granting the License.
+
+      "Legal Entity" shall mean the union of the acting entity and all
+      other entities that control, are controlled by, or are under common
+      control with that entity. For the purposes of this definition,
+      "control" means (i) the power, direct or indirect, to cause the
+      direction or management of such entity, whether by contract or
+      otherwise, or (ii) ownership of fifty percent (50%) or more of the
+      outstanding shares, or (iii) beneficial ownership of such entity.
+
+      "You" (or "Your") shall mean an individual or Legal Entity
+      exercising permissions granted by this License.
+
+      "Source" form shall mean the preferred form for making modifications,
+      including but not limited to software source code, documentation
+      source, and configuration files.
+
+      "Object" form shall mean any form resulting from mechanical
+      transformation or translation of a Source form, including but
+      not limited to compiled object code, generated documentation,
+      and conversions to other media types.
+
+      "Work" shall mean the work of authorship, whether in Source or
+      Object form, made available under the License, as indicated by a
+      copyright notice that is included in or attached to the work
+      (an example is provided in the Appendix below).
+
+      "Derivative Works" shall mean any work, whether in Source or Object
+      form, that is based on (or derived from) the Work and for which the
+      editorial revisions, annotations, elaborations, or other modifications
+      represent, as a whole, an original work of authorship. For the purposes
+      of this License, Derivative Works shall not include works that remain
+      separable from, or merely link (or bind by name) to the interfaces of,
+      the Work and Derivative Works thereof.
+
+      "Contribution" shall mean any work of authorship, including
+      the original version of the Work and any modifications or additions
+      to that Work or Derivative Works thereof, that is intentionally
+      submitted to Licensor for inclusion in the Work by the copyright owner
+      or by an individual or Legal Entity authorized to submit on behalf of
+      the copyright owner. For the purposes of this definition, "submitted"
+      means any form of electronic, verbal, or written communication sent
+      to the Licensor or its representatives, including but not limited to
+      communication on electronic mailing lists, source code control systems,
+      and issue tracking systems that are managed by, or on behalf of, the
+      Licensor for the purpose of discussing and improving the Work, but
+      excluding communication that is conspicuously marked or otherwise
+      designated in writing by the copyright owner as "Not a Contribution."
+
+      "Contributor" shall mean Licensor and any individual or Legal Entity
+      on behalf of whom a Contribution has been received by Licensor and
+      subsequently incorporated within the Work.
+
+   2. Grant of Copyright License. Subject to the terms and conditions of
+      this License, each Contributor hereby grants to You a perpetual,
+      worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+      copyright license to reproduce, prepare Derivative Works of,
+      publicly display, publicly perform, sublicense, and distribute the
+      Work and such Derivative Works in Source or Object form.
+
+   3. Grant of Patent License. Subject to the terms and conditions of
+      this License, each Contributor hereby grants to You a perpetual,
+      worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+      (except as stated in this section) patent license to make, have made,
+      use, offer to sell, sell, import, and otherwise transfer the Work,
+      where such license applies only to those patent claims licensable
+      by such Contributor that are necessarily infringed by their
+      Contribution(s) alone or by combination of their Contribution(s)
+      with the Work to which such Contribution(s) was submitted. If You
+      institute patent litigation against any entity (including a
+      cross-claim or counterclaim in a lawsuit) alleging that the Work
+      or a Contribution incorporated within the Work constitutes direct
+      or contributory patent infringement, then any patent licenses
+      granted to You under this License for that Work shall terminate
+      as of the date such litigation is filed.
+
+   4. Redistribution. You may reproduce and distribute copies of the
+      Work or Derivative Works thereof in any medium, with or without
+      modifications, and in Source or Object form, provided that You
+      meet the following conditions:
+
+      (a) You must give any other recipients of the Work or
+          Derivative Works a copy of this License; and
+
+      (b) You must cause any modified files to carry prominent notices
+          stating that You changed the files; and
+
+      (c) You must retain, in the Source form of any Derivative Works
+          that You distribute, all copyright, patent, trademark, and
+          attribution notices from the Source form of the Work,
+          excluding those notices that do not pertain to any part of
+          the Derivative Works; and
+
+      (d) If the Work includes a "NOTICE" text file as part of its
+          distribution, then any Derivative Works that You distribute must
+          include a readable copy of the attribution notices contained
+          within such NOTICE file, excluding those notices that do not
+          pertain to any part of the Derivative Works, in at least one
+          of the following places: within a NOTICE text file distributed
+          as part of the Derivative Works; within the Source form or
+          documentation, if provided along with the Derivative Works; or,
+          within a display generated by the Derivative Works, if and
+          wherever such third-party notices normally appear. The contents
+          of the NOTICE file are for informational purposes only and
+          do not modify the License. You may add Your own attribution
+          notices within Derivative Works that You distribute, alongside
+          or as an addendum to the NOTICE text from the Work, provided
+          that such additional attribution notices cannot be construed
+          as modifying the License.
+
+      You may add Your own copyright statement to Your modifications and
+      may provide additional or different license terms and conditions
+      for use, reproduction, or distribution of Your modifications, or
+      for any such Derivative Works as a whole, provided Your use,
+      reproduction, and distribution of the Work otherwise complies with
+      the conditions stated in this License.
+
+   5. Submission of Contributions. Unless You explicitly state otherwise,
+      any Contribution intentionally submitted for inclusion in the Work
+      by You to the Licensor shall be under the terms and conditions of
+      this License, without any additional terms or conditions.
+      Notwithstanding the above, nothing herein shall supersede or modify
+      the terms of any separate license agreement you may have executed
+      with Licensor regarding such Contributions.
+
+   6. Trademarks. This License does not grant permission to use the trade
+      names, trademarks, service marks, or product names of the Licensor,
+      except as required for reasonable and customary use in describing the
+      origin of the Work and reproducing the content of the NOTICE file.
+
+   7. Disclaimer of Warranty. Unless required by applicable law or
+      agreed to in writing, Licensor provides the Work (and each
+      Contributor provides its Contributions) on an "AS IS" BASIS,
+      WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
+      implied, including, without limitation, any warranties or conditions
+      of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
+      PARTICULAR PURPOSE. You are solely responsible for determining the
+      appropriateness of using or redistributing the Work and assume any
+      risks associated with Your exercise of permissions under this License.
+
+   8. Limitation of Liability. In no event and under no legal theory,
+      whether in tort (including negligence), contract, or otherwise,
+      unless required by applicable law (such as deliberate and grossly
+      negligent acts) or agreed to in writing, shall any Contributor be
+      liable to You for damages, including any direct, indirect, special,
+      incidental, or consequential damages of any character arising as a
+      result of this License or out of the use or inability to use the
+      Work (including but not limited to damages for loss of goodwill,
+      work stoppage, computer failure or malfunction, or any and all
+      other commercial damages or losses), even if such Contributor
+      has been advised of the possibility of such damages.
+
+   9. Accepting Warranty or Additional Liability. While redistributing
+      the Work or Derivative Works thereof, You may choose to offer,
+      and charge a fee for, acceptance of support, warranty, indemnity,
+      or other liability obligations and/or rights consistent with this
+      License. However, in accepting such obligations, You may act only
+      on Your own behalf and on Your sole responsibility, not on behalf
+      of any other Contributor, and only if You agree to indemnify,
+      defend, and hold each Contributor harmless for any liability
+      incurred by, or claims asserted against, such Contributor by reason
+      of your accepting any such warranty or additional liability.
+
+   END OF TERMS AND CONDITIONS
+
+   Copyright 2018-2021 Sebastian Thiel, and [contributors](https://github.com/byron/gitoxide/contributors)
+
+   Licensed under the Apache License, Version 2.0 (the "License");
+   you may not use this file except in compliance with the License.
+   You may obtain a copy of the License at
+
+       http://www.apache.org/licenses/LICENSE-2.0
+
+   Unless required by applicable law or agreed to in writing, software
+   distributed under the License is distributed on an "AS IS" BASIS,
+   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+   See the License for the specific language governing permissions and
+   limitations under the License.
diff --git a/vendor/gix-revwalk/LICENSE-MIT b/vendor/gix-revwalk/LICENSE-MIT
new file mode 100644
index 000000000..b58e818f1
--- /dev/null
+++ b/vendor/gix-revwalk/LICENSE-MIT
@@ -0,0 +1,21 @@
+MIT License
+
+Copyright (c) 2018-2021 Sebastian Thiel, and [contributors](https://github.com/byron/gitoxide/contributors).
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all
+copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+SOFTWARE.
diff --git a/vendor/gix-revwalk/src/graph/commit.rs b/vendor/gix-revwalk/src/graph/commit.rs
new file mode 100644
index 000000000..e11a28e36
--- /dev/null
+++ b/vendor/gix-revwalk/src/graph/commit.rs
@@ -0,0 +1,149 @@
+use smallvec::SmallVec;
+
+use super::LazyCommit;
+use crate::graph::{Commit, CommitterTimestamp, Either, Generation};
+
+impl<'graph> LazyCommit<'graph> {
+    /// Return an iterator over the parents of this commit.
+    pub fn iter_parents(&self) -> Parents<'graph> {
+        let backing = match &self.backing {
+            Either::Left(buf) => Either::Left(gix_object::CommitRefIter::from_bytes(buf)),
+            Either::Right((cache, pos)) => Either::Right((*cache, cache.commit_at(*pos).iter_parents())),
+        };
+        Parents { backing }
+    }
+
+    /// Returns the timestamp at which this commit was created.
+    ///
+    /// This is the single-most important date for determining recency of commits.
+    /// Note that this can only fail if the commit is backed by the object database *and* parsing fails.
+    pub fn committer_timestamp(&self) -> Result<CommitterTimestamp, gix_object::decode::Error> {
+        Ok(match &self.backing {
+            Either::Left(buf) => {
+                gix_object::CommitRefIter::from_bytes(buf)
+                    .committer()?
+                    .time
+                    .seconds_since_unix_epoch as CommitterTimestamp
+            }
+            Either::Right((cache, pos)) => cache.commit_at(*pos).committer_timestamp(),
+        })
+    }
+
+    /// Returns the generation of the commit if it is backed by a commit graph.
+    pub fn generation(&self) -> Option<Generation> {
+        match &self.backing {
+            Either::Left(_) => None,
+            Either::Right((cache, pos)) => cache.commit_at(*pos).generation().into(),
+        }
+    }
+
+    /// Convert ourselves into an owned version, which effectively detaches us from the underlying graph.
+    /// Use `new_data()` to provide the `data` field for the owned `Commit`.
+    pub fn to_owned<T>(&self, new_data: impl FnOnce() -> T) -> Result<Commit<T>, to_owned::Error> {
+        let data = new_data();
+        Ok(match &self.backing {
+            Either::Left(buf) => {
+                use gix_object::commit::ref_iter::Token;
+                let iter = gix_object::CommitRefIter::from_bytes(buf);
+                let mut parents = SmallVec::default();
+                let mut timestamp = None;
+                for token in iter {
+                    match token? {
+                        Token::Tree { .. } => {}
+                        Token::Parent { id } => parents.push(id),
+                        Token::Author { .. } => {}
+                        Token::Committer { signature } => {
+                            timestamp = Some(signature.time.seconds_since_unix_epoch as CommitterTimestamp);
+                            break;
+                        }
+                        _ => {
+                            unreachable!(
+                                "we break naturally after seeing the committer which is always at the same spot"
+                            )
+                        }
+                    }
+                }
+                Commit {
+                    parents,
+                    commit_time: timestamp.unwrap_or_default(),
+                    generation: None,
+                    data,
+                }
+            }
+            Either::Right((cache, pos)) => {
+                let mut parents = SmallVec::default();
+                let commit = cache.commit_at(*pos);
+                for pos in commit.iter_parents() {
+                    let pos = pos?;
+                    parents.push(cache.commit_at(pos).id().to_owned());
+                }
+                Commit {
+                    parents,
+                    commit_time: commit.committer_timestamp(),
+                    generation: Some(commit.generation()),
+                    data,
+                }
+            }
+        })
+    }
+}
+
+/// An iterator over the parents of a commit.
+pub struct Parents<'graph> {
+    backing: Either<
+        gix_object::CommitRefIter<'graph>,
+        (
+            &'graph gix_commitgraph::Graph,
+            gix_commitgraph::file::commit::Parents<'graph>,
+        ),
+    >,
+}
+
+impl<'graph> Iterator for Parents<'graph> {
+    type Item = Result<gix_hash::ObjectId, iter_parents::Error>;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        match &mut self.backing {
+            Either::Left(it) => {
+                for token in it {
+                    match token {
+                        Ok(gix_object::commit::ref_iter::Token::Tree { .. }) => continue,
+                        Ok(gix_object::commit::ref_iter::Token::Parent { id }) => return Some(Ok(id)),
+                        Ok(_unused_token) => break,
+                        Err(err) => return Some(Err(err.into())),
+                    }
+                }
+                None
+            }
+            Either::Right((cache, it)) => it
+                .next()
+                .map(|r| r.map(|pos| cache.id_at(pos).to_owned()).map_err(Into::into)),
+        }
+    }
+}
+
+///
+pub mod iter_parents {
+    /// The error returned by the [`Parents`][super::Parents] iterator.
+    #[derive(Debug, thiserror::Error)]
+    #[allow(missing_docs)]
+    pub enum Error {
+        #[error("An error occurred when parsing commit parents")]
+        DecodeCommit(#[from] gix_object::decode::Error),
+        #[error("An error occurred when parsing parents from the commit graph")]
+        DecodeCommitGraph(#[from] gix_commitgraph::file::commit::Error),
+    }
+}
+
+///
+pub mod to_owned {
+    /// The error returned by [`to_owned()`][crate::graph::LazyCommit::to_owned()].
+    #[derive(Debug, thiserror::Error)]
+    #[allow(missing_docs)]
+    pub enum Error {
+        #[error("A commit could not be decoded during traversal")]
+        Decode(#[from] gix_object::decode::Error),
+        #[error("Could not find commit position in graph when traversing parents")]
+        CommitGraphParent(#[from] gix_commitgraph::file::commit::Error),
+    }
+}
diff --git a/vendor/gix-revwalk/src/graph/errors.rs b/vendor/gix-revwalk/src/graph/errors.rs
new file mode 100644
index 000000000..a2d849fbf
--- /dev/null
+++ b/vendor/gix-revwalk/src/graph/errors.rs
@@ -0,0 +1,53 @@
+///
+pub mod lookup {
+    /// The error returned by [`try_lookup()`][crate::Graph::try_lookup()].
+    #[derive(Debug, thiserror::Error)]
+    #[error("There was an error looking up a commit")]
+    pub struct Error {
+        #[from]
+        source: Box<dyn std::error::Error + Send + Sync + 'static>,
+    }
+
+    ///
+    pub mod commit {
+        /// The error returned by [`try_lookup_or_insert_commit()`][crate::Graph::try_lookup_or_insert_commit()].
+        #[derive(Debug, thiserror::Error)]
+        #[allow(missing_docs)]
+        pub enum Error {
+            #[error(transparent)]
+            Find(#[from] crate::graph::lookup::Error),
+            #[error(transparent)]
+            ToOwned(#[from] crate::graph::commit::to_owned::Error),
+        }
+    }
+
+    ///
+    pub mod existing {
+        /// The error returned by [`lookup()`][crate::Graph::lookup()].
+        #[derive(Debug, thiserror::Error)]
+        #[allow(missing_docs)]
+        pub enum Error {
+            #[error(transparent)]
+            Find(#[from] super::Error),
+            #[error("Commit could not be found")]
+            Missing,
+        }
+    }
+}
+
+///
+pub mod insert_parents {
+    use crate::graph::{commit::iter_parents, lookup};
+
+    /// The error returned by [`insert_parents()`][crate::Graph::insert_parents()].
+    #[derive(Debug, thiserror::Error)]
+    #[allow(missing_docs)]
+    pub enum Error {
+        #[error(transparent)]
+        Lookup(#[from] lookup::existing::Error),
+        #[error("A commit could not be decoded during traversal")]
+        Decode(#[from] gix_object::decode::Error),
+        #[error(transparent)]
+        Parent(#[from] iter_parents::Error),
+    }
+}
diff --git a/vendor/gix-revwalk/src/graph/mod.rs b/vendor/gix-revwalk/src/graph/mod.rs
new file mode 100644
index 000000000..cf7e1629e
--- /dev/null
+++ b/vendor/gix-revwalk/src/graph/mod.rs
@@ -0,0 +1,321 @@
+use std::{fmt::Formatter, ops::Index};
+
+use gix_hash::oid;
+use smallvec::SmallVec;
+
+use crate::Graph;
+
+///
+pub mod commit;
+
+mod errors;
+pub use errors::{insert_parents, lookup};
+
+/// The time in seconds since unix epoch at which a commit was created.
+pub type CommitterTimestamp = u64;
+
+/// The generation away from the HEAD of graph, useful to limit algorithms by topological depth as well.
+///
+/// 0 would mean the starting point of the hierarchy, and 1 their parents.
+/// This number is only available natively if there is a commit-graph.
+pub type Generation = u32;
+
+impl<'find, T: std::fmt::Debug> std::fmt::Debug for Graph<'find, T> {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        std::fmt::Debug::fmt(&self.set, f)
+    }
+}
+
+impl<'find, T: Default> Graph<'find, T> {
+    /// Lookup `id` without failing if the commit doesn't exist, and assure that `id` is inserted into our set.
+    /// If it wasn't, associate it with the default value. Assure `update_data(data)` gets run.
+    /// Return the commit when done.
+    /// Note that none of the data updates happen if there was no commit named `id`.
+    pub fn try_lookup_or_insert(
+        &mut self,
+        id: gix_hash::ObjectId,
+        update_data: impl FnOnce(&mut T),
+    ) -> Result<Option<LazyCommit<'_>>, lookup::Error> {
+        self.try_lookup_or_insert_default(id, T::default, update_data)
+    }
+}
+
+/// Access and mutation
+impl<'find, T> Graph<'find, T> {
+    /// Returns true if `id` has data associated with it, meaning that we processed it already.
+    pub fn contains(&self, id: &gix_hash::oid) -> bool {
+        self.set.contains_key(id.as_ref())
+    }
+
+    /// Returns the data associated with `id` if available.
+    pub fn get(&self, id: &gix_hash::oid) -> Option<&T> {
+        self.set.get(id)
+    }
+
+    /// Returns the data associated with `id` if available as mutable reference.
+    pub fn get_mut(&mut self, id: &gix_hash::oid) -> Option<&mut T> {
+        self.set.get_mut(id)
+    }
+
+    /// Insert `id` into the graph and associate it with `value`, returning the previous value associated with it if it existed.
+    pub fn insert(&mut self, id: gix_hash::ObjectId, value: T) -> Option<T> {
+        self.set.insert(id, value)
+    }
+
+    /// Remove all data from the graph to start over.
+    pub fn clear(&mut self) {
+        self.set.clear();
+    }
+
+    /// Insert the parents of commit named `id` to the graph and associate new parents with data
+    /// by calling `new_parent_data(parent_id, committer_timestamp)`, or update existing parents
+    /// data with `update_existing(parent_id, &mut existing_data)`.
+    /// If `first_parent` is `true`, only the first parent of commits will be looked at.
+    pub fn insert_parents(
+        &mut self,
+        id: &gix_hash::oid,
+        mut new_parent_data: impl FnMut(gix_hash::ObjectId, CommitterTimestamp) -> T,
+        mut update_existing: impl FnMut(gix_hash::ObjectId, &mut T),
+        first_parent: bool,
+    ) -> Result<(), insert_parents::Error> {
+        let commit = self.lookup(id)?;
+        let parents: SmallVec<[_; 2]> = commit.iter_parents().collect();
+        for parent_id in parents {
+            let parent_id = parent_id?;
+            match self.set.entry(parent_id) {
+                gix_hashtable::hash_map::Entry::Vacant(entry) => {
+                    let parent = match try_lookup(&parent_id, &mut self.find, self.cache.as_ref(), &mut self.parent_buf)
+                        .map_err(|err| insert_parents::Error::Lookup(lookup::existing::Error::Find(err)))?
+                    {
+                        Some(p) => p,
+                        None => continue, // skip missing objects, this is due to shallow clones for instance.
+                    };
+
+                    let parent_commit_date = parent.committer_timestamp().unwrap_or_default();
+                    entry.insert(new_parent_data(parent_id, parent_commit_date));
+                }
+                gix_hashtable::hash_map::Entry::Occupied(mut entry) => {
+                    update_existing(parent_id, entry.get_mut());
+                }
+            }
+            if first_parent {
+                break;
+            }
+        }
+        Ok(())
+    }
+}
+
+/// Initialization
+impl<'find, T> Graph<'find, T> {
+    /// Create a new instance with `find` to retrieve commits and optionally `cache` to accelerate commit access.
+    ///
+    /// ### Performance
+    ///
+    /// `find` should be optimized to access the same object repeatedly, ideally with an object cache to keep the last couple of
+    /// most recently used commits.
+    /// Furthermore, **none-existing commits should not trigger the pack-db to be refreshed.** Otherwise, performance may be sub-optimal
+    /// in shallow repositories as running into non-existing commits will trigger a refresh of the `packs` directory.
+    pub fn new<Find, E>(mut find: Find, cache: impl Into<Option<gix_commitgraph::Graph>>) -> Self
+    where
+        Find:
+            for<'a> FnMut(&gix_hash::oid, &'a mut Vec<u8>) -> Result<Option<gix_object::CommitRefIter<'a>>, E> + 'find,
+        E: std::error::Error + Send + Sync + 'static,
+    {
+        Graph {
+            find: Box::new(move |id, buf| {
+                find(id, buf).map_err(|err| Box::new(err) as Box<dyn std::error::Error + Send + Sync + 'static>)
+            }),
+            cache: cache.into(),
+            set: gix_hashtable::HashMap::default(),
+            buf: Vec::new(),
+            parent_buf: Vec::new(),
+        }
+    }
+}
+
+/// commit access
+impl<'find, T> Graph<'find, Commit<T>> {
+    /// Lookup `id` without failing if the commit doesn't exist, and assure that `id` is inserted into our set
+    /// with a commit with `new_data()` assigned.
+    /// `update_data(data)` gets run either on existing or on new data.
+    ///
+    /// Note that none of the data updates happen if `id` didn't exist.
+    pub fn try_lookup_or_insert_commit_default(
+        &mut self,
+        id: gix_hash::ObjectId,
+        new_data: impl FnOnce() -> T,
+        update_data: impl FnOnce(&mut T),
+    ) -> Result<Option<&mut Commit<T>>, lookup::commit::Error> {
+        match self.set.entry(id) {
+            gix_hashtable::hash_map::Entry::Vacant(entry) => {
+                let res = try_lookup(&id, &mut self.find, self.cache.as_ref(), &mut self.buf)?;
+                let commit = match res {
+                    None => return Ok(None),
+                    Some(commit) => commit,
+                };
+                let mut commit = commit.to_owned(new_data)?;
+                update_data(&mut commit.data);
+                entry.insert(commit);
+            }
+            gix_hashtable::hash_map::Entry::Occupied(mut entry) => {
+                update_data(&mut entry.get_mut().data);
+            }
+        };
+        Ok(self.set.get_mut(&id))
+    }
+}
+
+/// commit access
+impl<'find, T: Default> Graph<'find, Commit<T>> {
+    /// Lookup `id` without failing if the commit doesn't exist, and assure that `id` is inserted into our set
+    /// with a commit and default data assigned.
+    /// `update_data(data)` gets run either on existing or on new data.
+    ///
+    /// Note that none of the data updates happen if `id` didn't exist.
+    ///
+    /// If only commit data is desired without the need for attaching custom data, use
+    /// [`try_lookup(id).to_owned()`][Graph::try_lookup()] instead.
+    pub fn try_lookup_or_insert_commit(
+        &mut self,
+        id: gix_hash::ObjectId,
+        update_data: impl FnOnce(&mut T),
+    ) -> Result<Option<&mut Commit<T>>, lookup::commit::Error> {
+        self.try_lookup_or_insert_commit_default(id, T::default, update_data)
+    }
+}
+
+/// Lazy commit access
+impl<'find, T> Graph<'find, T> {
+    /// Lookup `id` without failing if the commit doesn't exist, and assure that `id` is inserted into our set
+    /// with a `default` value assigned to it.
+    /// `update_data(data)` gets run either on existing or no new data.
+    /// Return the commit when done.
+    ///
+    /// Note that none of the data updates happen if `id` didn't exist.
+    ///
+    /// If only commit data is desired without the need for attaching custom data, use
+    /// [`try_lookup(id)`][Graph::try_lookup()] instead.
+    pub fn try_lookup_or_insert_default(
+        &mut self,
+        id: gix_hash::ObjectId,
+        default: impl FnOnce() -> T,
+        update_data: impl FnOnce(&mut T),
+    ) -> Result<Option<LazyCommit<'_>>, lookup::Error> {
+        let res = try_lookup(&id, &mut self.find, self.cache.as_ref(), &mut self.buf)?;
+        Ok(res.map(|commit| {
+            match self.set.entry(id) {
+                gix_hashtable::hash_map::Entry::Vacant(entry) => {
+                    let mut data = default();
+                    update_data(&mut data);
+                    entry.insert(data);
+                }
+                gix_hashtable::hash_map::Entry::Occupied(mut entry) => {
+                    update_data(entry.get_mut());
+                }
+            };
+            commit
+        }))
+    }
+
+    /// Try to lookup `id` and return a handle to it for accessing its data, but don't fail if the commit doesn't exist.
+    ///
+    /// It's possible that commits don't exist if the repository is shallow.
+    pub fn try_lookup(&mut self, id: &gix_hash::oid) -> Result<Option<LazyCommit<'_>>, lookup::Error> {
+        try_lookup(id, &mut self.find, self.cache.as_ref(), &mut self.buf)
+    }
+
+    /// Lookup `id` and return a handle to it, or fail if it doesn't exist.
+    pub fn lookup(&mut self, id: &gix_hash::oid) -> Result<LazyCommit<'_>, lookup::existing::Error> {
+        self.try_lookup(id)?.ok_or(lookup::existing::Error::Missing)
+    }
+}
+
+fn try_lookup<'graph>(
+    id: &gix_hash::oid,
+    find: &mut Box<FindFn<'_>>,
+    cache: Option<&'graph gix_commitgraph::Graph>,
+    buf: &'graph mut Vec<u8>,
+) -> Result<Option<LazyCommit<'graph>>, lookup::Error> {
+    if let Some(cache) = cache {
+        if let Some(pos) = cache.lookup(id) {
+            return Ok(Some(LazyCommit {
+                backing: Either::Right((cache, pos)),
+            }));
+        }
+    }
+    #[allow(clippy::manual_map)]
+    Ok(match find(id, buf)? {
+        Some(_) => Some(LazyCommit {
+            backing: Either::Left(buf),
+        }),
+        None => None,
+    })
+}
+
+impl<'a, 'find, T> Index<&'a gix_hash::oid> for Graph<'find, T> {
+    type Output = T;
+
+    fn index(&self, index: &'a oid) -> &Self::Output {
+        &self.set[index]
+    }
+}
+
+/// A commit that contains all information we can obtain through the commit-graph, which is typically enough to fuel any graph iteration.
+pub struct Commit<T> {
+    /// The parents of the commit.
+    pub parents: SmallVec<[gix_hash::ObjectId; 1]>,
+    /// The time at which the commit was created.
+    pub commit_time: CommitterTimestamp,
+    /// The generation of the commit, if available.
+    pub generation: Option<u32>,
+    /// Any kind of data to associate with this commit.
+    pub data: T,
+}
+
+impl<T> std::fmt::Debug for Commit<T>
+where
+    T: std::fmt::Debug,
+{
+    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
+        f.debug_struct("Commit")
+            .field("parents", &self.parents)
+            .field("commit_time", &self.commit_time)
+            .field("generation", &self.generation)
+            .field("data", &self.data)
+            .finish()
+    }
+}
+
+impl<T> Clone for Commit<T>
+where
+    T: Clone,
+{
+    fn clone(&self) -> Self {
+        Commit {
+            parents: self.parents.clone(),
+            commit_time: self.commit_time,
+            generation: self.generation,
+            data: self.data.clone(),
+        }
+    }
+}
+
+/// A commit that provides access to graph-related information, on demand.
+///
+/// The owned version of this type is called [`Commit`] and can be obtained by calling [`LazyCommit::to_owned()`].
+pub struct LazyCommit<'graph> {
+    backing: Either<&'graph [u8], (&'graph gix_commitgraph::Graph, gix_commitgraph::Position)>,
+}
+
+pub(crate) type FindFn<'find> = dyn for<'a> FnMut(
+        &gix_hash::oid,
+        &'a mut Vec<u8>,
+    )
+        -> Result<Option<gix_object::CommitRefIter<'a>>, Box<dyn std::error::Error + Send + Sync + 'static>>
+    + 'find;
+
+enum Either<T, U> {
+    Left(T),
+    Right(U),
+}
diff --git a/vendor/gix-revwalk/src/lib.rs b/vendor/gix-revwalk/src/lib.rs
new file mode 100644
index 000000000..44c5ca3e7
--- /dev/null
+++ b/vendor/gix-revwalk/src/lib.rs
@@ -0,0 +1,49 @@
+//! Utility types for traversing the git commit-graph.
+//!
+//! This crate considers itself very much *plumbing* and is meant for consumption by other plumbing crates.
+#![deny(missing_docs, rust_2018_idioms)]
+#![forbid(unsafe_code)]
+
+/// A graph of commits which additionally allows to associate data with commits.
+///
+/// It starts empty, but each access may fill it with commit information.
+/// Note that the traversal can be accelerated if a [commit-graph][gix_commitgraph::Graph] is also made available.
+///
+/// ### About replacements
+///
+/// Object replacements is an object database feature to substitute one object with another. We assume that this is transparently
+/// implemented by the `find` function that returns objects. Also we assume that the commitgraph as been written with replacements
+/// active to provide a consistent view.
+///
+/// ### Odb or `find` configuration
+///
+/// The `find` handle should be setup to *quickly determine if an object exists or not* to assure quick operation *on shallow repositories*.
+/// This typically means that it should not re-read the odb if there is an object miss.
+///
+/// Most usage of the Graph will benefit from fast ODB lookups, so setting up an object cache will be beneficial. If that's not the case,
+/// the method docs will inform about that.
+///
+/// Additionally, and only if `T` is [`Commit<T>`][graph::Commit], there is *no need for an object cache* as we keep track of
+/// everything related to commit traversal in our own hashmap.
+pub struct Graph<'find, T> {
+    /// A way to resolve a commit from the object database.
+    find: Box<graph::FindFn<'find>>,
+    /// A way to speedup commit access, essentially a multi-file commit database.
+    cache: Option<gix_commitgraph::Graph>,
+    /// The set of cached commits that we have seen once, along with data associated with them.
+    set: gix_hashtable::HashMap<gix_hash::ObjectId, T>,
+    /// A buffer for writing commit data into.
+    buf: Vec<u8>,
+    /// Another buffer we typically use to store parents.
+    parent_buf: Vec<u8>,
+}
+///
+pub mod graph;
+
+/// A utility type implementing a queue which can be used to automatically sort data by its time in ascending order.
+///
+/// Note that the performance of this queue is very relevant to overall algorithm performance of many graph-walking algorithms,
+/// and as it stands our implementation is about 6% slower in practice, probably also depending on the size of the stored data.
+#[derive(Default)]
+pub struct PriorityQueue<K: Ord, T>(std::collections::BinaryHeap<queue::Item<K, T>>);
+mod queue;
diff --git a/vendor/gix-revwalk/src/queue.rs b/vendor/gix-revwalk/src/queue.rs
new file mode 100644
index 000000000..1c7938965
--- /dev/null
+++ b/vendor/gix-revwalk/src/queue.rs
@@ -0,0 +1,119 @@
+use std::{cmp::Ordering, collections::BinaryHeap};
+
+use crate::PriorityQueue;
+
+pub(crate) struct Item<K, T> {
+    key: K,
+    value: T,
+}
+
+impl<K: Ord + std::fmt::Debug, T: std::fmt::Debug> std::fmt::Debug for Item<K, T> {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        write!(f, "({:?}: {:?})", self.key, self.value)
+    }
+}
+
+impl<K: Ord + std::fmt::Debug, T: std::fmt::Debug> std::fmt::Debug for PriorityQueue<K, T> {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        std::fmt::Debug::fmt(&self.0, f)
+    }
+}
+
+impl<K: Ord, T> PartialEq<Self> for Item<K, T> {
+    fn eq(&self, other: &Self) -> bool {
+        Ord::cmp(self, other).is_eq()
+    }
+}
+
+impl<K: Ord, T> Eq for Item<K, T> {}
+
+impl<K: Ord, T> PartialOrd<Self> for Item<K, T> {
+    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+        Ord::cmp(self, other).into()
+    }
+}
+
+impl<K: Ord, T> Ord for Item<K, T> {
+    fn cmp(&self, other: &Self) -> Ordering {
+        self.key.cmp(&other.key)
+    }
+}
+
+impl<K, T> Clone for Item<K, T>
+where
+    K: Clone,
+    T: Clone,
+{
+    fn clone(&self) -> Self {
+        Item {
+            key: self.key.clone(),
+            value: self.value.clone(),
+        }
+    }
+}
+
+impl<K, T> Clone for PriorityQueue<K, T>
+where
+    K: Clone + Ord,
+    T: Clone,
+{
+    fn clone(&self) -> Self {
+        Self(self.0.clone())
+    }
+}
+
+impl<K: Ord, T> PriorityQueue<K, T> {
+    /// Create a new instance.
+    pub fn new() -> Self {
+        PriorityQueue(Default::default())
+    }
+    /// Insert `value` so that it is ordered according to `key`.
+    pub fn insert(&mut self, key: K, value: T) {
+        self.0.push(Item { key, value });
+    }
+
+    /// Pop the highest-priority item value off the queue.
+    pub fn pop_value(&mut self) -> Option<T> {
+        self.0.pop().map(|t| t.value)
+    }
+
+    /// Pop the highest-priority item key and value off the queue.
+    pub fn pop(&mut self) -> Option<(K, T)> {
+        self.0.pop().map(|t| (t.key, t.value))
+    }
+
+    /// Iterate all items ordered from highest to lowest priority.
+    pub fn iter_unordered(&self) -> impl Iterator<Item = &T> {
+        self.0.iter().map(|t| &t.value)
+    }
+
+    /// Turn this instance into an iterator over its keys and values in arbitrary order.
+    pub fn into_iter_unordered(self) -> impl Iterator<Item = (K, T)> {
+        self.0.into_vec().into_iter().map(|item| (item.key, item.value))
+    }
+
+    /// Return true if the queue is empty.
+    pub fn is_empty(&self) -> bool {
+        self.0.is_empty()
+    }
+
+    /// Returns the greatest item `(K, T)` tuple, as ordered by `K`, if the queue is not empty, without removing it.
+    pub fn peek(&self) -> Option<(&K, &T)> {
+        self.0.peek().map(|e| (&e.key, &e.value))
+    }
+
+    /// Drop all items from the queue, without changing its capacity.
+    pub fn clear(&mut self) {
+        self.0.clear()
+    }
+}
+
+impl<K: Ord, T> FromIterator<(K, T)> for PriorityQueue<K, T> {
+    fn from_iter<I: IntoIterator<Item = (K, T)>>(iter: I) -> Self {
+        let mut q = PriorityQueue(BinaryHeap::new());
+        for (k, v) in iter {
+            q.insert(k, v);
+        }
+        q
+    }
+}